基于貝葉斯學習的視頻檢索相關反饋算法設計

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

關鍵詞： 視頻檢索；相關反饋；貝葉斯學習

中圖分類號：TN911.73; TP391.41文獻標志碼：A

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

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

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

該領域中人們做了很多工作[5~7]，取得了顯著的成績。

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

1視頻檢索中的貝葉斯相關反饋算法設計

1．1檢索框架

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

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

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

(1)

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

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

1．2概率更新過程

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

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

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

a）對于給定的檢索目標Ω，利用NFL計算視頻庫中每個鏡頭Sr與Ω的相似度并轉換為初始目標概率P1r。

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

c）用戶如果對檢索結果滿意，則本次檢索結束；否則，用戶對顯示的結果進行標記。

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

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

2實驗結果

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

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

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

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

3結束語

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

參考文獻：

[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]曹建榮，蔡安妮. 基于相關反饋的視頻檢索算法[J]. 吉林大學學報:自然科學版， 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)， 李子青，等. 基于關鍵幀提取的最近特征線 (NFL) 聚類算法的鏡頭檢索方法 [J]. 計算機學報，2000，23(12):12921298.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”