Fast and efficient visual codebook construction for multi-label annotation using predictive clustering trees

• Predictive clustering trees (PCTs) for multi label classification.
• Constructing visual codebook by using predictive clustering trees.
• Small ensemble of PCTs to increase the performance of the codebook.

The bag-of-visual-words approach to represent images is very popular in the image annotation community. A crucial part of this approach is the construction of visual codebook. The visual codebook is typically constructed by using a clustering algorithm (most often k-means) to cluster hundreds of thousands of local descriptors/key-points into several thousands of visual words. Given the large numbers of examples and clusters, the clustering algorithm is a bottleneck in the construction of bag-of-visual-words representations of images. To alleviate this bottleneck, we propose to construct the visual codebook by using predictive clustering trees (PCTs) for multi-label classification (MLC). Such a PCT is able to assign multiple labels to a given image, i.e., to completely annotate a given image. Given that PCTs (and decision trees in general) are unstable predictive models, we propose to use a random forest of PCTs for MLC to produce the overall visual codebook. Our hypothesis is that the PCTs for MLC can exploit the connections between the labels and thus produce a visual codebook with better discriminative power. We evaluate our approach on three relevant image databases. We compare the efficiency and the discriminative power of the proposed approach to the literature standard – k-means clustering. The results reveal that our approach is much more efficient in terms of computational time and produces a visual codebook with better discriminative power as compared to k-means clustering. The scalability of the proposed approach allows us to construct visual codebooks using more than usually local descriptors thus further increasing its discriminative power.