基于SIFT的圖像匹配算法

周麗芬

(曲靖師范學院計算機科學與工程學院，云南 曲靖 655011)

0 引言

圖像匹配是計算機視覺和圖像處理領(lǐng)域中的一個重要研究方向，它是許多其它應用的重要基礎，如圖像識別、圖像檢索、目標跟蹤、數(shù)據(jù)挖掘和3D重建等[1]。圖像匹配算法大體上可分為2種:基于全局特征的匹配算法和基于局部特征的匹配算法[2]。由于局部特征只與特征點周圍局部區(qū)域有關(guān)，所以基于局部特征的匹配算法更加穩(wěn)定。目前廣泛應用的基于局部特征的提取算法是Lowe提出的尺度不變特征變換 SIFT(Scale-Invariant Feature Transform)算法[1]，由于該算法的優(yōu)越性，現(xiàn)在已經(jīng)廣泛應用于計算機視覺的各個領(lǐng)域。

隨后出現(xiàn)了基于SIFT算法的很多改進算法，例如 PCA-SIFT[3]、 SURF[4]、 GSIFT[5]、 CSIFT[6]、ASIFT[7]等。文獻[2]中，作者對這幾種算法進行了詳細的分析與比較，把不同算法應用于各種圖像，評價各算法對尺度和旋轉(zhuǎn)、光照、模糊、仿射等不變性的能力，作者將評價等級分為3種等級，依次是:Good，Better，Best。利用SIFT算法提取特征對模糊圖像進行匹配的最終評價是Good。國內(nèi)學者也對SIFT算法進行了改進，文獻[8-9]等對SIFT算法的改進基本都是針對描述子部分，改變了關(guān)鍵點局部區(qū)域的結(jié)構(gòu)或者簡化了描述子構(gòu)造，雖然在某些情況比原始算法效果要好，但是由于描述子的改變可能會使得算法對于其它情況的效果并不理想。近年來也出現(xiàn)了一些新的描述子，如文獻[10-12]等，它們盡管效果很好，但是由于計算復雜度較高，描述子維數(shù)較高且結(jié)構(gòu)較復雜，所以使用價值有待提高。

實驗中發(fā)現(xiàn)，當要匹配的圖像比較模糊時，利用SIFT算法提取的關(guān)鍵點較少，導致匹配時正確匹配率不高。針對這種情況，本文提出基于SIFT的針對模糊圖像匹配增強算法，首先利用增強算子對圖像進行銳化處理，使其邊緣得到突出，再利用算法進行關(guān)鍵點提取。這樣的操作使獲得的關(guān)鍵點數(shù)量比直接利用SIFT算法有大幅度提高。當然關(guān)鍵點數(shù)量多并不意味著匹配效果一定好，因為關(guān)鍵點增多，誤匹配率也會增大。因此為了提高匹配率，利用雙向匹配算法[13]來刪除錯誤匹配，從而提高匹配精度。

1 SIFT算法

基本的SIFT算法包括4個步驟:1)構(gòu)造高斯差分金字塔;2)檢測極值點;3)為關(guān)鍵點分配方向;4)生成描述子。下面簡要介紹SIFT算法。

1.1 構(gòu)造高斯差分金字塔

首先建立多尺度空間，即高斯金字塔，通過將輸入圖像I(x，y)與不同尺度的高斯函數(shù)卷積得到高斯金字塔一組的每一層，然后由上一組尺度為2倍初始尺度的圖像降采樣得到下一組的第一層，按照上一組同樣的方式得到各層，最終構(gòu)造高斯金字塔。將高斯金字塔相鄰2層相減得到高斯差分金字塔:

1.2 檢測極值點

在高斯差分金字塔每組的第二層到倒數(shù)第二層檢測極值點，所檢測的點要與同一層周圍8個點和上下2層該點周圍的9×2個點比較，即總共與周圍26個點進行比較，這樣得到初步的極值點。再通過子像素插值精確定位極值點并刪除對比度較低的極值點，剩下的極值點即為最終的關(guān)鍵點。

