2D FFT

fft2.ts

import FFT from "fft.js";

const getColumns = (d: number[][], cs: number[]) => {
  const res: number[] = [];
  for (let i = 0; i < d.length; ++i) {
    const r = d[i];
    res.push(...cs.map((x) => r[x]));
  }
  return res;
};

export const fft2 = (signals: number[][]) => {
  const w = signals[0].length;
  const h = signals.length;
  const rFFT = new FFT(w);
  const cFFT = new FFT(h);

  const rSpectrums: number[][] = [];
  const cSpectrums: number[][] = [];

  for (let i = 0; i < h; ++i) {
    const signal = signals[i];
    const out: number[] = [];
    rFFT.transform(out, rFFT.toComplexArray(signal));
    rSpectrums.push(out);
  }

  for (let i = 0; i < w; ++i) {
    const complexColumns = getColumns(rSpectrums, [2 * i, 2 * i + 1]);
    const out: number[] = [];
    cFFT.transform(out, complexColumns);

    for (let j = 0; j < h; ++j) {
      cSpectrums[j] ||= [];
      cSpectrums[j].push(out[2 * j], out[2 * j + 1]);
    }
  }

  return cSpectrums;
};

export const ifft2 = (spectrums: number[][]) => {
  const w = spectrums[0].length / 2; // spectrum is complex array
  const h = spectrums.length;
  const rFFT = new FFT(w);
  const cFFT = new FFT(h);

  const rSignal: number[][] = [];
  const cSignal: number[][] = new Array(h).map(() => []);

  for (let i = 0; i < w; ++i) {
    const complexColumns = getColumns(spectrums, [2 * i, 2 * i + 1]);
    const out: number[] = [];
    cFFT.inverseTransform(out, complexColumns);

    for (let j = 0; j < h; ++j) {
      cSignal[j] ||= [];
      cSignal[j].push(out[2 * j], out[2 * j + 1]);
    }
  }

  for (let i = 0; i < h; ++i) {
    const signal = cSignal[i];
    const out: number[] = [];
    rFFT.inverseTransform(out, signal);
    const reOut: number[] = rFFT.fromComplexArray(out);
    rSignal.push(reOut);
  }

  return rSignal;
};

use-it.ts

import { fft2, ifft2 } from './fft2';

const signal = [
  [255, 255, 255, 255, 255, 255, 255, 255, 255, 254, 227, 219, 249, 255, 255, 255, 255, 255, 255, 255, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
  [255, 255, 255, 255, 255, 255, 255, 255, 254, 233, 217, 217, 222, 251, 255, 255, 255, 255, 255, 255, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]

const spectrums = fft2(signal);
/*
spectrums should be:
[
  [9993, 0, -1293.6691327592985, -4424.249156802339, 1632.6776875637192, -1193.5049405306809, -694.4117895616429, -425.9687313341152, 586.8908729652601, -1099.4879861599295, 475.0644531418548, -70.27266703400375, -228.17336536940482, -635.7034385612945, 694.0917830517428, -284.4191307449835, 26, -47, 252.90545597012854, -536.6633863890632, 435.58635344250206, 100.88357336560834, -17.929582770524092, -227.41903751308885, 509.1091270347399, -211.4879861599295, 126.96826132521095, 155.57190756281233, 203.90932436318354, -300.91792860377814, 456.98055160252886, 134.19359692959392, -5, 0, 456.98055160252875, -134.19359692959392, 203.9093243631835, 300.91792860377814, 126.96826132521097, -155.57190756281219, 509.1091270347399, 211.4879861599295, -17.92958277052429, 227.41903751308888, 435.5863534425022, -100.88357336560831, 252.90545597012854, 536.6633863890631, 26, 47, 694.0917830517428, 284.41913074498353, -228.17336536940488, 635.7034385612943, 475.0644531418547, 70.27266703400389, 586.8908729652601, 1099.4879861599295, -694.411789561643, 425.9687313341149, 1632.6776875637192, 1193.504940530681, -1293.6691327592994, 4424.249156802339 ],
  [65, 0, -31.452633093275722, -53.812389462301326, -26.707171129872336, 47.650697086600076, 42.739585159432295, -1.1175086756775556, -15.393398282201815, -23.435028842544398, -4.074813613848903, 11.432951795017942, -3.813043332824037, -2.823562599588058, 5.890783827555367, 17.164722512433514, 18, -23, -36.42088136432707, -4.541453021414213, 15.955178956554875, 37.03430177668103, 23.780989147696687, -32.40448303635739, -36.606601717798185, -3.4350288425443978, 13.921771674867031, 27.412588861094207, 10.565035506141442, -20.491438537130875, -14.384801738099583, 4.848967371998015, 11, 0, -14.384801738099583, -4.848967371998015, 10.565035506141385, 20.49143853713079, 13.921771674867003, -27.41258886109418, -36.60660171779821, 3.4350288425443978, 23.780989147696715, 32.40448303635738, 15.955178956554931, -37.034301776681005, -36.42088136432707, 4.541453021414213, 18, 23, 5.890783827555367, -17.164722512433514, -3.8130433328239235, 2.823562599588058, -4.074813613848903, -11.432951795017942, -15.393398282201815, 23.435028842544398, 42.739585159432295, 1.117508675677584, -26.707171129872222, -47.650697086600076, -31.452633093275722, 53.812389462301326 ]
]
*/

const rebuiltSignal = ifft2(spectrums);
/*
rebuiltSignal should be:
[
  [255, 255, 255, 255, 254.99999999999997, 255.00000000000003, 255, 255, 255, 254.00000000000003, 227, 219, 248.99999999999997, 255, 255, 255, 255, 255, 255, 255, 2.842170943040401e-14, -2.842170943040401e-14, 1.4210854715202004e-14, 0, 1.4210854715202004e-14, -2.842170943040401e-14, 0, -4.263256414560601e-14, 2.842170943040401e-14, 1.4210854715202004e-14, 0, 0 ],
  [255, 255, 255, 255, 255, 255, 255, 255, 254, 232.99999999999994, 217, 217, 222, 250.99999999999994, 254.99999999999997, 255, 255, 255, 255, 255, 0, 1.4210854715202004e-14, 0, 1.4210854715202004e-14, 0, 5.684341886080802e-14, 0, 1.4210854715202004e-14, 0, 5.684341886080802e-14, 2.842170943040401e-14, 1.4210854715202004e-14 ]
]
*/