SIFT算法圖像自適應優化

汪麗華，汪道寅，王澤梁

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

0 引言

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

1 SIFT算法簡介

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

1.1 圖像特征點確定

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

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

1.2 特征描述符形成

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

1.3 特征點匹配

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

2 算法優化思路

Lowe根據大量圖像統計的歐氏距離比概率密度分布［1］將距離比區間固定為［0，0.8］，此方法未必恰當，因其不能體現具體圖像的歐氏距離比概率密度分布。具體圖像匹配時，該區間并不總能適應。為使區間參數具有盡可能高的適應性以滿足不同情況需要，該區間參數應能根據圖像自適應調整。

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

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

3 實驗結果及分析

3.1 實驗圖像

實驗以湖邊教學樓圖像為例，如圖1所示，圖1(a)為大小131×131的參考圖像，圖1(b)為圖1(a)逆時針旋轉30°后形成的大小為179×179的待配準圖像。

3.2 特征產生與表示

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

圖1 參考圖像和待配準圖像

圖2 參考圖像和待配準圖像的特征點分布

3.3 距離比區間優化過程

實驗中歐氏距離比區間參數尋優過程如圖3所示。通過分塊查找的算法，距離比區間參數不斷尋優，直到最大重復率與相應距離比區間。圖1的實驗圖像的配準算法共進行了15輪分塊，重復率取得0.982 6，距離比區間上界取得0.689 2。由圖3可以看到，距離比區間參數通過不斷分塊、擺動、接近并最后取得適合的取值。

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

4 結束語

因SIFT算法具有尺度、旋轉、仿射和光照等不變性等優點，因而普遍應用于各類圖像配準領域。本文在該算法的特征匹配階段分塊隨機擺動調整距離比區間，通過實驗驗證，這一優化能在增加可接受的運算量下找到更優的距離比區間，更適應具體圖像配準。后續工作將對不同類型的圖像進行更多實驗和比較以分析距離比范圍的取值規律。

圖3 距離比區間迭代過程

圖4 距離比區間與重復率的關系

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