以多幅圖像非幾何約束線段匹配重建建筑物外立面三維線段模型

張琳彥，朱利

（1. 西安交通大學電子與信息工程學院，710049，西安；2. 西安交通大學軟件學院，710049，西安）

傳統上基于圖像的建筑物外立面三維重建得到的是三維點云模型，但點特征卻缺乏描述場景整體結構的能力[1-2]。人工建筑物場景的框架主要由線段構成，建筑物外立面三維線段重建，就是通過獲取建筑物外立面的二維線段在空間中的三維信息得到其三維線段模型。如圖 1所示，該建筑物的三維點云模型在缺少紋理的地方重建精度較差，而三維線段模型卻能提供更充分的結構信息，反映場景的幾何拓撲關系[3]。

建筑物外立面三維線段重建大體分為 3步，首先提取圖像中的特征線段，再匹配特征線段，最后根據匹配線段之間的對應關系重建出目標建筑物的三維線段模型。

圖1 三維點云模型與三維線段模型

特征線段的提取主要針對構成建筑物結構信息的邊界。，LSD(Line Segment Detector)[4]是目前較穩定的線段提取算法，該算法具有錯誤控制功能，保證了線段檢測結果的正確性。

特征線段匹配是在提取到的特征線段中，尋找同一條空間線段在不同成像圖像上的投影。特征線段具有首末端點不易界定的特點，且同一條空間線段在不同圖像中的投影線段之間缺乏很強的約束[5]。應用較廣的傳統特征線段匹配算法一般是依據圖像間預先獲知的對極幾何約束，只能匹配兩幅或三幅圖像間的線段[5-6]。近年來提出的不單純利用幾何約束的線段匹配算法[7-9]，雖然在一定程度上克服了純幾何約束的缺點，但只能匹配兩幅圖像間的線段。由文獻[5]擴展的算法[10]和 lmatch算法[11]對多幅圖像間線段的匹配效果雖然都較好，但都要預先獲取對極幾何知識，求解過程較繁瑣。

得到多幅圖像之間線段的對應關系后，即可重建出建筑物的三維線段結構。Hartley等提出的平面交線法[12]，求解過程受到特征線段首尾端點提取不準確的干擾。Werner也使用平面交線法重建三維線段，但要求輸入圖像必須含有三個相互正交的主方向[13]，現實中并不是所有的建筑物圖像都能滿足此要求。

針對上述問題，本文提出了一種改進算法。在特征線段匹配時，結合穩定性更高的雙視圖匹配算法，參照lmatch算法[11]的框架，進行多幅圖像間的線段匹配。隨后采用拼接的方式對匹配線段組進行三維線段重建，將每一條特征線段對應的空間線段片段連綴成一條完整的空間線段，并篩除部分空間線段，得到簡潔的建筑物三維線段模型。

1 算法

1.1 多幅圖像間的特征線段匹配

1.1.1 初始匹配線段組設輸入M幅圖像，第m幅圖像用LSD算法[4]提取Jm條線段，m= 1 ,2,…M，其第j條線段記為l={(xs,ys),(xe,ye)}，j= 1 ,2,…J，

mjmjmjmjmjm

(xs,ys)和(xe,ye)分別是線段l的首尾坐標。攝像

mjmjmjmjmj

機矩陣P3×4已知，通過SVD分解可計算得到相應光心，光心距離是兩個光心向量之間的歐氏距離。

根據輸入圖像光心之間的距離，均勻選取光心距離最近的若干組圖像對作為基礎圖像對，記為(mp,mq)，p,q∈ [1,M]。(mp,mq)中兩幅圖像的特征線段匹配采用點線相結合的算法[9]，產生的匹配線段集合記為Spq，Spq中任一組匹配線段si={lpj,lqb}的相似度為ri=SimL(lpj,lqb)，i= 1 ,2,… ,Ipq，Ipq為Spq中匹配線段組的總數。記k(Spq)為基礎圖像對圖像p,q，k＇ (Spq)為未與p,q匹配的圖像，Θ為計算得到的所有匹配線段組的集合。

對每一組基礎圖像對(mp,mq)，都重復下列步驟。

步驟1更新Θ為Θ:=Θ∪Spq。

步驟 2根據光心距離，由式(1)計算k＇ (Spq)中與k(Spq)圖像距離最近的圖像mp

