一種基于結(jié)構(gòu)學(xué)習(xí)的圖像標(biāo)注方法.doc

精品論文一種基于結(jié)構(gòu)學(xué)習(xí)的圖像標(biāo)注方法崔超然，馬軍（山東大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，濟(jì)南 250101）5摘要：圖像標(biāo)注工作對(duì)于當(dāng)前的基于關(guān)鍵詞的圖像檢索系統(tǒng)至關(guān)重要。本文中，我們將圖像 標(biāo)注問題看作一個(gè)最優(yōu)子集選擇的問題，并通過結(jié)構(gòu)學(xué)習(xí)的框架來學(xué)習(xí)一個(gè)得分函數(shù)，利用 該函數(shù)來評(píng)估不同候選標(biāo)注集合的質(zhì)量。一個(gè)標(biāo)注集合的質(zhì)量由它與待標(biāo)注圖像的視覺近鄰 圖像的多種關(guān)系來判定。在基準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果證明了該方法在圖像標(biāo)注任務(wù)中的有效 性。10關(guān)鍵詞：計(jì)算機(jī)應(yīng)用技術(shù)；圖像標(biāo)注；結(jié)構(gòu)學(xué)習(xí)中圖分類號(hào)：tp391image annotation via structural learningcui chaoran, ma jun15(school of computer science and technology, shandong university, jinan 250101) abstract: image annotation plays an important role in modern keyword-based image retrieval systems. in this paper, we formulate the image annotation problem as that of selecting the optimal keyword subset for an image, and employ a structural learning framework to learn a scoring function for evaluating the quality of different candidate subsets. the quality of a keyword subset20is assessed based on its relations with visually similar neighbors of that image. experiments on benchmark data set demonstrate the effectiveness of our approach for image annotation.keywords: computer applied technology; image annotation; structural learning0引言25伴隨著網(wǎng)絡(luò)的發(fā)展和數(shù)字?jǐn)z影技術(shù)的提高，互聯(lián)網(wǎng)中數(shù)字圖像的數(shù)目呈現(xiàn)出爆炸式的增 長。與此同時(shí)，這也增強(qiáng)了人們對(duì)高效的圖像檢索技術(shù)的需求。當(dāng)前的商用搜索引擎仍是采 用基于文本的檢索技術(shù)，通過對(duì)圖像的標(biāo)注信息建立索引，來為用戶提供檢索服務(wù)的，其檢 索性能依賴于圖像標(biāo)注的質(zhì)量。但由于人工手動(dòng)地為圖像添加標(biāo)注是一項(xiàng)十分耗時(shí)耗力的工 作，因此，近年來研究人員開展了對(duì)自動(dòng)圖像標(biāo)注技術(shù)的研究30自動(dòng)圖像標(biāo)注是指機(jī)器自動(dòng)地選擇一組相關(guān)的標(biāo)注詞來反映圖像的視覺內(nèi)容。已有的工 作大體可以分三類，即：基于概率的方法，基于分類的方法和基于近鄰的方法?；诟怕实?方法旨在利用訓(xùn)練集來推斷出圖像的視覺特征和標(biāo)注詞之間的聯(lián)合概率分布。在進(jìn)行標(biāo)注 時(shí)，分別計(jì)算不同的標(biāo)注詞相對(duì)圖像的條件概率。基于分類的方法為每一個(gè)標(biāo)注詞訓(xùn)練一個(gè) 分類器從而預(yù)測該標(biāo)注詞是否在圖像中出現(xiàn)。在基于近鄰的方法中，算法首選在訓(xùn)練中找到35一組與測試圖像視覺相近的“近鄰”圖像，然后將這些“近鄰”的標(biāo)注詞傳遞給測試圖像。 本質(zhì)上，圖像標(biāo)注工作的輸入是一幅圖像，輸出是一組標(biāo)簽集合。因此，該問題可以被看作一個(gè)結(jié)構(gòu)學(xué)習(xí)(structural learning)的問題。本文中，我們提出通過 structural svm1框架 來學(xué)習(xí)一個(gè)評(píng)價(jià)函數(shù)，并利用該函數(shù)評(píng)估不同的候選標(biāo)簽相對(duì)于給定圖像的相關(guān)性。一個(gè)標(biāo) 簽的相關(guān)性由它和測試樣本的“近鄰”圖像的多種關(guān)系來判定。我們采用了 cutting plane40算法2來求解問題中推導(dǎo)出的優(yōu)化問題，然后利用學(xué)習(xí)到的評(píng)價(jià)函數(shù)來為測試圖像選擇最優(yōu)基金項(xiàng)目：教育部博士點(diǎn)基金(20110131110028)作者簡介：崔超然，(1987-)，男，博士研究生，主要研究領(lǐng)域?yàn)樾畔z索、多媒體信息的分析與理解。通信聯(lián)系人：馬軍，（1956-），教授，博士生導(dǎo)師，主要研究領(lǐng)域?yàn)?web 文本和多媒體檢索、社會(huì)網(wǎng)絡(luò)。e-mail: - 6 -的標(biāo)注詞。實(shí)驗(yàn)中，我們?cè)?corel 5k 數(shù)據(jù)集上對(duì)本文提出的方法進(jìn)行了評(píng)測。實(shí)驗(yàn)結(jié)果顯示，相 比于以往方法在該數(shù)據(jù)上公布的實(shí)驗(yàn)結(jié)果，本文在準(zhǔn)確率和召回率等測度上均取得了最優(yōu)的 結(jié)果。451問題描述指定 x=x1,x2,.,xn代表一個(gè)圖像集合，所有可能在該集合中出現(xiàn)的不同的標(biāo)注詞的集 合為 w=w1,w2,.,wm。圖像標(biāo)注的目標(biāo)是學(xué)習(xí)一個(gè)映射 h: xy，其中 y 代表包含所有可能的標(biāo)注詞集合的空間。給定一幅圖像 xx，我們利用 h 為 x 預(yù)測一個(gè)合適的標(biāo)注詞集合 yw。在監(jiān)督學(xué)習(xí)中，我們會(huì)被給予一組訓(xùn)練樣本，s=(x(i),y(i)xy: i = 1,.,t，其中 y(i)是圖像50x(i)的真實(shí)標(biāo)注詞集合。我們希望學(xué)習(xí)到的映射函數(shù) h 可以使得訓(xùn)練樣本的經(jīng)驗(yàn)損失最小化， 即1tmin r (h) = min ( y( i ) , h( x(i ) )hsht i =1上式中，(y(i),h(x(i)代表預(yù)測標(biāo)注 h(x(i)和真實(shí)標(biāo)注 y(i)之間的差距。在本文中，我們將它定 義為如下形式：55( y, y ) = 1 -2 prp = | y y |p = | y y |p + r| y | y |其中，y 和 y分別代表兩個(gè)標(biāo)注詞集合，|y|代表 y 中標(biāo)簽的個(gè)數(shù)，|yy|表示兩個(gè)集合中相 同標(biāo)簽的個(gè)數(shù)。本文中，我們采用 structural svm 學(xué)習(xí)框架來解決上述問題。structural svm 框架的基 本思想是學(xué)習(xí)一個(gè)得分函數(shù) f(x,y): xyr，該函數(shù)度量了候選標(biāo)注集合 y 相對(duì)于給定圖像60x 的相關(guān)程度。我們通過特征向量(x,y)來表示圖像/標(biāo)注對(duì)(x,y)。類比于線性 svm，我們假 設(shè)得分函數(shù) f(x,y)可以被表示為(x,y)的線性組合，即f ( x, y) = wt ( x, y)其中，w 是一個(gè)權(quán)重向量。直觀上說，特征表示函數(shù)必須能較好地區(qū)別高質(zhì)量和低質(zhì)量的候選標(biāo)注。我們將在下一節(jié)介紹的具體表示形式。65當(dāng)?shù)梅趾瘮?shù) f(x,y)確定后，映射函數(shù) h 可以利用下式為圖像 x 預(yù)測它的標(biāo)注詞集合y* = h( x) = arg max f (x, y)yy 遵循以往的工作3-5，實(shí)驗(yàn)中我們每幅圖像預(yù)測 l(l = 5)個(gè)標(biāo)簽，因此，在上式中|y*| = l。2特征表示在本節(jié)中，我們討論圖像/標(biāo)注對(duì)的聯(lián)合特征表示函數(shù)。給定訓(xùn)練樣本集，我們希望70能代表一組聯(lián)合特征，使得圖像和真實(shí)標(biāo)注的特征與它和其它候選標(biāo)注的特征的差異較 大。直觀上感覺，視覺上相似的圖像的內(nèi)容往往反映了同一主題，因而它們更有可能會(huì)關(guān)聯(lián) 到相同的標(biāo)注詞。從這點(diǎn)出發(fā)，給定一個(gè)圖像/標(biāo)注對(duì)(x,y)，我們首選尋找 x 在訓(xùn)練集中的視 覺“近鄰”圖像，然后再根據(jù) y 與這些“近鄰”的關(guān)系來定義(x,y)。具體地，(x,y)被定 義為如下形式：1 s nn (w, nn1 ) 75 ( x, y) = | y |w y m s nnk (w, nn ) | y |wy k 其中 nn1, ., nnk 是與 x 最為相似的 k 個(gè)“近鄰”圖像，snn1, ., snnk 分別代表它們相對(duì)于 x的相似性。(w, nni)是一個(gè)特征向量，它編碼了標(biāo)注詞 w 和第 i 個(gè)“近鄰”nni 之間的關(guān)系。 進(jìn)一步地，我們可以看到，實(shí)際上(x,y)是 k 個(gè)這樣的關(guān)系分量的組合特征向量。在本文中，我們分別計(jì)算圖像在不同視覺特征上的距離，并取它們的平均值作為兩幅圖80像間最終的距離3，進(jìn)而根據(jù)距離的大小選擇出視覺“近鄰”。我們認(rèn)為“近鄰”nni 對(duì) x的影響程度與它和 x 的相關(guān)性大小呈正相關(guān)關(guān)系。定義 nni 相對(duì)于 x 的相關(guān)性為： 1s= expnni1 + d (x, nn ) i 其中，d(x, nni)是 x 和 nni 之間歸一化后的視覺距離。如上所述，(w, nni)編碼了標(biāo)注詞 w 和第 i 個(gè)“近鄰”nni 之間的關(guān)系。具體地，(w,85nni)反映了 w 相對(duì)于 nni 的以下三種關(guān)系，即出現(xiàn)頻率，共現(xiàn)性以及語義相關(guān)性。根據(jù) w 在訓(xùn)練集樣本中的出現(xiàn)頻率，我們可以通過多重伯努利模型(multiple bernoulli)6來估計(jì)用 w 來標(biāo)注 nni 的概率大小，即： w, nn + twp(w | nn ) =ii + t這里，是一個(gè)平滑參數(shù)，實(shí)驗(yàn)中我們通過交叉驗(yàn)證來確定它的取值大小。w, nni = 1，如90果 w 出現(xiàn)在 nni 的真實(shí)標(biāo)注詞集合中，反之，w, nni = 0。tw 代表訓(xùn)練集中含有標(biāo)簽 w 的圖 像的數(shù)目，而 t 表示訓(xùn)練集中全部圖像的數(shù)目。為了進(jìn)一步探究標(biāo)注詞 w 和“近鄰”圖像 nni 的相關(guān)性，我們考慮關(guān)鍵詞之間的兩種語義關(guān)系，即共現(xiàn)性和 wordnet 語義相關(guān)性。兩個(gè)關(guān)鍵詞之間的共現(xiàn)性 sco 被定義為：s (w , w ) = tf (w1 , w2 ) ，co12tf (w2 )95其中 w1 和 w2 是兩個(gè)關(guān)鍵詞，tf(w2)表示 w2 在訓(xùn)練集中的出現(xiàn)頻率，tf(w1,w2)表示訓(xùn)練集中同 時(shí)包含 w1 和 w2 的圖像的數(shù)目。此外，我們利用林氏相關(guān)度(lins similarity measure)7來估計(jì) 兩個(gè)關(guān)鍵詞之間的 wordnet 語義相關(guān)性 swn。根據(jù) sco 和 swn 的定義，w 與 nni 的標(biāo)注之間的 共現(xiàn)性和 wordnet 語義相關(guān)性進(jìn)而被分別定義為：rco (w, nni ) = max sco (w, t )tnni 。rwn (w, nni ) = max swn (w, t )tnni100基于上面的定義，(w, nni)的具體的形式是一個(gè)三維向量，即： p(w | nni ) (w, nni ) = rco (w, nni ) 。 rwn (w, nni )因此，當(dāng)我們考慮 x 的 k 個(gè)“近鄰圖像”時(shí)，聯(lián)合特征向量(x,y)的總維度是 3k。3基于 structural svm 的學(xué)習(xí)過程算法 1 cutting plane 算法 輸入：(x(1), y(1), ., (x(t), y(t), c, 輸出：w1. 初始化 wi for all i=1,.,t2. 重復(fù)3. for i = 1, ., t doi4. h ( y; w) ( y ( i ) , y) + wt ( x( i ) , y)5. 計(jì)算y* = arg max yy h ( y; w)6. 計(jì)算i = max0, max ywh ( y; w)7. if8.h ( y*; w) i + wi wi y*t9.重新求解優(yōu)化目標(biāo)min 1 | w |2 + ci10. end if11. end for12. 直到 沒有 wi 在本輪迭代中改變13. 返回 ww, 0 2n i =1算法 2 貪心標(biāo)簽子集選擇算法輸入：(x(i), y(i), w, l輸出：y*1. 初始化y* 2. v ( x, y, y) ( y, y) + wt ( x, y)3. for k =1,., l4. ( i ) (i )t* arg maxty v (x5. y y t*, y , y t)1056. end for7. 返回 y*在本節(jié)中，我們利用 structural svm 來訓(xùn)練一個(gè)圖像標(biāo)注模型。給定一組訓(xùn)練樣本， s=(x(i),y(i)xy: i = 1,.,t，structural svm 通過求解下面的優(yōu)化問題來得到最優(yōu)的權(quán)重 向量 w1：優(yōu)化問題 1. (structural svm)110min 1 | w |2 + ctisubjected to:w, 0 2i, y y y(i ) :n i =1iwt ( x(i ) , y(i ) ) wt (x( i ) , y) + ( y(i ) , y) 115上式中，每一幅圖像的每一個(gè)不正確的標(biāo)注候選項(xiàng)均對(duì)應(yīng)一個(gè)約束條件。因此，該優(yōu)化問題 總共涉及到關(guān)鍵詞個(gè)數(shù)的指數(shù)次方個(gè)約束條件。在本文中，我們采用 cutting plane 算法2來 解決該問題，過程如算法 1 所示。該算法旨在找到一個(gè)全部約束的子集，使得滿足該子集中120125約束的解同時(shí)也能在一定誤差率下滿足全部約束。算法為每一個(gè)訓(xùn)練樣本(x(i),y(i)尋找能產(chǎn)生 最違反的約束條件的候選標(biāo)注集 y*(算法 5 行)。如果此時(shí)的解違反約束子集的程度超過， 則算法將 y*加入到結(jié)合 wi 中，然后求解這一修改后的優(yōu)化問題(算法 7-10 行)。算法 1 中，我們需要在每一輪中迭代中尋找最違反的約束條件，即求解下面的優(yōu)化問題：arg max ( y( i ) , y) + wt ( x(i ) , y)yy本文中，我們提出了一個(gè)簡單而有效的貪心算法來解決該問題，如算法 2 所示。算法不斷的選擇能給當(dāng)前的標(biāo)注集合 y*帶來最大收益標(biāo)注詞 t*，并將 t*加入到 y*直到 y*中標(biāo)注詞的個(gè) 數(shù)達(dá)到 l。同時(shí)，該貪心算法也被用來在測試時(shí)為新圖像預(yù)測它的標(biāo)注詞集合。4實(shí)驗(yàn)tab. 1 不同方法的標(biāo)注結(jié)果的比較p% r% n+msc4 25jec3 27lasso3 24gs5 30our method 3132 13632 13929 12733 14636 1511301351401454.1實(shí)驗(yàn)設(shè)置實(shí)驗(yàn)中，我們采用了 corel 5k 數(shù)據(jù)集。該數(shù)據(jù)被廣泛應(yīng)用在以往的圖像標(biāo)注工作中， 因而我們可以與以往工作的結(jié)果進(jìn)行直接比較。對(duì)于每幅圖像，我們提取了與文獻(xiàn)3所述 相同的特征描述。為了評(píng)價(jià)方法給出的預(yù)測標(biāo)注的性能，我們以每一個(gè)關(guān)鍵詞為查詢進(jìn)行圖 像檢索操作，取各查詢結(jié)果的平均準(zhǔn)確率(p)和平均召回率(r)作為兩個(gè)評(píng)價(jià)指標(biāo)。同時(shí)，我 們也考慮了結(jié)果中非零召回率的查詢的個(gè)數(shù)(n+)。實(shí)驗(yàn)中，我們?yōu)槊糠鶊D像選取 k=100 個(gè) “近鄰”圖像。4.2實(shí)驗(yàn)結(jié)果我們將本文提出的方法與以往的多個(gè)算法進(jìn)行了比較，比較結(jié)果如表 1 所示。相比于 jec3方法，盡管我們的方法與它采用了相同的視覺特征來計(jì)算“近鄰”圖像，但卻在 p，r 和 n+三個(gè)測度上分別提高了 4%，4%和 12。同時(shí)，相比于以往方法中其他復(fù)雜模型的結(jié)果， 如 msc4，lasso3和 gs5，我們的方法也取得了最好的效果，這證明了本文提出的基于 結(jié)構(gòu)學(xué)習(xí)的圖像標(biāo)注方法的有效性。5結(jié)論本文給出了一種基于結(jié)構(gòu)學(xué)習(xí)的自動(dòng)圖像標(biāo)注方法。在本文中，圖像標(biāo)注問題被看作一 個(gè)結(jié)構(gòu)學(xué)習(xí)的問題。我們提出通過 structural svm 框架來學(xué)習(xí)一個(gè)評(píng)價(jià)函數(shù)，并利用該函數(shù) 來評(píng)估不同的候選標(biāo)簽相對(duì)于給定圖像的相關(guān)性。在基準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果顯示，相比于 以往方法公布的實(shí)驗(yàn)結(jié)果，本文在準(zhǔn)確率和召回率等測度上均取得了最優(yōu)的結(jié)果。參考文獻(xiàn) (references)1501 i. tsochantaridis, t. joachims, t. hofmann, y. altun. large margin methods for structured and interdependent output variablesj. journal of machine learning research, 2006, 6: 1453.2 t. joachims, t. finley. cutting-plane training of structural svmsj. machine learning, 2009, 77: 27-59. 3 a. makadia, v. pavlovic, s. kumar. a new baseline for image annotationa. proceedings of the 10th155160european conference on computer visionc. marseille, france4 wang c, yan s, zhang l, zhang h j. multi-la