H.264 中的指数哥伦布编码(Exponential-Golo

2019-03-14 本文已影响0人 smallest_one

1. 参考

[1] wikipedia/Exponential-Golomb_coding
[2] T-REC-H.264-201704-I
[3] The H.264 Advanced Video Compression Standard
[4] Zhuli/Lec 03 Entropy and Coding II Hoffman and Golomb Coding
[5] wikipedia/Golomb_coding
[6] QM_Golomb

2. 概述

指数哥伦布编码(Exponential-Golomb coding, Exp-Golomb)是一种通用的压缩编码方法。Teuhola在1978年提出[4]。

3. H.264 中的指数哥伦布编码规则

下面展示了指数哥伦布(Exp-Golomb)编码的码字(codeword)前面的一部分，code_num为codeword的序号。

code_num ⇒ code_medium ⇒ codeword
 0 ⇒ 1 ⇒ 1
 1 ⇒ 10 ⇒ 010
 2 ⇒ 11 ⇒ 011
 3 ⇒ 100 ⇒ 00100
 4 ⇒ 101 ⇒ 00101
 5 ⇒ 110 ⇒ 00110
 6 ⇒ 111 ⇒ 00111
 7 ⇒ 1000 ⇒ 0001000
 8 ⇒ 1001 ⇒ 0001001

可以根据以下规则从code_num得到codeword：

把code_num+1写成2进制的形式。
假设2进制表示使用的比特数量为n，增加n-1个0在之前的比特前面。

可以看出codeword的结构是有规则的：

codeword长度随着code_num的增加而增加。
每个codeword不需要查找表，可以逻辑地构造出来。

1个Exp-Golomb的codeword有以下的结构：
[Zero prefix] [1] [INFO]

codeword由M个前缀0组成，M>=0。
前缀0之后有一个1。
1之后是INFO。

每个codeword可以通过以下函数推导出来：
$M = floor(log2(code\_num + 1))$

$INFO = code\_num + 1 - 2^{M}$

相反的，
$code\_num = 2^{M} + INFO - 1$

注意： $len(codeword) = 2M + 1$

示例:
(a) code_num = 107

$log2(108) = 6.754. . ., M = 6$
$INFO = 107 + 1 – 2^{6} = 44_{10} = 1011002_2$
$codeword = 0000001101100$

(b) codeword = 000000011100011

$M = 7$
$INFO = 11000112_2 = 99_{10}$
$code\_num = 2^{7} + 99 – 1 = 226$

表（Mappings to code num）

Mapping type	Description
ue	无符号数：code_num = k. 使用于宏块类型、参考帧index等。
te	截断方式：如果编码变量k<=1，则发送一个比特 b, b = !code_num，如果k>1则，使用ue的方式。
se	有符号数：使用于MVD, delta QP等。编码变量k与num的对应关系如下： code_num = 2\|k\| (k ≤ 0) code_num = 2\|k\| − 1 (k > 0) $k = (−1)^{code\_num+1}ceil(code\_num / 2)$
me	映射表：k与code_num的对应关系通过标准中特定的映射表确定.

示例
在Baseline Profile设置下，一个帧内编码的宏块各符号的编码情况如下[2]：

Symbol name	Mapping	Notes
mb_type	ue(v)	Macroblock type; unsigned mapping to Exp-Golomb code with variable number of bits.
ref_index_l0	te(v)	Reference picture index, one per macroblock partition; truncated unsigned mapping to Exp-Golomb code.
mvd_l0	se(v)	Motion vector difference, two per macroblock partition; signed mapping to Exp-Golomb code.
coded_block_pattern	me(v)	Identifies 8 × 8 blocks containing non-zero coefficients; mapping to Exp-Golomb code according to specific table(s) in H.264 standard.
mb_qp_delta	se(v)	Differentially coded quantizer parameter; signed mapping to Exp-Golomb code
Residual. . .		Residual data coded using CAVLC.

4. Golomb 编码家族

Golomb Coding由Solomon W. Golomb于1960年发明。

Golomb Code 家族包括:

Unary Code
Golomb Code
Golomb-Rice Code
Exponential Golomb Code

4.1 Unary Code(Comma Code)

使用“n个1和1个0”(或者“n个0和1个1)来编码1个非负整数。

image.png

编码实现

UnaryEncode(n) {
    while (n > 0) {
        WriteBit(1);
        n--;
    }
    WriteBit(0);
}

解码实现

UnaryDecode() {
    n = 0;
    while (ReadBit(1) == 1) {
        n++;
    }
    return n;
}

4.2 Golomb Code

把所有的数字分成相同大小的组，大小为 $m$ 。
o 表示为Golomb(m)或Golomb-m。
值越小的符号组码长越短。
同一组符号的码长相似。
o 码长增长的速度要比unary code慢。

image.png

码字(codeword)

分为unary code和固定长编码。

golomb.png

$n = qm + r = \lfloor\frac{n}{m}\rfloor m + r$

注：其中r=n%m。

对q使用unary code

image.png

对r使用固定长度编码，有两种情况要考虑

如果 $m=2^k$ ，比如m=8，则r的码字为{000, 001, ......, 111}。
如果 $m!=2^k$ , 对更小的r分配 $\lfloor log_{2}m\rfloor$ 个比特，对更大的r分配 $\lceil log_{2}m\rceil$ 个比特，比如m=5，则r的码字为{00, 01, 10, 110, 111}

image.png

4.3 Golobm-Rice Code

$m=2^k$ 的一种特殊的Golobm code。

r正好是n低位的k个比特。

image.png

编码实现

GolombEncode(n, RBits) {//RBits表示r使用的比特个数，比如m=8时，r=3,
    q = n >> RBits;
    UnaryCode(q);
    WriteBits(n, RBits);//输出低RBits的表示
}

解码实现

GolombDecode(RBits) {
    q = UnaryDecode();
    n = (q << RBits) + ReadBits(RBits);
    return n;
}

4.4 指数哥伦布编码(Exponential Golomb Code, Exp-Golomb)

在Exp-Golomb中，组的大小是指数型增长的。

image.png

编码依然包含两部分
o Unary code和固定长度的编码

image.png

ExpGolombDecode() {
    GroupID = UnaryDecode();
        if (GroupID == 0) {
        return 0;
    } else {
        Base = (1 << GroupID) - 1;
        Index = ReadBits(GroupID);//读取GroupID个比特
        return (Base + Index);
}

5. 为什么使用Golomb编码

5.1 几何分布

$P(n) = p^{n}(1-p)$ , n>=0。
在一系列独立的Yes/No实验(伯努利试验)中，假设每次一次实验失败的概率为p，则直到第n+1次才成功的概率可以用上式表示。

当p<=1/2时，unary code是最优的前缀码。
p=1/4时，P(n)的取值为：0.75, 0.19, 0.05, 0.01, 0.003, ...
o 哈夫曼编码不需要重新排序——>等价于unary code。
o unary code是最优的前缀代码，但效率不高。( 平均长度 >> 熵)
p=3/4时，P(n)的取值为：0.25, 0.19, 0.14, 0.11, 0.08, ...
o 哈夫曼码需要重新排序，unary code不是最优前缀码。
p=1/2时，期望长度=熵。
o unary code不仅是最优前缀码，而且是所有前缀码中最优的熵编码(包括算术编码)。

几何分布对图像/视频压缩非常有用

示例1：游程编码(run-length coding)

假设二进制的序列是独立同分布。
$P(0) = p \approx 1$
序列样例：0000010000000010000110000001
熵 << 1，前缀码的性能很差。
游程编码用来压缩这样的数据很高效：
o r：统计1之间连续出现的0的个数
o 序列样例用游程编码可以表示为：5, 8, 4, 0, 6
游程编码r的统计概率
o $P(r=n) = p^{n}(1-p), n个0后面有1个1。
o r服从参数为p的单边的几何分布。

image.png

几何分布是指数分布的离散类比

image.png

双边的几何分布是拉普拉斯(Laplacian)分布(也叫双指数分布，double exponential distribution)的离散类比

Laplacian distribution.png

Golomb编码的重要性

对于任何几何分布(GD)， Golomb编码都是最优的前缀编码，并且尽可能接近熵(在所有前缀代码中)。

image.png

对于几何分布 $P(X=n) = p^{n}(1-p)$

当p<=1/2时，unary code是最优的前缀码。
o 在p=1/2时，在熵编码中也是最优的。

当p>1/2时，如何设计最优编码？

转换成p<=1/2的几何分布(近可能的接近)
如何做到呢？通过把m个事件组合在一起。
每个x可以写成： $x = x_{q}m + x_{r}$

image.png
$X_{q}服从参数为$ p^{m} $的几何分布$
当 $p^{m}<=1/2$ 时，Unary code是最优的
=> $m>=-\frac{1}{log_{2}{p}}$ ，所以$m=\lceil -\frac{1}{log_{2}{p}}\rceil是最小可能的整数。