張 芯，謝毓湘，欒悉道

(1.國防科學(xué)技術(shù)大學(xué)信息系統(tǒng)工程重點實驗室，湖南 長沙 410073;2.長沙大學(xué)信息與計算科學(xué)系，湖南 長沙 410073)

0 引言

視頻摘要，即以自動或半自動的方式對視頻的結(jié)構(gòu)和內(nèi)容進行分析，從原視頻中提取出有意義的部分，并將它們以某種方式進行組合，形成簡潔的、能夠充分表現(xiàn)視頻語義內(nèi)容的概要［1］。它是對長視頻內(nèi)容的簡短總結(jié)，通常用一段靜態(tài)或者動態(tài)的圖像序列來表示，并對原始信息予以保留。視頻摘要技術(shù)可以粗略的分為2大類型:靜態(tài)摘要和縮略視頻［2］。靜態(tài)摘要最常用的生成策略是從原始視頻中提取出一幀或多幀圖像序列來表示視頻的原始內(nèi)容，如文獻［3-5］中使用的方法。靜態(tài)摘要通常是基于較底層的特征信息［2，5］(顏色、紋理等)進行關(guān)鍵幀選取，而縮略視頻是基于視頻中重要片段的選?。?0］，所選取的片段通常為小的視頻片段。

近年來，視頻摘要技術(shù)快速發(fā)展，研究人員提出了很多視頻摘要生成方法。文獻［3］將主成分分析法和顏色直方圖混合來構(gòu)建三維的特征空間，使用2D-KD樹對特征信息進行索引查詢，提取出最優(yōu)的視頻關(guān)鍵幀;文獻［4］中使用顏色直方圖作為圖像特征，利用改進型的k均值算法對特征進行聚類，提出了一種面向多類型快速視頻摘要方法。文獻［5］使用FPF(最遠點開始)和M-FPF(改進型最遠點開始)方法來進行視頻摘要的生成。文獻［6］中使用DC圖像和ZNCC(零均值歸一化互相關(guān)方法)建立幀圖像之間的相似度模型，通過圖像間的差異確定GOP(圖像組)的個數(shù)，最終選取每個圖像組中的中間幀作為關(guān)鍵幀。文獻［7］為克服使用一種圖像特征內(nèi)容表現(xiàn)不強的缺點，對局部特征的提取和使用方法進行改進，將局部特征和全局特征進行融合，利用聚類思想提取視頻中的關(guān)鍵幀。文獻［8］針對動畫視頻自身的特點，對視頻進行結(jié)構(gòu)分析和內(nèi)容重要度計算，提出一種面向動畫視頻的摘要方法。

目前，大部分研究均是基于底層圖像特征(如顏色、紋理等)［3-8］，采用聚類等方法選出視頻代表幀或片段，利用故事板等表現(xiàn)技術(shù)生成瀏覽型或播放型的視頻摘要。這些方法的特點是視頻摘要生成效率較高，但摘要信息量較低，對原始視頻內(nèi)容表現(xiàn)能力較差。特別是針對長視頻，由于其內(nèi)容變化多，很難在保證視頻摘要生成速度的同時，具有很強的內(nèi)容表現(xiàn)力。

針對上述問題，本文提出一種信息量和摘要生成速度均衡的視頻摘要方法。第一步，使用預(yù)采樣技術(shù)對視頻進行預(yù)處理，降低視頻處理幀數(shù)量;第二步，提取視頻幀的旋轉(zhuǎn)不變均勻局部二值模式特征，使用該特征來表示視頻的主要內(nèi)容;第三步，使用改進型k均值算法對特征集合進行聚類，將具有相同語義的幀分布在同一個聚類中。第四步，使用“重要度”函數(shù)判定不同語義聚類的“重要度”，從“重要”聚類中選取距聚類中心最近的幀作為關(guān)鍵幀。第五步，使用故事板表現(xiàn)方式將選取出的關(guān)鍵幀按照時間順序排序，生成靜態(tài)瀏覽型的視頻摘要。視頻摘要算法結(jié)構(gòu)如圖1所示。

