一種基于最短路徑的視頻摘要方法

葛 釗, 趙 燁

(1.合肥工業(yè)大學(xué) 智能制造技術(shù)研究院,安徽 合肥 230051; 2.合肥工業(yè)大學(xué) 計算機(jī)與信息學(xué)院,安徽 合肥 230601)

0 引 言

視頻內(nèi)容作為多媒體信息的載體之一，一直被廣泛應(yīng)用于生活的方方面面。近些年來,隨著移動電話和其他面向消費(fèi)者的相機(jī)設(shè)備的快速發(fā)展,以及互聯(lián)網(wǎng)技術(shù)和多媒體技術(shù)的飛速發(fā)展,視頻內(nèi)容特別是用戶視頻的數(shù)量日益增長,這些海量的視頻數(shù)據(jù)給視頻存儲、傳輸、檢索等帶來巨大的壓力[1]。而且由于視頻內(nèi)容錯綜復(fù)雜,觀眾在瀏覽視頻時會耗費(fèi)大量的時間去尋找自己真正感興趣的內(nèi)容。

在這樣的背景下,視頻摘要技術(shù)應(yīng)運(yùn)而生。所謂視頻摘要,就是以簡短的內(nèi)容概括原始視頻的主要內(nèi)容,一般有靜態(tài)的摘要和動態(tài)的摘要,靜態(tài)的摘要從原始視頻中抽取一些具有代表性的關(guān)鍵幀以生成摘要,而動態(tài)的摘要是由原始視頻的一些視頻片段組成的。相對于動態(tài)視頻摘要而言,靜態(tài)視頻摘要不受視頻時序的約束,故形式更加直觀且靈活[2]?；诖?本文主要研究靜態(tài)視頻摘要。

靜態(tài)視頻摘要即關(guān)鍵幀的提取,最早可追溯到20世紀(jì)90年代。至今針對此問題,許多學(xué)者進(jìn)行了大量的研究并取得了一定的成果。比較典型的有基于聚類的方法,文獻(xiàn)[3]提出了VSUMM(video SUMMarization)方法,該方法基于幀圖片的顏色特征對視頻幀進(jìn)行K均值聚類,選取每個類的中心作為關(guān)鍵幀,從而生成視頻摘要;文獻(xiàn)[4]采用FCM(fuzzy C means clustering)算法對幀圖片進(jìn)行聚類求得各個類的隸屬度矩陣，將隸屬度高的幀作為關(guān)鍵幀;文獻(xiàn)[5]提出了STIMO 方法,該方法通過提取原始視頻幀的顏色特征,再使用FPF(farthest point-first) 算法對視頻幀進(jìn)行聚類,選取聚類中心并去除無意義的冗余關(guān)鍵幀;文獻(xiàn)[6]在DBSCAN算法的基礎(chǔ)上進(jìn)行改進(jìn),提出了新的對視頻進(jìn)行聚類的VSCAN 方法,最后選擇聚類中心作為關(guān)鍵幀;文獻(xiàn)[7]基于聚類方法做出了嘗試,首先對視頻幀進(jìn)行聚類,將每一類作為GOPs(groups of pictures),對GOPs 通過一種迭代算法進(jìn)行排序,再根據(jù)摘要長短需求選取合適的關(guān)鍵幀。基于圖模型的方法將視頻幀間的關(guān)系以圖的形式表達(dá),圖的頂點(diǎn)即為視頻幀,連接頂點(diǎn)的邊一般為幀間的相似性度量,最后通過相關(guān)目標(biāo)函數(shù)的優(yōu)化計算生成關(guān)鍵幀。文獻(xiàn)[8]對視頻采樣,提取采樣視頻幀的顏色特征,將每一個采樣視頻幀看作德勞內(nèi)(Delaunay) 圖的頂點(diǎn)并構(gòu)建德勞內(nèi)圖,通過移除德勞內(nèi)圖中的部分邊進(jìn)行聚類,最后選取距離聚類中心最近的一幀作為關(guān)鍵幀;文獻(xiàn)[9]在上述方法的基礎(chǔ)上進(jìn)行改進(jìn),在移除德勞內(nèi)圖中的部分邊進(jìn)行聚類時,加入了結(jié)構(gòu)約束,進(jìn)一步保證了能夠更好地保留類內(nèi)的邊,同時移除類間的邊;文獻(xiàn)[10]通過視頻幀構(gòu)建K近鄰圖,將其分割為多個子圖,最后通過一個混合模型選取關(guān)鍵幀;文獻(xiàn)[11]通過構(gòu)建骨架(skeleton) 圖,使用最小生成樹(MST) 的方法對頂點(diǎn)進(jìn)行篩選排序,從而選取關(guān)鍵幀集合。

