多媒体技术与应用 第6-8讲 多媒体数据处理与数据压缩

1、第6-8讲 多媒体数据处理与数据压缩多媒体技术与应用2掌握数据压缩的主要算法了解数据编码及数据压缩的相关标准 学习目标3主要内容3. 数据无损压缩4. 数据有损压缩1. 数据压缩概述2. 数据编码分类多媒体技术与应用多媒体技术与应用41. 数据压缩概述数据压缩概述1.1 数据压缩的必要性数据压缩的必要性n 多媒体应用中涉及的媒体有文字、图形、多媒体应用中涉及的媒体有文字、图形、图像、音频、动画、视频等图像、音频、动画、视频等n图形文件的数据量与图形内容和及文件格图形文件的数据量与图形内容和及文件格式有关式有关n动画的数据量与数据的制作格式有关（矢动画的数据量与数据的制作格式有关（矢量、点阵）量

2、、点阵）n绝大部分的图像、音频、视频的数据量都绝大部分的图像、音频、视频的数据量都非常大非常大多媒体技术与应用5 声音声音具有具有CD音乐音乐激光唱盘音质的波形激光唱盘音质的波形声音的典型参数：声音的典型参数： 采样频率采样频率44.1KHz 量化位数：量化位数：16位位 立体声声道数：立体声声道数：2 数据量：约数据量：约0.17MB/秒秒 注：数据量（采样频率注：数据量（采样频率量化位数量化位数声道数）声道数）/8 根据上面公式可以计算出以上数据量所需的存取时间：根据上面公式可以计算出以上数据量所需的存取时间：在在650MB的光盘中存放时间约的光盘中存放时间约1小时。小时。1. 数据压缩概

3、述数据压缩概述1.1 数据压缩的必要性数据压缩的必要性多媒体技术与应用6 （2）图像）图像静态图像：一幅中等分辨率的位图图像（静态图像：一幅中等分辨率的位图图像（640480，256色），典型参数为：色），典型参数为：a.图像分辨率：图像分辨率：640480b.图像颜色数：图像颜色数：256（=28）c.颜色深度颜色深度(位位)：8d.数据量为：约数据量为：约0.3MB注：注：数据量（垂直分辨率数据量（垂直分辨率水平分辨率水平分辨率颜色深度）颜色深度）/8 对于以上数据量，在对于以上数据量，在1.44MB的软盘中能存放约的软盘中能存放约5幅静幅静态图像。若用速率（态图像。若用速率（64kbps

4、）的电话线传输，一幅静态图）的电话线传输，一幅静态图像约需要传送像约需要传送38秒秒 。1. 数据压缩概述数据压缩概述1.1 数据压缩的必要性数据压缩的必要性多媒体技术与应用7 动态视频：一幅中等分辨率动态视频：一幅中等分辨率24位真彩色的位图图像位真彩色的位图图像（640480，24位位/像素），典型参数为：像素），典型参数为：a.图像分辨率：图像分辨率：640480b.图像颜色数：图像颜色数：16,777,216（=224）c.颜色深度颜色深度(位位)：24d.数据量为：约数据量为：约0.9MB 对于以上数据量，若用对于以上数据量，若用NTSC制式（制式（30帧帧/秒）播放动秒）播放动态视

5、频，需要约态视频，需要约27MB/秒的视频传输速度，在秒的视频传输速度，在650MB的光的光盘中存放时间约盘中存放时间约24秒。秒。1. 数据压缩概述数据压缩概述1.1 数据压缩的必要性数据压缩的必要性多媒体技术与应用8高清电视：典型参数为：高清电视：典型参数为：a.图像分辨率：图像分辨率：1024768b.图像颜色数：图像颜色数： 16,777,216（=224）c.颜色深度颜色深度(位位)：8 d. 帧率帧率 60帧帧/秒秒e.数据量为：约数据量为：约1.2GB/s注：注：数据量（垂直分辨率数据量（垂直分辨率水平分辨率水平分辨率颜色深度颜色深度 帧率）帧率）/8 对于以上数据量，在对于以上

6、数据量，在4.7G的光盘中能存放约的光盘中能存放约6分钟分钟的视频。传输速率需的视频。传输速率需1.2Gb/s，普通的宽带网络根本无法，普通的宽带网络根本无法承受。承受。1. 数据压缩概述数据压缩概述1.1 数据压缩的必要性数据压缩的必要性多媒体技术与应用91. 数据压缩概述数据压缩概述1.1 数据压缩的必要性数据压缩的必要性n因此，在多媒体应用中，存在着存储和传输两因此，在多媒体应用中，存在着存储和传输两个问题个问题n随着计算机技术的快速发展，存储介质的容量、随着计算机技术的快速发展，存储介质的容量、传输速率，以及系统和网络的传输速率都有了传输速率，以及系统和网络的传输速率都有了大幅度提高，

7、但是多媒体应用的需求也在发展。大幅度提高，但是多媒体应用的需求也在发展。n单纯的硬件技术无法满足应用需求，媒体数据单纯的硬件技术无法满足应用需求，媒体数据的压缩是最终的解决方案。的压缩是最终的解决方案。n压缩：把媒体的数据量变小。压缩：把媒体的数据量变小。101. 数据压缩概述数据压缩概述1.2 数据压缩的可能性数据压缩的可能性1. 感官的生理局限性感官的生理局限性n听觉局限性：听觉具有掩蔽性；对不同频段的听觉局限性：听觉具有掩蔽性；对不同频段的声音敏感程度不同；对语音信号的相位变化不声音敏感程度不同；对语音信号的相位变化不敏感敏感n视觉局限性：视觉具有掩蔽性，对图像的某些视觉局限性：视觉具有

