第二篇 压缩与编码 数字信号的压缩与编码是多媒体的核心技术和重要内容 音频信号的差分/自适应/LPC编码就是典型的压缩编码 本篇内容： 第7章 压缩与熵编码 第8章 DCT与JPEG编码 第9章 MPEG编码 第10章 H.264/AVC与H.265/HEVC编码 第11章 AVS视频编码

第7章 压缩与编码 由于多媒体信号的数据量巨大，为了节省存储空间和传输带宽，需进行压缩编码 多媒体数据的压缩方法，可以分成三大类，其中熵编码是基础，源编码是重点，而将它们二者相结合的混合编码则是各种编码标准所采用的主要方法 本章主要介绍压缩的基本概念和若干常用的熵编码算法 源编码和混合编码将在以后几章中介绍

7.1 压缩概论 本节先压缩的基本概念，包括 压缩的需要与可能 算法的特点与分类 一般的编码过程

压缩与编码 数据压缩(data compression) 与信号编码(signal coding)往往含义相同 解压缩/还原/重构(decompress) 编码(encode/coding) 解码/译码(decode) 相关学科：信息论、数学、信号处理、数据压缩、编码理论和方法

7.1.1 压缩的需要与可能 一. 压缩的需要 多媒体信号的数据量巨大，如： 7.1.1 压缩的需要与可能 一. 压缩的需要 多媒体信号的数据量巨大，如： 5分钟的CD音乐有50.47MB 一幅2千万像素的真彩图像有57.22MB 90分钟的PAL视频数字化后有203.68GB 90分钟的2K全高清视频有782.13GB 90分钟的4K超高清视频有3.05TB 为了节省存储空间和传输带宽，进行实时高质的多媒体通信，必须对多媒体数据进行压缩编码

二. 压缩的可能 多媒体数据和人类的感觉存在着各种冗余，如： 空间冗余：图像的相邻像素相关 时间冗余：相邻音频样本/视频帧相关 频率冗余：相邻的频谱值相关，人对高频信号不敏感或分辨率低 听觉冗余：人耳的低音听阈高、强纯音的频率屏蔽、相邻声音的时域屏蔽 视觉冗余：人眼对亮度变化比对色彩的变化更敏感、对高亮区的量化误差不敏感、视网膜分频道

三. 压缩的结果 音频：MP3算法（压缩10倍左右，~128kb/s）5分钟的CD音乐50.47MB→5.05MB 图像：JPEG算法（压缩10~30倍）一幅2千万像素的真彩图像57.22MB→5.72MB~1.91MB 视频：90分钟的视频压缩后的结果大小/使用4:2:0颜色子采样（每像素1.5B）

7.1.2 压缩算法的特点与分类 一．特点 用于多媒体数据的压缩方法众多，可按主要的特点分成不同类型： 1. 有/无损 2. 对称性 7.1.2 压缩算法的特点与分类 一．特点 用于多媒体数据的压缩方法众多，可按主要的特点分成不同类型： 1. 有/无损 无损压缩：能够无失真地从压缩后的数据重构，准确地还原原始数据。可用于对数据的准确性要求严格的场合。如差分编码、RLE、Huffman编码、LZW编码、算术编码 有损压缩：有失真，不能完全准确地恢复原始数据，重构的数据只是原始数据的一个近似。可用于对数据的准确性要求不高的场合。如预测编码、音感编码、分形压缩、小波压缩、JPEG/MPEG 2. 对称性 若编解码算法的复杂性/所需时间差不多，则为对称的编码方法。多数压缩算法都是对称的 不对称的一般是编码难而解码容易（如Huffman编码与分形编码）。但用于密码学的编码方法则相反，是编码容易，而解码则非常非常难

3. 帧间/内 在视频编码中会同时用到帧内与帧间的编码方法 帧内编码是指在一帧图像内独立完成的编码方法，同静态图像的编码，如JPEG 而帧间编码则需要参照前后帧才能进行编解码，并在编码过程中考虑对帧之间的时间冗余的压缩，如MPEG 4. 实时性 在有些多媒体的应用场合，需要实时处理或传输数据，编解码一般要求延时≤50ms。这需要简单/快速/高效的算法和高速/复杂的处理芯片 5. 分级处理 有些压缩算法可以同时处理不同分辨率、不同传输速率、不同质量水平的多媒体数据，如JPEG2000、MPEG-2/4

