馮文雯 陳珝玥 余虹亮 歐元漢

1(廣西大學(xué)計算機與電子信息學(xué)院 廣西 南寧 530004)2(南寧有無科技有限公司 廣西 南寧 530007)

?

基于約束Delaunay三角形的多視3D重建

馮文雯1陳珝玥2余虹亮1歐元漢1

1(廣西大學(xué)計算機與電子信息學(xué)院 廣西 南寧 530004)2(南寧有無科技有限公司 廣西 南寧 530007)

為解決多視立體重建的表面模型扭曲變形，建筑物平面凹凸不平進(jìn)而造成紋理貼圖出現(xiàn)錯誤和拉花的問題，提出一種加入直線約束的城市建筑三維重建方法。該方法使用無人機獲得的一系列圖片作為輸入，首先通過直線檢測器和超級像素提取圖像直線段和邊緣，經(jīng)邊緣多邊形簡化，再通過2D約束德勞內(nèi)三角化得到單視圖2D三角格網(wǎng)。然后根據(jù)密集點云回算2D三角格網(wǎng)頂點三維位置，得到單視圖3D格網(wǎng)模型，最后多視圖合并得到場景完整3D模型。實驗結(jié)果表明，算法表現(xiàn)出較好的性能、穩(wěn)定性和可擴展性，并且具有較高精確性和有效性。

約束Delaunay三角形 LSD 超級像素 多邊形精簡 多視立體重建

0 引 言

大規(guī)模城市場景3D重建在計算機視覺和圖形學(xué)領(lǐng)域一直以來都有著迫切的需求并應(yīng)用于城市規(guī)劃、導(dǎo)航、文化遺產(chǎn)等領(lǐng)域。谷歌、微軟和蘋果的地圖產(chǎn)品已相繼開始提供部分城市級別的3D模型數(shù)據(jù)，這都得益于多視立體三維重建MVS(Multiple View Stereo) 技術(shù)的迅速發(fā)展。MVS重建流程通常由運動獲取結(jié)構(gòu)SFM(Structure From Motion)計算相機位置參數(shù)、密集點云生成和表面模型重建3個步驟組成，其重建精度接近激光雷達(dá)[1]，但模型的視覺效果還存在許多改善的空間[2]。當(dāng)應(yīng)用于真實城市場景建模時由于大量平面缺乏紋理使得MVS點云重建的誤差增大，進(jìn)而導(dǎo)致表面模型扭曲變形，造成紋理貼圖出現(xiàn)錯誤和拉花現(xiàn)象。

觀察到城市場景中存在大量直線段，直線的斷續(xù)和扭曲是重建模型視覺效果變差的主要原因，若能在3D重建過程中加入直線段約束將會顯著改善上述問題。城市場景三維線段重建已有一些工作[3-5]，但其所得三維直線只是作為中間數(shù)據(jù)，而非完整的三維表面重建結(jié)果，也無紋理貼圖。

本文以大范圍城市場景三維建模為應(yīng)用背景，針對MVS模型扭曲變形的問題以重現(xiàn)城市建筑模型線條美為目標(biāo)，基于圖像的直線段建立2D約束德勞內(nèi)三角格網(wǎng)2D CDT(2D Constraint Delaunay Triangle)[6]，結(jié)合三維點云構(gòu)造單幅視圖的3D CDT，再使用圖割優(yōu)化方法選取表面模型對應(yīng)的最佳視圖，最終合并生成完整三維格網(wǎng)模型。

1 相關(guān)工作

MVS三維重建的研究多是針對單個物件，近十年出現(xiàn)了不少出色的成果[1]，但仍然面臨許多挑戰(zhàn)，視覺效果不佳是其中迫切需要解決的難題。目前標(biāo)準(zhǔn)的MVS流程是以文獻(xiàn)[7]為代表的PMVS+PSR方案，即通過多視密集匹配生成三維點云，再基于點云使用泊松重構(gòu)求解表面模型。該類方法得到的模型精度處于領(lǐng)先地位，但模型視覺效果并不理想，無法適用于城市建筑的重建。為得到更好的城市三維效果，對模型進(jìn)行曼哈頓約束[8]能夠得到建筑模型橫平豎直的重建效果，但欠缺通用性。對模型進(jìn)行平面提取等后處理[9]考慮了建筑物多平面的特征，但對于城市植被的重建效果欠佳。

