FFTW und Faltung



  • Hallo,

    ich versuchte mittels FFTW Lib. Bilder in den Frequenzraum zu bringen und dort weiterzuverarbeiten. Ich will eine Faltung im Frequenzbereich berechnen. Nun stellt sich die Frage wie das geht. Das Bild hat 386 mal 559 Pixel und die Filter maske nur 5x5 Pixel. Wie kann ich also meinen Filter auf das Format des Bildes bringen?

    Hoffe es kann mir wer weiterhelfen!

    LG



  • Dieser Thread wurde von Moderator/in SeppJ aus dem Forum C++ (auch C++0x) in das Forum Rund um die Programmierung verschoben.

    Im Zweifelsfall bitte auch folgende Hinweise beachten:
    C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

    Dieses Posting wurde automatisch erzeugt.



  • Pheeenix schrieb:

    Wie kann ich also meinen Filter auf das Format des Bildes bringen?

    Das hängt davon ab, was mit den Fourier-Koeffizienten außerhalb der Filtermaske geschehen soll.



  • Wie ist der Filter denn zustande gekommen? Für mich klingt das so, als wenn der Filter im Zeitbereich vorliegt. Wenn dem so ist, dann transformiere ihn ebenfalls mit der gleichen FT-Länge. Die fehlenden Wert kannst Du durch Zeropadding auffüllen. Damit das Ganze dann energieneutral bleibt, musst Du für die eingefügten Nullen noch den passenden Faktor in den transformierten Filter multiplizieren.



  • Pheeenix schrieb:

    ich versuchte mittels FFTW Lib. Bilder in den Frequenzraum zu bringen und dort weiterzuverarbeiten. Ich will eine Faltung im Frequenzbereich berechnen. Nun stellt sich die Frage wie das geht. Das Bild hat 386 mal 559 Pixel und die Filter maske nur 5x5 Pixel. Wie kann ich also meinen Filter auf das Format des Bildes bringen?

    Zero-Padding.

    Das Faltungsergebnis liefert Dir ein Bild mit (386+5-1=390) x (559+5-1=563) Pixeln. Die "FFT-Größe" muss also mindestens 390x563 sein, damit der sogenannte "Wrap-Around-Fehler" vermieden wird; denn die Multiplikation zweier Spektren, die man über eine diskrete Fourier-Transformation bekommen hat, entspricht einer zirkularen Faltung. Da die FFT-Algorithmen besonders gut funktionieren, wenn die Größen sich aus kleinen Primfaktoren zusammensetzen, solltest Du hier statt 390x563 so etwas wie 416x576 oder so benutzen.

    Beide Signale füllst Du entsprechend mit Nullen auf, so dass diese Größe erreicht wird, berechnest die komplexwertigen Spektren. Dann multiplizierst Du die Spektren (komplexe Multiplikation!) und auf dem Ergebnis wendest Du die inverse FFT an.

    Falls allerdings Deine Maske separierbar ist -- also in zwei Filter zerlegbar ist, wobei der eine nur in X-Richtung arbeitet und der andere nur in Y-Richtung arbeitet, wird's sehr wahrscheinlich ohne FFT schneller gehen, bei solchen "kleinen" Masken.



  • krümelkacker schrieb:

    [...]damit der sogenannte "Wrap-Around-Fehler" vermieden wird; denn die Multiplikation zweier Spektren, die man über eine diskrete Fourier-Transformation bekommen hat, entspricht einer zirkularen Faltung.

    Das gilt aber nur, wenn man eine zeitliche Folge von Samples in Blöcken verarbeitet. Das ist, so wie ich das hier verstanden habe, nicht der Fall. Es gibt ja keine Historie, (also ein X[k-5] vom vorherigen Block), sondern es wird das ganze Bild transformiert.

    krümelkacker schrieb:

    [...]Da die FFT-Algorithmen besonders gut funktionieren, wenn die Größen sich aus kleinen Primfaktoren zusammensetzen, solltest Du hier statt 390x563 so etwas wie 416x576 oder so benutzen.[...]

    Welche Primfaktoren verwendet werden dürfen, hängt vom zugrundeliegenden Algorithmus ab. Typisch ist eigentlich der Radix2 Algorithmus. Bei dem ist nur 2 als Primfaktor erlaubt. Die Primfaktor FFT wird nicht sehr oft in Bibliotheken angeboten. Für Deine Längen bräuchte man die aber. Keine Ahnung, ob FFTW das kann.



  • Tachyon schrieb:

    krümelkacker schrieb:

    [...]damit der sogenannte "Wrap-Around-Fehler" vermieden wird; denn die Multiplikation zweier Spektren, die man über eine diskrete Fourier-Transformation bekommen hat, entspricht einer zirkularen Faltung.

    Das gilt aber nur, wenn man eine zeitliche Folge von Samples in Blöcken verarbeitet.

    Das gilt immer. Multiplikation der diskreten "FFT-Spektren" = zirkulare Faltung. Immer.

    Tachyon schrieb:

    Das ist, so wie ich das hier verstanden habe, nicht der Fall. Es gibt ja keine Historie, (also ein X[k-5] vom vorherigen Block), sondern es wird das ganze Bild transformiert.

    ...was man eigentlich vermeiden kann, wenn man es in Teilbilder zerlegen kann. Irgendwann ist das auch eine Cache-Frage mit der Blockgröße etc...

    Tachyon schrieb:

    krümelkacker schrieb:

    [...]Da die FFT-Algorithmen besonders gut funktionieren, wenn die Größen sich aus kleinen Primfaktoren zusammensetzen, solltest Du hier statt 390x563 so etwas wie 416x576 oder so benutzen.[...]

    Welche Primfaktoren verwendet werden dürfen, hängt vom zugrundeliegenden Algorithmus ab. [...] Keine Ahnung, ob FFTW das kann.

    Die FFTW Lib kommt mit Primfaktoren 2,3,5 wunderbar klar.



  • Danke schon mal für die vielen Antworten, habt mir sehr weitergeholfen.

    was ich allerdings noch nicht herausgefunden habe ist, wie ich mit der fftw Lib. so ein zeropadding ausführen kann damit mein Faltungskern die selbe Größe als das Bild hat mit dem im Fequenzbereich gefaltet werden soll.

    ich hab mir zwar schon einige Tutorials angeschaut, bekomms aber irgendwie nicht hin 😞

    bitte um hilfe



  • Zeropadding machst Du selbst. Die FFTW Lib weiß davon nichts.

    Beispiel in 1D:

    Original:         [4 1 2]
    nach Zeropadding: [4 1 2 0 0 0 0 0]
    

    so einfach ist das.



  • krümelkacker schrieb:

    Tachyon schrieb:

    krümelkacker schrieb:

    [...]damit der sogenannte "Wrap-Around-Fehler" vermieden wird; denn die Multiplikation zweier Spektren, die man über eine diskrete Fourier-Transformation bekommen hat, entspricht einer zirkularen Faltung.

    Das gilt aber nur, wenn man eine zeitliche Folge von Samples in Blöcken verarbeitet.

    Das gilt immer. Multiplikation der diskreten "FFT-Spektren" = zirkulare Faltung. Immer.

    Meine Aussage bezog sich nicht auf die zirkuläre Faltung sondern auf die Notwendigkeit der Überlappung. Da Du selbst vorgeschlagen hast,das Ausgangsmaterial nicht in Teilfolgen zu zerlegen (was bei der bei diesem Problem aufkommenden Datenmenge auch nicht notwendig sein sollte), ist auch keine Überlappung notwendig. Da keine negativen Pixel Indizes vorhanden sind, gibt es auch nichts (außer Nullen) mit dem man Überlappen kann.
    Aperiodische Faltung ist nicht notwendig, wenn man einen Ausschnitt in seiner Gesamtheit behandelt. Dabei gibt es ja keinen "Wrap-Around".

    krümelkacker schrieb:

    Tachyon schrieb:

    Das ist, so wie ich das hier verstanden habe, nicht der Fall. Es gibt ja keine Historie, (also ein X[k-5] vom vorherigen Block), sondern es wird das ganze Bild transformiert.

    ...was man eigentlich vermeiden kann, wenn man es in Teilbilder zerlegen kann. Irgendwann ist das auch eine Cache-Frage mit der Blockgröße etc...

    Bei den Dimensionen wie gesagt mit Sicherheit kein Problem. Allerdings dürfte man da auch mit einer Faltung im Zeitbereich besser bedient sein, als mit einer Multiplikation im Frequenzbereich.



  • Danke für die Infos, ihr habt mir schon sehr geholfen.

    ich habe jetzt mittels zero padding meine maske angepasst und maske + bild mittels fft gewadelt.

    wie kannich nach dem wandeln in den Frequenzbereich punktweise multiplizieren oder dividieren? um eine Faltung bzw. inverse Faltung zu testen.

    Ich habe zwei pläne erstellt

    fftw_complex *in, *out;
    fftw_complex *inp2dpic, *outp2dpic;
    
    fftw_plan p2d;
    fftw_plan p2dpic;
    
    //alloc...
    //...
    
    p2d = fftw_plan_dft_2d(386,559,in,out,FFTW_FORWARD,FFTW_ESTIMATE); % Filter
    p2dpic = fftw_plan_dft_2d(386,559,inp2dpic,outp2dpic,FFTW_FORWARD,FFTW_ESTIMATE); % Bild
    
    //inputs für fft mit daten belegen
    for(int i = 0; i < 386* 559; i++){ 
      in[i][0] = dkernelpadded[i];  //kernel
      in[i][1] = 0;	
    }
    
    for(int i = 0; i < (386*559); i++){ 
      inp2dpic[i][0] = imgBuf1[i];   //Bild
      inp2dpic[i][1] = 0;
    }
    
    //FFT ausführen
    fftw_execute(p2d);						
    fftw_execute(p2dpic);
    
    //wie muss diese Mult erfolgen, da es sich bei den out daten ja um x[][] arrays 
    //handelt welche Realteil bzw. Imaginärteil enthalten.
    for(int i = 0; i < (386*559); i++){
      Faltung = out[i] * outoutp2dpic[i];
    
    }
    

    Wie muss ich nun meine Ausgangsdaten multiplizieren bzw. dividieren um eine Faltung bzw. inverse Faltung in richtiger Weise zu erhalten?

    (sorry für die blöden fragen, aber ich bin ein kompletter Anfänger)

    lg





  • Tachyon schrieb:

    Aperiodische Faltung ist nicht notwendig, wenn man einen Ausschnitt in seiner Gesamtheit behandelt. Dabei gibt es ja keinen "Wrap-Around".

    Aber sicher gibt es den. Wenn die Impulsantwort des Filters

    0 0 0 0 0
    0 0 0 0 0
    0 0 0 0 1
    0 0 0 0 0
    0 0 0 0 0
    

    ist (wobei die Mitte einer Nullverschiebung entspricht) dann verschiebt sich das Bild zwei Pixel nach rechts und die rechten zwei Pixelspalten des ursprünglichen Bilds werden links im neuen Bild wieder auftauchen.

    Tachyon schrieb:

    Allerdings dürfte man da auch mit einer Faltung im Zeitbereich besser bedient sein, als mit einer Multiplikation im Frequenzbereich.

    Die Zeit gibt's hier nicht. :p
    Wir haben hier Raumdomäne <-> Wellenzahlspektrum.

    kk


Anmelden zum Antworten