Scalable Similar Image Search by Joint Indices

Jing Wang1, Jingdong Wang2, Xian-Sheng Hua3, and Shipeng Li2
1Peking University  2Microsoft Research Asia  2Microsoft Bing
 
DemoInterface
 

Abstract

Text-based image search is able to return desired images for simple queries, but has limited capabilities in finding images with additional visual requirements. As a result, an image is usually used to help describe the appearance requirements. In this demonstration, we show a similar image search system that can support the joint textual and visual query. We present an efficient and effective indexing algorithm, neighborhood graph index, which is suitable for millions of im-ages, and use it to organize joint inverted indices to search over billions of images.

Main Technologies

In the demonstration, we first represent each image with a hybrid global feature, which is derived from HOG feature, SCH(Spation Color Histogram) feature and Gist feature.
To organize the images, we first adopt the algorithms in [1][2][3] to partition the huge dataset into sets of point, which can also be regarded as inverted lists. We compute the centers for each inverted list, and build a neighborhood graph over the centers. Then we assign each image to multiple inverted list by conducting a graph search algorithm [4] over the neighborhood graph.
For each in-index query, we can directly obatin its candidate neighbors by uniting those inverted lists it belongs to, and for eacb out-of-index query, we can obtain its candidate neighbors by first computing its nearest inverted lists by the graph search algorithm [4], and then uniting those inverted lists. Finally, we re-rank all the candidates by the feature distance.

Download

| PDF |

Results

Performance 1
Comparison1
Comparison1
Comparison1
Similar image search results for in-index queries. For each figure, the first image is the query. The first result is from neighborhood graph index and the remaining two are from inverted indices.
 
Performance 2
Comparison2
Comparison2
Comparison2
Similar image search results for out-of-index queries. The bottom right image (with a bounding box) in each figure is the query image. The second result is got without the help of text "flower", while the third result is got with the text "flower". All results are from neighborhood graph index.
 

References

[1] Optimizing kd-trees for scalable visual descriptor indexing
[2] Similar image search with a tiny bag-of-delegates representation
[3] Complementary Hashing for Approximate Nearest Neighbor Search
[4] Query-driven iterated neighborhood graph search for large scale indexing
©Copyright Jingdong Wang 2012
HTML Hit Counters