Methodology

1. Tiny image representation with nearest neighbor classifier

Using the 16*16 tiny image representation and training the data with a nearest neighbor classifier, the overall accuracy of the system reaches 22.5%.

2. Bags of SIFT features with nearest neighbor classifier

Two steps are conducted in this part. First, a vocabulary of size 200 is built using the training data. 20 features are randomly obtained from each image, with k-means clustering method applied afterwards to obtain the 500 centers for the vocabulary. Next, 1000 features are obtained from each image to form the histogram for each training and testin image. The label of the testing image is assigned by its nearest neighbor image in the training set. The overall accuracy reaches 52.3%.

3. Bags of SIFT features with support vector machine

This part differes from part2 only by the classifier chosen. Instead of using nearest neighbor classifier, 15 support vector machine classifiers are used with one for each class. The algorithm reaches 63.1% accuracy.

Extra Points Implementation

1. Soft Assignment for creating histogram

Instead of using the nearest neighbor for classfying features into clusters, each feature casts a vote on each cluster as long as it is near enough to the cluster center. In practice, the feature gives a vote with value 1 to its nearest cluster center. It will also give a vote with the value to every other cluster based on the ratio of the distance between feature and nearest cluster center and the distance between feature and the corresponding cluster center. This ratio is thresholded at the level of 0.8 to prevent giving out too many votes to completely irrevelant clusters. The accuracy is boosted by a bit, reaching 67% eventually.

2. Cross Validation

I have used cross validation for reporting the performance of the system. 100 training and testing images are randomly picked in each iteration. Average accuracy and standard deviation are reported. However, cross-validation runs pretty slow as it requires a few iterations of training. I have only run the algorithm for reporting accuracy for tiny images with nearest neighbor, and bags of SIFT features with svm. The result is visualized in the following table.

#	Tiny Images with Nearest Neighbor	Bags of SIFT with Support Vector Machine
1	0.231	0.672
2	0.243	0.683
3	0.223	0.685
4	0.215	0.677
5	0.223	0.669
6	0.216	0.676
7	0.224	0.670
8	0.231	0.677
9	0.241	0.661
10	0.235	0.681
Mean	0.2282	0.6751
Standard Deviation	0.0097	0.0073

The system presents pretty stable performance upon the cross validation.

3. Performance for different vocabulary size

I have done some experiments with the vocabulary size used and evaluated the accuracy. The experiment is on the bags of SIFT features with soft assignment and svm classifier. The result is shown in the following table.

Vocabulary Size	Accuracy	Average time for obtaining feature histogram for 100 images (s)
10	0.405	9.634
20	0.536	9.344
50	0.595	10.672
100	0.642	12.602
200	0.650	17.846
500	0.669	31.363
1000	0.671	50.303
10000	0.653	337.792

As the table shows, the accuracy increases as the vocabulary size increases, but capped at around 65% to 70%. When the vocabulary size reaches 100, the accuracy hardly increase as the vocabulary size increases. Therefore, the best accuracy that this system can probably achieve is around 65% to 70%. The running time increases a lot as the vocabulary increases. Given that the accuracy performance does not change a lot, it is probably unwise to keep a huge vocabulary.

4. Performance on multiple scales

I have also done some experiments with the scale of the image. The image gets gaussian blurred in each scale and the corresponding accuracy is reported in the following table.

Sigma	Accuracy
0 (Unblurred)	0.671
2^0.5	0.577
2^1.0	0.553
2^1.5	0.509
2^2.0	0.479
2^2.5	0.449

As the table shows, the accuracy of the recoginition drops by a few percent in each level. As the images are gradually losing high-ferequency information, it makes sense that the accuracy is in a decreasing trend.