CS 7321 Winter 1998.
Problem Set #1 Solution.
By Alan Daniels.

Index

• The Problem.
• My Solution.
• Assumptions and Weaknesses.
• Possible Improvements.
• The Results.
• The MATLAB code.

The Problem

For this problem set, we were to write a MATLAB program that used binary image processing methods to find instances of lower-case vowels in three supplied images. I've done this for each of the five standard vowels ("a", "e", "i", "o", and "u"), for each of the three images, for a grand total of fifteen result images.In each of the result images, I've shown the found vowels I found by using the color red.

The Solution.

Getting Started...

The first thing I did was to create a bunch of sample images to use as "templates". I took sample image no. 2 (since it was the largest, and thus had the most letters to choose from), and turned it into a grayscale. After looking at its histogram, and trying various thresholds, I decided to make it into a binary picture by using a threshold of 0.8. With that binary image, I made five samples for each vowel, for a grand total of twenty five. I've included those samples at the bottom of the page.

As part of this, I wrote routines to:

• Read in an indexed image and turn it into a grayscale image. I was doing this so often it seemed like a good idea anyway.
• Take a grayscale image and turn it into a binary image.

The First Run...

Since I had five samples per vowel, the first run at the logic I did was this. For simplicity, I'm skipping all the image inversions from white-black to black-white, and vice versa, to get the MATLAB routines to work right:

1. Load the image to be tested.
2. Load the five sample vowels.
3. Threshold the image into a binary image.
4. Take each of the five samples and "thin" them.
5. Erode each sample across the image.
6. Tally the results of each erosion. If three or more of the samples matched, we have a hit.
7. If needed, repeat this logic every 15 degrees, going from -90 to 90.
8. Using a colormap, draw the matches in red.

The flaws in the approach showed up pretty quickly. By thinning the samples, I guaranteed a match inside of a genuine match, but it also matched even when the sample just happened to fit inside an arbitrary letter. For example, I got lots of matches of "i" inside of an "l", an "h", etc. All it had to do was fit, which didn't take the background into account at all.

The Second Attempt...

I knew that I had to take the background pixels into account. The next thing that I tried to do was write my own eroder, using this logic for the samples, which I were using as Structuring Elements ("SE"s):

1. Take the SE, and copy it into two verions: One that has been "thinned", and one that hasn't.
2. Take the thin SE, and see how many places its foreground pixels match to the source image.
3. Take the fat SE, and see how many places its background pixels match to the source image.
4. If we get 90% success in both cases, consider it a successful match, and mark it as such.

This gave better results, but it was SLOW, as in five minutes for each individual erosion, which obviously wasn't acceptable. Also, I noticed that the background logic still didn't work very well. If I was sloppy with how the sample was done (such as an "e" with lots of space around it), the number of background pixels was too high. This convinced me to write two more routines:

• One to "squeeze" an image (shave away all the borders that contain nothing but background pixels).
• Another to "unsqueeze" an image, to add one pixel's worth of border back again.

The Third Attempt

I had established two major things: One, I needed to match all of the foreground pixels using a normal erosion, otherwise the processing would take forever. Second, the background matching should only use the "halo" around a sample, to show what the natural border of the SE was. In other words, only the pixels immediately surrounding a sample, since every pixel further than that is just extraneous information. So, I made another attempt at the eroding logic:

1. Take the SE and sqeeze out all the unneeded background,
2. Add one pixel-width worth of border back onto the SE.
3. Copy the SE into two verions: Thin and Fat.
4. Take the thin SE, and use it for a direct erosion. This gives us all the possible success points.
5. Take the fat SE, and get its "halo".
6. At each point where we got an erosion match, check the halo:
   1. See how many "halo" pixels match background pixels on the original image.
   2. If this is below 50% of the number of halo pixels, we know we've gotten a false hit, so remove the point.

I got the halo of an SE by using the following logic: Wherever there is a black pixel on the SE that has one or two white neighbors, then this is should be considered a point on the halo. Although this approach isn't ideal, the practical results work pretty well. A look at the halo image gives you a good idea of the SE that it originally contained.

The halo approach worked much better than the first two runs did. For example, even if I rotated an "i" by 45 degrees, I didn't have to worry about the large square's worth of background that would result from the rotation of such a thin SE. Only the edges of the "i" would matter.

Assumptions and Weaknesses.

Assumptions...

• Originally, for my 25 sample images, I made them after I had already turned the main image into a binary image. I did this on the assumption that a binary sample would be easier to work with, since it had a clean border (all zeros and ones). In retrospect, it may have been better to work with the original grayscale image, since the rotations of these would be closer to the original images.
• The final version of the logic also assumes that the overall shape of a letter is just as important as the holes inside the letter. It isn't. Even worse, the logic makes the shape more important, since it is made up of more black pixels than the holes inside the letter are.
• I still believe my overall "voting" scheme was a good idea. By that, I'm refering to the logic that says a match was only valid if three (or more) of the five samples confirmed it. Even if I were to start over, using a different method, I would still use some sort of voting scheme to validate the results.

Weaknesses...

• The main weakness ought to be obvious: It doesn't match the "i"s very well. The only thing differentiating an "i" from a normal line, such as inside an "h" or an "l", is the two or three pixels worth of separator between the body of the "i" and its dot. The halo logic didn't treat those pixels as any more important than the overall shape of the image, and as a result, those were ignored too easily.
• Similar problems happen across other gaps in letters. For example, the small gap in the circle composing the "e" sometimes gets ignored, leading to a match in letters such as the "m"s. The gap across the top of a "u" also gets matched too frequently frequently.

Possible Improvements.

To improve on the design I have now, I would add "priority" levels to the pixels in the SE. Therefore, not only could you take every pixel on the SE and label it "black", "white" or "doesn't matter", but you could also give each pixel a floating point rating from zero to one. That way, you could define the letter I so that the gap between the body of the I and the dot absolutely had to be there. For example, one possible way to accomplish this would be to make a custom eroder with five pixel types:

• Should be a white pixel.
• Should be a black pixel.
• Must be a white pixel.
• Must be a black pixel.
• A "don't care" pixel that isn't matched one way or the other.

The Results.

Original:
With "A":
With "E":
With "I":
With "O":
With "U":

Original:
With "A":
With "E":
With "I":
With "O":
With "U":

Original:
With "A":
With "E":
With "I":
With "O":
With "U":

The MATLAB Code.