数字图像处理 第8章-图像压缩
8.1 基础知识
术语数据压缩是指减少表示给定信息量所需数据量的处理。在该定义中，数据和信息是不相同的事情；数据是信息传递的手段。
因为相同数量的信息可以用不同数量的数据表示，包含不相关或重复信息的表示称之为冗余数据。如果我们令b和b’代表相同信息的两种表示中的比特数(或信息携带单元)，那么用b比特表示的相对数据冗余R是：
R=1−1/C
R=1-1/C
R=1−1/C
其中，C通常称为压缩率，定义为
C=b/b′
C=b/b'
C=b/b′
在数字图像压缩的内容中，b通常是以二维灰度值阵列表示一幅图像所需的比特数。
二维灰度阵列是人们观察和解释图像的首选格式，并且以它作为判定所有其他表示的标准。然而，当它变成紧凑的图像表示时，这些格式就远不是最佳格式了。二维灰度阵列受如下可被识别和利用的三种主要类型的数据冗余的影响：
1、编码冗余
2、空间和时间冗余
3、不相关的信息
当一个或多个几余被减少或消除时，压缩就实现了。
如下图所示：
8.1.1 编码冗余
我们已经在图像的灰度值为随机量的假设基础上，探讨了通过直方图处理进行图像增强的技术。我们将利用类似的表示方法介绍最佳信息编码。
假设在区间[0,L-1]内的一个离散随机变量rkr_krk用来表示一幅M*N的图像的灰度，并且每个rkr_krk发生的概率为 pr(rk)p_r(r_k)pr(rk)。
pr(rk)=nkMN,k=0,1,2,⋅⋅⋅.L−1
p_r(r_k)={n_k\over MN},k=0,1,2,···.L-1
pr(rk)=MNnk,k=0,1,2,⋅⋅⋅.L−1
其中，L是灰度级数，nkn_knk是第k级灰度在图像中出现的次数。
8.1.2 空间冗余和时间冗余
考虑图8.1(b)中由计算机生成的恒定灰度线的集合。在对应的二维灰度阵列中:
1.所有 256 种灰度都是等概率的。如图 8.2所示，图像的直方图是均匀的。
2.因为每条线的灰度是随机选择的，在垂直方向上，每条线的像素彼此是独立的。
3.因为沿每条线的像素是相同的，因此在水平方向上它们是最大相关的(完全互相依赖)。
在多数图像中，像素是空间(在x和y方向)和时间相关的(当该图像是视频序列的一部分时)。因为多数像素灰度可根据相邻像素灰度进行合理的预测，所以单个像素携带的信息较少。在这种意义上一个像素可由其相邻像素推断出来，那么它的视觉贡献的大多数就是冗余的。为减少空间与时间相关的像素涉及的冗余，二维灰度阵列必须变换为更有效但通常不可见的表示。例如，行程长度或相邻像素之间的差异可供利用。这种类型的变换称为映射。如果原始二维灰度阵列的像素可以根据变换后的数据集合无误地重建，则称这个映射是可逆映射，否则称这个映射是不可逆映射。
8.1.3 不相关的信息
压缩数据集最简的方法之一是从集合中消除多余的数据。在数字图像压缩方面，被人的视觉系统忽略的信息或与图像预期的应用无关的信息显然都是删除的候选者。
8.1.4 图像信息的度量
在前几节中，我们介绍了减少用于表示一幅图像的数据量的几种方法。自然地，出现的问题是:表示一幅图像中的信息实际上需要多少比特?也就是，存在一个不丢失信息的充分地描述一幅图像的最小数据量吗?信息论提供了回答这个问题和相关问题数学框架。它的基本前提是信息的产生可用一个概率过程建模，该过程可以用一种与直觉一致的方式加以度量。根据这一推测，一个具有概率P(E)的随机事件E可被说成是包含
I(E)=log1P(e)=−logP(E)
I(E)=log{1\over P(e)}=-logP(E)
I(E)=logP(e)1=−logP(E)
单位的信息。如果 P(E)=1(即事件总会发生)时，1(E)=0，并且，认为它没有信息。因为相关的该事件没有不确定性,所以在事件发生的通信过程中不会传递任何信息。
对数的底决定了度量信息所用的单位。如果使用以m为底的对数，则这种度量称为 m 元单位。如果底选择为2，则信息的单位是比特。注意，如果P(E)=1/2，那么I(E)=-log,1/2或1比特。也就是说，当两个出现概率相等的事件之一发生时，传达的信息量是1比特。一个简单的例子就是投掷一枚硬币及传递的结果。
8.1.5 保真度准则
在之前的讨论中，我们注意到去除“与视觉不相关”信息会导致真实的或一定数量的图像信息的丢失。因为信息的丢失，因此需要一种量化这种丢失的本质的方法。
两类准则可用于这样的评估：
(1)客观保真度准则；
(2)主观保真度准则。
当信息损失可以表示为压缩处理的输入和输出的数学函数时，则称其是以客观保真度准则为基础的。一个例子是两幅图像间的均方根误差。
令f(x,y)f(x,y)f(x,y)是输入图像，并令f^(x,y)\hat f(x,y)f^(x,y)是f(x,y)f(x,y)f(x,y)的近似，它来自对输入先压缩后解压缩的结果。对x和y的所有值，f(x,y)f(x,y)f(x,y)和f^(x,y)\hat f(x,y)f^(x,y)之间的误差e(x,y)e(x,y)e(x,y)为：
e(x,y)=f^(x,y)−f(x,y)
e(x,y)=\hat f(x,y)-f(x,y)
e(x,y)=f^(x,y)−f(x,y)
因此，两幅图像间的总误差为
∑x=0M−1∑y=0N−1[f^(x,y)−f(x,y)]
∑_{x=0}^{M-1}∑_{y=0}^{N-1}[\hat f(x,y)-f(x,y)]
x=0∑M−1y=0∑N−1[f^(x,y)−f(x,y)]
其中，图像的大小为 MN。而f(x,y)f(x,y)f(x,y)和f^(x,y)\hat f(x,y)f^(x,y)之间的均方根误差 ermse_{rms}erms为在 MN阵列上平均误差的平方的平方根，或写为
erms=[1MN∑x=0M−1∑y=0N−1[f^(x,y)−f(x,y)]2]
e_{rms}=[{1\over MN}∑_{x=0}^{M-1}∑_{y=0}^{N-1}[\hat f(x,y)-f(x,y)]^2]
erms=[MN1x=0∑M−1y=0∑N−1[f^(x,y)−f(x,y)]2]
如果认为 f^(x,y)\hat f(x,y)f^(x,y)是原始图像 f(x,y)f(x,y)f(x,y)和一个误差或“噪声”信号e(x,y)e(x,y)e(x,y)的和，则用 SNRmsSNR_{ms}SNRms表示的输出图像的均方信噪比可定义为
SNRms=∑x=0M−1∑y=0N−1f^(x,y)2∑x=0M−1∑y=0N−1[f^(x,y)−f(x,y)]2
SNR_{ms}={∑_{x=0}^{M-1}∑_{y=0}^{N-1}\hat f(x,y)^2 \over ∑_{x=0}^{M-1}∑_{y=0}^{N-1}[\hat f(x,y)-f(x,y)]^2 }
SNRms=∑x=0M−1∑y=0N−1[f^(x,y)−f(x,y)]2∑x=0M−1∑y=0N−1f^(x,y)2
表示为 SNRmsSNR_{ms}SNRms的信噪比的均方根值可通过求该式的平方根得到。尽管客观保真度准则提供了一种简单方便的评估信息损失的方法，但解压缩后的图像最终还是由人来观察的。因此，使用人的主观评估来衡量图像的质量通常更为适当。主观评估是通过向观察者显示解压缩的图像，并将他们的评估结果进行平均得到的。评估可使用一个绝对等级尺度或借助于f(x,y)f(x,y)f(x,y)和f^(x,y)\hat f(x,y)f^(x,y)的并排比较来获得。
8.1.6 图像压缩模型
图像压缩系统是由两个不同的功能部分组成的:一个编码器和一个解码器。编码器执行压缩操作，解码器执行解压缩的互补操作。
图像 f(x,…)f(x,…)f(x,…)被输入到编码器中，这个编码器创建该输入的压缩表示。把这一表示存储起来以备后续应用，或为传输而存储，以便远程应用。
当压缩后的表示送入其互补的解码器中时，就会产生重建的输出图像f^(x,…)\hat f(x,…)f^(x,…)。在静止图像应用中，编码的输入和解码器的输出分别是f(x,y)f(x,y)f(x,y)和f^(x,y)\hat f(x,y)f^(x,y);在视频应用中，它们分别是f(x,y,t)f(x,y,t)f(x,y,t)和f^(x,y,t)\hat f(x,y,t)f^(x,y,t)，其中离散参数t规定为时间。通常f^(x,…)\hat f(x,…)f^(x,…)可能是也可能不是f(x,y)f(x,y)f(x,y)的精确的复制品。如果是f(x,y)f(x,y)f(x,y)的精确复制品，则压缩系统被称为无误差的、无损的或信息保持的压缩系统;如果不是f(x,y)f(x,y)f(x,y)的精确复制品，则重建的输出图像就会失真，并且压缩系统称为有损压缩系统。
编码或压缩过程
图 8.5的编码器被设计为通过一系列三个独立操作去除在 8.1.1节至8.1.3节描述的冗余度的形式。
在编码处理的第一个阶段，映射器把f(x,…)f(x,…)f(x,…)变换为设计来降低空间和时间冗余的形式(通常不可见)。这一操作通常是可逆的，并且可能会也可能不会直接减少表示图像所需的数据量。行程编码就是一个映射的例子，该映射通常在编码处理的第一步中就会得到压缩。把一幅图像映射为一组不相关的变换系数是相关情况的一个例子(为实现压缩，必须对系数进行进一步处理)。在视频应用中，映射器使用前面的(在某些将来的情况下)视频帧来帮助去除时间冗余。
图 8.5中的量化器根据预设的保真度准则来降低映射器输出的精度。其目的是排除压缩表示的无关信息，这一操作是不可逆的。当希望进行无误差压缩时，这一步必须略去。在视频应用中，通常需要度量编码输出的比特率(比特/秒)，并调整量化器的操作，以保持预设的平均输出比特率。这样，输出的视觉质量就可根据图像内容逐帧变化。
在第三阶段，即信源编码处理的最后阶段，图 8.5 中的符号编码器生成一个定长编码或变长编码来表示量化器的输出，并根据该编码来变换输出。在大多数情况下，使用变长编码。最短的码字赋予出现频率最高的量化器输出值，以最小化编码冗余。这种操作是可逆的。该操作完成后，输入图像对于8.1.1节到8.1.3节中所描述的三种冗余的每一种去除都被处理过了。
解码或解压缩过程
图 8.5 中的解码器仅包含两个部分:一个符号解码器和一个反映射器。
它们以相反的顺序执行编码器的符号编码器和映射器的反操作。因为量化导致了不可逆的信息损失，所以反量化器模块没有包含在通常的解码器模型中。在视频应用中，解码后的输出帧保留在内部帧存储器中(没有显示)，并用于重新插入在编码器中去除的时间几余。
8.2 一些基本的压缩方法
8.2.1 霍夫曼编码
即我们数据结构中常说的哈夫曼编码。
8.2.2 Golomb 编码
符号⌊x⌋⌊x⌋⌊x⌋表示小于等于x的最大整数, ⌈x⌉⌈x⌉⌈x⌉表示大于等于x的最小整数，xmodyx mod yxmody表示x被y除的余数。
给定一个非负整数n和一个正整数除数m>0后，表示为Gm(n)G_m(n)Gm(n)的n关于m的Golomb编码是商⌊n/m⌋⌊n/m⌋⌊n/m⌋的一元编码和nmodmn mod mnmodm 的二进制表示的一个合并。Gm(n)G_m(n)Gm(n)的构建如下：
1、形成商⌊n/m⌋⌊n/m⌋⌊n/m⌋的一元编码(整数q的一元编码定义为q个1紧跟着一个 0)
2、令k=[log2m],c=2k−m,r=nmodmk=[log_2m],c=2^k-m,r = n \quad mod\quad mk=[log2m],c=2k−m,r=nmodm，并计算截短的余数r’，例如，使其满足
r′={r截短至k−1比特0≤r r'=\begin{cases} r截短至 k-1比特&0≤r r+c截短至k比特 &其他 \end {cases} r′={r截短至k−1比特r+c截短至k比特0≤r 3、连接步骤1和步骤2的结果。 8.2.3 算术编码 与前两节的变长编码不同，算术编码生成的是非块码。 算术编码给信源符号(或消息)的整个序列分配了一个单一的算术码字。这个码字本身定义了一个介于0和1之间的实数间隔当消息中的符号数量增加时，用于表示消息的间隔会变小，而表示该间隔所需的信息单位(假设为比特)的数量则会变大。消息的每个符号根据其出现的概率来减小该区间的大小。因为这种技术不要求像霍夫曼编码方法那样将每个信源符号转换成这些编码符号的整数(即每次对一个符号进行编码)，所以它仅在理论上达到了山农第一定理所设定的界限。 8.2.4 LZW编码 一种致力于图像中的空间冗余的无误差压缩方法，称为Lempel-Ziv-Welch(LZW)编码的这种技术将定长码字分配给变长信源符号序列。 8.2.5 行程编码 沿其行(或列)重复灰度的图像，通常可用相同灰度的行程表示为行程对来压缩，其中每个行程对指定一个新灰度的开始和具有该灰度的连续像素的数量。这种称为行程编码的技术，是20世纪50年代发展起来的，连同其二维扩展一起，已成为传真编码标准的压缩方法。压缩是通过消除空间冗余的一种简单形式(即一组相同的灰度)来实现的。当相同像素的行程较小(或没有)时，行程编码会导致数据扩展。 8.2.6 基于符号的编码 在基于符号或基于记号的编码中，一幅图像被表示为多幅频繁发生的子图像的一个集合，称为符号。每一个这样的符号都存储在一个符号字典中，且该图像以一个三元组(x1,y1,t1),(x2,y2,t2),…{(x_1,y_1,t_1),(x_2, y_2, t_2),…}(x1,y1,t1),(x2,y2,t2),…的集合来编码，其中，每个(xi,yi)(x_i,y_i)(xi,yi)对规定了图像中一个符号的位置，而记号tit_iti是该符号或子图像在字典中的地址。 也就是说，每一个三元组表示图像中一个字典符号的一个实例。通过仅存储一次重复的符号，可以有效地压缩图像通，特别是在文档存储和检索应用中，在这种情况下，符号通常是重复多次的字符位图。 考虑图 8.17(a)中简单的两级灰度图像。它包含一个字 banana，该字由三个单一符号abn组成:3 个a、1个b和2个n。假如b是在编码过程中第一个识别的符号，其 97位图存储在符号字典中的位置0内。如图 8.17(b)所示，识别b位图的记号是 0。这样，在编码后的图像表示中，第一个三元组是(0.2.0)「见图 8.17©，它指出表示b符号的矩形位图的左上角在解码图像中被放在了位置(0,2)处。对于a和n符号的位图被识别之后加到字典上，图像的其余部分可使用5个附加的三元组编码。只要用于定位图像中的符号的 6个三元组及定义它们的 3个位图小于原图像就可实现压缩。在这种情况下，起始图像有 951*1或459 比特，假定每个三元组由3个字节组成，压缩后的表示有(6x3x8)+[(9x7)+(6x7)+(6x6)]或 285 比特:得到的压缩率为 C=1.61。为对图 8.17©中基于符号的表示解码，您可以从符号字典中读取以三元组形式规定的符号位图，并将它们放置在每个三元组指定的空间坐标处。 8.2.7 比特平面编码 前几节讨论的行程编码技术和基于符号的编码技术可通过单独处理图像的比特平面的方法用于多于两级灰度的图像。 称为比特平面编码的这种技术基于如下概念： 把一幅多级(单色或彩色)图像分解为一系列二值图像，并使用几种熟知的二值压缩方法之一来压缩每幅二值图像。 一幅m比特单色图像的灰度可以用如下形式的基2的多项式来表示: am−12m−1+am−22m−2+⋅⋅⋅+a121+a020 a_{m-1}2^{m-1}+a_{m-2}2^{m-2}+···+a_12^1+a_02^0 am−12m−1+am−22m−2+⋅⋅⋅+a121+a020 基于这种特性，将该图像分解为二值图像集的一种简单方法是把该多项式的m个系数分离为m个1比特的比特平面。 正如 3.2.4节中解释的那样，最低阶比特平面(对应最低阶比特的平面)是通过收集每个像素的a0a_0a0比特生成的，而最高阶比特平面包含am−1a_{m-1}am−1比特或系数。一般来讲，每个比特平面都由给其像素置一个来自原始图像每一像素的合适的比特值或多项式系数来重建。这种分解方法的固有缺点是灰度的较小变化会对比特平面的复杂性产生显著的影响。 例如，如果一个灰度为127(01111111)的像素与一个灰度为 128(10000000)的像素相邻，每个比特平面将包含一个对应0到1(或1到0)的转换。譬如，因为127和128的二进制码的最高阶比特不同，所以最高比特平面将包含一个与值为1的像素相邻的零值像素，在该点产生一个0到1(或1到0)的转换。 一种可替代的分解方法(降低较小灰度变化带来的影响)是首先用一个m比特格雷码表示图像。对应于前一个式子中多项式的 m 比特格雷编码 gm−1⋅⋅⋅g2g1g0g_{m-1}···g_2g_1g_0gm−1⋅⋅⋅g2g1g0可由下式计算得到: gi=ai⊕ai+1,0≤i≤m−2 g_i=a_i⊕a_{i+1},0≤i≤m-2 gi=ai⊕ai+1,0≤i≤m−2 gm−1=am−1 g_{m-1}=a_{m-1} gm−1=am−1 这种编码的唯一特性是连续码字只有1个比特位不同。因此，较小的灰度变化不太可能影响所有m个比特平面。例如，当灰度级127和128 相邻时，只有最高阶比特平面包含有一个0到1的转换，因为对应于127和128的格雷码分别是01000000和11000000。 8.2.8 块变换编码 该技术把图像分成大小相等(如8x8)且不重叠的小块，并使用二维变换单独地处理这些块。在块变换编码中，用一种可逆线性变换(如傅里叶变换)把每个块或子图像映射为变换系数集合，然后，对这些变换系数进行量化和编码。对于大多数图像，大量系数都有较小的幅度值，并且可被粗糙地量化(或完全抛弃)而几乎没有多少图像失真。包括第 4章介绍的离散傅里叶变换在内的各种变换都可用于变换图像数据。 图8.21显示了一个典型的块变换编码系统。解码器执行(除了量化功能外)与编码器相反顺序的步骤。编码器执行4种相对简单的操作：子图像分解、变换、量化和编码。一幅大小为MN的输入图像首先被分解为大小为nn的子图像，然后变换这些子图以生成MN/n2MN/n^2MN/n2个子图像变换阵列，每个阵列的大小为nxn。变换处理的目的是对每幅子图像中的像素进行去相关，或用最少数量的变换系数包含尽可能多的信息。然后，在量化阶段，以一种预定义的方式有选择性地消除或更粗略地量化那些携带最少信息的系数)。这些系数对重建的子图像质量的影响最小。通过对量化后的系数进行编码(通常使用变长编码)结束编码过程。任何或所有的变换编码步骤都可以根据局部图像内容进行适应性调整，这称为自适应变换编码，而如果这些步骤对所有子图像都是固定的，则称为非自适应变换编码。 8.2.9 预测编码 这种方法不需要较大计算开销就可实现较好的压缩效果，并且可以是无误差的或有损的压缩。这种方法通常被称为预测编码，它是通过消除紧邻像素在空间和时间上的冗余来实现的，它仅对每个像素中的新信息进行提取和编码。一个像素的新信息定义为该像素的实际值与预测值之间的差。 8.2.10 小波编码 小波编码基于以下概念:对图像的像素解除相关的变换系数进行编码比对原图像像素本身进行编码的效率更高。如果变换的基函数——此时为小波函数——将大多数重要的可视信息包装到少量系数中，则剩下的系数可被粗略地量化或截取为零，而图像几乎没有失真。 图8.45 显示了一个典型的小波编码系统。为了对一幅大小为 2Jx2J2^Jx2^J2Jx2J的图像进行编码，选择一种分析小波ψψψ和最小分解级别J−PJ-PJ−P，并用于计算图像的离散小波变换。如果小波具有互补的尺度函数φφφ则可以使用快速小波变换。 不论哪种情况，计算出来的变换会将原图像的大部分转换为水平的、垂直的和对角分解系数，这些系数具有零均值和类似拉普拉斯分布。 由于许多计算的系数携带很少的视觉信息，这些系数可以最小的系数和编码冗余来量化和编码。此外，量化可以自适应地越过P分解级别而利用任何位置相关。一种或多种无损编码方法，如行程编码、霍夫曼编码、算术编码和比特平面编码等，都可以应用到最后的符号编码步骤中。解码可以用与编码相反的操作来实现–量化过程除外，因为量化过程不可能严格逆向执行。 图 8.45 中基于小波的系统与图 8.21中的变换编码系统之间的主要差别是省略了变换编码器的子图像处理阶段。因为小波变换的计算效率和固有的局部性(即小波的基函数在宽度上是有限的)，对原图像进行细分是没有必要的。 而细分步骤的取消可以消除块效应，这种效应正是以 DCT为基础的近似图像在高压缩比下的特性。