压缩编码绪论(2015)

1、1 1压缩编码技术压缩编码技术 21、课堂出勤。、课堂出勤。课程每学分不得超过一次缺勤课程每学分不得超过一次缺勤，每缺勤，每缺勤一次，期末总成绩扣五分；若缺勤次数超过课程学分数，一次，期末总成绩扣五分；若缺勤次数超过课程学分数，则取消该门课程的期末考试资格。则取消该门课程的期末考试资格。2、作业。课程作业缺交量超过作业总量、作业。课程作业缺交量超过作业总量30%及以上的，及以上的，取消该门课程的期末考试资格。办理课程免听的学生亦取消该门课程的期末考试资格。办理课程免听的学生亦参照此规定执行，教学办在学生办理免听手续时，须向参照此规定执行，教学办在学生办理免听手续时，须向学生声明强调此规定。学生

2、声明强调此规定。 学院的有关规定学院的有关规定3考核方式考核方式 开卷考试开卷考试 考试内容：考试内容： 基础知识和基本原理基础知识和基本原理 压缩编码方法压缩编码方法 4教材及参考书目教材及参考书目 1.吴乐南.数据压缩（第三版）.北京:电子工业出版社，2012.8 （主要教材）（主要教材）2.吴家安.数据压缩技术及应用.北京:科学出版社，2009.13.戴善荣.数据压缩.西安:西安电子科学技术出版社,2005.54.Khalid Sayood著.数据压缩导论.北京:人民邮电出版社,20095.David Salomon著.数据压缩原理与应用.北京:电子工业出版社,2003.9 5参考书目参

3、考书目 6参考书目参考书目 7其他参考书目其他参考书目 8其他参考书目其他参考书目 9教学内容教学内容 第一章第一章 绪论绪论 第二章第二章 信源的数字化与压缩系统评价信源的数字化与压缩系统评价 第三章第三章 数据压缩的信息论基础数据压缩的信息论基础 第四章第四章 统计编码统计编码 第五章第五章 预测编码预测编码 第六章第六章 变换编码变换编码 第七章第七章 子带编码与小波变换子带编码与小波变换 第八章第八章 图像图像/视频压缩编码的国际标准视频压缩编码的国际标准10第一章第一章 绪绪 论论1.1 什么是数据压缩？什么是数据压缩？1.2 数据压缩的必要性数据压缩的必要性1.3 数据压缩技术的分

4、类数据压缩技术的分类1.4 数据压缩技术的历史发展数据压缩技术的历史发展111.1 什么是数据压缩？什么是数据压缩？u数据压缩数据压缩：用紧致的方式表示信息的技术或科学。：用紧致的方式表示信息的技术或科学。探求任何信源的探求任何信源的“精纯精纯”表述，而又不致带来重表述，而又不致带来重大的失真，这就是数据压缩要解决的命题。大的失真，这就是数据压缩要解决的命题。121.1 什么是数据压缩？什么是数据压缩？u信息：抽象的，要表达的特定意思；信息：抽象的，要表达的特定意思；u消息：可以把信息表达出来的文字、语言或消息：可以把信息表达出来的文字、语言或图像等，具体的；图像等，具体的；u信号：消息的物理

5、体现，可在通信系统中传信号：消息的物理体现，可在通信系统中传输，如光信号、电信号；输，如光信号、电信号；l通信最基本、最重要的功能就是通信最基本、最重要的功能就是传递传递信信息，获取信息、处理信息、和利用信息。息，获取信息、处理信息、和利用信息。131.1 什么是数据压缩？什么是数据压缩？141.1 什么是数据压缩？什么是数据压缩？u信源编码：压缩与解压缩、加密与解密信源编码：压缩与解压缩、加密与解密 主要解决传输的主要解决传输的有效性有效性问题问题 用最少的数码传递最大的信息量。用最少的数码传递最大的信息量。u信道编码：尽量克服传输过程中的差错信道编码：尽量克服传输过程中的差错 主要解决传输

6、的主要解决传输的可靠性可靠性问题问题 151.1 什么是数据压缩？什么是数据压缩？161.1 什么是数据压缩？什么是数据压缩？u信源编码：压缩与解压缩、加密与解密信源编码：压缩与解压缩、加密与解密 主要解决传输的主要解决传输的有效性有效性问题问题l数据压缩：以最少的平均信息位来表示信源所发出数据压缩：以最少的平均信息位来表示信源所发出的信息，减少容纳给定消息集合或数据采样集合的的信息，减少容纳给定消息集合或数据采样集合的信号空间（数据存储介质、时间、带宽，即空域、信号空间（数据存储介质、时间、带宽，即空域、时域和频域等）。时域和频域等）。17 Winzip、RAR、ARJ、UNIX下的压缩程序

