txcl6-圖像變換

1、圖象變換概念為了有效和快速地對圖像進(jìn)行處理，常常需要將定義在原圖像空間上的圖像以某種形式轉(zhuǎn)換到另外的一些空間，并利用在這些空間的性質(zhì)方便地進(jìn)行一些加工，最后轉(zhuǎn)換到圖像空間中以得到所需的效果。這種轉(zhuǎn)換方法叫：圖像變換圖像空間-其他空間為正變換其他空間到圖像空間-為逆變換數(shù)字圖象處理圖象變換概念圖象變換一種重要的基本概念；是一種常用的、有效的分析工具。圖象變換的目的簡化圖像處理問題的求解；利于取得圖圖像的特征；從概念上增強(qiáng)對圖像信息的理解。圖象變換是一種二維正交變換，正交變換必須是可逆的（可逆性），正變換和反變換的算法不能太復(fù)雜（計(jì)算不復(fù)雜，有快速算法），簡化問題突出特征（有益于處理）；正交變換的

2、特點(diǎn)是在變換域中，圖像的能量集中分布在低頻部分，邊緣和線信息反映在高頻成分上。變換的實(shí)例對數(shù)變換（乘除變?yōu)榧訙p）；拉氏變換（微分方程的求解）；傅立葉變換（頻譜分析和濾波）。圖像變換的應(yīng)用圖像增強(qiáng)、恢復(fù)、特征提取、壓縮和形狀分析。常見變換沃爾什哈達(dá)瑪；哈爾變換；離散余弦變換；傅立葉變換；小波變換。數(shù)字圖象處理頻域與頻域變換頻域變換的理論基礎(chǔ)就是“任意波形都可以用單純的正弦波的加權(quán)和來表示”。 如圖7-1(a)所示的任意波形， 可分解為圖7-1(b)、 (c)、 (d)所示的不同幅值、 不同頻率的正弦波的加權(quán)和。 為便于理解， 將圖7-1(b)所示的正弦波取出來， 如圖6-2所示。 如果將虛線表示

3、的振幅為1且初相位為0的正弦波作為基本正弦波， 則實(shí)線表示的波形可由其振幅A和初相位確定。 圖象變換概念頻域世界與頻域變換頻域世界與頻域變換(a)(b)(c)(d)數(shù)字圖象處理圖1 任意波形可分解為正弦波的加權(quán)和 圖象變換概念初相位振幅 A基本 正弦波(A1, 0)角頻率OA數(shù)字圖象處理圖2 正弦波的振幅A和相位 圖象變換概念由此， 圖7-1(b)、 (c)、 (d)三個不同的正弦波形可以描述為圖7-3所示的兩幅圖。 其中圖7-3(a)表示振幅與頻率之間的關(guān)系， 稱為幅頻特性; 而圖7-3(b)表示初相位與頻率之間的關(guān)系，稱為相頻特性。 這樣便將圖7-1(a)所示的時域波形f(x)變換到圖7-

4、3所示的頻域F(f)。 顯然， 不管波形多么復(fù)雜， 均可將其變換到頻域。圖象變換概念數(shù)字圖象處理圖3（a）波形的頻域表示(a) 幅頻特性； (b) 相頻特性 AOfOf(a)(b)數(shù)字圖象處理圖象變換概念時域和頻域之間的變換可用數(shù)學(xué)公式表示如下： )(),()(ffAxf正變換逆變換(1) 式中： A(f)、 (f)分別為幅值和相位與頻率f之間的關(guān)系。 為能同時表示信號的振幅和相位， 通常采用復(fù)數(shù)表示法。 式(7-1)可用復(fù)數(shù)表示法表示為)()(fFxf正變換逆變換(2) 式中： F(f)用復(fù)數(shù)表示幅值、 相位與頻率f之間的關(guān)系。數(shù)字圖象處理圖象變換通用描述-離散通用公式（一維）正變換，正變換

5、核；反變換，反變換核；變換性質(zhì)由變換核性質(zhì)決定。通用公式（二維）正變換，正變換核；反變換核；變換性質(zhì)由變換核性質(zhì)決定。變換特性 可分離的； 加法對稱的。10),()()(NxuxgxfuT數(shù)字圖象處理10),()()(NuuxhuTxf1010),(),(),(NxNyvuyxgyxfvuT 1010),(),(),(NuNyvuyxhvuTvyxf),(),(),(21vyguxgvuyxg函數(shù)相等),(),(21vyguxg圖象變換通用計(jì)算方法可分離核一個具有可分離核的變換計(jì)算分兩步，每步作一個一維變換，f(x,y)行變換，T(x,v)列變換?？煞蛛x的和對稱核利用矩陣的優(yōu)點(diǎn)：得到的變換矩陣

6、可分解成若干個具有較少非零元素的矩陣乘積，可以減少操作次數(shù)。數(shù)字圖象處理102),(),(),(NyvygyxfvxT101),(),(),(NxuxgvxTvuTBAFABFBTBFABBAFABBTBAFAT1設(shè)計(jì)或構(gòu)建核函數(shù)設(shè)計(jì)或構(gòu)建核函數(shù)連續(xù)函數(shù)的傅立葉變換連續(xù)函數(shù)的傅立葉變換 若把一個一維輸入信號作一維傅立葉變換，該信號就被變換到頻域上的一個信號，即得到了構(gòu)成該輸入信號的頻譜，頻譜反映了該輸入信號由哪些頻率（幅值和相位）構(gòu)成。這是一種分析與處理一維信號的重要手段。 當(dāng)一個一維信號f(x)滿足狄里赫萊條件，即f(x) （1） 具有有限個間斷點(diǎn)； （2） 具有有限個極值點(diǎn)； （3） 絕對

7、可積。 圖象變換傅立葉變換數(shù)字圖象處理則其傅立葉變換對（傅立葉變換和逆變換）一定存在。在實(shí)際應(yīng)用中，這些條件一般總是可以滿足的。 一維傅立葉變換對的定義為 dueuFxfuFFdxexfuFxfFuxjuxj212)()()()()()(正變換 反變換 式中： ，x稱為時域變量，u稱為頻域變量。 1j數(shù)字圖象處理(3) (4) 以上一維傅立葉變換可以很容易地推廣到二維，如果二維函數(shù)f(x, y)滿足狄里赫萊條件，則它的二維傅立葉變換對為 dudvevuFyxfvuFFdxdyeyxfvuFyxfFvyuxjvyuxj)(21)(2),(),(),(),(),(),( 正變換 反變換 式中：x,

8、 y為時域變量；u, v為頻域變量。 (7-5) (7-6) 圖象變換傅立葉變換一維傅立葉變換及反變換F(u)是復(fù)函數(shù)數(shù)字圖象處理dueuFxfuFFdxexfuFxfFuxjuxj212)()()()()()()2sin(j)2cos()()(arctan()()()()(F)()()(F)2(sin)()()2(cos)()(R22222/122uxuxeuRuIuuIuRuuIuRudxuxxfvIdxuxxfuuxj相位能量振幅虛部實(shí)部 要在數(shù)字圖像處理中應(yīng)用傅立葉變換， 還需要解決兩個問題：一是在數(shù)學(xué)中進(jìn)行傅立葉變換的f(x)為連續(xù)（模擬）信號， 而計(jì)算機(jī)處理的是數(shù)字信號（圖像數(shù)據(jù)）

9、；二是數(shù)學(xué)上采用無窮大概念，而計(jì)算機(jī)只能進(jìn)行有限次計(jì)算。通常， 將受這種限制的傅立葉變換稱為離散傅立葉變換（Discrete Fourier Transform，DFT)。 設(shè)f(x)|f(0), f(1), f(2), , f(N-1)為一維信號f(x)的N個抽樣， 其離散傅立葉變換對為 圖象變換傅立葉變換數(shù)字圖象處理NuxjNxNuxjNxeuFNxfuFFexfuFxfF/2101/210)(1)()()()()(7-7) (7-8) 式中：x，u=0， 1， 2， , N1。 注： 式（7-8）中的系數(shù)1/N也可以放在式（7-7）中， 有時也可在傅立葉正變換和逆變換前分別乘以 ， 這是

10、無關(guān)緊要的， 只要正變換和逆變換前系數(shù)乘積等于1/N即可。 圖象變換傅立葉變換數(shù)字圖象處理N/ 1由歐拉公式可知 sincosjej將式(7-9)代入式(7-7)，并利用cos()=cos()，可得 102sin2cos)()(NxNuxjNuxxfuF 可見，離散序列的傅立葉變換仍是一個離散的序列，每一個u對應(yīng)的傅立葉變換結(jié)果是所有輸入序列f(x)的加權(quán)和（每一個f(x)都乘以不同頻率的正弦和余弦值），u決定了每個傅立葉變換結(jié)果的頻率。 (7-9) (7-10) 圖象變換傅立葉變換數(shù)字圖象處理根據(jù)傅立葉變換公式， 102sin2cos)()(NxNuxjNuxxfuF圖象變換傅立葉變換數(shù)字圖

11、象處理編程完成下列函數(shù)的傅立葉變換 (N=256,N512、N=1024)并統(tǒng)計(jì)出計(jì)算需要的時間。TxyTxyT/2通常傅立葉變換為復(fù)數(shù)形式， 即 )()()(ujIuRuF 式中，R(u)和I(u)分別是F(u)的實(shí)部和虛部。式也可表示成指數(shù)形式： F(u)=|F(u) |ej(u) 其中 )()(arctan)()()(| )(|22uRuIuuIuRuF(7-11) (7-12) 圖象變換傅立葉變換 通常稱|F(u) |為f(x)的頻譜或傅立葉幅度譜，(u)為f(x)的相位譜。 頻譜的平方稱為能量譜或功率譜，它表示為 )()(| )(|)(222uIuRuFuE圖象變換傅立葉變換 考慮到

12、兩個變量， 就很容易將一維離散傅立葉變換推廣到二維。 二維離散傅立葉變換對定義為1010)(2),(),(),(MxNyNvyMuxjeyxfvuFyxf1010)(21),(1),(),(MuNvNvyMuxjevuFMNyxfvuF(7-16) (7-17) 式中： u，x=0， 1， 2， ， M-1； v， y=0，1， ， N-1； x， y為時域變量； u，v為頻域變量。 圖象變換傅立葉變換圖象變換傅立葉變換二維傅立葉變換及反變換二維傅立葉變換離散表示數(shù)字圖象處理dudvevuFyxfvuFFdxdyeyxfvuFyxfFvyuxjvyuxj)(21)(2),(),(),(),()

