2.4 经典变换

2.4.1 快速傅里叶变换

快速傅里叶变换（Fast Fourier Transform，FFT）是利用计算机计算离散傅里叶变换（Discrete Fourier Transform，DFT）的高效、快速计算方法的统称，简称FFT，在1965年由Cooley和Tukey提出。FFT的本质就是DFT，可以将信号从时域变换到频域，而且时域和频域都是离散的。也就是说，FFT可以求出一个信号是由哪些正弦波叠加而成的，求出的结果就是这些正弦波的幅度和相位。例如，音乐播放器上面显示的就是音乐信号经过FFT之后的不同频率正弦波的幅度。在分析和合成语音信号时，在通信系统中实现全数字化的时分制与频分制（TDM/FDM）的复用转换时，在频域对信号滤波及相关分析时，我们都可以利用对雷达、声呐、振动信号的频谱分析的方法来提高对目标的搜索精度和跟踪的分辨率等。这些技术的应用都需要利用FFT。FFT具有计算量小的优点，能够广泛地应用在信号处理技术领域，再结合高速的硬件系统就可以实时处理信号。

首先来简单了解一下DFT的基本原理。

1.连续信号的傅里叶变换

设x(t)表示非周期连续的时间信号，可以利用傅里叶变换求出该信号的频谱信号。

式中，ω=2πf，f表示频率；X(ω)为非周期信号，并且具有连续的频率响应。

如果已知频谱信号X(ω)，可以利用式（2.19）的反傅里叶变换公式计算其时域响应。

2.一维离散傅里叶变换

为了在计算机上实现傅里叶变换计算，必须把连续函数离散化。离散函数的傅里叶变换称为离散傅里叶变换。

连续信号离散化过程如下。

（1）建立连续时间信号x(t)。

（2）设定采样间隔Δt。

（3）对连续信号做时域等间隔采样，得到离散序列x(kΔt)，k=0,1,2,N-1。

（4）得到具有N个元素的离散函数序列x(n)，x(n)可以利用式（2.20）计算求得。

式中，Ts表示采样周期，且Ts=1/Fs，Fs为采样频率。

因此，一维离散傅里叶变换（DFT）和一维离散傅里叶反变换（Inverse DFT）可表示为：

式中，ω'=ω/Fs，代表归一化后的频率弧长。

3.二维离散傅里叶变换

对于一个具有M×N尺度的二维离散函数f(x,y)，(x=0,1,2,M-1;y=0,1,2,N-1)，其离散傅里叶变换可以表示为：

对于一个具有M×N尺度的二维离散函数F(u,v),(u=0,1,2,M-1;v=0,1,2,N-1)，其离散反傅里叶变换可以表示为：

在运用计算机进行二维离散傅里叶变换时，可先对每一行或者每一列进行一维的离散傅里叶变换，然后对上一步的计算结果再进行列或者行的一维离散傅里叶变换，具体步骤不再赘述。通过观察不难发现，二维离散傅里叶变换具有许多非常实用的性质，主要包括可分离性、平移性、线性特性、比例特性、周期性和共轭对称性、微分特性、旋转特性等，因此，在数字图像处理领域同样发挥着重要的作用。

FFT是根据DFT的奇、偶、虚、实等特性，对DFT的算法进行改进获得的。FFT的基础原理是把已知的N点序列，按顺序分解成一系列的短序列，再利用DFT计算式中指数因子所具有的对称性质和周期性质，求出这些短序列相应的DFT并进行适当组合，实现重复计算，降低乘法运算次数进而简化结构。当N是素数时，可以将DFT计算转化为求循环卷积，从而进一步减少乘法次数，提高速度。FFT在傅里叶变换的理论中并没有发现创新点，但是能够将离散傅里叶变换应用在计算机系统，或者说，在数字系统中已经进了一大步。FFT的结果具有对称性，通常只需要利用前半部分的结果即可，即小于采样频率一半的结果。

2.4.2 图像变换

