黨宏社, 白　梅

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

?

一種基于分層AP的視頻關鍵幀提取方法研究

黨宏社, 白梅

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

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

關鍵詞：視頻檢索； 關鍵幀； AP； 層次劃分； 聚類

0引言

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

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

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

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

1AP算法簡介

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

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

(1)

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

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

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

(2)

(3)

(4)

(5)

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

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

(6)

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

(7)

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

2基于分層AP的關鍵幀提取

2.1　特征提取

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

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

(8)

2.2　分層AP算法

2.2.1分層聚類

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

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

2.2.2參考度的選取

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

(9)

K為當前的聚類個數(shù)，即在產生K個類別時動態(tài)調整參考度.

對于調整過程中不同的聚類結果引入Silhouette聚類評價指標獲取最佳聚類效果.假設N個樣本被聚為K個類別，則每個樣本的Sil指標為：

(10)

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

2.3　本文算法描述

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

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

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

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

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

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

3結果與分析

為了驗證該方法的有效性，本文引進視頻關鍵幀保真度和壓縮率[14,15]來評測關鍵幀提取的效果.保真度越大，所提取的關鍵幀越能準確描述原視頻表達的內容；壓縮率越大則表明提取的關鍵幀越簡潔，對于后續(xù)的視頻檢索或視頻摘要就越容易[16].

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

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

(11)

關鍵幀集合與原視頻集合的距離為：

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}

表示關鍵幀集合中某一幀與原始視頻中視頻序列的最遠距離.

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

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

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

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

少，因此壓縮率較高(如圖2所示).對比兩種方法的保真度指標(如圖1所示)，本文算法得到的關鍵幀并沒有丟失視頻鏡頭表達的關鍵內容.

圖3和圖4是分別采用標準AP和分層AP對同一個鏡頭進行關鍵幀提取的結果.

圖1　兩種方法的關鍵幀保真度

圖2　兩種方法的關鍵幀壓縮率

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

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

4結束語

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

參考文獻

[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]．軟件學報，2008，19(1)：48-61．

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

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

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

[7] 劉曉楠，尹美娟，李明濤，等．面向大規(guī)模數(shù)據(jù)的分層近鄰傳播聚類算法[J]．計算機科學，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].計算機工程，2014，40(6)：252-255．

[11] 谷瑞軍，汪加才，陳耿，等．面向大規(guī)模數(shù)據(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] 王開軍，張軍英，李丹，等．自適應仿射傳播聚類[J]．自動化學報，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．

【責任編輯：蔣亞儒】

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

中圖分類號：TP391

文獻標志碼：A

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

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

基金項目：陜西省科技廳科技攻關計劃項目(2015SF275)

收稿日期:*2015-11-27