劉光鑫

【摘要】 針對尺度不變特征變換（SIFT）匹配算法存在計算量大、復雜性等問題，本文提出了一種基于圖像自相關矩陣的跡的改進SIFT匹配算法。首先，將特征點的鄰域劃分為兩個同心圓，再以特征點的主方向為基準方向，每次逆時針旋轉度，將特征點鄰域圖像劃分了多個區(qū)域；其次，為每個區(qū)域圖像計算自相關矩陣的跡，按逆時針方向組合形成SIFT特征描述符；最后，對生成的特征描述符進行歸一化處理，得到較低維數(shù)的特征描述符，新的特征描述符提高了圖像匹配的效率。實驗結果表明，與傳統(tǒng)算法相比，改進的算法在保持較高匹配精度的情況下顯著提高了匹配的速度。

【關鍵詞】 SIFT算法 自相關矩陣 特征描述符 圖像匹配

一、引言

近年來，許多學者對圖像匹配問題做了大量的研究。按圖像匹配的不變特征分類，匹配方法可分為基于全局特征和基于局部特征的兩大類匹配方法。Hu不變矩，Hausdorff距離等是常用的全局匹配特征，基于這些特征的匹配方法要在整幅圖像內進行搜索，計算量較大，且沒有考慮局部特征，因此匹配的效果不太好。基于局部特征的匹配方法主要是基于特征點的匹配，其已成為圖像配準技術的主流方向和發(fā)展趨勢。目前最成功的局部匹配算子是Lowe在1999年提出的尺度不變特征變換（Scale Invariant Feature Transform），該算法較好的解決了場景部分遮擋、旋轉縮放、視點變化引起的圖像變形的等問題，但是算法存在因特征描述符維數(shù)過高而使匹配計算過于復雜、匹配時間過長等問題。針對生成SIFT高維特征描述向量的耗時性和匹配計算的復雜性，國內許多研究者對SIFT算法提出改進。改進算法的思想主要是在較好的保持特征描述向量的穩(wěn)定性上，降低特征描述向量的維數(shù)，減少生成特征描述符計算量和提高特征匹配效率。姚文偉等[1]提出的在以特征點為中心的圓形區(qū)域內構造4個圓環(huán)，在每個圓環(huán)內分別計均勻分布的12個方向上的梯度直方圖，最終生成維的特征描述向量；丁燦等[2]提出的計算以特征點為中心的8個同心方環(huán)內8個方向的梯度累加值，形成維的特征描述向量；YanKe[3]等使用PCA 對SIFT特征描述符進行降維，但該算法是在SIFT計算結果的基礎上，對于可以預先計算的離線情況是有用的，但對于實時情況，反而增加了計算量。針對SIFT算子存在的計算量大等問題，本文提出了基于圖像自相關矩陣的跡的改進SIFT算法。該算法降低了SIFT特征描述符的維數(shù)，提高了匹配的效率。

二、SIFT算法原理

SIFT算法通過高斯濾波保證檢測出的特征點不受噪聲影響，在DoG圖像上尋找極值點消除了亮度變化對特征點檢測的影響，基于特征點鄰域梯度統(tǒng)計思想建立的特征描述子具有較強的抗噪聲能力，最后對特征描述向量的歸一化處理去除了光照的影響。上述步驟建立的特征描述算子對光照變化、噪聲、圖像旋轉、部分遮擋等具有一定不變性、穩(wěn)定性。該算法的主要步驟如下：（1）建立尺度空間和DoG金子塔；（2）關鍵點定位；（3）關鍵點主方向確定；（4）生成關鍵點的SIFT特征矢量。

三、改進SIFT算法

為了對SIFT算法進行改進，對上節(jié)SIFT算法各步驟在整個匹配過程所占用的時間進行了統(tǒng)計，結果大致如下：（1）建立圖像的DOG金字塔： 3%～5%；（2）求局部極值確定關鍵點：3%～17%；（3）計算關鍵點方向：4%～15%；（4）計生成特征描述符：42%～55%。SIFT算法的（1）～（3）步驟保證了特征點對噪聲、光照及旋轉有較高的魯棒性，是后續(xù)匹配效果的穩(wěn)固基石，只占整個匹配過程的約一半時間，可優(yōu)化的空間很少。因此改進算法主要是在特征點描述符上優(yōu)化。

