楊維++朱文球++羅哲++李旺

摘要：sift特征匹配算法是圖像匹配算法中最為經(jīng)典的算法，對(duì)圖像的平移、旋轉(zhuǎn)、仿射變換具有很好的魯棒性。但其128維的特征描述向量使得處理匹配特征點(diǎn)計(jì)算龐大，導(dǎo)致時(shí)效性不高。提出了一種改進(jìn)的Sift特征配準(zhǔn)方法，將128維的特征描述向量降至40維，并且像素的描述范圍也由原來(lái)的16x16擴(kuò)大至20x20，減少了匹配的運(yùn)算次數(shù)，縮短了圖像配準(zhǔn)時(shí)間。通過(guò)實(shí)驗(yàn)證明了算法的有效性，與原sift算法比較，該算法匹配時(shí)間更短，精度更高。

關(guān)鍵詞：sift；特征點(diǎn)檢測(cè)；特征點(diǎn)描述；特征匹配

中圖分類號(hào)：TP3 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）25-0130-03

圖像匹配是指通過(guò)一定的匹配算法在兩幅或多幅圖像之間識(shí)別同名點(diǎn)的過(guò)程，主要可分為基于灰度的匹配和基于特征的匹配。特征點(diǎn)是圖像的本質(zhì)特性，與灰度特征相比，對(duì)灰度變化、圖像形變以及區(qū)域遮擋等有較好的魯棒性，因此被廣泛用于圖像匹配、全景拼接、目標(biāo)識(shí)別等領(lǐng)域。

Sift[1]算法采用一種基于尺度空間的、對(duì)圖像縮放、旋轉(zhuǎn)甚至仿射保持不變性的圖像局部特征描述算子提取特征點(diǎn)，在圖像處理領(lǐng)域應(yīng)用普遍。隨著計(jì)算機(jī)視覺(jué)的發(fā)展，基于圖像特征點(diǎn)的配準(zhǔn)方法是目前圖像匹配技術(shù)的主流方向和發(fā)展趨勢(shì)。因此，國(guó)內(nèi)外針對(duì)特征點(diǎn)的提取提出了很多算法。2006年Herbert Bay等人提出了SURF[2]算法，2011年Stefan Leutenegger等人提出的BRSIK[3]算法，Ethan Rublee等人提出的ORB[4]算法以及Alexandre Alahi等人提出的FREAK[5]算法，以上所述四種算法，在時(shí)間復(fù)雜度上均優(yōu)于sift算法[6]，但sift算法之所以仍被廣泛應(yīng)用，是由于其算法的精確性在普遍情況下要優(yōu)于其他算法。國(guó)內(nèi)一些研究者也提出了許多特征點(diǎn)檢測(cè)算法，楊幸芳提出了一種基于USAN的特征檢測(cè)算法[8]，王立中等人發(fā)明了一種基于圖像分塊的多尺度Harris特征檢測(cè)算法[9]，這些新的方法在耗時(shí)上要低于原sift算法，但精確度上不如原算法?；诖祟愒?，文章旨在提出一種保證精確性的情況下減小時(shí)間復(fù)雜度的算法，因此提出了一種改進(jìn)的sift匹配算法。

1 Sift算法簡(jiǎn)介

Sift（Scale-invariant feature transform）算法是David G.Lowe在1999年提出并于2004完善的一種基于尺度不變局部特征算法，在圖像特征點(diǎn)匹配方面具有良好的效果，整個(gè)匹配算法大概分為以下幾個(gè)部分：

1.1 生成尺度空間

尺度空間的生成是模擬圖像數(shù)據(jù)的多尺度特征，Lindeberg已經(jīng)證明高斯卷積核是實(shí)現(xiàn)尺度變換的唯一線性核。因此，一幅二維圖像的尺度空間定義為（1）

1.2 計(jì)算尺度空間的極值點(diǎn)

建立尺度空間后，需要在此基礎(chǔ)上尋找尺度空間的極值點(diǎn)，每一個(gè)采樣點(diǎn)要和它所有的相鄰點(diǎn)比較。如圖2所示，檢測(cè)點(diǎn)和它同尺度的8個(gè)相鄰點(diǎn)以及上下相鄰尺度對(duì)應(yīng)的9×2個(gè)點(diǎn)共26個(gè)點(diǎn)比較，若該點(diǎn)的值比其他26個(gè)相鄰點(diǎn)都大或者都小，那么該點(diǎn)被認(rèn)為是圖像在該尺度下的一個(gè)特征點(diǎn)。

1.3精確定位極值點(diǎn)

由于DoG值對(duì)噪聲和邊緣較敏感，在DoG尺度空間中檢測(cè)到局部極值點(diǎn)還要經(jīng)過(guò)進(jìn)一步的檢驗(yàn)才能精確定位為特征點(diǎn)。為了提高關(guān)鍵點(diǎn)的穩(wěn)定性，需要對(duì)尺度空間DoG函數(shù)進(jìn)行曲線擬合，利用DoG函數(shù)在尺度空間的泰勒展開(kāi)式（擬合函數(shù)）為：，其中，

2.1 原算法特征點(diǎn)的描述

為了使描述符具有旋轉(zhuǎn)不變性，需要利用圖像的局部特征為給每一個(gè)關(guān)鍵點(diǎn)分配一個(gè)主方向。 利用關(guān)鍵點(diǎn)鄰域像素的梯度方向分布特性為每個(gè)關(guān)鍵點(diǎn)指定方向參數(shù)，使算子具備旋轉(zhuǎn)不變性。

處梯度的模值和方向。完成關(guān)鍵點(diǎn)的梯度計(jì)算后，使用直方圖統(tǒng)計(jì)鄰域內(nèi)像素的梯度和方向，直方圖的范圍是0～360度，其中每10度一柱，共36 柱，隨后對(duì)于直方圖采取高斯平滑，以區(qū)分各像素點(diǎn)的影響值，離中心點(diǎn)越近，權(quán)值越大。直方圖中最大值作為該關(guān)鍵點(diǎn)的主方向，為了增強(qiáng)魯棒性，將大于主方向峰值80%的方向作為輔方向。

獲得關(guān)鍵點(diǎn)主方向后，每個(gè)關(guān)鍵點(diǎn)有位置、尺度和方向三個(gè)信息[7]，取以特征點(diǎn)為中心的16x16像素大小的鄰域，將此鄰域均勻地分為4x4個(gè)子區(qū)域，對(duì)每個(gè)子區(qū)域計(jì)算梯度方向直方圖。然后，對(duì)4x4個(gè)子區(qū)域的8方向梯度直方圖根據(jù)位置依次排序，這樣就構(gòu)成了一個(gè)4x4x8=128維的特征向量，該向量就作為sift特征的描述子。

a）鄰域梯度方向圖 b）特征點(diǎn)向量圖

圖2 以特征點(diǎn)為中心取8x8的窗口

2.2 改進(jìn)的sift特征描述

原sift算法描述子的維數(shù)為4x4x8=128維，像素范圍為16x16。由于維數(shù)過(guò)高，計(jì)算量也是龐大的，因此，提出一種改進(jìn)的特征描述子，將維數(shù)降低為40維。

在原算法像素搜索范圍內(nèi)降維可能會(huì)影響到配準(zhǔn)的精度，文章降低描述子維數(shù)的同時(shí)保證精度，改進(jìn)的算法以圓形區(qū)域代替原來(lái)的16x16特征區(qū)域，另外將區(qū)域擴(kuò)大為20x20。

1）為了保持旋轉(zhuǎn)不變性，首先將坐標(biāo)軸調(diào)整到與特征方向一致的角度，新的描述子如圖3所示，中心點(diǎn)代表特征點(diǎn)，用黑點(diǎn)表示，取以特征點(diǎn)為中心的16x16鄰域像素，形成直徑為16像素的圓形區(qū)域；

2）以為半徑單位將圓劃分為3個(gè)同心圓，分別計(jì)算圓內(nèi)的梯度值形成8維的特征向量，3個(gè)圓環(huán)總共生成3x8=24維的特征向量，其中針對(duì)圓弧經(jīng)過(guò)的像素塊，分別計(jì)算其梯度值，然后以其梯度值的一半分別計(jì)入相鄰的圓內(nèi)與圓外兩個(gè)圓環(huán)（圖3右所示）。

3）在16x16像素范圍內(nèi)，計(jì)算除去圓內(nèi)像素以外的所有像素梯度方向的累加值，形成一個(gè)8方向的種子點(diǎn)。在20x20像素范圍內(nèi)的計(jì)算除去16x16以外的所有像素點(diǎn)梯度方向的累加值，形成一個(gè)8方向的種子點(diǎn)。

4）統(tǒng)計(jì)所有種子點(diǎn)從而形成24+8+8=40維的特征向量，并且描述范圍擴(kuò)大到了20x20像素。

2.3 算法改進(jìn)的可行性