圖1 視頻摘要算法結(jié)構(gòu)圖

1 基于局部二值模式的視頻摘要模型

1.1 問題描述

在靜態(tài)摘要方法中，給定具有N幀的視頻片段，需要求解出最優(yōu)的采樣M(M＜N)來對N幀視頻內(nèi)容進行表現(xiàn)，同時需要保證視頻的失真率最?。?］。

假設(shè)X為初始樣本集合，表示為:其中，xt(1 ≤t≤N)表示特征向量集合中第t幀圖像特征。

X的一部分可以表示為Q:

其中 Qi(1 ≤i≤M)表示第i個幀聚類集合。Qi∩Qj= φ，?i，j且 i≠j。

1.2 視頻預(yù)處理

視頻預(yù)處理是視頻摘要生成的第一步。通過視頻預(yù)處理可以將視頻分割成鏡頭片段或幀序列集合，以方便對視頻操作。視頻預(yù)處理技術(shù)可以粗略分為2類［10］，視頻邊界探測技術(shù)和預(yù)采樣技術(shù)。最常用的視頻預(yù)處理技術(shù)是視頻邊界探測技術(shù)，其原理是對視頻進行時間序列上的分析。預(yù)采樣技術(shù)不需要對視頻進行時間序列上的分析，它只需要對視頻進行單獨的幀提取，通過調(diào)節(jié)預(yù)抽樣率來降低待分析視頻幀數(shù)量。由于視頻邊界探測方法對鏡頭探測技術(shù)依賴性較大，而鏡頭切換的自動檢測一直是視頻分析領(lǐng)域技術(shù)難點，所以本文選取預(yù)抽樣技術(shù)來對視頻進行預(yù)處理。

對于時間較長的視頻片段，視頻分析采用預(yù)抽樣方法較好，這在很大程度上降低了需要計算的幀數(shù)量。但是，一個不可忽視的因素是，抽樣率的大小會直接影響最終生成摘要對視頻內(nèi)容的表現(xiàn)能力。所以需要在摘要信息量和摘要生成速度上均衡，選取合適的抽樣率對視頻進行預(yù)處理。經(jīng)過試驗分析，本文采用的抽樣率為N=1/30。

1.3 視頻幀特征提取

全局特征如顏色特征，由于其提取速度較快且對圖像內(nèi)容有一定表現(xiàn)能力，所以在特征提取過程中應(yīng)用較為廣泛，文獻［3-6］均采用顏色特征來對視頻內(nèi)容表示。雖然全局特征提取速度較快，但對視頻內(nèi)容表現(xiàn)能力較差。文獻［7］嘗試將全局特征與局部特征融合，使用融合后的混合特征表示視頻內(nèi)容，該方法需要對2種特征分別進行提取并融合。融合后的特征在內(nèi)容表現(xiàn)上得到加強，但摘要生成效率降低。針對這種情況，本文提出基于局部二值模式(Local Binary Pattern)的均勻模式［11-12］對視頻內(nèi)容進行表現(xiàn)。

LBP算子為一種灰度尺度不變的紋理算子，是從局部鄰域紋理的普通定義得來的。其基本思想是:用其中心像素的灰度值作為閾值，與它的鄰域相比較得到的二進制碼來表述局部紋理特征。圖像區(qū)域LBP特征描述如圖2所示。

圖2 LBP算子示意圖

基本的LBP特征是對一個3×3鄰域的二進制進行描述，其計算過程如下:

Step1 將圖2所示的某3×3鄰域的周圍8個像素點的灰度值分別與中心像素點的灰度值進行比較，根據(jù)其大小關(guān)系對這8個像素點進行二值化。如果該像素點的灰度值大于中心像素點的灰度值，則將其置為0，否則置為1。

Step2 由圖2可知，該圖的 LBP模式為11110001，即1+2+4+16+128=151。

