黨宏社, 白　梅

(陜西科技大學(xué) 電氣與信息工程學(xué)院， 陜西 西安　710021)

?

一種基于分層AP的視頻關(guān)鍵幀提取方法研究

黨宏社, 白梅

(陜西科技大學(xué) 電氣與信息工程學(xué)院， 陜西 西安710021)

摘要：為從大量的視頻資源中高效準(zhǔn)確地提取關(guān)鍵幀圖像來(lái)表達(dá)視頻的主要內(nèi)容，針對(duì)傳統(tǒng)AP聚類方法提取關(guān)鍵幀無(wú)法適應(yīng)大規(guī)模圖像集的問(wèn)題，提出一種分層AP的關(guān)鍵幀提取方法.提取所有視頻序列的顏色和紋理特征，將待聚類的圖像集進(jìn)行分層，用傳統(tǒng)AP聚類方法求取每個(gè)圖像子集的聚類中心；用得到的聚類中心進(jìn)行自適應(yīng)的AP聚類，根據(jù)Silhouette指標(biāo)選取最優(yōu)的聚類結(jié)果，即可得到視頻序列的關(guān)鍵幀代表.實(shí)驗(yàn)表明,該方法能快速準(zhǔn)確地提取視頻最優(yōu)關(guān)鍵幀，在保證保真度指標(biāo)的同時(shí)能提高關(guān)鍵幀提取的壓縮比，且適用于不同類型的視頻資源. [5] 范少?zèng)_，彭進(jìn)業(yè)，馮曉，等．基于多核學(xué)習(xí)和AP聚類的圖像選取方法[J]．計(jì)算機(jī)應(yīng)用研究，2011，28(6)：2 365-2 368．

關(guān)鍵詞：視頻檢索； 關(guān)鍵幀； AP； 層次劃分； 聚類

0引言

視頻包含了大量的靜態(tài)幀圖像，同一個(gè)鏡頭下的視頻圖像極其相似，因此含有較多冗余信息.關(guān)鍵幀反映了鏡頭的主要內(nèi)容，提取最具代表性的幀圖像用以實(shí)現(xiàn)視頻檢索以及視頻摘要能達(dá)到更加高效準(zhǔn)確的結(jié)果.

關(guān)鍵幀的提取主要有閾值法、基于鏡頭邊界、運(yùn)動(dòng)分析和聚類的方法.閾值法根據(jù)幀與幀之間的差異與閾值的比較確定關(guān)鍵幀，當(dāng)視頻中有目標(biāo)快速運(yùn)動(dòng)，就會(huì)選擇過(guò)多的關(guān)鍵幀；邊界法依賴于鏡頭檢測(cè)的結(jié)果，所選關(guān)鍵幀不一定最具代表性；基于運(yùn)動(dòng)分析的方法要分析視頻中的運(yùn)動(dòng)[1]，難度與計(jì)算量都較大；聚類方法在模式識(shí)別、圖像處理領(lǐng)域都得到廣泛的應(yīng)用[2]，現(xiàn)在更多學(xué)者將關(guān)鍵幀提取的研究目光聚焦于不同的聚類方法.文獻(xiàn)[3,4]用類模糊C均值聚類和MeanShift可以自適應(yīng)提取關(guān)鍵幀數(shù)量，但均需指定初始聚類中心.文獻(xiàn)[5]利用AP(Affinity Propagation cluster，仿射傳播聚類，簡(jiǎn)稱AP)算法的優(yōu)勢(shì)，不需要指定聚類中心和聚類個(gè)數(shù)，對(duì)圖像進(jìn)行AP聚類再進(jìn)行摘要的選取，可以有效準(zhǔn)確地描述原始圖像集，但是當(dāng)數(shù)據(jù)增多會(huì)消耗更大的內(nèi)存和更多的時(shí)間.

文獻(xiàn)[6]對(duì)于大規(guī)模的數(shù)據(jù)，先利用CVM(Core Vector Machine，核心向量機(jī))進(jìn)行壓縮得到新的數(shù)據(jù)集再采用改進(jìn)的AP聚類算法可提高AP算法的速度.文獻(xiàn)[7]采用分層推舉和全局劃分的方式不僅提高了AP算法的效率，同時(shí)改善了數(shù)據(jù)的聚類效果.

本文對(duì)視頻圖像用AP算法進(jìn)行關(guān)鍵幀提取.視頻包含的圖像數(shù)據(jù)量巨大，直接采用AP聚類計(jì)算復(fù)雜度較大，先對(duì)視頻圖像數(shù)據(jù)量進(jìn)行分層，分為若干個(gè)圖像子集，對(duì)每一個(gè)子集進(jìn)行AP聚類，得到較多的聚類中心，再用這些聚類中心組成的圖像集進(jìn)行二次AP聚類，最終得到的聚類中心即為所要提取的關(guān)鍵幀.

