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

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

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

?

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

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

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

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

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

0 引 言

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

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

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

1 相關工作

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

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

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

圖1 提出方法的概述

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

2 基于CDT的三維格網重建

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

2.1 2D約束德勞內三角化

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

2.1.1 直線提取

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

圖2 線段LSD及超級像素

2.1.2 超級像素

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

2.1.3 邊緣多邊形簡化

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

圖3 超級像素邊緣簡化

2.1.4 2D CDT

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

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

圖4 通過所得直線段及頂點構造2D CDT

2.2 單視圖三維Mesh重建

(1)

(2)

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

圖5 3D Mesh及其貼圖

2.3 多視圖Mesh合并

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

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

3 實驗與結果分析

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

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

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

輸入數據GSLICLSD2DCDT3DCDT耗時/s5.22.31.76.1

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

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

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

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

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

圖10 本文方法和泊松重構效果對比

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

圖11 兩個數據集重建結果圖

4 結 語

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

[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].計算機工程與設計,2015(12):3291-3296.

[4] 羅宇,宋歌,楊紅雨.基于圖像識別的建筑物三維重建[J].計算機工程與設計,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。馮文雯，碩士，主研領域：計算機視覺。陳珝玥，碩士。余虹亮，碩士。歐元漢，副教授。

TP391

A

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