融合GMS與VCS+GC-RANSAC的圖像配準算法

丁 輝，李麗宏*，原 鋼

（1. 太原理工大學電氣與動力工程學院，太原030000； 2. 中國煤炭科工集團太原研究院，太原030000）

（?通信作者電子郵箱ya721@163.com）

0 引言

圖像拼接和圖像配準是圖像處理中十分重要的部分。其中圖像配準是圖像拼接的基礎，也是圖像拼接最重要的一個環節。圖像配準在醫療衛生［1］、機器人［2］、自動駕駛［3］、人臉識別［4］、圖像檢索［5］、目標跟蹤等領域都有廣泛的應用。圖像配準大致可分為灰度分析和基于特征分析兩種方法［6-7］。灰度分析主要是一類特定模板對目標圖像基于灰度評價函數的滑動匹配，受光照、角度和尺度變換影響較大；而基于特征分析的配準方法由于對光照等魯棒性較好，現已成為該領域主流的分析方法。

基于特征的圖像配準分析方法大致可分為三個步驟:特征點提取、特征點匹配、計算空間變換模型。對于特征點提取算法，有經典的尺度不變特征轉換（Scale-Invariant Feature Transform，SIFT）［8］，還有在其基礎上基于速度和精度方面的優化；在提取速度優化方面有SURF（Speeded Up Robust Features）［9］、ORB（Oriented FAST and Rotated BRIEF）［10］、AKAZE（Accelerated-KAZE）［11］等算法；在提取精度優化方面有PCA-SIFT（Principal Component Analysis-SIFT）［12］、ASIFT（Affine-SIFT）［13］等。特征點描述子粗匹配通常采用暴力匹配原則（Brute-Force）與快速最近鄰搜索庫（Fast Library for Approximate Nearest Neighbors，FLANN）［14］；而在特征點精匹配步驟中，普遍使用隨機抽樣一致性（RANDom SAmple Consensus，RANSAC）算法［15］進行錯誤點剔除。但當樣本數據繁多且模型外干擾點數量大時，算法局部最優模型收斂時間會呈指數型增長；同時剔除后也會存在一些明顯的錯誤匹配點。為了兼顧配準速度和精度，Bian 等［16］提出一種基于網格運動統計（Grid-based Motion Statistics，GMS）的算法，該算法利用網格將粗匹配點區域化，統計各小區域中匹配關系的特征點數量，以此進行錯誤匹配剔除。該算法運行速度能達到實時效果，缺點是會有明顯的匹配錯誤沒有剔除。朱成德等［17］提出一種通過根據左右圖匹配對距離相近原理改進的RANSAC 算法，算法原理簡單易懂，運行速度快；但該算法通過一個距離范圍進行錯誤點剔除，當配準圖像是大視角旋轉縮放時，正確匹配對也會有極大的距離，這種情況下算法會把大量正確匹配點進行剔除，故對于有縮放和旋轉的圖像配準效果并不好。Barath 等［18］提出圖割隨機抽樣一致性（Graph-Cut RANSAC，GC-RANSAC）算法，該算法通過在RANSAC 的局部優化環節利用圖割算法（能量函數）區分內野點，優化效果和全局最優模型都極佳，缺點就是當野點較多時，算法的運行速度受到極大限制。

針對以上各算法缺陷，本文提出一種融合GMS 與VCS+GC-RANSAC 圖像配準算法:首先通過ORB 對圖像進行特征點提取并對特征點進行暴力匹配；之后通過GMS 算法對圖像做網格劃分，利用網格中正確匹配點具有一定的特征支持量原理對粗匹配對進行第一次剔除；接著利用圖像特征點與正確匹配點構成的向量可由指定向量相加而成，應用矢量系數相似性（Vector Coefficient Similarity，VCS）原理對匹配對進行進一步剔除、整理，減小錯誤匹配所占比例，以利于后面算法減少迭代次數與運行時間；最后利用GC-RANSAC 算法建立局部最優模型，得到高精度配準圖像。

1 網格運動統計

