目录

1. 参考
2. 概述
3. H.264 中的指数哥伦布编码规则
4. Golomb编码家族
5. 为什么使用Golomb编码
6. 总结

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：

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

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

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

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

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

每个codeword可以通过以下函数推导出来：

相反的，

注意：

示例:
(a) code_num = 107

(b) codeword = 000000011100011

表（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)
me	映射表：k与code_num的对应关系通过标准中特定的映射表确定.

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

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

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

image.png

码字(codeword)

• 分为unary code和固定长编码。

  
  
  golomb.png

注：其中r=n%m。

对q使用unary code

image.png

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

1. 如果，比如m=8，则r的码字为{000, 001, ......, 111}。
2. 如果, 对更小的r分配个比特，对更大的r分配个比特，比如m=5，则r的码字为{00, 01, 10, 110, 111}

image.png

4.3 Golobm-Rice Code

的一种特殊的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 几何分布

, 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)

• 假设二进制的序列是独立同分布。
• 
• 序列样例：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<=1/2时，unary code是最优的前缀码。
  o 在p=1/2时，在熵编码中也是最优的。

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

• 转换成p<=1/2的几何分布(近可能的接近)

• 如何做到呢？通过把m个事件组合在一起。

• 每个x可以写成：
  

  image.png

• p^{m}

• 当时，Unary code是最优的
  => ， 所以$m=\lceil -\frac{1}{log_{2}{p}}\rceil是最小可能的整数。

寻找自适应Golomb编码的目标：对于给定的数据寻找最佳的m使得

如何从过去的统计数据找到p

image.png

image.png

6. 总结

指数哥伦布编码是一种通用的熵编码方式，编码规则比较简单，不需要知道编码数据的概率分布。

但是压缩效率是怎么而来的呢，还没有找到参考