LZW-编码详解PPT课件

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