基于改進(jìn)SIFT算法在圖像匹配中的研究*

彭興璇，唐雪嬌，董 星（遼寧師范大學(xué) 數(shù)學(xué)學(xué)院，遼寧 大連 116029）

基于改進(jìn)SIFT算法在圖像匹配中的研究*

彭興璇，唐雪嬌，董 星
（遼寧師范大學(xué) 數(shù)學(xué)學(xué)院，遼寧 大連 116029）

對(duì)于邊界顯著的圖像，用二值圖像代替灰度圖像進(jìn)行SIFT特征匹配，節(jié)約了運(yùn)行時(shí)間。同時(shí)在SIFT算法中用128維的特征描述子進(jìn)行特征描述影響了算法的實(shí)時(shí)性，用歐氏距離進(jìn)行匹配對(duì)算法的準(zhǔn)確性有一定的影響。提出了一種改進(jìn)SIFT算法，用64維的特征描述子以及加權(quán)的歐式距離進(jìn)行匹配。實(shí)驗(yàn)結(jié)果表明，所提出的改進(jìn)方法在提高準(zhǔn)確率的同時(shí)還減少了運(yùn)行時(shí)間。

SIFT算法；二值圖像；特征描述子；加權(quán)歐式距離

0 引言

目前圖像匹配的方法主要分為基于灰度的匹配方法［3］和基于特征的匹配方法［4］。前者直接利用圖像灰度進(jìn)行匹配，算法比較簡(jiǎn)單，但對(duì)噪聲等干擾比較敏感，匹配效率普遍較低。后者對(duì)形變、旋轉(zhuǎn)及平移的適應(yīng)性較好。SIFT（Scale Invariant Feature Transform）算法是一種相對(duì)穩(wěn)定的局部特征匹配算法［5］。

SIFT算法雖然可以對(duì)旋轉(zhuǎn)和平移在圖像匹配過(guò)程中的干擾進(jìn)行處理，但它也存在算法效率低、匹配精度差等問(wèn)題。本文提出了一種對(duì)于邊界顯著圖像的改進(jìn)的新方法，利用二值圖像代替灰度圖像，簡(jiǎn)化了圖像信息，利用64維特征描述子并且用加權(quán)的歐式距離進(jìn)行匹配。試驗(yàn)證明該方法不僅提高了算法的精度和準(zhǔn)確率，而且在邊界顯著的圖像的匹配中也有較好的適用性。

1 SIFT算法

SIFT算法主要包括尺度不變空間的特征點(diǎn)檢測(cè)、特征點(diǎn)信息描述、特征向量的匹配。

1.1 尺度不變空間的特征點(diǎn)檢測(cè)

在對(duì)尺度不變空間進(jìn)行特征點(diǎn)檢測(cè)時(shí)，首先要提取出尺度不變空間的極值點(diǎn)，然后精確定位特征點(diǎn)，最后為每個(gè)特征點(diǎn)分配方向。

尺度不變空間的極值點(diǎn)檢測(cè)。通過(guò)高斯核產(chǎn)生多尺度空間的核［6］。一幅二維圖像 I（x，y）與尺度可變高斯函數(shù) G（x，y，σ）做卷積，可得到該圖像的尺度不變空間 L （x，y，σ）如式（1）所示。

秦風(fēng)是新來(lái)的轉(zhuǎn)校生，老家重慶。他的到來(lái)在班上引起了小小的震動(dòng)，畢竟平日里的學(xué)習(xí)生活太單調(diào)枯燥了，突然來(lái)了一個(gè)新同學(xué)，大家都充滿了好奇。可他太靦腆，只是低著頭害羞的笑，大家熱鬧一陣子也就散了。我作為班長(zhǎng)，希望秦風(fēng)能夠早點(diǎn)融入班集體，更何況他還是我的新同桌，而且老師也希望我能夠幫助他，讓他早日熟悉學(xué)校里的一切。

其中，（x，y）表示圖像中像素點(diǎn)的坐標(biāo)，*是卷積，σ是尺度空間因子。通過(guò)對(duì)高斯尺度空間進(jìn)行采樣來(lái)建立高斯金字塔；再對(duì)相鄰兩層的高斯金字塔相減，生成高斯差分尺度空間（DOG scale-space）金字塔，即：

如果某點(diǎn)比DOG尺度空間中本層的8個(gè)點(diǎn)以及上下兩層的18個(gè)點(diǎn)都大或者都小，則把該點(diǎn)作為圖像在該尺度下的一個(gè)候選特征點(diǎn)，如圖1所示。

圖1 尺度空間局部極值檢測(cè)

在得到候選特征點(diǎn)之后，要檢測(cè)每個(gè)候選特征點(diǎn)的穩(wěn)定性，把檢測(cè)通過(guò)的特征點(diǎn)作為SIFT特征點(diǎn)。首先要對(duì)特征點(diǎn)中的邊緣響應(yīng)點(diǎn)和對(duì)比度較低的點(diǎn)進(jìn)行去除，然后構(gòu)造一個(gè)三元二次函數(shù)，利用此函數(shù)來(lái)更加精確特征點(diǎn)的位置和尺度。

