改進(jìn)的尺度不變特征轉(zhuǎn)換匹配算法

茅正沖，王 丹，唐雨玉

（江南大學(xué) 輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 無錫214122）

0 引 言

近年來，許多學(xué)者提出了不同的SIFT （scale－invariant feature transform algorithm）［1，2］改進(jìn)算法。文 獻(xiàn) ［3］提 出了Contourlet－SIFT 特征匹配算法，對尺度空間下旋轉(zhuǎn)不變特征進(jìn)行Contourlet變換后再進(jìn)行匹配，但是計(jì)算量偏大，不滿足實(shí)時(shí)性要求；文獻(xiàn) ［4］提出了基于D2OG 特征點(diǎn)檢測算子的改進(jìn)SIFT 特征匹配算法，適用于圖像信息豐富且對實(shí)時(shí)性要求較高的場合，但是算法提取的匹配點(diǎn)對數(shù)相對較少，限制了此算法處理的圖像類型；文獻(xiàn) ［5］提出了以街區(qū)距離代替歐氏距離作為特征描述符之間的相似性度量，降低了相似性度量公式的時(shí)間復(fù)雜度，但是沒有提高魯棒性；文獻(xiàn) ［6］提出了一種基于圖像Radon變化的改進(jìn)的SIFT 特征匹配算法，降低了SIFT 特征向量的維數(shù)，提高了特征匹配效率，但是在實(shí)際場景使用時(shí)性能有待提高；文獻(xiàn) ［7］提出了多尺度特征提取的雙目視覺匹配，雖然匹配率得到了提高，但是匹配耗時(shí)較長，時(shí)效性較差。

本文針對SIFT 算法運(yùn)行時(shí)間過長，匹配率不高的問題，提出了一種改進(jìn)的SIFT 算法。在原SIFT 算法基礎(chǔ)上，引入了二維Mallat快速小波變換算法，對待匹配圖像進(jìn)行預(yù)處理，重建圖像的低頻成分，以提高匹配速度；對高斯金字塔組數(shù)進(jìn)行調(diào)整，減少降采樣次數(shù)和高斯金字塔層數(shù)；通過優(yōu)化的隨機(jī)抽樣一致算法 （RANSAC）剔除誤匹配點(diǎn)。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法優(yōu)于原來的SIFT 算法，匹配率也有所提高。

1 二維Mallat小波變換

在利用小波變換進(jìn)行圖像處理的研究中，由于受到塔式算法的啟發(fā)，Mallat提出了一種快速的小波分解與重構(gòu)算法，即為馬拉特 （Mallat）算法［8］。

使用兩個相同的一維小波函數(shù)和一維尺度函數(shù)的乘積構(gòu)造二維小波基，生成的尺度函數(shù)和3個小波函數(shù)分別為

假設(shè)f ＝f（x，y）∈V2j為待分析的圖像信號，它的二維逼近圖像為下式所示

其中

然后再利用小波函數(shù)和尺度函數(shù)的正交性，可以得出

上式說明，j＋1尺度空間的尺度系數(shù)cj＋1（m，n）可以由j尺度空間的尺度系數(shù)cj（k，l）經(jīng)二維濾波器系數(shù)進(jìn)行加權(quán)求和得到。又

再引入一種矩陣算子，可以得出二維Mallat分解算法為

其中：Gr、Gc——用小波濾波器系數(shù)對行和列作用的算子，Hr、Hc——用尺度濾波器系數(shù)對行和列作用的算子。

而二維Mallat重構(gòu)算法為

通過二維Mallat小波變換分解后，得到了待配準(zhǔn)圖像的低頻成分和高頻成分。其中，低頻成分包含了大部分的圖像信息，而高頻成分主要包含的是噪聲，僅含有少量的信息，在進(jìn)行重構(gòu)時(shí)去掉高頻成分會使圖像匹配的魯棒性提高。實(shí)驗(yàn)結(jié)果表明，利用小波對圖像進(jìn)行多層分解時(shí)，2層以上的低頻成分的匹配點(diǎn)的數(shù)量非常少，分解層數(shù)越多，反而會增加匹配時(shí)間，所以本文采用的是2尺度分解。經(jīng)二維小波變換處理后的待配準(zhǔn)圖像，一方面可以減少每次參與匹配的像素點(diǎn)，提高了匹配速度，另一方面減少了弱匹配點(diǎn)，從而使誤匹配率下降。