PMVS+PSR流程的關(guān)鍵是精確、完整的密集點云生成，與此不同的另一類方法是快速生成不精確但足夠完整的點云。先構(gòu)造初始化粗糙Mesh，再根據(jù)多視重投影誤差最小化進(jìn)一步精細(xì)化初始模型[10]。這類方法是目前精度和視覺效果兼顧最好的，法國Acute3D公司的Smart3DCpature(后簡稱S3D)是領(lǐng)先的MVS建模軟件，其核心算法也屬于此類，但計算量大，且由于SFM過程的相機參數(shù)回算不夠準(zhǔn)確，Mesh精細(xì)化過程會對三角面片進(jìn)行誤差分配，造成模型的扭曲和起伏。沿用Mesh精細(xì)化的思路，Takayuki Sugiura等[11]加入3D直線改善模型效果，缺點是重建3D線段增加了復(fù)雜性和局限性。

本文方法是提取圖像的超級像素并獲取場景細(xì)分平面利用超級像素邊緣作為三角面片的邊，同時加入直線約束，能夠應(yīng)對人工建筑或自然景觀等多種場景。方法受到文獻(xiàn)[2,12]的啟發(fā)，與前者相比，并非將每個超級像素直接去回算3D空間的一個平面，而是將超級像素邊緣作為三角面片的邊，不再需要對平面做進(jìn)一步的表面模型求解；與后者相比，引用了直線約束而非單純使用超級像素，這樣的改變對城市建筑重建效果的改善起著關(guān)鍵作用，如圖1所示。

圖1 提出方法的概述

本文方法有3個特點。首先，單視圖足夠表示其主要可視場景，并能夠使模型在對應(yīng)視角觀察的視覺最大化接近照片效果。雖然通過多視圖優(yōu)化能小幅提高重建精度，卻因為需在各視圖中平均分配誤差，造成直線的變形。其次，單視圖重建再合并的技術(shù)路線本質(zhì)上是一種低耦合的輕量并行思想，非常適合大范圍城市三維重建。最后，表面模型的三角面片直接來源于圖像的2D CDT，圖像中的直線段構(gòu)成三角面片的邊不會造成斷續(xù)、扭曲，能夠改善重建模型的視覺效果。

2 基于CDT的三維格網(wǎng)重建

本文方法包含3個步驟:(1) 基于圖像線段的二維約束德勞內(nèi)三角化；(2) 單視圖三維Mesh重建；(3) 多視圖Mesh合并。

2.1 2D約束德勞內(nèi)三角化

本文方法的關(guān)鍵在于將圖像中的直線約束加入到表面模型的三角格網(wǎng)中，并盡可能讓三角格網(wǎng)的邊與圖像中的邊緣對應(yīng)起來以改善MVS表面模型中的扭曲變形。因此，采用的約束德勞內(nèi)三角化方法是基于圖像直線段和邊緣構(gòu)造2D三角格網(wǎng)。對于線段和點的輸入集合，約束德勞內(nèi)三角化以輸入線段作為三角格網(wǎng)的邊，輸入點作為三角格網(wǎng)頂點，構(gòu)造德勞內(nèi)三角格網(wǎng)，稱為約束德勞內(nèi)三角格網(wǎng)，即CDT。

2.1.1 直線提取

直線提取可以采用經(jīng)典的Hough變換方法，考慮到大場景二維線段提取，本文采用LSD(line segment detector)[13]方法對圖像進(jìn)行直線檢測。LSD是一種高效、無參數(shù)的直線檢測方法，能對具有同一梯度方向的像素幾何應(yīng)用最小二乘法估計線段的方向和端點能夠?qū)Ω叻直媛蕡D像提取直線段，適合針對大場景的線段提取。如圖2(a)所示。

圖2 線段LSD及超級像素

2.1.2 超級像素

