本节课内容 QM编码器 Golomb编码.

Presentation on theme: "本节课内容 QM编码器 Golomb编码."— Presentation transcript:

1 本节课内容 QM编码器 Golomb编码

2 QM编码器 二进制信源算术编码 只处理二进制信源符号 设计目标：简单、快速 对乘法操作进行近似 定点精度的整数算术编码
不断标定概率区间，使得近似结果接近于真正的乘法 在现代图像和视频压缩算法中广泛应用：JBIG, JPEG, JPEG2000, H.263, H.264

3 QM编码器 很多二值图像都存在局部结构 通过观察邻域状态，可以合理猜测当前像素的值 每种情况都是一个分布很不均衡的概率模型适合算术编码
在某个部分，大部分向素值为1（如背景区域） 而在另外某个部分，大部分向素值为0（如文字区域） 通过观察邻域状态，可以合理猜测当前像素的值 如邻域像素值为1，则当前像素值极有可能为1； 反之亦然 每种情况都是一个分布很不均衡的概率模型适合算术编码 对每种情况都分别采用一个算术编码器，以得到更好的性能（与对所有像素只用一个编码器相比）

4 QM编码器 例：像素值为0的概率 ，像素值为1的概率 则熵为： 若假设分为两个集合，分别包含80%和20%的像素
例：像素值为0的概率 ，像素值为1的概率 则熵为： 即只有一个算术编码器编码的话，平均码率将接近0.722比特 若假设分为两个集合，分别包含80%和20%的像素 第一个集合：95%的像素值为1 第二个集合：70%的像素为0 则两个集合的熵分别为0.286和0.881。如果对两个集合分别采用不同的算术编码器，则平均码率接近 JBIG/JPEG中采用多个模型（上下文），每个上下文对应不同的算术编码器，每个算术编码器的计算机制相同，只是概率模型不同。

5 QM编码器 基本思想：将输入符号（一个bit）分为大概率符号（More Probable Symbol, MPS）或小概率符号（Less Probable Symbol, LPS） 在输入下一位之前，编码器先利用一个统计模型（通常是上下文信息，如在黑-白图像编码中用二维的上下文）来预测MPS是0还是1，然后再输入该位并按其实际值分类 模型预测的MPS与实际值不一致，则编码器将该位归为LPS；否则继续归为MPS 输出流为MPS或LPS的流，MPS和LPS的概率动态更新，为算术编码器所用 解码器所知道的信息也是当前处理的位是MPS还是LPS，然后利用与编码器相同的统计模型得到信源符号的原值

6 QM编码器 令qc表示LPS的概率，并将较低的区间赋予MPS 符号 概率 累积概率 区间范围 LPS qc 1- qc [1- qc,1)
[0,1- qc) 1 1- qc

7 QM编码器 算术编码中的 的更新用 代替 出现MPS的迭代的规则为： 出现LPS的迭代的规则为 A A(1- qc)
符号 概率 累积概率 区间范围 LPS qc 1- qc [1- qc,1) MPS [0,1- qc) 算术编码中的 的更新用 代替 出现MPS的迭代的规则为： 出现LPS的迭代的规则为 A(1- qc) A 区间内的任何数字都可以作为输出，为简单起见，QM编码器将子区间的下界l作为输出

8 QM编码器 例： 初始化： 注意：当输入序列越来越长，区间越来越窄，l越来越大 符号 l A 初始值 1 LPS 0+（1-0.5）=0.5
1 LPS 0+（1-0.5）=0.5 1*0.5=0.5 MPS 0.5 0.5*（1-0.5）=0.25 （1-0.5）=0.625 0.25*0.5=0.125 0.625 0.125*(1-0.5)=0.0625

9 重新标定 在上例中，若 ，最后l=0.981，A=0.0081 当A太小，需要很高的精度才能将其与0分开
重新标定：对A和l同时放大一倍（对二进制数左移一位） 若A<0.5，可能需要重新标定多次（如上例中A=0.1，需重新标定3次，变成0.8） 输入LPS，肯定需要重新标定；输入MPS，可能需要重新标定，取决于A的具体值。 符号 l A 初始值 1 LPS 0+（1-0.1）=0.9 1*0.1=0.1 MPS 0.9 0.1*（1-0.1）=0.09 （1-0.1）=0.981 0.09*0.1=0.009 0.981 0.009*(1-0.1)=

