Speeding up Fourier-related transform computations in python (OpenCV)
Question: 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:<http://en.wikipedia.org/wiki/Short-time_Fourier_transform>).

In order to do that I need to :

(1) place a window at the starting pixel of the image (x,y)=(M/2,M/2)

(2) Truncate the image using this window

(3) Compute the FFT of the truncated image, save results.

(4) Incrementally slide the window to the right

(5) Go to step 3, until window reaches the end of the image

However I need to perform the aformentioned calculation in real time... But it
is rather slow !!!

Is there anyway to speed up the aformentioned process ??

I also include my 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]))
    


Answer: Of course the bulk of your time is going to be spent in the FFT's and other
transformation code, but I took a shot at easy optimizations of the other
parts.

# Changes

  * Frame size calculations are the same every loop so move them out (~nil improvement)
  * Type coercion from uint8 to float32 can be done once on the whole image rather than converting each frame. (small but measurable improvement)
  * If the window size is already the same as the optimal size (I guess it always will be if you keep M as a power of 2), then don't do the bordered copy. Just use the `face_win` view as-is. (small but measurable improvement)

Total improvement 26s --> 22s. Not much but there it is.

# Standalone Code (just add `1024x768.jpg`)

    
    
    import time
    import cv2
    import numpy as np
    
    # image loading for anybody else who wants to use this
    final_frame = cv2.imread('1024x768.jpg')
    final_frame = cv2.cvtColor(final_frame, cv2.COLOR_BGR2GRAY)
    final_frame_f32 = final_frame.astype(np.float32)  # moved out of the loop
    
    # base data
    M = 4
    height, width = final_frame.shape
    
    # various calculations moved out of the loop
    m_half = M//2
    height_win, width_win = [2 * m_half] * 2  # can you even use odd values for M?
    fftheight = cv2.getOptimalDFTSize(height_win)
    fftwidth = cv2.getOptimalDFTSize(width_win)
    bordertype = cv2.BORDER_CONSTANT
    right = fftwidth - width_win
    bottom = fftheight - height_win
    
    start = time.time()
    for j in range(m_half, height-m_half):
        for i in range(m_half, width-m_half):
            face_win = final_frame_f32[j-m_half:j+m_half, i-m_half:i+m_half]
            # only copy for border if necessary
            if (fftheight, fftwidth) == (height_win, width_win):
                nimg = face_win
            else:
                nimg = cv2.copyMakeBorder(face_win, 0, bottom, 0, right, bordertype, value=0)
            dft = cv2.dft(nimg, flags=cv2.DFT_COMPLEX_OUTPUT)
            dft_shift = np.fft.fftshift(dft)
            magnitude_spectrum = 20 * np.log(cv2.magnitude(dft_shift[:, :, 0], dft_shift[:, :, 1]))
    elapsed = time.time() - start
    
    print elapsed
    

# Bugs

  * I fixed these in the code above but I didn't edit your original since you may have intended it to be that way
  * you calculate nimg but then use the original face_win in the dft
  * to be explicit, I changed `M/2` etc. to `M//2`