8、掩蔽性，对图像的某些变化不敏感；视觉的色彩分辨力有限变化不敏感；视觉的色彩分辨力有限224 颜色颜色 (16,777,216色色)28 颜色颜色 (256色色)多媒体技术与应用111. 数据压缩概述数据压缩概述1.2 数据压缩的可能性数据压缩的可能性2. 多媒体数据的冗余多媒体数据的冗余n信息之所以能进行压缩，是因为信息本身通常信息之所以能进行压缩，是因为信息本身通常存在很大的存在很大的冗余量冗余量n1. 冗余冗余在平时说话时是大量存在的。在平时说话时是大量存在的。n2. 中文广播员中文广播员180个汉字个汉字/分钟分钟,一个汉字两个字节一个汉字两个字节, 360个个Byte 。 音频数据：采

9、样音频数据：采样1分钟，分钟，8K 60 = 480 K Byte/分分n 480 K byte / 360 byte = 1000倍的冗余倍的冗余n3. 中文百科全书扫描进入计算机冗余更大。中文百科全书扫描进入计算机冗余更大。 200万字万字x2=40000004MByte ；B5扫描（扫描（185X255 300dpi ） 一一页为页为6.61M Byte， 200万字万字1000页为页为6.61Gn4. 图像信息、视频信息的冗余就更大了。图像信息、视频信息的冗余就更大了。122. 多媒体数据的冗余多媒体数据的冗余n信息量与数据量的关系可由下式给出：信息量与数据量的关系可由下式给出： I

10、= D - du ( (I，D，du分别为信息量、数据量与冗余量。分别为信息量、数据量与冗余量。 冗余量冗余量du是指是指D中的数据冗余。中的数据冗余。) ) n数据冗余的类别：数据冗余的类别：空间冗余、时间冗余、信息冗余、结构冗余、空间冗余、时间冗余、信息冗余、结构冗余、知识冗余知识冗余 等等1. 数据压缩概述数据压缩概述1.2 数据压缩的可能性数据压缩的可能性多媒体技术与应用131. 数据压缩概述数据压缩概述1.2 数据压缩的可能性数据压缩的可能性2. 多媒体数据的冗余多媒体数据的冗余n空间冗余空间冗余 例: 图像中的“A”是一个规则物体。光的亮度、饱和度及颜色都一样，因此，数据A有很大的

11、冗余。A多媒体技术与应用141. 数据压缩概述数据压缩概述1.2 数据压缩的可能性数据压缩的可能性2. 多媒体数据的冗余多媒体数据的冗余n时间冗余时间冗余 例：图像序列AF2AF1多媒体技术与应用151. 数据压缩概述数据压缩概述1.2 数据压缩的可能性数据压缩的可能性2. 多媒体数据的冗余多媒体数据的冗余n结构冗余结构冗余图像有非常强的纹理结构，图图像有非常强的纹理结构，图像的象素值存在着明显的分布像的象素值存在着明显的分布模式。模式。多媒体技术与应用161. 数据压缩概述数据压缩概述1.2 数据压缩的可能性数据压缩的可能性2. 多媒体数据的冗余多媒体数据的冗余n知识冗余知识冗余 图像的理解

12、与某些基础知识有图像的理解与某些基础知识有关。关。 例例:人脸的图像有同样的结构：人脸的图像有同样的结构：嘴的上方有鼻子，鼻子上方有眼睛，嘴的上方有鼻子，鼻子上方有眼睛，鼻子在中线上鼻子在中线上 知识冗余是模型编码主要利用知识冗余是模型编码主要利用的特性。的特性。 多媒体技术与应用171. 数据压缩概述数据压缩概述1.2 数据压缩的可能性数据压缩的可能性2. 多媒体数据的冗余多媒体数据的冗余n统计冗余：统计冗余：编码中各种符号出现的频率不同，编码中各种符号出现的频率不同，如果每一种符号用相同的存储位数，也会产生如果每一种符号用相同的存储位数，也会产生冗余，这种冗余叫统计冗余。冗余，这种冗余叫统

13、计冗余。n信息熵冗余：信息熵冗余：图像中平均每个像素使用的比特图像中平均每个像素使用的比特数大于该图像的信息熵，则图像中存在冗余，数大于该图像的信息熵，则图像中存在冗余，这种冗余称为信息熵冗余。这种冗余称为信息熵冗余。 n其他的冗余其他的冗余 多媒体技术与应用18信息熵与信息量信息熵与信息量n信息量：指从信息量：指从N个相等的可能事件中选出一个事个相等的可能事件中选出一个事 件所需要的信息度量和含量。件所需要的信息度量和含量。n信息熵：指一组数据所带的信息量，平均信息量信息熵：指一组数据所带的信息量，平均信息量就是就是信息熵信息熵（entropy）。）。 例如例如:从从64个数中选出某一个数。

14、可先问个数中选出某一个数。可先问“是否大于是否大于32?”消除半数的可能消除半数的可能,这样只要这样只要6次就可选出某数。次就可选出某数。如果要选择的数是如果要选择的数是35,则过程如下则过程如下:1.大于大于/小于小于 32？ 大大2.大于大于/小于小于 32+16=48？小小3.大于大于/小于小于 48-8=40？小小4.大于大于/小于小于 40-4=36？小小5.大于大于/小于小于 36-2=34？大大6.大于大于/小于小于 34+1=35 等等多媒体技术与应用19如果要选择的数是如果要选择的数是63,63,则其过程如下则其过程如下: :1.1.大于大于/ /小于小于 3232？大大2.

