基于網(wǎng)格加速與順序選取策略的圖像匹配算法

江一葦，顧幸生

（華東理工大學(xué)能源化工過程智能制造教育部重點(diǎn)實(shí)驗(yàn)室，上海 200237）

自動駕駛、無人機(jī)、餐廳和醫(yī)院的服務(wù)機(jī)器人等都需要對機(jī)器人本體進(jìn)行實(shí)時定位，從而可以使機(jī)器人提供精準(zhǔn)的服務(wù)。獲取機(jī)器人位置與姿態(tài)的方法有激光、輪速傳感器、慣性測量單元（Inertial MeasurementUnit，IMU）和視覺傳感器等，而視覺傳感器以其低廉的價格以及較高的性能被廣泛應(yīng)用于上述場景中[1-3]。

相較于其他的定位方式，視覺傳感器尤其是雙目相機(jī)最接近人類的實(shí)際視覺系統(tǒng)[4]。其定位的主要方法是利用相機(jī)對物體或者場景進(jìn)行拍攝，對前后幀圖像進(jìn)行特征點(diǎn)與描述子的提取，然后對上一時刻與當(dāng)前時刻兩張圖像的特征點(diǎn)進(jìn)行匹配，以此估算特征點(diǎn)的運(yùn)動，還原出相機(jī)本體在世界坐標(biāo)系下的運(yùn)動[5]。特征點(diǎn)匹配的精確程度極大地影響著相機(jī)運(yùn)動的精度，如何進(jìn)一步提升特征點(diǎn)的匹配精度是近幾年的一個研究熱點(diǎn)。主流的方法是針對特征點(diǎn)本身進(jìn)行相關(guān)優(yōu)化，例如：旋轉(zhuǎn)不變性特征[6]（Oriented FAST and Rotated BRIEF，ORB），在FAST（Features fromAcceleratedSegmentTest）角點(diǎn)上加入了旋轉(zhuǎn)不變性與尺度不變性；尺度不變特征變換（Scale-Invariant FeatureTransform，SIFT）[7]算法能對旋轉(zhuǎn)、尺度縮放、亮度變化等保持不變性，是一種非常穩(wěn)定的局部特征優(yōu)化算法；加速穩(wěn)健特征（Speed-Up Robust Feature，SURF）[8]算法對SIFT 算法進(jìn)行了改進(jìn)，提升了算法的執(zhí)行效率，為算法在實(shí)時計(jì)算機(jī)視覺系統(tǒng)中的應(yīng)用提供了可能。

除了對特征點(diǎn)選取進(jìn)行優(yōu)化外，還可以對特征點(diǎn)匹配算法進(jìn)行優(yōu)化，其中應(yīng)用最廣泛的就是隨機(jī)抽樣一致（RandomSampleConsensus，RANSAC）[9]算法。該算法是一種為了消除誤匹配的魯棒估計(jì)方法，對噪聲具有較強(qiáng)的魯棒性和穩(wěn)定性。在RANSAC算法中，消除誤匹配和保持正確匹配取決于閾值。如果閾值偏低，除了消除誤匹配之外，還會刪除大量的正確匹配；如果閾值偏高，除了保持正確的匹配之外，同時也會保留大量的誤匹配，從而降低匹配精度。如果誤匹配過多，RANSAC 算法就有可能會失效，從而估算不出較為精確的模型；而當(dāng)特征點(diǎn)提取過多時，RANSAC 算法的多次迭代也會成為延長算法處理時間的一個重要因素。

為了將RANSAC 算法更好地在不同場景下進(jìn)行應(yīng)用，近幾年不少學(xué)者進(jìn)行了深入的研究。文獻(xiàn)[10]提出了一種考慮空間一致性的內(nèi)點(diǎn)判斷方法（Graph-CutRANSAC，GC-RANSAC），并結(jié)合圖割算法解決內(nèi)點(diǎn)判斷的優(yōu)化問題，從而提升了RANSCA 算法的精度與效率。文獻(xiàn)[11]提出了PASAC 算法，利用先驗(yàn)信息進(jìn)行模型估算。該算法分析了視覺里程計(jì)特征點(diǎn)跟蹤的誤差規(guī)律，進(jìn)行了快速的模型生成和不好模型的快速淘汰，使得位姿估計(jì)步驟比傳統(tǒng)RANSAC 算法更加快速和精確；文獻(xiàn)[12]提出了NG-RANSAC（ Neural-Guided RANSAC） 算 法， 將RANSAC 與神經(jīng)網(wǎng)絡(luò)相結(jié)合。該神經(jīng)網(wǎng)絡(luò)可以預(yù)測每個觀測值的權(quán)重，而權(quán)重則可以指導(dǎo)最小集的采樣，更好地處理誤差比例較大的數(shù)據(jù)。

