在JavaScript中的离散傅里叶变换

Question

我想使用Highcharts展示脉搏波。当数据完好无损时，图表效果很好，如下图所示：image。但是，当存在噪声时，算法就不起作用了，如下图所示：带有坏点的图像。因此，我决定使用傅里叶变换来解决这个问题。请问是否有任何库可以执行DFT？还是我必须自己编写代码？请告诉我库的名称或解决此问题的方法以及您的想法。非常感谢！

- 邓启凡

---

https://github.com/scijs/fourier-transform/blob/master/benchmark.md 提供了一个不错的起点列表，或者在 npm 上搜索。 - ccprog

由于我的数学和工程技能较差，尽管我几天前已经阅读了存储库 fourier，但我仍然不知道如何使用它来进行一维快速傅里叶变换...你能否向我展示如何使用它来转换 'sin(x)'？谢谢！ - 邓启凡

我编写了另一个函数来解决这个问题，并且它很好地替换了波浪的尖刺。在这里是代码（你需要在最开始设置正确的两个值）：Array.prototype.smooth = function (strength) { var len = this.length; var dis_arg, dis, dis_sum = 0; for (var i = 0; i < len - 1; i++) { dis_sum += Math.abs((this[i + 1] - this[i])); dis_arg = dis_sum / i; dis = Math.abs(this[i + 1] - this[i]); if (dis / dis_arg > strength) { this[i + 1] = 2 * this[i] - this[i - 1]; } } }; - 邓启凡

Answer 1

如果您愿意，可以自己实现它。这是一个如何在ES6中实现离散傅里叶变换函数的示例：

import ComplexNumber from '../complex-number/ComplexNumber';

const CLOSE_TO_ZERO_THRESHOLD = 1e-10;

/**
 * Discrete Fourier Transform (DFT): time to frequencies.
 *
 * Time complexity: O(N^2)
 *
 * @param {number[]} inputAmplitudes - Input signal amplitudes over time (complex
 * numbers with real parts only).
 * @param {number} zeroThreshold - Threshold that is used to convert real and imaginary numbers
 * to zero in case if they are smaller then this.
 *
 * @return {ComplexNumber[]} - Array of complex number. Each of the number represents the frequency
 * or signal. All signals together will form input signal over discrete time periods. Each signal's
 * complex number has radius (amplitude) and phase (angle) in polar form that describes the signal.
 *
 * @see https://gist.github.com/anonymous/129d477ddb1c8025c9ac
 * @see https://betterexplained.com/articles/an-interactive-guide-to-the-fourier-transform/
 */
export default function dft(inputAmplitudes, zeroThreshold = CLOSE_TO_ZERO_THRESHOLD) {
  const N = inputAmplitudes.length;
  const signals = [];

  // Go through every discrete frequency.
  for (let frequency = 0; frequency < N; frequency += 1) {
    // Compound signal at current frequency that will ultimately
    // take part in forming input amplitudes.
    let frequencySignal = new ComplexNumber();

    // Go through every discrete point in time.
    for (let timer = 0; timer < N; timer += 1) {
      const currentAmplitude = inputAmplitudes[timer];

      // Calculate rotation angle.
      const rotationAngle = -1 * (2 * Math.PI) * frequency * (timer / N);

      // Remember that e^ix = cos(x) + i * sin(x);
      const dataPointContribution = new ComplexNumber({
        re: Math.cos(rotationAngle),
        im: Math.sin(rotationAngle),
      }).multiply(currentAmplitude);

      // Add this data point's contribution.
      frequencySignal = frequencySignal.add(dataPointContribution);
    }

    // Close to zero? You're zero.
    if (Math.abs(frequencySignal.re) < zeroThreshold) {
      frequencySignal.re = 0;
    }

    if (Math.abs(frequencySignal.im) < zeroThreshold) {
      frequencySignal.im = 0;
    }

    // Average contribution at this frequency.
    // The 1/N factor is usually moved to the reverse transform (going from frequencies
    // back to time). This is allowed, though it would be nice to have 1/N in the forward
    // transform since it gives the actual sizes for the time spikes.
    frequencySignal = frequencySignal.divide(N);

    // Add current frequency signal to the list of compound signals.
    signals[frequency] = frequencySignal;
  }

  return signals;
}

这个函数只是直接实现了公式：

该函数速度较慢，时间复杂度为 O(n^2)。如果速度确实很重要，您可以选择使用 快速傅里叶变换:

更多详细描述请参见此处https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/fourier-transform

- Oleksii Trekhleb

Answer 2

我在 Stack Overflow 的另一个帖子中提出了一个建议：Fast Fourier Transform Javascript。
它接受一个一维数组的输入，假设它们是等间距的，并输出 DFT。也许这正是你正在寻找的？

- DavidB2013

---

实际上我正在寻找一个可以像Matlab中的fft()函数一样使用的库。谢谢，我会尝试您的建议。 - 邓启凡