一種基于語義子空間譜聚類的自動圖像標(biāo)注的方法

1、一種基于語義空間譜聚類的自動圖像標(biāo)注方法郭玉堂1,2，韓昌剛2 1合肥師范學(xué)院計算機(jī)科學(xué)與技術(shù)系,合肥 2306012安徽大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,合肥 230039摘 要: 由于“語義鴻溝”的存在，低層特征相同或相似的圖像，其語義有可能完全不同。如何挖掘圖像的高層語義與低層特征之間的內(nèi)在聯(lián)系是當(dāng)前圖像標(biāo)注領(lǐng)域研究的難點(diǎn)之一。在詳細(xì)分析現(xiàn)有的圖像標(biāo)注方法優(yōu)缺點(diǎn)的基礎(chǔ)上，提出了一種基于語義一致性的譜聚類圖像標(biāo)注方法。該方法首先在語義空間內(nèi)，對訓(xùn)練圖像先按語義聚類，使得語義相同或相近的圖像處于同一類中，再對每個語義類按區(qū)域特征聚類，把相似區(qū)域聚類到同一個塊中，然后運(yùn)用多伯努利模型求出語義類中每個塊

2、與語義間的聯(lián)合概率分布，利用該聯(lián)合概率分布模型為未標(biāo)注圖像進(jìn)行標(biāo)注。實驗結(jié)果表明所提出的方法明顯提高了標(biāo)注準(zhǔn)確度。能有效地建立圖像的低層特征與語義特征間的一致性。關(guān)鍵詞: 圖像標(biāo)注 K-調(diào)和均值 圖譜聚類 語義鴻溝Automatic Image Annotation Using Semantic Subspace graph spectral clustering AlgorithnGuo Yu-tang1 ， Han Chang-gang21Department of Computer Science and Technology in Hefei Normal College, Hefei

3、 230061,China2School of Computer Science and Technology in Anhui University, Hefei 230039,ChinaaieytAbstract: Due to existing the semantic gap, images with the same or similar low level features are possibly totally different on semantic level. How to find the underlying relationship between the hig

4、h-level semantic and low level features is one of the difficult problems for image annotation. In this paper, a new image annotation method based on graph spectral clustering with the consistency of semantics is proposed with detailed analysis on the advantages and disadvantages of the existed image

5、 annotation methods. This method firstly cluster image into several semantic classes by semantic similarity measurement in the semantic subspace. Within each semantic class, images are re-clustered with visual features of.region Then, the joint probability distribution of blobs and words was modeled

6、 by using Multiple-Bernoulli Relevance Model. We can annotate a unannotated image by using the joint distribution. Experimental results show the the effectiveness of the proposed approach in terms of quality of the image annotation, the consistency of high-level semantics and low level features is e

7、fficiently achieved.Key Words: image annotation, K-Harmonic Means, graph spectral clustering, semantic gap基 金項 目：安徽省自然科學(xué)基金項目（11040606M134）、安徽省高校自然科學(xué)基金重點(diǎn)項目（KJ2009A150）1 引言自動圖像標(biāo)注指的是指借助計算機(jī)視覺、機(jī)器學(xué)習(xí)與模式識別等多學(xué)科技術(shù)，從一組已標(biāo)注好的圖像集合中學(xué)習(xí)圖像特征與文本標(biāo)注兩種模態(tài)間的相關(guān)性，為未標(biāo)注的圖像推理出最為可能的標(biāo)注或關(guān)鍵字。一旦圖像被成功標(biāo)注，圖像檢索問題就可以轉(zhuǎn)化就可以用這樣一組關(guān)鍵詞來進(jìn)行，當(dāng)前技術(shù)

8、已相當(dāng)成熟的文本檢索方法就可以用于圖像檢索1中。因此，圖像語義標(biāo)注得到了國內(nèi)外相關(guān)領(lǐng)域的研究人員的廣泛重視。目前，國內(nèi)外已經(jīng)有許多學(xué)者提出了各種不同的方法，并取得了相當(dāng)多的成果。如共現(xiàn)模型2、翻譯模型 3-4、交叉媒體相關(guān)模型 5和多伯努利相關(guān)模型6等。聚類分析是機(jī)器學(xué)習(xí)領(lǐng)域中的一個主要分支，是人們認(rèn)識和探索事物之間內(nèi)在聯(lián)系的有效手段。近幾年來，基于聚類分析的自動圖像標(biāo)標(biāo)注技術(shù)運(yùn)應(yīng)而生，并取得了可喜的效果。在參考文獻(xiàn)7-8中，聚類用于一組訓(xùn)練圖像的低層特征，利用統(tǒng)計學(xué)方法獲得低層特征與標(biāo)注詞間的一組映射。用獲得的映射規(guī)則標(biāo)注圖像。這些方法都基于一種假設(shè)：視覺特征相同或相似的圖像，其語義也應(yīng)相同

