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

江一葦，顧幸生

（華東理工大學能源化工過程智能制造教育部重點實驗室，上海 200237）

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

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

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

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

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

1 特征匹配算法

1.1 GMS 算法

GMS 算法是一種基于網格的運動統計方法，其目的是為特征點匹配提供一種比較快速且魯棒的解決方案。主要思想是：實際情況下的物體運動一般都是平滑的，因此假設那些在圖像坐標系上相鄰的像素往往是一起運動的[14]。

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

圖1 運動統計示意圖Fig.1 Demonstrationofmotionstatistics

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

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

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

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

圖2 網格框架Fig.2 Grid-basedframework

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

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

1.2 基于網格運動統計與RANSAC 的優化圖像匹配算法

傳統的RANSAC 算法先選取少量的幾組數據估算出一個模型，然后使用其余的數據對該模型進行驗證，統計內點的數量。如此反復迭代一定的次數，選出內點數最多的那個模型作為最終的結果。

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

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

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

（2）隨機選取4 對特征點匹配進行估算，得出模型H（單應性）矩陣。

（3）將其他匹配代入模型進行驗證，統計內點個數（如果某匹配的誤差在一定的閾值范圍內則被稱為內點）。

（4）迭代到一定次數后，選出內點數最多的模型作為最優解。

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

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

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

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

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

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

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

圖4 求解高分網格的單應性矩陣Fig.4 Solvethehomographymatrixofahigh-resolutiongrid

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

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

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

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

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

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

優化算法的偽代碼如下：

（1）Input：N對特征點匹配對

（2）Output：最優單應性矩陣

（3）①對特征匹配進行灰度值相似度排序

（4）對特征點進行BF 匹配

（5）使用式（2）～式（4）進行灰度值相似度排序

（6）取前80%的特征匹配組成求參點集UF

（7）②選取評分前三的網格（以UF替代原始特征匹配集合進行處理）

（8）將圖片劃分為K個網格，進行GMS 打分

（9）選取評分最高的3 個網格塊

（10）分別存儲3 對網格塊內的特征點匹配M1、M2、M3

（11）③求出模型

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

（13） while（n≤迭代次數）do

（14）Mi內進行RANSAC（順序選取策略）計算

（15） 記錄Mi內的最優模型Hi

（16）end

（17）④對3 組模型進行聚合

（18）將3 組模型H1、H2、H3進行特征點聚合

（19）保存并輸出聚合后的結果

2 仿真實驗

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

圖7 數據集示意圖Fig.7 Demonstrationofdataset

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

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

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

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

圖10 旋轉+縮放圖像結果對比圖Fig.10 Comparisonofimagineresultswithdifferentrotationandscaling

為了檢驗改進算法對不同特征點的兼容性能，加入了SIFT 特征點的匹配實驗。實驗所用的數據集與上述一致，具體數據對比如表1 所示。

表1 SIFT 特征點仿真實驗結果Table1 SimulationexperimentresultsofSIFT

除了對精確率與召回率的提升，改進算法也采用了與特征點匹配的順序選取策略以及網格加速方法對算法效率進行優化。為了驗證算法的實際耗時，依次增加圖像ORB 特征點的選取個數，進行算法耗時測試，結果如表2 所示。

表2 算法耗時對比Table2 Comparisonofalgorithmtimeconsumption

圖9 不同亮度圖像結果對比圖Fig.9 Comparisonofimagineresultswithdifferentluminancevariation

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

3 結 論

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

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