一種基于多重約束的特征線匹配方法*

王欣波，王亞偉，厲寶山，張 寧，姜 濤，徐 剛，魏 麗

（1.中國科學(xué)院自動化研究所，北京 100190；2.佛山市科自智能系統(tǒng)技術(shù)有限公司，廣東佛山 528010；3.渤海造船廠集團(tuán)有限公司，遼寧葫蘆島 125000）

0 引言

特征線匹配是基于圖像的三維重建中的關(guān)鍵問題之一，目前已廣泛應(yīng)用于構(gòu)建攝影測量中的圖像查找、基于特征的對象識別、圖像拼接、運(yùn)動檢測、古建筑的三維場景恢復(fù)[1-3]等領(lǐng)域。現(xiàn)有的特征線匹配方法[4-12]可分為3 類。（1）基于特征線幾何屬性的匹配方法：該方法主要依賴提取特征線的長度、方向等幾何屬性進(jìn)行特征線的匹配。由于缺乏有效的約束條件，此類方法存在算法復(fù)雜度高、特征線誤匹配率高等問題。（2）基于特征線鄰域灰度的匹配方法：該方法主要依賴特征線周圍的鄰域灰度相似信息，因此適用于紋理豐富的圖像，在紋理重復(fù)嚴(yán)重的場景中存在誤匹配率高的問題。（3）基于特征線幾何約束的匹配方法：該方法主要借助多視幾何中單應(yīng)矩陣、極線約束等幾何約束，進(jìn)行誤匹配的剔除。因此理論基礎(chǔ)強(qiáng)，匹配結(jié)果嚴(yán)重依賴于幾何模型，因此不適用于視差變化較大、紋理重復(fù)的場景。

因此，針對結(jié)構(gòu)復(fù)雜、紋理重復(fù)嚴(yán)重的場景，受采集環(huán)境、采集設(shè)備、采集對象等因素影響，提取的特征線具有斷線情況嚴(yán)重、局部描述相似的特點(diǎn)，若采用上述特征線匹配方法，特征線匹配結(jié)果存在特征線匹配數(shù)量少、特征線匹配誤匹配率高等問題，進(jìn)而影響到后續(xù)結(jié)果。

針對上述問題，本文融合特征線區(qū)域信息和局部特征點(diǎn)信息，從灰度、尺度、旋轉(zhuǎn)等多角度，采用多重約束的思想，提出了一種新的特征線匹配方法。輸入兩幅待匹配圖像，該方法首先采用LSD 方法檢測圖像的特征線，利用SIFT 方法檢測圖像特征點(diǎn)。為了提高特征線匹配效率，將特征線和特征點(diǎn)信息融合為圖像特征集合，并計(jì)算每一條特征線矩形支持區(qū)域；其次在特征線矩形支持區(qū)域內(nèi)，依據(jù)核線約束和特征線兩端點(diǎn)及兩側(cè)緊鄰點(diǎn)間局部特征信息的NCC 度量值，計(jì)算特征線的待匹配特征線的支持區(qū)域；采用核線約束和灰度約束確定的候選匹配特征線，有效解決了圖像特征線的旋轉(zhuǎn)和尺度產(chǎn)生的誤匹配問題；最后從匹配特征線間的角度、垂直距離和水平距離3個角度出發(fā)，結(jié)合灰度相似性度量，在待匹配特征線的支持區(qū)域內(nèi)采用多重約束進(jìn)一步約束確定同名特征線，從而有效解決了一對多（多對一）的特征線誤匹配問題。

1 算法原理

