Wednesday, September 9, 2009

Activity 14 Pattern Recognition

Us humans already have the inborn instinct or skill that allows us to recognize or differentiate one thing from the other. And most of the time, our own observations and experiences are enough for us to learn which is which. However machines and computers do not posses this instinct (they don't have instincts); much like how we teach babies and kids, we must also exert effort to teach machines how to recognize various things it may encounter. The difficulty with machines is that, although their language is based on math, they are still much harder to teach compared to kids (machines are stupid). In spite of this, the growing demand to increase productivity through automation and the physical limitations of the human body (there is just so much our body can do) pushes us to rely on machines and computers for various tasks. This demand and need for automated machine recognition resulted to a field known as machine vision. One sub domain of machine vision is pattern recognition which, from the name implies, basically means having a machine recognize and classify/segregate objects of patterns. In this activity we will be using Scilab to do pattern recognition of objects from an image. Our method for classification we will be using is the minimum distance classification.

All pattern recognition problems start with having a set of patterns or objects with a finite number of classification groups or classes. Each group or class is differentiated from each other based on a set of identifiable features and parameters. Hence in all pattern recognition tasks the first step is selecting the parameters or features we base our differentiation from. Since we are dealing with images it is logical that we use visually obtained information as our features. These features may be, color, shape, size, area, etc. and we may use as many as we see fit. We just have to remember that we need to select features that are distinctive to our objects or patterns otherwise we wont be able to classify them. In our method we place these features into vector form. That for each object there corresponds a vector that contains all of its features (equation 1).
Equation 1

The next step is to train the computer to recognize the different patterns. In our method this simply means that for each class we select a few samples and we take the average of their feature vectors (equation 2). This mean vector serves as the representation of the whole class; that is, each class should have a unique mean feature vector.

Equation 2

The final step is to test whether our feature selection and training was sufficient. We do this by letting the computer classify the other objects (excluding those used in training). The accuracy of classification depends on how much of the objects were classified into their proper classes. The minimum distance classification, which we use in this activity works by following equation 3.

Equation 3

As in equations 1 and 2 wi is the feature vector of object i and mj is the mean feature vector of class j. Using this equation we simply calculate d for each object for each class. We then classify object i into the class that resulted in the highest value of d.

In this activity I chose the suites of playing cards as my object class. Since I don't have a camera, I scanned the cards and this served as my raw data. From this images I classified whether the pattern is heart, diamond, spade, or club. Take note that I only consider the figures as my object and not the actual playing card (in other words the 10 of spades has 10 spade objects).
Figure 1

I used three features to construct the vectors describing each object. The first feature is their normalized R value (see activity 12). As expected the R value of diamond and heart is the same and so is the value of spade and club. Diamond and heart had a very high R value whereas club and spade had a low one. This made it easy for me to segment these objects from the background (figure 1) and calculate the other features I used. However, the segmentation was still not perfect so I used closing and opening (activity 8 and 9) operations to further improve the quality.

The next 2 features I used both characterizes the shape of each object. I calculated the ratio of the total area of each object with the area of the minimum rectangle that can contain the object which served as the second feature. The area of the minimum rectangle is simply the product of the maximum dimensions of the object ([max(x)-min(x)]*[max(y)-min(y)]) The final feature was simply the ratio of the object's total area with the square of its perimeter.

Table 1. Features and Group of Training set
(click to enlarge)

Table 1 contains all the features and group classification of the 9 samples per class I used to construct the training set and the mean feature vector of each class. I also labeled each group such that grp 1 are hearts, grp 2 diamonds, grp 3 spades, and grp 4 clubs. Now using the feature vectors of the other 40 objects in figure 1 (10 per suite/class) I calculated the corresponding d for each class. Table 2 shows the result of classifying these 40 objects and we clearly see a 100% accuracy of classification. This is further highlighted in figure 2 where I plotted the feature vectors of each object. Although the plot of Area/maxDim vs R could not distinguish between heart and diamond, it was compensated by the other parameters as seen in the 3D plot (figure 2d).
Table 2. Parameters and Classification Results of the 40 Test Objects
(click to enlarge)
(click to enlarge)
Figure 2. a)Area/max Dimensions vs R, b) Area/Perimeter^2 vs R, c) Area/max Dimensions vs Area/Perimeter^2, d) 3D plot R (x axis), Area/max Dimensions (y axis), Area/Perimeter^2 (z axis). The classes heart, diamond, spade, club are represented by the red, green, blue, black markers respectively.

