Recognition of Handwritten Names

Presentation slides

2009-03-11T10:54:00.001-07:00

Jittering Data

2009-03-09T01:07:00.000-07:00

After my results came out really bad, I decided that my training data was the problem. Both quality and quantity wise. It is difficult to get more training data fast, so Serge recommended using what I have to make more. I used Piotr Dollar's jitterImage function to take a single image and apply transformations to it.

Exaggeration:

Piotr's function applies both rotational and translational rotation to images. Serge recommended playing around with thickness also by raising an image to a power greater than 1, and also a power between 0 and 1.

I did all this, and started out with around 50,000 examples of each character instead of 135. I found out quickly that I run out of memory with this many examples. I eventually had to bring it down to 625, and training took forever.

The first thing I noticed was that the error in the training data was much higher than for when I only had 135 examples. I think that this is because there is a lot more variation in the data now and it's hard to cover all cases in 200 features. When I only had 135 examples, the error eventually went down to 0. This is the error with the 625 examples.

Also, here are the ROC curves plotted on top of each other. When I only have 135 examples, the ROC curve was a right angle.

Here is half of the 625 training examples for 'a':

To cut to the chase, my algorithm still performs poorly, and probably even worse now. D:

Well, I ran it already

2009-03-04T01:56:00.001-08:00

Finally, I got everything together and ran my algorithm. It did horribly. We're talking 0% accuracy horrible. I am using the same hidden markov model (hmm) as last year and I think that the model is just too unforgiving. Once it mispredicts the first letter, we're basically screwed.

I tried abandoning the hmm and for each letter in the test name, find the prediction of that letter, independent of the rest of the letters in the name. I found the prediction by taking the max over all confidences for each of the 26 possibilities. Then, in the end, I find the nearest neighbor of the predicted name with all of the names in the roster. This also did horribly.

I took a look at what was going on under the covers. I found that for each letter, the confidence of that letter being the right letter is pretty high compared to the rest of the confidences, but some other letter always beats it by a little bit. And my algorithm doesn't care about 2nd place. Therefore, I need another way!

Huh. How 'bout dat

2009-03-02T22:51:00.001-08:00

Well. My real road block at this point was extracting letters from the test data character boxes because I lost my code from last year. But losing the code wasn't the real bad part - the code wasn't very good in the first place. It had all sorts of hough transforms in it.

Instead, I decided to take a blank sheet and do normalized cross correlation with it against a filled in box. This way, I could find the center of the filled in boxes. I basically figured out how big the boxes are, and can now extract the letter mo' betta. The red circle is where the normalized cross correlation signal was the strongest.

Zample:

To extract the letters, I found that the thickness of the character box lines were about 3 pixels wide so I took this into account.

The result:

Yee-haw. I took the output of this and fed it into my "get rid of white space" function, and resized the letters to 24 by 24 pixels. I also checked if the sum of the pixels of the character image are above a certain threshold, and if so, I assumed there was no letter there. I display these as gray cells with an x through them. This resulted in the following:

Here is another zample.

There is an issue though. SOME people (I'm not going to name any names) cannot write inside character boxes. Here is an example:

Because of that last 'a', my algorithm thinks there's a legitimate character there. See:

However, as far as I can tell, if someone can't keep their characters inside the boxes, they don't deserve to get their quiz graded! They can play games... but so can we! They want to play games, so be it! Let the games begin!

Testing out the classifiers

2009-03-02T11:20:00.000-08:00

I created and saved off 26 different classifiers - 1 for each lower case letter. I started out with 5000 haar-like features and brought it down to 200. So now, the feature vectors will be of length 200. I chose 200 because I found that after 200, there was no improvement in performance. Take a look at the following graph:

As you can see, performance is saturated after 180 iterations. This threshold varies for the different letters, but 200 is always enough from what I've seen.

I spent the majority of my time this weekend dealing with my old code for extracting letters from test data. To remind you, I am given something like:

... and I need to extract all of these letters. I wrote code for this last year but seem to have lost it :) So, I wrote new code to extract the letters which was time consuming. I am not entirely happy with the result of the code either, but I'll deal with it for now.

Given 4 images of 1 type of letter that were automatically extracted with the code I wrote, I ran a number of the 26 different classifiers on them to find the confidences. Confidence ranges from 0 to 1 where 1 indicates that it is 100% confident that the letter is a true instance, and 0 means the classifier is 100% confident that the letter is a false instance.