二．分类 1. 熵编码 熵编码(entropy encoding)是一类利用数据的统计信息进行压缩的无语义数据流的无损编码。如RLE、LZW、Huffman编码 2. 信源编码 （信）源编码(source coding)是一类利用信号原数据在时间域和频率域中的相关性和冗余进行压缩的有语义编码。种类繁多，可进一步分为 预测编码：利用先前和现在的数据对在时间或空间上相邻的下面或后来的数据进行预测，从而达到压缩的目的。如DM、ADPCM 变换编码：采用各种数学变换方法，将原时间域或空间域的数据变换到频率域或其他域，利用数据在变换域中的冗余或人类感觉的特征来进行压缩。如DCT、DWT 分层编码：将原数据在时空域或频率域上分成若干子区域，利用人类感觉的特征进行压缩编码，然后再合并。如子采样、子带编码 其他编码：如矢量量化、运动补偿、音感编码

3. 混合编码 混合编码(hybrid coding) = 熵编码 + 源编码 大多数压缩标准都采用混合编码的方法进行数据压缩，一般是先利用信源编码进行有损压缩，再利用熵编码做进一步的无损压缩。如H.261、H.263、JPEG、MPEG 常见编码方法

7.1.3 编码过程 一．编码准备 模数转换(A/D)： A/D 连续模拟信号 — 离散数字信号 采样/量化 7.1.3 编码过程 一．编码准备 模数转换(A/D)： A/D 连续模拟信号 — 离散数字信号 采样/量化 预处理：对得到的初始数字信号进行必要的处理，包括过滤、去噪、增强、修复等，以达到除去数据中的不必要成分、提高信号的信噪比、修复数据的错误等目的

二．编解码过程 A/D 预处理 压缩 多媒体信号 — 数字信号 — 处理过的数字信号 — 压缩数据 (子)采样/量化 过滤/去噪/增强/修复 源编码/熵编码 存储 解码 D/A — 压缩数据 — 重构的数字信号 — 显示/播放 传输 还原/重构 (插值)

7.2 熵编码 信息熵为信源的平均信息量（不确定性的度量） 熵编码是一类利用数据的统计信息进行压缩的无语义数据流的无损编码 7.2 熵编码 信息熵为信源的平均信息量（不确定性的度量） 熵编码是一类利用数据的统计信息进行压缩的无语义数据流的无损编码 本节在了解熵定义的基础上，讨论若干常用的熵编码算法，内容有： 7.2.1 熵 7.2.2 Shannon-Fano编码 7.2.3 Huffman编码 7.2.4 算术编码 7.2.5 RLE 7.2.6 LZW算法

7.2.1 熵 熵(entropy)本来是物理的热力学中用来度量热力学系统无序性的(热力学第二定律：孤立系统内的熵恒增)：(S为熵、Q为热量、T为绝对温度) 对可逆过程， (孤立系统) 信息熵的概念是香农(Shannon仙农)于1948年在他创建的信息论中引进的，用来度量信息中所含的信息量： 其中，H为信息熵（单位为bit），S为信源，pi为符号si在S中出现的概率

信息熵H为自信息量I： 的均值 例如，一幅用256级灰度表示的图像，如果每一个象素点灰度的概率均为pi=1/256，则 即编码每一个象素点都需要8位(I )，平均每一个象素点也需要8位(H)

7.2.2 Shannon-Fano编码 按照Shannon提出的信息理论，1948年和1949年分别由Shannon和Fano描述和实现了一种被称之为香农-范诺(Shannon-Fano)算法的编码方法，是一种变码长的符号编码 Shannon-Fano算法采用从上到下的方法进行编码：首先按照符号出现的概率排序，然后从上到下使用递归方法将符号组分成两个部分，使每一部分具有近似相同的频数，在两边分别标记0和1，最后每个符号从顶至底的0/1序列就是它的二进制编码

