王競雪，張 雪

(遼寧工程技術大學測繪與地理科學學院，遼寧 阜新 123000)

影像匹配實質(zhì)上是指兩幅或多幅影像之間通過相關函數(shù)確定同名特征，一般為點匹配、線匹配和面匹配，其中直線匹配是目前攝影測量和計算機視覺領域研究的熱點和難點[1-4]。目前，直線匹配研究多側(cè)重于兩個方面：一方面是尋找有效的幾何約束用于確定匹配候選，常用的約束條件有同名三角網(wǎng)約束[5-8]、同名點約束[9-10]、單應矩陣約束[11-12]、極線約束[13-15]等。這些約束條件將搜索影像上候選直線局限在設定的條件范圍內(nèi)，減少全局范圍匹配搜索時間，提高匹配效率。婁安穎等[12]結合單應矩陣約束和鄰域窗口灰度相似性確定同名直線；梁艷等[16]結合同名點約束和鄰域窗口灰度均值相關確定同名直線。然而上述這些方法更多側(cè)重于幾何約束，后續(xù)相似性計算大都直接利用直線鄰域窗口灰度信息，這種直接利用影像灰度信息的相似性計算方法對于影像視角變化較大或紋理復雜的影像難以獲得可靠的匹配結果。另一方面是直線描述子的構建，近幾年直線描述子成為匹配的研究熱點，類似于SIFT算子[17]，利用直線鄰域內(nèi)點的梯度等信息構建線描述子，取得較大的進展?？娋忍岢鰧⒋ヅ渲本€離散為若干點的集合[18]，根據(jù)直線方向和長度定義描述子的主方向和長度，統(tǒng)計離散點鄰域梯度信息構建128維描述子，得到n×128的描述子矩陣，n為直線上采樣點數(shù)目。該描述子僅利用直線上的點構建描述子，舍棄直線鄰域范圍內(nèi)的點，對于復雜地物影像，可靠性有待提高。在無任何幾何約束條件下，王志衡等提出了具有平移、旋轉(zhuǎn)、光照不變性的梯度幅值均值-標準差描述子(magnitude mean-standard deviation descriptor,MMSD)，用于直線匹配[19]。與直接基于灰度窗口相關相比，該描述子具有較好可區(qū)分性，能取得較好的直線匹配結果。但這種無需任何幾何約束，單一利用描述子的直線匹配方法對于拍攝傾角較大的復雜地物紋理影像，不僅耗時而且匹配可靠性有待提高。

因此，本文在已有MMSD描述子基礎上，提出一種結合幾何約束和梯度描述子的直線段匹配算法。在已有可靠同名點的基礎上，利用同名三角網(wǎng)和核線約束確定匹配候選，以目標直線和候選直線對應的重疊段為中心建立直線支撐域，并利用高斯卷積函數(shù)對梯度幅值進行加權處理用于候選描述子構建，保證了直線匹配的可靠性。

1 技術流程

結合幾何約束和梯度描述子的直線匹配算法，整理流程如圖1所示。

圖1 直線匹配流程

(1) 首先利用SIFT算子對兩張影像進行匹配，并采用RANSAC算法對結果進行誤匹配剔除，得到初始可靠同名點，同時對參考影像、搜索影像進行直線提取。

(2) 為了提高直線匹配效率及正確率，取代傳統(tǒng)窮舉法匹配策略，本文利用同名點構建參考影像、搜索影像上同名三角網(wǎng)，用于約束后續(xù)匹配，縮小候選直線搜索范圍。

(3) 在此基礎上進行核線約束，一方面用于進一步篩選候選直線，另一方面用于確定搜索影像上候選直線與目標直線對應的重疊部分。

(4) 對目標直線和每條候選直線分別建立MMSD描述子。對目標直線直接構建MMSD描述子；對每條候選直線，分別以其對應目標直線的重疊部分為中心構建MMSD描述子。

計算目標直線與候選直線描述子之間的歐氏距離，并結合最小歐氏距離和最近鄰距離比率(nearest neighbor distance ratio，NNDR)，確定同名直線。

2 約束條件

2.1 同名三角網(wǎng)約束

三角網(wǎng)約束指同名直線應位于同名三角網(wǎng)中。利用初始匹配獲取同名點構建參考影像、搜索影像上同名三角網(wǎng)。首先確定參考影像上目標直線經(jīng)過的三角形，對應的將搜索影像上同名三角形中存在的直線作為該目標直線的匹配候選直線。如圖2(a)為參考影像上索引為1的直線段經(jīng)過的三角形，圖2(b)為搜索影像上對應的同名三角形內(nèi)經(jīng)過的直線，索引號分別為2、3、4、5、6。

圖2 三角網(wǎng)約束

2.2 核線約束

為了提高匹配的效率，進一步利用核線約束對上述三角網(wǎng)約束確定的候選直線進行剔除與選擇。同時為了提高描述子的可靠性，確保兩張影像上對應直線描述子構建的區(qū)域一致性，以目標直線為基礎，需要利用核線確定候選直線與目標直線對應的重疊直線區(qū)域，如圖3所示。

圖3 核線約束

圖3中，l、l′分別為參考影像上目標直線段和搜索影像上候選直線段，兩直線段端點分別為a、b和c、d。計算目標直線段l兩端點a、b在搜索影像上的核線Ha、Hb，則搜索影像上候選直線l′與兩核線相交的交點為對應的同名端點，兩端點連線即為候選直線與目標直線對應的重疊區(qū)域。確定候選直線與目標直線對應的重疊區(qū)域，一般可分為以下4種情況：

(1) 當候選直線位于核線Ha、Hb范圍之外，說明候選直線與目標直線沒有重疊部分，將其剔除，如圖3(a)所示。

(2) 當候選直線位于兩核線之間，延長其兩邊端點至核線Ha、Hb上，交點為a′、b′，則延長后的直線段a′b′為對應的重疊區(qū)域，如圖3(b)所示。

(3) 當候選直線段與其中一條核線相交，如圖3(c)所示，l′與核線Ha相交，則交點a′為重疊段的一個端點，延長直線另一端與核線Hb相交，交點b′為重疊段的另一個端點，至此，對應的直線重疊區(qū)域a′b′已經(jīng)確定。

(4) 當候選直線段與兩條核線均相交，交點a′、b′，則認為直線段a′b′為對應的直線重疊區(qū)域，如圖3(d)所示。

3 直線匹配

3.1 梯度幅值描述子構建

以目標直線和候選直線對應的重疊區(qū)域為基礎，對目標直線和候選直線分別構建高斯卷積梯度幅值的均值-標準差描述子。描述子具體構建過程如下：

假定任一直線段L，長度為w，以其為中心軸建立如圖4(a)所示的長為w，寬為2r+1的矩形直線支撐域，并將其分解為2r+1條等長的平行直線段，如圖4(b)所示。對于候選直線，需要根據(jù)前文中核線確定的同名端點為基礎，確保候選直線支撐域方向與目標直線支撐域方向一致。

(1)

(2)

式中，d為點到直線距離；σ為支撐域長度的一半。對矩陣M(L)每一列進行高斯加權，則經(jīng)過加權之后的梯度幅值矩陣為

(3)

圖4 直線平行支撐域及分解

(4)

(5)

為使描述子不受光照影響，分別對上述均值和標準差向量進行歸一化處理，得到直線L的梯度幅值描述子

(6)

因梯度幅值本身具有旋轉(zhuǎn)不變性，因此MMSD描述子具有平移旋轉(zhuǎn)不變性、光照不變性等優(yōu)點。

3.2 匹配策略

本文結合最小歐氏距離和最近鄰距離比率NNDR確定同名直線。NNDR是指目標直線與候選直線最近的歐氏距離與次最近歐氏距離的比值，其值小于設定的閾值則認為與目標直線特征歐氏距離最近的候選直線為目標直線的同名直線。

設目標直線梯度描述子為(l1,l2,l3,…,lk)，候選直線的梯度描述子為(r1,r2,r3,…,rk)，則二者歐氏距離計算公式如下

(7)

計算目標直線與其對應的所有候選直線描述子之間的歐氏距離，設最近距離為d1，次近距離為d2，則確定同名直線的判斷條件為

(8)

即當比值小于τ則判定距離目標直線特征最近的候選直線為最終的同名直線。

4 試驗及分析

為驗證本文梯度幅值描述子具有旋轉(zhuǎn)不變性、光照不變性及其穩(wěn)健性，本文選取三組近景影像和一組航空影像進行直線匹配試驗。如圖5所示，其中圖5(a)、圖5(b)為存在旋轉(zhuǎn)變化的影像對，圖5(c)為光照不同的影像對，圖5(d)為建筑物區(qū)域航空影像對。同時為了進行對比分析，本文還實現(xiàn)了另外兩種算法的直線匹配試驗：①無約束條件下的MMSD描述子直線匹配；②相同約束條件下，基于灰度均值標準差描述子(gray mean-standard deviation descriptor，GMSD)的直線匹配。鑒于文章篇幅，文中僅顯示本文算法對上述四組影像進行直線匹配的結果，如圖6 所示，其中黑色線為正確匹配直線，粗線為錯誤匹配直線。直線提取及匹配結果統(tǒng)計見表1，通過人工目視判讀方法判斷匹配結果正確與否，表中MN(matching number)表示匹配直線的總數(shù)目，EM(error matching)表示錯誤匹配數(shù)目，CR(correct ratio)表示匹配正確率。試驗過程中，NNDR閾值τ設定為0.8，直線支撐域建立過程中r=10。

圖5(a)影像旋轉(zhuǎn)角度約為45°，左、右影像滿足條件的直線數(shù)為471、477，GMSD與本文算法匹配得到的直線數(shù)目分別為229、225，正確匹配率分別為94.7%、98.2%。

圖5(b)所示兩張影像旋轉(zhuǎn)角度約為30°，參考影像、搜索影像上提取直線數(shù)目分別為1109、757，GMSD與本文算法匹配得到的直線數(shù)目分別為344、259，本文算法同名直線數(shù)目少于前者，但錯誤匹配數(shù)目較少，匹配的正確率為90.7%。

圖5(c)為不同光照強度下同一建筑物拍攝獲取的影像對，參考影像、搜索影像上提取直線數(shù)目分別為728、446，GMSD與本文算法匹配得到的直線數(shù)目分別為249、267，正確匹配率分別為76.3%、92.1%。

圖5 試驗影像

圖6 本文算法直線匹配結果

影像提取直線數(shù)目描述子MNEMCR/(%)圖5(a)471/477GMSD2291294.7無約束MMSD1213769.4本文算法225498.2圖5(b)1109/757GMSD3446082.5無約束MMSD803951.2本文算法2592490.7圖5(c)728/446灰度相關2495976.3無約束MMSD2452291.0本文算法2672192.1圖5(d)839/882GMSD3793790.2無約束MMSD2423187.1本文算法4001496.5

圖5(d)為同視角同距離不同時間段對同一建筑物區(qū)域進行拍攝得到的影像對，參考影像、搜索影像上提取直線數(shù)目分別為839、882，GMSD結果中錯誤匹配直線數(shù)目為37，正確匹配率為90.2%，而本文算法匹配數(shù)目相對較多，誤匹配直線數(shù)目為14，正確匹配率為96.5%。上述試驗結果表明，基于梯度幅值描述子的可靠性要強于GMSD描述子。

在無約束條件下，利用文獻[19]中MMSD算法對上述四組影像進行直線匹配，與上述兩種方法相比，該方法匹配得到同名直線數(shù)目最少，但是錯誤直線數(shù)目相對較多。這是由于缺乏有效的幾何約束，匹配候選較多，導致錯誤匹配較多，匹配正確率較低。如對于圖5(d)影像，該方法和本文算法匹配得到同名直線的數(shù)目分別為242、400，誤匹配直線數(shù)目分別為31、14，該方法正確率為87.1%，而本文算法在結合三角網(wǎng)和核線約束后，匹配正確率提升至96.5%。

