비교적 느린 파이썬 numpy 3D 푸리에 변환

Question

제 작품에서는 큰 이미지에서 이산 푸리에 변환 (DFT)을 수행해야합니다. 현재 예제에서 나는 1921 x 512 x 512 이미지 (512 x 512 이미지의 2D FFT와 함께)에 3D FT가 필요합니다. 지금 당장 numpy 패키지와 관련 함수 np.fft.fftn()을 사용하고 있습니다.

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 

출력 :

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 

예시 아래의 코드는 다음과 같은 방법으로 동일한 크기의/약간 작은 2D/3D 난수 생성 된 그리드에 2D와 3D FFT 시간을 보여줍니다 문제는 내가이 과정을 아주 자주 필요로하기 때문에 이미지 당 보낸 시간이 짧아야한다는 것입니다. 내 컴퓨터에서 테스트 할 때 (중간 세그먼트 랩톱, 가상 컴퓨터에 할당 된 2GB RAM (-> 그러므로 더 작은 테스트 그리드)), 3D FFT는 ~ 5 초 (크기 순서)를가집니다. 이제는 직장에서 기계가 더 나은 방법으로, 클러스터/그리드 아키텍처 시스템과 FFT가 훨씬 빠릅니다. 두 경우 모두 2D가 즉시 준 준공합니다.

그러나 1921x512x512의 경우 np.fft.fftn()은 ~ 5 분이 소요됩니다. scipy의 구현이 그리 빠르지 않다고 생각하고 동일한 크기의 격자가있는 MATLAB FFT에서 ~ 5 초 내에 끝나는 것을 고려할 때 제 질문은 MATLAB 시간까지 프로세스를 가속화하는 방법이 있는지 여부입니다. FFT에 대한 나의 지식은 제한되어 있지만, 분명히 MATLAB은 FFTW 알고리즘을 사용하는데, 파이썬에서는 그렇지 않습니다. 어떤 pyFFTW 패키지와 비슷한 시간에 얻을 수있는 합리적인 기회가 있습니까? 또한 1921 년은 불행한 선택인데, 2 가지 주요 요인 (17, 113) 만 가지고 있기 때문에이 또한 중요한 역할을한다고 가정합니다. 반면에 512는 2의 적절한 힘입니다. 가능한 경우 MATLAB과 같은 시간을 2048까지 0으로 채우지 않고도 달성 할 수 있습니까?

FFT를 많이 사용해야 할 것입니다. (그러한 차이가 엄청난 영향을 줄 수있는 금액으로!) 파이썬에서 계산 시간을 줄일 가능성이없는 경우, 다른 빠른 구현으로 전환 할 수 있습니다.

Answer 1

예, 인터페이스 pyfftw을 통해 FFTW를 사용하면 numpy.fft 또는 scipy.fftpack에 비해 계산 시간이 단축 될 수 있습니다. DFT 알고리즘이 구현의 공연 등 this one 같은 벤치 마크에 비교 될 수있다 : 몇 가지 흥미로운 결과는 내가 테스트에 대한 다음 코드를 제안 Improving FFT performance in Python

에보고됩니다

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 

(127)의 크기를 * * 512 (512)는, 내 겸손 컴퓨터에, 나는 가지고 :

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

그래서 pyfftw이 numpy.fft 및 scipy.fftpack보다 훨씬 빠릅니다. 패딩 사용은 더 빠르지 만 계산되는 것은 다릅니다.

마지막으로 에 따라 FFTW_MEASURE 플래그를 사용하기 때문에 pyfftw이 처음 실행시 느린 것처럼 보일 수 있습니다. 동일한 크기의 많은 DFT가 연속적으로 계산되는 경우에만 좋은 일입니다.