待檢測(cè)到兩幅圖像的所有特征點(diǎn)集合后，通常通過(guò)對(duì)比兩集合的各個(gè)特征點(diǎn)來(lái)尋找匹配點(diǎn)對(duì)，其中基于紋理特征的相似性度量方法有歐氏距離和馬氏距離，而歐式距離是采用最為廣泛的方法，文章采用歐氏距離作為相似性度量方法。在原sift算法中，兩圖像的任意特征點(diǎn)分別表示為和，任意兩特征點(diǎn)的相似性度量表示為

對(duì)于改進(jìn)的算法，特征點(diǎn)描述子的維數(shù)從128維降到40維，則比對(duì)任意兩個(gè)特征點(diǎn)所需運(yùn)算次數(shù)為：減法40次，平方40次，加法39次，開(kāi)方1次，相比較原sift算法來(lái)說(shuō)，運(yùn)算量大大減少，對(duì)于檢測(cè)到的特征點(diǎn)越多的圖像，該算法更能體現(xiàn)出優(yōu)越性。

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

實(shí)驗(yàn)采用基于OpenCV的Visual Studio軟件為實(shí)驗(yàn)平臺(tái)，電腦系統(tǒng)為Windows7，CPU i5，主頻為3.10GHz，內(nèi)存4GB。實(shí)驗(yàn)首先選取實(shí)驗(yàn)數(shù)據(jù)集中的多組不同分辨率圖像進(jìn)行，之后通過(guò)自己錄制的視頻圖像進(jìn)行實(shí)驗(yàn)。

3.1 實(shí)驗(yàn)一

實(shí)驗(yàn)一首先采用兩幅lena頭像進(jìn)行匹配，圖像大小尺寸分別為256x256與512x512，實(shí)驗(yàn)結(jié)果如下圖所示，分析如下表所示。

4 結(jié)束語(yǔ)

Sift算法的時(shí)效性難以與其他算法比較，但因其精度上的準(zhǔn)確性，sift算法仍然被廣泛應(yīng)用?；贠penCV的Visual Studio平臺(tái)實(shí)驗(yàn)了原sift算法，并且在特征子描述方面對(duì)算法進(jìn)行改進(jìn)，將原算法特征描述符的維度由128為降為40維，像素搜索范圍也擴(kuò)大至20x20，在保證算法精確性不降低的同時(shí)提升了時(shí)效性，實(shí)驗(yàn)驗(yàn)證了該算法的可行性。

參考文獻(xiàn)：

[1] Lowe D G. Distinctive image features from scale-invariant keypoints[J]. International journal of computer vision， 2004， 60（2）： 91-110.

[2] Bay H， Tuytelaars T， Van Gool L. Surf： Speeded up robust features[M].Computer vision–ECCV 2006. Springer Berlin Heidelberg， 2006： 404-417.

[3] Leutenegger S， Chli M， Siegwart R Y. BRISK： Binary robust invariant scalable keypoints[C].Computer Vision （ICCV）， 2011 IEEE International Conference on. IEEE， 2011： 2548-2555.

[4] Rublee E， Rabaud V， Konolige K， et al. ORB： an efficient alternative to SIFT or SURF[C]. Computer Vision （ICCV）， 2011 IEEE International Conference on. IEEE， 2011： 2564-2571.

[5] Alahi A， Ortiz R， Vandergheynst P. Freak： Fast retina keypoint[C].Computer Vision and Pattern Recognition （CVPR）， 2012 IEEE Conference on. Ieee， 2012： 510-517.

[6] 索春寶， 楊東清， 劉云鵬. 多種角度比較 SIFT， SURF， BRISK， ORB， FREAK 算法[J]. 北京測(cè)繪， 2014（4）： 23-26.

[7] 高健， 黃心漢， 彭剛， 等. 一種簡(jiǎn)化的 SIFT 圖像特征點(diǎn)提取算法[J]. 計(jì)算機(jī)應(yīng)用研究， 2008， 25（7）： 2213-2215.

[8] 楊幸芳， 黃玉美， 李艷，等. 一種基于USAN的特征點(diǎn)檢測(cè)算法[J]. 機(jī)械科學(xué)與技術(shù)， 2011（30）：1120-1123.

[9] 王立中， 麻碩士， 薛河儒，等. 基于圖像分塊的多尺度Harris特征點(diǎn)檢測(cè)算法[J]. 內(nèi)蒙古大學(xué)學(xué)報(bào)：自然科學(xué)版， 2009， 40：326-329.