15、2.大于大于/ /小于小于 32+16=4832+16=48？大大3.3.大于大于/ /小于小于 48+8=5648+8=56？大大4.4.大于大于/ /小于小于 56+4=6056+4=60？大大5.5.大于大于/ /小于小于 60+2=6260+2=62？大大6.6.大于大于/ /小于小于 62+1=6362+1=63 等等每提问一次都会得到1比特的信息量。因此，在64个数中选定某一数所需的信息量是 log264=6(bits)信息熵与信息量信息熵与信息量多媒体技术与应用20设从设从N N个数中选任意一个数中选任意一个数个数x x的的概率为概率为 P(x)P(x)，假，假定选定任意一个数的

16、概率都相等，定选定任意一个数的概率都相等，P(x)= 1/NP(x)= 1/N，因此定义信息量因此定义信息量 I(x) =logI(x) =log2 2N N = -log = -log2 2(1/N)(1/N) = -log = -log2 2P(x)P(x) =IP(x) =IP(x)n信息量：指从信息量：指从N个 相 等 的 可个 相 等 的 可能事件中选出能事件中选出一个事件所需一个事件所需要的信息度量要的信息度量和含量。和含量。 如果将信源所有可能事件的信息量进行平均，就得到了信息熵(entropy)。熵就是平均信息量。信息熵与信息量信息熵与信息量21n数据压缩与解压缩数据压缩与解压

17、缩2. 数据压缩分类数据压缩分类u压缩的目的是为了最有效的利用存储、通信和计压缩的目的是为了最有效的利用存储、通信和计算资源算资源u压缩压缩：去掉信号数据的冗余性，也称为数据编码：去掉信号数据的冗余性，也称为数据编码u解压缩解压缩：压缩的逆过程，称为数据解码：压缩的逆过程，称为数据解码u按照压缩和解压缩算法耗费的代价不同，可把多按照压缩和解压缩算法耗费的代价不同，可把多媒体应用分为对称应用和非对称应用。媒体应用分为对称应用和非对称应用。u对称应用对称应用中：编码和解码的代价基本相同中：编码和解码的代价基本相同u非对称应用非对称应用中：解码比编码过程耗费的代价要小中：解码比编码过程耗费的代价要小

18、22n数据压缩算法的衡量标准数据压缩算法的衡量标准算法算法的压的压缩率缩率压缩压缩后的后的图像图像质量质量压缩压缩和解和解压缩压缩的速的速度度所需采所需采用的硬用的硬件和软件和软件及其件及其开销开销2. 数据压缩分类数据压缩分类23n衡量压缩率通常有两种方法：衡量压缩率通常有两种方法： (1)(1)看压缩后的位流中每个显示像素的位数。看压缩后的位流中每个显示像素的位数。 如：以如：以15000字节存储一幅字节存储一幅256240的图像，则的图像，则压缩率为：压缩率为： ( ( 150008 ) / ( ) / ( 256240 ) = ) = 2 位位/ /像素像素(2)(2)以压缩前后文件大

19、小和数据率作比较，其以压缩前后文件大小和数据率作比较，其比值为压缩率。比值为压缩率。 n数据压缩的衡量标准数据压缩的衡量标准24n根据图像质量有无损失，数据压缩可分为两种根据图像质量有无损失，数据压缩可分为两种类型类型 无损压缩指解压缩指解压缩还原得到还原得到的数据与的数据与原始数据原始数据完全相同完全相同指解压缩还指解压缩还原得到的数原得到的数据与原始数据与原始数据不完全相据不完全相同同有损压缩2. 数据压缩分类数据压缩分类25数据压缩技术无损压缩有损压缩哈夫曼编码行程编码算术编码Lempel Zev编码预测编码运动补偿面向频域面向重要性混合编码JPEGMPEGH.261量 化比特分配子采样

20、滤 波矢量量化标量量化子波变换(Wavelet)子带编码变换编码26 主要介绍目前用得最多和技术最成熟的无损压缩编码技术，包括：3. 数据无损压缩数据无损压缩香农-范诺编码霍夫曼编码算术编码RLE编码词典编码27编码器信源（消息集）编码输出集X=x1,xnZ=z1,zn符号集Am=a1,am熵熵( (Entropy) )的概念的概念 熵是信息量的度量方法，它表示某一事件出现的消息熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，数学上就是概率越小。越多，事件发生的可能性就越小，数学上就是概率越小。 某个事件的信息量用某个事件的信息量用 表示表示, ,其中其中Pi为第为

21、第i个个事件的概率，事件的概率，0H（S） 有冗余，不是最佳有冗余，不是最佳 N H(S) 不可能不可能 NH（S） （ N稍大于稍大于H（S）)是最佳编码是最佳编码香农香农- -范诺算法范诺算法29Shannon-Fano的树是根据旨在定义一个有效的代码表的规的树是根据旨在定义一个有效的代码表的规范而建立的。实际的算法很简单：范而建立的。实际的算法很简单：1.对于一个给定的符号列表：制定对于一个给定的符号列表：制定概率概率相应的列表或频率计相应的列表或频率计数，使每个符号的相对发生频率已知。数，使每个符号的相对发生频率已知。2.排序：根据频率的符号列表，最常出现的符号在左边，最排序：根据频率