網格運動統計（GMS）算法［16］是一種基于匹配對鄰域特征點支持量的評價方法。它主要是對經過ORB 特征提取以及暴力粗匹配后的特征匹配進行過濾。圖1為GMS鄰域特征點支持量原理示意圖。以圖1 為例，正確匹配對鄰域內有兩個正確匹配支持量，而錯誤匹配對鄰域內沒有正確匹配對對其支持。具體算法原理如下:假定標準圖和待匹配圖分別為Ia、Ib，其上有兩個已匹配完成的粗匹配區域Ra、Rb。假定Ra中含有n 個特征點集合｛a1，a2，…，an｝，Rb中含有相對應的n 個特征點集合｛b1，b2，…，bn｝。Ra、Rb區域的n 個匹配對集合為｛x1，x2，…，xn｝，其中xi=(ai，bi)表示一對特征點匹配對。設Si為xi匹配正確時，其鄰域Ra中特征點支持量，則

圖1 GMS鄰域特征點支持量原理示意圖Fig. 1 Schematic diagram of GMS neighborhood feature point support principle

由式（5）可知，當Ra、Rb匹配錯誤時，Ra中一個特征點恰好還匹配到Rb區域的一個特征點幾率近乎為0，至此便證明錯誤特征匹配對鄰域內近乎沒有特征匹配對支持的理論。

由式（3）、（4）可知，特征匹配鄰域內特征點支持量符合二項分布，即:

為了提高匹配速度，將標準圖與配準圖像網格化；同時，為了將正確匹配時特征點支持量與錯誤匹配時特征點支持量差距拉大，統計目標網格及其周圍8 個網格的特征點支持量作為目標網格區域某一特征匹配的支持量。因此，鄰域特征點支持量變為:

其中:K 代表與所在網格區域相鄰不相交的網格數。由式（7）可得Si標準差與均值:

根據Si的標準差與均值設定區分正確與錯誤匹配鄰域特征點支持量閾值:

在實驗中發現mf通常極小，而Sf較大，同時α較大可以有極高的置信度拒絕大量錯誤匹配對，所以mf可以忽略，即:

對于一個網格區分正確與錯誤匹配鄰域特征點支持量閾值

其中:na表示9個網格中特征總數的平均值。

通過式（11），將待配準網格中粗匹配對鄰域特征點支持量大于τi保留，將小于τi的粗匹配點剔除，即完成了GMS算法對粗匹配對的篩選。

圖2 匹配過程中各事件的相互關系Fig.2 Relationship between events in matching process

2 VCS+GC-RANSAC

2.1 圖割隨機抽樣一致性

圖割隨機抽樣一致性（GC-RANSAC）［18］于2018 年被提出，旨在克服一些傳統RANSAC算法不足。通過實驗和仿真，其在一系列問題上（直線擬合、仿射矩陣、基本矩陣的估計）的結果比傳統RANSAC算法更加精確。

傳統RANSAC主要算法步驟為:

1）隨機挑選計算模型所需最小點數子集；

2）計算模型相關參數；

3）計算所建立模型與所有點的距離，根據距離閾值將點集內點分為內點與野點；

4）保存內點個數和模型對應的基礎矩陣；

5）重復以上步驟，迭代k次得到k個模型及其對應的內點與基礎矩陣；

6）通過評價函數比較k個模型，最后輸出最好模型。

GC-RANSAC 主要對傳統RANSAC 算法的步驟3）（局部最優）進行優化改進，傳統RANSAC算法對于模型內點和野點的區分僅僅依靠一個閾值，沒有考慮數據的空間結構。傳統RANSAC根據式（12）區分內野點:

其中:P 為點集中一點；θ代表模型；φ 為距離函數；ε 代表點距模型距離的閾值。

GC-RANSAC 算法提出運用一元能量函數對內野點區分進行改進:

式（13）中:一元能量函數Ek(L)表示對點集Ω中單個點P與模型距離進行懲罰。由式（14）、（15）可知，當標簽為1（內點）距離模型越近懲罰越小，當標簽為0（野點）距離模型越近懲罰力度越大。將所有點懲罰值相加便得到一元能量函數。

