融合RANSAC 與GMS 圖像特征的匹配算法

馮寶鳳， 楊劍鋒，2， 嚴 可， 鄒 瓊， 仝天樂

（1 貴州大學數學與統計學院， 貴陽 550025； 2 貴州理工學院大數據學院， 貴陽 550003；3 深圳市瑞云科技股份有限公司， 廣東 深圳 518000； 4 貴州黔驢科技有限公司， 貴陽 550000）

0 引 言

圖像匹配是通過計算機和數學理論知識，對給定的圖像按照特定目的進行處理［1］，其在物體識別［2］、圖像拼接［3］、視覺映射［4］等領域應用廣泛。圖像匹配大致分為兩大類：對區域的匹配算法和對特征的匹配算法［5］。 對區域進行匹配的方法主要是指對圖像進行密集匹配，利用整幅圖像的像素強度進行圖像匹配，建立一個密集像素的對應關系；利用圖像特征進行匹配的方法，需要提取兩幅圖像中的特征點以及圖像的局部特征描述符，通過描述符與度量空間相似度的距離判斷來建立對應關系，進行圖像特征匹配。 其中，圖像特征匹配算法具有強魯棒性、高配準率、計算速度快等優勢，因此常被用于圖像處理［6］。

基于圖像的特征匹配算法發展至今，已經產生了許多經典以及改進算法。 如：Lowe 等［2］提出的SIFT（scale-invariant feature transform）算法，擁有旋轉不變性、尺度不變性以及獨特性，不會受光照、仿射變換、噪聲的影響，廣泛應用于各個領域，但其利用128 維數據，高維數據計算時間長，實時性目的較差；Bay 等［7］在SIFT 基礎上提出了具有64 特征維數的SURF（Speeded Up Robust Features）算法，SURF降低了數據維度，具有良好的魯棒性，但存在精度低、實時性差等缺點； Leutenegger 等［8］提出BRISK（Binary Robust Invariant Scalable Keypoints）算法，雖然該算法也擁有旋轉不變性、尺度不變性以及魯棒性，針對較大模糊的圖像配準較好，但存在配準率低的問題；2017 年，JW Bian 等［9］提出GMS（Gridbased Motion Statistics）算法，其具有運動特性，超魯棒性的優點，但其在進行網格劃分時，存在誤匹配等問題。 針對這些算法，國內外的許多優秀學者也對其計算速度、配準率進行了改進。 對于大部分匹配算法存在誤匹配問題，Wu 等［10］提出利用RANSAC算法刪除誤匹配，但是這個方法存在耗時長等問題。針對SIFT 算法實時性差，存在誤匹配問題，許多學者提出了大量優秀的改進方法。 針對RSANSAC［11］刪除誤匹配存在的不足問題，Muja 等［12］提出FLANN 算法，該算法主要是利用了比率測試，來刪除誤匹配，提高了計算速度；程明明等［13］進行雙邊建模，又加入運動的空間信息，對誤匹配進行刪除；程向紅等［14］加入了運動平滑約束，結合RANSAC 的單應矩陣對低匹配區域進行篩選，提高了召回率與RANSAC 的計算時間；陳潔等［15］將極限約束引入特征匹配中，但是該算法加大了匹配時間。 丁輝等［16］為解決傳統匹配算法配準時間長、配準率低問題，提出了一種將GMS、矢量系數相似度（VCS） 與RANSAC 相結合的GC-RANSAC 圖像配準算法，提高了匹配精度、縮短了匹配時間。

本文在GMS 算法的啟發下，由于GMS 匹配算法在利用運動平滑性約束進行匹配時仍會存在一些誤匹配問題，影響其匹配率與配準率。 因此為提高其算法的性能，本文提出了RGMS 算法，先用RANSAC 對兩幅圖像的特征進行篩選，再利用GMS進行圖像的特征匹配，使GMS 算法提高其配準率的情況下，不影響匹配的實時性，并對RGMS 算法進行了實證對比實驗分析研究。

1 ORB 特征點檢測算法

ORB 算法是由Ethan Rublee 等人［17］提出的一種基于FAST［18］和BRIEF［19］非?？焖俚亩M制描述符。 其主要貢獻在于：在FAST 中增加了一個快速和準確的方向計算，有效地計算了定向BRIEF 特征，并分析了定向BRIEF 特征的方差和相關性，減少了旋轉BRIEF 特征的方差損失。

1.1 OFAST 算法

