吴开兴，沈志佳

（河北工程大学 信息与电气工程学院，河北 邯郸 056038）

1 关键帧提取技术

关键帧提取是基于内容视频检索中最重要的技术之一。关键帧是一个镜头的某一帧或某几帧，它们就像一本书中的目录页，能够反映镜头的梗概信息。通过关键帧对视频进行索引，能够极大地减少视频检索的数据量，对于视频检索十分重要。目前关键帧提取技术主要可以分为以下4大类。

1）基于镜头边界的方法[1-2]

这种方法主要是通过固定选取镜头的首帧、中间帧、尾帧等来提取关键帧。此种方法简单易行，但是它提取关键帧的位置和数目都是固定的。如果镜头大小不一，或物体和摄像头处于高速运动中，此种关键帧提取方法的效果十分不理想。

2）基于内容的方法[3-4]

基于内容的方法，主要是通过镜头中视频帧内容的变化来提取关键帧。它的基本思想是当帧的颜色、纹理、形状等底层特征具有显著变化时，便认为其是关键帧。这种关键帧提取方法具有自适应性，会根据镜头内容自适应地在不同位置提取不同数量的关键帧。文献[3]通过结合直方图交集及非均匀分块加权的直方图方法，切割视频镜头，之后在HSV颜色空间基础上，通过计算每帧的图像熵得到关键帧。文献[4]通过比较相邻帧的灰度直方图，并通过与阈值作比较来提取关键帧。但是，如果当镜头的内容变化较大时，用这种方法提取出的关键帧往往数目过多，算法的冗余性较大。

3）基于运动的方法[5-6]

基于运动的方法主要是以物体或摄像机运动的幅度来提取关键帧，当物体或摄像机的运动达到局部最小值时，便定义此处的帧为关键帧。通过这种方法能够很好地表现镜头内全局性的内容变化，具有自适应性，并且与肉眼判断关键帧的准则一致。文献[5]中Worf提出了一种基于光流分析的关键帧提取算法，通过光流计算镜头中的运动量，并且在局部运动极小值处获得关键帧，文献[6]提出一种结合视频帧颜色特征和利用图像分块计算运动信息的方法来提取关键帧。但是由于这些算法复杂度较高，限制了它们的应用。

4）基于聚类的方法[7-9]

基于聚类的方法通过将镜头中相似的视频帧聚成相同的类，然后提取不同类中距离聚类中心最近的视频帧作为关键帧。基于聚类的方法能够很好地表达视频中内容的变化，是目前比较主流的关键帧提取算法。文献[7]中假设，越重要的内容需要的视频帧数越多，并且提出了一种基于统计模型的无监督聚类关键帧提取方法。文献[8]在模糊C均值聚类的基础上，加入了特征权重，使关键帧提取更准确。文献[9]利用蚁堆算法对镜头帧的颜色和边缘进行初始聚类，并利用凝聚算法优化聚类，提取距离聚类中心最近的帧为关键帧。

2 基于吞噬聚类的关键帧提取算法

本文借鉴蚁堆聚类算法、DBSCAN聚类算法，以及K-均值聚类算法的思想，提出了一种基于吞噬聚类的关键帧提取新算法。

DBSCAN是一种基于密度的算法，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇。但是它在划分簇时，需要计算与中心点距离为e的其他数据对象的个数，为此，它需要扫描完所有剩余的数据对象，算法复杂度较高，而且此算法需要2个初始参数：半径e和最小数据对象数目MinPts。这两个参数的取值直接影响算法的聚类效果。为此，本文借鉴了蚁堆算法中蚂蚁运动的思想，将数据对象表现为可以随机移动的吞噬体，吞噬体通过吞噬其他相近的数据对象，在保证其聚类密度没有减少的情况下，增大吞噬能力。吞噬主体吞噬其他客体概率的计算，也参考了蚁堆算法中蚂蚁放下或者拾取数据对象的概率公式。而吞噬体吞噬中心的确定，则借鉴了K-均值聚类算法中聚类中心的计算公式。

利用吞噬聚类算法提取镜头关键帧的步骤如下：

1）提取视频帧的特征矢量，本文采用文献[10]中基于HSV颜色直方图的特征向量提取方法，将色调空间H分为8份，饱和度空间S分为3份，亮度空间V分为3份，然后根据人眼对不同特征的感知程度，确定量化级数，把颜色分量合成一维特征矢量，即

式中：W的取值范围为[0,71]。通过计算基于W的直方图，便可得到关于视频帧的72维特征向量。

2）将所有数据对象随机分布在M×M的二维网格中，每个数据对象可以看作一个吞噬体，吞噬体具有吞噬中心和吞噬半径。其中吞噬中心为数据对象的特征向量，初始吞噬半径设为r。

3）所有吞噬体在二维网格上随机移动，当吞噬体遇到可以吞噬的客体后，会以一定几率将客体吞噬。吞噬后，吞噬主体的吞噬中心和吞噬半径将会随着吞噬客体而改变。

4）吞噬的机制：吞噬主体吞噬其他客体的概率公式为

式中：d(os,oo)为吞噬主客体间吞噬中心的距离；rs为吞噬主体的吞噬半径。

