数字图像处理：第5章 图像编码（第三讲）.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数字图像处理,第,5,章 图像编码,（,第三讲）,5.6,变换编码,图像编码中另一类有效的方法是变换编码。变换编码的通用模型如下图所示,图,542,图像变换编码模型,映射变换,量化器,编码器,图,542,图像变换解码模型,映射变换,解码器,变换编码主要由映射变换、量化及编码几部分操作组成。映射变换是把图像中的各个像素从一种空间变换到另一种空间，然后针对变换后的信号再进行量化与编码操作。在接收端，首先对接收到的信号进行译码，然后再进行反变换以恢复原图像。,映射变换的关键在于能够产生一系列更加有效的系数，对这些系数进行编码所需的总比特数比对原始图像进行编码所需要的总比特数要少得多，因此，使数据率得以压缩。,映射变换的方法很多。图像变换编码基本可分为两大类，,某些特殊的映射变换编码法，,函数变换编码法。,5.,6.1,几种特殊的映射变换编码法,特殊映射变换编码法包括诸如行程编码，轮廓编码等一些变换编码方法。它们特别适用于所谓二值图像的编码。这类图像包括业务信件、公文、气象图、工程图、地图、指纹卡片及新闻报纸等。当然在编码技术上同样可分为精确编码和近似编码两类。,精确编码可以不引入任何畸变，在接收端可以从编码比特流中精确恢复出原始图像。近似编码会引入一些畸变，但是，这种方法却可以在保证可用性的前提下获得较高的压缩比。下面通过几种具体的编码方法说明这种变换编码法的基本概念。,1、,一维行程编码,一维行程编码的概念如图,5,42,所示。,假如沿着某一扫描行的像素为 ，它们所具有的灰度值可能为 。在编码之前，可以首先把这些像素映射为成对序列 ，和 。,其中 表示某一灰度值，表示第,i,次运行的行程。也可以说是连续取值为 灰度值的像素的个数。经过这样映射变换后就可以对,编码，而不必对像素直接编码。,由于有些图像如前面提到的二值图像，连续取同一灰度级的像素很多，对映射后的序列进行编码会大大压缩比特率。,图,5,42,所示的例子可映射成表,5,14,所示的序列对。在这个例子中有,8,级灰度，,24,个像素。如果对 直接编码，总的比特数至少要,24,3=72bit,。,如果对表,5,14,的序列对编码，灰度值用,3,位码，行程长度用,4,位码，每对参数用,7,位码，共,4,对，总比特数只要,28bit,就够了。可见压缩率是很可观的。,表,5,14,序列对,i,1,3 6,2,5 10,3,4 2,4,8 6,行程编码可分为,行程终点编码,和,行程长度编码,。如果行程终点的位置由扫描行的开始点算起，并且由到达行程终点的像素计数来确定，就称为行程终点编码。如果行程终点位置由这一终点与前一终点的相对距离确定，就称为行程长度编码。,对于二值图像来说采用行程长度编码，甚至不需要传送灰度信息。假定某一扫描线含有,3,个白色像素，其后是,2,个黑色像素，接着又是,10,个白色像素。这样，在行程长度编码中，只传送行程长度,3,、,2,和,10,就可以了。每个行程长度告诉沿扫描线的下一个边界点的相对位置。,6,1,2,二维行程编码,二维行程编码也叫预测微分量化器,(,Predictive Differential,Quantizer,),，简称,PDQ,。其基本算法如图,543,所示。,PDQ,的基本算法是将图像元素阵列变换为整数对,和,的序列。这里,是相邻扫描行上行程的开始点之间的差。图中,是点和点的差。,是这相邻行行程的差。对应于起始点的行程为,l,1,，对应于起点的行程为,l,2,，因此，,l,2,l,1,。,是相邻扫描行上行程的开始点之间的差,是这相邻行,行程的差,“开始”,“消失”,另外，对于图中的暗面积还要有一个“开始”和“消失”的标记。这样就,把一幅图像的像素阵列按相继扫描行变换为,、,、开始、消失四个参量的序列,，然后便可对这四个参量来编码。,PDQ,法利用了扫描线间的相关性，因此，它有更大的压缩潜力。,另外一种方法叫做双重增量编码,（,Double Delta coding,）,，简称,DDC,。它是对,和 进行编码而不是对,和,编码。是前一扫描行的暗区后边界与相继扫描行暗区后边界的差。实验证明，这种方法的压缩比较,PDQ,法更大。,是相邻扫描行上行程的开始点之间的差,/,是前一扫描行的暗区后边界与相继扫描行暗区后边界的差,“开始”,“消失”,当在图像中有少数大的暗区时二维行程编码更有效，对于有许多小暗区的图像来说，一维行程编码更有效。,6,2,正交变换编码,变换编码中另一类方法是正交变换编码法（或称函数变换编码法）。这种方法的基本原理是通过正交函数变换把图像从空间域转换为能量比较集中的变换域。然后对变换系数进行编码，从而达到缩减比特率的目的。,6,2,1,正交变换编码的基本概念,正交变换编码的基本原理框图如图,550,所示。编码器由预处理、正交变换、量化与编码几部分组成，译码器由译码、反变换及后处理组成。,在编码操作中，模拟图像信号首先送入预处理器，将模拟信号变为数字信号。然后把数字信号分块进行正交变换，通过正交变换就使空间域信号变换到变换域。然后对变换系数进行量化和编码。,在信道中传输或在存储器中存储的是这些变换系数的码字。这就是编码端的处理过程。在译码端，首先将收到的码字进行译码，然后进行反变换以使变换系数恢复为空间域样值，最后经过处理使数字信号变为模拟信号以供显示,。,图,550,正交变换编码原理框图,预处理,正交变换,量化编码,传输、存储,解码,反变换,后处理,正交变换编码之所以能够压缩数据率，主要是它有如下一些性质：,（）,正交变换具有熵保持性质。,这说明通过正交变换并不丢失信息，因此，可以用传输变换系数来达到传送信息的目的。,（）,正交变换有能量保持性质。,这就是第三章提到的各种正交变换的帕斯维尔能量保持性质。它的意义在于：只有当有限离散空间域能量全部转移到某个有限离散变换域后，有限个空间取样才能完全由有限个变换系数对于基础矢量加权来恢复。,（）,能量重新分配与集中。,这个性质使我们有可能采用熵压缩法来压缩数据。也就是在质量允许的情况下，可舍弃一些能量较小的系数，或者对能量大的谱点分配较多的比特，对能量较小的谱点分配较少的比特，从而使数据率有较大的压缩。,（）,去相关特性。,正交变换可以使高度相关的空间样值变为相关性很弱的变换系数。换句话说，正交变换有可能使相关的空间域转变为不相关的变换域。这样就使存在于相关性之中的多余度得以去除。,综上所述，由于正交变换的结果，相关图像的空间域可能变为能量保持、集中且为不相关的变换域。如果用变换系数来代替空间样值编码传送时，只需对变换系数中能量比较集中的部分加以编码，这样就能使数字图像传输或存贮时所需的码率得到压缩。,6,2,2,变换编码的数学模型分析,正交变换编码的编码过程主要是在变换域上进行。在这个基础上可以建立以下变换编码的数学模型。,设一图像信源为一向量,(5,95),变换后输出一向量,(5,97),(5,96),取正交变换为,T,，那么,X,与,Y,之间的关系为,由于,T,是正交矩阵，所以,(5,98),这里,I,为单位矩阵，是,T,的转置，是,T,的逆。反之也有,(5,99),也就是说在编码端利用正变换得到,Y,，在译码端可用反变换来恢复,X,。,(5,100),如果在传输或存贮中只保留,M,个分量，,MN,，则可由,Y,的近似值 来恢复,X,。,当然 是,X,的近似值。但是只要选取得当，仍可保证失真在允许的范围内。,显然，关键问题在于选取什么样的正交变换,T,，才能既得到最大的压缩率，又不造成严重的失真。,因此，有必要研究一下由正交变换得到,Y,的统计特性。,Y,的统计特性中最为重要的是,协方差矩阵,。下面讨论一下正交变换后得到的,Y,的协方差矩阵采用何种形式。,当然，,X,的统计特性可以测得。,(5,101),设图像信号是维向量,X,的协方差矩阵,式中,C,X,是,X,的协方差矩阵，是,X,的均值，,E,是求数学期望值。,(5,102),又设变换系数向量为,(5,103),C,Y,为,Y,的协方差矩阵，所以,(5,104),式中,是,Y,的均值。,由正交变换的定义，有,因此,式,(5,105),说明，变换系数的协方差矩阵可以通过空间域图像的协方差矩阵的二维变换得到。由此可以得出结论：,(5,105),即,变换系数的协方差矩阵决定于变换矩阵,T,和空间域图像的协方差矩阵,C,X,。,而,C,X,是图像本身所固有的，因此，关键在于寻求合适的,T,。,我们希望的两个结果,:,1),、,如果,C,Y,是一个对角形矩阵，那就说明系数间的相关性完全解除了。也就是说解除了包含在相关性中的冗余度，为无失真压缩编码打下了基础。,2),、,还希望对角形矩阵中元素的能量尽量集中，以便使舍去若干系数后造成的误差不致于太大，这样，就为熵压缩编码提供了条件。综上所述，变换编码要解决的关键问题是合理地寻求变换矩阵,T,。,&,3.,最佳变换问题,在研究各种变换矩阵,T,的过程中，自然要比较它们的优劣，因此，就有一个比较准则问题。下面讨论最佳变换问题。,（）最佳变换应满足的条件,1).能使变换系数之间的相关性全部解除；,2).能使变换系数之方差高度集中。,显然，,第一个条件希望变换系数的协方差矩阵为对角形矩阵；,第二个条件希望对角形矩阵中对角线上的元素能量主要集中在前,项上，这样就可以保证在去掉,N-M,项后的截尾误差尽量小。,（）,最佳的准则,常用的准则仍然是均方误差准则。均方误差由下式表示,(5,106),式中,f,(,x,y,),代表原始图像，,g,(,x,y,),为经编译码后的恢复图像。均方误差准则就是要使 最小。,最小的变换就是最佳变换。,（）,均方误差准则下的最佳统计变换,均方误差准则下的最佳统计变换也叫,K-L,变换,(,Karhunen,loeve,Transform,),。,设,T,是一正交变换矩阵,(5,107),这是一个,矩阵，其中,是一个,维向量。这个矩阵是正交的，因此,显然,(5,108),另外,设有一数据向量,经正交变换后,(5,109),而,(5,110),这里,于是,(5,111),为了压缩数据，在恢复,X,时不取完整的,N,个,Y,分量，而是仅取,M,个分量，其中,M,N,。这样其中,M,个分量构成一个子集，即,：,用这,M,个分量去估计,X,，其余的用常量,b,i,来代替。于是可得到,(5,112),这里 是,X,的估计。,X,的值与 的误差为,(5,13),设 为均方误差，则,(5114),将 代入,由上述的正交条件可简化为,(5115),根据最小均方误差准则，要使 最小就要正确选取 及 。为了求得最佳的 和 ，可分两步来求：,第一步把 对 求导并令其等于零，即,(5116),又因为,所以,将,代入,，,则,(5,118),因为,所以,(5,119),第二步求最佳化的 。为了求得最佳的 ，不仅要找出 使 最小，而且还要满足 的条件。因此，可用求条件极值的拉格朗日乘数法法则。根据拉格朗日乘数法，在求 的条件极值时做一个新的函数 。,(5120),(5,122),(5121),对 求导，并注意到,所以,(5123),即,(5124),由线性代数理论可知,(5,125),显然，,i,就是,C,X,的特征根，就是,C,X,的特征向量。如,C,X,是对称矩阵，就可找到一个变换,T,，使,C,Y,成为对角形矩阵。,如果图像信源是一阶马尔可夫模型的话，,那么 将是一个,Toeplitz,矩阵，即,(5126),这是一个对称矩阵。因此，通过正交变换可以使 成为对角形矩阵。也就是说可以找到一个变换矩阵,T,而得到最佳变换结果。这就是,K-L,变换的核心。,(,),最佳变换的实现方法,由上面的分析可见，,K-L,变换中的变换矩阵,T,不是一个固定的矩阵，它必须由信源来确定。当给定一信源时，可用如下几个步骤求得,T,：,）给定一幅图像后，首先要统计其协方差矩阵,C,X,）由,C,X,求 矩阵，即 。并且由 求得其特征根，进而求得每一个特征根所对应的特征向量；,）由特征向量求出变换矩阵,T,；,）用求得的,T,对图像数据进行正交变换。,经过上面四步运算就可以保证在变换后使,是一个对角形矩阵。这个,T,就是,K-L,变换中的变换矩阵。,通过上面的讨论不难看出，图像不同,C,X,就不同，因此,T,也就不同。为了得到最佳变换，每送一幅图像就要重复上述四个步骤，找出,T,后再进行正交变换操作，所以运算相当繁琐，而且没有快速算法。此外，,K-L,变换在数学推导上总能实现，,但用硬件实现就不那么容易了。因此，,K-L,变换的实用性受到很大限制，一般多用来作变换性能的评价标准。当然，寻求,K-L,变换的简洁算法也是许多人研究的课题。下面举一个简单的例子说明,K-L,变换的具体实现方法。,例：已知某信源的协方差矩阵为,C,X,，,求最佳变换矩阵,T,。,写出,矩阵,求得,的特征向量,所以其基础解系为,(1 1 0),归一化后为,同理,时特征向量为,时特征向量为,由上面的结果可求得,T,便是,K-L,变换的变换矩阵。,4.,准最佳变换,最佳变换的性能固然好，但实现起来却不容易。因此，在实践中更加受到重视的是一些所谓的准最佳变换。,什么是准最佳变换呢？最佳变换的核心在于经变换后能使,C,Y,成为对角形矩阵形式。如果能找到某些固定的变换矩阵,T,，使变换后的,C,Y,接近于对角形矩阵，那也是比较理想的了。,在线性代数理论中知道，任何矩阵都可以相似于一个约旦形矩阵，这个约旦形矩阵就是准对角形矩阵，其形状如式,(5127),所示。,(5127),其主对角线上是特征值，在下对角线上仅有若干个，这也就比较理想了。从相似变换理论可知，总可以找到一个非奇异矩阵,，使得,(5128),而且这个,T,并不是唯一的。,在第三章讨论过的五种正交变换都具有,T,的性质。这五种正交变换就是常用的准最佳变换。尽管它们的性能比,K-L,变换稍差，但是，由于它们的变换矩阵,T,是固定的，这给工程实现带来了极大的方便。因此，首先付诸于实用的是这些准最佳变换法。,5.,各种准最佳变换的性能比较,从运算量大小以及压缩效果这两个方面来比较各种正交变换，其性能比较如表,5,16,所示。,6.编码,变换为压缩数据创造了条件，压缩数据还要靠编码来实现。通常所用的编码方法有二种，,一是区域编码法，,二是门限编码法。,（1）,区域编码法,这种方法的关键在于选出能量集中的区域。例如，正交变换后变换域中的能量多半集中在低频率（或列率）空间上，在编码过程中就可以选取这一区域的系数进行编码传送，而其他区域的系数可以舍弃不用。在译码端可以对舍弃的系数进行补零处理。这样由于保持了大部分图像能量，在恢复图像中带来的质量劣化并不显著。,在区域编码中，区域抽样和区域编码的均方误差均与方块尺度有关。图,552,示出了图像变换区域抽样的均方误差与方块尺度的关系。图,553,则示出了图像区域编码,均方误差与方块尺度,的关系。,图,552,图像变换区域抽样的均方误差,与方块尺度的关系,553,图像区域编码均方误差,与方块尺度的关系,区域编码的显著缺点是一旦选定了某个区域就固定不变了，有时图像中的能量也会在其他区域集中较大的数值，舍掉它们会造成图像质量较大的损失。,（,2）门限编码,这种采样方法不同于区域编码法，它不是选择固定的区域，而是事先设定一个门限值,T,。如果系数超过,T,值，就保留下来并且进行编码传送。如果系数值小于,值就舍弃不用。这种方法有一定的自适应能力。它可以得到较区域编码为好的图像质量。但是，这种方法也有一定的缺点，那就是超过门限值的系数的位置是随机的。,因此，在编码中除对系数值编码外，还要有位置码。这两种码同时传送才能在接收端正确恢复图像。所以，其压缩比有时会有所下降。一种简单实用的位置编码技术是对有效样本之间的无效样本数目编码。,图像编码的国际标准,在图像编码中，目前的国际标准是：,、静止图像:,JPEG(Joint Photographic Expert Group)：,“,联合图片专家组,”,1991年提出的,ISO CD 10916,建议草案。,这个建议规定了具体的编码方法及质量要求，即:,DCT+Huffman,编码 （基本）；,自适应算术编码（扩展）；,无失真预测，帧内预测及,Huffman；,、可视电话会议电视：,*,CCITT H.261,标准，1988年提出,P,64Kbit/s。P,为可变系数，对于可视电话，建议,P=2，,会议电视建议,P6。,编码方法可采用混合编码法，即采用,DCT,变换，运动补偿,DPCM,及,Huffman,编码等方法。,、,MPEG(Motion Picture Expert Group,运动图像专家组),CCITT,的,ISO CD 11172,号建议，,MPEG1,指标是压缩一次群(1.5,Mb/s-2Mb/s)，,采用,DCT、,运动补偿、帧内、帧间预测等方法。,到,MPEG1、MPEG2、MPEG4、MPEG7,等,