Having tested the accuracy of our method I further tested its flexibility using larger images with mixed objects (figure 3) with a total of 140 objects. The results shown in Table 3 and Figure 4 still shows a 100% accurate classification.
Figure 3.

Table 2. Classification Results of the 140 Test Objects in figure 3
(click to enlarge)
(click to enlarge)
Figure 4. a)Area/max Dimensions vs R, b) Area/Perimeter^2 vs R, c) Area/max Dimensions vs Area/Perimeter^2, d) 3D plot R (x axis), Area/max Dimensions (y axis), Area/Perimeter^2 (z axis).

I give myself a grade of 10 in this activity for a job well done. I would like to thank Ms. Cindy Liza Esporlas for helping me scan the cards and sending me the images. I also would like to thank Mr. Jay Samuel Combinido for teaching me to do 3D plots.

Main Reference

Maricor Soriano, A14 - Pattern Recognition, AP186 2008

Activity 13 Correcting Geometric Distortion

Have you ever tried looking through one of those door peepholes, the ones that allow you to see who is knocking on your door? I, myself, have only tried it ones when I visited my cousin who lived in a hotel and the door of their room had one. Anyway, for those of you who have tried using one, I am sure that you have also noticed that the image you see through it is highly distorted. This geometric distortion is similar to that found in some cameras (in a much lower degree) and other instruments that use spherical lenses. Basically geometric distortion results from the varying magnification as the distance from the optical axis increases. The two most common forms of this optical abberation is the barrel (magnification decreases farther from the optical axis) and pincushion distortion (magnification increases farther from the optical axis). In photography barrel distortion is commonly encountered when taking wide angle photos. In this activity we will be correcting geometrically distorted images numerically.
Figure 1. Example of distorted images

Our method of correcting geometric distortion involves two main steps. The first step is correcting the pixel coordinates, which refers to mapping the coordinates of the distorted image back to the ideal undistorted image. Our experience with image processing allows us to understand that the process of distortion simply involves the ideal undistorted image and a distorting transfer function such that
Equation 1

Where T is the transfer function and f and g are the undistorted and distorted images respectively. So given the distorted image we just need the transfer function to recover our ideal image. However the process to determine the transfer function requires us to have information on the undistorted image. Our method allows us to calculate the transfer function using only vertices of polygons or regularly occurring patterns present in our image.

Figure 2

Consider figure 2 above where we show an undistorted and distorted polygon/grid. assuming that the area of the polygon is not to large we can approximate the transformation as
Equation 2

The 8 unknown coefficients in this transformation can be solved using the for vertices of the polygon such that in matrix form
Equation 3

This resulting transfer function is valid for all points with in the polygon as long as it is not to large.

The ideal grid required in this method can easily be generated using the least distorted area in the distorted image. The dimensions of the least distorted "box" can be used to construct the ideal grid. We would then just need to determine the transfer function for each pair of distorted and undistorted "boxes." Using these transfer function we can now solve equation 2 to determine the distorted coordinates of each point in the ideal image. That is we can now determine the graylevel values for each ideal undistorted image coordinate by copying the graylevel value of its corresponding distorted coordinate. This is the second step of our correction process.

However, most of the time our calculated distorted coordinates are not integers. For such cases we need to interpolate the graylevel value for our ideal undistorted image. Three commonly used interpolation techniques are the nearest neighbor, bilinear interpolation, and cubic convolution. In this activity we choose to implement bilinear interpolation which has a much better quality than nearest neighbor and is much faster compared to cubic convolution.
Equation 4
Equation 5

