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

葛 釗, 趙 燁

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

0 引 言

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

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

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

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

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

1 SPVS算法

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

圖1 SPVS算法流程

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

1.1 視頻分段處理

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

1.2 提取特征和段內聚類

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

Efi=[ErEgEb]

(1)

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

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

(2)

(3)

(4)

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

1.3 構建有向圖

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

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

(5)

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

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

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

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

1.4 最短路徑求解

有向圖構建后只要計算第1個頂點到最后一個頂點的最短路徑,路徑上的幀圖片即選為關鍵幀。因為圖中頂點是一個20幀圖片的集合,所以選最短路徑時頂點內可能會有2張幀圖片被選擇,本文認為頂點內幀圖片是相似的,基于聚類結果此時只要選取隸屬度高的幀圖片即可。最短路徑確保了最后生成的關鍵幀圖片的獨特性,具有很低的冗余度。

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

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

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

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

2 實驗結果和評價

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

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

準確率為:

CUSA=NmAS/NUS

(6)

錯誤率為:

(7)

2.1 Open-Video數據集實驗

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

表1 Open-Video數據集實驗結果對比

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

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

2.2 SumMe數據集實驗

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

L=x/y

(8)

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

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

表2 SumMe數據集實驗結果

3 結 論

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