android Sdk中的FFT库

Question

我正在使用android项目.我需要FFT算法来处理android加速度计数据.在android sdk中有FFT库吗？

Answer 1

您可以使用此类,该类足够快,可用于实时音频分析

public class FFT {

  int n, m;

  // Lookup tables. Only need to recompute when size of FFT changes.
  double[] cos;
  double[] sin;

  public FFT(int n) {
      this.n = n;
      this.m = (int) (Math.log(n) / Math.log(2));

      // Make sure n is a power of 2
      if (n != (1 << m))
          throw new RuntimeException("FFT length must be power of 2");

      // precompute tables
      cos = new double[n / 2];
      sin = new double[n / 2];

      for (int i = 0; i < n / 2; i++) {
          cos[i] = Math.cos(-2 * Math.PI * i / n);
          sin[i] = Math.sin(-2 * Math.PI * i / n);
      }

  }

  public void fft(double[] x, double[] y) {
      int i, j, k, n1, n2, a;
      double c, s, t1, t2;

      // Bit-reverse
      j = 0;
      n2 = n / 2;
      for (i = 1; i < n - 1; i++) {
          n1 = n2;
          while (j >= n1) {
              j = j - n1;
              n1 = n1 / 2;
          }
          j = j + n1;

          if (i < j) {
              t1 = x[i];
              x[i] = x[j];
              x[j] = t1;
              t1 = y[i];
              y[i] = y[j];
              y[j] = t1;
          }
      }

      // FFT
      n1 = 0;
      n2 = 1;

      for (i = 0; i < m; i++) {
          n1 = n2;
          n2 = n2 + n2;
          a = 0;

          for (j = 0; j < n1; j++) {
              c = cos[a];
              s = sin[a];
              a += 1 << (m - i - 1);

              for (k = j; k < n; k = k + n2) {
                  t1 = c * x[k + n1] - s * y[k + n1];
                  t2 = s * x[k + n1] + c * y[k + n1];
                  x[k + n1] = x[k] - t1;
                  y[k + n1] = y[k] - t2;
                  x[k] = x[k] + t1;
                  y[k] = y[k] + t2;
              }
          }
      }
  }
}

警告:此代码似乎来自此处,并具有GPLv2许可证.

Answer 2

使用以下课程:https://www.ee.columbia.edu/~ronw/code/MEAPsoft/doc/html/FFT_8java-source.html

简短说明:调用fft()提供x作为振幅数据,y作为全零数组,在函数返回第一个答案后将是[0] = x [0] ^ 2 + y [0] ^ 2.

完整说明:FFT是复数变换,它需要N个复数并产生N个复数.所以x [0]是第一个数字的实部,y [0]是复数部分.此函数就地计算,因此当函数返回x时,y将具有变换的实部和复杂部分.

一种典型用法是计算音频的功率谱.您的音频样本只有实部,您的复杂部分是0.要计算功率谱,可以添加实部和复数部分的平方P [0] = x [0] ^ 2 + y [0] ^ 2.

另外重要的是要注意傅立叶变换,当应用于实数时,会产生对称结果(x [0] == x [x.lenth-1]).x [x.length/2]处的数据具有来自频率f = 0Hz的数据.x [0] == x [x.length-1]的频率数据等于采样率(例如,如果您采样的是44000Hz,则意味着f [0]反馈到22kHz).

完整程序:

1. 使用零创建512个样本的数组p [n]
2. 收集1024个音频样本,将其写在x上
3. 为所有n设置y [n] = 0
4. 计算fft(x,y)
5. 对于所有n = 0到512,计算p [n] + = x [n + 512] ^ 2 + y [n + 512] ^ 2
6. 去2再采取另一批(50批次后进入下一步)
7. 情节
8. 去1

比调整固定数量为您的口味.

数字512定义了采样窗口,我不会解释它.只是避免过多减少它.

数字1024必须始终是最后一个数字的两倍.

数字50定义了更新率.如果您的采样率是每秒44000个样本,则更新率将为:R = 44000/1024/50 = 0.85秒.

Answer 3

kissfft是一个足够体面的库,可以在android上编译.它具有比FFTW更通用的许可证(即使FFTW无疑更好).

你可以在libgdx中找到一个用于kissfft的android绑定https://github.com/libgdx/libgdx/blob/0.9.9/extensions/gdx-audio/src/com/badlogic/gdx/audio/analysis/KissFFT.java

或者,如果您想要基于纯Java的解决方案,请尝试使用jTransforms https://sites.google.com/site/piotrwendykier/software/jtransforms

Answer 4

使用此类（ EricLarch 的答案源自该类）。

使用说明

此函数将输入数组替换为 FFT 输出。

输入

• N = 数据点的数量（输入数组的大小，必须是 2 的幂）
• X = 要转换的数据的实部
• Y = 要转换的数据的虚部

即如果您的输入是 (1+8i, 2+3j, 7-i, -10-3i)

• 数 = 4
• X = (1, 2, 7, -10)
• Y = (8, 3, -1, -3)

输出

• X = FFT 输出的实部
• Y = FFT 输出的虚部

要获得经典的 FFT 图，您需要计算实部和虚部的大小。

就像是：

public double[] fftCalculator(double[] re, double[] im) {
    if (re.length != im.length) return null;
    FFT fft = new FFT(re.length);
    fft.fft(re, im);
    double[] fftMag = new double[re.length];
    for (int i = 0; i < re.length; i++) {
       fftMag[i] = Math.pow(re[i], 2) + Math.pow(im[i], 2);
    }
    return fftMag;
}

另请参阅StackOverflow 答案，了解如果原始输入是幅度与时间的关系如何获取频率。