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

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

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

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

1 線段檢測技術(shù)

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

圖1 LSD算法示意圖：（a）圖片，（b）線場區(qū)域，（c）水平線支撐區(qū)域，（d）對準(zhǔn)點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)降序排序。由于三維建模中數(shù)圖片集的數(shù)據(jù)量較大并且任意兩張圖片都存在重疊部分的可能性較小，本文選取相鄰圖片進行二維線段篩選與匹配以達(dá)到高效建模的目的。本文使用相鄰圖片集合Vi中相似性評分最高的前M張圖片即VM i，假設(shè)圖片集I有N張圖片，該算法時間復(fù)雜度為O(MN)。

3 二維線段匹配

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

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

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

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

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

4 結(jié)果與討論

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

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

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

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

表1 不同二維線段匹配閾值τ下的重建時間與線段數(shù)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對重建結(jié)果的影響

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

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

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

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

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

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

5 結(jié) 語

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