三維重建中線段匹配方法的研究

陳起鳳 ，劉 軍*，李 威 ，雷光元 ，董廣峰

1.智能機器人湖北省重點實驗室（武漢工程大學），湖北 武漢 430205；2.武漢工程大學計算機科學與工程學院，湖北 武漢 430205；3.國投新疆羅布泊鉀鹽有限責任公司，新疆 哈密 893000

隨著信息技術的迅猛發展，三維重建在許多領域有越來越多的應用，如文化遺產保護、文物研究、視頻監控、動畫電影制作、醫學圖像處理以及虛擬現實等［1-2］。在計算機視覺中［3-4］，基于圖像的三維重建技術是根據場景的兩張或兩張以上的二維圖像，由計算機自動計算并匹配場景的二維幾何信息和深度信息，最后建立三維模型的過程。傳統三維重建是基于點的特征提取與匹配［5-8］，三維點云模型在缺少紋理的地方重建精度較差，三維線段模型能提供更充分的結構信息，反映場景的幾何拓撲關系［9］。要生成一個基于線段的三維重建模型需要建立來自不同圖片的二維線段的對應關系，線段匹配［10-11］指在兩組線段中建立對應關系的過程。早期Schimid等［12］提出一種在三視圖間自動進行線匹配的方法，在已知相機姿態信息的情況下，建立基于強度的點向線段匹配的對應關系。2005年Bay等［13］提出借助寬基線圖像進行線段匹配的方法，通過計算任意相鄰線段上像素點的顏色直方圖（Hue，Saturation，Value，HSV）來完成，后來一種基于塊的線段描述方法［14］被提出，該方法能快速得到亞像素級別直線的位置，但未考慮尺度變化的自適應性，會造成某些塊過短從而線段無法被提取的現象。2009年，梯度均值-標準差描述子（mean-standard line deviation，MSLD）算法［15］被提出，該方法建立在梯度直方圖基礎上，在視角存在缺陷和光照有變化的情況下實驗結果良好，但缺少幾何屬性做約束條件，當存在尺度變換時線段匹配準確率較低。Kim等［16］提出一種利用共面二維線段相交透視不變性的線段匹配方法，在線段交點處通過歸一化交叉相關系數進行匹配，但未與建筑外觀相結合，在進行多視圖三維重建時模型表面會出現空洞現象。針對上述問題，本文將外觀和幾何約束相結合，利用直線提取（line segment detector，LSD）算法［17］檢測直線段。首先尋找相鄰圖片，然后在相鄰圖片間進行二維線段匹配，最后進行三維模型重建。

1 線段檢測技術

LSD算法是一種能在線性時間內得到亞像素級準確度的直線段分割檢測算法，將梯度方向作為判定像素點之間圖像關系依據進行線段檢測。該算法可分為6個步驟：1）圖像縮放；2）梯度計算；3）梯度排序；4）梯度閾值；5）區域增長；6）矩形估計。首先計算每個像素點附近的線場角度，生成一個線場區域即單位向量域，其中所有向量都與通過基準點的水平線相切。該區域被分割為連通的若干部分，它們在一定的容忍度內有相同的水平線角度，這些連通的部分被稱為水平線支撐區域。每個水平線支撐區域都是一個直線分割的備選區域，同時需要一個矩形與它對應，水平線支撐區域的主軸表示矩形的主方向。矩形中線場區域角度與矩形主方向在一定容忍度下保持一致的像素點稱為對準點。統計出矩形區域像素個數以及對準點個數，通過判定準則判斷水平線支撐區域是否為直線段。算法示意圖如圖1所示。

圖1 LSD算法示意圖：（a）圖片，（b）線場區域，（c）水平線支撐區域，（d）對準點Fig.1 Schematic diagram of LSD algorithm：（a）image，（b）lever-line field，（c）line support regions，（d）aligned points

2 尋找相鄰圖片

相似性評分越高表示兩張圖片重疊的部分越多，通過篩選相似性評分得到與圖片Ii相鄰的圖片集合：

對于每個圖片Ii，集合Vi僅包含所有相鄰圖片Ij的索引，并按照其視圖相似性評分SI(i，j)降序排序。由于三維建模中數圖片集的數據量較大并且任意兩張圖片都存在重疊部分的可能性較小，本文選取相鄰圖片進行二維線段篩選與匹配以達到高效建模的目的。本文使用相鄰圖片集合Vi中相似性評分最高的前M張圖片即VM i，假設圖片集I有N張圖片，該算法時間復雜度為O(MN)。

3 二維線段匹配

假設二維線段集合Li與Lj分別存在于圖片Ii與Ij中，在篩選完相鄰圖片后，選取相似度評分較高的M張圖片，相鄰圖片Ii與Ij應滿足條件二維線段匹配階段只需進行集合Li與Lj的線段匹配。

根據對極幾何知識，本文利用極線約束關系進行二維線段間的匹配。當且時，首先計算的端點與在另一張圖片中的極線，得到兩條極線與圖片Ij中的二維段相交，獲得與二維線段的端點與共線的兩個交點χ1和χ2，如圖2所示。

