第五章图象正交变换

第五章图象正交变换第一页，共一百二十九页，编辑于2023年，星期五什么是图象变换将图象看成是线性叠加系统图象在空域上相关性很强图象变换是将图象从空域变换到其它域如频域的数学变换常用的变换：傅立叶变换、离散余弦变换、沃尔什变换、离散K-L变换、小波变换等第二页，共一百二十九页，编辑于2023年，星期五连续函数集合的正交性正交函数集合当C=1时，称集合为归一化正交函数集合

第三页，共一百二十九页，编辑于2023年，星期五正交函数集合的完备性若f(x)是定义在t0和t0+T区间的实值信号，平方可积。可以表示为：对任意小的ε＞0，存在充分大的N，其中，则称函数U集合是完备的。

第四页，共一百二十九页，编辑于2023年，星期五离散情况n个正交向量当C=1时，称归一化正交

第五页，共一百二十九页，编辑于2023年，星期五满足：第六页，共一百二十九页，编辑于2023年，星期五一维正交变换对于一向量f，用上述正交矩阵进行运算：g=Af若要恢复f，则以上过程称为正交变换。第七页，共一百二十九页，编辑于2023年，星期五酉变换若A为复数矩阵，正交的条件为：其中A*为A的复数共轭矩阵，满足这个条件的矩阵为酉矩阵。对于任意向量f的运算称为酉变换：第八页，共一百二十九页，编辑于2023年，星期五酉变换、正交变换与信号分析正交变换是酉变换的特例它们都可以用于信号分析用于信号分析的基函数集合和正交矩阵都应满足正交性和完备性第九页，共一百二十九页，编辑于2023年，星期五二维酉变换

N×N二维函数可以类似于一维用正交序列展开和恢复正变换核反变换核第十页，共一百二十九页，编辑于2023年，星期五变换核的可分离性其中{au(x),u=0,1,…,N-1},{bv(y),v=0,1,…,N-1}为一维完备正交基向量的集合。用矩阵表示：A={a(u,x)}，B={b(v,y)}通常选择A=B。第十一页，共一百二十九页，编辑于2023年，星期五二维酉变换A=B时，二维酉变换正变换表示为用矩阵表示：F=AfAT类似的，对于M×N的二维函数f(x,y)第十二页，共一百二十九页，编辑于2023年，星期五基图象反变换－－看成是基图象F(u,v)－－权因子图象f(x,y)可以用N2个基图象的加权和来表示第十三页，共一百二十九页，编辑于2023年，星期五酉变换的性质酉矩阵是正交阵AA*T=A*TA=IN×N2.A为酉阵，则A-1和AT都是酉阵3.酉变换是能量保持的变换 对于一维酉变换F=Af,有||F||=||f|| 二维情况下，则有：第十四页，共一百二十九页，编辑于2023年，星期五酉变换的性质(2)设f(x,y)的均值和协方差为μf和Σf4.

均值和方差则F(u,v)的均值为：则F(u,v)的协方差为：第十五页，共一百二十九页，编辑于2023年，星期五酉变换的性质(3)5.其他性质：(1)A为酉阵，则其行列式值|A|=1(2)若a为向量，则作酉变换后向量模保持不变：b=Aa，则|b|=|a|。第十六页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换5.1.1一维傅立叶变换1.一维连续函数的傅立叶变换（FT）

定义：若函数f（x）满足条件：1）具有有限个间断点；2）具有有限个极值点；3）绝对可积，则把变换称为：傅立叶正变换：傅立叶反变换：傅立叶变换对：F（u）f（x）第十七页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换2.一维离散傅立叶变换（DFT）傅立叶正变换：傅立叶反变换：运算量为N*N次复数相乘和N*(N-1)次复数相加第十八页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换2.一维离散傅立叶变换（DFT）实序列的FT：第十九页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换目的:（1）用矩阵乘法的程序进行FT；（2）理论推导用。一维DFT的矩阵表示根据定义:令:则:展开:第二十页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换一维DFT的矩阵表示当N=4时：第二十一页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换一维DFT的矩阵表示例：第二十二页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换系数和具有周期性和对称性傅立叶系数的性质：第二十三页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换时间抽取基2FFT算法要求N为2的幂，即，M为正整数将输入时间序列按奇、偶抽取两个N/2点的FT3.快速傅立叶变换（FFT）第二十四页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换时间抽取基2FFT算法对于u>N/2-1的点，有以下规则给出：N=84点DFT4点DFT第二十五页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换时间抽取基2FFT算法蝶形运算(u=0,1,…,N/2-1)第二十六页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换时间抽取基2FFT算法用两个2点DFT代替4点DFT：第二十七页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换时间抽取基2FFT算法2点DFT2点DFT2点DFT2点DFT输入倒序排列第二十八页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换时间抽取基2FFT算法输入倒序排列第二十九页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换

