What is a vocabulary tree and how to build one?

Question

I'm reading a lot about vocabulary trees when it comes to fast queries for similar images or texts in big databases. But I couldn't find any good (easy to understand) description on what such a vocabulary tree is and how to build one of features.

Answer 1

Vocabulary tree is a compact way to do image retrieval. There are basically three steps to implement this algorithm, and it highly depends on other computer vision techniques e.g. SIFT features.

The first step is to build a kmeans tree using sift descriptors. The leaf nodes of this tree contain a "bag" of sift descriptors. The second step is to build a image database using the vocabulary tree you build in the first step. You can view this process as quantizing an image into a vector space. Then the third step is to query the image against the image database. Of course there are some detailed techniques such as inverted list, etc.

Here is a good implementation of vocabulary tree - libvot. It basically follow the three steps I described above. It use the C++11 standard multi-thread library to accelerate the build process so it runs pretty fast.

Here is the original research paper about it. It has high impact on computer vision community these years.