第三章 多媒体数据压缩
数字化了的视频和音频信号的数据量是非常大的，一幅具有中等分辨率(640象素×480象素)，彩色(24bit/象素)数字图象的数据量约 7.37Mbit/帧，帧速率为25帧/秒，那么这种视频信号的传送速率大约为184Mbit/秒。对于音频信号，假如采样率为44.1KHz，每个采样点以16bit量化，存储10分钟二通道立体声的录音，大约需要100MB的存储空间。由此可见，高效实时地压缩视频和音频的数据量是多媒体通信中不可回避的关键技术问题。
虽然为了传输和存储的目的需要进行数据压缩，但是数据压缩是否有可能呢? 回答是肯定的。数据压缩之所以可实现，是因为原始信源数据(视频图象和音频信号)存在着很大的冗余度，比如电视图象帧内邻近象素之间空域相关性及前后帧之间的时域相关性都很大，因而可以进行数据压缩减少或消除冗余。另一方面，在多媒体应用领域中，人是主要接收者，眼睛是图象信息的接收端，耳朵是声音信息的接收端。这样就有可能利用人的视觉对于图象边缘急剧变化不敏感, 对图象的亮度信息敏感和对色彩的分辨力弱的特点，以及听觉的生理特性实现数据压缩。数据压缩技术亦称数据编码技术，从1948年Oliver 提出PCM编码理论开始，迄今已有50余年的历史。随着数字通信技术和计算机科学的发展和，编码技术日臻成熟，应用范围愈加广泛。随着多媒体通信的进一步发展，对编码技术提出了更高的要求。
按照编码压缩方法是否产生失真，可以把现有的编码压缩方法分成无失真编码和有失真编码两大类。顾名思义，前者是指解压缩以后的还原图像与原始图像完全一致；后者是指解压缩之后的还原图像与原始图像存在一定的误差。当然这种误差应该在一定范围之内，并能满足具体应用的要求。
无失真编码方法主要有熵编码、算术编码、游程编码等；有失真编码主要有预测编码、变换编码、矢量量化编码、频带分割编码方法、基于模型的编码方法等。 本章着重介绍多媒体数据压缩的基本原理以及目前常用国际标准编码压缩方法。
3.1 信源编码的基本概念
图象数据压缩的目的是在满足一定的图象质量(或称失真度)的条件下，用尽可能少的比特数来表示原始图象，以提高图象传输的效率和减少图象存储量，这在信息论中称为信源编码。信源编码可分两大类：一类是无失真编码，另一类是有失真编码。下面介绍信源编码中的一些基本概念。
3.1.1 无失真编码定理
理论分析证明，在无干扰的条件下，存在一种无失真的编码方法，使编码的平均长度L与信源的熵H(s)任意的接近，即L=H(s)+?，其中?为任意小的正数；但以H(s)为其下限，即L?H(s)。这就是香农(Shannon)无干扰编码定理。
301
香农无干扰编码定理说明，对于无失真图象编码，原始图象数据的压缩存在一个下限，即平均码组长度不能小于原始图象的熵，而理论上的最佳编码的平均码长只能无限接近原始图象的熵。这样，就可以将原始图象数据的冗余度r定义为:
r?原始图象平均码长?1
原始图象的熵 ?L?1 （3-1） H(s)H(s)1? (3-2) L1?r编码效率?可定义为 ??
冗余度接近于零或编码效率接近于1的码便称为高效码。若原始数据的平均比特率
为n，编码后的平均比特率为nd ，则压缩比C定义为
C?nnd (3-3) 根据香农无干扰编码定理，无失真编码最大可能的数据压缩比为
CM?nH(s)???nH(s) (3-4) 为了进一步弄清熵与相关性和冗余度的关系，我们讨论一下离散的独立信源的
熵和马尔可夫(Markov)信源的熵。
3.1.2 独立信源
所谓独立信源，又称为无记忆信源， 即信源中符号si的出现与信源其它符号出现与否无关，也就是说，信源中各个符号出现的概率是独立的。
设信源包括s1,s2,?,sq等q个符号，各个符号出现的概率分别对应
p(s1),p(s2),?,p(sq)，则此信源的熵为
H(s)???p(s)logp(s) （3-5）
i2ii?1qL对于自然二进制码，q?2，其中L等于二进制码组的长度。如果信源中各符号出
现概率相等，即p(si)?1/q，则该信源熵为 Hm(s)??11 log?2qi?1qq 302
?1?L ?qi?1q ?L 比特 （3-6） 由以上分析可以看出，当信源中各符号出现概率不相等时，其熵小于Hm(s)。也就是说信源中各符号出现概率相等时，其熵为最大的Hm(s)。这时该信源冗余度
r?LHm(s)?1?0，不可能压缩。只有信源中的符号出现概率不相等时，这时信源
的熵H(s)?Hm(s)?L，其冗余度r?LHm(s)?1?0，才有可能压缩。这时，可以把出现概率大的符号用较短的码字表示，把出现概率小的符号用较长的码字表示，从而使平均码长L缩短，达到数据压缩的目的。
一幅图象也相当于一个信源，图象象素的灰度级别是有限的，通常 256个等级，
相当该图象信源有 256个符号，各灰度等级出现的概率可以统计出来，即可以算出该图象的直方图，因此可以很容易地计算出该幅图象的熵，进而分析该图象可能压缩的程度。
实际的信源，不可能是纯粹独立的信源。也就是说，信源中各符号的出现可能是互相之间有关系的。例如马尔可夫信源，是指某位符号si出现的概率与其前面出现的符号有关，如果只与前面出现的一位符号有关，则称一阶马尔可夫信源，如果与前面出现的二位符号有关，则称二阶马尔可夫信源。马尔可夫信源，又称为有限记忆信源。下面我们讨论一阶马尔可夫信源。
3.1.3 一阶马尔可夫信源
一阶马尔可夫信源的熵可由下式计算
H(s)?H1?H0 （3-7） 其中H0 是把该马尔可夫信源看成独立信源时的熵，H0???p(s)logii?1q2p(si)。
H1为考虑符号s1与其前面符号si1联合出现概率p(si1,si)后的条件熵，即
H1????p(si1?1i?1qqi1,si)log2p(si1,si) （3-8）
若相邻符号之间的相关性越大，则条件熵H1越小，熵H1越接近H0，完全相关时，
H1 = H0 ，这时H(s)?0。完全无关时，H1 = 2H0 ，H(s)?H0，这时马尔可
夫信源变成独立信源。由此可见，相邻符号的相关性使得信源的熵减小，有可能进
303
行编码压缩。
3.2 熵编码
在多媒体数据压缩中，经常用到熵编码，熵编码的原理是根据符号出现概率的大小分配不同长短的码字，即对于出现概率较高的符号分配短码字，对出现概率较低的符号分配较长的码字。这样分配以后，可使平均码长减小，从而达到压缩的目的，这种熵编码，也称为哈夫曼(Huffman)编码。
假设pi 是符号si 出现的概率， ?i 是对 si的编码码长，则这种编码方式的平均码长为 L??p?ii?1qi （3-9）
我们通过实例来说明这种编码方法。
设信源符号包括S?{s1,s2,s3,s4,s5,s6}, 其出现概率分别为p1?0.4,p2?0.3，
p3?01.,p4?0.06,p5?0.06,p6?0.04。求其哈夫曼码。
哈夫曼编码方法是先将信源符号按出现概率的大小排成一列，然后把最末两个符号的概率加起来，合成一个概率。再把这个概率与其余符号的概率按大小重新排列，再把最末两个概率加起来，合成一个概率。如此进行下去，直到最后剩下两个概率为止。
以上步骤完成之后，从最后两个概率开始逐步向前进行编码，每一步只须对二个分支各赋予一个二进制码，如对概率大的赋予码元0 ，对概率小的赋予码元1。这样，本例哈夫曼编码过程如图3.1所示。
信源符号出现频率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.600.41哈夫曼码10001101000101001011S1S2S3S4S5S601}01}01}01}图3.1 哈夫曼编码过程
最后一列是形成各个符号对应的哈夫曼码。形成哈夫曼码的规则是：依次记录该符
号本身概率所赋予的码元（0或1），及其在各步概率合并后赋予的码元（0或1），顺序排列起来再反序。例如s6，本身概率0.04，所赋码元为1，第一步合并概率0.1, 所赋码元 为1，第二步合并概率0.2，所赋码元为0，第三步合并概率0.3，赋码元为１，第四步合并概率0.6，所赋码元为0，则依次编码为11010，反序后01011即为s6的哈夫曼码。同样方法可求出各符号对应的码字如图3.1中最右列所示。
304
上述6个符号的平均码长 L??p?ii?16i
?0.4?1?0.3?2?0.1?3?0.1?4?0.06?5?0.04?5 ?2.2 比特 该信源的熵 H(s)???p(s)logp(s)
i2ii?16 ?2.14 比特 编码效率 ?? 冗余度 r?H(s)?0.975 LL?1?0.02 5 H(s) 假设对该信源用自然二进制编码的话，那么每个符号需用码长为3比特，因而该哈夫曼编码的压缩比为 C?n3??1.36 nd2.2 根据无失真编码定理，该信源最大可能的数据压缩比为 CM?n3??1.4 H(s)2.14由此可见上述哈夫曼编码的压缩比很接近理论压缩比。
3.3 预测编码
预测编码是一种简单而且十分有效的数据压缩方法, 广泛应用于声音，图象等类数据的压缩。所谓预测，就是根据已经出现的数据样本对将要出现的下一个数据的大小作出估计。由于声音、图象等类数据具有严格平滑连续性，相邻采样点间数值变化往往不大，因此借助前面的若干个数据样本往往可以较准确地预测出当前样本的数值，预测的误差一般都很小，如果我们不是直接对原始数据进行编码，而是先做预测，然后仅对较小的预测误差进行编码，这样就可以减少码长，达到压缩效果，这就是预测编码的基本思想。
一个基本的预测编码系统示于图3.2。原始数据送入编码单元，与预测器输出的估值相减，得到预测误差值，经编码器编码（如哈夫曼编码）后形成码流进行传输和存储。解码是首先恢复出预测误差值，再和用与编码器相同的预测器估计出的预测值相加，从而恢复出原始数据。
305