Similar image search with a tiny bag-of-delegates representation

Weiwen Tu1, Rong Pan1, and Jingdong Wang2
1Sun Yat-sen University  2Microsoft Research Asia 
 
 

Abstract

Similar image search over a large image database has been attracting a lot of attention recently. The widely-used solution is to use a set of codes, which we call bag-of-delegates, to represent each image, and to build inverted indices to organize the image database. The search can be conducted through the inverted indices, which is the same to the way of using texts to index images for search and has been shown to be efficient and effective.
In this paper, we propose a tiny bag-of-delegates representation that uses a small amount of delegates with a high search performance guaranteed. The main advantage is that less storage is required to save the inverted indices while having a high search accuracy. We propose an adaptive forward selection scheme to sequentially learn more and more inverted indices that are constructed using spatial partition trees. Experimental results demonstrate that our approach can require a smaller number of delegates while achieving the same accuracy and taking similar time.

AfsTreeAlgorithm

Download

| PDF |

Results

Performance Comparison 1
Comparison1
Accuracy vs. #indices over different bucket sizes: (a)500, (b) 300and (c)100. gis the number of target NNs. AFS means our approach. PCA means random PCA-trees.
 
Performance Comparison 2
Comparison2
Accuracy vs. #(accessed images) over different bucket sizes: (a)500, (b) 300and (c)100.
 
Performance Comparison 3
Comparison3
Accuracy vs #Indices for out-of-sample queries over bucket sizes: (a)500and (b)300.
 
Performance Comparison 4
Comparison3
Accuracy vs #(accessed images) for out-of-sample queries over bucket sizes: (a)500and (b) 300.
 
 
©Copyright Jingdong Wang 2012
HTML Hit Counters