Improving the quality of K-NN graphs for image databases through vector sparsification

Michael E. Houle, Xiguo Ma, Vincent Oria, Jichao Sun

Research output: Contribution to conferencePaperpeer-review

8 Scopus citations

Abstract

Neighborhood graphs are an essential component of many established methods for content-based image retrieval and automated image annotation. The performance of such methods relies heavily on the semantic quality of the graphs, which can be measured as the proportion of neighbors sharing the same class label as their query images. In this paper, we propose a new framework for the efficient construction of K-nearest neighbor (K-NN) graphs based on nearestneighbor descent (NN-Descent), in which selective sparsification of object feature vectors is interleaved with neighborhood refinement operations in an effort to improve the semantic quality of the result. A local variant of the Laplacian Score is used to identify noisy features with respect to individual images, whose values are then set to 0 (the global mean value after standardization). We show through extensive experiments that our graph construction method is able to increase the proportion of semantically-related images over unrelated images within the neighbor sets.

Original languageEnglish (US)
Pages89-96
Number of pages8
DOIs
StatePublished - 2014
Event2014 4th ACM International Conference on Multimedia Retrieval, ICMR 2014 - Glasgow, United Kingdom
Duration: Apr 1 2014Apr 4 2014

Other

Other2014 4th ACM International Conference on Multimedia Retrieval, ICMR 2014
CountryUnited Kingdom
CityGlasgow
Period4/1/144/4/14

All Science Journal Classification (ASJC) codes

  • Computer Graphics and Computer-Aided Design
  • Human-Computer Interaction
  • Software

Keywords

  • Image database
  • Iterative method
  • K-nearest neighbor graph
  • Locally noisy feature
  • Semantic quality
  • Vector sparsification

Fingerprint Dive into the research topics of 'Improving the quality of K-NN graphs for image databases through vector sparsification'. Together they form a unique fingerprint.

Cite this