Partitioned k-means clustering for fast construction of unbiased visual vocabulary

Bag-of-Words (BoW) model has been widely used for feature representation in multimedia search area, in which a key step is to vector-quantize local image descriptors and generate a visual vocabulary. Popular visual vocabulary construction schemes generally perform a flat or hierarchical clustering operation using a very large training set in their original description space. However, these methods usually suffer from two issues: (1) A large training set is required to construct a large visual vocabulary, making the construction computationally inefficient; (2) The generated visual vocabularies are heavily biased towards the training samples. In this work, we introduce a partitioned k-means clustering (PKM) scheme to efficiently generate a large and unbiased vocabulary using only a small training set. Instead of directly clustering training descriptors in their original space, we first split the original space into a set of subspaces and then perform a separate k-means clustering process in each subspace. Sequentially, we can build a complete visual vocabulary by combining different cluster centroids from multiple subspaces. Comprehensive experiments demonstrate that the proposed method indeed generates unbiased vocabularies and provides good scalability for building large vocabularies.