数字图像总复习第3章

第三章图象变换3.1概述和分类3.2傅里叶变换3.3快速傅里叶变换3.4其它可分离图象变换3.5霍特林变换第三章图象变换1第一节概述和分类为了有效地和快速地对图象进行处理和分析常常需要将原定义在图象空间的图象以某种形式转换到另外一些空间，并利用在这些空间的特有性质方便地进行一定的加工,最后再转换回图象空间以得到所需的效果。这些转换方法就是本章要着重介绍和讨论的图象变换技术。第三章图象变换2图象为什么要变换利用变换的某些性质，可以大大简化或加速图象处理过程空域图象经过变换后形成“对应域图象”，从中会看到在空域图象中不易看到的某些“东西”。变换后形成“对应域图象”，会呈现某些性态，利用这些性态可完成图象处理中某个应用领域的应用。

应选择什么样的变换才能满足各种要求是下面要讨论的主要问题之一。3变换选择的原则1)变换必须是可逆的。2)变换不能损失信息。3)变换必须是有好处的。4)变换算法必须是不复杂的。

4第一节概述和分类图象变换是许多图象处理和分析技术的基础，本章的主要目的是建立起图象变换及其性质的理论基础。把傅里叶变换放在主要地位反映了它在图象处理问题中应用的广泛性。对图象进行变换的目的：为了便于对图象进行分析，如对图象进行特征提取、匹配、识别；为了便于对图象进行处理，如简化处理操作、提高运算效率；为了便于对图象数据进行压缩，提高传输效率等第三章图象变换5第一节概述和分类图像变换的一种分类方法：可分离变换：傅里叶变换及性质快速傅里叶变换其它可分离变换统计变换：霍特林变换另一种分类方法：正弦型变换：傅里叶变换、DCT方波型变换：Walsh变换、Hadamard变换、Haar变换、Slant变换基于特征向量的变换：霍特林变换第三章图象变换6第二节傅里叶变换1-D傅里叶变换

设长度为N的离散序列为{f(0),f(1),f(2),…，f(N-l)}。则其离散傅里叶变换对定义为：第三章图象变换7第二节傅里叶变换：一维

在图象处理中f(x)总是实函数，但一般F(u)是复函数，可以写成：F(u)=R(u)+jI(u)其中R(u)和I(u)分别为F(u)的实部和虚部。上式也常写成指数形式：F(u)=|F(u)|exp[j(u)]第三章图象变换8第二节傅里叶变换：一维幅度函数|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)第三章图象变换9第二节傅里叶变换：一维指数项可借助欧拉公式写为：exp[-j2ux]=cos（2ux）-jsin（2ux）由于每个u值都确定所对应的正弦和余弦对的频率，所以称为频率变量。第三章图象变换10第二节傅里叶变换：二维2-D傅里叶变换图象f(x,y)的2-D傅里叶变换对是1-D傅里叶变换对的推广：第三章图象变换11第二节傅里叶变换：二维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)第三章图象变换12第二节傅里叶变换：二维第三章图象变换13第二节傅里叶变换：二维第三章图象变换14傅氏变换离散变换线性系统第二节傅里叶变换：二维一幅集成电路的扫描电子显微镜图象,放大将近2500倍15第二节傅里叶变换：二维变换特性二维傅立叶变换特性可分离性周期与共轭对称平移性旋转特性

线性与相似性均值性拉普拉斯卷积与相关第三章图象变换16第二节傅里叶变换：二维变换特性可分离性二维离散傅立叶变换DFT可分离性的基本思想是：

二维DFT可分离为两次一维DFT应用：

二维快速傅立叶算法FFT，是通过计算两次一维FFT实现的第三章图象变换17第二节傅里叶变换：二维变换特性可分离性的定义第三章图象变换18第二节傅里叶变换：二维变换特性可分离性成立的推导先对列（y变量）做变换：

N-1F(x,v)=1/Nf(x,y)exp(-j2vy/N)]

y=0然后对行（x变量）进行变换：M-1F(u,v)=1/NF(x,v)exp(-j2ux/N)]

x=0

第三章图象变换19第二节傅里叶变换：二维变换特性第三章图象变换行列20第二节傅里叶变换：二维变换特性平移性质f(x，y)exp[j2(u0x+v0y)／N]F(u-u0,v-v0)f(x-x0，y-y0)F(u,v)exp[-j2(u0x+v0y)／N]将f(x,y)与一个指数项相乘就相当于把其变换后的频域中心移动到新的位置。将F(u,v)与一个指数项相乘就相当于把其反变换后的空域中心移动到新的位置。同时可知，对f(x，y)的平移不影响其傅里叶变换的幅值。该两式的证明可直接从傅里叶变换的定义式获得。第三章图象变换21平移性（不影响幅值，由级数展开可得出对应关系）

表明原f（x,y）用f（x,y）exp[-2j（u0x+v0y）/N]替换后进行傅里叶变换，则变换后的频域中心平移到了新位置。与上述频域平移类似，f（x,y）

F（u-u0,v-v0）表明F（u,v）与一个指数项相乘后再进行傅里叶反变换，则变换后的空域中心平移到了新位置。空域平移。即f（x-x0,y-y0）

F（u,v）。22举例：当时有：可以简单的用乘以将的傅里叶变换的原点移动到相应频率方阵的中心。图像的离散傅里叶变换举例：2324平移性质平移性质表明，只要将f(x,y)乘以因子(－1)x+y，再进行离散傅立叶变换，即可将图像的频谱原点（0，0）移动到图像中心（M／2,N／2）处。图7-5是简单方块图像平移的结果。图7-5傅立叶频谱平移示意图(a)原图像；（b）无平移的傅立叶频谱；（c）平移后的傅立叶频谱(a)(b)(c)25第二节傅里叶变换：二维变换特性周期性和共扼对称性傅里叶变换和反变换均以N为周期，即：F(u，v)=F(u+N，v)=F(u,v+N)=F(u+N,v+N)上式可通过将右边几项分别代入傅里叶变换的定义式来验证。第三章图象变换26第二节傅里叶变换：二维变换特性证明：

所以上式成立。第三章图象变换27第二节傅里叶变换：二维变换特性周期性表明，尽管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)|

第三章图象变换28第二节傅里叶变换：二维变换特性证明：因为f(x,y)是实函数，所以f(x,y)=f*(x,y)，

证毕。第三章图象变换29第二节傅里叶变换：二维变换特性旋转性质

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,)，直接将它们代入傅里叶变换对即可得到。第三章图象变换30

旋转不变性由旋转不变性可知，如果时域中离散函数旋转θ0角度，则在变换域中该离散傅立叶变换函数也将旋转同样的角度。离散傅立叶变换的旋转不变性如图7-6所示。图7-6离散傅立叶变换的旋转不变性（a）原始图像；（b）原始图像的傅立叶频谱；（c）旋转45°后的图像；（d）图像旋转后的傅立叶频谱(a)(b)(d)(c)31第二节傅里叶变换：二维变换特性分配律根据傅里叶变换对的定义可直接得到：F{f1(x,y)+f2(x,y)}=F{f1(x,y)}+F{f2(x,y)}傅里叶变换和反变换对加法满足分配律，但对乘法则不满足，即一般有：F{f1(x,y)f2(x,y)}F{f1(x,y)}F{f2(x,y)}第三章图象变换32第二节傅里叶变换：二维变换特性尺度变换(缩放)给定二个标量a和b，则对傅氏变换有以下2式成立：af(x,y)aF(u,v)f(ax,by)（1/|ab|）F(u/a,v/b)证明：f(ax,by)的傅里叶变换为：（令x1=ax，y1=by）证毕。第三章图象变换33第二节傅里叶变换：二维变换特性平均值对一个2-D离散函数f(x,y),其平均值为：

因为，对一个2-D离散函数f(x,y)：第三章图象变换34第二节傅里叶变换：二维变换特性

