基于改進(jìn)SURF的快速圖像配準(zhǔn)算法*

胡旻濤， 彭 勇， 徐 赟

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122)

基于改進(jìn)SURF的快速圖像配準(zhǔn)算法*

胡旻濤， 彭 勇， 徐 赟

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無錫214122)

針對傳統(tǒng)加速魯棒特征(SURF)匹配算法存在實(shí)時(shí)性不高，誤匹配等問題，提出了基于改進(jìn)SURF特征提取快速的圖像配準(zhǔn)算法。利用快速黑塞(Hessian)矩陣提取圖像特征點(diǎn)，根據(jù)圖像熵信息對特征點(diǎn)進(jìn)行篩選，采用改進(jìn)的快速近鄰搜索算法進(jìn)行特征匹配，到用隨機(jī)抽樣一致(RANSAC)算法剔除誤匹配對。實(shí)驗(yàn)表明：改進(jìn)后的算法有效改善了匹配效率，提高了匹配準(zhǔn)確度。

加速魯棒特征； 圖像熵； 最近鄰搜索； 圖像配準(zhǔn)

0 引 言

圖像配準(zhǔn)是圖像處理過程中的關(guān)鍵技術(shù)，在目標(biāo)識別、圖像拼接、變化檢測、目標(biāo)跟蹤、三維重建等領(lǐng)域得到了廣泛應(yīng)用[1]。圖像配準(zhǔn)的算法主要分為基于灰度的匹配和基于特征的匹配兩大類[2,3]?；谔卣鞯钠ヅ浞椒ㄓ?jì)算量小，魯棒性強(qiáng)，是目前研究的主流。

2004年，Lowe D G提出了尺度不變特征變換 (scale invariant feature transform，SIFT)算法[4]，通過構(gòu)造尺度空間尋找極值點(diǎn)，提取極值點(diǎn)位置、尺度、旋轉(zhuǎn)不變特征量對圖片進(jìn)行匹配。2006年，Bay H等人提出了加速魯棒特征(speed up robust features,SURF)算法[5]，該算法引入了積分圖像和箱式濾波器，優(yōu)化了特征點(diǎn)搜索的過程。Luo J等人通過測試驗(yàn)證了SURF算法，在圖像發(fā)生尺度、光照、模糊變化時(shí)均有較好的魯棒性并且提高了運(yùn)算速度[6]。但在實(shí)際應(yīng)用中，SURF算法有大量特征點(diǎn)未進(jìn)行匹配，影響了匹配效率；高維數(shù)據(jù)的匹配開銷也很大，占用了較多時(shí)間；同時(shí)也存在著匹配錯(cuò)誤的情況。文獻(xiàn)[7]將現(xiàn)有SURF特征改進(jìn)，利用三角特征和對角線特征設(shè)計(jì)了新的描述算法，提高了算法的運(yùn)算速度。文獻(xiàn)[8]提出了一種改進(jìn)算法，利用擴(kuò)散距離代替歐氏距離進(jìn)行匹配，利用隨機(jī)抽樣一致(RANSAC)算法從候選匹配中排除錯(cuò)誤的匹配。文獻(xiàn)[9]引入了擴(kuò)展哈希算法，利用其較高的局部敏感性加速了高維特征向量的匹配。針對目前算法存在的問題，本文提出了一種改進(jìn)的SURF算法，引入特征點(diǎn)篩選機(jī)制剔除冗余特征點(diǎn)，并結(jié)合改進(jìn)的快速近鄰搜索算法加速特征點(diǎn)匹配，并采用RANSAC算法減少誤匹配對。

1 SURF算法

SURF算子的檢測基于尺度空間，采用黑塞(Hessian)矩陣提取特征點(diǎn)。給定圖像I中的某點(diǎn)(x,y)，在該點(diǎn)處，尺度為σ的Hessian矩陣H(x，σ)定義為

(1)

