KNN > SVM

I just finished fixing my K-nearest neighbor program and what do you know, its detection rate is consistently better than the svm. The results on the k-fold cross-validation testing where k=5 is:

KNN

(K=1)

1. 72% accuracy, # test images = 129
2. 82% accuracy, # test images = 129
3. 75% accuracy, # test images = 129
4. 74% accuracy, # test images = 128
5. 77% accuracy, # test images = 129

(K=3)

1. 79% accuracy, # test images = 129
2. 83% accuracy, # test images = 129
3. 77% accuracy, # test images = 129
4. 75% accuracy, # test images = 128
5. 77% accuracy, # test images = 129

(K=5)

1. 75% accuracy, # test images = 129
2. 86% accuracy, # test images = 129
3. 81% accuracy, # test images = 129
4. 73% accuracy, # test images = 128
5. 77% accuracy, # test images = 129

(K=7)

1. 79% accuracy, # test images = 129
2. 84% accuracy, # test images = 129
3. 76% accuracy, # test images = 129
4. 74% accuracy, # test images = 128
5. 79% accuracy, # test images = 129

SVM

1. 79% accuracy, # test images = 129
2. 65% accuracy, # test images = 129
3. 59% accuracy, # test images = 129
4. 62% accuracy, # test images = 128
5. 71% accuracy, # test images = 129

Personally, I find these results very interesting....

Cross-validation and KNN

Throughout the week I have been taking pictures of parking lots as I have walked to and from school each day. However, the number of ROI from my image set is still pretty small, around 650 distinct parking spaces, and this may be adversely affecting my training efforts. Most research papers that I've read have said that good results are often achieved with somewhere between 1000 and 2000 bits of training data.

The next thing that I did was to implement a cross-validation script. I ended up coding a K-fold in python which starts by randomizing the input data and then performs the cross validation. With K=5, the svm is classifying within a range of 59%-79% positive detection rate. This extremely wide range might be the result of poor randomization of the data on the part of the script and/or it might be due to the fact that I have very few night time images as part of my test data. Right now I'm going to increase the size of my test set and see if that has an effect in reducing the range of results returned by the cross-validation script.

The last thing that I worked on was to create a K-nearest neighbor classification program. I am still trying to debug the program but I hope to have it done sometime tonight or tomorrow.

SVMs

So I installed, trained, and ran SVMLight today. I used some images which weren't part of the training set and which were taken on completely different days than those taken for the training set (ie, no obviously similar images being used to train and test at the same time). However, these images were quite a bit larger than those that I trained on. I figure that because the features being used right now are color histograms and because this test was only to help me get my bearings, the difference in the sizes of the images wouldn't be extremely important for now. In the end, the SVM got 73% accuracy on the test set (58 pos detect, 21 neg detect), which I find encouraging for a first step.

One of the things I am considering doing next is relabeling my training set so that there are only non-occluded parking spaces being trained on. I also want to gather a more images to both increase the training set and also build a more realistic pseudo-test set. Lastly, I'm going to code up a program for visualizing the SVM's classification guesses overlaid on the test images if I have time.

Finished Histogramming

So I finally finished my color histogramming program. Since training the support vector machine is completely pointless unless the data you are training it on is accurate, I had to make sure that my 'histogrammer' was 100% bug free. Here are some of the test images I used to debug the program:

Currently, the program works by reading in the log file which contains a list of coordinate-image lines to extract the pixels from a particular region of an image. For each line in the log file the program does the following:

1. Compute the extraction region in the image.
   
2. Convert the image from RGB to L*a*b*.
3. Create 2 32-bin histograms, one for the 'a' channel and one for the 'b' channel (we discard the 'L' channel as it does not add much useful information in this case).
4. Compute the histograms.
5. Write out each histogram, bin by bin, to the resulting text file along with a 0 or a 1 to indicate if the region was a positive or negative training example.

With a log file of exactly 800 training regions, the program only took a couple of minutes to finish its calculations.

My next step will be to train a support vector machine on this training data. Since I'm most familiar with SVMLight, I'm probably going to start there.

Histograms

So I talked to Tom Duerig about using SMORs as the cascade backbone for my the detection algorithm. Although I'll probably have to do a bunch of tweaking, it sounds like SMORs will work really well with this project.

I also talked to Carolina Galleguillos about how GroZi uses color histograms as part of the overall algorithm. She was kind enough to give me a copy of the histogram source file to help me get an idea of how to create my color histogramming program.

I ended up coding the histogramming program from scratch since the code from GroZi was not completely applicable. Currently I'm in the process of testing and debugging the program.

Lastly, I labeled my training images using the labeling program I created last week.

Color Histograms

I have been researching different methods for coming up with features from the sets of empty and occupied parking spaces before I create the program to gather these features. The most useful paper that I've found on this subject is called Color Photo Categorization Using Compressed Histograms and Support Vector Machines by Xia Feng, Jianzhong Fang and Guoping Qiu. This paper goes over a bunch of different methods for describing color information in images as well as their methodology for using a support vector machine for classification using the color features described in the previous section. It seems that the MPEG-7 color structure descriptor got the best results and this is what I'm going to read about this in more detail next (specifically, Color and Texture Descriptors by B. S. Manjunath, Jens-Rainer Ohm, Vinod V. Vasudevan, and Akio Yamada).

Change of Direction

Due to some helpful advice I have refocused my research from car feature detection to the direct detection of vacant parking spaces. So far, the most promising work that I have found is by Qi Wu and Yi Zhang, two students at Carnegie Mellon. They're method for detecting the state (occupied/empty) of parking spaces centered around a SVM (Support Vector Machine) which was trained on the probability of the ground color. Overall, it sounds like they were pretty successful at creating a parking space detector. The one drawback to all of this is that this type of detector will only work well when there's very little occlusion by other vehicles due to a less than optimal camera angle. However, this seems like a good place to start and I think that using car feature detection in addition to this SVM-based detection algorithm could successfully deal with the cases where there's occlusion.

The first step towards implementing the SVM-based parking space detection algorithm is to extract the information from all of the parking spaces in the images in my training set. To this end, I have created a labeling program in Java which allows me to quickly label the parking spaces in the parking lot images and create a file log file of all of my label work. All one has to do is click on the 4 corners of a parking space and the program writes out the image path and coordinate information to the log file.

My next step will be to create a program to read the log file and quickly extract the set of pixels contained in each quadrangle. This way, I can label the pictures once, and extract the pixel info and create a set of parking space training features as many times as I want without having to relabel everything every time I make a change.