基于K-means聚类算法的视频关键帧提取的研究

司若妍，张明（上海海事大学信息工程学院，上海　201306）

基于K-means聚类算法的视频关键帧提取的研究

司若妍，张明
（上海海事大学信息工程学院，上海201306）

关键帧是视频处理中的一个关键技术。通过对视频进行关键帧提取，来有效地获取视频信息，从而提高人们在视频库中检索信息的准确性和效率。K-means聚类算法是视频关键帧提取的一个重要方法，但是，聚类阈值设定不合理，往往会导致关键帧的提取效果不理想，所以，针对以上问题提出一种自适应阈值的方法，并通过实验证明该方法的有效性。

K-means聚类算法；关键帧提取；自适应阈值

0　引言

随着现代计算机网络和多媒体信息技术的快速发展，越来越多的人依赖于网络作为自己的信息获取渠道。视频、音频、图像和文本是网络信息传递的主要媒介。视频由于其直观，内容丰富的特点，愈发成为人们欣然接受的一种信息获取方式和娱乐休闲方式。视频被广泛应用于生活中的各个领域，例如医疗、广告、影视、教育、体育竞赛等。但是，如何快速有效地在丰富的网络视频资源里，找出人们所需要的视频信息并非是一件易事，所以，这也越发引起人们的关注。

人们看到的视频是由一系列视频图像帧组合而成，而关键帧是可以代表视频的主要内容和事件的变化过程那些图像帧，所以，可以通过提取出视频中的关键帧来获取视频中的相关信息。关键帧的提取是视频处理的一个关键技术，是将对视频的处理转化为图像处理的一个重要的方法，它可以在很大程度上减少了计算机处理信息的数据量，同时也可以提高人们在视频库中检索视频信息的准确性和效率。

1　主要的关键帧提取方法

目前，关键帧的提取方法多种多样，主要可以归纳为以下几种：

只提取视频镜头序列中第一帧和最后一帧作为该视频的关键帧［1］的基于镜头边界的关键帧提取方法。分析和计算光流得出视频序列的运动量，然后比较各帧运动量的值，并选取局部最小值处的帧为关键帧的基于运动分析的关键帧提取方法［2］，通过对每一帧图像的颜色、纹理等视觉特征信息的比较，选取帧间的特征显著变化的帧作为关键帧的基于视频内容的关键帧提取方法［3］，无需对视频进行解压处理，可直接从MPEG压缩视频流上，进行关键帧的提取操作的基于压缩视频的关键帧提取方法［4］，以及依据帧图像间相似度的大小，将各个视频帧序列进行聚类，然后依次从每个聚类簇中选取一帧作为关键帧［5］的基于视频聚类的关键帧提取方法。

本文主要针对K-means聚类的关键帧提取方法展开研究，对于如何选取聚类中心和聚类数目的问题，提出一种自适应的阈值确定方法，来解决这一问题。

2　K-means聚类算法

K-means聚类算法是聚类分析中运用最为广泛的算法之一。无论在数据处理或是图像、视频处理中，都运用地相当广泛。

K-means算法在进行关键帧的提取的过程中，首先在n个数据对象中随机选取K个对象来作为初始的聚类中心，之后再计算当前帧与随机选取的K个聚类中心之间的距离，并把当前帧划分到距离其最近的聚类中心所属的聚类当中。再根据每个聚类中所有对象的均值（即中心对象），计算样本集中每个对象与这些中心对象的距离，再按照以上规则再次进行分类。循环往复以上步骤，直至聚类中心的变化小于某个预设的阈值，则运算停止，即可得到最后的聚类结果。通过该聚类算法，可以把图像序列中的图像帧划分为K类，并且每个类中的关键帧都是有一定相似性的，从而提高关键帧提取的效率。

但是K-means算法也有它的不足之处，K-means算法对初始中心敏感，不同的初始中心会导致不同的聚类结果。这便使得K-means算法会导致最后的聚类结果是局部最优而不是全局最优。

