Graph-theoretic clustering for image grouping and retrieval

Image retrieval algorithms are generally based on the assumption that visually similar images are located close to each other in the feature space. Since the feature vectors usually exist in a very high dimensional space, a parametric characterization of their distribution is impossible, so non-parametric approaches, like the k-nearest neighbor search, are used for retrieval. This paper introduces a graph-theoretic approach for image retrieval by formulating the database search as a graph clustering problem by using a constraint that retrieved images should be consistent with each other (close in the feature space) as well as being individually similar (close) to the query image. The experiments that compare retrieval precision with and without clustering showed an average precision of 0.76 after clustering, which is an improvement by 5.56% over the average precision before clustering.