圖像中的邊緣位置通常對應(yīng)場景深度的斷續(xù)，因此將Mesh的邊落在圖像的邊緣能夠改善3D模型的準(zhǔn)確度和視覺效果。邊緣提取有許多經(jīng)典算法，如sobel、canny等，考慮到大范圍城市場景的數(shù)據(jù)源多為超高分辨率的航拍照片，邊緣提取效率是需要首先考慮的因素，因此本文采用GPU超級像素GSLIC[14]方法，獲取圖像邊緣點，如圖2(b)所示。

2.1.3 邊緣多邊形簡化

超級像素能夠快速提取圖像中的邊緣點，Mesh的邊是線段，兩者要對應(yīng)起來，需要對超級像素邊界進(jìn)行多邊形簡化。Douglas-Peucker[15]算法通過計算頂點到邊的距離，以確定哪些點能夠簡化為一條邊，得到簡化多邊形，圖3是使用5個像素容忍度的超級像素邊緣多邊形簡化結(jié)果。

圖3 超級像素邊緣簡化

2.1.4 2D CDT

直線段和超級像素邊緣往往會有重合需要進(jìn)行去冗余處理并保證直線約束的優(yōu)先級，即刪除距離直線段太近的多邊形頂點。此處以直線為中軸外擴4個像素的矩形范圍內(nèi)的頂點做刪除得到直線段和最終參與構(gòu)造CDT的頂點，如圖4(a)所示。

約束德勞內(nèi)三角化是對包含n個頂點和非交叉邊按以下約束進(jìn)行三角化：(1) 預(yù)先指定的邊包含在三角劃分中，(2) 盡可能接近德勞內(nèi)三角剖分，即CDT是加了約束條件(預(yù)先指定的點和線)的德勞內(nèi)三角形。上述過程中提取的線段和去冗余后多邊形的頂點作為輸入得到2D CDT如圖4(b)所示。

圖4 通過所得直線段及頂點構(gòu)造2D CDT

2.2 單視圖三維Mesh重建

(1)

(2)

這是一個稀疏線性V×V系統(tǒng)(V是頂點數(shù)目)，通過常規(guī)線性系統(tǒng)求解方法即可高效得解，所得3D Mesh如圖5所示。

圖5 3D Mesh及其貼圖

2.3 多視圖Mesh合并

對每個視圖重構(gòu)得到的3D Mesh進(jìn)行合并得到完整的三維表面模型?；趫D像加入直線約束并擬合GCP得到的3D Mesh很好地表現(xiàn)了建筑物的直線條，并抑制了常用泊松表面重構(gòu)算法對模型的平滑。此處直接將所有單視圖3D Mesh的頂點合并如圖6所示，采用文獻(xiàn)[16]的方法，先對三維頂點集合構(gòu)造德勞內(nèi)四面體，再使用圖割優(yōu)化[17]標(biāo)記出內(nèi)外兩類四面體，內(nèi)、外四面體交界處，即為最終的表面模型。

圖6 單視圖頂點及多視圖合并頂點

3 實驗與結(jié)果分析

本文使用C++編程實現(xiàn)基于約束德勞內(nèi)三角形的多視三維重建方法，涉及的開源庫包括OpenCV、CGAL、boost和Eigen。其中，OpenCV用于圖像讀取基本操作、直線提取，使用boost進(jìn)行多邊形精簡，CGAL構(gòu)造2D CDT及相關(guān)mesh操作，Eigen求解線性系統(tǒng)。硬件環(huán)境為Intel(R) Xeon(R)CPU E5-16200 V3 @3.50 GHz，16 GB內(nèi)存的臺式機上，編程環(huán)境是Visual Studio 2013。

本文方法針對城市規(guī)模場景，實驗數(shù)據(jù)集選用無人機獲取的55張2 400萬像素航拍照片。SFM相機自檢校過程使用VisualSFM[18]，PMVS[19]密集點云生成，然后使用本文方法得到三維表面模型，結(jié)果如圖7所示，單視圖重建主要步驟(單張平均)耗時見表1所示。

圖7 本文方法得到3D模型過程

