張盼　阮俊　王雅繼

摘 要： 針對(duì)傳統(tǒng)SIFT匹配算法數(shù)據(jù)量大、時(shí)間復(fù)雜度高的問題，提出基于尺度不變特征變換（SIFT）特征提取方法獲得特征點(diǎn)，并采用變換步長(zhǎng)的圓形區(qū)域選區(qū)對(duì)特征點(diǎn)進(jìn)行描述，改進(jìn)了SIFT特征的64維描述符和88維描述符的不足。將改進(jìn)后的算法應(yīng)用到圖像拼接過程中，通過實(shí)驗(yàn)驗(yàn)證了改進(jìn)后的方法在時(shí)間復(fù)雜度方面有所改善。

關(guān)鍵詞： 特征點(diǎn)； SIFT描述符； 圖像配準(zhǔn)； 圖像拼接

中圖分類號(hào)： TN911.73?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2015）19?0072?04

Abstract： Since the traditional scale invariant and feature transform （SIFT） algorithm has large data size and high time complexity， a feature extraction method based on SIFT is proposed to acquire the feature points. The region in circular area with step?conversion is adopted to describe the feature points， and the insufficient of 64?dimensional descriptor and 88?dimensional descriptor of SIFT feature is improved. The improved algorithm was applied to image mosaic process. The experiment results verify that this method has great improvement in the aspect of time complexity.

Keywords： feature point； SIFT descriptor； image registration； image mosaic

特征的提取在圖像配準(zhǔn)及拼接過程中起著關(guān)鍵性作用，SIFT算法[1]是David G. Lowe在1999年首先提出的用于目標(biāo)識(shí)別的一個(gè)方法[2]。首先對(duì)兩幅圖像進(jìn)行尺度和灰度空間檢測(cè)，確定關(guān)鍵點(diǎn)位置和所處尺度，然后用特征點(diǎn)鄰域梯度的主方向作為方向特征生成關(guān)鍵的SIFT特征向量進(jìn)行匹配，然而這種算法仍然存在誤匹配。2004年Lowe提出了基于SIFT（Scale Invariant and Feature Transform）尺度不變特征變換，其對(duì)尺度空間、圖像縮放、仿射變換、噪音等具有不變性。隨后，基于特征點(diǎn)不變性和區(qū)域選擇的圖像配準(zhǔn)及拼接方法被廣泛應(yīng)用并多次改進(jìn)，降低特征描述符向量的維數(shù)，提高匹配效率已成為近幾年的研究熱點(diǎn)。文獻(xiàn)[3]提出了一種將SIFT算法結(jié)合Canny算子進(jìn)行96維的特征點(diǎn)匹配，其維數(shù)仍然較高。

1 基于SIFT的特征描述符

SIFT算法要在尺度空間和二維平面空間中同時(shí)進(jìn)行極值檢測(cè)以找出局部極值點(diǎn)，并對(duì)提取出的特征點(diǎn)進(jìn)行精確定位，然后根據(jù)此特征點(diǎn)所處位置周圍鄰域點(diǎn)的梯度方向計(jì)算出該特征點(diǎn)的主方向，以實(shí)現(xiàn)算子對(duì)幾何變換和旋轉(zhuǎn)的不變性。一般生成SIFT特征描述符需要以下幾個(gè)步驟：生成尺度空間及檢測(cè)極值點(diǎn)；進(jìn)行特征點(diǎn)定位和確定特征點(diǎn)的方向；生成特征點(diǎn)描述符。

1.1 生成尺度空間及檢測(cè)極值點(diǎn)

1.3 生成特征點(diǎn)描述符

如圖1所示，其中每一個(gè)小方格代表一個(gè)像素點(diǎn)，對(duì)于每一個(gè)特征點(diǎn)均以該特征點(diǎn)為中心，在該特征點(diǎn)周圍選取[16×16]的區(qū)域，然后將此區(qū)域平均分成[4×4]個(gè)子區(qū)域，對(duì)每個(gè)子區(qū)域計(jì)算16個(gè)像素點(diǎn)的主方向，這樣總共計(jì)算的像素點(diǎn)為[S=16×16個(gè)，]同時(shí)獲得[4×4×8=128]維的向量，記為SIFT 128。

1.4 SIFT 64

Tang C M等人采用環(huán)形區(qū)域取代SIFT的矩形區(qū)域[7]，以減少計(jì)算SIFT中主方向產(chǎn)生的時(shí)間消耗量，從而降低時(shí)間復(fù)雜度，其采用固定一個(gè)像素的步長(zhǎng)來對(duì)特征點(diǎn)進(jìn)行描述，如圖2所示。取8個(gè)子環(huán)，每個(gè)子環(huán)像素共有8個(gè)特征向量，故該[8×8=64]維向量就定義為該特征點(diǎn)的特征描述符，本文中記為SIFT 64。其最外層環(huán)所在區(qū)域?yàn)閇16×16]像素的方形區(qū)域中，所計(jì)算的總像素量[S8<][S<16×16]（[S8]指半徑為8個(gè)像素的圓形區(qū)域的像素總數(shù)）。

