H

H.64 中指数哥伦布算法的优化实现研究 翁慈洁, 张悠慧, 汪东升清华大学微处理器及片上系统研究中心 (100084) Emal: wengcj03@mals.tsnghua.edu.cn 摘要 : 本文研究了 H.64 视频压缩标准中指数哥伦布解码算法, 提出了一种优化实现 该实现利用指数哥伦布码字的特性, 给出了一种使用计算代替逐个比特读取的解码方式 根据实验数据, 使用这种方法, 可以比 JM(H.64 参考实现 ) 中的指数哥伦布解码方法提高 0% 左右的效率 关键词 :H.64, AVC, 指数哥伦布, 算法优化实现 Exp-Golomb Algorthm Optmal Implementaton n H.64 Cje Weng, Youhu Zhang, DongSheng Wang McroProcessor and SoC Research Center, Tsnghua Unv. (100084) Emal: wengcj03@mals.tsnghua.edu.cn Abstract Ths paper nvestgates the Exponental Golomb algorthm n H.64 vdeo compresson standard and provdes an optmal mplementaton of the algorthm. Ths mplementaton proposes a decodng method whch takes advantage of features of Exponental Golomb code word to use computaton nstead of readng and comparng bt-wsely to decode the code word. Accordng to the experment, ths method mproves the Exponental Golomb decodng by 0% than the JM mplementaton ( H.64 reference software). Keywords: H.64, AVC, Exp-Golomb, algorthm optmal mplementaton 1 引言 H.64 是由 ITU-T 的 VCEG(Vdeo Codng Experts Group) 和 ISO/IEC 的 MPEG(Moton Pcture Experts Group) 共同组成的 JVT (Jont vdeo Team) 于 003 年 3 月提出的一种视频编码标准 003 年 5 月被正式批准为国际标准,ISO/IEC 称之为 MPEG4 Part10/AVC,ITU-T 称之为 H.64 H.64 标准与之前的各种视频编码标准相比, 有以下几个重要优势 : 1. 高质量的视频图像 H.64 标准在各种应用环境下提供了稳定的视频编码质量, 尤其是在低比特率的情况下, 也能保持较高的图像质量. 与 MPEG4 相比, 在图像质量相当的 情况下,H.64 的比特率大约降低了 50% 3.H.64 既可以应用于低延迟的应用领域, 如在实时通信系统中的应用, 也可以用于对延迟没有限制的场合, 如视频存储系统 基于服务器的视频流应用等等 4.H.64 对于丢失的信息提供了错误掩盖的工具 5.H.64 分为视频编码层 (VCL) 和网络适配层 (NAL),VCL 提供了核心的视频内容压缩算法, 而 NAL 提供了针对特定网络传输的打包原则 由图 1-1 可以看到,H.64 视频码流 (Btstream) 先经过 NAL 解码, 由连续的比特流变成一个个单独的 NAL 单元 (NALU) NAL 单元经过熵解码得到 H.64 的语法单元, 其中包括输入到逆量化 (nverse 1

重排序 逆量化 逆变换 残差 NAL 解码 熵解码 帧间预测 滤波 输出 比特流 NAL 单元 帧间预测模式 图 1-1 H.64 解码流程图 运动向量, 参考帧 运动补偿 Quantzaton) 和逆变换 (nverse DCT) 的残差 (resdual) 语法元素, 输入到帧内预测 (Intra Predcton) 的帧内预测模式语法元素, 输入到运动补偿 (Moton Compensaton) 的运动向量 参考帧等语法元素 之后, 把预测部分和残差部分相加, 并经过滤波得到输出的图像 指数哥伦布编码就是图中 H.64 熵解码 (Entropy Decodng) 的一部分 它和其他熵解码算法, 也就是基于上下文自适应的可变长编码 (CAVLC) 或基于上下文自适应的算术编码 (CABAC) 一起用于把码流中的比特信息转换成 H.64 的各种语法元素, 为其他解码工具提供输入 本文的第二部分将介绍指数哥伦布算法的原理,JVT 提出的解码参考实现的流程及伪码表示 第三部分分析指数哥伦布算法的码字特点, 提出用计算和查表的方式进行解码的方法以及伪码实现 第四部分给出对指数哥伦算法的 H.64 参考实现和优化实现进行实验的结果 实验结果表明, 优化实现比参考实现节省了大约 0% 的解码时间 指数哥伦布算法.1 指数哥伦布算法的原理指数哥伦布算法是一种用于被 JVT 的 H.64 和中国的音视频编码标准 AVS 采用的 可变长编码算法 常用的可变长编码算法 Huffman 算法不能直接用于无限字母表的编码, 因为 Huffman 编码需要合并字母表中概率最小的字符, 形成 Huffman 树, 从而得到 Huffman 码 S.W. Golomb[3] 最早开始对非负整数的无限字母表进行编码的研究工作 他引入了对整数 优化的一类前缀码,>=0 并服从概率分布 P() = (1-q)q,q 是 1/ 的幂 Gallagher 和 Van Voorhs[4] 把 Golomb 的结果进行了推广, 使得 q 可取 0<q<1 的所有值 并且指出, 的优化码可以用公式 =lj + r 生成 其中 l 是整数, 满足 q l + q (l+ 1) 1 q (l 1) + q l ( 1) 码字由一进制的 j (j=floor(/l)) 和 Huffman 码的 r 构成 Rce[5] 研究了 l= k 这种重要特殊情况, 这样可以很方便的得到 j, 并且保证余数 r 是定长码 这种方法叫做 Golomb-Rce 编码 与此同时,Teuhola[6] 提出了指数哥伦布 (Exp-Golomb) 编码算法 与 Golomb-Rce 码相比较, 指数哥伦布码码字的数量与长度成指数关系 比如一串长度为 len 的 0 可以被分为长度为 k,k+1, k+,, k+-1 的子串, 加上一个长度不超过 k+ 的剩余串 这里面,k 是指数哥伦布算法的编码参数 对非负整数 len 进行编码的步骤如下 : 1 通过如下公式确定 的值 : 1 j= 0 j+ k len < j= 0 j+ k, 0 ( ) 用以 0 为符号的一进制数表示 即 个 0 组成码字的前缀, 其中 0 只是符号, 只有个数有意义 3 插入一个分隔符 1 与第 步相同, 1 只是符号, 只需与第二步的符号不同即可 4 用如下公式计算出二进制数的码字尾部 1 len j= 0 j+ k ( 3)

