一種KD樹的快速SURF圖像匹配算法

廣州南方學院電氣與計算機工程學院 彭 石 張 晴 曾海杰 張焱瑋

現有的圖像匹配算法存在運行慢、時間復雜度高等缺點，本文在研究了圖像特征和匹配算法的基礎上，提出了一種改進的快速匹配算法。該算法能有效地解決圖像尺寸過大帶來的匹配慢的問題，首先對于要匹配的的圖像，經過線性縮小后變為易于處理的灰度圖，再使用SURF算法計算初始特征點集，經過逆變換后映射到原圖像求得過濾后的點集，并且生成SURF特征描述子，針對SURF匹配慢的缺陷，本文采用KD樹來實現點集的匹配和查詢，測試結果表明，本文算法在保證了匹配精度的條件下，有效的降低了匹配的時間復雜度。

圖像匹配算法在遙感、航空航天、生物信息識別等方面應用廣泛，特別是隨著智能設備的普及，指紋識別、人臉識別等圖像處理技術越來越受到重視和關注?？焖贉蚀_地處理與識別圖像，滿足用戶個性化多樣化的需求，是國內外理論研究的重要參考原則。

圖像匹配可以采用不同的方法進行，有采用全局統計特性的匹配，還有基于局部特征的方法。前者一般采用統計的手段，后者先計算特征點，利用特征點的特征描述子來進行圖像的匹配。由于特征點數一般比較少，所以后者的匹配速度一般比前者快，精度也高很多。為了有效進行圖像匹配，Lowe DG提出了一種SIFT算法，該算法匹配和識別的效率較高，但實時性較差，Bay H,Tuyte T,Gool L Van針對SIFT的不足提出了改進的算法SURF，該算法具有匹配的速度比較快、在圖像尺度和仿射變換下保持不變性等優點；阮芹,彭剛,李瑞利用改進后的SURF算法，針對兩幅圖像的重疊部分提取局部特征點，實現了重疊部分的平滑過渡。

本文提出了一種基于KD樹的快速匹配算法，該算法能有效地解決圖像尺寸過大帶來的匹配慢的問題，首先該算法把要匹配的的圖像縮小后變為易于處理的灰度圖，再使用SURF算法計算初始特征點集，經過逆變換后映射到原圖像求得過濾后的點集，并且生成SURF特征描述子，最后采用KD樹來實現點集的匹配和查詢。該方法可以在匹配精度不變的條件下，顯著減少匹配的計算次數。

1 改進的SURF算法流程

1.1 圖像縮放

圖像縮放，本質上就是將每個像素點的矢量進行縮放，也就是將矢量x方向和y方向的坐標值縮放，假設縮小系數為k，縮放表示成矩陣的形式：

通過上述矩陣乘法的形式，把原圖像上的每一個像素點映射到新圖像上相應的像素點了，其逆變換為：

1.2 SURF特征點檢測

為了有效地提取圖像f(x,y)的特征，Surf通過計算其Hessian矩陣來實現圖像的預處理操作。Hessian矩陣通過計算圖像的偏導數得到包含圖像特征信息的初始矩陣，經過過濾可以得到SURF的關鍵特征點。由于f(x,y)圖像包含有噪聲信號，生成Hessian矩陣前一般先進行濾波操作，高斯濾波后的該矩陣數學表達式為：

得到Hessian矩陣之后，SURF通過計算其判別式是否為局部最大來尋找關鍵點的位置。局部最大值對應的點一般比周圍點更亮或更暗，這些點包含更多的圖像信息，為了準確找出這些點SURF使用盒式濾波器計算Hessian矩陣行列式：

上式中det表示在點(x,y)周圍區域的方框濾波響應值，如果行列式的值為負，并且特征值異號，該點不是局部極值；如果行列式為正并且特征值同號，則該點為局部極值。使用其它大小的模板，Hessian矩陣行列式就包含了多尺度響應信息，經過局部搜索周圍點的Hessian值，如果最大，則為標記為特征點。

圖1 線性變換

從縮放后的圖像得到特征點之后，本文通過運算得到原圖像的特征點。如圖1所示，已知P點為經過步驟1逆變換后的像素點，它的四周有四個待識別的點，利用上述步驟重新計算四個點的Hessian矩陣及其行列式，如果最大則標記為原圖像的特征點。

