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

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

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

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

1 ORB特征匹配算法

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

1.1 ORB特征描述與粗匹配

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

(1)

(2)

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

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

(3)

(4)

C表示特征點(diǎn)中心，根據(jù)式(3)、(4)可得特征點(diǎn)方向?yàn)椋?/p>

θ=arctan(w01/w10)

(5)

根據(jù)測試準(zhǔn)則式(6)構(gòu)造二進(jìn)制特征串：

(6)

其中：(xi,yi)表示特征點(diǎn)位于圖像中的坐標(biāo)。

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

(7)

設(shè)有n對位置坐標(biāo)(xi,yi)，構(gòu)造2×n方向信息矩陣：

(8)

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

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

(9)

經(jīng)過旋轉(zhuǎn)之后的BRIEF特征依然具有二進(jìn)制串特征。

1.2 特征點(diǎn)匹配

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

2 改進(jìn)的運(yùn)動平滑約束項(xiàng)誤匹配剔除

由于圖像視角、光照差異的變化，傳統(tǒng)的RANSAC等方法不能滿足高質(zhì)量和實(shí)時的圖像拼接。

本文借鑒PROSAC(PROgressive SAmple Consensus)方法[10]的思想，對運(yùn)動平滑約束項(xiàng)[11]誤匹配剔除進(jìn)行改進(jìn)：在每個不相重疊的網(wǎng)格區(qū)域內(nèi)，進(jìn)行運(yùn)動平滑約束項(xiàng)粗剔除，然后構(gòu)建結(jié)構(gòu)相似度函數(shù)[12]精剔除，得到穩(wěn)定的匹配點(diǎn)，再按照領(lǐng)域支持估計量進(jìn)行匹配點(diǎn)排序，并按順序進(jìn)行采樣，使得少量的分組擁有高比率的內(nèi)點(diǎn)。改進(jìn)的運(yùn)動平滑約束項(xiàng)誤匹配剔除算法提高了采樣的均勻性和準(zhǔn)確性，并對光線變化、旋轉(zhuǎn)圖像具有強(qiáng)魯棒性。

2.1 運(yùn)動平滑約束項(xiàng)的誤配粗剔除

運(yùn)動平滑約束項(xiàng)[11]的思想表述為：在一個區(qū)域的匹配對中，有足夠數(shù)量的鄰域特征點(diǎn)匹配對能夠被用來估計中心特征匹配點(diǎn)對的一致性運(yùn)動約束。

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

圖1 運(yùn)動平滑項(xiàng)約束示意圖

根據(jù)運(yùn)動平滑約束項(xiàng)的思想，在區(qū)域a中有足夠多的特征點(diǎn)與特征點(diǎn)Ni保持著相同的運(yùn)動，則匹配對xi是正確的匹配，反之匹配對xi匹配錯誤。

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

Si=|xi|-1

(10)

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

(11)

其中：m是區(qū)域b中特征點(diǎn)個數(shù)，M是模板圖像Ib中所有特征點(diǎn)個數(shù)，β是加權(quán)值。

圖2 特征點(diǎn)fa匹配過程的事件空間

(12)

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

β(1-t)(m/M)

(13)

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

(14)

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

(15)

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

(16)

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

(17)

(18)

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

(19)

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

2.2 空間幾何關(guān)系約束的誤配精剔除

通過運(yùn)動平滑約束項(xiàng)的誤配點(diǎn)剔除后，保留的特征點(diǎn)都是具有相似運(yùn)動的網(wǎng)格區(qū)域塊，其鄰域結(jié)構(gòu)非常相似，為了降低光照不均勻?qū)λ惴ǖ挠绊懀瑸榇死媒Y(jié)構(gòu)相似度[12]進(jìn)行改進(jìn)：構(gòu)建結(jié)構(gòu)相似度函數(shù)作進(jìn)一步核驗(yàn)，剔除頑固性誤匹配點(diǎn)，通過以下三個方面比較特征點(diǎn)鄰域相似程度。

亮度比較：

(20)

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

對比度比較：

(21)

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

結(jié)構(gòu)比較：

(22)

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

由式(20)、(21)、(22)可表示兩特征點(diǎn)鄰域的結(jié)構(gòu)相似度為：

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

(23)

c1、c2、c3為常數(shù)，k1、k2是非常小的常數(shù)。

2.3 分組排序采樣

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

(24)

其中：|Si|表示Si中樣本點(diǎn)個數(shù)，|Ji|表示Ji中匹配點(diǎn)的數(shù)量。

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

Mt=S1∪S2∪…∪Sk

(25)

(26)

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

2.4 時間復(fù)雜度分析

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

3 改進(jìn)的誤匹配剔除算法流程

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

1)在網(wǎng)格區(qū)域中，根據(jù)式(16)中χij的定義，計算Ia中第i個網(wǎng)格區(qū)域到模板圖像Ib第j個區(qū)域中的χij，當(dāng)其最大時，存儲{i,j}得到匹配區(qū)域?qū)Α?/p>

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

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

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

5)基于單應(yīng)矩陣H進(jìn)行圖像拼接。采用加權(quán)平均[14]融合的方法，實(shí)現(xiàn)拼接縫的自然過渡。

4 實(shí)驗(yàn)與分析

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

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

圖3 A組和B組原圖

4.1 主觀評價

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

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

4.2 客觀評價

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

CMR=內(nèi)點(diǎn)數(shù)/初始匹配數(shù)

(27)

式(27)中初始匹配數(shù)指的是經(jīng)過漢明距離初始匹配后的特征點(diǎn)個數(shù)，內(nèi)點(diǎn)數(shù)是在初始匹配數(shù)的基礎(chǔ)上進(jìn)一步進(jìn)行誤匹配剔除后所保留的特征點(diǎn)個數(shù)，CMR越大表示剔除誤匹配能力越強(qiáng)。

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

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

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

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

表1 不同算法誤匹配剔除結(jié)果對比

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

5 結(jié)語

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

[16] 單小軍,唐娉,鄭柯.GSSAC:一種用于遙感影像配準(zhǔn)的誤匹配點(diǎn)檢測方法[J].計算機(jī)應(yīng)用研究,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.)