計算(mp,mp)中所有的匹配線段。若mp中的線段lpa與Spq中的si相對應，如lpa與lpj匹配，則將lpa納入si中，si:={lpj,lqb,lpa}，ri:=ri+SimL(lpj,lpa)；若lpa與lpc形成了新的匹配線段組sv={lpa,lpc}，則Spq:=Sp∪qs，該組新匹配的相似度為rv=Si(mLl,p，同 時 ，Ipq:=Ipq+1，k＇(Spq):=k＇(Spq)mp。

步驟3重復步驟2，直到k＇ (Spq)中沒有圖像。

1.1.2 篩選匹配在上述過程結束后，Θ中包含了M幅圖像間所有的匹配線段組，但此時Θ中各匹配線段組之間的關系還不準確。兩個匹配線段組之間的關系可能會有三種情況：相同匹配（兩組匹配包含的數據完全一致）、相容匹配（兩組匹配包含的數據不一致，但不存在互相矛盾）和不相容匹配（兩組匹配包含的數據互相矛盾，如一幅圖中的一條線段與另一幅圖中的兩條不同線段形成匹配）。

在對各匹配線段組之間關系的分析基礎上，對Θ中數據進行篩選和整合，最終的準確數據會存放在Θ*中，具體步驟如下。

步驟 1在Θ中選取相似度最高的匹配線段組si，Θ*:=Θ*∪si，Θ:=Θsi。

步驟 2遍歷Θ中的sk，與si比較，若si與sk是相容匹配，則將sk中與si不同的匹配線段合并入si，Θ:=Θsk；若si與sk是完全相同匹配或不相容匹配，則Θ:=Θsk。

步驟 3重復步驟 1和步驟 2，直至Θ中沒有匹配線段組。

圖2所示為Wadham學院基準圖像集[14]中一幅圖像的特征線段匹配結果。圖2a和圖2b分別是本文算法和lmatch算法的結果。上方圖像為在輸入原圖上標注的匹配結果，圖中標注有數字的線段屬于各匹配線段組；下方圖像為局部放大圖。由圖可見，在本文算法匹配部分的結果中，建筑物外立面中大部分的線段都能在不同的圖像中找到正確的匹配，lmatch算法雖然也可以找到正確的匹配結果，但匹配的線段數量較為稀疏，并且基本都是直邊緣的線段，大門等存在弧形邊緣的部分沒有匹配線段結果。因此，本文方法得到的匹配線段組更為細致。

1.2 空間三維線段重建

1.2.1 重建初始三維線段下面以N(N≤M)幅圖像重構為例詳述平面交線法[12]重構三維線段的過程。假設有一組匹配線段組si= {l1a,l2b,… ,lNd}，N幅圖像對應的攝像機矩陣分別為P1，P2，…，PN。

首先重建匹配線段組si對應的空間直線。經過線段的直線記作Imj，由直線反向投影定義的平面是πmj=Imj，為Pm轉置。將si中的N條線段按照上述的過程，生成N個相互對應的平面π1a，π2b，…，πNd。

綜上，對比兩種不同取心鉆具所獲取的巖心樣品質量以及表1所示的巖心采取率，TK-NCC01型鉆具的優勢極為明顯，表現為以下兩點：①巖心質量方面，原有超前單動雙管鉆具獲取的巖心較松散；而TK-NCC01型鉆具所獲取的巖心相對比較完整，而且從圖8左圖可以看出，巖心樣品擾動很小，基本保持了巖心原狀。②在同區域相同地層中TK-NCC01型鉆具巖心采取率遠高于超前單動雙管鉆具，總進尺6 m，獲得巖心5.13 m，平均巖心采取率為85.5%。較超前單動雙管鉆具增加了52.5%，提高了159%。

N條投影直線I1a、I2b、…、INd是由同一條空間直線W（未知）產生的，所以π1a、π2b、…、πNd交于這條公共的三維直線。這個相交約束可以描述為N×N的矩陣

若AV=0，則點V在該重構直線W上。根據空間直線的平面表示方法[12]，A的秩為2，可推出該重構直線W上的點可表示為V=αξ0+βξ1，其中ξ0和ξ1是A的零空間的標準正交基。

圖2 多幅圖像特征直線段匹配結果

得到了空間直線上任一點的表達方式，便可據此在重構直線上截取匹配線段組對應的空間線段。傳統的做法通過最小化重投影誤差之和，對該空間線段首尾端點的確切位置進行最大似然估計。由于不能保證準確提取到線段真實的首末端點，并且計算時存在累積誤差，故最大似然估計的結果通常不理想。

針對上述缺陷，本文通過分段的方式得到三維空間線段，具體步驟如下。

步驟 1對一個匹配線段組中的一條線段，按照最大似然準則，求解對應的三維空間子線段。此時每一條三維子線段都不受匹配線段組中其他線段位置的影響，與相應的圖像線段是準確對應的。

匹配線段組中任一條線段對應的三維子線段都在W上，故可由W上的兩點定義該空間線段的首尾端點。取si中的線段l1a，設l1a對應的三維子線段為W1a={V0,V1}，其中V0=α0ξ0+β0ξ1，V1=α1ξ0+β1ξ1。依據最大似然準則，最小化W1a到圖像1的投影與l1a之間的重投影誤差，得到每個參數的值。

步驟 2對匹配線段組si中的每一條線段都重復步驟1，直到所有線段都生成對應的空間三維線段。

步驟 3將以上得到的所有三維子線段按照首尾相接的方式連接起來，形成一段完整的與si相對應的空間三維線段，記作W*。

步驟 4對Θ*中的每一個匹配線段組都重復步驟 1~步驟3，直到每一個匹配線段組都得到了其對應的空間三維線段。

得到建筑物三維重建的初始結果。如圖3所示，從圖中已經可以看到建筑物的整體形狀（共 630條線段），但結果中還有一些錯誤的線段（圖3中的黑色線段）需要在后續處理中去除。

圖3 建筑物三維重建的初始結果

1.2.2 過濾初始三維線段如圖3所示，由于線段提取錯誤、線段匹配錯誤等原因，重建出的線段也會有錯誤，這些錯誤的線段稱為“非期望假設”[15]。本文通過各種約束對其剔除。

長度約束是限制空間線段的長度。有一類“非期望假設”的長度遠大于組成建筑物的線段長度，因此可對空間線段的長度進行約束，將大于某一長度d0的線段丟棄。如圖4所思，圖4a為圖3經過長度約束后得到的結果（共473條線段）。

誤差約束是控制重投影誤差。計算某一匹配線段組對應的空間三維線段與匹配線段組中各線段之間的重投影誤差之和，當誤差小于閾值d1時，該空間線段才能被保留。

角度約束是限制空間線段與空間平面的夾角大小。一般構建建筑物的線條方向主要集中在某幾個方向，而“非期望假設”的方向卻通常雜亂無章，可以通過同時約束三維線段到任意兩個垂直平面的夾角，進一步剔除“非期望假設”。對夾角值分別進行分段統計，同時保留滿足兩種夾角值都占優（線段數最多）的空間線段。當加入的分段數目達到設定閾值d3時停止。圖4b為圖4a經過角度約束后的效果，共410條線段。

圖4 長度約束與角度約束后的結果

2 實驗結果及分析

實驗中的兩個圖像集均采用手持相機拍攝。角度約束時，兩種夾角值都是按照每 15度分一段。lmatch算法的參數DispRange設置為400。

2.1 實驗結果

第一組實驗重建具有平面狀的建筑物外立面。使用西安交通大學化工樓圖像集，共33幅大小為1 028×960的圖像，如圖5所示。圖5a為其中一幅圖像；圖5b和圖5c分別為lmatch算法和本文算法的重建結果。實驗中d0為2.5，d1為15，d2為2。由圖可見，本文算法能清晰顯示窗戶的單元格構造，且組成建筑物的線段大部分都是相互平行或垂直的，沒有過多“非期望假設”。lmatch算法雖然也可以看到建筑物的整體結構，但是由于線段匹配的精確度不高，導致“非期望假設”叢生，在一定程度上掩蓋了重建結果的主體結構。

圖5 化工樓圖像集結果

第二組實驗重建具有多外立面的建筑物。使用清華大學理科樓圖像集，共49幅大小為1 09 2×728的圖像。該樓是一個類U型的建筑物，共有三面，如圖6所示。圖6a為其中一幅圖像，圖6b和圖6c分別為lmatch算法和本文算法的重建結果，實驗中為2.5，d1為22，d2為3。由圖可見，本文算法可較好地體現建筑的整體框架，而lmatch算法只重建了建筑物中的兩個外立面，建筑物的整體結構都沒有得到有效重建。由于圖像集中有關左側建筑部分的圖像較多，因此在兩種算法中該部分墻面的重建精度都會高一些。

2.2 參數分析

參數影響重建結果的線段數目。參數選擇嚴格時，在剔除“非期望假設”的同時也會損失一部分組成建筑物結構的線段，最終重建結果中的線段數目也會較少。反之，如果約束過于寬松，較完整的三維模型結構也會淹沒在雜亂無章的“非期望假設”中。

參數d0和d2是兩個較為重要的參數，d0的確定主要依據組成建筑物的線段長短，若建筑物主要由較連貫的、長度較大的線段組成，d0的取值可以稍大；反之，d0的取值稍小為宜。一般情況下d0的取值為2~5之間。如圖7所示，以Wadham大學基準圖像集為例，顯示了d0取值的變化對重建結果的影響，其中n為各重建結果中的線段數目，實驗中保持d1=17.5，d2=4不變。該圖像集的原始重建結果經過d1和d2的約束得到305條線段，d0的約束會進一步減少這些線段，而隨著d0取值的增大，圖中水平和豎直線條漸漸增多，房屋的框架、窗體等結構也慢慢清晰。

圖6 理科樓圖像集結果

圖7 d0變化對重建結果的影響

d2的確定依據建筑物的主要結構，若建筑物的構造比較規整，主要由相互垂直的線段組成，d2可設置小一些，以便濾除更多的“非期望假設”；若建筑物中還有較多的曲線、斜線等方向的線條，稍大些的d2可保留更多的建筑物細節線條。d2的取值范圍一般是2~4之間的整數。如圖8所示，以Wadham大學基準圖像集為例，顯示了d2取值的變化對重建結果的影響，其中n為各重建結果中的線段數目，實驗中保持d0=5，d1=17.5不變。由實驗結果可以看出，隨著d2取值的增大，角度約束放松，圖中斜線增多，右側墻壁窗子上方的裝飾、房頂煙囪的尖頂等都漸漸顯現。

圖8 d2取值變化對重建結果的影響

若三維重建的效果已經較為滿意，則對d1稍加約束即可。該參數對線段數量和建筑物結構的影響沒有前兩個參數明顯。

3 結 論

針對建筑物三維線段模型重建問題，本文結合準確度更高的雙視圖線段匹配算法，在沒有幾何先驗的條件下，對任意幅輸入圖像進行更精確的線段匹配，三維線段的重建過程也不再因為匹配線段之間的位置干擾而受到影響。實驗結果表明，本文算法對于具有單一平面狀外立面及具有多外立面的建筑物，都有良好的重建結果。

[1]CHEN Tingwang, WANG Qing. 3D line segment detection for unorganized point clouds from multi-view stereo[C]//Proceedings of the 10th Asian Conference on Computer Vision. Berlin, Germany：Springer-Verlag, 2011:400-411.

[2]彭亞麗, 劉芳, 劉侍剛.一維子空間的三維重建方法[J].西安交通大學學報, 2009, 43(12):31-34.PENG Yali, LIU Fang, LIU Shigang. 3D reconstruction method with 1D subspace [J]. Journal of Xi’an Jiaotong University, 2009, 43(12):31-34.

[3]PARK J S. Interactive 3D reconstruction from multiple images:a primitive-based approach[J]. Pattern Recognition Letters, 2005, 26(16):2558-2571.

[4]VON GIOI RG, JAKUBOWICZ J, MOREL J M, et al. LSD:a fast line segment detector with a false detection control[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32 (4):722-732.

[5]SCHMID C, ZISSEMAN A. Automatic line matching across views[C]//Proceedings of the 1977 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway, NJ, USA:IEEE Computer Society, 1997:666-671.

[6]SCHMID C, ZISSEMAN A. The geometry and matching of lines and curves over multiple views [J]. International Journal of Computer Vision, 2000, 40 (3):199-233.

[7]BAY H, FERRARIS V, VAN GOOL L. Wide-baseline stereo matching with line segments [C]// Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway，NJ，USA：IEEE, 2005:329-336.

[8]WANG Zhiheng, WU Fuchao, HU Zhanyi. MSLD:A robust descriptor for line matching[J]. Pattern Recognition,2009, 42 (5):941-953.

[9]FAN Bin, WU Fuchao, HU Zhanyi. Robust line matching through line-point invariants [J]. Pattern Recognition, 2012,45 (2):794-805.

[10]BAILLARD C, SCHMID C, ZISSEMAN A, et al.Automatic line matching and 3D reconstruction of buildings from multiple views [C]// Proceedings of the ISPRS Conference on Automatic Extraction of GIS Objects from Digital Imagery. Amsterdam, Netherlands,Holland:Elsevier Science,1999:69-80.

[11]WERNER T. LMATCH:matlab toolbox for matching line segments accross multiple calibrated images [EB/OL].(2007-06-01)[2013-06-12].http://cmp.felk.cvut.cz/~werner/software/lmatch/.

[12]HARTLEY R, ZISSEMAN A. Multiple view geometry in computer vision[M]. Cambridge, UK:Cambridge University Press, 2000.

[13]WERNER T, ZISSERMAN A. New techniques for automated architectural reconstruction from photographs[C]// Proceedings of the 7th European Conference on Computer Vision. Berlin, Germany:Springer-Verlag, 2002:541-555.

[14]VERETNIK S. Benchmark data set of Wadham College[DB/OL].(2006-01-01)[2013-6-23].http://www.robots.ox.ac.uk/~vgg/data/datamview.html.

[15]NORONHA S, NEVATIA R. Detection and modeling of buildings from multiple aerial images[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2001, 23 (5):501-518.