基于改進網格運動統(tǒng)計特征的圖像匹配算法

朱成德 李志偉 王凱 高燕 郭亨長

摘 要：為了解決尺度不變特征變換（SIFT）算法在圖像匹配中匹配正確率低、耗時長等問題，提出一種基于改進網格運動統(tǒng)計特征RANSAC-GMS的圖像匹配算法。首先，利用快速旋轉不變性特征（ORB）算法對圖像進行預匹配，對預匹配的特征點采用網格運動統(tǒng)計（GMS）來支持估計量以實現(xiàn)正確匹配點與錯誤匹配點的區(qū)分;然后，采用改進的隨機抽樣一致性（RANSAC）算法通過匹配點間的距離相似性對特征點進行篩選，并采用評價函數(shù)對篩選后的新數(shù)據集進行重新整理，進而實現(xiàn)對誤匹配點的剔除。采用Oxford標準圖庫和現(xiàn)實中拍攝的圖像對圖像匹配算法進行測試對比，實驗結果表明，所提算法在圖像匹配中的平均匹配正確率達到91%以上;與GMS、SIFT、ORB等算法相比，該改進算法的近景匹配正確率和遠景匹配正確率分別最少提高了16.15個百分點和3.56個百分點，說明它能有效剔除誤匹配點，進一步提高圖像匹配精度。

關鍵詞：圖像匹配;特征點匹配;距離相似性;誤匹配;網格運動統(tǒng)計

中圖分類號：?TP391.41

文獻標志碼：A

Image matching algorithm based on improved RANSAC-GMS

ZHU Chengde1，2， LI Zhiwei1*， WANG Kai1， GAO Yan1， GUO Hengchang2

1.School of Electronic and Electrical Engineering， Shanghai University of Engineering Science， Shanghai 201620， China ;

2.Shanghai M&G Stationery Incorporation， Shanghai 201406， China

Abstract：?In order to solve the problem that Scale Invariant Feature Transform （SIFT） algorithm has low matching accuracy and long time consuming in image matching， an improved image matching algorithm based on grid motion statistical feature， namely RANSAC-GMS， was proposed. Firstly， the image was pre-matched by Oriented FAST and Rotated BRIEF （ORB） algorithm and Grid-based Motion Statistics （GMS） was used to support the estimator to distinguish the correct matching points from the wrong matching points. Then， an improved RANdom SAmple Consensus （RANSAC） algorithm was used to filter the feature points according to the distance similarity between the matching points， and an evaluation function was used to reorganize the filtered new datasets to eliminate the mismatching points. The experiments were carried out on Oxford standard image library and images taken in reality. Experimental results show that the average matching accuracy of the proposed algorithm in image matching is over 91%. Compared with algorithms such as GMS， SIFT and ORB， the near-scene matching accuracy and the far-scene matching accuracy of the proposed algorithm are improved by 16.15 percentage points and 3.56 percentage points respectively. The proposed algorithm can effectively eliminate mismatching points and achieve further improvement of image matching accuracy.

Key words：?image? matching; feature point matching; distance similarity; wrong matching; Grid-based Motion Statistics （GMS）

0 引言

