第4章无损数据压缩 初始编码间隔[0,0.5][0.5,0.75)[0.75,0.875)[0.875,1) 输入序列为xn:a2,a1,a3…。它的编码过程如图4-04所示,现说明如下。 输入第1个符号是x=a2,可知i=2,定义初始间隔l=,)=[∑P,∑P [0.5,0.75],由此可知d1=0.25,左右边界的二进制数分别表示为:L=0.5=0.1(B),R 0.75=0.11(B)。按照步骤2,1=V1,发送1。因a2≠v2’因此转到步骤3。 输入第2个字符x2=a1,=1,它的子间隔l2=[2)=+d∑p-1, 1+d∑P)=[0.5,0.625),由此可得d2=0.125。左右边界的二进制数分别表示为:L 0.5=0.100…(B),R=0.101…(B)。按照步骤2,l2=V2=0,发送0,而u3和v3不相 同,因此在发送0之后就转到步骤3 输入第3个字符,x3=a3,i=3,它的子间隔3=[2,n)=[l2+d2∑P1 l2+d2∑p,)=[0.59375,0.609375),由此可得d3=0.015625。左右边界的二进制数分别 表示为:L=0.59375=0.10011(B),R=0.609375=0.100111(B。按照步骤2, l4=V4=1,53=V5=1,但6和v不相同,因此在发送011之后转到步骤3。 发送的符号是:10011…。被编码的最后的符号是结束符号。 符号 a1 十进制0 05 075、08751.0 进制00 0.1 0110.11110 符号 2 1 十进制05 0625 0.68750.718750.75 进制01 0.101 0.l0ll0.101l10.11 符号 I a2“12“2a1 十进制0 0.56250.593750.6093750.625 进制0.1 0.1001 0.100110.1001110.101 图4-04算术编码概念 就这个例子而言,算术编码器接受的第1位是“1”,它的间隔范围就限制在[0.5,1) 但在这个范围里有3种可能的码符a2,a3和a4,因此第1位没有包含足够的译码信息。在 接受第2位之后就变成“10”,它落在[0.5,0.75)的间隔里,由于这两位表示的符号都指向 a2开始的间隔,因此就可断定第一个符号是a2。在接受每位信息之后的译码情况如下表 4-08所示
第4章 无损数据压缩 6 初始编码间隔 [0, 0.5] [0.5, 0.75) [0.75, 0.875) [0.875, 1) 输入序列为 xn : a2 ,a1 ,a3 , 。它的编码过程如图4-04所示，现说明如下。 输入第1个符号是 1 a2 x = ，可知 i = 2 ，定义初始间隔 I1 = [l 1 ,r1 ) = [ = − i i pi 1 1 ，= i i i p 1 ] ＝[0.5, 0.75]，由此可知 d1 = 0.25 ，左右边界的二进制数分别表示为：L＝0.5=0.1(B)，R ＝0.75＝0.11(B) 。按照步骤2， 1 1 u = v ，发送1。因 2 2 u v ，因此转到步骤3。 输入第 2 个字符 2 a1 x = ， i =1 ，它的子间隔 I 2 = [l 2 ,r2 ) = [l 1 + = − i i d pi 1 1 1 ， = + i i d pi l 1 1 1 )＝[0.5, 0.625)，由此可得 2 d =0.125。左右边界的二进制数分别表示为：L ＝0.5=0.100 … (B)，R＝0.101… (B)。按照步骤2，u2 = v2 = 0 ，发送0，而 3 u 和 3 v 不相 同，因此在发送0之后就转到步骤3。 输入第3个字符， 3 a3 x = ， i = 3 , 它的子间隔 I 3 = [I 3 ,r3 ) = [ = + − i i d pi l 1 2 2 1 , = + i i d pi l 1 2 2 )＝[0.59375, 0.609375)，由此可得 3 d =0.015625。左右边界的二进制数分别 表示为： L ＝0.59375=0.10011 (B)，R ＝0.609375=0.100111 (B)。按照步骤2，u3 = v3 = 0 ， u4 = v4 =1，u5 = v5 =1 ，但 6 u 和 6 v 不相同，因此在发送011之后转到步骤3。 … 发送的符号是：10011…。被编码的最后的符号是结束符号。 图4-04 算术编码概念 就这个例子而言，算术编码器接受的第1位是“1”，它的间隔范围就限制在[0.5, 1)， 但在这个范围里有3种可能的码符 a2 , 3 a 和 a4，因此第1位没有包含足够的译码信息。在 接受第2位之后就变成“10”，它落在[0.5, 0.75)的间隔里，由于这两位表示的符号都指向 a2 开始的间隔，因此就可断定第一个符号是 a2 。在接受每位信息之后的译码情况如下表 4-08所示
第4章无损数据压缩 表4-08译码过程表 接受的数字间隔 译码输出 [0.5,1) [0.5,0.75) [0.5,0.609375 [0.5625,0.609375) [0.59375,0.609375)a 在上面的例子中,我们假定编码器和译码器都知道消息的长度,因此译码器的译码过程 不会无限制地运行下去。实际上在译码器中需要添加一个专门的终止符,当译码器看到终止 符时就停止译码 在算术编码中需要注意的几个问题: (1)由于实际的计算机的精度不可能无限长,运算中出现溢出是一个明显的问题,但多 数机器都有16位、32位或者64位的精度,因此这个问题可使用比例缩放方法解决 (2)算术编码器对整个消息只产生一个码字,这个码字是在间隔[0,1)中的一个实数 因此译码器在接受到表示这个实数的所有位之前不能进行译码 (3)算术编码也是一种对错误很敏感的编码方法,如果有一位发生错误就会导致整个消 息译错。 算术编码可以是静态的或者自适应的。在静态算术编码中,信源符号的概率是固定的。 在自适应算术编码中,信源符号的概率根据编码时符号出现的频繁程度动态地进行修改,在 编码期间估算信源符号概率的过程叫做建模。需要开开发态算术编码的原因是因为事先知道 精确的信源概率是很难的,而且是不切实际的。当压缩消息时,我们不能期待一个算术编码 器获得最大的效率,所能做的最有效的方法是在编码过程中估算概率。因此动态建模就成为 确定编码器压缩效率的关键, 4.3RLE编码 现实中有许多这样的图像,在一幅图像中具有许多颜色相同的图块。在这些图块中,许 多行上都具有相同的颜色,或者在一行上有许多连续的像素都具有相同的颜色值。在这种情 况下就不需要存储每一个像素的颜色值,而仅仅存储一个像素的颜色值,以及具有相同颜色 的像素数目就可以,或者存储一个像素的颜色值,以及具有相同颜色值的行数。这种压缩编 码称为行程编码( run length encoding,RLE),具有相同颜色并且是连续的像素数目称为行 程长度。 为了叙述方便,假定有一幅灰度图像,第n行的像素值如图4-05所示: 00000000111888······888111100000000 } 8个03个150个 4个18 图4-05RLE编码的概念 用RLE编码方法得到的代码为:80315084180。代码中用黑体表示的数字是行程长度,黑 体字后面的数字代表像素的颜色值。例如黑体字50代表有连续50个像素具有相同的颜色值, 它的颜色值是8。 对比RLE编码前后的代码数可以发现,在编码前要用73个代码表示这一行的数据,而编 码后只要用11个代码表示代表原来的73个代码,压缩前后的数据量之比约为7:1,即压缩比 为7:1。这说明RLE确实是一种压缩技术,而且这种编码技术相当直观,也非常经济。RLE所
第4章 无损数据压缩 7 表4-08 译码过程表 接受的数字 间隔 译码输出 1 [0.5, 1) - 0 [0.5, 0.75) a2 0 [0.5, 0.609375) 1 a 1 [0.5625, 0.609375) - 1 [0.59375, 0.609375) 3 a … … … 在上面的例子中，我们假定编码器和译码器都知道消息的长度，因此译码器的译码过程 不会无限制地运行下去。实际上在译码器中需要添加一个专门的终止符，当译码器看到终止 符时就停止译码。 在算术编码中需要注意的几个问题： (1) 由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多 数机器都有16位、32位或者64位的精度，因此这个问题可使用比例缩放方法解决。 (2) 算术编码器对整个消息只产生一个码字，这个码字是在间隔[0, 1)中的一个实数， 因此译码器在接受到表示这个实数的所有位之前不能进行译码。 (3) 算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消 息译错。 算术编码可以是静态的或者自适应的。在静态算术编码中，信源符号的概率是固定的。 在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地进行修改，在 编码期间估算信源符号概率的过程叫做建模。需要开开发态算术编码的原因是因为事先知道 精确的信源概率是很难的，而且是不切实际的。当压缩消息时，我们不能期待一个算术编码 器获得最大的效率，所能做的最有效的方法是在编码过程中估算概率。因此动态建模就成为 确定编码器压缩效率的关键。 4.3 RLE编码 现实中有许多这样的图像，在一幅图像中具有许多颜色相同的图块。在这些图块中，许 多行上都具有相同的颜色，或者在一行上有许多连续的像素都具有相同的颜色值。在这种情 况下就不需要存储每一个像素的颜色值，而仅仅存储一个像素的颜色值，以及具有相同颜色 的像素数目就可以，或者存储一个像素的颜色值，以及具有相同颜色值的行数。这种压缩编 码称为行程编码(run length encoding，RLE)，具有相同颜色并且是连续的像素数目称为行 程长度。 为了叙述方便，假定有一幅灰度图像，第n行的像素值如图4-05所示： 00000000 111 888 • • • • • • 888 1111 00000000 8个0 3个1 50个8 4个1 8个0 图4-05 RLE编码的概念 用RLE编码方法得到的代码为：80315084180。代码中用黑体表示的数字是行程长度，黑 体字后面的数字代表像素的颜色值。例如黑体字50代表有连续50个像素具有相同的颜色值， 它的颜色值是8。 对比RLE编码前后的代码数可以发现，在编码前要用73个代码表示这一行的数据，而编 码后只要用11个代码表示代表原来的73个代码，压缩前后的数据量之比约为7:1，即压缩比 为7:1。这说明RLE确实是一种压缩技术，而且这种编码技术相当直观，也非常经济。RLE所