A Comparative Study of Irregular Pyramid Matching in Bag-of-Bags of Words Model for Image Retrieval

In this paper we assess three standard approaches to build irregular pyramid partitions for image retrieval in the bag-of-bags of words model that we recently proposed. These three approaches are: kernel k-means to optimize multilevel weighted graph cuts, Normalized Cuts and Graph Cuts, respectively. The bag-of-bags of words (BBoW) model, is an approach based on irregular pyramid partitions over the image. An image is first represented as a connected graph of local features on a regular grid of pixels. Irregular partitions (subgraphs) of the image are further built by using graph partitioning methods. Each subgraph in the partition is then represented by its own signature. The BBoW model with the aid of graph, extends the classical bag-of-words (BoW) model, by embedding color homogeneity and limited spatial information through irregular partitions of an image. 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 on Caltech-101 benchmark demonstrate that applying kernel k-means to graph clustering process produces better retrieval results, as compared with other graph partitioning methods such as Graph Cuts and Normalized Cuts for BBoW. Moreover, this proposed method achieves comparable results and outperforms SPM in 19 object categories on the whole Caltech-101 dataset.