曾华+王耀民

摘要：图片的互信息量特征包含颜色和空间信息，能很好地反映视频的帧间相似度，但互信息量计算量大，用于视频关键帧提取时间复杂度大。针对动画视频大量存在背景固定镜头，提出一种改进的互信息量关键帧提取算法。实验结果表明，算法在基本保持与互信息量特征提取结果相同的情况下，能有效降低关键帧提取的时间复杂度。

关键词：基于内容；动画视频；关键帧提取；互信息量； 时间复杂度

中图分类号：TP37 文献标识码：A 文章编号：1009-3044（2016）13-0220-03

Abstract： The mutual information feature contains the image color and spatial information， can well reflect the similarity between video frames， but mutual information calculation for content-based video key frame extraction is computation-intensive and time-consuming.. According to a fixed background animation video camera， this paper proposes an improved mutual information algorithm to extract key frames. The experimental results show that the algorithm can effectively reduce the time complexity of key frame extraction in the same condition， which is the same as the feature extraction of mutual information.

Key words： content-based； animation video； key frame extraction； mutual information； Time complexity

3 阶段关键帧提取

基于内容的视频检测技术中，视频包含大量的视频帧，以一个90分钟电影为例，假设每秒包含25帧，则视频总共由135000帧组成，所以处理时间长是一个比较突出的问题。文章提出一种先利用非均匀分块法将视频帧进行非均匀分块，将目标与背景进行分离，再利用视频背景与内容相结合的两阶段关键帧提取方法动画视频关键帧。

3.1 图像非均匀分块

传统视频关键帧提取，可以考虑对视频人物对象提取后根据视频人物内容进行关键帧提取。动画视频在制作上与传统的视频有很大的不同，导致动画视频有着自身明显的特点。例如，在动画视频中，目标物体的运动速率比一般的视频要快，而且为了突出效果，视频一般比较注重动作、表情的夸张表现。这些夸张的手法使得目标提取算法效果较差，可行性不高。

传统的视频多数是录制编辑而成的，而动画视频往往是先设计出动画人物的动作，在研究过程中发现相当数量的动画视频镜头的背景是相对固定的很多包含复杂动作的镜头其背景相对来说保持很高的相似性，甚至是一个固定的静态图像背景。实验对目前主流的迪士尼动画、日本动画、国产动画三类动画视频进行镜头类型统计。

从统计表可以看到，选取的动画视频中有超过半数的镜头是以静态图片为背景，这是动画视频的一个重要特征。根据动画视频这一特点文章提出相对简单可行的动画人物与背景分离方法，即将视频帧进行非均匀图像分块，从而图像帧分成目标对象区域与背景区域。图像的分块方法如下图所示：

从图2可以看到，文章给出的图像分块法可以有效将视频帧人物对象和背景进行分离，且方法简单易实现。

3.2 第一阶段关键帧提取

针对动画视频大量存在静态背景的特点，提出先对视频帧进行图像分块，然后通过计算背景区域的特征距离，对同一场景内大量高度相似的视频帧进行筛选。

第一阶段的关键帧提取主要是提取备选关键帧，算法计算复杂度是主要考量因素。上面提到的图像非均匀分块方法将背景分成三个不同的区域，背景区域2和背景区域4容易受台标、视频字幕或者其他因素的影响，实验选取背景区域3为代表进行特征距离计算。

特征距离的选取，第一阶段候选关键帧提取选取像素差作为特征距离，简单易实现。实验研究发现R、G、B三个分量像素差高度相似，在实验中计算帧间像素差时以R分量进行计算。下面是R分量的像素特征距离与处理后的帧间互信息量特征距离的对比示意图。

从图3可以看到，背景特征距离中大多数镜头分界明显，为了避免丢失关键信息，阈值设置应相对严格。通过设置严格阈值进行第一阶段的备选关键帧提取可以过滤大量高度相似的视频帧，降低视频帧数量。

第一阶段备选关键帧提取算法描述：

第一阶段算法步骤完成，得到视频候选关键帧序列。

3.3 基于互信息量特征的关键帧二次提取

第一阶段对原始视频帧进行筛选得到候选关键帧序列后，需要在候选关键帧集合进行第二阶段关键帧提取，得到最后的关键帧。根据概率关系式，图像互信息量的计算可演化成：

互信息量作为图像相似度，能较好地反映图像的相关度，同时对光照变化不敏感。

参考3.2中的算法步骤，候选关键帧集合的第一帧作为关键帧，并作为当前关键帧，选取集合下一帧，根据公式（5）计算与当前关键帧的互信息量，如果小于设定的阈值，说明帧间差异大，就将其加入最终关键帧集合，并更新当前关键帧；否则继续提取集合中其他关键帧进行检测，直到候选关键帧中的帧处理完毕，得到最终的关键帧集合。

4 实验结果分析

文章提出的算法主要目的是提高互信息为帧间特征的视频关键帧提取算法时间效率。实验选取5个不同类型动画视频实验对象，其中国内动画视频1个，日本动画视频1个，美国迪士尼动画视频3个，视频片断平均帧数超过2000帧。其中算法1是互信息量关键帧提取算法，算法2为文章提出的改进算法，关键帧提取结果如下：

实验数据表明，文章提出的算法对上述视频关键帧提取结果与单一使用互信息量为特征距离的提取结果镜头覆盖率稍差，但程序的时间复杂度大大降低，消耗的时间仅为算法1的18.61%。同时实验结果表明，提出的算法关键帧提取冗除较少，下图是其中《蜡笔小新》视频片断中的一个镜头提取关键帧结果对比：

5 结束语

文章针对互信息量计算量大的问题和动画视频大量存在镜头固定的特点，提出了一种先对视频帧进行简单可行的图像非均匀分块方法将目标与背景分离，选取计算复杂度低而且严格的特征描述对视频帧进行备选关键帧提取，最后利用互信息量进行关键帧二次提取。实验结果表明算法在基本保证与传统互信息量的提取相同的镜头覆盖率下，大大降低了时间复杂度。算法不足之处是对于并非静态背景视频较差，时间复杂度大大提高，是今后需要改进的。

参考文献：

[1] 曾华， 王耀民， 何文广. 动画视频镜头检测方法[J]. 电脑知识与技术， 2012（17）.

[2] 曾华，杨汉辉. 一种两阶段的关键帧提取方法[J].计算机与现代化，2011（6）.

[3] Mai K，Miller J，Zabih R.A robust method for detecting cuts and dissolves in video sequences. [J].Proceedings of ACM Multimedia . 1995

[4] 徐丹. 基于内容的视频检索系统研究[D] . 武汉理工大学， 2006.

[5] 冈萨雷斯. 数字图像处理[M].北京：电子工业出版社， 2005.

[6] 孔娟， 田丽. 基于互信息量的视频关键帧提取算法[J]. 安阳工学院学报，2010年04期

[7] 徐建华.图像处理与分析[M] .北京：科学出版社，1992.

[8] F Maes， A Collignon et al. Multimodality Image Registration by Maximization of Mutual Information[J]. IEEETrans. On Med. Imaging，1997，16（2）：189-198.