13、,(),( 1010)/(21010)/(2),(),(),(1),(MxNyNvyMuxjMxNyNvyMuxjevuFyxfeyxfMNvuF像一維離散傅立葉變換一樣， 系數(shù)1/(MN)可以在正變換或逆變換中， 也可以分別在正變換和逆變換前分別乘上系數(shù) ， 只要兩系數(shù)的乘積等于1/(MN)即可。 二維離散函數(shù)的傅立葉頻譜、 相位譜和能量譜分別為MN1),(),(),(22vuIvuRvuF),(),(arctan),(vuRvuIvu),(),(),(22vuIvuRvuE(7-18) (7-19) (7-20) 式中： R(u，v)和I(u，v)分別是F(u，v)的實(shí)部和虛部。 圖象變換

14、傅立葉變換數(shù)字圖象處理圖象變換傅立葉變換二維傅立葉變換性質(zhì)1、可分離性2、線性3、比例性質(zhì)-尺度定理4、空間位移平移定理5、共軛對稱性6、積分7、變量函數(shù)之積8、平均值9、180度旋轉(zhuǎn)10、旋轉(zhuǎn)不變旋轉(zhuǎn)定理11、能量12、空間域 13、頻率域 14、相關(guān) 15 、周期數(shù)字圖象處理表7-1 二維DFT的性質(zhì) 圖象變換傅立葉變換數(shù)字圖象處理 續(xù)表數(shù)字圖象處理圖象變換傅立葉變換1. 可分離性由可分離性可知，一個二維傅立葉變換可分解為兩步進(jìn)行， 其中每一步都是一個一維傅立葉變換?？上葘(x，y)按行進(jìn)行傅立葉變換得到F(x， v)， 再對F(x， v)按列進(jìn)行傅立葉變換，便可得到f(x， y)的傅立

15、葉變換結(jié)果F(u， v)， 如圖7-4所示。 顯然先按列進(jìn)行傅立葉變換， 再按行進(jìn)行傅立葉變換也是可行的。圖象變換傅立葉變換數(shù)字圖象處理圖7-4 用兩次一維DFT計(jì)算二維DFT 數(shù)字圖象處理同理， 傅立葉變換的逆變換也具有可分離性。 利用傅立葉變換的可分離性， 可以簡化傅立葉變換的軟、 硬件設(shè)計(jì)， 用一維傅立葉變換軟件或硬件便可實(shí)現(xiàn)二維傅立葉變換。圖象變換傅立葉變換2. 平移性質(zhì)平移性質(zhì)表明只要將f(x， y)乘上因子(1)x+y再進(jìn)行離散傅立葉變換，即可將圖像的頻譜原點(diǎn)(0， 0)移動到圖像中心(M/2， N/2)處?？梢?，利用傅立葉變換的平移性質(zhì)將圖像頻譜原點(diǎn)移動到方便。圖像中心，更便于分

16、析和處理，特別是設(shè)計(jì)濾波器時更加圖7-5 傅立葉頻譜平移示意圖(a) 原圖像；（b）無平移的傅立葉頻譜；（c）平移后的傅立葉頻譜 (a) (b) (c) 圖象變換傅立葉變換數(shù)字圖象處理3、由表7-1中性質(zhì)9可知， 圖像的頻譜原點(diǎn)(0，0)代表的是圖像灰度的平均值， 是圖像信號中的直流分量。 因此， 平移后的頻譜中，圖像能量的低頻成分將集中到頻譜中心， 圖像上的邊緣、線條細(xì)節(jié)信息等高頻成分將分散在圖像頻譜的邊緣。 圖象變換傅立葉變換數(shù)字圖象處理 4、旋轉(zhuǎn)不變性、旋轉(zhuǎn)不變性由旋轉(zhuǎn)不變性可知，如果時域中離散函數(shù)旋轉(zhuǎn)0角度，則在變換域中該離散傅立葉變換函數(shù)也將旋轉(zhuǎn)同樣的角度。離散傅立葉變換的旋轉(zhuǎn)不變性

17、如圖7-6所示。 離散傅立葉變換的旋轉(zhuǎn)不變性（a） 原始圖像； （b） 原始圖像的傅立葉頻譜； （c） 旋轉(zhuǎn)45后的圖像； （d） 圖像旋轉(zhuǎn)后的傅立葉頻譜 (a)(b)(d)(c)圖象變換傅立葉變換數(shù)字圖象處理圖象變換傅立葉變換數(shù)字圖象處理圖象變換傅立葉變換數(shù)字圖象處理圖象變換傅立葉變換數(shù)字圖象處理圖象變換傅立葉變換數(shù)字圖象處理圖象變換傅立葉變換數(shù)字圖象處理圖象變換傅立葉變換數(shù)字圖象處理圖象變換傅立葉變換數(shù)字圖象處理圖象變換傅立葉變換數(shù)字圖象處理圖象變換傅立葉變換數(shù)字圖象處理圖象變換傅立葉變換數(shù)字圖象處理用傅立葉變換處理和分析信號，就像用三棱鏡分解光線一樣。讓一束白光通過三棱鏡，可將白光分解成

18、七色的彩虹，若將分解開的七色光再次通過三棱鏡，又可以得到白光。從形式上看這是由簡單變換出了繁復(fù)，實(shí)則是將混合的東西分解成了基本的元素，通過對其基本元素的分析與處理，進(jìn)而完成對信號的處理和分析。因此，傅立葉變換又有“數(shù)字棱鏡”的美譽(yù)。圖象變換傅立葉變換數(shù)字圖象處理7.2.4 快速離散傅立葉變換基本離散傅立葉變換計(jì)算量非常大， 運(yùn)算時間長。 可以證明其運(yùn)算次數(shù)正比于N2， 特別是當(dāng)N較大時， 其運(yùn)算時間將迅速增長，以至于無法容忍。為此， 需要研究離散傅立葉變換的快速算法(Fast Fourier Transform， FFT)。 1965年Cooley和Tukey首先提出了一種稱為逐次加倍法的快速

19、傅立葉變換算法(FFT)。采用該FFT算法， 其運(yùn)算次數(shù)正比于N lbN， 在N很大時計(jì)算量可以大大減少。 例如， FFT的運(yùn)算次數(shù)和DFT的運(yùn)算次數(shù)之比， 當(dāng)N=1024時為1/102.4； 當(dāng)N=4096時可達(dá)1/341.3。 7.3 頻域變換的一般表達(dá)式7.3.1 可分離變換二維傅立葉變換可用通用關(guān)系式來表示： 1010),(),(),(MxNyvuyxgyxfvuF1010),(),(),(MuNvvuyxhvuFyxf(7-21) (7-22) 式中：x，u取0，1，2，M1；y，v取0，1，2，N1；g(x，y，u，v)和h(x，y，u，v)分別稱為正向變換核和反向變換核。如果),

