多媒体数据压缩的基本技术.ppt

第三讲 多媒体数据压缩的基本技术（1）,Outline多媒体数据压缩的理论依据量化标量量化矢量量化预测编码 差分脉冲编码调制（DPCM）自适应差分脉码调制（ADPCM）,压缩的必要性,AUDIO,VIDEO,数据压缩可分为两类：无损压缩有损压缩无损压缩是指压缩后的数据进行重构（还原，解压缩），重构后的数据与原来的数据完全相同。有损压缩是指压缩后的数据进行重构，重构的数据与原来的数据有所不同，但不影响人对原始资料表达信息的理解。,多媒体数据压缩的理论依据,信息论 现在科学领域中的一个重要分支 Shannon所创立的信息论对数据压缩有极为重要的指导意义 给出了数据压缩的理论极限 指明了数据压缩的技术途径 为通信技术的发展奠定了理论基础,两个基本概念：熵和信源熵,Entropy(熵)的概念：(1)熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，数学上就是概率越小。(2)某个事件的信息量用 Ii=-log2Pi 表示，其中Pi为第 i 个事件的概率,信源熵的定义,其中 P i 是符号 S i 在 S 中出现的概率，,表示包含在 Si 的信息量，也就是编码 Si 所需要的位数,例如，一幅用256级灰度表示的图像，如果每一个象素点灰度的概率均为 Pi=1/256，编码每一个象素点就需要8位。,无损编码定理,离散信源X无损编码所能达到的最小速率不能低于该信源的信源熵，即：,信源编码定理（有损编码定理）,对于给定的信源，在允许一定的失真D情况下，存在一率失真函数R(D)，当编码速率R不低于R(D)时，编码失真能够不大于D。R(D)一般不容易计算 该定理没有给出编码方法,熵编码（保熵编码、无损压缩）,定长编码香农-范诺(Shannon-Fano)编码霍夫曼编码 算术编码Ziv-Lempel编码（70年代末J.Ziv和A.Lempel）行程编码（Run Length Encoding，RLE）,举例说明：,有一幅40个象素组成的灰度图像，灰度共有5级，分别用符号A、B、C、D和E表示，40个象素中出现灰度A的象素数有15个，出现灰度B的象素数有7个，出现灰度C的象素数有7个等等，如右边所示。如果用3个位表示5个等级的灰度值（定长编码），也就是每个象素用3位表示，编码这幅图像总共需要120位。,就是说每个符号用2.196位表示，40个象素需用87.84位,按照信息论理论，这幅图像的熵为:,香农-范诺(Shannon-Fano)编码,按照符号出现的频度或概率排序，然后使用递归方法分成两个部分，每一部分具有近似相同的次数。Shannon(1948年)和Fano(1949年)最早阐述和实现这种编码，因此被称为香农-范诺(Shannon-Fano)算法。这种方法采用从上到下的方法进行编码。,香农-范诺编码举例,上例按照香农范诺算法的编码结果,编码后的位数 30 14 14 18 15 91（位）,霍夫曼编码,霍夫曼(Huffman)在1952年提出了一种编码方法，是从下到上的编码方法。基本思想是：对于出现概率较大的符号取较短的码长，而对概率较小的符号取较长的码长。是一种变长码，霍夫曼码通常被称为最优码,仍以上一个例子说明它的编码步骤：,1.初始化，根据符号概率的大小按由大到小顺序对符号进行排序2.把概率最小的两个符号组成一个节点，D和E组成节点P1 3.重复步骤2，得到节点P2、P3和P4，形成一棵“树”，其中的P4称为根节点 4.从根节点P4开始到相应于每个符号的“树叶”，从上到下标上“0”(上枝)或者“1”(下枝)，至于哪个为“1”哪个为“0”则无关紧要，最后的结果仅仅是分配的代码不同，而代码的平均长度是相同的。5.从根节点P4开始顺着树枝到每个叶子分别写出每个符号的代码,上例按照霍夫曼编码的结果（总共90位）,霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。例如，码串中的第1位为0，那末肯定是符号A，因为表示其他符号的代码没有一个是以0开始的，因此下一位就表示下一个符号代码的第1位。同样，如果出现“110”，那么它就代表符号D。如果事先编写出一本解释各种代码意义的“词典”，即码簿，那么就可以根据码簿一个码一个码地依次进行译码。,采用霍夫曼编码时需要注意的问题：,霍夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，哪怕是1位出现错误，不但这个码本身译错，更糟糕的是一错一大串，全乱了套，这种现象称为错误传播(error propagation)。计算机对这种错误是无能为力的，说不出错在哪里，更谈不上去纠正它。霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。,量化,量化是将具有连续幅度值的输入信号转换到只有有限个幅度值的输出信号的过程。标量量化均匀量化非均匀量化对数量化自适应量化矢量量化,标量量化,标量量化对信号的每个样点分别量化 连续信号的量化过程是将给定的连续信号幅度值x变成 有限个离散幅度值集合中的一个值y的过程数学描述：对取值连续的无限集合x，通过变换Q映射到一个只有L个离散值集合yk,k=1,2,L上,量化器 Q 输入 x 落入:,时,量化器输出为 yk,即:,其中 xk 称作分层电平或判决电平，yk 称作量化电平或重建电平。共有L1个分层电平和L个量化电平，要用 R 比特表示。其中：,输入输出特性曲线（量化器量化特性）,量化误差（量化噪声）,对于确定信号x，q也是确定信号；对于语音、图象等随机信号，q也是随机信号。设x的概率分布密度函数是px(x)，q的概率分布密度为pq(x)，则q的均方值为：,量化误差的方差同 px(x)、xk、yk及L都有关。那么问题就转化成为在给定px(x)和L的前提下，如何确定xk、yk，使量化误差功率（方差）最小？,1均匀量化,各量化区间相等,设量化器量化范围是-V到+V，则,量化电平取各量化区间中点,在这里我们只讨论输入信号幅度受限情况：,量化误差:,当L足够大,即足够小，近似有,为均匀分布，类似白噪声，也称颗粒噪声,只同L，V有关，同信号幅度概率分布及输入功率都无关,定义：,用分贝表示：,量化器每增加一个比特，SNR提高约6db,SNR与2x有关，即与信号大小和幅度概率分布有关,临界过载时SNR达最大值,均匀分布信号：,正弦信号：临界过载时,语音为非平稳随机信号，电话语音电平变化超过40db。对小信号电平输入，SNR应保证约2030db，即最大SNR需6070db，均匀量化器要1113比特。,2非均匀量化,均匀量化简单、易实现，但量化器特性曲线同输入信号幅度概率密度函数不匹配，采用非均匀量化可解决此问题，使量化效果更好。给定信号幅度概率分布密度，求解最佳分层电平和最佳量化电平。两种求解方法：迭代求解，大R值近似求解。,（1）最佳非均匀量化器的迭代求解方法,Lloyd 和Max提出，通常称劳依得-麦克思(Lloyd-Max)量化器，适用于L为任意值 由,为使上式达最小，分别对各分层电平和量化电平求偏导，并令其为零：,将量化噪声公式代入上两式可以得到,有：,以及：,因此有：,最佳分层电平应取两个相邻重建电平中点 最佳重建电平处于量化间隔概率质心上 一般情况下(L3)，求解需要使用迭代方法，其步骤如下所述：A 选初始值y1，由式（2）求出x2；B 根据y1，x2由式（1）求出y2；C 根据y2,x2，由式（2）求出x3。重复以上步骤，求出x2,x3,xL和y1,y2,yL。然后将xL及xL+1=代入（2）式右端求出值，看此值是否很接近已求出的yL。若不接近，则根据偏差调整y1的初值，重复以上过程，直到偏差满足给定的容差。,（2）大R值非均匀量化器近似求解,对于大R值，L足够大，可认为在每个量化间隔中，输入信号幅度概率密度近似为固定值,在该区间内，信号出现的概率为：,并有,当L值足够大，可以选V值较大，使,的概率很小，过载噪声功率可以忽略不计。,这时量化噪声方差为：,最佳量化电平应满足：,将（4）式代入上式，得：,最佳量化电平处于相邻两个分层电平中心，这是假定每一分层间隔内px(x)为均匀分布的必然结果。将上式代入（4）式可得：,总量化噪声是各量化间隔产生的量化噪声概率加权之和,2q 与分层电平有关，需进行优化。,将式（3）代入上式，得：,其中:,由于:,因此：,式中 K 为常数。以上式为约束条件，利用拉格朗日乘子法，有：,求出,代入式（5），解出可得到：,上式说明各量化间隔内产生的量化噪声功率相等时，总量化噪声功率最小。信号概率密度大的区间，量化间隔应该小些；反之，信号概率密度小的区间，量化间隔应该大些。可通过上式迭代求出各量化间隔，进而求出各分层电平。,通过引入压缩特性曲线,可以导出更方便的求解公式。,采用非线性压缩扩张的非均匀量器非线性压缩示意图,将输入非均匀分层映射成均匀分层，并满足：,当L很大时：,有：,利用式（3），得：,3对数量化,对数量化最大信噪比虽然没有最佳量化器的高，但动态范围大，可直接用于语音信号的量化。理想对数量化压缩特性为：,与输入信号概率分布无关。量化噪声方差为：,与输入信号方差成正比，这时,与输入信号的方差无关。,理想对数压缩无法实现，x0时c(x)-，将对数量化特性在x0的小信号区域进行修正。G.711采用A律和律两种压缩特性:,式中A取87.56，取255。,实际实现时压缩曲线分别用13段折线和15段折线近似。,4自适应量化,自适应量化根据输入信号短时方差，对量阶大小进行调整，使量化器与输入信号电平匹配，进一步改善量化效果。根据对短时方差估值方法来分，自适应量化可分为前向自适应量化（AQF）和后向自适应量化（AQB）。AQF估值不受量化噪声影响，延时大，要传边信息。AQB估值受量化噪声影响，延时小，不要传边信息。采用自适应量化明显提高分段信噪比。,矢量量化,矢量量化是先将 K个（K2）个采样值形成 K维空间 RK 中的一个矢量，然后将这个矢量一次进行量化。它可以大大降低数码率。矢量量化总是优于标量量化的。这是因为矢量量化有效地应用了矢量中各分量间的四种相互关联的性质：线性依赖性，非线性依赖性，概率函数的型状以及矢量数。,将NK个信号采样组成的信源序列 xj中每 K个为一组分为 N个随机矢量，构成信源空间 XX1,X2,XN(X在K维欧氏空间RK中),其中第 J个矢量可记为：,再把RK无遗漏地划分成 L=2M个互不相交的子空间R1，R2，。，RL，即满足:,在每个子空间Ri中找一个代表矢量Yi，令恢复矢量集,Y 也叫输出空间、码本或码书(Code Book)，Yi 称为码矢(Code Vector)或码字(Code Word)，Y内矢量的数目L，则叫做码本长度或码本尺寸。,当矢量量化器输入任意矢量,它首先判断Xj属于那个子空间，然后输出该子空间Ri的代表矢量,矢量量化过程就是用Yi代表Xj,即,式中Q为量化函数。,VQ编译码的全过程完成一个从 K 维欧氏空间RK到RK空间中有限子集的映射：,发端完成映射,收端完成映射,矢量量化Q则是C和D的结合,编码:,解码:,矢量量化示意图,矢量量化的比特率：,log2L:每个矢量所需要的编码比特数 K:每个矢量所包含的信号样点数K=1时,VQ退化成标量量化（SQ）,矢量量化的特点：,压缩能力强 一定产生失真,但失真易控制：X的分类越细，失真越小 可以实现每一维非整数比特量化 计算量大：每输入一个Xj，都要和L 个Yi逐一比较，搜索出畸变最小的。Xj和Yi都是K维矢量，故矢量搜索工作的计算量大。VQ是定长码,预测编码,预测编码基本思想：去处相邻样本之间的冗余度。这里说的“相邻”，包括“空间上的相邻”和“时间上的相邻”。例如，空间上的相邻指的是同一帧图像内上、下、左、右的像素之间；时间上的相邻指的是前帧、后帧图像中对应于同一空间位置上的像素。内容：差分脉冲编码调制（DPCM）自适应脉冲编码调制（APCM）自适应差分脉码调制（ADPCM）,差分脉冲编码调制（DPCM）,差分脉冲编码调制DPCM(differential pulse code modulation)是利用样本与样本之间存在的信息冗余度来进行编码的一种数据压缩技术。差分脉冲编码调制的思想是，根据过去的样本去估算(estimate)下一个样本信号的幅度大小，这个值称为预测值，然后对实际信号值与预测值之差进行量化编码，从而就减少了表示每个样本信号的位数。DPCM是对实际信号值与预测值之差进行量化编码，存储或者传送的是差值而不是幅度绝对值，这就降低了传送或存储的数据量。它能适应大范围变化的输入信号。,采用全极点预测器的DPCM原理如图所示,差值信号(余量信号、残差信号、预测误差信号)为：,量化后:,重建信号:,重建信号中的误差信号就是差值信号量化产生的量化误差信号,设,的方差分别为,那么DPCM的信噪比为：,式中,为预测增益，,是差值信号量化信噪比。,同PCM相比，DPCM通过预测使量化信噪比增加了10lgGp,（1）全极点预测器,Sp(n)由n时刻以前的N个重建语音样点线性组合得，,式中i，(i=1,N)称为线性预测系数。重建信号可写成:,两边取Z变换，有:,式中:,称做重建滤波器，是一个全极点滤波器，其系数 i可用语音信号的长时相关系数求出。定义系数矢量:,相关系数矢量,语音相关系数矩阵:,由线性预测理论，最佳线性预测系数矢量为：,可得最小预测误差为:,以上表明预测误差的平均功率比原始信号的功率要小在相同的均方量化误差下，要求较小的量化级数，传输上的数据率要低。,可证明，当预测器阶数 N时，极限最小预测误差为：,式中,是输入信号的功率谱密度。,可得极限最大预测增益为：,其中,定义为输入信号的谱平坦度，,反映了信号可预测程度。可以看出：,DPCM系统在极限情况下，产生的最小量化噪声为：,所能达到的极限最大信噪比为：,（2）其它类型预测器,DPCM系统也可以用全零点预测器或零极点混合器。,全零点预测器：预测信号由 n 时刻以前的M个量化后的差值信号样点线性组合得到，即：,重建信号为：,两边取Z变换，有:,重建滤波器是一个全零点滤波器。,对于零极点混合预测器DPCM，有：,以及：,其z变换表达式为：,重建滤波器为：,是一个零点极点混合滤波器。,自适应脉冲编码调制(APCM),自适应脉冲编码调制(adaptive pulse code modulation，APCM)是根据输入信号幅度大小来改变量化阶大小的一种波形编码技术。这种自适应可以是瞬时自适应，即量化阶的大小每隔几个样本就改变，也可以是音节自适应，即量化阶的大小在较长时间周期里发生变化。改变量化阶大小的方法有两种：前向自适应(forward adaptation)（APF）后向自适应(backward adaptation)（APB）,APF使用未量化的语音提取参数，效果好，但延时大，需要传边信息(side information)；,APB使用量化后的语音提取参数，延时小，不用传边信息，但精度会受量化噪声影响。,自适应差分脉码调制（ADPCM）,ADPCM(adaptive difference pulse code modulation)利用语音信号样点之间的相关性，并针对语音信号非平稳的特性，使用了自适应预测和自适应量化。ADPCM综合了APCM的自适应特性和DPCM系统的差分特性，是一种性能比较好的波形编码。它的核心思想是：利用自适应的思想改变量化阶的大小，即使用小的量化阶(step-size)去编码小的差值，使用大的量化阶去编码大的差值；使用过去的样本值估算下一个输入样本的预测值，使实际样本值和预测值之间的差值总是最小。,G.726 ADPCM编译码器,ADPCM是利用样本与样本之间的高度相关性和量化阶自适应来压缩数据的一种波形编码技术，ITU_T为此制定了G.726推荐标准，这个标准叫做40,32,24,16 kb/s自适应差分脉冲编码调制40,32,24,16kb/s Adaptive Differential Pulse Code Modulation(ADPCM),G.726的编解码框图：,