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

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

Read Denoising Nearest Neighbor Graph via Continuous CRF for Visual Re-ranking without Fine-tuning by Jaeyoon Kim, Yoonki Cho, Taeyong Kim, Sung-Eui Yoon (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-13875.txt.

Introduction

Four researchers clean up the neighbor graphs used to re-rank image search results, in a 2024 paper. Re-ranking compares each photo with its nearest neighbors to push the best matches up. Wrong links between unlike photos, called noisy edges, drag the method down.

Their fix runs before re-ranking and needs no model training. Around each anchor photo they build a fully linked group, then judge links with a statistical distance drawn from similarity patterns. A continuous random field model uses those distances to cut the noisy edges. The cleanup runs offline, so search stays fast. Tests showed steady gains across three different re-ranking methods. Retrieval accuracy rose by clear margins in each case. The authors offer the step as a plug-in upgrade for neighbor-based image search.

Catalog record

CREATORJaeyoon Kim, Yoonki Cho, Taeyong Kim, Sung-Eui Yoon
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE30 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-13875

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

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 using Nearest Neighbor graph (NN graph) has been adapted to yield high retrieval accuracy, since it is beneficial to exploring an high-dimensional manifold and applicable without additional fine-tuning. The quality of visual re-ranking using NN graph, however, is limited to that of connectivity, i.e., edges of the NN graph. Some edges can be misconnected with negative images. This is known as a noisy edge problem, resulting in a degradation of the retrieval quality. To address this, we propose a complementary denoising method based on Continuous Conditional Random Field (C-CRF) that uses a statistical distance of our similarity-based distribution. This method employs the concept of cliques to make the process computationally feasible. We demonstrate the complementarity of our method through its application to three visual re-ranking methods, observing quality boosts in landmark retrieval and person re-identification (re-ID). 1 Introduction (a) Initial NN graph (b) NN graph after reciprocity check (c) Diffusion-based retrieval of (b) (d) NN graph denoised by ours (e) Diffusion-based retrieval of (d) Figure 1 : This figure shows NN graph (affinity) of toy data on manifold. The blue and green colors of nodes indicate different manifolds, while a yellow node and red nodes represent a query point and the retrieval results from a visual re-ranking method of diffusion. The red edges are noisy edges that are connected between different manifolds. Results (e) of our approach (d) are on the correct manifold. Best viewed with zoom-in. Nearest neighbor search approaches [ 1 , 2 , 3 ] have used various visual re-ranking techniques [ 4 , 5 , 6 ] for further improvement of retrieval accuracy. Among them, average query expansion (AQE) [ 4 ] was considered to explore an image manifold on the descriptor space in a simple manner by using a new query averaged over nearest neighbor features at a query time. However, AQE is limited to only information between query and database images. Contrary to AQE, NN graph based retrieval methods, e.g., diffusion process [ 7 , 8 , 6 , 9 ] and graph traversal [ 10 , 11 ] , fully makes use of an affinity matrix between database images as well as information between the query and database images. Diffusion methods, revisited from Donoser et al. [ 8 ] , constructed the affinity matrix, while considering the query as a part of database images, and calculated solutions of diffusion methods in an iterative manner. However, regarding the query as one of database images requires huge computational costs in online time, because of creating a new affinity matrix whenever new queries are given. Iscen et al. [ 6 ] proposed a method that does not have to recreate the matrix even if new queries are given. Yang et al. [ 12 ] also made the Iscen’s method more efficient by shifting the diffusion step from online computing to offline one. Recently, Ouyang et al. [ 13 ] utilizes self-attention modules to aggregate similarities for improving visual re-ranking outcomes, while requiring additional fine-tuning. Shao et al. [ 14 ] highlight visual re-ranking from only top-M results using rich global features to enhance only retrieval precision, not recall. The reliance of this method on the initial ranked list may reduce its robustness across varied or broader retrieval contexts. Our work assumes conditions without fine-tuning and without rich global features, performing re-ranking across the entire database [ 15 ] . Yang et al. [ 16 ] tackled an issue where NN graph based re-ranking is quite sensitive to noisy data, since all edges, even those containing noise, are used to represent the affinity matrix. Thus, a locally constrained affinity construction was proposed based on edges of satisfying k nearest neighbors ( k -NN) constraints of images for relaxing noisy edges of negative images. A seminal approach [ 6 ] suggested an extension by filtering out noisy edges even from the locally constrained affinity by using a reciprocity check of outgoing and incoming edges of the locally constrained affinity (NN graph). In this paper, we found that this reciprocity check with NN graph is insufficient to address the noisy edge problem, since the reciprocity check considers only reciprocal relationships between two edges. Since the reciprocity check and k -NN constraints do not fully exploit all information from each other, we address the problem with full consideration of relationships between all edges in a clique where we can conservatively reach a consensus (Fig. 1 ). To realize this, we efficiently employ a fully connected C-CRF, when denoising the noisy NN graph in offline time. Conditional Random Field (CRF) has been extensively studied [ 17 ] , and Continuous CRF (C-CRF) [ 18 ] was proposed for regression tasks such as depth estimation, image denoising and metric learning for person re-ID [ 19 , 20 , 21 ] . Departing to these applications, our approach targets to refine similarities between each of database images that are robust to noisy edges for improving a diffusion performance in offline time. Main contributions are summarized as follows: • We introduce a C-CRF based refinement method for noisy NN graphs that serves as a pre-processing module to enhance visual re-ranking. • Our approach utilizes a statistical distance metric to ensure robust distance measurement and employs cliques for cost-effective denoising. • We show that our method significantly enhances existing visual re-ranking methods in landmark retrieval and person re-identification, confirming its role as a complementary tool. 2 Visual re-ranking with NN graph In this section, we summarize the diffusion process to show how the NN-graph can be applied for visual re-ranking. The diffusion process in visual re-ranking constructs revised similarity considering manifold from initial similarity computed from all images in the database. Generally, this process constructs an undirected graph structure from the affinity matrix, which is defined using the pairwise similarity between images, and performs diffusion on this graph using a random walk formulation [ 6 , 12 ] . We define a database \mathcal{X} as a set of N image descriptors, where each \mathbf{x}_{i} denotes a descriptor of image i with dimensionality d ; \mathbf{x}_{i}\in\mathbb{R}^{d} . We define the affinity matrix \mathbf{A}=(a_{ij})\in\mathbb{R}^{N\times N} , \forall i,j~\in~\{1,\dotsc,N\} , following the reciprocity check with a local constraint by considering k nearest neighbors [ 6 ] , where each element is obtained by: s_{k}(\mathbf{x}_{i}|\mathbf{x}_{j})=\begin{cases}s(\mathbf{x}_{i},\mathbf{x}_{j})&\mathbf{x}_{i}\in\mathrm{NN}_{k}(\mathbf{x}_{j})\\ 0&\mathrm{otherwise}\end{cases}, (1) a_{ij}=\min\{s_{k}(\mathbf{x}_{i}|\mathbf{x}_{j}),s_{k}(\mathbf{x}_{j}|\mathbf{x}_{i})\}, (2) where the similarity function s(\cdot,\cdot) is positive and has zero self-similarity, and \mathrm{NN}_{k}(\mathbf{x}) denotes k -NN of \mathbf{x} . Intuitively, a_{ij} equals to s(\mathbf{x}_{i},\mathbf{x}_{j}) if \mathbf{x_{i}} , \mathbf{x_{j}} are the k nearest neighbors of each other, and zero otherwise. The degree matrix \mathbf{D} is a diagonal matrix with the row-wise sum of \mathbf{A} . It is used to symmetrically normalize \mathbf{A} as: \mathbf{S}=\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2} . After the matrix computation, starting from an arbitrary vector \mathbf{v}^{0} that represents the initial similarity of a given query \mathbf{y} , the diffusion is performed until its state converges with a random walk iteration: \mathbf{v}^{t+1}=\rho\mathbf{Sv}^{t}+(1-\rho)\mathbf{v}^{0},~\rho\in(0,1). (3) Zhou et al. [ 7 ] shows this iteration converges to a closed-form solution when assuming 0<\rho<1 : \mathbf{v}^{*}=(1-\rho)(\mathbf{I}-\rho\mathbf{S})^{-1}\mathbf{v}^{0}. (4) In the conventional diffusion process, the values

Read the complete text