1.3 多媒体数据压缩编码技术

信息时代的重要特征是信息的数字化，数字化了的信息带来了“信息爆炸”。计算机面临的是数值、文字、语言、音乐、图形、图像、动画、视频等多种媒体承载的由模拟量转化成数字量信息的吞吐、存储和传输的问题。数字化了的视频、音频和多维的虚拟现实场景数据量大得惊人。

【案例1.1】数字化后未经压缩的视频和音频等媒体信息的数据量。

双通道立体声激光唱盘，采样频率为44.1kHz，采样精度16 bit，其一秒钟时间内的采样数据量为：44.1×1000×16×2÷8=176.4KB。此规格一个小时的音乐文件大约是620MB。

一部1080P画质的视频文件，其分辨率是1920×1080像素，24位（bit）真彩色，如果不压缩，按每秒30帧来说，1分钟是1920×1080×24÷8×30×60约10GB，而达到4K标准的2小时影视作品，压缩前的文件数据量竟然达到50TB。

巨大数字化信息的数据量对计算机存储资源和网络带宽有很高的要求，解决的办法就是要对视频、音频的数据进行大量的压缩。播放时，传输少量被压缩的数据，接收后再对数据进行解压缩并复原。研究结果表明，选用合适的数据压缩技术，有可能将字符数据量压缩到原来的1/2左右，语音数据量压缩到原来的1/10～1/2，图像数据量压缩到原来的1/60～1/2。

多媒体数据压缩技术的目的是将原先比较庞大的多媒体信息数据以较少的数据量表示，而不影响人们对原信息的识别。多媒体数据压缩技术是多媒体技术中的核心技术，揭示了多媒体数据处理的本质，是在计算机上实现多媒体信息处理、存储和应用的前提。

1.3.1 数据压缩的基本原理

数据压缩一般由两个过程组成：一是编码过程，即将原始数据经过编码进行压缩，以便存储与传输；二是解码过程，此过程对编码数据进行解码，还原为可以使用的数据。

目前，编码理论已日趋成熟，在研究和选用编码时，主要有两个问题：一个是该编码方法能用计算机软件或集成电路芯片快速实现；另一个是一定要符合压缩/解压缩编码的国际标准。

1.压缩编码的历史

1948年，Oliver提出PCM（脉冲码调制编码）。

1952年，Huffman提出根据字符出现的概率来构造平均长度最短的异字头码字，有时称为最佳编码。

1977年，Lempel和Ziv提出基于字典的编码。

20世纪80年代初，第一代压缩编码已成熟，并进入实用阶段。

20世纪80年代中期，开始了第二代压缩编码的研究。

1989年，研制出数据压缩集成电路。

2.数据压缩技术的指标

在多媒体信息中包含大量冗余的信息，把这些冗余的信息去掉，就实现了压缩。数据压缩技术有3个重要指标。

● 一是压缩前后所需信息存储量之比要大。

● 二是实现压缩的算法要简单，压缩、解压缩速度快，尽可能地做到实时压缩和解压缩。

● 三是恢复效果要好，要尽可能完全恢复原始数据。

3.数据冗余

（1）冗余的基本概念

实际上多媒体数据之间存在着很大的相关性，利用数据之间的相关性，可以只记录它们之间的差异，而不必每次都保存它们的共同点，这样就可以减少数据文件的数据量。在信息论中，将信息存在的各种性质的多余度称为冗余。

数字化后的数据量与信息量的关系为

I=D-du

式中，I为信息量；D为数据量；du为冗余量。

由上式可以知道，传送的数据量中有一定的冗余数据信息，即信息量不等于数据量，并且信息量要小于传送的数据量。这使得数据压缩能够实现。

（2）冗余的分类

一般而言，图像、音频、视频数据中存在的数据冗余类型主要有以下几种。

1）空间冗余。同一景物表面上各采样点的颜色之间往往存在着空间连贯性，但是基于离散像素采样来表示物体颜色的方式通常没有利用景物表面颜色的这种空间连贯性，从而产生了空间冗余。空间冗余如图1-7所示。