為了使SIFT算法具備旋轉(zhuǎn)不變性，需要為每個(gè)特征點(diǎn)分配方向。像素點(diǎn)（x，y）處的梯度值與方向分別為：

其中，L中的尺度是該特征點(diǎn)所在的尺度。

在實(shí)際計(jì)算中，利用取值在0～360°范圍內(nèi)的梯度直方圖來(lái)對(duì)特征點(diǎn)的鄰域像素的梯度方向進(jìn)行統(tǒng)計(jì)，其中每10°代表著一個(gè)方向，共分為36個(gè)方向，并把直方圖中的峰值作為該特征點(diǎn)的方向。至此，完成尺度不變空間的特征點(diǎn)檢測(cè)，每一個(gè)特征點(diǎn)都包含了方向、尺度和位置信息。

1.2 特征點(diǎn)信息描述

為了確保算法具有旋轉(zhuǎn)不變性，要將坐標(biāo)軸旋轉(zhuǎn)到特征點(diǎn)的方向。然后在特征點(diǎn)的周圍取16×16的像素窗口，在4×4的小塊圖像上計(jì)算8個(gè)方向的梯度方向直方圖，對(duì)每個(gè)梯度方向的累加值進(jìn)行描繪，構(gòu)成一個(gè)種子點(diǎn)。用16個(gè)種子點(diǎn)來(lái)描述每個(gè)特征點(diǎn)，就此形成了128維的SIFT特征描述子。

1.3 特征向量的匹配

2 本文提出的改進(jìn)算法

2.1 圖像二值化

在原始SIFT算法中，利用原圖像的灰度圖像來(lái)構(gòu)造DOG尺度空間。而對(duì)于邊界顯著的圖像，它的邊界和輪廓信息比較重要，背景信息相對(duì)可以忽略，如果使用灰度圖像來(lái)進(jìn)行SIFT特征匹配，會(huì)使算法在背景信息上浪費(fèi)時(shí)間。

本文利用二值圖像代替灰度圖像，由于二值圖像的灰度值均為1或0，這對(duì)于極值點(diǎn)的選取和特征向量的描述與匹配都有所簡(jiǎn)化。

2.2 改進(jìn)后算法的特征描述子

由于SIFT特征向量高達(dá)128維，這為后來(lái)的匹配工作帶來(lái)了很大的計(jì)算量［7］，但是多數(shù)降維方法由于沒(méi)有考慮到SIFT的特點(diǎn)進(jìn)行降維，從而導(dǎo)致它的匹配效率下降。本文利用的降維方法從SIFT的自身特點(diǎn)出發(fā)進(jìn)行降維，在匹配效率不變的情況下成功地節(jié)約了匹配時(shí)間。

如圖2所示，對(duì)于一個(gè)種子的8個(gè)方向的梯度方向直方圖的累加值a0，a1，…，a7，用4個(gè)方向b0，b1，b2，b3來(lái)表示，如圖3所示。其中

圖2 一個(gè)種子的8個(gè)方向的梯度方向直方圖的累加值

圖3 種子的新表示方法

這樣描述每個(gè)種子的累加值的數(shù)量由8個(gè)降到了4個(gè)，但是這4個(gè)累加值仍然包含了8個(gè)累加值中所有的信息，所以即使特征描述子由128維降到64維，也不影響對(duì)特征點(diǎn)信息的描述，對(duì)匹配效率也不產(chǎn)生影響。在特征匹配時(shí)，由于特征向量的維數(shù)減少了一半，因此此方法為計(jì)算距離節(jié)約了時(shí)間，提高了算法的實(shí)時(shí)性。

2.3 用加權(quán)的歐式距離進(jìn)行匹配

利用歐氏距離進(jìn)行相似性度量的方法能夠解決匹配的問(wèn)題，但是不難發(fā)現(xiàn)生成的64維的描述子之間是不等價(jià)的，離特征點(diǎn)越近的種子所生成的描述子起的作用越大。因此本文的改進(jìn)方法為用加權(quán)的歐式距離代替歐式距離進(jìn)行圖像匹配，從而提高匹配效率。

ωmax的逐漸增大，相匹配的特征點(diǎn)的數(shù)量會(huì)逐漸減少，同時(shí)考慮到匹配的特征點(diǎn)數(shù)量和算法精度的因素，本文認(rèn)為當(dāng)閾值ωmax∈［1.01，1.50］時(shí)匹配效果較好。

3 實(shí)驗(yàn)與分析

本文設(shè)計(jì)了一系列的實(shí)驗(yàn)來(lái)檢測(cè)本文改進(jìn)算法的性能。為了更好地對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行比較，所有實(shí)驗(yàn)都是利用MATLAB7.10編程，運(yùn)行在配置為Intel（R）core（TM）2Duo CPU P7350@2.00GHz、操作系統(tǒng)為Microsoft Windows7的微機(jī)平臺(tái)上。選擇邊界顯著的圖像作為匹配對(duì)象。為了使本文改進(jìn)算法的性能得到更加全面的體現(xiàn)，實(shí)驗(yàn)結(jié)果從特征點(diǎn)個(gè)數(shù)、匹配點(diǎn)對(duì)、特征點(diǎn)匹配時(shí)間、算法運(yùn)行總時(shí)間以及正確匹配率5個(gè)方面對(duì)改進(jìn)算法與原算法進(jìn)行比較，如圖4、圖5和表1所示，其中改進(jìn)的SIFT算法取ωmax=1.15。

