基于運動平滑約束項的快速誤匹配剔除算法

李 為，李為相，張 璠，揭 偉

(南京工業大學 電氣工程與控制科學學院，南京 211800)

常見的圖片拼接方法有基于變換域的方法、基于灰度相關的方法、基于圖像特征點的方法[1-2]。由于特征點法對光照條件、旋轉等變化呈現出很強的魯棒性，具有更高的可靠性，是目前圖片拼接的主流方向[3]。2011年提出的ORB(Oriented FAST (Features from Accelerated Segment Test) and Rotated BRIEF (Binary Robust Independent Elmentary Features))[4]特征點檢測與描述算法有效替代了傳統SIFT(Scale-Invariant Feature Transform)算法[5]，提升了特征點檢測的速度和魯棒性。在建立圖片之間的映射關系時，隨機抽樣一致性(RANdom SAmple Consensus, RANSAC)算法可以有效剔除誤匹配，但該方法在剔除少量誤配點的同時拋棄了大量正確的匹配點且速度慢，難以實現圖像的精確拼接和實時應用。邢凱盛等[6]提出了通過縮小抽樣點總量來減少RANSAC算法迭代次數，提高運算速度，但采用的線性規劃問題可能存在沒有可行解的情況，導致去誤匹配不穩定；王茜等[7]提出了加入自適應閾值提高候選特征點的質量，降低了RANSAC算法復雜度，但本質上在剔除誤匹配方面的性能沒有改變。

為解決上述問題，本文提出了一種基于運動平滑約束項和結構相似度的分組排序采樣一致性圖像拼接算法。首先，采用ORB算法提取圖像中的特征點，利用漢明距離(Hamming Distance, HD)初始匹配特征點[8]，然后進行改進的運動平滑項約束誤匹配粗剔除，保證鄰域內特征點的運動具有平滑性；再基于結構相似度剔除頑固性誤匹配點，以此替代RANSAC算法，通過排序采樣求解單應矩陣H，使用非線性最小化迭代算法(Levenberg-Marquardt, LM)逐步精煉變換矩陣H，并通過加權平均融合算法融合圖像。實驗表明，去誤匹配性能有較大提高：拼接后，主觀上拼接處細節清晰，拼接縫明顯消除；客觀上，算法保持了較高的運行效率。

1 ORB特征匹配算法

ORB是一種快速特征點提取和描述的算法，特征提取采用FAST(Features from Accelerated Segment Test)算法，特征點描述采用改進的BRIEF(Binary Robust Independent Elmentary Features)算法[9]。

1.1 ORB特征描述與粗匹配

利用式(1)選取以候選特征點為中心、9個像素為半徑的區域中Harris角點響應值最大的D個特征點:

(1)

(2)

其中：o為角點檢測區域的圓周中心，即候選特征點；L(x)為待檢測點周圍內可選隨機像素點的灰度值；L(o)表示待檢測點的灰度值；εd為閾值；D為最終符合條件的像素個數。利用式(2)角點響應函數來判定FAST特征點。

通過式(3)計算局部區域矩估計，用以建立主方向：

(3)

(4)

C表示特征點中心，根據式(3)、(4)可得特征點方向為：

θ=arctan(w01/w10)

(5)

根據測試準則式(6)構造二進制特征串：

(6)

其中：(xi,yi)表示特征點位于圖像中的坐標。

對n個角點位置(x,y)進行灰度差異二值化運算：

(7)

設有n對位置坐標(xi,yi)，構造2×n方向信息矩陣：

(8)

對每一個測試點對，使用特征點方向θ和對應的旋轉矩陣Rn構造旋轉之后的二值像素測試位置，其描述子可用式(9)表示：

gn(Q,θ)=Ln(Q)|{xi,yi}∈Tθ

(9)

經過旋轉之后的BRIEF特征依然具有二進制串特征。

1.2 特征點匹配

本文通過HD的大小來表示特征點之間的相似度，當特征點描述子的相似度小于一定閾值的時候，表示這兩個特征點相匹配。

2 改進的運動平滑約束項誤匹配剔除

由于圖像視角、光照差異的變化，傳統的RANSAC等方法不能滿足高質量和實時的圖像拼接。

