（通信与信息系统专业论文）运动估计搜索算法研究及dsp实现.pdf

武汉理工大学硕士学位论文 摘要 运动估计搜索算法是帧间编码的基础，常用的运动估计搜索算法采用在搜 索区域内搜索最佳s a d 匹配点来进行宏块匹配，获得宏块的运动矢量。不同的 搜索方法在搜索最佳s a d 点上采用不同的搜索策略。h 2 6 4 标准中提供了包括 全搜索法、三步搜索法、新三步搜索法、菱形搜索法等搜索方法，但目前的各 种搜索算法都存在搜索速度和精度相矛盾的问题，同时在特定的视频序列中， 搜索精度和搜索速度都有提升的空间。 本文的主要研究和工作包括以下几个方面： ( 1 ) 分析了全搜索法、三步搜索法、新三步搜索法、交叉搜索法、四步搜 索法和菱形搜索法，并对算法进行了仿真分析。仿真结果验证了在目前存在的 几种基本搜索算法中，菱形算法具有相对好的搜索性能。 ( 2 ) 在菱形算法基础上研究了方向菱形搜索算法，方向菱形搜索算法通过 采用水平方向和垂直方向模板代替菱形算法的大小模板减少了搜索点数，但存 在漏点问题。针对漏点问题，文中提出了一种改进的方向菱形搜索算法。改进 的方向菱形搜索算法通过预测宏块的运动类型采用不同的搜索模板来进行运动 估计搜索，当宏块预测为缓慢运动时采用小菱形模板，预测为剧烈运动时采用 方向性菱形模板，并采用相应的提前截止准则。仿真实验表明，与方向菱形搜 索算法相比，该算法在搜索视频序列中大部分运动为缓慢的宏块时能有效地消 除漏点现象，提高搜索的精度：同时也能减小搜索点数，提高搜索速度。 ( 3 ) 在t id m 6 4 2d s p 平台上实现了文中提出的改进的方向菱形搜索法。 通过设置p r o b e ( 探针) 断点将标准的视频序列数据加载到d s p 的缓冲区中， 对缓冲区内的数据进行处理，实现文中提出的改进方向菱形搜索算法。同时针 对h 2 6 4 标准的实时性要求，对d s p 的软件编程进行了大量的优化，确保搜索 算法能满足h 2 6 4 的要求。 改进的方向菱形搜索算法在搜索速度和精度上比传统搜索算法性能上都有 提高，具有一定的应用价值。 关键字：运动估计；搜索；方向菱形；s a d ；p s n r 武汉理工大学硕士学位论文 a b s t r a c t m o t i o ne s t i m a t i o ns e a r c ha l g o r i t h mi st h eb a s i so fi n t e re n c o d e , a n dt h e c o m m o n l ym o t i o ne s t i m a t i o ns e a r c ha l g o r i t h ma d o p t st h eb e s ts a d m a t c h e dp o i n t t oc a r r yt h r o u g ht h eb l o c km a t c hi nt h es e a r c ha r e ai no r d e rt oo b t a i nt h em o t i o n v e c t o ro f t h eb l o c lt h ed i f f e r e n ts e a r c hm e t h o d sa d o p td i f f e r e n ts e a r c hs t r a t e g i e si n t h es e a r c ho f t h eb e s ts a d i tp r o v i d e sf u l ls e a r c h 、t h r e es t e ps e a r c h 、n e wt h r e 4 s t e ps e a r c h 、d i a m o n ds e a r c hi nh 2 6 4s t a n d a r d b u ta l lo f t h e s ea l g o r i t h m se x i s tt h e p r o b l e mw h i c ht h es e a r c hs p e e dd o e s n tm a t c ht h ep r e c i s i o n ；m e a n w h i l e ，t h e r ei s p r o m o t i o ns p a c eb o t i la ts e a r c hp r e c i s i o na n ds p e e di nt h es p o c i f i c a lv i d e of r e q u e n c y n 圮m a i nr e s e a r c ha n dw o r ko f t h i sp a p e ri n c l u d es e v e r a ia s p e c t sa sf o i l o w s ： ( 1 ) a n a l y z ef l ms e a r c h , t h r e es t e ps e a r c h , n e wt h r e es t e ps e a r c h , f o u rs t e p s e a r c h , c r o s ss e a r c ha l g o r i t h m , a n dd i a m o n ds e a r c ha n dc a l l yo nt h es i m u l a t i o n n es i m u l a t i o nr e s u l tc o n f i r m st h a td i a m o n da l g o r i t h mh a st h er e l a t i v e l yg o o d p e r f o r m a n c ei nt h es e v e r a lb a s i cs e a r c ha l g o r i t h m sa tp r e s e n t ( 2 ) s t u d yt h ed i r e c t i o n a ld i a m o n da l g o r i t h mo nt h eb a s i so fd i a m o n da l g o r i t h m , a n dw ek n o wt h a tt h ed i r e c t i o n a ld i a m o n ds e a r c ha l g o r i t h mr e d u c e ss e a r c hp o i n t s t h r o u g ha d o p t i n gh o r i z o n t a la n dv e r t i c a lp l a t et or e p l a c et h eb i ga n ds m a l lp l a t eo f d i a m o n da l g o d t h a hb u tt h i sa l g o r i t h mw i l ll e a ks o m ep o i n t a i m i n ga tt h i sp r o b l e m , t h i sp a p e rp r o p o s e da ni m p r o v e dd i r e c t i o n a ld i a m o n ds e a r c ha l g o r i t h m i ta d o p t st h e t h r e s h o l dv a l u ea n du s e sd i f f e r e n ts e a r c hp l a t e st oc a r r yo nm o t i o ne s t i m a t i o n t h r o u g hp r e d i c t i n gt h em o t i o nt y p o so f t h em a c r ob l o c k ，w h e nt h eb l o c ki ss l o w , w e u s es m a l ld i a m o n dp l a t e i fn o t , w el l s ed i r e c t i o n a ld i a m o n dp l a t e c o m p a r i n gw i t l l t h ed i r e c t i o n a ld i a m o n da l g o r i t h m , t h ee x p e r i m e n ts h o w st h a t , t h i sm e t h o dc a n e l i m i n a t et h ep h e n o m e n o no fl e a k i n gp o i n t sa n di m p r o v et h es e a r c hp r e c i s i o nw h e n m o s to ft h eb l o c k sa l es l o wi nt h ev i d e of r e q u e n c y ；m e a n w h i l e , i ta l s oc a l lr e d u c e s e a r c hp o i n t sa n di m p r o v et h es p e e d ( 3 ) r e a l i z et h ei m p r o v e dd i r e c t i o n a ld i a m o n da l g o r i t h mi nt h i sp a p e ro nt h e p l a t f o r mo ft id m 6 4 2 t h r o u g hs e t t i n gp r o b et ol o a dt h es t a n d a r dv i d e os e q u e n c e d a t ai n t od s pb u f f e r , d i s p o s et h ed a t ai nt h eb u f f e r , a n dr e a l i z et h ei m p r o v e d d i r e c t i o n a ld i a m o n da l g o r i t h m a i m i n ga tt h er e a l - t i m ea p p e a lo fh 2 6 4 ，t h i sp a p e r m a k e sal o to fo p t i m i z a t i o nt od s ps o f tp r o g r a mi no r d e rt oi n s u r et h es e a r c h 武汉理工大学硕士学位论文 a l g o r i t h m f u l f i l lt h et m ea p p e a lo f h 2 6 4 c o m p a r i n g 、啊t ht h et r a d i t i o n a ls e a r c ha l g o r i t h m s , t h ei m p r o v e dd i r e c t i o n a l d i a m o n da l g o r i t h mh a sab e t t e rp r o m o t i o na tt h es e a r c hs p e e da n dp r e c i s i o n , i se a s y t or e a l i z eo nd s p , a n dh a sc e r t a i na p p l i c a t i o nv a l u e k e yw o r d s ：m o t i o ne s t i m a t i o n ；s e a r c h ；d i r e c t i o n a ld i a m o n d ；s a d ；p s n r m 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育机构的 学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权保 留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：至盈导师签名：差丝日期：鲤z 巫 武汉理工大学硕士学位论文 第1 章绪论 随着v l s i 、计算机和通信技术的迅猛发展，数字化技术越来越深刻地影响 人们的日常生活。人们对信息的需求已不局限于传统的电报电话业务，甚至连 文件传输、电子邮件等数据业务也己不能满足人们多样化的需求，人们现在期 望的是更高品质的集视频、图像、声音、文字为一体的多媒体应用服务。 众所周知，视频信息具有直观性、确切性、高效性、广泛性等一系列优点。 但是视频信息的信息量太大，若要视频得到有效的应用，必须首先解决视频压 缩编码问题，其次解决压缩后视频质量保证的问题。从1 9 4 8 年提出电视信号可 以数字化以来，图像压缩编码技术已有5 0 多年的历史，不仅在理论研究上取得 了重大进步，而且在实际应用中也获得了很大成果。1 9 8 4 年c c i t t 公布第一个 视频编码国际标准，进入9 0 年代以后，国际上先后制定了一系列图像压缩编码 标准，如用于静止图像的压缩编码标准j p e g 和j p e g 2 0 0 0 ，用于视频会议和可 视电话的h 2 6 1 、h 2 6 3 、h 2 6 4 ，用于视频存储和传输的m p e g 1 、m p e g - 2 、 m p e g - 4 标准等，这些视频编码标准都有一个共同的不断追求的目标，即在尽可 能低的码率下获得尽可能好的图像质量。 1 1 国内外研究背景及现状 h 2 6 4 a v c 是国际电信联盟i t u t 的视频编码专家组( v c e g ) 和国际化标准 组织i s o i e c 的运动图像专家组( m p e g ) 联合开发制定的一个新的视频编码标 准，它既是r r u - t 的h 2 6 4 ，又是i s o i e c 的m p e g - 4 的第l o 部分【”。 h 2 6 4 a v c 标准的制定工作可以追溯到1 9 9 8 年，当时v c e g 已经完成h 2 6 3 标准的制定工作并着手开始h 2 6 l 的研究，目标就是要制定出一个新的标准， 能够在相同的图像质量下获得比h 2 6 3 高一倍的压缩率，1 9 9 9 年9 月完成第一 个草案，2 0 0 1 年，v c e g 和m p e g 合并成立了联合视频小组( j v t ) 致力于 h 2 6 4 a v c 标准的制定，h 2 6 4 a v c 标准的目标是提供一个压缩性能优良，不受 传送网络限制( 网络“友好， ) 、实现简单、能够适用于多种需求的视频压缩方案。 2 0 0 3 年3 月，标准的研究工作己基本完成并制定了最终草案。 h 2 6 4 ，a v c 标准中采用了统一的v l c 符号编码，帧内预测，高精度、多模 武汉理工大学硕士学位论文 式的运动估计，基于4 x 4 的整数交换与量化、分层的编码语法等多种先进技术， 具有很好的压缩性能，能够适应绝大部分视频编码的需要。h 2 6 4 算法具有很高 的编码效率，在相同的重建图像质量下，能够比h 2 6 3 节约5 0 左右的码率； 对信道时延的适应性较强，既可工作于低时延模式以满足实时业务，如会议电 视等；又可工作于无时延限制的场合，如视频存储等；码流结构网络适应性强， 采用“网络友好”的结构和语法，增加了差错恢复能力，加强对误码和丢包的处理， 提高解码器的差错恢复能力，能够很好地适应i p 和无线网络的应用；在编解码 器中采用复杂度可分级设计，在图像质量和编码处理之间可分级，以适应不同 复杂度的应用。 由于h 2 6 4 为了提高编码效率，采用了许多高计算复杂度的算法，使得编解 码计算量很大，很难用软件方式进行实时编解码，同时为硬件实现编解码也增 加了难度。因此，为了使h 2 6 4 能比较容易地在低码率、高实时性的应用系统中 实现，必须采用有效、实用的快速算法对其编码算法进行优化，以提高h 2 6 4 中预测帧的编码速度，满足实时视频通信的要求。通过对h 2 6 4 编码器各个算法 模块进行的分析可以看出，运动估计i h i 是视频压缩系统中的一个重要组成部 分，它的计算量占整个编码器运算量的8 0 以上，因此，若对整个编码器进行 优化，运动估计模块应作为首选。 运动估计是视频压缩系统中的一个重要组成部分，其效率主要体现在图像 质量、压缩码率和搜索速度( 复杂度) 三个方面。其基本原理是利用视频图像 序列中相邻帧之间存在的时间相关性，建立序列相邻帧之间表达上的相互关系， 从而减少时间冗余，提高视频压缩编码的效率。 运动估计越准确，预测补偿的图像质量越高，补偿的残差就越小，补偿编 码所需位数越少，比特率越小。运动估计速度越快，越有利于实时应用。因此， 提高图像质量，加快估计速度，减小比特率是运动估计算法研究的目标。当前 常用的方法主要是通过确定初始搜索点、选取合适的匹配准则及运动搜索策略 来提高算法效率。 块匹配法b m a ”1 ( b l o c km a t c ha l g o r i t h m ) 是目前最常用的运动估计方法， 其实现效果主要取决于三个因素；匹配准则、搜索范围和搜索方式。匹配准则 多数采用绝对误差和s a d ( s u mo f a b s o l u t ed i f f e r e n c e s ) 准则，搜索范围一般以 宏块和块为单位，搜索方式是影响块匹配法性能的主要因素，也是运动估计算 法中的关键技术。 2 武汉理工大学硕士学位论文 在块匹配算法中，全搜索法f s t s - l ( f u l ls e a r c h ) 是精度最高的搜索算法， 它遍历了搜索区域的每一个点，但因其采用全局最优的搜索方法，运动估计要 占到整个编码器运算量的7 0 一9 0 ，计算量很大，难以实时处理。因此，为 了在保持图像质量不便的情况下减少运算量，人们提出许多快速运动估计算法。 三步搜索法t s s ( t h r e es t e ps e a r c h ) 【“j ，交叉法c s a t ”1 ( c r o s ss e a r c h a l g o r i t h m ) 的提出主要是通过限制搜索搜索位置的数目来减少计算量，但这些算法的第一 步搜索步长比较大，没有利用运动矢量的中心偏置分布特性，有可能将搜索引 致错误的方向，从而陷入局部最优。新三步搜索法n t s s t ”1 ( n e w ，r l l d s t e p s e a r c h ) ，四步搜索法f s s i l 4 l ( f o u rs t e ps e a r c h ) 利用了运动矢量的中心偏置分 布特性，提高了搜索速度和精度，但没有利用相邻宏块的空间相关性。由s h a hz h u 和k a i k u a n gm a 两人提出，又经过多次改进的菱形搜索法d s t l s - 2 0 l ( d i a m o n d s e a r c h ) ，在1 9 9 9 年1 0 月被m p e g - 4 国际标准采纳并收入验证模型( v m ) 。虽 然菱形算法在性能上获得了非常大的成功，但是仍然存在不足。方向性菱形算 法充分利用了运动矢量的中心偏置特性和相邻宏块在时间和空间上的相关性， 但是该算法亦存在搜索不精确的情况，在此基础上，文中提出一种改进的算法。 1 2 实验平台 文中的仿真实验在配置为p e n t i u m ( r ) i v 2 6 6 g h z w i n d o w sx p 的p c 平台下， 使用m i c r o s o f tv i s u a l c + + 6 0 作为仿真平台，仿真视频序列为8 个h 2 6 4 提供的 标准测试序列m o b i l e ，f l o w e r ，t e m p e t e ，e o a s t g u a r d ，w a t e r f a l l ，h a l l ，h i g h w a y ， c o n t a i n e r 。d s p 实现改进的方向菱形算法采用的是1 1 的t m s 3 2 0 d m 6 4 2 试验箱 作为移植平台，采用的视频序列为w a t e r f a l l 标准序列。 1 3 组织结构与工作 全文分六章，内容安排如下： 第一章为绪论，简要介绍h 2 6 4 a v c 视频编码标准的国内外研究背景及现 状，并介绍文中实验所使用的实验平台。 第二章概述h 2 6 4 a v c 视频编码标准及其编码框架，并详细介绍其关键技 术。 第三章对运动估计算法及匹配准则进行介绍，并详细分析了块匹配算法中 3 武汉理工大学硕士学位论文 的全搜索法、三步搜索法、新三步搜索法、交叉搜索法、四步搜索法和菱形搜 索法，并仿真分析了各种搜索算法的性能。 第四章在对方向性菱形算法的研究的基础上，针对水平和垂直搜索遗漏中 心点两旁的点，造成搜索不精确的情况，提出了一种改进的方向性菱形算法， 并在v i s u a l c + + 6 0 的环境下实现改进的算法的仿真，仿真结果验证了文中提出 的改进的算法具有更好的搜索性能。 第五章介绍了d s p 硬件平台和软件环境，实现了对改进的方向菱形算法在 d s p 平台的移植。 第六章全文的总结和展望。 4 武汉理工大学硕士学位论文 第2 章h 2 6 4 a v c 标准及关键技术 h 2 6 4 是i t u - t 视频编码专家组和i s o ，i e c 移动图像专家组制定的新一代视 频压缩编解码标准方案。国际电信联盟将该系统命名为h 2 6 4 a v c ，国际标准化 组织和国际电工委员会将其称为1 4 4 9 6 1 0 m p e g - 4a v c 。通过该标准，在同等 图象质量下的压缩效率比以前的标准提高了2 倍以上，因此，h 2 6 4 被普遍认为 是最有影响力的行业标准。 h 2 6 4 a v c 编解码框架见图2 - 1 所示。其中e 为当前帧，一。为参考帧，一 为重建帧，p 为预测值p r e d 。 图2 - 1h 2 6 4 编码器框架图 h 2 6 4 编码器采用的是变换和预测的混合编码法，输入的帧或场e 以宏块为 单位被编码器处理。首先，按帧内或帧间预测编码的方法进行处理。如果采用 帧内预测编码，其预测值p r e d 是由当前片中已编码的参考图像经运动补偿m c ( m o t i o n c o m p e n s a t i o n ) 后得出的，其中参考图像用一，表示。为了提高预测精 度，从而提高压缩比，实际的参考图像可在过去或未来已编码解码重建和滤波 的帧中进行选择。 武汉理工大学硕士学位论文 预测值p i l e d 和当前块相减后，产生一个残差块珑，经块变换、量化后产 生一组量化后的变换系数x ，再经熵编码，与解码所需的一些边信息，( 如预测 模式量化参数、运动矢量等) 一起组成一个压缩后的码流，经n a l ( 网络自适 应层) 供传输和存储用。 2 1 2i 1 2 6 4 的档次和级 h 2 6 4 规定了三种档次，每个档次支持一组特定的编码功能，并支持一类特 定的应用。 ( 1 ) 基本档次；利用i 片和p 支持帧内和帧闻编码，支持利用基于上下文 的自适应的变长编码进行的熵编码( c a v l c ) 。主要应用于视频会议、可视电话、 远程医疗、无线通信等实时视频通信。 ( 2 ) 主要档次：支持隔行视频，采用b 片的帧间编码和采用加权预测的帧 内编码；支持利用基于上下文的自适应的算术编码( c a b a c ) 。主要应用于消费 电子应用，如数字广播电视于数字视频存储。 ( 3 ) 扩展档次；支持码流之间有效的切换( s p 和s i 片) 、改进误码性能( 数 据分割) ，但不支持隔行视频和c a b a c 。主要用于流媒体中，如视频点播。 2 2i l 2 6 4 a v c 的关键技术及研究现状 与已经制定的视频编码标准h 2 6 1 2 3 和m p e g - i 2 4 相比，h 2 6 4 具有最高 的编码效率，良好的网络亲和性，对实现实时视频通信具有十分重要的作用。 h 2 6 4 的显著特点包括4 x 4 的整数d c t ( d i s c r e t e c o s i n e t r a n s f o r m ) 变换、更精 确的i 帧( i n t r a 帧，帧内帧) 帧内预测编码、i 4 像素运动估计、多参考帧1 2 1 1 以 及p 帧( i n t e r 帧，帧间预测帧) 的多种块尺寸运动预测，这些特点使得h 2 6 4 的编码效率大幅度提高。 2 2 1 帧内预测 帧内预测1 2 2 - 2 4 1 是h 2 6 4 标准的重要特性之一，它充分利用了图像的空间相 关性，根据相邻已编码过的相邻块的信息来预测当前块的信息，并且只对预测 差值进行变换编码，以消除空间冗余。因此，在对一给定的宏块编码时，首先 可以根据周围的宏块预测，然后对预测值与实际值的差值进行编码，这样，相 6 武汉理工大学硕士学位论文 对于直接对该帧编码而言，可以大大减小码率。 h 2 6 4 提供了三种帧内预测方式：基于4 x 4 亮度块的帧内预测，基于1 6 x 1 6 亮度块的帧内预测，基于8 x 8 色度块的帧内预测，并且为每一种预测方式提供 多种预测模式。当帧内编码图像的某个部分具有较多细节，变化相对较大、包 含多个不同对象的区域时，使用基于4 x 4 的块模式对该部分图像进行预测和编 码，以提供足够的预测精度1 2 ”。在图像平坦区域使用1 6 x 1 6 亮度块帧内预测， 预测值和原始值是很接近的，可以节约很多的比特数1 2 6 1 。帧内编码宏块的8 x 8 色度成分由已编码左上方色度像素的预测而得，两种色度成分常用同一种预测 模式。由于人眼视觉系统对色度变化的敏感性低于亮度变化，因此对8 x 8 色度 宏块帧内预测，所需预测模式只有4 种，类似于帧内1 6 x 1 6 预测的4 种预测模 式，其中d c 为模式0 ，水平为模式1 ，垂直为模式2 ，平面为模式3 。 驴酽 旷 图2 - 24 x 4 亮度块9 种预测模式 橱趱 h f ”零孽 v爹m e a n ( h + v ) 鬟 ” g 纛虢舔瞧蕊剥 图2 - 31 6 x 1 6 亮度块4 种预测模式 7 h l 7 刁 v 眵。i 麓鑫瀚蘸勰瓣勰渊 武汉理工大学硕士学位论文 2 2 2 帧问预测 帧间预测编码利用连续帧中的时间冗余进行运动估计和补偿。h 2 6 4 帧间预 测1 2 q 是利用已编码视频帧场和基于块的运动补偿的预测模式，其运动补偿支持 以往的视频编码标准中的大部分关键特性，而且灵活地添加了更多的功能，采 用不同大小的预测块进行运动估计；采用1 4 ( 甚至1 8 ) 像素精度的运动补偿 算法；采用多参考帧进行帧间预测编码；去块滤波器消除由块预测误差产生的 块效应；除了支持p 帧、b 帧外，还支持一种新的流问传送帧- _ s p 帧，码流 中包含s p 帧后，能在有类似内容但有不同码率的码流之间快速切换，同时支持 随机接入和快速回放模式。 h 2 6 4 标准中对帧间预测时的每个1 6 x 1 6 宏块根据不同的语法，将每个亮度 宏块划分成形状不等的区域，作为运动描述区域。其划分方法有1 6 x1 6 ，1 6 x 8 、 8 1 6 、8 x 8 共四种。当选用8 x 8 方式时，可以进一步划分成8 8 、8 x 4 、4 x 8 、和 4 x 4 共4 个子区域，其中色度块为亮度块的1 4 ，每个宏块的编码顺序如图2 - 4 所示。每个区域包含自己的运动向量，每个运动向量和区域选取信息需通过编 码传输。当选用较大区域时，用于表示运动向量和区域选取的数据量减小，但 运动补偿后的残差会增大。当选用小区域时，残差减小，预测更精确，但用于 表示运动向量和区域选取的数据量增大。大区域适合反映帧问同质部分，小区 域适合表现帧间的细节部分。 口田目田 田嚣圈 图2 - 4 宏块划分方式 由于采用不同大小的块进行帧问预测。使得运动估计模型更接近物体的实 际运动。因此，运动补偿的精度更高。这种方法比只使用1 6 1 6 块的预测方法 提高1 5 以上的编码率。 8 武汉理工大学硕士学位论文 2 2 3 整数变换 每一个残差宏块都要经过变换，量化和编码。先前的编码标准，如m p e g - l ， m p e g 2 ，m p e g - 4 和h 2 6 3 充分利用了8 x 8 离散余弦变换( d c t ) 作为基本 交换。与以往的压缩标准不同的是，h 2 6 4 中采用了三种变换：1 6 x 1 6 帧内预测 模式宏块的4 x 4 像素块的亮度直流系数采用h a d a m a r d 变换；任何宏块内的2 x 2 色度直流系数采用2 x 2 的h a d a m a r d 变换；对于其他的4 x 4 块的残差数据采用基 于d c t 改进的整数变换 2 a - 2 9 1 。 在具有4 x 4d c t 变换所有特性的同时，还具有以下特性：( 1 ) 所有操作使 用整数算术运算，从而保证了精度；( 2 ) 变换的核心操作没有乘法运算，只有 加法和位移；( 3 ) 变换的比例系数可以整合到量化器中，减少了运算量和复杂 度。为了进一步利用图像的空间相关性，在对色度分量的预测残差和1 6 x 1 6 帧 内预测的预测残差进行整数d c t 变换之后，标准还将每个4 x 4 变换系数块中的 d c 系数组成2 x 2 或4 x 4 大小的块，进一步做哈达玛( h a d a m a r d ) 变换 2 2 4 量化 量化是数据压缩中很重要的一步，h 2 6 4 的量化与以往的视频编解码标准相 比有其不同之处，变换系数通过无扩展的分计量化进行量化。其基本公式如( 2 1 ) 所示。 z 一一d c 去 沼， 其中z 为量化值，y 为输入系数值，q 。为量化步长。量化步长共有5 2 种， 每个宏块的量化步长由量化参数( q p ) 决定。q p 每增加1 ，量化步长就增加 1 2 5 。有些时候，亮度系数的量化非常粗糙，而色差信号在量化时则采用了这 种更精细的量化步长，因而色差信号的保真度较亮度系数大有改善。由于把交 换和量化融合在一起，因而有效地减少了压缩编码的运算量。h 2 6 4 的变换量化 的全过程可以描述为：对输入的4 x 4 采样差值x 进行w = c ，嬲；的变换，然后 进行量化。 h 2 6 4 还提供了自适应块变换( a b t ) ，它能够根据分块的尺寸调整变换和 量化的参数。量化后的变化系数对应于各种不同的频率。矩阵左上角的系数代 表直流值，而其他部分的系数则代表各种非零的频率值。 9 武汉理工大学硕士学位论文 2 2 5 熵编码 视频编码处理的最后一步就是熵编码，熵编码【驯是无损压缩编码方法，目 的是产生具有最小冗余的码字，它利用信源的统计特性进行码率压缩，通过赋 给概率大的符号( 串) 以较短的码字，将描述视频流的符号流编码成适合传输 或存储的压缩比特流，生成的码流可以经解码无失真地恢复出原始数据。 设信息熵x 可发出的消息符号集合为a = k ，l i = 1 , 2 ，肌 ，并设x 发出符号 q 的概率p ( a j ) 为，则定义符号a ，出现的自信息量如公式( 2 - 2 ) 所示。 x ( a 。) = 一l o g p ( a 。) ( 2 - 2 ) 通常，上式中的对数取2 为底，这是定义的信息量单位为“比特袖i t ) 。 如果各符号a 的出现是独立的，那么x 发出一符合序列的概率等于各符号 的概率之积，因而该序列出现的信息量等于相继出现的各符号的自信息量之和。 这类信源称为无记忆信源。 对信息源x 的各符号的自信息量取统计平均，可得平均信息量如公式( 2 3 ) 所示。 日) = 一p ( a , ) l o g ：p ( a ；) ( 2 - 3 ) t = 1 日伍) 称为信息源x 的熵( e n t r o p y ) ，单位为b i t g 号。它通常也称为x 的 一阶熵，表示信息源x 发任意一个符号的平均信息量。 在h 2 6 4 标准中采用了两种熵编码，一种是基于上下文白适应的可变长编码 ( c a v l c ) ；另种是基于内容的自适应二进制算术编码( c a b a c ) 。 ( 1 ) c a v l c 在h 2 6 4 的c a v l c 中，通过根据已编码句法元素的情况，动态调整编码中 使用的码表，取得了极高的压缩比。 c a v l c 用于亮度和色度残差数据的编码。残差经过变换量化后的数据表现 出如下特性：4 x 4 块数据经过预测、变换、量化后，非零系数主要集中在低频 部分，而高频系数大部分是零；量化后的数据经过锯齿形( z i g - z a g ) 扫描，d c 系 数附近的非零系数值较大。c a v l c 充分利用残差经过整数变换、量化后数据的 这些特性进行压缩，可进一步减少数据中的冗余信息，为h 2 6 4 卓越的编码效率 奠定了基础。 ( 2 ) c a b a c 1 0 武汉理工大学硕士学位论文 算术编码是一种高效的熵编码方案，其每个符号对应的码长被认为是分数。 由于对每一个符号的编码都与以前编码的结果有关，所以它考虑的是信源符号 序列整体的概率特性，而不是单个符号的概率特性，因而它能够更大程度地逼 近信源的极限尚，降低码率。c a b a c 比c a v l c 压缩效率高，但要复杂一些。 概括起来，c a b a c 有3 个主要特点： 内容建模提供编码符号条件概率分布的估计。利用适当的内容模型，在 编码当前符号时，根据已编码的临近符号的概率统计，在不同的概率模型问转 换，借此去掉符号闯的冗余。 算术编码可以给每一个符号字母分配非整数比特，因此符号能以接近它 的熵率被编码。这对概率 o 5 的符号很有效。如果选择了高效的概率模型，符 号概率常常大于0 5 ，这时分数比特就比u v i 。c 的整数比特( 至少l 比特) 高 效得多。 自适应的算术编码可以使熵编码器自适应动态符号的概率统计。一般情 况下，运动向量的概率统计随空间、时间的不同，或序列、比特率的不同可以 发生较大的变化。因此，自适应模型由于充分利用已编码符号的概率统计，可 使算术编码更好地适应当前符号的概率，从而提高了编码效率。 h 2 6 4 a v c 标准是视频编码的最新标准，比h 2 6 3 + + 及以前的标准增加了许 多瓤的技术，其中的熵编码技术也得到了改进。h t 2 6 4 ，怂，c 标准中的熵编码技术 由于采用了c a v l c 和c a b a c 编码，尤其是使用了c a b a c 后，使得编码效率 大大提高，但相应的计算量和复杂度也提高了。但由于现在芯片处理能力的巨 大进步，复杂度已经被人们接受，同时也提供了实现的可能性。 2 2 6 算法的分层结构 h 2 6 4 编码算法总体上分为两层：视频编码层( v i d e oc o d i n gl a y e r ，v c l ) 完成对视频内容的有效描述，尽可能地独立于网络的情况下进行高效地编解码； 网络提取层( n e t w o r ka b s t r a c t i o nl a y e r ，n a l ) 负责将v c l 产生的比特字符串适 配到各种各样的网络和多元环境中。 v c l 与2 6 3 + 算法一样，都是采用基于块的编码算法，差别在于v c l 的 编码算法更加灵活，且加入了一系列新的编码方法来提高编码效率。在v c l 和 n a l 之间定义了一个基于分组方式的接口，打包和相应的信令属于n a l 的一部 分。这样，高编码效率和网络友好性的任务分别由v c l 和n a l 来完成。因此， 武汉理工大学硕士学位论文 v c l 的设计目标是为了提高编码效率，而n a l 是解决视频q o s ( 服务质量) 与网 络o o s 的适配。 v c l 主要研究基于常规的运动补偿、系数变换编码、熵编码等编码技术来 提高视频信号编码效率，使用的最基本的表示法是切图( s l i c e ) 技术，即将一个待 处理的图像分割成许多宏块来进行处理。一般而言，v c l 主要包括4 个重要方 面的技术： 降低对视频帧的处理时间：通过将每个视频帧划分成由点阵组成的块， 将对视频帧的处理降到对块的处理。 降低视频帧在空间的冗余量：通过变换、量化和熵编码方式对原始块进 行编码。 在有效帧的宏块之间进行时间独立性分析，采用运动估计和补偿技术只 对那些在有效帧之间变化的数据进行编码。 通过对残差块的编码对视频帧中所残存的任何空间冗余进行利用。 除了研究提高编码效率和简化语法形式之外，为了实现“网络友好”和无缝传 输v c l 数据，n a l 将v c l 从具体的传输层中抽象出来，定义了一个基本的和 独立于网络的表示法。网络提取层( n a l ) 负责使用下层网络的分段格式来封装 数据，包括组帧、逻辑信道的信令、定时信息的利用或发序列结束信号。 2 3 本章小结 本章首先给出了h 2 6 钔w c 编码框架图，介绍了h 2 6 4 的档次和级，初步 对h 2 6 4 a v c 有了一个了解，然后对h 2 6 4 a v c 视频编码标准中关键技术做了 详细的介绍。h 2 6 4 a v c 针对不同视频内容，采取了一系列自适应的预测和编码 算法，大大提高了编码效率，相比其他编码标准，h 2 6 4 具有优异的压缩性能。 武汉理工大学硕士学位论文 第3 章运动估计算法研究与仿真 对于视频序列图像，由于相邻帧之间存在很大的时间相关性，即时间冗余 t r ( t e m p o r a lr e d u n d a n c y ) ，在一般情况下，相邻帧间的内容实际相差不多，而 且有很大一部分甚至是完全一样的，所以通过减少时间冗余，可以大幅度提高 视频压缩编码的效率。 将活动图像分成若干块或宏块，设法搜索出每个块或宏块在邻近帧图像中 的位置，并得出两者之间的空间位置的相对偏移量，得到的相对偏移量就是通 常所指的运动矢量m v ( m o t i o nv e c t o r ) ，得到运动矢量的过程称为运动估计。 3 1 运动估计原理 运动估计研究的主要内容是如何快速、有效地获得有足够精度的运动矢量。 运动估计的基本思想是将图像序列的每一帧分成许多互不重叠的宏块，并认为 宏块内所有像素的位移量都相同，对于当前帧中的每一块到前一帧或后一帧某 一给定搜索范围内根据一定的匹配准则找出与当前块最相似的块，郎匹配块， 由匹配块与当前块的相对位置计算出运动位移，所得运动位移即为当前块的运 动矢量。利用搜索到的运动矢量在参考帧上进行运动补偿，补偿残差( d i f f e r e n c e ) 经d c t 变换、量化、行程编码后与运动矢量共同经熵编码，然后以比特流形式 传出去。 运动估计算法多种多样，大体上可以把它们分成四类：块匹配、递归估计 法、贝叶斯估计法和光流法。块匹配运动估计算法因其具有算法简单、便于v l s i 实现等优点而得到了广泛应用。 3 1 1 像素递归法 像素递归法首先是由n e t r a v a l i 和r o b b i n s 于1 9 7 9 年提出的p 1 1 。该方法根据 像素亮度的变化和梯度，通过递归修正的方法估计每个像素的运动矢量，对物 体的运动有很高的灵敏度，运动估计精度高。但由于其跟踪单元小，导致它可 武汉理工大学硕士学位论文 以跟踪的位移范围小，对运动剧烈的序列效果不好，而且由于计算量大，硬件 实现复杂度较高，一般较少被采用。 3 1 2 块匹配法 运动估计块匹配法的基本思想是将图像序列的每一帧图像分割成一系列宏 块图像，宏块大小为m x n ( 一般取8 x 8 ，8 x 1 6 或1 6 1 6 ) 。把对单个像素的处理 转化为对宏块的处理，认为宏块中所有的像素单元具有相同的位移矢量。计算 当前帧中每一宏块与相邻帧中的各宏块的误差函数，把具有最小误差的相邻帧 的对应宏块作为当前块的预测块，并把两块的相对位移定义为整个宏块的位移 矢量即运动矢量。视频压缩的时候，只需保存运动矢量和残差数据就可以完全 恢复出当前块。运动估计越准确，补偿的残差就越小，编码的效率就越高，解 码出来的图像质量就越好。 3 2 块匹配准则的选取 运动估计算法中常用的匹配准则 3 2 , 3 3 1 有三种，即最小绝对差( m a d ) 、最小 均方误差( m s e ) 和归一化互相关函数( n c c f ) 。 ( 1 ) 最小绝对差 心d ( i , j 3 2 赤蚤善l ( 叫一九( 所咖+ 州( 3 - 1 ) 式( 3 - 1 ) 中，( i ，j ) 为位移矢量，兀和六一。分别为当前帧和上一帧的灰度值，m x n 为宏块的大小，若在某一个点( f o ，。)m a d ( i o ，y o ) 达到最小，则该点为要找的 最优匹配点。 ( 2 ) 最小均方误差 射蹬( f ，d = 嘉薹耋阮( 聊，力一以1 ( 聊+ 珈+ d 1 2 ( 3 - 2 ) m s e 值最小的点为最优匹配点。 ( 3 ) 归一化互相关函数 1 4 武汉理工大学硕士学位论文 以( 训山( “州) n c c f ( i , 俨i - 譬薪瓦可( 3 - 3 ) ie e e 2 ( 掰，n ) il _ 1 2 劬+ f ，拧+ 圳 l m t l 月，ljl m = ln - lj n c c f 值最大的点为最优匹配点。 在运动估计中，匹配准则对匹配的精度影响不是很大，由于v l a d 准则不需