35th Conference on Neural Information Processing Systems (NeurIPS 2021)

Hypergraph Propagation and Community Selection for Objects Retrieval Hypergraph Propagation and Community Selection for Objects Retrieval

by Guoyuan An, Yuchi Huo, Sung-Eui Yoon

Image search is a fundamental problem in computer vision with numerous applications such as content-based image browsing, visual localization, and 3D reconstruction. In this paper, 1) we propose a novel hypergraph model to efficiently propagate the spatial information in a sequence of images to improve the search performance; 2) we propose community selection to predict the accuracy of the initial search and to provide correct starting points for hypergraph diffusion; 3) our method significantly outperforms the existing query expansion and diffusion methods. And we achieve the state-of-the-art performance on the ROxford dataset with and without R1M distractors.



Abstract

Spatial verification is a crucial technique for particular object retrieval. It utilizes spatial information for the accurate detection of true positive images. However, existing query expansion and diffusion methods cannot efficiently propagate the spatial information in an ordinary graph with scalar edge weights, resulting in low recall or precision. To tackle these problems, we propose a novel hypergraph based framework that efficiently propagates spatial information in query time and retrieves an object in the database accurately. Additionally, we propose using the image graph's structure information through community selection technique, to measure the accuracy of the initial search result and to provide correct starting points for hypergraph propagation without heavy spatial verification computations. Experiment results on ROxford and RParis show that our method significantly outperforms the existing query expansion and diffusion methods.

How community selection evaluate the uncertainty of initial search?

We use the structure information of the image graph to predict the accuracy of initial search. The uncertainty of the initial search result of Q1 is lower than that of Q2 as most retrieved items of Q1 distribute in the same community.

How hypergraph propagation improve the performance?

The yellow boxes represent the correctly matched regions through hyperedges. In each row, the first image and the third image are wrongly connected through the second image in the ordinary graph. Our hypergraph propagation mechanism correctly separates these wrong connections by solving the ambiguity problem of propagation.

Contents

Paper (author preprint)
Appendix (author preprint)
Code
features
graph