基于貝葉斯學(xué)習(xí)的視頻檢索相關(guān)反饋算法設(shè)計(jì)

摘要：針對(duì)信息檢索中如何提高檢索的精度問題，提出了一個(gè)基于相關(guān)反饋的視頻檢索算法。使用概率框架來描述檢索問題，并根據(jù)貝葉斯學(xué)習(xí)按照用戶的行為來更新概率分布，實(shí)現(xiàn)自動(dòng)相關(guān)反饋，提高了檢索精度。實(shí)驗(yàn)表明，用該算法檢索的準(zhǔn)確度比基于最近鄰特征線（NFL）的視頻檢索方法有明顯提高。

關(guān)鍵詞： 視頻檢索；相關(guān)反饋；貝葉斯學(xué)習(xí)

中圖分類號(hào)：TN911.73; TP391.41文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2008)03－0934－02

基于內(nèi)容的視頻檢索是目前多媒體信息技術(shù)的研究熱點(diǎn)。由于計(jì)算機(jī)自動(dòng)抽取的視覺低級(jí)特征與人們所理解的語義之間存在巨大的差距，其檢索結(jié)果往往難以令人滿意，通常使用相關(guān)反饋技術(shù)來彌補(bǔ)這個(gè)差距，提高檢索精度。相關(guān)反饋在信息檢索中是一種指導(dǎo)性學(xué)習(xí)技術(shù)，用于提高系統(tǒng)的檢索能力。相關(guān)反饋方法的基本思路是在檢索過程中，允許用戶對(duì)檢索結(jié)果進(jìn)行評(píng)價(jià)和標(biāo)記，指出結(jié)果中哪些查詢是與查詢圖像相關(guān)的，哪些是無關(guān)的；然后將用戶標(biāo)記的相關(guān)信息作為訓(xùn)練樣本反饋給系統(tǒng)進(jìn)行學(xué)習(xí)，指導(dǎo)下一輪檢索，從而使得檢索結(jié)果更符合用戶的需求。相關(guān)反饋技術(shù)最早用于文檔檢索系統(tǒng)中[1]，之后在基于內(nèi)容的圖像檢索中得到廣泛應(yīng)用[2~6]。近年來也在基于內(nèi)容的視頻檢索中得到應(yīng)用[7~10]。

基于貝葉斯理論的相關(guān)反饋算法根據(jù)用戶的反饋信息進(jìn)行統(tǒng)計(jì)推算，用概率框架來描述檢索問題，與其他一些方法相比[1~4， 8~10]，基于概率統(tǒng)計(jì)的貝葉斯學(xué)習(xí)相關(guān)反饋算法在基于內(nèi)容的信息檢索任務(wù)中表現(xiàn)得更加突出一些。在

該領(lǐng)域中人們做了很多工作[5~7]，取得了顯著的成績(jī)。

Cox等人[5]首先把這一理論用于圖像檢索系統(tǒng)，根據(jù)在給定用戶目標(biāo)圖像的情況下用戶在交互中的行為模型，通過對(duì)當(dāng)前用戶行為的觀察，利用貝葉斯學(xué)習(xí)來預(yù)測(cè)目標(biāo)圖像，并利用貝葉斯框架試圖用熵估計(jì)來最小化反饋迭代的次數(shù)以進(jìn)行目標(biāo)搜尋。Vasconcelos等人[6]將特征分布看成一個(gè)高斯混合模型并用貝葉斯推理在一次檢索過程的迭代反饋中進(jìn)行學(xué)習(xí)。其特征分布模型支持區(qū)域匹配。該方法的潛在問題是計(jì)算效率問題和導(dǎo)致太多參數(shù)需要用極其有限的樣例進(jìn)行估計(jì)的復(fù)雜數(shù)據(jù)模型。文獻(xiàn)[7]利用距離確定初始鏡頭之間的相似度定義關(guān)聯(lián)矩陣，以確定不同鏡頭之間的關(guān)聯(lián)；然后利用貝葉斯公式來根據(jù)用戶的標(biāo)記更新目標(biāo)概率，并采用提升采樣來選擇下一次迭代顯示給用戶的目標(biāo)集合。該方法僅采用每一個(gè)鏡頭的第一幀作為關(guān)鍵幀。

1視頻檢索中的貝葉斯相關(guān)反饋算法設(shè)計(jì)

1．1檢索框架

本節(jié)給出相關(guān)反饋算法貝葉斯框架的總體描述。用戶通過一系列顯示和動(dòng)作在數(shù)據(jù)庫中尋找一個(gè)特殊的數(shù)據(jù)項(xiàng)。

記視頻庫為VS=S1，…，Sn，Sr為視頻庫中任意一個(gè)鏡頭，檢索目標(biāo)為Ω，假設(shè)本次檢索已進(jìn)行了t輪反饋，并且t輪反饋記錄為Ht={R0，A1，R1，A2，R2，…，At，Rt}。其中：Ri是第i輪系統(tǒng)的檢索結(jié)果顯示；Ai是用戶在第i輪做出的動(dòng)作，即對(duì)Ri中的鏡頭作出的語義相關(guān)性判斷。

