印刷专业平面设计课件.ppt

单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,印刷专业平面设计课件,印刷专业平面设计课件印刷专业平面设计课件7.1 图像编码的必要性与可能性7.1.1图像编码的必要性,数字图像的庞大数据对计算机的处理速度、存储容量都提出过高的要求。因此必须把数据量压缩。,从传送图像的角度来看，则更要求数据量压缩。在信道带宽、通信链路容量一定的前提下，采用编码压缩技术，减少传输数据量，是提高通信速度的重要手段。,1,7.1,图像编码的必要性与可能性,7.1.1,图像编码的必要性,数字图像的庞大数据对计算机的处理速度、存储容量都提出过高的要求。,因此必须把数据量压缩。,从,传送图像的角度来看,，则更要求数据量压缩。在信道带宽、通信链路容量一定的前提下，采用编码压缩技术，减少传输数据量，是提高通信速度的重要手段。,2,7.1.2,图像编码的可能性,组成图像的,各像素之间,，无论是在图像的行方向还是在列方向，都存在着一定的,相关性,。,常见的静态图像数据冗余包括：,空间冗余，结构冗余，知识冗余，视觉冗余，图像区域的相同性冗余，纹理的统计冗余,。,3,7.2,图像编码分类,根据解压重建后的图像和原始图像之间是否具有误差，可以将图像编码与压缩方法分为,无误差,(,亦称无失真、无损、信息保持,),编码和,有误差,(,有失真或有损,),编码两大类。,根据编码作用域划分，图像编码分为,空间域编码,和,变换域编码,两大类。,若从具体编码技术来考虑，又可分为,预测编码,、,变换编码,、,统计编码、轮廓编码、模型编码,等。,4,7.3,图像编码评价准则,在图像压缩编码中，解码图像与原始图像可能会有差异，因此，需要评价压缩后图像的质量。,描述解码图像相对原始图像偏离程度的测度一般称为,保真度,(,逼真度,),准则,。,常用的准则可分为两大类：,客观保真度准则,和,主观保真度准则。,5,7.3.1,客观保真度准则,最常用的客观保真度准则是原图像和解码图像之间的,均方根误差,和,均方根信噪比,两种。,均方根误差,:,均方信噪比:,对上式求平方根，就得到均方根信噪比。,（7-2）,（7-3）,6,7.3.2,主观保真度准则,具有相同客观保真度的不同图像，人的视觉可能产生不同的视觉效果。,这是因为客观保真度是一种统计平均意义下的度量准则，对于图像中的细节无法反映出来。,一种常用的方法是对一组,(,不少于,20,人,),观察者显示图像，并将他们对该图像的评分取平均，用来评价一幅图像的主观质量。,7,例如可用-3，-2，-1，0，1，2，3来代表主观评价很差，较差，稍差，相同，稍好，较好，很好。,评分,评价,说明,1,优秀,图像质量非常好，如同人能想象出的最好质量,2,良好,图像质量高，观看舒服，有干扰但不影响观看,3,可用,图像质量可以接受，有干扰但不太影响观看,4,刚可看,图像质量差，干扰有些妨碍观看，观察者希望改进,5,差,图像质量很差，几乎无法观看,6,不能用,图像质量极差，不能使用,表,7.1,电视图像质量评价尺度,8,7.4,图像编码模型,一个图像压缩系统包括两个不同的结构块：,编码器和解码器,。,图像,f,（,x,，,y,）输入到编码器中，编码器可以根据输入数据生成一组符号。在通过信道进行传输之后，将经过编码的表达符号送入解码器，经过重构后，生成输出图像。,f,(x,y),信源,编码,信道,编码,信道,信道,解码,信源,解码,f,(x,y),一个常用于图像压缩系统模型,9,7.4.1信源编码器和信源解码器,信源编码器的任务,是,减少或消除输入图像中的编码冗余、像素间冗余或心理视觉冗余,。,从原理来看主要分为,三个阶段,:,第一阶段将输入数据转换为可以减少输入图像中像素间冗余的数据的集合。,第二阶段设法去除原图像信号的相关性。,第三阶段是找一种编码方式。,信源解码器包含两部分：,符号解码器和反向转换器。,10,编码器模型,f(x,y),转换器,量化器,符号编码器,信道,信道,符号解码器,反向转换器,f,(x,y),（a）信源编码器,（b）信源解码器,11,7.4.2,信道编码器和解码器,当信道带有噪声或易于出现错误时，信道编码器和解码器就在整个译码解码处理中扮演了重要的角色。信道编码器和解码器通过向信源编码数据中插入预制的冗余数据来减少信道噪声的影响,最有用的,种信道编码技术是由,R,w,Hamming,提出的。这种技术是基于这样的思想，即向被编码数据中加入足够的位数以确保可用的码字间变化的位数最小。,12,7.5无损压缩,无损压缩可以精确无误地从压缩数据中恢复出原始数据。,常见的无损压缩技术包括：基于统计概率的方法和基于字典的技术。,1.,基于统计概率的方法是依据信息论中的变长编码定理和信息熵有关知识，用较短代码代表出现概率大的符号，用较长代码代表出现概率小的符号，从而实现数据压缩。,统计编码方法中具有代表性的是利用概率分布特性的著名的,霍夫曼,(Huffman),编码方法,另一种是,算术编码,。,13,2.,基于,字典技术,的数据压缩技术有两种,：,一种是,游程编码,(Running Length Coding),，简称为,RLC,，适用于灰度级不多、数据相关性很强的图像数据的压缩。但最不适用于每个像素都与它周围的像素不同的情况。,另一种称之为,LZW,编码,，,LZW,在对数据文件进行编码的同时，生成了特定字符序列的表以及它们对应的代码。,14,7.5.1霍夫曼编码,一个事件集合,x,1,x,2,x,n,处于一个基本概率空间，其相应概率为,p,1,p,2,p,n,，且,p,1+,p,2+,p,n=1,。每一个信息的信息量为,:,如定义在概率空间中每,事件的概率不相等时的平均不肯定程度或平均信息量叫作,熵,H,，则：,1.理论基础,（7-9）,（7-10）,15,熵是编码所需比特数的下限，即编码所需要最少的比特。,例,:,设,8,个随机变量具有同等概率为,1,8,，计算信息熵,H,。,解,:,根据公式,7-10,可得：,H=8*-1/8*(log2(1/8)=-8*-1/8*(-3)=3,16,Huffman,编码是,1952,年由,Huffman,提出的一种编码方法。,这种编码方法根据信源数据符号发生的概率进行编码。,在信源数据中出现概率越大的符号，相应的码越短,；出现概率越小的符号，其码长越长，从而达到用尽可能少的码符号表示源数据。,它在变长编码方法中是最佳的。,2.Huffman编码,17,设信源,A,的信源空间为：,其中 ，现用,r,个码符号的码符号集,对信源,A,中的每个符号（,i,1,，,2,，,，,N),进行编码。,具体编码的方法是,:,(1),把信源符号按其出现概率的大小顺序排列起来；,(2),把最末两个具有最小概率的元素之概率加起来；,(3),把该概率之和同其余概率由大到小排队，然后再把,两个最小概率加起来，再重新排队；,(4),重复,(2),直到最后只剩下两个概率为止。,Huffman编码具体方法：,18,例,:,设有编码输入,其频率分布分别为,现求其最佳霍夫曼编码。,解,:Huffman,编码过程下图所示：,符号 概率,x,1,0.7,x,2,0.3,x,3,0.1,x,7,0.1,x,5,0.06,x,6,0.04,1,0.7,0.3,0.1,0.1,0.1,2,0.7,0.3,0.2,0.1,3,0.7,0.3,0.3,7,0.6,0.7,19,本例中对,0.6,赋予,0,，对,0.4,赋予,1,，,0.4,传递到,x,1,，所以,x,1,的编码便是,1,。,0.6,传递到前一级是两个,0.3,相加，大值是单独一个元素,x,2,的概率，小值是两个元素概率之和，每个概率都小于,0.3,，所以,x2,赋予,0,，,0.2,和,0.1,求和的,0.3,赋予,1,。所以,x2,的编码是,00,，而剩余元素编码的前两个码应为,01,。,0.1,赋予,1,，,0.2,赋予,0,。以此类推，最后得到诸元素的编码如下：,20,经霍夫曼编码后，平均码长为：,=,=0.71+0.302+0.13+0.17+0.065+0.075,=2.20(bit),该信源的熵为,H,2.17 bit,，编码后计算的平均码长为,2.2 bit,非常接近于熵。可见,Huffman,编码是,种较好的编码。,21,注意,:,短码不作长码的起始部分。,Huffman,编码是最佳的，其平均码长相同，不影响编码效率和数据压缩性能。,由于,Huffman,码的码长参差不齐，因此，存在一个输入、输出速率匹配问题。解决的办法是设置一定容量的缓冲存储器,Huffman,码在存储或传输过程中，如果出现误码，可能会引起误码的连续传播,Huffman,编码对不同信源其编码效率也不尽相同。,Huffman,编码应用时，均需要与其他编码结合起来使用，才能进一步提高数据压缩比。,Huffman编码,实现,22,7.5.2,香农费诺编码,由于霍夫曼编码法需要多次排序，当很多时十分不便，为此费诺,(Fano)和香农(Shannon)分别单独提出类似的方法，使编码更简单。,具体编码方法如下,：,把 按概率由大到小、从上到下排成一列，然后把 分成两组，,并使得,把两组分别按0，1赋值。,然后分组、赋值，不断反复，直到每组只有一种输入为止。将每个所赋的值依次排列起来就是费诺香农编码。,23,以前面哈夫曼编码的例子进行香农费诺编码：,24,7.5.3,算术编码,理论上，用,Huffman,方法对源数据流进行编码可达到最佳编码效果。但,由于计算机中存储、处理的最小单位是“位”，因此，在一些情况下，实际压缩比与理论压缩比的极限相去甚远。,算术编码没有延用数据编码技术中用一个特定的代码代替一个输入符号的一般做法，它,把要压缩处理的整段数据映射到一段实数半开区间,0,，,1,内的某一区段，构造出小于,1,且大于或等于,0,的数值。,这个数值是输人数据流的唯,可译代码,。,25,对一个,5,符号信源,A,a1,a2,a3,a2,a7,，各字符出现的概率和设定的取值范围如下：,字符 概率 范围,a3,0.2,0.0,，,0.2,）,a1,0.2,0.2,，,0.4,）,a2,0.4,0.4,，,0.8),a7,0.2,0.8,，,1.0),“,范围”给出了字符的赋值区间。这个区间是根据字符发生的概率划分的。具体把,a1,、,a2,、,a3,、,a7,分配在哪个区间范围，对编码本身没有影响，只要保证编码器和解码器对字符的概率区间有相同的定义即可。为讨论方便起见，假定有,26,式中,Ns,为新于区间的起始位置；,Fl,为前于区间的起始位置，当前符号的区间左端；,N,e,为新于区间的结束位置；,Fe,为前子区间的结束位置；当前符号的区间右端；,L,为前子区间的长度。,按上述区间的定义，若数据流的第一个字符为,a1,，由字符概率取值区间的定义可知，代码的实际取值范围在,0.2,，,0.4,之间，即输入数据流的第一个字符决定了代码最高有效位取值的范围。,继续对源数据流中的后续字符进行编码。每读入一个新的符号，输出数值范围就进一步缩小。读入第二个符号,a2,取值范围在区间的,0.4,，,0.8,内。由于第一个字符,a1,已将取值区间限制在,0.2,，,0.4,的范围中，因此,a2,的实际取值是在前符号范围,0.2,，,0.4,的,0.4,，,0.8,处，从而字符,a2,的编码取值范围在,0.28,，,0.36,，而不是在,0,，,1,整个概率分布区间上。,27,每输入一个符号，都将按事先对概率范围的定义，在逐步缩小的当前取值区间上确定新的范围上、下限。继续读入第三个符号,a3,受到前面巳编码的两个字符的限制，它的编码取值应在,0.28,，,0.36,中的,0.0,，,0.2,内，即,0.28,，,0.296,。重复上述编码过程，直到输入数据流结束。最终结果如下：,输入字符 区间长度 范围,a1,0.2,0.2,，,0.4,）,a2,0.08,0.28,，,0.36,）,a3,0.016,0.28,，,0.296),a2,0.0067 0.2867,，,0.2928),a1,0.00128 0.2915,，,0.2928,随着字符的输入，代码的取值范围越来越小。可以用一个浮点数表示一个字符串，达到减少所需存储空间的目的。,28,7.5.4,游程编码,游程编码,(RLC),是一种利用空间冗余度压缩图像的方法，属于统计编码类。,设图像中的某一行或某一块像素经采样或经某种变换后的系数为：某一行或某一块内像素值可分为,k,段，长度为 的连续串，每个串具有相同的值，那么，该图像的某一行或某一块可由下面偶对 来表示：,其中 为每个串内的代表值，为串的长度。串长就是游程长度,(Runlength),，简写为,RL,，即由灰度值构成的数据流中各灰度值重复出现而形成的长度。如果给出了灰度值、对应长度及位置，就能很容易地恢复出原来的数据流。,29,RL,的基本结构,游程编码分为定长游程编码和变长游程编码两类。,定长游程编码是指编码的游程所使用位数是固定的，即,RL,位数是固定的。如果灰度连续相同的个数超过了固定位数所能表示的最大值，则进入下一轮游程编码。,变长游程编码是指对不同范围的游程使用不同位数的编码，即表示,RL,位数是不固定的。,X S,C,RL,串字符,串位置,串长,30,游程编码一般不直接应用于多灰度图像，但比较适合于二值图像的编码。,为了达到较好的压缩效果，有时游程编码和其他一些编码方法混合使用。,RLC,比较适合二值图像数据序列，其原因是在二值序列中，只有“,0”,和“,1”,两种符号；这些符号的连续出现，就形成了“,0”,游程：,L(0),，“,1”,游程：,L(1),。,定义了游程和游程长度之后，就可以把任何二元序列变换成游程长度的序列，简称游程序列。这一变换是可逆的，一一对应的。,31,7.5.5,无损预测编码,一幅二维静止图像，设空间坐标,(i,，,j),像素点的实际灰度为,f(i,j),，是根据以前已出现的像素点的灰度对该点的预测灰度，也称预测值或估计值，计算预测值的像素，可以是同一扫描行的前几个像素，或者是前几行上的像素，甚至是前几帧的邻近像素。实际值和预测值之间的差值，以下式表示：,（7-13）,32,由图像的统计特性可知，相邻像素之间有着较强的相关性。因此，其像素的值可根据以前已知的几个像素来估计，即预测。,预测编码是根据某一模型，利用以往的样本值对于新样本值进行预测，然后将样本的实际值与其预测值相减得到一个误差值，对于这一误差值进行编码。,如果模型足够好且样本序列在时间上相关性较强，那么误差信号的幅度将远远小于原始信号。,对差值信号不进行量化而直接编码就称之为无损预测编码。,33,无损预测编码器的工作原理图 如下：,预测器,源图像,熵编码器,编码表,压缩源图像,34,由先前三点预测可以定义为：,其中,a1,，,a2,a3,称预测系数，都是待定参数。如果预测器中预测系数是固定不变的常数，称之为线性预测。,预测误差：,（7-14）,（7-15）,35,设,a=f(i,j-1),，,b=f(i-1,j),c=f(i-1,j-1),，,的预测方法如右图所示，可有,8,种选择方法：,(a+b)/2,36,例：设有一幅图像，,f(i-1,j-1),f(i-1,j),f(i,j-1),f(i,j),的灰度值分别为,253,252,253,255,，用图,7-8,第四种选择方法预测,f(i,j),的灰度值，并计算预测误差。,解：,=a+b-c=f(i,j-1)+f(i-1,j)-f(i-1,j-1)=252+253-253=252,预测误差,=255-252=3,显然，预测误差,e(i,j)=2,比像素的实际值,f(i,j)=255,小的多，对,2,进行编码比对,255,直接编码将占用更少的比特位。,37,7.5.6,字典压缩算法,字典编码方法是以类似查字典的方式进行编码。它的,基本原理是以较长的字符串或经常出现的字母组合构成字典中的各个词条,，并用相对较短的数字或符号来表示的方法。,字典编码按其构成的方式可分为静态字典方法和动态字典方法。,38,1.LZ77,算法,LZ77,是,Jacob Ziv,和,Abraham Lempel,在,1977,年发表的一篇论文中提出的。利用该算法进行数据压缩、解压缩的过程，就像一个窗口在原始数据中滑动过程，故也常称为基于滑动窗口的自适应的字典压缩方法。,2 LZ78,算法,LZ78,是,Jacob Ziv,和,Abraham Lempel,在,1978,年发表的另一篇论文中提出的。,LZ78,算法不同于,LZ77,算法，它放弃了窗口概念，采用树形结构构造字典和保存短语，从而确保文件中的内容均能反映到字典中。,39,3 LZW,算法,1987,年，,Terry A.Welch,在,LZ78,的基础上进行了改进，这就是著名的,LZW,压缩算法。,LZW,压缩算法是一种基于字典算法的编码方法,.,他的基本思想是建立一个编码表,(,转换表,),也称串表,将输入字符串映射成定长的码子输出,通常码长设为,12bit.,12,位可以有,7 096,个不同的,12,位代码,这就是说,转换表有,7 096,个表项,其中,256,个表项用来存放已定义的字符,剩下,3 870,个表项用来存放前缀,40,LZW,编码算法的具体执行步骤如下,:,步骤,1:,开始时的词典包含所有可能的根,(Root),而当前前缀,P,是空的,;,步骤,2:,当前字符,(C):=,字符流中的下一个字符,;,步骤,3:,判断缀,2,符串,P+C,是否在词典中,(1),如果“是”,:P:=P+CPP(,用,C,扩展,P);,(2),如果“否”,把代表当前前缀,P,的码字输出到码字流,;,把缀,2,符串,P+C,添加到词典,;,令,P:=CPP(,现在的,P,仅包含一个字符,C);,步骤,7:,判断码字流中是否还有码字要译,(1),如果“是”,就返回到步骤,2;,(2),如果“否”,把代表当前前缀,P,的码字输出到码字流,;,结束,.,41,压缩算法流程图,42,举例：,原始码流,35 76 67 35 76 78 90 33 35 76 78 37,原理,(1).,准备一个数据字典,(,可以看做一个数组,).,数组的前,256,项初始化为,0,1,2,.,255,后面的项为空白,.,为方便起见,我们管字典中的每一项叫,模式,.(2),开始对图像文件编码,图像文件从左向右扫描,把扫描得到的数据与字典中的模式进行比较,.,如果相同,就把这个,模,index(,在数组中的位置,),作为码字输出,.,如果在字典中找不到与之匹配的模式,则在字典中创建一个新的模式,(,从第,256,项开始,).,43,原始码流,35 76 67 35 76 78 90 33 35 76 78 37,开始编码,:a,因为第一个数字是,35,我们必然可以从字典中找到与之匹配的模式,(,也就是第,35,个,),但我们不急着用第,35,个模式与之匹配,先看看第二个数字是,76,希望在字典中能找到一个更长的模式,35 76,这样的模式,与之匹配,但不幸的是我们没有找到,所以只对第一个数字,35,编码,结果输出,35;,同时把,35 76,加入字典的第,256,项,希望以后能碰到它,.b,同理,对,76,编码,输出,76,同时把,76 67,加入字典的第,257,项,.c,同理,对,67,编码,输出,67,同时把,67 35,加入字典的第,258,项,.d,这时注意了,:,对,35,编码,是不是现在还输出,35,呢,?,当然不是,我们发现,35,后面跟着,76,扫描字典,可以发现第,256,个模式与之匹配,输出,256.,同时,将模式,35 76 78,加入到字典的第,259,项,.e,同理,接下来输出,78,90,33,259,37.,所以输出的码流为,35 76 67 256 78 90 33 259 37.,44,参考文献,1,杨国梁,张光年,.,无损,LZW,压缩算法及实现,.,首都师范大学学报,(,自然科学版,).2007.12.25,卷，,11-13,2,董雪丰,严闪,.LZW,压缩算法,.,福建电脑,.2007.1,26-27,3,林小竹，籍俊伟,.,一种改进的,LZW,压缩算法,.,计算机工程,.2005.7,第,31,卷，,199-201,45,7.6有损压缩,有损编码是以丢失部分信息为代价来换取高压缩比。,有损压缩方法主要有有损预测编码方法、变换编码方法等。,46,7.6.1有损预测编码,在预测编码中，对差值信号进行量化后再进行编码就称之为有损预测编码。,有损预测方法有多种，其中差分脉冲编码调制,(Differential Pulse Code Modulation,，简称,DPCM),，是一种具有代表性的编码方法。,47,DPCM,系统由编码器和解码器组成，它们各有一个相同的预测器。,DPCM,系统的工作原理如下图所示,:,量化器,编码器,预测器,信道传输,解码器,输入,输出,预测器,48,系统包括发送、接收和信道传输三个部分。发送端由编码器、量化器、预测器和加减法器组成；接收端包括解码器和预测器等；信道传送以虚线表示。图中输入信号,f,(,i,j,),是坐标,(,i,j,),处的像素的实际灰度值，是由已出现先前相邻像素点的灰度值对该像素的预测灰度值。,e(i,j),是预测误差。,DPCM,包含量化器，这时编码器对编码，量化器导致了不可逆的信息损失，这时接收端经解码恢复出的灰度信号不是真正的,f,(,i,j,),，而是重建信号。可见引入量化器会引起一定程度的信息损失，使图像质量受损。但是可以利用人眼的视觉特性，丢失不易觉察的图像信息，不会引起明显失真。,49,7.6.2变换编码,变换编码不是直接对空域图像信号编码，而是首先将图像数据经过某种正交变换（如傅立叶变换（,DFT,），离散余弦变换（,DCT,），,K-L,变换等等）另一个正交矢量空间,(,称之为变换域,),，产生一批变换系数，然后对这些变换系数进行编码处理，从而达到压缩图像数据的目的。,50,变换编码的原理 如下图：,图像数据经过正交变换后，空域中的总能量在变换域中得到保持，但像素之间的相关性下降，能量将会重新分布，并集中在变换域中少数的变换系数上，因此，选择少数,F(u,v),来重建图像就可以达到压缩数据的目的，并且重建图像仅引入较小误差。,变换多采用正交函数为基础的变换。,f(x,y),重建,f(x,y),图象,正交,变换,样本,选择,量化,编码,F(u,v),反正交,变换,补零,解码,数字信道,51,卡胡南,-,列夫变换（,K-L,）,对于,N,N,的矩阵,T,，有,N,个标量,i,，,i=1,2,N,能使,|T-iI|=0,则,i,叫做矩阵,T,的特征值。另外，,N,个满足,的向量,V,i,叫做,T,的特征向量，这些特征向量构成一个正交基集。,设,X,是一个,N,1,的随机向量，也就是说，,X,的每个分量都是,x,i,随机变量。,X,的均值（平均向量）可以由,L,个样本向量来估计向量,Mx,：,（7-32）,52,Mx,协方差矩阵可以由,来估计。协方差矩阵是实对称的。对角元素是个随机变量的方差，非对角元素是它们的协方差。,定义一个线性变换,T,，它可由任何,X,向量产生一个新向量,Y,：,式中，,T,的各行是,Mx,的特征向量，即,T,的行向量就是,Mx,的特征向量。,（7-33）,（7-34）,53,变换得到的,Y,是期望为零的随机向量。,Y,的协方差矩阵可以由,X,的协方差矩阵决定：,因为,T,的各行是,x,的特征向量，故,y,是一个对角阵，对角元素是的,x,特征值。因此,这些也是的,x,特征值。,随机向量,Y,是由互不相关的随机变量组成的，因此线性变换,T,起到了消除变量间的相关性的作用。,x,1,0,0,N,（7-35）,54,特征向量变换是可逆的。,要实现对信号进行,KL,变换，首先要求出矢量,x,的协方差短阵,x,，再求协方差矩阵,x,的特征值,i,，然后求,对应的,x,的特征向量，再用,x,的特征向量构成正交矩阵,T,。,例,:,若已知随机矢量,x,的协方差矩阵为,求其正交矩阵,T,？,x,6 2 0,2 2 1,0 1 1,55,1),按,求,x,的特征值,i:,得,:,则可解得,:=6.857 =2 =0.176,2),求,i,对应的特征向量。将,1,，,2,，,3,代入,(7-31),中分别求得如下三个特征向量：,=,56,用,V1,，,V2,，,V3,的转置向量作为正交矩阵,T,的行向量，那么，对于任一均值为,0,的向量,X=(2,，,1,，,-0.1),的,K-L,变换为,:,则,Y,的协方差矩阵,y,为,:,Y=TX=,0.918 0.329 0.067,0.333 0.667 0.667,0.217 0.637 0.772,2,1,0.1,=,2.237,0.067,0.127,Y,=,T,X,T,T,=,6.857 0 0,0 2 0,0 0 0.176,57,离散余弦变换,(DCT),在数字图像压缩编码中，最佳变换,K-L,计算复杂，一般不采用。,由于,DCT,与,K-L,变换压缩性能和误差很接近，而,DCT,计算复杂度适中，又具有可分离特性，还有快速算法等特点，所以近年来在图像数据压缩中，采用离散余弦变换编码的方案很多。,JPEG,、,MPEG,、,H.261,等压缩标准，都用到离散余弦变换编码进行数据压缩。,余弦变换是傅立叶变换的一种特殊情况。在傅立叶级数展开式中，如果被展开的函数是实偶函数，那么，其傅立叶级数中只包含余弦项，再将其离散化由此可导出余弦变换，或称之为离散余弦变换,DCT(Discrete Cosine Transform),。,58,二维离散偶余弦正变换公式为：,式中，,x,y,u,v,0,，,1,，,N-1,。,当,u=v=0,时。,当,u=1,，,2,，,，,N-1,；,v=1,，,2,，,，,N-1,时。,（7-38）,59,二维离散偶余弦逆变换公式为：,式中,x,y,u,v,0,，,1,，,N-1,。,当,u=v=0,时。,当,u=1,，,2,，,，,N-1,；,v=1,，,2,，,，,N-1,时。,（7-39）,60,二维离散余弦变换核具有可分离特性，所以，其正变换和逆变换均可将二维变换分解成系列一维变换,(,行、列,),进行计算。,在,DCT,为主要方法的变换编码中，一般不直接对整个图像进行变换，而是首先对图像分块，将,MN,的一幅图像分成不重叠的,M/KN/K,个,KK,块分别进行变换。,这样做的好处主要体现在：,第一，降低运算量，如对一幅,512512,图像，分块变换仅需约,1,3,的运算量；,其次，后续的量化和扫描处理可以得到明显的简化；,第三，容易将传输误差引起的错误控制在一个块内，而不是整个图像扩散。分块大小通常选,8 8,和,16 16,。,61,7.7 JPEG,图像编码压缩标准,JPEG(Joint Photographic Expert Group,，简称,JPEG),是联合图像专家小组的英文缩写。其中“联合”的含意是指，国际电报电话咨询委员会,CCIITI,和国际标淮化协会,(ISO),联合组成的一个图像专家小组。,JPEG,算法被确定为,JPEG,国际标准，它是国际上彩色、灰度、静止图像的第一个国际标准。,JPEG,标准适于静图像的压缩，电视图像序列的帧内图像的压缩编码也常采用,JPEG,压缩标准。,62,7.7.1 JPEG,的工作模式,JPEG,对每一个图像分量单独编码。,JPEG,对每个不同的图像分量可以采用不同的量化参数和熵编码的码表,对于一个图像分量，,JPEG,提供,7,种工作模式。,顺序编码,：每一个图像分量按从左到右，从上到下扫描，一次扫描完成编码。,累进编码,：图像编码在多次扫描中完成。,无失真编码,：解码后能精确地恢复源图像采样值，其压缩比低于有失真压缩编码方法。,分层编码,：图像在多个空间分辨率进行编码。,63,7.7.2,基本工作模式,基于,DCT JPEG,编码的过程框图,88块,编码器,DCT,正变换,量化器,熵编码器,量化表,熵编码器,源图像数据,压缩的图像数据,64,7.7.2,基本工作模式,解码过程框图,解码器,逆变换,(IDCT),反量化器,熵解码器,量化表,熵编码器,恢复的图像,数据,65,JPEG,采用的是,88,大小的子块的二维离散余弦变换,(DCT),。,在编码器的输入端，把原始图像顺序地分割成一系列,88,的子块，设原始图像的采样精度为,P,位，是无符号整数，输入时把,0,，,2,P,范围的无符号整数变成,-2,P-1,，,2,P-1,-1,范围的有符号整数，以此作为离散余弦正变换的输入。,在解码器的输出端经离散余弦逆变换,(IDCT),后，得到一系列,8 8,的图像数据块，需将其数值范围由,-2,P-1,，,2,P-1,-1,再变回到,0,，,2,P,范围内的无符号整数，来获得重构图像。,66,为了达到压缩数据的目的，对,DCT,系数需作量化处理。量化处理是一个多到一的映射，它是造成,DCT,编解码信息损失的根源。,在,JPEG,中采用线性均匀量化器，量化定义为对,67,个,DCT,系数除以量化步长，四舍五入取整。,量化的作用是在一定的主观保真度图像质量前提下，丢掉那些对视觉效果影响不大的信息。,67,68,例,:,给定,Lena,图像的一个平坦区域（,88,子块）如下：,给出DCT变换系数量化过程。,69,如下是它的,DCT,变换系数，可以看到能量集中在少数低频系数,:,660.1250 77.0796 25.9980 10.3993 7.8750 8.7866 5.6025 1.3176,17.3267 2.6779 5.2236 1.3237 0.5222 0.2917 0.2800 2.281,0.0280 0.6763 0.9575 0.9620 2.7730 1.9783 0.316 2.1771,2.3003 0.7572 2.2703 3.5559 1.2907 1.0027 0.1580 0.9777,2.3750 0.1038 3.2220 0.9653 1.3750 2.2258 0.3875 3.5236,0.9297 1.3282 2.7256 0.9828 1.9317 0.6972 0.1253 1.856,0.3973 2.6670 0.5669 3.7168 0.8891 1.6182 2.575 1.732,2.1666 1.7238 0.3335 0.7808 2.6253 0.9699 1.7857 1.183,70,用,JPEG的亮度量化矩阵式对每个系数进行均匀量化，量化器输出为：,71 7 3 1 0 0 0 0,1 0 0 0 0 0 0 0,0 0 0 0 0 0 0 0,0 0 0 0 0 0 0 0,0 0 0 0 0 0 0 0,0 0 0 0 0 0 0 0,0 0 0 0 0 0 0 0,0 0 0 0 0 0 0 0,71,反量化后，进行,DCT,反变换，得到的解码图像为：,80 75 71 72 78 85 89 90,80 75 71 72 78 85 89 90,80 76 72 73 79 86 90 91,81 77 72 77 80 87 91 92,82 77 73 77 81 87 91 93,83 78 77 75 81 88 92 93,83 79 75 76 82 89 93 97,87 79 75 76 82 89 93 97,72,88,子块的,64,个变换系数经量化后，按直流系数,DC,和交流系数,AC,分成两类处理。,坐标,u=v=0,的直流系数,DC,实质上就是空域图像中,67,个像素的平均值。,相邻的,88,子块之间的,DC,系数有强的相关性，,JPEG,对,DC,系数采用,DPCM,编码，即对相邻块之间的,DC,系数的差值,DIFF,DC,i,-DC,i-1,编码。,DC,j-2,DC,j-1,DC,j,DC,j+1,DC,j+2,73,其余,63,个系数称为交流系数（,AC,系数）采用行程编码。由于低频分量多呈圆环形辐射状向高频率衰减，因此可看成按,Z,字形衰减，如下图所示。因此，,AC,系数按,Z,字形扫描读数。,AC,0,DC,AC,0,AC,7,AC,7,74,对这,63,个,AC,系数采用非常简单和直观的行程编码，行程编码采用两个字节表示。,JPEG,使用,1,字节的高,4,位表示连续“,0”,的个数，而使用它的低四位来表示下一个非“,0”,系数所需要的位数，跟在它后面的是量化,AC,系数的数值。,AC,系数的行程编码如下图所示：,N,N,N,N,S,S,S,S,两个非零值间连续零个数,表示下一个非零值需要的比特数,第一个字节,下一个字节,(Run Length),(Size),下一个非零值的实际值,75,为了进一步达到压缩数据的目的，可以对,DPCM,编码后的,DC,码和,RLE,编码后的,AC,码的码字再作熵编码。,JPEG,建议使用两种熵编码方法：哈夫曼,(Huffman),编码和自适二进制算术编码。,熵编码可分成两步进行，首先把,DPCM,编码后的,DC,码,DC,系数和行程编码的,AC,系数转换成中间符号序列,然后给这些符号赋以变长码字。,76,例,JPEG,标准编码和解码,考虑下列,88,子图像，使用,JPEG,基本标准进行压缩和重构：,52 55 61 66 70 61 67 73,63 59 66 90 109 85 69 72,62 59 68 113 177 107 66 73,63 58 71 122 157 106 70 69,67 61 68 107 126 88 68 70,79 65 60 70 77 68 58 75,85 71 67 59 55 61 65 83,87 79 69 68 65 76 78 97,77,原图像包含,256,个可能的灰度级，因此，编码过程从对原子图像的像素层次移动,-128,或,128,个灰度级开始。得到的移住阵列为：,-76 -73 -67-62-58 -67-67-55,-65 -69 -62-38-19 -73-59-56,-66 -69 -60-15 16 -27-62-55,-65 -70 -57-6 26 -22-58-59,-61 -67 -60-27-2 -70-60-58,-79 -63 -68-58 -51-65-70-53,-73 -57 -67-69 -73-67-63-75,-71 -79 -59-60 -63-52-50-37,78,对,N=8,，正向,DCT,，变换的阵列为：,-715-29 -62 25 55-20-l 3,7-21-62 9 11-7-6 6,-76 8 77 -25-30 10 7 -5,-50 13 35 -15-9 6 0 3,11 -8 -13 -2 -1 1 -7 1,-10 1 3 -3 -1 0 2 -1,-7 -l 2 -l 2-3 1 2,-1 -1 -1 -2 -1-l 0-1,79,如果用,JPEG,推荐的标准化阵列对变换阵列进行量化，则进行按比例舍入后的系数是：,-26-3 6 2 2 0 0 0,1 -2-7 0 0 0 0 0,-3 1 5 -l-10 0 0,-7 1 2-10 0 0 0,1 0 0 0 0 0 0 0,0 0 0 0 0 0 0 0,0 0 0 0 0 0 0 0,0 0 0 0 0 0 0 0,80,变换和标准化处理过程产生了大量的零值系数。按,z,形模式对这些系数进行重新排列的时候，得到的一维系数序列是：,-26-3 1-3-2-6 2-7 1 7 1 1 5 0 2 0