基于加權相似性度量的特征匹配方法

胡立華，左威健，聶瑤瑤

（太原科技大學計算機科學與技術學院，太原 030024）

（*通信作者電子郵箱sxtyhlh@126.com）

0 引言

特征匹配是建立來自同一物體的兩幅圖像間特征點的可靠對應關系，現已廣泛應用于汽車駕駛、目標跟蹤、即時定位與地圖構建（Simultaneous Localization And Mapping，SLAM）［1-2］、視覺導航、三維重建［3-4］等領域。但是由于采集圖像受環境、時間、攝像機角度差異、傳感器不同等問題的影響，易產生以下問題：1）采集的圖像存在大量噪聲；2）采集的圖像畸變情況嚴重。因此，如何精確、穩定地查找特征點之間的對應關系是計算機視覺中的一個傳統而關鍵的問題。在特征匹配過程中，圖像特征點之間的相似性度量標準是影響特征匹配結果的關鍵因素之一，因此，如何有效地定義特征點之間的相似性度量標準是提高特征匹配效率的關鍵問題。

目前，特征間的相似性度量標準的設計主要取決于應用場景的選擇。不同場景的相似性度量方法［5］主要包括三類：基于距離相似性的度量方法、基于圖像相關的相似性度量方法以及其他的度量方法。典型的基于距離相似性度量方法［6］有：Zhao等［7］提出了一種改進的Hausdorff距離算法，適用于像素值較少的灰度圖像，可有效處理噪聲圖像匹配；Wang 等［8］采用棋盤距離與城市距離的線性組合替換歐氏距離，在提高匹配精確率的同時還減少了算法的運行時間；Kang 等［9］采用部分Hausdorff 距離進行二值邊緣圖像匹配；劉坡等［10］為解決多尺度空間區域特征匹配的閾值問題，采用均方根誤差（Root Mean Square Error，RMSE）度量和相鄰元素的聚類算法匹配區域特征；Kumar 等［11］采用基于閔可夫斯基距離相似性度量的形狀匹配，有效地提高了識別準確率。然而，此類度量函數依賴于特征描述子效率，且計算時間復雜度較高。典型的基于圖像相關的相似性度量方法［12］有：Wei 等［13］提出了基于歸一化互相關的快速模板匹配算法，采用相關系數法比歸一化積相關法（Normalized Product correlation，NProd）抑制了噪聲；Mahmood 等［14］提出了一種基本/擴展模式部分相關消除的算法；Kolar等［15］利用相位相關方法極大地削減了度量函數對圖像灰度的依賴；Woo 等［16］采用互信息提高了度量函數的魯棒性。此類方法主要用于灰度特征的匹配，因此方法簡單易理解，但匹配精度不高。典型的基于紋理、顏色、直方圖統計、時間序列等特征的度量方法［17］有：Rubner 等［18］提出了基于兩種直方圖分布之間的地球移動距離用于基于內容的圖像檢索；Yoon 等［19］提出的獨特相似性度量方法解決了立體匹配中存在的模糊點問題；Wong等［20］通過使用圖像間的結構關系改善了特征匹配的效率；Zhou 等［21］采用互信息提高了匹配效率；Guo 等［22］提出了一種計算鄰域窗口圖像平均結構相似性指數算法；Lin 等［23］基于“相似物體具有相似鄰域”提出了一種相似性度量方法。

