一种基于分层AP的视频关键帧提取方法研究

党宏社, 白　梅

(陕西科技大学 电气与信息工程学院， 陕西 西安　710021)



一种基于分层AP的视频关键帧提取方法研究

党宏社, 白梅

(陕西科技大学 电气与信息工程学院， 陕西 西安710021)

摘要：为从大量的视频资源中高效准确地提取关键帧图像来表达视频的主要内容，针对传统AP聚类方法提取关键帧无法适应大规模图像集的问题，提出一种分层AP的关键帧提取方法.提取所有视频序列的颜色和纹理特征，将待聚类的图像集进行分层，用传统AP聚类方法求取每个图像子集的聚类中心；用得到的聚类中心进行自适应的AP聚类，根据Silhouette指标选取最优的聚类结果，即可得到视频序列的关键帧代表.实验表明,该方法能快速准确地提取视频最优关键帧，在保证保真度指标的同时能提高关键帧提取的压缩比，且适用于不同类型的视频资源. [5] 范少冲，彭进业，冯晓，等．基于多核学习和AP聚类的图像选取方法[J]．计算机应用研究，2011，28(6)：2 365-2 368．

关键词：视频检索； 关键帧； AP； 层次划分； 聚类

0引言

视频包含了大量的静态帧图像，同一个镜头下的视频图像极其相似，因此含有较多冗余信息.关键帧反映了镜头的主要内容，提取最具代表性的帧图像用以实现视频检索以及视频摘要能达到更加高效准确的结果.

关键帧的提取主要有阈值法、基于镜头边界、运动分析和聚类的方法.阈值法根据帧与帧之间的差异与阈值的比较确定关键帧，当视频中有目标快速运动，就会选择过多的关键帧；边界法依赖于镜头检测的结果，所选关键帧不一定最具代表性；基于运动分析的方法要分析视频中的运动[1]，难度与计算量都较大；聚类方法在模式识别、图像处理领域都得到广泛的应用[2]，现在更多学者将关键帧提取的研究目光聚焦于不同的聚类方法.文献[3,4]用类模糊C均值聚类和MeanShift可以自适应提取关键帧数量，但均需指定初始聚类中心.文献[5]利用AP(Affinity Propagation cluster，仿射传播聚类，简称AP)算法的优势，不需要指定聚类中心和聚类个数，对图像进行AP聚类再进行摘要的选取，可以有效准确地描述原始图像集，但是当数据增多会消耗更大的内存和更多的时间.

文献[6]对于大规模的数据，先利用CVM(Core Vector Machine，核心向量机)进行压缩得到新的数据集再采用改进的AP聚类算法可提高AP算法的速度.文献[7]采用分层推举和全局划分的方式不仅提高了AP算法的效率，同时改善了数据的聚类效果.

本文对视频图像用AP算法进行关键帧提取.视频包含的图像数据量巨大，直接采用AP聚类计算复杂度较大，先对视频图像数据量进行分层，分为若干个图像子集，对每一个子集进行AP聚类，得到较多的聚类中心，再用这些聚类中心组成的图像集进行二次AP聚类，最终得到的聚类中心即为所要提取的关键帧.

1AP算法简介

AP(Affinity Propagation cluster，仿射传播聚类)算法是2007年在Science上提出的一种新的聚类方法[8].该方法无需事先指定类别数目，在聚类初始时将数据集中所有样本均看作是聚类中心，通过消息相互传递和不断的迭代过程，每个样本竞争成为聚类中心或者选择至某个聚类中心的类别，最终获得若干个质量较高的聚类中心.

假设有数据集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　特征提取

本文中视频帧图像的特征通过颜色和纹理来表征.颜色矩利用线性代数中矩的概念，即图像中任何的颜色分布都可以用矩来表示.颜色分布主要集中在低阶矩中，将图像中的颜色分布用颜色一阶矩平均值(Average)、颜色二阶矩方差(Variance)和颜色三阶矩偏斜度(Skewness)来表示.利用颜色矩对图像进行描述，无需量化图像特征，由于每个像素具有颜色空间的三个颜色通道，因此总共用9个分量来描述一幅图像的颜色矩[10].图像纹理特征反映了图像区域内重复出现的结构变化及其灰度或色彩的排列规律，是图像的全局统计特征.基于Gabor滤波器的纹理特征提取方法利用Gabor小波多方向与多尺度的特点，提取相关纹理信息，但是算法处理过程中计算数据量大.本文采用灰度共生矩阵反映不同图像在方向、间隔、变化幅度及快慢上的差异.

通过颜色和纹理特征提取算法获取训练样本中每幅图像的特征向量R(r1,r2,…,r25)，为防止大数据淹没小数据，按照式(8)作归一化处理.

(8)

2.2　分层AP算法

2.2.1分层聚类

在处理小规模数据集的聚类实验结果中，标准AP算法均取得了较好的效果.但是随着数据规模增大，样本数目达到3 000以上时，AP算法的劣势也逐渐明显[11]，因为AP算法的核心思想就是每个数据点都是潜在的聚类中心，在计算过程中要分别计算多个N×N矩阵，样本与样本之间消息进行两两传递，需要更多的时间消耗.视频关键帧提取是视频检索、视频摘要提取的重要环节，速率要求较高，针对AP聚类算法处理数据量巨大的视频帧图像效率不高的缺陷，本文采用分层AP聚类算法对大量的视频帧图像进行关键帧的提取.

