Wanna Eat Six Kamatis

ACTIVITY 19 Restoration of Blurred Image

2009-10-12T08:53:00.000-07:00

In this activity, we demonstrate the degradation process and the restoration of the degraded image. A diagram is shown in Figure 1 to illustrate the process of degradation and then restoration of an image. The degradation part is equivalent to equation 1 where G, H, F and N are the Fourier transforms of the degraded image, degradation function, original image and noise, respectively. We used the model of motion blur as our degradation function (see equation 2). The assumption of this model is that the blurring is due to linear motion between the image and the sensor during image acquisition. In equation 2, T is the duration of the exposure, a and b are the total distances for which the image has been displaced in the x- and y-direction, respectively. In addition to degradation, noise was also introduced to the image in the form of Gaussian. The equation for this type of noise was already shown in the previous activity. The restoration process is through minimum mean square error (Weiner) filtering. Equations 3 and 4 give us the Fourier transform of the restored image. So, the restored image can be shown by getting the inverse Fourier of these transforms. Note that u and v are just the indices of the pixels in the image.

Figure 1.

Equation 1.

Equation 2.

Equation 3.

Equation 4.

Figure 1.

The following are the investigations I did in relation to the degradation and restoration of the image shown in Figure 1.

1.) The value of T in H (degradation function, equation 2) was varied.
Figure 2 shows the degraded and restored images for different values of T. As you can see, the only detectable difference in the images but not that obvious is that the image becomes whiter as the value of T is increased. This difference becomes more obvious when the images are restored as shown in Figure 2. This is because T is the duration of the exposure. So, the longer the time the image is exposed, the whiter the image will be.

2.) The values of a and b (same value) were varied.
Figure 3 shows the degraded and restored images for different values of a and b (same value). a and b are the total displacement in the x- and y-direction. So, the larger the values of these variables are,the more blurry the image will be. Moreover, the blurriness is equal in the two directions since a and b are equal. The more blurry the image is, the harder it is to restore. As you can see in Figure 3, the level of restoration decreases as the values of a and b increase.

3.) The values of a and b (different values) were varied.
Figure 4 shows the degraded and restored images when a and b (different values) were varied. Since a and b are not equal anymore, the blurriness is not the same in the two directions (x and y). As you can see, when a is larger(smaller), the degraded image appears to be stretched horizontally (vertically). Comparing the restored images, it can be observed that the lines (contour) of the texts are darker when a is larger than b.

4.) The standard deviation and mean in the Gaussian noise were varied.
Figure 5 shows the degraded and restored images for different values of the standard deviation and mean. The larger the value of these parameters are, the noisier the image is. Similar to the results of varying a and b but of equal values, it is harder to restore the image when it is noisier.

4.) The value of K in equation 4 was varied.
This time, we did not vary the degradation process but the restoration process. Figure 6 shows the restored images for different values of K. When the value of K is at extreme 0 or 1, the filter failed to restore the image. When it is near 0, the blurriness is removed but the noise remains. In fact, the noise already covers the entire image that it is not visible anymore. On the other hand, when it is near 1, the noise is removed but the image becomes more blurry. Thus, the value of K must be properly chosen to produce the best restored images. Compared to the restored image using equation 6, equation 7 produces images that are still noisy. This is because this equation assumes that the noise is spectral white. However, in our case, the noise we used is Gaussian. This is why equation 6 has better results because it is able to use the right noise.

Figure 2.

Figure 3.

Figure 4.

Figure 5.

Figure 6.

I would give myself a grade of 10 for this activity.

ACTIVITY 18 Noise Modeling and Basic Image Restoration

2009-10-08T07:48:00.001-07:00

In this activity, we explored the different types of noise and used the common filters to clean the noisy images. I used Figure 1 as my original image. The noise we introduced on the image are the common types of noise, namely, Gaussian (normal), exponential, gamma, Rayleigh, uniform and impulse (salt& pepper). These noises are described in equations 1 to 6. The resulting noisy images are shown in Figure 2. On the right side of the images are the histogram (PDF) of the noisy images. Given a noisy image with unknown type of noise, one can then determine the type of noise from its PDF. However, it must be noted that the images I am talking here are grayscale images.

Figure 1.

Figure 2.

Equation 1. Gaussian (normal) noise.

Equation 2. Rayleigh noise.

Equation 3. Erlang (gamma) noise.

Equation 4. Exponential noise.

Equation 5. Uniform noise.

Equation 6. Impulse (salt & pepper) noise.

The filters I used are the following: arithmetic mean filter, geometric mean filter, harmonic mean filter and contraharmonic mean filter. Equations 7 to 10 illustrate how these filters work. Figure 3 shows the cleaned images after applying the different filters. As you can see, no filter was able to perfectly restore the noisy images to the original image. For different types of noise introduced, a filter cleans the noisy images differently. Consider the cleaned images when ageometric mean filter was used (3rd row of Figure 3). The image with impulse noise obviously has a different cleaned image as compared to the other noises. Arithmetic mean and geometric mean slightly clean the image but it can be observed that there is partial blurring. Harmonic mean filter has the best result in some images (gamma and exponential) but it also fails to restore some images (normal and uniform). I think this is due to the type of distribution these noises produce. Gamma and exponential have similar PDF, as well as normal and uniform. The cleaned images using contraharmonic filter is shown in Figure 4. Recall equation 10. When Q is +/-, salt(white)/pepper (black) noise is removed. This is why the images is dark/bright when Q is +/-.

Equation 7. Arithmetic mean filter.

Equation 8. Geometric mean filter.

Equation 9. Harmonic mean filter.

Equation 10. Contraharmonic mean filter.

Figure 3. The first row is the set of images with noise incorporated in the following sequence: salt & pepper, exponential, normal (Gaussian), gamma, uniform. In the succeeding rows are the resulting images after applying the arithmetic filter, geometric filter and harmonic filter, respectively.

Figure 4. The first row is the set of images with noise incorporated in the following sequence: salt & pepper, exponential, normal (Gaussian), gamma, uniform. In the succeeding rows are the resulting images after applying the contraharmonic mean filter with Q (-) and Q (+), respectively.

In equations 7 to 10, notice that the computation of the new pixel values is confined in a window of size m x n. I investigated how the cleaning varies for different window sizes. Figure 5 shows the cleaned images. As you can see, more noise is removed when the window size is bigger. However, the images become more blurry also. So, the window size must be properly chosen such that enough noise is removed and the restored image is not so blurry.

Figure 5. The resulting images after applying all the filters with different window sizes
(1st row - 3 x 3, 2nd - 5 x 5, 3rd - 9 x 9) in one of the noisy images.

I also tried applying the filters to the noisy images I downloaded from the internet (see Figure 6). From their PDFs,it can be inferred that the noise is Gaussian. The cleaned images are shown in Figures 7 to 10. As you can see, the restoration is still not perfect. The results are just the same as the cleaning of the images in Figure 2.

Figure 6. PDFs of the images.

Figure 7.

Figure 8.

Figure 9.

Figure 10.

I would give myself a grade of 10 for this activity.

ACTIVITY 17 Photometric Stereo

2009-10-08T07:45:00.000-07:00

In this activity, we used the technique photometric stereo in constructing the 3D shape of an object. This technique works under the assumption that the source is at infinity and so, the radial waves reaching the surface appear as planar waves. Moreover, it is assumed that the intensity captured by a camera at point (x,y) is directly proportional to the brightness of the surface at that point.

By capturing multiple images with the sources at different locations, one can estimate the shape of the object. The sources can be represented by matrix V in equation 2 where Vn1, Vn2 and Vn3 are the component of the source n in the x-, y- and z- direction, respectively. If we know the intensity of the surface image captured by source n, then we can solve for g as illustrated in equation 3. The surface normals can then be calculated by normalizing g with its length (see equation 4). The surface elevation, z, is a function of x and y. The partial derivatives of this function with respect to x and y are shown in equation 5. Therefore, the surface elevation is given by equation 6.

In this activity, we used four sources and the surface images captured by these sources are shown in Figures 1 to 4. After implementing equations 2 to 6, we were able to generate a 3D shape of the object as shown in Figure 5.

Figure 1.

Figure 2.

Figure 3.

Figure 5.

ACTIVITY 16 Neural Networks

2009-10-08T07:32:00.000-07:00

In this activity, we classify the patterns presented in Activity 14 using artificial neural networks. An advantage of this method over the algorithms reported in the previous activities is that one does not need heuristics and recognition rules to perform classification.

A neural network is a computational model of the neural structure of the brain. As implied by the name, it is a network of neurons that are either sets of input values (xi) and associated weights or functions that sum the input values according to their weights and map the results to an output (y). See Figure 1 for illustration. These neurons are organized into layers as shown in Figure 2.

Figure 1.

Figure 2.

The key features of neural networks are:
(1) the evaluation of the patterns one at a time and
(2) the manner of learning through comparison of their classification with the known actual classification of the pattern.
The learning process of a neural network is iterative. Moreover, the classification process is continuously modified based on the errors fed back from the previous classification stage. The modification is through the adjustment of weights associated with the input values in order to have a more accurate prediction of the class of the pattern.

