第6章图像压缩

1、1图像压缩图像压缩2本章内容v背景背景v数据冗余数据冗余v图像保真度准则图像保真度准则v压缩方法分类压缩方法分类v数据压缩模型数据压缩模型/流程流程v信息论基础信息论基础v压缩的发展（第一代、第二代）压缩的发展（第一代、第二代）v霍夫曼编码霍夫曼编码v行程编程行程编程v算术编码算术编码v无损预测编码（无损预测编码（DPCM）v图像压缩标准图像压缩标准3本次课内容v背景v数据冗余v图像保真度准则v压缩方法分类v数据压缩模型/流程v信息论基础4研究背景v信息传输方式发生了很大的改变信息传输方式发生了很大的改变v通信方式的改变通信方式的改变文字文字+语音语音图像图像+文字文字+语音语音v通信对象的改

2、变通信对象的改变人与人人与人人与机器，机器与机器人与机器，机器与机器5v图像的传输与存储中，其数据量的庞大图像的传输与存储中，其数据量的庞大,成为一个必须解决的问题成为一个必须解决的问题.而其中问题而其中问题最多的，也是最常用的包括了最多的，也是最常用的包括了数字视频数字视频信号和传真信号。信号和传真信号。v请大家计算，对于电视画面的分辨率请大家计算，对于电视画面的分辨率640640* *480480的彩色图像，的彩色图像，3 3字节，每秒字节，每秒3030帧，帧，则一秒钟的数据量是多少？则一秒钟的数据量是多少？ 640640* *480480* *2424* *30=221.12M bit3

3、0=221.12M bitv所以播放时，需要所以播放时，需要221Mbps221Mbps的通信回路。的通信回路。 6v实时传输：实时传输：v 在在10M带宽网上实时传输的话，需要压缩带宽网上实时传输的话，需要压缩到原来数据量的到原来数据量的0.045。v 即即1.08bit/pixel。v存储：存储： 1张张CD可存可存640Mv 如果不进行压缩，如果不进行压缩，1张张CD则仅可以存放则仅可以存放2.89秒的数据。秒的数据。v 存存2小时的信息则需要压缩到原来数据量小时的信息则需要压缩到原来数据量的的0.0004,即：约即：约0.001bit/pixel。7v传真数据量 如果只传送如果只传送2

4、 2值图像，以值图像，以200dpi200dpi的分辨率传的分辨率传输，一张输，一张A4A4稿纸的数据量为：稿纸的数据量为： 16541654* *23372337* *1=3865398 bit 1=3865398 bit v按目前按目前14.4K14.4K的电话线传输速率，需要传的电话线传输速率，需要传送的时间是：约送的时间是：约270270秒（秒（4.54.5分）分）8v由于通信方式和通信对象的改变带来的最大问由于通信方式和通信对象的改变带来的最大问题是：题是：v v给我们带来的一个难题，也给了我们一个机会：给我们带来的一个难题，也给了我们一个机会：v 9图像数据压缩的应用领域：图像数据

5、压缩的应用领域：1、办公自动化；、办公自动化；2、医学图像处理；、医学图像处理；3、卫星遥感遥测系统；、卫星遥感遥测系统；4、高清晰度电视、高清晰度电视HDTV；5、可视电话、会议电视；、可视电话、会议电视；6、移动多媒体图像及视频传输：、移动多媒体图像及视频传输： 彩信业务，手机视频；彩信业务，手机视频；凡是涉及到图像数据的传输、交换与存储的领域均要凡是涉及到图像数据的传输、交换与存储的领域均要求进行图像数据的压缩。求进行图像数据的压缩。10数据和信息v数据和信息之间给予明确的区分。数据和信息之间给予明确的区分。v实际上，数据是信息传送的手段。对相同数量的信实际上，数据是信息传送的手段。对相

6、同数量的信息可以以不同数量的数据表示。息可以以不同数量的数据表示。v术语术语“数据压缩数据压缩”指减少表示给定信息量所需的数指减少表示给定信息量所需的数据量。据量。v比如，有这样一种可能的情况，对于同一个故事可比如，有这样一种可能的情况，对于同一个故事可以叙述得冗长罗嗦，也可以说得简明扼要。如果两以叙述得冗长罗嗦，也可以说得简明扼要。如果两个不同的人用不同数量的词句讲述同样的故事，那个不同的人用不同数量的词句讲述同样的故事，那么这个故事就有了两个版本，且至少有一个版本包么这个故事就有了两个版本，且至少有一个版本包含了不必要的数据。这就是数据冗余。含了不必要的数据。这就是数据冗余。 11v你的妻

