基于密集點云重投影的三維線段模型重建算法

歐元漢，黃 鴻＋，陸宇海

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

0 引 言

基于圖像的三維重建過程主要包括密集點云生成、曲面重建、紋理映射等步驟。密集點云模型在缺乏紋理的地方出現(xiàn)空洞，在建筑物邊緣容易產(chǎn)生重建誤差較大的外點。以上缺陷導(dǎo)致由密集點云生成的網(wǎng)格模型表面出現(xiàn)起伏凹陷，本該平直而銳利的邊緣出現(xiàn)扭曲和平滑。直線是建筑物表面和邊緣最常見的幾何元素，相比密集點云模型，建筑物的三維線段模型能有效體現(xiàn)建筑物的幾何結(jié)構(gòu)并保留規(guī)整的建筑物邊緣。生成網(wǎng)格模型時，借助三維線段模型提供的邊緣信息，可使網(wǎng)格模型具有更加平整的表面和銳利的邊緣，改善后續(xù)產(chǎn)生的貼圖模型的視覺效果。因此建筑物場景的三維線段模型有重要的實用價值。

1 相關(guān)工作

三維線段模型重建的主要過程包括多視圖間線段匹配和三維線段生成。

多視圖間線段匹配問題的本質(zhì)是尋找同一三維線段在各視圖中的重投影線段。線段匹配的難點在于受光線，角度和遮蔽等因素影響，各視圖中的線段端點不一致；在不同拍攝角度下，建筑物邊緣線段周圍的背景有較大反差，基于線段附近區(qū)域灰度值的匹配方法很難奏效。Bay等［1］提出使用直線表面特征和拓撲關(guān)系匹配線段，用線段附近的顏色直方圖進行初匹配，根據(jù)線段間的拓撲關(guān)系去除誤匹配，尋找新匹配。該方法計算量大，且顏色特征對光照和圖像間反差敏感；Wang等［2］利用線段周圍像素的梯度信息構(gòu)建MSLD 線段描述子用于線段匹配，但線段周圍往往缺乏豐富的紋理，且該方法不能處理尺度變換問題；Wang等［3］使用線段端點計算線段間的角度和長度比例，根據(jù)這些信息進行線段匹配，該方法在端點位置出現(xiàn)較大誤差時無法奏效；Fan等［4］先對圖像進行特征點匹配線段，然后基于線點不變性 （line－point invariants）匹配線段，該方法能穩(wěn)健處理旋轉(zhuǎn)、尺度和光照變換問題，匹配準確率高，但受制于稀疏的特征點匹配，匹配線段數(shù)量不夠多。

得到多視圖間線段的匹配關(guān)系后，可用平面交線法［5］重建三維線段，該方法受線段端點位置不準確的影響，對輸入圖像的幾何約束太強，不能有效處理誤匹配線段，導(dǎo)致三維線段出現(xiàn)較大的估計誤差，模型中充滿雜線；Chen等［6］提出的建筑物三維線段模型的方法，該方法重建速度快，但依靠點云模型確定線段端點，使得線段模型過度依賴于點云模型。當(dāng)點云模型出現(xiàn)局部稀疏或缺失時，會影響線段模型的完整重建；點云在建筑物邊緣并非整齊分布，造成線段模型在邊緣處出現(xiàn)不規(guī)整的線段。Hofer等［7，8］通過對極幾何產(chǎn)生潛在匹配線段，生成大量候選三維線段，最后通過三維線段聚類濾除多余雜線，形成最后的三維線段模型。該方法主要用于重建輸電塔這類紋理很少的直線框架物體，所以不要求準確匹配線段，但需生成數(shù)量龐大的候選三維線段，計算量大，重建速度慢，不適用于實體建筑物重建。

為解決上述問題，本文提出了基于密集點云重投影的三維線段重建算法。主要貢獻有：①使用關(guān)聯(lián)同一空間點的二維線段存在匹配關(guān)系原理構(gòu)建匹配線段集，避免依賴線段紋理特征，解決點云重投影后產(chǎn)生的深度信息丟失問題，實現(xiàn)多視圖間線段的準確匹配；②針對以往方法對噪聲敏感的問題，本文采用空間直線與空間平面相交法重建三維線段，并以RANSAC［9］濾除因線段誤匹配產(chǎn)生的雜線，實現(xiàn)三維線段的穩(wěn)健估計；③定義三維線段的重投影誤差，并以最小化重投影誤差方法優(yōu)化三維線段模型，使模型精度進一步提高。

2 算 法