本文對RANSAC 算法的耗時與精確度進(jìn)行了優(yōu)化，其中部分思路借鑒了基于網(wǎng)格的運(yùn)動估計(jì)（Grid-based Motion Statistics，GMS）[13]理 論，并 對RANSAC 算法的隨機(jī)采樣進(jìn)行了優(yōu)化。首先對兩幅圖的特征點(diǎn)進(jìn)行暴力匹配（Brute-Force)[11]，并按照特征點(diǎn)的匹配質(zhì)量進(jìn)行排序；然后借鑒GMS 理論，進(jìn)一步剔除誤匹配；同時利用網(wǎng)格法降低算法的復(fù)雜度，對分值最高（網(wǎng)格內(nèi)特征點(diǎn)匹配正確率最高且匹配對數(shù)最多）的3 塊網(wǎng)格采用順序選取策略分別進(jìn)行模型估算；最后將這3 個模型進(jìn)行聚合從而獲取更為精確的匹配結(jié)果。

1 特征匹配算法

1.1 GMS 算法

GMS 算法是一種基于網(wǎng)格的運(yùn)動統(tǒng)計(jì)方法，其目的是為特征點(diǎn)匹配提供一種比較快速且魯棒的解決方案。主要思想是：實(shí)際情況下的物體運(yùn)動一般都是平滑的，因此假設(shè)那些在圖像坐標(biāo)系上相鄰的像素往往是一起運(yùn)動的[14]。

在實(shí)際生活中，剛性物體的運(yùn)動具有一定的一致性，因此相鄰像素有很大的概率分布在該物體上。如運(yùn)動統(tǒng)計(jì)示意圖（圖1）中所示，黃圈內(nèi)的點(diǎn)都是匹配正確的特征點(diǎn)；綠色連接線的一對特征點(diǎn)在其鄰域內(nèi)有著其他多對匹配的支持（如白線所示）；而紅色圈內(nèi)匹配的特征點(diǎn)其實(shí)是錯誤的，所以該匹配周圍就沒有能夠支持它的其他匹配。

圖1 運(yùn)動統(tǒng)計(jì)示意圖Fig.1 Demonstrationofmotionstatistics

設(shè)有兩幅圖像 G1和 G2，對這兩張圖片分別進(jìn)行特征點(diǎn)提取，并假設(shè)經(jīng)過暴力匹配后一共有n對是特征點(diǎn)匹配，C表示總的匹配集合，ci表示其中的每一對匹配，即C={c1,c2,···,cn}。

正確的匹配受運(yùn)動平滑性約束，而錯誤的匹配往往不受其影響。如圖1 所示，在鄰域內(nèi)，正確的匹配往往比錯誤的匹配有著更多的支持，這個支持稱為“相似匹配”（圖1 中黃色圈內(nèi)的白色連接線所連接的匹配對），用si表示。所以，“相似匹配”的數(shù)量（記作 |S）i| 可以判斷某個匹配是正確還是錯誤，即|Si|可以作為ci運(yùn)動上的支持。

若對每個特征匹配都進(jìn)行打分會導(dǎo)致算法的時間消耗過大，時間復(fù)雜度達(dá)到O(N)（N為特征匹配數(shù)量）。所以GMS 算法進(jìn)一步提出了網(wǎng)格統(tǒng)計(jì)的方法，將一幅圖像默認(rèn)劃分為20×20 的網(wǎng)格，對每個網(wǎng)格進(jìn)行評分。

圖2 所示的網(wǎng)格框架中，將兩個圖像G1和G2分別劃分為無重疊的網(wǎng)格單元。定義ci是落在單元格Ga和Gb中的匹配（例如圖中的紅色對應(yīng)關(guān)系）。ci鄰域內(nèi)的特征點(diǎn)被重新定義為

