第二章 图像变换 - 南京大学计算机科学与技术系

第3章图像变换傅立叶变换(FFT)离散余弦变换(DCT)K-L变换小波变换问题的提出为达到某种目的将原始图象变换映射到另一个空间上，使得图象的某些特征得以突出，以便于后面的处理和识别。一般变换后的图象，大部分能量都分布于低频谱段，这对以后图象的压缩、传输都比较有利。使得运算次数减少，节省时间φ傅立叶变换FFT线性系统对于一般线性系统，往往是用时间作为参数来描述的，表示为一维(t)系统。在图像处理中是用空间作为参数来描述的，通常表示为二维(x,y)系统。输入函数f(x,y)表示原始图像，输出函数g(x,y)表示经处理后的图像，线性系统可看作是一种映射φ，它反映了各种线性的图像处理方法，其输入和输出的关系表示为：二维线性系统叠加原理点源和狄拉克δ函数

一幅图像可以看成由无穷多极小的象素组成，每一个象素都可以看作为一个点源，因此，一幅图像也可以看成由无穷多点源所组成数学上，点源可以用狄拉克δ函数来表示，二维δ函数定义为满足狄拉克δ函数性质(1)δ函数为偶函数，即(2)位移性或用卷积符号*表示为(3)可分性(4)乘积性(5)筛选性当且仅当α＝β＝0时(6)指数函数卷积假设f(x)(x=0,1…,A-1)以及g(x)(x=0,1,…,C-1)是两个有限离散函数，其线性卷积为原点对折平移x对于图像二维函数的卷积，则相关2个函数的相关定义为其中f*(i)为f(i)的复共轭

一维连续傅立叶变换定义及基本概念设f(x)为x的函数，如果f(x)满足下面的狄里赫莱条件：（1）具有有限个间断点（2）具有有限个极值点（3）绝对可积则有下列式成立：x为时域变量，u为频域变量(1)(2)如果令w＝2πu，则有称为傅立叶变换对函数f(x)的傅立叶变换一般是一个复量，它可以用下式表示：指数形式：|F(w)|称为傅立叶谱，φ(w)称为相位谱，E(w)为能量谱或功率普实例傅立叶变换其相位为Af(x)xτ/2-τ/2π-πuφ(u)傅立叶谱周期函数的傅立叶变换f(x)x傅立叶级数来表示傅立叶变换