ORB 算法首先提出基于FAST 的OFAST（FAST Keypoint Orientation）算法。 FAST 算法是一種二維圖像的特征點檢測算法。 其將圖片轉換為灰度圖，快速檢測其特征點，具體步驟如下：

（1）設中心點p為目標像素，半徑為r， 得到M個領域像素點；

（2）分別對像素點與p點灰度值之差的絕對值進行計算；

（3）利用設定的閾值與步驟（2）得到的值進行對比，如果像素點與目標像素點p的灰度值之差的絕對值大于設定的閾值，則認為該點為FAST 點，否則該點不為FAST 點。

OFAST 使用FAST-9 算法進行關鍵點檢測定位，該算法利用一個“強度質心點”來計算角點的方向。 強度質心點［20］的具體定義為：假設一個角度的強度從其中心偏移，則可以使用向量來計算方向。計算流程為：

（1）Rosin 定義圖像矩為

（2）利用這些圖像矩找到質心點

（3）計算圖像的中心點到強度質心點的向量由此得到角點的角度：

其中，atan2 是arctan 的四邊形感知。

為提高度量的旋轉不變性，x和y在以r為半徑的圓形區域內。

1.2 RBRIEF 算法

RBRIEF（Rotation-Aware Brief）算法是通過對關鍵點的區域進行二進制計算，得到二進制字符串描述符。 考慮圖像塊p，定義τ為一個二進制計算：

其中，p（x） 是p在某點x的強度。

由此可以得到n個二進制操作的組合向量：

對不同類型的測試分布，該算法考慮了高斯分布，選擇描述子的長度n＝256，每一個點是來自31×31 像素塊的5×5 的子窗口。 為了使BRIEF 不受圖像旋轉的影響，可根據關鍵點的方向來引導BRIEF。

對于任何長度為n的描述子，需要n個匹配對，在位置（xi，yi），定義一個2×n的矩陣：

在得到關鍵點的方向θ和其旋轉矩陣Rθ的情況下，構造S的旋轉矩陣Sθ：

所以，得到旋轉的BRIEF 運算符變為

但是，旋轉的BRIEF 方差會有損失。 為了得到一個良好的二進制特征，提高描述子各個位置的方差，提出了如下RBRIEF 算法，RBRIEF 在方差和相關性方面對旋轉BRIEF 進行了改進。

（1）針對所有訓練集的圖像塊進行計算，得到矩陣；

（2）計算矩陣每一列的均值，按從小到大進行排序，得到向量T；

（3）貪心搜索：

①從T中取出一個對比對，計算該對比對與R各個對比對的相關聯程度。 若相關度大于閾值，則舍棄取出的對比對，否則將這個對比對加入R中。

②重復進行步驟①的操作，其結果是讓256 個對比對存在R中。 如果少于256 個對比對，則提高設定的域值重復操作。

③最終得到固定的256 個對比對。

2 改進的RGMS 特征匹配算法

利用ORB進行圖像特征點提取后，兩幅圖片的特征點存在明顯差異，兩幅圖片差異越大，特征點越不一致。 因此，本文提出RGMS算法，先用RANSAC算法對兩幅圖像的特征進行篩選，再結合GMS算法進行特征點匹配，提高圖像的特征點匹配率。

2.1 RANSAC 特征篩選

RANSAC（Random Sample Consensus）算法是由MA Fischler等［11］提出的一種應用于圖像分析和自動制圖的模型擬合算法，該算法能夠解釋含有相當大比例的嚴重錯誤數據，非常適用于圖像分析的應用。RANSAC算法主要是通過一組含有“異常值”的數據，得到一個正確的數學模型。 圖像中的＂異常值＂，通常是指提取數據中含有噪聲的干擾。RANSAC并不是使用的數據越多越好，而是利用盡可能少的數據集，通過估計模型不斷擴展數據集，直到得到合適的模型。RANSAC的具體計算流程如下：

（1）設定模型M1：該模型需要大于等于n個數據點來獲得自由參數，一組數據p（其中的數據點數量應該大于n），通過從p中隨機選擇n個數據點的一個子集S1 來實例化模型；

（2）通過M1 確定p中的子集S1*，S1*在M1的某個誤差容限之內，稱為S1 的共識集；

（3）如果S1*大于閾值t，則利用S1*來計算一個新的模型M1*；如果S1*小于閾值t， 則隨機再選擇一個新的子集，重復上述步驟。 設定迭代次數k，經過k次迭代后，找到最大的共識集擬合模型，或者以失敗告終。

RANSAC算法包含3 個未指定參數。

2.1.1 確定誤差容限

