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

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

常見(jiàn)的圖片拼接方法有基于變換域的方法、基于灰度相關(guān)的方法、基于圖像特征點(diǎn)的方法[1-2]。由于特征點(diǎn)法對(duì)光照條件、旋轉(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)檢測(cè)與描述算法有效替代了傳統(tǒng)SIFT(Scale-Invariant Feature Transform)算法[5]，提升了特征點(diǎn)檢測(cè)的速度和魯棒性。在建立圖片之間的映射關(guān)系時(shí)，隨機(jī)抽樣一致性(RANdom SAmple Consensus, RANSAC)算法可以有效剔除誤匹配，但該方法在剔除少量誤配點(diǎn)的同時(shí)拋棄了大量正確的匹配點(diǎn)且速度慢，難以實(shí)現(xiàn)圖像的精確拼接和實(shí)時(shí)應(yīng)用。邢凱盛等[6]提出了通過(guò)縮小抽樣點(diǎn)總量來(lái)減少RANSAC算法迭代次數(shù)，提高運(yùn)算速度，但采用的線性規(guī)劃問(wèn)題可能存在沒(méi)有可行解的情況，導(dǎo)致去誤匹配不穩(wěn)定；王茜等[7]提出了加入自適應(yīng)閾值提高候選特征點(diǎn)的質(zhì)量，降低了RANSAC算法復(fù)雜度，但本質(zhì)上在剔除誤匹配方面的性能沒(méi)有改變。

為解決上述問(wèn)題，本文提出了一種基于運(yùn)動(dòng)平滑約束項(xiàng)和結(jié)構(gòu)相似度的分組排序采樣一致性圖像拼接算法。首先，采用ORB算法提取圖像中的特征點(diǎn)，利用漢明距離(Hamming Distance, HD)初始匹配特征點(diǎn)[8]，然后進(jìn)行改進(jìn)的運(yùn)動(dòng)平滑項(xiàng)約束誤匹配粗剔除，保證鄰域內(nèi)特征點(diǎn)的運(yùn)動(dòng)具有平滑性；再基于結(jié)構(gòu)相似度剔除頑固性誤匹配點(diǎn)，以此替代RANSAC算法，通過(guò)排序采樣求解單應(yīng)矩陣H，使用非線性最小化迭代算法(Levenberg-Marquardt, LM)逐步精煉變換矩陣H，并通過(guò)加權(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個(gè)像素為半徑的區(qū)域中Harris角點(diǎn)響應(yīng)值最大的D個(gè)特征點(diǎn):

(1)

(2)

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

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

(3)

(4)

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

θ=arctan(w01/w10)

(5)

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

(6)

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

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

(7)

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

(8)

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

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

(9)

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

1.2 特征點(diǎn)匹配

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

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

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

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

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

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

在圖1中，有匹配圖像Ia、模板圖像Ib，分別有N、M個(gè)特征點(diǎn)。形成圖像對(duì){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)表示一對(duì)特征點(diǎn)匹配對(duì)，當(dāng)區(qū)域a的范圍擴(kuò)大到整個(gè)匹配圖像Ia時(shí)，有|χ|≤N(N即為匹配圖片中Ia的特征點(diǎn)個(gè)數(shù))。

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

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

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

Si=|xi|-1

(10)

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

(11)

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

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

(12)

則fa匹配錯(cuò)誤的概率pf為：

β(1-t)(m/M)

(13)

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

(14)

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

(15)

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

(16)

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

(17)

(18)

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

(19)

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

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

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

亮度比較：

(20)

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

對(duì)比度比較：

(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 分組排序采樣

通過(guò)運(yùn)動(dòng)平滑約束項(xiàng)粗剔除和結(jié)構(gòu)相似度的精剔除后，匹配點(diǎn)具有了較高的可靠性。匹配點(diǎn)分組的目的是為了在求解單應(yīng)矩陣的過(guò)程中提高輸入?yún)?shù)的均勻性，防止輸入?yún)?shù)被局限在某一個(gè)特征點(diǎn)的局部。將經(jīng)過(guò)誤匹配剔除得到的匹配點(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ì)量的值遞增排序。排序完成后根據(jù)式(24)計(jì)算每組采樣的樣本集Si：

(24)

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

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

Mt=S1∪S2∪…∪Sk

(25)

(26)

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

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

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

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

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

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

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

3)以每個(gè)保留的區(qū)域匹配對(duì)中的特征點(diǎn)為中心建立15×15鄰域窗口，然后以窗口內(nèi)每個(gè)像素點(diǎn)建立7×7的子窗口，計(jì)算子窗口內(nèi)式(23)的值，再計(jì)算窗口內(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)拼接縫的自然過(guò)渡。

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

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

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

圖3 A組和B組原圖

4.1 主觀評(píng)價(jià)

由圖4的主觀視覺(jué)上可以看出，Hamming Distance初匹配提供了豐富的特征點(diǎn)匹配對(duì)，但誤匹配較多。文獻(xiàn)[6]去除誤匹配后還明顯存在大量誤匹配點(diǎn)，同時(shí)去除了大量正確匹配對(duì)。文獻(xiàn)[7]取得了一定效果但特征點(diǎn)分布不均。從圖4(d)可以看出，本文算法明顯剔除了大量誤匹配對(duì)，并極大地保留了正確匹配對(duì)，特征點(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 客觀評(píng)價(jià)

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

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

(27)

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

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

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

從表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ù)同時(shí)，有更高的誤匹配剔除率，其誤匹配剔除性能較文獻(xiàn)[6]算法提升了75.6%，較文獻(xiàn)[7]算法提升了24.0%。

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

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

圖6 三種算法誤匹配剔除性能對(duì)比

5 結(jié)語(yǔ)

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

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