Here are 4 examples of the letter 'n':


Classifier  Image 1  Image 2  Image 3  Image 4
    n       0.4799   0.4897   0.5225   0.5120
    a       0.3878   0.4333   0.3969   0.3969
    b       0.4337   0.4499   0.4552   0.4967
    c       0.3715   0.3448   0.3443   0.3232

So, the 'n' classifier does the best, which is a relief. However, these numbers can be pretty close, so hopefully the roster information will take care of this.

I wrote another perl script to generate the transition probabilities because I seem to have lost my old one also. Given that the current letter is 'x', I find the probability that the next letter is a 'y' by dividing the number of occurrences of the string 'xy' by the number of occurrences of the letter 'x'.

Where the classifier is at now

2009-02-23T15:32:00.001-08:00

Here is the ROC curve for the training data:

And for testing:

The curve is perfect for training but not excellent for testing. The next step is just to use what I have for my overall project.

Improving the ROC curve

2009-02-22T23:13:00.000-08:00

It turns out that the ROC curve posted in the previous post was incorrect. I accidentally tested on my training data. Oooops! Once I fixed this bug, my ROC curve became very ugly. In fact, this is what it looked like:

Uh oh! This scared me. I started tweaking the algorithm by changing the number of haar features from 1,000 to 5,000, and changed the number of weak classifiers from 25 to 100. This barely made any difference. I then thought that maybe my 24 by 24 pixel character images simply weren't sufficient so I generated new training data and made the images slightly bigger - 40 by 40 pixels. This also didn't make a difference.

What did make a difference was centering each of the images and getting rid of the extra white space. This changed the ROC curve to this:

Boosting in Matlab

2009-02-18T15:06:00.001-08:00

Boris gave me his Matlab boosting code. His code is an implementation of Adaboost using haar-like features. The weak classifier is just a stump (looks at 1 feature and thresholds it).

The idea behind boosting is that many weak classifiers together create 1 strong classifier. The weak classifiers used in this implementation are extremely trivial and their individual accuracy is not that much better than 0.5. However, as we add more weak classifiers to the overall classifier, the overall accuracy improves, as shown in the following graph:

What is a haar feature?
In this implementation, a random number of rectangles are created, each with a different weight. Note that all of the training images must be the same size. We choose these haar features without seeing the images yet. The sum of the pixels in each of the different rectangles and the weights are used to come up with the feature. Each haar feature will result in 1 singleton value for each image.

Example of haar features:

What you'll need for an 'X' classifier:
1. A pool of images of 'X' (positive examples)
2. A pool of images that do not contain 'X' in them (negative examples)

Set aside part of each of the above pools for testing. The remaining, you'll use for training.

How it will go down:
1. Choose the number of haar features to create, and call this nh.
2. Apply all nh haar features to all of the training images, both positive and negative. As a result, for each image, we will have a feature vector of length nh.
3. Choose the number of weak classifiers desired, and call this nwc. Note that nwc <= nh.
4. Choose nwc of the nh haar features. Ideally, these nwc haar features are the best haar features out of the bunch. This means that these features are the strongest. Associate a threshold for each of the nwc haar features.
5. For each of the test images, find the nwc features. We now have a feature vector of length nwc for each of the test images.
6. Given the threshold for each of the nwc features, come up with a confidence for each test image.

I created an 'a' classifier for my project. I resized all of my training images to 24 by 24 pixels. I used a portion of the images of 'a' as the positive training examples, and used the remainder of them for testing. I used a combination of images of letters 'b' through 'z' as the negative training examples, and a separate portion of those for testing. Using a threshold of 0.5, the number of false positives was 194/1350, which comes out to a rate of 14%. The true positive rate is 100%. Here is the ROC curve:

How this will apply to my project: Given an image of a letter, I will apply all 26 classifiers to it. I will then have a score for each letter, and can use this instead of the nearest neighbor mechanism I was using before.

Boosting with OpenCV

2009-02-09T15:49:00.000-08:00

My next step is to apply OpenCV's boosting framework to my problem. I have OpenCv installed, and after a bunch of linking issues, I can at least get things to compile. I have spent this weekend and today figuring out how to use it. I have a much better handle on it now and will hopefully get it working soon.

I have been referencing this tutorial, which is ok.