本文提出的建筑物三維線段模型重建算法的主要流程是：①由SFM 和MVS算法生成密集點云和各視圖的攝相機矩陣；②在各視圖中的提取二維線段；③將密集點云重投影回各視圖中獲得線段的匹配關(guān)系；④使用空間直線與空間平面相交法重建三維線段；⑤最小化三維線段的重投影誤差，優(yōu)化場景模型。

2.1 線段檢測

LSD （line segment detector）［10］線段提取算法對具有同一梯度方向的像素集合應(yīng)用最小二乘法估計線段的方向和端點，檢測精度高和誤檢率低，計算復(fù)雜度正比于圖像像素總數(shù)，檢測速度快，適合大規(guī)模圖像的二維線段提取。

LSD 算法輸出線段的兩個端點坐標和外接矩形。在線段外接矩形內(nèi)的所有像素構(gòu)成稱為線段支持區(qū)域 （line support region）的像素集合。各線段的支持區(qū)域之間沒有交集，所以三維空間中的一點X 重投影回某一視圖后只有兩種可能：若重投影點x 在某一線段l 的支持區(qū)域內(nèi) （x∈l）則此三維點X 關(guān)聯(lián)該線段，若重投影點不在任何線段的支持區(qū)域內(nèi)則三維點X 不關(guān)聯(lián)任何線段。

2.2 線段匹配

2.2.1 線段的弱匹配

本文使用關(guān)聯(lián)同一空間點的線段存在弱匹配關(guān)系原理對線段進行初始匹配。設(shè)空間點X 在各視圖中的重投影點為xi＝PiX，Pi是第i幅視圖的相機矩陣。定義視圖i中的線段lia與視圖j 中的線段ljb存在弱匹配關(guān)系，當(dāng)且僅當(dāng)兩線段關(guān)聯(lián)相同的空間點X，即存在空間點集η R3使得η＝｛X｜xi＝PiX，xj＝PjX，xi∈lia，xj∈ljb｝。

記outX 為關(guān)聯(lián)空間點X 的線段集合，根據(jù)弱匹配關(guān)系原理，該集合內(nèi)的線段存在弱匹配關(guān)系。記outl為重投影點屬于二維線段l 的空間點集合，這些空間點應(yīng)在同一條三維線段上，因為l是這條三維線段的投影。

圖1為3個視圖間線段的匹配情況?？臻g點Xb和Xc在視圖B中的重投影點都屬于lb，在視圖C 中的重投影點都屬于lc，所以outXb＝outXb＝ ｛lb，lc｝，outlb＝ ｛Xa，Xc｝，lb與lc存在弱匹配關(guān)系。三維空間點重投影回視圖后變?yōu)槎S平面點會造成深度信息丟失，上述的線段匹配方法將產(chǎn)生許多誤匹配。如空間點Xa和Xb在視圖C 中的重投影點重合且屬于同一線段lc，但視圖C 顯然不能觀察到空間點Xa；若在視圖A 中Xa的重投影點被檢測屬于la，則會造成la與lc誤匹配，這將不利于后續(xù)的三維線段生成。為解決深度信息丟失問題，必須得到有哪些視圖可以觀察到該空間點的信息，記visXi為空間點Xi的可視視圖集合，該集合內(nèi)的所有視圖均可觀察到Xi。本文使用修改后的PMVS［11］軟件生成每個空間點的可視視圖集，同時生成密集點云。

生成outXi時，為避免由于深度信息丟失而造成線段誤匹配，只將Xi投影到visXi包含的視圖中，然后在各視圖中檢查重投影點是否屬于某一線段，并將符合條件的線段加入outXi。為生成outlia，只需在線段lia加入outXi時，將空間點Xi加入outlia。

圖1 多視圖間線段匹配

2.2.2 篩選匹配

上述線段弱匹配關(guān)系存在大量誤匹配，必須進行篩選，形成正確的線段匹配關(guān)系。對一條三維線段，可由在此線段上的空間點X 的outX 得到在各視圖中具有弱匹配關(guān)系的二維線段，而此三維線段上的所有空間點可提供各視圖中匹配線段的統(tǒng)計信息。對這些線段的匹配次數(shù)進行統(tǒng)計，在各視圖中選取匹配次數(shù)最多的線段為該視圖中正確匹配的線段。記Θ 為計算得到的所有匹配線段組的集合，計算Θ 的步驟如下：

步驟1 取outlia中的一個空間點Xi，將outXi中所有二維線段的匹配計數(shù)加1。