例子 有一幅60个象素组成的灰度图像，灰度共有5级，分别用符号A、B、C、D和E表示， 60个象素中各级灰度出现次数见下表 如果直接用二进制编码，则5个等级的灰度值需要3位表示，也就是每个象素用3位表示，编码这幅图像总共需要60 * 3 = 180位。按照香农理论，这幅图像的熵为 H = (20/60)×log2(60/20) + (10/60)×log2 (60/10) +… + (10/60) ×log2 (60/10) ≈ 2.189 这就是说平均每个符号用2.189位表示就够了，60个象素共需用131.33位，压缩比约为3 / 2.189 ≈ 1.37 : 1。

按照Shannon-Fano算法，先按照符号出现的频度或概率排序：A、D、B、E、C，然后分成次数相近左右两个部分——AD(35)与BEC(25)，并在两边分别标记0和1 然后类似地再将AB分成A(20)与B(15)、BEC分成B(10)与EC(15)，最后再把EC分成E(10)与C(5)：

Shannon-Fano算法举例表 按照这种方法进行编码得到的总位数为135，实际的压缩比为180/135 = 4/3≈1.33 : 1

7.2.3 Huffman编码 Huffman（哈夫曼/赫夫曼/霍夫曼）在1952年提出了另一种从下到上的编码方法，是一种统计最优的变码长符号编码，让最频繁出现的符号具有最短的编码 Huffman编码的过程 = 生成一棵二叉树（H树） 树中的叶节点为被编码符号及其概率 中间节点为两个概率最小符号（串）的并所构成的符号串及其概率所组成的父节点 根节点为所有符号之串及其概率1

具体编码步骤 (1) 将符号按概率从小到大顺序从左至右排列叶节点 (2) 连接两个概率最小的顶层节点来组成一个父节点，并在到左右子节点的两条连线上分别标记0和1 (3) 重复步骤2，直到得到根节点，形成一棵二叉树 (4) 从根节点开始到相应于每个符号的叶节点的0/1串，就是该符号的二进制编码 由于符号按概率大小的排列既可以从左至右、又可以从右至左，而且左右分枝哪个标记为0哪个标记为1是无关紧要的，所以最后的编码结果可能不唯一，但这仅仅是分配的代码不同，而代码的长度是相同的

Huffman编码例

压缩比也为180/135 = 4/3 ≈ 1.33 : 1

香农-范诺编码与哈夫曼编码 它们都属于不对称、无损、变码长的熵编码。码长虽然都是可变的，但却都不需要另外附加同步代码(即在译码时分割符号的特殊代码)。如果事先编写出一本解释各种代码意义的“词典”，即码簿(H表)，那么就可以根据码簿一个码一个码地依次进行译码 两个问题值得注意： 没有错误保护功能——在译码时，如果码串中有哪怕仅仅是1位出现错误，则不但这个码本身译错，而且后面的码都会跟着错。称这种现象为错误传播，计算机对这种错误也无能为力，不能知道错误出在哪里，更谈不上去纠正它 不能随机定位——因为是可变长度码，所以很难在压缩文件中直接对指定音频或图像位置的内容进行译码，这就需要在存储代码之前加以考虑 与香农-范诺编码相比，哈夫曼编码方法的编码效率一般会更高一些。尽管存在上面这些问题，但哈夫曼编码还是得到了广泛应用

H表 利用哈夫曼方法进行编解码，在编码时需要计算造H表，存储和传输时需要存储和传输H表，解码时则需要查H表 即使是计算造表，也一般只对高频符号计算编码，而对其他符号则直接编码。这种方法尤其适用于有大量不同的输入符号，但只有少数高频符号的情况

自适应哈夫曼编码 还有一种自适应哈夫曼编码(adaptive Huffman coding)，不需要存储和传输H表，而是按与编码严格一致的方法建立同样的H表 还可以利用兄弟节点的特征来加快更新H树的过程