1AP算法簡(jiǎn)介

AP(Affinity Propagation cluster，仿射傳播聚類)算法是2007年在Science上提出的一種新的聚類方法[8].該方法無(wú)需事先指定類別數(shù)目，在聚類初始時(shí)將數(shù)據(jù)集中所有樣本均看作是聚類中心，通過(guò)消息相互傳遞和不斷的迭代過(guò)程，每個(gè)樣本競(jìng)爭(zhēng)成為聚類中心或者選擇至某個(gè)聚類中心的類別，最終獲得若干個(gè)質(zhì)量較高的聚類中心.

假設(shè)有數(shù)據(jù)集L=(X1,X2,…,XN)，N個(gè)樣本點(diǎn)建立N×N的相似度矩陣S.樣本Xi=(x1,x2,…,xn)與Xj=(r1,r2,…,rn)的相似度定義為：

(1)

該值越大表示樣本Xi與Xj越相似.

相似度矩陣S對(duì)角線位置上s(i,i)的大小稱為參考度，決定了樣本Xi能否成為聚類中心，s(i,i)的值越大，表明樣本Xi成為聚類中心的可能性越大[9].

初始化參考度后樣本與樣本之間進(jìn)行吸引度r(i,j)與歸屬度a(i,j)消息的傳遞.

(2)

(3)

(4)

(5)

在初始時(shí)刻，參考度均取相同的值，按照上述公式進(jìn)行迭代更新，在更新的過(guò)程中，為了防止震蕩，引入一個(gè)阻尼因子λ，主要起收斂作用，在迭代過(guò)程中進(jìn)行加權(quán)更新.

ri=(1-λ)ri+λ ri-1

(6)

ai=(1-λ)ai+λ ai-1

(7)

多次迭代，得到收斂的聚類中心.

2基于分層AP的關(guān)鍵幀提取

2.1　特征提取

本文中視頻幀圖像的特征通過(guò)顏色和紋理來(lái)表征.顏色矩利用線性代數(shù)中矩的概念，即圖像中任何的顏色分布都可以用矩來(lái)表示.顏色分布主要集中在低階矩中，將圖像中的顏色分布用顏色一階矩平均值(Average)、顏色二階矩方差(Variance)和顏色三階矩偏斜度(Skewness)來(lái)表示.利用顏色矩對(duì)圖像進(jìn)行描述，無(wú)需量化圖像特征，由于每個(gè)像素具有顏色空間的三個(gè)顏色通道，因此總共用9個(gè)分量來(lái)描述一幅圖像的顏色矩[10].圖像紋理特征反映了圖像區(qū)域內(nèi)重復(fù)出現(xiàn)的結(jié)構(gòu)變化及其灰度或色彩的排列規(guī)律，是圖像的全局統(tǒng)計(jì)特征.基于Gabor濾波器的紋理特征提取方法利用Gabor小波多方向與多尺度的特點(diǎn)，提取相關(guān)紋理信息，但是算法處理過(guò)程中計(jì)算數(shù)據(jù)量大.本文采用灰度共生矩陣反映不同圖像在方向、間隔、變化幅度及快慢上的差異.

通過(guò)顏色和紋理特征提取算法獲取訓(xùn)練樣本中每幅圖像的特征向量R(r1,r2,…,r25)，為防止大數(shù)據(jù)淹沒(méi)小數(shù)據(jù)，按照式(8)作歸一化處理.

(8)

2.2　分層AP算法

2.2.1分層聚類

在處理小規(guī)模數(shù)據(jù)集的聚類實(shí)驗(yàn)結(jié)果中，標(biāo)準(zhǔn)AP算法均取得了較好的效果.但是隨著數(shù)據(jù)規(guī)模增大，樣本數(shù)目達(dá)到3 000以上時(shí)，AP算法的劣勢(shì)也逐漸明顯[11]，因?yàn)锳P算法的核心思想就是每個(gè)數(shù)據(jù)點(diǎn)都是潛在的聚類中心，在計(jì)算過(guò)程中要分別計(jì)算多個(gè)N×N矩陣，樣本與樣本之間消息進(jìn)行兩兩傳遞，需要更多的時(shí)間消耗.視頻關(guān)鍵幀提取是視頻檢索、視頻摘要提取的重要環(huán)節(jié)，速率要求較高，針對(duì)AP聚類算法處理數(shù)據(jù)量巨大的視頻幀圖像效率不高的缺陷，本文采用分層AP聚類算法對(duì)大量的視頻幀圖像進(jìn)行關(guān)鍵幀的提取.

