基于圖像聚類與挖掘的視頻摘要方法

陳 宏

（浙江廣播電視集團，浙江 杭州 310005）

1 視頻摘要的基本概念

視頻摘要技術，它的概念類似于文本摘要，即通過計算機自動處理技術，對視頻的內容和結構進行分析，并從原視頻內容中提取出用戶需要的信息，再做進一步處理。如果一個視頻摘要能夠做到盡量準確和充分，那么就能夠讓用戶在最短時間內獲得最關鍵的信息，極大地提高效率[1-4]。

根據摘要信息表現形式的不同，視頻摘要技術可以分為靜態圖像摘要和動態圖像摘要。靜態圖像摘要，又稱關鍵幀序列，它是從原始視頻中提取出最關鍵、最具代表性的圖像集合。動態圖像摘要，又稱縮略視頻，它是由原始視頻中提取部分關鍵視頻段，以切變或漸變的方式組合。實際上，這摘要本身也是一個視頻段，只不過在時間長度上大大短于原始視頻時間。電影預告片便是一種常用的動態圖像摘要。

靜態圖像摘要獲取的信息簡潔明了，大幅降低了視頻分析和檢索的復雜難度，但同時由于其縮略幅度太大，往往容易刪減掉一些潛在的重要信息。而動態圖像摘要包含了音頻和動態信息，大大增加了摘要的表現力[5-7]。

2 靜態圖像摘要的主要形式

靜態圖像摘要技術主要有以下幾種形式：

1）標題（Title）。標題是對視頻進行簡短描述的一個詞或一句話。雖然從嚴格意義上來講，它不算是視頻摘要的一種，但是它也是用一種簡單的方式表現視頻的內容。標題的優勢就是簡單便捷，它的產生十分方便，可以用戶直接輸入，也可以從語音轉錄文本或相關信息中抽取。它的存儲和呈現也同樣十分方便。但是不足之處是它能傳達的信息量比較少，文字很難形象地描述多媒體信息，用戶看過它之后不能有直觀的感受。

2）海報（Poster）。海報又被稱為視頻代表幀或視頻縮略圖。它從原始視頻中提取出一張或少量幾幀圖片，再加上視頻的一些相關文字信息，比如人物、簡短介紹等構成一種靜態摘要。海報是目前用的最多的摘要呈現方式，大部分的在線視頻網站的視頻展現都采用了這種方式。海報與標題相比，提供了視頻圖片，可以給用戶更直觀的感受。而且海報的產生也比較簡單，只要抽取其中幾張圖片，輔以一些文字就可以形成。但是它也有不足之處，最主要的就是它抽取的僅是視頻中的少量幾張靜態圖片，這些圖片僅僅是視頻在某些時刻的畫面，它們很難表示視頻的具體內容和發生的事件。

3）故事板（Storyboard）。故事板是在視頻進行鏡頭切分以及抽取出所有關鍵幀之后，將這些關鍵幀按照時間順序組合成一個列表的靜態摘要。故事板給用戶提供了視頻的大致結構。相比于海報，故事板抽取出來的圖片都是關鍵幀，它包含了更多的視頻語義，所有的關鍵幀構成了視頻的大致框架，可以提供給用戶較為完整的視頻信息。

4）幻燈片（Slide）。幻燈片是將經過抽取出來的幾張關鍵幀形成一張有動畫效果的GIF圖片的靜態摘要。它在鏡頭切分和關鍵幀抽取部分和故事板一樣，但他們的不同之處在于，故事板是將所有的關鍵幀呈現為一個列表，而幻燈片是在關鍵幀中抽取出一部分然后形成一張GIF圖片。這種方式的優勢是大幅度地減少了需要傳輸的圖片數量，占用的顯示空間也只有一張圖片大小。這種方式主要應用在視頻檢索時返回的視頻列表的顯示，因為這時需要在一個頁面中顯示盡量多的視頻。

3 基于圖像聚類與挖掘的視頻摘要方法

筆者提出一種基于圖像聚類與挖掘的靜態摘要方法。它的輸入是多視頻文檔以及它們對應的語音轉錄文本，輸出是一種圖片加文本的靜態摘要呈現方式，它由具有隱含主題代表性的關鍵幀和關鍵詞構成[8-9]。生成摘要的過程由3個步驟組成：首先，通過分析視覺內容抽取出一個鏡頭集合，通過分析文本內容抽取出一個關鍵詞集合；其次，進行復雜圖構建并且對抽取出來的鏡頭和關鍵詞進行聚類；最后，從聚類后的復雜圖中挖掘出最有主題代表性的關鍵幀和關鍵詞。基于圖像聚類與挖掘的視頻摘要算法框架如圖1所示。

