結(jié)合FAST-SURF和改進k-d樹最近鄰查找的圖像配準

陳劍虹， 韓小珍

(西安理工大學 機械與精密儀器工程學院，陜西 西安 710048)

?

結(jié)合FAST-SURF和改進k-d樹最近鄰查找的圖像配準

陳劍虹， 韓小珍

(西安理工大學 機械與精密儀器工程學院，陜西 西安 710048)

針對兩圖像之間存在平移和旋轉(zhuǎn)變化的圖像匹配，提出了一種結(jié)合FAST-SURF和改進k-d樹最近鄰查找的圖像配準算法。該算法首先用FAST(加速分割檢測特征)檢測器進行特征點提取，然后根據(jù)特征點周圍鄰域的信息生成SURF(快速魯棒特征)描述子，采用一種改進的k-d樹最近鄰查找算法BBF(最優(yōu)節(jié)點優(yōu)先)尋找特征點的最近鄰點及次近鄰點，接著進行雙向匹配得到初匹配點對，最后利用RANSAC(隨機抽樣一致性)算法消除誤匹配點，findHomography函數(shù)尋找單應性變化矩陣，從而計算出圖像間的相對平移量和旋轉(zhuǎn)量。實驗結(jié)果表明，該算法平移參數(shù)的最大誤差為0.022個像素，旋轉(zhuǎn)參數(shù)的最大誤差為0.045度，優(yōu)于傳統(tǒng)的SURF圖像匹配算法，實現(xiàn)了圖像的快速、高精度配準。

圖像匹配； FAST-SURF算法； BBF； 雙向匹配； RANSAC

圖像匹配是常見的一種圖像處理技術(shù)，它是將處于不同傳感器、不同時刻、或者不同條件下的兩幅圖像進行對準的過程，用以找到兩幅圖像間的平移及旋轉(zhuǎn)關(guān)系，廣泛用于遙感圖像分析、工業(yè)檢測、圖像融合等領域[1]。在很多應用場景中，例如遙感圖像配準、圖像測量等領域，對圖像配準精度有較高要求。

圖像匹配算法一般有基于灰度值的匹配和基于特征的匹配[2]兩大類。前者是根據(jù)圖像間像素點的灰度值來進行相似性比較的一種算法，該算法計算量相對較大，需要逐像素進行比較，匹配精度高，適用于圖像間存在平移變換的圖像匹配。后者是先提取特征點，然后采用一定的方法生成描述向量，最后實現(xiàn)特征配準的一種算法。該算法優(yōu)點是匹配速度快，抗噪聲能力強，而且對仿射變換、光照等都有比較強的魯棒性。典型的特征點提取算法主要有Moravec、SUSAN[3]、Harris[4]、SIFT[5-6](Scale-invariant Feature Transform) 以及SURF (Speeded Up Robust Feature) 算子等。其中，使用較多的有Harris、SIFT和SURF算子。Lowe[7]等人提出的SIFT算法在噪聲、仿射變換等方面都具備非常好的匹配能力，尤其是在抗旋轉(zhuǎn)方面，但SIFT算法在計算的過程中會產(chǎn)生大量的描述符，從而引起計算量大、運行時間長的問題。Bay等人在2006年提出了SURF算法[8]，該算法在匹配的過程中引入了積分圖像，從而使其匹配速度遠遠超過了SIFT算法，然而此類關(guān)鍵點特征運算量還是過于龐大，檢測的特征點數(shù)目過少，導致獲得的匹配點數(shù)量少，降低了匹配的效率。Rosten等人提出了一種快速、有效的FAST特征點檢測算法[9]，該算法既減少了檢測時間，又進一步提取了圖像細節(jié)處的特征點，提高了匹配精度。

因此，筆者提出了一種結(jié)合FAST-SURF和改進的k-d樹最近鄰查找的圖像配準算法，該算法用FAST檢測器對特征點進行提取，同時結(jié)合了SURF特征描述子，并用BBF算法進行查找，然后利用雙向匹配算法獲取初匹配點對，實現(xiàn)了對傳統(tǒng)單向匹配算法的改進，最后使用RANSAC實現(xiàn)精確匹配，計算得出變化參數(shù)。實驗仿真結(jié)果表明，本文算法對于圖像間存在平移、旋轉(zhuǎn)變化有非常好的配準效果。

1　算法介紹

由于FAST算法在檢測特征點方面具有快速和穩(wěn)定的特性，可用它來進行角點的檢測。本文基于FAST的特征檢測來取代基于SURF特征檢測，提高了提取速度，同時與SURF描述子相結(jié)合，使特征點具有抗旋轉(zhuǎn)特性。

在特征匹配過程中，采用BBF算法實現(xiàn)最近鄰查找，然后用雙向匹配算法得到初匹配點對，最后使用RANSAC算法實現(xiàn)精確匹配，該算法的流程如圖1所示。

圖1　算法流程圖Fig.1　Algorithm flowchart

算法的具體步驟如下: ①采用FAST算法檢測特征點; ②根據(jù)特征點周圍的鄰域信息生成SURF描述子: ③利用改進的k-d樹BBF算法對特征點進行查找，使用雙向匹配算法進行粗匹配; ④使用RANSAC實現(xiàn)精確匹配，并計算得出變化參數(shù)。

1.1FAST特征點檢測

FAST特征檢測算法是利用特征點周圍的圖像灰度值來定義的，是非常簡單又快速的特征檢測算子。如圖2所示，該算法通過選定圖像中的任意一個像素點作為候選特征點，并以該候選特征點為圓心構(gòu)造一個圓形區(qū)域，檢測圓周上的像素灰度值，并與該候選點的灰度值進行比較，假如兩者的灰度值差別很大，并且圓周上滿足這一條件的點數(shù)足夠多，則選定該候選點為特征點。

圖2　FAST特征點提取Fig.2　Detection of FAST feature

特征點的判斷過程為：設I(p)為候選特征點p的灰度值，I(x)為圓周上點x的像素灰度值，εd為給定閾值。以N表示滿足下述公式的圓周上像素點x的個數(shù)：

|I(x)-I(p)|>εd

(1)

如果滿足判定條件的像素點數(shù)N大于設定值，一般為周圍圓周點的四分之三，即認為p是特征點。

本文采用FAST角點提取改進算法，使其可以快速的排除一些非特征點，從而加快了算法的提取速度。首先檢測候選點p圓周上每隔90°角的4個點(點1、5、9、13)，如果這4個像素點至少有3個滿足公式(1)，則再計算其他點；假如不滿足，則認為此候選點不是特征點。

1.2SURF特征點描述

1.2.1特征點主方向的選取

完成特征點的檢測后，必須對其進行主方向的選取。首先，構(gòu)建一個圓形區(qū)域，該區(qū)域?qū)⑻卣鼽c設為中心，半徑設為6s(s即特征點的尺度值)，然后計算區(qū)域內(nèi)像素點的Haar小波響應值。

如圖3所示，左側(cè)為Haar小波在x方向上的響應，右側(cè)為Haar小波在y方向上的響應，將高斯權(quán)重系數(shù)賦予響應值，使離特征點近的Haar響應貢獻比較大，而離特征點遠的貢獻比較小，把60度區(qū)域內(nèi)的所有響應相加，獲得新的矢量，接著遍歷整個區(qū)域，特征點主方向即為矢量最長的方向。

最后計算每個特征點，獲得所有特征點的主方向[10]。

圖3　Haar小波響應Fig.3　Response of Haar wavelet

1.2.2特征點描述符的生成

生成SURF描述符的第一步是構(gòu)造一個正方形區(qū)域，將特征點設為該區(qū)域的中心，邊長設為20s，區(qū)域方向設置為與特征點方向一致。

如圖4所示，然后對該區(qū)域?qū)崿F(xiàn)等間隔采樣(采樣間隔為s)，并將其劃分成4×4=16個子區(qū)域，計算這些子區(qū)域Haar小波響應。

圖4　描述符表示Fig.4　Representation of a descriptor

(2)

將16個子區(qū)域的V組合在一起，獲得16×4=64維特征描述向量，即生成了SURF描述符。

1.3FAST-SURF算法

FAST特征檢測的優(yōu)點主要有以下幾點。

1) 計算簡單、快速。FAST檢測算子是通過特征點周圍的灰度值來判斷是否為特征點，操作方便。