I plan to train 26 different classifiers, one for each letter.

Random fact: OpenCV either lets you give it one training image, where it takes random samples of the image, or it lets you give it a bunch of images and it does nothing with those. Although the tutorial mentioned above provides a way to combine the 2 approaches.

Trying PCA

2009-02-02T14:46:00.001-08:00

I decided to use PCA on my training data. The way I did this is I used Matlab's princomp function. So I run princomp on my n x p matrix (n row vectors, where each row vector has p values). I then get a matrix D of size p x p. I decided to use the first 100 components, so I multiplied my n x p data matrix by D(:,1:100). Sometimes the results are better, sometimes they are worse. I will do more experimentation and report back.

Fixing the cropping issue

2009-01-26T15:10:00.000-08:00

I've spent some time now fixing up my cropping function. The reason I've been spending my time on this is because I think that it's really important to have quality training data. If my training data is crap, then nothing will work. I want to be able to cleanly cut out letters. So, I changed my cropping algorithm to the following:
cut the original image into 4 pieces, as follows:

Here is the left piece:

Right piece:

Top piece:

Bottom piece:

I run the hough transform on all four pieces. In each, I know where a line would be, if there exists one. I have some way of thresholding whether or not there is a line there (if the maximum number of votes is higher than a certain percentage of the length of the image). If so, I cut the appropriate piece out.

The performance isn't as great as expected. I think that I need to fix up my hough transform function because sometimes, when there appears to be a dark line, it won't find it (the number of votes is low).

Here are the overall results anyway:

The letters straight out of the training sheet look like this, with no postprocessing:

The next step for me is to fix my hough transform function, get the training data looking good, retrying nearest neighbor, and then moving on to opencv (boosting).

Cropping

2009-01-14T13:34:00.000-08:00

I get better accuracy now, when I try to classify my test data. However, I noticed that after my "cropping" tool, the test data can get pretty deformed. For example, take a look at a before and after sequence:

Before:

After:

I decreased the dimensionality of the test data by a lot. The new test data characters are 32 by 32 pixels. Before this, it was 120 by 123 pixels. This reduction in dimensionality really brought down the running time of classification. I think that I need to tweak my cropping tool though.

Cropping tool = bad. Exhibit A:
=

When I change it that only 2% of the pixels can be all white (instead of 5%), then the cut out changes to:

Now, the same test set looks like this:

Fixing up training data

2009-01-12T15:29:00.000-08:00

I noticed that the actual letters in my training data take up a small area in the actual image. This seems bad, so I fixed up my code to minimize the amount of white space surrounding the actual letter.

Example of old training data:

Example of new training data:

I'm baaaack

2009-01-03T22:08:00.000-08:00

Didn't get enough last year? Miss me? Well, I'm back for more. I will be continuing the same project. Here is a refresher of how the project works:

The first thing that I will be doing this week is getting back to the point I was at at the end of winter 2008. I will then research machine learning methods to apply to the problem, to replace the nearest neighbor approach.

Presentation slides

2008-03-11T20:08:00.001-07:00

...can be found here.

LoG filter not too hot either

2008-03-11T19:42:00.001-07:00

I still need to play with the kernel size but so far LoG (Laplacian of Gaussian) hasn't been helping out at all.

Using a bigger binomial kernel

2008-03-11T19:23:00.000-07:00

Using a bigger kernel didn't seem to help the nearest neighbor out :(

Incorporating another set of NN

2008-03-11T19:15:00.000-07:00

Currently when I run my algorithm, I come up with the most likely set of states that made up the character images. In other words, I come up with a predicted name. I now run nearest neighbor with the predicted name against the roster names and say that the nearest neighbor is my predicted name. This way my predicted name is at least a valid possibility.

And now... I get 100% accuracy. That's right. Yeah yeah, the roster only has 7 names but it is a start!!1!!.

The way I calculate the distance between two strings is I have a digit array with the indices of the characters - 'a' maps to 1, 'b' to 2, 'c' to 3 etc. Then I use Euclidean distance. In the future I can apparently use edit distance but Euclidean is fine for me for now.

Ok there is one more hack in there. The names are not all the same length, and in order for nearest neighbor to work, each feature vector needs to be the same size. The way I do this is have all of the feature vectors be the size of the longest name on the roster. The extra slots in the feature vector for names not as long as the longest name are set to zero. I require that the nearest neighbor returned be the same length as the query vector (before I add zeros). I think that this step helps a lot especially since the roster is so small. The next step is to have a test set that is much larger.