10 重新标定 问题：找到一个阈值t，当A<t时，对A放大一倍； 另：A和2*A应尽量接近1，即：
找到t>0.5，使得 (max(1-t, 2t -1))最小  t=0.75. 另外，A的更新需要乘法 A := A (1 – qc) 或 A := Aqc JBIG委员会推荐用近似代替乘法 A 接近1时，A (1 – qc) 用 (A– qc)代替，Aqc用qc代替。 当采用最佳阈值t = 0.75, A 的值总是在区间 [0.75, 1.5)内 整数实现,大多数计算的字长为16位

11 条件交换 通过重新标定进行近似带来一个问题：分配给MPS的子区间可能比LPS分配的子区间还小 例： qc =0.45，输入4个MPS
由于用A= A- qc 去近似 A=A(1- qc) 例： qc =0.45，输入4个MPS 初始化：A=1，l=0 第1个MPS：A=0.55  A=1.1, l=0 第2个MPS：A=0.65  A=1.3, l=0 第3个MPS：A=0.85, l=0 第4个MPS：A=0.40, l=0 分配给MPS的区间为0.4，而分配给LPS的区间为qc =0.45 当接近0.5时会出现这种情况 A=A– qc A-qc= = 0.4

12 重新标定 发生这种情况的条件为： 解决办法：有条件交换（conditional exchange） 当满足上述条件时，交换两个区间
由于有条件交换只发生在重新标定时的近似过程中，只需在决定要重新标定后才测试交换的条件是否满足

13 重新标定 采用标定，修改后的编码器为： 总是要重新标定

14 重新标定 带有条件交换的重新标定近似的伪代码为：

15 QM解码器 解码过程为编码的逆过程 A A(1- qc)
初始化： ，分割线为A(1- qc)=1(1-0.5)=0.5，因此MPS和LPS对应的区间分别为 输入码字为C，对应编码中的l

16 QM解码器 解码器的伪代码为：

17 主要内容 游程编码 Golomb码 一元码 Golomb-Rice码 指数Golomb （ Exp-Golomb ）码 自适应Golomb码
在JPEG-LS (Lossless JPEG)中的应用

18 游程编码 许多0和不太多的1 简单游程码： 传真 图形 00000010000000001000000000010001001.....
对整数序列进行编码

19 一元码（Unary Code） 对非负整数n，用n个1和一个0表示（或者n个0和一个1） 在什么情况下是最佳码？ 为前缀码
当概率为1/2、1/4、1/8、1/16、1/32… 此时Huffman码就是一元码

20 实现 编码（Encoding）： 解码（Decoding）：

21 一元码 如果输入时负整数呢？ 可能的解决方案： 在JPEG-LS部分再详述

22 几何分布 （Geometric Distribution, GD）
参数为 的几何分布： 在Bernoulli实验中，在第一次成功之前失败次数为x的概率，失败的概率为 当参数 时，一元码为最佳前缀码： Huffman编码：不需要重新排序等价于一元码 一元码为最佳前缀码，但效率不高 Huffman编码需要重新排序，一元码不是最佳前缀码 平均长度=熵 一元码不仅是最佳前缀码，而且是所有熵编码中是最佳的（包括算术编码）

23 为什么用几何分布？ 几何分布对图像/视频压缩很有用 例：游程编码 i.i.d. 分布的二值序列
例： 熵<<1，前缀码的性能不好 游程编码对压缩数据很有效： r: 在两个1中间连续的0的个数：5，8，4，0，6 游程r的概率分布： n个0接着一个1 参数为 的单边几何分布

24 为什么用几何分布？ 例2：预测误差 大多数的 的值都很小，在0附近可用双边几何分布(GD)建模 双边GD可用单边GD近似：
减少自适应熵编码中上下文的数目 将负数映射成正数： 映射可能不止一个 在JPEG-LS中再详述

25 为什么用几何分布？ GD分布是对指数分布的离散近似。指数分布为：
双边几何分布为Laplacian分布（亦称为双边指数分布）的离散近似。Laplacian分布为：

