基于语义相关的视频关键帧提取算法

王俊玲，卢新明

山东科技大学 计算机科学与工程学院，山东 青岛 266500

随着多媒体信息的发展，视频成为人们获取信息的重要途径，面对海量的视频，如何从视频中提取关键部分，提高人们看视频的效率已经成为人们所关注的问题。视频摘要技术正是解决这一问题的关键，在视频摘要技术中的核心部分就是关键帧的提取。关键帧的提取可以分为以下六类：

（1）基于抽样的关键帧提取

基于抽样的方法是通过随机抽取或在规定的时间间隔内随机抽取视频帧。这种方法实现起来最为简单，但存在一定的弊端，在大多数情况下，用随机抽取的方式得到的关键帧都不能准确地代表视频的主要信息，有时还会抽到相似的关键帧，存在极大的冗余和信息缺失现象，导致视频提取效果不佳[1]。

（2）基于颜色特征的关键帧提取

基于颜色特征的方法是将视频的首帧作为关键帧，将后面的帧依次和前面的帧进行颜色特征比较，如果发生了较大的变化，则认为该帧为关键帧，以此得到后续的一系列关键帧。该方法针对相邻帧进行比较，不相邻帧之间无法进行比较，对于视频整体关键帧的提取造成一定的冗余。

（3）基于运动分析的关键帧提取

比较普遍的运动分析算法是将视频片段中的运动信息根据光流分析计算出来，并提取关键帧。如果视频中某个动作出现停顿，即提取为关键帧，针对不同结构的镜头，可视情况决定提取关键帧的数量。但它的缺点也十分突出，由于需要计算运动量选择局部极小点，这一过程十分复杂，会消耗大量时间，并且由此得到的关键帧不一定能够准确描述视频内容[2-3]。

（4）基于镜头边界的关键帧提取

Nagasak 等人[4]提出了基于镜头边界的关键帧提取[5]算法，主要是通过镜头内容的变化，利用算法将视频以镜头为单位分割并提取关键帧。这种方法需要将输入的视频分段，分别提取第一帧、中间帧、最后一帧作为该片段的关键帧。由于每个镜头内的内容几乎没有变化，而不同镜头间存在差异，因此提取出的关键帧数量相对稳定。与抽样方法相比，镜头分割算法考虑了内容信息，在镜头内容变动较小、动作不剧烈的视频中十分适用。当镜头内容变化复杂，或者强烈运动时，由于不能够完全表达镜头内的全部内容，有时会丢失视频的重要部分。

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

基于视频内容的关键帧提取算法[6-11]是目前使用最广的方法，其基本思想是在每个内容中设定第一帧为对比关键帧，根据颜色、形状、纹理等视觉特征将对比关键帧与下一视频帧进行相似度比较，当相似度小于设定的阈值时，将该视频帧加入关键帧集合，并将该帧作为对比关键帧，以此类推，直到检测完该内容为止。该方法提取出来的关键帧较多地保留了原视频的内容，与基于镜头边界的方法进行比较，更加注重视频内容的变化。缺点是阈值选取影响关键帧提取的质量，且该算法计算量大，对于内容复杂、变换频繁的视频，效果不佳。

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

基于聚类的关键帧提取算法[12-15]充分考虑了镜头内以及镜头间的相关性，将相似的视频帧分为一簇，满足簇内相似度大，簇间相似度小的原则，依次从每簇中选取一帧作为关键帧。该方法解决了不同镜头之间可能存在相似视频帧的情况，减少了信息冗余。缺点是聚类数目和聚类中心需要提前设定，在对视频内容不了解的情况下，提前设定聚类数目和中心是非常困难的，且运算时间较长。

由于传统的关键帧提取算法单纯地提取底层信息，存在大量信息缺失、冗余现象突出等问题，本文提出了一种基于语义的视频关键帧提取算法，该算法可以减少信息的缺失和降低关键帧的冗余。

本文算法流程：

（1）把视频分成n帧，聚成n个类。

（2）利用感知哈希算法对n个类进行相似性度量。将相似的帧合并成一类形成k类(k＜n)，同一类内的视频帧是相似的，类与类之间的视频帧是不相似的。

