基于改進(jìn)網(wǎng)格劃分統(tǒng)計(jì)的特征點(diǎn)快速匹配方法

陳方杰，韓 軍， 王祖武

(1.上海大學(xué) 通信與信息工程學(xué)院，上海 200444；2.上海先進(jìn)通信與數(shù)據(jù)科學(xué)研究院，上海 200444)

0 引言

圖像特征匹配是計(jì)算機(jī)視覺領(lǐng)域中基礎(chǔ)又重要的研究課題，其廣泛應(yīng)用于視覺SLAM，圖像拼接和三維重建等領(lǐng)域[1]?；谔卣鞯钠ヅ洳呗砸话闶峭ㄟ^尋找兩幅圖像之間的局部映射關(guān)系來完成，主要包括點(diǎn)匹配[2]，線匹配[3]和區(qū)域匹配[4]等。由于特征點(diǎn)更易提取，匹配方式靈活，所以基于特征點(diǎn)的匹配算法在圖像特征匹配中被普遍采用?；谔卣鼽c(diǎn)的匹配算法有兩種：特征描述子相似約束和幾何約束。

對(duì)于特征描述子相似約束，其實(shí)是使用特征點(diǎn)周圍的信息作為描述特征，通過優(yōu)化描述特征，提高匹配精度和匹配速度。SIFT(scale invariant feature transform)算法[5]在關(guān)鍵點(diǎn)鄰域計(jì)算局部梯度，生成的描述子具有較好的尺度不變性和旋轉(zhuǎn)不變性，但計(jì)算耗時(shí)較久，匹配描述子的計(jì)算量很大，實(shí)時(shí)性較低。文獻(xiàn)[6]對(duì)SIFT算法進(jìn)行改進(jìn)，提出SURF(speed-up robust features)算法，其采用Hessian矩陣和積分圖加快計(jì)算，但當(dāng)圖像間視角變換過大時(shí)，提取的特征點(diǎn)沒有SIFT穩(wěn)定，而且仍達(dá)不到實(shí)時(shí)性要求。Rublee等人[7]提出ORB(ORiented Brief)算法，其先利用改進(jìn)的FAST (features from accelerated segment test)[8]算法檢測特征點(diǎn)，再利用改進(jìn)的BRIEF(binary robust independent elementary features)[9]算法計(jì)算特征點(diǎn)描述子，極大地提高了特征點(diǎn)檢測和匹配速度。LIFT算法[10]利用卷積神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)圖像特征點(diǎn)檢測、方向估計(jì)和特征描述符提取。其通過三步訓(xùn)練，可以比SIFT算法得到更多的正確特征點(diǎn)匹配對(duì)，對(duì)光照和季節(jié)性變化的圖像具有更強(qiáng)的魯棒性，但在訓(xùn)練過程中容易出現(xiàn)過擬合，而且對(duì)數(shù)據(jù)集依賴較大。

