最大边界重要和覆盖的视频摘要方法*

冀 中，马亚茹，何宇清

天津大学 电气自动化与信息工程学院，天津 300072

1 引言

近年来，网络视频的数量急速增长，使得用户很难短时间内获取想要的内容，降低了浏览的效率。为此，人们迫切需要一种能够高效浏览和理解视频内容的技术，从而能够更加有效地获取想要的信息。视频摘要由一组静止的关键帧图像序列或者视频片段组成，并以一种简洁的方式将视频的主要内容呈现出来，是一种有效的浏览、管理视频的技术，广泛应用在视频存档、搜索引擎、交互浏览等领域[1-3]。

视频摘要主要有两种形式：静态摘要和动态摘要。静态视频摘要通过一系列的关键帧组成相应的语义单元，概括表示视频的内容，表达形式直观简洁。动态视频摘要则是由视频小片段组成，保持了视频内容随时间变化的固有特征，易于用户的理解[4]。本文采用静态摘要呈现形式。

视频摘要的优劣主要通过最小信息冗余、重要信息优先和最大信息覆盖3个标准来判断。其中，最小信息冗余指尽可能地降低视频摘要中的冗余信息，即摘要长度要尽可能短；重要信息优先指尽量将视频的重要内容优先挑选到摘要中；最大信息覆盖指提取的关键帧能够尽可能覆盖视频的主要内容。

目前的方法主要有基于聚类的方法[5-6]、帧间最小相似度的方法[7-8]以及最小重构误差的方法[9-10]等。其中，基于聚类的方法将视频帧看作特征空间中的数据点，通过选取聚类中心作为关键帧形成摘要。例如，文献[5,11]分别提出利用k均值和基于图模型的聚类算法实现视频摘要。聚类方法生成的摘要可覆盖视频的所有内容，容易满足最大信息覆盖这一标准，这对于含有少量噪音信息的视频来说具有较好的效果。但对于那些含有大量噪音信息的视频，聚类方法却无法判断出重要信息，使提取出来的摘要含有噪音信息。另外，由于语义鸿沟的存在，要准确地实现有意义的聚类也较为困难。

帧间最小相似度的方法目的是使关键帧之间的相似度最小，其代表方法之一是序列决定点过程（sequential determinal point process，seqDPP）[7]。该类方法能够生成低冗余度、最大覆盖信息的视频摘要。近年来，最小重构误差的思想也被用于视频摘要领域[9-10]，其思想是使得原始视频帧与关键帧的重构误差最小，从而迭代选择关键帧构成视频摘要。这类方法考虑了摘要的冗余性和最大信息覆盖标准，但忽略了重要性优先标准。上述帧间最小相似度方法和最小重构误差方法认为视频内容之间的相似度是影响视频摘要的关键因素，忽略了视频内容的重要性优先标准，这对于含有少量噪音信息的视频来说是有效的，但是现在视频内容越来越复杂，仅仅考虑这两个标准提取摘要达不到理想的效果。

另外，最近的研究开始引入一些高层信息，如用户偏好、重要事件、网页图像等信息，试图从这些角度获取视频的语义信息以弥补语义鸿沟问题[3,12-13]。例如，Liu等人[14]通过用户点击信息获取用户查询意图，从而判断视频中的重要性信息，这类方法旨在查找视频的重要内容生成动态摘要。虽然能达到一定的效果，但是对于静态摘要而言因为更加看重冗余性问题，所以这种方法不能达到较好效果。

然而，以上方法通常针对视频集的特点，根据不同的目标，从不同的角度将视频摘要过程看作不同的数学模型。而由于模型的限制，设计的摘要框架很少能够同时满足本文所述摘要标准，使得摘要的效果并未达到预期效果。针对此问题，本文设计了一种同时满足所需3个标准的摘要框架。受最大边界相关算法（maximal marginal relevance，MMR）启发，本文提出最大边界重要和覆盖（maximal marginal importance and coverage，MMIC）框架，同时优化冗余性、重要性和覆盖率3个指标。特别地，利用基于KRNN（K-regular nearest neighbor）图的流形排序算法[15]设计了一种重要性计算方法，还提出了摘要覆盖率标准（summarization coverage criterion，SCC）自动生成合适长度的视频摘要。在主流的Open Video Project和YouTube数据集上进行了大量主观和客观实验，验证了MMIC算法的有效性和先进性。本文的贡献主要为以下两点：