冲激序列w003w0w-3w0-w0F(u)结论1、只要满足一定条件，连续函数就可以进行傅立叶变换，实际上这个条件在工程应用中很容易满足。2、连续非周期函数的傅立叶谱是连续的非周期函数，连续的周期函数的傅立叶谱是离散的非周期函数。二维连续傅立叶变换如果二维函数f(x,y)满足狄里赫莱条件，则将有下面的傅立叶变换对存在：与一维傅立叶变换类似，二维傅立叶变换的傅立叶谱和相位谱为：例：求如图所示的函数的傅立叶谱xyf(x,y)Af(x,y)函数其傅立叶变换为：其傅立叶谱为：离散傅立叶变换由于实际问题的时间或空间函数的区间是有限的，或者是频谱有截止频率离散傅立叶变换(DiscreteFourierTransform－简称DFT)在数字信号处理和数字图像处理中应用十分广泛，它建立了离散时域和离散频域之间的联系一维离散傅立叶变换非周期性的连续信号周期性的连续信号非周期性的离散谱取样作离散化处理周期性的连续谱离散化并延拓为周期性信号离散的周期性谱连续的非周期性的波形二维离散傅立叶变换由于图像的频率是表征图像中灰度变化剧烈程度的指标，是灰度在平面空间上的梯度。如：大面积的沙漠在图像中是一片灰度变化缓慢的区域，对应的频率值很低；而对于地表属性变换剧烈的边缘区域在图像中是一片灰度变化剧烈的区域，对应的频率值较高。傅立叶变换在实际中的物理意义，设f是一个能量有限的模拟信号，则其傅立叶变换就表示f的谱。从纯粹的数学意义上看，傅立叶变换是将一个函数转换为一系列周期函数来处理的。从物理效果看，傅立叶变换是将图像从空间域转换到频率域，其逆变换是将图像从频率域转换到空间域。换句话说，傅立叶变换的物理意义是将图像的灰度分布函数变换为图像的频率分布函数，傅立叶逆变换是将图像的频率分布函数变换为灰度分布函数。一个M×N大小的二维函数f(x,y)，其离散傅立叶变换对为在数字图像处理中，图像一般取样为方形矩阵，即N×N，则其傅立叶变换及其逆变换为（1）可分性从上式可以看出，一个二维傅立叶变换可用二次一维傅立叶变换来实现傅立叶变换的性质其意义：一个二维傅立叶变换或反变换都可以分解为二步进行，其中每一步都是一个一维傅立叶变换或反变换f(x,y)(0,0)N-1N-1xyF(x,v)(0,0)N-1N-1xvF(u,v)(0,0)N-1N-1vu行变换列变换二维傅立叶变换分离成两个一维变换行变换列变换（2）平移性在空域中，图像原点平移到(x0，y0)时，其对应的频谱F(u,v)要乘上一个负的指数项在频域中，原点平移到(u0，v0)时，其对应的f(x,y)要乘上一个正的指数项也就是说，当空域中f(x,y)产生移动时，在频域中只发生相移，而傅立叶变换的幅值不变反之，当频域中F(u,v)产生移动时，相应的f(x,y)在空域中也只发生相移，而幅值不变在数字图像处理中，我们常常将F(u,v)的原点移到N×N频域方阵的中心，以使能清楚地分析傅立叶变换谱的情况，只需令：u0＝v0＝N/2则即，如果将图像频谱的原点从起点(0，0)移到图像中心点(N/2，N/2)，只要f(x,y)乘上(－1)(x＋y)因子进行傅立叶变换即可平移（3）周期性和共轭对程性周期性可表示为

