徐明，刁燕

（四川大學機械工程學院，成都610065）

0 引言

圖像匹配是指在兩幅或者多幅圖像中通過一定的算法找到相似影像的方法[1]。在數字圖像處理的研究過程中，圖像的特征提取以及圖像匹配一直是一個關鍵問題，在圖像配準、目標檢測、模式識別、計算機視覺等領域發(fā)揮著至關重要的作用[2]。

1998 年，Harris 和Stephens 在工作的啟發(fā)下提出Harris 角點檢測算法[3]，是對Moravec 算法的擴充和完善。通過分別計算像素點在x 和y 方向上的梯度，利用高斯核函數對圖像進行高斯濾波，然后根據角點響應函數計算原圖像上對應的每個像素點的響應值，最后通過給定的閾值選取局部極值點來確定圖像的特征點。Harris 算法是直接通過灰度圖像然后進行角點提取，該算法適用于L 型的角點檢測，穩(wěn)定性好，但是容易出現角點信息丟失和角點的位置偏移以及聚簇現象，運行速度也比較慢。

2004 年，Lowe 發(fā)表了尺度不變特征（Scale Invariant Feature Transform，SIFT）算法[4]，通過構建高斯尺度空間，尋找極值點，剔除不穩(wěn)定特征點，確定關鍵點方向和生成特征點描述子來提取圖像的特征點。

SIFT 算法引入圖像金字塔結構，在不影響提取圖像中大量特征點的基礎下，降低了計算量，但是SIFT算法沒有考慮到空間中的幾何約束信息，造成了誤匹配率高，而且還容易出現特別明顯的亂配和錯配現象。

2006 年，Bay 對SIFT 算子進行了改進，提出了加速魯棒特征（Speeded Up Robust Feature，SURF）算法[5]，該算法通過構建Hessian 矩陣，建立尺度空間，定位特征點，確定特征點主方向，最后生成特征點描述子來得到特征點。SURF 算法引入積分圖像并且與Harris 特征相結合，在圖像尺度和仿射變換都可以保持不變性的條件下，更好地提高了程序的運算速度，同時在多幅圖片中也具備良好的魯棒性，但誤匹配率高仍然存在。

通過對上述方法的研究，本文提出了基于加速魯棒特征（Speed Up Robust Feature，SURF）算法與快速近似最近鄰查找（Fast Library for Approximate Nearest Neighbors，FLANN）搜索的圖像匹配方法。首先采用Hessian 矩陣來獲知圖像的局部最值，然后在圖像上構建尺度空間，通過不同的尺度空間定位出特征點，并確立特征點的主方向，再生成特征點描述子，最后結合FLANN 搜索算法對圖像進行匹配。實驗表明，該算法相對傳統(tǒng)的圖像匹配方法提高了準確度和匹配效果。

1 SURF算子原理

1.1 特征點檢測

首先需要在一幅圖像上構建Hessian 矩陣，然后通過Hessian 矩陣得到圖像上穩(wěn)定的邊緣點，為接下來的特征提取奠定基礎。若一幅圖像為f（x,y），則此圖像的上某個像素點的Hessian 矩陣可如下表示：

由于求出的特征點需要具有尺度無關性，則在構建Hessian 矩陣之前需要對處理圖像進行高斯濾波，經過高斯濾波后得到的Hessian 矩陣為：

為了提高運算速度，Bay 提出采用盒子濾波器，然后使用Dxx、Dxy和Dyy來替換Hessian 矩陣中的Lxy、Lxy、Lyy，則Hessian 矩陣判別式可以簡化為：

其中w 為通用系數，在實際應用中不斷總結經驗得到該值近似為0.9。

當Hessian 矩陣判別式取得局部極大值時，可以判斷該點比周圍鄰域內的其他點更亮或者更暗，從而定位出興趣點的位置。

1.2 構建尺度空間

構建尺度空間，顧名思義，是指在不同的維度上對圖像進行特征檢測，現在常用的方法是通過建立圖像金字塔，然后通過圖像金字塔來對圖像進行多維度描述。在SIFT 算法中，首先通過對目標圖像進行下采樣得到多幅圖像，然后通過生成的高斯金字塔中同組圖像中上一層圖像減去下一層圖像，從而獲得差分圖像，改變了原始圖像的大小，該方法運算慢，效率低。而在SURF 算法中，不改變目標圖像的大小，根據提出的盒式濾波器，在改變盒式濾波器的模板尺寸大小從而獲得圖像金字塔，該方法運算速度快，提高了效率，如圖1所示。

圖1 金字塔結構

1.3 特征點定位

在得到興趣點的位置和建立圖像金字塔之后，需要在興趣點中定位出特征點。首先需要選擇合適的閾值，在興趣點當中保留響應最強烈的點，選取的閾值越大，則保留下來的特征點越多。然后根據非極大值抑制，將得到的點與尺度空間中周圍鄰域的8 個像素點相比較，再與上次兩層的尺度空間的各9 個像素點進行比較，總共是26 個像素點，不包括圖像金字塔的第一層和最后一層，如圖2 所示。最后對選出的關鍵點進行三次線性插值計算，可以得到穩(wěn)定的特征點。

