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

摘要:提出一種多尺度圖像檢索算法，該算法基于SIFT特征提取，它將一幅圖像轉(zhuǎn)換成特征向量的集合，圖像間的相似距離是通過(guò)計(jì)算兩幅圖像特征向量間的歐氏距離來(lái)實(shí)現(xiàn)的。實(shí)驗(yàn)結(jié)果很好地說(shuō)明了該算法具有尺度#65380;平移#65380;旋轉(zhuǎn)不變性，一定的仿射#65380;光照不變性以及算法能很好地應(yīng)用在特定形狀特征目標(biāo)的檢索中。

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

中圖分類號(hào):TP391.3文獻(xiàn)標(biāo)志碼:A

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

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

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

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

本文提出了一種基于SIFT特征提取的圖像檢索算法，并結(jié)合K－L變換對(duì)該特征向量進(jìn)行主成分分析，降低向量空間維數(shù)，減少計(jì)算量。圖像間的相似特征向量的搜索由ANN搜索算法實(shí)現(xiàn)。文中描述了SIFT特征向量的提取過(guò)程，并給出三個(gè)不同的實(shí)驗(yàn)來(lái)檢測(cè)該算法的檢索性能。

1SIFT特征提取算法

1.1圖像的多尺度表示

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

1.2SIFT特征描述

David G.Lowe在文獻(xiàn)[3]中提出一種稱之為SIFT的圖像局部特征描述算子，并通過(guò)實(shí)驗(yàn)證實(shí)了該算子對(duì)圖像的尺度縮放#65380;平移#65380;旋轉(zhuǎn)變換保持不變，對(duì)圖像的亮度變化以及仿射變換也具有相當(dāng)?shù)姆€(wěn)健性(robust)。

SIFT算法的本質(zhì)就是從圖像中提取SIFT關(guān)鍵點(diǎn)(keypoint)的過(guò)程。SIFT特征提取的算法包含四步驟。

1.2.1尺度空間的極值檢測(cè)

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

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

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

為了產(chǎn)生下一階的Gaussian圖像，對(duì)上一階產(chǎn)生的最后一幅N×N的Gaussian圖像進(jìn)行1:2的亞采樣，生成N/2×N/2的圖像。在亞采樣圖像基礎(chǔ)上重復(fù)上述建立s+3層Gaussian圖像的過(guò)程。

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

1.2.2關(guān)鍵點(diǎn)的確定

極值檢測(cè)得到的所有候選關(guān)鍵點(diǎn)，還必須通過(guò)兩步檢驗(yàn)才能確定是關(guān)鍵點(diǎn):一是它必須與周圍的像素有明顯的差異，也就是說(shuō)低對(duì)比度的點(diǎn)不要;二是它不能是邊緣點(diǎn)。

對(duì)于每一個(gè)關(guān)鍵點(diǎn)，本文考慮它的鄰近的一個(gè)鄰域窗口內(nèi)點(diǎn)的梯度方向，最多人投票的方向就當(dāng)做該點(diǎn)的主方向。而每個(gè)鄰近的點(diǎn)對(duì)中央這個(gè)點(diǎn)的權(quán)重由高斯分布再乘上該點(diǎn)的梯度的大小來(lái)決定。

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

1.2.4SIFT特征向量描述子

為了確保旋轉(zhuǎn)不變性，首先將坐標(biāo)軸旋轉(zhuǎn)為關(guān)鍵點(diǎn)的方向。以一個(gè)關(guān)鍵點(diǎn)為中心，取8×8的窗口，將該窗口切成2×2的子窗口，統(tǒng)計(jì)每個(gè)子窗口中的方向直方圖，如圖3所示。

每一個(gè)子窗口的方向由其上4×4的小塊的方向用之前的方法來(lái)決定。圖中的每個(gè)關(guān)鍵點(diǎn)方向由2×2共4個(gè)種子點(diǎn)的方向決定，一個(gè)種子點(diǎn)有8個(gè)方向的信息，則每個(gè)關(guān)鍵點(diǎn)就有4×8=32維。

在實(shí)際計(jì)算過(guò)程中，為了增強(qiáng)匹配的穩(wěn)健性，通常采用4×4共16個(gè)種子點(diǎn)來(lái)描述，這樣一個(gè)關(guān)鍵點(diǎn)就有16×8=128維的數(shù)據(jù)，形成128維的SIFT特征向量。圖4是一幅標(biāo)記了SIFT特征向量的圖像，箭頭的起點(diǎn)#65380;長(zhǎng)度#65380;方向表示了關(guān)鍵點(diǎn)的位置#65380;該點(diǎn)的梯度大小以及梯度的方向。

2圖像的檢索算法

