Answers.Body: <h2>Introduction</h2>
  
  <p><a href="https://www.researchgate.net/publication/48190777_Introduction_to_the_Bag_of_Features_Paradigm_for_Image_Classificationand_Retrieval" rel="nofollow noreferrer"><strong>Bag-of-features</strong></a> (BoF) (also known as <strong>bag-of-visual-words</strong>) 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 <a href="https://en.wikipedia.org/wiki/Content-based_image_retrieval" rel="nofollow noreferrer">content-based image retrieval (CBIR)</a>, i.e. find an image in a database that is closest to a query image.</p>
  
  <h2>Steps</h2>
  
  <p>The BoF can be divided into three different steps. To understand all the steps, consider a training dataset <span class="math-container">$D = \{x_1, \dots, x_N \}$</span> of <span class="math-container">$N$</span> training images. Then BoF proceeds as follows.</p>
  
  <h3>1. Feature extraction</h3>
  
  <p>In this first step, we extract all the <em>raw</em> features (i.e. keypoints and descriptors) from all images in the training dataset <span class="math-container">$D$</span>. This can be done with <a href="https://www.cs.ubc.ca/~lowe/papers/ijcv04.pdf" rel="nofollow noreferrer">SIFT</a>, where each descriptor is a <span class="math-container">$128$</span>-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). </p>
  
  <p>If you are not familiar with this extraction of <em>computer vision</em> (sometimes known as <em>handcrafted</em>) features, you should read the <a href="https://www.cs.ubc.ca/~lowe/papers/ijcv04.pdf" rel="nofollow noreferrer">SIFT paper</a>, which describes a feature (more precisely, keypoint and descriptor) extraction algorithm.</p>
  
  <p>Note that image <span class="math-container">$x_i \in D$</span> may contain a different number of features (keypoints and descriptors) than image <span class="math-container">$x_j \neq x_i \in D$</span>. As we will see in the third step, BoF produces a feature vector of size <span class="math-container">$k$</span> for all images, so all images will be represented by a fixed-size vector. </p>
  
  <p>Let <span class="math-container">$F= \{f_1, \dots, f_M\}$</span> be the set of descriptors extracted from all training images in <span class="math-container">$D$</span>, where <span class="math-container">$M \gg N$</span>. So, <span class="math-container">$f_i$</span> may be a descriptor that belongs to any of the training examples (it does not matter which training image it belongs to).</p>
  
  <h3>2. Codebook generation</h3>
  
  <p>In this step, we cluster all descriptors <span class="math-container">$F= \{f_1, \dots, f_M\}$</span> into <span class="math-container">$k$</span> clusters using k-means (or another clustering algorithm). This is sometimes known as the <em>vector quantization</em> (VQ) step. In fact,  the idea behind VQ is very similar to clustering and sometimes VQ is used interchangeably with clustering. </p>
  
  <p>So, after this step, we will have <span class="math-container">$k$</span> clusters, each of them associated with a centroid <span class="math-container">$C = \{ c_1, \dots, c_k\}$</span>, where <span class="math-container">$C$</span> is the set of centroids (and <span class="math-container">$c_i \in \mathbb{R}^{128}$</span> in the case that SIFT descriptors have been used). These centroids represent the main features that are present in the whole training dataset <span class="math-container">$D$</span>. In this context, they are often known as the <strong>codewords</strong> (which derives from the vector quantization literature) or <strong>visual words</strong> (hence the name <em>bag-of-visual-words</em>). The set of codewords <span class="math-container">$C$</span> is often called <strong>codebook</strong> or, equivalently, the <strong>visual vocabulary</strong>.</p>
  
  <h3>3. Feature vector generation</h3>
  
  <p>In this last step, given a new (test) image <span class="math-container">$u \not\in D$</span> (often called the <em>query image</em> in this context of CBIR), then we will represent <span class="math-container">$u$</span> as a <span class="math-container">$k$</span>-dimensional vector (where <span class="math-container">$k$</span>, if you remember, is the number of codewords) that will represent its <em>feature vector</em>. To do that, we need to follow the following steps.</p>
  
  <ol>
  <li><p>Extract the raw features from <span class="math-container">$u$</span> with e.g. SIFT (as we did for the training images). Let the descriptors of <span class="math-container">$u$</span> be <span class="math-container">$U = \{ u_1, \dots, u_{|U|} \}$</span>.</p></li>
  <li><p>Create a vector <span class="math-container">$I \in \mathbb{R}^k$</span> of size <span class="math-container">$k$</span> filled with zeros, where the <span class="math-container">$i$</span>th element of <span class="math-container">$I$</span> corresponds to the <span class="math-container">$i$</span>th codeword (or cluster).</p></li>
  <li><p>For each <span class="math-container">$u_i \in U$</span>, find the <em>closest</em> codeword (or centroid) in <span class="math-container">$C$</span>. Once you found it, increment the value at the <span class="math-container">$j$</span>th position of <span class="math-container">$I$</span> (i.e., initially, from zero to one), where <span class="math-container">$j$</span> is the found closest codeword to the descriptor <span class="math-container">$u_i$</span> of the query image.</p>
  
  <p>The distance between <span class="math-container">$u_i$</span> and any of the codewords can be computed e.g. with the Euclidean distance. Note that the descriptors of <span class="math-container">$u$</span> and the codewords have the same dimension because they have been computed with the same feature descriptor (e.g. SIFT).</p>
  
  <p>At the end of this process, we will have a vector <span class="math-container">$I \in \mathbb{R}^k$</span> that represents the frequency of the codewords in the query image <span class="math-container">$u$</span> (akin to the <em>term frequency</em> in the context of the bag-of-words model), i.e. <span class="math-container">$u$</span>'s feature vector. Equivalently, <span class="math-container">$I$</span> can also be viewed as a histogram of features of the query image <span class="math-container">$u$</span>. Here's an illustrative example of such a histogram.</p>
  
  <p><a href="https://i.sstatic.net/Rx3XK.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Rx3XK.png" alt="enter image description here"></a></p>
  
  <p>From this diagram, we can see that there are <span class="math-container">$11$</span> 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 <span class="math-container">$7$</span>th codeword is the most frequent in this particular query image.</p>
  
  <p>Alternatively, rather than the codeword frequency, we can use the <a href="https://en.wikipedia.org/wiki/Tf%E2%80%93idf" rel="nofollow noreferrer">tf-idf</a>. 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 <a href="https://www.researchgate.net/publication/48190777_Introduction_to_the_Bag_of_Features_Paradigm_for_Image_Classificationand_Retrieval" rel="nofollow noreferrer">this paper</a> for more details (where they show how to calculate tf-idf in this context; specifically, section 4.1, p. 8 of the paper).</p></li>
  </ol>
  
  <h2>Conclusion</h2>
  
  <p>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 (<a href="http://vision.stanford.edu/documents/Fei-FeiPerona2005.pdf" rel="nofollow noreferrer">such as CBIR</a>). More precisely, if you want to perform CBIR, you could compare your query's feature vector with the feature vector of every image in the database, e.g. using the cosine similarity.</p>
  
  <p>The first two steps above are concerned with the creation of a <strong>visual vocabulary</strong> (or codebook), which is then used to create the feature vector of a new test (or query) image.</p>
  
  <h2>A side note</h2>
  
  <p>As a side note, the term <em>bag</em> 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.</p>
  
  <h2>Further reading</h2>
  
  <p>For more info, I suggest that you read the following papers </p>
  
  <ol>
  <li><a href="http://www.robots.ox.ac.uk/~vgg/publications/papers/sivic03.pdf" rel="nofollow noreferrer">Video Google: A Text Retrieval Approach to Object Matching in Videos</a> (2003) by Sivic and Zisserman</li>
  <li><a href="http://vision.stanford.edu/documents/Fei-FeiPerona2005.pdf" rel="nofollow noreferrer">A Bayesian Hierarchical Model for Learning Natural Scene Categories</a> (2005) by Fei-Fei and Perona</li>
  <li><a href="https://www.researchgate.net/publication/48190777_Introduction_to_the_Bag_of_Features_Paradigm_for_Image_Classificationand_Retrieval" rel="nofollow noreferrer">Introduction to the Bag of Features Paradigm for Image Classification and Retrieval</a> (2011) by O'Hara and Draper</li>
  <li><a href="https://www.researchgate.net/publication/258403856_Bag-of-Words_Representation_in_Image_Annotation_A_Review" rel="nofollow noreferrer">Bag-of-Words Representation in Image Annotation: A Review</a> (2012) by Tsai</li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-05-01T03:15:13.683Z
