Denoising Nearest Neighbor Graph via Continuous CRF for Visual Re-ranking without Fine-tuning

Jaeyoon Kim, Yoonki Cho, Taeyong Kim, Sung-Eui Yoon

Abstract

Visual re-ranking is essential for large-scale image retrieval but is often hampered by "noisy edges" in Nearest Neighbor (NN) graphs. We propose a novel denoising method using Continuous Conditional Random Fields (C-CRF) and a statistical distance metric to prune these incorrect connections. Our approach requires no fine-tuning and significantly improves retrieval accuracy across standard benchmarks.

Introduction

In large-scale image retrieval, initial rankings based on global feature similarity are often refined through visual re-ranking. This process typically utilizes an NN graph to explore the data manifold. However, high-dimensional spaces frequently produce "noisy edges"—erroneous links between dissimilar images that appear superficially similar. These edges act as bridges to irrelevant parts of the manifold, degrading the performance of re-ranking algorithms like diffusion.

Visualization of the denoising process on a toy dataset.

Traditional fixes, such as reciprocity checks, are often too simplistic as they evaluate image pairs in isolation. We address this by considering the local group consensus within image cliques.

Methodology

Our denoising framework consists of three primary stages:

  1. Clique Construction: We build fully connected subgraphs (cliques) around anchor images to provide a dense local context for relationship evaluation.
  2. Continuous Conditional Random Fields (C-CRF): We apply a C-CRF to these cliques to refine similarity scores. By balancing individual feature similarity with neighborhood consensus, we can identify and weaken inconsistent edges. The formulation allows for an efficient closed-form solution.
  3. Statistical Distance (SD): We introduce a Similarity-Based Distribution (SBD) for each node, serving as a local "fingerprint." By measuring the J-Divergence between these distributions, we can identify noisy edges that raw feature distance might miss.

Experimental Results

The method was evaluated on the ROxford and RParis benchmarks using ResNet and VGG features. Integrating our denoising step with existing re-ranking algorithms led to substantial performance gains.

mAP performance across varying neighborhood and clique sizes.

On the ROxford dataset, our method improved the mAP of Online Diffusion by up to +7.4 on the "Hard" protocol. Across all tests, we observed average improvements of 4.6 mAP for ROxford and 1.7 mAP for RParis. Notably, the method is robust to variations in neighborhood size ($k$) and clique size, performing exceptionally well even with sparse graphs.

Conclusion

We presented a robust, training-free denoising method for NN graphs. By leveraging local consensus through C-CRF and statistical distributions, our approach effectively prunes noisy edges and enhances visual re-ranking. Its plug-and-play nature makes it easily adaptable to various retrieval pipelines and architectures.

Summary updated

BibTeX
@misc{kim2024denoising,
  author = {Jaeyoon Kim and Yoonki Cho and Taeyong Kim and Sung-Eui Yoon},
  title = {{Denoising Nearest Neighbor Graph via Continuous CRF for Visual Re-ranking without Fine-tuning}},
  year = {2024},
  eprint = {2412.13875},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2412.13875},
}
Figure