哥伦布(Golomb)压缩编码

2020年12月11日 / 219次阅读 / Last Modified 2020年12月11日
算法

Golomb

哥伦布(Golomb)编码是一种无损的数据压缩方法,由数学家Solomon W.Golomb在1960年代发明。Golomb编码只能对非负整数(unsigned int)进行编码。当待编码符号表中的符号出现的概率符合几何分布(Geometric Distribution)时,使用Golomb编码可以取得最优效果,也就是说Golomb编码比较适合小数字比大数字出现概率高的场景编码。它使用较短的码长编码较小的数字,较长的码长编码较大的数字。

Golomb编码是一种分组编码,需要一个正整数参数m。用m对待编码的数字(n)进行求商(q=int(n/m))和余(r=n%m),然后对商做一元编码,对余做固定长度的二进制编码(用固定bit数来表示余数)。对余数(r)的编码,有个细节要注意。整体如下图:

下图是wiki上的一个case:

m=10,余数从0到9,让一部分余数用3个bit表示,一部分用4个bit表示,能够其它压缩的效果(比全部都用4个bit强)。

有了m,通过bitstream,得到q和r,就能解码。

Rice–Golomb

Rice-Golomb是Golomb编码的一个变种,它给Golomb编码的参数m添加了个限制条件,m必须是2的次幂。这样有两个好处:

  • 求余更简单:r = N & (m-1)
  • 对余数的编码,由于m是2的幂,编码也简单了
>>> 8%4
0
>>> 8 & (4-1)
0
>>> 55%4
3
>>> 55 & (4-1)
3

Exp-Golomb

Exp-Golomb编码的变化较大,我觉得它只是有点Golomb编码的形式,编解码的方式完全不一样。

Exp-Golomb的码元结构是:[M zeros prefix] [1] [Offset]

Exp-Golomb编码中,有一个阶的概念,K。不同K值的选择,编码长度不太一样。看图吧:

当k=0时,解码:

>>> k=0
>>> 2**0 - 1
0
>>> 2**1 - 1 + 0
1
>>> 2**1 - 1 + 1
2
>>> 2**2 - 1 + 0
3
>>> 2**2 - 1 + 1
4
>>> 2**2 - 1 + int('10',2)
5
>>> 2**2 - 1 + int('11',2)
6
>>> 2**3 - 1 + int('000',2)
7
>>> 2**3 - 1 + int('001',2)
8
>>> 2**3 - 1 + int('010',2)
9
>>> 2**3 - 1 + int('011',2)
10
>>> 2**3 - 1 + int('100',2)
11
>>> 2**3 - 1 + int('101',2)
12
>>> 2**3 - 1 + int('110',2)
13
>>> 2**3 - 1 + int('111',2)
14
>>> 2**4 - 1 + int('0000',2)
15

k不为0时,编解码方式不一样。

AVC和HEVC,都是用0阶Exp-Golomb编码。

-- EOF --

本文链接:https://www.pynote.net/archives/3020

留言区

《哥伦布(Golomb)压缩编码》有1条留言

您的电子邮箱地址不会被公开。 必填项已用*标注

  • 麦新杰

    HEVC在CABAC解码部分,将EGk编码中的1和0的含义刻意颠倒了,ue部分的解码与本文中0和1的含义一致,真坑... [回复]


前一篇:
后一篇:

More


©Copyright 麦新杰 Since 2019 Python笔记

go to top