林強

（四川大學計算機學院，成都 610065）

一種改進的SIFT圖像匹配算法

林強

（四川大學計算機學院，成都 610065）

針對尺度不變特征變換（SIFT）算法的匹配結(jié)果存在錯誤匹配點以及冗余匹配點的問題，提出一種改進的圖像匹配算法。該算法將SIFT算子的尺度空間極值點作為初始特征點，用Harris角點檢測算子對初始特征點進行篩選，選擇高對比度的點作為最終特征點。接著設置合適的歐氏距離閾值進行粗匹配。由于SIFT得到的匹配點集存在冗余與錯誤匹配，改進的算法在匹配后再進行一次逆向匹配，最后，利用RANSAC算法進行糾錯，得到正確的匹配特征點對。實驗結(jié)果表明，在圖像有旋轉(zhuǎn)、平移、光照等情況下，該算法穩(wěn)定、可靠。

圖像匹配；SIFT特征；隨機抽樣一致性；歐氏距離

0 引言

圖像匹配是解決很多計算機視覺問題的基礎，包括目標或場景識別，目標跟蹤等。圖像匹配算法一般分為兩種：一種是基于圖像的某些區(qū)域的匹配算法，另一種則是基于圖像的局部特征進行匹配的算法。

圖像匹配技術(shù)發(fā)展到今天，已經(jīng)有比較多的經(jīng)典圖像匹配算法，例如SIFT[1～3]、SURF[4]、PCA-SIFT[5]、Harris[6]、MSER[7]，等等。在眾多經(jīng)典的圖像匹配算法中，SIFT在基于圖像局部特征的匹配算法中具有里程碑的意義，它是由D.G.Lowe于1999年提出，并于2004總結(jié)發(fā)表在期刊論文上。SIFT特征點是被使用最廣泛的興趣特征點之一，它已經(jīng)被成功應用到各種計算機視覺算法，中例如目標檢測、目標跟蹤以及大規(guī)模的圖像檢索中。盡管SIFT描述符對于尺度與旋轉(zhuǎn)具有高度的魯棒性，但是SIFT算法存在較高的時間復雜度，對時間要求很高的實時應用來說它有很多需要改進的地方。對于SIFT算法存在的問題，已經(jīng)有很多改進的算法，例如前面提到的PCA-SIFT，還有RIT-SIFT[8]、文獻[9]以及文獻[10]提出的改進算法等。本文針對SIFT算法的時間復雜度問題，提出了一種改進算法。改進的SIFT算法針對SIFT算法的時間復雜度與精確度分別使用了Harris算法與RANSAC算法。實驗表明，該算法相對于SIFT算法在速度和精確度上有了一定的提升。

1 SIFT算法簡介

文獻[1～2]中已經(jīng)描述過，SIFT算法計算步驟包括四步。

1.1 尺度空間極值

為一幅圖像建立高斯金字塔，在不同的尺度空間中檢測極值點。尺度空間函數(shù)等于可變尺度的高斯函數(shù)G（x，y，σ）與輸入圖像I（x，y）的卷積，公式如下：

其中：

通過建立高斯金字塔來求取特征點的位置，高斯金字塔是通過對輸入圖像進行降采樣形成的圖像組。為了有效獲取穩(wěn)定的特征點位置，采用差分高斯金字塔DoG，即：

1.2 去除不可靠的特征點

在上面建立的高斯差分金字塔中檢測極值，檢測的范圍是差分高斯金字塔中所有的圖像（最上面的圖像與最下面的圖像除外），檢測到的極值是利用金字塔中檢測范圍內(nèi)的圖像的所有像素點與相鄰的26個點做比較，包括上下層圖像各9個點以及自身圖像的8個點。因為尺度空間極值檢測產(chǎn)生太多的候選特征點，其中一些是不穩(wěn)定的。通過擬合三維二次函數(shù)去除低對比度的特征點以及利用Hessian矩陣去除不穩(wěn)定的邊緣點。

1.3 特征點方向分配

每個特征點都被分配一個或多個方向基于梯度直方圖。

上式（4）、（5）分別為（x，y）處梯度的模值和方向計算公式。每個特征點被指定一個主方向和一個輔方向。

1.4 生成特征描述符

局部圖像梯度是在每個特征點區(qū)域已經(jīng)選擇好的尺度下檢測的。一旦一個特征點方向被選好，特征描述符是由特征點周圍的16×16鄰域內(nèi)計算的，將鄰域分成4×4的子塊，然后對每個子像素塊計算8個方向的直方圖。這樣每個特征點的特征向量是4×4×8=128維。圖1是特征向量的生成過程[11]。

圖1 由關(guān)鍵點鄰域梯度信息生成特征向量的過程

2 改進的SIFT匹配算法

2.1 Harris角點檢測算法

Harris角點檢測算法是基于信號特征點提取的，它使窗口w（通常是矩形區(qū)域）無窮小位移向任何方向移動，其中灰度的變化定義如下[12]：

