i want to speed up my code for Fourier Transform .how can i do it??

I Am taking selective frames from a video and applying 3D FFT. I want to reduce the execution time of the 3D FFT & IFFT. How can I achieve this, e.g. by using vectorization or preallocation?

i have added my code

%take selective frames from a video

 for
  t=1:100:T; %T is no of frames 
  f1= read(video,t); %read frames from video file video
  f2=rgb2gray(f1);   
  I(:,:,t)=f2; %I is for storing database of each frame 
 end

%apply 3-d Fourier Transform on frames

 Phase=zeros(400,400,20);%memory preallocate
 mag=zeros(400,400,20);%memory preallocate
 Phasestruct=zeros(400,400,20);%memory preallocate
 magstruct=zeros(400,400,20);%memory preallocate
 for s=1:100:T
  for u=1:r1 %r1 and c1 are dimensions of frame
   for v=1:c1  
   dft=0;
   mag(u,v,s)=0;
   phase(u,v,s)=0;
    for t=1:100:T             
     for x=1:r1          
      for y=1:c1                
      v1=exp(((-1j)*2*pi*(x-1)*(u-1))/r1);                 
      v2=exp(((-1j)*2*pi*(y-1)*(v-1))/c1);                             
      v3=exp(((-1j)*2*pi(t-1)*(s-))/(T-31));                                  
      dft=dft+ I(x,y,t)*((v1)*(v2)*(v3))/(r1*c1*(T));
      dft1=(fftshift(dft));             
      mag(u,v,s)=mag(u,v,s)+log(1+abs(dft1));%magnitude spectrum                
      phase(u,v,s)=phase(u,v,s)+exp(1j*angle(dft));%phase spectrum            
      end
     end
    end
   end        
  end 
 magstruct(s)=struct('magnitude',mag(:,:,s));%use of structure for storing  magnitude data    
 phasestruct(s)=struct('phase',phase(:,:,s));%use of structure for storing phase data
 end

%reconstruct frames from phase spectrum only using 3-d Inverse Fourier Transform

 idft=zeros(400,400,20);%memory preallocate 
 idft2=zeros(400,400,20); %memory preallocate
 reconstruct=zeros(1000)%memory preallocate
 for t=1:100:T 
  for x=1:r1 
   for y=1:c1 
   idft(x,y,t)=0;   
    for s=1:100:T
     for u=1:r1
      for v=1:c1   
       z1=exp(((1j)*2*pi*(x-1)*(u-1))/r1);               
       z2=exp(((1j)*2*pi*(y-1)*(v-1))/c1);                  
       z3=exp(((1j)*2*pi*(t-1)*(s-1))/(T));   
       idft(x,y,t)=idft(x,y,t)+ (phasestruct(s).phase(u,v))*((z1)*(z2)*(z3)); %as i will reconstruct frames from phase spectrum only   
       idft2(x,y,t)=idft(x,y,t).*conj(idft(x,y,t));            
       end
      end
     end
    end
   end
  reconstruct(t)=struct('reconstructed',idft(:,:,t));
  end

/* 1.when i run it ,it takes almost 3-4 hours for getting output results..

2.when i used direct matlab function "fftn" instead of six "for" loops for 3d fft formula, it gives error as "unsupported dimensions" at line "f1= read(video,t);".

3.when i used memory preallocation it gives error at line " phasestruct(s)=struct('phase',phase(:,:,s));" as "cannot covert from double to structure".

so i'm totally confused..so please help me so that i can get output results within few minutes .......thanks */

[dpb]

Please format your code legibly first so can read it...HINT: don't put blank lines between code lines--that starts the wyswig formatting over again.

Suggestions

1) Use the profiler to find the bottlenecks

2) Show the error on preallocation in context; don't make us guess...

[ramdas patil]

Sir, now I have formatted my code and also added lines where i am getting errors for preallocation,so that u can understand it properly...

Can i use any direct function (and/or) memory preallocation(and/or) vectorization to speed up my code......?

How??

Please help me ............... thanks!!!!!

Answer 1

[dpb]

1.when i run it ,it takes almost 3-4 hours...

Not too surprised...amongst other things of a zillion duplicated computations of constants, you've put the terms in only one or at most two of the loop-dependent variables at the deepest nesting where they could/should be at a level or two or three higher.

2.when i used direct matlab function "fftn" instead of six "for" loops for 3d fft formula, it gives error as "unsupported dimensions" at line "f1= read(video,t);"

That has nothing to do with the use of fftn as that occurs well ahead of the need to call it. You've got something else wrong but it's impossible to diagnose a problem w/o the actual code and error in context and without modification.

3.when i used memory preallocation it gives error at line "phasestruct(s)=struct('phase',phase(:,:,s));" as "cannot covert from double to structure".

Because you preallocated phasestruct and magstruct as arrays, too. What's the point of the struct, anyway, it doesn't really buy anything as you've already got the result arrays.

But, the obvious is go back to fftn and work out the problem you had -- you're never going to get anything like the performance of a builtin fft routine w/ highlevel Matlab code like this if performance is the issue as opposed to an academic exercise.

See

doc fftn
doc fftw

for some hints.

[ramdas patil]

thank u very much sir for your suggestion .now i am trying to use "fftn" function but i got new errors. my new code is

clc;
clear all;
close all;
% video=VideoReader('C:\Users\Public\Videos\Sample Videos\Wildlife.wmv');
video=read('C:\Users\Public\Videos\Sample Videos\gray\myvideo.avi');
f=fftn(v);

 i=imread('C:\Users\Public\Videos\Sample Videos\gray\2.jpg');
 f=fftshift(fftn(i));
 figure,imshow(i);
 figure,imshow(log(1+f),[]);

1.when i apply "fftn" for single frame i get same results as "fft2" function

 i=imread('C:\Users\Public\Videos\Sample Videos\gray\2.jpg');
 f=fftshift(fftn(i));

2.But when i apply "fftn" on "video" i got error

 "??? Undefined function or method 'read' for input arguments of type 'char'" 
at line
"v=read('C:\Users\Public\Videos\Sample Videos\gray\myvideo.avi');"

when i uncomment line

 "video=VideoReader('C:\Users\Public\Videos\Sample Videos\Wildlife.wmv');" i get error as 
 "??? Undefined function or method 'VideoReader' for input arguments of type 'char'."

so will u please tell me how to use "fftn" and "ifftn" to apply 3d fft on video sequence .... getback frames from phase spectrum only......???

i gone through algorithms of "fftn "and "ifftn"but couldn't find out solution

3.also is there any need to convert rgb video to gray video before applying fftn function on video ...???

thanks

[dpb]

??? Undefined function or method 'read' for input arguments of type 'char'" at line

v=read('C:\Users\Public\Videos\Sample Videos\gray\myvideo.avi');

The problem has nothing to do with fftn; as the error says, it failed on the read call; didn't even get to trying the fft.

I've never used it; don't know of any peculiarities beyond what doc's say. I note there's an embedded space in the file name; try enclosing it in double quotes as

v=read('"C:\Users\Public\Videos\Sample Videos\gray\myvideo.avi"');

and see if that helps.