1.3 為關(guān)鍵點分配方向

利用關(guān)鍵點鄰域像素的梯度方向分布特性為每一個關(guān)鍵點分配方向，使得算子具有旋轉(zhuǎn)不變性。首先計算關(guān)鍵點處的梯度模值和方向。在以關(guān)鍵點為中心的鄰域窗口內(nèi)采樣，并利用直方圖統(tǒng)計鄰域像素的梯度方向，直方圖的峰值對應的度數(shù)代表了關(guān)鍵點的主方向。當存在超過主峰值80%的峰值時，其對應的方向作為該關(guān)鍵點的輔方向。

1.4 生成描述子

首先將坐標軸按照關(guān)鍵點的方向旋轉(zhuǎn)，保證旋轉(zhuǎn)不變性，然后以關(guān)鍵點為中心取16×16的窗口，分割成4×4的小區(qū)域，每個小區(qū)域上計算8個方向的梯度直方圖，繪制每個梯度方向的累加值，就可形成一個種子點，因此總共有16個種子點，每個種子點由8個數(shù)字組成，所以最終形成了一個長度為128的向量，即為該關(guān)鍵點的SIFT特征向量。計算每一個關(guān)鍵點的SIFT特征向量，得到最終描述子，利用描述子可以進行匹配。

2 基于銳化的匹配算法

通過SIFT算法的原理和實驗可以發(fā)現(xiàn)，SIFT算法檢測到的許多關(guān)鍵點都是邊緣點，然而由于在構(gòu)造金字塔的時候會將圖像經(jīng)過多次高斯平滑，使得邊緣點變得很平滑，如果所獲取的圖像本來就質(zhì)量不高，直接利用SIFT算法提取關(guān)鍵點進行匹配，將會大大降低匹配精度。為了提高匹配率，本文提出先對圖像進行銳化處理以提高SIFT提取的關(guān)鍵點數(shù)，再采用雙向匹配算法進行匹配。

2.1 銳化算子

圖像銳化處理的主要目的是突出圖像灰度的過渡部分，即邊緣，二階微分是經(jīng)常用來增強邊緣的算子，其中拉普拉斯算子是最簡單的各項同性微分算子[14]。一個圖像函數(shù)f(x，y)的拉普拉斯算子定義為:

其中二階導數(shù)計算的離散公式為:

則拉普拉斯算子可表示為:

實際應用中，拉普拉斯算子可以通過下面的濾波模板來實現(xiàn):

2.2 雙向匹配算法

在文獻[13]中，為了提高匹配精度，提出了雙向匹配:利用SIFT算法進行特征提取，得到2幅待匹配圖像的特征集，對第一個特征集中的每一個特征，在第二個特征集中計算最鄰近距離和次鄰近距離的比值(Ratio)，如果比值小于某閾值則匹配。這樣經(jīng)過第一輪匹配后，再在已匹配點中，對第二個特征集中的每一個特征，在第一個特征集中計算最鄰近和次鄰近距離的比值，如果比值小于某閾值則為匹配，當?shù)诙纹ヅ鋾r，這樣的關(guān)鍵點才規(guī)定為最終的匹配點。

在Lowe的算法中設定的閾值為Ratio=0.8，由于閾值設定得越小，匹配點數(shù)越少，閾值設定得越大，匹配點數(shù)越多，但是錯誤匹配也會增多。本文通過大量的實驗，設定的2次閾值分別為Ratio1=0.8，Ratio2=0.5時效果較好。第一個閾值較大，這樣可以得到較多的匹配點，第二個閾值較小，這樣可以刪除很多錯誤匹配，從而提高匹配精度。

2.3 本文算法

本文算法是在傳統(tǒng)SIFT基礎上增加圖像銳化處理過程，并且在匹配時使用雙向匹配算法。匹配算法步驟如下:

