视频镜头分割与关键帧提取算法研究*

王文诗，黄樟钦，王伟东，田 锐

(1.北京工业大学 北京未来网络科技高精尖创新中心，北京 100124；2.北京工业大学 北京市物联网软件与系统工程技术研究中心，北京 100124)

随着互联网及存储媒介的发展，视频数据量正快速增长.存储、管理、分类、索引、检索和浏览等应用中有效地处理视频数据成为一个迫切的问题[1].在这些应用中，关键帧提取方法已经受到工业界和学术界的广泛关注，并且取得了大量的研究成果[2].提取的关键帧集合必须包含与视频相关度最高的内容和避免冗余，同时保留视频的原始信息[3-4].对视频数据的充分表示有助于有效的信息检索和快速浏览整个视频内容.

通常，关键帧提取是在利用镜头边界检测技术将视频分割为镜头之后进行.Priya等[5]采用基于HSV空间的颜色特征和最小二乘逼近方法检测镜头边界.该方法首先使用卡方检验测度(chi-square test)和基于阈值的算法检测切变边界，然后提取剩余的视频帧进行渐变边界检测，在这个过程中，采用亚基莫夫斯基似然比(Yakimovsky likelihood ratio, YLR)检验测度计算帧间相似度.为了降低相机或目标等运动对边界检测性能的影响，该方法采用了新的思想，即使用最小二乘多项式逼近方法进一步计算相似度的近似值.接着，使用渐变边界检测算法检测视频的淡变和溶解区域.Baber等[6]采用图像全局特征和局部特征检测视频淡变和突变边界.Lu等[7]针对交互应用中对实时性的要求，首先采用自适应阈值预测镜头边界的位置和渐变镜头的长度，同时移除大多数非边界帧.然后在可能包含镜头边界的候选视频片段中利用颜色直方图和奇异值分解降低图像特征向量的维数.最后通过一个基于相似度测度的模式匹配方法检测视频突变和渐变镜头.Priya等[8]提出了一种新的镜头边界检测方法.Chasanis等[9]采用经典的基于颜色直方图的方法检测镜头边界.在每一个镜头内，采用改进的谱聚类算法提取关键帧.Guan等[10]首次提出基于关键点特征的关键帧提取框架，该方法在每个镜头内采用一个贪婪算法提取关键帧.实验结果表明，该方法具有很好的性能.Souza等[11]提出一种基于颜色直方图和SIFT局部特征描述子的关键帧提取方法.Zong等[12]提出一种基于动态的颜色直方图和快速的小波直方图的关键帧提取方法.

为了提供视频序列有效的表示和检索，本文提出了一种包含有效镜头边界检测的关键帧提取方法.在每个分割的镜头内，采用颜色特征直方图、小波统计特征和SIFT局部特征描述子计算视频的帧间综合相似度矩阵.最后使用改进的谱聚类算法将镜头帧分组，每一组的中心帧被选为关键帧.实验结果表明，提出的方法提取的关键帧可以获得较高的保真度和重构度提出的镜头边界检测方法获得的F1分数为93.4%.

1 提出的方法

1.1 镜头分割

视频序列可以被看作一个从上到下的层级结构，包括原始视频序列、场景、镜头和帧.这样，视频分析可以针对不同的目的在不同的层级上进行.通常，关键帧提取在检测到的每个镜头中实现，即在每个分割的镜头中提取有代表性的帧作为关键帧.本文中，我们通过镜头边界检测方法[13]进行镜头分割.假设视频序列F={f1,f2,…,fn}，其中n是视频帧的数目，以及视频相邻帧间相似度θ′.为了检测视频镜头，采用聚类方法将视频帧分组.

首先考虑空类Cd，即d=1，将第一个相似度θ′赋值到类C1中.通过顺序遍历所有帧比较相似度θ′与阈值δ，θ′被赋值到已存在的类或新的类中.视频帧聚类步骤如下：

(1) 初始化d=1，i=1；

(2) 赋值Cd={θ′(i,i+1)}；// 这里θ′(i,i+1)指的是两相邻帧i和i+1，通过它们之间的相似度表示.

(3) Fori=2,3,…,n-1//n是视频的总帧数.

(4) Ifθ′(i,i+1) <δ,θ′(i,i+1)被赋值到Cd中；

(5) Else if类Cd中元素的个数等于1，then

(6) 分配类Cd中的元素到类Cd-1；

(7) Else if类Cd中元素的个数大于1且小于5，then

(8) 考虑类Cd-1中最后项θ′(l)、类Cd中第一项θ′(f)和第二项θ′(s)，并且

(9) If (θ′(f)-θ′(l))-(θ′(f)-θ′(s)) < 0.5δ

(10)连接类Cd到类Cd-1；

(11) Elsed=d+1// 新的聚类索引

(12) Endif; endif; endif;

(13) Endfor; //重复步骤(3)～(12)，直到所有的帧按顺序包含在各自相关的类中.