（1）提出MMIC视频摘要框架，利用MMIC算法同时优化摘要的重要优先性、最大覆盖率和最小冗余性。

（2）提出利用K-RNN图的流形排序算法设计一种计算视频帧的重要性分数的方法。

2 最大边距相关算法

最大边距相关是一种平衡相关性和冗余性算法，在文本摘要领域中有着重要的应用[16]。该算法在选择摘要句子时，使得选择的句子既与文档主题的相关性最高，又使该句与已选的文摘句的冗余性最小。因此保证了摘要句子既与主题相关，又含有较少的冗余信息。

假设给定一个集合D，并想获得一个与查询q相关的子集Dk，且MMR算法在给定的条件下，根据式（1）所示标准，利用贪婪方式选择下一个元素构成子集，以此迭代获得子集Dk。

其中，sim1(dj,q)表示元素dj与查询q的相似性；sim1(dj,di)表示已选元素di∈Dj-1与待选元素dj∈DDj-1的相似性；λ用于平衡相关性和冗余性。

3 MMIC算法

理想的视频摘要需满足最大覆盖率、重要优先性和最小冗余性等准则，且受文本摘要领域中的最大边界相关算法的启发，本文提出同时优化上述3个目标的MMIC算法。该算法平衡了摘要的重要性、覆盖率和冗余性标准。与文本摘要中仅依赖一个静态的查询不同的是，视频摘要中不需要静态查询，依赖逐步迭代选择关键帧构成视频摘要。在每次迭代时，希望选择的关键帧同时满足重要性最大，其构成的关键帧集的覆盖率最大，同时与已选的关键帧集的冗余性最小。根据这种思想本文设计了如下目标函数：

其中，Sk表示第k次迭代后选择的关键帧集；V表示视频帧集；C=VSk表示视频帧集V与关键帧集Sk的差集；I(xi)表示视频帧xi的重要性大小；Cov((Sk⋃xi),V)表示候选关键帧集{Sk⋃xi}（这里候选关键帧集指的是已选关键帧集与任意视频帧xi∈C的并集）与视频帧集V的覆盖率；重要性和覆盖率计算模型将在下一部分展开介绍；sim(xi,gj)表示视频帧xi与关键帧gj的余弦相似性大小，用以控制摘要冗余性大小；λ表示前后两项的平衡系数。

下面将分别描述重要性和覆盖率摘要标准，并对MMIC的关键帧选择算法进行详细介绍。

3.1 视频帧重要性计算模型

（1）构建视频的K-RNN相似图

首先，采用每秒2帧等间隔采样的方法提取候选帧集，然后提取视觉特征。由于颜色特征提取简单，且对相机拍摄位置的变化有较强的鲁棒性，常用在视频摘要领域。为此本文采用8×8×4量化的HSV颜色直方图表征视觉内容。

然后，采用无向带权重的K-RNN相似图[15]G=(V,E)来描述视频帧之间的关系。顶点集V={x1,x2,…,xn}表示视频帧集，顶点xi是视频V中的第i帧。E⊂V×V表示边集，若顶点xi和顶点xj之间有连接边，则根据高斯相似性计算连接权重wij(i≠j)。在K-RNN图中，每个顶点的度是相对它与其他顶点的位置而定的。例如，如果一个顶点与其他所有点距离较远的话，则这个点是孤立的点，因此需要最小化与这个顶点相连接的边的权重和。反之，则该顶点具有较高的顶点度，这些点应该以较高的概率分为一类。根据此思想利用贪婪算法构建视频的K-RNN图。

