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

1、基于流形特征的镜头边界检测后处理算法镜头是视频分析和检索的基础, 为了有效检测镜头边界, 并对镜头边界进行分类, 提出一种新的镜头边界描述子: 镜头边界流形 视频流可以看做一个高维空间, 镜头边界流形是隐含在该空间中的局部结构, 它能够有效区分镜头边界和非镜头边界, 以及区分不同类型的镜头边界 采用这种特征, 提出一种后处理算法, 一方面去除预检测镜头边界的虚警, 另一方面将真正的镜头边界分类 实验结果证实了镜头边界流行的有效性以及后处理算法的优异性能关键词 镜头边界检测; 镜头边界检测后处理; 镜头边界分类; 拉普拉斯特征映射中图法分类号 TP181; T P37 随着多媒体技术的发展, 对

2、海量的视频数据进行索引和检索已成为一个重要的研究课题 视频通常是无结构的流, 为了方便对视频内容进行分析处理, Rui 等人 1 提出将视频流按内容进行层次划分,从高层到低层分别为视频( video ) 、场景( scene) 、镜头组( group) 、镜头( shot ) 和关键帧( key frame) 镜头是指摄像机从打开到关闭的过程中记录下来的一组连续的帧图像, 它是组成视频的基本物理单位, 视频索引和检索就建立在镜头边界检测的基础上由于视频后期剪辑制作不同, 镜头边界大致分为两类: 切变( cut ) 和渐变( gradual) 渐变镜头边界又分很多种, 主要包括淡入淡出( fad

3、e inout ) 、溶解( dissolve) 和擦变( w ipe) 镜头边界的类型能提供更多高层语义, 比如, 一段排球比赛中, 直播镜头与回放镜头之间的切换常常使用擦变 检索回放镜头时可以在擦变镜头中寻找, 大大缩小了检索范围 因此, 镜头边界分类对于视频分析与检索有重要价值文献 23 对多种镜头边界检测算法进行了比较 以往检测算法的要点包括两个方面: 一是特征( feature)及度量( met ric) ; 二是针对度量的决策算法特征用来刻画视频流中每一帧的视觉内容特性, 可以是颜色 4 、边缘 5 或者压缩域上的参数 6; 度量用来刻画视频流中帧与帧之间的特征变化, 文献 7对多

4、种度量进行介绍并比较了它们的性能 决策算法的任务则是根据度量采取一定策略和算法检测出镜头边界在现有的镜头边界检测算法中, 采用的特征有像素值( 灰度值或颜色值) 、直方图以及MPEG 压缩域上的参数 衡量帧间差异最简单的度量方法是计算两帧基于像素点的距离, 但该方法对运动敏感, 容易造成误检 直方图描述的是图像的全局信息, 一定程度上可以减小运动对检测的影响 由于目前多数视频采用MPEG 压缩标准, 直接在压缩域上提取特征可以提高检测速度, 常用的压缩域特征包括DC图 8 、运动向量、预测宏块数、宏块的类型信息 6 等现有的针对度量的决策算法包括全局阈值法、自适应阈值法、双阈值比较法 9 、基

5、于统计的决策算法全局阈值法对整段视频序列采用一个全局阈值, 这种方法最简单直接, 但鲁棒性差, 对于不同类型的视频片段或同类型视频的不同时间片段需要设置不同的阈值 自适应阈值法利用一个滑动窗口, 统计该窗口内视频的局部特性, 根据统计特性设定动态阈值 以上两种方法适用于检测突变镜头, 不能对渐变镜头进行准确定位 文献 9 提出的双阈值比较法能够检测出渐变镜头的起始和终止位置, 但不能区分缓变镜头边界的具体类型本文把视频看做图像在时间轴上展开的一个高维空间, 空间中的各点在时间轴上是局部相关的镜头发生切换时, 高维空间的点呈现特有分布, 这种相关性分布可以看做一个低维的流形嵌入在高维空间中 我们

6、采用流形学习的方法 10 把它提取出来刻画不同类型的镜头边界, 以这种特征为基础, 提出一种基于学习的镜头边界检测后处理方法1 镜头边界类型分析镜头边界的编辑效果有很多种, 主要包括切变和渐变, 渐变镜头边界又可以分为溶解、淡入淡出和擦变 以下给出它们的数学模型 公式中, S( x , y ,t ) 表示镜头发生切换时镜头边界的各帧, 表示镜头边界的类型, S 1( x , y , t ) 和S 2 ( x , y , t ) 分别表示切换前的镜头和切换后的镜头1) 切变: 两_L_謃个镜头直接拼接在一起, 对于边界处两帧, 所有像素值发生突然变化S cut( x , y , t ) =S 1

7、( x , y , t ) , t ! t 1,S 2( x , y , t ) , t t 1 2) 溶解: 镜头S 1 逐渐变弱, 镜头S 2 逐渐变强,两个镜头交叠在一起直至变换结束S dissolve( x , y , t ) = S 1( x , y ) (t - t 1T) +S 2( x , y ) (t 2 - tT) ,式中, t 1 和t 2 分别表示溶解变换开始和结束的时间, T 表示镜头变换持续的时间3) 淡入淡出: 淡入是镜头从无到有的过程, 淡出反之S fadein( x , y , t ) = S ( x , y ) (t - t 1T) ,S fadeout(

8、x , y , t ) = S ( x , y ) (t 2 - tT) ,式中, t 1 表示淡入开始的时间, t 2 表示淡出结束的时间, T 表示淡入淡出持续的时间4) 擦变: 镜头S 2 按某个方向将镜头S 1 逐渐擦除 处于变换过程中的某帧图像从空间上来看, 一部分属于镜头S 1, 一部分属于镜头S 2S wipe( x , y , t ) = S 1( x , y ) f ( x , y , t ) +S 2( x , y ) 1 - f ( x , y , t ) 擦变有多种类型, 包括横向、竖向、对角线、圆形擦变等, 因而引入函数f ( x , y , t ) 来表示擦变规则,

9、函数的取值为0 或者1由以上分析, 各种镜头边界的视觉特征明显不同, 第2 节提出的方法能将这种特征有效提取出来2 镜头边界流形学习本节给出镜头边界流形提取的详细算法 视频流可以看做一个高维欧氏空间Rf N + 1, N 为每帧的像素个数, 另外一维是时间 视频中的每帧可以看做Rf N + 1空间中的一点, 这些点有着局部相关性在空间Rf N + 1中, 不同类型镜头边界中的各帧对应的高维空间点有着不同的局部相关性 我们采用流形学习的方法把这种嵌入在空间RfN + 1 中的局部结构提取出来, 以描述不同的镜头边界 首先给出流形学习的定义 11 :定义1 流形学习 令Y 是包含在Rf d 欧氏空

10、间的d 维域, 令f : Y Rf d 为一光滑嵌入, 其中N d 数据点 yi Y 由某个随机过程生成, 经f映射形成观测空间的数据 x i = f ( y i ) Rfd 一般称Y 为隐空间, y i 为隐数据 流形学习的目标是要从观测数据 x i 中重构f 和 yi 我们采用拉普拉斯特征映射的流形学习方法来发现和重构隐藏在空间Rf N + 1 中的边界流形 拉普1994 计算机研究与发展 2006, 43( 11)拉斯特征映射是基于局部保序思想来获得高维观测空间与低维结构的在局部意义下的对应 11 文献 10 的实验表明, 拉普拉斯特征映射所得到的流形有很好的聚类和分类效果, 这一点正符

11、合本文镜头后处理算法的需要 以下给出具体的镜头边界流形的学习算法:1) 抽取局部点集视频流有时间相关性, 因此首先抽取时间轴上临近的N 帧 设k 是候选镜头边界上某一帧的帧号, 以k 为中心取一个大小为N 的窗口, 即在k 帧前取( N - 1)2 帧, k 帧后取( N - 1)2 帧 将窗口中的每一帧作为一个节点, 构造加权的帧间关系图2) 构造帧间关系图对于Step1 中抽取的点集 X 1, #, X N , 如果X i 和X j 相关性高, 就将节点i 和j 之间加一条边加边的方式有两种: 邻接法 参数% R , 如果&X i- Xj &2 , 则将节点i 和j 之间用边连接起来; n

12、 近邻法 参数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

13、= ( jWj i , 然后得到拉普拉斯矩阵: L = D -W, 拉普拉斯矩阵L 是一个对称、半正定矩阵, 它可以被看做一个定义在图G 节点上的操作函数 计算下式的广义特征值和特征向量:Lf = Df ( 1) 设y0, #, y k- 1 是式( 1) 的特征向量, 按对应特征值从小到大排列, 可以证明, y0 对应的特征值为0, 向量y 0 的每个元素都为1 我们取一维向量y 1作为镜头边界的流形结构经过拉普拉斯特征映射之后得到的特征具有很好的区分特性 图1 给出了4 种类型镜头边界以及非镜头边界的帧间关系图和镜头边界流形 图1( a)表示帧间关系图, 示例图中所取窗口大小为N =11,

14、 颜色越浅表明相似度越高; 图1( b) 表示将图1( a) 的帧间关系图做拉普拉斯特征映射之后的流形结构 可以看出, 不同类型的镜头边界以及非镜头边界, 它们的帧间关系图具有不同的特征, 拉普拉斯特征映射之后的镜头边界流形是一维向量, 维数更低, 却能更好地区分不同的镜头边界 第4 节的实验结果证明了镜头边界流形的有效性Fig 1 Featur es for four shot boundar y ty pes and nonboundary ( a) Interfr ame graph and ( b) Shot boundary manifold图1 四种类型镜头边界以及非镜头边界的特征

15、图 ( a) 帧间关系图; ( b) 镜头边界流形3 基于流形特征的后处理算法第2 节提出的镜头边界流形有很好的区分特性, 我们在此基础上提出一种镜头边界检测后处理算法 首先, 进行镜头边界预检测, 得到候选的镜头边界位置; 然后提取候选镜头边界的流形; 最后, 把镜头边界流形送入分类器进行分类, 分为非镜头王 贝等: 基于流形特征的镜头边界检测后处理算法1995边界和镜头边界, 同时得到镜头边界的类型 系统流程图如下:Fig 2 The flow chart of shot boundary postrefinementalgor ithm图2 镜头边界后处理算法流程图 在图2 中, 上面的

16、虚线框表示训练模块, 下面的虚线框表示测试模块, 以下详细介绍:31 训练模块为了充分训练分类器, 训练模块采用大量训练样本 镜头内部存在着由多种原因造成的视觉内容变化, 包括闪光灯、物体运动和相机运动, 这些很容易造成检测算法的误检, 普通的阈值算法很难完全解决运动所带来的问题 而在我们的后处理算法中, 只要保证非镜头边界样本中包括容易造成误检的种种情况, 就能够大幅度提高镜头边界检测的准确率 训练模块采用第2 节提出的方法对样本提取边界流形32 边界预检测及后处理模块1) 镜头边界预检测预检测可以采用任何已有的镜头检测算法 预检测步骤的关键在于必须保证检测结果的高查全率, 因此需要将算法中

17、的阈值设置较低 这一步中检测的镜头边界虚警率很高, 但可以通过后继步骤消除虚警 本文采用的是文献 9 中提出的双阈值比较法 算法中有两个阈值T c 和T g , T g 小于T c,T c 用于检测切变镜头和渐变镜头的结束, T g 用于检测渐变镜头的开始 检测算法采用的特征是HSV颜色直方图, H, S, V 三个方向各有12, 4, 4 个槽, 直方图总维数为12 ) 4 ) 4= 192 这一步中的检测是在DC 图上进行的, 使用DC 图的好处有以下两点: DC 图可以直接由压缩域的参数计算得到, 不需要完全解码, 提取速度快; DC 图由压缩域得到,其大小是原始图像的164, 部分消除

18、了物体运动和相机运动的干扰2) 合并过短镜头步骤1) 中, 由于阈值设置较低, 会出现大量短镜头, 我们计算超短镜头( 10 帧) 与它前一镜头或后一镜头的相似度, 选择相似度较高的一个, 将短镜头与它合并 计算镜头相似度时, 采用的特征是HSV 直方图 这一步骤使得候选镜头边界的数量减少, 消除了部分明显不可能的候选边界, 减小了步骤3) 的计算量, 有利于提高后处理的准确率3) 提取候选镜头边界的流形采用第2 节介绍的方法提取候选镜头边界流形构造帧间关系图时所取的窗口长度为11, 帧间关系图中边的权重采用热核权重33 分类器将训练模块和检测模块提取的结果分别送入分类器进行训练和检测, 分类

19、器将候选镜头边界分为两大类: 镜头边界和非镜头边界 非镜头边界被作为虚警丢弃掉, 从而提高了镜头检测的准确率 同时镜头边界又可以进一步分为切变、溶解、擦变和淡入淡出4 种类型 现有的分类器都可以采用, 我们采用k 近邻( kNN) 分类器, 实验证明它性能好并且计算简单 12 4 实验与分析为验证镜头边界流形和后处理算法的有效性,我们在大量视频数据上进行实验 实验数据总共25段 帧、963 个镜头 这些数据具有很大挑战性, 视频内容多样, 涵盖了新闻、体育、科普、广告、教学等多类电视节目; 另外, 这些视频数据中的镜头边界类型也非常多样 实验中非镜头边界样本共有300 个, 它们取自预检测之后

20、的虚警边界 我们将训练样本之外的视频作为测试数据 我们采用了两种常用的性能评价标准 查全率( recall) : Recal l=N cN c+ N m, 准确率( precision) : Precision =N cN c+ N f,其中, N c 表示正确检测到的镜头边界数; N m 表示漏检的镜头边界数; N f 表示误检的边界数 表1 给出了测试数据信息:Table 1 Summary of Training and Testing Video Sets表1 训练与测试数据统计Video Number of FramesNumber of Shot BoundariesCuts Di

21、ssolves Wipes FadesT raining 323 276 43 62Test ing 42522 175 52 5 3241 镜头边界检测后处理结果为了验证后处理算法能否有效地去除虚警, 我们统计了测试视频在预检测之后以及后处理之后所1996 计算机研究与发展 2006, 43( 11) 有类型镜头边界总的查全率和准确率,给出:Table 2 Refinement Perf ormance of Shot Boundary Detection预检测之后的查全率很高, 准确率很低 通过后处理算法, 多数虚警镜头边界被去除,但查全率有所降低 总体来看, 查全率平均下降2%, 准确率平均上升28% 牺牲较小的查全率换取准确率的大幅提高, 这表明边界流形能够区分镜头边界与非镜头边界, 预检测边界的后处理是有效的对实验数据的观察表明, 被去除的虚警主要包括以下4 种类型: 闪光灯和光照影响; 字幕的出现或者消失; 物体运动, 比如在运动视频 足球 中, 场上球员的跑动容易导致预检测算法的误检; +遮挡,视频拍摄过程中忽然有人从镜头前晃过, 使得镜头内连续几帧视觉内容与其他帧完全不同42 镜头边界分类结果表3 给出了镜头边界分类的结果Table 3