圖2 網(wǎng)格框架Fig.2 Grid-basedframework

并且“相似匹配”重新定義為

其中：Ca為位于網(wǎng)格Ga的匹配；Cab為同時落在Ga和Gb上的匹配。也就是說，同一個網(wǎng)格內(nèi)的匹配都稱為“鄰居”，用Ni表示；同時在一對網(wǎng)格對內(nèi)的匹配稱為“相似匹配”，用Si表示。落在同一網(wǎng)格單元對中的對應(yīng)關(guān)系共享相同的運(yùn)動支持，因此只需要對網(wǎng)格單元對進(jìn)行分類，而不是將所有匹配分別進(jìn)行正確性區(qū)分，從而可以將總的復(fù)雜度降到O(1)。

1.2 基于網(wǎng)格運(yùn)動統(tǒng)計(jì)與RANSAC 的優(yōu)化圖像匹配算法

傳統(tǒng)的RANSAC 算法先選取少量的幾組數(shù)據(jù)估算出一個模型，然后使用其余的數(shù)據(jù)對該模型進(jìn)行驗(yàn)證，統(tǒng)計(jì)內(nèi)點(diǎn)的數(shù)量。如此反復(fù)迭代一定的次數(shù)，選出內(nèi)點(diǎn)數(shù)最多的那個模型作為最終的結(jié)果。

將RANSAC 算法應(yīng)用到視覺中的最終模型是單應(yīng)性矩陣[15]。單應(yīng)性矩陣定義了兩幅圖像之間的映射關(guān)系，也就是說，在知道了某點(diǎn)在一幅圖像的像素點(diǎn)位置后，可以通過單應(yīng)性矩陣求得其在另一幅圖像中點(diǎn)的確切位置。如式（3）所示：

其中： [x′y′1]T和 [x y1]T分別為3D 空間點(diǎn)在兩個像素平面的2D 齊次坐標(biāo)，這兩個像素點(diǎn)通過單應(yīng)性矩陣（式中3×3 矩陣）建立起對應(yīng)關(guān)系。實(shí)際處理時一般令單應(yīng)性矩陣中的h33為1，因此只有8 個未知參數(shù)。即需要隨機(jī)選取4 對特征點(diǎn)匹配（每幅圖中選取的4 個特征點(diǎn)不可共線），列出8 個線性方程進(jìn)行計(jì)算。具體流程如下：

（1）對兩幅圖像進(jìn)行特征點(diǎn)的選取，利用暴力匹配方法進(jìn)行特征點(diǎn)的初始匹配。

（2）隨機(jī)選取4 對特征點(diǎn)匹配進(jìn)行估算，得出模型H（單應(yīng)性）矩陣。

（3）將其他匹配代入模型進(jìn)行驗(yàn)證，統(tǒng)計(jì)內(nèi)點(diǎn)個數(shù)（如果某匹配的誤差在一定的閾值范圍內(nèi)則被稱為內(nèi)點(diǎn)）。

（4）迭代到一定次數(shù)后，選出內(nèi)點(diǎn)數(shù)最多的模型作為最優(yōu)解。

從上述步驟中可以看出，傳統(tǒng)RANSAC 算法存在較多的局限性，主要分為效率與精度兩個部分。首先，特征點(diǎn)的質(zhì)量與數(shù)量對算法的最終結(jié)果影響較大，若特征點(diǎn)誤匹配較多，則需要進(jìn)行更多次數(shù)的迭代，并且每一次迭代計(jì)算得到的單應(yīng)性矩陣都會對所有的特征匹配進(jìn)行內(nèi)外點(diǎn)檢驗(yàn)，這大大增加了RANSAC 算法的耗時；其次是RANSAC 算法最終只采用一組解，剩余模型中包含的有效信息全部被舍棄，而這些被舍棄的模型經(jīng)過算法處理能夠提供更多的有效信息，使得位姿估計(jì)結(jié)果更加精準(zhǔn)。

針對這些問題，本文提出了RANSAC 改進(jìn)算法，算法步驟如下：

