SIFT算法圖像自適應(yīng)優(yōu)化

汪麗華，汪道寅，王澤梁

(1.黃山學(xué)院信息工程學(xué)院，安徽 黃山245041;2.中國科學(xué)技術(shù)大學(xué)電子工程與信息科學(xué)系，安徽 合肥，230027;3.合肥工業(yè)大學(xué)計算機(jī)與信息學(xué)院，安徽合肥230009)

0 引言

尺度不變特征變換(Scale-Invariant Feature Transform，SIFT)算法具有尺度、旋轉(zhuǎn)、仿射和光照等不變性的特征［1］。該算法主要包含兩個階段:一是SIFT特征生成，即從待配準(zhǔn)圖像中提取對尺度縮放、旋轉(zhuǎn)、亮度變化無關(guān)的特征向量;二是SIFT特征向量的匹配。通過對比SIFT，PCA-SIFT，steerable filter，moment invariants等數(shù)10種特征描述后指出［2］，SIFT是目前最為有效地特征檢測算子。SIFT算法因其性能的優(yōu)異，得到廣泛關(guān)注，陸續(xù)出現(xiàn)了一些變種算法，PCA-SIFT 算法［3］、GLOH 算法［2］、SURF 算法［4］、ASIFT算法［5］等。本文通過對SIFT算法配準(zhǔn)過程進(jìn)行研究，針對其未根據(jù)圖像調(diào)整配準(zhǔn)區(qū)間的不足實(shí)現(xiàn)了圖像自適應(yīng)的配準(zhǔn)區(qū)間參數(shù)優(yōu)化方法，實(shí)驗(yàn)表明優(yōu)化更有效的實(shí)現(xiàn)了圖像配準(zhǔn)。

1 SIFT算法簡介

二維圖像在計算機(jī)中可以表示為二維灰度矩陣，從不同的距離觀察同一場景則得到該場景的不同尺度下的圖像，構(gòu)成了圖像金字塔，即該場景的尺度空間表示。

1.1 圖像特征點(diǎn)確定

圖像金字塔可以用圖像和可變高斯核函數(shù)的卷積表示。Lowe利用歸一化拉普拉斯近似，對圖像金字塔相鄰層求差，構(gòu)造出差分高斯金字塔，其表示如下:

用梯度方向直方圖來統(tǒng)計鄰域象素的梯度方向。在0～360°的梯度方向中，每10°表示為一個柱，直方圖的峰值便是該特征點(diǎn)主方向。

1.2 特征描述符形成

在以特征點(diǎn)為中心的16×16的象素區(qū)域中(不含特征點(diǎn)所在行、列)，利用高斯加權(quán)法統(tǒng)計每個4×4的小塊的8個方向的梯度方向直方圖的累加值，構(gòu)成16×16/4×4=16個種子點(diǎn)。特征描述符由所有小塊的梯度方向直方圖構(gòu)成。因此，最終形成8×16=128維的SIFT特征向量。

1.3 特征點(diǎn)匹配

當(dāng)最近鄰和次近鄰之間的歐氏距離的比值|DA－DB|/|DA－DC|滿足一定區(qū)間范圍要求時，此時的最近鄰歐氏距離所對應(yīng)的特征點(diǎn)是匹配特征點(diǎn)。因此可通過計算特征描述符之間的歐氏距離大小來確定2個特征點(diǎn)的匹配度。當(dāng)2個特征描述符的歐氏距離最小且與次最小歐氏距離的比值屬于區(qū)間［0，0.8］，則這2個特征點(diǎn)為匹配點(diǎn)。

2 算法優(yōu)化思路

Lowe根據(jù)大量圖像統(tǒng)計的歐氏距離比概率密度分布［1］將距離比區(qū)間固定為［0，0.8］，此方法未必恰當(dāng)，因其不能體現(xiàn)具體圖像的歐氏距離比概率密度分布。具體圖像匹配時，該區(qū)間并不總能適應(yīng)。為使區(qū)間參數(shù)具有盡可能高的適應(yīng)性以滿足不同情況需要，該區(qū)間參數(shù)應(yīng)能根據(jù)圖像自適應(yīng)調(diào)整。

對于同一場景的兩幅圖像，定義其中都出現(xiàn)的特征點(diǎn)占所有特征點(diǎn)的比例為重復(fù)率，重復(fù)率反映了整個算法檢測到的特征點(diǎn)的幾何穩(wěn)定性，它可以作為圖像配準(zhǔn)算法評價的一個標(biāo)準(zhǔn)。通過在算法中加入自適應(yīng)過程來找到與具體圖像相適應(yīng)的歐氏距離比區(qū)間參數(shù)，用重復(fù)率來衡量參數(shù)是否已適應(yīng)。重復(fù)率大，則表明匹配程度高，區(qū)間選取合理;反之則區(qū)間選取越不合理。目前尚無研究成果表明重復(fù)率與歐氏距離比區(qū)間設(shè)定的關(guān)系，通過大量實(shí)驗(yàn)，得出歐氏距離比區(qū)間上界在［0.4，0.8］之間較為恰當(dāng)。匹配區(qū)間上界太大，則要求太寬泛，錯配點(diǎn)將增多;匹配區(qū)間上界太小，則要求太嚴(yán)，正配點(diǎn)將減少。目前已有很多智能優(yōu)化方法，如遺傳算法、蟻群算法等。由于僅需對歐氏距離比區(qū)間參數(shù)在已明確的大致范圍內(nèi)進(jìn)行調(diào)整，為減少不必要的時間消耗可不采用上述智能方法。從歐氏距離比概率密度分布曲線可知，正配點(diǎn)的概率密度在距離比0.45左右時達(dá)到極值，而后開始減小，因而距離比設(shè)定在前端的可能性更大些，故按照斐波那契數(shù)列將區(qū)間分塊，塊內(nèi)隨機(jī)擺動探測。具體思路為:(1)設(shè)待找尋區(qū)間為［l，h］，以斐波那契數(shù)列前n項(xiàng)為長度將區(qū)間劃分為n塊;(2)在每塊中隨機(jī)產(chǎn)生一點(diǎn)c1～cn，計算其重復(fù)率R(ci);(3)令nm=max(R(ci))，選取nm所在的區(qū)間作為新的待找尋區(qū)間，劃分為n塊，重復(fù)步驟(2)直至前后兩次的nm相差小于0.01或找尋次數(shù)大于50或nm=1。

