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

4 views (last 30 days)
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 */
  2 Comments
dpb
dpb on 22 Apr 2014
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
ramdas patil on 23 Apr 2014
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!!!!!

Sign in to comment.

Accepted Answer

dpb
dpb on 23 Apr 2014
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.
  2 Comments
ramdas patil
ramdas patil on 28 Apr 2014
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
dpb on 28 Apr 2014
??? 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.

Sign in to comment.

More Answers (0)

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!