第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所