---

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.