Bilinear interpolation works as in equation 4. That is, the greylevel v is assigned to the coordinate (xhat,yhat). so by solving equation 4 we can obtain the gray values even for non-integer coordinates. The unknown coefficients of equation 4 can likewise be determined similar to equation 3 but know we use the four nearest pixels around (xhat,yhat) (figure 3, equation 5).
Figure 3. Visualization of Bilinear Interpolation

In this activity I used an image with barrel distortion downloaded from the internet. Figure 4 shows the original image and the ideal grid I generated using the least distorted area in the image. After implementing the method we have discussed I was able to remove the obvious barrel distortion of the image.
Figure 4. (left) Original distorted image with indication of corrected area (red box) and area of least distortion (yellow box). (center) Ideal grid generated from area of least distortion. (right and bottom) Resulting corrected image.

The result presented in figure 4 shows that our method is very effective in removing barrel distortion. It is clearly seen that the previously curved lines are now vertically and horizontally straight. The bricks that previously had different sizes are now more uniform. The only inaccuracy we can see is that some of the bricks are slightly tilted. It is hard to determine whether they should be tilted or not but I believe it is safe to assume that most of them are squarely laid-out. Still, even with this slight error, we see very promising and convincing results.

Figure 5. Corrected image with color. The red circles identify areas with erroneous color.

Figure 5 shows a colored version of our result. This was generated by implementing the correction process for the 3 color channels and combining them into one image. This colored result shows one more error. We clearly see that at some points have colors that are obviously not accurate. This is because at these points one or two of the three color components are not properly represented. Using the same reference points in all the color channels may result in some points having the wrong color component values. In other words although the gray scale result looks almost perfect it cannot be directly implemented to a colored image and expect the same level of accuracy.

I thank Ate Cherry for helping me understand the correction procedure. I give my self a grade of 10!!

Image source:
http://www.nicovandijk.net/lenses.htm

Main Reference:
A13 – Correcting Geometric Distortions by Maricor Soriano, AP186 2009

Thursday, August 6, 2009

Activity 12 Color Image Segmentation

So far we have been doing image segmentation and morphology on binary and gray-scale images. In the past activities simple thresholding is enough to seperate our region of interest (ROI) but in some cases this wont be sufficient. In image processing there instances where binarizing an image or converting it into gray-scale wont separate it from the background, in such cases we need to utilize its color information. In this activity we use normalized chromaticity coordinates to do segmentation via color information.


Figure 1. Normalize Chromaticity Coordinates

The normalized chromaticity coordinates (NCC), shown in figure 1, can be thought of as a way of expressing 3 dimensional RGB information to a simpler 2 Dimensional r-g color space. The basis for this transform is that r+g+b=1 (done by normalizing RGB), hence the third value is redundant and it is enough to express color by only two values, in this case r and g.

After expressing an image in NCC we can now do the segmentation by using the probability distribution function (PDF) of the ROI in NCC. By mapping the image to the PDF of the ROI we are able to separate the ROI from the rest of the image. In this activity we calculate the PDF of the ROI using two methods, one of these is the parametric method which assumes that the PDF is a gaussian. In the parametric method we simply obtain the mean and standard deviation of the r and g of the ROI and use this to calculate its 2 dimensional PDF. The other method is the non-parametric method, here we do not assume any form of the PDF and we simply use the r and g (2 dimensional) histogram of the image and use this as the PDF. In both methods we obtain the PDF of the ROI by only taking a patch of it.

I used an image of multicolored candies to test these two methods for color image segmentation. Excluding the background, there are only three main colors in this image; red, orange, and green.

Figure 2 below shows the results of the segmentation using both parametric and non-parametric methods. For both methods separating the green region was accomplished almost perfectly. The pixelated result for the parametric method is caused by the actual texture of the candy and the parametric method wont be able to compensate for such a feature. On the otherhand the holes on the result of non-parametric method are most likely due to the patch I used to sample the ROI. This simply means that there are other colors which are part of the ROI that were not included in the sample patch. Using a better sampled patch would improve the result in this case.

Compared to the non-parametric the parametric method did not fare as well when segmenting the red or orange regions of the image. Since the parametric method assumes a gaussian PDF it is higly probable that the PDF of the red or orange ROI includes each other. Hence the parametric method fails when we try to separate colors that are very close to each other.