對(duì)于幾何約束，傳統(tǒng)的特征點(diǎn)匹配方法先使用NNDR (nearest neighbour distance ratio)算法[11]進(jìn)行特征點(diǎn)匹配，再利用RANSAC (random sample consensus)算法[12]剔除錯(cuò)誤匹配。RANSAC算法是從包含錯(cuò)誤匹配的特征點(diǎn)匹配點(diǎn)集中，通過迭代方式估計(jì)數(shù)學(xué)模型參數(shù)的方法。其魯棒性較好，但準(zhǔn)確率會(huì)隨著錯(cuò)誤匹配的比例增大而降低，增大迭代次數(shù)可以提高一定的準(zhǔn)確率，但運(yùn)算時(shí)間也會(huì)增加，實(shí)時(shí)性較低。為了提供特征點(diǎn)匹配的效率和精度，Yuille等人[13]提出VFC (vector field consensus)算法，其使用公認(rèn)集和幾何約束來建立對(duì)應(yīng)點(diǎn)，通過內(nèi)插兩個(gè)點(diǎn)集之間的矢量場來求解對(duì)應(yīng)關(guān)系，然后使用Tikhonov正則化器計(jì)算圖像的Hilbert空間。在此基礎(chǔ)上，利用EM算法計(jì)算所提取的貝葉斯模型方差，最后與預(yù)期值對(duì)比，剔除錯(cuò)誤特征匹配點(diǎn)對(duì)。Bian等人[14]提出GMS (grid-based motion statistics)算法，其將運(yùn)動(dòng)平滑度轉(zhuǎn)換為區(qū)域?qū)χg具有一定數(shù)量特征匹配的統(tǒng)計(jì)似然性。GMS算法提出九宮格劃分法，較大地提高了特征點(diǎn)匹配速度，實(shí)時(shí)性較高。但該算法存在兩個(gè)問題，第一個(gè)問題是當(dāng)圖像間旋轉(zhuǎn)角度較小，甚至無旋轉(zhuǎn)角度時(shí)，特征點(diǎn)匹配的準(zhǔn)確率最高，但大多數(shù)成對(duì)的圖像都會(huì)存在一定的旋轉(zhuǎn)關(guān)系。該算法的解決方法是根據(jù)九宮格形狀，計(jì)算8次不同狀態(tài)下最大的九宮格特征分?jǐn)?shù)，即增加額外7次旋轉(zhuǎn)統(tǒng)計(jì)操作，此方法一定程度上解決了旋轉(zhuǎn)關(guān)系問題，但相應(yīng)增加了額外計(jì)算量。第二個(gè)問題是對(duì)于任何圖像，GMS算法都是根據(jù)設(shè)定好的經(jīng)驗(yàn)值來固定網(wǎng)格的劃分?jǐn)?shù)量，而且一般設(shè)定成橫向網(wǎng)格數(shù)量與縱向網(wǎng)格數(shù)量相同。這種劃分方法對(duì)于長寬比不一致的圖像，其劃分的網(wǎng)格呈矩形狀，會(huì)使得在旋轉(zhuǎn)統(tǒng)計(jì)操作時(shí)，網(wǎng)格中的特征點(diǎn)可能出現(xiàn)分布不均等問題。

基于上述分析，本文針對(duì)幾何約束的GMS算法所存在的問題進(jìn)行優(yōu)化，提出一種改進(jìn)網(wǎng)格劃分統(tǒng)計(jì)的特征點(diǎn)快速匹配算法。本文主要的創(chuàng)新點(diǎn)是：1)改進(jìn)網(wǎng)格統(tǒng)計(jì)方法，提出一種五宮格統(tǒng)計(jì)法，保證結(jié)構(gòu)對(duì)稱性的同時(shí)，減少了旋轉(zhuǎn)次數(shù)，減少了計(jì)算量；2)改進(jìn)網(wǎng)格劃分方法，提出一種方形狀網(wǎng)格劃分法，將輸入圖像的長寬比作為約束項(xiàng)，確保劃分后的網(wǎng)格形狀不受輸入圖像的形狀影響。

1 GMS算法

1.1 運(yùn)動(dòng)平滑

GMS算法本質(zhì)上是匹配統(tǒng)計(jì)約束模型。對(duì)于從不同角度拍攝同一場景的成對(duì)圖像，特征點(diǎn)匹配表示一幅圖像上的特征點(diǎn)在另一幅圖像上是一致的。如果場景中的物體發(fā)生移動(dòng)，那么特征點(diǎn)相鄰的像素和特征也將一塊移動(dòng)。運(yùn)動(dòng)平滑保證正確匹配的鄰域看到相同的區(qū)域，而錯(cuò)誤匹配的鄰域看到不同的區(qū)域。從特征點(diǎn)的角度來看，在兩幅圖像上正確匹配特征點(diǎn)的鄰域中會(huì)存在一些匹配特征點(diǎn)，而錯(cuò)誤匹配特征點(diǎn)的鄰域是不同的，所以錯(cuò)誤匹配鄰域中正確匹配的數(shù)量基本為零。

將{F1,F2}記為輸入圖像{I1,I2}的初始匹配點(diǎn)集，假設(shè)一共有N組匹配點(diǎn)對(duì)，所以其中F1={f1,1,f1,2,...,f1,N}和F2={f2,1,f2,2,...,f2,N}。

