FFT affidabile e veloce in Java

Question

poiché non voglio farlo da solo, sto cercando una buona implementazione FFT per java. Prima ho usato questo qui FFT Princeton ma usa oggetti e il mio profiler mi ha detto che non è molto veloce a causa di questo fatto. Così ho cercato nuovamente su Google e ho trovato questo: FFT Columbia che è più veloce. Forse qualcuno di voi conosce un'altra implementazione FFT? Mi piacerebbe avere il "migliore" perché la mia app deve elaborare una quantità enorme di dati audio, e agli utenti non piace aspettare ... ;-)

Cordiali saluti.

Answer 1

FFTW è il 'Fourier veloce trasforma in Occidente', e ha alcuni wrapper Java:

http://www.fftw.org/download.html

Speranza che aiuta!

Answer 2

Sto cercando di utilizzare SSTJ per FFT in Java. Può reindirizzare tramite JNI a FFTW se la libreria è disponibile o se non utilizzerà un'implementazione Java pura.

Answer 3

In ritardo per la festa - qui come pura soluzione java per quelli in cui JNI non è un'opzione. JTransforms

Answer 4

Ho scritto una funzione per la FFT in Java: http://www.wikijava.org/wiki/The_Fast_Fourier_Transform_in_Java_%28part_1%29

E 'nel pubblico dominio in modo da poter utilizzare tali funzioni in tutto il mondo (progetti personali o aziendali troppo). Basta citarmi nei titoli di coda e mandarmi solo un link del tuo lavoro, e tu stai bene.

È completamente affidabile. Ho controllato il suo output contro la FFT di Mathematica e sono sempre stati corretti fino alla 15 ° cifra decimale. Penso che sia un'implementazione FFT molto buona per Java. L'ho scritto sulla versione 1.6 di J2SE e l'ho testato sulla versione 1.5-2.6 di J2SE.

Se si conta il numero di istruzioni (è molto più semplice di una stima della funzione di complessità computazionale perfetta) si può chiaramente vedere che questa versione è ottima anche se non è ottimizzata affatto. Sto pianificando di pubblicare la versione ottimizzata se ci sono abbastanza richieste.

Fammi sapere se è stato utile e segnalami eventuali commenti che ti piacciono.

condivido lo stesso codice proprio qui:

/** 
* @author Orlando Selenu 
* 
*/ 
public class FFTbase { 
/** 
* The Fast Fourier Transform (generic version, with NO optimizations). 
* 
* @param inputReal 
*   an array of length n, the real part 
* @param inputImag 
*   an array of length n, the imaginary part 
* @param DIRECT 
*   TRUE = direct transform, FALSE = inverse transform 
* @return a new array of length 2n 
*/ 
public static double[] fft(final double[] inputReal, double[] inputImag, 
          boolean DIRECT) { 
    // - n is the dimension of the problem 
    // - nu is its logarithm in base e 
    int n = inputReal.length; 

    // If n is a power of 2, then ld is an integer (_without_ decimals) 
    double ld = Math.log(n)/Math.log(2.0); 

    // Here I check if n is a power of 2. If exist decimals in ld, I quit 
    // from the function returning null. 
    if (((int) ld) - ld != 0) { 
     System.out.println("The number of elements is not a power of 2."); 
     return null; 
    } 

    // Declaration and initialization of the variables 
    // ld should be an integer, actually, so I don't lose any information in 
    // the cast 
    int nu = (int) ld; 
    int n2 = n/2; 
    int nu1 = nu - 1; 
    double[] xReal = new double[n]; 
    double[] xImag = new double[n]; 
    double tReal, tImag, p, arg, c, s; 

    // Here I check if I'm going to do the direct transform or the inverse 
    // transform. 
    double constant; 
    if (DIRECT) 
     constant = -2 * Math.PI; 
    else 
     constant = 2 * Math.PI; 

    // I don't want to overwrite the input arrays, so here I copy them. This 
    // choice adds \Theta(2n) to the complexity. 
    for (int i = 0; i < n; i++) { 
     xReal[i] = inputReal[i]; 
     xImag[i] = inputImag[i]; 
    } 

    // First phase - calculation 
    int k = 0; 
    for (int l = 1; l <= nu; l++) { 
     while (k < n) { 
      for (int i = 1; i <= n2; i++) { 
       p = bitreverseReference(k >> nu1, nu); 
       // direct FFT or inverse FFT 
       arg = constant * p/n; 
       c = Math.cos(arg); 
       s = Math.sin(arg); 
       tReal = xReal[k + n2] * c + xImag[k + n2] * s; 
       tImag = xImag[k + n2] * c - xReal[k + n2] * s; 
       xReal[k + n2] = xReal[k] - tReal; 
       xImag[k + n2] = xImag[k] - tImag; 
       xReal[k] += tReal; 
       xImag[k] += tImag; 
       k++; 
      } 
      k += n2; 
     } 
     k = 0; 
     nu1--; 
     n2 /= 2; 
    } 

    // Second phase - recombination 
    k = 0; 
    int r; 
    while (k < n) { 
     r = bitreverseReference(k, nu); 
     if (r > k) { 
      tReal = xReal[k]; 
      tImag = xImag[k]; 
      xReal[k] = xReal[r]; 
      xImag[k] = xImag[r]; 
      xReal[r] = tReal; 
      xImag[r] = tImag; 
     } 
     k++; 
    } 

    // Here I have to mix xReal and xImag to have an array (yes, it should 
    // be possible to do this stuff in the earlier parts of the code, but 
    // it's here to readibility). 
    double[] newArray = new double[xReal.length * 2]; 
    double radice = 1/Math.sqrt(n); 
    for (int i = 0; i < newArray.length; i += 2) { 
     int i2 = i/2; 
     // I used Stephen Wolfram's Mathematica as a reference so I'm going 
     // to normalize the output while I'm copying the elements. 
     newArray[i] = xReal[i2] * radice; 
     newArray[i + 1] = xImag[i2] * radice; 
    } 
    return newArray; 
} 

/** 
* The reference bitreverse function. 
*/ 
private static int bitreverseReference(int j, int nu) { 
    int j2; 
    int j1 = j; 
    int k = 0; 
    for (int i = 1; i <= nu; i++) { 
     j2 = j1/2; 
     k = 2 * k + j1 - 2 * j2; 
     j1 = j2; 
    } 
    return k; 
    } 
} 

Answer 5

Immagino che dipende da quello che si sta elaborando. Se stai calcolando la FFT per un lungo periodo potresti scoprire che ci vuole un po 'di tempo a seconda di quanti punti di frequenza desideri. Tuttavia, nella maggior parte dei casi per l'audio è considerato non stazionario (cioè la media dei segnali e la varianza cambia molto nel tempo), quindi prendere una FFT grande (stima Periodogram PSD) non è una rappresentazione accurata. In alternativa, è possibile utilizzare la trasformata di Fourier a breve termine, in modo da suddividere il segnale in fotogrammi più piccoli e calcolare la FFT. La dimensione del fotogramma varia a seconda della velocità con cui le statistiche cambiano, per il parlato di solito è di 20-40 ms, per la musica presumo che sia leggermente più alto.

Questo metodo è valido se si esegue il campionamento dal microfono, poiché consente di memorizzare ogni fotogramma su ciascun fotogramma alla volta, calcolare il valore fft e fornire ciò che l'utente percepisce come interazione "in tempo reale". Perché 20 ms è veloce, perché non possiamo davvero percepire una differenza di tempo così piccola.

Ho sviluppato un piccolo benchmark per testare la differenza tra le librerie c FFTW e KissFFT su un segnale vocale. Sì, FFTW è altamente ottimizzato, ma quando si utilizzano solo i cortocircuiti, l'aggiornamento dei dati per l'utente e l'utilizzo di una piccola dimensione fft, sono entrambi molto simili. Ecco un esempio su come implementare lo KissFFT libraries in Android usando LibGdx dai giochi badlogic. Ho implementato questa libreria utilizzando frame sovrapposti in un'app Android che ho sviluppato alcuni mesi fa, denominata Speech Enhancement for Android.