网络出版时间：2011-7-20 15:14
网络出版地址：wwwki/kcms/detail/11.2127.tp.20110720.1514.032.html
2011-4-14
韩一石， 王建华，黄明政， 孙运龙
Han Yi-Shi，Wang Jian-Hua, Huang Ming-Zheng , Sun Yun-Long
广东工业大学 信息工程学院，广东省 广州市 510006
Department of Information Engineering, Guangdong University of Technology, Guangzhou 510006, China
An Optimized CA VLC Decoding Algorithm Based on indexing query
摘 要：针对CAVLC解码算法中码表查算法存在运算量大和复杂度高的问题，本文在分析研究CA VLC码 表结构特征的基础上提出一种新CA VLC解码优化算法。该算法基本思路是对CAVLC码字前缀0的个数进 行一级索引，对码字后缀进行二级索引，由一二级索引查询快速得到解码输出。测试结果表明，相比原算
法，新优化解码算法在解码时间，存储空间方面都有显著的提高。
关键词: CAVLC码表；索引技术；H.264；熵编码 Abstract: In this paper, we propose a new CA VLC decoding algorithm which based on the analysis of the
structure of CA VLC code table, aiming to solve the problem of large computing and high complexity during
lookup the code table. The basic idea of this algorithm is to take the numbers of zero in CA VLC code prefix as the
primary index and to take the CA VLC code suffix as the secondary index, so to get the decoded output quickly by
the primary index and the secondary index. The results show that the new algorithm has improved significantly in
the decoding time and storage space, comparing with the original algorithm.
Key words: CA VLC codebook ; index techniques;H.264; Entropy coding
中图法分类号TN919.81 文献标示符A
1 引言
H.264是ITU-VCEG(Video Coding Experts Group)和ISO MPEG(Moving Picture Experts
Group)共同制定的视频压缩编码国际标准，它具有高编码压缩效率、友好的面向网络接口和
在较低带宽上提供高质量图像传输的特点，在数字视频通信和存储领域得到了越来越广泛的
应用，被普遍认为是最有影响力的行业标准。
CAVLC（基于上下文自适应的可变长编码）是H.264标准中熵编码的一种常见方式，它根据视频流的不同而动态的在多组结构不同的码表中进行切换，以提高编码效率。但在熵编
凡宇资讯码效率提高的同时，解码的复杂度和运算量也随之增加，其高性能的获得是以增加其编解码
的复杂度为代价的。据估计，H.264解码复杂度约相当于H．263的2倍，CAVLC的解码算法
的复杂度高会直接影响到相关视频解码方面工作的效率。因此对解码算法的优化成为当前研
究的一个方向。本文先对CAVLC的解码原理及过程作介绍，接着对CAVLC解码算法复杂度进
行分析，在此基础上提出了一个基于索引技术解码查表方法，此方法既可提高查表速度又可
节俭存储空间，大大提高了解码器整体性能。
2 CAVLC解码原理及复杂度分析
CAVLC是对早期UVLC（统一的可变长编码）的一种改进，它利用相邻的4×4变换块之间的关系来提高熵编码的效率，根据已编码语法元素的情况动态调整编码中使用的码表，为所
要编码的符号选择合适的上下文模型，其主要用于亮度块和度残差块编码上。CAVLC解码
具体过程为：取码表中的一个码字，根据码字长度从码流中取出相应长度的bit串，比较此
作者简介：韩一石（1970-），副教授，硕士生导师，主要研究方向：无线视频传输，图像处理，光通信网
络，城域网技术；；王建华（1982-），硕士生，主要研究方向：3G无线视频传输；
码字和bit串，若相同则表示查成功，然后从码字中获取对应的语法元素，否则取码表中的下一个码字，继续循环上述操作，直到解码完成。由于CAVLC解码是通过不断的搜索和判断最后得到码字和码长，所以从本质上说它既是一种搜索方法，也是一个查表判断的过程。解码搜索和查表判断时间的高低直接影响着其解码器的性能，所以我们需要对CAVLC解码器的搜索和查表算法做些改进和优化，来提高解码器的整体解码速度。目前，常见的CAVLC解码方法包含以下几种。
(1) 全码表解码方法
由于编码码表中的码字是以非连续的方式存在的，因此可以通过对每个码字的扩展来构建一张连续的解码码表[2]。解码时只需一次性读取特定比特，按其大小到解码码表中查即可。此解码方法的优点是查速度快，只需一次比较就能完成，但缺点是需要极大的存储空间。
(2) 二叉树解码方法
将码表存储结构转换成树型结构，就形成了二叉树解码树，解码过程就是寻节点的过程。此方法虽
然充分利用了码字之间的相关性，消耗很少的存储空间，但它是以一个比特作为比较对象来解码的，所以其解码速度非常慢[3]。
(3) Hashemian解码方法
Hashemian解码方法[4]是上述全码表解码方法和二叉树解码方法的有效结合。此方法通过一次比较特定的比特来提高解码速率，同时使用码字分割技术来减少存储空间。但缺点是它无法充分利用一个已经给定的存储空间而且中转码表的使用更加减少了存储空间的利用率。
通过分析发现，在CAVLC解码过程中，导致CAVLC解码运算量大，复杂度高，解码效率低下的主要原因有：
1)码表存储结构的复杂性；CAVLC码表存储结构为二维性，对于一个二维码表，若通过其残酷的欲望
坐标查对应的内容是很容易的，而反过来，要通过内容查对应的坐标，就需要对整个表进行遍历。只有当输入的码流的字长和数值同时唯一确定才能得到一个正确的输出。CAVLC码表存储结构二维性大大加大了其解码的复杂性，使解码运算性大增
2)解码系数的多样性；CAVLC的每一个系数都对应着有各自多个的码表，而码表结构复杂，
种类繁多，需花大量的计算去做解码匹配过程，增加CAVLC的解码复杂度和运算量
3)变长编码的码长不定性；CAVLC变长编码的码长是不定的，而解码输人的码流是连续的，
中间没有间隔符，所以CAVLC熵解码器必须从连续的比特流中分辨各个长度不同的码字，而对码流不定长度的判断也会大大增加了解码的困难。
总之， CAVLC的解码需要全搜索来遍历整个码表，通过不断的搜索和判断而得到最后码字和码长的，因而解码效率比较低，在实际的应用中难于满足实时性的要求。故需对解码算法进行优化，以减少解码的运算量和复杂度，提高解码系统的运行速度。
3 改进的变长码表查算法
法希文
本文提出一种新的CAVLC码表解码算法，其基本思路是到一种利用码字前缀0的个数和码字长度之间特殊关系，快速确定码字后缀输入的方法；结合索引技术，对CAVLC的码字前缀0个数进行一级索引，对码字后缀数进行二级索引，由一二级索引，快速查询得到所需解码输出。
索引也叫“引得”，是一个单独的、物理的数据结构，用来快速访问数据库表中的特定信息，常用在经常查询的大量数据上。使用索引技术，能大大加大数据的检索速度，减少数据查询中分组和排序的时间，其解码过程如下：
Step1：根据变量NC（Number Current，当前块值）的取值范围，确定所要查的码表；
Step2：制作码字前缀0的个数和码长对应关系表，
Step3：读入码流，计算码流前缀0的个数；
Step4：根据码字前缀0的个数和码长对应关系，确定码流后缀长度和数值；
Step5：将码流前缀0的个数进行一级索引，码流后缀进行二级索引，由一二级索引查表确定解码输出。
这里我们以亮度块码表系数coell_token为例，分析利用索引技术快速解码查表方法。在解码前，需根据NC的取值范围，确定所要查的码表，其中NC值的确定规则如下：度的直流系数NC=-1；其他系数类型NC值根据当前块左边4*4块的非零系数数目（NA）当前块上面4*4块的非零系数数目（NB）求得的。常用的NC的取值范围有0≤NC＜2，2≤NC＜4，4≤NC ＜8和 NC≥8。
对标准的CAVLC码表结构进行分析[6]，可以发现标准的CAVLC码表中的码字与TotalCoeff 和Tls值之间存在有一定的一一对应关系。表1所示为NC取值值变化情况下，标准CAVLC码表中码字与TotalCoeff和Tls值之间部分对应关系。
进一步，我们根据CAVLC码表制作索引表，索引表制作规则为：以码流前缀0的个数为一级索引，以码字后缀位数为二级索引，由一二级索引共同组成一个新索引号，索引号对应的存储空间用以存放由Tls和TotalCoeff组成的索引值。其中索引值的高3位为Tls值，低5位为TotalCoeff值。进行CAVLC码表查时，首先通过码流前缀0的个数和码字后缀位数共同确定一个新索引，再由这个新索引号快速定位到其对应的索引值，从而快速确定所需Tls和TotalCoeff值。
表3为0≤NC＜2情况下，CAVLC码表得到的索引表。其中索引号由码字前缀0的个数和码字后缀组成，索引值由Tls和TotalCoeff组成，索引值前3位表示Tls，范围为0到7，后5位表示TotalCoeff，范围为0到31。在优化算法中，把TotalCoeff和Tls的信息写在同一个码字中能更加充分的利用给定的空间，也是索值存储的需要。预先写入的过程与其后查的过程相
反，目的是能够快速，准确的查对应的TotalCoeff和Tls值。
表3 由CAVLC码表制作的索引表（0≤NC＜2）
为了测试全搜索算法和优化算法在解码查表速度方面的性能，本文通过对比readSyntaxEiement_NumCoeflTrailingOnes函数在全搜索算法和优化算法中执行所占用的时间的百分比来衡量算法的效果，得到结果如表5所示。
表5 解码查表占用百分比（%）
从表5我们可以看出，优化后的解码算法明显比原解码算法所需时间减少，其减少主要原因有：
a)利用了码字前缀0的个数和码字长度之间特殊关系快速确定输入码字后缀的位数和数
值；根据它们之间这个对应关系，使解码时对输入码字后缀不定长取值变为定长取值，不定长解码变为定长解码，大大缩短了码字重复判断所带来的时间延迟和减少了码字查询次数；
b)解码查表使用了索引查询技术；把码字前缀0的个数作一级索引，码字后缀作二级索引，
由一二级索引直接查询得到输出，只需一次查表便可得到输出，大大加快了数据的搜索速度，避免了
对CAVLC码表进行遍历，重复确认和判断码字的操作，极大提高解码器的性能。
由于CAVLC解码查表采用了索引查询的技术，在提高解码查表速度的同时也大大节省存储空间。以CAVLC码表存储空间占用为例，由于新算法使用索引查询，查表只需存储索引号和储索值，一个码字占用两个存储空间，一个CAVLC码表总占用存储空间为：124B
（62x2=124B），而一个CAVLC原码表占用总存储空间数为：224B（62x3+38=224B，38表示一个CAVLC中有38个码字需2字节存储），相比之下，新算法比原算法可以节省100B
（224-124=100B）存储空间，又由于常用的NC取值有4个，对应4个不同的CAVLC码表，所以用新算法一共可节省400B(100x4=400B) ，存储空间利用率提高44.6%。
使用优化后的查表算法，在解码速度和存储容量有了显著的提高的同时图像的质量没有丝毫下降，优化效果理想，是一种具有可行性的优化算法。
5 总结
CAVLC解码效率的优劣是决定H.264视频解码器性能的关键因素之一，本文提出一种采用索引技术的CAVLC码表查询优化方案，通过对CAVLC的码字前缀0个数进行一级索引，对码字后缀数进行二级索引，由一二级索引，快速查询得到所需解码输出，减少查询的复杂度。经测试表明，优化后的码表查
算法在速度上比原算法提高了50%以上，同时，存储空间利用率提高了40%以上。该算法简单明了，容易实现，而且由于采用独特汇编指令CLZ，使其可应用于嵌入式环境中。
参考文献椒图科技
[1]张秀丽，万忠，鲍程红. 基于码头分组的CAVLC解码算法优化[J].电路与系统学报，2007，14（3）：
26-30.
[2]IYENGAR V，CHAKRABARTY K．An efficient finite—state machine implementation of Hufman
decoders[J]．Information Processing Letters，1997，64(6)：27l-275．
[3]Bi Hou-jie．A Novel Video Coding Standard-H.264／AVC[M]．Beijing：Posts and Telecom Press，
2005：119-121．
[4]曹宁，梅侠.CAVLC解码的一种有效方法[J].中国图像图形学报，2008，13（2）：230-233.
[5]Gary J.Sulliva ,“Video Compression—From Concepts，to the H．264，AVC Standard，”Proceeding
唐晓鹰
of the IEEE，v01．93，No．1Jan．2005．
[6]毕厚杰 主编．新一代视频压缩编码标准—H．264／AVC[M]．北京：人民邮电出版社，2005：119-121．
[7]ITU-T Rec．H．264／ISO／IEC 11496-10，Advanced Video Coding[S]．Final Committee Draft，
oeument JVT-G050，2003-03．
[8]龚建锋，金文光，季爱明．基于H．264解码中CAVLC的优化[J].微电子学与计算机，2007，24(1)
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议