基于流形特征的镜头边界检测后处理算法

基于流形特征的镜头边界检测后处理算法镜头是视频分析和检索的基础,为了有效检测镜头边界,并对镜头边界进行分类,提出一种新的镜头边界描述子:镜头边界流形�视频流可以看做一个高维空间,镜头边界流形是隐含在该空间中的局部结构,它能够有效区分镜头边界和非镜头边界,以及区分不同类型的镜头边界�采用这种特征,提出一种后处理算法,一方面去除预检测镜头边界的虚警,另一方面将真正的镜头边界分类�实验结果证实了镜头边界流行的有效性以及后处理算法的优异性能�关键词�镜头边界检测;镜头边界检测后处理;镜头边界分类;拉普拉斯特征映射中图法分类号�TP181;TP37��随着多媒体技术的发展,对海量的视频数据进行索引和检索已成为一个重要的研究课题�视频通常是无结构的流,为了方便对视频内容进行分析处理,Rui等人[1]提出将视频流按内容进行层次划分,从高层到低层分别为视频(video)、场景(scene)、镜头组(group)、镜头(shot)和关键帧(keyframe)�镜头是指摄像机从打开到关闭的过程中记录下来的一组连续的帧图像,它是组成视频的基本物理单位,视频索引和检索就建立在镜头边界检测的基础上�由于视频后期剪辑制作不同,镜头边界大致分为两类:切变(cut)和渐变(gradual)�渐变镜头边界又分很多种,主要包括淡入淡出(fadein�out)、溶解(dissolve)和擦变(wipe)�镜头边界的类型能提供更多高层语义,比如,一段排球比赛中,直播镜头与回放镜头之间的切换常常使用擦变�检索回放镜头时可以在擦变镜头中寻找,大大缩小了检索范围�因此,镜头边界分类对于视频分析与检索有重要价值�文献[2�3]对多种镜头边界检测算法进行了比较�以往检测算法的要点包括两个方面:一是特征(feature)及度量(metric);二是针对度量的决策算法�特征用来刻画视频流中每一帧的视觉内容特性,可以是颜色[4]、边缘[5]或者压缩域上的参数[6];度量用来刻画视频流中帧与帧之间的特征变化,文献[7]对多种度量进行介绍并比较了它们的性能�决策算法的任务则是根据度量采取一定策略和算法检测出镜头边界�在现有的镜头边界检测算法中,采用的特征有像素值(灰度值或颜色值)、直方图以及MPEG压缩域上的参数�衡量帧间差异最简单的度量方法是计算两帧基于像素点的距离,但该方法对运动敏感,容易造成误检�直方图描述的是图像的全局信息,一定程度上可以减小运动对检测的影响�由于目前多数视频采用MPEG压缩标准,直接在压缩域上提取特征可以提高检测速度,常用的压缩域特征包括DC图[8]、运动向量、预测宏块数、宏块的类型信息[6]等�现有的针对度量的决策算法包括全局阈值法、自适应阈值法、双阈值比较法[9]、基于统计的决策算法�全局阈值法对整段视频序列采用一个全局阈值,这种方法最简单直接,但鲁棒性差,对于不同类型的视频片段或同类型视频的不同时间片段需要设置不同的阈值�自适应阈值法利用一个滑动窗口,统计该窗口内视频的局部特性,根据统计特性设定动态阈值�以上两种方法适用于检测突变镜头,不能对渐变镜头进行准确定位�文献[9]提出的双阈值比较法能够检测出渐变镜头的起始和终止位置,但不能区分缓变镜头边界的具体类型�本文把视频看做图像在时间轴上展开的一个高维空间,空间中的各点在时间轴上是局部相关的�镜头发生切换时,高维空间的点呈现特有分布,这种相关性分布可以看做一个低维的流形嵌入在高维空间中�我们采用流形学习的方法[10]把它提取出来刻画不同类型的镜头边界,以这种特征为基础,提出一种基于学习的镜头边界检测后处理方法�1�镜头边界类型分析镜头边界的编辑效果有很多种,主要包括切变和渐变,渐变镜头边界又可以分为溶解、淡入淡出和擦变�以下给出它们的数学模型�公式中,S�(x,y,t)表示镜头发生切换时镜头边界的各帧,�表示镜头边界的类型,S1(x,y,t)和S2(x,y,t)分别表示切换前的镜头和切换后的镜头�1)切变:两_L___謃个镜头直接拼接在一起,对于边界处两帧,所有像素值发生突然变化�Scut(x,y,t)=S1(x,y,t),t!t1,S2(x,y,t),tt1���2)溶解:镜头S1逐渐变弱,镜头S2逐渐变强,两个镜头交叠在一起直至变换结束�Sdissolve(x,y,t)=S1(x,y)(t-t1T)+S2(x,y)(t2-tT),式中,t1和t2分别表示溶解变换开始和结束的时间,T表示镜头变换持续的时间�3)淡入淡出:淡入是镜头从无到有的过程,淡出反之�Sfadein(x,y,t)=S(x,y)(t-t1T),Sfadeout(x,y,t)=S(x,y)(t2-tT),式中,t1表示淡入开始的时间,t2表示淡出结束的时间,T表示淡入淡出持续的时间�4)擦变:镜头S2按某个方向将镜头S1逐渐擦除�处于变换过程中的某帧图像从空间上来看,一部分属于镜头S1,一部分属于镜头S2�Swipe(x,y,t)=S1(x,y)f(x,y,t)+S2(x,y)[1-f(x,y,t)]���擦变有多种类型,包括横向、竖向、对角线、圆形擦变等,因而引入函数f(x,y,t)来表示擦变规则,函数的取值为0或者1�由以上分析,各种镜头边界的视觉特征明显不同,第2节提出的方法能将这种特征有效提取出来�2�镜头边界流形学习本节给出镜头边界流形提取的详细算法�视频流可以看做一个高维欧氏空间RfN+1,N为每帧的像素个数,另外一维是时间�视频中的每帧可以看做RfN+1空间中的一点,这些点有着局部相关性�在空间RfN+1中,不同类型镜头边界中的各帧对应的高维空间点有着不同的局部相关性�我们采用流形学习的方法把这种嵌入在空间RfN+1中的局部结构提取出来,以描述不同的镜头边界�首先给出流形学习的定义[11]:定义1�流形学习�令Y是包含在Rfd欧氏空间的d维域,令f:Y∀Rfd为一光滑嵌入,其中Nd�数据点{yi}Y由某个随机过程生成,经f映射形成观测空间的数据{xi=f(yi)}Rfd�一般称Y为隐空间,{yi}为隐数据�流形学习的目标是要从观测数据{xi}中重构f和{yi}�我们采用拉普拉斯特征映射的流形学习方法来发现和重构隐藏在空间RfN+1中的边界流形�拉普1994计算机研究与发展�2006,43(11)拉斯特征映射是基于局部保序思想来获得高维观测空间与低维结构的在局部意义下的对应[11]�文献[10]的实验表明,拉普拉斯特征映射所得到的流形有很好的聚类和分类效果,这一点正符合本文镜头后处理算法的需要�以下给出具体的镜头边界流形的学习算法:1)抽取局部点集视频流有时间相关性,因此首先抽取时间轴上临近的N帧�设k是候选镜头边界上某一帧的帧号,以k为中心取一个大小为N的窗口,即在k帧前取(N-1)�2帧,k帧后取(N-1)�2帧�将窗口中的每一帧作为一个节点,构造加权的帧间关系图�2)构造帧间关系图对于Step1中抽取的点集{X1,#,XN},如果Xi和Xj相关性高,就将节点i和j之间加一条边�加边的方式有两种:∃�邻接法[参数�%R],如果&Xi-Xj&2�,则将节点i和j之间用边连接起来;∋n近邻法[参数n%N],如果i是j的n个最近邻点之一,或者j是i的n个最近邻点之一,则把节点i和j连接起来�我们采取的方法是将窗口中的点两两连线,因为它们在时间轴上相邻,具有较高的相关性�3)选取权值帧间关系图中,边的权值选取方法有两种:∃热核法[参数t%R],如果节点i和j是相连的,则将它们的边的权值设置为Wij=e&Xi-Xj&2t;∋简单方法[没有参数],只要节点i和j相连,就置权值Wij=1,我们采用的是热核权重�4)特征映射对于构造好的帧间关系图G,根据边的权重得到它的邻接矩阵W,由W计算对角矩阵D,Dii=(jWji,然后得到拉普拉斯矩阵:L=D-W,拉普拉斯矩阵L是一个对称、半正定矩阵,它可以被看做一个定义在图G节点上的操作函数�计算下式的广义特征值和特征向量:Lf=Df�(1)��设y0,#,yk-1是式(1)的特征向量,按对应特征值从小到大排列,可以证明,y0对应的特征值为0,向量y0的每个元素都为1�我们取一维向量y1作为镜头边界的流形结构�经过拉普拉斯特征映射之后得到的特征具有很好的区分特性�图1给出了4种类型镜头边界以及非镜头边界的帧间关系图和镜头边界流形�图1(a)表示帧间关系图,示例图中所取窗口大小为N=11,颜色越浅表明相似度越高;图1(b)表示将图1(a)的帧间关系图做拉普拉斯特征映射之后的流形结构�可以看出,不同类型的镜头边界以及非镜头边界,它们的帧间关系图具有不同的特征,拉普拉斯特征映射之后的镜头边界流形是一维向量,维数更低,却能更好地区分不同的镜头边界�第4节的实验结果证明了镜头边界流形的有效性�Fig�1�Featuresforfourshotboundarytypesandnon�boundary�(a)Inter�framegraphand(b)Shotboundarymanifold�图1�四种类型镜头边界以及非镜头边界的特征图�(a)帧间关系图;(b)镜头边界流形3�基于流形特征的后处理算法第2节提出的镜头边界流形有很好的区分特性,我们在此基础上提出一种镜头边界检测后处理算法�首先,进行镜头边界预检测,得到候选的镜头边界位置;然后提取候选镜头边界的流形;最后,把镜头边界流形送入分类器进行分类,分为非镜头王�贝等:基于流形特征的镜头边界检测后处理算法1995边界和镜头边界,同时得到镜头边界的类型�系统流程图如下:Fig�2�Theflowchartofshotboundarypost�refinementalgorithm�图2�镜头边界后处理算法流程图��在图2中,上面的虚线框表示训练模块,下面的虚线框表示测试模块,以下详细介绍:3�1�训练模块为了充分训练分类器,训练模块采用大量训练样本�镜头内部存在着由多种原因造成的视觉内容变化,包括闪光灯、物体运动和相机运动,这些很容易造成检测算法的误检,普通的阈值算法很难完全解决运动所带来的问题�而在我们的后处理算法中,只要保证非镜头边界样本中包括容易造成误检的种种情况,就能够大幅度提高镜头边界检测的准确率�训练模块采用第2节提出的方法对样本提取边界流形�3�2�边界预检测及后处理模块1)镜头边界预检测预检测可以采用任何已有的镜头检测算法�预检测步骤的关键在于必须保证检测结果的高查全率,因此需要将算法中的阈值设置较低�这一步中检测的镜头边界虚警率很高,但可以通过后继步骤消除虚警�本文采用的是文献[9]中提出的双阈值比较法�算法中有两个阈值Tc和Tg,Tg小于Tc,Tc用于检测切变镜头和渐变镜头的结束,Tg用于检测渐变镜头的开始�检测算法采用的特征是HSV颜色直方图,H,S,V三个方向各有12,4,4个槽,直方图总维数为12)4)4=192�这一步中的检测是在DC图上进行的,使用DC图的好处有以下两点:∃DC图可以直接由压缩域的参数计算得到,不需要完全解码,提取速度快;∋DC图由压缩域得到,其大小是原始图像的1�64,部分消除了物体运动和相机运动的干扰�2)合并过短镜头步骤1)中,由于阈值设置较低,会出现大量短镜头,我们计算超短镜头(10帧)与它前一镜头或后一镜头的相似度,选择相似度较高的一个,将短镜头与它合并�计算镜头相似度时,采用的特征是HSV直方图�这一步骤使得候选镜头边界的数量减少,消除了部分明显不可能的候选边界,减小了步骤3)的计算量,有利于提高后处理的准确率�3)提取候选镜头边界的流形采用第2节介绍的方法提取候选镜头边界流形�构造帧间关系图时所取的窗口长度为11,帧间关系图中边的权重采用热核权重�3�3�分类器将训练模块和检测模块提取的结果分别送入分类器进行训练和检测,分类器将候选镜头边界分为两大类:镜头边界和非镜头边界�非镜头边界被作为虚警丢弃掉,从而提高了镜头检测的准确率�同时镜头边界又可以进一步分为切变、溶解、擦变和淡入淡出4种类型�现有的分类器都可以采用,我们采用k近邻(kNN)分类器,实验证明它性能好并且计算简单