3.1 視頻內容分析

假定現有一些帶有語音轉錄文本的視頻集D={d1,…,dm,…,dM}。為了分析這些給定視頻的視覺內容，采用了一種穩健的鏡頭邊界檢測算法來將所有視頻分割成鏡頭集合，用U={u1,…,ui,…,uI}來表示，其中ui表示一個鏡頭，I表示鏡頭的數目。為了進一步的視覺內容處理，選取了每個鏡頭的中間那一幀作為關鍵幀，然后用423維的特征向量來表示它，這個向量包含了6種特征，包括256維的顏色直方圖、6維顏色矩、128維顏色一致向量、15維的MSRSAR紋理、10維Tamura紋理的粗糙度和8維Tamura紋理的方向度。

除此之外，為了分析給定視頻的文本內容，分2個步驟來從語音轉錄文本中提取有意義的關鍵詞：1）使用一個語音標注器來標出語音轉錄文本中的名詞；2）使用鍵詞的分數并從中選擇出最重要的關鍵詞。

3.2 復雜圖構建和聚類

考慮這樣一個任務：從視頻集D中抽取出了一個鏡頭集U和關鍵詞集W，現在要找出它們的聚類結構。一般可以采用單邊的聚類算法來分別對鏡頭和關鍵詞進行聚類[5]，也可以采用協同聚類算法來同時對鏡頭和關鍵詞進行聚類。筆者采用一種復雜圖聚類的算法來同時獲得鏡頭聚類和關鍵詞聚類以及它們之間的關系。

首先使用鏡頭集U和關鍵詞集W來構建一個由鏡頭節點和關鍵詞節點構成的圖。設定用G=(V(1),V(2),E(1,1),E(1,2))來表示這個復雜圖，其中V(1)={v(1)1,…,v(1)i,…,v(1)I}表示鏡頭節點集，v(1)i是V(1)中的第i個節點，對應于U的第ith個鏡頭。V(2)={v(2)1,…,v(2)j,…,v(2)J}表示關鍵詞節點集，v(2)j是V(2)中的第jth個節點，對應于W的第j個關鍵詞。E(1,1)表示鏡頭節點之內的同構邊，E(1,2)表示鏡頭節點和關鍵詞節點之間的異構邊。用關聯矩陣S∈RI×I+表示E(1,1)的權重，用A∈RI×J+來表示E(1,2)的權重。采用余弦相似性來生成矩陣S。也就是說，節點v(1)i和節點v(1)q之間邊的權值Si,q可以用如下公式來表示

式中：fe(ui)表示鏡頭ui的關鍵幀特征。另外，鏡頭和關鍵詞之間的共現性用來生成矩陣A。也就是說鏡頭節點v(1)i和關鍵詞節點v(2)j之間邊的權重Ai,j可以用如下公式來表示

注意到單詞wj可能在包含鏡頭ui的視頻中出現多次，所以每一次的出現用索引k來表示。定義一個時間相似性的函數simt(t(ui),t(wkj))，其中t(ui)表示鏡頭ui的中間時間點，t(wkj)表示單詞wj第k次出現的中間時間點，它可以用如下公式來表示

式中：simt()函數是一個分段函數，它在t(wkj)落在時間區間t(ui)start和t(ui)end之間時取值為1，這兩個時間點分別為鏡頭ui的起始時間點和結束時間點。而為了補償鏡頭和關鍵詞出現時間上的延遲，它的兩邊按照標準差為σt的高斯濾波函數進行擴散。

然后，用一種聚類算法[6]來獲得鏡頭聚類和關鍵詞聚類以及它們之間的關系。假設已將鏡頭節點V(1)聚成了K 類CU={cu(1),…,cu(k),…,cu(K)}，將關鍵詞節點V(2)聚成了L類CW={cw1,…,cwl,…,cwL}。用C(1)∈(0,1)I×K表示鏡頭節點V(1)的聚類成員矩陣，其每個元素C(1)i,k表示第i個鏡頭節點與第k個聚類的關聯權重。用C(2)∈(0,1)J×L表示關鍵詞節點V(2)的聚類成員矩陣，其每個元素C(2)j,l表示第j個詞與第l聚類的關聯權重。用D∈RK×K表示同類節點聚類間的關聯關系，其每個元素Dk,r表示第k個鏡頭聚類cuk與第r個鏡頭聚類cur的關聯強度。用B∈RK×L表示不同類節點聚類間的關聯關系，其每個元素Bk,l表示第k個鏡頭聚類cuk與第l個關鍵詞聚類的關聯強度。

