第一章：概率统计基础

Size: px

Start display at page:

Download "第一章：概率统计基础"

淞唱绍
5 years ago
Views:

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

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

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

4 QM 编码器 P ( ) = ( ) 例 : 像素值为 0 的概率 0 0.2, 像素值为 1 的概率 P 1 = 0.8 则熵为 : H = 0.2log log 0.8 = 即只有一个算术编码器编码的话, 平均码率将接近比特若假设分为两个集合, 分别包含 80% 和 20% 的像素第一个集合 :95% 的像素值为 1 第二个集合 :70% 的像素为 0 则两个集合的熵分别为和如果对两个集合分别采用不同的算术编码器, 则平均码率接近 = 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 0 QM 编码器令 q c 表示 LPS 的概率, 并将较低的区间赋予 MPS q c [ 0,0.5] 符号概率累积概率区间范围 LPS q c 1- q c [1- q c,1) MPS 1- q c 0 [0,1- q c ) 1 1- q c

7 QM 编码器符号概率累积概率区间范围 LPS q c 1- q c 0 [1- q c,1) MPS 1- q c [0,1- q c ) n n 算术编码中的 l, u 的更新用 l n, A n = u n l n 代替 ( ) ( ) ( n) ( n 1) ( n 1) ( ) ( ) ( ) ( ( ) ( 1) ) ( 1) 出现 MPS 的迭代的规则为 : ( n) ( n 1) A = A 1 q 出现 LPS 的迭代的规则为 ( ) A = A F x F x = A P x n n 1 n 1 X n X n n l = l + A F x l ( n) ( n 1) = l ( n) ( n 1) A = A q X ( ) ( n) ( n 1) ( n 1) c c n ( 1 ) l = l + A q c ( ) ( ) ( ) ( ) 区间内的任何数字都可以作为输出, 为简单起见,QM, 编码器将子区间的下界 l 作为输出 ( ) ( k k l ) u = l + u l ( k) ( k 1) ( k 1) ( k 1) ( x ) ( k) ( k 1) ( 1) ( 1) l = l + u F ( x 1) A A(1- q c ) 0 A q c F X X ( q ) A 1 c k k

8 q 例 : c = 初始化 : l QM 编码器 ( LPS MPS LPS MPS ) 0.5, Input:,,, ( 0) ( 0) = 0, A = 1 符号 l A 初始值 0 1 LPS 0+(1-0.5)=0.5 1*0.5=0.5 MPS *(1-0.5)=0.25 LPS MPS (1-0.5)= *0.5= *(1-0.5)= 注意 : 当输入序列越来越长, 区间越来越窄,l 越来越大

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

10 重新标定问题 : 找到一个阈值 t, 当 A<t 时, 对 A 放大一倍 ; 另 :A 和 2*A 应尽量接近 1, 即 : 找到 t>0.5, 使得 (max(1-t, 2t -1)) 最小 t=0.75. 另外,A 的更新需要乘法 A := A (1 q c ) 或 A := Aq c JBIG 委员会推荐用近似代替乘法 A 接近 1 时,A (1 q c ) 用 (A q c ) 代替,Aq c 用 q c 代替当采用最佳阈值 t = 0.75, A 的值总是在区间 [0.75, 1.5) 内

11 条件交换通过重新标定进行近似带来一个问题 : 分配给 MPS 的子区间可能比 LPS 分配的子区间还小由于用 A= A- q c 去近似 A=A(1- q c ) 例 : q c =0.45, 输入 4 个 MPS 初始化 :A=1,l=0 第 1 个 MPS:A=0.55 A=1.1, l=0 A=A q c 第 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 的区间为 q c =0.45 当接近 0.5 时会出现这种情况

12 重新标定发生这种情况的条件为 : q > A 2, or q > A q c c c 解决办法 : 有条件交换 (conditional exchange) 当满足上述条件时, 交换两个区间由于有条件交换只发生在重新标定时的近似过程中, 只需在决定要重新标定后才测试交换的条件是否满足

13 重新标定采用标定, 修改后的编码器为 : When MPS is encoded Begin l is unchanged; A := A - q c ; If (A<0.75) then Renormalize A and l; endif End When LPS is encoded Begin l := l+ A-q c ; A := q c ; Renormalize A and l; End 总是要重新标定

