樸 林

(遼寧民族師范高等?？茖W(xué)校,遼寧 沈陽 110032)

0 引 言

對于影像局部特征的檢測，傳統(tǒng)的尺度不變特征轉(zhuǎn)換(scale-invariant feature transform，SIFT)向量檢索法能夠通過提取圖像特征并將其轉(zhuǎn)化為多組128維向量的方式，在空間尺度中進(jìn)行極值點的搜索，并確定其尺度、位置、旋轉(zhuǎn)不變量的相關(guān)數(shù)據(jù)。該方法在亮度變化、尺度縮放、旋轉(zhuǎn)角度等方面保持固定，可以在一定程度上控制噪聲干擾、仿聲變換和視角變化，魯棒性很強(qiáng)。雖然是圖像檢索中最為常用的方法，但在大數(shù)據(jù)背景下其固有的缺陷也逐漸顯現(xiàn)出來，包括需要基于訓(xùn)練集以人工的低效方式確定vocabulary tree的高度M；進(jìn)行建樹和檢索時，每個128維向量都必須與某個中心點的多個分支點完成距離的檢測，耗時過長、效率過低；向量到達(dá)葉子節(jié)點后所獲取的結(jié)果不完全與原向量相符，但仍被提取，極大地影響了檢索精度。為此，本文提出了一種基于尺寸不變特征轉(zhuǎn)換向量的圖像檢索精度優(yōu)化方法，構(gòu)建了新的樹節(jié)點聚類法來完成建樹，從測試集中提取出SIFT特征向量來創(chuàng)建樹模型下的倒排文件，在檢索過程中基于歐氏距離信息對SIFT特征向量進(jìn)行統(tǒng)一處理，從而有效提高了圖像特征檢索的效率和精度。

1 聚類方法

對于影像特征檢索常用的SIFT特征向量法，其聚類方法無法將多個近似特征向量聚合到同一個葉子節(jié)點上且存在分配錯誤的可能，即在檢索和倒排文件的過程中存在所謂的“維數(shù)災(zāi)難”，所以使算法的精度受到很大的影響[3-4]。為了盡可能消除這些分配誤差，本文所提出的方法將聚類與分類兩個過程結(jié)合在一起，基于類半徑以及聚類中心R與目標(biāo)向量P之間的距離實現(xiàn)最終的聚類，在設(shè)定闕值后可以獲取聚類數(shù)量，具體方式為

(1)

式中，Q代表從倒排文件中提取的任意向量。

匹配任意2個向量需要確定它們之間的距離，但創(chuàng)建倒排文件時并未將圖片集中的SIFT特征向量保存于其中，所以不能直接搜索與目標(biāo)向量相似的向量，需要通過式(1)保證近似向量同處某一范圍之內(nèi)，遍歷全部被檢索向量之后，包含大量相同ID號的即可判定為正確圖片，由此可以獲取類半徑及分支節(jié)點的數(shù)量。

2 樹模型建立

2.1 建樹

建數(shù)是通過分類與系統(tǒng)聚類的方法將訓(xùn)練集中的全部特征向量構(gòu)建成一組復(fù)雜的多維向量坐標(biāo)的過程。首先，通過式(2)計算所有特征向量的平均向量：

(2)

然后以該向量坐標(biāo)為聚合中心節(jié)點(具有標(biāo)示符性質(zhì)的根節(jié)點)求出訓(xùn)練集中的所有向量與它的間距：

(3)

對所有計算結(jié)果進(jìn)行排序，設(shè)定合理的闕值，通過式(1)對這些向量進(jìn)行分類。假設(shè)聚類數(shù)量為K，在中心點中保存與其相連的K個分支節(jié)點的數(shù)量，同時保存單個類與中心節(jié)點的最大距離，以此來大幅提高圖像檢索的效率。最后逐一檢查單個分支節(jié)點與中心節(jié)點的間距以及與該分支節(jié)點對應(yīng)的類的半徑之和，如果小于某個設(shè)定的闕值，則該分支節(jié)點不再繼續(xù)對這些類進(jìn)行聚合，并且直接轉(zhuǎn)換為葉子節(jié)點；如果大于闕值則繼續(xù)迭代聚類，直到獲取想要的結(jié)果。

