差分动态二进制化的二进制算数编码

文章编号:1009 － 2552(2013)08 － 0111 － 03 中图分类号:TN919． 81 文献标识码:A 差分动态二进制化的二进制算数编码 吴江铭 (上海交通大学电子工程系，上海 200030) 摘 要:JCT － VC组织公布的 HEVC 草案沿用了 H264 的 CABAC，改进了二进制化过程。 在阐述高性能压缩算法 CABAC的同时，创新性地提出了动态二进制化算数编码，并预先对数据 进行差分。最后，通过压缩 Java文件实验证实差分动态二进制化算数编码在压缩率方面有较大 的提高，高于 PAQ和 CABAC。 关键词:二进制算数编码;二进制化;霍夫曼编码 Difference and dynamic binarization of binary arithmetic coding WU Jiang-ming (Department of Electrical Engineering，Shanghai Jiaotong University，Shanghai 200030，China) Abstract:It provides an overview of the high efficiency compression method CABAC proposed in HEVC which will be published by JCT-VC． Then it optimizes the binarization process of binary arithmetic coding by dynamic Huffman coding and makes the difference before the binarization． At last，it demonstrates the experimental results in comparison with the PAQ to validate the efficiency of the new method difference and dynamic binarization of binary arithmetic coding． Key words:binary arithmetic coding;binarization;Huffman coding 0 引言 新一代视频编码 HEVC 发布的 JCTVC － H1003_dK［1］在 H264 的基础上，编码块的大小更为 灵活;帧 内 预 测 的 角 度 也 多 达 34 种;沿 用 CABAC［2］，增加二进制化方法;V2V［3］对变长的二 进制序列采用霍夫曼编码。 本文提出动态更新二进制化方式，降低 CABAC 概率状态迁移造成的编码冗余，同时对信源数据进 行差分处理，降低信源数据间的冗余。 1 基于上下文的高性能压缩算法 著名的压缩算法有上下文树加权 CTW［4］，部分 串匹配预测 PPM［5］以及概率后缀树 PST［6］。CTW 适用于一维{0，1}编码;PPM 对于字符集合采用逃 逸概率来估计未出现的上下文;PST 更好地平滑了 概率分布，合并了相近概率的公共后缀的上下文。 视频编码采用基于上下文的自适应的二进制算数 编码［2］。 CABAC分为 3 个步骤:二进制化;上下文建模; 二进制算数编码，如图 1 所示。 (1)CABAC的二进制化过程是将可能出现的字 符二进制化，字符出现的概率为每个二进制化后比特 位的概率乘积。H264 采用 Unary Binarization、Trun- cated Unary Binarization、Fixed － Length Binarization、 Kth order Exp － Golomb Binarization 等二进制化方 法［7］。HEVC增加 Truncated Rice Binarization［1］。宏 块、子宏块类型和分区模式采用 VLC二进制化［1］。 (2)CABAC的上下文建模［2］。 多方向的连续上下文建模:当前的上下文环境 决定于当前上方和左边的语法元素。 收稿日期:2012 － 12 － 20 作者简介:吴江铭(1984 －) ，男，在职研究生，研究方向为图像数据 传输，现从事 Java虚拟机的研究开发工作。 —111— 图 1 CABAC编码图［2］ 此外，宏块类型和子宏块类型根据不同片类型 使用不同的上下文;上下文决定于残差块的类型 (亮度直流分量、亮度交流分量、色度直流分量等)。 (3)二进制算数编码［2］ 二进制算数编码的字符集{0，1}，MPS 为大概 率字符，而 LPS为小概率字符。 初始状态 LowBound = 0，Range = 1，LPS出现的 概率 PLPS。当下一个字符为 LPS 时，LowBound = Range ×(1 － PLPS) ，Range = Range × PLPS，更新 LPS 出现的频率 PLPS。反之，LowBound 不变，Range = Range ×(1 － PLPS) ，更新 LPS 出现的频率 PLPS。循 环直到序列编码结束，［LowBound，LowBound + Range］之间的浮点数可以代源序列。 上述过程中，PLPS的更新以及区域 Range 的更 新需要进行乘法操作。H264［7］的编码将概率统计 分成 64 个状态(如图 2 所示) ，简化了 PLPS的计算 (见文献［7］中的 Fig6)。 图 2 CABAC状态迁移 2 视频编码中的二进制算数编码的差 分动态二进制化 CABAC的二进制化过程［1，7］大多采用固化的二 进制方法，而 64 个概率状态值的迁移必然增大编码 冗余。本文创新性地提出动态二进制化的方式，采 用动态霍夫曼树动态更新二进制化的 Bin，使大概 率符号动态地集中于短的二进制化 Bin，减少多个 Bin状态迁移造成的冗余;并在二进制化前对数据 进行差分，进一步降低冗余。 2． 1 动态二进制化 二进制化算数编码的冗余: H冗余 =∑ i pi log2 1 1 +∑ j △pij pij (式中，pi =∏ j pij 表示某个符号出现的概率，pij 为表示该符号的各个 Bin的概率，Δpij 为 64 个概率状态带来的误差)。 易见，使符号概率大的 Bin越少，则编码中总体 状态迁移的 Bin 越少，总体冗余越少。这可以采用 动态霍夫曼树方法来实现，使概率大的符号更新的 Bin最少，则总体更新的 Bin减少，且总体冗余降低。 编码过程中，更新符号的出现次数，并回溯至根结 点，在回溯过程中检查经过的结点是否平衡(左结 点概率小于右结点概率) ，不平衡时重建霍夫曼树。 —211— 2． 2 语法元素值的差分变换 同一语法元素有些数据相邻，有些则间隔一些 其他语法元素，例如宏块类型。采用非连续的上下 文编码，对同一种的语法元素的值进行差分，可以增 加前后差分值重复的概率，使差分值集中在低幅值。 语法元素随机分布时，差分值 d的出现概率: p(d)= 2 ×(N + 1 － d) (N + 2) (N － 1)，由此可见随着差分值 的变大，其出现概率下降。 3 差分动态二进制化二进制算数编码 应用至 Java数据压缩 Java文件现阶段有两种主要压缩方式，一种是 Sun的 class文件采用 Zip 压缩方式进行压缩(生成 Jar包) ，另一种 Android的 dex文件采用 Zip 压缩方 式进行压缩(生成 Apk包)。 Java文件中最主要的数据是常量池和字节码。 常量池描述了一系列的数据以及数据之间的引用关 系［8］。Apk包与 Jar包最主要的区别便是 Apk 对不 同类的常量池进行了合并，Apk对字节码指令进行 了优化［8］。 3． 1 动态Huffman编码实现动态二进制化算数编码 将常量池中的数据抽象成一组同一类型的数据 的集合。对该数据进行从小至大进行排序(兼顾引 用次数，同时调整其他常量池和属性对其的引用) ， 并对其求差分。将所得的差分值按照 2． 1 节生成动 态霍夫曼树。由于视频编码需要进行实时编解码， 概率统计时，只能根据已经出现的序列，进行概率统 计。而 Java文件压缩并没有实时性编译的，所 以可以先统计整个文件的概率分布，在解压缩的时 候，对已知的分布进行调整。 3． 2 Java文件压缩试验结果 对 j2sk － 1． 4 运行时库进行压缩，如表 1 所示。 LPAQ8 对差分数据的压缩率高于非差分数据。动 态二进制化 CABAC可以提高压缩性能。LPAQ8 对 常量池的压缩率不如差分动态二进制化 CABAC。 LPAQ8 的压缩时间最长，两种差分二进制化算数编 码时间接近。 表 1 压缩率与压缩时间的对比 压缩对象 差分数据对压缩率 的影响(LPAQ8)P /% 非差分 数据 差分 差分 动态 CABAC 压缩率的 提升 P /% 总体压缩性能 对比 P /% LPAQ8 动态差分 CABAC 时间对比 t /ms LPAQ8 动态差分 CABAC 差分 CABAC Utf8 长度 72． 46 67． 06 0． 075 72． 46 64． 97 250 62 47 Integer 51． 26 61． 58 9． 822 51． 26 60． 66 31 0 0 Float 30． 73 30． 73 12． 772 30． 73 39． 24 0 0 0 Long 49． 11 49． 11 2． 920 49． 11 59． 43 16 16 0 Double 37． 67 37． 67 6． 688 37． 67 34． 26 0 0 0 Class 51． 08 80． 66 0． 702 51． 08 79． 30 63 16 15 String 51． 75 79． 96 0． 047 51． 76 78． 19 94 16 0 Field 32． 20 52． 07 0． 676 32． 20 52． 35 234 31 16 Method 36． 62 55． 57 0． 048 36． 62 55． 32 390 47 47 Interface 33． 45 48． 53 0． 840 33． 45 50． 84 16 16 31 NameAndType 38． 23 57． 15 0． 046 38． 23 56． 78 312 63 31 常量池总体 46． 80 60． 13 27． 780 46． 80 59． 48 1406 267 187 4 结束语 本文介绍了 CABAC 算法，创新性地提出对二 进制化过程采用动态霍夫曼树更新，并对数据进行 差分。通过实验验证差分动态二进制化编码实时性 降低 43%，压缩率提升 28%。 参 考 文 献: ［1］Benjamin Bross． High efficiency video coding (HEVC)text specifi- cation draft 6［C］． JCT-VC of ITU-T SG16 WP3 and ISO /IEC JTC1 /SC29 /WG11，JCTVC-H1003，8th Meeting:San José，CA， USA，1 － 10 Feb． 2012． ［2］Detlev Marpe，Heiko Schwarz，Thomas Wiegand． Context-Based A- daptive Binary Arithmetic Coding in the H． 264 /AVC Video Com- pression Standard［J］． IEEE Transactions on Circuits and Systems for Video Technology，Jul． 2003，13(7) :1 － 18． ［3］Gergely Korodi，Da-ke He． Dynamic Source Selection［C］． JCT-VC of ITU-T SG16 WP3 and ISO /IEC JTC1 /SC29 /WG11，JCTVC- B034，2nd Meeting:Geneva，CH，21 － 28 Jul． 2010． ［4］Willems F M J，Shtarkov Y M，Tjalkens T J． The context-tree weighting method:basic properties［J］． IEEE Trans． Inform． Theo- ry，May 1995，41(3) :653 – 664． ［5］Moffat A． Implementing the PPM data compression scheme［J］． IEEE Trans． Communications，Nov． 1990，COM-38:1917 － 1921． ［6］Kermorvant C，Dupont P． Improved smoothing for probabilistic suf- fix trees seen as variable order markov chains［C］． European Conf． Machine Learning，2002:185 － 194． ［7］Advanced video coding for generic audiovisual services［J］． ITU-T Recommendation H． 264 ＆ ISO /IEC 14496 － 10 AVC． ［8］Sohail Khan． Analysis of Dalvik Virtual Machine and Class Path Li- brary［M］． Security Engineering Research Group，Pakistan． Nov． 2009． 责任编辑:肖滨 —311—