原SIFT算法統(tǒng)計特征點鄰域內所有像素梯度信息，生成的SIFT特征描述子具有良好的穩(wěn)定性。本文改進的SIFT算法首先使用SIFT特征檢測算法前3步檢測出特征點，再在每個特征點鄰域內統(tǒng)計像素梯度直方圖確定特征點的主方向，然后以特征點主方向為基準方向，每次旋轉，將像素點的鄰域劃分為多個區(qū)域，計算每個區(qū)域的，生成的特征描述符有效避免了圖像旋轉而使特征描述子的改變，最后的歸一化處理減少了光照變化對特征描述子的影響。改進SIFT特征描述子生成的具體步驟：

（1）使用前文介紹的SIFT算法的前3步檢測出特征點并確定特征點的主方向。

（2）生成2d維的特征描述子。將特征點的鄰域劃分為兩個同心圓，再以（1）中計算出的特征點主方向為參考方向，每次逆時針旋轉角度，確定其它d-1條直線，，…，，如圖1所示。計算特征點鄰域每塊區(qū)域的自相關矩陣M的跡Trace（M）。

選取適當?shù)男D角，生成相應維數(shù)的特征描述子，再對生成的特征描述子進行歸一化處理。如選取，計算每個區(qū)域的自相關矩陣M的跡生成72維的特征描述符。

在匹配兩幅圖像過程中，把待匹配的圖像稱為基準圖像，另一幅圖像稱為后續(xù)圖像。使用SIFT算法檢測出來特征點并構建出了特征點描述向量后，計算特征點之間的歐式距離。

在SIFT向量匹配中，采用最近鄰NN方法，即待匹配特征點與后續(xù)圖像中特點的最近距離與次鄰近距離之間的比值來進行匹配準則。當NN比值小于設定閾值T ，則認為匹配成功，接收匹配點對。閾值的設定對匹配的結果有很大的影響，Lowe推薦使用T=0.8可以消除90%的錯誤匹配，而只有5%的正確匹配被剔出。

四、實驗結果分析

為了驗證改進的SIFT算法在保證對光照、噪聲及旋轉具有較高魯棒性的同時，較原SIFT具有更高的匹配效率，本文選取2對圖片進行實驗，對改進的SIFT算法進行測試，實驗平臺為：CPU Intel P4 2.4 GHz，內存1G，Windows 7，VS2010。比較兩種算法的正確匹配率、誤匹配數(shù)及匹配時間。實驗中最近距離/次鄰近距離的域T設為0.8。特征匹配率等于正確的匹配特征點數(shù)與兩幅圖像的總匹配數(shù)之比。匹配結果如表1所示，效果圖如圖1，圖2所示。

由結果可知，在圖像分別存在尺度變化及旋轉的條件下，36維的改進SIFT特征描述符保持了SIFT特征匹配的較高精確度，而且匹配時間大約減少10%。因此可得出改進的SIFT算法在保持較高匹配率的同時，提高了匹配的效率。

五、總結

本文針對尺度不變特征變換（SIFT）匹配算法存在計算量大、復雜性等問題，提出了基于圖像自相關矩陣M的跡的改進SIFT算法，該算法在保證較高精度的特征提取的同時，降低了特征描述字的維數(shù)；在特征匹配上，采用最近鄰歐氏距離作為度量標準，Best Bin First（BBF）作為搜索策略，快速計算得到粗匹配，在極線約束未知的條件下，利用RANSAC算法估計出基礎矩陣，計算得到極限約束，同時利用一致性約束、唯一性約束、互對應約束剔除虛假匹配，并通過實驗驗證其正確性。

參 考 文 獻

[1] 姚文偉. 圖像匹配算法SIFT的改進[J]. 鄭州輕工業(yè)學院學報，2011（6）：67-70

[2] 丁燦，曲長文等. 改進的SIFT匹配算法[J]. 計算機科學與應用，2012（2）204-208

[3] Ke Y. PCA-SIFT： a more distinctive representation for local image descriptors. CVPR 2004， 2： 506-513.

[4] Guil N.，Villalba J.，Zapata E.L..A fast hough transform for segment detection[C].IEEE Transactions on Image Processing，1995，4（11）：1541-1548

[5] M. A. Fischler and R. C. Bolles. Random sample consensus： A paradigm for model fitting with applications to image analysis and automated cartography [J]. Communications of the ACM， 1981， 24（6）： 381-395

[6] LOWE D G. Distinctive image features from scale-invariant key-points[J]. International Journal on Computer Vision， 2004， 60（2）： 91-110.

[7] 馬頌德，馬正友. 計算機視覺——計算理論與算法基礎[M]. 北京：科學出版社，1998.