Bag-of-bags of words irregular graph pyramids vs spatial pyramid matching for image retrieval

This paper presents a novel approach, named bag-of-bags of words (BBoW), to address the problem of Content-Based Image Retrieval (CBIR) from image databases. The proposed bag-of-bags of words model extends the classical bag-of-words (BoW) model. An image is represented as a connected graph of local features on a regular grid. Then irregular partitions (subgraphs) of images are further built via Normalized Cuts. Each subgraph in the partition is then represented by its own signature. Compared to existing methods for image retrieval, such as Spatial Pyramid Matching (SPM), the BBoW model does not assume that similar parts of a scene always appear at the same location in images of the same category. The extension of the proposed model to pyramid gives rise to a method we name irregular pyramid matching (IPM). The experiments demonstrate the strength of our method for image retrieval when the partitions are stable across an image category. The statistical analysis of subgraphs is discussed in the paper.