PQ kernel: A rank correlation kernel for visual word histograms

• We describe an efficient algorithm to compute the PQ kernel in the dual form.
• We provide open source implementations of the PQ kernel in Matlab and C/C++.
• We leverage the use of the PQ kernel for large vocabularies.
• We present extensive object recognition experiments using various kernels.

Computer vision researchers have developed various learning methods based on the bag of words model for image related tasks, including image categorization and image retrieval. In this model, images are represented as histograms of visual words from a vocabulary that is obtained by clustering local image descriptors. Next, a classifier is trained on the data. Most often, the learning method is a kernel-based one. Various kernels, such as the linear kernel, the intersection kernel, the χ2 kernel or the Jensen-Shannon kernel, can be plugged into the kernel method. Recent results indicate that the novel PQ kernel of Ionescu and Popescu [8] seems to improve the accuracy over most of the state of the art kernels. The PQ kernel is inspired from a set of rank correlation statistics specific for ordinal data, that are based on counting concordant and discordant pairs among two variables. This paper describes an algorithm to compute the PQ kernel in O(nAPTARANORMALlogn)O(nAPTARANORMALlogn) time, based on merge sort. Matlab and C/C++ implementations are provided for future development and use at http://pq-kernel.herokuapp.com. Extensive object recognition experiments are conducted to compare the PQ kernel with other state of the art kernels on two benchmark data sets. The PQ kernel has the best results on both data sets, even when a spatial pyramid representation is used. In conclusion, the PQ kernel can be used to obtain a better pairwise similarity between visual word histograms, which, in turn, improves the object recognition accuracy of the bag of visual words system.