How to achieve full number of words in a Bag-of-Features model based on Hierarchical K-Means?

Question

I'm implementing a baseline system that uses a Vocabulary Tree, i.e. a BoF model based on HKM, for images classification. Currently I'm obtaining low quality recognition due to the poor quality of the quantization structure resulting from the HKM.

I'm obtaining 100.000 words in my final vocabulary in a tree of depth 6 and branch factor 10 where the theoretical number of words is 10^6 = 1'000.000

In several papers, like those of Zisserman related to Large Scale Landmark recognition, they claim to be using a 1'000.000 words vocabulary, something I found difficult to understand since this number is theoretical while in practice there is no guarantee to obtain it.

Am I understanding something wrong? If not, what should I do to increase the vocabulary size despite of using more descriptors to train the tree?

PS: my only hint so far is using a different seeding algorithm for clusters initialization like k-means++ or gonzales

Thanks, any suggestion is welcome.

---

After reading @penelope's answer I came back to report my findings. The configuration of my implementation for building the vocabulary tree is: depth 6, branch factor 10, maximum 10 iterations, and random seeding.

Addressing some of the spots:

• Severely underpopulated clusters at early levels: I checked clusters at first level and they were kind of uniformly distributed, e.g. the first cluster was typically 10% of the whole set.

• K-means termination criteria: I'm running the clustering process until convergence or until reaching 10 iterations. I took this parameter from the experiments of Neister 2006 where the performance will not improve farther than ~12 iterations while doing so could affect the overall algorithm duration.

• Uniform coverage of feature space: I am seeding centers using random selection, as I said in the question using other algorithm like k-means++ or gonzalez would become in a more uniform coverage of the feature space.

• Number of training features should be considerably bigger than the expected number of clusters: with "expected number of cluster" I understand "expected number of words", being it so, this is very likely the root cause of my problem. I'm training a 1 million words vocabulary using 3 million descriptors while the experiments of Zisserman use ~17 million descriptors from the Oxford Buildings dataset and those of Marc Pollefeys team use ~16 million from the San Francisco Landmark dataset.

• Pairing several detectors and descriptors: I have the restriction of comparing my approach which uses binary features against a baseline using DoG/MSER and SIFT descriptors. In the near future I plan to evaluate performance as well using other detectors like AGAST which produce more keypoints of similar quality to those produced by DoG.

• HKM termination conditions: in @penelope's answer it was mentioned that obtaining a vocabulary tree of expected size was not a problem. I was wondering if such a thing was truly possible and started to think about HKM termination conditions. In my implementation they are:

  • Reaching last level.
  • Having less data than clusters.
  • Obtaining, at clustering initialization time, centers which are too close one another so there is a big chance they represent the same word, hence not very distinctive.

  The first two conditions are enough and necessary but the third one isn't, I included it because the vocabulary might result more distinctive, at least in theory. I borrowed it from the hierarchical k-means index implementation in OpenCV. Could it be convenient removing it?

Answer 1

Unfortunately, I think what causes the problems is most probably the training set of images you're using to construct the tree. (or, more in general, the database you're working on). Without a way to inspect the concrete images, I can only give a few vague guesses.

First, I would diagnose where it goes wrong, by simply inspecting the tree and looking at the first branches which become severely underpopulated and consequently don't branch any more in the lower levels. I would look at those features and... think. But, since I can't actually do that since I don't have your dataset, let me try further.

If you're afraid that it's the K-means that is going wrong, not because the features aren't (more-or-less) uniformly distributed over the feature space, but simply because of the way that algorithm works, before implementing a fancier algorithm, you might first try running K-means several times for each branching and picking the best result (e.g. the one that divides the feature space in most equal parts). This will probably be too slow for the final implementation, but it could be a fast, minimum-effort way do diagnose the problem.

I would say, in order for HKM to work, your initial number of features should be several orders of magnitude greater than the expected number of clusters. So, if that's not the case, you know you're doing something wrong. I don't know how many is enough, but I would say minimum $100$ times, but better at least $1000$ times more features than expected clusters. This might be caused by two (related) issues:

• Maybe your training set is just too small, or maybe it is a bad representation of the database, containing images that are too similar? Try increasing the size of the training set, and maybe (just for testing purposes), cherry pick the training set by selecting very different, representative images.

• Maybe your feature detector performs badly on the image set you're using. For some images, some detectors just do not detect enough features. Problematic images usually contain large single-colored areas (e.g. white wall, blue sky). Try combining several feature detectors. (e.g. in my thesis I was working with DoG and MSER features). You can always do that, since you can finally describe all the features from several detectors with the same descriptor.

---

Unfortunately, there's no more ideas I can think of based on so little information. You might simply have an implementation error sometimes. I know it's not easy to here, and it's not a most helpful diagnosis, but as somebody who actually implemented such a CBIR system, I have to tell you, I never had any problem in constructing a vocabulary tree of expected size.

If you give any more info, or updates, or whatever, I can try and think of other ways this might have gone wrong. Until then, I hope this helps.

Answer 2

After a long time checking my code, I found the root cause of my problem, a misunderstanding of tree depth. I was counting the root of the node as a level hence when setting depth as 6 I was expecting to obtain 1M words but I could have just obtained at most 100K.

So far in the best run using the full dataset I obtained 997.228 words, a more reasonable number than before considering there is no guarantee on obtaining full vocabulary size.

As a side comment I tried removing the too close descriptors termination condtion but the performance decreased, indicating it might lead to a more discriminative vocabulary.