冀 中，馬亞茹，何宇清

天津大學 電氣自動化與信息工程學院，天津 300072

1 引言

近年來，網(wǎng)絡(luò)視頻的數(shù)量急速增長，使得用戶很難短時間內(nèi)獲取想要的內(nèi)容，降低了瀏覽的效率。為此，人們迫切需要一種能夠高效瀏覽和理解視頻內(nèi)容的技術(shù)，從而能夠更加有效地獲取想要的信息。視頻摘要由一組靜止的關(guān)鍵幀圖像序列或者視頻片段組成，并以一種簡潔的方式將視頻的主要內(nèi)容呈現(xiàn)出來，是一種有效的瀏覽、管理視頻的技術(shù)，廣泛應(yīng)用在視頻存檔、搜索引擎、交互瀏覽等領(lǐng)域[1-3]。

視頻摘要主要有兩種形式：靜態(tài)摘要和動態(tài)摘要。靜態(tài)視頻摘要通過一系列的關(guān)鍵幀組成相應(yīng)的語義單元，概括表示視頻的內(nèi)容，表達形式直觀簡潔。動態(tài)視頻摘要則是由視頻小片段組成，保持了視頻內(nèi)容隨時間變化的固有特征，易于用戶的理解[4]。本文采用靜態(tài)摘要呈現(xiàn)形式。

視頻摘要的優(yōu)劣主要通過最小信息冗余、重要信息優(yōu)先和最大信息覆蓋3個標準來判斷。其中，最小信息冗余指盡可能地降低視頻摘要中的冗余信息，即摘要長度要盡可能短；重要信息優(yōu)先指盡量將視頻的重要內(nèi)容優(yōu)先挑選到摘要中；最大信息覆蓋指提取的關(guān)鍵幀能夠盡可能覆蓋視頻的主要內(nèi)容。

目前的方法主要有基于聚類的方法[5-6]、幀間最小相似度的方法[7-8]以及最小重構(gòu)誤差的方法[9-10]等。其中，基于聚類的方法將視頻幀看作特征空間中的數(shù)據(jù)點，通過選取聚類中心作為關(guān)鍵幀形成摘要。例如，文獻[5,11]分別提出利用k均值和基于圖模型的聚類算法實現(xiàn)視頻摘要。聚類方法生成的摘要可覆蓋視頻的所有內(nèi)容，容易滿足最大信息覆蓋這一標準，這對于含有少量噪音信息的視頻來說具有較好的效果。但對于那些含有大量噪音信息的視頻，聚類方法卻無法判斷出重要信息，使提取出來的摘要含有噪音信息。另外，由于語義鴻溝的存在，要準確地實現(xiàn)有意義的聚類也較為困難。

幀間最小相似度的方法目的是使關(guān)鍵幀之間的相似度最小，其代表方法之一是序列決定點過程（sequential determinal point process，seqDPP）[7]。該類方法能夠生成低冗余度、最大覆蓋信息的視頻摘要。近年來，最小重構(gòu)誤差的思想也被用于視頻摘要領(lǐng)域[9-10]，其思想是使得原始視頻幀與關(guān)鍵幀的重構(gòu)誤差最小，從而迭代選擇關(guān)鍵幀構(gòu)成視頻摘要。這類方法考慮了摘要的冗余性和最大信息覆蓋標準，但忽略了重要性優(yōu)先標準。上述幀間最小相似度方法和最小重構(gòu)誤差方法認為視頻內(nèi)容之間的相似度是影響視頻摘要的關(guān)鍵因素，忽略了視頻內(nèi)容的重要性優(yōu)先標準，這對于含有少量噪音信息的視頻來說是有效的，但是現(xiàn)在視頻內(nèi)容越來越復雜，僅僅考慮這兩個標準提取摘要達不到理想的效果。