圖像匹配作為對兩幅或多幅圖像相似性或一致性檢測的分析方法，在人臉識別[1]、目標跟蹤[2]、視覺導航[3]、圖像拼接及檢索[4]等領域具有較為廣泛的應用。常用的圖像匹配方法主要分為基于灰度信息的匹配方法[5-6]和基于特征的匹配方法[7-8]。基于特征的圖像匹配算法主要包括尺度不變特征變換（Scale-Invariant Feature Transform， SIFT）算法[9]、加速穩(wěn)健特征（Speeded Up Robust Features， SURF）算法[10]、快速特 征點提取和描述ORB（Oriented FAST （Features from Accelerated Segment Test） and Rotated BRIEF （Binary Robust Independent Elementary Features））[11]等算法。ORB算法將FAST角點檢測和BRIEF特征描述相結合，保證了尺度和旋轉的不變性，具有匹配質量高、匹配速度快等優(yōu)點;但在實際運用中，該算法仍然存在圖像特征點匹配精度較低等問題。隨著研究的不斷推進，ORB算法被不斷完善，在構建圖像之間的映射關系時，經常與隨機抽樣一致性（RANdom SAmple Consensus，RANSAC）算法[12-14]相結合。RANSAC算法可有效剔除誤匹配，但當樣本中數(shù)據較多且局內點所占比例較低時，RANSAC算法計算最優(yōu)模型參數(shù)時間將呈指數(shù)增長，且經過剔除誤匹配后依然會有明顯的匹配錯誤存在。鑒于此，陳樹等[15]將提取的彩色圖像顏色不變量信息與SURF-ORB算法相結合，通過優(yōu)化RANSAC算法完成圖像的匹配，但該算法針對不同光照強度和光照角度情況下，圖像匹配效果有所提升;

秦曉飛等[16]提出通過8點改進法減少RANSAC迭代次數(shù)，采用極線約束來剔除誤匹配，但采用極線約束可能存在沒有可行解的情況。

Bian等[17]提出了一種基于網格運動統(tǒng)計（Grid-based Motion Statistics，GMS）特征的匹配算法，具有計算速度快、存儲量高等優(yōu)點，但也存在著大量的錯誤匹配點。

基于上述分析，本文提出了一種基于改進的網格運動統(tǒng)計特征RANSAC-GMS的圖像匹配算法，著重于進一步提高圖像匹配正確率。本文首先介紹了GMS算法和RANSAC算法，在此基礎上提出改進的RANSAC算法，根據匹配點間的距離相似對匹配點進行篩選，進一步利用評價函數(shù)對數(shù)據進行整理，以此增大局內點所占比例、減少迭代次數(shù)。實驗結果表明，本文所提算法可以有效剔除誤匹配點，實現(xiàn)圖像匹配正確率的進一步提高，有利于工程推廣應用。

1 GMS算法

GMS算法[18-19]是一種根據網格劃分特征點來作為鄰域支持估計量，將高數(shù)量匹配點轉換成高質量匹配的快速、高魯棒性的圖像匹配算法。GMS算法利用ORB算法對特征點進行提取和描述，采用基于網格運動統(tǒng)計鄰域支持估計量以區(qū)分正確匹配點和錯誤匹配點。圖1為正確匹配與錯誤匹配的特征分布圖，左側為匹配圖像Ia、右側為待匹配圖像Ib。兩幅圖像分別有M、N個特征點，其對應的特征點集合為{M，N}。a、b區(qū)域的匹配點集合為x={x1，x2，…，xn}，其中xi={Mi， Ni}表示一對特征點匹配對。正確匹配點附近存在若干對符合匹配關系的特征，而錯誤匹配的周圍符合匹配關系的特征數(shù)量較少甚至沒有，根據此特性，在a區(qū)域有一特征點Mi匹配到b區(qū)域中的Ni中，匹配對xi匹配正確，而匹配對xj匹配錯誤。對圖1中的a區(qū)域，用si表示xi鄰域支持估計量，則有：

si= | xi | -1

（1）

其中：-1表示去除a區(qū)域的原始特征點Mi。圖1中si=2。

匹配過程中，為了計算區(qū)域a中特征點到區(qū)域b中匹配正確的概率，用圖2表示特征點匹配過程的事件空間，其中圖（a）為區(qū)域a和區(qū)域b匹配正確事件，圖（b）為區(qū)域a和區(qū)域b匹配錯誤事件。區(qū)域a中的一個特征點用fa表示，事件fba表示fa匹配到區(qū)域b，反之匹配到區(qū)域b之外的事件記為fba 。事件fta表示fa匹配到區(qū)域b中特征點匹配正確，反之匹配錯誤記為事件ffa。事件Tab、Fab分別表示區(qū)域a和區(qū)域b匹配正確和匹配錯誤。其中，事件ffa發(fā)生時事件fba發(fā)生的概率為：