Filtering with a discrete binomial kernel

2008-03-11T14:14:00.000-07:00

I tried filtering both the training data and test data before running nearest neighbor on it to try and improve the nearest neighbor performance. Here is an example of a filtered test name:

As compared to the original unfiltered:

I used a 7x7 binomial kernel which turns out to be the following divided by 4096.


     1     6    15    20    15     6     1
     6    36    90   120    90    36     6
    15    90   225   300   225    90    15
    20   120   300   400   300   120    20
    15    90   225   300   225    90    15
     6    36    90   120    90    36     6
     1     6    15    20    15     6     1

This actually hurt my performance. For example, previously my accuracy on "James Carter" was ~45%. Now I predict "Geora Rdrter" and my accuracy is ~36%. Similarly, for "Richard Nixon" I now predict "Gerdora Rtero" and my accuracy is ~8.3%, when it used to be 25%.

It turns out that both 3x3 and 5x5 binomial filters are better than the 7x7, but still never improve performance; for the most part filtering with a binomial kernel hurts performance.

Emission probabilities

2008-03-10T13:25:00.000-07:00

An emission probability in my case is P(image|letter) ... the probability of the image given that you know it is of a particular character. In other words, the probability of a certain letter looking like this. The way I've been calculating this probability is P(letter|image), since I've been doing my own version of the nearest neighbor density. P(letter|image ) != P(letter|image).. this was wrong! I can use Bayes' rule to turn the probability around though:

P(image|letter) = P(letter|image)P(image) / P(letter)

I don't know what to plug in for P(image) so for now I've just been using 1 - each image has equal probability. For P(letter), this is easy to find - just look at how many times each letter appears in the roster and divide by the total number of characters. Since P(image) = 1, my new equation is:

P(image|letter) = P(letter|image) / P(letter)

I noticed that if a letter has high probability, P(image|letter) will go down (compared to a less likely character. The probability will go up because the denominator will always be <= 1) and if P(letter) is very low then P(image|letter) will be very high.

My results became worse once I took this new probability into account.

Results after scaling

2008-03-10T11:58:00.000-07:00

Like I said in my last post, the test images ranged from around 111 - 255, while the training images ranged from 0 - 255. I changed the range of the test images to also be 0 - 255 and I believe that my results improved.



Query name       Predicted Name   Accuracy
Lyndon Johnson   Gerdon Aninson   53.84615%
Gerald Ford      Gerald Rerd      80%
George Bush      George Resh      80%
Richard Nixon    Rildora Rtero    25%
William Clinton  William Clinton  100%
Ronald Reagan    Ronald Rerdon    75%
James Carter     Geora Carter     45.45455%

Looking into why my nearest neighbor results are awful

2008-03-08T15:14:00.000-08:00

Here I am comparing one of my test L's to half of my training L's. The test L is always on the right. Also the test L is a lot lighter than the training L's. In particular, the minimum value of the test L is 111 whereas the minimum value of the training L's is consistently 0. I am not sure if this will have an impact on my results or not.

Similarly, here are some 'o' comparisons, where the test 'o' is always on the right. No training 'o' matches the test 'o' exactly in size, which is a problem.

I'm not quite sure that the Viterbi algorithm is the right thing to be using for my case because it does not take into account the lexicon (roster) as much as it should.

Viterbi getting a little better

2008-03-03T12:02:00.000-08:00

I have implemented an "isPrefix" function in Matlab that works fine. The problem is that I don't know how to incorporate it into the Viterbi algorithm. Instead of using that, I have a function that takes in a character and an index and returns true if there exists a string in the roster with that character at that index, and false otherwise. I use this function when assigning emission probabilities - I only assign a character a positive emission probability if this character could be for realz.

Now the algorithm guesses "william clinton" correctly, but "lyndon johnson" it now guesses to be "lildon joreron", and "gerald ford" to be "georicarin". This algorithm will work especially badly for large rosters where the function taking in a character and an index will almost always return true. However with my small roster of 7 this function has helped.

Instead of having an "isPrefix" function, I plan to implement an "isSuffix" function because of the way that the Viterbi algorithm works when finding the most likely sequence. It starts at the end and works its way backwards.

Viterbi experiments

