Thursday, July 23, 2009

Activity 8: Morphological Operations

An image contain informations that can be extracted using image processing. Usually before image processing, we try to enhance the input through morphological operations. Morphology refers to shape and structure manipulation, thinning, expanding, closing of holes and the like. Because of its versatility,morphological operations find many applications in area measurement, counting, and tracking to name a few [1]. Morphological operations make use of set theory. A brief rundown of set theory is available in source[2].

In this activity, we're going to demonstrate two basic morphological operations, dilation and erosion. We proceed by defining dilation and erosion using set theory and provide examples using different images. To futher understand dilation and erosion better, the reader is recommended to predict the outcome of dilation and erosion on a piece of paper before programming it on a computer.

DILATION
From our activity manual, "dilation of A by B denoted by A dilation B is defined as".
It is important to note that dilation of A by B is the set of all Z's such that B translated by Z union A is not an empty set. B here is called the structuring element. The figure above demonstrates this effect of dilation. In general, we can say that dilation expands the image by the shape of B.

In this activity we use images of square (50×50) , a triangle (base = 50 , height= 30), a circle radius 25), a hollow square (60×60, edges are 4 pixels thick), and a plus sign (8 pixels thick and 50 pixels long for each line). The structuring elements used are 4 x 4 ones, 2 x 4 ones, 4 x 2 ones and a cross. Below are the result of my predictions and the corresponding dilated images.
  • my predictions were mostly correct, except for the dilation of a cross using a cross as structuring element. I failed to account for the corners of the cross.
  • Results below can be summarize in general as follows:
    • 4x4 ones just increase the size uniformly adding 3 pixels
    • 2x4 makes the image wider (horizontally) by about 3 pixels
    • 4x2 makes the image longer (vertically) by about 3 pixels
    • cross adds 2 pixels on all sides except on corners
  • Or as a rule of thumb, dilation expands the object similar to the shape of the structuring element (see definition above).
Dilation of different images (leftmost) by different structuring elements (columns 2 to 5)

EROSION
From our activity manual, "The erosion of A by B is the set of all z's such that B translated by z is contained in A."
Similar to dilation, the effect of erosion is to reduce the image by the shape of B.
Summarize below are my predictions and the result of my simulation.
  • I failed to predict erosion of the hollow figure using a cross (i.e., presence of 4 dots) and the erosion of the cross using a cross as structuring elements.
  • similar to the dilation, the effect of erosion can be thought of as eroding the shape of the element by the structuring element.
Erosion of different images (leftmost) by different structuring elements (columns 2 to 5)

I give myself a grade of 10 for performing the activity on time and for predicting the results quite well.

I want to acknowledge master, jaya, thirdy for the laughs while programming the code and predicting the results of the erosion and dilation. Miguel for the gimp and the incident about his computer :-p.

References
[1] AP 186 Activity 8 manual
[2] http://en.wikipedia.org/wiki/Set_(mathematics)

Friday, July 17, 2009

Activity 7 Enhancement in the Frequency Domain

Filtering in Fourier Space

Signal processing as the name implies is an area that deals with analyzing and processing of signals. A major concern in signal processing is the signal to noise ratio. By definition, anything that you do not want is considered noise [1]. One of the methods use in signal processing is filtering in Fourier space. In essence, if we know the characteristic frequency of a signal we can use a filter to remove unwanted frequencies and enhance the signal thereby increasing the signal to noise ratio. In this activity, we demonstrate basic use of filtering in Fourier space to remove unwanted signals.

Activity 7.A: Convolution Theorem
Before we dwell on filtering, we must first familiarize ourselves with the convolution theorem. This is a crucial step since the process of filtering in Fourier space is basically just a convolution. For example, the convolution of a Dirac delta is just equal to the function itself on the location of the Dirac delta. Below are Fourier Transform images of different patterns.
FT of two dots is a sinusoid with a distinct frequency(Dirac delta at f).

FT of circles of different radius. As we increase the radius of the circle the FT decreases in radius. This is expected. i.e., similar to the rect function since FT is anamorphic.

FT of squares of different sides. Again as we increase the length of the side, the width of the FT decreases. In fact, the limit (side -> inf) will result to a dirac delta (point).

FT of gaussian of varying variance. The unique property of a gaussian is that its FT is also a gaussian. Again similar to square and cirlces, as you increase the variance of a gaussian its FT decreases in variance.

Comparing the imaginary and real part of gaussian and inverse gaussian.
click on the image to ZOOM
Gaussian of varying variance with the (a)[leftmost] image of gaussian (b) its real part (c) imag part (d) and FT (e) [bottom] inverse gaussian image (f) real part of inv gaussian (g) imag part of inv gaussian and (h) FFT of inv gaussian.

