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

精品論文一種基于結(jié)構(gòu)學(xué)習(xí)的圖像標注方法崔超然，馬軍（山東大學(xué)計算機科學(xué)與技術(shù)學(xué)院，濟南 250101）5摘要：圖像標注工作對于當前的基于關(guān)鍵詞的圖像檢索系統(tǒng)至關(guān)重要。本文中，我們將圖像 標注問題看作一個最優(yōu)子集選擇的問題，并通過結(jié)構(gòu)學(xué)習(xí)的框架來學(xué)習(xí)一個得分函數(shù)，利用 該函數(shù)來評估不同候選標注集合的質(zhì)量。一個標注集合的質(zhì)量由它與待標注圖像的視覺近鄰 圖像的多種關(guān)系來判定。在基準數(shù)據(jù)集上的實驗結(jié)果證明了該方法在圖像標注任務(wù)中的有效 性。10關(guān)鍵詞：計算機應(yīng)用技術(shù)；圖像標注；結(jié)構(gòu)學(xué)習(xí)中圖分類號：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ù)字攝影技術(shù)的提高，互聯(lián)網(wǎng)中數(shù)字圖像的數(shù)目呈現(xiàn)出爆炸式的增 長。與此同時，這也增強了人們對高效的圖像檢索技術(shù)的需求。當前的商用搜索引擎仍是采 用基于文本的檢索技術(shù)，通過對圖像的標注信息建立索引，來為用戶提供檢索服務(wù)的，其檢 索性能依賴于圖像標注的質(zhì)量。但由于人工手動地為圖像添加標注是一項十分耗時耗力的工 作，因此，近年來研究人員開展了對自動圖像標注技術(shù)的研究30自動圖像標注是指機器自動地選擇一組相關(guān)的標注詞來反映圖像的視覺內(nèi)容。已有的工 作大體可以分三類，即：基于概率的方法，基于分類的方法和基于近鄰的方法?；诟怕实?方法旨在利用訓(xùn)練集來推斷出圖像的視覺特征和標注詞之間的聯(lián)合概率分布。在進行標注 時，分別計算不同的標注詞相對圖像的條件概率?；诜诸惖姆椒槊恳粋€標注詞訓(xùn)練一個 分類器從而預(yù)測該標注詞是否在圖像中出現(xiàn)。在基于近鄰的方法中，算法首選在訓(xùn)練中找到35一組與測試圖像視覺相近的“近鄰”圖像，然后將這些“近鄰”的標注詞傳遞給測試圖像。 本質(zhì)上，圖像標注工作的輸入是一幅圖像，輸出是一組標簽集合。因此，該問題可以被看作一個結(jié)構(gòu)學(xué)習(xí)(structural learning)的問題。本文中，我們提出通過 structural svm1框架 來學(xué)習(xí)一個評價函數(shù)，并利用該函數(shù)評估不同的候選標簽相對于給定圖像的相關(guān)性。一個標 簽的相關(guān)性由它和測試樣本的“近鄰”圖像的多種關(guān)系來判定。我們采用了 cutting plane40算法2來求解問題中推導(dǎo)出的優(yōu)化問題，然后利用學(xué)習(xí)到的評價函數(shù)來為測試圖像選擇最優(yōu)基金項目：教育部博士點基金(20110131110028)作者簡介：崔超然，(1987-)，男，博士研究生，主要研究領(lǐng)域為信息檢索、多媒體信息的分析與理解。通信聯(lián)系人：馬軍，（1956-），教授，博士生導(dǎo)師，主要研究領(lǐng)域為 web 文本和多媒體檢索、社會網(wǎng)絡(luò)。e-mail: - 6 -的標注詞。實驗中，我們在 corel 5k 數(shù)據(jù)集上對本文提出的方法進行了評測。實驗結(jié)果顯示，相 比于以往方法在該數(shù)據(jù)上公布的實驗結(jié)果，本文在準確率和召回率等測度上均取得了最優(yōu)的 結(jié)果。451問題描述指定 x=x1,x2,.,xn代表一個圖像集合，所有可能在該集合中出現(xiàn)的不同的標注詞的集 合為 w=w1,w2,.,wm。圖像標注的目標是學(xué)習(xí)一個映射 h: xy，其中 y 代表包含所有可能的標注詞集合的空間。給定一幅圖像 xx，我們利用 h 為 x 預(yù)測一個合適的標注詞集合 yw。在監(jiān)督學(xué)習(xí)中，我們會被給予一組訓(xùn)練樣本，s=(x(i),y(i)xy: i = 1,.,t，其中 y(i)是圖像50x(i)的真實標注詞集合。我們希望學(xué)習(xí)到的映射函數(shù) h 可以使得訓(xùn)練樣本的經(jīng)驗損失最小化， 即1tmin r (h) = min ( y( i ) , h( x(i ) )hsht i =1上式中，(y(i),h(x(i)代表預(yù)測標注 h(x(i)和真實標注 y(i)之間的差距。在本文中，我們將它定 義為如下形式：55( y, y ) = 1 -2 prp = | y y |p = | y y |p + r| y | y |其中，y 和 y分別代表兩個標注詞集合，|y|代表 y 中標簽的個數(shù)，|yy|表示兩個集合中相 同標簽的個數(shù)。本文中，我們采用 structural svm 學(xué)習(xí)框架來解決上述問題。structural svm 框架的基 本思想是學(xué)習(xí)一個得分函數(shù) f(x,y): xyr，該函數(shù)度量了候選標注集合 y 相對于給定圖像60x 的相關(guān)程度。我們通過特征向量(x,y)來表示圖像/標注對(x,y)。類比于線性 svm，我們假 設(shè)得分函數(shù) f(x,y)可以被表示為(x,y)的線性組合，即f ( x, y) = wt ( x, y)其中，w 是一個權(quán)重向量。直觀上說，特征表示函數(shù)必須能較好地區(qū)別高質(zhì)量和低質(zhì)量的候選標注。我們將在下一節(jié)介紹的具體表示形式。65當?shù)梅趾瘮?shù) f(x,y)確定后，映射函數(shù) h 可以利用下式為圖像 x 預(yù)測它的標注詞集合y* = h( x) = arg max f (x, y)yy 遵循以往的工作3-5，實驗中我們每幅圖像預(yù)測 l(l = 5)個標簽，因此，在上式中|y*| = l。2特征表示在本節(jié)中，我們討論圖像/標注對的聯(lián)合特征表示函數(shù)。給定訓(xùn)練樣本集，我們希望70能代表一組聯(lián)合特征，使得圖像和真實標注的特征與它和其它候選標注的特征的差異較 大。直觀上感覺，視覺上相似的圖像的內(nèi)容往往反映了同一主題，因而它們更有可能會關(guān)聯(lián) 到相同的標注詞。從這點出發(fā)，給定一個圖像/標注對(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 個“近鄰”圖像，snn1, ., snnk 分別代表它們相對于 x的相似性。(w, nni)是一個特征向量，它編碼了標注詞 w 和第 i 個“近鄰”nni 之間的關(guān)系。 進一步地，我們可以看到，實際上(x,y)是 k 個這樣的關(guān)系分量的組合特征向量。在本文中，我們分別計算圖像在不同視覺特征上的距離，并取它們的平均值作為兩幅圖80像間最終的距離3，進而根據(jù)距離的大小選擇出視覺“近鄰”。我們認為“近鄰”nni 對 x的影響程度與它和 x 的相關(guān)性大小呈正相關(guān)關(guān)系。定義 nni 相對于 x 的相關(guān)性為： 1s= expnni1 + d (x, nn ) i 其中，d(x, nni)是 x 和 nni 之間歸一化后的視覺距離。如上所述，(w, nni)編碼了標注詞 w 和第 i 個“近鄰”nni 之間的關(guān)系。具體地，(w,85nni)反映了 w 相對于 nni 的以下三種關(guān)系，即出現(xiàn)頻率，共現(xiàn)性以及語義相關(guān)性。根據(jù) w 在訓(xùn)練集樣本中的出現(xiàn)頻率，我們可以通過多重伯努利模型(multiple bernoulli)6來估計用 w 來標注 nni 的概率大小，即： w, nn + twp(w | nn ) =ii + t這里，是一個平滑參數(shù)，實驗中我們通過交叉驗證來確定它的取值大小。w, nni = 1，如90果 w 出現(xiàn)在 nni 的真實標注詞集合中，反之，w, nni = 0。tw 代表訓(xùn)練集中含有標簽 w 的圖 像的數(shù)目，而 t 表示訓(xùn)練集中全部圖像的數(shù)目。為了進一步探究標注詞 w 和“近鄰”圖像 nni 的相關(guān)性，我們考慮關(guān)鍵詞之間的兩種語義關(guān)系，即共現(xiàn)性和 wordnet 語義相關(guān)性。兩個關(guān)鍵詞之間的共現(xiàn)性 sco 被定義為：s (w , w ) = tf (w1 , w2 ) ，co12tf (w2 )95其中 w1 和 w2 是兩個關(guān)鍵詞，tf(w2)表示 w2 在訓(xùn)練集中的出現(xiàn)頻率，tf(w1,w2)表示訓(xùn)練集中同 時包含 w1 和 w2 的圖像的數(shù)目。此外，我們利用林氏相關(guān)度(lins similarity measure)7來估計 兩個關(guān)鍵詞之間的 wordnet 語義相關(guān)性 swn。根據(jù) sco 和 swn 的定義，w 與 nni 的標注之間的 共現(xiàn)性和 wordnet 語義相關(guān)性進而被分別定義為：rco (w, nni ) = max sco (w, t )tnni 。rwn (w, nni ) = max swn (w, t )tnni100基于上面的定義，(w, nni)的具體的形式是一個三維向量，即： p(w | nni ) (w, nni ) = rco (w, nni ) 。 rwn (w, nni )因此，當我們考慮 x 的 k 個“近鄰圖像”時，聯(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. 計算y* = arg max yy h ( y; w)6. 計算i = max0, max ywh ( y; w)7. if8.h ( y*; w) i + wi wi y*t9.重新求解優(yōu)化目標min 1 | w |2 + ci10. end if11. end for12. 直到 沒有 wi 在本輪迭代中改變13. 返回 ww, 0 2n i =1算法 2 貪心標簽子集選擇算法輸入：(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)練一個圖像標注模型。給定一組訓(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上式中，每一幅圖像的每一個不正確的標注候選項均對應(yīng)一個約束條件。因此，該優(yōu)化問題 總共涉及到關(guān)鍵詞個數(shù)的指數(shù)次方個約束條件。在本文中，我們采用 cutting plane 算法2來 解決該問題，過程如算法 1 所示。該算法旨在找到一個全部約束的子集，使得滿足該子集中120125約束的解同時也能在一定誤差率下滿足全部約束。算法為每一個訓(xùn)練樣本(x(i),y(i)尋找能產(chǎn)生 最違反的約束條件的候選標注集 y*(算法 5 行)。如果此時的解違反約束子集的程度超過， 則算法將 y*加入到結(jié)合 wi 中，然后求解這一修改后的優(yōu)化問題(算法 7-10 行)。算法 1 中，我們需要在每一輪中迭代中尋找最違反的約束條件，即求解下面的優(yōu)化問題：arg max ( y( i ) , y) + wt ( x(i ) , y)yy本文中，我們提出了一個簡單而有效的貪心算法來解決該問題，如算法 2 所示。算法不斷的選擇能給當前的標注集合 y*帶來最大收益標注詞 t*，并將 t*加入到 y*直到 y*中標注詞的個 數(shù)達到 l。同時，該貪心算法也被用來在測試時為新圖像預(yù)測它的標注詞集合。4實驗tab. 1 不同方法的標注結(jié)果的比較p% r% n+msc4 25jec3 27lasso3 24gs5 30our method 3132 13632 13929 12733 14636 1511301351401454.1實驗設(shè)置實驗中，我們采用了 corel 5k 數(shù)據(jù)集。該數(shù)據(jù)被廣泛應(yīng)用在以往的圖像標注工作中， 因而我們可以與以往工作的結(jié)果進行直接比較。對于每幅圖像，我們提取了與文獻3所述 相同的特征描述。為了評價方法給出的預(yù)測標注的性能，我們以每一個關(guān)鍵詞為查詢進行圖 像檢索操作，取各查詢結(jié)果的平均準確率(p)和平均召回率(r)作為兩個評價指標。同時，我 們也考慮了結(jié)果中非零召回率的查詢的個數(shù)(n+)。實驗中，我們?yōu)槊糠鶊D像選取 k=100 個 “近鄰”圖像。4.2實驗結(jié)果我們將本文提出的方法與以往的多個算法進行了比較，比較結(jié)果如表 1 所示。相比于 jec3方法，盡管我們的方法與它采用了相同的視覺特征來計算“近鄰”圖像，但卻在 p，r 和 n+三個測度上分別提高了 4%，4%和 12。同時，相比于以往方法中其他復(fù)雜模型的結(jié)果， 如 msc4，lasso3和 gs5，我們的方法也取得了最好的效果，這證明了本文提出的基于 結(jié)構(gòu)學(xué)習(xí)的圖像標注方法的有效性。5結(jié)論本文給出了一種基于結(jié)構(gòu)學(xué)習(xí)的自動圖像標注方法。在本文中，圖像標注問題被看作一 個結(jié)構(gòu)學(xué)習(xí)的問題。我們提出通過 structural svm 框架來學(xué)習(xí)一個評價函數(shù)，并利用該函數(shù) 來評估不同的候選標簽相對于給定圖像的相關(guān)性。在基準數(shù)據(jù)集上的實驗結(jié)果顯示，相比于 以往方法公布的實驗結(jié)果，本文在準確率和召回率等測度上均取得了最優(yōu)的結(jié)果。參考文獻 (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