利用二进小波基对函数f(t).ppt

1、6.1 概述6.2 图像编码的基本理论6.3 无损压缩编码6.4 限失真编码6.5 二值图像编码6.6 小波变换及在图像压缩编码中的应用6.7 图像压缩国际标准简介,第6章 图像压缩编码, 图像压缩的必要性 图像作为信息的重要表现形式，其具有数据量 大、带宽宽等特点。 一方面： 需要增加信道，但这很有限，因为信道的 增加永远赶不上信息的爆炸式增长，况且 还要受到环境的限制。 另一方面： 必须减少表示图像的数据量，以达到压缩 图像数据的目的。,6.1 概 述,图像压缩的可能性 空间上的冗余：相邻像素或者序列相邻帧间有较大的相关性； 人的视觉特性：人眼的分辨率非常有限； 去除数字图像中的冗余，来减

2、少数据量。图像压缩编码的概念 图像数据的压缩和编码表示。 图像压缩编码系统： (1)图像编码: 对图像信息进行压缩和编码，在存储、处理 和传输前进行，也称图像压缩； (2)图像解码：对压缩图像进行解压以重建原图像或其近似 图像。,6.1 概 述,图像压缩方法分类 按压缩前及解压后的信息保持程度和方法的原理来分类：1按照压缩前及解压后的信息保持程度分成三类： （1） 信息保持（存）型 压缩、解压中无信息损失，主要用于图像存档，其特点是信息无失真，但压缩比有限，也称无失真/无损/可逆型编码。 （2） 信息损失型 牺牲部分信息，来获取高压缩比，数字电视、图像传输和多媒体等应用场合常用这类压缩，其特点

3、是通过忽略人的视觉不敏感的次要信息来提高压缩比，也称有损压缩。 （3） 特征抽取型 仅对于实际需要的（提取）特征信息进行编码，而丢掉其它非特征信息，属于信息损失型。 这里的第三类是针对特殊的应用场合 ，因此，一般就将图像压缩编码分成无损和有损两大类。,6.1 概 述,6.1 概 述,2按照图像压缩的方法原理可分成四类： （1）像素编码 编码时只对每个像素单独处理。如脉冲编码调制、熵编码、行程编码等。 （2）预测编码 通过去除相邻像素之间的相关性和冗余性，只对新的信息进行编码。常用的有差分脉冲编码调制。 （3）变换编码 对给定图像采用某种变换，使得大量的信息能用较少的数据来表示。通常采用的变换包

