基于GMS和GS_LMEDS的圖像匹配算法

紀棟梁，張國偉，云偉俊，疏雅麗，王博

（1.上海電力大學自動化工程學院，上海200082；2.上海市閔行區高新技術產業化促進中心，上海201100）

針對GMS算法在特征點檢測較少時存在誤匹配的問題，結合高斯濾波和LMEDS，提出一種基于GMS和GS_LMEDS的特征匹配算法。該法首先對圖像預處理，進行高斯濾波，再使用ORB算法提取特征點和特征描述子，使用Brute-Hamming進行粗匹配，最后使用GMS做初次精匹配以及LMEDS做二次精匹配。實驗成果表明：相比于其他二次精匹配算法，該算法能有效去除錯誤的匹配點，準確匹配率普遍更高。

圖像匹配；GMS；誤匹配；準確匹配率

0 引言

圖像匹配主要是檢測兩幅或多幅圖像的相似性或一致性，在目標識別、三維重建等方面都起著重要作用。常用方法主要分為基于灰度信息[1]和基于特征[2]，目前大多算法都采用基于特征的方法，一般完整的基于特征匹配的方法主要包括特征提取、特征匹配和剔除誤匹配三個過程。匹配效果主要在于特征提取準確度以及速度等性能，例如待匹配圖像在旋轉、縮放、光照等方面的差異都會影響匹配效果[3-6]。

目前，圖像匹配方法有多種，其中常用的有SIFT[7]、SURF[8]和ORB[9]等。SIFT（Scale Invariant Feature Transform）在圖像尺度變換、旋轉變換及亮度變化方面有高穩定性，且對噪聲污染、視角和仿射變換有較強的魯棒性，劣勢主要在于運算成本高。SURF（Speed Up Robust Feature）是在SIFT上改進而來，在特征點和特征描述向量方面進行完善，運算成本得到大幅降低，并且具有很強的魯棒性。ORB（Oriented FAST and Rotated BRIEF）算法結合FAST[10]和BRIEF[11]算法，具有尺度和旋轉不變性，匹配的質量高，最大優點是速度快。但ORB特征匹配時精度較低，需進行進一步精匹配。GMS[12]（Grid-based Motion Statistics，GMS）算法由Bian等提出，該算法基于網格運動統計，將運動平滑度作為統計量，具有計算快、魯棒性強的特點，但也依舊存在誤匹配點。最小中值法[13]（Least Median of Squares，LMEDS）可以看成是最小二乘法的改進，計算機視覺的輸入數據是圖像，一般都包含噪聲，此時最小二乘法往往無法正確擬合數據，而LMEDS可以更好實現擬合，排除outlier數據，但該算法對高斯噪聲敏感。

針對上述分析，本文提出一種基于GMS和GS_LMEDS的圖像匹配算法，目的在于進一步提高準確匹配率。首先對圖像高斯濾波，再利用ORB提取特征點和描述子，然后通過Brute-Hamming進行粗匹配，最后使用GMS初次精匹配，最小中值法做二次精匹配。實驗成果表明，相比于其他二次匹配算法，本文算法具有更高的準確匹配率。

1 ORB算法

1.1 特征檢測與提取

特征點即為圖像中比較顯著的點，例如邊界點、亮區域暗點、暗區域亮點，等等。ORB使用FAST來獲得特征點，該法步驟如下：首先選取一個像素點P，設定一個合適閾值t，當兩點之間的灰度值差的絕對值大于t時，認為這兩點不同。然后在P點周圍選擇一個半徑r的圓，圓上所有的像素點便是評價P點是否為特征點的依據。圖1中r=3，因此需要考慮P點周圍的16個像素。如果圓周上有連續8個點滿足灰度值差絕對值大于t，則將P設為特征點。為了減少計算成本，FAST算法中僅將P與圓中的4個等距像素相比，例如選取1、5、9、13位置上的灰度值，如果P為特征點，那這四個位置上必有3個或4個滿足條件。

圖1 特征點檢測

