基于概念的視頻檢索中概念語(yǔ)義匹配算法研究

張皓翔，尚麟宇

(北京交通大學(xué)軌道交通控制與安全國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100044)

為了實(shí)現(xiàn)基于概念視頻檢索中從底層內(nèi)容到查詢的語(yǔ)義貫通，應(yīng)用基于WordNet詞典的語(yǔ)義相似度算法，通過(guò)對(duì)三種不同原理的算法對(duì)比應(yīng)用，得出基于信息量算法在本應(yīng)用中更有優(yōu)勢(shì)，語(yǔ)義匹配可以提高檢索精度，最優(yōu)映射數(shù)目為2至3個(gè)，以及在目前發(fā)展水平下，映射到合適的概念比檢測(cè)器精度更合適四個(gè)重要結(jié)論.

語(yǔ)義視頻檢索;相似度算法;查詢預(yù)處理;概念檢測(cè)器過(guò)濾;映射數(shù)目

1 引言

統(tǒng)計(jì)顯示，著名的視頻共享網(wǎng)站YouTube每天新增6.5萬(wàn)部視頻，網(wǎng)絡(luò)視頻量在以驚人的速度增加.基于概念的視頻檢索技術(shù)不用人工標(biāo)注，直接根據(jù)視頻內(nèi)容建立中間語(yǔ)義概念進(jìn)行索引，滿足了應(yīng)用需求［1－3］.但是基于概念的視頻在底層特征到上層用戶查詢之間存在著語(yǔ)義鴻溝，如何跨越語(yǔ)義鴻溝，實(shí)現(xiàn)語(yǔ)義上的貫通，成為人們的研究熱點(diǎn)［1－2］.

在目前的發(fā)展水平上看，基于語(yǔ)義概念的視頻檢索包括概念檢測(cè)、查詢到概念的匹配和結(jié)果融合三個(gè)核心內(nèi)容［3］，其中概念檢測(cè)模塊實(shí)現(xiàn)了從視頻內(nèi)容到語(yǔ)義概念的語(yǔ)義鴻溝跨越，但查詢到概念的匹配通常采用布爾方法，即使是相似度計(jì)算也沒(méi)有涉及語(yǔ)義.這樣就導(dǎo)致了從查詢到底層特征的語(yǔ)義中斷.為了實(shí)現(xiàn)從查詢到底層內(nèi)容的語(yǔ)義貫通，引入基于WordNet詞典的語(yǔ)義相似度算法［4］，結(jié)合理論分析，對(duì)語(yǔ)義匹配進(jìn)行研究，得到了語(yǔ)義貫通會(huì)提高檢索精度，基于信息量的算法有優(yōu)勢(shì)，最優(yōu)匹配數(shù)目以及現(xiàn)有條件下，匹配概念數(shù)目比較重要的結(jié)論.

2 相關(guān)工作

在查詢到概念的映射模塊，根據(jù)使用的特征不同可以分為:基于文本特征的映射;基于視覺(jué)內(nèi)容的映射［5］等.在本文的實(shí)驗(yàn)中沒(méi)有用到樣例查詢，只是對(duì)查詢主題的文本描述，所以本文研究是基于文本特征的映射.基于文本的映射主要包括兩步:

第一步是查詢和概念的預(yù)先處理，如詞根化，去除停用詞，高頻詞，并進(jìn)行相應(yīng)的格式變換.第二步是映射.可以通過(guò)判斷查詢中是否包含概念描述中的詞，來(lái)確定查詢是否匹配到該概念，完成布爾匹配.或者通過(guò)一些相似度計(jì)算方法實(shí)現(xiàn)軟匹配［6］，如基于向量空間模型的相似度計(jì)算［3］語(yǔ)言模型［4］等.但是這些研究都沒(méi)有涉及語(yǔ)義的層面，如“person”和“car”從詞形或者詞義上看都沒(méi)有關(guān)系，語(yǔ)義上卻有相關(guān)性，因?yàn)槿粘Ｉ钪?，人?jīng)常是需要車作為代步工具的，這用布爾匹配或者向量空間模型是無(wú)法表示的.

