基于时空切片的关键帧提取研究

雷少帅，曹长青，古 赟，谢 刚

（太原理工大学 信息工程学院，太原 030024)

视频是时间连续的一系列图像帧的集合，是一种没有结构的图像流。如果把视频看作一本没有目录和索引的书，那么一幅图像帧就相当于书中的一页。由于视频这部书缺乏目录和索引信息，人们无法对它进行高效浏览和检索，于是人们提出利用关键帧作为基本访问单元为视频建立有效的目录结构。关键帧是原始视频中最有代表性的一幅或多幅图像。关键帧提取就是研究如何用最少的视频帧来反映视频的主要内容。它的使用极大地减少了视频检索的数据量，并为视频摘要和视频检索提供了内容组织框架。关键帧的数量取决于视频内容的复杂度，一般视频内容越复杂，内容变化越快，提取的关键帧应越多。关键帧的提取原则是在保存主要视频内容的前提下尽量消除冗余。理论上讲，镜头中的主要信息，如镜头中出现的主要物体、发生的主要运动和事件等，都应该通过关键帧被选取出来。

目前常用的关键帧提取方法有：

1)基于镜头的方法［1］。首先将视频分割成若干个镜头，然后选取每个镜头的首帧或尾帧作为关键帧。此方法简单，但关键帧的数量和位置都是固定的，对于存在摄像机运动和物体运动的视频镜头效果非常不理想。

2)基于内容的方法。此方法将颜色、形状、纹理等底层特征发生显著变化的帧作为关键帧。文献［2］先把镜头中的第一帧选为关键帧，然后计算当前帧与上一关键帧的直方图距离，如果大于某阈值，则被选为关键帧。文献［3］计算当前帧的直方图和前N帧的平均直方图之间的距离来确定关键帧。文献［4］首先创造一张参考帧（对于参考帧的创造方法，有兴趣的读者可参考文献［5］)，然后比较当前帧与此参考帧的直方图距离，然后与阈值比较选择关键帧。该方法是根据镜头内容的变化程度自适应地确定关键帧的数量。但对于内容变化较快的视频，此方法选取的关键帧往往过多，冗余性较大。

3)基于聚类的方法。通过聚类算法，将镜头中相似的视频帧聚成相同的类，从每个类中选取距离类心最近的帧作为关键帧［6］，即聚类个数等同于关键帧数目。文献［7］通过应用聚类有效性分析，能自动确定最优聚类个数。该方法能有效地消除冗余，提取的关键帧能够较好地反映镜头内容。但此方法选取的关键帧打破了原有视频帧的时间序列，将画面相似但时间并不连续的视频帧归为一类，难以体现视频的时间信息。例如一个人从房间走出再进来，聚类的结果是只体现人走进或者走出的过程，没有体现人走出再走进的过程，即难以体现视频时间性。

4)基于运动的方法。利用视频镜头中物体或摄像机的运动信息来提取关键帧。文献［8］通过光流分析来计算镜头中的运动量，在运动量局部最小值处选取关键帧。另外有很多学者通过MPEG视频流中的运动向量来分析视频中物体和镜头的运动情况，从而提取关键帧。这种方法可以根据物体或摄像机的运动量大小进行关键帧提取，但是，计算量相当大。

现有方法都是利用视频帧的空间信息进行关键帧提取，而忽略了视频帧之间存在的时间信息，难以动态反映视频内容，不符合人眼视觉感知。因此，必须加强对视频时空特性的分析，力争从时空联合特性上确定关键帧数目和位置。但视频时空特性分析是关键帧提取领域中的一个难点，面临极大的挑战。

由于时空切片包含了视频镜头的物体和摄像机的运动信息，能反映视频的动态特性，因此本文提出了一种基于视频时空切片的关键帧提取方法。

1 视频时空切片

时空切片的概念是E.H.Adelson和J.Bergen于1985年在“Spationtemporal Energy Models for the Perception of Motion”一文中首次提出的。所谓视频时空切片，是将连续的视频图像在时间轴上展开，然后在各帧相同的位置进行采样，如提取所有图像的某一行（列)像素组合而成的一幅二维图像［9］。因此时空切片能得到该视频内容在指定位置上随时间变化的信息。时空切片通常有三种取法：垂直切片、水平切片、和对角线切片，切片方法如图1所示。

图1 时空切片分割方式示例

