第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 與本章內(nèi)容有關的與本章內(nèi)容有關的MATLAB文件文件 目錄目錄希爾伯特空間中的正交變換希爾伯特空間中的正交變換賦范線性空間賦范線性空間 內(nèi)積空間內(nèi)積空間 完備

2、的內(nèi)積空間（希爾伯特空間）完備的內(nèi)積空間（希爾伯特空間）信號的分解信號的分解 設空間 是由 N 維空間一組向量12,NXspan 12,N XNnnnx1 對任一 ，都可作如下分解：xX所張成，即Xx信號的離散表示,或信號的分解12,N是分解系數(shù)或信號的變換 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如果：信號的正交變換信號的正交變換給定數(shù)據(jù)向量： (0), (1), (1)Txxx Nx及算子N NA 作變換yAx矩陣 的行（列）向量即是前面的向量Ai若：, Ax Axx xy, y則上述變換即為正交變換，或保范（數(shù)）變換。A實際上是正交矩陣，1TAA以上正交變換是從線性代數(shù)的角度來定義。正交變換的性質(zhì)：性質(zhì)1：正交變換的基向量即是其對偶基向量。由性質(zhì)1可知正交變換具有如下的優(yōu)點：NNA 2. 正交變換在計算上最為簡單。如果是離 散信號，且 N 是有限值，那么變換只是簡單的矩陣與向量運算：yAx3. 反變換：1TxA yA y不需要求逆，特別有利于硬件實

4、現(xiàn)1. 若正變換存在，那么反變換一定存在，且變換是唯一的； 非正交基的情況下，“基向量”稱為“標架（Frame)”, 這時，展開系數(shù)不是準確投影。2*| |( ) ( ),nxx n x nx x22|nn此性質(zhì)實際上是 Parsevals 定理，即信號變換前后能量保持不變。注意，只有正交變換才有此性質(zhì)。性質(zhì)4：信號正交分解具有最小平方近似性質(zhì)。 1,Nnnnnnx 1Lnnnx ,1,nnnL2( , )x x221( , )Nnn Lx x 性質(zhì)5：正交變換的系數(shù)具有去除相關和集 中能量的性質(zhì)。0111TNACAACAAC取取決決于于基基函函數(shù)數(shù)?，F(xiàn)現(xiàn)能能量量集集中中，分分量量的的相相關關

