4-图像压缩与编码2算术编码等

数据压缩可分成两种类型,一种叫做无损压缩,另一种叫做有损压缩。无损压缩是指使用压缩后的数据进行重构(或者叫做还原,解压缩),重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。一个很常见的例子是磁盘文件的压缩。根据目前的技术水平,无损压缩算法一般可以把普通文件的数据压缩到原来的1/2~1/4。一些常用的无损压缩算法有霍夫曼(Huffman)算法和LZW(Lem-pel-Ziv&Welch）算法。有损压缩是指使用压缩后的数据进行重构,重构后的数据与原来的数据有所不同,但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。例如,图像和声音的压缩就可以采用有损压缩,因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息,丢掉一些数据而不至于对声音或者图像所表达的意思产生误解,但可大大提高压缩比。2.2.6算术编码算术编码在图像数据压缩标准中扮演了重要的角色。在算术编码中，消息用0到1之间的实数进行编码。算术编码用到的两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。算术编码器的编码过程可用下面的例子加以解释。例：假设信源符号为{00，01，10，11}，这些符号的概率分别为{0.1，0.4，0.2，0.3}根据这些概率可把间隔[0，1]分成4个子间隔:[0,0.1),[0.l,0.5),[0.5,0.7),[0.7,1),其中[x,y)表示半开放间隔，即包含x不包含y。上面的信息可综合在表中信源符号,概率和初始编码间隔符号概率初始编码间隔000.1[0，0.1）010.4[0.1，0.5)100.2[0.5，0.7)110.3[0.7，1)如果二进制消息序列的输入为:10001100101101,编码时首先输入的符号是10,找到它的编码范围是[0.5,0.7]。由于消息中第二个符号00的编码范围是[0,0.1],因此它的间隔就取[0.5,0.7]的第一个十分之一作为新间隔[0.5,0.52]。依此类推,编码第3个符号11时取新间隔为[0.514,0.52],编码第4个符号00时,取新间隔为[0.514,0.5146],···。消息的编码输出可以是最后一个间隔中的任意数。整个编码过程如图所示。编码过程步骤输入符号编码间隔110[0.5，0.7）200[0.5，0.52）311[0.514，0.52）400[0.514，0.5146）510[0.5143，0.51442）611[0.514384，0.51442）701[0.5143836，0.514402）8从[0.5143876，0.514402）中选择一个数作为数出：0.5143876译码过程步骤间隔译码符号1[0.5，0.7）102[0.5，0.52）003[0.514，0.52）114[0.514，0.5146）005[0.5143，0.51442）106[0.514384，0.51442）117[0.51439，0.5143948）01译码的消息10001100101101根据上面所举的例子,可把计算过程总结如下：考虑一个有M个符号ai=(1,2,…,M)的字符表集,假设概率p(ai)=pi,,而Σpi(ai)=p1+p2+…+pM=1。输入符号用xn表示,第n个子间隔的范围用In=[ln,rn)=[ln-1+dn-1Σpi-1,ln-1+dn-1Σpi]表示。其中l0=0,d0=1和p0=0,ln表示间隔左边界的值,rn表示间隔右边界的值,dn=rn-ln表示间隔长度。编码步骤如下:(1)首先在1和0之间给每个符号分配一个初始子间隔,子间隔的长度等于它的概率,初始子间隔的范围用I1=[l1,r1]=[Σpi-1,Σpi]表示。令d1=r1-l1,L=l1和R=r1。(2)L和R的二进制表达式分别表示为:L=Σμk2-k和R=Συk2-k其中μk和υk等于“1”或者“0”。比较u1和v1，若不等，不发送任何数据，转到步骤3，若相等，就发送二进制符号u1比较u2和v2，若不等，不发送任何数据，转到步骤3，若相等，就发送二进制符号u2……这种比较一直进行到两个符号不相同为止，然后进入步骤(3)(3)n加1，读下一个符号。假设第n个输入符号为xn=ai,按照以前的步骤把这个间隔分成如下所示的子间隔：In=[In,rn)=[In-1+dn-1∑pi-1,In-1+dn-1∑pi)然后转到步骤2为了更好的理解这几步，我们再看一个例子：例假设有4个符号的信源，他们的概率如下所示:信源符号概率初始编码间隔a1p1=0.5[0,0.5)a2p2=0.25[0.5,0.75）a3p3=0.125[0.75,0.875)a4p4=0.125[0.875,1)输入续列为a2,a1,a3,a4……它的编码过程说明如下步骤输入符号编码间隔编码判决110[0.5,0.7]符号的间隔范围[0.5,0.7)200[0.5,0.52][0.5,0.7]间隔的第一个1/10311[0.514,0.52][0.5,0.52]间隔的最后三个1/10400[0.514,0.5146][0.514,0.52]间隔的第一个1/10510[0.5143,0.51442][0.514,0.5146]间隔的第五个1/10开始，二个1/10611[0.514384,0.51442][0.5143,0.51442]间隔的最后3个1/10701[0.5143836,0.514402][0.514384,0.51442]间隔的4个1/10，从第1个1/10开始8从[0.5143876,0.514402)中选择一个数作为输出：0.5143876步骤间隔译码符号译码判决1[0.5,0.7]100.51439在间隔[0.5,0.7)2[0.5,0.52]000.51439在间隔[0.5,0.7)的第1个1/103[0.514,0.52]110.51439在间隔[0.5,0.52)的第7个1/104[0.514,0.5146]000.51439在间隔[0.514,0.52)的第1个1/105[0.5143,0.51442]100.51439在间隔[0.514,0.5146)的第5个1/106[0.514384,0.51442]110.51439在间隔[0.5143,0.51442)的第7个1/107[0.51439,0.5143948]010.51439在间隔[0.51439,0.5143948]的第1个1/107译码的消息：10001100101101在算术编码中需要注意的几个问题:(1)由于实际的计算机的精度不可能无限长,运算中出现溢出是一个明显的问题,但多数机器都有16位、32位或者64位的精度,因此这个问题可使用比例缩放方法解决。(2)算术编码器对整个消息只产生一个码字，这个码字是在间隔[0,1]中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。(3)算术编码也是一种对错误很敏感的编码方法,如果有一位发生错误就会导致整个消息译错。算术编码可以是静态的或者自适应的。在静态算术编码中,信源符号的概率是固定的。在自适应算术编码中,信源符号的概率根据编码时符号出现的频繁程度动态地进行修改,在编码期间估算信源符号概率的过程叫做建模。需要开发动态算术编码的原因是因为事先知道精确的信源概率是很难的,而且是不切实际的。当压缩消息时,我们不能期待一个算术编码器获得最大的效率,所能做的最有效的方法是在编码过程中估算概率。因此动态建模就成为确定编码器压缩效率的关键。5.2.7RLE编码现实中有许多这样的图像,在一幅图像中具有许多颜色相同的图块。在这些图块中,许多行上都具有相同的颜色,或者在一行上有许多连续的像素都具有相同的颜色值。在这种情况下就不需要存储每一个像素的颜色值,而仅仅存储一个像素的颜色值,以及具有相同颜色的像素数目就可以,或者存储一个像素的颜色值，以及具有相同颜色值的行数。这种压缩编码称为行程编码，常用（runlengthencoding,RLE）表示，具有相同颜色并且是连续的像素数目。为了叙述方便,假定一幅灰度图像,第n行的像素值为：用RLE编码方法得到的代码为:80315084180。代码中用黑体表示的数字是行程长度,黑体字后面的数字代表像素的颜色值。例如,黑体字50代表有连续50个像素具有相同的颜色值,它的颜色值是8。000000001118888881111000000008个03个150个84个18个0对比RLE编码前后的代码数可以发现,在编码前要用73个代码表示这一行的数据,而编码后只要用11个代码表示代表原来的73个代码,压缩前后的数据量之比约为7：1,即压缩比为7：1。这说明RLE确实是一种压缩技术,而且这种编码技术相当直观,也非常经济。RLE所能获得的压缩比有多大,这主要是取决于图像本身的特点。如果图像中具有相同颜色的图像块越大，图像块数目越少，获得的压缩比就越高。反之，压缩比就越小。5.2.8字典编码有许多场合,开始时不知道要编码数据的统计特性,也不一定允许你事先知道它们的统计特性。因此,人们提出了许许多多的数据压缩方法,企图用来对这些数据进行压缩编码,在实际编码过程中以尽可能获得最大的压缩比。这些技术统称为通用编码技术。词典编码(dictionaryencoding)技术就是属于这一类,这种技术属于无损压缩技术。字典编码的思想字典编码的根据是数据本身包含有重复代码这个特性。例如文本文件和光栅图像就具有这种特性。字典编码可归纳为两类:第一类是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分。它的输出仅仅是指向早期出现过的字符串的“指针”。第二类算法的想法是企图从输入的数据中创建一个短语字典。它可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的短语时，编码器就输出这个短语的索引号，而不是短语本身。LZ77算法为了更好地说明LZ77算法的原理，首先介绍算法中用到的几个术语：(1)输入数据流(inputstream)：要被压缩的字符序列。(2)字符(character)：输入数据流中的基本单元。(3)编码位置(codingposition)：输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符。(4)前向缓冲存储器(Lookaheadbuffer)：存放从编码位置到输入数据流结束的字符序列的存储器。(5)窗口(window)：指包含W个字符的窗口，字符是从编码位置开始向后数也就是最后处理的字符数。指针(pointer)：指向窗口中的匹配串且含长度的指针。LZ77算法LZ77编码算法的核心是查找从前向缓冲存储器开始的最长的匹配串。编码算法的具体执行步骤如下：(1)把编码位置设置到输入数据流的开始位置。(2)查找窗口中最长的匹配串。(3)以“(Pointer,Length)Characters”的格式输出，其中Pointer是指向窗口中匹配串的指针，Length表示匹配字符的长度，Characters是前向缓冲存储器中的不匹配的第1个字符。(4)如果前向缓冲存储器不是空的，则把编码位置和窗口向前移(Length+1)个字符，然后返回到步骤2。LZ77算法LZSS算法LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题,但这个解决方案包含有冗余信息。冗余信息表现在两个方面,一是空指针,二是编码器可能输出额外的字符,这种字符是指可能包含在下一个匹配串中的字符。LZSS算法以比较有效的方法解决这个问题,它的思想是如果匹配串的长度比指针本身的长度长就输出指针,否则就输出真实字符。由于输出的压缩数据流中包含有指针和字符本身,为了区分它们就需要有额外的标志位,即ID位。LZSS算法LZSS编码算法的具体执行步骤如下:(1)把编码位置置于输入数据流的开始位置。(2)在前向缓冲存储器中查找与窗口中最长的匹配串①Point