4、括：离散傅立叶变换(DFT），离散余弦变换(DCT)和离散小波变换(DWT)。 （4）其它方法 早期的编码，如混合编码、矢量量化、LZW算法。 近些年来也出现了很多新的压缩编码方法，如使用人工神经元网络的压缩编码算法、分形、小波、基于对象的压缩编码算法、基于模型的压缩编码算法等。, 数据冗余 概念 代表无用信息或重复表示了其它数据已经表示过的信息的数据称为数据冗余。常用压缩比和冗余度表示。 设 和 代表用来表示相同信息的两个数据的容量,那么压缩比可以定义为 是压缩前的数据量， 是压缩后的数据量。 用 表示的相对冗余度（即 相对于 ）可以定义为：,6.2 图像编码的基本理论,其中， 的取值范围为

5、(0, )， 的取值范围为(-,1)。当 时, , , 相对于 不包含冗余。 当 时, 表示几乎100的压缩和几乎全部的冗余。 当 时， 表示没有压缩，反而是几乎100的放大。数据冗余主要有三种： 编码冗余、像素间冗余和心理视觉冗余，减少或消除了其中的一种或多种时，就实现了图像的压缩。,6.2 图像编码的基本理论,6.2 图像编码的基本理论,编码冗余 对于给定图像其数据量就已确定，即 完全确定。因此，图像压缩后的数据量 就决定了压缩比。 其中 表示图像像素个数， 是平均码字长。由此引入如下几个概念： (1) 码字：信息编码中每个符号的二进制编码值。 (2) 码字长：码字的长度，即其二进制编码值

6、的位数，也就是比特数。(3) 平均码字长:每个像素所需的平均比特数。 若设图像的灰度级为k，则k出现的概率为: 这里 L 是灰度级数， 是第 k 个灰度级在图像中出现的次数，n 是图像的总像素个数。,若每个灰度级k的编码长度为l(k)，则平均码字长为：（4）自然编码：每个灰度级（或每个像素）均用m位的二进制码表示，也称等长编码，此时（5）变长（不等长）编码：对于图像中的不同灰度级采用不同长度的码字表示。此时 （6）编码冗余：不同的编码方法可能会有不同的 ，由此引出两种编码冗余。 相对编码冗余： 大的编码相对于 小的编码就存在相对编码冗余。 绝对编码冗余：使 的编码就存在绝对编码冗余。,6.2

7、图像编码的基本理论,像素间的冗余 由于像素间存在相关性，那么对于任一给定的像素值，原理上都可以通过它的相邻像素值预测得到。这就带来了像素间的冗余。 心理视觉冗余 人观察图像是基于目标物特征而不是像素，这就使得某些信息显得不重要，可以忽略，则表示这些可忽略信息的数据就称为心理视觉冗余。电视广播中的隔行扫描就是常见的例子。,6.2 图像编码的基本理论,例6.1 变长编码与自然编码的对比。,6.2 图像编码的基本理论,其中自然编码的平均码字长为3，采用表中所示变长编码的平均码字长就减少为：,这个例子说明变长编码是用尽量少的比特数来表达尽可能多的灰度级以实现数据的压缩。,图像编解码模型信息传输系统模型

8、 图6.2.1 信息传输系统模型 上图给出了一个信息传输系统的模型，它主要由三部分组成（图中的三个虚线框），即编码器、解码器和信号传输。,6.2 图像编码的基本理论,6.2 图像编码的基本理论,图像编解码模型 图6.2.2 图像编解码模型 （a） 信源编码器；（b） 信源解码器 变换器对输入数据进行转换，以改变数据的描述形式，减少或 消除像素间的冗余（可逆） 。 量化器根据给定的保真度准则降低变换器输出的精度，以进一步减少心理视觉冗余（不可逆） 。,6.2 图像编码的基本理论,保真度准则 对图像的失真程度或质量进行评价，以便将图像失真限制在给定的范围内。客观保真度准则 将信息损失的多少，表示为

9、原始图像与压缩后又解压缩得到的重建图像的函数，就称为客观保真度准则。通常以均方根误差、均方根信噪比和峰值信噪比三种形式来表示。（1）均方根（RMS）误差 若原图像为f(m,n)，压缩又解压后的图像为g(m,n)，则误差图像为：,6.2 图像编码的基本理论,均方根（RMS）误差为： （2）均方根信噪比 令 ，即把重建图像g(m,n)和输入图像f(m,n)之间的误差看作是噪声，将重建图 像信噪比SNR作为保真度准则，即,6.2 图像编码的基本理论,实际中使用时常将SNR归一化并用分贝（dB）表示，即 ， 其中， 为图像平均值。,（3）峰值信噪比 如果令 那么峰值信噪比为：对于常见的256级灰度图像

10、， 255。,主观保真度准则 对于最终作为人的视觉感受使用的视觉图像，一般也采用主观保真度准则进行主观评价，包括综合评价法和成对比较打分法。（1）综合评价法 不同的观察者对给出的图像进行评价，然后将评价结果加以平均，作为综合评价的结果。 表6.2.2 电视图像质量评价表,6.2 图像编码的基本理论,（2）成对比较打分法 可以按照某种相对的尺度对f(m,n)和g(m,n)进行比较打分，从而获得相对的质量分。 比如，可以用-3，-2，-1，0，1，2，3来表示主观评价很差，较差，稍差，相同、稍好、较好、很好。,6.2 图像编码的基本理论,无损压缩在压缩后不丢失信息，即对图像的压缩编码解码后可以不失

11、真地恢复原图像。我们把这种压缩编码称为无损压缩编码，简称无损编码，或称无失真编码、信息保持编码或熵保持编码。信息量 一个信息若能传达给我们许多原来未知的内容，我们就认为这个信息很有意义，信息量大；反之，一个信息传达给我们的是已经确知的东西，则这个传达就失去了意义，信息量就为零。所以，信息论中关于信息量是按该信息所传达的事件的随机性来度量的。,6.3 无损压缩编码,6.3 无损压缩编码,如果某随机事件x出现的概率为 P(x)，则此事件包含的信息量为 若a=2，则信息量单位为比特（binary unit，bit），即若a=e, 则为奈特（nature unit，nat）；若a=10，则为哈特（ha

12、rt，以纪念hartley）。 一般以2为底取对数，由此定义的信息量等于描述该信息所用的最少二进制位数。,信源的熵图6.3.1 一个简单的信息系统模型 信息的来源称为信源，信源发出信息后通过信道传送到接收方，称为信宿。 若信源由J个符号组成信源集： 对应各符号出现的概率为 ，且 与 不相关，则该信源的平均随机程度或平均信息量就称为信源的熵，表示为,6.3 无损压缩编码,相当于灰度级i， 相当于灰度级出现的频数（概率），即直方图。信源的熵则表示图像各灰度级的平均比特数或图像信源的平均信息量。基本编码定理 1. 无失真编码定理 在无干扰条件下，存在一种无失真的编码方法，使编码的 与信源的熵H(A)

13、任意的接近。即但以H(A)为下限，即 。这就是Shannon的无失真编码定理。同时，该定理也为我们提供了一个评价无失真编码的标准。因此，我们可给出描述无失真编码性能的几个参数：,6.3 无损压缩编码,6.3 无损压缩编码,（1） 编码效率（2） 冗余度（3） 压缩比其中，m为采用自然编码时的码长。此时，式中分母 有下限，则对应最大压缩比为：,2变字长编码定理 在变字长编码中，对出现概率 大的信符 赋予短码字，而对 小的 赋予长码字。如果码字长度严格按照所对应信符的出现概率大小逆序排列，则编码的平均码长不会大于任何其它排列方式。 即若 则 下面将介绍利用变字长编码定理进行无失真编码的两种常用方法

14、霍夫曼编码法和算术编码法。,6.3 无损压缩编码,6.3 无损压缩编码,霍夫曼编码法 霍夫曼编码法是消除编码冗余最常用的方法，它实际上是变长编码定理的一种实现算法。其编码过程分为2步：1.缩减信符数量（1）将输入符号（图像中的灰度级） 按出现概率 由大到小排列，即（2）将最小的两个 相加，形成一个新的概率集合（此时就缩减了一个 ），再按（1）重复直到只剩下两个概率为止。,6.3 无损压缩编码,图6.3.2给出了一个实际信源符号的缩减过程。图6.3.2 霍夫曼编码中的信符缩减过程,2. 分配码字 图6.3.3给出了上述经缩减信符后的码字分配过程。6.3.3 霍夫曼编码中的码字分配过程,6.3 无

15、损压缩编码,到此，就得到了原始信源对应的码字，如表6.3.1所示。按照码字表将原图像中的各个像素灰度值用对应的码字表示，就可得到图像的霍夫曼编码结果。解码过程与编码过程相反，即将图像编码值变成原灰度图像。表6.3.1 霍夫曼编码的码字表,6.3 无损压缩编码,6.3 无损压缩编码,同时也可以计算与编码性能相关的几个参数：（1） 信源的熵（2） 霍夫曼编码的平均码字长（3） 霍夫曼编码的效率,6.3 无损压缩编码,（4） 冗余度（5） 压缩比 霍夫曼编码是无失真编码中效率较高的一种编码方法。在分配码字过程中，随机赋“0”和“1”的不同，结果会使码字不同（不唯一），而码字长和平均码字长不会改变，它

16、也是唯一可解码的。但其缺点是信源缩减过程复杂，运算量大。为克服这个缺点，人们也相继提出了一些改进方法。, 香农费诺编码法 Shannon和Fano提出了另一种变长编码方法。相比于霍夫曼编码方法，该方法更方便、快捷，有时也能达到最优性能。具体编码方法是：（1） 将信符 按出现概率 由大到小排列（2） 将X分成两个子集,6.3 无损压缩编码,并且保证成立或差不多成立。（3）给两个子集赋不同的码元值，如 中的符号赋“0”， 中的 符号就赋“1”，也可以反过来。（4）重复（2）（3），即对每个子集再一分为二，并分别赋予 不同码元值，直到每个子集仅含一个信符为止。下面通过霍夫曼编码中用过的同样例子，说明

17、上述编码过程。将信源,6.3 无损压缩编码,则其编码过程如图6.3.4所示。,6.3 无损压缩编码,记为,图6.3.4 香农费诺码编码过程,6.3 无损压缩编码,算术编码 算术编码是采用一种比特数目可变的方法来进行编码的，它和霍夫曼编码类似，都属于变长编码。但算术编码可以分配带有小数的比特数目信符。例如，当概率为0.3的符号，它的理想码字应该为 ，那么霍夫曼编码只能给该信符分配1或2比特，算术编码则克服了这一问题。算术编码更接近于最优熵编码，压缩性能优于霍夫曼编码。 算术编码的基本原理是将被编码的信息流（称为消息）表示成实数0和1之间的一个区间。消息越长，编码表示它的区间就越小，表示这一小区间

18、所需的二进制位数就越多。 算术编码用到两个基本参数：符号的概率和它的编码区间。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号在0到1之间的区间，编码过程中的区间决定了符号压缩后的输出。,6.3 无损压缩编码,算术编码步骤如下： （1）“当前区间”初始化为0,1)。（2）对于输入信息流中的每个信符，编码器执行如下两个步 骤： 将“当前区间”分成子区间，该子区间的长度正比于符 号的概率； 选择下一个信符对应的子区间，并使它成为新的“当 前区间”、（3）将整个消息处理后，在“当前区间”中任取一个数，该数 就是输入信息流的算术编码。,下面结合一个实例来说明算术编码的具体步骤。,6.3 无损