2)FAST特征檢測子可以提取大量的有用的特征點，即提取的特征點大多位于圖像的細節(jié)區(qū)域，避免了邊緣區(qū)域提取太多的特征點的問題。

3) 如果圖像存在平移、旋轉(zhuǎn)變換，F(xiàn)AST角點檢測子依然很穩(wěn)定。

SURF特征檢測算法的優(yōu)點是具有尺度不變性，當圖像發(fā)生仿射、光照、噪聲等變換時，該算法也具有很好的穩(wěn)定性。盡管SURF算法在特征檢測方面具有很多優(yōu)點，但由于其特征檢測數(shù)量相對較少，速度較慢，降低了圖像的匹配速度和精確度。

針對此問題，本文用FAST角點檢測器來替代傳統(tǒng)的SURF特征檢測器，克服了傳統(tǒng)的SURF檢測子提取特征點少，計算量大的問題，同時又保留了SURF描述子的抗旋轉(zhuǎn)特性，實現(xiàn)了對SURF算法較好的改進。

1.4改進的k-d樹最近鄰查找算法的特征點匹配

利用FAST角點檢測器和SURF特征描述子得到特征點后，要實現(xiàn)圖像匹配。

針對普通的k-d樹最近鄰查找算法對于高維數(shù)據(jù)的查找時間較長，速度慢的缺點，本文采用了一種改進的k-d樹BBF查找算法來替代傳統(tǒng)的k-d樹查找方法。BBF算法由于在k-d樹算法的基礎上加入了優(yōu)先隊列，即在形成搜索路徑的同時也形成了優(yōu)先隊列，在回溯查找的過程主要按照優(yōu)先隊列來進行查找，從而避免了重復路徑的搜索過程，進一步提高了搜索效率。

本文首先利用歸一化的歐氏距離準則[11]，得到兩幅圖像特征點之間的相似性距離，然后建立64維的k-d樹，采用改進的k-d樹算法在待匹配圖像中查找與原圖像歐氏距離最近的特征點和次近的特征點，利用比率法判斷是否匹配，即最近距離與次近距離相除，假如比值結(jié)果小于某個閾值(本文取0.6)，則確定該點為匹配點。

通常閾值選取值越小越好。通過對大量任意存在尺度、旋轉(zhuǎn)和亮度變化的兩幅圖片進行匹配，結(jié)果表明ratio取值在0.4～0.6之間最佳，小于0.4的很少有匹配點，大于0.6的則存在大量錯誤匹配點，因此本文選擇0.6作為閾值。

上述算法實現(xiàn)了兩幅圖像之間的單向匹配，為了提高匹配精度，本文將單向匹配進行改進，實現(xiàn)圖像間的雙向匹配。首先將原圖像和待匹配圖像實現(xiàn)匹配，獲取第一組匹配點對，接著反過來將待匹配圖像與原圖像實現(xiàn)匹配，獲取第二組匹配點對，將這兩組中相同的匹配點對提取出來作為最終的匹配結(jié)果。

1.5變換參數(shù)的計算

本文研究圖像間發(fā)生平移與旋轉(zhuǎn)的仿射變化關(guān)系，圖像進行特征點匹配后，根據(jù)匹配的特征點對可以得出單應性變換矩陣，從而進一步獲得圖像間的相對變化參數(shù)。

設(X,Y)和(x,y)為兩幅圖像的任意一對匹配點對，則有：

(3)

根據(jù)其變化關(guān)系，H矩陣可表示為：

(4)

其中，θ為旋轉(zhuǎn)角度，Δx、Δy分別為x方向和y方向的像素平移量。

為了提高H的計算精度，本文采用RANSAC[12]算法來消除誤匹配點對，從而獲得更準確的變換參數(shù)。RANSAC算法的基本內(nèi)容是：

1) 任意選取兩幅圖像的3組匹配點對，可估算出H矩陣的6個參數(shù)值；

2) 使用H矩陣對剩余的匹配點對來進行判別，對匹配的內(nèi)點和外點進行區(qū)分，并且記錄內(nèi)點的總體數(shù)量，用得到的新內(nèi)點再次計算H的各個參數(shù)；

3) 當內(nèi)點數(shù)量達到最多時，采用該組內(nèi)點計算H的最佳參數(shù)。

