第五讲图像变换2离散余弦变换PPT课件

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五讲图像变换,2,离散余弦变换,1,2,3.2.1,离散余弦变换的定义,一维离散余弦变换的定义由下式表示,(3,74),(3,75),3,式中 是第 个余弦变换系数，是广义频率变量，；是时域,N,点序列，,一维,离散余弦反变换,由下式表示,(3,76),显然，式,(3,74),式,(3,75),和式,(3,76),构成了一维离散余弦变换对。,4,二维离散余弦变换,的定义由下式表示,(3,77),5,式,(3,77),是正变换公式。其中 是空间域二维向量之元素。，是变换系数阵列之元素。式中表示的阵列为,N N,6,二维离散余弦反变换,由下式表示,(3,78),7,8,9,10,余弦变换与傅里叶变换有什么关系？,11,式中的符号意义同正变换式一样。式,(3,77),和式,(3,78),是离散余弦变换的解析式定义。更为简洁的定义方法是采用矩阵式定义。如果令,N,4,，那么由一维解析式定义可得如下展开式,(3,79),12,写成矩阵式,(3,80),若定义 为变换矩阵，为变换系数矩阵，为时域数据矩阵，则一维离散余弦变换的矩阵定义式可写成如下形式,(3,81),13,同理，可得到反变换展开式,(3,82),写成矩阵式,14,即,(3,84),当然，二维离散余弦变换也可以写成矩阵式,(3,85),式中 是空间数据阵列，是变换系数阵列，是变换矩阵，是 的转置。,15,3.2.2,离散余弦变换的正交性,由一维,DCT,的定义可知,它的基向量是,(3,86),16,在高等数学中，切比雪夫多项式的定义为,(3,87),17,式中 是 和 的多项式。它的第,N,个多项式为,如果,那么,将此式代入,18,显然，这与一维,DCT,的基向量是一致的。因为切比雪夫多项式是正交的，所以,DCT,也是正交的。另外，离散余弦变换的正交性也可以通过实例看出。如前所示，当,N,时，,(3,88),则,19,显然,这是满足正交条件的。从上述讨论可见，离散余弦变换是一类正交变换。,20,3.2.3,离散余弦变换的计算,与傅里叶变换一样，离散余弦变换自然可以由定义式出发进行计算。但这样的计算量太大，在实际应用中很不方便。所以也要寻求一种快速算法。,首先，从定义出发，作如下推导,21,(389),22,式中 是取其实部的意思。如果把时域数据向量作下列延拓，即：,(3,90),则 的离散余弦变换可写成下式,23,(3,91),24,由式,(3,91),可见,是,2N,点的离散傅里叶变换。所以，在作离散余弦变换时，可以把序列长度延拓为,2N,，然后作离散傅里叶变换，产生的结果取其实部便可得到余弦变换。,25,同样道理，在作反变换时，首先在变换空间，把 作如下下延拓,(3,92),那么，反变换也可用式,(3,93),表示,26,(3,93),27,由式,(393),可见，离散余弦反变换可以从,的,2N,点反傅里叶变换实现。,28,3.3,离散,K-L,变换,又称为霍特林,(Hotelling),变换,KL(Karhunen-Loeve),或,DKT,以图像的统计性质为基础的,变换核矩阵,由图像阵列的协方差矩阵的,特征值和特征向量,所决定又称为特征向量变换,29,当变量之间存在一定的相关关系时，可以通过原始变量的线性组合，构成数目较少的不相关的新变量代替原始变量，而每个新变量都含有尽量多的原始变量的信息。这种处理问题的方法，叫做主成分分析，新变量叫做原始变量的主成分。,目的是寻找任意统计分布的数据集合之主要分量的子集。相应的基向量组满足正交性且由它定义的子空间最优地考虑了数据的相关性。将原始数据集合变换到主分量空间使单一数据样本的互相关性,(cross-correlation),降低到最低点。,30,图像协方差矩阵,假设对某幅,NN,的图像,f(x,y),，在某个传输通道上传输了,M,次，因会受到各种因素的随机干扰，接收到是一个图像集合,将,M,次传送的图像集合写成,M,个,N,2,维向量,X,1,X,2,X,i,X,M,生成向量的方法可以采用行堆叠或列堆叠的方法，对第,i,次获得的图像,f,i,(x,y),，可用,N,2,维向量,X,i,表示：,31,问题是：如何选取一个合适的正交变换,A,，使得变换后的图像,Y=AX,1),是具有,MN,2,个分量的向量,2),由,Y,经反变换而恢复的,(,向量,X,的估值,),和原始图像具有最小的均方误差，即,称满足这两个条件的正交变换,A,为,K-L,变换。如果能找到这样一个变换，那么就意味着经过一个变换，不仅删除了,N,2,-M,个分量，并且由变换结果,Y,重新恢复的图像,是有效的过滤了随机干扰的原图像的最佳逼近。,32,X,向量的协方差矩阵,C,X,定义为,设,e,i,和,i,是协方差矩阵,C,X,对应的特征向量和特征值，将特征值按减序排列，即,则,K-L,变换核矩阵,A,的行用,C,X,的特征值,i,所对应的特征向量,e,i,构成：,33,直接求矩阵,C,X,的特征值和特征向量很困难。这是因为,C,X,是,N,2,N,2,维矩阵，尽管图像的大小,N,可能不是很大的，但,N,2,却是很大的数据。这样求其特征向量和特征值速度较慢。但如果样本图象个数,M,不太多，可以先计算出,MM,维方阵,L,A,T,A,的特征值,k,和特征向量,v,k,左乘矩阵,A,，则有,是矩阵,C,X,的 特征向量,可以选择,P(PM),个较大特征值对应的特征向量（主成分），构造新的,P,维主成分空间,Q,因为,C,X,是实对称矩阵，总能找到一个标准正交的特征向量集合，使,A,-1,=A,T,，那么可得,K-L,反变换为,34,K-L,变换的性质和特点,（,1,）,Y,的平均值向量,m,y,0,，即为零向量,0,（,2,）,Y,向量的协方差,35,（,3,）对角性,对角线上的元素是原始图像向量的协方差矩阵,C,X,对应的特征值,i,，它也是,Y,向量的方差。而非对角线上的元素值为,0,，说明,Y,向量中各元素之间相关性小，而,C,X,的非对角线上元素不为,0,，说明原始图像元素之间相关性强，这就是采用,K-L,变换进行编码，数据压缩比大的原因,显然,K-L,坐标系将矩阵,C,X,对角化了，换句话说，通过,K-L,变换，消除了原有向量,X,的各分量之间的相关性，从而可能去掉那些带有较少信息的坐标轴，以达到降低特征空间维数的目的。,36,X1,X2,e 1,e 2,在原来坐标系中，要用两个分量,X1,X2,来表示各个样本，而在,K-L,坐标系中，只要用,e1,就可以，去掉,e2,并不会带来很大的误差,假设矩阵,C,X,只有少数几个数值大的特征值，而其余的特征值数值很小，,K-L,坐标系就可以有效的进行信息压缩,37,K-L,变换的最大优点是去相关性好，可用于数据压缩和图像旋转,主要困难是由于协方差矩阵,C,X,求特征值,和特征向量解方程的计算量大，同时,K-L,变换是非分离的，二维不可分，一般情况下，,K-L,变换没有快速算法,38,实例,以,K-L,变换进行自动的人脸识别为例说明,我们把一幅数字图像看成一个矩阵或一个数组，用,B(i,j),或,bij,表示，,一,幅,NN,大小的人脸图像按列相连构成一个,N,2,维矢量,x=(b11 b21bN1 b12b22bN2 b1N b2NbNN),它可视为,N,2,维空间中的一个点，假设,N=128,。由于人脸,结构的相似性,，当把很多这样的人脸图像归一化之后，这些图像在这一超高维空间中,不是随机或散乱分布,的，而是存在,某种规律,，因此可以通过,K-L,变换用一个,低维子空间描述人脸图像,，同时又能保存所需要的识别信息,39,图像的归一化,对于一个全自动的人脸识别系统，其首要的工作是人脸,图像的分割以及主要器官的定位,。另外，由于,K-L,变换本质上依赖于,图像灰度在空间分布上的相关性,，因此还需要对人脸图像进行一系列的预处理，以达到位置校准和灰度归一化的目的,假设已根据分割及定位算法，得到了人脸正面图像,左右两眼中心的位置，并分别记为,Er,和,El,，则可通过下述步骤达到图像校准的目的,40,1,、进行,图像旋转,，以使,Er,和,El,的,连线,ErEl,保持水平,。这保证了人脸,方向的一致性,，体现了人脸在图像平面内的,旋转不变性,2,、根据图所示的比例关系，进行图像裁剪。图中，,O,点为,ErEl,的中点，且,d=ErEl,。经过裁剪，在,2d2d,的图像内，可保证,O,点固定于,(0.5d,d),处。这保证了人脸,位置的一致性,，体现了人脸在图像平面内的,平移不变性,3,、进行图像缩小和放大变换，得到统一大小的标准图像，规定标准图像的大小为,128128,象素点，则缩放倍数为,=2d/128,。这使得,d=ErEl,为定长,(64,个象素点,),，即保证了人脸,大小的一致性，体现了人脸在图像平面内的尺度不变性,41,经过校准，不仅在一定程度上获得了人脸表示的几何不变性，而且还基本上消除了头发和背景的干扰。,完成了旋转、平移和尺度不变性后，需要对校准的图像做灰度拉伸，以改善图像的对比度，然后采用直方图修正技术使图像具有统一的均值和方差，一部分消除光照强度的影响,假设人脸数据库中，由,20,人，每人,10,幅人脸图像,42,K-L,变换,以归一化后的标准图像做为训练样本集，以该样本集的总体散布矩阵为协方差矩阵，即,xi,为第,i,个训练样本的图像向量，,为训练样本集的平均图像，,M,为训练样本的总数,为了,N,2,N,2,维矩阵的特征值和正交归一的特征向量，直接计算是困难的，因此引入一个定理，奇异值分解,SVD,43,设,A,是一秩为,r,的,nr,维矩阵，则存在两个正交矩阵：,以及对角阵,满足,其中,i,为矩阵,AA,T,和,A,T,A,的非,0,特征值，,u,和,v,分别为,AA,T,和,A,T,A,对应于,i,的特征向量，上述分解称为矩阵,A,地奇异值分解，,为,A,的奇异值,推论,44,由于可表示为：,故，构造矩阵：,容易求其特征值,i,及相应的正交归一特征向量,vi(i=0,1,2M-1),。由推论可知，的正交归一化特征向量,ui,为,这就是图像的特征向量，它是通过计算较低维矩阵,R,的特征值与特征向量而间接求出的,45,将特征值从大到小排序：,0 1 r-1,，其对应的特征向量为,u,i,。这样，每一幅人脸图像都可以投影到由,u,0,u,1,u,M-1,张成的子空间中。因此每一幅人脸图像对应于子空间中的一个点，同样，子空间中的任一点也对应于一幅图像,46,特征脸,