這些傳統(tǒng)的基于聚類方法和圖模型方法的有效性都已得到驗(yàn)證,然而其實(shí)都有各自的缺陷。例如聚類方法中往往要人為設(shè)定初始聚類中心、確定關(guān)鍵幀數(shù)目、選擇閾值等，關(guān)鍵幀提取一定程度上受到主觀因素影響；雖然層次聚類方法[12-13]無需提前設(shè)定聚類中心和關(guān)鍵幀數(shù)目,但是其有著計算復(fù)雜度大、合并點(diǎn)或分裂點(diǎn)難以選擇的缺點(diǎn)。而基于圖模型的方法共同點(diǎn)是將視頻幀看作圖的頂點(diǎn),通過邊的權(quán)重來衡量2個頂點(diǎn)的相似性,實(shí)際情況中,一個視頻的視頻幀數(shù)量往往是相當(dāng)大的,如果考慮所有的幀圖片間的關(guān)系,那么圖模型會變得相當(dāng)復(fù)雜,計算量也會加大。

本文將聚類方法和圖模型的方法結(jié)合并優(yōu)化,提出了一種新的基于有向圖最短路徑算法的視頻摘要方法(shortest path for video summary,SPVS)。SPVS方法先將視頻分段處理,之后在分段內(nèi)部進(jìn)行聚類操作,在構(gòu)建圖模型時引入了頂點(diǎn)連接的約束條件,大大降低了圖模型的復(fù)雜度,最后將關(guān)鍵幀提取問題轉(zhuǎn)化為最短路徑求解問題。

1 SPVS算法

SPVS算法的主要步驟如圖1所示。

圖1 SPVS算法流程

對于輸入的視頻首先進(jìn)行分段處理,也就是將其分為n個分段,從每個分段文章中提取幀圖片的顏色特征并進(jìn)行一次聚類處理,在每個分段中選取距離聚類中心最近的20張幀圖片并以此構(gòu)建有向圖,最后轉(zhuǎn)化為最短路徑問題,通過求解結(jié)果生成視頻摘要。

1.1 視頻分段處理

靜態(tài)視頻摘要的生成可以分為2個步驟:① 視頻的分段處理; ② 基于分段的結(jié)果在每段中進(jìn)行關(guān)鍵幀的提取。將視頻分成合適的分段對于最后的摘要生成是有好處的,傳統(tǒng)的方式有均勻采樣或者隨機(jī)采樣,這種隨意的分段方式顯然不能很好地符合視頻的真實(shí)情況;也有基于視頻邊界檢測的方法[14-15]找到視頻中鏡頭突變的幀作為邊界來分割視頻,這種方法對于一些編輯過的有明顯的鏡頭切換的視頻效果較好,而對于未編輯過的用戶視頻往往并不能合適地進(jìn)行分段。由于人們在觀看視頻時容易受到運(yùn)動信息變化的影響,文獻(xiàn)[16]提出了一種稱之為SuperFrame的視頻分段方法,初始對視頻幀均勻采樣,通過計算采樣位置的前向信息、后向信息以及運(yùn)動信息對目標(biāo)函數(shù)進(jìn)行優(yōu)化并使之收斂,最后確定視頻的分段位置，本文在分段處理上采用這種方法。

