数据压缩技术课件

第5章多媒体技术MULTIMEDIATECHNOLOGY1第5章多媒体技术MULTIMEDIATECHNOLOGY1第5

章多媒体数据压缩技术5.1数据压缩基本原理

5.1.1信息、数据与编码

5.1.2数据压缩的条件

5.1.3数据冗余5.2数据压缩算法

5.2.1数据压缩算法分类

5.2.2预测编码原理

5.2.3变换编码原理

5.2.4统计编码原理

5.2.5霍夫曼编码原理

5.2.6行程编码原理5.2.7算术编码原理

5.2.8LZW压缩编码5.3静态图像JPEG压缩编码技术

5.3.1JPEG标准的由来

5.3.2JPEG压缩算法

5.3.3无失真预测编码

5.3.4有失真DCT压缩编码5.4动态图像MPEG压缩编码技术

5.4.1基本原理

5.4.2MPEG技术标准2第5章多媒体数据压缩技术5.1数据压缩基本原理数据压缩基本原理5.1数据压缩的对象是数据。数据是信息的载体，用来记录和传送信息。真正有用的不是数据本身，而是数据所携带的信息。大的数据量并不代表含有大的信息量。而对于去掉冗余的数据对信息没有本质的影响称为压缩。●数据压缩原理3数据压缩基本原理5.1数据压缩的对象是数据。数据是信息的载体5.1.1信息、数据与编码我们了解的东西，描述它用的信息量少，不了解的东西，描述它用的信息量大。在信息论中，可以说：信息是用不确定的度量来定义的；一个消息的可能性越小，其信息含量越大；消息的可能性越大，则信息含量越小。例自然现象45.1.1信息、数据与编码我们了解的东西，描述它用的信息数据压缩基本原理5.15.1.1信息、数据与编码1．信息和熵●信息量的大小和消息有一定的关系。在数学上，消息是其出现概率的单调下降函数。信息量越大，消息的可能性越小，反之亦然。●信息量：为了从N个相等的可能事件中挑选出一个事件所需的信息度量和含量，所提问“是或否”的次数。也就是说，在N个事件中辨识特定的一个事件要询问“是或否”次数。要从256个数中选定某一个数，可以先提问“是否大于128？”，不论回答是与否，则半数的可能事件被取消。如果继续询问下去，每次询问将对应一个1bit的信息量。例5数据压缩基本原理5.15.1.1信息、数据与编码1．信息例●随着每次询问，有半数的可能事件被取消，这个过程由公式表示：可看出：对于256个数的询问只要进行8次，即可确定一个具体的数。设：从N个数中选定任意一个数x的概率为p(x)，假定选定任意一个数的概率都相等，即p(x)=1/N，则信息量为：log2256=8bit如果将信息源所有可能事件的信息量进行平均，即可得到信息的“熵”(熵是平均信息量)，信息源X的符号集为xi(i=1,2,…,N)。设：xi出现的概率为p(xi)，则信息源X的熵为：I(x)=log2N=-log21／N=-log2p(x)=I[p(x)]H(x)=P(xi)log2p(xi)∑P(xi)I[p(xi)]=-∑ni=1ni=16例●随着每次询问，有半数的可能事件被取消，这个过程由公式表示信息与数据2.信息可以用函数表示，该函数由信息论创始人C.E.Shannon香农提出，以概率论的观点对信息进行定量描述，具体的信息函数表达式为：I(ai)=-log2Pi(i=1,2,…,r)公式中，Pi(i

=1,2,…,r)是随机消息组合X{a1,a2,…,ar}中的消息ai(i

=1,2,…,r)的先验概率。Pi

可以度量ai(i

=1,2,…,r)所含的信息量。而I(ai)(i=1,2,…,r)在X的先验概率空间P{p1,p2,…,pr}中的统计平均值为信息源X的熵：信息源X的熵用来度量X中每种消息所包含的平均信息量。信息熵主要表示信息系统的有序程度，而不是热力学中系统的无序程度。H(X)=H{p1,p2,…,pr}=-Pilog2pi∑ni=17信息与数据2.信息可以用函数表示，该函数由信息论创始人C.E例2-1设信源有16种符号，其出现的概率相同，即P（Xi）=1/16。计算其平均信息熵。例8例2-1设信源有16种符号，其出现的概率相同，即P（Xi

例2-2某信源有8种符号，其出现的概率如下：例9例2-2某信源有8种符号，其出现的概率如下：例9信源中含有自然冗余度，这些冗余度既来自于信源本身的相关性，又来自于信源概率分布的不均匀性，只要找到去除相关性或改变概率分布不均匀性的手段和方法，也就找到了信息熵编码的方法。但信源所含有的平均信息量（熵）是进行无失真编码的理论的极限，只要不低于此极限，就能找到某种适宜的编码方法，去逼近信息熵，实现数据压缩。香侬理论的要点2.10信源中含有自然冗余度，这些冗余度既来自于信源本身的相关性，又多媒体信息的数据量3.1)文本

——假设屏幕显示分辨率为1024×768，字符为16×16点阵，每个字符用4个字节表示，则显示一屏字符所需要的存储空间为：（1024/16）×（768/16）×4B=12288B（约合12KB）2)图像

——假定图像显示在1024×768分辨率的屏幕上，则满屏幕像点所占用的空间为：

1024×768×log2256=768KB3)音频

——假定模拟声音频率22050Hz，其数字采样频率44100Hz，采样精度为16bit，双声道立体声模式，则1min所需数据量为：

44100Hz×2B(16bit采样精度)×2(双声道)×60s=10MB/min4)视频

——采用带宽为5MHz的PAL制视频信号，扫描速度25帧/s，样本宽度24bit，采样频率最低10MHz，则一帧数字化图像所占用的最少存储空间为：

10(采样频率)÷25(扫描速度)×24(样本宽度)=9.6Mbit(合1.2MB)11多媒体信息的数据量3.1)文本——假设屏幕显示分辨率为考虑一张640×480的全彩影像

640×480×3×8=7,372,800Bits

调制解调器(Modem)为

36Kbps

7372800/36000=204.8(sec)=3.41(min)

假设压缩算法(JPEG)的压缩率为1:12

(7372800/12)/36000=17.1(sec)

对图片压缩效果较好，但对色彩单纯的图形則效果一般不很理想。

例12考虑一张640×480的全彩影像

640×数据压缩的条件5.1.2●

数据冗余度(重复数据、可忽略数据)●

信息传输与存储的限制(压缩→传输或存储→解压缩)■44.1kHz/Stereo1.3MB■22.0kHz/Mono0.3MB■Stop重复数据可忽略数据●

人类不敏感因素(颜色、亮度、细节等)224颜色(16,777,216色)28颜色(256色)●音频不敏感因素(试听)●

颜色不敏感因素13数据压缩的条件5.1.2●数据冗余度(重复数据、可忽略数数据冗余5.1.3●

冗余基本概念●

冗余

——信息所具有的各种性质中多余的无用空间●

冗余度

——多余的无用空间的程度I=D－duI—信息量D—数据量du—冗余量，包含在D中●

信息量与冗余的关系●

冗余举例播音员——180字/分钟，2Byte一个字，360Byte

(合0.35KB/分钟)音频数据——8kHz采样×8bit×60秒=3840KBit(合480KB/分钟)14数据冗余5.1.3●冗余基本概念●冗余——信息所具有冗余分类●[1]空间冗余——规则物体的物理相关性[2]时间冗余——视频与动画画面间的相关性[3]统计冗余——具有空间冗余和时间冗余[6]视觉冗余——视觉、听觉敏感度和非线性感觉[7]知识冗余——凭借经验识别[4]结构冗余——规则纹理、相互重叠的结构表面[5]信息熵冗余——编码冗余，数据与携带的信息[8]其他冗余——上述7种以外的冗余15冗余分类●[1]空间冗余——规则物体的物理相关性[2]时冗余分类[1]空间冗余——规则物体的物理相关性[2]时间冗余——视频与动画画面间的相关性[3]统计冗余——具有空间冗余和时间冗余[6]视觉冗余——视觉、听觉敏感度和非线性感觉[7]知识冗余——凭借经验识别[4]结构冗余——规则纹理、相互重叠的结构表面[5]信息熵冗余——编码冗余，数据与携带的信息[8]其他冗余——上述7种以外的冗余●16冗余分类[1]空间冗余——规则物体的物理相关性[2]时间冗余分类[1]空间冗余——规则物体的物理相关性[2]时间冗余——视频与动画画面间的相关性[3]统计冗余——具有空间冗余和时间冗余[6]视觉冗余——视觉、听觉敏感度和非线性感觉[7]知识冗余——凭借经验识别[4]结构冗余——规则纹理、相互重叠的结构表面[5]信息熵冗余——编码冗余，数据与携带的信息[8]其他冗余——上述7种以外的冗余●17冗余分类[1]空间冗余——规则物体的物理相关性[2]时间冗余分类[1]空间冗余——规则物体的物理相关性[2]时间冗余——视频与动画画面间的相关性[3]统计冗余——具有空间冗余和时间冗余[6]视觉冗余——视觉、听觉敏感度和非线性感觉[7]知识冗余——凭借经验识别[4]结构冗余——规则纹理、相互重叠的结构表面[5]信息熵冗余——编码冗余，数据与携带的信息[8]其他冗余——上述7种以外的冗余●18冗余分类[1]空间冗余——规则物体的物理相关性[2]时间冗余分类[1]空间冗余——规则物体的物理相关性[2]时间冗余——视频与动画画面间的相关性[3]统计冗余——具有空间冗余和时间冗余[6]视觉冗余——视觉、听觉敏感度和非线性感觉[7]知识冗余——凭借经验识别[4]结构冗余——规则纹理、相互重叠的结构表面[5]信息熵冗余——编码冗余，数据与携带的信息[8]其他冗余——上述7种以外的冗余10110001110010110001110001011010101010111100010111111010●19冗余分类[1]空间冗余——规则物体的物理相关性[2]时间冗余分类[1]空间冗余——规则物体的物理相关性[2]时间冗余——视频与动画画面间的相关性[3]统计冗余——具有空间冗余和时间冗余[6]视觉冗余——视觉、听觉敏感度和非线性感觉[7]知识冗余——凭借经验识别[4]结构冗余——规则纹理、相互重叠的结构表面[5]信息熵冗余——编码冗余，数据与携带的信息[8]其他冗余——上述7种以外的冗余224色28色●20冗余分类[1]空间冗余——规则物体的物理相关性[2]时间冗余分类[1]空间冗余——规则物体的物理相关性[2]时间冗余——视频与动画画面间的相关性[3]统计冗余——具有空间冗余和时间冗余[6]视觉冗余——视觉、听觉敏感度和非线性感觉[7]知识冗余——凭借经验识别[4]结构冗余——规则纹理、相互重叠的结构表面[5]信息熵冗余——编码冗余，数据与携带的信息[8]其他冗余——上述7种以外的冗余●印度金庙泰姬陵21冗余分类[1]空间冗余——规则物体的物理相关性[2]时间冗余分类[1]空间冗余——规则物体的物理相关性[2]时间冗余——视频与动画画面间的相关性[3]统计冗余——具有空间冗余和时间冗余[6]视觉冗余——视觉、听觉敏感度和非线性感觉[7]知识冗余——凭借经验识别[4]结构冗余——规则纹理、相互重叠的结构表面[5]信息熵冗余——编码冗余，数据与携带的信息[8]其他冗余——上述7种以外的冗余声音频率文字组句色彩渐变主观意识::●22冗余分类[1]空间冗余——规则物体的物理相关性[2]时间数据压缩算法5.25.2.1数据压缩算法分类●

无损压缩编码

——压缩数据还原后，与原始数据一致，无损失。(可逆编码)霍夫曼编码行程编码算术编码……●

有损压缩编码

——压缩后再还原的数据有损失。(不可逆编码)预测编码变换编码统计编码行程编码算数编码LZW编码……压缩比：2:1～5:1压缩比：≤1：10023数据压缩算法5.25.2.1数据压缩算法分类●无损压缩视频压缩算法结构图●视频压缩无损压缩有损压缩霍夫曼编码行程编码算术编码LZW编码预测编码变换编码模型编码基于重要性混合编码DPCMADPCM运动编码DCT变换小波变换子带编码分形变换滤波子采样矢量量化H.261MPEG24视频压缩算法结构图●视频无损有损霍夫曼编码预测编码DPCMD预测编码原理5.2.2●预测编码——有损压缩编码，主要对统计冗余进行压缩。1．预测编码的基本原理用原样本值对新样本进行预测，得到新样本的预测值。接着，取新样本的实际值和预测值进行比较，二者相减得到差值，然后对差值进行编码。2．预测编码的应用预测编码用于图像的传输和存储。对于连续的多帧图像，新一帧通常保留前一帧的部分内容。首先存储当前内容，如像点、帧或线。然后与下一帧图像进行比较（预测），把不同点存储或传输，而相同点则是数据冗余，予以剔除。对于语音，就是通过预测去除语音信号时间上的相关性。例如语音中的LPC(linearPredictiveCoding，线性预测)。例25预测编码原理5.2.2●预测编码——有损压缩编码，主要变换编码原理5.2.3●变换编码(Transformcoding)

有损压缩编码，用于对统计冗余(图像数据)的压缩。●工作原理首先对时域上的信号进行函数运算，并变换到频域上，然后在频域上对变换后的信号进行编码。在频域上，信息是按照频谱的能量和频率分布进行排列的。卡胡南·劳埃夫变换离散傅里叶变换离散余弦变换WHT变换例如，声音中的频谱分析实际上是对语音波形进行了快速傅里叶变换（FFT），将时域信号变到了频域中，可以清楚地看到能量集中在哪些频率范围内。例26变换编码原理5.2.3●变换编码(Transformc5.2.4统计编码原理

统计编码

——无损压缩编码。根据消息出现的概率分布特性，在消息和码字之间确定严格的对应关系，以便准确无误地恢复数据。一般而言，图像中某些数据出现概率比较高，而另一些出现概率较低。对出现概率高的数据分配短码，对出现概率低的数据分配长码。此种方式不舍弃数据冗余，只改变编码分配的长度，因此总数据流量降低。275.2.4统计编码原理统计编码——霍夫曼编码原理5.2.5●

霍夫曼编码——无损编码。●

编码特点[1]编码长度可变，压缩与解压缩较慢。[2]硬件实现困难。[3]编码效率取决于信号源的数据出现概率。●

编码原理——出现频率高的数据编码长度短，反之亦然。[1]信号源的数据按照出现概率递减的顺序排列。[2]合并两个最小出现概率，作为新数据出现概率。[3]重复进行[1][2]，直至概率相加为1为止。[4]合并运算时，概率大者取0，概率小者取1。[5]记录概率为1处到信号源的0、1序列。28霍夫曼编码原理5.2.5●霍夫曼编码——无损编码。●设信号源为X={、a、e、I、m、t、c、h、r}。对应的概率为p={O.22、0.22、0.14、O.07、0.07、0.07、0.07、0.07、0.07},试给出该信源的霍夫曼编码方案。解：

若传送一个串字符串“Iamateacher”，共14个字符。若用ASCII传送，每个字符8位，共需112位。该字符串中有9个不同的符号，至少需要4位二进制才能表示，这样传送该字符串也要56位。若用刚计算的Huffman编码，只需要42位。霍夫曼编码举例●︺29设信号源为X={、a、e、I、m、t、c、h、r霍夫曼编码过程

●可以得到：

a的编码00e的编码111I的编码1101m的编码1100t的编码1011c的编码1010h的编码1001r的编码1000原字符串（二进制）长度：=112（14×8）位Huffman编码长度：=42位（0100111110111001011101010011000）30霍夫曼编码过程●可以得到：30行程编码原理5.2.6●行程编码（RunLengthCoding）——无损压缩编码。例一个字符串：5555557777733322221111111行程编码：(5,6)(7,5)(3,3)(2,4)(1,7)可见，行程编码的位数远远少于原始字符串的位数。●基本原理用一个符号值或串代替具有相同值的连续符号，使符号长度少于原始数据的长度。在对图像数据进行编码时，沿一定方向排列的，具有相同灰度值的像素被看成是连续符号，并用字串代替这些连续符号，可大幅度减少数据量。31行程编码原理5.2.6●行程编码（RunLengthC设有数据流“AAABBBBCCCCCDAAAAAA”，试计算该数据的行程编码。解：A重复3次，B重复4次，C重复5次，D不重复，A重复6次，RLC数据流为：“SA3SB4SC5DSA6”，其中S为指示符。总共占用13个字节，而源数据占用19个字节。有时行程编码不用指示符，重复与否相同对待，则相应的RLC为“A3B4C5D1A6”占用10个字节。例32设有数据流“AAABBBBCCCCCDAAAAAA”，试计算算术编码原理5.2.7●算术编码——无损压缩编码，属于统计编码。20世纪60年代由Elias提出，某些方面优于霍夫曼编码。因此，在JPEG标准的扩展系统中，算术编码已经取代了霍夫曼编码。●基本原理将被编码的信息表示成实数轴上0和1之间的间隔，信息越长，间隔越小，表示这一间隔所需的二进制位数就越多。●特点1)算术编码有基于概率统计的固定模式，也有相对灵活的自适应模式。2)自适应模式适用于不进行概率统计的场合。3)当信号源符号的出现概率接近时，算术编码的效率高于霍夫曼编码。4)算术编码的实现相应地比霍夫曼编码复杂，但在图像测试中表明，算术编码效率比霍夫曼编码效率高5％左右。33算术编码原理5.2.7●算术编码——无损压缩编码，属于LZW压缩编码5.2.8●LZW（LempelZivWelch）无损压缩编码，用于图像数据的压缩。LZW（LempelZivWelch）是一种字典式无损压缩编码。1977年两位以色列教授Lempel和Ziv提出了查找冗余字符和用较短的符号标记替代冗余字符的概念。1985年美国人Welch将该技术发展到实际运用阶段，命名为LZW技术。LZW把数据流中复杂的数据用简单的代码来表示，并把代码和数据的对应关系建立一个转换表（“字符串表”）。该转换表是在压缩或解压缩过程中动态生成的表,并用于压缩和解压缩过程中。LZW被广泛用于图像压缩领域。34LZW压缩编码5.2.8●LZW（LempelZivWLZW压缩编码●●