SURF算子使用盒裝濾波器，構(gòu)造快速Hessian矩陣。根據(jù)圖像的Hessian行列式值找出特征點(diǎn)的位置，并建立64位的特征描述向量，最后根據(jù)描述向量之間的歐氏距離實(shí)現(xiàn)特征點(diǎn)的匹配。

2 本文算法

2.1 特征點(diǎn)檢測算法改進(jìn)

采用SURF算法提取特征點(diǎn)進(jìn)行匹配時(shí)，當(dāng)檢測圖像的細(xì)節(jié)比較豐富時(shí)，提取特征點(diǎn)的數(shù)量較大而且分布不均勻，導(dǎo)致后續(xù)特征描述和匹配的時(shí)間大幅增加，同時(shí)誤匹配的數(shù)量也會增加，匹配效果變差[10]。通常,包含信息量較少的特征點(diǎn)成功匹配的幾率遠(yuǎn)遠(yuǎn)小于信息量豐富的特征點(diǎn)。本文引入圖像信息熵剔除冗余特征點(diǎn)。

對于一幅m×n的圖像，信息熵[11，12]的近似公式為

(2)

pi,j=f(i,j)/σ2

(3)

為了盡可能保留圖像細(xì)節(jié)，可將圖像劃分為不同區(qū)域，設(shè)定不同的圖像熵閾值。區(qū)域中熵值大于該閾值的特征點(diǎn)則認(rèn)為是有效的特征點(diǎn)，將其保留。具體特征點(diǎn)檢測步驟：

1)利用快速Hessian矩陣遍歷圖像，計(jì)算每個(gè)點(diǎn)的行列式值，設(shè)定Hessian矩陣響應(yīng)值閾值T，將圖像中行列式值低的點(diǎn)去除。利用非最大值抑制法與插值法在其余的像素點(diǎn)中找到特征點(diǎn)；

2)將原圖劃分為3×3共9個(gè)區(qū)域,分別計(jì)算出每個(gè)區(qū)域的信息熵作為該區(qū)域的熵閾值，將每個(gè)區(qū)域中熵值小于熵閾值的特征點(diǎn)去除；

3)對保留的特征點(diǎn)采用原SURF算法構(gòu)建成64位特征描述向量并進(jìn)行歸一化處理。

2.2 特征向量匹配算法改進(jìn)

特征點(diǎn)匹配，通過某種相似性度量建立兩類圖像特征之間一一對應(yīng)關(guān)系，一般采用歐式距離進(jìn)行度量。歐氏距離越小，表明特征向量的相似度越高。特征向量P和Q的歐氏距離可以表示為

(4)

2009年,Muja M等人通過歸納總結(jié)提出了一種高維數(shù)據(jù)的快速最近鄰匹配算法[13，14]，但在實(shí)際應(yīng)用中常常出現(xiàn)誤匹配的問題。

本文提出了一種改進(jìn)的快速近鄰匹配算法。通過設(shè)定距離閾值刪除相似度較低的匹配對，引入雙向匹配機(jī)制確保匹配對的唯一性。算法步驟：

1)采用快速近鄰匹配算法找到圖像B中與圖像A具有最小歐氏距離的初始匹配點(diǎn)并建立合集{p,p′};

2)根據(jù)所有匹配點(diǎn)對的歐氏距離d找出最小距離dmin，設(shè)置距離閾值D=μ×dmin。(本文μ=2);

3)判斷匹配點(diǎn)對的距離與閾值的大小，若d≥D，則剔除該匹配點(diǎn)對;

4)按照上述方法再找出圖像A中與圖像B具有最小歐氏距離的匹配點(diǎn)對合集{q,q′}，將兩次匹配結(jié)果進(jìn)行比較，只保留正反兩次匹配結(jié)果一致的匹配點(diǎn)對。

根據(jù)最小距離dmin設(shè)定的距離閾值能有效過濾不相干的匹配點(diǎn)對，同時(shí)圖像雙向匹配策略能夠保證匹配點(diǎn)對的唯一性，提高了匹配正確率。

2.3 隨機(jī)樣本一致性算法