WordNet語(yǔ)義詞典是由Princeton大學(xué)研制出的聯(lián)機(jī)英語(yǔ)詞匯檢索系統(tǒng)，根據(jù)詞義而不是詞形來(lái)組織單詞.基于這種詞典結(jié)構(gòu)有很多種算法，文獻(xiàn)［5，7，8］計(jì)算兩個(gè)單詞之間的相似度，［9］根據(jù)上下文建立向量計(jì)算形似度，［11］根據(jù)詞典的路徑長(zhǎng)度計(jì)算相似度，［6］根據(jù)信息量計(jì)算相似度.另外在查詢到概念映射模塊，［9］只選擇最優(yōu)的一個(gè)概念，［10－11］的概念檢測(cè)器集合比較小，都沒(méi)有涉及檢測(cè)器精度過(guò)濾這樣的問(wèn)題.

在本論文中，第3部分介紹用到的語(yǔ)義相似度算法，以及概念檢測(cè)器過(guò)濾方法.第4部分介紹對(duì)概念視頻檢索實(shí)現(xiàn)語(yǔ)義貫通的實(shí)驗(yàn)，包括要解決最優(yōu)映射數(shù)目和概念檢測(cè)器過(guò)濾問(wèn)題，最后是結(jié)論和進(jìn)一步的工作.

3 語(yǔ)義匹配方法

WordNet核心組織原則是由同義詞集合組成上下位關(guān)系，將單詞由詞形組織轉(zhuǎn)化為語(yǔ)義組織.基于WordNet的語(yǔ)義相似度算法有三種原理.

3.1 基于路徑長(zhǎng)度的算法

針對(duì)WordNet的詞典結(jié)構(gòu)，很直觀的計(jì)算相似度的方法是計(jì)算兩個(gè)單詞之間的路徑長(zhǎng)度.比如說(shuō)要計(jì)算nickel和credit card的相似度，從結(jié)構(gòu)樹的分支nickel往上尋找到第一個(gè)同時(shí)包含這兩個(gè)單詞的概念，Medium of Exchange，從這個(gè)單詞向下找到另外一個(gè)分支Credit Card，共有七步，可以據(jù)此得到兩個(gè)單詞的相似度.WUP和LCH是基于路徑長(zhǎng)度的算法.

3.2 基于信息量的算法

基于信息量的算法RES，JCN是根據(jù)單詞在訓(xùn)練語(yǔ)料中的出現(xiàn)頻率計(jì)算熵值得到相似度.

RES算法公式如下:

JCN算法公式如下:

公式中的I表示熵值，即信息量.詞典中單詞的出現(xiàn)頻率是從Brown Corpus of American English(100萬(wàn)個(gè)單詞，涵蓋新聞、自然科學(xué)領(lǐng)域等)語(yǔ)料庫(kù)訓(xùn)練得到的.

3.3 基于二次共現(xiàn)信息的算法

基于二次共現(xiàn)信息的算法VECTORE和LESK是根據(jù)Harris的分布假設(shè)理論提出，分布假設(shè)理論指語(yǔ)義相似的詞在同一語(yǔ)言文本中共同出現(xiàn)的概率相比于沒(méi)有語(yǔ)義關(guān)系的詞更大.因此根據(jù)詞典中單詞的注釋信息建立二次共現(xiàn)上下文向量，計(jì)算兩個(gè)單詞向量空間的夾角余弦得到相似度.

這三種原理的方法都是基于WordNet語(yǔ)義詞典，因此計(jì)算得到的是語(yǔ)義相似度.將其應(yīng)用到基于內(nèi)容的視頻檢索中，可以實(shí)現(xiàn)查詢到中間概念的語(yǔ)義匹配.

3.4 概念檢測(cè)器過(guò)濾方法

對(duì)每個(gè)概念檢測(cè)器計(jì)算其可信度，公式如下，SHLF_i表示鏡頭S在第i個(gè)概念檢測(cè)器中的產(chǎn)生概率，系統(tǒng)中我們?cè)O(shè)η=0.1，那么概念檢測(cè)器K的可信度計(jì)算公式如下:

為了最大化這些概念檢測(cè)器的精度，從TRECVID2007HLF任務(wù)中選擇最優(yōu)的6個(gè)結(jié)果進(jìn)行融合.取列表中的前500個(gè)鏡頭，根據(jù)每個(gè)鏡頭在提交列表中的位置信息按如下公式計(jì)算:

其中Contains(Sij)表示列表j中是否包含鏡頭Si.maxPos表示列表里最大的排序數(shù)，這里為500. Pos(Sij)表示鏡頭Si在列表j中的排序.公式的前半部分表示有多少個(gè)列表中包含鏡頭Si，后半部分進(jìn)一步描述鏡頭Si在這些列表中的重要程度.

4 實(shí)驗(yàn)

基于語(yǔ)義概念的視頻檢索包括概念檢測(cè)、查詢到概念的匹配和結(jié)果融合三個(gè)核心內(nèi)容，如下圖1所示.

圖1 基于概念的視頻檢索框架圖

在底層內(nèi)容到中間語(yǔ)義概念模塊，采用香港城市大學(xué)訓(xùn)練的374個(gè)LSCOM基于局部描述子的概念檢測(cè)器，用SVM支持向量機(jī)方法訓(xùn)練得到.在結(jié)果融合模塊，工作是把多個(gè)排序結(jié)果融合為一個(gè)，即最終的視頻檢索結(jié)果.可以采用1∶1的系數(shù)進(jìn)行融合［5］，在本實(shí)驗(yàn)中，采用有權(quán)重的融合方法.

實(shí)現(xiàn)語(yǔ)義的貫通，需要跨越查詢和中間概念的語(yǔ)義鴻溝.在這個(gè)模塊，采用國(guó)際檢索會(huì)議TRECVID2007年的24個(gè)查詢主題，應(yīng)用語(yǔ)義相似度算法后，應(yīng)該得到如表1所示的結(jié)果.

其中“0197”到“0220”是TRECVID2007年的24個(gè)查詢主題編號(hào)，“Actor”到“Yasser_Arafat”是香港城市大學(xué)訓(xùn)練的374個(gè)概念.

將三種原理的六種語(yǔ)義相似度算法分別進(jìn)行計(jì)算得到如表所示的結(jié)果，來(lái)驗(yàn)證信息量算法在基于內(nèi)容視頻檢索上的優(yōu)勢(shì).

表1 相似度比較結(jié)果示意圖

根據(jù)不同的語(yǔ)義相似度算法得到24個(gè)主題的檢索結(jié)果，用Trecvid評(píng)測(cè)工具對(duì)結(jié)果進(jìn)行評(píng)測(cè).

4.1 最優(yōu)映射數(shù)目實(shí)驗(yàn)

同布爾映射不同的是，語(yǔ)義匹配的結(jié)果經(jīng)過(guò)歸一化和排序之后，需要選擇一定數(shù)目的概念，數(shù)目不同對(duì)結(jié)果的影響也不同.如果選擇的概念數(shù)目少，會(huì)丟失查詢主題信息的可能;如果選擇的概念數(shù)目多，會(huì)造成混入噪聲的可能.

對(duì)每個(gè)算法的每個(gè)主題選擇2～5個(gè)概念進(jìn)行實(shí)驗(yàn)，如對(duì)WUP算法計(jì)算出來(lái)的查詢和概念的相似度，選擇前2個(gè)概念融合結(jié)果，計(jì)算24個(gè)查詢主題的平均MAP值，再選擇三個(gè)概念和四個(gè)概念，分別計(jì)算平均MAP值，將三個(gè)值進(jìn)行比較，得到的最好結(jié)果對(duì)應(yīng)的映射概念數(shù)目視為最優(yōu).

圖2 最優(yōu)映射概念數(shù)目實(shí)驗(yàn)結(jié)果

圖2中的橫軸代表六種算法，每種算法的直方圖從左到右依次代表映射2到5個(gè)概念，縱軸代表映射精度，即平均MAP值.從實(shí)驗(yàn)結(jié)果來(lái)看，除了JCN算法的最優(yōu)映射數(shù)目為3個(gè)，其它的算法映射兩個(gè)概念得到最好的結(jié)果，隨著映射概念數(shù)目的增多，融合效果會(huì)變差，所以最優(yōu)的映射個(gè)數(shù)是2～3個(gè).

4.2 算法應(yīng)用結(jié)果比較

將語(yǔ)義相似度算法應(yīng)用到基于概念的視頻檢索中，根據(jù)實(shí)驗(yàn)數(shù)據(jù)，對(duì)不同原理的語(yǔ)義匹配效果進(jìn)行分析.

