DFT(Discrete Fourier Transform)代表着离散傅里叶变换，是作为有限长序列的在数字信号处理中被广泛使用的一种频域表示方法，。DFT来源于傅里叶变换(FT)和周期序列的离散傅里叶级数(DFS)，DFS是一种适用于周期序列的变换。但由于实际的数字信号处理的过程中获取和处理的序列是有限长的序列，而周期序列作为一种理论上的模型实际上只有有限个序列值才具有意义，而且它和有限长序列有着本质上的联系。因此可以从周期序列的离散傅里叶级数(DFS)出发推导出有限长序列的离散频谱表达式(DFT)。可以将DFT所要变换的对象——有限长序列看成是周期序列的一个周期表示，即先把序列值周期延拓后再取主值序列后即可得到有限长序列。从而可以推断出DFT和IDFT的变换式为：

X\left(k\right)=DFT\left[x\left(n\right)\right]=\sum_{n=0}^{N-1}{x\left(n\right)e^{-j\frac{2\pi}{N}kn}}=\sum_{n=0}^{N-1}{x\left(n\right)W_N^{kn}}

x(n) = IDFT[X(k)] = \frac{1}{N}\sum\limits_{n = 0}^{N - 1} {X(k){e^{j\frac{{2\pi }}{N}kn}}} = \frac{1}{N}\sum\limits_{n = 0}^{N - 1} {X(k)W_N^{ - nk}}

同时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时的次数的千分之五。

DCT为离散余弦变换，是在DFT的基础上推导出来的，是DFT的一种特殊形式。在DFT傅立叶级数展开式中，如果被展开的函数是实偶函数，那么其傅立叶级数就只包含余弦项，再将其离散化(DFT)可导出该余弦项的余弦变换就是离散余弦变换(DCT)。离散余弦变换被展开的函数是实偶函数，因此离散余弦变换相当于一个长度是其本身两倍的离散傅里叶变换，并且离散余弦变换后的函数仍然为一个实偶函数。一维的DCT变换公式如下：

F(u) = \sqrt {\frac{2}{N}} \sum\limits_{x = 0}^{N - 1} {f(x)\cos \frac{{2(x + 1)u\pi }}{{2N}}}

f(x) = \sqrt {\frac{1}{N}} F(0) + \sqrt {\frac{2}{N}} \sum\limits_{u = 1}^{N - 1} {F(u)\cos \frac{{(2x + 1)u\pi }}{{2N}}}

对于图像这类的二维离散序列A来说，它的二维离散余弦变换定义如下所示： {B_{pq}} = {\alpha p}{\alpha _q}\sum\limits{m = 0}^{M - 1} {\sum\limits_{n = 0}^{N - 1} {{A_{mn}}\cos \frac{{\pi (2m + 1)p}}{{2M}}{\rm{cos}}\frac{{\pi (2n + 1)q}}{{2N}},0 \le p} \le M - 1;0 \le q \le N - 1}

其中B的值被称为矩阵A的DCT系数，在得到所有的DCT系数后，便形成了一个与A同样大小的矩阵B。通过下面的反离散余弦变换公式，可以由矩阵B恢复原来的离散序列A：

{A_{mn}} = \sum\limits_{p = 0}^{M - 1} {\sum\limits_{q = 0}^{N - 1} {{\alpha p}{\alpha _q}{B{pq}}\cos \frac{{\pi (2m + 1)p}}{{2M}}\cos \frac{{\pi (2n + 1)q}}{{2N}},0 \le m} \le M - 1;0 \le n \le N - 1}