如将u=v=0代入傅里叶变换定义式，可以得到：

比较以上两式可得f(x,y)的平均值与傅里叶变换的关系。第三章图象变换35第二节傅里叶变换：二维变换特性卷积定理对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)第三章图象变换36第二节傅里叶变换：二维变换特性离散卷积定理根据傅里叶变换和反变换的周期性，假设f(x)和g(x)具有周期M，则卷积结果具有相同的周期。只有当MA+B-1时，卷积的周期才不会重迭，否则卷积结果就会产生重迭(wrap-around)误差。若给上述二个序列加一些零以得到其长度为M的扩展序列：第三章图象变换37第二节傅里叶变换：二维变换特性它们的离散卷积可如下定义：

用fe(x)和ge(x)就可以避免重迭误差，卷积定理对离散序列仍可成立。第三章图象变换38第二节傅里叶变换：二维变换特性例1函数卷积示例第三章图象变换39第二节傅里叶变换：二维变换特性例2连续卷积和离散卷积的比较第三章图象变换40第二节傅里叶变换：二维变换特性两个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)第三章图象变换41

卷积与傅里叶变换的关系

两个函数卷积的傅里叶变换对应于两个函数傅里叶变换的乘积；许多图像变换是卷积运算在频域的乘积运算比在空域的卷积运算快，特别是有了快速傅立叶变换以后，效果更加明显。两个函数乘积的傅里叶变换对应于两个函数傅里叶变换的卷积；42第二节傅里叶变换：二维变换特性为求得2-D的离散卷积，可让f(x,y)和g(x,y)分别用尺寸为A×B和C×D，周期为M和N的离散数组表示。这里需要选择MA+C-l和NB+D-1以避免重迭误差。周期性扩展序列构造如下：第三章图象变换43第二节傅里叶变换：二维变换特性它们的离散卷积可如下定义：与一维情况同样，只要我们利用fe(x,y)和ge(x,y)就可以避免重迭误差，卷积定理对2-D离散情况仍成立。第三章图象变换44第二节傅里叶变换：二维变换特性相关定理对l-D连续情况，二个函数的相关定义为：如果f(x)和g(x)是同一个函数，上式算得的结果常称为自相关。而如果f(x)和g(x)不是同一个函数，则算得的结果常称为互相关。第三章图象变换45第二节傅里叶变换：二维变换特性例一维函数相关示例：第三章图象变换46第二节傅里叶变换：二维变换特性定义1-D离散相关：进一步可对2-D连续和离散相关分别定义如下：第三章图象变换47

相关与傅里叶变换的关系

相关主要应用于模板和原型匹配给定一个未知图像和已知图像集之间求最紧密的匹配。其基本途径是求相关，然后取相关函数最大值。48第二节傅里叶变换：二维变换特性对卷积和相关，要求f(x,y)和g(x,y)是周期为M和N的离散数组。这里需要选择MA+C-l和NB+D-1以避免重迭误差。周期性序列fe(x,y)和ge(x,y)为：第三章图象变换49由采样重建图象问题的提出：连续时间信号先要在时间和幅度上进行离散化后才能被计算机处理。同理，连续图象信号也首先要在时间和幅度上进行离散化后才能被计算机处理。为了达到对原来连续时间信号或连续图像信号较好的近似，或者说要使经采样后得到的离散数字信号或数字图象不失真，需要多大的采样率？是不是越高越好？最低不能低于多少？

501、抽样定理如果函数f(x)在x=T处连续，则函数f(x)在时间T的一个样本表示为：函数的抽样波形：如果函数f(t)在x=nT=nΔx，n＝0，1，2…处连续，则称为f(x)函数的抽样波形。函数的抽样波形是一个等间隔的无限脉冲序列，每一个脉冲的幅度就等于函数f(x)在脉冲出现时刻的值。定义：为采样函数。51函数的抽样波形实际上就是连续函数f(x)和脉冲序列s(x)的乘积。相乘s(x)xf(x)s(x)xf(x)x52函数的抽样后的频域波形应用频率的卷积定理，连续函数f(x)和脉冲序列的乘积就等于频域中两个函数的傅立叶变换的卷积的傅立叶逆变换。卷积逆变换-fcfcS(u)F(u)F(u)

