笫5章 数据压缩.ppt

第五章 数据压缩 以字符串“ABABABCBABAB”为例说明Lempel-Ziv的解压过程。假设接收方收到的代码串为“013324”，代码表中的初始值为A/0、B/1和C/2。解压缩运行结果由表8-3给出。 － － － － EOF － － 8 4 2 3 3 1 0 当前代码cd B B C A A B － 当前串首字符ch B AB 是 AB/3 B BAB BAB 否 BAB/8 BAB BA CB 是 CB/7 BA C ABC 是 ABC/6 C AB ABA 是 ABA/5 AB AB BA 是 BA/4 AB A － 是 A/0 B/1 C/2 A 打印内容 临时串temp 是否在表中 代码表code 前缀 表8-3 Lempel-Ziv解压缩算法的运行时结果 5.6 图像压缩 图像压缩是计算机多媒体数据应用、存储及传输的基础。 图像在计算机中是由若干充分小的点来表示的，这些点称为像素（pixel）。一幅传真图像由若干黑白像素构成，每一个像素只需要采用0或1来表示，即使用1个比特对应表示一个像素。但对于一幅彩色照片的表示就要复杂得多，不同的像素在颜色的亮度和色度上可能存在差异。为了反映这种差异，视频技术采用RGB（红绿蓝）三种基本色的组合来表示每一个像素：即每一种基色采用8比特表示，共28＝256个灰度级。每一个像素的三种基色可由3×8=24个比特表示，可以显示224（约为1亿6千7百万）种不同的色彩，称为真彩色。为此需要建立一个数据结构，用来表示每个像素对应的颜色组合。 由于人眼对于不同颜色的亮度及色度存在敏感差异，所以，全美电视系统委员会（NTSC）建立了另一种表示像素色度及亮度的系统—YIQ系统。 YIQ系统仍然采用3个8比特组，其中一个组表示亮度，用Y表示；另外两个组表示色度，分别用I和Q表示。Y、I、Q与R、G、B的对应关系为： 通过以上公式，可以容易地实现RGB系统到YIQ系统的转换，反之亦然。本节所讨论的重点是图像在存储和传输中的压缩问题，而不关心图像具体的表示标准，只要知道一个像素可以用三个8比特组表示就足够了。 假设需要传输一幅典型的VGA屏幕图像，已知一幅VGA图像由640?480个像素构成，则需要24?640?480=7372800 bit。对于视频信号通常每秒包含30幅图像，而且经常需要同时向不同的用户进行传输，需要传输的数据量高达数千兆比特。由此可见，采用压缩算法显著地减少比特数量是网络多媒体应用的基础。 5.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将一幅图像划分成若干个矩阵，每个矩阵由8?8个像素组成。对于单色灰度图像，每个像素用一个8 bit的数字表示。每个矩阵可以用一个8?8的二维数组表示，数组元素为0～255的8 bit整数。如果图像是彩色的，则每个像素需要用24 bit来表示，即用三个8?8的二维数组表示一个彩色矩阵。离散余弦变换就是作用于每一个数组使其具有更好的压缩效果。假设有8?8的数组P和T，离散余弦变换定义为： 其中i=0,1,2,…7，j= 0,1,2,…7，以及 在公式（8-1）中，矩阵T是原始矩阵P经过离散余弦变换后得到的一个新的矩阵，它是像素在方块中位置的函数，称为空间频率（spatial frequencies），T[0,0]的值称为DC系数，其他值称为AC系数。 T[i,j]=0.25c(i)c(j) (8-1) C（i）= 对于DC系数， 当i和j均为0时，余弦函数都为1，它与数组P的平均值有关，反映了该矩阵的基本色调；而对于AC系数，i 和j 的值越大，像素值乘上的余弦函数频率就越大，即对应更高的空间频率，此时AC系数随着与