第4章圖像變換(1)

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

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

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

4、(u) + j I(u)幅度譜：相位譜：)(/ )(arctan)()()()(2122uRuIuuIuRuF復數(shù)表示：指數(shù)表示：)()()(ujeuFuF功率譜（譜密度）：)()()()(222uIuRuFuP也稱為 f (x) 的傅里葉頻譜傅里葉頻譜2122)()()(uIuRuF傅里葉反變換為：傅里葉反變換為：dueuFxfuxj2)()(數(shù)字圖像處理(2) 一維傅里葉變換舉例一維傅里葉變換舉例方波信號傅里葉變換后的幅度譜傅里葉變換傅里葉變換 光學透鏡光學透鏡通過傅里葉變換，可以從頻率成分分析一個函數(shù)。通過傅里葉變換，可以從頻率成分分析一個函數(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個點。這些點是等間隔點。采樣： 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) 一個M點離散函數(shù)（非零點K個）；(b) (a)的傅里葉頻譜(c)

6、 M點離散函數(shù)（非零點2K個） ； (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) 二維離散傅里葉變換二維離散傅里葉變換對于二維傅里葉變換，其離散

8、形式為：10102),(1),(MxNyNvyMuxjeyxfMNvuF逆變換為：10102),(),(MuNvNvyMuxjevuFyxf幅譜(頻譜)、相譜：),(),(arctan),(),(),(),(),(),(),(),(2122),(vuRvuIvuvuIvuRvuFvujIvuRevuFvuFvuj數(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、頻域矩陣頻域矩陣 復數(shù)復數(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) 傅里葉頻譜的意義傅里葉頻譜的意義原始圖像原始圖像 頻譜圖頻譜圖 中心化并標定的頻譜圖中心化并標定的頻譜圖 相位譜圖相位譜圖 中心化并標定的相位譜圖中心化并標定的相位譜圖數(shù)字圖像處理頻譜中保留部分從左到右依次增大（園以中心為半徑）頻譜中保留部分從左到右依次增大（園以中心為半徑） 由上一行對應列頻譜圖重建的圖像由上一行對應列頻譜圖重建的圖像數(shù)字圖像處理頻譜中去除部分從左到右依次增大（園以中心為半徑）頻譜中去除部分從左到右依次增大（園以中心為半徑） 由上

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

12、構圖像相位譜圖4.13 傅里葉頻譜和相位譜反變換對應的圖像(二)數(shù)字圖像處理3. 二維二維( (離散離散) )傅里葉變換性質傅里葉變換性質(1) 線性性質線性性質),(),(),(),(22112211vuFavuFayxfayxfa(2) 比例比例(尺度變換尺度變換)性質性質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) 空間位移空間位移(時間時間/空間平移空間平移)NvyuxjevuFyyxxf/ )(20000),(),(5) 頻率位移頻率位移(頻率平移頻率平移),(),(00/ )(200vvuuFeyxfNyvxuj圖像中心化圖像中心化當圖像在頻率域時移動時需要用到頻率位移性質當圖像在頻率域

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

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

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

17、稱為信號處理的一種基礎工具的主要原因之一快速傅里葉快速傅里葉變換（變換（FFT） N點一維傅里葉變換要求N2次乘/加運算，而使用FFT只需進行Nlog2N次運算。圖4.17 FFT與DFT的運算量比較圖 n = 15 (32768點) 時，F(xiàn)FT相對DFT有接近2200：1的優(yōu)勢數(shù)字圖像處理(1) 快速傅里葉變換算法原理快速傅里葉變換算法原理NxuxNNxNuxjWxfNexfNuF002)(1)(1)(逐次倍加法一維DFT：其中：NjNeW2設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)式，可以得出： 一個N

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

20、再做一次加法即可得到F(1)。 n = 2 4點變換， m(2) = 2m(1)+2，a(2) = 2a(1)+4 獲取F(u)的第一半需計算2個2點的變換，這需要2m(1)=2次乘法和2a(1)=4次加法； 另一半還需令2次乘法和另2次加法。02W數(shù)字圖像處理 n = 3 8點變換， m(3) = 2m(2)+4 ，a(3) = 2a(2)+8 為得到Feven(u) 和Fodd(u) 需計算2個4點變換，需要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點一維離散快速傅里葉變換要求的乘法和加法運算次數(shù)：快速傅里葉優(yōu)于直接的一維離散傅里葉的計算優(yōu)勢定義：NNNNNNC222loglog)(假設,2nN 則計算優(yōu)勢可以用n表示：nnCn2)(數(shù)字圖像處理n = 15 (32768點) 時，F(xiàn)FT相對DFT有接近2200：1的優(yōu)勢nnCn2)(圖4.17 FFT與DFT的運算量比較圖數(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ū)間上的復正弦復正弦基函數(shù)基函數(shù)和信號的內積描述信號中總體頻率分布，或者是將信號向不同頻率變量基函數(shù)矢量投影。 基函數(shù)基函數(shù)可以有其它不同類型，相當于用不同類型基函數(shù)去分解信號（圖像）。 常用的幾種：余弦變換余弦變換沃爾什沃爾什-哈德瑪（哈德瑪（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ù)字圖像處理余弦變換可以利用傅里葉變換實現(xiàn)：將延拓為：則有： 1010212expRe2212cos2NxNxcNxujxfNNxuxfNuF 12 , 1, 01, 1 , 0,NNNxNxxfxfe 1200NxecxfF 12012012022exp2expRe2212expRe2212cos2NxeNxeNxecNuxjxfNujNNxujxfNNxuxfNuF數(shù)字圖像處理借助傅立葉變換計算余弦變換的步驟：1) 把 f (x)延拓成 fe(x) ，長度為2N；2) 求 fe (x) 的2N點的FFT；3) 對u各項