步驟2 對outlia中的所有空間點重復(fù)步驟1，得到與lia存在匹配關(guān)系的所有二維線段的匹配計數(shù)。二維線段ljb的匹配計數(shù)代表視圖j 內(nèi)的ljb與視圖i內(nèi)的lia的匹配程度。

步驟3 在視圖j中，取匹配計數(shù)最大即匹配程度最高的線段為該視圖中唯一與lia匹配的線段。

步驟4 在所有視圖中重復(fù)步驟3，獲得n 個視圖中與lia匹配的n 個線段組成的匹配線段組s，并將s中的所有線段標記為已匹配。

步驟5 更新Θ 為Θ：＝Θ∪s。

步驟6 對所有標記為未匹配的二維線段，重復(fù)執(zhí)行上述步驟1～步驟5，即可獲得匹配線段組集合Θ。

2.3 三維線段生成

平面交線法［5］反投影匹配線段生成多個反投影平面，然后用SVD 分解確定這些反投影平面的公交線。SVD 分解本質(zhì)上是最小二乘法，最小二乘法的缺點是對噪聲比較敏感，當(dāng)出現(xiàn)線段檢測誤差和誤匹配線段時，線段模型會出現(xiàn)較大的重建誤差，產(chǎn)生大量雜線。

為解決上述問題，本文采用空間直線與空間平面相交法計算候選三維線段，并參考RANSAC算法濾除外點，穩(wěn)健估計模型參數(shù)的思想準確計算三維線段。

從匹配線段組中任意選取一對匹配線段，計算一條候選三維線段。將三維線段重投影回匹配線段組對應(yīng)的各視圖中，評估各視圖中重投影線段與原始匹配線段的重合程度。若在大多數(shù)視圖中，重投影線段與原始匹配線都重合，則此三維線段的重建精度較高。而雜線的重投影線段在大多數(shù)視圖中與原始匹配線段都不重合。一條候選三維線段的重合次數(shù)越大代表它的重建精度越高。根據(jù)上述方法計算匹配線段組內(nèi)所有可能的一對匹配線段的候選三維線段和它的重合計數(shù)。取重合計數(shù)最高的三維線段為該匹配線段組對應(yīng)的三維線段。

2.3.1 估計候選三維線段

本文采用空間直線與空間平面相交法計算三維線段端點。如圖2所示，l1經(jīng)過攝像機P1反向投影得到平面π1＝P1l1，l2的端點e21經(jīng)攝像機P2反向投影得到的直線與π1相交得到三維線段L 的一個端點E21，同理得另外3個端點E22，E11，E12。由于線段端點不能精確匹配，L 的端點不能精確計算，本文采取的策略是在這4個候選端點中選取其中兩個使L 的長度達到最長。如圖2中選取E21，E12為L的端點。

圖2 估計三維線段

為計算反投影直線與反投影平面的交點，設(shè)視圖的攝像機矩陣為P＝ ［M ｜p4］，則攝像機光心為C＝ （－M－1P4，1）T。視圖中一點x被攝像機反投影形成的射線L 交無窮遠平面于點D＝ （（M－1x）T，0）T，由D 和C 可將投影射線L 定義為點束

射線L（φ）與平面π的交點L（φX）必在平面π上，故有πΤL（φX）＝0，代入式 （1）得

可解出

將式 （3）帶入式 （1）即可求出交點L（φX）。

2.3.2 計算候選三維線段的重合計數(shù)

為判斷候選三維線段L 是否為重建誤差較大的雜線，首先將L 重投影到匹配線段l 所在的視圖中，得到重投影線段lp。當(dāng)同時滿足以下3個條件時判定l與lp重合。

（1）l兩端點到lp的距離小于閾值d；

（3）lp與l之間夾角小于閾值θ。

將L 重投影回匹配線段組對應(yīng)的各視圖中，并累計L的重合計數(shù)。若重合計數(shù)太小，表明候選三維線段存在較大的估計誤差，而重合計數(shù)越大表明候選三維線段的重建精度越高，所以僅保留重合計數(shù)最大的三維線段，并記與此三維線段重投影線段重合的匹配線段集為visL，該集合基本濾除了重投影誤差很大的誤匹配線段。

2.4 三維線段模型優(yōu)化

圖3 三維線段重投影誤差

本文使用ceres－solver［12］求解這個非線性最小二乘問題，優(yōu)化調(diào)整所有三維線段，進一步減小三維線段的重投影誤差，提高模型的重建精度。

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