為了獲得旋轉不變性，ORB用矩法確定FAST特征點方向。由矩計算出特征點周圍r半徑區域質心，特征點坐標到質心形成一個向量作其方向。矩定義如下：式中I(x,y)為圖像灰度表達式。該矩的質心為：

假設特征點坐標為原點，則向量角度即為其方向。計算公式如下：

FAST計算速度快，但其提取的特征點無尺度不變性，若圖像縮放則無法匹配相應特征點。為改進這一點，需使用圖片的尺度金字塔，單圖像的多尺度表示法由原始圖像的各分辨率版本組成，在各尺度計算FAST特征點。具體做法為設置比例因子scaleFactor（一般取1.2）和金字塔的層數nlevels（一般取8），按照scaleFactor值將原圖縮小成nlevels幅圖像，縮放后圖像為：

nlevels幅不同比例圖像的特征點即為這幅圖像的oFAST特征點。

1.2 特征描述子

rBRIEF由BRIEF加旋轉因子改進而來，具體步驟如下：在特征點P的鄰域內，選n對點pi、qi（i=1,2,…,n），然后比較每對的灰度值，如果I(pi)>I(qi)，則生成二進制串中的1，否則為0。所有點對比較所得結果合在一起，得到長度為n（一般取256）的二進制串。

BRIEF描述子在選取點對時是以當前特征點為原點，以水平方向為x軸，以垂直方向為y軸建立坐標系。當圖片發生旋轉時，坐標系不變，若還使用同樣的取點模式得到的描述子就不一樣。在計算描述子時，rBRIEF將特征點設置為原點，特征點和形心連線做為x軸建立坐標系，這樣遇到圖像旋轉，ORB選取點對的坐標系是固定的，即滿足旋轉一致性。

1.3 特征匹配

ORB具有一個二進制串向量形式的特征描述子，使用漢明距離計算各特征描述子之間不同位值的數量，將其中距離最小的特征點作為匹配點。

2 GMS算法

GMS是一種基于統計的匹配算法，其核心內容如下：由于運動具有的平滑性，使得匹配出現一對多的情況，即匹配到的特征點周圍也存在多個符合條件的匹配點，統計這些都符合條件的匹配點數，依此為依據來判斷該匹配正確與否。

假設圖像PL中有m個特征點集合{α1,α,…,αm}，圖像PR中有n個特征點集合{β1,β2,…,βn}。PL和PR所有的特征匹配集合{γ1,γ2,…,γk}，其中γi=(αi,βi)表示一對特征點匹配對。當匹配正確時，則有：

其中：1表示原來正確匹配的特征點。因為匹配具有足夠小的面積以及相對獨立分布的點對，可將其二項分布表示為：

其中：n表示匹配點對的數量，K表示與γi所在網格區域相鄰不相交的網格數目，pt表示準確匹配率，pf表示錯誤匹配率。根據式（6）可以得出Si標準差與均值：

根據Si的標準差和均值設定用于判斷匹配的鄰域特征點支持量閾值：

其中：mf一般極小，而Sf和α都較大，可以將mf省略不計。

對于一個網格區分匹配的鄰域特征點支持量閾值：

根據式（10），保留待配準網格中鄰域特征點支持量大于τi的粗匹配點對，剔除小于該值的點對，到此GMS便完成了對粗匹配對的篩選。

3 GS_LMEDS算法

由于GMS進行特征匹配后仍有錯誤匹配，所以本文使用LMEDS算法對GMS后所得的匹配特征點對再一次進行誤匹配剔除，該算法從樣本中隨機抽出N個子集，使用最小二乘法，計算各子集的估計參數和偏差，得到各子集中居中的那個偏差（即Med），最后選N個樣本子集中Med最小的所對應參數作為擬合參數。該法對高斯噪聲敏感，所以在特征匹配前先對圖像進行高斯濾波，提高算法的魯棒性，并且實驗中發現使用高斯濾波可以得到更高的匹配準確率。

4 實驗與分析

