陳方杰，韓 軍， 王祖武

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

0 引言

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

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

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

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

1 GMS算法

1.1 運動平滑

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

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

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

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

(1)

(2)

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

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

(3)

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

(4)

(5)

(6)

(7)

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

圖2 九宮格示意圖

圖3 九宮格旋轉示意圖

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

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

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

(8)

(9)

(10)

閾值T的計算公式修改如下：

T=μln(αWi+β)

(11)

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

圖4 五宮格示意圖

圖5 五宮格旋轉示意圖

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

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

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

(12)

比如當Iw:Ih=4:3時，令E=8，則P=6,Q=8, 所以五宮格劃分的結果如圖7所示。

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

3 實驗結果與分析

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

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

3.1 圖像匹配評價指標

本文采用精確率，召回率和運算時間3個評價指標對算法進行綜合評價。

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

(13)

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

(14)

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

3)采用精匹配運行時間對匹配速度進行評價。

3.2 圖像匹配實驗結果

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

表1 特征點精匹配對數(shù)結果

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

表3 精確率結果 %

表4 召回率結果 %

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

4 結束語

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