c++ - 2D FFT将两个矩阵都转换为FFT格式后该怎么办？

Question

假设我有2个矩阵:image, filter;，大小为MxM and NxN。
我的常规卷积看起来像这样，并生成矩阵output大小(M-N+1)x(M-N+1)。基本上，它将滤镜的左上角放在一个像素上，进行卷积，然后将总和分配给该像素:

for (int i=0; i<M-N; i++)
for (int j=0; j<M-N; j++)
{
    float sum = 0;
    for (int u=0; u<N; u++)
    for (int v=0; v<N; v++) 
        sum += image[i+u][j+v] * filter[u][v];
    output[i][j] = sum;
}

接下来，执行FFT:

在image, filter的右侧和底部都应用零填充(即，在右侧添加更多零列，在底部添加零行)。现在都具有(M + N)x(M + N);原始图片位于image[0->M-1][0-M-1]。

(对两个矩阵都执行相同操作)计算每行进入新矩阵的FFT，然后计算该新矩阵每一列的FFT。

现在，我有2个矩阵imageFreq和filterFreq，大小均为(M + N)x(M + N)，这是图像和滤波器的FFT形式。
但是如何从它们中获得所需的卷积值(如示例代码中所述)？

Answer 1

使用 FFT在A,B之间进行卷积是通过频域中每个元素的乘法完成的，因此在1D中类似这样:

通过FFT转换A，B
假设大小为N,M的A[N],B[M]第一个零填充到普通大小Q(其为2的幂)，并且大小至少为M+N，然后应用FFT:

Q = exp2(ceil(log2(M+N)));
zeropad(A,Q);
zeropad(B,Q);
a = FFT(A);
b = FFT(B);

卷积
在频域中，仅使用逐元素乘法:

for (i=0;i<Q;i++) a[i]*=b[i];

重建结果
只需应用IFFT(FFT的倒数)...

AB = IFFT(a); // crop to first N (real) elements

并仅使用第一个N元素(除非使用的算法需要更多取决于您在做什么...)

对于2D ，您可以直接在2D中进行卷积(使用2个嵌套的循环)，也可以分别对每个轴进行卷积。请注意，分隔轴还需要通过一些常数(取决于尺寸，分辨率和所使用的内核)对结果进行归一化
因此，当放在一起(还假设分辨率NxN和MxM相同)时，首先将零填充到(QxQ)，然后:

Q = exp2(ceil(log2(M+N)));
zeropad(A,Q,Q);
zeropad(B,Q,Q);
a = FFT(A);
b = FFT(B);
for (i=0;i<Q;i++)
 for (j=0;j<Q;j++) a[i][j]*=b[i][j];
AB = IFFT(a); // crop to first NxN (real) elements

再次裁剪为AB到NxN大小(除非...)以获取更多信息，请参阅:

How to compute Discrete Fourier Transform?

以及那里的所有子链接...同样在最后是使用NTT(FFT的一种特殊形式)来计算bignum乘法的一维卷积示例:

Modular arithmetics and NTT (finite field DFT) optimizations

同样，如果您想要真实结果，则仅使用结果的真实部分(忽略虚部)。