第6讲多媒体数据压缩编码方法

第6讲多媒体数据压缩

和信息编码内容提要多媒体数据压缩基本特征和方法图像统计特性无损数据压缩编码方法有损数据压缩编码方法多媒体数据压缩基本特征和方法1.数据压缩的处理过程：编码过程：对原始数据进行压缩，便于存储和传输。解码过程：对压缩数据进行解压，恢复成可用数据。2、数据压缩技术的性能指标评价一种数据压缩技术的性能好坏有三个关键指标：压缩比、再现质量、压缩和解压的速度。此外，还要考虑压缩算法所需要的软件和硬件。压缩比：输入数据量/输出数据量再现质量：与压缩类型有关

无损压缩系统不担心图像（音频）质量；有损压缩系统压缩前后图像（音频）不完全一样，但不影响视（听）觉。压缩和解压的速度：速度越快越好动态视频15帧/s，全动态视频25帧/s和30帧/s。客观尺度：均方误差、信噪比（SNR）、峰值信噪比（PSNR）3、数据冗余的类型与压缩方法分类A:数据冗余的类型空间冗余、时间冗余、信息熵冗余、视觉冗余、听觉冗余和其他冗余B:数据压缩方法的分类根据解压后数据压缩的保真度，数据压缩技术分为无损压缩编码和有损压缩编码两大类。无损压缩编码：解压后数据与原始数据相同，无任何偏差。特点：压缩比比较低，一般在2:1～5:1。常用编码方法：行程编码（利用相关性）、霍夫曼编码和算术编码（利用概率分布）等。应用：传真机，文本文件传输等。有损压缩：解压后数据与原始数据有一定偏差，但仍可以保证一定的视听效果。

特点：压缩比最高可达100:1,压缩比越高，解压后视频、音频质量越差。

常用编码：预测编码、变换编码、矢量量化编码、分层编码、子带编码等

应用：图像、声音、动态视频的压缩。多媒体技术侧重于有损压缩，并出台了一系列的国际标准图像统计特性图像的信息量

信源符号Si概率：

符号Si的信息量：离散信源图像的信息熵无损压缩编码方法无损编码（无失真编码）：又称统计编码，包括行程编码、LZW编码、霍夫曼编码、算术编码等。

根据信息出现的概率的分布特性而进行的压缩编码。A:行程编码RLC：主要检测重复的比特或者字符序列，并用他们出现的次数取而代之，它计算信源符号出现的行程长度，然后将行程长度转换为代码。B.LZW编码

LZW（

LempelZivWelch）压缩编码是一种压缩效率较高的无损数据压缩技术。该技术取得了LZW专利，被广泛用于图像压缩领域。LZW压缩基本原理

LZW压缩的基本原理是：LZW压缩把每一个第一次出现的字符串用一个数值来编码，在还原程序中再将这个数值还成原来的字符串。例如用数值0x100代替字符串“abccddeee”这样每当出现该字符串时，都用0x100代替。把数据流中复杂的数据用简单的代码来表示，就起到了压缩的作用。并把代码和数据的对应关系建立一个转换表，又叫“字符串表”或“编码对照表”。

LZW压缩的特点

压缩过程复杂，但过程完全可逆。对于简单图像和平滑且噪音小的信号源具有较高的压缩比，并且有较高的压缩和解压缩速度。对机器硬件条件要求不高。

可压缩任何类型和格式的数据。对于任意宽度和像素位长度的图像，都具有稳定的压缩过程。常用于GIF格式的图像压缩，其平均压缩比在2：1以上，最高压缩比可达到3：1。用于文本程序等数据压缩领域，对于数据流中连续重复出现的字节和字串，LZW压缩技术具有很高的压缩比。对于可预测性不大的数据具有较好的处理效果.LZW压缩编码过程

LZW压缩过程中主要处理：输入流，即为原始图像数据流；输出流，压缩所生成的代码流；字符串表，记录代码与数据的转换关系，是压缩算法的核心。一般一个字符串表项大于255但小于512，这时我们可以使用9bit的代码。

LZW压缩程序工作时，根据内存大小开辟了两个缓冲区：当前前缀码（CurrentPrefix）缓冲区，用于存放上一次处理的代码；当前串（CurrentString）缓冲区，用于存放前缀码所代表的字符串，并把两种字符串连接在一起。

