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

第第7 7章章_ _沃尔什沃尔什-哈达玛变哈达玛变换换第七章 频域处理 十进制十进制二进制二进制二进制二进制格雷码格雷码（自然排序）（自然排序）（倒序）（倒序）00000000001001100001201001001130111100104100001110510110111161100111017111111100例：例：第七章 频域处理（2）格雷码到二进制的转换：）格雷码到二进制的转换：第七章 频域处理 7.5.2 拉德梅克函数（拉德梅克函数（Rademacher）1.拉德梅克函数定义拉德梅克函数定义 可见，可见，R(n,t)为周期函数。为周期函数。第七章 频域处理 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)/2n 处作取样，则可得到一个离散的数据序列处作取样，则可得到一个离散的数据序列 R(n,k)，其中，其中，k=0,1,22n-1。（离散）（离散）第七章 频域处理 7.5.3 沃尔什函数（沃尔什函数（Walsh）沃尔什函数有三种不同的函数定义，但都可由拉德梅沃尔什函数有三种不同的函数定义，但都可由拉德梅克函数构成。克函数构成。（1）按沃尔什排列的沃尔什函数）按沃尔什排列的沃尔什函数其中，其中，R(k+1,t)是任意拉德梅克函数，是任意拉德梅克函数，g(i)是是i的格雷码，的格雷码，g(i)k是此格雷码的第是此格雷码的第k位数。位数。P为正整数，为正整数，。第七章 频域处理 例：当例：当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(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第七章 频域处理 取样后得到的按沃尔什排列的沃尔什函数矩阵取样后得到的按沃尔什排列的沃尔什函数矩阵第七章 频域处理（2）按佩利（）按佩利（Paley）排列的沃尔什函数）排列的沃尔什函数其中，其中，R(k+1,t)是任意拉德梅克函数，是任意拉德梅克函数，ik是自然二进制码是自然二进制码的第的第k位数。位数。P为正整数，为正整数，。第七章 频域处理 例：当例：当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,-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 第七章 频域处理 取样后得到的按佩利排列的沃尔什函数矩阵取样后得到的按佩利排列的沃尔什函数矩阵第七章 频域处理（3）按哈达玛（）按哈达玛（Hadamard）排列的沃尔什函数）排列的沃尔什函数其中，其中，R(k+1,t)是任意拉德梅克函数，是任意拉德梅克函数，是倒序的二进是倒序的二进制码的第制码的第k位数。位数。P为正整数，为正整数，。第七章 频域处理 例：当例：当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,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第七章 频域处理 取样后得到的按哈达玛排列的沃尔什函数矩阵取样后得到的按哈达玛排列的沃尔什函数矩阵第七章 频域处理 2n阶哈达玛矩阵有如下形式：阶哈达玛矩阵有如下形式：第七章 频域处理 可见，哈达玛矩阵的最大优点在于它具有简单的递推关系，可见，哈达玛矩阵的最大优点在于它具有简单的递推关系，即高阶矩阵可用两个低阶矩阵的克罗内克积即高阶矩阵可用两个低阶矩阵的克罗内克积(Kronecker Product)求得。因此常采用哈达玛排列定义的沃尔什变换。求得。因此常采用哈达玛排列定义的沃尔什变换。第七章 频域处理 7.5.4 离散沃尔什哈达玛变换（离散沃尔什哈达玛变换（DWHT）一维离散沃尔什变换定义为一维离散沃尔什变换定义为 一维离散沃尔什逆变换定义为一维离散沃尔什逆变换定义为 第七章 频域处理 和和式中，式中，HN为为N阶哈达玛矩阵。阶哈达玛矩阵。第七章 频域处理 由由哈哈达达玛玛矩矩阵阵的的特特点点可可知知，沃沃尔尔什什-哈哈达达玛玛变变换换的的本本质质上上是是将将离离散散序序列列f(x)的的各各项项值值的的符符号号按按一一定定规规律律改改变变后后，进进行行加加减减运运算算，因因此此，它它比比采采用用复复数数运运算算的的DFT和和采采用用余余弦弦运运算算的的DCT要简单得多。要简单得多。第七章 频域处理 例：例：将一维信号序列将一维信号序列0，0，1，1，0，0，1，1作作WHT变变换及反变换。换及反变换。第七章 频域处理 二维离散沃尔什变换二维离散沃尔什变换很容易将一维很容易将一维WHT的定义推广到二维的定义推广到二维WHT。二维。二维WHT的的正变换核和逆变换核分别为正变换核和逆变换核分别为 和和式中：式中：x,u=0,1,2,M1；y,v=0,1,2,N1。第七章 频域处理 例：例：二维离散沃尔什变换的矩阵形式表达式为二维离散沃尔什变换的矩阵形式表达式为 和和求这两个信号的二维求这两个信号的二维WHT。第七章 频域处理 M=N=4，其二维其二维WHT变换核为变换核为第七章 频域处理 所以所以第七章 频域处理 第七章 频域处理 二维二维WHT结果结果（a）原图像）原图像（b）WHT结果结果第七章 频域处理 从从以以上上例例子子可可看看出出，二二维维WHT具具有有能能量量集集中中的的特特性性，而而且且原原始始数数据据中中数数字字越越是是均均匀匀分分布布，经经变变换换后后的的数数据据越越集集中中于于矩矩阵的边角上。因此，二维阵的边角上。因此，二维WHT可用于压缩图像信息。可用于压缩图像信息。第七章 频域处理 7.5.5 快速沃尔什变换（快速沃尔什变换（FWHT）类类似似于于FFT，WHT也也有有快快速速算算法法FWHT，也也可可将将输输入入序序列列f(x)按奇偶进行分组，分别进行按奇偶进行分组，分别进行WHT。FWHT的基本关系为的基本关系为 第七章 频域处理 以以8 8阶沃尔什哈达玛变换为例，说明其快速算法。阶沃尔什哈达玛变换为例，说明其快速算法。第七章 频域处理 令：令：则：则：算法一算法一第七章 频域处理 第七章 频域处理 第七章 频域处理 第七章 频域处理-1-1-1-1-1-1-1-1-1-1-1-11/81/81/81/81/81/81/81/8沃尔什沃尔什-哈达玛的蝶形运算示意图（算法一）哈达玛的蝶形运算示意图（算法一）第七章 频域处理 算法二算法二由于由于H8 G0 G1 G2均为对称矩阵，均为对称矩阵，故故H8 H8G0 G0 G1 G G2 G第七章 频域处理 令：令：则：则：第七章 频域处理 1/81/81/81/81/81/81/81/8-1-1-1-1-1-1-1-1-1-1-1-1沃尔什沃尔什-哈达玛的蝶形运算示意图（算法二）哈达玛的蝶形运算示意图（算法二）第七章 频域处理 综综上上所所述述，WHT是是将将一一个个函函数数变变换换成成取取值值为为1或或1的的基基本本函函数数构构成成的的级级数数，用用它它来来逼逼近近数数字字脉脉冲冲信信号号时时要要比比FFT有有利利。同同时时，WHT只只需需要要进进行行实实数数运运算算，存存储储量量比比FFT要要少少得得多多，运运算算速速度度也也快快得得多多。因因此此，WHT在在图图像像传传输输、通通信信技技术术和数据压缩中被广泛使用。和数据压缩中被广泛使用。结束语结束语谢谢大家聆听！谢谢大家聆听！40