We are lucky enough that SciLab has a toolbox for artificial neural neutworks. We need not worry anymore of generating a code for the learning process of a neural network. All we need is initialize the necessary input parameters. A code made by Jeric Tugaff was used as a guide in understanding what the needed parameters are. Below is the discussion of the code. We also used the blog of Cole Fabros as a reference.

SciLab Code:
rand('seed',0);
//this is to ensure that it has same starting point each time

N = [a,b,c];
//definition of network: a - number of neurons (features) in the input layer, b - number of
hidden layers, c - number of outputs/classes to be identified
// in this case, a = 3, b = 2 and c = 4

x = [];
x = x';
//feature vectors of the training set (must be an m x a matrix, a - total number of patterns)
//in this case, 20 x 3 since there are 4 classes of 5 samples each and 3 features are considered
(see Table 1)
//Note: If the features have very large values, these must be normalized. Otherwise, the results
would be wrong or the neural network won't work properly.

Table 1.

y = [];
//desired output/known actual classification of the patterns (must be a c x m matrix)
//in this case, 4 x 20 since members of the 4 classes are to be determined simultaneously
//value is either 1 or 0, 1 if right classification and 0 if wrong classification
//in this case, according to the order of patterns listed in Table 1, the desired output must
be similar to the matrix shown below (1st row - members of orange class, 2nd - nagaraya,
3rd - grapes, 4th - eggnog).

lp = [s,t];
//s - learning rate; t - threshold for the error tolerated by the network
//in this case, s is varied while t is always 0

W = ann_FF_init(N);
//initialization of weights

T = r;
//training cycles: r - number of iterations
//in this case, r is also varied

W = ann_FF_Std_online(x,y,N,W,lp,T);
//variables are already explained above
//adjusted weights after T iterations

ann_FF_run(x,N,W)
//testing the neural network, outputs its classification of the training patterns

test = [];
//feature vectors of the test set (must be an m1 x a matrix, m1 - total number of patterns)
//in this case, same as training set size: 20 x 3 matrix (see Table 2)
//Note: If the features have very large values, these must be normalized. Otherwise, the results
would be wrong or the neural network won't work properly.

Table 2.

class = ann_FF_run(test,N,W);
class = round(class);
//testing the neural network with a set of data it is not trained
//outputs its classification of the test patterns
// in this case, recall: 1st row - oranges, 2nd - nagaraya, 3rd - grapes, 4th - eggnog

oranges = find(class(1,:) == 1)
nagaraya = find(class(2,:) == 1)
grapes = find(class(3,:) == 1)
eggnog = find(class(4,:) == 1)
//outputs the data indices of the members of the said classes

First, I will disscuss the training results of the neural network. As mentioned above, the output must either be 1 or 0: 1 if the classification is right and 0 if not. But as you can notice in Table 3 and 4, the output values are not 1 or 0 but values that are near 0 and 1. This means the neural network had not learned enough to be precise in the classification of the patterns. However, the obtained values are already acceptable as classification of the patterns.

Table 3. Prediction after applying neural networks. Different learning rates were tried and compared.

Table 4. Prediction after applying neural networks. Different numbers of training cycles were tried.

Before proceeding with the discussion of the training results, I want to note that the output of the code is a 4 x 20 matrix and not just 4 x 4 (size of the tables). The reason why the tables are just 4 x 4 because data of the members of one class are averaged as a summary of the results. That is the output values of the 5 patterns belonging to the classes oranges, nagaraya, grapes and eggnog are averaged.

As an investigation, I varied the learning rate (s) and number of training cycles or iterations (r) to see if the output values get nearer to 1 and 0. Table 3 is the summary when the learning rate is varied while Table 4 is the summary when the number of training cycles is varied. Results show that the output values get nearer to 1 and 0 if both parameters are increased.

The next thing I did is test the neural network to a set of feature vectors it is not trained. The classification of the neural network is correct, i.e., the value close to 1, if it has the same row and column label. Looking at the values in Table 5, we can say that the neural network was able to classify correctly all the patterns (100%) even the data it was not trained.

Table 5.

As another investigation, I tried disarranging the test set as illustrated in Tables 6 and 7 to test whether the neural network is dependent on the order of the patterns. Table 6 is disarranged in such a way that the eggnog and oranges were interchanged in their positions. Table 7, on the other hand, is a random arrangement of the patterns. Tables 8 and 9 are the resulting classification of the patterns for the arrangement of data in Tables 6 and 7, respectively. Results show that using the training parameters mentioned above, the neural network was still able to classify correctly all the patterns (100%).

Table 6.

Table 7.

Table 8.

Table 9.

Since I was able to classify correctly all the patterns and then give a nice discussion
above (I think), I give myself a grade of 10 for this activity.

ACTIVITY 15 Linear Discriminant Analysis

2009-10-07T06:59:00.000-07:00

For this activity, we did pattern recognition using linear discriminant analysis (LDA). The patterns I used are the images shown in the previous activity. I also used the same features and method of determining the feature values. The images were also divided into two sets: training set and test set.

LDA can be used to classify patterns if the classes can be assumed to be linearly separable, i.e., classes can be separated by a linear combination of the features. Since three features of the pattern were used, the separator must be a plane.

In LDA, two variables are needed:
(1) dependent variable (y) which is the class of the pattern and
(2) independent variable (x) which is the feature of the pattern.
The size of y must be n x 1, where n is the total number of patterns. Moreover, x must be of size n x 3; 3 since there are three features. Same row in x and y represent one pattern. The diagram below shows the sequence of the necessary parameters needed to be calculated in LDA.

In evaluating f, all the variables except those with subscript T were calculated using the training set. The patterns were classified by first calculating f for all classes. It was then assigned to the class with the maximum f.

Tables 1 and 3 show the feature vectors of the patterns. Table 2 and 4 are summaries of the calculated f for all classes. The column of the highlighted f (red color) is the classification of the pattern. As you can see, LDA was also able to correctly assign all the patterns to their right classes (100%).

Figure 1. Feature vectors (green, red, area) of the training images of oranges, nagaraya, grapes and eggnog.

I give myself a grade of 10 for this activity.

ACTIVITY 14 Pattern Recognition

2009-10-06T09:57:00.001-07:00

In the succeeding 3 activities, we generated codes that can be used in pattern recognition using different algorithms. For this activity, I discuss the results of the classification when the minimum distance algorithm is used.

The patterns I used are images of oranges, nagaraya, grapes and eggnog as shown in Figures 1 to 4. The following features were determined from these patterns: redness, green-ness and area. Each pattern was represented by a feature vector, which is an ordered set of the feature values. The patterns were classified according to their class, namely, orange, nagaraya, grape and eggnog.

Figure 1. Nagaraya Training and Testing Images.

Figure 2. Orange Training and Testing Images.

Figure 3. Grapes Training and Testing Images.

Figure 4. Eggnog Training and Testing Images.

Determination of the Feature Values

1. & 2. Redness and Green-ness

First, a patch consisting of pure red, pure blue and pure green (primary colors) strips was created (see Figure 5). The patch was used in the image segmentation process. An advantage of creating a patch is there is no more need to select the portion of the pattern for the determination of the RGB values. Since it is our aim to approximate the pattern recognition capability of the humans, it is better that it is not the human who gets to decide what portion of the pattern will be considered. The code for the image segmentation (parametric, assuming Gaussian distribution) process is shown below. Since the patch used contains pure primary colors, then finding the probability that the pixels in the pattern have chromaticities r and g (p_r and p_g) is the same asdetermining how red (redness) and how green (green-ness) the pattern is. The first two rows of Figures 6 to 9 are the images of the p_r and the p_g of the patterns. As you can see, only when there is a comparable difference in the R or G values among the pixels in the image will there be a clear distinction between the pattern and the background. If there is no significant difference, then the image will just appear black at all points like the p_g of most patterns. The third row in these figures is the binarized image of the p_r*p_g of the patterns. The probabilitieswere multiplied and binarized in order to partially, if not totally, segment the pattern from its background. Finally, the redness and green-ness of the patterns were measured by getting the mean of the p_r and p_g, respectively, of the portions in the image where the binarized p_r*p_g is equal to 1 (pattern only without considering the background).

SciLab Code:
patch = imread('F:\Documents\5th year\AP186\activity 14\patch.jpg');

I = patch(:,:,1) + patch(:,:,2) + patch(:,:,3);
Pr = patch(:,:,1).*(I.^(-1));
Pg = patch(:,:,2).*(I.^(-1));
m_r = mean(Pr);
m_g = mean(Pg);
s_r = stdev(Pr);
s_g = stdev(Pg);

fname = 'F:\Documents\5th year\AP186\activity 14\orange\orange1.jpg';
image = imread(fname);

Int = image(:,:,1) +image(:,:,2) + image(:,:,3);
Int(find(Int==0))= 100000;
Ir = image(:,:,1).*(Int.^(-1));
Ig = image(:,:,2).*(Int.^(-1));

p_g = ((1/s_g)*(1/sqrt(2*%pi)))*exp(-((Ig - m_g).^2)/(2*(s_g^2)));
p_g = 1-p_g;

p_r = ((1/s_r)*(1/sqrt(2*%pi)))*exp(-((Ir - m_r).^2)/(2*(s_r^2)));
p_r = 1-p_r;

prod = im2bw(p_r.*p_g,0.035);
pmG = mean(p_g(find(prod==1)));
pmR = mean(p_r(find(prod==1)));
area = sum(prod);

