改進的sift特征匹配方法

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

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

關鍵詞：sift；特征點檢測；特征點描述；特征匹配

中圖分類號：TP3 文獻標識碼：A 文章編號：1009-3044（2015）25-0130-03

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

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

1 Sift算法簡介

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

1.1 生成尺度空間

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

1.2 計算尺度空間的極值點

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

1.3精確定位極值點

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

2.1 原算法特征點的描述

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

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

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

a）鄰域梯度方向圖 b）特征點向量圖

圖2 以特征點為中心取8x8的窗口

2.2 改進的sift特征描述

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

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

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

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

3）在16x16像素范圍內，計算除去圓內像素以外的所有像素梯度方向的累加值，形成一個8方向的種子點。在20x20像素范圍內的計算除去16x16以外的所有像素點梯度方向的累加值，形成一個8方向的種子點。

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

2.3 算法改進的可行性

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

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

3 實驗結果與分析

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

3.1 實驗一

實驗一首先采用兩幅lena頭像進行匹配，圖像大小尺寸分別為256x256與512x512，實驗結果如下圖所示，分析如下表所示。

4 結束語

Sift算法的時效性難以與其他算法比較，但因其精度上的準確性，sift算法仍然被廣泛應用。基于OpenCV的Visual Studio平臺實驗了原sift算法，并且在特征子描述方面對算法進行改進，將原算法特征描述符的維度由128為降為40維，像素搜索范圍也擴大至20x20，在保證算法精確性不降低的同時提升了時效性，實驗驗證了該算法的可行性。

參考文獻：

[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]. 北京測繪， 2014（4）： 23-26.

[7] 高健， 黃心漢， 彭剛， 等. 一種簡化的 SIFT 圖像特征點提取算法[J]. 計算機應用研究， 2008， 25（7）： 2213-2215.

[8] 楊幸芳， 黃玉美， 李艷，等. 一種基于USAN的特征點檢測算法[J]. 機械科學與技術， 2011（30）：1120-1123.

[9] 王立中， 麻碩士， 薛河儒，等. 基于圖像分塊的多尺度Harris特征點檢測算法[J]. 內蒙古大學學報：自然科學版， 2009， 40：326-329.