第8章：信号处理中常用的正交变换

1、第8章 信号处理中常用的正交变换8.1 希尔伯特空间中的正交变换希尔伯特空间中的正交变换8.2 K-L变换变换8.3 离散余弦变换离散余弦变换(DCT)与与离散正弦变换离散正弦变换(DST) 8.4* 离散离散Hartley变换变换(DHT) 8.5* 离散离散W变换变换(DWT) 及正弦类变换及正弦类变换8.6* DCT、DST及及DWT快速算法简述快速算法简述8.7* 图象压缩简介图象压缩简介8.8* 重叠正交变换重叠正交变换8.9 与本章内容有关的与本章内容有关的MATLAB文件文件 目录目录希尔伯特空间中的正交变换希尔伯特空间中的正交变换赋范线性空间赋范线性空间 内积空间内积空间 完备

2、的内积空间（希尔伯特空间）完备的内积空间（希尔伯特空间）信号的分解信号的分解 设空间 是由 N 维空间一组向量12,NXspan 12,N XNnnnx1 对任一 ，都可作如下分解：xX所张成，即Xx信号的离散表示,或信号的分解12,N是分解系数或信号的变换 Nnnnx1由x正变换由x反变换12,N12,N12,N1,0iji jijij Step1:双正交关系( biorthogonality)Nnnnx11,Nnnjjn ,jx1,Nnnjn 12,N12,N对1,0iji jijij 则称12,N为一组正交基。一组正交基满足：注意：满足双正交关系的两组基向量各自并不满足正交关系，只是相互

3、之间满足正交关系。1,2,iiiN如果：信号的正交变换信号的正交变换给定数据向量： (0), (1), (1)Txxx Nx及算子N NA 作变换yAx矩阵 的行（列）向量即是前面的向量Ai若：, Ax Axx xy, y则上述变换即为正交变换，或保范（数）变换。A实际上是正交矩阵，1TAA以上正交变换是从线性代数的角度来定义。正交变换的性质：性质1：正交变换的基向量即是其对偶基向量。由性质1可知正交变换具有如下的优点：NNA 2. 正交变换在计算上最为简单。如果是离 散信号，且 N 是有限值，那么变换只是简单的矩阵与向量运算：yAx3. 反变换：1TxA yA y不需要求逆，特别有利于硬件实

4、现1. 若正变换存在，那么反变换一定存在，且变换是唯一的； 非正交基的情况下，“基向量”称为“标架（Frame)”, 这时，展开系数不是准确投影。2*| |( ) ( ),nxx n x nx x22|nn此性质实际上是 Parsevals 定理，即信号变换前后能量保持不变。注意，只有正交变换才有此性质。性质4：信号正交分解具有最小平方近似性质。 1,Nnnnnnx 1Lnnnx ,1,nnnL2( , )x x221( , )Nnn Lx x 性质5：正交变换的系数具有去除相关和集 中能量的性质。0111TNACAACAAC取取决决于于基基函函数数。现现能能量量集集中中，分分量量的的相相关关