通過這一方法，聚類過程不再受到vocabulary tree層數(shù)M與分支節(jié)點數(shù)量K的限制，所有訓(xùn)練集中的特征向量直接轉(zhuǎn)化為任意高度和分支數(shù)量的樹，由此在很大程度上消除了維數(shù)過多所引起的檢索誤差，有效避免了SIFT向量的“維數(shù)災(zāi)難”。

2.2 創(chuàng)建倒排文件

構(gòu)建分層多維向量坐標(biāo)后，將測試集中的所有特征向量作為葉子節(jié)點，即可完成倒排文件的創(chuàng)建。由樹節(jié)點所構(gòu)建的向量坐標(biāo)具有一定的指向性，當(dāng)前節(jié)點的一個SIFT向量運(yùn)動到某一個分支節(jié)點后，進(jìn)行一次歐式距離的計算即可選擇下一個目標(biāo)分支節(jié)點，最終停留在葉子節(jié)點。由此每個向量都被單獨分配了一條按照節(jié)點指向從中心節(jié)點到達(dá)葉子節(jié)點的路徑，這條路徑的距離是最短的。到達(dá)葉子節(jié)點后，向量計算其與葉子節(jié)點中心向量之間的間距，如果大于設(shè)定的闕值，則直接舍棄該節(jié)點，不再將其列入移動目標(biāo)分支節(jié)點的范圍。此外，闕值需要結(jié)合訓(xùn)練集的具體情況來確定。

在使用該方法對海量圖片模型進(jìn)行檢索時，并不保存到達(dá)葉子節(jié)點的向量，而是保存其ID編號，以便節(jié)省存儲空間，如此一來葉子節(jié)點中便存在一個維數(shù)與測試集包含的圖片數(shù)量相等的數(shù)組，圖片向量終點即為葉子節(jié)點的向量數(shù)量，通過其中一個維度來表示，具體形式如圖1所示。

圖1中的Ii，j為包含在第i個葉子節(jié)點中的第j張圖片的特征向量的數(shù)量。倒排文件的整體排列形式如圖2所示。

圖1 倒排文件的具體形式 圖2 通過建樹所得到的倒排文件

為了得到更高的檢索精度，本文在進(jìn)行圖像檢索的過程中借鑒了文本檢索中的TF-IDF(term frequency inverse document frequency)檢索機(jī)制。由于圖片到SIFT特征向量的轉(zhuǎn)換，使圖像檢索的過程變換為在規(guī)模龐大的向量集中搜索與目標(biāo)向量近似的那些向量，即利用向量來檢索向量，這本來屬于文本檢索的范疇，通過這種方式能夠?qū)崿F(xiàn)檢索結(jié)果明顯得到改善。引入TF-IDF檢索機(jī)制能夠賦予葉子節(jié)點一個權(quán)值，如果某個葉子節(jié)點包含對應(yīng)圖片庫中全部圖片的向量，那么它就不適合參與圖片的區(qū)分，因為在這種情況下每個節(jié)點都能夠與這個葉子節(jié)點產(chǎn)生聯(lián)系，所以檢索過程中無法獲取足夠的圖像匹配信息。反之，如果某個葉子節(jié)點僅包含一個或少數(shù)幾個近似的圖片向量，則當(dāng)向量取最短路徑達(dá)到該葉子節(jié)點時，就代表該向量所對應(yīng)的圖片與其所到達(dá)葉子節(jié)點內(nèi)倒排文件所對應(yīng)的圖片符合匹配的條件，也就是說這個葉子節(jié)點能夠在檢索過程中用以表示特定的一張或幾張近似的圖片。同時，取最短路徑到達(dá)節(jié)點的向量僅存在于近似圖片之中，所以可以為該葉子節(jié)點賦予一個較大的權(quán)值，如此就能使該葉子節(jié)點的作用充分發(fā)揮出來。

