基于图像聚类与挖掘的视频摘要方法

陈 宏

（浙江广播电视集团，浙江 杭州 310005）

1 视频摘要的基本概念

视频摘要技术，它的概念类似于文本摘要，即通过计算机自动处理技术，对视频的内容和结构进行分析，并从原视频内容中提取出用户需要的信息，再做进一步处理。如果一个视频摘要能够做到尽量准确和充分，那么就能够让用户在最短时间内获得最关键的信息，极大地提高效率[1-4]。

根据摘要信息表现形式的不同，视频摘要技术可以分为静态图像摘要和动态图像摘要。静态图像摘要，又称关键帧序列，它是从原始视频中提取出最关键、最具代表性的图像集合。动态图像摘要，又称缩略视频，它是由原始视频中提取部分关键视频段，以切变或渐变的方式组合。实际上，这摘要本身也是一个视频段，只不过在时间长度上大大短于原始视频时间。电影预告片便是一种常用的动态图像摘要。

静态图像摘要获取的信息简洁明了，大幅降低了视频分析和检索的复杂难度，但同时由于其缩略幅度太大，往往容易删减掉一些潜在的重要信息。而动态图像摘要包含了音频和动态信息，大大增加了摘要的表现力[5-7]。

2 静态图像摘要的主要形式

静态图像摘要技术主要有以下几种形式：

1）标题（Title）。标题是对视频进行简短描述的一个词或一句话。虽然从严格意义上来讲，它不算是视频摘要的一种，但是它也是用一种简单的方式表现视频的内容。标题的优势就是简单便捷，它的产生十分方便，可以用户直接输入，也可以从语音转录文本或相关信息中抽取。它的存储和呈现也同样十分方便。但是不足之处是它能传达的信息量比较少，文字很难形象地描述多媒体信息，用户看过它之后不能有直观的感受。

2）海报（Poster）。海报又被称为视频代表帧或视频缩略图。它从原始视频中提取出一张或少量几帧图片，再加上视频的一些相关文字信息，比如人物、简短介绍等构成一种静态摘要。海报是目前用的最多的摘要呈现方式，大部分的在线视频网站的视频展现都采用了这种方式。海报与标题相比，提供了视频图片，可以给用户更直观的感受。而且海报的产生也比较简单，只要抽取其中几张图片，辅以一些文字就可以形成。但是它也有不足之处，最主要的就是它抽取的仅是视频中的少量几张静态图片，这些图片仅仅是视频在某些时刻的画面，它们很难表示视频的具体内容和发生的事件。

3）故事板（Storyboard）。故事板是在视频进行镜头切分以及抽取出所有关键帧之后，将这些关键帧按照时间顺序组合成一个列表的静态摘要。故事板给用户提供了视频的大致结构。相比于海报，故事板抽取出来的图片都是关键帧，它包含了更多的视频语义，所有的关键帧构成了视频的大致框架，可以提供给用户较为完整的视频信息。

4）幻灯片（Slide）。幻灯片是将经过抽取出来的几张关键帧形成一张有动画效果的GIF图片的静态摘要。它在镜头切分和关键帧抽取部分和故事板一样，但他们的不同之处在于，故事板是将所有的关键帧呈现为一个列表，而幻灯片是在关键帧中抽取出一部分然后形成一张GIF图片。这种方式的优势是大幅度地减少了需要传输的图片数量，占用的显示空间也只有一张图片大小。这种方式主要应用在视频检索时返回的视频列表的显示，因为这时需要在一个页面中显示尽量多的视频。

3 基于图像聚类与挖掘的视频摘要方法

笔者提出一种基于图像聚类与挖掘的静态摘要方法。它的输入是多视频文档以及它们对应的语音转录文本，输出是一种图片加文本的静态摘要呈现方式，它由具有隐含主题代表性的关键帧和关键词构成[8-9]。生成摘要的过程由3个步骤组成：首先，通过分析视觉内容抽取出一个镜头集合，通过分析文本内容抽取出一个关键词集合；其次，进行复杂图构建并且对抽取出来的镜头和关键词进行聚类；最后，从聚类后的复杂图中挖掘出最有主题代表性的关键帧和关键词。基于图像聚类与挖掘的视频摘要算法框架如图1所示。