20、(),(),(21vyguxgvuyxg),(),(),(21vyhuxhvuyxh(7-23) (7-24) 則稱正反變換核是可分離的。進(jìn)一步，如果g1和g2，h1和h2在函數(shù)形式上一樣，則稱該變換核是對稱的。二維傅立葉變換對是式(7-21)和式(7-22)的一個特殊情況，它們的變換核為NvyjMuxjNvyMuxjeeevuyxg22)(2),(NvyjMuxjNvyMuxjeNeMeMNvuyxh22)(2111),(7-25) (7-26) 可見，它們均為可分離的和對稱的。如前所述，二維傅立葉變換可以利用變換核的可分離性，用兩次一維變換來實(shí)現(xiàn)，即可先對f(x，y)的每一行進(jìn)行一維變換得

21、到F(x，v)，再沿F(x，v)每一列取一維變換得到變換結(jié)果F(u，v)。對其它的圖像變換，只要其變換核是可分離的，同樣可用兩次一維變換來實(shí)現(xiàn)二維變換。 若先對f(x，y)的每一列進(jìn)行一維變換得到F(y，u)，再沿F(y，u)每一行取一維變換得到F(u，v)，其最終結(jié)果相同。該結(jié)論對逆變換也適用。7.3.2 圖像變換的矩陣表示數(shù)字圖像都是實(shí)數(shù)矩陣，設(shè)f(x，y)為MN的圖像灰度矩陣，通常，為了分析、推導(dǎo)方便，將可分離變換寫成矩陣的形式：QfPF 11FQPf(7-27) (7-28) 式中：F、f是二維MN的矩陣；P是MM矩陣；Q是NN矩陣。圖像變換的矩陣表達(dá)式和代數(shù)表達(dá)式其本質(zhì)相同，將式(7

22、-27)寫成代數(shù)表達(dá)式如下： 1010),(),(),(),(MxNyvxQyxfuxPvuF(7-29) 式中：u取0，1，2，M1；v取0，1，2，N1。對二維離散傅立葉變換，則有： MxujeuxguxP21),(),(NvyjevygvyQ22),(),(7-30) (7-31) 圖像處理實(shí)踐中，除了DFT變換之外，還可采用其它正交變換，例如離散余弦變換、沃爾什-哈達(dá)瑪變換、K-L變換等。下面對常用的變換作簡要介紹。Cooley-Tukey FFT算法的基本思想是將f(x)序列按x的奇偶進(jìn)行分組計(jì)算，并充分利用傅立葉變換的周期性和對稱性進(jìn)行計(jì)算，采用迭代法，大大簡化了程序設(shè)計(jì)的復(fù)雜度，

