Creating efficient codebooks for visual recognition

Visual codebook based quantization of robust appearance descriptors extracted from local image patches is an effective means of capturing image statistics for texture analysis and scene classification. Codebooks are usually constructed by using a method such as k-means to cluster the descriptor vectors of patches sampled either densely ('textons') or sparsely ('bags of features' based on key-points or salience measures) from a set of training images. This works well for texture analysis in homogeneous images, but the images that arise in natural object recognition tasks have far less uniform statistics. We show that for dense sampling, k-means over-adapts to this, clustering centres almost exclusively around the densest few regions in descriptor space and thus failing to code other informative regions. This gives suboptimal codes that are no better than using randomly selected centres. We describe a scalable acceptance-radius based clusterer that generates better codebooks and study its performance on several image classification tasks. We also show that dense representations outperform equivalent keypoint based ones on these tasks and that SVM or mutual information based feature selection starting from a dense codebook further improves the performance.

1. Introduction

Representations based on loose collections of invariant appearance descriptors extracted from local image patches have become very popular for texture analysis and visual recognition [1], [5], [7], [9], [12], [17], [18], [19],[5], [24], [26], [27]. They are flexible and relatively easy to construct, they capture a significant proportion of the complex statistics of real images and visual classes in a convenient local form, and they have good resistance to occlusions, geometric deformations and illumination variations. In particular, the statistics of natural image classes can be encoded by vector quantizing the appearance space and accumulating histograms or signatures of patch appearances based on this coding. Traditionally one codes a dense set of patches ‘texton’ representation) [18], but sparser sets based on keypoints or ‘points of interest’ detected by invariant local feature detectors have generated a lot of interest recently [1], [5], [7], [17], [26], [27]. Key-points potentially provide greater invariance and more compact coding, but they were not designed to select the most informative regions for classification and, as we will show below, dense sampling followed by explicit discriminative feature selection gives significantly better results. Figure 1: Top: sample images from four categories of the ‘Xerox 7’ dataset. Bottom: the image regions assigned to the 100 codewords with maximal inter-category discrimination in this dataset. The codewords represent meaningful object parts, even though they were learned without using the category labels.