7.2.4 算术编码 算术编码(arithmetic coding)是由Langdon于1984年提出的，从信息论上讲是与Huffman编码一样的最优变码长的熵编码。其主要优点是克服了Huffman编码必须为整数位，这与实数的概率值相差大的缺点。如在Huffman编码中，本来只需要0.1位就可以表示的符号，必须用1位来表示，结果造成10 倍的浪费。 算术编码的解决办法是，不用二进制代码来表示符号，而改用[0，1)中的一个宽度等于其出现概率的实数区间来表示一个符号，符号表中的所有符号刚好布满整个[0，1)区间（概率和为1，不重不漏）。把输入符号串（数据流）映射成[0，1)区间中的一个实数值

编码方法 符号串编码：将串中使用的符号表按原编码（如字符的ASCII编码、数字的二进制编码）从小到大顺序排列成表。计算表中每种符号si出现的概率pi，然后依次根据这些符号概率大小pi来确定其在[0, 1)期间中对应的小区间范围[xi, yi)： 其中，p0 = 0。显然，符号si所对应的小区间的宽度就是其概率pi ：

输入串编码：设串中第j个符号cj为符号表中的第i个符号si，则可根据si在符号表中所对应区间的上下限xi和yi，来计算编码区间Ij = [lj, rj)： 其中，dj = rj - lj为区间Ij的宽度，初值l0 = 0、r0 = 1、d0 = 1。显然，lj↑而dj与rj↓ 串的最后一个符号所对应区间的下限ln就是该符号串的算术编码值 例如：输入符号串为“helloworld”（10个字符），符号表含7个符号，按字母顺序排列，容易计算它们各自出现概率和所对应的区间。下表是符号表及其符号的概率和对应区间

符号表

编码过程表 编码输出为l10 = 0.214615788

解码方法 由符号表（包括符号对应的概率与区间）和实数编码ln，可以按下面的解码算法来重构输入符号串： 设v1 = ln = 码值 若vj ∈[xi, yi) → cj = si , j = 1, … , n vj+1 = (vj - xi) / pi , j = 1, … , n-1

解码过程表 重构输入符号串为v10 = “helloworld”

需注意的几个问题 (1) 由于实际计算机的浮点运算器不够长(一般为80位)，可用定长的整数寄存器低进高出来接收码串，用整数差近似实数差来表示范围，但可能会导致误差积累。 (2) 算术编码器对整个消息只产生一个码字，这个码字是在间隔[0, 1)中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码 (3) 算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错

7.2.5 RLE RLE/RLC = run length encoding/coding 行程编码或游程长度编码。 未压缩的数据：ABCCCCCCCCDEFFGGG RLE编码：AB8CDEFF3G RLE确实是一种压缩技术，而且相当直观，也非常经济 RLE所能获得的压缩比有多大，这主要是取决于图像本身的特点。如果图像中具有相同颜色的图像块越大，图像块数目越少，获得的压缩比就越高。反之，压缩比就越小 译码时按照与编码时采用的相同规则进行，还原后得到的数据与压缩前的数据完全相同。因此，RLE是无损压缩技术

RLE与图像压缩 RLE压缩编码尤其适用于计算机生成的图像，对减少图像文件的存储空间非常有效 这并不是说RLE编码方法不适用于自然图像的压缩，相反，在自然图像的压缩中（如JPEG）还真少不了RLE，只不过是不能单纯使用RLE一种编码方法，需要和其他的压缩编码技术联合应用

BMP中的RLE 在BMP文件中，对16色和256色的普通格式的位图可进行行程编码(RLE)压缩，编码由若干信息单位构成，每个信息单位有2个字节 信息单位的第一个字节一般为同一色索引的象素数，这时第二个字节对BI_RLE8为一个颜色索引(8b)，对BI_RLE4为两个颜色索引（各4b，高4位为第一个象素，低4位为第二个象素）。即

在信息单位的第一个字节为0时，第二个字节表示四类特殊意义：0——线结束、1——位图结束、2——偏移（后跟的两个字节分别表示从当前位置向右和向下偏移的象素数）、3~255——后跟的未压缩的象素（色索引）数（填充到双字节边界，不足时补0）。即

BI_RLE8例 压缩数据 解压数据 03 04 04 04 04 05 06 06 06 06 06 06 00 03 45 56 67 00 45 56 67 02 78 78 78 00 02 05 01 右移5且下移1 00 00 行结束 09 1E 1E 1E 1E 1E 1E 1E 1E 1E 1E 00 01 RLE位图结束