1)讀入待匹配的2幅圖像，將圖像與拉普拉斯濾波模板卷積得到銳化后的圖像;

A：根據(jù)十九大精神，我們企業(yè)已經(jīng)進入了新的發(fā)展階段。前些年我們已經(jīng)著手進行了調(diào)整轉(zhuǎn)型，現(xiàn)在需要在這個基礎上進一步思考持續(xù)發(fā)展的問題。當前公司面臨的任務是印刷產(chǎn)業(yè)的轉(zhuǎn)型升級、環(huán)保治理，等等。我們認為，在新的形勢下，二二〇七工廠，應當把服務首都功能和為軍服務保障統(tǒng)一起來，這是企業(yè)持續(xù)發(fā)展的基礎，是體現(xiàn)企業(yè)存在價值的重要方面。

2)使用傳統(tǒng)SIFT對銳化后的圖像進行特征提取，得到描述特征點的2個特征向量集;

3)使用雙向匹配算法以歐氏距離為測度進行圖像匹配。

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

為了驗證該算法的優(yōu)越性，進行了以下實驗。實驗平臺:處理器為Intel(R)Pentium(R)CPU G620@2.60 GHz;內(nèi)存為 4.00 GB(2.99 GB 可用);系統(tǒng)類型為32位Win7系統(tǒng);軟件為Matlab 2012a。

3.1 仿真實驗

利用Cameraman的512×512的灰度圖像，首先對其進行高斯平滑，得到平滑后的模糊圖像，然后將平滑后的模糊圖像與原圖像進行匹配。采用以下3種匹配方式:

方式1:直接利用SIFT算法提取特征進行匹配;

方式2:先利用拉普拉斯算子對模糊圖像銳化處理，再利用SIFT算子提取特征進行匹配;

方式3:首先利用拉普拉斯算子對模糊圖像銳化處理，然后利用SIFT算子提取特征，最后利用雙向匹配算法進行匹配。

由圖1可以看出，在圖1(a)中匹配點數(shù)不多，而且存在很多錯誤匹配;由于利用拉普拉斯算子銳化了模糊圖像，所以圖1(b)中匹配點數(shù)增多，但是錯誤匹配也會增多;如果利用雙向匹配算法進行匹配可以在很大程度上刪除錯誤匹配點，如圖1(c)中錯誤匹配幾乎沒有，匹配點數(shù)也較多，所以匹配效果最好。

圖1 3種方式匹配結(jié)果

圖2 不同sigma時3種方式的匹配率

圖2是不同sigma值時3種情況的匹配率，由圖可以看出，方式3比前2種方式的匹配率都高，匹配效果最好。在不同sigma值時，方式2有時比方式1的匹配率高，有時反而低，這是因為雖然經(jīng)過拉普拉斯算子銳化后使得匹配點數(shù)增多，但是同時也會使得錯誤匹配點數(shù)增多，所以匹配率可能變大，也可能變小，這與sigma值有關(guān)，即與匹配圖像本身質(zhì)量有關(guān);但是，如果匹配的時候利用雙向匹配法，設定不同的閾值，這樣可以刪除很多錯誤匹配，從而使得匹配率增大，匹配效果較好。

3.2 實際圖像實驗

實驗所用圖像如圖3所示，是標準測試圖像中驗證模糊不變性的圖像[15]。圖3中P1是清晰的圖像，P2～P6為模糊的圖像，模糊程度依次增大。實驗的方法是分別用P2～P6與P1匹配。

圖3 實驗圖像