23、提高了計(jì)算速度。Sande-Tukey FFT算法與Cooley-Tukey FFT算法類似，只不過它是將f(x)序列按中心位置點(diǎn)進(jìn)行分組計(jì)算的。限于篇幅，F(xiàn)FT算法的詳細(xì)內(nèi)容不再冗述。當(dāng)然對于計(jì)算機(jī)專業(yè)的學(xué)生而言，每個人都應(yīng)嘗試編寫快速傅立葉變換的程序。有關(guān)傅立葉變換的算法還有很多，網(wǎng)上的FFT算法源代碼也非常多，但不建議大家拿來就用。當(dāng)你得到類似的代碼后，一定要認(rèn)真分析其實(shí)現(xiàn)過程和思路，只有這樣才能不斷地提高編程水平。 圖象變換快速傅里葉變換傅里葉變換計(jì)算量很大N的4次方 復(fù)數(shù)乘法和N2(N2-1)次加法，相當(dāng)8N4次方浮點(diǎn)運(yùn)算?？焖俑道锶~變換 u的N個值中每次都需進(jìn)行N次復(fù)數(shù)乘法和N-1

24、次加法，即乘法和加法都正比于N的平方。 但e項(xiàng)可計(jì)算一次然后存儲于一個表中備查，所以正確分解公式，可以把乘法和加法減少為NLog2N。 這個分解過程為快速傅里葉變換（FFT） 數(shù)字圖象處理1.,1 , 0.)(1)(10 x/2NuexfNuFNNuxj 由于二維離散傅立葉變換具有可分離性， 即它可由兩次一維離散傅立葉變換計(jì)算得到，因此，僅研究一維離散傅立葉變換的快速算法即可。 先將式傅里葉變換寫成 10)()(NxuxWxfuF(5-21) 式中，W=e-j2N ，稱為旋轉(zhuǎn)因子。 這樣，可將式(7-21)所示的一維離散傅立葉變換（DFT）用矩陣的形式表示為 ) 1() 1 ()0() 1()

25、 1 ()0()1()1()1(2)1(1)1(00)1(02010)1(0201100)1(020100NfffWWWWWWWWWWWWWWWNFFFNNNNNNNN式中，由Wux構(gòu)成的矩陣稱為W陣或系數(shù)矩陣。 (5-22) 觀察DFT的W陣，并結(jié)合W的定義表達(dá)式W=e-j2N，可以發(fā)現(xiàn)系數(shù)W是以N為周期的。這樣，W陣中很多系數(shù)就是相同的， 不必進(jìn)行多次重復(fù)計(jì)算，且由于W的對稱性，即 xuNxuNxuNNjNWWWWeW22222, 1因此可進(jìn)一步減少計(jì)算工作量。 例如，對于N=4， W陣為 9630642032100000WWWWWWWWWWWWWWWW(5-23) 由W的周期性得：W4W

26、0，W6W2，W9W1；再由W的對稱性可得： W3W1，W2W0。于是式(7-23)可變?yōu)?1010000010100000WWWWWWWWWWWWWWWW(5-24) 可見N=4的W陣中只需計(jì)算W0和W1兩個系數(shù)即可。這說明W陣的系數(shù)有許多計(jì)算工作是重復(fù)的，如果把一個離散序列分解成若干短序列， 并充分利用旋轉(zhuǎn)因子W的周期性和對稱性來計(jì)算離散傅立葉變換，便可以簡化運(yùn)算過程，這就是FFT的基本思想。 設(shè)N為2的正整數(shù)次冪， 即 , 2 , 12nnn如令M為正整數(shù)，且 N=2M (5-25) (5-26) 將式（5-26）代入式（5-21），離散傅立葉變換可改寫成如下形式： 10) 12(2)2

27、(2101202) 12()2()()(MxxuMxuMMxMxuxMWxfWxfWxfuF由旋轉(zhuǎn)因子W的定義可知， 因此式(7-27)變?yōu)?uxMuxMWW22uMuxMMxMxuxMWWxfWxfuF21010) 12()2()( 現(xiàn)定義 1, 1 , 0,) 12()(1, 1 , 0,)2()(1010MxuWxfuFMxuWxfuFMxuxMoMxuxMe(5-27)(5-28)(5-29)(5-30)于是式(5-28)變?yōu)?)()()(2uFWuFuFouMe(5-31) 進(jìn)一步考慮W的對稱性和周期性可知 和， 于是 uMMuMWWuMMuMWW22)()()(2uFWuFMuFo

28、uMe(5-32)由此，可將一個N點(diǎn)的離散傅立葉變換分解成兩個N2短序列的離散傅立葉變換，即分解為偶數(shù)和奇數(shù)序列的離散傅立葉變換Fe(u)和Fo(u) 。 在此，以計(jì)算N=8的DFT為例，此時n=3，M=4。由式(5-31)和式(5-32)可得 ) 3() 3()7()2()2()6() 1 () 1 ()5()0()0()4() 3() 3() 3()2()2()2() 1 () 1 () 1 ()0()0()0(3828180838281808oeoeoeoeoeoeoeoeFWFFFWFFFWFFFWFFFWFFFWFFFWFFFWFF(5-33) 式（5-33）中，u取07時的F(u)

29、、Fe(u)和Fo(u)的關(guān)系可用圖7-7描述。左方的兩個節(jié)點(diǎn)為輸入節(jié)點(diǎn)，代表輸入數(shù)值；右方兩個節(jié)點(diǎn)為輸出節(jié)點(diǎn)，表示輸入數(shù)值的疊加，運(yùn)算由左向右進(jìn)行。線旁的W18和W18為加權(quán)系數(shù)，定義由F(1)、 F(5)、Fe(1)和Fo(1)所構(gòu)成的結(jié)構(gòu)為蝶形運(yùn)算單元, 其表示的運(yùn)算為 ) 1 () 1 ()5() 1 () 1 () 1 (1818oeoeFWFFFWFF(5-34) 圖5-7 蝶形運(yùn)算單元 Fe(1)F(1)F(5)Fo(1)18W18W 由于Fe(u)和Fo(u)都是4點(diǎn)的DFT，因此，如果對它們再按照奇偶進(jìn)行分組， 則有 ) 1 () 1 () 3()0()0()2() 1 ()

