改進的尺度不變特征轉換匹配算法

茅正沖，王 丹，唐雨玉

（江南大學 輕工過程先進控制教育部重點實驗室，江蘇 無錫214122）

0 引 言

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

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

1 二維Mallat小波變換

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

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

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

其中

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

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

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

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

而二維Mallat重構算法為

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

2 尺度空間的構造

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

圖1 SIFT 算法步驟

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

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

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

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

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

3 特征點匹配

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

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

4 實驗結果和分析

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

4.1 性能評價指標

本文采用正確匹配率和匹配耗時作為算法性能的評價指標。

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

匹配耗時指的是從構建尺度空間開始一直到匹配結束。

4.2 結果分析

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

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

圖2 不同光照下的匹配結果

圖3 不同視角下的匹配結果

表1 不同光照下的匹配結果對比

圖4 不同尺度下的匹配結果

表2 不同視角下的匹配結果對比

表3 不同尺度下的匹配結果對比

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

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

5 結束語

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

［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］.自動化學報，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］.電子與信息學報，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］.系統仿真學報，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］.中國機械工程，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）.［于麗莉，戴青.一種改進的SIFT 特征匹配算法 ［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］.計算機工程與應用，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］.電子學報，2013，41 （6）：1146－1152.］

［9］Zhang Qi，Rui Ting，Fang 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 特征點匹配的目標跟蹤算法研究［D］.合肥：合肥工業大學，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）.［董文會，常發亮，李天平.融合顏色直方圖及SIFT 特征的自適應分塊目標跟蹤方法 ［J］.電子與信息學報，2013，35 （4）：770－776.］