本文借鑒PROSAC(PROgressive SAmple Consensus)方法[10]的思想，對運動平滑約束項[11]誤匹配剔除進行改進：在每個不相重疊的網格區域內，進行運動平滑約束項粗剔除，然后構建結構相似度函數[12]精剔除，得到穩定的匹配點，再按照領域支持估計量進行匹配點排序，并按順序進行采樣，使得少量的分組擁有高比率的內點。改進的運動平滑約束項誤匹配剔除算法提高了采樣的均勻性和準確性，并對光線變化、旋轉圖像具有強魯棒性。

2.1 運動平滑約束項的誤配粗剔除

運動平滑約束項[11]的思想表述為：在一個區域的匹配對中，有足夠數量的鄰域特征點匹配對能夠被用來估計中心特征匹配點對的一致性運動約束。

在圖1中，有匹配圖像Ia、模板圖像Ib，分別有N、M個特征點。形成圖像對{Ia,Ib}，特征點集合{N,M}。在匹配圖像Ia中有一特征點Ni匹配到模板圖像Ib中的Mi,a、b區域分別表示Ni和Mi的鄰域，則有從a區域匹配到b區域的特征點集合χ={x1,x2,…,xN}，其中xi=(Ni,Mi)表示一對特征點匹配對，當區域a的范圍擴大到整個匹配圖像Ia時，有|χ|≤N(N即為匹配圖片中Ia的特征點個數)。

圖1 運動平滑項約束示意圖

根據運動平滑約束項的思想，在區域a中有足夠多的特征點與特征點Ni保持著相同的運動，則匹配對xi是正確的匹配，反之匹配對xi匹配錯誤。

將圖片分為k個區域，用Si表示的xi鄰域支持估計量：

Si=|xi|-1

(10)

其中：-1表示去除Ia中的原始特征點Ni。圖1中Si=2,Sj=0。

(11)

其中：m是區域b中特征點個數，M是模板圖像Ib中所有特征點個數，β是加權值。

圖2 特征點fa匹配過程的事件空間

(12)

則fa匹配錯誤的概率pf為：

β(1-t)(m/M)

(13)

根據式(12)、(13)可以得出的Si近似分布和xi的二項分布之間的關系如式(14)所示：

(14)

為了讓誤匹配剔除具有更快的速度，把圖像分成G=g×g個互不重疊的網格區域，每個網格區域的k鄰域也是單個網格區域，根據式(10)可得匹配區域間的鄰域支持估計量Sij為：

(15)

對圖像進行網格區域分割后，{i,j}表示兩個匹配的網格區域，i表示Ia中第i個網格區域，j表示Ib中第j個網格區域，χij表示{i,j}的鄰域支持估計量，χikjk表示在匹配區域對{i,j}第k個鄰域內的支持估計量，本文選擇區域匹配對{i,j}的9鄰域(即k=9)模式，計算區域匹配對的鄰域支持估計量，則根據式(14)有sij與{i,j}二項分布的關系：

(16)

根據式(14)有sij的均值和方差為：

(17)

(18)

區域匹配對{i,j}隨著特征點的變化符合不同的二項分布，通過合理的閾值τ可以將匹配錯誤的區域匹配對{i,j}有效剔除，隨著sij的增大，區域匹配對{i,j}匹配正確的可能性逐步增大，使得本文中通過sij的大小對網格區域進行排序，得到可靠的內點范圍并降低特征點數量的方法得以實現。根據可靠的閾值τ可得區域匹配對{i,j}的二值化表達式：

(19)

其中α為權重值。將鄰域支持估計量小于閾值的網格區域匹配對剔除后，保留下來的網格區域匹配塊中包含大量可信度很高的特征匹配點，為采樣提供了可靠的特征匹配對。

2.2 空間幾何關系約束的誤配精剔除

通過運動平滑約束項的誤配點剔除后，保留的特征點都是具有相似運動的網格區域塊，其鄰域結構非常相似，為了降低光照不均勻對算法的影響，為此利用結構相似度[12]進行改進：構建結構相似度函數作進一步核驗，剔除頑固性誤匹配點，通過以下三個方面比較特征點鄰域相似程度。

亮度比較：

(20)

其中：μx,μy分別表示兩幅圖像的灰度均值，c1=(k1L)2。

對比度比較：

(21)

其中:σx、σy分別表示兩幅圖像的灰度方差，c2=(k2L)2。