基本原理把复杂的数据用简单的代码表示，并把代码和数据的对应关系建立转换表，又叫“字符串表”。转换表记录了代码和数据的对应关系。在压缩和解压缩过程中，LZW压缩编码会生成两个完全相同的转换表，数据以严格对应的方式被压缩和还原。●

特点1)对于可预测性不大的数据效果较好，常用于GIF格式的图像压缩。2)对于数据流中连续重复出现的字节和字串，具有很高的压缩比。3)被用于文本程序等数据压缩领域。4)有很多变体，如常见的ARC、RKARC、PKZIP高效压缩程序。5)压缩和解压缩速度较快，对硬件条件要求不高。35LZW压缩编码●●基本原理把复杂的数据用简单的代码表示，并静态图像JPEG压缩编码技术5.35.3.1JPEG标准的由来1991年，联合专家组提出了ISOCD建议草案，后经过国际电子技术委员会ISO/IEC的批准，正式成为第10918号标准，并正式命名为“JPEG高质量静止图像压缩编码标准”，简称“JPEG标准”。多灰度静止图像的数字压缩编码标准计算机业内人士探寻一种压缩比大、图像质量高的压缩编码。在这种背景下,压缩标准成为急待解决的问题。1986年CCITT和ISO共同成立了JPEG联合图像专家组，从事图像压缩的工业标准和学术意义的研究、探索。提出了ISOCD建议草案、即多灰度静止图像的数字压缩编码标准。36静态图像JPEG压缩编码技术5.35.3.1JPEG标准●JPEG算法概述JPEG算法根据人眼对亮度和颜色变化比较敏感的原理，在对图像数据进行压缩时，只保存亮度和颜色变化的数据部分，而舍弃人眼不敏感的成分，以达到压缩的目的。在图像还原时，并不重新建立原始图像，而是生成类似图像，该图像保留了人眼敏感的色彩和亮度。JPEG适合于连续色调、多级灰度、彩色或黑白图像的数据压缩。37●JPEG算法概述JPEG算法根据人眼对亮度和颜色变化比较JPEG压缩算法5.3.2●适用于连续色调、多级灰度、彩色或黑白图像的数据压缩。无损压缩比：大约为4:1。有损压缩比：在10:1~100:1之间。不大于40:1时，还原的图像在色彩、清晰度、颜色分布等方面与原始图像相比，误差不大，基本上保持了原始图像的风貌。●