Len k = 0 k = 1 k = CodeWord ( 码字 ) CodeWord ( 码字 ) CodeWord ( 码字 ) 0 0 1 0 10 0 100 1 1 010 11 101 011 1 0100 110 3 00100 0101 111 4 00101 0110 1 01000 5 00110 0111 01001 6 00111 001000 01010 7 3 0001000 001001 01011 8 0001001 001010 01100 9 0001010 001011 01101 表 -1 指数哥伦布码表 表 -1 是 k=0, 1, 时指数哥伦布码的 前 9 个码字 在 H.64 标准中, 对语法元素的编码选择了 k=0 的指数哥伦布码 下面所称得指数哥伦布码都是指的 H.64 标准中 k=0 的指数哥伦布码 从表 -1 中可以看出, 指数哥伦布码的码字结构如下 : [ M][ 1][ TAIL] ( 4) 解码算法如下 : 1 读出码字中前导 0 的个数, 赋给 M 跳过分隔符 1 3 读入 M 比特的二进制数, 赋给 TAIL 4 用下面公式算出语法元素的值 ( 5) M 1+ TAIL 其中,M 域为一个一进制数, 是 M-bt 个 0 组成的序列,M>=0 1 域为分隔符, 此处固定为比特 1 TAIL 域为码尾, 表示一个 M-bt 二进制无符号数. 指数哥伦布算法解码的伪码描述 ITU-T Rec. H.64 ISO/IEC 14496-10 AVC 中指数哥伦布解码描述为, 从码流的当前比特开始读直到第一个非零比特, 并记录比特 0 的个数到 leadngzerobts, 跳过分隔符, 读入 leadngzerobts 个比特 算法描述如下 : leadngzerobts=-1; for (b=0;!b; leadngzerobts++) b=read_bts(1); 其中, leadngzerobts 记录着码字的开始的 0 的个数, 就是公式 -1 中的 M 由 read_bts() 返回的值被解析为最高有效位在先的无符号整数 len 就是解码出来的值 3 算法优化 3.1 分析指数哥伦布算法指数哥伦布编码是一种变长编码算法 变长码 (Varable Length Code) 采用不同长度比特位的码字来表示数据, 对常用的数据采用较短的码字, 对不常用的数据采用较长的码字 这样做的好处是提高了存储的效率, 降低了传输时对网络带宽的占用 与定长码相比, 变长码提高了编码效率, 但其码长由其码字内容决定, 它的解码不象定长码那样预先就知道确定的码长, 而是需要逐位读出码字来决定码字的值 这样的逐位读取码字的操作会使增加函数调用次数, 引入过多的函数调用开销 并且不利于编译器对程序的优化和容易打断处理器的流水线操作 如果能改变逐位读取码流中的比特方式 采用一次性读取多个比特, 并直接对其进行分析解码的办法, 将会改善解码的效率 在下一小节优化方法中, 首先根据码字的数学特性提出了一种通过计算解码的方法 然后对于常见的码字长度, 采用查表的方法, 进一步提高了解码效率 3. 优化实现方案对指数哥伦布解码进行优化, 就要改变逐位读取码的情况 根据 H.64 解码标准和实际统计的结果 ( 表 3-), 在 H.64 码流中指数哥伦布码字不会超过 3-bt 长 所以, 我们一次读入 3 比特存放在缓冲区里面 根据码字的特性, 对 3-bt 的缓冲区内容进行计算解码 3..1 计算的方法首先, 分析指数哥伦布码字的数学特性 假设,3-bt 缓冲区 buf 中的内容如下 : 0000 0010 1000 0010 0000 0010 1000 0010 如果要从中找出码字, 首先要计算出前导的 0 的个数 M M 的计算方法如下 : len = leadngzerobts 1 + read_bts(leadngzerobts) 3

