第7章_沃尔什-哈达玛变换

1、第七章 频域处理 7.5 7.5 离散沃尔什离散沃尔什- -哈达玛变换哈达玛变换（Walsh HadamardWalsh Hadamard Transform Transform） 7.5.1 格雷码（格雷码（Gray Code）（1）二进制到格雷码的转换：）二进制到格雷码的转换：Bokppnnnnnnn),.,.,(1221Gokppggggggg),.,.,(1221010121121211,.,nngnngnngnngngkkkppppp第七章 频域处理 十进制十进制 二进制二进制 二进制二进制 格雷码格雷码 （自然排序）（自然排序） （倒序）（倒序） 0 000 000 000 1 0

2、01 100 001 2 010 010 011 3 011 110 010 4 100 001 110 5 101 101 111 6 110 011 101 7 111 111 100 例：例：第七章 频域处理 （2）格雷码到二进制的转换：）格雷码到二进制的转换：03210321321321211.ggggnggggngggnggngnpppkpppkppppppppp第七章 频域处理 7.5.2 拉德梅克函数（拉德梅克函数（Rademacher） 1 . 拉德梅克函数定义拉德梅克函数定义 可见，可见，R(n,t)为周期函数。为周期函数。)2sgn(sin),(ttnRn0101)sgn(

3、xxx第七章 频域处理 2 . 拉德梅克函数的规律和特性拉德梅克函数的规律和特性（1）周期函数）周期函数 n=0时，时，T2； n=1时，时，T1； n=2时，时，T1/2； n=3时，时，T1/22； R(n,t)=R(n,t+1/2n-1)120第七章 频域处理 （2） 函数的取值函数的取值 R(n,t)的取值只有的取值只有1和和1。（3） 函数的频率特性函数的频率特性 R(n,t)是是R(n1,t)的二倍频。的二倍频。（4） 函数离散化函数离散化 如果已知如果已知n ，则，则R(n,t)在（在（0t1）范围内有）范围内有2n-1个周期。个周期。（连续）（连续） 若在若在t=(k+1/2)

4、/2n 处作取样，则可得到一个离散的数据序列处作取样，则可得到一个离散的数据序列 R(n,k)，其中，其中，k=0,1,22n-1 。（离散）（离散）第七章 频域处理 7.5.3 沃尔什函数（沃尔什函数（Walsh） 沃尔什函数有三种不同的函数定义，但都可由拉德沃尔什函数有三种不同的函数定义，但都可由拉德梅克函数构成。梅克函数构成。（1）按沃尔什排列的沃尔什函数）按沃尔什排列的沃尔什函数10)(), 1(),(pkkwigtkRtiWal其中，其中，R(k+1,t)是任意拉德梅克函数，是任意拉德梅克函数，g(i)是是i的格雷码，的格雷码， g(i)k是此格雷码的第是此格雷码的第k位数。位数。P

5、为正整数，为正整数， 。 1 , 0)(kig第七章 频域处理 例：当例：当p3时，对前时，对前8个个Walw(i,t)取样，则：取样，则：Walw(0,t)=1 1, 1, 1, 1, 1, 1, 1, 1Walw(1,t)=R(1,t) 1, 1, 1, 1,-1,-1,-1,-1Walw(2,t)=R(1,t) R(2,t) 1, 1, -1,-1,-1,-1, 1,1Walw(3,t)=R(2,t) 1, 1,-1,-1, 1, 1,-1,-1Walw(4,t)=R(2,t) R(3,t) 1,-1,-1, 1, 1,-1,-1, 1Walw(5,t)=R(1,t) R(2,t) R(

6、3,t) 1,-1,-1, 1,-1, 1, 1,-1Walw(6,t)=R(1,t) R(3,t) 1,-1, 1,-1,-1, 1,-1, 1Walw(7,t)=R(3,t) 1,-1, 1,-1, 1,-1, 1,-1第七章 频域处理 1111111111111111111111111111111111111111111111111111111111111111WH取样后得到的按沃尔什排列的沃尔什函数矩阵取样后得到的按沃尔什排列的沃尔什函数矩阵第七章 频域处理 （2）按佩利（）按佩利（Paley）排列的沃尔什函数）排列的沃尔什函数10), 1(),(pkkpitkRtiWal其中，其中，

7、R(k+1,t)是任意拉德梅克函数，是任意拉德梅克函数，ik是自然二进制码是自然二进制码的第的第k位数。位数。P为正整数，为正整数， 。 1 , 0ki第七章 频域处理 例：当例：当p3时，对前时，对前8个个Walp(i,t)取样，则：取样，则：Walp(0,t)=1 1, 1, 1, 1, 1, 1, 1, 1Walp(1,t)=R(1,t) 1, 1, 1, 1,-1,-1,-1,-1Walp(2,t)=R(2,t) 1, 1,-1,-1, 1, 1,-1,-1Walp(3,t)= R(1,t) R(2,t) 1, 1, -1,-1,-1,-1, 1,1Walp(4,t)=R(3,t) 1

8、,-1, 1,-1, 1,-1, 1,-1Walp(5,t)=R(1,t) R(3,t) 1,-1, 1,-1,-1, 1,-1, 1Walp(6,t)=R(2,t) R(3,t) 1,-1,-1, 1, 1,-1,-1, 1Walp(7,t)=R(1,t) R(2,t) R(3,t) 1,-1,-1, 1,-1, 1, 1,-1 第七章 频域处理 1111111111111111111111111111111111111111111111111111111111111111PH取样后得到的按佩利排列的沃尔什函数矩阵取样后得到的按佩利排列的沃尔什函数矩阵第七章 频域处理 （3）按哈达玛（）按哈

9、达玛（Hadamard）排列的沃尔什函数）排列的沃尔什函数10), 1(),(pkkHitkRtiWal其中，其中，R(k+1,t)是任意拉德梅克函数，是任意拉德梅克函数，是倒序的二是倒序的二进制码的第进制码的第k位数。位数。P为正整数，为正整数， 。 1 , 0ki第七章 频域处理 例：当例：当p3时，对前时，对前8个个WalH(i,t)取样，则：取样，则：WalH(0,t)=1 1, 1, 1, 1, 1, 1, 1, 1WalH(1,t)=R(3,t) 1,-1, 1,-1, 1,-1, 1,-1WalH(2,t)=R(2,t) 1, 1,-1,-1, 1, 1,-1,-1WalH(3,

10、t)=R(2,t) R(3,t) 1,-1,-1, 1, 1,-1,-1, 1WalH(4,t)=R(1,t) 1, 1, 1, 1,-1,-1,-1,-1WalH(5,t)=R(1,t) R(3,t) 1,-1, 1,-1,-1, 1,-1, 1WalH(6,t)=R(1,t) R(2,t) 1, 1, -1,-1,-1,-1, 1,1WalH(7,t)=R(1,t) R(2,t) R(3,t) 1,-1,-1, 1,-1, 1, 1,-1第七章 频域处理 1111111111111111111111111111111111111111111111111111111111111111HH取样

11、后得到的按哈达玛排列的沃尔什函数矩阵取样后得到的按哈达玛排列的沃尔什函数矩阵第七章 频域处理 2n阶哈达玛矩阵有如下形式：阶哈达玛矩阵有如下形式： 1111 1 21HH111111111111111122224HHHHH2222222222211111NNNNNHHHHHHHHHHHHnnnnnn第七章 频域处理 可见，哈达玛矩阵的最大优点在于它具有简单的递推关系，可见，哈达玛矩阵的最大优点在于它具有简单的递推关系， 即高阶矩阵可用两个低阶矩阵的克罗内克积即高阶矩阵可用两个低阶矩阵的克罗内克积(Kronecker Product)求得。因此常采用哈达玛排列定义的沃尔什变换。求得。因此常采用哈

12、达玛排列定义的沃尔什变换。 第七章 频域处理 7.5.4 离散沃尔什哈达玛变换（离散沃尔什哈达玛变换（DWHT） 一维离散沃尔什变换定义为一维离散沃尔什变换定义为 10),()(1)(NxHxuWalxfNuW一维离散沃尔什逆变换定义为一维离散沃尔什逆变换定义为 10),()()(NuHxuWaluWxf第七章 频域处理 ) 1() 1 ()0(1) 1() 1 ()0(NfffHNNWWWN和和 ) 1() 1 ()0() 1() 1 ()0(NWWWHNfffN式中，式中，HN为为N阶哈达玛矩阵。阶哈达玛矩阵。第七章 频域处理 由哈达玛矩阵的特点可知，沃尔什由哈达玛矩阵的特点可知，沃尔什-

13、哈达玛变换的本质上是哈达玛变换的本质上是将离散序列将离散序列f(x)的各项值的符号按一定规律改变后，进行加减运的各项值的符号按一定规律改变后，进行加减运算，算， 因此，它比采用复数运算的因此，它比采用复数运算的DFT和采用余弦运算的和采用余弦运算的DCT要简单得多。要简单得多。 第七章 频域处理 例：例：将一维信号序列将一维信号序列0，0，1，1，0，0，1，1作作WHT变变换及反变换。换及反变换。000002/102/111001100111111111111111111111111111111111111111111111111111111111111111181)7()6()5()4()