9、相似。由于語義鴻溝的存在，實際情況并非如此，那些有著相似的視覺特征的圖像它們的語義并不相同，甚至相差很遠(yuǎn)。如“天空”與“大?！笔遣煌恼Z義，但它們的視覺特征卻很相似。如何挖掘圖像的高層語義與低層特征之間的內(nèi)在聯(lián)系是當(dāng)前圖像標(biāo)注領(lǐng)域中研究難點(diǎn)之一。本文提出基于語義子空間譜聚類的圖像自動標(biāo)注方法。為了建立圖像的低層視覺特征與標(biāo)注文本特征間的相關(guān)性，在訓(xùn)練集上分別提取圖像的低層視覺特征和語義特征。在語義子空間內(nèi)，以圖像標(biāo)注詞作為特征向量，利用調(diào)和均值譜聚類算法對圖像進(jìn)行聚類，形成若干個語義類。用每個類的中心詞作為該類的標(biāo)簽，再在圖像空間內(nèi)對每個語義類中的圖像分割成區(qū)域，提取每分割后的每區(qū)域的低層特征

10、，根據(jù)區(qū)域的低層特征的相似關(guān)系，再次利用譜聚類算法把同一語義類中的相似區(qū)域聚類到同一個塊中，形成若干個塊。然后運(yùn)用多伯努利模型求出語義類中每個塊與主題詞的聯(lián)合概率分布，通過兩次聚類有效地建立圖像的低層特征與語義特征間的一致性。這樣，我們就在圖像語義與低層特征之間架建了一座橋梁。利用該聯(lián)合概率分布我們可以為未標(biāo)注圖像進(jìn)行自動標(biāo)注。2基于語義子空間譜聚類的圖像自動標(biāo)注2.1 基于K-調(diào)和均值譜聚類如果把一幅圖像看作一個文檔，圖像的標(biāo)注詞看作文檔的關(guān)鍵詞，那么我們對圖像的標(biāo)注詞為特征進(jìn)行聚類，就采用文本聚類方法對圖像進(jìn)行聚類了。目前流行的聚類方法主要有以K-Means為代表的基于劃分的方法和譜聚類方

11、法等。譜聚類方法是基于圖理論，根據(jù)數(shù)據(jù)間的相似性進(jìn)行聚類，由于與數(shù)據(jù)點(diǎn)的維數(shù)無關(guān)，只與數(shù)據(jù)點(diǎn)的個數(shù)有關(guān)，因此適用于非測度空間。它得到廣泛關(guān)注9。但傳統(tǒng)的譜聚類算法對初始中心選擇的比較敏感,使得其運(yùn)行結(jié)果不穩(wěn)定,且易于陷入局部極小點(diǎn)。同時,文本聚類問題本身也有其特殊性，文本向量通常為稀疏向量,含有較多的0,這也為聚類中心的選擇帶來困難。為此，我們通過引入K-調(diào)和均值,改善譜聚類算法的性能。K-調(diào)和均值（K-Harmonic Means，KHM）算法10是一種基于中心的聚類算法，該算法通過計算數(shù)據(jù)點(diǎn)到聚類中心距離的調(diào)和平均來構(gòu)造其性能函數(shù)。算法表述如下：算法1:基于 K-調(diào)和均值譜聚類算法輸入：n

12、個數(shù)據(jù)點(diǎn)，聚類數(shù)目k輸出：數(shù)據(jù)點(diǎn)集的類別Step 1: 構(gòu)造相似矩陣，其中，。其中是參數(shù). Step 2: 構(gòu)造Laplacian矩陣。其中是對角矩陣，Step 3: 計算的前k個最大的特征值所對應(yīng)的特征向量，生成矩陣；Step 4: 將矩陣的行向量轉(zhuǎn)變?yōu)閱挝幌蛄?，得到矩陣。Step 5: 采用KHM算法，把矩陣的每行聚成k類；由于KHM算法用數(shù)據(jù)點(diǎn)與所有聚類中心的距離的調(diào)和平均替代了數(shù)據(jù)點(diǎn)與聚類中心的最小距離，克服了對初始值敏感的問題。2.2 基于語義子空間的圖像聚類設(shè)是用于標(biāo)注圖像的關(guān)鍵詞詞匯表，m是詞匯表的大小，設(shè)是訓(xùn)練圖像集，是圖像的一組標(biāo)注詞。如果把圖像看作一個文檔，則可視為文檔的關(guān)

