БПФ библиотека в Android Sdk

Question

Я работаю с проектом Android. Мне нужен алгоритм FFT для обработки данных акселерометра Android. Есть ли библиотека FFT в Android SDK?

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 = 0 Гц.x [0] == x [x.length-1] содержит данные для частоты, равной частоте дискретизации (например, если частота дискретизации была 44000 Гц, это означает, что f [0] относится к 22 кГц).

Полная процедура:

1. создать массив p [n] с 512 сэмплами с нулями
2. Собрать 1024 сэмпла, записать их в x
3. Установить y [n]= 0 для всех n
4. вычислить fft (x, y)
5. вычислить p [n] + = x [n + 512] ^ 2 + y [n + 512] ^ 2 для всехn = от 0 до 512
6. , чтобы перейти к 2, чтобы взять другую партию (после 50 партий перейти к следующему шагу)
7. сюжет p
8. перейти к 1

Чем настроить фиксированное число на свой вкус.

Число 512 определяет окно выборки, я не буду его объяснять.Просто не уменьшайте его слишком сильно.

Число 1024 всегда должно быть двойным от последнего числа.

Число 50 определяет частоту обновления.Если ваша частота дискретизации составляет 44000 выборок в секунду, частота обновления будет равна: R = 44000/1024/50 = 0,85 секунды.

Answer 3

kissfft - достаточно приличная библиотека, которая компилируется на Android. У него более универсальная лицензия, чем у FFTW (хотя, по общему признанию, FFTW лучше).

Вы можете найти привязку андроида для kissfft в libgdx 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)

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

Вывод

• X = действительная часть вывода БПФ
• Y = мнимая часть вывода БПФ

ПолучитьВаш классический график БПФ, вы хотите рассчитать величину действительной и мнимой частей.

Что-то вроде:

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 для получения информации о том, как получить частоты, если ваш исходный вход был величиной по времени.

Answer 5

@ Дж Ван Ваша выходная величина кажется лучше, чем ответ, данный в цепочке, которую вы связали, однако она по-прежнему равна квадрату величины ... величина комплексного числа

z = a + ib

рассчитывается как

|z|=sqrt(a^2+b^2)

ответ в связанной ветке говорит о том, что для чисто реальных входов выходы следует использовать a ² или a для вывода, поскольку значения для

a_(i+N/2) = -a_(i),

с b_(i) = a_(i+N/2) означает, что сложная часть в их таблице находится во втором половина выходной таблицы.

т.е. во второй половине выходной таблицы для входной таблицы вещественных чисел есть сопряжение действительного ...

так z = a-ia дает величину

|z|=sqrt(2a^2) = sqrt(2)a

так что стоит отметить коэффициенты масштабирования ... Я бы порекомендовал посмотреть все это в книге или на вики, чтобы быть уверенным.

Answer 6

Да, есть JTransforms, который поддерживается на github здесь и доступен как Maven плагин здесь .

Использовать с:

compile group: 'com.github.wendykierp', name: 'JTransforms', version: '3.1'

Но в более поздних версиях Gradle вам нужно использовать что-то вроде:

dependencies {
    ... 
    implementation 'com.github.wendykierp:JTransforms:3.1'
}