輸入數(shù)據(jù)GSLICLSD2DCDT3DCDT耗時/s5.22.31.76.1

圖8是本文方法與常用重建方法PMVS+PSR的結(jié)果對比，可以看出后者對城市建筑產(chǎn)生了過平滑，細(xì)節(jié)缺失，而本文方法則有了較好的改善。

圖8 本文方法與PMVS+PSR對比

S3D是當(dāng)前公認(rèn)效果最好的商業(yè)軟件，此處以同樣的數(shù)據(jù)集，使用S3D最高精度選項進(jìn)行對比實驗，如圖9所示。實驗結(jié)果表明本文方法與S3D的結(jié)果已經(jīng)相當(dāng)接近，而對于紋理貼圖模型可以看到本文結(jié)果的扭曲、拉花缺陷略少。

圖9 S3D方法與本文方法對比

我們使用30張像素為2 400萬的照片作為輸入獲得密集點云，對軟件S3D進(jìn)行最高精度設(shè)置建立基準(zhǔn)模型。通過本文方法和泊松重構(gòu)獲得的模型分別與基準(zhǔn)模型進(jìn)行精度測量。如圖10中(a)、(b)分別為本文建模和泊松重構(gòu)精度測量結(jié)果，(c)表示顏色誤差分布，顏色越深誤差越大，明顯看出本文建模算法效果高于傳統(tǒng)泊松重構(gòu)效果；(d)是本文方法和泊松重構(gòu)誤差分布情況，橫坐標(biāo)是誤差，縱坐標(biāo)是誤差點數(shù)占總點數(shù)的百分比。本文方法全部點最大誤差在0.1 m左右范圍內(nèi)這體現(xiàn)了本方法的完整性和精確性，而泊松重構(gòu)70%以上的點誤差大于1.5 m。事實證明本文重建模型比傳統(tǒng)泊松重構(gòu)建模效果更好。

圖10 本文方法和泊松重構(gòu)效果對比

此外，針對城市建筑，還使用本文方法進(jìn)行了多個數(shù)據(jù)集的實驗，照片像素均為2 400萬，如圖11所示。

圖11 兩個數(shù)據(jù)集重建結(jié)果圖

4 結(jié) 語

本文針對城市建筑物3D模型重建提出與傳統(tǒng)三維建模(輸入航拍圖片-SFM相機姿態(tài)估計-密集點云重建-表面重建得到表面網(wǎng)格模型-貼圖)不同思路的三維建模方式，其基于約束Delaunay三角形的多視圖3D重建算法。該算法經(jīng)2D約束Delaunay三角化獲得單視圖2D CDT，降低了復(fù)雜度且提高了模型重建精度，通過密集點云回算2D CDT頂點三維信息得到單視圖3D格網(wǎng)，最后通過多視圖合并構(gòu)建城市建筑3D模型。實驗結(jié)果表明，本文重建模型有較好的適用性和可擴展性，與傳統(tǒng)方法相比改善了視覺效果。在后續(xù)工作中，我們將對建筑物2D和3D Mesh進(jìn)一步優(yōu)化調(diào)整，期待得到速度更快、視覺效果更好的格網(wǎng)模型。

[1] Seitz S M,Curless B,Diebel J,et al.A comparison and evaluation of multi-view stereo reconstruction algorithms[C]//Computer vision and pattern recognition,2006 IEEE Computer Society Conference on.IEEE,2006,1:519-528.

[3] 歐元漢,黃鴻,陸宇海.基于密集點云重投影的三維線段模型重建算法[J].計算機工程與設(shè)計,2015(12):3291-3296.

[4] 羅宇,宋歌,楊紅雨.基于圖像識別的建筑物三維重建[J].計算機工程與設(shè)計,2015,36(1):191-196.

[5] Hofer M,Wendel A,Bischof H.Line-based 3D reconstruction of wiry objects[C]//Computer Vision Winter Workshop (CVWW),2013.

[6] Qi M,Cao T T,Tan T S.Computing 2D constrained Delaunay triangulation using the GPU[J].Visualization and Computer Graphics,IEEE Transactions on,2013,19(5):736-748.