14 重新标定带有条件交换的重新标定近似的伪代码为 : When MPS is encoded When LPS is encoded Begin Begin l is unchanged; If (A- q c >= q c ) then A := A - q c ; l := l + A- q c ; A = q c ; If (A<0.75) then Else If (A< q c ) then A := A-q c l := l + A; endif A = q c ; Endif Renormalize A and l; End Renormalize A and l; endif End

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

16 QM 解码器解码器的伪代码为 : Input C, A=1 and Begin X := A (1- q c ); MPS_interval = [0,X); LPS_interval = [X, A); If C is in the MPS_interva then Output MPS symbol; C is unchanged; A := A (1- q c ); Else Output LPS symbol; C := C A (1- q c ); A := Aq c ; Endif End

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

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

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) 参数为的几何分布 : x P( x) = ρ ( 1 ρ ), x Z+ 在 Bernoulli 实验中, 在第一次成功之前失败次数为 x 的概率, 失败的概率为 ρ 当参数 12时, 一元码为最佳前缀码 : ρ = 1 4 : P x : 0.75, 0.19, 0.05, 0.01, 0.003,... Huffman 编码 : 不需要重新排序等价于一元码一元码为最佳前缀码, 但效率不高 ρ = ρ ρ ( ) ( ) 3 4 : P x : 0.25, 0.19, 0.14, 0.11, 0.08,... Huffman 编码需要重新排序, 一元码不是最佳前缀码 ρ =1 2: 平均长度 = 熵一元码不仅是最佳前缀码, 而且是所有熵编码中是最佳的 ( 包括算术编码 )

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

24 为什么用几何分布? 例 2: 预测误差 e n = x n pred x 1,..., x n 1 ( ) ( ) ( ) ( ) ( ) 大多数的 e n 的值都很小, 在 0 附近可用双边几何分布 (GD) 建模 1 ρ x P( x) = ρ,0< ρ < 1 1+ ρ 双边 GD 可用单边 GD 近似 : 减少自适应熵编码中上下文的数目将负数映射成正数 : 映射可能不止一个在 JPEG-LS 中再详述 ( )

25 为什么用几何分布? GD 分布是对指数分布的离散近似指数分布为 : ( ) x f x = λe λ 双边几何分布为 Laplacian 分布 ( 亦称为双边指数分布 ) 的离散近似 Laplacian 分布为 : 1 f ( x) = λe λ 2 x

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 码 n n= qm+ r = m+ r m r: 余数, 固定长度码 q: 商, 用一元码 m = 2 k 当时,k 比特 : m=8: 000, 001,, 111 m 2 k 当时, r r k 2 - > m, k 2 -m, k k = log2 m 1 比特, 以 k个 1结束 m=5: 00, 01, 10, 110, 111 k 比特

29 Golomb 码 m=5 时的 Golomb 码 (Golomb-5):

30 Golomb 码 n m = 0 m = 1 m = 2 m = m 较小,Golomb 码初始很短, 但增长很快, 适合 RLE 中较小, 即大游程很少的情况 m 较大, 初始 Golomb 码很长, 但增长很慢, 适合 RLE 中较大, 即大游程较多的情况 ρ ρ

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

32 实现编码 (Encoding): 解码 (Decoding):

33 指数 Golomb 码 (Exp-Golomb) Golomb 码将字母分为等大小的组在 Exp-Golomb 码中, 组的大小呈指数增长码字仍然包括两部分 : ( 一元码, 固定长度码 )

34 实现编码 (Encoding): x > 0 对的组的码字 : 对 x 用一元码编码用 X 比特表示组内索引组号 (GroupID): log2 n + 1 ( )

35 实现

36 解码 (Decoding): 实现

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

38 几何分布的最佳码参数为 ρ 的几何分布 P n ( X = n) = ρ ( 1 ρ ) 当参数当 ρ 12 ρ = 12 时, 一元码为最佳前缀码时, 在所有的熵编码是最佳的当 ρ >1 2时, 怎样构造最佳一元码? ρ 1 2 转化为的几何分布 ( 尽可能接近 ) 怎样转化?: 将 m 个事件组成一组

