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

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

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

0 引言

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

因此，針對結構復雜、紋理重復嚴重的場景，受采集環境、采集設備、采集對象等因素影響，提取的特征線具有斷線情況嚴重、局部描述相似的特點，若采用上述特征線匹配方法，特征線匹配結果存在特征線匹配數量少、特征線匹配誤匹配率高等問題，進而影響到后續結果。

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

1 算法原理

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

圖1 特征線匹配流程

2 具體方法

2.1 相關定義

給定兩幅待匹配圖像{IA，IB}，IA為輸入原始圖像，IB為待匹配圖像；首先利用LSD 對圖像IA進行特征線提取后生成特征線集合LA={lA1，lA2，lA3，…，lAm}，采用LSD 對圖像IB進行特征線提取后生成特征線集合LB={lB1，lB2，lB3，…，lBn}。利用SIFT對圖像IA進行特征點提取后生成特征點集合PA={pA1，pA2，pA3，…，pAw}，采用SIFT 對圖像IB進行特征點提取后生成特征點集合PB={pB1，pB2，pB3，…，pBv}。已有方法對兩幅圖像進行特征檢測后的結果為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提取的特征線數量；w為圖像IA提取的特征點數量；m為圖像IB提取的特征線數量；v為圖像IB提取的特征點數量；X為圖像中的檢測到特征點p的幾何位置即為（x，y）；g為圖像中檢測到特征點的灰度信息。結合上述特征點和特征線信息，相關定義如下。

（1）定義1。目標特征線的矩形支持區域RAi：設給定圖像IA中任意特征線lAi，采用下式計算特征線lAi的矩形支持區域RAi：

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

（2）定義2。矩形支持區域RAi的局部特征點集合RPAi：設給定圖像IA中任意特征線lAi，采用下式計算矩形支持區域RAi的局部特征點集合RPAi：

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

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

2.2 特征線匹配過程

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

2.2.1 計算待匹配特征線的支持區域

輸入圖像IA、IB，結合定義（1）～（3）計算：圖像IA任一特征線li的特征線矩形支持區域Ri、矩形支持區域Ri的局部特征點集合，并組合為特征集合。依據特征線li的特征線矩形支持區域Ri范圍內且位于特征線兩側距離特征線最近的特征點為基礎，計算待匹配圖像IB中待匹配特征線的支持區域。

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

圖2 構建待匹配特征線的支持區域

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

2.2.2 支持區域內候選匹配特征線的確定

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

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

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

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

圖3 垂直距離約束

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

圖4 水平距離約束

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

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

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

灰度值矩陣的均值為：

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

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

3 實驗分析

為了驗證本文提出的特征線匹配算法的效率，采用不同場景下的圖像對進行驗證。實驗環境為：采用Windows 10 作為操作系統，采用英特爾Core i7-8750H @ 2.20GHz 為處理器，內存為8G；采用MatlabR2016a 為編程語言，Opencv3.4.5 計算機視覺庫，以標準公開數據集中包含旋轉變換、尺度變換、光照變化的3對圖像對為實驗數據，進行特征線匹配實驗。

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

表1 數據集信息

圖5 對比實驗結果

4 結束語

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