其中X和Y是一個有序的灰度層次的梯度，它們能夠通過圖像的卷積得到如下式：

為了提高抗噪聲的能力，選擇高斯窗口在圖像中平滑，

其中：

E接近偏自相關(guān)函數(shù)，M用來描述自相關(guān)函數(shù)形成的起源。讓M矩陣的特征值通過λ1和λ2來定義。λ1與λ2是自相關(guān)函數(shù)的曲率，它們構(gòu)成自旋變量M。因此，可以通過λ1與λ2的值決定平面區(qū)域、角點以及邊緣，有以下三種情況[13]：

（1）如果兩個曲率都太小，則表明自相關(guān)函數(shù)是平的。

（2）如果一個曲率比較大，另一個曲率很小，則表明E在偏自相關(guān)函數(shù)是類似邊緣的時候有一個小小的改變。

（3）如果兩個曲率都很大，則表明偏自相關(guān)函數(shù)有一個峰值，并且E沿著任何方向有一個很大的改變，這里就是角點。

Harris特征點定義為局部區(qū)域的最大值：

其中Tr2（M）矩陣的跡，Det（M）是矩陣的行列式的值，k取值在0.04～0.06之間得到的結(jié)果比較好。

2.2 RANSANC算法簡介

RANSAC算法是兩個階段的迭代算法，包括假設生成與假設評估。

假設生成：首先，RANSAC算法隨機選取數(shù)據(jù)集，然后從樣本集中估計一個參數(shù)。如果給定的模型是一條直線ax+by+c=0（a2+b2=1），M=［a，b，c］T是被評估的參數(shù)，這是一個正確的假設。RANSAC在迭代過程中生成一系列的假設。

RANSAC不是像最小二乘法以及支持向量機這樣的算法一樣是一種遞歸技術(shù)[14]。RANSAC使用的是樣本數(shù)據(jù)的一部分而不是全部，如果選擇的數(shù)據(jù)都是內(nèi)點，這些數(shù)據(jù)將會使假設進一步接近真實。這個假設需要使用足夠的迭代次數(shù)來以一個失敗概率α選取樣本集中所有的點至少一次，公式：

其中m是用來生成假設的數(shù)據(jù)的數(shù)量，γ是選取內(nèi)點的概率，即整個數(shù)據(jù)內(nèi)點的比例。然而實際上內(nèi)點比例γ是不知道的，由使用者根據(jù)需要決定。

RANSAC將一個在連續(xù)域內(nèi)的估計問題轉(zhuǎn)換成在一個離散域內(nèi)的選擇問題。例如，用200個點求一條直線，使用最小二乘法每次需要兩個點，200個點共有19900可供選擇的點對?，F(xiàn)在的問題是在巨大數(shù)量的點對中選擇合適的點對。

假設評估：RANSAC最終選擇由大部分候選的內(nèi)點支持的最可能的假設。被認為是內(nèi)點候選的規(guī)則是，在一個假設中點的誤差在一個預先定義的閾值范圍內(nèi)。

RANSAC解決選擇候選內(nèi)點問題作為一個優(yōu)化問題，用公式表示如下：

其中D是樣本數(shù)據(jù)，Loss是一個損失函數(shù)，Err是一個誤差函數(shù)，例如幾何距離。最小二乘法的損失函數(shù)表示為Loss（e）=e2。相比之下，RANSAC使用

其中c是閾值。RANSAC在大的誤差條件下有恒定的損失，而最小二乘法有巨大誤差。外點干擾最小二乘法因為它們通常有巨大的誤差。

2.3 改進的SIFT算法

在SIFT算法步驟中，當精確定位特征點位置獲得初步特征點后，用Harris角點檢測算子對初始特征點進行篩選。選擇具有高對比度的點作為最終的特征點。接著利用所求的特征點集，設置合適的SIFT描述符向量之間的歐氏距離最小值與次小值比值的閾值，對特征點集進行粗匹配。由于SIFT匹配得到的匹配點集存在大量的冗余與錯誤匹配，改進的算法在SIFT算法匹配之上對兩幅圖像進行一次逆向匹配，即若測試圖像中存在一個點對應原始圖像的多個點，求出原始圖像中的每個點到測試圖像中的這點的距離，選擇距離最小的兩個點作為匹配點，去除其余原始圖像的特征點。最后，利用隨機抽樣一致性（RANSAC）算法進行處理，選擇正確的匹配特征點對。因為在提取特征點的時候減少了特征點的數(shù)量，而且在SIFT匹配完后進一步對匹配后的特征點對做了一次RANSAC算法處理，因此改進的算法不僅在速度上快于SIFT算法，而且在精度上高于SIFT算法。

3 實驗結(jié)果

為了檢測本文提出的改進的SIFT算法在速度和精度上都高于原始的SIFT算法。實驗采用了三組圖像，分別用于測試改進的算法中旋轉(zhuǎn)、縮放，以及光照變化的不變性。實驗使用不同的場景不同的圖像進行測試，以避免隨機性帶來的誤差。

