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

紀(jì)棟梁，張國(guó)偉，云偉俊，疏雅麗，王博

（1.上海電力大學(xué)自動(dòng)化工程學(xué)院，上海200082；2.上海市閔行區(qū)高新技術(shù)產(chǎn)業(yè)化促進(jìn)中心，上海201100）

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

圖像匹配；GMS；誤匹配；準(zhǔn)確匹配率

0 引言

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

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

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

1 ORB算法

1.1 特征檢測(cè)與提取

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

圖1 特征點(diǎn)檢測(cè)

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

假設(shè)特征點(diǎn)坐標(biāo)為原點(diǎn)，則向量角度即為其方向。計(jì)算公式如下：

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

nlevels幅不同比例圖像的特征點(diǎn)即為這幅圖像的oFAST特征點(diǎn)。

1.2 特征描述子

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

BRIEF描述子在選取點(diǎn)對(duì)時(shí)是以當(dāng)前特征點(diǎn)為原點(diǎn)，以水平方向?yàn)閤軸，以垂直方向?yàn)閥軸建立坐標(biāo)系。當(dāng)圖片發(fā)生旋轉(zhuǎn)時(shí)，坐標(biāo)系不變，若還使用同樣的取點(diǎn)模式得到的描述子就不一樣。在計(jì)算描述子時(shí)，rBRIEF將特征點(diǎn)設(shè)置為原點(diǎn)，特征點(diǎn)和形心連線做為x軸建立坐標(biāo)系，這樣遇到圖像旋轉(zhuǎn)，ORB選取點(diǎn)對(duì)的坐標(biāo)系是固定的，即滿足旋轉(zhuǎn)一致性。

1.3 特征匹配

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

2 GMS算法

GMS是一種基于統(tǒng)計(jì)的匹配算法，其核心內(nèi)容如下：由于運(yùn)動(dòng)具有的平滑性，使得匹配出現(xiàn)一對(duì)多的情況，即匹配到的特征點(diǎn)周圍也存在多個(gè)符合條件的匹配點(diǎn)，統(tǒng)計(jì)這些都符合條件的匹配點(diǎn)數(shù)，依此為依據(jù)來判斷該匹配正確與否。

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

其中：1表示原來正確匹配的特征點(diǎn)。因?yàn)槠ヅ渚哂凶銐蛐〉拿娣e以及相對(duì)獨(dú)立分布的點(diǎn)對(duì)，可將其二項(xiàng)分布表示為：

其中：n表示匹配點(diǎn)對(duì)的數(shù)量，K表示與γi所在網(wǎng)格區(qū)域相鄰不相交的網(wǎng)格數(shù)目，pt表示準(zhǔn)確匹配率，pf表示錯(cuò)誤匹配率。根據(jù)式（6）可以得出Si標(biāo)準(zhǔn)差與均值：

根據(jù)Si的標(biāo)準(zhǔn)差和均值設(shè)定用于判斷匹配的鄰域特征點(diǎn)支持量閾值：

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

對(duì)于一個(gè)網(wǎng)格區(qū)分匹配的鄰域特征點(diǎn)支持量閾值：

根據(jù)式（10），保留待配準(zhǔn)網(wǎng)格中鄰域特征點(diǎn)支持量大于τi的粗匹配點(diǎn)對(duì)，剔除小于該值的點(diǎn)對(duì)，到此GMS便完成了對(duì)粗匹配對(duì)的篩選。

3 GS_LMEDS算法

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

4 實(shí)驗(yàn)與分析

為了體現(xiàn)本文算法在匹配準(zhǔn)確度與運(yùn)行速度上的性能，將其與ORB+GMS+RANSAC、SIFT+GMS+RANSAC、SURF+GMS+RANSAC比較，測(cè)試平臺(tái)為個(gè)人筆記本：操作系統(tǒng)為Ubuntu 16.04，處理器為Intel Core i7-9750H CPU@2.6GHz，內(nèi)存16GB。運(yùn)行環(huán)境是系統(tǒng)終端，調(diào)用OpenCV 4.1.1，程序采用C++編寫，測(cè)試數(shù)據(jù)集為Oxford標(biāo)準(zhǔn)仿射變換圖集。

通過準(zhǔn)確匹配率（Correct Matching Rate，CMR）和運(yùn)行時(shí)間對(duì)算法評(píng)價(jià)，其中CMR定義為：

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

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

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

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

圖2 不同算法在Oxford圖集上的CMR實(shí)驗(yàn)

表1 Bark圖集各算法結(jié)果對(duì)比

圖3 Bark數(shù)據(jù)集原圖及各算法配準(zhǔn)效果圖

圖2 中是根據(jù)選取特征點(diǎn)數(shù)量變化所得的CMR數(shù)據(jù)，可以從一定角度說明本文算法在該方面比其他三種算法更為出色。為了更嚴(yán)謹(jǐn)?shù)捏w現(xiàn)本文算法的優(yōu)勢(shì)，對(duì)Oxford圖集的單個(gè)子圖集的所有圖像進(jìn)行實(shí)驗(yàn)分析，以模糊度對(duì)比方面為例，表2展示了選取同樣數(shù)量的特征點(diǎn)，本文算法和ORB+GMS+RANSAC算法在CMR方面的差距，平均下來本文算法的CMR比ORB+GMS+RANSAC算法要高3.58%。

表2 Leuven圖集測(cè)試結(jié)果對(duì)比

綜上所述，本文算法在準(zhǔn)確匹配率方面優(yōu)于其他三種算法，且具有較高的實(shí)時(shí)性。

5 結(jié)語(yǔ)

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