基于加權(quán)相似性度量的特征匹配方法

胡立華，左威健，聶瑤瑤

（太原科技大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，太原 030024）

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

0 引言

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

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

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

1 相關(guān)定義

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

定義1L(PA，PB)是PA與PB之間的HD，dPB(XAi)為任一特征點(diǎn)XAi中幾何位置與PB內(nèi)所有特征點(diǎn)幾何位置之間距離的最小值，‖ * ‖是一種距離范式如L2，h(PA，PB)是PA內(nèi)所有特征點(diǎn)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 加權(quán)相似性度量特征匹配

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

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

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

2.1 特征點(diǎn)的描述

2.2 度量函數(shù)

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

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

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

最后，基于D1、D2、D3和三個加權(quán)參數(shù)，圖像區(qū)域(Ai，Bi)內(nèi)特征點(diǎn)之間的度量函數(shù)D可定義為：

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

2.3 算法描述及分析

依據(jù)上述加權(quán)相似性度量，結(jié)合文獻(xiàn)［24］，基于FM_GMC的WSM特征匹配算法描述如下：

算法1 加權(quán)相似性度量方法。

輸入 圖像A和B；

步驟1 根據(jù)FM_GMC 算法的結(jié)果將圖像A和B分成多個對應(yīng)的聚類區(qū)域；

步驟2 采用Canny提取各聚類區(qū)域內(nèi)的邊緣特征點(diǎn)；

步驟3 采用SIFT描述子描述邊緣特征點(diǎn)；

步驟4 計算各對應(yīng)聚類區(qū)域邊緣特征點(diǎn)間的Hausdorff距離D1；

步驟5 計算各對應(yīng)聚類區(qū)域邊緣特征點(diǎn)描述符之間的歐氏距離D2；

步驟6 計算各對應(yīng)聚類區(qū)域內(nèi)像素之間的NCC記為D3；

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

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

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

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

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

2.4 算法復(fù)雜度分析

為方便計算，設(shè)圖像A和B提取的SIFT 特征點(diǎn)個數(shù)均為N，圖像A和B的網(wǎng)格數(shù)量為M。若采用傳統(tǒng)的RANSAC 算法進(jìn)行特征匹配，其時間復(fù)雜度為O(N2+N)。因?yàn)閃SM 的特征匹配均在對應(yīng)聚類區(qū)域內(nèi)進(jìn)行，所以時間復(fù)雜度主要取決于圖像劃分網(wǎng)格的數(shù)量M。表1給出了WSM算法各階段時間復(fù)雜度。

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

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

3 實(shí)驗(yàn)結(jié)果與分析

本章從精確性和魯棒性兩個方面對WSM 的性能進(jìn)行了評價，并將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）等匹配算法進(jìn)行比較。實(shí)驗(yàn)環(huán)境為：Windows 10 操作系統(tǒng)，2.3 GHz Intel Core i5 處理器，4 GB 內(nèi)存；以及開放源碼工具箱opencv3.2.0、matlabR2014a、python3.6.0。

3.1 參數(shù)分析

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

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

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

從表2可以得到以下結(jié)果：

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

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

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

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

依據(jù)表2可得出如下結(jié)論：當(dāng)θ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 精確率和魯棒性驗(yàn)證

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

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

從圖2與圖3中發(fā)現(xiàn)：

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

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

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

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

部分匹配結(jié)果如圖4 所示。從匹配結(jié)果中可以看出，WSM 在圖像發(fā)生尺度縮放、旋轉(zhuǎn)變化等情況下，特征匹配數(shù)量較多且匹配準(zhǔn)確率較高。

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

圖4 旋轉(zhuǎn)、尺度縮放匹配結(jié)果Fig.4 Experimental results of feature matching with rotation and scaling

3.3 WSM算法在三維重建中的應(yīng)用

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

圖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 結(jié)語

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