表2是各個(gè)算法的MAP值:(映射概念數(shù)目2個(gè)到3個(gè)的結(jié)果算術(shù)平均)

表2 語(yǔ)義匹配效果

在視頻檢索中采用布爾匹配的映射方法，得到的檢索結(jié)果平均MAP值為0.0156，所以可以從表3中看出，上述六種語(yǔ)義算法的應(yīng)用相比于布爾匹配都可以提高檢索精度.

從圖2中可以看到，基于路徑長(zhǎng)度的算法LCH要優(yōu)于WUP，基于二次共現(xiàn)信息向量的算法VECTOR要優(yōu)于LESK，基于信息量的算法RES和JCN結(jié)果相當(dāng).將查詢主題映射到2個(gè)概念時(shí)，RES的應(yīng)用效果最好，將查詢主題映射到3個(gè)概念時(shí)，JCN的應(yīng)用效果最好.這兩種算法都是基于信息量的語(yǔ)義算法，所以基于信息量的算法在視頻檢索的語(yǔ)義匹配占有優(yōu)勢(shì).

而基于二次共現(xiàn)信息向量方法，由于對(duì)詞性沒(méi)有限制，應(yīng)該體現(xiàn)應(yīng)用優(yōu)勢(shì)，在這里可能是數(shù)據(jù)中的名詞居多，因此這兩種算法特有的優(yōu)勢(shì)沒(méi)有發(fā)揮出來(lái).

相比于前兩種原理的算法，基于信息量的相似度算法減少了詞典結(jié)構(gòu)不合理性對(duì)結(jié)果的影響，融入了人類語(yǔ)言中不同單詞出現(xiàn)的頻率對(duì)語(yǔ)義的作用，所以會(huì)更有優(yōu)勢(shì).

4.3 語(yǔ)義概念過(guò)濾

從查詢到中間概念的匹配采用語(yǔ)義匹配方法之后可以提高檢索的精度，并且用基于信息量的相似度算法為最好.但就目前的研究情況，關(guān)于語(yǔ)義匹配的一個(gè)問(wèn)題是概念訓(xùn)練數(shù)目不夠多并且精度不夠高.

美國(guó)CMU Alex G.Hauptmann領(lǐng)導(dǎo)的研究組得出人工語(yǔ)義概念研究的理論基礎(chǔ):(1)關(guān)于語(yǔ)義概念集的大小:用幾千個(gè)(＜5000)概念就能達(dá)到很高的檢索精度，并且每個(gè)概念的檢測(cè)精度不用太高(也不能低于MAP=10%)，可以達(dá)到和文本檢索相當(dāng)?shù)男Ч?MAP=65%).

從這個(gè)理論出發(fā)，目前比較成熟的概念檢測(cè)器如香港城市大學(xué)的374個(gè)LSCOM基于局部描述子的概念檢測(cè)器，相對(duì)于5000個(gè)概念，數(shù)目顯然很少，并且訓(xùn)練的概念精度也都不是很高，需要過(guò)濾.因此在語(yǔ)義匹配問(wèn)題上出現(xiàn)了選擇題:(1)映射到合適的概念，但有些概念檢測(cè)器的精度比較低;(2)映射到較少的概念，但是概念檢測(cè)器的精度較高.這兩種情況下的語(yǔ)義匹配結(jié)果是不同的.下面的實(shí)驗(yàn)驗(yàn)證了在目前的條件下，第一種情況的語(yǔ)義匹配結(jié)果更好.

結(jié)果按照精度從高到低的順序排序，選擇域值為1，得到187個(gè)概念進(jìn)行語(yǔ)義匹配實(shí)驗(yàn)，依次是六種算法映射到2～4個(gè)概念，得到最后的視頻檢索精度(平均MAP值)如表3所示:

表3 概念檢測(cè)器過(guò)濾實(shí)驗(yàn)結(jié)果

從表中可以看到，匹配概念數(shù)目為2的時(shí)候，只有三種方法的平均檢測(cè)精度上升，WUP、LCH和RES算法的檢測(cè)精度值甚至下降.主題映射到3個(gè)概念時(shí)，應(yīng)用效果有了明顯的下降.