d(os,oo)采用欧氏距离，计算公式为

式中：xsi为吞噬主体吞噬中心的第i维分量；xoi为吞噬客体吞噬中心的第i维分量；n为吞噬中心的向量维数，此处n=72。

吞噬后，新吞噬中心的计算公式为

式中：os1为吞噬主体新的吞噬中心；ks和ko分别为吞噬主客体内数据对象的个数。

吞噬后，新的吞噬半径计算公式为

式中：rs1为吞噬主体新的吞噬半径；ρ为标准聚类密度，即当吞噬体的聚类密度大于ρ时，吞噬半径将扩展，吞噬体的吞噬能力进一步加强。

5）当吞噬进行到一定次数后，如果吞噬聚类效果不理想，依然存在较多吞噬密度小于ρ的吞噬体，则可以递减标准吞噬密度ρ，按照步骤4）中的公式重新定义吞噬半径，继续进行吞噬。

6）最后所剩余的吞噬体的吞噬中心即为聚类中心，选取与聚类中心距离最近的向量所代表的视频帧作为关键帧。

DBSCAN算法需要初始参数：半径e和最小数据对象数目MinPts，而本算法仅仅需要一个标准聚类密度ρ，并且ρ的值会随着聚类效果的优劣而自动改变。

蚁群算法容易出现局部极值问题，即本应该属于相同聚类的数据对象，却在不同的位置分别聚类，而本算法，则可以简单地通过吞噬体的互相吞噬，合并相近的聚类。

K-均值算法需要初始的聚类中心和聚类个数，本算法则会根据数据对象的复杂程度，自动确定聚类中心和聚类个数，具有自适应性。

3 实验结果与讨论

利用吞噬聚类算法提取出的某个镜头的关键帧如图1所示。

图1 镜头关键帧序列（截图）

可见提取出的关键帧代表了某一汽车躲避警察抓捕的全过程，提取出的关键帧具有代表意义。

利用本算法提取出的某个演讲镜头的关键帧如图2所示。

图2 演讲镜头关键帧

由于该演讲镜头内视频内容变化很少，所以仅提取出了唯一的关键帧，由此可见，本算法具有自适应性，能够根据镜头内容的复杂程度，自适应地提取出不同数量的关键帧。

为了验证算法的有效性，本文采用了120个不同的镜头来对算法进行分析，其中体育类型、新闻类型、动画类型、电影类型各30个，以查全率和查准率来作为算法有效性的衡量标志。

为了对比算法的效果，本文以K-均值聚类算法、DBSCAN算法、蚁堆聚类算法与本文算法在查全率和查准率上作对比，具体的实验结果如表1、表2所示。

表1 各算法查准率对比表

表2 各算法查全率对比表

可见，在体育类、新闻类、动画类、电影类的视频中，本文算法的查准率均优于其他的传统算法。但是在查全率方面，针对体育类和动画类视频，本算法效果略低于蚁群算法。

4 小结

本文章借鉴了蚁堆聚类算法、DBSCAN聚类算法，以及K-均值聚类算法的思想，提出了一种基于吞噬聚类的关键帧提取新算法，与传统算法作对比，虽然对于体育类视频和动画类视频在查全率方面，本算法略低于蚁堆聚类算法，但是总体来说，本算法的提取效果优于其他的聚类算法，具有一定的应用价值。

：

[1]TANIGUCHI Y.An intuitive and efficient access interface to real—time incoming video based on automatic indexing[C]//Proc.3rd ACM International Conference on Multimedia.New York，USA：ACM Press，1995：25-33.

[2]ZHANG Hongjian，WU Jianhua，ZHONG Di，et al.An integrated system for content-based video retrieval and browsing[J].Pattern Recognition，1997，30（4）：643-658.

[3]瞿中，高腾飞，张庆庆.一种改进的视频关键帧提取算法研究[J].计算机科学，2012（8）：300-303.

[4]柴饶军，马彩文.图像序列中目标关键帧快速搜索算法[J].光子学报，2004（10）：1233-1235.

[5]WORF W.Key frame selection by motion analysis[C]//Proc.IEEE International Conference on Acoustics,Speech and Signal Processing.Atlanta，USA：IEEE Computer Society，1996：1228-1231.

[6]顾家玉，覃团发，陈慧婷.一种基于MPEG-7颜色特征和块运动信息的关键帧提取方法[J].广西大学学报：自然科学版，2010（2）：310-314.

[7]YANG Shuping，LIN Xinggang.Key frame extraction using unsupervised clustering based on a statistical model[J].Tsinghua Science and Technology，2005（2）：169-173.

[8]HUA M，JIANG P.A feature weighed clustering based key-frames extraction method[C]//Proc.the 2009 International Forum on Information Technology and Applications.Piscataway：IEEE Computer Society，2009：69-72.

[9]张建明，刘海燕，孙淑敏.改进的蚁群算法与凝聚相结合的关键帧提取[J].计算机工程与应用，2013（3）：222-225.

[10]王娟，孔兵，贾巧丽，等.基于颜色特征的图像检索技术[J].计算机系统应用，2011（7）：160-164.