知网论文查重第一章 绪论

1.1 研究背景

随着当前互联网的飞速发展，多媒体技术逐渐兴起，与视频相关的网络流量急剧增长，面对如此海量的视频数据应该如何从中选择自己感兴趣的信息对于众多互联网用户来说是一件富有挑战性的事情，因此与视频相关的技术与应用，如视频搜索、视频快速浏览、视频索引与存储等用户需求也日益增加。在这些技术与应用背后，一个核心问题就是如何快速地浏览海量的视频数据并从中获取和展现视频的关键性内容。为了解决该问题，视频摘要技术应运而生。

视频摘要技术是以自动或半自动的方式，利用计算机技术来分析和处理视频的结构和内容，从原始的视频数据中提取具有代表性的部分，并将其合并成紧凑的、简明的、用户可浏览的、能够充分展现原始视频内容的缩略形式^[1]。在现实生活中，视频摘要技术有着广泛的适用性和应用价值，其主要的应用范围如下：（1）视频存储与检索方面的应用^[2]：由于视频数据的多样性、海量性，对于视频数据的检索十分不便，而利用视频摘要技术对视频数据的存储进行改进后，检索速度可以得到极大程度的提升。同时视频摘要还可以作为视频数据库的索引，通过视频摘要，用户可以快速地查询到自己感兴趣的视频内容。（2）新闻视频方面的应用^[3]：在现实生活中，每天都有大量的新闻视频，要想仔细地浏览每一则新闻是不可能的，对于大多数新闻观众来说，自己感兴趣或者关系紧密的新闻会得到主要的关注，因此可以利用视频摘要技术将新闻制作成摘要的形式，以便用户从中选取自己感兴趣的新闻片段。（3）影视广告业方面的应用^[4]：在当前的影视行业中，在电影正式上映之前通常会花费高昂的费用来制作一部关于影片的宣传片，以供用户提前浏览影片的主要内容，从而吸引用户，然而宣传片的制作通常由人工进行，成本较高，耗时较长，因此，以一种自动或半自动的方式来制作宣传片已成为影视广告行业的迫切需求。（4）家庭娱乐业方面的应用^[5]：由于当前互联网上视频数据的多样性和丰富性，用户在选择自己感兴趣的视频时通常具有盲目性，为了解决该问题，目前主流的做法是为每一段视频进行人工打分，用户根据分数的高低来选择需要观看的视频，然而人工打分的方法具有很强的主观性，对于同一段视频，不同的人极有可能打出差异较大的分数，在一定程度上会误导用户，而视频摘要技术可以通过客观的方式为每一段视频提取其缩略形式，用户可以通过观看视频的缩略形式来决定视频的观看价值。

由于视频摘要技术的应用范围广且具有较大的实用价值，学术界对视频摘要技术进行了广泛的研究。目前视频摘要技术主要分为基于视频片段的摘要和基于视频关键帧的摘要，其中，基于视频片段的摘要也称为动态视频摘要，主要是通过提取原始视频中的一小段视频或者合并多个所提取的视频片段来展现原始视频的主要内容^[6]，而基于视频关键帧的摘要也称为静态视频摘要，该种摘要技术是以一幅或多幅关键性的视频帧图片的方式来反映原始视频的主要内容^[6]。在本文中，我们主要研究基于关键帧的视频摘要的设计与实现。基于关键帧的视频摘要技术的核心在于如何通过选取若干具有代表性的视频帧图片来最大程度地展示原始视频的主要内容，这里我们把具有代表性的视频帧图片称为视频的关键帧，因此设计一个性能良好的视频关键帧提取算法是解决基于关键帧的视频摘要问题的核心所在。

尽管视频关键帧提取算法的设计问题已经在学术界进行了广泛的研究，很多优秀的框架和算法在部分视频测试数据上，如宣传片、广告、动画、电影等类型的视频，也取得了良好的效果，然而视频关键帧提取算法的设计与实现仍然是一个非常具有挑战性的问题，其中主要的原因如下：（1）视频的种类繁多，不同类型的视频在内容和结构上具有较大的差异，如宣传片、广告、动画、电影类视频属于结构化的视频类型，该类视频拥有着明显的剪辑痕迹，如镜头突变、渐变等，针对该类视频进行关键帧提取时主要是通过镜头的检测和分割算法将原始视频分割成若干个不同的镜头，然后从各个镜头中提取视频的关键帧。然而某些用户自主拍摄的视频，不同于新闻、体育这类结构化的视频，它们由不同的用户拍摄，而每一个用户的摄影习惯及方式不同，导致此类视频的内容及结构千差万别，且该类视频通常没有明显的剪辑痕迹，视频的内容主要集中于局部物体及摄像机的运动，因而基于镜头检测与分割的视频关键帧提取算法在该类视频上通常不能够取得较好的效果。由于视频数据的多样性，导致视频的关键帧提取算法没有一个通用的适用于所有视频类型的解决方案，因此，在设计和实现视频关键帧提取算法时，通常需要针对具体视频的类型来设计不同的算法。（2）在评价视频关键帧提取算法的效果时，即算法所提取的关键帧是否能够满足用户的需求，不同的算法通常采用不同的评价标准，如Ciocca,G等使用保真度、压缩率^[7]等指标来评价提取效果的优劣，而VT Chasanis等则将自动提取的结果与人工提取的结果进行对比^[8]，利用精确度、召回率^[8]等指标来衡量算法的提取质量，导致算法评价标准具有差异性的主要原因是关键帧质量好坏的评价通常具有主观性，对于同一段视频，不同的人往往会选择不同的关键帧序列，因此，在评价算法自动提取结果时需要将主观因素考虑在内。