特点1)对图像进行帧内编码，每帧色调连续，随机存取。2)在宽范围内调节图像的压缩比和保真度，解码器可参数化。3)对图像进行压缩时，可随意选择期望的压缩比值。4)对于硬件环境要求不高，只要有一般的CPU运算速度即可。5)可运行四种编码模式：DCT顺序编码模式、DCT递增模式、无失真编码模式和分层编码模式。JPEG算法更多……38JPEG压缩算法5.3.2●适用于连续色调、多级灰度、彩色无失真预测编码5.3.3●无失真预测编码——无损压缩，压缩比一般为2:1。原始图像数据经过无失真编码器进行预测编码，然后把压缩图像数据存储在介质中或传送出去。在使用图像时，经过解码器解码，建立与原始图像一致的不失真图像。●原理预测器图像数据熵编码器码表说明解码器压缩图像数据无失真编码器还原图像数据采用了简单的线性预测编码方法，DPCM压缩算法和霍夫曼压缩算法，硬件容易实现，重新建立的图像质量与原始图像无差别。●特点39无失真预测编码5.3.3●无失真预测编码——无损压缩，有失真DCT压缩编码5.3.4●采用DCT（DiscreteCosineTransform）离散余弦变换的压缩算法。1．DCT离散余弦变换●原理源图像在输入到编码器之前，被分割成一系列顺序排列的由8×8像点构成的数据块，把原始采样数据中无符号整数转换成有符号整数，进行正变换。还原图像时，解码器输出端经过逆变换，重新建立图像。由于运算误差和系数的量化，因而重建不很精确，与源图像存在差异。2．DCT系数的量化量化依据量化表进行，量化表中的元素由开发人员根据人类视觉特性制作。量化的定义：CQ(u,v)=IntegerRound[F(u,v)/Q(u,v)]解量化是量化过程的逆运算，其公式为：CQ(u,v)=CQ(u,v)·Q(u,v)40有失真DCT压缩编码5.3.4●采用DCT（Discret有失真DCT压缩编码5.3.43．图像的质量与压缩比●采用DCT算法存在失真，但是，只要量化表中的元素更科学、更符合人类视觉敏感度，则压缩后的图像不会产生过大的视觉变化。压缩结果bit/像素图像质量的主观评价●假定某图像的像素采用8bit编码，则压缩结果和图像效果见下表。1.5~2.00.75~1.50.5~0.750.25~0.5色彩、灰阶过度、清晰度等与原始图像差别不大。图像质量良好，灰阶过度和层次略感有损失。图像质量中等，灰阶过度、层次、色彩稍差。图像质量一般，色彩和灰阶与原始图像相比有明显差别41有失真DCT压缩编码5.3.43．图像的质量与压缩比●采用动态图像MPEG压缩编码技术5.45.4.1基本原理1．动态图像压缩主要解决的问题1)正确区分静止图像和动态图像。2)提取动态图像中的活动成分。3)进行帧之间的预测，提供压缩的依据。2．帧的预测编码1)条件像素补充法

——比较两帧对应位置的像素亮度，若亮度差超过预先规定的阀值，则认为两个像素有变化，传送像素。若亮度差未超过阀值，不处理。2)运动补偿法

——跟踪画面上的活动元素，并进行向量计算，加以补偿，然后再利用帧间预测进行压缩。适用于活动元素少的可视电话和电视会议。42动态图像MPEG压缩编码技术5.45.4.1基本原理1．图像的分类3.●MPEG标准根据处理图像的性质，把图像分成以下三类：1)帧内图像（Intrapictures）

——又称“I图像”，JPEG标准按照静止图像的模式进行压缩处理。主要利用静止图像自身的相关性进行编码，实现数据压缩的目的。帧内图像的压缩比属于中度压缩，典型的压缩像素编码为2bit。2)预测图像（Predictedpictures）

——又称“P图像”，通过对最近的前一帧I图像或者P图像进行预测的“前向预测”过程，把前面图像作为预测下一帧图像的参照物，使图像编码的数据量减少。预测图像有较高的压缩比，但会增加失真。3)双向图像（Bidirestionalpictures）