為了提高基本LBP特征的表達能力，Ojala等［11］對基本LBP特征進行了擴展，計算LBP特征時不再局限于3×3鄰域，而是設(shè)定一個采樣半徑R和采樣點數(shù)P，并以中心點為圓心，R為半徑的圓周上等間隔地采樣P個點。這P個點的灰度值通過與中心點的灰度值比較大小進行二值化?，F(xiàn)在以P=8，R=1的情況為例，說明擴展LBP特征的計算過程。假設(shè)中心像素點的灰度值為gc，8個采樣的像素點的灰度值分別為 g0，g1，...，g7，則中心像素點周圍區(qū)域的LBP特征計算公式為:

考察LBP的定義，發(fā)現(xiàn)LBPP，R可以產(chǎn)生2p種不同輸出，對應(yīng)了局部近鄰集中P個像素形成的2p個不同的二進制形式。很顯然，圖像發(fā)生旋轉(zhuǎn)時，圓形鄰域的灰度值gi在以gc為中心半徑為R的圓周上移動。由公式(3)可以看出，只要s( gi-gc)不全為0或者不全為1，圖像的旋轉(zhuǎn)就會得到不同的LBP值，因此，Ojala等人又對LBP算法進行了擴展，提出了具有旋轉(zhuǎn)不變性的 LBP(Rotation Invariant LBP)［11］，即不斷旋轉(zhuǎn)圓形鄰域得到一系列初始定義的LBP值，取其最小值作為該鄰域的LBP值:

其中，gp=g0。滿足U≤2的所有模式稱為均勻模式。在P鄰域中，滿足 U≤2的所有模式的個數(shù)為P( P-1)+2，再進一步將它們旋轉(zhuǎn)到最小值后，具有旋轉(zhuǎn)不變性的均勻模式(Rotation Invariant Uniform Pattern)的個數(shù)則為P+1。因此，任何均勻模式的LBP值都可以通過統(tǒng)計二值編碼中l(wèi)的個數(shù)得到，而非均勻模式的LBP值均等于P+1:

LBP算子是一種無參數(shù)的方法，所以在應(yīng)用過程中不需要對它的分布進行預(yù)先假設(shè)。與傳統(tǒng)的全局特征如顏色直方圖相比，LBP特征具有尺度不變，灰度不變性，對內(nèi)容表現(xiàn)較強等優(yōu)點;與局部特征例如經(jīng)典的SIFT特征相比，LBP特征具有結(jié)構(gòu)簡單，提取速度快的特點，很好地克服了全局特征內(nèi)容表現(xiàn)力差，局部特征提取速度慢等缺點。相比于LBP特征，旋轉(zhuǎn)不變均勻模式LBP特征二進制模式的種類大大減少，而不會丟失任何信息。由于原始的LBP算子對紋理特征的描述有限，而旋轉(zhuǎn)不變均勻模式不僅可以有效地描述出圖像的大部分紋理特征，而且能明顯減少特征的數(shù)量。綜合分析，本實驗采用尺度為(8，1)的旋轉(zhuǎn)不變均勻模式LBP算子。

1.4 特征聚類

獲取幀圖像顏色特征信息后，需要對圖像特征信息進行語義層面的分析，本文擬使用聚類方法對圖像特征信息進行處理。k均值聚類方法是一種簡單的無監(jiān)督學(xué)習(xí)算法，它聚類速度快，但k均值方法聚類效果對初始聚類數(shù)目要求較高。例如，聚類初始個數(shù)k=5，那么k均值算法會將特征點迭代的放入這5個聚類中，直到滿足聚類的終止條件。因此，聚類初始數(shù)目的設(shè)定，直接影響最終聚類效果。為了克服k均值聚類方法這一缺點，優(yōu)化聚類結(jié)果，本文根據(jù)視頻內(nèi)容不同［4］，動態(tài)的生成聚類數(shù)目k。

其中1≤i≤N，τ表示幀圖像內(nèi)容變化閾值。