（3）从每个类中提取一帧作为关键帧，如果一个类中帧的数目太少，则这个类不具有代表性，可以直接与相邻的帧合并，得到层次聚类的初始化结果。

（4）得到的关键帧可能会存在冗余现象，再使用语义相关算法对其进一步处理，得到最后的关键帧。

1 视频关键帧初步提取

1.1 感知哈希算法判断图像相似度

感知哈希算法通过将一幅图像转化成固定长度的字符串（指纹）[16]，通过计算图像间汉明距离(H)判断其相似性。

本文利用均值哈希算法进行计算，步骤如下：

（1）将图像尺寸缩小为8×8大小。

（2）将缩小后的图像进行灰度化处理。

（3）计算图像像素的平均值（将大于均值的记为1，小于均值的记为0）。

（4）生成哈希值，得到一个64位的0，1序列，即为哈希指纹。

生成哈希指纹后对比两幅图像的哈希指纹，计算它们之间的汉明距离(H)，相同位置的值相同，距离不变，不相同距离加1，通常情况下，如果汉明距离(H)小于10，则认为两幅图像是相似的，汉明距离大于10，则认为两幅图像不相似，由此：

通过图1 可以看出，（a）和（b）相似，汉明距离为6，（a）和（c）不相似，汉明距离为26。由此可以看出哈希指纹越接近，相似度就越高。

图1 哈希指纹提取

1.2 计算图像信息熵

信息熵的概念由Shannon[17]提出来的，用来度量信息的不确定性。一幅图像可以看成一个二维的离散信号，用信息熵可以衡量图像中包含信息量的多少，也可称之为图像熵[18]。对于一幅灰度级为L(1＜L ＜256)，大小为M×N的灰度级图像I，用f(x,y)表示图像中坐标为(x,y)的像素灰度值，则f(x,y)的取值范围是[0,L-1]。令fi为图像中灰度级为i的个数，则灰度级i出现的概率为：

根据信息熵的定义，二维图像的信息熵可定义为：

此时，一幅图像中含有多少信息量就可以用图像熵来衡量。如图2所示，信息量越多，图像熵越大，信息量越少，图像熵越小。

图2 计算图像信息熵

1.3 视频关键帧的初步提取

首先将视频分成n帧，聚成n个类，然后通过计算汉明距离对n个类进行合并，得到k个类(k＜n)，最后计算每个类中图像的信息熵，取熵值最大的图像为该类视频的关键帧。

由图3可以看出，n/k=12 时，分类的准确率能达到最大值，本文取得k值为n/12。

图3 k 值随分类准确率的变化曲线

2 语义相关算法提取视频关键帧

2.1 SIFT特征提取算法

尺度不变特征变换[19-21]（Scale Invariant Feature Transform，SIFT）是由加拿大教授Lowe 于1999 年提出的，用来描述影像中局部性特征，其优点是对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性，可以在海量特征数据库中进行快速、准确的匹配。

SIFT算法实现流程图如图4所示。

SIFT特征提取算法的实现过程如下：

步骤1尺度空间极值点检测。

将一个变化尺度的高斯函数G(x,y,σ) 与原图像I(x,y)的卷积定义为一个图像的尺度空间，并将其设为L(x,y,σ)。

其中，*表示卷积运算。高斯函数表示为：

公式中的m、n代表高斯模板的维度；函数坐标中，(x,y)代表图像的像素位置；σ则表示尺度空间因子，值越小表示图像被平滑得越少，相应的尺度也就越小。为了在尺度空间中有效地检测到稳定关键点的位置，使用高斯差分算子（Difference of Gaussian，DOG）进行极值检测。

在尺度空间中，需要检测出稳定关键点的位置，极值检测提供了有效的检测方法。这里使用高斯差分算子进行极值检测。

使用该公式得到的关键点是由DOG空间的局部极值点组成的。通过对同一组内各DOG相邻两层图像之间进行比较，从而完成对于关键点的初步探查。其中每一个像素点，都要与它上下左右所有的相邻点比较，观察其图像域与尺度域的相邻点大小，才能找到该DOG函数的极值点。