相較于特征點(diǎn)匹配，特征線具有更強(qiáng)的幾何約束信息，因此廣泛應(yīng)用于特征匹配過程中。依據(jù)特征線的區(qū)域信息和局部特征點(diǎn)信息，本文提出的一種基于多重約束的圖像特征線匹配算法流程如圖1 所示。該算法主要分為5 個過程：（1）輸入待匹配的兩幅圖像，采用LSD算法檢測待匹配圖像的特征線，利用SIFT 算法檢測待匹配圖像的幾何特征點(diǎn)信息，融合特征線和特征點(diǎn)組合位特征集合；（2）依據(jù)特征線周圍鄰域特征點(diǎn)信息，計(jì)算特征線支持區(qū)域及每一條特征線周圍的鄰域特征點(diǎn)集；（3）采用NCC 方法度量特征線間的灰度相似性，獲得同名點(diǎn)匹配集合；（4）結(jié)合核線約束條件，確定待匹配圖像中特征線的支持區(qū)域，核線約束有效地保證了特征線匹配的旋轉(zhuǎn)不變性和尺度不變性；（5）在待匹配圖像特征線的支持區(qū)域內(nèi)，綜合采用特征線間的角度、垂直距離、水平距離進(jìn)一步約束特征線的匹配。進(jìn)而解決由于特征線檢測方法導(dǎo)致的“一對多”或“多對一”特征線誤匹配問題。

圖1 特征線匹配流程

2 具體方法

2.1 相關(guān)定義

給定兩幅待匹配圖像{IA，IB}，IA為輸入原始圖像，IB為待匹配圖像；首先利用LSD 對圖像IA進(jìn)行特征線提取后生成特征線集合LA={lA1，lA2，lA3，…，lAm}，采用LSD 對圖像IB進(jìn)行特征線提取后生成特征線集合LB={lB1，lB2，lB3，…，lBn}。利用SIFT對圖像IA進(jìn)行特征點(diǎn)提取后生成特征點(diǎn)集合PA={pA1，pA2，pA3，…，pAw}，采用SIFT 對圖像IB進(jìn)行特征點(diǎn)提取后生成特征點(diǎn)集合PB={pB1，pB2，pB3，…，pBv}。已有方法對兩幅圖像進(jìn)行特征檢測后的結(jié)果為LA={lA2，lA2，lA3，…，lAm}、LB={lB2，lB2，lB3，…，lBn}和PA={pA1，pA2，pA3，…，pAw}、PB={pB1，pB2，pB3，…，pBv}。其中：pAi={(XAi，gAi)，i=1，2，…，w}，pBj={(XBj，gBj)，j=1，2，…，v}；n為圖像IA提取的特征線數(shù)量；w為圖像IA提取的特征點(diǎn)數(shù)量；m為圖像IB提取的特征線數(shù)量；v為圖像IB提取的特征點(diǎn)數(shù)量；X為圖像中的檢測到特征點(diǎn)p的幾何位置即為（x，y）；g為圖像中檢測到特征點(diǎn)的灰度信息。結(jié)合上述特征點(diǎn)和特征線信息，相關(guān)定義如下。

（1）定義1。目標(biāo)特征線的矩形支持區(qū)域RAi：設(shè)給定圖像IA中任意特征線lAi，采用下式計(jì)算特征線lAi的矩形支持區(qū)域RAi：

其中L(lAi)為特征線lAi矩形支持區(qū)域的長，即特征線長度；2ε為定義的矩形支持區(qū)域的寬；D（）表示為歐氏距離。

（2）定義2。矩形支持區(qū)域RAi的局部特征點(diǎn)集合RPAi：設(shè)給定圖像IA中任意特征線lAi，采用下式計(jì)算矩形支持區(qū)域RAi的局部特征點(diǎn)集合RPAi：

（3）定義3。NCC同名特征點(diǎn)度量：給定圖像IA中任意特征線lAi，其矩形支持區(qū)域RAi內(nèi)特征點(diǎn)任一pAi查找同名點(diǎn)pBj的過程為：假設(shè)選取的滑動窗口的長和寬分別為2a+1，2b+1，特征點(diǎn)pAi、pBj位于滑動窗口的中心，特征點(diǎn)pAi、pBj的NCC度量值NCC(pAi,pBi)為：