2）时间冗余。图1-8所示是序列图像（电视图像、运动图像）表示中经常包含的冗余。

序列图像一般为位于同一时间轴区间内的一组连续画面，其中的相邻帧往往包含相同的背景和移动物体，只不过移动物体所在的空间位置略有不同，所以后一帧的数据与前一帧的数据有许多共同的地方。这些共同的地方是由于相邻帧记录了相邻时刻的同一场景画面，所以称为时间冗余。

3）信息熵冗余。信源编码时，要求分配给某个码元素的位数使编码后单位数据量等于其信源熵，即达到其压缩极限。但实际中各码元素的先验概率很难预知，位分配不能达到最佳，实际的单位数据量大于信源熵时，便存在信息熵冗余。

4）视觉冗余。事实表明，人类的视觉系统对图像场的敏感性是非均匀和非线性的。然而，在记录原始的图像数据时，通常假定视觉系统是线性和均匀的，对视觉敏感和不敏感的部分同等对待，从而产生了比理想编码（即把视觉敏感和不敏感的部分区分开来编码）更多的数据，这就是视觉冗余。

5）听觉冗余。人耳对不同频率的声音的敏感性是不同的，并不能察觉所有频率的变化，对某些频率不必特别关注，因此存在听觉冗余。

6）结构冗余。在有些图像的纹理区，图像的像素值存在着明显的分布模式，例如，方格状的地板图案等，即可称为结构冗余，如图1-9所示。

7）知识冗余。有些图像的理解与某些知识有相当大的相关性。例如，人脸的图像有固定的结构，即嘴的上方有鼻子，鼻子的上方有眼睛，鼻子位于脸的中线上等。这类规律性的结构可由先验知识和背景知识得到，称此类冗余为知识冗余。

根据已有的知识，对某些图像中所包含的物体，可以构造其基本模型，并创建对应各种特征的图像库，使图像的存储只需要保存一些特征参数，从而可以大大减少数据量。知识冗余是模型编码主要利用的特性。

【案例1.2】对字符串“aa bb cccc dddd eeeeeeee”进行编码。

上述字符串的每一个字符，在ASCII码表中都可以查到，每一个字符对应一个8位二进制码，存储时占用1B。字符与其ASCII编码的对应关系见表1-1。

可以采取以下几种编码方式。

1）方式1：ASCII码直接编码。对每一个字符直接写出其ASCII编码，分别如下。

01100001 01100001 00100000 01100010 01100010…

上述字符串的编码总长度为：24（字符个数）×8（每个字符的编码长度）=192bit。

2）方式2：等长压缩编码。取每一个字符ASCII码的后3位进行观察，可以看出它们各不相同（即可以通过这3位唯一识别），如只取每个字符的后3位直接编码，则新的码字序列可写为

001 001 000 010 010…

编码总长度为：24（字符个数）×3（每个字符的编码长度）=72（bit），数据压缩比为37.5%。

3）方式3：不等长编码。查看字符串中不同字符出现的概率并对其重新定义一个编码见表1-2。

则其编码的总长度为：8×1+4×3×3+2×4×2=60（bit），数据压缩比达到31.2%。

与之对应，数据经过压缩编码后，如果要解开压缩的数据，则可采取相应的解压缩方法得到（如查编码表）。对于等长压缩编码方式来说，解压缩过程比较简单，只要从压缩编码中取出n bit，就可以得到对应的一个原始字符；而对于不等长编码来说，解压缩过程相对复杂一些。

1.3.2 数据压缩方法

数据压缩的核心是计算方法，不同的计算方法，产生不同形式的压缩编码，以解决不同数据的存储与传送问题。数据冗余类型和数据压缩算法是对应的，一般根据不同的冗余类型采用不同的编码形式，再采用特定的技术手段和软硬件，以实现数据压缩。

根据解码后数据是否能够完全无丢失地恢复原始数据，将压缩方法分为无损压缩和有损压缩两大类，如图1-10所示。