7、子，你的妻子，Helen，将于明天晚上，将于明天晚上6点零点零5分分在上海的虹桥机场接你。在上海的虹桥机场接你。v (23*2+10=56个半角字符个半角字符)v你的妻子将于明天晚上你的妻子将于明天晚上6点零点零5分在虹桥机分在虹桥机场接你场接你v (20*2+2=42个半角字符）个半角字符）v Helen将于明晚将于明晚6点在虹桥接你点在虹桥接你v (10*2+6=26个半角字符）个半角字符）结论：只要接收端不会产生误解，就结论：只要接收端不会产生误解，就可以减少承载信息的数据量。可以减少承载信息的数据量。12数据冗余的概念数据冗余的概念v我们从一些简单的例子来体会数据冗余我们从一些简单的例

8、子来体会数据冗余的概念。的概念。v在下面的例子中，用一种最好的方式来在下面的例子中，用一种最好的方式来发送一封电报。发送一封电报。13n描述语言描述语言1 1） “这是一幅这是一幅2 2* *2 2的图像，的图像，图像的第一个像素是红的，图像的第一个像素是红的，第二个像素是红的，第三第二个像素是红的，第三个像素是红的，第个像素是红的，第 四个像素是红的四个像素是红的”。 2 2）“这是一幅这是一幅2 2* *2 2的图的图 像，像，整幅图都是红色的整幅图都是红色的”。由此我们知道，整理图像的描述方法可由此我们知道，整理图像的描述方法可以达到压缩的目的。以达到压缩的目的。14A、图像彩色光谱空间

9、的冗余；、图像彩色光谱空间的冗余；B、视频图像信号在时间上的冗余；、视频图像信号在时间上的冗余；压缩的目的就是去除信息冗余压缩的目的就是去除信息冗余6.2.1 数据冗余数据冗余15数据冗余数据冗余v分类：编码冗余像素间冗余心理视觉冗余166.2.1-1.编码冗余v编码2，表示图像所需编码的平均比特数就减少为：17v确定公式准确的冗余水平：v图像的直方图如下：v编码2中最短的码字赋予图像中出现频率最高的灰度级 18像素间冗余1（1）空间冗余空间冗余：规则物体和规：规则物体和规则背景的表面物理特性具有相则背景的表面物理特性具有相关性。关性。空间冗余空间冗余时间冗余时间冗余（2）时间冗余时间冗余：序

10、列图像：序列图像像素的灰度级和颜色之间具像素的灰度级和颜色之间具有相关性，随机场模型有相关性，随机场模型19（3）结构冗余结构冗余：纹理结构：纹理结构（4）知识冗余知识冗余：人脸的固定结构。：人脸的固定结构。空间冗余、时间冗余又称空间冗余、时间冗余又称统计冗余统计冗余，将图像信，将图像信号作为概率信号时的统计特性。号作为概率信号时的统计特性。20 6.2.1-2、图像的空间冗余；、图像的空间冗余；-象素间冗余象素间冗余2相同的目标相同的目标相同的直方图相同的直方图象素间的相象素间的相关性不同关性不同21象素间冗余象素间冗余3v图图 (e)和和(f)显示了沿着每幅图像的某行线计算得到的各自的显示

11、了沿着每幅图像的某行线计算得到的各自的相关系数。这些系数是使用下式计算得到的：相关系数。这些系数是使用下式计算得到的：v另一种数据冗余的重要形式另一种数据冗余的重要形式一种图像中与像素间相关的一种图像中与像素间相关的直接关系。直接关系。因为任何给定像素的值可以根据与这个像素相邻因为任何给定像素的值可以根据与这个像素相邻的像素进行适当的预测的像素进行适当的预测，所以由单个像素携载的信息相对较，所以由单个像素携载的信息相对较少。单一像素对于一幅图像的多数视觉贡献是多余的；它的少。单一像素对于一幅图像的多数视觉贡献是多余的；它的值可以通过以与其相邻的像素值为基础进行推测。值可以通过以与其相邻的像素值

12、为基础进行推测。v许多命名，包括空间冗余、几何冗余和帧间冗余都用来表示许多命名，包括空间冗余、几何冗余和帧间冗余都用来表示这些像素间的依赖性。这些像素间的依赖性。226.2.1-3、图像的视觉心理冗余、图像的视觉心理冗余v产生这种现象的原因是由于眼睛对所有视觉信息感产生这种现象的原因是由于眼睛对所有视觉信息感受的灵敏度不同。在正常的视觉处理过程中各种信受的灵敏度不同。在正常的视觉处理过程中各种信息的相对重要程度不同。息的相对重要程度不同。v那些不十分重要的信息称做心理视觉冗余。那些不十分重要的信息称做心理视觉冗余。v这些冗余在不会削弱图像感知质量的情况下可以消这些冗余在不会削弱图像感知质量的情

13、况下可以消除。除。v由于消除心理视觉冗余数据会导致一定量信息的丢由于消除心理视觉冗余数据会导致一定量信息的丢失，所以这一过程通常称为失，所以这一过程通常称为“量化量化”。它表示将一。它表示将一个范围很广的输人值集合映射成有限的输出值个范围很广的输人值集合映射成有限的输出值23v图图 (a)显示了一幅具有显示了一幅具有256个灰度级的单色图像。图个灰度级的单色图像。图 (b)显示了将这幅图显示了将这幅图像均匀量化为像均匀量化为4比特或比特或16种灰度级后的结果。压缩率为种灰度级后的结果。压缩率为2：1。 v(c)说明充分利用人类视觉系统特性进行压缩。尽管这种量化过程的压缩说明充分利用人类视觉系统

14、特性进行压缩。尽管这种量化过程的压缩率还是只有率还是只有2：1，为减少假轮廓而增加了额外的开销，但减少了讨厌的，为减少假轮廓而增加了额外的开销，但减少了讨厌的颗粒状纹路。颗粒状纹路。 v方法：进行量化之前用一个伪随机数加到每个像素上将这些边缘拆散。方法：进行量化之前用一个伪随机数加到每个像素上将这些边缘拆散。24数据冗余压缩原理数据冗余压缩原理v由于一幅图像存在数据冗余和主观视觉冗余，我由于一幅图像存在数据冗余和主观视觉冗余，我们的压缩方式就可以从这两方面着手开展。们的压缩方式就可以从这两方面着手开展。v因为有因为有编码和像素数据冗余数据冗余，当我们将图像信息，当我们将图像信息的描述方式改变之

15、后，可以压缩掉这些冗余。的描述方式改变之后，可以压缩掉这些冗余。v因为有因为有主观视觉冗余主观视觉冗余，当我们忽略一些视觉不太，当我们忽略一些视觉不太明显的微小差异，可以进行所谓的明显的微小差异，可以进行所谓的“有损有损”压缩。压缩。25v如何评价图像编码中的解码图像与原始如何评价图像编码中的解码图像与原始图像之间的偏离程度？图像之间的偏离程度？v通过保真度通过保真度(逼真度逼真度)准则准则v两大类准则：客观保真度准则，主观保两大类准则：客观保真度准则，主观保真度准则真度准则26客观保真度准则客观保真度准则v当所损失的信息量可用编码输入图像与解当所损失的信息量可用编码输入图像与解码输出图像的函

16、数表示时，基于客观保真码输出图像的函数表示时，基于客观保真度准则的。度准则的。常用的准则有：常用的准则有：总误差总误差均方根误差均方根误差erms均方信噪比均方信噪比SNRrms27总误差总误差v图像大小为图像大小为MN像素像素v并令并令 f (x,y) 表示由对输入先压缩后解压缩表示由对输入先压缩后解压缩得到的得到的f(x，y)的估计量或近似量的估计量或近似量v两幅图像的总体误差为：两幅图像的总体误差为： 28均方根误差均方根误差erms29均方信噪比均方信噪比SNRrmsvf (x,y)含噪声的图像含噪声的图像v如果认为是初始图像和噪声信号如果认为是初始图像和噪声信号e(x，y)的和，的和

17、，则输出图像的均方信噪比用则输出图像的均方信噪比用SNRrms表示表示30主观保真度准则主观保真度准则v一般情况下，解压图像最终是依靠人的视觉来判断的，一般情况下，解压图像最终是依靠人的视觉来判断的，用主观保真度准则。所以，有时使用观察者的主观评用主观保真度准则。所以，有时使用观察者的主观评估衡量图像品质通常是更为适当的。估衡量图像品质通常是更为适当的。 如对电视图像质量进行绝对评价的尺度为如对电视图像质量进行绝对评价的尺度为评分评分评价评价说明说明1优秀的优秀的优秀的具有极高质量的图像优秀的具有极高质量的图像2好的好的 是可供观赏的高质量的图像，干扰并不令人讨厌是可供观赏的高质量的图像，干扰

18、并不令人讨厌 3可通过的可通过的 图像质量可以接受，干扰不讨厌图像质量可以接受，干扰不讨厌4边缘的边缘的图像质量较低，希望能加以改善，干扰有些讨厌图像质量较低，希望能加以改善，干扰有些讨厌5劣等的劣等的图像质量很差，尚能观看，干扰显著地令人讨厌图像质量很差，尚能观看，干扰显著地令人讨厌6不能用不能用图像质量非常之差，无法观看图像质量非常之差，无法观看31v(b)和和(c)的量化图像的的量化图像的erms误差分别为误差分别为6.93和和6.78。对应的。对应的SNRrms信噪比为信噪比为10.25和和10.39。尽管这些值很相近，但两。尽管这些值很相近，但两幅编码图像视觉品质的主观评估也许会是，

19、对图幅编码图像视觉品质的主观评估也许会是，对图 (b)中图像中图像为为“4-边缘的边缘的”等级，对图等级，对图 (c)中图像为中图像为“3-可通过的可通过的”等等级。级。 32压缩的分类v图像压缩编码的分类图像压缩编码的分类（1）无损编码）无损编码(哈夫曼编码、算术编码、行程编码哈夫曼编码、算术编码、行程编码)v又称为又称为信息保持编码信息保持编码。（2）有损编码）有损编码v常被称为常被称为保真度编码保真度编码。v预测编码：预测编码：DPCM差值脉冲编码调制法差值脉冲编码调制法(Differential Pulse Code Modulation), 运动补偿运动补偿v频率域方法：余弦变换编码

20、频率域方法：余弦变换编码v其他编码方法：矢量量化编码其他编码方法：矢量量化编码（3）特征抽取编码）特征抽取编码v是另一种是另一种有损编码有损编码。33图像压缩/解压缩流程图像信息源图像信息源图像预处理图像预处理图像信源图像信源编码编码信道编码信道编码调制调制信道传输信道传输解调解调信道解码信道解码图像信源图像信源解码解码显示图像显示图像346.2.3图像压缩模型图像压缩模型信源编信源编码器码器信道编信道编码器码器信道解信道解码器码器信源解信源解码器码器信息信息EncoderDecoder输入输入图像图像f(x,y)Removes inputredundanciesIncreasesthe no

21、iseimmunity编码器编码器356.2.3图像压缩模型图像压缩模型 v一个图像压缩系统包括两个不同的结构块：一个编码器一个图像压缩系统包括两个不同的结构块：一个编码器和一个解码器。图像和一个解码器。图像f(x，y)输人到编码器中。这个编码输人到编码器中。这个编码器可以根据输器可以根据输 入数据生成一组符号。在通过信道进行传入数据生成一组符号。在通过信道进行传输之后，将经过编码的表达符号送入解码器，经过重构输之后，将经过编码的表达符号送入解码器，经过重构后，就生成了输出图像后，就生成了输出图像 (x,y)。v编码器由一个消除输入冗余的信源编码器和一个用于增编码器由一个消除输入冗余的信源编码

22、器和一个用于增强信源编码器输出的噪声抗扰性的信道编码器构成。强信源编码器输出的噪声抗扰性的信道编码器构成。 v一个解码器包括一个信道解码器，它后面跟着一个信源一个解码器包括一个信道解码器，它后面跟着一个信源解码器。解码器。v信道编码器和解码器通过向信源编码数据中插入预制的信道编码器和解码器通过向信源编码数据中插入预制的冗余数据来减少信道噪声的影响。冗余数据来减少信道噪声的影响。 f36信源编码器/解码器 v第一阶段，转换器将输入数据转换为可以减少输入图像中像素间第一阶段，转换器将输入数据转换为可以减少输入图像中像素间冗余的格式。通常是可逆的并且有可能直接减少表示图像的数据冗余的格式。通常是可逆

23、的并且有可能直接减少表示图像的数据量。量。 v在第二阶段中，将转换程序的输出精度调整到与预设的保真度准在第二阶段中，将转换程序的输出精度调整到与预设的保真度准则相一致。减少了输则相一致。减少了输 入图像的心理视觉冗余。入图像的心理视觉冗余。v在第三阶段，符号编码器生成一个固定的或可变长编码用于表示在第三阶段，符号编码器生成一个固定的或可变长编码用于表示量化器输出。它用最短的码字表示出现频率最高的输出值，量化器输出。它用最短的码字表示出现频率最高的输出值， v信源解码器仅包含两部分：一个符号解码器和一个反向转换器。信源解码器仅包含两部分：一个符号解码器和一个反向转换器。 376.2.3-2 信道

24、编/解码器v背景：信道带有噪声或易于出现错误。背景：信道带有噪声或易于出现错误。v信道编码器和解码器通过向信源编码数据中信道编码器和解码器通过向信源编码数据中插入预制的冗余数据，即验证码。插入预制的冗余数据，即验证码。v由于信源编码器几乎不包含冗余，它对噪声由于信源编码器几乎不包含冗余，它对噪声传送有很高的敏感性。传送有很高的敏感性。v代表：海明码代表：海明码38信息理论信息理论（一）、信源空间概述（一）、信源空间概述信息论的基本前提是信息的产生可以被模拟为一个概率过程，信息论的基本前提是信息的产生可以被模拟为一个概率过程，这个过程可以用与我们的直觉相一致的方法度量。这个过程可以用与我们的直觉

25、相一致的方法度量。 1 1、信息：事物运动状态或存在方式的不确定性的描述；、信息：事物运动状态或存在方式的不确定性的描述；2 2、信源空间：随机符号及其出现概率的空间；、信源空间：随机符号及其出现概率的空间；3 3、信源的分类：、信源的分类：（1 1）、）、 连续信源连续信源离散信源离散信源混合信源；混合信源；（2 2）、无记忆信源）、无记忆信源有记忆信源（相关信源）有记忆信源（相关信源）有限有限长度记忆信源（长度记忆信源（MarkovMarkov信源）信源）39（二）、信息的度量（二）、信息的度量1、信息公理、信息公理（1）、信息由）、信息由不确定性程度不确定性程度进行度量；进行度量； 确定

26、事件的信息量为零。确定事件的信息量为零。（2）、不确定性程度）、不确定性程度越高越高信息量信息量越大越大；（3）、相互独立性与信息量可加性；）、相互独立性与信息量可加性； 独立事件的联合信息等于两个独立事件的信息总和。独立事件的联合信息等于两个独立事件的信息总和。 以事件概率为基础定义信息函数为：以事件概率为基础定义信息函数为： 此公式此公式 满足信息公理满足信息公理 )(log)(aPaI402、离散无记忆信源（、离散无记忆信源（DNMS）的信息量度量：）的信息量度量：（1）信源符号）信源符号 的的自信息量自信息量定义为：定义为：)(log)(iiaPaI(a)、非负性；、非负性；(b)、信

27、息量的单位：、信息量的单位：底为底为2时时单位为：比特（单位为：比特（bit）如果如果P(ai)=1/2，I(ai)=-log21/2=1比特。就是说，当两种出现概率相等的比特。就是说，当两种出现概率相等的事件发生时，传送的信息量是事件发生时，传送的信息量是1比特。这类情况的简单例子就是抛硬币比特。这类情况的简单例子就是抛硬币并传送结果并传送结果. 底为底为e时时单位为：奈特（单位为：奈特（Nat）底为底为10时时单位为：哈特单位为：哈特ia41（2）、信源平均自信息量（信息熵）、信源平均自信息量（信息熵）离散无记忆信源离散无记忆信源A的的平均自信息量平均自信息量（信息熵信息熵）定）定义为：义

28、为：miiimiiiaPaPaIaPAH11)(log)()()()(同理，图像熵的定义为：同理，图像熵的定义为：当灰度级集合当灰度级集合D中中di出现的概率相等时，熵具有最大值出现的概率相等时，熵具有最大值miiidpdpd）H1)(log)(v图像熵的含义：图像熵的含义：1.度量某消息包含的信息量：信息量越大，熵度量某消息包含的信息量：信息量越大，熵越大。越大。2.度量某事件发生的不确定性：不确定性越度量某事件发生的不确定性：不确定性越强，强， ，熵越大。，熵越大。3.度量某事件概率分布的分散性：分散性越度量某事件概率分布的分散性：分散性越强，强， ，熵越大。，熵越大。42433、平均码字

29、长、平均码字长v借助熵的概念可以定义量度任何特定码的性借助熵的概念可以定义量度任何特定码的性能的准则，即平均码字长度。能的准则，即平均码字长度。v其中其中i为灰度级为灰度级di所对应的码字长度。单位也所对应的码字长度。单位也是比特是比特/字符。字符。 miiidpN1)(444、编码效率、编码效率编码符号是在字母集合编码符号是在字母集合A=a1,a2,a3,an中选取的。如中选取的。如果编码后形成一个新的等概率的无记忆信源，字母数为果编码后形成一个新的等概率的无记忆信源，字母数为n，则它的最大熵应为则它的最大熵应为logn比特比特/符号。因此这是一个极限值。符号。因此这是一个极限值。如果如果H

30、(d)/ N=logn (N为平均码字长为平均码字长) ，则可以认为编码效，则可以认为编码效率已经达到率已经达到100%，如果，如果H(d)/N logn，则可认为编码效，则可认为编码效率较低。率较低。nNdHlog)(nNdHnNRdlog)(log1编码效率定义：编码效率定义：冗余度定义：冗余度定义：45二进制编码时N（平均码长）和H的关系v最好的编码结果是最好的编码结果是N等于或稍大于等于或稍大于H，这种状，这种状态的编码称为最佳编码。既不丢信息，又占态的编码称为最佳编码。既不丢信息，又占用比特数最少。用比特数最少。v NH时，存在无失真编码时，存在无失真编码v如果编码结果如果编码结果N

31、远远大于远远大于H，表明此编码方法，表明此编码方法效率低，占用比特数多。效率低，占用比特数多。v若若NH时，丢失信息，引起图像失真。时，丢失信息，引起图像失真。465、压缩比、压缩比v压缩比是衡量数据压缩程度的指标之一。目前压缩比是衡量数据压缩程度的指标之一。目前常用的压缩比定义为常用的压缩比定义为 v其中其中LB为源代码长度，为源代码长度，Ld为压缩后代码长度，为压缩后代码长度，Pr为压缩比。为压缩比。v压缩比的物理意义是被压缩掉的数据占据源数压缩比的物理意义是被压缩掉的数据占据源数据的百分比。当压缩比据的百分比。当压缩比Pr接近接近100%时压缩效时压缩效果最理想。果最理想。 %100Bd

32、BrLLLP476、互信息、互信息v信源编码输出为信源编码输出为bk给出的关于给出的关于ai的信息量究竟为多少呢？为此将的信息量究竟为多少呢？为此将引入另外一个信息量度互信息引入另外一个信息量度互信息 v对给定的两个离散信源对给定的两个离散信源X和和Y，Y中事件中事件bk的发生给出关于的发生给出关于X中事中事件件ai的互信息的互信息I(ai:bk)定义为：定义为：v其中，其中，p(ai|bk)表示信源编码输出为表示信源编码输出为bk，估计信源输入，估计信源输入为为ai的条件概率。的条件概率。I(ai|bk)称为条件自信息量，表示在发称为条件自信息量，表示在发现信源编码输出为现信源编码输出为bk

33、，对信源输入为，对信源输入为ai的不确定性的猜的不确定性的猜测或知道测或知道bk后后ai还还保留保留的信息量。的信息量。I(ai)表示表示ai的不确定的不确定性。两者值差即为性。两者值差即为bk解除的解除的ai不确定性的多少不确定性的多少，即是，即是在观察一个单一输出符号在观察一个单一输出符号bk时给出的关于时给出的关于ai的信息量。的信息量。 )()|(log)|()();(ikikiikiapbapbaIaIbaI48本节课内容v压缩的发展（第一代、第二代）v霍夫曼编码v行程编程49压缩发展v第一代压缩编码第一代压缩编码八十年代以前，主要是根据传统的信源编码方法。八十年代以前，主要是根据传

34、统的信源编码方法。v第二代压缩编码第二代压缩编码 八十年代以后，突破信源编码理论，结合分形、八十年代以后，突破信源编码理论，结合分形、模型基、神经网络、小波变换等数学工具，模型基、神经网络、小波变换等数学工具，充分充分利用视觉系统生理心理特性和图像信源的各种特利用视觉系统生理心理特性和图像信源的各种特性（与第一代编码的主要区别）性（与第一代编码的主要区别）。实现从。实现从“波形波形”编码到编码到“模型模型”编码的转变，以便获得更高压缩编码的转变，以便获得更高压缩比比。50像素编码像素编码变换编码变换编码预测编码预测编码位平面编码位平面编码增量调制增量调制熵编码熵编码算术编码算术编码DCTDCT

35、变换变换DPCMDPCM调制调制第一代压缩编码第一代压缩编码其他编码其他编码行程编码行程编码51子带子带编码编码模型编码模型编码分层分层编码编码分型编码分型编码第二代压缩编码第二代压缩编码子带和分层两种方法的基本原理为将图像分解到子带和分层两种方法的基本原理为将图像分解到不同的频带中（便于引入视觉特性）不同的频带中（便于引入视觉特性）,然后对不同频带的系数采用不同的压缩编码方法然后对不同频带的系数采用不同的压缩编码方法52压缩的分类v无损压缩编码哈夫曼编码哈夫曼编码算术编码算术编码行程编码行程编码v有损压缩编码预测编码：预测编码：DPCM，运动补偿，运动补偿频率域方法：余弦变换编码频率域方法：

36、余弦变换编码其他编码方法：矢量量化编码其他编码方法：矢量量化编码53v图像冗余无损压缩的原理图像冗余无损压缩的原理RGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGB16RGB从原来的从原来的1616* *3 3* *8=284bits8=284bits压缩为：压缩为：(1+3)(1+3)* *8=32bits8=32bits54v图像冗余有损压缩的原理图像冗余有损压缩的原理36353434343434323434333730343434343434343435343431343434343434343434343434343434343434343

37、43434343434253455无损压缩编码无损压缩编码v哈夫曼编码哈夫曼编码v游程编码游程编码v无损预测编码无损预测编码56变长最佳编码定理和唯一可译代码变长最佳编码定理和唯一可译代码-12kKi定理：在变长编码中，对出现概率大的信息符号赋予短码字，而对于出现概率小的信息符号赋予长码字。可以证明，如果码字长度严格按概率大小的逆序排列，则平均码字长度一定小于任何其他排列方式。：如果码字之间不加同步码，则要求编码序列唯一可译。：任何码字不能在其后面添加码元而形成其他码字，称为非续长代码。：任意有限长码字序列，只能唯一地分割成一个个码字。其充要条件是唯一可译编码非续长代码单义代码1。非续长代码一

38、定是单义代码，反之未必。瞬时可译瞬时可译唯一可译唯一可译变长编码的码字具有单义性和非续长性。变长编码的码字具有单义性和非续长性。57举例v唯一可译码（单义码）：如 W=0,10,11，对代码序列S=100111000，只能分割成10、0、11、10、0、0。v非续长代码：如W=0,10,100,111就不是非续长代码，其中“100”是“10”的续长。非续长代码一定是单义码，但单义码不一定是非续长代码。如 W=0,01是单义码，但又是续长代码。58哈夫曼编码哈夫曼编码v50年代提出，一种无损的统计编码方法v为了达到大的压缩率，提出了一种方法就是将在图像中出现频度大的像素值,给一个比较短的编码，将

39、出现频度小的像数值,给一个比较长的编码。v用变长的码使冗余量达到最小，用一棵二叉树来编码，使常出现的字符用较短的码表示，不常出现的字符用较长的码表示。v符合可变长度最佳编码定理。59v例：例：v aaaa bbb cc d eeeee fffffff v 4 3 2 1 5 7v如果不进行特殊的编码，按照图像像素的描述，需要的数如果不进行特殊的编码，按照图像像素的描述，需要的数据量为：据量为：v v 22*8=176 bits 60v aaaa bbb cc d eeeee fffffffv 4 3 2 1 5 7v v按照熵编码的原理进行编码：按照熵编码的原理进行编码：v f=0 e=10

40、a=110 b=1111 c=11100 d=11101v这里的编码规则是长短不一的异字头码这里的编码规则是长短不一的异字头码 61v由：由：v f=0 e=10 a=110 b=1111 c=11100 d=11101 v aaaa bbb cc d eeeee fffffffv数据量：数据量：7*1+5*2+4*3+3*4+2*5+1*5=56 bit v压缩率为：压缩率为：56/176=31 .8%62方法方法v首先求出图像中灰度分布的灰度直方图；首先求出图像中灰度分布的灰度直方图；v根据该直方图，对其按照分布概率从小到大根据该直方图，对其按照分布概率从小到大的顺序进行排列；的顺序进行排

41、列；v每一次从中选择出两个概率为最小的节点相每一次从中选择出两个概率为最小的节点相加，形成一个新的节点，构造一个称为加，形成一个新的节点，构造一个称为“Huffman树树”的二叉树；的二叉树；v对这个二叉树进行编码，就获得了对这个二叉树进行编码，就获得了Huffman编码码字。编码码字。63v例如：例如：aaaa bbb cc d eeeee fffffffv分布为：分布为：v a:4/22 b:3/22 c:2/22v d:1/22 e:5/22 f:7/22v排序为：排序为：v d, c, b, a, e, fv 1/22 2/22 3/22 4/22 5/22 7/2264cbafe7/

42、227/225/225/224/224/222/222/2210f=11 e=01 a=00 b=101 c=1001 d=1000d1/221/223/223/226/226/2222/2222/2213/2213/229/229/223/223/221010101065v对这个例子，计算出经过对这个例子，计算出经过Huffman编码后的编码后的数据为：数据为： v00000000101101101100110011000010101010111111111111111v 共共 7*2+5*2+4*2+3*3+2*4+1*4=53 bitv比前面我们给出的编码得到的比前面我们给出的编码得到的

43、56bit的数据量的数据量还小，压缩率为还小，压缩率为53/176=30.1%。aaaa bbb cc d eeeee fffffff66v1、缩减信源符合数量将概率从大到小排列，再将两、缩减信源符合数量将概率从大到小排列，再将两个概率最小的符号结合得到个概率最小的符号结合得到1个组合符号，如果剩下的个组合符号，如果剩下的符号多余符号多余2个，继续上述过程，直到只剩个，继续上述过程，直到只剩2个符号为止。个符号为止。给出一组初始信源的概率分布给出一组初始信源的概率分布符号符号a1a2a3a4a5a6概率概率0.10.40.060.10.040.3初始信源初始信源信源的消减步骤信源的消减步骤符号

44、符号概率概率123 4a20.4 0.4 0.4 0.4 0.6a60.3 0.3 0.3 0.3 0.4a10.1 0.1 0.2 0.3a40.1 0.1 0.1a30.06 0.1a50.04123467v2、对每个信源赋值先从、对每个信源赋值先从(消减到消减到)最小的信源开最小的信源开始，逐步回到初始信源，过程如表所示。对一个始，逐步回到初始信源，过程如表所示。对一个只有只有2个符号的信源，最短长度的二元码由符号个符号的信源，最短长度的二元码由符号0和和1组成，将它们赋予对应最右列组成，将它们赋予对应最右列2个概率的符号个概率的符号10码字码字0100 1码字码字011010001码字

45、码字01010100011001码字码字01011010100100011001码字码字0.04a50.10.06a30.10.10.1a40.30.20.10.1a10.40.30.30.30.3a60.60.40.40.40.4a24321概率概率符号符号对消减信源的赋值对消减信源的赋值初始信源初始信源1234请大家计算此编码的信息熵、平均码字长度、编码效率请大家计算此编码的信息熵、平均码字长度、编码效率（列出公式即可）（列出公式即可）68v哈夫曼编码效率哈夫曼编码效率信源熵为：信源熵为：H=-Pilog2Pi=-(0.4log20.4+0.3log20.3+2*0.1log20.1+0.

46、06log20.06+0.04log20.04)=2.14比特比特/符号符号69平均码字长度：平均码字长度：R=iPi码字码字长度长度R= iPi =0.41+0.3 2+0.1 3+0.1 4+0.06 5+0.04 5=2.2比特比特/符号符号编码效率：编码效率：=H/R(%)=H/R=2.14/2.2=0.973=97.3%70Huffman编码非续长性/单义性v这种编码是瞬时的，因为符号串中的每个码字无须这种编码是瞬时的，因为符号串中的每个码字无须参考后继符号就可以进行解码。参考后继符号就可以进行解码。v它又是惟一可解码的，因为任何符号串只能以一种它又是惟一可解码的，因为任何符号串只能

47、以一种方式进行解码。因此，任何霍夫曼编码的符号串，方式进行解码。因此，任何霍夫曼编码的符号串，可以通过从左到右的方式对串中每个符号进行分析可以通过从左到右的方式对串中每个符号进行分析来解码。来解码。v对编码串对编码串010100111100从左到右的扫描显示，第从左到右的扫描显示，第一个有效码字为一个有效码字为01010，这个编码的符号是，这个编码的符号是a3。下。下一个有效的编码是一个有效的编码是011，它所对应的符号为，它所对应的符号为a1。以。以这种方式持续下去得到的完整解码信息是这种方式持续下去得到的完整解码信息是a3a1a2a2a6。 71图像压缩vHuffman编码在图像压缩中的实

48、现编码在图像压缩中的实现v 我们知道，对一幅图像进行编码时，我们知道，对一幅图像进行编码时，如果图像的大小大于如果图像的大小大于256时，这幅图像时，这幅图像的不同的码字就有可能是很大，例如极的不同的码字就有可能是很大，例如极限为限为256个不同的码字。个不同的码字。 v 这时如果采用全局这时如果采用全局Huffman编码则编码则压缩效率不高。甚至与原来的等长编码压缩效率不高。甚至与原来的等长编码的数据量相同。的数据量相同。 72v常用的且有效的方法是：v 将图像分割成若干的小块，对每块进行独将图像分割成若干的小块，对每块进行独立的立的Huffman编码。例如：分成较小的子编码。例如：分成较小

49、的子块，就可以大大降低不同灰度值的个数块，就可以大大降低不同灰度值的个数（最多是（最多是64而不是而不是256）。）。738 8* *8 8分块的压缩分块的压缩率为率为47.27%47.27%1616* *1616分块的分块的压压缩缩率约为率约为61%61%全图的全图的压缩压缩率率为为91.47%91.47%74哈夫曼编码方法小结方法小结v首先求出图像中灰度分布的灰度直方图；首先求出图像中灰度分布的灰度直方图；v根据该直方图，对其按照分布概率从小到大根据该直方图，对其按照分布概率从小到大的顺序进行排列；的顺序进行排列；v每一次每一次从中选择出两个概率为最小的节点相从中选择出两个概率为最小的节点

50、相加，形成一个新的节点，构造一个称为加，形成一个新的节点，构造一个称为“Huffman树树”的二叉树；的二叉树；v对这个二叉树进行编码，就获得了对这个二叉树进行编码，就获得了Huffman编码码字。编码码字。75cbafe7/227/225/225/224/224/222/222/2210f=11 e=01 a=00 b=101 c=1001 d=1000d1/221/223/223/226/226/2222/2222/2213/2213/229/229/223/223/221010101076游程编码游程编码RLCv行程编码是一种最简单的，在某些场合是非常行程编码是一种最简单的，在某些场合是

51、非常有效的一种无损压缩编码方法。有效的一种无损压缩编码方法。v虽然这种编码方式的应用范围非常有限，但是虽然这种编码方式的应用范围非常有限，但是因为这种方法中所体现出的编码设计思想非常因为这种方法中所体现出的编码设计思想非常明确，所以在图像编码方法中都会将其作为一明确，所以在图像编码方法中都会将其作为一种典型的方法来介绍。种典型的方法来介绍。v它是传真它是传真(FAX)编码的标准压缩方法。编码的标准压缩方法。 v通过改变图像的描述方式，来实现图像的压缩。通过改变图像的描述方式，来实现图像的压缩。v将一行中灰度值相同的相邻像素，用一个计数值和该灰度将一行中灰度值相同的相邻像素，用一个计数值和该灰度

52、值来代替。值来代替。77v根据对各类图像的统计，发现图像信源中象素的空间相根据对各类图像的统计，发现图像信源中象素的空间相关性比较强。在经过采用和量化形成数字彩色图像后，关性比较强。在经过采用和量化形成数字彩色图像后，其相邻象素的相关性体现在相邻象素亮度取值变化不大其相邻象素的相关性体现在相邻象素亮度取值变化不大对典型的黑白文本图像进行分析发现，前一象素为白色象素时，当前象对典型的黑白文本图像进行分析发现，前一象素为白色象素时，当前象素取值为白的条件概率素取值为白的条件概率P(W|W)平均在平均在97%以上，而由白象素变为黑象以上，而由白象素变为黑象素的概率素的概率P(B|W)仅为仅为3%，类

53、似的，当前一象素为黑，当前象素为黑的，类似的，当前一象素为黑，当前象素为黑的条件概率条件概率P(B|B)平均为平均为75%，由黑变白的概率，由黑变白的概率P(W|B)仅为仅为25%。对重复出现的字符、字符连续重复的个数以及起对重复出现的字符、字符连续重复的个数以及起始位置进行编码，就能记录该字符串始位置进行编码，就能记录该字符串重复字符重复字符游程标志游程标志游程长度游程长度基本基本RLC结构结构78v 举例说明：举例说明：a=100,b=1,c=23,d=254v aaaa bbb cc d eeeee fffffff v (共共22*8=176 bits) v 4a3b2c1d5e7f v

54、 (共共12*8=96 bits)v 压缩率为：压缩率为：96/176=54.5%79传真中的行程编码方法传真中的行程编码方法v传真件中一般都是白色比较多，而黑色相对传真件中一般都是白色比较多，而黑色相对比较少。所以可能常常会出现如下的情况：比较少。所以可能常常会出现如下的情况：v 500W 3b 470w 12b 4w 3b 3000wv v 计算上面的行程编码所需用的比特数：上面的行程编码所需用的比特数：v 因为：因为：204830004096v 所以：计数值必须用所以：计数值必须用12 bit来表示来表示 80v对于：对于： 600W 3b 570w 12b 4w 3b 3000wv因为

55、只有白或黑，而且排版中一定要留出页边距，因为只有白或黑，而且排版中一定要留出页边距，因此，一般情况下，可以只传输计数值即可。因此，一般情况下，可以只传输计数值即可。v编码为：600,3, 570, 12, 4, 3, 3000 v编码位数为:12,12, 12, 12, 12,12,12v需要的数据量为：需要的数据量为：v 12*7=84 bitv 81v现在我们就希望对其进行改善现在我们就希望对其进行改善v 既然已经可以预制知白色多黑色少，可以既然已经可以预制知白色多黑色少，可以对白色和黑色的计数值采用不同的位数。对白色和黑色的计数值采用不同的位数。v 以这个例子，可以定义：以这个例子，可以

56、定义：v 白色：白色：12 bit，黑色：，黑色：4 bit 82v编码为： 600,3,570,12,4, 3,3000 v编码位数为: 12,4,12, 4,12,4,12v所需比特数为：所需比特数为：v 4*12+3*4=60bitv 比原来的比原来的RLE方式方式84bit减少了减少了24bit。 83从从RLC基本数据占用基本数据占用3个字节，即只有当重复字符串长度大个字节，即只有当重复字符串长度大于于24(即连续有即连续有24个象素取值相同个象素取值相同)时，才有数据压缩效益。时，才有数据压缩效益。先判断游程长度，再决定是否使用先判断游程长度，再决定是否使用RLC从根本上讲，游程编

57、码依然是通过去除图像象素间从根本上讲，游程编码依然是通过去除图像象素间的相关性，来达到数据压缩的目的的相关性，来达到数据压缩的目的但是它不仅仅只利用一个相邻象素的信息，实际上，利但是它不仅仅只利用一个相邻象素的信息，实际上，利用了图像多个象素间的相关性用了图像多个象素间的相关性数字传真压缩编码标准数字传真压缩编码标准二值文本图像二值文本图像重复字符重复字符游程标志游程标志游程长度游程长度84二维行程编码二维行程编码要解决的核心问题是二维行程编码要解决的核心问题是: : 将二维排列的像素，采用某种方式将二维排列的像素，采用某种方式转化成一维排列的方式。之后按照一维转化成一维排列的方式。之后按照一

58、维行程编码方式进行编码。行程编码方式进行编码。85如下图所示，是两种典型的二维行程编码的排列如下图所示，是两种典型的二维行程编码的排列方式：方式：(a) (b) 86例：例：130130130129134133129130130130130129134133130130130130130129132132130130129130130129130130129129127128127129131 129131 130127128127128127128132132125126129129127129133132127125128128126130131131f数据量：数据量：6464* *8=5

59、12(bit)8=512(bit)87如果按照行扫描的顺序排列的话，数据分布为：如果按照行扫描的顺序排列的话，数据分布为：130，130，130，129，134，133，129，130； 130，130，130，129，134，133，130，130； 130，130，130，129，132，132，130，130；129，130，130，129，130，130，129，129； 127，128，127，129，131，129，131，130；127，128，127，128，127，128，132，132； 125，126，129，129，127，129，133，132；127，125，128

60、，128，126，130，131，131行程编码为行程编码为: :（3，130），（），（1，129），（），（1，134），（），（1，133），（），（1，129），（），（4，130），），（1，129），（），（1，134），（），（1，133），（），（5，130），（），（1，129），（），（2，132），），（2，130），（），（1，129），（），（2，130），（），（1，129），（），（2，130），（），（2，129），），（1，127），（），（1，128），（），（1，127），（），（1，129），（），（1，131），（），（1，129），），（1，131）