We introduce a new image representation that encompasses both the general layout of groups of quantized local invariant descriptors as well as their relative frequency. A graph of interest points clusters is constructed and we use the matrix of commute times between the different nodes of the graph to obtain a description of their relative arrangement that is robust to large intra class variation. The obtained high dimensional representation is then embedded in a space of lower dimension by exploiting the spectral properties of the graph made of the different images. Classification tasks can be performed in this embedding space. We expose classification and labelling results obtained on three different datasets, including the challenging PASCAL VOC2007 dataset. The performances of our approach compare favorably with the standard bag of features, which is a particular case of our representation.

In this paper we provide an overview of an image representation approach based on the description of layout and appearance properties of groups of features. In each image a graph of quantized features of interest is constructed. The features that are assigned to the same codebook bin are then grouped to produce a collapsed graph; the image content is represented by the matrix of commute times of this collapsed graph. This novel image descriptor can be used to label satellite image databases; we demonstrate the relevance and the efficiency of our approach by addressing classification problems on a dataset of 0.6 m resolution Quick bird images.