22、的符号列表，最常出现的符号在左边，最少出现的符号在右边。少出现的符号在右边。3.清单分为两部分：使左边部分的总频率和尽可能接近右边清单分为两部分：使左边部分的总频率和尽可能接近右边部分的总频率和。部分的总频率和。4.该列表的左半边分配二进制数字该列表的左半边分配二进制数字0，右半边是分配的数字，右半边是分配的数字1。这意味着，在第一半符号代都是将所有从这意味着，在第一半符号代都是将所有从0开始，第二半开始，第二半的代码都从的代码都从1开始。开始。5.对左、右半部分递归应用步骤对左、右半部分递归应用步骤3和和4，细分群体，并添加位，细分群体，并添加位的代码，直到每个符号已成为一个相应的代码树的叶

23、。的代码，直到每个符号已成为一个相应的代码树的叶。香农香农- -范诺算法范诺算法30符号ABCDE计数157665概率0.384615380.179487180.153846150.153846150.12820513香农香农- -范诺算法范诺算法例：一组字母的香农编码结构，这五个可被编码的字母有如下出现次数例：一组字母的香农编码结构，这五个可被编码的字母有如下出现次数从左到右，所有的符号以它们出现的次数划分。在字母从左到右，所有的符号以它们出现的次数划分。在字母B与与C之间划定分割线，这样就把两组的差别降到最小。之间划定分割线，这样就把两组的差别降到最小。通过这样的分割通过这样的分割, A与

24、与B同时拥有了一个以同时拥有了一个以0为开头的码为开头的码字字, C，D，E的码子则为的码子则为1 。随后，在树的左半边，于。随后，在树的左半边，于A，B间建立新的分割线，这样间建立新的分割线，这样A就成为了码字为就成为了码字为00的叶子的叶子节点，节点，B的码子的码子01。经过四次分割，得到了一个树形编。经过四次分割，得到了一个树形编码。在最终得到的树中，拥有最大频率的符号被两位编码。在最终得到的树中，拥有最大频率的符号被两位编码，其他两个频率较低的符号被三位编码。码，其他两个频率较低的符号被三位编码。在最终得到的树中，拥有最大频率在最终得到的树中，拥有最大频率的符号被两位编码，其他两个频率

25、的符号被两位编码，其他两个频率较低的符号被三位编码。较低的符号被三位编码。符号ABCDE编码00011011011131香农香农- -范诺算法范诺算法算法举例算法举例有一幅有一幅4040个象素组成的灰度图像，灰度共有个象素组成的灰度图像，灰度共有5 5级，分别用符级，分别用符号号A A、B B、C C、D D和和E E表示，表示，4040个象素中出现灰度个象素中出现灰度A A的象素数有的象素数有1515个，出现灰度个，出现灰度B B的象素数有的象素数有7 7个，出现灰度个，出现灰度C C的象素数有的象素数有7 7个等个等等，如下表所示。如果用等，如下表所示。如果用3 3个位表示个位表示5 5个

26、等级的灰度值，也就个等级的灰度值，也就是每个象素用是每个象素用3 3位表示，编码这幅图像总共需要位表示，编码这幅图像总共需要120120位。位。符 号ABCDE出现的次数157765概率15/407/407/406/405/40对于上例，对于上例，S=（A，B，C，D，E）H（S）=15/40 * log2(40/15)+ 7/40 * log2(40/7) + 5/40 * log2(40/5)=2.196这就是说每个符号用这就是说每个符号用2.196位表示，位表示，40个象素需用个象素需用87.84位。位。32n香农香农-范诺编码算法并非总能得到最优编码，范诺编码算法并非总能得到最优编码，

27、霍霍夫曼夫曼( (Huffman) )在在1952年提出了另一种编码方年提出了另一种编码方法，法，这个算法可以为任何的可能性提供出一个这个算法可以为任何的可能性提供出一个理想的树。理想的树。n香农香农-范诺编码是从树的根节点到叶子节点所进范诺编码是从树的根节点到叶子节点所进行的的编码，哈夫曼编码算法却是从相反的方行的的编码，哈夫曼编码算法却是从相反的方向，暨从叶子节点到根节点的方向编码的，向，暨从叶子节点到根节点的方向编码的，即即从下到上的编码方法：从下到上的编码方法： 概率大的用短码，概率小的用长码概率大的用短码，概率小的用长码 霍夫曼霍夫曼(Huffman)编码编码33n霍夫曼编码的方法：

28、霍夫曼编码的方法：v信元的符号按概率大小进行排列信元的符号按概率大小进行排列, ,设法按逆次设法按逆次序分配码字的长度。序分配码字的长度。 v分配码字长度时分配码字长度时, ,首先将出现概率最小的两个首先将出现概率最小的两个符号的概率相加，合成一个新的数值。符号的概率相加，合成一个新的数值。v把合成的数值看成是一个新的组合符号的概率，把合成的数值看成是一个新的组合符号的概率，重复上述操作，直到剩下最后两个符号。重复上述操作，直到剩下最后两个符号。 v完成上述概率的排列后，再返回向前给予编码完成上述概率的排列后，再返回向前给予编码, ,每层有两个分支每层有两个分支, , 分别赋予分别赋予0 0和