S(u)-1/Δxuuu1/Δx53混迭效应如果时域的抽样间隔时间太大，则等距脉冲序列f的间隔太小，它们与频率函数F(u)的卷积就产生了波形的相互重迭，抽样后函数的傅立叶变换的这种畸变称为混迭效应。卷积逆变换-fcfcF(u)F(u)

S(u)S(u)uuu54截止频率函数f(x)的傅立叶变换(即F(u))的最高频率称为截止频率。如下面(a)图所示，其中的fc即为截止频率。避免混迭效应：如果抽样间隔T等于截止频率倒数的一半，混迭效应就不会出现。此时，脉冲序列S(u)的间隔为2fc，如上面(b)图所示。-fcfcF(u)(a)-2fc2fcS(u)(b)uu55结论——抽样定理的两个条件1)、要保证信号信息不丢失对于比fc

高的频率，f(x)的傅立叶变换必须为零(带限)。2)、抽样间隔选择为T=1/2fc。这是使抽样定理成立的最小抽样间隔。2fc称为奈奎斯特采样频率。-fcfcF(u)u56函数的恢复——从频域恢复F(u)

S(u)相乘-fcfcF(u)逆变换xf(x)uuH(u)-fc-fcu572、有限区间函数的采样与恢复结论：在频域中处理经截断后的信号，不可能完全恢复原信号状态；但是能够恢复截断部分的采样信号。h(x)x1XH(u)*[F(u)*S(u)]u混迭效应f(x)s(x)xKH(u)u58设图像f(x,y)是一连续二维信号，其空间频谱F(fx,fy)在x方向具有截止频率Wu，在y方向具有截止频率Wv。所谓采样是对f(x,y)乘以空间采样函数：式中Δx和Δy为x、y两个方向的采样间隔，上式为脉冲函数δ(x,y)沿x、y两个方向的展开。3、二维连续图像信号的采样59第二节傅里叶变换：由采样重建图象第三章图象变换60对一个带限函数f(x,y)(即它的傅立叶变换在某个有限区间R外为零),如果选择如下频域里的函数(见上图b)与f(x,y)和s(x,y)的乘积的傅立叶变换相乘,就有可能完全恢复f(x,y)如果设2Wu和2Wv分别为能完全包含R的最小长方形在U和V方向的长度,并通过选择采样间隔使之满足下式,就能由采样完全重建f(x,y)61练习题（P70）3．53．8第三章图象变换62第三节快速傅里叶变换快速傅里叶变换算法原理我们只考虑1-D的情况，因为2-D傅里叶变换可由连续两次1-D傅里叶变换得到。已知1-D傅里叶变换：第三章图象变换63第三节快速傅里叶变换为计算全部的傅里叶系数，需要：复数乘法（N2）和加法（N（N-1））它们的次数都正比于N2。注意到exp[-j2ux/N]可只计算一次然后存放在一个表中以备查用，所以正确地分解上式可将复数乘法和加法的次数减少为正比于Nlog2N。这个分解过程称为快速傅里叶变换(FFT)算法。FFT算法与原始变换算法的计算量之比是log2N/N，当N比较大时，计算量的节省是相当可观的。第三章图象变换64第三节快速傅里叶变换FFT算法——基本思想FFT算法基于一个叫做递推加倍的方法。为方便起见我们用下式表达离散傅立叶变换公式

N-1 F(u)=1/N∑f(x)(WN)ux

x=0

这里

WN

=exp(-j2/N)是一个常数第三章图象变换65第三节快速傅里叶变换假设N为：

N=2n

其中n是一个正整数，因此N可表示为：

N=2M

这里M仍然是一个正整数。将N=2M代入上式，得到：2M-1F(u)=1/(2M)∑f(x)(W2M)ux x=0

