title: Speeding up Fourier-related transform computations in python (OpenCV)
body: <p>I have an image and I need to compute a fourier-related transform over it called Short Time Fourier Transform (for extra mathematical info check:<a href="http://en.wikipedia.org/wiki/Short-time_Fourier_transform" rel="nofollow">http://en.wikipedia.org/wiki/Short-time_Fourier_transform</a>).</p>
  
  <p>In order to do that I need to :</p>
  
  <p>(1) place a window at the starting pixel of the image (x,y)=(M/2,M/2)</p>
  
  <p>(2) Truncate the image using this window</p>
  
  <p>(3) Compute the FFT of the truncated image, save results.</p>
  
  <p>(4) Incrementally slide the window to the right </p>
  
  <p>(5) Go to step 3, until window reaches the end of the image</p>
  
  <p>However I need to perform the aformentioned calculation in real time...
  But it is rather slow !!!</p>
  
  <p>Is there anyway to speed up the aformentioned process ??</p>
  
  <p>I also include my code:</p>
  
  <pre><code>        height, width = final_frame.shape
          M=2
          for j in range(M/2, height-M/2):
              for i in range(M/2, width-M/2):
                  face_win=final_frame[j-M/2:j+M/2, i-M/2:i+M/2]
  
                  #these steps are perfomed in order to speed up the FFT calculation process
                  height_win, width_win = face_win.shape
                  fftheight=cv2.getOptimalDFTSize(height_win)
                  fftwidth=cv2.getOptimalDFTSize(width_win)
                  right = fftwidth - width_win
                  bottom = fftheight - height_win
                  bordertype = cv2.BORDER_CONSTANT 
                  nimg = cv2.copyMakeBorder(face_win,0,bottom,0,right,bordertype, value = 0)
  
                  dft = cv2.dft(np.float32(face_win),flags = cv2.DFT_COMPLEX_OUTPUT)
                  dft_shift = np.fft.fftshift(dft)
                  magnitude_spectrum = 20*np.log(cv2.magnitude(dft_shift[:,:,0],dft_shift[:,:,1]))
  </code></pre>