上述初始計(jì)算得到的匹配集中仍包含有錯(cuò)誤的匹配點(diǎn)對，可以使用隨機(jī)樣本一致性 (random sample consensus，RANSAC)算法去除誤匹配對。RANSAC算法是一種基于概率的魯棒的參數(shù)估計(jì)法，計(jì)算得到有效樣本數(shù)據(jù)。具體步驟如下：

1)將匹配結(jié)果作為候選匹配特征集，從候選匹配特征點(diǎn)對中隨機(jī)選取4組匹配點(diǎn)建立方程組，估計(jì)變換矩陣M的8個(gè)未知參數(shù)。

2)計(jì)算剩余特征點(diǎn)經(jīng)過變換矩陣M的變換，并計(jì)算與其候選匹配點(diǎn)之間的距離，距離小于某一閾值，則該候選特征點(diǎn)為內(nèi)點(diǎn)；否則，為外點(diǎn)。

3)找出內(nèi)點(diǎn)數(shù)目最多的估計(jì)，將判斷出的外點(diǎn)剔除，用所有內(nèi)點(diǎn)進(jìn)行最優(yōu)參數(shù)估計(jì)。

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

實(shí)驗(yàn)硬件環(huán)境為Windows 10系統(tǒng)，CPU Intel(R) Core(TM)i5—4200 2.8 GHz，8 GB內(nèi)存的PC機(jī)；軟件開發(fā)平臺為Visual studio 2010和OpenCV2.4.9。使用ukbench標(biāo)準(zhǔn)圖像庫[15]進(jìn)行算法測試，所有圖片分辨率均為640×480。

3.1 圖像匹配效果實(shí)驗(yàn)

在標(biāo)準(zhǔn)圖像庫中選取4幅具有典型變換特征的圖像進(jìn)行實(shí)驗(yàn)，測試圖像如圖1所示。

圖1 實(shí)驗(yàn)圖像

為了驗(yàn)證算法的性能，引入recall vs 1-precision曲線作為評價(jià)標(biāo)準(zhǔn)。其中召回率(recall)指所有正確的特征點(diǎn)被檢測出的比例，精度(precision)指檢測出的點(diǎn)中正確的比例。當(dāng)曲線越靠近Y軸時(shí)說明匹配效果越好。如圖2為圖像發(fā)生尺度、模糊、旋轉(zhuǎn)、光照變化下2種算法的性能比較?？梢钥闯?在不同的環(huán)境下本文的算法的曲線整體高于原SURF算法，更靠近Y軸，說明匹配效果更好，能更好地完成實(shí)際需求。但2種算法在旋轉(zhuǎn)變換時(shí)匹配效果欠佳。

圖2 不同環(huán)境情況下圖像匹配性能比較

3.2 圖像匹配效率實(shí)驗(yàn)

在標(biāo)準(zhǔn)數(shù)據(jù)庫中選取50組圖片進(jìn)行測試。表1統(tǒng)計(jì)了2種算法檢測出的平均匹配對數(shù)，平均準(zhǔn)確率和平均匹配時(shí)間。分析數(shù)據(jù)可知：改進(jìn)后的算法因?yàn)橐肓嘶趫D像熵的特征點(diǎn)篩選機(jī)制，刪除了部分冗余的特征點(diǎn)，減少了特征向量描述和匹配的時(shí)間，提高了算法的速度，并且提高了匹配的準(zhǔn)確率，證明了本文算法在各種情況下均能保持較好的魯棒性。

表1 本文算法和SURF算法匹配效率比較

4 結(jié)束語

分析了目前SURF算法所存在的問題，提出了一種改進(jìn)的SURF算法。利用快速Hessian矩陣檢測特征點(diǎn)，引入圖像信息熵篩選特征點(diǎn)，用改進(jìn)的快速近鄰算法進(jìn)行特征向量匹配，采用RANSAC算法剔除誤匹配，有效地減少了計(jì)算時(shí)間，并且提高了匹配準(zhǔn)確率。實(shí)驗(yàn)表明:本文算法在縮放、旋轉(zhuǎn)、光照、模糊變化下均有良好的魯棒性。下一步工作將在運(yùn)動目標(biāo)跟蹤和定位方面展開。