Figure 5. Patch consisting of the three primary colors: red, green and blue.

Figure 6. Training images of the nagaraya based on its (a) red content and (b) green content.
(c) BW images of the nagaraya. Note: (a) - 1st row, (b) - 2nd row, (c) - 3rd row.

Figure 7. Training images of the oranges based on its (a) red content and (b) green content.
(c) BW images of the oranges. Note: (a) - 1st row, (b) - 2nd row, (c) - 3rd row.

Figure 8. Training images of the grapes based on its (a) red content and (b) green content.

Figure 9. Training images of the eggnog based on its (a) red content and (b) green content.

3. Area
The area of the patterns were determined by simply getting the number (sum) of 1s in the binarized p_r*p_g (see last line of code above). Looking at the binarized images in Figures 6 to 9 (third row), you can see that there are small holes in some parts or excess regions. But since these are only few (much less than the total area), the values I got are still good approximations of the area of the patterns.

After determining the feature vectors of all the patterns, I divided the images into a training set and a test set. In the training set, the average of the feature vectors of all the patterns belonging to one class were determined. Table 1 is the summary of the mean feature vectors of the different classes.It was then used in the classification of the patterns in the test set using the minimum distance algorithm, which uses the equations given below. Also shown below is the simple code implementing the said algorithm. The algorithm basically computes the distance (or difference) between the feature vector of the test pattern and the mean feature vectors in the training set. The class of the mean feature vector that gives the minimum distance is the classification of the test pattern.