29、和1(1(大的赋大的赋0 0或小或小的赋的赋0 0均可）。均可）。 34霍夫曼霍夫曼(Huffman)编码编码算法举例算法举例符号ABCDE计数157665概率0.384615380.179487180.153846150.153846150.12820513D，E频率最低，分别分配为频率最低，分别分配为0和和1，分组结合，分组结合概率的概率的0.28205128。现在最低的是。现在最低的是B和和C，所，所以他们就分配以他们就分配0和和1，结合概率为，结合概率为0.33333333。这使得这使得BC和和DE结合的概率最低，所以他们结合的概率最低，所以他们前面加上前面加上0和和1的代码。然后只是

30、一个的代码。然后只是一个A和和BCDE，分别为，分别为1和和0，然后结合。这使我们，然后结合。这使我们与一个单一的节点结合，我们的算法是完整与一个单一的节点结合，我们的算法是完整的。的。这次这次A代码的代码长度是代码的代码长度是1比特，其余字符是比特，其余字符是3比特。比特。字符ABCDE代码100000101001135霍夫曼霍夫曼(Huffman)编码编码经经Huffman编码之后的数据为：编码之后的数据为：按照高概率赋按照高概率赋1，低概率赋，低概率赋0；概率相同时靠近高；概率相同时靠近高概率的赋概率的赋1，靠近低概率的赋，靠近低概率的赋0，结果：，结果：f: 11, e: 01, a:

31、 00, b:101, c:1001; d:100036 霍夫曼码的码长虽是可变的，但却不需要另霍夫曼码的码长虽是可变的，但却不需要另外附加同步代码。几个问题值得注意：外附加同步代码。几个问题值得注意：1.1. 霍夫曼码没有错误保护功能；霍夫曼码没有错误保护功能；2.2. 霍夫曼码是可变长度码，因此很难随意查找或霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码调用压缩文件中间的内容，然后再译码; ;3.3. 对信源进行编码后形成霍夫曼编码表，在存储对信源进行编码后形成霍夫曼编码表，在存储和传输过程中必须首先存储或传输这个编码表；和传输过程中必须首先存储或传输这个编码表

32、；接收端需保存一个与发送端相同的霍夫曼码表，接收端需保存一个与发送端相同的霍夫曼码表，解码时必须参照这个表才能够正确解码。解码时必须参照这个表才能够正确解码。 霍夫曼霍夫曼(Huffman)编码编码37n霍夫曼编码优缺点：霍夫曼编码优缺点：优点：优点：当信源符号概当信源符号概率是率是2 2 的负幂次方时的负幂次方时, ,HuffmanHuffman编码法编码效编码法编码效率达到率达到100%100%。一般情况。一般情况下，它的编码效率要下，它的编码效率要比其它编码方法的效率比其它编码方法的效率高，是最佳变长码。高，是最佳变长码。缺点缺点：HuffmanHuffman码依赖于码依赖于信源的统计特

33、性，必须信源的统计特性，必须先统计得到信源的概率先统计得到信源的概率特性才能编码，这就限特性才能编码，这就限制了实际的应用。通常制了实际的应用。通常可在经验基础上预先提可在经验基础上预先提供供HuffmanHuffman码表，此时性码表，此时性能有所下降。能有所下降。n对一副图像进行编码时，如果图像的大小大于对一副图像进行编码时，如果图像的大小大于256，这幅图像的不同的码子就有可能很大，如极限为这幅图像的不同的码子就有可能很大，如极限为256个不同的码子个不同的码子n例如，对整幅图像直接进行霍夫曼编码时，小分布的例如，对整幅图像直接进行霍夫曼编码时，小分布的灰度值就有可能具有很长的编码（大于

34、灰度值就有可能具有很长的编码（大于100），这样），这样不仅不能达到压缩的效果还可能增加数据量，怎么办不仅不能达到压缩的效果还可能增加数据量，怎么办？n常用并且有效的方法常用并且有效的方法是：将图像分割成若干小块儿，是：将图像分割成若干小块儿，对每块进行独立的霍夫曼编码，如，分成对每块进行独立的霍夫曼编码，如，分成8x8的子块的子块，就可以大大降低不同灰度值的个数（最多为，就可以大大降低不同灰度值的个数（最多为64而不而不是是256）38多媒体技术与应用霍夫曼霍夫曼(Huffman)编码编码n霍夫曼编码在图像压缩中的实现霍夫曼编码在图像压缩中的实现39n霍夫曼编码使用整数个二进制位对符号进行霍

35、夫曼编码使用整数个二进制位对符号进行编码，这种方法在许多情况下无法得到最优编码，这种方法在许多情况下无法得到最优的压缩效果。假设某个字符的出现概率为的压缩效果。假设某个字符的出现概率为80%80%，那么该字符只需要，那么该字符只需要-log-log2 2(0.8)=0.322 (0.8)=0.322 位编码。但霍夫曼编码一定会为其分配位编码。但霍夫曼编码一定会为其分配0 0或或者者1 1。可以想象，整个信息的。可以想象，整个信息的80%80%在压缩后都在压缩后都几乎相当于理想长度的几乎相当于理想长度的3 3倍左右。倍左右。n能否只输出能否只输出0.3220.322个个0 0或者或者0.3220

36、.322个个1 1呢？可以呢？可以用剪刀把计算机中用剪刀把计算机中 二进制位剪开吗？二进制位剪开吗？算术编码算术编码40n算术编码对整条信息（无论信息有多么算术编码对整条信息（无论信息有多么长），其输出仅仅是一个数，一个介于长），其输出仅仅是一个数，一个介于0 0和和1 1之间的二进制小数。之间的二进制小数。n例如：算术编码对某条信息的输出为例如：算术编码对某条信息的输出为10100011111010001111，那么它表示小数，那么它表示小数0.10100011110.1010001111，也即十进制数，也即十进制数0.64.0.64.算术编码算术编码41算法举例算法举例1假设信源符号为假设

37、信源符号为00, 01, 10, 1100, 01, 10, 11，这些符号的概率，这些符号的概率分别为分别为 0.1, 0.4, 0.2, 0.3 0.1, 0.4, 0.2, 0.3 ，根据这些概率可把，根据这些概率可把间隔间隔0, 1)0, 1)分成分成4 4个子间隔：个子间隔：0, 0.1), 0.1, 0.5), 0, 0.1), 0.1, 0.5), 0.5, 0.7), 0.7, 1)0.5, 0.7), 0.7, 1)，二进制消息序列的输入为：，二进制消息序列的输入为：10 00 11 00 10 11 0110 00 11 00 10 11 01算术编码算术编码符 号0001