p（fba | ffa）=βn/N;? β∈（0，1）

（2）

其中：n是區(qū)域b中特征點個數(shù);N是待匹配圖像Ib中特征點總個數(shù);β是權重值。

由特征點fa匹配事件空間的分布，設pt、 pf分別表示在區(qū)域a中一個特征點匹配到區(qū)域b中正確的概率和錯誤的概率，令事件fta的概率為p（fta）=t，則pt、pf分別為：

pt= p（fba | Tab）=

p（fba | Tab）+p（fba， fba | Tab）=

p（fta）+p（ffa）p（fba | ffa）=t+（1-t）βn/N

（3）

pf=p（fba | Fab）=p（ffa， fba | Fab）=β（1-t）（n/N）

（4）

根據式（3）、式（4），si鄰域支持估計量和xi的二項分布之間的關系如下：

si～ B（n，pt），?? xi匹配正確B（n，pf）， xi匹配錯誤

（5）

為了快速區(qū)分正確匹配和錯誤匹配，把圖像劃分為G=g×g個網格，圖3展示了網格運動劃分，這里將鄰域支持估計量分配給一個單元網格，而不是計算每一個特征點對應的支持估計量。通過計算周圍相鄰網格的估計量，來加快區(qū)分匹配點。根據式（1）得到匹配網格區(qū)域間支持估計量si的表達式為：

si=∑ K k=1 ?| xakbk |

（6）

其中：K表示與匹配xi一起連續(xù)的不相交區(qū)域網格數(shù)目;xakbk∈x表示在xi預測周圍區(qū)域對應的匹配子集{ak，bk}。相鄰網格區(qū)域的鄰域支持估計量si的二項分布如下：

si～ B（Kn，pt），?? xakbk匹配正確B（Kn，pf）， xakbk匹配錯誤

（7）

根據以上得si的均值和標準差的分布如下：

mt=Knpt，st= Knt（1-pt） ，?? xakbk匹配正確mf=Knpf，sf= Knt（1-pf） ， xakbk匹配錯誤

（8）

由于運動網格的劃分，使得正確匹配與錯誤匹配的概率相差越來越大，即si的值逐漸增大。根據計算的均值和標準差可得到區(qū)域匹配對{ak，bk}的二值化表達式：

cell-pair{i， j}∈ F，? sij≤τ=mf+αsf

T， sij>τ=mf+αsf

（9）

其中：i表示圖像Ia中第i個網格區(qū)域;j表示圖像Ib中第j個網格區(qū)域;{i， j}表示兩個匹配的網格區(qū)域;α為權重值。在實踐中，τ可以近似為：

τ≈αsf≈α n

（10）

將鄰域估計量si大于τ的網格區(qū)域匹配對保留下來，則保留下的網格中存在大量滿足條件的特征點，為樣本提供了可靠的特征匹配對。

2 改進RANSAC算法

2.1 RANSAC算法

RANSAC算法[20]是根據一組觀測數(shù)據集，經過反復迭代的方式計算出數(shù)據集的參數(shù)模型，去除不符合模型的局外點及噪聲，進而得到可信的樣本數(shù)據的算法。RANSAC算法消除錯誤匹配的本質是尋找一個最優(yōu)參數(shù)單應矩陣（Homography Matrix），假設A圖像中坐標點為（xa，ya），B圖像中的點為（xb，yb），則向量表達關系為Bi= H Ai，進行 H 變換的一般式為：

xbyb1? =? h11 h12 h13h21 h22 h23h31 h32 h33 ?=? xaya1

（11）

對于單應矩陣 H ，通常令h33=1進行歸一化處理。此時單應矩陣 H 含有8個未知參數(shù)，需要4對匹配點來計算單應矩陣模型參數(shù)。雖然RANSAC算法很大程度上能夠提取正確的匹配點，但大量的實驗表明，直接使用RANSAC算法剔除誤匹配點的運行效率較低。RANSAC算法的迭代次數(shù)直接體現(xiàn)了RANSAC的運行效率，而模型最小迭代次數(shù)k須滿足：