誤差容限定義為超過平均誤差的一至兩個標準差，標準差可以通過實驗得到。 如計算干擾數據和測量造成的隱含誤差，可以得到樣本偏差。 數據的樣本偏差是數據的誤差容限的一個函數，誤差容限對每個模型都是不同的。 與總誤差的大小相比，誤差容限的變化相對較小。

2.1.2 確定最大迭代次數

得到最終模型需要設定所需的預期實驗次數k，實驗次數越多，所需的時間也就越久。 設w是任何選定的數據點在模型的誤差容限內的概率。則有：

其中，由k得到的期望值為

因為幾何數列之和具有如下性質：

則可利用該性質對a進行微分，得到：

因此，可以得到：

E（k） 一些數值列表對應的n和w的值見表1。再計算k的標準差SD（k）：

表1 E（k）的一些數值的列表對應的n 和w 的值Tab. 1 List of some values of E（k） corresponding to the values of n and w

其中，

利用幾何數列的特性和兩個不同的指數，得到：

因此，最終可以得到：

由此可看出，SD（k） 約等于E（k）。

如果想以概率z確保隨機選擇中至少有一個是由n個數據點組成的無錯誤組合，則需要k次選擇（每次至少選擇n個數據點），其中：

可以得到，當wn?1 時，k≈log（1-z）E（k）。因此，想要保證有一個高的概率z， 本文選擇當z＝0.9，wn?1 時，得到k≈2.3E（k）。 為了達到篩選的目的，選擇對模型進行500 次迭代，即K＝500。

2.1.3 閾值t的選擇

閾值t是確定p的所有子集被找到的下限，其必須有一個足夠大的共識集。 因此，閾值t的值不能太小。 閾值的選擇必須滿足要有足夠數量的數據點，并對改進的模型可以進行正確的評估。 為了不讓錯誤的模型和共識集兼容，令y是隨機給定的數據點在不正確模型誤差容限內的概率，同時要求足夠小。 目前還沒有能夠完全精確得到y的方法，但可由假設其小于w且y ＜0.5，則t-n的值等于5 時，就可以達到高于95%概率，使其與錯誤的模型不會存在兼容性。

2.2 GMS 特征匹配

GMS（Grid-based Motion Statistics）算法［9］是一種快速匹配特征檢測點的算法，通過該算法對篩選出的特征點進行匹配，得到RGMS 改進的匹配結果。 GMS 算法假設：運動平滑可以使得在一個領域周圍的正確匹配，可在另一幅三維圖像中相同的位置檢測到。 該假設意味著在正確匹配的鄰近點，對于一個相同的位置，兩幅圖像中有著更多相似的特征。

GMS 算法流程如下：

假設圖像Ia和Ib對應的區域為{a，b}，Ia有N個特征點，Ib有M個特 征 點。X＝{x1，x2，x3，…，xi，…，xN} 是Ia到Ib中所有最近鄰特征匹配的集合。Xi?X是區域{a，b} 中xi匹配的子集。Si是鄰域支持的衡量標準：

xi鄰域內的匹配數可以通過二項分布來計算，特征點的匹配是相互獨立的，可以得到：

式中：pt＝t＋（1-t）m／M為真匹配的概率，pf＝β（1-t）m／M是假匹配的概率，t為區域a支持域中一個特征正確匹配的概率，m為b鄰域區域中的特征點數，M為Ib中的所有特征點數，β為彌補假設所增加的參數。

為了增大描述差異，對Si進行更廣義的假設：

其中，K表示兩個不相交區域內匹配i預測一起移動的數量，akbk

{} 表示預測的區域對。

同時也可以得到Si的二項分布：

其中，n表示每個支持區域中的特征數量平均值，K表示每個網格劃分的區域。

由于GMS 算法的性能和網格的大小相關，因此網格的劃分非常重要。 網格單元格越多，匹配定位效果越好，但也會影響計算時間。 實驗結果證明，G＝20× 20 的網格有10 000 個特征，得到n的平均值為25，如果需要更多的特征就需要更精細的單元格。 為了達到更好的效果，本文采用G＝20× 20 網格進行劃分。 對于閾值Sij的設定，會把單元對分成真集、假集{T，F} 兩個集合。 為了能夠拒絕大量的錯誤單元對，閾值可以近似為，由此可以得到一個單一的參數閾值函數：

其中，ni是單個網格單元格中的特征數量的平均值，將每個網格劃分為9 個單元格，根據實驗可得α＝6，GMS 算法是在BF 算法的啟發下得到的，BF算法可以得到大量的匹配對，但是難以可靠的分離正確和錯誤匹配。 GMS 算法是將運動平滑封裝在一個區域內，可以通過計算一個支持區域內的匹配數量，來區分一個匹配是否正確。

