基于双向自适应时空切片的关键帧提取算法

韩震博

（四川大学计算机学院，成都610065）

1 视频关键帧提取概述

随着大数据时代的到来，网络上的视频数量大幅增加，如何快速且有效地在大量的视频中找到所需要的视频片段成为人们关注的热点问题。

视频是由连续变化的图像帧组合而成，人们将这段连续的图像帧中能够有效地代表视频主要内容的帧称为关键帧。关键帧提取技术在视频处理领域中发挥着重要作用，通过对视频中关键帧的提取，能有效地减少冗余信息，使得需要处理的数据量大大减少，为后续的视频处理提供便捷。

目前，关键帧提取技术主要包括以下4类[1]：

（1）基于视频运动信息的关键帧提取：

视频中包含着大量的运动信息，可以通过对视频中运动信息的提取及分析，实现视频关键帧的提取，具体的方法包括基于运动特征的关键帧提取方法[2]、基于运动分析的关键帧提取方法[3]等。

（2）基于视频内容的关键帧提取：

这类方法使用视频帧序列中每一帧图像的纹理、颜色、形状等底层特征作为关键帧提取的依据[4]。相邻帧间特征差异的大小可以有效地反映出视频内容变化的显著程度，因此可以通过这类方法完成关键帧的提取。

（3）基于视频镜头信息的关键帧提取：

这类方法首先通过一定的方式，将视频分割成若干个独立的镜头，然后按照一定的规则在每个独立的镜头中完成关键帧的提取。常用的方法有基于像素的关键帧提取方法[5]以及基于直方图的关键帧提取方法[6]等。

（4）基于聚类的关键帧提取：

这类方法对视频镜头间以及视频镜头内信息的关联性进行充分利用，基于帧间图像的相似性对视频序列进行聚类，并从每一类聚类结果中选出一帧作为关键帧。常用的聚类方法包括K-means算法、层次聚类算法[7]等，各聚类算法有着不同的优缺点。

2 基于双向自适应时空切片的关键帧提取算法

针对现有关键帧提取算法中常出现的存在漏帧、冗余帧等问题，本文提出了一种基于双向自适应时空切片的关键帧提取算法。这一部分将对本文中采用的关键技术及算法流程进行介绍。

2.1 基于活动强度图的时空切片位置选择

时空切片是一种高效的视频时空分析方法，具有计算量低、抗干扰能力强等特点[8]。时空切片是将视频帧序列中每一帧在选定的同一位置上的像素信息进行提取，并组合成一幅具有完整的视频时间维度信息的二维图像。时空切片通常有三种取法：垂直切片、水平切片和对角线切片[9]，如图1所示。

图1时空切片示意图

在进行时空切片时，基本都是基于视频帧中心点横（纵）向的延伸线作为切片位置，但该切片位置并不一定属于视频中物体运动的区域，因此，基于该位置提取出的时空切片并不一定能较好地包含视频中的物体运动信息。

为了获取视频中内容变化的区域及强度，本文定义了活动强度图，其计算方式如下：首先，对图像帧序列进行灰度化处理；其次，从第一帧开始，计算相邻两帧在同一像素点上灰度值的差值，当该值的绝对值大于设定的阈值时，则认为该像素点在相邻两帧间变化明显；如果同一像素点在相邻两帧间灰度值的差值的绝对值大于设定的阈值，那么将此值进行累加，并将得到的值称为该像素点的灰度变化累加值；最后将各个像素点的灰度变化累加值归一化到[0,255]，即可得到活动强度图。活动强度图的计算公式如下：

式（4）中，I(x,y)为最终得到的活动强度图。

对一段“投掷铅球”的视频进行活动强度图的提取，提取结果如图2所示。

图2活动强度图

在活动强度图中，灰度值越大的点代表该像素点的信息变化强度越大。因此在进行时空切片时，可以选择信息变化强度最大的行（列），作为时空切片的位置，使得提取到的时空切片中能够包含更多的视频信息。

2.2 基于切片位置自适应的双向时空切片方法

基于时空切片的关键帧提取效果在很大程度上受时空切片包含视频中物体运动的信息量的影响，也就是说，为了得到更好地关键帧提取效果，时空切片中就要尽可能多地包含视频中的物体运动信息。

本文提出的基于切片位置自适应的双向时空切片方法能够有效地解决这一问题，一方面，基于活动强度图的时空切片位置选择能够保证在单一方向的时空切片中包含更多的图像信息；另一方面，采用双向时空切片可以在一定程度上解决单一方向的时空切片时空间信息匮乏的问题。仍以上述“投掷铅球”的视频为例，本文提取出的双向时空切片图像如图3所示。