在进行K-means聚类算法的关键帧提取的过程中，因为关键帧的数目是由指定的阈值来确定，所以，阈值的选取对关键帧的提取效果影响很大，尤其是在对视频内容一无所知的情况下，预先选取合适的阈值是很困难的一件事，如果阈值设定过大，就会提取过多的关键帧，若设定的阈值过小，提取到的关键帧不能代表镜头。

2.1特征选取

为了能有效进行聚类，选取合适的聚类特征参数也是很重要的。目前，使用比较普遍的方法是颜色直方图，本文选用每一帧的HSV颜色空间中的颜色直方图和纹理特征因子组合成的特征因子作为视觉特征。

（1）颜色特征选取

HSV颜色模型是色调（H，Hue）、饱和度（S，Saturation）、亮度（V，Value）三个英文单词的首字母缩写，由A.R.Smith在1978年创建的一种颜色空间，与传统的RGB颜色空间模型相比，HSV颜色模型因为其具备有线性伸缩性的性质，所以更加符合人类视觉的特点，与人类的视觉感知更接近，因此人们更倾向于用HSV颜色模型来描述颜色。

然而在通常的情况下，由于RGB颜色模型的简便性，我们依然习惯于采用RGB颜色空间模型来描述图像，因此我们首先需对颜色空间模型进行转换，把RGB颜色空间转换成HSV颜色空间。设（r，g，b）分别是一个颜色的红、绿、蓝坐标，它们均为0到1之间的实数。那么，HSV空间中的（h，s，v）可以表示如下：

其中，h∈［0，360°）是角度的色相角，而s，v∈［0，1］分别表示饱和度和亮度。在进行提取的过程中，因为一个图像帧中所包含的颜色信息十分丰富，如果直接采用HSV空间的颜色直方图来描述一个图像帧，计算量会非常大，为了计算的简便，本文按照文献［6］的方法，来对HSV颜色模型进行等间隔量化，将色调H 以20°为一间隔，分为18份，饱和度S和亮度V以0.3为一间隔分为3份，这样就把HSV颜色空间划分为166种颜色来进行颜色特征的提取。经过量化后，为了减少计算量，因为人的视觉对于分量H较为敏感，S次之，V最弱，所以，本文再按照公式（4）将H，S，V合成为一个一维矢量。

（2）纹理特征

在对图像帧处理的过程中，如果仅仅是以颜色特征作为特征提取的参数，对于种类繁多的视频资源来说，显得过于单一，所以，本文在原本的颜色特征的基础上，引入纹理特征算子。

本文利用LBP［7］（局部二值模式）纹理特征描述算子来对帧图像的纹理特征进行处理。因为其所具有的灰度不变和旋转不变的性质很巧妙地避免了由光照显著改变而引起的实验结果的误差。

LBP算子的基本思想是选取所要计算的区域的中心像素并将其灰度值设为阈值，再对周围圆形邻域内的像素进行二值化处理，即将周围圆形邻域内的像素灰度值与该阈值进行比较，若像素值大于该阈值则此邻域的像素值为1，反之为0，由此可得一串二进制的值，再对不同位置的像素值进行加权求和，即可得到该区域的LBP值。表示在半径为R的圆形邻域内有P个像素点。

图1　基本的LBP算子计算示意图

用公式可以表示为：

其中，P表示为在半径为R的圆形邻域内有P个像素点。bi为像素点的像素值，bc为中心点的像素值。如果bi-bc的值大于0，则s（x）的值为1，反之，s（x）值为0。

本文在原本LBP算子的基础上，运用LBP算子的等价模式，将其降维，以减少计算量。LBP等价模式是：如果某个LBP所对应的循环二进制数的序列所包含的0到1或从1到0最多有2次跃变时，那么，该LBP所对应的二进制就称为一个等价模式类。例如，00000000，00011111，10000011分别有0次，1次，2次跃变，它们都可以划归为等价模式类。若对于二进制10101111而言，因为它有4次跃变，所以不可以划归为等价模式类，这种模式被划归为混合模式类。用公式可以表示为：

其中，u表示循环二进制数中0-1跃变的次数。

在经过LBP算子等价模式的处理之后，原先LBP算子中256维的计算维度可以简化为59维，这就起到了降维的目的。

