第7章_沃爾什-哈達(dá)瑪變換

1、第七章 頻域處理 7.5 7.5 離散沃爾什離散沃爾什- -哈達(dá)瑪變換哈達(dá)瑪變換（Walsh HadamardWalsh Hadamard Transform Transform） 7.5.1 格雷碼（格雷碼（Gray Code）（1）二進(jìn)制到格雷碼的轉(zhuǎn)換：）二進(jìn)制到格雷碼的轉(zhuǎn)換：Bokppnnnnnnn),.,.,(1221Gokppggggggg),.,.,(1221010121121211,.,nngnngnngnngngkkkppppp第七章 頻域處理 十進(jìn)制十進(jìn)制 二進(jìn)制二進(jìn)制 二進(jìn)制二進(jìn)制 格雷碼格雷碼 （自然排序）（自然排序） （倒序）（倒序） 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）格雷碼到二進(jìn)制的轉(zhuǎn)換：）格雷碼到二進(jìn)制的轉(zhuǎn)換：03210321321321211.ggggnggggngggnggngnpppkpppkppppppppp第七章 頻域處理 7.5.2 拉德梅克函數(shù)（拉德梅克函數(shù)（Rademacher） 1 . 拉德梅克函數(shù)定義拉德梅克函數(shù)定義 可見，可見，R(n,t)為周期函數(shù)。為周期函數(shù)。)2sgn(sin),(ttnRn0101)sgn(

3、xxx第七章 頻域處理 2 . 拉德梅克函數(shù)的規(guī)律和特性拉德梅克函數(shù)的規(guī)律和特性（1）周期函數(shù)）周期函數(shù) n=0時(shí)，時(shí)，T2； n=1時(shí)，時(shí)，T1； n=2時(shí)，時(shí)，T1/2； n=3時(shí)，時(shí)，T1/22； R(n,t)=R(n,t+1/2n-1)120第七章 頻域處理 （2） 函數(shù)的取值函數(shù)的取值 R(n,t)的取值只有的取值只有1和和1。（3） 函數(shù)的頻率特性函數(shù)的頻率特性 R(n,t)是是R(n1,t)的二倍頻。的二倍頻。（4） 函數(shù)離散化函數(shù)離散化 如果已知如果已知n ，則，則R(n,t)在（在（0t1）范圍內(nèi)有）范圍內(nèi)有2n-1個(gè)周期。個(gè)周期。（連續(xù)）（連續(xù)） 若在若在t=(k+1/2)

4、/2n 處作取樣，則可得到一個(gè)離散的數(shù)據(jù)序列處作取樣，則可得到一個(gè)離散的數(shù)據(jù)序列 R(n,k)，其中，其中，k=0,1,22n-1 。（離散）（離散）第七章 頻域處理 7.5.3 沃爾什函數(shù)（沃爾什函數(shù)（Walsh） 沃爾什函數(shù)有三種不同的函數(shù)定義，但都可由拉德沃爾什函數(shù)有三種不同的函數(shù)定義，但都可由拉德梅克函數(shù)構(gòu)成。梅克函數(shù)構(gòu)成。（1）按沃爾什排列的沃爾什函數(shù)）按沃爾什排列的沃爾什函數(shù)10)(), 1(),(pkkwigtkRtiWal其中，其中，R(k+1,t)是任意拉德梅克函數(shù)，是任意拉德梅克函數(shù)，g(i)是是i的格雷碼，的格雷碼， g(i)k是此格雷碼的第是此格雷碼的第k位數(shù)。位數(shù)。P

5、為正整數(shù)，為正整數(shù)， 。 1 , 0)(kig第七章 頻域處理 例：當(dāng)例：當(dāng)p3時(shí)，對(duì)前時(shí)，對(duì)前8個(gè)個(gè)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取樣后得到的按沃爾什排列的沃爾什函數(shù)矩陣取樣后得到的按沃爾什排列的沃爾什函數(shù)矩陣第七章 頻域處理 （2）按佩利（）按佩利（Paley）排列的沃爾什函數(shù)）排列的沃爾什函數(shù)10), 1(),(pkkpitkRtiWal其中，其中，

7、R(k+1,t)是任意拉德梅克函數(shù)，是任意拉德梅克函數(shù)，ik是自然二進(jìn)制碼是自然二進(jìn)制碼的第的第k位數(shù)。位數(shù)。P為正整數(shù)，為正整數(shù)， 。 1 , 0ki第七章 頻域處理 例：當(dāng)例：當(dāng)p3時(shí)，對(duì)前時(shí)，對(duì)前8個(gè)個(gè)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取樣后得到的按佩利排列的沃爾什函數(shù)矩陣取樣后得到的按佩利排列的沃爾什函數(shù)矩陣第七章 頻域處理 （3）按哈達(dá)瑪（）按哈

9、達(dá)瑪（Hadamard）排列的沃爾什函數(shù)）排列的沃爾什函數(shù)10), 1(),(pkkHitkRtiWal其中，其中，R(k+1,t)是任意拉德梅克函數(shù)，是任意拉德梅克函數(shù)，是倒序的二是倒序的二進(jìn)制碼的第進(jìn)制碼的第k位數(shù)。位數(shù)。P為正整數(shù)，為正整數(shù)， 。 1 , 0ki第七章 頻域處理 例：當(dāng)例：當(dāng)p3時(shí)，對(duì)前時(shí)，對(duì)前8個(gè)個(gè)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、后得到的按哈達(dá)瑪排列的沃爾什函數(shù)矩陣取樣后得到的按哈達(dá)瑪排列的沃爾什函數(shù)矩陣第七章 頻域處理 2n階哈達(dá)瑪矩陣有如下形式：階哈達(dá)瑪矩陣有如下形式： 1111 1 21HH111111111111111122224HHHHH2222222222211111NNNNNHHHHHHHHHHHHnnnnnn第七章 頻域處理 可見，哈達(dá)瑪矩陣的最大優(yōu)點(diǎn)在于它具有簡(jiǎn)單的遞推關(guān)系，可見，哈達(dá)瑪矩陣的最大優(yōu)點(diǎn)在于它具有簡(jiǎn)單的遞推關(guān)系， 即高階矩陣可用兩個(gè)低階矩陣的克羅內(nèi)克積即高階矩陣可用兩個(gè)低階矩陣的克羅內(nèi)克積(Kronecker Product)求得。因此常采用哈達(dá)瑪排列定義的沃爾什變換。求得。因此常采用哈

12、達(dá)瑪排列定義的沃爾什變換。 第七章 頻域處理 7.5.4 離散沃爾什哈達(dá)瑪變換（離散沃爾什哈達(dá)瑪變換（DWHT） 一維離散沃爾什變換定義為一維離散沃爾什變換定義為 10),()(1)(NxHxuWalxfNuW一維離散沃爾什逆變換定義為一維離散沃爾什逆變換定義為 10),()()(NuHxuWaluWxf第七章 頻域處理 ) 1() 1 ()0(1) 1() 1 ()0(NfffHNNWWWN和和 ) 1() 1 ()0() 1() 1 ()0(NWWWHNfffN式中，式中，HN為為N階哈達(dá)瑪矩陣。階哈達(dá)瑪矩陣。第七章 頻域處理 由哈達(dá)瑪矩陣的特點(diǎn)可知，沃爾什由哈達(dá)瑪矩陣的特點(diǎn)可知，沃爾什-

13、哈達(dá)瑪變換的本質(zhì)上是哈達(dá)瑪變換的本質(zhì)上是將離散序列將離散序列f(x)的各項(xiàng)值的符號(hào)按一定規(guī)律改變后，進(jìn)行加減運(yùn)的各項(xiàng)值的符號(hào)按一定規(guī)律改變后，進(jìn)行加減運(yùn)算，算， 因此，它比采用復(fù)數(shù)運(yùn)算的因此，它比采用復(fù)數(shù)運(yùn)算的DFT和采用余弦運(yùn)算的和采用余弦運(yùn)算的DCT要簡(jiǎn)單得多。要簡(jiǎn)單得多。 第七章 頻域處理 例：例：將一維信號(hào)序列將一維信號(hào)序列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。 第七章 頻域處理 例：例：二維離散沃爾什變換的矩陣形式表達(dá)式為二維離散沃爾什變換的矩陣形式表達(dá)式為 133

15、11331133113311f和和 11111111111111112f求這兩個(gè)信號(hào)的二維求這兩個(gè)信號(hào)的二維WHT。 第七章 頻域處理 M=N=4， 其二維其二維WHT變換核為變換核為 11111111111111114H第七章 頻域處理 所以所以 00000000000010021111111111111111133113311331133111111111111111114121W第七章 頻域處理 00000000000000011111111111111111111111111111111111111111111111114122W第七章 頻域處理 二維二維WHT結(jié)果結(jié)果（a）原圖像）原

16、圖像 （b）WHT結(jié)果結(jié)果 第七章 頻域處理 從以上例子可看出，二維從以上例子可看出，二維WHT具有能量集中的特性，而具有能量集中的特性，而且原始數(shù)據(jù)中數(shù)字越是均勻分且原始數(shù)據(jù)中數(shù)字越是均勻分布，經(jīng)變換后的數(shù)據(jù)越集中于矩布，經(jīng)變換后的數(shù)據(jù)越集中于矩陣的邊角上。因此，二維陣的邊角上。因此，二維WHT可用于壓縮圖像信息。可用于壓縮圖像信息。 第七章 頻域處理 7.5.5 快速沃爾什變換（快速沃爾什變換（FWHT） 類似于類似于FFT，WHT也有快速算法也有快速算法FWHT， 也可將輸入序也可將輸入序列列f(x)按奇偶進(jìn)行分組，分按奇偶進(jìn)行分組，分別進(jìn)行別進(jìn)行WHT。FWHT的基本關(guān)系為的基本關(guān)系為

17、 )()(21)2()()(21)(uWuWNuWuWuWuWoeoe第七章 頻域處理 以以8 8階沃爾什哈達(dá)瑪變換為例，說明其快速算法。階沃爾什哈達(dá)瑪變換為例，說明其快速算法。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沃爾什沃爾什-哈達(dá)瑪?shù)牡芜\(yùn)算示意圖（算法一）哈達(dá)瑪?shù)牡芜\(yùn)算示意圖（算法一）第七章 頻域處理 算法二算法二21