SciLab Code:
for k = 1:4,
distance(k) = sqrt((FVs(:,k) - test)'*(FVs(:,k) - test));
end;
classification = find(distance == min(distance));

Table 1. Feature vectors of the objects as determined from the training images.

The output of the code (classification of all the test patterns) is not presented anymore since it was just a matrix of numbers 1, 2, 3 and 4 corresponding to the four classes (oranges, nagaraya, grapes and eggnog). But I was able to classify correctly all the test patterns, and even the training patterns (100%). This means the features I chose are good separators or distinctions of the four classes.

I give myself a grade of 10 for this acitivity.

ACTIVITY 13 Correcting Geometric Distortions

2009-10-06T09:27:00.001-07:00

In this activity, we generated a SciLab code that can be used to correct distortions, specifically geometric distortions, in an image. These distortions are usually due to the manner the sensor in a capturing device detects light. Any straight line in the object space is perceived by a sensor as a curved line. The two common observable distortions are the barrel distortion and pincushion distortion. Barrel distortion happens when the edges of the image seem to be bent outwards. The image is bulging but smaller than the undistorted image. On the other hand, pincushion distortion occurs when the edges of the image seem to be bent inwards. The boundaries are expanded, so the image is bigger than the undistorted image. However, even with the distortions, the center of the image usually remains undistorted. See Figure 1 for the illustrations of the aforementioned distortions.

Figure 1. Left: undistorted; center: with barrel distortion; right: with pincushion distortion.
(Source: http://toothwalker.org/optics/distortion.html)

In generating the code, a checkerboard image with barrel distortion is used as the sample image as shown in Figures 2 and 3. The correction of the image was done on the two image properties, pixel coordinates and graylevel values. The pixel coordinates were corrected by finding the transformation function for mapping the pixel coordinates in the distorted image to the undistorted image. Moreover, the graylevel values were corrected using bilinear interpolation. A detailed discussion of the correction process can be found below.

Figure 2. Original Image
(Source: http://immersaview.com/images/sol7smile.png)

Figure 3. The cropped portion of the image that was restored to its undistorted form.

Before correcting the image, it is important to have the correct pixel coordinates. In the sample image (checkerboard), these pixel coordinates correspond to the corners of the rectangles. For images with nonperiodic objects/structures, gridlines need to be created in the image, as well as in the reference (undistorted) image, such as those shown in Figure 4. The pixel coordinates will be the intersections of the gridlines.

The pixel coordinates in the sample image were determined after isolating the corner points of each of the white rectangles in the checkerboard. Several image processing techniques were applied on the binarized image to isolate all the corner points. First, the image was reduced to only the structure of the checkerboard being shown by perfoming edge detection using the imcorrcoef() function in Scilab. Then, the image was dilated with a square to make the lines thicker. After which, the image is eroded with a cross so that only the intersections/corners would remain. A series of erosion of the image with different sizes of rectangles (depending on the size of the corners left with the previous erosion with a cross) was then performed. The goal was that only single corner points must remain. The code below ensured that only one point in every corner after every erosion was left.

[image,n] = bwlabel(image);
for i=1:n,
f = find(image1==i);
reg_size = size(f,'*');
if reg_size > 1,
image1(f) = 0;
end
end
image = (image>0)*1;

However, the generated code for determining the pixel coordinates in the distorted images does not work for most images. It would only work for perfect checkerboard images. Another way to determine the pixel coordinates would be to locate the desired points in the image. This is the easiest method but requires so much time and must be accurate in locating the points. Figure 5 shows the isolated single corner points using the generated code. It must be noted that the x coordinate is the column number while the y coordinate is the row number. The said convention was carefully followed throughout the code to avoid errors.

Figure 5. Corners of the white/black rectangles determined after image segmentation.

The next pixel coordinates determined were of the undistorted or the ideal checkerboard. The data needed were the following: height and width of the undistorted (central) rectangle, lowest x and y coordinates. The undistorted pixel coordinates were determined by first creating a matrix of the same size as the image. Then starting from the lowest x and y coordinates, the other coordinates were determined by generating the set of points with a column interval equal to the width and a row interval equal to the height. Figure 6 shows the image of the ideal points, which was created by assigning a value of 1 in the determined ideal pixel coordinates of the zero matrix. The ideal checkerboard was then created from these points as shown in Figure 7.

Figure 6. Corners of the ideal (undistorted) rectangles with the same height and width as the central rectangles (not distorted) of the image .

Figure 7. Ideal checkerboard when there are no distortions at the edges.

After determining the pixel coordinates in the distorted image and the ideal checkerboard, we proceeded to determining the transformation function which was used in mapping the pixel coordinates in the distorted image to the ideal checkerboard (see Figure 8). Equations 1 to 6 are the important equations describing the mapping process. As described in equation 6, coefficients C1 to C8 need to be determined first by using uquation 5. However, the first four equations require the grouping of the corner points into 4 corresponding to one rectangle. Once the pixel coordinates have been grouped into 4, the determination of the coefficients is much easier as illustrated in the code below after the equations. With the coefficients already known, the corresponding undistorted pixel coordinates were determined using equation 6. Note that it must done for all points/pixel coordinates in the distorted image and not only the corner points. The set of coefficients to be used depends on what corner points surround the distorted pixel coordinates to be mapped.

Figure 8.

Equation 1. r and s are the transformation functions for x and y coordinates, respectively.

Equation 2. Expression of the r and s transformation functions.

Equation 3. Matrix equations mapping undistorted to distorted pixel coordinates.

Equation 4. Compact form of equation 3.

Equation 5. Solution for determining the coefficients C1 to c8.

Equation 6. Reverse of equation 3: mapping of distorted to undistorted pixel coordinates.

for i = 1:196,
xC = cornerDx(i,:);
yC = cornerDy(i,:);
xT = cornerUNDx(i,:);
yT = cornerUNDy(i,:);
T = [xT(1) yT(1) xT(1)*yT(1) 1; xT(2) yT(2) xT(2)*yT(2) 1; xT(3) yT(3) xT(3)*yT(3) 1; xT(4) yT(4) xT(4)*yT(4) 1];
T = inv(T);
cx(i,1:4) = (T * xC')';
cy(i,1:4) = (T * yC')';
end;

The next step was to determine the graylevel values of the mapped undistorted pixel coordinates. If the obtained pixel coordinates were integers, the value at that location in the distorted image was its value. However, if the obtained pixel coordinates were non-integers, bilinear interpolation was implemented (see equation 7). Just like in finding the transformation functions, the coefficients a, b, c and d need to be determined first. Similar equations as equations 3 to 5 were used in determining the values of this constants. For the 4 points needed, its four neighboring points were used. Below is the code used to map the distorted points to the ideal points and calculate its graylevel value.

Equation 7. Bilinear interpolation

imagenew = zeros(s(1),s(2));

for i = 1:196,
for y = min(cornerUNDy(i,:)):max(cornerUNDy(i,:)),
for x = min(cornerUNDx(i,:)):max(cornerUNDx(i,:)),
xnew = sum(CoeffX(i,:) .* [x y x*y 1]);
ynew = sum(CoeffY(i,:) .* [x y x*y 1]);
if xnew/floor(xnew) > 1 | ynew/floor(ynew) > 1,
xnew1 = floor(xnew);
ynew1 = floor(ynew);
neighy = [xnew1 xnew1+1];
neighx = [ynew1 ynew1+1];
dy = xnew - xnew1;
dx = ynew - ynew1;
vnew = dx*dy*image(neighy(1),neighx(1)) + (1-dx)*dy*image(neighy(1),neighx(2)) + (1-dx)*(1-dy)*image(neighy(2),neighx(2)) + dx*(1-dy)*image(neighy(2),neighx(1));
imagenew(y,x) = vnew;
else;
vnew = image(xnew,ynew);
imagenew(y,x) = vnew;
end;
end;
end;

end;

Figure 8. Restored image with no distortions at the edges anymore.

Figure 8 shows the corrected image, in which there are no more distortions. It can be observed that the boundaries/edges of the rectangles are somewhat blurry or not defined. But if you zoom the original distorted image in Figure 3, you can see that the edges are not defined also. So, it just makes sense why the corrected image looks like that.

I would myself a grade of 10 for this activity since I was able to correct the distorted image.

ACTIVITY 12 Color Image Segmentation

2009-08-06T04:41:00.001-07:00

In previous activities, the segmentation of the ROI from the background was done by binarization of the grayscale image. However, if the the grayscale image is similar to that shown below, it would be hard choose a threshold value which can properly separate the ROI from the background. Thus, new techniques of segmentation are introduced in this activity: parametric and nonparametric. There is no need to convert the truecolor image into a grayscale image. The histogram of the RGB values will be used to separate the ROI from the background.

Before proceeding with the segmentation process, the variation in the brightness level of the 3D objects were dealt with first. Brightness information can be disregarded if the RGB values are normalized to the intensity values at each point. That is, the RGB values at a point are divided by the sum of the of the RGB values at that point. This color space, which contains only chromaticity/color information, is called the normalized chromaticity coordinates or NCC. Figure 1 shows the NCC where the x-axis is r and the y-axis is g. b need not be shown here because its value can already be derived from r and g.

Parametric segmentation is done by assuming that the probability distribution function (PDF) of the image is a Gaussian distribution independent along r and g. The Gaussian PDF equations, form shown in the manual, for r and g are established by getting the mean, standard deviation and variance of the rg values of the ROI, which must be a monochromatic patch. The probability values along r and g are then multiplied and the product is already the correlation between the color information of the points in the image and the ROI. The process of segmentation is done by determining the probability that the rg values at points in the image belong to the color distribution of the ROI. This means the portion in the image that has the same color as the ROI, or high probability, will appear as bright spots in the resulting segmented image.

In nonparametric segmentation, no form of PDF is assumed and the 2D histogram of the binned rg values is used. The histogram is a N x N matrix where N is the number of bins. A sample code of creating a 2D histogram is shown in the manual. The process of segmentation is done by histogram backprojection. That is the pixel locations are assigned with new values depending on the r and g values. The new value is the value in the 2D histogram of the (r*N, g*N) location. Bright spots correspond to the portions of the image with the same color information as the ROI.

Figure 1. Resulting images after nonparametric and parametric segmentation of the patches of the sample images (third and last column). The patches are the small images just above the sample images. The second column consists of the 2D histogram of the patches.

Figure 1 shows several examples of nonparametric and parametric segmentation (third and last columns, respectively). The first four images illustrate how the segmentation process can also be used to highlight only the portions in a monochromatic object that have the same shade as the patch. The variation in the color of a 3D object is also evident in these results. The fifth image is a clear proof that the techniques used can properly segment the ROI from the background without having to convert the image into grayscale. The succeeding images segment the fruits in the image having the same color as the patch. The colors may not be exactly the same. As long as the fruit has r or/and g values, which are more or less the same as that in the patch, that fruit will be highlighted in the segmented image. The correlation in the in the r and g values of the image and the patch is illustrated in the variation of brightness of the highlighted spots. The nearer the color of the fruit to the color of the patch, the brighter the highlighted spots will be.

The created 2D histograms were checked by comparing the bright portions in the histogram with the NCC plot above. It can be seen that the bright portions are located at the same position as the location in the NCC plot of the color of the patch.

Comparing the results of parametric and nonparametric segmentation, it can be seen that the former is a better technique of highlighting portions that have color more or less the same as the patch. The trace of the fruits in the segmented image is more solid when the former technique is used as compared to when the latter technique is used. This is probably because the Gaussian distribution generates higher probability than when using the 2D histogram of the patch. However, it must be noted that the number of bins used for the parametric segmentation above is 256. This means the colors/shades of colors are highly separated, and so fewer portions in the image will be detected having the same color as the patch. This explains why in the results above the parametric method has darker and fewer highlighted spots than the parametric method. Figure 2 shows the different results when different number of bins is used. It can be seen that more fruits are highlighted when the bin is just 10. The trace is even more solid than the trace using parametric method. This is because with smaller bins, more colors of the same shade are grouped. From the results below, it can be seen that using 100 bins gives us the best result for highlighting only the fruits that have exactly the same color as the patch.

Figure 2. Parametric segmentation of the banana and grape patches using different bins (10, 100, 256).

I would like to thank Thirdy, Master and all other who have helped me understand what has to be done for this activity. I would give myself a grade of 10 for a job well done (according to me).

References:

1. Orange image: http://msp256.photobucket.com/albums/hh194/yehitsroger/orange.jpg
2. Mango: http://carinderia.net/blog/wp-content/uploads/2008/12/mango13.jpg
3. Green Apple: http://2.bp.blogspot.com/_wxeBei5m--0/SeaZnk8DBfI/AAAAAAAAARE/uci2eKrBTtU/s400/apple_green_fruit_240421_l.jpg
4. Red Apple: http://www.ableweb.org/news/winter2009/images/fruitApple1c4.jpg
5. Fruits: http://files.myopera.com/buksiy/albums/739313/Fruits.jpg
6. Apple Tree: http://www.kevinecotter.com/appletree.jpg

ACTIVITY 11 Color Camera Processing

2009-08-05T18:27:00.000-07:00

The main goal for this activity is to balance unbalanced images using white patch (WP) and gray world (GW) algorithms. The image is unbalanced if the portions that are supposed to be white do not appear white. Just like the images in Figure 1, the supposedly white portions appear bluish. This means the images are captured using a WB setting not appropriate for the lighting conditions of the room/surroundings.

White patch algorithm divides all RGB values with the RGB values of the supposedly white portions. In doing so, these portions are forced to have a value of 1 producing a true white color. In this case, the bluish color can be thought of as an offset of the white color. Forcing the bluish color to be white allows the rest of the colors to be rendered correctly with respect to the white color. The balanced images using WP algorithm appear darker in Figure 1 (second column) because a constant (< style="text-decoration: underline;">

Figure 1. White balancing of unbalanced images. First column: unbalanced images; second column: using white patch algorithm; third column: using gray world algorithm.

Figure 2. White balancing of unbalanced images. First column: unbalanced images; second column: using white patch algorithm; third column: using gray world algorithm.

Figure 3 below shows the balancing of an image containing only a single hue. The resulting images show that WP algorithm produces better results than GW algorithm. Unlike in the multicolor images (Figures 1 and 2), the single hue introduces a bias in the balancing of the image. The yellowish color in the balanced image of GW algorithm is due to the bias in the red color since the mean of the whole image (mostly red) is used and not just of the white portion.

Figure 3. The white portion inside the black circle is the white patch used.

Figure 4. White balancing of an unbalanced image with single hue. First column: unbalanced images; second column: using gray world algorithm; third column: using white patch algorithm.

For this activity, I would give myself a grade of 10 because I was able to balance the images using both algorithms and explain the results I got. Thank you to Thirdy and all those who lent me their things for the photoshoot.

ACTIVITY 10 Preprocessing Text

2009-08-05T18:23:00.000-07:00

The available image is titled, so it has to be rotated first using the mogrify() function in SciLab. Figure 1 shows an example of a cropped image and the resulting image after rotating it by 1.21 degrees. A disadvantage of rotating the image is the resulting image has lower resolution or blurry.

Figure 1. Rotation of the image.

Figure 2 shows the resulting images after applying a technique on the original image or the processed image. The first image is the inverted image of the original image (black becomes white and vice versa). Inversion of the image makes the choosing of the threshold value in the binarization of the image much easier. To remove the horizontal line between the texts ‘DEMO III’ and ‘Position’, a filter mask (vertical line with a hole at the center) was multiplied to the Fourier transform of the image. This technique is simply linear filtering in the Fourier/frequency domain. The resulting image is already clean, i.e., texts well separated from the background, so no further processing needs to be done. To make the texts one-pixel thick, the thin() function is applied to the image. Looking at the results, it can be observed that the characters in the word 'Position' are not highly resolved probably because the the spacing is too small that they seem to be connected. The failure to extract the letters in their complete form is due to the uneven brightness of the lines forming the letters. Making the texts one-pixel thick worsens their reconstruction. This is because of our failure to extract the letters completely, as well as clearly separate from each other.

Figure 2. Processing of the 'DEMO III, POSITION' text in the image.

The next figure demonstrates the processing of plain handwritten texts in a cropped image of the form. Again, the image is inverted first and then the horizontal lines are removed by linear filtering in the Fourier domain using the same filter mask. Since the binarized image is not yet that clean, it is further processed by applying the morphological operation opening on the binarized image. The texts are then made one-pixel thick. The reconstruction is still not good especially in the one-pixel thick texts. It is not possible to discern what these letters are using the results of our reconstruction. This is mainly because of the indecipherable handwriting of the person writing these texts. Acually, the reconstruction is good if we just look at the original image and not considering that these are supposed to be letters. If we think of the texts as just lines or curves, then we can say that the reconstruction is good. To illustrate how the labeling of the letters could have been done fo perfectly reconstructed texts, Figure 4 is shown below.

Figure 3. Processing of the handwritten texts in the image.

Figure 4. Labeling of the texts.

For this part of the activity, we counted the number of times the word 'DESCRIPTION' appeared in the image. We did it by using the correlation function we have learned in activity 5. The technique to have a good correlation when the word appears is to binarize the image and the template using the same threshold value. The word in the template must also be located at the center to be able to project the correct location of the words in the image of correlation values. Since there are three 'DESCRIPTIONs' in the image, there appear three very bright small dots in the image of the correlation values. Figures 5 and 6 show the location of the words in the image and the location of the bright spots in the image of correlated values, respectively.

Figure 5. Encircled 'DESCRIPTION' in the image.

Figure 6. Instances of the word 'DESCRIPTION' in the image.

I would like to thank Thirdy, Mandy, Jaze, Gilbert, Rommel, Alva and all others who have helped me understand this activity. I would give myself a grade of 10 because I was able to generate the necessary results and explain them.

ACTIVITY 9 Binary Operations

2009-08-05T18:11:00.001-07:00

The purpose for this activity is to learn the techniques of properly segmenting/separating the region of interest (ROI) from the background. One technique is the binarization of the image. However, this method is not enough sometimes especially when there is an overlap in the graylevel distribution of the background and the ROI. One way to improve the separation of the ROI from the background using this technique is by creating subimages. The goal would be to have less ROI in the subimage to avoid the overlapping in the graylevel distribution. The threshold value may differ for the different subimages. This means the more the subimages are, the higher the success that the ROI will be well segmented from the background.

Unfortanately, binarization even with so many subimages is still not enough. A technique can be employed in the binarized subimages to further clean them. This is with the use of the morphological operations we learned in the previous activity, i.e., erosion and dilation. For this activity, we will be using new operations which utilizes both erosion and dilation. Opening is the operation in which the image is eroded first, and then the result is dilated using the same structuring element (SE) or another one. Closing, on the other hand, is the operation that dilates first, and then erodes the resulting image.

Proper segmentation is required especially when dealing with image-based measurements. For example, in this activity, we would like to calculate the area of the circles/holes. To be able to arrive at an accurate value, the image has to be prepocessed first.

The following were done to have a well-segmented ROI from the background:

1.) The images were subdivided into 6 subimages. (see Figure 1)

2.) For each subimage, the histogram was generated. (see Figure 2)

3.) Choosing a threshold value for each subimage (~0.80), the subimages were binarized. (see Figure 3)

4.) The binarized images were then further cleaned using only the opening function. (see Figure 4) I didn't find the closing function usefeul becauses it does not separate nearly connected blobs but instead treat them as one blob. On the other hand, using both opening and closing functions do not give that much difference in the calculation of the area.

5.) The blobs in the each subimage are then labeled using the function bwlabel(). It simply assigns an integer number to all connected pixel locations. Different groups of connected pixels have different assigned values. (see Figure 5)

6.) The area of each blob in the subimage is then calculated. This was done by simply getting the size of the blob with that assigned integer number. A bar graph of the calculated areas arranged in decreasing order is then established (see Figure 6) Extreme values are not included in the calculation of the mean area and standard deviation. In this case, only data 10-52 are included. The calculated mean area is 521 pixels while the standard deviation is 23.

