第3章 图像变换p傅立叶变换(FFT)p离散余弦变换(DCT)pK-L变换p小波变换问题的提出p为达到某种目的将原始图象变换映射到另一个空间上， 使得图象的某些特征得以突出，以便于后面的处理和识 别。p一般变换后的图象，大部分能量都分布于低频谱段，这 对以后图象的压缩、传输都比较有利。使得运算次数减 少，节省时间p傅立叶变换FFT线性系统p对于一般线性系统，往往是用时间作为参数来描述的， 表示为一维(t)系统。在图像处理中是用空间作为参数来 描述的，通常表示为二维(x,y)系统。输入函数f(x,y)表 示原始图像，输出函数g(x,y)表示经处理后的图像，线 性系统可看作是一种映射，它反映了各种线性的图像 处理方法，其输入和输出的关系表示为： 二维线性系统p叠加原理点源和狄拉克函数 p一幅图像可以看成由无穷多极小的象素组成，每一个象 素都可以看作为一个点源，因此，一幅图像也可以看成 由无穷多点源所组成 p数学上，点源可以用狄拉克函数来表示，二维函数定 义为 p满足狄拉克函数性质(1) 函数为为偶函数，即(2)位移性或用卷积积符号*表示为为(3)可分性(4)乘积积性(5)筛选筛选 性当且仅仅当0时时(6)指数函数卷积p假设f(x)(x=0,1,A-1)以及g(x)(x=0,1,C -1)是两个有限离散函数，其线性卷积为 原点对 折平移xp对于图像二维函数的卷积，则 相关p2个函数的相关定义为 其中f*(i)为f(i)的复共轭 一维连续傅立叶变换p定义及基本概念设f(x)为x的函数，如果f(x)满足下面的狄里赫莱条件：（1）具有有限个间断点 （2）具有有限个极值点 （3）绝对可积则有下列式成立：x为时域变量，u 为频域变量(1)(2)如果令w2u，则有称为傅立 叶变换对函数f(x)的傅立叶变换一般是一个复量，它可以用下式 表示：指数形式 ：|F(w)|称为傅立 叶谱，(w)称 为相位谱， E(w)为能量谱 或功率普p实例p傅立叶变换p其相位为Af(x)x/2-/2-u(u)p傅立叶谱p周期函数的傅立叶变换f(x )x傅立叶级数 来表示傅立叶变换 冲激序列w003w0w -3w0-w0F(u)结论p1、只要满足一定条件，连续函数就可以进行傅 立叶变换，实际上这个条件在工程应用中很容 易满足。p2、连续非周期函数的傅立叶谱是连续的非周期 函数，连续的周期函数的傅立叶谱是离散的非 周期函数。二维连续傅立叶变换如果二维函数f(x,y)满足狄里赫莱条件，则将有下 面的傅立叶变换对存在：与一维傅立叶变换类似，二维傅立叶变换 的傅立叶谱和相位谱为：例：求如图所示的函数的傅立叶谱xyf(x,y)Af(x,y)函数其傅立叶变换为：其傅立叶谱为：离散傅立叶变换p由于实际问题的时间或空间函数的区间是有限 的，或者是频谱有截止频率 p离散傅立叶变换(Discrete Fourier Transform简称DFT)在数字信号处理和数字 图像处理中应用十分广泛，它建立了离散时域 和离散频域之间的联系 p一维离散傅立叶变换非周期性的 连续信号周期性的连续 信号 非周期性的 离散谱取样作离散 化处理周期性的连 续谱离散化并延拓 为周期性信号离散的周 期性谱连续的非周期 性的波形二维离散傅立叶变换p由于图像的频率是表征图像中灰度变化剧烈程度的指标，是灰度在 平面空间上的梯度。p如：大面积的沙漠在图像中是一片灰度变化缓慢的区域，对应的频 率值很低；而对于地表属性变换剧烈的边缘区域在图像中是一片灰 度变化剧烈的区域，对应的频率值较高。p傅立叶变换在实际中的物理意义，设f是一个能量有限的模拟信号 ，则其傅立叶变换就表示f的谱。p从纯粹的数学意义上看，傅立叶变换是将一个函数转换为一系列周 期函数来处理的。p从物理效果看，傅立叶变换是将图像从空间域转换到频率域，其逆 变换是将图像从频率域转换到空间域。p换句话说，傅立叶变换的物理意义是将图像的灰度分布函数变换为 图像的频率分布函数，傅立叶逆变换是将图像的频率分布函数变换 为灰度分布函数。 一个MN大小的二维函数f(x,y)，其离散傅立叶变换对为 在数字图像处理中，图像一般取样为方形矩阵，即 NN，则其傅立叶变换及其逆变换为 （1）可分性从上式可以看出，一个二维傅立叶变换 可用二次一维傅立叶变换来实现傅立叶变换的性质其意义：一个二维傅立叶变换或反变换都可以分 解为二步进行，其中每一步都是一个一维傅立叶 变换或反变换f(x,y )(0,0)N-1N-1xy F(x,v )(0,0)N-1N-1xv F(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)的原点移到NN频 域方阵的中心，以使能清楚地分析傅立叶变换谱的情况 ，只需令：u0v0N/2则即，如果将图像频谱的原点从起点(0，0)移到图像中 心点(N/2，N/2)，只要f(x,y)乘上(1)(xy)因子进行傅 立叶变换即可平移（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)的卷积定义为其二维卷积定理可由下面关系表示设则指出傅立叶变换一个主要好处：与其在一个域中作不 直观的，和难懂的卷积，不如在另外一个域中作乘法 ，可以达到相同的效果它表明两个二维连续函数在空间域中的卷积可用求其相应的 两个傅立叶变换乘积的逆变换而得。反之，在频域中的卷积可用空间域中乘积的傅立叶变换而得 ，应用卷积定理明显的好处是避免了直接计算卷积的麻烦， 它只需要先算出各自的频谱，然后相乘，再求其逆变换，即 可得到卷积。 p离散傅立叶变换和逆变换都是周期函数，为了 防止卷积后产生交叠误差，需要对离散的二维 函数的定义域加以扩展。p利用一维函数来说明函数定义域的扩展，设 f(x)(x=0,1. A-1)和g(x)(x=0,1,.C-1)是 两个有限的离散函数，也就是说f(x)定义域为 0xA-1，g(x)的定义域为0xC-1。则其 线性卷积为 p如果利用卷积定理来计算该卷积，则相当于把f(x)和g(x)分别以 A和C为周期进行周期延拓，因此，将上式改写为(一个周期) p求得结果将不是需要的z(x)，而是周期循环的 p为了避免循环卷积，可以对原被卷积函数补零 。由于卷积结果的长度为N=A+C-1，因此， 可以把两个被卷积的函数的长度扩展到N，并 在原函数定义区间外的部分补零，即取 同样地，二维离散卷积计算时，也必须对被卷积函数 进行延拓和补零，如果被卷积函数f(x,y)和g(x,y)地大 小分别为AB和CD，则延拓后地函数为：（8）相关定理对于二维连续函数f(x,y)和g(x,y)的相关定义为 相关定理可表示为p在离散情况下，与离散卷积一样，需要用增补 零的方法扩充f(x,y)和g(x,y)为fe(x,y)和 ge(x,y)，并根据卷积定理相类似的方法来选取 M和N，以避免在相关函数周期内产生交叠误差 。 快速傅立叶变换(FFT)p离散傅立叶变换已成为数字信号处理的重要工具，然而 ，它的计算量达，运算时间长，在某种程度上却限制了 它的使用范围。p快速算法大大提高了运算速度，在某些应用场合已能作 实时处理，并且应用在控制系统中p快速傅立叶变换不是一种新的变换，它是离散傅立叶变 换的一种算法，它是在分析离散傅立叶变换中的多余运 算的基础上，进而消除这些重复工作的思想指导下得到 的其原理：对于一个有限长序列f(x)(0x N-1)，它的傅立叶 变换由下式表示：令傅立叶变换对可写为：(1 )(2 )将正变换(1)展开得到：矩阵表示为：从上式可以看出，要得到每一个频率分量，需进行N次乘 法和N-1次加法运算。要完成整个变换需要N2次乘法和 N(N-1)次加法运算。当序列较长时，必然要花费大量的时 间观察上面的系数矩阵，发现Wmn是以N为周期的，即当N=8时，其周期性如图所示，由于所以当N=8时，可得：W0W1 W2W3W4W5W6W7可见，离散傅立叶变换中的乘法运算有许多重复内容 。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)2 N次，总共为2(N/2)2N次运算即可完成，而原来需要 N2次运算，可见分解后的乘法计算次数减少了近一半。当N为2的整数幂时，则上式中的F1(u)和F2(u)还可以再分 成两个更短的序列，因此计算时间会更短。由此可见，利用WNm的周期性和分解运算，从而减少乘法 运算次数是实现快速运算的关键实例离散余弦变换p离散余弦变换(Discrete Cosine Transform-简称DCT)是傅 里叶变换的一种特殊情况。在傅里叶级数展开式中，被展开的函数 是实偶函数时，其傅里叶级数中只包含余弦项，称之为余弦变换 pDCT计算复杂性适中，又具有可分离特性，还有快速算法，所以被 广泛地用在图象数据压缩编码算法中，如JPEG、MPEG-1、 MPEG-2及H.261等压缩编码国际标准都采用了离散余弦变换编 码算法 p其变换核是为实数的余弦函数，因而DCT的计算速度比DFT快得 多p对于具有一阶马尔可夫过程的随机信号，DCT是K-L变换的最好近 似，已被广泛应用到图像压缩编码、语音信号处理等领域p一维离散余弦变换 一维离散余弦反变换p二维离散余弦变换 二维离散反余弦变换如果令N=4，由一维解析式定义可得如下展开式：写成矩阵形式：F(u)=Af(x)同理，可得到反变换展开形式：写成矩阵形式：f(x)=ATF(u)二维离散余弦变换为： F(u,v)=Af(x,y)ATf(x,y)=ATF(u,v) AT离散余弦变换的计算与傅立叶变换一样，离散余