离散傅里叶变换

我们将寻求以下问题的答案：

• 什么是傅里叶变换（Fourier transform），为什么要使用它？
• 如何在 OpenCV 中实现？
• 诸如 copyMakeBorder()、merge()、dft()、getOptimalDFTSize()、log() 和 normalize() 等函数的使用。

源代码

C++

你可以从此处下载，或在 OpenCV 源码库的 samples/cpp/tutorial_code/core/discrete_fourier_transform/discrete_fourier_transform.cpp 中找到它。

Java

你可以从此处下载，或在 OpenCV 源码库的 samples/java/tutorial_code/core/discrete_fourier_transform/DiscreteFourierTransform.java 中找到它。

Python

你可以从此处下载，或在 OpenCV 源码库的 samples/python/tutorial_code/core/discrete_fourier_transform/discrete_fourier_transform.py 中找到它。

以下是 dft() 的一个使用示例：

（完整代码实现见C++ 源代码、Java 源代码、Python 源代码。）

解释

傅里叶变换会将一幅图像分解为它的正弦和余弦分量。换句话说，它会将图像从空间域变换到频率域。其核心思想是：任何函数都可以用无穷多个正弦和余弦函数之和来精确近似。傅里叶变换就是实现这一目标的一种方法。在数学上，二维图像的傅里叶变换为：

$F(k,l) = \displaystyle\sum\limits_{i=0}^{N-1}\sum\limits_{j=0}^{N-1} f(i,j)e^{-i2\pi(\frac{ki}{N}+\frac{lj}{N})}$

$e^{ix} = \cos{x} + i\sin {x}$

这里 f 是图像在空间域中的值，F 是图像在频率域中的值。变换的结果是复数。可以通过一幅实部图像和一幅虚部图像来显示它，也可以通过一幅幅值图像和一幅相位图像来显示。然而，在所有的图像处理算法中，只有幅值图像是有意义的，因为它包含了我们所需的关于图像几何结构的全部信息。不过，如果你打算在这些形式下对图像做一些修改然后再将其反变换回来，你就需要同时保留这两者。

在这个示例中，我将展示如何计算并显示傅里叶变换的幅值图像。数字图像是离散的，这意味着它们只能取给定值域中的某个值。例如，在一幅基本的灰度图像中，值通常介于 0 到 255 之间。因此，傅里叶变换也需要是离散类型的，由此得到离散傅里叶变换（Discrete Fourier Transform，DFT）。当你需要从几何角度确定一幅图像的结构时，就会用到它。以下是需要遵循的步骤（针对灰度输入图像 I）：

将图像扩展到最佳尺寸

DFT 的性能取决于图像尺寸。当图像尺寸是数字 2、3、5 的倍数时，它往往最快。因此，为了获得最佳性能，通常给图像填充边界值以得到具有这种特征的尺寸是一个好主意。getOptimalDFTSize() 返回这个最佳尺寸，我们可以使用 copyMakeBorder() 函数来扩展图像的边界（追加的像素初始化为零）：

（扩展图像尺寸的代码实现见源代码。）

为实部和虚部值腾出位置

傅里叶变换的结果是复数。这意味着对于每个图像值，结果是两个图像值（每个分量一个）。此外，频率域的范围远大于其空间域对应部分。因此，我们通常至少以 float 格式来存储它们。于是，我们将输入图像转换为这种类型，并用另一个通道来扩展它以存放复数值：

（为实部和虚部腾出位置的代码实现见源代码。）

执行离散傅里叶变换

可以进行就地计算（输入与输出相同）：

（执行 DFT 的代码实现见源代码。）

将实部和虚部值转换为幅值

一个复数有一个实部（Re）和一个虚部（Im）。DFT 的结果是复数。DFT 的幅值为：

$M = \sqrt[2]{ {Re(DFT(I))}^2 + {Im(DFT(I))}^2}$

转换为 OpenCV 代码：

（计算幅值的代码实现见源代码。）

切换到对数尺度

事实证明，傅里叶系数的动态范围太大，无法在屏幕上显示。我们有一些小的和大的变化值，这样无法直接观察到。因此，所有的高值都会变成白点，而小值则变成黑点。为了利用灰度值进行可视化，我们可以将线性尺度变换为对数尺度：

$M_1 = \log{(1 + M)}$

转换为 OpenCV 代码：

（对数尺度变换的代码实现见源代码。）

裁剪与重排

还记得在第一步中我们扩展了图像吗？现在该丢弃那些新引入的值了。出于可视化目的，我们还可以重排结果的各个象限，使原点（零，零）与图像中心相对应。

（裁剪与重排的代码实现见源代码。）

归一化

这一步同样是为了可视化目的。我们现在已经有了幅值，但它们仍然超出了图像显示范围 0 到 1。我们使用 cv::normalize() 函数将值归一化到这个范围。

（归一化的代码实现见源代码。）

结果

一个应用思路是确定图像中存在的几何方向。例如，让我们看看文本是不是水平的？观察一些文本时你会注意到，文本行多少形成了水平线，而字母多少形成了垂直线。在傅里叶变换中也可以看到文本片段的这两个主要分量。让我们使用这张水平和这张旋转的文本图像。

水平文本的情况：

旋转文本的情况：

可以看到，频率域中最具影响力的分量（幅值图像上最亮的点）遵循图像上物体的几何旋转。由此我们可以计算出偏移量，并进行图像旋转以校正可能的对齐偏差。