Ich implementiere derzeit eine zweidimensionale FFT für reale Eingabedaten mit opencl (genauer gesagt eine schnelle 2D-Faltung mit FFTs, also brauche ich nur etwas, das sich ähnlich genug verhält, um die Faltung anzuwenden). Die 2D-FFT wird unter Verwendung einer 1D-FFT auf den Zeilen und anschließend einer 1D-FFT auf den Spalten implementiert.Effiziente 2D FFT an realen Eingabedaten?
Um dies effizienter zu machen, versuche ich die Symmetrien von FFTs mit realem Eingang zu verwenden, um kleinere FFTs berechnen zu können. Ich habe herausgefunden, dass ich zwei Zeilen zu einer kombinieren kann, indem ich die erste als reelle Komponente, die zweite als imaginäre Komponente, die erste 1D FFT für die resultierende Zeile und dann die Symmetrieeigenschaften verwende, um die Ergebnisse der 1D FFTs des Individuums zu konstruieren Zeilen davon. Also was ich tue ist im Grunde Folgendes:
Lassen Sie f und g Zeilen aus der Matrix sein.
- Construct
x = f + i * g F(x) = F(f) + i * F(g)Symmetrien- benutzen Sie Trans
F(f)undF(g)vonF(x)
extrahieren kann ich nicht aber Eingang nur die Ergebnisse direkt in die zweite 1D FFT, weil In diesem Fall würde ich nicht die gesamte Matrix, sondern zwei Submatrizen transformieren. Das Extrahieren der Daten zwischen den Transformationen bedeutet jedoch, dass entweder mehr Daten gespeichert werden (n/2+1 Einträge, um das Ergebnis einer 1D FFT an realen Eingaben auszudrücken) oder die Elemente mit Index 0 und Index n/2 zu einem Element kombiniert werden (kombiniert mit demselben Trick, da beide Zahlen sind garantiert echt) und verwenden die gleiche Menge an Speicherplatz, müssen aber in meiner Faltung einen besonderen Fall dafür machen.
Da ich versuche, Puffer so viel wie möglich zu verwenden (aufgrund der begrenzten RAM verfügbar auf der GPU) mit mehr Speicher ist keine nette Lösung. Darüber hinaus sind meine Algorithmen nicht für Matrixgrößen geeignet, die keine Potenz von 2/Vielfachen von 16 sind (variiert von Kernel zu Kernel). Ich würde es auch lieber vermeiden, Sonderfälle einzuführen, da diese meine Kernel komplexer machen würden, was die Effizienz beeinträchtigt (ich habe bereits Probleme, die von jedem Kernel verwendete Registeranzahl zu minimieren).
Also meine Frage ist, ob es eine elegante Herangehensweise an dieses Problem gibt, gemeint ist eine, die funktioniert, ohne entweder mehr Speicher oder Sonderfälle für bestimmte Elemente zu verwenden?
Idealerweise würde ich gerne die ganze FFT machen können, ohne meine kombinierten Daten in der Mitte der FFT zu teilen, aber ich bin mir nicht sicher, ob das möglich ist.
Wird dies in absehbarer Zeit als Taschenbuch heraus sein? –
Müssen Sie wirklich eine komplexe FFT machen? Wahrscheinlich nicht. – phkahler
gute Frage, hatte ich fast das gleiche Problem während der Durchführung von FFT für die Erkennung von Steganographie. aber ich habe damals nicht gemerkt, dass stackoverflow existiert;/ – dfens