38、1011概 率0.10.40.20.3初始编码间隔0,0.1)0.1,0.5)0.5,0.7)0.7,1)42算法举例算法举例1算术编码算术编码43算法举例算法举例2算术编码算术编码44算法举例算法举例2算术编码算术编码45n算术编码把信源集合用算术编码把信源集合用0 0到到1 1之间的实数进之间的实数进行编码，算术编码用到两个基本的参数：行编码，算术编码用到两个基本的参数：符号的概率和它的编码间隔符号的概率和它的编码间隔。n信源符号的概率决定压缩编码的效率，也信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些决定编码过程中信源符号的间隔，而这些间隔包含在间隔包含在0 0

39、到到1 1之间。编码过程中的间隔之间。编码过程中的间隔决定了符号压缩后的输出。决定了符号压缩后的输出。n区间越窄，说明符号串越长，二进制码长区间越窄，说明符号串越长，二进制码长越长越长算术编码算术编码46n在不知道信源统计的情况下，只要能监视一小段在不知道信源统计的情况下，只要能监视一小段时间内码符号出现的频度，不管是平稳的还是非时间内码符号出现的频度，不管是平稳的还是非平稳信号，编成的码率总能趋近于信源熵值。平稳信号，编成的码率总能趋近于信源熵值。n算术编码适合的场合：算术编码适合的场合：n小字母表，如二进制信源小字母表，如二进制信源n概率分布不均衡概率分布不均衡n建模与编码分开建模与编码分

40、开n算术编码虽然比霍夫曼编码复杂，但它不需要传算术编码虽然比霍夫曼编码复杂，但它不需要传送像霍夫曼码的码表，具有可构造性，即可以使送像霍夫曼码的码表，具有可构造性，即可以使用迭代方法每次只处理一个数据符号，且只有算用迭代方法每次只处理一个数据符号，且只有算术运算。术运算。算术编码算术编码47在算术编码中需要注意的几个问题：在算术编码中需要注意的几个问题：n由于实际计算机精度不可能无限长，运算中溢出由于实际计算机精度不可能无限长，运算中溢出是明显的问题，但多数机器都有是明显的问题，但多数机器都有1616位、位、3232位或者位或者6464位的精度，因此可使用比例缩放法解决。位的精度，因此可使用比

41、例缩放法解决。n算术编码器对消息只产生一个码字，这个码字是算术编码器对消息只产生一个码字，这个码字是在在0, 1)0, 1)中的一个实数，因此译码器在接受到表中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。示这个实数的所有位之前不能进行译码。n算术编码也是一种对错误很敏感的编码方法，如算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。果有一位发生错误就会导致整个消息译错。算术编码算术编码48n算术编码可以是静态的或者自适应的。算术编码可以是静态的或者自适应的。n在静态算术编码中，信源符号的概率是固定的在静态算术编码中，信源符号的概率是固定的n

42、在自适应算术编码中，信源符号的概率根据编在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地进行修改，在码时符号出现的频繁程度动态地进行修改，在编码期间估算信源符号概率的过程叫做建模。编码期间估算信源符号概率的过程叫做建模。n在图像数据压缩标准在图像数据压缩标准( (如如JPEG, JBIG)JPEG, JBIG)中扮演了中扮演了重要的角色重要的角色算术编码算术编码49多媒体技术与应用算法举例算法举例2自适应编码自适应编码算术编码算术编码自适应模型：假自适应模型：假设初始频度都为设初始频度都为1，随着编码的，随着编码的进行更新频度进行更新频度如图：输入第一如图：输入第一个个B之

43、后更新频之后更新频度度最后的编码输出：最后的编码输出：0.64假设一份数据由假设一份数据由A A，B B，C C三个符号构成，要编码的数据三个符号构成，要编码的数据是是“BCCBBCCB”50多媒体技术与应用算法举例算法举例2自适应编码自适应编码算术编码算术编码解码过程：解码过程：由由0.640.64确定第一个字母为确定第一个字母为B B，输出，输出B B后更新后更新频度，按新频度对频度，按新频度对B B所在的区间所在的区间0.3333,0.66670.3333,0.6667进行分割，这时，进行分割，这时，0.640.64落落在区间在区间0.5834,0.66670.5834,0.6667中，