如果F(u,v)是f(x,y)的傅立叶变换，则F*(-u,-v)是f(-x,-y)的傅立叶变换的共轭函数F(u,v)=F*(-u,-v)|F(u,v)|=|F(-u,-v)|共轭对称性可表示为（4）旋转不变性如果引入极坐标则f(x,y)和F(u,v)分别变为f(r,θ)和F(ω，φ)在极坐标系中，存在以下变换对该式表明，如果空间域函数f(x,y)旋转θ0角度后，相应的傅立叶变换F(u,v)在频域中也旋转同一θ0角，反之，F(u,v)在频域中旋转θ0角，其反变换f(x,y)在空间域中也旋转θ0角（5）分配性和比例性傅立叶变换的分配性表明，傅立叶变换和反变换对于加法可以分配，而对乘法则不行，即傅立叶变换的比例性表明，对于二个标量a和b，有在空间比例尺度的展宽，相应于频域中比例尺度的压缩，其幅值也减少为原来的（6）平均值性质定义二维离散函数的平均值为将u=v=0代入二维离散傅立叶公式，可得比较上面两式，可看出若求二维离散信号f(x,y)的平均值，只需算出相应的傅立叶变换F(u,v)在原点的值F(0,0)（7）卷积定理卷积定理和相关定理都是研究两个函数的傅立叶变换之间的关系，这构成了空间域和频域之间的基本关系对于两个二维连续函数f(x,y)和g(x,y)的卷积定义为其二维卷积定理可由下面关系表示设则指出傅立叶变换一个主要好处：与其在一个域中作不直观的，和难懂的卷积，不如在另外一个域中作乘法，可以达到相同的效果它表明两个二维连续函数在空间域中的卷积可用求其相应的两个傅立叶变换乘积的逆变换而得。反之，在频域中的卷积可用空间域中乘积的傅立叶变换而得，应用卷积定理明显的好处是避免了直接计算卷积的麻烦，它只需要先算出各自的频谱，然后相乘，再求其逆变换，即可得到卷积。离散傅立叶变换和逆变换都是周期函数，为了防止卷积后产生交叠误差，需要对离散的二维函数的定义域加以扩展。利用一维函数来说明函数定义域的扩展，设f(x)(x=0,1….A-1)和g(x)(x=0,1,….C-1)是两个有限的离散函数，也就是说f(x)定义域为0≤x≤A-1，g(x)的定义域为0≤x≤C-1。则其线性卷积为如果利用卷积定理来计算该卷积，则相当于把f(x)和g(x)分别以A和C为周期进行周期延拓，因此，将上式改写为(一个周期)求得结果将不是需要的z(x)，而是周期循环的为了避免循环卷积，可以对原被卷积函数补零。由于卷积结果的长度为N=A+C-1，因此，可以把两个被卷积的函数的长度扩展到N，并在原函数定义区间外的部分补零，即取同样地，二维离散卷积计算时，也必须对被卷积函数进行延拓和补零，如果被卷积函数f(x,y)和g(x,y)地大小分别为A×B和C×D，则延拓后地函数为：（8）相关定理对于二维连续函数f(x,y)和g(x,y)的相关定义为相关定理可表示为在离散情况下，与离散卷积一样，需要用增补零的方法扩充f(x,y)和g(x,y)为fe(x,y)和ge(x,y)，并根据卷积定理相类似的方法来选取M和N，以避免在相关函数周期内产生交叠误差。快速傅立叶变换(FFT)离散傅立叶变换已成为数字信号处理的重要工具，然而，它的计算量达，运算时间长，在某种程度上却限制了它的使用范围。快速算法大大提高了运算速度，在某些应用场合已能作实时处理，并且应用在控制系统中快速傅立叶变换不是一种新的变换，它是离散傅立叶变换的一种算法，它是在分析离散傅立叶变换中的多余运算的基础上，进而消除这些重复工作的思想指导下得到的其原理：对于一个有限长序列{f(x)}(0≤x≤N-1)，它的傅立叶变换由下式表示：令傅立叶变换对可写为：(1)(2)将正变换(1)展开得到：矩阵表示为：从上式可以看出，要得到每一个频率分量，需进行N次乘法和N-1次加法运算。要完成整个变换需要N2次乘法和N(N-1)次加法运算。当序列较长时，必然要花费大量的时间观察上面的系数矩阵，发现Wmn是以N为周期的，即当N=8时，其周期性如图所示，由于所以当N=8时，可得：W0W1W2W3W4W5W6W7可见，离散傅立叶变换中的乘法运算有许多重复内容。1965年库利-图基提出原始的N点序列依次分解成一系列短序列，然后，求出这些短序列的离散傅立叶变换，以此来减少乘法运算，例如，设：由此，离散傅立叶变换可写成下面的形式：因为：所以：F1(u)和F2(u)分别是f1(x)和f2(x)的N/2点的傅立叶变换

由于F1(u)和F2(u)均是以N/2为周期，所以