——又称“B图像”，可使用前一帧图像和后一帧图像作参照物，进行双向预测。双向预测可以采用四种编码技术，即帧内图像编码、前向预测编码、后向预测编码、双向预测编码。43图像的分类3.●MPEG标准根据处理图像的性质，把图像分成MPEG技术标准5.4.2●MPEG-Ⅰ标准●

诞生于1991年，主要特点：1)以1.5Mb/s的速率传输视频信号，即压缩信号带宽为1.5Mb/s。2)以单通道64kb/s、128kb/s和192kb/s的传输速率传输音频信号。3)可通过差值运算，在352×240画面分辨率上显示活动图像。4)分三个组成部分：视频、音频和系统。5)对于帧内图像，采用二维余弦变换、自适应算术编码、行程编码、变字长编码，以及差分脉冲编码（DPCM）进行压缩。6)帧间压缩采用运动补偿预测编码和运动补偿内插编码。●允许采用多种存储介质，如CD-ROM、数字录音带、磁盘、CD-R、

CD-RW、M.O.，以及ISDN集成服务数字网络、LAN局域网络等。设计MPEG压缩算法时，要考虑随机访问、快进快退、检索、声像同步、容错、延时控制、可编辑特性以及视频窗口设置的灵活性等。44MPEG技术标准5.4.2●MPEG-Ⅰ标准●诞生于19MPEG技术标准5.4.2●MPEG-Ⅱ标准●

主要特点1)压缩信号带宽为4~15Mb/s，即信号传输速率为4~15Mb/s。2)支持NTSC制720×480画面分辨率，PAL制720×576画面分辨率，画面质量达到广播级，适用于HDTV高质量电视信号的传送与播放。3)解码器同时支持MPEG-Ⅰ和MPEG-Ⅱ两种标准。4)视频信号的传输速率为30帧/s，音频信号的质量达到CD级。5)为了在画面质量、数据量和带宽之间寻求最佳值，允许在一定范围内调整压缩比。6)最高压缩比为200:1，但由于画面中活动内容的多少和人为调整压缩比等因素的影响，大多数情况下达不到最高压缩比。7)MPEG-Ⅱ用于DVD视频信号的压缩，DVD音频信号的压缩随制式的不同而不同：PAL制采用MPEG-Ⅱ；NTSC制采用AC3压缩标准。45MPEG技术标准5.4.2●MPEG-Ⅱ标准●主要特点1第5章多媒体数据压缩技术小结●5.1数据压缩基本原理

5.1.1信息、数据与编码

5.1.2数据压缩的条件

5.1.3数据冗余5.2数据压缩算法

5.2.1数据压缩算法分类

5.2.2预测编码原理

5.2.3变换编码原理

5.2.4统计编码原理

5.2.5霍夫曼编码原理

5.2.6行程编码原理5.2.7算术编码原理

5.2.8LZW压缩编码5.3静态图像JPEG压缩编码技术

5.3.1JPEG标准的由来

5.3.2JPEG压缩算法

5.3.3无失真预测编码

5.3.4有失真DCT压缩编码5.4动态图像MPEG压缩编码技术

5.4.1基本原理