对长度为L的视频序列V，本文采用水平切片法提取每帧中间位置的横向像素线，因此共计L条像素线，然后将它们按列排列拼成一张新图片，即此段视频的时空切片。下面分析时空切片中像素间的时空特性。以图2-a所示的时空切片为例，以该帧左上角为原点，右方作为X正向，下方作为Y正向建立坐标系FXOY。在FXOY中，时空切片在Y方向上的相邻像素点是同一帧中同一像素线上的相邻点，反映的是像素点在空间分布的相关性，X方向上的相邻像素点则是相邻帧中位于同一位置上的像素点，反映了不同视频帧的时间相关性，这表明时空切片融合了视频片段的时空联合特性。

图2是从几个视频镜头中提取的视频时空切片。图2-a所对应的视频镜头是飞机起飞的过程。开始飞机在地上缓慢向前移动，所以镜头基本上是静止的，图2-a开始处的平行纹理就反映了这一点；随着飞机的快速起飞，摄像机随飞机快速移动，背景逐渐发生变化，此过程可由图2-a中的纹理变得倾斜以及纹理颜色变白就可看出。变白是因为飞机已经飞上天空，显示的是背景白云的颜色。

图2-b所对应的视频镜头是一个人在说话，视频内容基本没有变化，这可由视频切片的纹理反映出来。切片的纹理基本是平行的没有发生变化，其中中间颜色较深的部分代表了画面中的人物，由此看出画面中的人物也没有发生运动。

图2-c所对应的镜头是一个人在跑步，一会跑进镜头，一会跑出镜头，背景不变。由其切片图可以看出黑色的线代表跑步的人，由此可清楚的看出人的运动轨迹。由于背景不变，所以时空切片的背景是纯色的，没有其他纹理和颜色变化。

图2 从几个视频镜头中提取的视频时空切片

2 基于时空切片的关键帧提取

由以上分析可见，颜色和纹理包含了对应视频的大量信息，包括摄像机的运动，物体的运动，背景的变化等等。颜色和纹理的不连续性意味着新的镜头内容出现，因此通过分析时空切片特性就可很好地表征颜色纹理等特征。正是由于视频时空切片不同程度地表现了视频内容的变化情况，提出了基于视频时空切片的关键帧提取方法。具体算法可描述如下：

1)首先提取镜头的视频水平时空切片，设视频图像的高和宽分别为H和W，将每帧灰度化后，提取各帧H／2处的水平方向像素线，随后将水平像素线按列排序拼接出视频的时空切片。水平方向像素线由（x，H／2)处的像素组合生成，其中x＝1，2，...；W 代表像素在原始视频中的横坐标。时空切片的每一列可由每列像素的像素值表示，即可由一个W×1的列向量hi表示。

2)对时空切片进行K均值聚类。先选取K个聚类中心，K可以根据用户的需求自己选择。实验所选K＝4，聚类中心根据镜头长度平均分成4份，取每份的中心作为聚类中心。然后，以时空切片的列向量hi为特征进行K均值聚类。如图3所示，黑色代表的类在时间上是不连续的，如按聚类方法它们会被合并为一类。因此定义，如聚类特征相同但时间不连续的像素线不能被聚成同一类。

3)聚类完成后，在时空切片中还会出现只有极少量帧同属一类的现象。由于视频内容表达具有时间持续性，极少量的帧难以表达语义内容，因此，补充如下定义：如果少于5帧被单独聚成一类，且这个类两边的聚类颜色相同，则认为这几帧聚类错误，应和其前后类被归结为同一类；如果这个类两边的聚类颜色不同，则将它归到与其聚类中心较近的那一类。

图3 聚类后的时空切片示意图

4)提取候选关键帧。聚类后，每一个类（相同颜色但是时间不连续的看做不同的类)代表一个子镜头，然后从每个子镜头中提取一个关键帧。提取的方法为：计算每个类内的相邻帧差，选取帧间差最大的两帧中的后者作为候选关键帧。

5)提取关键帧。为了减少冗余，对候选帧进一步筛选。相邻两个候选关键帧的对应像素相减，P＝｜pk-pk-1｜，pk为候选关键帧中的像素，如果P＞3，则认为两个像素不相同，统计相邻两个候选关键帧中不相同的像素个数P，如果P＞PN／3，PN为每帧的像素个数，则认为相邻两个候选帧不相似。如图4所示，第一行代表7个候选帧，第二行代表相邻两帧之间是否相似，0代表相似，1代表不相似。我们定义如下的关键帧提取准则：如果第二行有单独为0的（连续两帧相似)，则对应的前一帧保留，此时候选帧间的相似程度如图5所示；针对图5，如果第二行有连续2或2个以上个为0（连续3帧以上相似)，则只保留连续相似帧的第一帧和最后一帧，其余去掉。

