第一章：概率统计基础

Size: px

Start display at page:

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

琪汉赵
5 years ago
Views:

1 第三章 :Huffmn 编码信源概率模型已知的 Huffmn 编码信源概率模型未知的 Huffmn 编码自适应 Huffmn 编码 Huffmn 编码中的码字设计最小方差 Huffmn 编码规范 Huffmn 编码应用 : 文本图像语音

2 Shnnon-Fno 编码第一个基于 Shnnon 理论的编码次优码 ( 其研究生 Dvi Huffmn 改进成了最优码 ) 算法以空码开始计算所有符号的频率 / 概率对所有符号按其概率排序将符号集合划为为两个概率差异最小集合在第一个集合的码字前加 0, 在第二个集合的码字前加对划分得到的两个子集递归编码, 知道每个集合不能被再划分

3 Shnnon-Fno 编码 (2) 0 0 f f

4 Shnnon-Fno 编码 (3) 0 0 f f

5 Shnnon-Fno 编码 (4) 00 0 f f

6 Shnnon-Fno 编码 (5) 00 0 f f

7 Shnnon-Fno 编码 (6) f f

8 Shnnon-Fno 编码 (7) f f

9 Shnnon-Fno 编码 (8) f f

10 Shnnon-Fno 编码 (9) f f

11 Shnnon-Fno 编码 (0) f f

12 Huffmn 编码由 Dvi Huffmn 提出 :Rort Fno 的信息论作业 Shnnon-Fno 编码的改进 Dvi. Huffmn. A Mtho for th Constrution of Minimum Runny Cos. Proing of th IRE, 40(9): 098-0

13 最优前缀码最优码的一些重要性质. 出现频率越高的符号的码长应该越短 2. 出现频率最低的两个符号其长度应该相等证明. 假设相反该编码肯定是次优的 2. 假设相反令 X, Y 表示出现频率最低的两个符号, 且 o(x) = k, o(y) = k+ 则由于是前缀码,o(X) 不能为 o(y) 的前缀同时, 所有其他的码字更短去掉 o(y) 的最后一个比特将产生一个新的更短的前缀码!!! 这与最优码相矛盾!!!

14 Huffmn Coing y Exmpl 初始化 : 为每个字符创建一个集合字母码字概率集合集合的概率

15 Huffmn Coing y Exmpl. 根据集合的概率对集合进行排序 ( 升序 ) 字母码字概率集合集合的概率

16 Huffmn Coing y Exmpl 2. 对最前面集合的字母的码字中插入前缀字母码字概率集合集合的概率

17 Huffmn Coing y Exmpl 3. 对第二个集合中字母的码字中插入前缀 0 字母码字概率集合集合的概率

18 Huffmn Coing y Exmpl 4. 合并最前面的两个集合字母字母码字码字概率概率集合集合集合的概率集合的概率字母字母码字码字概率概率集合集合集合的概率集合的概率

19 Huffmn Coing y Exmpl. 根据集合的概率对集合进行排序 ( 升序 ) 字母码字概率集合集合的概率

20 Huffmn Coing y Exmpl 字母字母码字码字概率概率集合集合集合的概率集合的概率字母字母码字码字概率概率集合集合集合的概率集合的概率对最前面集合的字母的码字中插入前缀

21 Huffmn Coing y Exmpl 字母字母码字码字概率概率集合集合集合的概率集合的概率字母字母码字码字概率概率集合集合集合的概率集合的概率对第二个集合中字母的码字中插入前缀 0

22 Huffmn Coing y Exmpl 4. 合并前两个集合字母字母码字码字概率概率集合集合集合的概率集合的概率字母字母码字码字概率概率集合集合集合的概率集合的概率

23 Huffmn Coing y Exmpl. 根据集合的概率对集合进行排序 ( 升序 ) 字母码字概率集合集合的概率

24 Huffmn Coing y Exmpl 字母字母码字码字概率概率集合集合集合的概率集合的概率字母字母码字码字概率概率集合集合集合的概率集合的概率对最前面集合的字母的码字中插入前缀

25 Huffmn Coing y Exmpl 字母字母码字码字概率概率集合集合集合的概率集合的概率字母字母码字码字概率概率集合集合集合的概率集合的概率对第二个集合中字母的码字中插入前缀 0

