医学图像处理 第三章图像变换

1、第3章 正交变换在图像处理中的应用第一节 傅氏变换在图像处理中的应用 3.1.1 一维连续傅氏变换1、变换对dxxfuFuxj2e)()(duuFxfuxj2e)()()u(F)x(f F(u)一般是复数，表示形式为： F(u) = R(u) + j I(u) 或)u(je)u(F)u(F这里 |F(u)| = 称为f(x)的傅立叶谱22)()(uIuR 相角 能量谱)()(tanarc)(uRuIu 2| )(|)(uFuE 2、快速算法因为所以：当f(x)为偶函数，则第二项为零，当f(x)为奇函数，则第一项为零。 ux2jsin)ux2(cos)x(fdxe )x(f)u(Fuxj2 3.

2、1.2 二维连续傅氏变换变换对：dxdyyxfvuF)vyux(j2e ),(),(dudve ) v , u ( F) y, x ( f)vyux(j2)v, u(F)y, x(f)v, u(I)v, u(R)v, u(F22),(),(tanarc),(vuRvuIvu)v, u(I)v, u(R)v, u(E22 3.1.3 一维离散傅氏变换（DFT）1、变换对1N0 xNuxj2e )x(f)u(F设f(0), f(1), f(2), , f(N-1)为一维信号f(x)的N个抽样， 其离散傅立叶变换对为 1NouNuxj2e )u(FN1)x(f)u(F)x(fx=0，1，2，N-1u

3、=0，1，2，N-1 以N=4为例，序列f(0),f(1),f(2),f(3)的傅氏变换F(u)。利用公式 ，取N=4，则有：，展开有：1N0Nuxj2e )x(f)u(Fx30 x4ux2je )x(f)u(F 29jj223j0j3j2j023jj2j03210e3fe2fe1fe0f)3(Fe3fe2fe1fe0f)2(Fe3fe2fe ) 1 (fe )0(f) 1 (Fe3fe2fe ) 1 (fe )0(f)0(F写成矩阵形式：设： 3f2f1f0feeeeeeeeeeeeeeeeF(3)F(2)F(1)F(0)29j -j2-23j -0j3-j2-j -023j -j -2j

4、-00000uxN2juxNeW 则： 记作：9N6N3N0N6N4N2N0N3N2N1N0N0N0N0N0N29j -j2-23j -0j3-j2-j -023j -j -2j -00000WWWWWWWWWWWWWWWWeeeeeeeeeeeeeeeefWFN 2、 的性质（1）对称性（2）周期性（3）可分性uxNW*uxNx)uN(N)xN(uNWWWu)x(NN)xN(uNuxNWWW2ux2NuxNWW1W2NNux2N2uxNWWuN2NuNWW 3.1.4 二维离散傅氏变换1、变换对x,u=0，1，2，M-1y,v=0，1，2，N-11 -M0 x1 -N0yNvyMuxj2-e

5、 )y, x(f)v, u(F1N0u1M0v)NvyMux(j2e )v, u(FMN1)y, x(f)v, u(F)y, x(f 2、二维离散傅氏变换的性质（1）周期性和共轭对称性周期性：共轭对称性：)nNv,mMu(F)v, u(F)nNy,mMx( f)y, x( f)v, u(F)v, u(F)vnN, umM(F)v, u(F* （2）空域移位 （3）频域移位 （4）卷积设 则 vyNuxM0000WW)v, u(F)yy,xx(f)vv,uu(FWW)y, x( f00-yvN-xuM00) v, u(G) y, x( g),v, u( F) y, x( f)v, u(G*)v,