針對結構復雜、紋理重復嚴重的圖像，若采用目前單一的特征匹配度量方法，特征匹配結果可能存在以下問題：1）誤匹配率高且正確匹配數量少；2）匹配結果魯棒性較差。為了提高基于圖像的特征匹配的效率，本文將局部特征點描述子、特征點之間幾何空間聚類約束和特征點之間圖像灰度信息引入到特征匹配度量過程中，設計了一種基于加權相似性度量的特征匹配方法。該方法依據基于網格多密度聚類的特征匹配（Feature Matching based on Grid and Multi-Density Clustering，FM_GMC）算法［24］得到的對應聚類區域，首先在圖像間的聚類區域采用Hausdorff 距離（Hausdorff Distance，HD）度量聚類區域之間的空間上下文相似性；其次，采用Canny 從聚類區域中獲取邊緣特征點并用尺度不變特征變換（Scale Invariant Feature Transform，SIFT）描述子描述聚類區域的邊緣特征點，利用歐氏距離（Euclidean Distance，ED）度量聚類區域內的特征點外觀局部梯度信息之間的相似性；然后，采用歸一化互相關（Normalized Cross Correlation，NCC）方法度量特征點局部區域內灰度信息的相似性；最后，根據HD、ED 以及NCC 所帶來的影響大小不同，分別賦予它們不同的權值，設計一種加權相似性度量函數。最終正確匹配結果采用最近鄰距離比值（Nearest Neighbor Distance Ratio，NNDR）確定。

1 相關定義

給定一對圖像{A，B}，圖像A有p個特征點，圖像B有q個特征點，分別表示為PA={XAi(x，g)，i=1，2，…，p}，PB={XBi(x，g)，i=1，2，…，q}，其中x為特征點幾何位置坐標即(x，y)，g為灰度信息。SAi是任一特征點XAi的SIFT描述，記為SAi(fA1，fA2，…，fA128)?；谏鲜雒枋?，HD、ED 和NCC 分別可定義為：

定義1L(PA，PB)是PA與PB之間的HD，dPB(XAi)為任一特征點XAi中幾何位置與PB內所有特征點幾何位置之間距離的最小值，‖ * ‖是一種距離范式如L2，h(PA，PB)是PA內所有特征點dPB(XAi)的最大值，L(PA，PB)是PA到PB的距離或者PB到PA的距離的最大值，即PA與PB之間的HD。

定義2特征描述子之間的歐氏距離d(SAi，SBj)為：

定義3圖像A與B中像素灰度間的NCC可定義為：

其中：gA和gB分別為圖像A的中心像素灰度值和匹配圖像B的中心像素灰度值分別為圖像A的平均灰度值和匹配圖像B的平均灰度值。

2 加權相似性度量特征匹配

在基于圖像的特征匹配過程中，由于采集的圖像易受到光照、環境、尺度等因素影響，不同視角下的圖像匹配特征點之間存在著仿射、射影等變化，直接導致圖像匹配特征點之間的空間位置改變，尤其是針對結構復雜、重復紋理現象嚴重的圖像，特征點之間的空間位置改變會導致特征點周圍局部梯度信息產生變化，進而產生了較多噪聲點，直接影響了圖像之間的特征匹配效率。因此，在圖像特征匹配過程中，若僅考慮圖像特征點之間的局部梯度信息，則特征匹配結果將產生誤匹配率較高、匹配魯棒性較弱等問題。

為了提高特征匹配效率，本文針對特征匹配過程由單一的特征點局部梯度度量函數易產生特征匹配結果錯誤率高、匹配結果魯棒性較弱等問題，結合FM_GMC 算法［24］，在特征聚類塊的基礎上提取圖像邊緣信息，同時融入基于距離相似性度量方法與基于圖像相關的相似性度量方法，設計了一種加權相似性度量的特征匹配方法。該方法首先根據FM_GMC算法將圖像劃分成多個對應聚類區域，在此基礎上，利用Canny 算法和SIFT 算法得到幾何信息和特征點的描述信息。最后，采用加權相似性度量函數進行灰度特征、局部梯度特征以及空間幾何特征的度量。具體過程如圖1所示。

圖1 加權相似性度量特征匹配過程Fig.1 Flowchart of feature matching based on weighted similarity measurement

2.1 特征點的描述

2.2 度量函數

