基于视频聚类的关键帧提取算法

引言

随着互联网和多媒体技术的飞速发展，形象生动的数字视频已经逐渐取代单调的文本信息，成为了人们网络生活中传播信息的重要方式之一。面对互联网上大量的视频，能否在较短的时间内找到需要的视频片段，已经成为了人们越来越关注的问题。在视频帧序列中，包含视频重要内容的帧可以简单有效地概括视频的主要内容，称为视频的关键帧。关键帧的提取技术在基于内容的视频检索中有着举足轻重的地位。在实际应用中，关键帧的提取技术可以分为以下4大类：

基于运动分析的关键帧提取技术。运动分析一般是基于流光运算的，通过分析和计算光流得出视频序列的运动量。然后比较运动量的值，并选取局部最小值处的帧为关键帧。这种方法提取关键帧的最大优点是:针对不同结构的镜头,可以根据实际情况提取数量合适的关键帧。但这种方法计算复杂，时间开销大，而且由局部最小值得到的关键帧不一定能准确描述视频内容。

基于镜头边界的关键帧提取技术。这种方法首先将视频分割成若干个镜头，然后在每个镜头内部分别提取第一帧、中间帧和最后一帧作为关键帧。这种方法容易设计，计算简单，适合视频内容简单或场景固定的情况，但当镜头变换频繁且变换方式多样时，有可能导致提取的关键帧不能准确地描述视频的内容。

基于视觉内容的关键帧提取技术。该方法根据每一帧图像的形状、纹理、颜色等视频信息的改变来提取关键帧。这种方法可以根据视频内容变化的显著程度灵活的确定要选取的关键帧的数目，但缺点是：当镜头变化频繁时容易导致选取的关键帧过多，造成信息冗余。

基于聚类分析的关键帧提取技术。该方法充分考虑了镜头内以及镜头间的相关性，依据帧图像间相似度的大小，将视频帧序列进行聚类，然后依次从每类中选取一帧作为关键帧。大多数情况下，基于聚类分析提取关键帧能准确的描述视频主要的内容。但该方法最大的不足之处在于：需要在聚类前提前设定好聚类的数目和聚类中心。在视频内容不确定的的情况下，提前设定聚类的数目和中心是十分困难的，且运算时间较长，这一缺陷极大的制约了这类方法的进一步发展。

层次聚类算法无需提前设定聚类中心和聚类数目，但该算法收敛速度相对较慢。K-means算法设计简单、容易实现,且收敛速度较快，但其对初始聚类中心较敏感，容易陷入局部最优解［10］。针对这两种算法在提取关键帧过程中出现的不足，本文提出一种改进的基于视频聚类的关键帧提取算法。该算法过程为：首先，依次提取帧图像的信息熵，并使用欧式距离公式计算帧间相似度；然后，运用层次聚类算法对所有帧进行聚类，得到初始聚类结果；运用K-means算法优化并完成最终聚类；最后，将距离聚类中心最近的帧作为关键帧输出。

1基于视频聚类的关键帧提取过程

1.1特征提取

1948年，信息论创始人shannon首次提出信息熵的概念,用以描述随机变量X所包含的平均信息量。X的信息熵定义为:

其中，X={xiIi=1，2，3，•••,"}表示随机变量；(x)表示Xi出现的概率。

对于一段包含N帧的视频序列：=(/1"•••,£},假设

该视频序列的每一帧均为256级的灰度图像。本文首先将图 像分割为B块，每块图像的信息熵定义为:

其中,P 3,)表示图像中灰度值为i的像素出现的概率。图像 的特征向量定义为：

其中,H表示第j块图像的信息熵。

1.2计算帧间相似度

我们用欧式距离表示帧间的相似度。欧式距离越小，帧 间相似度就越高。帧间的欧式距离定义为：

其中，N为视频中帧的数量,F«和Fb分别表示图像a和图像b 的特征向量，d (Fa, Fb)为帧间的相似度。

1.3利用层次聚类得到初始聚类结果

本文使用凝聚型的层次聚类算法对视频序列进行初始聚 类，其主要思想是：先将每个待聚类的样本做为一类，然后 依据帧间相似度的大小，合并相似的类使之成为一类，直到 满足终止条件。

假设视频序列有N个待聚类的样本，基本步骤为：

确定终止条件。设要提取的关键帧的数量为计 算特征向量的均值M和方差V:

其中,D={di| i=1, 2, 3,…,N}表示距离向量。本文中,K 的值与帧间距离d(F”Fb)4V的帧的数量相等。

初始化：首先，将每个样本单独归为一类，依次计 算每两类之间的相似度；

寻找距离最近的两个类，并把他们归为一类；

重新计算新生成的这个类与各个旧类之间的相似度；

重复3和4,直到聚类数目为K,结束。

1.4利用K-means聚类算法优化聚类结果

本文将层次聚类产生的结果作为K-means算法的输入， 将层次聚类产生的每一类的中心，作为K-means算法的初始 聚类中心，这样可以避免随机产生初始聚类中心对K-means 算法的聚类结果产生的影响。由于层次聚类后，样本已经基 本聚类成功，故K-means算法迭代的次数将大大减少。

具体步骤如下：

计算层次聚类产生的聚类的中心，即每个聚类对象 的平均值；

计算每一帧与聚类中心的距离，并根据最小距离准 则对相应帧重新进行分类;

重新计算每个类的聚类中心；

重复2和3,直到每个聚类中的对象不再发生变化；

( 5)计算每一类的聚类中心，将距离聚类中心最近的帧 作为关键帧输出。

本文将每个视频帧分为B块并提取每块的信息熵，然后 组成特征向量，充分考虑了每个视频帧的特征。同时，该算法 利用了层次聚类能在短时间内得到聚类结果的优势，大大提 高了工作效率。此外，本文将已经初步分类成功的层次聚类的 结果作为K-means算法的输入，避免了人为定义初始聚类中心 对K-means聚类结果的影响。

2实验结果与分析

本文在 Intel i7, 2.4 GHz CPU, 4 GB 内存，Windows 8 ( 64位)环境下和Matlab平台上实现该算法，以检验该算法的 有效性。本文使用的实验视频长度从几百帧到几千帧，类型丰 富全面，包括广告、电影、新闻、卡通等。同时，人工对数据 集进行关键帧的识别统计作为算法的比较标准。

本文采用查全率和准确率这两个参量来检验算法的有效 性［11］。其中，查全率和准确率的定义如下公式所示：

查全率=正确检测数/ (正确检测数+漏检数)

准确率=正确检测数/(正确检测数+误检数)

由于传统的直方图法［12］广泛应用于关键帧的提取，且该 方法具有较好的检测性能和较快的运算速度，故本文采用其 作为对比实验。提取关键帧的结果如表1所列。

由表1可知，对于广告、电影、新闻、卡通等不同类型 的视频片段，使用本文的算法提取关键帧具有较大优势。例如， 在随机选取的卡通类视频中，本文提出的算法查全率为86.9% 和准确率为85.7%,比直方图法的查全率和准确率高很多。由 此可见，本文提出的算法能很好的描述视频的主要内容，且 查全率和准确率较高。本文选取了一段包含1 348帧的卡通视 频序列，以验证该算法提取的关键帧具有代表性，部分关键 帧如图1所示。

图1列举了从视频序列中提取的部分关键帧。其中，前10个关键帧内容变换较大，准确反映了汽车在空旷的平原上静止、加速、超车等一系列过程，因此提取为关键帧。后8个关键帧内容变化不大，关键帧序列特写了黑色轿车超过红色轿车的过程。从以上实验结果可以看出，本文提出的基于视频聚类的关键帧提取算法，有较高的查全率和准确率，提取的关键帧能较为准确的描述视频的主要内容。

3结语

本文提出了基于视频聚类的关键帧提取算法，有效地改进了传统聚类算法在提取关键帧过程中出现的不足。该算法将层次聚类和K-means算法的优势充分结合，并扬长避短，使用K-means算法对层次聚类的结果再次优化，最终得到了视频的关键帧。从大量的实验数据可以看出，该算法有很好的适应性，可以针对不同类型的视频提取适当数目的关键帧，且提取关键帧的查全率和准确率高于传统方法。

20211221_61c1dea1a3293__基于视频聚类的关键帧提取算法