6.3.2.8 Discrete Fourier transform ¶

As we have stated several times so far, the input image is a digitized, pixelated or discrete array of values ($f_s(l)$, see Sampling theorem). The input is not a continuous function. Also, all our numerical calculations can only be done on a sampled, or discrete Fourier transform. Note that $F_s(\omega)$ is not discrete, it is continuous. One way would be to find the analytic $F_s(\omega)$, then sample it at any desired “freq-pixel”¹⁷⁶ spacing. However, this process would involve two steps of operations and computers in particular are not too good at analytic operations for the first step. So here, we will derive a method to directly find the ‘freq-pixel’ated $F_s(\omega)$ from the pixelated $f_s(l)$. Let’s start with the definition of the Fourier transform (see Fourier transform):

$$F_s(\omega)=\int_{-\infty}^{\infty}f_s(l)e^{-i{\omega}l}dl$$

From the definition of $f_s(\omega)$ (using $x$ instead of $n$) we get:

$$\eqalign{ F_s(\omega) &= \displaystyle\sum_{x=-\infty}^{\infty} \int_{-\infty}^{\infty}f(l)\delta(l-xP)e^{-i{\omega}l}dl \cr &= \displaystyle\sum_{x=-\infty}^{\infty} f_xe^{-i{\omega}xP} }$$

Where $f_x$ is the value of $f(l)$ on the point $x$ or the value of the $x$th pixel. As shown in Sampling theorem this function is infinitely periodic with a period of $2\pi/P$. So all we need is the values within one period: $0<\omega<2\pi/P$, see Figure 6.3. We want $X$ samples within this interval, so the frequency difference between each frequency sample or freq-pixel is $1/XP$. Hence we will evaluate the equation above on the points at:

$$\omega={u\over XP} \quad\quad u = 0, 1, 2, ..., X-1$$

Therefore the value of the freq-pixel $u$ in the frequency domain is:

$$F_u=\displaystyle\sum_{x=0}^{X-1} f_xe^{-i{ux\over X}}$$

Therefore, we see that for each freq-pixel in the frequency domain, we are going to need all the pixels in the spatial domain¹⁷⁷. If the input (spatial) pixel row is also $X$ pixels wide, then we can exactly recover the $x$th pixel with the following summation:

$$f_x={1\over X}\displaystyle\sum_{u=0}^{X-1} F_ue^{i{ux\over X}}$$

When the input pixel row (we are still only working on 1D data) has $X$ pixels, then it is $L=XP$ spatial units wide. $L$, or the length of the input data was defined in Fourier series and $P$ or the space between the pixels in the input was defined in Dirac delta and comb. As we saw in Sampling theorem, the input (spatial) pixel spacing ($P$) specifies the range of frequencies that can be studied and in Fourier series we saw that the length of the (spatial) input, ($L$) determines the resolution (or size of the freq-pixels) in our discrete Fourier transformed image. Both result from the fact that the frequency domain is the inverse of the spatial domain.