13、鍵詞。對每個圖像，我們構(gòu)造其關(guān)鍵詞的矢量。如果詞匯表中第k個關(guān)鍵詞，則。否則。由此我們可得到訓(xùn)練圖像集中圖像的標(biāo)注詞特征向量： (1) 兩特征向量，之間的距離定義為，利用余弦距離計算的值。在文本空間內(nèi)，以圖像標(biāo)注詞向量作為特征，利用K-調(diào)和均值譜聚類算法對進(jìn)行聚類，形成n個語義類。用每個類的中心詞作為該類的語義（類標(biāo)簽）2.3 圖像低層特征與語義映射關(guān)系在每個語義類中，我們把圖像分割成區(qū)域，提取分割后的區(qū)域的低層特征（包括形狀、空間位置、顏色和紋理等）用特征矢量表示。采用24維矢量表示。根據(jù)區(qū)域的低層特征的相似關(guān)系，再次利用K-調(diào)和均值譜聚類算法把同一語義類中的相似區(qū)域聚類到同一個塊（blob

14、）中，形成K個塊。通過優(yōu)化塊的個數(shù)K，使得每塊內(nèi)盡可能集中，塊與塊間距盡可能遠(yuǎn)離。為了確定最優(yōu)K值，通過設(shè)置不同的K進(jìn)行多次聚類，對不同的K值，計算各塊之間的距離和每個塊內(nèi)距根據(jù)Davies-Bouldin指數(shù)11，式（2）： (2) 取得最小值時的K應(yīng)為最優(yōu)的K值，也即： (3) 從而，在每個語義類內(nèi)，我們獲得了k個塊。這些塊繼承了所在類的語義。通過兩次聚類，訓(xùn)練圖像集被分割成若干個語義類，每個語義類用可用塊的中心特征和該類的關(guān)鍵詞表示： (4) 在一個語義類中，塊與關(guān)鍵詞的聯(lián)合概率分布通過下式求得： (5)式中是類的先驗概率，表示類中關(guān)鍵詞的條件概率，根據(jù)多伯努利模型可得： (6)上式中是

15、平衡系數(shù)；如果類有標(biāo)注詞，取值為1，否則為0。表示標(biāo)注詞在類中出現(xiàn)的次數(shù)，表示類中圖像個數(shù)?？赡芡ㄟ^下式計算得到： (7)其中表示塊中區(qū)域的個數(shù)。算法描述如下：算法2:區(qū)域塊與標(biāo)注詞語義映射算法輸入：訓(xùn)練圖像集； 標(biāo)注詞詞匯表 ； 輸出：區(qū)域塊與語義詞的聯(lián)合概率表。Step 1: 對每一訓(xùn)練集中圖像，提取其顏色、紋理、形狀等低層特征，并組成特征向量。根據(jù)公式（1）提取標(biāo)注詞特征向量Step 2: 以標(biāo)注詞特征向量為特征，利用K-調(diào)和均值譜聚類算法對圖像進(jìn)行聚類，形成n個語義類。并計算每個類的中心詞作為該類的語義Step 3: 對每一圖像，運(yùn)用分割算法進(jìn)行區(qū)域分割，提取分割后的每區(qū)域的低層特征（

16、包括形狀、空間位置、顏色和紋理等）用特征矢量f 表示；Step 4: 根據(jù)區(qū)域的低層特征的相似關(guān)系，再次利用K-調(diào)和均值譜聚類算法把同一語義類中的相似區(qū)域聚類到同一個塊中，形成K個語義塊。 Step 5: 利用公式（5）。計算塊與詞的聯(lián)合概率并保存。2.4圖像標(biāo)注過程利用公式（5）我們可以為未標(biāo)注圖像進(jìn)行自動標(biāo)注。對輸入的待標(biāo)注圖像，首先進(jìn)行分割，提取各區(qū)域特征，對每一個確定它所在塊： (8)然后，計算詞匯表中每一個標(biāo)注詞對圖像的概率： (9)其中： (10)表示區(qū)域像素的個數(shù)。 (11)輸出前N個概率最大的詞匯作為I的最終標(biāo)注結(jié)果。算法描述如下：算法3:圖像標(biāo)注算法輸入：區(qū)域塊與主題詞的聯(lián)合

17、概率表； 待標(biāo)注圖像；輸出：前N個概率最大的詞。Step 1: 對輸入的待標(biāo)注圖像，首先進(jìn)行分割，提取各區(qū)域特征Step 2: 利用公式（8）對每一個確定它所在塊Step 3: 利用公式（9）計算每個標(biāo)注詞對圖像的概率Step 4: 輸出前N個概率最大的詞。3 實驗結(jié)果與分析為了便于進(jìn)行比較，我們采用Duygulu等人的Corel數(shù)據(jù)集作為實驗數(shù)據(jù)，這是由于近年來在該數(shù)據(jù)集上公布的、可供參考的實驗成果最為全面。實驗中我們?nèi)匀皇褂闷骄闇?zhǔn)率（average precision）與平均查全率（average recall）作為圖像標(biāo)注的性能指標(biāo)。我們根據(jù)圖像的標(biāo)注詞特征向量，采用利用K-調(diào)和均值譜