較之于二分查找的方法，斐波那契分塊充分考慮了正配點(diǎn)在距離比設(shè)定變化時的概率密度分布趨勢，在正配點(diǎn)高密度處查找更多，同時一次劃分更多塊，整個算法循環(huán)次數(shù)減少。由于匹配環(huán)節(jié)占SIFT算法中的整個運(yùn)算比例很小，故以上過程不會給SIFT算法帶來太大的運(yùn)算負(fù)擔(dān)。

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

3.1 實(shí)驗(yàn)圖像

實(shí)驗(yàn)以湖邊教學(xué)樓圖像為例，如圖1所示，圖1(a)為大小131×131的參考圖像，圖1(b)為圖1(a)逆時針旋轉(zhuǎn)30°后形成的大小為179×179的待配準(zhǔn)圖像。

3.2 特征產(chǎn)生與表示

參考圖像共檢測到148個特征點(diǎn)，待配準(zhǔn)圖像共檢測到164個特征點(diǎn)，檢測結(jié)果如圖2所示。對檢測到的特征點(diǎn)生成特征描述算子時，描述子的位置和特征點(diǎn)的位置一致。

圖1 參考圖像和待配準(zhǔn)圖像

圖2 參考圖像和待配準(zhǔn)圖像的特征點(diǎn)分布

3.3 距離比區(qū)間優(yōu)化過程

實(shí)驗(yàn)中歐氏距離比區(qū)間參數(shù)尋優(yōu)過程如圖3所示。通過分塊查找的算法，距離比區(qū)間參數(shù)不斷尋優(yōu)，直到最大重復(fù)率與相應(yīng)距離比區(qū)間。圖1的實(shí)驗(yàn)圖像的配準(zhǔn)算法共進(jìn)行了15輪分塊，重復(fù)率取得0.982 6，距離比區(qū)間上界取得0.689 2。由圖3可以看到，距離比區(qū)間參數(shù)通過不斷分塊、擺動、接近并最后取得適合的取值。

距離比區(qū)間參數(shù)對不同的圖像其值的選取是不同的，并且具有不同的分布，所以應(yīng)該針對不同的圖像進(jìn)行選擇。本文圖像的距離比區(qū)間與重復(fù)率的關(guān)系如圖4所示，可知圖像距離比上界設(shè)定在0.72后重復(fù)率下降，因而其最優(yōu)距離比上界約為0.72，由此亦論證固定距離比區(qū)間上界為0.8是不恰當(dāng)?shù)?。由于算法利用斐波那契?shù)列分塊尋優(yōu)思想，能夠較快的找到此最優(yōu)參數(shù)。

4 結(jié)束語

因SIFT算法具有尺度、旋轉(zhuǎn)、仿射和光照等不變性等優(yōu)點(diǎn)，因而普遍應(yīng)用于各類圖像配準(zhǔn)領(lǐng)域。本文在該算法的特征匹配階段分塊隨機(jī)擺動調(diào)整距離比區(qū)間，通過實(shí)驗(yàn)驗(yàn)證，這一優(yōu)化能在增加可接受的運(yùn)算量下找到更優(yōu)的距離比區(qū)間，更適應(yīng)具體圖像配準(zhǔn)。后續(xù)工作將對不同類型的圖像進(jìn)行更多實(shí)驗(yàn)和比較以分析距離比范圍的取值規(guī)律。

圖3 距離比區(qū)間迭代過程

圖4 距離比區(qū)間與重復(fù)率的關(guān)系

［1］ David L G.Distinctive Image Features from Scale-invariant Keypoints［J］.International Journal of Computer Vision，2004，60(2):91－110.

［2］ Mikolajczyk k，Schmid C.A Performance Evaluation of Local Descriptors［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27(10):1 615－1 630.

［3］ Ke Y，Sukthankar R.PCA-SIFT:A more distinctive representation for local image descriptors［C］.Washington，DC:Proceedings of IEEE International Conference on Computer Vision and Pattern Recognition，2004:511－517.

［4］ Bay H，Tuytelaars T，Gool L V.SURF:Speeded up robust features［C］.Berlin:Springer-Verlag，2006:404 －417.

［5］ Morel J M，Yu G S.ASIFT:A New Framework for Fully Affine Invariant Image Comparison［J］.Society for Industrial and Applied Mathematics Journal on Image Sciences，2009，2(2):438 －469.

［6］ Mikolajczyk K，Schmid C.Scale and Affine invariant interest point detectors［J］.International Journal of Computer Vision，2004，60(1):63－86.