第五章图象正交变换PPT讲稿.ppt

第五章图象正交变换第1页，共129页，编辑于2022年，星期三什么是图象变换什么是图象变换将图象看成是线性叠加系统将图象看成是线性叠加系统图象在空域上相关性很强图象在空域上相关性很强图象变换是将图象从空域变换到其它域图象变换是将图象从空域变换到其它域如频域的数学变换如频域的数学变换常用的变换：傅立叶变换、离散余弦变常用的变换：傅立叶变换、离散余弦变换、沃尔什变换、离散换、沃尔什变换、离散K-L变换、小波变变换、小波变换等换等第2页，共129页，编辑于2022年，星期三连续函数集合的正交性连续函数集合的正交性正交函数集合正交函数集合当当C=1时，时，称集合为归一化正交函数集合称集合为归一化正交函数集合 第3页，共129页，编辑于2022年，星期三正交函数集合的完备性正交函数集合的完备性若若f(x)是定义在是定义在t0和和t0+T区间的实值信号区间的实值信号，平，平方可积。可以表示为：方可积。可以表示为：对任意小的对任意小的0，存在充分大的，存在充分大的N，其中其中，则称函数则称函数U集合是完备的。集合是完备的。第4页，共129页，编辑于2022年，星期三离散情况离散情况n个正交向量个正交向量当当C=1时，时，称归一化正交称归一化正交 第5页，共129页，编辑于2022年，星期三满足：满足：第6页，共129页，编辑于2022年，星期三一维正交变换一维正交变换对于一向量对于一向量f，用上述正交矩阵进行，用上述正交矩阵进行运算：运算：g=Af若要恢复若要恢复f，则，则以上过程称为以上过程称为正交变换正交变换。第7页，共129页，编辑于2022年，星期三酉变换酉变换若若A为复数矩阵，正交的条件为：为复数矩阵，正交的条件为：其中其中A*为为A的复数共轭矩阵，满足这个的复数共轭矩阵，满足这个条件的矩阵为条件的矩阵为酉矩阵酉矩阵。对于任意向量。对于任意向量f的运算称为的运算称为酉变换酉变换：第8页，共129页，编辑于2022年，星期三酉变换、正交变换与信号分析酉变换、正交变换与信号分析正交变换是酉变换的特例正交变换是酉变换的特例它们都可以用于信号分析它们都可以用于信号分析用于信号分析的基函数集合和正交矩阵用于信号分析的基函数集合和正交矩阵都应满足正交性和完备性都应满足正交性和完备性第9页，共129页，编辑于2022年，星期三二维酉变换二维酉变换 NN二维函数可以类似于一维用正交序列展开和恢二维函数可以类似于一维用正交序列展开和恢复复正变换核正变换核反变换核反变换核第10页，共129页，编辑于2022年，星期三变换核的可分离性变换核的可分离性其中其中au(x),u=0,1,N-1,bv(y),v=0,1,N-1为为一维完备正交基向量的集合。用矩阵表示：一维完备正交基向量的集合。用矩阵表示：A=a(u,x)，B=b(v,y)通常选择通常选择A=B。第11页，共129页，编辑于2022年，星期三二维酉变换二维酉变换A=B时，二维酉变换正变换表示为时，二维酉变换正变换表示为用矩阵表示：用矩阵表示：F=AfAT类似的，对于类似的，对于MN的二维函数的二维函数f(x,y)第12页，共129页，编辑于2022年，星期三基图象基图象反变换反变换看成是基图象看成是基图象F(u,v)权因子权因子图象图象f(x,y)可以用可以用N2个基图象的加权和来表示个基图象的加权和来表示第13页，共129页，编辑于2022年，星期三酉变换的性质酉变换的性质1.酉矩阵是正交阵酉矩阵是正交阵2.AA*T=A*TA=INN3.2.A为酉阵，则为酉阵，则A-1和和AT都是酉阵都是酉阵4.3.酉变换是能量保持的变换酉变换是能量保持的变换5.对于一维酉变换对于一维酉变换F=Af,有有|F|=|f|6.二维情况下，则有：二维情况下，则有：第14页，共129页，编辑于2022年，星期三酉变换的性质酉变换的性质(2)设设f(x,y)的均值和协方差为的均值和协方差为f和和f4.均值和方差均值和方差则则F(u,v)的均值为：的均值为：则则F(u,v)的协方差为：的协方差为：第15页，共129页，编辑于2022年，星期三酉变换的性质酉变换的性质(3)5.其他性质：其他性质：(1)A为酉阵，则其行列式值为酉阵，则其行列式值|A|=1(2)若若a为向量，则作酉变换后向量为向量，则作酉变换后向量模保持不变：模保持不变：b=Aa，则，则|b|=|a|。第16页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 5.1.1 一维傅立叶变换一维傅立叶变换1.一维连续函数的傅立叶变换（一维连续函数的傅立叶变换（FT）定义：若函数定义：若函数f（x）满足条件：）满足条件：1）具有有限个间断点；）具有有限个间断点；2）具有有限个极值点；）具有有限个极值点；3）绝对可积，）绝对可积，则把变换称为：则把变换称为：傅立叶正变换：傅立叶正变换：傅立叶反变换：傅立叶反变换：傅立叶变换对：傅立叶变换对：F（u）f（x）第17页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 2.一维离散傅立叶变换（一维离散傅立叶变换（DFT）傅立叶正变换：傅立叶正变换：傅立叶反变换：傅立叶反变换：运算量为运算量为N*N次复数相乘和次复数相乘和N*(N-1)次复数相加次复数相加第18页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 2.一维离散傅立叶变换（一维离散傅立叶变换（DFT）实序列的实序列的FT：第19页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 目的:（1）用矩阵乘法的程序进行FT；（2）理论推导用。一维一维DFT的矩阵表示的矩阵表示根据定义:令:则:展开:第20页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 一维一维DFT的矩阵表示的矩阵表示当当N=4时：时：第21页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 一维一维DFT的矩阵表示的矩阵表示例：例：第22页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 系数 和 具有 周期 性和对称性 傅立叶系数的性质：傅立叶系数的性质：第23页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 时间抽取基时间抽取基2 FFT算法算法 要求N为2的幂，即 ，M为正整数将输入时间序列按奇、偶抽取两个N/2点的FT3.快速傅立叶变换（快速傅立叶变换（FFT）第24页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 时间抽取基时间抽取基2 FFT算法算法对于uN/2-1的点，有以下规则给出：N=84点DFT4点DFT第25页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 时间抽取基时间抽取基2 FFT算法算法蝶形运算蝶形运算(u=0,1,N/2-1)第26页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 时间抽取基时间抽取基2 FFT算法算法用两个2点DFT代替4点DFT：第27页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 时间抽取基时间抽取基2 FFT算法算法2点DFT2点DFT2点DFT2点DFT输入倒序排列第28页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 时间抽取基时间抽取基2 FFT算法算法输入倒序排列第29页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 标号二进制表示 按位倒序的二进制表示倒序后标号0123456700000101001110010111011100010001011000110101111104261537时间抽取基时间抽取基2 FFT算法算法第30页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 4.用计算机实现快速傅里叶变换用计算机实现快速傅里叶变换利用利用FFT蝶形流程图算法在计算机上实现快速付里叶变换必须解决如下蝶形流程图算法在计算机上实现快速付里叶变换必须解决如下问题：迭代次数问题：迭代次数r的确定、对偶节点的计算、加权系数的确定、对偶节点的计算、加权系数 的计算、重新的计算、重新排序问题。排序问题。(1)迭代次数迭代次数r的确定的确定 由蝶形流程图可见，迭代次数与由蝶形流程图可见，迭代次数与N有关。有关。r值可由下式确定：值可由下式确定：式中式中N是变换序列的长度，对于基是变换序列的长度，对于基2的蝶形程图，的蝶形程图，N是是2的整的整数次幂。例如，序列长度为数次幂。例如，序列长度为8则要三次迭代，序列长度为则要三次迭代，序列长度为16时就要时就要4次迭代。次迭代。第31页，共129页，编辑于2022年，星期三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)。对偶节点的计算也就是求出在每次迭代小对偶节点的间隔。由。对偶节点的计算也就是求出在每次迭代小对偶节点的间隔。由流程图可见，第一次迭代的间距为计流程图可见，第一次迭代的间距为计N2，第二次迭代的节距为，第二次迭代的节距为N4，第三次迭代的节距为人，第三次迭代的节距为人N23等等。由以上分析可得到对等等。由以上分析可得到对偶节点的计算方法。如果某一节点为偶节点的计算方法。如果某一节点为xi(k)，那么它的对偶节点为，那么它的对偶节点为第32页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 4.用计算机实现快速傅里叶变换用计算机实现快速傅里叶变换(3)加权系数加权系数 的计算的计算 的计算主要是确定的计算主要是确定p值。值。p值可用下述方法求得：值可用下述方法求得：把把k值写成值写成r位的二进制数位的二进制数(k序列的序号数，序列的序号数，r是迭代次数是迭代次数)；把这个二进制数右移把这个二进制数右移r-1位，并把左边的空位补零位，并把左边的空位补零(结果仍为结果仍为r位位)把这个右移后的二进制数倒序把这个右移后的二进制数倒序把倒序后的二进制数转换维十进制数就得到把倒序后的二进制数转换维十进制数就得到p值。值。第33页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 4.用计算机实现快速傅里叶变换用计算机实现快速傅里叶变换(4)重新排序重新排序 由蝶形流程图可见，如果序列由蝶形流程图可见，如果序列x(n)是按顺序排列的，经过蝶式是按顺序排列的，经过蝶式运算后，其变换序列是倒序排列的；反之，如果运算后，其变换序列是倒序排列的；反之，如果x(n)是倒序排列是倒序排列的，那么输出就是顺序排列的。因此，为了便于输出的，那么输出就是顺序排列的。因此，为了便于输出使用，最好加入倒序程序以保证使用，最好加入倒序程序以保证x(n)与它的变换系数与它的变换系数X(m)的对应关的对应关系。系。第34页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 5.如何提高如何提高FFT的速度？的速度？（1）减少乘法次数；（2）基4、基8算法；（3）实数FFT；（4）硬件实现（DSP芯片，FFT集成块）第35页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 6.FFT举例举例w2w1w3-1-1-1-1F（u）-1-1-1-1w2w2-1-1-1-11001-1001111-1-1-1202000001001f（x）其中：第36页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 6.FFT举例举例21+j01-j000010101000-101111-11-1-j-1 j第37页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 6.FFT举例举例F（u）=2，0，幅度谱：幅度谱图：0121234567uF（u）第38页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 5.1.2 二维傅立叶变换二维傅立叶变换1.二维连续函数傅立叶变换（二维连续函数傅立叶变换（2D FT）定义定义:若若f(x,y)是连续图象函数是连续图象函数正变换正变换:反变换反变换:变换对变换对:第39页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 2.幅度谱、相位谱、能量谱幅度谱、相位谱、能量谱一般一般F(u,v)是复函数是复函数,即即:幅度谱幅度谱:相位谱相位谱:能量谱能量谱:第40页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 二维连续傅立叶变换举例：二维连续傅立叶变换举例：函数函数 f(x，y)=A,0,其他其他 求求F(u,v)。f(x,y)xy0XYAXY(0,0)图象屏幕显示图象屏幕显示第41页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 ；代入函数；分离变量；查积分表；欧拉公式第42页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 两个SINC函数的乘积幅度谱：u=0，v方向v=0，u方向谱图（截面图）第43页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 幅度谱：幅度谱的屏幕显示：u=0，v方向第44页，共129页，编辑于2022年，星期三Fourier 变换示意图变换示意图第45页，共129页，编辑于2022年，星期三Fourier 变换示意图第46页，共129页，编辑于2022年，星期三Fourier变换的频率特性 第47页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 5.1.2 二维傅立叶变换二维傅立叶变换2.二维离散傅立叶变换（二维离散傅立叶变换（2D DFT）定义定义:若若f(x,y)是离散图象函数是离散图象函数正变换正变换:反变换反变换:第48页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 二维离散傅立叶变换的矩阵表示二维离散傅立叶变换的矩阵表示令:正变换:反变换:(忽略1/N)第49页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 根据可分离性：令:忽略1/N第50页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 FT：IFT：（忽略1/N）第51页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 5.1.3 二维傅立叶变换的性质二维傅立叶变换的性质1.可分离性可分离性正变换第52页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 同样，反变换也具有可分离性同样，反变换也具有可分离性第53页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 利用二维傅立叶变换的可分离性，可将二维利用二维傅立叶变换的可分离性，可将二维DFT转化成一维转化成一维DFT计计算。即，先在算。即，先在x（或（或y）方向进行一维）方向进行一维DFT，再在，再在y（或（或x）方向进行）方向进行一维一维DFT：第一步：第二步：第54页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 二维离散傅立叶变换过程图示：二维离散傅立叶变换过程图示：第一步：第二步：f（x，y）=F（u，y）=在在x方向逐行进行一维方向逐行进行一维FT在在y方向逐列进行一维方向逐列进行一维FT1/NF（u，v）=第55页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 二维离散傅立叶变换举例二维离散傅立叶变换举例例例1：x方向FFT11001111201-j1+j21-j01+j-1-1-1-1w1y方向FFT1/4第56页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 二维离散傅立叶变换举例二维离散傅立叶变换举例1111220040004000-1-1-1-1w1第57页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 二维离散傅立叶变换举例二维离散傅立叶变换举例例例2：二维傅立叶反变换：二维傅立叶反变换用下式求反变换，与正变换使用同一流程：第58页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 二维离散傅立叶变换举例二维离散傅立叶变换举例例例2：二维傅立叶反变换：二维傅立叶反变换第59页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 二维离散傅立叶变换举例二维离散傅立叶变换举例例例2：二维傅立叶反变换：二维傅立叶反变换逐列FFT逐行FFT1/4逐像素求共轭第60页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 5.1.3 二维傅立叶变换的性质二维傅立叶变换的性质2.平移性平移性FT则：则：相当于相当于F（u，v）的坐标原点）的坐标原点移到（移到（u0，v0）点）点第61页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 即：移中性移中性同理：第62页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 移中性移中性移中性的用途：移中性的用途：图象作傅立叶变换时，若采用以下公式变换，则变换后主要能量图象作傅立叶变换时，若采用以下公式变换，则变换后主要能量（低频分量）集中在频率平面的中心。（低频分量）集中在频率平面的中心。第63页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 移中性移中性先以一维为例：先以一维为例：f（x）=1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0，N=16。求求 F（u）0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16N/2直流分量直流分量高频分量高频分量低频分量低频分量周期性重复周期性重复周期性重复周期性重复第64页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 f（x）=1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0，N=16。求求 F（u）0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16N/2直流分量直流分量高频分量高频分量低频分量低频分量0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16N/2直流分量直流分量高频分量高频分量低频分量低频分量高频分量高频分量低频分量低频分量f(x)=f(x)(-1)x=1-1 1-1 1-1 1-1 0 0 0 0 0 0 0 0，求求 F(u)第65页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 移中性移中性未移中的变换：未移中的变换：移中的变换：移中的变换：能量集中于中心（示意图）能量集中于中心（示意图）移中移中FT原图象原图象f（x，y）FT能量分布于四角（示意图）能量分布于四角（示意图）第66页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 移中移中FT移中移中FT第67页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 移中性计算举例移中性计算举例FT1/4 FT1/4 第68页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 3.周期性周期性非周期性离散函数的非周期性离散函数的FT是离散的周期性函数是离散的周期性函数第69页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 4.旋转性旋转性当变量当变量x，y，u，v都用极坐标表示时，即：都用极坐标表示时，即：则：则：若：若：此式含义是：当原图象旋转某一角度时，此式含义是：当原图象旋转某一角度时，FT后的图象也后的图象也旋转同一角度。旋转同一角度。第70页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 旋转性举例：旋转性举例：原图象及其傅立叶幅度谱图象原图象及其傅立叶幅度谱图象原图象旋转原图象旋转45，其幅度谱图象也旋转，其幅度谱图象也旋转45 第71页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 5.二维函数的卷积定理若：*卷积 乘积 则：空域频域第72页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 6.二维函数的相关定理二维函数的相关定理若：若：则：则：空域空域频域频域*共轭共轭 乘积乘积 相关相关 第73页，共129页，编辑于2022年，星期三5.1 傅立叶变换傅立叶变换 5.1.4 二维傅立叶幅度谱的显示二维傅立叶幅度谱的显示1.求移中的傅立叶变换：求移中的傅立叶变换：2.求幅度谱：求幅度谱：3.求幅度谱的对数函数：求幅度谱的对数函数：步骤步骤:4.显示显示D(u,v)若若D(u,v)很小或很大，则将其线性扩展或压缩到很小或很大，则将其线性扩展或压缩到0-255第74页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.1 引言引言比较比较:傅立叶变换傅立叶变换:快速算法快速算法,复数运算复数运算,乘法乘法,速度慢速度慢,可硬件实现可硬件实现,精度高精度高Walsh变换变换:快速算法快速算法,实数运算实数运算,加减法加减法,速度快速度快,可硬件实现可硬件实现,精度低精度低拉德梅克拉德梅克(Rademacher)函数的定义函数的定义:其中：其中：n为序号，为序号，n=0，1，N-1 t为连续时间变量为连续时间变量符号函数：符号函数：第75页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.1 引言引言拉德梅克拉德梅克(Rademacher)函数函数:符号函数：符号函数：+1-1+1-1+1-1+1-11ttttt+1-11111n=0n=1n=2n=3（2）是一个不完备的函数，只有奇函数，不能用于变换。）是一个不完备的函数，只有奇函数，不能用于变换。拉德梅克函数的特点：拉德梅克函数的特点：（1）是正交函数族：）是正交函数族：第76页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.2 Walsh函数函数1.连续连续Walsh函数的定义函数的定义(1)Walsh序的序的Walsh函数函数定义定义:其中其中:拉德梅克函数拉德梅克函数第77页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.2 Walsh函数函数1.连续连续Walsh函数的定义函数的定义(1)Walsh序的序的Walsh函数函数 二进制码二进制码 格雷码格雷码n b2b1b0 g2g1g00 000 0001 001 0012 010 0113 011 0104 100 1105 101 1116 110 1017 111 100第78页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.2 Walsh函数函数1.连续Walsh函数的定义(1)Walsh序的Walsh函数 二进制码 格雷码n b2b1b0 g2g1g00 000 0001 001 0012 010 0113 011 0104 100 1105 101 1116 110 1017 111 100第79页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.2 Walsh函数函数1.连续Walsh函数的定义(1)Walsh序的Walsh函数+1-1+1-1+1-11ttt11+1-1+1-1+1-11ttt1111111tttttWalsh序的序的Walsh函数的特点函数的特点:(1)是完备的正交函数是完备的正交函数,序号为偶数序号为偶数的是偶函数的是偶函数,序号为奇数的是奇函序号为奇数的是奇函数数;可用于正交变换。可用于正交变换。(2)一个周期内一个周期内,过零点数与序号一过零点数与序号一致致.第80页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.2 Walsh函数函数1.连续Walsh函数的定义(2)Paley序的Walsh函数(略)(3)Hadamard序的Walsh函数定义:其中:Ii 是 n 的二进制码的倒序码 的第 i 位 二进制码 倒序码n b2b1b0 I2I1I00 000 0001 001 1002 010 0103 011 1104 100 0015 101 1016 110 0117 111 111第81页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.2 Walsh函数函数1.连续Walsh函数的定义(3)Hadamard序的Walsh函数定义:第82页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.2 Walsh函数函数2.离散离散Walsh函数的定义函数的定义定义定义:(1)Walsh序的离散序的离散Walsh函数函数其中其中:第83页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.2 Walsh函数函数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第84页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.2 Walsh函数函数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第85页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.2 Walsh函数函数2.离散离散Walsh函数的定义函数的定义(1)Walsh序的离散序的离散Walsh函数函数例例:N=8,n=0,1,7,t=0,1,7 同理，可求出：同理，可求出：WW(n,t)Walsh序的序的Walsh矩阵矩阵第86页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.2 Walsh函数函数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）第87页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.2 Walsh函数函数2.离散Walsh函数的定义(2)Hadamard序的离散Walsh函数Hadamard序的序的Walsh矩阵矩阵第88页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.2 Walsh函数函数5.Walsh矩阵(1)Walsh序的Walsh矩阵第89页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.2 Walsh函数函数5.Walsh矩阵(2)Hadamard序的Walsh矩阵第90页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.2 Walsh函数函数5.Walsh矩阵(2)Hadamard序的Walsh矩阵第91页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.2 Walsh函数函数5.Walsh矩阵矩阵(2)Hadamard序的序的Walsh矩阵矩阵一般来说：一般来说：第92页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.3 一维离散一维离散Walsh变换变换(WT)1.定义定义正变换正变换:反变换反变换:注意注意:Walsh正、反变换的变换核都一样！正、反变换的变换核都一样！第93页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.3 一维离散一维离散Walsh变换变换(WT)2.一维离散一维离散Walsh变换的矩阵算法变换的矩阵算法正变换正变换:展开：展开：第94页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.3 一维离散一维离散Walsh变换变换(WT)2.一维离散一维离散Walsh变换的矩阵算法变换的矩阵算法令：令：IWT：WT：(1/N可以忽略不写可以忽略不写)注意注意:（1）正反变换的变换矩阵）正反变换的变换矩阵W都一样；都一样；（2）W代表代表Walsh序的序的Walsh矩阵。矩阵。第95页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.3 一维离散一维离散Walsh变换变换(WT)2.一维离散一维离散Walsh变换的矩阵算法变换的矩阵算法注意注意:当变换矩阵为当变换矩阵为Hadamard矩阵矩阵HN时时,称为称为Hadamard序的序的 Walsh变换。变换矩阵如下写法：变换。变换矩阵如下写法：IWHT：WHT：(1/N可可忽略不写忽略不写)其中其中H为为Hadamaed序的序的Walsh矩阵。矩阵。第96页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.3 一维离散一维离散Walsh变换变换(WT)2.一维离散一维离散Walsh变换的矩阵算法变换的矩阵算法IWT：WT：举例举例:求求Walsh序的一维离散序的一维离散Walsh变换变换F(u).反变换：反变换：正变换：正变换：Walsh序的序的Walsh变换：变换：第97页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.3 一维离散一维离散Walsh变换变换(WT)2.一维离散一维离散Walsh变换的矩阵算法变换的矩阵算法举例举例:求求Walsh序的一维离散序的一维离散Walsh变换变换F(u)。用。用WHT。用用WHT：用用WT：结果为结果为Walsh序序结果为结果为Hadamard序序对应关系对应关系W序序 H序序0 01 22 33 1IWT：WHT：Hadamard序的序的Walsh变换：变换：第98页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.3 一维离散一维离散Walsh变换变换(WT)5.Walsh序和序和Hadamard序的相互转换序的相互转换变换结果为变换结果为Hadamard序的，要转换为序的，要转换为Walsh序序可以推导出以下转换方法（可以推导出以下转换方法（N=4）：）：格雷码格雷码二进制码二进制码倒序码倒序码 00 00 00 01 01 10 10 11 11 11 10 01（W序）序）（P序）序）（H序）序）对应关系对应关系W序序 H序序0 01 22 33 1第99页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.3 一维离散一维离散Walsh变换变换(WT)5.Walsh序和Hadamard序的相互转换N=8时的转换方法：时的转换方法：格雷码格雷码二进制码二进制码 倒序码倒序码 000 000 000 001 001 100 010 011 110 011 010 010 100 110 011 101 111 111 110 101 101 111 100 001（W序）序）（P序）序）（H序）序）对应关系对应关系W序序 H序序0 01 42 63 24 35 76 57 1第100页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.2 Walsh函数函数1.连续连续Walsh函数的定义函数的定义Hadamard序的Walsh函数Walsh序的Walsh函数对应关系W序 H序0 01 42 63 24 35 76 57 1第101页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.3 一维离散一维离散Walsh变换变换(WT)变换结果为Hadamard序的，要转换为Walsh序对应关系W序 H序0 01 22 33 1用WHT：5.Walsh序和Hadamard序的相互转换第102页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.3 一维离散一维离散Walsh变换变换(WT)4.一维一维Walsh变换的物理意义变换的物理意义正如一维傅立叶变换（连续）是将一个函数分解成无正如一维傅立叶变换（连续）是将一个函数分解成无穷个正弦波的叠加，而傅立叶幅度谱是这些正弦波的穷个正弦波的叠加，而傅立叶幅度谱是这些正弦波的幅度系数。幅度系数。一维一维Walsh变换变换（连续）（连续）是将一个函数是将一个函数分解成无穷个分解成无穷个Walsh函数（方波）的叠加，而函数（方波）的叠加，而F(u)是这些是这些Walsh函数的幅度系数函数的幅度系数.第103页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.3 一维离散一维离散Walsh变换变换(WT)4.一维Walsh变换的物理意义0 12 3t0 12 3t3182第104页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.4 快速快速Walsh变换变换(FWT)1.快速Walsh-Hadamard变换以以N=8为例为例,第105页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.4 快速快速Walsh变换变换(FWT)1.快速Walsh-Hadamard变换第106页，共129页，编辑于2022年，星期三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序序第107页，共129页，编辑于2022年，星期三5.2 沃尔什沃尔什(Walsh)变换变换 5.2.4 快速快速Walsh变换变换(FWT)1.快速Walsh-Hadamard变换FWHT举例:,用FWHT求其WT.-101234567-1-1-1-1-1-