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

關(guān)鍵詞:基于內(nèi)容的圖像檢索;分形維數(shù)[1];索引;聚類

中圖分類號(hào):TP391.4 文獻(xiàn)標(biāo)識(shí)碼:A

1 引 言

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

2 圖像的分形維數(shù)作為紋理特征

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

2.1 圖像的紋理特征

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

2.1.1 求取經(jīng)過四種變換后的圖像分?jǐn)?shù)維

1) 圖像的變換^[8]

圖像變換是圖像分形維數(shù)估計(jì)中常用的方法:

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

2) 圖像的FD估計(jì)

用差分盒計(jì)數(shù)法^[10]和基于分形布朗運(yùn)動(dòng)自相似模型法^[10]分別對(duì)上述產(chǎn)生的5幅圖像進(jìn)行分形維數(shù)FD的估計(jì)，得到10個(gè)紋理特征向量#65377;這里使用的是兩種FD結(jié)合的方法，原因是這兩種方法對(duì)粗糙度不同的紋理的敏感性不同，如表1所示，編號(hào)50的圖像，用方法一測試比方法二的值要大，因?yàn)榉椒ㄒ荒懿煊X到很細(xì)微的紋理，即具較強(qiáng)的紋理敏感性，而方法二的敏感性卻較弱#65377;具體分析可參考^[10]#65377;

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

分形維數(shù)布朗運(yùn)動(dòng)自相似模型差分盒子維法

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

當(dāng)分析數(shù)字圖像S時(shí)，最常用的計(jì)算分?jǐn)?shù)維的方法是盒子維方法，這種方法的一個(gè)缺點(diǎn)是:沒有考慮圖像象素點(diǎn)在不同盒子中的分布特征，為了克服上述缺點(diǎn)，在分析數(shù)字圖像時(shí)，不僅要計(jì)算覆蓋圖像所需的盒子數(shù)，還要統(tǒng)計(jì)不同盒子所含的象素點(diǎn)數(shù)#65377;為此，針對(duì)每個(gè)邊長為ε的盒子分配一個(gè)量

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

這里的N是圖像S包含的總象素?cái)?shù)，Ni是第i個(gè)盒子所包含的象素?cái)?shù)，由此可得集合M:

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

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

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

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

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

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

則τ(q)稱為質(zhì)量指數(shù)#65377;

根據(jù)μ的q階矩可以定義廣義Renyi維數(shù)

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

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

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

2.2 圖像相似度計(jì)算

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

3 圖像紋理的聚類索引結(jié)構(gòu)構(gòu)造

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

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

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

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

E:判斷循環(huán)停止的閾值;

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

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

2) 算法處理過程

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

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

step2:對(duì)于圖像庫中的每幅圖像分別計(jì)算其與每個(gè)重心的距離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:對(duì)于每個(gè)聚類，計(jì)算距離和Dsum(I);

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

step4:計(jì)算所有圖像的距離總和DD;

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

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

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

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

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

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

step8:判斷D′-D

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

step9:對(duì)于每個(gè)聚類重心及類中圖像建立索引鏈表，結(jié)束#65377;

3) 關(guān)于算法的幾點(diǎn)補(bǔ)充說明

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

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

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

4 實(shí)驗(yàn)結(jié)果和測試

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

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

圖像聚類數(shù)檢索算法檢索到的圖像相關(guān)的圖像檢索時(shí)間查準(zhǔn)率 順序檢索5782897847ms47.1% 10索引檢索 151692770ms69.4%順序檢索 5782897847ms47.1% 16索引檢索108543001ms72.3%

5 結(jié)束語

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

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