19、压缩编码,设要编码的信息流（即信源）为“bcadc”，信源中各符号出现的概率分别为 ， ， ，,首先，将各符号在区间0,1)内的初始区间l,h)设定为表6.3.2所示。,表6.3.2 信源符号出现概率和初始编码区间分配表,定义“当前区间”为 ，当前编码符号的初始区间为l,h)。则“当前区间”的起始值 和结束值 为,6.3 无损压缩编码,第一个编码符号为“b”，其初始区间为 ，则“当前区间” 为,其中“当前区间”的初始化值为 ，则,代入后可得,第二个编码符号为“c”，则其,，,，同理“当前区间”为,6.3 无损压缩编码,即“bc”的编码区间为,第三个被编码的符号为“a”，其初始区间为,同理可得“

20、当前区间”为,即“bca”的编码区间为,。,第四个被编码的符号为“d”，其初始区间为,则“当前区间”为,6.3 无损压缩编码,第五个被编码符号为“c”，同理可得,至此，输入信息流 “bcadc” 被描述为一个实数区间 ，或者说在此区间内的任一实数值都唯一对应该信息流。,将该区间 用二进制形式可表示为,取这个区间位数最少的一个数0.010111111作为信息流“bcadc”的编码输出，同时“0.”也可忽略。因此，信息流“bcadc”的编码值为010111111。,6.3 无损压缩编码,图6.3.5描述了以上算术编码过程。,图6.3.5 算术编码过程示意图,算术解码是编码的逆过程，根据编码时的符号