我們使用無人機對城市某一范圍內(nèi)建筑物場景進行航拍，采集了141 幅6000＊4000 的圖像。實驗環(huán)境為Intel Xeon E3－1230v2，16GB內(nèi)存，編程環(huán)境為Visual Studio 2010。

為驗證本文線段匹配算法的有效性，我們對圖4和圖5所示的兩個圖像對進行線段匹配，并與文獻 ［4］的方法（RLM）進行比較，文獻 ［4］的實驗結(jié)果表明，RLM 的性能相比MSLD［2］和Line Signature［3］均有提高。RLM 算法實現(xiàn)代碼由作者提供。為加快實驗進度，減少線段數(shù)量，我們將圖像降采樣至1500＊1000分辨率。

表1圖像對一欄括號內(nèi)的數(shù)字是兩幅圖像檢測出的線段數(shù)量，算法欄括號內(nèi)數(shù)字分別是匹配線段數(shù)，正確匹配線段數(shù)和匹配正確率。本文算法和RLM 算法均使用LSD提取線段。

圖4 圖像對a

圖5 圖像對b

表1 線段匹配結(jié)果

圖像對a的兩幅圖像視角變化不大，兩種算法都有較高的正確率，但本文算法正確匹配線段的數(shù)量較多。圖6左側(cè)和右側(cè)分別是RLM 算法和本文算法在同一區(qū)域的線段匹配結(jié)果，可見本文算法的匹配線段更密集。因為RLM 用落在線段附近支持區(qū)域內(nèi)的稀疏SIFT 特征點確定線段的匹配關(guān)系。而本文使用的密集點云重投影點比SIFT 特征點數(shù)量多且稠密，有更多的點落在線段支持區(qū)域內(nèi)，所以檢測匹配線段數(shù)量有較大提升。

圖6 線段匹配結(jié)果

圖像對b的兩幅圖像視角變化較大，兩種算法的匹配線段數(shù)量和正確率均有下降，但RLM 算法的下降幅度更大。因為在視角變化較大時SIFT 算法無法產(chǎn)生足夠數(shù)量的匹配點；建筑物邊緣處線段的支持區(qū)域在不同視角下變化很大，兩個變化較大視角有可能只觀測到線段不同側(cè)的支持區(qū)域。本文算法不利用線段附近支持區(qū)域內(nèi)特征點或灰度信息，而是利用關(guān)聯(lián)同一三維點的重投影點確定線段匹配關(guān)系，所以對較大視角變化不敏感，仍能達到較高的檢出率和正確匹配率。

為驗證本文的三維線段重建算法，先用Bundler［13］生成稀疏點云模型和攝像機矩陣，然后使用修改過的PMVS生成密集點云和可視視圖信息。圖7為由圖像生成的密集點云模型，該模型的建筑物主體出現(xiàn)了的空洞，且未能良好體現(xiàn)建筑物規(guī)整的結(jié)構(gòu)特征。本文算法生成三維線段模型時，將重投影線段與匹配線段間夾角閾值θ設(shè)為5°，匹配線段端點到重投影線段的距離閾值d 設(shè)為兩個像素，線段長度比例閾值δ 設(shè)為0.25。最后根據(jù)重建結(jié)果與文獻［5］和文獻 ［6］的方法進行比較分析。

圖7 密集點云模型

如圖8所示，本文算法能完整體現(xiàn)建筑的整體框架和直線邊緣，很少出現(xiàn)因誤匹配和錯誤重建產(chǎn)生的雜線，表明本文算法能有效應(yīng)對線段的誤匹配和測量誤差，濾除重建誤差較大的雜線，穩(wěn)健性強。模型準確還原了建筑物表面具有直線特征的窗戶和廣告牌位，線段端點沒有出現(xiàn)過長的冒頭和過短的斷續(xù)，建筑物邊緣清晰銳利，模型的細節(jié)部分也得到了良好體現(xiàn)，表明最后的優(yōu)化調(diào)整算法確實能有效提高重建精度。

圖8 本文算法重建結(jié)果

文獻 ［5］提出平面交線法生成三維線段模型。由于最小二乘法對噪聲敏感，且算法在生成三維線段時沒有濾除誤匹配線段，造成初始重建的三維線段模型充斥大量雜線，淹沒了建筑物的主體結(jié)構(gòu)，必須用長度約束和角度約束濾除雜線。經(jīng)過實驗調(diào)整，我們將文中提到的閾值d0設(shè)為0.2，d1設(shè)為15，d2設(shè)為4。設(shè)定閾值這項工作只能由人工依據(jù)特定場景的視覺效果逐步調(diào)整，不同的場景需要不同的閾值，未能實現(xiàn)完全自動化，且有很強的主觀性。而本文算法的自適應(yīng)性強，不用根據(jù)特定場景調(diào)整閾值，無需人工干預(yù)，實現(xiàn)了自動化重建。重建結(jié)果如圖9 所示，建筑物邊緣處仍有很多短小的雜線，未能體現(xiàn)清晰的邊緣特征。因為全局的長度約束和角度約束無法濾除符合約束的雜線，而且有可能濾除正確重建但不符合約束的三維線段。

圖9 文獻 ［5］重建結(jié)果

文獻 ［6］沒有使用匹配線段和攝像機參數(shù)計算三維線段，而是選定點云內(nèi)某些三維點作為三維線段的端點，雖然速度很快，但三維線段模型完全依賴于密集點云模型，容易受到點云疏密的影響。如圖7和圖10所示，高樓的密集點云模型在主體位置出現(xiàn)空洞，三維線段模型在同一位置也出現(xiàn)空洞。模型邊緣的線段也不夠整齊銳利。因為在邊緣處點云并非規(guī)整平直的分布在一條直線上，甚至存在許多外點，以這些點作為三維線段端點無法達到更高的精度。本文算法生成三維線段模型時不依賴密集點云，所以模型結(jié)構(gòu)完整，未出現(xiàn)空洞。

圖10 文獻 ［6］重建結(jié)果

4 結(jié)束語

本文針對建筑物的三維線段模型重建，提出了基于密集點云重投影的多視圖線段匹配算法，該算法匹配準確度高，且對差別較大的視圖變換具有較強的魯棒性。穩(wěn)健的三維線段生成算法能有效處理誤匹配線段和端點檢測誤差，減少雜線的產(chǎn)生。模型優(yōu)化調(diào)整算法可最小化三維線段的重投影誤差，提高模型的重建精度。實驗結(jié)果表明，本文算法重建的建筑物三維線段模型能完整體現(xiàn)建筑物的框架結(jié)構(gòu)和規(guī)整的直線邊緣，具有良好的視覺效果。在后續(xù)工作中，我們將利用本文算法提供的三維線段模型對建筑物網(wǎng)格模型進行優(yōu)化調(diào)整，以期得到邊緣更規(guī)整，視覺效果更好的建筑物網(wǎng)格模型。

［1］Bay H，F(xiàn)errari 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，2005：329－336.

［2］Wang Z H，Wu F C，Hu Z Y.MSLD：A robust descriptor for line matching ［J］.Pattern Recognition，2009，42 （5）：941－953.

［3］Wang L，Neumann U，You S.Wide－baseline image matching using line signatures ［C］／／Proceedings of the IEEE international Conference on Computer Vision，2009：1311－1318.

［4］Fan B，Wu F C，Hu Z Y.Robust line matching through linepoint invariants ［J］.Pattern Recognition，2012，45 （2）：794－805.

［5］ZHANG Linyan，ZHU Li.3Dline segments reconstruction for building facades with line matching across multi－image with nongeometry constraint［J］.Journal of Xi’an Jiaotong University，2014，48 （4）：15－19 （in Chinese）.［張琳彥，朱利.以多幅圖像非幾何約束線段匹配重建建筑物外立面三維線段模型［J］.西安交通大學(xué)學(xué)報，2014，48 （4）：15－19.］

［6］Chen T W，Wang Q.3Dlinesegment detection for unorganized point clouds from multi－view stereo ［C］／／Proceedings of the Asian Conference on Computer Vision.Berlin，Germany：Springer－Verlag，2011：400－411.

［7］Hofer M，Wendel A，Bischof H.Line－based 3Dreconstruction of wiry objects［C］／／Computer Vision Winter Workshop，2013.

［8］Hofer M，Wendel A，Bischof H.Incremental line－based 3Dreconstruction using geometric constraints［C］／／British Machine Vision Conference，2013.

［9］Fischler M A，Bolles R C.Random sample consensus：A paradigm for model fitting with applications to image analysis and automated cartography ［J］.Communications of the ACM，1981，24 （6）：381－395.

［10］Gioi V，Grompone R.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.

［11］Furukawa Y，Ponce J.Accurate，dense，and robust multiview stereopsis ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32 （8）：1362－1376.

［12］Agarwal S，Mierle K.Ceres solver ［CP／OL］.http：／／ceres－solver.org，2010.

［13］Snavely N，Steven M S，Szeliski R.Photo tourism：Exploring image collection in 3D ［J］.ACM Transactions on Graphics，2006，25 （3）：835－846.