（计算机应用技术专业论文）基于内容的视频分割与检索技术研究.pdf

长奋t 业，i 学硕j 学位论史 摘要 随着计算机多媒体技术的发展和多媒体信息处理需求的不断增长，基于内容的视 频检索技术c b v r ( c o n t e n t - b a s e dv i d e or e t r i e v a l ) 越来越受到人们的广泛关注，相 关的视频处理研究成为当前一个重要的研究领域。 视频数据可用幕、场景、镜头、帧等描述。视频分割的一般做法是基于帧的分割， 其任务主要集中于镜头( s h o t ) 边界检测，从而将视频在时间轴上分成镜头的集合。镜 头分割是视频处理的第一步，是随后的高层语义分析、分类、索引和检索的基础，其准 确性将直接影响到后续处理的结果。镜头边界检测的关键是找到图像帧之间的差别， 并在此基础上提取出关键帧和运动信息以供浏览和检索之用。 视频检索就是要从大量的视频数据中找到所需的视频片断，传统的视频检索只能 通过快进和快退等顺序的方法人工查找，因而是一件非常繁琐耗时的工作，这显然已 无法满足多媒体数据库的要求。用户往往希望只要给出例子或特征描述，系统就能自 动地找到所需的视频片断点，从而实现基于内容的视频检索。 本文首先介绍了基于内容的视频分割与检索的一般理论和一些典型算法，然后提 出了一个新的视频分割和检索系统的概要描述模型，通过该模型可以指导各种层次化 的视频数据的处理。接着通过对压缩域视频数据的研究，本文提出了一个多模式快速 镜头边界检测算法，用以在基于m p e g 标准的视频流数据上进行快速的镜头分割。之后 本文讨论了视频数据的特征提取、描述与检索的一般理论与方法，最后对本文的理论 算法进行了实验验证与性能评价。 关键词：视频检索镜头边界检测层次化描述关键帧提取 k 备工业大学形! i 学位论文 a b s t r a c t a l o n gw i t ht h ed e v e l o p m e n to fc o m p u t e rm u l t i m e d i at e c h n o l o g ya n dt h eg r o w i n g d e m a n df o rm u l t i m e d i ai n f o r m a t i o np r o c e s s i n g ，p e o p l ea r eg e t t i n gm o r ea n dm o r ea t t e n t i o n a b o u tc b v r ( c o n t e n t b a s e dv i d e or e t r i e v a l ) t e c h n o l o g y r e s e a r c hr e l a t e dt ov i d e op r o c e s s i n g h a sb e c o m ea l li m p o r t a n tf i e l do fs t u d y v i d e od a t ac a l lb ed e s e r i p t e db ya c t ，$ c c t i _ e ，s h o ta n df r a m e t h et r a d i t i o n a lv i d e o s e g m e n t a t i o nm e t h o di sb a s e do nf r a n l ep r o c e s s i n g ，w h i c h i sf o c u s e do nt h es h o t - b o u n d a r y d e t e c t i o n , s ov i d e od a t ac a nb ed i v i d e d i n t oan u m b e ro fs h o t s s h o ts e g m e n t a t i o ni st h e f i r s ts t e pi nv i d e op r o c e s s i n g ，w h i c hi st h eb a s i so ff o l l o w i n gh i g h l e v e ls e m a n t i ca n a l y s i s ， c l a s s i f i c a t i o n ，i n d e x i n g a n dr e t r i e v a l t h ea c c u r a c yo fv i d e os e g m e n t a t i o nh a sag r e a t i n f l u e n c eo i lt h ef o l l o w - u pp r o c e s s i n gr e s u l t s t h ek e yo fs h o t - b o u n d a r yd e t e c t i o ni st of i n d t h ed i f f e r e n c e sb e t w e e ni m a g e s ，a n dt h e ne x t r a c t i n gt h ek e y f r a m e sa n dm o t i o ni n f o r m a t i o n f o rb r o w s i n ga n dr e t r i e v i n g t h er e c a l l so fv i d e or e t r i e v a li st of i n dt h en e e d e dv i d e of r a g m e n tf r o mt h el a r g e n u m b e ro f v i d e od a t a t h et r a d i t i o n a lv i d e or e t r i e v a li sb a s e do nt h em a n u a ls e a r c h ，s oi ti sa v e r yt e d i o u sa n dt i m e - c o n s u m i n gw o r k , w h i c hi so b v i o u s l yu n a b l et om e e tt h ed e m a n d so f m u l t i m e d i ad a t a b a s e u s e r su s u a l l yw a n tt og i v e se x a m p l e so rf e a t u r e sd e s c r i p t i o n ，t h e s y s t e mw i l la u t o m a t i c a l l yf m d t h ew a n t e dv i d e os e g m e n t a t i o n ，w h i c hi sc a l l e dc o n t e n t - b a s e d v i d e or e t r i e v a l f i r s to fa l l ，t h i sp a p e ri n t r o d u c e st h eg e n e r a lt h e o r ya n ds o m et y p i c a la l g o r i t h mo f v i d e os e g m e n t a t i o na n dc o n t e n t - b a s e dv i d e or e t r i e v a l ，t h e np r o p o s e dan e wd e s c r i p t i o n m o d e lo ft h ev i d e os e g m e n t a t i o na n dr e t r i e v a ls y s t e m ，w h i c hi st h eb a s i so fv a r i o u s h i e r a r c h i c a lv i d e od a t ap r o c e s s i n g f o rc o m p r e s s e dv i d e od a t ar e s e a r c h ，t h i sp a p e rp r e s e n t sa n e wm u l t i m o d a lf a s ts h o t - b o u n d a r yd e t e c t i o na l g o r i t h m ，w h i c hi sa p p r o p r i a t ef o rm p e g s t a n d a r d sb a s e dv i d e od a t as e g m e n t a t i o n t h i sp a p e rd i s c u s s e st h eg e n e r a lt h e o r ya n d m e t h o d so fv i d e od a t af e a t u r ee x t r a c t i o n ，r e t r i e v a la n dd e s c r i p t i o n ，f i n a l l y ，e x p e r i m e n t a l v e r i f i c a t i o na n dp e r f o r m a n c ee v a l u a t i o ni sp r o v i d e d k e yw o r d s ：v i d e or e t r i e v a l s h o t - b o u n d a r yd e t e c t i o n h i e r a r c h i c a ld e s c r i p t i o n k e y f f a m e e x t r a c t i o n i i 【：备t 业人学坝j 学位论文 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作 所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经 发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本声明的法律结果由本人承担。 论文作者签名：乌枣旋 + ：，一，z 日期： 妒7 年争月2 日 l ：备t 业人学倾i 学位论上 1 1 研究背景及应用领域 1 1 1 研究背景 第一章综述 随着信息时代的到来，特别是计算机技术和网络技术的发展，海量的信息在全球被 采集、传输、流通和应用。在这些信息中最大量的就是视觉信息，这对我们管理视觉信 息的方法提出了更高的要求。视觉信息有其自身的特点，那就是数据量大，抽象程度低， 所以视觉信息膨胀带来的问题也非常严重。很多领域由于对大量的视觉信息无法有效 的处理而使采集的视觉信息闲置。由于越来越多的视觉信息数据库的建立和人们对视 觉信息越来越多的需求，视觉信息的描述和检索已经成为了当今研究的热点，如何有效 的描述视觉信息、如何实现基于内容的信息分割与检索等一系列问题成为多媒体信息 领域研究的重点。 传统视频信息检索系统是通过访问字符串文本的方式查询视频信息，其优点是简 单、快速。但是由于系统采用单纯基于文本的方式，有其自身难以解决的问题，这主要 体现在以下几个方面： ( 1 )在传统视频检索系统中，描述的模糊性是其自身难以克服的先天不足。因为 视频信息内容的丰富性决定了很难用文本语言准确、完整的描述视频信息的全部内容， 这就使得对视频信息的描述存在很大的模糊性，大大影响了检索结果的准确性。 ( 2 )文字描述是对视频信息的一种特定的抽象，这就要求描述方法要符合一定的 标准，这也就增加了文字描述的不确定性，因为如果描述标准改变了，那么视频描述也 得重新制作才能适应新的查询要求，也就是特定的描述只符合特定的查询要求。 ( 3 )随着人们对信息依赖性的加强，人们对视频资料中包含的具体信息的需求也 越来越多。传统的对视频的描述都是通过手工注释完成的，所以说如果采用传统的描述 方式，那么越来越多的重复劳动是不可避免的，这样不仅浪费了大量的人力、物力，而且 观察者在疲劳的状态下工作的准确性也会大大降低。 ( 4 )由于文字描述都是通过观察者选定后加在视频标注上的，因此视频描述很大 程度上受到主观因素的影响，不同的观察者或同一个观察者在不同的条件下对同一幅 图像会给出不同的描述，有时这种差异会很大。因而传统的描述方法不够客观，在没有 统一标准的时候有可能会自相矛盾。 2 0 世纪9 0 年代初，随着大规模数字图像库和视频库的出现，基于内容的视频检 k 弁t 业，、学坝l 学位论文 索( c o n t e n t b a s e dv i d e or e t r i e v a l ) 应运而生，c b v r 技术能够自动提取图像的色彩、 纹理、形状、区域等视觉内容特征，以视频视觉特征或与视频相似的草图、范例作为 用户查询和系统检索的依据，克服了传统检索方式的局限性，所以新一代基于内容的 视频分割与检索系统正在被人们广泛的研究并实际应用。基于内容的视频分割与检索 就是指根据视频的内容及上下文关系，对大规模视频数据库中的视频数据进行分类和 检索。它提供这样一种管理方式，在视频描述端，由计算机自动分割并提取描述视频信 息的低级语义描述子，而后由观察者加入高级语义的文本描述。在检索端，新一代的检 索系统在文本检索的基础上融合了图像理解、模式识别、计算机视觉等相关技术，为使 用者提供了丰富灵活的检索方式，其主要特点如下： ( 1 )基于内容的检索突破了传统的基于文本检索的局限，它直接对视频数据库中 的图像、视频、音频内容进行分析，抽取特征和语义。对视频信息的描述更加具体、客 观和全面。利用这些内容特征建立索引进行检索准确率会大大提高。 ( 2 )在基于内容的视频检索系统中采用了许多低级语义描述子。低级描述子的特 点之一就是可以由计算机自动提取，这就省去了从大量数据中标识对象的重复劳动，同 时也极大程度的降低了文本描述信息中的主观性，大大提高了检索结果的准确性。 ( 3 )大量的描述子使基于内容的检索可以是一种近似的匹配。由于对内容的表示 不是一种精确描述，因此基于内容的检索采用相似性匹配的方法逐步求精，以获得查询 结果，即不断减小查询结果的范围，直到定位于要查找的目标。这是一个迭代过程，这与 常规数据库检索的精确匹配法不同。 ( 4 )基于内容的视频信息检索为我们提供了更多的视频内在信息，比如视频段的 运动活动性、摄像机运动方式或者是关键帧的主颜色、纹理特征等重要信息，并且这些 信息都可以作为视频信息的特征值进行匹配查询。 ( 5 )基于内容的视频信息检索为我们提供了多样灵活的检索方式。我们既可以输 入一段有关日出的视频或是一幅有关日出的图像来查找视频数据库中与日出相关的视 频信息，也可以通过一幅手工画出的日出草图对视频数据库中的视频信息进行查询，这 些查询方式在传统的检索系统中是无法想象的。 1 1 2 应用领域 基于内容的多媒体检索技术的日益成熟不仅将创造出巨大的社会价值而且将改变 人们的生活方式。因为它与传统数据库技术相结合可以方便地实现海量多媒体数据的 存储和管理，与传统w e b 搜索引擎技术相结合，它可以用来检索h t m l 网页中丰富的多 媒体信息。在可预见的将来基于内容的多媒体检索技术将会在以下领域中得到广泛应 用： k 存t 业，：学彤! 。学位论文 多媒体数据库 木知识产权保护 术数字图书馆 木网络多媒体搜索引擎 木遥感和地球资源管理 木医学影像 半交互电视 木天气预报系统 木军事指挥系统 丰艺术收藏和博物馆管理 木零售业 木时尚和装饰设计 书法律的实施和罪犯调查等等 这里举一个具体的例子，网上零售服装目录可以允许用户通过传统的方式进行查 询如样式、价格范围等等，也可以允许用户通过图像属性进行查询如颜色、纹理等等。 这样，用户可以在一个特定价格范围内找到合适的衬衫，如合适的颜色和花样。同样 时装设计师也可以使用这样一个数据库，它包含了织物样本、图案、设计草图以及实 际服装外表的图片，设计师可以随心所欲的进行检索和查看，以便自己的创造性设计。 多媒体信息检索是信息检索与服务的重要内容，基于内容检索技术大规模网络化 是多媒体信息检索的关键。随着电子出版物、网络化信息资源的普及利用，基于内容检 索技术的应用将会越来越普遍。 1 2 研究的发展与现状 1 2 1 当前基于内容的视频分割技术研究动态 视频分割是视频分析的首要问题，主要研究如何获得进行视频分析处理的基本单 元。目前的视频分割研究分为视频时域分割和视频对象的分割。视频时域分割主要集 中于镜头( s h o t ) 边缘检测，将视频在时间轴上分成镜头的集合。视频对象的分割是从视 频序列中分割出有语义意义的对象，即更具有实际意义和使用价值的信息。 1 视频时域分割 虽然视频时域分割的研究取得了很大的进展，但是现有的分割算法仍然存在准确 性、可靠性、实时性、通用性等问题。采用颜色直方图、边缘、运动和统计等方法进 行的突变检测算法已经日趋成熟，目前的研究在于提出了许多改进算法。典型的改进算 k 奋t 业大学形! i 学位论文 法有以下几种： ( 1 ) v a s c o n c e l o s 和l i p p m a n 2 3 提出的在贝叶斯方程的基础上自适应设置阈值的 方法。实验证明，此方法比通常使用的固定阈值法有更好的检测效果。 ( 2 ) l e e 2 4 提出的基于特征的快速突变检测算法。通过直接从m p e g 视频的d c t 系 数提取边缘特征，检测速度可与d c 序列帧差突变切换检测相比。 ( 3 ) n a n g 2 5 提出的把相邻b 帧的宏块关系加入突变切换检测的方法。利用相邻b 帧的宏块关系来衡量两帧的相似性。这种方法比利用帧的向前和向后的运动矢量数比 的方法有更强的健壮性。 ( 4 ) h u a 2 6 提出的变步长方法。这种方法不是从一帧到另一帧的顺序检测，而是自 适应或者二进制查找，这样可以跳过不必要的帧更快的定位。这种方法比顺序检测可以 提高1 6 倍速率。 渐变切换中帧之间结构上很强的相关性，因此检测有一定困难。利用对镜头编辑的 先验知识，对各种镜头切换建立数学模型，即采用基于数学模型的方法，对镜头渐变的 检测往往能取得好的效果。 另外，其他简便且有效的渐变检测方法有如下两种：( 1 ) b o u t h e m y 2 7 提出的二维 参数运动模型检测突变和渐变的统一算法。突变通过相邻帧的主运动支撑层的大小来 检测，一个帧中的主运动支撑层的大小明显下降，表明了突变的出现，渐变需要一段时 间观察支撑层的大小来检测。这种方案计算上比较费时，不适合实际应用，但估计出来 的运动信息非常有用。( 2 ) j u n 2 8 提出了利用m p e g 视频的宏块信息快速、有效检测慢 转换镜头的方法。这些切片是视频序列沿时间轴的一系列二维图像。不同的镜头切换 方式对应着不同的切片模式，切片模式通过把颜色和纹理模式都考虑在内的空能量模 型决定。 1 2 2 国内外基于内容的视频检索研究成果 基于内容的视频分析与检索目前已经取得了很多研究成果，国内外已研发出多个 基于内容的视频检索系统，主要有： ( 1 ) i b m 的q b i c 和c u e v i d e o 项目 o b i c 是i b m 公司推出的第一个商用的基于内容的图像查询系统，也是基于内容检索 系统的典型代表，其系统框架和关键技术对后来的图像检索研究具有深远影响。q b i c 系统允许使用例子图像、用户构建的草图和图画、选择的颜色和纹理模式、镜头和目 标运动和其它图形信息等，对大型图像和视频数据库进行查询。 c u e v i d e o 系统则由视频检索和浏览系统、多媒体信息自动索引系统组成，其目标是 解决大规模视频数据库的生成、索引和使用等具有挑战性的问题。c u e v i d e o 主要是解 4 k 奋丁业人学碗i 。学位论文 决两个瓶颈问题：为海量视频数据库建立索引的代价很大；用户难以做到方便检索和 浏览视频的内容。为了快速实现全自动的索引和建立超级链接，它组合视频和音频分 析、语音识别、文本信息检索和人工智能等技术。 ( 2 ) p h o t o b o o k 系统 p h o t o b o o k 系统是由m i t 的媒体实验室开发的一套交互式图像数据库浏览和查询工 具。p h o t o b o o k 网上演示版给出了四种应用领域的示范：纹理识别、形状识别、人脸识 别和大脑形状识别。纹理识别主要针对以纹理为主体内容的图像，形状识别给出了一 些具有简单形状物体( 如板手) 的检索示例，人脸识别是基于m i t 研究基础上开发的重 要应用。大脑形状识别则是p h o t o b o o k 新的应用领域，它在检索过程中能处理图像 的3 d 数据，此外还允许用户通过动态的加载代码来定义匹配算法。f o u r e y e s 是 p h o t o b o o k 的扩展版本，它突出了交互式语义查询及系统学习功能，并且还应用了相关 反馈技术。系统可保留用户的记录，使用一个代理设施来进行学习，通过分析选择出 较好的匹配模式以改进功能。 ( 3 ) c o k e 系统 新加坡国立大学开发的一个基于内容的检索系统。其显著技术特色包括：多种特征 提取方法、多种基于内容检索方法、使用自组织神经网络对复杂特征度量、建立基于 内容索引的新方法以及对多媒体信息进行模糊检索的新技术。 ( 4 ) v i s u a l s e e k 和w e b s e e k 系统 v i s u a l s e e k 和w e b s e e k 系统由美国哥伦比亚大学图像和高级电视实验室开发的基 于w e b 的图像、视频搜索工具。该系统的主要特点是用到了图像区域的空间关系查询 和直接从压缩数据中提取视觉特征。它实现了互联网上的“基于内容”的图像视频 检索系统，提供了一套工具供人们在w e b 上搜索和检索图像和视频。v i s u a l s e e k 是一 个通用的搜索引擎，它根据图像中不同色块的空间关系进行相似匹配，此外也用到颜 色、纹理等特征提取技术，在解决快速索引问题上采用了二叉树索引技术。v i s u a l s e e k 与q b i c 一样提供了多种查询方法，可根据视觉特征、 图像注释、草图甚至是图像的 u r l 。w e b s e e k 是一个专用的面向w w w 的搜索引擎。目的是在w w w 上建立一个可视化 对象的自动辞典供用户查询，并提供基于注释和基于图像视觉信息的用户查询接口。 ( 5 ) t v f i 系统 t s i n g h u a v i d e o f i n d h 是清华大学开发的视频节目管理系统。该系统可以提供视频数 据入库、基于内容的浏览、检索等功能，并提供多种数据访问模式，包括基于关键字 查询、示例查询、按视频结构浏览及按用户自定义类别进行浏览。 ( 6 ) v i r a g e 是v i r a g ei n c 公司开发的基于内容图形搜索引擎，类似于q b i c ，v i r a g e 支持基 于颜色、颜色布局、纹理、结构等视觉信息的检索，支持上述几种原子查询的组合查 k 奋丁业人学碗j 学位论文 询，用户能根据自己的意愿调整某个查询权重。 ( 7 ) n e t r a u c s b 为a l e x a n d r a 数字图书馆项目研制的原型系统，它用颜色、纹理、形状和分 割后的图像区域之间的空域关系等视觉特征。 ( 8 ) b l o b w o r l d u cb e r k e l e y 开发，它将原始图像转换为一组局部相关的颜色和纹理，使用户观看 图像内部表示和查询结果，让用户能够直观地改进检索结果。 ( 9 ) i n f o r m e d i a 系统 美国n s f 、a r p a 和n a s a 资助的数字图书馆项目其主要研究目标：搜集、存 储和组织数字信息的新技术，通过网络实现信息的搜索、检索和处理。例如，参加单 位之一c m u 大学所承担的i n f o r m e d i a 项目允许用户访问、挖掘、检索海量的数字视频 库，在其系统中集成语言、图像和自然语言理解技术。i n f o r m e d i a 同等看待语音和视 频信息的作用，采取多种智能处理技术，利用c n n 广播电视节目中的脚本信息 ( c l o s e d c a p t i o n ) 构造文本索引，采用s p h i n xi i i 语音识别器将伴音转换为文本； 使用视频分析模块提取人脸特征、叠加在屏幕上的文本、视频镜头边界等，然后将这 些信息全部绑定形成最终索引结构，支持快速相似检索。 另外还有许多类似的系统，例如加利福尼亚大学s a n t a b a r b a r a 分校的n e t r a 、伊 利诺依大学的m a r s 、c m u 的i n f o m e d i a 以及哥伦比亚大学的v i d e o o 等。 6 匕奋t 业人学砸i 。学位记上 第二章基础理论与关键技术 2 1 图像数据的压缩理论 压缩机制通常可以分为两种有损压缩和无损压缩。在无损压缩中，我们关心 的是精确重建没有信息丢失的数据，无损压缩通常被用于文本文件的压缩中。 对于有损压缩，我们允许压缩后产牛质量上的误差。有损压缩机制的优点是可以 得到比无损压缩高得多的压缩比，但是它只能用于可以用近似的数据代替原始数据， 而这种相近数据又是容易被压缩的情况。举例来说，一幅和原图像在视觉上没有区别 的图像可以看作是原图像的近似。 任何压缩机制的根本思想都是除去数据中存在的相关性。所谓相关性，就是能够 根据给出的一部分数据来判断出其相邻的数据。实际中存在着很多种数据相关性，这 里给出常见的几种： ( 1 ) 空间相关性：可以根据图像中某一点的像素值推断出其相邻点的像素值； ( 2 ) 频率相关性：一个信号的傅立叶变换通常是光滑的。这意味着可以根据某一部 分的频率来推断其相邻部分的频率。 ( 3 ) 时间相关性：在数字视频中，在时间上相邻两帧图像的大部分像素的值变化很 d 、。 有损压缩的标准过程是变换编码。基本思想是用一个和原来不同的数学基来表示 数据，在这种新的表示下，数据的相关性能够显露出来或被拆开。在这种新的基下， 大部分的系数都接近零，可以忽略，于是可以将余下的信息存储在一个较小的数据包 中。压缩是通过数据变换，把域值以下的系数置零，对非零的数据进行无损的编码来 实现的。 2 1 1 无损压缩 ( 1 ) 行程( r u n l e n g t h ) 编码技术 行程编码是相对简单的一种编码，是指在一行扫描的像素中，比较相邻像素的幅 度( 如亮度) 。当幅度有一个显著变化时，就说有一个行程存在。像素幅度的连续长度 和终点位置标记是其重要参数。随终点位置标记方法不向，行程编码可分为两类： 1 ) 行程终点编码：行进的终点位置由扫描行的起始点算起至行程终点位置时的像 素数确定。 2 ) 行程长度编码：某行程的终点位置由它距前一终点的相对距离来确定。 行程终点编码又分为两种： 7 k 奋t 业，、学埘! f 学位论z 线性码法( a 码)根据不同行程长度赋予不同码字。大行程码字长，小行程码字 短。 对数码法( b 码)它的码字长度与行程长度的对数成正比。 行程编码适用于二值图像。行程编码的编码效率不如h u f f m a n 编码方法高，但它 的码字结构相对简单，故在许多情况下也被采用。 ( 2 ) h u f f m a n 编码压缩 无损压缩的编码方法中，h u f f m a n 编码方法是一种较有效的编码方法。h u f f m a n 编码是一种长度不均匀的、平均码率可以接近信息源墒值的一种编码。它的编码基本 思想是：对于出现概率大的信息采用短字长的码，对于出现概率小的信号用长字长的 码，以达到缩短平均码长，从而实现数据的压缩的目的。h u f f m a n 编码采用以下方法进 行：首先将信源符号按其出现概率的大小顺序排列，然后把出现概率最小的两个符号 的概率值相加，得到一个新的概率。第二步，把这个新概率看成是一个新符号的概率， 和其他符号再按概率大小排列，再把最后两个概率相加。重复上述做法，直到最后只 剩下两个符号的概率为止。完成以上概率相加作顺序排列后，再反过来逐步向前进行 编码，每一步有两个分文各赋予一个二进制码，可以对概率大的赋码元o ，对概率小的 赋码元1 ，亦可对概率大的赋码元1 ，对概率小的赋码元0 。h u f f m a n 在变字长编码方 法户足最佳的，其码字平均长度很接近信息符号的熵值。h u f f m a n 编码的最高压缩效率 可以达到8 ：1 ，但是在一般实施过程中，很难达到这种压缩比例。苦图像文件中存在 某个拥有长程的字节值时，使用行程编码压缩算法可能更好。 ( 3 ) 字典压缩方法 目前广泛采用的字典压缩算法包括两种类型。一种是在数据压缩过程中，寻找当 前等待进行比缩处理的数据串中是否在已经处理过的数据串中出现过，如果确实曾经 出现过，则利用指向该已经进行处理数据串的指针代替当前等待进行压缩的数据串， 此时，宁典是隐式的，它用曾经处理过的数据描述。这类字典压缩算法都是基于a b r a h a m 与j a k o b z i v 于1 9 7 7 提出并发表的l z 7 7 算法，该算法提出后，s t o r e r 与s z y m n n s k i 于1 9 8 2 年对其进行了改进，并提出相应的l z s s 算法，l z s s 算法成为现在实践中广泛 使用的该类算法的基础。 另外一种字典压缩算法是为输入数据创建一个短路宁典，如果在当前等待进行压 缩的数据流中发现字典中已经存在相应的短语，则利用该短语在字典中的相应索引值 取代原始数据，这种类型的算法基于l a m p e l 与z i v 在1 9 7 8 年提出并发表的l z 7 8 算法。 后来该压缩算法由s p e r r y 公司的研究员w e l c h 于1 9 8 4 年在硬件设计过程中改进并用 于高性能磁盘控制器的设计，由l e m p e l 和z i v 两人在实际工作中实现，因此被命名力 l z w 编码。l z w 压缩算法现在已经派生出几种流行的算法格式，不仅可以用于文字数据 的压缩，而且也可以成功地用于某些图像数据的压缩处理。现全，w i n z i p 、g z i p 、p k z i p 长奋t 业j 、学耐! 卜学位论z 等压缩软件广泛使用l z 7 7 压缩算法进行数据压缩。 ( 4 ) 算术压缩方法 算术压缩方法与h u f f m a n 压缩方法相似，都是利用比较短的代码取代图像数据中 出现比较频繁的数据，而利用比较长的代码取代图像数据中使用频率比较低的数据从 而达到数据压缩的目的。它同时又采纳了l z w 压缩算法的思想，不仅压缩数据值，而 且压缩值的序列，从而可以达到更加现想的压缩比例，尤其适合于大多数数据由相同 的重复序列组成的图像文件。但是算术压缩算法的实现比较复杂，其基本思想将每个 不同的序列按照出现频率映射到0 和1 之间的相应数字区域内，该区域表示成可以改 变精度的二进制小数，其中出现频率越低的数据利用精度越高的小数进行表示。算术 压缩算法中两个基本的要素为源数据出现的频率以及其对应的编码区间。其中，源数 据的出现频率决定该算法的压缩效果，同时也决定编码过程中源数据对应的区间范同， 而编码区间则决定算术压缩算法最终的输出数据。 算术压缩算法可以大隔度地减小文件长度，甚至可以达到1 0 0 ：1 的压缩比例，在 j b l g 与j p e g 等图像文件格式的数据压缩处理步骤中占有很重要的地位，针对不同的图 像文件，其压缩比例主要是与源文件的数据分布及其所采用标准模式的精度有关，同 时，阻碍算术压缩算法广范推广的原因不仅是因为算法的复杂性，还有另外一个重要 原因是其受到几项i b m 的专利保护，从而导致了算法许可证的不确定性。 2 1 2 有损压缩 ( 1 ) 预测编码方法 如果已知图像的一个像素离散值，利用其相邻像素的相关性，预测它的下一个像 素( 水平方向或垂直方向) 的可能值，求其两者差、再量化、编码。这种方法称为预 测编码方法，简称预测法( d p c m 法) 。 预测编码方法计算简单，若采用h u f f m a n 编码技术，压缩比从2 ：1 到4 ：1 仍有 满意的效果。但本方法是基于差值信号的统计特性基础上发展起来的，它有如下缺点： 1 ) 对黑白灰度有突变的点，会有较大的预测误差，使重建图像的边缘模糊、分辨 率降低。 2 ) 对图像亮度值变化缓慢区域、其差值信号应为零，但因预测值偏大而使重建图 像产生噪音。 针对预测编码方法的缺点，其改进的方法是自适应预测编码方法。 ( 2 ) 正交变换编码 图像变换编码的系统框图如图所示： 9 k 击t 业j ：学坝f 擘位论文 输入一回一囤一回一回一 回一回一输出 图像变换编码系统框图 图像经过正交变换后能够实现图像数据压缩的物理本质在于：经过多维坐标系中 的适当的坐标旋转和变换，能够把散布在各个坐标轴上的原始图像数据，在新的适当 的坐标系中集中到少数坐标轴上，因而有可能用较少的编码比特数来表示一幅子图像， 实现图像的压缩编码。 从数学上来看，可用于图像压缩编码的正交变换的方法除f o u r i e r 变换、 w a l s h h a d a m a r d 变换外，还有正弦变换、余弦变换、斜变换、哈尔变换、k l 变换等。 不同的变换有不同的压缩效果( 压缩比和重建图像质量) 。数学上已证明，采用均方差 最小准则，k 一变换( 即离散信号的h o t e l l i n g 变换) 具有最佳变换性质，余弦变换次之。 变换的效率还与子图的大小有关，一般说来子图增大能提高编码效率，但也会使计算 量增大而给实现带来困难。同时图像的相关性一般局限在2 0 个邻近像素之内。因此， 目前通常采用的子图像大小为8 8 或1 6 1 6 。 ( 3 ) 金字塔编码 由b u r t 和a d e l s o n 提出的金字塔算法把原图像分解成许多不同的分辨率的子图 像，并把高分辨率( 尺寸较大的) 的子图像放在下层，把低分辨率( 尺寸较小) 的子图像 放在上层，从而构成了一个金字塔，借助于拉普拉斯金字塔算法，对图像的每一层分 别量化、编码，并对视觉不敏感的层粗化，用较少的码字编码，从而达到压缩的目的。 图像的金字塔表示方法也是计算机视觉中常用的一种多分辨率表示法，利用金字 塔表示法，能分析图像中不同大小的物体，例如高分辨率的下层可用于分析细节，低 分辨率的上层可用于分析较大的物体，同时，通过对低分辨率、尺寸较小的上层进行 分析所得到的信息还能用来指导对高分辨率、尺寸较大的下层进行分析，从而大大简 化了分析和计算。 图像的金子塔编码有其合理的一面，金字塔编码能大致上做到在对数频率上以半 倍频形式分解频段，并且金字塔编码本身符合逐级浮现的图像编码要求，高层子图显 示全图概貌，在解码过程中能由上到下，逐层添加细节，直到较低层的了图满足要求。 然而这种塔形分解并不理想，它使数据量增大了，并且没有体现方向性，因此，目前 主要集中在性能更加优越的图像分解表达方法上，如小波变换，但多分辨率表达和复 原图像的思想已经体现在其他各种图像编码的标准中。 1 0 k 奋t 业凡学硕l 学位论文 ( 4 ) 子带编码 子带编码最早用于语音编码，w o o d 和0 n e i l 在1 9 8 6 年首先把子带编码应用于图 像编码。子带编码先将原图用若干数字滤波器( 分解滤波器) 分解成不同频率成分的分 量，再对这些分量进行亚抽样，形成子带图像，最后对不同的子带图像分别用与其相 匹配的方法进行编码，在接受端，将解码后的子带图像补零、放大，并经合成滤波器 的内插，将各子带信号相加，进行图像复原。 与d c t ( 离散余弦变换) 编码相比，子带编码的最大优点是复原图像无方块效应，因 此得到了广泛的研究，是一种有潜力的图像编码方法。 各子带图像的统计特性是以人眼对它们的敏感程度确定的，可以根据信息沦和人 眼的视觉特性，用不同的方法对各子带编码，其要点可以归结为以下两条： 1 )l l 分量最重要，应该较精确的编码，一般可用d p c m 、d c t 等方法，量化也要 精确一些 2 ) 高频分量重要性差一些，不适于用d c t 编码，由于用d p c m 不比p c m 好多少， 所以通常直接用p c m 编码，另外，为了降低码率及噪声的影响，高频分量的量化在零 附近有个死区。 ( 5 ) 矢量量化编码 矢量量化在图像编码个要优于标量量化，目前得到较为广泛的研究应用的有：空 间域矢量量化、预测矢量量化、变量矢量量化、混合矢量量化，以及子带矢量量化、 神经网络矢量量化等技术。 2 2 多媒体数字视频压缩标准 数字视频技术广泛应用于通信、计算机、广播电视等领域，带来了会议电视、可 视电话及数字电视、媒体存储等一系列应用，促使了许多视频编码标准的产生。i t u t 与i s o i e c 是制定视频编码标准的两大组织，i t u t 的标准包括h 2 6 1 、h 2 6 3 、h 2 6 4 ， 主要应用于实时视频通信领域，如会议电视；m p e g 系列标准是由i s o i e c 制定的，主 要应用于视频存储( d v d ) 、广播电视、因特网或无线网上的流媒体等。两个组织也共同 制定了一些标准，h 2 6 2 标准等同于m p e g 一2 的视频编码标准，而最新的h 2 6 4 标准则 被纳入m p e g 一4 的第1 0 部分。下图说明了视频编解码标准的发展历程： k 存t 业，、学mj 学位论文 舯0 i s t l n 曲 d s h 篮lh 2 站h 2 e *h 2 1 4 州 | l 睁e g 。f j ， 罗。 i 勘岫 i 馏弘 蛆6 伯船 9 驰1 9 9 2 9 时1 9 9 61 9 9 2 如2 22 0 0 4 2 2 1h 2 6 x 标准 ( 1 ) b 2 6 1 视频编码标准 h 2 6 1 是i t u t 为在综合业务数字网( i s d n ) 上开展双向声像业务( 可视电话、视频 会议) 而制定的，速率为6 4 k b s 的整数倍。h 2 6 1 只对c i f 和q c i f 两种图像格式进行 处理，每帧图像分成图像层、宏块组( 6 0 b ) 层、宏块( m b ) 层、块( b l o c k ) 层来处理。h 2 6 1 是最早的运动图像压缩标准，它详细制定了视频编码的各个部分，。包括运动补偿的帧 间预测、d c t 变换、量化、熵编码，以及与固定速率的信道相适配的速率控制等部分。 ( 2 ) h 2 6 3 视频压缩标准 h 2 6 3 是i t u t 为低于6 4 k b s 的窄带通信信道制定的视频编码标准。它是在h 2 6 1 基础上发展起来的，其标准输入图像格式可以是s - q c i f 、q c i f 、c i f 、4 c i f 或者1 6 c i f 的彩色4 ：2 ：0 亚取样图像。h 2 6 3 与h 2 6 1 相比采用了半象素的运动补偿，并增加了 4 种有效的压缩编码模式。 无限制的运动矢量模式允许运动矢量指向图像以外的区域。当某一运动矢量所指 的参考宏块位于编码图像之外时，就用其边缘的图像象素值来代替。当存在跨边界的 运动时，这种模式能取得很大的编码增益，特别是对小图像而言。另外，这种模式包 括了运动矢量范围的扩展，允许使用更大的运动矢量，这对摄像机运动特别有利。 基于句法的算术编码模式使用算术编码代替霍夫曼编码，可在信噪比和重建图像 质量相同的情况下降低码率。先进的预测模式允许一个宏块中4 个8 8 亮度块各对应 一个运动矢量，从而提高了预测精度；两个色度块的运动矢量则取这4 个亮度块运动 矢量的平均值。补偿时，使用重叠的块运动补偿，8 8 亮度块的每个象素的补偿值由 3 个预测值加权平均得到。使用该模式可以产生显著的编码增益，特别是采用重叠的块 k 备t 业，：学倾l 。学位论上 运动补偿，会减少块效应，提高主观质量。p b 一帧模式规定一个p b 一帧包含作为一个单 元进行编码的两帧图像。p b 一帧模式可在码率增加不多的情况下，使帧率加倍。 i t u t 在h 2 6 3 发布后又修订发布了h 2 6 3 标准的版本2 ，非正式地命名为h 2 6 3 + 标准。它在保证原h 2 6 3 标准核心句法和语义不变的基础上，增加了若干选项以提高 压缩效率或改善某方面的功能。原h 2 6 3 标准限制了其应用的图像输入格式，仅允许5 种视频源格式。h 2 6 3 + 标准允许更大范围的图像输入格式，自定义图像的尺寸，从而 拓宽了标准使用的范围，使之可以处理基于视窗的计算机图像、更高帧频的图像序列 及宽屏图像。 为提高压缩效率，h 2 6 3 + 采用先进的帧内编码模式；增强的p b 一帧模式改进了h 2 6 3 的不足，增强了帧间预测的效果；去块效应滤波器不仅提高了压缩效率，而且提供重 建图像的主观质量。为适应网络传输，h 2 6 3 + 增加了时间分级、信噪比和空间分级， 对在噪声信道和存在大量包丢失的网络中传送视频信号很有意义；另外，片结构模式、 参考帧选择模式增强了视频传输的抗误码能力。 t t 2 6 3 + + 在h 2 6 3 + 基础上增加了3 个选项，主要是为了增强码流在恶劣信道上的抗误 码性能，同时为了提高增强编码效率。这3 个选项为：选项i i 一称为增强型参考帧选 择，它能够提供增强的编码效率和信道错误再生能力( 特别是在包丢失的情形下) ，需 要设计多缓冲区用于存贮多参考帧图像。选项v 称为数据分片，它能够提供增强型 的抗误码能力( 特别是在传输过程中本地数据被破坏的情况下) ，通过分离视频码流中 d c t 的系数头和运动矢量数据，采用可逆编码方式保护运动矢量。选项w 一在h 2 6 3 + 的码流中增加补充信息，保证增强型的反向兼容性，附加信息包括：指示采用的定点 i d c t 、图像信息和信息类型、任意的二进制数据、文本、重复的图像头、交替的场指 示、稀疏的参考帧识别。 ( 3 ) h 2 6 4 视频编码标准 h 2 6 4 和以前的标准一样，也是d p c m