基于子镜头分割的自适应关键帧提取算法
基于子镜头分割的自适应关键帧提取算法
段豪，谢刚，雷少帅，杨倩
作者简介：段豪，（1987-），女，硕士研究生，主要研究方向：图像处理，视频检索
通信联系人：谢刚，（1972-），男，教授，主要研究方向：模式识别与智能信息处理. E-mail:
duanhaowqh@https://www.sodocs.net/doc/3915848678.html,
（太原理工大学信息工程学院，太原 030024） 摘要：关键帧的提取是基于内容的视频检索的重要技术，它也是视频分析和基于高级语义的5 视频检索的基础。本文提出了一种基于子镜头分割的自适应关键帧提取算法。该方法首先利用样本分类中的距离可分性准则构建分割判别函数，随后通过探讨判别函数的极值来实现子镜头分割，最后根据每个子镜头内容的变化自适应地提取相应数目的关键帧。实验结果表明，该算法提取的关键帧不仅保持了视频的时序性，而且能以较低的冗余度实现对视频内容的准确描述。
10
关键词：关键帧提取；子镜头；距离可分性；自适应
中图分类号：TP391
Sub-shot Segmentation-Based Self-Adaptive Key Frame Extraction Algorithm
15 DUAN Hao, XIE Gang, LEI Shaoshuai, YANG Qian
(College of Information Engineering,Taiyuan University of Technology, TaiYuan 030024) Abstract: Key frame extraction is an important technology for content-based video retrieval, which is also the foundation of the video analysis and the video retrieval based on advanced semantic. A self-adaptive key frame extraction algorithm based on sub-shot segmentation is 20 proposed in this paper. The segmentation discriminate function utilizing distance separability criteria of sample classification is constructed firstly, and then sub-shot segmentation is achieved by exploring the local maximum of discriminant function. Finally, the key frame is adaptive selected by analyzing the sub-shot content change. Experimental results show that, the key frame extracted by the algorithm not only to maintain the video frame timing, but also can achieve 25
accurate description of video content with lower redundancy.
Keywords: Key frame extraction; Sub-shots; Distance separability; Adaptive
0 引言
随着多媒体技术及计算机网络技术的迅速发展，视频数量急剧增长，视频检索系统受到
30 了越来越多的关注。而关键帧提取作为视频检索的重要环节，其提取效果将直接影响视频检索系统的性能。视频关键帧提取就是研究如何利用尽量少的图像来有效地反映镜头的主要内容。
选取关键帧的经典方法有：(1)基于聚类的方法[1~5], 该方法首先确定一个初始类心，然后根据当前帧与类心的距离来判断当前帧是归为该类还是作为新的类心，将镜头中的帧分类
35 后，取各类中与类心距离最近的帧作为关键帧。聚类方法能有效地消除镜头间的相关性，但不能有效地保存原镜头内图像帧的时间顺序和动态信息。(2)基于视觉内容分析的方法[6~7],它可以根据镜头内容的变化程度从镜头中选取固定数目的关键帧，此方法对于变化少的镜头来说选取的关键帧过多，而对于运动较多的镜头又不能充分描述视频内容。为了兼顾时序性和自适应性，许多文献[8]提出了基于子镜头分割的方法，该方法在子镜头分割时首先计算当
40 前帧与前一帧或前几帧的差，然后将计算结果与设定阈值相比较，实现关键帧的提取。此方法对阈值的选取依赖性很大，由于视频内容的千差万别，阈值法在子镜头分割精度上效果不
理想。而且每个子镜头中提取的关键帧有的不能代表视频内容的变化，或者提取的数量过多，冗余性太大。
1 视频子镜头分割
45 1.1 特征提取
HSV 颜色空间较其它颜色空间更符合人类视觉特性，因此本文采用HSV 颜色直方图作为视频帧的特征向量。由于人眼对Hue 比对Saturation 和Value 敏感，故将Hue 分成16个量化级，将Saturation 和Value 均分为4个量化级，并按公式L=16H+4S+V 合成一个接近于人类视觉的模型。因此，每张图像可量化为包含256柄的一维直方图，即每帧可由一个列向
50 量表示。
1.2 子镜头分割算法
1.2.1 前期准备
首先建立长度为L 2的滑动窗口,并设滑动窗口的前L 帧为样本集()(i)2)L -(i 1)L -(i 1,...,,Hist Hist Hist L ++=，后L 帧为样本集()L)(i 2)(i 1)(i 2,...,,+++=Hist Hist Hist L 。
55 随后按公式（1）计算前后两类样本集的均值向量i m ，1m 代表前L 帧的均值向量，2m 代表后L 帧的均值向量。
2,11=∑=∈i H L m i H i ω (1)
最后计算样本集1L 的类内离散矩阵1S ，1L 、2L 类间离散矩阵b S 。类内离散矩阵1S 在形式上与协方差矩阵很相似，但协方差矩阵是一种期望值，而类内离散矩阵表示有限样本在
60 空间分布的离散程度。
T H m H m H S )()(1111??=
∑∈ω (2)
T b m m m m S ))((2121??= (3)
1.2.2
构建评判函数 滑动窗内两类样本的类间距离最大、类内距离最小时即为子镜头变化之处。根据距离可
65 分性准则可知，类间距离最大、类内距离最小，即等同于即)det(b S 最大、)det(1S 最小。因此可基于距离可分性准则构造如下判别公式。
)det()det(1S S F b =
(4) 1.2.3
计算镜头的F 值曲线 逐帧向后移动滑动窗口，并计算F 值。当整个滑动窗口处在同一镜头中时，F 值基本
70 不变，理想的情况下是趋近于零；当滑动窗口逐渐进入下个子镜头时，F 的取值逐渐变大，当后L 帧全部进入下个子镜头，而前L 帧仍处于前一个子镜头时，F 的取值最大，然后又逐渐变小，直至前L 帧也全部进入下一个子镜头。因此，可以利用F 的特征曲线中极大值对应的帧号作为子镜头分割边界。
1.2.4 子镜头分割 75 视频库https://www.sodocs.net/doc/3915848678.html,/中的视频ROAD 为例，其F 特征曲线如图1所示。
由图可见，F 特征曲线中除两个大极值点外，还存在两个较小极值点。在利用式（4）进行F 值计算时，特征曲线中会存在一些如图1所示的锯齿波，这是由于镜头中的闪光、物体运动和镜头自身运动等原因造成的噪音，而非真正的子镜头分割点。因此，在极大值提取前，首先利用（5）对F 曲线进行滤波，图2是滤波后的特征曲线。 80 F F F ?=′ (5) 其中，F F F std mean +=，F mean 、F std 分别表示F 曲线的均值和标准偏差。
将F 曲线滤波后，假设新的到的函数关系式为)(i f F =′，i 表示帧号。我们采用二次差分的方法进行极大值提取，如公式（6）所示。
2)]1()([)]()1([?=????+i f i f sign i f i f sign (6)
85 其中，sign 为符号函数，??
???=0,10,00,1)(x x x x sign 。
最终求得的极大值点处的帧号如图3所示，从图中可以看出，二次差分结果等于-2处为极大值点，等于1处为尖峰的边界点。该方法可以很好地提取出子镜头的边界，实现对镜头的时序分割。
90
图1 ROAD 视频F 曲线 图2 F ′曲线求得的极值 图3 F 曲线求得的极值
2 子镜头中的关键帧提取
在子镜头分割完成后，利用子镜头的变化率来提取关键帧。好的提取方法应该在不漏掉关键帧的前提下，保证关键帧最少。由于帧间距离能够描述帧间内容的差异，因此本文的基
95 本思想是通过帧间距离变化率来确定关键帧数目k ，
最后提取帧间距离最大的前k 帧作为关键帧。
2.1 确定关键帧数目k
假设子镜头的总帧数为n ，本文利用式（7）表示子镜头变化率，自适应地确定关键帧个数k 。 100 ∑?=+?=11)1,(1)
,(n i i i dist a b b a dist k (7)
其中，),(j i dist 表示i ，j 两帧的欧式距离，),(b a dist 是子镜头首尾两帧的欧式距离，
∑?=+?11
)1,(1n i i i dist a b 表示整个子镜头内帧间欧式距离的均值。 当1≤k 时，说明子镜头中的视频内容变化不大，提取一帧即可；
当1>k 时， 选取最接近k 的整数为关键帧个数。
105 2.2 提取关键帧
计算镜头内相邻帧的欧氏距离，取距离较大的前k 值作为关键帧，并提取所对应的帧序号。
3 实验结果及分析
110
图4 视频hcil_2002的关键帧
图5 视频ROAD 的关键帧 115
图6 视频UGS06_001的关键帧
120 为探讨本算法的鲁棒性，本文做了大量的测试，限于篇幅，仅以三段特征不同的视频序列为例进行分析，如表1所示。视频hcil_2002为一个人在演讲的镜头，共329帧，此视频内容变化缓慢，本算法只提取了2帧关键帧。如图4所示提取的2帧关键帧，即可概括原镜头的主要内容。视频ROAD 是汽车在路上行驶、拐弯的镜头，对于这种存在物体快速运动的视频，本算法提取了4帧关键帧，由图5可见，所提取的关键帧亦能准确地反映视频内容。
125 视频UGS06_001是新闻报道中关于地震的一个镜头，视频中既有显著物体运动，又有镜头自身的运动。表2给出了视频UGS06_001的5个子镜头边界及每个子镜头的关键帧帧号，相应的关键帧如图6所示。
130
表1 实验结果
视频序列总帧数子镜头数提取的关键帧数视频特点
hcil_2002 329 2 2 镜头和景物变化慢
ROAD 84 3 4 镜头移动较大
UGS06_001 285 5 11 镜头变化较慢,局部运动多
135
表2 视频UGS06_001关键帧分析
子镜头帧号范围提取的关键帧
1 1～80 59,65
2 81～97 81,84
3 98～119 99,102,104
4 120～158126,158
5 159～285178,256
4结论
本文提出一种基于子镜头的自适应提取关键帧的新方法，对视频镜头从子镜头、图像帧两个层次进行分析。从镜头中检测出子镜头，自适应提取关键帧，使用户能根据少量的可视140
化数据对视频有快速的了解。该方法首先提取视频的颜色特征向量，然后利用样本分类中的距离可分性准则进行子镜头分解，通过对子镜头的内容变化进行分析选取关键帧。实验结果表明，本文方法提取的关键帧具有较高的准确率，能有效地表达镜头的主要内容，并保持了镜头的时序性。
[参考文献] (References)
145
[1] 沈航,王士林,李生红. 基于内容的视频镜头的分类[J]. 信息安全与通信保密, 2008,11(1):75-80.
[2] WANG Ting,WU Yu,CHEN Long. An approach to video key-frame extraction based on rough set[A].WANG
Ting. Proc of International Conference on Multimedia and Ubiquitous Engineering[C]. Seoul :MUE'07,2007.
590-596.
150
[3] 张建明,李广翠,蒋兴杰.基于群体智能与K-均值相结合的关键帧提取[J].计算机应用研
究,2011,28(1):360-363.
[4] HANJALIC ALAM, ZHANG Hongjiang. An integrated scheme for automated video abstraction based on
unsupervised cluster-validity analysis[J]. IEEE Trans on Circuits and Systems for Video Technology,
1999,9(8):1280-1289.
155
[5] YANG Shuping ,LIN Xinggang. Key Frame Extraction Using Unsupervised Clustering Based on a Statistical
Model[J]. Tsinghua Science and Technology, 2005,10(2): 169-173.
[6] 彭利民. 基于自适应阈值的聚类算法提取关键帧研究[J]. 上海应用技术学院学报, 2008,8(1):41-44.
[7] Li Li,Xiaoqin Zhang,Yanguo Wang,Weiming Hu,Pengfei Zhou.Nonparametric motion feature for key frame
extraction in sports video[C].Pattern Recognition CCPR 08 Chinese Conference,2008:182-186.
160
[8] 王华伟,施智平,史忠植,胡宏. 一种基于子镜头聚类的情节代表帧选取方法[J]. 计算机工程与应
用,2005,27(1):157-159.