（1）首先利用同一物體在相似圖像上呈現(xiàn)出的特征點(diǎn)的鄰域灰度值往往有較高相似度的特性，對誤匹配進(jìn)行初步篩除。因?yàn)镽ANSAC 算法一般會應(yīng)用于圖像拼接、視覺里程計(jì)或是三維重建中，在這些應(yīng)用場景下，相鄰近的圖像幀之間的構(gòu)圖和灰度值差異都不會很大。根據(jù)這一特性將初始匹配點(diǎn)按照灰度梯度變化的相似性從大到小依次排序，并保留前80%的特征點(diǎn)匹配對作為求參點(diǎn)集UF，從而減少單應(yīng)性矩陣估計(jì)的迭代次數(shù)。本文采用8 鄰域的拉普拉斯算子[16]（如圖3 所示）計(jì)算特征點(diǎn)周圍灰度值的梯度變化。具體公式如下：

圖3 8鄰域拉普拉斯算子模板Fig.3 Eight-neighborhoodLaplaceoperator

其中： ?f(x,表y) 示點(diǎn) (x,y的) 梯度變化；I(x,y)表示點(diǎn) (x,y)處的灰度值。

（2）利用GMS 算法對上一步求得的UF內(nèi)的特征點(diǎn)匹配進(jìn)行處理，篩除更多干擾，為RANSAC 算法提供更高質(zhì)量的匹配，從而進(jìn)一步降低RANSAC 算法的迭代次數(shù)并獲取更精確的模型。同時利用網(wǎng)格統(tǒng)計(jì)方法，分別對得分最高的3 個網(wǎng)格內(nèi)的特征點(diǎn)匹配進(jìn)行單應(yīng)性矩陣的計(jì)算，求出每個網(wǎng)格的最終模型。

如圖4 所示，A、B 和C 分別為特征匹配得分最高的3 個網(wǎng)格。以A 網(wǎng)格為例，將其鄰域（周圍紅色斜紋部分）納入計(jì)算范圍，增加更多的有效信息。將該九宮格區(qū)域內(nèi)的特征匹配作為局部的求參點(diǎn)集，利用RANSAC 算法求解出其對應(yīng)的單應(yīng)性矩陣。B 和C 網(wǎng)格的操作與A 一致，分別得到B 與C 的單應(yīng)性矩陣。

圖4 求解高分網(wǎng)格的單應(yīng)性矩陣Fig.4 Solvethehomographymatrixofahigh-resolutiongrid

將這3 個模型進(jìn)行聚合優(yōu)化，進(jìn)一步提升RANSAC算法的精度，如圖5 所示。RANSAC 需要找到一個能滿足最多特征點(diǎn)匹配的模型，并讓模型估計(jì)出的特征點(diǎn)與真實(shí)特征點(diǎn)之間的誤差盡可能最?。↖mage2中的紅色點(diǎn)是真實(shí)特征點(diǎn)，黃色點(diǎn)則是由不同的迭代模型估算出的特征點(diǎn)位置）?？梢悦黠@看出，藍(lán)色虛線框內(nèi)的黃色點(diǎn)距離真實(shí)特征點(diǎn)的距離均很近，即模型H1、H2和H3都是較優(yōu)秀的模型。模型的精確性會受到許多因素的干擾，其中最主要的因素就是其本身的估計(jì)噪聲以及數(shù)據(jù)測量的噪聲影響[17]。由于較好的候選模型所估算出的特征點(diǎn)位置在真實(shí)值附近一般都是呈現(xiàn)零均值高斯分布，所以通過對模型進(jìn)行聚合，可以盡量消除噪聲影響，從而生成更為精確的結(jié)果。

圖5 模型聚合示意圖Fig.5 Demonstrationofmodelaggregation

（3）傳統(tǒng)RANSAC 算法在求解單應(yīng)性矩陣的迭代過程中，首先會統(tǒng)計(jì)該矩陣對應(yīng)的內(nèi)點(diǎn)數(shù)目，并將其和設(shè)定的期望值比較，若大于期望值，則判定該單應(yīng)性矩陣為最終模型；反之迭代次數(shù)加1，并重復(fù)上述步驟，直至達(dá)到迭代次數(shù)后，選取內(nèi)點(diǎn)率最高的模型作為最終模型。而隨機(jī)采樣方法有較大的概率選取到質(zhì)量較差的特征點(diǎn)匹配，導(dǎo)致計(jì)算出的單應(yīng)性矩陣的內(nèi)點(diǎn)數(shù)小于設(shè)定好的期望值，從而使得每次計(jì)算都需要執(zhí)行完所有的迭代次數(shù)。這種情形不但大幅增加了算法耗時，同時也有較大概率無法獲取符合預(yù)期的模型。

