Vergleichsweise langsame Python-Numpy 3D Fourier Transformation

Liebe StackOverflow Community!

Für meine Arbeit muss ich diskrete Fourier-Transformationen (DFTs) auf großen Bildern durchführen. Im aktuellen Beispiel benötige ich ein 3D FT für ein 1921 x 512 x 512 Bild (zusammen mit 2D FFTs von 512 x 512 Bildern). Im Moment nutze ich das numpy Paket und die zugehörige Funktion np.fft.fftn () . Das Code-Snippet unten zeigt beispielhaft 2D- und 3D-FFT-Zeiten auf einem gleichgroßen / etwas kleineren 2D / 3D-Zufallszahlen-generierten Gitter auf folgende Weise:

import sys import numpy as np import time tas = time.time() a = np.random.rand(512, 512) tab = time.time() b = np.random.rand(100, 512, 512) tbfa = time.time() fa = np.fft.fft2(a) tfafb = time.time() fb = np.fft.fftn(b) tfbe = time.time() print "initializing 512 x 512 grid:", tab - tas print "initializing 100 x 512 x 512 grid:", tbfa - tab print "2D FFT on 512 x 512 grid:", tfafb - tbfa print "3D FFT on 100 x 512 x 512 grid:", tfbe - tfafb 

Ausgabe:

 initializing 512 x 512 grid: 0.00305700302124 initializing 100 x 512 x 512 grid: 0.301637887955 2D FFT on 512 x 512 grid: 0.0122730731964 3D FFT on 100 x 512 x 512 grid: 3.88418793678 

Das Problem, das ich habe, ist, dass ich diesen Prozess sehr oft brauchen werde, also sollte die Zeit pro Bild kurz sein. Beim Testen auf meinem eigenen Computer (Mittelsegment-Laptop, 2GB RAM für virtuelle Maschine (-> also kleineres Testgitter)), wie man die 3D-FFT sehen kann, nimmt man ~ 5 s (Größenordnung). Jetzt sind bei der Arbeit die Maschinen viel besser, Cluster / Grid-Architektur-Systeme und FFTs sind viel schneller. In beiden Fällen beenden die 2Ds quasi sofort.

Allerdings mit 1921x512x512, np.fft.fftn () dauert ~ 5 min. Da ich vermute, dass die Implementierung von scipy nicht viel schneller ist und in der Erwägung, dass auf MATLAB FFTs gleichgroßer Raster innerhalb von ~ 5 s beendet ist, ist meine Frage, ob es eine Methode gibt, den Prozess bis zu oder fast zu MATLAB mal zu beschleunigen. Mein Wissen über FFTs ist begrenzt, aber anscheinend verwendet MATLAB den FFTW-Algorithmus, den python nicht macht. Jede vernünftige Chance, dass mit einigen pyFFTW-Paket bekomme ich ähnliche Zeiten? Auch 1921 scheint eine unglückliche Wahl zu haben, die nur 2 Primfaktoren hat (17, 113), also nehme ich an, dass dies auch eine Rolle spielt. Auf der anderen Seite ist 512 eine gut genutzte Kraft von zwei. Sind MATLAB-ähnliche Zeiten erreichbar, wenn möglich auch ohne Auffüllung mit Nullen bis 2048?

Ich frage, weil ich FFTs viel nutzen muss (zu einem Betrag, in dem solche Unterschiede von großem Einfluss sein werden) und falls es keine Möglichkeit gibt, die Rechenzeiten in Python zu reduzieren, müsste ich auf andere wechseln , Schnellere Implementierungen.

Jeder Rat wird sehr geschätzt!

One Solution collect form web for “Vergleichsweise langsame Python-Numpy 3D Fourier Transformation”

Ja, es gibt eine Chance, dass mit FFTW durch die Schnittstelle pyfftw wird Ihre Rechenzeit im Vergleich zu numpy.fft oder scipy.fftpack . Die Performances dieser Implementierungen von DFT-Algorithmen können in Benchmarks wie diesem verglichen werden: einige interessante Ergebnisse werden in der Verbesserung der FFT-Performance in Python berichtet

Ich schlage vor, den folgenden Code für einen Test:

 import pyfftw import numpy import time import scipy f = pyfftw.n_byte_align_empty((127,512,512),16, dtype='complex128') #f = pyfftw.empty_aligned((33,128,128), dtype='complex128', n=16) f[:] = numpy.random.randn(*f.shape) # first call requires more time for plan creation # by default, pyfftw use FFTW_MEASURE for the plan creation, which means that many 3D dft are computed so as to choose the fastest algorithm. fftf=pyfftw.interfaces.numpy_fft.fftn(f) #help(pyfftw.interfaces) tas = time.time() fftf=pyfftw.interfaces.numpy_fft.fftn(f) # here the plan is applied, nothing else. tas = time.time()-tas print "3D FFT, pyfftw:", tas f = pyfftw.n_byte_align_empty((127,512,512),16, dtype='complex128') #f = pyfftw.empty_aligned((33,128,128), dtype='complex128', n=16) f[:] = numpy.random.randn(*f.shape) tas = time.time() fftf=numpy.fft.fftn(f) tas = time.time()-tas print "3D FFT, numpy:", tas tas = time.time() fftf=scipy.fftpack.fftn(f) tas = time.time()-tas print "3D FFT, scipy/fftpack:", tas # first call requires more time for plan creation # by default, pyfftw use FFTW_MEASURE for the plan creation, which means that many 3D dft are computed so as to choose the fastest algorithm. f = pyfftw.n_byte_align_empty((128,512,512),16, dtype='complex128') fftf=pyfftw.interfaces.numpy_fft.fftn(f) tas = time.time() fftf=pyfftw.interfaces.numpy_fft.fftn(f) # here the plan is applied, nothing else. tas = time.time()-tas print "3D padded FFT, pyfftw:", tas 

Für eine Größe von 127 * 512 * 512, auf meinem bescheidenen Computer, bekam ich:

 3D FFT, pyfftw: 3.94130897522 3D FFT, numpy: 16.0487070084 3D FFT, scipy/fftpack: 19.001199007 3D padded FFT, pyfftw: 2.55221295357 

Also pyfftw ist deutlich schneller als numpy.fft und scipy.fftpack . Mit Padding ist noch schneller, aber die Sache, die berechnet wird, ist anders.

Schließlich kann pyfftw im ersten Lauf langsamer erscheinen, da es die FFTW_MEASURE nach der Dokumentation benutzt . Es ist eine gute Sache, wenn und nur wenn viele DFTs der gleichen Größe nacheinander berechnet werden.

  • Welches ist der effizienteste Weg, um durch eine Liste in Python zu iterieren?
  • Leistung von verschiedenen Methoden, um für ein Palindrome zu testen [Python]
  • Python-String 'join' ist schneller (?) Als '+', aber was ist hier falsch?
  • Was ist in der Regel schneller, ein Ertrag oder ein Append?
  • Ist die Leistung zwischen der Python- oder C ++ - Codierung von OpenCV unterschiedlich?
  • Warum ist Looping Beat Indexierung hier?
  • Schnellste Methode, um große zufällige Zeichenfolge mit niedrigeren lateinischen Buchstaben zu erzeugen
  • Beschleunige das Schreiben in Dateien
  • Python - finden Vorkommen der Liste der Zeichenfolgen innerhalb der Zeichenfolge
  • Python-Multiprocessing - Pipe vs Queue
  • String Performance - Python 2.7 vs Python 3.4 unter Windows 10 vs Ubuntu
  • Python ist die beste Programmiersprache der Welt.