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

数字图像处理学第5章图像编码（第四讲）5.6变换编码图像编码中另一类有效的方法是变换编码变换编码的通用模型如下图所示图542图像变换编码模型映射变换量化器编码器变换编码主要由映射变换、量化及编码几部分操作组成映射变换是把图像中的各个像素从一种空间变换到另一种空间，然后针对变换后的信号再进行量化与编码操作在接收端，首先对接收到的信号进行译码，然后再进行反变换以恢复原图像映射变换的关键在于能够产生一系列更加有效的系数，对这些系数进行编码所需的总比特数比对原始图像进行编码所需要的总比特数要少得多，因此，使数据率得以压缩映射变换的方法很多图像变换编码基本可分为两大类，某些特殊的映射变换编码法，函数变换编码法5.6.1几种特殊的映射变换编码法特殊映射变换编码法包括诸如行程编码，轮廓编码等一些变换编码方法它们特别适用于所谓二值图像的编码这类图像包括业务信件、公文、气象图、工程图、地图、指纹卡片及新闻报纸等当然在编码技术上同样可分为精确编码和近似编码两类 精确编码可以不引入任何畸变，在接收端可以从编码比特流中精确恢复出原始图像近似编码会引入一些畸变，但是，这种方法却可以在保证可用性的前提下获得较高的压缩比。

下面通过几种具体的编码方法说明这种变换编码法的基本概念1、一维行程编码一维行程编码的概念如图542所示假如沿着某一扫描行的像素为 ，它们所具有的灰度值可能为 在编码之前，可以首先把这些像素映射为成对序列 ， 和 其中表示某一灰度值，表示第i次运行的行程也可以说是连续取值为灰度值的像素的个数经过这样映射变换后就可以对编码，而不必对像素直接编码由于有些图像如前面提到的二值图像，连续取同一灰度级的像素很多，对映射后的序列进行编码会大大压缩比特率图542所示的例子可映射成表514所示的序列对在这个例子中有8级灰度，24个像素如果对编码，总的比特数至少要243=72bit如果对表514的序列对编码，灰度值用3位码，行程长度用4位码，每对参数用7位码，共4对，总比特数只要28bit就够了可见压缩率是很可观的表514序列对i1362510342486行程编码可分为行程终点编码和行程长度编码如果行程终点的位置由扫描行的开始点算起，并且由到达行程终点的像素计数来确定，就称为行程终点编码如果行程终点位置由这一终点与前一终点的相对距离确定，就称为行程长度编码对于二值图像来说采用行程长度编码，甚至不需要传送灰度信息。

假定某一扫描线含有3个白色像素，其后是2个黑色像素，接着又是10个白色像素这样，在行程长度编码中，只传送行程长度3、2和10就可以了每个行程长度告诉沿扫描线的下一个边界点的相对位置612二维行程编码二维行程编码也叫预测微分量化器(Predictive Differential Quantizer)，简称PDQ其基本算法如图543所示PDQ的基本算法是将图像元素阵列变换为整数对和的序列这里是相邻扫描行上行程的开始点之间的差图中是点和点的差是这相邻行行程的差对应于起始点的行程为 l1 ，对应于起点的行程为 l2 ，因此， l2 l1 是相邻扫描行上行程的开始点之间的差是这相邻行行程的差“开始”“消失” 另外，对于图中的暗面积还要有一个“开始”和“消失”的标记这样就把一幅图像的像素阵列按相继扫描行变换为、开始、消失四个参量的序列，然后便可对这四个参量来编码PDQ法利用了扫描线间的相关性，因此，它有更大的压缩潜力另外一种方法叫做双重增量编码（Double Delta coding），简称DDC它是对和进行编码而不是对和编码是前一扫描行的暗区后边界与相继扫描行暗区后边界的差实验证明，这种方法的压缩比较PDQ法更大。