6、 u(F)y, x(g)y, x(f)v, u(G)v, u(F)y, x(g*)y, x(f （5）能量守恒设则（6）二维核可分离性)v, u(F)y, x( f1N0u1N0v221N0 x1N0y2v)F(u,N1)y, x( fNvy2jNux2jNvyuxj2eee 3、二维傅氏变换的矩阵表示 令 则：1 -M0 x1 -N0yNvyMuxj2-e )y, x(f)v, u(FN2jNM2jMeW,eW1 -M0 x1 -N0yvyNuxM1 -M0 x1 -N0yvyNuxMW)y, x(fWWW)y, x(f)v, u(F 用矩阵表示为：) 1N, 1M(F.) 1 , 1M(F

7、)0 , 1M(F.) 1N, 1 (F.) 1 , 1 (F)0 , 1 (F) 1N, 0(F.) 1 , 0(F)0 , 0(F2) 1N(NW.) 1N(NW0NW.) 1N(NW.1NW0NW0NW.0NW0NW) 1N, 1M(f.) 1 , 1M(f)0 , 1M(f.) 1N, 1 (f.) 1 , 1 (f)0 , 1 (f) 1N, 0(f.) 1 , 0(f)0 , 0(f2) 1M(MW.) 1M(MW0MW.1MW.1MW0MW0MW.0MW0MW是 的逆矩阵上式用矩阵符号表示为：NMfWWF 11FfNMWW1MW1NWMWNW同理付立叶反变换为：、例：求数字图像

8、的2DDFT2000120011201112解：9464340464442404342414040404040494643404644424043424140404040404WWWWWWWWWWWWWWWW*2000120011201112*WWWWWWWWWWWWWWWWFj1j11111j1-j111112000120011201112j1j11111j1-j11111F3.1.5 快速傅氏变换（FFT）一、基于时间抽取(DIT)的FFT一维离散傅氏变换 全部计算需要N2次乘法和N(N-1)次加法，当N很大时,运算量将是惊人的,如N=1024,则要完成1048576 次(一百多万次)乘法

9、运算.这样,难以做到实时处理.1N0 xNux2je )x(f)u(Fx=0，1，2，N-1u=0，1，2，N-1 快速算法要求 N为2的整数次幂，即 N=2m（m为整数）。 一维离散傅立叶变换的表达式 x=0，1，2N-1u=0，1，2N-1设 则：1N0 xNux2je )x(f)u(FN2jNeW1N0 xuxNW)x(f)u(F 因为N为偶数，可将其分为两部分之和，即N/2个偶数项和N/2个奇数项之和，写为： 因为 所以有 12N0 x)12x(uN12N0 x)2x(uNW) 12x(fW)2x(f)u(Fux2N2uxNWW1N10 xux2NuN12N0 xux2NW) 12x(

10、fWW)2x(f)u(F 我们知道F(u)（u=0,1,2N-1）共有N个值，如果我们把前N/2个离散值和后N/2个离散值分成两个式子来表示，则有u=0，1，2， （1） u=0，1，2， （2）12N0 xux2NuN12N0 xux2NW) 12x(fWW)2x(f)u(F12N12N0 x)x2N(u2N)2N(uN12N0 x)x2N(u2NW) 12x(fWW)2x(f)2Nu(F12N 因为： 则上述(2)式可简化为：u=0，1，2，（3）uN2NNuN)2Nu(NWWWWux2N2Nx2Nux2N)x2N(u2NWWWW12N0 xux2NuN12N0 xux2NW) 12x(

11、fWW)2x( f)u(F12N 令： 则（1）式和（3）式可写为: （4）u=0,1,12N0 xux2NW)2x(f)u(F偶12N0 xux2NW) 12x(f)u(F奇12N)u(FW)u(F)2Nu(F)u(FW)u(F)u(FuNuN奇偶奇偶 计算一维离散傅立叶变换，可以分两步：第一步，先按定义求出F偶(u)和F奇(u),然后按(4)式计算傅立叶变换F(u)的前N/2个点和后N/2个点。4N2N2212N2N(1)N/2点的DFT运算量:复乘次数:复加次数:(2)两个N/2点的DFT运算量:复乘次数:复加次数: (3)N/2个蝶形运算的运算量:复乘次数:复加次数: : 计算工作量分

12、析计算工作量分析复乘:复加:总共运算量:按奇、偶分组后的计算量：但是,N N点DFTDFT的复乘为N N2 2 ; ;复加N(N-1);N(N-1);与分解后相比可知,计算工作点差不多减少 一半。2N2) 12N(N2NN2N22N2N2N222NN) 12N(N2 例如 N=8N=8 时的DFT,DFT,可以分解为两个 N/2=4N/2=4点的DFTDFT。具体方法如下: :（1 1）n n为偶数，即为偶数，即f(0),f(2),f(4),f(6);f(0),f(2),f(4),f(6);进行进行N/2=4N/2=4点的点的DFTDFT，得，得F F偶偶(u):(u):u=0,1,2,312

13、N0 xux2NW)2x(f)u(F偶 （2）当n为奇数时，即f(1),f(3),f(5),f(7)；u=0，1，2，312N0 xux2NW) 12x(f)u(F奇进行N/2=4点的DFT，得F奇(u):u=0，1，2，3)u(FW)u(F)4u(F)u(FW)u(F)u(Fu8u8奇偶奇偶(3)(3)对F偶(u) )和F奇(u) 进行蝶形运算： f1 1(0)=(0)=f(0) (0) f1(1)=(1)=f(2) (2) N/2N/2点点 f1(2)=(2)=f(4) DFT (4) DFT f1(3)=(3)=f(6) (6) f2(0)=(0)=f(1) (1) f2(1)=(1)=