5、性性、能能否否出出）投投影影的的结结果果能能否否减减少少（或或者者新新基基底底上上的的向向量量。底底上上的的投投影影，看看成成向向量量在在标标准准正正交交基基正正交交变变换换的的结结果果，可可以以为为特特征征向向量量。为为特特征征值值，存存在在正正交交变变换换维维离离散散信信号号对对）（具具有有下下列列性性质质：正正交交变变换换4)3()(,)2(;110111iiNTTTTMNTTAAAxxAAxxAxAxAxNIAAAAAAA 佳佳正正交交变变换换变变换换：统统计计意意义义上上的的最最变变换换（及及离离散散变变换换离离散散，离离散散正正弦弦变变换换，离离散散余余弦弦变变换换傅傅里里叶叶变变

6、换换正正弦弦类类正正交交变变换换斜斜变变换换及及变变换换，变变换换非非正正弦弦类类正正交交变变换换：变变换换正正弦弦类类正正交交变变换换非非正正弦弦类类正正交交变变换换正正交交变变换换的的种种类类LKDWTWDHTHartleyDSTDCTDFTSLTHRTHaarWHTHadamardWalshLK )()(),()()()()(:正交基的选择原则：正交基的选择原则：正交变换的实例：正交变换的实例： FS,FT, DTFT, DFS, DFT DCT,DST, DHT Walsh-Hadamard, Haar 变换 SLT(斜变换）正弦类正交变换非正弦类正交变换佳佳正正交交变变换换变变换换：

7、统统计计意意义义上上的的最最LK yAxyAxPCAAAAxxAAxxAxAxNxNTTiiNTTTTMN)(2)(,1101 。降降维维和和降降噪噪中中的的应应用用信信号号损损失失的的能能量量最最小小后后，的的结结果果中中较较小小分分量量丢丢掉掉：如如何何变变换换，使使变变换换后后背背景景问问题题为为特特征征向向量量。为为特特征征值值，个个信信号号互互不不相相关关或或者者变变换换后后相相关关矩矩阵阵对对角角化化使使变变换换结结果果的的如如何何正正交交变变换换维维离离散散信信号号：对对背背景景问问题题特征值分解特征值分解用于信号降噪用于信号降噪PCANmimmmmNimNixxxxxxxxxx

8、xxxxx1212143213211,3 ,2,1 ,1, 2, 23 , 22, 21 , 21, 1, 13 , 12, 11 , 1mNmimmmmmNimNixxxxxxxxxxxxxxxNjxjNjmxjlklkj, 11,min,min11,Njxj, 1 有趣发现有趣发现:相位不变。相位不变。阶次与截止频率？阶次与截止频率？ KL 变换 (Karhunen-Loeve) (0), (1), (1)Txxx Nx数据向量：0,00,10,11,01,11,11,01,11,1()()TxxxNNNNNNEcccccccccCxx协方差阵：( , )( , )xxC i jCj i体

9、现了信号各元素之间的相互关系KL 变换的思路：寻找正交矩阵 ，做变换 ， 使 的协方差阵 为对角阵。011yNC这样 (0), (1), (1)Tyyy Ny 之间彻底去除了相关性。AAxy yyC1. 由0 xIC求 的特征值011,N 3. 将 归一化，即令011,NA AA,1,0,1,1;iiiNA A步骤：xCxCN4. 由归一化的011,NA AA构成正交阵A5. 由 实现对 的 KL 变换：yAxx011TyxNCAC AAxy xy KL 变换的应用数据压缩：011(0)(1)(1)TNyyy NxA yAAA01(0)(1)( )myyy mmNxAAA 的 KL 展开x截短

10、yA xx欲使均方误差：2Exx为最小011,NA AA应是 的特征向量。xC11Nii m最小这时(0), (1), ( )yyy mmN由于用x表示xxC注意：对正交变换yAxy 不是时域序列，而是 的变换系数（即 ） ，如 DFT 的 。正交变换后，信号的能量一般集中在少数的变换系数上，所以可以舍去绝大部分系数，这并不明显损失信号的能量。由剩下的少量系数，如 ，通过反变换 可以很好的恢复出原信号。从而达到数据压缩的目的。x( )X k1xA y yiyKL 变换： 去相关性最彻底，在此意义上是最佳正交变换； 方向依赖待变换的信号。信号发生变化时，要重新求变换矩阵。特征值和特征向量的计算是

11、相当费时的，因此，KL变换没有快速算法。这就限制了KL变换的实际应用。011,NxAA AACx变换的正交矩阵 8.3 离散余弦变换（DCT）( ),0,1,1x nnN给定：定义：10)(1)0(NncnxNX102(21)( )( )cos21,2,1NcnnkXkx nNNkNDCT的 定义构成一矩阵，是变换的核函数变换域,2(21)cos2,0,1,1k nknkCgNNn kN012;10kggfor kDCT的核函数，DCT矩阵,2(2)cos2()22cos,0,1,1k nkknkkCgNNnkkgNNn kN离散余弦变换离散余弦变换(DCT)为正交矩阵为正交矩阵或合写为：或合

12、写为：离散余弦变换离散余弦变换NcTNNckNnnkNncNncNncCXCxxCXkkgNnkNknkgNnxCnxkXNkNknnxNkXnxNXDCT,;0012/1; 1, 2 , 1,2) 12(cos)(2)()()(; 1, 2 , 1,2) 12(cos)(2)()(1)0(: )(10,101010 DCT 的特点 DCT 是实变换； DCT 是正交变换； 在一定条件下，DCT近似 K-L 变换； DCT有快速算法。 正因为DCT有上述特点，因此，DCT在语音和图像压缩中已获得广泛应用。0187111135152coscoscoscos1161616168721351052c

13、oscoscoscos16161616ccCc1,0ijijij c c所以DCT是正交变换例：8 点 DCT：1TNcNcxCXCX1012(21)( )(0)( )cos2Nccknkx nXXnNNN DCT 反变换 在DCT中，正变换矩阵和反变换矩阵是一样的，都是实矩阵。特别有利于实时实现及硬件实现。 一阶马尔可夫过程（Markov-1):语音和图象处理中常用的数学模型。一个随机信号 ，若其pdf满足如下关系： 则称 为一阶马尔可夫过程。该式的含意是：已知过程在现在时刻的状态，那么，下一个时刻的状态只和现在的状态有关，而和过去的状态无关。111100()( ),(),()nnnnnnp

14、 X txX txX txX tx11()( ),( )( )nnnnnp X txX txX tX n)(tX212231231111NNNxNNN R 令 是Markov-1 随机序列相邻两元素之间的相关系数，则该序列的协方差矩阵有如下关系：,0,1,1,1ijx i ji jNR按 KL 变换的思路，现需要求 的特征值及特征向量，以形成变换的正交矩阵 。但对Markov-1 过程，协方差阵 的特征向量可以解析的给出，因此正交变换的矩阵也可解析的得到： 1/2,2(1) sin(1)(1)22,0,1,1i jjjNijNi jNAxRxRA)cos(2)cos()sin()1 ()tan