由定義3可知：確定模板下任意兩個特征點(diǎn)的NNC度量結(jié)果范圍為[-1，1]，也就是說在當(dāng)前模板下，若任意兩個特征點(diǎn)對pAi、pBj灰度完全匹配，則NCC值為1；若任意兩個特征點(diǎn)對pAi、pBj灰度完全不相關(guān)，則NCC值為-1。NCC方法度量的特征間相關(guān)性有效地約束了特征點(diǎn)間的灰度變化，進(jìn)一步保證了特征點(diǎn)間的灰度不變性。

2.2 特征線匹配過程

受到圖像采集環(huán)境、采集設(shè)備等因素影響，待匹配中同一對象間存在尺度、旋轉(zhuǎn)等變換，因此采用LSD提取的特征線存在特征線不完備、提取特征線錯誤率較高等問題。究其原因，主要問題在兩圖像中同一對象提取的特征線長度、方向、灰度等信息都不一致，同一特征線兩端點(diǎn)間經(jīng)常存在不一致的情況，最終影響到特征線匹配結(jié)果。針對上述問題，本文結(jié)合特征線和鄰域特征點(diǎn)信息，采用核線約束確定待匹配特征線的支持區(qū)域，進(jìn)而解決了特征線匹配過程中的旋轉(zhuǎn)和尺度問題；利用特征線間的角度距離，垂直距離和水平距離對待匹配的錯誤特征線進(jìn)行剔除，進(jìn)一步刪除了誤匹配的特征線。結(jié)合圖1 中的流程，特征線匹配過程如下。

2.2.1 計(jì)算待匹配特征線的支持區(qū)域

輸入圖像IA、IB，結(jié)合定義（1）～（3）計(jì)算：圖像IA任一特征線li的特征線矩形支持區(qū)域Ri、矩形支持區(qū)域Ri的局部特征點(diǎn)集合，并組合為特征集合。依據(jù)特征線li的特征線矩形支持區(qū)域Ri范圍內(nèi)且位于特征線兩側(cè)距離特征線最近的特征點(diǎn)為基礎(chǔ)，計(jì)算待匹配圖像IB中待匹配特征線的支持區(qū)域。

待匹配圖像IB中待匹配特征線的支持區(qū)域具體如圖2 所示，在圖中，給定圖像IA任一特征線lAi，設(shè)d1，d2為特征線lAi的兩個端點(diǎn)坐標(biāo)，p1，p2為特征線lAi矩形支持區(qū)域RAi的兩個局部特征點(diǎn)。利用圖像對間的核線約束條件，設(shè)圖像IA、IB的核線為h1，h2。理想情況下，d1、d2、p1、p2在待匹配圖像IB中的匹配信息為，即端點(diǎn)的連線li′應(yīng)該為圖像IA中特征線li的正確匹配特征線。然而受到圖像采集環(huán)境、采集設(shè)備的影響，特征線匹配過程中的確定存在一定的問題。

圖2 構(gòu)建待匹配特征線的支持區(qū)域

針對上述問題，本文基于核線約束思想，將待匹配特征線的約束限制在局部區(qū)域內(nèi)，進(jìn)一步提高特征線匹配的效率，首先構(gòu)建待匹配圖像IB中特征線li的局部支持區(qū)域。具體過程為：首先選擇圖像IA特征線li，圖像IB特征線，依據(jù)NCC度量圖像兩對端點(diǎn)（d1、d2）與（、）；其次若（d1、d2）與（、）間滿足NCC度量條件，選擇li的局部特征點(diǎn)集合RPAi中的特征點(diǎn)p1、p2，選擇的局部特征點(diǎn)集合RPAi中的特征點(diǎn)、，并計(jì)算（、）的核線h1、h2；然后以、的連線為基礎(chǔ)，過、兩點(diǎn)做平行于的兩條平行直線；最后平行直線且與核線h1、h2相交，構(gòu)成的四邊形區(qū)域可定義為圖像IB中待匹配特征線li的支持區(qū)域RBj。

2.2.2 支持區(qū)域內(nèi)候選匹配特征線的確定