1.5 SIFT 88

吳建等人在Tang的基礎(chǔ)上對(duì)SIFT 64進(jìn)行了改進(jìn)，提出變步長(zhǎng)的方法計(jì)算特征描述符[8]，如圖3所示，其仍采用8環(huán)即（4，4，3，3，2，2，1，1）的環(huán)數(shù)對(duì)特征點(diǎn)進(jìn)行描述，但其在每環(huán)的8個(gè)特征向量的基礎(chǔ)上增加了正負(fù)灰度差累積值和灰度累加值，總維數(shù)為[8+2+1×8=88，]本文記為SIFT 88。其最外層環(huán)所在區(qū)域?yàn)閇40×40]像素的方形區(qū)域中，所計(jì)算的像素量[S20

綜上所述，兩種算法中SIFT 64將傳統(tǒng)SIFT 128從128維降低至64維，時(shí)間復(fù)雜度有所降低；SIFT 88雖將SIFT 64進(jìn)行改進(jìn)，但仍存在如下不足：

（1） SIFT 88算法中采用變步長(zhǎng)進(jìn)行采樣，解決了離散像素的采樣偏移，但對(duì)像素點(diǎn)的計(jì)算量過大，其S值遠(yuǎn)遠(yuǎn)大于SIFT 64的S值，導(dǎo)致時(shí)間復(fù)雜度高的問題。本文將采用另一種算法解決該問題，大大減小了S的計(jì)算量，降低了時(shí)間復(fù)雜度。

（2） SIFT 88算法采用最小值移位方法解決誤匹配，但在實(shí)際中不僅存在誤匹配，也存在著重復(fù)匹配的問題，其采用的算法無法去除重復(fù)匹配。本文綜合窮舉搜索方法并利用圓形區(qū)域的旋轉(zhuǎn)不變特征同時(shí)去除重復(fù)匹配和誤匹配的問題，確保了精準(zhǔn)度。

2 改進(jìn)的特征描述符

針對(duì)傳統(tǒng)的SIFT算法、SIFT 64以及SIFT 88存在的問題，本文提出更好的改進(jìn)方法：

（1） 如圖4所示。本文采用變換環(huán)數(shù)代替SIFT 64的固定環(huán)數(shù)，即子環(huán)步長(zhǎng)不是固定值，而是逐漸減小步長(zhǎng)，越靠近中心區(qū)域，步長(zhǎng)越大。增大亞像素的權(quán)重，盡量減少誤匹配。但由于環(huán)數(shù)增多則會(huì)加大時(shí)間開銷量，因此，本文在采用變換步長(zhǎng)的基礎(chǔ)上也對(duì)總環(huán)數(shù)進(jìn)行了控制，以減小時(shí)間復(fù)雜度，即從靠近中心像素算起依次為（3，3，2，2，1，1）的環(huán)數(shù)，這樣總環(huán)數(shù)為3+3+2+2+1+1=12環(huán)，像素計(jì)算量為半徑為12的圓形區(qū)域，設(shè)總像素量為[S，]則[S12

（2） 新增一個(gè)權(quán)重系數(shù)（[weight1，][weight2，][weight3，] [weight4，][weight5，][weight6]），分別控制（3，3，2，2，1，1）各層對(duì)中心像素點(diǎn)的影響度。使得越靠近中心點(diǎn)，其影響度越大，越遠(yuǎn)離中心點(diǎn)，影響度越小。

（3） 采用變尺度滑動(dòng)窗口的方法累加灰度差。即將整個(gè)環(huán)作為一個(gè)大的區(qū)域[R，]每環(huán)產(chǎn)生一個(gè)正的灰度累積值及一個(gè)負(fù)的灰度累積值（[HRi+，HRi-]），在累積值計(jì)算時(shí)采用大小為兩個(gè)環(huán)的滑動(dòng)窗口進(jìn)行累加，即第2環(huán)的灰度累加值為第1環(huán)和第2環(huán)的灰度累加值之和；第3環(huán)的灰度累加值為第2環(huán)和第3環(huán)的灰度累加值之和，以此類推。計(jì)算出每環(huán)的灰度累計(jì)值，故每環(huán)描述符為二維向量。

（5） 本文采用窮舉搜索方法除去誤匹配和一些重復(fù)的匹配點(diǎn)：在基于歐式距離的初步匹配基礎(chǔ)上進(jìn)行雙向匹配，并使用隨機(jī)抽樣一致性算法RANSAC進(jìn)一步除去誤匹配和一些重復(fù)的匹配點(diǎn)，其主要思想是兩個(gè)特征集[Keypoint1i]和[Keypoint2i，]其中[Keypoint1i]中已經(jīng)匹配出來的特征集為[Keypoint1m]，[Keypoint2i]已匹配的特征集[Keypoint2n]的交集，只需保留交集[Unioni=Keypoint1m?Keypoint2n]即可，再采用最小值移位法去除誤匹配點(diǎn)。這樣便可消除重復(fù)匹配點(diǎn)和誤匹配點(diǎn)。

（6） 為避免光照產(chǎn)生的影響，本文對(duì)特征向量做歸一化處理。本文改進(jìn)后的特征描述符共由3部分組成：第一部分為特征描述符的8個(gè)方向（0，45，90，135，180，225，270，315）上的加權(quán)梯度大小及方向累計(jì)值；第二部分為正負(fù)灰度差累計(jì)直方圖（[HRi+，][HRi-]）；第三部分為特征點(diǎn)周圍各環(huán)的灰度累加值gray。

綜上所述，局部描述子每一環(huán)的維數(shù)為8+2+1=11，總維數(shù)為[11×6=66]，在本文記為SIFT 66。最后對(duì)圖像進(jìn)行自動(dòng)拼接[9?10]。

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

3.1 圖像信息

本文采用圖像為保定地質(zhì)調(diào)查中心調(diào)度樓拍攝照片，圖像大小為512×384像素并使用不同算法對(duì)兩組圖像的整體拼接時(shí)間做實(shí)驗(yàn)分析。在圖像特征提取階段，本文也對(duì)公認(rèn)測(cè)試圖像進(jìn)行了驗(yàn)證。

3.2 實(shí)驗(yàn)環(huán)境

本文采用的實(shí)驗(yàn)環(huán)境為：CPU為Intel?CoreTMi5?2430M 2.40 GHz，內(nèi)存為4.0 GB，顯存為1.0 GB，操作系統(tǒng)為Windows 7旗艦版，仿真平臺(tái)為Matlab R2012b。

3.3 實(shí)驗(yàn)結(jié)果

由表1～表4可以看出，本文改進(jìn)后算法在保持了原算法的配準(zhǔn)精度的基礎(chǔ)上提高了配準(zhǔn)的時(shí)間效率，也可以從數(shù)據(jù)分析得知，增加采樣像素可以提高精度，但對(duì)于不同的特征點(diǎn)的鄰域也會(huì)有相似鄰域像素的干擾，使得過多的變換環(huán)數(shù)（即過多的采樣像素）不僅增加了時(shí)間開銷，并且配準(zhǔn)精度未能得到提高。同時(shí)，由于SURF算法本身受光照和旋轉(zhuǎn)的影響較大，魯棒性不強(qiáng)，在特征點(diǎn)描述過程中也沒有使用本文的加權(quán)方法，在特征點(diǎn)提取階段出現(xiàn)的誤匹配較多。在原圖像配準(zhǔn)過程中雖然時(shí)間消耗優(yōu)于本文算法，但配準(zhǔn)精度只達(dá)到了50%左右，后續(xù)對(duì)圖像的拼接不能達(dá)到本文的拼接效果，并且原圖像旋轉(zhuǎn)和增加噪聲之后其配準(zhǔn)時(shí)間沒有文中改進(jìn)后的算法配準(zhǔn)時(shí)間短。

4 結(jié) 語

將改進(jìn)后的SIFT算法應(yīng)用到圖像拼接中，在圖像的特征提取階段將維數(shù)從128維降低至66維，提高了運(yùn)行速度，并且保持了SIFT 88的穩(wěn)定性和精確性。本文在拼接過程中未作更詳細(xì)的處理，仍存在細(xì)微的拼接縫隙，將作為后續(xù)深入研究的方向。

參考文獻(xiàn)

[1] LOWE D G. Object recognition from local scale?invariant features [C]// Proceedings of 1999 IEEE International Conference on Computer vision. Corfu： IEEE， 1999： 1150?1157.

[2] LOWE D G. Distinctive image features from scale?invariant key points [J]. International Journal of Computer vision， 2004， 60（2）： 91?110.

[3] 劉輝，申海龍.一種基于改進(jìn)SIFT算法的圖像配準(zhǔn)方法[J].微電子學(xué)與計(jì)算機(jī)，2014，31（1）：38?42.

[4] 周峰.基于尺度不變特征變換（SIFT）的圖像配準(zhǔn)技術(shù)研究[D].昆明：昆明理工大學(xué)，2010.

[5] 馮嘉.SIFT算法的研究和改進(jìn)[D].長(zhǎng)春：吉林大學(xué)，2010.

[6] 章毓晉.圖像工程：圖像處理和分析[M].北京：清華大學(xué)出版社，1999.

[7] TANG Chunming. Automatic registration based on improved sift for medical microscopic sequence images [C]// 2008 Second IEEE International Symposium on Intelligent Information Technology Application. [S.l.]： IEEE， 2008， 1： 580?583.

[8] 吳建，馬躍.一種改進(jìn)的SIFT算法[J].計(jì)算機(jī)科學(xué)，2013，40（7）：270?272.

[9] CHALECHALE A，NAGHDY G， MERTINS A. Sketch?based image matching using angular partitioning systems [J]. IEEE Transactions on Man and Cybernetics， Part A， 2005， 35（1）： 28?41.

[10] 陳虎.基于特征點(diǎn)匹配的圖像拼接算法研究[J].海軍工程大學(xué)學(xué)報(bào)，2007，19（4）：94?97.