基于文本和視覺特征融合的Web動畫素材標注

邱兆文, 吳 瑕, 陳海燕

(東北林業(yè)大學 信息與計算機工程學院，黑龍江 哈爾濱 150040)

1 引言

隨著信息技術(shù)的發(fā)展，網(wǎng)絡(luò)上的動畫素材急劇增加，如何合理利用其所在網(wǎng)頁的上下文信息分析和提取動畫素材的外部信息以提高檢索效率，是Web動畫素材檢索工作的重點。目前，針對Web動畫素材的研究還很少，但在Web圖像檢索方面取得了很大進步，如Wang等[1]利用從圖像所在網(wǎng)頁上的標注信息作為指導，結(jié)合視覺空間學習到的距離測度，實現(xiàn)了基于內(nèi)容的圖像檢索和基于檢索的圖像標注。

本文首先利用基于視覺特征網(wǎng)頁分割算法(VIPS)

從動畫素材周圍提取關(guān)鍵的文本信息，并對圖像進行分割，采用顯著圖方法提取視覺突出特征；然后結(jié)合文本信息與視覺特征，利用基于視覺相關(guān)的標注字過濾算法，突出與視覺特征具有明顯相關(guān)性的標注字，抑制或排除與動畫素材不相關(guān)的標注字，達到自動標注Web動畫素材，并提高其可靠性的目的。

2 Web動畫素材文本特征提取

2.1 Web動畫素材文本特征信息源

Web動畫素材與其所在的Web網(wǎng)頁存在密切聯(lián)系，因此Web文檔中的文本可以作為Web動畫素材的文本信息源。主要有6種： 動畫素材的名稱、所在的Html頁面所表達的主題、鏈接地址名稱、提示信息(標記的ALT屬性)、動畫素材與其周圍密切環(huán)繞的上下文信息以及TAG標記類型。這6種文本信息源可在基于關(guān)鍵詞的Web動畫素材檢索研究中部分或全部應(yīng)用，然后通過算法從這些信息源中抽取關(guān)鍵詞索引并檢索動畫素材。

2.2 基于視覺的頁面分割算法VIPS

基于視覺特征網(wǎng)頁分割算法VIPS[2]的數(shù)學模型是一個三元組Ω=(O,Φ,δ)，其中

O=(Ω1,Ω2,...,Ωn)是兩兩互不相交的網(wǎng)頁分塊集合，每個分塊可以看作為子網(wǎng)頁遞歸劃分為更小的子塊；

Φ=(Φ1,Φ2,...,ΦT)表示網(wǎng)頁分隔符集合，分為水平分隔符和垂直分隔符兩種；

δ表示集合O中分塊間的聯(lián)系，并有

δ=O×O→Φ∪{NULL}。

基于視覺特征的網(wǎng)頁分割算法循環(huán)執(zhí)行三個步驟： 可視塊的抽取、可視分隔條檢測以及網(wǎng)頁內(nèi)容結(jié)構(gòu)的構(gòu)建。首先將頁面分割成若干較大的分塊，并記錄當前塊的層次結(jié)構(gòu)。然后，對于較大的分塊繼續(xù)進行分割，直到分塊的內(nèi)聚度(degree of coherence，DoC)值達到給定的閾值為止，結(jié)束分割。

每次循環(huán)中，可以從網(wǎng)頁中提取與當前分塊相應(yīng)的帶有視覺信息的DOM(Document Object Model)[3]樹。檢查DOM樹當前層的每個DOM結(jié)點是否構(gòu)成一個單獨的頁面塊。如果不能，則按照同樣的方式對它的子結(jié)點進行檢查。當抽取所有分塊后，根據(jù)可視屬性賦予DoC值并存儲在頁面塊池中。然后，進行可視分隔條檢測，根據(jù)其相鄰分塊的視覺特征來設(shè)定分割條的權(quán)重，并重新構(gòu)建頁面的布局結(jié)構(gòu)。

在VIPS算法中, 給定閾值定義了整個頁面整體分塊粒度。但對頁面而言，各個區(qū)域的分塊粒度可能是不同的。為此，根據(jù)文獻[4]定義最大深度h與閾值一起控制頁面分塊的粒度。在VIPS算法建立了頁面的塊結(jié)構(gòu)樹后，若塊結(jié)構(gòu)樹的深度大于h，則從樹的頂點截取深度為h的子樹作為所需的塊結(jié)構(gòu)樹，因此可以實現(xiàn)對不同區(qū)域內(nèi)不同分塊粒度的要求。根據(jù)上述迭代的分割算法，能夠得到此網(wǎng)頁基于視覺特征所建立的最終內(nèi)容結(jié)構(gòu)圖。