BI_RLE4例 压缩数据 解压数据 03 04 0 4 0 05 06 0 6 0 6 0 00 06 45 56 67 00 4 5 5 6 6 7 04 78 7 8 7 8 00 02 05 01 右移5且下移1 00 00 行结束 09 1E 1 E 1 E 1 E 1 E 1 00 01 RLE位图结束

7.2.6 LZW算法 1977年以色列Jakob Ziv和Abraham Lempel提出了一种基于词典编码的压缩算法，称为LZ77算法；1978年他们对该算法作了改进，称为LZ78；1984年Terry A.Weltch又对LZ78进行了实用性修正，因此把这种编码方法称为LZW(Lempel-Ziv Walch)算法 词典编码(dictionary encoding)的根据是数据本身包含有重复代码块这个特性。词典编码法的种类很多，归纳起来大致有两类：

第一类词典算法 其想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。这种编码概念如下图所示： 这类编码中的所有算法都是以LZ77算法为基础的

第二类词典算法 其想法是企图从输入的数据中创建一个“短语词典”，这种短语不一定具有语义，它可以是任意字符的组合 编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身 LZ78是首个第二类词典法编码，LZW压缩编码也属于这类编码

第二类词典法编码概念

LZW编码 LZW编码是围绕称为词典的转换表来完成的。这张转换表用来存放称为前缀(prefix)的字符序列，并且为每个表项分配一个码字(code word)，或者叫做序号 这张转换表实际上是把8位ASCII字符集进行扩充，增加的符号用来表示在文本或图像中出现的可变长度ASCII字符串。扩充后的代码可用9位、10位、11位、12位甚至更多的位来表示 Weltch的论文中用了12位，12位可以有4096个不同的12位代码，这就是说，转换表有4096个表项，其中256个表项用来存放已定义的单个字符，剩下3840个表项用来存放前缀 LZW编码器就是通过管理这个词典完成输入与输出之间的转换

LZW编码算法 LZW编码器的输入是字符流(charstream)，字符流可以是用8位ASCII字符组成的字符串，而输出是用n位(例如12位)表示的码字流(codestream)，码字代表单个字符或多个字符组成的字符串 LZW编码器使用了一种很实用的贪婪分析算法(greedy parsing algorithm)。每一次分析都要顺序检查来自字符流的字符串，从中分解出已经识别的最长的字符串，也就是已经在词典中出现的最长的前缀 用已知的前缀p(prefix)上加上下一个输入字符c(current character当前字符)作为该前缀的扩展字符，形成新的扩展字符串(string缀符串)：pc 这个新的缀符串是否要加到词典中，还要看词典中是否存有和它相同的缀符串。如果有，那么这个缀符串就变成前缀，继续输入新的字符，否则就把这个缀符串写到词典中生成一个新的前缀，并给一个代码

GIF图像中的LZW算法 GIF文件对图像光栅数据采用变长LZW压缩编码。图像象素按从上到下(行交叉标志位为1时除外)、从左到右的扫描顺序排列 LZW算法是1984年T.A.Welch对LZ78进行了实用性修正后提出的一种逻辑简单、速度快、硬件实现廉价的压缩算法 LZW算法是一种基于字典的编码——将变长的输入符号串映射成定长的码字——形成一本短语词典索引(串表)，利用字符出现的频率冗余度及串模式高使用率冗余度达到压缩的目的 该算法只需一遍扫描，且具有自适应的特点(从空表开始逐步生成串表，码字长从象素位数n+1逐步增加到12)，不需保存和传送串表 串表具有前缀性——若串pc(c为字符)在表中，则串p也在串表中(所以，可初始化串表为含所有单个字符的串) 匹配采用贪婪算法——每次只识别与匹配串表中最长的已有串p(输出对应的码字)、并可与下一输入字符c拼成一个新的码字pc 对串表的改进：用p的码字来代替pc中的p，则串表中的串等长；当串表已满时(一般表长为212)，可清表重来(输出清表码字) 清表码字=2n，结束码字=2n+1，故第一个可用的多字符串的码字= 2n+2

LZW压缩算法 初始化： 将所有单个(n位)字符的串放入串表ST中(实际操作时不必放入，只需空出串表的前2n项即可)，设前缀串p空； 设置码长初值：codeBits=n+1； 设置ST中当前表项的索引值next=初始码字=2n+2； 循环： 读下一输入字符c； 若c=EOF(文件结束符)，则输出p的码字，结束循环，输出结束码字2n+1； 若pc已在串表中，则p=pc，转到循环开始处； 否则，输出p的码字，将pc放入ST中的next处，next++； 令p=c，转到循环开始处； 若next的位数超过码长(>codeBits)，则codeBits++； 若串表已满(next的位数已超过最大码长12)，则清空串表，输出清表码字2n ，转到初始化开始处。

LZW还原算法 初始化 将所有单个字符的串放入串表ST中(实际操作时不必放入，只需空出串表的前2n项即可)，设前缀串old空； 串表中当前表项的索引next=2n+2； 设置码长初值： codeBits=n+1； 读首个码字(对应的单个字符)入老串old，输出该字符； 循环： 读下一码字new； 若new=结束码字2n+1 ，结束循环； 若new=清表码字2n ，则清空串表，转到初始化开始处； 若new>=next，则输出串newStr= old+old[0] (例外处理)； 若new<next，则输出串newStr； 将old+newStr[0]放入串表ST[next]中，next++； 若next的位数超过码长(>codeBits)，则codeBits++； 但若加一后的codeBits > 12，则重新让codeBits = 12； old=newStr，转到循环开始处。 其中：newStr=ST[new] (串表中索引为new的串)

LZW算法例子 被编码字符串如下表 编码过程： 译码过程：

GIF文件格式 可交换图形格式（GIF=Graphics Interchange Format），由CompuServe公司于87年起定义，现有87a与89a两个主要版本，采用变长LZW压缩算法，只支持索引色

全局标志 其中： 像素位数n=pixelBits==pixel+1=颜色位数colorBits=cr+1=1~8 颜色数N=2pixelBits=2colorBits=21~8=2/4/8/16/32/64/128/256 象素纵横比：若=0，则为1:1；若>0，则= (比值+15)/64

数据块格式1（图像块）

局部标志

其中 象素位数n=pixelBits==pixel+1=1~8 颜色数N=2pixelBits=21~8 编码长度(码长)：初始码长，一般=象素位数n。实际的初始码长=n+1

数据块格式2（扩展块）

89a版中定义的若干扩展块 GIF文件的格式还可参见课本80~81

作业 平时作业9（必做）：对下列符号进行Huffman编码，并计算压缩比。 符号及其在图像中出现的数目 平时作业10（必做）：写出串“good night”（注意当中的空格符）之算术编码的编解码过程。 平时作业11（必做）：对字符串“ababcbababaaaaaaa”进行手工LZW编解码。 平时作业12（选做）：实现BMP文件中RLE压缩算法（读写/显示）。（可与第4章的平时作业5合做在一起） 平时作业13（选做）：实现LZW算法，读写并显示（只含单个图片的）GIF文件。 大作业参考选题10：PNG图像格式的编解码（参见4.6.1之5.）。

复习思考题 多媒体数据为什么需要压缩？为什么可以压缩？ 常见编码算法MP3、JPEG、MPEG-2、H.264/AVC和H.265/HEVC的（高品质结果的）压缩比大约各是多少？ 压缩算法有哪些特点与分类？ 信息熵是什么？熵编码是什么类型的编码？ 给出Shannon-Fano编码的思路。 给出Huffman编码的思路与过程。 Shannon-Fano编码和Huffman编码有哪些共同的优缺点？哪个编码效率更高一些？ 与Huffman编码比较，算术编码有什么优势？给出算术编码的思路与过程。

RLE的英文原文与中文译文各是什么？RLE编码的思路什么？其压缩效率如何？ 什么样的BMP文件支持RLE压缩？它们是如何编码的？ LZW的含义是什么？ LZW属于什么类型的压缩算法？ GIF中的LZW算法有什么特点？它具体是如何工作的？ GIF文件格式有什么局限？其数据块有几类？数据子块的大小最大是多少？ GIF的交叉编码需要几遍扫描？如何扫？