在计算机视觉领域，所谓的图像变换技术，就是为了更加快速有效地处理和分析图像。首先，需要通过某种形式将原定义在图像空间的图像转化到另外的空间，然后利用空间的特性对图像进行一定的加工，最后再转换回图像空间得到所需的效果。许多图像处理和分析技术都是以图像变换技术为背景的，上文提到的傅里叶变换是应用最广泛和重要的图像变换手段之一。为了提高运算速度，计算机中多采用快速傅里叶变换算法。

对于数字图像而言，图像变换的作用对象为一个个独立的像素点，每一个像素点的值由多个通道的数值组合表示，而图像变换就是针对这些具体的像素值来操作的。在后面的实验章节，我们将结合Python语言及工具库，对几种比较简单的图像变换方法进行实验验证。

教材配套演示实验中包含了计算机视觉中经常使用的两个图像变换实例。为方便理解，现对这两个变换的基本原理进行简单的讲解。

1.Gamma变换

Gamma变换是对输入图像灰度值进行的非线性操作，使输出图像灰度值与输入图像灰度值呈指数关系，这个指数即Gamma。变换公式如下：

其中，Vin的取值范围为0～1，因此，在程序中需要先进行归一化处理，然后再进行指数运算。

人眼对外界光源的感光值与输入光强二者之间满足指数型关系。换句话说，就是在低照度下，人眼更容易分辨出亮度的变化，但光照强度的逐渐增加使得人眼不易分辨出亮度的变化，但是摄像机感光与输入光强二者之间满足线性关系。Gamma变换主要用于图像增强，可以提升图像黑暗部分细节的亮度。简单来说，就是通过非线性变换，让图像从曝光强度的线性响应变得更接近人眼感受的响应，即对过曝或曝光不足的图片进行矫正。

输入值经过Gamma变换后输出的图像灰度值关系如图2-1所示：横坐标表示输入灰度值，纵坐标表示输出灰度值，上方曲线表示的是gamma值小于1时的输入输出关系，下方曲线表示的是gamma值大于1时的输入输出关系。从图2-1可以看出，当gamma值小于1时，图像的整体亮度值得到提升，同时低灰度处的对比度得到增加，因而更利于分辨低灰度值时的图像细节。

Gamma变换规律可以总结如下：

gamma>1，较亮的区域灰度被拉伸，较暗的区域灰度被压缩得更暗，图像整体变暗；

gamma<1，较亮的区域灰度被压缩，较暗的区域灰度被拉伸得较亮，图像整体变亮。

2.卷积

卷积，有时也叫算子。用一个模板去和另一个图片对比，进行卷积运算，目的是使目标与目标之间的差距变得更大。卷积在数字图像处理中常见的应用为锐化和边缘提取。例如边缘提取，假如目标像素点和它周边的值有较大差异，就可以通过这个算子对原图矩阵中的这个位置进行卷积运算，得出的值和该像素点原来的灰度值会有显著的差异。当这种前后差异超过我们预设的范围后，就将这个像素点标记为0（白色），其余点标记为255（黑色），这样就得到了一幅以黑色为背景，白色线条作为边缘或形状的边缘提取效果图。

几个常用术语如下。

模板。模板就是一个矩阵（其实就是下面说的卷积核），也就是处理图像这个过程对应的函数，它对应卷积运算。

卷积运算。它可以看作加权求和的过程，为了增强图像和减少噪声，用该像素点的邻域像素点进行加权，处理完之后得到这个点的像素点。

卷积核。上面说的卷积运算，需要确定点的邻域和哪个矩阵进行加权，以及邻域内像素点所占的权重是多少。这些权重构成的矩阵就叫卷积核，卷积核的行数和列数都是奇数。

举例来说，对于数字图像来说，已知矩阵R和G，如果要对R5这个像素点进行卷积运算，有式（2.26）成立，这个卷积核的数组直接决定卷积的结果。

使用卷积核的时候会出现一个问题——边界问题：当处理图像边界像素时，如果卷积核不能匹配于图像使用区域，卷积核的中心与边界像素点对应，卷积运算会出现问题。一般可以选择如下两种处理方法：

（1）忽略边界像素，即处理后的图像将丢掉这些像素；

（2）保留原边界像素，即复制边界像素到处理后的图像。