2.3 候選關(guān)鍵詞提取

本文以WordNet作為語義詞典庫，利用基于視覺的頁面分割算法VIPS[2]進行頁面內(nèi)容分塊的預(yù)處理，從結(jié)果中取出動畫素材的上下文，然后與動畫名稱、頁面主題、URL、ALT屬性聯(lián)合組成候選術(shù)語集合，然后經(jīng)過文本過濾，利用本文提出的規(guī)則為每個候選術(shù)語分配權(quán)值，從中挑選關(guān)鍵字。

對每個候選術(shù)語，先按式(1)計算其分值。

其中，Wtag為術(shù)語的Html標簽權(quán)值；Wfam為WordNet為每個術(shù)語定義了“熟悉度“的權(quán)值，術(shù)語對人們越常見，分配權(quán)值越高；Wsort表示術(shù)語類別的重要程度，術(shù)語越特定，分配權(quán)值Wsort越高；Nlevel為記錄術(shù)語在WordNet的上下位關(guān)系樹中的層次數(shù)，Wlevel為其權(quán)重，層次越高，術(shù)語越特定，若種類不在層次內(nèi)，則不需計算。

根據(jù)上述分值，對每一幅動畫素材選取Top-N(這里設(shè)N=10)的候選關(guān)鍵字集，按照式(2)將分值轉(zhuǎn)換為關(guān)鍵字相對于動畫素材的權(quán)重，為后續(xù)的基于語義網(wǎng)絡(luò)的自動標注過程使用。

3 Web動畫素材視覺特征提取

3.1 視覺突出性的區(qū)域提取

本文采用Mean Shift[5]算法對動畫素材圖像進行分割，但可能包含一些“噪音塊”，因此我們采用多種視覺特征相綜合的顯著圖方法[6]進一步求精，其方法是將動畫素材圖像分解成相應(yīng)的一組圖像區(qū)域，然后采用顏色、紋理及形狀特征對分割后的區(qū)域進行描述。

3.2 視覺突出區(qū)域描述方式

本文采用主顏色描述子(dominant color descriptor)[7]作為每個區(qū)域的顏色特征。首先，采用顏色聚類算法獲得動畫素材區(qū)域的代表顏色，代表顏色和它所占的比例構(gòu)成了動畫素材區(qū)域的主顏色描述子F：

其中系數(shù)aij表示兩種顏色ci和cj間的相似性，即

這里，dij=‖ci-cj‖為顏色向量ci和cj之間的歐氏距離；dmax為將兩種顏色之間的最大距離。

對于紋理特征，本文采用的是同構(gòu)型紋理圖像描述子[8]。同構(gòu)型紋理圖像描述子(homogeneous texture descriptor, HTD)[9]由 62個數(shù)字組成，要根據(jù)圖像紋理的方向和大小提取底層特征。其中開頭兩個數(shù)字fCD、fSD分別代表圖像空間域中的平均值和標準差，其余則代表不同頻率的頻道上能量的平均值和標準差。同時將頻率域按照方向和半徑分割成了30個頻道。其描述子可定義為：

其中，ei和di分別表示第i個頻道中的能量平均值和能量標準差。經(jīng)由Gabor濾波器增強這些頻道上的能量后，用HTD就可以描述一幅圖像的紋理。同時將HTD1與HTD2之間的紋理距離定義為式(7)。

利用Dt(HTD1,HTD2)測量它們的相似度，其中i為整數(shù)，范圍為1～62；a(i)是正規(guī)化參數(shù)，設(shè)a(i)=1。

針對于形狀特征，此處分別采用區(qū)域面積、離心率(Eccentricity)以及方向作為動畫素材區(qū)域的形狀特征[10]，其中，區(qū)域R的離心率CR定義為區(qū)域主軸與次軸之比，區(qū)域的方向則由區(qū)域R的中心矩確定。

這里，μp,q為區(qū)域R的第p+q階中心矩，則區(qū)域R1和R2之間的形狀相似性定義為：

在確定了區(qū)域間的顏色、紋理及形狀相似性判別之后，可將兩個區(qū)域間的集成相似性測度定義為：

其中，α、β和δ是它們的權(quán)重，且α+β+δ=1。

4 Web動畫素材語義標注

4.1 基于視覺相關(guān)的標注字過濾算法