所以在目前的研究水平上，映射到合適數(shù)目的概念比過(guò)濾檢測(cè)器精度效果更好.

5 結(jié)論和進(jìn)一步工作

通過(guò)以上的實(shí)驗(yàn)，我們得到如下的結(jié)論:

(1)在查詢到概念的匹配模塊，采用語(yǔ)義匹配方法會(huì)實(shí)現(xiàn)語(yǔ)義貫通，提高檢索精度，使得結(jié)果從平均MAP0.0156提高到0.02235(RES)，0.02145(JCN);

(2)基于WordNet的相似度算法中，基于信息量的算法減少了詞典結(jié)構(gòu)不合理性對(duì)結(jié)果的影響，融入了單詞頻率對(duì)語(yǔ)義的作用，因此更有優(yōu)勢(shì);

(3)語(yǔ)義匹配最優(yōu)映射概念數(shù)目為2～3個(gè).從實(shí)驗(yàn)分析，映射到一個(gè)概念的時(shí)候，會(huì)丟失查詢主題信息，映射到4個(gè)以上概念的時(shí)候，會(huì)引入誤匹配噪聲，對(duì)結(jié)果產(chǎn)生消極影響;

(4)在概念檢測(cè)器目前的發(fā)展水平上，將查詢主題匹配到合適數(shù)目的概念比映射精度較高的概念效果要好.結(jié)合4.3節(jié)理論分析，如果有5000個(gè)概念，即使精度比較低，也能得到滿意的結(jié)果，但是實(shí)驗(yàn)中用到的374個(gè)概念相對(duì)于5000概念，顯然比較少，所以單純提高檢測(cè)器精度并不能改善結(jié)果，大規(guī)模的訓(xùn)練語(yǔ)義概念應(yīng)該是今后發(fā)展的重點(diǎn).

本論文在基于概念的視頻檢索中實(shí)現(xiàn)了語(yǔ)義匹配，從查詢到底層內(nèi)容的語(yǔ)義實(shí)現(xiàn)了貫通，提高了檢索精度.下一步的工作是針對(duì)查詢和概念的零概率問(wèn)題，提出統(tǒng)計(jì)和規(guī)則相結(jié)合的查詢擴(kuò)展方法，用擴(kuò)展后的查詢進(jìn)行概念匹配，以期提高檢索精度.

［1］Han J，Ngan K N，LiMingjing，etal.Amemory learning framework for effective image retrieval［J］.IEEE Transactionson Image Processing，2005，14(4):511－524.

［2］魏維，游靜，劉鳳玉，許滿武.語(yǔ)義視頻檢索綜述［J］.計(jì)算機(jī)科學(xué)，2006，2(10).

［3］Pedersen T.，Patwardhan S.，Michelizzi J.Wordnet::similarity－measuring the relatedness of concepts［J］.In AAAI，2004，(9).

［4］D.Wang，X.Li，J.Li，B.Zhang.The importance ofquery－concept－mapping for automatic video retrieval［J］.In ACM Multimedia，2007，(11).

［5］劉群，李素建.基于《知網(wǎng)》的詞匯語(yǔ)義相似度計(jì)算［J］.中文計(jì)算語(yǔ)言學(xué)，2002，(7):59－76.

［6］X.Li，D.Wang，J.Li，B.Zhang.Video search in concept subspace:A text－like paradigm［J］.In Proc.of CIVR，2007，(8).

［7］Z.Wu，M.Palmer.Verb semantic and lexical selection［J］.In Annual Meeting of the ACL，1994，(12).

［8］Resnik P.Using information content to evaluate semantic similarity in a taxonomy［J］.In IJCAL，1995，(6).

［9］C.G.Snoek，B.Huurnink，L.Hollink，M.de Rijke，G.Schreiber，M.Working.Adding semantics to detectors for video retrieval［J］.IEEE transactions on Multimedia，2007，(11).

［10］A.Haubold，A.P.Natsev，M.R.Naphade.Semantic multimedia retrieval using lexical query expansion and model－based reranking［J］.In Proc.of ICME，2006，(5).

［11］M.G.Christel，A.G.Hauptmann.The use and utility of highlevel semantic feature extraction［J］.In Proc.of CIVR，2005，(7).