数字图像处理(冈萨雷斯)8 无损压缩ppt课件.ppt

第8章图像压缩,8.1基本概念8.2图像压缩模型8.3信息论基础8.4无损压缩8.5有损压缩8.6图像压缩标准8.7视频压缩标准,图像压缩编码的分类,哈夫曼编码算术编码LZW编码位平面编码行程编码无损预测编码,有损预测编码,K.L变换Haar变换Walsh.Hadamard变换离散余弦变换离散傅立叶变换斜变换小波变换,8.4 无损压缩,无误差压缩（无损压缩）的必要性,在医疗或商业文件的归档，有损压缩因为法律原因而被禁止；卫星成像的收集，考虑数据使用和所花费用，不希望有任何数据损失；X光拍片，信息的丢失会导致诊断的正确性；,无损压缩的压缩率一般为210,减少像素间冗余:建立一种可替代的图像表达方式减少编码冗余:对这种表达方式进行编码,无误差压缩技术,8.4.1 变长编码,无误差图像压缩的最简单方法就是减少仅有的编码冗余。编码冗余通常存在于表示图像灰度级的自然二进制编码过程中。它可以对灰度级进行编码，使表示一个像素的码字的平均比特数最小来消除编码冗余。这样做需要变长编码结构，通常将最短的码字赋予出现概率最大的灰度级。,8.4 无损压缩,霍夫曼编码,将需要考虑的符号概率排序，并将最低概率的符号联结为一个单一符号对每个化简后的信源进行编码，从最小的信源开始，一直编码到原始的信源,8.4.1 变长编码,（一）霍夫曼编码信源化简步骤：,设信源 有 个符号(消息)，,1.把信源中的消息按概率从大到小顺序排列;2.把最后两个出现概率最小的消息合并成一个消息,并同时再按信源符号（消息）出现的概率从大到小排列；3.重复上述2步骤,直到信源最后为 为止；4.将被合并的消息分别赋予1和0，并对最后的两个消息也相应的赋予1和0；通过上述步骤就可构成最优变长码(Huffman Codes)。,（一）霍夫曼编码信源化简,8.4.1 变长编码,（二）霍夫曼化简后的信源编码,其信源熵为:,编码的平均长度：,编码的效率：,8.4.1 变长编码,8.4.1 变长编码,（三）霍夫曼解码,解码通过查询表的方式完成。,例：编码串 01010 011 1 1 00,对编码串010100111100解码，其解码唯一：a3a1a2a2a6,huffman码的优点：,是一种最优变长编码（平均码长最短；最接近于熵）；一种快码，因为各个信源符号都被解成一组固定次序的码符号；一种即时码，因为1串码符号中的每个码字都可以不考虑其后的符号而解出；是一种可唯一解开的码；,8.4.1 变长编码,其它接近最佳的变长编码：为什么需要？,当对大量符号进行编码，构造霍夫曼编码比较复杂对J个信源符号，需要进行J-2次信源化简和J-2次编码分配对256个灰度级图像，需要256-2=254次信源化简和254次编码分配考虑牺牲编码效率以减少编码构造的复杂性,表8.5给出了几种简化的编码方法：截断霍夫曼编码，B编码、二元平移及霍夫曼移位。,几种变长编码,截取霍夫曼编码,霍夫曼编码,二进制编码,B2编码,二值移位编码,霍夫曼移位编码,8.4.1 变长编码,8.4.1 变长编码,截断huffman编码,一种简单改进，它只对具有最大概率的 个符号进行霍夫曼编码，而对其它所有码用：前缀码+定长码（二进制编码）来表示。把M个符号之后的所有符号合成一个特殊符号，其概率为各符号概率之和 把该特殊符号对应的霍夫曼码作为前缀码；,例如：，则符号 的概率之和 再查0.2概率对应的霍夫曼码（10）作为前缀码,8.4.1 变长编码,B编码,当信源符号的概率服从如下的幕规律时，B码逼近最优。,每个码字由两部分组成：延续比特+信息比特（二进制数）,延续比特：,用字母C表示；随每个码字变化交替取“0”或“1”；它的变化表示一个新的码字的开始；,信息比特：,表示不同的信息符号；B2码代表每一延续比特位后有2个信息位；,例如：的B2编码为：,或者,注：有下划线的为延续比特；,8.4.1 变长编码,B编码,B码是单义码，但是是续长码，译码时要向前看一位延续比特；B码也是给出现概率最大的消息分配最短的码字，然后依次排列下来；B码的编、译码简单，对误码的抗干扰能力也较强；,8.4.1 变长编码,移位编码,移位编码步骤：排列信源符号，使概率单调递减；将符号总数分成大小相同的符号块，一般第一个块叫基准块；对所有块中的各元素采用同样方法编码；除基准块外，对每个块加上移、下移符号加以区别。,二进制移位码又叫Sn码。,优点：移位码对于具有单调递减概率的消息非常有效；,8.4.1 变长编码,平移编码示例：,例如：表8.5中的二进制平移码的获得：,21个信源符号依出现的概率进行单调递减排序；分成3块，每块7个符号；基准块的7个单独符号用自然二进制编码需3位，所以用S3编码；,表8.5中的霍夫曼平移码可以类似获得。,只是基准块的7个单独符号 用huffman编码；所有概率相加，得0.39，移位符号是具有最大概率(0.39)的符号，且被分配一个最短的霍夫曼码字00表示。,8.4.1 变长编码,算术编码,算术编码生成的是非块码；在信源符号和码字之间不存在一一对应的关系；算术编码是给整个符号序列分配一个单一的算术码字，这个码字本身定义了一个介于0和1之间的实数间隔；当消息中的符号数目增加时，用于描述消息的间隔变的更小，而表示间隔所需要的信息单元的数目就变得更多了。,消息的每个符号根据符号出现的概率减小间隔的大小，这种技术不象霍夫曼方法那样要求每次对一个符号进行编码，所以理论上达到了无噪声编码准则确定的界限。,8.4.1 变长编码,算术编码,8.4.1 变长编码,算术编码,一个五个符号的序列a1,a2,a3,a3,a4来自一个四符号信源。经过算术编码后，区间被确定为0.06752,0.0688),这个区间的任何数字（比如0.068)都可以用来表示这个消息。,编码的效率：,8.4.2 LZW编码,在编码处理的开始阶段，先构造一个对信源符号进行编码的编码本（字典）。对于8位单色图像，字典中前256个字被分配给灰度值0255。当编码器顺序地分析图像像素的时候，字典中没有包括的灰度级序列由算法决定其出现的位置。,8.4 无损压缩,LZW编码：消除像素间冗余的无误差编码方法,LZW编码的原理：,对信源符号的可变长度序列分配固定长度码字，不需要了解有关被编码符号的出现概率的知识。,是由Lemple和Ziv最早提出，然后由Welch充实的有专利保护的LZW算法.Lempel-Ziv-Welch(LZW)编码,使用LZW的文件格式包括GIF，TIFF和PDF等。,LZW编码基本思想是这样的:以8位（256个灰度级）图像为例.1.准备一个数据字典(可以看做一个数组).数组的前256项初始化为0,1,2,.,255,后面的项为空白.为方便起见,我们管字典中的每一项叫“条目”.2.开始对图像文件编码,图像文件从左向右、从上到下扫描,把扫描得到的灰度级数据与字典中的条目进行比较.如果相同,就把这个条目的index(在数组中的位置)作为码字输出.如果在字典中找不到与之匹配的条目,则在字典中创建一个新的条目(从第256项开始).,一个512字的字典,一个44、8位图像,示例 原始码流 35 46 67 35 46 78 90 33 35 46 78 34 开始编码:因为第一个数字是35,我们必然可以从字典中找到与之匹配的条目(也就是第35个),但我们不急着用第35个条目与之匹配,先看看第二个数字是46,希望在字典中 能找到一个更长的模式“35 46”这样的条目,与之匹配,但不幸的是我们没有找到,所以只对第一个数字35编码,结果输出35;同时把“35 46”加入字典的第256项,希望以后能碰到它.同理,对46编码,输出46,同时把“46 67”加入字典的第257项.同理,对67编码,输出67,同时把“67 35”加入字典的第258项.这时注意了:对35编码,是不是现在还输出35呢?当然不是,我们发现35后面跟着 46,扫描字典,可以发现第256个模式与之匹配,输出256.同时,将模式“35 46 78“加入到 字典的第259项.同理,接下来输出 78,90,33,259,34.所以输出的码流为35 46 67 256 78 90 33 259 34.对上面的过程归纳一下:在编码的过程中生成字典;一边从字典中选择长度尽量长的模式 与原始码流匹配.,8.4.3 位平面编码,二值图像位平面；灰度编码位平面；,8.4 无损压缩,消除像素间冗余,位平面分解的两种方法：,位平面编码过程可以分成两步：位平面分解；二值图像压缩,将一幅图像分解为一系列二值图像并通过二值图像压缩方法对每幅二值图像进行压缩,二值图像位平面,一幅m比特的灰度图像具有的灰度级表示如下,零级位平面是通过收集每个像素的a0位生成，第(m-1)级位平面包含am-1位,缺点：图像在灰度级上稍有变化就会对位平面的复杂性产生显著影响，如亮度127(01111111)和亮度128(10000000)的转换,灰度编码位平面,图像的灰度编码是先用一个m比特的格雷码表示图像,避免二值图像位平面的缺点，连续码字只在1位位置上不同,如亮度127(01000000)和亮度128(11000000)的转换,位平面分解示例图8.14,8.4.3 位平面编码,二值图像位平面,灰度编码位平面,二值图像位平面,灰度编码位平面,高比特位平面比低比特要简单；高比特位平面包含大块的均匀区域，图像细节较少；灰度编码位平面比二值位平面复杂性较少,二值图像压缩编码,常数值区域编码CAC一维行程编码二维行程编码（略）轮廓线追踪和编码（略）,常数块编码,将图像分成全黑，全白或混合的pq尺寸的块；出现频率最高的类赋予码字0，其它两类分别赋予码字10和11；,压缩二值图或位平面的一种简单有效的方法是使用指定的码字识别大片连续的“1”或“0”区域。这样的方法称为区域编码(CAC),8.4.3 位平面编码,原来需用pq比特表示的常数块现在只用1位或2位表示，达到压缩的目的；赋予混合块的码只是作为前缀，后面还需跟上该块的用pq位表示的模式；当需压缩的图像主要由白色部分组成时（如文档），可将白色区域编为0，其它块用1接上该块的位模式编码WBS编码（跳过白色块编码）；,将二值图或位平面迭代地分解成尺寸越来越小的子块。如果子块不是全白，继续分解，直至某个事先确定的子块尺寸。如果最后子块全白，就编为0，反之编为1加上该块的位模式,WBS编码(White Block Skipping)：大多数二值图像中的黑象素只占图像象数总数很少的一部分。因此若能跳过白色区域，对黑色像素编码这样表示这些图像的比特数将减少，每个像素平均比特数也就可以减少,跳过白色块（WBS）编码,1)一维WBS编码,将图像的每条扫描线分成若干段，每段有N个像素。对全部是白色的像素用“0”表示。对于至少有一个黑色像素的像素段采用N十1个比特编码。即第一个比特人为地规定为1，其余的N比特采用直接编码(白色为“0”黑色为“1”码字)。,一维WBS编码平均码字长度为,其中：N段长；段长为N的全白像素段出现的概率。,段长N不同，全白概率也不同。为了获得最小的平均码字长度，对给定的一幅二值图像应有一个最佳N值，不同图像的最佳段长N值不同。,N=4时，全白概率必须大于14才可能获得压缩效果,1)一维WBS编码,2)二维WBS编码,最终获得的编码：0100100010101000,假设像素块尺寸为MN，全部为白色的像素块用“0”表示，非全白像素块用(MN+1)个比特码表示。其中第一个比特为“1”。其余MN个比特采用直接编码。,二值图像压缩编码,一维行程编码,8.4.3 位平面编码,是传真编码的标准压缩方法；对从左到右扫描一行时所遇到的1或0的连接组（行程）的长度进行编码；,决定行程长度值的常用方法：,指定每一行第一个行程的长度值；假设每一行从白色行程开始，这次行程的长度可能为0；,在一个逐行存储的二值图象或位平面图像中，具有相同灰度值的一些象素组成的序列 称为一个行程。在编码时，对于每个行程 只存储一个灰度值的码，再紧跟着存储这个行程的长度。这种按照行程进行的编码被称为行程编码（Run Length Encoding）。,行程的表示：,常数值区域编码CAC一维行程编码二维行程编码（略）轮廓线追踪和编码（略）,一维行程编码,见p332图8.3,尽管行程长度编码本身是一种压缩图像的有效方法，但其它的压缩方法通常可以通过对行程长度本身进行变长编码实现。这些变长编码是根据他们自身的统计数据特殊制定的。,通过用变长码对游程的长度编码可取得更高的压缩率；将黑和白的游程长度分开，并根据它们的统计特性分别用变长码编码；,令符号 代表长为j的一个黑色游程,这样，图像的游程熵近似为：,用式(8.4.4)估计每个像素所需的平均比特数。,白色行程的信源熵,L0、L1分别代表黑色和白色游程长度的平均值。,二值图像压缩编码,二维行程编码,8.4.3 位平面编码,1D行程编码（Run Length Coding）只考虑了消除每行象素（或水平分解元素）的相关性，而未考虑消除行间象素（或垂直分解元素）的相关性。2D行程编码将考虑两个方向的分解元素的相关性。,2-D游程长度编码（相对地址编码RAC）：其基本原理是跟踪各个黑色和白色游程的起始和终结过渡点。,cc是从c到上1行在e之后第1个类似过渡点c之距离。如果ecccRAC距离d=ec，反之，如果eccc取RAC距离d=cc（取小的，取下边）,常数值区域编码CAC一维行程编码二维行程编码（略）轮廓线追踪和编码（略）,采用类似B1码对RAC距离编码。最短的距离用最短的码字，其它所有距离用如下方法编：用第1个前缀表示最短的RAC距离 第2个前缀将d赋给某个距离范围 再如上d-范围下限的二进制表示 如在上图中ec=8 cc=4 则RAC码 1100 0 11,对多数图像来说，RAC距离的概率分布是不均匀的，所以要用合适的变长码来对RAC距离进行编码。,2-D游程长度（相对地址）编码例子图8.17（b）,分析：对于有大面积色块的图像，压缩效果很好对于纷杂的图像，压缩效果不好，最坏情况下，会加倍图像,行程编码,二值图像压缩编码,边界跟踪和编码,8.4.3 位平面编码,通过跟踪二值图中的区域边界并进行编码，也可达到对常数区编码的目的，预测微分量化就是一种面向扫描线的边界跟踪方法（叫PDQ）。,常数值区域编码CAC一维行程编码二维行程编码（略）轮廓线追踪和编码（略）,DDC编码：,PDQ编码：,各参数的意义见图8.18。前一扫描行和后一扫描行的对应差异对 连结起来，解码器可根据这些信息正确地确定边界在图中的位置。PDQ和DDC编码的最后一步都是对 或 及表示新边界开始和旧边界结束的行和列的坐标用变长码编码。为了避免对每个表示新边界开始和边界结束的行和列坐标都编码，需用1个独特的码代表与区域不相交的扫描线。,结论：（1）各种方法得到的码率都比一阶熵估计要小，说明各种方法均能消除一定的像素冗余，其中游程码最好。（2）灰度编码能提高编码性能约为1bit/pixel（相对于二值编码）。（3）所有5种方法压缩率都在12之间，这主要是因为它们对低位面的压缩的最差，“”代表此处数据膨胀。,例8.14。二值压缩技术的比较。见下页表8.8用游程编码的熵的一阶估计作为变长码所能达到的压缩性能（H）的近似。,8.4.4无损预测编码,该像素的当前值与预测值的差,8.4 无损压缩,消除像素间冗余,一个像素的新信息定义为：,仅提取每个像素中的新信息并对新信息编码来消除像素间的冗余,正是由于像素间有相关性，所以才使预测成为可能;大多数情况下，是通过m个以前像素的线性组合来生成的；例如：一维线性预测编码一维线性预测不能对每一行的前m个像素进行，故这些像素必须用其他方法进行编码（如霍夫曼编码）,8.4 无损压缩,（1）当输入图像的像素序列 逐个进入编码器，预测器根据过去的输入产生当前输入像素的估计值。预测器的输出舍入成最近的整数 并被用来计算预测误差。（2）该误差用符号编码器借助变长码进行编码以产生压缩数据流的下一个元素。然后解码器根据接收到的变长码字重建，并执行下列操作（3）还有局部的、全局的、自适应的方法生成,8.4.4 无损预测编码 例8.15,叫前像素预测器，相应的编码过程称为差分编码或前像素编码。压缩比一般为2：1左右,预测误差的概率密度函数：一般用0均值不相关的拉普拉斯概率密度函数表示,附录：Laplace分布,在概率论与统计学中，拉普拉斯分布是以皮埃尔-西蒙拉普拉斯的名字命名的一种连续概率分布。由于它可以看作是两个不同位置的指数分布背靠背拼接在一起，所以它也叫作双指数分布。两个相互独立同概率分布指数随机变量之间的差别是按照指数分布的随机时间布朗运动，所以它遵循拉普拉斯分布。,那么它就是拉普拉斯分布。其中，是位置参数，0 是尺度参数。如果=0，那么，正半部分恰好是尺度为 1/2 的指数分布。拉普拉斯分布的概率密度函数让我们联想到正态分布，但是，正态分布是用相对于 平均值的差的平方来表示，而拉普拉斯概率密度用相对于平均值的差的绝对值来表示。因此，拉普拉斯分布的尾部比正态分布更加平坦。,附录：Laplace分布,根据绝对值函数，如果将一个拉普拉斯分布分成两个对称的情形，那么很容易对拉普拉斯分布进行积分。它的累积分布函数为：,那么它就是拉普拉斯分布。其中，是位置参数，0 是尺度参数。如果=0，那么，正半部分恰好是尺度为 1/2 的指数分布。拉普拉斯分布的概率密度函数让我们联想到正态分布，但是，正态分布是用相对于 平均值的差的平方来表示，而拉普拉斯概率密度用相对于平均值的差的绝对值来表示。因此，拉普拉斯分布的尾部比正态分布更加平坦。,逆累积分布函数为:,附录：Laplace分布,如果 Y=|X|并且 XLaplace，则 YExponential 是指数分布。如果 Y=X1 X2且X1、X1Exponential，则 YLaplace。,已知区间(-1/2,1/2 中均匀分布上的随机变量 U，随机变量 为参数 与 的拉普拉斯分布。,当两个相互独立同分布指数(1/)变化的时候也可以得到 Laplace(0,)变量。同样，当两个相互独立同分布一致变量的比值变化的时候也可以得到 Laplace(0,1)变量。,