Monday, July 19, 2010

AP 186 Act6 – Fourier Transform Model of Image Formation

In this activity we will be dealing with Fourier Transforms (Fast Fourier Transforms) and their applications in image processing. Cooley and Tukey made the FFT algorithm and it’s widely used in image as well as signal processing.

Part A. Familiarization with FFT

First we’re asked to make a white circle centered on a black background:

(Note that this circle can also represent a circular aperture. I’ve made my circle smaller since this will result in a bigger Airy disk as will be seen later.)

Then we converted this to grayscale and performed the Fast Fourier Transform (FFT). Abs() was used to get the intensity values since the FFT will return an array of complex numbers.

I = imread('C:\circle.PNG');
Igray = im2gray(I);
FIgray = fft2(Igray);
imshow(abs(FIgray), []);
And this is the result:

FFT of the white circle

It looks like a pure black picture but take a look at the four corners. :p

This is a result of the FFT. It’s fast, but it also results in the reversal of the quadrants diagonally. Therefore, applying the fftshift will give:

imshow(fftshift(abs(FIgray)), []);
shifted FFT of the circle

Now that’s better. :) That’s the Fourier transform of the white circle.

Applying the FFT again on the transformed image (or consequently, applying the FFT twice on the original image) will theoretically result in an inverted original image:

imshow(abs(fft2(FIgray)));

circle FFT'ed twice

Well, we got the original image alright. But we can’t tell if this is inverted since an inverted circle is still a circle. So we try this on the letter “A”:

The (unshifted) FFT of A:

I = imread('A.bmp');
Igray = im2gray(I);
FIgray = fft2(Igray);
imshow(abs(FIgray), []);

unshifted FFT of "A"

And applying fftshift:

imshow(fftshift(abs(FIgray)), []);

shifted FFT of "A"

And that’s the Fourier transform of “A”.

Now applying the FFT twice… we get:

imshow(abs(fft2(FIgray)));

"A" FFT'ed twice

Which is indeed, the inverted image of the letter “A”. :D An inverted image results in the application of FFT twice because doing so will result in the introduction of a negative sign in the x’s and y’s. If you want to get your original image back from a Fourier transformed image, do the inverse Fourier transform. :)

Part B. Simulation of an imaging device

We’re asked to create an image of the letters “VIP” and this will be our object to be imaged. I used Arial font because according to the activity manual, sans serif fonts are sharp.

object

We also created a white circle on a black background and this represents the aperture of a lens.

aperture

The image of the “VIP” can be obtained by convolving the object with the transfer function of the imaging system. Convolution is done by taking the product of the FFT of the grayscaled object with the fftshifted aperture and then inverse fourier transforming. The aperture image doesn’t need to be FFT-ed because it is already in the Fourier Plane.

T = gray_imread('C:\VIP.bmp');
A = gray_imread('C:\circle.PNG');
Ar = fftshift(A);
Ta = fft2(T);
FRA = Ta.*Ar;
IRA = fft2(FRA);
imshow(abs(IRA), []);
The output is:

r = 0.7

Note that it is inverted and this is true for real images.

Making the size of the aperture smaller, we get…

r = 0.4

r = 0.25

r = 0.1

The image quality reduces when the lens aperture becomes smaller and smaller because less and less rays are able to pass through it. The more rays the lens can collect, the better the image quality.

Part C. Template Matching using correlation

Template matching is basically a type of pattern recognition in which it will determine matches between the test object and the template.

For this part, we created the white texts in black background of: “THE RAIN IN SPAIN STAYS MAINLY IN THE PLAIN.”

text

and our template will be the letter “A” with the same font style and size as in our text:

template

We get the correlation of these two by multiplying the FT of A and the conjugate of the FT of the text and then inverse Fourier transforming by using ifft().

T = gray_imread('C:\text.PNG');
A = gray_imread('C:\A.bmp');
FT = fft2(T);
FA = fft2(A);
FTconj = conj(FT);
FRA = FA.*FTconj;
IRA = ifft(FRA);
imshow(abs(IRA), []);
This is what I got:

correlation of text and template using ifft

It looked like the quadrants were reversed diagonally so I applied the fftshift after inverse FT-ing:

imshow(fftshift(abs(IRA)), []);

shifted correlation

Now it looks inverted… so I tried using the fft2 instead of ifft:

IRA = fft2(FRA);
imshow(abs(IRA), []);
correlation of text with template using ifft2

and fftshifting…


imshow(fftshift(abs(IRA)), []);

shifted correlation

Now this looks more correct. The original text could be made out from this image but there seems to be bright spots were the letter “A” is present. Therefore the bright spots represent a match since these are the positions were the correlation is highest.

I thought… what if the template is a “P” and there are “B”’s in the text… what would happen? So I made my own text:

text 2

And my own template:

template 2

And the correlation is…

limitation of method

It can be seen that despite there is only one capital “P”, there are multiple bright spots. This is because the other letters like “B” looks very similar to P except that it has an extra part at the bottom. The other letters also have parts that are similar to “P” so they have a high correlation. Therefore this shows the limitation of the technique.


Part D. Edge detection using the convolution integral

We were asked to make a 3x3 matrix pattern of edges such that the sum of all the elements is zero. Then we convolved this with the "VIP" image using imcorrcoef():

For the matrix:

[-1 -1 -1

2 2 2

-1 -1 -1]

We get:

convolved image

We can see that the horizontal edges of the image are brighter. Also note that the matrix has the same values horizontally. What this does it that it scans the image and tries to match its edges with the matrix.

For the vertical matrix:
[-1 2 -1
-1 2 -1
-1 2 -1]

We get:

convolved image

This time, the vertical edges of the image are brighter :D

For the spot pattern:
[-1 -1 -1
-1 8 -1
-1 -1 -1] :

convolved image

This time, all of the edges of the image are bright. This is because in the pattern, all of the edges have the same value.

The code for this is:
T = gray_imread("C:\VIP.bmp");

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

F = imcorrcoef(T, pattern);

imshow(F, []);

And that wraps up the activity. :)

For the score, I give myself a 10/10 for producing the required output and understanding the lesson. Plus 2 points for testing the limitations of the technique of correlation, which gives a total of...

Score: 12/10

Lastly, I would like to acknowledge Dr. Soriano for the helpful discussions. :D


- Dennis

References:
1. M. Soriano, "A6 - Fourier Transform Model of Image Formation"

No comments:

Post a Comment