視差引導下的影像線段特征匹配算法

王海彬,吳　軍,彭智勇

(桂林電子科技大學 電子工程與自動化學院，廣西 桂林　541004)

視差引導下的影像線段特征匹配算法

王海彬,吳軍,彭智勇

(桂林電子科技大學 電子工程與自動化學院，廣西 桂林541004)

摘要：為提高線段特征匹配的效率和準確率，通過引入SGM算法生成立體像對的初始視差信息,改進了影像線段特征匹配算法。該算法利用生成的視差信息建立待匹配線段的梯形搜索窗口，根據線段提供的幾何和灰度特性，剔除梯形搜索窗口內的歧義線段，通過最小視差差分準則，迭代計算待匹配線段與搜索窗口內候選線段的匹配代價，從而確定最終的同名線段。實驗結果表明，該算法提高了線段特征匹配的效率，且準確率達到98%以上。

關鍵詞：同名直線；視差信息；梯形搜索窗口；迭代準則

影像線段特征匹配是立體視覺、目標識別、運動估計等領域的重要實現(xiàn)手段，也是三維重建工作的基礎步驟和關鍵技術[1-3]，其實際是在2幅影像之間識別同名線段的過程[4]，是計算機視覺以及數字攝影測量領域研究的核心問題。現(xiàn)有的影像線段特征匹配算法可分為單線段特征匹配和組線段特征匹配2類。

1)基于單線段特征匹配過程主要考慮線段之間的對應限制條件，利用線段的幾何屬性和灰度屬性，或利用核線約束確定線段之間支持區(qū)域，自適應建立相似性測度來實現(xiàn)同名線段的匹配。文獻[1]利用線段特征與鄰域內以同名點為端點的虛擬線段的相交仿射不變性，進行候選同名線段的搜索，再借助核線約束確定待匹配線段與候選同名線段的重疊部分，最后通過線段特征的角度及支撐域灰度相關系數的綜合相似性測度進行匹配，但同名像點的數量會對算法產生一定影響。

2)基于組線段特征匹配過程主要利用線段特征間的拓撲信息完成同名線段的匹配。文獻[5]利用提取的點、線特征建立物體結構信息拓撲關系表，然后根據基匹配及拓撲關系表，利用圖深度遍歷的方法進行匹配傳遞，完成不同影像間同名線段的匹配，但對拓撲分析的復雜性以及對結構分割錯誤的敏感性影響了其在實際中的應用。

鑒于單線段特征匹配和組線段特征匹配的局限性，引入半全局匹配(semi global matching，簡稱SGM)算法生成立體像對的初始視差信息，改進了影像線段特征匹配算法。該算法充分利用生成的視差信息，即立體像對同名點的坐標關系，建立待匹配線段的梯形搜索窗口，縮小了待匹配線段的搜索范圍，能夠提高線段特征匹配的效率和準確率。

1算法原理

視差引導下的影像線段特征匹配流程如圖1所示。

圖1　視差引導下的影像線段特征匹配流程圖Fig.1　The flow chart of image segment feature matching with disparity guidance

以LOG算子為邊緣檢測手段，對左右影像進行線段特征提取，同時利用SGM算法生成立體像對的初始視差信息。然后根據同名點之間的視差信息建立待匹配線段的梯形搜索窗口，并利用線段的幾何和灰度特性剔除搜索窗口內的歧義線段。最后通過最小視差差分準則，迭代計算待匹配線段與候選線段的匹配代價，確定同名線段。

1.1SGM算法生成初始視差

采用SGM算法生成立體像對初始視差。SGM算法本質上是一種改進的動態(tài)規(guī)劃匹配算法，它以影像互信息作為匹配相似性測度，對光照變換不敏感，通過引入平滑約束來提高整體匹配的可靠性。SGM算法可分為3個階段[6-8]：

1)像素匹配代價計算。基于互信息的像素匹配代價為：

(1)

其中：mI1,I2為基于信息熵的影像互信息；Ip為待匹配影像像素p的灰度值；Iq為匹配影像中與p所對應的像素q=e(p,d)的灰度值，e(p,d)為在核線影像上2個同名像點之間的坐標關系；d為所對應同名像點之間的水平視差。若待匹配影像已沿核線方向進行掃描，則

mI1,I2可由影像的信息熵hI1、hI2與聯(lián)合信息熵hI1,I2定義，即

(2)

hI和hI1,I2經過泰勒級數展開可表示為：

(3)

(4)

其中：PI、PI1,I2分別為待匹配影像灰度概率分布及聯(lián)合概率分布，可通過影像灰度直方圖求出；?g(i,k)為高斯卷積；n為影像總像素。

2)視差計算。以像素匹配代價為基礎，SGM算法定義如下能量函數：

(5)

其中：p為任一像素；Np為像素p的鄰域；P1、P2為像素p鄰域內視差變化的懲罰系數，且P2>P1>0，P1懲罰較小的視差變化，P2懲罰較大的視差變化；D為待匹配影像的密集視差圖；T為選取懲罰系數的布爾函數。為解決E(D)全局最小化這一NP問題，SGM算法采用多路徑動態(tài)規(guī)劃優(yōu)化計算：

(6)

其中：S(p,d)為累加路徑代價，當路徑代價取得最小值時，所對應的視差d即為像素p的最優(yōu)視差；Lr(p,d)為像素p沿路徑r的匹配代價；Lr(p-r,d)為當前路徑r上像素p的前一點的匹配代價。

3)視差優(yōu)化。主要包括左右一致性視差檢查、濾波、插值、亞像素精度計算等。

SGM算法以其逐像素匹配能力為待匹配影像生成初始視差，為線段特征匹配提供同名像點的視差信息約束。

1.2基于視差信息的待匹配線段搜索窗口的建立

對于搜索窗口的建立，首先通過SGM算法得到立體像對之間的視差圖，即得出影像對間同名像點之間的坐標關系，如圖2所示。待匹配影像的某一像素p，坐標為(px,py)，匹配影像上的同名像點為q=e(p,d)，虛線為同名核線。

圖2　立體影像中同名像點的坐標關系Fig.2　The coordinate relation of the homonymous points in stereo image

在視差信息的引導下，根據線段的2個端點估計其同名線段的位置，從而確定以預測線段為中心的梯形搜索窗口[9]。待匹配線段搜索窗口的建立如圖3所示。

圖3　待匹配直線搜索窗口的建立Fig.3　Search window construction of the matching segment

給定待匹配線段a(p1,p2)，設其在匹配影像上預測出的梯形搜索窗口的4個端點為W1、W2、W3、W4。此時，

其中：p1-L1為線段端點p1沿水平核線方向在視差圖上向左搜索到的第1個當前視差有效像點；p1+R1為線段端點p1沿水平核線方向在視差圖上向右搜索到的第1個視差有效像點。同理，

待匹配線段的同名線段必定位于上述所建的梯形搜索窗口中。

1.3歧義直線的初步剔除

當待匹配線段在右影像上梯形搜索窗口形成后，為了剔除搜索窗口內的歧義線段，定義如下2個相似性度量函數。

1.3.1線段方向相似性函數

兩線段方向相似性函數定義為：

(8)

其中θi、θj分別為線段ai、bj的水平夾角。

1.3.2線段梯度幅值相似性函數

兩線段梯度幅值的相似性函數定義為：

(9)

其中G(ai)為線段ai的梯度幅值。

當式(8)、(9)同時滿足時，待匹配線段的候選線段才保留，否則將位于搜索窗口內的候選線段剔除。

1.4最小視差差分準則匹配代價計算

最小視差差分準則由Medioni等[10]于1985年引入匹配領域，并得到迅速發(fā)展。對于每個可能的匹配對(ai,bj)，依賴于線段ai、bj鄰域內的線段平均視差dhk和ai、bj所對應的線段平均視差dij。此時，評價函數v(ai,bj)定義為：

(10)

其中：t+1為迭代次數，t=0為第1次迭代；w(bj)為線段bj的搜索窗口；N1、N2分別為位于搜索窗口w(bj)、w(ai)內線段的數量；C1(ah)為迭代t次時的最優(yōu)集，其符合如下2個條件：

