基于兩種紋理特征聚類的圖像檢索

摘 要:設計和實現兩種不同的分形維數作為紋理特征進行聚類的方法#65377;提取幾百幅不同圖像的兩種紋理特征，對特征庫按聚類算法建立索引結構，形成圖像的分類庫，通過兩種不同紋理特征的檢索與無聚類的特征檢索相比，實驗結果表明聚類方法大大縮短了檢索時間#65377;結論:作為海量圖像的檢索，有效的圖像特征結合聚類是一個有力工具，在研究信息分類與識別等方面具有應用潛力#65377;

關鍵詞:基于內容的圖像檢索;分形維數[1];索引;聚類

中圖分類號:TP391.4 文獻標識碼:A

1 引 言

多媒體信息的訪問包括數據圖像#65380;視頻#65380;聲音#65380;圖形和文本數據#65377;所以目前對基于內容的圖像檢索(CBIR)的研究已非常廣泛#65377;然而圖像作為存儲信息的一種直觀#65380;簡單的方法，成為數據庫的重要組成部分，但其容量大，圖像檢索的效率很低#65377;如何在圖像數據庫中建立有效的索引結構是提高檢索效率的關鍵#65377;圖像的檢索常用的方法是基于單一特征的聚類#65377;本文結合了兩種對強弱紋理敏感性不同的紋理特征作為索引結構的關鍵值構成聚類索引，提高了檢索的效率#65377;

2 圖像的分形維數作為紋理特征

由于圖像的索引結構是建立在基于圖像紋理相似度的基礎上，因此必須從圖像中選取有效的紋理特征及圖像相似度算法來構造索引結構#65377;

2.1 圖像的紋理特征

紋理通常定義為圖像的某種局部性質，是對圖像空間信息的分布進行一定程度的定量描述，本文中紋理特征的提取是以分形維數為基礎的#65377;但自然界很多視覺上差別大的紋理，其分形維數卻是近似相同，因此，單一分形維數不能提供足夠信息來描述和識別紋理#65377;為了克服分形數維的缺陷，本文采用了兩種分形維數作為紋理特征，提取算法分別如下:

2.1.1 求取經過四種變換后的圖像分數維

1) 圖像的變換^[8]

圖像變換是圖像分形維數估計中常用的方法:

這里gmin，gmax和av分別表示圖像I的灰度最小值#65380;最大值和平均值#65377;I2和I3分別稱為I的高灰度值和低灰度值圖像#65377;I4和I5分別為圖像的垂直和水平平滑定義#65377;用以上方法產生的5幅圖像將作為特征提取的圖像#65377;

2) 圖像的FD估計

用差分盒計數法^[10]和基于分形布朗運動自相似模型法^[10]分別對上述產生的5幅圖像進行分形維數FD的估計，得到10個紋理特征向量#65377;這里使用的是兩種FD結合的方法，原因是這兩種方法對粗糙度不同的紋理的敏感性不同，如表1所示，編號50的圖像，用方法一測試比方法二的值要大，因為方法一能察覺到很細微的紋理，即具較強的紋理敏感性，而方法二的敏感性卻較弱#65377;具體分析可參考^[10]#65377;

表1 兩種不同分形維對紋理的敏感程度測試

分形維數布朗運動自相似模型差分盒子維法

2.1.2 基于多重維數的分形維(廣義維)^[7]

當分析數字圖像S時，最常用的計算分數維的方法是盒子維方法，這種方法的一個缺點是:沒有考慮圖像象素點在不同盒子中的分布特征，為了克服上述缺點，在分析數字圖像時，不僅要計算覆蓋圖像所需的盒子數，還要統計不同盒子所含的象素點數#65377;為此，針對每個邊長為ε的盒子分配一個量

計算技術與自動化2007年6月第26卷第2期趙海英等:基于兩種紋理特征聚類的圖像檢索μ=NiN(5)

這里的N是圖像S包含的總象素數，Ni是第i個盒子所包含的象素數，由此可得集合M:

這里的B是覆蓋圖像S所需的盒子數，且

D=-limε→0logBlogε，就是圖像S的盒子維

為了分析圖像S的不同分形子集，定義μ的q階矩

N(q，ε)=∑N(ε)i=1μqi(7)

其中，N(ε)是覆蓋S所需的盒子數，引入廣義γ維測度

有限正值λ=τ(q)(10)

則τ(q)稱為質量指數#65377;

根據μ的q階矩可以定義廣義Renyi維數

D(q)與τ(q)滿足下述關系

-τ′(1)q=1且τ(q)可微(13)

廣義維數譜q-D(q)的計算理論上可采用公式(11)，但計算太復雜#65377;文獻[8]提出了一種簡單的近似算法可求出廣義分數維#65377;通過大量的實驗，本文是改變q的值5次，得到5個分數維D的值#65377;

2.2 圖像相似度計算

由于本文作者曾對相似度算法的動態選取作過比較(具體分析參^[11])，所以選取了L2距離法作為相似度測量#65377;

3 圖像紋理的聚類索引結構構造

在對圖像進行基于內容檢索時，需要對圖像庫中的圖像進行匹配，本文選用了Cluster算法(考慮了特征的維數)對圖像庫中的圖像進行了事先處理，建立聚類索引表(Cluster-index table)來縮小查詢范圍，加快檢索效率#65377;

通過聚類加速檢索的過程是:首先將圖像庫中的圖像聚成R類(必須經過先驗知識或大量的實驗算法來測試R值)#65377;每個圖像聚類都有一個代表樣本，類中平均有N/R幅圖像，但具體每個類中圖像的個數和圖像的特征分布有關，有的類中圖像會多一些#65377;進行查詢時，將查詢圖像分別與圖像庫中的聚類代表樣本(稱之為聚類重心)進行匹配，找到與查詢圖像最相似的聚類重心#65377;則在該聚類中，用查詢圖像與類中每一幅圖像進行匹配;根據用戶要求的相似度，將結果返回，并按相似度高低進行排序#65377;設計的算法如下:

1) 定義以下參數:R:聚類個數，這個值非常重要，它關系到后期的查詢的準確率，為此進行了大量的實驗來測算R的大小#65377;本文中R值確定為10和16#65377;詳見^[12]

z1，z2，…，zR:分別表示R個聚類的重心;m1，m2，…，mR:分別表示每個類中圖像的個數;N:圖像庫中圖像的總數;則有:N=m1+m2+…+mR;

E:判斷循環停止的閾值;

x(i):i=1，2，…，15;表示圖像的紋理特征向量;(10個是由圖像變換得到，5個廣義分數維)

zj(i):i=1，2，…，15，j=1，2，…，R:表示重心的紋理特征向量#65377;

2) 算法處理過程

step1:給定初始條件#65377;由于聚類重心的關鍵性，它的選取方法直接決定了聚類的好壞，為此瀏覽圖像庫，進行粗估計與先驗學習(計算與視覺相結合，參見^[12])#65377;

z1，z2，…，zR:相互相異的聚類重心初始值;

step2:對于圖像庫中的每幅圖像分別計算其與每個重心的距離distance;

Sim(I)=Im ɑgeMɑtch(floɑtX，floɑtZI)其中I=1，2，…，R

Sim為圖像的紋理特征與重心的紋理特征的相似度#65377;

distnɑce(i)=1-Sim(i)，If distance(i)最小，則將圖像聚類i類#65377;

step3:對于每個聚類，計算距離和Dsum(I);

Dsum(I)為該聚類中所有圖像與重心的距離(distance)總和;

step4:計算所有圖像的距離總和DD;

DD=Dsum(1)+Dsum(2)+…+Dsum(R);

step5:根據矢量空間重心計算公式，計算該聚類幾何重心:

Z′(I)=1mi∑mij=1x(n)j; 其中x=(x1，x2，x3，…，x15)T為圖像的紋理特征

step6:計算類中每幅圖像與幾何重心的距離Distɑnce′(J)

Distɑnce′(j)=1-Imɑge Mɑtch(x，Z′j)，J=1，2，mi

step7:重新計算每個聚類中圖像的距離總和D′(I)和圖像數據庫中所有圖像的距離總和D′，計算方法同上(步驟3和4);

step8:判斷D′-D

如果為真，則將幾何重心作為新的聚類重心，返回到step2;否則，到step9;

step9:對于每個聚類重心及類中圖像建立索引鏈表，結束#65377;

3) 關于算法的幾點補充說明

(1)聚類個數的選擇#65377;由于圖像庫容量和從圖像中抽取的內容特征的不同，因此選取聚類的個數不同#65377;在圖像的數目很大(在幾萬幅以上)時，我們根據mɑx(N，d)來決定聚類個數(d為特征的維數)^[4]#65377;如果圖像的數目不是很大，那么據圖像的數目N>聚類個數>，然后由實驗來決定#65377;

(2)由于CBIR采用的是相似匹配，如果在構造的聚類索引結構后，返回的圖像還是不能完全滿足檢索的要求，則可以擴展到相鄰的類再進行相似匹配^[4]，也可加入了交互式的檢索機制#65377;

(3)在算法中，聚類的個數和圖像相似距離的選擇直接影響到聚類的結構#65377;初始聚類重心的選擇將會影響到構造聚類索引的準確性和速度#65377;一般來說，要根據數據庫圖像的大概紋理分布來選取#65377;如果圖像的紋理分布很廣，則可以按照強#65380;中#65380;弱三種紋理的分數維在紋理特征空間中均勻選取#65377;

4 實驗結果和測試

為了測試索引結構對CBIR的圖像數據庫的效率，我們建立了測試模型#65377;在測試模型中，選取了700幅花卉#65380;房屋#65380;海面#65380;飛機等圖像，查詢圖像為一幅\"湖面圖像\"(編號為N0.400)，從圖像中抽取紋理特征，在相同的測試條件下，進行了基于顏色#65380;紋理和形狀三種特征綜合的檢索^[2]，返回查詢結果的時間和準確率(查準率=檢索出的圖像中相關圖像的數目/檢索出的圖像數目)，如表2所示#65377;

通過測試可以看出，在對圖像的紋理特征建立了索引結構后，檢索效率有了很大提高，查到的不相關圖像大大減少，從而使檢索時間縮短了近 28.7 % #65377;這正是由于采用了聚類算法，聚集相關的圖像根據其特征值在多維空間的分布#65377;索引結構的建立，使檢索時訪問的不相關節點大大減少，也減少了訪問這些節點的開銷#65377;表2 在不同情況的聚類結果

圖像聚類數檢索算法檢索到的圖像相關的圖像檢索時間查準率 順序檢索5782897847ms47.1% 10索引檢索 151692770ms69.4%順序檢索 5782897847ms47.1% 16索引檢索108543001ms72.3%

5 結束語

無論是對于圖像聚類/分類，還是針對圖像信息檢索，特征項的選取都是一個基礎性的工作#65377;特征選取的優劣將直接決定最終結果的好壞#65377;從實驗結果中可以看出，相對于兩種紋理結合的特征選項，對于圖像的聚類是一種較好的方法#65377;若能使用迭代加權過程和交互式反饋技術來進一步挖掘出的圖像集蘊涵的內容，就能夠更加有效地反映出圖像集的本質內容，進而有助于圖像的聚類/分類和檢索#65377;

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