胡旻濤， 彭 勇， 徐 赟

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

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

胡旻濤， 彭 勇， 徐 赟

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

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

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

0 引 言

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

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

1 SURF算法

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

(1)

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

2 本文算法

2.1 特征點檢測算法改進

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

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

(2)

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

(3)

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

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

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

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

2.2 特征向量匹配算法改進

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

(4)

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

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

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

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

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

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

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

2.3 隨機樣本一致性算法

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

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

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

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

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

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

3.1 圖像匹配效果實驗

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

圖1 實驗圖像

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

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

3.2 圖像匹配效率實驗

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

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

4 結(jié)束語

分析了目前SURF算法所存在的問題，提出了一種改進的SURF算法。利用快速Hessian矩陣檢測特征點，引入圖像信息熵篩選特征點，用改進的快速近鄰算法進行特征向量匹配，采用RANSAC算法剔除誤匹配，有效地減少了計算時間，并且提高了匹配準(zhǔn)確率。實驗表明:本文算法在縮放、旋轉(zhuǎ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] 劉少鵬,郎躍東,丁祝順.改進的SURF算法及其在目標(biāo)跟蹤中的應(yīng)用[J].傳感器與微系統(tǒng),2012,31(12):148-152.

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

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

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

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

[12] 楊作廷,阮 萍,翟 波.基于圖像熵的高動態(tài)范圍場景的自動曝光算法[J].光子學(xué)報,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

江蘇省交通運輸廳資助項目(2012X08—2)

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