醫(yī)學(xué)圖像處理 第三章圖像變換

1、第3章 正交變換在圖像處理中的應(yīng)用第一節(jié) 傅氏變換在圖像處理中的應(yīng)用 3.1.1 一維連續(xù)傅氏變換1、變換對dxxfuFuxj2e)()(duuFxfuxj2e)()()u(F)x(f F(u)一般是復(fù)數(shù)，表示形式為： F(u) = R(u) + j I(u) 或)u(je)u(F)u(F這里 |F(u)| = 稱為f(x)的傅立葉譜22)()(uIuR 相角 能量譜)()(tanarc)(uRuIu 2| )(|)(uFuE 2、快速算法因為所以：當(dāng)f(x)為偶函數(shù)，則第二項為零，當(dāng)f(x)為奇函數(shù)，則第一項為零。 ux2jsin)ux2(cos)x(fdxe )x(f)u(Fuxj2 3.

2、1.2 二維連續(xù)傅氏變換變換對：dxdyyxfvuF)vyux(j2e ),(),(dudve ) v , u ( F) y, x ( f)vyux(j2)v, u(F)y, x(f)v, u(I)v, u(R)v, u(F22),(),(tanarc),(vuRvuIvu)v, u(I)v, u(R)v, u(E22 3.1.3 一維離散傅氏變換（DFT）1、變換對1N0 xNuxj2e )x(f)u(F設(shè)f(0), f(1), f(2), , f(N-1)為一維信號f(x)的N個抽樣， 其離散傅立葉變換對為 1NouNuxj2e )u(FN1)x(f)u(F)x(fx=0，1，2，N-1u

3、=0，1，2，N-1 以N=4為例，序列f(0),f(1),f(2),f(3)的傅氏變換F(u)。利用公式 ，取N=4，則有：，展開有：1N0Nuxj2e )x(f)u(Fx30 x4ux2je )x(f)u(F 29jj223j0j3j2j023jj2j03210e3fe2fe1fe0f)3(Fe3fe2fe1fe0f)2(Fe3fe2fe ) 1 (fe )0(f) 1 (Fe3fe2fe ) 1 (fe )0(f)0(F寫成矩陣形式：設(shè)： 3f2f1f0feeeeeeeeeeeeeeeeF(3)F(2)F(1)F(0)29j -j2-23j -0j3-j2-j -023j -j -2j

4、-00000uxN2juxNeW 則： 記作：9N6N3N0N6N4N2N0N3N2N1N0N0N0N0N0N29j -j2-23j -0j3-j2-j -023j -j -2j -00000WWWWWWWWWWWWWWWWeeeeeeeeeeeeeeeefWFN 2、 的性質(zhì)（1）對稱性（2）周期性（3）可分性uxNW*uxNx)uN(N)xN(uNWWWu)x(NN)xN(uNuxNWWW2ux2NuxNWW1W2NNux2N2uxNWWuN2NuNWW 3.1.4 二維離散傅氏變換1、變換對x,u=0，1，2，M-1y,v=0，1，2，N-11 -M0 x1 -N0yNvyMuxj2-e

5、 )y, x(f)v, u(F1N0u1M0v)NvyMux(j2e )v, u(FMN1)y, x(f)v, u(F)y, x(f 2、二維離散傅氏變換的性質(zhì)（1）周期性和共軛對稱性周期性：共軛對稱性：)nNv,mMu(F)v, u(F)nNy,mMx( f)y, x( f)v, u(F)v, u(F)vnN, umM(F)v, u(F* （2）空域移位 （3）頻域移位 （4）卷積設(shè) 則 vyNuxM0000WW)v, u(F)yy,xx(f)vv,uu(FWW)y, x( f00-yvN-xuM00) v, u(G) y, x( g),v, u( F) y, x( f)v, u(G*)v,

6、 u(F)y, x(g)y, x(f)v, u(G)v, u(F)y, x(g*)y, x(f （5）能量守恒設(shè)則（6）二維核可分離性)v, u(F)y, x( f1N0u1N0v221N0 x1N0y2v)F(u,N1)y, x( fNvy2jNux2jNvyuxj2eee 3、二維傅氏變換的矩陣表示 令 則：1 -M0 x1 -N0yNvyMuxj2-e )y, x(f)v, u(FN2jNM2jMeW,eW1 -M0 x1 -N0yvyNuxM1 -M0 x1 -N0yvyNuxMW)y, x(fWWW)y, x(f)v, u(F 用矩陣表示為：) 1N, 1M(F.) 1 , 1M(F

7、)0 , 1M(F.) 1N, 1 (F.) 1 , 1 (F)0 , 1 (F) 1N, 0(F.) 1 , 0(F)0 , 0(F2) 1N(NW.) 1N(NW0NW.) 1N(NW.1NW0NW0NW.0NW0NW) 1N, 1M(f.) 1 , 1M(f)0 , 1M(f.) 1N, 1 (f.) 1 , 1 (f)0 , 1 (f) 1N, 0(f.) 1 , 0(f)0 , 0(f2) 1M(MW.) 1M(MW0MW.1MW.1MW0MW0MW.0MW0MW是 的逆矩陣上式用矩陣符號表示為：NMfWWF 11FfNMWW1MW1NWMWNW同理付立葉反變換為：、例：求數(shù)字圖像

8、的2DDFT2000120011201112解：9464340464442404342414040404040494643404644424043424140404040404WWWWWWWWWWWWWWWW*2000120011201112*WWWWWWWWWWWWWWWWFj1j11111j1-j111112000120011201112j1j11111j1-j11111F3.1.5 快速傅氏變換（FFT）一、基于時間抽取(DIT)的FFT一維離散傅氏變換 全部計算需要N2次乘法和N(N-1)次加法，當(dāng)N很大時,運算量將是驚人的,如N=1024,則要完成1048576 次(一百多萬次)乘法

9、運算.這樣,難以做到實時處理.1N0 xNux2je )x(f)u(Fx=0，1，2，N-1u=0，1，2，N-1 快速算法要求 N為2的整數(shù)次冪，即 N=2m（m為整數(shù)）。 一維離散傅立葉變換的表達式 x=0，1，2N-1u=0，1，2N-1設(shè) 則：1N0 xNux2je )x(f)u(FN2jNeW1N0 xuxNW)x(f)u(F 因為N為偶數(shù)，可將其分為兩部分之和，即N/2個偶數(shù)項和N/2個奇數(shù)項之和，寫為： 因為 所以有 12N0 x)12x(uN12N0 x)2x(uNW) 12x(fW)2x(f)u(Fux2N2uxNWW1N10 xux2NuN12N0 xux2NW) 12x(

10、fWW)2x(f)u(F 我們知道F(u)（u=0,1,2N-1）共有N個值，如果我們把前N/2個離散值和后N/2個離散值分成兩個式子來表示，則有u=0，1，2， （1） u=0，1，2， （2）12N0 xux2NuN12N0 xux2NW) 12x(fWW)2x(f)u(F12N12N0 x)x2N(u2N)2N(uN12N0 x)x2N(u2NW) 12x(fWW)2x(f)2Nu(F12N 因為： 則上述(2)式可簡化為：u=0，1，2，（3）uN2NNuN)2Nu(NWWWWux2N2Nx2Nux2N)x2N(u2NWWWW12N0 xux2NuN12N0 xux2NW) 12x(

11、fWW)2x( f)u(F12N 令： 則（1）式和（3）式可寫為: （4）u=0,1,12N0 xux2NW)2x(f)u(F偶12N0 xux2NW) 12x(f)u(F奇12N)u(FW)u(F)2Nu(F)u(FW)u(F)u(FuNuN奇偶奇偶 計算一維離散傅立葉變換，可以分兩步：第一步，先按定義求出F偶(u)和F奇(u),然后按(4)式計算傅立葉變換F(u)的前N/2個點和后N/2個點。4N2N2212N2N(1)N/2點的DFT運算量:復(fù)乘次數(shù):復(fù)加次數(shù):(2)兩個N/2點的DFT運算量:復(fù)乘次數(shù):復(fù)加次數(shù): (3)N/2個蝶形運算的運算量:復(fù)乘次數(shù):復(fù)加次數(shù): : 計算工作量分

12、析計算工作量分析復(fù)乘:復(fù)加:總共運算量:按奇、偶分組后的計算量：但是,N N點DFTDFT的復(fù)乘為N N2 2 ; ;復(fù)加N(N-1);N(N-1);與分解后相比可知,計算工作點差不多減少 一半。2N2) 12N(N2NN2N22N2N2N222NN) 12N(N2 例如 N=8N=8 時的DFT,DFT,可以分解為兩個 N/2=4N/2=4點的DFTDFT。具體方法如下: :（1 1）n n為偶數(shù)，即為偶數(shù)，即f(0),f(2),f(4),f(6);f(0),f(2),f(4),f(6);進行進行N/2=4N/2=4點的點的DFTDFT，得，得F F偶偶(u):(u):u=0,1,2,312

13、N0 xux2NW)2x(f)u(F偶 （2）當(dāng)n為奇數(shù)時，即f(1),f(3),f(5),f(7)；u=0，1，2，312N0 xux2NW) 12x(f)u(F奇進行N/2=4點的DFT，得F奇(u):u=0，1，2，3)u(FW)u(F)4u(F)u(FW)u(F)u(Fu8u8奇偶奇偶(3)(3)對F偶(u) )和F奇(u) 進行蝶形運算： f1 1(0)=(0)=f(0) (0) f1(1)=(1)=f(2) (2) N/2N/2點點 f1(2)=(2)=f(4) DFT (4) DFT f1(3)=(3)=f(6) (6) f2(0)=(0)=f(1) (1) f2(1)=(1)=