Answers.Text: Can I infer then for matching images you compare the histogram vectors of different images with examplars?
Answers.UserDisplayName: IntegrateThis
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-15T19:24:57.230Z
Answers.LastActivityDate: 2020-06-16T16:55:19.063Z
Answers.LastEditDate: 2020-06-16T16:55:19.063Z
Answers.UserDisplayName: nbro
Body: <p>In computer vision, what are bag-of-features (also known as bag-of-visual-words)? How do they work? What can they be used for? How are they related to the bag-of-words model in NLP?</p>
  
Tags: <computer-vision><feature-extraction><features><bag-of-features><content-based-image-retrieval>
Title: What are bag-of-features in computer vision?
UserDisplayName: nbro
ThreadText: # What are bag-of-features in computer vision?
  
  (Asked by: username_0 on 2020-06-15)
  
  In computer vision, what are bag-of-features (also known as bag-of-visual-words)? How do they work? What can they be used for? How are they related to the bag-of-words model in NLP?
  
  **Tags:** computer-vision, feature-extraction, features, bag-of-features, content-based-image-retrieval
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2020-06-15. Score: 5 | Accepted answer
  
  ## Introduction
  
  [**Bag-of-features**](https://www.researchgate.net/publication/48190777_Introduction_to_the_Bag_of_Features_Paradigm_for_Image_Classificationand_Retrieval) (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)](https://en.wikipedia.org/wiki/Content-based_image_retrieval), 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](https://www.cs.ubc.ca/~lowe/papers/ijcv04.pdf), 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](https://www.cs.ubc.ca/~lowe/papers/ijcv04.pdf), 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](https://i.sstatic.net/Rx3XK.png)](https://i.sstatic.net/Rx3XK.png)
  
     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](https://en.wikipedia.org/wiki/Tf%E2%80%93idf). 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](https://www.researchgate.net/publication/48190777_Introduction_to_the_Bag_of_Features_Paradigm_for_Image_Classificationand_Retrieval) 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](http://vision.stanford.edu/documents/Fei-FeiPerona2005.pdf)). More precisely, if you want to perform CBIR, you could compare your query's feature vector with the feature vector of every image in the database, e.g. using the cosine similarity.
  
  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](http://www.robots.ox.ac.uk/~vgg/publications/papers/sivic03.pdf) (2003) by Sivic and Zisserman
  2. [A Bayesian Hierarchical Model for Learning Natural Scene Categories](http://vision.stanford.edu/documents/Fei-FeiPerona2005.pdf) (2005) by Fei-Fei and Perona
  3. [Introduction to the Bag of Features Paradigm for Image Classification and Retrieval](https://www.researchgate.net/publication/48190777_Introduction_to_the_Bag_of_Features_Paradigm_for_Image_Classificationand_Retrieval) (2011) by O'Hara and Draper
  4. [Bag-of-Words Representation in Image Annotation: A Review](https://www.researchgate.net/publication/258403856_Bag-of-Words_Representation_in_Image_Annotation_A_Review) (2012) by Tsai
  
  > **Comments:**
  > **username_1**: Can I infer then for matching images you compare the histogram vectors of different images with examplars?  
  
  ---
  
  