3.3 主題代表性的關鍵幀與關鍵詞的挖掘

這一步主要是為了從聚類后的復雜圖中挖掘出隱含主題的最有代表意義的關鍵幀和關鍵詞。具體步驟有：

1）定義鏡頭節點和關鍵詞節點重要性的度量方法。本文采用先前提到的修改版tf-idf公式來計算關鍵詞節點的重要性。而計算鏡頭節點的重要性時，將同時考慮視覺和相關的文本特征。

2）定義了鏡頭聚類和關鍵詞聚類信息量的度量方法。與單個視頻生成摘要不同，多視頻通常包含幾個子主題或者子事件，并且每個子主題或子事件可以通過一個主題相關的關鍵詞聚類或者一個事件相關的鏡頭聚類來呈現[10-11]。因此，計算一個關鍵詞聚類的重要性可以基于如下觀察：（1）一個聚類越復雜，那么它就越重要；（2）一個聚類包含的關鍵詞越重要，那么它就越重要。

3）選擇隱含主題的最有代表性的關鍵幀和關鍵詞。由于每個聚類表示了一個隱含的子主題或子事件。因此，筆者提出用2個步驟的選擇方法來最大化主題的覆蓋度，同時也盡可能的移除冗余：（1）選取那些重要性分數最高的鏡頭聚類，然后在選取出來的每個聚類中，選擇最重要的那個鏡頭的關鍵幀作為其代表；（2）選取那些重要性分數最高的關鍵詞聚類，然后在選取出來的每個聚類中，選擇最重要的關鍵詞作為其代表。

4 小結

視頻摘要是許多視頻應用程序的有機組成部分，如視頻索引、瀏覽以及檢索。高效智能的視頻摘要生成系統能夠幫助用戶更加快速地處理大量視頻。近年來，很多研究機構都積極開展視頻摘要新技術的研究，并提出了多種算法和思路。筆者提出了一種基于圖像聚類與挖掘的視頻摘要方法，在解決視頻摘要主題分散性與多模態難點的道路上做了一些探索，如何通過更優的算法來更加準確地表達出整段視頻的內容將是未來工作的努力方向。

[1]CHRISTEL M G，HAUPTMANN A G，LIN W H，et al.Exploring the utility of fast-forward surrogates for BBC rushes[EB/OL].[2011-01-20].http：//citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.141.7507＆rep=rep1＆type=pdf.

[2]SHAO J，JIANG D，WANG M，et al.Multi-video summarization using complex graph clustering and mining[J].Journal of Computer Science and Information System，2010，7（1）：85-97.

[3]CHEN B，WANG J，WANG J.A novel video summarization based on mining the story-structure and semantic relations among concept entities[J].IEEE Tran.Multimedia，2009，11（2）：295-312.

[4]王毅，李弼程，彭天強.視頻摘要技術[J].信息工程大學學報，2009，10（4）：493-497.

[5]YE Z Y，WU F.A robust fusion algorithm for shot boundary detection[J].Journal of Computer Aided Design and Computer Graphics，2003，15（11）：950-955.

[6]XIA D Y，WU F，ZHANG X，et al.Local and global approaches of affinity propagation clustering for large scale data[J].Journal of Zhejiang University：Science A，2008，9（10）：1373-1381.

[7]程文剛，須德，蔣軼瑋，等.一種新的動態視頻摘要生成方法[J].電子學報，2005，33（8）：1461-1466.

[8]章毓晉.基于內容的視覺信息檢索[M].北京：科學出版社，2003.

[9]顧諍，肖若貴.基于AP聚類和頻繁模式挖掘的視頻摘要生成方法[J].計算機應用與軟件，2010，27（6）：5-7.

[10]余衛宇，曹燕，謝勝利.視頻摘要的現狀和研究進展[J].計算機應用研究，2008，25（7）：1948-1952.

[11]姚彬，史萍，葛菲，等.監控視頻的摘要提取方法研究[J].電視技術，2010，34（4）：106-108.