一種基于局部二值模式的關(guān)鍵幀提取方法

張 芯，謝毓湘，欒悉道

(1.國(guó)防科學(xué)技術(shù)大學(xué)信息系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室，湖南 長(zhǎng)沙 410073;2.長(zhǎng)沙大學(xué)信息與計(jì)算科學(xué)系，湖南 長(zhǎng)沙 410073)

0 引言

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

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

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

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

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

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

1.1 問(wèn)題描述

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

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

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

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

1.2 視頻預(yù)處理

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

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

1.3 視頻幀特征提取

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

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

圖2 LBP算子示意圖

基本的LBP特征是對(duì)一個(gè)3×3鄰域的二進(jìn)制進(jìn)行描述，其計(jì)算過(guò)程如下:

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

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

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

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

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

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

1.4 特征聚類(lèi)

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

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

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

1.5 關(guān)鍵幀提取

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

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

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

2 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

3 結(jié)束語(yǔ)

針對(duì)靜態(tài)視頻摘要信息量和生成速度問(wèn)題，本文提出了一種基于旋轉(zhuǎn)不變均衡局部二值模式的摘要方法。該方法首先對(duì)視頻進(jìn)行預(yù)處理，降低分析處理數(shù)據(jù)量。使用旋轉(zhuǎn)不變均衡局部二值模式特征對(duì)幀圖像進(jìn)行描述，利用改進(jìn)的k均值算法動(dòng)態(tài)得到聚類(lèi)數(shù)目k，獲取到相對(duì)應(yīng)的語(yǔ)義相關(guān)聚類(lèi)，根據(jù)引進(jìn)的“重要度”函數(shù)從聚類(lèi)集合中選取“重要聚類(lèi)”。選取距聚類(lèi)中心最近幀作為關(guān)鍵幀，將關(guān)鍵幀按照時(shí)間序列排序，使用故事板表現(xiàn)方式生成瀏覽型的視頻摘要?；贠pen Video Project項(xiàng)目數(shù)據(jù)來(lái)對(duì)實(shí)驗(yàn)方法效果進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(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］袁志民，吳玲達(dá)，陳丹雯，等.一種面向動(dòng)畫(huà)視頻的摘要方法［J］.軟件學(xué)報(bào)，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］曹建榮，蔡安妮.基于支持向量機(jī)的視頻關(guān)鍵幀語(yǔ)義提取［J］.北京郵電大學(xué)學(xué)報(bào)，2006，29(2):123-126.