图4 候选帧间第一次相似性度量

图5 侯选帧间第二次相似性度量

3 实验结果分析

为了验证本方法的有效性，本文从标准视频库OPENVIDEO中选取了大量不同类型的视频进行了实验，下面选取了5个不同类型的视频镜头进行分析说明。

视频Broken是一个特技效果类视频，描述的是盘子在特技作用下慢慢聚拢，然后突然破碎的过程，提取结果如图6所示。

图6 视频Broken的实验结果

视频ROAD是个摄像机运动的镜头，描述的是摄像机随汽车前进、拐弯、拍摄路边景象，最后行驶在新在道路上的过程。图7为提取的关键帧。

图7 视频ROAD的实验结果

视频vipmen是一个摄像机不动，物体运动的镜头。画面描述了白衣男子走到拐角等待另一个男子的到来，然后两人握手交谈，最后白衣男子原路返回。利用本文算法的实验结果如图8所。

图8 视频vipmen的实验结果

视频BOR10-002是个存在物体和摄像机双重运动的镜头，描述的是一架飞机滑行、起飞，最后飞向天空并渐渐消失的过程。图9为提取的关键帧结果。

视频hcil-2002是个静止的镜头，描述的是一个人在说话，视频画面基本没有变化。图10为提取的关键帧结果。

图9 视频BOR10-002的实验结果

图10 视频hcil-2002的实验结果

由以上实验结果可见，我们的算法具有良好的鲁棒性，针对不同类型的视频镜头均能取得良好效果。由于关键帧提取目前尚无统一的评价标准，且评价主观性较大，因此并未与其他算法进行性能比较。但实验结果表明，本算法能准确捕捉视频主要内容，以最少的关键帧反映了视频动态特性，具有良好的人眼视觉感知。

4 结论

提出了一种基于视频时空切片和K均值聚类的关键帧提取方法，由于视频切片中包含了物体和镜头的运动信息，所以提取的关键帧能够很好的描述视频镜头所描述的过程及内容，反映了视频的时空特性。通过K均值聚类，选取的关键帧能以极低的冗余度反映视频连续性，具有良好的人眼视觉感知。

目前的聚类个数还是人为定义的参数，下一步的研究重点是研究自适应聚类个数方法，从而满足视频多样性的需求。另外，还要加深对时空切片的物理特性研究，挖掘更多可以利用的信息，为关键帧的提取提供更加有效的聚类依据。

［1］Taniguchi Y.An Intuitive and Efficient Access Interface to Real-time Incoming Video Based on Automatic Indexing［C］.Proc of ACM Multimedia，1995：25-33.

［2］Zhang H J，Wu J，Zhong D，et al.An integrated system for content-based video retrieval and browsing［J］.Pattern Recognit，1997，30（4)：643-658.

［3］Ferman A M，Tekalp A M.Two-stage Hierarchical Video Summary Extraction to Match Low-level User Browsing Preferences［J］.IEEE Transactions on Multimedia，2003，5（2)：244-256.

［4］Z.Sun，K.Jia，and H.Chen.Video Key Frame Extraction Based on Spatial-Temporal Color Distribution［C］.Proc.Conference on Intelligent Information Hiding and Multimedia Signal Processing，2008：196-199.

［5］Sze K W，Lam K M，Qiu G P.A New Key Frame Representation for Video Segment Retrieval［J］.IEEE Transactions on Circuits and Systems for Video Technology，2005，15（9)：1148-1155.

［6］罗森林，马舒洁，梁静，等.基于子镜头聚类方法的关键帧提取技术［J］.北京理工大学学报，2011，31（33)：348-352.

［7］Huiyu Zhou，Abdul H Sadka，Mohammad R Swash.Feature extraction and clustering for dynamic video summarisation［J］.Neurocomputing，2010，73（10)：1718-1729.

［8］Wolf W.Key selection by motion analysis［C］.In Proc IEEE Int Conf Acoust，Speech Signal Proc，1996：1228-1231.

［9］潘雪峰，李锦涛，张勇东，等.基于视觉感知的时空联合视频拷贝检测方法［J］.计算机学报，2009，32（1)：107-114.