[7] Furukawa Y,Ponce J.Accurate,dense,and robust multiview stereopsis[J].Pattern Analysis and Machine Intelligence,IEEE Transactions on,2010,32(8):1362-1376.

[8] Furukawa Y,Curless B,Seitz S M,et al.Reconstructing building interiors from images[C]//Computer Vision,2009 IEEE 12th International Conference on.IEEE,2009:80-87.

[9] Gallup D,Frahm J M,Mordohai P,et al.Real-time plane-sweeping stereo with multiple sweeping directions[C]//Computer Vision and Pattern Recognition,2007.CVPR’07.IEEE Conference on.IEEE,2007:1-8.

[10] Vu H H,Labatut P,Pons J P,et al.High accuracy and visibility-consistent dense multiview stereo[J].Pattern Analysis and Machine Intelligence,IEEE Transactions on,2012,34(5):889-901.

[11] Sugiura T,Torii A,Okutomi M.3D surface reconstruction from point-and-line cloud[C]//3D Vision (3DV),2015 International Conference on.IEEE,2015:264-272.

[12] Bódis-Szomorú A,Riemenschneider H,Van Gool L.Superpixel meshes for fast edge-preserving surface reconstruction[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,2015:2011-2020.

[13] Gioi R G V,Jakubowicz J,Morel J M,et al.LSD:A line segment detector[J].Image Processing on Line,2012,2(4):35-55.

[14] Ren C Y,Reid I.gSLIC:a real-time implementation of SLIC superpixel segmentation[R].University of Oxford,Department of Engineering,Technical Report,2011.

[15] Park J H,Jang B J,Kwon O J,et al.Vector Map Data compression based on Douglas Peucker Simplification Algorithm and Bin Classification[J].Journal of Korea Multimedia Society,2015,18(3):298-311.

[16] Jancosek M,Pajdla T.Exploiting visibility information in surface reconstruction to preserve weakly supported surfaces[J].International Scholarly Research Notices,2014,2014:1-20.

[17] Sinha S N,Mordohai P,Pollefeys M.Multi-view stereo via graph cuts on the dual of an adaptive tetrahedral mesh[C]//Computer Vision,2007.ICCV 2007.IEEE 11th International Conference on.IEEE,2007:1-8.

[18] Wu C.VisualSFM:A visual structure from motion system[Z].2011.

[19] Li Z,Wang K,Zuo W,et al.Detail-preserving and Content-aware Variational Multi-view Stereo Reconstruction[J].Image Processing,IEEE Transactions on,2016,25(2):864-877.

MULTI-VIEW 3D RECONSTRUCTION BASED ON CONSTRAINT DELAUNAY TRIANGLE

Feng Wenwen1Chen Xuyue2Yu Hongliang1Ou Yuanhan1

1(CollegeofComputerScienceandElectronicInformation,GuangxiUniversity,Nanning530004,Guangxi,China)2(YouWuCo.,Ltd,Nanning530007,Guangxi,China)

In order to solve the problem that the surface model of multi-view-stereo reconstruction is distorted and the plane of the building is uneven, which causes the error of texture mapping and garland, a method of 3D reconstruction of urban buildings with linear constraint is proposed. The method uses a series of pictures obtained by the UAV as input. Firstly, straight line segment and edge are extracted by line segment detector and super-pixel. After the polygon simplified, 2D single triangle 2D mesh is obtained by 2D constrained Delaunay triangulation. Then, according to the dense point cloud, the 3D position of 2D triangular mesh vertex is back-calculated, and the single view 3D mesh model is obtained. Finally, the multi-view merges to obtain the complete scene 3D model. The experimental results show that the proposed algorithm has good performance, stability and expansibility, and has high accuracy and efficiency.

Constraint Delaunay triangle LSD Super-pixel Polygon simplification Multi-view stereo reconstruction

2016-07-13。馮文雯，碩士，主研領(lǐng)域：計算機視覺。陳珝玥，碩士。余虹亮，碩士。歐元漢，副教授。

TP391

A

10.3969/j.issn.1000-386x.2017.07.023