5.4.2MPEG技术标准46第5章多媒体数据压缩技术小结●5.1数据压缩基本原理●习题五5.1数据压缩的理由有哪些？5.2什么是数据冗余？5.3冗余有多少种？分别是什么？5.4无损压缩编码指的是什么？5.5数据压缩具备哪两个过程？5.6霍夫曼编码的特点是什么？5.7采用JPEG压缩格式的静态图像具有哪些主要特点？5.8动态图像压缩主要解决哪些问题？5.9MPEG-Ⅱ标准具有哪些主要特点？47●习题五5.1数据压缩的理由有哪些？47香农1948年则创立了信息论(informationtheory)。克劳德•香农在公众中并不特别知名，但他是使我们的世界能进行即时通信的少数科学家和思想家之一。他是美国科学院院士、美国工程院院士、英国皇家学会会员、美国哲学学会会员。他获得过许多荣誉和奖励。例如1949年Morris奖、1955年Ballantine奖、1962年Kelly奖、1966年的国家科学奖章、IEEE的荣誉奖章、1978年Jaquard奖、1983年Fritz奖、1985年基础科学京都奖。●香农克劳德•香农(ClaudeElwoodShannon，1916-2001)1916年4月30日诞生于美国密西根州的Petoskey。2001年2月24日，香农在马萨诸塞州Medford辞世，享年85岁。香农被信息界誉为信息论及数字通信时代的奠基人。返回48香农1948年则创立了信息论(informationtheHuffman树的定义构造Huffman树Huffman编码●Huffman(哈夫曼）编码49Huffman树的定义●Huffman(哈夫曼）编码49Huffman树也称为最优树，是一类带权路径最短的二叉树。树的带权路径长度定义为：

WPL=∑wklkk=1n

其中：

n树中叶结点的个数

wi

第i个结点的权值

li第i个结点的路径长度●Huffman树的定义50Huffman树也称为最优树，是一类带权路径最短的二叉树。以下有三棵树：WPLa=7x2+5x2+2x2+4x2=36WPLb=7x3+5x3+2x1+4x2=46

WPLc=7x1+5x2+2x3+4x3=35√事实证明按哈夫曼树构造二叉树，可得到很好的特性，应用于实际问题，可提高处理效率。（a）（b）（c）abcdabcdacbd777555222444●Huffman树举例51以下有三棵树：WPLa=WPLb=WPLc=事实证由统计规律可知，考试成绩的分布符合正态分布：-110

分数0～5960～6970～7980～8990～100比例数0.050.150.400.30.10根据正态分布规律，在60～90之间的分数占85%，而不及格和优秀是少数。●应用举例52由统计规律可知，考试成绩的分布符合正态分布：-110分判定树比较：若输入1万个数据：按A的判定过程进行操作，约需比较3.2万次而按B比较,则仅需2.2万次。a<60?a<70?a<80?a<90?不及格

及格

中等

良好

优秀YYYYNNNNa<80?a<70?a<90?a<60?不及格

优秀

良好

中等

中等

及格不及格YYYNNNNYY(A)(B)●将百分制转换成五分制53判定树比较：若输入1万个数据：a<60?a<70?a<80?构造Huffman树算法步骤：Step1将n个带权值wi（i≤n）的结点构成n棵二叉树的集合T={T1，T2，……，Tn}，每棵二叉树只有一个根结点。Step2在T中选取两个权值最小的结点作为左右子树，构成一个新的二叉树，其根结点的权值取左右子树权值之和；Step3在T中删除这两棵树，将新构成的树加入到T中；Step4重复2）、3）步的操作，直到T中只含一棵树为止，该树就是Huffman树。●构造Huffman树54构造Huffman树算法步骤：●构造Huffman树54以权值分别为7，5，2，4的结点a、b、c、d构造Huffman树。T={abcd}cdT3246bT3T26511bT26511cd2418aT2711T1618a7T1bT3T251118a7T1b511cd264（d）T={T1}（c）T={aT2}（b）T={abT3}（a）T={abcd}代入T2代入T3代入T1示例●构造Huffman树举例55以权值分别为7，5，2，4的结点a、b、c、d构造Huffm编码：用二进制数的不同组合来表示字符的方法。前缀编码：一种非等长度的编码(任一个字符的编码都不是另一个字符编码的前缀)。Huffman编码：一种非等长度的编码。以给定权值的结点构造Huffman树，按二进制前缀编码的方式构成的编码为Huffman编码。

a0b01cd011编码：a（0）

b（01）

c（011）

d（111）方法约定：1）左分支为‘0’2）右分支为‘1’3）由叶到根路径上字符组成的二进制串就是该叶结点的编码。●Huffman编码56编码：用二进制数的不同组合来表示字符的方法。Huffman编在某系统的通信联络中可能出现8种字符，其频率分别为0.05、0.29、0.07、0.08、0.14、0.23、0.03、0.11，设权值分别为{5，29，7，8，14，23，3，11}，n=8，其Huffman树为：000000011111115378142911234258100Huffman编码为：A50110B2901C70111D81111E14011F2300G31110H11010●返回Huffman编码举例57在某系统的通信联络中可能出现8种字符，其频率分别为0.05、●JPEG算法的四种编码模式1)DCT顺序编码模式——基本操作模式，也称基本系统，所有JPEG

编码解码器都必须支持基本系统，采用二维余弦变换的编码方案。2)DCT递增模式，该模式又叫累进模式。3)无失真编码模式。4)分层编码模式。⑴基线编码系统。面向大多数有损压缩的应用，采用DCT变换压缩。输入图像精度8位/像素/色，顺序模式，采用Huffman或算术编码；⑵扩展编码系统。为满足更广泛领域的应用而设置的，从低分辨率到高分辨率逐步递进传递的应用。输入图像精度12位/像素/色，累进模式，采用Huffman或算术编码；⑶独立编码系统。面向无损压缩的应用，采用无损预测压缩。输入图像精度2-16位/像素/色，顺序模式，采用Huffman或算术编码。●一个产品或系统必须包括对基线系统的支持。●JPEG算法的三种压缩系统58●JPEG算法的四种编码模式1)DCT顺序编码模式——顺序模式累进模式●顺序模式和累进模式59顺序模式累进模式●顺序模式和累进模式59有失真DCT压缩编码●采用DCT（DiscreteCosineTransform）离散余弦变换的压缩算法。1．DCT离散余弦变换●原理源图像在输入到编码器之前，被分割成一系列顺序排列的由8×8像点构成的数据块，把原始采样数据中无符号整数转换成有符号整数，进行正变换。还原图像时，解码器输出端经过逆变换，重新建立图像。由于运算误差和系数的量化，因而重建不很精确，与源图像存在差异。2．DCT系数的量化量化依据量化表进行，量化表中的元素由开发人员根据人类视觉特性制作。量化的定义：CQ(u,v)=IntegerRound[F(u,v)/Q(u,v)]解量化是量化过程的逆运算，其公式为：CQ(u,v)=CQ(u,v)·Q(u,v)●60有失真DCT压缩编码●采用DCT（DiscreteCos⒈正向离散余弦变换(ForwardDiscreteCosineTransform，FDCT)

把空间域表示的图像变换为频率域表示的图像。⒉量化DCT系数用加权函数对DCT系数进行量化，该加权函数对于人视觉系统是最佳的。⒊Huffman编码用Huffman可变字长编码器对量化系数进行编码。译码或者叫做解压缩的过程与压缩编码过程相反。

有失真压缩三个步骤

