视频检索中的关键帧提取方法研究

2019-08-21王红霞晏杉杉

沈阳理工大学学报 2019年3期

王红霞，王磊，晏杉杉

(沈阳理工大学信息科学与工程学院，沈阳 110159)

随着互联网技术的蓬勃发展，日益增长的视频信息充斥在互联网中，大量以视频为主体的信息交流形式不断涌现，如何从海量的视频中进行高效准确的检索成为当下亟待解决的问题。关键帧提取作为视频检索极为关键的一步，是本文研究的重点。因此，如何从完整视频中提取到能代表主要信息的帧是首先要解决的问题。

文献[1]提出了基于镜头边界的关键帧提取算法，假设镜头内的变化较小，取镜头的首帧和尾帧作为关键帧，但存在由于镜头内容变化较大仅仅采用首帧和尾帧不能充分表达视频内容而导致信息遗漏的问题；文献[2]提出了基于内容分析的关键帧提取方法，把颜色、形状和纹理等视觉特征变化明显的帧作为关键帧，但存在由于镜头中物体过快从而导致选取过多冗余帧的不足；文献[3]提出了基于聚类的关键帧提取方法，确定聚类中心，将最接近聚类中心的帧作为关键帧，但往往存在算法复杂度过高而导致运算时间较长且聚类中心和数目难以确定的不足。通过针对已有算法特性深入分析并取长补短，本文提出了基于自定义k值聚类和内容分析的关键帧提取方法，该方法提取的关键帧不仅可最具代表性且关键帧数量能很好把握又不产生冗余。

1 基于自定义k值聚类和内容分析的关键帧提取方法

1.1 概述

聚类方法是常见的一种关键帧提取方法，该方法主要是把镜头内的帧按照相似度进行分类，相似度越高，划分到同一类的可能性越大，而不同类之间的相似度差异比较大，最后提取同类中的能代表这类主要内容的一帧作为这类的关键帧，最终得到的k个关键帧则为这个镜头的关键帧。本文通过对聚类算法的深入研究，提出了基于自定义k值聚类和内容分析的关键帧提取方法，对已有的聚类算法进行了改进，并融合了内容分析方法，使得提取的关键帧相比于传统方法无论在数目合理性还是内容代表性上都有较大的提升。

选取一个自定义k值。假设经过镜头分割之后的一个独立镜头内有n帧(可对每一帧编号，为1，2，……,n)，而本文选取的自定义k值的取值为n/4

算法流程图如图1所示。

图1 提取关键帧流程图

算法具体步骤如下。

(1)启动算法，为每个镜头的帧序列进行编号，用fi(i=1，2，…，n)表示。确定k值大小，选取前k帧，将f1帧到fk帧的每一帧单独作为一个类，且为各自所在类的中心，形成k个聚类。

(2)计算前k帧中两两帧之间的互信息量，把互信息量最大的两帧聚类为一类，因此聚类数目减1，此时的聚类为k-1个。

(3)依次加入第m帧，m=k+1，k+2，……，n-1，n。如果m=k+1，k+2，……，n-1，执行第4步；否则，执行第5步。

(4)加入一帧，作为单独的一个聚类，且为这个聚类的中心，与之前的k-1个聚类形成k个聚类。循环第2步和第3步。

(5)加入最后一帧，根据基于镜头边界的关键帧提取算法，将最后一帧作为关键帧，且为单独一类，得到k个聚类。

(6)对于得到的k个聚类，针对每一个聚类中的所有图像帧，根据基于视频内容分析的关键帧提取算法，得到每一帧的统计直方图后求平均值，把聚类中最接近平均值的一帧作为关键帧。

(7)算法结束，得到k个关键帧。

1.2 互信息量特征提取

互信息量作为图像配准的一个准则，通常用来测量并统计两个随机变量相关性[5]。假设X是一个离散型的随机变量，其n个取值分别为a1、a2、……、an。各个取值出现的概率分别为p1=p(a1)、p2=p(a2)、……、pn=p(an)，其中各个取值的概率和为1，如式(1)所示。

(1)

随机变量X的取值是有限个或可列无限多个，一般情况下没有固定的函数式可以表示，但存在一个概率分布的函数f(p1，p2，……，pn)，在满足连续性、等概率时为单调函数和可加性三个条件时，函数形式是确定的，如式(2)所示。

(2)

通常把式(2)称为熵，用Hs表示，其可对随机变量的不确定程度进行度量，用式(3)表示。

(3)

若设定图像A和B，其互信息量MI可定义式(4)所示。

MI(A,B)=Hs(A)+Hs(B)-Hs(A,B)

(4)

式中：Hs(A)和Hs(B)分别为图像A和B的熵；Hs(A，B)为二者的联合熵。

随机变量X和Y的平均互信息和联合熵的关系可如式(5)所示。

I(X,Y)=Hs(X)+Hs(Y)-Hs(XY)

(5)

式中Hs(X)和Hs(Y)分别为X、Y的边界熵。

平均互信息可通过其信息量和条件熵来定义，如式(6)所示。

I(X,Y)=Hs(X)+Hs(X|Y)

(6)

