CODEWITHSUNDEEP
pythonopencvpython-2.7image-processingfft
obelix
obelix

Reputation: 890

Speeding up Fourier-related transform computations in python (OpenCV)

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]))

Upvotes: 3

Views: 1221

Answers (1)

KobeJohn
KobeJohn

Reputation: 7545

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

Upvotes: 3

Related Questions