第4章圖像變換

1、數(shù)字圖像處理第四章第四章 圖像變換圖像變換李熙瑩李熙瑩 副教授副教授http:/數(shù)字圖像處理一、概述一、概述 為了對(duì)圖像進(jìn)行處理和分析，將原來定義在空間域的圖像以某種形式轉(zhuǎn)換到另一些空間，利用這些空間特有的性質(zhì)進(jìn)行一些加工。 數(shù)學(xué)上：空域空域其它域其它域(如頻域如頻域)的數(shù)學(xué)變換的數(shù)學(xué)變換數(shù)字圖像處理 圖像（正交）變換圖像（正交）變換廣泛地應(yīng)用在圖像增強(qiáng)、圖像復(fù)原、特征提取、圖像識(shí)別和圖像編碼壓縮等處理中。 常用(正交)變換： 傅里葉變換傅里葉變換 離散余弦變換離散余弦變換 小波變換小波變換 離散離散K-L變換變換 典型變換： 傅里葉變換傅里葉變換頻率域頻率域數(shù)字圖像處理傅里葉變換傅里葉變換

2、法國數(shù)學(xué)家傅里葉法國數(shù)學(xué)家傅里葉 任何周期函數(shù)都可以表示為任何周期函數(shù)都可以表示為不同頻率不同頻率的正弦和的正弦和/或余弦和的形式，每個(gè)正弦和或余弦和的形式，每個(gè)正弦和/或余弦乘以不或余弦乘以不同的系數(shù)（傅里葉級(jí)數(shù)）。同的系數(shù)（傅里葉級(jí)數(shù)）。 非周期函數(shù)（有限）也可以用正弦和非周期函數(shù)（有限）也可以用正弦和/或余弦或余弦乘以加權(quán)函數(shù)的積分表示。乘以加權(quán)函數(shù)的積分表示。 用傅里葉級(jí)數(shù)或變換表示的函數(shù)特征可以通用傅里葉級(jí)數(shù)或變換表示的函數(shù)特征可以通過傅里葉反變換完全重建，不丟失任何信息。過傅里葉反變換完全重建，不丟失任何信息。數(shù)字圖像處理數(shù)字圖像處理本章主要內(nèi)容本章主要內(nèi)容 圖像（正交）變換、頻域