M-1

M-1

=1/2[1/M∑f(2x)W2Mu(2x)+1/M∑f(2x+1)W2Mu(2x+1)] x=0 x=0第三章图象变换66第三节快速傅里叶变换由于：WN=exp(-j2/N)

W2M2ux

=exp[-j22ux/2M] =exp[-j2ux/M]=WMux所以：W2M2xu

=Wmxu代入上式有：M-1M-11/2[1/M∑f(2x)Wmux+1/M∑f(2x+1)WMux

W2Mu]x=0x=0第三章图象变换67第三节快速傅里叶变换定义两个符号：

M-1Feven(u)=1/M∑f(2x)Wmux偶数部分

x=0 u=0,1,2,…M-1 M-1Fodd(u)=1/M∑f(2x+1)Wmux奇数部分 x=0u=0,1,2,…M-1第三章图象变换68第三节快速傅里叶变换得出FFT的第一个递推公式：

F(u)=1/2(Feven(u)+Fodd(u)W2Mu)该公式说明F(u)可以通过奇部和偶部之和来计算第三章图象变换69第三节快速傅里叶变换另有：WMu+M=

exp[-2j(u+M)/M] =exp[-2ju/M]exp[-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第三章图象变换70第三节快速傅里叶变换因为：WMu+M=Wmu；

W2Mu+M=

-W2Mu得出u+M的DFT为：M-1F(u+M)=1/2[1/M∑f(2x)WM(u+M)x+x=0 M-1 1/M∑f(2x+1)WM(u+M)x

W2Mu+M]

x=0

=1/2(Feven(u)-Fodd(u)W2Mu)

第三章图象变换71第三节快速傅里叶变换得出FFT的第二个递推公式：

F(u+M)=1/2(Feven(u)-Fodd(u)W2Mu)

该公式说明F(u+M)可以通过F(u)偶部和奇部之差来计算第三章图象变换72第三节快速傅里叶变换分析这些表达式得到如下一些有趣的特性：（1）一个N个点的变换，能够通过将原始表达 式分成两个部分来计算（2）通过计算两个（N/2）个点的变换。得到 Feven(u)和Fodd(u)（3）奇部与偶部之和得到F(u)的前(N/2)个值。（4）奇部与偶部之差得到F(u)的后(N/2)个值。且不需要额外的变换计算。第三章图象变换73第三节快速傅里叶变换归纳快速傅立叶变换的思想：1）通过计算两个单点的DFT，来计算两个点的DFT，2）通过计算两个双点的DFT，来计算四个点的DFT，…，以此类推3）对于任何N=2m的DFT的计算，通过计算两个N/2点的DFT，来计算N个点的DFT第三章图象变换74第三节快速傅里叶变换第三章图象变换75第三节快速傅里叶变换逆向FFT算法算法思想描述：用正向变换计算逆向变换

N-1F(u)=1/Nf(x)exp[-j2ux/N]

x=0 u=0,1,2,...N-1

N-1

f(x)=F(u)exp[j2ux/N]

u=0 x=0,1,2,...N-1第三章图象变换76第三节快速傅里叶变换在离散逆向变换表达式两边同取共轭，并除N

N-11/Nf*(x)=1/NF*(u)exp[-j2ux/N]

u=0 u=0,1,2,...N-1

用正向变换算法计算，得到1/Nf*(x)，取共轭并乘上N，即得到f(x)

第三章图象变换77第三节快速傅里叶变换算法实现实现按时间抽取FFT算法的关键是将输入数据排列成满足连续运用奇偶分解所需的次序。对输入数据的排序可根据一个简单的位对换规则进行（称为倒位序）。如用x表示f(x)的一个自变量值，那么它排序后对应的值可通过把x表示成二进制数并(左右)对换各值得到。当把输入数据进行了重新排序，则输出结果是正确的次序。不把输入数据进行排序，则输出结果需要重新排序才能得到正确的次序。第三章图象变换78第三节快速傅里叶变换第三章图象变换79第三节快速傅里叶变换例：N=23，f(6)排序后为f(3)，因为6=1102倒位序后0112=3。01234567输入000001010 011100101 110111自然序000100010110001101011111倒位序0 4 2 615 3 7FFT的输入序第三章图象变换80按照前面叙述的FFT方法,第1层(4组2个点的运算)：同理：81第2层（2组4个点的运算）：同理：82第3层（1组8个点的运算）：83算法计算量比较NFTFFT倍数864242.71281638489618.32566553520483210241024*102422528102.420482048*204822528186.284练习题（P71）3．10、3．12、第三章图象变换85傅立叶变换的优点与主要问题优点：1)、傅立叶变换的系数恰好表现的是被变换信号各个频率点上的幅值。可以根据要求精确地设计滤波器滤除不需要的频率成分。对图象而言，高频部分代表细节；低频部分表示背景或大面积的灰度变化不剧烈的部分。2)、利用卷积定理可以方便地对图象进行滤波处理。缺点：傅立叶变换的参数都是复数，在数据的描述上相当于实数的两倍。

