[HW5] Scene Recognition with Bag of Words

Bag of words models are a popular technique for image classification inspired by models used in natural language processing. The model ignores or downplays word arrangement (spatial information in the image) and classifies based on a histogram of the frequency of visual words. The visual word "vocabulary" is established by clustering a large corpus of local features. See Szeliski chapter 14.4.1 [1st ed.] / 6.2.1 [2nd ed.] for more details on category recognition with quantized features. In addition, 14.1 [1st ed.] / 6.3 [2nd ed.] covers classification techniques.

Strat by extracting features from training data images. We can use cv2 Python library functions cv2.SIFT_create() and cv2.HOGDescriptor() to scale-invariant feature transform (SIFT) features and histogram of oriented gradients (HOG) features, respectively. You should implement to extract features using both of these in feature_extraction.py. You can use cv2 library functions for SIFT and HOG feature extractors, but you should investigate how to use these functions and convert their returns into desired format, suggested by comment lines in feature_extraction.py. Note that we have learned that there are two ways regular grid and interest regions for feature extraction in the lecture (see p.61 in slide22). In this homework you should implement via regular grid. When you implement SIFT, use an image grid size 20, and use an image grid size 16 for HOG. If we run SIFT feature extractor with parameters given in the starter code then the feature dimension becomes 128, and if we run HOG then it becomes 36.

We will not apply PCA for the final result of scene recognition in this assignment, but PCA is a significant technique of data analysis. You should implement PCA on our vocabulary, a set of feature vectors, and reduce the feature dimension to 3. The implemented code should be written into get_features_from_pca.py, and you should visualize the PCA result using the starter code pca_visualize.py. Attach the visualization figure to your writeup document.

Now we are ready to represent our training and testing images as histograms of visual words. For each image we will densely sample many feature descriptors. Instead of storing hundreds of feature descriptors, we simply count how many feature descriptors fall into each cluster in our visual word vocabulary. This is done by finding the nearest neighbor k-means centroid for every feature descriptor. Thus, if we have a vocabulary of 50 visual words, and we detect 220 features in an image, then our bag of words representation will be a histogram of 50 dimensions where each bin counts how many times a feature descriptor was assigned to that cluster and sums to 220. The histogram should be normalized using L2-norm so that the image size and the number of features do not dramatically change the bag of feature magnitude. You should implement code to get bag of words representation as a histogram from given image file in get_bags_of_words.py. The starter code function pdist() in distance.py may be helpful to get distances between the feature vector and each of vocabularies.

The last task is to train 1-vs-all linear SVMs to classify the bag of words feature space. Linear classifiers are a simple learning model. The feature space, the space of the histogram vectors, is partitioned by a learned hyperplane and test cases are categorized based on which side of that hyperplane they fall on. Despite this model being far less expressive than the nearest neighbor classifier, it will often perform better. For example, maybe in our bag of words representation 40 of the 50 visual words are uninformative. They simply don’t help us make a decision about whether an image is a 'forest' or a 'bedroom'. Perhaps they represent smooth patches, gradients, or step edges which occur in all types of scenes. The prediction from a nearest neighbor classifier will still be heavily influenced by these frequent visual words, whereas a linear classifier can learn that those dimensions of the feature vector are less relevant and thus downweight them when making a decision.

There are numerous methods to learn linear classifiers, but we will find linear decision boundaries with a support vector machine. You do not have to implement the support vector machine. However, linear classifiers are inherently binary and we have a 15-way classification problem, so you should implement the 15-way classification in svm_classify.py using svm library functions. To decide which of 15 categories a test case belongs to, you will train 15 binary 1-vs-all SVMs. 1-vs-all means that each classifier will be trained to recognize 'forest' vs. 'non-forest', 'kitchen' vs. 'non-kitchen', etc. All 15 classifiers will be evaluated on each test case and the classifier which is most confidently positive "wins". E.G. if the 'kitchen' classifier returns a score of -0.2 (where 0 is on the decision boundary), and the 'forest' classifier returns a score of -0.3, and all of the other classifiers are even more negative, the test case would be classified as a kitchen even though none of the classifiers put the test case on the positive side of the decision boundary. When learning an SVM, you have a free parameter 'lambda' which controls the model regularization. Your accuracy will be very sensitive to lambda, so be sure to test many values. See svm_classify.py for more details.