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?
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:


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.

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).