基于網(wǎng)格的統(tǒng)計(jì)優(yōu)化特征匹配算法

趙春暉, 樊斌, 胡勁文, 張志遠(yuǎn), 潘泉

(西北工業(yè)大學(xué) 自動(dòng)化學(xué)院, 陜西 西安 710072)

圖像匹配是計(jì)算機(jī)視覺和數(shù)字圖像處理的基礎(chǔ)技術(shù)，廣泛應(yīng)用于圖像拼接[1]、目標(biāo)定位[2]、SLAM(simultaneous localization and mapping)[3]等領(lǐng)域?；谔卣鼽c(diǎn)的圖像匹配算法作為當(dāng)前圖像匹配技術(shù)的主流方向，得到了國(guó)內(nèi)外研究學(xué)者的廣泛關(guān)注，主要研究如何增加特征點(diǎn)之間的區(qū)分性。SIFT[4]、SURF(speeded up robust features)[5]、ORB(oriented FAST and rotated BRIEF)[6]、Harris角點(diǎn)[7]等經(jīng)典特征得以提出，相應(yīng)的關(guān)于特征描述子的改進(jìn)工作，如重新設(shè)計(jì)SIFT特征描述子[8-11]，改進(jìn)相似性度量方式[12-16]，使用CNN(convlutional neural networks)訓(xùn)練LIFT(learned invariant feature transform)描述子[17]等方法不斷被提出。以上這些對(duì)圖像特征的改進(jìn)手段在一定程度上能夠提高匹配的精度和速度，但由于傳統(tǒng)的特征匹配方法在區(qū)分正確和錯(cuò)誤匹配時(shí)過度依賴特征描述子，可能會(huì)導(dǎo)致許多正確匹配被不合理地拒絕，匹配召回率仍然不高。

對(duì)BF(brute force)[4,18]、FLANN(fast library for approximate nearest neighbors)[19]等經(jīng)典匹配方法展開研究，發(fā)現(xiàn)：BF匹配方法通過計(jì)算2幅圖像的特征點(diǎn)描述子之間的歐式距離，尋找最近鄰的特征點(diǎn)作為匹配對(duì)。由于特征點(diǎn)都是基于局部區(qū)域的特征，當(dāng)2幅圖像中存在重復(fù)紋理時(shí)，會(huì)很容易產(chǎn)生誤匹配。雖然BF匹配方法的匹配數(shù)目較多，但是誤匹配也較多，綜合匹配性能較差，如何合理地區(qū)分正確與錯(cuò)誤匹配成為了BF方法急需解決的問題。FLANN方法可以利用比率測(cè)試來驗(yàn)證候選匹配特征點(diǎn)對(duì)，以剔除虛假匹配，但是由于相似的外觀，比率測(cè)試會(huì)拒絕許多重復(fù)結(jié)構(gòu)的特征點(diǎn)，導(dǎo)致許多正確匹配的錯(cuò)誤拒絕，影響了匹配的召回率。RANSAC(random sample consensus)[20-23]也可以緩解這一問題，但RANSAC本身要求大多數(shù)誤匹配應(yīng)被預(yù)先排除，并且當(dāng)最近距離匹配集合中的誤匹配數(shù)量較多時(shí)會(huì)失效。針對(duì)RANSAC方法在剔除SIFT誤匹配點(diǎn)方面的不足，譚仁龍等[24]提出了一種基于主方向的SIFT誤匹配點(diǎn)剔除方法，利用特征點(diǎn)間的主方向夾角近似相等作為約束條件，提高了特征匹配的可靠性和準(zhǔn)確性。雷俊鋒等[11]將特征點(diǎn)周圍鄰域的主方向梯度作為特征之一，采用主方向梯度和歐式距離相結(jié)合的計(jì)算方法進(jìn)行特征點(diǎn)的匹配，提高了特征匹配效率。邊家旺等[25]在特征匹配中引入了運(yùn)動(dòng)平滑約束和鄰域匹配支持的思想，并在網(wǎng)格框架下加速ORB特征點(diǎn)匹配，使得特征匹配更加快速。此外，以互相關(guān)系數(shù)作為相似性度量準(zhǔn)則的特征匹配算法也被研究[14-16]，通過比較2幅圖像在各個(gè)位置的相關(guān)系數(shù)，得到相關(guān)值最大的點(diǎn)，即最佳匹配位置，提高了匹配準(zhǔn)確率。