系統(tǒng)通過貝葉斯公式，根據(jù)式(1)增量地計(jì)算概率為

(1)

其中：P(Sr=Ω|Ht)為目標(biāo)概率，它反映了當(dāng)前檢索的反饋記錄是Ht、檢索目標(biāo)鏡頭是Sr的概率。系統(tǒng)根據(jù)目標(biāo)概率的分布，從視頻庫中選擇目標(biāo)概率最大的一組鏡頭，生成輸出結(jié)果顯示給用戶。系統(tǒng)合理地將相關(guān)反饋引入到檢索模型中，根據(jù)用戶做出的動(dòng)作來調(diào)整目標(biāo)概率。

算法保持?jǐn)?shù)據(jù)庫中數(shù)據(jù)是搜索目標(biāo)概率的當(dāng)前分布。每次迭代，前N個(gè)概率最大的鏡頭被選擇用來顯示給用戶，而用戶的動(dòng)作則用來更新概率分布。用歸一化后的最近鄰特征線方法（NFL）[11]得到的相似性來初始化開始概率分布。

1．2概率更新過程

視頻庫中每個(gè)鏡頭Sr是目標(biāo)鏡頭Ω的概率隨著用戶標(biāo)記和反饋的進(jìn)行不斷更新。由式（1），目標(biāo)概率P(Sr=Ω|Ht)的計(jì)算轉(zhuǎn)換為概率P(At|Sr=Ω，Rt，Ht-1）的計(jì)算。概率P(At|Sr=Ω，Rt，Ht-1)一般稱為用戶模式，它根據(jù)給定前一輪反饋歷史Ht-1、第t輪顯示給用戶的檢索結(jié)果Rt及假定Sr為檢索目標(biāo)Ω時(shí)預(yù)測(cè)用戶的行為。

在顯示給用戶的鏡頭集合R中，用集合Q={Xq1，Xq2，…，XqK}表示被用戶標(biāo)記的鏡頭集；D={Xd1，Xd2，…，XdL}表示未標(biāo)記集合。顯然，D=R-Q。對(duì)于視頻庫中的鏡頭Sr，如果Sr與Q更接近， Sr是檢索目標(biāo)的可能性就會(huì)更大一些；反之，如果與D相似，則是檢索目標(biāo)的可能性就會(huì)變小。本文使用文獻(xiàn)[11]給出的最近鄰線性方法來計(jì)算Sr與集合Q和D中的鏡頭之間的相似性Dist(Sr，Xqi)及Dist(Sr，Xdj)。

由以上分析可知，根據(jù)貝葉斯公式，視頻庫中每一個(gè)鏡頭Sr的目標(biāo)概率更新步驟如下：

a）對(duì)于給定的檢索目標(biāo)Ω，利用NFL計(jì)算視頻庫中每個(gè)鏡頭Sr與Ω的相似度并轉(zhuǎn)換為初始目標(biāo)概率P1r。

b）根據(jù)Ptr從大到小對(duì)VS排序，取概率最大的前N個(gè)鏡頭構(gòu)成Rt顯示給用戶。

c）用戶如果對(duì)檢索結(jié)果滿意，則本次檢索結(jié)束；否則，用戶對(duì)顯示的結(jié)果進(jìn)行標(biāo)記。

d）根據(jù)用戶的標(biāo)記計(jì)算似然函數(shù)P(At|Sr=Ω，Rt，Ht-1）。

e）根據(jù)式（1）計(jì)算Pt+1r，t=t+1轉(zhuǎn)b）。

2實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)數(shù)據(jù)是從國(guó)際影視檢索測(cè)評(píng)（TREC video retrieval evaluation， TRECVID）提供的CNN headline news和ABC world news tonight視頻中隨機(jī)選取的幾個(gè)視頻段，建立一個(gè)包含2 060個(gè)鏡頭的視頻庫。這幾段視頻內(nèi)容非常豐富，有人物、事件、體育和影視等各方面的新聞內(nèi)容。本實(shí)驗(yàn)選了五個(gè)語義類作為查詢鏡頭，它們是新聞片頭、新聞播音員、籃球、體育新聞片頭、一段電影片段，如圖1所示。對(duì)每個(gè)查詢鏡頭主觀地選取一組視覺相似的鏡頭作為標(biāo)準(zhǔn)。

實(shí)驗(yàn)使用關(guān)鍵幀在HSV上的72個(gè)分量作為顏色特征值，具體做法是將H、S、V等三個(gè)分量按照人的顏色感知進(jìn)行9:3:1的比例非等間隔量化，把量化后的三個(gè)顏色分量合成一個(gè)72位的一維特征矢量。用NFL方法來度量?jī)蓚€(gè)鏡頭間的相似性。圖2給出了實(shí)驗(yàn)算法的用戶界面。上面一行是查詢視頻鏡頭，顯示當(dāng)前的查詢目標(biāo)Ω；下面是查詢結(jié)果區(qū)域。如果用戶認(rèn)為哪一個(gè)鏡頭是相似的，就可以用鼠標(biāo)單擊多選框選中該鏡頭，然后單擊“GO”按鈕，系統(tǒng)根據(jù)用戶的標(biāo)記更新庫中鏡頭的目標(biāo)概率，選擇概率最大的前九個(gè)顯示給用戶；如果用戶找到滿意的檢索結(jié)果單擊“FOUND”按鈕就可以終止這次查詢。

