离散沃尔什变换(DWT

第二章图像变换2.3离散沃尔什变换（DWT，DiscreteWalshTransform）由于傅里叶变换和余弦变换的变换核由正弦、余弦函数组成，运算速度受影响。在特定问题中，往往引进不同的变换方法，以求运算简单且变换核矩阵产生方便。WalshTransform中的变换矩阵简单（只有1和－1），占用存储空间少，产生容易，有快速算法，在需要实时处理大量数据的图像处理问题中，应用广泛。2.3.1One-DWalshTransform[4]假如，则离散2nN=()(0,1,2,,1)fxxN=−的WalshT1,,2,1,0)1)((1)(1,,2,1,0)1)((1)(10)()(10)()(101101−=∑−=−=∑−=∑∑−=−=−=−−−=−−NxuWNxfNuxfNuWNuubxbNxubxbniininiini其变换核：1101()()1()()01(,)(,)(1)1(1)niniiinibxbunbxbuigxuhxuNN−−−=−−−=∑==−=−∏其中：z的二进制数的第i＋1位的值（即0或1）。()ibz例如，N＝2n=8时的变换核和反变换核用矩阵形式表示为1第二章图像变换()81111111111111111111u=01234567x=01111111111111111118121111113G−−−−−−−−−−−−=−−−−−−45111111111111111111111176⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥−−⎢⎥−−⎢⎥⎢⎥−−⎢⎥−−−−⎢⎥⎣⎦例、G中元素（－1）。对应x=1,u=4,n=3,考虑x=1=(0001)二进制，u=4=(0100)二进制,而110()()niniibxbu−−−=∑∵＝b0(1)b2(4)＋b1(1)b1(4)+b2(1)b0(4)=1*1+0*0+0*0=1()110()()-11niniibxbu−−−=∑∴=−实际上，上述的变换核函数是所谓Paley序的离散公式，还有所谓Walsh序和Hadamard序的核函数表示式，这三种序是可以互相转换的，可参见本章参考文献1（容观澳书）pp.87-88。2第二章图像变换2.3.2Two-D离散Walsh变换[4]正反变换核相同，为[]111100()()()()(,,,)(,,,)1(1)mnimijnjijbxbubybvgxuyvhxuyvMN−−−−−−−−⎡⎤+⎣⎦=∑∑=−①二维Walsh变换对为1100W(,)(,)(,,,)(0,1,2,,10,1,2,,1)MNxyuvfxygxuyvuMvN−−====−=∑∑−−②1100(,)(,)(,,,)(0,1,2,,10,1,2,,1)MNuvfxyWuvhxuyvxMyN−−====−=∑∑③这里假定了nmNM2,2==●变换核具有可分离性质从①式可知：[][]∑−∑−====−=−−−=−−111111)()()()(2121)1(1)1(1),(),(),(),(),,,(),,,(njjnjmiimivbxbubxbNMvyhuxhvyguxgvyuxhvyuxg二维离散Walsh变换可由两次变换来实现。●变换对的矩阵形式121111,WGfGfGMNMN==2WG其中是1GMM×的变换核方阵；是2GNN×的变换核方阵。两者由＋1或－1组成。3第二章图像变换●WT具有能量集中性质例、对于均匀分布的二维图像信号1111111111111111f⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦作WalshTransform,可得1000000000000000W⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦这说明，假如输入的原始图像均匀分布，那么Walsh变换后的数据会集中于矩阵的边角上，可见此变换可以用于图像信息压缩。●快速WT运算可采用与快速傅里叶变换类似的计算，将FFT中的⎥⎦⎤⎢⎣⎡−uxNjπ2exp变成1即可。快速Walsh变换简写为FWT。关于的WT的快速算法的蝶形图构成举例和算法，可参见本章参考文献1（容观澳书）pp.89-90。8N=关于WT，在本章参考文献3（阮秋琦书）pp.85-112中，有较深入的介绍。4