圖2 二維線段匹配圖Fig.2 Matched image of two-dimensional line segments

其中，d(χ1，χ2)與表示兩個二維端點之間的歐幾里得距離。由圖2看出，四個端點共線。如果這兩個二維線段是同一個三維模型的測量結果，理想情況下匹配得分的值為1。由于光照變化、鏡頭畸形、相機參數變化、拍攝角度改變等因素，對匹配得分有一定影響，本文只取大于一個定值的一部分集合。假設當匹配得分超過閾值τ時，二維線段與視為一組潛在的匹配線段。

通過閾值篩選，二維線段匹配程序擁有較高的查全率，但查準率很低。單純提高閾值，在線段檢測時會存在檢測不精確的問題，本文選取K個與特定二維線段潛在相匹配的線段。二維線段匹配階段提到了三個重要參數值：二維線段匹配閾值τ、相鄰圖片個數M、在相鄰圖中與特定二維線段相匹配的線段個數K。本文將這三個參數分為兩組進行評估分析：首先對τ單獨進行分析，然后將M與K組合進行分析。

4 結果與討論

首先用小米無人機、iphone手機、索尼微單相機對武漢工程大學（Wuhan Institute of Technology，WIT）校園建筑進行了3組圖片集采集。分別為36張的武漢工程大學圖書館圖片集、41張的武漢工程大學教務處圖片集、250張的武漢工程大學全景圖片集，另外本文選取了PHOTOSCAN軟件中50張建模實例圖片集。然后，對這4組圖片集進行重建實驗。

4.1 二維線段匹配閾值τ對重建結果的影響

二維線段匹配閾值τ默認值設置為0.25，即兩種可能匹配的二維線段的相互重疊率至少要達到25%。為了獲得最佳的閾值，選取5個值0.1、0.25、0.5、0.75、0.9進行對比試驗。其中0.1表示二維線段極少重疊，0.9表示二維線段幾乎完全重疊。實驗結果如表1所示。不同閾值τ下圖書館重建模型如圖3所示。

數據表1與圖3表明三維模型中的三維線段數量與極線重疊閾值成反比，當閾值增加時，三維線段數量遞減；運行時間也與閾值成反比，閾值越小，所花費的時間越長。當閾值低于0.5時，重建模型相對穩定，當閾值超過0.5，重建線段數會減少，三維模型會逐漸模糊，尤其在閾值等于0.9時，重建模型線段數銳減，模型完全不符合預期效果。根據實驗結果得出結論：極線重疊閾值應該選擇一個較小的值，一般低于0.5更合適，這樣可以降低誤刪正確線匹配的可能性。

表1 不同二維線段匹配閾值τ下的重建時間與線段數Tab.1 Time and line numbers of 3D reconstruction under differentτ

圖3 不同閾值 τ對WIT圖書館三維重建模型的影響：（a）0.1，（b）0.25，（c）0.5，（d）0.75，（e）0.9Fig.3 Effects of different τon 3D reconstruction of library of WIT：（a）0.1，（b）0.25，（c）0.5，（d）0.75，（e）0.9

4.2 M和K對重建結果的影響

相鄰圖片個數M、在相鄰圖像中與特定二維線段相匹配的線段數K默認值是10，表示選取每張圖片最相鄰的10張圖片，在可視相鄰圖片中與某個二維線段相匹配的個數限制為10條。M與K的乘積表示潛在匹配二維線段的總數，在不考慮運行時間的情況下，M與K乘積越大，重建的結果越精確。

為了分析M與K單個參數對重建結果的影響，本文選取WIT圖書館圖片集，對M與K分別取M∈{5，10，20}與K∈{1，5，10，20}組合實驗，得到12組重建結果，實驗數據總表如表2所示，不同M、K對重建結果的運行時間和線段數影響如圖4所示。

當擁有充足的運行時間預算時，選用越大的M、K值，重建線段數越多，得到的重建結果會越精密。M選取值為5、20時，重建時間一直隨K值增大而增大。M選取值為10，當K值小于5時，重建時間隨K值增大而增大；當K值選取5到10時，重建時間隨K值增大而減小，K值為10時，重建時間最短；K值由10增到20時，重建時間與K值成正比。

表2 不同M、K下的圖書館圖片集重建時間與線段數Tab.2 Time and line numbers of 3D reconstruction of library of WIT at different M，K

圖4 不同M、K對重建結果的影響：（a）時間，（b）線段數Fig.4 Effects of different M，K of 3D reconstruction on（a）time，（b）line numbers

綜上所述，選用M=10、K=10組合時，能夠接近最佳重建效果并保證算法擁有較低的時間復雜度。

5 結 語

利用LSD線段提取算法檢測出圖片集中二維線段，在二維線段匹配階段，對二維線段匹配閾值τ、相鄰圖片個數M、在相鄰圖像中與特定二維線段相匹配的線段個數K三個重要參數進行評估，實驗結果表明當閾值τ低于0.5，M=10，K=10時三維建模效果最好并且運行時間可接受度較高，為后續對三維重建算法優化提供依據。