令{N1,N2}表示為{F1,F2}匹配點(diǎn)集的鄰域，即N1={N1,1,N1,2,...,N1,N},N2={N2,1,N2,2,...,N2,N}。針對(duì){f1,i,f2,i}粗匹配特征點(diǎn)對(duì)，計(jì)算在N1,i中的粗匹配特征點(diǎn)集{f1,i,1,f1,i,2,...,f1,i,Wi}和粗匹配特征點(diǎn)數(shù)量Wi。然后統(tǒng)計(jì)上述特征點(diǎn)初始匹配的特征點(diǎn)集{f2,i,1,f2,i,2,...,f2,i,Wi}和{f2,i,1,f2,i,2,...,f2,i,Wi}位于N2,i中的數(shù)量，記為特征鄰域分?jǐn)?shù)Si。其中令si,k表示N1,i中第k個(gè)特征點(diǎn)粗匹配對(duì)應(yīng)的特征點(diǎn)是否位于N2,i的標(biāo)志分?jǐn)?shù)，若位于N2,i中，計(jì)分為1，反之不計(jì)分。最后根據(jù)分?jǐn)?shù)閾值T來判定第i組粗匹配特征點(diǎn)對(duì){f1,i,f2,i}是正確匹配還是錯(cuò)誤匹配。

部分潮汕美食和傳統(tǒng)節(jié)日相關(guān)文化負(fù)載詞的翻譯譯者采用音譯（潮汕方言），同時(shí)考慮到讀者的認(rèn)知能力，為使其無須付出不必要的努力，而獲得充分的語境效果，所以在音譯后面添加文本注釋，既保留文化的差異性，又能幫助譯文讀者花較少的努力，獲得較大的語境效果。音譯加上文本注釋可以看作是跨文化傳播策略初期的一種嘗試，甚至可以培養(yǎng)語境，慢慢消除“意義真空”。

(1)

(2)

1.2 九宮格統(tǒng)計(jì)法

為了提高特征鄰域分?jǐn)?shù)的計(jì)算速度，GMS算法將輸入圖像進(jìn)行網(wǎng)格劃分，生成G=P×Q個(gè)網(wǎng)格，其中P表示縱向網(wǎng)格數(shù)量，Q表示橫向網(wǎng)格數(shù)量，即將鄰域統(tǒng)計(jì)問題轉(zhuǎn)化為網(wǎng)格統(tǒng)計(jì)問題，如圖1所示。在統(tǒng)計(jì)特征點(diǎn)所在網(wǎng)格的特征分?jǐn)?shù)的同時(shí)，統(tǒng)計(jì)環(huán)繞其四周相鄰的8個(gè)網(wǎng)格的特征分?jǐn)?shù)，其中Si,j表示第i個(gè)網(wǎng)格所在的九宮格中第j個(gè)網(wǎng)格特征分?jǐn)?shù)。九宮格如圖2所示，其中G1,5表示I1中一個(gè)特征點(diǎn)所在的網(wǎng)格，G1,1,G1,2…,G1,9表示G1,5相鄰對(duì)稱的8個(gè)網(wǎng)格。GMS算法將此方法的特征鄰域分?jǐn)?shù)之和稱為九宮格特征分?jǐn)?shù)S，公式如下：

(3)

圖1 網(wǎng)格劃分和九宮格網(wǎng)格鄰域

(4)

(5)

(6)

(7)

其中:α為權(quán)重稀疏系數(shù)，一般設(shè)置為6。

圖2 九宮格示意圖

圖3 九宮格旋轉(zhuǎn)示意圖

2 改進(jìn)的五宮格劃分統(tǒng)計(jì)

2.1 五宮格統(tǒng)計(jì)法

對(duì)特征點(diǎn)所在的網(wǎng)格需要計(jì)算8個(gè)額外相鄰網(wǎng)格的特征分?jǐn)?shù)，這種統(tǒng)計(jì)方法會(huì)增加不必要的計(jì)算量。根據(jù)觀察，本文針對(duì)網(wǎng)格分布的對(duì)稱性，旨在保持魯棒性的前提下，只統(tǒng)計(jì)與當(dāng)前網(wǎng)格相鄰且對(duì)稱的4個(gè)網(wǎng)格特征分?jǐn)?shù)，分布情況如圖4所示。將此方法的特征鄰域分?jǐn)?shù)之和稱為五宮格特征分?jǐn)?shù)S，計(jì)算公式如下：