結構比較：

(22)

其中:σxy表示兩幅圖像的灰度協方差，c3=c2/2。

由式(20)、(21)、(22)可表示兩特征點鄰域的結構相似度為：

SSIM(x,y)=l(x,y)·c(x,y)·s(x,y)

(23)

c1、c2、c3為常數，k1、k2是非常小的常數。

2.3 分組排序采樣

通過運動平滑約束項粗剔除和結構相似度的精剔除后，匹配點具有了較高的可靠性。匹配點分組的目的是為了在求解單應矩陣的過程中提高輸入參數的均勻性，防止輸入參數被局限在某一個特征點的局部。將經過誤匹配剔除得到的匹配點cell-pair{i,j}記為Pn，將Pn分成J組，記為Ji(i=1,2,…,J,J≤m)，m是求單應矩陣所需最少匹配點數量，匹配點分組后，根據鄰域支持估計量的值遞增排序。排序完成后根據式(24)計算每組采樣的樣本集Si：

(24)

其中：|Si|表示Si中樣本點個數，|Ji|表示Ji中匹配點的數量。

然后，根據計算出來的|Si|和迭代次數進行采樣，第t次迭代的樣本集Mt如式(25)所示:

Mt=S1∪S2∪…∪Sk

(25)

(26)

其中：Rit-1表示從Ji的前t-1個匹配點中隨機選擇|Si|-1個匹配底點；ct表示Ji中的第t個匹配點；Rit1表示從Ji的前t個匹配點中隨機選擇1匹配點。

2.4 時間復雜度分析

使用RANSAC算法實現誤匹配剔除的時間復雜度為O(N)，其中N為匹配圖像Ia的特征點個數。由于圖像Ib中的特征點都要與圖像Ia中每一個特征點進行迭代運算，以此找到包含內點數最多的單應矩陣H，導致時間復雜度較高。本文算法通過建立網格區域，建立相似運動塊，誤匹配剔除時，只需要將圖像Ib中的相似運動塊與圖像Ia中對應的網格區域進行鄰域支持估計量的統計，不需要與Ia中的網格區域逐一對比，使得時間復雜度降為O(1)，實現誤匹配的快速準確剔除。

3 改進的誤匹配剔除算法流程

本文中將匹配圖像和模板圖像分別劃分成G=20×20互不重疊的網格區域。

1)在網格區域中，根據式(16)中χij的定義，計算Ia中第i個網格區域到模板圖像Ib第j個區域中的χij，當其最大時，存儲{i,j}得到匹配區域對。

2)計算匹配區域對{i,j}的9鄰域內具有平滑運動的特征點個數χikjk，根據式(17)計算sij，并按照其大小遞增排序，剔除sij>τ的區域匹配對。

3)以每個保留的區域匹配對中的特征點為中心建立15×15鄰域窗口，然后以窗口內每個像素點建立7×7的子窗口，計算子窗口內式(23)的值，再計算窗口內所有像素SSIM值的平均值作為特征點的結構相似度,剔除結構相似度小于閾值T的點。

4)按sij的順序采樣，建立單應矩陣H，使用非線性最小化迭代算法(LM)[13]逐步精煉矩陣H。

5)基于單應矩陣H進行圖像拼接。采用加權平均[14]融合的方法，實現拼接縫的自然過渡。

4 實驗與分析

本文在處理器為Inter Core i5-4210U CPU 1.70 GHz 2.40 GHz,內存為4.00 GB，顯卡為NVIDA GeForce 820M配置下的計算機上，編程環境為Visual Studio 2013,并加入了開源庫OpenCV 3.0，完成誤匹配點剔除與圖像拼接實驗。

為了驗證本文算法的性能在不同場景下的剔除誤匹配點的有效性，選取2組[15]不同特點的圖像進行仿真實驗。圖3中A組圖像建筑結構具有相似性的局部特征，且建筑旋轉角度較大；圖3中B組圖像具有視角的變化，建筑在視角的變化發生了旋轉。在粗剔除時，根據文獻[11]，計算特征點鄰域支持估計量時，窗口經驗值為G=20×20，閾值τ是基于權重α的sij均值和方差的和，取α=6；在精匹配時，當式(23)的分母為零時，結構相似度不穩定，一般取k1=0.01,k2=0.03,L=255時較穩定，結構相似度閾值T一般取0.6≤T<1，本文選取T=0.7與文獻[12]保持一致。