18、聚類算法對每組圖像進(jìn)行聚類，形成87個語義類。用每個類的中心詞作為該類的語義（類標(biāo)簽）。圖（1）是語義類實例（a） Jet plane sky (b) cloud sky sun圖1 語義類Fig.1 Examples of semantic classes在每一個語義類，利用圖像分割方法12把每幅圖像分割成2-10個區(qū)域并提取每個區(qū)域的形狀、空間位置、顏色和紋理等24維區(qū)域特征向量。根據(jù)區(qū)域的低層特征的相似關(guān)系，再次調(diào)用K-調(diào)和均值譜聚類算法把同一語義類中的相似區(qū)域聚類到同一個塊中，形成K個語義塊。實驗中K取4-5效果較好，這和式（3）計算結(jié)果一致。這樣，每一組Corel圖像集共形成了369

19、個語義塊。然后計算每個語義塊與標(biāo)注詞的聯(lián)合概率。對待標(biāo)注圖像，首先進(jìn)行分割，形成2-10區(qū)域，同樣提取每個區(qū)域的形狀、空間位置、顏色和紋理等區(qū)域特征向量。計算每個區(qū)域與語義塊的相似度，采用公式(10)計算圖像與詞匯表中的每個標(biāo)注的聯(lián)合概率，輸出前5個概率最大的詞匯作為I的最終標(biāo)注結(jié)果。在Corel數(shù)據(jù)集上，我們把當(dāng)今其它優(yōu)秀算法的性能指標(biāo)作為基準(zhǔn)，比較了本文提出的基于譜聚類的圖像自動標(biāo)注系統(tǒng)的標(biāo)注性能。Avg-precisionAvg-recall00.050.4CMRMMBRMProposed algorithmTM圖2 Corel數(shù)據(jù)集上不同標(biāo)注系

20、統(tǒng)的性能比較Fig. 2 Performance comparison with different annotation on Corel data set與其它基于聚類的圖像標(biāo)注方法相比較，本文提出的方法無論是平均查準(zhǔn)率,還是平均查全率都得到改善。我們從圖(2)中可以看出，本文提出的方法在Corel數(shù)據(jù)集上超過了TM、CMRM和MBRM的性能。4 小結(jié)本文提出了一種簡單、有效的圖像自動標(biāo)注方法。為了建立圖像的低層特征與語義特征間的相關(guān)性。被提算法首先在語義子空間內(nèi)，對訓(xùn)練圖像先按語義聚類，使得語義相同或相近和圖像處于同一語義類中，再對每個語義類按區(qū)域特征聚類，使得相似區(qū)域聚類到同一個塊中。

21、通過這兩次聚類有效地建立圖像的低層特征與語義特征間的一致性。然后利用多伯努利模型求出區(qū)域塊與語義詞的聯(lián)合概率分布，在圖像語義與低層特征之間架建了一座橋梁。有效縮短了語義鴻溝。在Corel數(shù)據(jù)集上，進(jìn)行實驗比較，結(jié)果表明所提出的方法較好地提高了圖像標(biāo)注準(zhǔn)確度。參考文獻(xiàn)1 Liu Y,Zhang D S,Lu G J,et al. A survery of content-based image retrieval with high-level semanticsJ.Pattern Recognition. 2007, 40(1): 262-2822 Mori Y,Takahashi H,Oka

22、 R. Image-to-word transformation based on dividing and vector quantizing images with wordsOL. http:/citeseer.ist. /368129.html3 Duygulu P,Barnard K,de Freitas J F G, et al. Object recognition as machine translation:learning a lexicon for a fixed image vocabularyM. Leture Noyes in Computer Sci

23、ence. Heidelberg: Springer. 2002, 23(53):97-1124 Barnard K, Duygulu P, Forsyth D,et al. Mathing words and picturesJ. Journal of Machine Learning Research.2003,3(2):1107-11355 Jeon J,Lavrenko V,Mnmatha R. Automatic image annotation and retrieval using cross-media relevance modelsC. Proceedings. of th

24、e 26th Annual Intelnational ACM SIGIR Conference on Research and Development in information Retrieval,Toronto.2003:119-1266 Feng S L, Manmatha R, Lavrenko V. Multiple Bernoulli relevance models for image and video annotationC. Proc. Of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Washington D C, 2004:1002-1009 7 Stan D, Sethi I K. Mapping low-level image features to semantic conceptsC. Proceedings of the Storage and Retrieval for Media Databases. 2001:172-179.8 Jin W, Shi R, Chua T S. A semi-