（2）基于K-RNN图的流形排序的重要性计算

通常视频中重复出现的帧是比较重要的内容。据此本文设计了一种基于流形排序的视频帧重要性计算方法。在给定查询的情况下，流形排序将数据点按照它们在数据流形结构中与查询的相关性进行排序[17]。本文利用这一特性通过将每个视频帧看作查询，其余的数据点作为待查询的帧来获得与查询帧相关性大于一定阈值的待查询帧数，帧数越多说明该查询帧在此视频中占据的分量越大，该帧越重要。本文首先将任意视频帧xi看作查询帧，其余帧看作待排序的帧。然后根据流形排序计算待排序的帧集的排序分数，并设置一定的阈值判断分数大于该阈值Th的帧的数量si，则该帧的重要性分数I(xi)的具体计算过程如下：

这里，n指的是视频帧集的数量。

3.2 信息覆盖计算模型

摘要的信息覆盖率值反映了摘要涵盖原视频内容的大小程度，因此摘要的覆盖率越大表明摘要包含的视频的信息越多，摘要质量越高。为了使所选的关键帧构成的摘要与视频之间的覆盖率最大，需在每次迭代时保证选择的关键帧构成的关键集的覆盖率最大，为此需要计算候选关键帧集{Sk⋃xi}与视频V之间的覆盖率。本文通过计算两者之间的相似性，来衡量其覆盖率，且认为两者之间距离越小候选关键帧集{Sk⋃xi}的覆盖率越大，其计算公式如下所示：

其中，Cov(Sk⋃xi,V)表示候选关键帧集{Sk⋃xi}与视频集V的相似性；d(xi,g)表示视频帧xi与关键帧g之间的欧式距离。

3.3 基于MMIC的优化算法

在满足上述标准后，本文将根据式（1）迭代选择关键帧构成视频摘要。其迭代过程如下：

其中，S1表示初始摘要集；Sk+1表示第k+1次迭代生成的关键帧集。

接下来设定迭代终止条件。常用的方法是为摘要设定一定长度，但是在对视频无先验信息的情况下，为摘要设定一个合适长度较为困难。为此，本文提出了一个摘要覆盖率标准（summarization coverage criterion，SCC)自动选取合适的摘要长度。当SCC达到阈值TSCC时（这里TSCC=0.85），迭代终止。通过设定不同的阈值可以获得不同的摘要长度，能够适应于不同类型的视频。迭代过程中SCC的计算如下：

图1给出了MMIC算法的流程图。生成整个视频摘要的过程如下所示。

Fig.1 Flow chart of proposed MMIC algorithm图1 所提MMIC算法的流程图

算法MMIC算法

输入：视频帧集V={x1,x2,…,xn}。

输出：视频摘要S。

1.根据式（5）选择关键帧集的第一帧构成S1；

2.根据式（6）迭代选择摘要中的第k+1个关键帧构成Sk+1；

3.迭代步骤2直到摘要的覆盖率SCCk+1达到一定的阈值TSCC，算法结束。

4 实验结果与分析

4.1 数据集与评价方法

本文在YouTube和Open Video Project[5]数据集上进行实验。YouTube数据集是自行从YouTube视频分享网站下载的20个视频，这些视频时长限制为1～4分钟，且该数据集包含的主题主要有电影片段、监控视频、BBC新闻、体育比赛4个主题，没有人工标注。Open Video Project数据集包含50个视频，且每个视频时长限制为1～4分钟。该数据集包含的主题主要有记录片、科教片、短片、历史片、课堂等主题，涵盖主题范围较广，且该数据集提供了人工视频摘要，可用于摘要结果的客观评价。

通常采用客观和主观评价两种方法评价视频摘要的优劣。所用的客观评价方法是通过比较所提方法生成的视频摘要和用户摘要中的关键帧之间的距离所得[9]。具体地，首先计算自动视频摘要和用户摘要中的帧之间的欧式距离，然后将其与预先设定的阈值（本文设定该阈值为0.5）相比较来决定两帧是否匹配。如果两帧匹配，则在下一次比较过程中删除这两帧，并进行下一次比较。最后用准确率(P)、召回率(R)和F-score(F)3个标准来综合评价摘要。其具体的计算方式如下所示：

其中，nAS、nmAS和nUS分别表示自动视频摘要中的关键帧数量、匹配的关键帧数量和用户摘要中的关键帧数量。而且为了降低用户的主观性，本文利用多个用户摘要进行比较，并对这3个评价标准取平均从而评价摘要。

对于主观评价，邀请用户观看完自动视频摘要后，从重要度、覆盖率和多样性三方面考虑给出一个评价。评价等级分为Good、Acceptable、Bad共3个等级。其中Bad表示所提算法生成的摘要的效果糟糕，Good表示生成的摘要结果比较理想。

4.2 结果分析

4.2.1 Open Video Project数据集

（1）客观评价

为了验证本文MMIC算法的有效性，对比了DT（Delaunay triangulation）[18]、OV（open video storyboards）[19]、KMC（K-means methods on color feature）[6]、KMCE（K-means methods on color and edge features）[6]、k-means和 MSR（minimum sparse reconstruction）[9]等6种方法，如表1所示。为了保持一致性，在所有这些方法中除KMCE外均使用颜色特征作为视频帧的视觉表征。

①DT[18]算法：该算法首先构建德劳内三角形图，通过移除类间边来获得聚类结果,并在每类中选取一帧作为关键帧。

②OV[19]算法：和聚类相似，曲线简化的方法也是将视频帧看成特征空间中的点，不过它进一步将视频看作这些点按时间顺序连成的曲线，然后通过曲线分割的方法实现摘要算法。

③KMC[6]算法：该算法提出了一种使用动态Delaunay图聚类的迭代边缘修剪策略，将结构条件作为图顶点的导数的下限，提高了摘要的质量，并且利用了信息理论的预采样获得了信息量大的帧。

④KMCE[6]算法：该算法与KMC算法的差别在于所用的特征不同，KMCE所用的特征是颜色和边缘特征，而KMC算法仅仅利用颜色特征。

⑤k-means算法：该算法首先将视频分割成帧并对其进行预采样生成候选关键帧，然后利用k-means聚类算法实现帧的聚类，最后在每类中选择与聚类中心最近的帧作为关键帧构成视频摘要。

⑥MSR[9]算法：该模型将稀疏编码算法应用到视频摘要任务中。它将摘要集和视频帧集分别看作基向量组（也称为字典）和候选基向量组，并通过稀疏编码学习一组基向量来重构原来的视频主题空间。该算法首先随机选择一帧作为关键帧来初始化摘要集，而下一关键帧则按照最大减少摘要集和原来的视频帧集之间的重构误差的原则进行选取，并迭代直至满足一定的条件。

Table 1 Precision(P),recall(R),F-value(F)and average length(L)of different algorithms on Open Video Project表1 Open Video Project上不同算法的精度(P)、召回率(R)、F-值(F)和摘要平均长度(L)结果对比

从表1中可以看出，在准确率方面MMIC算法性能相对较好，分别比k-means、OV、DT、MSR高约10%、3%、3%、20%，但分别比KMC和KMCE低了约3%和5%。在召回率方面MMIC算法优于大部分对比算法，分别比k-means、OV、DT、KMC、KMCE高约1%、1%、22%、12%和13%，但比MSR算法低了约7%。在F值方面MMIC算法均高于其他算法，分别比k-means、OV、DT、KMC、KMCE和MSR高约6%、2%、14%、4%、4%和11%。

根据摘要长度比较可以看出，MMIC算法的摘要长度高于KMC和KMCE，摘要长度影响了算法的准确率，因此准确率低于这两种算法。但是从召回率的角度分析，MMIC算法高于k-means、OV、DT、KMC、KMCE算法，但略低于MSR算法，这是因为MSR算法的摘要长度高于所提MMIC算法，所以匹配的帧数略大于MMIC算法。总之MMIC算法的摘要中匹配帧数大于多数对比算法的匹配帧数，效果明显高于其他算法。从F值也可以看出，MMIC算法的F值明显高于其他算法。综上，所提MMIC算法的性能在Open Video Project数据集上表现较好。