圖3 A組和B組原圖

4.1 主觀評價

由圖4的主觀視覺上可以看出，Hamming Distance初匹配提供了豐富的特征點匹配對，但誤匹配較多。文獻[6]去除誤匹配后還明顯存在大量誤匹配點，同時去除了大量正確匹配對。文獻[7]取得了一定效果但特征點分布不均。從圖4(d)可以看出，本文算法明顯剔除了大量誤匹配對，并極大地保留了正確匹配對，特征點分布更加均勻。

在圖像拼接方面，從圖5(a)可以看出，文獻[6]的拼接結果還明顯存在鬼影現象且拼接縫明顯存在，在圖5(b)中，文獻[7]的拼接結果不夠精確，建筑物存在明顯畸形。從圖5(d)可以看出，本文算法有效去除了鬼影進而拼接縫，實現了圖像的高質量拼接。因此本文算法剔除誤匹配能力和拼接質量的主觀效果好于文獻[6]和文獻[7]。

4.2 客觀評價

為進一步驗證本文算法的有效性，本文用匹配正確率CMR(Correct Matching Rate)[16]和圖像拼接過程中各步驟所用時間等圖像質量評價指標對各種算法的誤匹配剔除和圖像拼接質量進行定量分析，各評價指標數據如表1所示，表1中t1表示誤匹配剔除所用時間，t2表示從特征提取到拼接過程所用總時間。

CMR=內點數/初始匹配數

(27)

式(27)中初始匹配數指的是經過漢明距離初始匹配后的特征點個數，內點數是在初始匹配數的基礎上進一步進行誤匹配剔除后所保留的特征點個數，CMR越大表示剔除誤匹配能力越強。

圖4 A組和B組圖片的誤匹配剔除效果對比

圖5 三種算法對A組和B組圖像拼接效果對比

從表1中的CMR指標數據上可以看出，本文算法匹配正確率明顯高于文獻[6]算法和文獻[7]算法，從圖6(a)看出文獻[6]算法、文獻[7]算法和本文算法誤匹配剔除率分別為0.07、0.59、0.83，文獻[7]算法加入自適應閾值后誤匹配剔除率有明顯改善，剔除誤匹配能力加強，但從表1中看出文獻[7]初始匹配數較文獻[6]和本文算法明顯偏少，不能為拼接模型提供均勻可靠的特征點，本文算法在與文獻[6]算法保持同等程度的初始匹配數同時，有更高的誤匹配剔除率，其誤匹配剔除性能較文獻[6]算法提升了75.6%，較文獻[7]算法提升了24.0%。

在運行時間上，從圖6(b)看出：文獻[6]算法減少了初始樣本點數獲得了極快的速度，但同時拋棄了大量正確匹配對，降低了拼接精度；文獻[7]在誤匹配剔除階段計算開銷較大。從表1看出，本文算法在提升誤匹配剔除率與拼接精度的同時保證其拼接時間較文獻[6]和文獻[7]最短，因此本文算法在快速圖像配準的基礎上實現了圖像的精確拼接。

表1 不同算法誤匹配剔除結果對比

圖6 三種算法誤匹配剔除性能對比

5 結語

本文針對RANSAC算法去除誤匹配點的缺陷，提出了基于運動平滑約束項和結構相似度的分組排序采樣一致性的去誤匹配算法。實驗結果表明，本文實現了將高數量特征點的圖像匹配轉化為了高質量特征點的圖像匹配，并利用加權平均算法，完成了重疊區域的平滑過渡，過渡區域細節保存完整。由于本文去誤匹配算法需大量特征點，使得重疊區域較少時去誤匹配效果欠佳且圖像融合運算時間成本較高，所以尋求重疊區域較少的圖像融合方法，仍是今后進一步研究的方向。

[16] 單小軍,唐娉,鄭柯.GSSAC:一種用于遙感影像配準的誤匹配點檢測方法[J].計算機應用研究,2016,33(5):1562-1565.(SHAN X J, TANG P, ZHENG K. GSSAC: false matching points detection method for remote sensing images [J]. Application Research of Computers, 2016, 33(5): 1562-1565.)