数据压缩实验指导书.doc

目 录实验一 用C/C+语言实现游程编码2实验二 用C/C+语言实现算术编码4实验三 用C/C+语言实现LZW编码10实验四 用C/C+语言实现2D-DCT变换13实验一 用C/C+语言实现游程编码1. 实验目的1) 通过实验进一步掌握游程编码的原理；2) 用C/C+语言实现游程编码。2. 实验要求给出数字字符，能正确输出编码。3. 实验内容现实中有许多这样的图像，在一幅图像中具有许多颜色相同的图块。在这些图块中，许多行上都具有相同的颜色，或者在一行上有许多连续的象素都具有相同的颜色值。在这种情况下就不需要存储每一个象素的颜色值，而仅仅存储一个象素的颜色值，以及具有相同颜色的象素数目就可以，或者存储一个象素的颜色值，以及具有相同颜色值的行数。这种压缩编码称为游程编码，常用(run length encoding，RLE)表示，具有相同颜色并且是连续的象素数目称为游程长度。为了叙述方便，假定一幅灰度图像，第n行的象素值为：用RLE编码方法得到的代码为：08138501408。代码中用黑体表示的数字是游程长度，黑体字后面的数字代表象素的颜色值。例如黑体字50代表有连续50个象素具有相同的颜色值，它的颜色值是8。对比RLE编码前后的代码数可以发现，在编码前要用73个代码表示这一行的数据，而编码后只要用11个代码表示代表原来的73个代码，压缩前后的数据量之比约为7:1，即压缩比为7:1。这说明RLE确实是一种压缩技术，而且这种编码技术相当直观，也非常经济。RLE所能获得的压缩比有多大，这主要是取决于图像本身的特点。如果图像中具有相同颜色的图像块越大，图像块数目越少，获得的压缩比就越高。反之，压缩比就越小。译码时按照与编码时采用的相同规则进行，还原后得到的数据与压缩前的数据完全相同。因此，RLE是无损压缩技术。RLE压缩编码尤其适用于计算机生成的图像，对减少图像文件的存储空间非常有效。然而，RLE对颜色丰富的自然图像就显得力不从心，在同一行上具有相同颜色的连续象素往往很少，而连续几行都具有相同颜色值的连续行数就更少。如果仍然使用RLE编码方法，不仅不能压缩图像数据，反而可能使原来的图像数据变得更大。请注意，这并不是说RLE编码方法不适用于自然图像的压缩，相反，在自然图像的压缩中还真少不了RLE，只不过是不能单纯使用RLE一种编码方法，需要和其他的压缩编码技术联合应用。4、思考题：如果是英文字符，应该从哪几方面去进行考虑？是否所有的字符都要RLE编码方法来进行编码？如何区分字符与重复因子？实验二 用C/C+语言实现算术编码1. 实验目的1) 通过实验进一步掌握算术编码的原理；2) 用C/C+语言实现算术编、解码。2. 实验要求1) 能正确进行码字刷新及区间刷新；2) 合理输出码字；3) 能正确解码。3. 实验内容过程1 假设信源符号为00, 01, 10, 11，这些符号的概率分别为 0.1, 0.4, 0.2, 0.3 ，根据这些概率可把间隔0, 1)分成4个子间隔：0, 0.1), 0.1, 0.5), 0.5, 0.7), 0.7, 1)，其中表示半开放间隔，即包含不包含。上面的信息可综合在表1中。表1 信源符号，概率和初始编码间隔符号00011011 概率0.10.40.20.3 初始编码间隔0, 0.1)0.1, 0.5)0.5, 0.7)0.7, 1) 如果二进制消息序列的输入为：10 00 11 00 10 11 01。编码时首先输入的符号是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)， 。消息的编码输出可以是最后一个间隔中的任意数。整个编码过程如图1所示。图1 算术编码过程举例这个例子的编码和译码的全过程分别表示在表4-05和表4-06中。根据上面所举的例子，可把计算过程总结如下。考虑一个有M个符号的字符表集，假设概率，而。输入符号用表示，第个子间隔的范围用表示。其中，和，表示间隔左边界的值, 表示间隔右边界的值，表示间隔长度。编码步骤如下：步骤1：首先在1和0之间给每个符号分配一个初始子间隔，子间隔的长度等于它的概率，初始子间隔的范围用，)表示。令，和。步骤2：L和R的二进制表达式分别表示为： 和其中和等于“1”或者“0”。比较和：如果，不发送任何数据，转到步骤3；如果，就发送二进制符号。比较和：如果，不发送任何数据，转到步骤3；如果，就发送二进制符号。这种比较一直进行到两个符号不相同为止，然后进入步骤3，步骤3：加1，读下一个符号。假设第个输入符号为，按照以前的步骤把这个间隔分成如下所示的子间隔：令，和，然后转到步骤2。表2 编码过程步骤 输入符号编码间隔 编码判决1100.5, 0.7)符号的间隔范围0.5, 0.7) 2000.5, 0.52)0.5, 0.7)间隔的第一个1/103110.514, 0.52)0.5, 0.52)间隔的最后一个1/104000.514, 0.5146)0.514, 0.52)间隔的第一个1/105100.5143, 0.51442)0.514, 0.5146)间隔的第五个1/10开始，二个1/106110.514384, 0.51442)0.5143, 0.51442)间隔的最后3个1/107010.5143836, 0.514402)0.514384, 0.51442)间隔的4个1/10，从第1个1/10开始8从0.5143876, 0.514402中选择一个数作为输出：0.5143876表3 译码过程步骤 间隔译码符号 译码判决 10.5, 0.7)100.51439在间隔 0.5, 0.7)20.5, 0.52)000.51439在间隔 0.5, 0.7)的第1个1/1030.514, 0.52)110.51439在间隔0.5, 0.52)的第7个1/1040.514, 0.5146)000.51439在间隔0.514, 0.52)的第1个1/1050.5143, 0.51442)100.51439在间隔0.514, 0.5146)的第5个1/1060.514384, 0.51442)110.51439在间隔0.5143, 0.51442)的第7个1/1070.51439, 0.5143948)010.51439在间隔0.51439, 0.5143948)的第1个1/107译码的消息：10 00 11 00 10 11 01过程2 假设有4个符号的信源，它们的概率如表4所示：表4 符号概率信源符号ai概率初始编码间隔0, 0.5)0.5, 0.75)0.75, 0.875)0.875, 1)输入序列为。它的编码过程，现说明如下。输入第1个符号是，可知，定义初始间隔，)0.5, 0.75)，由此可知，左右边界的二进制数分别表示为：L0.5=0.1(B)，R0.70.11 (B) 。按照步骤2，发送1。因，因此转到步骤3。输入第2个字符，它的子间隔， )0.5, 0.625)，由此可得=0.125。左右边界的二进制数分别表示为：L0.5=0.100 (B)，R0.101 (B)。按照步骤2，发送0，而和不相同，因此在发送0之后就转到步骤3。输入第3个字符，, 它的子间隔, )0.59375, 0.609375)，由此可得=0.015625。左右边界的二进制数分别表示为：0.59375=0.10011 (B)，0.609375=0.100111 (B)。按照步骤2，但和不相同，因此在发送011之后转到步骤3。发送的符号是：10011。被编码的最后的符号是结束符号。图2 算术编码概念就这个例子而言，算术编码器接受的第1位是“1”，它的间隔范围就限制在0.5, 1)，但在这个范围里有3种可能的码符, 和，因此第1位没有包含足够的译码信息。在接受第2位之后就变成“10”，它落在0.5, 0.75)的间隔里，由于这两位表示的符号都指向开始的间隔，因此就可断定第一个符号是。在接受每位信息之后的译码情况如下表5所示。表5 译码过程表接受的数字间隔译码输出10.5, 1)-00.5, 0.75)00.5, 0.609375)10.5625, 0.609375)-10.59375, 0.609375)在上面的例子中，我们假定编码器和译码器都知道消息的长度，因此译码器的译码过程不会无限制地运行下去。实际上在译码器中需要添加一个专门的终止符，当译码器看到终止符时就停止译码。在算术编码中需要注意的几个问题：1) 由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多数机器都有16位、32位或者64位的精度，因此这个问题可使用比例缩放方法解决。 2) 算术编码器对整个消息只产生一个码字，这个码字是在间隔0, 1)中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。 3) 算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。算术编码可以是静态的或者自适应的。在静态算术编码中，信源符号的概率是固定的。在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地进行修改，在编码期间估算信源符号概率的过程叫做建模。需要开开发态算术编码的原因是因为事先知道精确的信源概率是很难的，而且是不切实际的。当压缩消息时，我们不能期待一个算术编码器获得最大的效率，所能做的最有效的方法是在编码过程中估算概率。因此动态建模就成为确定编码器压缩效率的关键。实验三 用C/C+语言实现LZW编码1. 实验目的1) 通过实验进一步掌握LZW编码的原理；2) 用C/C+语言实现LZW编、解码。2. 实验要求给出字符，能正确输出编码，并能进行译码。3. 实验内容1) 编码过程LZW编码是围绕称为词典的转换表来完成的。这张转换表用来存放称为前缀(Prefix)的字符序列，并且为每个表项分配一个码字(Code word)，或者叫做序号，如表6所示。这张转换表实际上是把8位ASCII字符集进行扩充，增加的符号用来表示在文本或图像中出现的可变长度ASCII字符串。扩充后的代码可用9位、10位、11位、12位甚至更多的位来表示。Welch的论文中用了12位，12位可以有4096个不同的12位代码，这就是说，转换表有4096个表项，其中256个表项用来存放已定义的字符，剩下3840个表项用来存放前缀(Prefix)。表6 词典码字(Code word)前缀(Prefix)1193A194B2551305abcdefxyF01234LZW编码器(软件编码器或硬件编码器)就是通过管理这个词典完成输入与输出之间的转换。LZW编码器的输入是字符流(Charstream)，字符流可以是用8位ASCII字符组成的字符串，而输出是用n位(例如12位)表示的码字流(Codestream)，码字代表单个字符或多个字符组成的字符串。LZW编码器使用了一种很实用的分析(parsing)算法，称为贪婪分析算法(greedy parsing algorithm)。在贪婪分析算法中，每一次分析都要串行地检查来自字符流(Charstream)的字符串，从中分解出已经识别的最长的字符串，也就是已经在词典中出现的最长的前缀(Prefix)。用已知的前缀(Prefix)加上下一个输入字符C也就是当前字符(Current character)作为该前缀的扩展字符，形成新的扩展字符串缀-符串(String)：Prefix.C。这个新的缀-符串(String)是否要加到词典中，还要看词典中是否存有和它相同的缀-符串String。如果有，那么这个缀-符串(String)就变成前缀(Prefix)，继续输入新的字符，否则就把这个缀-符串(String)写到词典中生成一个新的前缀(Prefix)，并给一个代码。LZW编码算法的具体执行步骤如下：步骤1： 开始时的词典包含所有可能的根(Root)，而当前前缀P是空的；步骤2： 当前字符(C) ：=字符流中的下一个字符；步骤3： 判断缀-符串P+C是否在词典中(1) 如果“是”：P ：= P+C / (用C扩展P) ；(2) 如果“否” 把代表当前前缀P的码字输出到码字流; 把缀-符串P+C添加到词典; 令P ：= C /(现在的P仅包含一个字符C);步骤4： 判断码字流中是否还有码字要译(1) 如果“是”，就返回到步骤2；(2) 如果“否” 把代表当前前缀P的码字输出到码字流; 结束。译码过程LZW译码算法中还用到另外两个术语：当前码字(Current code word)：指当前正在处理的码字，用cW表示，用string.cW表示当前缀-符串；先前码字(Previous code word)：指先于当前码字的码字，用pW表示，用string.pW表示先前缀-符串。LZW译码算法开始时，译码词典与编码词典相同，它包含所有可能的前缀根(roots)。LZW算法在译码过程中会记住先前码字(pW)，从码字流中读当前码字(cW)之后输出当前缀-符串string.cW，然后把用string.cW的第一个字符扩展的先前缀-符串string.pW添加到词典中。LZW译码算法的具体执行步骤如下：步骤1： 在开始译码时词典包含所有可能的前缀根(Root)。步骤2： cW ：=码字流中的第一个码字。步骤3： 输出当前缀-符串string.cW到字符流。步骤4： 先前码字pW ：= 当前码字cW。步骤5： 当前码字cW ：= 码字流中的下一个码字。步骤6： 判断先前缀-符串string.cW是否在词典中(1) 如果“是”，则： 把先前缀-符串string.cW输出到字符流。 当前前缀P ：=先前缀-符串string.pW。 当前字符C ：=当前前缀-符串string.cW的第一个字符。 把缀-符串P+C添加到词典。(2) 如果“否”，则： 当前前缀P ：=先前缀-符串string.pW。 当前字符C ：=当前当缀P的第一个字符。 输出缀-符串P+C到字符流，然后把它添加到词典中。步骤7： 判断码字流中是否还有码字要译(1) 如果“是”，就返回到步骤4。(2) 如果“否”, 结束。过程 编码字符串如表7所示，编码过程如表8所示。现说明如下：“步骤”栏表示编码步骤； “位置”栏表示在输入数据中的当前位置； “词典”栏表示添加到词典中的缀-符串，它的索引在括号中； “输出”栏表示码字输出。表7 被编码的字符串位置123456789字符 ABBABABAC表8 LZW的编码过程步骤位置 词典输出(1)A(2)B(3)C11(4)A B(1)22(5)B B(2)33(6)B A(2)44(7)A B A(4)56(8)A B A C(7)6-(3)表9解释了译码过程。每个译码步骤译码器读一个码字，输出相应的缀-符串，并把它添加到词典中。例如，在步骤4中，先前码字(2)存储在先前码字(pW)中，当前码字(cW)是(4)，当前缀-符串string.cW是输出(“A B”)，先前缀-符串string.pW (B)是用当前缀-符串string.cW (A)的第一个字符，其结果(B A) 添加到词典中，它的索引号是(6)表9 LZW的译码过程步骤代码词典输出(1)A(2)B(3)C1(1)-A2 (2)(4)A BB3 (2)(5)B BB4 (4)(6)B AA B5 (7)(7)A B AA B A 6 (3)(8)A B A CC实验四 用C/C+语言实现2D-DCT变换1. 实验目的1) 通过实验进一步掌握2D-DCT变换的原理；2) 用C/C+语言实现2D-DCT变换，并能进行逆变换。2. 实验要求输入一个88数组，实现2D-DCT变换，并能进行逆变换。3. 实验内容DCT算法的实质是：压缩88图像块灰度样本数据流。原图像在输入到编码器之前