26 Golomb码 对例如游程的几何分布，一种方式对游程用Huffman编码得到前缀码。
但游程的数目很大，而且可能不能预知，所以一个更好的办法是构造一个无限族的最佳前缀码，使得对无论多大的游程，在该前缀码族中都可以找到一个码字对该游程进行编码 该前缀码族与概率 有关，称为参数前缀码。Golomb码就是这样一组码，且对几何分布而言是最佳码 参数 越大，大的游程比较可能 参数 越小，大的游程不太可能出现

27 Golomb码 一种多分辨率的方法： 码字：（一元码，固定长度） 将所有数字分为等大小为m的组：表示为Golomb(m)或Golomb-m
符号值较小的组分配的码长较短 同一组内符号码长基本相等：码长的增长比一元码要慢得多 码字：（一元码，固定长度） 组号：一元码 每组内的索引编号：固定长度码 S. Golomb, Run-length encodings, IEEE Trans. Information Theory, Vol. 12, No. 3, Jul 1966, pp

28 Golomb码 r：余数，“固定长度”码 q: 商，用一元码 当 时，k比特： 当 时， m=8: 000, 001, …, 111
当 时， m=5: 00, 01, 10, 110, 111

29 Golomb码 m=5时的Golomb码（Golomb-5）：

30 Golomb码 m较小，Golomb码初始很短，但增长很快，适合RLE中 较小，即大游程很少的情况
n m = 0 m = 1 m = 2 m = 3 1 0 0 0 00 0 000 2 10 0 1 0 01 0 001 3 110 10 0 0 10 0 010 4 1110 10 1 0 11 0 011 5 11110 110 0 10 00 0 100 6 111110 110 1 10 01 0 101 7 1110 0 10 10 0 110 8 1110 1 10 11 0 111 9 110 00 1 000 m较小，Golomb码初始很短，但增长很快，适合RLE中 较小，即大游程很少的情况 m较大，初始Golomb码很长，但增长很慢，适合RLE中 较大，即大游程较多的情况

31 Golomb-Rice码 特定的Golomb码： 余数r为n的k低位 m=8：

32 实现 编码（Encoding）： 解码（Decoding）：

33 指数Golomb码（Exp-Golomb）
码字仍然包括两部分： （一元码，固定长度码）

34 实现 编码（Encoding）： 对 的组的码字： 对x用一元码编码 用X比特表示组内索引 组号（GroupID）：

35 实现

36 实现 解码（Decoding）：

37 为什么用Golomb码 Golomb码的重要性： 问题：
对任何几何分布（GD），可以找到一个Golomb码为最佳前缀码，且和熵尽可能接近（在所有的前缀码中） 问题： 怎样确定Golomb的参数？ 怎样将其应用到实际的编码器中？

38 几何分布的最佳码 参数为 的几何分布 当参数 时，一元码为最佳前缀码 当 时，怎样构造最佳一元码？ 怎样转化？：将m个事件组成一组
参数为 的几何分布 当参数 时，一元码为最佳前缀码 当 时，在所有的熵编码是最佳的 当 时，怎样构造最佳一元码？ 转化为 的几何分布（尽可能接近） 怎样转化？：将m个事件组成一组

39 几何分布的最佳码 当 时，每个x可以写成： 为参数为 的几何分布 若 ，一元码为 的最佳码  为最小的可能整数

40 几何分布的最佳码 怎样对 编码？ 对 ，如果 ，则  的码字比 多一个比特  的码长相等 这正好是Golomb码的格式：
怎样对 编码？ 对 ，如果 ，则  的码字比 多一个比特  的码长相等 这正好是Golomb码的格式： 对q用一元码编码 对余数用（近似）等长码编码 问题：怎样找到最佳的参数

41 Golomb参数估计（JPEG-LS） 自适应Golomb编码的目的： 怎样根据过去的数据估计 ？ 对给定数据，寻找最佳的参数m，使得
怎样根据过去的数据估计 ？ 对每个像素来说，计算费用太高

42 Golomb参数估计（JPEG-LS） 一种快速方法： 假设

43 自适应Golomb编码 初始化： For each End 初始估计的均值 对每个符号 ，用参数为k的Golomb码编码 在编码后更新：
If //重新归一化 End 防止溢出 慢慢忘记过去