在程序中，使用cv::findHomography函數(shù)計算單應性變換，利用RANSAC算法求取最佳H矩陣。

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

實驗仿真平臺的硬件環(huán)境為：Intel(R)Core(TM)i3-2330MCPU，主頻2.20GHz，內(nèi)存2.00GB的PC機；軟件開發(fā)工具為：Windows7操作系統(tǒng)、VS2010+OpenCV2.4.9[13]。

為了驗證本文算法的快速性和正確性，對圖5所示大小為512×512的Lena圖像先進行特征點提取，然后分別進行平移和旋轉(zhuǎn)變化，采用本文算法和傳統(tǒng)的SURF算法進行特征匹配，計算出實際的平移量和旋轉(zhuǎn)量，并與理論值相比較。

圖5　Lena圖Fig.5　Lena figure

1) 分別用FAST角點檢測算法和SURF特征檢測算法對圖5進行特征點提取，如圖6所示，并統(tǒng)計出特征點的個數(shù)和檢測時間，如表1所示。對比可知，F(xiàn)AST算法相對于SURF算法檢測出的特征點數(shù)量多，而且運行時間較短，該算法提取的特征點進一步突出了圖像的細節(jié)，從而使匹配準確率得到了提高。

圖6　特征點檢測結(jié)果Fig.6　Results of feature point detection

表1　特征點檢測時間比較

2) 將圖5所示的圖像作為參考圖像，分別對其進行平移和旋轉(zhuǎn)變化，得到待配準圖像，然后采用本文提出的算法進行特征點匹配，如圖7和圖8所示，計算其平移量和旋轉(zhuǎn)量，并與理論值做比較，結(jié)果如表2所示。

圖7　平移變換匹配結(jié)果Fig.7　Translational transformation matching results

圖8　旋轉(zhuǎn)變換匹配結(jié)果Fig.8　Rotation transformation matching results

表2　圖像配準試驗數(shù)據(jù)

由圖7和圖8的匹配效果可以看出，本文算法對平移、旋轉(zhuǎn)變換具有良好的匹配效果。由表2可知，平移參數(shù)的最大誤差為0.022個像素，旋轉(zhuǎn)參數(shù)的最大誤差為0.045°。

為了進一步評價匹配結(jié)果，將本文的算法與傳統(tǒng)的SURF算法在匹配正確率和所用時間上進行比較，結(jié)果如表3所示。

由表3可看出，本文算法相比SURF算法在精確度和速度方面得到了很好的提升。這主要是由于FAST角點檢測器的優(yōu)良特性和SURF特征描述符的抗旋轉(zhuǎn)性，不僅使計算復雜度降低，速度加快，而且對旋轉(zhuǎn)變化具有一定不變性。

3　結(jié)　語

本文根據(jù)圖像匹配技術(shù)精度高、速度快的要求，提出了結(jié)合FAST-SURF和改進k-d樹最近鄰查找的圖像配準算法。該算法利用了FAST角點的快速性、穩(wěn)定性以及SURF描述子的抗旋轉(zhuǎn)性的優(yōu)點，采用改進的k-d樹BBF算法查找特征點，并對得到的特征點對進一步實現(xiàn)雙向匹配，得到初匹配點對，為了實現(xiàn)更精確的匹配，使用RANSAC算法消除誤匹配點。實驗結(jié)果表明，平移參數(shù)的最大誤差為0.022個像素，旋轉(zhuǎn)參數(shù)的最大誤差為0.045°，本算法實現(xiàn)了較高的匹配速度和精度。

[1]朱琳，王瑩，劉淑云，等. 基于改進快速魯棒特征的圖像快速拼接算法[J]. 計算機應用，2014，34(10)：2944-2947.

ZHU Lin, WANG Ying, LIU Shuyun, et al. Fast image stitching algorithm based on improved speed up robust feature[J]. Journal of Computer Applications, 2014, 34(10):2944-2947.

[2]SCHMID C, MOHR R, BAUCKHAGE C. Evaluation of interest point detector[J]. International Journal of Computer Vision, 2000, 37(2):151-172.

[3]SMITH S M, BRADY J M. SUSAN -A new approach to low level image processing[J]. International Journal of Computer Vision, 1997, 23(1):45-78.

