Implement 2D Discrete Fourier Transform?

Hello, I try to implement Discrete Fourier Transform (DFT) and draw the spectrum without using fft function.

The problem is that the calculation of DFT taking too long. Do you have any ideas to increase the calculation speed?

Please find the tested image at https://www.dropbox.com/s/vk9o5cpxjr0dyhc/cameraman.tif?dl=0 ! Thanks

 Img=double(imread('cameraman.tif'));
 [Img_M, Img_N] = size(Img);
 Output=zeros(Img_M,Img_N);
 SumInner = 0;
 SumOutner = 0;
 %%2D Discrete Fourier Transform
 for u = 1:(Img_M-1)
    for v = 1:(Img_N-1)      
        for x = 1:(Img_M-1)
            for y = 1:(Img_N-1)
                SumInner = SumInner + Img(x,y) * exp(-1i*2*3.1416*((u*x/Img_M)+(v*y/Img_N)));
            end
            SumOutner = SumOutner + SumInner;
        end
        Output(u,v) = SumOutner;
        SumOutner = 0;
        SumInner = 0;
    end
 end

 %%Calculate Spectrum and show
 Output2 = zeros(Img_M,Img_N);
 for u = 1:(Img_M-1)
    for v = 1:(Img_N-1)
        Output2(u,v) = sqrt((real(Output(u,v))^2+imag(Output(u,v))^2))/1000000;
    end
 end
 imshow(Output2)

Answer 1

[Subeesh Vasu]

 Img=double(imresize(imread('cameraman.tif'),0.3));
 [Img_M, Img_N] = size(Img);
 Output=zeros(Img_M,Img_N);
 SumOutner = 0;

 %%Centralized 2D Discrete Fourier Transform

 [nx,ny]=ndgrid([0:Img_M-1]-(Img_M-1)/2,[0:Img_N-1]-(Img_N-1)/2 );
 du=1;
 for u = [0:Img_M-1]-(Img_M-1)/2
     dv=1;
    for v = [0:Img_N-1]-(Img_N-1)/2  
        SumOutner=sum(sum(Img.*exp(-1i*2*3.1416*(u*nx/Img_M+v*ny/Img_N))));
        Output(du,dv) = SumOutner;
        dv=dv+1;
    end
    du=du+1;
 end

%%Calculate Spectrum and show
 imshow(uint8(abs(Output)/60))

Answer 2

[Image Analyst]

Well you got x and y reversed. It should be Img(y, x), NOT Img(x,y). Don't agree? Just think about it and you should have a forehead slapping moment.

And your loops, like over u and v should have the left most index be the innermost for loop .

Answer 3

[reetika dash]

if true
  % code
endImg=imread('cameraman.tif');
%Img=mat2gray(Img);

[x,y]=size(Img); subplot(1,2,1); imshow(Img); Img=double(Img);

A=zeros(x,y); for i=1:x for j=1:y A(i,j)=exp((-1*1j*2*pi*j*i)/x); end end %output=zeros(80,80); Output=A*Img*A'; Output=fftshift(Output); Output2 = zeros(x,y);

 for u = 1:x
    for v = 1:y
        Output2(u,v) = sqrt((real(Output(u,v))^2+imag(Output(u,v))^2));
    end
 end
 %Output2=fftshift(Output2);
 subplot(1,2,2);
 imshow(mat2gray(log10(1+Output2)))