{\alpha _p} = \left\{ \begin{array}{l} \frac{1}{{\sqrt M }},{\rm{ }}p = 0\\ \sqrt {\frac{2}{M}} ,{\rm{ }}1 \le p \le M - 1 \end{array} \right.{\rm{ }}{\alpha _q} = \left\{ \begin{array}{l} \frac{1}{{\sqrt N }},{\rm{ }}q = 0\\ \sqrt {\frac{2}{N}} ,{\rm{ }}1q \le N - 1 \end{array} \right.

DWT(Discrete Wavelet Transformation)代表着离散小波变换，是对基本小波的尺度和平移进行离散化的一种新型谱分析工具。它既能过考察考察局部时域过程的频域特征，又能考察局部频域过程的时域特征，因此即使是那些非平稳过程能够进行很好的变换和处理。对于图像来说，它能够将图像变换为一系列的小波系数并将这些系数进行高效的压缩和储存，并且小波的粗略边缘消除了DCT压缩普遍具有的方块效应从而可以更好地还原和表现图像。

在数字图像处理的过程中需要将连续的小波及小波变换进行离散化。一般计算机是二进制运算和处理的，因此使用计算机进行小波变换的实现需要进行二进制离散处理。这种离散化的小波及其相应的小波变换称为离散小波变换。实际上，离散小波变换是对连续小波变换的尺度、位移按照2的幂次进行离散化得到的，因此也被称为二进制小波变换。虽然经典的傅里叶变换能够反映出信号的全局及整体信息，但其表现形式却不够直观，并且信号频谱易受噪声信息的干扰从而复杂化。因此需要使用一系列的带通滤波器将信号分解为不同的频率分量并对这些频率子带进行分开处理。而小波分解的好处就在于它能够在不同的尺度上对信号进行分解，可以根据不同的用途及目标选择不同的尺度来获得想要的频域信息。

对于很多信号来说，其低频分量常常蕴藏在信号的基本特征，而高频信号只是给出了信号的细节信息，如图像信号的边缘轮廓信息。语音信号如果去掉了高频信号仍能听出所承载信息的基本内容，尽管声音听起来和以前可能不同；如果去掉信号的低频部分，则听到的是一些没有意义的声音。因此我们可以有选择的丢弃掉高频信息以达到有损压缩信号的目的。在小波分析中经常将信号分解为近似部分和细节部分，其中近似部分表示信号的低频信息；细节部分代表着信号的高频信息。因此原始信号通过两个相互的滤波器产生两个信号。通过不断的分解可以将近似信号连续分解成许多低分辨率的信号成分直到达到想要的目标。因此在实际的应用中，一般根据信号的特征或者合适的标准来选择适当的分解层数。

对于一个二维平面的任意函数 来说，其连续的小波变换为：

{W_f}(a,b) = \frac{1}{{\sqrt {|a|} }}\psi (\frac{{t - b}}{a}){\rm{ }}a,b \in R;a \ne 0

其重构公式(逆变换)为：

f(t) = \frac{1}{{{C_\psi }}}\int_{ - \infty }^\infty {\int_{ - \infty }^\infty {\frac{1}{{{a^2}}}{W_f}(a,b)\psi (\frac{{t - b}}{a})dadb} }

离散小波变换需要将连续小波变换中的尺度参数a和平移参数b平移参数b进行离散化。因此可以得到相应的离散小波变换为：

{W_f}(a,b) = < f,{\psi _{a,b}}(t) >

其重构公式为：

f(t) = \sum\limits_{a,b \in Z} { < f,{\psi {a,b}} > } {\psi {a,b}}(t)

这三种变换都是通过将空间域上的图像信号转换到频域中，然后在将图像的频域分解各个子带并对各个子带进行分析以得到想要的图像信息。其中DCT是DFT的一种特殊的形式，若被展开的函数是实偶函数，则其傅立叶级数中只包含余弦项，再将其离散化(DFT)就可导出DCT。因此DCT属于DFT 的一个子集，它们都是对信号的整体进行分析变换。而DCT和DWT的联系在于图像信号经过这两种变换之后的基本信息都集中于左上角，因此都可以只保留左上角的数据而删除其他数据并很好的还原回原始数据从而能进行图像压缩(见图1)。

从上文可知DCT是DFT的一种特殊的形式，DCT是对实偶函数进行转换的，它相当于一个长度大概是其两倍的傅里叶变换，并且变换之后得到的函数仍然是实偶函数。在图像处理的运用方面，DFT主要用于去除杂质成分对图像造成的干扰，如图像去噪等。图像经过离散傅里叶变换之后从时域信息变成了频域信息进而分为高频部分和低频部分，对高频噪声进行滤波即可去除掉在时域中难以区分的噪声及杂质成分。DCT则主要用于图像的压缩。图像经过离散余弦变换后其基本信息主要集中在左上角，因此可以去除除左上角之外的其他数据也能很好的将图像复原成原始的样子，因此能够在误差可接受的范围内将图像进行压缩储存。 DWT和DCT的区别在于图像进行DWT变换后其小波域分为四个子带，每个子带不仅包括图像的频域成分还包括其空域成分。并且其包含图像主要信息的左上角子带(LL子带)能够再次不断的进行DWT变换从而将其连续分解成许多不同分辨率的信号成分(见图2)，这意味着我们可以通过控制小波变换的层数来实现不同的压缩率目标。

从图3中我们可以看到尽管原始图像经过了多次小波变换，其基本的图像信息仍然集中在左上角的LL子带。因此虽然其图像的分辨率成指数级下降，我们还是可以使用各个层级的LL子带的数据恢复出原始的图像从而达到基本恢复图像的前提下各种压缩比的要求。

本文首发于我的个人网站上，禁止转载，侵权必究！