Revision c0609d69-e3c2-4496-a7ef-382621769fc1 - Artificial Intelligence Stack Exchange

### Introduction

[**Bag-of-features**][1] (BoF) (also known as **bag-of-visual-words**) is a method to represent the features of images. 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 phases (or steps). To understand all the phases, consider a training dataset $D = \{x_1, \dots, x_N \}$ of $N$ training images. Then BoF proceeds as follows.

1. 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 neighbourhood 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 next 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 to which training image it belongs, in this phase).

2. 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 phase, 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. Now, for simplicity, let's assume that we want to perform CBIR. Given a new image $u \not\in D$ (often called the _query image_, in this context), then, first, we will represent $u$ as a $k$-dimensional vector (where $k$, if you remember, is the number of codewords). 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 $1$), where $j$ is the 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$ represents 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).

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.

As a side note, the term _bag_ is used because the (relative) order information of the features in the image is lost during this 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