5、性性、能能否否出出）投投影影的的結(jié)結(jié)果果能能否否減減少少（或或者者新新基基底底上上的的向向量量。底底上上的的投投影影，看看成成向向量量在在標標準準正正交交基基正正交交變變換換的的結(jié)結(jié)果果，可可以以為為特特征征向向量量。為為特特征征值值，存存在在正正交交變變換換維維離離散散信信號號對對）（具具有有下下列列性性質(zhì)質(zhì)：正正交交變變換換4)3()(,)2(;110111iiNTTTTMNTTAAAxxAAxxAxAxAxNIAAAAAAA 佳佳正正交交變變換換變變換換：統(tǒng)統(tǒng)計計意意義義上上的的最最變變換換（及及離離散散變變換換離離散散，離離散散正正弦弦變變換換，離離散散余余弦弦變變換換傅傅里里葉葉變變

6、換換正正弦弦類類正正交交變變換換斜斜變變換換及及變變換換，變變換換非非正正弦弦類類正正交交變變換換：變變換換正正弦弦類類正正交交變變換換非非正正弦弦類類正正交交變變換換正正交交變變換換的的種種類類LKDWTWDHTHartleyDSTDCTDFTSLTHRTHaarWHTHadamardWalshLK )()(),()()()()(:正交基的選擇原則：正交基的選擇原則：正交變換的實例：正交變換的實例： FS,FT, DTFT, DFS, DFT DCT,DST, DHT Walsh-Hadamard, Haar 變換 SLT(斜變換）正弦類正交變換非正弦類正交變換佳佳正正交交變變換換變變換換：

7、統(tǒng)統(tǒng)計計意意義義上上的的最最LK yAxyAxPCAAAAxxAAxxAxAxNxNTTiiNTTTTMN)(2)(,1101 。降降維維和和降降噪噪中中的的應應用用信信號號損損失失的的能能量量最最小小后后，的的結(jié)結(jié)果果中中較較小小分分量量丟丟掉掉：如如何何變變換換，使使變變換換后后背背景景問問題題為為特特征征向向量量。為為特特征征值值，個個信信號號互互不不相相關關或或者者變變換換后后相相關關矩矩陣陣對對角角化化使使變變換換結(jié)結(jié)果果的的如如何何正正交交變變換換維維離離散散信信號號：對對背背景景問問題題特征值分解特征值分解用于信號降噪用于信號降噪PCANmimmmmNimNixxxxxxxxxx

8、xxxxx1212143213211,3 ,2,1 ,1, 2, 23 , 22, 21 , 21, 1, 13 , 12, 11 , 1mNmimmmmmNimNixxxxxxxxxxxxxxxNjxjNjmxjlklkj, 11,min,min11,Njxj, 1 有趣發(fā)現(xiàn)有趣發(fā)現(xiàn):相位不變。相位不變。階次與截止頻率？階次與截止頻率？ KL 變換 (Karhunen-Loeve) (0), (1), (1)Txxx Nx數(shù)據(jù)向量：0,00,10,11,01,11,11,01,11,1()()TxxxNNNNNNEcccccccccCxx協(xié)方差陣：( , )( , )xxC i jCj i體

9、現(xiàn)了信號各元素之間的相互關系KL 變換的思路：尋找正交矩陣 ，做變換 ， 使 的協(xié)方差陣 為對角陣。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構(gòu)成正交陣A5. 由 實現(xiàn)對 的 KL 變換：yAxx011TyxNCAC AAxy xy KL 變換的應用數(shù)據(jù)壓縮：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 不是時域序列，而是 的變換系數(shù)（即 ） ，如 DFT 的 。正交變換后，信號的能量一般集中在少數(shù)的變換系數(shù)上，所以可以舍去絕大部分系數(shù)，這并不明顯損失信號的能量。由剩下的少量系數(shù)，如 ，通過反變換 可以很好的恢復出原信號。從而達到數(shù)據(jù)壓縮的目的。x( )X k1xA y yiyKL 變換： 去相關性最徹底，在此意義上是最佳正交變換； 方向依賴待變換的信號。信號發(fā)生變化時，要重新求變換矩陣。特征值和特征向量的計算是

11、相當費時的，因此，KL變換沒有快速算法。這就限制了KL變換的實際應用。011,NxAA AACx變換的正交矩陣 8.3 離散余弦變換（DCT）( ),0,1,1x nnN給定：定義：10)(1)0(NncnxNX102(21)( )( )cos21,2,1NcnnkXkx nNNkNDCT的 定義構(gòu)成一矩陣，是變換的核函數(shù)變換域,2(21)cos2,0,1,1k nknkCgNNn kN012;10kggfor kDCT的核函數(shù)，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中，正變換矩陣和反變換矩陣是一樣的，都是實矩陣。特別有利于實時實現(xiàn)及硬件實現(xiàn)。 一階馬爾可夫過程（Markov-1):語音和圖象處理中常用的數(shù)學模型。一個隨機信號 ，若其pdf滿足如下關系： 則稱 為一階馬爾可夫過程。該式的含意是：已知過程在現(xiàn)在時刻的狀態(tài)，那么，下一個時刻的狀態(tài)只和現(xiàn)在的狀態(tài)有關，而和過去的狀態(tài)無關。111100()( ),(),()nnnnnnp

14、 X txX txX txX tx11()( ),( )( )nnnnnp X txX txX tX n)(tX212231231111NNNxNNN R 令 是Markov-1 隨機序列相鄰兩元素之間的相關系數(shù)，則該序列的協(xié)方差矩陣有如下關系：,0,1,1,1ijx i ji jNR按 KL 變換的思路，現(xiàn)需要求 的特征值及特征向量，以形成變換的正交矩陣 。但對Markov-1 過程，協(xié)方差陣 的特征向量可以解析的給出，因此正交變換的矩陣也可解析的得到： 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經(jīng)化簡結(jié)論：當 時，對Markov-1過程做KL變換的正交矩陣正是DCT變換的變換矩陣，也即：此時的DCT近似KL變換。因為DCT有快速算法，另外， Markov-1過程可作為一大類信號（語音、圖象）

16、的數(shù)學模型，因此 DCT在圖象、語音壓縮中起到了關鍵性的作用，成為國際上許多標準（如 JPEG, MPEG）的重要工具。1( ),1,2,x nnN給定：12( )( )sin()111,2,NsnnkXkx nNNkN定義：DST12( )( )sin()111,2,Nsknkx nXkNNnN反變換：離散正弦變換（DST）離散正弦變換離散正弦變換(DST) 為正交矩陣為正交矩陣核函數(shù)核函數(shù)離散正弦變換離散正弦變換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正交矩陣的行（或列）向量具有上述形式y(tǒng)AxxRyR正弦類變換：1,12,1( , )( , )Nxi jijNyi jiji ji jRR變換前相關矩陣非對角線上元素的和；變換后相關矩陣非對角線上元素的和；越小越好12/1去除相關的“效率”，越