7、等：下的压缩程序等： JPEG、GIF： AVI、MPEG2、MPEG4： PostScript： 基于字典模型的压缩技术（基于字典模型的压缩技术（LZ77、LZ78、LZW）灰度、彩色图像的压缩灰度、彩色图像的压缩矢量图像压缩矢量图像压缩声音视频信号的压缩声音视频信号的压缩实实 际际 应应 用用18第一章第一章 绪绪 论论1.1 什么是数据压缩？什么是数据压缩？1.2 数据压缩的必要性数据压缩的必要性1.3 数据压缩技术的分类数据压缩技术的分类1.4 数据压缩技术的历史发展数据压缩技术的历史发展191.2 数据压缩的必要性数据压缩的必要性数字传输系统的优点：数字传输系统的优点： 数字传输质量

8、高于模拟传输质量，经多次中继不引数字传输质量高于模拟传输质量，经多次中继不引起严重的噪声累积，不受系统非线性影响起严重的噪声累积，不受系统非线性影响 易于采用信道编码技术提高传输的可靠性易于采用信道编码技术提高传输的可靠性 便于利用时分复用技术与其他通信业务相结合便于利用时分复用技术与其他通信业务相结合 易于数字加密，提高信息安全性易于数字加密，提高信息安全性 数字电路易于大规模集成数字电路易于大规模集成 数字设备可靠性高，维护简便数字设备可靠性高，维护简便20采用数字技术（或系统）具有许多优越性，但也使采用数字技术（或系统）具有许多优越性，但也使数据量大增数据量大增。数字信号的传输速率或比特

9、率。数字信号的传输速率或比特率 I 为：为： (bit/s or b/s)sIfR其中：数字化信号的取样频率其中：数字化信号的取样频率 ，每个取样幅度值，每个取样幅度值用用R 位二进制编码（位二进制编码（R bit）。可理解为：该信号在）。可理解为：该信号在通信线路上每秒钟应通信线路上每秒钟应传送的位数传送的位数，或着保存一秒钟，或着保存一秒钟信号样值所需要占用的信号样值所需要占用的存储容量存储容量。当取样速率一定时，比特率当取样速率一定时，比特率(或数码率、码率、速或数码率、码率、速率、数据率率、数据率)也可简单地用也可简单地用R表示表示，意为每个样值，意为每个样值R bit。一般传输时多用

10、。一般传输时多用I ，存储时只用，存储时只用R 。sf1.2 数据压缩的必要性数据压缩的必要性211.2 数据压缩的必要性数据压缩的必要性几种常见视频图像源未压缩的原始数据率几种常见视频图像源未压缩的原始数据率视频源视频源每秒每秒 帧率帧率分辨率（帧分辨率（帧内像素数）内像素数）未压缩数据率未压缩数据率 / / MbpsMbpsNTSCNTSC3030720720 480480125125PALPAL2525720720 576576125125VCRVCR2525352352 2882883131HDTVHDTV303019201920 1080108010001000221.2 数据压缩的

11、必要性数据压缩的必要性表表1.1 数字化音、视频格式数字化音、视频格式数字音频格式数字音频格式频带范围频带范围（Hz）取样频率取样频率（kHz）样本精度样本精度（bit）声道数声道数原始码率原始码率（Kb/s）电话电话300340088164调幅（调幅（AM）广播）广播50700011.025161176.4调频（调频（FM）广播）广播201500022.03162705.6激光唱盘（激光唱盘（CD）202000044.11621411.2数字录音带（数字录音带（DAT）2020000481621536数字视频格式数字视频格式每秒帧数每秒帧数图像分辨率图像分辨率（像素）（像素）样本精度样本精度

