一、DFT、DCT和DWT的概述

1.1 DFT與FFT簡介

DFT(Discrete Fourier Transform)代表著離散傅里葉變換，是作為有限長序列的在數字信號處理中被廣泛使用的一種頻域表示方法，。DFT來源于傅里葉變換(FT)和周期序列的離散傅里葉級數(DFS)，DFS是一種適用于周期序列的變換。但由于實際的數字信號處理的過程中獲取和處理的序列是有限長的序列，而周期序列作為一種理論上的模型實際上只有有限個序列值才具有意義，而且它和有限長序列有著本質上的聯系。因此可以從周期序列的離散傅里葉級數(DFS)出發推導出有限長序列的離散頻譜表達式(DFT)。可以將DFT所要變換的對象——有限長序列看成是周期序列的一個周期表示，即先把序列值周期延拓后再取主值序列后即可得到有限長序列。從而可以推斷出DFT和IDFT的變換式為：

同時x(n)的N點DFT也是其傅里葉變換在區間[0,2π]上的N點等間隔采樣，因此與傅里葉變換(FT)也關系密切。一般情況下，信號序列x(n)及其頻譜序列都是用復數來表示的，因此計算DFT的一個值X(k)需要進行N次復數乘法和N-1次復數加法。這就說明直接計算N點的DFT需要進行N2次復數乘法以及N(N-1)次復數加法，IDFT亦是如此。因此，DFT與IDFT的運算次數與N2成正比，隨著N的增加，運算量將急劇增加。

為了減少DFT的計算量從而快速的得到變換之后的結果，研究人員發明了一種算法——FFT算法。FFT算法將時域序列逐次分解為一組子序列，利用旋轉因子的特性由子序列的DFT來實現整個序列的DFT。DIT-FFT算法的原理是通過將原始有限長序列不斷進行奇偶分解成2M個DFT，再利用旋轉因子的特性和DFT的隱含周期性將計算量縮短。因此N=2M的序列經過M級時域奇偶抽取可分解為N個1點DFT（即時域序列本身）和M級蝶形運算，其中每一級蝶形運算有N/2個蝶形，含N/2次復乘和N次復加。通過計算可以得到總運算量為 次復乘和 次復加。FFT算法比直接計算DFT的運算量大大減少，尤其是N較大時，計算量的減少更為顯著。比如，當N=1024時，采用FFT算法時復數乘法的次數低于直接DFT時的次數的千分之五。

1.2 DCT簡介

DCT為離散余弦變換，是在DFT的基礎上推導出來的，是DFT的一種特殊形式。在DFT傅立葉級數展開式中，如果被展開的函數是實偶函數，那么其傅立葉級數就只包含余弦項，再將其離散化(DFT)可導出該余弦項的余弦變換就是離散余弦變換(DCT)。離散余弦變換被展開的函數是實偶函數，因此離散余弦變換相當于一個長度是其本身兩倍的離散傅里葉變換，并且離散余弦變換后的函數仍然為一個實偶函數。一維的DCT變換公式如下：

對于圖像這類的二維離散序列A來說，它的二維離散余弦變換定義如下所示：

其中B的值被稱為矩陣A的DCT系數，在得到所有的DCT系數后，便形成了一個與A同樣大小的矩陣B。通過下面的反離散余弦變換公式，可以由矩陣B恢復原來的離散序列A：

1.3 DWT簡介

DWT(Discrete Wavelet Transformation)代表著離散小波變換，是對基本小波的尺度和平移進行離散化的一種新型譜分析工具。它既能過考察考察局部時域過程的頻域特征，又能考察局部頻域過程的時域特征，因此即使是那些非平穩過程能夠進行很好的變換和處理。對于圖像來說，它能夠將圖像變換為一系列的小波系數并將這些系數進行高效的壓縮和儲存，并且小波的粗略邊緣消除了DCT壓縮普遍具有的方塊效應從而可以更好地還原和表現圖像。