图3双向时空切片图像

2.3 算法描述

下面是本文算法的整体步骤：

步骤一：提取视频帧序列的活动强度图

对灰度化处理后的视频帧序列进行活动强度图的提取；

步骤二：选择最佳时空切片位置

统计活动强度图中像素值最大的行和列，并将该行和该列分别作为此视频帧序列进行水平切片及垂直切片的位置；

步骤三：提取出视频的双向时空切片

根据最佳时空切片位置，提取出视频帧序列的双向时空切片；

步骤四：通过改进K-means算法对提取出的双向时空切片进行聚类

使用改进K-means算法对双向时空切片图进行聚类。图4所示为图3的聚类结果。

图4聚类结果

在聚类结果中，不同的颜色代表不同的类别。值得注意的是，由于视频具有时间上的连续性，因此，将颜色相同但不连续的类视为不同的类别。

步骤五：对连续视频帧数量少的类进行处理

在对双向的时空切片进行聚类时，可能会出现较少数量的连续视频帧被聚为一类的情况，这种情况往往是由于视频中存在干扰信息所致，因此在这一类中提取出的关键帧往往不能很好地表达视频信息。对此，本文采用如下的处理方案：当连续3帧及以下的视频帧被分为一类时，将这一类归并到其相邻的类中，若这一类两侧相邻的类颜色相同，则将这一类与其两侧相邻的类合并为一类；若这一类两侧相邻的类颜色不同，则将这一类合并到相邻两类中聚类中心间的距离更近的那一类中。

步骤六：候选关键帧的提取

在完成对双向时空切片的聚类后，选取每一类的聚类中心作为候选关键帧。

步骤七：筛选最终的关键帧

双向的时空切片图可以在一定程度上弥补单一方向时空切片的空间信息不足的问题，但二者一般会包含冗余信息，进而导致提取出的候选关键帧存在冗余，因此需要对候选关键帧进行进一步的筛选。本文采用的筛选方法是通过计算相邻候选关键帧之间的时间间隔进行的，若相邻候选帧间的时间间隔大于5帧，则认为这两帧间不存在冗余，均为最终的关键帧；否则，两帧间存在冗余，保留两帧中与各自聚类中心距离更近的帧作为最终的关键帧。

算法流程图如图5。

图5算法流程图

3 实验设计与结果分析

本文实验环境如表1所示。

表1 实验环境

3.1 实验数据与评价指标

本文方法是对整个视频区域进行活动强度图的提取，在视频背景区域变化较小时，提取到的活动强度图能更为精确的反映视频中物体的运动信息。因此，本文从体育、演讲、汽车、太空四类视频中分别选取三个视频背景区域变化较小的视频作为测试视频。实验数据来源于UCF101数据集[10]以及开放的标准视频库[11]，实验中使用的测试视频长度不一、分辨率不同、内容差别明显，能够充分验证各关键帧提取方法的有效性。

目前，在视频关键帧提取领域中存在多个较为通用的评价指标，本文选取了查全率与查准率两个指标来评价本文方法的性能。

（1）查全率

该指标可以用来衡量关键帧漏检的程度。计算公式如下：

式（5）中，Nc为提取正确的关键帧数量，Nm为漏检的关键帧数量。

（2）查准率

该指标可以用来衡量提取到关键帧的准确程度。计算公式如下：

式（6）中，Nf为误检的关键帧数量。

3.2 实验结果与分析

分别使用本文方法与直方图法、文献[12]提出的方法、文献[13]提出的方法对测试视频进行关键帧的提取，并通过查全率、查准率来衡量各方法的性能。实验结果如表2所示。

从实验结果可以看出，在不同的视频类别下，本文方法提取关键帧的查全率与查准率相较于各对比算法均有明显的提升。由此可见，本文提出的基于双向自适应时空切片的关键帧提取算法性能优良，使用该算法提取出的关键帧能够较为准确地完成对视频主要内容的表达。

表2 在不同视频类别下各方法的查全率与查准率统计

4 结语

本文提出了一种基于双向自适应时空切片的关键帧提取算法，通过引入活动强度图充分利用视频的运动信息，进而实现了垂直与水平方向上切片位置自适应的时空切片方法，在使得后续聚类结果具有时间信息的同时，解决了传统的固定位置时空切片、单一方向时空切片导致提取信息不足的问题，然后通过改进Kmeans算法实现了阈值自适应的候选关键帧提取，最终，对从两幅时空切片图中提取出的候选关键帧进行进一步的筛选，得到最终的关键帧。实验结果表明，本文方法在能够保证较低压缩比的情况下，查全率与查准率明显优于同类算法，提取出的视频帧能够有效地反映视频的主要内容。