The non-parametric method does not suffer from the same problem as the parametric method since it uses the actual histogram of the ROI as the PDF for mapping. This means that even if the two colors are very close to each other there wont be any confusion as long as the other color does not appear frequently inside the ROI. As we can see from the histograms the orange and red are very close to each other but their histograms are almost mutually exclusive.




Figure 2. Original unsegmented image with the results of both parametric and non-parametric color segmentation. The patch of the ROI is also included as well as its histogram.

Overall, by looking at the results, I have to say that the non-parametric method is a much better color segmentation technique. Compared to the parametric method, the non-parametric is much more versatile, accurate, and the quality is also better.

I give myself a grade of 10 in this activity.

Activity 11 Color Image Processing

We have learned in our Applied Physics 187 course that an image captured by a color digital camera is composed of an array of pixels each having R, G, and B information. These three color information are each a product of the spectral profile of the light source, objects reflectivity and the cameras spectral reflectivity for R, G, and B. To obtain the actual appearance of the object we must divide these R, G, and B values with a scaling/balancing factor equivalent to the R, G, and B values of purely white imaged captured by the camera. This scaling factor is just the product of the cameras sensitivity and the illuminator's spectral profile. If the wrong scaling factor is used or it is miscalculated then the resulting image would not appear as good. The process of applying these scaling factors to a digital image is called White Balancing. In this activity we try out the White Patch and Gray World algorithms in doing White Balancing.

To test the effectiveness of these algorithms; we take pictures of objects containing the major hues which are obviously not properly balanced. We do so by not using the "auto white balance" function of the camera and just selecting the different balancing conditions. In the camera we used these conditions are called "daylight", "cloudy", "fluorescent", and "incandescent".

The White Patch algorithm makes use of information "obviously white" regions in the image. That is we calculate the balancing factor by taking the average R, G, and B values within a white patch of the image. On the other hand the Gray World algorithm assumes that the average color of the world is gray. Since the ratio of the R, G, and B values for gray is the same as white or black, this method takes the RGB of gray and uses it for White Balancing. In the Gray World algorithm the RGB values of gray is taken as the average R, G, and B of the whole image (whole world).

We must remember though that these White Balancing Methods wont work if the captured image is saturated, even for just a single color channel. A saturated image actually contains no color information and would not be useful in calculating the balancing factor.

Figure 1 below shows samples of captured images and their corresponding RGB channels. The blacked out regions on the RGB channels indicate the areas of saturation and wont be useful for our purposes. Therefore, in selecting the white patch we create a composite image (figure 1 last column) using the RGB channels that blacks out all the areas that are not useful. For the Gray World algorithm we simply take out the saturated regions in calculating the white balancing factors.


Figure 1. Sample captured images with their RGB channels and a composite image
indicating (blacked out) the areas that saturated.

Taking into account the saturated regions the results of applying the White Patch and Gray world algorithms on an image containing the major hues (RGB) are shown in figure 2 . First let us note that the results for both White Patch and Gray world algorithms for the incandescent and fluorescent settings are obviously wrong. The resulting image takes on an extreme shade of blue (or red) which is clearly not the true color of the objects. This error is mainly due to the fact that the original images taken with these settings were mostly saturated on the blue channel. On the other hand the images taken with Daylight and Cloudy settings were seen to improve by using the White Patch algorithm. In the daylight setting the original image is slightly bluish which after processing took on more accurate colors of the object.s This was also observed in the cloudy setting which initially had a reddish or brownish that was cured after processing. As for the Gray world algorithm, it was only seen to improve the images taken with cloudy setting resulting to a final image that displayed white as "white" even better than the White Patch algorithm.

Figure 2. Original image taken with different white balancing settings and
their respective results after applying White Patch and Gray World.