30、 1 () 1 ()0()0()0(28082808eoeeeeoeeeeoeeeeoeeeFWFFFWFFFWFFFWFF) 1 () 1 () 3()0()0()2() 1 () 1 () 1 ()0()0()0(28082808oooeooooeooooeooooeoFWFFFWFFFWFFFWFF（5-35a） （5-35b） 圖5-8 4點(diǎn)DFT分解為2點(diǎn)DFT的蝶形流程圖 Fee(0)Feo(1)08W28WFee(1)Feo(0)Fe(0)Fe(1)Fe(2)Fe(3)28W08WFoe(0)Foo(1)08W28WFoe(1)Foo(0)Fo(0)Fo(1)Fo(2)Fo(3)

31、28W08W圖5-9 8點(diǎn)DFT的蝶形流程圖 Fee(0)Feo(1)08W28WFee(1)Feo(0)Fe(0)Fe(1)Fe(2)Fe(3)28W08WFoe(0)Foo(1)08W28WFoe(1)Foo(0)Fo(0)Fo(1)Fo(2)Fo(3)28W08Wf (0)f (4)08W08Wf (2)f (6)08W08Wf (1)f (5)08W08Wf (3)f (7)08W08W08W18W28W38W08W18W28W38WF(0)F(1)F(2)F(3)F(4)F(5)F(6)F(7)圖5-10 8點(diǎn)DFT逐級分解框圖 第一級N / 4點(diǎn)DF Tf (0)f (4)N /

32、4點(diǎn)DF Tf (2)f (6)N / 2點(diǎn)DF TN / 4點(diǎn)DF Tf (1)f (5)N / 4點(diǎn)DF Tf (3)f (7)N / 2點(diǎn)DF T第二級N 點(diǎn)DFT第三級F(0)F(1)F(2)F(3)F (4)F(5)F(6)F (7)表表5-2 自然順序與碼位倒序（自然順序與碼位倒序（N=8） 上述FFT是將f(x)序列按x的奇偶進(jìn)行分組計(jì)算的，稱之為時間抽選FFT。如果將頻域序列的F(u)按u的奇偶進(jìn)行分組計(jì)算， 也可實(shí)現(xiàn)快速傅立葉計(jì)算， 這稱為頻率抽選FFT。 至此，讀者應(yīng)該對傅立葉變換的理論基礎(chǔ)及其實(shí)現(xiàn)方式有所了解。對于計(jì)算機(jī)專業(yè)的學(xué)生而言，每個人都應(yīng)該嘗試編寫快速傅立葉變換的

33、程序。當(dāng)然，有關(guān)傅立葉變換的算法還有很多， 網(wǎng)上的FFT算法源代碼也非常多，但不建議大家拿來就用。當(dāng)你得到類似的代碼后，一定要認(rèn)真分析其實(shí)現(xiàn)過程和思路，只有這樣才能不斷地提高編程水平。 離散余弦變換（離散余弦變換（DCT） 離散余弦變換（Discrete Cosine Transform， DCT）的變換核為余弦函數(shù)。DCT除了具有一般的正交變換性質(zhì)外， 它的變換陣的基向量能很好地描述人類語音信號和圖像信號的相關(guān)特征。因此，在對語音信號、圖像信號的變換中，DCT變換被認(rèn)為是一種準(zhǔn)最佳變換。近年頒布的一系列視頻壓縮編碼的國際標(biāo)準(zhǔn)建議中，都把DCT作為其中的一個基本處理模塊。除此之外， DCT還是

34、一種可分離的變換。 一維離散余弦變換一維離散余弦變換 一維DCT的變換核定義為 NuxNuCuxg2) 12(cos2)(),(式中，x, u=0, 1, 2, , N1； 其他1021)(uuC(5-47) (5-48) 一維DCT定義如下： 設(shè)f(x)|x=0, 1, , N-1為離散的信號列。 102) 12(cos)(2)()(NxNuxxfNuCuF(5-49) 式中，u, x=0, 1, 2, , N1。 將變換式展開整理后， 可以寫成矩陣的形式， 即 F=Gf （5-50） 其中 )2/) 12)(1cos()2/3)(1cos()2/) 1cos(/2)2/) 12cos()2