另外，最近的研究開始引入一些高層信息，如用戶偏好、重要事件、網(wǎng)頁圖像等信息，試圖從這些角度獲取視頻的語義信息以彌補語義鴻溝問題[3,12-13]。例如，Liu等人[14]通過用戶點擊信息獲取用戶查詢意圖，從而判斷視頻中的重要性信息，這類方法旨在查找視頻的重要內(nèi)容生成動態(tài)摘要。雖然能達到一定的效果，但是對于靜態(tài)摘要而言因為更加看重冗余性問題，所以這種方法不能達到較好效果。

然而，以上方法通常針對視頻集的特點，根據(jù)不同的目標，從不同的角度將視頻摘要過程看作不同的數(shù)學模型。而由于模型的限制，設(shè)計的摘要框架很少能夠同時滿足本文所述摘要標準，使得摘要的效果并未達到預期效果。針對此問題，本文設(shè)計了一種同時滿足所需3個標準的摘要框架。受最大邊界相關(guān)算法（maximal marginal relevance，MMR）啟發(fā)，本文提出最大邊界重要和覆蓋（maximal marginal importance and coverage，MMIC）框架，同時優(yōu)化冗余性、重要性和覆蓋率3個指標。特別地，利用基于KRNN（K-regular nearest neighbor）圖的流形排序算法[15]設(shè)計了一種重要性計算方法，還提出了摘要覆蓋率標準（summarization coverage criterion，SCC）自動生成合適長度的視頻摘要。在主流的Open Video Project和YouTube數(shù)據(jù)集上進行了大量主觀和客觀實驗，驗證了MMIC算法的有效性和先進性。本文的貢獻主要為以下兩點：

（1）提出MMIC視頻摘要框架，利用MMIC算法同時優(yōu)化摘要的重要優(yōu)先性、最大覆蓋率和最小冗余性。

（2）提出利用K-RNN圖的流形排序算法設(shè)計一種計算視頻幀的重要性分數(shù)的方法。

2 最大邊距相關(guān)算法

最大邊距相關(guān)是一種平衡相關(guān)性和冗余性算法，在文本摘要領(lǐng)域中有著重要的應(yīng)用[16]。該算法在選擇摘要句子時，使得選擇的句子既與文檔主題的相關(guān)性最高，又使該句與已選的文摘句的冗余性最小。因此保證了摘要句子既與主題相關(guān)，又含有較少的冗余信息。

假設(shè)給定一個集合D，并想獲得一個與查詢q相關(guān)的子集Dk，且MMR算法在給定的條件下，根據(jù)式（1）所示標準，利用貪婪方式選擇下一個元素構(gòu)成子集，以此迭代獲得子集Dk。

其中，sim1(dj,q)表示元素dj與查詢q的相似性；sim1(dj,di)表示已選元素di∈Dj-1與待選元素dj∈DDj-1的相似性；λ用于平衡相關(guān)性和冗余性。

3 MMIC算法

理想的視頻摘要需滿足最大覆蓋率、重要優(yōu)先性和最小冗余性等準則，且受文本摘要領(lǐng)域中的最大邊界相關(guān)算法的啟發(fā)，本文提出同時優(yōu)化上述3個目標的MMIC算法。該算法平衡了摘要的重要性、覆蓋率和冗余性標準。與文本摘要中僅依賴一個靜態(tài)的查詢不同的是，視頻摘要中不需要靜態(tài)查詢，依賴逐步迭代選擇關(guān)鍵幀構(gòu)成視頻摘要。在每次迭代時，希望選擇的關(guān)鍵幀同時滿足重要性最大，其構(gòu)成的關(guān)鍵幀集的覆蓋率最大，同時與已選的關(guān)鍵幀集的冗余性最小。根據(jù)這種思想本文設(shè)計了如下目標函數(shù)：

其中，Sk表示第k次迭代后選擇的關(guān)鍵幀集；V表示視頻幀集；C=VSk表示視頻幀集V與關(guān)鍵幀集Sk的差集；I(xi)表示視頻幀xi的重要性大?。籆ov((Sk?xi),V)表示候選關(guān)鍵幀集{Sk?xi}（這里候選關(guān)鍵幀集指的是已選關(guān)鍵幀集與任意視頻幀xi∈C的并集）與視頻幀集V的覆蓋率；重要性和覆蓋率計算模型將在下一部分展開介紹；sim(xi,gj)表示視頻幀xi與關(guān)鍵幀gj的余弦相似性大小，用以控制摘要冗余性大小；λ表示前后兩項的平衡系數(shù)。