● 无损压缩：无损压缩方法利用数据的编码冗余进行压缩，保证在数据压缩中不引入任何误差，在还原过程中可完全恢复原始数据，多媒体信息没有任何损耗或失真。典型算法有行程编码、哈夫曼编码、算术编码、LZW编码等。

● 有损压缩：有损压缩方法利用了人类视觉对图像中的某些频率成分不敏感的特性，采用一些高效的有限失真数据压缩算法，允许压缩过程中损失一定的信息，大幅度减少多媒体中的冗余信息，虽然不能完全恢复原始数据，但是所损失的部分对理解原始图像的影响较小，却换来了大得多的压缩比，例如预测编码、变换编码等。在通常情况下，数据压缩比越高，信息的损耗或失真也越大，这就需要根据实际情况找出一个较佳的平衡点。

1.常用无损压缩编码

（1）哈夫曼编码

哈夫曼编码（Huffman Coding）是一种用于无损压缩的熵编码（权编码）算法。在计算机资料处理中，哈夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估源符号出现概率的方法得到的，出现概率高的字母使用较短的编码，反之出现概率低的字母则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

例如，在英文中，e的出现概率最高，而z出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用1 bit来表示，而z则可能用25 bit（不是26 bit）来表示。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8bit。两者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。

哈夫曼编码过程如下。

① 将信源符号按概率递减顺序排列。

② 把两个最小的概率加起来作为新符号的概率。

③ 重复①和②，直到概率和达到1为止。

④ 在每次合并消息时，将被合并的消息赋予1和0或赋予0和1。

⑤ 寻找从每一信源符号到概率为1的路径，记录下路径上的1和0。

⑥ 对每一符号写出从码树的根结点到终结点的1、0序列。

例如，信源符号有集合{X1，X2，X3，X4，X5，X6，X7，X8}，对应的概率为{0.40，0.18，0.10，0.10，0.07，0.06，0.05，0.04}，采用哈夫曼编码的过程如图1-11所示。

哈夫曼编码的特点如下。

● 哈夫曼编码字长参差不齐，硬件实现困难。因此译码时间较长，使得哈夫曼编码的压缩与还原相当费时。

● 哈夫曼编码对不同信源的编码效率是不同的。在信源概率分布很不均匀时效率高，所以当信源概率比较均匀时，不用哈夫曼编码。

● 对信源进行编码后，形成对应的信源符号编码表；在解码时，必须参照此编码表才能正确译码。

● 为保证解码的唯一性，短码字不构成长码字的前缀。

● 由于“0”与“1”的指定是任意的，故由上述过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能。

（2）算术编码

算术编码方法的原理是将被编码的信息表示成实数0和1之间的一个间隔。信息编码越长表示它的间隙就越小，表示这一间隙所需的二进制位就越多。大概率符号出现的概率越大对应于区间越宽，可用较短码字表示；小概率符号出现概率越小区间越窄，可用较长码字表示。

算术编码的工作原理：在给定符号集和符号概率的情况下，算术编码可以给出接近最优的编码结果。使用算术编码的压缩算法通常先要对输入符号的概率进行估计，再编码。这个估计越准，编码结果就越接近最优的结果。

算术编码的特点如下。

● 算术编码有基于概率统计的固定模式，也有相对灵活的自适应模式，自适应模式适用于不进行概率统计的场合。

● 算术编码是一种对错误很敏感的编码方法，如果有一位发生错误就导致整个消息译错。

● 当信号源符号的出现概率接近时，算术编码的效率高于哈夫曼编码。

● 算术编码的实现比哈夫曼编码复杂，但在图像测试中表明，算术编码效率比哈夫曼编码的效率高5%左右。

（3）行程编码