通過公式(7)可以動態(tài)確定聚類數(shù)目k。如果連續(xù)2幀圖像之間LBP特征的歐式距離大于閾值τ，聚類數(shù)目k則加1;如果小于τ，聚類數(shù)目k不變(初始聚類數(shù)目k=1)。因此，聚類數(shù)目k的僅僅依賴于閾值τ，經(jīng)過實驗測試，本文設(shè)定閾值τ為0.5。在實驗過程中，對不同時長、內(nèi)容的視頻，通過進行幀圖像特征距離計算獲取聚類k數(shù)目。

1.5 關(guān)鍵幀提取

通過上一步的計算之后，確定聚類數(shù)目k，并對獲取到的LBP特征進行聚類。為了描述獲取聚類的“重要度”，本文引入聚類重要度函數(shù)I( i)對聚類的“重要度”進行評測［13］。其計算公式是:

其中xi表示第i個聚類所包含的幀數(shù)目;m表示聚類包含的平均幀數(shù)目;σ是聚類幀數(shù)目的偏差，其計算公式為:

利用式(8)和式(9)計算每個聚類的“重要度”值，求取所有聚類的“重要度”平均值，再根據(jù)聚類“重要度”平均值設(shè)置一個閾值。如果聚類“重要度”值大于該閾值，則提取距聚類中心最近的幀作為關(guān)鍵幀，生成最終的視頻摘要。最后，將選取的關(guān)鍵幀按照時間序列排序，利用故事板表現(xiàn)技術(shù)生成靜態(tài)瀏覽型視頻摘要。

2 實驗結(jié)果分析

為了與不同視頻摘要方法進行對比，本文采用與文獻［4-6］統(tǒng)一的實驗數(shù)據(jù)和評價標(biāo)準(zhǔn)。實驗所用數(shù)據(jù)為開放視頻項目(Open Video Project)庫中的50個視頻片段，這些視頻片段所采用數(shù)據(jù)相同，對比性強。OV庫中視頻統(tǒng)一為 MEPG-1格式(30 fps，352×240pixels)，選取出來的視頻片段有以下幾種:紀(jì)錄片、教育片、歷史片、演講。

本文使用用戶摘要對比方法來對自動生成的視頻摘要質(zhì)量進行評價，該用戶摘要由50個用戶手動生成。其中，每一個用戶觀看5個視頻片段并手動生成視頻摘要，即每一個視頻都有5個用戶摘要用來進行對比。在與其它3種方法進行對比之前，首先對本文2種不同的方法進行對比。L1方法在每個聚類選取出一個關(guān)鍵幀，L2方法在每個“重要”聚類中選取一個關(guān)鍵幀，將這2種方法與其它3種自動摘要方法［4-6］進行對比分析。使用正確率(CUSA)和錯誤率(CUSE)兩個指標(biāo)進行評價對視頻摘要的質(zhì)量評價方法。

表1 不同方法之間的平均準(zhǔn)確率CUSA和平均錯誤率CUSE

表2 不同方法在置信區(qū)間為98%條件下，平均準(zhǔn)確率CUSA的差異

表3 各種方法在置信區(qū)間為98%條件下，平均錯誤率CUSE的差異

表1實驗結(jié)果表明，L1方法的摘要準(zhǔn)確率最高，L2方法的摘要錯誤率最低。為了驗證這些結(jié)果的數(shù)據(jù)有效性，分別計算2種方法的置信區(qū)間。如果該置信區(qū)間包含0，那么這2種方法在該置信水平差異不明顯;如果置信區(qū)間不包含0，則表明2種方法中一種比另外一種要好。表2和表3給出了方法L1與其它方法的對比，其中表2為L1方法與其它方法準(zhǔn)確率的對比，表3表示L1方法與其它方法錯誤率對比。從表1中可以發(fā)現(xiàn)L1方法較L2方法準(zhǔn)確率較高，而L2方法的錯誤率較L1錯誤率更低。在實際應(yīng)用中，若要求高準(zhǔn)確率可以選擇L1方法，對錯誤率有嚴(yán)格限制，則可以選擇L2方法進行摘要生成。圖3為OV數(shù)據(jù)庫摘要，VSUMM摘要方法以及本文L1方法3種不同方法生成的視頻摘要。