2008-03-02T18:13:00.000-08:00

I implemented the Viterbi algorithm and my results are not good yet but I am optimistic. Here is the setup:

I have 7 test images, here is the roster:

lyndon johnson
george bush
gerald ford
richard nixon
william clinton
ronald reagan
james carter

The names are all lower case because I'm not taking case into account yet.

I have calculated the transition probabilities - so I have a 26x26 matrix containing the probability of transitioning from 1 character to another. Here is how I calculated that:

P(o|e) = Count(oe) / Count(e)

This means that the probability that I see the sequence "oe" is the number of times I saw the sequence "oe" divided by the number of times I just saw the letter "e".

Emission probabilities, in my case, are supposed to mean "the probability of seeing this character image given that I know what the character is". For example, the probability of seeing this character image given that I know it is an 'a'. That probability is hard to calculate, I would have to use Gaussians and other crazy math. So, instead of doing that, for now I am doing a very simple nearest neighbor probability calculation. Given a character image, I run nearest neighbor against all of my training data and take the top 40 votes. I say that the probability that this character is an 'a' is the amount of votes for 'a' + 1 divided by 40 + 26. Ideally I would just say that the probability that this character is an 'a' is the amount of votes for 'a' / 40. However, my nearest neighbor framework is working pretty poorly so just because I have no votes for 'a' I don't want to completely eliminate this possibility. Therefore, no letter has zero probability.

I thought that even though my nearest neighbor framework is working pretty badly, that the transition probabilities would help out a lot because the roster is so small. Not really the case though!

Here is an example of an input name:

Here is what my algorithm came up with for the name:
licallinilicl

Yeah, pretty bad. At first I was like "are those even valid transitions?!" but it's true, each of those transitions are valid. For example "li", "William" is in the roster. So, I need to figure out a way to take more into account than just the bigrams. Maybe I should have an "isPrefix" function such that as I'm going through the HMM, only give something a probability if it is a valid prefix of a name. Ok that is what I will do next.

Experimenting with nearest neighbor

2008-02-25T14:31:00.000-08:00

Nearest neighbor shockingly doesn't work that well. I think part of the problem is that the training data isn't all that great and there isn't enough of it.

Here's the setup:

Training:
I have 90 training images for each letter in the alphabet (there are 26 of those). This makes for 2340 total training images, for those of you that can't do maf. All of the training images are the same size - 8 bit images of 120 by 123 pixels.

Testing:
So far I only have 2 names that I'm testing against but that size will grow shortly. I made the test characters also be 120 by 123 pixels (by adding extra white space evenly around the edges).

Here is the testing process:
I load all of my training data into a huge matrix of size 2340 x 14760, where each row is a strung out training image (of a character). I then read in a test character image, and find the euclidean distance between that test image and each of the training images, and sort the results based on the distances.

Currently I am looking at the top 50 closest matches and having those vote on a character. I have been getting some good and some bad results.

The first letter I tried, 'J' from "Jean Poole" had 'J' as its top match!
At that point life was pretty good. For one thing, all of the top 10 matches were j's. So that case works pretty well.

The next letter I tried was 'e':

The top match for that was 'p'... not so good. In fact, only 3 of the 50 votes were for 'e'. Here are the training e's... so you're trying to tell me only 3 of these look like that 'e' up there?

Here is another example.. 'o':

Luckily the mode of the top 50 matches is 'o', so 'o' wins but still, some weird results. The training image that is closest to the 'o' is the following 'n':...

I don't really get why that is. Here is the second closest match:

This is a little more reasonable, even though it is a 'c'. You can see the resemblance.

Lastly, here is the third match:

This happens to be a 'g' that was cut-off at the bottom during the traumatizing training process. This is also fairly understandable. Finally, the 4th closest match is an 'o'. (Of course after that there are plenty more random results.) This is what the first matching 'o' looks like:

First try at nearest neighbor - very simple!

2008-02-13T15:58:00.000-08:00

I took one of my a's from "Jean Poole" and ran nearest neighbor with it against my training a's and b's only, and the nearest neighbor was an 'a'! Phew. At least that works. As a matter of fact, the top 10 nearest neighbors were a's, and then there was a 'b' and so on. And now for harder tests....

Test images all the same size

2008-02-13T13:37:00.001-08:00

These are some examples of test images after I've made them all the same size. Now I have to do the same for training images and make sure the test images AND training images can be the same size!

