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

陳 宏

（浙江廣播電視集團(tuán)，浙江 杭州 310005）

1 視頻摘要的基本概念

視頻摘要技術(shù)，它的概念類似于文本摘要，即通過(guò)計(jì)算機(jī)自動(dòng)處理技術(shù)，對(duì)視頻的內(nèi)容和結(jié)構(gòu)進(jìn)行分析，并從原視頻內(nèi)容中提取出用戶需要的信息，再做進(jìn)一步處理。如果一個(gè)視頻摘要能夠做到盡量準(zhǔn)確和充分，那么就能夠讓用戶在最短時(shí)間內(nèi)獲得最關(guān)鍵的信息，極大地提高效率[1-4]。

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

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

2 靜態(tài)圖像摘要的主要形式

靜態(tài)圖像摘要技術(shù)主要有以下幾種形式：

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

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

3）故事板（Storyboard）。故事板是在視頻進(jìn)行鏡頭切分以及抽取出所有關(guān)鍵幀之后，將這些關(guān)鍵幀按照時(shí)間順序組合成一個(gè)列表的靜態(tài)摘要。故事板給用戶提供了視頻的大致結(jié)構(gòu)。相比于海報(bào)，故事板抽取出來(lái)的圖片都是關(guān)鍵幀，它包含了更多的視頻語(yǔ)義，所有的關(guān)鍵幀構(gòu)成了視頻的大致框架，可以提供給用戶較為完整的視頻信息。

4）幻燈片（Slide）。幻燈片是將經(jīng)過(guò)抽取出來(lái)的幾張關(guān)鍵幀形成一張有動(dòng)畫(huà)效果的GIF圖片的靜態(tài)摘要。它在鏡頭切分和關(guān)鍵幀抽取部分和故事板一樣，但他們的不同之處在于，故事板是將所有的關(guān)鍵幀呈現(xiàn)為一個(gè)列表，而幻燈片是在關(guān)鍵幀中抽取出一部分然后形成一張GIF圖片。這種方式的優(yōu)勢(shì)是大幅度地減少了需要傳輸?shù)膱D片數(shù)量，占用的顯示空間也只有一張圖片大小。這種方式主要應(yīng)用在視頻檢索時(shí)返回的視頻列表的顯示，因?yàn)檫@時(shí)需要在一個(gè)頁(yè)面中顯示盡量多的視頻。

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

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

3.1 視頻內(nèi)容分析

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

除此之外，為了分析給定視頻的文本內(nèi)容，分2個(gè)步驟來(lái)從語(yǔ)音轉(zhuǎn)錄文本中提取有意義的關(guān)鍵詞：1）使用一個(gè)語(yǔ)音標(biāo)注器來(lái)標(biāo)出語(yǔ)音轉(zhuǎn)錄文本中的名詞；2）使用鍵詞的分?jǐn)?shù)并從中選擇出最重要的關(guān)鍵詞。

3.2 復(fù)雜圖構(gòu)建和聚類

考慮這樣一個(gè)任務(wù)：從視頻集D中抽取出了一個(gè)鏡頭集U和關(guān)鍵詞集W，現(xiàn)在要找出它們的聚類結(jié)構(gòu)。一般可以采用單邊的聚類算法來(lái)分別對(duì)鏡頭和關(guān)鍵詞進(jìn)行聚類[5]，也可以采用協(xié)同聚類算法來(lái)同時(shí)對(duì)鏡頭和關(guān)鍵詞進(jìn)行聚類。筆者采用一種復(fù)雜圖聚類的算法來(lái)同時(shí)獲得鏡頭聚類和關(guān)鍵詞聚類以及它們之間的關(guān)系。

首先使用鏡頭集U和關(guān)鍵詞集W來(lái)構(gòu)建一個(gè)由鏡頭節(jié)點(diǎn)和關(guān)鍵詞節(jié)點(diǎn)構(gòu)成的圖。設(shè)定用G=(V(1),V(2),E(1,1),E(1,2))來(lái)表示這個(gè)復(fù)雜圖，其中V(1)={v(1)1,…,v(1)i,…,v(1)I}表示鏡頭節(jié)點(diǎn)集，v(1)i是V(1)中的第i個(gè)節(jié)點(diǎn)，對(duì)應(yīng)于U的第ith個(gè)鏡頭。V(2)={v(2)1,…,v(2)j,…,v(2)J}表示關(guān)鍵詞節(jié)點(diǎn)集，v(2)j是V(2)中的第jth個(gè)節(jié)點(diǎn)，對(duì)應(yīng)于W的第j個(gè)關(guān)鍵詞。E(1,1)表示鏡頭節(jié)點(diǎn)之內(nèi)的同構(gòu)邊，E(1,2)表示鏡頭節(jié)點(diǎn)和關(guān)鍵詞節(jié)點(diǎn)之間的異構(gòu)邊。用關(guān)聯(lián)矩陣S∈RI×I+表示E(1,1)的權(quán)重，用A∈RI×J+來(lái)表示E(1,2)的權(quán)重。采用余弦相似性來(lái)生成矩陣S。也就是說(shuō)，節(jié)點(diǎn)v(1)i和節(jié)點(diǎn)v(1)q之間邊的權(quán)值Si,q可以用如下公式來(lái)表示

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

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

式中：simt()函數(shù)是一個(gè)分段函數(shù)，它在t(wkj)落在時(shí)間區(qū)間t(ui)start和t(ui)end之間時(shí)取值為1，這兩個(gè)時(shí)間點(diǎn)分別為鏡頭ui的起始時(shí)間點(diǎn)和結(jié)束時(shí)間點(diǎn)。而為了補(bǔ)償鏡頭和關(guān)鍵詞出現(xiàn)時(shí)間上的延遲，它的兩邊按照標(biāo)準(zhǔn)差為σt的高斯濾波函數(shù)進(jìn)行擴(kuò)散。

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

3.3 主題代表性的關(guān)鍵幀與關(guān)鍵詞的挖掘

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

1）定義鏡頭節(jié)點(diǎn)和關(guān)鍵詞節(jié)點(diǎn)重要性的度量方法。本文采用先前提到的修改版tf-idf公式來(lái)計(jì)算關(guān)鍵詞節(jié)點(diǎn)的重要性。而計(jì)算鏡頭節(jié)點(diǎn)的重要性時(shí)，將同時(shí)考慮視覺(jué)和相關(guān)的文本特征。

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

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

4 小結(jié)

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

[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]王毅，李弼程，彭天強(qiáng).視頻摘要技術(shù)[J].信息工程大學(xué)學(xué)報(bào)，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]程文剛，須德，蔣軼瑋，等.一種新的動(dòng)態(tài)視頻摘要生成方法[J].電子學(xué)報(bào)，2005，33（8）：1461-1466.

[8]章毓晉.基于內(nèi)容的視覺(jué)信息檢索[M].北京：科學(xué)出版社，2003.

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

[10]余衛(wèi)宇，曹燕，謝勝利.視頻摘要的現(xiàn)狀和研究進(jìn)展[J].計(jì)算機(jī)應(yīng)用研究，2008，25（7）：1948-1952.

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