下面將分別描述重要性和覆蓋率摘要標準，并對MMIC的關(guān)鍵幀選擇算法進行詳細介紹。

3.1 視頻幀重要性計算模型

（1）構(gòu)建視頻的K-RNN相似圖

首先，采用每秒2幀等間隔采樣的方法提取候選幀集，然后提取視覺特征。由于顏色特征提取簡單，且對相機拍攝位置的變化有較強的魯棒性，常用在視頻摘要領(lǐng)域。為此本文采用8×8×4量化的HSV顏色直方圖表征視覺內(nèi)容。

然后，采用無向帶權(quán)重的K-RNN相似圖[15]G=(V,E)來描述視頻幀之間的關(guān)系。頂點集V={x1,x2,…,xn}表示視頻幀集，頂點xi是視頻V中的第i幀。E?V×V表示邊集，若頂點xi和頂點xj之間有連接邊，則根據(jù)高斯相似性計算連接權(quán)重wij(i≠j)。在K-RNN圖中，每個頂點的度是相對它與其他頂點的位置而定的。例如，如果一個頂點與其他所有點距離較遠的話，則這個點是孤立的點，因此需要最小化與這個頂點相連接的邊的權(quán)重和。反之，則該頂點具有較高的頂點度，這些點應(yīng)該以較高的概率分為一類。根據(jù)此思想利用貪婪算法構(gòu)建視頻的K-RNN圖。

（2）基于K-RNN圖的流形排序的重要性計算

通常視頻中重復出現(xiàn)的幀是比較重要的內(nèi)容。據(jù)此本文設(shè)計了一種基于流形排序的視頻幀重要性計算方法。在給定查詢的情況下，流形排序?qū)?shù)據(jù)點按照它們在數(shù)據(jù)流形結(jié)構(gòu)中與查詢的相關(guān)性進行排序[17]。本文利用這一特性通過將每個視頻幀看作查詢，其余的數(shù)據(jù)點作為待查詢的幀來獲得與查詢幀相關(guān)性大于一定閾值的待查詢幀數(shù)，幀數(shù)越多說明該查詢幀在此視頻中占據(jù)的分量越大，該幀越重要。本文首先將任意視頻幀xi看作查詢幀，其余幀看作待排序的幀。然后根據(jù)流形排序計算待排序的幀集的排序分數(shù)，并設(shè)置一定的閾值判斷分數(shù)大于該閾值Th的幀的數(shù)量si，則該幀的重要性分數(shù)I(xi)的具體計算過程如下：

這里，n指的是視頻幀集的數(shù)量。

3.2 信息覆蓋計算模型

摘要的信息覆蓋率值反映了摘要涵蓋原視頻內(nèi)容的大小程度，因此摘要的覆蓋率越大表明摘要包含的視頻的信息越多，摘要質(zhì)量越高。為了使所選的關(guān)鍵幀構(gòu)成的摘要與視頻之間的覆蓋率最大，需在每次迭代時保證選擇的關(guān)鍵幀構(gòu)成的關(guān)鍵集的覆蓋率最大，為此需要計算候選關(guān)鍵幀集{Sk?xi}與視頻V之間的覆蓋率。本文通過計算兩者之間的相似性，來衡量其覆蓋率，且認為兩者之間距離越小候選關(guān)鍵幀集{Sk?xi}的覆蓋率越大，其計算公式如下所示：

其中，Cov(Sk?xi,V)表示候選關(guān)鍵幀集{Sk?xi}與視頻集V的相似性；d(xi,g)表示視頻幀xi與關(guān)鍵幀g之間的歐式距離。

3.3 基于MMIC的優(yōu)化算法

在滿足上述標準后，本文將根據(jù)式（1）迭代選擇關(guān)鍵幀構(gòu)成視頻摘要。其迭代過程如下：