將本文算法與直接由SIFT特征進行匹配的算法相比較，計算P2～P6與P1的匹配率，得到如圖4所示的結(jié)果?？梢钥闯鯬2～P6與P1匹配結(jié)果中，本文算法都比直接由SIFT特征進行匹配的算法要好，由于P2～P6圖像模糊程度是逐漸增大的，直接利用SIFT特征進行匹配時的匹配率會逐漸減小，因為圖像越模糊，檢測的關(guān)鍵點越少。本文算法可以通過拉普拉斯算子銳化，將圖像邊緣增強，從而檢測到的關(guān)鍵點數(shù)增加，再通過雙向匹配法來減少錯誤匹配，進而達到很高的匹配率。例如，當圖像很模糊時(圖3中P6)，直接利用SIFT特征進行匹配的匹配率為96.91%，而本文算法的匹配率為99.02%。圖5列出了2種方法對P1與P3的匹配結(jié)果。圖5(a)是直接利用SIFT特征匹配的結(jié)果，圖中顯示明顯有很多錯誤的匹配，而且總的匹配點數(shù)沒有圖5(b)中的總匹配點數(shù)多;圖5(b)是本文算法的匹配結(jié)果，圖中顯示總的匹配點數(shù)較多，而且?guī)缀鯖]有錯誤匹配?？傊?，由實驗結(jié)果可以看出本文的算法比基本的基于SIFT特征的匹配算法效果要好。

圖4 匹配率

圖5 P3與P1的匹配效果圖

4 結(jié)束語

由于SIFT算法中要計算主方向，而主方向的計算是造成誤差的一個主要原因[12]，但是本文在傳統(tǒng)的SIFT算法的基礎上，通過銳化處理和利用雙向匹配算法進行特征匹配，從而減小了匹配誤差，在沒有改變SIFT算法本質(zhì)的同時保證了匹配精度。實驗結(jié)果表明本文提出的方法在提高匹配效果的同時可以加強基本SIFT算子進行匹配的模糊不變性。由于本文提出的方法增加了對圖像的銳化處理，并進行雙相匹配的操作，因此算法復雜度會增加。但是增加的時間復雜度相對原始算法本身的復雜度較小，所以在一定范圍內(nèi)可以利用本文所提出的算法進行匹配，以達到提高匹配率的目的。

[1] Lowe D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60(2):91-110.

[2] Wu Jian，Cui Zhiming，Sheng V S，et al.A comparative study of SIFT and its variants[J].Measurement Science Review，2013，13(3):122-131.

[3] Ke Yan，Sukthankar R.PCA-SIFT:A more distinctive representation for local image descriptors[C]//Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.2004，2:506-513.

[4] Bay H，Ess A，Tuytelaars T，et al.Speeded-up robust features(SURF)[J].Computer Vision and Image Understanding，2008，110(3):346-359.

[5] Mortensen E N，Deng Hongli，Shapiro L.A SIFT descriptor with global context[C]//Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.2005，1:184-190.

[6] Abdel-Hakim A E，F(xiàn)arag A A.CSIFT:A SIFT descriptor with color invariant characteristics[C]//Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.2006，2:1978-1983.

[7] Morel J M，Yu Guoshen.ASIFT:A new framework for fully affine invariant image comparison[J].SIAM Journal on Imaging Sciences，2009，2(2):438-469.

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

[9] 張官亮，鄒煥新，秦先祥，等.基于改進SIFT特征和圖轉(zhuǎn)換匹配的圖像匹配算法[J].計算機應用研究，2013，30(9):2861-2864.

[10] Heikkila M，Pietikainen M，Schmid C.Description of interest regions with local binary patterns[J].Pattern Recognition，2009，42(3):425-436.

[11] Gupta R，Patil H，Mittal A.Robust order-based methods for feature description[C]//Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition.2010:334-341.

[12] Fan Bin，Wu Fuchao，Hu Zhanyi.Rotationally invariant descriptors using intensity order pooling[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34(10):2031-2045.

[13] 騫森，朱劍英.基于改進的SIFT特征的圖像雙向匹配算法[J].機械科學與技術(shù)，2007，26(9):1179-1182.

[14] 阮秋琦.數(shù)字圖像處理學[M].北京:電子工業(yè)出版社，2007.

[15] Katholieke Universiteit Leuven.Affine Covariant Features[DB/OL].http://www.robots.ox.ac.uk/～ vgg/research/affine/index.html，2007-07-15.