結(jié)合幾何約束和梯度描述子的直線段匹配

王競(jìng)雪，張 雪

(遼寧工程技術(shù)大學(xué)測(cè)繪與地理科學(xué)學(xué)院，遼寧 阜新 123000)

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

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

1 技術(shù)流程

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

圖1 直線匹配流程

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

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

(3) 在此基礎(chǔ)上進(jìn)行核線約束，一方面用于進(jìn)一步篩選候選直線，另一方面用于確定搜索影像上候選直線與目標(biāo)直線對(duì)應(yīng)的重疊部分。

(4) 對(duì)目標(biāo)直線和每條候選直線分別建立MMSD描述子。對(duì)目標(biāo)直線直接構(gòu)建MMSD描述子；對(duì)每條候選直線，分別以其對(duì)應(yīng)目標(biāo)直線的重疊部分為中心構(gòu)建MMSD描述子。

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

2 約束條件

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

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

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

2.2 核線約束

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

圖3 核線約束

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

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

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

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

(4) 當(dāng)候選直線段與兩條核線均相交，交點(diǎn)a′、b′，則認(rèn)為直線段a′b′為對(duì)應(yīng)的直線重疊區(qū)域，如圖3(d)所示。

3 直線匹配

3.1 梯度幅值描述子構(gòu)建

以目標(biāo)直線和候選直線對(duì)應(yīng)的重疊區(qū)域?yàn)榛A(chǔ)，對(duì)目標(biāo)直線和候選直線分別構(gòu)建高斯卷積梯度幅值的均值-標(biāo)準(zhǔn)差描述子。描述子具體構(gòu)建過程如下：

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

(1)

(2)

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

(3)

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

(4)

(5)

為使描述子不受光照影響，分別對(duì)上述均值和標(biāo)準(zhǔn)差向量進(jìn)行歸一化處理，得到直線L的梯度幅值描述子

(6)

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

3.2 匹配策略

本文結(jié)合最小歐氏距離和最近鄰距離比率NNDR確定同名直線。NNDR是指目標(biāo)直線與候選直線最近的歐氏距離與次最近歐氏距離的比值，其值小于設(shè)定的閾值則認(rèn)為與目標(biāo)直線特征歐氏距離最近的候選直線為目標(biāo)直線的同名直線。

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

(7)

計(jì)算目標(biāo)直線與其對(duì)應(yīng)的所有候選直線描述子之間的歐氏距離，設(shè)最近距離為d1，次近距離為d2，則確定同名直線的判斷條件為

(8)

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

4 試驗(yàn)及分析

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

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

圖5 試驗(yàn)影像

圖6 本文算法直線匹配結(jié)果

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

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

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

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

5 結(jié) 論

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

參考文獻(xiàn)：

[1] 王競(jìng)雪,宋偉東,韓丹，等.邊緣視差連續(xù)性約束的航空影像特征線匹配算法[J].信號(hào)處理，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].信號(hào)處理，2015,31(8):912-917.

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

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

[7] 張?jiān)粕?朱慶,吳波，等.一種基于三角網(wǎng)約束的立體影像線特征多級(jí)匹配方法[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，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] 陸麗娜.基于三焦點(diǎn)張量的多視圖目標(biāo)三維重建[D].南京：南京航空航天大學(xué)，2010：86-88.

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

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

[14] 陳浩，高志強(qiáng)，密保秀，等.引入極線約束的SURF特征匹配算法[J].中國(guó)圖象圖形學(xué)報(bào),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].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，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] 繆君，儲(chǔ)珺，張桂梅.一種仿射不變的直線描述子與直線匹配[J].電子學(xué)報(bào)，2015,43(12):2505-2512.

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