(8)

(9)

(10)

閾值T的計(jì)算公式修改如下：

T=μln(αWi+β)

(11)

其中:α是特征點(diǎn)數(shù)量均值Wi的權(quán)重系數(shù)，β是對(duì)數(shù)函數(shù)的偏差系數(shù)，μ是對(duì)數(shù)函數(shù)的權(quán)重系數(shù)。

圖4 五宮格示意圖

圖5 五宮格旋轉(zhuǎn)示意圖

2.2 方形狀網(wǎng)格劃分法

GMS算法中網(wǎng)格劃分的P值和Q值都是人工定義的經(jīng)驗(yàn)值，一般設(shè)置為P=Q，這樣的經(jīng)驗(yàn)值會(huì)限制網(wǎng)格劃分?jǐn)?shù)量，對(duì)于長寬比例不一致的圖像，會(huì)生成不同的矩形狀網(wǎng)格，導(dǎo)致九宮格或者五宮格內(nèi)每個(gè)網(wǎng)格中粗匹配特征點(diǎn)數(shù)量分布不均，如Iw:Ih=4:3，P=Q=8時(shí)，劃分結(jié)果如圖6所示。

針對(duì)這個(gè)問題，本文提出將每幅圖像的長寬比值作為約束項(xiàng)，目的使得劃分的網(wǎng)格形狀接近規(guī)則的正方形，即只通過一個(gè)經(jīng)驗(yàn)值E和圖像自身的長寬比值來初始化P值和Q值。經(jīng)驗(yàn)值E，P值和Q值的計(jì)算關(guān)系如下：

(12)

比如當(dāng)Iw:Ih=4:3時(shí)，令E=8，則P=6,Q=8, 所以五宮格劃分的結(jié)果如圖7所示。

圖6 矩形狀網(wǎng)格

3 實(shí)驗(yàn)結(jié)果與分析

本文算法利用Visual Studio 2013編寫C++代碼，在CPU為2.3 GHz Intel core i5，12 GB內(nèi)存的計(jì)算機(jī)上運(yùn)行。本文采用了被廣泛使用的Oxford公開標(biāo)準(zhǔn)數(shù)據(jù)集[15]，該數(shù)據(jù)集共有8組圖像，包含多種類型的圖像變化，如平移、旋轉(zhuǎn)和視角變換等，本文針對(duì)其中bike和graffiti這兩組圖像進(jìn)行測試，圖像尺寸分別為1 000×700和800×640，如圖8(a)～8(b)所示。同時(shí)為了驗(yàn)證本文算法的實(shí)際應(yīng)用效果，本文采用兩組由無人機(jī)實(shí)際拍攝的遙感圖像進(jìn)行測試，圖像尺寸為7 952×5 304，如圖8(c)～8(d)所示。

本文算法的實(shí)驗(yàn)數(shù)據(jù)參數(shù)統(tǒng)一設(shè)置為{N,E,μ,α,β}={3 000,25,10,1.1,2}，其它比較算法均使用默認(rèn)參數(shù)。為公平起見，所有算法的輸入是相同的ORB特征點(diǎn)和粗匹配點(diǎn)集。

3.1 圖像匹配評(píng)價(jià)指標(biāo)

本文采用精確率，召回率和運(yùn)算時(shí)間3個(gè)評(píng)價(jià)指標(biāo)對(duì)算法進(jìn)行綜合評(píng)價(jià)。

1)精確率(Precision)表示預(yù)測為正確匹配的樣本中真正正確匹配的比例，定義如下：

(13)

2)召回率(Recall)表示預(yù)測為正確匹配的樣本占所有真正正確匹配的比例，定義如下：

(14)

其中:TP表示檢測出的正確匹配的樣本數(shù)量，F(xiàn)P表示將錯(cuò)誤匹配誤檢為正確匹配的數(shù)量，F(xiàn)N表示將正確匹配誤檢為錯(cuò)誤匹配的數(shù)量。

3)采用精匹配運(yùn)行時(shí)間對(duì)匹配速度進(jìn)行評(píng)價(jià)。