為了體現本文算法在匹配準確度與運行速度上的性能，將其與ORB+GMS+RANSAC、SIFT+GMS+RANSAC、SURF+GMS+RANSAC比較，測試平臺為個人筆記本：操作系統為Ubuntu 16.04，處理器為Intel Core i7-9750H CPU@2.6GHz，內存16GB。運行環境是系統終端，調用OpenCV 4.1.1，程序采用C++編寫，測試數據集為Oxford標準仿射變換圖集。

通過準確匹配率（Correct Matching Rate，CMR）和運行時間對算法評價，其中CMR定義為：

其中：內點數為算法最終保留的匹配對數，重復特征點數指的是兩幅圖像的單應矩陣計算所得，假設在圖像a中選擇m個特征點，圖像b中選取n個特征點，先將a中m個特征點集分別乘以兩圖像的單應矩陣H，生成新的點集m1。將新點集經過圖像b范圍約束篩選后，得到剩余點集m2；將圖像b的n個特征點分別乘以H-1，生成新點集n1。該點集經過圖像a范圍約束篩選后得到剩余點集n2；然后根據重復率評估公式：

其中：分子dist(m2,n1)為兩個點集的點之間的歐氏距離，如果其閾值小于設定值，則該點就是一個重復點。最后，兩圖像的重復特征點數由選取的特征點數乘以重復率所得。

圖2展現了本文算法與其他三種二次精匹配算法在Oxford圖集的4個子數據集的CMR對比。數據集包含了光照敏感對比（Leuven）、模糊度對比（Bike）、視角轉變和尺寸縮放（Bark）、圖像壓縮（Ubc）這四類配準測試圖像。由圖2的4幅圖像可以看出本文算法在視角轉變和尺寸縮放方面比其他算法更加出色，匹配準確率比ORB+GMS+RANSAC算法平均高8%。除了在模糊度對比方面與其相差不多，在光照和壓縮方面本文算法的匹配準確率比ORB+GMS+RANSAC要高3%左右。此外，由圖可以明顯看出選用ORB算法比SIFT和SURF可以獲得更多的匹配對及更高的準確匹配率。

圖3（b）～（e）展示了以Oxford圖集中Bark子圖集為例，應用本文與其他三種算法進行圖像配準的效果。Oxford圖集中配準最難的便是Bark子圖集，該圖集包含了極大角度的視角變換和尺寸縮放，表1展示了各算法在該圖集的結果。由表1可以看到本文算法在匹配準確率上明顯優于其他算法，CMR比其他三個算法分別高了8.2%、51.5%、41.7%，運行時間與ORB+GMS+RANSAC算法相差很小，實時性較高。

圖2 不同算法在Oxford圖集上的CMR實驗

表1 Bark圖集各算法結果對比

圖3 Bark數據集原圖及各算法配準效果圖

圖2 中是根據選取特征點數量變化所得的CMR數據，可以從一定角度說明本文算法在該方面比其他三種算法更為出色。為了更嚴謹的體現本文算法的優勢，對Oxford圖集的單個子圖集的所有圖像進行實驗分析，以模糊度對比方面為例，表2展示了選取同樣數量的特征點，本文算法和ORB+GMS+RANSAC算法在CMR方面的差距，平均下來本文算法的CMR比ORB+GMS+RANSAC算法要高3.58%。

表2 Leuven圖集測試結果對比

綜上所述，本文算法在準確匹配率方面優于其他三種算法，且具有較高的實時性。

5 結語

本文針對GMS存在誤匹配的問題，提出了基于GMS+GS_LMEDS的二次精匹配算法。該法利用高斯濾波預處理圖像，再利用ORB特征提取，然后根據漢明距離進行粗匹配，最后使用GMS和LMEDS算法分別進行第一次和第二次精匹配。實驗結果表明：相對于其他二次精匹配的算法，本文算法具有更高的準確匹配率，同時也具有較高的實時性。但本文算法在視角轉變和尺寸變換這兩方面的準確匹配率不高，如何使得在這些環境下獲得更高匹配率是下一步要研究的方向。