基于ＳＩＦＴ特征的圖像檢索

摘要:提出一種多尺度圖像檢索算法，該算法基于SIFT特征提取，它將一幅圖像轉換成特征向量的集合，圖像間的相似距離是通過計算兩幅圖像特征向量間的歐氏距離來實現的。實驗結果很好地說明了該算法具有尺度#65380;平移#65380;旋轉不變性，一定的仿射#65380;光照不變性以及算法能很好地應用在特定形狀特征目標的檢索中。

關鍵詞:基于內容的圖像檢索; 尺度不變特征變換特征; K－L變換; 近似最近鄰搜索; 歐氏距離

中圖分類號:TP391.3文獻標志碼:A

文章編號:1001－3695(2008)02－0478－04

基于內容的視覺信息檢索是由于視覺信息的飛速膨脹而得到關注并被提出來的。如何快速準確地提取視覺信息內容是視覺信息檢索最關鍵的一步。當今流行的一些圖像檢索系統多利用圖像的底層特征，如顏色#65380;紋理#65380;形狀以及空間關系等。這些特征對于圖像檢索有著不同的作用，但是同時也存在著不足。顏色特征是一種全局特征，它對圖像或圖像區域的方向#65380;大小等變化不敏感，所以顏色特征不能很好地捕捉圖像中對象的局部特征，也不能表達顏色空間分布的信息。它也是一種全局特征，紋理特征只是物體表面的一種特性，并不能完全反映物體的本質屬性。最嚴重的一個缺點是，當物體受到光照#65380;反射等影響時，從二維圖像中反映出來的紋理不一定是物體真實的紋理。這些虛假的紋理均會對檢索造成誤導。全局的特征描述并不能很好地適應在對目標感興趣的圖像檢索。基于形狀的特征常常可以利用圖像中感興趣的目標進行檢索。但是形狀特征的提取，常常受到圖像分割效果的影響。空間關系特征可以加強對圖像內容的描述和區分能力，但空間關系特征對圖像或者目標的旋轉#65380;平移#65380;尺度變換等比較敏感，并且不能準確地表達場景的信息。圖像檢索領域急需一種能夠對目標進行檢索，并且對圖像目標亮度#65380;旋轉#65380;平移#65380;尺度甚至仿射不變的檢索算法。本文就是在這樣的基礎上提出的。

SIFT是David G. Lowe 2004年總結不變量技術的特征檢測方法，提出的一種對尺度空間#65380;圖像縮放#65380;旋轉甚至仿射不變的圖像局部特征描述算子。

SIFT特征向量有如下特性:a)局部性。SIFT特征向量是一種局部特征，其對旋轉#65380;尺度縮放#65380;亮度變化保持不變，并且對圖像目標受到部分遮擋的情況下也有很好的檢索性能。b)特殊性。SIFT特征向量包含豐富的圖像內容信息，適合在海量的目標數據庫中進行檢索#65380;匹配。c)多量性。僅有少量的一個目標也可以產生大量的SIFT特征向量。d)高效性。SIFT能夠快速地從圖像中提取出來，并且實現高效的特征匹配。

本文提出了一種基于SIFT特征提取的圖像檢索算法，并結合K－L變換對該特征向量進行主成分分析，降低向量空間維數，減少計算量。圖像間的相似特征向量的搜索由ANN搜索算法實現。文中描述了SIFT特征向量的提取過程，并給出三個不同的實驗來檢測該算法的檢索性能。

1SIFT特征提取算法

1.1圖像的多尺度表示

多尺度技術也稱為多分辨率技術。多尺度圖像技術指對圖像采用多尺度的表達，并在不同尺度下分別進行處理。在很多情況下，圖像中某種尺度下不容易看出或獲取的特性在另外的尺度下很容易看出來或檢測到。所以利用多尺度常可以更有效地提取圖像特征，獲取圖像內容。對同一幅圖像用不同的尺度表達后，相當于給圖像數據的表達增加了一個新的坐標。即除了一般使用的空間的分辨率外，現在又多了一個刻畫當前分辨率層次的新參數。如果用σ來標記這個新的尺度參數，則包含一系列有不同分辨率的圖像的數據結構可被稱為尺度空間(scale space)。可用G(x，y，σ)來表示圖像G(x，y)的尺度空間。Lindeberg在文獻[2]中證實在一些一般性的假設條件下，高斯核和高斯微分是尺度空間分析的惟一平滑核。

1.2SIFT特征描述

David G.Lowe在文獻[3]中提出一種稱之為SIFT的圖像局部特征描述算子，并通過實驗證實了該算子對圖像的尺度縮放#65380;平移#65380;旋轉變換保持不變，對圖像的亮度變化以及仿射變換也具有相當的穩健性(robust)。

SIFT算法的本質就是從圖像中提取SIFT關鍵點(keypoint)的過程。SIFT特征提取的算法包含四步驟。

1.2.1尺度空間的極值檢測

為了達到尺度不變性，理論上必須在圖像所有可能的尺度空間中搜索不變的特征，但是實際上這是不可能的。解決方法就是對尺度空間圖像進行亞采樣。將平滑和亞采樣重復進行，就可得到能構成金字塔的一系列圖像。如下定義二維高斯濾波函數。其中σ表示高斯函數的方差。

采用DoG算子建立的尺度空間如圖1所示。

圖1左邊顯示的Gaussian金字塔中，最底層就是沒有作過高斯濾波的原始圖像。高斯金字塔分為n階(octave)，每一階分為s1層。為了在這s層上檢測特征點，需要產生s+2幅DoG圖像，對應s+3幅Gaussian圖像。這s+3幅Gaussian圖像從下到上尺度比例以k遞增，即是說，若當前的Gaussian圖像的尺度參數為σ，則下一層的Gaussian圖像的尺度參數為kσ。為了要讓一階之間有s層，本文規定k=21/s。將同一階中的s+3層的Gaussian圖像，相鄰的圖像相減就產生了相應的s+2層DoG圖像。

為了產生下一階的Gaussian圖像，對上一階產生的最后一幅N×N的Gaussian圖像進行1:2的亞采樣，生成N/2×N/2的圖像。在亞采樣圖像基礎上重復上述建立s+3層Gaussian圖像的過程。

為了檢測D(x，y，σ)的局部極值點，需要比較DoG圖像中每個像素與其26個近鄰像素的值。若像素(x，y)是一個可能的SIFT關鍵點，則它必須在它周圍的26個近鄰像素(上一個尺度的9個點+同尺度的8個點+下一個尺度的9個點)中是極值點，如圖2所示。所有這樣的局部極值點，就構成了一個SIFT候選關鍵點的集合。

1.2.2關鍵點的確定

極值檢測得到的所有候選關鍵點，還必須通過兩步檢驗才能確定是關鍵點:一是它必須與周圍的像素有明顯的差異，也就是說低對比度的點不要;二是它不能是邊緣點。

對于每一個關鍵點，本文考慮它的鄰近的一個鄰域窗口內點的梯度方向，最多人投票的方向就當做該點的主方向。而每個鄰近的點對中央這個點的權重由高斯分布再乘上該點的梯度的大小來決定。

如果梯度直方圖中存在另一個相當于主峰值80%的峰值時，則將整個方向認為是該關鍵點的輔方向。一個關鍵點可能被指定多個方向(一個主方向，一個以上的輔方向)。這種情況下，就可復制同一個關鍵點，使它們分別朝向不同的方向。

1.2.4SIFT特征向量描述子

為了確保旋轉不變性，首先將坐標軸旋轉為關鍵點的方向。以一個關鍵點為中心，取8×8的窗口，將該窗口切成2×2的子窗口，統計每個子窗口中的方向直方圖，如圖3所示。

每一個子窗口的方向由其上4×4的小塊的方向用之前的方法來決定。圖中的每個關鍵點方向由2×2共4個種子點的方向決定，一個種子點有8個方向的信息，則每個關鍵點就有4×8=32維。

在實際計算過程中，為了增強匹配的穩健性，通常采用4×4共16個種子點來描述，這樣一個關鍵點就有16×8=128維的數據，形成128維的SIFT特征向量。圖4是一幅標記了SIFT特征向量的圖像，箭頭的起點#65380;長度#65380;方向表示了關鍵點的位置#65380;該點的梯度大小以及梯度的方向。

2圖像的檢索算法

128維的向量有力地刻畫了圖像的局部內容特征，并且具有很強的局部特征匹配能力。當兩幅圖像的SIFT特征向量生成后，筆者采用關鍵點特征向量的歐氏距離作為兩幅圖像中關鍵點的相似性判斷度量。取查詢圖中的某個關鍵點，找出其與數據庫圖像中歐氏距離最近的前兩個關鍵點。在這兩個關鍵點中，如果最近的距離除以次近的距離少于某個比例閾值(distance ratio)，則接收這一對匹配點。降低比例閾值，匹配的點的數量就會減少，匹配的精確度就會提高。適當的閾值可以減少采樣過程和圖像背景因素引起的錯誤匹配數量。

2.1特征向量的匹配

一幅圖像中可能有成千上萬的SIFT特征向量，對于這128維的向量來說，要找出數據庫圖像中與之距離最小的向量，其計算量可想而知是十分巨大的。為了解決高維空間搜索問題，本文采用的解決方法是:a)K－L變換降低向量的空間維數;b)利用ANN搜索(approximate nearest neighbor searching)算法實現圖像中最近鄰向量的快速搜索。

2.1.1K－L變換

K－L變換又稱為主成分分析(PCA)，通常應用在圖像的數據壓縮中。離散的K－L變換是針對向量的變換。設N維的矩陣X，其均值向量為MX，設K－L的變換矩陣A是由X的協方差矩陣的特征向量按特征值遞減順序排列組成的變換核矩陣。則典型的K－L變換寫為

Y=A(X-MX)(10)

由于能量集中在特征值λ比較大的系數中，因此可以舍棄對應特征值λ較小的Y系數而不會影響圖像的質量。取λ最大的前k個特征向量組成的變換核矩陣，記做Ak，則有

Y′=Ak(X-MX)(11)

這相當于原y的k維投影。在本文的實驗中，取k=20，這樣就使128維的向量降到了20維。

2.1.2ANN搜索算法

為了準確匹配特征向量，對于查詢圖中的每一個SIFT特征向量，需要比較它與查詢圖中所有特征向量的歐氏距離。明顯地，窮舉搜索可以實現精確定位，但實際應用中卻十分低效。在準確性與效率之間作個權衡，本文選擇ANN搜索算法。

ANN近似最近鄰搜索算法，由Arya等人[6]提出，為了解決高維空間的快速搜索問題。ANN搜索算法基本思想是:給定一個d維空間的點集P，算法將數據組織成kd樹結構，對于每一個查詢的點集Q，ANN算法能夠快速返回P與Q中各點距離最近的k個點對。

2.2圖像的相似距離

若關鍵點匹配的數量越多，圖像的相似程度就越高。在實驗中，使用匹配程度百分數來表示相似程度。筆者規定，匹配程度百分數=圖像匹配的關鍵點總數/查詢圖像中總的關鍵點的數量。

3實驗及其結果分析

首先，測試算法是否可以實現相似檢索。選用四幅內容相關的圖像。一幅全景圖像，給出三幅包含全景圖像中部分景色的圖像。計算全景圖像與其三幅片段圖像之間的相似距離。算法給出的結果如圖5所示，結果按相似程度從大到小排序，圖像結果下方顯示了匹配程度百分數。很明顯，算法給出的結果也符合人類的視覺感受。

從實驗1返回的結果可以看出，查詢圖與它的片段圖像之間有很好的相似距離。如果僅是利用顏色#65380;紋理#65380;形狀或者空間關系等圖像特征，將有可能得到完全不同的結果。從實驗返回的結果也可以看出，SIFT特征完全不同于顏色#65380;紋理#65380;空間關系等全局特征，是一種局部區域特征。

在實驗2中，本文選用一個特定的圖像數據庫進行檢索，該數據庫包含了近300幅的軍用飛機圖像。數據庫中圖像的分辨率均為1 024×1 536。檢索結果按照相似度從左到右#65380;從上到下排列，如圖6所示。

從實驗2的結果可以看出，該算法可以很好地描述查詢圖中目標的內容，并且確實具有尺度縮放#65380;平移#65380;旋轉#65380;亮度不變的優點，對于一定程度的仿射變換也保持較好的穩定性。

實驗3，筆者在一個包含4 000幅各類圖像的綜合圖像數據庫進行檢索，圖像大小均為1 024×1 536。庫中包含了各類常見的圖像，人物#65380;花草#65380;上水#65380;建筑#65380;軍事等。實驗返回前10幅相似程度最高的圖像，如圖7所示。最上方的圖像為查詢圖，也是結果返回的擁有最近相似距離的圖像。

實驗3的結果是令人興奮的，除了第8和第9幅是不相關的圖像外，其余8幅都是正確的關聯圖像。圖像庫中有上百張的飛禽圖像，但僅有15張鷹的圖像。這里檢出了8幅，事實上，剩余的7幅圖像也在最相似的前20幅圖像中檢出。結果中出現了兩幅不相關的圖像，其原因主要有以下幾點:a)該算法與圖像中目標形狀關系密切，如果目標形狀發生了較大的改變，則該算法就不容易將其檢出。后7幅的鷹的圖像實際上就是與查詢圖中目標姿態上存在較大區別。b)在計算兩個關鍵點的相似距離時，比例閾值的選擇對檢索結果的精確性有很大影響。比例閾值越小，匹配的數量就越少，但匹配的精確度高，實驗中，比例閾值選擇為0.6。c)在特征向量的降維過程中，對向量包含的信息量不可避免地造成損失，這也對圖像匹配過程中的穩健性造成影響。