圖像檢索是一個特殊的檢索過程，對倒排文件的檢索也需要滿足一些特殊條件，僅通過TF-IDF機(jī)制是無法實現(xiàn)檢索的，其對文本進(jìn)行檢索的方式為

w=T×I

(4)

式中，w代表葉子節(jié)點被賦予的權(quán)值，T代表特定單詞在某篇文章中的詞頻TF，I代表特定單詞在所有文章中出現(xiàn)的情況IDF。本文通過式(5)為葉子節(jié)點賦予權(quán)值：

w=I

(5)

理論上，葉子節(jié)點中所包含向量能夠?qū)?yīng)的圖片id越多，其被賦予的權(quán)值越小，假設(shè)：

(6)

式中，N代表測試集中所包含的圖片總數(shù)，m代表倒排文件向量中所包含的數(shù)組的維數(shù)，Ii，j代表包含在第i個葉子節(jié)點中的第j張圖片的SIFT特征向量的數(shù)量，函數(shù)f(Ii，j)的取值方式為

(7)

這是一個在倒排文件數(shù)組中搜索通過該葉子節(jié)點可能發(fā)現(xiàn)的圖片的過程。利用式(5)、(6)、(7)能夠獲取葉子節(jié)點的權(quán)值，由此通過該權(quán)值與向量中的數(shù)組即可構(gòu)建倒排文件。

3 圖像檢索

將特定的圖片轉(zhuǎn)換為SIFT特征向量后，就可以在樹中搜索相似度最高的向量來判斷圖片之間的匹配程度。取該圖片中所有特征向量與中心節(jié)點的距離，節(jié)點中保存有其與所有分支節(jié)點的距離信息，所以可以在最短路徑中找到下一個節(jié)點，即樹中的某個分支節(jié)點，這是本文提出的提高搜索效率的基本方法原理。樹的高度為M，平均分支數(shù)量為K，計算2個向量間歐式距離所需的時間為t，傳統(tǒng)算法的檢索時間為

T=M×(K-1)×t

(8)

而本算法消耗時間為T=Mt，這就意味著，通過本文提出的方法進(jìn)行圖像檢索所消耗的時長僅為傳統(tǒng)方法的1/(K-1)，而利用節(jié)省的時間可以在其它方面進(jìn)一步提高檢索的精度。

在每個向量均已獲取到達(dá)葉子節(jié)點最短路徑的條件下，從倒排文件中提取信息用以構(gòu)造檢索圖片向量和測試集中圖片的向量，檢索圖片向量的具體形式為

S=(w1×n1，w2×n2，…，wn×nn)

(9)

由式(9)可見圖片向量的終點為葉子節(jié)點的數(shù)量與其各自權(quán)值的乘積。測試圖片向量的具體形式為

Dj=(w1×I1，j，w2×I2，j，…，wn×In，j)

(10)

傳統(tǒng)算法基于向量的單一化來計算圖片的匹配度，即

(11)

根據(jù)實際的使用經(jīng)驗，在該算法下，由于不同的圖像包含不同數(shù)目的信息量，包含信息量較多的圖片會經(jīng)歷多次檢索，這在很大程度上影響了算法的精度，所以本文對算法進(jìn)行了優(yōu)化，即

(12)

式中，N代表檢索圖片中包含的特征向量的總數(shù)。由此可按照匹配度對獲取的圖片進(jìn)行排序。

4 實驗與結(jié)果分析

從Ukbench數(shù)據(jù)集中選取2 500組不同的圖像，每4張拍攝相同事物的圖片為一個圖像組，但每張圖片的角度、光線、分辨率和背景噪音各不相同，因此互為相似圖片。用本文提出的方法對與目標(biāo)圖片相似的圖片進(jìn)行檢索。圖片的檢索精度由式(13)進(jìn)行計算：

(13)