行程编码（run-length encoding，RLE）又称游长编码、变动长度编码法（run coding），它的原理是通过检测统计数据流中重复的位或字符序列，并用它们出现的次数和每次出现的个数形成新的代码，从而达到数据压缩的目的。行程编码是一种简单的非破坏性资料压缩法，加压缩和解压缩都非常快。假定有一幅灰度图像，其第n行的像素值如图1-12所示，一共有70（7+5+45+13）位。若选用行程编码方法对其进行编码，得到的代码为7051458131共10位，压缩比为7∶1。即原来要用70位（bit）存储空间才能表示的信息，只要10位就可以表示清楚了。

行程编码的特点如下。

● 压缩比的大小取决于图像本身的特点。如果图像中具有相同颜色的图像块越大、数目越多，则压缩比就越高；反之，压缩比就越低。

● 连续精确的编码。如果其中一位符号发生错误，就影响整个编码序列，使行程编码无法还原。在实际中，常采用同步措施来限制错误的作用范围。

2.常用有损压缩编码

有损压缩广泛应用于语音、图像和视频数据的压缩。常见的声音、图像、视频压缩基本都是有损的。

（1）预测编码

预测编码（Predictive coding）是根据离散信号之间存在着一定关联性的特点，利用前面一个或多个信号预测下一个信号，然后对实际值和预测值的差（预测误差）进行编码。如果预测比较准确，误差就会很小，在同等精度要求的条件下，就可以用比较少的位进行编码，达到压缩数据的目的。

预测编码中典型的压缩方法有脉冲编码调制PCM、差分脉冲编码调制DPCM、自适应差分脉冲编码调制ADPCM等，它们较适合于声音、图像数据的压缩，因为这些数据由采样得到，相邻的样本值之间的差相差不会很大，可以用较少的位来表示。

1）PCM编码。脉冲编码调制（Pulse Code Modulation，PCM）是概念上最简单、理论上最完善、最早研制成功、使用最为广泛的编码系统，但也是数据量最大的编码系统。它的输入是模拟信号，首先经过时间采样，然后对每一样值都进行量化，作为数字信号输出。

量化有多种方法，最简单的是只应用于数值，称为标量量化。另一种是对矢量（又称向量）量化。标量量化可归纳为两类：一类为均匀量化；另一类为非均匀量化。理论上，标量量化也是矢量量化的一种特殊形式。采用的量化方法不同，量化后的数据量也就不同。因此，可以说量化也是一种压缩数据的方法。

① 均匀量化。如果采用相等的量化间隔处理采样得到的信号值，那么这种量化称为均匀量化。均匀量化就是采用相同的“等分尺”来度量采样得到的值，也称为线性量化，如图1-13所示。

② 非均匀量化。用均匀量化方法量化输入信号时，无论对大的输入信号还是小的输入信号一律都采用相同的量化间隔。为了适应幅度大的输入信号，同时又满足精度要求，就需要增加量化间隔，这将导致样本位数增加。但是，有些信号（例如语音信号），大信号出现的机会并不多，增加的样本位数就没有充分利用。为了克服这个不足，就出现了非均匀量化的方法，这种方法也叫作非线性量化，如图1-14所示。非线性量化的基本想法是，对输入信号进行量化时，大的输入信号采用大的量化间隔，小的输入信号采用小的量化间隔，这样就可以在满足精度要求的情况下用较少的位数来表示。量化数据还原时，采用相同的规则。

2）DPCM编码。模拟信号数字化处理中，就语音信号而言，经常存在变化较为平缓的局部时段；而活动图像（Video）的前后画面（帧）之间也有很大的相同性。在这些情况下，抽样样本序列的相邻样本间，显现出一定或较大相关性，即相邻样本间的变化比整个信号进程中的变化要小。当利用PCM编码时，这些相邻样本很可能在一个量化级，或只差1、2个量化级，这样的PCM码序列，就产生了“冗余”信息。如果设法在编码前就去掉这些相关性很强的冗余，则可进行更为有效的信息传输。

在PCM系统中，原始的模拟信号经过采样后得到的每一个样值都被量化成为数字信号。为了压缩数据，可以不对每一个样值都进行量化，而是预测下一个样值，并量化实际值与预测值之间的差值，这就是差分脉冲编码调制DPCM。1952年贝尔（Bell）实验室的C. C. Cutler取得了差分脉冲编码调制系统的专利，奠定了预测编码系统的基础。

为实现DPCM目标，应当具有一定的“预测”能力，或至少能在编码本位样本时估计到下一样本是否与本位样值有所差别，或没有什么不同，如果能做到这种近似估计，就相当于在一个样本编码前大体“知道”了该样本值。

（2）变换编码

变换编码也称转换编码，指欲编码的数值经过一种数学转换后映射至另一值域后再进行编码处理。常用于音频信号编码和图像/视频信号编码。变换编码经常与量化一起使用，进行有损数据压缩。

下面以图像信号为例说明变换编码过程。此方法不是直接对原图像信号压缩编码，而是首先将图像信号进行某种函数变换，从一种信号（空间）映射到另一个域中，产生一组变换系数，然后对这些系数量化、编码、传输。在空间上具有强相关性的信号，反映在频域上是某些特定的区域内能量常常被集中在一起，或是变换系数矩阵的分布具有规律性。可利用这些规律，在不同的频域上分配不同的量化位数，从而达到压缩数据的目的。模拟图像经采样后，成为离散化的亮度值。假如把整幅图像一次进行变换，则运算比较复杂，所需时间也较长。通常把图像在水平方向和垂直方向上分成若干子区，以子区为单位进行变换。每个子区通常有8×8个像素，每个子区的全部像素值构成一个空间域矩阵。

还有一个例子是彩色电视机。由于人眼对亮度的敏感性远远大于对色度的敏感性，所以将最初的基于RGB颜色空间的色彩转换到YCbCr空间，并利用较低的分辨率来表示色差（Cb和Cr）信号（也属于某种量化）。这使得彩色电视机可以使用与黑白电视机相同的约6MB的带宽来传送，而人眼感觉不到太大差别。实际上一般的彩色电视机的亮度分辨率约为350扫描线，而Cb信号约为50扫描线，Cr信号约为150扫描线。复杂的人眼系统能够在这样的基础上重建完整的彩色图像。

在视频和音频信号数字化后，变换编码就更常用了。从最常见的JPEG静止图像压缩标准到MPEG等运动图像压缩标准，都使用了变换编码。最常用的变换是离散余弦变换，其次还有小波变换、Hadamard变换等。离散余弦变换在性能上接近K-L变换（Karhunen-Loève变换），能够很好地实现能量集中，应用于几乎所有的视频压缩标准中。

3.有损压缩编码的优点与不足

有损压缩方法的一个优点就是在有些情况下能够获得比任何已知无损压缩方法小得多的文件大小，同时又能满足系统的需要。当用户得到有损压缩文件时，为了节省下载时间，解压文件与原始文件在数据位的层面上可能会大相径庭，但是从实用角度来说，人耳或者人眼并不能分辨出两者之间的区别。有损视频编解码总能达到比音频或者静态图像好得多的压缩比。音频能够在没有察觉到质量下降的情况下实现10∶1的压缩比，视频能够在稍微观察到质量下降的情况下实现如300∶1的压缩比。

有损压缩图像的特点是保持颜色的逐渐变化，删除图像中颜色的突然变化。生物学中的大量实验证明，人类大脑会利用与附近最接近的颜色来填补所丢失的颜色。例如，对于蓝色天空背景上的一朵白云，有损压缩的方法就是删除图像中景物边缘的某些颜色部分。当在屏幕上看这幅图时，大脑会利用在景物上看到的颜色填补所丢失的颜色部分。利用有损压缩技术，某些数据被有意地删除了，而被删除的数据也不再恢复。

有损静态图像压缩通常能够得到原始数据大小的1/10，是会影响图像质量的，尤其是在仔细观察时，质量下降更加明显。另外，使用了有损压缩的图像仅在屏幕上显示，可能对图像质量影响不太大，至少对于人类眼睛的识别程度来说区别不大。但是，如果要把一幅经过有损压缩技术处理的图像用高分辨率打印机打印出来，图像就感觉有明显的受损痕迹。