標(biāo)準(zhǔn)AP算法的計(jì)算復(fù)雜度為O(N2)，當(dāng)N增大，算法復(fù)雜度急劇增長(zhǎng).分層AP的主要思想是分層執(zhí)行AP聚類，先對(duì)所有樣本數(shù)據(jù)進(jìn)行層次劃分，將N個(gè)大規(guī)模數(shù)據(jù)樣本劃分為若干個(gè)小規(guī)模子集，對(duì)每個(gè)子集執(zhí)行AP聚類算法，得到每個(gè)子集中具有代表意義的樣本，然后對(duì)這些代表樣本再次進(jìn)行AP聚類，進(jìn)而得到最終的聚類中心.在進(jìn)行分區(qū)大小選擇時(shí)，將子集大小設(shè)置為1 000，即先對(duì)每1 000個(gè)樣本進(jìn)行標(biāo)準(zhǔn)AP聚類，得到進(jìn)行自適應(yīng)AP聚類的新數(shù)據(jù)集.

2.2.2參考度的選取

參考度p又稱偏向參數(shù)，p(i)代表了樣本被選作聚類中心的傾向性，由式(2)、(3)看出，參考度選的越大，最終得到的聚類類別越多，為了得到較好的聚類效果，文獻(xiàn)[12]和文獻(xiàn)[13]通過(guò)自動(dòng)調(diào)整參考度大小以獲取最佳聚類效果.一般取相似度的中值可獲得相對(duì)中等的聚類數(shù)目，將p的調(diào)整范圍設(shè)為[2pm,pm/2]，其中pm為相似度的中值.從大到小調(diào)整參考度，每次調(diào)整的幅度為：

(9)

K為當(dāng)前的聚類個(gè)數(shù)，即在產(chǎn)生K個(gè)類別時(shí)動(dòng)態(tài)調(diào)整參考度.

對(duì)于調(diào)整過(guò)程中不同的聚類結(jié)果引入Silhouette聚類評(píng)價(jià)指標(biāo)獲取最佳聚類效果.假設(shè)N個(gè)樣本被聚為K個(gè)類別，則每個(gè)樣本的Sil指標(biāo)為：

(10)

其中，a(i)表示樣本i與該樣本所在類別的其他樣本的平均距離，b(i)表示樣本i與最近類別中的樣本的平均距離.聚類結(jié)果中所有樣本的Sil平均值即可反映聚類結(jié)果的好壞，該值越大表明聚類效果越優(yōu)，選取Sil指標(biāo)最大對(duì)應(yīng)的聚類結(jié)果即為最優(yōu)聚類結(jié)果.

2.3　本文算法描述

本文對(duì)視頻幀圖像進(jìn)行顏色、紋理特征提取，再按照上述分層AP聚類算法進(jìn)行關(guān)鍵幀提取.算法具體步驟設(shè)計(jì)如下：

(1)選取一段視頻，讀取將其轉(zhuǎn)換為靜態(tài)幀圖像，假設(shè)共有N幀圖像，記為圖像集L=(X1,X2,…,Xn)，提取每幀圖像的顏色和紋理特征屬性Xi=(x1,x2,…,xn)；

(2)將數(shù)據(jù)集L劃分為M個(gè)子集L1,L2,…,LM，則每個(gè)子集中有N/M個(gè)樣本，L=L1∪L2∪…∪LM；

(3)對(duì)每個(gè)子集執(zhí)行標(biāo)準(zhǔn)AP聚類算法，在進(jìn)行初始聚類的時(shí)候，為了得到相對(duì)中等數(shù)目的關(guān)鍵幀，在初始化參考度的時(shí)候選擇相似度矩陣的中位值；

(4)對(duì)得到的子集的代表樣本再次進(jìn)行AP聚類，參與再次聚類的圖像數(shù)據(jù)集明顯減少，動(dòng)態(tài)調(diào)整參考度，結(jié)合Silhouette指標(biāo)選取其中的最優(yōu)聚類結(jié)果；

(5)獲得最終聚類結(jié)果，選取每個(gè)類別的聚類中心即為該段視頻的關(guān)鍵幀.

3結(jié)果與分析

為了驗(yàn)證該方法的有效性，本文引進(jìn)視頻關(guān)鍵幀保真度和壓縮率[14,15]來(lái)評(píng)測(cè)關(guān)鍵幀提取的效果.保真度越大，所提取的關(guān)鍵幀越能準(zhǔn)確描述原視頻表達(dá)的內(nèi)容；壓縮率越大則表明提取的關(guān)鍵幀越簡(jiǎn)潔，對(duì)于后續(xù)的視頻檢索或視頻摘要就越容易[16].