基于上述背景，在本文中我们设计并实现了基于滑动窗口、图像全局特征Gist和局部特征点检测算法SURF的视频关键帧提取算法来解决针对拥有剪辑痕迹和镜头转换视频对象的基于关键帧的视频摘要问题。在本文的算法中，原始视频首先被分解为若干幅静态的图片，然后对每一幅视频帧画面进行特征提取，本文中我们使用Gist^[9]来构建视频帧画面的全局场景信息，该特征由A.Oliva等提出，并被应用于图像识别与分类，Chikkerur等使用该特征进行视频镜头分割^[10]，Cong Y等则将该特征与稀疏字典学习算法^[11]结合进行视频关键帧提取。在为视频帧画面提取Gist特征后，我们利用SURF^[12]特征点检测算法为每一幅视频帧画面提取局部特征点集合，该算法由Herbert Bay等提出，在图像特征点检测方面得到了广泛应用，J. Baber等将SURF特征点检测与图像信息熵结合进行视频镜头分割^[13]，取得了良好效果。在完成视频帧画面的特征提取后，我们利用本文所设计的基于滑动窗口的视频镜头分割和合并算法将原始视频划分为若干镜头序列，并从每一个镜头中提取最具代表性的帧作为关键帧。最后我们对算法自动提取的结果进行了主观和客观上的评价。

1.2 国内外研究现状

基于关键帧的视频摘要指的是选取原始视频中最具代表性的视频帧画面来概括和展现原始视频的主要内容，其最大的挑战在于如何选取尽可能少的关键帧来最大程度上的展示原始视频的主要内容。最简单最直接的关键帧提取算法是对原始视频进行均匀采样，即对原始视频在时域范围内进行均匀等分，然后从得到的视频片段中随机抽取若干帧作为关键帧^[6]。基于采样的关键帧提取算法的最大优点在于算法简单高效，时空复杂度低，然而通过该算法得到的关键帧的质量与采样间隔紧密相关，当采样间隔过大时，算法会遗漏一些短小但拥有丰富语义的视频片段，反之，随着采样间隔的减小，算法会提取大量冗余的关键帧序列。由于视频数据的多样性，同时随着用户对于所提取的关键帧质量的要求日渐提高，近来年国内外涌现了大量不同形式的视频关键帧提取算法。

经典的经典视频关键帧提取算法可以划分为两大类：基于视频镜头分割的关键帧提取算法和基于视频帧聚类的关键帧提取算法。

在第一类算法中^{[14][15][16][17][18]}，视频关键帧提取通常是基于镜头的检测与分割算法，当原始视频被分割成若干镜头后，再从每一个镜头中提取最具代表性的视频帧作为其关键帧。该类算法在结构化视频上具有广泛的适用性，这主要是因为其处理的视频类型通常有着明显的剪辑痕迹，如突变、渐变和溶变^[19]等。然而该类算法在非结构化视频以及只有一个镜头的视频上的提取效果不是很理想。

对于第二类算法，聚类方法^{[20][21][22][23][24]}被频繁的应用于视频关键帧的提取，原始视频中的帧画面被聚集成多个类簇，而距离每个类簇中心最近的帧将被选取为关键帧。典型的K-MEANS算法聚类过程描述如下^[25]：（1）在算法初始阶段，从原始视频帧序列中随机选取k帧作为初始聚类中心；（2）根据每个聚类对象的均值，即类簇中心，计算原始视频中的每一帧与各个中心的距离，并根据最小距离将其划分到某一个类簇中；（3）重新计算每一个发生变化，即有新的帧画面加入的类簇的均值；（4）计算标准测度函数，当满足收敛条件时，如每个类簇中心间的距离满足预先设定的阈值等，算法终止，否则回到步骤（2）继续下一轮的迭代。在上述聚类算法中，在算法初始化阶段我们需要提前设定类簇的个数，即k值，而该数目将直接影响到所提取视频关键帧的数量和质量。除此之外，通常的聚类算法是基于反复迭代的计算方式，因而得到最优结果往往需要耗费较多的时间。