圖2 特征點定位

1.4 選取特征點主方向

為了確保圖像具有旋轉不變形，需要給每一個特征點選擇一個主方向，在SURF 算法中，是通過Haar小波特征來確定。以特征點為中心，取半徑為6s 的繪制一個圓形，在圓形區(qū)域內取一個60°扇形，計算在60°扇形范圍內的Harr 小波特征，形成一個新的矢量，然后再轉動扇形直到所有的圓形區(qū)域被覆蓋，最后在整個圓形區(qū)域內選取一條最長的新的矢量作為此特征點的主方向，如圖3 所示。

圖3 特征點主方向求取過程

1.5 生成特征描述子

計算出特征點的位置以及選取出特征點的主方向，最后一步就是在局部區(qū)域內生成特征描述子。在SURF 算法中，以特征點為中心，在特征點附近選取4×4 個矩形區(qū)域，計算每個區(qū)域內的Harr 小波響應值。由于每個子區(qū)域含有4 個特征向量，故SURF 特征向量共有4×4×4 即64 維特征向量來表示每一個特征點。

2 FLANN搜索

FLANN 算法是在2009 年由Muja 和Lowe[6-7]提出的，主要是根據KD-TREE 操作或者是K 均值樹實現，由已知的數據集的分布特點以及所要求的空間資源消耗來給出有效的搜索類型和檢索參數。FLANN 算法要求的特征空間通常是n 維實數向量空間Rn，此算法的關鍵點是根據歐氏距離尋找在實例點附近鄰域最鄰近的點，歐氏距離的數學定義式如下所示。

如果得到的D 值越小，就說明所存在的特征點對之間的距離就很“近”，也就是圖像中的特征點對的相似程度就越高。

本方法將n 維空間Rn中的數據點根據KD-TREE方法分成幾個特定的區(qū)域，其作用是在查詢點鄰域范圍內檢索出與其查詢點最近的歐氏距離[8]。

在n 維空間Rn中，通過KD-TREE 這種結構存儲所有的歐氏距離，就可以很方便而且更行之有效地查找與參考點最鄰近的點。KD-TREE 結構的搜索過程是由上而下進行遞歸。首先根據特定的基準將目標點與分割點分離開，然后將它們進行比較，判斷目標點是在基準點左邊還是右邊；逐一與對應點進行循環(huán)比較，直到目標點被成功搜索。

3 實驗結果分析

根據上述提出的算法，本次實驗以SURF 算法與SURF+FLANN 算法作對比，在Windows 10 上運行，使用到Visual Studio 2015 和OpenCV3.4，通過Mikolajazyk[9]數據集進行驗證。

第一組實驗取自Mikolajazyk 數據集中的bark 的兩幅圖像，圖4 為原始輸入的圖像，圖5 為采用SURF算法進行特征點檢測并進行特征匹配后的實驗結果，圖6 為采用SURF+FLANN 算法進行特征點檢測并進行特征匹配后的實驗結果。

圖4 原始輸入圖像

圖5 SURF特征匹配

圖6 SURF+FLANN特征匹配

第二組實驗取自Mikolajazyk 數據集中的tree 的兩幅圖像，圖7 為原始輸入的圖像，圖8 為采用SURF 算法進行特征點檢測并進行特征匹配后的實驗結果，圖9為采用SURF+FLANN 算法進行特征點檢測并進行特征匹配后的實驗結果。

圖7 原始輸入圖像

圖8 SURF特征匹配

圖9 SURF+FLANN特征匹配

本文分別統(tǒng)計了在SURF 算法與SURF+FLANN算法下，左圖特征點數量、右圖特征點數量、兩幅圖像之間的匹配點數量以及正確匹配點數量的四個指標，并計算出匹配正確率，統(tǒng)計結果如表1 所示。

表1 SURF 與SURF+FLANN 特征匹配數據對比

在表1 中可以看出，在相同的實驗條件下，SURF+FLANN 算法提取的特征點以及兩幅圖像之間的匹配點數量雖然不如SURF 算法多，但是兩幅圖像之間的正確匹配點數量以及匹配的正確率要比SURF 算法高，說明SURF+FLANN 算法能夠更準確地提取出匹配點，具有較強的匹配能力，匹配出的效果也更佳，也能夠更豐富地表現出兩幅圖像的細節(jié)信息以及相似程度。

4 結語

本文針對傳統(tǒng)的圖像匹配算法中存在的誤匹配率高和匹配效果不佳的問題，提出了基于SURF 算法與FLANN 搜索的圖像匹配方法。利用SURF 算法對圖像提取大量有效的特征信息，同時結合FLANN 搜索算法，在不影響匹配準確率的前提下，提高了圖像匹配的效果。由實驗結果可知，本文提出的算法在圖像匹配效果以及準確率方面都要表現地更好。