1、图像压缩基本概念图像压缩模型信息论基础无损压缩有损压缩图像压缩标准视频压缩标准图像压缩基本概念概述数据冗余编码冗余像素间冗余心理视觉冗余图像保真度和质量图像压缩的必要性为什么要压缩为什么要压缩?计算机图像处理中的数字图像其灰度多数用计算机图像处理中的数字图像其灰度多数用8bit来量化，一幅最简单的黑来量化，一幅最简单的黑白照片白照片,若按若按512512点阵取样点阵取样,表示这幅图像的二进制数据量表示这幅图像的二进制数据量 5125128=2048Kbit= 2Mbit=256KB而医学图像处理和其他科研应用的图像的灰度量化可用到而医学图像处理和其他科研应用的图像的灰度量化可用到12bit以上
2、，因而以上，因而所需数据量太大。所需数据量太大。10241024 12 =12Mbit=1536KB=1.5MB遥感图像如遥感图像如SAR图像用图像用8bit量化，量化，100公里公里*100公里，公里，10m分辨率的图像的分辨率的图像的大小为大小为1000010000。这样一个地区的图像需。这样一个地区的图像需108B=100MB以上。这无疑以上。这无疑对图象的对图象的存储存储、处理处理、传送传送带来很大的困难。带来很大的困难。动态视频数据量非常大。动态视频数据量非常大。数字高清：数字高清：1080i/50Hz1080i/50Hz19201920* *10801080* *2424* *50
3、=2 488 320 000 =2.5Gb/s50=2 488 320 000 =2.5Gb/s视频信号的传输率约为视频信号的传输率约为2.5GB/s2.5GB/s这样大的数据量不仅超出了计算机的存储和处理能力，更是当前通信信道的传这样大的数据量不仅超出了计算机的存储和处理能力，更是当前通信信道的传输速率所不及的。因此，为了存储、处理和传输这些数据，必须进行压缩。输速率所不及的。因此，为了存储、处理和传输这些数据，必须进行压缩。 传输 存储压缩解压介质压缩解压信道主要目的主要目的图像压缩图像压缩的方法消除冗余数据，从数学角度看，将原始图像转化为从统计角度统计角度看尽可能不相关的数据集一般分为两
4、类：无损压缩无损压缩：在压缩和解压缩过程中没有信息损失有损压缩有损压缩：能取得较高的压缩率，但压缩后不能通过解压缩恢复原状其它：如根据需要，即可进行无损，也可进行有损压缩的技术；准无损技术图像压缩图像压缩的理论基础信息论图像处理的概念和技术压缩方法预测编码方法（对应空域方法）变换编码方法（对应频域方法）图像压缩的可能性8.1 数据冗余的概念数据是用来表示信息的。如果不同的方法为，那么使用较多数据量的方法中，有些数据必然是代表了无用的信息，或者是重复地表示了其它数据已表示的信息，这就是数据冗余的概念。图像压缩的可能性相对数据冗余的定义（续）如果n1和n2代表两个表示相同信息的数据集合中所携载信息
5、单元的数量，则n1表示的数据集合的定义为：R D 1 1C RCR称为，定义为C R n1n 2图像压缩的可能性相对数据冗余和压缩率的一些特例n1相对于n2n1 = n2CR1RD0对应的情况第1种表达相对第2种表达不含冗余数据n1 n2 1 第1种数据集合包含相当多的冗余数据n1 n2 0 第2种数据集合包含相当多的冗余数据图像压缩的可能性三种基本的数据冗余8.1.1编码冗余8.1.2像素间冗余 8.1.3心理视觉冗余如果能减少或消除上述三种冗余的1种或多种冗余，就能取得数据压缩的效果图像压缩什么是编码冗余？如果一个图像的，使用了多于实际需要的编码符号，就称该图像包含了编码冗余黑白二值图像编
6、码如果用8位表示该图像的像素，我们就说该图像存在编码冗余，因为该图像的像素只有两个灰度，用一位即可表示。nk,8.1.1 编码冗余图像直方图的定义pr rk k 0,1 2,.,L 1nnk是第k个灰度级在图像中出现的次数，n是图像中的像素总数，L是灰度级数。 如果用于表示每个rk值的比特数为l(rk)，则表达为：Lavg L 1 l rk p r rk k 0表示不同的灰度级值的平均码字长度.对MN的图像进行编码所需的比特数为MNL avg参考page 328的例8.18.1.2 像素间冗余什么是像素间冗余？反映图像中像素之间的相互关系因为任何给定像素的值可以根据与这个像素相邻的像素进行预测
7、，所以单个像素携带的信息相对较少对于一幅图像，很多单个像素对视觉的贡献是冗余的。它的值可以例：原图像数据：234 223 231 238 235压缩后数据：234 -1187-3 像素间冗余像素间冗余有直方图特征可知，可以用有直方图特征可知，可以用变长编码减少编码冗余。但变长编码减少编码冗余。但编码处理不会改变图像像素编码处理不会改变图像像素之间的相关性级别。也就是之间的相关性级别。也就是说用于表示每幅图像的灰度说用于表示每幅图像的灰度级的编码与像素之间的相关级的编码与像素之间的相关性无关，这些性无关，这些相关相关来自于图来自于图像中对象之间的像中对象之间的结构结构或或几何几何关系关系。相关性
8、反映了图像中像素间相关性反映了图像中像素间的直接关系。的直接关系。a)、b)两幅图像c)、d)灰度直方图e)、f)沿着某一条线计算的自相关函数()(0)nAnA101,NnnyAfx y fx ynNn :),(),(算公式算公式的归一化相关系数的计的归一化相关系数的计和和图像图像yxhyxf 10210102101010),(),(),(),(NyMxNyMxNyMxyxhyxfyxhyxfr8.1.3 心理视觉冗余什么是心理视觉冗余？人眼感觉到的图像区域亮度不仅取决于该区域的反射光，例如根据马赫带效应，在灰度值为常数的区域也能感觉到灰度值的变化这是由于所有。在正常视觉处理过程中各种信息的相
9、对重要程度不同有些信息在通常的视觉过程中与另外一些信息相比并，这些，去除这些信息并不会明显降低图像质量心理视觉冗余什么是心理视觉冗余？（续） 由于消除心理视觉冗余数据会导致一定量信息的丢失，所以这一过程通常称为心理视觉冗余压缩是不可恢复的，它表示从一个范围很宽的输入集合到一个有限个输出值的集合的映射，所以结果导致了数据的33K15K心理视觉冗余心理视觉冗余a)256灰度级原图像b)量化为16级后图像c)利用人类视觉特性进行量化后图像原来原来8bit/像素像素压缩后压缩后4bit/像素像素压缩率为压缩率为2：1存在假轮廓效应存在假轮廓效应改进的灰度级（改进的灰度级（IGS）量化方法）量化方法IG
10、S量化过程：先由当前的量化过程：先由当前的8位灰度级值位灰度级值(Gray Level)与前一个与前一个 sum（初始值为零）的低（初始值为零）的低4位相加。如果当前值的高位相加。如果当前值的高4位是位是11112，则用，则用00002与其相加，保持其不变。将得到的和的高与其相加，保持其不变。将得到的和的高4位的值作位的值作为编码像素值。为编码像素值。IGS利用眼睛对边缘固有的敏感性，通过一个伪随机数加到每利用眼睛对边缘固有的敏感性，通过一个伪随机数加到每个像素上将这些边缘拆散。这个伪随机数是在对结果进行量化个像素上将这些边缘拆散。这个伪随机数是在对结果进行量化之前，根据表示相邻像素灰度级的原
11、编码的低位生成的。由于之前，根据表示相邻像素灰度级的原编码的低位生成的。由于低位完全是随机的，所以这样做等于增加了通常与伪轮廓相关低位完全是随机的，所以这样做等于增加了通常与伪轮廓相关的人工边缘随机性的灰度级。的人工边缘随机性的灰度级。8.1.4 保真度准则保真度准则图像压缩可能会导致信息损失，如去除心理视觉冗余数据需要以描述解码图像相对于原始图像的偏离程度，这些测度称为常用保真度准则分为两大类：客观保真度准则主观保真度准则保真度准则客观保真度准则当所损失的信息量可以用编码输入图像与编码输出图像的函数表示时，它就是基于客观保真度准则的常用的两种客观保真度准则均方根误差均方信噪比客观保真度准则输
12、入图和输出图之间的均方根误差 令 f x, y 代表输入图，f x, y 代表对 f x, y 先压缩后解压缩后得到的 f x, y 的近似，则 f x, y 和f x, y 之间的误差定义为ex, y f x, y f x, y 如两幅图像尺寸均为MN，则它们的总误差为M 1 N 1 f x, y f x, y x 0 y 0输入图和输出图之间的均方根误差这样 f x, y和 f x, y 之间的为 2110102),(),(1 MxNyrmsyxfyxfMNe输出图的均方信噪比 如果将 f x, y 看作原始图 f x, y 和噪声信号 ex, y的和，那么输出图的 SNR ms为 101
13、0210102),(),(),(MxNyMxNymsyxfyxfyxfSNR SNR rms为 1010210102),(),(),(MxNyMxNyrmsyxfyxfyxfSNR46评分1235评价优秀良好可用刚可看差不能用说明图像质量非常好，如同人想象出的最好质量图像质量高，观看舒服，有干扰但不影响观看图像质量可接受，有干扰但不太影响观看图像质量差，干扰有些妨碍观看，希望改进图像质量很差，妨碍观看的干扰始终存在，几乎无法观看图像质量极差，不能使用8.2 图像压缩模型f x, y信源编码信道编码信道信道解码信源解码f x, y编码器解码器一个图像压缩系统包括两个不同的一个图像压缩系统包括两个
14、不同的模块：模块：和和一般来讲如果输出图像是输入的准一般来讲如果输出图像是输入的准确复制，系统就是确复制，系统就是无误差无误差的或具有的或具有信息保持编码的系统信息保持编码的系统。编码器由一个消除输入冗余的编码器由一个消除输入冗余的信源编码器信源编码器和一个用于增强信和一个用于增强信源编码器输出的抗噪能力的源编码器输出的抗噪能力的信道编码器信道编码器构成。构成。如果编码器和解码器之间的信道是无噪的，则信道编解码器如果编码器和解码器之间的信道是无噪的，则信道编解码器可以省去。可以省去。图像压缩模型信源编码器f x, y转换器量化器符号编码器信道信源编码器信源编码器：减少或消除输入图像中的编码冗余
15、、像素间冗余及心理视觉冗余转换器：减少像素间冗余量化器：减少心理视觉冗余，符号编码器：减少编码冗余并不是每个图像压缩系统都必须包含这3种操作，如进行无误差压缩时，必须去掉量化器图像压缩模型信源解码器信道符号解码器反向转换器f x, y信源解码器符号解码器：进行符号编码的逆操作反向转换器：进行转换器的逆操作为什么没有反向量化器？图像压缩模型8.2.2信道编码器和信道解码器在有噪声的或易产生误差时，信道编码器和信道解码器对整个编解码过程非常重要信道编码器和解码器通过向信源编码数据中来减少信道噪声的影响。由于信源编码器几乎不包含冗余，所以如果没有附加这种预制的冗余，它对噪声传送会有很高的敏感性。因此
16、，信道编码是，尽量使处理过的信号在传输过程中不出错或少出错，即使出错也要有能力尽量纠正错误。 信道编码技术：比如汉明(Hamming)编码。在编了码的码字后面增加足够的比特位以保证各个正确的码字之间至少有一定数量的比特位不相同图像压缩模型8.3 信息论基础显示一幅图像需要多大的数据量？有没有描述一幅图像且没有信息丢失的最小数据量？信息测量对一个随机事件E，如果它的出现概率是P(E),那么它包含的信息：I E log1PE log PE I(E)称为E的。如果P(E)=1(即事件总发生)，那么I(E)=0图像压缩模型8.3.2 信息信道信 源信 道信 宿信道是连接信源和用户的物理媒介。它可以是电
17、话线、无线传播、导线或internetJT信息论基础信源A=a1,a2,aJ称为信源产生符号aj的事件概率是P(aj),且一个J1向量 P a j 1j 1z P a1 , P a2 ,.,P aJ 用于表示所有信源符号的概率集合有限总体集合(A,z)完全描述了信源信源信息理论基础信息理论基础直观地理解自信息量的概念直观地理解自信息量的概念: 一个概率小的符号出现将带来更大的信息量一个概率小的符号出现将带来更大的信息量.每个符号的平均自信息量每个符号的平均自信息量单位单位: 比特比特/符号符号一般来讲，事件一般来讲，事件E的自信息量与的自信息量与E的概率的关系是反向的。如果的概率的关系是反向的
18、。如果P(E)=1，则则I(E)=0。因为：。因为：(a)越不可能出现的字符，它的出现对于消息的信息量的贡献越大。越不可能出现的字符，它的出现对于消息的信息量的贡献越大。(b)整个消息的信息量是构成它的那些字符中对于信息量有贡献的那部整个消息的信息量是构成它的那些字符中对于信息量有贡献的那部分之和。分之和。 jJjjaPaPzHlog1()logjjI aP a JJ信息论基础信源（续）如果产生k个信源符号，则大数定律保证对于一个充分大的k，符号aj将平均被输出k P(aj)次。因此，输出得到的平均自信息是 k P aj logP aj j 1每个信源输出的平均信息每个信源输出的平均信息，也称
19、为为H z P a j log P a j j 1如果信源符号的出现是等可能性的，则上述熵被最如果信源符号的出现是等可能性的，则上述熵被最大化，此时信源提供最大信息量大化，此时信源提供最大信息量Jk信息论基础信道输出B=b1,b2,bk称为提交给用户的字符bk的概率是P(bk)有限集合完整描述了输出和用户收到的信息，v Pb1 , Pb2 ,.,PbK 给定信道输出概率P(bK)和信源符号概率 P(aJ),它们由下式相联系P bk P bj 1| a j P a j 信息论基础信道输出（续）将上式中的条件概率放入一个KJ的正向信道传递矩阵Q，其元素qkj= P(bk|aj)为条件概率则输出符号
20、集的概率分布由下式计算v Qz )|()|()|()|()|()|()|()|(2121212111JkkkJJJkabpabpabpabpabpabpabpabpQJkJKjJKjJKj信息论基础条件熵函数H(z|bk)H z | bk P a j | bk log P a j | bk j 1条件概率H(z|v)H z | v K H z | bk 1P bk P aj 1 k 1 P aj 1 k 1| bk log P a j | bk P bk | bk P bk log P a j | bk P a j , bk log P aj 1 k 1| bkK信息论基础因为两个事件C和D的
21、联合概率是PC, D PC| DPD PD| CPCP(aj)的变换（下面推导互信息使用）Paj Paj ,b1 Paj ,b2 . Paj ,bK Paj ,bK k1定义信道传输元素qkj P bk | a j J J K JKJKPa j | bk JKPa j Pa j | bk Pbk JKPa j Pbk JKjkjk , j 1 k 1 j k信息论基础z和v的互信息定义为I z, v H z H z | v Pa j log Pa j Pa j , bk log Pa j | bk j 1 j 1 k 1 Pa j , bk log Pa j | bk Pa j , bk lo
22、g Pa j j 1 k 1 j 1 k 1 Pa j , bk logj 1 k 1 Pa j , bk logj 1 k 1 Pa , b log PPaaPbb P a , b JKjkP a P b P b | a P a JKkjjP a P b JKki信息论基础z和v的互信息的另外一种表达I z , v P a j , bk logj 1 k 1 j k P bk | a j P a j logj 1 k 1 j k P a j qj 1 k 1kjlogq kjP bk J Kj 1 k 1P a j q kj logJ P bi 1q kjk | a i P a i J Kj
23、 1 k 1P a j q kj logq kjJ P a i qi 1信息论基础互信息总结互信息I(z,v)是信源符号概率向量z和信道矩阵Q的函数当输入和输出符号统计独立时，I(z,v)取得最小值0 I(z,v)对所有信源分布u的最大值就是信道容量 C maxI u, v u信道容量定义了能够通过信道可靠地传送信息的最大传送率信息论基础基本编码定理无噪声编码定理噪声编码定理（自学）信源编码定理（自学）无噪声编码定理无噪声编码定理平均码字长度平均码字长度 1avgLH zH znn( )avgH znL/avgLn1() ()nJavgiiiLP a l a11log()log1()()iii
24、l aP aP a信源输出信源输出ai是用一个码字表示的，码字的长度为不小于其自信息量的最小整数是用一个码字表示的，码字的长度为不小于其自信息量的最小整数图像压缩编码的分类图像压缩编码的分类 图像压缩编码图像压缩编码有损压缩有损压缩无损压缩无损压缩哈夫曼编码哈夫曼编码算术编码算术编码LZW编码编码位平面编码位平面编码行程编码行程编码无损预测编码无损预测编码有损预测编码有损预测编码变换编码变换编码K.L变换变换Haar变换变换Walsh.Hadamard变换变换离散余弦变换离散余弦变换离散傅立叶变换离散傅立叶变换斜变换斜变换小波变换小波变换消除编码冗余消除编码冗余消除象素间冗余消除象素间冗余信息
25、论基础8.4 无损压缩变长编码霍夫曼(Huffman)编码其它变长编码算术编码LZW编码位平面编码无损预测编码无误差压缩无误差压缩的必要性在医疗或商业文件的归档，有损压缩因为法律原因而被禁止卫星成像的收集，考虑数据使用和所花费用，不希望有任何数据损失X光拍片，信息的丢失会导致诊断的正确性无损压缩的压缩率一般为无损压缩的压缩率一般为2-10无误差压缩技术减少像素间冗余减少像素间冗余: : 建立一种可替代的图像表达方式建立一种可替代的图像表达方式减少编码冗余减少编码冗余: : 对这种表达方式进行编码对这种表达方式进行编码8.4.1 变长编码变长编码无误差图像压缩的最简单方法就是无误差图像压缩的最简
26、单方法就是减少仅有的减少仅有的编码冗余编码冗余。编码冗余通常存在。编码冗余通常存在于表示图像灰度级的自然二进制编码过程于表示图像灰度级的自然二进制编码过程中。它可以对灰度级进行编码，使中。它可以对灰度级进行编码，使来消除编来消除编码冗余。这样做需要码冗余。这样做需要变长编码变长编码结构，结构， 10LkkrkavgrprlL1.2.无误差压缩变长编码减少编码冗余变长编码，即把最短的码字赋予出现概率最大的灰度级霍夫曼编码将需要考虑的符号概率排序，并将最低概率的符号联结为一个单一符号对每个化简后的信源进行编码，从最小的信源开始，一直编码到原始的信源霍夫曼编码霍夫曼编码（一）（一）霍夫曼编码信源化简
27、步骤：霍夫曼编码信源化简步骤：设信源设信源 有有 个符号个符号(消息消息)，1.把信源中的消息按概率从大到小顺序排列，把信源中的消息按概率从大到小顺序排列，2.把最后两个出现概率最小的消息合并成一个消息把最后两个出现概率最小的消息合并成一个消息,从而从而 使信源的消息数减少，并同时再按信源符号（消息）使信源的消息数减少，并同时再按信源符号（消息）出现的概率从大到小排列；出现的概率从大到小排列；3.重复上述重复上述2步骤步骤,直到信源最后为直到信源最后为 为止；为止；4.将被合并的消息分别赋予将被合并的消息分别赋予1和和0，并对最后的两个消息也，并对最后的两个消息也相应的赋予相应的赋予1和和0；
28、通过上述步骤就可构成最优变长码通过上述步骤就可构成最优变长码(Huffman Codes)。XmmmpxppxxX2121oooooppxxX2121霍夫曼编码霍夫曼编码霍夫曼编码信源化霍夫曼编码信源化简简霍夫曼编码霍夫曼编码（二）霍夫曼化简后的信源编码（二）霍夫曼化简后的信源编码编码的平均长度：编码的平均长度：(0.4)(1)(0.3)(2)(0.1) 3(0.1)(4)(0.06)(5)(0.04)(5)2.2/avgLbit（ ）符号其 信 源 熵 为其 信 源 熵 为2.14bit/符号。符号。编码的效率：编码的效率：973. 02 . 214. 2 霍夫曼编码霍夫曼解码解码通过的方式
29、完成例：编码串010100111100 a3 a1 a2a2a6对编码串对编码串010100111100解码，其解码唯一：解码，其解码唯一：a3a1a2a2a6霍夫曼编码其它接近最佳的变长编码：为什么需要？当对大量符号进行编码，构造霍夫曼编码比较复杂对J个信源符号，需要进行J-2次信源化简和J-2次编码分配对256个灰度级图像，需要256-2=254次信源化简和254次编码分配考虑牺牲编码效率以减少编码构造的复杂性几种变长编码几种变长编码截取霍夫曼编码霍夫曼编码二进制编码B2编码二值移位编码霍夫曼移位编码算术编码算术编码算术编码生成的是非块码，在信源符号和码字之算术编码生成的是非块码，在信源符
30、号和码字之间不存在一一对应的关系。算术编码是给整个符间不存在一一对应的关系。算术编码是给整个符号序列分配一个单一的算术码字，这个码字本身号序列分配一个单一的算术码字，这个码字本身定义了一个介于定义了一个介于0和和1之间的实数间隔。当消息中之间的实数间隔。当消息中的符号数目增加时，用于描述消息的间隔变的更的符号数目增加时，用于描述消息的间隔变的更小，而表示间隔所需要的信息单元的数目就变得小，而表示间隔所需要的信息单元的数目就变得更多了。更多了。消息的每个符号根据符号出现的概率减小间隔的消息的每个符号根据符号出现的概率减小间隔的大小，这种技术不象霍夫曼方法那样要求每次对大小，这种技术不象霍夫曼方法
31、那样要求每次对一个符号进行编码，所以理论上达到了无噪声编一个符号进行编码，所以理论上达到了无噪声编码准则确定的界限。码准则确定的界限。算术编码算术编码0.080.20.040.04=0+(0.2-0)/510.08=0+(0.2-0)/520.056=0.04+(0.08-0.04)/520.072=0.04+(0.08-0.04)/54=0.04+0.032一个五个符号的序列一个五个符号的序列a1,a2,a3,a3,a4来来自一个四符号信源。自一个四符号信源。经过算术编码后，区间被确定为经过算术编码后，区间被确定为0.06752,0.0688),这个区间的任这个区间的任何数字都可以用来表示这
32、个消息何数字都可以用来表示这个消息（比如（比如0.068)。8.4.2 LZW编码编码LZW编码：消除像素间冗余像素间冗余的无误差编码方法是由Lemple和Ziv最早提出，然后由Welch充实的有专利保护的LZW算法. Lempel-Ziv-Welch(LZW)编码编码对信源符号的对信源符号的分配固定长度码字，不需要分配固定长度码字，不需要了解有关被编码符号的出现概率的知识。了解有关被编码符号的出现概率的知识。LZWLZW编码的原理：编码的原理：在编码处理的开始阶段，先构造一个对信源符号进在编码处理的开始阶段，先构造一个对信源符号进行编码的编码本（行编码的编码本（字典字典）。对于）。对于8 8
33、位单色图像，位单色图像，字典中前字典中前256256个字被分配给灰度值个字被分配给灰度值0-2550-255。当编码。当编码器顺序地分析图像像素的时候，字典中没有包括器顺序地分析图像像素的时候，字典中没有包括的灰度级序列由算法决定其出现的位置。的灰度级序列由算法决定其出现的位置。使用使用LZW的文件格式包括的文件格式包括GIF，TIFF和和PDF等等。字典位置index条目0125525651101255 以以8 8位（位（256256个灰度级）图像为例个灰度级）图像为例. . 1.1.准备一个数据字典准备一个数据字典( (可以看做一个数组可以看做一个数组). ). 数组的前数组的前25625
34、6项初始化为项初始化为0,1,2,.,255,0,1,2,.,255,后面的项为空白后面的项为空白. .为方便起见为方便起见, ,我们我们管字典中的每一项叫管字典中的每一项叫“条目条目”. . 2.2.开始对图像文件编码开始对图像文件编码, ,图像文件从左向右、从上到下扫描图像文件从左向右、从上到下扫描, ,把扫描得到的灰把扫描得到的灰度级数据与字典中的条目进行比较度级数据与字典中的条目进行比较. . 如果相同如果相同, ,就把这个就把这个 条目条目 的的index(index(在在数组中的位置数组中的位置) )作为码字输出作为码字输出. . 如果在字典中找不到与之匹配的条目如果在字典中找不到
35、与之匹配的条目, ,则在字典中创建一个新的条目则在字典中创建一个新的条目( (从第从第256256项开始项开始). ). 一个一个512字节的字典字节的字典一个一个44、8位图像位图像3546353946784639679078126353334126 示例示例 原始码流原始码流 35 46 67 35 46 78 90 33 35 46 78 34 开始编码开始编码: 因为第一个数字是因为第一个数字是35,我们必然可以从字典中找到与之匹配的条目我们必然可以从字典中找到与之匹配的条目(也就是第也就是第35个个), 但我们不急着用第但我们不急着用第35个条目与之匹配个条目与之匹配,先看看第二个数
36、字是先看看第二个数字是46, 希望在字典中希望在字典中 能找到一个更长的模式能找到一个更长的模式“35 46”这样的条目这样的条目,与之匹配与之匹配, 但不幸的是我们没有找到但不幸的是我们没有找到, 所以只对第一个数字所以只对第一个数字35编码编码, 结果输出结果输出35; 同时把同时把“35 46”加入字典的第加入字典的第256项项, 希望以后能碰到它希望以后能碰到它. 同理同理,对对46编码编码, 输出输出46, 同时把同时把“46 67”加入字典的第加入字典的第257项项. 同理同理,对对67编码编码, 输出输出67, 同时把同时把“67 35”加入字典的第加入字典的第258项项. 这时
37、注意了这时注意了: 对对35编码编码, 是不是现在还输出是不是现在还输出35呢呢? 当然不是当然不是,我们发现我们发现35后面跟着后面跟着 46, 扫描字典扫描字典,可以发现第可以发现第256个模式与之匹配个模式与之匹配, 输出输出256. 同时同时,将模式将模式“35 46 78“加入到加入到 字典的第字典的第259项项. 同理同理,接下来输出接下来输出 78, 90, 33, 259, 34. 所以输出的码流为所以输出的码流为35 46 67 256 78 90 33 259 34. 对上面的过程归纳一下对上面的过程归纳一下: : 在编码的过程中生成字典在编码的过程中生成字典; ;一边从字
38、典中选择长一边从字典中选择长度尽量长的度尽量长的 模式模式 与原始码流匹配与原始码流匹配. .LZW编码例子编码例子Appear39-39126-12639-3939-39-126126-3939-1268.4.3位平面编码位平面编码：消除像素间冗余消除像素间冗余将一幅图像分解为一系列二值图像并通过二值图像压缩方法对每幅二值图像进行压缩位平面编码过程可以分成两步：位平面编码过程可以分成两步：一是位平面分解一是位平面分解二是二值图像压缩二是二值图像压缩二值图像位平面灰度编码位平面位平面分解的两种方法 位平面分解位平面分解二值图像位平面二值图像位平面一幅一幅m比特的灰度图像具有的灰度级表示如下比特
39、的灰度图像具有的灰度级表示如下am 1 2 m 1 am 2 2 m 2 . a1 21 a0 2 0零级位平面是通过收集每个像素的零级位平面是通过收集每个像素的a0位生位生成，第成，第(m-1)级位平面包含级位平面包含am-1位位缺点：图像在灰度级上稍有变化就会对位平缺点：图像在灰度级上稍有变化就会对位平面的复杂性产生显著影响，如亮度面的复杂性产生显著影响，如亮度127(01111111)和亮度和亮度128(10000000)的转换的转换 位平面分解位平面分解灰度编码位平面灰度编码位平面图像的灰度编码根据下列方法得到：图像的灰度编码根据下列方法得到：g m 1 am 1g i ai ai 1
40、0 i m - 2避免二值图像位平面的问题，避免二值图像位平面的问题，连续码字只在连续码字只在1位位置上不同位位置上不同,如亮度如亮度127 (01000000)和亮度和亮度128(11000000)的转换的转换位平面分界例8比特单色图像二值图像位平面分解例二值图像位平面灰度编码位平面 采用不同分层编码方采用不同分层编码方法处理的图像。法处理的图像。 左侧是第一种方法分左侧是第一种方法分层编码的高层编码的高4位位图位位图 右侧是第二种方法编右侧是第二种方法编码的高码的高4位位图位位图 高阶平面比低阶部分高阶平面比低阶部分要简单，高比特位平要简单，高比特位平面包含大块的均匀区面包含大块的均匀区域
41、，图像细节较少。域，图像细节较少。灰度编码位平面比二灰度编码位平面比二值位平面复杂性较少值位平面复杂性较少位平面分解例二值图像位平面灰度编码位平面 常数值区域编码常数值区域编码CAC 一维行程编码一维行程编码 二维行程编码二维行程编码常数块编码常数块编码用专门的码字表达全是用专门的码字表达全是0或或1的连通区域的连通区域将图像分成全黑，全白或混合的pq尺寸的块。出现频率最高的类赋予1位码字0，其它2类分别赋予2位码字10和11压缩二值图或位平面的一种简单有效的方法是使用指定的码压缩二值图或位平面的一种简单有效的方法是使用指定的码字识别大片连续的字识别大片连续的1 1或或0 0区域。这样的方法称
42、为区域。这样的方法称为区域编码区域编码(CAC)(CAC)常数块编码（续）常数块编码（续）当需压缩的图像主要由白色部分组成时（如文档），可将白色区域编为0，其它块用1接上该块的位模式编码WBS编码编码另一种办法：将二值图或位平面迭代地分解成尺寸越来越小的子块。如果子块不是全白，继续分解，直至某个事先确定的子块尺寸。如果最后子块全白，就编为0，反之编为1加上该块的位模式由于原来需用pq比特表示的常数块现在只用1位或2位表示，这样就达到了压缩的目的赋予混合块的码只是作为前缀，后面还需跟上该块的用pq位表示的模式WBS编码编码(White Block Skipping)：大多数二值图像中的黑大多数二
43、值图像中的黑象素只占图像象数总数很少的一部分。因此若能跳过白色象素只占图像象数总数很少的一部分。因此若能跳过白色区域，对黑色像素编码这样表示这些图像的比特数将减区域，对黑色像素编码这样表示这些图像的比特数将减少，每个像素平均比特数也就可以减少少，每个像素平均比特数也就可以减少 1)一维一维WBS编码编码 将图像的每条扫描线分成若干段，每段有将图像的每条扫描线分成若干段，每段有N个像素。对个像素。对全 部 是 白 色 的 像 素 用全 部 是 白 色 的 像 素 用 l b i t “ 0 ” 表 示 。表 示 。对于至少有一个黑色像素的像素段采用对于至少有一个黑色像素的像素段采用N十十1个比特
44、编个比特编码即第一个比特人为地规定为码即第一个比特人为地规定为1其余的其余的N比特采用直接比特采用直接编码编码(白色为白色为“0”黑色为黑色为“1”码字码字)。跳过白色块编码跳过白色块编码 一维一维WBS编码平均码字长度为编码平均码字长度为 PN:段长为段长为N的的。b41.25-P4。全白概率全白概率必须大于必须大于14才可能获得压缩效果。才可能获得压缩效果。 段长段长N不同，全白概率也不同不同，全白概率也不同。为了获得最小的平均码。为了获得最小的平均码字长度，对字长度，对给定的一幅二值图像应有一个最佳给定的一幅二值图像应有一个最佳N值，不同值，不同图像的最佳段长图像的最佳段长N值不同。值不
45、同。分成五段：段长N4 00000010000001000000编码01001001010002)二维二维WBS编码编码 一维一维WBS编码可以方便地推广到二维。编码可以方便地推广到二维。 一维的像素段一维的像素段 二维中像素块二维中像素块 假设像素块尺寸为假设像素块尺寸为MN，全部为白色的像素块用，全部为白色的像素块用“0”表示，非全白像素块用表示，非全白像素块用(MN+1)个个比特码表示。其中第一个比特为比特码表示。其中第一个比特为“1”。其余。其余MN个比特采用直接编码。个比特采用直接编码。00000000100001010000000001001 0001010 1000最终获得的编码
46、：最终获得的编码：0100100010101000 位平面编码位平面编码一维行程编码一维行程编码在一个逐行存储的图象中，在一个逐行存储的图象中，具有相同灰度值的一些象素组具有相同灰度值的一些象素组成的序列称为成的序列称为。在编码时，对于每个行程只存储一。在编码时，对于每个行程只存储一个灰度值的码，再紧跟着存储这个行程的长度。这种按照行个灰度值的码，再紧跟着存储这个行程的长度。这种按照行程进行的编码被称为程进行的编码被称为（Run Length EncodingRun Length Encoding）。）。 是传真编码的标准压缩方法是传真编码的标准压缩方法对从左到右扫描一行时所遇到的对从左到右扫
47、描一行时所遇到的1 1或或0 0的连接组，使用的连接组，使用这些连接组的长度进行编码这些连接组的长度进行编码决定行程长度值的常用方法：决定行程长度值的常用方法：指定每一行第一次行程的值指定每一行第一次行程的值假设每一行从白色行程开始，这次行程的长度可假设每一行从白色行程开始，这次行程的长度可能为能为0 0一维行程编码一维行程编码见见p332图图8.3尽管行程长度编码本尽管行程长度编码本身是一种压缩图像的身是一种压缩图像的有效方法，但其它的有效方法，但其它的压缩方法通常可以通压缩方法通常可以通过对行程长度本身进过对行程长度本身进行变长编码实现。这行变长编码实现。这些变长编码是根据他些变长编码是根
48、据他们自身的统计数据特们自身的统计数据特殊制定的。殊制定的。 分析：分析： 对于有大面积色块的图像，压缩效果很好对于有大面积色块的图像，压缩效果很好 对于纷杂的图像，压缩效果不好，最坏情况下，会加倍图像对于纷杂的图像，压缩效果不好，最坏情况下，会加倍图像行程编码行程编码8.4.4无损预测编码预测编码的基本思想通过仅提取每个像素中的新信息并来消除像素间的冗余消除像素间的冗余一个像素的：该像素的当前值与预测值的差正是由于像素间有相关性，所以才使预测成为可能nnff 大多数情况下， 是通过m个以前像素的线性组合来生成的nf无损预测编码无损预测编解码系统无损预测编码当输入图像的像素序列fn逐个进入编码器，预测器根据过去的输入产生当前输入像素的估计值。预测器的输出舍入成最近的整数 f n 并被用来计算预测误差e n f n f n该误差用符号编码器借助变长码进行编码该误差用符号编码器借助变长码进行编码以产生压缩数据流的下一个元素。然后解码器根据接收到的变长码字重建en，并执行下列操作f n e n f n