查準(zhǔn)率(precision)和查全率(recall)是視頻檢索中常用的兩個(gè)評(píng)價(jià)指標(biāo)。查準(zhǔn)率用檢索到的與主觀標(biāo)準(zhǔn)相符的鏡頭數(shù)與所有檢索到的鏡頭數(shù)比值進(jìn)行衡量；查全率用檢索到的與主觀標(biāo)準(zhǔn)相符的鏡頭數(shù)與主觀選取所有鏡頭數(shù)比值進(jìn)行衡量。圖3給出了這五個(gè)目標(biāo)類在未使用相關(guān)反饋時(shí)根據(jù)NFL方法查詢與五次相關(guān)反饋后的precisionrecall曲線。

從圖3可以看出，使用本文給出的相關(guān)反饋算法后，曲線下面的面積有了明顯的增加，隨著recall的增加，precision下降的速度變慢，取得了更好的檢索效果，證明了利用相關(guān)反饋來彌補(bǔ)語義鴻溝的有效性。另外，在CPU 3 GHz、3 GB內(nèi)存的DELL PWS630電腦上執(zhí)行一次反饋的時(shí)間僅為5.6 s，對(duì)于2 060個(gè)鏡頭的視頻庫來說，這個(gè)速度還是比較快的，用戶還是能夠接受的。當(dāng)然，也可以在一個(gè)鏡頭內(nèi)取更多的關(guān)鍵幀，選擇更多的特征來表示關(guān)鍵幀，與此同時(shí)也會(huì)帶來檢索時(shí)間的增加。

3結(jié)束語

本文給出了一種基于貝葉斯學(xué)習(xí)的視頻相關(guān)反饋算法，使用貝葉斯學(xué)習(xí)方法來預(yù)測(cè)視頻庫中任一個(gè)鏡頭檢索目標(biāo)的概率，在反饋過程中不需要修改查詢，系統(tǒng)根據(jù)反饋?zhàn)詣?dòng)更新目標(biāo)鏡頭的分布。實(shí)驗(yàn)結(jié)果表明，該方法能夠有效地提高檢索性能，消除圖像低級(jí)特征與用戶理解之間的語義鴻溝。

參考文獻(xiàn)：

[1]LKNSON R W， HNGSTON P. Using the cosine measure in a neural network for document retrieval[C]//Proc of ACM SIGIR Conference on Research and Development in Information Retrieval. Chicago：[s.n.]， 1991:202－210.

[2]YONG R. Relevance feedback: a power tool for interactive contentbased image retrieval[J]. IEEE Trans on Circuits and Systems for Video Technology， 1998，8(5):644－655.

[3]RUI Y， HUANG T S， MEHROTRA S. Contentbased image retrieval with relevance feedback in MARS[C]//Proc of International Confe￣rence on Image Processing. 1997:815－818.

[4]ISHIKAWA Y， SUBRAMANYA R， FALOUTSOS C. Mindreader: query databases through multiple examples[C]//Proc of the 24th VLDB Conference. New York:[s.n.]， 1998:218－227.

[5]COX I J， MILLER M L， MINKA T P， et al. The Bayesian image retrieval system， PicHunter: theory， implementation， and psychophysical experiments[J]. IEEE Trans on Image Processing， 2000，9(1):20－37. [6]VASCONCELOS N， LIPPMAN A. Bayesian relevance feedback for contentbased image retrieval[C]//Proc of IEEE Workshop on Contentbased Access of Image and Video Libraries: 2000.

[7]BOLDAREVA L， HIEMSTRA D. Interactive retrieval of video using precomputed shotshot similarities[J]. IEEE Proc of Vision， Ima￣ge and Signal Processing， 2005，152(6):919－926.

[8]MUNESAWANG P， LING G. Adaptive video indexing and automa￣tic/semiautomatic relevance feedback[J]. IEEE Trans on Circuits and Systems for Video Technology， 2005，15(8):10321046.

[9]曹建榮，蔡安妮. 基于相關(guān)反饋的視頻檢索算法[J]. 吉林大學(xué)學(xué)報(bào):自然科學(xué)版， 2006， 24(2):138143.

[10] LAVRENKO V， FENG S L， MANMATHA R. Statistical models for automatic video annotation and retrieval[C]//Proc of IEEE Confe￣rence on Acoustics， Speech， and Signal. Montreal:[s.n.]， 2004:10441047.

[11] 趙黎， 祁衛(wèi)， 李子青，等. 基于關(guān)鍵幀提取的最近特征線 (NFL) 聚類算法的鏡頭檢索方法 [J]. 計(jì)算機(jī)學(xué)報(bào)，2000，23(12):12921298.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”