假設(shè)原始視頻集中L=(X1,X2,…,XN)有N幀圖像，提取出的關(guān)鍵幀有K幅圖像，F(xiàn)=(R1,R2,…,RK)，關(guān)鍵幀集合F與原視頻中隨機(jī)幀Xi的距離定義為：

D(F,Xi)=min{D(Rj,Xi)|j=1,2,…,K}

(11)

關(guān)鍵幀集合與原視頻集合的距離為：

D(F,L)=max{D(F,Xi)|j=1,2,…,K}

(12)

保真度則為：

Fildelity(F,L)=max{D(Xi,Rj)|i=1,2,…,N;

j=1,2,…,K}-D(F,L)

(13)

max{D(Xi,Rj)|i=1,2,…,N;j=1,2,…,K}

表示關(guān)鍵幀集合中某一幀與原始視頻中視頻序列的最遠(yuǎn)距離.

原始視頻序列的壓縮率為：

CR(F,L)=1-K/N

(14)　　　本文選取了不同類型不同時(shí)長(zhǎng)的視頻資源，取阻尼系數(shù)λ=0.5，最大迭代次數(shù)設(shè)置為1 000，分別對(duì)其進(jìn)行特征提取再進(jìn)行分層AP聚類后關(guān)鍵幀的提取,結(jié)果如表1所示.標(biāo)準(zhǔn)AP與分層AP算法提取的關(guān)鍵幀的保真度與壓縮率結(jié)果如圖1、圖2所示.

由表1可以看出，當(dāng)圖像集規(guī)模較小(<3 000)時(shí)，標(biāo)準(zhǔn)AP算法執(zhí)行速度較快，提取的關(guān)鍵幀數(shù)目較多，能反映視頻鏡頭的主要內(nèi)容.但是當(dāng)視頻圖像集規(guī)模增大，標(biāo)準(zhǔn)AP算法需要的時(shí)間開銷急劇增大，提取關(guān)鍵幀消耗過(guò)多的時(shí)間會(huì)嚴(yán)重影響視頻檢索的速度.采用分層AP算法提取的關(guān)鍵幀由于將大數(shù)據(jù)集分層執(zhí)行，速度明顯提升，而且分層后的AP算法由于二次聚類的圖像集只是各個(gè)圖像子集的聚類中心， 提取到關(guān)鍵幀的數(shù)目減

少，因此壓縮率較高(如圖2所示).對(duì)比兩種方法的保真度指標(biāo)(如圖1所示)，本文算法得到的關(guān)鍵幀并沒(méi)有丟失視頻鏡頭表達(dá)的關(guān)鍵內(nèi)容.

圖3和圖4是分別采用標(biāo)準(zhǔn)AP和分層AP對(duì)同一個(gè)鏡頭進(jìn)行關(guān)鍵幀提取的結(jié)果.

圖1　兩種方法的關(guān)鍵幀保真度

圖2　兩種方法的關(guān)鍵幀壓縮率

體育類視頻的特點(diǎn)是包含了很多運(yùn)動(dòng)對(duì)象，因此相比于其他類型的視頻，該類關(guān)鍵幀的保真度較低.從圖3和圖4的仿真結(jié)果可以看出，用標(biāo)準(zhǔn)AP算法得到的一個(gè)鏡頭(該鏡頭包含69幀圖像)的16幅關(guān)鍵幀，采用分層算法僅用2幅圖像即可代表該鏡頭，在能夠代表鏡頭內(nèi)容的前提下，大大提高了壓縮率.

(a)第962幀圖像　　　　　　　　　　　　　　　　　　　　(b)第1002幀圖像圖4　分層AP提取的關(guān)鍵幀

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

本文采用分層AP聚類算法對(duì)視頻圖像進(jìn)行關(guān)鍵幀提取，AP聚類算法克服了傳統(tǒng)的聚類算法需要事先指定聚類數(shù)目以及需要初始化聚類中心等不足.針對(duì)大規(guī)模視頻資源，本文提出的方法可高效準(zhǔn)確地自適應(yīng)提取視頻中的關(guān)鍵幀信息，通過(guò)對(duì)不同類型的視頻資源進(jìn)行仿真與分析，表明本文的方法具有很強(qiáng)的通用性.如何合理有效地對(duì)大規(guī)模數(shù)據(jù)進(jìn)行分區(qū)，使得分區(qū)結(jié)果既有代表性又能很好地提高算法的效率是下一步研究的主要工作內(nèi)容.