由于待匹配圖像間同一對象的特征線間存在端點(diǎn)不一致的情況，為了提高匹配特征線效率，在待匹配支持區(qū)域內(nèi)結(jié)合特征線間的角度、距離等信息對特征線進(jìn)行剔除。具體過程為：在圖像IB中確定圖像IA特征線li中的支持區(qū)域RBj后，將li與圖像IB內(nèi)所有特征線進(jìn)行計(jì)算，若圖像IB中任一特征線與支持區(qū)域RBj的交集不為空，將該特征線標(biāo)記為特征線li的候選待匹配特征線。具體如圖2 所示，經(jīng)過觀察，圖像IA特征線li與支持區(qū)域RBj內(nèi)的候選特征線存在以下幾種情況，可羅列為特征線l1、l2、l3、l4、l5、l6、l7。若采用單一的NCC 和距離度量函數(shù)，與特征線li匹配的特征線可能存在一對多（多對一）的情況。

為了解決上述問題，需對錯誤匹配的特征線進(jìn)行剔除，從圖2 中也可以看到：由于特征線檢測方法的不同，待匹配特征線可能分為l2、l3兩條特征線的情況，而l4僅僅與支持區(qū)域RBj局部相交，l4很可能是錯誤匹配特征線不在待匹配特征線的支持區(qū)域內(nèi)，所以l4不是待匹配的特征線。綜合上述情況，可從角度、垂直距離、水平距離三個角度考慮，在支持區(qū)域RBj內(nèi)剔除錯誤的匹配特征線，進(jìn)一步提高特征線匹配效率。具體如下。

（1）角度約束：參照圖2，匹配特征線間的角度約束可定義為：選擇在支持區(qū)域RBj待匹配特征線，如果li與的角度θ小于一定的閾值，則認(rèn)為是正確的候選待匹配特征線；如果li與的角度大于閾值，則認(rèn)為是錯誤的候選待匹配特征線，應(yīng)剔除。由于角度具有旋轉(zhuǎn)不變性，因此角度約束進(jìn)一步保證了特征線的旋轉(zhuǎn)不變性。本文為中l(wèi)i與角度θ值定義為特征線間斜率的反正切函數(shù)，經(jīng)過反復(fù)實(shí)驗(yàn)，θ值設(shè)置為小于π/8。

（2）垂直約束：參照圖3，匹配特征線間的垂直距離約束可定義為：在支持區(qū)域RBj內(nèi)，待匹配特征線lj的兩個端點(diǎn)到特征點(diǎn)li的距離為D1、D3，特征點(diǎn)li的兩個端點(diǎn)到待匹配特征線lj的距離為D2、D4，依據(jù)上述距離，待匹配特征線lj到特征點(diǎn)li的距離若，則待匹配特征線lj為特征點(diǎn)li的候選特征線。由于距離具有尺度不變性，因此垂直距離的約束進(jìn)一步保證了特征線匹配間的尺度不變性。經(jīng)過反復(fù)實(shí)驗(yàn)，λ為不超過3個像素。

圖3 垂直距離約束

（3）水平約束：參照圖4，水平距離約束可定義為：在支持區(qū)域RBj內(nèi)，待匹配特征線lj的中點(diǎn)與li中點(diǎn)間的距離可表示為Dh。若，則待匹配特征線lj為特征點(diǎn)li的候選特征線。水平約束的使用有一定的限制：待匹配圖像對間的平移向量不應(yīng)太大。

圖4 水平距離約束

2.2.3 待匹配特征線間的灰度相似性約束

上述過程從角度、水平、垂直距離約束出發(fā)，保證了特征線匹配具有旋轉(zhuǎn)、尺度不變性，為了提高特征線匹配效率，結(jié)合特征線間的灰度相似性進(jìn)行約束。具體過程為：輸入圖像IA特征線li和li的支持區(qū)域RBj中的候選特征線，首先將特征線li和候選匹配特征線lj離散化長度一致的離散點(diǎn)，設(shè)特征線li離散的特征點(diǎn)個數(shù)為M、特征線lj離散的特征點(diǎn)個數(shù)為N；然后以li、lj為中心軸，在li、lj的矩形支持區(qū)域內(nèi)選擇2r條平行線，分別標(biāo)記為Gr(li)、Gr(lj)，設(shè)矩形支持區(qū)域內(nèi)第i條平行線上第j個像素點(diǎn)的灰度值為。考慮到特征線矩形支持區(qū)域內(nèi)平行線的遠(yuǎn)近對特征線匹配結(jié)果的影響，本文采用權(quán)重因子ζ對支持區(qū)域內(nèi)平行線的權(quán)重進(jìn)行設(shè)置，具體思想為：權(quán)重因子ζ在平行支持域內(nèi)，從特征線出發(fā)，依照平行線的兩側(cè)遞減，因此權(quán)重因子定義為如下分段函數(shù)：