标准AP算法的计算复杂度为O(N2)，当N增大，算法复杂度急剧增长.分层AP的主要思想是分层执行AP聚类，先对所有样本数据进行层次划分，将N个大规模数据样本划分为若干个小规模子集，对每个子集执行AP聚类算法，得到每个子集中具有代表意义的样本，然后对这些代表样本再次进行AP聚类，进而得到最终的聚类中心.在进行分区大小选择时，将子集大小设置为1 000，即先对每1 000个样本进行标准AP聚类，得到进行自适应AP聚类的新数据集.

2.2.2参考度的选取

参考度p又称偏向参数，p(i)代表了样本被选作聚类中心的倾向性，由式(2)、(3)看出，参考度选的越大，最终得到的聚类类别越多，为了得到较好的聚类效果，文献[12]和文献[13]通过自动调整参考度大小以获取最佳聚类效果.一般取相似度的中值可获得相对中等的聚类数目，将p的调整范围设为[2pm,pm/2]，其中pm为相似度的中值.从大到小调整参考度，每次调整的幅度为：

(9)

K为当前的聚类个数，即在产生K个类别时动态调整参考度.

对于调整过程中不同的聚类结果引入Silhouette聚类评价指标获取最佳聚类效果.假设N个样本被聚为K个类别，则每个样本的Sil指标为：

(10)

其中，a(i)表示样本i与该样本所在类别的其他样本的平均距离，b(i)表示样本i与最近类别中的样本的平均距离.聚类结果中所有样本的Sil平均值即可反映聚类结果的好坏，该值越大表明聚类效果越优，选取Sil指标最大对应的聚类结果即为最优聚类结果.

2.3　本文算法描述

本文对视频帧图像进行颜色、纹理特征提取，再按照上述分层AP聚类算法进行关键帧提取.算法具体步骤设计如下：

(1)选取一段视频，读取将其转换为静态帧图像，假设共有N帧图像，记为图像集L=(X1,X2,…,Xn)，提取每帧图像的颜色和纹理特征属性Xi=(x1,x2,…,xn)；

(2)将数据集L划分为M个子集L1,L2,…,LM，则每个子集中有N/M个样本，L=L1∪L2∪…∪LM；

(3)对每个子集执行标准AP聚类算法，在进行初始聚类的时候，为了得到相对中等数目的关键帧，在初始化参考度的时候选择相似度矩阵的中位值；

(4)对得到的子集的代表样本再次进行AP聚类，参与再次聚类的图像数据集明显减少，动态调整参考度，结合Silhouette指标选取其中的最优聚类结果；

(5)获得最终聚类结果，选取每个类别的聚类中心即为该段视频的关键帧.

3结果与分析

为了验证该方法的有效性，本文引进视频关键帧保真度和压缩率[14,15]来评测关键帧提取的效果.保真度越大，所提取的关键帧越能准确描述原视频表达的内容；压缩率越大则表明提取的关键帧越简洁，对于后续的视频检索或视频摘要就越容易[16].

假设原始视频集中L=(X1,X2,…,XN)有N帧图像，提取出的关键帧有K幅图像，F=(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)　　　本文选取了不同类型不同时长的视频资源，取阻尼系数λ=0.5，最大迭代次数设置为1 000，分别对其进行特征提取再进行分层AP聚类后关键帧的提取,结果如表1所示.标准AP与分层AP算法提取的关键帧的保真度与压缩率结果如图1、图2所示.

由表1可以看出，当图像集规模较小(<3 000)时，标准AP算法执行速度较快，提取的关键帧数目较多，能反映视频镜头的主要内容.但是当视频图像集规模增大，标准AP算法需要的时间开销急剧增大，提取关键帧消耗过多的时间会严重影响视频检索的速度.采用分层AP算法提取的关键帧由于将大数据集分层执行，速度明显提升，而且分层后的AP算法由于二次聚类的图像集只是各个图像子集的聚类中心， 提取到关键帧的数目减

少，因此压缩率较高(如图2所示).对比两种方法的保真度指标(如图1所示)，本文算法得到的关键帧并没有丢失视频镜头表达的关键内容.

图3和图4是分别采用标准AP和分层AP对同一个镜头进行关键帧提取的结果.

图1　两种方法的关键帧保真度

图2　两种方法的关键帧压缩率

体育类视频的特点是包含了很多运动对象，因此相比于其他类型的视频，该类关键帧的保真度较低.从图3和图4的仿真结果可以看出，用标准AP算法得到的一个镜头(该镜头包含69帧图像)的16幅关键帧，采用分层算法仅用2幅图像即可代表该镜头，在能够代表镜头内容的前提下，大大提高了压缩率.

(a)第962帧图像　　　　　　　　　　　　　　　　　　　　(b)第1002帧图像图4　分层AP提取的关键帧

4结束语

本文采用分层AP聚类算法对视频图像进行关键帧提取，AP聚类算法克服了传统的聚类算法需要事先指定聚类数目以及需要初始化聚类中心等不足.针对大规模视频资源，本文提出的方法可高效准确地自适应提取视频中的关键帧信息，通过对不同类型的视频资源进行仿真与分析，表明本文的方法具有很强的通用性.如何合理有效地对大规模数据进行分区，使得分区结果既有代表性又能很好地提高算法的效率是下一步研究的主要工作内容.

参考文献

[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] 刘晓楠，尹美娟，李明涛，等．面向大规模数据的分层近邻传播聚类算法[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] 谷瑞军，汪加才，陈耿，等．面向大规模数据集的近邻传播聚类[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，Fu 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-)，男，陕西武功人，教授，博士，研究方向：计算机控制、多源信息融合、数字图像处理

基金项目：陕西省科技厅科技攻关计划项目(2015SF275)

收稿日期:*2015-11-27