## 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 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 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 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), 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). Equivalently, $I$ can also be viewed as a histogram of features of the query image $u$, i.e. the feature vector of $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!), and, on the y-axis, we have the frequency of each of the codewords in a given 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