这说明当m≥N/2时，上式也是成立的，因此下式成立：由上面的分析可见，一个N点的离散傅立叶变换可由两个N/2点的傅立叶变换得到离散傅立叶变换的计算时间主要由乘法决定，分解后所需的乘法次数大为减少。第一项为(N/2)2次，第二项为(N/2)2＋N次，总共为2×(N/2)2＋N次运算即可完成，而原来需要N2次运算，可见分解后的乘法计算次数减少了近一半。当N为2的整数幂时，则上式中的F1(u)和F2(u)还可以再分成两个更短的序列，因此计算时间会更短。由此可见，利用WNm的周期性和分解运算，从而减少乘法运算次数是实现快速运算的关键实例离散余弦变换离散余弦变换(DiscreteCosineTransform-简称DCT)是傅里叶变换的一种特殊情况。在傅里叶级数展开式中，被展开的函数是实偶函数时，其傅里叶级数中只包含余弦项，称之为余弦变换DCT计算复杂性适中，又具有可分离特性，还有快速算法，所以被广泛地用在图象数据压缩编码算法中，如JPEG、MPEG-1、MPEG-2及H.261等压缩编码国际标准都采用了离散余弦变换编码算法其变换核－是为实数的余弦函数，因而DCT的计算速度比DFT快得多对于具有一阶马尔可夫过程的随机信号，DCT是K-L变换的最好近似，已被广泛应用到图像压缩编码、语音信号处理等领域一维离散余弦变换一维离散余弦反变换二维离散余弦变换二维离散反余弦变换如果令N=4，由一维解析式定义可得如下展开式：写成矩阵形式：[F(u)]=[A][f(x)]同理，可得到反变换展开形式：写成矩阵形式：[f(x)]=[A]T[F(u)]二维离散余弦变换为：[F(u,v)]=[A][f(x,y)][A]T[f(x,y)]=[A]T[F(u,v)][A]T离散余弦变换的计算与傅立叶变换一样，离散余弦变换可以由定义出发进行计算，但这样的计算量太大，在实际应用中很不方便，寻找快速算法首先，从定义出发，作如下推导取实部的意思如果把时域数据向量作系列延拓，即则fe(x)的离散余弦变换可写成为：则是2N点的离散傅立叶变换，所以在作余弦变换时，可以把序列长度延拓为2N，然后作离散傅立叶变换，产生的结果取其实部便可得到余弦变换同理，在反变换时，首先在变换空间，把[F(u)]作如下延拓：反变换表示为：可见，离散余弦反变换可以从的2N点反傅立叶变换实现计算余弦变换的步骤为

1、把f(x)延拓成，长度为2N2、求的2N点FFT3、对u各项乘上对应的因子

4、取实部，并乘上因子

5、取F(u)的前N项，即维f(x)的余弦变换离散K-L变换又称为霍特林(Hotelling)变换以图像的统计性质为基础的变换核矩阵由图像阵列的协方差矩阵的特征值和特征向量所决定－又称为特征向量变换当变量之间存在一定的相关关系时，可以通过原始变量的线性组合，构成为数较少的不相关的新变量代替原始变量，而每个新变量都含有尽量多的原始变量的信息。这种处理问题的方法，叫做主成分分析，新变量叫做原始变量的主成分。目的是寻找任意统计分布的数据集合之主要分量的子集。相应的基向量组满足正交性且由它定义的子空间最优地考虑了数据的相关性。将原始数据集合变换到主分量空间使单一数据样本的互相关性(cross-correlation)降低到最低点。图像协方差矩阵假设对某幅N×N的图像f(x,y)，在某个传输通道上传输了M次，因会受到各种因素的随机干扰，接收到是一个图像集合将M次传送的图像集合写成M个N2维向量{X1,X2,…Xi,…XM},生成向量的方法可以采用行堆叠或列堆叠的方法，对第i次获得的图像fi(x,y)，可用N2维向量Xi表示：问题是：如何选取一个合适的正交变换A，使得变换后的图像Y=AX1)是具有M<<N2个分量的向量2)由Y经反变换而恢复的(向量X的估值)和原始图像具有最小的均方误差，即称满足这两个条件的正交变换A为K-L变换。如果能找到这样一个变换，那么就意味着经过一个变换，不仅删除了N2-M个分量，并且由变换结果Y重新恢复的图像是有效的过滤了随机干扰的原图像的最佳逼近。

X向量的协方差矩阵CX定义为设ei和λi是协方差矩阵CX对应的特征向量和特征值，将特征值按减序排列，即则K-L变换核矩阵A的行用CX的特征值λi所对应的特征向量ei构成：直接求矩阵CX的特征值和特征向量很困难。这是因为CX是N2×N2维矩阵，尽管图像的大小N可能不是很大的，但N2却是很大的数据。这样求其特征向量和特征值速度较慢。但如果样本图象个数M不太多，可以先计算出M×M维方阵L＝ATA的特征值μk和特征向量vk左乘矩阵A，则有

是矩阵CX的特征向量可以选择P(P≤M)个较大特征值对应的特征向量（主成分），构造新的P维主成分空间Q因为CX是实对称矩阵，总能找到一个标准正交的特征向量集合，使A-1=AT，那么可得K-L反变换为

K-L变换的性质和特点（1）Y的平均值向量my＝0，即为零向量0（2）Y向量的协方差（3