1-（1-εq）k=p

（12）

其中：ε表示每次選取一個局內點在樣本中所占的概率;q表示計算模型參數(shù)所需的最小數(shù)據點數(shù);p表示為被測量參數(shù)測量值可信程度的物理量。由式（12）可以求出為：

k=lg（1-p）/lg（1-εq）

（13）

由式（13）可知，在置信度p∈[0.95，0.99]情況下，ε減小，則k增大;反之，ε增大，則k減小。因此，為了提高計算最優(yōu)內點集的效率，縮短算法運行時間，可以通過提高局內點在數(shù)據集中所占比例來減少迭代次數(shù)。

2.2 改進的RANSAC算法

盡管RANSAC算法具有極大的容錯性和較好的魯棒性，然而，當提取的數(shù)據集含有較多錯誤的匹配點時，算法的運行時間將呈指數(shù)增加，加之初始模型參數(shù)估計的數(shù)據源具有一定的隨機性，因此，在剔除誤匹配點方面仍然有進一步改進的空間。本文通過計算匹配點對的距離，根據距離相似性特點進行篩選，實現(xiàn)部分局外點的剔除，剩下的匹配點組成新的數(shù)據集，此時局內點所占的比例較高，可以計算出最優(yōu)單應矩陣參數(shù)模型;同時，也減少了計算最優(yōu)模型參數(shù)的迭代次數(shù)，提高了算法剔除誤匹配點效率，減少了運行時間。

為了進一步說明本文方法，采用圖4所示的匹配點距離相似篩選示意圖來作詳細說明。設（Ai，Bi）和（Aj，Bj）是參考圖像A和待匹配圖像B最鄰近匹配對，那么，Ai和Bi的距離l（Ai，Bi）應相似于Aj和Bj的距離l（Aj，Bj）;再由距離一致性原理，該距離應滿足l∈[Lmin，λ·Lmax]，其中Lmax為匹配距離的最大值，Lmin為匹配距離的最小值，λ∈[0，1]為比例因子。

要獲取更多特征點，可以將λ設定靠近1，該λ可以通過實驗確定，一般λ取0.6～0.8較為合適，本文λ取值0.7。利用參考圖像A和待匹配圖像B中匹配對（Ai，Bi）與最鄰近匹配對（Aj，Bj）距離關系相似性來評價距離兩點對應關系，提出如下評價函數(shù)：

F（i）=∑ c j=1? R（i， j） 1+Y（i， j）

（14）

R（i， j）=exp - ?| l（Ai，Bi）-l（Aj，Bj） | ?Y（i， j）

（15）

Y（i， j）=[l（Ai，Bi）+l（Aj，Bj）]/2

（16）

其中：c為內點個數(shù);R（i， j）表示（Ai，Bi）與各自對應特征點距離相對差異;Y（i， j）表示（Ai，Bi）與各自相對應特征點的平均距離。根據式（14），若想要得到穩(wěn)定的特征點，計算該距離與最鄰近距離的F（i）應盡可能地小。

改進RANSAC算法步驟如下：

1）求出匹配圖像A和待匹配圖像B中特征點匹配距離l和最鄰近點距離l′，該距離應滿足l∈[Lmin，λ·Lmax]。

2）計算評價函數(shù)F（i）的所有值并求取平均值，平均值記為F 。

3）對選取的匹配距離l進行F（i）值條件判斷，若F（i）小于F ，將匹配點保留下來組成新的樣本集C。

4）從C中隨機抽取4個匹配對作為內點集Ci，用這4個樣本數(shù)據擬合出一個模型 H i。

5）利用當前計算的模型去驗證樣本集C中剩余的內點集，如果某個點對適合當前模型 H i，且誤差小于閾值μ，則認為該點為局內點，將其加入內點集Ci。