●61⒈正向离散余弦变换(ForwardDiscreteCoDCT变换是数字图像处理中的重要变换。但对于大尺寸的二维数值矩阵，若采用普通DCT变换，其花费的时间将是让人难以忍受甚至无法达到实用。解决方案，关注快速DCT变换的算法研究。目前而言，DCT变换的快速算法有以下两种方式：1．快速FFT算法。直接利用FFT来实现DCT变换的快速算法。特点是实现相对较容易，但计算过程会涉及到复数运算。由于DCT变换前后的数据都是实数，而引入复数，显然是增加了运算量，也给硬件存储提出了更高的要求。2．直接在实数域进行DCT快速变换。显然，这种方法相比于前一种而言，计算量和硬件要求都要优于前者。鉴于此，一般采用第二种方法来实现DCT变换的快速算法。DCT变换存在的问题●62DCT变换是数字图像处理中的重要变换。但对于大尺寸的二维数值DCT变换是一种实数域变换，其变换核心为实数的余弦函数。变换实质是将一个空间域上的信号，变换为一个频域上的信号。设一幅图像，或者一幅图像的某个彩色分量经过数字化后存为矩阵A，并设A为M×N矩阵，则2维DCT变换定义为：-1-1-1-1DCT变换的快速算法●63DCT变换是一种实数域变换，其变换核心为实数的余弦函数。变换

采用快速DCT变换对一幅256灰度的256×256的图像进行DCT正变换只需94ms。而如果采用普通DCT变换，所需时间要575,172ms。举例●例64采用快速DCT变换对一幅256灰度的256×256的图像进图像矩阵分块颜色变换零偏置转换 频域变换系数量化符号编码JPEG压缩步骤

●量化器DCT正向变换构造8×8的子图输入图像N×N符号编码器压缩图像颜色空间转换零偏置转换65图像矩阵分块JPEG压缩步骤●量化器DCT正构造8×8输入人眼对亮度更敏感，提取亮度特征，将RGB转换为YCbCr模型。对亮度采用特殊编码：Y=0.299R+0.5870G+0.1140BCb=–0.1787R–0.3313G+0.5000B+128Cr=0.5000R–0.4187G–0.0813B+128颜色解码：R=Y+1.40200(Cr

–128)G=Y–0.34414(Cb

–128)–0.71414(Cr

–128)B=Y+1.77200(Cb

–128)颜色空间转换RGB转到YCbCr●66人眼对亮度更敏感，提取亮度特征，将RGB转换为YCbCr模型YUV是电视系统中采用的颜色模式。Y是亮度信号，U、V是色度信号。转换公式:YUVRGB=

0.300.590.11-0.15-0.290.440.61-0.52-0.096RGB与YUV颜色空间的转换●67YUV是电视系统中采用的颜色模式。Y是亮度信号，U、V是色度将图像矩阵分为8×8的子块，对每一块单独进行DCT变换。根据人眼对亮度信号比对色度信号更加敏感的生理特性，将Y分量划分为8×8的块，将U、V分量划分为16×16的块。U、V分量的每一块舍弃1/2的信息后形成一个8×8的矩阵。构造子图像●68将图像矩阵分为8×8的子块，对每一块单独进行DCT变换。根据对变换后的DCT矩阵进行量化处理（用表1和表2的量化矩阵分别对Y分量和U、V分量量化）。量化的原则：低频部分用小值量化，高频部分用大值量化，量化结果使高频部分出现大量“0”。采用阈值作为子图系数位置函数的量化方式。所有子图使用同一个全局阈值模板，但阈值的取值与系数的位置相关，阈值模板给出了不同位置上系数的相应阈值。对于亮度和颜色使用不同的量化阈值模板，并取整。量化处理●69对变换后的DCT矩阵进行量化处理（用表1和表2的量化矩阵分别表1JPEG标准所推荐的亮度量化表亮度的量化模板系数●70表1JPEG标准所推荐的亮度量化表亮度的量化模板系数●71718 24 47 99 99 99 9918 21 26 66 99 99 99 9924 26 56 99 99 99 99 9947 66 99 99 99 99 99 9999 99 99 99 99 99 99 9999 99 99 99 99 99 99 9999 99 99 99 99 99 99 9999 99 99 99 99 99 99 99表2JPEG标准所推荐的色度量化表颜色的量化模板系数●711718 24 47 99 99 99 1）正向量化：Squv=round(Suv/Quv)其中：Suv是DCT系数，Quv量化模板系数2）逆向量化：Ruv=SquvQuv例：Sq(0,0)=round[-415/16] =round[-25.9]=-26 Ruv(0,0)=-26*16=-416系数量化公式●721）正向量化：系数量化公式●72-26-3-6 2 2

0 0 00

1 -2-4 0 0

0 00-315 -1 -1

0 0 00

-412 -1 0

0 0 00

1

00 0 0 0 0 0

0 00 0 0 0 0 00 00 0 0 0 0 00 00 0 0 0 0 0量化变换后矩阵样式示意图低频部分高频部分量化结果●73-26-3-6 2 2 0 0 0为了增加连续“0”系数的个数，重新编排量化后的系数。方法是按照Z字形的式样编排（把一个8×8的矩阵变成一个1×64的矢量，频率较低的系数放在矢量的顶部）。

[-26-31-3-2-62-41-41150200-1200000-1-1EOB]

全零结尾用特殊符号EOB重新编排量化后的系数●74为了增加连续“0”系数的个数，重新编排量化后的系数。[-在重新对量化数据进行编码后，得到的数据有大量连续的零。对全部数据进行Huffman编码。完成后的编码数组（重排的）是：10101100100001010001011000010110100011001100011001001100101111001101101100110111101000001010其中空格是为了可阅读性而插入的。完成编码的重排数组的总位数是92，不压缩需要8×8×8=512位。结果的压缩率是512/92，或5.6:1。对量化结果进行编码●75在重新对量化数据进行编码后，得到的数据有大量连续的零。对全部压缩图像数据IDCT逆量化器熵解码器恢复的图像数据解码器压缩图像数据FDCT量化器熵编码器源图像数据编码器解码过程基于DCT编码过程●76压缩图像数据IDCT逆量化器熵解码器恢复的图像数据解码器压缩彩色图像像素645×600在计算机中存储为3个矩阵每个矩阵为645×600

各存储R、G、B的3个分量信息。

举例●例77彩色图像举例●例77变换后矩阵的左上角是图像的低频部分，越靠近右下角，频率越高。人的眼睛对高频部分是不敏感的。可以舍弃图像中的高频部分而基本上不影响图像质量。DCT变换后的图

●例78变换后矩阵的左上角是图像的低频部分，越靠近右下角，频率越高。对应645×600的矩阵A，为了舍弃高频部分，将该矩阵的高频部分置为0值。在这令此时矩阵减小为387×360，数据量是原来的（387×360）/（645×600）=36%（387×360）a1,1a1,2……a1,360

00……0a2,1a2,2……

a2,360

00……0

…………

……a387,1a387,2…a387,360

00……000……000……0………………00……000……0不同压缩比率的图像质量比较

●79对应645×600的矩阵A，为了舍弃高频部分，将该矩阵的高频重构后的图像只保留部分258×240

（258×240）增大高频部分的舍弃范围（1）

●数据量是原图的16%80重构后的图像只保留部分258×240（258×240）只保留部分130×120

数据量是原图的4%（130×120）重构后的图像增大高频部分的舍弃范围（2）

●81只保留部分130×120数据量是原图的4%（130×1只保留部分65×60

数据量是原图的1%（65×60）重构后的图像增大高频部分的舍弃范围（3）

●82只保留部分65×60数据量是原图的1%（65×60将矩阵A的前15行和列置为0。去掉少量低频部分对图像的影响

●重构后的图像显然对低频部分的细小修改都会对图像有很大的影响返回83将矩阵A的前15行和列置为0。去掉少量低频部分对图像的影响第5章多媒体技术MULTIMEDIATECHNOLOGY84第5章多媒体技术MULTIMEDIATECHNOLOGY1第5

章多媒体数据压缩技术5.1数据压缩基本原理

5.1.1信息、数据与编码

5.1.2数据压缩的条件

5.1.3数据冗余5.2数据压缩算法

5.2.1数据压缩算法分类

5.2.2预测编码原理

5.2.3变换编码原理

5.2.4统计编码原理

5.2.5霍夫曼编码原理

5.2.6行程编码原理5.2.7算术编码原理

5.2.8LZW压缩编码5.3静态图像JPEG压缩编码技术

5.3.1JPEG标准的由来

5.3.2JPEG压缩算法

5.3.3无失真预测编码

5.3.4有失真DCT压缩编码5.4动态图像MPEG压缩编码技术

5.4.1基本原理

5.4.2MPEG技术标准85第5章多媒体数据压缩技术5.1数据压缩基本原理数据压缩基本原理5.1数据压缩的对象是数据。数据是信息的载体，用来记录和传送信息。真正有用的不是数据本身，而是数据所携带的信息。大的数据量并不代表含有大的信息量。而对于去掉冗余的数据对信息没有本质的影响称为压缩。●数据压缩原理86数据压缩基本原理5.1数据压缩的对象是数据。数据是信息的载体5.1.1信息、数据与编码我们了解的东西，描述它用的信息量少，不了解的东西，描述它用的信息量大。在信息论中，可以说：信息是用不确定的度量来定义的；一个消息的可能性越小，其信息含量越大；消息的可能性越大，则信息含量越小。例自然现象875.1.1信息、数据与编码我们了解的东西，描述它用的信息数据压缩基本原理5.15.1.1信息、数据与编码1．信息和熵●信息量的大小和消息有一定的关系。在数学上，消息是其出现概率的单调下降函数。信息量越大，消息的可能性越小，反之亦然。●信息量：为了从N个相等的可能事件中挑选出一个事件所需的信息度量和含量，所提问“是或否”的次数。也就是说，在N个事件中辨识特定的一个事件要询问“是或否”次数。要从256个数中选定某一个数，可以先提问“是否大于128？”，不论回答是与否，则半数的可能事件被取消。如果继续询问下去，每次询问将对应一个1bit的信息量。例88数据压缩基本原理5.15.1.1信息、数据与编码1．信息例●随着每次询问，有半数的可能事件被取消，这个过程由公式表示：可看出：对于256个数的询问只要进行8次，即可确定一个具体的数。设：从N个数中选定任意一个数x的概率为p(x)，假定选定任意一个数的概率都相等，即p(x)=1/N，则信息量为：log2256=8bit如果将信息源所有可能事件的信息量进行平均，即可得到信息的“熵”(熵是平均信息量)，信息源X的符号集为xi(i=1,2,…,N)。设：xi出现的概率为p(xi)，则信息源X的熵为：I(x)=log2N=-log21／N=-log2p(x)=I[p(x)]H(x)=P(xi)log2p(xi)∑P(xi)I[p(xi)]=-∑ni=1ni=189例●随着每次询问，有半数的可能事件被取消，这个过程由公式表示信息与数据2.信息可以用函数表示，该函数由信息论创始人C.E.Shannon香农提出，以概率论的观点对信息进行定量描述，具体的信息函数表达式为：I(ai)=-log2Pi(i=1,2,…,r)公式中，Pi(i

=1,2,…,r)是随机消息组合X{a1,a2,…,ar}中的消息ai(i

=1,2,…,r)的先验概率。Pi

可以度量ai(i

=1,2,…,r)所含的信息量。而I(ai)(i=1,2,…,r)在X的先验概率空间P{p1,p2,…,pr}中的统计平均值为信息源X的熵：信息源X的熵用来度量X中每种消息所包含的平均信息量。信息熵主要表示信息系统的有序程度，而不是热力学中系统的无序程度。H(X)=H{p1,p2,…,pr}=-Pilog2pi∑ni=190信息与数据2.信息可以用函数表示，该函数由信息论创始人C.E例2-1设信源有16种符号，其出现的概率相同，即P（Xi）=1/16。计算其平均信息熵。例91例2-1设信源有16种符号，其出现的概率相同，即P（Xi

例2-2某信源有8种符号，其出现的概率如下：例92例2-2某信源有8种符号，其出现的概率如下：例9信源中含有自然冗余度，这些冗余度既来自于信源本身的相关性，又来自于信源概率分布的不均匀性，只要找到去除相关性或改变概率分布不均匀性的手段和方法，也就找到了信息熵编码的方法。但信源所含有的平均信息量（熵）是进行无失真编码的理论的极限，只要不低于此极限，就能找到某种适宜的编码方法，去逼近信息熵，实现数据压缩。香侬理论的要点2.93信源中含有自然冗余度，这些冗余度既来自于信源本身的相关性，又多媒体信息的数据量3.1)文本

——假设屏幕显示分辨率为1024×768，字符为16×16点阵，每个字符用4个字节表示，则显示一屏字符所需要的存储空间为：（1024/16）×（768/16）×4B=12288B（约合12KB）2)图像

