林強(qiáng)

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

一種改進(jìn)的SIFT圖像匹配算法

林強(qiáng)

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

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

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

0 引言

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

圖像匹配技術(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特征點(diǎn)是被使用最廣泛的興趣特征點(diǎn)之一，它已經(jīng)被成功應(yīng)用到各種計(jì)算機(jī)視覺算法，中例如目標(biāo)檢測(cè)、目標(biāo)跟蹤以及大規(guī)模的圖像檢索中。盡管SIFT描述符對(duì)于尺度與旋轉(zhuǎn)具有高度的魯棒性，但是SIFT算法存在較高的時(shí)間復(fù)雜度，對(duì)時(shí)間要求很高的實(shí)時(shí)應(yīng)用來說它有很多需要改進(jìn)的地方。對(duì)于SIFT算法存在的問題，已經(jīng)有很多改進(jìn)的算法，例如前面提到的PCA-SIFT，還有RIT-SIFT[8]、文獻(xiàn)[9]以及文獻(xiàn)[10]提出的改進(jìn)算法等。本文針對(duì)SIFT算法的時(shí)間復(fù)雜度問題，提出了一種改進(jìn)算法。改進(jìn)的SIFT算法針對(duì)SIFT算法的時(shí)間復(fù)雜度與精確度分別使用了Harris算法與RANSAC算法。實(shí)驗(yàn)表明，該算法相對(duì)于SIFT算法在速度和精確度上有了一定的提升。

1 SIFT算法簡(jiǎn)介

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

1.1 尺度空間極值

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

其中：

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

1.2 去除不可靠的特征點(diǎn)

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

1.3 特征點(diǎn)方向分配

每個(gè)特征點(diǎn)都被分配一個(gè)或多個(gè)方向基于梯度直方圖。

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

1.4 生成特征描述符

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

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

2 改進(jìn)的SIFT匹配算法

2.1 Harris角點(diǎn)檢測(cè)算法

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

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

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

其中：

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

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

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

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

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

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

2.2 RANSANC算法簡(jiǎn)介

RANSAC算法是兩個(gè)階段的迭代算法，包括假設(shè)生成與假設(shè)評(píng)估。

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

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

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

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

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

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

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

其中c是閾值。RANSAC在大的誤差條件下有恒定的損失，而最小二乘法有巨大誤差。外點(diǎn)干擾最小二乘法因?yàn)樗鼈兺ǔＳ芯薮蟮恼`差。

2.3 改進(jìn)的SIFT算法

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

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

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

圖1 用于進(jìn)行實(shí)驗(yàn)的組圖

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

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

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

表1 SIFT與改進(jìn)的SIFT的實(shí)驗(yàn)結(jié)果對(duì)比

表2 SIFT與改進(jìn)SIFT運(yùn)行的時(shí)間對(duì)比

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

4 結(jié)語

本文分析了SIFT匹配算法的原理及其存在的缺點(diǎn)，提出了一種改進(jìn)的SIFT匹配算法。該算法旨在提高SIFT算法匹配的速度與精度。通過利用Harris角點(diǎn)檢測(cè)算法在求取SIFT極值點(diǎn)時(shí)進(jìn)行進(jìn)一步篩選，減少了SIFT特征點(diǎn)的匹配點(diǎn)對(duì)數(shù)，同時(shí)也相應(yīng)地提高了精度。在得到匹配點(diǎn)后，對(duì)原始圖像與測(cè)試圖像進(jìn)行一次逆向匹配，接著利用RANSAC對(duì)得到的匹配點(diǎn)進(jìn)行進(jìn)一步處理，刪除外點(diǎn)，選擇正確的匹配點(diǎn)對(duì)，使匹配精度提高。實(shí)驗(yàn)結(jié)果表明改進(jìn)的算法相對(duì)于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] 唐朝偉，肖健，邵艷清，苗光勝.一種改進(jìn)的SIFT描述子及其性能分析[J].武漢大學(xué)學(xué)報(bào)信息科學(xué)版，2012（1）:11～16

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

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

[11] 江道寅.基于SIFT圖像配準(zhǔn)算法的研究[D].中國(guó)科技大學(xué)，2011:45～47

[12] 王靜.基于SIFT和角點(diǎn)檢測(cè)的自動(dòng)圖像配準(zhǔn)方法研究[D].華中科技大學(xué)，2010：19～24

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

[14] 常青，張斌，邵金玲.基于SIFT和RANSAC的特征圖像匹配方法[J].華東理工大學(xué)學(xué)報(bào)自然科學(xué)版，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

林強(qiáng)（1983-），男，四川成都人，碩士，研究方向?yàn)橛?jì)算機(jī)視覺

2014-12-31

2015-01-21