LZW 编码详解课件.ppt

; 行程编码适合于对二值图像的编码，如果 图像是由很多块颜色或灰度相同的大面积区域 组成的，采用行程编码可以达到很大的压缩比。 通常，为了达到比较好的压缩效果，一般 不单独使用行程编码，而是和其他编码方法结合 使用。如：在JPEG中，就综合使用了行程编码以及哈夫曼编码。;1977年,以色列人Lempel和Ziv共同提出了查找冗余字符;压缩的数据并与一个字典库(库开始是空的)中; 步骤1：将词典初始化为包含所有可能的单字;令P:=C，现在的P仅包含一个字符C;步骤4：判断码字流中是否还有码字要译;LZW编码举例;初始化字符串表 ;;LZW编码步骤;LZW编码步骤;LZW编码步骤;LZW编码步骤;LZW编码步骤;LZW编码步骤;LZW编码步骤;LZW编码步骤;LZW编码步骤;LZW编码步骤;LZW编码步骤;LZW编码步骤;LZW编码步骤;解码步骤;4)读入code=1H,输出“b”,然后将oldcode=0H所对应的字符串“a”加上code=1H对应的字符串的第一个字符”b”,即”ab”添加到字典中，其索引为5H，同时oldcode=code=1H 5)读入code=6H,由于字典中不存在该索引，将oldcode=1H所对应的字符串“b”加上oldcode=1H对应的字符串的第一个字符”b”,即”bb”添加到字典中，其索引为6H，同时oldcode=code=6H ;6)读入code=4H,输出“aa”,然后将oldcode=6H所对应的字符串“bb”加上code=4H对应的字符串的第一个字符”a”,即”bba”添加到字典中，其索引为7H，同时oldcode=code=4H 7)读入code=6H,输出“bb”,然后将oldcode=4H所对应的字符串“aa”加上code=6H对应的字符串的第一个字符”b”,即”aab”添加到字典中，其索引为8H，同时oldcode=code=6H 8)读入code=3H,解码完毕。;解码过程; ①由于LZW算法的关键是通过翻译表来实; ②串表中的每一个串均具有前缀特性，即：; 算 术 编 码 ; 算术编码具体方法是将被编码的信源消息表示成实数轴0-1之间的一个间隔，消息越长，编码表示的间隔就越小，即这一间隔所; 待编码的数据序列为“dacab”，信源中各符号出现的概率依次为P(a)=0.4，P(b)=0.2，P(c)=0.2， P(d)=0.2。;a=［0, 0.4）, b=［0.4, 0.6）, c=［0.6, 0.8）, d［0.8, 1.0）;a=［0, 0.4）, b=［0.4, 0.6）, c=［0.6, 0.8）, d［0.8, 1.0）;a=［0, 0.4）, b=［0.4, 0.6）, c=［0.6, 0.8）, d［0.8, 1.0）;a=［0, 0.4）, b=［0.4, 0.6）, c=［0.6, 0.8）, d［0.8, 1.0）; 设待编码的数据序列为“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） ; 第一个被压缩的符号为“d”，其初始间隔为［0.8, 1.0)； 第二个被压缩的符号为“a”，由于前面的符号“d”的取值区间被限制在［0.8, 1.0)范围内，所以“a”的取值范围应在前一符号间隔［0.8, 1.0)的［0, 0.4)子区间内， 根据上式可知 ; 第三个被压缩的符号为“c”， 其编码取值范围应在［0.8, 0.88)区间的［0.6, 0.8)的子区间内.; 第五个被压缩的符号为“b”;［0.110110011011, 0.110110100001］。 0.1101101位于这个区间内并且其编码最短， 故把其作为数据序列“dacab”的编码输出。不考虑“0.”，把1101101作为本例中的数据序列的算术编码。由此可见， 数据序列“dacab”用7比特的二进制代码就可以表示， 平均码长为1.4比特／字符。; 算 术 编 码 ; 算 术 编 码 ;算 术 编 码