数字图像总复习第3章.ppt

第三章 图象变换,3.1 概述和分类3.2 傅里叶变换3.3 快速傅里叶变换3.4 其它可分离图象变换3.5 霍特林变换,第三章 图象变换,第一节 概述和分类,为了有效地和快速地对图象进行处理和分析常常需要将原定义在图象空间的图象以某种形式转换到另外一些空间，并利用在这些空间的特有性质方便地进行一定的加工,最后再转换回图象空间以得到所需的效果。这些转换方法就是本章要着重介绍和讨论的图象变换技术。,第三章 图象变换,图象为什么要变换,利用变换的某些性质，可以大大简化或加速图象处理过程空域图象经过变换后形成“对应域图象”，从中会看到在空域图象中不易看到的某些“东西”。变换后形成“对应域图象”，会呈现某些性态，利用这些性态可完成图象处理中某个应用领域的应用。应选择什么样的变换才能满足各种要求是下面要讨论的主要问题之一。,变换选择的原则,1)变换必须是可逆的。2)变换不能损失信息。3)变换必须是有好处的。4)变换算法必须是不复杂的。,第一节 概述和分类,图象变换是许多图象处理和分析技术的基础，本章的主要目的是建立起图象变换及其性质的理论基础。把傅里叶变换放在主要地位反映了它在图象处理问题中应用的广泛性。对图象进行变换的目的：为了便于对图象进行分析，如对图象进行特征提取、匹配、识别；为了便于对图象进行处理，如简化处理操作、提高运算效率；为了便于对图象数据进行压缩，提高传输效率等,第三章 图象变换,第一节 概述和分类,图像变换的一种分类方法：可分离变换：傅里叶变换及性质 快速傅里叶变换 其它可分离变换统计变换：霍特林变换另一种分类方法：正弦型变换：傅里叶变换、DCT方波型变换：Walsh变换、Hadamard变换、Haar变换、Slant变换 基于特征向量的变换：霍特林变换,第三章 图象变换,第二节 傅里叶变换,1-D傅里叶变换 设长度为N的离散序列为f(0),f(1),f(2),，f(N-l)。则其离散傅里叶变换对定义为：,第三章 图象变换,第二节 傅里叶变换：一维,在图象处理中f(x)总是实函数，但一般F(u)是复函数，可以写成：F(u)=R(u)+j I(u)其中R(u)和I(u)分别为F(u)的实部和虚部。上式也常写成指数形式：F(u)=|F(u)|exp j(u),第三章 图象变换,第二节 傅里叶变换：一维,幅度函数|F(u)|和相位函数(u)为：|F(u)|=R2(u)+I2(u)1/2(u)=arctan I(u)/R(u)|F(u)|又称为f(x)的傅里叶频谱，(u)称为相位角。频谱的平方称为f(x)的功率谱或频谱密度，记为P(u)：P(u)=|F(u)|2=R2(u)+I2(u),第三章 图象变换,第二节 傅里叶变换：一维,指数项可借助欧拉公式写为：exp-j2 u x=cos（2 u x）-j sin（2 u x）由于每个u值都确定所对应的正弦和余弦对的频率，所以称为频率变量。,第三章 图象变换,第二节 傅里叶变换：二维,2-D傅里叶变换 图象f(x,y)的2-D傅里叶变换对是1-D傅里叶变换对的推广：,第三章 图象变换,第二节 傅里叶变换：二维,2-D傅里叶变换的频谱、相位角和功率谱如下：频谱：|F(u,v)|=R2(u,v)+I2(u,v)1/2 相位角：(u,v)=arctan I(u,v)/R(u,v)功率谱：P(u,v)=|F(u,v)|2=R2(u,v)+I2(u,v),第三章 图象变换,第二节 傅里叶变换：二维,第三章 图象变换,第二节 傅里叶变换：二维,第三章 图象变换,傅氏变换,离散变换,线性系统,第二节 傅里叶变换：二维,一幅集成电路的扫描电子显微镜图象,放大将近2500倍,第二节 傅里叶变换：二维变换特性,二维傅立叶变换特性可分离性周期与共轭对称平移性旋转特性,线性与相似性 均值性 拉普拉斯 卷积与相关,第三章 图象变换,第二节 傅里叶变换：二维变换特性,可分离性二维离散傅立叶变换DFT可分离性的基本思想是：二维DFT可分离为两次一维DFT应用：二维快速傅立叶算法FFT，是通过计算两次一维FFT实现的,第三章 图象变换,第二节 傅里叶变换：二维变换特性,可分离性的定义,第三章 图象变换,第二节 傅里叶变换：二维变换特性,可分离性成立的推导先对列（y变量）做变换：N-1F(x,v)=1/N f(x,y)exp(-j2vy/N)y=0然后对行（x变量）进行变换：M-1F(u,v)=1/N F(x,v)exp(-j2ux/N)x=0,第三章 图象变换,第二节 傅里叶变换：二维变换特性,第三章 图象变换,行,列,第二节 傅里叶变换：二维变换特性,平移性质f(x，y)expj2(u0 x+v0y)N F(u-u0,v-v0)f(x-x0，y-y0)F(u,v)exp-j2(u0 x+v0y)N 将f(x,y)与一个指数项相乘就相当于把其变换后的频域中心移动到新的位置。将F(u,v)与一个指数项相乘就相当于把其反变换后的空域中心移动到新的位置。同时可知，对f(x，y)的平移不影响其傅里叶变换的幅值。该两式的证明可直接从傅里叶变换的定义式获得。,第三章 图象变换,平移性（不影响幅值，由级数展开可得出对应关系）表明原f（x,y）用f（x,y）exp-2j（u0 x+v0y）/N替换后进行傅里叶变换，则变换后的频域中心平移到了新位置。与上述频域平移类似，f（x,y）F（u-u0,v-v0）表明F（u,v）与一个指数项相乘后再进行傅里叶反变换，则变换后的空域中心平移到了新位置。空域平移。即 f（x-x0,y-y0）F（u,v）。,举例：当 时有：可以简单的用 乘以 将 的傅里叶变换的原点移动到相应频率方阵的中心。图像的离散傅里叶变换举例：,平移性质 平移性质表明，只要将f(x,y)乘以因子(1)x+y，再进行离散傅立叶变换，即可将图像的频谱原点（0，0）移动到图像中心（M2,N2）处。图7-5是简单方块图像平移的结果。,图7-5 傅立叶频谱平移示意图(a)原图像；（b）无平移的傅立叶频谱；（c）平移后的傅立叶频谱,第二节 傅里叶变换：二维变换特性,周期性和共扼对称性 傅里叶变换和反变换均以N为周期，即：F(u，v)=F(u+N，v)=F(u,v+N)=F(u+N,v+N)上式可通过将右边几项分别代入傅里叶变换的定义式来验证。,第三章 图象变换,第二节 傅里叶变换：二维变换特性,证明：所以上式成立。,第三章 图象变换,第二节 傅里叶变换：二维变换特性,周期性表明，尽管F(u,v)对无穷多个u和v的值重复出现，但只需根据在任一个周期里的N个值就可以从F(u,v)得到f(x，y)。同样的结论对f(x，y)在空域也成立。如果f(x,y)是实函数，则有共扼对称性：F(u，v)=F*(-u,-v)|F(u，v)|=|F(-u,-v)|,第三章 图象变换,第二节 傅里叶变换：二维变换特性,证明：因为f(x,y)是实函数，所以f(x,y)=f*(x,y)，证毕。,第三章 图象变换,第二节 傅里叶变换：二维变换特性,旋转性质 f(r,+0)F(w，+0)上式表明，对f(x,y)旋转0对应于将其傅里叶变换F（u,v)也旋转0。类似地，对F(u,v)旋转0也对应于将其傅里叶反变换f(x,y)旋转0。证明可首先进行极坐标变换 x=rcos，y=rsin，u=wcos，v=wsin，将f(x,y)和F(u,v)转换为f(r,)和F(w,)，直接将它们代入傅里叶变换对即可得到。,第三章 图象变换,旋转不变性 由旋转不变性可知，如果时域中离散函数旋转0角度，则在变换域中该离散傅立叶变换函数也将旋转同样的角度。离散傅立叶变换的旋转不变性如图7-6所示。,图7-6 离散傅立叶变换的旋转不变性（a）原始图像；（b）原始图像的傅立叶频谱；（c）旋转45后的图像；（d）图像旋转后的傅立叶频谱,第二节 傅里叶变换：二维变换特性,分配律 根据傅里叶变换对的定义可直接得到：Ff1(x,y)+f2(x,y)=F f1(x,y)+F f2(x,y)傅里叶变换和反变换对加法满足分配律，但对乘法则不满足，即一般有：Ff1(x,y)f2(x,y)F f1(x,y)F f2(x,y),第三章 图象变换,第二节 傅里叶变换：二维变换特性,尺度变换(缩放)给定二个标量a和b，则对傅氏变换有以下2式成立：a f(x,y)a F(u,v)f(ax,by)（1/|ab|）F(u/a,v/b)证明：f(ax,by)的傅里叶变换为：（令x1=ax，y1=by）证毕。,第三章 图象变换,第二节 傅里叶变换：二维变换特性,平均值 对一个2-D离散函数f(x,y),其平均值为：因为，对一个2-D离散函数f(x,y)：,第三章 图象变换,第二节 傅里叶变换：二维变换特性,如将u=v=0代入傅里叶变换定义式，可以得到：比较以上两式可得f(x,y)的平均值与傅里叶变换的关系。,第三章 图象变换,第二节 傅里叶变换：二维变换特性,卷积定理对1-D连续情况，两个函数的卷积定义为：卷积定理：如果f(x)的傅里叶变换是F(u)，g(x)的傅里叶变换是 G(u)，那么：f(x)*g(x)F(u)G(u)f(x)g(x)F(u)*G(u),第三章 图象变换,第二节 傅里叶变换：二维变换特性,离散卷积定理 根据傅里叶变换和反变换的周期性，假设f(x)和g(x)具有周期M，则卷积结果具有相同的周期。只有当M A+B-1时，卷积的周期才不会重迭，否则卷积结果就会产生重迭(wrap-around)误差。若给上述二个序列加一些零以得到其长度为M的扩展序列：,第三章 图象变换,第二节 傅里叶变换：二维变换特性,它们的离散卷积可如下定义：用fe(x)和g e(x)就可以避免重迭误差，卷积定理对离散序列仍可成立。,第三章 图象变换,第二节 傅里叶变换：二维变换特性,例 1 函数卷积示例,第三章 图象变换,第二节 傅里叶变换：二维变换特性,例 2 连续卷积和离散卷积的比较,第三章 图象变换,第二节 傅里叶变换：二维变换特性,两个2-D函数的卷积定义为：2-D卷积定理：f(x,y)*g(x,y)F(u,v)G(u,v)f(x,y)g(x,y)F(u,v)*G(u,v),第三章 图象变换,卷积与傅里叶变换的关系 两个函数卷积的傅里叶变换对应于两个函数傅里叶变换的乘积；许多图像变换是卷积运算 在频域的乘积运算比在空域的卷积运算快，特别是有了快速傅立叶变换以后，效果更加明显。两个函数乘积的傅里叶变换对应于两个函数傅里叶变换的卷积；,第二节 傅里叶变换：二维变换特性,为求得2-D的离散卷积，可让f(x,y)和g(x,y)分别用尺寸为AB和CD，周期为M和N的离散数组表示。这里需要选择M A+C-l和N B+D-1以避免重迭误差。周期性扩展序列构造如下：,第三章 图象变换,第二节 傅里叶变换：二维变换特性,它们的离散卷积可如下定义：与一维情况同样，只要我们利用fe(x,y)和g e(x,y)就可以避免重迭误差，卷积定理对2-D离散情况仍成立。,第三章 图象变换,第二节 傅里叶变换：二维变换特性,相关定理对l-D连续情况，二个函数的相关定义为：如果f(x)和g(x)是同一个函数，上式算得的结果常称为自相关。而如果f(x)和g(x)不是同一个函数，则算得的结果常称为互相关。,第三章 图象变换,第二节 傅里叶变换：二维变换特性,例 一维函数相关示例：,第三章 图象变换,第二节 傅里叶变换：二维变换特性,定义1-D离散相关：进一步可对2-D连续和离散相关分别定义如下：,第三章 图象变换,相关与傅里叶变换的关系 相关主要应用于模板和原型匹配给定一个未知图像和已知图像集之间求最紧密的匹配。其基本途径是求相关，然后取相关函数最大值。,第二节 傅里叶变换：二维变换特性,对卷积和相关，要求f(x,y)和g(x,y)是周期为M和N的离散数组。这里需要选择M A+C-l和N B+D-1以避免重迭误差。周期性序列fe(x,y)和ge(x,y)为：,第三章 图象变换,由采样重建图象,问题的提出：连续时间信号先要在时间和幅度上进行离散化后才能被计算机处理。同理，连续图象信号也首先要在时间和幅度上进行离散化后才能被计算机处理。为了达到对原来连续时间信号或连续图像信号较好的近似，或者说要使经采样后得到的离散数字信号或数字图象不失真，需要多大的采样率？是不是越高越好？最低不能低于多少？,1、抽样定理,如果函数 f(x)在 x=T 处连续，则函数 f(x)在时间 T 的一个样本表示为：,函数的抽样波形：如果函数f(t)在 x=nT=nx，n0，1，2 处连续，则称,为 f(x)函数的抽样波形。,函数的抽样波形是一个等间隔的无限脉冲序列，每一个脉冲的幅度就等于函数f(x)在脉冲出现时刻的值。定义：为采样函数。,函数的抽样波形,实际上就是连续函数 f(x)和脉冲序列 s(x)的乘积。,相乘,函数的抽样后的频域波形,应用频率的卷积定理，连续函数 f(x)和脉冲序列的乘积就等于频域中两个函数的傅立叶变换的卷积的傅立叶逆变换。,混迭效应,如果时域的抽样间隔时间太大，则等距脉冲序列 f 的间隔太小，它们与频率函数 F(u)的卷积就产生了波形的相互重迭，抽样后函数的傅立叶变换的这种畸变称为混迭效应。,卷积,逆变换,-fc,fc,F(u),F(u)S(u),S(u),u,u,u,截止频率,函数 f(x)的傅立叶变换(即F(u)的最高频率称为截止频率。如下面(a)图所示，其中的 fc 即为截止频率。,避免混迭效应：如果抽样间隔 T 等于截止频率倒数的一半，混迭效应就不会出现。此时，脉冲序列 S(u)的间隔为 2fc，如上面(b)图所示。,结论抽样定理的两个条件,1)、要保证信号信息不丢失对于比 fc 高的频率，f(x)的傅立叶变换必须为零(带限)。,2)、抽样间隔选择为 T=1/2fc。这是使抽样定理成立的最小抽样间隔。,2fc 称为奈奎斯特采样频率。,函数的恢复从频域恢复,F(u)S(u),相乘,-fc,fc,F(u),逆变换,x,f(x),u,u,2、有限区间函数的采样与恢复,结论：在频域中处理经截断后的信号，不可能完全恢复原信号状态；但是能够恢复截断部分的采样信号。,h(x),x,1,X,H(u)*F(u)*S(u),u,混迭效应,f(x)s(x),x,K,H(u),u,设图像f(x,y)是一连续二维信号，其空间频谱F(fx,fy)在x方向具有截止频率Wu，在y方向具有截止频率Wv。所谓采样是对f(x,y)乘以空间采样函数：,式中x和y为x、y两个方向的采样间隔，上式为脉冲函数(x,y)沿x、y两个方向的展开。,3、二维连续图像信号的采样,第二节 傅里叶变换：由采样重建图象,第三章 图象变换,对一个带限函数f(x,y)(即它的傅立叶变换在某个有限区间R外为零),如果选择如下频域里的函数(见上图b)与f(x,y)和s(x,y)的乘积的傅立叶变换相乘,就有可能完全恢复f(x,y),如果设2 Wu和2Wv分别为能完全包含R的最小长方形在U和V方向的长度,并通过选择采样间隔使之满足下式,就能由采样完全重建f(x,y),练 习 题,（P70）3538,第三章 图象变换,第三节 快速傅里叶变换,快速傅里叶变换算法原理我们只考虑1-D的情况，因为2-D傅里叶变换可由连续两次1-D傅里叶变换得到。已知1-D傅里叶变换：,第三章 图象变换,第三节 快速傅里叶变换,为计算全部的傅里叶系数，需要：复数乘法（N2）和加法（N（N-1）它们的次数都正比于N2。注意到 exp-j2ux/N可只计算一次然后存放在一个表中以备查用，所以正确地分解上式可将复数乘法和加法的次数减少为正比于Nlog2N。这个分解过程称为快速傅里叶变换(FFT)算法。FFT算法与原始变换算法的计算量之比是log2N/N，当 N比较大时，计算量的节省是相当可观的。,第三章 图象变换,第三节 快速傅里叶变换,FFT算法基本思想 FFT算法基于一个叫做递推加倍的方法。为方便起见我们用下式表达离散傅立叶变换公式 N-1F(u)=1/Nf(x)(WN)ux x=0 这里 WN=exp(-j2/N)是一个常数,第三章 图象变换,第三节 快速傅里叶变换,假设N为：N=2n 其中n是一个正整数，因此N可表示为：N=2M 这里M仍然是一个正整数。将N=2M代入上式，得到：2M-1 F(u)=1/(2M)f(x)(W2M)ux x=0 M-1 M-1=1/2 1/Mf(2x)W2Mu(2x)+1/Mf(2x+1)W2Mu(2x+1)x=0 x=0,第三章 图象变换,第三节 快速傅里叶变换,由于：WN=exp(-j2/N)W2M2ux=exp-j22ux/2M=exp-j2ux/M=WMux 所以：W2M2xu=Wmxu 代入上式有：M-1 M-1 1/21/Mf(2x)Wmux+1/Mf(2x+1)WMux W2Mu x=0 x=0,第三章 图象变换,第三节 快速傅里叶变换,定义两个符号：M-1 Feven(u)=1/Mf(2x)Wmux 偶数部分 x=0u=0,1,2,M-1 M-1 Fodd(u)=1/Mf(2x+1)Wmux 奇数部分 x=0 u=0,1,2,M-1,第三章 图象变换,第三节 快速傅里叶变换,得出FFT 的第一个递推公式：F(u)=1/2(Feven(u)+Fodd(u)W2Mu)该公式说明F(u)可以通过奇部和偶部之和来计算,第三章 图象变换,第三节 快速傅里叶变换,另有：WMu+M=exp-2j(u+M)/M=exp-2ju/Mexp-2j=WMuej(-2)=WMu(-1)(-2)=Wmu且：W2Mu+M=exp-2j(u+M)/2M=exp-2ju/2M ej(-1)=W2Mu(-1)(-1)=-W2Mu最后有：WMu+M=Wmu；W2Mu+M=-W2Mu,第三章 图象变换,第三节 快速傅里叶变换,因为：WMu+M=Wmu；W2Mu+M=-W2Mu得出u+M 的DFT为：M-1F(u+M)=1/2 1/Mf(2x)WM(u+M)x+x=0 M-1 1/Mf(2x+1)WM(u+M)x W2Mu+M x=0=1/2(Feven(u)-Fodd(u)W2Mu),第三章 图象变换,第三节 快速傅里叶变换,得出FFT的第二个递推公式：F(u+M)=1/2(Feven(u)-Fodd(u)W2Mu)该公式说明F(u+M)可以通过F(u)偶部和奇部之差来计算,第三章 图象变换,第三节 快速傅里叶变换,分析这些表达式得到如下一些有趣的特性：（1）一个N个点的变换，能够通过将原始 表达 式分成两个部分来计算（2）通过计算两个（N/2）个点的变换。得到 Feven(u)和 Fodd(u)（3）奇部与偶部之和得到F(u)的前(N/2)个值。（4）奇部与偶部之差得到F(u)的后(N/2)个值。且不需要额外的变换计算。,第三章 图象变换,第三节 快速傅里叶变换,归纳快速傅立叶变换的思想：1）通过计算两个单点的DFT，来计算两个点的DFT，2）通过计算两个双点的DFT，来计算四个点的DFT，以此类推3）对于任何N=2m的DFT的计算，通过计算两个N/2点的DFT，来计算N个点的DFT,第三章 图象变换,第三节 快速傅里叶变换,第三章 图象变换,第三节 快速傅里叶变换,逆向FFT算法算法思想描述：用正向变换计算逆向变换 N-1F(u)=1/N f(x)exp-j2ux/N x=0u=0,1,2,.N-1 N-1 f(x)=F(u)expj2ux/N u=0 x=0,1,2,.N-1,第三章 图象变换,第三节 快速傅里叶变换,在离散逆向变换表达式两边同取共轭，并除N N-11/Nf*(x)=1/N F*(u)exp-j2ux/N u=0u=0,1,2,.N-1 用正向变换算法计算，得到1/Nf*(x)，取共轭并乘上N，即得到f(x),第三章 图象变换,第三节 快速傅里叶变换,算法实现 实现按时间抽取FFT算法的关键是将输入数据排列成满足连续运用奇偶分解所需的次序。对输入数据的排序可根据一个简单的位对换规则进行（称为倒位序）。如用x表示f(x)的一个自变量值，那么它排序后对应的值可通过把x表示成二进制数并(左右)对换各值得到。当把输入数据进行了重新排序，则输出结果是正确的次序。不把输入数据进行排序，则输出结果需要重新排序才能得到正确的次序。,第三章 图象变换,第三节 快速傅里叶变换,第三章 图象变换,第三节 快速傅里叶变换,例：N=23，f(6)排序后为f(3)，因为6=1102倒位序后0112=3。0 1 2 3 4 5 6 7 输入000 001 010 011 100 101 110 111 自然序000 100 010 110 001 101 011 111 倒位序 0 4 2 6 1 5 37 FFT的输入序,第三章 图象变换,按照前面叙述的FFT方法,第1层(4组2个点的运算)：,同理：,第2层（2组4个点的运算）：,同理：,第3层（1组8个点的运算）：,算法计算量比较 N FT FFT 倍数 8 64 24 2.7 128 16384 896 18.3256 65535 2048 32 1024 1024*1024 22528 102.42048 2048*2048 22528 186.2,练 习 题,（P71）310、312、,第三章 图象变换,傅立叶变换的优点与主要问题,优点：1)、傅立叶变换的系数恰好表现的是被变换信号各个频率点上的幅值。可以根据要求精确地设计滤波器滤除不需要的频率成分。对图象而言，高频部分代表细节；低频部分表示背景或大面积的灰度变化不剧烈的部分。2)、利用卷积定理可以方便地对图象进行滤波处理。缺点：傅立叶变换的参数都是复数，在数据的描述上相当于实数的两倍。,第四节 其它可分离图象变换,可分离变换1-D变换的一般形式可用下式表示：其中T(u)为f(x)的变换，g(x,u)称为正向变换核。反变换可表示为：其中h(x,u)称为反向变换核。,第三章 图象变换,第四节 其它可分离图象变换,对2-D的情况，正变换和反变换可分别表示为：,第三章 图象变换,第四节 其它可分离图象变换,如果：g(x,y,u,v)=g1(x,u)g2(y,v)成立 则称正向变换核是可分离的。如果g1与g2的函数形式一样，则称正向变换核是对称 的。即：g(x,y,u,v)=g1(x,u)g1(y,v),第三章 图象变换,第四节 其它可分离图象变换,前面讨论的傅里叶变换是可分离变换中的一个特例。例：傅里叶变换的正向变换核：g(x,y,u,v)=exp-j2(ux+vy)/N/N 它是可分离的和对称的，因为：g(x,y,u,v)=g1(x,u)g1(y,v),第三章 图象变换,第四节 其它可分离图象变换,只有可分离变换核的2-D变换可分成两个步骤计算，每个步骤用一个 l-D变换：先沿f(x,y)的每一行进行 l-D变换，x,v=0，l，N-l 然后沿T(x,v)的每一列进行1-D变换得到：u,v=0，l，N-l,第三章 图象变换,第四节 其它可分离图象变换,当g(x,y,u,v)是可分离的和对称的，图象变换的矩阵形式：T=AFA F是NN图象矩阵，A是NN对称变换矩阵，T是输出的NN变换结果。从反变换式，有：F=BTB 将T=AFA代入上式，则：F=BAFAB 如果B=A-1，这表明图象 F可完全由其变换恢复。,第三章 图象变换,第四节 其它可分离图象变换,如果B不等于A-1，则得F的一个近似：利用矩阵形式的一个优点是，所得到的变换矩阵可分解成若干个具有较少非零元素的矩阵的乘积，这样可减少冗余并减少操作次数。,第三章 图象变换,第四节 其它可分离图象变换,沃尔什变换 沃尔什变换其变换核是由+1和-1组成的，因此在变换过程中只有加法和减法，计算速度快而且易于用硬件实现。当 N=2n 时，沃尔什变换核为：,第三章 图象变换,第四节 其它可分离图象变换,函数 f(x)的离散沃尔什(Walsh)正变换W(u)为：由沃尔什变换核组成的矩阵是一个对称矩阵并且其行和列正交。,第三章 图象变换,由美国数学家Walsh提出而得名；沃尔什变换（WT）的变换核及其变换（设N=2n）一维正变换核：沃尔什正变换：式中 是z的二进制表达中的第k位（取0或1值）；例如n=3时，若z=6=1102，则b2（z）=1，b1（z）=1，b0（z）=0。,举例，Walsh变换核的值求解过程：设N=8（n=3），则 求g（0,0），即x=0=0002；u=0=0002，显然，b2（0）=0，b1（0）=0，b0（0）=0，所以，g（0,0）=（1/8）(-1)0*0(-1)0*0(-1)0*0=（1/8）。,第四节 其它可分离图象变换,N=8时1-D的沃尔什变换核的值(常数 l/N略去）。例如x=6(110)，u=1(001)，则bi(x)bn-1-i(u)=1+0+0=1，所以系数为-1。,第三章 图象变换,第四节 其它可分离图象变换,离散沃尔什反变换核为：所以离散沃尔什反变换为：沃尔什正变换和反变换只差一个常数项 l/N，所以用于正变换的算法也可用于反变换。,第三章 图象变换,第四节 其它可分离图象变换,2-D沃尔什正变换和反变换：沃尔什正变换核和反变换核都是可分离的和对称的，g(x,y,u,v)=g1(x,u)g1(y,v)=h1(x,u)h1(y,v)2-D的沃尔什正反变换都可分成两个步骤计算，每个 步骤用一个1-D变换实现。,第三章 图象变换,第四节 其它可分离图象变换,沃尔什变换可用类似于FFT算法快速地计算，只需将那里的指数项设为“l”即可。快速沃尔什变换为（FWT）：W(u)=Weven(u)+Wodd(u)/2 W(u+M)=Weven(u)-Wodd(u)/2,第三章 图象变换,第四节 其它可分离图象变换,图象变换可以通过对核进行恰当的级数展开来得到 由于正向变换核和反向变换核只依赖于x，y，u,v而与f(x,y)或F(u,v)的值无关。这些核可看作一组基本函数，一旦图象尺寸确定这些函数也完全确定。例如对沃尔什变换：W=UFV=(uo t uN-1 t)F ui t vj即为基本函数。,第三章 图象变换,第四节 其它可分离图象变换,例如对N=4，l-D沃尔什变换核的值：,第三章 图象变换,第四节 其它可分离图象变换,则：uo=(1 1 1 1),vo=(1 1 1 1),u1=(1 1 1 1),v1=(1 1 1 1),u2=(1 1 1 1),v2=(1 1 1 1),u3=(1 1 1 1)，v3=(1 1 1 1),第三章 图象变换,第四节 其它可分离图象变换,第三章 图象变换,二维沃尔什变换对的定义,例：用44沃尔什变换阵G对给定图像f1(x,y)和f2(x,y)进行变换，求其变换后的“图像”W1(u,v)和W2(u,v)。,能量集中在边角！且图像越平滑能量越集中。,第四节 其它可分离图象变换,哈达玛变换(Hadamard)正向哈达玛变换核定义如下：l-D的离散哈达玛变换H(u)为：,第三章 图象变换,第四节 其它可分离图象变换,N=8时1-D哈达玛变换核的值 与沃尔什变换类似，由哈达玛变换核组成的矩阵是个对称矩阵并且其行和列正交。,第三章 图象变换,第四节 其它可分离图象变换,同样反变换核与正变换核只差一个常数 l/N，即：离散哈达玛反变换为：,第三章 图象变换,第四节 其它可分离图象变换,1-D的哈达玛正变换和反变换只差一个常数项1/N，所以用于正变换的算法也可用于反变换。2-D的哈达玛正变换和反变换：,第三章 图象变换,第四节 其它可分离图象变换,同样，哈达玛正变换核和反变换核都是可分离的和对称的，所以2-D的哈达玛正变换和反变换都可分成两个步骤计算，每个步骤用一个1-D变换实现。在绝大多数图象变换应用中有N=2 n成立，所以沃尔什变换和哈达玛变换常混合使用。沃尔什-哈达玛变换常用来指两者中的任一个。,第三章 图象变换,第四节 其它可分离图象变换,在选择采用哪个变换时有两个因素需要考虑：（1）FWT可直接写成逐次加倍的形式，所以可以靠修改FFT算法得到。而为了计算快速哈达玛变换（FHT)，需要进一步考虑数据的排序。当然也可以先用FWT然后再将结果排序以得到哈达玛变换。（2）尽管哈达码变换的排序问题使得它不易直接用逐次加倍的方式实现，但哈达码变换具有的简单迭代性质可以方便地产生实现运算所必需的变换矩阵。,第三章 图象变换,第四节 其它可分离图象变换,快速哈达玛变换（FHT）：最小阶(N=2)的哈达玛矩阵是：如果用 HN代表N阶哈达玛变换矩阵，则HN满足迭代关系：,第三章 图象变换,例如：N=8时，有哈达玛变换阵,每一行的符号的变化次数称作这个行的列率。,哈达玛变换的正反变换核是一样的。变换核生成有一规律，使其生成非常方便(如果图像是NN，N=2n)。,第四节 其它可分离图象变换,沿哈达玛矩阵某一列的符号变换次数常称为该列的阶或序。前述N=8哈达玛矩阵的序依次为0,7,3,4,1,6,2和5。我们可以定义随u增加而序也增加的哈达玛变换核。以下两式给出满足该条件的1-D哈达玛变换对：,第三章 图象变换,第四节 其它可分离图象变换,其中：,第三章 图象变换,第四节 其它可分离图象变换,N=8时经过排序的1-D哈达玛变换核的值：经过排序的2-D哈达玛变换核同样是可分离并且对称的。,第三章 图象变换,第四节 其它可分离图象变换,第三章 图象变换,第四节 其它可分离图象变换,离散余弦变换1-D离散余弦变换(DCT)和其反变换由以下2式定义：其中a(u)由下式定义：,第三章 图象变换,第四节 其它可分离图象变换,其矩阵形式为：,第三章 图象变换,第四节 其它可分离图象变换,2-D的 DCT对由下面两式定义：经DCT变换后信号的能量将向左上角集中，因而有利于图象数据的压缩。,第三章 图象变换,第四节 其它可分离图象变换,N=4时经过排序的DCT基本函数的图示,第三章 图象变换,第四节 其它可分离图象变换,哈尔变换 哈尔(Haar)变换基于定义在连续闭区间0,1上的哈尔函数hk(z)，其中k=0,1,2,N-1，要求N=2n。哈尔函数：,第三章 图象变换,第四节 其它可分离图象变换,其中：整数k可被唯一地分解（即对于任意的k0，总存在2的最大幂2 p和余数q-1）：k=2 p+q-1 k=2 p+q-1（k=0,1,2,N-1，要求N=2n）其中 0 p n-1，当p=0时，q=0 或q=1，当p=1时，q=1、2，当p=2时，q=1、2、3、4，即当p 0时，1 q 2 p。例如对N=4，当k=0时有p=0和q=0，而当k=1时有p=0和q=1。在这里p规定了尺度，q规定了平移量。,第三章 图象变换,第四节 其它可分离图象变换,根据哈尔函数可得出哈尔矩阵。对1个NN矩阵，其第i行是由z=0/N，1/N，(N-1)N的h i(z)的元素构成。哈尔矩阵A为：,第三章 图象变换,第四节 其它可分离图象变换,例如N=2时，哈尔矩阵为：,第三章 图象变换,第四节 其它可分离图象变换,例如N=8时，哈尔矩阵为：哈尔矩阵是正交矩阵，它具有实现快速变换所需的性质。由于哈尔矩阵中有许多常数和“0”，所以哈尔变换可以很快地计算出来。,第三章 图象变换,第四节 其它可分离图象变换,N=8时哈尔变换的基函数,第三章 图象变换,第四节 其它可分离图象变换,斜变换 斜(slant)变换也称斯拉特变换。设N为偶数，一个 NN阶的斯拉特矩阵由下列迭代关系定义：,第三章 图象变换,第四节 其它可分离图象变换,第三章 图象变换,第四节 其它可分离图象变换,例 斯拉特矩阵示例 N=4时的斯拉特矩阵为：,第三章 图象变换,第四节 其它可分离图象变换,N=8时的斯拉特矩阵系数图示,第三章 图象变换,练 习 题,（P71）316317 318,第三章 图象变换,第五节 霍特林变换,霍特林(Hotelling)变换是基于图象统计特性的变换，霍特林变换也常称为特征值变换、主分量变换或离散K-L变换。霍特林变换的突出优点是去相关性好，主要用于数据压缩和图象旋转上。,第三章 图象变换,第五节 霍特林变换,设给定一组M个随机矢量（即x有M个样本）：k=1,2,M 这组随机矢量的均值矢量为：m x=Ex 这组随机矢量的协方差矩阵为：C x=E（x-m x）（x-m x）T,第三章 图象变换,第五节 霍特林变换,若是从同一个随机母体得到了M个矢量采样，则其均值矢量和协方差矩阵可分别用以下两式来近似：,第三章 图象变换,第五节 霍特林变换,例 协方差矩阵计算示例 设有4个矢量 x1=0 0 0T，x2=1 0 0T，x3=1 1 0T，x4=1 0 1T，则可得均值矢量为：m x=1/4 3 1 1 T,第三章 图象变换,第五节 霍特林变换,第三章 图象变换,第五节 霍特林变换,因为矩阵C x是一个实对称矩阵，所以总可以找到它的一组N个正交特征值。令ei和i(i=1,2,N-1)分别为C x的特征矢量和对应的特征值，再令A为由C x的特征矢量组成的矩阵，则霍特林变换定义为：y=A(x-mx),第三章 图象变换,第五节 霍特林变换,由这个变换得到的y 矢量其均值为零，协方差矩阵为对角矩阵，即：my=0 C y=A C x AT,第三章 图象变换,第五节 霍特林变换,证明：因为my=EY=EA（X-m x）=AEX-A m x=0 所以 my=0 而 y矢量的协方差矩阵可由A和C x得到：因为C y=E（Y-m y）（Y-m y）T=EY YT=E（AX-Am x）（AX-Am x）T=EA（X-m x）（X-m x）TAT=A E（X-m x）（X-m x）TAT=A C x AT(该变换即是对C x的对角化变换)所以 C y=A C x AT=C y是一个对角矩阵，它的主对角线上的元素正是C x的特征值。,第三章 图象变换,第五节 霍特林变换,霍特林变换的性质：变换后的图象向量Y的均值向量my为0向量；Y向量的协方差矩阵C y=A C x AT；协方差矩阵C y为对角矩阵，其对角线上的元素等于C x的特征值，这说明向量Y的元素是不相关的。霍特林变换的突出优点是去相关性好，主要用于数据压缩和图象旋转上，另外也作为评价图象变换性能优劣的标准。,第三章 图象变换,第五节 霍特林变换,霍特林变换应用的例子：,第三章 图象变换,第五节 霍特林变换,（1）原始数据的分布指明了特征向量的方向；（2）利用变换y=A(x-mx)作数据旋转和中心化。,第三章 图象变换,第五节 霍特林变换,用霍特林变换将x映射到y实际上是建立了一个新的坐标系，其坐标轴在C x的特征矢量方向上。借助这个坐标系可看出，霍特林变换是一个将物体沿特征矢量对齐的旋转变换，这个变换将数据解除了相关。另外，特征值是沿C y的主对角线的，所以i是沿特征矢量ei的yi分量的方差。,第三章 图象变换,第五节 霍特林变换,第三章 图象变换,第五节 霍特林变换,从 y重建x：A的各行都是正交归一化矢量，从而A-1=AT，所以任一个矢量x都可由y 恢复：x=AT y+m x 当用对应C x 中K个最大特征值的K个特征矢量构造变换矩阵Ak，这样得到的y矢量是K阶的，因而重建的 x就只是一个近似而不再精确了。用Ak 重建的矢量为：,第三章 图象变换,第五节 霍特林变换,可以证明x和 x 之间的均方误差是：上式表明，如果K=N（即如果在变换中利用所有特征矢量)则误差为零。因为i是单调减小的，所以上式也表明，通过选择对应最大特征值的K个特征矢量可以使得x和之间的均方误差最小。这说明在最小化矢量x和它的近似x之间在均方误差的意义上，霍特林变换是最优的。,第三章 图象变换,练 习 题,（P71）320 321,第三章 图象变换,