一种快速动画镜头检测算法
2016-06-30曾华郑胜前何文广
曾华+郑胜前++何文广
摘要：互信息量特征包含颜色和空间信息很好地反映视频帧间相似度。互信息量计算量大，用于视频镜头检测时间复杂度大。针对动画视频大量存在背景固定镜头的情况，提出先运用背景特征进行镜头筛选，再利用互信息量进行最终确认的两阶段的镜头检测方法。实验结果表明，算法在基本保持与互信息量特征提取结果相同的情况下，可有效降低视频镜头检测时间复杂度。
关键词：基于内容；动画视频；镜头检测；互信息量；联合直方图
中图分类号：TP37 文献标识码：A 文章编号：1009-3044（2016）14-0174-03
A Fast Animation Video Shot Detection Algorithm
ZENG Hua， ZHENG Sheng-qian，HE Wen-guang
（School of Information Engineering， Guangdong Medical College， Dongguan 523808，China）
Abstract： The color and spatial information of mutual information can reflect the similarity between video frames. The feature of mutual information can be used in video shot detection， but there is a large amount of computation. There is a large amount of background fixed scenes in the animation video， the paper proposes to use the background feature to screen the shot， and then use the mutual information to confirm the shot detection method. Experimental results show that the algorithm can effectively reduce the time complexity of video shot detection in the same condition， which is the same as mutual information feature extraction algorithm.
Key words： content-based； animation video； shot detection； mutual information； co-histogram
随着数字多媒体技术与计算机网络技术快速发展，移动设备的不断更新，大量的视频信息已广泛地应用于各个领域，数字多媒体与网络技术快速发展，互联网线上线下的数字视频资源不断地增长，人们所接触的视频也越来越多，面对周围海量的视频信息，如何快速有效地对视频资源进行准确描述，方便用户高效地进行视频检索与浏览，成为了迫切的需求，基于内容的视频检索技术因此正是基于这种需求而出现的。
动画视频可根据其特点分成不同的类型，比如一些全部由现代CG技术制作出来的新的动画类电影；还有一些主要在于强调其寓意，而制作手法简单所以其画面也非常简单；还有一些是非常受欢迎的以美国迪斯尼为主的动画片。其中迪斯尼这一类动画片受欢迎，而且制作出来的动画视频有着其鲜明的特点：题材吸引人，而且制作手法比较大胆夸张，其中以《猫和老鼠》和《米老鼠与唐老鸭》等等为代表。动画视频中往往因含有大量的目标物体快速运动且不规则、表情大胆夸张，其中第三类的动画视频尤其明显，而现有的主要的视频分析处理方法主要都是针对普通的电影电视、体育、新闻等视频的，而正如前面所说，动画视频从其创作到制作整个过程都有着它自身鲜明的特点，而且正因为这些独特的特点，使得现有的视频镜头边界检测算法对动画视频往往不能取得良好效果。
图片互信息量包含了图片间的颜色和空间特征信息，能较好地反映图片间差别，在基于内容的视频检索中作为视频的帧间特征能较好地反映视频内容的变化，但其计算复杂度高。动画存在大量背景相似的镜头，镜头边界只占极小部分，通过背景可以筛选大量非镜头边界的视频帧。文章根据动画视频背景相对固定的特高提出一种快速有效的互信息量镜头切变检测方法。
1 现有基于内容镜头检测技术
自上世纪九十年代基于内容的视频检索研究兴起以来，国内外学者提出了很多视频镜头检测的算法，其中包括了很多传统的经典算法。（1）模版匹配法，是一种最直接的基于两幅视频帧的灰度图对应点像素值差的绝对值的方法。（2）基于直方图的方法，这是一种较为简单的基于统计的方法，方法利用图像的整体特征，因此受镜头和目标运动的影响较小。直方图法通常还可以将视频帧的各个像素的灰度、亮度或颜色均匀分成K等级，再对每个等级统计像素数目构成直方图进行比较。（3）基于分块匹配法，与前面提到的相邻图像上逐点像素比较法不同，基于块匹配的方法先将每一帧图像划分成K块，连续帧之间的相似性通过比较对应的块来进行估计。这种方法主要利用局部特征来抑制图像噪声和摄像机及物体运动干扰。对于像素值较为相似，而场景不同的镜头边界，可能会出现漏判的情况。若块匹配法可以较好地与其他方法相结合，往往可以达到较高的检测率。（4）基于图像边缘信息方法，Ramin Zabih与Justin Mille等人提出了一种基于图像边缘信息的镜头检测方法。
此外不少学者研究运用视频基本运动信息进行镜头检测，同时也有相关压缩域的镜头检测方法研究。
2 非均匀分块方法
视频镜头检测与关键帧提取技术主要包括两个方面，基于文字描述和基于内容两大类。其中基于内容的视频检测技术是针对视频内容进行的检测，可以避免因文字描述不当所导致的检索错误。而由于每个视频为了达到流畅视频效果，往往要求每秒至少包含25个视频帧，所以包含大量的相似视频帧，这导致基于内容的镜头检测和关键帧提取存在处理时间长的突出问题。文章提出了一种非均匀分块法将视频帧进行非均匀分块，用简单可行的方法先将目标与背景进行分离，再利用视频背景与内容相结合的两阶段镜头检测算法进行镜头检测。
动画视频在制作上与传统的视频有很大的不同，导致动画视频有着自身明显的特点。例如，动画视频中的目标对象的运动速率比传统视频要快，同时动画视频为了突出视觉效果，视频往往更加注重目标动作、表情的夸张表现方法。
动画视频往往是先设计出动画人物的动作，而传统的视频多数是录制编辑而成，研究发现：相当数量的动画视频镜头的背景是相对固定的，很多镜头目标复杂动作，但背景却是相对有较高的相似性，甚至存在大量镜头背景为一个固定的静态图像。实验对目前主流的国内外动画视频进行镜头类型统计，实验通过统计发现：动画视频有超过50%的镜头是以静态图片为背景，说明背景相对固定是动画视频的重要特征。根据动画视频这一特点文章提出一种简单有效的动画人物与背景分离方法，即将视频帧进行非均匀图像分块，将图像帧分成目标区域与背景区域。图像的非均匀分块方法如图1所示：
从上面的示意图可以看出：文章给出的图像分块法可以有效将视频帧人物对象和背景进行分离，且方法简单易实现。
3 第一阶段候选镜头边界检测
第一阶段：候选镜头边界检测。第一阶段针对动画视频大量存在静态背景的特点，提出先对视频帧进行图像分块，然后通过计算背景区域的联合直方图特征距离，对同一场景内大量高度相似的非镜头边界视频帧进行筛选。
3.1 联合直方图特征距离
像素值p在大小为M*N的图像f（x，y）中出现的概率定义为：
[Hf（p）=1MNy=1Mx=1Nδ（f（x，y），p）] （1）
式（1）中，[δ（f，p）]是克罗内克函数：
[δ（f，p）=10if（f=p）if（f≠p）] （2）
如此可见，对于给定的大小为M*N的两幅图像f（x，y）、g（x，y），它们之间对应的像素值对（p，q）联合概率的定义为：
[H（p，q）=1MNy=1Mx=1Nδ（f（x，y），p）?δ（g（x，y），q）] （3）
由式（3）可知，对可能的像素值对（p，q）求其联合概率[H（p，q）]的值，即可以计算出两幅图像f（x，y）和g（x，y）之间的联合直方图。而图像间的联合直方图对称性可以很好的描述两幅图像的相似性：对于相同的两幅图片，它们之间的联合直方图关于对角线严格对称，即对角线上才有取值；而如果两幅图像非常相似，联合直方图相应展现出非常高的对称性；只有当两幅图像存在很大的差别时，计算所得的联合直方图取值区域会变得很大，而且关于对角线对称性差。综上，求两幅图像的联合直方图，通过联合直方图对称性即可判定图像的相似程度。下面是联合直方图对称性定义：
[symmetry=αpH2（p，p）+p，qβH（p，q）H（q，p）αpH2（p，p）+p，qβH2（p，q）] （4）
其中[α]是对角线上的权值，为小于1的常量；[β=（p-q）n]是远离对角线元素的权重， n是整数。在实验中为了可以突出图像间联合直方图差异，上式中 [α]应赋较小值，而β赋较大值。实验给[α]取值1/8，n取值2。
3.2 第一阶段镜头检测方法
第一阶段的候选镜头检测主要通过计算图像分块后的背景区域来获取，帧间特征选取联合直方图。第一阶段候选镜头检测的算法主要步骤描述：
Step1：计算帧间背景区域联合直方图特征距离，得到视频联合直方图帧间差特征向量[D=（d1，d2，…，dN）]，设置N=5，作为用于镜头渐变检测容忍度；
Step2：对于当前视频帧i的帧间特征距离[di]，若[di]>[Thigh]，说明视频帧i可能是候选的镜头切变，转step3；若[Tlow]<[di]<[Thigh]，说明视频帧i可能是候选渐变，转step5；
Step3：闪光干扰检测：计算[Diffi-1，i+1]，若[Diffi-1，i+1]<[Thigh]，判定为误检；否则计算[Diffi-1，i+3]，如果[Diffi-1，i+3]<[Thigh]，判定为误检，否则转step4进行切变判定；
Step4：切变检测：以要检测的帧为中心设定长度为21双侧滑动窗口[W]，若同时候满足以下两个条件：[di=max（W）]，[di>5*avg]，其中[avg]是[W]窗口中除当前帧间特征距离外的特征距离平均值，判定为候选切变。i=i+1，转step2；
Step5：渐变检测：标记当前帧为可能的渐变开始帧，j=i+1，继续向后进行检测，若同时满足[dj] >[Tlow]和[Diffi，j>Diffi，j-1]，则N=N-1； j=j+1，直到N=0或者[Diffi，j
Step6：算法结束，得到第一阶段的候选切变和渐变集合。
4 第二阶段镜头检测
在1995年Viola和Collignon分别独立提出了利用互信息量作为图像之间的相似性测试，随后图像的互信息量相似性测试在应用上取得巨大的成功。对于两幅图像A和B，它们之间的互信息量的定义为：
（8）
其中PA，PB，PAB分别为A， B的概率分布和联合概率分布。从式（5）互信息量定义可知：I（A， B）值越大说明A，B越相似；I（A， B）的值越小说明A，B越不相关。
在两阶段的镜头检测方法中，第二阶段对第一阶段选取的镜头进行二次确认，选取互信息量描述帧间相似性，对第一阶段的切变边界进行窗口为21帧重新互信息量特征，参照3.2中step4进行切变判断；对渐变边界，参照3.2中step5进行渐变判断。
通过对候选镜头重新确认，得到视频最终的镜头边界集合。
5 实验结果分析
针对本文提出的镜头分割方法，我们分别选取了几段动画视频片断进行测试，为了使检测结果更加有普遍性，实验选取了国外动画及国产动画做实验，其中国外动画中人物动作幅度大，一般的特征描述方法所得的镜头分割效果误检率比较高；而片断三和片断四是两个国内动画，其视频内容相对简单，人物动作小，误检率较低，一般算法均可达到较高的查准率。实验中主要和基于像素的镜头检测算法和互信息量的检测算法比较。其中算法1为基于像素的检测算法，算法2为互信息量的检测算法。
实验数据表明，对于实验选取的视频片断，三种算法的查全率相同，互信息量算法和文章提出的算法较基于像素的方法查准率高；运行时间，基于像素检测算法较快，没有加入比较，本文算法是互信息量检测算法的31.25%，在查全率与查准率保持不变的基础上有效地降低了时间复杂度。
6 结束语
针对互信息量计算量大的问题和动画视频大量存在镜头固定的特点，文章提出先对视频帧进行简单可行的图像非均匀分块，将目标与背景分离，先选取计算复杂度相对较低的联合直方图对背景区域进行候选镜头检测，再利用互信息量特征进行最终镜头边界确认。实验结果表明，文章算法较为有效地降低了时间复杂度。
参考文献：
[1] 曾华， 王耀民， 何文广. 动画视频镜头检测方法[J]. 电脑知识与技术， 2012（17）.
[2] Pengwei Hao， Ying Chen. Co-Histogram and Its Application in Video Analysis. In Proceedings of IEEE International Conference on Multimedia and Expo（ICME），Taiwan， 2004，195-203
[3] Mai K，Miller J，Zabih R.A robust method for detectingcuts and dissolves in video sequences. Proceedings of ACM Multimedia . 1995
[4] 陶志勇.一种基于颜色直方图的图像检索方法[J].科学技术与工程，2007（24）.
[5] 冈萨雷斯. 数字图像处理[M].北京：电子工业出版社，2005.
[6] 孔娟，田丽. 基于互信息量的视频关键帧提取算法[J].安阳工学院学报，2010（4）.
[7] 方勇，戚飞虎，冉鑫. 基于窗帧差的镜头边界系数模型及其应用[J]. 电子学报， 2005，34（5）：810-816.