Figure 1. The image subdivided into 6 parts.

Figure 2. Histogram of the subimages.

Figure 3. Binarized form of the subimages.

Figure 4. Resulting image after applying the opening function on the subimages.

Figure 5. Labeled holes of the subimages.

Figure 6. Calculated areas arranged in decreasing order.

I would give myself a grade of 10 for this acitvity because I believe I did this activity correctly. I would like to thank Thirdy and Jaze for their help in some parts of this acitivity.

ACTIVITY 8 Morphological Operations

2009-07-25T05:15:00.001-07:00

This activity was done to illustrate what the two common morphological operations, erosion and dilation, do when applied on an image of shapes or patterns. Figure 1 shows the image of shapes used in the activity. Before using the available functions in Scilab, the resulting images after applying erosion and dilation using the structuring elements (SE) in Figure 2 were first predicted. Theoretically, the resulting image after dilation is the set of all possible translations of the reflected SE such that when it is intersected with the image/shape, it is not an empty set. In the case of erosion, it contains all the possible translations of SE such that it is still contained in the shape. Given the definitions above, using dilation increases the size of the shape while using erosion reduces its size.

Figure 1. The shapes used to illustrate the effect of the morphological operations/functions, dilation and erosion, on binary images.

Figure 2. Structuring elements used to dilate and erode the images of shapes above: (4 x 4 ones), (2 x 4 ones), (4 x 2 ones) and a cross of length 5 and thickness 1.

Predictions:
For dilation, I just placed the SE at the corners of the shape such that at least 1 pixel is left contained in the shape. After which, I traced the corners of the SE located at the corners of the shape. My predictions show that the dimension of the shape is, indeed, increased by twice the (width/length -1) of the SE. Also, the resulting shape has curves similar to the SE.
For erosion, I translated the SE at the corners of the shape such that the edge of the SE and the shape coincide. Then, I chose the edges of the resulting shape such that at least one pixel of the SE is contained in that new shape. My predictions show that the dimension of the shape is reduced by twice the (width/length -1) of the SE. The resulting shape has also curves similar to the shape of the SE.
For a clearer visualization of what I meant above, look at the figures for my predictions.

Simulation using SciLab:

Figures 3 to 7 show the resulting images after applying the erosion and dilation functions available in SciLab on the images in Figure 1 using the stucturing elements in Figure 2. The gray portion is the original size while the white portion is new size (erosion) or increase in size (dilation). A detailed list of the dimensions of the resulting shapes can be found in the table below. The outline/curves of the resulting shapes match my predictions. However, only or some shapes and some SEs were my predictions able to match the simulation results. The following are the reasons for the disagreement of the results with my predictions:
1. The original size in my predictions is wrong. The shapes I created are smaller than my expected original size.
2. I forgot that the set of translations must be positive.
After realizing the those two things, I was able to correct my predictions and get the same results as the simulation results. Instead of the twice the (length/width of the SE- 1) increase or decrease in the dimension that I have predicted earlier, the change in dimension must only be by (length/width of the SE- 1) .

Figure 3. First row: dilation of square; second row: erosion of square.

Figure 4. First row: dilation of circle; second row: erosion of circle.

Figure 5. First row: dilation of triangle; second row: erosion of triangle.

Figure 6. First row: dilation of hollow square; second row: erosion of hollow square.

Figure 7. First row: dilation of plus sign; second row: erosion of plus sign.

Figures 8 and 9 are illustrations of the morphological operations, thin and skeleton, that are also available in SciLab. The thin function, basically, makes the images/shapes/patterns one-pixel thick. On the other hand, the skeleton function traces the interior/exterior skeleton of the images/shapes/patterns. It is dependent on the number of sides of the shape.

Figure 8. Results after applying the thin function on the images.

Figure 9. Results after applying the skel function on the images. First row: using the interior side; second row: using the exterior side.

I would give myself a grade of 9 for this activity. My predictions did not match the simulation results but I have explained above the reasons why it didn't.
Thank you to all those who have helped me in this activity.

ACTIVITY 7 Enhancement in the Frequency Domain

2009-07-22T08:42:00.001-07:00

7.A Convolution Theorem

Figure 1 shows a set of patterns, which illustrates the Fourier transform of the convolution of two images. The last three images can also be thought of as the convolution of the patterns (square, circle, Gaussian) with the two dots in the first image. Recall that the Fourier transform of a convolution is just the the product of the Fourier transforms of the images. Recalling the Fourier transform of a square and a circle, which are shown in the previous activity, Figure 1, indeed, illustrates that the Fourier transform of convolution of two images is just the product of their Fourier transform. Figures 2, 3 and 4 show the variation in the Fourier transform when the sizes of the patterns are varied. It can be seen that the size of the pattern in the Fourier transform, most obvious with the brightest spot, generally decreases with increasing size of the image pattern. Inverting the grayscale value of the image pattern yields a similar Fourier transform pattern but of inverted grayscale value also (see Figure 6).

Figure 1. Fourier transform of different image patterns.

Figure 2. Fourier transform of square dots of different sizes.

Figure 3. Fourier transform of circular dots of different sizes.

Figure 4. Fourier transform of Gaussian dots of different sizes.

Figure 5. Comparison of the real and imaginary parts of the Fourier transforms of the Gaussian dots and the inverted Gaussian dots.

7.B Fingerprints: Ridge Enhancement

Image enhancement can be done either in the spatial domain. Histogram equalization to improve the contrast of the image, which we did in activity 4 is an example of enhancing in the spatial domain. In this activity, the enhancement of the image is done in the frequency domain by blocking all unnecessary frequency (bias and noise) so that the Fourier transform contains only the information (frequencies) regarding the actual image. Basically, the remaining parts of this activity is about filtering in the frequency domain. Filter masks were created depending on the Fourier transform of the image and the frequency that has to be blocked. It is important that the masks are of inverted grayscale value (background-1, foreground/pattern-0). Basically, the masks just follow the shape of the frequency patterns that will be blocked. The concept behind linear filtering in the frequency domain is the convolution theorem. Thus, the inverse Fourier transform of the product of the filter mask and the Fourier transform of the image is the convoluted image of the original image and the noise pattern, which is of inverted grayscale value. This results in an image without the noise patterns.

