基于圖像自相關(guān)矩陣的改進(jìn)SIFT算法研究

劉光鑫

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

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

一、引言

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

二、SIFT算法原理

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

三、改進(jìn)SIFT算法

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

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

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

（2）生成2d維的特征描述子。將特征點(diǎn)的鄰域劃分為兩個(gè)同心圓，再以（1）中計(jì)算出的特征點(diǎn)主方向?yàn)閰⒖挤较?，每次逆時(shí)針旋轉(zhuǎn)角度，確定其它d-1條直線，，…，，如圖1所示。計(jì)算特征點(diǎn)鄰域每塊區(qū)域的自相關(guān)矩陣M的跡Trace（M）。

選取適當(dāng)?shù)男D(zhuǎn)角，生成相應(yīng)維數(shù)的特征描述子，再對(duì)生成的特征描述子進(jìn)行歸一化處理。如選取，計(jì)算每個(gè)區(qū)域的自相關(guān)矩陣M的跡生成72維的特征描述符。

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

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

四、實(shí)驗(yàn)結(jié)果分析

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

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

五、總結(jié)

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

參 考 文 獻(xiàn)

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

[2] 丁燦，曲長文等. 改進(jìn)的SIFT匹配算法[J]. 計(jì)算機(jī)科學(xué)與應(yīng)用，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] 馬頌德，馬正友. 計(jì)算機(jī)視覺——計(jì)算理論與算法基礎(chǔ)[M]. 北京：科學(xué)出版社，1998.