12、（bit）亮度信号原始码率亮度信号原始码率（Mb/s）CIF格式的亮度信号格式的亮度信号30352 x 288824.33CCIR 601的亮度信号的亮度信号30/25720 x 576882.944HDTV亮度信号亮度信号601920 x 10808995.323数字音频、视频信号数据传输速率计算数字音频、视频信号数据传输速率计算 从传输角度：从传输角度： 数字电话数字电话 一路广播级的彩色数字电视一路广播级的彩色数字电视(若按若按4:2:2（亮度（亮度/色差色差/色差）色差）的分量编码标准格式，用的分量编码标准格式，用13.5/6.75/6.75 MHz频率采样，每频率采样，每像素（像素（

13、pixel: picture element, 简写为简写为pel）用）用8位编码：位编码： 8864 kb/s(kbps)I 亦写作64等于等于3375路数字话路；路数字话路； Mb/s 2168)75. 675. 65 .13(I24从存储角度：从存储角度： 512512像素、像素、8bit/pel黑白图像：黑白图像： 512512像素、每分量像素、每分量8bit/pel的彩色图像：的彩色图像： 一幅一幅223022308bit的气象卫星红外云图的气象卫星红外云图37.94MB： kB 2568512512RkB 7683kB 256RMB 37.948MB 74. 4822302230R

14、数字音频、视频信号数据传输速率计算数字音频、视频信号数据传输速率计算 25 海洋地球物理勘探遥测数据海洋地球物理勘探遥测数据： 60路传感器，每路信号按路传感器，每路信号按1KHz频率采样、频率采样、16位位模模-数转换器（数转换器（A/D）量化而得，每）量化而得，每1km就需记录就需记录1盘盘0.5英寸的计算机磁带，而仅仅一条测量船每英寸的计算机磁带，而仅仅一条测量船每年可勘测年可勘测15000km 。 一颗卫星每半个小时即可发回一次全波段数据（一颗卫星每半个小时即可发回一次全波段数据（5个个波段），每天的数据率高达波段），每天的数据率高达1.1GB 数字音频、视频信号数据传输速率计算数字音

15、频、视频信号数据传输速率计算 261.2 数据压缩的必要性数据压缩的必要性u数据压缩的目的数据压缩的目的1. 在现有系统特性限制下，通过数据压缩来满足在现有系统特性限制下，通过数据压缩来满足工作要求。工作要求。2. 在新系统设计时，通过数据压缩，节省成本。在新系统设计时，通过数据压缩，节省成本。3. 在某些情况下，由于客观条件限制，即使不惜在某些情况下，由于客观条件限制，即使不惜成本也无法满足设计要求，数据压缩就是唯成本也无法满足设计要求，数据压缩就是唯一的途径。一的途径。27为什么可以压缩？为什么可以压缩？u自然界中的大多数数据都是冗余的：任何非随机选择自然界中的大多数数据都是冗余的：任何非

16、随机选择的数据都有一定结构，可利用这种结构得到数据的更的数据都有一定结构，可利用这种结构得到数据的更紧致表示紧致表示 统计冗余：大多数常见的压缩算法都利用了该冗余统计冗余：大多数常见的压缩算法都利用了该冗余 字母冗余：英文中字母字母冗余：英文中字母E最常出现，而最常出现，而Z很少出现很少出现 文本冗余：字母文本冗余：字母Q后常跟有字母后常跟有字母U 图像冗余：自然图像中相邻像素的颜色往往比较相近图像冗余：自然图像中相邻像素的颜色往往比较相近 数据的物理产生过程数据的物理产生过程 如利用人类的发声系统，设计语音压缩算法如利用人类的发声系统，设计语音压缩算法 可用在军事、移动通信和玩具中的语音合成

17、中可用在军事、移动通信和玩具中的语音合成中 数据的应用：感知冗余数据的应用：感知冗余 听觉冗余：如听觉冗余：如mp3音频编码音频编码 视觉冗余视觉冗余28例：空间冗余例：空间冗余u图像中存在大面积部分相似或完全一样的像素图像中存在大面积部分相似或完全一样的像素 水平相邻像素的联合直方图水平相邻像素的联合直方图pmf29例：时间冗余例：时间冗余u视频图像前后几帧的内容变化不大（位置可能不视频图像前后几帧的内容变化不大（位置可能不同，可用运动估计方法找到对应位置）同，可用运动估计方法找到对应位置）30例：结构冗余例：结构冗余u图像中物体表面纹理等结构存在冗余图像中物体表面纹理等结构存在冗余311.

18、2 数据压缩的必要性数据压缩的必要性u不进行数据压缩，无论传输或存储都很难实用化，不进行数据压缩，无论传输或存储都很难实用化，数据压缩的好处就在于：数据压缩的好处就在于：1. 较快地传输各种信源，降低信道占用的费用；较快地传输各种信源，降低信道占用的费用；（时间域上的压缩）（时间域上的压缩）2. 在有限带宽上能开展更多的并行业务。在有限带宽上能开展更多的并行业务。 （频率域上的压缩）（频率域上的压缩）3. 对移动设备而言，能够降低发射功率。对移动设备而言，能够降低发射功率。 （能量域上的压缩）（能量域上的压缩）4. 减少数据存储的容量。（空间域上的压缩）减少数据存储的容量。（空间域上的压缩）3

19、2第一章第一章 绪绪 论论1.1 什么是数据压缩？什么是数据压缩？1.2 数据压缩的必要性数据压缩的必要性1.3 数据压缩技术的分类数据压缩技术的分类1.4 数据压缩技术的历史发展数据压缩技术的历史发展33可逆压缩可逆压缩 (Lossless Compression) 冗余度压缩：去除或减少那些可能是后来插入数据中的冗余冗余度压缩：去除或减少那些可能是后来插入数据中的冗余度，是一个可逆过程。度，是一个可逆过程。香农（香农（C.E.ShannonC.E.Shannon）信息论：）信息论：数据数据= =信息信息+ +冗余度冗余度其他术语：无损压缩、无失真、无差错编码（其他术语：无损压缩、无失真、无

20、差错编码（Error Free Coding）、无噪声（）、无噪声（Noiseless）编码、冗余度压缩）编码、冗余度压缩(Redundancy Reduction)、熵编码、熵编码 (Entropy Coding)、数、数据紧缩据紧缩 (Data compaction)、信息保持编码（、信息保持编码（Lossless, Bit-preserving）。）。 34例例1-4 计算不同采样值间重复采样的数目计算不同采样值间重复采样的数目(游程游程)，然，然后将变化的采样值与该重复数目一起发送。后将变化的采样值与该重复数目一起发送。 Compression（压缩）（压缩） : 针对数据内部的多余信

21、息进行压缩；针对数据内部的多余信息进行压缩； 例例1-5 12位位A/D变换，通常采用变换，通常采用1字字(2Byte)来存一个采来存一个采样值，这样每个样值就额外增加了样值，这样每个样值就额外增加了4位冗余度，但是位冗余度，但是如果改用如果改用3个字（个字（48bit）来存）来存4个数据，可消除冗余度。个数据，可消除冗余度。Compaction（紧缩）（紧缩） : 针对数据外在冗余度进行压缩。针对数据外在冗余度进行压缩。 举举 例例35不可逆压缩不可逆压缩(Lossy Compression) 又称又称: : 有失真（有失真（Lossy）压缩、熵压缩（）压缩、熵压缩（Entropy Comp

22、ression）。）。 例例1-61-6 对采样值设置门限，当采样值超过该门限对采样值设置门限，当采样值超过该门限时才传输时才传输原始采样值不可能恢复，信息丢失；原始采样值不可能恢复，信息丢失；举例：举例：36 有失真压缩（茶叶粉末无法恢复出茶叶）有失真压缩（茶叶粉末无法恢复出茶叶）例例1-71-7 茶叶压缩的例子茶叶压缩的例子 ，直观理解，直观理解 冗余度压缩冗余度压缩无失真压缩（茶叶保持完整）无失真压缩（茶叶保持完整） 外在冗余度：空气外在冗余度：空气数据紧缩数据紧缩 内在冗余度：水份内在冗余度：水份冗余度压缩冗余度压缩 茶叶压成粉末茶叶压成粉末铁罐可以装得更多铁罐可以装得更多茶叶（茶叶（

23、“数据数据”）放入铁罐（）放入铁罐（“存储器存储器”）37一般结论一般结论 有冗余度就可以压缩有冗余度就可以压缩 压缩只能在一定程度内可逆压缩只能在一定程度内可逆 超过一定限度，必然带来失真超过一定限度，必然带来失真 允许的失真越大，压缩的比例也可以越大允许的失真越大，压缩的比例也可以越大381.3 数据压缩技术分类数据压缩技术分类u按照信息论基本概念进行分类按照信息论基本概念进行分类冗余度压缩：仅对数据源中的冗余度进行压缩，冗余度压缩：仅对数据源中的冗余度进行压缩，去除冗余信息，又称无失真压缩、无噪压缩或去除冗余信息，又称无失真压缩、无噪压缩或可逆压缩。可逆压缩。熵压缩：不仅对数据源中的冗余

24、信息进行压缩，熵压缩：不仅对数据源中的冗余信息进行压缩，还要对数据源所含的信息本身进行压缩，又称还要对数据源所含的信息本身进行压缩，又称有失真压缩、有损压缩或不可逆压缩。有失真压缩、有损压缩或不可逆压缩。391.3 数据压缩技术分类数据压缩技术分类u按照压缩所依据的信源输出分布特性分按照压缩所依据的信源输出分布特性分类类统计编码：根据信源输出符号的统计特性进行统计编码：根据信源输出符号的统计特性进行编码，以便最大限度去除压缩数据之间的统计编码，以便最大限度去除压缩数据之间的统计相关性，实现压缩目的。统计编码属于冗余度相关性，实现压缩目的。统计编码属于冗余度压缩，是经典的数据压缩方法。压缩，是经

25、典的数据压缩方法。字典编码：又称为字典编码：又称为LZ编码，是从信源输出的数编码，是从信源输出的数据中选择字符串，并把字符串编码为一个标识据中选择字符串，并把字符串编码为一个标识加以保存，利用查字典的原理对字符串编码，加以保存，利用查字典的原理对字符串编码，实现压缩的目的。实现压缩的目的。401.3 数据压缩技术分类数据压缩技术分类u按照数据编码所使用的编码技术分类按照数据编码所使用的编码技术分类预测编码、变换编码、基于模型的编码、基于预测编码、变换编码、基于模型的编码、基于小波方法的编码、分形编码等。小波方法的编码、分形编码等。u按照被压缩数据的频率范围分类按照被压缩数据的频率范围分类音频压

26、缩：语音压缩、声频压缩音频压缩：语音压缩、声频压缩视频压缩视频压缩411.3 数据压缩技术分类数据压缩技术分类u按照被压缩数据的属性分类按照被压缩数据的属性分类语音压缩、文本压缩语音压缩、文本压缩 、图形和图像压缩。、图形和图像压缩。u按照压缩算法的实现手段分类按照压缩算法的实现手段分类硬件压缩：通过硬件实现数据压缩硬件压缩：通过硬件实现数据压缩软件压缩：通过软件实现数据压缩软件压缩：通过软件实现数据压缩421.3 数据压缩技术分类数据压缩技术分类u按照数据压缩系统自适应能力分类按照数据压缩系统自适应能力分类自适应数据压缩：能够随着数据源的变化而自适应数据压缩：能够随着数据源的变化而相应调整压

27、缩编码器的特性以适应数据变化。相应调整压缩编码器的特性以适应数据变化。非自适应数据压缩：不能随着数据源的变化非自适应数据压缩：不能随着数据源的变化而相应调整压缩编码器特性的压缩方法。而相应调整压缩编码器特性的压缩方法。431.3 数据压缩技术分类数据压缩技术分类u按照压缩器和解压器的复杂度分类按照压缩器和解压器的复杂度分类对称压缩：压缩编码器和解压缩译码器的复对称压缩：压缩编码器和解压缩译码器的复杂度及工作量相同或基本相同。（多媒体通杂度及工作量相同或基本相同。（多媒体通信系统中的数据压缩多为对称压缩）信系统中的数据压缩多为对称压缩）非对称压缩：压缩编码器和解压缩译码器的非对称压缩：压缩编码器

28、和解压缩译码器的复杂度及工作量不同。（多媒体录放系统中复杂度及工作量不同。（多媒体录放系统中的数据压缩多为非对称压缩）的数据压缩多为非对称压缩）441.3 数据压缩技术分类数据压缩技术分类u按照数据压缩的应用领域分类按照数据压缩的应用领域分类遥测数据压缩、地震数据压缩、医学信息压遥测数据压缩、地震数据压缩、医学信息压缩、报纸压缩、数据库压缩等缩、报纸压缩、数据库压缩等u按照数据压缩使用的量化技术分类按照数据压缩使用的量化技术分类标量量化数据压缩标量量化数据压缩矢量量化数据压缩矢量量化数据压缩45数数据据压压缩缩冗余度冗余度压缩压缩（熵编（熵编码）码）统计编码统计编码霍夫曼编码、游程编码、二进制

29、信源编码等霍夫曼编码、游程编码、二进制信源编码等算术编码算术编码基于字典的编码：基于字典的编码：LZWLZW编码等编码等其他编码其他编码完全可逆的小波分解完全可逆的小波分解+ +统计编码等统计编码等熵压缩熵压缩特征抽取特征抽取分析分析/ /综合编码综合编码子带、小波、分形等子带、小波、分形等量化量化其他其他无记忆量化无记忆量化均匀量化、压扩量化均匀量化、压扩量化有有记记忆忆量量化化序列序列量化量化预测预测 编码编码增量调制、线性增量调制、线性/ /非线非线性性/ /自适应预测等自适应预测等其他其他 方法方法序贯量化等序贯量化等分组分组量化量化直接直接 映射映射矢量量化、神经网等矢量量化、神经网

30、等变换变换编码编码正交变换正交变换 KLTKLT、DCTDCT等等非正交变换非正交变换其他函数变换其他函数变换表表1.2 1.2 数据压缩技术的简单分类数据压缩技术的简单分类46编码实例：盲文编码实例：盲文 u由路易由路易布莱尔（布莱尔（Louis Braille）发明：）发明：3 x 2凸印点阵凸印点阵u26个盲文字母个盲文字母u一些盲文字和字符串一些盲文字和字符串u例：例：“to others”47编码实例：编码实例：Morse码码u19世纪中叶，由世纪中叶，由 Samuel Morse发明发明 每个字符用每个字符用“ . ” 表示表示48编码实例：编码实例：Morse码码 (2)uMor

31、se码与字母频率码与字母频率：u基本原则：基本原则：用较短的码字表示出现频率高的字符，较长的码字表示用较短的码字表示出现频率高的字符，较长的码字表示出现频率低的字符出现频率低的字符 但也不是但也不是100% 满足（如满足（如l vs. m ）u这就是利用统计冗余编码的基本思想这就是利用统计冗余编码的基本思想49图像压缩实例图像压缩实例u图象图象 丢失高频部分细节丢失高频部分细节 50第一章第一章 绪绪 论论1.1 什么是数据压缩？什么是数据压缩？1.2 数据压缩的必要性数据压缩的必要性1.3 数据压缩技术的分类数据压缩技术的分类1.4 数据压缩技术的历史发展数据压缩技术的历史发展51n 早在早

32、在1949年年，贝尔实验室的，贝尔实验室的 Claude Shannon 和和 MIT 的的 R.M.Fano 几乎同时提出了的对符号进行有效几乎同时提出了的对符号进行有效编码从而实现数据压缩的编码从而实现数据压缩的 Shannon-Fano 编码编码方法方法 。Shannon-FanoShannon-Fano 编码编码大多数信息的表达都存在着一定的冗余度，通过采用一定大多数信息的表达都存在着一定的冗余度，通过采用一定的模型和编码方法，可以降低这种冗余度。的模型和编码方法，可以降低这种冗余度。1.4 数据压缩技术的历史发展数据压缩技术的历史发展52n 60 年代、年代、70 年代乃至年代乃至

33、80 年代的早期，数据压缩领年代的早期，数据压缩领域几乎一直被域几乎一直被 Huffman 编码及其分支所垄断。编码及其分支所垄断。 n UNIX 系统上一个压缩程序系统上一个压缩程序 COMPACT 就是就是 Huffman 0 阶自适应编码的具体实现。阶自适应编码的具体实现。80 年代初，年代初，Huffman 编码编码又在又在 DOS 系统中实现，其代表程序叫系统中实现，其代表程序叫 SQ。 n 1952年年D.A.Huffman 第一次发表了他的论文第一次发表了他的论文“最小冗余度代码的构造方法最小冗余度代码的构造方法”(A Method for the Construction of

34、 Minimum Redundancy Codes)。 Huffman Huffman 编码编码53n 80年代，数学家们从新的角度入手，遵循年代，数学家们从新的角度入手，遵循 Huffman 编码的主导思想，设计出另一种更为精确，更能接近信编码的主导思想，设计出另一种更为精确，更能接近信息论中息论中“熵熵”极限的编码方法极限的编码方法算术编码。算术编码。 算术编码得到的压缩效果可以最大地减小信息的冗余算术编码得到的压缩效果可以最大地减小信息的冗余度，用最少量的符号精确表达原始信息内容。算术编度，用最少量的符号精确表达原始信息内容。算术编码虽然可以得到最好的压缩效果，但却要消耗也许几码虽然可以

35、得到最好的压缩效果，但却要消耗也许几十倍的计算时间。十倍的计算时间。 算术算术编码编码54能不能既在压缩效果上超越能不能既在压缩效果上超越 Huffman，又不增加，又不增加程序对系统资源和时间的需求呢？程序对系统资源和时间的需求呢？ n 1977年之前，数据压缩的研究工作主要集中于熵、年之前，数据压缩的研究工作主要集中于熵、字符和单词频率以及统计模型等方面，字符和单词频率以及统计模型等方面， n 1977年，以色列人年，以色列人 Jacob Ziv 和和 Abraham Lempel 发表了论文发表了论文“顺序数据压缩的一个通用算法顺序数据压缩的一个通用算法”(A Universal Alg

36、orithm for Sequential Data Compression)。字典式字典式编码编码55字典式编码不但在压缩效果上大大超过了字典式编码不但在压缩效果上大大超过了Huffman，而且，对于算法的实现，其压缩和解压缩的速度也异而且，对于算法的实现，其压缩和解压缩的速度也异常惊人。常惊人。 n 1978年，他们发表了该论文的续篇年，他们发表了该论文的续篇“通过可变通过可变比率编码的独立序列的压缩比率编码的独立序列的压缩”(Compression of Individual Sequences via Variable-Rate Coding)。在这两篇论文中提出的两个压缩技术。在这两

37、篇论文中提出的两个压缩技术被称为被称为 LZ77 和和 LZ78 。基于这一思路的编码方。基于这一思路的编码方法被称作法被称作“字典字典”式编码。式编码。字典式字典式编码编码56n 1984年，年，Terry Welch 发表了名为发表了名为“高性能数据高性能数据压缩技术压缩技术”(A Technique for High-Performance Data Compression)的论文，实现了的论文，实现了 LZ78 算法的一算法的一个变种个变种LZW。LZW 继承了继承了 LZ77 和和 LZ78 压缩压缩效果好、速度快的优点，而且在算法描述上更容易效果好、速度快的优点，而且在算法描述上更

38、容易被人们接受，实现也比较简单。被人们接受，实现也比较简单。n 不久，不久，UNIX上出现了使用上出现了使用 LZW 算法的算法的 Compress 程序，很快成为了程序，很快成为了 UNIX 世界的压缩程序世界的压缩程序标准。紧随其后的是标准。紧随其后的是 MS-DOS环境下的环境下的ARC 程序，程序，还有象还有象 PKWare、PKARC 等仿制品。等仿制品。LZ78 和和 LZW 一时间统治了一时间统治了 UNIX 和和 DOS 两大平台。两大平台。字典式字典式编码编码57另外对于另外对于 GIF 格式，格式，GIF 格式格式可以把原始图形文件可以把原始图形文件以非常小数据量存储，可以

39、在同一个文件中存储多以非常小数据量存储，可以在同一个文件中存储多幅图像从而实现动画效果。知道幅图像从而实现动画效果。知道 GIF 中的图像使用中的图像使用什么方法压缩的吗？什么方法压缩的吗？LZW! GIF 精确地保留了原始图像的每一个精确地保留了原始图像的每一个像素信息，是无损图像压缩的代表。像素信息，是无损图像压缩的代表。当然，当然，GIF 文件中除了经过文件中除了经过 LZW 压缩的像素信息以压缩的像素信息以外，还保存有图像的各种属性信息以及图像所使用外，还保存有图像的各种属性信息以及图像所使用的调色板信息等。的调色板信息等。字典式字典式编码编码58n 80年代中期以后，人们对年代中期以

40、后，人们对 LZ77 进行了改进，随进行了改进，随之诞生了一批我们今天还在大量使用的压缩程序。之诞生了一批我们今天还在大量使用的压缩程序。 ARJ 是其中著名的例子。是其中著名的例子。LZ77 得以和得以和 LZ78、LZW 一起垄断当今的通用数据压缩领域。一起垄断当今的通用数据压缩领域。n 目前，基于字典方式的压缩已经有了一个被广泛目前，基于字典方式的压缩已经有了一个被广泛认可的标准，从古老的认可的标准，从古老的 PKZip 到现在的到现在的 WinZip，特，特别是随着别是随着 Internet 上文件传输的流行，上文件传输的流行，ZIP 格式成为格式成为了事实上的标准，没有哪一种通用的文

41、件压缩、归档了事实上的标准，没有哪一种通用的文件压缩、归档系统敢于不支持系统敢于不支持 ZIP 格式。格式。 字典式字典式编码编码59现在对声音、图像、视频等多媒体信息的压缩有两条现在对声音、图像、视频等多媒体信息的压缩有两条思路：思路： 要么采用成熟的通用数据压缩技术进行压缩；要么采用成熟的通用数据压缩技术进行压缩； 要么根据媒体信息的特性设计新的压缩方法。要么根据媒体信息的特性设计新的压缩方法。60根据媒体特性量身定制的压缩方法中，根据媒体特性量身定制的压缩方法中，游程编码游程编码(RLE: Run-Length Encoding)是最为简单、最容易被想到的一是最为简单、最容易被想到的一种

42、。大多数种。大多数计算机中产生的图像计算机中产生的图像(和现实世界的图像例如和现实世界的图像例如照片不同照片不同)都具有着大面积重复的颜色块，完全可以用一都具有着大面积重复的颜色块，完全可以用一个颜色值加一个重复次数来表示这一块图像，冗余度由个颜色值加一个重复次数来表示这一块图像，冗余度由此减小了，这就是此减小了，这就是 RLE 方法的基本思路。方法的基本思路。显然，它不适于用来压缩照片、声音等很少连续重复信息显然，它不适于用来压缩照片、声音等很少连续重复信息的数据。的数据。RLE RLE 方法最有代表性的实现有方法最有代表性的实现有 PCX PCX 和和 TargaTarga 图图形格式。形

43、格式。游程游程编码编码61只有黑白两种颜色的只有黑白两种颜色的二值图像二值图像以及只有以及只有 256 256 级灰度级灰度变化的图像变化的图像具有一些独特的地方，可以被压缩算法加具有一些独特的地方，可以被压缩算法加以利用。以利用。对于对于灰度图像灰度图像，除了著名的，除了著名的 JPEG JPEG 标准以外，一种叫标准以外，一种叫 FELICSFELICS 的算法可以实现效果非常好的无损压缩。的算法可以实现效果非常好的无损压缩。627070年代末年代末8080年代初年代初，人们逐渐意识到，对到多数灰度，人们逐渐意识到，对到多数灰度或是彩色图像乃至声音文件，没有必要忠实地保留其或是彩色图像乃至

44、声音文件，没有必要忠实地保留其所有信息，所有信息，在允许一定的精度损失的情况下，可以实在允许一定的精度损失的情况下，可以实现更为有效的压缩方法。现更为有效的压缩方法。到到8080年代末年代末，许多人已经在这一领域取得了不小的，许多人已经在这一领域取得了不小的收获，设计出了一批在压缩效果上让人惊讶不已的收获，设计出了一批在压缩效果上让人惊讶不已的声音和图像压缩算法。声音和图像压缩算法。63在此基础上，国际标准化组织在此基础上，国际标准化组织(ISO)(ISO)和和CCITTCCITT联合组成联合组成了两个委员会：了两个委员会： 静态图像联合专家小组静态图像联合专家小组( JPEG )( JPEG

45、 ) JPEG JPEG 的压缩目标是静止图像的压缩目标是静止图像( (灰度的和彩色的灰度的和彩色的) )， 动态图像联合专家小组动态图像联合专家小组( MPEG ) ( MPEG ) MPEG MPEG 的目标则是声音和视频的目标则是声音和视频他们的基本思路是完全一样的，即保留媒体信息中最有他们的基本思路是完全一样的，即保留媒体信息中最有规律、最能体现信息主要特征的数据，而略去其他不重规律、最能体现信息主要特征的数据，而略去其他不重要的数据。要的数据。64主要数据压缩标准和应用主要数据压缩标准和应用 标准化组织标准化组织 国际标准化组织（国际标准化组织（International Organ

46、ization International Organization for Standardization, for Standardization, 简称简称ISO） 是目前世界上最大、最具权威性的国际标准化专 门机构。 国际电工委员会国际电工委员会(International ElectrotechnicalInternational Electrotechnical Commission Commission，简称，简称IECIEC） 是世界上最早的国际性电工标准化机构。65 国际电信联盟的电子标准部国际电信联盟的电子标准部(International International Te

47、lecommunication UnionTelecommunication Union，简称，简称ITUITU）是联合国的一个专门机构，国际电信界最权威的标准修订组织。1972年12月, 电信标准化部、无线电通信部和电信发展部承担着ITU的实质性标准制订工作。其中，电信标准化部门由原来的国际电报电话咨询委员会（CCITT）和国际无线电咨询委员会（CCIR）的标准化部门合并而成，其主要职责是实现国际电信联盟有关电信标准化的目标，使全世界的电信标准化。66标准标准发发 布布日日 期期标标 题题应用场合应用场合H.2611990.12p 64 kbits/s的音视的音视频业务的编译码频业务的编译码

48、综合业务数字网综合业务数字网(ISDN)中的视频中的视频会议会议H.2631996.3低比特率的视频压低比特率的视频压缩编码缩编码桌面可视电话移桌面可视电话移动视频通信等动视频通信等H.263+1998.1H.263+2000.11H.264/AVC2003.5H.264/AVC视频压视频压缩标准缩标准有线电视、无线有线电视、无线视频通信、分组视频通信、分组网络视频传输、网络视频传输、IP视频会议等视频会议等H.264/AVC2004.7H.264补充扩展高补充扩展高保真压缩保真压缩JBIG1991.9二值图像的渐进压二值图像的渐进压缩编码缩编码传真等传真等67标准标准发布日期发布日期标标 题

49、题应用场合应用场合JPEG1992.10静止图像的静止图像的数字压缩编码数字压缩编码数字照相、数字照相、图像图像/视频编辑视频编辑JPEG20002000.12新一代静止新一代静止图像编码标准图像编码标准IP网、传真、电子商网、传真、电子商务、遥感图像编码务、遥感图像编码MPEG-11992.11面向数字存储的运动面向数字存储的运动图像及伴音的编码图像及伴音的编码光盘存储、家用视频、光盘存储、家用视频、视频监控视频监控MPEG-21994.11活动图像及伴音活动图像及伴音的通用编码的通用编码数字电视、数字电视、DVD、高、高清晰度电视、卫星清晰度电视、卫星电视、视频点播等电视、视频点播等MPEG-41995.5音视频对象的音视频对象的通用编码通用编码IP网、交互视频、移网、交互视频、移动通信、专业视频、动通信、专业视频、视频会议等视频会议等68ITU-GITU-G系列标准技术参数系列标准技术参数标标 准准算算 法法 类类 型型码码 率率(