Home > Image Processing > 8a. Fourier Transforms and Basic Image Patterns

8a. Fourier Transforms and Basic Image Patterns

Oftentimes we see repetitive patterns on images we capture in photography or encounter in image processing.  Whether these are unexpected by the viewer or not, their origins are better understood by the concept of Fourier Transform.  In this section, we will develop a deeper understanding on the concept of Convolution Theorem.  We note that:

(1) the FT of the convolution of two functions f and g is equal to the product of their individual Fourier Transforms;

(2) the convolution of a function f and a Dirac delta function results in the replication of the function on the location of the function.

_
Convolution Theorem

From the basic properties of 2D Fourier Transform, we learned how two dots equidistant to the origin produce an FT output composed of bright and dark fringes (Figure 1).

Figure 1. Fourier Transform of a pair of dots.  Left: original pattern of the two dots; Right: FT of the pattern.

Now if we modify this pattern into circles of some radius, we get an FT pattern composed of concentric circles where the middle circle (maximum) becomes smaller in radius and number of concentric ones increase as the apertures are enlarged (Figure 2).  These is referred to as the Airy pattern, which model is used to describe diffraction patterns in optics.

Figure 2. Fourier Transform of two circles with various radii. Top row (left to right): pairs of circles with radius 0.02 to 0.06 at 0.01 increments; Bottom row: corresponding FT of the patterns.

If we replace the circles instead with squares, we obtain an FT pattern where the maximum frequency follows the shape of a square (Figure 3).

Figure 3. Fourier Transform of two squares with various widths. Top row (left to right): pairs of squares with width 0.02 to 0.06 at 0.01 increments; Bottom row: corresponding FT of the patterns.

Next we try to replace these with Gaussians, expressed by:

where μ0 is the mean and σ2 is the variance.  At increasing values for variance, we get FT patterns similar to the ones in Figure 4.  We notice that the width of the FT pattern decreases as the width of the spatial Gaussian is increased.

Figure 4. Fourier Transform of Gaussians with different variance. Top row (left to right): pairs of 2D gaussians at σ = 0.01 to 0.05 at 0.01 increments; Bottom row: corresponding FT of the patterns.

This is performed with the following Scilab implementation:

nx = 128; ny = 128; // defines the number of elements along x and y

x = linspace(-1, 1, nx); //defines the range
y = linspace(-1, 1, ny);

[X,Y] = ndgrid(x, y); // creates two 2-D arrays of x and y coordinates

A = zeros(nx, ny);
var = (0.05)^2;

r = sqrt((X.^2 + (Y - 0.3).^2)/var);
A1 = exp(-r);
r = sqrt((X.^2 + (Y + 0.3).^2)/var);
A2 = exp(-r);

A = A1 + A2;

scf(0); imshow(A, []);
scf(1); imshow(fftshift(abs(fft2(A))), []);

The Dirac delta function can be approximately produced on a 2D image by putting a value 1 on a matrix composed of zeros.  We create 10 Dirac delta’s placed on random locations of a 200×200 binary matrix and convolve it with 3×3 patterns (Figure 5).  We us Scilab’s imconv() function to perform this.

A = zeros(nx, ny);

while sum(A) < 10
   A(round(rand()*200)+1, round(rand()*200)+1) = 1;
end;

pattern = [-1 -1 -1; 2 2 2; -1 -1 -1];  // horizontal

img = imconv(agray, pattern);
Figure 5. Convolution with the Dirac delta function. A. 10 randomly placed Dirac delta functions; B. horizontal pattern; C. convolution of the Dirac with the horizontal pattern; D. diagonal pattern; E. convolution of the Dirac with the diagonal pattern.

We observe on the resulting Fourier Transforms that a replication of the patterns were created on the locations of the Dirac deltas.  Let’s create a modification of this where the Dirac delta functions are placed on equally spaced points along the x- and y-axis.  The Scilab implementation will read as follows:

A = zeros(nx, ny);

interval = 2

for i = 1:interval:nx+1
  for j = 1:interval:ny+1
    A(i, j) = 1;
  end
end

FIgray = fft2(A);
imshow(fftshift(abs(FIgray)), []);

At increasing values of spacing between the 1’s we get the following FT results (Figure 5).  Notice that the frequencies of the Dirac deltas shown in the Fourier Transform appear closer to each other as the spacing between the 1’s are increased.

Figure 6. Fourier Transform of equally spaced Dirac delta functions. Top row (left to right): Dirac delta peaks with spacing 2 to 10px at 2px interval; Bottom row : corresponding FT of the patterns.

The basic knowledge on the important concept behind these FT patterns allows us to utilize this as an intelligent technique in image processing.  A succeeding article on enhancement in the frequency domain describes these basic applications.

———————————————————————————————–—————–————————————
References:
[1] Soriano, 2010. Enhancement in the Frequency domain.  Applied Physics 186.
[2] Weisstein, 2010. Convolution. MathWorld–A Wolfram Web Resource.

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: