1、第3章 图像变换,傅立叶变换(FFT)离散余弦变换(DCT)K-L变换小波变换,问题的提出,为达到某种目的将原始图象变换映射到另一个空间上，使得图象的某些特征得以突出，以便于后面的处理和识别。一般变换后的图象，大部分能量都分布于低频谱段，这对以后图象的压缩、传输都比较有利。使得运算次数减少，节省时间,傅立叶变换FFT,线性系统,对于一般线性系统，往往是用时间作为参数来描述的，表示为一维(t)系统。在图像处理中是用空间作为参数来描述的，通常表示为二维(x,y)系统。输入函数f(x,y)表示原始图像，输出函数g(x,y)表示经处理后的图像，线性系统可看作是一种映射，它反映了各种线性的图像处理方法，
2、其输入和输出的关系表示为：,二维线性系统,叠加原理,点源和狄拉克函数,一幅图像可以看成由无穷多极小的象素组成，每一个象素都可以看作为一个点源，因此，一幅图像也可以看成由无穷多点源所组成 数学上，点源可以用狄拉克函数来表示，二维函数定义为 满足,狄拉克函数性质,(1) 函数为偶函数，即,(2)位移性,或用卷积符号*表示为,(3)可分性,(4)乘积性,(5)筛选性,当且仅当0时,(6)指数函数,卷积,假设f(x)(x=0,1,A-1)以及g(x)(x=0,1,C-1)是两个有限离散函数，其线性卷积为,对于图像二维函数的卷积，则,相关,2个函数的相关定义为,其中f*(i)为f(i)的复共轭,一维连续
3、傅立叶变换,定义及基本概念,设f(x)为x的函数，如果f(x)满足下面的狄里赫莱条件：,（1）具有有限个间断点（2）具有有限个极值点（3）绝对可积,则有下列式成立：,x为时域变量，u为频域变量,(1),(2),如果令w2u，则有,称为傅立叶变换对,函数f(x)的傅立叶变换一般是一个复量，它可以用下式表示：,实例,傅立叶变换,其相位为,傅立叶谱,周期函数的傅立叶变换,傅立叶级数来表示,结论,1、只要满足一定条件，连续函数就可以进行傅立叶变换，实际上这个条件在工程应用中很容易满足。2、连续非周期函数的傅立叶谱是连续的非周期函数，连续的周期函数的傅立叶谱是离散的非周期函数。,二维连续傅立叶变换,如果
4、二维函数f(x,y)满足狄里赫莱条件，则将有下面的傅立叶变换对存在：,与一维傅立叶变换类似，二维傅立叶变换的傅立叶谱和相位谱为：,例：求如图所示的函数的傅立叶谱,f(x,y)函数,其傅立叶变换为：,其傅立叶谱为：,离散傅立叶变换,由于实际问题的时间或空间函数的区间是有限的，或者是频谱有截止频率 离散傅立叶变换(Discrete Fourier Transform简称DFT)在数字信号处理和数字图像处理中应用十分广泛，它建立了离散时域和离散频域之间的联系,一维离散傅立叶变换,二维离散傅立叶变换,由于图像的频率是表征图像中灰度变化剧烈程度的指标，是灰度在平面空间上的梯度。如：大面积的沙漠在图像中是
5、一片灰度变化缓慢的区域，对应的频率值很低；而对于地表属性变换剧烈的边缘区域在图像中是一片灰度变化剧烈的区域，对应的频率值较高。傅立叶变换在实际中的物理意义，设f是一个能量有限的模拟信号，则其傅立叶变换就表示f的谱。从纯粹的数学意义上看，傅立叶变换是将一个函数转换为一系列周期函数来处理的。从物理效果看，傅立叶变换是将图像从空间域转换到频率域，其逆变换是将图像从频率域转换到空间域。换句话说，傅立叶变换的物理意义是将图像的灰度分布函数变换为图像的频率分布函数，傅立叶逆变换是将图像的频率分布函数变换为灰度分布函数。,一个MN大小的二维函数f(x,y)，其离散傅立叶变换对为,在数字图像处理中，图像一般取
6、样为方形矩阵，即NN，则其傅立叶变换及其逆变换为,（1）可分性,从上式可以看出，一个二维傅立叶变换可用二次一维傅立叶变换来实现,傅立叶变换的性质,其意义：一个二维傅立叶变换或反变换都可以分解为二步进行，其中每一步都是一个一维傅立叶变换或反变换,行变换,列变换,二维傅立叶变换分离成两个一维变换,（2）平移性,在空域中，图像原点平移到(x0，y0)时，其对应的频谱F(u,v)要乘上一个负的指数项,在频域中，原点平移到(u0，v0)时，其对应的f(x,y)要乘上一个正的指数项,也就是说，当空域中f(x,y)产生移动时，在频域中只发生相移，而傅立叶变换的幅值不变,反之，当频域中F(u,v)产生移动时，
7、相应的f(x,y)在空域中也只发生相移，而幅值不变,平移,（3）周期性和共轭对程性,周期性可表示为,该式表明，如果空间域函数f(x,y)旋转0角度后，相应的傅立叶变换F(u,v)在频域中也旋转同一0角，反之，F(u,v)在频域中旋转0角，其反变换f(x,y)在空间域中也旋转0角,（5）分配性和比例性,傅立叶变换的分配性表明，傅立叶变换和反变换对于加法可以分配，而对乘法则不行，即,傅立叶变换的比例性表明，对于二个标量a和b，有,在空间比例尺度的展宽，相应于频域中比例尺度的压缩，其幅值也减少为原来的,（6）平均值性质,定义二维离散函数的平均值为,将u=v=0代入二维离散傅立叶公式，可得,比较上面两
8、式，可看出,（7）卷积定理,卷积定理和相关定理都是研究两个函数的傅立叶变换之间的关系，这构成了空间域和频域之间的基本关系,对于两个二维连续函数f(x,y)和g(x,y)的卷积定义为,指出傅立叶变换一个主要好处：与其在一个域中作不直观的，和难懂的卷积，不如在另外一个域中作乘法，可以达到相同的效果,它表明两个二维连续函数在空间域中的卷积可用求其相应的两个傅立叶变换乘积的逆变换而得。 反之，在频域中的卷积可用空间域中乘积的傅立叶变换而得，应用卷积定理明显的好处是避免了直接计算卷积的麻烦，它只需要先算出各自的频谱，然后相乘，再求其逆变换，即可得到卷积。,离散傅立叶变换和逆变换都是周期函数，为了防止卷积
9、后产生交叠误差，需要对离散的二维函数的定义域加以扩展。利用一维函数来说明函数定义域的扩展，设f(x)(x=0,1. A-1)和g(x)(x=0,1,.C-1)是两个有限的离散函数，也就是说f(x)定义域为0xA-1，g(x)的定义域为0xC-1。则其线性卷积为,如果利用卷积定理来计算该卷积，则相当于把f(x)和g(x)分别以A和C为周期进行周期延拓，因此，将上式改写为(一个周期) 求得结果将不是需要的z(x)，而是周期循环的,为了避免循环卷积，可以对原被卷积函数补零。由于卷积结果的长度为N=A+C-1，因此，可以把两个被卷积的函数的长度扩展到N，并在原函数定义区间外的部分补零，即取,同样地，二
10、维离散卷积计算时，也必须对被卷积函数进行延拓和补零，如果被卷积函数f(x,y)和g(x,y)地大小分别为AB和CD，则延拓后地函数为：,（8）相关定理,对于二维连续函数f(x,y)和g(x,y)的相关定义为,相关定理可表示为,在离散情况下，与离散卷积一样，需要用增补零的方法扩充f(x,y)和g(x,y)为fe(x,y)和ge(x,y)，并根据卷积定理相类似的方法来选取M和N，以避免在相关函数周期内产生交叠误差。,快速傅立叶变换(FFT),离散傅立叶变换已成为数字信号处理的重要工具，然而，它的计算量达，运算时间长，在某种程度上却限制了它的使用范围。快速算法大大提高了运算速度，在某些应用场合已能作
11、实时处理，并且应用在控制系统中快速傅立叶变换不是一种新的变换，它是离散傅立叶变换的一种算法，它是在分析离散傅立叶变换中的多余运算的基础上，进而消除这些重复工作的思想指导下得到的,其原理：,对于一个有限长序列f(x)(0x N-1)，它的傅立叶变换由下式表示：,令,将正变换(1)展开得到：,矩阵表示为：,从上式可以看出，要得到每一个频率分量，需进行N次乘法和N-1次加法运算。要完成整个变换需要N2次乘法和N(N-1)次加法运算。当序列较长时，必然要花费大量的时间,观察上面的系数矩阵，发现Wmn是以N为周期的，即,当N=8时，其周期性如图所示，由于,所以当N=8时，可得：,可见，离散傅立叶变换中的
12、乘法运算有许多重复内容。1965年库利-图基提出原始的N点序列依次分解成一系列短序列，然后，求出这些短序列的离散傅立叶变换，以此来减少乘法运算，例如，设：,由此，离散傅立叶变换可写成下面的形式：,因为：,所以：,F1(u)和F2(u)分别是f1(x)和f2(x)的N/2点的傅立叶变换,由于F1(u)和F2(u)均是以N/2为周期，所以,这说明当mN/2时，上式也是成立的，因此下式成立：,由上面的分析可见，一个N点的离散傅立叶变换可由两个N/2点的傅立叶变换得到,离散傅立叶变换的计算时间主要由乘法决定，分解后所需的乘法次数大为减少。第一项为(N/2)2次，第二项为(N/2)2N次，总共为2(N/
13、2)2N次运算即可完成，而原来需要N2次运算，可见分解后的乘法计算次数减少了近一半。,当N为2的整数幂时，则上式中的F1(u)和F2(u)还可以再分成两个更短的序列，因此计算时间会更短。由此可见，利用WNm的周期性和分解运算，从而减少乘法运算次数是实现快速运算的关键,实例,离散余弦变换,离散余弦变换(Discrete Cosine Transform-简称DCT)是傅里叶变换的一种特殊情况。在傅里叶级数展开式中，被展开的函数是实偶函数时，其傅里叶级数中只包含余弦项，称之为余弦变换 DCT计算复杂性适中，又具有可分离特性，还有快速算法，所以被广泛地用在图象数据压缩编码算法中，如JPEG、MPEG
14、-1、MPEG-2及H.261等压缩编码国际标准都采用了离散余弦变换编码算法 其变换核是为实数的余弦函数，因而DCT的计算速度比DFT快得多对于具有一阶马尔可夫过程的随机信号，DCT是K-L变换的最好近似，已被广泛应用到图像压缩编码、语音信号处理等领域,一维离散余弦变换,一维离散余弦反变换,二维离散余弦变换,二维离散反余弦变换,如果令N=4，由一维解析式定义可得如下展开式：,写成矩阵形式：,F(u)=Af(x),同理，可得到反变换展开形式：,写成矩阵形式：,f(x)=ATF(u),二维离散余弦变换为：,F(u,v)=Af(x,y)ATf(x,y)=ATF(u,v) AT,离散余弦变换的计算,与
15、傅立叶变换一样，离散余弦变换可以由定义出发进行计算，但这样的计算量太大，在实际应用中很不方便，寻找快速算法首先，从定义出发，作如下推导,取实部的意思,如果把时域数据向量作系列延拓，即,则fe(x)的离散余弦变换可写成为：,同理，在反变换时，首先在变换空间，把F(u)作如下延拓：,反变换表示为：,计算余弦变换的步骤为,1、把f(x)延拓成,，长度为2N,2、求,的2N点FFT,3、对u各项乘上对应的因子,4、取实部，并乘上因子,5、取F(u)的前N项，即维f(x)的余弦变换,离散K-L变换,又称为霍特林(Hotelling)变换以图像的统计性质为基础的变换核矩阵由图像阵列的协方差矩阵的特征值和特
16、征向量所决定又称为特征向量变换,当变量之间存在一定的相关关系时，可以通过原始变量的线性组合，构成为数较少的不相关的新变量代替原始变量，而每个新变量都含有尽量多的原始变量的信息。这种处理问题的方法，叫做主成分分析，新变量叫做原始变量的主成分。目的是寻找任意统计分布的数据集合之主要分量的子集。相应的基向量组满足正交性且由它定义的子空间最优地考虑了数据的相关性。将原始数据集合变换到主分量空间使单一数据样本的互相关性(cross-correlation)降低到最低点。,图像协方差矩阵,假设对某幅NN的图像f(x,y)，在某个传输通道上传输了M次，因会受到各种因素的随机干扰，接收到是一个图像集合,将M次
17、传送的图像集合写成M个N2维向量X1,X2,Xi,XM,生成向量的方法可以采用行堆叠或列堆叠的方法，对第i次获得的图像fi(x,y)，可用N2维向量Xi表示：,问题是：如何选取一个合适的正交变换A，使得变换后的图像Y=AX 1)是具有MN2个分量的向量2)由Y经反变换而恢复的 (向量X的估值)和原始图像具有最小的均方误差，即,称满足这两个条件的正交变换A为K-L变换。如果能找到这样一个变换，那么就意味着经过一个变换，不仅删除了N2-M个分量，并且由变换结果Y重新恢复的图像,是有效的过滤了随机干扰的原图像的最佳逼近。,X向量的协方差矩阵CX定义为,设ei和i是协方差矩阵CX对应的特征向量和特征值
18、，将特征值按减序排列，即,则K-L变换核矩阵A的行用CX的特征值i所对应的特征向量ei构成：,直接求矩阵CX的特征值和特征向量很困难。这是因为CX是N2N2维矩阵，尽管图像的大小N可能不是很大的，但N2却是很大的数据。这样求其特征向量和特征值速度较慢。但如果样本图象个数M不太多，可以先计算出MM维方阵LATA的特征值k和特征向量 vk,左乘矩阵A，则有,是矩阵CX的 特征向量,可以选择P(PM)个较大特征值对应的特征向量（主成分），构造新的P维主成分空间Q,因为CX是实对称矩阵，总能找到一个标准正交的特征向量集合，使A-1=AT，那么可得K-L反变换为,K-L变换的性质和特点,（1）Y的平均值
19、向量my0，即为零向量0,（2）Y向量的协方差,（3）对角性,对角线上的元素是原始图像向量的协方差矩阵CX对应的特征值i，它也是Y向量的方差。而非对角线上的元素值为0，说明Y向量中各元素之间相关性小，而CX的非对角线上元素不为0，说明原始图像元素之间相关性强，这就是采用K-L变换进行编码，数据压缩比大的原因,显然K-L坐标系将矩阵CX对角化了，换句话说，通过K-L变换，消除了原有向量X的各分量之间的相关性，从而可能去掉那些带有较少信息的坐标轴，以达到降低特征空间维数的目的。,在原来坐标系中，要用两个分量X1,X2来表示各个样本，而在K-L坐标系中，只要用e1就可以，去掉e2并不会带来很大的误差
20、,假设矩阵CX只有少数几个数值大的特征值，而其余的特征值数值很小，K-L坐标系就可以有效的进行信息压缩,K-L变换的最大优点是去相关性好，可用于数据压缩和图像旋转主要困难是由于协方差矩阵CX求特征值和特征向量解方程的计算量大，同时K-L变换是非分离的，二维不可分，一般情况下，K-L变换没有快速算法,实例,以K-L变换进行自动的人脸识别为例说明,我们把一幅数字图像看成一个矩阵或一个数组，用B(i,j)或bij 表示，幅NN大小的人脸图像按列相连构成一个N2维矢量,x=( b11 b21bN1 b12b22bN2 b1N b2NbNN),它可视为N2维空间中的一个点，假设N=128。由于人脸结构的
21、相似性，当把很多这样的人脸图像归一化之后，这些图像在这一超高维空间中不是随机或散乱分布的，而是存在某种规律，因此可以通过K-L变换用一个低维子空间描述人脸图像，同时又能保存所需要的识别信息,图像的归一化,对于一个全自动的人脸识别系统，其首要的工作是人脸图像的分割以及主要器官的定位。另外，由于K-L变换本质上依赖于图像灰度在空间分布上的相关性，因此还需要对人脸图像进行一系列的预处理，以达到位置校准和灰度归一化的目的,假设已根据分割及定位算法，得到了人脸正面图像左右两眼中心的位置，并分别记为Er和El，则可通过下述步骤达到图像校准的目的,1、进行图像旋转，以使Er和El的连线ErEl保持水平。这保
22、证了人脸方向的一致性，体现了人脸在图像平面内的旋转不变性,2、根据图所示的比例关系，进行图像裁剪。图中，O点为ErEl的中点，且d=ErEl。经过裁剪，在2d2d的图像内，可保证O点固定于(0.5d,d)处。这保证了人脸位置的一致性，体现了人脸在图像平面内的平移不变性,3、进行图像缩小和放大变换，得到统一大小的标准图像，规定标准图像的大小为128128象素点，则缩放倍数为=2d/128。这使得d=ErEl为定长(64个象素点)，即保证了人脸大小的一致性，体现了人脸在图像平面内的尺度不变性,经过校准，不仅在一定程度上获得了人脸表示的几何不变性，而且还基本上消除了头发和背景的干扰。,完成了旋转、平
23、移和尺度不变性后，需要对校准的图像做灰度拉伸，以改善图像的对比度，然后采用直方图修正技术使图像具有统一的均值和方差，一部分消除光照强度的影响,假设人脸数据库中，由20人，每人10幅人脸图像,K-L变换,以归一化后的标准图像做为训练样本集，以该样本集的总体散布矩阵为协方差矩阵，即,xi为第i个训练样本的图像向量， 为训练样本集的平均图像，M为训练样本的总数,为了N2N2维矩阵的特征值和正交归一的特征向量，直接计算是困难的，因此引入一个定理，奇异值分解SVD,设A是一秩为r的nr维矩阵，则存在两个正交矩阵：,以及对角阵,满足,其中i为矩阵AAT和ATA的非0特征值，u和v分别为AAT和ATA对应于
24、i的特征向量，上述分解称为矩阵A地奇异值分解，为A的奇异值,推论,由于可表示为：,故，构造矩阵：,容易求其特征值i及相应的正交归一特征向量vi( i=0,1,2M-1)。由推论可知，的正交归一化特征向量ui为,这就是图像的特征向量，它是通过计算较低维矩阵R的特征值与特征向量而间接求出的,将特征值从大到小排序：0 1 r-1，其对应的特征向量为ui。这样，每一幅人脸图像都可以投影到由u0,u1,uM-1张成的子空间中。因此每一幅人脸图像对应于子空间中的一个点，同样，子空间中的任一点也对应于一幅图像,特征脸,对于任一待识别样本f，可通过向“特征脸”子空间投影求出其系数向量： y=Utf其重建图像
25、f=Uy考虑重建图像的信噪比 RSN=10lg(|f|2/|f-f|2) 若其小于阈值，则 可判断f不是人脸图像。,小波变换,广泛应用：信号处理、图像处理、模式识别、量子物理、非线性科学领域原则上，凡传统使用Fourier分析的方法，都可以用小波分析代替与Fourier变换、Gabor变换相比，小波变换是空间（时间）和频率的局部变换伸缩和平移等运算功能可对函数或信号进行多尺度的细化分析，解决了Fourier变换不能解决的许多困难，对高频采取逐渐精细的时域或空域步长，从而可以聚焦到分析对象的任意细节数学显微镜,为了用傅立叶变换研究一个模拟信号的谱特性，必须获得信号在时域中的全部信息，包括将来的信
26、息，即傅立叶变换对时间的分辨率为0，对频率的分辨率为无穷。如果一个信号在某个时刻的一个小的邻域中变化了，那么整个频谱就受到影响。如语音信号、地震信号等，希望知道信号在突变时刻的频率成分，如利用傅立叶变换，这些非平稳的突变成分被傅立叶变换的积分作用平滑了。可以看出，在非平稳信号分析和实时信号处理的许多应用中，只有傅立叶变换公式是不够的，傅立叶变换无法反映信号的局部时域和频域特性，只适宜处理平稳信号,正是由于傅立叶变换存在不能同时进行时间-评论局部分析的缺点，Gabor提出一种加窗傅立叶变换,在信号的时间-频率分析中，D.Gabor注意到了傅立叶变换的不足，在1946年，论文中为提取信号傅立叶变换
27、的局部信息，引入了一个时间局部变化的“窗函数”，称为Gabor变换，又称为加窗傅立叶变换,但Gabor变换的时-频窗口是固定不变的，窗口没有自适应性，不适于分析多尺度信号过程和突变过程，而且其离散形式没有正交展开，难于实现高效算法，这是Gabor变换的主要缺点,在非平稳信号的分析中，希望存在一种变换函数，它能满足：对于高频谱的信息，时间间隔要相对的小，以便给出比较好的精度；而对于低频谱的信息，时间间隔要相对的宽，以便给出完全的信息，也就是说，要有一个灵活可变的时间-频率窗，使在高“中心频率”时，时窗宽度自动变窄；在低“中心频率”时，时频窗宽度自动变宽,1984由法国的从事石油勘测信号处理的地球
28、物理学家Morlet提出的，他在分析地震波的时频局部特性时，希望使用在高频处时窗变窄，低频处频窗变宽的自适应变换。引用高斯余弦调整函数，将其伸缩和平移得到一组函数系数，后称为“Morlet小波基”,作为多尺度分析工具，小波变换为信号在不同尺度上的分析和表征提供了一个精确和统一的框架，从图像处理的角度看，小波变换存在以下几个优点：,(1)小波分解可以覆盖整个频域(提供了一个数学上完备的描述)(2)小波变换通过选取合适的滤波器，可以极大的减小或去除所提取得不同特征之间的相关性(3)小波变换具有“变焦”特性，在低频段可用高频率分辨率和低时间分辨率(宽分析窗口)，在高频段，可用低频率分辨率和高时间分辨率(窄分析窗口)(4)小波变换实现上有快速算法(Mallat小波分解算法),图像的小波处理,小波分解,低频系数,水平系数,垂直系数,对角系数,小波重构,