由于某些情况引起的干扰，例如视频中目标和相机同时发生运动，不能被有效地消除，所以应用步骤(5)～(10)避免单个镜头被错误地分成多个镜头.由于镜头边界检测的目标是提取关键帧，用于视频索引和检索，所以没有考虑镜头的变化类型.

1.2 关键帧提取

为了在每个镜头中提取关键帧，采用改进的谱聚类算法[9]将镜头中的视频帧分组.每一组中与其他所有帧的相似度平均值最大的帧被记为关键帧.

假设将镜头S=s1,s2,…,sN分成K组，改进的谱聚类算法的主要步骤如下：

(1) 计算镜头S的帧间相似度矩阵A∈RN×N；

(2) 定义对角矩阵D，它的对角线元素(i,i)等于矩阵A的第i行元素的和.计算拉普拉斯矩阵L=I-D-1/2AD-1/2.

(3) 计算矩阵L的K个主特征向量x1,x2,…,xK，并且构造N×K阶矩阵X=[x1,x2, …,xK].

(5) 使用快速全局k均值聚类算法将矩阵Y的行分成K组.

(6) 分配帧si到类j中当且仅当矩阵Y第i行被分配到类j中.每一类中与其他所有帧的相似度平均值最大的帧被记为关键帧.

2 实验结果与分析

提出的方法在Intel i5，3.2 GHz CPU，4 GB 内存，Windows 10 (64位)环境下和Matlab平台上实现和评估.测试视频数据类型包括新闻、教育、体育、动画等，详细信息如表1所示.另外，人工对数据集进行镜头边界的识别统计作为算法的比较标准.对提出的方法的评估分为两部分：镜头边界检测；关键帧提取.

采用查全率(V)、查准率(P)和F1分数(F1)评估镜头边界检测方法的性能.这些比率值越大，说明算法性能越好.在视频边界检测算法中，参数δ的取值需要实验确定，通常选择范围为[-3,8]，实验中选取固定值δ=2.

提出的方法与基于全局与局部特征的方法[6]进行比较,查准率、查全率、F1分数及其平均值实验结果如表2所示.可以观察到，提出的方法具有更好的结果，查准率、查全率和F1分数三个测度的平均值分别为95.6%、91.2%和93.4%.其中产生的误差主要由视频内容的变化造成，当相邻两个镜头具有很相似的内容时，相应的镜头可能被漏检.

表1 测试视频数据Tab.1 Details of the test video sequences

表2 不同方法的性能比较结果Tab.2 Comparative results of different methods

在视频分析领域，对由不同关键帧提取算法产生的摘要进行评估是最具挑战性的问题之一.提出的方法采用两种客观的评价标准：保真度和镜头重构度[19].设镜头V={F1,F2,…,FN}及提取的关键帧集合keys，其中N表示镜头中的图像帧数.保真度定义为关键帧与镜头中所有帧之间的距离.归一化的镜头保真度(Fid)定义如下

提出的方法在实验中与基于颜色直方图方法(HSV)、基于SIFT特征描述子方法和基于小波统计方法(Wavelet)进行了比较，保真度测度及其平均值的实验结果如表3所示.首先，没有一个特征描述子的性能能针对所有视频内容超过其他描述子.从表3中可以看出，与所有单特征方法比较，提出的方法获得了最好的结果.保真度越高说明提取的关键帧对视频内容的全局描述越准确.

表3 基于保真度测度(Fid)的单特征方法和多特征方法的实验结果比较Tab.3 Comparative results of fidelity by using single feature method and multiple features method

表4 基于镜头重构度测度(SRD)的单特征方法和多特征方法的实验结果比较Tab.4 Comparative results of SRD by using single feature method and multiple features method

为了判断提出的方法相对于其他单特征方法的性能改进，采用下式计算相对改进测度ΔP.

ΔP=(提出的方法测度-单特征方法测度)/单特征方法测度

经过计算，提出的方法的保真度值相对于其他单特征方法的改进都超过了20%，主要是因为单特征描述子不能全面地描述整个图像的内容.图1给出了不同方法的镜头保真度测度的标准差比较结果.可以看出，相对于其他单特征方法，提出的方法的镜头保真度离散程度更小.为了评估关键帧提取方法对视频内容的局部描述质量，表4给出了镜头重构度测度的实验结果，可以看出与其他基于单特征的方法比较，提出的方法取得了更好的结果.

3 结束语

由于视频内容种类繁多，而且没有任何单个图像特征描述子能针对所有视频内容比其他特征描述子优越，所以基于单特征提取关键帧并不总是有效.因此，本文提出了基于多特征的关键帧提取方法.提出的方法包括两个部分：镜头边界检测和关键帧选取.在每个镜头内，通过采用颜色特征直方图、小波统计特征、SIFT局部特征描述子分别对图像描述计算帧间综合相似度测度，然后使用一个改进的谱聚类方法提取关键帧.通过提出的方法提取的关键帧能够代表视频的主要内容，并能解决视频内容多样性带来的困难.实验结果表明，提出的多特征方法获得的平均保真度值和平均镜头重构度值分别为0.826和6.612，平均保真度性能相对其他单特征方法的提高都超过了20%.