[4]HARRIS C G, STEPHENS M J. A combined corner and edge detector[C]//Proceeding of 4th Alvey Vision Conference, 1988:147-151.

[5]張靜，桑紅石. 基于初始尺度變換的SIFT匹配算法[J].紅外與毫米波學報，2014，33(2)：177-182.

ZHANG Jing, SANG Hongshi. SIFT matching method based on base scale transformation[J]. Journal of Infrared and Millimeter Waves,2014,33(2):177-182.

[6]劉志文，劉定生，劉鵬. 應用尺度不變特征變換的多源遙感影像特征點匹配[J]. 光學精密工程，2013，21(8)：2146-2153.

LIU Zhiwen, LIU Dingsheng, LIU Peng. SIFT feature matching algorithm of multi-source remote image[J]. Optics and Precision Engineering, 2013, 21(8): 2146-2153.

[7] LOWE D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision,2004,60(2):91-110.

[8]BAY H, TUYTELAARS T, VAN GOOL L. SURF: Speeded up robust features[C]//9th European Conference on Computer Vision, Graz, Austria, 2006: 404-417.

[9]ROSTEN E, DRUMMOND T. Machine learning for high-speed corner detection[C]//9th European Conference on Computer Vision, Graz, Austria, 2006: 430-443.

[10] 杜杰，劉亞秋，孫垚. 基于仿射不變閉合區(qū)域和SURF的圖像匹配算法[J]. 計算機應用研究，2014，31(1)：295-298.

DU Jie, LIU Yaqiu, SUN Yao. Image matching algorithm based on affine-invariant closed region and SURF[J]. Application Research of Computers,2014,31(1):295-298.

[11]堯思遠，王曉明，左帥. 基于SURF的特征點快速匹配算法[J]. 激光與紅外,2014,44(3):347-350.

YAO Siyuan, WANG Xiaoming, ZUO Shuai. Fast feature point matching algorithm based on SURF[J]. Laser & Infrared, 2014, 44(3):347-350.

[12]羅天健，劉秉瀚. 融合特征的快速SURF配準算法[J].中國圖象圖形學報，2015，20(1)：95-103.

LUO Tianjian, LIU Binghan. Fast SURF key-points image registration algorithm by fusion feature[J]. Journal of Image and Graphics,2015,20(1):95-103.

[13]BRADSKI G.Learning OpenCV[M].南京：東南大學出版社，2009：20.

(責任編輯王緒迪,王衛(wèi)勛)

Image matching algorithm combining FAST-SURF and improved k-d tree nearest neighbor search

CHEN Jianhong， HAN Xiaozhen

(School of Mechanical and Precision Instrument Engineering，Xi’an University of Technology，Xi’an 710048,China)

An algorithm combining FAST-SURF and improved k-d tree nearest neighbor search is proposed to solve the matching problem of translation and rotation changes between two images. Feature points are first extracted using FAST (Features from Accelerated Segment Test) corner detector, and then SURF (Speeded Up Robust Feature) descriptors are generated based on the feature points around the neighborhood information. And an improved k-d tree nearest neighbor search algorithm BBF (Best Bin First) is adopted to find out the feature highlights of two nearest neighbor points. The preliminary match point is obtained by bidirectional matching, and finally RANSAC (Random Sample Consensus) algorithm is adopted to eliminate false matching points, with findHomography function used to find transformation matrix to calculate the relative amount of translation and rotation of the two images. Experimental results are superior to traditional SURF image matching algorithm with the maximum error of the algorithmic translation parameter being 0.022 pixels, and the maximum error of rotation parameters is 0.045 degree, thus achieving a fast and accurate precision of the image registration.

images matching; FAST-SURF algorithm; BBF; bidirectional matching; RANSAC

1006-4710(2016)02-0213-05

10.19322/j.cnki.issn.1006-4710.2016.02.014

2015-08-14

陜西省自然科學基礎研究計劃資助項目(2012JM8006)；陜西省教育廳科研計劃資助項目(2013JK1049)

陳劍虹，男，副教授，博士，研究方向為光電檢測與光譜分析。E-mail: chenjianhong@xaut.edu.cn

TP391.4

A