gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-03 07:21:55 26 4
gpt4 key购买 nike

假设我有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个矩阵 imageFreqfilterFreq,大小均为(M + N)x(M + N),这是图像和滤波器的FFT形式。
    但是如何从它们中获得所需的卷积值(如示例代码中所述)?

    最佳答案

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

  • 通过FFT转换A,B
    假设大小为N,MA[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个嵌套的循环),也可以分别对每个轴进行卷积。请注意,分隔轴还需要通过一些常数(取决于尺寸,分辨率和所使用的内核)对结果进行归一化
    因此,当放在一起(还假设分辨率 NxNMxM相同)时,首先将零填充到( 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
    再次裁剪为 ABNxN大小(除非...)以获取更多信息,请参阅:
  • How to compute Discrete Fourier Transform?

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

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

    关于c++ - 2D FFT将两个矩阵都转换为FFT格式后该怎么办?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/64851542/

    26 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com