Observe that the real part of the gaussian and inverse gaussian are the same.

Activity 7.B Fingerprints: Ridge Enhancement

One of the use of filtering in Fourier space is through ridge enhancement of fingerprints. The process can be basically summarize as follows
  • the FT of the image (i.e, fingerprint - input) was obtained. In order to enhance the visibility of the frequencies, the FT was obtained in log scale.
  • The obtained FT was analyzed and was used as a template to create a mask that will enhance the frequencies of ridge while decreasing other unwanted frequencies.
  • It must be noted that use of binary mask is not too adviseable as this will pick only the desired frequencies but not enhance them relative to the other frequencies. Use of gradient mask or grayscale mask is more adviseable. If we know exactly the frequency of the object we want, we can maximize the pixel value of the mask at that location while blurring or decreasing the pixel value of other frequencies that we do not want.
  • In this example, the author was having a hard time separating the background from the frequency of the ridges. As as a solution, I use a gradient mask on the frequencies of the ridges while blurring it as you go away from the signal. Similarly for the zero order (background), a gradient mask was used which is darker at the center and increasingly bright moving away from the center. This was done because complete removal of the zero-order will not result to a very good reconstruction.

For our purposes, this reconstruction is not the best reconstruction that could be achieve but its a start. The ridges are well defined and darkening of the background provided additional contrast. It is recommended however that further refining be done for better reconstruction.

Activity 7.C Lunar Landing Scanned Pictures: Line Removal
From our previous discussion of FT, we know that the FT of vertical lines are two points symmetric about the center along the horizontal axis. The picture of the lunar above was filled with vertical lines resulting from stitching of several digital "framelets" to obtain a composite image. We can remove this in Fourier space by filtering the image using a mask by filtering the frequencies along the horizontal direction. (see mask used)

Activity 7.D Canvass Weave Modelling and Removal
Similar to ridge enhancement we can remove the pattern created by the canvass weave using filtering in Fourier space. Observe that the canvass weave looks a lot like corrugated sinusoids, thus, we must remove frequencies along the vertical and horizontal side. Also by virtue of rotation, other frequencies might also be evident around the center. The presence of dots in the masked pattern was due to thresholding in scilab (i.e, img(img~=0)=1).

For this activity, I give myself a grade of 10 for obtaining the requirements needed to complete the activity. However, I admit that the reconstructions I presented above are not the best reconstructions. Further research can be devoted to this area to provide better algorithms for filtering and pattern recognition.

I would like to acknowledge Irene and Miguel for all the help they've given while doing this activity. (jokes, company and intellectual discussions)

References
[1] http://en.wikipedia.org/wiki/Noise
[2] Applied Physics 186 Activity 7 Manual.

Thursday, July 9, 2009

Activity 6: Properties of the 2D Fourier Transform

Fourier Theorem states that any function can be expressed as infinite sum of sinusoids of different frequencies. In imaging, this translates to finding the spatial frequencies of an image. In 2D FT, rotation of the image results to rotation of the resulting FT, we will investigate this property in a while but let us first familiarize ourselves with FT of different patterns [1]

Activity 6.A: Familiarization with FT of different 2D patterns
Below is the FT of different patterns. A quick way to check if the result is correct is to imagine placing a mask(aperture) in front of a light source and observe the image in a screen far away. The resulting FT should have the somewhat the same symmetry as the object.
















Observe the difference with the square above, i.e. similar to subtracting terms in your diffraction. In Fresnel diffraction, this amounts to removing zones in your image.
















Textbook example of two slits along the x-axis (see Hecht, section diffraction on Fraunhoffer diffraction)








The FT of two dots is a sinousoid. This is textbook example of Young's double slit experiment.

Activity 6.B: Anamorphic Property of the Fourier Transform









Sinusoid of frequency 4 generated using sin(2*pi*f*x).








Sinusoid of frequency 8. The dots are more widely separated. Imagine placing a frequency axis on the y-axis above. The higher the frequency of the sinusoid, the farther apart the dots.

In digital imaging, there is no negative values, adding a bias to an image results to the presence of zero order. This is exactly what happens when we add bias to the image of the sinusoids above.
Sinusoid of frequency 4 with bias. The center dot is the zero-order frequency. In electronics, we can imagine a DC bias or in imaging, the image is offset by the background.