圖3 視頻Drift Ice as a Geologic Agent，segment 8使用不同方法生成的視頻摘要

3 結(jié)束語

針對靜態(tài)視頻摘要信息量和生成速度問題，本文提出了一種基于旋轉(zhuǎn)不變均衡局部二值模式的摘要方法。該方法首先對視頻進行預(yù)處理，降低分析處理數(shù)據(jù)量。使用旋轉(zhuǎn)不變均衡局部二值模式特征對幀圖像進行描述，利用改進的k均值算法動態(tài)得到聚類數(shù)目k，獲取到相對應(yīng)的語義相關(guān)聚類，根據(jù)引進的“重要度”函數(shù)從聚類集合中選取“重要聚類”。選取距聚類中心最近幀作為關(guān)鍵幀，將關(guān)鍵幀按照時間序列排序，使用故事板表現(xiàn)方式生成瀏覽型的視頻摘要?；贠pen Video Project項目數(shù)據(jù)來對實驗方法效果進行驗證，實驗結(jié)果表明，該方法生成的視頻摘要在摘要信息量和生成速度上表現(xiàn)較好，用戶滿意程度較高。

［1］Truong B T，Venkatesh S.Video abstraction:A systematic review and classification［J］.ACM Transactions on Multimedia Computing， Communications and Applications，2007，3(1):3.

［2］Cotsaces C，Nikolaidis N，Pitas I.Video shot boundary detection and condensed representation:A review［J］.IEEE Signal Processing Magazine，2006，23(2):28-37.

［3］Jiang Junfeng，Zhang Xiaoping.Gaussian mixture vector quantization-based video summarization using independent component analysis［C］//IEEE International Workshop on Multimedia Signal Processing(MMSP'10).2010:443-448.

［4］De Avila Sandra Eliza Fontes，Lopes Ana Paula Brand?o，da Luz Jr Antonio，et al.VSUMM:A mechanism designed to produce static video summaries and a novel evaluationmethod［J］.Pattern Recognition Letters，2011，32(1):56-68.

［5］Furini Marco，Geraci Filippo，Montangero Manuela，et al.STIMO:STIll and MOving video storyboard for the Web scenario［J］.Springer Netherlands，2010，46(1):47-69.

［6］Almeida Jurandy，Leite Neucimar J，Torres Ricardo da S.VISON:Video summarization for online applications［J］.Pattern Recognition Letters，2012，33(4):397-409.

［7］Guan Genliang，Wang Zhiyong，Yu Kaimin，et al.Video summarization with global and local features［C］//IEEE International Conference on Multimedia and Expo Workshops.2012:570-575.

［8］袁志民，吳玲達，陳丹雯，等.一種面向動畫視頻的摘要方法［J］.軟件學(xué)報，2009，20(z1):51-58.

［9］Jiang Junfeng，Zhang Xiaoping.A novel vector quantization-based video summarization method using independent component analysis mixture model［C］//IEEE International Conference on Acoustics，Speech and Signal Processing(ICASSP).2011:1341-1344.

［10］Cernekova Z，Pitas I，Nikou C.Information theory-based shot cut/fade detection and video summarization ［J］.IEEE Trans.Circuits Systems Video Technol，2006，16(1):82-91.

［11］Ojala T，Pietikinen M，Maenpaa T.Multiresolution grayscale and rotation invariant texture classification with local binary patterns［J］.IEEE Transaction on Pattern Analysis and Machine Intelligence，2002，24(7):971-987.

［12］王玲.基于LBP的特征提取研究［D］.北京:北京交通大學(xué)，2009.

［13］曹建榮，蔡安妮.基于支持向量機的視頻關(guān)鍵幀語義提取［J］.北京郵電大學(xué)學(xué)報，2006，29(2):123-126.