一種KD樹(shù)的快速SURF圖像匹配算法

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

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

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

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

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

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

1.1 圖像縮放

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

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

1.2 SURF特征點(diǎn)檢測(cè)

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

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

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

圖1 線(xiàn)性變換

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

1.3 SURF特征描述子

1.3.1 特征點(diǎn)方向分配

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

1.3.2 特征向量生成

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

1.4 特征匹配

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

1.4.1 kd樹(shù)的生成過(guò)程

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

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

1.4.2 查詢(xún)匹配過(guò)程

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

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

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

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

2 實(shí)驗(yàn)結(jié)果與分析

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

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

表1 各算法的識(shí)別精度比較

表2 各算法的平均匹配時(shí)間比較

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

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