則Gr(li)、Gr(lj)內(nèi)平行線上點(diǎn)的灰度值矩陣為：

灰度值矩陣的均值為：

利用NCC度量兩個平行支持域的灰度相似性：

采用NCC度量特征線li和候選匹配特征線lj后，進(jìn)一步保證了特征線li和候選匹配特征線lj具有灰度不變性。且特征線li和候選匹配特征線lj灰度遵循線性變化約束，依照線性約束條件g(A)=αg(B)+β，特征線li和候選匹配特征線的灰度變化關(guān)系滿足ljG(li)=αG(lj)+β，α、β值本文設(shè)置為0.5 和0.5。只要特征線li和候選匹配特征線lj的灰度變化滿足上式，則li和lj為正確的特征線匹配；否則，li和lj為錯誤的匹配，該剔除。

3 實(shí)驗(yàn)分析

為了驗(yàn)證本文提出的特征線匹配算法的效率，采用不同場景下的圖像對進(jìn)行驗(yàn)證。實(shí)驗(yàn)環(huán)境為：采用Windows 10 作為操作系統(tǒng)，采用英特爾Core i7-8750H @ 2.20GHz 為處理器，內(nèi)存為8G；采用MatlabR2016a 為編程語言，Opencv3.4.5 計(jì)算機(jī)視覺庫，以標(biāo)準(zhǔn)公開數(shù)據(jù)集中包含旋轉(zhuǎn)變換、尺度變換、光照變化的3對圖像對為實(shí)驗(yàn)數(shù)據(jù)，進(jìn)行特征線匹配實(shí)驗(yàn)。

為了減少實(shí)驗(yàn)數(shù)據(jù)的誤差，與文獻(xiàn)[13]相同，本文采用SIFT進(jìn)行特征點(diǎn)提取，采用LSD方法進(jìn)行特征線提取，特征線匹配結(jié)果與文獻(xiàn)[13]和文獻(xiàn)[14]中的算法進(jìn)行比較。3 組圖像的特征點(diǎn)檢測結(jié)果如表1 所示。具體檢測結(jié)果如圖5 所示，其中第一組和第二組的特征線匹配結(jié)果中特征線匹配總數(shù)量、正確匹配對數(shù)量結(jié)果參照文獻(xiàn)[13]中數(shù)據(jù)，第三組圖的特征線匹配結(jié)果來源于文獻(xiàn)[14]中的數(shù)據(jù)。

表1 數(shù)據(jù)集信息

圖5 對比實(shí)驗(yàn)結(jié)果

4 結(jié)束語

在場景復(fù)雜、重復(fù)紋理、光照變換的復(fù)雜場景中，現(xiàn)有的特征線匹配方法存在匹配數(shù)量少、誤匹配率高等問題，進(jìn)而直接影響了特征線匹配結(jié)果。針對上述問題，本文融合特征線信和和局部特征點(diǎn)信息，提出了一種基于多重約束的特征線匹配方法，該方法從旋轉(zhuǎn)、尺度、灰度3 個角度對特征線匹配結(jié)果進(jìn)行約束，進(jìn)而有效解決了復(fù)雜場景中誤匹配率高的問題。經(jīng)過實(shí)驗(yàn)驗(yàn)證，結(jié)果表明在圖像差異較大的情況下，特征線匹配數(shù)量、特征線匹配效率均優(yōu)于其他算法，從而進(jìn)一步驗(yàn)證了本文算法的有效性。