39 几何分布的最佳码 ρ >1 2 x = xm+ x 当时, 每个 x 可以写成 : X q q m 1 m 1 为参数为 r, qm+ r qm qm ( ) ( ) ( 1 ) ( 1 ) ( m = 1 ) X + = ρ ρ = ρ ρ = ρ ρ P q P qm r r= 0 r= 0 ρ m x ( ) = ( 1 ) P x ρ ρ 的几何分布 X q m 若 ρ 12, 一元码为的最佳码 1 ρ 1+ ρ m 1 1, m= log ρ log 2 2 ρ 为最小的可能整数

40 几何分布的最佳码怎样对 X r 编码? n m 对 P X = n = ρ 1 ρ, 如果 ρ = 12, 则 X = n+ m 的码字比 X = n 多一个比特 P ( ) ( ) n m n ( X = n+ m) = ρ + ( 1 ρ) = 1 2ρ ( 1 ρ) = 1 2P( X = n) X = n, n+ 1,..., n+ m 1 这正好是 Golomb 码的格式 : 对 q 用一元码编码对余数用 ( 近似 ) 等长码编码的码长相等问题 : 怎样找到最佳的参数 m? ( m= 2 k )

41 Golomb 参数估计 (JPEG-LS) 自适应 Golomb 编码的目的 : 对给定数据, 寻找最佳的参数 m, 使得 ρ 怎样根据过去的数据估计 ρ? ( ) = ( 1 ) P x E x ρ ρ x ρ E = ρ xρ = ρ = 1 1+ E ( X) ( 1 ) x= 0 ( ) ( X ) m ( ρ ) m 12 ( X ) ( X ) ( ) ( X ) m X 1 1 X ρ E m 1 log + E = 1+ E 2 E m ( X ) ( X ) k 1+ E = 2 k log2 1 log E 对每个像素来说, 计算费用太高

42 Golomb 参数估计 (JPEG-LS) E ( X ) = ρ ( 1 ρ ) 一种快速方法 : 假设 ρ 1, 1 ρ 0 ( 1 ρ ) m ( ( )) m m ρ = 1 1 ρ 1 m( 1 ρ) 1 m = 1 ρ E m 1 k 1 ρ m= 2 E 2 2 ( X) ( X ) k 1 = max 0, log2 E( X) 2

43 初始化 : A= ˆ μx, N = 1 For each n = 0,1,2,... k 自适应 Golomb 编码 A max 0, log2 2 N x n 初始估计的均值对每个符号, 用参数为 k 的 Golomb 码编码 1 k = max 0, log2 E( X) 2 End 在编码后更新 : N = N max If // 重新归一化 A= A 2, N = N 2 A A x N N = +, 1 n = + 防止溢出慢慢忘记过去

44 JPEG-LS 中的应用 JPEG-LS: 无失真 JPEG(Lossless JPEG) JPEG 中也有无失真算法, 但没有被广泛采用 JPEG-LS: 开始于 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 中预测规则的一个等价表示为 : xˆ = median, ( a, b a + b c)

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

49 残差分布 : 映射到单边 GD 情况 1: s 12 情况 2: s > 12

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

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

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

53 自适应 Golomb 编码对每个像素 : 1. 根据邻居计算预测值 2. 确定上下文索引 λ 3. 利用当前上下文索引 λ 的条件概率, 用自适应 Golomb 码对预测残差编码为了估计 Golomb 参数 : 1 k = max 0, log2 E( X) 2 将每个上下文映射成单边 GD 后, 都应该进行该过程 : 1 k max = 0, log ( ) ( ) 2 E ε λ max 0, log 2 ε λ 2 E ε 2 ε { }

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

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

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

57 Reading Golomb 码 : 电子书 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 字典编码下节课内容

Book1

Book1 經辦網點名稱網點位址第一支行營業室廣東省廣州市越秀區沿江中路 193 號第二支行營業室廣東省廣州市沿江西路 145 號吉祥支行廣東省廣州市東風中路 313 號荔灣支行營業室廣東省廣州市荔灣區南岸路 63 號三樓北京路支行營業