6）如果內點集Ci中元素個數(shù)大于閾值θ，則更新內點集，重新計算當前模型;否則，轉到4）。

7）重復以上過程，如果迭代次數(shù)大于k，則退出。

2.3 本文算法設計

在本文中將匹配圖像和待匹配圖像分別劃成G=20×20個互不重疊的網格區(qū)域[17]，采取K=9鄰域網格進行估計，閾值τ是基于α的sij均值和方差之和，取α=6，在進行匹配點距離一致性篩選時，取λ=0.7?？傮w算法流程如下：

1）對參考圖像和待匹配圖像進行網格劃分，并使用ORB算法對特征點進行提取，分別獲取粗匹配特征點集。

2）使用基于網格運動統(tǒng)計鄰域支持估計量進行正確匹配點和錯誤匹配點的區(qū)分，組成可信度較高的匹配點集。

3）采用改進的RANSAC算法進行誤匹配點的剔除，完成圖像匹配。

具體流程如圖5所示。

3 實驗結果與分析

本文測試算法實驗條件為，筆記本電腦：操作系統(tǒng)為Windows 10（64位），Intel Core i5-4210U CPU @ 2.40GHz，4GB內存，運行環(huán)境為Visual Studio 2015和opencv3.4.0，程序采用C+ +編寫。為了驗證改進的RANSAC-GMS算法在圖像模糊、旋轉縮放、光照變化等圖像變換下具有良好的匹配效果，選取4個近期具有代表性的算法（GMS、ORB、SIFT、文獻[21]算法）與本文算法進行測試對比。對比實驗采用Oxford標準圖集[21]，圖6（a）～（g）分別有圖像模糊（image blur）、視點變換（viewpoint change）、縮放/尺度（zoom/scale）、光照變化（illumination change）和JPEG壓縮（JPEG compression）等7組圖像，每組包括6幅不同變換程度的相同場景圖像。

[4]?侯一民，隋文秀，孫曉雪. SIFT特征降維方法及其在圖像檢索中的應用 [J].中國激光， 2015，42（s1）：s108002. （HOU Y M， SUI W X， SUN X X. SIFT feature dimension reduction method and its application in image retrieval [J]. Chinese Journal of Lasers， 2015， 42（s1）：108002.）

[5]?王凱，李志偉，朱成德，等.基于二次引導濾波的局部立體匹配算法[J]. 激光與光電子學進展， 2019，56（8）：081004. （WANG K， LI Z W， ZHU C D， et al. Local stereo matching algorithm based on twice guided filtering [J]. Laser & Optoelectronics Progress， 2019， 56（8）： 081004.）

[6]?吳強，侯樹艷，李旭雯.融合圖像灰度信息與邊緣特征的快速匹配算法[J]. 信號處理， 2013，29（2）：268-273. （WU Q， HOU S Y， LI X W. Fast image matching algorithm based on gray and edge features [J]. Journal of Signal Processing， 2013， 29（2）： 268-273.）

[7]?賈雯曉，張貴倉，汪亮亮，等.基于SIFT和改進的RANSAC圖像配準算法[J].計算機工程與應用，2018，54（2）：203-207. （JIA W X， ZHANG G C， WANG L L， et al. Image registration algorithm based on SIFT and improved RANSAC [J]. Computer Engineering and Applications， 2018， 54（2）： 203-207.）

[8]?陳虹，肖越，肖成龍，等.基于SIFT算子融合最大相異系數(shù)的自適應圖像匹配算法[J].計算機應用，2018，38（5）：1410-1414. （CHEN H， XIAO Y， XIAO C L， et al. Adaptive image matching algorithm based on SIFT operator fused with maximum dissimilarity coefficient [J]. Journal of Computer Applications， 2018， 38（5）： 1410-1414.）

[9]?LOWE D G. Distinctive image features from scale-invariant keypoints [J]. International Journal of Computer Vision， 2004， 60（2）： 91-110.

[10]?BAY H， ESS A， TUYTELAARS T， et al. Speeded-up robust features [J]. Computer Vision & Image Understanding， 2008， 110（3）： 346-359.