就是说，表中的第i项是由字符串<i>组成，并对应着代码值<i。假如我们有一个字母表a、b、c、d，那么初始化字符串表就是：#0=a,#1=b,#2=c,#3=d。可以看出，其中第1、2、3、4项对应着代码值分别为0、1、2、3。表的第<256>项和第<257>项分别用于清零和结束代码，以便于确定每个编码条文的开始和结束。而加入字串表的第一个多字符项是从代码值<258>位置开始的。图7-1LZW编码过程

举例：如果有一个输入的字符流abacaba。读取第1个字符a，a可以在编译表中找到，修改“前缀=a”；读取第2个字符b，这时的ab在编译表中找不到，那么添加#4=ab到编译表，同时输出前缀码（也就是a）的索引#0到编码流，修改“前缀=b”；读取第3个字符a，这时的ba在编译表中找不到，添加编译表#5=ba，输出前缀码（b）的索引#1到编码流，修改“前缀=a”；读下一个字符c，这时的ac在编译表中找不到，添加#6=ac到编译表，输出前缀码（a）的索引#0到编码流，修改“前缀=c”；读下一个字符a，这时的ca在编译表中找不到，添加#7=ca到编译表，输出前缀码（c）的索引#2到编码流，修改“前缀=a”；读下一个字符b，这时的ab可找到编译表的#4=ab，修改“前缀=ab”；读取最后一个字符a，这时的aba在编译表中找不能，添加#8=aba到编译表，输出前缀码（ab）的索引#4到编码流，修改“前缀=a”；没有数据了，输出前缀码（a）的索引#0到编码流，最后的输出结果就是：#0#1#0#2#4#0。B:霍夫曼编码霍夫曼(Huffman)在1952年提出了对统计独立信源能达到最小平均码长的编码方法。霍夫曼码通常称为最优码。

编码的基本思想：是根据信源符号出现的概率大小进行排序，出现的概率大的符号分配短码，反之分配长码。在分配代码过程中，需要建立一个n阶二叉树。编码过程如下：①对信源符号按其出现的概率进行递减排序；②将两个最小的概率相加，其和作为新符号的概率；③重复①和②，直到概率之和达到1为止；④每次合并消息时，将被合并的消息赋予1和0或者0和1；⑤寻找从每个信源符号到概率为1处的路径，记录下路径上的1和0；⑥从树根节点到叶子节点，对每个信源符导列出0、1序列。有一幅39个象素组成的灰度图像，灰度共有5级，分别用符号A、B、C、D和E表示，39个象素中出现灰度A的象素数有15个，出现灰度B的象素数有7个，出现灰度C的象素数有6个等等，如下表所示。如果用3个位表示5个等级的灰度值，也就是每个象素用3位表示，编码这幅图像总共需要117位。符号A

B

CＤＥ出现的次数15

7

6

6

5概率15/397/396/396/395/39

熵编码－建立在随机过程的统计特性基础上

S=（A，B，C，D，E）符号出现的次数(Pi)log2(1/pi)分配的代码需要位数A15(0.3846)1.38015B7(0.1795)2.4810021C6(0.1538)2.7010118D6(0.1538)2.7011018E5(0.1282)2.9611115

01ABC0110DE01这幅图像的熵为:

H（S）=(15/39)log2(39/15)+(7/39)log2(39/7)+(7/39)log2(39/7)+(6/39)log2(39/6)+(5/39)log2(39/5)

=2.1859这说明每个符号可用2.1859位表示，39个象素需用85.25位。编码中以N表示编码器输出码字的平均码长，用熵值衡量是否最佳编码，即：当N>>H（S）有冗余，不是最佳；N<H(S)，不可能；N≈H（S）（N稍大于H（S）），是最佳编码。

本例中，N稍大于H，是最佳：N=1*0.3846+3*(0.1795+0.1538+0.1538+0.1282)=2.2305总结：（1）N要稍大于H（2）保证解码唯一性，短码不构成长码前缀，编码不唯一。（3）接收端与发送端保存相同霍夫曼码表，编码效率一致。C:算术编码：算术编码是另一种最佳编码方式，它与霍夫曼编码一样，也是对出现概率较大的符号采用短码，对概率较小的符号采用长码。但是它的编码原理却与霍夫曼编码很不相同，也不局限于仅使用整数码，编码效率比霍夫曼编码高。常用于图像数据压缩标准(如JPEG，JBIG)中。基本思想：把一个信源集合表示为实数线上的0到1之间的一个区间，这个集合中的每个元素都用来压缩这个区间。信源集合的元素越多，所得到的区间就越小，当区间变小时，就需要一些更多的数位来表示这个区间。算术编码首先假设一个信源的概率模型，然后用概率来缩小表示信源的区间。二进制编码，信源符号只有两个。因此在算术编码初始阶段可预置一个大概率Pe和小概率Qe，然后对被编码比特流符号进行判断。设编码初始化子区间为[0，1]，Qe从0算起，则Pe＝1-Qe.随着被编码数据流符号的输入，子区间逐渐缩小。算术编码基本原理

