Schnellste Methode compute Faltungs

Question

ich auf jede Reihe von vielen Bildern ein Faltungsfilter anwenden müssen. Der Klassiker ist 360 Bilder von 1024x1024 Pixeln. In meinem Anwendungsfall ist es 720 Bilder 560x600 Pixel.

Das Problem ist, dass mein Code ist viel langsamer als das, was in Artikel beworben wird.

Ich habe die naive Faltung implementiert, und es dauert 2m 30s. Ich wechselte dann zu FFT fftw. Ich verwenden komplexen 2-Komplex, das Filtern in zwei Reihen jeweils zu transformieren. Ich bin jetzt um 20s.

Die Sache ist die, dass die Artikel rund um 10s werben und noch weniger für den klassischen Zustand. So würde Ich mag die Experten hier fragen, ob es ein schnellerer Weg sein könnte, die Faltung zu berechnen.

Numerische Rezepte vorschlagen, die Sortierung erfolgt in der dft und Anpassung der Frequenzbereichsfilterfunktion entsprechend zu vermeiden. Aber es gibt kein Codebeispiel, wie dies geschehen könnte.

Vielleicht verliere ich Zeit Daten zu kopieren. Mit echten 2 realen verwandeln würde ich muss die Daten in die complexe Werte nicht kopieren. Aber ich habe mit 0 sowieso Pad.

EDIT: s. Meine eigene Antwort unten für den Fortschritt Feedback und weitere Informationen zu diesem Thema zu lösen

Frage (genaue Neuformulierung):

Ich suche nach einem Algorithmus oder ein Stück Code, der eine sehr schnelle Faltung zu einer diskreten nicht periodischen Funktion (512-2048 Werte) anzuwenden. Offenbar ist die diskrete Zeit-Fourier-Transformation ist der Weg zu gehen. Obwohl, ich möchte Daten zu komplexen kopieren und Umwandlung zu vermeiden, und der Schmetterling Umsortierung zu vermeiden.

Answer 1

FFT ist die schnellste Methode für Falten Signale bekannt, und FFTW ist die schnellsten freie Bibliothek zur Verfügung, die die FFT zur Berechnung.

Der Schlüssel für Sie maximale Leistung zu erhalten (außerhalb von Hardware ... die GPU ist ein guter Vorschlag) aufzufüllen, Ihre Signale zu einer Zweierpotenz. Wenn FFTW Verwendung verwenden, um die ‚Patienten‘ einstellen, wenn Ihr Plan erstellen die beste Leistung zu erhalten. Es ist höchst unwahrscheinlich, dass Sie die Hand-Rolle eine schnellere Implementierung als das, was FFTW bietet (vergessen N. R.). Auch sicher sein, mit der Echt Version des Vorwärts-1D FFT und nicht die komplexe Version zu sein; und nur einzelne (floating point) Präzision verwenden, wenn Sie können.

Wenn FFTW schneidet es nicht für Sie, dann würde ich auf Intels aussehen (sehr erschwinglich) IPP-Bibliothek. Die haben Hand abgestimmt FFT für Intel-Prozessoren, die für Bilder mit verschiedenen Bit-Tiefen optimiert wurden.

Paul
CenterSpace Software

Answer 2

Sie möchten Bildverarbeitung als Tag hinzuzufügen.

Aber kann dieser Artikel von Interesse sein, besonders mit der Annahme, das Bild eine Macht ist oder 2. Sie können auch sehen, wo sie die FFT optimieren. Ich gehe davon aus, dass die Artikel, die Sie bei gemacht einigen Annahmen suchen und dann die Gleichungen für diejenigen optimiert.

http://www.gamasutra.com/view/feature/3993 /sponsored_feature_implementation_.php

Wenn Sie schneller gehen wollen Sie möchten die GPU nutzen, um tatsächlich die Arbeit machen.

Dieses Buch hilfreich sein für Sie, wenn Sie mit der GPU gehen: http://www.springerlink.com/content/kd6qm361pq8mmlx2/

Answer 3

Diese Antwort ist die Sammlung Fortschrittsbericht Feedback zu diesem Thema.

Bearbeiten 11. Oktober .:

Die I Ausführungszeit gemessen spiegelt nicht die effektive Zeit der FFT. Ich habe bemerkt, dass, wenn mein Programm endet, ist die CPU noch damit beschäftigt, in der Systemzeit bis zu 42% für 10s. Wenn ich warte, bis die CPU wieder auf 0% ist, bevor mein Programm neu zu starten erhalte ich dann die 15.35s Ausführungszeit, die von der GPU-Verarbeitung kommt. Ich erhalte die gleiche Zeit, wenn ich die FFT-Filterung auf Kommentar.

So ist die FFT ist in der Tat noch schneller als die GPU und wurde einfach durch eine konkurrierendes System Aufgabe behindert. Ich weiß noch nicht, was dieses System Aufgabe. Ich vermute, es ergibt sich aus der Zuordnung eines riesigen Haufen Block, in dem ich das Verarbeitungsergebnis kopieren, bevor es auf die Festplatte zu schreiben. Für die Eingangsdaten ich eine Speicherkarte.

Ich werde jetzt meinen Code ändern, um eine genaue Messung der FFT-Verarbeitungszeit zu erhalten. So dass es schneller ist nach wie vor Aktualität, weil es Raum durch Pipelining die Übertragung von Daten zu verarbeiten, die GPU-Verarbeitung wie zum Beispiel zu optimieren.