14、f(3) (3) N/2N/2点点 f2(2)=(2)=f(5) (5) DFT DFT f2(3)=(3)=f(7)(7) F F偶偶(0)(0)F F偶偶(1)(1)F F偶偶(2)(2)F F偶偶(3)(3)F F奇奇(0)(0)F F奇奇(1)(1)F F奇奇(2)(2)F F奇奇(3)(3)WN2WN1WN0WN3-1-1-1-1F(0)F(0)F(1)F(1)F(2)F(2)F(3)F(3)F(4)F(4)F(5)F(5)F(6)F(6)F(7)F(7) 因为N=2n，N是偶数，当 时，N/2还是偶数，因此F偶(u) )和F奇(u) （u=0，1，2， ）的计算仍可以按同样方法分解

15、为偶、奇两个集，得出如下结果：u=0，1，2n 12N)u(FW)u(F)4Nu(F)u(FW)u(F)u(Fu2Nu2N偶奇偶偶偶偶奇偶偶偶)u(FW)u(F)4Nu(F)u(FW)u(F)u(Fu2Nu2N奇奇奇偶奇奇奇奇偶奇14N 式中： u=0,1,，14N0 xux4NW)4x(f)u(F偶偶14N0 xux4NW)24x(f)u(F偶奇14N0 xux4NW) 14x(f)u(F奇偶14N0 xux4NW)34x(f)u(F奇奇14N 如果按这种方法一直进行下去，直到求出两点离散函数的傅立叶变换为止。这就是快速傅立叶变换的原理。 因此8点DFT的FFT的运算流图如下： f(0) f

16、(4) f(2) f(6) f(1) f(5) f(3) f(7)WN0WN0WN0W0N-1-1-1-1F偶偶 (0)F 偶偶(1)F 偶奇(0)F 偶奇(1)F 奇偶(0)F奇偶(1)F奇奇 (0)F奇奇 (1)WN0WN2WN0WN2-1-1-1-1F偶 (0)F 奇(0)F 奇(1)F 奇(2)F 奇(3)WWWWN0N1N2N3-1-1-1-1F(0)F(1)F(2)F(3)F(4)F(5)F(6)F(7)F偶 (1)F偶 (2)F偶 (3)二二. .运算量运算量 由上述分析可知,N=8N=8需三级蝶形运算 N=2N=23 3=8,=8,由此可知,N=2N=2L L 共需L L级蝶形

17、运算,而且每级都由N/2N/2个蝶形运算 组成,每个蝶形运算有一次复乘,两次复加。 因此,N N点的FFTFFT的运算量为复乘:（N/2N/2）L=L=（N/N/2） loglog2 2 N N复加: N L=N logN L=N log2 2 N N 由于计算机的乘法运算比加法运算所需的时间多得多，故以乘法作为比较基准。2 2 倒位序规律倒位序规律输出F F(u)(u)按正常顺序排列在存储单元,而输入是按顺序:f(0),f(4),f(2),f(6);f(1),f(5),f(3),f(7) 这种顺序称为比特倒序。 二进制为(n2 n1 n0 )2 的数, , 比特倒序为(n0 n1 n2 )2

18、 。例如，N=8时如下表： 0 00 0 0 0 0 00 0 0 0 0 0 0 0 1 01 0 0 0 1 11 1 0 0 0 4 0 4 2 02 0 1 1 0 00 0 1 1 0 2 0 2 3 03 0 1 1 1 11 1 1 1 0 6 0 6 4 14 1 0 0 0 00 0 0 0 1 1 1 1 5 15 1 0 0 1 11 1 0 0 1 5 1 5 6 16 1 1 1 0 00 0 1 1 1 3 1 3 7 17 1 1 1 1 11 1 1 1 1 7 1 7 自然顺序n n 二进制n n n n n n 倒位序二进制n n n n n n 倒位顺序n

19、 n2 1 0 0 1 2按频率抽取(DIF)的FFT算法 要求：N=2n10 xux)x(f)u(FNNW10 x)x(u10 xux12/xux10 xux2222)2x(f)x(f)x(f)x(fNNNNNNNNNNWNWWW 由于 故 因此 F(u)可表为 ux10 xu22)2x( f)x( fNNWWNNN, 12jNeWNuu) 1(2NNWux10 xu2)2x( f) 1()x( f)u(FNWNN1, 1 , 0uN N点DFT按u的奇偶分组可分为两个N/2的DFT 当u u为偶数,即 u=2ru=2r时,(-1)u =1； 当u u为奇数,即 u=2r+1 =2r+1 时

20、 (-1)u =-1 。 这时F(u)可分为两部分： rx10 xx210 x222)2x(f)x(f)2x(f)x(fNNNWNWNrN)2r(F)u(F1, 1 , 02Nru u为偶数时： 可见,上面两式均为N/2N/2的DFTDFT。x10 xxx)12(10 x222)2x(f)x(f)2x(f)x(f) 12(F)u(FrNrNNNNWWNWNru u为奇数时：1, 1 , 02Nr-1-1)2x(f)x(fN1, 1 ,0 x2Nx)2x(f)x(fNWN蝶形运算进行如下碟形运算：和)2x(f)x(fNxNW)2x(fN)x(f-1-1-1-1-1-1-1-1W WW WW WW

21、 WN NN NN NN N0 01 12 23 3N=8N=8时时, ,按按u u的奇偶分解过程的奇偶分解过程 先蝶形运算，后先蝶形运算，后DFT:DFT:)0(f) 1 (f)5(f)4(f) 3(f)2(f)7(f)6(f)0(F)2(F)6(F) 1 (F) 3(F)5(F)7(F)4(FDFTN点2DFTN点2仿照DIFDIF的方法 再将N/2N/2点DFTDFT按u的奇偶分解为两个N/4N/4点的DFTDFT,如此进行下去,直至分解为2 2点DFTDFT。 (0) F(0)(0) F(0)(1) F(4)(1) F(4)(2) F(2)(2) F(2)(3) F(6)(3) F(6

22、)(4) F(1)(4) F(1)(5) F(5)(5) F(5)(6) F(3)(6) F(3)(7) F(7)(7) F(7)-1-1-1-1-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 01 12 23 3-1-1-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 02 20 02 2-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 00 00 00 0ffffffff例如 N=8N=8时DIFDIF的FFTFFT流图如下： 1. 1.相同点 (1)(1)进行原位运算； (2)(2)运算量相同, ,均为（N/

23、2) Log2N次复乘, ,N Log2N次复加。 2.2.不同点 (1)DIT(1)DIT输入为倒位序,输出为自然顺序； DIFDIF正好与此相反。但DITDIT也有输入为自然顺序,输出为倒位序的情况。DIFDIF法与法与DITDIT法的异同法的异同原位运算：当数据输入到存储器以后，每一组运算的结果，仍然存放在这同一组存储器中直到最后输出。rNmmmWjkj)(F)(F)(F11rNmmmWjkk)(F)(F)(F11)(F1km)(F1jmrNW1(2)(2)蝶形运算不同a.a.(DIT)(DIT)用矩阵表示)(F km)(FjmrNWrNW)(F1km)(F1jm=11rNmmmWjkj

24、)(F)(F)(F11)(F)(F)(F11jkkmmm)(F1km)(F1jmrNW1b.b.(DFT)(DFT)用矩阵表示)(F km)(FjmrNWrNW)(F1km)(F1jm=11(3)(3)两种蝶形运算的关系 互为转置（矩阵）； 将流图的所有支路方向都反向, ,交换输入和输出，即可得到另一种蝶形。 a.a. DIT DITb.b.DFTDFTrNWrNW1111rNWrNWIFFTIFFT算法算法一一.稍微变动稍微变动FFT程序和参数可实现程序和参数可实现IFFT uxN1N0u1N0 xuxNW)u(FN1)u(FIDFT)x(fW)x(f)x(fDFT)u(F 比较两式可知,

25、,只要DFTDFT的每个系数 换成 , ,最后再乘以常数1/N1/N就可以得到IDFTIDFT的快速算法-IFFT。 另外, ,可以将常数1/N1/N分配到每级运算中, , , ,也就是每级蝶形运算均乘以1/1/2 2。 nkNWnkNWLLN)21(211二二.不改不改(FFT)(FFT)的的程序程序直接实现直接实现IFFTIFFT uxN1N0u1N0u*uxNW)u(FN1W)u(FN1)x(f)u(FDFTN1W)u(FN1uxN1N0u)x(f因此，BABAWWnkNnkN , 这就是说, ,先将F(u)F(u)取共轭, ,即将F(u)F(u)的虚部乘-1-1，直接利用FFTFFT程

26、序计算DFT；然后再取一次共轭；最后再乘1/N,1/N,即得 (x)(x)。所以FFT,IFFTFFT,IFFT可用一个子程序。f线性卷积的线性卷积的FFTFFT算法算法一一. .线性卷积的长度线性卷积的长度 设一离散线性移不变系统的冲激响 应为 , ,其输入信号为 . .其输出 为 . .并且 的长度为L点, , 的 长度为M点, ,则： )(nx)(nx)(nh)(nh)(ny)(nx)(nh10)()()()()(Lmmnhmxnhnxny)(ny以实例说明：0 1 0 1 2 2 3 31 12 23 3)(mx)(mh01211.。1。0 1 0 1 1 12 23 3)(mx2 3

27、)(m mh h )1(m mh h 300)()() 0(mmhmxy301)1 ()() 1 (mmhmxy。0 0 1 1 2 2 3 3)2(m mh h )3(m mh h 。0 1 0 1 1 12 23 3)(mx2 3。303)2()() 2(mmhmxy306)3()() 3(mmhmxy0 0 1 1 2 2 3 3 4 40 0 1 1 2 2 3 3 4 4 5 5)4(m mh h )5(m mh h 0 1 0 1 1 12 23 3)(mx2 3。305)4()() 4(mmhmxy303)5 ()() 5 (mmhmxy0 0 1 1 2 2 3 3 4 4 5

28、 51 13 33 35 56 66 6)(n ny y1)(MLny的长度为可见，。二二.用用FFTFFT算算 的步骤：的步骤： )(n ny y;1)(),(. 1点补零点，至少为将LMNnhnx；求)()(.2nhFFTkH；求)()(.3nxFFTkX；求)()()(.4kHkXkY。求)()(.5kYIFFTnyFFTFFTIFFTxx(n)h(n)y(n)X(k)H(k)Y(k)流程图3.1.6 总结 1、一维连续傅氏变换 2、二维连续傅氏变换F(u)f(x) due)u(F)x(fdxe)x(f)u(Fuxj2uxj2)v,u(F)y,x(f dudve)v,u(F)yx,(fd

29、xdye)y,x(f)v,u(F)vyux(j2)vyux(j2 3、一维离散傅氏变换fWF 1-N10u, x)u(F)x(f e )u(FN1)x(fe )x(f)u(FN1N0uNux2j1N0 xNux2j， 4、二维离散傅氏变换1N1 -MNM1M0u1N0v)NvyMux(j21M0 x1N0y)NvyMux(j2FWWf fWWF v)F(u,y)f(x, 1-N10y v 1-M1 , 0 xu, e )v, u(FMN1)yx,(fe )y, x(f)v, u(F， 图像频域变换的一般表达式： 反向变换核正向变换核式中：:v)u,y,h(x,:v)u,y,g(x,1N,2,1

30、 ,0v,y1-M,2,1 ,0u,x)v,u,y,x(h)v,u(F)y,x(fv)u,y,g(x,)y,x(f)v,u(F1M0u1N0v1M0 x1N0y 如果 则称正、反变换核是可分离的。 如果g1和g2，h1和h2在函数形式上是一样的，则称该变换核是对称的。)v, y(h)u, x(h)v, u, y, x(h)v, y(g)u, x(g)v, u, y, x(g2121例如，二维傅氏变换变换核：它们都是可分离的和对称的。Nuy2jMux2j)NvyMux(j2Nuy2jMux2j)NvyMux(j2eee)v, u, y, x(heee)v, u, y, x(g 图像变换的矩阵表示

31、： 其中，F和f是二维 的矩阵，P是 矩阵， Q是 矩阵。 11FQPfPfQFNNMMNM3.1.7 DFT应用中的问题 1、频谱的图像显示 谱图像就是把 作为亮度显示在屏幕上。但在傅立叶变换中F(u,v)随u,v的衰减太快，其高频只看到一两个峰，其余皆不清楚。在实际应用中，设显示信号为D(u,v)，有：)vu,(F)v, u(F1 (log)v, u(D 实用的公式，还要用K系统调整显示图像：|F(u,v)|u|D(u,v)|u)v, u(FK1 (log)v, u(D 2、频谱的频率移中将f(x, y)乘以因子(1)x+y，再进行离散傅立叶变换，即可将图像的频谱原点（0，0）移动到图像中

32、心（M2, N2）处。(a) 原图像；（b）无平移的傅立叶频谱；（c）平移后的傅立叶频谱(a) (b) (c) 3、旋转不变性用极坐标表示傅立叶变换对：则旋转不变性为： 如果时域中离散函数旋转0角度，则在变换域中该离散傅立叶变换函数也将旋转同样的角度。),R(F),(f),R(F),(f00(a)(b)(d)(c)（a） 原始图像； （b） 原始图像的傅立叶频谱； （c） 旋转45后的图像； （d） 图像旋转后的傅立叶频谱 第二节 离散余弦变换 3.2.1 一维离散余弦变换 设f(0),f(1),f(N-1)为离散的信号序列，则余弦正变换为： 其中：10u) 12x(2Ncos)(2)()(N

33、xxfNuCuF式中，u, x=0, 1, 2, , N1。1N,2, 1u1021)(uuC 将变换式展开整理后， 可以写成矩阵的形式， 即F=Cf其中2N) 12N)(1N(cos2N1)-3(Ncos2N) 1N(cos2N) 12N(cos2N3cos2Ncos212121N2c 反变换：可见一维DCT的逆变换核与正变换核是相同的记作：10u) 12x(2Ncos)()(2)(NuuFuCNxf式中， x, u=0, 1, 2, , N1FCfT 3.2.2 二维离散余弦变换NvyMuxvCuCyxfMNvuFMxNy2) 12 (cos2) 12 (cos)()(),(2),(101

34、0二维DCT定义如下：设f(x, y)为MN的数字图像矩阵，则 式中： x, u=0, 1, 2, , M1； y, v=0, 1, 2, , N1。 类似一维矩阵形式的DCT，可以写出二维DCT的矩阵形式如下：TNMfCCF 式中：x, u=0, 1, 2, , M1； y, v=0, 1, 2, , N1。 记作矩阵形式:NvyMuxvuFvCuCMNyxfMuNv2) 12(cos2) 12(cos),()()(2),(1010二维DCT逆变换定义如下：NTMFCCf 式中：1M,2, 1u1021)(Cuu1N,2, 1v10v21)v(C 快速离散余弦变换快速离散余弦变换 首先，将f

35、(x)延拓为 0)()(xfxfex=0, 1, 2, , N-1x=N， N+1, , 2N-1 按照一维DCT的定义，fe(x)的DCT为10)(1)0(NxexfNF NxujNxeNujNuxjNxeNxeNxexfeNexfNNuxxfNNuxxfNuF2212022)12(12012010)(Re2)(Re22) 12(cos)(22) 12(cos)(2)(式中，Re表示取复数的实部。 由于 为fe(x)的2N点DFT。因此，在 作DCT时，可把长度为N的f(x)的长度延拓为2N点的序列fe(x)，然后对fe(x)作DFT，最后取DFT的实部便可得到DCT的结果。12022)(N

36、xNxujeexf 同理对于离散余弦逆变换IDCT，可首先将F(u)延拓为0)()(uFuFeu=0, 1, 2, , N-1u=N, N+1, , 2N-1 1202221212) 12(121)(Re2)0(21)(Re2)0(12) 12(cos)(2)0(1)(NuNxujNujeeNuNuxjeeNueeeeuFNFNNeuFNFNNuxuFNFNxf即：DCT可由FFT来实现第三节 离散沃尔什变换3.3.1一维离散沃尔什变换（DWT） 要求样点 ，则 f(x)（x=0,1,2,N-1）的离散沃尔什变换对为： 式中 u、x = 0、1、2 N-1 nN210)()(101010)()

37、(1i1i)1()()()1()(1)(niubxbNuNxniubxbininuWxfxfNuW这里 是x的二进制表示的第i位值。10)()(10)()(11)1(),()1(1),(niubxbniubxbiniiniuxhNuxg 沃尔什正反变换核为：)(xbi当 n= 1、2、3时 如下表)(xbi下面是 n = 1、2、3 时的 g(x,u)，用“+”表示 +1、用“-”表示 -1例：求N = 4 时的沃尔什变换 因为 所以 u、x = 0、1、2、3 , n = 2224N)3()2()1 ()0(41)1()(41)0(3010)0()(12ffffxfWxibxbii)3()2

38、()1 ()0(41)1()(41)1 (3010)1()(1ffffxfWxibxbii)3()2()1 ()0(41)1()(41)3(3010)3()(1ffffxfWxibxbii)3()2()1()0(41)1()(41)2(3010)2()(1ffffxfWxibxbiiW ( 0 )W ( 1 )W ( 2 )W ( 3 ) f ( 0 ) f ( 1 ) f ( 2 ) f ( 3 )= 1/41 1 1 11 1 -1 -11 -1 1 -11 -1 -1 1用矩阵表达如下二维变换对为：其中，x,y,u,v=0,1,2N-1 101010)()()()(211) 1(),(1

39、),(NxNynivbybubxbiniiniyxfNvuW101010)()()()(11) 1(),(),(NuNvnivbybubxbiniinivuWyxf3.3.2、二维离散沃尔什变换其中，沃尔什正反变换核分别为：10)()()()(211) 1(1),(nivbybubxbiniiniNvuyxg10)()()()(11) 1(),(nivbybubxbiniinivuyxh沃尔什正反变换核是可分离的和对称的：GfGNW21GWGf 沃尔什变换的矩阵形式：g (x, y, u, v) = g1 (x, u) g2 (y, v) h (x, y, u, v) = h1 (x, u)

40、h2 (y, v) 其中，G是NxN的矩阵例：一个二维数字图像信号的矩阵为 求此信号的二维DWT。解：因为 这里N = 41331133113311331fGfGNW210000000000001002000000000000160032161111111111111111113311331133113311111111111111111241W第四节 离散哈达玛变换 也叫沃尔什-哈达玛变换。 哈达玛变换是一种特殊排列的沃尔什变换。哈达玛变换的最大优点在于它的变换核矩阵具有简单的递归关系，即高阶矩阵可以用两个低阶矩阵直积求得。3.4.1 一维离散哈达玛变换要求N=2n，一维离散哈达玛变换对为： 其中 u、x = 0、1、2 N-11010)()()1)(1)(NxniuibxibxfNuH1010)()()1)()(NuniuibxibuHxf)(zkb是z的二进制表示的第 k 位1010)()()()