汪麗華，汪道寅，王澤梁

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

0 引言

尺度不變特征變換(Scale-Invariant Feature Transform，SIFT)算法具有尺度、旋轉(zhuǎn)、仿射和光照等不變性的特征［1］。該算法主要包含兩個(gè)階段:一是SIFT特征生成，即從待配準(zhǔn)圖像中提取對(duì)尺度縮放、旋轉(zhuǎn)、亮度變化無(wú)關(guān)的特征向量;二是SIFT特征向量的匹配。通過(guò)對(duì)比SIFT，PCA-SIFT，steerable filter，moment invariants等數(shù)10種特征描述后指出［2］，SIFT是目前最為有效地特征檢測(cè)算子。SIFT算法因其性能的優(yōu)異，得到廣泛關(guān)注，陸續(xù)出現(xiàn)了一些變種算法，PCA-SIFT 算法［3］、GLOH 算法［2］、SURF 算法［4］、ASIFT算法［5］等。本文通過(guò)對(duì)SIFT算法配準(zhǔn)過(guò)程進(jìn)行研究，針對(duì)其未根據(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算法簡(jiǎn)介

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

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

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

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

1.2 特征描述符形成

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

1.3 特征點(diǎn)匹配

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

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

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

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

較之于二分查找的方法，斐波那契分塊充分考慮了正配點(diǎn)在距離比設(shè)定變化時(shí)的概率密度分布趨勢(shì)，在正配點(diǎn)高密度處查找更多，同時(shí)一次劃分更多塊，整個(gè)算法循環(huán)次數(shù)減少。由于匹配環(huán)節(jié)占SIFT算法中的整個(gè)運(yùn)算比例很小，故以上過(guò)程不會(huì)給SIFT算法帶來(lái)太大的運(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)逆時(shí)針旋轉(zhuǎn)30°后形成的大小為179×179的待配準(zhǔn)圖像。

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

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

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

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

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

實(shí)驗(yàn)中歐氏距離比區(qū)間參數(shù)尋優(yōu)過(guò)程如圖3所示。通過(guò)分塊查找的算法，距離比區(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ù)通過(guò)不斷分塊、擺動(dòng)、接近并最后取得適合的取值。

距離比區(qū)間參數(shù)對(duì)不同的圖像其值的選取是不同的，并且具有不同的分布，所以應(yīng)該針對(duì)不同的圖像進(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é)束語(yǔ)

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

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

圖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.