從網(wǎng)頁上自動提取的描述動畫素材的一些關(guān)鍵字，可能與動畫素材的語義內(nèi)容無關(guān)或相關(guān)程度較低；同時由于語義鴻溝的存在，導致視覺相似的動畫素材無法保證語義內(nèi)容的一致性。但動畫素材的視覺特征和標注字之間具有良好的信息互補性，因此，本文利用視覺特征與標注字之間的相關(guān)性，根據(jù)視覺特征對自動提取的Web標注字描述方式進行過濾。

本文采取EMD(Earth Mover’s Distance)相似性測量[11]計算動畫素材間的視覺相似性，它廣泛應(yīng)用于線性規(guī)劃中的運輸問題，即尋找一個滿足消費者需求的最小運輸成本的貨物流量，由此可得到基于 EMD 相似度測量的公式為式(11)。

其中，d(r1,r2)為供應(yīng)者與消費者之間的單位運輸成本，作為素材R1的區(qū)域特征ri與素材R2的區(qū)域特征rj之間的相似性距離；fij為貨物的流量，可作為素材的區(qū)域面積。

而對于文本標注的過濾，則采取一種信度傳播的方式，將每幅動畫素材自動提取的標注字向其視覺鄰近的動畫素材傳播，根據(jù)鄰近動畫素材間的視覺相似程度決定信息傳播量，并按照發(fā)送者和接受者標注字間的相關(guān)性進行主動接收信息，因此避免視覺相似而語義不相關(guān)的動畫素材之間的信息干擾。

若傳播動畫素材A所傳送的每個標注字為wA，則接收者Q所接收到的wA的信息量為式(12)所示。

其中rel代表標注字之間的相關(guān)性，在此本文采用基于WordNet語義網(wǎng)絡(luò)中的詞匯相似性來計算，N代表接收動畫素材Q中的標注字個數(shù)。

基于視覺相關(guān)的標注字過濾算法[12]可歸納如下：

Step 1 算法初始化： 設(shè)置視覺最近鄰個數(shù)k=100。

Step 2 對每幅動畫l，采用EMD距離計算它的k個視覺最近鄰，形成一組以動畫l為中心的視覺聚類Cl。

Step 3 將視覺聚類Cl中的每個動畫的標注字wk，向聚類中心待標注動畫l傳播，傳播的信息量用wk的權(quán)值來表示。

Step 4 對待標注接收動畫l，按照與自身標注的相關(guān)程度，接收動畫k發(fā)送的標注字信息，并將動畫原有標注字和接收到標注字合并，通過WordNet歸并同義標注字，選擇同義詞中較大權(quán)值作為歸并后的標注字權(quán)值；按權(quán)值統(tǒng)一排序，維持標注字個數(shù)不變，排除權(quán)值較低的標注字，并對標注字權(quán)值重新歸一化。

Step 5k=k+1，判斷k是否<100，是則轉(zhuǎn)Step 3，否則退出循環(huán)。

4.2 動畫素材的語義標注

利用標注與視覺特征的相關(guān)性，能夠獲得比較合理的標注字描述。對于查詢，則采用方便用戶使用的關(guān)鍵字查詢方式。為了提高檢索的速度，同時為了提高查全率，避免缺少標注的動畫素材被漏檢，本文采用概率潛在語義分析(PLSA)方法[13]將自動提取的WEB動畫素材的標注信息轉(zhuǎn)換到一個低維的潛在的語義空間zk∈{z1,z2,z3,…,zk}。

對于圖像Ij與標注字wi的聯(lián)合概率表示為：

其中，p(wi|Ij)表示對于任意一幅圖像Ij中標注字wi出現(xiàn)的條件概率：

PLSA算法中，潛在變量的估計常使用的是最大似然估計法EM算法。E步驟計算隱含變量的后驗概率：

M步驟對完全數(shù)據(jù)的似然函數(shù)極值化：

經(jīng)E步驟和M步驟的迭代后，滿足收斂條件時終止。

為了提高結(jié)果的可靠性，實際運算中本文采用了Tempered EM算法[14]。

對于用戶給出的查詢關(guān)鍵字wquery，將其投影到隱含語義空間：

然后采用公式(19)來判別wquery與自動提取的標注圖像Ii之間的相似程度[15]：

5 實驗結(jié)果

