遥感数字图像处理-第六章-图像编码与压缩PPT课件

-,1,第六章图像编码与压缩,讲解内容1.图像压缩的概念、目的和意义2.霍夫曼编码方法3.费诺-仙龙编码4.图像的行程编码目的1.了解图像压缩的目的和意义，熟悉图像压缩评价方法；2.掌握图像行程编码、霍夫曼编码方法,-,2,图像编码的研究背景,数码图像的普及，导致了数据量的庞大。图像的传输与存储，必须解决图像数据的压缩问题。,-,3,第六章图像编码与压缩6.1概述,6.1.1图像数据压缩的必要性与可能性数据压缩的研究内容包括数据的表示、传输、变换和编码方法，目的是减少存储数据所需的空间和传输所用的时间。图像编码与压缩就是对图像数据按一定的规则进行变换和组合，达到以尽可能少的代码（符号）来表示尽可能多的图像信息。,-,4,图像数据的特点之一是信息量大。海量数据需要巨大的存储空间。如多媒体中的海量图像数据，不进行编码压缩处理，一张600M字节的光盘，能存放20秒左右的640480像素的图像，没有编码压缩多媒体信息保存有多么困难是可想而知的。在现代通信中，图像传输已成为重要内容之一。采用编码压缩技术，减少传输数据量，是提高通信速度的重要手段。可见，没有图像编码与压缩技术的发展，大容量图像信息的存储与传输是难以实现的，多媒体、信息高速公路等新技术在实际中的应用会遇到很大困难。,-,5,数据冗余的概念数据是用来表示信息的。如果不同的方法为表示定量的信息使用了不同的数据量，那么使用较多数据量的方法中，有些数据必然是代表了无用的信息，或者是重复地表示了其它数据已表示的信息，这就是数据冗余的概念。冗余数据有：编码冗余、像素间冗余、心理视觉冗余3种。,-,6,512,512,数字图像的表示编码,存储上面灰度图像所需的容量(数据量):,-,7,为表达图像数据需要用一系列符号，用这些符号根据一定的规则来表达图像就是对图像编码。对每个信息所赋的符号序列称为码字，而每个码字里的符号个数称为码字的长度。编码所用的符号构成的集合称为码本。,-,8,等长码：对于一个消息集合中的不同消息，用相同长度的不同码字表示，编解码简单，编码效率不高。,变长码：与等长码相对应，对于一个消息集合中的不同消息，也可以用不同长度的码字表示，编码效率高，编码解码复杂。,-,9,什么是编码冗余？如果一个图像的灰度级编码，使用了多于实际需要的编码符号，就称该图像包含了编码冗余。,数据冗余,-,10,什么是像素间冗余？由于任何给定的像素值，原理上都可以通过它的邻居预测到，单个像素携带的信息相对是小的。对于一个图像，很多单个像素对视觉的贡献是冗余的。这是建立在对邻居值预测的基础上。原始图像越有规则，各像素之间的相关性越强，它可能压缩的数据就越多。例如：原图像数据：234223231238235压缩后数据：234-1187-3,数据冗余,-,11,这是由于眼睛对所有视觉信息感受的灵敏度不同。在正常视觉处理过程中各种信息的相对重要程度不同。有些信息在通常的视觉过程中与另外一些信息相比并不那么重要，这些信息被认为是心理视觉冗余的，去除这些信息并不会明显降低图像质量。,数据冗余,什么是心理视觉冗余？,33K,15K,-,12,如果能减少或消除其中的1种或多种冗余，就能取得数据压缩的效果。因此图像信息的压缩是可能的。但到底能压缩多少，除了和图像本身存在的冗余度大小有关外，很大程度取决于对图像质量的要求。广播电视压缩比31可视电话压缩比15001目前高效图像压缩编码技术已能用硬件实现实时处理，在广播电视、工业电视、电视会议、可视电话、传真和互连网等多方面得到应用。,-,13,图像压缩的目的,图像数据压缩的目的是在满足一定图像质量条件下，用尽可能少的比特数来表示原始图像，以提高图像传输的效率和减少图像存储的容量。在信息论中称为信源编码。,-,14,图像数据压缩技术的重要指标,（1）压缩比：图像压缩前后所需的信息存储量之比，压缩比越大越好。,（2）失真性：压缩前后图像存在的误差大小。,-,15,6.2图像保真度准则描述解码图像相对原始图像偏离程度的测度一般称为保真度。常用的保真度准则可分为两大类：客观保真度准则和主观保真度准则。,-,16,6.2.1.客观保真度准则当所损失的信息量可以用初始图像（或输入图像）与先被压缩而后被解压缩的输出图像的函数表示时，它就是基于客观保真度准则的。常用的两种客观保真度准则均方根误差均方根信噪比,保真度准则,-,17,6.2.2主观保真度准则很多解压图最终是供人观看的，一种常用的方法是让一组（不少于20人）观察者观察图像并给该图像评分，将他们对该图像的评分取平均，作为这幅图像的质量。,一个主观保真度准则规定为：,-,18,原始图像经编码后成为一串特定的码流，这串码流经解码又成为一幅图像解码图像与原始图像相同，称编解码过程是无损的；解码图像也可以与原始图像不同，称编解码过程是有损的,-,19,6.1.2图像编码压缩的分类根据解压重建后的图像和原始图像之间是否具有误差，图像编码压缩分为无误差（亦称无失真、无损、信息保持）编码和有误差（有失真或有损）编码两大类。根据编码作用域划分，图像编码为空间域编码和变换域编码两大类。,图像压缩,无损编码,有损编码,霍夫曼编码行程编码算术编码,预测编码变换编码其它编码,-,20,无损压缩的必要性在医疗或商业文件的归档，有损压缩因为法律原因而被禁止。卫星成像的收集，考虑数据使用和所花费用，不希望有任何数据损失。X光拍片，信息的丢失会导致诊断的正确性无损压缩技术减少像素间冗余减少编码冗余,无损压缩,-,21,平均码长是灰度值为i的编码长度冗余度为编码效率为,6.2.3图像冗余度和编码效率根据Shannon无干扰信息保持编码定理，若对原始图像数据的信息进行无失真图像编码，压缩后平均码长存在一个下限，这个下限是图像信息熵H。理论上最佳信息保持编码的平均码长可以无限接近图像信息熵H。但总是大于或等于图像的熵H。,-,22,变长最佳编码定理定理在变长码中，对出现概率大的信息符号赋予短码字，而对于出现概率小的信息符号赋予长码字。如果码字长度严格按照所对应符号出现概率大小顺序排列，则编码结果平均码字长度一定小于任何其它排列方式。变长编码是统计编码中最为主要的一种方法。,-,23,6.3统计编码方法6.3.2霍夫曼编码Huffman编码是1952年由Huffman提出的一种编码方法。这种编码方法是根据信源数据符号发生的概率进行编码的。思想：在信源数据中出现概率越大的符号，编码以后相应的码长越短；出现概率越小的符号，其码长越长，从而达到用尽可能少的码符表示信源数据。它在无损变长编码方法中是最佳的。通过减少编码冗余来达到压缩的目的。,-,24,哈夫曼编码基本思想1)统计一下符号的出现概率，2)建立一个概率统计表，将最常出现（概率大的）的符号用最短的编码，最少出现的符号用最长的编码。设输入编码为，其频率分布分别为P(x1)=0.4，P(x2)=0.3，P(x3)=0.1，P(x4)=0.1，P(x5)=0.06，P(x6)=0.04。求其最佳霍夫曼编码,-,25,编码方法是：把输入符号按出现的概率从大到小排列起来,接着把概率最小的两个符号的概率求和;把它（概率之和）同其余符号概率由大到小排序,然后把两个最小概率求和;重复,直到最后只剩下两个概率为止。,在上述工作完毕之后，从最后两个概率开始逐步向前进行编码。对于概率大的消息赋予0，小的赋予1。,-,26,Huffman编码,输入S1S2S3S4S5S6,输入概率0.40.30.10.10.060.04,-,27,Huffman编码,输入S1S2S3S4S5S6,输入概率0.40.30.10.10.060.04,第一步0.40.30.10.10.1,-,28,Huffman编码,输入S1S2S3S4S5S6,输入概率0.40.30.10.10.060.04,第一步0.40.30.10.10.1,第二步0.40.30.20.1,-,29,Huffman编码,输入S1S2S3S4S5S6,输入概率0.40.30.10.10.060.04,第一步0.40.30.10.10.1,第二步0.40.30.20.1,第三步0.40.30.3,-,30,Huffman编码,输入S1S2S3S4S5S6,输入概率0.40.30.10.10.060.04,第一步0.40.30.10.10.1,第二步0.40.30.20.1,第三步0.40.30.3,第四步0.60.4,-,31,Huffman编码,输入S1S2S3S4S5S6,输入概率0.40.30.10.10.060.04,第一步0.40.30.10.10.1,第二步0.40.30.20.1,第三步0.40.30.3,第四步0.60.4,01,01,01,01,01,-,32,Huffman编码,输入S1S2S3S4S5S6,输入概率0.40.30.10.10.060.04,第一步0.40.30.10.10.1,第二步0.40.30.20.1,第三步0.40.30.3,第四步0.60.4,01,01,01,01,01,S1=1,-,33,Huffman编码,输入S1S2S3S4S5S6,输入概率0.40.30.10.10.060.04,第一步0.40.30.10.10.1,第二步0.40.30.20.1,第三步0.40.30.3,第四步0.60.4,01,01,01,01,01,S2=00,-,34,Huffman编码,输入S1S2S3S4S5S6,输入概率0.40.30.10.10.060.04,第一步0.40.30.10.10.1,第二步0.40.30.20.1,第三步0.40.30.3,第四步0.60.4,01,01,01,01,01,S3=011,-,35,Huffman编码,输入S1S2S3S4S5S6,输入概率0.40.30.10.10.060.04,第一步0.40.30.10.10.1,第二步0.40.30.20.1,第三步0.40.30.3,第四步0.60.4,01,01,01,01,01,S4=0100,-,36,Huffman编码,输入S1S2S3S4S5S6,输入概率0.40.30.10.10.060.04,第一步0.40.30.10.10.1,第二步0.40.30.20.1,第三步0.40.30.3,第四步0.60.4,01,01,01,01,01,S5=01010,-,37,Huffman编码,输入S1S2S3S4S5S6,输入概率0.40.30.10.10.060.04,第一步0.40.30.10.10.1,第二步0.40.30.20.1,第三步0.40.30.3,第四步0.60.4,01,01,01,01,01,S6=01011,-,38,元素xix1x2x3x4x5x6概率P(xi)0.40.30.10.10.060.04,编码wi10001101000101001011,x10.4x20.3x30.1x40.1x50.06x60.04,(01010),(01011),(0100),(0101),0.40.30.10.10.1,0.40.30.20.1,0.40.30.3,(010),(011),0.60.4,(00),(01),(0),(1),Huffman编码讨论（1）Huffman编码的平均码长接近于熵；（2）缺点：需要多次排序，耗费时间。,-,40,用二叉树方法实现Huffman编码方法也较为便利。（P130）,0.6,0.4x1,0.3x2,0.3,0.1x3,0.2,0.1x4,0.04x6,0.06x5,0.1,计算该信源的熵、编码后的平均码长，并思考对于同一图像采用Huffman编码，编码是否唯一？,？,01,01,01,01,01,-,41,Huffman编码举例,例：对数据序列aaaabbbccdeeeeefffffff其概率分布为：a:4/22b:3/22c:2/22d:1/22e:5/22f:7/22概率大小的排序为：d,c,b,a,e,f1/222/223/224/225/227/22,-,42,c,b,a,f,e,7/22,5/22,4/22,2/22,1,0,f=11e=01a=00b=101c=1001d=1000,d,1/22,3/22,6/22,22/22,13/22,9/22,3/22,1,0,1,0,1,0,1,0,Huffman编码举例,-,43,对这个例子，计算出经过Huffman编码后的数据为：00000000101101101100110011000010101010111111111111111共7*2+5*2+4*2+3*3+2*4+1*4=53bit,压缩比为176：53=3.32:1,f=11e=01a=00b=101c=1001d=1000,Huffman编码举例,-,44,Huffman编码在图像压缩中的实现我们知道，对一幅图像进行编码时，如果图像的大小大于256时，这幅图像的不同的码字就有可能是很大，例如极限为256个不同的码字。对整幅图直接进行Huffman编码时，小分布的灰度值，就有可能具有很长的编码。如：100位以上，这样不但达不到压缩的效果反而会使数据量加大，应该如何处理？,Huffman编码举例,-,45,常用的且有效的方法是：将图像分割成若干的小块，对每块进行独立的Huffman编码。例如：分成的子块，就可以大大降低不同灰度值的个数（最多是64而不是256）。,Huffman编码举例,-,46,8*8分块的编码压缩比为2.12:1,16*16分块的编码压缩比为1.64:1,全图的编码压缩比为1.09:1,Huffman编码图像压缩中的应用,-,47,题目示例：,1.有如下信源x，,其中：P10.21,P20.09,P30.11,P40.13,P50.07,P60.12,P70.08,P80.19。将该信源进行哈夫曼编码。,2.设一幅灰度级为8（分别用S0、S1、S2、S3、S4、S5、S6、S7表示）的图像中，各灰度所对应的概率分别为0.40、0.18、0.10、0.10、0.07、0.06、0.05、0.04。对其进行哈夫曼编码,X,-,48,3.设有一信源X=x1,x2,x3,x4，对应概率P=0.5,0.1975,0.1775,0.125.进行霍夫曼编码(要求大概率的赋码字0,小概率的赋码字1)，给出码字，平均码长，编码效率;对码串10101011010110110000011110011解码.,-,49,由于霍夫曼编码法需要多次排序，当很多时十分不便，为此费诺(Fano)和香农(Shannon)分别单独提出类似的方法，使编码更简单。具体编码方法如下：把按概率由大到小、从上到下排成一列，然后把分成两组，并使得把两组分别按0，1赋值。然后分组、赋值，不断反复，直到每组只有一种输入为止。将每个所赋的值依次排列起来就是费诺香农编码。,6.3.3香农费诺编码,以前面哈夫曼编码的例子进行香农费诺编码：,-,51,6.3.5行程编码RLE(RunLengthEncoding)图像中经常包含一些区域，尤其是那些包含很少几个灰度级的图像，它们是由具有相同颜色或灰度的相邻像素组成的。在一个逐行存储的图像中，具有相同灰度值的一些像素的序列，称为一个行程。,基本原理：通过改变图像的描述方式，来实现压缩。将一行中颜色值相同的相邻像素用一个计数值和该颜色值来代替。举例说明：aaaabbbccdeeeeefffffff(共22*8=176bits)4a3b2c1d5e7f(共12*8=96bits),压缩比为：176：96=1.83:1,-,52,行程编码是一种最简单的，在某些场合是非常有效的一种无损压缩编码方法。虽然这种编码方式的应用范围非常有限，但是因为这种方法中所体现出的编码设计思想非常明确，所以在图像编码方法中都会将其作为一种典型的方法来介绍。,-,53,二维行程编码基本概念,二维行程编码要解决的核心问题是:将二维排列的像素，采用某种方式转化成一维排列的方式。之后按照一维行程编码方式进行编码。,-,54,二维行程编码数据排序,如下图所示，是两种典型的二维行程编码的排列方式：,(a),(b),-,55,二维行程编码例,例：,数据量：64*8=512(bit),-,56,二维行程编码例,如果按照行扫描的顺序排列的话，数据分布为：,130，130，130，129，134，133，129，130；130，130，130，129，134，133，130，130；130，130，130，129，132，132，130，130；129，130，130，129，130，130，129，129；127，128，127，129，131，129，131，130；127，128，127，128，127，128，132，132；125，126，129，129，127，129，133，132；127，125，128，128，126，130，131，131,-,57,二维行程编码例,一维行程编码后为:,（3，130），（1，129），（1，134），（1，133），（1，129），（4，130），（1，129），（1，134），（1，133），（5，130），（1，129），（2，132），（2，130），（1，129），（2，130），（1，129），（2，130），（2，129），（1，127），（1，128），（1，127），（1，129），（1，131），（1，129），（1，131），（1，130），（1，127），（1，128），（1，127），（1，128），（1，127），（1，128），（2，132），（1，125），（1，126），（2，129），（1，127），（1，129），（1，133），（1，132），（1，127），（1，125），（2，128），（1，126），（1，130），（2，131）,数据量为:46*（3+8）=506(bit)压缩比为：512：506=1.02:1,-,58,二维行程编码例,如果按照方式(a)扫描的顺序排列的话，数据分布为：,130，130，130，130，130，130，130，130，130；129，129，129，129，130，130，129；127，128，127，129，131，130，132，134，134；133，133，132，130，129，128，127，128，127，128，127，125，126，129，129；127，129，133，132，131，129，130，130；129，130，130，130，129，130，132，132；131，131，130，126，128，128，127，127,-,59,二维行程编码例,一维行程编码为:,数据量为:43*（3+8）=473(bit)压缩比为：512：473=1.08:1,（7，130），（2，130），（4，129），（2，130），（1，129）；（1，127），（1，128），