其中，S1表示初始摘要集；Sk+1表示第k+1次迭代生成的關(guān)鍵幀集。

接下來設(shè)定迭代終止條件。常用的方法是為摘要設(shè)定一定長度，但是在對視頻無先驗信息的情況下，為摘要設(shè)定一個合適長度較為困難。為此，本文提出了一個摘要覆蓋率標準（summarization coverage criterion，SCC)自動選取合適的摘要長度。當SCC達到閾值TSCC時（這里TSCC=0.85），迭代終止。通過設(shè)定不同的閾值可以獲得不同的摘要長度，能夠適應(yīng)于不同類型的視頻。迭代過程中SCC的計算如下：

圖1給出了MMIC算法的流程圖。生成整個視頻摘要的過程如下所示。

Fig.1 Flow chart of proposed MMIC algorithm圖1 所提MMIC算法的流程圖

算法MMIC算法

輸入：視頻幀集V={x1,x2,…,xn}。

輸出：視頻摘要S。

1.根據(jù)式（5）選擇關(guān)鍵幀集的第一幀構(gòu)成S1；

2.根據(jù)式（6）迭代選擇摘要中的第k+1個關(guān)鍵幀構(gòu)成Sk+1；

3.迭代步驟2直到摘要的覆蓋率SCCk+1達到一定的閾值TSCC，算法結(jié)束。

4 實驗結(jié)果與分析

4.1 數(shù)據(jù)集與評價方法

本文在YouTube和Open Video Project[5]數(shù)據(jù)集上進行實驗。YouTube數(shù)據(jù)集是自行從YouTube視頻分享網(wǎng)站下載的20個視頻，這些視頻時長限制為1～4分鐘，且該數(shù)據(jù)集包含的主題主要有電影片段、監(jiān)控視頻、BBC新聞、體育比賽4個主題，沒有人工標注。Open Video Project數(shù)據(jù)集包含50個視頻，且每個視頻時長限制為1～4分鐘。該數(shù)據(jù)集包含的主題主要有記錄片、科教片、短片、歷史片、課堂等主題，涵蓋主題范圍較廣，且該數(shù)據(jù)集提供了人工視頻摘要，可用于摘要結(jié)果的客觀評價。

通常采用客觀和主觀評價兩種方法評價視頻摘要的優(yōu)劣。所用的客觀評價方法是通過比較所提方法生成的視頻摘要和用戶摘要中的關(guān)鍵幀之間的距離所得[9]。具體地，首先計算自動視頻摘要和用戶摘要中的幀之間的歐式距離，然后將其與預先設(shè)定的閾值（本文設(shè)定該閾值為0.5）相比較來決定兩幀是否匹配。如果兩幀匹配，則在下一次比較過程中刪除這兩幀，并進行下一次比較。最后用準確率(P)、召回率(R)和F-score(F)3個標準來綜合評價摘要。其具體的計算方式如下所示：

其中，nAS、nmAS和nUS分別表示自動視頻摘要中的關(guān)鍵幀數(shù)量、匹配的關(guān)鍵幀數(shù)量和用戶摘要中的關(guān)鍵幀數(shù)量。而且為了降低用戶的主觀性，本文利用多個用戶摘要進行比較，并對這3個評價標準取平均從而評價摘要。

對于主觀評價，邀請用戶觀看完自動視頻摘要后，從重要度、覆蓋率和多樣性三方面考慮給出一個評價。評價等級分為Good、Acceptable、Bad共3個等級。其中Bad表示所提算法生成的摘要的效果糟糕，Good表示生成的摘要結(jié)果比較理想。

4.2 結(jié)果分析

4.2.1 Open Video Project數(shù)據(jù)集

（1）客觀評價

為了驗證本文MMIC算法的有效性，對比了DT（Delaunay triangulation）[18]、OV（open video storyboards）[19]、KMC（K-means methods on color feature）[6]、KMCE（K-means methods on color and edge features）[6]、k-means和 MSR（minimum sparse reconstruction）[9]等6種方法，如表1所示。為了保持一致性，在所有這些方法中除KMCE外均使用顏色特征作為視頻幀的視覺表征。

①DT[18]算法：該算法首先構(gòu)建德勞內(nèi)三角形圖，通過移除類間邊來獲得聚類結(jié)果,并在每類中選取一幀作為關(guān)鍵幀。

②OV[19]算法：和聚類相似，曲線簡化的方法也是將視頻幀看成特征空間中的點，不過它進一步將視頻看作這些點按時間順序連成的曲線，然后通過曲線分割的方法實現(xiàn)摘要算法。

③KMC[6]算法：該算法提出了一種使用動態(tài)Delaunay圖聚類的迭代邊緣修剪策略，將結(jié)構(gòu)條件作為圖頂點的導數(shù)的下限，提高了摘要的質(zhì)量，并且利用了信息理論的預采樣獲得了信息量大的幀。

④KMCE[6]算法：該算法與KMC算法的差別在于所用的特征不同，KMCE所用的特征是顏色和邊緣特征，而KMC算法僅僅利用顏色特征。

⑤k-means算法：該算法首先將視頻分割成幀并對其進行預采樣生成候選關(guān)鍵幀，然后利用k-means聚類算法實現(xiàn)幀的聚類，最后在每類中選擇與聚類中心最近的幀作為關(guān)鍵幀構(gòu)成視頻摘要。

⑥MSR[9]算法：該模型將稀疏編碼算法應(yīng)用到視頻摘要任務(wù)中。它將摘要集和視頻幀集分別看作基向量組（也稱為字典）和候選基向量組，并通過稀疏編碼學習一組基向量來重構(gòu)原來的視頻主題空間。該算法首先隨機選擇一幀作為關(guān)鍵幀來初始化摘要集，而下一關(guān)鍵幀則按照最大減少摘要集和原來的視頻幀集之間的重構(gòu)誤差的原則進行選取，并迭代直至滿足一定的條件。

Table 1 Precision(P),recall(R),F-value(F)and average length(L)of different algorithms on Open Video Project表1 Open Video Project上不同算法的精度(P)、召回率(R)、F-值(F)和摘要平均長度(L)結(jié)果對比

從表1中可以看出，在準確率方面MMIC算法性能相對較好，分別比k-means、OV、DT、MSR高約10%、3%、3%、20%，但分別比KMC和KMCE低了約3%和5%。在召回率方面MMIC算法優(yōu)于大部分對比算法，分別比k-means、OV、DT、KMC、KMCE高約1%、1%、22%、12%和13%，但比MSR算法低了約7%。在F值方面MMIC算法均高于其他算法，分別比k-means、OV、DT、KMC、KMCE和MSR高約6%、2%、14%、4%、4%和11%。

根據(jù)摘要長度比較可以看出，MMIC算法的摘要長度高于KMC和KMCE，摘要長度影響了算法的準確率，因此準確率低于這兩種算法。但是從召回率的角度分析，MMIC算法高于k-means、OV、DT、KMC、KMCE算法，但略低于MSR算法，這是因為MSR算法的摘要長度高于所提MMIC算法，所以匹配的幀數(shù)略大于MMIC算法。總之MMIC算法的摘要中匹配幀數(shù)大于多數(shù)對比算法的匹配幀數(shù)，效果明顯高于其他算法。從F值也可以看出，MMIC算法的F值明顯高于其他算法。綜上，所提MMIC算法的性能在Open Video Project數(shù)據(jù)集上表現(xiàn)較好。

為了直觀對比MMIC與其他算法，從50個視頻摘要中抽樣出一個可視化摘要結(jié)果，如圖2所示，每一行呈現(xiàn)一種摘要算法的結(jié)果。從圖2可以直接看出所提MMIC算法相比較于其他算法，能夠較好地去除冗余性，且選擇的關(guān)鍵幀能夠較好地代表原來的視頻內(nèi)容，性能優(yōu)于其他算法。

