（计算机软件与理论专业论文）基于演化算法的视频场景分割.pdf

摘要 随着计算机技术在视频方面应用的发展，让计算机理解视频内容成为现代计 算机视觉技术研究的重点。视频场景分割是实现视频语义理解的第一步，也是实 现视频数据高效浏览与索引的关键性步骤。场景分割是在一个较高的层次上对视 频进行分割，它需要在视频镜头检测与镜头关键帧提取的基础之上，综合运用视 频场景检测专业知识来实现。镜头检测是场景检测的前提，本文在充分调研目前 数字视频技术、视频分割技术的基础上提出了一种基于h s v 颜色空间的镜头新检 测方法；在计算机视频场景自动检测方面，本文首次将演化算法引入到视频场景 分割领域，产生了一种与现有方法完全不同的场景检测新技术。 本文提出的基于h s v 颜色空视频镜头检测算法，首先，把视频帧图像从r g b 颜色空间映射到h s v 颜色空间。然后，重新量化图像的h 与s 分量到1 2 7 个彩色 区域。最后，通过直方图方式计算图像的帧间相似性。同时，算法采取了有效的 虚假镜头分割分析机制，以减少图像快速变化的影响。实验结果表明，本算法不 仅具有较高的准确率、查全率和较快的处理速度，而且算法运行能克服光线变化 和运动的影响，因此在视频镜头分割领域具有一定的实用性，能很好与本文提出 的场景检测算法配合实现场景检测。 演化算法本质上是一种不依赖具体问题的直接搜索方法。通过自然选择、遗 传、变异等作用机制，实现提高各个个体的适应性。基于演化算法的视频场景检 测是一种全新的场景分割技术。本文在场景检测过程中，将每个镜头的分割点视 为一个基因，运用独特的基因编码方式、种群演化规则和个体评价机制，形成了 一种简单高效的视频场景分割方法。实验结果表明，该方法分割精度比较高，且 运行速度快，在场景分割应用上具有较强的技术实用性。 关键词：h s v 颜色空间；镜头检测；演化算法；场景分割 a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rv i d e ot e c h n o l o g y , i th a sb t 沁o m oaf o c u so f c o m p u t e rv i s i o nr e s e a r c ht om a k et h ec o m p u t e ru n d e r s t a n dt h ev i d e o sc o n t e n ls c e n e s e g m e n t a t i o ni st h ef i r s ts t e pt o w a r ds e m a n t i cu n d e r s t a n d i n go fv i d e o ，a n di t a l s o p r o v i d e st h ee f f e c t i v ea p p r o a c ht ob r o w s ea n di n d e xv i d e od a t a b a s e v i d e os c e n e s e g m e n t a t i o ni sd o n ea tah i g h e rl e v e l ，i tb a s e so nt h er e s u l to fv i d e os h o td e t e c t i o na n d k e yf la m e sa b s t r a c t i o n , i n t e g r a t e st h ep r o f e s s i o n a lk n o w l e d g eo f5 c e i ! ed e t e c t i o n s h o t - d e t e c t i o ni st h ep r e c o n d i t i o no fs c e n es e g m e n t a t i o n , o nt h eb a s i so ff u l l i n v e s t i g a t i o no nc u r r e n td i g i t a lv i d e oa n dv i d e os e g m e n t a t i o nt e c h n o l o g i e s ，t h i sp a p e r p r o p o s e das h o td e t e c t i o nm e t h o dw h i c hb a s e do nh s vc o l o rm o d e l ；i nc o m p u t e r s c e n ed e t e c t i o n , t h i sp a p e ra p p l i e st h ee v o l u t i o n a r ya l g o r i t h mt ot h ev i d e os c e n e s e g m e n t a t i o nf i e l d ，a n d f o r m san e ws c e n ed e t e c t i o nm e t h o dw h i c hi sc o m p l e t e l y d i f f e r e n tf r o mt h ec u r r e n t t h es h o td e t e c t i o nm e t h o dp r o p o s e db yt h i sp a p e rt r a n s f o r m st h ev i d e op i c t u r e sf r o m r g b s p a c et oh s vs p a c ef i r s t l y t h e nr e q u a n t i t a t et h eh a n dsc o m p o n e n t so fp i c t u r e s t o12 7c o l o ra r e a st oo v e r c o m et h ei n t e r f e r e n c ep r o d u c e db yi l h m a i n a t i o nc h a n g i n ga n d m o v e m e n t l a s t l yc o m p u t et h es i m i l a r i t yb e t w e e na d j a c e n tf l a m e sb yh i s t o g r a m f u r t h e rm o r e , i ta d o p t e dt h ef a l s e - s h o t - a n a l y s i sa p p r o a c ht ow e a k e nt h ei n t e r f e r e n c e b r o u g h tb yf a s tc h a n g eo fp i c t u r e s t h ee x p e r i m e n tr e s u l t ss h o wt h a tt h i sm e t h o dh a s h i g h e ra c c u r a c ya n dr e c a l lr a t i o ，a sw e l la sf a s t e rp r o c e s s i n gs p e e d a n di th a st h e s t r o n gp r a c t i c a b i l i t yi ns h o td e t e c t i o na p p l i c a t i o n i tc o o p e r a t e sw e l lw i t ht h e $ c 舄l l o s e g m e n t a t i o nm e t h o dp r o p o s e db yt h i sp a p e rt os e g m e n tt h ev i d e os c e n e i ne s s e n c e , e v o l u t i o n a r ya l g o r i t h mi sak i n do fd i r e c ts e a r c hm e t h o dw h i c hd on o t d e p e n do nt h es p e c i f i cp r o b l e m ，i ti m p r o v e st h ei n d i v i d u a l s a d a p t a b i l i t yb yt h e m e c h a n i s m ss u c ha sn a t u r a ls e l e c t i o n ，i n h e r i t a n c e , m u t a t i o n , e t c i ti sab r a n d - n 唧 a t t e m p tt oa p p l yt h ee v o l u t i o n a r ya l g o r i t h mt ot h ev i d e o 文? , e l l es e g m e n t a t i o nf i e l d 1 1 1 t h ep r o c e s so fs c e n es e g m e n t a t i o n , t h i sp a p e rv i e w st h ed i v i s i o np o i n t so fs h o t sa s g e n e s , u s e st h es p e c i a lg c n ec o d i n gn l o d e , p o p u l a t i o n se v o l v e m e n tr e g u l a t i o n sa n d i n d i v i d u a le v a l u a t i n gm e c h a n i s m t h ee x p e r i m e n tr e s u l t ss h o wt h a ti ti sas i m p l eb u t e f f i c i e n tv i d e os c e n cs e g m e n t a t i o nm e t h o d , a n di th a sh i g h e rf e a s i b i l i t yo fs c c i i e k e yw o r d s ：i - i s vc o l o rm o d e l , s h o td e t e c t i o n ，e a ，s c e n es e g m e n t a t i o n 厦门大学学位论文原刨性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成果。 本人在论文写作中参考的其他个人或集体的研究成果，均在文中以明 确方式标明。本人依法享有和承担由此论文产生的权利和责任 声明人( 签名) ：颉鸿瓦 彳年箩月2 , ge l 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大 学有权保留并向国家主管部门或其指定机构送交论文的纸质版和电子 版，有权将学位论文用于非赢利目的的少量复制并允许论文进入学校 图书馆被查阅，有权将学位论文的内容编入有关数据库进行检索，有 权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适用 本规定。 本学位论文属于 1 、保密() ，在年解密后适用本授权书。 2 、不保密() ( 请在以上相应括号内打“4 ) 作者签名：崮澎凤 导师签名：柳垮 日期：卯彭年乡月劈日 日期：知嘲矿车，月杉日 第一章绪论 1 1 研究的目的和意义 第一章绪论 视频场景检测研究课题隶属于国家“8 6 3 计划项目引入觉知机制的视 觉动态计算模型及其应用实现。此项目是依据人类视觉认知机理研究的新成果， 通过参考意识模型的有关成果，引入觉知机制，采用可资利用的各种神经计算模 型，来形成一种有意识的视觉感知动态计算模型，并具体应用于动态场景中人物 的自动监视。它主要研究内容包括觉知计算模块的构建与实现、有意识视觉感知 计算模型的建立和动态场景中人物自动监视应用。根据研究计划，本项目要在第 一年度形成初步的视频场景检测与定位系统平台。视频场景检测与定位是实现视 频内容结构化的必要步骤，而视频内容结构化是对海量的视频数据进行高效的计 算机处理，实现视频内容的索引、查找、分析、语义描述和压缩等的前提，因此 其研究具有重要的实际意义。 视频内容结构化就是对视频流中的连续帧序列进行切分，把一个连续视频流 按其内容展开的不同，将其分成若干语义段落单元n 1 。根据切分内容的粒度与层 次不同，切分可以按帧、镜头、场景来进行。若干帧图像组成镜头，若干个镜头 形成场景，最后由若干个场景组成一段有意义的视频流。场景是视频所蕴涵的高 层抽象概念和语义的表达，因此场景具有很强的视频表征能力。但由于视频题材 内容、表现手法和影视技术的形式多样，使得形成通用的场景构造方法极其困难。 用传统的完全手工的方法来分割视频，是一项枯燥又很耗时的工作，通常由 电影制片人完成。为了用自动的方法分割视频，目前按处理对象的不同可分为： 非压缩域内的镜头检测和压缩域内的镜头检测。非压缩域( 象素域) 镜头检测是针 对未经压缩的数字视频，或压缩视频解码后的帧图像。它可以利用帧图像的象素 域信息，直接进行各种图像处理，提取帧图像的特征向量来进行镜头检测。压缩 域的处理主要针对m p e g 压缩视频的。由于越来越多的视频数据是以m p e g 、h 2 6 x 压缩形式进行捕捉、传输和存储的，因而直接对压缩或半解压视频进行镜头检测 成为近年来研究的热点。 基于演化算法的视频场景分割 通过场景分割，生成涵盖了其最大语义内容的视频结构化信息。在视频内容 浏览、视频数据库索引、视频自动语义描述以及视频数据压缩等方面都有极其重 要的作用。用户通过互联网无线网访问视频信息时，也能极大节约网络带宽开销。 1 2 主要研究工作和创新点 1 2 1 主要研究工作 充分的调研是做好本课题的必要条件，针对本文课题的研究对像及目的一视 频及其结构化。本文主要做了以下工作： 1 研究了数字视频技术和视频结构化技术。对数字视频的概念、采集、转 换和编码作了充分的了解。详细地分析了现有的主流数字视频压缩技术， 如a v i 、j p e g 、m p e g - x 系列和h 2 6 x 系列等。对视频结构化概念、原 理和工作流程也进行详细的调查。 2 研究了目前的视频镜头检测技术与关键帧提取方法，分析了镜头检测的 困难与研究现状，以及目前各类典型镜头检测算法的原理、优劣性与适 应范围。在此基础上，本文提出了一种基于h s v 颜色空间的镜头检测算 法。并对关键帧提取方法也做了简要的分析。 3 研究了目前的视频场景分割方法，分析视频场景检测的困难与研究现状。 以目前各类典型场景分割算法为基础，提出了运用演化算法进行场景检 测的新方法。 4 最后设计了2 个实验项目检测本文所提出的方法。介绍了实验的环境、 实验数据与检验标准。并对实验结果进行了详细的分析。 1 2 2 本文的创新点 本文的创新点归纳如下： 1 在非压缩视频镜头检测方面，本文提出了一种基于h s v 颜色空间的镜头 检测方法。该方法将视频帧图像从r g b 颜色空间映射到h s v 颜色空间，再从帧 图像中提取h ( 色调) 、s ( 饱和度) 分量并重新量化。最后按照直方图方法进行 帧间相似性检测。该方法忽略了v ( 亮度) 分量，所以能避免光照变化的影响。 同时该方法对运动也具有较好的容忍度。 2 第一章绪论 2 在视频场景检测方面，本文将演化算法引入到场景检测中，提出了一种新 的场景分割方法。为了能让演化算法进行场景检测，该方法设计了一种长度与镜 头数量相当的个体编码方式，该方式不受场景数量变化的影响，并且能与场景分 割的顺序要求一致。为了能让优胜劣汰的演化机制发挥作用，该方法还设计了一 种场景分割方案评价算法。另外，在新方法中还采用了预处理措施以提高种群演 化速度。 3 基于演化算法的视频场景分割 第二章数字视频技术与视频结构化 数字视频( d i 舀t a jv i d e o ) 就是先用摄像机之类的视频捕捉设备，将外界影像 的颜色和亮度信息转变为离散的数字信号，再记录到储存介质( 如磁盘) 。通过 视频播放软件可以再现其影像信息。 数字视频的来源有很多，如来自于摄像机、录像机，影碟机等视频源的信号， 包括从家用级到专业级、广播级的多种素材。还有计算机软件生成的图形、图像 和连续的画面等。 2 1 视频数字化及其标准 2 1 1 视频采集 模拟视频信号的波形在时自j 和幅度上都是连续的为了把模拟波形转换成数 字信号，必须把这两个量转换成不连续的值。幅度表示成一个整数值，而时间表 示成一系列按时间轴等步长的整数距离值。把时间转换成离散值的过程称作为采 样，而把幅度转换成离散值的过程称为量化。这两个过程一起称为模拟一数字转 换( a i d ) 。由于连续的模拟信号籼转换后变成离散值，所以只能建立原始信号 的近似值。但如果选择的采样值、量化值比较合适，a d 转换就能以充分的精度完 成，以使近似误差由数字系统再现时不被观测出来。 根据奈奎斯特取样定型2 1 ：对于最大频率为f m 的信号f 【t ) ，当取样频率不低于 2 f m 时，由截止频率为f m 矩形低通滤波器可以从取样信号中完全恢复原信号。 采样过程是把模拟信号变成时间上离散的脉冲信号，量化的过程则是进行幅 度上的离散化处理。如果我们把最大的幅度分成2 5 6 级量化电平，就可对任一幅度 值赋予一个从0 到2 5 5 的值，每一个采样值都与适当的阈电平相匹配，这样就能赋 予相应的数值。然后这个数值就可以编码，如2 5 6 级量化就可用8 个二进制位表示， 也被叫做8 比特量化。这种简单的数字编码流被称为脉冲编码调制( p c m ) 。当然， 数字编码不只限于采用一系列线性量化值。 视频信号有不同的信号格式。对于大多数视频处理系统来讲，均以删3 1 ： 亮度信号，u 、v 分别表示两个色度信号，亦称y c r c b ，属于p a 分量格式分三路 4 第二章数字视频技术与视频结构化 进行模数转换，以其它信号格式送入的信号，都要先转换成y u v 分量格式，然后 再进行模数转换。由于视频信号的模数转换分成y 、u 、v 三个信号的单独转换， 这就又产生了一个采样格式的概念。采样格式指的是y 、u 、v 三个信号采样速率 的比值，目前有4 ：4 ：4 、4 ：2 ：2 、4 ：1 ：1 以及4 ：2 ：0 等几种采样速率都以y 分量为基准， u 、v 分量按比例进行。表2 1 例举了目前常用的两种速率1 3 5m h z 与1 4 7 5 m h z ， 它们应用的系统分别是p a lt i u r 6 0 1 标准和p a l 方形【4 1 。而对于量化，一般采用y 、 u 、v 信号各8 比特化的方式来进行。 表2 1 两种常见的视频采样速率 标准名称采样速率每行采样点图像大小 p a lm 瓜6 0 l1 3 5 m h z8 6 47 2 0 x5 7 6 儿方形1 4 7 5 m h z 9 4 4 7 6 8 x 5 7 6 模拟视频信号数字化后，数码率太高，数据量非常大。如果直接存储和传输 不但开销很大，而且有时设备也承受不了如此大的负荷。压缩编码以压缩信源数 码率为目的，尽量减少信源各符号的相关性，使信源的传输效率提高。 2 1 2 视频序列的时间码s m p t e s m p t e 口1 ( t h es o c i e t yo fm o t i o np i c t u r ea n dt e l e v i s i o ne n g i n e e r s ) 。它 是目前在影音工业中得到广泛应用的一个时间码概念。该码用于设备间驱动的时 间同步和计数方式。通常用时间码来识别和记录视频数据流中的每一帧，从一段 视频的起始帧到终止帧，其间的每一帧都有一个唯一的时间码地址。标准格式是： 小时：分钟：秒：帧( h o u r s ：m i n u t e s ：s e c o n d s ：f r a m e s ) 。一段长度为o o ：0 2 ：3 1 ： 1 5 的视频片断的播放时间为2 分钟3 1 秒1 5 帧，如果以每秒3 0 帧的速率播放， 则播放时间为2m i n3 1 5s 。 根据电影、录像和电视工业中使用的帧率的不同，各有其对应的s m p t e 标准。 常见有s m p t e 2 9 2 m ，s m p t e 2 5 9 m 。由于技术的原因，n t s c 制式实际使用的帧率是 2 9 9 7 帧秒而不是3 0 帧秒，因此在时间码和实际播放之间有o 1 的误差 为了解决这个误差问题，设计出丢帧( d r o p - f r a m e ) 格式，即在播放时每分钟要丢 5 基于演化算法的视频场景分割 2 帧( 实际上是使得有两帧不显示而不是将这两帧从文件中删除) ，这样可以保证 时间码与实际播放时间的一致。与丢帧格式对应的是不丢帧( n o n d r o p - f r a m e ) 格 式，它忽略时间码与实际播放帧之间的误差。 2 2 视频压缩 数字视频之所以能够被压缩，是因为在数字视频中存在着大量的冗余信息。 这些冗余信息有以下三种类型： 空间冗余度：这是由于相邻像素之间的相关性造成的。 频谱冗余度：这是由于不同彩色平面之间的相关性造成的。 时间冗余度：这是由于数字视频中不同帧之间的相关性造成的。 另外压缩编码还有一个重要依据，就是显示数字视频时，为收看者显示他们 眼睛不能辨别的多余信息是没有必要的。 压缩方案可利用冗余度的任一方面或所有方面，其目的是通过去掉这些冗余 度来减少表示数字视频的数据量。图像压缩有许多方法，但这些方法基本可分成 两类，即无损压缩和有损压缩。在无损压缩中，当数据被压缩之后再进行解压， 得到的重现图像与原始图像完全相同。显然，无损压缩是理想的，因为不丢失任 何信息。但是对于数字视频来说，其压缩的效果通常很小，并不适用。在有损压 缩中，解压后得到的重现图像相对于原始图像产生了误差，质量降低了，但有损 压缩所引起的误差可以说是很细微的，人眼不足以发现这种差别。有损压缩可提 供更高的压缩比，因此在视频处理中得到了广泛应用。 2 2 1 视频压缩理论 1 9 5 9 年s h a n n o n 创立的信息率失真理论奠定了信息编码的理论基础。此后， 视频图像压缩编码理论和方法都有很大的发展，主要有预测编码、交换编码、统 计编码三大经典编码方法f 5 】。预测编码的基本思想是：根据数据的统计特性得到 预测值，然后传输图像像素与其预测值的差值信号，使传输的码率降低，达到压 缩的目的。变换编码的基本思想是：由于数字图像像素问存在高度相关性，因此 可以进行某种变换来消除这种相关性。变换编码不直接对空域图像像素编码，而 是先将它变换到频域，得到一组变换系数。虽然变换并不对数据进行压缩，但经 6 第二章数宁视频技术与视频结构化 过变换后，能量相对集中，通过后续的量化、编码就能达到压缩的目的。变换编 码方法中的离散余弦变换( dct ) 和小波变换( w a v e l e t ) 在视频图像压缩中得 到了广泛应用。统计编码的基本思想是：根据信息码字出现概率的分布特征而进 行压缩编码，寻找概率与码字长度间的最优匹配。统计编码主要针对无记忆信源， 它又可分为定长码和变长码( v l c ) ，h u f f m a n 编码和算术编码是两种常见的变长 码字编码方法。 2 0 世纪8 0 年代后期以来，一种基于d c t 变换和运动补偿的混合编码方案在 视频压缩中得到了广泛应用，并逐步形成了一系列国际标准，如h 2 6 x 和m p e g x 等。这些标准都有相似的编码原理，它们都将图像看成是二维波形，利用d c t 变换消除图像空间域上的冗余，以运动估计与运动补偿消除运动图像时间域上的 冗余，从而达到压缩数据的目的。 2 2 2 常见视频压缩编码标准 目前，常用的压缩编码技术有微软的a v i 和国际标准化组织推荐的j p e g 、 h 2 6 x 和m p e g 。 a v i ( a u d i ov i d e oi n t e r l e a v e d ) 即音频视频交错格式砸1 。是将语音和影像同 步组合在一起的文件格式。它于1 9 9 2 年被m i c r o s o f t 公司推出，随w i n d o w s 3 1 一起被人们所认识和熟知。a v i 的出现宣告了p c 上哑片时代的结束，a v i 格式代 表了多媒体在p c 上的兴起。它对视频文件采用了一种有损压缩方式，但压缩比较 高。这种视频格式的优点是图像质量好，可以跨多个平台使用，其缺点是体积过 于庞大，而且更加糟糕的是压缩标准不统一尽管如此，但由于a v i 本身的开放 性，获得了众多编码技术研发商的支持，不同的编码使得a v i 不断被完善，现在 几乎所有运行在p c 上的通用视频编辑系统都是以支持a v i 为主的，因此其应用范 围仍然非常广泛。 j p e g ( t h ej o i n tp h o t o g r a p h i ce x p e r t sg r o u p ) 是用于静态图像压缩的标 准h 1 。其主要方法包括两部分：一是基于d p c m ( 空间线性预测) 技术的无失真编码， 一是基于d c t ( 离散余弦变换) 和哈夫曼编码的有失真算法。前者图像压缩无失真， 但是压缩比很小，目前主要应用的是后一种算法，图像有损失但压缩比很大，压 缩2 0 倍左右时基本看不出失真。j p e g 虽是静止图像的压缩编码标准，但其算法 7 基于演化算法的视频场景分割 已经由硬件实现，可以实现对视频图像的实时压缩和解压缩，因此形成了 m o t i o n - j p e g 压缩方式。现在，用于电视非线性编辑处理的视频卡，采用的基本 都是m o t i o n - j p e g 压缩方式。这种方式对活动的视频图像通过实时帧内编码单独 地压缩每一帧，因此在编辑过程中可随机编辑任意帧，而与其它帧不相关这对 于以帧为精度的后期编辑处理来讲是非常重要的。不过经m o t i o n - j p e g 压缩后的 数字视频，容量仍很可观，它的重放再现必须由专门的硬件来处理。 h 2 6 x 是由国际电信联盟i t u ( 前称国际电报电话咨询委员会c c i ，i i ，r ) 制定的 嘲。该标准家簇主要有h 2 6 1 ( 制定时间：1 9 9 0 年1 2 月) h 2 6 3 ( $ q 定时问：1 9 9 5 ) 和h 2 6 4 ( 制定时间：2 0 0 3 年3 月) 。它首创的基于运动估计与补偿的帧间压缩模 式比起基于帧内压缩的j p e g 具有更高的压缩比。它的最初目的是为了在速率为p 6 4 kb it s s ( p = l 一- - 3 0 ) 的信道上传输可视电话与会议电视。这个标准草案对以 后同类标准的发展产生了深远的影响。u 2 6 4 是迄今为止最先进视频压缩标准。 m p e g ( m o t i o np i c t u r e se x p e r t sg r o u p ) 是专门用来处理运动图像的标准h 刀。 目前m p e g 在计算机和民用电视领域获得广泛使用，如v c d 影碟机。m p e g 压缩算 法的核心是处理帧间冗余以大幅度的压缩数据，它依赖两项基本技术，一是基于 1 6x1 6 块的运动补偿，二是j p e g 帧内压缩。在整个处理过程中，还要有一个标 准，也就是一个仅采取j p e g 压缩处理的说明参考帧，这样才能将那些只存储了变 化信息的帧还原出原始图像。由于m p e g 压缩形成的数字视频不具有帧的定位功 能，因此无法对帧进行编辑处理。在视频制作过程中，往往是非线性编辑系统先 采用通用格式如a v i 进行编辑，最后再转换成m p e g 文件。 m p e g 的帧间编辑采用三种方式，有i 帧、p 帧和b 帧。i 帧就是说明参考帧， 作为其它帧的基准。p 帧是预测帧，它是根据当前帧的变化预测出的帧。b 帧是双 向预测帧，它根据前后的i 帧和p 帧或p 帧和p 帧双向预测产生的。i 帧、p 帧和 b 帧之间的时间间隔，可根据被压缩视频的复杂程度以及所要求的质量综合考虑， 它决定了压缩比的大小。v c d 采用的是m p e g - 1 算法，能将数字视频信号压缩到 1 1 5 m b s ，达到约1 4 0 ：1 的压缩比。 m p e g 家簇呻1 ，按不同的用途主要有：m p e g - 1 ( 1 9 9 3 年8 月) 、m p e g 一2 ( 1 9 9 4 年 1 1 月) 、m p e g - 4 ( 1 9 9 9 年2 月) 、m p e g - 7 ( 2 0 0 1 年9 月) 和m p e g - 2 1 ( 制定过程中) m p e g - i 能将图像和伴音的总码率压缩到1 s m b s ，应用于象v c d 这样对图像质量 8 第二二章数字视频技术与视频结构化 要求不太高的领域；m p e g - 2 是针对能提供广播级质量要求的编码标准，目前已用 于d v d 、高清晰度电视等领域；m p e g - 4 主要应用于交互式多媒体的节目制作，网 上视频传输，交互式移动多媒体，数字视频监控等诸多领域；m p e 6 - 7 主要应用在 数字图书馆( 如图像目录、音乐字典) ，多媒体名录服务( 如网页) ，广播媒体 选择( 如无线电信道、t v 信道) ，多媒体编辑( 个人电子新闻业务，媒体写作) 等领域。 此外还有一些其它标准，如r e a lv i d e o 、q u i c k t i m e 等它们主要由一些公 司针对自己的产品研发出来的标准。 表2 2 列出了几种常用编解码技术及其对应的视频文件格式【7 1 。表2 3 是几 种常见的视频文件格式应用情况介绍阳】 表2 2 常用编解码技术及其对应格式对照表 编解码技术对应的视频文件格式 m e p g l m p g ，m lv ，r o p e ，m p e g ，d a t m e p g 一2 m p g ，r o p e tm p e g ，m 2 v ，v o b m e p g 一4 h 2 6 4 a s f 、m o v 、a v i r e a l m e d i ar 、r m v b w i n d o w sm e d i a- 田v 、a s f q u i c k t i m e v f l v s w f 、f l a 表2 3 常见的视频文件格式 文件后缀播放软件 特点 适用范围 名 w i n d o w sm e d i a 将视频和音频信号混合，存储在一 w i n d o w s 操作 奉a v i p l a y e r起，它是一种有损的压缩算法。 系统中 q u i c kt i m ef o r 压缩率高，有损的压缩算法，视频 幸i o v网络环境 w i n d o w s 质量较好，支持在线播放。 流格式，支持在线播放；压缩率可 控制；播放是可根据数据传输速率网络环境中大 t 珥r e a lp l a y e r 自适应的调整播放效果( 既支持恒数据量的视频 定速度的传输和变速传输) ； 9 基于演化算法的视频场景分割 标准化组织提供的压缩算法；不同 m p e g m e d i ap l a y e r的版本压缩率不同，视频质量也不 同： 木d a tm e di ap l a y e r 基丁肝e g 标准 v c d 2 3 视频结构化 对于具有一定故事情节的视频数据，它们是由存在时间上依赖的图像帧序列 流组成的。所谓时问依赖是指：要想欣赏某个情节，在现有技术下，就必须先顺 序地浏览这个情节前面的全部视频内容，或快速越过前面的视频内容，然后丌始 欣赏某个故事情节，而不能通过检索标注手段快速到达这个情节所位于的特定的 视频单元。 其实，视频数据流的一个重要特点就是它有很强的情节发展性，导演在拍摄 中常用到“分场景 和“分镜头一之类的概念，如拍摄“飞机起飞 的分镜头和 拍摄“汽车爆炸”的“分场景”。得到不同的镜头和场景后，视频数据进入后期 制作，导演或创作人员将先期拍摄得到的“分镜头 和“分场景”组合起来，就 是观众最后看到的视频录像。 视频节目制作中其实是存在镜头和场景等内容层次的，但是这些结构层次在 最后节目中消失了，这弱化了人们对视频数据进行欣赏尤其是管理的功能。如果 能够自动分析出视频数据流中所蕴含的结构，也就是说对视频数据流进行结构化。 通过这些结构来对视频流建立索引，这样可以帮助用户更好地了解视频内容。 通常在文本检索中，会用单词和短语作为语句、段落或者文献的索引。类似地， 在视频系统中，需要用视频流中的一些主要图像( 关键帧) 或者图像序列( 帧序列) 来索引部分场景或者整个视频，使视频用户可以使用这些索引结构快速浏览或检 索视频内容。使用关键帧为视频建立索引有几个好处：( 1 ) 可以更方便对视频进行 表征。使用若干关键帧对视频流进行表征，与使用几百或更多图像来表征视频数 据流相比，可以极大地简化视频流的表示。( 2 ) 有效地比较视频之间是否相似。可 以通过比较视频流的关键帧之间的是否相似，来达到判断视频是否相似的目的。 然而，找寻视频流中的关键帧，对视频进行索引，实现视频流的表征与相似 度衡量，这种过程需要建立在切分有意义的视频段的基础上，即视频结构化。视 1 0 第二章数字视频技术吁视频结构化 频结构化过程即是对视频流中的连续帧序列进行切分，把一个连续的视频流按其 内容展开的不同，将它分成若干语义段落单元。视频流的结构化方法能够从一部 很长的视频中抽象出视频内部隐含的情节发展结构，它为大数据量视频的导航和 浏览提供了一种非常好的手段。由于视频流是由成千上万个图像帧组成，要为每 一帧图像建立关于图像底层特征的索引，在时问和空间上效率都很低，也没有必 要。而且，用户对视频进行检索和浏览时，往往也不需要看整个视频流。所以， 在视频结构化过程中，将整个视频划分为若干级的层次结构一般来说，在视频 结构化过程中，可以把连续视频流分割成包括镜头、组和场景等视频单元，这里 先引入一些基本的定义： ( 1 ) 帧( f r a m e ) ：帧是视频流中的基本组成单元，每一帧均可看成一个独立的 图像，视频流数据就是由连续图像帧构成的，在p a l 视频格式中，视频帧采样率 为2 5 帧秒，n t s c 制式中，视频采样率为3 0 帧秒。 ( 2 ) 镜头( s h o t ) ：摄像机拍下的不问断帧序列，是视频数据流进一步结构化的 基础结构层。一般来讲，同一组镜头中，视频帧的图像特征保持稳定。如在拍摄 “飞机起飞这组镜头时，画面的色彩和纹理等图像特征将保持不变。镜头是对 视频流进行处理的最小物理单元，而视频帧是视频流的基本单元，它蕴涵了少许 的语义内容。由于在同一组镜头中，属于同一组镜头的图像帧之间的特征保持稳 定。如果相邻图像帧之间的特征发生了明显变化，则认为发生了镜头变化，需要 对视频数据进行切分。对视频数据流进行结构化时，首先要找出每个独立的镜头 单元，一组组独立的镜头单元就构成了视频数据流。 ( 3 ) 关键帧( k e y f r a m e ) ：关键帧是可以用来代表镜头内容的图像。在切分出 来镜头结构后，关键帧被用来代表各镜头的特征，进行进一步的结构化。在一组 视频镜头中，一般关键帧数目远远小于镜头所包含的图像帧数目，如对于3 秒长、 采样率为3 0 帧秒的一组视频镜头，其最简单的关键帧提取方法是把这个镜头的 第一帧和最后一帧作为关键帧，所以这个镜头就使用首尾两幅图像帧来进行表示， 与其所包含的9 0 个图像帧相比，使用关键帧表示这个视频镜头显得十分简单和有 效。 ( 4 ) 场景( s c e n e ) ：语义上相关和时间上相邻的若干组镜头组成了一个场景， 场景是视频所蕴涵的高层抽象概念和语义的表达。如，“学校运动会一这个场景 基于演化算法的视频场景分割 可以由“运动员入场 、“运动员比赛和“观众呐喊 等若干镜头组成，虽然 每个镜头所代表的语义不多，但是若干镜头所组合成的场景就表达了一个符合人 们思维比较丰富的语义。由于镜头是由关键帧组成的，所以场景可以使用属于这 个场景的若干镜头所对应的关键帧表示。这里没有使用文字信息来标注场景，而 是使用关键帧( 本质上是视觉信息) 来标注镜头与场景，因为不同人对同一场景的 文字标注是不一样的。 ( 5 ) 组( g r o u p ) ：组是介于物理镜头和语义场景之问的结构。例如：一段采访 录像，镜头在主持人与被采访者之间频繁切换，整个采访属于一个场景，而那些 关于主持人的所有镜头属于一组，关于被采访者的所有镜头属于另一组。 视频场景一 视频组 视频镜头一 视频关键帧 图2 1 视频结构化流程 图2 1 显示了按照上面定义对视频数据流进行结构化的过程：连续的视频 图像帧通过视频镜头边缘检测被分割成长短不一的镜头单元；然后对每个镜头 单元提取关键帧，得到可以表征每个镜头单元的关键帧。要注意，由于每个镜 头长短不一，所以可以提取的关键帧数目也不一样。接着分析视频关键帧，得到 视频组；最后在视频组的基础上，得到视频场景。在这个结构化过程中，就得到 了视频目录，用它来作为原始的无结构视频数据流的索引。 1 2 第二章数! 声视频技术与视频结构化 从图2 1 中可以明确知道，视频结构化过程中镜头单元检测、关键帧提取和 视频场景构造是结构化视频的主要任务，后续部分将分别介绍这些内容。 1 3 基于演化算法的视频场景分割 第三章视频镜头分割与关键帧提取 镜头是指由个摄像机镜头连续拍摄的一组内在相关的连续帧，它用来表现 在时空上连续的一组运动。通常，一段视频节目往往由若干个镜头编辑加工而成， 而视频镜头分割就是要对一段已经合成好的视频节目，切分成一个个独立镜头。 镜头分割是视频处理的第一步，是随后的高层内容分析、分类、索引和查询的基 础。镜头分割的准确性将直接影响到后续处理的效果。因此，视频镜头的分割算 法，从一开始就得到广泛的重视，它在基于内容的视频分析和检索中有着最长的 研究历史和最丰富的研究成果。然而直到今天，仍然没有在各种情况下都能表现 出良好性能的算法。 一般来说，同一组镜头中视频帧的图像特征保持稳定，如果相邻两帧的特征 发生了明显的变化，则认为发生了镜头切变。由于镜头切变形式的多样性与镜头 内容的特殊性，使得镜头检测存在一定的难度。 3 1 镜头分割面临的困难 1 4 镜头分割的效果受较多因素的影响，主要有以下几种： ( 1 ) 镜头切换形式 镜头切换是指一段连续视频图像序列变换到另一段连续视频图像序列。 它对镜头边缘的检测影响最大。一般在视频的后期编辑制作中，为了将多个 来自不同地点、不同时间以及不同拍摄角度的镜头有机的组织起来，往往要 运用镜头切换。例如一部2 小时的电影通常由数百个镜头组成。镜头之间的 切换形式主要有突变( a b r u p tt r a n s i t i o n ) 和渐变( g r a a 岫lt r a n s i t i o n ) 两大类。渐变 又可分为隐现( d i s s o l v e ) ，淡入淡出( f a d e ) 和擦除( w i p e ) 等不同类型。 表3 1 列出最常用的一些镜头切换形式f 。 表3 1 常见的十种镜头变换 效果描述 切变( c u t ) 前一镜头的尾帧被下一镜头的首帧快速代替 第三章视频镜头分割与关键帧提取 淡入淡出 某镜头的尾帧缓慢而均匀地变黑直至全部消失( 谈出) ，或某 ( f a d ei n f a d eo u t ) 镜头的首帧缓慢而均匀地从黑屏中出现( 淡入) 叠化( d i s s o l v e )前一镜头的尾帧缓慢而均匀地变成下一镜头的首帧 翻页( p a g et r a n s l a t e ) 前一镜头的尾帧从屏幕一边拉出，并逐渐显露出下一镜头的 首帧 拉进( s l i d e )下一镜头的首帧从屏幕一边或一角平稳地拉进，同时前一镜 头的尾帧从另一边或一角拉山 滑入( w i p e ) 下一镜头的首帧逐渐穿过并覆盖前一镜头的尾帧 弹进弹出某镜头的首帧立即从屏幕中出现或某镜头的尾帧立即从屏 ( p o po n p o po f f ) 幕中消失 上拉下拉下一镜头的首帧如窗帘一样从屏幕项部拉f ，运蔽前一镜头 ( p u l lu p p u l ld o w n )的尾帧 翻转( f l i p ) 前一镜头的尾帧翻转，在另一面显示下一镜头的首帧 旋转( s p i n ) 下一镜头的首帧以旋转方式出现并覆盖前一镜头的尾- 跌 镜头的切换形式，往往模糊了镜头的边界，给镜头边界检测制造了困难。 实际中还有一些应用较少的切换形式如“破裂一、。波纹”、“变形 等。此外， 当镜头变换伴随物体运动时，情况将更为复杂。 ( 2 ) 视频的质量 视频的清晰程度也会影响到镜头边界的检测。如果视频不够清晰，则无 法得到正确反应视频帧图像的特征。镜头边界检测往往是通过分析相邻帧问 的图像特征来进行的。因此视频图像中的几何形状失真、马赛克、斑点以及 其它形式噪音都会对镜头边界检测形成障碍。 ( 3 ) 视频题材 视频题材种类繁多，有新闻、体育、综艺、生活、战斗，功夫等。由于 题材不一样，帧图像内对像变化速度也不一样。其中新闻、综艺、生活片等 相邻帧图像变化较缓，而体育、战斗、功夫片等则较快。现在，有许多算法 是通过设定相邻帧间阈值来检测镜头边界的因此对于这种算法，将很难设 置一个通用的阈值来检测所有视频。而且即使是确定了题材的视频，也会有 l s 基于演化算法的视频场景分割 这种帧图像变化速度不一致的情况出现，因此镜头边界检测变得更困难。 3 2 镜头分割研究现状 目前镜头检测方法朝着两个方向进行。一种是在压缩域内进行检测，它不需 要解码还原视频信号，而是直接读取视频文件的压缩编码信息，因而能大大的降 低计算复杂度。a r m a n 1 等人提出的用关键帧( i 帧) 的i ) c t 系数来探测场景变化的技 术。z h a n g n