Just to give you an idea, the size of the characters are about 76 by 40 pixels.

The 'h' here is bad, but I can't fix this without changing the code a lot and in the process making other things break:

This one looks good to me:

Example of test data

2008-02-13T12:22:00.002-08:00

Here is what the test data looks like once I've isolated the character boxes and done a little thresholding:

Here is what the test data looks like after I've removed the unwanted lines towards the edges:

Training data all set

2008-02-11T15:40:00.000-08:00

Partial set of training data for character 'a':
All of these individual characters are saved to their own .png file. The next step is to make them all the same size by adding extra white pixels to the boundaries, based on the size of the largest training image. Then, I will perform the nearest neighbor algorithm on the test data. The goal is for this to be done by Wednesday.

Looking at thresholded characters

2008-02-06T13:50:00.000-08:00

Just for kicks, this is what the training images look like as binary images. The top row is the 8-bit image and the bottom row is the binary image.

And b's, as always:

Here all I have to store are the non-zero indices, as opposed to storing the whole image, which is beneficial. And now I should center these characters! (Subtract off the centroid... why is that so hard?!)

Using results of edge.m

2008-02-04T15:11:00.000-08:00

Since there are artifacts near the edges on the letters both in the training and test data, perhaps I will use the results of edge.m to run nearest neighbor on. Here are examples of outputs of edge.m (the figures with black in the background).

Training data 'a':

Training data 'b':

Test data with edge.m run on the individual characters (after removing the leftover lines). Still needs some work.

And these were the original characters.

Another test data image:

I'm better at getting rid of leftover lines!

2008-02-04T14:16:00.001-08:00

Yes, I am. Now the next step is to save all training characters in one place. Here are some examples of the training data (because you really need more).

Top line is after lines were removed, bottom is before.

Example 1:

Example 2:

Example 3:

Example 4:

Getting rid of leftover lines

2008-02-04T12:44:00.000-08:00

To get rid of the leftover lines, I expand a rectangle starting in the middle of the character image and stop it when the sum of each rectangle edge is at a maximum (has the most white space).

One issue is that the size of the character boxes will vary now, but hopefully I will be able to correct this by zero padding the images (or 1 padding...).

Sometimes it works, sometimes it doesn't. Here are some examples of before and after removing the leftover lines. The images on the top half of the figures are after, and on the bottom are before.

Good example of 'a':

Good 'b' example:

Bad 'a' example:

Removing leftover edges

2008-01-31T16:16:00.000-08:00

Hmmmmmmmm..... how to get rid of the junk towards the edges of the figure.

I got some training data

2008-01-30T15:56:00.000-08:00

Fabian gave me 18 filled out handwriting sheets, which is very helpful! I have been parsing those, and have been getting better results. Here is an example of another filled out sheet - that was scanned in at an angle. Luckily, that isn't a problem!

Here are examples of the a's from this image:

Here are examples of the b's from this image:

Example of cut out training data

2008-01-28T15:46:00.000-08:00

Here are some example a's:

Here are some example b's:

You get the picture. The question now is how much that extra noise at the edges of the letters is going to have an effect.

Example of training data

2008-01-28T14:36:00.000-08:00

Here is an example of the training data I'll be using for character classification. It is called ABCDETC and is from NEC Labs, available here

I am using the same parsing method that I am using for the scanned names. Here non maximal suppression actually works!

Non maximal suppression not really working

2008-01-25T15:20:00.001-08:00

My plan was to find the top vertical line found from the hough transform (the one with the most votes) and then take the angle from that line and assume that that angle is the angle of the remaining vertical lines that I'm interested. So at that point I take the column vector of the hough space corresponding to that angle and sort it in descending order and plot the top 20 lines found. I also implemented non maximal suppression in the following way: for each line that I'm about to plot, I check if the amount of votes for that line is the maximum in that cell's surrounding window (just looking at changes in rho, not theta). If it isn't a maximum then I skip it - I don't plot that line.

I've been having a hard time playing around with the window threshold - how big should the window be? When it is too big then I start missing lines that I need but when it is too small then it doesn't get rid of enough lines. The following is a perfect example. I was playing with the threshold for the following image and this was the best I could get it. It didn't get rid of the additional vertical line between the e and the a, while it missed the line between the n and the space.

Isolated letters