4結束語

本文針對圖像檢索領域在圖像目標發生一定變化情況下不能很好實現檢索問題，提出一種新穎的多尺度圖像檢索算法，基于SIFT特征提取的圖像檢索算法。該算法將圖像內容轉換成128維特征向量的集合，通過計算向量之間的歐氏距離實現匹配。實驗結果表明該算法能較好地描述圖像內容，具有較好的尺度縮放#65380;平移#65380;旋轉#65380;亮度不變性，以及一定程度的仿射不變性。

事實上，SIFT的局部特性對于圖像中目標被部分阻隔的情況也有很好的檢索效果。如果能夠將該圖像特征與圖像的全局特征如顏色#65380;紋理#65380;空間關系等相結合，將能得到更好的檢索效果。從實驗2和3可以看出，該算法尤其適用于圖像中有特定目標的檢索，如果數據庫圖像中有部分片段與查詢圖中相同，或者說是相似，該算法就有很高的概率將其檢索出。算法也有不適用的地方，比如對草圖的查詢，其主要原因是草圖繪制過程中，對目標形狀的描述可能會有很大的誤差，并且草圖提供的圖像信息一般過于簡單，缺少必要的區域梯度信息。

SIFT特征向量結合ANN搜索算法使得整個檢索過程穩定而且高效，甚至在標準配置的個人電腦上均可達到實時的效果。

該檢索算法有著很大的應用前景，如對徽標的檢測，給出一個徽標圖像，就可以精確地查詢到數據庫中是否有相同的徽標;或者應用在指紋識別中，由于指紋圖案有著明顯的梯度信息，控制尺度空間參數以及采樣頻率，可以達到精確識別效果;也可以應用在武器庫圖像檢索中，如果給定一張包含了某一武器設備的查詢圖像，該算法可以以很高的概率在武器圖像庫中檢索該武器。

進一步的研究計劃是將圖像SIFT特征與全局特征相結合，以尋求更好的檢索效果和系統的穩定性。

參考文獻:

[1]章毓晉.基于內容的視覺信息檢索[M].北京:科學出版社，2003.

[2]TONG L. Scale－space theory: a basic tool for analyzing structures at different scales[J]. Journal of Applied Statistics， 1994，21(2):224－270.

[3]LOW D G. Object recognition from local scale－invariant features[C]//Proc of the 7th IEEE International Conference on Computer Vision. Kerkyra， Greece:[s.n.]， 1999:1150－1157.

[4]LOWE D G. Distinctive image features from sacle－invariant keypoints[J]. International Journal of Computer Vision， 2004，60(2):91－110.

[5]JORDAN M I. Properties of kernels and the Gaussian kernel[M]. Topics in Learning and Decision Making， 2004.

[6]ARYA S， MOUNT D M， NETANYAHU N S， et al. An optimal algorithm for approximate nearest neighbor searching[J]. Journal of the ACM， 1998，45(6):891－923.

[7]BEIS J， LOWE D G. Shape indexing using approximate nearest neighbour search in high－dimensional spaces[C]//Proc of Conference on Computer Vision and Pattern Recognition.1997:1000－1006.

[8]HARRIS C， STEPHENS M. A combined corner and edge detector[C]//Proc of the 4thAlvey Vision Conference， 1988:147－151.

[9]CROWLEY J L， PARKER A C. A representation for shape based on peaks and ridges in the difference of low－pass transform[J]. IEEE Trans on Pattern Analysis and Machine Intelligence， 1984，6(2):156－170.

[10]FRIEDMAN J H， BENTLEY J L， FINKEL R A. An algorithm for finding best matches in logarithmic expected time[J]. ACM Trans on Mathematical Software， 1977，3(3):209－226.

[11]章毓晉，圖像工程(上冊)——圖像處理[M].2版.北京:清華大學出版社，2006.

[12]歐珊瑚，王倩麗，朱哲瑜.Visual C++ .NET 數字圖像處理技術與應用[M].北京:清華大學出版社，2004.

[13]KANUNGO T， MOUNT D M， NETANYAHU N， et al. An efficient K－means clustering algorithm: analysis and implementation[J]. IEEE Trans on Pattern Analysis and Machine Intelligence， 2002，24(7):881－892.

[14]向友君，謝勝利.圖像檢索技術綜述[J].重慶郵電學院學報:自然科學版，2006，18(3):348－354.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”