步骤2特征点定位。

离散空间的极值点，可以通过上述的高斯差分算子方法进行检测。如果需要精确确定关键点的位置和尺度，就需要用到拟合三维二次函数。由于DOG 算子会产生较强的边缘响应，这种方法不但能够去除不稳定的边缘响应点，也去除了低对比度的关键点，从而增强了匹配稳定性，提高了抗噪声能力。

步骤3关键点的方向确定。

为了保持描述符具有旋转不变性，利用图像的局部特征，给每一个关键点分配一个基准方向，使用图像梯度求取局部结构的稳定方向。这种方法需要采集像素的梯度和方向分布特征，将DOG检测中得到的关键点，在其所在的高斯图像3σ邻域窗口内将两种数值采集出来。梯度的模值和方向如下：

图4 SIFT算法实现流程图

通过以上步骤，已经找出了关键点，以每一个关键点为圆心，1.5σ为半径的圆内，对关键点进行梯度计算。完成相关计算后，使用基于梯度直方图的统计方法，以直方图的形式，统计邻域内像素的梯度和方向。梯度直方图将360°每10°分成一个柱（bins），共分为36个柱，每个柱都代表自己的方向和数值。如图5 所示，直方图中的峰值代表关键点的主方向（为简化，图中只画了8个方向的直方图）。

图5 直方图表示

在方向梯度直方图中，峰值代表在该特征点处邻域梯度的方向，直方图中的最大值就作为该关键点的主方向。为了增强匹配的效果，只保留峰值大于主方向峰值80%的方向作为该关键点的辅方向。

步骤4关键点描述。

特征描述子的生成，是对关键点当前尺度周围区域的梯度进行统计得出的。以关键点为圆心，将其邻域旋转θ，从而使得旋转具有不变性。旋转后得到的图像，再次将关键点作为中心，并将其分割成16×16的均匀区域，组合形成共计16个4×4的子窗口，然后利用高斯模糊增加距离关键点较近区域的权重，同时减小距离关键点位置较远的区域权重。

如图6，在每个4×4的区域内，分别对0，45，90，135，180，225，270，315 这8 个方向的梯度进行累加，最后用4×4×8共计128维特征向量表示特征描述子。

图6 特征描述子

经过以上一系列操作后，将去除了尺度、旋转变化影响的SIFT特征描述子，再进行进一步的归一化处理，以减少光照的影响。最后按特征点的尺度对特征描述向量进行排序，生成SIFT特征描述向量。

2.2 BOF算法

BOF（Bag of Feature）是用于图像和视频检索的算法，源自于BOW（Bag of Words）算法。BOW是文本分类中的一种，通过抓取一段文本的关键词，根据关键词出现的频率确定这段文本的中心思想。BOF 算法正是运用这种思想，不同的是BOF 抽取的关键词是图像的关键特征。

算法步骤：

（1）视频单词提取：首先用SIFT算法提取图像库中所有的图像特征，生成图像库中每一幅图的特征点及描述符。

（2）视觉词典的构建：用k-means 算法对图像库中的特征点进行聚类，得到视觉词典。

（3）针对输入特征集，根据视觉词典进行量化。

（4）图像表示：统计每张图像在每个聚类中的特征的个数，每张图片可以由一个分布直方图表示，每个图像都可以由基本词汇表示。

（5）根据直方图构造特征到图像的倒排表，通过倒排表快速索引相关图像。

（6）根据索引结果进行直方图匹配。

3 实验与分析

本文在Intel i5，2.20 GHz CPU，4 GB内存，Windows10（64位）环境下python平台上实现该算法。

3.1 实验1

本文选取VSUMM[22]提供的YouTube数据集进行实验。YouTube数据集中共包括50个不同的视频，所有视频采用FLV和AVI多媒体标准格式，显示分辨率为352×240，视频的时长在1～10 min 不等，视频主要有广告视频、商业视频、新闻节目、电视节目、卡通视频。该数据集还提供了50 名用户手动提取的关键帧，方便了研究者做对比实验。本文从该数据集的每一类中随机抽取视频进行实验，实验视频信息如表1 所示。图7 和图8是在YouTube数据集选取视频v71进行人工摘要与本文算法摘要进行对比实验的结果。