14、3()2() 1 ()0(WWWWWWWW第七章 频域处理 二维离散沃尔什变换二维离散沃尔什变换 很容易将一维很容易将一维WHT的定义推广到二维的定义推广到二维WHT。二维。二维WHT的的正变换核和逆变换核分别为正变换核和逆变换核分别为 1010),(),(),(1),(NyHHMxyvWslxuWalyxfMNvuW1010),(),(),(),(NvHHMuyvWslxuWalvuWyxf和和 式中：式中：x, u=0, 1, 2, , M1； y, v=0, 1, 2, , N1。 第七章 频域处理 例：例：二维离散沃尔什变换的矩阵形式表达式为二维离散沃尔什变换的矩阵形式表达式为 133

15、11331133113311f和和 11111111111111112f求这两个信号的二维求这两个信号的二维WHT。 第七章 频域处理 M=N=4， 其二维其二维WHT变换核为变换核为 11111111111111114H第七章 频域处理 所以所以 00000000000010021111111111111111133113311331133111111111111111114121W第七章 频域处理 00000000000000011111111111111111111111111111111111111111111111114122W第七章 频域处理 二维二维WHT结果结果（a）原图像）原

16、图像 （b）WHT结果结果 第七章 频域处理 从以上例子可看出，二维从以上例子可看出，二维WHT具有能量集中的特性，而具有能量集中的特性，而且原始数据中数字越是均匀分且原始数据中数字越是均匀分布，经变换后的数据越集中于矩布，经变换后的数据越集中于矩阵的边角上。因此，二维阵的边角上。因此，二维WHT可用于压缩图像信息。可用于压缩图像信息。 第七章 频域处理 7.5.5 快速沃尔什变换（快速沃尔什变换（FWHT） 类似于类似于FFT，WHT也有快速算法也有快速算法FWHT， 也可将输入序也可将输入序列列f(x)按奇偶进行分组，分按奇偶进行分组，分别进行别进行WHT。FWHT的基本关系为的基本关系为

17、 )()(21)2()()(21)(uWuWNuWuWuWuWoeoe第七章 频域处理 以以8 8阶沃尔什哈达玛变换为例，说明其快速算法。阶沃尔什哈达玛变换为例，说明其快速算法。1111 1 21HH00000000000000000000000000000021044442222222222224444222222224444444444428GGGIIIIIIIIIIIIHHHHIIIIHHHHHHHHIIIIHHHHHHHHH1111 1 21HH第七章 频域处理 )(81)(81)(2108xfGGGxfHuW令：令：)()()()()()(20311221xfGxfxfGxfxfGx

18、f)(81)(3xfuW则：则：算法一算法一第七章 频域处理 )()()()()()(20311221xfGxfxfGxfxfGxf)7()3()6()2()5() 1 ()4()0()7()3()6()2()5() 1 ()4()0()7()6()5()4()3()2() 1 ()0()7()6()5()4()3()2() 1 ()0(211111111ffffffffffffffffffffffffGffffffff第七章 频域处理 )()()()()()(20311221xfGxfxfGxfxfGxf)7()5()6()4()7()5()6()4()3() 1 ()2()0()3() 1

19、 ()2()0()7()6()5()4()3()2() 1 ()0()7()6()5()4()3()2() 1 ()0(111111111111111111111111122222222ffffffffffffffffffffffffGffffffff第七章 频域处理 )()()()()()(20311221xfGxfxfGxfxfGxf)7()6()7()6()5()4()5()4()3()2()3()2() 1 ()0() 1 ()0()7()6()5()4()3()2() 1 ()0()7()6()5()4()3()2() 1 ()0(22222222222222222222222203

20、3333333ffffffffffffffffffffffffGffffffff第七章 频域处理 )7()6()5()4()3()2() 1 ()0(22222222ffffffff)7()6()5()4()3()2() 1 ()0(33333333ffffffff)7()6()5()4()3()2() 1 ()0(WWWWWWWW)7()6()5()4()3()2() 1 ()0(ffffffff)7()6()5()4()3()2() 1 ()0(11111111ffffffff-1-1-1-1-1-1-1-1-1-1-1-11/81/81/81/81/81/81/81/8沃尔什沃尔什-哈达玛的蝶形运算示意图（算法一）哈达玛的蝶形运算示意图（算法一）第七章 频域处理 算法二算法二21