2 尺度空間的構(gòu)造

SIFT 特征表征的不是圖像的全局特征，而是局部特征，在平移、旋轉(zhuǎn)、亮度變化和尺度縮放等方面具有良好的不變性［9］。SIFT 算法主要包括圖像特征點(diǎn)的提取以及特征點(diǎn)的匹配兩個方面［10］。特征點(diǎn)提取是指在不同的尺度空間上查找出圖像的關(guān)鍵點(diǎn)，并且計(jì)算出這些關(guān)鍵點(diǎn)的方向和大小，最后生成關(guān)鍵點(diǎn)描述子。SIFT 特征點(diǎn)的提取可分解為4個步驟，如圖1所示。

圖1 SIFT 算法步驟

一幅二維圖像I（x，y）的尺度空間L（x，y，σ）定義為一個變化尺度的高斯函數(shù)與原圖像的卷積［12］，即

式中：σ——尺度空間的空間尺度因子，G（x，y，σ）——高斯核函數(shù)，其定義為

為了能在尺度空間中檢測到穩(wěn)定的關(guān)鍵點(diǎn)，使用高斯差分 （DoG）算子近似尺度歸一化的拉普拉斯——高斯（LoG）算子。通過圖像與不同尺度的高斯差分卷積核生成

高斯金字塔分成O 組、S層，其中，O 和S一般取為4和5，下一組的第一層是通過上一組的最后一層降采樣得到的。在構(gòu)造尺度空間之前，本文已先利用二維小波變換對待配準(zhǔn)圖像進(jìn)行預(yù)處理，舍棄了高頻成分，只保留了低頻成分對其進(jìn)行重建，包含的信息已經(jīng)有所減少，所以沒有必要做與原來一樣的降采樣次數(shù)。因此，本文通過對高斯金字塔的組數(shù)和層數(shù)進(jìn)行調(diào)整，從而減少降采樣次數(shù)，縮短尺度空間建立的時(shí)間。

經(jīng)過二維小波變換處理過的圖像，不包含圖像的高頻能量，即去掉了少部分的有效的信息和噪聲。在對圖像構(gòu)建高斯金字塔時(shí)，金字塔的最后一層包含了很少的興趣點(diǎn)，對最終的匹配結(jié)果沒有太大的影響。所以，去除掉由高斯金字塔生成高斯差分金字塔的最后一層。文獻(xiàn) ［11］列出了保持其它條件不變，改變不同的降采樣次數(shù)和高斯金字塔層數(shù)下的匹配結(jié)果和時(shí)間。當(dāng)高斯金字塔減少2層，降采樣次數(shù)減少2次時(shí)，沒有足夠多的匹配點(diǎn)保證匹配的準(zhǔn)確性，所以本文只將最后一層高斯金字塔出除。實(shí)驗(yàn)結(jié)果表明，通過對降采樣次數(shù)和高斯差分金字塔的層數(shù)進(jìn)行調(diào)整，不僅減少了匹配特征點(diǎn)所需要的時(shí)間，同時(shí)一些誤匹配點(diǎn)也可以去除，從而提高了匹配效率。

3 特征點(diǎn)匹配

本文采用K－近鄰算法對生成的SIFT 特征向量進(jìn)行匹配。假設(shè)最近鄰特征點(diǎn)與待匹配點(diǎn)的距離為d1，次近鄰與待匹配點(diǎn)的距離為d2，當(dāng)d1＜0.8＊d2時(shí)，則認(rèn)為最近鄰特征點(diǎn)是正確匹配點(diǎn)，特征點(diǎn)對匹配。在計(jì)算特征點(diǎn)之間的歐氏距離時(shí)，采用了BBF算法來處理128維的特征向量。

在對所有特征點(diǎn)進(jìn)行粗匹配之后，使用RANSAC 算法估計(jì)兩個圖像對之間的單位變換矩陣并將其作為幾何約束，進(jìn)而去除一些誤匹配點(diǎn)，完成圖像之間的精確匹配，提高匹配效率。

4 實(shí)驗(yàn)結(jié)果和分析