21、出现概率的初始编码区间分配表和压缩后数据编码所在的范围，确定所对应信息流的每一个符号。 算术编码的实现方法要比霍夫曼编码复杂一些，但其编码效率一般高于霍夫曼编码。,6.4 限失真编码,在实际生活和应用中，人们并不要求获得完全无失真的信息，通常只要求近似地再现原信息，也就是允许一定的失真存在。这种把失真限制在某一允许限度以内，可以达到更高压缩比的压缩编码称为限失真编码。信息率失真理论 信息率与允许失真之间的关系，就是香农提出的信息率失真理论的内 容。 根据信息率失真理论，有一个函数R(D)存在，只要信息率大于R(D)，必存在一种编码方法，其平均失真可无限逼近D；反之，若信息率小于R(D)，则任何

22、编码的平均失真必须大于D。这就是香农的限失真编码定理。 这里的R(D)称为率失真函数，如图6.4.1所示，它是D 的单调递减函数。,图6.4.1 一个率失真函数的示意图,若以均方误差作为失真度量，对于正态分布的信源，其率失真函数为,6.4 限失真编码,下面介绍两种常用的限失真编码方法：预测编码和正交变换编码。,图像像素之间存在高度的相关性。通过对图像进行某种变换，数值较大的方差会集中在少数系数中，这样可以给那些小幅值系数分配很少的比特数，从而达到压缩的目的。,预测编码,6.4 限失真编码,1预测编码的概念,图6.4.2给出了摄像师（camera）图像及其相邻像素差值图像的直方图，从中可看出，行

