廣州南方學(xué)院電氣與計算機(jī)工程學(xué)院 彭 石 張 晴 曾海杰 張焱瑋

現(xiàn)有的圖像匹配算法存在運(yùn)行慢、時間復(fù)雜度高等缺點，本文在研究了圖像特征和匹配算法的基礎(chǔ)上，提出了一種改進(jìn)的快速匹配算法。該算法能有效地解決圖像尺寸過大帶來的匹配慢的問題，首先對于要匹配的的圖像，經(jīng)過線性縮小后變?yōu)橐子谔幚淼幕叶葓D，再使用SURF算法計算初始特征點集，經(jīng)過逆變換后映射到原圖像求得過濾后的點集，并且生成SURF特征描述子，針對SURF匹配慢的缺陷，本文采用KD樹來實現(xiàn)點集的匹配和查詢，測試結(jié)果表明，本文算法在保證了匹配精度的條件下，有效的降低了匹配的時間復(fù)雜度。

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

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

本文提出了一種基于KD樹的快速匹配算法，該算法能有效地解決圖像尺寸過大帶來的匹配慢的問題，首先該算法把要匹配的的圖像縮小后變?yōu)橐子谔幚淼幕叶葓D，再使用SURF算法計算初始特征點集，經(jīng)過逆變換后映射到原圖像求得過濾后的點集，并且生成SURF特征描述子，最后采用KD樹來實現(xiàn)點集的匹配和查詢。該方法可以在匹配精度不變的條件下，顯著減少匹配的計算次數(shù)。

1 改進(jìn)的SURF算法流程

1.1 圖像縮放

圖像縮放，本質(zhì)上就是將每個像素點的矢量進(jìn)行縮放，也就是將矢量x方向和y方向的坐標(biāo)值縮放，假設(shè)縮小系數(shù)為k，縮放表示成矩陣的形式：

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

1.2 SURF特征點檢測

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

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

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

圖1 線性變換

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

1.3 SURF特征描述子

1.3.1 特征點方向分配

經(jīng)過上一步得到特征點后，接下來就需要計算每個點對應(yīng)的主要方向。SURF算法在特征點的周圍區(qū)域通過小波變換計算領(lǐng)域特征，每計算一次，按照一定的角度旋轉(zhuǎn)繼續(xù)進(jìn)行下一次特征計算，所有方向統(tǒng)計完成，小波響應(yīng)值最大的方向即為特征點的主要參考方向。

1.3.2 特征向量生成

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

1.4 特征匹配

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

1.4.1 kd樹的生成過程

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

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

1.4.2 查詢匹配過程

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

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

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

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

2 實驗結(jié)果與分析

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

圖2 特征匹配結(jié)果

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

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

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

結(jié)束語：本文提出了一種基于KD樹的快速匹配算法，該算法能有效地解決圖像匹配速度慢的問題，首先該算法把要匹配的的圖像縮放后變?yōu)橐子谔幚淼幕叶葓D，再使用SURF算法計算初始特征點集，經(jīng)過逆變換后映射到原圖像求得最終的特征點集，并且生成SURF特征描述子，最后采用KD樹來實現(xiàn)點集的匹配和查詢。實驗結(jié)果表明，本文方法能夠在保證匹配精度不降低的條件下，明顯降低匹配的時間復(fù)雜度。