1.3 统计直方图

直方图是计算相邻两帧图像中对应像素位置变化的平均值[6]，并将相邻帧间的差值定义为

(7)

式中：Ik(x,y)和Ik+1(x,y)分别表示第k帧和第k+1帧在(x,y)处的亮度值；M和N分别表示该帧的高度和亮度。

1.4 帧间相似度计算

图像帧之间的相似度匹配是视频检索的关键性技术，相似度匹配的好坏直接影响最后的检索结果。常用的帧间相似度计算方法有欧式距离、马氏距离和二次式距离三种[7]。

欧式距离是空间中两点之间的真实距离，如果该特征向量正交无关且各个分量之间权值相同，即可使用欧式距离计算帧间相似度。A和B两个特征向量之间的欧式距离如式(8)所示。

(8)

式中：m表示特征向量的维度；n可以取1或2。在本文，计算帧间相似度时，采用的是这种方式。

马氏距离适用于特征向量的各个分量之间权值不同或分量之间有相关性的情况，如式(9)所示。

D=(A-B)iC-1(A-B)

(9)

式中C表示协方差矩阵。

如果各个分量之间没有相关性，如式(10)所示。

(10)

式中Ci表示各个分量的方差。

二次式距离则根据不同颜色间的相似程度计算相似度，如式(11)所示。

D=(Q-I)iA(Q-I)

(11)

式中：Q和I分别表示不同的颜色直方图，A为颜色相似矩阵，A中的数据为对应下标颜色区间之间的相似度。

2 实验结果与分析

为更加形象的对比本文方法与其它不同方法提取关键帧的效果，选取一段AVI格式的且分辨率为544×960的较短视频，分别使用基于镜头边界的关键帧提取方法、基于内容分析的关键帧提取方法、基于聚类的关键帧提取方法以及本文方法提取关键帧做对比。

基于镜头边界的关键帧提取方法，这种方法最简单，直接选取该镜头内部的第一帧、最后一帧和中间的那一帧作为关键帧，如图2所示。

图2 基于视频镜头边界的关键帧

基于视频视觉内容分析的关键帧提取方法，先把第一帧选为关键帧，对于其后面的帧，都以这一帧为参考。在计算得到后面各帧的特征信息之后，都需要与第一个关键帧进行做差比较。如果，计算到某一帧的时候，所得的差值大于事先设定好的阈值，则把这一帧加入关键帧序列。以此类推，直到视频帧序列的最后一帧为止，如图3所示。

图3 基于视频视觉内容分析的关键帧

基于聚类的关键帧提取方法，首先，确定初始的聚类中心；然后，通过判断每帧图像与这个聚类中心的距离来确定是否归为该类。将这个距离与预设阈值比较，可有两种结果，一种是小于阈值，当前帧归为该类，另一种是大于阈值，当前帧作为新的聚类中心。将镜头中的所有帧全部进行分类后，分别计算每帧与其所在那类聚类中心的差值，选取差值最小的帧作为关键帧如图4所示。

图4 基于聚类的关键帧

利用本文方法提取的关键帧如图5所示。

图5 本文方法的关键帧

由以上结果可知，不同方法得出的关键帧及数目的确存在差异，但本文方法，在数量上适中，且每一幅关键帧图像存在明显差异，能较好的表示这段视频的关键内容。对于视频中关键信息，即大熊猫动作的变化展示的非常清晰，且不冗余，效果十分明显。

通过以上实验，可以看出，文本方法可行，但依然需要进一步验证其提取到的关键帧的准确性。通常，使用准确率和查全率两个参数评价关键帧提取的效果[8]，如式(12)、式(13)所示。

(12)

(13)

选取一段稍长的视频，使用以上方法提取关键帧，并与人工标注的关键帧进行对比。对于所选视频，人工标注的关键帧数为8，检测结果如表1所示。

表1 不同方法提取关键帧检测结果

从准确率和查全率来看，本文方法取得了较高的准确率和查全率，结果显示本文方法相比其他方法，在提取关键帧方面更有效。

本文进一步比较了四种方法的运行效率，选取3段上述格式视频进行测试，三种方法各自的帧处理平均时间如表2所示。

表2 算法处理时间比较

由表2可知基于镜头边界的方法耗时最少，原因在于该方法选取首帧和尾帧作为关键帧，只需要很小的计算量。但是该方法选取关键帧不够灵活，极容易造成信息遗漏。基于内容分析的方法根据视觉特征的变化选取关键帧，该方法选取的关键帧虽然相对基于镜头边界的方法效果有所提高，但面对运动较快的视频目标容易产生大量冗余，大大降低了运行效率。基于聚类的关键帧提取方法由于算法的复杂度较高，在处理时间上比基于内容分析的方法还要高些。本文的基于自定义k值聚类和内容分析的关键帧提取方法，在保证提取的关键帧代表性的前提下解决了基于内容分析方法的冗余帧问题，在运行效率上要高于基于内容分析方法和基于聚类方法。虽然本文方法相比于基于镜头边界方法耗时略高，但对原视频内容的表达更为准确，且耗时在相同数量级，满足工程要求。