( 3 1) leadngzerobts = 3 (logbuf + 1) 然后计算 M-bt TAIL 的值 因为 M 的值已经计算出来了, 只要把 buf 向右移位, 剩下 M+1 位的码字 这 M+1 位包括 M 个 0, 一个 1, 和 TAIL 值 由公式 -5 所知 len = M 1+ TAIL ( 3 ) 其中第 M 位为 1 的值,TAIL 就是后面 M-bt 的值, 所以,len 就是 buf 右移后的值 -1 右移的位数, 计算方法如下 : rghtshftbts=3-leadngzerobts+1=log buf 31 因此, 计算码字的伪码如下 : rghtshftbts=log buf 31 buf>>rghtshftbts len=buf-1 3.. 查表的方法用计算的方法解码比逐比特读取提高了解码效率 根据对表 3- 的观察, 我们可以发现, 绝大多数码字的长度都比较短 比如, 码字长度小于等于 9, 也就是对于 M<=4 的情况, 占到从指数哥伦布算法的 97.1% 单就码字长度等于 1 的情况来说, 根据表 -1, 它仅仅是对 1 比特的码字进行解码, 还要多次调用对数, 移位等计算 这样的重复计算, 不仅浪费了计算得资源, 而且会增加解码时间 根据当前的计算机硬件的发展, 内存已经不是什么昂贵的设备 如果能用空间换取时间的方法, 把经常出现的码字事先计算出来, 通过查表的方式进行解码, 将能进一步提高解码的效率 码字长度出现次数 1 9795 3 105796 5 6660 7 5139 9 19947 11 1036 13 4374 15 789 17 11 表 3-: 指数哥伦布同长度码字出现次数统计我们以 M<4, 也就是码字长度小于 9 为例来 看看如何通过查表的方式进行解码 与 3..1 相同, 假设 3-bt 的缓冲区 buf 内容如下 : 0001 0010 1000 0010 0000 0010 1000 0010 首先, 需要把这 9-bt 的数据提取出来, 就是用移位的方法把不是码字的信息去除 也就是 buf=buf>>3-9 移位之后,buf 的内容如下 : 0000 0000 0000 0000 0000 0000 0010 0101 然后, 需要根据 buf 中的最后 9 比特的信息, 通过查表确定码字的解码结果 9 比特的指数哥伦布码最多对应值 30, 每一个表项占用一个字节 表项的总数为 9=51 个 所以编码表格占用的空间为 51 字节 编码表格的示意图如表 3-3 所示 : 码字值码字值 000000000 0 000000001 0 010000000 1 010000001 1 000001111 0 000010000 15 010111111 1 000010001 16 011000001 011000001 000011111 30 000100000 7 011111111 000100001 7 100000000 0 000100010 7 100000001 0 000100011 7 000100100 8 111111111 0 表 3-3 小于 9-bt 指数哥伦布编码表格从表中可以看出,9 比特的指数哥伦布码一共有 31 个, 却占用了 51 字节的空间 但对于内存空间比较充裕的应用来说 这样的代价还是值得的 另外需要注意的是, 用查表的方式解码之后, 无法判定码字的长度是多少 也就无法知道此次解码消耗了多少比特 这样会使下面的解码过程无法进行 所以查表之后, 必须再通过码长表格的得到这次解码消耗了多少比特 表格与编码表格相同, 只是值部分由解码值变成了码的长度 大小也是 51 字节 4

