9

这不是一个“编程”问题。但我确信这是在这个社区中广为人知和理解的东西。

我有一个图像 x 和一个小得多的图像 y，我需要通过乘以它们的 FFT 来对两者进行卷积。但由于它们的大小不同，我不知道如何进行频域乘法。

我采用 x 的（二维）FFT（它是一个维度为 4096 x 4096 的整数矩阵），它给出了频域表示 X（它是一个复数矩阵，我认为它的维度是 2048 x 2048 ）。

同样，我采用（y 的二维 FFT（它是一个 64 x 64 维的整数矩阵），它给出了频域表示 Y（它也是一个复数矩阵，我认为它的维数是 32 × 32)。

我在 Numerical Recipes 中使用了fourn 函数，所以我的输入矩阵 x 和 y 必须折叠成一维数组，这些数组被它们的离散傅里叶变换 X 和 Y 所取代。关键是即使这是一个图像的二维问题，我正在处理一维数组。

如果我试图对两个尺寸完全相同的图像 x 和 y 进行卷积。这一切都非常简单：

 X = FFT(x)

 Y = FFT(y)

 Z = X * Y (term by term multiplication)

 Convolution of x and y = IFFT(Z)

但是如果 X 和 Y 的长度不同，我该如何做乘法呢？

一种可能性是将 y 填充为与 x 具有相同的尺寸。但这似乎非常低效。另一种可能性是填充 Y 使其具有与 X 相同的尺寸。但我不知道这在频率空间中意味着什么。

这是问这个问题的另一种方式：如果我想使用 FFT 对两个尺寸非常不同的图像进行卷积，以便可以对其光谱进行乘法（频域表示），我该如何进行乘法运算？

谢谢，

〜迈克尔。

4

2 回答 2

8

用零填充较小的数组（卷积核，在您的情况下为 y）以匹配输入图像大小（您的矩阵 x）是标准方法。如果您在空间域中进行卷积，那将是非常低效的，但是如果您将 FFT 相乘，这是必要的，并且计算填充数组的 FFT 的成本并不算太糟糕。

于 2009-09-03T22:38:42.757 回答
4

您认为两个频率间隔必须相同是正确的。举一个一维的例子（我使用的是 Matlab 语法）：

N = 4096;
M = 64;

x = randn(N, 1);
y = hann(M, 'symmetric');

zLinear = conv(x,y);
zCircular = ifft( fft(x) .* fft(y,N) );

disp(max(abs(zLinear(65:4096) - zCircular(65:4096))));

两种技术之间的差异约为 2e-14，因此舍入误差。请注意，由于线性卷积和循环卷积之间的差异，您必须跳过前 64 个样本。

在计算 zCircular 时，请注意 fft(y,N)，这是 Matlab 语法，用于在计算 fft 之前用零填充 y 信号直到 N。这可能被认为在内存使用方面效率低下，但比较速度：

线性卷积：4096 次乘法/加法，每个 64 = 262144 次乘法/加法

循环卷积：4096 的 2 个 FFT + 2 * 4096 个元素的 1 个复数乘法 + 1 个逆 FFT
= 3 * 4096 * log2(4096) + 4096 * 6 = 172032（假设复数乘法有 6 个操作）

基本上，FFT 的 NlogN 速度，即使你需要其中三个，也胜过 N * M 卷积运算，除非 M 非常短。

编辑为 2D 案例添加速度估计

值得补充的是，对于 2D 数据，速度优势被放大了。一个 2D FFT 需要 N * N * log2(N * N) 次运算，因此 N = 4096 的 3 个 FFT + 复数 N^2 数组相乘是 1.3e10 次运算。但是直接卷积是 N^2 * M^2 = 6.9e10 次操作，慢了大约 50 倍。

于 2009-09-03T22:39:32.753 回答