Fig.2 Results of MMIC and baselines for video“ANew Horizon”(the red box is a redundant video frame)圖2 MMIC與對比算法對視頻“ANew Horizon”的摘要結(jié)果(紅色框內(nèi)為冗余的視頻幀)

（2）主觀評價

為了進一步比較MMIC算法的性能，邀請了3個男生和3個女生共6個用戶參與主觀評價，要求這些用戶觀看視頻后對該算法所提的摘要結(jié)果進行評價。評價等級分為Good、Acceptable、Bad共3個等級，用戶根據(jù)摘要滿足重要性、覆蓋率和多樣性標準的程度綜合給出摘要的主觀評價。具體的評價結(jié)果如表2所示。

Table 2 Subjective evaluation of MMIC algorithm on Open Video Project表2 OpenVideo Project上MMIC算法的主觀評價結(jié)果

從表2中可以看出MMIC算法的主觀評價整體上較好。50個視頻中，Good評價等級的視頻約有40個，占整個數(shù)據(jù)集的80%，Acceptable評價等級的視頻約有8個，占整個數(shù)據(jù)集的約16%，而Bad評價等級的視頻有2個，占整個數(shù)據(jù)集的約4%?？傮w來說，MMIC算法生成的摘要結(jié)果能夠較好地代表視頻的主要內(nèi)容。

另外，為了進一步證明MMIC算法優(yōu)于其他對比算法，本文要求參與評價的用戶對這些算法的摘要結(jié)果進行主觀評價，如表3所示?？梢钥闯?個用戶分別對這6種算法的投票結(jié)果為：MMIC算法的評價等級為Good的視頻個數(shù)平均為40（視頻總數(shù)為50），高于其他對比算法；而評價為Bad的視頻平均為2個，遠小于其他對比算法。因此所提MMIC算法效果較以往摘要方法有了明顯的改善。

Table 3 Average results of subjective evaluation of different algorithms on Open Video Project表3 OpenVideo Project上不同算法的主觀評價的平均結(jié)果

4.2.2 YouTube數(shù)據(jù)集

YouTube數(shù)據(jù)集是從YouTube上下載的視頻集，沒有統(tǒng)一可用的用戶摘要標準。因此本文只對該數(shù)據(jù)集的結(jié)果進行主觀評價。按照Open Video Project數(shù)據(jù)集的主觀評價標準對YouTube數(shù)據(jù)集上的摘要結(jié)果進行主觀評價，如表4所示。

Table 4 Subjective evaluation of MMIC algorithm onYouTube dataset表4 YouTube數(shù)據(jù)集上MMIC算法的主觀評價結(jié)果

可以看出，20個視頻中約有16個視頻的評價等級為Good，約3個視頻的評價等級為Acceptable，而僅僅約有1個視頻的評價等級為Bad。因此可以進一步證明所提MMIC算法生成的摘要結(jié)果能夠較好地代表視頻的主要內(nèi)容。

另外，本文還要求用戶在YouTube數(shù)據(jù)集上對其他對比算法進行主觀評價，如表5所示?？梢钥闯?，所提MMIC算法的評價等級為Good的視頻個數(shù)約為16（視頻總數(shù)為20），優(yōu)于其他算法；而評價等級為Bad的視頻個數(shù)約為1，均低于其他算法。這表明MMIC算法在YouTube數(shù)據(jù)集取得了較好的效果，更加證明了該算法的魯棒性。

Table 5 Subjective evaluation of MMIC algorithm onYouTube dataset表5 YouTube上不同算法的主觀評價的平均結(jié)果

5 結(jié)束語

本文在MMR算法的啟發(fā)下提出了一種融合最小冗余性、最大重要性和最大覆蓋率標準的MMIC摘要算法，并提出了利用基于K-RNN圖的流形排序算法計算視頻幀的重要性。在迭代選擇關(guān)鍵幀時，為了同時滿足上述提及的3個摘要標準，利用MMIC算法來實現(xiàn)關(guān)鍵幀的選擇，從而構(gòu)建視頻摘要。并在Open Video Project和YouTube數(shù)據(jù)集進行了實驗，驗證了所提算法的有效性和先進性。