葛 釗, 趙 燁

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

0 引 言

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

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

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

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

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

1 SPVS算法

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

圖1 SPVS算法流程

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

1.1 視頻分段處理

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

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

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

Efi=[ErEgEb]

(1)

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

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

(2)

(3)

(4)

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

1.3 構(gòu)建有向圖

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

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

(5)

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

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

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

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

1.4 最短路徑求解

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

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

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

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

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

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

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

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

準(zhǔn)確率為:

CUSA=NmAS/NUS

(6)

錯(cuò)誤率為:

(7)

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

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

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

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

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

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

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

L=x/y

(8)

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

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

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

3 結(jié) 論

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