1.2 提取特征和段內(nèi)聚類

在視頻摘要領(lǐng)域,圖片顏色特征、紋理特征、運(yùn)動估計特征被廣泛使用, 其中顏色特征和運(yùn)動特征起著主導(dǎo)作用。本文將采用顏色特征,與一般方法中使用的顏色直方圖形式不同,本文采用熵值的形式,圖像熵反映了圖像包含的信息量,通過對RGB 3個不同顏色強(qiáng)度平面計算熵值,可以得到圖像傳送的平均信息,即

Efi=[ErEgEb]

(1)

其中:Efi為視頻幀序列中第i幀的特征向量;Er為圖像在紅色平面的熵值;Eg為圖像在綠色平面的熵值;Eb為圖像在藍(lán)色平面的熵值。

將視頻序列分成了n個分段,在每段中提取幀圖片的熵值信息,并在分段內(nèi)部進(jìn)行聚類操作。本文使用FCM聚類算法,FCM算法是一種以隸屬度來確定每個數(shù)據(jù)點(diǎn)屬于某個聚類程度的算法。該算法首先用0～1的隨機(jī)數(shù)初始化隸屬度矩陣,且矩陣所有元素和為1,然后開始迭代直到目標(biāo)函數(shù)收斂到極小值,根據(jù)迭代結(jié)果,由最后的隸屬矩陣確定數(shù)據(jù)所屬的類,顯示最后的聚類結(jié)果。本文使用FCM聚類算法的目標(biāo)函數(shù)定義為:

(2)

(3)

(4)

根據(jù)最后聚類結(jié)果在每個分段中選取隸屬度最高的20張圖片,n個分段后得到圖片幀集合S={S1,S2,S3,…,Sn}作為摘要候選幀。

1.3 構(gòu)建有向圖

對于集合S中的幀圖片,本文提取圖片的加速穩(wěn)健特征(speeded up robust features, SURF),其結(jié)果是一個64維的向量,代表一張圖片幀。

SURF特征是一種穩(wěn)健的圖像識別和描述算法,不僅擁有尺度不變性,而且相對于尺度不變特征變換(scale-invariant feature transform,SIFT)而言更加高效。將幀集合Si作為一個整體,基于SURF特征計算兩兩幀集合中圖片的相似度Aij,且0≤Aij≤1,構(gòu)建相似度矩陣。如對于集合S1、S2,相似度矩陣如下:

(5)

其中,A11為集合S1中的第1幀和集合S2中的第1幀的相似度。

有向圖的連接關(guān)系可以用一個鄰接矩陣M來表示,矩陣M中元素Mij,即頂點(diǎn)Si到頂點(diǎn)Sj的連接的邊。若邊存在的話,則Mij=w(Si,Sj);不存在,則置為∞。本文將集合S中所有頂點(diǎn)考慮進(jìn)來,找到它們兩兩的連接關(guān)系,生成鄰接矩陣并構(gòu)建有向圖。在實(shí)際構(gòu)建有向圖時,發(fā)現(xiàn)如果對于所有頂點(diǎn)都產(chǎn)生連接的話將是不符合實(shí)際的。對于本文的任務(wù)來說,需要一定的約束條件。首先,視頻是有時序的,Mij若存在,則j>i;其次,如果時間上相隔一定距離的頂點(diǎn)中幀圖片差異很大,那么此時相似度φ會很小,它們連接的邊的權(quán)重w也會很小,甚至?xí)∮谥虚g頂點(diǎn)的連接邊的和,此時計算最短路徑將會錯誤地淘汰中間頂點(diǎn),從而使最后產(chǎn)生的摘要缺少信息,基于此,定義一個閾值Tmin,Mij若存在,則Mij≥Tmin;最后,在實(shí)驗(yàn)時發(fā)現(xiàn),對于有些視頻,基于2個約束條件構(gòu)建的有向圖在尋找最短路徑時,還是會或多或少地錯誤淘汰一些關(guān)鍵頂點(diǎn),為此在第2個約束條件的基礎(chǔ)上再加上條件,即若Mij存在,則對于所有的i≤k≤j,都有w(Si,Sk)≥Tmin。