為了在剔除錯(cuò)誤匹配的同時(shí)盡可能地保留更多的正確匹配，以克服特征匹配召回率較低的問題，提高特征匹配的綜合匹配性能。本文對(duì)特征點(diǎn)主方向和尺度的統(tǒng)計(jì)特性展開研究，并借鑒BF匹配方法的高召回率低準(zhǔn)確率的特點(diǎn)，采用網(wǎng)格手段，綜合利用SIFT特征點(diǎn)的主方向、尺度和位置等約束優(yōu)化特征匹配，提出了一種基于網(wǎng)格的統(tǒng)計(jì)優(yōu)化特征匹配算法。首先在目標(biāo)圖中尋找原圖中每個(gè)特征點(diǎn)的最近鄰(BF)匹配特征點(diǎn)，得到初匹配結(jié)果，其次利用匹配主方向差剔除初匹配中的大部分錯(cuò)誤匹配，然后基于匹配尺度比信息對(duì)匹配圖像劃分網(wǎng)格，統(tǒng)計(jì)匹配特征點(diǎn)的位置信息在網(wǎng)格間的分布情況，計(jì)算原圖中每個(gè)網(wǎng)格細(xì)胞的歸一化互相關(guān)系數(shù)以判斷該網(wǎng)格細(xì)胞的匹配是否正確，最終得到優(yōu)化后的特征匹配結(jié)果。

本文主要工作是：①研究了最近鄰匹配中匹配主方向差和匹配尺度比的統(tǒng)計(jì)特性。②提出了匹配主方向差約束、匹配尺度比約束和匹配位置約束，并將其引入特征匹配，克服了特征匹配召回率較低的問題。③基于匹配特征點(diǎn)的位置信息，利用歸一化互相關(guān)函數(shù)和網(wǎng)格法篩選出正確匹配。

1 算法說明

本文算法首先在目標(biāo)圖中尋找原圖特征點(diǎn)的最近鄰匹配，然后對(duì)匹配結(jié)果中匹配主方向差和匹配尺度比的統(tǒng)計(jì)特性展開研究，1.2節(jié)表明可以利用匹配主方向差約束剔除大量誤匹配，1.3節(jié)表明可以利用匹配尺度比約束為2個(gè)匹配特征點(diǎn)劃分小鄰域，以確保小鄰域?qū)?yīng)的3D信息基本相同，為本文算法中網(wǎng)格的劃分提供了依據(jù)，1.4節(jié)表明可以利用匹配位置約束進(jìn)一步地剔除誤匹配，從而盡可能地保留最近鄰匹配結(jié)果中的正確匹配，提高匹配召回率和綜合匹配性能。

1.1 定義與記號(hào)

由SIFT的定義[4]，假設(shè)某SIFT特征點(diǎn)的位置為(x,y),尺度為σ,如圖1a)所示。

圖1 SIFT特征參數(shù)及梯度方向直方圖

則該特征點(diǎn)所在的尺度圖像為

L(x,y)=G(x,y,σ)*I(x,y)

(1)

式中,I(x,y)是圖像區(qū)域,G(x,y,σ)是高斯核函數(shù),滿足:

(2)

計(jì)算以(x,y)為中心,以3×1.5σ為半徑的鄰域內(nèi)每個(gè)像素L(x,y)對(duì)應(yīng)梯度的幅值和幅角,公式如下:

(3)

利用梯度直方圖統(tǒng)計(jì)該鄰域內(nèi)所有像素的梯度分布特性,如圖1b)所示,橫軸是梯度幅角,縱軸是對(duì)應(yīng)的梯度幅值的累加值,然后通過對(duì)直方圖中主峰值和距離它最近的2個(gè)柱值進(jìn)行拋物線插值得到該特征點(diǎn)的主方向θ(0°≤θ≤360°)。如圖2所示,設(shè)原圖中的SIFT特征點(diǎn)的主方向?yàn)棣仍?，尺度為σ?目標(biāo)圖中匹配SIFT特征點(diǎn)的主方向?yàn)棣饶?尺度為σ目,記:

θ1=θ原

