3
$\begingroup$

I was reading these slides about Bag of Features (BoF), in particular at slide 23:

A visual vocabulary of 1M words is generated using an approximate K-means clustering method based on randomized trees.

By "words" they means the centroids obtained by k-means? Otherwise what they mean?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I think so. When you cluster in the centroids, you are creating your dictionary. Each one of the entries of the dictionary, are each one of the words. A word is nothing more than a feature vector, really. $\endgroup$
    – Marcel
    Commented Jul 22, 2016 at 11:26
  • $\begingroup$ But this looks weird...I mean, the histograms are going to be of 1M dimensions! This is INSANE! Right? :D $\endgroup$
    – user6321
    Commented Jul 22, 2016 at 12:36
  • $\begingroup$ The histograms are one dimensionals because it is just a feature count. Imagine in a visual image, that you have a visual feature which is an eye. Eye is your visual word. Then, in your dictionary, you are going to have more than one, perhaps mouth,nose, whatever... all the words. The eye can have more than one feature (e.g. colours), however, in the histogram, you count how many eyes you have detected. In short, a histogram is a count, and the x axis is just the index of the visual word. $\endgroup$
    – Marcel
    Commented Jul 22, 2016 at 13:27
  • $\begingroup$ I'm sorry, i think that I'm not explaining myself. What I mean is that EVERY Image is going to be represnted as a 1 million dimensions vector! There is NO way that you can use such a vector, it's definitely too big! Do you know what I mean? $\endgroup$
    – user6321
    Commented Jul 22, 2016 at 15:07

2 Answers 2

Reset to default
1
$\begingroup$

The "centroid" really refers to the coordinates.

The concept of "word" means it's simply a symbol, not something meaningful like coordinates.

Every SIFT vector is mapped to a word (e.g. "42"); the image is represented as a bag of such words ("42 13 17 42 17"), not as a string of centroid coordinates.

The "dictionary" translates coordinates to words.

Yes, there may be a million words (although most appear to only use a few thousand?). But most will be 0, and you don't need to store these zero values. Just as with text.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Ok, but according to the quoted text this means that our vector is composed by MILLIONS of dimensions! This absolutely insane, no way that we can manage in any way such big vectors! And can you imagine running k-means for finding 1 million centroids? Something is wrong here I guess :D $\endgroup$
    – user6321
    Commented Jul 23, 2016 at 5:03
  • 1
    $\begingroup$ How many different words are there on the internet? Text usually has millions of dimensions, but most of them are 0 and don't need to be managed. Use sparse vectors. $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented Jul 23, 2016 at 6:49
  • $\begingroup$ I guess you're right for texts, but here we're talking about images. If this would be the case, then I think that PCA would a mandatory step in every application that involves BoF/BoW, because we cannot deal with such big vectors. But this doesn't happens (there are several implemented applications which doesn't use PCA at all). $\endgroup$
    – user6321
    Commented Jul 23, 2016 at 7:19
  • $\begingroup$ I mean, vectors of millions of dimension are too big even for LSH! The curse of dimensionality happens where we have vectors with some hundreds of dimensions. Millions of dimensions is unrealistic :D $\endgroup$
    – user6321
    Commented Jul 23, 2016 at 7:19
  • $\begingroup$ No, PCA would be an infeasible route. But you are seeing a problem that doesn't exist. The point of this approach is to use text techniques; and usually images do produce sparse vectors, too. $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented Jul 23, 2016 at 7:23
0
$\begingroup$

Once you created the vocabulary, you have a list of all possible words in the training set(dictionary). Let's do an easy example. The training set contains an 'eye', a 'mouth' and a 'nose'. When a new test image comes, then you are going to extract features and you are going to try to detect these three features. Then, what you do is you create a histogram, having as index these three. 1.eye 2. mouth. 3.nose. For every feature that is similar to an eye, you are going to add a +1. Say that now you test with an image where there are 100 eyes. Then your histogram for that image is going to be [100 0 0] (no mouth and no nose.) Therefore, in this case, this image is represented with 3 components.

100 | 0 | 0

e | m | n

I hope it is clearer now. An image, will kind of have a 'signature' which will be a kind of summary of your features. In this case, the histogram would define perfectly the image as 100 eyes! And it is precisely what the image would be, right?

Let me know if something is not clear!

Improve this answer
$\endgroup$
3
  • $\begingroup$ thanks for your explenation. I was not sure about the meaning of "word" in such a context. But my observation still remain: according to text we have MILLIONS of words. This means that each image is represented through an histogram (vector) of MILLIONS of dimension. Can you imagine managing such a vector? It's simply IMPOSSIBLE! :D $\endgroup$
    – user6321
    Commented Jul 23, 2016 at 5:10
  • $\begingroup$ Oh sure. You have a histogram which has as many dimensions as words in your dictionary. But note that most of them are going to be empty, so you can store only the ones that are not :) $\endgroup$
    – Marcel
    Commented Jul 23, 2016 at 23:06
  • $\begingroup$ I just saw that the sparsity thing has been comented below. $\endgroup$
    – Marcel
    Commented Jul 23, 2016 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.