标号二进制表示按位倒序的二进制表示倒序后标号0123456700000101001110010111011100010001011000110101111104261537时间抽取基2FFT算法第三十页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换4.用计算机实现快速傅里叶变换利用FFT蝶形流程图算法在计算机上实现快速付里叶变换必须解决如下问题：迭代次数r的确定、对偶节点的计算、加权系数的计算、重新排序问题。(1)迭代次数r的确定由蝶形流程图可见，迭代次数与N有关。r值可由下式确定：式中N是变换序列的长度，对于基2的蝶形程图，N是2的整数次幂。例如，序列长度为8则要三次迭代，序列长度为16时就要4次迭代。第三十一页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换4.用计算机实现快速傅里叶变换(2)对偶节点的计算在流程图中把标有xi(k)的点称为节点。其中下标i为列数，也就是第几次迭代，例如，x1(k)则说明它是第一次迭代的结果。k代表流程图中的行数，也就是序列的序号数。其中每节点的值均是用前一节点对计算得来的。例如，x1(0)和x1(4)均是x(0)和x(4)计算得来的。在蝶形流程图中，把具有相同来源的一对节点叫做对偶节点。如：x1(0)和x1(4)就是一对对偶节点，因为它们均来源于x(0)和x(4)

。对偶节点的计算也就是求出在每次迭代小对偶节点的间隔。由流程图可见，第一次迭代的间距为计N／2，第二次迭代的节距为N／4，第三次迭代的节距为人N／23等等。由以上分析可得到对偶节点的计算方法。如果某一节点为xi(k)，那么它的对偶节点为第三十二页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换4.用计算机实现快速傅里叶变换(3)加权系数的计算的计算主要是确定p值。p值可用下述方法求得：把k值写成r位的二进制数(k序列的序号数，r是迭代次数)；把这个二进制数右移r-1位，并把左边的空位补零(结果仍为r位)把这个右移后的二进制数倒序把倒序后的二进制数转换维十进制数就得到p值。第三十三页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换4.用计算机实现快速傅里叶变换(4)重新排序由蝶形流程图可见，如果序列x(n)是按顺序排列的，经过蝶式运算后，其变换序列是倒序排列的；反之，如果x(n)是倒序排列的，那么输出就是顺序排列的。因此，为了便于输出使用，最好加入倒序程序以保证x(n)与它的变换系数X(m)的对应关系。第三十四页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换5.如何提高FFT的速度？（1）减少乘法次数；（2）基4、基8算法；（3）实数FFT；（4）硬件实现（DSP芯片，FFT集成块）第三十五页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换6.FFT举例w2w1w3-1-1-1-1F（u）-1-1-1-1w2w2-1-1-1-11001-1001111-1-1-1202000001001f（x）其中：第三十六页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换6.FFT举例21+j01-j000010101000-101111-11-1-j-1j第三十七页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换6.FFT举例F（u）=[2，0，，，，，，]幅度谱：幅度谱图：0121234567uF（u）第三十八页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换5.1.2二维傅立叶变换1.二维连续函数傅立叶变换（2DFT）定义:若f(x,y)是连续图象函数正变换:反变换:变换对:第三十九页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换2.幅度谱、相位谱、能量谱一般F(u,v)是复函数,即:幅度谱:相位谱:能量谱:第四十页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换二维连续傅立叶变换举例：函数f(x，y)=A,0,其他求F(u,v)。f(x,y)xy0XYAXY(0,0)图象屏幕显示第四十一页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换；代入函数；分离变量；查积分表；欧拉公式第四十二页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换两个SINC函数的乘积幅度谱：u=0，v方向v=0，u方向谱图（截面图）第四十三页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换幅度谱：幅度谱的屏幕显示：u=0，v方向第四十四页，共一百二十九页，编辑于2023年，星期五Fourier变换示意图第四十五页，共一百二十九页，编辑于2023年，星期五Fourier变换示意图第四十六页，共一百二十九页，编辑于2023年，星期五Fourier变换的频率特性第四十七页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换5.1.2二维傅立叶变换2.二维离散傅立叶变换（2DDFT）定义:若f(x,y)是离散图象函数正变换:反变换:第四十八页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换二维离散傅立叶变换的矩阵表示令:正变换:反变换:(忽略1/N)第四十九页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换根据可分离性：令:忽略1/N第五十页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换FT：IFT：（忽略1/N）第五十一页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换5.1.3二维傅立叶变换的性质1.可分离性正变换第五十二页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换同样，反变换也具有可分离性第五十三页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换利用二维傅立叶变换的可分离性，可将二维DFT转化成一维DFT计算。即，先在x（或y）方向进行一维DFT，再在y（或x）方向进行一维DFT：第一步：第二步：第五十四页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换二维离散傅立叶变换过程图示：第一步：第二步：f（x，y）=F（u，y）=在x方向逐行进行一维FT在y方向逐列进行一维FT1/NF（u，v）=第五十五页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换二维离散傅立叶变换举例例1：x方向FFT11001111201-j1+j21-j01+j-1-1-1-1w1y方向FFT1/4第五十六页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换二维离散傅立叶变换举例1111220040004000-1-1-1-1w1第五十七页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换二维离散傅立叶变换举例例2：二维傅立叶反变换用下式求反变换，与正变换使用同一流程：第五十八页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换二维离散傅立叶变换举例例2：二维傅立叶反变换第五十九页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换二维离散傅立叶变换举例例2：二维傅立叶反变换逐列FFT逐行FFT1/4逐像素求共轭第六十页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换5.1.3二维傅立叶变换的性质2.平移性FT则：相当于F（u，v）的坐标原点移到（u0，v0）点第六十一页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换即：移中性同理：第六十二页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换移中性移中性的用途：图象作傅立叶变换时，若采用以下公式变换，则变换后主要能量（低频分量）集中在频率平面的中心。第六十三页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换移中性先以一维为例：f（x）=[1111111100000000]，N=16。求F（u）012345678910111213141516N/2直流分量高频分量低频分量周期性重复周期性重复第六十四页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换f（x）=[1111111100000000]，N=16。求F（u）012345678910111213141516N/2直流分量高频分量低频分量012345678910111213141516N/2直流分量高频分量低频分量高频分量低频分量f´(x)=f(x)(-1)x=[1-11-11-11-100000000]，求F´(u)第六十五页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换移中性未移中的变换：移中的变换：能量集中于中心（示意图）移中FT原图象f（x，y）FT能量分布于四角（示意图）第六十六页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换移中FT移中FT第六十七页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换移中性计算举例FT1/4FT1/4第六十八页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换3.周期性非周期性离散函数的FT是离散的周期性函数第六十九页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换4.旋转性当变量x，y，u，v都用极坐标表示时，即：则：若：此式含义是：当原图象旋转某一角度时，FT后的图象也旋转同一角度。第七十页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换旋转性举例：原图象及其傅立叶幅度谱图象原图象旋转45，其幅度谱图象也旋转45第七十一页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换5.二维函数的卷积定理若：*卷积•乘积则：空域频域第七十二页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换6.二维函数的相关定理若：则：空域频域*共轭乘积相关第七十三页，共一百二十九页，编辑于2023年，星期五5.1傅立叶变换5.1.4二维傅立叶幅度谱的显示1.求移中的傅立叶变换：2.求幅度谱：3.求幅度谱的对数函数：步骤:4.显示D(u,v)若D(u,v)很小或很大，则将其线性扩展或压缩到0-255第七十四页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.1引言比较:傅立叶变换:快速算法,复数运算,乘法,速度慢,可硬件实现,精度高Walsh变换:快速算法,实数运算,加减法,速度快,可硬件实现,精度低拉德梅克(Rademacher)函数的定义:其中：n为序号，n=0，1，，N-1t为连续时间变量符号函数：第七十五页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.1引言拉德梅克(Rademacher)函数:符号函数：+1-1+1-1+1-1+1-11ttttt+1-11111n=0n=1n=2n=3（2）是一个不完备的函数，只有奇函数，不能用于变换。拉德梅克函数的特点：（1）是正交函数族：第七十六页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.2Walsh函数1.连续Walsh函数的定义(1)Walsh序的Walsh函数定义:其中:拉德梅克函数第七十七页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.2Walsh函数1.连续Walsh函数的定义(1)Walsh序的Walsh函数二进制码格雷码nb2b1b0g2g1g000000001001001201001130110104100110510111161101017111100第七十八页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.2Walsh函数1.连续Walsh函数的定义(1)Walsh序的Walsh函数二进制码格雷码nb2b1b0g2g1g000000001001001201001130110104100110510111161101017111100第七十九页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.2Walsh函数1.连续Walsh函数的定义(1)Walsh序的Walsh函数+1-1+1-1+1-11ttt11+1-1+1-1+1-11ttt1111111tttttWalsh序的Walsh函数的特点:(1)是完备的正交函数,序号为偶数的是偶函数,序号为奇数的是奇函数;可用于正交变换。(2)一个周期内,过零点数与序号一致.第八十页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.2Walsh函数1.连续Walsh函数的定义(2)Paley序的Walsh函数(略)(3)Hadamard序的Walsh函数定义:其中:Ii是n的二进制码的倒序码的第i位二进制码倒序码nb2b1b0I2I1I000000001001100201001030111104100001510110161100117111111第八十一页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.2Walsh函数1.连续Walsh函数的定义(3)Hadamard序的Walsh函数定义:第八十二页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.2Walsh函数2.离散Walsh函数的定义定义:(1)Walsh序的离散Walsh函数其中:第八十三页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.2Walsh函数2.离散Walsh函数的定义定义:(1)Walsh序的离散Walsh函数例:N=8,n=0,1,,7,t=0,1,,7计算WW(4,0)

n=4=(100)2t=0=(000)2t的格雷码g=(000)2第八十四页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.2Walsh函数2.离散Walsh函数的定义(1)Walsh序的离散Walsh函数例:N=8,n=0,1,,7,t=0,1,,7计算WW(4,t)

同理，可求出：实际上，这个序列就是从连续的Walsh序的Walsh函数WW（4，t）在等间距的N个点上的抽样（取中间值）tWW（4，t）+1-1第八十五页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.2Walsh函数2.离散Walsh函数的定义(1)Walsh序的离散Walsh函数例:N=8,n=0,1,,7,t=0,1,,7

同理，可求出：WW(n,t)

Walsh序的Walsh矩阵第八十六页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.2Walsh函数2.离散Walsh函数的定义定义:(2)Hadamard序的离散Walsh函数例:N=8,n=0,1,,7,t=0,1,,7计算WH(4,t)

这个序列可看成从连续的Hadamard序的Walsh函数WH（4，t）在等间距的N个点上的抽样而得到。tWH（4，t）第八十七页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.2Walsh函数2.离散Walsh函数的定义(2)Hadamard序的离散Walsh函数Hadamard序的Walsh矩阵第八十八页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.2Walsh函数5.Walsh矩阵(1)Walsh序的Walsh矩阵第八十九页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.2Walsh函数5.Walsh矩阵(2)Hadamard序的Walsh矩阵第九十页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.2Walsh函数5.Walsh矩阵(2)Hadamard序的Walsh矩阵第九十一页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.2Walsh函数5.Walsh矩阵(2)Hadamard序的Walsh矩阵一般来说：第九十二页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.3一维离散Walsh变换(WT)1.定义正变换:反变换:注意:Walsh正、反变换的变换核都一样！第九十三页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.3一维离散Walsh变换(WT)2.一维离散Walsh变换的矩阵算法正变换:展开：第九十四页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.3一维离散Walsh变换(WT)2.一维离散Walsh变换的矩阵算法令：IWT：WT：(1/N可以忽略不写)注意:（1）正反变换的变换矩阵W都一样；（2）W代表Walsh序的Walsh矩阵。第九十五页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.3一维离散Walsh变换(WT)2.一维离散Walsh变换的矩阵算法注意:当变换矩阵为Hadamard矩阵HN时,称为Hadamard序的Walsh变换。变换矩阵如下写法：IWHT：WHT：(1/N可忽略不写)其中H为Hadamaed序的Walsh矩阵。第九十六页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.3一维离散Walsh变换(WT)2.一维离散Walsh变换的矩阵算法IWT：WT：举例:求Walsh序的一维离散Walsh变换F(u).反变换：正变换：Walsh序的Walsh变换：第九十七页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.3一维离散Walsh变换(WT)2.一维离散Walsh变换的矩阵算法举例:求Walsh序的一维离散Walsh变换F(u)。用WHT。用WHT：用WT：结果为Walsh序结果为Hadamard序对应关系W序H序00122331IWT：WHT：Hadamard序的Walsh变换：第九十八页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.3一维离散Walsh变换(WT)5.Walsh序和Hadamard序的相互转换变换结果为Hadamard序的，要转换为Walsh序可以推导出以下转换方法（N=4）：格雷码二进制码倒序码000000010110101111111001（W序）（P序）（H序）对应关系W序H序00122331第九十九页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.3一维离散Walsh变换(WT)5.Walsh序和Hadamard序的相互转换N=8时的转换方法：格雷码二进制码倒序码000000000001001100010011110011010010100110011101111111110101101111100001（W序）（P序）（H序）对应关系W序H序0014263243576571第一百页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.2Walsh函数1.连续Walsh函数的定义Hadamard序的Walsh函数Walsh序的Walsh函数对应关系W序H序0014263243576571第一百零一页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.3一维离散Walsh变换(WT)变换结果为Hadamard序的，要转换为Walsh序对应关系W序H序00122331用WHT：5.Walsh序和Hadamard序的相互转换第一百零二页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.3一维离散Walsh变换(WT)4.一维Walsh变换的物理意义正如一维傅立叶变换（连续）是将一个函数分解成无穷个正弦波的叠加，而傅立叶幅度谱是这些正弦波的幅度系数。一维Walsh变换（连续）是将一个函数分解成无穷个Walsh函数（方波）的叠加，而F(u)是这些Walsh函数的幅度系数.第一百零三页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.3一维离散Walsh变换(WT)4.一维Walsh变换的物理意义0123t0123t3182第一百零四页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.4快速Walsh变换(FWT)1.快速Walsh-Hadamard变换以N=8为例,第一百零五页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.4快速Walsh变换(FWT)1.快速Walsh-Hadamard变换第一百零六页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.4快速Walsh变换(FWT)1.快速Walsh-Hadamard变换FWHT流程图(N=8)-1F（3）F（4）F（5）F（6）F（7）f(0)f(1)f(2)f(3)f(4)f(5)f(6)f(7)x1(0)x1(1)x1(2)x1(3)x1(4)x1(5)x1(6)x1(7)x2(0)x2(1)x2(2)x2(3)x2(4)x2(5)x2(6)x2(7)x3(0)x3(1)x3(2)x3(3)x3(4)x3(5)x3(6)x3(7)-1-1-1-1-1-1-1-1-1-1-1F（u）f(x)F（0）F（1）F（2）规律性:每个蝶形运算都是上加下减.结果为Hadamard序,必须转换为Walsh序第一百零七页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.4快速Walsh变换(FWT)1.快速Walsh-Hadamard变换FWHT举例:,用FWHT求其WT.-101234567-1-1-1-1-1-1-1-1-1-1-1F（u）f(x)3.5-0.5-10-200046810-4-4-4-41216-4-4-8-80028-4-80-16000第一百零八页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.4快速Walsh变换(FWT)1.快速Walsh-Hadamard变换FWHT举例:若求FH(u)的反变换,采用与正变换同一流程,只是不乘系数1/8.01234567-1-1-1-1-1-1-1-1-1-1-1-1F（u）f(x)3.5-0.5-10-20001.5-0.5-105.5-0.5-10-0.50.5-0.52.54.5-0.56.5-0.5,求f(x).第一百零九页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.4快速Walsh变换(FWT)也可推导出FWT的流程图(N=8):规律性:先将f(x)进行码位倒置.每次迭代中,偶数分组每个蝶形运算都是上加下减,奇数分组每个蝶形运算则是上减下加.结果为Walsh序.-1f(0)f(1)f(2)f(3)f(4)f(5)f(6)f(7)x1(0)x1(1)x1(2)x1(3)x1(4)x1(5)x1(6)x1(7)x2(0)x2(1)x2(2)x2(3)x2(4)x2(5)x2(6)x2(7)x3(0)x3(1)x3(2)x3(3)x3(4)x3(5)x3(6)x3(7)-1-1-1-1-1-1-1-1-1-1-1F（u）f(x)F（0）F（1）F（2）F（3）F（4）F（5）F（6）F（7）x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)2.快速Walsh变换（FWT）第一百一十页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.4快速Walsh变换(FWT)2.快速Walsh变换（FWT）0123456719513-1-1-1-1622-4-400-2-228-160-8000-4-1-1-1-1-1-1-1-1-1-1-1-1F（u）f(x)3.5-20-1000-0.504261537FWT举例:,用FWT求其WT.快速Walsh反变换与正变换用同样流程第一百一十一页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.5一维Walsh变换的性质(略)1.线性2.相乘性5.变换4.移位定理5.平均值定理6.卷积定理7.相关定理第一百一十二页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换5.2.6二维离散Walsh变换1.定义:正变换:反变换:注意：正变换和反变换的变换核都一样。第一百一十三页，共一百二十九页，编辑于2023年，星期五5.2沃尔什(Walsh)变换