Accurate Image Retrieval with Unsupervised 2-Stage k-NN Re-Ranking

Accurate Image Retrieval with Unsupervised 2-Stage k-NN Re-Ranking

Dawei Li (Lehigh University, Bethlehem, PA, USA) and Mooi Choo Chuah (Lehigh University, Bethlehem, PA, USA)
DOI: 10.4018/IJMDEM.2016010103
OnDemand PDF Download:


Many state-of-the-art image retrieval systems include a re-ranking step to refine the suggested initial ranking list so as to improve the retrieval accuracy. In this paper, we present a novel 2-stage k-NN re-ranking algorithm. In stage one, we generate an expanded list of candidate database images for re-ranking so that lower ranked ground truth images will be included and re-ranked. In stage two, we re-rank the list of candidate images using a confidence score which is calculated based on, rRBO, a new proposed ranking list similarity measure. In addition, we propose the rLoCATe image feature, which captures robust color and texture information on salient image patches, and shows superior performance in the image retrieval task. We evaluate the proposed re-ranking algorithm on various initial ranking lists created using both SIFT and rLoCATe on two popular benchmark datasets along with a large-scale one million distraction dataset. The results show that our proposed algorithm is not sensitive for different parameter configurations and it outperforms existing k-NN re-ranking methods.
Article Preview


Image retrieval systems allow a user to search an image of interest by returning a list of similar images (e.g., including the same physical object) which are ranked by the similarity to the query. A typical image retrieval system involves two required components: image representation and image similarity calculation, and one optional but quite effective component: result re-ranking. Let us consider how an image retrieval system using the popular Bag-of-Visual-Word (BOVW) framework (Sivic, 2003) works. First, local image features such as SIFT (Scale-invariant feature transform) (Lowe, 2004) are extracted from each image and quantized using a pre-trained codebook into a histogram of visual words as the image representation, and the histogram is further weighted using the tf-idf (term frequency–inverse document frequency) scheme. Extensive studies for improving the robustness of the BOVW image representation have made significant advancements, such as Hamming Embedding (Jegou, 2008) and Multiple Assignment (Jegou, 2009). Second, an inverted index is constructed over the database images for real-time image similarity calculation, so that only images with common visual words to those in a query image are compared and included in the returned ranked list. Finally, a re-ranking method is applied to the initial list using some metrics and additional image information, e.g., feature geometric verification (Philbin, 2007).

In this paper, we focus on the problem of the final re-ranking step assuming an initial ranking list is given. Traditionally used raw feature geometric verification method which relies on applying the RANSAC (Random sample consensus) algorithm over local features’ coordinates (Fischler, 1981) is expensive in terms of both computation and storage overhead. For better efficiency and effectiveness, a new class of k-Nearest Neighbor (k-NN) re-ranking methods (Chen, 2014; Pedronette, 2014; Qin, 2011; Shen, 2012; Li, 2015a) were proposed and have been demonstrated to outperform the geometric verification method. The k-NN based re-ranking methods are motivated by the fact that an image retrieval system will return similar ranked lists for visually similar images, and thus they refine an initial ranked list by comparing the k-NN of a query image to those of the candidate database images (e.g., the initially highly ranked images). The only additional information required for performing k-NN re-ranking is the nearest neighbors of each candidate database image which can be pre-calculated during the database index construction stage for less real-time computational cost.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing