一种高效的视频切变检测算法

第4卷( A 版)　第10期 1999年10月 中国图象图形学报 Journal of Image and Graphics Vol. 4( A ) , No . 10 Oct. 1999 * 本文研究得到国家自然科学基金和“863”高技术计划支持 收稿日期: 1998-11-11;收到修改稿日期: 1999-02-03 一种高效的视频切变检测算法* 陆海斌 章毓晋 (清华大学电子工程系, 北京　100084) 摘　要　介绍了一种可以在压缩域和非压缩域实时检测视频切变的算法。算法采用了大小双重窗口,利用大窗口 全局阈值提取候选切变位置, 再在以候选切变位置为中心的小窗口中结合双侧和单侧判断进一步检测真实切变位 置。算法能有效地避免因摄像机和目标的剧烈运动造成误检和漏检的情况, 在检测五段视频(近9000帧, 共98个切 变)的实验中,取得100%的查全率和96%的准确率。 关键词　基于内容检索　视频分割　切变检测 0　引　言 视频分割是基于内容的视频查询和非线性浏览 系统的一个重要模块, 通过将输入的视频流分割成 其基本单元——镜头——的集合, 最终提取出关键 帧和运动信息以供浏览和检索之用。由于在一般影 片和电视剧中,场景的变化主要是切变(场景的突然 变化)以及淡入、淡出、淡入又淡出等渐变, 因此我们 主要侧重于对这些变化的高准确率的检测。切变是 视频分割要解决的第一个问题, 本文先简单总结一 些切变检测方法的特点,然后给出一个快速且查全 率和准确率很高的算法。 1　现有切变检测算法讨论 一个通用的切变检测框图可见图1。视频源 MPEG 流 提取 DC图象 视频序列 8× 8非压缩视频 邻域平均 切变检测 镜头集 闪光检测 图1　切变检测框图 既可以是MPEG 流, 也可以是图象采集卡得到的非 压缩的视频序列。从 MPEG 流中提取 DC 图象, 而 从非压缩的视频序列通过8×8邻域平均都可以得到 供切变检测的序列图象。切变检测算法在此基础上 可以检测出视频序列中的切变位置和闪光位置。闪 光位置不应该是镜头的边界, 所以从切变位置中刨 除闪光位置,得到初步的镜头集。 以下先简要地介绍现有几种典型切变检测算法 的优缺点, 然后就切变检测中的阈值选取、DC 图象 的获取、闪光的检测给予一些具体讨论。 1. 1　现有切变检测算法 场景变化检测算法可分为压缩域和非压缩域两 类。两类算法的思路大体一致,只是压缩域中的算法 由于利用了压缩域的信息有一些自己的特点。在压 缩域的场景变化检测算法中, 较为流行的是先比较 相邻两个 I 帧的差异, 找到可能有镜头变化的 I帧, 再利用相邻两个 I 帧之间的B、P 帧的信息来确定切 变的准确位置[ 1]。这种方法的好处是不用解码,直接 在 MPEG 流中检测, 因此算法速度快。缺点是由于 要利用MPEG 的编码信息, 所以受到该编码算法优 劣的影响,造成检测效果不稳定。另一个缺点是很难 直接利用这些信息去检测渐变。 非压缩域中的场景变化检测算法基本是顺序比 较相邻两帧的差异,所不同的是选取什么特征来表 示差异。最流行的算法是比较相邻两帧的直方图(灰 度或彩色直方图) [ 2] , 再以欧氏距离(见式( 1) )或直 方图交叉(见式( 2) )等作为差异度量: D ( j , k) = ∑M i= 1 {h j ( i) - hk( i ) } 2 ( 1) D ( j , k) = ∑M i= 1 min{hj ( i ) , hk( i ) } ∑M i= 1 hk( i ) ( 2) 其中 j , k 为视频序列中相邻的两帧, h (�)为直方 图,M 为直方图级数。 这类算法认为有相同背景、相同目标的两帧图 象在直方图上的差异应很小。由于直方图体现了图 象总体的灰度分布, 因此基于直方图的比较法对小 运动和噪声不敏感。它存在的问题是有时不同目标 的场景可以有近似的灰度或颜色分布,所以容易造 成漏检。图2给出两个实例,第一行是本文所用一个 测试片段(《空军一号》)中的两组相邻帧图(分别为 第63帧和64帧与第387帧和388帧) ,第二行给出它们 对应的直方图。由图可见仅用直方图做度量,很难将 每组相邻帧中的两帧图切分开。 另一类方法是累计相邻两帧中对应象素的差 异,当差异超过预定的阈值时认为有切变存在 [ 3]。这 种方法的最大问题是对摄像机和物体的运动比较敏 感,当运动较大时,相邻两帧的差异往往会超过预定 的阈值,从而造成误检。可行的解决办法是先平滑图 象,比如用8×8邻域平滑以抵消一些运动的影响, 同 时滤去噪声(这对通过图象采集卡得到的数据尤其 重要)。但是对较大的运动, 帧间差异仍然会较大而 使误检情况严重。 还有一类方法通过检测当前帧相对前一帧的边 界位置的变化来分割视频 [ 4] , 不过该算法对过暗或 过亮的镜头的检测效果差,因为这时候边界不显著。 另外虽然它对切变的检测效果同前两种相当, 但计 算量要比前两种大很多。 图2　直方图比较法的漏检情况 1. 2　切变检测中的阈值选取 选取合适的阈值以判定切变是一个困难的工 作。在文献[ 2]中,当直方图间的差异大于平均差异 的5到6倍时, 算法就认为有切变发生。试验证明,这 种类似全局阈值的方法有较大弊端。比如, 当镜头内 有剧烈运动时,会有连续多帧被判定为切变,从而造 成严重的误检;而对于背景变化较小的切变,该方法 会发生漏检。 文献[ 5]中提出了一种“滑动窗口”的检测方法。 首先定义一个大小为2m- 1的窗口, 使需检测的帧 位于窗口正中。然后根据下式计算第 i 和 i+ 1帧的 差异: D i= D ( i , i + 1) = ∑ x , y I i( x , y ) - I i+ 1( x , y ) ( 3) 其中, I i ( x , y )是第 i 帧象素( x , y )的亮度。如果满 足以下条件认为第 l帧为切变位置: ( 1) D l� D j , j= l- m+ 1,⋯, l- 1, l+ 1,⋯, l+ m- 1; ( 2) D l� b×D k, D k 为窗口中第二大的差异值, b 为系数。 上述方法由于利用了切变位置局部的信息,检测效 果比全局阈值法有相当大的提高。但是,我们通过对 该算法的分析和试验发现它仍存在两个问题: 一个是漏检问题。在我们测试的《空军一号》里 806 中国图象图形学报 第4卷( A 版) 的一个片段( 1360帧,共20个切变)中,利用文献[ 5] 中的算法,会有5处切变被漏检。分析发现, 由于该片 段在晃动的机舱中拍摄,镜头中又有大目标的运动, 造成镜头内一系列的较大差异, 如对图3中的 A 段 (两个峰 a、b之间是一个镜头) ,文献[ 5]算法在 b点 造成漏检,因为此时算法的条件( 2)不满足。 另一个是误检问题。图4给出另一个差异图的实 例(取自《4个婚礼1个葬礼》) ,其中 a、b 是两个切变 的位置, c、d 是由于加字幕, 去字幕原因产生的小扰 动。本来 a、b 之间画面几乎静止, 但文献[ 5]的算法 仍会在 c、d 两点造成误检。 图3　《空军一号》中的一段差异图 图4　《4个婚礼1个葬礼》中的一段差异图 1. 3　DC图象获取 将 MPEG流完全解码是很费时间的,对有些工 作也是没有必要的。DC 图象是原图的缩微, 是原图 8×8平均的结果,邻域平均能减少差异度量对运动 的敏感程度,所以利用 DC 图象有可能更好地检测 切变。MPEG 流分 I 帧、P 帧、B 帧, 典型的 MPEG 流显示顺序为 IBBPBBPBBPBBPBBI⋯。从 I 帧中提 取 DC 图 象 不需 要 作 运 算, 因 为 c ( 0, 0) = 1 8∑ 7 x= 0 ∑7 y= 0 f ( x , y )。从B、P 帧中提取DC图象需要一 些运算。文献[ 5]中讨论了提取方法,并提出了一个 近似算法。该近似算法从 B、P 帧中提取 DC 图象只 需要对每个点进行4次乘法, 由于320×240全图的 DC 图象为40×30,所以得到一幅 DC图象共需4800 次乘法。这样的计算量在 Pent ium 级的机器上是完 全可以实时处理的。 1. 4　闪光检测 视频中常有突然的闪光出现,比如,照相机的闪 光灯常常表明有需要注意的场景出现。闪光持续时 间很短,亮度变化很大,但是场景中人物的变化却由 于时间短暂而变化很小。在差异图中闪光表现为两 个相邻很近,高度相当的突起,而在两峰之间和两峰 的旁边, 差异很小。按照一般的检测算法,闪光出现 时和结束时都会被认为是切变。但是无论从切变的 定义看,还是从视频内容上看,把闪光位置认为是切 变位置是不合理的。因此, 有必要去掉闪光的影响。 自然,最有效的办法就是检测到闪光的位置, 从而把 它从切变中除去。考虑到以上指出的闪光特征,对它 们的检测并不困难。文献[ 5]中给出了一个闪光检测 算法依据:局部最大值同局部第二大值很相近,且比 其余的值大许多。 2　双重窗口切变检测算法 通过上面的分析,可以看到现有切变检测算法 各有不同的特点,也存在不同的问题。我们进行视频 分割的目的是为了进一步的视频检索和浏览, 所以 希望在保证查全率的基础上提高准确率。为此,我们 以累计对应象素差异为主要度量,并且采用双重窗 口的方法, 利用在大窗口中取全局阈值以提取候选 切变位置, 再利用以候选切变位置为中心的小窗口 具体检测切变位置。在小窗口检测中我们又结合了 双侧和单侧检测方法以提高查全率。为避免单侧检 807第10期 陆海斌等:一种高效的视频切变检测算法 测可能造成的误检, 我们通过将图象分块并比较前 后两帧对应块直方图的方法做进一步确认。具体算 法步骤如下: ( 1) 先定义差异度量为: D ( j , k ) = ∑ x, y f ( �Y j ( x , y ) - Y k ( x , y ) � ) N ( 4) 其中 N 是一帧中的总象素数, 阈值函数 f (�)由下 式定义: f ( x ) = 1, x > T 0, o therw ise ( 5) 　　( 2) 定义一个大窗口,其大小为 WB ,它包含待 检测的帧。在该窗口中统计差异均值 mean; 均值 mean 的引入是为了筛选出可能的切变位置,即大于 mean 一定倍数的差异才被进一步检测,以确认是否 是真正的切变位置。这个条件体现在后面( 4)之( a) 和( 5)之� 中。 ( 3) 再定义一个小窗口, 其大小 WS = 2m- 1, 使待检测的候选帧位于窗口正中; ( 4) 令 D l= D ( l- 1, l)为两帧间的差异,如果同 时满足以下(双侧)条件: � D l� a1×mean; � D l� D j , j = l- m+ 1,⋯, l- 1, l+ 1,⋯, l+ m- 1; � D l� b1×D k , D k 为窗口中第二大的差异值。 则认为第 l帧为切变位置,返回( 2) , 从第 l + m 帧 继续检测; ( 5) 如果满足以下(单侧)条件: � D l� a2×mean; � D l� b2×D k1　或　D l� b2×D k2。 其中: D k1= max ( D j ) , j = l- m+ 1,⋯, l- 1, D k2= max ( D j ) , j = l + 1, ⋯, l+ m- 1, 则认为可能有切 变,需进一步判断。为此又定义一个差异度量(其中, hj , hk 分别是 j , k 帧的直方图,分母为归一化因子) : �( j , k ) = ∑ M i= 1 �hj ( i ) - hk ( i) � ∑M i= 1 {hj ( i ) + hk ( i) } ( 6) 如果又满足 �( l- 1, l ) � c, 则认为第 l 帧为切变位 置,返回( 2) , 从第 l+ m 帧继续检测。 这里有几点再说明一下: 首先应用滑动大窗口 WB 是为了避免误检, 类似于全局阈值法,通过引入 差异均值 mean可以解决前述文献[ 5]算法的误检 问题, 同时减少了搜索量。其次用单侧滑动小窗口, 即算法第( 5)步是为了解决因大运动造成的漏检现 象,但考虑到同时也有可能引入误检,因此加入条件 �( l- 1, l) � c, 可有效避免误检现象。最后由于对全 图进行直方图统计会丢失象素灰度空间分布信息, 所以将图象分成 n×n块,对前后帧的对应块求 �i, i = 0, 1, ⋯, n×n, 然后取平均, 得 �( l - 1, l) = 1 n× n∑ n×n i= 0 �i, 这样可以有效避免不同场景有相同空 间灰度分布的情况。 3　试验结果 为了比较双重窗口算法和文献[ 5]的算法,我们 选取5部影片中的有代表性且较难分割的片段作为 测试数据。其中《空军一号》中,有许多大目标剧烈的 运动;《4个婚礼1个葬礼》的片段中有几乎静止的镜 头、闪光、及不少摄像机的运动;《壮志凌云》的片段 是空战的场景, 切变很多,同时兼有摄像机和目标的 剧烈运动。另外还有《新难兄难弟》中一个人从楼顶 坠下,摄像机跟随的镜头和动画片《小倩》中的一个 片段。 为了比较算法效率, 我们定义了两个衡量标准: ( 1) 查全率 = 正确检测数 / (正确检测数 + 漏检数) ( 2) 准确率 = 正确检测数 / (正确检测数 + 误检数) 在试验中我们对算法的参数选择如下:双重窗 口算法中,WB= 500, m= 12, a1= a2= 1. 2, b1= b2= 2, n= 2, c= 0. 3,文献[ 5]中算法: m= 10, b= 2。 表1和表2分别给出用文献[ 5]中算法和双重窗口 算法对前述视频片段的检测结果。可以看出, 双重窗 口算法在查全率上有很大提高; 在准确率上由于引入 大窗口,误检情况也有所减少。需要指出两种算法在 《壮志凌云》片段中的误检都最多,事实上误检位置处 飞机有高速的运动,以致于相邻两帧虽然有一样的飞 机,其背景(主要是云层)已经很不相同了。 很显然,算法中参数的选取对查全率、准确率至 关重要,增加小窗口尺寸 m 将提高准确率, 但是会 降低查全率;对 b2的选取也有同样的情况。文献[ 5] 探讨了参数选取问题,思路是变动一个参数, 固定其 它参数, 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 漏检、误检的变化,最终选取一组折衷 的参数。本文用类似的方法确定参数的范围, 得出 WB= 400～800, m= 8～15, a1= a2= 1. 0～1. 7, b1= b2= 2～3, c= 0. 27～0. 35。需要指出的是,这种观察 的方法有局限性, 首先对不同类型的片段参数范围 808 中国图象图形学报 第4卷( A 版) 会略有不同, 其次由于观测数据有限,对同一类型的 片段该范围的合理性也可商榷。我们正在研究这个 问题,希望通过非监督聚类避免参数选择的问题。 表1　文献[ 5]算法试验结果 序列来源 总帧数 总切变数 正确检测数 漏检数 误检数 查全率 准确率 空军一号 1360 20 15 5 0 75% 100% 4个婚礼1个葬礼 3434 18 16 2 2 89% 89% 壮志凌云 1602 36 28 8 3 78% 90% 新难兄难弟 962 12 12 0 0 100% 100% 小倩(动画) 1402 12 10 2 0 83% 100% 总和 8760 98 81 17 5 83% 94% 表2　双重窗口算法试验结果 序列来源 总帧数 总切变数 正确检测数 漏检数 误检数 查全率 准确率 空军一号 1360 20 20 0 0 100% 100% 四个婚礼一个葬礼 3434 18 18 0 0 100% 100% 壮志凌云 1602 36 36 0 3 100% 92% 新难兄难弟 962 12 12 0 0 100% 100% 小倩(动画) 1402 12 12 0 1 100% 92% 总和 8760 98 98 0 4 100% 96% 4　讨　论 本文提出了一种能同时处理非压缩域视频和 MPEG视频的实用视频切变检测算法。考虑到视频 分割的目的是为了视频检索和浏览,我们在保证查 全率的基础上提高准确率。为此,我们以累计对应象 素差异为主要度量, 并且利用大窗口全局阈值提取 候选切变位置,再在以候选切变位置为中心的小窗 口中结合双侧和单侧检测切变位置。为避免单侧检 测可能造成的误检, 我们又利用将图象分块比较前 后两帧对应块直方图的方法做进一步确认。算法在 不需要人工干预的情况下,取得了很高的查全率和 准确率。 参 考 文 献 1　Kobla V, Doermann D. Compress ed d om ain video lndexing tech- n iques using DCT and m ot ion vector informat ion in MPEG video. S PIE , 1997, 3022: 200～211. 2　Zhang H J , Kankanhal i A, Smoliar S W . Automatic part it ioning of ful l-mot ion video. Mult im edia S ystem s, 1993, 1: 10～28. 3　Zhang H J , Smoliar S W , Wu J H. C on tent-based video brow - s ing tool s. SPIE, 1995, 2417: 389～398. 4　Zabih R, Miller J, Mai K. A feature-based algorithm for dete- ct ing and classifying scene break s. ACM, Mu lt imed ia'95, 1995, 189～200. 5　Yeo B L, Liu B. Rap id s cene analysis on compres sed video. IEEE T rans Circuit s and Sys tems for Video T echnology, 1995, 5: 533～544. 　　　陆海斌　1997年毕业于清华大学电 子工程系, 现为清华大学电子工程系硕 士研究生。研究方向为信号与信息处理、 图象处理、基于内容的图象和视频检索。 　　　章毓晋　教授, 博士生导师。1989年 获比利时列日大学应用科学博士学位, 从1989年至1993年在荷兰德尔夫特大学 作博士后及研究工作。近年来承担了国 家自然科学基金、国家科委高技术计划 “863”、国家“九五”重点科技攻关及国家 教委博士点基金等项目。主要研究领域 为图象工程 (图象处理, 图象分析, 图象 理解及其应用)和相关学科,已在上述领 域发表了近100篇研究 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 。现任中国图 象图形学会常务理事,副秘书长, 学术委 员会副主任, 《中国图象图形学报》副主 编。 809第10期 陆海斌等:一种高效的视频切变检测算法 An Efficient Algorithm for Detecting Abrupt Scene Change in Video Lu Haibin, Zhang Yujin ( Depar tment of E le ctronic Eng ineer ing , T singhua Univ er si ty, Beij ing 100084) Abstract　A real-time alg or ithm is proposed fo r t he detection of abrupt scene change in uncom pressed as well as compressed video . T he proposed alg or ithm is based on the dual ( one big and one sma ll) sliding w indows. T he big w indow is used fo r se- lecting the probable positions of abrupt scene change , and the small window w hose center is at the pr obable positio n selected is used for determ ining the r eal posit ions o f abrupt scene change. The decision made in the small w indow is helped by a combi- na tion o f double side checking and a sing le side checking. T his a lg or ithm can effectively avo id t he false detection and m iss de- tection caused by the v iolent m otion o f camera and/ o r la rg e objects. The effectiveness of our algo r ithm has been demonst rated using fiv e video clips ( about 9000 fr ames, 98 abrupt scene changes) , t he r ecall r ate is 100% and the precision rat e is 96% . Keywords　Cont ent -based r etrieval, V ideo segmentation, Abrupt scene change detection 3D Blaster GeForce 世界上首枚图形处理器(GPU)隆重登场了 现在您所拥有的3D Blaster GeForce 图形加速卡是一款具有划时代意义的产品。它的心脏就是世界上第一枚图形处理器 ( GPU )——来自 NVIDIA 公司的 GeForce 256加速芯片。从此,您将获得从未有过的、真实的3D 游戏体验。 目前, 成千上万的用户所使用的3D 游戏加速器仅仅是一个简单的渲染引擎,它仍然需要依赖 CPU 来处理变换和光照等 关键的3D 图形处理步骤。为了赢得尽可能多的用户,保证游戏的流畅度,开发商们别无选择, 只能限制每一个场景中多边形和 物体的数量,从而使得游戏的3D 效果难以尽如人意。而有了3D Blaster GeForce之后,整个3D 处理流水线不再需要 CPU , 皆 可由 GeForce 256加速芯片单独完成, 从而使开发商们可以更充分地利用 CPU 的资源,创造出更丰富、更细腻的3D 世界,更精 确的物理模型和更高的人工智能。总之, 您会觉得3D游戏更难玩、更好玩,每一幅场景甚至是每一个物体都更加真实动人、简 直令你置身于其中而难辨真伪。 3D Blaster GeForce性能与特征 �独一无二的独立单元并行处理结构 GeForce 256独有全新的 QuadEng ine设计结构(即独立的变换、光照、三角形构造和渲染引擎) , 可提供令人难以置信的高 效的渲染能力——每秒钟可处理1500万个三角形。每一种引擎并行运行,再借助于 AGP4X 接口的巨大数据吞吐量和强大性 能, 将3D 图形处理带入一个更高的境界。这枚举世无双的芯片集成了2300万个晶体管——相当于 Pentium Ⅲ的整整两倍还多 呢! �10亿个象素= 1000个百万象素 256位 QuadPipe 渲染引擎由4个独立的并行工作的3D 渲染引擎,每秒可渲染4. 8亿个象素。在丝毫不影响性能的情况下, 每一个象素仍然可以支持32位色,同时还支持象8向各向异性过滤、模板缓存以及点乘积凹凸映射等这样的复杂材质处理效 果。 �它还可以帮您作什么? 3D Blaster GeFo rce 不仅仅是针对游戏而设计的。它还集成有完全支持Window s 和 OpenGL ICD 的2D 加速器,因此您可 以用 GeFo rce 进行 CAD/ CAM、设计或电子表格处理。当然啦,一旦您觉得工作疲劳时, 还可以用 GeForce玩一玩游戏, 放松 一下您的神经。因为它也支持所有主要的3D API, 包括 Microsoft Dir ect X 7和 OpenGL。 如果再配合WinDVD(当然啦,您还得有一个 DVD-ROM 驱动器) , 您就可以在您的 PC 上尽情享受到 DVD 影片带给您 的高清晰画面和强烈震撼的体验。这是因为 3D Blaster GeForce 同样也支持 MPEG2回放,包括8�1缩放引擎,这样即可保证从 小窗口到大窗口的切换时不会有任何图象保真度的损失。 (下转第817页) 810 中国图象图形学报 第4卷( A 版)