Submodular Reranking with Multiple Feature Modalities for Image Retrieval

Fan Yang1, Zhuolin Jiang2 and Larry S. Davis1

1 Department of Computer Science, University of Maryland, College Park, United States
2 Noah's Ark Lab, Huawei Technologies, Hong Kong SAR, China

Abstract

We propose a submodular reranking algorithm to boost image retrieval performance based on multiple ranked lists obtained from multiple modalities in an unsupervised manner. We formulate the reranking problem as maximizing a submodular and non-decreasing objective function that consists of an information gain term and a relative ranking consistency term. The information gain term exploits relationships of initially retrieved images based on a random walk model on a graph, then images similar to the query can be found through their neighboring images. The relative ranking consistency term takes relative relationships of initial ranks between retrieved images into account. It captures both images with similar ranks in the initial ranked lists, and images that are similar to the query but highly ranked by only a small number of modalities. Due to its diminishing returns property, the objective function can be efficiently optimized by a greedy algorithm. Experiments show that our submodular reranking algorithm is effective and efficient in reranking images initially retrieved by multiple modalities. Our submodular reranking framework can be easily generalized to any generic reranking problems for real-time search engines.

Approach

We aim to address the problem: Given a query image represented by multiple feature modalities, how to improve retrieval quality by fusing these modalities?

We present a submodular objective function for reranking images retrieved by multiple feature modalities, which is very efficient and fully unsupervised. It consists of two terms.

Experimental Results

Code and Datasets

The MATLAB implementation (version 1.0) can be downloaded from here. Due to large size of the pre-computed data (similarity matrices), only an example on Holidays dataset is included. If you would like to use the pre-computed data of the other three datasets, please send me an email. I would be happy to share the data via some other ways.

Publications