改進(jìn)算法步驟（1）中已經(jīng)對原始的特征點(diǎn)匹配進(jìn)行了篩選并排序，因此本文對隨機(jī)采樣這一步驟進(jìn)行優(yōu)化，變更為按照灰度相似度排序，并依次選取4 組特征點(diǎn)匹配進(jìn)行計(jì)算。

如圖6 所示，選取的九宮格區(qū)域內(nèi)的特征匹配已經(jīng)在步驟（1）中按照灰度梯度變化的相似性從大到小依次排序，所以按照順序選取4 組特征匹配進(jìn)行模型計(jì)算，這樣可以大概率在迭代上限之前求得滿足預(yù)期要求的高質(zhì)量模型，從而有效地減少RANSAC算法的迭代次數(shù)，提高模型求取的速度。

圖6 順序選取示意圖Fig.6 Schematicdiagramofsequentialselection

優(yōu)化算法的偽代碼如下：

（1）Input：N對特征點(diǎn)匹配對

（2）Output：最優(yōu)單應(yīng)性矩陣

（3）①對特征匹配進(jìn)行灰度值相似度排序

（4）對特征點(diǎn)進(jìn)行BF 匹配

（5）使用式（2）～式（4）進(jìn)行灰度值相似度排序

（6）取前80%的特征匹配組成求參點(diǎn)集UF

（7）②選取評分前三的網(wǎng)格（以UF替代原始特征匹配集合進(jìn)行處理）

（8）將圖片劃分為K個網(wǎng)格，進(jìn)行GMS 打分

（9）選取評分最高的3 個網(wǎng)格塊

（10）分別存儲3 對網(wǎng)格塊內(nèi)的特征點(diǎn)匹配M1、M2、M3

（11）③求出模型

（12）for（1≤i≤3）分別對M1、M2、M3進(jìn)行模型估計(jì)

（13） while（n≤迭代次數(shù)）do

（14）Mi內(nèi)進(jìn)行RANSAC（順序選取策略）計(jì)算

（15） 記錄Mi內(nèi)的最優(yōu)模型Hi

（16）end

（17）④對3 組模型進(jìn)行聚合

（18）將3 組模型H1、H2、H3進(jìn)行特征點(diǎn)聚合

（19）保存并輸出聚合后的結(jié)果

2 仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)使用平臺的處理器為inteli7-8750H，內(nèi)存16GB，運(yùn)行Ubuntu16.04 系統(tǒng)。用于實(shí)驗(yàn)的圖像來自牛津大學(xué)提供的數(shù)據(jù)集。為了驗(yàn)證算法的性能，在數(shù)據(jù)集中選取若干個圖片組，每組包含一張參照圖像和5 張對比圖像。相比于參照圖像，對比圖像會進(jìn)行不同形式的變換。如圖7 所示，第1 組(圖7(a))為模糊變換，即對同一圖像用不同的高斯核進(jìn)行模糊處理，模糊處理后的圖像逐一與原始圖像進(jìn)行匹配。其中上方為參照圖像，下方為對比圖像（一組內(nèi)共有不同變換程度的5 張對比圖像）；第2 組(圖7(b))為亮度變換，即對同一圖像逐漸降低亮度，將改變亮度后的圖像逐一與原始圖像進(jìn)行匹配；第3 組(圖7(c))為旋轉(zhuǎn)縮放變換，即對參照圖像進(jìn)行一定程度的縮放并同時逐步增加旋轉(zhuǎn)角度，將變換后的圖像依次與原始圖像進(jìn)行匹配。

圖7 數(shù)據(jù)集示意圖Fig.7 Demonstrationofdataset

將改進(jìn)算法分別與經(jīng)典RANSAC 算法以及GMS 與RANSAC 的融合算法進(jìn)行對比。所有圖像都使用ORB 特征點(diǎn)法進(jìn)行特征點(diǎn)提取，提取個數(shù)為每幅圖像2000 個。選取的判定指標(biāo)為精確率（P）與召回率（R），并且認(rèn)為與真實(shí)的距離小于等于10 個像素的匹配關(guān)系是正確的，其余則判定為錯誤匹配。

