变长编码二元化

Created at 2017-08-31 Updated at 2017-10-17 Category 2017年9月 Tag 视频编码

变长编码

在视频编码当中，有存在很多的冗余，各种方法的设计都是为了消除这些冗余，从而在压缩程度上达到最好。

在编码过程中，如果我们要编码的数的范围时从0到7，那么0和1只需要一个比特就可以表示，7需要三个比特，那么我们都统一用三个比特进行表示的话。那么小的数就会浪费一些比特。

所以在这种情况下，我们就出现了变长编码。也就出现了一些生成变长码的方法，这里只说明其中比较重要的两个，哥伦布编码（EGK）和截断莱斯（TR）。

K阶哥伦布编码

一个非负整数的K阶哥伦布码的生成步骤：

1、将需要编码的整数以二进制的形式写出，去掉最低的K个比特位，之后加1。

2、统计剩下的比特数，将次数减一，就是需要增加的前缀零的个数。

3、把之前去掉的K个比特位补回到比特串的末尾。

现在举个例子说明，比如说整数5的1阶码：

1、5的二进制形式时 101，那么去掉最低1位的比特位，就变成10，之后再加1，就是11。
2、11就是2个比特数，把2减一就是1，也就是需要补1个前缀0，那么现在的比特就变成011。
3、把之前去掉的最低1位的1补回到比特串的结尾，就变成0111，这就是整数5的1阶哥伦布码。

编码完，我们现在要知道怎么解码。
解码原理：根部编码的时候，我们知道第一步去掉k个比特，第三步的时候补上了，所以这k个比特的值是没有改变的，就是在第一步的最后，我们还加了一个1，那么我们在解码的时候就是要将这个1减掉。那么因为第三步又加了k个比特，就相当于第一步的那个1，是2^k的大小，所以就是把所有的值减去2^k,就是解码会来的值。
例如：
上面的整数5的2阶码为 01001，那么这个二进制的值为9-2^2 = 5。
或者按照书中的codeNum = 2^(m+k)-2^k+value(这个值为后m+k个二进制的值)也是一样的。

接着，我们用代码实现一下。

编码的时候：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
	
    int value = 5;//这个就是需要编码的值
    int pre = (value >> k)+1;//这个实现的就是第一步。
    int m = (int)log2(pre);//获取前面的0的个数，之前还不知道怎么取，
//还用一个变量右移然后求出个数。也就是第二步。
    int last = value - ((value>>k)<<k);//求出右移k的比特，因为之后要加到比特串后面。
    pre = pre << (32 - (2*m+1));//把前半部分比特移动最左边，我们之后好一个一个取出来传输。
    int res = pre | (last<<(32-(2*m+k+1)));//这个就是最后要编码的值。也就是0111 后面还有很多零。
    unsigned int mark = 0x80000000;//这边一定要用无符号，不然的话有符号，右移的话会根据符号进行填充左边的值，而不是填充0。
    for(int i = 0; i < 2*m+k+1; i++){
        int bit = !!(mark & res);//取出每一个bit。
        printf("%d\t",bit);
        put_cabac_bypass(enc_context.cabac_context,bit);
        mark >>= 1;
    }

解码的时候：

1
2
3
4
5
6
7
8
9
10
11
12
   
int value = 0;
     int m = 0;
     int k = 1;
     while(get_cabac_bypass(dec_context.cabac_context) == 0){
         m++;//知道前面有多少个零。
     }
     for(int i = 0; i < m+k; i++){
         value = (value << 1) + get_cabac_bypass(dec_context.cabac_context);//求出后面的值。
     }
     int res = ((1<<(m+k))-(1<<k)+value);//根据之前的公式求出最后的值。

这个指数哥伦布还有有符号的时候，对应的关系是：

CodeNum = {2V-1, V > 0; -2V , V <= 0}

CodeNum及其对应的有符号数的V

截断莱斯编码

一个非负整数截断莱斯码的生成步骤：

在已知门限值cMax，和莱斯参数R,已经需要编码的值V，就可以获得截断莱斯的二元码串。截断莱斯码分为前缀和后缀。

1、前缀的计算方法为： P = V >> R;

2、 若P<(cMac>>R),则前缀由P个1和一个0组成，长度为P+1。若P >= (cMac>>R)，则由（cMax>>R）个1组成，长度为（cMac>>R）。

2、当V=cMax的时候没有后缀值。

PS: 其实当R设置为0的时候，也就是让它没有后缀码。

在代码实现之前，我们可以把截断莱斯码列出来看一下。

cMax = 6, r = 1

同样，我们代码实现一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int value = i;
int r = 1;
int cMax = 6;
int p = value >> r;//这个实现的就是第一步。
int pre = 0;
int res = 0;
unsigned int mark = 0x80000000;
if((value>>r) < (cMax>>r)){
    if(p){
        pre = 0xffffffff << (32-p);
    }
    int s = value-(p<<r);
    res = pre | s <<(32-r-p-1);
    for(int i = 0; i < p+1+r; i++){
        int bit = !!(mark & res);
        put_cabac_bypass(enc_context.cabac_context,bit);
        mark >>= 1;
    }
}else{
    res = 0xffffffff <<(32-(cMax>>r));
    for(int i = 0; i < (cMax>>r); i++){
        int bit = !!(mark & res);
        put_cabac_bypass(enc_context.cabac_context,bit);
        mark >>= 1;
    }
}

解码代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
	
int value = 0;
   int r = 1;
   int cMax = 6;
   int p = 0;
   int t = cMax >> r;
   while(get_cabac_bypass(dec_context.cabac_context) == 1 && p < t){
       p++;
   }
   if(p >= t){
       value = cMax;
   }else{
       int suf = 0;
       for(int i = 0; i < r; i++){
           suf = (suf << 1) + get_cabac_bypass(dec_context.cabac_context);
       }
       value = (p<<r) + suf;
   }

通过上面的分析，我们会发现，这个cMax的值和莱斯参数R不是随便设置都可以的。
我们知道，当R = 0和 Value = cMax的这两种情况是没有后缀码的。

但是如果cMax = 7 ，R = 1。那么当Value = 6的时候的前缀码等于Value = 7的前缀码，但是一个有后缀，一个无后缀，我们在解码的时候就没有办法确定。所以cMax = 7,R = 1。这种设置就是不合理的。

所以截断莱斯还会配合着指数哥伦布使用。