14、f(3) (3) N/2N/2點點 f2(2)=(2)=f(5) (5) DFT DFT f2(3)=(3)=f(7)(7) F F偶偶(0)(0)F F偶偶(1)(1)F F偶偶(2)(2)F F偶偶(3)(3)F F奇奇(0)(0)F F奇奇(1)(1)F F奇奇(2)(2)F F奇奇(3)(3)WN2WN1WN0WN3-1-1-1-1F(0)F(0)F(1)F(1)F(2)F(2)F(3)F(3)F(4)F(4)F(5)F(5)F(6)F(6)F(7)F(7) 因為N=2n，N是偶數(shù)，當(dāng) 時，N/2還是偶數(shù)，因此F偶(u) )和F奇(u) （u=0，1，2， ）的計算仍可以按同樣方法分解

15、為偶、奇兩個集，得出如下結(jié)果：u=0，1，2n 12N)u(FW)u(F)4Nu(F)u(FW)u(F)u(Fu2Nu2N偶奇偶偶偶偶奇偶偶偶)u(FW)u(F)4Nu(F)u(FW)u(F)u(Fu2Nu2N奇奇奇偶奇奇奇奇偶奇14N 式中： u=0,1,，14N0 xux4NW)4x(f)u(F偶偶14N0 xux4NW)24x(f)u(F偶奇14N0 xux4NW) 14x(f)u(F奇偶14N0 xux4NW)34x(f)u(F奇奇14N 如果按這種方法一直進行下去，直到求出兩點離散函數(shù)的傅立葉變換為止。這就是快速傅立葉變換的原理。 因此8點DFT的FFT的運算流圖如下： f(0) f

16、(4) f(2) f(6) f(1) f(5) f(3) f(7)WN0WN0WN0W0N-1-1-1-1F偶偶 (0)F 偶偶(1)F 偶奇(0)F 偶奇(1)F 奇偶(0)F奇偶(1)F奇奇 (0)F奇奇 (1)WN0WN2WN0WN2-1-1-1-1F偶 (0)F 奇(0)F 奇(1)F 奇(2)F 奇(3)WWWWN0N1N2N3-1-1-1-1F(0)F(1)F(2)F(3)F(4)F(5)F(6)F(7)F偶 (1)F偶 (2)F偶 (3)二二. .運算量運算量 由上述分析可知,N=8N=8需三級蝶形運算 N=2N=23 3=8,=8,由此可知,N=2N=2L L 共需L L級蝶形

17、運算,而且每級都由N/2N/2個蝶形運算 組成,每個蝶形運算有一次復(fù)乘,兩次復(fù)加。 因此,N N點的FFTFFT的運算量為復(fù)乘:（N/2N/2）L=L=（N/N/2） loglog2 2 N N復(fù)加: N L=N logN L=N log2 2 N N 由于計算機的乘法運算比加法運算所需的時間多得多，故以乘法作為比較基準。2 2 倒位序規(guī)律倒位序規(guī)律輸出F F(u)(u)按正常順序排列在存儲單元,而輸入是按順序:f(0),f(4),f(2),f(6);f(1),f(5),f(3),f(7) 這種順序稱為比特倒序。 二進制為(n2 n1 n0 )2 的數(shù), , 比特倒序為(n0 n1 n2 )2

18、 。例如，N=8時如下表： 0 00 0 0 0 0 00 0 0 0 0 0 0 0 1 01 0 0 0 1 11 1 0 0 0 4 0 4 2 02 0 1 1 0 00 0 1 1 0 2 0 2 3 03 0 1 1 1 11 1 1 1 0 6 0 6 4 14 1 0 0 0 00 0 0 0 1 1 1 1 5 15 1 0 0 1 11 1 0 0 1 5 1 5 6 16 1 1 1 0 00 0 1 1 1 3 1 3 7 17 1 1 1 1 11 1 1 1 1 7 1 7 自然順序n n 二進制n n n n n n 倒位序二進制n n n n n n 倒位順序n

19、 n2 1 0 0 1 2按頻率抽取(DIF)的FFT算法 要求：N=2n10 xux)x(f)u(FNNW10 x)x(u10 xux12/xux10 xux2222)2x(f)x(f)x(f)x(fNNNNNNNNNNWNWWW 由于 故 因此 F(u)可表為 ux10 xu22)2x( f)x( fNNWWNNN, 12jNeWNuu) 1(2NNWux10 xu2)2x( f) 1()x( f)u(FNWNN1, 1 , 0uN N點DFT按u的奇偶分組可分為兩個N/2的DFT 當(dāng)u u為偶數(shù),即 u=2ru=2r時,(-1)u =1； 當(dāng)u u為奇數(shù),即 u=2r+1 =2r+1 時

20、 (-1)u =-1 。 這時F(u)可分為兩部分： rx10 xx210 x222)2x(f)x(f)2x(f)x(fNNNWNWNrN)2r(F)u(F1, 1 , 02Nru u為偶數(shù)時： 可見,上面兩式均為N/2N/2的DFTDFT。x10 xxx)12(10 x222)2x(f)x(f)2x(f)x(f) 12(F)u(FrNrNNNNWWNWNru u為奇數(shù)時：1, 1 , 02Nr-1-1)2x(f)x(fN1, 1 ,0 x2Nx)2x(f)x(fNWN蝶形運算進行如下碟形運算：和)2x(f)x(fNxNW)2x(fN)x(f-1-1-1-1-1-1-1-1W WW WW WW

21、 WN NN NN NN N0 01 12 23 3N=8N=8時時, ,按按u u的奇偶分解過程的奇偶分解過程 先蝶形運算，后先蝶形運算，后DFT:DFT:)0(f) 1 (f)5(f)4(f) 3(f)2(f)7(f)6(f)0(F)2(F)6(F) 1 (F) 3(F)5(F)7(F)4(FDFTN點2DFTN點2仿照DIFDIF的方法 再將N/2N/2點DFTDFT按u的奇偶分解為兩個N/4N/4點的DFTDFT,如此進行下去,直至分解為2 2點DFTDFT。 (0) F(0)(0) F(0)(1) F(4)(1) F(4)(2) F(2)(2) F(2)(3) F(6)(3) F(6

22、)(4) F(1)(4) F(1)(5) F(5)(5) F(5)(6) F(3)(6) F(3)(7) F(7)(7) F(7)-1-1-1-1-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 01 12 23 3-1-1-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 02 20 02 2-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 00 00 00 0ffffffff例如 N=8N=8時DIFDIF的FFTFFT流圖如下： 1. 1.相同點 (1)(1)進行原位運算； (2)(2)運算量相同, ,均為（N/

23、2) Log2N次復(fù)乘, ,N Log2N次復(fù)加。 2.2.不同點 (1)DIT(1)DIT輸入為倒位序,輸出為自然順序； DIFDIF正好與此相反。但DITDIT也有輸入為自然順序,輸出為倒位序的情況。DIFDIF法與法與DITDIT法的異同法的異同原位運算：當(dāng)數(shù)據(jù)輸入到存儲器以后，每一組運算的結(jié)果，仍然存放在這同一組存儲器中直到最后輸出。rNmmmWjkj)(F)(F)(F11rNmmmWjkk)(F)(F)(F11)(F1km)(F1jmrNW1(2)(2)蝶形運算不同a.a.(DIT)(DIT)用矩陣表示)(F km)(FjmrNWrNW)(F1km)(F1jm=11rNmmmWjkj

24、)(F)(F)(F11)(F)(F)(F11jkkmmm)(F1km)(F1jmrNW1b.b.(DFT)(DFT)用矩陣表示)(F km)(FjmrNWrNW)(F1km)(F1jm=11(3)(3)兩種蝶形運算的關(guān)系 互為轉(zhuǎn)置（矩陣）； 將流圖的所有支路方向都反向, ,交換輸入和輸出，即可得到另一種蝶形。 a.a. DIT DITb.b.DFTDFTrNWrNW1111rNWrNWIFFTIFFT算法算法一一.稍微變動稍微變動FFT程序和參數(shù)可實現(xiàn)程序和參數(shù)可實現(xiàn)IFFT uxN1N0u1N0 xuxNW)u(FN1)u(FIDFT)x(fW)x(f)x(fDFT)u(F 比較兩式可知,

25、,只要DFTDFT的每個系數(shù) 換成 , ,最后再乘以常數(shù)1/N1/N就可以得到IDFTIDFT的快速算法-IFFT。 另外, ,可以將常數(shù)1/N1/N分配到每級運算中, , , ,也就是每級蝶形運算均乘以1/1/2 2。 nkNWnkNWLLN)21(211二二.不改不改(FFT)(FFT)的的程序程序直接實現(xiàn)直接實現(xiàn)IFFTIFFT uxN1N0u1N0u*uxNW)u(FN1W)u(FN1)x(f)u(FDFTN1W)u(FN1uxN1N0u)x(f因此，BABAWWnkNnkN , 這就是說, ,先將F(u)F(u)取共軛, ,即將F(u)F(u)的虛部乘-1-1，直接利用FFTFFT程

26、序計算DFT；然后再取一次共軛；最后再乘1/N,1/N,即得 (x)(x)。所以FFT,IFFTFFT,IFFT可用一個子程序。f線性卷積的線性卷積的FFTFFT算法算法一一. .線性卷積的長度線性卷積的長度 設(shè)一離散線性移不變系統(tǒng)的沖激響 應(yīng)為 , ,其輸入信號為 . .其輸出 為 . .并且 的長度為L點, , 的 長度為M點, ,則： )(nx)(nx)(nh)(nh)(ny)(nx)(nh10)()()()()(Lmmnhmxnhnxny)(ny以實例說明：0 1 0 1 2 2 3 31 12 23 3)(mx)(mh01211.。1。0 1 0 1 1 12 23 3)(mx2 3

27、)(m mh h )1(m mh h 300)()() 0(mmhmxy301)1 ()() 1 (mmhmxy。0 0 1 1 2 2 3 3)2(m mh h )3(m mh h 。0 1 0 1 1 12 23 3)(mx2 3。303)2()() 2(mmhmxy306)3()() 3(mmhmxy0 0 1 1 2 2 3 3 4 40 0 1 1 2 2 3 3 4 4 5 5)4(m mh h )5(m mh h 0 1 0 1 1 12 23 3)(mx2 3。305)4()() 4(mmhmxy303)5 ()() 5 (mmhmxy0 0 1 1 2 2 3 3 4 4 5

28、 51 13 33 35 56 66 6)(n ny y1)(MLny的長度為可見，。二二.用用FFTFFT算算 的步驟：的步驟： )(n ny y;1)(),(. 1點補零點，至少為將LMNnhnx；求)()(.2nhFFTkH；求)()(.3nxFFTkX；求)()()(.4kHkXkY。求)()(.5kYIFFTnyFFTFFTIFFTxx(n)h(n)y(n)X(k)H(k)Y(k)流程圖3.1.6 總結(jié) 1、一維連續(xù)傅氏變換 2、二維連續(xù)傅氏變換F(u)f(x) due)u(F)x(fdxe)x(f)u(Fuxj2uxj2)v,u(F)y,x(f dudve)v,u(F)yx,(fd

29、xdye)y,x(f)v,u(F)vyux(j2)vyux(j2 3、一維離散傅氏變換fWF 1-N10u, x)u(F)x(f e )u(FN1)x(fe )x(f)u(FN1N0uNux2j1N0 xNux2j， 4、二維離散傅氏變換1N1 -MNM1M0u1N0v)NvyMux(j21M0 x1N0y)NvyMux(j2FWWf fWWF v)F(u,y)f(x, 1-N10y v 1-M1 , 0 xu, e )v, u(FMN1)yx,(fe )y, x(f)v, u(F， 圖像頻域變換的一般表達式： 反向變換核正向變換核式中：:v)u,y,h(x,:v)u,y,g(x,1N,2,1

30、 ,0v,y1-M,2,1 ,0u,x)v,u,y,x(h)v,u(F)y,x(fv)u,y,g(x,)y,x(f)v,u(F1M0u1N0v1M0 x1N0y 如果 則稱正、反變換核是可分離的。 如果g1和g2，h1和h2在函數(shù)形式上是一樣的，則稱該變換核是對稱的。)v, y(h)u, x(h)v, u, y, x(h)v, y(g)u, x(g)v, u, y, x(g2121例如，二維傅氏變換變換核：它們都是可分離的和對稱的。Nuy2jMux2j)NvyMux(j2Nuy2jMux2j)NvyMux(j2eee)v, u, y, x(heee)v, u, y, x(g 圖像變換的矩陣表示

31、： 其中，F(xiàn)和f是二維 的矩陣，P是 矩陣， Q是 矩陣。 11FQPfPfQFNNMMNM3.1.7 DFT應(yīng)用中的問題 1、頻譜的圖像顯示 譜圖像就是把 作為亮度顯示在屏幕上。但在傅立葉變換中F(u,v)隨u,v的衰減太快，其高頻只看到一兩個峰，其余皆不清楚。在實際應(yīng)用中，設(shè)顯示信號為D(u,v)，有：)vu,(F)v, u(F1 (log)v, u(D 實用的公式，還要用K系統(tǒng)調(diào)整顯示圖像：|F(u,v)|u|D(u,v)|u)v, u(FK1 (log)v, u(D 2、頻譜的頻率移中將f(x, y)乘以因子(1)x+y，再進行離散傅立葉變換，即可將圖像的頻譜原點（0，0）移動到圖像中

32、心（M2, N2）處。(a) 原圖像；（b）無平移的傅立葉頻譜；（c）平移后的傅立葉頻譜(a) (b) (c) 3、旋轉(zhuǎn)不變性用極坐標表示傅立葉變換對：則旋轉(zhuǎn)不變性為： 如果時域中離散函數(shù)旋轉(zhuǎn)0角度，則在變換域中該離散傅立葉變換函數(shù)也將旋轉(zhuǎn)同樣的角度。),R(F),(f),R(F),(f00(a)(b)(d)(c)（a） 原始圖像； （b） 原始圖像的傅立葉頻譜； （c） 旋轉(zhuǎn)45后的圖像； （d） 圖像旋轉(zhuǎn)后的傅立葉頻譜 第二節(jié) 離散余弦變換 3.2.1 一維離散余弦變換 設(shè)f(0),f(1),f(N-1)為離散的信號序列，則余弦正變換為： 其中：10u) 12x(2Ncos)(2)()(N

33、xxfNuCuF式中，u, x=0, 1, 2, , N1。1N,2, 1u1021)(uuC 將變換式展開整理后， 可以寫成矩陣的形式， 即F=Cf其中2N) 12N)(1N(cos2N1)-3(Ncos2N) 1N(cos2N) 12N(cos2N3cos2Ncos212121N2c 反變換：可見一維DCT的逆變換核與正變換核是相同的記作：10u) 12x(2Ncos)()(2)(NuuFuCNxf式中， x, u=0, 1, 2, , N1FCfT 3.2.2 二維離散余弦變換NvyMuxvCuCyxfMNvuFMxNy2) 12 (cos2) 12 (cos)()(),(2),(101

34、0二維DCT定義如下：設(shè)f(x, y)為MN的數(shù)字圖像矩陣，則 式中： x, u=0, 1, 2, , M1； y, v=0, 1, 2, , N1。 類似一維矩陣形式的DCT，可以寫出二維DCT的矩陣形式如下：TNMfCCF 式中：x, u=0, 1, 2, , M1； y, v=0, 1, 2, , N1。 記作矩陣形式:NvyMuxvuFvCuCMNyxfMuNv2) 12(cos2) 12(cos),()()(2),(1010二維DCT逆變換定義如下：NTMFCCf 式中：1M,2, 1u1021)(Cuu1N,2, 1v10v21)v(C 快速離散余弦變換快速離散余弦變換 首先，將f

35、(x)延拓為 0)()(xfxfex=0, 1, 2, , N-1x=N， N+1, , 2N-1 按照一維DCT的定義，fe(x)的DCT為10)(1)0(NxexfNF NxujNxeNujNuxjNxeNxeNxexfeNexfNNuxxfNNuxxfNuF2212022)12(12012010)(Re2)(Re22) 12(cos)(22) 12(cos)(2)(式中，Re表示取復(fù)數(shù)的實部。 由于 為fe(x)的2N點DFT。因此，在 作DCT時，可把長度為N的f(x)的長度延拓為2N點的序列fe(x)，然后對fe(x)作DFT，最后取DFT的實部便可得到DCT的結(jié)果。12022)(N

36、xNxujeexf 同理對于離散余弦逆變換IDCT，可首先將F(u)延拓為0)()(uFuFeu=0, 1, 2, , N-1u=N, N+1, , 2N-1 1202221212) 12(121)(Re2)0(21)(Re2)0(12) 12(cos)(2)0(1)(NuNxujNujeeNuNuxjeeNueeeeuFNFNNeuFNFNNuxuFNFNxf即：DCT可由FFT來實現(xiàn)第三節(jié) 離散沃爾什變換3.3.1一維離散沃爾什變換（DWT） 要求樣點 ，則 f(x)（x=0,1,2,N-1）的離散沃爾什變換對為： 式中 u、x = 0、1、2 N-1 nN210)()(101010)()

37、(1i1i)1()()()1()(1)(niubxbNuNxniubxbininuWxfxfNuW這里 是x的二進制表示的第i位值。10)()(10)()(11)1(),()1(1),(niubxbniubxbiniiniuxhNuxg 沃爾什正反變換核為：)(xbi當(dāng) n= 1、2、3時 如下表)(xbi下面是 n = 1、2、3 時的 g(x,u)，用“+”表示 +1、用“-”表示 -1例：求N = 4 時的沃爾什變換 因為 所以 u、x = 0、1、2、3 , n = 2224N)3()2()1 ()0(41)1()(41)0(3010)0()(12ffffxfWxibxbii)3()2

38、()1 ()0(41)1()(41)1 (3010)1()(1ffffxfWxibxbii)3()2()1 ()0(41)1()(41)3(3010)3()(1ffffxfWxibxbii)3()2()1()0(41)1()(41)2(3010)2()(1ffffxfWxibxbiiW ( 0 )W ( 1 )W ( 2 )W ( 3 ) f ( 0 ) f ( 1 ) f ( 2 ) f ( 3 )= 1/41 1 1 11 1 -1 -11 -1 1 -11 -1 -1 1用矩陣表達如下二維變換對為：其中，x,y,u,v=0,1,2N-1 101010)()()()(211) 1(),(1

39、),(NxNynivbybubxbiniiniyxfNvuW101010)()()()(11) 1(),(),(NuNvnivbybubxbiniinivuWyxf3.3.2、二維離散沃爾什變換其中，沃爾什正反變換核分別為：10)()()()(211) 1(1),(nivbybubxbiniiniNvuyxg10)()()()(11) 1(),(nivbybubxbiniinivuyxh沃爾什正反變換核是可分離的和對稱的：GfGNW21GWGf 沃爾什變換的矩陣形式：g (x, y, u, v) = g1 (x, u) g2 (y, v) h (x, y, u, v) = h1 (x, u)

40、h2 (y, v) 其中，G是NxN的矩陣例：一個二維數(shù)字圖像信號的矩陣為 求此信號的二維DWT。解：因為 這里N = 41331133113311331fGfGNW210000000000001002000000000000160032161111111111111111113311331133113311111111111111111241W第四節(jié) 離散哈達瑪變換 也叫沃爾什-哈達瑪變換。 哈達瑪變換是一種特殊排列的沃爾什變換。哈達瑪變換的最大優(yōu)點在于它的變換核矩陣具有簡單的遞歸關(guān)系，即高階矩陣可以用兩個低階矩陣直積求得。3.4.1 一維離散哈達瑪變換要求N=2n，一維離散哈達瑪變換對為： 其中 u、x = 0、1、2 N-11010)()()1)(1)(NxniuibxibxfNuH1010)()()1)()(NuniuibxibuHxf)(zkb是z的二進制表示的第 k 位1010)()()()