23、列相邻像素取差运算后的差值主要集中在0附近，相比于原图像直方图，差值直方图的分布也很集中。这说明，通过对原图像行列取差值，可以减少或消除原图像像素间的相关性，使差值的方差大大降低。,图像中某一像素f(m,n)的灰度值可以用其邻近的若干个像素来预测（估计），则f(m,n)与其预测值 之差（称为预测误差）为:,图6.4.2 原图像及其像素差值直方图对比,（c）原图像行列取差值的三维图,（d）行列取差值图像的直方图,6.4 限失真编码,（a） 原图像,（b）原图像直方图,（d）行列取差值图像的直方图,如果像素间相关性较强，灰度值预测较准确，则e(m,n)的分布比上例中的差值要更集中于0附近，从而使预

24、测误差方差很小，即 。这里的 为原图像方差。,原图像信源和差值信源（假设都是正态分布）的率失真函数分布为： ，,则直接对f(m,n)进行量化编码而改为对差值e(m,n)进行量化编码，可以使信息率（平均码字长）平均减少,这种利用原图像与其预测图像的差值代替原图像进行编码的方法就称为预测编码。预测编码中最有代表性的方法就是差分脉冲编码调制(DPCM：Differential Pulse Code Modulation)方法。,6.4 限失真编码,6.4 限失真编码,由与之相关的前m个像素来预测,图6.4.3 DPCM 编解码原理框图,2DPCM编码的基本原理 DPCM编码的基本原理如图6.4.3所

25、示。其中的编码部分由量化器、预测器和编码器组成，解码部分由解码器和预测器组成。,3最优预测器的设计,预测编码一般属于有失真编码，预测编码的失真程度取决于量化器和预测器的设计方法以及它们之间的相互作用，预测器一般设计成与被预测像素最近的m个像素的线性组合，即,并有限制条件：,最优预测器的条件为编码的均方预测误差降至最小：,这里设计最优预测器就是求 ，使,6.4 限失真编码,为求最小,为求极值，令 ，得到如下方程组：,通过求解如上方程组，就可求得最优预测系数,或者写成：,6.4 限失真编码,写成矩阵形式，即为：,在假定 具有零均值和方差 的条件下，求出联立方程的解集，得到：,其中， 是下列mm自相

26、关矩阵的逆矩阵：,6.4 限失真编码,和 分别为图像水平和垂直方向的相关系数，且有,此时在最优预测条件下，预测误差的方差为：,实际应用中自相关函数为：,对于二维平面图像，预测采用从左至右，从上到下的因果形式进行。上述描述及公式中 和 与图像像素关系如图6.4.4所示。,图6.4.4 因果形式图像预测的示意图,6.4 限失真编码,这里预测 所用像素个数称为预测器的阶。若某一平稳图像，则其三阶线性预测器为：,也可写为,可求得最优预测系数为： , , 由此可得到线性预测器为：其预测方差为：,6.4 限失真编码,6.4 限失真编码,图a至d分别是用4个预测器对Lena图进行编码后的解码图，量化器均用德

27、尔塔2级量化器。由图中可以看出，视觉感受的误差随预测器阶数的增加而减少。图c三阶的质量好于图b二阶，图b的质量又好于图a一阶。图d是一阶自适应预测的结果，比a质量好但比b差。图e到h是对应的误差图，误差大的预测图质量就差。, 正交变换编码,1正交变换编码的基本原理,图6.4.5 正交变换编码原理框图（a）编码部分；（b）译码部分。,6.4 限失真编码,2方法步骤,（1） 子图像划分,在图像正交变换编码中，通常先将NN的原始图像f(m,n)分割成dd的图像子块（可称为子图像），再对每个子图像进行正交变换。这样做的好处是：一方面可增加子图像块内的均匀性，使正交变换后能量更集中；另一方面也会大大减少

