張盼　阮俊　王雅繼

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

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

中圖分類號： TN911.73?34 文獻(xiàn)標(biāo)識碼： A 文章編號： 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)識別的一個方法[2]。首先對兩幅圖像進行尺度和灰度空間檢測，確定關(guān)鍵點位置和所處尺度，然后用特征點鄰域梯度的主方向作為方向特征生成關(guān)鍵的SIFT特征向量進行匹配，然而這種算法仍然存在誤匹配。2004年Lowe提出了基于SIFT（Scale Invariant and Feature Transform）尺度不變特征變換，其對尺度空間、圖像縮放、仿射變換、噪音等具有不變性。隨后，基于特征點不變性和區(qū)域選擇的圖像配準(zhǔn)及拼接方法被廣泛應(yīng)用并多次改進，降低特征描述符向量的維數(shù)，提高匹配效率已成為近幾年的研究熱點。文獻(xiàn)[3]提出了一種將SIFT算法結(jié)合Canny算子進行96維的特征點匹配，其維數(shù)仍然較高。

1 基于SIFT的特征描述符

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

1.1 生成尺度空間及檢測極值點

1.3 生成特征點描述符

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

1.4 SIFT 64

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

1.5 SIFT 88

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

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

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

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

2 改進的特征描述符

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

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

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

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

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

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

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

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

3.1 圖像信息

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

3.2 實驗環(huán)境

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

3.3 實驗結(jié)果

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

4 結(jié) 語

將改進后的SIFT算法應(yīng)用到圖像拼接中，在圖像的特征提取階段將維數(shù)從128維降低至66維，提高了運行速度，并且保持了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] 劉輝，申海龍.一種基于改進SIFT算法的圖像配準(zhǔn)方法[J].微電子學(xué)與計算機，2014，31（1）：38?42.

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

[5] 馮嘉.SIFT算法的研究和改進[D].長春：吉林大學(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] 吳建，馬躍.一種改進的SIFT算法[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] 陳虎.基于特征點匹配的圖像拼接算法研究[J].海軍工程大學(xué)學(xué)報，2007，19（4）：94?97.