2008-01-25T10:58:00.000-08:00

These are what the letters look like when I cut them out of the image based on the lines found by the hough transform:

My next step is to write a function that takes in one of these letter images and determines whether or not there is a letter inside. I also need to think of a way to implement non maximal suppression!

Better Isolated Boxes

2008-01-23T11:05:00.001-08:00

Here are two examples of the lines around the character boxes. This is after determining the width and height of the boxes and then drawing lines on top of the figure.

Isolating character boxes

2008-01-22T20:19:00.000-08:00

This is where I'm currently at with regards to isolating the character boxes:
This is without rotating the image at all - just taking both the vertical and horizontal gradient, running edge.m on each of those, and then running the hough transform on the result.

Here is a cool image of the hough space for the vertical lines:

I have been trying so hard to rotate the images properly that I forgot my real goal which was to isolate the character boxes. Finally when I was able to rotate the image, it turned out that that did not help me out at all! Here are examples of before and after rotated images:
As you can see, Matlab didn't do a great job cropping the image after rotating it, even though I specified 'crop' to imrotate.m. Oh well, for the time being I'm not using it anyway.

Better angles from Hough

2008-01-16T15:03:00.000-08:00

I decreased the size of the cells in the accumulator array that the Hough Transform uses and the accuracy of the angles of the detected lines significantly improved. Yesterday I was using a resolution of 1 radian, but now my resolution is pi/450.

There are still too many lines detected for the upper boxes compared to the lower boxes. Here is what I get when I plot the top 5 lines detected (instead of thresholding):

3 of the 5 lines detected are for the top horizontal line. The 12th line that is detected is the upper horizontal line for the PID. I'm not quite sure why that is. Here is what I get when taking the top 12 lines:

When I get greedy and increase the resolution of the angle too much, I start to hurt from it by failing to detect lines. For example, when I set the resolution to pi/720, my top 20 detected lines are the following:

It doesn't even detect the bottom horizontal line.

This is the process I've been using to detect the lines:
1. Resize the image to half of its size.
2. Take the gradient of the image.
3. Run edge.m on the vertical gradient image, specifying 'sobel' as a parameter.
4. Run the Hough Transform on the result of edge.m
5. Sort the accumulator matrix in descending order and plot the top x lines on top of the original image.

Here is an example vertical gradient of the image:

Here is an example of the output of edge.m, passed into the Hough Transform function:

Finally, here is an example of output from the Hough Transform function:

The white portions in the middle of the image correspond to the lines detected in the image.

The next significant problem is detecting the vertical lines. When I instead use the horizontal gradient, here are the top 20 lines I detect (none of which are useful):

Also, here is the output of the Hough Transform. Note how many white parts there are - meaning lots of lines were detected.

Ok one last thing - here is what is given to the Hough Transform function in the vertical case:

Hough is working better but not there yet

2008-01-15T13:51:00.000-08:00

The change I made was first taking the gradient of the image before running edge.m on it (and finally the hough transform). This seemed to get rid of a lot of the extra lines towards the top of the image without sacrificing the lines on the bottom of the image.

I still have the problem that the lines that are detected seemed to not be oriented correctly - perhaps the angle is off.

Here is what I get now just looking at the vertical gradient and thresholding at 50% of the accumulator:

The next step is to get the lines detected on target (have the right angle) and also detect the vertical lines (which has proven to be significantly more difficult).

Why is the Hough Transform not working?

2008-01-14T19:27:00.001-08:00

Ugh... these lines are incorrect!

Thresholding at 50% max value of accumulator:
Finds too little lines and the lines that it finds aren't completely correct imho:

Thresholding at ~44% max value of accumulator:
Finds too many lines for the name portion and not enough lines for the PID portion!:

[Ignore the titles of these images!]

Sample Input

2008-01-11T16:02:00.000-08:00

Here is an example of an input quiz or assignment. This is the subset of the quiz or assignment that contains the student's name and PID number. Part of the preprocessing will be isolating the name and PID number from the rest of the quiz.

One idea that is up in the air right now is using character boxes for the students to enter their name and PID. This simplifies the problem significantly, as I do not need to figure out myself where one letter ends and the next begins.

Welcome to Dafna's CSE 190 blog!

2008-01-06T12:57:00.000-08:00

I will be doing a project on the recognition of handwritten names from a limited and closed lexicon using a hidden markov model.