一种基于CAVLC解码的快速码表查找算法

第３９卷第２期　Ｖｂｌ＿３９　Ｎｏ．２　计算机工程　

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　２０１３年２月　

Ｆｅｂｒｕａｒｙ　２０１３　

・专栏・　文章编号ｌ　１０００—３４２８（２０１３）０２—００２３—Ｏ４　文献标识码Ｉ　Ａ　中翻分类号ｌ　ＴＮ９１９．８１　

一种基于ＣＡＶＬＣ解码的快速码表查找算法　黄明政，王建华，韩一石，孙运龙　（广东工业大学信息工程学院，广州５　１　０００６）　摘要：在分析和研究基于上下文的自适应可变长度编码（ＣＡＶＬＣ）码表结构特点的基础上，结合码表统计规律，提出一种　新的ＣＡＶＬＣ解码码表查找算法。根据码字前缀０的个数和码字长度之间的关系共同决定输入码字后缀位数和数值，实现　对输入码流的快速确定，对确定的输入码字，只需再查一次表便可以得到其对应的解码输出。测试结果表明，该优化算法　在解码查表速度方面比原算法提高约２０％。　关健诃：基于上下文的自适应可变长度编码；码表查找；码字前缀；码字后缀；码字长度　

Ａ　Ｑｕｉｃｋ　Ｃｏｄｅ　Ｔａｂｌｅ　Ｌｏｏｋｕｐ　Ａｌｇｏｒｉｔｈｍ　Ｂａｓｅｄ　ｏｎ　ＣＡＶＬＣ　Ｄｅｃｏｄｉｎｇ　ＨＵＡＮＧ　Ｍｉｎｇ－ｚｈｅｎｇ，ＷＡＮＧ　Ｊｉａｎ－ｈｕａ，ＨＡＮ　Ｙｉ－ｓｈｉ，ＳＵＮ　Ｙｕｎ—ｌｏｎｇ　（Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｇｕａｎｇｄｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｇｕａｎｇｚｈｏｕ　５　１　０００６，Ｃｈｉｎａ）　［Ａｂｓｔｒａｃｔ］Ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｔｈｏｒｏｕｇｈ　ａｎａｌｙｓｉｓ　ａｎｄ　ｓｔｕｄｙ　ｏｎ　ｔｈｅ　ｓｔｒｕｃｔｕｒａｌ　ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ　ｏｆ　Ｃｏｎｔｅｘｔ—ｂａｓｅｄ　Ａｄａｐｔｉｖｅ　Ｖａｒｉａｂｌｅ　Ｌｅｎｇｔｈ　Ｃｏｄｉｎｇ（ＣＡＶＬＣ）ｃｏｄｅ　ｔａｂｌｅｓ，ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｓ　ａ　ｎｅｗ　ｔａｂｌｅ　ｌｏｏｋｕｐ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ＣＡＶＬＣ　ｄｅｃｏｄｉｎｇ　ｗｉｔｈ　ｔｈｅ　ｓｔａｔｉｓｔｉｃａｌ　ｌａｗ　ｏｆ　ｃｏｄｅ　ｔａｂｌｅｓ．Ｔｈｅ　ｉｄｅａ　ｏｆ　ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｒｅｌａｔｉｏｎｓｈｉｐ　ｂｅｔｗｅｅｎ　ｔｈｅ　ｎｕｍｂｅｒｓ　ｏｆ　ｚｅｒｏ　ｉｎ　ｃｏｄｅ　ｐｒｅｆｉｘ　ａｎｄ　ｔｈｅ　ｌｅｎｇｔｈ　ｏｆ　ｃｏｄｅ．　Ｗｉｔｈ　ｉｔ，ｉｔ　ｐｒｏｐｏｓｅｓ　ａ　ｓｃｈｅｍｅ，ｉｎ　ｗｈｉｃｈ　ｔｈｅ　ｃｏｄｅ　ｓｕｆｆｉｘ　ａｎｄ　ｔｈｅ　ｃｏｄｅ　ｖａｌｕｅ　ａｒｅ　ｄｅｔｅｒｍｉｎｅｄ　ｂｙ　ｔｈｅ　ｒｅｌａｔｉｏｎｓｈｉｐ　ｂｅｔｗｅｅｎ　ｔｈｅ　ｎｕｍｂｅｒｓ　ｏｆ　ｚｅｒｏ　ｉｎ　ｃｏｄｅ　ｐｒｅｆｉｘ　ａｎｄ　ｔｈｅ　ｌｅｎｇｔｈ　ｏｆ　ｃｏｄｅ，ａｎｄ　ｉｔ　ｃａｎ　ｄｅｃｏｄｅ　ｔｈｅ　ｉｎｐｕｔ　ｃｏｄｅ　ｑｕｉｃｋｌｙ．Ａｓ　ａ　ｒｅｓｕｌｔ，ａ　ｓｐｅｃｉｆｉｃ　ｉｎｐｕｔ　ｃｏｄｅ　Ｃａｎ　ｂｅ　ｄｅｃｏｄｅｄ　ｗｉｔｈ　ｏｎｌｙ　ｏｎｅ　ｔｉｍｅ　ｔａｂｌｅ　ｌｏｏｋｕｐ．Ｔｅｓｔ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｏｐｔｉｍｉｚｅｄ　ａｌｇｏｒｉｔｈｍ　Ｃａｎ　ａｃｈｉｅｖｅ　２０％ｓｐｅｅｄ—ｕｐ　ｉｎ　ｔｈｅ　ｔａｂｌｅ　ｌｏｏｋｕｐ　ｃｏｍｐａｒｅｄ　ｗｉｔｈ　ｔｈｅ　ｏｒｉｇｉｎａｌ　ａｌｇｏｒｉｔｈｍ．　［Ｋｅｙ　ｗｏｒｄｓ］Ｃｏｎｔｅｘｔ－ｂａｓｅｄ　Ａｄａｐｔｉｖｅ　Ｖａｒｉａｂｌｅ　Ｌｅｎｇｔｈ　Ｃｏｄｉｎｇ（ＣＡＶＬＣ）；ｃｏｄｅ　ｔａｂｌｅ　ｌｏｏｋｕｐ；ｃｏｄｅ　ｐｒｅｆｉｘ；ｃｏｄｅ　ｓｕｆｆｉｘ；ｃｏｄｅ　ｌｅｎｇｔｈ　ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００—３４２８．２０１３．０２．００５　