綜上所述,本文將每個視頻分段視為頂點(diǎn),相似度作為連接頂點(diǎn)的邊,并且w(Si,Sj)=min(Aij),在約束條件下構(gòu)建了有向圖,成功將關(guān)鍵幀提取問題轉(zhuǎn)化為最短路徑求解問題。

構(gòu)建有向圖時,邊(Si,Sj)存在連接的3個約束條件為：

1.4 最短路徑求解

有向圖構(gòu)建后只要計算第1個頂點(diǎn)到最后一個頂點(diǎn)的最短路徑,路徑上的幀圖片即選為關(guān)鍵幀。因?yàn)閳D中頂點(diǎn)是一個20幀圖片的集合,所以選最短路徑時頂點(diǎn)內(nèi)可能會有2張幀圖片被選擇,本文認(rèn)為頂點(diǎn)內(nèi)幀圖片是相似的,基于聚類結(jié)果此時只要選取隸屬度高的幀圖片即可。最短路徑確保了最后生成的關(guān)鍵幀圖片的獨(dú)特性,具有很低的冗余度。

關(guān)于最短路徑求解問題的算法有很多,對于本文的有向圖來說,由于沒有負(fù)權(quán)值且為單源的,可以采用Dijkstra算法。Dijkstra算法采用的是一種貪心的策略,聲明一個數(shù)組dis來保存源點(diǎn)到各個頂點(diǎn)的最短距離和一個頂點(diǎn)的集合T保存已經(jīng)找到的最短路徑,其主要步驟如下:

(1) 初始時,源點(diǎn)S1的路徑權(quán)重被賦為 0 (dis[S1]=0)。若對于頂點(diǎn)S1存在能直接到達(dá)的邊(S1,Si),則把dis[Si]設(shè)為w(S1,S2),同時把所有其他(S1不能直接到達(dá)的)頂點(diǎn)的路徑長度設(shè)為無窮大。初始時,集合T只有頂點(diǎn)S1,然后,從dis數(shù)組選擇最小值,則該值就是源點(diǎn)S1到該值對應(yīng)的頂點(diǎn)的最短路徑,并且把該點(diǎn)加入到T中。

(2) 確認(rèn)新加入的頂點(diǎn)是否可以到達(dá)其他頂點(diǎn),并且通過該頂點(diǎn)到達(dá)其他點(diǎn)的路徑長度是否比源點(diǎn)直接到達(dá)短,如果是,那么就替換這些頂點(diǎn)在dis中的值。

(3) 從更新后的dis中找出最小值,重復(fù)上述步驟,直到集合T中包含了圖的所有頂點(diǎn)。

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

為了驗(yàn)證所提SPVS方法的有效性,在Open-Video數(shù)據(jù)集和 SumMe數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。Open-Video數(shù)據(jù)集是視頻摘要算法使用的一個經(jīng)典的數(shù)據(jù)集,采用其中的50個不同種類的視頻進(jìn)行測試,每個視頻長度大約為2～5 min,同時該數(shù)據(jù)集對每個視頻給出了由用戶手工產(chǎn)生的摘要作為真值。SumMe數(shù)據(jù)集包含25個用戶視頻,即未編輯過的視頻,內(nèi)容有料理、運(yùn)動等,每個視頻長度在1.5～6.5 min之間。

視頻摘要評價標(biāo)準(zhǔn)主要有主觀評價和客觀評價2種。主觀評價即讓用戶對生成的視頻摘要進(jìn)行主觀判斷,如給生成的摘要打分決定摘要的好壞,是一種直觀而且有效的方法?？陀^評價則是通過制定評價函數(shù)來評價視頻摘要的好壞,比較普遍的評價函數(shù)有準(zhǔn)確率(CUSA)和錯誤率(CUSE)。對于Open-Video數(shù)據(jù)集，由于有用戶摘要作為對照,因此采用客觀評價標(biāo)準(zhǔn)；對于SumMe數(shù)據(jù)集由于缺少真值將采用主觀評價標(biāo)準(zhǔn)。

準(zhǔn)確率為:

CUSA=NmAS/NUS

(6)

錯誤率為:

(7)

2.1 Open-Video數(shù)據(jù)集實(shí)驗(yàn)

對于Open-Video數(shù)據(jù)集,很多方法都曾證明了其有效性,本文將使用客觀評價的方法分別與OV[17]、STIMO[5]、VSUMM[3]、FCM[4]、MST[11]5種方法進(jìn)行對比,以證明所提SPVS算法的優(yōu)良性能,具體的數(shù)據(jù)結(jié)果見表1所列。

表1 Open-Video數(shù)據(jù)集實(shí)驗(yàn)結(jié)果對比

由表1可知,在準(zhǔn)確率方面SPVS算法僅略遜于VSUMM算法,比STIMO算法更是高出了25%,而在錯誤率方面,SPVS算法也有良好的表現(xiàn),在幾個算法中僅比STIMO高出1%。這說明SPVS算法能在保持低的錯誤率的同時仍能擁有較高的準(zhǔn)確率,整體來說性能上優(yōu)于其他幾個算法。為了更直觀地將本文所提的SPVS算法與其他算法進(jìn)行對比,本文將SPVS算法與其他對比算法在2個視頻上的摘要結(jié)果進(jìn)行直觀對比,如圖2所示。

圖2 第9個、第34個視頻上視頻摘要結(jié)果對比

2.2 SumMe數(shù)據(jù)集實(shí)驗(yàn)

對于SumMe數(shù)據(jù)集,本文采用主觀評價來評價SPVS算法生成摘要的好壞,制定3個評價等級,分別為較差、普通、較好。20個聲稱經(jīng)常瀏覽各種視頻并對視頻摘要有一定了解的志愿者參與了本次實(shí)驗(yàn)。為了結(jié)果更加直觀且方便統(tǒng)計,使用數(shù)值L來表示算法生成摘要所獲得的分?jǐn)?shù),即

L=x/y

(8)

其中:x為用戶對所生成摘要評價為較好的個數(shù);y為參與的志愿者的數(shù)量。實(shí)驗(yàn)結(jié)果見表2所列。

由表2可知,用戶對于所提算法生成的摘要的評價主要集中在普通和較好等級上,且兩者平均個數(shù)相差不大,較差的評價所占比例較小,較好的評價所占比例平均為30.6%,其中最高比例更是達(dá)到了85%,這表明了對于未編輯的用戶視頻,本文所提SPVS算法仍然具有相當(dāng)不錯的表現(xiàn),進(jìn)一步證明了SPVS算法的優(yōu)越性。

表2 SumMe數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

3 結(jié) 論

本文通過將聚類方法和圖模型的方法相結(jié)合并優(yōu)化,提出了一種新的基于最短路徑算法的靜態(tài)視頻摘要方法(SPVS)。SPVS方法將視頻摘要的關(guān)鍵幀提取問題轉(zhuǎn)化為有向圖的最短路徑求解問題,通過相似性度量找到的最短路徑上的關(guān)鍵幀具有良好的代表性。在2個數(shù)據(jù)集上的大量主客觀實(shí)驗(yàn)和與其他經(jīng)典方法的對比也證明了所提方法的良好性能。