为了直观对比MMIC与其他算法，从50个视频摘要中抽样出一个可视化摘要结果，如图2所示，每一行呈现一种摘要算法的结果。从图2可以直接看出所提MMIC算法相比较于其他算法，能够较好地去除冗余性，且选择的关键帧能够较好地代表原来的视频内容，性能优于其他算法。

Fig.2 Results of MMIC and baselines for video“ANew Horizon”(the red box is a redundant video frame)图2 MMIC与对比算法对视频“ANew Horizon”的摘要结果(红色框内为冗余的视频帧)

（2）主观评价

为了进一步比较MMIC算法的性能，邀请了3个男生和3个女生共6个用户参与主观评价，要求这些用户观看视频后对该算法所提的摘要结果进行评价。评价等级分为Good、Acceptable、Bad共3个等级，用户根据摘要满足重要性、覆盖率和多样性标准的程度综合给出摘要的主观评价。具体的评价结果如表2所示。

Table 2 Subjective evaluation of MMIC algorithm on Open Video Project表2 OpenVideo Project上MMIC算法的主观评价结果

从表2中可以看出MMIC算法的主观评价整体上较好。50个视频中，Good评价等级的视频约有40个，占整个数据集的80%，Acceptable评价等级的视频约有8个，占整个数据集的约16%，而Bad评价等级的视频有2个，占整个数据集的约4%。总体来说，MMIC算法生成的摘要结果能够较好地代表视频的主要内容。

另外，为了进一步证明MMIC算法优于其他对比算法，本文要求参与评价的用户对这些算法的摘要结果进行主观评价，如表3所示。可以看出6个用户分别对这6种算法的投票结果为：MMIC算法的评价等级为Good的视频个数平均为40（视频总数为50），高于其他对比算法；而评价为Bad的视频平均为2个，远小于其他对比算法。因此所提MMIC算法效果较以往摘要方法有了明显的改善。

Table 3 Average results of subjective evaluation of different algorithms on Open Video Project表3 OpenVideo Project上不同算法的主观评价的平均结果

4.2.2 YouTube数据集

YouTube数据集是从YouTube上下载的视频集，没有统一可用的用户摘要标准。因此本文只对该数据集的结果进行主观评价。按照Open Video Project数据集的主观评价标准对YouTube数据集上的摘要结果进行主观评价，如表4所示。

Table 4 Subjective evaluation of MMIC algorithm onYouTube dataset表4 YouTube数据集上MMIC算法的主观评价结果

可以看出，20个视频中约有16个视频的评价等级为Good，约3个视频的评价等级为Acceptable，而仅仅约有1个视频的评价等级为Bad。因此可以进一步证明所提MMIC算法生成的摘要结果能够较好地代表视频的主要内容。

另外，本文还要求用户在YouTube数据集上对其他对比算法进行主观评价，如表5所示。可以看出，所提MMIC算法的评价等级为Good的视频个数约为16（视频总数为20），优于其他算法；而评价等级为Bad的视频个数约为1，均低于其他算法。这表明MMIC算法在YouTube数据集取得了较好的效果，更加证明了该算法的鲁棒性。

Table 5 Subjective evaluation of MMIC algorithm onYouTube dataset表5 YouTube上不同算法的主观评价的平均结果

5 结束语

本文在MMR算法的启发下提出了一种融合最小冗余性、最大重要性和最大覆盖率标准的MMIC摘要算法，并提出了利用基于K-RNN图的流形排序算法计算视频帧的重要性。在迭代选择关键帧时，为了同时满足上述提及的3个摘要标准，利用MMIC算法来实现关键帧的选择，从而构建视频摘要。并在Open Video Project和YouTube数据集进行了实验，验证了所提算法的有效性和先进性。