Scalable k-NN graph construction
for visual descriptors

Jing Wang1, Jingdong Wang2, Gang Zeng1, Zhuowen Tu2,3, Rui Gan1 and Shipeng Li2
1Peking University  2Microsoft Research Asia
3Lab of Neuro Imaging and Department of Computer Science, UCLA
 
Overview
 

Abstract

The k-NN graph has played a central role in increas- ingly popular data-driven techniques for various learning and vision tasks; yet, finding an efficient and effective way to construct k-NN graphs remains a challenge, especially for large-scale high-dimensional data. In this paper, we propose a new approach to construct approximate k-NN graphs with emphasis in: efficiency and accuracy. We hi- erarchically and randomly divide the data points into sub- sets and build an exact neighborhood graph over each sub- set, achieving a base approximate neighborhood graph; we then repeat this process for several times to generate mul- tiple neighborhood graphs, which are combined to yield a more accurate approximate neighborhood graph. Further- more, we propose a neighborhood propagation scheme to further enhance the accuracy. We show both theoretical and empirical accuracy and efficiency of our approach to k-NN graph construction and demonstrate significant speed-up in dealing with large scale visual data.

 

Download

| PDF |
 

Bibtex

@inproceedings{WangWZTGL12,
  author    = "Jing Wang, Jingdong Wang, Gang Zeng, Zhuowen Tu, Rui Gan, Shipeng Li",
  title     = "Scalable k-NN graph construction for visual descriptors",
  booktitle = "CVPR",
  year      = "2012",
}
 

Results

Performance Comparison
Comparison
Accuracy vs. Time performance comparisons over Caltech 101, Recognition Benchmark, Imagenet, and TinyImage
 
Performance for object discovery
Example3
Performance for object discovery over Oxford5K dataset
 
Visual results
 
Visual Example 1
Example1
Image ranking result comparison between rank-order distance and Euclidean distance. The first image in each row are the query and the images with green dot at bottom right are the correct images containing the same face as the query. (a) gives the results of using Euclidean distance and (b) gives the results of using Rank-order distance.
 
Visual Example 2
Example2
CObject discovery results: each row represents one discovered object cluster and the images are randomly picked out from the cluster.
©Copyright Jingdong Wang 2012
HTML Hit Counters