44、可解码输出中，可解码输出C C，以此类推，可全部解码以此类推，可全部解码51基本原理基本原理用一个符号值或串代替具有相同值的连续符号，用一个符号值或串代替具有相同值的连续符号，使符号长度少于原始数据的长度。使符号长度少于原始数据的长度。比如：比如：一个字符串：一个字符串：5 5 5 5 5 5 7 7 7 7 7 3 3 3 2 5 5 5 5 5 5 7 7 7 7 7 3 3 3 2 2 2 2 1 1 1 1 1 1 12 2 2 1 1 1 1 1 1 1行程编码：行程编码：(6, 5) (5, 7) (3,3) (4, 2) (7, 1)(6, 5) (5, 7) (3,3) (4,

45、 2) (7, 1)可见，行程编码的位数远远少于原始字符串的位可见，行程编码的位数远远少于原始字符串的位数。数。RLE(run length encoding）编码编码52n主要适用于图像，在图像中具有相同颜色主要适用于图像，在图像中具有相同颜色并且是连续的像素数目称作行程长度并且是连续的像素数目称作行程长度n对图像中颜色相同的图块儿，仅存储一个对图像中颜色相同的图块儿，仅存储一个像素的颜色值以及具有相同颜色的像素数像素的颜色值以及具有相同颜色的像素数目，或存储一个像素值及具有相同颜色值目，或存储一个像素值及具有相同颜色值的行数。的行数。RLE(run length encoding）编码编码

46、53RLE(run length encoding）编码编码 译码时按照与编码时采用的相同规则进行，还原后得译码时按照与编码时采用的相同规则进行，还原后得到的数据与压缩前的数据完全相同。到的数据与压缩前的数据完全相同。 用用RLERLE编码方法得到的代码为：编码方法得到的代码为：8 80 03 31 150508 84 41 18 80 0。代码。代码中下划线表示的数字是行程长度，后面的数字代表象素中下划线表示的数字是行程长度，后面的数字代表象素的颜色值。例如带下划线的的颜色值。例如带下划线的5050代表有连续代表有连续5050个象素具有个象素具有相同的颜色值，它的颜色值是相同的颜色值，它的颜

47、色值是8 8。54词典编码的基本思想词典编码的基本思想 构造一个字典，将信息中反复出现构造一个字典，将信息中反复出现的字符串登记为较短的字符串，解码时的字符串登记为较短的字符串，解码时对这种字符串通过查字典转换为原字符对这种字符串通过查字典转换为原字符串。串。 最原始的字典法是模式置换压缩算最原始的字典法是模式置换压缩算法。法。词典编码词典编码55词典编码的思想词典编码的思想1 第一类词典法的想法是企图查找正在压缩的字符序列第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输

48、出仅仅是指向早期出现过的符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的字符串的“指针指针”。词典编码词典编码56词典编码的思想词典编码的思想2 第二类算法的想法是第二类算法的想法是企图从输入的数据中创企图从输入的数据中创建一个建一个“短语词典短语词典 ( (dictionary of the dictionary of the phrases)”phrases)”，这种短语这种短语可以是任意字符的组合。可以是任意字符的组合。编码数据过程中当遇到编码数据过程中当遇到已经在词典中出现的已经在词典中出现的“短语短语”时，编码器就时，编码器就输出这个词典中的短语输出这个词典中的短语的的“索

49、引号索引号”，而不是，而不是短语本身。短语本身。词典编码词典编码57词典编码词典编码58多媒体技术与应用 LZ算法 n1977 1977 年，年，Jacob Ziv Jacob Ziv 和和 Abraham LempelAbraham Lempel发表了论发表了论文文顺序数据压缩的一个通用算法顺序数据压缩的一个通用算法。1978 1978 年，年，他们发表了该论文的续篇他们发表了该论文的续篇通过可变比率编码的独通过可变比率编码的独立序列的压缩立序列的压缩。n这两篇论文提出的两个压缩技术被称为这两篇论文提出的两个压缩技术被称为 LZ77 LZ77 和和 LZ78LZ78算法。它们的思路和字典法颇

50、为相似，因此，算法。它们的思路和字典法颇为相似，因此，人们将基于这一思路的编码方法称作字典式编码。人们将基于这一思路的编码方法称作字典式编码。字典式编码不但在压缩效果上大大超过了哈夫曼编字典式编码不但在压缩效果上大大超过了哈夫曼编码，而且，对于好的实现，其压缩和解压缩的速度码，而且，对于好的实现，其压缩和解压缩的速度也异常惊人。也异常惊人。59nLZ77算法算法 为了更好地说明为了更好地说明LZ77算法的原理，首先算法的原理，首先介绍算法中用到的几个术语：介绍算法中用到的几个术语：n输入数据流输入数据流( (input stream)input stream)：要被压缩的要被压缩的字符序列。字

51、符序列。n字符字符( (character)character)：输入数据流中的基本输入数据流中的基本单元。单元。n编码位置编码位置( (coding position)coding position)：输入数据流输入数据流中当前要编码的字符位置，指前向缓冲存中当前要编码的字符位置，指前向缓冲存储器中的开始字符。储器中的开始字符。 60nLZ77算法算法n前向缓冲存储器前向缓冲存储器( (LookaheadLookahead buffer) buffer)：存放存放从编码位置到输入数据流结束的字符序列的从编码位置到输入数据流结束的字符序列的存储器。存储器。n窗口窗口( (window)wind

52、ow)：指包含指包含W W个字符的窗口，字符个字符的窗口，字符是从编码位置开始向后数，也就是最后处理是从编码位置开始向后数，也就是最后处理的字符数。的字符数。n指针指针( (pointer)pointer)：指向窗口中的匹配串且含长指向窗口中的匹配串且含长度的指针。度的指针。61LZ77编码算法的核心是查找从前向缓冲存储器开始编码算法的核心是查找从前向缓冲存储器开始的最长的匹配串。编码算法的具体执行步骤如下：的最长的匹配串。编码算法的具体执行步骤如下：把编码位置设置到输入数据流的开始位置把编码位置设置到输入数据流的开始位置。1查找窗口中最长的匹配串查找窗口中最长的匹配串。2以以“( (Poin

53、ter, Length) ) Characters”的格式输出，其中的格式输出，其中3如果前向缓冲存储器不是空的，则把编码位置和如果前向缓冲存储器不是空的，则把编码位置和窗窗Pointer是指向窗口中匹配串的指针，是指向窗口中匹配串的指针，Length表示匹配字符表示匹配字符的的3长度，长度， Characters是前向缓冲存储器中的不匹配的第是前向缓冲存储器中的不匹配的第1个字符。个字符。4口向前移口向前移( (Length+1) )个字符，然后返回到步骤个字符，然后返回到步骤2。n假设我们刚编码过的 10 个字符是：abcdbbccaa，即将编码的字符为：abaeaaabaee。n首先发现

54、，可以和要编码字符匹配的最首先发现，可以和要编码字符匹配的最长串为长串为 ab (off = 10, len = 2), ab 的下一个的下一个字符为字符为 a，我们输出三元组：，我们输出三元组：(10, 2 ) a。 LZ77LZ77算法算法62a b c d b b c c a a a b a e a a a b a e e窗口，搜索窗口，搜索缓冲区缓冲区a b a前向缓冲区前向缓冲区匹配指针匹配指针编码位置编码位置n现在将窗口向后滑动现在将窗口向后滑动3(2+1)3(2+1)个字符，窗口个字符，窗口中的内容为：中的内容为：dbbccaaabadbbccaaaba，剩余字符为，剩余字符为e

55、aaabaeeeaaabaee，下一个字符，下一个字符 e e 在窗口中没有在窗口中没有匹配，我们输出三元组：匹配，我们输出三元组：(0, 0 ) e(0, 0 ) e。a b c d b b c c a a a b a e a a a b a e eLZ77LZ77算法算法63n又将窗口向后滑动又将窗口向后滑动 1 1 个字符，其中内容变个字符，其中内容变为：为：bbccaaabaebbccaaabae。这时发现，要编码的。这时发现，要编码的 aaabae aaabae 在窗口中存在在窗口中存在(off = 6, len = 6)(off = 6, len = 6)，其后的字符为，其后的字符

56、为 e e，可以输出：，可以输出：(6,6)e(6,6)e。 a b c d b b c c a a a b a e a a a b a e eLZ77LZ77算法算法64a b c d b b c c a a a b a e a a a b a e en最后又将窗口向后滑动最后又将窗口向后滑动 7 7 个字符。这个字符。这样，我们将可以匹配的字符串都变成了样，我们将可以匹配的字符串都变成了指向窗口内的指针，并由此完成了对上指向窗口内的指针，并由此完成了对上述数据的压缩。述数据的压缩。LZ77LZ77算法算法6566例例:步骤位置匹配串字符输出11-A(0,0) A22AB(1,1) B34-

57、C(0,0) C45BB(2,1) B57ABC(5,2) C输出栏以输出栏以“( (Back_chars, Chars_length) Back_chars, Chars_length) Explicit_character”Explicit_character”格式输出。其中，格式输出。其中，( (Back_chars, Back_chars, Chars_length)Chars_length)是指向匹配串的指针，告诉译码器是指向匹配串的指针，告诉译码器“在这个窗在这个窗口中向后退口中向后退Back_charsBack_chars个字符然后拷贝个字符然后拷贝Chars_lengthCha

58、rs_length个字符到个字符到输出输出”，Explicit_characterExplicit_character是真实字符。例如，是真实字符。例如， “(5,2) (5,2) C”C”告诉译码器回退告诉译码器回退5 5个字符，然后拷贝个字符，然后拷贝2 2个字符个字符“AB”AB”位置123456789字符AABCBBABCLZ77LZ77算法算法67例例:步骤位置匹配串字符输出11-B(0,0) B22-A(0,0) A33BAB(2,2) B46BABC(5,3) C步骤位置匹配串字符输出11-A(0,0) A22AB(1,1) B34BC(1,1) C46BBA(3,2) A59A

59、BB(7,2) B位置123456789字符BABABBABC位置1234567891011字符AABBCBBAABB68 LZ77LZ77通过输出真实字符解决了在窗口中出现没通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面，一是空指针，二是编码冗余信息表现在两个方面，一是空指针，二是编码器可能输出额外的字符，这种字符是指可能包含在器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。下一个匹配串中的字符。LZSSLZSS算法以比较有效的方法解决这个问题，它算法以比较有效的方法解决

60、这个问题，它的思想是的思想是如果匹配串的长度比指针本身的长度长就如果匹配串的长度比指针本身的长度长就输出指针输出指针，否则就输出真实字符否则就输出真实字符。由于输出的压缩。由于输出的压缩数据流中包含有指针和字符本身，为了区分它们就数据流中包含有指针和字符本身，为了区分它们就需要有额外的标志位，即需要有额外的标志位，即IDID位。位。6969把编码位置置于输入数据流的开始位置把编码位置置于输入数据流的开始位置。1 1在前向缓冲存储器中查找与窗口中最长的匹配串在前向缓冲存储器中查找与窗口中最长的匹配串2 2判断匹配串长度判断匹配串长度LengthLength是否大于等于最小匹配串长度是否大于等于最