3.3 优化算法伪码描述输入 : 从码流读入的 3-bt buf 输出 :len f (buf>(1<<7)) buf=buf>>3-9 len=code[buf] else rghtshftbts=log buf 31 buf>>rghtshftbts len=buf-1 其中 Code[] 为表 3-3 所示的小于 9-bt 指数哥伦布编码表格 该算法首先用 buf 与 0x08000000, 也就是 1<<7 比较, 判断 buf 中的码字是否小于 9 位 如果小于那么就用查表的方法, 否则就用计算的方法 具体方法在前面已经分析了 不再赘述 3.4 算法分析用优化前的方法解码, 有 M+1 次 readbts(1),m+1 次的自增运算,1 次 readbts(m),1 次 M 运算,1 次减法 其中 M 为指数哥伦布编码的起始 0 的个数 readbts() 操作, 至少需要 1 次移位操作 M 运算需要一次移位操作, 所以一共需要 M+3 次移位操作,M+1 次自增操作, 和 1 次减法 时间复杂度为 O(M) 用单纯计算的方法解码, 需要 1 次 log 操作,1 次移位和 次减法 注意到这里的 log 的作用就是找出非零的最高位的位置, 通过移位就可以完成 平均时间就是 16 次移位 根据表 3-, 可以根据最常见的码字长度, 构造一个表格, 绝大部分 log 操作可以通过查表完成, 少量的需要移位 所以 log 的时间复杂度是 O(1) 该方法总的时间复杂度也为 O(1) 用查表的方法解码, 需要 1 次移位和一次查表 ( 即通过索引寻址的访存 ) 时间复杂度为 O(1) 综上所述, 计算的方法和查表的方法时间复杂度都是 O(1), 逐比特读取的方法时间复杂度为 O(M) 4 实验与结果 4.1 实验方法及实验环境根据第二部分和第三部分的分析, 对指数哥伦布解码时间进行测量并验证优化队解码时间的改进程度 为此编写了三个测量程序, 分别是优化前 使用查表和计算进行优化及单纯使用计算进行优化的指数哥伦布解码程序 测量过程是用三种不同的解码程序对于每个测试序列均运算 10 次, 统计出指数哥伦布解码时间的平均值, 并计算出优化前和综合使用查表和计算进行优化的加速比和综合使用计算和查表的优化与单纯计算的优化方法间的加速比 解码程序均运行在 lnux 操作系统上, 内核版本.4.7 使用的编译器为 gcc, 版本是 3.3.5 测试所使用的视频序列均为 JVT 中常用的序列, 如 football,foreman,news, stefan, tempete,moble 并用 AVC 的参考实现 JM10.1 版本进行编码 4. 实验结果通过实验结果表 4-1 可以看到 优化后的方法比优化前提高了 0% 左右 通过 4- 可以看到, 查表的方式比单纯使用计算的方法提高了 1% 至 5% 不等 计算和查表 (ms) 单纯计算 (ms) 加速比 news 40.43 5.0 4.67% football 571.47 593.7 3.75% foreman 536.95 547.53 1.93% stefan 760.07 771.34 1.46% tempete,37.0,366.4 1.66% moble 3,175.14 3,08.53 1.04% 表 4-1 使用查表和计算的优化与仅使用计算的优化的比较 计算和查表 (ms) 单纯计算 (ms) 加速比 news 40.43 331.85 7.55% football 571.47 787.93 7.47% foreman 536.95 646.86 16.99% stefan 760.07 933.70 18.60% tempete,37.0,907.99 19.97% moble 3,175.14 3,969.11 0.00% 表 4- 使用查表和计算的优化方法后的的计算时间 实验表明, 使用查表和计算的方法有效的提高了指数哥伦布算法的解码效率 建议对于内存空间比较紧张的应用可以使用单纯的 5

计算的方法 对于没有内存约束的应用, 可以考虑用查表的情况 表的大小可以根据应用和内存约束以及对解码效率的提高来权衡 参考文献 : [1] Jont Vdeo Team of ITU-T and ISO/IEC JTC 1, Draft ITU-T Recommendaton and Fnal Draft Internatonal Standard of Jont Vdeo Specfcaton (ITU-T Rec. H.64 ISO/IEC 14496-10 AVC), Jont Vdeo Team (JVT) of ISO/IEC MPEG and ITU-T VCEG, JVT-G050, March 003. [] Thomas Wegand, Gary J. Sullvan, Gsle Bjontegaard, and Ajay Luthra, Overvew of the H.64 / AVC Vdeo Codng Standard, IEEE Transactons on Crcuts and Systmers for Vdeo Technology, July 003 [3] Golomb, S.W., Run-length encodngs, IEEE Trans. Inf. Theory, 1966, 7, (1), pp. 399 401 [4] Gallager, R.G., and Van Voorhs, D.C., Optmal source codes for geometrcally dstrbuted nteger alphabets, IEEE Trans. Inf. Theory, 1975, 3, (1), pp.8 30 [5] Rce, R.F., Some practcal unversal noseless technques, Tech. Rep. JPL-79-, Jet Laboratory, Pasadena, CA, March 1979 [6] J. Teuhola, A Compresson Method for Clustered Bt-Vectors, Informaton Processng Letters, vol. 7, pp. 308-311, October 1978. [7] Wen, J., and Vllasenor, J.D., Structured prefx codes for quantzed low-shape-parameter generalzed Gaussan sources, IEEE Trans. Inf. Theory, 1999, 5, (45), pp. 1307 1314, pp. 350-364, 1999. 6