title: How Bag of Features works?
body: <p>I'm not sure that this is the right forum for this question, I'm sorry otherwise.</p>
  
  <p>I'm quite new to the <a href="https://en.wikipedia.org/wiki/Bag-of-words_model_in_computer_vision" rel="nofollow">Bag of Features</a> model and I'm trying to implement in order to represent an image through a vector (for a CBIR project).</p>
  
  <p>From what I've understood, given a training set <code>S</code> of <code>n</code> images and supposing that we want to represent an image through a vector of size <code>k</code>, these are the steps for implementing BoF:</p>
  
  <ol>
  <li>For each image <code>i</code>, compute the set of keypoints and from that compute the set of descriptor <code>i-D</code>.</li>
  <li>Put all together the set of descriptor from all the images, so now we have <code>D</code>. </li>
  <li>Run the <code>k</code> means (where <code>k</code> is defined above) algorithm on <code>D</code>, so now we have <code>k</code> clusters and each descriptor vector belongs exactly to one cluster.</li>
  <li>Define <code>iv</code> as the resulting BoF vector (of size <code>k</code>) relative to image <code>i</code>. Each dimension is initialized to 0.  </li>
  <li>For each image <code>i</code>, and for each descriptor <code>d</code> belonging to <code>i-D</code>, find out which cluster <code>d</code> belongs between all the <code>k</code> clusters. Supposing that <code>d</code> belongs to the <code>j</code>-th cluster, then <code>vi[j]++</code>.</li>
  </ol>
  
  <p>What is not clear to me is how to implement point 5., so how do we understand to which cluster a descriptor belongs to, <strong>in particular if the image that we are trying to compute the BoF vector is a query image (and so didn't belong to the initial dataset)</strong>? Should we find the nearest neighbor (1-NN) in order to understand to which cluster the query descriptor belongs to?</p>
  
  <p><strong>WHY I NEED THIS - THE APPLICATION:</strong></p>
  
  <p>I'm implementing the BoF model in order to implement a CBIR: given a query image <code>q</code>, find the most similar image <code>i</code> of <code>q</code> in a dataset of images. In order to do this, we need to solve the 1-approximate nearest neighbor problem, for example using <a href="https://en.wikipedia.org/wiki/Locality-sensitive_hashing" rel="nofollow">LSH</a>. The problem is that the input in LSH each image is represented as a vector, so we need the BoF in order to do that! I hope that now it's clearer why I need it :)</p>
  
  <p>Please, let me know also if I did some mistake in the procedure described above.</p>