2.2计算帧间的相似度

因为本文是利用颜色特征和纹理特征共同来对帧图像进行描述，所以，两帧之间的相似度可以用二者差值来表示。在本文中，首先计算两帧图像之间的颜色直方图的差值，再计算两帧图像之间的LBP纹理算子的差值，再将这两个差值进行加权计算，最后得到的总差值即可表示为两帧之间的相似度，差值越大，说明两帧之间相似度越大，反之，相似度越小。

其中，I代表帧图像，C代表帧图像的颜色直方图矢量值，V代表采用LBP纹理算子方法计算得到的纹理特征值，D（Cc，Cc+1）和D（Vc，Vc+1）则可以分别表示两帧图像的颜色特征及纹理特征的归一化相似度，数值越大，说明相似度越低，ω1，ω2分别代表颜色相似度以及纹理相似度的权重，且满足权值关系：ω1+ω2=1，在本文的实验中，ω1和ω2均取值0.5。

3　自适应阈值关键帧提取

在进行聚类算法的关键帧提取过程中，因为要随机选取聚类中心和人为设定聚类阈值，而使得算法计算量过大，用时过多，导致算法效率不高，所以为了提高K-means算法的提取关键帧效率，本文从聚类中心和聚类阈值这两个方面上进行研究，改进一种自适应阈值的聚类计算方法。

（1）假设一个视频镜头中有N帧｛f1，f2，f3，…，fn｝，利用公式（7）求相邻两帧之间的相似度，计算相邻两帧之间的帧差可以得到一个帧差序列D=｛D1，D2，D3，…，Dn-1｝

（2）根据帧差序列，设定一个参数T，令

其中，令M=n-c-1

μc为当前帧差的平均值，为当前帧差的方差。用表示当前聚类的离散度。

（3）若相邻两帧之间的帧差≥DT，那么开始新的聚类；否则，若当前帧与当前类中心的聚类≥DT，那么开始新的聚类。

（4）算法停止，得到初始聚类的划分，和初始聚类个数。

对于一个视频镜头聚类，最理想的聚类效果是在聚类中各个镜头帧之间特征越相似，聚类外，各个镜头帧之间差异越大。所以，我们希望聚类内的分散度越小，而各聚类间的分散度越大。本文用表示聚类间的离散度，用示聚类内的离散度。

所以，我们可以用二者的一个比值衡量聚类效果的好坏，这个比值越大说明此时的聚类效果最优。再将这个最大值取反函数，即可得到第T个帧差处可以取得该最大值，即表示此处可以取得最优聚类数。

4　实验结果与分析

本文在Intel i3，2.13GHz CPU，6GB内存，Windows 7（64位）实验环境下和MATLAB平台进行该算法的实现，用来检验该算法的有效性。本文选取动画、电影、音乐MV、新闻几种不同类别的视频片段，实验中使用的视频长度从几百到几千帧不等，按照本文的方法进行了关键帧的提取实验。

目前，对于视频关键帧的提取效果还没有统一性的指标来进行判定，所以，本文依照查全率和查准率这两个参数来检验视频关键帧的提取效果。其中，查全率和查准率的定义如下所示：

查全率=正确检测到的帧数/（正确检测到的帧数+漏检帧数）

查准率=正确检测到的帧数/（正确检测到的帧数+误检帧数）

本文通过按照传统的颜色直方图在设定阈值为0.8的情况下，与本文提出的算法进行对比实验，通过查全率和查准率这两个指标进行对比，实验结果如表1所示。

表1　查全率和查准率比较

从表格中可以发现，对于不同类型的视频片段，本文所使用的方法更能够准确地提取关键帧，而颜色直方图的方法还存在相对较大的误差，本文的方法在查全率和查准率这两个指标上也明显高于颜色直方图的方法。虽然，关键帧的提取效果会受到视频类型和内容变化的影响，视频内容变化激烈的提取的关键帧相对就多，视频内容变化平缓的相对就少，但是，对于实验结果来看，本文的方法在一定程度上，对聚类算法的关键帧提取能够起到一定的改进作用，更能实现对视频内容的完整描述。本文选取实验中包含4390帧的影视剧片段，作为参考对象，运用本文的方法提取出的一些关键帧来说明该算法提取出的关键帧是否具有代表性，部分关键帧如图（2）所示：