128維的向量有力地刻畫了圖像的局部?jī)?nèi)容特征，并且具有很強(qiáng)的局部特征匹配能力。當(dāng)兩幅圖像的SIFT特征向量生成后，筆者采用關(guān)鍵點(diǎn)特征向量的歐氏距離作為兩幅圖像中關(guān)鍵點(diǎn)的相似性判斷度量。取查詢圖中的某個(gè)關(guān)鍵點(diǎn)，找出其與數(shù)據(jù)庫(kù)圖像中歐氏距離最近的前兩個(gè)關(guān)鍵點(diǎn)。在這兩個(gè)關(guān)鍵點(diǎn)中，如果最近的距離除以次近的距離少于某個(gè)比例閾值(distance ratio)，則接收這一對(duì)匹配點(diǎn)。降低比例閾值，匹配的點(diǎn)的數(shù)量就會(huì)減少，匹配的精確度就會(huì)提高。適當(dāng)?shù)拈撝悼梢詼p少采樣過(guò)程和圖像背景因素引起的錯(cuò)誤匹配數(shù)量。

2.1特征向量的匹配

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

2.1.1K－L變換

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

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

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

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

這相當(dāng)于原y的k維投影。在本文的實(shí)驗(yàn)中，取k=20，這樣就使128維的向量降到了20維。

2.1.2ANN搜索算法

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

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

2.2圖像的相似距離

若關(guān)鍵點(diǎn)匹配的數(shù)量越多，圖像的相似程度就越高。在實(shí)驗(yàn)中，使用匹配程度百分?jǐn)?shù)來(lái)表示相似程度。筆者規(guī)定，匹配程度百分?jǐn)?shù)=圖像匹配的關(guān)鍵點(diǎn)總數(shù)/查詢圖像中總的關(guān)鍵點(diǎn)的數(shù)量。

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

首先，測(cè)試算法是否可以實(shí)現(xiàn)相似檢索。選用四幅內(nèi)容相關(guān)的圖像。一幅全景圖像，給出三幅包含全景圖像中部分景色的圖像。計(jì)算全景圖像與其三幅片段圖像之間的相似距離。算法給出的結(jié)果如圖5所示，結(jié)果按相似程度從大到小排序，圖像結(jié)果下方顯示了匹配程度百分?jǐn)?shù)。很明顯，算法給出的結(jié)果也符合人類的視覺(jué)感受。

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

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

從實(shí)驗(yàn)2的結(jié)果可以看出，該算法可以很好地描述查詢圖中目標(biāo)的內(nèi)容，并且確實(shí)具有尺度縮放#65380;平移#65380;旋轉(zhuǎn)#65380;亮度不變的優(yōu)點(diǎn)，對(duì)于一定程度的仿射變換也保持較好的穩(wěn)定性。

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

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

4結(jié)束語(yǔ)

本文針對(duì)圖像檢索領(lǐng)域在圖像目標(biāo)發(fā)生一定變化情況下不能很好實(shí)現(xiàn)檢索問(wèn)題，提出一種新穎的多尺度圖像檢索算法，基于SIFT特征提取的圖像檢索算法。該算法將圖像內(nèi)容轉(zhuǎn)換成128維特征向量的集合，通過(guò)計(jì)算向量之間的歐氏距離實(shí)現(xiàn)匹配。實(shí)驗(yàn)結(jié)果表明該算法能較好地描述圖像內(nèi)容，具有較好的尺度縮放#65380;平移#65380;旋轉(zhuǎn)#65380;亮度不變性，以及一定程度的仿射不變性。

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

SIFT特征向量結(jié)合ANN搜索算法使得整個(gè)檢索過(guò)程穩(wěn)定而且高效，甚至在標(biāo)準(zhǔn)配置的個(gè)人電腦上均可達(dá)到實(shí)時(shí)的效果。

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

進(jìn)一步的研究計(jì)劃是將圖像SIFT特征與全局特征相結(jié)合，以尋求更好的檢索效果和系統(tǒng)的穩(wěn)定性。

參考文獻(xiàn):

[1]章毓晉.基于內(nèi)容的視覺(jué)信息檢索[M].北京:科學(xué)出版社，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]章毓晉，圖像工程(上冊(cè))——圖像處理[M].2版.北京:清華大學(xué)出版社，2006.

[12]歐珊瑚，王倩麗，朱哲瑜.Visual C++ .NET 數(shù)字圖像處理技術(shù)與應(yīng)用[M].北京:清華大學(xué)出版社，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]向友君，謝勝利.圖像檢索技術(shù)綜述[J].重慶郵電學(xué)院學(xué)報(bào):自然科學(xué)版，2006，18(3):348－354.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”