根據(jù)表1可知，在參考影像、搜索影像上直線提取數(shù)目相同的情況下，針對上述四組試驗影像，相比于GMSD和無約束MMSD匹配方法，本文結合幾何約束和梯度幅值描述子的直線匹配算法得到的同名直線數(shù)目多，錯誤少，匹配正確率高。試驗結果表明，本文算法具有一定的可靠性。

5 結 論

針對無約束條件下，基于描述子直線匹配的可靠性問題，本文提出了一種結合幾何約束和梯度描述子的直線匹配算法。該方法在已有MMSD描述子基礎上，增加三角網(wǎng)約束和核線約束確定匹配候選，減少匹配搜索范圍，提高匹配的效率及正確率；同時在描述子構建過程中，分別以目標直線和候選直線對應的重疊段直線為中心建立直線支撐域，并利用高斯卷積函數(shù)對支撐域內(nèi)像素點梯度幅值進行加權處理，提高描述子的有效性及可靠性。通過選擇4組不同類型的影像對進行匹配試驗，并與無約束MMSD描述子和GMSD描述子兩種方法進行對比分析，得出如下結論：與GMSD相比，基于梯度幅值的描述子MMSD適用性及可靠性更強；與無約束MMSD相比，可靠的幾何約束不僅提高了直線匹配的效率，同時大大提高了直線匹配的正確率。

參考文獻：

[1] 王競雪,宋偉東,韓丹，等.邊緣視差連續(xù)性約束的航空影像特征線匹配算法[J].信號處理，2015,31(3):364-371.

[2] CHEN M,SHAO Z,LIU C,et al.Scale and Rotation Robust Line-based Matching for High Resolution Images [J].Optik-International for Light and Electron Optics,2013,22(124):5318-5322.

[3] HAN W,ZHENG J B.Fast and Accurate Stereo Matching Algorithm Based on Epipolar Line Restriction[J].Computer Engineering & Applications,2008,44(1):51-53.

[4] 朱紅,宋偉東,杜北，等.重合度約束的近景影像直線匹配算法[J].信號處理，2015,31(8):912-917.

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

[6] 朱慶,吳波,趙杰.基于自適應三角形約束的可靠影像匹配方法[J].計算機學報,2005,28(10):1734-1739.

[7] 張云生,朱慶,吳波，等.一種基于三角網(wǎng)約束的立體影像線特征多級匹配方法[J].武漢大學學報(信息科學版)，2013,38(5):522-527.

[8] WO B，ZHANG Y S，ZHU Q.Integrated Point and Edge Matching on Poor Textural Images Constrained by Self-adaptive Triangulations[J].ISPRS Journal of Photogram-metry and Remote Sensing，2012，68(1)：40-55.

[9] FAN B,WU F，HU Z.Line Matching Leveraged by Point Correspondences[C]∥IEEE Conference on Computer Vision and Pattern Recognition.San Francisco:IEEE,2010:390-397.

[10] FAN B，WU F，HU Z.Robust Line Matching through Line Point Invariants[J].Pattern Recognition,2012，45(2)：794-805.

[11] 陸麗娜.基于三焦點張量的多視圖目標三維重建[D].南京：南京航空航天大學，2010：86-88.

[12] 婁安穎，宋偉東，劉薇.基于單應矩陣的直線匹配[J].遙感信息，2011,15(3):9-13.

[13] 易成濤，王孝通，徐曉剛.基于極線約束的角點匹配快速算法[J].系統(tǒng)仿真學報，2008,20(S1):371-374.

[14] 陳浩，高志強，密保秀，等.引入極線約束的SURF特征匹配算法[J].中國圖象圖形學報,2016,21(8):1048-1056.

[15] SCHMID C,ZISSERMAN A.The Geometry and Matching of Lines and Curves over Multiple View[J].International Journal of Computer Vision,2000,40(3):199-233.

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

[17] LOWE D G.Distinctive Image Features from Scale-invariant Keypoints[J].International Journal of Computer Vision,2004,60(2):91-110.

[18] 繆君，儲珺，張桂梅.一種仿射不變的直線描述子與直線匹配[J].電子學報，2015,43(12):2505-2512.

[19] 王志衡，吳福朝.均值-標準差描述子與直線匹配[J].模式識別與人工智能，2009,22(1):32-39.