35、/6cos()2/cos(/2)2/) 12cos()2/3cos()2/cos(/2111/1NNNNNNNNNNNNNNNNNNNG(5-51) 一維DCT的逆變換IDCT定義為 102) 12(cos)()(2)(NuNuxuFuCNxf(5-52) 式中， x, u=0, 1, 2, , N1。可見一維DCT的逆變換核與正變換核是相同的。 二維離散余弦變換二維離散余弦變換 考慮到兩個變量，很容易將一維DCT的定義推廣到二維DCT。其正變換核為 NvyMuxvCuCMNvuyxg2) 12(cos2) 12(cos)()(2),(5-53) 式中，C(u)和C(v)的定義同式（7-48）

36、；x, u=0, 1, 2, , M1； y, v=0, 1, 2, , N1。 二維DCT定義如下：設(shè)f(x, y)為MN的數(shù)字圖像矩陣，則 NvyMuxvCuCyxfMNvuFMxNy2) 12(cos2) 12(cos)()(),(2),(1010(5-54) 式中： x, u=0, 1, 2, , M1； y, v=0, 1, 2, , N1。 二維DCT逆變換定義如下： NvyMuxvuFvCuCMNyxfMuNv2) 12(cos2) 12(cos),()()(2),(1010(5-55) 式中：x, u=0, 1, 2, , M1； y, v=0, 1, 2, , N1。 類似一

37、維矩陣形式的DCT，可以寫出二維DCT的矩陣形式如下： F=GfGT (5-56) 同時，由式(5-55)和式(5-54)可知二維DCT的逆變換核與正變換核相同，且是可分離的，即 NvyvCNMuxuCMvyguxgvuyxg2) 12(cos)(22) 12(cos)(2),(),(),(21(5-57)式中：C(u)和C(v)的定義同式（7-48）； x, u=0, 1, 2, , M1； y, v=0, 1, 2, , N1。 通常根據(jù)可分離性， 二維DCT可用兩次一維DCT來完成， 其算法流程與DFT類似， 即 ),(),(),(),(),(),(),(vuFvuFvxFFvxFvxF

38、yxfFyxfTTT轉(zhuǎn)置列轉(zhuǎn)置行(5-58) 快速離散余弦變換快速離散余弦變換 離散余弦變換的計(jì)算量相當(dāng)大， 在實(shí)用中非常不方便， 也需要研究相應(yīng)的快速算法。目前已有多種快速DCT（FCT）， 在此介紹一種由FFT的思路發(fā)展起來的FCT。 首先，將f(x)延拓為 0)()(xfxfex=0, 1, 2, , N-1x=N， N+1, , 2N-1 (5-59) 按照一維DCT的定義，fe(x)的DCT為 10)(1)0(NxexfNF(5-60) NxujNxeNujNuxjNxeNxeNNxeNxeNNxNxNxexfeNexfNNuxxfNNuxxfNNuxxfNNuxNNuxxfNNux

39、xfNuF2212022)12(1201201210121010)(Re2)(Re22) 12(cos)(22) 12(cos)(22) 12(cos)(22) 12(cos022) 12(cos)(22) 12(cos)(2)(式中，Re表示取復(fù)數(shù)的實(shí)部。 由于 為fe(x)的2N點(diǎn)DFT。因此，在作DCT時，可把長度為N的f(x)的長度延拓為2N點(diǎn)的序列fe(x)，然后對fe(x)作DFT，最后取DFT的實(shí)部便可得到DCT的結(jié)果。 同理對于離散余弦逆變換IDCT，可首先將F(u)延拓為12022)(NxNxujeexf0)()(uFuFeu=0, 1, 2, , N-1u=N, N+1,

40、, 2N-1 (5-62) 由式(5-52)可得，DCT的IDCT為 1202) 12(21212) 12(121)(Re2) 0(21)(Re2) 0(12) 12(cos)(2) 0(1)(NuNuxjNujeeNuNuxjeeNueeeeuFNFNNeuFNFNNuxuFNFNxf（5-63） 由式（7-63）可見，IDCT可由 的2N點(diǎn)的IDFT來實(shí)現(xiàn)。 NujeeuF2)( 最后要注意的是二維DCT的頻譜分布， 其譜域分布與DFT相差一倍，如圖7-11所示。 從圖中可以看出，對于DCT而言，(0, 0)點(diǎn)對應(yīng)于頻譜的低頻成分，(N-1, N-1)點(diǎn)對應(yīng)于高頻成分，而同階的DFT中，

41、(N2, N2)點(diǎn)對應(yīng)于高頻成分（注： 此頻譜圖中未作頻譜中心平移）。 由于DFT和IDFT已有快速算法FFT和IFFT，因此可用它們實(shí)現(xiàn)快速DCT和IDCT算法FCT及IFCT。不過，由于FFT及IFFT中要涉及到復(fù)數(shù)運(yùn)算， 因此這種FCT及IFCT算法并不是最佳的。 圖5-11 DFT和DCT的頻譜分布（a）DFT頻譜分布； （b） DCT頻譜分布 圖象變換離散余弦變換離散余弦變換簡化傅立葉變換的重要方法，圖像壓縮與傳輸中用。 虛數(shù)傅立葉變換項(xiàng) 為零時，不需計(jì)算，只需計(jì)算余弦項(xiàng)，是傅立葉變換的特例。數(shù)字圖象處理)2) 12(cos()()()()2) 12(cos()()()(1010Nu

42、xuCuaxfNuxxfuauCNxNx)2) 12(cos()2) 12(cos(),()()(),()2) 12(cos()2) 12(cos(),()()(),(101010NuyNuxvuCvauayxfNvyNuxyxfvauavuCNxNxNy 圖像增強(qiáng)的目的主要包括：消除噪聲，改善圖像的視覺效果；突出邊緣，有利于識別和處理。前面是關(guān)于圖像空間域增強(qiáng)的知識，下面介紹頻率域增強(qiáng)的方法。 假定原圖像為f(x，y)，經(jīng)傅立葉變換為F(u，v)。頻率域增強(qiáng)就是選擇合適的濾波器H(u,v)對F(u,v)的頻譜成分進(jìn)行處理，然后經(jīng)逆傅立葉變換得到增強(qiáng)的圖像g(x,y)。 頻率域增強(qiáng)的一般過程如

43、下： DFT H(u，v) IDFT f(x，y) F(u，v) F(u，v)H(u，v) g(x，y) 濾波圖象變換圖像的頻率域增強(qiáng)數(shù)字圖象處理 主要過程：（1）計(jì)算需增強(qiáng)圖像的傅里葉變換（2）將傅里葉變換結(jié)果與一個轉(zhuǎn)移函數(shù)（根據(jù)需要設(shè)計(jì)）相乘（3）將處理結(jié)果用傅里葉反變換以得到增強(qiáng)結(jié)果常見方法：（1）、低通濾波（2）、高通濾波（3）、帶通和帶阻濾波（4）、同態(tài)濾波圖象變換圖像的頻率域增強(qiáng)數(shù)字圖象處理 圖像的平滑除了在空間域中進(jìn)行外，也可以在頻率域中進(jìn)行。由于噪聲主要集中在高頻部分，為去除噪聲改善圖像質(zhì)量，濾波器采用低通濾波器H(u,v)來抑制高頻成分，通過低頻成分，然后再進(jìn)行逆傅立葉變換獲

44、得濾波圖像，就可達(dá)到平滑圖像的目的。常用的頻率域低濾波器H(u,v)有四種：1理想低通濾波器 設(shè)傅立葉平面上理想低通濾波器離開原點(diǎn)的截止頻率為D0，則理想低通濾波器的傳遞函數(shù)為 由于高頻成分包含有大量的邊緣信息，因此采用該濾波器在去噪聲的同時將會導(dǎo)致邊緣信息損失而使圖像邊模糊。 ) 14 . 4 (),(0),(1),(00DvuDDvuDvuH圖象變換頻率域平滑頻率域平滑數(shù)字圖象處理2Butterworth低通濾波器 n階Butterworth濾波器的傳遞函數(shù)為： 它的特性是連續(xù)性衰減，而不象理想濾波器那樣陡峭變化，即明顯的不連續(xù)性。因此采用該濾波器濾波在抑制噪聲的同時，圖像邊緣的模糊程度大

45、大減小，沒有振鈴效應(yīng)產(chǎn)生。 nDvuDvuH20),(11),(圖象變換 Butterworth低通濾波器數(shù)字圖象處理3指數(shù)低通濾波器 指數(shù)低通濾波器是圖像處理中常用的另一種平滑濾波器。它的傳遞函數(shù)為： 采用該濾波器濾波在抑制噪聲的同時，圖像邊緣的模糊程度較用Butterworth濾波產(chǎn)生的大些，無明顯的振鈴效應(yīng)。 n-0Dv)D(u,e v)H(u,圖象變換指數(shù)低通濾波器數(shù)字圖象處理 4. 梯形低通濾波器 梯形低通濾波器是理想低通濾波器和完全平滑濾波器的折中。它的傳遞函數(shù)為： 它的性能介于理想低通濾波器和指數(shù)濾波器之間，濾波的圖像有一定的模糊和振鈴效應(yīng)。110DDD-v)D(u,0Dv)D(

46、u,0D),(DDv)D(u,1 v)H(u,101vuD圖象變換梯形低通濾波器數(shù)字圖象處理a) 出現(xiàn)虛假輪廓的圖 b) 理想低通濾波器平滑結(jié)果 c) 巴特沃斯濾波器平滑結(jié)果數(shù)字圖象處理圖像的邊緣、細(xì)節(jié)主要位于高頻部分，而圖像的模糊是由于高頻成分比較弱產(chǎn)生的。頻率域銳化頻率域銳化就是為了消除模糊，突出邊緣。因此采用高通濾波器讓高頻成分通過，使低頻成分削弱，再經(jīng)逆傅立葉變換得到邊緣銳化的圖像。常用的高通濾波器有： 1）理想高通濾波器 二維理想高通濾波器的傳遞函數(shù)為 00),(1),(0),(DvuDDvuDvuH圖象變換頻率域銳化頻率域銳化數(shù)字圖象處理2）巴特沃斯高通濾波器 n階巴特沃斯高通濾波器的傳遞函數(shù)定義如下 H(u，v)=1/1+(