基本原理:将出现概率较多的“事件”(可以是字符或字符串)，用尽可能少的位或字节来表示。算术编码是一种变长码，主要针对出现的概率高的事件序列标识的信息进行压缩。两个基本参数:符号概率和编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，间隔则决定了符号压缩后的输出。例如一个信源符号“10”可表示成[0.5,0.7]。信息越长，这个间隔就越小，一个较长的信源符号可表示成[0.514384,0.51442]，表示这一间隔所需的二进制位数就越多。也就是说，

区别于霍夫曼编码:算数编码根据信源符号估计出各个元素的概率，然后进行迭代计算;霍夫曼编码必须预先得知信源的出现概率。算术编码的过程

（1）设定编码区间的高端位h，编码区间的低端位为l，编码区间的长度为len，设fh为某个编码字符所分配区间的高端，fl为该编码字符所分配区间的低端。（2）根据有限的信源符号估算出各元素的概率和区间。（3）对于待编码元素b1，根据（2）估算出的概率和区间，计算出该元素编码后新的h和l，计算公式如下：l=l+len×fl 和h=l+len×fh得到新的区间高端、低端和区间范围len=h-l。（4）对于下一个编码元素b2，利用上述公式重新计算h、l和len。（5）重复上述过程以得到新的间隔值。迭代次数越多，区间越小，所需表示区间的数据位数越多。如果有一个二进制消息序列的输入为：10001100101101。其中第一个输入符号是10，它的编码区间范围是[0.5,0.7]。第二个符号00的编码区间范围是[0,0.1），根据计算公式：l=l+len×fl=0.5+(0.7-0.5)×0=0.5h=l+len×fh=0.5+(0.7-0.5)×0.1=0.52新的间隔就取[0.5,0.7]的第一个十分之一[0.5,0.52]。依此可得到所有新的间隔，见表7-1编码过程。消息的编码输出可以是最后一个间隔中的任意数，如从[0.5143876,0.514402]中选择一个数输出：0.5143887。在算术编码中需要注意的是：

1.的精度在64位以内，对于运算中溢出问题，可使用比例缩放方法解决。2.算术编码器对整个消息只产生一个码字，这个码字是在间隔[0,1]中的一个实数，译码器在接受到表示这个实数的所有位后才能进行译码。

3.算术编码对错误很敏感，如果有一位发生错误就会导致整个消息译错。

4.算术编码可以是静态的或者自适应的。在静态算术编码中，信源符号的概率是固定的。但事先很难的知道精确的信源概率。最有效的方法是在编码过程中估算概率，是自适应算术编码，信源符号的概率根据编码时符号出现的频繁程度动态地进行修改，也就是在编码期间估算信源符号概率建模。有损压缩编码方法有损压缩（有失真编码）：允许一定失真，压缩

比提高。利用失真函数度量失真程度。失真度量：均匀误差；绝对误差代表的编码方法：预测编码、变换编码、分析合成编码A、预测编码根据原始离散信号之间存在着一定的相关性，利用前面的一个或多个信号对下一个信号进行预测，然后对实际值和预测值的差值进行编码。ⅠPCMPCM（脉冲调制编码）是将原始模拟信号经过时间采样，然后对每一样值进行量化，作为数字信号传输。广泛应用的语音编码技术，也是数字传输的标准接口信号。主要优点：①编码方法简单，数据压缩不需要复杂的信号处理技术，无任何信号延迟：②基于对话音信号波形采样的瞬时处理，具有较高的信噪比。PCM组成原理框图差分脉冲编码的基本工作原理图

Ⅱ:DPCM编码：S(k)量化器预测器++Se(k-1)+Se(k-1)++dq(k)Sr(k)d(k)-下图是DPCM的工作示意图，其中d(k)是输入信号S(k)和预测器输出的估算值Se(k-1)之差。Se(k-1)是S(k)的预测值。Sr(k)是差分信号dq(k)与过去的样本信号的估算值求和得到。Ⅲ:ADPCM编码进一步改善量化性能和压缩数据率的方法是采用自适应量化或自适应预测。电话通信网中，32kb／sADPCM主要用于扩充现有的PCM信道传输容量，把两个30路PCM信号合并成一个2Mb／s的60路ADPCM信号。简化的ADPCM编解码器原理框图a）ADPCM编码器b）ADPCM解码器变换编码是一种有失真的编码，是对信号进行某种函数变换，将信号从一种信号空间变换到另一种信号空间，为数据压缩提供必要的基础。变换编码的三个步骤：变换、变换域采样和量化。变换原理：通过变换编码将信号从时域变换到频域，分离出低频分量和高频分量，然后通过量化，使大多数高频分量变成零值。最后经过熵编码压缩掉这些零值序列．从而达到数据压缩的目的。

——人的视觉和听觉对高频成分不敏感，如果去除图像或声音信号中的一些高频分量．对图像或声音质量的影响将是很微弱的。B、变换编码变换编码原理图

数据压缩对变换矩阵的选择有两方面要求:准确再现信源向量，即要求再现误差尽量小；尽可能除去相关性。常见的变换方法有：最佳变换编码离散傅立叶变换(DFT)编码离散余弦变换(DCT)编码最佳变换编码

K-L（Karhvnen-Loeve）变换编码，即最佳变换编码是建立在图像的统计特性的基础上的一种正交变换，也被称为特征向量变换或主分量变换。K-L变换的计算比较复杂，必须对不同的信号，先求出其协方差矩阵，然后分别计算其特征根和对应的特征向量。x向量的协方差矩阵为：对一幅离散图像数据，在信道上经M次的传送，在接收方得到M个包括噪音在内的信号源Fi(x,y)，可将这些信号源Fi(x,y)写成M个N2维的向量。然后通过向量的协方差矩阵定义Cx=E{(X-mx)(X-mx)^T}，写出x向量的协方差矩阵。其中mx=E{X}是平均值向量，E是期望值。经过K-L变换核矩阵A可得到新的对称矩阵Y=TX，其中T为变换矩阵。变换后的协方差矩阵为Cy=E{(Y-my)(Y-my)T}，如果变换矩阵为正交矩阵，必有TTT=T-1T=E，则有关系X=T-1Y=TTY。若λi是Cx矩阵的特征值，由此可以确定K-L变换的核矩阵A，它不是固定不变的。如下面的对称矩阵中，每行表示特征值λi对应的特征向量。数据压缩主要是要去除信源的相关性，而协方差矩阵能够表征相关性的统计特征。协方差矩阵主对角线上的各元素就是变量的方差，其它元素就是变量的协方差。当协方差矩阵Cy除对角线上的元素外，其余各元素均为0时，即这些元素间的相关性为0。变换后矩阵的协方差为对角矩阵，则表示最大限度地压缩数据。因此，在已知输入信号X矩阵的基础上，根据其协方差矩阵去寻找最佳的正交变换矩阵T，使得变换后的矩阵的协方差接近一个对角矩阵，是变换编码的关键所在。

FDCTIDCT图像的DCT编码：对某一8×8灰度图像像素块进行变换，编码器进行FDCT变换，输出64个DCT系数，空间频率为0的系数称为直流系数（DC）它是块中所有像素的平均值，其余63个系数称为交流系数（AC）。大多数信号集中在低频区。解码器实行IDCT重建8×8数据块。

离散余弦（DCT）变换DCT编码方法普通使用在JPEG、MPEG和H．261等标准中。音频信号压缩采用一维DCT编码，图像压缩则采用二维DCT编码。

这类编码方法突破了经典数据压缩编码理论的框架，实质上都是通过对原数据的分析，将其分解成一系列更适合于表示的“基元”或从中提取若干具有更本质意义的参数，编码仅对这些基本单元或特征参数进行。而译码时则借助于一定的规则或模型，按照一定的算法将这些基元或参数再综合成原数据的一个逼近。分为四类：量化编码、小波变换编码、分形编码、子带编码C、分析—合成编码量化编码：矢量量化编码是在图像、语音信号编码技术中研究得较多的新型量化编码方法，它不仅仅是作为量化器设计而提出的，更多的是将它作为压缩编码方法来研究的。标量量化：在传统的预测和变换编码中，首先将信号经某种映射变换变成一个数的序列，然后对其一个一个地进行标量量化编码。矢量量化：把输入数据几个一组地分成许多组，成组地量化编码，即将这些数看成一个k维矢量，然后以矢量为单位逐个矢量进