(11)

(12)

其中Sp(ai)為搜索窗口w(ai)內的線段集合，受式(8)、(9)兩個相似性度量函數的約束。

該評價函數在vt+1(ai,bj)=vt(ai,bj)條件下終止迭代。

最后，選擇最小的匹配代價v(ai,bj)表示2條線段為最好的匹配結果，并作為同名線段的輸出結果。

2實驗結果與分析

2.1實驗數據

為了測試改進算法的有效性，選取2組影像進行實驗，并以Microsoft Visual Studio 2010作為軟件開發(fā)工具，在惠普工作站(主頻3.6 GHz，內存16 GB)、Windows 7操作系統(tǒng)下實現(xiàn)該算法。實驗影像如圖4所示，其中圖4(a)為無人機拍攝的某地區(qū)測試立體像對，影像大小均為640像素×640像素，圖4(b)的航空影像對由Track Air公司的MIDAS攝影系統(tǒng)獲取，像對的像幅大小為3488像素×3811像素，空間分辨率約為0.1 m，均已作畸變校正處理。

圖4　實驗影像Fig.4　Experimental image

2.2直線匹配結果與分析

為了驗證算法的匹配效果，將改進算法與文獻[10]算法進行比較。文獻[10]算法與改進算法主要存在以下區(qū)別：

1)前者未引入視差信息，而是利用立體像對之間的最大視差，建立了較大且固定的搜索窗口，增加了線段搜索的范圍；

2)前者在搜索窗口內剔除歧義線段時，未考慮梯度幅值相似性度量，使部分候選線段未被剔除，增加了線段誤匹配的可能性。

以LOG算子為邊緣檢測手段，分別對立體影像對進行線段提取操作，建立立體像對線段特征集合，線段提取的具體算法參見文獻[11]。由于較短線段不能直接反映物體的重要輪廓特征，剔除較短線段后，將線段用粗線繪于原始影像中，顯示結果如圖5所示。利用SGM算法生成的視差圖如圖6所示。為避免引入誤差，除立體像對的密集匹配結果經一致性視差檢查去除誤配點外，均未對視差圖進行插值。

圖5　線段提取結果Fig.5　The extracting results of segment

圖6　SGM算法視差圖Fig.6　Disparity maps with SGM

根據文獻[10]的算法，測試像對線段匹配結果如圖7所示，錯誤匹配結果用黑色箭頭標示，如線段標號為7、14、54。

改進算法通過視差信息建立待匹配線段的梯形搜索窗口，分別利用線段的方向和梯度幅值相似性進行窗口內歧義線段的初步剔除，最后通過最小視差差分迭代，得到立體像對的同名線段結果，并將同名線段繪制于影像上進行分析，且將線段標號標記于影像上，用相同的編號來表明2條線段為同名線段。改進算法的線段匹配結果如圖8所示。為驗證實驗的有效性，針對圖8(b)中的2個方形局部區(qū)域，航空立體像對線段的匹配結果如圖9所示。

改進算法和文獻[10]算法的線段特征匹配結果如表1所示。

圖7　測試立體像對直線匹配結果Fig.7　Segment matching results of the testing stereo images

圖8　改進算法的線段匹配結果Fig.8　Segment matching results of the improved algorithm

圖9　航空立體像對線段匹配結果Fig.9　Segment matching results of aerial stereo images

算法立體像對提取線段數目最終匹配對正確匹配對匹配正確率/%時間/s文獻[10]測試圖像左測試圖像右104111615793.48.5改進算法測試圖像左測試圖像右104111585798.36.8文獻[10]航空影像左航空影像右2368247071666192.381.2改進算法航空影像左航空影像右2368247079178598.769.4

