# How do I represent SURF Features into Bag of Words to determine Nearest Neighbors?

I'm trying to use Speeded Up Robust Features (SURF) to get the $k$ most similar images from a set of images in my directory. I'm planning to use $k$-Nearest Neighbours ($k$-NN) for this. As far as I know, the size of SURF descriptors are $n \times 64$ or $n \times 128$ depending on how many descriptors I want. There are suggestions and I've read about the Bag of Visual Words method, where these patches are converted to bags of words, similar to the common Natural Language Processing technique. I've also read that Bag of Visual Words are generated by clustering, whereas the feature patches are clustered together.

What I don't understand is, how can I use these Bag of Visual Words to train my $k$-NN such that I can get similar images? I really can't grasp how those clusters can generate BoWs. Say I have 1000 images, if I convert them, what will they look like? Will they be 1000 BoWs that still represent the same images?

• Multiple approaches to the problem are possible, making this question hard to answer. For instance, you could try making Bags of Visual Words. Oct 23 '17 at 16:08
• I see. But I do understand that Bag of Words just makes the descriptors clustered into one another but how do I get the nearest neighbors of the query image? Oct 23 '17 at 16:40
• You would treat the resulting BoWs as a feature vector: compare the query image's BoW with the other images' BoWs. Oct 23 '17 at 16:45
• This is the part where I don't understand what's happening. Aren't BoWs generated using clustering? How do I retrieve or generate the BoWs of the images of they're in clusters? Oct 23 '17 at 16:47
• You may wish to edit your question to narrow it down to that specific concern. Then me or someone else may answer it. Oct 23 '17 at 16:48

The Bags of Visual Words (BoWs) approach to image retrieval, described in works such as Sivic et al. "Video Google: a text retrieval approach to object matching in videos" (2003) and Csurka et al. "Visual categorization with bags of keypoints" (2004), is composed of multiple phases:

1. First, a visual vocabulary, often called a codebook, is generated. This is usually done by applying k-means clustering over the keypoint descriptors of a data set, or a sufficiently descriptive fraction of it. The vector $\mathcal{V}$ of size $k$ containing the centroids $\mathcal{V_i}$ of each cluster is your visual vocabulary.

• In this case, each image $x$ should yield a variable number $x_n$ of SURF keypoint descriptors, usually of size 64 each. One can aggregate all keypoint descriptors from multiple images and perform k-means clustering over all of them.
• The choice of the $k$ hyperparameter in clustering depends on the image domain. One may try multiple values of $k$ (10, 100, 1000) to understand which is more suitable for the intended task.
2. Afterwards, each image is "tested" against the codebook, by determining the closest visual vocabulary points and incrementing the corresponding positions in the BoW for each keypoint descriptor in the image. In other words, considering an image's BoW $B = \{ o_i \}$: for each image keypoint descriptor $d_j$, $o_i$ is incremented when the smallest distance (often the Euclidean distance) from $d_j$ to all other visual vocabulary points in $\mathcal{V}$ is the distance to $\mathcal{V}_i$.

• The result is a histogram of visual descriptor occurrences of size $k$, which can be used for representing the visual content. As similar images will yield similar bags of words, one can compare images through their BoWs. The Euclidean distance between them is a commonly used metric here.

Therefore, the bag of words of each image makes a global representation of that image. When performing content-based image retrieval, the $n$ most similar images are retrieved by fetching the $n$ closest (or approximately closest) bags of words to the query image's. No training process is required at this point (we can picture visual vocabulary generation as an offline training phase).

• Ahhh. I see. Now I understand why no training is required. However, are all of these doable using scikit-learn? I do understand the theory in it. However, please correct me if I am wrong but what I'm gonna do is that, I'm going to cluster the descriptors of 1k images OR do I put them all in one array and cluster them? After which, in order to "test" against the codebook, I get the closest cluster for each descriptor and each descriptor would represent an column in the BoW? Oct 23 '17 at 18:13
• (1) You can use scikit-learn for k-means clustering. The BoW calculation procedure might not exist directly in it, but it's fairly easy to implement (I've once written this part in Rust). (2) You cluster once, over all of the image descriptors. This makes the codebook aware of the entire domain. (3) That is correct. Each possible index in a BoW vector is associated to a cluster in the vocabulary. Oct 23 '17 at 18:28
• Correct me if I'm wrong, after converting all images into BoWs, I'll still have to iterate over all of them and then compute the closest one using Euclidean distances? Oct 23 '17 at 18:34
• Yes, that would need to happen on each query, unless you build an index of feature vectors designed for fast ND feature vector retrieval, some of which provide near-optimal results. Oct 23 '17 at 18:37