LZW-编码详解ppt课件.ppt

LZW编码 1 行程编码适合于对二值图像的编码 如果图像是由很多块颜色或灰度相同的大面积区域组成的 采用行程编码可以达到很大的压缩比 通常 为了达到比较好的压缩效果 一般不单独使用行程编码 而是和其他编码方法结合使用 如 在JPEG中 就综合使用了行程编码以及哈夫曼编码 2 1977年 以色列人Lempel和Ziv共同提出了查找冗余字符 和用较短的符号标记替代冗余字符的概念 简称LZ压缩技术 1985年 美国人Welch将LZ压缩技术从概念发展到实用阶段 简称LZW压缩技术 广泛用于图象压缩领域 LZW Lempel Ziv Welch 编码又称字串表编码 属于一种无损编码 LZW编码与行程编码类似 也是对字符串进行编码从而实现压缩 但它在编码的同时还生成了特定字符串以及与之对应的索引字符串表 LZW编码 3 压缩的数据并与一个字典库 库开始是空的 中 字符串插入字典中 字符串数据在字典库中的位置索引 的字符串对比 LZW压缩使用字典库查找方案 它读入待 如有匹配的字符串 则输出该 否则将该 4 步骤1 将词典初始化为包含所有可能的单字 步骤2 当前字符C 字符流中的下一个字符 字符 当前前缀P初始化为空 LZW编码算法 5 令P C 现在的P仅包含一个字符C 步骤3 判断P C是否在词典中 1 如果 是 则用C扩展P 即让P P C 2 如果 否 则 输出与当前前缀P相对应的码字 将P C添加到词典中 6 步骤4 判断码字流中是否还有码字要译 1 如果 是 就返回到步骤2 2 如果 否 把代表当前前缀P的码字输出到码字流 结束 7 LZW编码举例 输入数据流 编码过程 8 初始化字符串表 LZW编码实例aabcabbbbd 9 输入数据S2 S1 S2 输出结果 S1 生成的新字符串及索引 NULL a a b c a b b b b d NULL NULL a a a aa 4H 0H 0H ab bc ca ab abb bb bb bbd 1H 2H 7H 1H BH 3H 5H b c a ab b b bb d aa ab bc ca abb bb bbd S1为NULL 故输出结果为空 S1 S2在字符表中 S1 S1 S2 aa不存在 故输出S1 a 的索引0H S1 S2不在字符表中 S1 S2 a ab不存在 故输出S1 a 的索引0H S1 S2不在字符表中 S1 S2 b S1 S2结果已存在 故输出结果为空 S1 S2在字符表中 S1 S1 S2 此时已无输入 输出S1的索引3H 输出LZW EOI标志的索引 10 LZW编码步骤 设来源于二色系统的图像数据源 aabbbaabb 1 根据图像中使用的颜色数初始化一个字符串表 字符串表中的每个颜色对应一个索引 在初始字符串表的LZW CLEAR和LZW EOI分别为字符表初始化标志和编码结束标志 11 LZW编码步骤 2 输出LZW CLEAR在字串表中的索引2H 12 LZW编码步骤 3 从图像数据流中第一个字符开始 读取一个字符a 将其赋给字符串变量S2 判断S1 S2 a 在字符串表中 则S1 S1 S2 a 13 LZW编码步骤 4 读下一个字符a 将其赋给S2 判断S1 S2 aa 不在字符串表中 输出S1 a 在字串表中的索引0H 并在字符串表末尾为S1 S2 aa 添加索引4H 且S1 S2 a 14 LZW编码步骤 5 读下一个字符b赋给S2 判断S1 S2 ab 不在字符串表中 输出S1 a 在字串表中的索引0H 并在字符串表末尾为S1 S2 ab 添加索引5H 且S1 S2 b 15 LZW编码步骤 6 读下一个字符b赋给S2 S1 S2 bb 不在字符串表中 输出S1 b 在字串表中的索引1H 并在字符串表末尾为S1 S2 bb 添加索引6H 且S1 S2 b 16 LZW编码步骤 7 读字符b赋给S2 S1 S2 bb 在字符串表中 则S1 S1 S2 bb 17 LZW编码步骤 8 读字符a赋给S2 S1 S2 bba 不在字符串表中 输出S1 bb 在字串表中的索引6H 并在字符串表末尾为S1 S2 bba 添加索引7H 且S1 S2 a 18 LZW编码步骤 9 读字符a赋给S2 S1 S2 aa 在字符串表中 则S1 S1 S2 aa 19 LZW编码步骤 10 读字符b赋给S2 S1 S2 aab 不在字符串表中 输出S1 aa 在字串表中的索引4H 并在字符串表末尾为S1 S2 aab 添加索引8H 且S1 S2 b 20 LZW编码步骤 11 读字符b赋给S2 S1 S2 bb 在字符串表中 则S1 S1 S2 b 21 LZW编码步骤 12 输出S1中的字符串 b 在字串表中的索引1H 22 LZW编码步骤 13 输出结束标志LZW EOI的索引3H 编码完毕 23 解码步骤 1 读第一个编码code 2H 无输出2 读code 0H 输出0H对应的a oldcode code 0H3 code 0H 输出0H对应的a 然后将oldcode 0H所对应的字符串 a 加上code 0H对应的字符串的第一个字符 a 即 aa 添加到字典中 其索引为4H 同时oldcode code 0H 24 4 读入code 1H 输出 b 然后将oldcode 0H所对应的字符串 a 加上code 1H对应的字符串的第一个字符 b 即 ab 添加到字典中 其索引为5H 同时oldcode code 1H5 读入code 6H 由于字典中不存在该索引 将oldcode 1H所对应的字符串 b 加上oldcode 1H对应的字符串的第一个字符 b 即 bb 添加到字典中 其索引为6H 同时oldcode code 6H 25 6 读入code 4H 输出 aa 然后将oldcode 6H所对应的字符串 bb 加上code 4H对应的字符串的第一个字符 a 即 bba 添加到字典中 其索引为7H 同时oldcode code 4H7 读入code 6H 输出 bb 然后将oldcode 4H所对应的字符串 aa 加上code 6H对应的字符串的第一个字符 b 即 aab 添加到字典中 其索引为8H 同时oldcode code 6H8 读入code 3H 解码完毕 26 解码过程 27 由于LZW算法的关键是通过翻译表来实 对LZW算法的分析 增加表中长串的数量 则压缩比也就越高 即串越长 输出越少 串 然后对其进行编码 现压缩的 而且每次找出的串是在表中最长的 因此 如果我们设法 28 串表中的每一个串均具有前缀特性 即 则字的前缀K一定在串表中 称之为前缀条件 如果Kx K为一个串 x为一个字符 在串表中 29 算术编码 是一种从整个符号序列出发 采用递推形式连续编码的方法 与建立在符号和码字对应基础上的块码不同 在算术编码中 源符号和码字间的一一对应关系并不存在 1个算术码字要赋给整个信源符号码字 而每个码字本身确定了0和1之间的1个实数区间 30 算术编码具体方法是将被编码的信源消息表示成实数轴0 1之间的一个间隔 消息越长 编码表示的间隔就越小 即这一间隔所 采用算术编码每个符号的平均编码长度可以为小数 需的二进制位数就越多 算术编码 31 待编码的数据序列为 dacab 信源中各符号出现的概率依次为P a 0 4 P b 0 2 P c 0 2 P d 0 2 数据序列中的各数据符号在区间 0 1 内的间隔 赋值范围 设定为 a 0 0 4 b 0 4 0 6 c 0 6 0 8 d 0 8 1 0 32 a 0 0 4 b 0 4 0 6 c 0 6 0 8 d 0 8 1 0 输入d 其初始间隔为 0 8 1 0 输入a 其初始间隔为 0 0 4 StartN 0 8 0 1 0 0 8 0 8 a 的实际编码区间在 0 8 0 88 之间 a 的取值范围应在前一符号间隔 0 8 1 0 的 0 0 4 子区间内 EndN 0 8 0 4 1 0 0 8 0 88 33 a 0 0 4 b 0 4 0 6 c 0 6 0 8 d 0 8 1 0 输入c 其初始间隔为 0 6 0 8 StartN 0 8 0 6 0 88 0 8 0 848 c 的取值范围应在前一符号间隔 0 8 0 88 的 0 6 0 8 子区间内 EndN 0 8 0 8 0 88 0 8 0 864 c 的实际编码区间在 0 848 0 864 之间 34 a 0 0 4 b 0 4 0 6 c 0 6 0 8 d 0 8 1 0 输入a 其初始间隔为 0 0 4 StartN 0 848 0 0 864 0 848 0 848 a 取值范围应在前一符号间隔 0 848 0 864 的 0 0 4 子区间内 EndN 0 848 0 4 0 864 0 848 0 8544 a 的实际编码区间在 0 848 0 8544 之间 35 a 0 0 4 b 0 4 0 6 c 0 6 0 8 d 0 8 1 0 输入b 其初始间隔为 0 4 0 6 StartN 0 848 0 4 0 8544 0 848 0 85056 b 取值范围应在前一符号间隔 0 848 0 8544 的 0 4 0 6 子区间内 EndN 0 848 0 6 0 8544 0 848 0 85184 b 的实际编码区间在 0 85056 0 85184 之间 36 设待编码的数据序列为 dacab 信源中各符号出现的概率依次为P a 0 4 P b 0 2 P c 0 2 P d 0 2 数据序列中的各数据符号在区间 0 1 内的间隔 赋值范围 设定为a 0 0 4 b 0 4 0 6 c 0 6 0 8 d 0 8 1 0 新间隔的起始位置和结束位置 表示前一间隔的起始位置 前一间隔的长度 当前编码符号的初始区间的左端和右端 37 第一个被压缩的符号为 d 其初始间隔为 0 8 1 0 第二个被压缩的符号为 a 由于前面的符号 d 的取值区间被限制在 0 8 1 0 范围内 所以 a 的取值范围应在前一符号间隔 0 8 1 0 的 0 0 4 子区间内 根据上式可知 StartN 0 8 0 1 0 0 8 0 8EndN 0 8 0 4 1 0 0 8 0 88 a 的实际编码区间在 0 8 0 88 之间 38 第三个被压缩的符号为 c 其编码取值范围应在 0 8 0 88 区间的 0 6 0 8 的子区间内 第四个被压缩的符号为 a StartN 0 848 0 0 864 0 848 0 848 EndN 0 848 0 4 0 864 0 848 0 8544 39 第五个被压缩的符号为 b StartN 0 848 0 4 0 8544 0 848 0 85056 EndN 0 848 0 6 0 8544 0 848 0 85184 数据序列 dacab 已被描述为一个实数区间 0 85056 0 85184 在此区间内的任一实数值都惟一对应该数据序列 这样 就可以用一个实数表示这一数据序列 把区间 0 85056 0 85184 用二进制形式表示为 0 110110011011 0 110110100001 40 0 110110011011 0 110110100001 0 1101101位于这个区间内并且其编码最短 故把其作为数据序列 dacab 的编码输出 不考虑 0 把1101101作为本例中的数据序列的算术编码 由此可见 数据序列 dacab 用7比特的二进制代码就可以表示 平均码长为1 4比特 字符 41 算术编码 对信源 baacc 进行算术编码 1 计算信源中各符号出现的概率P a 0 4 P b 0 2 P c 0 4 2 将数据序列中的各数据符号在区间 0 1 内的间隔 赋值范围 设定为a 0 0 4 b 0 4 0 6 c 0 6 1 0 42 算术编码 3 第一个被压缩的符号为 b 其初始间隔为 0 4 0 6 4 第二个被压缩的符号为 a 由于前面的符号 b 的取值区间被限制在 0 4 0 6 范围内 所以 a 的取值范围应在前一符号间