（通信与信息系统专业论文）基于h264的熵解码与环路滤波算法的研究与实现.pdf

武汉理工大学硕士学位论文 摘要 h 2 6 4 在带来编解码效率提高的同时也带来了计算复杂度的提高。因此如何 通过软件方法降低h 2 6 4 计算复杂度以适应通用嵌入式平台，最终实现h 2 6 4 在移动终端上的应用成为各科研机构和院校的研究热点。本文的研究目标是通 过对h 2 6 4 解码程序中的耗时模块进行算法改进和代码优化，最终实现解码程序 在a r m 9 平台上的实时解码。论文的主要工作安排如下： 论文第二章是c a v l c 解码算法的研究。本章首先分析了c a v l c 熵解码过 程中影响熵解码速度的主要原因查找变长码表，同时使用测试软件进行耗 时分析找出了主要的耗时模块。然后探讨了相关文献作者优化变长码表的方法， 在此基础上，提出了一种改进的c a v l c 解码算法一基于数据存储格式和码表 地址映射的算法。通过改变数据的存储格式，可以节省存储空间；通过分析码 字的特点，确定码字与数组下标的映射关系，使用下标查找匹配信息，可以降 低查表运算。最后给出了算法的程序设计并对上述算法给出了实验证明。 论文第三章是环路滤波算法的研究。本章首先对环路滤算法中的滤波条件 判定进行了分析。通过分析找出了产生这些复杂判定条件的主要原因，因为编 码端采用了过多的预测模式，导致了滤波时严苛的判定条件。然后文章通过分 析这个判定依据的合理性，提出了以宏块边界是否平滑作为是否对宏块边界滤 波的有效依据。新算法先计算整条边界的梯度，如果梯度在给定的阈值范围内， 则判定为平滑，使用强滤波，否则分情况判断。对于宏块内的分块，则分成帧 内和帧间来讨论，帧内统一使用中等强度滤波，帧间根据选用预测块大小使用 弱滤波或不滤波。最后给出了算法的程序设计并对上述算法给出了实验证明。 论文第四章选择j m l l 3 解码部分代码作为研究对象，通过验证解码程序在 a r m + w i n c e 平台上解码实时性来验证上述改进算法的有效性和可行性。本章 首先介绍了解码程序的移植，接着重点以熵解码和环路滤波为研究对象，讨论 了解码程序的代码结构优化和基于c 语言和a r m 汇编语言优化。最后在e v c 下编写了一个播放器应用程序，通过边解码边播放的形式验证了优化后的解码 程序在a r m 平台上实时解码的可行性。 关键词：h 2 6 4 ；w i n d o w sc e n e t ；a r m ；c a v l c ：环路滤波 武汉理工大学硕士学位论文 a b s t r a c t a st h eh 2 6 4b r o u g h tc o d e ce f f i c i e n c yt h es a n l et i m eh a sa l s ob r o u g h ti n c r e a s e d c o m p u t a t i o n a lc o m p l e x i t y s oh o w t or e d u c et h ec o m p u t a t i o n a lc o m p l e x i t yo fh 2 6 4 t om e e tt h ec o m m o ne m b e d d e dp l a t f o r mb ys o f t w a r em e t h o da n di m p l e m e n tt h e h 2 6 4a p p l i c a t i o n su l t i m a t e l yo nm o b i l ed e v i c e sh a sb e c a m et h er e s e a r c hf o c u si n m a n yr e s e a r c hi n s t i t u t i o n sa n d i n s t i t u t i o n s t h es t u d yg o a li nt h i sp a p e ri st oa c h i e v e i nr e a l - t i m ed e c o d i n go na r m 9p l a t f o r mt h r o u g ha l g o r i t h mi m p r o v e m e n t sa n dc o d e o p t i m i z a t i o nf o rt h et i m e c o n s u m i n gm o d u l e so ft h eh 2 6 4d e c o d i n gp r o c e s sa n dt h e m a i nw o r ka sf o l l o w s ： t h es e c o n dc h a p t e ri nt h ep a p e ri sa b o u tt h er e s e a r c ho ft h ec a v l cd e c o d i n g a l g o r i t h m t h i sc h a p t e rf n s ta n a l y z e dt h em a i nr e a s o nw h a ta f f e c t i n gt h ee n t r o p yd e c o d i n g s p e e di nc a v l ce n t r o p yd e c o d i n gp r o c e s s f i n d i n gv a r i a b l e - l e n g t hc o d et a b l e ，a tt h es a m et i m e t e s ts o f t w a r eh a sb e e nu s e dt oa n a l y z et i m e c o n s u m i n gt oi d e n t i f yt h em a i n t i m e c o n s u m i n gm o d u l e t h e nt h i sc h a p t e ri n v e s t i g a t e dt h em e t h o da b o u tt h er e l a t e d l i t e r a t u r e sa u t h o rh o wt oo p t i m i z et h ev a r i a b l e - l e n g t hc o d et a b l e ，o nt h i sb a s i s ，t h e p a p e rp u tf o r w a r da ni m p r o v e da l g o r i t h mf o rc a v l cd e c o d i n 哥b a s e do nd a t a s t o r a g ef o r m a ta n dt h ec o d et a b l ea d d r e s sm a p p i n ga l g o r i t h m b yc h a n g i n gt h ed a t a s t o r a g ef o r m a ti nt h i sc h a p t e r ，t h es t o r a g es p a c ew a ss a v e d w ec a i ld e t e r m i n et h e m a p p i n gb e t w e e nt h ec o d ew o r da n dt h ea r r a ys u b s c r i p tb ya n a l y z i n gt h ec o d ew o r d c h a r a c t e r i s t i c s b yu s i n gt h es u b s c r i p tt of i n dm a t c h i n gi n f o r m a t i o nc a r lr e d u c et h e l o o k u po p e r a t i o na n dt h ea l g o r i t h m sc o m p u t a t i o n a lc o m p l e x i t y f i n a l l y , t h ec h a p t e r r e a l i z e da n dp r o v e dt h ea l g o r i t h m t h et 1 1 i r dc h a p t e ri sa b o u tt h er e s e a r c ho ft h el o o pf i l t e ra l g o r i t h m t b i sc h a p t e r f i r s ta n a l y z e dt h ef i l t e rd e t e r m i n i n gc o n d i t i o n si nl o o pf i l t e ra l g o r i t h m b e c a u s et h e e n c o d e ru s em a n yf o r e c a s t i n gm o d e l s ，t ol e a dt oah a r s hj u d g ec o n d i t i o n sf o rf i l t e r i n g t h e nt h ea r t i c l e p r o p o s e dae f f e c t i v ew a yb yj u d g i n gt h ei m a g em a c r ob l o c k b o u n d a r yi ss m o o t h t h en e wa l g o r i t h mf i r s tc a l c u l a t e d t h ee n t i r eb o r d e ro ft h e g r a d i e n t ，i ft h eg r a d i e n tt h r e s h o l d si nag i v e nc o n t e x t ，t ob ed e t e r m i n e da ss m o o t h ，u s e 武汉理工大学硕士学位论文 as t r o n gf i l t e r , o rp o i n t so fj u d g m e n t t h em a c r ob l o c kw i t h i nt h eb l o c kh a sb e e n d i v i d e di n t oi n t r aa n di n t e r - f r a m et od i s c u s s t h ei n t r af r a m eu s eo fm o d e r a t ei n t e n s i t y f i l t e ra n dt h ei n t e rf r a m eu s ew e a ki n t e n s i t yf i l t e ro rn o ta c c o r d i n gt op r e d i c t i o nb l o c k s i z e f i n a l l y , t h ec h a p t e rr e a l i z e da n dp r o v e dt h ea l g o r i t h m c h a p t e rf o u rs e l e c t e dj m l1 3d e c o d i n gc o d ef o rt h es t u d yo b j e c ta n dv e r i f i e dt h e e f f e c t i v e n e s sa n df e a s i b i l i t yo fi m p r o v e da l g o r i t h mi nt h i sp a p e rb yv e r i f y i n gt h e d e c o d i n gp r o c e s si sr e a l t i m ei m p l e m e n t i n go na r m + w i n c ep l a t f o r m t h i sc h a p t e r f i r s ti n t r o d u c e dt h et r a n s p l a n to ft h ed e c o d i n gp r o c e s s ，t h e nd i s c u s s e dt h ed e c o d i n g p r o c e s so p t i m i z a t i o na n dc o d eo p t i m i z a t i o nb a s e do nc a n da r m a s s e m b l yl a n g u a g e f i n a l l y , w ee d i t e dap l a y e ra p p l i c a t i o nu n d e re v ca n dv e r i f i e dt h ef e a s i b i l i t yo f r e a l t i m ed e c o d i n go ft h eo p t i m a ld e c o d i n gp r o c e s sb yd e c o d i n gs i d eb ys i d ei nt h e f o r mo fp l a y k e y w o r d s ：h 2 6 4 ；w i n d o w sc e n e t ；a r m ；c a v l c ；l o o p - f i l t e r a l g o r i t h m i i i 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其它教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 - 7 、z 签名：兰! 丝日期： 丝乜： ：) 7 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即： 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：互1 压 导师( 签名) ：育需p 期吖n 厂7 武汉理工大学硕士学位论文 第1 章绪论 1 1 课题的研究背景与意义 随着多媒体通信技术和电子技术的快速发展，数字视频技术被广泛应用于 移动通信、广播电视等领域。但是由于经过数字化处理的视频图像信号数据量 非常庞大，不利于本地存储和远程传输，因此对数字视频信号进行压缩处理和 开发各种数字视频解码软件成为当前的研究热点。 从1 9 9 3 年起，i t u _ t 等国际标准化组织陆续颁布了近十个视频编码标准， 大大推动了视频通信和数字广播电视的发展，但视频压缩比例与图像质量之间 的矛盾依然存在。2 0 0 3 年3 月，i t u t i s o 正式公布了h 2 “视频编码标准，由 于比已往其他标准具有更优越的性能，被人们称为新一代视频编码标准【l j 【2 j 。具 体讲，h 2 6 4 与h 2 6 3 或m p e g 4 相比，在同样质量下，其数码率能降低一半左 右。其次，它还对网络传输具有很好的支持功能，它支持流媒体传输以及无线 信道中抗干扰传输，支持低带宽的网络传输。 目前，视频解码器的应用越来越普遍，很多消费电子产品厂商都在自己的 产品上使用了m p e g 1 、m p e g 2 、m p e g 4 等解码器芯片，而且有些厂商还在 其产品中加入了对h 2 6 4 解码器功能的支持1 3 l 。 在数码产品方面：m p 4 、数码相机等数码产品已经成为人们生活中的日用品， 这些产品的视频解码器主要采用m p e g 2 、m p e g 4 格式，因为这两种格式的压 缩比都不高，对存储卡的容量要求较高，不适合嵌入式产品的海量存储。 在手持移动设备方面：移动设备的视频标准主要采用的是3 g p 格式，3 g p 格式的视频有一些缺点，首先，视频质量不佳，其次，通用性不强，互联网上 3 g p 格式的视频较少，需要使用视频转换软件转换。而h 2 6 4 在降低压缩率、 抗误码、抗干扰和抑制噪声等方面诸多优越性，非常适合移动方面的需求。 在数字电视方面：数字电视已成为世界电视发展的趋势。很多国家推出了 从模拟电视向数字电视转化的宏伟计划。2 0 0 2 年中国数字电视系统标准获得通 过：2 0 0 5 年全国2 5 的电视台已经开始发射和传输数字电视信号；2 0 1 0 年全国 计划全面推广数字电视；2 0 1 5 年数字电视将在全国范围内取代模拟广播电视。 武汉理工大学硕士学位论文 h 2 6 4 因其对主要档次的支持，基于h 2 6 4 标准的数字解码芯片将在数字电视领 域占据一席之地。 1 2 关键技术介绍 1 2 1h 2 6 4 标准 h 2 6 4 和以前的标准一样，也是d p c m 加变换编码的混合编码模式1 4 。但它 采用“回归基本”的简洁设计，不用众多的选项，获得比h 2 6 3 + + 好得多的压缩 性能；加强了对各种信道的适应能力，采用“网络友好 的结构和语法，有利 于对误码和丢包的处理；应用目标范围较宽，以满足不同速率、不同解析度以 及不同传输( 存储) 场合的需求。 技术上，它集中了以往标准的优点，并吸收了标准制定中积累的经验。与 h 2 6 3v 2 ( h 2 6 3 + ) 或m p e g - 4 简单类( s i m p l ep r o f i l e ) 相比，h 2 6 4 在使用与上述编 码方法类似的最佳编码器时，在大多数码率下最多可节省5 0 的码率。h 2 6 4 在 所有码率下都能持续提供较高的视频质量。h 2 6 4 能工作在低延时模式以适应实 时通信的应用( 如视频会议) ，同时又能很好地工作在没有延时限制的应用，如视 频存储和以服务器为基础的视频流式应用。h 2 6 4 提供包传输网中处理包丢失所 需的工具，以及在易误码的无线网中处理比特误码的工具。 在系统层面上，h 2 6 4 提出了一个新的概念，在视频编码层( v i d e oc o d i n g l 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 ) 之间进行概念性分 割，前者是视频内容的核心压缩内容之表述，后者是通过特定类型网络进行递 送的表述，这样的结构便于信息的封装和对信息进行更好的优先级控制。 1 2 2 熵解码 熵编码是一种无损压缩编码，它生成的码流经解码后可以无失真地恢复出 原数据。h 2 6 4 中，熵编码采用了两种方法，一种是基于上下文的可变长编码 ( c a v l c ) ，另一种是基于内容自适应的二进制算术编码( c a b a c ) 。从编码的性 能来看，采用c a b a c 编码的码流比采用c a v l c 编码的码流更接近于信源熵， 但从编码算法的复杂度来看，c a v l c 的编码复杂度只有c a b a c 编码复杂度的 一半。鉴于这种情况，标准将c a b a c 列为可选项岭】，主要应用在h d v d 和数 字电视领域。而将c a v l c 应用在可视电话、视频会议等领域。在h 2 6 4 的基本 2 武汉理工大学硕士学位论文 档次中，c a v l c 是唯一采用的熵编码方式。除了一些控制参数，其他数据( 如 m v d 、s a d ) 黼jc a v l c 编码【6 1 。采用c a v l c 熵编码的码流的解码过程如图 1 1 所示。 图1 1c a v l c 熵解码流程图 首先根据输入的参数求得输入数据的块类型，相邻宏块中非零系数的个数 等参数，随后求变量n c ，并根据变量n c 的值来选择所要查找的表格，以 c o e f ft o k e n 这个句法元素为入口参数，查找变长表格求解非零系数的个数 ( t o t a l c o e f f s ) 和拖尾系数的个数( t r a i l i n g o n e s ) 。接着求解拖尾系数的符号 和循环求解除拖尾系数外的非零系数幅值。最后求解零值的个数和每个非零系 数前连续零的个数。 1 2 3 环路滤波 在h 2 6 4 视频编解码标准中，编解码器端反变换后图像会出现方块效应。其 产生的原因有两个。最重要的一个原因在于基于块的帧内和帧间预测残差的 d c t 变换。其变换系数的量化过程相对粗糙，因而反量化过程恢复的变换系数 带有误差，会造成在图像块边界上的视觉不连续【刀，而且随着量化参数q p 的 增加，这种方块效应将更加明显，这是因为q p 的增加导致量化步长增加，从而使 武汉理工大学硕士学位论文 更多残差信息丢失。第二个原因来于运动补偿预测。运动补偿块可能是从不同 帧的不同位置上内插计算得来的。因为运动补偿块的匹配不可能是绝对准确的， 所以就会在复制块的边界上产生数据不连续。当然，参考帧中本身存在边界不 连续也被复制到需要补偿的图像块内。尽管h 2 6 4 采用较小的变换尺寸可以降低 这种不连续现象，但仍然需要一个去方块滤波器，以最大程度地提高其解码性 能。 在视频编解码器加入去方块滤波的方法有两种：后置滤波器和环路滤波器。 后置滤波器只处理编码环路外的显示缓冲区中的数据，而环路滤波器处理编码 环路中的数据。在编码器中，经环路滤波后的图像帧可以作为后续编码帧运动 补偿的参考帧；在解码器中，经环路滤波后的图像可以直接输出显示。使用环 路滤波器比后置滤波器有三处优点【8 】。首先，环路滤波器可以保证不同水平的图 像质量。其次，在解码器端没有必要再为滤波器准备额外的帧缓存。最后，环 路滤波比后置滤波能更可靠地提高图像的主客观评价质量水平，能有效的区分 真实和人为的图像边界，并对后者进行有效滤斛9 j 。 尽管环路滤有以上优点，但其实现复杂度较高。滤波器高度复杂的原因是 它具有高度的自适应性，它需要对方块边界及样点量化值进行条件判断来选择 滤波强度。这样，在算法的主要内部循环中不可避免地出现条件分支。另一个 高度复杂的原因是h 2 6 4 编码算法中残差编码的尺寸。对于4 x 4 的方块大小，平 均要在每个方向上对2 个点滤波，这样几乎图像中的每个点都要被调入到内存 中看是否要被修正。而对其他编解码器来说，他们只需要对8 x 8 方块边界进行 滤波操作，不是所有点都被纳入到计算范畴。 1 3 课题的来源及本文工作安排 本课题来源于来源于华中数控公司的车间设备运行状况监控项目，本课题 主要负责项目中终端解码显示。 本课题研究的主要内容是针对h 2 6 4 解码算法复杂度高，无法将其解码程序 直接移植到通用嵌入式平台上使用的情况，对解码算法中的耗时部分进行算法 改进和代码优化并从理论和实验上给予验证，最终达到在嵌入式终端上应用的 目的。本文共分五章进行，具体安排如下： 第一章简单介绍论文的研究背景与意义、论文涉及到的知识点、论文的主 要工作和工作安排。 4 武汉理工大学硕士学位论文 第二章研究c a v l c 熵解码算法，从数据存储格式和码表地址映射两个方面 对查找表进行优化，对改进的算法给出程序设计与验证。 第三章研究解码过程中的环路滤波算法，从图像平滑和宏块编码模式两个 方面对选择滤波模型的判定条件作出调整，加快滤波模型的选择，对改进的算 法给出程序设计与验证。 第四章首先在a r m 平台上移植h 2 6 4 的参考模型j m l l 3 的解码程序代码， 然后对程序的结构进行优化并且从c 语言和a r m 汇编语言优化的角度对部分耗 时函数进行改写，最后编写一个播放应用程序，通过验证解码程序在通用嵌入 式平台上实时解码的可行性来验证改进算法的有效性。 5 武汉理工大学硕士学位论文 第2 章c a v l c 解码算法研究 2 1c a v l c 解码算法分析 1 2 2 节中提到在c a v l c 解码过程中，求解t o t a l c o e f f s 和t r a i l i n g o n e s 需要 查找变长码表。标准算法中变长码表采用二维数组的方式存储，存储的内容为 码字，为了便于规整的存储与读取码字，所有的码字都通过在末位加零的方法 扩展成1 6 位( 标准中的最长码字为1 6 位) ，2 维下标分别代表t o t a l c o e f f s 和 t r a i l i n g o n e s 。以除拖尾系数外非零系数个数小于2 、非零系数个数小于6 的4 x 4 亮度编码块( 即：0 _ n c 2 ，t o t a l c o e f f s 6 ) 为例，该变长码表的存储结构如表2 1 。 表2 1变长码表的存储结构( x 表示不足1 6 位填充的o ) t r a i l i n g o n e s t o t a l c o e f f sb i t c o d e t r a i l i n g o n e s t o t a l c o e f f sb i t c o d e 0o1 x20x o l0 0 0 1 0 1 x2 1x 020 0 0 0 0 11 1 x 2 20 0 l x 030 0 0 0 0 0 1 1 l x230 0 0 0 1 0 l x 040 0 0 0 0 0 0 11 1 x240 0 0 0 0 1 0 1 x 050 0 0 0 0 0 0 0 11 1 x250 0 0 0 0 0 1 0 1 x 1ox30x 110 1 x3lx 120 0 0 1 0 0 x32x 130 0 0 0 0 1 1 0 x330 0 0 1 1 x 140 0 0 0 0 0 1l o x 3 4 0 0 0 0 1 1 x l50 0 0 0 0 0 0 1 1 0 x350 0 0 0 1o o x 其二维数组定义为： u s i g n e ds h o r tc o d e 3 5 = 1 x ， ； 查表求解t o t a l c o e f f s 和t r a i l i n g o n e s 的步骤如下所示： ( 1 ) 从码流中读取码字信息； ( 2 ) 从变长码表中读取一个码字； ( 3 ) 比较两个码字串，相同则该码字的下标即为所求，否则返回( 2 ) 重复。 6 武汉理工大学硕士学位论文 从查表解码的步骤可以看出，整个解码的过程就是在不断的搜索、匹配。 如果读取的码字长度越长，匹配的时间越长。另外熵编码的突出优点是对出现 概率高的信息分配较短的码字，这样便于解码时能够快速匹配，但从表2 - 1 来看， 这种优势完全无法体现出来。参考文献【1 0 】的作者曾经做过实验，采用表2 1 变 长码表解码，一次匹配命中的概率不到3 0 。 采用h 2 6 4 参考模型j m l l 3 在p c 环境下使用v c 自带分析工具p r o f i l e 对 算法进行分析，得到c a v l c 解码过程中各子任务的耗时比如表2 1 所示： 表2 2c a v l c 解码中各子任务耗比 c a v l c 解码中子任务耗时百分比m t o t a l c o e f f s 和t r a i l i n g o n e s t d t a l z e r o s r u n b e f o r e l e v e l s o t h e l - s 7 4 9 1 5 5 6 1 1 7 1 8 从表2 - 2 中可以看出，解码t o t a l c o e f f s 和t r a i l i n g o n e s 所消耗的时间接近 整个c a v l c 解码时间的7 5 。因此，当应用于嵌入式平台时需要对其改进。 2 2c a l v c 常用解码算法比较 从2 1 节中的分析可知，解决查表耗时问题的关键是合理安排码表，下面以 三种不同的变长码表算法为例，分析各自的优缺点，找出改进的途经。 2 2 1 全码表解码算法 全码表的存储结构与2 1 节中提到的变长码表存储结构不同，它采用一维数 组的方式存储，存储的内容为t o t a l c o e f f s 和t r a i l i n g o n e s ，数组下标为扩展的码 字数值大小。下标的最大值根据编码码表中码字的最大长度来定，如最大长度 为l ，则下标的最大值为2 l 1 【l l 】。一维数组的构造形式如下： t y p e d e f s t r u c t o n e t a b l e u n s i g n e dc h a rt r a i l i n g o n e s ； u n s i g n e dc h a r t o t a l c o e f f ； 7 武汉理工大学硕士学位论文 o n e _ t a b l e 2 l ； 因为一维数组是连续的，所以解码时只需要从码流中读取一个码字，扩展 成l 位后计算出大小，然后根据大小到解码码表中去查找结果。这种解码方法 非常快速，只需要一次查找就能匹配信息。但它有个明显的缺点，它只适用于l 很小的场合，随着l 的增大，这张查找表将变得非常庞大，在存储资源较少的 嵌入式设备上，这种方法是不可取的。 2 2 2 二叉树解码算法 二叉树解码方法的原理就是将二维数组存储结构的码字转化为树形存储结 构的码字，所要查找的信息都存放在二又树的叶节点上，即形成一棵二叉解码 树。解码的过程实际上就是根据比特流信息逐位寻找叶节点的过程【1 2 】。以表2 1 中的数据为例，构建的二叉解码树如图2 1 所示： 矗0 聪0 穗0 1 1 o 由晤 尚尚高 2 嚣蒜下忐 2 ，3 i1 3 ，4 起 点 图2 1 二叉解码树 图2 1 中，二叉树码表的节点定义为： t y p e d e f s t r u c tn o d e s t r u c tn o d e 奎p l e f t c h i l d 木p r i g h t e h i l d ； u n s i g n e dc h a rt r a i l i n g o n e s ； u n s i g n e dc h a r t o t a l c o e f f ； b i t n o d e ； 二叉解码树的特点是充分利用了码字的相关性和熵编码的概率分布特性， 它将出现概率高的码字排在了离根节点较近的地方，而将出现概率低的码字排 在了离根节点较远的地方。每当从码流中读取一个码字信息后，就从根节点开 始查找，具体的查找过程可以用图2 2 所示的流程图表示。 8 武汉理工大学硕士学位论文 文献 1 3 】的作者曾统计过，经过五次比特位匹配就能找到结果的概率高达 8 0 。采用这种树形存储结构的码表还有一个优点，他不用存储码字，它只要存 储一些指针地址和叶节点信息。虽然这种方法能够节省存储空间和时间，但也 不是最优的方案。1 ) 通过指针访问数据没有直接访问数组来得快；2 ) 如果遇到码 字比较长的情况，需要匹配的次数会增加不少。 读取一个码字赋值给c o d e i 读取码字中的最高位赋值给b i t c o d e = c o d e 1 l b i t - - - 0 上一i 除。l l 移动当前节点指 查找到结果 i 移动当前节点指i 1 针到左分支 针到右分支 图2 - 2 二叉树解码流程图 2 2 3 自动化码表分割的解码算法 自动化码表分割的解码算法综合了全码表解码算法和二叉树解码算法的优 点。它的解码思想是：将解码二又树进行不同长度的分割，然后逐级查找分割 表，直到找到所要的结果【1 4 】【1 5 】。 如何对解码二叉树进行不同长度的分割是算法的关键，我们先对表2 2 进行 一个统计，统计的结果如表2 3 所示： 表2 3 码字长度和对应个数统计 由表2 3 可知，存储这些码字所需最小存储空间为1 2 0 ，要想使实际分配的 存储空间最小，第一级码表必须遵循2 k 1 o 则表示所查结果r 即为 所求，否则根据r 的值查找中转表，在中转表中选择下一级码表的入口地址； ( 3 ) 取码字的剩余长度，重复第( 1 ) 、( 2 ) 步，直到查找结束，注意每次要改 变读取长度和选择不同码表。 显然使用自动化码表分割的解码算法可以大幅提高熵解码的速率【1 6 1 。与全 码表相比，它不用扩展大量的码字，减少了对存储空间的要求；而与二叉解码 算法相比，它能够一次匹配多个比特，解码速度要提高很多。实验表明，使用 该算法能够使c a v l c 在解码过程的平均耗时百分比由1 6 下降到7 5 。 虽然如此，这种自动化码表分割的解码算法也存在缺点【1 7 1 18 1 。1 ) 中转表的 使用和部分码字的扩展会减少可利用的存储空间，2 ) 中转表的使用使得该算法的 搜索速度永远无法达到全码表的搜索速度。 2 3 改进的c a v l c 解码算法 通过对前面三种常用c a v l c 解码算法的分析，我们知道了各种算法的优 劣。第一种算法提高了解码速度，但对存储空间的利用率很低；第二种算法降 低了对存储空间的使用，但解码速度提高有限，第三种方法在这两方面都做了 改进，但还是没有达到理想的效果。下面的改进算法将从降低存储空间和提高 解码速度出发，利用t r a i l i n g o n e s 和t o t a l c o e f f s 的数据相关性，将两个不同的数 据融合成一个数据，进一步减少对存储空间的使用。利用地址映射技术，将不 连续的码字映射到连续的地址空间，且整个过程没有码字扩展。 武汉理工大学硕士学位论文 2 3 1 数据存储格式 改进的算法继承了2 1 1 节中全码表解码算法的特点，用一维数组来存储 t r a i l i n g o n e s 和t o t a l c o e f f s 。三种对比算法都将t o t a l c o e f f s 和t r a i l i n g o n e s 分开 存储，每个系数占用一个字节的存储空间。如果能够将两个系数融合成一个系 数来存储，那么所需存储空间将会减少一半。 在h 2 6 4 a v c 中，t o t a l c o e f f s 的最大值为1 6 ，t r a i l i n g o n e s 的最大值为3 ， 且t r a i l i n g o n e s _ t o t a l c o e f f s ，则t r a i l i n g o n e s 和t o t a l c o e f f s 的所有组合情况如公 式2 1 所示： ( t r a i l i n g o n e s ，t o t a l c o e f f s ) = ( o ，o ) ，( 0 ，1 ) ，( o ，1 6 ) ，( 1 ，1 ) ，( 1 ，2 ) ，( 1 ，1 6 ) ， ( 2 ，2 ) ，( 2 ，3 ) ，( 2 ，1 6 ) ，( 3 ，3 ) ，( 3 ，1 6 ) )( 2 - 1 ) 采用公式2 2 计算后，新的组合情况如公式2 3 所示： t t s = t r a i l i n g o n e s 事16 + t o t a l c o e f f s( 2 2 ) t t s = 0 ，1 ，1 6 ，1 7 ，3 2 ，3 4 ，4 8 ，5 1 ，2 , - - - - - 6 4 ( 2 - 3 ) 显然组合后的系数值都小于2 5 6 ，每个系数只需要一个字节的存储空间。举 例：如果( t r a i l i n g o n e s ，t o t a l c o e f f s ) = ( 2 ，3 ) ，可求得t t s = 2 x 1 6 + 3 = 3 5 ：反之如果 t t s = 3 5 ，可求得t r a i l i n g o n e s = 3 5 1 6 = 2 ，t o t a l c o e f f s = 3 5 1 6 = 3 ，满足条件 t r a i l i n g o n e s _ t o t a l c o e f f s 。因此当查表得到t t s 后，可以很容易通过公式求得 t r a i l i n g o n e s 和t o t a l c o e f f s 的值。因为上述算法使存储空间的利用率提高了一倍， 所以非常适合嵌入式设备存储资源有限的情况。 2 3 2 码表地址映射 为了方便分析，我们先对表2 1 做一下调整，将短码字排列在前，长码字排 列在后，码字大小小的排列在前，码字大小大的排列在后，排好的码表结构如 表2 4 所示( 因原始码表太长，t o t a l c o e f f s 从6 到1 6 的码字就没有列出) ： 表2 - 4 改进的变长码表的存储结构 t r a i l i n g o n e s t o t a l c o e f f sb i t c o d e t r a i l i n g o n e s t b t a l c o e f f sb i t c o d e 0 0 1 x 25 0 0 0 0 0 0 1 0 1 x 1 1 o l x l4 0 0 0 0 0 0 11 0 x 2 2 0 0 1 x o 30 0 0 0 0 0 1 1 1 x 330 0 0 l l x 1 50 0 0 0 0 0 0 1 1 0 x 1 2 武汉理工大学硕士学位论文 t r a i l i n g o n e s t o t a l c o e f f sb i t c o d e t r a i l i n g o n e s t o t a l c o e f f sb i t c o d e l20 0 0 1 0 0 x040 0 0 0 0 0 0 1 11 x 010 0 0 1 0 1 x050 0 0 0 0 0 0 0 11 1 x 340 0 0 0 1 1 x30x 350 0 0 0 l o o x31x 230 0 0 0 1 0 l x32x 24