44 JPEG-LS中的应用 JPEG-LS: 无失真JPEG（Lossless JPEG） JPEG中也有无失真算法，但没有被广泛采用
开始于1995，完成于1999 目标：只用最小的复杂性提高性能 基于HP实验室的LOCO-I （LOw COmplexity LOssless COmpression for Images)）算法：对图像进行低复杂性压缩 JPEG-LS比无失真JPEG 2000的性能更好 采用的技术： 预测 自适应Golomb码 上下文自适应编码 游程编码

45 JPEG-LS流程图 对输入样本以光栅顺序编码 游程模型： 预测模型： 在平坦区域采用（所有4个邻居都相等），此时前缀码不是很有效
在其他区域采用 根据上下文预测 确定上下文 在每个上下文中，对预测残差找到一个概率模型 对残差用自适应Golomb码编码

46 预测 根据3个邻居预测每个样本x的值 基于简单的边缘检测： 预测残差：

47 预测 此时，预测值在a, b, c确定的平面上 JPEG-LS中预测规则的一个等价表示为：

48 残差分布 若预测设计得很好，则可以用一个双边的几何分布来对残差进行建模： 由于使用整数预测，通常会出现偏差 T
偏差T可被分为其整数部分C和小数部分s： T = C - s. 可以估计并取消C 因此剩余的偏差为： s的值决定双边几何分布向单边几何分布的映射

49 残差分布：映射到单边GD 情况1： 情况2：

50 上下文模型 根据局部条件概率 对每个预测残差进行自适应Golomb码 上下文：邻域内样本的每个配置
可以利用高阶条件获得较小的熵（更好的压缩） 条件会降低熵 问题： 为了跟踪更多的上下文文会增加费用 对每个上下文没有足够多的训练数据来训练 JPEG-LS中的上下文：基于4个邻居的3个局部梯度 g1 = d – b, g2 = b – c, g3 = c – a.

51 上下文 g1 = d – b, g2 = b – c, g3 = c – a: 上下文量化： JPEG-LS：将每个梯度分为9个区域
如果a, b, c, d 在[0, 255]内，则会有太多可能的 {g1, g2, g3} 上下文量化： 将每个梯度分为大致等概率的区域 目的：最大化 x(n)和其邻居之间的互信息 JPEG-LS：将每个梯度分为9个区域 {g1, g2, g3}组合的总的数目： 仍然太多了！

52 上下文 对称性假设：为了进一步减少上下文的数目，假设
在JPEG-LS，当第一个非0的gi是负数，将采用 上下文 –{g1, g2, g3}，并将ε编码为–ε。 解码器：当解码器发现第一个非0的gi是负数，也采用 –{g1, g2, g3}为上下文来解码残差，然后翻转符号。 通过对称性假设，上下文的数目合并为： 总的上下文数目为： = 365.

53 自适应Golomb编码 对每个像素： 1. 根据邻居计算预测值 2. 确定上下文索引λ
将每个上下文映射成单边GD后，都应该进行该过程：

54 自适应Golomb编码 为了方便参数估计，对每个上下文，维护： Aλ：上下文λ中|ε|之和 Nλ：上下文λ中的事件总数目
C/C++ 实现：for (i = 0; (N << i) < A; i++); 为了消除预测残差中整数偏差C的影响，对每个上下文，维护： Bλ：上下文λ中所有ε 之和

55 自适应Golomb编码 在编码后更新： 偏差更新：由于整数偏差在以前的ε中被去掉， Bλ / Nλ的值不会太大 Aλ = Aλ + |ε|;
If Nλ = Nλ + 1. 偏差更新：由于整数偏差在以前的ε中被去掉， Bλ / Nλ的值不会太大

56 游程模式 当所有4个邻居都相同时，编码器进入游程模式 x 极有可能也为相同值 前缀码此时不是很有效
对游程r进行编码：r为像素值连续相同的像素数目 游程r满足单边几何分布。

57 Reading Golomb码： JPEG-LS：
电子书Data Compression The Complete Reference, 3rd Edition第2.4节 JPEG-LS： M. Weinberger, G. Seroussi and G. Sapiro, The LOCO-I lossless image compression algorithm: principles and standardizations into JPEG-LS, IEEE Trans. Image Processing, Vo.. 9(8), pp , Aug 《数据压缩原理与应用》第4.7节

58 下节课内容 字典编码