26 Huffmn Coing y Exmpl 字母字母码字码字概率概率集合集合集合的概率集合的概率合并前两个集合字母字母码字码字概率概率集合集合集合的概率集合的概率

27 Huffmn Coing y Exmpl. 根据集合的概率对集合进行排序 ( 升序 ) 字母码字概率集合集合的概率

28 Huffmn Coing y Exmpl 字母字母码字码字概率概率集合集合集合的概率集合的概率字母字母码字码字概率概率集合集合集合的概率集合的概率对最前面集合的字母的码字中插入前缀

29 Huffmn Coing y Exmpl 字母字母码字码字概率概率集合集合集合的概率集合的概率字母字母码字码字概率概率集合集合集合的概率集合的概率对第二个集合中字母的码字中插入前缀 0

30 Huffmn Coing y Exmpl 字母字母码字码字概率概率集合集合集合的概率集合的概率合并前两个集合字母字母码字码字概率概率集合集合集合的概率集合的概率 Th END

31 例 : 总结平均码长熵 l = x + x2 + x3 + 0.x4 + 0.x4 = 2.2 its/symol H = Σ s=.. P(s) log 2 P(s) = 2.22 its/symol 冗余 l - H = its/symol

32 Huffmn 树 0 字母码字

33 构建 Huffmn 树字母码字

34 构建 Huffmn 树 (2) 字母码字

35 构建 Huffmn 树 (3) 字母码字

36 构建 Huffmn 树 (4) 0.0 字母码字

37 另一棵 Huffmn 树字母码字

38 另一棵 Huffmn 树 (2) 字母码字

39 另一棵 Huffmn 树 (3) 字母码字

40 另一棵 Huffmn 树 (4) 0 字母码字平均码长 l = x + ( )x3= 2.2 its/symol

41 再一棵 Huffmn 树字母码字平均码长 l = x2+ ( + )x2 + ( )x3= 2.2 its/symol

42 最小方差 Huffmn 树 Huffmn 编码不惟一但所有编码的平均码长相同我们应该选择哪一个呢? 答案 : 方差最小者为佳 ( 码字长度方差最小 ) 即高度最小的树为什么? 编码流中的编码变化最小怎样达到? 在排序时, 将较小的集合 ( 元素数目少 ) 尽可能放在上面也可以将新合并的集合尽可能放在下面 ( 即认为它们的码长应该更短一些 )

43 最小方差 Huffmn 树 (2) 2 码字长度的方差 σ : 长度 li 与平均码长 l之差的平方的数学期望, 即 2 σ 2 m 2 i i i i= ( l l) P( x )( l l) = E = 编码一码字长度方差 : σ = ( 2.2) + (2 2.2) + (3 2.2) + (0.+ 0.)(4 2.2) =

44 最小方差 Huffmn 树 (2) 编码二码字长度方差 : σ 2 = ( 2.2) + ( )(3 2.2) = 编码三码字长度方差 : σ 3 = ( + + )(2 2.2) + (0.+ 0.)(3 2.2) = 采用第三种编码方法 : 码长变化较小 ( 比较接近于平均码长 ) 第一种方法编出的 5 个码字有 4 种不同的码长 ; 0 第三种方法编出的码长只有两种不同的码长 ; 显然, 第三种编码方法更简单更容易实现 0. 0.

45 最小方差 Huffmn 树 (3) 由于码位要以固定的速率传输, 所以编码器要用缓冲器平滑比特产生率的变化码字的方差越大, 码位进入缓冲器的速率越不稳定, 因而编码器需要的缓冲器也越大 0 例 : 假设传输字符的速率固定, 如 0,000 字符 / 秒, 平均码长为 2.2 its/ 字符, 则接收方每秒将平均收到 22,000 比特几秒内一直产生包含 4,5 的字符串采用第一种编码方式, 这样产生的比特率为 40,000 比特 / 秒, 缓冲区每秒需保存 8,000 比特采用第三种编码方式, 比特率为 30,000 比特 / 秒, 缓冲区每秒需保存 8,000 比特几秒内一直产生包含的字符串采用第一种编码方式, 这样产生的比特率为 0,000 比特 / 秒, 传输带宽浪费 2,000 比特 / 秒采用第三种编码方式, 比特率为 20,000 比特 / 秒, 传输带宽浪费 2000 比特 / 秒 0 方差大的代码将导致编码器的输出码率不断变化