給定兩個對應聚類區域Ai和Bi分別包含p、q個邊緣特征點及相應的特征描述信息，根據式（1）～（3）可將D1定義為Ai和Bi對應聚類區域內特征點空間位置的HD：

D2為特征點描述子之間的ED，其中特征點通過Canny 提取，采用SIFT 進行特征描述。用fAimj和fBinj分別表示Ai和Bi中特征點的描述子，參照式（4），Ai中特征點與Bi中第q個特征點的描述子間的歐氏相似度量D2可通過式（7）進行計算。

D3為NCC 估計圖像中像素強度的相似度，以聚類區域Ai與聚類區域Bi為例，Ai(x，y)表示Ai中以(x，y)為左上角點與Bi模板一樣的子塊，且Bi子塊大小為m，通過相關系數式（8）可得到Ai與Bi間的相關系數矩陣ρ(x，y)，并判斷它們是否相關。

最后，基于D1、D2、D3和三個加權參數，圖像區域(Ai，Bi)內特征點之間的度量函數D可定義為：

設DN和DM分別為聚類區域Ai中任一特征點與Bi中所有特征點距離之間的最近鄰和次近鄰值，比值Rr由式（11）確定。通過設置閾值R可剔除誤匹配，如果Rr＜R，則保留該匹配。

2.3 算法描述及分析

依據上述加權相似性度量，結合文獻［24］，基于FM_GMC的WSM特征匹配算法描述如下：

算法1 加權相似性度量方法。

輸入 圖像A和B；

步驟1 根據FM_GMC 算法的結果將圖像A和B分成多個對應的聚類區域；

步驟2 采用Canny提取各聚類區域內的邊緣特征點；

步驟3 采用SIFT描述子描述邊緣特征點；

步驟4 計算各對應聚類區域邊緣特征點間的Hausdorff距離D1；

步驟5 計算各對應聚類區域邊緣特征點描述符之間的歐氏距離D2；

步驟6 計算各對應聚類區域內像素之間的NCC記為D3；

步驟7 將D1、D2和D3合并到D中，并分配不同的權重；

步驟8 在D各橫向量中查找最近鄰和次近鄰，分別標記為DN和DM；

步驟9 設置閾值R并且計算Rr=DN/DM；

步驟10 如果Rr ＜R，保留匹配，否則刪除匹配。

上述WSM 方法可有效地剔除由環境、光照、尺度等原因產生的噪聲點，具體原因為：依據FM_GMC 算法［24］得到的對應聚類區域，首先在圖像間的聚類區域采用Hausdorff 距離（D1）度量對應聚類區域之間的空間相似性，從而保持特征匹配區域之間的空間位置的一致性，有效地剔除由空間不一致造成的噪聲點；其次，采用Canny 從聚類區域中獲取邊緣特征點，并用SIFT 描述子描述聚類區域的邊緣特征點，利用歐氏距離（D2）度量聚類區域內的特征點局部梯度信息間的相似性，進而從圖像旋轉和尺度上保證對應邊緣特征點的局部梯度一致性，進一步剔除由旋轉和尺度變化形成的噪聲點；然后，為了減小光照對圖像的影響，采用了NCC 方法（D3）來度量特征點局部區域內灰度信息的相似性，有效地剔除由光照變化形成的噪聲點。

2.4 算法復雜度分析

為方便計算，設圖像A和B提取的SIFT 特征點個數均為N，圖像A和B的網格數量為M。若采用傳統的RANSAC 算法進行特征匹配，其時間復雜度為O(N2+N)。因為WSM 的特征匹配均在對應聚類區域內進行，所以時間復雜度主要取決于圖像劃分網格的數量M。表1給出了WSM算法各階段時間復雜度。

表1 WSM算法各階段時間復雜度Tab.1 Time complexity of the WSM algorithm in different stages

