笫5章-数据压缩.

第五章 数据压缩数据压缩概述n由于多媒体数据量非常大，造成计算机的存储和网络传输负担若帧速率为25帧秒，则1s的数据量大约为25MB，一个640MB的光盘只能存放大约25s的动态图像一幅640480分辨率的24位真彩色图像的数据量约为900KB；一个100MB的硬盘只能存储约100幅静止图像画面n解决办法之一就是进行数据压缩数据压缩，压缩后再进行存储和传输，到需要时再解压、还原。以目前常用的位图格式的图像存储方式为例，像素与像素之间无论是在行方向还是在列方向都具有很大的相关性，因而整体上数据的冗余度冗余度很大，在允许一定限度失真的前提下，能够对图像数据进行很大程度的压缩。n数据压缩方法无损压缩：无损压缩：n利用数据的统计冗余进行压缩，可完全恢复原始数据利用数据的统计冗余进行压缩，可完全恢复原始数据而不引入任何失真，但压缩率受到统计冗余度理论限而不引入任何失真，但压缩率受到统计冗余度理论限制，一般为制，一般为2：1到到5：1。n多媒体应用中经常使用的无损压缩方法主要是基于统多媒体应用中经常使用的无损压缩方法主要是基于统计的编码方案，如游程编码计的编码方案，如游程编码(run length)、Huffman编编码、算术编码和码、算术编码和LZW编码等等。编码等等。n常用工具：常用工具：WinRar、WinZip、ARC等等 n数据压缩方法有损压缩：有损压缩：n利用了人类视觉和听觉器官对图像或声音中的某些利用了人类视觉和听觉器官对图像或声音中的某些频率成分不敏感的特性，允许在压缩过程中损失一频率成分不敏感的特性，允许在压缩过程中损失一定的信息；虽然不能完全恢复原始数据，但是所损定的信息；虽然不能完全恢复原始数据，但是所损失的部分对理解原始图像或声音的影响较小，却换失的部分对理解原始图像或声音的影响较小，却换来了大得多的压缩比。有损压缩广泛应用于语音、来了大得多的压缩比。有损压缩广泛应用于语音、图像和视频数据的压缩。图像和视频数据的压缩。n常用的有损压缩方法有：常用的有损压缩方法有：PCM(脉冲编码调制脉冲编码调制)、预测、预测编码、变换编码编码、变换编码(主要是离散余弦变换方法主要是离散余弦变换方法)、插值和、插值和外推法外推法(空域亚采样、时域亚采样、自适应空域亚采样、时域亚采样、自适应)等等。等等。n常用工具：常用工具：JPEG、MPEG等等 5.25.2 频率相关编码 在ASII文档中，各个字符出现的频率通常是不一样的，如经过大量的实验统计得知：英语中最常用的字母依次是e、t、o、a、n等。频率相关编码就是对需要传送的文档重新编码，使文档中的各个字符按照出现的频率分别对应不同长度的编码，达到文档代码长度最短的一种编码方法。5.2.1 5.2.1 哈夫曼编码哈夫曼编码 创建哈夫曼编码的步骤为：1）为每个字符指定一个只包含一个节点的二叉树，并以该字符的频率作为二叉树的权；2）选取两棵权最小的树合并成一棵带有新的根节点的树，其左右子树分别是选取的两棵树，新树的权为左右子树的权重之和；3）重复上面的步骤，直到只剩下最后一棵树；4）树中每个非叶节点的左指针分配“0”，右指针分配“1”，由此，从根出发可得各字符（叶节点）的哈夫曼编码。例如，假设某数据文件中各字符的频率如表8-1所示：字母 频率（）字母 频率（）A 25 B 15 C 10 D 20 E 30则构造哈夫曼树的过程如图8-1(a)8-1(e)所示。A B C D E 0.25 0.15 0.10 0.20 0.30图8-1(a)初始树 A B C D E 0.25 0.20 0.30图8-1(b)1次合并之后0.25表8-1 字母AE的频率 A B C E 0.25 0.30图8-1(c)2次合并之后D0.45图8-1(d)3次合并之后0.55D0.45 E A B C 根据哈夫曼树可得各字符的哈夫曼编码字符 编码 A 01 B 110 C 111 D 10 E 00图8-1(e)4次合并之后D1B C 0111000E A图8-1 合并哈夫曼树 哈夫曼编码是一种字符长度不固定的编码方法，它具有称为非前缀性质的特性，即任何字符的代码都不会与另一个代码的前缀相同。比如，A的哈夫曼编码是01，那么绝不会有别的代码以01开始。根据哈夫曼编码的这种特性，接收端按位拼接收到的比特位，当位串与某个编码对应时，即得到当前字符。如此重复，最终完成数据文档的接收还原。5.2.2 5.2.2 算术压缩算术压缩 算术压缩是一种采用一个0，1之间的实数来表示一个字符串的数据压缩方法。事实上，一个字符编码的0、1序列，可以理解为一个实数的二进制表示。算术压缩算法的过程是逐步产生长度递减的子区间，每一次所产生的子区间由当前字符以及它们的频率唯一确定。字符串中字符越多，对应的子区间越小。当处理完最后一个字符后，字符串与一个子区间对应，该子区间中任意一个实数（例如中点）表示相应的字符串。算术压缩算法的基本思想描述如下：1）按照各字符出现的频率将区间x，y=0，1 划分成若干子区间；2）查看当前字符，根据它的频率确定对应的子区间p，q；3）对区间x，y重新定义，缩小x，y。即：新x值现在x值wp 新y值现在x值wq 其中 w yx 表示区间x，y的宽度；4）查看下一字符，根据其频率再次决定x，y的正确子区间；5）对字符串中的每一字符重复第2步第4步。例如，假定字符串CABACADA中各字符的频率如表5-2所示：字符频率（）子区间p，qA250，0.25B150.25，0.4C100.4，0.5D200.5，0.7E300.7，1.0字符串CABA的压缩码计算过程如下：初始时x=0，y=1，w=10.40.5p=0.4q=0.5x=0y=1确定C的子区间确定A的子区间确定B的子区间x=x+wp=0+10.4=0.4y=x+wq=0+10.5=0.5x=x+wp=0.4+0.10=0.4y=x+wq=0.4+0.10.25=0.425确定A的子区间p=0q=0.25w=0.1p=0.25q=0.4w=0.025x=x+wp=0.4+0.0250.25=0.40625x=x+wp=0.4+0.0250.4=0.41w=0.00375p=0q=0.25字符串CABA算术编码的步骤 步骤12345字符串CCACABCABA下一字符CABAC目前区间x,y0,10.4,0.50.4,0.4250.40625,0.410.40625,0.4071875p，q0.4,0.50,0.250.25,0.40,0.250.4,0.5区间长度w=y-x1.00.10.0250.003750.0009375计算新xx=x+wp0+10.4=0.40.4+0.10=0.40.4+0.0250.25=0.406250.40625+0.003750=0.406250.40625+0.00093750.4=0.406625计算新yy=x+wq0+10.5=0.50.4+0.10.25=0.4250.4+0.0250.4=0.410.40625+0.003750.25=0.40718750.40625+0.00093750.5=0.4067187由上表可知，字符串“CABAC”落在区间0.406625，0.4067187中，换言之，该区间任一实数均可表示该字符串。现在的问题是：从一个已知的实数，如何对上述过程进行逆转，得到其对应的字符串？基本思路是，从首字符开始，依次判断各字符所在区间。例如，假设有实数N=0.4067，它落在0.4，0.5区间内，由此知，实数N对应的字符串的首字符必为C（任何其他字符只能落在该区间以外）。下一步确定第二个字符所在区间，为此用实数N减去p，然后除以区间长度w，即：（N-p）/w(0.4067-0.4)/0.1=0.067，该数落在区间0，0.25，表明实数0.067必然为A而不会是其他字符。同样的道理求出（0.067-0)/0.25=0.2680.25，0.4，可知第三个字符为B。依此类推，可以得到实数0.4067所表示的字符串。如表8-4所示。怎样确定解压的终止条件呢？算术压缩编码通常采用在原字符集中添加一个特殊的终结字符来解决，该字符与其他字符压缩和解压方法完全一样，仅作为解压过程的终止判断条件。思考题：假定有10个等概率字符，你能否提出更简单的算术编码实现方法？0.80.08C0.100.4,0.50.4850.480.12A0.250,0.250.1240.120.018B0.150.25,0.40.26830.2680.067A0.250,0.250.06720.0670.0067C0.100.4,0.50.40671(Np)/WNp字符长度W区间p,qN步骤从算术编码数值中提取字符5.35.3 行程编码 在频率相关编码中，要求已知待传文件各字符的频率值，并假设比特位被组成字符或其他一些重复的单元。在实际应用中，还有很多传播数据不具这样的性质，如二进制（机器代码）文件、传真数据、音频/视频信号等。为此需要一种更加通用的能够对任意比特串进行压缩的技术。行程编码（run-length encoding）正是适应这种压缩要求的一种简单压缩方法，其基本思想是：对需要传输的比特串进行分析，寻找连续的0或1，通过只发送有多少个连续的0或1实现数据传输的压缩。8.2.1 相同比特的行程编码相同比特的行程编码 相同比特的行程编码主要用于原始比特流中大多数连续序列为0的情况，例如传真传输。这种方法只是将每个连续的0序列长度（连续的0的个数）用一个固定长度的二进制整数传送出去。接收方将收到的整数转换成对应个数的0序列，并在各序列间插入一个“1”即可使压缩编码还原。例如，假设用4个比特表示连续的0序列长度，考虑图8-2（a）的比特流。序列长度（二进制）1110 1001 0000 1111 0101 1111 1111 0000 0000 1011序列长度（十进制）14 9 0 15 5 15 15 0 0 11 （b）行程编码流图8-2 压缩前的比特流和行程编码流在原始比特流中，如果第一个比特位为1，则在起始处填充一个长度为0的零序列；在连续的非0序列间以0序列填充（如图8-2（b）中红色表示的0000序列）；若序列长度不足以用4bit表示时（如30），则以若干“全1”序列及一个“非全1”序列表示（如图8-2（b）中蓝色表示的0000即为填充的“非全1”序列），称为组成码。1400 1900200030001100111190比特比特流非0非01（a）压缩前的比特流 5.3.2 5.3.2 不同字符的行程不同字符的行程 相同比特编码技术适用于原始比特流中有很多个零序列的压缩。随着值为1的比特出现频率的增大，效率也将有所下降。在极端的情况下，采用这种技术甚至会产生更长的比特流。如果原始数据由不同的字符组成，对于连续的相同字符，也可以采用相同比特编码的思想：在一个序列长度后面紧跟实际字符来表示。例如，字符串 HHHHHHHUFFFFFFFFFFFFFFYYYYYYYYYYYYYYYYYDGGGGGGGG可以采用数字和字符交替的形式发送出去，即用序列7、H、1、U、14、F、17、Y、1、D、8、G表示上述字符流。这样的一种表示方式称为不同字符的行程编码。5.3.3 5.3.3 传真压缩传真压缩 传真机是通过扫描页面，产生一个比特图代表页面上的图像，并在电话网上使用数字技术传输图像。下面仅就A4文档的传真技术进行讨论。A4文档的大小尺寸为210297mm，如果每一平方毫米用一个88的像素矩阵表示，则每一页需要传输超过300万个像素。用于传真压缩的T.4和T.6标准采用了一种基于序列长度的频率相关编码技术，即白黑像素序列之后，添加由序列长度的频率决定的频率相关编码，称为改进的哈夫曼编码。前提和编码过程如下：1）每一行中白像素和黑像素序列交替出现；2）每一行由白像素序列开始。如果页面带有黑色边界，扫描过程将在每行起始和终止处添加白像素；3）为交替出现的白、黑像素序列计算编码，并传输编码比特流。序列长度常见的有6比特、7比特、8比特几种形式，当像素序列长度少于64（26）位时，作为终止码；而当序列长度大于规定比特数时，使用组成码。5.45.4 相对编码 传真压缩技术适用于长序列页面的压缩，平均压缩率可以达到90%以上。然而，对于相邻行之间差别不大的页面，如图像传真，则这样的方法甚至可能产生负压缩率。类似的例子还有视频传输。对于图像传真，T.6标准采用先建立一个基础行，然后计算下一行与其差异，并只对这些差异进行编码传输的技术。这就是相对编码（relative encoding）的基本思想。视频传输较图像传真要复杂得多，其特点是：每秒传输30幅图像，单一的视频图像重复很少，但相邻的单一图像间会有大量重复。为此，视频压缩采用了相对编码的技术：不是把每一个帧当作一个独立的实体进行压缩和传输，而是考虑一个帧与前一个帧的差异之处，并对其进行编码传输。这样的方法也称为差分编码（differential encoding）。原理十分简单：第一个帧被发送出去，并存储在接收方的缓冲区中。接着发送方将第二帧与第一帧比较，对差别进行编码，并以帧格式发送出去。接收方收到这个帧，对差别部分在第一帧的基础上进行相应操作，产生第二帧，并将其存储到缓冲区中。继续该过程，不断产生新的帧。图8-3显示了其工作原理。7 6 2 8 6 6 3 5 66 5 7 6 5 6 3 2 3 78 4 6 8 5 6 4 8 8 5 1 3 9 8 6 5 5 7 65 5 2 9 9 6 8 9 5 1 第二帧 7 6 2 8 6 6 3 5 66 5 8 6 5 6 3 3 3 78 4 6 8 5 6 4 8 8 5 1 3 9 7 6 5 5 8 65 5 2 9 9 6 8 9 5 1 第三帧0 0 0 0 0 0 0 0 0 00 0 0 1 0 0 0 0 1 00 0 0 0 0 0 0 0 0 00 0 1 0 0 0 0 0 1 00 0 0 0 0 0 0 0 0 0 传输帧中包含第一帧 和第二帧差异的编码0 0 0 0 0 0 0 0 0 00 0 1 0 0 0 0 1 0 00 0 0 0 0 0 0 0 0 00 0 0 0-1 0 0 0 1 00 0 0 0 0 0 0 0 0 0 传输帧中包含第二帧 和第三帧差异的编码 7 6 2 8 6 6 3 5 66 5 7 5 5 6 3 2 4 78 4 6 8 5 6 4 8 8 5 1 2 9 8 6 5 5 6 65 5 2 9 9 6 8 9 5 1 第一帧图8-3 相对编码5.5 5.5 Lempel-Ziv压缩 与行程编码不同，Lempel-Ziv压缩技术是通过对原始数据中重复出现的位串或字符串以一个特定的编码进行替代的压缩方法。这种技术或其变体也经常在UNIX的压缩命令、调制解调器的V.42 bis压缩标准以及图形交换格式GIF（Griphic Interchange Format）等多种应用中使用。例如，考查下面的句子：the tropical rain fell in drenching sheets，hammering the corrugated roof of the clinic building，roaring down the metal gutters，splashing on the ground in a torren.有几个字母序列重复出现：the、ro、ing等，假设我们用特殊符号、和分别代替这些字符串，则上述句子可以压缩为：t pical rain fell in drench sheets，hammer corrugated of clinic build ，ar down metal gutters，splash on g und in a torren.Lempel-Ziv压缩的一个重要特性是支持对任意字符序列的压缩，因为任何文件都可以看成ASCII字符的序列，所以这使该算法成为一种适用范围更广、更加灵活的算法。为了对一个Lempel-Ziv压缩文件进行解压，一种方法是将一张表明符号与字符串对应关系的符号表连同压缩文件一起传送出去，这样会部分抵消压缩的价值。Lempel-Ziv采用了一种无须传送符号表，对重复串自动进行匹配的简单算法，Lempel-Ziv压缩算法的工作原理简述如下：假设事先已设置一个代码表，存放重复串及其对应代码；开辟一个缓冲区，存放即将发送的字符串；以及一个用以构造重复串的临时字符串。压缩过程可描述为以下6个步骤：1）对代码表进行初始化，为原始文本文件中的每一个不同字母分配一个代码，并存储到代码表中；2）从文件中读取一个字符CH，与缓冲区中的字符串进行连接，形成一个临时字符串；3）判断临时字符串是否曾经出现过，即检查代码表中是否有该字符串；4）如果临时字符串未出现在代码表中，则为其分配一个代码，将字符串和代码存储到代码表中，同时输出缓冲区内容对应的代码，并以CH重置缓冲区；5）如果临时字符串曾经出现过，则将其移到缓冲区中；6）返回执行2），直至文件结束。上述过程可以通过流程图（图8-4）加以说明。其中，代码表由标识符code表示，缓冲区由buff表示，临时字符串由temp表示，当前输入字符由ch表示。开始代码表初始化从文件中读入一个字符chCh=EOF将ch与缓冲区buff中的内容连接后临时串temptempcode临时串temp缓冲区buff发送缓冲区buff代码结束分配一个代码给temp并一同存入代码表code发送buff对应代码以ch重置buffYYNN图8-4 Lempel-Zip压缩流程图该条件表示判断临时串temp是否曾经出现过，即temp是否包含在代码表code中例，假设文本文件内容为“ABABABCBA”，原文中包含ABC三个字符，表8-2显示了Lempel-Ziv压缩过程。当前字符ch代码表code缓冲区buff临时串temp发送内容代码初始化A/0 B/1 C/2AAABAB/3BAB0（A)ABA/4ABA1（B）BABABAABA/5AABA3（AB）BABABCABC/6CABC3（AB）BCB/7BCB2（C）ABABAEOF4（BA）Lempel-Ziv是一种以空间换取时间的算法。随着文件长度的增加，代码表中存储的字符串也将越来越长，从而传输的次数越来越少，使得传输的性能也就越来越好。例如对于上述文件“ABABABCBA”，只需要传输代码串“013324”即可。Lempel-Ziv算法的另一个方面涉及到解压缩算法，即接收方需要在没有代码表的情况下，对收到的代码串进行无差错地转换成对应的字符串，这就需要接收方重构代码表。为此，接收方必须事先获得最基础的基本信息初始字符代码表。如本例中初始代码表中包含的基础信息包括字符A、B、C及其对应的代码0、1、2。接收方依据输入的代码值和初始代码表中的有限信息，重建与发送方相同的代码表，并完成代码值到字符串的转换。流程图8-5为解压缩算法的思想描述。图8-5 Lempel-Ziv解压缩流程图开始代码表code初始化接收第一个代码cd并打印对应字符cdcode取对应串首字符ch并将其连接到前缀后构成临时串temp为临时串temp分配代码并存储到代码表code中取前缀首字符ch，并连接到前缀后构成临时串temp结束分配一个代码给temp并一同存入代码表code打印临时串tempYN将其作为临时串temp前缀接收下一代码cd打印代码cd对应字符串cd=EOFYN以字符串“ABABABCBABAB”为例说明Lempel-Ziv的解压过程。假设接收方收到的代码串为“013324”，代码表中的初始值为A/0、B/1和C/2。解压缩运行结果由表8-3给出。EOF8423310当前代码cdBBCAAB当前串首字符chBAB是AB/3BBABBAB否BAB/8BABBACB是CB/7BACABC是ABC/6CABABA是ABA/5ABABBA是BA/4ABA是A/0 B/1 C/2A打印内容临时串temp是否在表中代码表code前缀表8-3 Lempel-Ziv解压缩算法的运行时结果5.65.6 图像压缩 图像压缩是计算机多媒体数据应用、存储及传输的基础。图像在计算机中是由若干充分小的点来表示的，这些点称为像素（pixel）。一幅传真图像由若干黑白像素构成，每一个像素只需要采用0或1来表示，即使用1个比特对应表示一个像素。但对于一幅彩色照片的表示就要复杂得多，不同的像素在颜色的亮度和色度上可能存在差异。为了反映这种差异，视频技术采用RGB（红绿蓝）三种基本色的组合来表示每一个像素：即每一种基色采用8比特表示，共28256个灰度级。每一个像素的三种基色可由38=24个比特表示，可以显示224（约为1亿6千7百万）种不同的色彩，称为真彩色。为此需要建立一个数据结构，用来表示每个像素对应的颜色组合。由于人眼对于不同颜色的亮度及色度存在敏感差异，所以，全美电视系统委员会（NTSC）建立了另一种表示像素色度及亮度的系统YIQ系统。YIQ系统仍然采用3个8比特组，其中一个组表示亮度，用Y表示；另外两个组表示色度，分别用I和Q表示。Y、I、Q与R、G、B的对应关系为：通过以上公式，可以容易地实现RGB系统到YIQ系统的转换，反之亦然。本节所讨论的重点是图像在存储和传输中的压缩问题，而不关心图像具体的表示标准，只要知道一个像素可以用三个8比特组表示就足够了。假设需要传输一幅典型的VGA屏幕图像，已知一幅VGA图像由640480个像素构成，则需要24640480=7372800 bit。对于视频信号通常每秒包含30幅图像，而且经常需要同时向不同的用户进行传输，需要传输的数据量高达数千兆比特。由此可见，采用压缩算法显著地减少比特数量是网络多媒体应用的基础。0.31B0.52G0.21RQ0.32B0.28G0.6RI 0.11B0.59G0.3RY5.6.2 JPEG5.6.2 JPEG压缩压缩 JPEG（Joint Photographics Expert Group）是联合图像专家组的缩写。JPEG压缩算法用于灰度图像和照相级别的彩色图像的压缩。无损压缩（lossless compression）：解压缩算法能够恢复嵌在压缩代码中的所有信息。有损压缩（lossy compression）：解压缩后获得的图像可能与原始图像不同。JPEG压缩属于后者。利用人类视觉系统的局限性实现图像的最大压缩比压缩，正是JPEG算法的设计目标。JPEG压缩可分为三个阶段：离散余弦变换（Discrete Cosine Transform）、量化（quantization）和编码（encoding）阶段，如图8-6所示。图像DCT量化编码图8-6 JPEG压缩的三个阶段1、DCT阶段JPEG将一幅图像划分成若干个矩阵，每个矩阵由88个像素组成。对于单色灰度图像，每个像素用一个8 bit的数字表示。每个矩阵可以用一个88的二维数组表示，数组元素为0255的8 bit整数。如果图像是彩色的，则每个像素需要用24 bit来表示，即用三个88的二维数组表示一个彩色矩阵。离散余弦变换就是作用于每一个数组使其具有更好的压缩效果。假设有88的数组P和T，离散余弦变换定义为：其中i=0,1,2,7，j=0,1,2,7，以及在公式（8-1）中，矩阵T是原始矩阵P经过离散余弦变换后得到的一个新的矩阵，它是像素在方块中位置的函数，称为空间频率（spatial frequencies），T0,0的值称为DC系数，其他值称为AC系数。)16)12(cos()16)12(cos(,7070jyixyxPxyTi,j=0.25c(i)c(j)(8-1)其他，若 10,21iC（i）=对于DC系数，当i和j均为0时，余弦函数都为1，它与数组P的平均值有关，反映了该矩阵的基本色调；而对于AC系数，i 和j 的值越大，像素值乘上的余弦函数频率就越大，即对应更高的空间频率，此时AC系数随着与左上角距离的增大而逐渐变小，它是像素精度变化的一种尺度。图8-7为应用离散余弦变换到两个不同数组的结果。P数组160150140130120110100901501401301201101009080140130120110100908070130120110100908070601201101009080706050110100908070605040100908070605040309080706050403020T数组（四舍五入取整）0000000-1000000000000000-6000000000000000-19000000000000000-182-10-60-190-182720图8-7（a）数组P对应一幅均匀变化且不太精细的图像，在进行离散余弦变换后得到一个包含大量0值的数组TP数组120101901010050120120101901201010150302001001070150200201201502002019090120200200101001020012019090101005015020200301302001012030120200201101020012020015010010050150100T数组（向下取整）80-76-48-210-9352-1432-62-185-8015-53-3713235-61152-66544-18-23-18967-36-40-56-24-7150-48-272830-1227-35924-1781-37105130-9-32110-71-601411-36-6046-3869-56559-1715835图8-7（b）数组P对应一幅小范围颜色剧烈变化且包含许多精密细节的图像，变换后得到的数组T的AC系数均不为0 仅有离散余弦的变换是不够的，还必须有相应的逆变换，即将空间频率变换的结果重新转换为像素值。变换公式为：)16)12(cos()16)12(cos(,)()(7070jyixjiTjcicxyPx,y=0.25(8-2)2、量化阶段量化阶段提供了一种忽略一幅图象中不易察觉的细小差异的方法，它通过将每个T值除以某个数，然后取最近的整数来定义另一个二维数组（称为Q数组）。例如，假设T数组00000000070-1020-7000000000-10130-30-800000000020-30380-48000000000-70-80-480152Q数组000000000100000-1000000000001000-1000000000000040-5000000000-10-10-5015(8-3)(8-4)其中Q数组是T数组中每一个元素除以10并取整后得到的，这样做的目的是为了创建一个具有更多相同数的数组。如数组Q较数组T包含更多的0，换言之，Q比T具有更好的压缩效果。然而，这样做也意味着会丢失一些颜色。另一方面，这样的压缩过程不能通过逆运算使数组T还原。为了减少信息的丢失，我们希望尽可能多地保留数组中左上角位置的信息，因为它们所对应的是图像中不太精细而一旦改变容易察觉的部分。因此，通常的方法是定义一个称为U的量化数组，其左上角部分的值较小，而右下部分的值较大。然后对Q作如下定义：Qi,j=round(Ti,j/Ui,j)i=0,1,2,7;j=0,1,2,7这里round为取整函数。例如，对于（8-3）中的数组T，定义数组U如下（8-5）所示，量化后将得到数组Q如（8-6）所示。U数组29272523211917152725232119171513252321191715131123211917151311921191715131197191715131197517151311975315131197531(8-5）Q数组000000000000000-1000000000001000-1000000000000040-10000000000-10-10-100152(8-6）采用量化数组U对T所作的变换仍然是不可逆的，但数组U的值可以根据实际要求来设置：取值越小，则失真率也就越低。当然，这样压缩比也相应越低。在JPEG规范中，没有对U的取值作硬性规定，而取决于具体的应用。所以，寻找一个适当的U，以实现最小的丢失和最大的压缩比是一个重要的课题。3、编码阶段编码阶段的主要功能是对量化后的二维数组Q进行线性化处理，以实现最大化的压缩传输。因为量化后的数组通常包含多个连续的0，一种合理的线性化方法是使用行程编码。对于不同的排序方法，压缩结果存在很大的差异。000000000000000-1000000000001000-1000000000000040-10000000000-10-10-100152(8-6）例如，对于（8-6）式所示的数组Q，如果以两行作为一个序列进行编码，则每个序列所得到的连续0的最大长度为：第1、2行：9个 第3、4行：13个 第5、6行：11个 第7、8行：15个但如果我们把整个数组作为一个序列，并按图中箭头方向对元素进行排序，则将得到如下的序列：长度为11的序列 长度为24的系列 在第二种方法中充分利用了量化数组空间频率较高的值相对集中的特点，从而达到较好的压缩效果。5.6.3 GIF5.6.3 GIF压缩压缩 JPEG应用于全彩色（支持224种不同的颜色）图像，而图形交换格式GIF（Graphics Interchange Format）是一种采用256（28）种颜色的图像表示方法。其基本思想是：建立一个索引表，将256种颜色存储在表中，用8比特索引代替24比特像素值，索引指向包含最符合原始色彩的表格条目，再对得到的比特值用Lempel-Ziv编码的变种版本进行压缩。如果色彩超过256种，GIF文件就是有损耗的，否则就是无损耗的。GIF格式适用于含有相对较少颜色且色彩边界严格定义的图像。如卡通、图表和线条画等。对于类似真彩色照片一类多变化、有阴影的高质量图像则不适用。5.75.7 多媒体压缩 5.7.1 MPEG5.7.1 MPEG压缩压缩 MPEG是ISO、IEC（国际电工委员会）和ITU（国际电信联盟）合作定义视频图像标准的专业组织移动图像专家组（Moving Pictures Expert Grroup）的缩写。由MPEG定义的视频压缩标准主要有：MPEG-1：为CD-ROM视频及早期广播卫星设计。MPEG-2：用于高要求的应用，如多媒体娱乐、高清晰数字电视（HDTV）以及广播卫星通信等。最初专为HDTV定义的MPEG-3后来被并入MPEG-2中。MPEG-4：用于低带宽信道上的视频会议。当前已对支持更广泛应用的MPEG-7进行了定义，它在多媒体数据的传输将占用更多带宽的假设前提下，为定义和访问内容提供多种多媒体工具。如声音、图像的非规范检索。本节仅就MPEG-1的原理进行讨论，并认为是MPEG的普遍原理。视频流压缩的相对编码原理在MPEG实现的时候进行了扩充，这是因为：1）差别计算适用于帧间差别极小的情况。当场景发生改变或出现新的物体时，若仍用基本帧来衡量所有的帧，则成功的几率极小。2）如果使用差分方法计算后续帧的差异，那么在一个帧中引入的任何误差都会传播到后续的帧中。3）在直播系统中，任何人可以在任何时刻加入收看。如果加入时错过了基本帧，就不能得到与后续帧比较的基本信息。针对上述问题，MPEG标识了三种不同类型的帧：I帧（Intrapicture frame图像内帧）一种自包含的帧，其实质就是一幅JPEG图像。P帧（Predicated frame预测帧）一种通过计算当前帧与前一个帧的差别来进行编码的帧。B帧（Bidirectional frame双向帧）类似于P帧，用于在前一个帧和后续帧之间插入的帧。图88显示了一个典型的MPEG帧序列。其中I帧必须在任何帧序列中周期性地出现；在两个I帧之间夹着一个P帧，P帧基本上是与前一个I帧的差值；在I帧与P帧之间则夹着若干个B帧，B帧是根据已知的I帧和P帧的值经差值计算得到的帧。图88显示的是MPEG帧的播放次序，而不是传送次序。P帧在最初的两个B帧前面传送；第二个I帧在最后两个B帧前面传送；P帧和两个I帧被缓存起来，接收端据此对收到的B帧进行解码。I帧I帧P帧B帧B帧B帧B帧图88 典型的MPEG帧序列 P帧使用一种称为运动补偿预测的方法进行编码，它把图像划分成若干块，每块包含256（1616）个像素。假设每个像素用一个亮度值和两个色度值表示（即YIQ系统），那么每个块就需要用三个1616的数组表示。MPEG用四个色度值的平均值来代替这四个值，将两个色度数组缩减为两个88的数组，如图89所示。这样做虽然会产生信息损耗，但通常不是很明显。图89 将1616的色度数组缩减为88的色度数组 在发送每个P帧之前，先在前一个I帧中临近区域查找最佳的匹配块。一旦找到最佳匹配块就计算匹配帧之间的差值及运动向量，并保存起来。帧中的所有块都做相同的操作，然后按JPEG的方法对结果进行编码并发送。其中差值用于重建块，而运动向量用于确定块在帧中的位置。时间将来当前过去YFYCYP插入线图810 用插入法估计一个值 B帧的编码也是类似的，但它的块被插入在前后两个帧的匹配块之间。图810说明了插入的方法：假设横轴表示时间，已知某个过去时刻和某个将来时刻的数量值，分别用YP和YF表示，由此可以估算出当前时刻的值YC。至于插入算法不在本节讨论之列。B帧的编码方法也适用于在前一个帧中匹配不成功的情况。比如视图中出现新的物体的时候尤其有效。5.7.2 MP35.7.2 MP3 MP3（MPEG audio layer 3）是指MPEG的第三层，用于音频压缩。在1992年公布的ISO/IEC标准将MPEG的音频信号分为三个层次进行压缩，每层在编码复杂度、压缩比以及声音质量方面均有所不同：第一层产生大约4：1的压缩比率，以每一通道192 kbps的比特率来产生声音。第二层产生大约8：1的压缩比率，以每一通道128 kbps的比特率来产生声音。第三层产生大约12：1的压缩比率，适用于每一通道大约64 kbps的比特率。对于高保真音频信号，人们可以识别的频率范围在20Hz到20 kHz之间。根据采样定理，采样频率为44.1kHz，每个采样使用16比特的样本，以此速率进行采样和编码，足以重建信号，并产生CD质量的声音。但是，由此产生的数据量为 1644.11000700000bps 这还只是一个声道的数据量，对于双声道立体声，数据量达到1.4 Mbps。不仅文件大，而且还需要1.4 Mbps的传输率来产生声音。如果采用减少量化级别或减少采样频率的方法进行压缩，都将导致声音失真。考虑到人们对于声音的听觉屏蔽，MP3技术主要基于心理声学模型原理来实现压缩。简单的说，MP3就是通过对捕捉到的每一个音频信号进行判断，将人耳听力范围之外的信号从音频流中删除，仅对剩下的信号进行编码的数字化技术。MP3压缩过程可以分为滤波、量化和编码三个阶段，如图811所示。滤波器库量化阶段哈夫曼编码心理声学模型音频流子带输出按块划分量化值MP3流决定每一子带输出的比特数图8-11 MP3编码过程 MP3压缩的第一步是子带编码，它将音频流经滤波器库生成若干不同频率范围的非重叠的信号分量，称为频段或子带。每一个频段对应一个滤波器。由于听觉屏蔽，根据心理声学模型滤掉冗余信号后，对剩余的各个子带分别提供不同的频率：对于较弱的信号所提供的分辨率较低，而对于较强的信号则采用较高的分辨率。经过第一步的滤波压缩后，音质不会产生明显损耗。最终结果是每一子带使用不同的比特数目进行编码。第二步，子带信号进入量化阶段。对于不同子带分别采用JPEG压缩，去除一些不易察觉的微小差异，以减少每一子带中数据量的总数。最后对量化值再进行哈夫曼编码，这样就得到了MP3比特流。数据压缩技术小结数据压缩技术利用不同应用的冗余类型所设计的压缩方法也各不相同。常见的压缩算法小结如下：哈夫曼编码哈夫曼编码：对原文中的各个字符进行频率统计，为频繁使用的字符分配较短的比特编码，而较少使用的字符分配较长的比特序列。算术压缩算术压缩：采用一个0，1之间的实数来表示一个字符串。其基本思想是从区间x，y0，1开始，随着字符串的增长，逐渐缩小区间x，y的宽度，最终获得一个可以表示该字符串的特定区间，由此建立实数区间x，y与字符串的映射关系。行程编码行程编码：当数据中包含有一长串相同的字符或比特时，采用序列串长度值替换该序列。相对编码相对编码：比较数据块之间的差异，仅对差别进行编码传输。这里，数据块可以是行结构，也可以是帧结构。Lempel-ZivLempel-Ziv编码编码：用特定的代码替换重复出现的字符或比特序列进行压缩传输。JPEGJPEG：利用图像的小子集细节变化小的特点，将一幅图像分割成若干88像素矩阵，将离散余弦变换应用到各像素矩阵上，对运算结果进行量化，尽可能保留像素矩阵的基本特点，去除影响不大的细节，然后对量化后的频率系数进行编码。GIFGIF：用8 bit（256色）的像素值取代24 bit的真彩色，为此需要建立二者的对应索引表，再对得到的比特值进行Lempel-Ziv进行压缩。MPEGMPEG：使用JPEG对内帧（I帧）进行压缩，同时利用连续帧之间的冗余，通过计算连续帧的差别和运动预测技术进行预测帧（P帧）及双向帧（B帧）的计算。MP3MP3：利用滤波器库将音频信号划分成若干频段，根据心理声学模型去除冗余音频信号，然后分别对各频段按需进行量化和编码。