## Introduction

[**Bag-of-features**][1] (BoF) (also known as **bag-of-visual-words**) is a method to represent the features of images (i.e. a feature extraction/generation/representation algorithm). BoF is inspired by the bag-of-words model often used in the context of NLP, hence the name. In the context of computer vision, BoF can be used for different purposes, such as [content-based image retrieval (CBIR)][2], i.e. find an image in a database that is closest to a query image.

## Steps

The BoF can be divided into three different steps. To understand all the steps, consider a training dataset $D = \{x_1, \dots, x_N \}$ of $N$ training images. Then BoF proceeds as follows.

### 1. Feature extraction

In this first step, we extract all the _raw_ features (i.e. keypoints and descriptors) from all images in the training dataset $D$. This can be done with [SIFT][3], where each descriptor is a $128$-dimensional vector that represents the neighborhood of the pixels around a certain keypoint (e.g. a pixel that represents a corner of an object in the image). 

If you are not familiar with this extraction of _computer vision_ (sometimes known as _handcrafted_) features, you should read the [SIFT paper][3], which describes a feature (more precisely, keypoint and descriptor) extraction algorithm.

Note that image $x_i \in D$ may contain a different number of features (keypoints and descriptors) than image $x_j \neq x_i \in D$. As we will see in the third step, BoF produces a feature vector of size $k$ for all images, so all images will be represented by a fixed-size vector. 

Let $F= \{f_1, \dots, f_M\}$ be the set of descriptors extracted from all training images in $D$, where $M \gg N$. So, $f_i$ may be a descriptor that belongs to any of the training examples (it does not matter which training image it belongs to).

### 2. Codebook generation

In this step, we cluster all descriptors $F= \{f_1, \dots, f_M\}$ into $k$ clusters using k-means (or another clustering algorithm). This is sometimes known as the _vector quantization_ (VQ) step. In fact,  the idea behind VQ is very similar to clustering and sometimes VQ is used interchangeably with clustering. 

So, after this step, we will have $k$ clusters, each of them associated with a centroid $C = \{ c_1, \dots, c_k\}$, where $C$ is the set of centroids (and $c_i \in \mathbb{R}^{128}$ in the case that SIFT descriptors have been used). These centroids represent the main features that are present in the whole training dataset $D$. In this context, they are often known as the **codewords** (which derives from the vector quantization literature) or **visual words** (hence the name _bag-of-visual-words_). The set of codewords $C$ is often called **codebook** or, equivalently, the **visual vocabulary**.

### 3. Feature vector generation

In this last step, given a new (test) image $u \not\in D$ (often called the _query image_ in this context of CBIR), then we will represent $u$ as a $k$-dimensional vector (where $k$, if you remember, is the number of codewords) that will represent its _feature vector_. To do that, we need to follow the following steps.

  1. Extract the raw features from $u$ with e.g. SIFT (as we did for the training images). Let the descriptors of $u$ be $U = \{ u_1, \dots, u_{|U|} \}$.

  2. Create a vector $I \in \mathbb{R}^k$ of size $k$ filled with zeros, where the $i$th element of $I$ corresponds to the $i$th codeword (or cluster).

  3. For each $u_i \in U$, find the _closest_ codeword (or centroid) in $C$. Once you found it, increment the value at the $j$th position of $I$ (i.e., initially, from zero to one), where $j$ is the found closest codeword to the descriptor $u_i$ of the query image.

     The distance between $u_i$ and any of the codewords can be computed e.g. with the Euclidean distance. Note that the descriptors of $u$ and the codewords have the same dimension because they have been computed with the same feature descriptor (e.g. SIFT).


   At the end of this process, we will have a vector $I \in \mathbb{R}^k$ that represents the frequency of the codewords in the query image $u$ (akin to the _term frequency_ in the context of the bag-of-words model), i.e. $u$'s feature vector. Equivalently, $I$ can also be viewed as a histogram of features of the query image $u$. Here's an illustrative example of such a histogram.

  [![enter image description here][4]][4]

  From this diagram, we can see that there are $11$ codewords (of course, this is an unrealistic scenario!). On the y-axis, we have the frequency of each of the codewords in a given image. We can see that the $7$th codeword is the most frequent in this particular query image.

  Alternatively, rather than the codeword frequency, we can use the [tf-idf][5]. In that case, each image will be represented not by a vector that contains the frequency of the codewords but it will contain the frequency of the codewords weighted by their presence in other images. See [this paper][1] for more details (where they show how to calculate tf-idf in this context; specifically, section 4.1, p. 8 of the paper).

## Conclusion

To conclude, BoF is a method to represent features of an image, which could then be used to train classifiers or generative models to solve different computer vision tasks ([such as CBIR][7]). The first two steps above are concerned with the creation of a **visual vocabulary** (or codebook), which is then used to create the feature vector of a new test (or query) image.

## A side note

As a side note, the term _bag_ is used because the (relative) order of the features in the image is lost during this feature extraction process, and this can actually be a disadvantage.

## Further reading

For more info, I suggest that you read the following papers 


1. [Video Google: A Text Retrieval Approach to Object Matching in Videos][6] (2003) by Sivic and Zisserman
2. [A Bayesian Hierarchical Model for Learning Natural Scene Categories][7] (2005) by Fei-Fei and Perona
3. [Introduction to the Bag of Features Paradigm for Image Classification and Retrieval][1] (2011) by O'Hara and Draper
4. [Bag-of-Words Representation in Image Annotation: A Review][8] (2012) by Tsai

  [1]: https://www.researchgate.net/publication/48190777_Introduction_to_the_Bag_of_Features_Paradigm_for_Image_Classificationand_Retrieval
  [2]: https://en.wikipedia.org/wiki/Content-based_image_retrieval
  [3]: https://www.cs.ubc.ca/~lowe/papers/ijcv04.pdf
  [4]: https://i.sstatic.net/Rx3XK.png
  [5]: https://en.wikipedia.org/wiki/Tf%E2%80%93idf
  [6]: http://www.robots.ox.ac.uk/~vgg/publications/papers/sivic03.pdf
  [7]: http://vision.stanford.edu/documents/Fei-FeiPerona2005.pdf
  [8]: https://www.researchgate.net/publication/258403856_Bag-of-Words_Representation_in_Image_Annotation_A_Review