由于FM_GMC算法的網格數量M大于9，所以從表1中可以得出如下結論：相較于傳統的隨機抽樣一致（RANdom SAmple Consensus，RANSAC）匹配方法，WSM 特征匹配的時間復雜度O(2*N/M+3*(N/M)2)＜O(N2+N)。因此，算法WSM在時間上優于傳統的RANSAC算法。

3 實驗結果與分析

本章從精確性和魯棒性兩個方面對WSM 的性能進行了評價，并將WSM 與SIFT+RANSAC、SURF（Speeded-Up Robust Features）+RANSAC、FM_GMC、LIFT（Learned Invariant Feature Transform）和EECS442（http：//web.eecs.umich.edu/～fouhey/teaching/EECS442_W19/index.html）等匹配算法進行比較。實驗環境為：Windows 10 操作系統，2.3 GHz Intel Core i5 處理器，4 GB 內存；以及開放源碼工具箱opencv3.2.0、matlabR2014a、python3.6.0。

3.1 參數分析

算法WSM 涉及到的關鍵參數分別為：θ1、θ2、θ3和R，為比較參數的不同取值對WSM 效果的影響，本文進行了如下的實驗，其中參照傳統SIFT特征匹配算法中的取值情況，R取0.6。根據θ1、θ2、θ3的不同取值能夠發現特征匹配的精確率p（Precision）的變化浮動比較大。精確率p計算參考文獻［25］，可定義為匹配結果中正確匹配對占所有匹配對的比率：

表2給出了當θ1取值為0.15、0.2、0.3、0.4、0.5 時，θ1、θ2、θ3與特征匹配精確率p之間的數據。

表2 θ1、θ2、θ3與精確率p的關系Tab.2 Relationship between p and θ1，θ2，θ3

從表2可以得到以下結果：

1）WSM 算法特征匹配精度最高時的取值為：θ1=0.4，θ2=0.35，θ3=0.25。

2）在特征匹配過程中，特征聚類區域之間的相似度可通過兩個區域之間的空間位置相似度D1定義。從表2中的結果可以看出，D1對應權值θ1的改變對特征匹配結果的影響最大，這是由于WSM 的匹配效果好壞主要取決于初始匹配結果及初始聚類區域的選擇，從同一對象提取出的特征點的位置信息往往保持一致。因此，對于WSM 來說，對應特征區域的精度對特征匹配結果影響最大。如在參數θ3=0.15 的條件下，θ1變化范圍為0.2～0.5，匹配精度對應變化范圍為0.74～0.9。

3）局部幾何相似度D2主要描述了特征描述子相似度。從表2可以看出，D2對應權值θ2對匹配結果的影響次之，這是由于針對特征點而言，特征描述子的相似性能夠更詳盡地刻畫特征局部領域之間的相似關系。如在參數θ1=0.3 的條件下，θ2變化范圍為0.2～0.65，匹配精度對應變化范圍為0.78～0.92。

4）NCC 度量因子D3主要描述了特征點與周圍鄰域間的灰度變化情況，因此，可作為補充條件有效地剔除由于光照變化造成的誤匹配。從表2 中可以看出，D3對應的權值θ3對特征匹配精度影響最小。

依據表2可得出如下結論：當θ1的取值范圍為0.3～0.45，θ2的取值范圍0.25～0.35，θ3在0.2～0.25 時，特征匹配精度可保持在90%左右，因此本文建議θ1、θ2、θ3的取值分別為0.4、0.35、0.25。

3.2 精確率和魯棒性驗證

本節從精確率上分析了WSM 與其他算法（SIFT+RANSAC、SURF+RANSAC、LIFT、EECS442 以及FM_GMC）的比較結果。其中WSM 中各參數設置分別為：θ1=0.4，θ2=0.35，θ3=0.25，R=0.6，其他算法的參數設置均提供默認值。圖2 與圖3 分別展示了各匹配算法精確率與匹配數量間的關系：圖2 中的橫軸代表匹配算法所用的圖像數量，縱軸代表各算法在當前輸入圖像下的平均精確率；圖3 中的橫軸代表各算法20 幅圖像的平均正確匹配數量，縱軸代表采用的匹配算法。