[1] 盧 浩，胡華平，劉譚博怡.圖像特征提取與匹配[D].北京：中國科學(xué)院自動化研究所,2008.

[2] Goshtasby A A.References[M]∥2D and 3D image registration:For medical,remote sensing,and industrial applications.Hoboken:John Wiley & Sons Inc,2005.

[3] Duan C,Meng X,Tu C,et al.How to make local image features more efficient and distinctive[J].Iet Computer Vision,2008,2(3):178-189.

[4] Lowe D G.Distinctive image features from scale-invariant key-points[J].International Journal of Computer Vision,2004,60(2):91-110.

[5] Bay H,Tuytelaars T,Gool L V.SURF:Speeded up robust features[J].Computer Vision & Image Understanding,2006,110(3):404-417.

[6] Luo J,Gwun O.A comparison of SIFT,PCA-SIFT and SURF[J].International Journal of Image Processing,2009,3(4):143-152.

[7] 劉少鵬,郎躍東,丁祝順.改進(jìn)的SURF算法及其在目標(biāo)跟蹤中的應(yīng)用[J].傳感器與微系統(tǒng),2012,31(12):148-152.

[8] 貢 超,蔣建國,齊美彬.基于擴(kuò)散距離的SURF特征圖像匹配算法[J].合肥工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版,2015,38(4):474-478.

[9] 吳銘心.一種基于SURF和擴(kuò)展哈希的空間約束圖像匹配算法[J].重慶師范大學(xué)學(xué)報(bào):自然科學(xué)版,2015,32(2):104-110.

[10] 高素青,譚勛軍,黃承夏.一種基于SURF的圖像配準(zhǔn)改進(jìn)算法[J].解放軍理工大學(xué)學(xué)報(bào):自然科學(xué)版,2013,14(4):372-376.

[11] 聶仁燦,周冬明,趙東風(fēng).基于Unit-Linking PCNN和圖像熵的圖像分割新方法[J].系統(tǒng)仿真學(xué)報(bào),2008,20(1):222-227.

[12] 楊作廷,阮 萍,翟 波.基于圖像熵的高動態(tài)范圍場景的自動曝光算法[J].光子學(xué)報(bào),2013,42(6):742-746.

[13] Muja M,Lowe D G.Scalable nearest neighbor algorithms for high dimensional data[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2014,36(11):2227-2240.

[14] 梁艷菊,李 慶,林蓁蓁,等.一種基于SURF的全景圖像配準(zhǔn)算法[J].傳感器與微系統(tǒng),2012,31(5):132-135.

[15] The University of Kentucky Center for Visualization & Virtual Environments.Object recognition benchmark[EB/OL].(2016—04—12)http:∥www.vis.uky.edu/～stewe/ukbench/.

FastimagematchingalgorithmbasedonimprovedSURF*

HU Min-tao， PENG Yong， XU Yun

(SchoolofInternetofThingsEngineering,JiangnanUniversity,Wuxi214122,China)

Aiming at problem of poor real-time and false matching of images matching algorithm based on speed up robust features(SURF),present an images matching algorithm based on improved SURF.Features point of image is extracted by using the Fast-Hessian matrix.Features point is sifting by image entropy information.RANSAC algorithm is used to exclude mistake matching pair.The experiments show that this algorithm improves matching efficiency,and improve matching accuracy.

speed up robust features(SURF); image entropy; nearest neighbor search; image matching

10.13873/J.1000—9787(2017)11—0151—03

TP 391.41

A

1000—9787(2017)11—0151—03

2016—11—28

江蘇省交通運(yùn)輸廳資助項(xiàng)目(2012X08—2)

胡旻濤(1991-)，男，碩士研究生,主要研究方向?yàn)闄C(jī)器視覺、嵌入式系統(tǒng)，E—mail:420855432@qq.com。