基于改進網格劃分統計的特征點快速匹配方法

陳方杰，韓 軍， 王祖武

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

0 引言

圖像特征匹配是計算機視覺領域中基礎又重要的研究課題，其廣泛應用于視覺SLAM，圖像拼接和三維重建等領域[1]。基于特征的匹配策略一般是通過尋找兩幅圖像之間的局部映射關系來完成，主要包括點匹配[2]，線匹配[3]和區域匹配[4]等。由于特征點更易提取，匹配方式靈活，所以基于特征點的匹配算法在圖像特征匹配中被普遍采用。基于特征點的匹配算法有兩種：特征描述子相似約束和幾何約束。

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

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

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

1 GMS算法

1.1 運動平滑

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

將{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}和粗匹配特征點數量Wi。然后統計上述特征點初始匹配的特征點集{f2,i,1,f2,i,2,...,f2,i,Wi}和{f2,i,1,f2,i,2,...,f2,i,Wi}位于N2,i中的數量，記為特征鄰域分數Si。其中令si,k表示N1,i中第k個特征點粗匹配對應的特征點是否位于N2,i的標志分數，若位于N2,i中，計分為1，反之不計分。最后根據分數閾值T來判定第i組粗匹配特征點對{f1,i,f2,i}是正確匹配還是錯誤匹配。

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

(1)

(2)

1.2 九宮格統計法

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

(3)

圖1 網格劃分和九宮格網格鄰域

(4)

(5)

(6)

(7)

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

圖2 九宮格示意圖

圖3 九宮格旋轉示意圖

2 改進的五宮格劃分統計

2.1 五宮格統計法

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

(8)

(9)

(10)

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

T=μln(αWi+β)

(11)

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

圖4 五宮格示意圖

圖5 五宮格旋轉示意圖

2.2 方形狀網格劃分法

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

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

(12)

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

圖6 矩形狀網格

3 實驗結果與分析

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

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

3.1 圖像匹配評價指標

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

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

(13)

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

(14)

其中:TP表示檢測出的正確匹配的樣本數量，FP表示將錯誤匹配誤檢為正確匹配的數量，FN表示將正確匹配誤檢為錯誤匹配的數量。

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

3.2 圖像匹配實驗結果

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

表1 特征點精匹配對數結果

表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算法剔除特征點錯誤匹配后，剩余的特征點數量最少，且由于自身算法復雜度較大，因此運算時間最長，平均耗時119.85 ms。VFC算法剔除錯誤匹配后，剩余的特征點數量相對最多，運行速度明顯優于RANSAC算法，但運算時間還是較久，平均耗時44.84 ms。GMS算法剔除錯誤匹配后，剩余的特征點數量與VFC算法相近，平均耗時24.97 ms。而本文算法剔除錯誤匹配后，剩余的特征點數量也相對較多，略少于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%。由上述可知，將九宮格統計法替換成五宮格統計法，精確率沒有明顯變化，雖然召回率相對略有減小，但仍然屬于有效范圍內。

4 結束語

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