式(13)表示檢索結(jié)果中排名靠前的10張圖片中，存在ni張相似圖片。從圖片庫中任意選取不同數(shù)量的圖片組建測試集，分別用L1-norm、L2-norm和本文方法在統(tǒng)一化的unit-norm標(biāo)準(zhǔn)下進(jìn)行測試，具體結(jié)果如圖3所示。

圖3 不同標(biāo)準(zhǔn)下的測試結(jié)果

圖3中的橫軸為每次測試選取的圖片數(shù)量，縱軸為檢索精度，顯而易見，在本文所提出算法的統(tǒng)一化標(biāo)準(zhǔn)下能夠獲得更高的圖片檢索精度。

同時，在unit-norm標(biāo)準(zhǔn)下，通過舍棄與葉子節(jié)點間距最大的SIFT向量的方法進(jìn)行檢索，得到的檢索精度如圖4所示。

圖4 舍棄最大間距SIFT向量的檢索精度

為了驗證本文方法的優(yōu)越性，選用文獻(xiàn)[6]的方法進(jìn)行檢索精度比對，比對結(jié)果如下：

圖5 檢索精度對比

對以上3項測試所進(jìn)行分析，可以得到以下結(jié)果：

1)在由圖片轉(zhuǎn)換為SIFT向量的過程中會產(chǎn)生一定的誤差，在圖片數(shù)量足夠多的情況下這種誤差不易被發(fā)現(xiàn)，由于SIFT向量的規(guī)模過于龐大，可能導(dǎo)致錯誤的分配結(jié)果，使向量誤入非設(shè)定路徑上的分支節(jié)點，由這種情況所引起的誤差本文提出的方法已通過歐式距離的計算最大限度地進(jìn)行控制；

2)圖片生成地SIFT向量數(shù)量會對檢索精度產(chǎn)生一定的影響，雖然SIFT向量過少也可能導(dǎo)致誤差的產(chǎn)生，但統(tǒng)一化方法有效消除了海量SIFT向量引起的誤差，兩者相比本文提出方法的誤差要小很多，所以該方法對最終檢索結(jié)果的誤差控制是相對有效的；

3)相對于常用的文獻(xiàn)基于圖像色彩特征的檢索方法而言，本文方法的檢索精度更高。

5 結(jié) 論

為了解決海量圖片數(shù)據(jù)檢索過程中存在的精度較低的問題，本文提出了一種基于尺寸不變特征轉(zhuǎn)換向量的圖像檢索精度優(yōu)化方法，在傳統(tǒng)SIFT特征向量檢索方法的基礎(chǔ)上，通過聚、分類的結(jié)合設(shè)計了更為合理的聚類方式，利用計算得到的歐式距離對SIFT特征向量進(jìn)行統(tǒng)一化的處理，最終采取倒排文件的方式有效控制了圖片檢索的誤差。通過以上圖像檢索的優(yōu)化方式，形成以下結(jié)論：

1)適當(dāng)解除對vocabulary tree的高度M和分支數(shù)量K的限制，同時依據(jù)訓(xùn)練集的具體情況自行決定分類的數(shù)量，能夠明顯提高圖像檢索的效率與精度；

2)可以根據(jù)目標(biāo)向量與葉子節(jié)點中心向量的間距有選擇性地剔除一部分已經(jīng)產(chǎn)生偏差的SIFT特征向量；

3)可以采用新的匹配機(jī)制對向量所對應(yīng)的圖片與葉子節(jié)點所對應(yīng)的圖片進(jìn)行相似度匹配，以此來大幅降低大數(shù)據(jù)條件下的SIFT誤差。

測試結(jié)果表明，本文所提出的方法具有較高的檢索效率和精度，適用于圖片局部特征的檢索。但是，由于研究時間較短、理論研究不夠透徹等原因，本次研究還存在一些不足之處，例如尚未完全解決vocabulary tree分支數(shù)量會產(chǎn)生干擾的問題，仍需以人工的方式進(jìn)行確定。在今后的研究中，將繼續(xù)探索自動確定分支數(shù)量的合理方法，以進(jìn)一步提高圖像檢索的精度。