其中：NT為算法提取出的正確的特征點(diǎn)匹配數(shù)目；N為算法提取出的所有的特征點(diǎn)匹配數(shù)目；M為利用數(shù)據(jù)集給出的單應(yīng)性矩陣算出的所有的匹配對，即樣本中所有的信息總數(shù)。

圖8～圖10 示出了各組圖片特征匹配精確率與召回率的折線圖，其中橫坐標(biāo)表示每組圖像內(nèi)5 張經(jīng)過變換的圖片?？梢悦黠@看到，改進(jìn)算法在各個場景下都有良好的魯棒性，性能較傳統(tǒng)RANSAC 算法有明顯的提升，相比于性能較優(yōu)的RANSAC+GMS融合算法，精確率提升了4.8%；召回率則提升了6.2%。

圖8 不同模糊程度圖像結(jié)果對比圖Fig.8 Comparisonofimagineresultswithdifferentblurvariation

圖10 旋轉(zhuǎn)+縮放圖像結(jié)果對比圖Fig.10 Comparisonofimagineresultswithdifferentrotationandscaling

為了檢驗(yàn)改進(jìn)算法對不同特征點(diǎn)的兼容性能，加入了SIFT 特征點(diǎn)的匹配實(shí)驗(yàn)。實(shí)驗(yàn)所用的數(shù)據(jù)集與上述一致，具體數(shù)據(jù)對比如表1 所示。

表1 SIFT 特征點(diǎn)仿真實(shí)驗(yàn)結(jié)果Table1 SimulationexperimentresultsofSIFT

除了對精確率與召回率的提升，改進(jìn)算法也采用了與特征點(diǎn)匹配的順序選取策略以及網(wǎng)格加速方法對算法效率進(jìn)行優(yōu)化。為了驗(yàn)證算法的實(shí)際耗時，依次增加圖像ORB 特征點(diǎn)的選取個數(shù)，進(jìn)行算法耗時測試，結(jié)果如表2 所示。

表2 算法耗時對比Table2 Comparisonofalgorithmtimeconsumption

圖9 不同亮度圖像結(jié)果對比圖Fig.9 Comparisonofimagineresultswithdifferentluminancevariation

可以明顯看出，本文的改進(jìn)算法相比于傳統(tǒng)RANSAC 算法在時間消耗上明顯縮短。為了與上文的實(shí)驗(yàn)保持一致，將特征點(diǎn)個數(shù)為2000 的這組數(shù)據(jù)進(jìn)行比較。由表中數(shù)據(jù)可得，此時RANSAC 算法、GMS+RANSAC 融合算法耗時以及本文改進(jìn)算法耗時分別為115.80、70.80、78.23ms。對比可得改進(jìn)算法的計(jì)算時間較RANSAC 算法減少32.44%，與GMS+RANSAC 融合算法耗時基本一致，可以更快速地完成較高質(zhì)量的特征點(diǎn)匹配。

3 結(jié) 論

本文在圖像特征點(diǎn)匹配算法（RANSAC）的基礎(chǔ)上進(jìn)行了精度與效率上的改進(jìn)：在使用BF 法初步匹配后，將初始匹配點(diǎn)按照灰度梯度變化的相似性從大到小依次排序；在此基礎(chǔ)上對所有匹配進(jìn)行網(wǎng)格劃分并對各網(wǎng)格進(jìn)行評分，使用順序選取策略進(jìn)行模型迭代。最終使用聚合后的最優(yōu)模型對初始匹配進(jìn)行篩選，從而獲得更好的匹配質(zhì)量與更少的迭代次數(shù)，提升了算法的性能。

仿真實(shí)驗(yàn)結(jié)果表明，本文提出的基于網(wǎng)格加速與順序選取策略的優(yōu)化圖像匹配算法在模糊場景、旋轉(zhuǎn)縮放以及明暗變化等不同場景下都具有較好的魯棒性。相較于一些傳統(tǒng)的算法，其精確率與召回率有明顯提升；同時，計(jì)算耗時較傳統(tǒng)RANSAC算法也大幅減少。