In the case of fingerprint ridges enhancement, the filter mask created is not of inverted grayscale value because it makes filtering much easier. This is because the actual frequencies of the fingerprint are much more obvious than the unnecessary frequencies. A circular filter mask is used for the actual frequencies of the fingerprint while a Gaussian dot is used for the cutoff in the central frequency, which is the needed mask (controlling factor) for ridge enhancement. The filter used leaves all components inside the circle and Gaussian unchanged but cuts off all components outside these regions. The results are shown in Figures 6 and 8. A binarized form of the original and enhanced images are shown in Figure 7 to clearly illustrate the enhancement of the image due to the filtering process. Blotches are removed and the lines or ridges are more defined.

Figure 6. Clockwise from top left: grayscale image of a fingerprint; its Fourier transform; filter mask used; enhanced grayscale image of the fingerprint.

Figure 7. Clockwise from top left: grayscale image of the fingerprint; equivalent binary image; enhanced grayscale image; equivalent enhanced binary image.

Figure 8. Clockwise from top left: paler grayscale image of another fingerprint; its Fourier transform; filter mask used; enhanced grayscale image of the fingerprint.

7.C Lunar Landing Scanned Pictures: Line Removal

Recall that the Fourier transform of equally spaced lines is approximately a line but perpendicular to the direction of the lines in the image. So, if the horizontal (vetical) lines have to be removed, the vertical (horizontal) line in the Fourier domain has to be filtered. Figure 8 shows the resulting images when only the horizontal lines are removed and when both horizontal and vertical lines are removed.

Figure 9. First column from top: original grayscale image; vertical lines removed in the image; both horizontal and vertical lines removed in the image. Second column from top: Fourier transform of the original original image; filter mask used to remove vertical lines; filter mask used to remove both horizontal and vertical lines.

7.D Canvas Weave Modeling and Removal

Figure 10 shows the Fourier transform of the image, filter mask used to remove the canvas weave pattern and the resulting enhanced image. Figure 11 shows the inverse Fourier transform of the inverted filter mask. It is more or less similar to the canvas weave pattern in the image. It is even shown, also in Figure 11, that when the pattern is added to the enhanced image, the original image having the canvas weave pattern is restored.

Figure 10. Clockwise from top left: original grayscale image; its Fourier transform; filter mask used; enhanced grayscale image without the canvas weave pattern.

Figure 11. Clockwise from top left: inverted grayscale image of the filter mask used; reconstructed canvas weave pattern; resultant image of adding the reconstructed canvas weave pattern and the enhanced grayscale image; original image.

I created the filter masks using SciLab only because it is easier for me than creating them using Paint. There is a risk, however, for this procedure that it will also block the needed frequencies and not totally filter the undesired frequencies. But since the images are perfectly enhanced, the filter masks that were created avoided the risks mentioned above.

I would like to thank Raffy for explaining to me the process of filtering especially the correct usafe of the fftshift() function. I would also like to thank Thirdy and all others who have helped me finish this acitivity. A grade of 10 for this activity because the images were perfectly enhanced.

References:
1. Fingerprint: http://www.staffordsheriff.com/content/childsafety/Image/Fingerprint picture 1.jpg
2. Digital Image Processing using MATLAB by R. Gonzales, R. Woods and S. Eddins

ACTIVITY 6 Properties of the Fourier Transform

2009-07-09T00:31:00.000-07:00

6.A Familiarization with FT of Different Patterns

Below are some simple patterns commonly used in image processing and their Fourier transform. It can be seen that the Fourier transform is unique to each pattern. Complex patterns may have Fourier transform as combination of the Fourier transform of these simple patterns.

Figure 1. click the image for a better view

6.B Anamorphic Property of the Fourier Transform

The anamorphic property of Fourier transforms is being investigated here by getting the Fourier transform of sinusoid of different frequencies and at different directions. Figure 2 shows the variation in the Fourier transform when the frequency of the sinusoid is varied. The increase in frequency is illustrated in the decrease in spacing between the lines and the width of the lines itself (white lines). Notice that the image of the sinusoid can also be represented as equally spaced slits. The Fourier transform is, therefore, composed of the Fourier transform of two slits (see Figure 1). Two rectangular spots are prominent in the Fourier transform. The spacing between these two spots increases as the frequency of the sinusoid is increased. These also become longer when the frequency is increased. It can also be observed that the direction of the Fourier transform is perpendicular to the direction of the lines. In this case, the sinusoid is composed of horizontal lines and so, the Fourier transform is in the vertical direction.

Figure 2. click the image for a better view

Figure 3 illustrates the effect of a constant bias to a sinusoid. It is evident from the images that adding a constant bias would just give a zero frequency in the Fourier transform, i.e., at the center. No matter how large the constant bias is, it will just be translated as a zero-frequency in the Fourier domain. To get the actual frequency of the sinusoid, one can cover/filter the zero-frequency using a filter mask that has zero value at the center and a value of 1 at other pixel locations. Filtering the zero-frequency leaves only the actual frequencies in the Fourier transform. If the bias added isnonconstant and unknown, a Fourier transform containing only the actual frequencies can still be produced by creating a filter mask which has a value of 1 only at pixel locations having the information about the actual frequencies. However, this is only possible if the actual frequencies are known, i.e., involving the common patterns such as those presented above.

Figure 3. click the image for a better view

Rotating the sinusoid can also be reflected in its Fourier transform as shown in Figure 4. But the direction of rotation in the Fourier transform is always opposite or perpendicular to the direction of rotation in the image. In the figure below, the sinusoid is rotated with respect to the horizontal but the rotation in the Fourier transform is with respect to the vertical. The angle of rotation is the same for both domains.

Figure 4. click the image for a better view

The Fourier transform of a combination or an addition of sinusoid with different frequencies and with different angle of rotations is just the superposition of the Fourier transform of each component. As predicted, the Fourier transform in Figure 6 is the superposition of the Fourier transform the 8 sinusoid that constitute the image. If the sinusoid are multiplied, then a Fourier transform such as that in Figure 5 will be the result.

Figure 5. click the image for a better view

Figure 6. click on the image for a better view

In summary, different patterns produce different patterns of Fourier transform. A combination of these patterns results in a superposition of their Fourier transform. The anamorphic property of Fourier transform is the characteristic difference in spacings due to the change in spacing in the image. It also explains the perpendicularity in the direction of the image and the Fourier transform lines. Any rotation in the image results in a rotation in the Fourier transform.

I give myself a grade of 10 for this activity because I was able to do everything that has to be done. I would like to thank Thirdy and all those who have helped me finish this acitvity.

ACTIVITY 5 Fourier Transform Model of Image Formation

2009-07-07T05:21:00.000-07:00

Programming Language: Scilab 4.1.2

6.A Familiarization with Discrete FFT

This part of the activity allows us to visualize the basic meaning of the fundamental functions of Fourier transform greatly needed in image formation and image processing. The first function we tried is fft(). The information embedded in an image is in the spatial domain. By applying fft() on the image, we are transforming the image information into the frequency domain (see FFT of Figures 1 and 2). However, the Fourier transform of an image is not much of a help also in understanding the information encoded in the image. The second function we tried is fftshift(). It rearranges the fft output in such a way that the zero-frequency component of the spectrum is shifted at the center (see FFTSHIFT of Figures 1 and 2). For the circle, the resulting image resembles the Airy disk or pattern which is the analytic Fourier transform of circles. In the case of letter A, the resulting image is the combination of the Fourier transforms of the vertical diagonal lines and a horizontal line that form the letter, i.e. two intersecting horizontal diagonal lines and a vertical line, respectively. This is in accordance to the distributive property of Fourier transform. As an additional exercise, we also tried applying the ff() function twice on the image (see FFT of FFT of Figures 1 and 2). The resulting image is the inverted form of the original image. This can be explained by recalling the duality property of Fourier transforms, i.e. FT of FT of f(x) = f(-x). The inversion is not evident in the circle since it is symmetric in all directions. The visualization of applying fft() twice is more obvious in letter A, which is inverted along the horizontal axis. So, again, applying the function fft() twice does not give you back the original image. If you want to get the original image, you must use the ifft() function or the inverse Fourier transform.

Figure 1. click on the image for a better view

Figure 2. click on the image for a better view

6.B Simulation of an Imaging Device

Simulation of an imaging device is similar to getting the convolution of two functions or the product of the Fourier transform of the two functions. It is also the same as "smearing" of one function against the other such that the resulting function looks similar to both functions. In the case of an imaging device, the resulting image would be how the device detects the object being viewed. For this activity, our object is the word VIP and our imaging device is the circular aperture representing a cicular lens of finite radius. Finite radius means the lens can only detect a limited number of light rays reflected off the object resulting into an image that is never 100% similar to the actual object. The resulting image is dependent on the radius of the circle as shown in Figure 3. For very small circles, the resulting image is distorted and cannot be read. This is because the light rays allowed by the lens to pass is not enough to reconstruct the word VIP. As the circle gets bigger, the resulting image becomes more like the original image. As you can see in Figure 3, the reconstructed VIP word is still gray when the medium-sized circle is used. It becomes whiter and the edges are more defined when the larger circle is used. This just means that the lens is able to collect more light rays enough to reconstruct the word VIP. The variation in the radius of the lens is reflected in the varying color of the reconstructed word from gray to white.