當數據包含很多野點，且這些野點與模型距離也比較近，在這種情況下，對不同標記的鄰近點使用相同懲罰會導致野點的主導優勢，這樣會使所有內點被標記為野點。針對這一問題，GC-RANSAC算法通過考慮點與點之間的空間結構一致性，提出基于空間一致性的能量函數Es(L):

將兩個能量函數結合成一個多項式，該多項式既考慮點對模型的匹配度又考慮空間結構一致性，即

其中:λ是一個平衡參數。

全局最佳標記L*= min E(L)，利用圖割算法可計算得到E(L)的最小值時點集標記。

2.2 VCS+GC-RANSAC原理

盡管GC-RANSAC 較之前RANSAC 和LO-RANSAC 算法，大幅提高了精度，但當野點（在圖像配準中即為錯誤匹配點）比例占點集數量（匹配集）較大時，算法可能會迭代很多次才能找到局部最優模型，這樣算法的運行速度和效率就會受到極大影響。

在圖像配準中，即使圖像經過縮放、旋轉、平移，但其各個特征點與特定的穩定特征點之間位置相對關系并不會有很大改變（穩定特征點與各個特征點構成一個整體），即由基向量運算得到的特征點矢量系數不會有太大的突變。

由此本文提出一種基于矢量系數相似性（VCS）原理對錯誤匹配特征點進行部分剔除的方法。以下為原理詳解。

根據平面向量基本原理提出假設:任一平面內任一向量均可以由兩不共線的向量相加得到，經基本仿射變換后，該向量表示形式不變。

由式（20）可得:

將式（18）代入式（21），可得

合并其他項整理得:

同理可證:

對比式（19）、（22）可證向量經仿射變換后由兩向量相加的系數不變性。考慮到一些客觀問題，本文算法將通過一個系數相似性閾值進行錯誤匹配剔除。

綜上，基于VCS的GC-RANSAC算法步驟如下:

1）挑選3 組穩定、正確且不共線的匹配對，將匹配圖與待匹配圖的3個特征點組成兩特征基向量；

2）將待評價的匹配對分別與穩定匹配對之一組成向量，并求得它們在特征基向量下的系數值；

3）將對應的系數值做相似度對比，判斷相似度值是否大于給定相似閾值T，符合條件的匹配對即組成樣本集S；

4）將樣本集S作為GC-RANSAC 算法待檢測樣本，求出局部最優模型。

3 實驗與結果分析

為了驗證本文所提改進算法運行速度與匹配精度的優異性，將本文算法與SIFT+RANSAC、ASIFT+RANSAC、GMS+GCRANSAC、AKAZE+RANSAC、GMS 進行比較，測試平臺為個人筆記本:其中操作系統Windows 7，Intel core i5-4210M CPU@2.6 GHz 內存為4 GB，算法通過Visual Studio 2015 編譯平臺編寫C++代碼進行實現，測試數據集為Oxford 標準仿射變換圖集及現實拍攝圖集。

采用匹配正確率（Correct Matching Rate，CMR）［20］與匹配時間兩個指標對算法進行綜合評價，其中CMR 評價指標的定義為:

其中:nc為特征點對匹配正確的數目；nt為算法得到的總的匹配對數目。nc可由Oxford 圖集所提供的仿射變換矩陣真值獲得。

圖3 展現了本文算法與SIFT+RANSAC、AKAZE+RANSAC、GMS 算法在Oxford 圖集的6 個子數據集的CMR 對比。實驗序號1～5 是各個算法在測試數據集序號2～6 的圖像與標準圖1 配準結果。數據集中包含了光照明暗對比（Leuven），視角尺度對比（Wall、Graf、Boat）以及模糊度對比（Trees、Bikes）三類配準測試圖像。由圖3（a）、（b）可以看出本文算法在處理模糊配準方面相較于其他三種算法更加穩定，匹配精度平均可達92%以上；四種算法在光照強度對比方面（圖3（f））匹配準確率相差不多，但本文算法仍具有些許優勢。在視角尺度變化方面（圖3（c）～（e））可以看出所有算法在實驗5 匹配精度近乎為0，這是因為視角變換太大時，匹配難度呈指數型增長，而本文算法也因GMS 算法所提鄰域特征點支持量急劇下降，導致正確匹配率驟跌。但本文算法相較于其他三種算法在前4 次實驗仍有較大優勢。而且本文算法相較于文獻［17］算法在視角尺度方面（圖3（c）實驗5 以及圖3（e）實驗4）也具有一定優勢，這主要是由于GC-RANSAC 相比RANSAC有更強的局部最優模型的刻畫。