3.1 视频内容分析

假定现有一些带有语音转录文本的视频集D={d1,…,dm,…,dM}。为了分析这些给定视频的视觉内容，采用了一种稳健的镜头边界检测算法来将所有视频分割成镜头集合，用U={u1,…,ui,…,uI}来表示，其中ui表示一个镜头，I表示镜头的数目。为了进一步的视觉内容处理，选取了每个镜头的中间那一帧作为关键帧，然后用423维的特征向量来表示它，这个向量包含了6种特征，包括256维的颜色直方图、6维颜色矩、128维颜色一致向量、15维的MSRSAR纹理、10维Tamura纹理的粗糙度和8维Tamura纹理的方向度。

除此之外，为了分析给定视频的文本内容，分2个步骤来从语音转录文本中提取有意义的关键词：1）使用一个语音标注器来标出语音转录文本中的名词；2）使用键词的分数并从中选择出最重要的关键词。

3.2 复杂图构建和聚类

考虑这样一个任务：从视频集D中抽取出了一个镜头集U和关键词集W，现在要找出它们的聚类结构。一般可以采用单边的聚类算法来分别对镜头和关键词进行聚类[5]，也可以采用协同聚类算法来同时对镜头和关键词进行聚类。笔者采用一种复杂图聚类的算法来同时获得镜头聚类和关键词聚类以及它们之间的关系。

首先使用镜头集U和关键词集W来构建一个由镜头节点和关键词节点构成的图。设定用G=(V(1),V(2),E(1,1),E(1,2))来表示这个复杂图，其中V(1)={v(1)1,…,v(1)i,…,v(1)I}表示镜头节点集，v(1)i是V(1)中的第i个节点，对应于U的第ith个镜头。V(2)={v(2)1,…,v(2)j,…,v(2)J}表示关键词节点集，v(2)j是V(2)中的第jth个节点，对应于W的第j个关键词。E(1,1)表示镜头节点之内的同构边，E(1,2)表示镜头节点和关键词节点之间的异构边。用关联矩阵S∈RI×I+表示E(1,1)的权重，用A∈RI×J+来表示E(1,2)的权重。采用余弦相似性来生成矩阵S。也就是说，节点v(1)i和节点v(1)q之间边的权值Si,q可以用如下公式来表示

式中：fe(ui)表示镜头ui的关键帧特征。另外，镜头和关键词之间的共现性用来生成矩阵A。也就是说镜头节点v(1)i和关键词节点v(2)j之间边的权重Ai,j可以用如下公式来表示

注意到单词wj可能在包含镜头ui的视频中出现多次，所以每一次的出现用索引k来表示。定义一个时间相似性的函数simt(t(ui),t(wkj))，其中t(ui)表示镜头ui的中间时间点，t(wkj)表示单词wj第k次出现的中间时间点，它可以用如下公式来表示

式中：simt()函数是一个分段函数，它在t(wkj)落在时间区间t(ui)start和t(ui)end之间时取值为1，这两个时间点分别为镜头ui的起始时间点和结束时间点。而为了补偿镜头和关键词出现时间上的延迟，它的两边按照标准差为σt的高斯滤波函数进行扩散。

然后，用一种聚类算法[6]来获得镜头聚类和关键词聚类以及它们之间的关系。假设已将镜头节点V(1)聚成了K 类CU={cu(1),…,cu(k),…,cu(K)}，将关键词节点V(2)聚成了L类CW={cw1,…,cwl,…,cwL}。用C(1)∈(0,1)I×K表示镜头节点V(1)的聚类成员矩阵，其每个元素C(1)i,k表示第i个镜头节点与第k个聚类的关联权重。用C(2)∈(0,1)J×L表示关键词节点V(2)的聚类成员矩阵，其每个元素C(2)j,l表示第j个词与第l聚类的关联权重。用D∈RK×K表示同类节点聚类间的关联关系，其每个元素Dk,r表示第k个镜头聚类cuk与第r个镜头聚类cur的关联强度。用B∈RK×L表示不同类节点聚类间的关联关系，其每个元素Bk,l表示第k个镜头聚类cuk与第l个关键词聚类的关联强度。