為了比較改進(jìn)后的SIFT 算法對光照、旋轉(zhuǎn)、尺度縮放均具有良好的魯棒性，而且在正確匹配率和匹配時(shí)間上的變化，本節(jié)從光照、旋轉(zhuǎn)、尺度3 個方面進(jìn)行研究分析。實(shí)驗(yàn)平臺是CPU 2.5GHz、內(nèi)存4.00G 的筆記本電腦，軟件平臺為MATLAB2013a。實(shí)驗(yàn)圖片分別從光照、旋轉(zhuǎn)、尺度三方面選取，圖像大小均為320＊320。

4.1 性能評價(jià)指標(biāo)

本文采用正確匹配率和匹配耗時(shí)作為算法性能的評價(jià)指標(biāo)。

正確匹配率指的是匹配正確的特征對數(shù)與所有匹配上的特征對數(shù)之比，正確匹配率越高，誤匹配率就越低，則說明算法魯棒性越好。公式表示如下

匹配耗時(shí)指的是從構(gòu)建尺度空間開始一直到匹配結(jié)束。

4.2 結(jié)果分析

本文利用改進(jìn)的SIFT 算法對不同類型的圖片進(jìn)行多次匹配實(shí)驗(yàn)，并與原始的SIFT方法和文獻(xiàn) ［7］提出的雙目視覺匹配算法進(jìn)行對比。圖2～圖4分別為不同光照下的匹配結(jié)果、不同視角下的匹配結(jié)果和不同尺度下的匹配結(jié)果。表1～表3分別為這3種情況下的正確匹配率和匹配耗時(shí)對比。

從圖2、圖3、圖4可以看出，使用本文算法產(chǎn)生的匹配對相較于原始SIFT 算法減少了，同時(shí)誤匹配對也相對減少了。雖然本文加入了小波變換，增加了小波變換的時(shí)間，但是最后總的匹配耗時(shí)減少了。然而相較于雙目視覺匹配算法，在不同視角和不同尺度下產(chǎn)生的總匹配對相對多一些，誤匹配對也相差無幾。

圖2 不同光照下的匹配結(jié)果

圖3 不同視角下的匹配結(jié)果

表1 不同光照下的匹配結(jié)果對比

圖4 不同尺度下的匹配結(jié)果

表2 不同視角下的匹配結(jié)果對比

表3 不同尺度下的匹配結(jié)果對比

根據(jù)圖2～圖4得出的數(shù)據(jù)和算法運(yùn)行時(shí)間制成表1～表3。從表1、表2、表3可以看出，采用本文算法在不同條件下對圖像進(jìn)行匹配，正確匹配率都有明顯地提高，剔除了很多錯誤的匹配對，并且匹配耗時(shí)也有明顯地減少，優(yōu)于原始的SIFT 算法，運(yùn)行時(shí)間相對于原始的SIFT 算法減少了一半多。相對于雙目視覺匹配算法，本文算法在不同尺度下的正確匹配率略低一些，但是本文算法匹配耗時(shí)遠(yuǎn)小于雙目視覺匹配算法，運(yùn)行時(shí)間明顯減少了很多，大大減小了計(jì)算量，時(shí)效性得到了提高。

從實(shí)驗(yàn)結(jié)果可以得出，運(yùn)用本文算法在光照、旋轉(zhuǎn)、尺度方面均具有良好的魯棒性和時(shí)效性。取二維Mallat快速小波變換后的圖像進(jìn)行匹配，圖像的特征點(diǎn)數(shù)均有一定數(shù)量的減少，正確匹配率增加了。在構(gòu)建尺度空間時(shí)，通過減少一次降采樣次數(shù)使構(gòu)建尺度空間的時(shí)間縮短了，提高了時(shí)效性，并且運(yùn)用RANSAC 算法剔除了部分誤匹配點(diǎn)。改進(jìn)后的SIFT 算法雖然特征點(diǎn)減少了，但是仍有足夠的特征點(diǎn)保證匹配的正確性，優(yōu)于原來的SIFT 算法。

5 結(jié)束語

由于SIFT 算法計(jì)算時(shí)間過長，在實(shí)際應(yīng)用中，不能滿足實(shí)時(shí)性的要求，針對這一問題，本文提出了一種改進(jìn)的SIFT 算法。實(shí)驗(yàn)結(jié)果表明，該算法不僅保留了原來SIFT算法在光照、旋轉(zhuǎn)、尺度等方面具有很好的魯棒性的特點(diǎn)，而且縮短了匹配時(shí)間，提高了正確匹配率，具有良好的匹配效果。但是，需要指出的是，為了使SIFT 算法能夠更好地運(yùn)用于實(shí)際中，時(shí)效性還有待提高，而且在匹配時(shí)還存在少量的誤匹配對。因此還需要在時(shí)效性和匹配率上對本文的算法進(jìn)行改進(jìn)，這將是下一步的研究方向，并為運(yùn)動目標(biāo)跟蹤等方面做好準(zhǔn)備。