3 實驗結果與分析

3.1 實驗平臺

本次實驗使用的CPU 為Intel（R） Core（TM） i5-10300H，頻率為2.50 GHz，操作系統為Windows 10，實驗測試的圖片來自TUM 數據集。 對于TUM 數據集，選取兩類圖片進行實驗。 其中，實驗1 為紋理清晰豐富的家庭辦公室長桌面圖片集，實驗2 為表面光滑紋理較少的柜子圖片集，分別選取200 張圖片，100 組數據進行實驗分析。 實驗1、實驗2 的圖片樣式如圖1 所示。

圖1 測試圖片Fig. 1 Test pictures of experiments 1 and 2

3.2 實驗結果分析

經典的特征點匹配方法種類有暴力匹配算法、SIFT 算法、FLANN 算法等，但是這些算法都存在匹配率低的問題，特別是在圖片紋理低的情況下，匹配率不高。 本文在GMS 的算法下融合RANSAC 算法，在紋理豐富和紋理低的情況下都能很好的進行特征點匹配，匹配率均高于其他算法。 通過暴力匹配、FLANN、GMS 以及本文算法，分別對兩類圖片集進行特征點匹配實驗。

實驗1 的RGMS 算法匹配效果如圖2 所示，4種算法的匹配率如圖3 所示，4 種算法對圖片集的特征點匹配效果對比詳見表2。 由表2 可知，傳統的BF＋KNN 算法的匹配率為21.02%，FlANN 算法的匹配率為19.59%，GMS 算法的匹配率為27.52%，RGMS 算法的匹配率為29.65%；RGMS 算法比GMS算法提高了2.13%，比FlANN 算法提高了10.06%，比BF 算法提高了8.63%；雖然匹配時間略高于其它算法，但總體上并不影響該算法的實時性。

圖2 RGMS 算法對實驗1 圖片匹配效果圖Fig. 2 RGMS algorithm matching effect for experiment 1 images

圖3 實驗1 中4 種算法匹配率的結果圖Fig. 3 Graph of the results of the matching rate of the four algorithms in Experiment 1

表2 基于ORB 算法的4 種算法對實驗1 圖片集的特征點匹配效果對比Tab. 2 Comparison of four algorithms based on ORB algorithm for matching feature points on the experiment 1 image set

表3 是對實驗2 紋理少的圖片集進行特征點提取與特征點匹配，RGMS 算法匹配效果如圖4 所示，4 種算法的匹配率效果如圖5 所示。 由此可見，對于表面紋理少的圖片，傳統的BF＋KNN 算法的匹配率為9.52%，FlANN 的匹配率為6.78%，GMS 的匹配率為15.34%，RGMS 算法的匹配率為17.54%；RGMS 算法比GMS 算法提高了2.2%，比FlANN 算法提高了10.76%，比BF 算法提高了8.02%；匹配時間較其它算法略高，但比GMS 算法用時少0.01，且總體上不影響該算法的實時性，說明該算法在圖片紋理較少的情景更具優勢。

圖4 RGMS 算法對實驗2 圖片匹配效果圖Fig. 4 RGMS algorithm matching effect for experiment 2 images

圖5 實驗2 中4 種算法匹配率的結果圖Fig. 5 Graph of the results of the matching rate of the four algorithms in Experiment 2

表3 基于ORB 算法的4 種算法對實驗2 圖片集的特征點匹配效果對比Tab. 3 Comparison of the four algorithms based on the ORB algorithm for matching feature points on the Experiment 2 image set

4 結束語

本文提出的RGMS 算法是為解決傳統的算法存在配準率低的問題。 該算法主要是將RANSAC 與GMS 算法相結合，采用RANSAC 算法篩選特征點，得到更適合匹配的特征；再通過GMS 對特征點進行平滑約束以及劃分網格計算，優化了匹配結果。 同時，將傳統算法與RGMS 算法進行對比實驗得到：

（1）RGMS 算法的匹配率在不影響計算速度的情況下高于其他匹配方法；

（2）在對紋理少的圖片集匹配時，RGMS 算法匹配時間少于GMS 算法，縮短了匹配時間，更具有匹配優勢，可以進行高質量、實時的特征匹配。

關于如何提高本文算法的匹配時間，如何獲得更高的匹配率和準確率，并將其運用于圖像拼接、三維重建中，將是本文的后續研究內容。