8
$\begingroup$

I hope this is on topic, I found this through the proposal here: https://area51.meta.stackexchange.com/questions/320/shall-we-unite-computational-science-proposals

A good visual description of BOW: enter image description here

I don't quite understand the point of some of the steps here however. I know feature extraction gets some form of unique features from an image. But that's it.

Encoding seems like some form of kd-tree manipulation, but it seems like the most common method is histogram encoding. Just with the encoding stage I can get to object recognition, because with encoding I can directly search match feature columns.

But the standard model goes on, and here is where I get completely lost.

I have no idea what pooling is. But the pooling step I'm interested in is max or sum pooling using pyramid match kernel. What is the point of pooling?

Finally, with classification, some form of SVM is used to compare the input image classifier with the rest of the classifiers. I sort of understand this process, but it doesn't seem necessary unless I need to find what class an object belongs to, rather than recognizing an object itself.

So ignoring the classification part, how does encoding and pooling work? Why do I need to pool at all if I could achieve object recognition just by extracting features and comparing it with a database of feature converted to a kd-tree?

Improve this question
$\endgroup$
8
$\begingroup$

There are several ways to implmenet a BoW (Bag of Words) model, but generally speaking:

  • Encoding is the quantization of the image patches that constitute the image or object to be classified. Basic encoding schemes work by first running K-means on the set of all (e.g. 3x3) pixel patches that you collect across multiple instances of your images/objects during a training/pre-processing step. This builds what is known a dictionary represented by the centroids obtained from the clustering.

    At the end of this process, you end up with K representative "visual words" (the centroid of each cluster after K means ends) of 3x3 patches. These "visual words" represent what is usually understood as your visual dictionary. Once you have these visual words, encoding is the process of assigning each 3x3 patch within your image/object the closest 3x3 word (nearest neighbor) in the dictionary.

  • Pooling refers to the process of representing an image (or the object to be classified) as a "bag of words". The word bag here is meant to convey that once you have encoded each patch with a word (a number between 1 and K), you build a new representation (a bag) that discards the spatial relationship between the words that constitute your image or object.

    This representation is often a histogram or a collection of spatially adjacent histograms of the 3x3 words (i.e. histograms of values 1 to K) that together form your object or image. "Pooling" is thus the process of building a histogram of words (i.e. pooling ~ "sampling" words from the image to build a probability mass function of words)

    To clarify, the purpose of pooling is two fold:

    1. By building a feature vector that is a histogram of words (as opposed to putting the full "sentence of words" in the feature vector), your descriptor will be invariant to changes in "the ordering of words". In computer vision this translates into invariance with respect to rotations and distortions of the image and object, which is a desirable thing to have.

    2. If the dictionary is small compared to the length of the sentence, a histogram of words has less dimensions than the original vector. Less dimensions makes learning (training) much easier.

    Classification refers to the process of classifying your image/object now represented by a "bag of words". Following the example above, the feature vector here would be the histogram (or histograms) of words (3x3 patches) for your object or image.

The above implies that your working word is an image patch (in the example I used, a 3x3 pixel patch). But nothing prevents you from defining words that correspond to other visual cues or descriptors such as SIFT feature vectors (which is the case in the diagram you posted).

Improve this answer
$\endgroup$
  • $\begingroup$ it seems like I've been doing things wrong then. I have just been extracting SIFT features, and saving the entirety of it in the database. When doing obj recognition, I make a tree out of my entire database and match with the extracted features. $\endgroup$ – mugetsu Dec 15 '11 at 18:23
  • $\begingroup$ FYI @mugetsu, I have updated and expanded the post. To clarify, when encoding the image in a set of tiles of quantized vectors, you don't have to use use 3x3 pixel patches. You can associate each tile with any other descriptor, such as quantized SIFT features. $\endgroup$ – Amelio Vazquez-Reina Dec 15 '11 at 19:34
  • $\begingroup$ Thanks for the clarification, it's really difficult for me to find any materials online that defines all this. Research papers all assume that I know the basics. Let me just summarize this a bit, please tell me if this is right: Encoding, convert image into "words" that spell a sentence. Pooling breaks up this sentence and stores it in an array of sorts. Classification matches this array with other existing arrays. $\endgroup$ – mugetsu Dec 16 '11 at 1:19
  • $\begingroup$ @mugetsu, your summary is correct. I have also expanded my explanation of pooling to describe its benefits in more detail. $\endgroup$ – Amelio Vazquez-Reina Dec 16 '11 at 1:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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