huffman表在xvid中的应用

guitarhua 2013-11-12

展开全文

图像编码不管是基于JPEG协议还是MPEG-4以及最新的H264协议，基本过程都是经过视频格式转换---运动预测----DCT变换---量化----zigzag扫描----霍夫曼可变长变换编码，从而生成了编码的码流。霍夫曼可变长编码基于信息出现的频率统计特性对信息重新编码，很大程度上减少了信息的冗余度。

XviD编解码库中，可变长霍夫曼编解码是通过查找表的方式进行的，也就是根据霍夫曼表建立编码表和解码表，表以多维数组的形式储存。编码表是主要是按照游程编码后的run及level值为索引找到对应的霍夫曼编码值及其长度，当然编码表按照是否为块内编码和是否为块最后一个游程可以分为四个编码表，解码表以码流中的12比特为索引来查询对应的游程码，进而恢复解码块，这12比特的高位为霍夫曼码，低位从全部为0填充到全部为1，这样做主要为了使以同一个霍夫曼码为高位建立的不同的12比特数最后会指向同一个霍夫曼编码，当然解码也可以通过建立霍夫曼树来按位查到叶子来找到对应结果，但前者提高了解码时间效率，是典型的用空间换取时间的做法。后面会有详细解释。

根据游程是否在霍夫曼表中，可以将编码方式分为基本霍夫曼编码和ESCAPE扩展霍夫曼编码，基本思想就是对不再霍夫曼表里的游程值通过设置标志，将其也纳入到霍夫曼表再进行编码，如果实在纳入不了的话，也设置标志位，让其在解码时单独解码。

霍夫曼可编程编码主要过程为：

初始化霍夫曼编码表----zigzag扫描----游程编码----查霍夫曼编码表编码----写入编码流。

霍夫曼解码主要过程为：

初始化霍夫曼解码表----从码流中读出12比特----查霍夫曼解码表解码----反zigzag扫描----输出块解码块。

以下为代码详细解释：

如果要调用XviD库的话，要先对库的一些参数进行初始化，初始化API定义为：

Int xvid_global(void *handle,

int opt,

void *param1,

void *param2)

当这个API参数opt定义为XVID_GBL_INIT 时，会执行函数xvid_gbl_init((xvid_gbl_init_t*)param1);在这个函数中会根据CPU架构以及色彩空间转换的一些初始化，也包括对霍夫曼编码表及解码表的初始化，函数为：init_vlc_tables()，在这个函数中主要用到三个表：

VLC_TABLE const coeff_tab[2][102]

static VLC coeff_VLC[2][2][64][64]

static REVERSE_EVENT DCT3D[2][4096]

coeff_tab是最基本的霍夫曼表，其他两个表都是根据这个表来创建的，coeff_VLC为编码过程要用到的编码表，DCT3D为解码时要用到的解码表。

我们来看coeff_tab的定义：

VLC_TABLE const coeff_tab[2][102] =