图2　两种方法视频各关键帧提取比较

从图2（a）中提取出的关键帧中可以看出视频的一系列变化过程，2位自行车车手在比赛，首先蓝色衣服的车手在后面。之后，蓝衣车手一步步逼近骑行在前面的黑衣车手，直至反超黑衣车手。从本文的算法中可以明确地看出蓝衣车手的一系列超车过程。但是，运用预设阈值为0.8的K-means算法对该段视频进行关键帧提取时，整段过程就提取了两帧，并没有完整的描述整个超车的过程。

从本文的算法提取的关键帧中，可以准确地反映出两位车的比赛过程。而运用传统预设的阈值来处理时，关键帧提取的效果并不好，只有两帧。从实验结果中，不难发现本文所提出的基于聚类算法的关键帧提取的改进方法，具有较高的查全率以及查准率，能提取出较为准确的关键帧来描述视频的内容。

5　结语

本文针对基于聚类算法的关键帧提取方法进行有效的改进。针对K-means聚类算法中，聚类中心数目和聚类阈值无法确定的问题提出改进方法。通过视频中各个图像帧之间的帧差，自适应地得到该视频的阈值。并通过实验论证，本算法有效地将原本算法中存在的不足进行了改进，避免了原本聚类算法中，阈值设定不合理而造成的关键帧提取效果不理想的问题。但是，本文算法的时间复杂度过高，可以在以后的研究中，在针对时间复杂度的问题上进行改进。

K-means Clustering Algorithm；Key Frame Extraction；Adaptive Threshold

［1］方勇，戚飞虎.一种新的视频镜头边界检测及关键帧提取方法［J］.华东理工大学学报∶自然科学版，2004（S1）∶18-23.

［2］Wolf W.Key Frame Selection by Motion Analysis［C］.Proc.IEEE Int Conf.On Acoustics，Speech，and Signal Processing，ICASSP，Ailanta.1996，2∶1228-1231.

［3］杨华芬，郑欢鸣.基于内容的视频关键帧提取技术研究［D］.福建电脑，2010，05∶49-51

［4］朱映映，周洞汝.一种从压缩视频流中提取关键帧的方法［D］.计算机工程与应用，2003，18∶13-14

［5］刘华咏，郝会芬，李涛.基于视频聚类的关键帧提取算法［D］.物联网技术，2014，08∶59-61

［6］Michel Lantagne，Marc Parizeau，Robert Bergevin.VIP∶Vision Tool for Comparing Images of People［DB/OL］.http∶∥vision.gel.ulaval. ca/～lantagne/LantagneVI2003.pdf，2007-11-26.

［7］王玮，黄非非，李见为，冯海亮.使用多尺度LBP特征描述与人脸识别［D］.光学精密工程，2008，04（16）∶697-704.

Research on Video Key Frame Extraction by K-means Clustering Algorithm

SI Ruo-yan，ZHANG Ming
（College of Information Engineering，Shanghai Maritime University，Shanghai 201306）

The key frame is a key technology of video processing.People can get information of the video effectively，through extracting key frame of video.It can improve the accuracy and efficiency of people to retrieve information from video library.K-means clustering algorithm is a key method of video key frame extraction.However，setting unreasonable clustering threshold can lead the consequence of key frame extraction to be unsatisfactory.Thus，puts forward an adaptive threshold method to solve above problems，and the experimental results show the effectiveness of the proposed method.

1007-1423（2016）20-0059-05

10.3969/j.issn.1007-1423.2016.20.012

司若妍（1991-），女，江苏南京人，硕士研究生，研究方向为模式识别与图像处理技术与开发

张明（1957-），男，博士，教授，研究方向为多媒体信息处理、分布式多媒体技术、多媒体数据库、视觉信息检索与分析、网络信息安全、人工智能、航运信息化技术等

2016－05－04

2016－07－13