《静态图像压缩与编码技术.ppt》由会员分享，可在线阅读，更多相关《静态图像压缩与编码技术.ppt（95页珍藏版）》请在三一办公上搜索。
1、多媒体信息技术October 222023年10月,计算机与信息学院,主要内容,数据压缩概述经典数据压缩理论香农范诺与霍夫曼编码算术编码行程编码词典编码预测编码变换编码现代数据压缩理论小波分形多媒体数据压缩编码的国际标准,数字信号的压缩与编码是多媒体的核心技术和重要内容;音频信号的差分/自适应/LPC编码就是典型的压缩编码.,多媒体信息技术October 222023年10月,计算机与信息学院,数据压缩技术是多媒体技术的关键技术，也是多媒体技术发展的基础。在多媒体技术发展到的今天，大家已经知道数据是可以压缩的，但数据为什么要压缩？为什么能够实现数据压缩？理论基础与原理是什么？实现数据压缩的具体
2、方法有哪些？目前世界通用的数据压缩标准是什么？其规范与实现的途径又有哪些？,思 考,多媒体信息技术October 222023年10月,计算机与信息学院,4.1 多媒体数据压缩编码的重要性和分类,数据压缩就是在一定的精度损失条件下，以最少的数码表示信源所发出的信号,什么是数据压缩,多媒体信息技术October 222023年10月,计算机与信息学院,4.1.1 多媒体数据压缩编码的重要性,数据压缩的必要性多媒体信号的数据量巨大，如：一幅1024*1024真彩图有3MB5分钟的CD音乐有50.47MB90分钟的PAL视频数字化后有204.68GB为了节省存储空间和传输带宽，进行实时高质的多媒体通
3、信，必须对多媒体数据进行压缩编码,多媒体信源引起了“数据爆炸”,如果不进行数据压缩,传输和存储都难以实用化。,多媒体信息技术October 222023年10月,计算机与信息学院,4.1.2 多媒体数据压缩的重要性,1分钟数字音频信号需要的存储空间,多媒体信息技术October 222023年10月,计算机与信息学院,1分钟数字视频信号需要的存储空间,4.1.2 多媒体数据压缩的重要性,多媒体信息技术October 222023年10月,计算机与信息学院,数据压缩的好处,时间域压缩迅速传输媒体信源频率域压缩并行开通更多业务空间域压缩降低存储费用能量域压缩降低发射功率,多媒体信息技术Octobe
4、r 222023年10月,计算机与信息学院,4.1.2 多媒体数据压缩的可能性,声音、视频、图像数据表示有很大的压缩潜力，多媒体数据和人类的感觉存在着各种冗余，如：空间冗余：在同一幅图像中，规则物体和规则背景的表面物理特性具有相关性，这些相关性的光成像结果在数字化图像中就表现为数据冗余。,压缩的可能,多媒体信息技术October 222023年10月,计算机与信息学院,4.1.2 多媒体数据压缩的可能性,时间冗余：时间冗余反映在图像序列中就是相邻帧图像之间有较大的相关性，一帧图像中的某物体或场景可以由其它帧图像中的物体或场景重构出来。音频的前后样值之间也同样有时间冗余。,F2,A,F1,A,多
5、媒体信息技术October 222023年10月,计算机与信息学院,4.1.2 多媒体数据压缩的可能性,听觉冗余：人耳对不同频率的声音的敏感性是不同的，并不能察觉所有频率的变化，对某些频率不必特别关注，因此存在听觉冗余。信息熵冗余：信源编码时，当分配给第i个码元类的比特数b(yi)=log pi，才能使编码后单位数据量等于其信源熵，即达到其压缩极限。但实际中各码元类的先验概率很难预知，比特分配不能达到最佳。实际单位数据量dH(S)，即存在信息冗余熵。,多媒体信息技术October 222023年10月,计算机与信息学院,4.1.2 多媒体数据压缩的可能性,视觉冗余：人眼对于图像场的注意是非均匀
6、的，人眼并不能察觉图像场的所有变化。事实上人类视觉的一般分辨能力为26灰度等级，而一般图像的量化采用的是28灰度等级，即存在着视觉冗余。结构冗余：图象有非常强的纹理结构。如草席图结构上存在冗余。,多媒体信息技术October 222023年10月,计算机与信息学院,4.1.2 多媒体数据压缩的可能性,知识冗余：图像的理解与某些基础知识有关。例:人脸的图像有同样的结构：嘴的上方有鼻子，鼻子上方有眼睛，鼻子在中线上 其它冗余：图象空白的非定长性。,多媒体信息技术October 222023年10月,计算机与信息学院,4.1.3 多媒体数据压缩技术的性能指标,数据压缩技术的性能指标有三个关键参数评价
7、一个压缩系统压缩比图象质量压缩和解压的速度另外，也必须考虑每个压缩算法所需的硬件和软件。,多媒体信息技术October 222023年10月,计算机与信息学院,4.1.3 多媒体数据压缩技术的性能指标,压缩比压缩性能常常用压缩比定义输入数据和输出数据比 例一幅512480pixels图像，24bit/pixel 输入512480(24/8)=737280 byte 输出15000 byte 压缩比7372801500049,多媒体信息技术October 222023年10月,计算机与信息学院,4.1.3 多媒体数据压缩技术的性能指标,图象质量无损压缩（图象质量不变）有损压缩：失真情况很难量化，
8、只能对测试的图象进行估计。模拟图象质量的指标：信噪比、分辨率、颜色错，但必须在观察了实际图象以后。,多媒体信息技术October 222023年10月,计算机与信息学院,4.1.3 多媒体数据压缩技术的性能指标,压缩/解压速度在许多应用中，压缩和解压缩可能不同时用，所以，压缩、解压速度分别估计。静态图象中，压缩速度没有解压速度严格；动态图象中，压缩、解压速度都有要求，因为需实时地从摄像机或VCR中抓取动态视频。,多媒体信息技术October 222023年10月,计算机与信息学院,4.1.4 多媒体数据压缩的硬、软件系统,硬、软件系统有些压缩、解压工作可用软件实现。一般地讲，设计系统时必须充分
9、考虑：算法复杂 压缩解压过程长算法简单 压缩效果差目前有些特殊硬件可用于加速压缩解压。硬接线系统速度快，但各种选择在初始设计时已确定，一般不能更改。因此在设计硬接线压缩/解压系统时必须先将算法标准化。,多媒体信息技术October 222023年10月,计算机与信息学院,多媒体数据压缩技术,数据压缩(data compression)与信号编码(signal coding)往往含义相同压缩(compress)解压缩/还原/重构(decompress)编码(encode/coding)解码/译码(decode)相关学科：信息论、数学、信号处理、数据压缩、编码理论和方法,多媒体信息技术Octobe
10、r 222023年10月,计算机与信息学院,无损压缩是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。,4.1.5 数据压缩技术的分类,多媒体信息技术October 222023年10月,计算机与信息学院,4.1.5 数据压缩技术的分类（2）,多媒体信息技术October 222023年10月,计算机与信息学院,4.1.5 数据压缩技术的
11、分类（3）,1.熵编码熵编码(entropy encoding)是一类利用数据的统计信息进行压缩的无语义数据流的无损编码。它是基于平均信息量的技术把所有的数据当作比特序列，而不根据压缩信息的类型优化压缩。如RLE、LZW、Huffman编码2.信源编码（信）源编码(source coding)是一类利用信号原数据在时间域和频率域中的相关性和冗余进行压缩的有语义编码。种类繁多，可进一步分为预测编码：利用先前和现在的数据对在时间或空间上相邻的下面或后来的数据进行预测，从而达到压缩的目的。如DM、ADPCM变换编码：采用各种数学变换方法，将原时间域或空间域的数据变换到频率域或其他域，利用数据在变换域
12、中的冗余或人类感觉的特征来进行压缩。如DCT、DWT分层编码：将原数据在时空域或频率域上分成若干子区域，利用人类感觉的特征进行压缩编码，然后再合并。如子采样、子带编码其他编码：如矢量量化、运动补偿、音感编码,多媒体信息技术October 222023年10月,计算机与信息学院,4.1.5 数据压缩技术的分类（4）,4.混合编码混合编码(hybrid coding)=熵编码+源编码大多数压缩标准都采用混合编码的方法进行数据压缩，一般是先利用信源编码进行有损压缩，再利用熵编码做进一步的无损压缩。如H.261、H.263、JPEG、MPEG常见,多媒体信息技术October 222023年10月,计
13、算机与信息学院,4.2 压缩编码研究史（1）,1843年莫尔斯（Morse）的电报码是最原始的变长码数据压缩实例。1938年里夫斯（Reeves）、1946年德劳雷恩（E.m.Delorain）以及贝尔公司的卡特勒（C.C.Cutler）分别发明了脉冲编码调制（Pulse Code Modulation，PCM）、增量调制（Delta Modulation，）以及差分脉冲编码调制（Differential PCM，DPCM）。,多媒体信息技术October 222023年10月,计算机与信息学院,4.2 压缩编码研究史（2）,1948年香农（C.E.Shannon）在其经典论文“通信的数学原理
14、”中首次提到信息率失真函数概念，1959年又进一步确立了率失真理论，从而奠定了信源编码的理论基础。1948年提出电视信号数字化后，就开始了图像压缩编码的研究工作。1952年霍夫曼(D.A.Huffman)给出最优变长码的构造方法。同年贝尔实验室的奥利弗(B.M.Oliver)等人开始研究线性预测编码理论；1958年格雷哈姆(Graham)用计算机模拟法研究图像的DPCM编码方法；1966年奥尼尔（J.B.ONeal）对比分析了DPCM和PCM，又于1969年进行了线性预测的实验。,多媒体信息技术October 222023年10月,计算机与信息学院,4.2 压缩编码研究史（3）,20世纪60年
15、代，科学家们也开始探索比预测编码效率更高的编码方法。包括KL变换、傅立叶变换等正交变换。1968年安德鲁斯（H.C.Andrews）等人采用二维离散傅立叶变换(2D-DFT)提出了变换编码。此后相继出现了沃尔什-哈达玛（Walsh-Hadamard）变换、斜变换(Slant变换，由Enomoto和Shibata引入)、K-L变换、离散余弦变换（DCT）等。1976年美国贝尔系统的克劳切(R.E.Crochjiere)等人引入了语音的子带编码，1985年奥尼尔（S.D.ONeil）将子带编码推广到对图像的编码。,多媒体信息技术October 222023年10月,计算机与信息学院,4.2 压缩编
16、码研究史（4）,1983年瑞典的Forchheimer 和Fahlander提出了基于模型图像编码（Model-Based Coding）。1986年，Meyer在理论上证明了一维小波函数的存在，创造性地构造出具有一定衰减特性的小波函数。1987年Mallat提出了多尺度分析的思想及多分辨率分析的概念，成功地统一了在此之前各种具体小波的构造方法，提出了相应的快速小波算法Mallat算法，并把它有效地应用于图像分解和重构；1989年，小波变换开始用于多分辨率图像描述。,多媒体信息技术October 222023年10月,计算机与信息学院,4.2 压缩编码研究史（5）,1988年美国Georgia
17、理工学院的M.F.Barnsley在BYTE上发表了分形压缩方法，1992年A.Jacquin实现分块迭代函数系统（PIFS），完善了分形编码压缩方法。1988年在图像压缩编码的发展历史中是极为重要的一年。几十年研究的成果集中表现在确定了H.261和JPEG两个建议的原理框架，奠定了20世纪90年初相继提出的MPEG-1、MPEG-2、H.263等标准的基础。,多媒体信息技术October 222023年10月,计算机与信息学院,4.2 压缩编码研究史（6）,1991年3月，“联合图片专家组”（JPEG，Joint Photographic Expert Group）提出JPEG标准草案，19
18、94年正式通过（ISO 10918）。1991年为二值图像编码制订了JBIG标准（ISO 11544）。新的JPEG版本是JPEG-LS（ISO/IEC 14495，1999），和JPEG 2000（ISO/IEC 15444，等同的ITU-T编号T.800），于1999年3月形成工作草案，2000年正式颁布的。JPEG的这些标准主要应用于静止图像处理。H.263(H.261 P x 64)涉及低分辨率的视频序列。它可以与为ISDN和移动通信开发的音频编码标准一起实现，这些标准已成为CCITT标准。,多媒体信息技术October 222023年10月,计算机与信息学院,4.2 压缩编码研究史（
19、7）,1992年，“运动图片专家组”（MPEG，Moving Picture ExpertGroup）提出了“用于数字存储媒体运动图像及其伴音率为1.5Mbit/s的压缩编码”，简称为MPEG-1，作为ISO CD11172号建议通过，1993年正式通过。1993年提出MPEG-2标准草案，1994年正式通过（ISO/IEC 13818，视频部分为ITU-T H.262），处理能力可达广播级水平。MPEG-2标准兼容MPEG-1标准，适应于1.5Mbit/s 80Mbit/s编码范围。MPEG-2标准也是DVD和高清晰度电视（HDTV）全数字方案所采用的数据压缩标准。,多媒体信息技术Octob
20、er 222023年10月,计算机与信息学院,4.2 压缩编码研究史（8）,1995年1月，国际标准化组织ITU-TLBC工作组为极低数码率可视电话（VeryLowBitRateVisualTelephony）的工作形成了H.263视频压缩编码草案。1997年11月提出了MPEG-4用于极低数码率数据压缩，1999年MPEG-4形成国际标准。又一个MPEG标准MPEG-7，是“多媒体内容描述接口”，在2001年正式颁布。目前正在开发的新的MPEG-21。,多媒体信息技术October 222023年10月,计算机与信息学院,4.3 量化,量化处理是使数据比特率下降的一个强有力的措施。脉冲编码调
21、制（PCM）的量化处理是采样之后进行，从理论分析的角度，图像灰度值是连续的数值，而我们通常看到的是以（0255）的整数表示图像灰度，这是经A/D变换后的以256级灰度分层量化处理了的离散数值，这样可以用log2256=8比特表示一个图像像素的灰度值，或色差信号值。,4.4.1 量化原理,多媒体信息技术October 222023年10月,计算机与信息学院,4.3 量化,数据压缩编码中的量化处理，不是指A/D变换后的量化，而是指以PCM码作为输入，经正交变换、差分、或预测处理后，熵编码之前，对正交变换系数、差值或预测误差的量化处理。量化输入值的动态范围很大，需要以多的比特数表示一个数值，量化输出
22、只能取有限个整数，称作量化级，希望量化后的数值用较少的比特数便可表示。每个量化输入被强行归一到与其接近的某个输出，即量化到某个级。量化处理总是把一批输入，量化到一个输出级上，所以量化处理是一个多对一的处理过程，是个不可逆过程，量化处理中有信息丢失，或者说，会引起量化误差（量化噪声）。,4.4.1 量化原理,多媒体信息技术October 222023年10月,计算机与信息学院,4.3 量化,量化器的设计要求 通常设计量化器有下述两种情况：给定量化分层级数，满足量化误差最小。限定量化误差，确定分层级数，满足以尽量小的平均比特数，表示量化输出。,4.4.2 标量量化器的设计,多媒体信息技术Octob
23、er 222023年10月,计算机与信息学院,4.3 量化,量化方法有标量量化和矢量量化之分，标量量化又可分为:均匀量化非均匀量化自适应量化,4.4.2 标量量化器的设计,多媒体信息技术October 222023年10月,计算机与信息学院,4.3 量化,均匀量化特性曲线,非均匀量化特性曲线,多媒体信息技术October 222023年10月,计算机与信息学院,4.3 量化,矢量量化编码是近年来图像、语音信号编码技术中颇为流行的一种新型量化编码方法。矢量量化编码方法一般是有失真编码方法。矢量量化的名字是相对于标量量化而提出的。对于PCM数据，一个数一个数地进行量化叫标量量化。若对这些数据分组，
24、每组K个数构成一个K维矢量，然后以矢量为单元，逐个矢量进行量化，称矢量量化。,4.4.3 矢量量化,矢量量化编码解码框图,多媒体信息技术October 222023年10月,计算机与信息学院,4.4 常用多媒体压缩方法,一编码准备模数转换(A/D)：A/D连续模拟信号 离散数字信号采样/量化预处理：对得到的初始数字信号进行必要的处理，包括过滤、去噪、增强、修复等，以达到除去数据中的不必要成分、提高信号的信噪比、修复数据的错误等目的,编码过程,多媒体信息技术October 222023年10月,计算机与信息学院,编码与解码,A/D 预处理 压缩多媒体信号 数字信号 处理过的数字信号 压缩数据(子
25、)采样/量化 过滤/去噪/增强/修复源编码/熵编码存储 解码D/A 压缩数据 重构的数字信号 显示/播放传输 还原/重构(插值),二编解码过程,多媒体信息技术October 222023年10月,计算机与信息学院,熵编码,信息量和信息熵 图像的概率分布、信息量和信息熵之间有什么关系？在图像编码压缩理论研究中，为什么要引入信息论中“熵”值的概念，有什么重要意义？这是我们下面需要说明的问题。,信息论中的信源编码理论解决的主要问题：（1）数据压缩的理论极限（2）数据压缩的基本途径,多媒体信息技术October 222023年10月,计算机与信息学院,熵编码,编码器,信源(消息集),编码输出集(接收端
26、),X=x1,x2,xn,Z=z1,z2,zn,符号集Am=a1,a2,am,编码器模型图,其中X是消息集,由几个信号单元xj构成（j=1,2,n）Z是输出集，由几个码字zj构成（j=1,2,n），zj与xj一一对应。Am是符号集，由m个码元ai构成(i=1,2,m)，符号集中的码元组成输出码字。,多媒体信息技术October 222023年10月,计算机与信息学院,熵编码,信息熵为信源的平均信息量（不确定性的度量）熵编码是一类利用数据的统计信息进行压缩的无语义数据流的无损编码 本节在了解熵定义的基础上，讨论若干常用的熵编码算法，内容有：熵 Shannon-Fano编码 Huffman编码 算
27、术编码 RLE LZW算法,多媒体信息技术October 222023年10月,计算机与信息学院,4.4.1 熵编码,熵(entropy)本来是物理的热力学中用来度量热力学系统无序性的(热力学第二定律：孤立系统内的熵恒增)：(S为熵、Q为热量、T为绝对温度)对可逆过程，(孤立系统)信息熵的概念是香农(Shannon仙农)于1948年在他创建的信息论中引进的，用来度量信息中所含的信息量：其中，H为信息熵（单位为bit），S为信源，pi为符号si在S中出现的概率,多媒体信息技术October 222023年10月,计算机与信息学院,仙农信息论把一个事件（字符s1）所携带的信息量定义为：I(s1)=
28、log2(1/p)=-log2 p(bit)其中p为事件发生（字符出现）的概率I(s1)即随机变量X取值为s1时所携带的信息量,多媒体信息技术October 222023年10月,计算机与信息学院,信息熵H为自信息量I：的均值如果将信源所有可能事件信息量进行平均就得到信息的熵(熵就是平 均信息量)。例如，一幅用256级灰度表示的图像，如果每一个象素点灰度的概率均为pi=1/256，则即编码每一个象素点都需要8位(I)，平均每一个象素点也需要8位(H),多媒体信息技术October 222023年10月,计算机与信息学院,4.4.1 熵编码,熵的大小与信源的概率模型有着密切的关系。最大离散熵定理
29、：当与信源对应的字符集中的各个字符为等概率分布时，熵具有极大值log2m。m为字符集中字符个数信源均含有的平均信息量(熵),就是进行无失真编码的理论极限。,多媒体信息技术October 222023年10月,计算机与信息学院,4.4.1 熵编码,信源均含有的平均信息量(熵),就是进行无失真编码的理论极限。信源中或多或少的含有自然冗余。对于同一个信源其总的信息量是不变的，如果能够通过某种变换（编码），使信源尽量等概率分布，则每个输出符号所独立携带的信息量增大，那么传送相同信息量所需要的序列长度就越短。信源的冗余度隐含在信源符号的非等概率 分布之中。只要H（S）小于log2m，就存在数据压缩的可能
30、,多媒体信息技术October 222023年10月,计算机与信息学院,4.4.2 Shannon-Fano编码,按照Shannon提出的信息理论，1948年和1949年分别由Shannon和Fano描述和实现了一种被称之为香农-范诺(Shannon-Fano)算法的编码方法，是一种变码长的符号编码Shannon-Fano算法采用从上到下的方法进行编码：首先按照符号出现的概率排序，然后从上到下使用递归方法将符号组分成两个部分，使每一部分具有近似相同的频数，在两边分别标记0和1，最后每个符号从顶至底的0/1序列就是它的二进制编码,多媒体信息技术October 222023年10月,计算机与信息学
31、院,例1,例有一幅40个像素组成的灰度图像，灰度共有5级，分别用符号A，B，C，D，E表示，40个像素出现不同灰度的结果如下表所示。如果用3个位表示5个等级的灰度值，编码这幅图像总共需要120位。按照shannon的理论，这幅图像的熵为：这就是说每个符号用2.196位表示，共需87.84位。压缩比约为3/2.196 1.37:1。,多媒体信息技术October 222023年10月,计算机与信息学院,按照Shannon-Fano算法，先按照符号出现的频度或概率排序：A、B、C、D、E，然后分成次数相近左右两个部分:AB(22)与CDE(18)，并在两边分别标记0和1,按照这种方法进行编码所需总
32、位数为91，实际的压缩比为120:91=1.3:1。,多媒体信息技术October 222023年10月,计算机与信息学院,例2,有一幅60个象素组成的灰度图像，灰度共有5级，分别用符号A、B、C、D和E表示，60个象素中各级灰度出现次数见下表如果直接用二进制编码，则5个等级的灰度值需要3位表示，也就是每个象素用3位表示，编码这幅图像总共需要60*3=180位。按照香农理论，这幅图像的熵为H=(20/60)log2(60/20)+(10/60)log2(60/10)+(10/60)log2(60/10)2.189这就是说平均每个符号用2.189位表示就够了，60个象素共需用131.33位，压缩
33、比约为3/2.189 1.37:1。,多媒体信息技术October 222023年10月,计算机与信息学院,然后类似地再将AB分成A(20)与B(15)、BEC分成B(10)与EC(15)，最后再把EC分成E(10)与C(5)：,按照Shannon-Fano算法，先按照符号出现的频度或概率排序：A、D、B、E、C，然后分成次数相近左右两个部分AD(35)与BEC(25)，并在两边分别标记0和1,多媒体信息技术October 222023年10月,计算机与信息学院,Shannon-Fano算法举例表,按照这种方法进行编码得到的总位数为135，实际的压缩比为180/135=4/31.33:1,多媒
34、体信息技术October 222023年10月,计算机与信息学院,4.4.3 Huffman编码,Huffman（哈夫曼/赫夫曼/霍夫曼）在1952年提出了另一种从下到上的编码方法，是一种统计最优的变码长符号编码，让最频繁出现的符号具有最短的编码Huffman编码的过程=生成一棵二叉树（H树）树中的叶节点为被编码符号及其概率中间节点为两个概率最小符号（串）的并所构成的符号串及其概率所组成的父节点根节点为所有符号之串及其概率1,多媒体信息技术October 222023年10月,计算机与信息学院,具体编码步骤,(1)将符号按概率从小到大顺序从左至右排列叶节点(2)连接两个概率最小的顶层节点来组成
35、一个父节点，并在到左右子节点的两条连线上分别标记0和1(3)重复步骤2，直到得到根节点，形成一棵二叉树(4)从根节点开始到相应于每个符号的叶节点的0/1串，就是该符号的二进制编码创建霍夫曼表。压缩编码时，将码值用码字代替。解码时，将码字用码值代替。由于符号按概率大小的排列既可以从左至右、又可以从右至左，而且左右分枝哪个标记为0哪个标记为1是无关紧要的，所以最后的编码结果可能不唯一，但这仅仅是分配的代码不同，而代码的长度是相同的,多媒体信息技术October 222023年10月,计算机与信息学院,Huffman编码例(2),多媒体信息技术October 222023年10月,计算机与信息学院,
36、压缩比也为180/135=4/3 1.33:1,多媒体信息技术October 222023年10月,计算机与信息学院,例：已知信源符号的概率分别为：请对该信源序列做霍夫曼编码。,例3,例2,多媒体信息技术October 222023年10月,计算机与信息学院,香农-范诺编码与哈夫曼编码,它们都属于不对称、无损、变码长的熵编码。码长虽然都是可变的，但却都不需要另外附加同步代码(即在译码时分割符号的特殊代码)。如果事先编写出一本解释各种代码意义的“词典”，即码簿(H表)，那么就可以根据码簿一个码一个码地依次进行译码两个问题值得注意：没有错误保护功能在译码时，如果码串中有哪怕仅仅是1位出现错误，则不
37、但这个码本身译错，而且后面的码都会跟着错。称这种现象为错误传播，计算机对这种错误也无能为力，不能知道错误出在哪里，更谈不上去纠正它不能随机定位因为是可变长度码，所以很难在压缩文件中直接对指定音频或图像位置的内容进行译码，这就需要在存储代码之前加以考虑与香农-范诺编码相比，哈夫曼编码方法的编码效率一般会更高一些。尽管存在上面这些问题，但哈夫曼编码还是得到了广泛应用,多媒体信息技术October 222023年10月,计算机与信息学院,H表,利用哈夫曼方法进行编解码，在编码时需要计算构造H表，存储和传输时需要存储和传输H表，解码时则需要查H表有时为了加快编码速度、减少存储空间和传输带宽，可以对多媒
38、体数据使用标准的H表，但其压缩率一般比计算造表稍低 如果只关心编码速度、存储空间和传输带宽，可以采用标准H表方法；如果更关心压缩质量和压缩比，则可以自己计算造H表即使是计算造表，也一般只对高频符号计算编码，而对其他符号则直接编码。这种方法尤其适用于有大量不同的输入符号，但只有少数高频符号的情况,多媒体信息技术October 222023年10月,计算机与信息学院,霍夫曼表（H表）,多媒体信息技术October 222023年10月,计算机与信息学院,静态Huffman编码的缺点,上述所介绍的Huffman编码算法又称静态Huffman编码在静态霍夫曼编码中，要构造编码树必须提前统计被编码对象中
39、的符号出现概率，因此必须对输入符号流进行两遍扫描，第一遍统计符号出现概率并构造编码树，第二遍进行编码，这在很多实际应用的场合中之不能接受的。其次，在存储和传送霍夫曼编码时，必须先存储和传送霍夫曼编码树（表）。再次，静态编码树构造方案不能对输入符号流的局部统计规律变化做出反应。这些问题使得静态霍夫曼编码在实际中并未得到广泛的应用。,多媒体信息技术October 222023年10月,计算机与信息学院,自适应哈夫曼编码,自适应Huffman编码方案不需要事先扫描输入符号流，而是随着编码的进行同时构造Huffman树，因此，只需要进行一次扫描即可。在接收端伴随着解码过程同时进行着编码树的构造。自适应
40、霍夫曼编码解决了静态编码树所面临的主要问题，因此在实际领域比如在高质量的图像和视频流传输中获得了广泛的应用。自适应哈夫曼编码(adaptive Huffman coding)，不需要存储和传输H表，而是按与编码严格一致的方法建立同样的H表这种编码方案对符号的统计也动态进行，随着编码的进行，同一个符号的编码可能发生改变（变得更长或更短）,多媒体信息技术October 222023年10月,计算机与信息学院,4.4.4 算术编码,算术编码(arithmetic coding)是由Langdon于1984年提出的，从信息论上讲是与Huffman编码一样的最优变码长的熵编码。其主要优点是克服了Huff
41、man编码必须为整数位，这与实数的概率值相差大的缺点。如在Huffman编码中，本来只需要0.1位就可以表示的符号，必须用1位来表示，结果造成10 倍的浪费。算术编码的解决办法是，不用二进制代码来表示符号，而改用0，1)中的一个宽度等于其出现概率的实数区间来表示一个符号，符号表中的所有符号刚好布满整个0，1)区间（概率和为1，不重不漏）。把输入符号串（数据流）映射成0，1)区间中的一个实数值,多媒体信息技术October 222023年10月,计算机与信息学院,编码方法,符号串编码：将串中使用的符号表按原编码（如字符的ASCII编码、数字的二进制编码）从小到大顺序排列成表。计算表中每种符号si
42、出现的概率pi，然后依次根据这些符号概率大小pi来确定其在0,1)期间中对应的小区间范围xi,yi)：其中，p0=0。显然，符号si所对应的小区间的宽度就是其概率pi：,多媒体信息技术October 222023年10月,计算机与信息学院,输入串编码：设串中第j个符号cj为符号表中的第i个符号si，则可根据si在符号表中所对应区间的上下限xi和yi，来计算编码区间Ij=lj,rj)：其中，dj=rj-lj为区间Ij的宽度，初值l0=0、r0=1、d0=1。显然，lj而dj与rj串的最后一个符号所对应区间的下限ln就是该符号串的算术编码值例如：输入符号串为“helloworld”（10个字符），
43、符号表含7个符号，按字母顺序排列，容易计算它们各自出现概率和所对应的区间。下表是符号表及其符号的概率和对应区间,多媒体信息技术October 222023年10月,计算机与信息学院,符号表,多媒体信息技术October 222023年10月,计算机与信息学院,编码过程表,编码输出为l10=0.214615788,多媒体信息技术October 222023年10月,计算机与信息学院,解码方法,由符号表（包括符号对应的概率与区间）和实数编码ln，可以按下面的解码算法来重构输入符号串：设v1=ln=码值若vj xi,yi)cj=si,j=1,n vj+1=(vj-xi)/pi,j=1,n-1,多媒体
44、信息技术October 222023年10月,计算机与信息学院,解码过程表,重构输入符号串为v10=“helloworld”,多媒体信息技术October 222023年10月,计算机与信息学院,需注意的几个问题,(1)由于实际计算机的浮点运算器不够长，可用定长的整数寄存器低进高出来接收码串，用整数差近似实数差来表示范围，但可能会导致误差积累。(2)算术编码器对整个消息只产生一个码字，这个码字是在间隔0,1)中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码(3)算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错,多媒体信息技术October 22
45、2023年10月,计算机与信息学院,4.4.5 RLE,RLE/RLC=run length encoding/coding 行程编码或游程长度编码。RLE视数字信息为无语义的字符序列(字节流)，对相邻重复的字符，用一个数字表示连续相同字符的数目(称为行程长度)，可达到压缩信息的目的。如未压缩的数据：ABCCCCCCCCDEFFGGG RLE编码：AB8CDEFF3GRLE确实是一种压缩技术，而且相当直观，也非常经济RLE所能获得的压缩比有多大，这主要是取决于图像本身的特点。如果图像中具有相同颜色的图像块越大，图像块数目越少，获得的压缩比就越高。反之，压缩比就越小译码时按照与编码时采用的相同规
46、则进行，还原后得到的数据与压缩前的数据完全相同。因此，RLE是无损压缩技术,多媒体信息技术October 222023年10月,计算机与信息学院,RLE与图像压缩,RLE压缩编码尤其适用于计算机生成的图像，对减少图像文件的存储空间非常有效RLE对颜色丰富的自然图像就显得力不从心，在同一行上具有相同颜色的连续像素往往很少，而连续几行都具有相同颜色值的连续行数就更少。如果仍然使用RLE编码方法，不仅不能压缩图像数据，反而可能使原来的图像数据变得更大这并不是说RLE编码方法不适用于自然图像的压缩，相反，在自然图像的压缩中（如JPEG）还真少不了RLE，只不过是不能单纯使用RLE一种编码方法，需要和其
47、他的压缩编码技术联合应用,多媒体信息技术October 222023年10月,计算机与信息学院,BMP中的RLE,在BMP文件中，对16色和256色的普通格式的位图可进行行程编码(RLE)压缩，编码由若干信息单位构成，每个信息单位有2个字节信息单位的第一个字节一般为同一色索引的象素数，这时第二个字节对BI_RLE8为一个颜色索引(8b)，对BI_RLE4为两个颜色索引（各4b，高4位为第一个象素，低4位为第二个象素）。即,多媒体信息技术October 222023年10月,计算机与信息学院,在信息单位的第一个字节为0时，第二个字节表示四类特殊意义：0线结束、1位图结束、2偏移（后跟的两个字节分
48、别表示从当前位置向右和向下偏移的象素数）、3255后跟的未压缩的象素（色索引）数（填充到双字节边界，不足时补0）。即,多媒体信息技术October 222023年10月,计算机与信息学院,BI_RLE8例,压缩数据解压数据03 04 04 04 04 05 06 06 06 06 06 06 00 03 45 56 67 00 45 56 67 02 78 78 78 00 02 05 01 右移5且下移1 02 78 78 78 00 00 行结束09 1E 1E 1E 1E 1E 1E 1E 1E 1E 1E 00 01 RLE位图结束,多媒体信息技术October 222023年10月,
49、计算机与信息学院,BI_RLE4例,压缩数据解压数据03 04 0 4 005 06 0 6 0 6 0 00 06 45 56 67 00 4 5 5 6 6 7 04 78 7 8 7 8 00 02 05 01 右移5且下移1 04 78 7 8 7 8 00 00 行结束09 1E 1 E 1 E 1 E 1 E 1 00 01 RLE位图结束,多媒体信息技术October 222023年10月,计算机与信息学院,4.4.6 LZW算法,1977年以色列Jakob Ziv和Abraham Lempel提出了一种基于词典编码的压缩算法，称为LZ77算法；1978年他们对该算法作了改进，称
50、为LZ78；1984年Terry A.Weltch又对LZ78进行了实用性修正，因此把这种编码方法称为LZW(Lempel-Ziv Walch)算法词典编码(dictionary encoding)的根据是数据本身包含有重复代码块这个特性。词典编码法的种类很多，归纳起来大致有两类：,多媒体信息技术October 222023年10月,计算机与信息学院,第一类词典算法,其想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。这种编码概念如下图所示：这类编码中的所有算法都是以LZ77算法为基础的,多媒体