參考文獻(xiàn)

[1] Liu Tianming，Zhang Hongjiang，Qi Feihu．A novel video key frame extraction algorithm based on perceived motion energy model[J]．IEEE Transactions on Circuits and Systems for Video Technology，2003，13(10)：1 006-1 013．

[2] 孫吉貴，劉杰，趙連宇，等．聚類算法研究[J]．軟件學(xué)報(bào)，2008，19(1)：48-61．

[3] 張亞迪，李俊山，胡雙演．類模糊C均值聚類的關(guān)鍵幀提取算法[J]．微電子學(xué)與計(jì)算機(jī)，2009，26(2)：89-92．

[4] 楊鵬，裴繼紅，楊烜．基于不變矩和MeanShift聚類的視頻關(guān)鍵幀提取[J]．計(jì)算機(jī)應(yīng)用與軟件，2009，26(2)：238-240．

[6] 甘月松，陳秀宏，陳曉暉．一種AP算法的改進(jìn)：M-AP聚類算法[J]．計(jì)算機(jī)科學(xué)，2015，42(1)：232-235．

[7] 劉曉楠，尹美娟，李明濤，等．面向大規(guī)模數(shù)據(jù)的分層近鄰傳播聚類算法[J]．計(jì)算機(jī)科學(xué)，2014，41(3)：184-188．

[8] Frey B J，Dueck D．Clustering by passing messages between data points[J]．Science，2007，315(5 814)：972-976．

[9] Paccanaro A，Casbon J A，Saqi M A．Spectral clustering of protein sequences[J]．Nucleic Acids Research，2006，34(5)：1 571-1 580．

[10] 張少博，全書海，石英，等．基于顏色矩的圖像檢索算法研究[J].計(jì)算機(jī)工程，2014，40(6)：252-255．

[11] 谷瑞軍，汪加才，陳耿，等．面向大規(guī)模數(shù)據(jù)集的近鄰傳播聚類[J]．計(jì)算機(jī)工程，2010，36(23)：22-24．

[12] Ding Fan，Luo Zhigang，Shi Jinglong，et al．Overlapping community detection by kernel-based fuzzy affinity propagation[C]//Proceedings of International Workshop on Intelligent Systems and Applications.Wuhan:IEEE，2010：1-4．

[13] 王開軍，張軍英，李丹，等．自適應(yīng)仿射傳播聚類[J]．自動(dòng)化學(xué)報(bào)，2007，33(12)：1 242-1 246．

[14] H.S.Chang，S.Sull，S.U.Lee．Efficient video indexing scheme for content-based retrieval[J]．IEEE Trans on Circuits and Systems for Video Technology，1999，9(8)：1 269-1 279．

[15] T.Y.Liu，X.Zhang．Shot reconstruction degree:A novel criterion for key frame selection[J]．Pattern Recognition Letters，2004，25(1)：1 451-1 457．

[16] Sun Z H，F(xiàn)u P,Xiao J，et al.A feature distance based algorithm for video segmentation[C]//Proceedings of the 7th IASTED International Conference on Computer Graphics and Imaging．Kauai Hawaii：ACTA Press，2004：406-410．

【責(zé)任編輯：蔣亞儒】

Research on video key-frame extraction based on

hierarchical affinity propagation clustering

DANG Hong-she， BAI Mei

(College of Electrical and Information Engineering, Shaanxi University of Science & Technology, Xi′an 710021, China)

Abstract:In order to extract key frames from large-scale different videos more effectively and accurately，since traditional AP algorithm is inappropriate to the large-scale pictures clustering,a hierarchical AP method for key frame extraction is proposed.First get the color and texture features of all video sequences,the pictures set is divided into several subsets，the traditional AP is used to obtain the exemplars of each subset;Then the adaptive AP is implemented on the obtained exemplars,the key frames of video sequences are extracted according to the index of Silhouette for the best clustering result.The experimental result shows that proposed method is efficient in key-frame extraction and suitable for all types video resources, has a high fidelity while the compression ratio is improved greatly.

Key words:video retrieval; key-frame; AP; hierarchical division; clustering

中圖分類號(hào)：TP391

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1000-5811(2016)01-0159-05

作者簡(jiǎn)介:黨宏社(1962-)，男，陜西武功人，教授，博士，研究方向：計(jì)算機(jī)控制、多源信息融合、數(shù)字圖像處理

基金項(xiàng)目：陜西省科技廳科技攻關(guān)計(jì)劃項(xiàng)目(2015SF275)

收稿日期:*2015-11-27