［1］Liao Kaiyang，Liu Guizhong，Hui Youshi.An improvement to the SIFT descriptor for image representation and matching ［J］.Pattern Recognition Letters，2013，34 （11）：1211－1220.

［2］LIU Pingping，ZHAO Hongwei.A fast local feature description algorithm ［J］.Acta Automatica Sinica，2010，36 （1）：40－45 （in Chinese）.［劉萍萍，趙宏偉.一種快速局部特征描述算法 ［J］.自動化學(xué)報(bào)，2010，36 （1）：40－45.］

［3］CHEN Shurong，LI Bo，DONG Rong.Contourlet－SIFT feature matching algorithm ［J］.Journal of Electronic ＆Information Technology，2013，35 （5）：1215－1221 （in Chinese）.［陳抒瑢，李勃，董蓉.Contourlet－SIFT 特征匹配算法 ［J］.電子與信息學(xué)報(bào)，2013，35 （5）：1215－1221.］

［4］CAO Juan，LI Xingwei，LIN Weiting，et al.Study on improved SIFT feature matching algorithm ［J］.Journal of System Simulation，2010，22 （11）：2760－2763 （in Chinese）.［曹娟，李興瑋，林偉廷，等.SIFT 特征匹配算法改進(jìn)研究［J］.系統(tǒng)仿真學(xué)報(bào)，2010，22 （11）：2760－2763.］

［5］YANG Xingfang，CAO Yumei，HAN Xuzhao，et al.A method for improving matching efficiency of SIFT feature ［J］.China Mechanical Engineering，2012，23 （11）：1297－1301（in Chinese）. ［楊幸芳，曹玉美，韓旭炤，等.一種提高SIFT 特征匹配效率的方法 ［J］.中國機(jī)械工程，2012，23（11）：1297－1301.］

［6］YU Lili，DAI Qing.Improved SIFT feature matching algorithm ［J］.Computer Engineering，2011，37 （2）：210－212（in Chinese）.［于麗莉，戴青.一種改進(jìn)的SIFT 特征匹配算法 ［J］.計(jì)算機(jī)工程，2011，37 （2）：210－212.］

［7］KONG Jun，TANG Xinyi，JIANG Min.Matching algorithm of binocular vision based on multi－scale feature extraction ［J］.Computer Engineering and Applications，2010，46 （33）：1－5（in Chinese）.［孔軍，湯心溢，蔣敏.多尺度特征提取的雙目視覺匹配 ［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46 （33）：1－5.］

［8］HOU Yi，ZHOU Shilin.Invariant feature with multi－characteristic scales using gabor filter bank ［J］.Acta Electronica Sinica，2013，41 （6）：1146－1152 （in Chinese）. ［候毅，周石琳.基于Gabor濾波器組的多特征尺度不變特種證提取方法［J］.電子學(xué)報(bào)，2013，41 （6）：1146－1152.］

［9］Zhang Qi，Rui Ting，F(xiàn)ang Hushang.Particle filter object tracking based on Harris－SIFT feature matching ［J］.Procedia Engineering，2012，29：924－929.

［10］Zhong Sheng，Wang Jianhui，Yan Luxin.A real－time embedded architecture for SIFT ［J］.Journal of Systems Architecture，2013，59 （1）：16－29.

［11］LI Ming.Research on object tracking algorithm based on SIFT feature－points matching ［D］.Hefei：Hefei University of Technology，2008 （in Chinese）.［李明.基于SIFT 特征點(diǎn)匹配的目標(biāo)跟蹤算法研究［D］.合肥：合肥工業(yè)大學(xué)，2008.］

［12］DONG Wenhui，CHANG Faliang，LI Tianping.Adaptive fragments－based target tracking method using color histogram and SIFT features［J］.Journal of Electronics ＆Information，2013，35 （4）：770－776 （in Chinese）.［董文會，常發(fā)亮，李天平.融合顏色直方圖及SIFT 特征的自適應(yīng)分塊目標(biāo)跟蹤方法 ［J］.電子與信息學(xué)報(bào)，2013，35 （4）：770－776.］