Next, figure 3 shows the results of applying White Patch and Gray World on images that had a dominant color, which in this case is blue. Again it is observed that applying a white balance on the images taken with fluorescent and incandescent settings resulted in a dark image. But even though these processed images are darker they are stilled considered improvements on the original since the original pictures are actually very bluish are actually worse representations of the true color of the image. As for the results of the Daylight settings we first note that the original image actually seems to be properly white balanced. We also see very little difference in comparing the original with the result after the White patch algorithm. But looking at the results of the Gray world algorithm we see that the image lost its yellowish color after it was processed. It is though to determine which is the more correct result. Finally the image taken with the cloudy setting has a very yellowish color which is obviously not correct. After doing the White patch we see that the yellowish color is removed which is a significant improvement. But after doing the Gray world algorithm the final image completely lost its yellowish shade but also became darker.

Figure 3. Original image taken with different white balancing settings and their respective results after applying White Patch and Gray World. The images have blue as the dominant color

Overall the results suggest that in general the White Patch algorithm results in a much better white balancing. The results of the gray world algorithm is seen to be highly dependent on the dominant color of the image.

I thank ate Cherry for lending us her camera and Irene for taking the pictures. I give my self a grade of 10 in this activity.

Activity 10 Preprocessing Text

In our past few activities we learned various ways of manipulating images both in the frequency domain and the morphologically. This time we will use all that we have learned to extract handwriting and other texts from a scanned document.


Figure 1. (Left) Original document and (Right) the schematic
on how the tilt angle was calculated.

Looking at the given document we first notice that it is slightly rotated so our first task is to straighten the document. We do this by using the 'rotate' argument of the mogrify() function in Scilab. This is a function that edits or distorts an image in numerous ways, in this case we do rotation. But before we do the rotation, we must first determine the angle of tilt of the image. We measure this angle by creating a horizontal line across the lines of the document and we calculate the angle by simple trigonometry (figure 1). And doing this method the angle we calculated was 1.05 degrees. The results of the rotation are shown on figure 2.


Figure 2. The result of rectifying the whole image and also a selected area.

We also note that the horizontal lines of the image are actually not needed and that it interferes with our objective. To remove these lines we must first invert our image (white over black) and convert it to gray-scale then apply a filter or mask in inverse space. This is similar to what we did in activity 7 and since we already know that the FT of horizontal lines would be along the vertical we simply create a mask that removes this portion of the images FT. After we apply the mask we then binarize the image to remove the background. The mask and resulting images are shown on figure 3, Fourier transform of the image is also included.


Figure 3. (top) The inverted image with its Fourier transform and (below) to the right is the mask used to filter the lines. To the left is the resulting binarized image after filtering.

After removing the lines we now go on to extracting the handwritings. We only cut a select few regions in the image where we will extract the handwritings. Our first step is to binarize the selected regions using a threshold just like in the past activities. Then we did some morphological operations hoping that it would result to a clear, readable, and distinct letter characters separated from each other. Then we label each character using bwlabel(). Unfortunately this task is very very difficult to accomplish. The handwriting through out the document overlaps with unwanted structures. And since the handwriting also has a lower gray value compared to the unwanted structures separating them becomes even more difficult. Further more if we are not careful the morphological operations destroy the letters instead of making them more distinct. Figure 4 shows the results after morphology, here I used the skel() function of Scilab to reduce the characters to single pixel width. The results, however, show that the final product does not actually look like letters. Still it is also true that these are actually similar to the original handwriting and to some degree each character was separated from each other.



Figure 4. (Left) The slected area of the document with handwriting and (Right) the result by extracting the handwriting using different morphological operations.

Our last task is to find instances of the word description with in the document. We did this by taking a template of the word description and correlating it with the image. The correlation is done similar to how we did it in activity 5. We simply multiply the FT of the template and the conjugate of the FT of the image and then take the FT of this product. If the correlation is correct it would result to an image that have the highest value at the instances of the word description. Figure 5 shows the template and the result of locating the instances of the word description. By comparing the image with the result of the correlation we see that as expected the correlation peaks at the locations of the word description. This result means that our method for locating a template works even if the quality of the image is not ideal.


Figure 5. The binarized image and mask used to locate the instances of the word description. The result of the correlation indicating the instances is also shown at the bottom.

I give myself a grade of 9 in this activity.