在數字圖像處理的過程中需要將連續的小波及小波變換進行離散化。一般計算機是二進制運算和處理的，因此使用計算機進行小波變換的實現需要進行二進制離散處理。這種離散化的小波及其相應的小波變換稱為離散小波變換。實際上，離散小波變換是對連續小波變換的尺度、位移按照2的冪次進行離散化得到的，因此也被稱為二進制小波變換。雖然經典的傅里葉變換能夠反映出信號的全局及整體信息，但其表現形式卻不夠直觀，并且信號頻譜易受噪聲信息的干擾從而復雜化。因此需要使用一系列的帶通濾波器將信號分解為不同的頻率分量并對這些頻率子帶進行分開處理。而小波分解的好處就在于它能夠在不同的尺度上對信號進行分解，可以根據不同的用途及目標選擇不同的尺度來獲得想要的頻域信息。

對于很多信號來說，其低頻分量常常蘊藏在信號的基本特征，而高頻信號只是給出了信號的細節信息，如圖像信號的邊緣輪廓信息。語音信號如果去掉了高頻信號仍能聽出所承載信息的基本內容，盡管聲音聽起來和以前可能不同；如果去掉信號的低頻部分，則聽到的是一些沒有意義的聲音。因此我們可以有選擇的丟棄掉高頻信息以達到有損壓縮信號的目的。在小波分析中經常將信號分解為近似部分和細節部分，其中近似部分表示信號的低頻信息；細節部分代表著信號的高頻信息。因此原始信號通過兩個相互的濾波器產生兩個信號。通過不斷的分解可以將近似信號連續分解成許多低分辨率的信號成分直到達到想要的目標。因此在實際的應用中，一般根據信號的特征或者合適的標準來選擇適當的分解層數。

對于一個二維平面的任意函數 來說，其連續的小波變換為：

其重構公式(逆變換)為：

離散小波變換需要將連續小波變換中的尺度參數a和平移參數b平移參數b進行離散化。因此可以得到相應的離散小波變換為：

其重構公式為：

二、DFT、DCT和DWT的聯系和區別

2.1 聯系

這三種變換都是通過將空間域上的圖像信號轉換到頻域中，然后在將圖像的頻域分解各個子帶并對各個子帶進行分析以得到想要的圖像信息。其中DCT是DFT的一種特殊的形式，若被展開的函數是實偶函數，則其傅立葉級數中只包含余弦項，再將其離散化(DFT)就可導出DCT。因此DCT屬于DFT 的一個子集，它們都是對信號的整體進行分析變換。而DCT和DWT的聯系在于圖像信號經過這兩種變換之后的基本信息都集中于左上角，因此都可以只保留左上角的數據而刪除其他數據并很好的還原回原始數據從而能進行圖像壓縮(見圖1)。

圖1 DFT、DCT和DWT的聯系示意圖

2.2 區別

從上文可知DCT是DFT的一種特殊的形式，DCT是對實偶函數進行轉換的，它相當于一個長度大概是其兩倍的傅里葉變換，并且變換之后得到的函數仍然是實偶函數。在圖像處理的運用方面，DFT主要用于去除雜質成分對圖像造成的干擾，如圖像去噪等。圖像經過離散傅里葉變換之后從時域信息變成了頻域信息進而分為高頻部分和低頻部分，對高頻噪聲進行濾波即可去除掉在時域中難以區分的噪聲及雜質成分。DCT則主要用于圖像的壓縮。圖像經過離散余弦變換后其基本信息主要集中在左上角，因此可以去除除左上角之外的其他數據也能很好的將圖像復原成原始的樣子，因此能夠在誤差可接受的范圍內將圖像進行壓縮儲存。DWT和DCT的區別在于圖像進行DWT變換后其小波域分為四個子帶，每個子帶不僅包括圖像的頻域成分還包括其空域成分。并且其包含圖像主要信息的左上角子帶(LL子帶)能夠再次不斷的進行DWT變換從而將其連續分解成許多不同分辨率的信號成分(見圖2)，這意味著我們可以通過控制小波變換的層數來實現不同的壓縮率目標。

圖2 連續DWT變換示意圖

從圖3中我們可以看到盡管原始圖像經過了多次小波變換，其基本的圖像信息仍然集中在左上角的LL子帶。因此雖然其圖像的分辨率成指數級下降，我們還是可以使用各個層級的LL子帶的數據恢復出原始的圖像從而達到基本恢復圖像的前提下各種壓縮比的要求。

圖3 三次haar小波變換后生成的圖像