[11]?BRADSKI G， RUBLEE E， KONOLIGE K， RABAUD V， et al. ORB： an efficient alternative to SIFT or SURF [C] // Proceedings of the 13th IEEE International Conference on Computer Vision. Washington， DC： IEEE Computer Society， 2011： 2564-2571.

[12]?TRAN Q， CHIN T， CARNEIRO G， et al. In defence of RANSAC for outlier rejection in deformable registration [C]// Proceedings of the 2012 European Conference on Computer Vision， LNCS 7575. Berlin： Springer， 2012： 274-287.

[13]?馮文斌，劉寶華.改進的SIFT算法圖像匹配研究[J].計算機工程與應用，2018，54（3）：200-205. （FENG W B， LIU B H. Research on image matching based on improved SIFT algorithm [J]. Computer Engineering and Applications， 2018， 54（3）： 200-205.）

[14]?孫雪強，黃旻，張桂峰，等.改進RANSAC算法在多光譜圖像匹配中的應用 [J].半導體光電，2018，39（4）：563-568. （SUN X Q， HUANG M， ZHANG G F， et al. Application of improved RANSAC algorithm to multi-spectral image matching [J]. Semiconductor Optoelectronics， 2018， 39（4）： 563-568.）

[15]?陳樹，楊天，孫順遠.融合彩色不變量和SURB檢測的特征點匹配算法[J]. 激光與光電子學進展，2018，55（5）：138-145. （CHEN S， YANG T， SUN S Y. Feature point matching algorithm for fusion of color invariants and SURB detection [J]. Laser & Optoelectronics Progress， 2018， 55（5）： 138-145.）

[16]?秦曉飛，皮軍強，李峰.基于極線約束的ORB特征匹配算法[J].計算機應用研究，2018，35（8）：2865-2868. （QIN X F，PI J Q， LI F.ORB feature matching based on epipolar constraint [J]. Application Research of Computers， 2018， 35（8）： 2865-2868.）

[17]?BIAN J， LIN W， MATSUSHITA Y， et al. GMS： Grid-based motion statistics for fast， ultra-robust feature correspondence [C]// Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition. Washington， DC：IEEE Computer Society， 2017： 2828-2837.

[18]?陳方杰，韓軍，王祖武，等.基于改進GMS和加權投影變換的圖像配準算法[J].激光與光電子學進展，2018，55（11）：174-180. （CHEN F J， HAN J， WANG Z W， et al. Image registration algorithm based on improved GMS and weighted projection transformation [J]. Laser & Optoelectronics Progress， 2018， 55（11）：174-180.）

[19]?YAN K， HAN M. Aerial image stitching algorithm based on improved GMS [C]// Proceedings of the 2018 Eighth International Conference on Information Science and Technology. Washington， DC： IEEE Computer Society， 2018： 351-357.

[20]?趙明富，陳海軍，宋濤，等.改進RANSAC-SIFT算法在圖像匹配中的研究[J].激光雜志，2018，39（1）：114-118. （ZHAO M F， CHEN H J， SONG T， et al. Research on image matching based on improved RANSAC-SIFT algorithm [J]. Laesr Journal， 2018， 39（1）： 114-118.）

[21]?李倩，江澤濤.二值化的SIFT特征描述子及圖像拼接優(yōu)化[J].中國圖象圖形學報，2016，21（12）：1593-1601. （LI Q， JIANG Z T. Binary quantized SIFT feature descriptors for optimized image stitching [J]. Journal of Image and Graphics， 2016， 21（12）： 1593-1601.）

[22]?李為，李為相，張璠，等.基于運動平滑約束項的快速誤匹配剔除算法[J].計算機應用，2018，38（9）：2678-2682. （LI W， LI W X， ZHANG F， et al. Rapid mismatching elimination algorithm based on motion smoothing constraints [J]. Journal of Computer Applications， 2018， 38（9）： 2678-2682.）