数字图像处理ppt第5章图像压缩

1、Digital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods Chapter 8图像压缩Digital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods Chapter 8图像压缩图像压缩 图像压缩探讨减少表示数字图像所需之数据量的问题图像压缩探讨减少表示数字图像所需之数据量的问题。减。减数据量的基本原则是移去冗余的数据。以数学的观点，这数据量的基本原则是移去冗余的数据。以数学的观点，这等于是一个等于是一个2 2维像素数组转换成统计上不相关的数据集维像

2、素数组转换成统计上不相关的数据集。图。图像的储存或传输前都要先转换。之后，压缩图像就被解压像的储存或传输前都要先转换。之后，压缩图像就被解压缩以重建原始图像或它的近似。缩以重建原始图像或它的近似。 在本章中我们将讨论图像压缩处理的理论与实现。在本章中我们将讨论图像压缩处理的理论与实现。 8.1 8.1到到8.38.3节构成基础的介绍，而此基础整合起来就形成此节构成基础的介绍，而此基础整合起来就形成此领域的理论。领域的理论。 8.4 8.4到到8.68.6节讨论图像压缩的实际面。节讨论图像压缩的实际面。Digital Image Processing, 2nd 2002 R. C. Gonzal

3、ez & R. E. Woods 8.18.1背景基础背景基础数据压缩数据压缩 (data compression)(data compression)这术语是指降低表示一个所给这术语是指降低表示一个所给信息量所需之数据量的一种处理。我们必须弄清楚数据信息量所需之数据量的一种处理。我们必须弄清楚数据(data)(data)与与信息信息 (information)(information)的区别。其实的区别。其实数据数据是传递信息的是传递信息的载体载体，同样的信息量可能可以用各种不同的数据量来代表。，同样的信息量可能可以用各种不同的数据量来代表。例如，一个喜欢喋喋不休的人与另一个总是简短

4、扼要讲话的例如，一个喜欢喋喋不休的人与另一个总是简短扼要讲话的人来讲同样的故事。人来讲同样的故事。这些数据（或言语）不是提供一些无关紧要的信息就是重述这些数据（或言语）不是提供一些无关紧要的信息就是重述一些早已知道的东西。因此说它含有一些早已知道的东西。因此说它含有数据数据冗余性冗余性 ( data( data redundancy ) redundancy )Digital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 8.18.1背景基础背景基础信息信息 与与 图像图像的关系的关系 ！Digital Image Pr

5、ocessing, 2nd 2002 R. C. Gonzalez & R. E. Woods 数据冗余性数据冗余性是数学上是数学上可定量描述可定量描述的实体。如的实体。如果用果用 与与 代代表用来表示表用来表示同一个信息同一个信息之两组数据的信息载体单位个数，则之两组数据的信息载体单位个数，则第一组数据集合第一组数据集合（用字母用字母 表示者表示者）的的相对数据冗余性相对数据冗余性 ( relative data redundancy ) 可定义成可定义成 (8.1-1)其中其中 通常称为通常称为压缩率压缩率 ( compression ratio ) (8.1-2)RDCR11RC

6、1n2n1nDR21nnCRDigital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods Digital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 在数字图像压缩中，有三种基本的数据冗余性可以被确认与在数字图像压缩中，有三种基本的数据冗余性可以被确认与利用：利用：编码编码（codingcoding）冗余性、）冗余性、像素间像素间（interpixelinterpixel）冗余性）冗余性及及心理视觉心理视觉（psychovisualpsychov

7、isual）冗余性。）冗余性。当减少或消除这些冗余性的一种或多种时，就可达成数据压当减少或消除这些冗余性的一种或多种时，就可达成数据压缩的效果。缩的效果。Digital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 8.1.18.1.1编码冗余性编码冗余性与第三章一样，让我们再次假设在区间与第三章一样，让我们再次假设在区间0 , 1 中的离散随机中的离散随机变数变数 代表一图像的灰阶，且每个代表一图像的灰阶，且每个 出现的机率为出现的机率为 (8.1-3)式中式中 L 为灰阶数为灰阶数， 为第为第 k 个灰阶在图像中出现