15、(22N是方程的根11tan()0N1, 1 , 0,/NjNjj有：由：22(1) (1 2cos()jj必有：11)1 (12200,1,1,jjN再由：1010NjjNjjjxR0Ni0,1,1,jjN0N将1, 1 , 0,/NjNjj正是DCT变换矩阵！代入1/2,2(1) sin(1)(1)22,0,1,1i jjjNijNi jNA,2(21) cos2i jijNNA,01 iNA经化简结论：当 时，对Markov-1过程做KL变换的正交矩阵正是DCT变换的变换矩阵，也即：此时的DCT近似KL变换。因为DCT有快速算法，另外， Markov-1过程可作为一大类信号（语音、图象）

16、的数学模型，因此 DCT在图象、语音压缩中起到了关键性的作用，成为国际上许多标准（如 JPEG, MPEG）的重要工具。1( ),1,2,x nnN给定：12( )( )sin()111,2,NsnnkXkx nNNkN定义：DST12( )( )sin()111,2,Nsknkx nXkNNnN反变换：离散正弦变换（DST）离散正弦变换离散正弦变换(DST) 为正交矩阵为正交矩阵核函数核函数离散正弦变换离散正弦变换NsTNNsnkNksNnsSXSxxSXNknNnkNSNnNnkkXNnXNkNnknxNkXDST,;, 2 , 1,1sin12;, 2 , 1,1sin)(12)(;,

17、2 , 1,1sin)(12)(: )(,1111 ,2sin()11,1,2,k nnkSNNn kN变换矩阵1,0ijijijs sDST也是正交变换,TsNNsXS xxS X)9/64sin()9/16sin()9/8sin()9/16sin()9/4sin()9/2sin()9/8sin()9/2sin()9/sin(928S可以证明，DST在一定条件下也是对KL变换的近似。如何评判近似的好坏)sin()(mmmmkakDFT:DCT:DST:KL :,n kn kn kn kWCSA正交矩阵的行（或列）向量具有上述形式yAxxRyR正弦类变换：1,12,1( , )( , )Nxi jijNyi jiji ji jRR变换前相关矩阵非对角线上元素的和；变换后相关矩阵非对角线上元素的和；越小越好12/1去除相关的“效率”，越