丁 輝，李麗宏*，原 鋼

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

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

0 引言

圖像拼接和圖像配準是圖像處理中十分重要的部分。其中圖像配準是圖像拼接的基礎(chǔ)，也是圖像拼接最重要的一個環(huán)節(jié)。圖像配準在醫(yī)療衛(wèi)生［1］、機器人［2］、自動駕駛［3］、人臉識別［4］、圖像檢索［5］、目標跟蹤等領(lǐng)域都有廣泛的應(yīng)用。圖像配準大致可分為灰度分析和基于特征分析兩種方法［6-7］?；叶确治鲋饕且活愄囟０鍖δ繕藞D像基于灰度評價函數(shù)的滑動匹配，受光照、角度和尺度變換影響較大；而基于特征分析的配準方法由于對光照等魯棒性較好，現(xiàn)已成為該領(lǐng)域主流的分析方法。

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

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

1 網(wǎng)格運動統(tǒng)計

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

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

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

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

為了提高匹配速度，將標準圖與配準圖像網(wǎng)格化；同時，為了將正確匹配時特征點支持量與錯誤匹配時特征點支持量差距拉大，統(tǒng)計目標網(wǎng)格及其周圍8 個網(wǎng)格的特征點支持量作為目標網(wǎng)格區(qū)域某一特征匹配的支持量。因此，鄰域特征點支持量變?yōu)?

其中:K 代表與所在網(wǎng)格區(qū)域相鄰不相交的網(wǎng)格數(shù)。由式（7）可得Si標準差與均值:

根據(jù)Si的標準差與均值設(shè)定區(qū)分正確與錯誤匹配鄰域特征點支持量閾值:

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

對于一個網(wǎng)格區(qū)分正確與錯誤匹配鄰域特征點支持量閾值

其中:na表示9個網(wǎng)格中特征總數(shù)的平均值。

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

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

2 VCS+GC-RANSAC

2.1 圖割隨機抽樣一致性

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

傳統(tǒng)RANSAC主要算法步驟為:

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

2）計算模型相關(guān)參數(shù)；

3）計算所建立模型與所有點的距離，根據(jù)距離閾值將點集內(nèi)點分為內(nèi)點與野點；

4）保存內(nèi)點個數(shù)和模型對應(yīng)的基礎(chǔ)矩陣；

5）重復(fù)以上步驟，迭代k次得到k個模型及其對應(yīng)的內(nèi)點與基礎(chǔ)矩陣；

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

GC-RANSAC 主要對傳統(tǒng)RANSAC 算法的步驟3）（局部最優(yōu)）進行優(yōu)化改進，傳統(tǒng)RANSAC算法對于模型內(nèi)點和野點的區(qū)分僅僅依靠一個閾值，沒有考慮數(shù)據(jù)的空間結(jié)構(gòu)。傳統(tǒng)RANSAC根據(jù)式（12）區(qū)分內(nèi)野點:

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

GC-RANSAC 算法提出運用一元能量函數(shù)對內(nèi)野點區(qū)分進行改進:

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

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

將兩個能量函數(shù)結(jié)合成一個多項式，該多項式既考慮點對模型的匹配度又考慮空間結(jié)構(gòu)一致性，即

其中:λ是一個平衡參數(shù)。

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

2.2 VCS+GC-RANSAC原理

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

在圖像配準中，即使圖像經(jīng)過縮放、旋轉(zhuǎn)、平移，但其各個特征點與特定的穩(wěn)定特征點之間位置相對關(guān)系并不會有很大改變（穩(wěn)定特征點與各個特征點構(gòu)成一個整體），即由基向量運算得到的特征點矢量系數(shù)不會有太大的突變。

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

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

由式（20）可得:

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

合并其他項整理得:

同理可證:

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

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

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

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

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

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

3 實驗與結(jié)果分析

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

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

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

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

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

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

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

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

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

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

圖5 本文算法在現(xiàn)實所拍數(shù)據(jù)集上的配準效果Fig.5 Registration results of the proposed algorithm on real dataset

4 結(jié)語

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