圖4 匹配效果圖（圖像一）

表1 圖像匹配比較數(shù)據(jù)

通過(guò)分析實(shí)驗(yàn)數(shù)據(jù)和匹配結(jié)果可以發(fā)現(xiàn)：改進(jìn)的算法由于用二值圖像進(jìn)行匹配，簡(jiǎn)化了圖像信息；同時(shí)用64維的特征描述子，大大節(jié)約了匹配的時(shí)間；用加權(quán)的歐式距離提高了算法的匹配率。由此可見本文的改進(jìn)算法運(yùn)算速度更快、準(zhǔn)確率更高。

4 結(jié)論

通過(guò)對(duì)SIFT算法的深入研究，本文就SIFT算法自身的不足進(jìn)行了改進(jìn)，利用二值圖像進(jìn)行特征匹配，同時(shí)在不影響匹配效率的前提下對(duì)SIFT算法成功地進(jìn)行了降維，最后用加權(quán)的歐式距離作為相似性度量進(jìn)行匹配。經(jīng)過(guò)大量的實(shí)驗(yàn)不難發(fā)現(xiàn)，對(duì)于邊界顯著的圖像，本文改進(jìn)的算法在匹配時(shí)間和匹配效率上都要優(yōu)于原始的SIFT算法。但本文改進(jìn)算法也有不足之處，匹配的特征點(diǎn)對(duì)相對(duì)較少，因此對(duì)該算法處理的圖像類型有一定的限制，所以如何改進(jìn)此問(wèn)題是下一步工作的重點(diǎn)。

［1］吳立德.計(jì)算機(jī)視覺［M］.上海：復(fù)旦大學(xué)出版社，1993.

［2］吳毅良.一種基于SIFT和SUSAN特征的圖像匹配方法［J］.微型機(jī)與應(yīng)用，2011，30（12）：33-35.

［3］MORTANI M，SATIONH F.Image template matching based on ratio of mean and central pixel in local area［J］.Proceedings of the SPIE The International Society for Optical Engineering，2007，67（94）：1-6.

［4］ZITOVA B，F(xiàn)LUSSER J.Image registration methods：a survey［J］.Image and Vision Computing，2003，21（11）：977-100.

［5］DAVID G L.Distinctive image features from scale-invariant keypoints［J］.International Journal of Computer Vision（S0920-5691），2004，60（2）：20.

［6］LINDEBERG T.Scale-space theory：a basic tool for analyzing structures at different scales［J］.Journal of Applied Statistics，1994，21（2）：225-270.

［7］Zhu Hongbo，Xu Xuejun，Wang Jing，et al.A rapid automatic image registration method based on improved SIFT［J］. Procedia Environmental Sciences，2011，11（A）：85-91.

作者簡(jiǎn)介：

朱道遠(yuǎn)（1988-），通信作者，男，碩士研究生，主要研究方向：圖像處理、模式識(shí)別。E-mail：zhudaoyuan2009@foxmail.com。

鄭勝（1965-），男，博士，教授，主要研究方向：圖像處理、模式識(shí)別、計(jì)算機(jī)視覺、神經(jīng)網(wǎng)絡(luò)。

曾祥云（1989-），男，碩士研究生，主要研究方向：圖像處理、神經(jīng)網(wǎng)絡(luò)。

Research for image matching based on improved SIFT algorithm

Peng Xingxuan，Tang Xuejiao，Dong Xing
（College of Mathematics，Liaoning Normail University，Dalian 116029，China）

Aiming at the images of salient boundary，this paper uses threshold images instead of gray ones to reduce the processing time.And 128-dimensional feature vector takes too much time to match.The computation of Euclidean distance reduces the efficiency of the algorithm.This paper proposes an improved SIFT algorithm.The improved algorithm uses 64-dimensional feature descriptor and the weighted Euclidean distance.Experimental results prove that the improved algorithm has higher matching accuracy and needs less matching time.

SIFT algorithm；threshold images；feature descriptor；weighted Euclidean distance

TP391

A

1674-7720（2015）20-0036-03

彭興璇，唐雪嬌，董星.基于改進(jìn)SIFT算法在圖像匹配中的研究［J］.微型機(jī)與應(yīng)用，2015，34（20）：36-38.

2015-07-16）

彭興旋（1979-），女，博士，副教授，碩士生導(dǎo)師，主要研究方向：計(jì)算幾何、圖像處理。

唐雪嬌（1990-），女，碩士研究生，主要研究方向：圖像處理。

董星（1990-），女，碩士研究生，主要研究方向：圖像處理。

遼寧省教育廳科學(xué)技術(shù)研究項(xiàng)目（ L2014428 ）