表1 实验信息表

从图7 和图8 的实验结果中可以得知，本文算法提取的关键帧数量比人工提取的关键帧数量少，且冗余少，涵盖的视频内容丰富，能较好地表现视频的完整信息。本文采用准确率（Accuracy Rate，AR）与误差率（Error Rate，ER）对算法进行评价，其计算公式为：

图7 人工提取关键帧

图8 本文算法提取关键帧

其中，nu为用户提供的视频关键帧数量，nm为视频关键帧提取算法生成的视频关键帧与用户提供的视频关键帧相匹配的帧数，nmˉ为视频关键帧提取算法生成的视频关键帧与用户提供的视频关键帧不相匹配的帧数。表2 为本文算法与VSUMM 算法准确率和误差率的比较。

表2 本文算法与VSUMM算法准确率与误差率

通过绘制直方图更直观地对比两种算法的准确率和误差率，图9和图10分别为准确率比较和误差率比较。通过比较可以看出，本文算法比VSUMM算法略好。

图9 准确率直方图比较

图10 误差率直方图比较

选译v14进行实验，采用本文算法与VSUMM算法分别提取关键帧，结果如图11～图13 所示。可以得出本文算法比VSUMM 算法能更好地表达视频内容，且冗余较少。

图11 VSUMM提取关键帧

图12 本文算法提取关键帧

图13 用户提取关键帧

3.2 实验2

采用OVP数据集[23]进行实验。该数据集有50个视频，包含多种类型的视频，视频时长1～4 min 不等，采用统一多媒体标准格式MPEG-1，视频分辨率为352×240像素，以每秒29 帧的速度播放，每个视频都有来自5 个不同用户的人工视频关键帧提取。为了进一步评价本文提出的算法，以数据集人工提取关键帧作为结果对比评价的基础，采用两种评价指标对实验结果进行分析：

（1）用漏检率和错误率进行对比分析；

（2）用精度（Precision Rate，PR）、召回率（Recall Rate，RR）、F-Measure（F）进行对比分析。

漏检率指未检测出的关键帧所占的比率，漏检率越低，说明检测出的关键帧越能代表视频的完整性；错误率指检测出的关键帧中提取错误的关键帧所占的比率，错误率越低，说明该算法准确率越高。将本文算法与DT[24]、STIMO[25]进行比较。公式如下：

其中，RM表示漏检率，RF表示错误率，Nm表示未检测出的关键帧数目，Nc表示检测出的关键帧与人工检测出的关键帧正确匹配的数目，Nj表示检测出错误的关键帧数目。由表3可以看出，本文算法的漏检率有所降低，错误率高于 STIMO 算法，但比 DT 和 VSUMM 算法有所提高。

精度（PR）是指提取的视频关键帧中选中正确关键帧的能力（正确关键帧是指用户摘要中所具有的关键帧）。召回率（RR）是指生成的视频关键帧中符合用户要求的性能。F-Measure（F）是精度与召回率的均衡指标，是对视频关键帧质量的总体评估。计算公式如下：

表3 不同算法提取的关键帧漏检率和错误率

式中，nm表示视频关键帧提取算法创建的视频关键帧与用户提取关键帧相匹配的数量；na表示视频关键帧提取算法创建的总帧数；nu表示用户提取的关键帧总帧数。

通过表4对比结果可以看出，本文算法的精度高于其他算法，而且视频关键帧的质量也比较好。

表4 计算不同算法精度、召回率、F-Measure

4 结束语

本文提出了一种基于语义相关的视频关键帧提取算法。该算法首先使用层次聚类算法对视频关键帧进行初步提取，然后结合语义相关算法对初步提取的关键帧进行直方图对比，去掉冗余帧，确定视频的关键帧。计算各种评价指标来衡量本文算法，通过与其他算法进行比较可以看出本文算法性能略好一点，但是仍然存在误检和漏检的问题。由此需要进一步分析，改革特征的提取方法，降低漏检率和误检率。