86第四节其它可分离图象变换可分离变换1-D变换的一般形式可用下式表示：

其中T(u)为f(x)的变换，g(x,u)称为正向变换核。反变换可表示为：

其中h(x,u)称为反向变换核。第三章图象变换87第四节其它可分离图象变换对2-D的情况，正变换和反变换可分别表示为：第三章图象变换88第四节其它可分离图象变换如果：g(x,y,u,v)=g1(x,u)g2(y,v)成立则称正向变换核是可分离的。如果g1与g2的函数形式一样，则称正向变换核是对称的。即：g(x,y,u,v)=g1(x,u)g1(y,v)第三章图象变换89第四节其它可分离图象变换前面讨论的傅里叶变换是可分离变换中的一个特例。例：傅里叶变换的正向变换核：g(x,y,u,v)={exp[-j2(ux+vy)/N]}/N它是可分离的和对称的，因为：g(x,y,u,v)=g1(x,u)g1(y,v)第三章图象变换90第四节其它可分离图象变换只有可分离变换核的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第三章图象变换91第四节其它可分离图象变换当g(x,y,u,v)是可分离的和对称的，图象变换的矩阵形式：

T=AFAF是N×N图象矩阵，A是N×N对称变换矩阵，T是输出的N×N变换结果。

从反变换式，有：F=BTB将T=AFA代入上式，则：F=BAFAB如果B=A-1，这表明图象F可完全由其变换恢复。第三章图象变换92第四节其它可分离图象变换如果B不等于A-1，则得F的一个近似：利用矩阵形式的一个优点是，所得到的变换矩阵可分解成若干个具有较少非零元素的矩阵的乘积，这样可减少冗余并减少操作次数。第三章图象变换93第四节其它可分离图象变换沃尔什变换沃尔什变换其变换核是由+1和-1组成的，因此在变换过程中只有加法和减法，计算速度快而且易于用硬件实现。当N=2n时，沃尔什变换核为：第三章图象变换94第四节其它可分离图象变换函数f(x)的离散沃尔什(Walsh)正变换W(u)为：由沃尔什变换核组成的矩阵是一个对称矩阵并且其行和列正交。第三章图象变换95

由美国数学家Walsh提出而得名；沃尔什变换（WT）的变换核及其变换（设N=2n）一维正变换核：

沃尔什正变换：式中是z的二进制表达中的第k位（取0或1值）；例如n=3时，若z=6=1102，则b2（z）=1，b1（z）=1，b0（z）=0。96

