一种新的冗余关键帧去除算法

解晓萌，黎绍发

（华南理工大学 计算机科学与工程学院，广东 广州 510006）

随着互联网技术的发展，尤其是近几年视频网站的兴起，越来越多的人上网查找和观看自己所喜欢的视频。视频的种类也越来越多，从新闻、娱乐到广告和教育，网络视频所展示的信息已涉及到社会的方方面面。与此同时，网络视频的数量极其庞大，且每天都有源源不断的新的视频信息被发布到网络中去，这就使得如何高效、快速查找出用户所需要的视频信息成为一个重要的研究课题，越来越多的工作者投入大量精力做视频检索方面的研究。

和基于关键字的视频检索方法不同，基于内容的视频检索方法主要是通过分析源视频的内容信息来查找相关视频，已被认为是将来视频检索研究的方向，具有很好的前景。基于内容的视频检索流程图如图1所示。

图1 基于内容的视频检索的流程

本文研究的重点在于关键帧提取，下面就现有的主要的关键帧提取技术做一下简单介绍。第1类是基于镜头的方法，这类方法的基本思想是选取镜头中的特定帧作为关键帧，最简单的是选取第一帧作为关键帧[1]，这类方法中比较经典的算法有帧平均法和直方图平均法[2]。这类方法的优点是思路比较简单，易于编程实现，容易选取到视频图像中具有一般代表意义的帧；缺点是该种方法无法处理运动强度较高的镜头。第2类是基于内容分析的方法，该类方法主要依赖于信息统计论的观点，认为相关性较小的帧图像比相类似的图像携带更多的信息[3-4]。当选取关键帧时，应该选取最不相关的几帧作为关键帧。该类方法的最主要的问题是计算量大，且所选取的帧不一定具有代表意义。第3类是基于运动分析的方法，该类方法以光流分析算法[5]和MPEG-7描述符算法[6]为代表。光流分析算法由Wolf等人提出，它通过光流分析技术来计算镜头中的运动量，并把运动量为局部极小值的帧作为关键帧。该帧反映视频信息的静止，通常对应视频中的重要信息。MPEG-7描述符算法使用了两个MPEG-7描述符，分别使用行为强度和行为空间分布来做关键帧的提取。该类方法的主要问题也是计算量大，时间效率低，所选取的关键帧也不一定准确。第4类是基于聚类的方法，主要研究如何找出镜头间的关系。该方法是将内容上有关系的镜头结合起来，以描述视频节目中有意义的事件或活动。有些学者也称该方法为场景转换、情节分割、镜头聚集等[3，7]。第5类是基于压缩视频流提取的方法。文献[8]提出了通过检测MPEG压缩视频流中已有的离散余弦变换（DCT）的DC系数和运动矢量（MV）来提取关键帧的方法。该方法与其他基于原始视频流的关键帧提取算法不同，它直接在编码后的视频流上识别关键帧，从而节省不必要的解压缩计算。

以上介绍了当前一些主流的关键帧提取方法，但这些算法都会面对一个同样的问题，即冗余关键帧的存在，其原因是不同的镜头所提取出的关键帧相似。所以，在视频关键帧提取系统中，对所提取出的关键帧做去冗余处理是非常有必要的。

1 基于颜色和结构的冗余帧去除算法

本文所提出的方法通过图像的灰度直方图（颜色）和图像的轮廓（结构）来对两张图像做比较，找出冗余的关键帧。下面对图像的灰度直方图和图像的轮廓作介绍。

1.1 图像的灰度直方图

在一幅灰度图像中，像素的取值范围从0～255，把像素的取值作为横坐标，把一幅图像中取某一像素值的像素的个数与总像素个数的比值作为纵坐标画一幅图，即为图像的灰度直方图（见图2）。

式中：k代表像素点的取值；nk代表取k值的像素点的个数；N代表图像中所有像素的个数。

通过求图像的灰度直方图，可以将一幅图像转换为一个256维的列向量I=[i0,i1,…，i255]T。下面介绍如何用图像的灰度直方图来比较两幅图像，假设两幅图像的灰度直方图为P，Q，两幅图片的差别为D，则

式中，D表示两幅图像颜色上的差别。可以简单的给D设一个阈值a来判断两幅图像是否相似，如果两幅图像相似，它们的颜色差别会小于a,否则两幅图像的颜色差别会大于a。但这样做会出现一个问题，如图3所示。

图3a、3b两幅图像是水平翻转所得，它们本质上是不同的图像，但是它们却有相同的灰度直方图，两幅图像的灰度直方图的差别为零。所以，单从应用图像的底层颜色信息来比较图像无法克服这一问题，下面将介绍用图像的轮廓来比较图像。

1.2 图像的轮廓

图像的轮廓即图像的边缘，本文中用Canny边缘检测来提取图像的边缘。Canny边缘检测器是高斯函数的一阶导数，是对信噪比与定位之乘积的最优化逼近算子[1]。Canny认为好的边缘检测应该具有3个特点：1）错标非边缘点和漏标真实边缘点的概率比较低；2）检测出的边缘点尽量接近真实边缘中心；3）具有单值边缘响应。

图4是某一幅图像应用Canny边缘提取法所提取出的轮廓图。图像的轮廓表示的是图像的结构信息，下面介绍如何用图像的轮廓来比较两幅图像。

图像的轮廓图（图4b）只包含两种像素点，白色和黑色。把黑色看成背景，白色的像素看成背景上的点，每一个白像素点都有一个坐标（用该像素点所在的列数作为横坐标，以其所在的行数作为纵坐标），可以得到一个坐标的集合

式中n为所有白像素点的个数。得到坐标集C后，用其来拟合一条直线（见图5），所用的方法是最小二乘法，假设所要似合的直线为y=a+bx，则

式中，N是坐标集C中坐标的个数。

假设有两幅图像，通过提取轮廓和直线拟合后得到两条直线y=a1+b1x和y=a2+b2x，则两条线的夹角为

用两幅图像所拟合的直线的夹角来判断两幅图像是否相似，如果小于某一阈值，则认为相似；否则，认为不相似。

1.3 冗余帧去除算法

首先定义几个函数，hist_similar（a，b）是通过上方介绍的通过直方图求得的图像a和b的差异值，edge_similar（a，b）是求得a和b两张图像拟合直线的夹角，则判断两张图像是否相同的函数similar（a，b）定义为

下面给出算法的伪代码：

算法中拿关键帧集中的某一帧同该帧后的所有的帧用similar函数进行比较，如果相同，则删除掉该重复帧。因为similar函数需要同时满足两个条件（灰度直方图比较相同和拟合直线比较相同）才认为两幅图像相同，这样会大大减少误删的发生。

2 实验及讨论

实验机器是CPU为Intel CoreTM2 Duo 2.33 GHz、内存为2 Gbyte的台式机。实验中所需的参数设定为α=0.3，β=5。实验中所用的视频是从优酷视频网下载所得，题材包括了娱乐、动画、电影、运动和新闻。运用文献[3]的方法来提取关键帧，结果列于表1中。

表1 实验用视频信息

下面介绍两个衡量标准，错正率FP和错负率FN。

从表2～表4实验结果可以看出，结合了图像颜色和图像结构的冗余帧去除算法比单纯的只使用图像颜色或者是图像结构的算法在准确率上有了很大的提高，结果证明本论文提出的方法对冗余帧去除这一问题得到了很好地解决。

表2 结合图像颜色和图像结构所得的实验结果

表3 只用图像颜色所得的实验结果

表4 只用图像结构所得的实验结果

3 总结

关键帧提取在基于内容的视频检索研究中是重要的一步，当下的关键帧提取算法当中都会存在冗余关键帧的问题，冗余关键帧不但不能提供信息量，而且需要存储空间和处理时间，本文提出了结合图像像素颜色和图像结构的冗余帧去除算法，实验证明结合后的方法较单独使用的方法性能有很大的提高，证明了本文提出的方法是有效的。但本文的算法也存在不足，对不同种类的视频的效果存在差异，这也是接下来工作的内容。

[1]SHAHRARAY B，GIBBON D C.Automatic generation of pictorial transcripts of video programs[EB/OL].[2012-01-01].http://dx.doi.org/10.1117/12.206078.

[2] 张继东，陈都.基于内容的视频检索技术[J].电视技术，2002，26（8）：17-19.

[3] 章毓晋.基于内容的视觉信息检索[J].北京：科学出版社，2003.

[4] 王新舸，罗志强.代表帧及其提取方法[J].电视技术，2010，35（10）：26-28.

[5] WOLF W.Key Frame selection by motion analysis[C]//Proc.ICASSP 96.[S.L.]:IEEE Press，1996：1228-1231.

[6]NARASIMHA R,SAVAKIS A，RAO R M，et al.Key frame extraction using MPEG-7motion descriptors[EB/OL].[2012-01-10].http://www.ce.rit.edu/～savakis/papers/Asilomar03_Narasimha_Savakis_Rao_deQueiroz.pdf.

[7] 钟玉琢，向哲，沈洪.流媒体和视频服务器[M].北京：清华大学出版社，2003.

[8] 钟玉琢，王琪，赵黎，等.MPEG-2运动图像压缩编码国际标准及MPEG的新进展[S].北京：清华大学出版社，2002.