3.2 圖像匹配實(shí)驗(yàn)結(jié)果

首先使用實(shí)時(shí)性較高的ORB算法對(duì)每幅圖像檢測出3 000個(gè)特征點(diǎn)，然后利用暴力匹配法得到圖像間的3 000組粗匹配點(diǎn)對(duì)，最后利用RANSAC算法，VFC算法，GMS算法和本文算法進(jìn)行特征點(diǎn)精匹配的實(shí)驗(yàn)比較。最終的實(shí)驗(yàn)結(jié)果都是對(duì)每組圖像數(shù)據(jù)進(jìn)行50次測試的平均結(jié)果。

表1 特征點(diǎn)精匹配對(duì)數(shù)結(jié)果

表2運(yùn)算時(shí)間結(jié)果 ms

方法圖8(a)圖8(b)圖8(c)圖8(d)RANSAC93.19132.28122.65131.27VFC41.8948.6339.8648.97GMS20.2223.7526.1329.77本文算法14.8717.5219.6821.53

通過表1和表2上的實(shí)驗(yàn)結(jié)果可知，RANSAC算法剔除特征點(diǎn)錯(cuò)誤匹配后，剩余的特征點(diǎn)數(shù)量最少，且由于自身算法復(fù)雜度較大，因此運(yùn)算時(shí)間最長，平均耗時(shí)119.85 ms。VFC算法剔除錯(cuò)誤匹配后，剩余的特征點(diǎn)數(shù)量相對(duì)最多，運(yùn)行速度明顯優(yōu)于RANSAC算法，但運(yùn)算時(shí)間還是較久，平均耗時(shí)44.84 ms。GMS算法剔除錯(cuò)誤匹配后，剩余的特征點(diǎn)數(shù)量與VFC算法相近，平均耗時(shí)24.97 ms。而本文算法剔除錯(cuò)誤匹配后，剩余的特征點(diǎn)數(shù)量也相對(duì)較多，略少于VFC算法，但運(yùn)行速度最快，平均耗時(shí)18.41 ms，相對(duì)于GMS算法，提高35.6%。因此在運(yùn)算速度方面，本文算法相對(duì)于RANSAC算法，VFC算法和GMS算法有明顯的提升。

表3 精確率結(jié)果 %

表4 召回率結(jié)果 %

通過表3和表4上的實(shí)驗(yàn)結(jié)果可知，RANSAC算法的平均精確率適中，而平均召回率為89.71%，在這4種算法中相對(duì)最低。VFC算法的平均精確率整體高于RANSAC算法，且平均召回率在這4種算法中最高。GMS算法的平均精確率略低于VFC算法，而平均召回率較高。本文算法的平均精確率與GMS算法相近，平均召回率略低于GMS算法，分別可達(dá)97.25%和92.85%。由上述可知，將九宮格統(tǒng)計(jì)法替換成五宮格統(tǒng)計(jì)法，精確率沒有明顯變化，雖然召回率相對(duì)略有減小，但仍然屬于有效范圍內(nèi)。

4 結(jié)束語

針對(duì)目前特征點(diǎn)匹配算法計(jì)算時(shí)間長，無法應(yīng)用在對(duì)實(shí)時(shí)性要求較高的領(lǐng)域等問題，如視覺SLAM，本文提出了一種改進(jìn)網(wǎng)格劃分統(tǒng)計(jì)的特征點(diǎn)快速匹配算法。把圖像的長寬比作為約束項(xiàng)，使得劃分的網(wǎng)格呈方形狀，并根據(jù)對(duì)稱性將特征點(diǎn)所在網(wǎng)格相鄰的4個(gè)網(wǎng)格作為鄰域來統(tǒng)計(jì)五宮格鄰域分?jǐn)?shù)。相比于GMS算法，統(tǒng)計(jì)網(wǎng)格數(shù)量和旋轉(zhuǎn)次數(shù)都減少一半，較大地提高了特征點(diǎn)匹配效率。實(shí)驗(yàn)結(jié)果表明，與目前特征點(diǎn)匹配算法相比，本文算法在保持較高精度的情況下，具有較大的速度優(yōu)勢，綜合效率較高。