3.3 主题代表性的关键帧与关键词的挖掘

这一步主要是为了从聚类后的复杂图中挖掘出隐含主题的最有代表意义的关键帧和关键词。具体步骤有：

1）定义镜头节点和关键词节点重要性的度量方法。本文采用先前提到的修改版tf-idf公式来计算关键词节点的重要性。而计算镜头节点的重要性时，将同时考虑视觉和相关的文本特征。

2）定义了镜头聚类和关键词聚类信息量的度量方法。与单个视频生成摘要不同，多视频通常包含几个子主题或者子事件，并且每个子主题或子事件可以通过一个主题相关的关键词聚类或者一个事件相关的镜头聚类来呈现[10-11]。因此，计算一个关键词聚类的重要性可以基于如下观察：（1）一个聚类越复杂，那么它就越重要；（2）一个聚类包含的关键词越重要，那么它就越重要。

3）选择隐含主题的最有代表性的关键帧和关键词。由于每个聚类表示了一个隐含的子主题或子事件。因此，笔者提出用2个步骤的选择方法来最大化主题的覆盖度，同时也尽可能的移除冗余：（1）选取那些重要性分数最高的镜头聚类，然后在选取出来的每个聚类中，选择最重要的那个镜头的关键帧作为其代表；（2）选取那些重要性分数最高的关键词聚类，然后在选取出来的每个聚类中，选择最重要的关键词作为其代表。

4 小结

视频摘要是许多视频应用程序的有机组成部分，如视频索引、浏览以及检索。高效智能的视频摘要生成系统能够帮助用户更加快速地处理大量视频。近年来，很多研究机构都积极开展视频摘要新技术的研究，并提出了多种算法和思路。笔者提出了一种基于图像聚类与挖掘的视频摘要方法，在解决视频摘要主题分散性与多模态难点的道路上做了一些探索，如何通过更优的算法来更加准确地表达出整段视频的内容将是未来工作的努力方向。

[1]CHRISTEL M G，HAUPTMANN A G，LIN W H，et al.Exploring the utility of fast-forward surrogates for BBC rushes[EB/OL].[2011-01-20].http：//citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.141.7507＆rep=rep1＆type=pdf.

[2]SHAO J，JIANG D，WANG M，et al.Multi-video summarization using complex graph clustering and mining[J].Journal of Computer Science and Information System，2010，7（1）：85-97.

[3]CHEN B，WANG J，WANG J.A novel video summarization based on mining the story-structure and semantic relations among concept entities[J].IEEE Tran.Multimedia，2009，11（2）：295-312.

[4]王毅，李弼程，彭天强.视频摘要技术[J].信息工程大学学报，2009，10（4）：493-497.

[5]YE Z Y，WU F.A robust fusion algorithm for shot boundary detection[J].Journal of Computer Aided Design and Computer Graphics，2003，15（11）：950-955.

[6]XIA D Y，WU F，ZHANG X，et al.Local and global approaches of affinity propagation clustering for large scale data[J].Journal of Zhejiang University：Science A，2008，9（10）：1373-1381.

[7]程文刚，须德，蒋轶玮，等.一种新的动态视频摘要生成方法[J].电子学报，2005，33（8）：1461-1466.

[8]章毓晋.基于内容的视觉信息检索[M].北京：科学出版社，2003.

[9]顾诤，肖若贵.基于AP聚类和频繁模式挖掘的视频摘要生成方法[J].计算机应用与软件，2010，27（6）：5-7.

[10]余卫宇，曹燕，谢胜利.视频摘要的现状和研究进展[J].计算机应用研究，2008，25（7）：1948-1952.

[11]姚彬，史萍，葛菲，等.监控视频的摘要提取方法研究[J].电视技术，2010，34（4）：106-108.