function [ output ] = DFT( image_matrix )
% realizes the forward Discrete Fourier Transformation,
% ? the parameters of this function should be as follows:
%     ? input1: image matrix
%     ? output: Fourier Transformation of the image;
% ? it should work with grayscale images (check if the input image is grayscale),
% ? note: the naive implementation of the transformation is O(N^4), do not use it on
% large images,
% ? note: the imaginary number in MATLAB is i, the built-in constant for ? is pi,the
% exponential function is exp().

if (size(image_matrix,3) ~= 1)
    error 'This picture is not grayscale!'
end

[N1, N2] = size(image_matrix);
im = double(image_matrix);
output = zeros(N1, N2);

for x = 1:N1
   for y = 1:N2
      for n1 = 1:N1
         for n2 = 1:N2
             output(x,y) = output(x,y) + im(n1,n2) * ...
                exp(-1i * 2*pi * ((x-1) * (n1-1) / N1 + (y-1) * (n2-1) / N2));
         end
      end
   end
end

end