Suppose then that we took a picture of an interferogram, we can obtain the actual frequencies of the object by adding a constant bias to the image (i.e., min value). Or we just obtain the FT and neglect the zero order frequency. However, if the resulting interferogram has non-constant bias then we can add a filter to obtain the desired frequencies. For example, suppose that the image was added with very low frequency sinusoids. We can obtain the frequencies by obtaining the FT of the image and multiply the resulting FT with a high pass filter (i.e, to remove the low frequencies) and then obtain the inverse FT to get the final image of the object. Depending on the bias, we can adjust the filter to obtain the desired frequencies.

In 2D FT, rotating the sinusoids result to a rotated FT.








Rotated sinusoid with its corresponding FT. Observe that the resulting FT is also rotated in the same direction as the object.








Fourier transform of combination of sinusoids. Left: multiplication of two corrugated roofs, in the X and Y direction and right: FT of the object, 4 dots of the same distance signifying same frequency in the X and Y direction.








We added a rotated sinusoid to the corrugated image above using different frequency (f=16 and rotated for 90 degrees). Observe the presence of the 4 dots similar above and the addition of two dots.









We added a different rotated sinusoid using different frequency (f=12 and rotated for 30 degrees).








Added rotated sinusoid of f=8 and rotated for 60 degrees.








Combination of all the above rotated sinusoids. Here we can see that the result is just the addition of all the FT of the different rotated sinusoids. This is because FT is a linear transform, i.e.,
let X=A+B+C then F{X} = F{A} + F{B} + F{C}

Here, we investigated the different properties of the 2D Fourier Transform, in particular
  • rotation of the object results to a rotated FT
  • FT is a linear transform
  • FT obtains the spatial frequencies of the image
For this activity, I give myself a grade of 10 for doing the required objectives.

I would like to acknowledge miguel and martin for useful discussions and master for knowing the spelling of Hecht =).

References:
[1] Activity 6 Manual


Tuesday, July 7, 2009

Activity 5: Fourier Transform Model of Image Formation

Lens as a Fourier Transform

Activity 5.A Familiarization with discrete FFT
Using the built-in FT of scilab, fft2, we are going to obtain the FFT of different patterns.







Left: image of circle, right: Fourier transform of circle. As expected, the FT is a bright spot most intense in the center, imagine imaging uniform disk of same intensity.







Left: image of letter 'A' and right: Fourier tranform of circle. The resulting FT has higher frequency components as expected from the shape of letter A.

Activity 5.B Convolution: Simulation of an imaging device
The representation of an image using an imaging device is not a perfect reconstruction but is a "smeared/convolve" image of the original image. Consider the equation below in frequency space
H=FG
Where F is the transfer function of the imaging device and G is the original image. The convolution of f and g results to the image we actually see. In frequency space, by the Convolution theorem, this is just the multiplication of the linear transform (i.e, Laplace of Fourier) of f and g. We simulate an imaging device using an aperture as our transfer function (i.e, this can be modeled as a lens) and convolve to an image of our choice. Below is the image of letters "VIP" which we are going to image using different sets of apertures.
Original image that we will image.








Left: Convolution of the original image using the aperture on the right. Observe that the resulting image is blurry (i.e., diffraction effect). We can imagine in our real life model, i.e lens, that the aperture did not collect sufficient amount of photons resulting to blurry image or the other way to put it is that the NA (numerical aperture) of the lens is very low.








Left: Convolution of the FT of the aperture in the right with the original image. Observe the significant change in resolution when we increase the size of the aperture. (increase NA)








Left: Convolution of the FT of the aperture in the right with the original image. Further increase in the aperture results to better resolution.








Left: Convolution of the FT of the aperture in the right with the original image. The largest apertuer that we can construct. Although observe that even with the highest NA, we cannot replicate the original image (i.e, presence of blurring at the edges) this is because in the mathematics of Fourier Analysis, in order to perfectly reconstruct we must have infinite coefficients to represent a function, but in our case, we are limited to discrete frequencies.

Activity 5.C: Template Matching using correlation
Correlation is basically finding the overlap of two functions. Thus, it can be used for pattern matching.








"The rain...": Image that we will correlate with the image with letter 'A'. The resulting image results with the all the letter 'A' in the image to have high intensity (appear white in the result).


Activity 6.D: Edge Detection
Using similar concept as above, we can correlate an image with different patterns and thus highlighting those parts that we need depending on the pattern.









Edge detection using the pattern in the right. As observed, the pattern can be deduced to detect all point in the edges.










Edge detection using a vertical pattern, as expected, all the vertical parts of the letter VIP are highlighted.









Edge detection using horizontal pattern. The horizontal edges are highlighted.
It must be noted that the sum of the matrix in the pattern is zero.

For this activity, I give myself a grade of 10 for performing all the requirements needed.