(4)

θ2=(θ原+180°)/360°

(5)

定義1匹配主方向差為2個(gè)主方向之間的夾角α,若目標(biāo)圖中匹配特征點(diǎn)的主方向位于區(qū)域A,則α>0;若目標(biāo)圖中匹配特征點(diǎn)的主方向位于區(qū)域B,則α<0。如圖2和(6)式、(7)式所示:

圖2 匹配主方向差的定義示意圖

① 當(dāng) 0°≤θ原<180°時(shí)，

(6)

② 當(dāng) 180°≤θ原<360°時(shí)，

(7)

定義2匹配尺度比為原圖中的特征點(diǎn)的尺度與目標(biāo)圖中匹配特征點(diǎn)尺度的比值。即:

(8)

因此匹配主方向差的范圍是-180°～180°,可以利用直方圖研究其在最近鄰匹配中的統(tǒng)計(jì)特性。

1.2 匹配主方向差約束

假設(shè)1:對(duì)于原圖中的某一個(gè)特征點(diǎn),若它匹配錯(cuò)誤,則它在目標(biāo)圖中對(duì)應(yīng)的匹配特征點(diǎn)的主方向可能處于任意方向。

采用TUM[26]的freiburg3數(shù)據(jù)集,進(jìn)行大量實(shí)驗(yàn)驗(yàn)證匹配主方向差的分布。當(dāng)匹配錯(cuò)誤時(shí),雖然2個(gè)匹配特征點(diǎn)最相似且都具有旋轉(zhuǎn)不變性,但由于重復(fù)紋理的影響,它們的主方向可能差別較大。

取數(shù)據(jù)集的第0幀與第10幀圖像,分別提取1 000個(gè)特征點(diǎn),用BF匹配方法進(jìn)行匹配,得到1 000個(gè)匹配對(duì),其中正確匹配數(shù)為686,錯(cuò)誤匹配數(shù)為314。正確匹配、錯(cuò)誤匹配和所有BF匹配結(jié)果的匹配主方向差的標(biāo)準(zhǔn)差分別為3.68,101.92和57.19,它們的匹配主方向差的分布直方圖分別如圖3所示。取數(shù)據(jù)集中第0幀圖像分別與第0,…,99幀圖像進(jìn)行匹配,得到匹配主方向差的標(biāo)準(zhǔn)差分布,如圖4所示。

圖3 匹配主方向差的分布直方圖

圖4 正確匹配的匹配主方向差的標(biāo)準(zhǔn)差分布情況

由圖3a)和圖4可知,正確匹配的匹配主方向差近似服從正態(tài)分布,標(biāo)準(zhǔn)差較小,分布較為集中。由圖3b)可知,錯(cuò)誤匹配的匹配主方向差近似服從均勻分布,標(biāo)準(zhǔn)差較大,分布較為發(fā)散。結(jié)合圖3c)可知,所有BF匹配的匹配主方向差的分布直方圖只有單峰,而且正確匹配恰好完全落在其中,這與假設(shè)1相對(duì)應(yīng)。因此,可以通過匹配主方向差優(yōu)化BF匹配結(jié)果,即:統(tǒng)計(jì)BF匹配的匹配主方向差的分布直方圖,選取對(duì)應(yīng)于最高峰和次高峰的匹配對(duì)作為初始匹配結(jié)果,這樣就可以剔除大量錯(cuò)誤匹配。

1.3 匹配尺度比約束

由圖5可知,正確匹配的匹配尺度比均值與目標(biāo)圖像的縮放倍數(shù)近似成反比,近似滿足Mtrue=1/λ,Mtrue為正確匹配的匹配尺度比的均值,λ為目標(biāo)圖像縮放倍數(shù);相比BF匹配的匹配尺度比的均值,經(jīng)過匹配主方向差優(yōu)化后的匹配尺度比的均值更加接近真實(shí)值。因此,對(duì)于正確匹配對(duì)應(yīng)的2個(gè)特征點(diǎn),可以利用匹配主方向差優(yōu)化后的匹配尺度比的均值對(duì)它們劃分小鄰域,以確保這2個(gè)小鄰域?qū)?yīng)的3D信息基本相同。即,對(duì)于原圖中某個(gè)特征點(diǎn),設(shè)它的鄰域半徑為r,若它匹配正確,則它在目標(biāo)圖中對(duì)應(yīng)的匹配特征點(diǎn)的鄰域半徑近似等于r/M,M為匹配主方向差優(yōu)化后的匹配尺度比的均值。

圖5 匹配尺度比的均值的分布情況

1.4 匹配位置約束

假設(shè)2:對(duì)于某匹配,若它匹配正確,則它的鄰域內(nèi)存在足夠多的匹配支持該匹配;若它匹配錯(cuò)誤,則它的鄰域內(nèi)存在較少或沒有匹配支持該匹配。

鄰域定義為匹配特征點(diǎn)周圍的小鄰域,如圖6中區(qū)域a、區(qū)域b所示。假設(shè)2成立是由于運(yùn)動(dòng)平滑,正確匹配對(duì)的鄰域?qū)?yīng)著相同的3D信息,從而在鄰域內(nèi)存在足夠多的相似特征,即存在足夠多的匹配支持;相反地,錯(cuò)誤匹配的鄰域?qū)?yīng)著不同的3D信息,從而在鄰域內(nèi)存在較少或不存在相似特征[25]。

圖6 匹配位置約束示意圖

2 基于網(wǎng)格的統(tǒng)計(jì)優(yōu)化特征匹配算法

基于以上的分析,本文使用基于互相關(guān)函數(shù)的網(wǎng)格法加速對(duì)匹配位置約束的求解。2.1節(jié)介紹了基于匹配尺度比的網(wǎng)格劃分,2.2節(jié)介紹了基于匹配特征點(diǎn)的位置信息,在網(wǎng)格框架下引入歸一化互相關(guān)函數(shù)篩選正確匹配的方法。算法概述如下：

輸入:原圖像Ia和目標(biāo)圖像Ib

輸出:Inliers

初始化:

1:分別提取SIFT特征點(diǎn)并計(jì)算描述子;

2:對(duì)Ia中的每個(gè)特征點(diǎn),在Ib中尋找最近鄰匹配,得到初匹配S0;

3:利用S0的匹配主方向差約束得到初始匹配集合S1;

4:將Ia劃分為G1個(gè)非重疊網(wǎng)格;

5:利用S1的匹配尺度比約束,將Ib劃分為G2個(gè)非重疊網(wǎng)格;

6:forL=1toG1do

7:R=1;

8: fori=1 toG2do

9: ifχLi>χLR, then

10:R=i;

11: end if

12: end for

13:計(jì)算S(L,R)NCC

14:ifS(L,R)NCC≥Tth, then

15:Inliers=Inliers∪χLR

16:end if

17:end for

迭代:

(1)將原圖中的網(wǎng)格分別沿x方向、y方向以及x和y方向平移半個(gè)網(wǎng)格細(xì)胞,重復(fù)步驟6～17;

(2)對(duì)于不同的G2,重復(fù)步驟5～17。

2.1 網(wǎng)格劃分

設(shè)匹配主方向差的分布直方圖的橫坐標(biāo)范圍是-180°～180°,其中每10°一個(gè)柱,總共36個(gè)柱。首先統(tǒng)計(jì)BF匹配的匹配主方向差的分布直方圖,選取對(duì)應(yīng)于最高峰和次高峰的匹配作為初始匹配集合S1。

圖7 網(wǎng)格細(xì)胞{L,R}的8個(gè)鄰域示意圖

2.2 基于互相關(guān)網(wǎng)格的匹配優(yōu)化

設(shè)2幅圖像間的正確匹配集合和錯(cuò)誤匹配集合分別為T和F。劃分網(wǎng)格后,基于S1統(tǒng)計(jì)網(wǎng)格細(xì)胞間的匹配數(shù)目{χ|χij≥0,i=1,…,G1,j=1,…,G2}。利用匹配位置約束的特點(diǎn),設(shè)原圖中某網(wǎng)格細(xì)胞L在目標(biāo)圖中對(duì)應(yīng)的網(wǎng)格細(xì)胞為R(如圖7所示),為考察網(wǎng)格細(xì)胞{L,R}的8個(gè)鄰域的匹配支持情況,定義{L,R}之間的互相關(guān)函數(shù)為

(9)

