Where the classifier is at now

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

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

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

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

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.