（模式识别与智能系统专业论文）基于gpu的视频编码和分割的研究.pdf

摘要 摘要 视频编码和分割的主要任务是怎样改善编码和分割的效率。但是由于c p u ( c e n t r a lp r o c e s s i n gu n i t ) 性能及其它因素的限制，现在很多的视频分割和编码难以 达到多媒体服务的实时要求。根据图形处理芯片g p u ( g r a p h i cp r o c e s s i n gu n i t ) 的技 术发展和性能特点( 支持整型运算、内部图形处理运算精度只有四分之一个精度) ， 论文提出了使用g p u 和c p u 相结合来改善视频编码和分割效率的方案，并分析了传 统的视频分割和视频编码的方法，探讨了如何找到适合g p u 运算的算法，来完成视 频压缩编码和分割需要的视频对象。 本论文从g p u 特点出发，提出了算法改进的指导思想：( 1 ) 用整型运算方法来替 代浮点运算方法，或者把部分c p u 的整型运算转移到g p u 上来；( 2 ) 以图像面而不是 以像素点来考虑问题。本文对基于g p u 的视频编码和视频分割深入系统的研究，具 体的创新和研究成果如下： 一、本文在可变大小块四分树分割的基础上提出了一个基于对象的运动估计算 法。该算法根据图像边缘的特性，对图像的内容做适当的分析，将图像画面分割为静 止及运动物体的块，然后根据运动物体块的边缘特性分割出不同的区域，针对不同的 区域分别进行运动估计。实验表明，利用边缘特性做分割块的准则符合人类视觉系统 的特性，其重建的图像更接近人眼实际观看的品质。本论文的算法的速度和所预测出 来的图像的效果要优于目前的全局搜索法和可变四分树分割算法。 二、根据g p u 的运算精度低的特点，提出了一个提升方案修改变换系数，采用 舍入操作，把传统的离散余弦变换算法从线性变换转变为的整数变换，推导出一维整 数离散余弦变换算法和二维整数离散余弦变换算法，并采用整数离散余弦变换完成视 频编码工作。 三、在g p u 与c p u 相结合的视频分割算法研究方面，介绍了如何选择合适的色彩 空间，并结合基于对象的运动估计，提出了一个时域上的分割算法，建立了一个有效 率的统计模型来估计在运动状态下之可预测点；并详细描述了一个改进传统马尔可夫 随机场的空域分割模型，并且使用了图之问边与边的关系得到适合寻找最佳路径的权 值，提出了适合g p u 运算的随机游动邻接矩阵算法。实验表明，相对传统的视频分割 算法与本文的算法错误概率较小，分割速度要快。 关键词： 图形处理芯片，整数离散余弦变换，运动估计，视频分割 a b s t r a c t a b s t r a c t t h em a j o rt a s ko ft h ev i d e o c o d i n ga n d v 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 sf o r m u l t i m e d i aa p p l i c a t i o n si sh o wt o i m p r o v et h ec o d i n ga n ds e g m e n t a t i o ne f f i c i e n c y h o w e v e r , b e c a u s eo ft h el i m i t a t i o no fc p u ( c e n t r a lp r o c e s s i n gu n i t ) a n do t h e rr e a s o n s ， m o s to fv i d e oc o d i n ga n ds e g m e n t a t i o nt e c h n o l o g i e sc a nn o t s a r i s f yt h er e a l t i m e d e m a n d i n go fm u l t i m e d i aa p p l i c a t i o n s t h i st h e s i si st os o l v et h e s ep r o b l e m sb yu s i n gg p u ( g r a p h i c a lp r o c e s s i n gu n i t ) b u tg p uo n l ys u p p o r t si n t e g e rc o m p u t a t i o na n dt h ep r e c i s i o n o fp i x e ls h a d e ri s v e r yl o w , t h i st h e s i st r i e s t os o l v et h i sd i f f i c u l t y , a n ds e v e r a ln e w a l g o r i t h m sa r ep r o p o s e db yc o m b i n i n gg p ua n dc p u a c c o r d i n gt ot h ep r o p e r t i e so fg p u ，o u ra l g o r i t h m sa r ed i r e c t e db yt w ob a s e s ：1 ) f l o a t i n go p e r a t i o n sa r er e p l a c e db yi n t e g e ro p e r a t i o n s ，o ri n t e g e ro p e r a t i o n so nc p ua r e t r a n s f e r r e dt og p u ；2 ) c p ui sp r o c e s s e dp i x e lv a l u e si ni m a g ep r o c e s s i n g w h i l eg p ui s p r o c e s s e dt h ew h o l ei m a g es u r f a c e t h em a i nc o n t r i b u t i o n so f t h et h e s i sa r ea sf o l l o w i n g ： t h ef i r s tp a r tp r o p o s e sam o t i o ne s t i m a t i o na l g o r i t h mb a s e do nt h ev a r i a b l eb l o c k ，s i z e q u a d - t r e es e g m e n t a t i o na l g o r i t h m t h ea l g o r i t h mf i r s to b t a i n sd i f f e r e n t r e g i o n sb y a n a l y z i n gt h eo b j e c tc h a r a c t e ra n di m a g ee d g ec h a r a c t e r ，a n dt h e ng e t sm o t i o nv e c t o r so f d i f f e r e n tr e g i o n s e x p e r i m e n t a lr e s u l t ss h o wt h ep r o p o s e da l g o r i t h mn o t o n l ya g r e e so nt h e h u m a nv i s u a ls y s t e m ，b u ta l s ot h ew h o l er u n n i n g s p e e da n dq u a l i t yo ft h ep r e d i c t e di m a g e a r eb e t t e rt h a nt h o s eo ff u l l s e a r c h a l g o r i t h ma n dv a r i a b l eb l o c k s i z eq u a d t r e e s e g m e n t a t i o na l g o r i t h m t h es e c o n dp a r tw i l ld i s c u s sh o wt oc o m p l e t ed i s c r e t ec o s i n et r a n s f o r m ( d c t ) b y g p u b e c a u s et h eo p e r a t i o np r e c i s i o no fg p ui sv e r yl o w ，w ei m p r o v et r a d i t i o n a ld c t a l g o r i t h ma n dp r o p o s ea ni n t e rd i s c r e t ec o s i n et r a n s f o r ma l g o r i t h mb yl i f t i n gs c h e m i n g a n dr o u n d i n go p e r a t i o n f i r s tw ei n t r o d u c et h et h e o r yf u n d a m e n to fi n t e g e rd c t ，a n dt h e n p r o p o s eo n ed i m e n s i o nd c ta n dt w od i m e n s i o n sd c t a l g o r i t h m s t h et h i r dp a r ti st op r o p o s eav i d e o s e g m e n t a t i o na l g o r i t h mc o m b i n i n gg p ua n dc p u f i r s t l y ，w ei n t r o d u c eh o wt os e l e c t a p p r o p r i a t ec o l o rs p a c e ，a n dt h e nd i s c u s st h e t i m e d o m a i ns e g m e n t a t i o na l g o r i t h mb a s e d0 1 1 o b j e c tm o t i o ne s t i m a t i o mi nt h ee n d ，w e 中国科学院0 轴纯所硕士学位论文 p r o p o s eas p a t i a l - d o m a i na l g o r i t h mb a s e do nm a r k o vr a n d o mf i e l da n dg r a p hm o d e l e x p e r i m e n t a lr e s u l t ss h o wt h ep r o p o s e dt e c h n o l o g yn o to n l yh a st h es m a l le r r o rp r o b a b i l i t y b u ta l s oh a sh i 曲c o d i n ge f f i c i e n c y k e yw o r d s ：g r a p h i c a lp r o c e s s i n gu n i t ，i n t e r - d c t , m o t i o ne s t i m a t i o n ，v i d e os e g m e n t a t i o n i i l 独创性声明 本人声明所成交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果。与我一同工作的同：恙对本研究所做的任何贡献 均已在论文中作了明确地说明并表示了谢意。 签名：垒多笙 日期：王臣丝竺主 关于论文使用授权的说明 本人完全了解中国科学院自动化研究所有关保留、使用学位论文的规定，即： 中国科学院自动化研究所有权保留送交论文的复印件，允许论文被查阅和借阅： 可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 躲辑新虢继日期：碰：趔 第一章绪论 1 1 背景 第一章绪论 数字化后的图像如果不压缩的话，其数据量是极大的：诸如一幅5 1 2 x5 1 2 的真彩 色( 2 4 b i t s p i x e l ) 的未压缩图像，其原始数据量达6 m b i t ，一个c dr o m 盘( 现在最 大位7 2 0 m ) 只能存放1 2 0 多幅。如果是序列图像，每秒3 0 帧，只能存放4 秒钟的图 像数据。这样大的数据量，无论存储还是传输都是极其困难的。因此，图像压缩编码 是十分必要的。1 9 4 8 年，s h a n n o n 和他的两个学生o l i v e r 与p i e r c e 联合发表了对电视 信号进行脉冲编码调制( p c m ，p u l s ec o d i n gm o d u l a t i o n ) 的论文【7 ，标志着数字图 像压缩编码技术的开端。从二十世纪四十年代末开始，图像编码技术经历了半个世纪 的发展。五、六十年代对基本方法的探讨和七十年代早期可视电话的研究，使得这一 领域有了长足进展，许多基本的思想和方法都相继提出。到八十年代前后，顺应信息 化的趋势，面向各种应用的开发研究都大力开展起来。二十世纪九十年代中后期，随 着互联网的迅猛发展，人们萌发了通过网络传输视频和图像的愿望，互联网由最初的 提供数据服务发展为支持多媒体服务( 包括视频、图像、图形、语音、文字) 。与此 同时，国际标准化组织( i s o ) 和国际电信联盟( i t u ) 先后制定了一系列静止和运 动图像编码标准，包括二值图像编码标准j b i g 8 、用于彩色和连续扶度静止图像压 缩的j p e g 9 1 、面向i s d n 视频传输的h 2 6 1 1 0 、用于数字视频和音频传输及存储的 m p e g 一1 1 1 】、支持h d t v 等高品质数字视频和音频传输与存储的m p e g 一2 f 1 2 1 、适合 于低码率视频传输的h 2 6 3 1 3 、基于对象的视频编码标准m p e g 4 1 4 和刚刚完成的 致力于低码率高编码效率的h 2 6 4 1 1 5 1 。 不同于以语音业务为中心的第二代无线通信系统，未来的宽带无线通讯网络的特 征是以提供高速接入和多媒体服务。为了有效利用最少的数据与传输频宽，表现最多 的使用者信息，更先进的影音与数据压缩方法是绝对必要的。现在很多视频标准以对 象为基础架构( o b j e c t - b a s e d ) ，依内容不同将声音与视频分割成许多个对象，有可能 是固定的背景( b a c k g r o u n d ) 、一个正在讲话的人、及其说话的声音、或是背景音乐， 以期能达到有效地表达、储存、传送多媒体数据，使得使用者能容易地处理编辑每个 对象，这样非常适合于多媒体的各种应用 1 6 】。但是图像视频分割这个难题制约了这 方面的发展，尽管有些分割算法得到理想分割结果但是不能满足实时要求。例如：在 中国科! 学院臼动化所硕十学位论文 m p e g 一4 的视频压缩标准中，图像序列中的每一个画面，将分割成几个视频对象平面 ( v i d e oo b j e c tp l a n e s ) ，每个视频对象平面涵盖某一对象的信息，但是很难找到一个计 算复杂度低的算法分离出形状( s h a p e ) 、纹理( t e x t u r e ) 、动作( m o t i o n ) 等，再分别去进 行编码。 目前图像视频的处理基本上是在c p u 的基础上完成的。由于c p u 还不可能快速 地完成大规模并行图像处理运算。尽管现在c p u 的主频己经很高，但还是达不到进 行某些图像视频处理的要求。例如：一台主频是p 41 8g 的c p u ，如果解码1 9 2 0 x 1 0 8 0 的高码率视频( 编码和解码采用d i v x 格式) ，根本达不到每秒至少2 4 帧的要求；常用 的视频分割算法很难达到实时的分割。有没有其他的方法来解决这些问题? g p u ( g r a p h i cp r o c e s s i n gu n i t ) 图形处理芯片，它是显示卡的1 心脏”，也就 相当于c p u 在电脑中的作用。1 9 9 9 年，n v i d i a 公司推出了g e f o r c e 一2 5 6 ，这是第一 款带有g p u 的显卡，g p u 主要完成几何变换与光照向量计算，这是c p u 的功能第一 次向g p u 迁移。g p u 使c p u 摆脱了处理绘图计算的任务，如此可让c p u 做其它的 工作，绘图效能不受c p u 速度的影晌而达到高分辨率和高幅速率的效果f ijo 我们可 以对比一下g p u 和c p u 来进一步深入了解g p u 。例如：g e f o r c ef x 芯片( 见图l 1 ) 采用了0 1 3 微米制程，至少整合了1 亿2 5 0 0 万个晶体管用于计算 2 1 。i n t e l 最复杂 的c p u 是i n t e lx e o nm p ，其整合度达到了l 亿8 0 0 万个，但是其中三分之二的晶体 管都用于了二级缓存和三级缓存，所以c p u 的主体部分的复杂程度远远的低于 图1 1g e f o r c ef x g p u 芯片 第一章绪论 一一 1 2 研究动机 g p u 本身的t & l ( t r a n s f o r ma n dl i g h t i n g ) 技术原因决定g p u 主要面向图形处理。 g p u 为了快速的并行运算所以只支持整型运算( 内部图形处理运算只有四分之一个精 度1 。但是图像视频处理需要大量的浮点运算，而且g p u 的运算指令完全不同于c p u ， 所以让g p u 来完成图像视频处理是很困难的，有没有解决方法? 我们仔细的研究发 现g p u 的核心部分是s h a d e r ，分p i x e ls h a d e r 和v e r t e xs h a d e r 。p i x e l s h a d e r 完成图形运算和v e r t e xs h a d e r 完成顶点运算【3 1 1 4 6 】。p i x e l s h a d e r 的图形运算必须整数( 不得大于3 2 位) ，v e r t e xs h a d e r 的顶点运算可以 是浮点数。所以我们主要是改变算法的思维方式，使它在c p u 的思维转换到适应g p u 的思维：( 1 ) 用整型运算方法来替代浮点运算方法，或者把部分c p u 的实现整型运算 转移到g p u 上来。( 2 ) 图像处理中。因为c p u 处理的是像素点，我们经常用像素点来 考虑问题，现在g p u 处理的是面，将要用图像面来处理问题 7 1 。 因此在本篇论文当中，我们将不仅探讨如何使用g p u 与c p u 结台进行视频编码， 而且还希望通过g p u 与c p u 结合，使用视频序列当中视频内容的特性，来切割出足够 准确的视频对象。 如果g p u 能够单独完成图像视频分割和编码，那么将要有很多重大意义，首先图 像视频处理的时问可以大大的缩短，因为g p u 的运算速度很快，其次硬件的成本将要 很大的降低( 现在的显卡的成本大大的降低了) 。在1 1 节已经提过由于g p u 主要是整 型运算，所以我们不可能完全t h g p u 来完成图像视频的分割和编码工作。但是可以找 到一个方法最大限度的让g p u 完成大部分工作，c p u 参与完成其它的工作。怎样让 g p u 完成大部分工作? 本文提出了一个可以适用于g p u 视频编码的方法来解决此类 问题，与此视频编码方法相对应，本文相应的也提出了一个适应于o p u 的分割方法。 本文的算法可以适应诸如视频会议、数字存储媒体、电视广播、因特网流媒体及通信。 对于高压缩比运动图像的感兴趣区域提取与编码，可允许编码视频图像以灵活的方式 在多种网络环境中使用。例如：医学图像不像一般自然图像可以容许失真，图像品质 在诊断上是很重要的，因此在传输或储存时，医学图像通常是使用非失真型压缩。 般而言，医学图像是以特定的方式在人体的特定部位取像，若锁定在特定图像并运这 方面的知识在压缩上，就能达到更高的压缩比而不会损失医师诊断所需的必要信息。 而且还可以通过可伸缩编码技术传输一些附加信息以帮助医生诊断。一项通过国际互 联网的医学诊断可以通过分割得到医生的感兴趣区域，并且根据网络的带宽决定是否 整个诊断对象区域，这样可以动态的决定某些操作( 诸如手术) 。 中国科学院自动化所硕士学位论文 1 3 论文框架 图1 2 医院网络视频处理传输方案 论文主要介绍了使用g p u 进行视频压缩编码和分割的算法。其中，在视频编码方 面，论文作者完成两个部分的工作：离散余弦转换系数( d c t ，d i s c r e t ec o s i n et r a n s f o r m ) 和运动补偿( m o t i o ne s t i m a t i o n ，m e ) 。前者是为了减少空间上的冗余信皂, ( s p a t i a l r e d u n d a n c y ) ，而后者是为了减少时间轴上的冗余信息( t e m p o r a lr e d u n d a n c y l 。此外，本 文还提出了一个用于视频分割的算法。 包括绪论，论文在结构上分六个章节。第二章介绍了分割和编码的基本知识和算 法，其中包括现在的一些常用的编码方法、动态视频分割方法、以及一些有关模型对 比和模型描述的方法。第三章介绍基于对象运动估计法的理论：全局搜索法、可变大 小块四分树分割算法，改进了一个用于g p u 运算的基于对象运动估计法，并从时间 和信噪比上进行比较各个算法的优劣。第四章介绍了整数d c t 变换算法及其应用， 结合g p u 的处理器特点，我们把d c t 变换的理论基础从线性变换简化到整数变换， 推导出了一维整数d c t 变换算法和二维整数d c t 变换算法。并给出了用于g p u 运 算的整数d c t 变换算法的实验结果。第五章对本文方案中采用的分割算法进行了介 绍。内容包括怎样选择适合的色彩空间作为后续分割的基础，并结合第三章的基于对 象的运动估计方法，改进了时域分割算法和基于马尔可夫随机场与图论的空域分割的 第一章绪论 算法，并且提供了一些理论证明和实验结果分析；最后说明了怎样结合空域与时域的 分割算法及其实验分析。第六章贝q x q 整个工作进行了总结，指出了一些算法的局限性。 第一章编码理论与视频分割简介 - 一一一 第二章编码理论与视频分割简介 在多媒体时代的新纪元罩，计算机与通讯将能有效地处理结合了声音、文字、 图像以及视频等各种来源的媒体。这一章我们将讨论视频编码与分割的基本理论和算 法。 2 ，1 图像视频编码理论 图像视频编码解决的主要问题是如何采用一种新的表达方式来缩小表示图像所 需要的数据量。般的图像视频编码算法是在对数字图像进行大量统计分析的基础 上，充分利用图像自身相关性强的特点，减少图像信息的冗余度，降低码率 1 7 】。数 字图像数据的冗余度主要在三方面：空间冗余度一在一切自然图像中，相邻像素的 相关性相当大：频域冗余度在一幅多频带图像中，同一像素的频谱值经常是相关 的：时间相关性在一串视频序列中，相邻帧之间的差别通常很小。图像压缩编码 就是以去除这三种冗余为基础的。 根据解码结果对原图像视频的保真程度，图像视频压缩可以分成无损压缩和有损 压缩。用有损压缩数据还原出的图像视频会存在信息损失，但是它一般可以获得较高 的压缩率。因此，无特殊要求的图像视频压缩一般都采用有损压缩的方法。由于图像 视频数据在变换域的表现形式比在空域中更加紧凑，编码质量较高，因此在有损压缩 的过程中，图像视频数据首先要被变换到频域，然后变换系数经过量化再使用常规的 无损技术编码。对重建图像视频质量的客观评价一般使用p s n r ( p e a ks i g n a l t o n o i s e r a t i o ) 作为指标。虽然p s n r 高的图像在主观感受上的质量并不一定好，但这是目前 唯一比较通用、同时也比较可行的客观评价方案。p s n r 的定义如式( 2 1 ) 所示： 一枷l o g l 。i 2 5 5 2 瓦丽 式中n 为图像像素个数，y 。f 为参照图像，y 。为处理过的图像。 ( 21 ) 中国科学院自动化所硕士学位论文 211 编码的基本理论 为了能够更深入的理解论文，我们在这里粗略的介绍一下编码的。一些基本知说。 1 熵的概念 在信号s 中平均每种符号所含的信息量，其单位为信息位( b i to f i n f o r m a t i o n ) ，其 中p 为信号s 中之各符号出现之概率【1 8 。其公式为：一事件发生概率为p ，则此事件 的信息量为i ( p ) ，其关系为i ( p ) = l o g l p ，可知当p = 1 时，i ( p ) = o ，也就是说当概率等于 l 时，完全无信息可言。当概率越来越小时，所得到的信息量却越来越大，且变化速 度递增。 2 唯一解码 唯一解码是指经过编码后的信号只有唯一的一种译码方式。例如有信号含有四 个符号，并且其编码成s l = 0 ，s 2 = 0 1 ，s 3 = l o ，s 4 = 0 0 。而现今收到编码后的信号0 0 0 t ， 则可解码成：s ls 1s 2 或s 4s 2 两种情况，则此种编码方式不是唯一译码的编码法。若 将上述编码为下列情形，则为难一译码的编码法s l = 0 ，s 2 = 1 0 ，s 3 = 1 1 0 ，s 4 = t 1 1 。而现 今收到编码后的信号0 0 1 1 1 0 ，则只能译码成：s ls ls 4s 1 ，没有存在第二种译码方式。 3 实时码 实时码是指所收到的信号其字位只被检查一次，旦收到一个完整的符号码则可 立即解码出来，不需再向后判读位数据。实时码的编码条件为在编码中没有一个荷号 的编码是另一符号的前置。实时码代表着其存在着一解码树亦称决定树 1 9 】。 4 空域( s p a t i a ld o m a i n ) 的压缩 一段视频是由单张的连续画面组合而成的，而单独一张画面是可以利用压缩程序 来减低其数据量0 s 。 ( 1 ) 进行空域之压缩时常利用转换( t r a n s f o r m ) 和量化( q u a n t i z e r ) 之程序来达成。 ( 2 ) 转换是指原信号经过个程序转变成另一种表示法，这个表示法可以经由逆 转回复成原信号，而转换的目的是为了使得能量更加集中，以便进行数据的压缩，而 常用的是离散余弦转换( d i s c r e t ec o s i n et r a n s f o r m ，d c t ) 。 ( 3 ) 量化过程可以视为一个滤波器，将人类视觉较不灵敏察觉的高频部份滤去 以达到减少数据量的目的。 第二章编码理论与视频分割简介 一一 5 时域( t e m p o r a ld o m a i n ) 的压缩 由于画面和画面之问的f 叫隔时间只有1 3 0 秒，非常的短暂，所以画面之间有着非 常高度的相关性，我们便呵以利用前后画面问的相关性来进行视频的压缩，而这又称 为时域( t e m p o r a ld o m a i n ) 压缩，其方法为将画面分为l 、b 、p 三种，其中1 画面为单 独自行做空域之压缩，而p 画面是指将画面做切割成许多区块，而去上一张画面搜寻 出各类相关编码。 6 可变长度编码( v a r i a b l el e n g t hc o d i n g ，v l c ) 将欲进行可变长度编码( v a r i a b l et 七n g t hc o d i n g ，v l c ) 的信号先针对其内容予以 概率分析，对于信号中的各个符号，若出现概率较高者，则用较少的位来加以编码， 若概率较低者，则使用较多的位编码 1 8 1 2 0 1 。下面我们介绍一下代表性的编码方法： 算术编码法和h u f f m a n 编码法。 ( 1 ) 算术编码( a r i t h m e t i cc o d i n g ) 算术编码( a r i t h m e t i cc o d i n g ) 法不使用一个符号一个码的方式，而是一串符号用 一个实数来表示。而其输出是介于0 与1 之间的实数，利用这个实数解码端可以唯一 译码回原来的讯息。算术编码( a r i t h m e t i cc o d i n g ) 步骤如下： 第一步先计算各符号之概率，并设定各符号的范围。整个讯息的设定范围是从 o 到l ，而各符号则是视其概率大小，有其一定大小的范围。 第二步设定l o v f o 0 ，h i g h = 1 0 。 第三步读入新的符号。设定范围r a n g e = h i g h l o w = 1 0 。 第四步查范围表。令新读入符号的范围为i r “，2 ) 8 预测编码( p r e d i c t i v ec o d i n g ) ： 预测编码( p r e d i c t i v ec o d i n g ) 的想法是认为误差信号的交化要比原信号的变化小， 所以可以使用较少的位来为每一个取样傲编码以达到减少数据量的目的【1 8 。在预测 编码( p r e d i c t i v ec o d i n g ) 中，最常使用的是误差信号编码f d i f f e r e n t i a lp u l s ec o d e m o d u l a t i o n ，d p c m ) ，它是将实际之取样值和预测值相减后得到误差值，再将这个误 差值量化与编码后输出。 9 离散余弦转换( d i s c r e t ec o s i n et r a n s f o r m ，d c n 在一张单独静止的图像中，一般而言画面中的像素间的差异不会很大，彼此存在 着很大的相关性，也就是所谓空域上的冗余。离散余弦转换c t ) 是将图像数据经过 ! ! 兰皇塑塑堡堡兰塑塑坌型塑坌 一一 一一一。 数学的运算，进而转换成为频率域的表示方式，经过转换后的信号能量比原先的信号 更加集中，而大部份的能量可以集中于某些系数上，使得接下来可以利用量化的方式 来进行减少数据量的目的【2 1 。由于二维离散余弦转换( t w o 。d i m e n s i o n a l d i s c r e t e c o s i n et r a n s f o r m ，2 d d c t ) 具有高度紧束能量的特性，所以广泛地被使用， 也是m p e g 标准所采用的转换方式。而一个n n 二维d c t 转抉公式如下： d c t 矩阵如= k ( “，x ) 】。，定义 ；=“= 0 ，x = 0 ，n 一1 f ，、 ( 2 2 ) 居c o s 学一，鹏一 u “ 2 dd i s c r c t ec o s i n et r a n s f o m 。【c 】= 4 【厂m 逆变换 = 稆【c m ；【c k ( 2 3 ) 故d c t 转换是将区块内的数据依空间频率来分解，再将相同频率部份相加总形成一 矩阵，矩阵内的系数为其相对位置所代表频率的阵幅，左上角为低频系数，越往右下 角频率越高，其重要性越低，最左上角由于其水平频率和垂直频率皆为0 ，故称为直 流项( d cc o m p o n e n 0 ，其余的称为交流项( a cc o m p o n e n t ) 。由于进, t d c t 的转换只 是将数据转换至频率域，总能量不变，在数据量上也没有减少。常规的d c t 变换都是 采用浮点运算的，本文将介绍一个算法，可十分方便地构造整数到整数的d c t 变换。 将整数d c t 变换用于图像压缩就可以用整数d c t 变换进行的图像压缩。这为我们在 g p u 上进行d c t 变换提供了可能。我们将在第四章介绍整数d c t 变换。 l o 量化( q u a n t i z a t i o n ) 量化是将经过d c t 转换后的数据，除以相对应位置量化矩阵系数，然后取它的 商，对于余数则舍去或四舍五入。也就是将某一个范围的值都以同一数值代表，所以 经过量化的运算后便减少了数据量，但造成了部分信息的损失，即量化误差。一般而 言，经过d c t 转换后，能量大部份集中在直流项和直流项附近的几个交项上，也就 是能量是集中于左上方，再加上由于人类视觉特性的关系，对于高频部份反应较不敏 感，所以对于所经过d c t 转换的运算后的矩阵，我们对于越高频的部份则以较大的 量化程度，进一步来减少数据量。m p e g 2 视频标准中提供了两组量化矩阵1 1 4 1 ，一为 中国科学院自动化所硕士学位论文 使用帧i 太l ( i n t r a ) j n 缩技术的量化矩阵如图2 1 所示，另一为使用帧i n q ( n o n - i n t r a ) i 丢, 缩技 术的量化矩阵，如巨t 2 2 所示，由于帧间压缩技术是用动态补偿的方式，其区块内的能 量分布并不像帧内直接转换而来会大部分集中在左上方，而是散布于各个系数上，所 以帧间量化矩阵的系数值均为1 6 。 81 61 92 2 2 62 72 9 3 4 1 61 62 22 42 72 9 3 43 7 1 9 2 22 62 7 2 93 43 43 8 2 2 2 2 2 62 72 93 43 74 1 3 2 2 2 62 72 93 23 54 04 8 2 6 2 72 93 23 54 04 85 8 2 62 72 93 43 84 65 6 6 9 2 7 2 9 3 53 84 65 6 6 93 3 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 】6 1 6 1 6 1 6 1 6 1 6 图2 1m p e g 预设之帧内量化矩阵 图2 2m p e g 预设之帧间量化矩阵 1 1 小波变换图像压缩的发展 小波变换的最初提出是为了弥补f o u r i e r 变换在短时信号分析中的不足，以对时变 信号的频率特性进行更细致的分析。如上节所述，由于小波变换引入了尺度伸缩变换 ( 或多分辨率分析) ，它对信号频域的处理是非线性的，具有优良的时频局部性。在 d a u b e c h i e s 等人提出完备小波基的构造方法后，小波变换在信号处理和分析的各个领 域中得到了广泛研究和应用。小波变换的优异性能可以归纳为： i ) 小波变换是一个满足能量守恒方程的线性变换，能将一信号分解成对空间与尺 度的独立贡献，同时又不失原信号所包含的信息。 i i ) 小波分析相当于一个具有放大、缩小和平移功能的数字显微镜，通过检查不 同的放大倍数下信号的变化来研究其动态特性。 i i i ) 时频局部性好。巧妙地利用了非均匀分布的分辨率，较好地解决了时间与频 率分辨率的矛盾：在低频段，采用高的频率分辨率和低的时间分辨率( 即宽的时间分析 窗口) ；而在高频段则相反，与时变信号的特性形成了一致。小波变化将信号分解为对 数坐标中的相同大小频带的集合，这种以非线性的对数方式而不是以线性方式处理频 率的方法对时变信号有明显的优越性。 i v ) 可利用- - t - w g n d 、波正交基将原始图像在独立的频带与不同的空间方向上分 解，便$ 币i j n h v s ( ) k 类视觉系统) 在相应频带与空间方向选择上敏感性的不同。 小波变换用于图像压缩的研究热潮是在1 9 8 9 年m a l l a t 引入多分辨率分析与小波变 第l = 章编码理论与视频分割简介 换相结合并提出快速小波分解与重构算法( & l j m a l l a t 算法) 之后掀起的。在 2 2 】中，m a l l a t 提出了基于小波变换、采用基本标量量化的图像压缩方法。先对图像数据进行多级分 解，然后对不同的分辨率子带采用不同的量化步长进行量化编码，达到压缩的目的。 d a u b e c h i e s 基于离散滤波器迭代的方法构造了紧支集的规范正交小波基，使信号与小 波基函数的内积运算转化为简单的信号与离散滤波器的卷积运算t z 3 。从上个世纪九 十年代开始，小波变换图像压缩表现出的良好性能吸引了众多图像压缩的研究者。短 短若干年内基于小波变换的图像压缩算法取得了引人注目的结果。由于小波变换般 是对整幅图像进行分解，从而在低码率压缩时没有t j p e g 中令人讨厌的方块效应，有 效地提高了恢复图像的主观质量。 1 9 9 4 年，w s w e l d e n s 等人提出种不依赖于f o u r i e r 变换的新的双正交小波构造方 法一提升方法( l i k i n gs c h e m e ) 2 4 。提升方法的内涵是；开始用非常简单而一般的多 分辨率分析，然后逐渐向带有某一特定性质的多分辨率分析靠拢。一般称提升方法为 第二代小波构造方法。提升方案为扩展小波变换的应用领域提供了更多的灵活性。 小波图像压缩算法包括变抉、量化和无失真编码三个部分。原始图像通过小波变 换产生去相关的变换数据，变换般认为是无损的，虽然实际并不完全是这样。变换 系数被量化产生符号流，每一个符号是对应着特定的量化阶层的标记，信息的损失通 常发生在这一级。无失真编码的目的在于将符号流表示为尽可能少的数据流，该部分 通常采用熵编码，如i - l u f f m a n 编码、算术编码等。 2 2 视频分割技术评析 图像视频分割是低级计算机视觉中最基本最重要的研究内容，是成功进行图像分 析、理解与描述的关键技术，因为图像分割结果的质量直接影响尔后进行的分析、识 别和解释的质量。其应用领域包括从医学诊断中的癌细胞识别直到从遥感图片中识别 多种有用的军事或民用目标 2 5 】。图像分割可以分解为两个任务，即识别( r e c o g n i t i o n ) 和描绘( d e l i n e a t i o n ) 。识别的目的在于确定目标物体的大致位置并区别于图像中的其 它物体；而描绘的任务在于精确定义和刻画图像中目标物体的区域或边缘的空间范围 医学图像处理是数字图像处理的一个重要方面。 在m p e g 一4 的视频压缩标准中，图像序列中的每一个画面，将分割成几个视频对 象3 f 面( v i d e oo b j e c tp l a n e s ) ，每个视频对象平硒涵盖某一对象