1.3 SURF特征描述子

1.3.1 特征點方向分配

經過上一步得到特征點后，接下來就需要計算每個點對應的主要方向。SURF算法在特征點的周圍區域通過小波變換計算領域特征，每計算一次，按照一定的角度旋轉繼續進行下一次特征計算，所有方向統計完成，小波響應值最大的方向即為特征點的主要參考方向。

1.3.2 特征向量生成

Surf算法的每個特征點都包含一個64維的特征向量，其計算方法是沿著每個點的主要參考方向，取16個排列成4X4正方形的方塊，每個方塊都包含25個像素，通過計算這些像素不同的小波特征，每個方塊生成4維的向量，故每個特征點需要統計的特征向量有64個值。

1.4 特征匹配

經過上述步驟得到特征點和特征向量之后，本文使用kd樹完成特征點的查詢和匹配的過程。

1.4.1 kd樹的生成過程

（1）對于需要統計的點集，假設每個點有m維數據，分別計算各個維度的方差，選擇方差最大的維度n，假設該維度下對應的中值為d，以其對應的節點為根節點對原始點集進行劃分，維度n下比d小的和比d大的生成兩個子集A、B。

（2）對A、B子集按照1的方法繼續進行劃分，不斷地生成新的子集和節點，直到所有集合劃分結束，kd樹生成完畢。

1.4.2 查詢匹配過程

（1）kd樹的查詢過程是從根節點開始的，將查詢節點Q特征向量相應維度上的值與kd樹的相應的值作比較，若前者小遍歷左邊的分支及其節點，否則去另一邊的分支，重復上述過程不斷記錄節點Q與葉結點向量之間的距離，最小距離dmin對應的數據點稱為最近鄰點。

（2）進行遍歷回滾，在找到的節點附近的節點進行上述過程，防止存在離Q更近的節點。

對于找到的最近鄰與次近鄰點值，本文通過以下步驟進行判斷是否為正確匹配，對于目標圖片的中每個特征點，使用上述的方法計算它的最近鄰和次近鄰，

如果二者之差的絕對值大于某個閾值，則認為該匹配是成功的，否則就進行下一次匹配。對于待匹配的兩張圖像，將各圖像所有特征點都進行上述的SURF特征匹配過程。

2 實驗結果與分析

為了驗證本文算法的有效性，實驗中選擇了1000張圖片進行了性能測試，這些圖片分成5組，每組200張圖片，各組前100張是不同主題的原始圖像，后100張是從不同方向拍攝或者旋轉后的圖像。將后100張圖片分別用SIFT、SURF以及本文算法與前100張進行匹配識別，然后從識別的精度和時間復雜度兩個方面比較測試的結果。每進行一次匹配，將所有匹配后的特征點距離按照從小到大排序，然后計算前50個最近距離之和作為兩張圖的相似度，經過100次計算后，如果正確匹配就將正確的次數加1，否則將錯誤次數加1。

圖2 特征匹配結果

表1 各算法的識別精度比較

表2 各算法的平均匹配時間比較

圖2所示為旋轉后的圖片和原圖的匹配過程，左右圖上的連線表示匹配成功。全部圖片進行上述過程得到的結果如下所示，表1、2為用三種算法實驗得到的精度和時間復雜度表。從表1可以看出，本文算法的匹配精度不低于SURF算法，遠遠高于SIFT算法。從表2可知，本文算法的匹配時間遠遠低于SIFT，和SURF算法相比，足足縮短了2倍多。由此可知，本文算法在匹配上具有時間復雜度低的優勢。

結束語：本文提出了一種基于KD樹的快速匹配算法，該算法能有效地解決圖像匹配速度慢的問題，首先該算法把要匹配的的圖像縮放后變為易于處理的灰度圖，再使用SURF算法計算初始特征點集，經過逆變換后映射到原圖像求得最終的特征點集，并且生成SURF特征描述子，最后采用KD樹來實現點集的匹配和查詢。實驗結果表明，本文方法能夠在保證匹配精度不降低的條件下，明顯降低匹配的時間復雜度。