{

/* intra = 0 */

{ /* code len last run level */

{{ 2, 2}, {0, 0, 1}},

{{15, 4}, {0, 0, 2}},

……

从代码的注释可以看出结构体的5项依次为：霍夫曼码，码长，是否为最后一个非零值的标志位，游程值run(非零前零的个数)，游程值level(非零的值)。

根据定义，第一行我们可以理解为：对于块间编码(intra = 0)，zigzag扫描后如果一个数为1前面没有0，并且不是块中最后一个非零值，我们就将其编码为二进值的10，也就是2。同样第二行表示：就将数2并且前面没零编码为二进制的1111，也就是15。下面还有如：

{{28, 8}, {0, 13, 1}}就是zigzag扫描后将如果数1前面有13个零我们将其定义为二进制的00001000，注意长度为8位，即使二进制的8不够八位长的话也要前面补0凑成8位。

根据定义我们就可以将一段数据比如 101040010003写成(0,1),(1,1),(1,4)，（2,1）(3,3)，查找对应霍夫曼表的值以后就可以将其编码为二进制的: 10 110 0000001111 1110 0000001101。

可以看出这个表有局限的，因为并不是每一个游程编码都能找到对应的霍夫曼编码，如 intra = 0, last = 0,run = 3,level = 5 时就没有对应的霍夫曼码，以及level为负数时也没有对应的编码，这时就要根据其他设置ESCAPE标志对其进行编码，后面有其解释。

来看下面的代码：

for (intra = 0; intra < 2; intra++) {

for (last = 0; last < 2; last++) {

for (run = 0; run < 63 + last; run++) {

for (level = 0; level < (uint32_t)(32 << intra); level++) {

offset = !intra * LEVELOFFSET;

coeff_VLC[intra][last][level + offset][run].len = 128;

}

此处为初始化编码表，先将编码表中的霍夫曼码长度置为128，因为根据coeff_tab定义，霍夫曼码最长为12，而这里初始为128，就能根据这个值来区别此时的[intra][last][level][run]索引对应的值到底在不在ceoff_tab中直接找到。

接下来一段代码：

for (intra = 0; intra < 2; intra++) {

for (i = 0; i < 102; i++) {

offset = !intra * LEVELOFFSET;

for (j = 0; j < (uint32_t)(1 << (12 - coeff_tab[intra][i].vlc.len)); j++) {

DCT3D[intra][(coeff_tab[intra][i].vlc.code << (12 - coeff_tab[intra][i].vlc.len)) | j].len = coeff_tab[intra][i].vlc.len;

DCT3D[intra][(coeff_tab[intra][i].vlc.code << (12 - coeff_tab[intra][i].vlc.len)) | j].event = coeff_tab[intra][i].event;

} //used for decode of Xvid; DCT3D[intra?][code|len].len,.event;

coeff_VLC[intra][coeff_tab[intra][i].event.last][coeff_tab[intra][i].event.level + offset][coeff_tab[intra][i].event.run].code

= coeff_tab[intra][i].vlc.code << 1;

coeff_VLC[intra][coeff_tab[intra][i].event.last][coeff_tab[intra][i].event.level + offset][coeff_tab[intra][i].event.run].len

= coeff_tab[intra][i].vlc.len + 1;//use for encode coeff_VLE[intra?][last?][level][run].code , .len

if (!intra) {

coeff_VLC[intra][coeff_tab[intra][i].event.last][offset - coeff_tab[intra][i].event.level][coeff_tab[intra][i].event.run].code

= (coeff_tab[intra][i].vlc.code << 1) | 1;

coeff_VLC[intra][coeff_tab[intra][i].event.last][offset - coeff_tab[intra][i].event.level][coeff_tab[intra][i].event.run].len

= coeff_tab[intra][i].vlc.len + 1;//saving negative

}

这段代码根据最基本的霍夫曼表来填充编码表和解码表，先看对编码表coeff_VLC 的处理，此表主要以游程值run,level为索引，存储的为霍夫曼码code及码长len。Xvid对intra块和inter块进行不同的编码方法，对于intra块，也就是intra = 1 时，其索引值就是霍夫曼表intra, last, level, run值，通过这些索引查到的本应该是对应的霍夫曼表code值，在这里却是code << 1，并且相应的长度 len 增加了1，也就是为code预留了一位，而这个预留的位就是符号位，前面提到过霍夫曼表level值没有负数，而当编码时如有负值level,则将此游程对应的level取绝对值编码，并将最后一位置1，表示为负数，这样解码时读取此位，就可以将level正负分开。

对于块间编码，则程序先将level值加一个offset值，此值定义为：

offset = !intra * LEVELOFFSET;

LEVELOFFSET 为32, 也就是将霍夫曼表level加32，再建立块间编码表，这样的话，到了真正编码编码时也要将level加32再查找编码表，和块内编码不同的是，符号位在初始化时已经设置好，而在真正编码时就不再需要判断符号位了，即当level索引为[coeff_tab[intra][i].event.level + offset] 对应的为正level编码，为[offset - coeff_tab[intra][i].event.level] 时，是负level编码。

从以上可以看出块内编码没有对level进行偏移，符号位也不是在初始化中完成的，而块间编码初始化时已经对level加了32，符号位也已经初始完成。

再看对解码表，也就是对数组DCT3D[][]的处理，解码表以主要以霍夫曼码code为索引，存储的是此霍夫曼码对应的游程值及其他一些标志位，因为霍夫曼编码是可变长编码，编码长度是不一样的，从coeff_tab可以看出来长度为2到12，编码流就是这些编码按顺序放在一起的，比如前面提到的已经编码好的码流：10 110 0000001111 1110 0000001101(假设intra = 0)，程序从左到右先找到1，从霍夫曼表coeff_tab看到没有code为1，然后向后加一位找到10，也就是2，就可以在coeff_tab中找到code为2时，对应的游程run为0，level为1，这样就解码了码流的2比特，同理，程序继续往前可以分别找到110、0000001111、1110、0000001101对应的游程码。

上述的解码过程在原理上是可行的，但在实际操作中，由于对解码速度的要求，上述方法运行效率比较低(时间复杂度为O(n)，n为码流比特数)一般不会采用，取而代之的是建立定长的解码表，此时可以得到高效率的解码，此时复杂度为O(m),m为n比特码流对应的编码个数,如上述编码码流比特数n = 29,编码数m = 5。Xvid解码也采取了这种方法。

具体来说，在Xvid中，解码时就是从编码流中取出12比特，查找解码表，还原出原来的值，但我们知道，Xvid中霍夫曼编码长度最长为12比特，如果一个码值小于12比特(大部分情况是这样的)，取出来的12比特中必将包含另一个编码值的一部分，那么如何将这个12比特的值和不定长的霍夫曼值对应起来呢？就要利用霍夫曼编码的特性了，霍夫曼编码表霍夫曼码虽然长短不一，但如果将码值都按照最长的长度补齐，并将码值放在定长的高位，低位补零的话，这些值都是唯一的，还是以前面的霍夫曼表为例，这个表中最长的霍夫曼码长度为12，那么我们就将解码表解码值长度定为12，那

么前面的编码流10 110 0000001111 1110 0000001101 包含的5个码值补成12位就为：

10 变为 100000000000

110变为 110000000000

0000001111 变为 000000111100

1110 变为 111000000000

0000001101 变为 000000110100

可见，这些值同样是唯一的，我们来看解码的过程，程序从编码流中取出第一个12比特值，也就是101100000001，这个值我们要对应的是10所对应的解码值，因为10后面的值是由下一个编码值决定的，所以从100000000000 到 101111111111的值都有可能为10所对应的解码值，那么我们就把解码表中索引从100000000000到101111111111的所有解码游程值都定义为10所对应的解码值，这也是程序对解码表DCT3D做的主要工作，我们看代码：

for (j = 0; j < (uint32_t)(1 << (12 - coeff_tab[intra][i].vlc.len)); j++) {

DCT3D[intra][(coeff_tab[intra][i].vlc.code << (12 - coeff_tab[intra][i].vlc.len)) | j].len = coeff_tab[intra][i].vlc.len;

DCT3D[intra][(coeff_tab[intra][i].vlc.code << (12 - coeff_tab[intra][i].vlc.len)) | j].event = coeff_tab[intra][i].event;

}

上述程序主要作用就是：对于同一个编码值，建立很多索引指向这一个编码值对应的游程解码值，这些索引的共同点是高位都是编码值，这些索引放在一起，就组成了高位相同，而低位从全0变化为全1的所有数值，这样只要我们读任何12比特编码，只要这12比特以一个编码开始，我们不管下面的值是什么，通过查找解码表就得到了这个编码值解码的结果，结果结构体中的len变量告诉我们这一个编码值真正的长度，我们跳过这个编码真实的长度，再取出12比特，对这一个12比特进行同样的解码，这样一来，时间效率大大提高，需要注意的是前面编码时code的长度我们加了1，而我们在这里解码时找到的长度仍是code原来的长度，并没有将符号位包含进去，通过符号位我们就可以判断解码的结果的level值是否为负数，我们在解完一个码后要跳过的长度是编码真实的长度加1。

从以上叙述可以看出，编码时，如果将level取绝对值后得到游程值在霍夫曼表中出现，我们就能对其进行正确的编解码，但如果这样得到的游程值没有在基本的霍夫曼表中出现怎么办呢？

来看下面的一组代码：

在讲解处理之前，我们还要了解另外两个需要用到的数组：max_level[intra][last][run]和max_run[intra][last][level], 当intra和last 确定时，对于游程值(run, level)，max_level[intra][last][run]为这个run值在霍夫曼表coeff_tab中能找到的的最大的level值，同样的，max_run[intra][last][level]为这个level值在coeff_tab表中能查到的最大的run值。

这时假设有游程值对(run, level) 及

level_esc = level - max_level[intra][last][run]

run_esc = run - 1 - max_run[intra][last][level]

level_Xvid分三种方式处理：

方式1：如果level_esc <= max_level[intra][last][run] && run <= max_run[intra][last][level_esc]

也就是说将原始的level值进行相应的“缩小“为level_esc后，如果这时的(run, level_esc)在霍夫曼表中出现的话，我们就将其按照方式1处理，设置相应的变量为：

escape = ESCAPE1;// ESCAPE1 = 6；

escape_len = 7 + 1;

run_esc = run;

方式2：如果run_esc <= max_run[intra][last][level] && level <= max_level[intra][last][run_esc]

就是原始的run值经过相应的“缩小“为run_esc后，如果这时的(run_esc, level)在霍夫曼表中出现的话，我们就将其按照方式2处理，设置相应的变量为：

escape = ESCAPE2;

escape_len = 7 + 2;

level_esc = level; //run_esc is in range.

方式3：如果上述两种情况都不能满足的话，我们就采取直接

编码的方式将这游程值编码进去，也就是：

coeff_VLC[intra][last][level + offset][run].code

= (ESCAPE3 << 21) | (last << 20) | (run << 14) | (1 << 13) | ((level & 0xfff) << 1) | 1;

coeff_VLC[intra][last][level + offset][run].len = 30;

解码时我们就可以根据ESCAPE3标志位判断出第三种方式，通过简单的移位操作判断出这个编码对应的run和level值，长度是固定为30。

上述三种方式中只有第三种方式已经对其进行了编码，前两种方式只是设置了一些变量，还没有对其编码，这两种方式是如何进行编码的呢？看下面的代码：

coeff_VLC[intra][last][level + offset][run].code

= (escape << coeff_VLC[intra][last][level_esc + offset][run_esc].len)| coeff_VLC[intra][last][level_esc + offset][run_esc].code;

coeff_VLC[intra][last][level + offset][run].len

= coeff_VLC[intra][last][level_esc + offset][run_esc].len + escape_len;

可以看出，这两种编码方式和最基本的编码方式很相似，游程编码值存储的是经过“缩小“后查霍夫曼表得到的编码值，只是在这里code值向左移了escape位，而且长度len也加了escape_len，这是出于什么目的呢？

想象一下解码时，如果解到按照这两种方式编码的值时，我们无法区分这个编码是不是经过“缩小”后的编码，于是就通过设立标志ESCAPE1和ESCAPE2来确定这两种方式，来看一下几个ESCAPE宏定义：

#define ESCAPE1 6

#define ESCAPE2 14

#define ESCAPE3 15

而第一种方式将长度加了8，第二种方式将长度加9，也就是说对于方式1，在编码值code前加了前缀 00000110，方式2在编码前加了前缀000001110。

这样的话，如果解码时程序取出12比特编码流，我们可以看到没有一个基本的霍夫曼编码形成的12比特索引和由上面的前缀形成的12比特重复！根据这个我们就可以判断出是不是这两种方式编码的，解码出(run, level)值后我们再根据ESCAPE值查找max_run或max_level表就能求出最终的run和level值！同样地，我们看到前面的方式3前缀为ESCAPE3 << 21，ESCAPE3为15，这样的前缀就是000001111，这个前缀也是其他编码值所没有的，根据它就可以区分出第三种方式了。

这样即使在霍夫曼表中没有出现的游程值，我们仍然可以按照这三种方式进行编解码。块内编码和块间编码有一点不同就是块内编码方式3的编码表没有设置，而是在程序真正进行编码时通过判断长度len是否为128，如果不是128的话，说明长度值已经在初始化时设置过，可以直接编码。为128的话就直接按方式3编码。

块间编码表则已经在初始时已经完全设定好，正负level值都已经加了偏移32，这两种方式对符号的判断也是根据设定的符号位判定的。

到这里，对编码表和解码表的初始化就基本已经完成了，接下来就进入到真正的编解码过程了，其实真正到编解码时就很简单了，因为两个表已经包含了足够的信息了，只要在编解码时找到相应的索引，通过查表就能很快的得到结果了。：）

先看块内编码，其对应的函数是：

static __inline void

CodeCoeffIntra(Bitstream * bs,

const int16_t qcoeff[64],

const uint16_t * zigzag)

bs为码流，qcoeff为经过DCT变换的8x8块，zigzag为扫描顺序，程序主要就是对8x8数据块进行zigzag扫描，然后对扫描得到的游程值进行编码，看其中这样一段代码：

if ((level = qcoeff[zigzag[i++]]) != 0)

{

abs_level = abs(prev_level);

abs_level = abs_level < 64 ? abs_level : 0;

code = coeff_VLC[1][0][abs_level][prev_run].code;

len = coeff_VLC[1][0][abs_level][prev_run].len;

if (len != 128)

code |= (prev_level < 0);

else

{

code = (ESCAPE3 << 21) | (prev_run << 14) | (1 << 13) | ((prev_level & 0xfff) << 1) | 1;

len = 30;

}

程序先取level绝对值，根据run,level索引查找编码表coeff_VLC对此上一个循环找到的游程进行编码，如果发现len不为128的话，说明此游程是经过编码的，只要置符号位就可以了，如果为128的话，说明此游程还没有在编码表正正确的得到解码。直接对块内zigzag扫描数据按照方式三进行编码。

8x8块最后一次扫描得到的游程值要单独编码，此时last = 1。这就是程序最后单独一次编码的作用。

块间编码的函数为：

static __inline void

CodeCoeffInter(Bitstream * bs,

const int16_t qcoeff[64],

const uint16_t * zigzag)

参数和块内编码类似，看代码：

if ((level = qcoeff[zigzag[i++]]) != 0)

{

level_shifted = prev_level + 32;

if (!(level_shifted & -64))//if 0 < level_shifted < 64

{

code = coeff_VLC[0][0][level_shifted][prev_run].code;

len = coeff_VLC[0][0][level_shifted][prev_run].len;

}

else

{

code = (ESCAPE3 << 21) | (prev_run << 14) | (1 << 13) | ((prev_level & 0xfff) << 1) | 1;

len = 30;

}

程序先给level加32，if (!(level_shifted & -64))语句将level_shifted限制在[0 64]区间，因为块间编码表已经完全初始化完毕，只要level的绝对值小于32，那么其对应的游程都已经得到编码，所以不用再像块内编码那样通过判断是否被编码了，而且其符号位在编码表初始化时也已经设定好。在这里如果level_shifted仍然按照方式三进行处理，这也是可行的。

到这里，Xvid的霍夫曼编码过程都已经完毕，编码的码流存储在结构体Bitstream内，下面就是在解码过程中对其进行解码了。霍夫曼解码的块内和块间合并为一个函数，函数原型为：

static __inline int

get_coeff(Bitstream * bs,

int *run,

int *last,

int intra,

int short_video_header)

bs为要解码的码流，run,last为要返回的run,last 值，intra告诉解码函数此块是帧内块还是帧间块。来看代码：

if (GET_BITS(cache, 7) != ESCAPE) {

reverse_event=&DCT3D[intra][GET_BITS(cache, 12)];

if ((level = reverse_event->event.level) == 0)

goto error;

*last = reverse_event->event.last;

*run = reverse_event->event.run;

/* Don't forget to update the bitstream position */

BitstreamSkip(bs, reverse_event->len+1);

return (GET_BITS(cache, reverse_event->len+1)&0x01) ? -level : level;

}

代码先从码流cache中取出7比特值，然后检查是否等于ESCAPE，ESCAPE宏定义为3，在前面提到，以霍夫曼最基本的表建立的12比特索引值前7位值都不等于3，而通过ESCAPE前缀建立的3种编码方式前7位都为3，因为：

ESCAPE1（6）前缀： 00000110 长度：8

ESCAPE2（14）前缀： 000001110 长度：9

ESCAPE3（15）前缀： 000001111 长度：9 （可以从方式三时code = (ESCAPE3 << 21) |……），总长度为30推断出)

这样通过这7位的判断就将基本编码方式和ESCAPE扩展编码分开了，对于基本编码就可以直接查解码表得到最终的run和level以及last的值，而正负号就可以查询紧跟其后的1比特符号位来判断。

程序最后通过BitstreamSkip略过了len+1位，因为解码表中对应的长度并为加上符号位。

如果通过上述判断，得出此编码的编码方式为ESCAPE方式，那么我们就判断是其中哪种ESCAPE方式并对其解码，来看下面的代码：

cache <<= 7;

……

if ((mode = GET_BITS(cache, 2)) < 3) {

const int skip[3] = {1, 1, 2}; // 0 or 1 means ESCAPE1 and 2 means ESCAPE2 ,as ESCAPE1 only has 1 bit flag now,the low bit belongs to the coeff_tab.

cache <<= skip[mode];

reverse_event = &DCT3D[intra][GET_BITS(cache, 12)];

if ((level = reverse_event->event.level) == 0)

goto error;

*last = reverse_event->event.last;

*run = reverse_event->event.run;

if (mode < 2) {

/* first escape mode, level is offset */

level += max_level[intra][*last][*run]; // if level

} else {

/* second escape mode, run is offset */

*run += max_run[intra][*last][level] + 1;

}

代码对cache左移7位以后，取出其中的前两位，因为ESCAPE1前缀为00000110只有8位，左移7位后，只剩一位0，如果取两位的话要么是00，要么是01，而ESCAPE2前缀为000001110，左移7位再取两位值为10，同样的ESCAPE3取两位得到的为11，因此当这两位值小于3时，设置模式查找表skip来判断ESCAPE方式，若这两位值为0或1对应ESCAPE1，为2对应ESCAPE2，然后略过相应的位数，再取出12比特查找解码表得到“缩放”后的(run,level)，再根据ESCAPE方式，加上max_level或max_run就得到了最后的(run, level)游程值！