圖2 各算法的平均精確率Fig.2 Average precisions of different algorithms

從圖2與圖3中發現：

1）相 較 于 SIFT+RANSAC、SURF+RANSAC、LIFT、EECS442和FM_GMC，WSM的精確率保持在92.08%左右。

2）相 較 于SIFT+RANSAC、SURF+RANSAC、LIFT 和EECS442，FM_GMC 將聚類引入到特征匹配中，保證了特征匹配的空間一致性，提高了特征匹配的精度，但是匹配的數量比WSM 少。這是由于WSM 是通過Canny 提取邊緣特征點，而FM_GMC 是通過SIFT 來提取特征點，導致其提取出的圖像特征點數量較少。

3）當光照差異較大時，SIFT+RANSAC 和SURF+RANSAC的匹配效果較差且匹配數量較少；當圖像發生旋轉變換或尺度縮放時，EECS442的匹配效果最差，但它考慮到圖像中所有的Harris角，所以在匹配的數量上做得很好。

4）LIFT 采用深度網絡架構并且使用最近鄰匹配策略，提高了匹配精度，但匹配數量不理想；而WSM 將空間位置、特征信息和灰度信息融合在一起，同時提高了匹配的精確率和匹配數量。

部分匹配結果如圖4 所示。從匹配結果中可以看出，WSM 在圖像發生尺度縮放、旋轉變化等情況下，特征匹配數量較多且匹配準確率較高。

圖3 各算法20幅圖像的平均正確匹配數量Fig.3 Average matching numbers of different algorithms

圖4 旋轉、尺度縮放匹配結果Fig.4 Experimental results of feature matching with rotation and scaling

3.3 WSM算法在三維重建中的應用

依據WSM 算法得出特征匹配點應用于古建筑圖像三維重建的流程為：首先，選擇兩幅晉祠圖像用于初始化后續所需的一系列場景結構以及相機的運動計算。由于三維重建的前提需要，這兩幅圖像間必須有充足的匹配點，本文算法WSM提供的古建筑圖像特征匹配數量平均值達到226，基本滿足其要求。其次，根據兩幅圖像的匹配關系，可通過三角測量進行場景重建，并向已重建好的結構中添加23 幅圖像。最后，由于兩幅圖像對應的初始相機的位姿已被確定，隨著新圖像的不斷加入和重建計算，重建結構也隨之不斷地更改，新的三維點更新生成。這一部分是通過中國科學院自動化研究所提供的軟件實現的。重建結果如圖5，其中重建點云個數為5 762 844；圖6 為Visual SFM 三維重建效果圖，其重建點云個數為4 108，特征匹配結果在三維重建效果上得到驗證。

圖5 WSM的晉祠三維重建效果圖Fig.5 3D reconstruction effect of Jinci temple by using WSM

圖6 Visual SFM晉祠三維重建效果圖Fig.6 3D reconstruction effect of Jinci temple using Visual SFM

4 結語

針對結構復雜、紋理重復的對象，為了提高圖像的特征匹配的效率和魯棒性，本文提出了一種基于加權相似性度量的特征匹配方法WSM。該方法首先根據FM_GMC 算法將圖像分成若干對應聚類區域；其次，采用Canny 方法提取對應聚類區域內的邊緣特征信息，并利用SIFT 進行幾何特征描述；然后，結合聚類區域的空間一致性信息、匹配特征間的局部描述信息和特征點周圍領域內灰度信息，采用加權的方法進行相似性度量；最后，采用晉祠古建筑驗證了WSM 算法的有效性。由于該算法不僅從全局上考慮了匹配特征點間的空間一致性，而且從旋轉、尺度、灰度方面考慮了匹配特征點間的局部結構特征，從而有效提高了特征匹配的效率。