举例，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）。97第四节其它可分离图象变换N=8时1-D的沃尔什变换核的值(常数l/N略去）。例如x=6(110)，u=1(001)，则bi(x)bn-1-i(u)=1+0+0=1，所以系数为-1。第三章图象变换98第四节其它可分离图象变换离散沃尔什反变换核为：所以离散沃尔什反变换为：沃尔什正变换和反变换只差一个常数项l/N，所以用于正变换的算法也可用于反变换。第三章图象变换99第四节其它可分离图象变换

2-D沃尔什正变换和反变换：沃尔什正变换核和反变换核都是可分离的和对称的，g(x,y,u,v)=g1(x,u)g1(y,v)=h1(x,u)h1(y,v)2-D的沃尔什正反变换都可分成两个步骤计算，每个步骤用一个1-D变换实现。第三章图象变换100第四节其它可分离图象变换沃尔什变换可用类似于FFT算法快速地计算，只需将那里的指数项设为“l”即可。快速沃尔什变换为（FWT）：W(u)=[Weven(u)+Wodd(u)]/2W(u+M)=[Weven(u)-Wodd(u)]/2第三章图象变换101第四节其它可分离图象变换图象变换可以通过对核进行恰当的级数展开来得到由于正向变换核和反向变换核只依赖于x，y，u,v而与f(x,y)或F(u,v)的值无关。这些核可看作一组基本函数，一旦图象尺寸确定这些函数也完全确定。例如对沃尔什变换：W=UFV=(uotuN-1t)Fuitvj即为基本函数。第三章图象变换102第四节其它可分离图象变换例如对N=4，l-D沃尔什变换核的值：第三章图象变换103第四节其它可分离图象变换则：uo=(1111),vo=(1111),u1=(11–1–1),v1=(11–1–1),u2=(1–11–1),v2=(1–11–1),u3=(1–1–11)，v3=(1–1–11)第三章图象变换104第四节其它可分离图象变换第三章图象变换105二维沃尔什变换对的定义例：用4×4沃尔什变换阵G对给定图像f1(x,y)和f2(x,y)进行变换，求其变换后的“图像”W1(u,v)和W2(u,v)。106能量集中在边角！且图像越平滑能量越集中。107第四节其它可分离图象变换哈达玛变换(Hadamard)正向哈达玛变换核定义如下：l-D的离散哈达玛变换H(u)为：

第三章图象变换108第四节其它可分离图象变换

N=8时1-D哈达玛变换核的值

与沃尔什变换类似，由哈达玛变换核组成的矩阵是—个对称矩阵并且其行和列正交。第三章图象变换109第四节其它可分离图象变换同样反变换核与正变换核只差一个常数l/N，即：离散哈达玛反变换为：第三章图象变换110第四节其它可分离图象变换1-D的哈达玛正变换和反变换只差一个常数项1/N，所以用于正变换的算法也可用于反变换。2-D的哈达玛正变换和反变换：第三章图象变换111第四节其它可分离图象变换同样，哈达玛正变换核和反变换核都是可分离的和对称的，所以2-D的哈达玛正变换和反变换都可分成两个步骤计算，每个步骤用一个1-D变换实现。在绝大多数图象变换应用中有N=2n成立，所以沃尔什变换和哈达玛变换常混合使用。沃尔什--哈达玛变换常用来指两者中的任一个。第三章图象变换112第四节其它可分离图象变换在选择采用哪个变换时有两个因素需要考虑：（1）FWT可直接写成逐次加倍的形式，所以可以靠修改FFT算法得到。而为了计算快速哈达玛变换（FHT)，需要进一步考虑数据的排序。当然也可以先用FWT然后再将结果排序以得到哈达玛变换。（2）尽管哈达码变换的排序问题使得它不易直接用逐次加倍的方式实现，但哈达码变换具有的简单迭代性质可以方便地产生实现运算所必需的变换矩阵。第三章图象变换113第四节其它可分离图象变换快速哈达玛变换（FHT）：

最小阶(N=2)的哈达玛矩阵是：如果用HN代表N阶哈达玛变换矩阵，则HN满足迭代关系：第三章图象变换114例如：N=8时，有哈达玛变换阵每一行的符号的变化次数称作这个行的列率。哈达玛变换的正反变换核是一样的。变换核生成有一规律，使其生成非常方便(如果图像是N×N，N=2n)。115第四节其它可分离图象变换沿哈达玛矩阵某一列的符号变换次数常称为该列的阶或序。前述N=8哈达玛矩阵的序依次为0,7,3,4,1,6,2和5。我们可以定义随u增加而序也增加的哈达玛变换核。