是相邻扫描行上行程的开始点之间的差/是前一扫描行的暗区后边界与相继扫描行暗区后边界的差“开始”“消失”当在图像中有少数大的暗区时二维行程编码更有效，对于有许多小暗区的图像来说，一维行程编码更有效62正交变换编码变换编码中另一类方法是正交变换编码法（或称函数变换编码法）这种方法的基本原理是通过正交函数变换把图像从空间域转换为能量比较集中的变换域然后对变换系数进行编码，从而达到缩减比特率的目的621正交变换编码的基本概念正交变换编码的基本原理框图如图550所示编码器由预处理、正交变换、量化与编码几部分组成，译码器由译码、反变换及后处理组成在编码操作中，模拟图像信号首先送入预处理器，将模拟信号变为数字信号然后把数字信号分块进行正交变换，通过正交变换就使空间域信号变换到变换域然后对变换系数进行量化和编码在信道中传输或在存储器中存储的是这些变换系数的码字这就是编码端的处理过程在译码端，首先将收到的码字进行译码，然后进行反变换以使变换系数恢复为空间域样值，最后经过处理使数字信号变为模拟信号以供显示图550正交变换编码原理框图预处理正交变换量化编码传输、存储解码反变换后处理正交变换编码之所以能够压缩数据率，主要是它有如下一些性质：（）正交变换具有熵保持性质。

这说明通过正交变换并不丢失信息，因此，可以用传输变换系数来达到传送信息的目的正交变换有能量保持性质这就是第三章提到的各种正交变换的帕斯维尔能量保持性质它的意义在于：只有当有限离散空间域能量全部转移到某个有限离散变换域后，有限个空间取样才能完全由有限个变换系数对于基础矢量加权来恢复能量重新分配与集中这个性质使我们有可能采用熵压缩法来压缩数据也就是在质量允许的情况下，可舍弃一些能量较小的系数，或者对能量大的谱点分配较多的比特，对能量较小的谱点分配较少的比特，从而使数据率有较大的压缩去相关特性正交变换可以使高度相关的空间样值变为相关性很弱的变换系数换句话说，正交变换有可能使相关的空间域转变为不相关的变换域这样就使存在于相关性之中的多余度得以去除综上所述，由于正交变换的结果，相关图像的空间域可能变为能量保持、集中且为不相关的变换域如果用变换系数来代替空间样值编码传送时，只需对变换系数中能量比较集中的部分加以编码，这样就能使数字图像传输或存贮时所需的码率得到压缩622变换编码的数学模型分析正交变换编码的编码过程主要是在变换域上进行在这个基础上可以建立以下变换编码的数学模型设设一图图像信源为为一向量(595)变换后输出一向量(597)(596)取正交变换为T，那么X与Y之间的关系为由于T是正交矩阵，所以(598)这里I为单位矩阵，是T的转置，是T的逆。

反之也有(599)也就是说在编码端利用正变换得到Y，在译码端可用反变换来恢复X5100)如果在传输或存贮中只保留M个分量，MN，则可由Y的近似值来恢复X当然是X的近似值但是只要选取得当，仍可保证失真在允许的范围内显然，关键问题在于选取什么样的正交变换T，才能既得到最大的压缩率，又不造成严重的失真因此，有必要研究一下由正交变换得到Y的统计特性Y的统计特性中最为重要的是协方差矩阵下面讨论一下正交变换后得到的Y的协方差矩阵采用何种形式当然，X的统计特性可以测得5101)设图设图 像信号是维维向量X的协协方差矩阵阵式中 CX 是X的协方差矩阵， 是X的均值，E是求数学期望值5102)又设变换设变换 系数向量为为(5103)CY为Y的协方差矩阵，所以(5104)式中是Y的均值由正交变换变换 的定义义，有因此式(5105)说明，变换系数的协方差矩阵可以通过空间域图像的协方差矩阵的二维变换得到由此可以得出结论：(5105)即变换系数的协方差矩阵决定于变换矩阵T和空间域图像的协方差矩阵CX而CX是图像本身所固有的，因此，关键在于寻求合适的T我们希望的两个结果:1) 、如果 CY 是一个对角形矩阵，那就说明系数间的相关性完全解除了。

也就是说解除了包含在相关性中的冗余度，为无失真压缩编码打下了基础2)、还希望对角形矩阵中元素的能量尽量集中，以便使舍去若干系数后造成的误差不致于太大，这样，就为熵压缩编码提供了条件综上所述，变换编码要解决的关键问题是合理地寻求变换矩阵T3.最佳变换问题在研究各种变换矩阵T的过程中，自然要比较它们的优劣，因此，就有一个比较准则问题下面讨论最佳变换问题 最佳变换应满足的条件 1).能使变换系数之间的相关性全部解除； 2).能使变换系数之方差高度集中 显然， 第一个条件希望变换系数的协方差矩阵为对角形矩阵； 第二个条件希望对角形矩阵中对角线上的元素能量主要集中在前项上，这样就可以保证在去掉 N-M 项后的截尾误差尽量小最佳的准则则常用的准则则仍然是均方误误差准则则均方误误差由下式表示(5106)式中f(x,y)代表原始图像，g(x,y)为经编译码后的恢复图像均方误差准则就是要使最小最小的变换就是最佳变换均方误误差准则则下的最佳统计变换统计变换均方误误差准则则下的最佳统计变换统计变换 也叫K-L变换变换(Karhunen loeve Transform)设设T是一正交变换变换 矩阵阵(5107)这是一个矩阵，其中是一个维向量。

这个矩阵是正交的，因此显然(5108)另外,设设有一数据向量经经正交变换变换 后(5109)而(5110)这这里于是(5111)为了压缩数据，在恢复X时不取完整的N个Y分量，而是仅取M个分量，其中MN这样其中M个分量构成一个子集，即：用这M个分量去估计X，其余的用常量bi 来代替于是可得到(5112)这里是X 的估计X 的值与的误差为(513)设为均方误差，则(5114)将代入由上述的正交条件可简简化为为(5115)根据最小均方误差准则，要使最小就要正确选取及为了求得最佳的和，可分两步来求：第一步把对求导并令其等于零，即(5116)又因为所以将代入，则(5118)因为所以(5119)第二步求最佳化的为了求得最佳的，不仅要找出使最小，而且还要满足的条件因此，可用求条件极值的拉格朗日乘数法法则根据拉格朗日乘数法，在求的条件极值时做一个新的函数5120)(5122)(5121)对求导，并注意到所以(5123)即(5124)由线线性代数理论论可知(5125)显然，i 就是CX的特征根，就是CX的特征向量如CX是对称矩阵，就可找到一个变换T，使CY成为对角形矩阵如果图图像信源是一阶马阶马 尔可夫模型的话话，那么将是一个Toeplitz矩阵阵，即(5126)这是一个对称矩阵。

因此，通过正交变换可以使成为对角形矩阵也就是说可以找到一个变换矩阵T而得到最佳变换结果这就是K-L变换的核心)最佳变换的实现方法由上面的分析可见，K-L变换中的变换矩阵T不是一个固定的矩阵，它必须由信源来确定当给定一信源时，可用如下几个步骤求得T：；）给给定一幅图图像后，首先要统计统计 其协协方差矩阵阵CX）由CX求矩阵，即并且由求得其特征根，进而求得每一个特征根所对应的特征向量；）由特征向量求出变换矩阵T；）用求得的T对图像数据进行正交变换经过上面四步运算就可以保证在变换后使是一个对角形矩阵这个T就是K-L变换中的变换矩阵通过上面的讨论不难看出，图像不同, CX 就不同，因此T也就不同为了得到最佳变换，每送一幅图像就要重复上述四个步骤，找出T后再进行正交变换操作，所以运算相当繁琐，而且没有快速算法此外，K-L变换在数学推导上总能实现， 但用硬件实现就不那么容易了因此，K-L变换的实用性受到很大限制，一般多用来作变换性能的评价标准当然，寻求K-L变换的简洁算法也是许多人研究的课题下面举一个简单的例子说明K-L变换的具体实现方法例：已知某信源的协方差矩阵为 CX ， 求最佳变换矩阵T写出矩阵求得的特征向量所以其基础解系为(110)归归一化后为为同理时特征向量为时时特征向量为为由上面的结结果可求得T便是K-L变换的变换矩阵。

4. 准最佳变换最佳变换的性能固然好，但实现起来却不容易因此，在实践中更加受到重视的是一些所谓的准最佳变换什么是准最佳变换呢？最佳变换的核心在于经变换后能使CY成为对角形矩阵形式。