Discrete Fourier Transform
Introduction to the Fourier transform and the Frequency Domain

This section introduces the Fourier transform in one and two dimensions. The focus is mostly on a discrete formulation of the continuous transform and some of its properties.

The One-Dimensional Fourier Transform and its Inverse
The Fourier transform, F (u), of a single variable, continuous function, f (x), is defined by the equation
$$F(u)=\int_{-\infty}^{\infty} f(x)\space e^{-j2\pi ux} dx \space \space \space ……(2.1-1)$$
Where j=$\sqrt{-1}$Conversely, given F(u), we can obtain f(x) by means of the
Inverse Fourier transform
$$f(x)=\int_{-\infty}^{\infty} F(u)\space e^{-j2\pi ux} dx \space \space \space ……(2.1-2)$$
These two equations comprise the Fourier transform pair. They indicate the important fact mentioned in that a function can be recovered from its transform. These equations are easily extended to two variables, u and v:
$$f(u,v)=\int_{-\infty}^{\infty}\int_{-\infty}^{\infty} f(x,y)\space e^{-j2\pi (ux+vy)} dx\space dy \space \space \space ……(2.1-3)$$
and, similarly for the inverse transform,
$$f(x,y)=\int_{-\infty}^{\infty}\int_{-\infty}^{\infty} F(u,v)\space e^{j2\pi (ux+vy)} du\space dv \space \space \space ……(2.1-4)$$
Our interest is in discrete functions, so we will not dwell on these equations here. However, in some cases, the reader may find them easier to manipulate than their discrete equivalents in proving the validity of properties of the 2-D Fourier transform.
The Fourier transform of a discrete function of one variable, f ( x), x = 0, 1, 2, ... , M - 1, is given by the equation
$$F(u)=\sum_{x=0}^{M-1} f(x)e^{-j2\pi ux/M}\space\space for u=0,1,2,….,M-1\space \space \space ……….(2.1-5)$$
This discrete Fourier transform (DFT) is the foundation for most of the work in this chapter. Similarly, given F(u), we can obtain the original function back using the inverse DFT:
$$F(x)=\sum_{u=0}^{M-1} F(u)e^{j2\pi ux/M}\space\space for x=0,1,2,….,M-1\space \space \space ……….(2.1-6)$$

The 1/ M multiplier in front of the sometimes is placed in front of the inverse instead. Other times (not as often) both equations are multiplied by 1/VM. The location of the multiplier does not matter. If two multipliers are used, the only requirement is that their product be equal to 1/ M. Considering their importance, these equations really are very simple. In order to compute F( u) in Eq. (2.1-5) we start by substituting u = 0 in the exponential term and then summing for all values of x. We then substitute u = 1 in the exponential and repeat the summation over all values of x. We repeat this process for all M values of u in order to obtain the complete Fourier transform. It takes approximately M2 summations and multiplications to compute the discrete Fourier transform. Like f(x), the transform is a discrete quantity, and it has the same number of components as f(x). Similar comments apply to the computation of the inverse Fourier transform. An important property of the discrete transform pair is that, unlike the continuous case, we need not be concerned about the existence of the DFT or its inverse. The discrete Fourier transform and its inverse always exist. This can be shown by substituting either of Eqs. (2.1-5) or (2.1-6) into the other and making use of the orthogonality of the exponential terms. We will get an identity, indicating the existence of the two functions. Of course, there is always the question of what happens if f(x) has infinite values, but we deal strictly with finite quantities in this book. These comments are directly applicable to two-dimensional (and higher) functions. Thus, for digital image processing, the existence of either the discrete transform or its inverse is not an issue.

The Two-Dimensional DFT and Its Inverse
Extension of the one-dimensional discrete Fourier transform and its inverse to two dimensions is straightforward. The discrete Fourier transform of a function (image) f(x,y) of size M xN is given by the equation
$$F(u,v)=\frac{1}{MN}\sum_{x=0}^{M-1}\sum_{y=0}^{N-1} f(x,y)e^{-j2\pi (\frac{ux}{M}+\frac{vy}{N})}$$

As in the 1-D case, this expression must be computed for values of u = 0. 1, 2... M-1, and also for v = 0. 1, 2... N-1. Similarly, given F(u,v) we obtain f(x,y) via the inverse Fourier transform, given by the expression $$f(x,y)=\sum_{u=0}^{M-1}\sum_{v=0}^{N-1} F(u,v)e^{j2\pi (\frac{ux}{M}+\frac{vy}{N})}$$

for x = 0, 1, 2, ... , M-1 and y = 0, 1, 2, ... , N-1. Both the above equations comprise the two-dimensional, discrete Fourier transform (DPT) pair. The variables u and v are the transform or frequency variables, and x and y are the spatial or image variables. As in the one-dimensional case, the location of the 1/ MN constant is not important. Sometimes it is located in front of the inverse transform. Other times it is found split into two equal terms of 1/$\sqrt{MN}$ multiplying the transform and its inverse. Finally, as in the 1-D case, we have the following relationships between samples in the spatial and frequency domains:
$$\Delta u=\frac{1}{M\Delta x}$$
and
$$\Delta v=\frac{1}{N\Delta y}$$

Properties of DFT – Walsh, Hadamard

The basis vectors of the discrete Hadamard and the discrete Walsh-Hadamard transforms consist of the values ±a. Both transforms are unitary. Basically, they differ only in the order of the basis vectors.
We have
$$y=Hx$$
$$x=Hy$$
$$H^T=H=H^{-1}$$
The transform matrix of the 2x2-Hadamard transform is given by
$$ H^{(2)}=\frac{1}{\sqrt 2} \left[ {\begin{array}{cc} H^n&H^n \\ H^n & -H^n\\ \end{array} } \right]$$ From this, all transform matrices$H^{(n)}$ of $size^2n=2^k$ n= 2^k,k∈IN can be calculated recursively:
$$ H^{(3)}=\frac{1}{\sqrt 2} \left[ {\begin{array}{cc} H^n&H^n \\ H^n & -H^n\\ \end{array} } \right]$$
The Walsh-Hadamard transform is obtained by taking the Hadamard transform and rearranging the basis vectors according to the number of zero crossings. Somehow, this yields an order of the basis vectors with respect to their spectral properties.