Hypergraph with sampling for image retrieval

Qingshan Liu, Yuchi Huang, Dimitris N. Metaxas

Research output: Contribution to journalArticlepeer-review

39 Scopus citations


In this paper, we propose a new transductive learning framework for image retrieval, in which images are taken as vertices in a weighted hypergraph and the task of image search is formulated as the problem of hypergraph ranking. Based on the similarity matrix computed from various feature descriptors, we take each image as a 'centroid' vertex and form a hyperedge by a centroid and its k-nearest neighbors. To further exploit the correlation information among images, we propose a soft hypergraph, which assigns each vertex vi to a hyperedge ej in a soft way. In the incidence structure of a soft hypergraph, we describe both the higher order grouping information and the affinity relationship between vertices within each hyperedge. After feedback images are provided, our retrieval system ranks image labels by a transductive inference approach, which tends to assign the same label to vertices that share many incidental hyperedges, with the constraints that predicted labels of feedback images should be similar to their initial labels. We further reduce the computation cost with the sampling strategy. We compare the proposed method to several other methods and its effectiveness is demonstrated by extensive experiments on Corel5K, the Scene dataset and Caltech 101.

Original languageEnglish (US)
Pages (from-to)2255-2262
Number of pages8
JournalPattern Recognition
Issue number10-11
StatePublished - Oct 2011

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence


  • Hypergraph
  • Image retrieval


Dive into the research topics of 'Hypergraph with sampling for image retrieval'. Together they form a unique fingerprint.

Cite this