Pairwise Similarity Propagation Based Graph Clustering for Scalable Object Indexing and Retrieval

Given a query image of an object of interest, our objective is to retrieve all instances of that object with high precision from a database of scalable size. As distinct from the bag-of-feature based methods, we do not regard descriptor quantizations as ”visual words”. Instead a group of selected SIFT features of an object together with their spatial arrangement are represented by an attributed graph. Each graph is then regarded as a ”visual word”. We measure the similarity between graphs using the similarity of SIFT features and the compatibility of their arrangement. Using the similarity measure we efficiently identify the set of K nearest neighbor graphs (KNNG) using a SOM based clustering tree. We then extend the concept of “query expansion” widely used in text retrieval to develop a graph clustering method based on pairwise similarity propagation (SPGC), in that the trained KNNG information is utilized for speeding up. Using SOM based clustering tree and SPGC, we develop a framework for scalable object indexing and retrieval. We illustrate these ideas on a database of over 50K images spanning more than 500 objects. We show that the precision is substantially boosted, achieving total recall in many cases.