從圖9可看出，線段分布于建筑物邊緣，僅有少量線段分布于建筑物內部，這些線段作為特征線段具有很好的穩(wěn)定性和可靠性。從表1可看出，在相同數目的線段參與匹配的情況下，通過引入SGM算法生成的視差信息，改進算法的匹配階段的耗時明顯比文獻[10]算法少，提高了運算效率；由于充分利用了幾何和灰度特征約束，消除“歧義”線段時，避免了運算量大的最小視差差分迭代的相關計算，并且在匹配的準確率上也有明顯提升，達到98%以上。

3結束語

通過引入SGM算法生成的視差信息，提出了一種視差引導下的影像線段特征匹配算法，并在測試影像和航空影像上進行了實驗。實驗結果表明了此算法的有效性和準確性。對于更加復雜的場景圖像，線段端點提取的準確性和線段的數目是特征匹配的關鍵，因航空影像存在大量的遮擋區(qū)域，如何選擇合適的自動提取線段算法和將遮擋區(qū)域中的線段剔除，將是下一步研究的重點。

參考文獻:

[1]梁艷，盛業(yè)華，張卡，等.利用局部仿射不變及核線約束的近景影像直線特征匹配[J].武漢大學學報(信息科學版)，2014,39(2):229-233.

[2]陳寧江，李介谷.基于支持區(qū)域的直線段匹配[J].紅外與激光工程，2000,29(5):10-14.

[3]王偉璽，安菲佳，王競雪.多重約束條件下的影像直線匹配算法研究[J].測繪科學，2014,39(11):15-19.

[4]張祖勛，張劍清.數字攝影測量學[M].武漢：武漢大學出版社，2012:175-254.

[5]張春森，范金健.利用物體結構信息進行影像線特征關系匹配[J].武漢大學學報(信息科學版)，2012,37(9):1059-1063.

[6]吳軍，姚澤鑫，程門門.融合SIFT與SGM的傾斜航空影像密集匹配[J].遙感學報，2015,19(3):431-442.

[7]吳軍，程門門，姚澤鑫，等.傾斜航空影像的城區(qū)DSM生成[J].中國圖象圖形學報，2015,20(6):845-856.

[8]HIRSCHMULLER H.Stereo processing by semi global matching and mutual information[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2008,30(2):328-341.

[9]吳軍，陳丹清.基于相對定向結果和多視幾何約束的序列影像直線相關研究[J].武漢大學學報(信息科學版)，2004,29(12):1084-1088.

[10]MEDIONI G,NEVATIA R.Segment-based stereo matching[J].Computer Vision,Graphics and Image Processing,1985(31):2-18.

[11]張祖勛，吳軍，張劍清.一種基于線空間的直線抽取算法研究[J].武漢大學學報(信息科學版)，2004,29(3):189-194.

編輯：張所濱

Image Segment feature matching algorithm with disparity guidance

WANG Haibin, WU Jun, PENG Zhiyong

(School of Electronic Engineering and Automation, Guilin University of Electronic Technology, Guilin 541004, China)

Abstract：In order to improve the efficiency and accuracy of segment feature matching, SGM dense matching is used to obtain initial disparity information, segment feature matching algorithm for image is improved. Trapezoidal searching window is established by disparity information. After that, ambiguity segment in this search window are eliminated through geometric and gradation characteristics. Finally according to the minimizing parallax difference, the matching cost between candidate segment and matched segment is calculated iteratively for obtaining the same name segment. The experimental results show that the accuracy rate of segment feature matching is more than 98%.

Key words：homonymous segment; disparity information; trapezoidal searching window; iteration criterion

收稿日期：2015-12-25

基金項目：國家自然科學基金(60962003)；廣西自然科學基金(2014GXNSFAA118302)；廣西自動檢測技術與儀器重點實驗室基金(YQ15108)；廣西教育廳科研項目(KY2015YB111)

通信作者：吳軍(1973-)，男，湖北武漢人，教授，博士，研究方向為數字攝影測量、計算機視覺、遙感影像處理理論及應用。E-mail:wujun93161@163.com

中圖分類號：TP391.9

文獻標志碼：A

文章編號：1673-808X(2016)02-0129-07

引文格式： 王海彬，吳軍，彭智勇.視差引導下的影像線段特征匹配算法[J].桂林電子科技大學學報，2016,36(2):129-135.