28、变换所需运算量。图像分块大小的选择应该使得相邻子图像之间的相关性保持到某个可接受的程度，并且将分块的长和宽设定为2 的整次幂。,6.4 限失真编码,（2） 正交变换,采用正交变换对图像进行处理，可将空域高度相关的像素灰度值变为弱相关或不相关的系数。经正交变换后，并没有丢失图像所包含的信息，总的能量保持不变，但是能量重新分配。 正交变换编码能够获得高压缩比的原因在于图像通过正交变换后实现了能量的集中，使得大多数系数为零或是很小的数值。 若采用均方差最小准则，K-L变换是具有最佳能量集中能力的变换，但K-L变换的变换矩阵依赖于具体图像，而不能得到固定的变换矩阵，特征值和特征向量的计算具有很高复杂度

29、，K-L变换没有快速算法。常用的正交变换包括离散DCT变换、Walsh-Hadamard变换，它们的去相关和能量集中特性都低于K-L变换，但是都存在快速算法，并且具有固定的变换矩阵，因而比K-L应用更加广泛。,6.4 限失真编码,这一步的计算公式为：,（3） 量化和编码：,正交变换后对其系数的量化和编码一般结合起来分成两步进行，第一步是系数选择，第二步是选择系数的量化和编码。, 系数选择,系数选择的过程相当于滤波，即选择上的系数保留，未选择上的令其为零，即,6.4 限失真编码,系数选择通常有两种方法：区域法和阈值法。,区域法,区域法是选取特定区域中的变换系数进行量化编码，区域外的系数被舍弃。这

30、是因为根据信息论中的不确定原理，具有最大方差的变换系数包含有最多的图像信息，故这些系数应该保留下来。选择滤波器为,这样，就保留了大部分的图像能量，但是由于舍去了高频分量，使得恢复图像出现轮廓以及细节的模糊。,6.4 限失真编码,区域选择越大，图像失真就越小，但压缩比会降低。反之，区域越小，则失真越大，但压缩比会提高。区域大小的选定应根据子图像变换后频域能量的集中程度，能量越集中，区域应越小，反之能量越分散，区域应越大。区域种类一般可选大、中偏大、中偏小和小4种，编码时用2比特表示4种区域。这样每个子图像编码时要增加2比特，而整个图像编码值要增加 比特。图6.4.6（a）给出了一种区域选择滤波器

31、。,阈值法,阈值法就是采用最大幅值原则，根据实际情况设定适当幅度的阈值，若变换系数超过该阈值，则保留系数进行编码，否则补零。选择滤波器为,6.4 限失真编码,在选取过程中，不仅大部分的低频成分被保留下来，某些超过阈值的高频成分也被保留下来，这样在一定程度上保留了恢复图像轮廓以及细节。其缺点是需要对选择系数的位置进行编码，编码占用比特数较多，这样就会大大降低有效压缩比。图6.4.6（c）给出了一种阈值选择滤波器。, 选择系数的量化和编码,将带小数的系数变成整数，并使大数值变换成小数值。量化处理导致了有损压缩。量化后的数值就可分配码字，分配的原则是：方差大的系数分配长码字，方差小的系数分配短码字。