以下两式给出满足该条件的1-D哈达玛变换对：第三章图象变换116第四节其它可分离图象变换其中：第三章图象变换117第四节其它可分离图象变换N=8时经过排序的1-D哈达玛变换核的值：经过排序的2-D哈达玛变换核同样是可分离并且对称的。第三章图象变换118第四节其它可分离图象变换第三章图象变换119第四节其它可分离图象变换离散余弦变换1-D离散余弦变换(DCT)和其反变换由以下2式定义：其中a(u)由下式定义：第三章图象变换120第四节其它可分离图象变换其矩阵形式为：第三章图象变换121第四节其它可分离图象变换2-D的DCT对由下面两式定义：经DCT变换后信号的能量将向左上角集中，因而有利于图象数据的压缩。第三章图象变换122第四节其它可分离图象变换N=4时经过排序的DCT基本函数的图示第三章图象变换123第四节其它可分离图象变换哈尔变换哈尔(Haar)变换基于定义在连续闭区间[0,1]上的哈尔函数hk(z)，其中k=0,1,2,,N-1，要求N=2n。哈尔函数：第三章图象变换124第四节其它可分离图象变换其中：整数k可被唯一地分解（即对于任意的k0，总存在2的最大幂2p和余数q-1）：k=2p+q-1k=2p+q-1（k=0,1,2,,N-1，要求N=2n）其中0pn-1，当p=0时，q=0或q=1，当p=1时，q=1、2，当p=2时，q=1、2、3、4，即当p0时，1q2p。例如对N=4，当k=0时有p=0和q=0，而当k=1时有p=0和q=1。在这里p规定了尺度，q规定了平移量。第三章图象变换125第四节其它可分离图象变换根据哈尔函数可得出哈尔矩阵。对1个N×N矩阵，其第i行是由z=0/N，1/N，…，(N-1)／N的hi(z)的元素构成。哈尔矩阵A为：第三章图象变换126第四节其它可分离图象变换

例如N=2时，哈尔矩阵为：

第三章图象变换127第四节其它可分离图象变换例如N=8时，哈尔矩阵为：哈尔矩阵是正交矩阵，它具有实现快速变换所需的性质。由于哈尔矩阵中有许多常数和“0”，所以哈尔变换可以很快地计算出来。第三章图象变换128第四节其它可分离图象变换N=8时哈尔变换的基函数第三章图象变换129第四节其它可分离图象变换斜变换斜(slant)变换也称斯拉特变换。设N为偶数，一个N×N阶的斯拉特矩阵由下列迭代关系定义：第三章图象变换130第四节其它可分离图象变换第三章图象变换131第四节其它可分离图象变换例斯拉特矩阵示例N=4时的斯拉特矩阵为：第三章图象变换132第四节其它可分离图象变换N=8时的斯拉特矩阵系数图示第三章图象变换133练习题（P71）3．163．173．18第三章图象变换134第五节霍特林变换霍特林(Hotelling)变换是基于图象统计特性的变换，霍特林变换也常称为特征值变换、主分量变换或离散K-L变换。霍特林变换的突出优点是去相关性好，主要用于数据压缩和图象旋转上。第三章图象变换135第五节霍特林变换设给定一组M个随机矢量（即x有M个样本）：k=1,2,…,M这组随机矢量的均值矢量为：mx=E{x}这组随机矢量的协方差矩阵为：Cx=

E{（x-mx）（x-mx）T}第三章图象变换136第五节霍特林变换若是从同一个随机母体得到了M个矢量采样，则其均值矢量和协方差矩阵可分别用以下两式来近似：第三章图象变换137第五节霍特林变换例协方差矩阵计算示例设有4个矢量x1=[000]T，x2=[100]T，x3