46 自适应 Huffmn 编码 Huffmn 编码需要各符号的概率概率来源 : 静态概率模型 : 根据训练数据得到, 然后不同信源利用同一个概率表无需传送 Huffmn 码表 / 码树 H.263 视频编码器半自适应统计模型 : 必须传送 Huffmn 码表和压缩流需 2 遍扫描但在很多情况下不实用 : 如压缩网络传输自适应 / 动态概率模型 : 遍扫描开始时认为是等概率根据前 k (k =, 2, ) 个符号统计重新产生码字并编码第 k+ st 个字符 Unix 系统对程序的压缩 : 基于单词的自适应 Huffmn 编码

47 Huffmn 解码在开始压缩之前, 编码器必须根据符号的概率 ( 或出现的频率 ) 确定码字解码器利用这些信息对压缩流进行解码, 所以应该将这些信息也写入压缩流中, 以便解码器能解码该压缩流变长码 : 不好, 因为码长不同写入频率 / 概率 : 将频率 / 概率标定为整数, 然后解码器利用该频率信息构造 Huffmn 树通常只会在压缩流中增加几百字节写入 Huffmn 树 : 比只写频率花费的字节数更多

48 Huffmn 解码一. 比特串行解码 ( 固定输入比特率可变输出符号率 ( 假定二进制码树在解码器端可得 ). 逐个比特读入输入压缩流, 并遍历树, 直到到达一个叶节点 2. 输入流的每个比特用过后即丢弃当到达叶节点时,Huffmn 解码器输出叶节点处的符号即完成该符号的解码 3. 重复步骤和 2, 直到所有的输入都解完由于所有码字长度不同, 解码比特率对所有符号并不相同

49 Huffmn 解码二. 基于查找表的解码 : 对所有符号解码率恒定在解码端从符号码字映射表中构建查找表如果表中的最长码字为 l 比特, 则需要一个 2 l 个入口的查找表空间限制 : 图象 / 视频最长的 l=6~20. 构造查找表 : x w 设 i对应的码字为 i, 假定有比特构造一个 l 比特地址, 前 l i 个比特是 w i, 后 l l i 个比特取任意 0 和的组合所以, 对符号 x l i 有 2 l i 个地址在每个入口形成 ( x, l ) i i w i l i

50 Huffmn 解码 2. 解码步骤 : 从压缩输入比特流中, 读 l 个比特到缓冲区中 ; 将缓冲区中的 l 比特字作为查找表中的地址, 得到对应的符号令码字长度为, 即解码一个符号 x k l k 移出缓冲区中的前个比特, 再移入若干比特, 使得缓冲区重新为 l 个比特重复步骤 2 和 3, 直到所有的符号都解码 l k

51 规范 Huffmn 编码并非只有使用二叉树建立的前缀编码才是 Huffmn 编码, 只要符合 () 是前缀编码 (2) 某一字符编码长度和使用二叉树建立的该字符的编码长度相同这两个条件的编码都可以叫做 Huffmn 编码规范 (Cnonil): 简单快速

52 规范 Huffmn 编码编码步骤 : 统计每个符号的频率根据这些频率信息求出该符号所需的位数 / 编码长度关心的仅仅是该符号在树中的深度, 完全没有必要构造二叉树, 仅用一个数组就可以模拟二叉树的创建过程并得到符号的深度 ( 详见数据压缩原理与应用节 ) 统计从最大编码长度到的每个长度对应多少个符号, 然后为每个符号递增分配编码编码输出压缩信息

53 规范 Huffmn 编码例 : 一组 6 个字符 3 比特 :4 个字符 ;5 比特 :5 个字符 ;6 比特 :7 个字符 (): 规范 Huffmn 编码可能码长 : 每个码长的码字 : 每组的第一个码字 :

54 规范 Huffmn 编码例 :( 续 ) 3 比特 :4 个字符 ;5 比特 :5 个字符 ;6 比特 :7 个字符 () 为规范 Huffmn 编码可能码长 : 每个码长的码字 : 每组的第一个码字 : 保证所有长于 l 位的码字的前 l 位前缀小于 first[l], 满足前缀码的要求

55 规范 Huffmn 编码对大字母表且必须快速解码时, 规范 Huffmn 编码特别有用解码器很容易逐个读入和检测输入位来识别码长知道码长, 即可进一步解码读出符号解码规则 : 所有长于 l 位的码字的前 l 位前缀小于 first[l] 例 : 输入 :000 v:0,00=0,00=,00=3;000=6 l:, 2, 3, 4, 5 first[l]: 2, 4, 3, 5, 4 码长为 l=5, v-first[5] = 6-4=2, 即符号为码长为 5 的 3 个字符 ( 编号从 0 开始 )

56 规范 Huffmn 编码码长的确定 : 用最小堆实现满二叉树 : 除叶子节点外的所有节点都有两个分支的二叉树平衡二叉树 : 底部有些节点缺少右分支的满二叉树堆 (hp): 为平衡二叉树, 且树中每个叶子都包含一个有序数据, 使得从叶子到根的每条路径都已排序最小堆 : 非增序的堆堆筛选 : 将堆底部最右边节点的值作为新的树根保证筛选后的数仍是一课平衡二叉树, 然后对堆排序, 使得其为最小堆

57 规范 Huffmn 编码平衡 : 不用额外的指针就可将其保存在数组中数组第 i 节点的两个分支分别置于第 2i 和第 2i+ 位置数组第 j 个节点的父亲节点第 j 2 位置码长的确定 : 用一个长度为 2m 的数组 A, 其中 m 为信源符号的数目将 m 个符号出现的频率放在数组的高半段 A[m+] 到 A [2m] 中将最小堆放在 A [] 到 A [m] 中, 堆中的数据项则指向数组高半段频率的指针然后算法进入循环, 在每次迭代中, 用堆来找出两个频率最小的数据项, 并用其和来替代它们 ; 将和保存在前一个堆的位置 A [h] 中, 这样堆就可以收缩一个位置重复循环, 直到堆中只剩下一个指针

58 规范 Huffmn 编码可以不依赖任何树结构进行高速解压缩而且在整个压缩解压缩过程中需要的空间比传统 Huffmn 编码少得多

59 Huffmn 编码的局限性当符号集较大且概率分布不是很悬殊时,Huffmn 的平均码长可接近于熵对于概率分布悬殊的消息集合, 上限可能很大, 意味着编码冗余度较大一个极端的例子 : 黑白传真 X : x x 2 PX ( ) : H X = 0.99 log log 0.0 = it/ pl ( ) ( ) { } 采用 Huffmn 编码, 得到 W = 0,, 都需要 l= 位, 没起到压缩的作用编码效率仅为 ( ) l 8% η = H X = 这是因为 Huffmn 编码只能为每个信源符号分配整数个比特, 只有当每个符号的概率是 2 的负整数倍时, 才能达到熵值

60 Huffmn 编码的局限性 Huffmn 编码的平均码长满足平均码长界定定理 : 对 Huffmn 编码, 更紧致的上界 : p mx H( X) l < H( X) + 令表示最大概率, 若 pmx 0.5, 则平均码长满足 : l < H( X) + p mx 若 p <, 则平均码长满足 : mx 0.5 l < H( X) + p mx 所以最大概率比较大 ( 概率不均衡 ) 时, 上界离熵值相差较大, 编码效率不高

61 扩展 Huffmn 编码考虑信源 : A = {,, }, P() = 0.8, P() = 0.02, P() = 0.8 H = 0.86 its/symol Huffmn 编码 : 0 0 l =.2 its/symol 冗余 = /sym (47%!) Q: 能做得更好吗?

62 扩展 Huffmn 编码 (2) 思想考虑对两个字母序列编码, 而不是单个字母合并信源符号 ( 联合熵 ) 字母概率码字 l =.7228/2 = 冗余 = 比特 / 字符

63 扩展 Huffmn 编码 (3) 该思想还可以扩展考虑所有 m k 的序列设码符号集 A =, 2,..., m K 信源符号的 k 次扩展 : X = x, x2,..., xn K W W = { w, w2,..., wn}, 其平均长度为 k 如果要求 W 为唯一可译码, 则 kh ( X ) kh ( X ) + > lk log m log m 每个信源符号的平均码长 { } X { } l = l k 当 k 足够大时, 平均码长 l 可以无限接近下界值, 从而在一定程度上提高了编码的有效性 l k H( X) lk H( X) + > log m k k log m k

64 扩展 Huffmn 编码 (4) 理论上, 通过考虑更多序列可以改进编码实践中, 字母表随序列长度指数增长使得它不现实如, 对长度为 3 的 ASCII 序列 :256 3 = 2 24 = 6M 大多数序列的频率为 0 需要其他方法

65 例 : 离散无记忆信源 X: x x2 P(X): 0.8 则 : H(X) = - log -0.8 log 0.8 =0.729 比特 / 信符用二进制符号集 A:{0,} 进行无失真信源编码 : x w=0; x2 w2=; H( X) l = =, η = = l

66 例 : 对其二次扩展信源进行编码 : X 2 p(wi) wi xx / xx2 4/25 00 x2x 4/25 0 x2x2 6/25 37 l2 37 l2 = 码符 /2 信符, l = = 码符 / 信符 H( X) η = = = 0.97 l 37 / 50

67 Huffmn 编码的应用在实际应用中, Huffmn 编码通常与其他编码技术一起使用例 : 无损图像压缩 Gry imgs (0~255), Img siz: 256*256 Sn Snsin Erth Omh

68 在图像压缩中的应用 Img Nm 直接对像素用 Huffmn 编码进行压缩 Bits/Pxl Totl Siz (yts) 压缩率不是很高, 平均每个像素约减少比特更实用的技术 : 与预测模型一起使用 Comprssion Rtio Sn , Snsin , Erth , Omh

69 在图像压缩中的应用 Img Nm 对像素差分用 Huffmn 编码进行压缩 Bits/Pxl Totl Siz (yts) Comprssion Rtio Sn , Snsin ,54.70 Erth , Omh 利用预测模型 xˆn = x n, 然后对预测残差, 即像素差分进行编码, 带来压缩率的提高

70 在文本压缩中的应用文本压缩比较适合 Huffmn 编码字母表是离散的, 而且概率模型基本稳定教材节中 Tl 3.26 和 Tl 3.27 中不同文本的字母概率很相似用 Huffmn 编码对教材第三章进行编码, 文件大小从 70,000 字节下降到 43,000 个字节可以利用其他技术进一步去除文本中的相关性 ( 教材第五章和第六章 )

71 在音频压缩中的应用 CD 质量的音频 : 采样频率 :44.kHz; 每个样本 6 比特数据量巨大对 6 比特的 CD 质量音频用 Huffmn 编码进行压缩 Fil Nm Originl Fil Siz (Byts) Mozrt 939,862 Entropy (its) Estimt Comprssion Fil Siz (yts) Comprssion Rtio , Cohn 402, ,300.5 Mir ,540.6

72 在音频压缩中的应用对 6 比特的 CD 质量音频差分用 Huffmn 编码进行压缩 Fil Nm Originl Fil Siz (Byts) Mozrt 939,862 Entropy (its) Estimt Comprssion Fil Siz (yts) Comprssion Rtio , Cohn 402,442 26, Mir , 利用预测模型 xˆn = x n, 然后对预测残差, 即像素差分进行编码, 带来压缩率的提高

73 小结最早的 Shnnon Fno 编码 Huffmn 编码考虑了信源的统计特性 : 经常出现的信源符号对应较短的码字编码方法不惟一, 码长方差较小的编码更好对信源的统计特性没有特殊要求, 编码效率比较高, 对编码设备的要求也比较简单其他 Huffmn Optimlity of Huffmn Cos /3.2.2/ Non-inry Huffmn Cos /3.3/ 相关编码 Golom /3.5/ Ri /3.6/ Tunstll /3.7/

74 下节课内容 : 作业 : 第三章 () 不做算术编码 / 自适应算术编码

第一章：概率统计基础

第一章：概率统计基础本节课内容 QM 编码器 Golomb 编码 QM 编码器二进制信源算术编码只处理二进制信源符号设计目标 : 简单快速对乘法操作进行近似定点精度的整数算术编码不断标定概率区间, 使得近似结果接近于真正的乘法在现代图像和视频压缩算法中广泛应用 :JBIG, JPEG, JPEG2000, H.263, H.264 QM 编码器很多二值图像都存在局部结构在某个部分, 大部分向素值为