3、概念圖像（正交）變換、頻域概念 （離散）傅里葉變換和性質(zhì)（離散）傅里葉變換和性質(zhì) 圖像在離散傅里葉變換中的特性圖像在離散傅里葉變換中的特性要求要求 理解圖像變換理解圖像變換（傅里葉變換）原理原理 明確其在數(shù)字圖像處理上的應(yīng)用明確其在數(shù)字圖像處理上的應(yīng)用數(shù)字圖像處理二、傅里葉變換二、傅里葉變換dxexfuFuxj2)()( (1) 定義定義 f (x)為連續(xù)可積函數(shù)，其傅里葉變換定義傅里葉變換定義為：1. 一維傅里葉變換一維傅里葉變換傅里葉變換的指數(shù)項(xiàng)可以寫為：uxjuxuxj2sin2cosexp2 每個(gè)u值都確定所對(duì)應(yīng)的正弦和余弦對(duì)的頻率，所以稱為頻率頻率變量。數(shù)字圖像處理 F(u) = R

4、(u) + j I(u)幅度譜：相位譜：)(/ )(arctan)()()()(2122uRuIuuIuRuF復(fù)數(shù)表示：指數(shù)表示：)()()(ujeuFuF功率譜（譜密度）：)()()()(222uIuRuFuP也稱為 f (x) 的傅里葉頻譜傅里葉頻譜2122)()()(uIuRuF傅里葉反變換為：傅里葉反變換為：dueuFxfuxj2)()(數(shù)字圖像處理(2) 一維傅里葉變換舉例一維傅里葉變換舉例方波信號(hào)傅里葉變換后的幅度譜傅里葉變換傅里葉變換 光學(xué)透鏡光學(xué)透鏡通過傅里葉變換，可以從頻率成分分析一個(gè)函數(shù)。通過傅里葉變換，可以從頻率成分分析一個(gè)函數(shù)。圖4.1 一維傅里葉變換舉例數(shù)字圖像處理(

5、3) 一維離散傅里葉變換一維離散傅里葉變換(DFT)1, 1 , 0)(1)(102NuexfNuFNxNuxj1, 1 , 0)()(102NxeuFxfNuNuxj一維離散傅里葉變換公式為：逆變換為： 函數(shù) f (x) , x = 0, 1, 2, , N-1 表示從連續(xù)的公式取N個(gè)點(diǎn)。這些點(diǎn)是等間隔點(diǎn)。采樣： f (x0), f (x0+x), , f (x0+N-1x)。f (x) = f (x0+xx)F (u) = F (uu)u = 1/Nx數(shù)字圖像處理(a) (b)(c) (d)圖4.2 一維離散傅里葉頻譜(a) 一個(gè)M點(diǎn)離散函數(shù)（非零點(diǎn)K個(gè)）；(b) (a)的傅里葉頻譜(c)

6、 M點(diǎn)離散函數(shù)（非零點(diǎn)2K個(gè)） ； (d) (c)的傅里葉頻譜數(shù)字圖像處理2. 二維傅里葉變換二維傅里葉變換(1) 定義定義：二維傅里葉變換由一維傅里葉變換推廣而來： yxvyuxjyxfvuFdd)(2exp),(),(逆變換： vuvyuxjyxFyxfdd)(2exp),(),(相位譜(相位角)：2122),(),(),(vuIvuRvuF幅度譜幅度譜(頻譜）：頻譜）：),(),(arctan),(vuRvuIvu功率譜(譜密度)：),(),(),(),(222vuIvuRvuFvuP數(shù)字圖像處理例：給定二維方波 f (x,y) 如圖4-3（教材圖3-19） 所示，求其傅里葉變換F(u,

7、v)。0,; 0,00 ,0),(yYyxXxYyXxAyxf(2) 二維傅里葉變換舉例二維傅里葉變換舉例圖4.3 二維方波 f (x,y)二維方波數(shù)字圖像處理幅度(傅里葉譜)： dxdyeyxfvuFvyuxj)(2),(),( XYvyuxjdxdyAe00)(2XYvyjuxjdyedxeA0022YvxjXuxjvjeujeA020222121222vxjuxjevjAeujAvYevYuXeuXAXYvyjuxj)sin()sin(vYvYuXuXAXYvuF)sin()sin(| ),(|傅里葉變換：數(shù)字圖像處理(3) 二維離散傅里葉變換二維離散傅里葉變換對(duì)于二維傅里葉變換，其離散

8、形式為：10102),(1),(MxNyNvyMuxjeyxfMNvuF逆變換為：10102),(),(MuNvNvyMuxjevuFyxf幅譜(頻譜)、相譜：),(),(arctan),(),(),(),(),(),(),(),(2122),(vuRvuIvuvuIvuRvuFvujIvuRevuFvuFvuj數(shù)字圖像處理 圖像矩陣 實(shí)數(shù)1)1,(.1,1)(1,0)(.1)(1,.(1,1)(1,0)1)(0,.(0,1)(0,0)1)1,(.1,1)(1,0)(.1)(1,.(1,1)(1,0)1)(0,.(0,1)(0,0)NNFnFnFNFFFNFFFNNfnfnfNfffNfff

9、頻域矩陣頻域矩陣 復(fù)數(shù)復(fù)數(shù)數(shù)字圖像處理Nyvxuje/2圖4.4 傅里葉變換過程數(shù)字圖像處理(4) 二維離散傅里葉變換圖例二維離散傅里葉變換圖例傅里葉譜：傅里葉譜：|F(u,v)|=R2(u,v)+I2(u,v)1/2相位相位: : (u,v)= arctan(I(u,v)/R(u,v)(xF)(xF傅里葉譜圖傅里葉譜圖( (幅度譜)log(|F(u,v)|)相位譜圖相位譜圖圖4.5 二維離散傅里葉變換舉例數(shù)字圖像處理圖像的傅里葉變換例子圖像的傅里葉變換例子圖4.6 不同圖像的二維離散傅里葉變換從左到右：原圖像、幅度譜、相位譜 數(shù)字圖像處理幾何圖形的二維離散傅里葉變換（頻譜）幾何圖形的二維離散

10、傅里葉變換（頻譜）圖4.7 圓斑及其傅里葉頻譜圖圖4.8 方塊及其傅里葉頻譜圖數(shù)字圖像處理圖4.9 其他幾何圖像及其傅里葉頻譜圖數(shù)字圖像處理(5) 傅里葉頻譜的意義傅里葉頻譜的意義原始圖像原始圖像 頻譜圖頻譜圖 中心化并標(biāo)定的頻譜圖中心化并標(biāo)定的頻譜圖 相位譜圖相位譜圖 中心化并標(biāo)定的相位譜圖中心化并標(biāo)定的相位譜圖數(shù)字圖像處理頻譜中保留部分從左到右依次增大（園以中心為半徑）頻譜中保留部分從左到右依次增大（園以中心為半徑） 由上一行對(duì)應(yīng)列頻譜圖重建的圖像由上一行對(duì)應(yīng)列頻譜圖重建的圖像數(shù)字圖像處理頻譜中去除部分從左到右依次增大（園以中心為半徑）頻譜中去除部分從左到右依次增大（園以中心為半徑） 由上

11、一行對(duì)應(yīng)列頻譜圖重建的圖像由上一行對(duì)應(yīng)列頻譜圖重建的圖像數(shù)字圖像處理圖4.10 傅里葉頻譜圖中不同位置點(diǎn)的含義數(shù)字圖像處理(6) 傅傅里里葉變換應(yīng)用示例葉變換應(yīng)用示例圖4.11 應(yīng)用圖例圖像中的周期性噪聲產(chǎn)生了變換中的尖峰信號(hào)，可以通過修改傅里葉變換頻譜圖消除之。數(shù)字圖像處理(7) 幅值與相位在圖像恢復(fù)幅值與相位在圖像恢復(fù)(反變換反變換)中的作用中的作用 xFF1 xFxFF/ )(1只對(duì)幅度譜進(jìn)行恢復(fù)的結(jié)果只對(duì)幅度譜進(jìn)行恢復(fù)的結(jié)果只利用相位譜（頻譜為常數(shù)）進(jìn)行恢復(fù)的結(jié)果只利用相位譜（頻譜為常數(shù)）進(jìn)行恢復(fù)的結(jié)果圖4.12 傅里葉頻譜和相位譜反變換對(duì)應(yīng)的圖像數(shù)字圖像處理幅值譜幅值重構(gòu)圖像 相位重

12、構(gòu)圖像相位譜圖4.13 傅里葉頻譜和相位譜反變換對(duì)應(yīng)的圖像(二)數(shù)字圖像處理3. 二維二維( (離散離散) )傅里葉變換性質(zhì)傅里葉變換性質(zhì)(1) 線性性質(zhì)線性性質(zhì)),(),(),(),(22112211vuFavuFayxfayxfa(2) 比例比例(尺度變換尺度變換)性質(zhì)性質(zhì)byaxFabbyaxf,1),(3) 可分離性可分離性),(),(),(),(),(),(1111vuFFFvuFFFyxfyxfFFyxfFFvuFuvvuxyyx數(shù)字圖像處理(3) 可分離性可分離性 圖像1)1,(.1,1)(1,0)(.1)(1,.(1,1)(1,0)1)(0,.(0,1)(0,0)1)1,( .

13、1,1)( 1,0)( .1)(1,.(1,1)(1,0)1)(0,.(0,1)(0,0)1)1,(.1,1)(1,0)(.1)(1,.(1,1)(1,0)1)(0,.(0,1)(0,0)NNFNFNFNFFFNFFFNNFNFNFNFFFNFFFNNfNfNfNfffNfff 橫向橫向 縱向縱向數(shù)字圖像處理(4) 空間位移空間位移(時(shí)間時(shí)間/空間平移空間平移)NvyuxjevuFyyxxf/ )(20000),(),(5) 頻率位移頻率位移(頻率平移頻率平移),(),(00/ )(200vvuuFeyxfNyvxuj圖像中心化圖像中心化當(dāng)圖像在頻率域時(shí)移動(dòng)時(shí)需要用到頻率位移性質(zhì)當(dāng)圖像在頻率域

14、時(shí)移動(dòng)時(shí)需要用到頻率位移性質(zhì) 把圖像進(jìn)行傅里葉變換后，往往要把中心移到u0=v0=N/2的位置上。)2,2()1)(,(NvNuFyxfyxyxyxjNyvxujee) 1()(/ )(200數(shù)字圖像處理圖4.14 傅里葉頻譜中心化(a) 512512圖像，中心白色矩形大小為 2040，坐標(biāo)原點(diǎn)在左上角；(b) (a)的中心傅里葉頻譜，經(jīng)過了對(duì)數(shù)變換(a)(b)數(shù)字圖像處理(6) 周期性周期性 F(u,v) = F(u+aN, v+bN), f (x,y) = f (x+aN, y+bN)(7) 共軛對(duì)稱性共軛對(duì)稱性),(),(*vuFyxf(a) 圖形的頻譜分析和顯示(b) 圖像中心化102

15、102)()1(1)(1)2(NxNuxjxNxNuxjexfNexfNNuF周期性和共軛對(duì)稱性的應(yīng)用周期性和共軛對(duì)稱性的應(yīng)用數(shù)字圖像處理),(),(00Frf(8) 旋轉(zhuǎn)不變性旋轉(zhuǎn)不變性圖4.15 圖像旋轉(zhuǎn)前后對(duì)應(yīng)的傅里葉頻譜圖數(shù)字圖像處理10102),(),(1)0 , 0(NxNyyxfyxfNF(9) 平均值平均值(10) 卷積定理卷積定理),(),(),(),(vuHvuFyxhyxf),(),(),(),(vuHvuFyxhyxf(11) 相關(guān)定理相關(guān)定理互相關(guān)：),(),(),(),(*vuGvuFyxgyxf),(),(),(),(*vuGvuFyxgyxf自相關(guān)：2),(),

16、(),(vuFyxfyxf),(),(),(2vuFvuFyxf數(shù)字圖像處理圖像相關(guān)圖像相關(guān)圖4.16 利用相關(guān)尋找圖像中特定字符(a) 原始圖像(b) 模板(c) 相關(guān)圖像(d) 其中一行取值最高相關(guān)值最高相關(guān)值灰度級(jí)灰度級(jí)剖面線剖面線數(shù)字圖像處理(12) 帕塞瓦定理（能量定理）帕塞瓦定理（能量定理）10101010*21*21),(),(),(),(NxNyNuNvvuFvuFyxfyxf若 f1(x, y) = f2(x, y) = f (x, y)，則有：1010101022),(),(NxNyNuNvvuFyxf數(shù)字圖像處理4. 快速傅里葉變換快速傅里葉變換(FFT) 離散傅里葉變換

17、稱為信號(hào)處理的一種基礎(chǔ)工具的主要原因之一快速傅里葉快速傅里葉變換（變換（FFT） N點(diǎn)一維傅里葉變換要求N2次乘/加運(yùn)算，而使用FFT只需進(jìn)行Nlog2N次運(yùn)算。圖4.17 FFT與DFT的運(yùn)算量比較圖 n = 15 (32768點(diǎn)) 時(shí)，F(xiàn)FT相對(duì)DFT有接近2200：1的優(yōu)勢數(shù)字圖像處理(1) 快速傅里葉變換算法原理快速傅里葉變換算法原理NxuxNNxNuxjWxfNexfNuF002)(1)(1)(逐次倍加法一維DFT：其中：NjNeW2設(shè)N為2的正整數(shù)次冪，即：nN2N也可以表示為：,2MN M也是正整數(shù)。代入(1)式：1202)(21)(MxuxMwxfMuF120)12(210)2

18、(2) 12(1)2(121MxxuMMxxuMwxfMwxfM(1)(2)(3)(4)數(shù)字圖像處理由NjNeW2可知uxMuxMWW22所以12010) 12(1)2(121)(MxuMuxMMxuxMwwxfMwxfMuF定義：1, 1 , 0)2(1)(10MuwxfMuFMxuxMeven1, 1 , 0) 12(1)(120MuwxfMuFMxuxModd則uModdevenwuFuFuF2)()(21)(同理，由uMMuMWW和uMMuMWW22可得：uModdevenwuFuFMuF2)()(21)(5)(6)(7)(8)(9)數(shù)字圖像處理分析(6)到(9)式，可以得出： 一個(gè)N

19、點(diǎn)變換可以通過將原始表達(dá)式分成兩部分來計(jì)算。如式(8)和(9)所示。計(jì)算F(u)的前半部分： 對(duì)式(6)和式(7)給出的兩個(gè)N/2點(diǎn)變換進(jìn)行計(jì)算。計(jì)算出的Feven(u) 和Fodd(u)結(jié)果代入式(8)得到F(u)，u=0, 1, 2, , (N/2-1)。 另一半直接可從式(9)得出。數(shù)字圖像處理(2) 運(yùn)算次數(shù)運(yùn)算次數(shù) 令m(n)和a(n)分別代表算法所要求的復(fù)數(shù)乘法和加法的次數(shù)。 n = 1 2點(diǎn)變換， m(1) = 1，a(1) = 2 2點(diǎn)變換，需計(jì)算F(0)和F(1)。此時(shí)M=1, 單點(diǎn)傅里葉變換即其本身。由式(8)，只需一次Fodd(0)與 的乘法和一次加法即可得到F(0)；

20、再做一次加法即可得到F(1)。 n = 2 4點(diǎn)變換， m(2) = 2m(1)+2，a(2) = 2a(1)+4 獲取F(u)的第一半需計(jì)算2個(gè)2點(diǎn)的變換，這需要2m(1)=2次乘法和2a(1)=4次加法； 另一半還需令2次乘法和另2次加法。02W數(shù)字圖像處理 n = 3 8點(diǎn)變換， m(3) = 2m(2)+4 ，a(3) = 2a(2)+8 為得到Feven(u) 和Fodd(u) 需計(jì)算2個(gè)4點(diǎn)變換，需要2m(2)次乘法和2a(2)次加法。 另外還需要4次乘法和8次加法已得到全部變換。 任意n， 所需乘法次數(shù)：m(n) = 2m(n-1)+2n-1 ， n 1 所需加法次數(shù)：a(n)

21、= 2a(n-1)+2n ， n 1 如果 n = 0， m(0)=0，a(0)=0 可以用歸納法證明數(shù)字圖像處理NNnm2log21)(NNna2log)(N點(diǎn)一維離散快速傅里葉變換要求的乘法和加法運(yùn)算次數(shù)：快速傅里葉優(yōu)于直接的一維離散傅里葉的計(jì)算優(yōu)勢定義：NNNNNNC222loglog)(假設(shè),2nN 則計(jì)算優(yōu)勢可以用n表示：nnCn2)(數(shù)字圖像處理n = 15 (32768點(diǎn)) 時(shí)，F(xiàn)FT相對(duì)DFT有接近2200：1的優(yōu)勢nnCn2)(圖4.17 FFT與DFT的運(yùn)算量比較圖數(shù)字圖像處理 f(0) f(1) f(2) f(3) f(4) f(5) f(6) f(7) f(0) f(4

22、) f(2) f(6) f(1) f(5) f(3) f(7) f1 (0) f1 (1) f1 (2) f1 (3) f1 (4) f1 (5) f1 (6) f1 (7) f(0) f(4) f(2) f(6) f(1) f(5) f(3) f(7) W 0 W 4 W 0 W 4 W 0 W 4 W 0 W 4 f1 (0) f1 (1) f1 (2) f1 (3) f1 (4) f1 (5) f1 (6) f1 (7) W 4 W 6 f2 (0) f2 (1) f2 (2) f2 (3) f2 (4) f2 (5) f2 (6) f2 (7) W 0 W 2 W 4 W 6 W 0

23、W 2 f3 (0) f3 (1) f3 (2) f3 (3) f3 (4) f3 (5) f3 (6) f3 (7) f2 (0) f2 (1) f2 (2) f2 (3) f2 (4) f2 (5) f2 (6) f2 (7) W 4 W 5 W 7 W 6 W 3 W 2 W 1 W 0 F(0) F(1) F(2) F(3) F(4) F(5) F(6) F(7) FFT變換蝶形圖變換蝶形圖數(shù)字圖像處理 n2n1n0 x ( 0 0 0 ) x ( 0 0 1 ) x ( 0 1 0 ) x ( 0 1 1 ) x ( 1 0 0 ) x ( 1 0 1 ) x ( 1 1 0 ) x

24、 ( 1 1 1 ) x (000) x (100) x (010) x (110) x (001) x (011) x (101) x (111) n0=0 n0=1 x (000) x (100) x (010) x (110) x (001) x (101) x (101) x (111) n1=0 n1=1 n1=0 n1=1 x (000) x (100) x (010) x (110) x (001) x (101) x (101) x (111) n2=0 n2=1 n2=0 n2=1 n2=0 n2=1 n2=0 n2=1 奇偶分組和比特倒序奇偶分組和比特倒序數(shù)字圖像處理三、其

25、他可分離的圖像變換三、其他可分離的圖像變換 傅里葉變換是用無窮區(qū)間上的復(fù)正弦復(fù)正弦基函數(shù)基函數(shù)和信號(hào)的內(nèi)積描述信號(hào)中總體頻率分布，或者是將信號(hào)向不同頻率變量基函數(shù)矢量投影。 基函數(shù)基函數(shù)可以有其它不同類型，相當(dāng)于用不同類型基函數(shù)去分解信號(hào)（圖像）。 常用的幾種：余弦變換余弦變換沃爾什沃爾什-哈德瑪（哈德瑪（Walsh-Hadamard）變換）變換小波變換小波變換數(shù)字圖像處理 10)(10NxxfNF一維離散余弦變換定義： 102) 12(cos)(2NxNuxxfNuF一維離散余弦反變換定義： 102) 12(cos)(201)(NuNuxuFNFNxf1. 離散余弦變換離散余弦變換余弦變換的

26、變換核為NxuNxug212cos2,數(shù)字圖像處理1010),(10 , 0NxNyyxfNF二維離散余弦變換定義：10102) 12(cos),(2, 0NxNyNvyyxfNvF10102) 12(cos),(20 ,NxNyNuxyxfNuF10102) 12(cos2) 12(cos),(2,NxNyNvyNuxyxfNvuF數(shù)字圖像處理二維離散余弦反變換定義：111111112) 12(cos2) 12(cos),(22) 12(cos)0 ,(22) 12(cos), 0(20 , 01),(NuNvNuNvNvyNuxvuFNNuxuFNNvyvFNFNyxf數(shù)字圖像處理余弦變換可以利用傅里葉變換實(shí)現(xiàn)：將延拓為：則有： 1010212expRe2212cos2NxNxcNxujxfNNxuxfNuF 12 , 1, 01, 1 , 0,NNNxNxxfxfe 1200NxecxfF 12012012022exp2expRe2212expRe2212cos2NxeNxeNxecNuxjxfNujNNxujxfNNxuxfNuF數(shù)字圖像處理借助傅立葉變換計(jì)算余弦變換的步驟：1) 把 f (x)延拓成 fe(x) ，長度為2N；2) 求 fe (x) 的2N點(diǎn)的FFT；3) 對(duì)u各項(xiàng)