Description
Overview The bag-of-words (BoW) approach, which you learned about in class, has been applied to many recognition problems in computer vision. For example, object recognition [5, 7] and scene classification [6, 8]1 . Video Google https://www.robots.ox.ac.uk/~vgg/research/vgoogle/ is a good demonstration of this. This technique draws connection from Information Retreival, and has been studied extensively. Thus, there are many variants and extensions for the traditional approach explained in class. For example, two important extensions are pyramid matching [2, 4] and feature encoding [1]. What you will be doing: 1. You will take responses of a filter bank on images and build a dictionary of visual words (Section 2). 2. You will learn a model for the visual world based on a bag of visual words, and use nearest-neighbor to predict scene classes in a test set (Section 3). 3. Finally, we ask you to dig deep into visual words by trying to visualize them (Section 4). If the assignment looks long or difficult to you, DONT panic! We provide you with stepby-step instructions to implement a working scene recognition framework. There are not many lines of code to write. However, it may take a few hours for the base system to run, so make sure to try each component on a subset of the data set first before putting everything together. We have provided you with small subsets of the data for such testing (see Section 6). Image Data You will be working with a subset of the SUN database22 . The data set contains 1600 images from 9 scene categories like “kitchen”, “sky” and “desert”. A complete submission consists of a zip file with the following folders (please keep each system in a separate folder): 1. baseline/: the baseline spatial pyramid classification system that you implement through this homework; 1This homework aims at being largely self-contained; however, reading the listed papers (even without trying to truly understand them) is likely to be helpful. 2https://groups.csail.mit.edu/vision/SUN/ 2 2. improved/: (if you do the extra credit): the custom system that you design to boost the performance of your system; 3. a write-up (.pdf format). We provide you with a number of functions and scripts in the hopes of alleviating some tedious or error-prone sections of the implementation. You can find a list of files provided in Section 6. Please read these descriptions. Figure 3: The provided multi-scale filter bank 1 Warming up with some theory (10pts) In this section, you will answer some questions about the most basic Bag-of-Words approach. We provide a suggested number of lines for each answer are mentioned. Question 1.1 (3pts, 2-3 lines) Given an N × N image, and an h × h Gaussian filter, how would you convolve the image and the filter in O(h) instead of O(h 2 )? Question 1.2 (2pts, 2-3 lines) Does the bag-of-words approach respect spatial information? Why? Question 1.3 (5 pts, 2-3 lines) For images, why is it a better idea to use filter responses as features rather than raw pixel values? 2 Representing the World with Visual Words (40pts) We have provided you with a multi-scale filter bank that you will use to understand the visual world. You can get it with the following provided function: 3 Figure 4: An input image and filter responses for each of the 3 channels (a) Color Input (b) Output Map of Visual Words Figure 5: A sample output, rendered with imagesc. [filterBank] = createFilterBank() filterBank is a cell array3 Open the file createFilterBank.m to see how the filters were created. We have also provided you with a function to extract filter responses that takes a 3-channel RGB image and a filter bank and returns the responses of the filters on the image. [filterResponses] = extractFilterResponses(I, filterBank) filterResponses is an N ×M matrix, where N is the number of pixels in the input image, and M is the number of filter responses (three times the size of the filter bank, since you are applying it to a 3-channel image). Question 2.1 (5 pts, 3-4 lines) Theory: What properties do each of the filter functions pick up? You should group the filters into broad categories (i.e., all the Gaussians). Answer in your write-up. Creating Visual Words You will now create a dictionary of visual words from the filter responses using k-means. After applying k-means, similar filter responses will be represented by the same visual word. You will use a dictionary with fixed-size. Instead of using all of the filter responses (that can exceed the memory capacity of your computer), you will use responses at α random pixels4 . If there are T training images, then you should collect a matrix filterResponses over all the images that is αT × N, where N is the number of filter responses. Then, to generate a 3Look at MATLABs documentation for more details, but filterBank{i} is a 2D matrix, and filterBank{i} and filterBank{j} are not necessarily the same size. 4Try using randperm. 4 visual words dictionary with K words, you will cluster the responses with k-means using the built-in MATLAB function kmeans as follows: [unused, dictionary] = kmeans(filterResponses, K, ’EmptyAction’,’drop’); Question 2.2 (15 pts) You should write the following function to generate a dictionary given a list of images. [filterBank, dictionary] = getFilterBankAndDictionary(imPaths) As an input, getFilterBankAndDictionary takes a cell array of strings containing the full path to all images. You can load each file by iterating from 1:length(imPaths), and doing imread(imPaths{i}). Generate the αT filter responses over the training files and call k-means. A sensible initial value to try for K is between 100 and 300, and for α is between 50 and 150, but they depend on your system configuration and you might want to play with these values. Question 2.3 (5 pts, 3-4 lines) Theory How does the dictionary size affect the representation power of the bag-of-words pipeline, e.g., if I set k = 10 or k = 10, 000? What is the problem of a dictionary that is too small or too large? Once you are done with getFilterBankAndDictionary, call the provided script computeDictionary, which will pass in the file names, and go get a coffee. If all goes well, you will have a .mat file named dictionary.mat that contains the filter bank as well as the dictionary of visual words. Dont worry about “did-not-converge” errors. If it takes more than 10 minutes, reduce the number of clusters and samples. If you have debugging issues, try passing in a small number of training files manually. Computing Visual Words Question 2.4 (15 pts) We want to map each pixel in the image to its closest word in the dictionary. Create the following function to do this: [wordMap] = getVisualWords(I, filterBank, dictionary) wordMap is a matrix with the same width and height as I, where each pixel in wordMap is assigned the index of the closest visual word of the filter response at that pixel in I. We will use the standard Euclidean distance to do this; to do this efficiently, use the MATLAB function pdist2. A result is shown in Fig. 5. Since this can be slow, we have provided a function batchToVisualWords(numberOfCores) that will apply your implementation of the function getVisualWords to every image in the training and testing set. This function will automatically5 use as many cores as you tell it to use. For every image “X.jpg” in images/, there will be a corresponding file named “X.mat” in wordmaps/ containing the variable wordMap. You are highly encouraged to visualize a few of the resulting word maps; they should look similar to the ones in Figs. 2,5. 5 Interested parties should investigate batchToVisualWords.m and the MATLAB commands matlabpool and parfor. 5 3 Building a Recognition System (95pts) We have formed a convenient representation for recognition. We will now produce a basic recognition system with spatial pyramid matching. The goal of the system is presented in Fig. 1: given an image, classify (“name”) the scene where the image was taken. Traditional classification problems follow two phases: training and testing. During training time, the computer is given a pile of formatted data (i.e., a collection of feature vectors) with corresponding labels (e.g., “grass”, “sky”) and then builds a model of how the data relates to the labels: “if green, then grass”. At test time, the computer takes features and uses these rules to infer the label: e.g., “this is green, therefore it is grass”. In this assignment, we will use the simplest classification model: k-nearest neighbor. At test time, we will simply look at the querys top k nearest neighbors in the training set and transfer the majority label6 . In this example, you will be looking at the query image and looking up its k nearest neighbors in a collection of training images whose labels are already known. This approach works surprisingly well given a huge amount of data, e.g., a very cool graphics applications from [3]. The components of any nearest-neighbor system are: features (how do you represent your instances?) and similarity (how do you compare instances in the feature space?). You will implement both. Extracting Features We will first represent an image with a bag-of-words approach. In each image, we simply look at how often each word appears. Question 3.1 (10 pts) Create a function getImageFeatures that extracts the histogram7 of visual words within the given image (i.e., the bag of visual words). [h] = getImageFeatures(wordMap, dictionarySize) As inputs, the function will take: • wordMap is an H × W image containing the IDs of the visual words • dictionarySize is the number of visual words in the dictionary. As output, the function will return h, a dictionarySize × 1 histogram that is L1 normalized, (i.e ., Phi = 1). You may wish to load a single visual word map, visualize it, and verify that your function is working correctly before proceeding. Question 3.2 Extra credit (5 pts 2-3 lines) Theory: Why is it a good idea to normalize the histogram of visual words? (Hint: See Section 3.2 of [4]) 6 in case of a tie, use odd k 0 . 7Look at hist in MATLAB 6 Multi-resolution: Spatial Pyramid Matching Bag of words ignores the entire spatial structure of the image. In many cases, this may not be desirable. One way to alleviate this issue (and thus can often have a better representation) is to use spatial pyramid matching. The general idea is to divide the image into a small number of cells, and concatenate the histogram of these cells to the histogram of the original image, with a proper weight per cell. We will be using the work of [4] as reference, and will point you to specific sections as needed. Here we will implement a popular scheme that cuts the image into 2l × 2 l cells where l is the layer number. We treat each cell as a small image and count how often each visual word appears. This results in a histogram for every single cell in every layer. Finally to represent the entire image, we concatenate all the histograms together after normalization by the total number of features in the image. If there are L layers and K visual words, the resulting vector has dimensionality K PL l=0 4 l = K 4 (L+1) − 1 /3. Now comes the weighting scheme. Note that when concatenating all the histograms, histograms from different levels are assigned different weights. Typically (in Section 3 of [4]), a histogram from layer l gets half the weight of a histogram from layer l + 1, with the exception of layer 0, which is assigned a weight equal to layer 1. A popular choice is to set the weight for layer 0 and layer 1 to 2−L , and for the rest to 2l−L−1 (e.g., in a three layer spatial pyramid, L = 2 and weights are set to 1/4, 1/4 and 1/2 for layer 0, 1 and 2 respectively, see Fig. 6). Note that the L1 norm (absolute values of all dimensions summed up together) for the final vector is 1. Question 3.3 Extra credit (5 pts 2-3 lines) Theory Why do we weight different levels of the histogram differently? (Hint: See Section 3.1 of [4]) Figure 6: Spatial Pyramid Matching: From [4]. Toy example of a pyramid for L = 2. The image has three visual words, indicated by circles, diamonds, and crosses. We subdivide the image at three different levels of resolution. For each level of resolution and each channel, we count the features that fall in each spatial bin. Finally, weight each spatial histogram. Question 3.4 (20 pts) Create a function getImageFeaturesSPM that form a multi-resolution representation of the given image. [h] = getImageFeaturesSPM(layerNum, wordMap, dictionarySize)