本文使用網(wǎng)絡(luò)爬蟲程序從50多個有代表性的動畫網(wǎng)站上一共收集了5 000多幅Web動畫素材圖像作為測試數(shù)據(jù)以驗證本文提出算法的有效性。測試數(shù)據(jù)集包含海灘、樓房、汽車、白云、花、山、樹和鳥，并且以上8類動畫素材每類不少于100個。實驗中，首先分別采用基于文本和融合文本與視覺特征的標注對這些素材進行語義標注，然后通過查準率來衡量不同標注方式下的檢索的效果。為了便于計算，每次查詢通過統(tǒng)計返回結(jié)果中前100幅圖像中的相關(guān)圖像來計算查準率。表1 給出了8類動畫素材的查準率對比。

表1 動畫素材標注查準率比較

續(xù)表

標注方式素材類 基于文本特征標注融合文本和視覺特征標注白云0.580.73花 0.620.83山 0.560.75樹 0.440.65鳥 0.480.69平均查準率0.5750.74

圖1是查準率對比實驗結(jié)果。

圖1 動畫素材標注查準率比較結(jié)果

根據(jù)以上的查準率對比實驗結(jié)果可以看出，采用融合文本和視覺特征的標注方法比只使用Web文本標注的查準率提高了16.5%，有效地提高了Web動畫素材標注的準確率。

6 結(jié)論

本文首先自動抽取Web動畫素材上下文信息，結(jié)合素材的名稱、頁面主題、URL、ALT等屬性組成特征集，以WordNet作為語義詞典庫，提取文本特征；接著采用顯著圖方法提取視覺突出性的區(qū)域；然后利用視覺特征與標注字之間的相關(guān)性，對自動提取的標注字進行過濾，最后采取PLSA方法實現(xiàn)了對Web動畫素材進行自動標注。文本提出的Web動畫素材自動標注方法易于對缺少標注的動畫素材進行自動標注和文本檢索，增強了標注的可靠性，同時便于對動畫素材進行組織、管理，提高了檢索效率和質(zhì)量。

[1] C H Wang，L Zhang. Learning to Reduce the Semantic Gap in Web Image Retrieval and Annotation[C]//Proceedings of the SIGIR’08, Singapore. 2008,7.

[2] Deng Cai, Shipeng YU, Ji-rong Wen, et al. Extracting content structure for Web pages based on visual representation[C]//Proceedings of the 5th AsianPaci-fic Web Conference(AP Web). London: Springer-Verlag. 2003:406-417.

[3] 王琦,唐世渭,楊冬青,王騰蛟. 基于DOM的網(wǎng)頁主題信息自動提取.計算機研究與發(fā)展[J].2004,41(10):1786-1792.

[4] 高琰,谷士文,譚立球. 基于多種策略的頁面內(nèi)容提取算法.西南交通大學學報[J]. 2007,42(4):473-477.

[5] 陳兆學,趙曉靜,聶生.Mean shift 方法在圖像處理中的研與應(yīng)用. 中國醫(yī)學物理學[J].2010,27(6):2244-2249.

[6] L Itti, C Koch, E Niebur. A Model of Saliency-based Visual Attention for Rapid Scene Analysis[C]//Proceedings of the IEEE Trans. on Pattern Analysis and Machine Intelligence. 1998:1254-1259.

[7] H Shao, Y S Wu, W C Cui, et al. Image Retrieval Based on MPEG-7 Dominant Color Descriptor[C]//Proceedings of the 9th International Conference for Young Computer Scientists. 2008:753-757.

[8] 李偉,王樹梅,王玲. 基于內(nèi)容的電影動畫素材檢索. 計算機工程[J]. 2007,33(12):222-230.

[9] Lumini A, Maio D. A Wavelet-based Image Watermarking Scheme[C]//Proceedings of Intel. Conf. on Information Tech.: Coding and Computing. 2000: 122-127.

[10] 向友君，謝勝利. 圖像檢索技術(shù)綜述. 重慶郵電學院學報(自然科學版)[J].2006,18(3):348-354.

[11] 邰曉英, 吳成玉, 趙杰煜. 基于平均值位移聚類與 EMD 測量的圖像檢索. 電路與系統(tǒng)學報[J].2007,12(1):62-67.

[12] 邱兆文. 面向用戶的Web圖像檢索關(guān)鍵技術(shù)研究[D].哈爾濱工業(yè)大學博士學位論文.2009.

[13] H Thomas. Probabilistic Latent Semantic Indexing[C]//Proceedings of the Twenty-Second Annual International SIGIR Conference on Research and Development in Information Retrieval (SIGIR-99). 1999.

[14] T. Hofmann. Unsupervised Learning by Probabilistic Latent Semantic Analysis. Machine Learning[J]. 2001,42 (1):177-196.

[15] Girolami, M. On an equivalence between PLSI and LDA[C]//Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York, NY,USA: ACM Press, 2003:433-434.