Figure 3. click on the image for a better view

6.C Template Matching Using Correlation

Our goal for this part is to count the number of A's in the text "THE RAIN IN SPAIN STAYS MAINLY IN SPAIN". We did this by getting the correlation between the two images containing the text and a letter A made using Microsoft Paint. It must be noted that the text and A must be of the same font size to be able to successfully correlate the two images. As mentioned in the manual, the correlation of the two functions representing the images measures their degree of similarity. The more identical the two images are on the same position, the higher their correlation value is. High correlation values are represented by very bright dots in the resulting image (see MATCHED in Figure 4). The mesh plot of the image supports this also. There are 5 bight dots in MATCHED and 5 spikes in the mesh plot, which means there are 5 A's in the text. We also manually counted 5 A's in the text Hence, the code we created can be used for template matching. It is also mentioned in the manual that correlation is related to convolution and if at least one of the functions is even, the correlation is just equal to the convolution. If the A, which is symmetrical, is located at the center of the image, then the function representing it would be even. It means the correlation would just be equal to the convolution of the images.

Figure 4. click on the image for a better view

6.D Edge Detection Using the Convolution Integral

We were able to successfully detect the edges of the word VIP depending on the orientation of the black portions in the leftmost images (see Figure 5). If it they are oriented horizontally (vertically), then only the horizontal (vertical) lines in the edges will be detected. In the case of the All Around, all edges are detected since it contains both horizontal and vertical orientations. The diagonal lines in the edges may also be detected since they have components in both orientations (horizontal and vertical).

Figure 5. click on the image for a better view

I was able to successfully generate the necessary images for this activity but I was not able to finish it before deadline, so I would just myself a grade of 9 for this activity. I would like to thank Mr. Luis Buno III, Mr. Jaya Combinido and Ms. Kaye Vergel for answering some of my questions. I would also like to thank Prof. Maricor Soriano for her suggestion about mesh plot in part C.

References:
1. Activity 5 Manual
2. http://www.dspguide.com/ch24/5.htm
3. http://www.insight-journal.org/browse/publication/125
4. http://www.scilab.org/product/man/fftshift.html
5. Integral Transforms and Applications by Lokenath Debnath

ACTIVITY 4 Enhancement by Histogram Manipulation

2009-07-01T08:58:00.000-07:00

For this activity, we tried to enhance grayscale images with poor contrast. For an 8-bit image, its gray levels can range from 1 to 256. However, those with poor contrast have gray levels which occupy only a small portion of the available range of values. To have a better understanding, we create a histogram of our image. Consider the probability distribution function (PDF) of the original image in Figure 1 (click on the images for a better view). Notice that it covers only the range 75-125 out of the 1-256 possible range. This implies that the image has poor contrast. Another way to show that the image has poor contrast is by creating a cumulative distribution function (CDF). If the CDF is linear from 1 to 256, then the gray levels of the image are of "uniform density" in the entire available range of values.

So, how did we enhance the poorly contrasted images? As mentioned above, the contrast of the image has something to do with its histogram. A narrow histogram indicates an image with poor contrast and low visibility while a widely distributed histogram means the image has good contrast and high visibility. Thus, by manipulating the histogram, we would be able to make some changes on the contrast of the image. For this activity, we will be using the technique histogram equalization. This technique allows the transformation of a narrow histogram into a widely distributed histogram. Widely distributed signifies an approximately uniform histogram. In doing so, we are also able to to stretch the dynamic range of gray levels of the image. This means the lighter pixels of the image can still be lighter and the relatively darker pixels can be even darker. Hence, the contrast of the image is improved or increased resulting into an enhanced image.

Basically, what we did is we assigned each pixel a new value; however, this value is dependent on the original value. The relation between the new value and the original value is based on the CDF. As mentioned above, a uniform histogram produces a linear CDF. So, we generated the CDF of the original image by getting the integral of its histogram and created a linear line with pixel values from 1 to 256 and CDF values from 0 to 1. The pixel value in the original image is mapped onto the equivalent pixel value in the linear line, i.e. same CDF value. The new image now contains information which produces a contrast-enhanced image, specifically histogram- equalized image. It must be noted that the assumption for this technique is that the information contained in the image is related to the probability of occurence of the pixel values as illustrated in the image histogram. It is expected that the histogram of the new image can be approximated as uniform with gray levels ranging from 1 to 256 and that the CDF is linear.

Listed below are the important lines of the code:

1.) Reads and shows the image.
1 image = imread('F:\Documents\AP186\activity 4\grayscale10.jpg');
2 subplot(331)
3 imshow((image-1)/255);
4 title('Original Image', 'fontsize', 3)

2.) Creates a histogram or probability distribution function (PDF) of the image.
5 s = size(image);
6 maximum = max(image);
7 minimum = min(image);
8 histogram = zeros(1,256);
9 for i = minimum:maximum,
10 var = (image==i)*1;
11 histogram(i) = sum(var);
12 end
13 histogram = histogram/(s(1)*s(2));
14 subplot(332)
15 plot2d((1:256),histogram);
16 title('PDF', 'fontsize', 3)

3.) Creates a cumulative distribution function (CDF) -- cumulative sum of the image histogram
17 cdf = cumsum(histogram);
18 cdf = cdf/max(cdf);
19 subplot(233)
20 plot2d((1:256),cdf)
21 title('CDF', 'fontsize', 3)

4.) Assigning of new values to the pixels using the linear CDF (equation of the line/relationship between the original value and the new value: Pixel Value = CDF Value *255 +1).
23 newimage = image;
24 for j = minimum:maximum,
25 old = cdf(j);
26 new = old*255 + 1;
27 w = find(image==j);
28 newimage(w)= new;
29 end

The histogram and CDF of the new image were established using the same lines listed above for (2) and (3). Figures 1, 2 and 3 show some examples illustrating the technique histogram equalization in order to enhace the contrast of a poorly contrasted image. The first row shows the orginal image and its histogram, as well as its CDF. In the second row is the new image, its histogram and CDF. As you can see, the histogram of the original image is initially narrow. Moreover, the CDF increases over a small range of values only. The image has poor contrast and low visibility; the details of the image are not that clear. After performing the histogram equalization technique, the light and dark pixels are now evident. This means the contrast of the image is enhanced, as well as its visibility. As expected, the dynamic range of pixel values or gray levels is increased occupying almost the entire available range of values. The histogram is not really perfectly uniform but more or less of uniform density. This is why an approximately linear CDF is generated.

Figure 1. http://homepages.inf.ed.ac.uk/rbf/HIPR2/histeq.htm

Figure 2. http://fourier.eng.hmc.edu/e161/lectures/contrast_transform/node3.html

Figure 3. http://homepages.inf.ed.ac.uk/rbf/HIPR2/histeq.htm

As an additional exercise, we were asked to create a CDF that can mimic the human eye response, which is nonlinear. I chose the logarithmic function to do this and the third row of the figures above shows the new image after the transformation. This time, the equation used is Pixel Value = EXP(LOG(256)*CDF Value) instead of the equation of the line to generate the new image. Note: Logarithmic is used in converting pixel value to CDF value, so, exponential must be used for CDF value to pixel value. It can be seen that image is now relatively darker as compared to the histogram-equalized image. The histogram is more or less uniform in the available range of values (widely distributed) but it also peaks on the dark portions (extremely low pixel values). This explains why the image is darker although the contrast of the image is still enhanced. The result makes sense since the mapping CDF used, which is logarithmic, is a function that discriminates brightness. As you can see in the generated CDF plot, the CDF value rapidly increases for low pixel vales and then the increase slows down at higher values.
Another nonlinear functions can be used to mimic human eye response like Gaussian. It is possible that these functions have a better effect in the image after transformation.

I would give myself a grade of 10 for this activity because I believe I performed well in enhancing a poorly contrasted image depending on the function (linear and logarithmic) used, as well as creating a histogram and CDF plot of the image. I am proud of myself because I was able to create a program with not much help from others. I would like to thank Mr. Luis C. Buno III, Mr. Jaya Combinido, Ms. Cherry Palomero, Mr. Miguel Sison and Mr. Jayson Villangca for answering some of my questions, which helped me a lot in successfully doing this activity.

Reference: Image Processing by Tinku Acharya and Ajoy K. Ray

ACTIVITY 2 Area Estimation for Images with Defined Edges

2009-06-29T11:22:00.000-07:00

For this activity, the area of several shapes (shown below) with defined edges was calculated both analytically and using Green's theorem. The area was calculated analytically using the known formulas for computing the area of regular polygons, i.e. circle, rectangle, triangle and trapezoid. Some of the shapes below are formed by combining the different regular polygons. Arrow = triangle + rectangle; Heart = 3 triangles; letter T = 2 rectangles. The area of these shapes were calculated by simply adding the area of the regular polygons forming the shapes. The dimensions (length/width/height) of the shapes were determined by counting the number of pixels along the border. Consider the rectangle in Figure 2 as an example. By knowing the pixel coordinates of the corners, it would now be easy to determine the dimensions of the rectangle.

Length = (192-57) + 1
Width = (145-55) +1

Area = Length x Width = 136 x 91 = 12376

