第7章_沃爾什-哈達瑪變換

1、第七章 頻域處理 7.5 7.5 離散沃爾什離散沃爾什- -哈達瑪變換哈達瑪變換（Walsh HadamardWalsh Hadamard Transform Transform） 7.5.1 格雷碼（格雷碼（Gray Code）（1）二進制到格雷碼的轉(zhuǎn)換：）二進制到格雷碼的轉(zhuǎn)換：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）格雷碼到二進制的轉(zhuǎ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時，時，T2； n=1時，時，T1； n=2時，時，T1/2； n=3時，時，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個周期。個周期。（連續(xù)）（連續(xù)） 若在若在t=(k+1/2)

4、/2n 處作取樣，則可得到一個離散的數(shù)據(jù)序列處作取樣，則可得到一個離散的數(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時，對前時，對前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取樣后得到的按沃爾什排列的沃爾什函數(shù)矩陣取樣后得到的按沃爾什排列的沃爾什函數(shù)矩陣第七章 頻域處理 （2）按佩利（）按佩利（Paley）排列的沃爾什函數(shù)）排列的沃爾什函數(shù)10), 1(),(pkkpitkRtiWal其中，其中，

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

9、達瑪（Hadamard）排列的沃爾什函數(shù)）排列的沃爾什函數(shù)10), 1(),(pkkHitkRtiWal其中，其中，R(k+1,t)是任意拉德梅克函數(shù)，是任意拉德梅克函數(shù)，是倒序的二是倒序的二進制碼的第進制碼的第k位數(shù)。位數(shù)。P為正整數(shù)，為正整數(shù)， 。 1 , 0ki第七章 頻域處理 例：當(dāng)例：當(dāng)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、后得到的按哈達瑪排列的沃爾什函數(shù)矩陣取樣后得到的按哈達瑪排列的沃爾什函數(shù)矩陣第七章 頻域處理 2n階哈達瑪矩陣有如下形式：階哈達瑪矩陣有如下形式： 1111 1 21HH111111111111111122224HHHHH2222222222211111NNNNNHHHHHHHHHHHHnnnnnn第七章 頻域處理 可見，哈達瑪矩陣的最大優(yōu)點在于它具有簡單的遞推關(guān)系，可見，哈達瑪矩陣的最大優(yōu)點在于它具有簡單的遞推關(guān)系， 即高階矩陣可用兩個低階矩陣的克羅內(nèi)克積即高階矩陣可用兩個低階矩陣的克羅內(nèi)克積(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、哈達瑪變換的本質(zhì)上是哈達瑪變換的本質(zhì)上是將離散序列將離散序列f(x)的各項值的符號按一定規(guī)律改變后，進行加減運的各項值的符號按一定規(guī)律改變后，進行加減運算，算， 因此，它比采用復(fù)數(shù)運算的因此，它比采用復(fù)數(shù)運算的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結(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)按奇偶進行分組，分按奇偶進行分組，分別進行別進行WHT。FWHT的基本關(guān)系為的基本關(guān)系為

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沃爾什沃爾什-哈達瑪?shù)牡芜\算示意圖（算法一）哈達瑪?shù)牡芜\算示意圖（算法一）第七章 頻域處理 算法二算法二21