圖1 用于進行實驗的組圖

圖2 SIFT與改進SIFT在圖像旋轉(zhuǎn)后的匹配結(jié)果

圖3 SIFT與改進SIFT在圖像縮放后的匹配結(jié)果

圖4 SIFT與改進SIFT在光照變化后的匹配的結(jié)果

表1 SIFT與改進的SIFT的實驗結(jié)果對比

表2 SIFT與改進SIFT運行的時間對比

實驗結(jié)果表明，改進的SIFT匹配算法不僅保持了原始的SIFT具有的特征，而且改進的SIFT匹配算法確實在速度與精度上超越了原始的SIFT算法，雖然在檢測特征點的時候是以減少特征點數(shù)量為代價來提高運算速度，但是在總體上并不影響圖像的匹配精度。

4 結(jié)語

本文分析了SIFT匹配算法的原理及其存在的缺點，提出了一種改進的SIFT匹配算法。該算法旨在提高SIFT算法匹配的速度與精度。通過利用Harris角點檢測算法在求取SIFT極值點時進行進一步篩選，減少了SIFT特征點的匹配點對數(shù)，同時也相應地提高了精度。在得到匹配點后，對原始圖像與測試圖像進行一次逆向匹配，接著利用RANSAC對得到的匹配點進行進一步處理，刪除外點，選擇正確的匹配點對，使匹配精度提高。實驗結(jié)果表明改進的算法相對于SIFT算法在匹配精度和匹配速度上有一定提高。

[1] D.Lowe.Object Recognition from Loca1 Sca1e Invariant Features[C].Proceedings of the ICCV.Kerkyra，Greece，1999：1150～1157

[2] D.Lowe.Distinctive Image Features from Sca1e Invariant Keypoints[J].Internationa1 Journa1 of Computer Vision，2004，60（2）：91～110

[3] Aniruddha Acharya K，R.Venkatesh Babu:Speeding up SIFT Using GPU[C].2013 4th Nationa1 Conference on Computer Vision.Pattern Recognition.Image Processing and Graphics，NCVPRIPG 2013

[4] Bay Herbert，Tuyte1aars Tinne，Goo1LucVan.SURF:Speeded Up Robust Features[J].Computer Vision and Image Understanding，2008，110（3）：346～359

[5] Y.Ke，R.Sukthankar.PCA-SIFT:“A More Distinctive Representation for Loca1 Image Descriptors”[C].Proc.Conf.Computer Vision and Pattern Recognition，2004：511～517

[6] HARRIS C，STEPHENS M.A Combined Corner and Edge Detection[J].Image Vision Computing，1998，15（6）:121～127

[7] J.Matas，O.Chum，M.Urban，T Pajd1a.Robust Wide-Base1ine Stereo from Maxima11y Stab1e Exterma1 Regions[C].Proceedings of the British Machine Vision Conference，Cardiff，UK，2002：384～393

[8] 唐朝偉，肖健，邵艷清，苗光勝.一種改進的SIFT描述子及其性能分析[J].武漢大學學報信息科學版，2012（1）:11～16

[9] 于麗莉，戴青.一種改進的SIFT匹配算法[J].計算機工程，2011（1）:210`212

[10] 趙壘，侯振杰.一種改進的SIFT圖像配準方法.計算機工程，2010（6）:226～228

[11] 江道寅.基于SIFT圖像配準算法的研究[D].中國科技大學，2011:45～47

[12] 王靜.基于SIFT和角點檢測的自動圖像配準方法研究[D].華中科技大學，2010：19～24

[13] 章毓晉.圖像處理（第2版）.北京:清華大學出版社，2006:270～278

[14] 常青，張斌，邵金玲.基于SIFT和RANSAC的特征圖像匹配方法[J].華東理工大學學報自然科學版，2012（12）:747～751

An Improved SIFT Image Matching Algorithm

LIN Qiang
（Department of Computer Science，Sichuan University，Chengdu 610065）

Puts forwards an improved image matching a1gorithm aiming at the prob1ems of that Sca1e Invariant Feature Transform a1gorithm has a few fa1se and repeated matching feature points.The improved image matching method takes the extremum got by the SIFT descriptor as origina1 keypoints,then fi1ters the origina1 keypoints by Harris corner detection operator.Se1ects points which have a high contrast as fina1 points and match fina1 points by using the proportion of the Euc1idean distance.As there are some redundant and error matching points, converse1y matches both images based on SIFT matching.Fina11y uses RANSAC a1gorithm to se1ect the correct match keypoints.The resu1ts show that the a1gorithm is stab1e and re1iab1e under the change of rotation,trans1ation,1ight,contrast and so on.

Image Matching;SIFT Feature;RANSAC;Euc1idean Distance

1007-1423（2015）05-0058-05

10.3969/j.issn.1007-1423.2015.05.013

林強（1983-），男，四川成都人，碩士，研究方向為計算機視覺

2014-12-31

2015-01-21