Zuverlässige und schnelle FFT in Java

Question

Da ich es nicht alleine machen will, suche ich nach einer guten FFT-Implementierung für Java. Zuerst benutzte ich dieses hier FFT Princeton, aber es verwendet Objekte und mein Profiler sagte mir, dass es nicht wirklich schnell aufgrund dieser Tatsache ist. Also habe ich nochmal gegoogelt und dieses gefunden: FFT Columbia was schneller ist. Vielleicht kennt einer von euch eine andere FFT-Implementierung? Ich hätte gerne den "besten", weil meine App eine riesige Menge an Sounddaten verarbeiten muss und die Nutzer nicht gerne warten ... ;-)

Grüße.

Answer 1

FFTW ist die 'schnellste fourier im Westen verwandeln', und hat einige Java-Wrapper:

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

Hoffnung, das hilft!

Answer 2

Ich bin in der Verwendung von SSTJ für FFTs in Java suchen. Es kann über JNI zu FFTW umleiten, wenn die Bibliothek verfügbar ist, oder eine reine Java-Implementierung verwenden, wenn nicht.

Answer 3

Spät zur Party - hier als reine Java-Lösung für diejenigen, wenn JNI keine Option ist. JTransforms

Answer 4

Ich schrieb eine Funktion für die FFT in Java: http://www.wikijava.org/wiki/The_Fast_Fourier_Transform_in_Java_%28part_1%29

Es ist in der Public Domain, so dass Sie diese Funktionen überall (auch persönliche oder Business-Projekte) nutzen können. Nenne mich einfach im Abspann und sende mir nur einen Link von deiner Arbeit, und du bist in Ordnung.

Es ist absolut zuverlässig. Ich habe seine Ausgabe gegen die FFT der Mathematica geprüft und sie waren immer korrekt bis zur 15. Dezimalziffer. Ich denke, es ist eine sehr gute FFT-Implementierung für Java. Ich schrieb es auf der Version J2SE 1.6 und testete es auf der Version J2SE 1.5-1.6.

Wenn Sie die Anzahl der Anweisungen zählen (es ist viel einfacher als eine perfekte computational complexity Funktion Schätzung), können Sie deutlich sehen, dass diese Version groß ist, auch wenn es überhaupt nicht optimiert ist. Ich plane, die optimierte Version zu veröffentlichen, wenn genug Anfragen vorliegen.

Lassen Sie mich wissen, wenn es nützlich war, und sagen Sie mir einen Kommentar, den Sie mögen.

Ich teile den gleichen Code hier:

/** 
* @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

Ich denke, es hängt davon ab, was Sie verarbeiten. Wenn Sie die FFT über einen längeren Zeitraum berechnen, können Sie feststellen, dass es eine Weile dauert, abhängig davon, wie viele Frequenzpunkte Sie wünschen. In den meisten Fällen für Audio wird es jedoch als nicht stationär betrachtet (dh die Signale bedeuten und die Varianz ändert sich zu viel im Laufe der Zeit), so dass eine große FFT (Periodogram PSD Schätzung) keine genaue Darstellung ist. Alternativ können Sie die Kurzzeit-Fourier-Transformation verwenden, wobei Sie das Signal in kleinere Frames zerlegen und die FFT berechnen. Die Framegröße variiert je nachdem, wie schnell sich die Statistik ändert, für Sprache beträgt sie normalerweise 20-40ms, für Musik nehme ich an, dass sie etwas höher ist.

Diese Methode ist gut, wenn Sie vom Mikrofon abtasten, da Sie damit jeden Rahmen einzeln puffern, das fft berechnen und dem Benutzer das geben können, was der Benutzer als "Echtzeit" -Interaktion empfindet. Weil 20ms schnell sind, weil wir einen so kleinen Zeitunterschied nicht wirklich wahrnehmen können.

Ich entwickelte eine kleine Benchmark, um den Unterschied zwischen FFTW und KissFFT c-Bibliotheken auf einem Sprachsignal zu testen. Ja FFTW ist stark optimiert, aber wenn Sie nur kurze Frames verwenden, die Daten für den Benutzer aktualisieren und nur eine kleine Größe verwenden, sind beide sehr ähnlich. Hier ist ein Beispiel, wie man das KissFFT libraries in Android mit LibGdx von Badlogic Spielen implementiert. Ich implementierte diese Bibliothek mit überlappenden Frames in einer Android App, die ich vor ein paar Monaten mit dem Namen Speech Enhancement for Android entwickelt habe.