Biblioteca FFT en Android Sdk

Estoy trabajando con un proyecto Android. Necesito el algoritmo FFT para procesar los datos del acelerómetro Android. ¿Hay una biblioteca FFT disponible en Android SDK?

Puedes usar esta clase, que es lo suficientemente rápida para el análisis de audio en tiempo real

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; } } } } } 

Advertencia: este código parece ser derivado de aquí , y tiene una licencia GPLv2.

Usando la clase en: https://www.ee.columbia.edu/~ronw/code/MEAPsoft/doc/html/FFT_8java-source.html

Breve explicación: invoque a fft () proporcionando x como datos de amplitud, y como matriz de todos los ceros, después de que la función devuelva su primera respuesta será a [0] = x [0] ^ 2 + y [0] ^ 2.

Explicación completa: FFT es una transformación compleja, toma N números complejos y produce N números complejos. Entonces x [0] es la parte real del primer número, y [0] es la parte compleja. Esta función se calcula in situ, por lo que cuando la función devuelve x e y tendrá las partes reales y complejas de la transformación.

Un uso típico es calcular el espectro de potencia del audio. Sus muestras de audio solo tienen una parte real, su parte compleja es 0. Para calcular el espectro de potencia, agregue el cuadrado de las partes reales y complejas P [0] = x [0] ^ 2 + y [0] ^ 2.

También es importante notar que la transformada de Fourier, cuando se aplica sobre números reales, da como resultado un resultado simétrico (x [0] == x [x.lenth-1]). Los datos en x [x.length / 2] tienen los datos de la frecuencia f = 0Hz. x [0] == x [x.length-1] tiene los datos para una frecuencia igual a la velocidad de muestreo (por ejemplo, si el muestreo fue 44000Hz de lo que significa f [0] refeers a 22kHz).

Procedimiento completo:

  1. crear una matriz p [n] con 512 muestras con ceros
  2. Recoge 1024 muestras de audio, escríbelas en x
  3. Establezca y [n] = 0 para todo n
  4. calcular fft (x, y)
  5. calcule p [n] + = x [n + 512] ^ 2 + y [n + 512] ^ 2 para todo n = 0 a 512
  6. ir 2 para tomar otro lote (después de 50 lotes ir al siguiente paso)
  7. ttwig p
  8. ir a 1

Luego ajusta el número fijo para tu gusto.

El número 512 define la ventana de muestreo, no lo explicaré. Solo evite reducirlo demasiado.

El número 1024 debe ser siempre el doble del último número.

El número 50 define la tasa de actualización. Si su frecuencia de muestreo es de 44000 muestras por segundo, la tasa de actualización será: R = 44000/1024/50 = 0,85 segundos.

kissfft es una biblioteca lo suficientemente decente que comstack en Android. Tiene una licencia más versátil que FFTW (aunque es cierto que FFTW es mejor).

Puede encontrar un enlace de Android para kissfft en libgdx https://github.com/libgdx/libgdx/blob/0.9.9/extensions/gdx-audio/src/com/badlogic/gdx/audio/analysis/KissFFT.java

O si desea una solución pura basada en Java, intente jTransforms https://sites.google.com/site/piotrwendykier/software/jtransforms

Utilice esta clase (de la que se deriva la respuesta de EricLarch).

Notas de uso

Esta función reemplaza sus matrices de entradas con la salida FFT.

Entrada

  • N = la cantidad de puntos de datos (el tamaño de su matriz de entrada debe ser una potencia de 2)
  • X = la parte real de tus datos a ser transformada
  • Y = la parte imaginaria de los datos a transformar

es decir, si su entrada es (1 + 8i, 2 + 3j, 7-i, -10-3i)

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

Salida

  • X = la parte real de la salida de FFT
  • Y = la parte imaginaria de la salida de FFT

Para obtener su gráfico FFT clásico, querrá calcular la magnitud de las partes real e imaginaria.

Algo como:

 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; } 

Consulte también esta respuesta de StackOverflow sobre cómo obtener frecuencias si su entrada original fue de magnitud frente a tiempo.

@J Wang Tu magnitud de salida parece mejor que la respuesta dada en el hilo que has vinculado pero que sigue siendo de magnitud al cuadrado … la magnitud de un número complejo

 z = a + ib 

se calcula como

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

la respuesta en el hilo enlazado sugiere que para las entradas reales puras las salidas deberían usar un 2 o una para la salida porque los valores para

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

con b_(i) = a_(i+N/2) significa que la parte compleja en su tabla se encuentra en la segunda mitad de la tabla de resultados.

es decir, la segunda mitad de la tabla de salida para una tabla de entrada de reales es el conjugado de la real …

entonces z = a-ia dando una magnitud

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

por lo tanto, vale la pena señalar los factores de escala … Recomendaría buscar todo esto en un libro o en una wiki para estar seguro.