32、 为了将所有的变换系数按照幅值从大到小的顺序排列，通常采用图6.4.6（d）所示从低频到高频（从0126263)的Z字形扫描，并且一般只保留 个系数，然后对保留的系数进行量化。,6.4 限失真编码,(a),(b),(c),(d),图6.4.6 量化和编码的示意图 (a) 区域选择滤波器； （b）区域量化和码字分配； (c）阈值选择滤波器； （d）Z形扫描编码顺序。,6.4 限失真编码,在区域选择量化编码中，一般采用均匀量化方法。均匀量化方法有两种。第一种方法是：首先假设数据是由8位无符号数组成，那么这些数据在范围0,255间。选择一个间隔参数 ,并且计算均匀量化的值0， , , , ,255。

33、k满足： 而 这样每一个数据就可以转换成该序列中与其最接近的一个数，从而实现量化。,6.4 限失真编码,另一种方法是选择系数门限T，输入数据可以做如下变换,这样最终的量化值为,二值图像是指只有黑白两个亮度值的图像。,6.5 二值图像编码,常数块编码与空白块编码,常数块编码就是采用专门的码字来表达全0或者全1的连通区域，该编码方法常用于二值图像压缩和位平面压缩。编码过程中，图像首先被分成ab的图像子块。然后将其分为全白块、全黑块和混合块，将出现频率最高的块分配一个比特码字“0”，其余两类子块分配两个比特码字“10”和“11”。当图像白块区域较多时，通常采用空白块编码，该编码方法将全白的图像子块分

34、配一个比特码字“0”，而将全黑和混合图像子块用（ab1）个比特码来表示。并且将“1”作为编码的前缀，编码的其余部分利用“0”（或“1”）来表示子块各个像素为“黑”（或“白”）。该编码方法主要针对白色区域多的二值图像编码，也可以实现压缩。,游程编码分为定长游程编码和变长游程编码两类。其中定长游程编码是指编码的游程所使用的位数是固定的，一旦灰度相同且连续的个数超过了固定位数所能表示的最大值，则转入下一轮游程编码。变长游程编码则是指不同范围的游程使用不同位数来进行编码。,6.5 二值图像编码, 游程编码（RLC）,游程编码适合于二值图像编码，原因是由于二值图像的每一行（列）都是由若干个黑白像素段交替

35、出现的，对应着“0”和“1”两种符号，“0”符号对应“黑”游程，“1”符号对应“白”游程。这些符号连续出现，形成了“0”游程和“1”游程。“0”游程和“1”游程是交替出现的。若规定是“0”游程开始，那么接着就是“1”游程，然后是“0”游程，以此类推。这样，就可以将二元序列转换为游程长度的序列，该变换是可逆的。,例如，对于一个二元序列 0000001111100011001 对应的游程序列为 653221，由于设定为从“0”开始，故可以容易的恢复出原始的二元序列。然后根据不同长度段发生的概率来分配不同长度的码字，通常采用Huffman编码。RLC中每个像素的平均码长满足下式,6.5 二值图像编码

36、,（bit/像素）,其中 为RLC像素的平均码长； 为每个像素的熵值； ，,为白、黑像素出现的概率； ， 分别为白、黑像素所需的码长。,扫描方式见图6.5.1所示,6.5 二值图像编码,图6.5.1 一维游程编码用于图像数据的扫描模式,6.5 二值图像编码,四叉树方法是逐个区域扫描位图，查找像素取值相同的区域。从建立孤立节点开始，它是四叉树的根。首先把位图分为4个象限，每个成为根的子节点。如果对应区域为相同像素值，则它成为根的叶子节点，否则成为根的一个子节点。把任何不具有相同像素值的区域递归地划分为4个更小的子象限，它是四叉树的4个兄弟节点。在图6.5.2中，右边的0,1表示输出的比特值，共计

37、输出28bits，实际的输出顺序为: 1010000001110011110001000100。,四叉树编码,图6.5.2 一颗四叉树,二值图像区域 ，大小记为 ，区域内像素值求和得到 。编码算法的步骤为：（1） 分割一幅位图为4个象限 ，(从左到右，从上到下)；（2） 对于 且 ，依次输出其四个叶子的像素比特值； 否则：如果 ，输出比特1； 继续四叉树分割 ，回到（1）(递归编码过程)； 否则，输出比特0； 如果 ，输出比特0； 否则，输出比特1；,6.5 二值图像编码,小波变换压缩编码的基本思想是利用小波变换将原图像转换为小波域上的系数，由于小波变换的能量集中作用，会使原图像的绝大部分能量

38、集中在少量小波系数上，通过量化处理，忽略一些能量很小的系数，只保留那些能量较大的系数进行编码，就可达到图像压缩的目的。小波变换编码具备如下的特点：（1）小波变换能将一信号分解成同时包含时域和频域局部特 性的变换系数，但传统变换（如DFT和DCT等）会失去信号 在时域的局部特性。（2）小波变换能兼顾不同应用中对时、频不同分辨率的要 求，具有“数学显微镜”的美称，但传统变换（DFT和DCT 等）虽然在频域具有最高分辨率，但在时域无分辨率而言。,6.6 小波变换及在图像压缩编码中的应用,（3）小波变换和传统正交变换都有能量守恒和能量集中的作用，但小波变换能有效消除传统变换的分块效应的存在以及分块效应

39、对图像编码的影响。（4）小波变换能根据图像特点自适应地选择小波基，从而既能保证解压后图像的质量，又能提高压缩比。而DCT则不具备自适应性。（5）通过小波变换可以充分利用变换系数之间的空间相关性对系数建模，进一步提高压缩比。 鉴于小波变换编码的上述优点，小波变换已成为图像压缩领域的研究和应用热点，并取代DCT而成为JPEG2000、MPEG4和MPEG7等新的图像编码标准中的变换方法。,6.6 小波变换及在图像压缩编码中的应用,对于一个确定性信号 ，在整个区间是连续或分段连续，只要满足平方可积条件，即,6.6 小波变换及在图像压缩编码中的应用,从傅立叶分析到小波变换,经典傅立叶变换,就称f(x)

40、在空间 上可测，且 可以表示为一标准函数族 的加权和；,或,就称为原函数f(x)的傅立叶正变换，记作傅立叶反变换，记作同样，对于随机信号，其自相关函数 与功率谱 也构成一傅立叶变换对：,6.6 小波变换及在图像压缩编码中的应用,其中权函数,傅立叶变换不能表述信号的时变特性，为此，Gabor于1946年提出了加窗傅立叶变换的概念。用一个有限区间（称为窗口）外恒等于零的光滑函数去乘原函数f(x)，然后对乘积进行傅立叶变换，就称为加窗傅立叶变换，也称短时傅立叶变换。即其中g(x)称为窗函数。上式对应的反变换为,6.6 小波变换及在图像压缩编码中的应用,加窗傅立叶变换,加窗傅立叶变换是一种局部化的时频

41、分析方法，只要适当选择窗函数，就可以通过信号的加窗傅立叶变换获得它在局部时间区间内的时变特性。 但加窗傅立叶变换仍存在一定的不足： 其一，因为窗函数一旦选定，其大小和形状就是固定不变 的，这样就不能自适应地反映信号的突变，而信号 的突变在很大程度上就反映了目标的特征信息。 其二，在信号分析时，对于高频特性，时窗宽度应相对窄 些，而对于低频特性，时窗宽度相对宽些。即应给 出一可调时频窗，而加窗傅立叶变换是固定窗，不 能很好地刻画出信号的时域特性。因此，这种自适 应改变窗口大小的思想，加窗傅立叶变换是无法实 现的，而利用小波变换可迎刃而解。,6.6 小波变换及在图像压缩编码中的应用,小波变换发展了

42、加窗傅立叶变换的局部化思想，其窗宽是自适应可变的，在高频时使用窄窗口，在低频时则使用宽窗口。1 连续小波变换基函数所谓小波（wavelet）就是存在于一个较小（有限）区域的波，图6.6.1(a)所示就是一例。设 ，其傅立叶变换为 ，满足条件：则称 为一个基本小波或小波母函数（简称母波），并称上式为小波函数的可允许条件。,连续小波变换,6.6 小波变换及在图像压缩编码中的应用,将母波 进行平移和伸缩，有则称 为小波基函数，简称小波或子波。其中a称为伸缩因子（也称尺度因子），它决定一个特定基函数的伸缩性质，b称为平移因子。 由于a 和b 均取连续变化的值，因此上式又称连续小波基函数，它们是由同一母函数（母波） 经平移和伸缩后得到的一组函数簇，也称为子波基函数。,6.6 小波变换及在图像压缩编码中的应用,6.6 小波变换及在图像压缩编码中的应用,(b),(c),图6.6.1 母波及其平移、伸缩后得到的小波基示例（a）一个母波，（b）平移得到的小波基，（c）再伸缩得到的小波基。,(a),2 小波函数的时频特性定义母波 的时域窗口中心为 ，窗口宽度为 ，则可求得连续小波 的时窗中心及窗口宽度分别为 同样， 的傅立叶变换 的频域窗口中心为 ，窗口宽度为 ，则 的傅立叶变换 为,