数字信号处理-正交变换

第8章正交变换8.1正交变换；8.2K—L变换8.3离散余弦（正弦）变换（DCT,DST）8.4离散Hartley变换（DHT）8.5离散W变换8.6DCT、DST、DWT快速算法（略）8.7关于图像压缩及国际标准（讲座1）8.8重叠正交变换（LOT）（讲座2）一、信号的分解设空间是由N维空间一组向量12{,,,}NXspan12,,,NX概念：8.1正交变换Nnnnx1对任一，都可作如下分解：xX所张成，即信号的离散表示,或信号的分解12,,,N是分解系数或信号的变换Nnnnx1由x正变换由x反变换12,,,N12,,,N如何求出分解系数设想另有一组向量12ˆˆˆ,,,N1ˆ,0ijijijijStep1:满足：双正交关系(biorthogonality)1ˆ2ˆ21例如：1100.5ˆ112220.5ˆ101ˆ2ˆ2111ˆ,1显然：12ˆ,021ˆ,022ˆ,1两组向量，互为“对偶基”，或“倒数基”。1ˆ,NnnjjnStep2:做内积1ˆ,Nnnjnˆ,jx*ˆ()()jxttdtˆ(),()jjxtt*ˆ()()jnxnnˆ(),()jjxnnNnnnx112ˆˆˆ,,,N12,,,N对1,0ijijijij则称12,,,N为一组正交基。一组正交基满足：注意：满足双正交关系的两组基向量各自并不满足正交关系，只是相互之间满足正交关系。ˆ1,2,,iiiN如果：几点说明：用向量表示信号，会出现几种不同的情况，取决于的性质：iix1.如果空间中的任一元素都可由来分解，则称该向量是“完备（complete）”的；xXi2.如果完备且线性相关，则对的表示必然存在信息冗余，且对偶向量不唯一。可能构成一个“标架（Frame)”;iix3.如果是完备的，且是线性无关的，则它构成中的一组基向量，这时其对偶向量存在且唯一，即存在前述的双正交关系；这时的基称为Riesz基。Xi4.如果ˆ1,2,,iiiN则是中的一组正交基。Xi二、信号的正交变换[(0),(1),,(1)]TxxxNx给定数据向量：及算子NNA作变换yAx若：,,AxAxxxy,y则上述变换即为正交变换，或保范（数）变换矩阵的行（列）向量即是前面的向量AiNNA实际上是正交矩阵，1TAA以上正交变换是从线性代数的角度来定义。正交变换的性质：性质1：正交变换的基向量即是其对偶基向量。由性质1可知正交变换具有如下的优点：2.正交变换在计算上最为简单。如果是离散信号，且N是有限值，那么变换只是简单的矩阵与向量运算：yAx3.反变换：1TxAyAy不需要求逆，特别有利于硬件实现1.若正变换存在，那么反变换一定存在，且变换是唯一的；性质2：展开系数是信号在基向量上的准确投影非正交基的情况下，“基向量”称为“标架（Frame)”,这时，展开系数不是准确投影。123123x2*||||()(),nxxnxnxx22||||||nn性质3：正交变换保证变换前后信号的能量不变，此性质又称为“保范(数)变换”。此性质实际上是Parseval’s定理，即信号变换前后能量保持不变。注意，只有正交变换才有此性质。性质4：信号正交分解具有最小平方近似性质。1,Nnnnnnx1ˆLnnnx最小的条件：,1,,nnnL2ˆ(,)xx221ˆ(,)NnnLxx傅立叶级数的截短、第7章的FIR滤波器设计等，均要用到该性质。ˆxxˆ,xx2ˆ||||xx2ˆ(,)xx性质5：正交变换的系数具有去除相关和集中能量的性质。数据压缩的理论基础。后面即将讨论。给定一个实对称矩阵，一定可以找到一个正交阵，使得：CA0111TNACAACA正交基的选择原则：具有所希望的物理意义或实用意义；正交基函数应尽量简单，计算量小；最大限度浓缩信号能量，去除相关性；基函数应能同时具有频域和时域的定位功能正交变换的实例：FS，FT,DTFT,DFS,DFTDCT，DST,DHTWalsh-Hadamard,Haar变换，SLT(斜变换）正弦类正交变换非正弦类正交变换8.2K—L变换(Karhunen--Loeve)[(0),(1),,(1)]TxxxNx数据向量：0,00,10,11,01,11,11,01,11,1()()TxxxNNNNNNEcccccccccCxx协方差阵：(,)(,)xxCijCji体现了信号各元素之间的相互关系K—L变换的思路：寻找正交矩阵，做变换，使的协方差阵为对角阵。AyAxyyC这样[(0),(1),,(1)]TyyyNy之间彻底去除了相关性。如何实现1.由求的特征值2.求的个特征向量N3.将归一化，即令步骤：4.由归一化的构成正交阵A5.由实现对的K—L变换:yAxx这样，信号中的各个元素之间彻底去除了相关性！y要求：会证明此式K—L变换的应用－数据压缩：011(0)(1)(1)TNyyyNxAyAAA01ˆ(0)(1)()myyymmNxAAA的K—L展开x截短yAx欲使均方误差：2ˆ[]Exx为最小应是的特征向量。11Niim最小这时(0),(1),,()yyymmN由于用x表示注意：对正交变换yAxy不是时域序列，而是的变换系数（即），如DFT的。正交变换后，信号的能量一般集中在少数的变换系数上，所以可以舍去绝大部分系数，这并不明显损失信号的能量。由剩下的少量系数，如，通过反变换可以很好的恢复出原信号。从而达到数据压缩的目的。x()Xk1ˆˆxAyˆyiK—L变换：去相关性最彻底，在此意义上是最佳正交变换；方向依赖待变换的信号。信号发生变化时，要重新求变换矩阵。特征值和特征向量的计算是相当费时的，因此，K—L变换没有快速算法。这就限制了K—L变换的实际应用。变换的正交矩阵8.3离散余弦变换（DCT）(),0,1,,1xnnN给定：定义：DCT的定义构成一矩阵，是变换的核函数变换域012;10kggforkDCT的核函数，DCT矩阵2jnknkNNWeDCT的特点DCT是实变换；DCT是正交变换；在一定条件下，DCT近似K-L变换；DCT有快速算法。正因为DCT有上述特点，因此，DCT在语音和图像压缩中已获得广泛应用。1,0ijijijcc所以DCT是正交变换例：8点DCT：DCT反变换在DCT中，正变换矩阵和反变换矩阵是一样的，都是实矩阵。特别有利于实时实现及硬件实现。一阶马尔可夫过程（Markov-1):语音和图象处理中常用的数学模型。一个随机信号，若其pdf满足如下关系：则称为一阶马尔可夫过程。该式的含意是:已知过程在现在时刻的状态，那么，下一个时刻的状态只和现在的状态有关，而和过去的状态无关。111100[()(),(),,()]nnnnnnpXtxXtxXtxXtx11[()()],()()nnnnnpXtxXtxXtXn()Xt212231231111NNNxNNNR令是Markov-1随机序列相邻两元素之间的相关系数，则该序列的协方差矩阵有如下关系：,[],,0,1,,1,1ijxijijNR按K—L变换的思路，现需要求的特征值及特征向量，以形成变换的正交矩阵。但对Markov-1过程，协方差阵的特征向量可以解析的给出，因此正交变换的矩阵也可解析的得到：xRxRA是的特征值xR,jjj是方程的根11tan()0N有：由：必有：0,1,1,jjN再由：0N0,1,1,jjN0N将正是DCT变换矩阵！代入经化简结论：当时，对Markov-1过程做K—L变换的正交矩阵正是DCT变换的变换矩阵，也即：此时的DCT近似K—L变换。因为DCT有快速算法，另外，Markov-1过程可作为一大类信号（语音、图象）的数学模型，因此DCT在图象、语音压缩中起到了关键性的作用，成为国际上许多标准（如JPEG,MPEG）的重要工具。1下图是时K—L变换矩阵、DCT变换矩阵、DST变换矩阵的行向量。8,0.95N(),1,2,,xnnN给定：定义：DST反变换：离散正弦变换（DST）变换矩阵DST也是正交变换可以证明，DST在一定条件下也是对K—L变换的近似。如何评判近似的好坏DFT:DCT:DST:K—L:,,,,nknknknkWCSA正交矩阵的行（或列）向量具有上述形式yAxxRyR正弦类变换：变换前相关矩阵非对角线上元素的和；变换后相关矩阵非对角线上元素的和；越小越好去除相关的“效率”，越大越好80.91NDCT:DFT:DST:98.05%89.48%84.97%E：反映了变换后能量集中的程度。若越小、越大，则能量越集中。ME8.4Hartley变换FT:HT:定义偶部奇部()()()()Re[()]Im[()]FHFFXjEjOXjXjXjFT和HT的关系DHT离散Hartley变换矩阵也是正交阵，且是周期的，周期为。DHT可用来实现DFT的几乎所有功能，而这些实现都是在实数域进行的。N有关DHT的性质及用于卷积运算的讨论见书8.4节，此处不再详细讨论。8.5离散W变换无穷多种DFT的定义有一种，DWT有四种。四种DWT都是正交变换,它们分别对应两种形式的抽样，即的整数抽样和的半整数抽样。若用它作谐波分析，可以得到分数倍谐波（基波的奇数倍/2)。(,0)(,1/2)1W即是Hartley变换矩阵。四种DWT矩阵有着密切的关系，由它们可引导出四种类型的DCT和四种类型的DST。22/cos[(1/2)/],0,1,,1NkCNgnkNnkNDCT-Ⅱ已定义过四种形式的DCTDCT-Ⅰ112/cos(/),0,1,,NnkCNggnkNnkNDCT-Ⅲ32/cos[(1/2)/],0,1,,1NnCNgnkNnkNDCT-Ⅳ42/cos[(1/2)(1/2)/],0,1,,1NCNnkNnkN112342/sin(/),1,2,,12/sin[(1/2)/],1,2,,2/sin[(1/2)/],1,2,,2/sin[(1/2)(1/2)/],0,1,,1NNkNnNSNnkNnkNSNgnkNnkNSNgnkNnkNSNnkNnkNDST-ⅠDST-ⅡDST-ⅢDST-Ⅳ已定义过四种形式的DST四种形式的DCT、DST是由不同的学者在不同的文献上提出的，它们在不同的条件下对K—L变换有着不同的近似。如：1:DCT-Ⅱ对K—L变换的近似最好；0:DST-Ⅰ对K—L变换的近似最好；0.45~0.85:DCT-Ⅰ优于DCT-Ⅱ；1:DCT-Ⅱ对K—L变换的近似极坏；:未知时使用DCT-Ⅰ要比DCT-Ⅱ安全。实际上，用的最多的还是DCT-Ⅱ!8.6DCT、DST、DWT快速算法DCT、DST、DWT基本上都可以通过FFT来实现，当然也可发展其他适合它们特点的算法。对DCT-Ⅱ:补N个零其他有关内容见教材8.6图象压缩及其国际标准--DCT应用讲座(1)一、图像的基本概念图像的灰度彩色图像：(,){(,),(,),