4. freie 2D FFT Referenzimplementierung in C++?

freie 2D FFT Referenzimplementierung in C++?

  • C

    Ja, die optimierten sind wunderbar für die Geschwindigkeit, aber leider auch schwer zu verstehen, wenn es ums Lernen geht. Wenn es nach Speed geht, da habe ich auch schon die FFTW gefunden. Ich werde mein Progrämmchen so gestalten, dass ich meine Lernroutinen später recht einfach durch externe Libs austauschen kann, falls ich wirklich mal das Projekt dann weiter machen will.

    Ist ja alles nur zum Lernen und ich werde da auch ganz viele Fehler machen, aber die Erfahrungen sind dann auf jeden Fall die Sache wert.

    0

  • Und FT ohne "fast" tut's nicht?
    Die sollte man sich in 5~50 Min. aus dem Wikipediaartikel zur FT selbst schreiben können.
    Die Variante ist dann halt wirklich schön langsam, dafür versteht man dann was ne FT überhaupt macht.

    0
  • R
    Mod

    wenn man FFT lernen will, wird man es mittels 'nur' FT nicht.

    ich empfehle:
    http://www.drdobbs.com/cpp/a-simple-and-efficient-fft-implementatio/199500857

    0
  • ?

    Danke für den Artikel, gute Auffrischung und der Template-Ansatz sehr interessant!

    0
  • C

    Schaut nicht schlecht aus und ja ich könnte es auch erst mal mit der normalen Transformation ohne Optimierung durch Zwischenspeichern und Teile und Herrsche versuchen.

    0

  • rapso schrieb:

    wenn man FFT lernen will, wird man es mittels 'nur' FT nicht.

    Klar. Aber für die die nicht wissen was ne FT überhaupt macht, ist es denke ich ne gute Grundlage.
    Wie soll man denn verstehen warum man nen bestimmten Algorithmus auf eine bestimmte Art und Weise optimieren kann, wenn man nichtmal weiss was der Algorithmus überhaupt macht?

    0
  • C

    Der genaue mathematische Hintergrund ist mir bis jetzt verborgen geblieben. Ich weiß nur, dass die Bildinformationen(Pixel) von ihrem System der Positionen(X,Y) in ein System von Frequenzanteilen von Sin/Cos Schwingungen transformiert werden. Da spielt dann wohl noch Einheitswurzeln eine Rolle, bis man auf die endgültige Formeln kommt, aber mehr habe ich auch nicht verstanden.

    Wenn man seine Daten transformiert hat, kann man halt viel einfacher auf Frequenzbasis filtern und arbeiten. Nach dem die Arbeit getan ist, wird wieder in das ursprüngliche System mit den Positionen zurück transformiert.

    Bei dem gesamten Vorgehen wird noch beachtet, dass es sich um diskrete Werte handelt, weswegen dass dann auch DFT heißt.

    Die schnellere Variante müsste auch eigentlich FDFT heißen, da auch hier mit diskreten Werten gearbeitet wird. Bei dieser Art der Transformation wird ein bestimmte Fenstergröße vorausgesetzt die auf 2er Potenzen basiert. Hat man solche Datengröße nicht, so muss man mit Nullen auffüllen oder wiederholen. Dabei muss man beachten, dass man bei einem Rechteckfenster Sprünge drin haben kann, die sich als hohe Frequenzen zeigen, weswegen man gerne auch nichtlineare Fenster wählt.

    Das ist jetzt das, was ich aus dem Stehreif weiß. Vielleicht kann mir jemand sagen, falls ich hier kompletten Unsinn geschrieben habe und es verbessern. Ich bin weder Mathematiker noch Informatiker, sondern nur ein alter Selfmade-Programmierer mit Festeinstellung in PHP.

    0
  • Mod

    Wieso brauchst du dann eine C++-Referenzimplementierung? Das erschließt sich mir irgendwie nicht.

    Das "diskret" bezieht sich übrigens auf den Definitionsbereich, nicht die Werte.

    0
  • C

    Einfach mal um zu schauen wie so etwas umgesetzt wird und um dann die Werte mit meiner eigenen Implementierung zu vergleichen. Daher sollte diese "Referenzimplementierung" auch nicht groß optimiert sein, da man dann IMHO schlechter als Anfänger durch blickt. Also alles nur zu Lernzwecken, für einen produktiven Einsatz würde ich dann so etwas wie FFTW nehmen.

    0
  • Mod

    Was ist denn beispielsweise mit den Implementierungen hier:
    http://rosettacode.org/wiki/Fast_Fourier_transform#C.2B.2B
    Ganz, ganz einfach gehalten, ohne jede Optimierung (und numerisch grauenhaft ungenau 🙂 ). Die C++-Variante ist sogar recht elegant mit den valarrays geschrieben. Oder wenn du es noch eine weitere Stufe naiver möchtest, dann steht doch in Wikipedia schon Pseudocode, den man ebenfalls mal auf die schnelle in C++ hacken kann:

    template<typename InputIterator, typename OutputIterator> void SFFT_1D // Slow fast Fourier transform :-p
(InputIterator in, OutputIterator out, std::size_t N, std::size_t s = 1)
{
  typedef typename std::iterator_traits<OutputIterator>::value_type Complex;
  const double PI = 3.14159265359;

  if (N==1)
    *out = *in;
  else
    {
      SFFT_1D(in, out, N/2, 2*s);
      SFFT_1D(in + s, out + N/2, N/2, 2*s);
      for(size_t k = 0; k < N/2; ++k)
        {
          Complex t = out[k];
          Complex e = std::polar(1., -2*PI*k/N)*out[k+N/2];
          out[k] =  t + e;
          out[k+N/2] = t - e;
        }
    }
};

    Ist zwar alles 1D, aber die 2D-Transformation separiert man dann ganz einfach in 1D-Transformationen. Mag zwar bei hochoptimierten Varianten einen besseren Weg geben, aber das wäre dann ebenfalls der naive, einfach verständliche Weg. Das vorzumachen, erspar ich mir mal.

    So, nix neues gelernt, nicht einmal zu googeln, aber nun kannst du deine Hausaufgaben endlich abschreiben 🙄 .

    0
  • C

    Besten Dank, aber von welchen Hausaufgaben redest du?

    0
Anmelden zum Antworten