3.4 离散沃尔什变换
DFT或DCT变换都是以正弦或余弦三角函数为基本的正交函数基，而DFT的快速运算是复数范围内进行运算，不仅运算量庞大，而且运算复杂，DCT变换虽然避免了复数运算，但需要进行三角函数运算，运算复杂程度依然很高。因此，无论DFT，还是DCT运算，占用时间仍然较多，而在实际应用中，有时需要更为有效和便利的变换方法。沃尔什变换就是其中一种，它有效地避免了因数据本身原因所产生的运算复杂性，它由只有+1和—1两个数值所构成的完备正交基组成。由于沃尔什函数基是二值正交基，与数字逻辑的两个状态相对应，因而更加适用于计算机技术、数字信号处理等应用领域。
此外，与DFT相比，沃尔什变换减少了存储空间并提高了运算速度，这一点对图像处理来说是至关重要的，特别是在大量数据需要进行实时处理时，沃尔什变换更加显示出其优越性。
3.4.1 一维离散沃尔什变换
沃尔什（Walsh）变换与沃尔什函数密切相关，沃尔什函数是1923年由美国数学家沃尔什首先提出的。沃尔什函数系是一个完备正交函数系，其值只能取+1和—1。从排列次序上可将沃尔什函数分为三种定义方法：一是按照佩利排列来定义（按自然排序）；二是按照沃尔什排列来定义（按列率排序）；三是按照哈达玛排列来定义，又称为哈达玛变换。
1. 沃尔什正变换
设f（x）表示N点的一维离散序列，则一维沃尔什变换定义为
其中，一维沃尔什变换核为
式中，u=0，1，2，3，…，N—1；x=0，1，2，3，…，N—1。N是沃尔什变换的阶数，N=2n。bi（z）是z的二进制数的第i位数值，取值为0或1。如i=6，由于6的二进制表示为110，因此b0（z）=0，b1（z）=1，b2（z）=1。
2. 沃尔什逆变换
一维离散沃尔什逆变换定义为
逆变换的核为
h（x，u）=g（x，u）
一维沃尔什正、反变换核相同，沃尔什变换核是一个对称阵列，其行和列是正交的。沃尔什正、反变换形式本质上相同，因此，计算沃尔什变换的算法可直接用来求其逆变换。一维沃尔什变换也具有快速算法，简称为FWT，在形式上和FFT算法类似。当N=8时，其变换核用矩阵表示为
3.4.2 二维离散沃尔什变换
1. 二维沃尔什正变换
设f（x，y）表示M×N的二维离散序列，则二维沃尔什变换定义为
其中，二维离散沃尔什变换核为
式中，M=2m，N=2n。
二维离散沃尔什变换的变换核是可分离的，即
根据沃尔什变换的定义形式可以得出，二维沃尔什变换具有可分离特性，即一次二维沃尔什变换可以通过两次一维沃尔什变换来实现。
2. 二维沃尔什逆变换
二维沃尔什逆变换定义为
二维离散沃尔什逆变换核为
式中，M=2m，N=2n。
二维沃尔什逆变换的核为
h（x，u，y，v）=g（x，u，y，v）
同样，二维逆变换具有可分离性。二维沃尔什变换也可以表示为矩阵形式，即
式中，G1为M×M变换核方阵；G2为N×N变换核方阵。
3.4.3 沃尔什变换的频谱
和DCT变换相同，二维沃尔什变换也具有能量集中的性质，原始图像数据越是均匀分布，沃尔什变换后的数据越集中于矩阵的边角上，因此，二维沃尔什变换也常用于压缩图像信息。
例3-5：沃尔什变换实例
如图3-8所示是沃尔什变换的实例，图3-8（a）为对应于图3-7（a）的沃尔什变换结果，图3-8（b）为对应于图3-7（c）的沃尔什变换结果。
图3-8 沃尔什变换的频谱分布
沃尔什变换是将一个函数变换成取值为+l或—1的基本函数构成的级数，用它来逼近数字脉冲信号时要比DFT有利。因此，它在图像传输、通信技术和数据压缩中获得了广泛的使用。同时，沃尔什变换是实数，所以对工程应用问题，沃尔什变换的存储量比DFT少，而且运算速度非常快。
例3-6：有两个二维数字图像信号，即
（1）
（2）
分别求f1和f2的二维沃尔什变换。
离散二维沃尔什变换的求解过程如下：
根据理论，对于（1）和（2），均有M=N=4，因此，其二维沃尔什变换的核为
由此可得