１概述　新的视频压缩标准Ｈ．２６４是ＩＴＵ—ＶＣＥＧ（Ｖｉｄｅｏ　Ｃｏｄ－　ｉｎｇ　Ｅｘｐｅｒｔｓ　Ｇｒｏｕｐ）和ＩＳＯ　ＭＰＥＧ（Ｍｏｖｉｎｇ　Ｐｉｃｔｕｒｅ　Ｅｘｐｅｒｔｓ　Ｇｒ０ｕｐ）共同制定的视频压缩编码国际标准＿Ｊ　Ｊ，它具有高编　码压缩效率、友好的面向网络接口和在较低带宽上提供　高质量图像传输的特点，在数字视频通信和存储领域得　到了越来越广泛的应用，被普遍认为是现代最有影响力　的行业标准。　基于上下文自适应的可变长编码（ＣＡＶＬＣ）是Ｈ．２６４　标准中熵编码的一种常见方式，它根据视频流的不同而　动态地在多组结构不同的码表中进行切换　Ｊ，以提高编　码效率。在熵编码效率提高的同时，解码的复杂度和运　算量也随之增加，其高性能的获得是以增加其编解码的　复杂度为代价的，因此，对解码算法的优化成为当前研　究的一个方向。　本文介绍了Ｈ．２６４标准的ＣＡＶＬＣ解码原理和过程，　对Ｈ．２６４标准中的解码算法进行复杂度的分析，然后对　ＣＡＶＬＣ解码优代算法的现状进行概述，并对比相关算　法的优劣，最后在此基础上提出了改进的变长码表查表　算法。　２　ＣＡＶＬＣ解码原理和过程描述　ＣＡＶＬＣ是对可变长编码（ＶＬＣ）的一种改进，其原理　是根据已编码语法元素的情况动态调整编码中使用的码　表，利用相邻已编码符号所提供的相关性，为所要编码　