圖3 不同算法在Oxford數據集上的CMR實驗Fig.3 CMR experiment for different algorithms on Oxford dataset

為了展示本文算法與其他算法的不同，下面將對算法綜合指標進行評價。圖4（b）～（f）展示了以Oxford 圖集中bark子數據集實驗5 為例（原圖為圖4（a）），應用本文算法與ASIFT+RANSAC、AKAZE+RANSAC、GMS、GMS+GC-RANSAC 算法進行圖像配準的結果。Bark子數據集是Oxford數據集中配準難度最大的數據集，包含了極大角度的視角轉變和尺寸縮放，這對配準提出了極大挑戰，表1 是本文算法在Bark 子數據集實驗的量化展現。由圖4配準圖可以看出，ASIFT等算法較本文算法有更多特征匹配對，但本文算法匹配對平順且無明顯的錯誤匹配對，ASIFT 算法雖然有很多特征對匹配出現，但匹配雜亂無章，有許多可見錯誤匹配對。AKAZE+RANSAC 與GMS 匹配雖然較本文算法運行速度較快，但在配準圖示中可以清晰可見有錯誤匹配對。GMS+GC-RANSAC算法匹配圖也有可見的錯誤匹配對。遵循配準中正確率首要的準則，雖配準數量較少但匹配平順且無明顯的錯誤匹配對的本文算法，相對于其他4個算法具有一定優勢。

表1 不同算法在Bark數據集實驗5的運行結果比較Tab. 1 Comparison of running results of different algorithms in Bark dataset experiment 5

圖4 Bark數據集上實驗5原圖及不同算法的配準結果Fig.4 Original image and registration results of different algorithms of experiment 5 in Bark dataset

通過表1 各算法表現分析在全局表現中，本文算法在平均匹配精度上提高了30.34%，平均匹配時間縮短了0.54 s。在局部對比方面，本文算法雖然比ASIFT 算法最后得到的匹配對數量少，但匹配正確率比ASIFT 高3.465 個百分點，且運行時間幾乎僅是ASIFT 的一半，這對實時性要求高的情況是非常重要的。本文算法較AKAZE、GMS 的運行時間分別多了0.734 s、0.503 s，這是由于GC-RANSAC 算法比RANSAC 尋找局內最優模型需要更多時間，而且GMS 的算法鄰域特征點支持量也需要比其他暴力匹配算法需要更多的時間；但匹配精度比兩種算法分別提高了62.12%、52.03%。這種在大視角變換情況下的配準正確率提高是十分重要的，是求取配準圖與待配準圖之間的仿射變換矩陣真值，進行真實圖像拼接的十分重要一步。本文算法由于在GC-RANSAC 之前對樣本進行了一次篩選，故而比GMS+GC-RANSAC 擬合最優模型迭代次數更少，運行時間更短，同時正確率也有提高。綜上所述，考慮配準確率及運行時間兩個評價指標，本文算法優于其他4種算法。

為進一步展示本文算法的實用性，對現實所拍實物圖集進行配準，該圖集包含了煤礦巷道所用液壓支架的大角度視角變換和重復性紋理物體在暗光嚴峻條件的大角度視角變換。從如圖5 所示的配準效果中可以看出，配準平順無明顯錯誤對，本文算法在實用性方面有很好表現。

圖5 本文算法在現實所拍數據集上的配準效果Fig.5 Registration results of the proposed algorithm on real dataset

4 結語

本文針對現有配準算法在復雜環境中配準正確率較低、配準時間較長的問題，提出融合GMS 與VCS+GC-RANSAC 的配準算法，經權威數據集以及現實所拍圖集的測試對比與驗證，說明了本文算法的魯棒性和高效性均有提高。但算法在大角度視角轉變環境下的一些配準仍存在欠缺，改進本文算法以期在復雜視角下的配準取得更好效果是下一步研究的方向。