这个逆 FFT 实现有什么问题

Question

我正在对图像使用以下快速傅立叶逆变换 (FFT) 的实现，其中大小为 N 乘以 N 的图像存储在长度为 N x N 的向量中（具有 N一个平方数）。当我为这个实现提供一个除两个 1 之外的零矩阵，其中一个在中心上方几行并且在中心下方对称时，逆正确地是一个具有垂直带的图像，其频率与 1s 的位置匹配。

然而，当 1 位于中心的左侧和右侧时，我得到了水平条带，但它们并不是完全水平的。他们有一个非常小的坡度。当我在 Mathematica 中使用内置

InverseFourier

函数执行完全相同的操作时，条带非常精确地水平。

下面的JavaScript实现有问题吗？相关代码如下； this JSFiddle

提供完整的 MWE

function invFFT_radix2(out, start, input, N, offset, s ) {
    if (N === 1) {
        out[start] = input[offset];
    } else {
        invFFT_radix2(out, start,     input, N/2, offset,   2*s);
        invFFT_radix2(out, start+N/2, input, N/2, offset+s, 2*s);
        for (var k = 0; k < N/2; k++) {
            var twiddle = cisExp(2*Math.PI*k/N);
            var t = out[start+k];
            out[start+k]     = t.plus ( twiddle.times(out[start+k+N/2]) );
            out[start+k+N/2] = t.minus( twiddle.times(out[start+k+N/2]) );
        }
    }
}

调用

invFFT_radix2(out, 0, input, input.length, 0, 1 )

其中

input

是输入向量，

out

包含结果。所有条目都是

Complex

数字（根据this response）和功能

cisExp

被定义为

function cisExp(x) { // e^ix = cos x + i*sin x
    return new Complex(Math.cos(x), Math.sin(x));
}

作为对比，这是使用 JSFiddle 放大后的图像顶部

和 Mathematica

JS 图像从左边的白线开始，右边变成黑色。

Answer 1

2D [逆] DFT 是一个轴上的 1D 版本然后另一个，所以你可以这样做，例如，

for (let i = 0; i < 2; i++) {
  for (let y = 0; y < HEIGHT; y++) {
    invFFT_radix2(out, y * WIDTH, ss, WIDTH, y * WIDTH, 1);
  }
  ss = out.slice();
  transpose(ss);
}

在哪里

const WIDTH = 256;
const HEIGHT = 256;
const swap = (arr, i, j) => {
  const t = arr[i];
  arr[i] = arr[j];
  arr[j] = t;
};
const transpose = (ss) => {
  for (let i = 1; i < HEIGHT; i++) {
    for (let j = 0; j < i; j++) {
      swap(ss, i * WIDTH + j, j * WIDTH + i);
    }
  }
};