Figure 1. Arrow, circle, heart, triangle, letter T, rectangle, trapezoid.

Figure 2. This was done using Paint, zoomed to 800%.

Below is the programming code used to calculate the area of the shapes using Green's theorem. The Green's formula in discrete form used for computing the area of enclosed regions is given below. (x,y) are the coordinates of the points along the contour line bordering the region. If it is already the last coordinate, then it must be multiplied to first coordinate to be able to close the contour line, a requirement for Green's theorem.

Since the image used is in JPEG format, it has to be binarized first, i.e. in terms of 1's and 0's only (see line 2). Line 4 of the code traces the the contour of the shape and outputs the pixel coordinates along the contour line. Lines 6-13 is the code for the Green's formula. Another way of checking if the calculated area is correct is by adding the 1s in the binarized image (see line 14). However, it must be noted that the outermost pixels or portion of the white area is used as the boundary/contour line of the region. This means the two calculated areas, from Green's theorem (area 1) and by summing the 1s (area 2), can never be equal. To account for this error, the number of points along the boundary (size of the output of line 2) is added to area 1. When this is done, area 1 now becomes greater than area 2. But if only half of the size + 1 is added, the calculated areas are now equal. (+1) can be explained by looking at the plot of the points along the contour line (see Figure 3). It can be observed that the curve is not closed, lacking one point/pixel.

1 image = imread('F:\Documents\AP186\activity 2 & 3\pics\arrow.jpg');
2 binarized_image = im2bw(image,0.5);
3 imshow(binarized_image)
4 [x, y] = follow(binarized_image);
5 plot2d(x,y)
6 s = size([x,y]);
7 xi = [x(1:s(1)-1)];
8 xi1 = [x(2:s(1))];
9 yi = [y(1:s(1)-1)];
10 yi1 = [y(2:s(1))];
11 sum1 = sum(xi.*yi1) + x(s(1))*y(1);
12 sum2 = sum(xi1.*yi) + x(1)*y(s(1));
13 area 1 = 0.5*(sum1-sum2) + 0.5*s(1) + 1
14 area 2 = sum(binarized_image)

Figure 3.

The table above lists the shapes used and their area calculated analytically, using Green's theorem and by summing the 1s. The % error is very very small, so it means the code above is highly accurate in calculating the area of shapes with defined edges. There is still error probably because, although defined, the edges are still pixelated.

I would give myself a grade of 9 for this activity because I was able to calculate the area of 7 shapes. Not perfect score because I cannot explain why only half the size of the border points has to be added.

I would like to thank Mr. Luis Buno III, Mr. Miguel Sison and Ms. Jaziel Vitug for answering some of my questions.

ACTIVITY 3 Image Types and Basic Image Enhancement

2009-06-22T20:23:00.001-07:00

There are four basic image types: truecolor, grayscale, indexed and binary. Below are examples of each of the image types. We checked the image type by looking at the bit depth in its properties when we right click the image. If the bit depth is 8 and the image is black and white, then it is a grayscale image. If the image has many colors, then it must be an indexed image. For truecolor images, their bit depth would be greater than 8. Moreover, the image is binary if the bit depth is 1.

Figure 1. Truecolor Image

http://home.earthlink.net/~richditch/images/burrowingowl20.jpg

Figure 2. Grayscale Image
http://fourier.eng.hmc.edu/e161/lectures/contrast_transform/node3.html

Figure 3. Indexed Image
http://www.creative-flow.net/tut5.gif

Figure 4. Binary Image
http://en.wikipedia.org/wiki/File:Neighborhood_watch_bw.png

Shown below in Figure 5 is a grayscale image and we want to determine the area of the apple in the image. Looking at the histogram in Figure 6, we can say that our region of interest (ROI) is well separated from its background. Therefore, we can use the programming code generated in activity 2 to calculate the area of the apple. The detailed description of the method can be found in the previous blog. Recall that it uses discrete Green's theorem for computing the area of any enclosed region. Before proceeding, we have to convert first the grayscale image into a binary image (in terms of 1's and 0's only) using the function im2bw(). The threshold value to be used in the conversion must be properly chosen to ensure that only the ROI will be in 1's (white). Looking again at the histogram of the image, we see that or ROI has pixel values ranging from ~150 to ~256. The ratio of this is 0.68, so we used 0.65 as our threshold value. Figure 7 shows the contour traced in the image, which was used in implementing Green's theorem. The area calculated by the program is 2871. We validated it by summing the 1s in the binary image and we got the same result. Therefore, we are successful in calculating the area of the apple. We have also shown in the previous blog that the method we used is accurate to about 1%. And for this, I would give myself a grade of 9. Just 9 because I was super late already in finishing this activity.

Figure 5. Grayscale image

Figure 6. Histogram of the grayscale image.

Figure 7. Contour of our ROI, i.e. apple.

I would like to thank Mr. Luis Buno III and Mr. Miguel Sison for their help..

ACTIVITY 1: DIGITAL SCANNING

2009-06-17T21:19:00.000-07:00

This activity is designed to experience how measurement of the actual dimension of the object is being done given only the image of the object. By knowing the relationship between the pixel location in the image and the physical variable, one can already tell the object's actual length. This method is not easy and erroneous but I guess it is the simplest technique for a rough estimation.

I got the graph I used from a paper entitled Electrolytic Determination and Separations with the Use of a Rotating Anode from The Journal of American Chemical Society Volume XXIX of 1907 (January 25 1907). Thanks to the author of the paper, Julia Langness, for this graph.

Thanks to Mr. Luis C. Buno III for helping me in rotating the image using MATLAB and answering some of my questions. The image had to be rotated since the scanned image is tilted.

Hand-drawn graphs are indeed difficult to reconstruct. The gridlines of the graph are unevenly thick and not aligned, thus, unevenly spaced. Due to this problem, the determination of the the equivalent pixel location in the image of a point in the graph is very much prone to error. The table below shows the pixel location of the ticks in the X-axis (Minutes) and the Y-axis (Grams). It can be seen that the difference between two consecutive ticks in the X-axis greatly varies ranging from 103 to 115, a very large deviation by 12. The same deviation in the Y-axis can be observed. To minimize the error due to the large deviation in reconstructing the gridlines of the graph, the mean of the differences was used.

By the way, the pixel location of the ticks in both axes was determined using the Paint program and then tabulated using Microsoft Excel. Instructions for determining the pixel location can be found in the manual for this activity.

Equations relating the pixel location to the physical variable in both axes were established. The proportionality factor was obtained by getting the ratio of the increment per division to the mean difference. It must be noted that the origin of the graph does not correspond to the (0,0) pixel location of the image. To account for this offset, the (X,Y) pixel location of the origin was subtracted from/to the pixel location of the points in the graph. Hence, the equations are the following:

X-axis: minutes = 2*(1355-x)/113
Y-axis: grams = 0.05*(y-67)/109

Several points to represent the best fit line, including the data points, were selected to be able to create a smooth reconstructed curve. The pixel location of each of these points were determined. The reconstruction of the graph was done by converting the pixel locations back into their equivalent physical values using the generated equations.
Note that the best fit line is also unevenly thick, so this introduces additional error.

The fun part in this activity was determining the pixel locations in the image of the points in the graph. Wait, was it really fun? hhhhmmmm... Yeah, I had fun especially because this is the first activity. But, it was also tiresome.. :( and painful to my eyes since I had to stare for so long at the computer. The frustrating part, on the other hand, was the next thing to be done. That is, overlaying the image of the graph on the reconstructed graph It wasn't supposed to be frustrating but I wasn't able to find out immediately how to overlay the image. And my seatmate was done already. Time was past 11am. Our class is until 11:30am only. So, I became a 'lil bit' fidgety. Thanks to the power of Google, I figured it out how to overlay an image as a background on a chart.

To overlay an image in a chart using Excel, the following must be done:
Go to Format Plot Area. Probably by pointing the mouse to the Plot Area and then right click.
Then, in the Fill tab, choose the option Picture or texture fill. Insert the image you want to overlay.

Below is the figure of the reconstructed graph with the original graph overlaid on it. The gridlines, as well as the reconstructed curve, were made thicker to compensate the errors (uneven thickness of the lines in the original graph) that were introduced above. It must be noted that the original graph has to be cropped properly so that it fits, more or less, the reconstructed graph.

Looking at the figure above, it can be seen that the graph is not perfectly reconstructed. Some of the reconstructed and original gridlines do not coincide. Same also with the curve and the data points. The reasons for this are already explained above. It is because the gridlines are unevenly thick and unevenly spaced.
The author of this paper is probably better in drawing horizontal lines than vertical lines. :) As you can see above, more vertical gridlines are inclined.

Although I was not able to perfectly reconstruct the graph, which isn't my fault (hehehe), I think I still deserve a grade of 9. :) Why? I didn't finish it on time but I believe I did this activity correctly as I have explained what I did above.

Guys, please comment!!! :) Tell me what you think about what I did and what I said above.

why WANNA EAT SIX KAMATIS????

2009-06-15T19:58:00.000-07:00

WANNA - 1na
EAT - 8
SIX - 6
KAMATIS - wala lang, yun kasi naisip ni thirdy

===> ito ang title ko dahil ang blog na 'to ay para sa Applied Physics 186 class namin...