——假定图像显示在1024×768分辨率的屏幕上，则满屏幕像点所占用的空间为：

1024×768×log2256=768KB3)音频

——假定模拟声音频率22050Hz，其数字采样频率44100Hz，采样精度为16bit，双声道立体声模式，则1min所需数据量为：

44100Hz×2B(16bit采样精度)×2(双声道)×60s=10MB/min4)视频

——采用带宽为5MHz的PAL制视频信号，扫描速度25帧/s，样本宽度24bit，采样频率最低10MHz，则一帧数字化图像所占用的最少存储空间为：

10(采样频率)÷25(扫描速度)×24(样本宽度)=9.6Mbit(合1.2MB)94多媒体信息的数据量3.1)文本——假设屏幕显示分辨率为考虑一张640×480的全彩影像

640×480×3×8=7,372,800Bits

调制解调器(Modem)为

36Kbps

7372800/36000=204.8(sec)=3.41(min)

假设压缩算法(JPEG)的压缩率为1:12

(7372800/12)/36000=17.1(sec)

对图片压缩效果较好，但对色彩单纯的图形則效果一般不很理想。

例95考虑一张640×480的全彩影像

640×数据压缩的条件5.1.2●

数据冗余度(重复数据、可忽略数据)●

信息传输与存储的限制(压缩→传输或存储→解压缩)■44.1kHz/Stereo1.3MB■22.0kHz/Mono0.3MB■Stop重复数据可忽略数据●

人类不敏感因素(颜色、亮度、细节等)224颜色(16,777,216色)28颜色(256色)●音频不敏感因素(试听)●

颜色不敏感因素96数据压缩的条件5.1.2●数据冗余度(重复数据