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.
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:
- Clique Construction: We build fully connected subgraphs (cliques) around anchor images to provide a dense local context for relationship evaluation.
- 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.
- 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.
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