基金项目：广东省科技计划基金资助项目（２０１１Ｂ０９０４００３４４，２０１１Ｂ０１０２０００２９）　作者简介：黄明政（１９８９－－），男，硕士研究生，主研方向：视频通信，视频编解码；王建华，硕士研究生；韩一石，副教授；　孙运龙，硕士研究生　收稿日期：２０１２—０３—２９　修回日期：２０１２－０５—２３　Ｅ－ｍａｉｌ：ｍｉｎｇｚｈｅｎｇｈｕａｎｇ＠１６３．ｃｏｍ　２４　计算机工程　２０１３年２月１５日　的符号选择合适的上下文模型。上下文模型的选择主要　体现在选择变长表格，其运算量约为解码器总运算量的　１３％左右　。　ＣＡＶＬＣ主要用于亮度块和色度残差块方面的编码，　其解码总思路是不断地读取码流，判断，直到在码表中　找到该码字，具体过程为取码表中的一个码字，根据码　字长度从码流中取出相应长度的比特串，比较此码字和　比特串，若相同则表示查找成功，然后从码表中获取对　应的语法元素，不同则取码表中的下一个码字，继续循　环上述操作，直到解码完成。　对ＣＡＶＬＣ解码过程可简要描述如下步骤：　（１）对非零系数个数（ＴｏｔａｌＣｏｅｆ）和拖尾系数个数　（ＴｒａｉｌｉｎｇＯｎｅｓ）进行解码。　（２）对拖尾系数符号数（ＦＬＣ）进行解码。　（３）对除了拖尾系数外的非零系数幅值（Ｌｅｖｅｌｓ）进行　解码。　（４）对最后一个非零系数之前零的个数（Ｔｏｔａｌ—Ｚｅｒｏｓ）　进行解程。　（５）对每个非零系数前零个数（Ｒｕｎ＿ｂｅｆｏｒｅ）进行解码。　３　ＣＡＶＬＣ解码算法复杂度分析　对于一个二维码表，若通过其坐标查找对应的内容　是很容易的，而反过来，要通过内容查找对应的坐标则　不容易，需要对整个表进行遍历。由于ＣＡＶＬＣ码表存　储结构为二维码表，因此对ＣＡＶＬＣ码表的解码需做大　量的搜索和查表判断的过程，解码运算量非常巨大。　在ＣＡＶＬＣ解码过程中，由于ＣＡＶＬＣ的每一个系　数都对应着多个各自不同的码表，而每个码表结构复杂，　种类繁多，都需做大量运算过程去匹配，而ＣＡＶＬＣ解　码对码字一次匹配的命中率不到４０％　，因此需要读取、　匹配多次才能得到正确的信息，导致ＣＡＶＬＣ解码复杂　度的增加。　在ＣＡＶＬＣ解码过程中，由于ＣＡＶＬＣ变长解码的　码长是不定的，而解码输入的码流却是连续的，中间没　有间隔符，导致解码时ＣＡＶＬＣ解码器需从连续的比特　流中去分辨各个长度不同的码字，而对码流不定长度的　判断恰恰也大大增加了解码的时间和困难。　总之，ＣＡＶＬＣ的解码需要通过不断的搜索和判断去　得到最后码字和码长，消耗时间长，运算量大，因而解　码速度慢、效率低，在实际的应用中难以满足实时性的　要求，故在实际应用中需寻找新的有效解码方法或需对　原解码算法进行一些优化，以减少解码的运算量和运行　时间，提高解码系统整体性能。　

４　ＣＡＶＬＣ的解码优化现状　在ＣＡＶＬＣ解码算法中，由于二维码表的解码查　找时间占据整个解码时间的相当大一部分，因此有效减　少二维码表的查找时间就能大大提高整个解码系统的处　理速度。所以在近年来，人们提出了很多关于提高　ＣＡＶＬＣ解码算法的方案都集中在二维码表的查找改进　和优化上，对二维查表方法的改进已经成为现当前解法　算法优化的热点。　从目前提出的优化算法来看，其大部分算法基本思　路都是对ＣＡＶＬＣ码表的结构进行重新调整，通过使用　分组或分级方法减少对整张码表的遍历次数来提高解　码效率　Ｊ。目前，对二维码表进行优化方法主要有如下　３种：　（１）把二维码表构造成哈夫曼树，虽然可以避免对整　个码表的遍历，但其缺点是存储空间利用率不高。　（２）把二维码表分层次查表，可以减小遍历范围，但　缺点是需做多次搜索和判断，运行时间长，不适用于实　时处理的情况。　（３）根据码头的特点对码字进行分组，查找速度较快，　但缺点是无法快速得到码字长度和反馈码长度。　

５改进的变长码表查表算法　本文在参考上述优化思想的基础上，结合已有的解　码方法，提出了一种快速的解码查表算法，其基本思路　是：从ＣＡＶＬＣ码表中码字前缀０的个数与码字长度之　间存在的特殊对应关系出发，提出根据码字前缀０的个　数和码字长度共同动态确定输入码字后缀，实现输入码　流的快速确定方案，对确定的输入码流只需查一次表，　便可得到相应的解码输出。　下面以Ｃｏｅｆｆ　ｔｏｋｅｎ为例，讲述这种快速解码查表　算法。　解码前，需根据ＮＣ的取值范围，确定所要查找的　码表，其中，ＮＣ值的确定规则如下：色度的直流系数　ⅣＣ＝一１；其他系数类型ＮＣ值是根据当前块左边４ｘ４块　的非零系数数目（＾　）和当前块上面４ｘ４块的非零系数数　目（佃）求得的。不同的ＮＣ对应不同的码表，常用的ＮＣ　的取值范围有Ｏ￣ＮＣ＜２，２￣ＮＣ＜４，４≤ⅣＣ＜８，ＮＣ＝－Ｉ