除了上述两类经典的视频关键帧提取算法以外，近年来涌现出了许多其他不同类型的算法。Tiecheng Liu等将视频关键帧提取过程被规范为视频的时域分割问题，原始视频的帧序列被表示为一系列的特征向量，后续的关键帧提取算法主要基于最小二叉堆的贪心策略^[26]，其基本思想如下：首先定义一个关键帧集合，算法初始化时原始视频中的所有帧都被看做关键帧，将其添加到关键帧集合中；然后，每一步，对所有关键帧计算这样一个属性值：如果从当前关键帧集合中删去该帧，将它变为非关键帧，将会使得VSE（Video Sampling Error）增大的程度，同时删除该属性值最小的帧；接着，计算被删除的关键帧与在当前关键帧集合中与其前后相邻的关键帧之间的内容信息差异，并将其归属到与其内容差异最小的关键帧所代表的帧段落中。如此循环，直到关键帧集合中剩余的关键帧数量等于用户的要求，算法停止。该算法的平均时间复杂度接近于O(nlogn)。该文所提出的关键帧提取算法具有良好的时间和空间复杂性，同时其关键帧的提取和视频镜头的划分同时进行，因此具有较高的效率。但是该算法提取关键帧时仅考虑了关键帧序列与原始视频之间的内容信息差异，没有考虑选取关键帧时的其他原则，如关键帧画面的清晰度、关键帧中运动的复杂性、关键帧的选取是否符合用户的真实意图等，因此所选取的关键帧可能不是很符合用户的要求和意图。

VT Chasanis等利用统计学上的单峰性检测来判断视频帧集合内所有的帧序列在画面内容上是否具有一致性和均匀性，如果是则称视频帧集合为单峰窗口，否则称为多峰窗口^[8]。由于多峰窗口内的视频帧一般情况下属于镜头的切换画面，因此在提取关键帧时可以仅考虑单峰窗口。当视频镜头内的所有单峰窗口检测完毕后，就从每一个单峰窗口内提取一帧作为该窗口的关键帧。在该文中单峰性检测使用的是Dip-dist准则^[27]，该准则的基本思想是如果一个集合内的所有数据的概率密度分布具有单峰性，那么该数据集合内的数据就具有一致性和均匀性。具体来说，数据集合中的每一个数据称为一个观察者（viewer），当该观察者和其他数据间的距离分布具有单峰性时，该观察者（从其自身的角度）就认为该数据集合具有单峰性。当集合内认为该集合具有单峰性的观察者数量超过一定阈值时，那么该数据集合就被判定为具有单峰性。在进行关键帧提取时，该文的算法维护一个大小为w的窗口，该窗口包含源视频中的一系列的连续视频帧序列，初始时窗口大小w=1，即此时仅包含镜头的第一帧画面。随着算法的运行，窗口大小随之增大，每当一帧画面加入该窗口时，就使用单峰性检测来判断该窗口是否为单峰窗口，如果窗口是单峰窗口则为当前帧赋上一个标志值0，否则为其赋值1。反复如此，直到镜头内的所有帧处理完毕。然后，将所有标志值为0的帧序列的序列号保存下来，就可以得到镜头中所有的单峰窗口的帧序列的范围，对于窗口大小小于5的单峰窗口该算法不予考虑。在得到所有单峰窗口后，从每一个单峰窗口中提取具有最小平均差异值的视频帧作为该窗口的关键帧，从而可得到原始视频的关键帧序列。

Z.Rasheed等利用基于颜色直方图的镜头分割算法^[28]对原始视频进行划分，在得到一系列的视频镜头后，通过关键帧提取算法为每一个镜头选取若干候选关键帧，这些候选关键帧在视觉内容上代表其所对应的视频镜头的主要内容。该文使用的候选关键帧提取算法描述如下：假设当前视频镜头S的起始帧号和结束帧号分别为a和b，其候选关键帧集合为K，则（1）选取镜头的中间帧作为当前镜头的第一帧候选关键帧，并将其添加到集合K中；（2）对于当前镜头的其他任意帧r，如果其视觉内容与当前候选关键帧集合K中的任意关键帧k满足：

（1.1）

其中，Th为最小帧间相似度阈值，取值范围一般为[0.8,0.9]，为任意视频帧间的颜色直方图相似度。如果上述条件满足，则将其添加到集合K中，重复该步骤直到遍历完当前镜头中的所有帧。在得到所有视频镜头的候选关键帧集合后，以镜头为单位，利用Normalized Cut^[29]算法对镜头进行聚类，从而得到一系列的场景，最后从场景中提取最终的视频关键帧序列。在对镜头进行聚类时，首先需要计算镜头间的相似度，对于任意镜头i和j，其相似度计算公式：