式中：Ai表示Li和Ri之間的匹配對(duì)數(shù)目；Bi表示Li與R′之間的匹配對(duì)數(shù)目；R′表示在目標(biāo)圖中與Li匹配數(shù)目最多的網(wǎng)格細(xì)胞。

因此,S(L,R)NCC越接近1,網(wǎng)格細(xì)胞{L,R}之間的匹配可信度越高。即:

(10)

3 實(shí)驗(yàn)及結(jié)果

本實(shí)驗(yàn)基于64位PC平臺(tái)的Ubuntu 14.04系統(tǒng)。實(shí)驗(yàn)選取TUM[26]和DTU[27]數(shù)據(jù)集中的圖像進(jìn)行測(cè)試,TUM 是視頻圖像序列,DTU包含旋轉(zhuǎn)、尺度、視角、亮度等不同圖像。實(shí)驗(yàn)圖像如圖8所示,第一、二行分別為原圖像和目標(biāo)圖像,圖像分辨率為640×480。

圖8 實(shí)驗(yàn)圖像

圖9 實(shí)驗(yàn)結(jié)果對(duì)比圖

實(shí)驗(yàn)序號(hào)ROBUST算法匹配數(shù)目準(zhǔn)確率/%召回率/%FLANN算法匹配數(shù)目準(zhǔn)確率/%召回率/%本文算法匹配數(shù)目準(zhǔn)確率/%召回率/%a63410074.168598.779.073198.183.8 b39899.761.645593.866.153296.079.1 c81009.521994.721.43390.935.7 d66199.866.972399.472.888798.688.6

圖10 3種算法的準(zhǔn)確率、召回率和F值對(duì)比圖

圖11 4組實(shí)驗(yàn)中準(zhǔn)確率、召回率和F值與網(wǎng)格大小的關(guān)系

實(shí)驗(yàn)序號(hào)SIFT特征提取ROBUSTFLANN本文算法a336.055404.824376.169384.507b323.137380.942346.533360.824c317.437380.929350.093350.213d358.387418.290385.041407.836

由圖9和表1可知,本文算法不僅在匹配準(zhǔn)確率上保持了與其他算法相當(dāng)?shù)聂敯粜?而且大大提高了匹配召回率。圖10中本文算法的F值優(yōu)于經(jīng)典的FLANN和ROBUST算法,結(jié)合表1可知本文算法的匹配召回率平均提高了10%以上,因此本文算法的綜合匹配性能更好。由圖11可知,匹配準(zhǔn)確率隨網(wǎng)格數(shù)量增大而增大,匹配召回率隨網(wǎng)格數(shù)量增大而減小,綜合來看網(wǎng)格大小為20×20時(shí)既能獲得較魯棒的準(zhǔn)確率和召回率,也能保證較高的計(jì)算效率。另外,由表2可知,本文算法計(jì)算量較大,耗時(shí)主要集中在SIFT特征提取部分(約334 ms),匹配部分耗時(shí)相對(duì)較少(約42 ms),可見本文的統(tǒng)計(jì)優(yōu)化思想可以快速地對(duì)基于SIFT特征點(diǎn)的最近鄰匹配結(jié)果進(jìn)行優(yōu)化。

4 結(jié) 論

本文提出一種基于網(wǎng)格的統(tǒng)計(jì)優(yōu)化特征匹配算法,給出了特征點(diǎn)匹配主方向差和尺度比約束,并在基于歸一化相關(guān)函數(shù)的網(wǎng)格框架下加速對(duì)匹配位置約束的求解,綜合利用SIFT特征的主方向、尺度和位置等信息優(yōu)化特征匹配。與經(jīng)典的FLANN和ROBUST匹配算法相比,本文方法顯著提高了匹配召回率,獲得了更好的綜合匹配性能。但是,因?yàn)楸疚姆椒ɑ趫D像中SIFT特征點(diǎn)之間的最近鄰匹配,而SIFT特征點(diǎn)的提取耗時(shí)較大,所以本文方法耗時(shí)較大。如何加快SIFT特征點(diǎn)間的匹配或?qū)⒈疚姆椒ǖ慕y(tǒng)計(jì)優(yōu)化思想用于基于ORB等特征點(diǎn)的圖像匹配將是接下來的研究目標(biāo)。