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?