8、的次数个灰阶在图像中出现的次数，而而 n 为图像中像素的总数。如果用来表示每个为图像中像素的总数。如果用来表示每个 值值的位的位数是数是 ，则表示则表示每一个像素每一个像素所需的平均位数为所需的平均位数为(8.1-4)krkr)(krrp1,2, 1 ,0)(Lknnrpkkrknkr)(krl)()(10krLkkavgrprlLDigital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 也就是说，指定给各种不同灰阶之码字的平均码长是代表每也就是说，指定给各种不同灰阶之码字的平均码长是代表每一个灰阶的位数与该灰阶出现

9、之机率乘积的和。因此，对一个灰阶的位数与该灰阶出现之机率乘积的和。因此，对一个一个 图像编码所需要的总位数为图像编码所需要的总位数为 。用用 m 位位的自然二进码来代表图像的灰阶的自然二进码来代表图像的灰阶( (常数），代入常数），代入 (8.1-4)可得式右边简化为可得式右边简化为 m 位位。NMavgMNLDigital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods kr范例范例8.1可变长度编码可变长度编码的一个简单例的一个简单例证证一幅八阶图像有表一幅八阶图像有表8.18.1中所示的灰阶分布。如果用中所示的灰阶分

10、布。如果用三位的自然二进码（三位的自然二进码（code 1code 1）来表示八种可能的）来表示八种可能的灰阶，则因为对所有的灰阶，则因为对所有的 都有都有 ，所以所以是是3 3位。不过如果用表位。不过如果用表8.18.1中的中的code 2code 2，则对该，则对该图像编码所需要的平均位数就降为图像编码所需要的平均位数就降为3)(1krlavgLDigital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 099.011.11111.17.237.2)02.0(6)03.0(6)06.0(5)08.0(4)16.0(

11、3)21.0(2)25.0(2)19.0(2)()(702DRkrkkavgRCrprlL位元Digital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 图图8.18.1说明应用说明应用code 2code 2能达到能达到数据压缩的道理数据压缩的道理。图中同时显。图中同时显示了图像的直方图与示了图像的直方图与 。因为这两函数成反比，故因为这两函数成反比，故codecode2 2中的最中的最短码字被分配给图像中最常出现的灰阶短码字被分配给图像中最常出现的灰阶。)(2krlDigital Image Processing,

12、 2nd 2002 R. C. Gonzalez & R. E. Woods 在上面的例子中，在上面的例子中，对出现机率较大的灰阶比出现机率较小者对出现机率较大的灰阶比出现机率较小者分配以较少的位数分配以较少的位数，达到了数据压缩的目的。这个过程常，达到了数据压缩的目的。这个过程常称为称为可变长度编码可变长度编码（variable-length codingvariable-length coding）编码冗余编码冗余是基于图像灰度级出现的可能性。是基于图像灰度级出现的可能性。Digital Image Processing, 2nd 2002 R. C. Gonzalez &

13、 R. E. Woods 8.1.28.1.2像素间冗余性像素间冗余性考虑考虑图图8.28.2中所示的图像。因为这些图像中的灰阶值不是等中所示的图像。因为这些图像中的灰阶值不是等机率分布，故用机率分布，故用可变长度编码可变长度编码可以从像素的直接或自然二进可以从像素的直接或自然二进制码中降低编码冗余性。不过编码过程制码中降低编码冗余性。不过编码过程并不改变图像内各像并不改变图像内各像素间的相关程度素间的相关程度。换言之，用来代表每一图像灰阶值的码并。换言之，用来代表每一图像灰阶值的码并未涉及到像素之间的相关性。这些未涉及到像素之间的相关性。这些相关性来自图像中各物体相关性来自图像中各物体间的结

14、构或几何关系间的结构或几何关系。8.2(e)8.2(e)与与(f)(f)分别显示每一幅图像沿一列所计算出来的分别显示每一幅图像沿一列所计算出来的自相关自相关系数系数 ( autocorrelation coefficient )( autocorrelation coefficient )。Digital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 这些相关系数是用(4.6-30)式的正规化版本所计算出的：(8.1-5)式中(8.1-6)0()()(AnAnnNynyxfyxfnNnA10),(),(1)(Digita

15、l Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods (1) 45 和和 90个样本分开的像个样本分开的像素之间的高度相关；素之间的高度相关；(2) 当当n=1时，高的相关性时，高的相关性Digital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 这些图例反映了数据冗余性的另一个重要形式与这些图例反映了数据冗余性的另一个重要形式与图像内像图像内像素间一种冗余性素间一种冗余性。由于任一已知像素的灰阶值都可以从其近邻。由于任一已知像素的灰阶值都可以从其近

16、邻的值合理的预测出，所以的值合理的预测出，所以各别像素所携带的信息量相当小各别像素所携带的信息量相当小。为了减少图像中的像素间冗余性，一般用于人类视觉和理解为了减少图像中的像素间冗余性，一般用于人类视觉和理解的二维像素数组必须转换成更有效的二维像素数组必须转换成更有效 （但通常是非视觉）的（但通常是非视觉）的形式（如相邻像素之间的差异用来描绘图像）。此种类型的转形式（如相邻像素之间的差异用来描绘图像）。此种类型的转换称为换称为映射映射 ( mapping )( mapping )。如果原始图像元素可以从经转换。如果原始图像元素可以从经转换的数据集合重建就称为的数据集合重建就称为可逆的映射可逆的

17、映射 ( reversible mapping ( reversible mapping ) )Digital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 8.1.38.1.3心理视觉冗余性心理视觉冗余性在正常的视觉处理中，在正常的视觉处理中，某些信息比起其他信息相对不那么重某些信息比起其他信息相对不那么重要要，则我们称此信息是，则我们称此信息是心理视觉冗余的心理视觉冗余的 ( psychovisually( psychovisually redundant ) redundant )。它可以被消除而使图像质量感受无明

18、显损伤。它可以被消除而使图像质量感受无明显损伤。心理视觉冗余性不像编码和像素间冗余，而与真实的或可定心理视觉冗余性不像编码和像素间冗余，而与真实的或可定量的视觉信息有关。只有当信息本身对一般视觉处理并不重量的视觉信息有关。只有当信息本身对一般视觉处理并不重要时才可以被删去。因为要时才可以被删去。因为心理视觉冗余数据被删去造成定量心理视觉冗余数据被删去造成定量信息的损失，所以通常称之为信息的损失，所以通常称之为量化量化 ( quantization )( quantization )。因为它。因为它是一个非可逆的运算，故是一个非可逆的运算，故量化导致有失真的数据压缩量化导致有失真的数据压缩。Di

19、gital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 范例范例8.38.3：量化压缩：量化压缩考虑考虑图图8.48.4（a)a)显示一幅有显示一幅有256256可能灰阶的黑白图像可能灰阶的黑白图像 (b) (b)显示经过显示经过4 4位或位或1616种可能灰度级后的结果，注意在本来种可能灰度级后的结果，注意在本来平滑区域中出现假轮廓（平滑区域中出现假轮廓（利用人眼对灰度不敏感压缩利用人眼对灰度不敏感压缩）。）。 (c)所得的压缩率为所得的压缩率为2 2：1 1。说明利用人类视觉系统特性的量。说明利用人类视觉系统特性的

20、量化使图像有很大改善的可能。用来产生此种结果的方法称化使图像有很大改善的可能。用来产生此种结果的方法称为为改进灰阶改进灰阶 ( IGS , improved gray-scale )量化。量化。Digital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 这个方法认为这个方法认为人类眼睛对边缘有特有的灵敏度，因此对每一人类眼睛对边缘有特有的灵敏度，因此对每一个像素加上一个虚拟随机数以打散这些边缘个像素加上一个虚拟随机数以打散这些边缘，其中虚拟随机，其中虚拟随机数是由量化以前之相邻像素的数是由量化以前之相邻像素的低位产生低

21、位产生。因为低位数相。因为低位数相当随机，这就相当于对伴随于假轮廓的人造边缘加上一定量当随机，这就相当于对伴随于假轮廓的人造边缘加上一定量的随机性。的随机性。表表8.28.2说明这个方法。一个说明这个方法。一个总和起初设定为零总和起初设定为零，接着从目前，接着从目前的的8 8位灰阶值与前一个产生总和的最低位灰阶值与前一个产生总和的最低4 4位相加形成总位相加形成总和。不过如果目前像素值最高四位为和。不过如果目前像素值最高四位为11111111，则用，则用00000000代替代替去相加。所得总和的最高去相加。所得总和的最高4 4位作为编码的像素灰阶值。位作为编码的像素灰阶值。Digital Im

22、age Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods Digital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 重点重点Digital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 8.1.4 8.1.4 保真度准则保真度准则正如在前面所谈到的，心理视觉冗余数据的移除会导致真实正如在前面所谈到的，心理视觉冗余数据的移除会导致真实的或可定量之视觉信息的损失。因为感兴趣的信息可能丢失的或

23、可定量之视觉信息的损失。因为感兴趣的信息可能丢失，所以很需要有一个可重复或再现的方法以，所以很需要有一个可重复或再现的方法以衡量信息丢失的衡量信息丢失的特性与程度特性与程度。这种评估的基本准则通常有两大类：。这种评估的基本准则通常有两大类：(1)(1) 客观保真度准则客观保真度准则( objective fidelity criterion )( objective fidelity criterion )(2)(2) 主观保真度准则主观保真度准则( subjective fidelity criterion )( subjective fidelity criterion )当当信息损失的程

24、度信息损失的程度可以表示成原始的或输入图像与经过压缩可以表示成原始的或输入图像与经过压缩及解压缩的输出图像的函数时，就说这是根据及解压缩的输出图像的函数时，就说这是根据客观的保真度客观的保真度准则准则 ( objective fidelity criterion )( objective fidelity criterion )Digital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 输入与输出图像之间的均方根输入与输出图像之间的均方根( rms )误差就是个好例子误差就是个好例子。假设假设 代表输入图像，对输入图像

25、经过压缩与解压缩代表输入图像，对输入图像经过压缩与解压缩所得的图像所得的图像 代表代表 的估测或近似。对的估测或近似。对 或或的任意值的任意值， 与与 之间的误差之间的误差 可以定可以定义为义为(8.1-7)因此，两个图像之间总误差为因此，两个图像之间总误差为),(yxf),(yxf),(yxfxy),(yxf),(yxf),(yxe),(),(),(yxfyxfyxe ),(),(1010MxNyyxfyxfDigital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 与 之间的均方根误差之间的均方根误差( root-

26、mean-square error ) 为：为：(8.1-8)输出图像的均方信噪比输出图像的均方信噪比( mean square signal-to-noise ratio)(8.1-9),(yxf),(yxfrmse2110102rms),(),(1 MxNyyxfyxfMNe2101010102 ),(),(),(MxNyMxNymsyxfyxfyxfSNRSNRrms取平方根取平方根Digital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods Digital Image Processing, 2nd 2002 R

27、. C. Gonzalez & R. E. Woods 主观保真度准则主观保真度准则 ( subjective fidelity criterion )虽然客观保真度准则提供了一种简单方便的评估机制，但大虽然客观保真度准则提供了一种简单方便的评估机制，但大多数解压缩图像的最终观察者还是人。因此，用一个观察者多数解压缩图像的最终观察者还是人。因此，用一个观察者的主观评估来衡量图像质量往往更为适合。其作法为：选一的主观评估来衡量图像质量往往更为适合。其作法为：选一部分适当的观察者代表，让他们对典型的解压缩图像评部分适当的观察者代表，让他们对典型的解压缩图像评分，然后对其评分取平均。评分可以

28、用一个绝对等级尺度或分，然后对其评分取平均。评分可以用一个绝对等级尺度或是以是以 与与 对照比较对照比较。表表8.3显示一种可能的显示一种可能的绝对等级尺度绝对等级尺度。),(yxf),(yxfDigital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 1 极好极好 2好好 3过得去过得去 4勉强可以勉强可以5 差差 6不可用不可用Digital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 范例范例8.48.4：图像质量的比较：图像质量的比较图

29、图8.4(b)8.4(b)和和(c)(c)中量化后图像的均方根误差为中量化后图像的均方根误差为6.936.93与与6.786.78灰灰阶。相对应的阶。相对应的rmsrms信噪比为信噪比为10.2510.25与与10.3910.39。虽然这些。虽然这些数值很类似，但两幅被编码图像的主观视觉质量的评价却不数值很类似，但两幅被编码图像的主观视觉质量的评价却不同：图同：图8.4(b)8.4(b)为勉强通过为勉强通过( marginal )( marginal )等级，而等级，而8.4(c)8.4(c)则则是可以通过是可以通过( passable )( passable )的等级。的等级。Digital

30、 Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 8.28.2图像压缩模型图像压缩模型如下图所示，一个压缩系统由两个不同的结构区块组成：如下图所示，一个压缩系统由两个不同的结构区块组成：编码器编码器 (encoder)(encoder)与与译码器译码器 (decoder)(decoder)。输入图像。输入图像 被被送进编码器，编码器从输入数据中产生一组符号。经过通道送进编码器，编码器从输入数据中产生一组符号。经过通道(channel)(channel)传输后，被编码过的数据送到译码器，译码器产生传输后，被编码过的数据送到译

31、码器，译码器产生一个重建输出图像一个重建输出图像 。),(yxf),(yxfDigital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 图中所显示的编码器与译码器都含有两个相当独立的功能区图中所显示的编码器与译码器都含有两个相当独立的功能区块或子区块。编码器由信源编码器块或子区块。编码器由信源编码器( source encoder )( source encoder )与信道与信道编码器编码器( channel encoder )( channel encoder )组成，前者移除输入组成，前者移除输入冗余性冗余性，后

32、者，后者则增强信源编码器输出的则增强信源编码器输出的抗噪声抗噪声能力。译码器则包括信道解能力。译码器则包括信道解码器码器(channel decoder)(channel decoder)及其后的信源译码器及其后的信源译码器(source decoder)(source decoder)Digital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 8.2.1信源编码器和译码器信源编码器和译码器信源编码器负责缩减或删去输入图像中的任何冗余性。具体信源编码器负责缩减或删去输入图像中的任何冗余性。具体的应用与伴随的保真度要求决

33、定了在任何所给情况下可用的的应用与伴随的保真度要求决定了在任何所给情况下可用的最好编码方法。通常，这种方法可用三个独立运算串联的模最好编码方法。通常，这种方法可用三个独立运算串联的模型来表示。如型来表示。如图图8.6(a)8.6(a)。第一阶段第一阶段由由映射器映射器 (mapper)(mapper)将输入将输入资料转换成可以缩减输入图像之像素间冗余性的格式，资料转换成可以缩减输入图像之像素间冗余性的格式，DCTDCT变变换是一个映射例子。换是一个映射例子。第二阶段第二阶段是是量化器量化器 (quantizer)(quantizer)，根据，根据某一个预先建立的保真度准则，降低映像器输出的精确

34、度以某一个预先建立的保真度准则，降低映像器输出的精确度以缩减心理视觉冗余性。缩减心理视觉冗余性。第三阶段第三阶段是是符号编码器符号编码器 (symbol (symbol coder)coder)产生一个表示量化器输出的固定或可变长度码并根据产生一个表示量化器输出的固定或可变长度码并根据该码映射输出。以减少编码冗余。该码映射输出。以减少编码冗余。Digital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 图图8.6(b)8.6(b)所显示的信源译码器仅含有两个部份：一个所显示的信源译码器仅含有两个部份：一个符号解符号解码

35、器码器 (symbol decoder)(symbol decoder)和一个和一个反映射器反映射器 (inverse mapper)(inverse mapper)。这两个区块依相反的顺序执行信源编码器中的符号编码器和这两个区块依相反的顺序执行信源编码器中的符号编码器和映射区块的反运算。因为量化产生不可逆的信息损失，故在映射区块的反运算。因为量化产生不可逆的信息损失，故在通常的译码器模型中并未包括反量化器区块。通常的译码器模型中并未包括反量化器区块。Digital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 8.2.

36、28.2.2信道编码器和译码器信道编码器和译码器当信道中有噪声或容易错误时，信道编码器和译码器在整个当信道中有噪声或容易错误时，信道编码器和译码器在整个编码编码- -译码过程中扮演重要的角色。信道编码器在信源编码资译码过程中扮演重要的角色。信道编码器在信源编码资料中料中插入插入受控制的受控制的冗余性冗余性来来减少信道噪声的冲击减少信道噪声的冲击。因为信源。因为信源编码器的输出不含有冗余性，如果不加此受控制的冗余性编码器的输出不含有冗余性，如果不加此受控制的冗余性就会对传输噪声高度敏感。就会对传输噪声高度敏感。最有名的信道编码技术之一是由最有名的信道编码技术之一是由R. W. R. W. Ham

37、mingHamming发明的。它发明的。它是是对要编码的数据加入足够的位，以确保有效码字之间的对要编码的数据加入足够的位，以确保有效码字之间的位改变至少要达某一最小数位改变至少要达某一最小数。Digital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 伴随伴随4 4位二进制位二进制数数 的的 7 位元位元 Hamming (7,4) code 为为(8.2-1)其中其中 表示表示 XOR 运算。注意位元运算。注意位元 ， 和和 分別是字节分別是字节 ， 与与 的的偶校验偶校验 (even parity bits)( 回

38、想一下：若在一串二位字符串中有偶数个回想一下：若在一串二位字符串中有偶数个1 1的位，则其有的位，则其有 偶校验偶校验。)0123bbbb76521hhhhh012401320231bbbhbbbhbbbh07162533bhbhbhbh1h2h4h023bbb013bbb012bbbDigital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 要对汉明编码的结果译码，信道译码器必须检验编码值，对要对汉明编码的结果译码，信道译码器必须检验编码值，对先前已建立偶同位校验的字节进行奇同位校验。先前已建立偶同位校验的字节进行奇

39、同位校验。单一个位单一个位元错误元错误由非零的同位字组由非零的同位字组 所示，其中所示，其中(8.2-2)如果发现了非零值如果发现了非零值，则译码器只要将同位字组指出的码字位，则译码器只要将同位字组指出的码字位元位置取补码即可。接着从被更正的码字中提取出译码后的元位置取补码即可。接着从被更正的码字中提取出译码后的二进制数值二进制数值 。124ccc765447632275311hhhhchhhhchhhhc7653hhhhDigital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 范例范例8.58.5：Hamming

40、encodingHamming encoding考虑考虑表表8.28.2的的4 4位位IGSIGS数据在有噪声的信道上传输。单一数据在有噪声的信道上传输。单一位错误会引起解压缩后像素的灰阶值最高达位错误会引起解压缩后像素的灰阶值最高达128128阶误差。阶误差。汉明信道编码器藉由插入足够冗余性的方法可以检出并更正汉明信道编码器藉由插入足够冗余性的方法可以检出并更正单一个位错误。由单一个位错误。由(8.2-1)(8.2-1)式，式，表表8.28.2中第一个中第一个IGSIGS值值(0110)(0110)的汉的汉明编码结果为明编码结果为 。因为汉明信道编码器使表示。因为汉明信道编码器使表示IGSI

41、GS数据所需的位数从数据所需的位数从4 4增加到增加到7 7，所以在，所以在IGSIGS例子中所提到例子中所提到的的2 2：1 1压缩率也减到压缩率也减到8/78/7或或1.141.14：1 1。压缩率减少就是增加压缩率减少就是增加抗噪声能力所付出的代价抗噪声能力所付出的代价。21100110Digital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 8.38.3信息论基础信息论基础在在8.18.1节中我们介绍了几种缩减用来表示一图像之数据量的节中我们介绍了几种缩减用来表示一图像之数据量的方式。很自然产生的问题是：表示

42、一幅图像所需的数据量到方式。很自然产生的问题是：表示一幅图像所需的数据量到底可少到什么程度？也就是说，底可少到什么程度？也就是说，是否存在有一个既足够完是否存在有一个既足够完全地描述图像又不丢失信息的最小数据量全地描述图像又不丢失信息的最小数据量？信息论提供一个数学架构以回答这个以及相关的问题。信息论提供一个数学架构以回答这个以及相关的问题。Digital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 8.3.1测量测量信息信息信息论的基本前提是信息论的基本前提是信息的产生可以被模拟为一个概率过程信息的产生可以被模拟为一

43、个概率过程，这个过程可以用与我们的直觉相一致的方法度量。根据，这个过程可以用与我们的直觉相一致的方法度量。根据这个假设，一个发生机率为这个假设，一个发生机率为 的的随机事件随机事件 ，我们称它我们称它含有含有(8.3-1)单位的单位的信息信息。 这个量常称为这个量常称为 的的自信息自信息( self-Information )（P(E)=1,则则I(E)=0,信息为信息为0）)(EPE)(log)(1log)(EPEPEI)(EIEDigital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 8.3.28.3.2信息信道

44、信息信道当在信息源与信息用户之间传递自信息时，我们说信息当在信息源与信息用户之间传递自信息时，我们说信息源与信息用户之间是由源与信息用户之间是由信息信道信息信道 ( information channel )相相连接。连接。图图8.78.7显示一个离散信息系统的简单数学模型。这里显示一个离散信息系统的简单数学模型。这里特别感兴趣的参数是系统的特别感兴趣的参数是系统的容量容量 ( capacity )，定义成系统传定义成系统传递信息的能力。假设图中的递信息的能力。假设图中的信息源产生一个随机的符号序列信息源产生一个随机的符号序列 ，称为原始字母集称为原始字母集A A ( source alpha

45、bet A )，集合中的元素用集合中的元素用 表示，称为表示，称为符号符号(symbol)或字母或字母 (letter)。信息源会产生符号信息源会产生符号 这事件的机率这事件的机率为为 ，且，且(8.3-2),21Jaaajaja)(jaPJjjaP11)(Digital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods Chapter 8Image CompressionDigital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 一个 维向量 常用

46、来表示所有原始符号机率的集合 。有限的总总体体 (ensemble) 完整描述了此信息源。假设离散源发送符号 的机率为 ，则根据(8.3-1)式，一个单一信息源符号所产生的自我信息为 。如果产生 个信息源符号，大数定律告诉我们，对足够大的，符号 平均将输出 次。因此平均自我信息为1JTJaPaPaP)(,),(),(21z)(,),(),(21JaPaPaP),(zAja)(jaP2()log()jjI aP a kkja)(jakP)(log)()(log)()(log)(2211JJaPakPaPakPaPakPDigital Image Processing, 2nd 2002 R. C

47、. Gonzalez & R. E. Woods 或或每个信息源输出的平均信息每个信息源输出的平均信息用用 表示为表示为(8.3-3)这个量称为信息源的这个量称为信息源的不确定性不确定性 (uncertainty)或或熵熵 (entropy)。它定义了由观察单一个信息源输出所得的它定义了由观察单一个信息源输出所得的平均信息量平均信息量。)(log)(1jJjjaPaPk)(zH)(log)()(1jJjjaPaPHzDigital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 因为我们对图8.7信息信道的输入是以

48、一个离散的随机变量为模型来描述，所以传递到信息信道输出的信息也是一个离散随机变数，它的值来自一个可数符号集合称为信道字母集信道字母集B (channel alphabetB)。符号 被呈现给信信息息使用者使用者 (information user)的这事件的机率为 。有限总集 完全描述了通道输出以及被用户接收到的信息，其中 。一个已知通道输出机率 和信源原始机率分布 的关系式为(8.3-4),21kbbbkb)(kbP),(vBTkbPbPbP)(,),(),(21v)(kbPz)()|()(1jJjjkkaPabPbPDigital Image Processing, 2nd 2002 R.

49、 C. Gonzalez & R. E. Woods 如果在上式中的条件机率被安排成 的矩阵 ，使得(8.3-5)则全部输出字母的机率分布可由下式计算(8.3-6) 称为正向通道转移矩阵正向通道转移矩阵 (forward channel transition matrix)或简称信信道矩阵道矩阵 (channel matrix) 。JK Q)|()|()|(.)|()|()|()|(211212111JKKKJabPabPabPabPabPabPabPQQzv QDigital Image Processing, 2nd 2002 R. C. Gonzalez & R. E.

50、Woods 为了求一个具有信道矩阵 的信道容量，我们必须先计算在使用者观察到某特定输出 的假设下，信息源的熵值。8.3-4式定义对任意观察的 的原始符号分布，所以每一个 都有一个条件熵函数条件熵函数 (conditional entropy function)。可写成(8.3-7)此表示式对所有 的期望值为(8.3-8)Qkbkbkb)|(log)|()|(1kjJjkjkbaPbaPbHzkb)()|()|(1kKkkbPbHHzvzDigital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 以(8.3-7)式取代

51、并做一些改写之后，上式可写成(8.3-9) 的术语称为 对 的模棱两可不确定性模棱两可不确定性 (equivocation)它代表假设已观察到由一原始符号的产生所得的输出符号后此一原始符号的平均信息。因为 是在假设不知道任何关于输出符号条件下的一个原始符号的平均信息，故 与 之间的差值就是因观察到一个输出符号所接收到的平均信息。)|(kbH z)|(log),()|(11kjJjKkkjbaPbaPHvz)|(vzHzv)(zH)|(vzH)(zHDigital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 这差值称之为

52、 与 的交互信息(mutual information)(8.3-10)将(8.3-3)与(8.3-9)式代入得到(8.3-11)可重写成(8.3-12)zv)|()(),(vzzvzHHI)()(),(log),(),(11kjkjJjKkkjbPaPbaPbaPIvzJikiikjkjJjKkjqaPqqaPI111)(log)(),(vzDigital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 从在 中所有可能的信源机率中选择出 的最大值，就是以信道矩阵 所描述之信道的容量 (capacity) ，亦即(8.3

53、-13)其中最大值是对所有可能的输入符号机率做考虑而选出的，它不取决于信源的输入概率，而取决于信道的条件概率。z),(vzI),(maxvzzIC QCDigital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 范例范例8.68.6：二元的状况考虑 的一个二元信息源。信息源产生符号 与 的机率分别为 及 。熵值为因为 ，所以 只与单一参数有关。方程式右边的部份称为二元熵函数( binary entropy function)，记作 。图8.8 (a)显示 在的图。1 , 0,21aaA1a2abspaP)(1bsbsp

54、paP1)(2bsbsbsbsppppH22loglog)(zTbsbsTppaPaP1 ,)(),(21z)(zHbsp)(bsH)(bsbspH10bspDigital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 现在假设信息要在一个有噪声的二元信道上传送并令任一符号在传送期间发生错误的机率为 ，这样的通道称为二元对称通道(binary symmetric channel , BSC )，定义为接收到输出 与 的机率可以由(8.3.6)式求得：epeeeeeeeepppppppp11Q1b2b) 1 ()0()()

55、(21PPbPbPppppppppppppppbsebsebsebsebsbseeeeQzvDigital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 由(8.3-12)式来计算BSC的交互信息：显示在图8.8 (b)。图(c)中的BSC容量为当Pe=0(信道不出错），或Pe=1时，信道容量取得1比特最大值，当Pe=1/2时，容量为0，信道不能传送任何信息。)()(),(ebsebsebsbspHppppHIvz)(1ebspHCDigital Image Processing, 2nd 2002 R. C. Gonz

56、alez & R. E. Woods Chapter 8Image CompressionDigital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 8.3.3基本编码定理基本编码定理在8.3.2节中所介绍的数学架构是以图8.7的模型为基础所建立的。本节中我们给该模型加上一个通讯系统并探讨关于信息的编码或表示的三个基本定理，如下图所示。Digital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 无噪声编码定理无噪声编码定理当信息信道与通

57、讯系统都是无错误时，通讯系统的主要功能是尽可能简洁地表示信息源。在这种情况下，无噪声编码定无噪声编码定理理 (noiseless coding theorem) 也称为Shannons first theorem定义出每个原始符号所能达到的最小平均码字长度。一个具有限总集 和具有统计独立信息源符号的信息源称为零记忆(zero-memory)源。如果考虑它的输出为从原始字母表来的一个n重符号，则信息源输出会是 个可能值之一，并记作 ，所有可能集合),(zAnJi,21nJADigital Image Processing, 2nd 2002 R. C. Gonzalez & R. E.

58、Woods 一已知 的机率 与单一个符号机率 的关系为(8.3-14)向量 表示所有讯源机率的集合信息源的熵为(8.3-15)i)(iP)(iaP)()()()(21jnjjiaPaPaPPz)(,),(),(21nJPPP)()(log)()(1zznHPPHiJiinDigital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 因为讯源输出 的自我信息为 ，理应用长度为整数 的码字对 编码，使得(8.3-16)对此结果乘以 并对所有 求和，得出：i )(1logiP)(ili1)(1log)()(1logiiiPlP

59、)(iPi1)(1log)()()()(1log)(111iJiiiJiiiJiiPPlPPPnnnDigital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 或(8.3-17)其中 表示对应于非扩展源之n 阶扩展的码字平均长度：(8.3-18)由 (8.3-15) 及 (8.3-17) 式(8.3-19)1)()(zzHLHavgavgL)()(1iJiiavglPLnnHnLHavg1)()(zzDigital Image Processing, 2nd 2002 R. C. Gonzalez & R. E

60、. Woods 在极限情况下，上式变成(8.3-20)因为 是 的低界，故任何编码策略的效率(efficiency)可定义为(8.3-21)(limzHnLavgn)(zHnLavgavgLHn)(zDigital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 范例范例8.7：扩展编码第一种编码的熵0.918 bits/symbol，效率为(1)(0.918)/1=0.918二阶扩展编码的平均码长为17/9或1.89，熵是0.9182=1.83所以效率为1.83/1.89 = 0.97，比第一种稍好一些。Digital Image Processing, 2nd 2002 R. C. Gonzalez & R. E. Woods 有噪声编码定理有噪声编码定理范例范例8.88.8：有噪声的二元信道 假定一个BSC有错误机率 ，提高通讯可靠度的一个简单方法是将每一讯息重复几次。例如，000或111。传送3个符号讯息过程中不发生错误的机率是 或发生一个错误的机率 ，两个错误的机率 ，而