# Unifying Retrieval and Segmentation: A Hypergraph Diffusion Approach with
Spatial Verification and Uncertainty Awareness

Guoyuan An  Yuchi Huo  Sung-Eui Yoon  The authors are with the SGVR Group,
KAIST. Manuscript received Mar 01, 2024.

# Fast and Accurate Pixel Retrieval via Spatial and Uncertainty Aware
Hypergraph Diffusion

Guoyuan An  Yuchi Huo  Sung-Eui Yoon  The authors are with the SGVR Group,
KAIST. Manuscript received Mar 01, 2024.

###### Abstract

This paper presents a novel method designed to enhance the efficiency and
accuracy of both image retrieval and pixel retrieval. Traditional diffusion
methods struggle to propagate spatial information effectively in conventional
graphs due to their reliance on scalar edge weights. To overcome this
limitation, we introduce a hypergraph-based framework, uniquely capable of
efficiently propagating spatial information using local features during query
time, thereby accurately retrieving and localizing objects within a database.

Additionally, we innovatively utilize the structural information of the image
graph through a technique we term “community selection”. This approach allows
for the assessment of the initial search result’s uncertainty and facilitates
an optimal balance between accuracy and speed. This is particularly crucial in
real-world applications where such trade-offs are often necessary.

Our experimental results, conducted on the (P)ROxford and (P)RParis datasets,
demonstrate the significant superiority of our method over existing diffusion
techniques. We achieve state-of-the-art (SOTA) accuracy in both image-level
and pixel-level retrieval, while also maintaining impressive processing speed.
This dual achievement underscores the effectiveness of our hypergraph-based
framework and community selection technique, marking a notable advancement in
the field of content-based image retrieval.

###### Index Terms:

Landmark retrieval, segmentation, graph diffusion, spatial verification,
retrieval uncertainty

##  I Introduction

Image search, a fundamental task in computer vision, has seen significant
advancements even before the advent of deep learning [30, 28, 8]. Despite
these successes, challenges remain, particularly when the object of interest
occupies only a small part of the true positive image, which often includes a
complex background. This complexity can hinder users from recognizing the
correct images easily, even when the search engine ranks them highly [2]. To
address this problem, recent studies emphasize the importance of not just
identifying but also precisely localizing and segmenting the query object
within the retrieved images [2, 33]. This new task, known as pixel retrieval,
aims to enhance the accuracy and user-friendliness of image search results.

There are several existing approaches for pixel retrieval. SPatial
verification (SP) examines the spatial arrangement of matched local features
to pinpoint the target object in database images [27]. Meanwhile, detection
and segmentation methods treat the query image as a learning example to
localize and segment the target in database images [25, 18]. Dense-matching
methods involve training neural networks to establish pixel correspondences
for query and database image pairs [41]. Although these methods show promise
in pixel retrieval performance, they share a common limitation: the real-time
computation of pixel correspondences for each image pair, leading to
significant time consumption [2].

In real-world applications, pixel retrieval demands both speed and accuracy.
Our paper proposes a novel approach to address this need: pre-computing
spatial matching information of database images offline and swiftly
propagating this information for any given online query. We introduce a
spatial aware hypergraph diffusion model, which efficiently constructs a
hypergraph for a given query and propagates spatial relationships through
hyperedges across a sequence of images.

This novel technique excels in achieving rapid and accurate pixel retrieval,
and it also notably enhances the performance of image-level retrieval of
relation-based reranking methods like query expansion and diffusion. Query
expansion [8, 13, 31, 3, 14] issues a new query by aggregating useful
information of nearest neighbors of the prior query. Unfortunately, this
approach only explores the neighborhood of similar images, resulting in a low
recall [15]. On the other hand, diffusion [15, 50] explores more images on a
neighborhood graph of the dataset. It, however, adopts false positive items in
practice, leading to a low precision [30].

A key issue in these methods is the spatial ambiguity in propagation, as
illustrated in Fig. 1. Since each database image may contain multiple objects,
a sequence of images identified based on simple global feature similarity
might not consistently contain the same object. Our hypergraph diffusion
technique addresses these low recall and precision issues by effectively
propagating to only corresponding local features along spatially aware
hyperedges.

Another contribution of this paper is the development of a novel method for
measuring the uncertainty of retrieval results. Predicting retrieval
uncertainty is an essential but less explored topic in image retrieval; it is
crucial for balancing accuracy and speed in image search engines [1]. We
leverage the graph structure of the database, wherein each image is a node
connected to similar nodes. Our hypothesis is that images in the same
community likely contain the same object. A high-quality retrieval for a query
would typically yield images from a singular community. Conversely, a spread
across diverse communities indicates higher uncertainty, prompting the search
engine to employ more intensive reranking techniques. We term this approach
“community selection.”

Our experimental findings demonstrate that the spatial aware hypergraph
diffusion method achieves outstanding performance in both image-level and
pixel-level retrieval, surpassing current state-of-the-art methods. On the
challenging ROxford dataset, our hypergraph-based approach records impressive
mean Average Precisions (mAPs) of 73.0 and 60.5, with and without R1M
distractors, respectively. Moreover, our method exhibits superior pixel
retrieval accuracy at a significantly faster speed compared to existing
techniques. Additionally, the community selection technique effectively
reflects the actual quality of retrieval, confirming its efficiency.

In summary, our contributions are threefold.

  1. 1.

We introduce a fast and accurate method for pixel retrieval, offloading the
slow spatial matching process offline and leveraging a novel hypergraph model
for real-time spatial information propagation.

  2. 2.

We demonstrate that this hypergraph diffusion method substantially improves
the image-level retrieval performance of existing relation-based reranking
methods, achieving state-of-the-art accuracy on ROxford and RParis datasets.

  3. 3.

We propose a unique community selection strategy to predict retrieval quality
without user feedback, effectively balancing accuracy and speed in real-life
applications.

##  II Related works

###  II-A Pixel retrieval

Pixel retrieval, an advanced variant of image retrieval, concentrates on
identifying and segmenting pixels associated with a query object within
database images [2]. It aims to offer more detailed and user-centric results
compared to traditional image retrieval [33, 2].

In the realm of pixel retrieval, existing methods can be classified into
spatial verification [8, 27, 4], detection and segmentation [11, 21], and
dense matching [41]. Spatial verification evaluates the spatial location
consistency of matched local features, such as SIFT [20], DELF [24], and DELG
[4]. Originally developed to enhance image-level retrieval performance, it
also effectively pinpoints the location of objects in images.

Techniques like Open-World Localization (OWL) [22], Hypercorrelation Squeeze
Networks (HSNet) [21], and the Self-Support Prototype model (SSP) [11]
represent the detection and segmentation approach. They treat the query image
as a one-shot example to localize or segment the target object in database
images.

Dense matching methods, including prominent ones like GLUNet [39] and PDCNet
[40], focus on establishing dense pixel correspondences. They play a crucial
role in identifying corresponding points in database images for pixels in the
query image, thereby achieving pixel retrieval objectives.

However, these methods require identifying corresponding pixels between the
database and query images during the query time, a process that can be time-
consuming and negatively impact user experience in retrieval applications [30,
2]. To overcome this limitation, this paper introduces an innovative approach
that significantly speeds up the pixel retrieval process while maintaining
high accuracy, thereby enhancing efficiency and user experience in pixel
retrieval applications.

###  II-B Relation-based search: query expansion and diffusion

Numerous methods leverage the interrelations among database images to improve
search results. These techniques are primarily categorized into query
expansion (QE) [27] and diffusion [50].

QE [8] aggregates the top-ranked initial candidates into an expanded query,
which is then used to search for more images in the database. The critical
factor here is aggregating only helpful information and culling out unrelated
information. Average query expansion (AQE) [8] mean-aggregates the top k
retrieved images as the expanded query. Average query expansion with decay
(AQEwD) [13] gives the top k images the monotonically decaying weights over
their ranks. Alpha query expansion ($\alpha$QE) [31] uses the power-normalized
similarity between the query and the top-ranked images as the aggregation
weights. Discriminative query expansion (DQE) [3] also uses the weighted
average, where the weight is the dual-form solution of an SVM, which
classifies the positive (top-ranked) and negative (low-ranked) images of a
query. Learnable attention-based query expansion (LAttQE) [14] uses self-
attention [42] to share information between the query and the top-ranked items
to compute better aggregation weights.

Diffusion [50, 15] ameliorates the abovementioned problem by propagating
similarities through a pairwise affinity matrix. The works of Chang et al. [5]
and Liu et al. [17] are two novel variants of this line. The critical issue in
diffusion is how to calculate the affinity matrix. Some works [29, 15] use the
reciprocal neighborhood relations to refine the search results, and other [28,
5] use the inliers number of SP to re-weight the similarity. However, these
methods compress the relations between two images as a single scale. As a
result, these prior methods lost the spatial matching detail. Although the
propagation methods are elegant, they have difficulties recovering good
relations to guide the diffusion direction.

We propose a novel and straightforward hypergraph model to utilize the
relations among database images better. It connects the corresponding local
features among images using hyperedges; in a sequence of similar images, it
detects the image from which the following images are no longer relevant to
the query. This approach significantly enhances both image and pixel retrieval
performance.

###  II-C Local descriptors and spatial verification

Local descriptors are the representations of an image’s important patches.
Some popular local descriptors are RootSIFT [3], deep local feature (DELF)
[24] and deep local and global feature (DELG) [4].

Local descriptors’ location information is usually used in the spatial
verification (SP) [27] stage. A standard SP pipeline is first using a KD-tree
[27] to find the nearest neighbors between local descriptors in two images.
Then it uses the RANSAC algorithm [12] to estimate the homography matrix [34]
and the number of inlier correspondences between two images. Existing image
search engines commonly apply SP on the shortlist, say the top 100 images
ranked by a global descriptor.

SP is known to be crucial for verifying true positive images [30]. Performing
SP before diffusion improves the final retrieval performance [30, 5]. However,
it is also the slowest process [3, 28] in image search. In this paper, we put
the heavy SP in an offline setting and propose the hypergraph diffusion method
to propagate the spatial matching information online. In addition, we also
introduce the community selection technique to reduce SP’s computing overhead.
Community selection frames the diffusion initialization task as selecting a
community for the given query rather than verifying the top-ranked images
individually. The experiment shows that our hypergraph diffusion and community
selection reduce SP overhead without hurting accuracy.

##  III Overview

We first discuss issues of query expansions and diffusion process of ordinary
graphs in Sec.III-A and our novel hypergraph based propagation (Sec. III-B)
and initialization scheme utilizing the concept of community (Sec. III-C) for
achieving accurate diffusion process.

Figure 1:  a) shows a part of an ordinary graph with scalar-weighted, i.e.,
similarity, edges. Orange frames are the common visible regions among images
$\textbf{x}_{1}$, $\textbf{x}_{2}$, $\textbf{x}_{3}$, and $\textbf{x}_{4}$.
Purple frames are the common visible regions between images $\textbf{x}_{2}$
and $\textbf{x}_{5}$. $\textbf{x}_{3}$ and $\textbf{x}_{5}$ are close
neighbors to image $\textbf{x}_{2}$. While $\textbf{x}_{3}$ is related to
$\textbf{x}_{1}$ by sharing the orange frame, $\textbf{x}_{5}$ is not.
Utilizing scalar-weighted edges cannot propagate the query in the ordinary
graph without this ambiguity issue. b) shows the corresponding hypergraph of
a). Inter-image hyperedges $\textbf{e}^{1}_{s}$ are shown in yellow, intra-
image hyperedges $\textbf{e}^{2}_{k}$ are in blue, and local features
$\textbf{y}_{n}$ are in green. A hypergraph path connects local features from
$\textbf{y}_{1}$ to $\textbf{y}_{9}$ in $\textbf{x}_{1}$ and $\textbf{x}_{3}$,
but no path connects local features in $\textbf{x}_{1}$ and $\textbf{x}_{5}$.
A large version of this figure is in the appendix.

###  III-A Propagating in ordinary graph

We can use a graph $\textbf{{G}}=(\textbf{{X}},\textbf{{F}})$ to represent the
database images.
$\textbf{{X}}:=\left\\{\textbf{x}_{1},...,\textbf{x}_{m}\right\\}$ is the node
set, where item $\textbf{x}_{i}$ could be either an image or an image region
depending on a chosen retrieval method; F is the set of edges whose scalar
weight represents the similarity between two nodes connected by each edge.
Utilizing information in this ordinary graph is an important strategy to
improve retrieval results, and, thus, widely used in various methods, such as
query expansion [8, 7, 31, 14] and diffusion [15, 50]. Both diffusion and
query expansion can be represented by the following function:

$\textbf{f}^{*}=I(\textbf{f}^{0}),$ (1)

where $I$ represents the post-processing process, $f_{u}\in\mathbb{R}$ is the
ranking score for $\textbf{x}_{u}$, $\textbf{f}^{0}$ is the initial ranking
vector with $f_{u}^{0}=1$ if $\textbf{x}_{u}$ is a query and $f_{u}^{0}=0$
otherwise, and $\textbf{f}^{*}$ is the ranking vector after query expansion or
diffusion. Diffusion methods diffuse the label of the query node to its
neighbors along the graph edges until reaching a stationary state. The
stationary state is found by repeating the iteration function:
$\textbf{f}^{t+1}=\alpha\textbf{O}\textbf{f}^{t}+(1-\alpha)\textbf{f}^{0}$,
where O is the normalized affinity matrix that describes the weights of graph
edges, $\alpha$ is a jumping probability. Query expansion gathers useful
information in the query node’s nearest neighbors to update the ranking list.

Diffusion and query expansion have different advantages and disadvantages.
Diffusion can efficiently propagate information to the whole graph through a
compact formulation. However, the propagation is conducted through the
affinity matrix O [50, 15], whose scalar value cannot represent accurate
spatial information, resulting in low precision. Take Figure 1 as an example,
where images of $\textbf{x}_{1}$ and $\textbf{x}_{5}$ are incorrectly
connected through image $\textbf{x}_{2}$ in the ordinary graph with scalar
edge weights; note that they do not share common regions. This leads to false
positives in the diffusion process. We denote this as the ambiguity problem of
propagation. In contrast, query expansion uses sophisticated approaches, such
as transformer [14] and spatial verification [8, 3], to guarantee that only
shared information between query and its nearest neighbors are used to update
the ranking list. This approach, however, only explores the neighborhood of
very similar images due to the computational overhead [30, 3, 8], resulting in
a low recall.

This paper proposes novel hypergraph propagation and community selection,
settling the ambiguity problem separately in the propagation and
initialization stages. We describe these two techniques next.

###  III-B Extension to hypergraph

One meaningful direction to overcome the drawbacks of diffusion and query
expansion is to handle the ambiguity problem of graph propagation by
explicitly resolving the propagation in a more informative space. The local
features contain informative spatial information that can help to distinguish
the ambiguity through geometric verification [27]. However, considering the
large scale of the image database, it is impractical to do the geometric
verification on all the pairs. In practice, image search engines usually build
the kNN graph instead of the complete graph, which means every image only
connects with its top k similar images [15]. To utilize the spatial
information on the kNN graph, we propose a novel hypergraph propagation model
to efficiently propagate spatial information through hyperedges, connecting an
arbitrary number of nodes. This technique is appropriate for the real-world
situation where the same object in different images has a different number of
local features. In the example of Figure 1, image $\textbf{x}_{1}$ can connect
image $\textbf{x}_{3}$ by matching the local features with those of image
$\textbf{x}_{2}$, but will not connect image $\textbf{x}_{5}$.

When a query is given, we define a hypergraph
$\textbf{{H}}=(\textbf{{Y}},\textbf{{E}})$ on top of the ordinary image graph,
where its node set
$\textbf{{Y}}=\left\\{\textbf{y}_{1},...,\textbf{y}_{n}\right\\}$ contains all
the local features extracted, and the edge set E consists of hyperedges, which
are used to connect the local features related to the query object in
different images. Our model then propagates the label of local features of the
query to their neighbors and uses an aggregation function to find the final
ranking list of images, as follows:

$\textbf{l}^{*}=I_{h}(\textbf{l}^{0}),\textbf{f}^{*}=Agg(\textbf{l}^{*}),$ (2)

where $\textbf{l}^{0}$ and $\textbf{l}^{*}$ are the initial and final ranking
lists of local features respectively, $\textbf{f}^{*}$ is the ranking list of
images, $I_{h}$ is the propagation function in a hypergraph, and $Agg$ is the
aggregation function that converts ranking scores of local features to ranking
scores of images. We will discuss the construction of hypergraph in Section
IV-A and the propagation process in Section IV-B.

###  III-C Handling new queries: community selection

Diffusion methods [10, 49] usually consider the query point to be contained in
the dataset. The standard approach to handle a new query is representing the
query using its top-ranked images in the initial search to start the
propagation [15]. However, it is hard to guarantee that these global
descriptor-based nearest neighbors contain the same object as the query. We
call it the ambiguity problem of initialization. Recent studies [30, 5]
perform online spatial verification on 100 nearest neighbors of the query and
delete the wrong neighbors to improve the quality of diffusion. Unfortunately,
conducting spatial verification for 100 images in query time is a heavy
computational load for a search engine.

We find that the structure of the image graph [28, 3] contains helpful
information to measure the accuracy of the nearest neighbors. Following the
term in graph theory, we call tightly connected groups communities, which are
sets of nodes with many connections inside and few to outside. We observe that
the items containing the same objects have a high probability of composing a
community and having short geodesic distances. Based on this observation, we
frame the diffusion initialization task as selecting a community for the given
query instead of using spatial verification to delete the wrong neighbors.
This graph-based approach improves both accuracy and speed. We will give the
detail of community selection in Section IV-C

##  IV Methods

###  IV-A Construction

Assume that we have an image dataset
$\textbf{{X}}=\left\\{\textbf{x}_{1},...,\textbf{x}_{m}\right\\}$, where
$\textbf{x}_{u}$ is an image, and its corresponding K-nearest neighbor (Knn)
graph [50, 9] $\textbf{{G}}=(\textbf{{X}},\textbf{{F}})$, where F is the
ordinary edge sets. For hypergraph propagation, we define a hypergraph
$\textbf{{H}}=(\textbf{{Y}},\textbf{{E}})$, where
$\textbf{{Y}}=\left\\{\textbf{y}_{1},...,\textbf{y}_{n}\right\\}$ is the set
of vertices and $\textbf{y}_{i}$ represents a local feature in an image.
$\textbf{{E}}=\textbf{{E}}^{1}\cup\textbf{{E}}^{2}$ is the union of the inter-
image hyperedges set
$\textbf{{E}}^{1}=\left\\{\textbf{e}^{1}_{1},\textbf{e}^{1}_{2},...\textbf{e}^{1}_{s}\right\\}$
and the intra-image hyperedges set
$\textbf{{E}}^{2}=\left\\{\textbf{e}^{2}_{1},\textbf{e}^{2}_{2},...\textbf{e}^{2}_{k}\right\\}$.
An inter-image hyperedge connects local features in two images; we also say it
connects two images in this paper. An intra-image hyperedge connects local
features in the same image. These hyperedges are shown by the orange and blue
groups in Figure 1-b). The hypergraph has two incidence matrixes
$\textbf{S}^{1}=(s^{1}_{ia})$ and $\textbf{S}^{2}=(s^{2}_{ia})$, where
$s^{\alpha}_{ia}$ is 1 if $\textbf{y}_{i}\in\textbf{e}^{\alpha}_{a}$ and 0
otherwise. We build the ordinary Knn offline and build the hypergraph on top
of the Knn graph online. We call the local features in the hypergraph
activated local features. We now describe how to construct the hypergraph.

In order to solve the ambiguity problem of graph propagation, hypergraph
propagation propagates only among the spatially matched local features of
images. This paper uses RANSAC [12], the most common features matching method
in the spatial verification stage of image search [30, 24, 4], to pre-compute
the homography matrix [12] between two images offline. We then use these pre-
computed homography matrixes to verify if two features in two images are
matched when building the hyperedges at query time.

We assume the query image can be represented by local features in Y and will
discuss how to handle a new query in Section IV-C. Because a propagation
process of a query is progressive, we expand hyperedges on-demand. To judge if
an image is related to the query in a sequence of similar images, we only need
to see if it has the activated local features. An inter-image hyperedge is
then defined as follows:

######  Definition IV.1 (Inter-image hyperedge).

For two images $\textbf{x}_{u}$ and $\textbf{x}_{v}$, let
$\textbf{{V}}_{u}\subset\textbf{Y}$ and $\textbf{{I}}_{v}\subset\textbf{Y}$ be
the spatially matched local feature sets between $\textbf{x}_{u}$ and
$\textbf{x}_{v}$. The inter-image hyperedge from features in $\textbf{x}_{u}$
to $\textbf{x}_{v}$ is:
$\textbf{e}^{1}=\left(In=\textit{V}_{u},OUT=\textit{I}_{v}\right)$.

If the matching inliers between two images are less than a threshold, they
could be directly verified as irrelevant with each other. As the target of
hypergraph is to search the related images for the query, we do not build the
hyperedge for them. We set the threshold as 20 in this paper, which is the
standard threshold in the spatial verification stage of the image search
systems [28, 6]. Note that even if an image has more than 20 matching inliers
with another one, its activated local features may not be matched.

Similar to object detection [32], we use bounding box to describe the object
region. In an image, local features depicting an object locate in the object’s
bounding box. As a homography does not guarantee to find all the matched
features between two images, the inter-image hyperedges do not connect all the
features in an object’s bounding box. Unfortunately, the unmatched related
features are also important for propagation. As shown in Figure 1-b), features
$\textbf{y}_{1}$, $\textbf{y}_{2}$ and $\textbf{y}_{3}$ are in the same region
and describing the same building, but only $\textbf{y}_{1}$ and
$\textbf{y}_{3}$ are connected within image $\textbf{x}_{2}$ using an inter-
image hyperedge to image $\textbf{x}_{1}$. Without an intra-image hyperedge
connecting $\textbf{y}_{1}$, $\textbf{y}_{2}$ and $\textbf{y}_{3}$, we cannot
propagate information from images $\textbf{x}_{1}$ to $\textbf{x}_{3}$. To
recover the unmatched yet related local features, we define the intra-image
hypergraph as follows:

######  Definition IV.2 (Intra-image hyperedge).

Intra-image hyperedges are built after inter-image hyperedges. Given a feature
set in an image $\textbf{x}_{u}$, let $\textbf{{V}}_{u}\subset\textbf{{Y}}$ be
the local features that are connected by an inter-image hyperedge in
$\textbf{x}_{u}$, and $\textbf{{I}}_{u}\subset\textbf{{Y}}$ be the set of all
the local features of $\textbf{x}_{u}$. Let the smallest rectangle covering
all the features in $\textbf{{V}}_{u}$ be the bounding box $b$. The intra-
image hyperedge in $\textbf{x}_{u}$ is defined as $\textbf{e}^{2}=$ (
$IN=\textbf{{V}}_{u},OUT=\\{\textbf{y}_{j}\in\textbf{{I}}_{u};\textbf{y}_{j}\mbox{
exists in }b\\})$.

Due to the high computing cost, it is impractical to perform the propagation
on a large-scale dataset consisting of millions of images. Inspired by the
idea of truncation [15] in diffusion, we build inter-image hyperedges only
among the hop-$N$ neighbors 111Node A is in B’s hop-$N$ neighbors if A can be
connected with B using not more than $N$ different hyperedges. of a given
query image. Specifically, we build the inter-image hyperedges from image
$\textbf{x}_{u}$ to $\textbf{x}_{v}$ only if both of them are in the hop-$N$
neighbors of the query.

###  IV-B Propagation

After building the hypergraph, we use a diffusion model in the hypergraph to
calculate the final ranking scores of retrieved images. Specifically, we
define a diffusion matrix $\textbf{P}=(p_{ij})$ and set the diffusion weight
between $\textbf{y}_{i}\in\textbf{x}_{u}$ and
$\textbf{y}_{j}\in\textbf{x}_{v}$ as
$p_{ij}=d(\textbf{x}_{u},\textbf{x}_{v})\max_{akb}(s^{1}_{ia}s^{1}_{ka}s^{2}_{kb}s^{2}_{jb})$,
where $d(\textbf{x}_{u},\textbf{x}_{v})$ is the Euclidean distance between the
global features of $\textbf{x}_{u}$ and $\textbf{x}_{v}$, and
$\max_{akb}(s^{1}_{ia}s^{1}_{ka}s^{2}_{kb}s^{2}_{jb})$ records whether
$\textbf{y}_{i}$ and $\textbf{y}_{j}$ are connected in the hypergraph. More
specifically, $s^{1}_{ia}s^{1}_{ka}s^{2}_{kb}s^{2}_{jb}$ indicates that
$\textbf{y}_{i}$ and $\textbf{y}_{j}$ can be connected through a intermediate
node $\textbf{y}_{k}$; $s^{1}_{ia}s^{1}_{ka}$ shows $\textbf{y}_{i}$ and
$\textbf{y}_{k}$ are connected through inter-image hyperedge
$\textbf{e}_{a}^{1}$, and $s^{2}_{kb}s^{2}_{jb}$ shows $\textbf{y}_{k}$ and
$\textbf{y}_{j}$ are connected through intra-image hyperedge
$\textbf{e}_{b}^{2}$. If $k=i$ or $k=j$, $\textbf{y}_{i}$ and $\textbf{y}_{j}$
are directly connected. The diffusion matrix is normalized using the degree
matrix $\textbf{D}=diag(\textbf{P}\textbf{1}_{n})$ as
$\textbf{P}^{\prime}=\textbf{P}\textbf{D}$. For aggregation function,
$a_{iu}\in\textbf{A}$ is set as $\frac{1}{b_{u}}$ if
$\textbf{y}_{i}\in\textbf{x}_{u}$, and 0 otherwise, where $b_{u}$ is the
number of activated local features in $\textbf{x}_{u}$. Then the diffusion
function in Equation 2 can be written as:

$\displaystyle\textbf{Y}^{*}$
$\displaystyle=I_{h}(\textbf{Y}^{0})=\textbf{Y}^{0}+\textbf{Y}^{0}\textbf{P}^{\prime}+\textbf{Y}^{0}\textbf{P}^{\prime
2}+\cdots+\textbf{Y}^{0}\textbf{P}^{\prime N},$ (3)
$\displaystyle\textbf{f}^{*}$
$\displaystyle=Agg(\textbf{Y}^{*})=\textbf{Y}^{*}\textbf{A},$

where $\textbf{Y}^{0}$ is the initial score vector for local features. In
$\textbf{Y}^{0}$, the scores of local features in the query image are set as
1, while others are 0. The iteration version for Equation 3 is
$\textbf{Y}^{t}=\textbf{Y}^{t-1}\textbf{P}^{\prime}+\textbf{Y}^{0}$. When
$t=N$ and $t$ is large, $\textbf{Y}^{t}$ is converged to
$\textbf{Y}^{*}=\textbf{Y}^{0}+\textbf{Y}^{0}\textbf{P}^{\prime}+\textbf{Y}^{0}\textbf{P}^{\prime
2}+\cdots+\textbf{Y}^{0}\textbf{P}^{\prime
N}=(\textbf{I}-\textbf{P}^{\prime})^{-1}\textbf{Y}^{0}$; this convergence is
guaranteed because $\sum_{i}p_{ij}<1$ based on its definition and
$\textbf{Y}^{0}+\textbf{Y}^{0}\textbf{P}^{\prime}+\textbf{Y}^{0}\textbf{P}^{\prime
2}+\cdots+\textbf{Y}^{0}\textbf{P}^{\prime N}$ is the power series
representation of $(\textbf{I}-\textbf{P}^{\prime})^{-1}\textbf{Y}^{0}$.
Intuitively, this diffusion function gives high scores to the images with
shorter hypergraph geodesic distances to the query while considering
similarities of global features.

This diffusion method can simultaneously achieve pixel retrieval. After
diffusion, we treat all the local features with non-zero scores as the related
local features of the target object. For each retrieved image, we draw the
related local features’ bounding box or polygon as the target object region.

###  IV-C Community selection for new query

The hypergraph propagation described in Sec. IV assumes the query is in the
database, which may not be true in a general retrieval scenario. Now we
consider how to find the good starting nodes for a new query.

As discussed in Section III, we observe that the items containing the same
object usually belong to the same community in $G$. By checking whether the
top S items of the initial search are in the same community, we can evaluate
the quality of the initial search without query time spatial verification. As
shown in Figure 2, the quality of the global-feature-based search of Q1 is
better than Q2 because its top-ranked items are in the same community.

Figure 2: Two queries on an image graph with three communities. The numbers on
the nodes are their rankings in the 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.

Specifically, after the initial search, we use the top $S$ images and their
connected edges in $G$ to build a subgraph $G_{s}$. $G_{s}$ consists of one or
more components, and each component represents a community in $G$. We call the
top-1 image of initial search the dominant image, its component in $G_{s}$ the
dominant component, and its community in $G$ the dominant community. We call
other components in $G_{s}$ as the opposition components. Intuitively if all
the top $S$ images in $G_{s}$ constitute a single component, all of them may
contain the same object with the query image. Otherwise, the uncertainty will
increase if the number and size of the opposition components increase. This
observation also agrees with our experimental results. Inspired by Shannon
entropy, we define the uncertainty index, $U$, of the initial search as:

$U=-\sum_{i=1}^{n_{G}}P\left(C_{i}\right)\log P\left(C_{i}\right),$ (4)

where $n_{G}$ is the number of component in $G_{s}$, $C_{i}$ is a component
and $P\left(C_{i}\right)$ is the proportion of $C_{i}$ in $G_{s}$.

Community selection is the pre-stage of hypergraph propagation. The overall
retrieval process with community selection is to perform the initial search
firstly and then calculate the uncertainty of the initial search result. If
the uncertainty index is low, say $U$ is lower than 1, hypergraph propagation
uses images in the dominant community to represent the query image and starts
the propagation process from them. If the uncertainty index is high, the
search engine does the spatial verification on the top $T$ images of the
initial search to find a new dominant community for the query. In this way, we
significantly reduce the number of spatial verification while keeping very
high accuracy.

##  V Experiment

We first introduce the benchmarks and implementation detail in Section V-A and
V-B, respectively. We then compare the accuracy of our hypergraph diffusion
and the SOTA image-level and pixel-level methods in Section V-C and V-D. We
show the effectiveness of community selection in Section V-E. Finally, we
report and discuss the time and memory costs in Section VI.

###  V-A Test datasets and evaluation protocals

For image-level retrieval, we evaluate our methods on two well-known landmark
retrieval benchmarks: revisited Oxford (ROxf) and revisited Paris (RPar) [30].
There are 4,993 (6,322) database images in the ROxf (RPar) dataset, and a
different query set for each dataset, both with 70 images. We also report the
result with the R1M distractor set, which contains 1M images. The accuracy is
measured using mean average precision (mAP).

For the pixel-level retrieval, we evaluate our methods on pixel-retrieval
benchmarks: pixel revisited Oxford (PROxford) and pixel revisited Paris
(PRParis) [2]. These two datasets are designed based on the famous ROxford and
RParis [30]. They have the same query, database, and distractor images as
ROxford and RParis, and they provide pixel-level annotation. The accuracy is
measured using mAP@50:5:95. Each ground truth image in the ranking list is
treated as a true-positive only if its detection Intersection over Union (IoU)
is larger than a threshold n; the threshold n is set from 0.5 to 0.95, with
step 0.05. As [2], we report the mean of IoU (mIoU) for all the methods and
report the mAP@50:5:95 for some representative methods.

###  V-B Implementation

We use the DELG model [4] trained on GLDv2 [44] to extract both global and
local features for our Hypergraph Diffusion (HD) and all the baseline methods
unless a specific explanation is given. We find the nearest neighbor number
$K$ does not influence the final result of HD a lot, and we report the
performance of setting $K$ as 200.

For the image-level comparison, we evaluate the performance of HD and baseline
methods under the ordinary retrieval pipeline: performing the initial search,
followed by conducting reranking methods like query expansion and diffusion.
We reorder the initial ranking list using $\textbf{f}^{*}$ after the HD as the
final results. We do not use community selection and always start the HD from
the initial dominant community for all the queries to make the comparison
fair.

For the pixel-level comparison, we test all the methods using the same image-
level ranking result, the image ranking result obtained by our HD, for a fair
comparison. HD directly produces the pixel-level result when reranking the
image-level result without having any extra time-consumption. For the SOTA
baseline methods, we use them to calculate for each database and query pair to
get the pixel-level result. The accuracy is reported in Section V-D, and the
time and memory cost is reported in Section VI.

For community selection, we set $S$, the number of images for calculating the
uncertainty, as 20. When testing the performance of combining community
selection and hypergraph propagation, we set the uncertainty threshold as 1,
which we find to be a good balance between the accuracy and computation
overhead. For the query with an uncertainty index higher than the threshold,
we do the spatial verification for the top 100 items using SIFT features [19].
Once we find an item with more than 20 inliers, we treat its community as the
new dominant community, stop the spatial verification, and apply hypergraph
propagation in the new dominant community.

We conduct the offline process on 6 Intel(R) Core(TM) i9-9900K CPUs @ 3.60GHz
and 896GB of RAM and implement the online hypergraph propagation and community
selection on one CPU and 50GB of memory. The code of this work is publicly
available on https://sgvr.kaist.ac.kr/~guoyuan/hypergraph_propagation/

TABLE I: Results (% mAP) on the ROxf/RPar datasets and their large-scale versions ROxf+1M/RPar+1M, with both Medium and Hard evaluation protocols. Bold number indicates the best performance, and underline indicate the second and third one. | ROxf | ROxf+R1M | RPar | RPar+R1M
---|---|---|---|---
Method |  M |  H |  M |  H |  M |  H |  M |  H
Using standard DELG features
Global search [4] |  76.3 |  55.6 |  63.7 |  37.5 |  86.6 |  72.4 |  70.6 |  46.9
Spatial verification [4] |  81.2 |  64.0 |  69.1 |  47.5 |  87.2 |  72.8 |  71.5 |  48.7
Average QE [8] |  77.2 |  57.1 |  68.5 |  43.0 |  87.6 |  74.3 |  75.4 |  54.8
Average QE with decay [13] |  78.4 |  58.0 |  70.4 |  44.7 |  88.2 |  75.3 |  76.2 |  56.0
$\alpha$ QE [31] |  65.2 |  43.2 |  57.0 |  30.2 |  91.0 |  81.2 |  81.0 |  64.1
Diffusion [15] |  81.0 |  59.3 |  63.9 |  38.7 |  91.4 |  82.7 |  80.0 |  64.9
Hypergraph Diffusion (Ours) |  85.7 |  70.3 |  78.0 |  60.0 |  92.6 |  83.3 |  86.6 |  72.7
Advanced reranking methods
LAttQE [14] |  73.4 |  49.6 |  58.3 |  31.0 |  86.3 |  70.6 |  67.3 |  42.4
LAttDBA+LAttQE [14] |  74.0 |  54.1 |  60.0 |  36.3 |  87.8 |  74.1 |  70.5 |  48.3
SAA [26] |  78.2 |  59.1 |  61.5 |  38.2 |  88.2 |  75.3 |  71.6 |  51.0
GSS [17]+SAA [26] |  79.3 |  62.2 |  62.1 |  42.3 |  90.7 |  80.0 |  85.1 |  70.3
Diffusion [15]+SAA [26] |  76.3 |  57.8 |  66.2 |  42.4 |  90.2 |  81.2 |  86.3 |  75.4
Advanced deep learning models fine-tuned using SfM
HOW (R50) [37] |  78.3 |  55.8 |  63.6 |  36.8 |  80.1 |  60.1 |  58.4 |  30.7
FIRe (R50) [43] |  81.8 |  61.2 |  66.5 |  40.1 |  85.3 |  70.0 |  67.6 |  42.9
Advanced deep learning models fine-tuned using GLD
D2R-DELF-ASMK (R50) [35] |  76.0 |  52.4 |  64.0 |  38.1 |  80.2 |  58.6 |  59.7 |  29.4
Token (R101) [45] |  77.8 |  60.1 |  66.7 |  43.1 |  87.9 |  74.7 |  75.2 |  53.2
DOLG (R101) [47] |  78.4 |  58.6 |  75.5 |  52.4 |  88.5 |  75.4 |  78.3 |  61.9
SOLAR (R101) [23] |  81.6 |  63.3 |  71.8 |  45.3 |  88.2 |  75.2 |  72.9 |  51.3
SpCa-cro (R50) [48] |  79.9 |  59.3 |  72.8 |  49.3 |  87.4 |  73.1 |  78.0 |  58.3
SpCa-cat (R50) [48] |  81.6 |  61.2 |  73.2 |  48.8 |  88.6 |  76.2 |  78.2 |  60.9
SpCa-cro (R101) [48] |  82.7 |  65.6 |  77.8 |  53.4 |  90.2 |  79.3 |  79.1 |  65.8
SpCa-cat (R101) [48] |  83.2 |  65.9 |  77.8 |  53.3 |  90.6 |  80.0 |  79.5 |  65.0
CFCD-3 scales (R50) [51] |  82.5 |  63.6 |  72.7 |  48.5 |  89.6 |  78.1 |  78.9 |  60.1
CFCD-3 scales (R101) [51] |  84.1 |  67.8 |  74.7 |  54.1 |  91.0 |  81.2 |  82.2 |  65.5
CFCD-5 scales (R50) [51] |  82.4 |  65.1 |  73.1 |  50.8 |  91.6 |  81.7 |  81.6 |  62.8
CFCD-5 scales (R101) [51] |  85.2 |  70.0 |  74.0 |  52.8 |  91.6 |  81.8 |  82.8 |  65.8

###  V-C Comparison to the image retrieval state-of-the-art

Figure 3: Illustration of hypergraph diffusion mechanism. The orange boxes
with arrows represent the hyperedges, and the blue curved arrows are the
ordinary graph edges. In each triplet, the first image and the third image are
wrongly connected through the second image. While traditional diffusion and QE
methods wrongly propagate the similarity score from the first to the third
image through ordinary graph edge, our hypergraph diffusion does not diffuse
the similarity scores from the first to the third image by solving the spatial
ambiguity problem of propagation.

Baselines and implementation. We compare with the result of global search and
SPatial verification (SP) using DELG features. For SP, we use the standard
RANSAC implemented in the scikit-learn package to predict the affine transform
between two images. The initial local feature matching pairs for RANSAC are
first going through a ratio test with a threshold of 0.9. We set the maximum
RANSAC trials as 1000. This setting is also used by the origin DELG paper [4].
We tried several different settings during the experiment, such as changing
the ratio test threshold and increasing the maximum RANSAC trials, but did not
observe performance gain.

We compare hypergraph propagation against the existing query expansion and
diffusion methods: average query expansion [8], average query expansion with
decay [13], $\alpha$ query expansion, and diffusion [10]. We directly
implement query expansion methods and use the open code from Mishkin to
reproduce diffusion. Query expansion and diffusion are applied to global DELG
features. Although the efficient diffusion approach [15] can work for sparse
local features like R-MAC (21 features for each image), we find it is not easy
to directly apply it to the dense local features like DELG (each image
contains up to 1000 features). We additionally compare with some recent
advanced learning-based reranking methods that use dense features, which we
will introduce next.

This manuscript builds upon our prior work [1]. During the preparation of this
manuscript, several advanced methods have been introduced. We benchmark our
approach against these new techniques. We directly report the best-reported
performance for each method instead of reproducing them. The new reranking
methods are Guided Similarity Separation (GSS)[17], Learnable Attention-based
Database-side Augmentation (LAttDBA), Query Expansion (LAttQE)[14], and Self-
Attention Aggregation (SAA)[26]. We also evaluate against cutting-edge deep
learning models, particularly those fine-tuned on Structure-from-Motion (SfM)
datasets, namely HOW[37] and Feature Integration-based Retrieval (FIRe)[43],
as well as those refined using the Google Landmark Dataset (GLD), including
Detection-to-Retrieval (D2R)[35], Token-based model (Token)[45], Deep
Orthogonal fusion of Local and Global features (DOLG)[47], Second-Order Loss
and Attention for Image Retrieval (SOLAR)[23], Spatial-Context-Aware model
(SpCa)[48], and Coarse-to-Fine Compact Discriminative model (CFCD) [51].

Result. Table I compares the accuracy of hypergraph diffusion (HD) and other
retrieval methods. Among the QE/diffusion methods, HD obtains the best result
on ROxford and RParis, both with and without the R1M distractor set. Compared
to RParis, ROxford is more challenging as it contains more difficult retrieval
cases such as the change of viewpoint [30]. The performance improvement of our
method on ROxford hard cases is impressive; we get the mAP 70.3 and 60 with
and without 1M distractors, outperforming the traditional diffusion method
18.5% and 55%, respectively. Our results are also better than other techniques
in [30, 5], which integrate additional steps with more computation and memory
requirements.

In Figure 3, we demonstrate the efficacy of hypergraph propagation using
actual query examples. The figure utilizes highlighted regions, marked in
yellow, to indicate areas where correct matches are identified through
hyperedges in our model. The figure presents triplets of images to illustrate
a common issue in traditional diffusion and QE methods. In each triplet, the
first and third images are often mistakenly linked via the second image,
although they do not contain the same object. This linkage exemplifies the
famous false-positive problem in image retrieval, as discussed in [30]. Our
hypergraph mechanism addresses this by resolving the spatial ambiguity
commonly observed in propagation processes. By diffusing along the hyperedges
instead of the ordinary graph edge, our method significantly mitigates the
false-positive issue in existing diffusion and QE techniques.

Ordinary diffusion is better than QE methods on all the datasets except
ROxford with R1M distractors. We think that the texture and shape of medieval
buildings in ROxford are common and tend to appear in other buildings around
the world. When retrieving these objects with R1M distractors, its ambiguity
problem explores more false positive items, leading to a low mAP than QE
methods. Our hypergraph propagation keeps the spatial information during
propagation, thus avoiding the false positive issue of ordinary diffusion,
resulting in high accuracy.

While preparing this manuscript, several advanced and promising methods have
emerged in the field. As shown in Table I, our HD approach maintains a
competitive accuracy compared to these recent methods. HD achieves the highest
accuracy on the ROxford and RParis benchmarks. The exception is in the
challenging scenario of RParis with 1 million distractors under the hard
setting, where the diffusion [15] combined with SAA [26] outperforms others.
Table I shows that our HD achieves top-tier accuracy among the existing
reported performances of models fine-tuned with standard Google Landmarks
Dataset (GLD) and Structure-from-Motion (SfM). These results show that our
diffusion approach on dense local features using hypergraphs is promising.
Note that only SP and our HD can localize the target object among the methods
in Table I, which we will introduce in the next section.

###  V-D Comparison to the pixel retrieval state-of-the-art

TABLE II: Results of pixel retrieval from ground truth query-index image pairs (% mean of mIoU) on the PROxf/PRPar datasets with both Medium and Hard evaluation protocols. D and S indicate detection and segmentation results respectively. Bold number indicates the best performance, and underline indicates the second one. Our HD achieves both the best image-level (Table I ) and pixel-level retrieval accuracy among the retrieval and localization unified methods. Note that HD is much faster than SP, detection, segmentation, and dense matching methods, as shown in Table III and Sec. VI.  Method | Medium | Hard |
---|---|---|---
| PROxf | PRPar | PROxf | PRPar |  Average
|  D |  S |  D |  S |  D |  S |  D |  S |
Retrieval and localization unified methods
SIFT+SP [27] |  26.1 |  10.9 |  24.2 |  9.7 |  18.2 |  7.3 |  19.3 |  7.8 |  15.44
DELF+SP [24] |  43.7 |  20.0 |  40.7 |  16.7 |  33.2 |  13.9 |  32.2 |  12.4 |  26.60
DELG+SP [4] |  44.1 |  19.7 |  40.1 |  16.5 |  34.8 |  14.5 |  31.2 |  11.7 |  26.57
D2R [35]+Resnet-50-Faster-RCNN+Mean |  20.2 |  - |  29.6 |  - |  16.7 |  - |  27.4 |  - |  -
D2R [35]+Resnet-50-Faster-RCNN+VLAD [16] |  25.8 |  - |  37.5 |  - |  21.6 |  - |  35.5 |  - |  -
D2R [35]+Resnet-50-Faster-RCNN+ASMK [36] |  26.3 |  - |  38.5 |  - |  21.6 |  - |  35.6 |  - |  -
D2R [35]+Mobilenet-V2-SSD+Mean |  19.7 |  - |  25.9 |  - |  20.1 |  - |  27.9 |  - |  -
D2R [35]+Mobilenet-V2-SSD+VLAD [16] |  23.1 |  - |  33. |  - |  20.9 |  - |  33.6 |  - |  -
D2R [35]+Mobilenet-V2-SSD+ASMK [36] |  22.4 |  - |  34.0 |  - |  20.8 |  - |  33.1 |  - |  -
HD (ours) |  29.7 |  24.7 |  49.2 |  38.2 |  22.6 |  19.4 |  39.1 |  31.0 |  31.74
Detection methods
OWL-VIT (LiT) [22] |  11.4 |  - |  18.0 |  - |  6.3 |  - |  15.0 |  - |  -
OS2D-v2-trained [25] |  10.5 |  - |  13.7 |  - |  11.7 |  - |  14.3 |  - |  -
OS2D-v1 [25] |  7.0 |  - |  8.5 |  - |  8.7 |  - |  9.2 |  - |  -
OS2D-v2-init [25] |  13.6 |  - |  15.4 |  - |  14.0 |  - |  15.1 |  - |  -
Segmentation methods
SSP (COCO) + ResNet50 [11] |  19.2 |  34.5 |  31.1 |  48.7 |  15.1 |  25.3 |  29.8 |  41.7 |  30.68
SSP (VOC) + ResNet50 [11] |  19.7 |  34.3 |  31.4 |  48.8 |  16.1 |  26.1 |  30.3 |  40.4 |  30.89
HSNet (COCO) + ResNet50 [21] |  23.4 |  32.8 |  37.4 |  41.9 |  21.0 |  25.7 |  34.7 |  36.5 |  31.67
HSNet (VOC) + ResNet50 [21] |  21.0 |  29.8 |  31.4 |  39.7 |  17.1 |  23.2 |  29.7 |  34.9 |  28.35
HSNet (FSS) + ResNet50 [21] |  30.5 |  35.7 |  39.4 |  40.2 |  22.7 |  25.1 |  34.7 |  32.8 |  32.64
Mining (VOC) + ResNet50 [46] |  18.3 |  30.5 |  29.6 |  42.7 |  15.1 |  21.4 |  28.1 |  34.3 |  27.50
Mining (VOC) + ResNet101 [46] |  18.1 |  28.6 |  29.5 |  40.0 |  14.2 |  20.4 |  28.2 |  34.4 |  26.68
Dense matching methods
GLUNet-Geometric [39] |  18.1 |  13.2 |  22.8 |  15.2 |  7.7 |  4.6 |  13.3 |  7.8 |  12.84
PDCNet-Geometric [40] |  29.1 |  24.0 |  30.7 |  21.9 |  20.4 |  15.7 |  20.6 |  12.6 |  21.87
GOCor-GLUNet-Geometric [38] |  30.4 |  26.0 |  33.4 |  25.6 |  20.8 |  16.0 |  19.8 |  13.3 |  23.16
WarpC-GLUNet-Geometric (megadepth) [41] |  31.3 |  25.4 |  36.6 |  27.3 |  21.9 |  15.8 |  26.4 |  17.3 |  25.25
GLUNet-Semantic [39] |  18.5 |  14.4 |  22.4 |  15.6 |  8.7 |  5.6 |  12.8 |  7.8 |  13.22
WarpC-GLUNet-Semantic [41] |  27.5 |  21.4 |  36.8 |  25.7 |  18.5 |  11.9 |  28.3 |  17.6 |  23.46
Figure 4: Visual examples of how Hypergraph Diffusion (HD) achieves better pixel retrieval results than direct SPatial verification (SP) using the same DELG features. The yellow boxes in query images are the cropped region given by the benchmark. Yellow boxes in SP are the minimum bounding box of the matching points. Yellow boxes with line arrows indicate the diffusion pathes in HD from the query region to the correspondence region in the target database image. In A, an ‘easier’ database image offers a clear, unoccluded view of the target query landmark, demonstrating improved matching. B highlights how these database images provide viewpoints more aligned with the query image, enhancing object matching. C shows the advantage in scenarios with varying illumination, where ‘easier’ images assist in achieving more accurate matches. Lastly, D reveals that when the target database image has a more complex background than the query image, direct spatial verification can lead to outlier matchings. In contrast, the ‘easier’ database images selected by HD provide additional context, thus facilitating more precise pixel retrieval.  TABLE III: Results of pixel retrieval from database (% mean of mAP@50:5:95) on the PROxf/PRPar datasets and their large-scale versions PROxf+1M/PRPar+1M, with both Medium (M) and Hard (H) evaluation protocols. Red indicates the best performance and Bold indicates the second best performance. The speed of hypergraph propagation (HP) in the reranking stage is 0.23s per 100 image pairs; it does not add any additional time or computing cost for pixel-level matching/segmentation. Compared with DELG+SP, OWL-ViT, SSP, and WarpCGLUNet, HD is much faster while maintaining high accuracy. Compared with D2R+Faster-RCNN+ASMK, HD achieves higher accuracy on both pixel retrieval and image retrieval (Table I).  | PROxf | PROxf+R1M | PRPar | PRPar+R1M |
---|---|---|---|---|---
M |  H |  M |  H |  M |  H |  M |  H |
Image retrieval: DELG initial ranking [4] \+ HD reranking [1] |  Overhead per 100 image pairs
Pixel retrieval methods |  DELG + SP [4] |  39.6 |  30.5 |  36.0 |  28.2 |  34.8 |  20.2 |  34.7 |  19.5 |  41.22s
|  D2R+Faster-RCNN+ASMK [35] |  30.1 |  23.5 |  30.5 |  22.0 |  26.3 |  25.3 |  25.7 |  24.9 |  0.11 s
|  OWL-VIT [22] |  12.3 |  6.6 |  12.1 |  13.6 |  7.9 |  7.6 |  7.9 |  7.8 |  296.21s
|  SSP [11] |  33.0 |  29.7 |  35.7 |  30.5 |  46.4 |  37.2 |  45.6 |  37.2 |  62.33 s
|  WarpCGLUNet [41] |  31.2 |  32.6 |  31.5 |  31.7 |  34.1 |  27.3 |  34.3 |  28.1 |  181.64s
|  HD |  26.9 |  39.7 |  25.3 |  33.1 |  43.7 |  39.6 |  43.8 |  38.9 |  0s

Baselines. Besides the image level performance, we compare our hypergraph
diffusion with the state-of-the-art (SOTA) methods on pixel retrieval
benchmarks PROxford and PRParis in Table III. To find the pixel
correspondences in the given database image, we choose the SOTA methods for
landmark search, detection, segmentation, and dense matching fields. SPatial
verification (SP) with Scale-Invariant Feature Transform (SIFT), DEep Local
Feature (DELF), and DEep Local and Global features (DELG) [4] are the SOTA
matching approaches in the landmark retrieval field. We also test the SOTA
detection method Detect-to-Retrieval (D2R) in the landmark retrieval field,
where the detailed implementation is explained in the next paragraph. The
Vision Transformer for Open-World Localization (OWL-ViT) [22] and One-Stage
one-shot Detec- tor (OS2D) are the SOTA methods in detection. The Self-Support
Prototype model (SSP) [11], Hypercorrelation Squeeze Network (HSNet), and
Mining model (Mining) are the SOTA segmentation methods. The Global-Local
Universal Network (GLUNet), Probabilistic Dense Correspondence Network
(PDCNet), and GLUNet trained using Globally Optimized Correspondence (GOCor)
and Warp Consistency objective (WarpCGLUNet) [41] are the SOTA methods in
dense matching. We directly use the reported performance of these methods from
the pixel retrieval benchmark [2].

We additionally introduce the implementation detail about D2R [35] in Table II
and III because this is the first time to use its fine-tuned detector for
localization purposes. D2R was originally designed to increase the image-level
retrieval performance; it detects many candidate regions for each database
image to get a better global feature. In this paper, we do not change the
image-level ranking order for comparison fairness; Table I shows that our HD
gives better results on the image-level ranking. For each proposed candidate
region detected by D2R, we use the Aggregated Selective Match Kernel (ASMK) to
aggregate all the DELG local features inside it. The region with the highest
matching score with the ASMK feature of the query image is chosen as the final
region. When aggregating the local features, we also tried the Vector of
Locally Aggregated Descriptors (VLAD) and the simple average (Mean)
aggregation. We report its result of using Faster-RCNN [32] or SSD [18]
backbones fine-tuned on a huge manually boxed landmark dataset [35].

Result. In Tables II and III, we present a comparative analysis of pixel-
retrieval accuracy between our Hypergraph Diffusion (HD) method and other
state-of-the-art (SOTA) techniques. Unlike conventional approaches that
compute direct correspondences for each query-database image pair, HD employs
an innovative strategy. It diffuses spatial information from the query to the
database images, which significantly cuts down on time and computational
resources. Notably, despite initial expectations of a trade-off between speed
and accuracy, our results reveal that HD’s accuracy is not uniformly inferior
to direct Spatial verification (SP) methods. Using the same DELG local
features, HD demonstrates a reduced accuracy on the PROxford dataset but
excels in the PRParis dataset compared to SP.

The underlying reason for this performance differential might lie in our
diffusion approach. Rather than matching query and database images directly
via SP, HD initially identifies correspondences in more straightforward
database images and subsequently tackles more challenging ones. This stepwise
diffusion process effectively mitigates the impact of viewpoint and
illumination variations between image pairs, breaking down severe changes into
manageable phases.

To validate this hypothesis, we conducted visualizations, as depicted in Fig.
4. The visual evidence suggests that while the direct SP struggles to localize
correspondence objects accurately in complex cases, our HD method achieves
superior localization. It starts by detecting correspondences in less complex
images, gradually extending to more challenging ones. Intriguingly, the
‘easier’ database images contain additional visual cues absent in the query
images and significantly aid the RANSAC-based SP in matching objects in more
complex scenarios. For example, Fig.4-A illustrates how an ‘easier’ database
image provides a clearer, unoccluded view of the target query landmark.
Similarly, Fig.4-B shows that these database images offer viewpoints more
closely aligned with the query image, aiding in object matching. In scenarios
with changing illumination, as shown in Fig. 4-C, ‘easier’ database images
help mitigate this change, facilitating more accurate matching. Furthermore,
in Fig. 4-D, we observe that the target database image has a more complex
background than the query image. Note that the input query is only the yellow
region. This complexity often leads to outlier matchings in direct SP.
However, the ‘easier’ database images selected by our HD method provide
additional background context, resulting in more accurate pixel retrieval.

Tables II and III illustrate that HD surpasses current SOTA detection methods
capabilities and offers competitive, if not superior, performance than
segmentation and dense-matching methods. Significantly, our approach merges
image-level and pixel-level analyses, outpacing traditional two-step methods
by delivering pixel-level results simultaneously with image-level rankings.
This efficiency, crucially discussed in Section VI, positions HD as a robust
and efficient solution for pixel retrieval tasks. It shows that shifting the
spatial verification to an offline process not only enhances image-level
performance but also drastically reduces retrieval time, achieving good pixel-
retrieval performance. Considering accuracy and speed, HD emerges as a
compelling choice for pixel retrieval.

###  V-E Effectivness of community selection

Figure 5: mAP of the query results above the uncertainty threshold. Uncertainty predicts the query quality well. Figure 6: In this example, the top 11 images and the initial dominant community is unrelated to the query. Its uncertainty index is 1.77, which means the search engine is very uncertain about the accuracy of initial dominant community. So CS finds a new dominant community using spatial verification. After hypergraph propagation in this new dominant community, the retrieval performance is significantly improved.  TABLE IV:  Comparison between with and without community selection (CS) as the pre-stage when using spatial verification (SP) to initialize the hypergraph propagation (HP). This table shows both the mAP and the total number of queries which need SP when testing the corresponding dataset.  |  HP | CS + SP + HP | SP + HP
---|---|---|---
|  mAP |  mAP |  total # SP |  mAP |  total # SP
ROxf(M/H) |  85.7/70.3 |  88.4/73.0 |  4 |  88.4/73.0 |  70
ROxf+R1M(M/H) |  78.0/60.0 |  79.1/60.5 |  7 |  79.1 / 60.5 |  70
RPar(M/H) |  92.6/83.3 |  92.6/83.3 |  0 |  92.6/83.3 |  70
RPar+R1M(M/H) |  86.6/72.7 |  86.6/72.7 |  0 |  86.6/72.7 |  70

Figure 5 shows the mAP of the initial search results in ROxford with different
uncertainty thresholds. As the uncertainty increases, the mAP of the initial
search result decreases. The uncertainty index predicts the quality of the
initial search without any user feedback. Only for the high uncertainty
retrieval results, we use the computationally heavy approach, i.e., spatial
verification, to improve the precision of nearest neighbors before the
hypergraph propagation.

Table IV compares the performances between with and without community
selection (CS) as the pre-stage when using spatial verification (SP) to
initialize the hypergraph propagation (HP). With CS, the search engine
improves the performance of hypergraph propagation in ROxford very efficiently
by only conducting SP on 4 and 7 queries with and without R1M distractors,
respectively. The performance improvement with R1M distractors is less than
that without them. We think its reason is that the correct items with the R1M
distractors are ranked outside the top 100 images and thus are not detected by
SP. Although CS does not improve the retrieval results of these cases, it
successfully tags them as uncertain cases. We think this result leads to a
promising future direction. Because once a search engine can automatically
detect the failed query cases, it is possible to refine the representation
ability by relabeling and training only for the failed cases instead of
training on a large dataset.

Thanks to the improved representation ability of DELG [4] features, the
nearest neighbors of all queries in RParis dataset have high precision. The
average precisions of the top 20 items of the initial result of all the
queries in RParis are 0.97 and 0.90 in medium and hard protocols,
respectively. As the initial dominant communities for all the queries in
RParis are correct, online SP is not helpful for the propagation process. CS
avoids these unnecessary SPs in these cases as the uncertainties of all the
queries are low, as shown in Table IV. CS significantly improves the retrieval
performance for some hard cases. Figure 6 shows an impressive example in
ROxford, in which the mAP increases from 0.077 and 0.062 to 0.988 and 0.987 in
medium and hard protocols, respectively.

In summary, the main benefits of CS include: 1) CS quickly detects the low-
quality retrieval result, which is either because of the difficult query or
the insufficient feature representation ability; 2) CS avoids the unnecessary
computationally heavy spatial verification process; 3) CS provides significant
performance improvement for some hard cases.

##  VI Time and memory cost

TABLE V: Average data size per database image (in Byte), measured in Numpy array format. Spatial verification (SP) averagely requires 1040000 bytes, whereas Hypergraph Diffusion (HD) needs only 2678. HD demonstrates a significantly higher memory efficiency, being 388 times more efficient than SP. Global feature |  Matching information for HD |  Local features for SP
---|---|---
8192 B |  2678 B |  1040000 B
TABLE VI: Breakdown of average time per query. Initial search |  Hypergraph diffusion |  Uncertainty calculation
---|---|---
0.62 s |  1.07 s |  0.0003 s
TABLE VII: Comparison of time complexity and latency across different pixel-retrieval approaches. K indicates the number of images to calculate the pixel-level result. h (set as 3 in this paper) indicates the maximum iteration in hypergraph diffusion. r (set as 1000, the most common choice in this field) is the maximum RANSAC iteration time. l and d are the local features’ numbers and dimensions, 1000 and 1024 for DELG. n is the image resolution or feature map size, f is the representation dimension, k is the kernel size of convolutions, and L is the number of Transformer or CNN layers. When testing the latency, we use an i9-9900K CPU @ 3.60GHz for HD and SP and a GeForce RTX™ 3090 Ti for deep learning methods. We use OWL [22] and WarpCGLUNet [41] as the representative transformer-based and CNN-based models, respectively. Our method is much faster than the existing approaches for the pixel retrieval task. Method |  Hypergraph diffusion (ours) |  Spatial verification |  Transformer backbone |  CNN backbone
---|---|---|---|---
Time complexity per query |  $O(h)$ |  $O(K\times r\times l^{2}\times d^{2})$ |  $O(K\times L\times n^{2}\times f)$ |  $O(K\times L\times c\times n\times f^{2})$
Latency per 100 image pairs |  0.23s |  41.22s |  296.2s (OWL [22]) |  181.6s (WarpCGLUNet [41])

In this section, we focus on assessing the time and memory costs associated
with Hypergraph Diffusion (HD) in retrieval systems. While the accuracy of HD
has been addressed in previous sections, here we aim to shed light on its
efficiency and resource utilization, essential factors for practical
deployment.

For hypergraph construction during query execution, spatial matching
information for each database image and its k-nearest neighbors (with k set to
200 as introduced in Sec. V-B) is recorded. Table V presents a comprehensive
breakdown of memory usage. The matching information occupies an average of
2,678 bytes per database image. Notably, this memory usage constitutes only
about 33% of the memory required for the DELG global feature and a mere 0.2%
of that for local features. Note that HD does not need to load the local
features in query time. This comparison illustrates HD’s memory efficiency.

In Table VI, we show the average query time during our experiments on the
ROxford + R1M dataset. HD averages 1.07 s per query, while the initial search
takes 0.62 s. This overhead, we argue, is reasonable given the benefits in
accuracy and memory efficiency. Furthermore, the latency for uncertainty
checks via our community selection technique is impressively minimal at 0.0003
s, bolstering our claim about the method’s efficiency.

In Table VII, we compare the time complexity and latency of various pixel
retrieval methods, including HD. Unlike Spatial Verification (SP) and neural
network-based approaches, HD leverages pre-calculated matching information,
leading to a time complexity linearly dependent on the diffusion process’s
maximum iteration number ($O(h)$). This simplicity starkly contrasts with the
complexity of SP and the inference latency inherent in neural network methods,
as shown in Table VII. To provide a tangible comparison, we document the
latency experienced in processing 100 image pairs using different methods,
with HD showing a marked advantage in speed. This comparative analysis
underpins the practical viability of HD in time-sensitive applications. Our
experiments used an i9-9900K CPU @ 3.60GHz for HD and SP and a GeForce RTX™
3090 Ti for deep learning methods. This hardware setup reflects a high but
realistic standard in computational resources, ensuring that our results
represent potential real-world deployments.

##  VII Discussion and conclusion

Our research introduces a novel approach to both image-level and pixel-level
retrieval, leveraging hypergraph diffusion and community selection. This
method has demonstrated high accuracy and remarkable efficiency in both time
and memory usage, positioning it as a strong candidate for advanced retrieval
systems. Despite these promising results, we acknowledge several areas for
future exploration and improvement:

Reducing Offline Computing Overhead: Currently, our system relies on multiple
CPUs for offline spatial verification, requiring approximately 12 hours to
process the ROXford dataset on a single CPU. A transition to a GPU-based
implementation is anticipated to enhance offline computing speed
significantly.

Enhancing Online Processing Speed: The online processing speed, directly
related to the number of diffusion steps in hypergraph diffusion, presents an
opportunity for optimization. While our current implementation uses Python,
transitioning to a C implementation could substantially improve processing
speed, which is particularly important for real-time applications.

Optimizing for Large-Scale Queries: Improving the system’s performance in
large-scale query scenarios remains a critical challenge. Efficient handling
of extensive datasets and queries is essential for practical applications.

Database Management Efficiency: An important aspect to consider is the
efficient addition and deletion of images in the database. This process
involves applying spatial verification for newly added database images, which
requires efficient management to maintain system performance.

In conclusion, we believe that our approach combining hypergraph propagation
with community selection takes a meaningful step in the realm of image and
pixel search techniques. Notably, our method has achieved impressive mean
Average Precision (mAP) scores of 73.0 and 60.5 on the ROxford dataset’s hard
protocol, with and without R1M distractors, respectively. To the best of our
knowledge, these results represent state-of-the-art achievements in this
field. We hope that our work lays a solid foundation for future research and
development in efficient and accurate image retrieval systems.

##  Acknowledgement

We express our profound appreciation to Prof. Giorgos Tolias from the Czech
Technical University in Prague. His readiness to meticulously review drafts of
our paper and offer comprehensive and constructive feedback has been
instrumental to the advancement of our work.

## References

  * [1] Guoyuan An, Yuchi Huo, and Sung-Eui Yoon.  Hypergraph propagation and community selection for objects retrieval.  Advances in Neural Information Processing Systems, 34:3596–3608, 2021.
  * [2] Guoyuan An, Woo Jae Kim, Saelyne Yang, Rong Li, Yuchi Huo, and Sun-Eui Yoon.  Towards content-based pixel retrieval in revisited oxford and paris.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 20507–20518, 2023.
  * [3] Relja Arandjelović and Andrew Zisserman.  Three things everyone should know to improve object retrieval.  In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 2911–2918. IEEE, 2012.
  * [4] Bingyi Cao, André Araujo, and Jack Sim.  Unifying deep local and global features for image search.  In European Conference on Computer Vision, pages 726–743. Springer, 2020.
  * [5] Cheng Chang, Guangwei Yu, Chundi Liu, and Maksims Volkovs.  Explore-exploit graph traversal for image retrieval.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9423–9431, 2019.
  * [6] Ondrej Chum et al.  Large-scale discovery of spatially related images.  IEEE transactions on pattern analysis and machine intelligence, 32(2):371–377, 2009.
  * [7] Ondřej Chum, Andrej Mikulik, Michal Perdoch, and Jiří Matas.  Total recall ii: Query expansion revisited.  In CVPR 2011, pages 889–896. IEEE, 2011.
  * [8] Ondrej Chum, James Philbin, Josef Sivic, Michael Isard, and Andrew Zisserman.  Total recall: Automatic query expansion with a generative feature model for object retrieval.  In 2007 IEEE 11th International Conference on Computer Vision, pages 1–8. IEEE, 2007.
  * [9] Wei Dong, Charikar Moses, and Kai Li.  Efficient k-nearest neighbor graph construction for generic similarity measures.  In Proceedings of the 20th international conference on World wide web, pages 577–586, 2011.
  * [10] Michael Donoser and Horst Bischof.  Diffusion processes for retrieval revisited.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1320–1327, 2013.
  * [11] Qi Fan, Wenjie Pei, Yu-Wing Tai, and Chi-Keung Tang.  Self-support few-shot semantic segmentation.  2022\.
  * [12] Martin A Fischler and Robert C Bolles.  Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography.  Communications of the ACM, 24(6):381–395, 1981.
  * [13] Albert Gordo, Jon Almazan, Jerome Revaud, and Diane Larlus.  End-to-end learning of deep visual representations for image retrieval.  International Journal of Computer Vision, 124(2):237–254, 2017.
  * [14] Albert Gordo, Filip Radenovic, and Tamara Berg.  Attention-based query expansion learning.  In European Conference on Computer Vision, pages 172–188. Springer, 2020.
  * [15] Ahmet Iscen, Giorgos Tolias, Yannis Avrithis, Teddy Furon, and Ondrej Chum.  Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2077–2086, 2017.
  * [16] Hervé Jégou, Matthijs Douze, Cordelia Schmid, and Patrick Pérez.  Aggregating local descriptors into a compact image representation.  In 2010 IEEE computer society conference on computer vision and pattern recognition, pages 3304–3311. IEEE, 2010.
  * [17] Chundi Liu, Guangwei Yu, Maksims Volkovs, Cheng Chang, Himanshu Rai, Junwei Ma, and Satya Krishna Gorti.  Guided similarity separation for image retrieval.  2019\.
  * [18] Wei Liu, Dragomir Anguelov, Dumitru Erhan, Christian Szegedy, Scott Reed, Cheng-Yang Fu, and Alexander C Berg.  Ssd: Single shot multibox detector.  In European conference on computer vision, pages 21–37. Springer, 2016.
  * [19] David G Lowe.  Object recognition from local scale-invariant features.  In Proceedings of the seventh IEEE international conference on computer vision, volume 2, pages 1150–1157. Ieee, 1999.
  * [20] David G Lowe.  Distinctive image features from scale-invariant keypoints.  International journal of computer vision, 60:91–110, 2004.
  * [21] Juhong Min, Dahyun Kang, and Minsu Cho.  Hypercorrelation squeeze for few-shot segmentation.  In Proceedings of the IEEE/CVF international conference on computer vision, pages 6941–6952, 2021.
  * [22] Matthias Minderer, Alexey Gritsenko, Austin Stone, Maxim Neumann, Dirk Weissenborn, Alexey Dosovitskiy, Aravindh Mahendran, Anurag Arnab, Mostafa Dehghani, Zhuoran Shen, et al.  Simple open-vocabulary object detection with vision transformers.  arXiv preprint arXiv:2205.06230, 2022.
  * [23] Tony Ng, Vassileios Balntas, Yurun Tian, and Krystian Mikolajczyk.  Solar: second-order loss and attention for image retrieval.  In Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part XXV 16, pages 253–270. Springer, 2020.
  * [24] Hyeonwoo Noh, Andre Araujo, Jack Sim, Tobias Weyand, and Bohyung Han.  Large-scale image retrieval with attentive deep local features.  In Proceedings of the IEEE International Conference on Computer Vision (ICCV), Oct 2017.
  * [25] Anton Osokin, Denis Sumin, and Vasily Lomakin.  OS2D: One-stage one-shot object detection by matching anchor features.  In proceedings of the European Conference on Computer Vision (ECCV), 2020.
  * [26] Jianbo Ouyang, Hui Wu, Min Wang, Wengang Zhou, and Houqiang Li.  Contextual similarity aggregation with self-attention for visual re-ranking.  Advances in Neural Information Processing Systems, 34:3135–3148, 2021.
  * [27] James Philbin, Ondrej Chum, Michael Isard, Josef Sivic, and Andrew Zisserman.  Object retrieval with large vocabularies and fast spatial matching.  In 2007 IEEE conference on computer vision and pattern recognition, pages 1–8. IEEE, 2007.
  * [28] James Philbin and Andrew Zisserman.  Object mining using a matching graph on very large image collections.  In 2008 Sixth Indian Conference on Computer Vision, Graphics & Image Processing, pages 738–745. IEEE, 2008.
  * [29] Danfeng Qin, Stephan Gammeter, Lukas Bossard, Till Quack, and Luc Van Gool.  Hello neighbor: Accurate object retrieval with k-reciprocal nearest neighbors.  In CVPR 2011, pages 777–784. IEEE, 2011.
  * [30] Filip Radenović, Ahmet Iscen, Giorgos Tolias, Yannis Avrithis, and Ondřej Chum.  Revisiting oxford and paris: Large-scale image retrieval benchmarking.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5706–5715, 2018.
  * [31] Filip Radenović, Giorgos Tolias, and Ondřej Chum.  Fine-tuning cnn image retrieval with no human annotation.  IEEE transactions on pattern analysis and machine intelligence, 41(7):1655–1668, 2018.
  * [32] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  arXiv preprint arXiv:1506.01497, 2015.
  * [33] Xiaohui Shen, Zhe Lin, Jonathan Brandt, Shai Avidan, and Ying Wu.  Object retrieval and localization with spatially-constrained similarity measure and k-nn re-ranking.  In 2012 IEEE Conference on Computer Vision and Pattern Recognition.
  * [34] Richard Szeliski.  Computer vision: algorithms and applications.  Springer Science & Business Media, 2010.
  * [35] Marvin Teichmann, Andre Araujo, Menglong Zhu, and Jack Sim.  Detect-to-retrieve: Efficient regional aggregation for image search.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5109–5118, 2019.
  * [36] Giorgos Tolias, Yannis Avrithis, and Hervé Jégou.  Image search with selective match kernels: aggregation across single and multiple images.  International Journal of Computer Vision, 116(3):247–261, 2016.
  * [37] Giorgos Tolias, Tomas Jenicek, and Ondřej Chum.  Learning and aggregating deep local descriptors for instance-level recognition.  In Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part I 16, pages 460–477. Springer, 2020.
  * [38] Prune Truong, Martin Danelljan, Luc V Gool, and Radu Timofte.  Gocor: Bringing globally optimized correspondence volumes into your neural network.  Advances in Neural Information Processing Systems, 33:14278–14290, 2020.
  * [39] Prune Truong, Martin Danelljan, and Radu Timofte.  Glu-net: Global-local universal network for dense flow and correspondences.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 6258–6268, 2020.
  * [40] Prune Truong, Martin Danelljan, Radu Timofte, and Luc Van Gool.  Pdc-net+: Enhanced probabilistic dense correspondence network.  arXiv preprint arXiv:2109.13912, 2021.
  * [41] Prune Truong, Martin Danelljan, Fisher Yu, and Luc Van Gool.  Warp consistency for unsupervised learning of dense correspondences.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 10346–10356, 2021.
  * [42] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  Advances in neural information processing systems, 30, 2017.
  * [43] Philippe Weinzaepfel, Thomas Lucas, Diane Larlus, and Yannis Kalantidis.  Learning super-features for image retrieval.  arXiv preprint arXiv:2201.13182, 2022.
  * [44] Tobias Weyand, Andre Araujo, Bingyi Cao, and Jack Sim.  Google landmarks dataset v2-a large-scale benchmark for instance-level recognition and retrieval.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2575–2584, 2020.
  * [45] Hui Wu, Min Wang, Wengang Zhou, Yang Hu, and Houqiang Li.  Learning token-based representation for image retrieval.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 2703–2711, 2022.
  * [46] Lihe Yang, Wei Zhuo, Lei Qi, Yinghuan Shi, and Yang Gao.  Mining latent classes for few-shot segmentation.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 8721–8730, 2021.
  * [47] Min Yang, Dongliang He, Miao Fan, Baorong Shi, Xuetong Xue, Fu Li, Errui Ding, and Jizhou Huang.  Dolg: Single-stage image retrieval with deep orthogonal fusion of local and global features.  In Proceedings of the IEEE/CVF International conference on Computer Vision, pages 11772–11781, 2021.
  * [48] Zhongyan Zhang, Lei Wang, Luping Zhou, and Piotr Koniusz.  Learning spatial-context-aware global visual feature representation for instance image retrieval.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 11250–11259, 2023.
  * [49] Dengyong Zhou, Olivier Bousquet, Thomas N Lal, Jason Weston, and Bernhard Schölkopf.  Learning with local and global consistency.  In Advances in neural information processing systems, pages 321–328, 2004.
  * [50] Dengyong Zhou, Jason Weston, Arthur Gretton, Olivier Bousquet, and Bernhard Schölkopf.  Ranking on data manifolds.  Advances in neural information processing systems, 16:169–176, 2004.
  * [51] Yunquan Zhu, Xinkai Gao, Bo Ke, Ruizhi Qiao, and Xing Sun.  Coarse-to-fine: Learning compact discriminative representation for single-stage image retrieval.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 11260–11269, 2023.

|  Guoyuan An is now a Ph.D. candidate in Computer Science at KAIST. He earned
his B.S. degrees in Industrial Engineering and Computer Science from Inha
University in 2018, followed by a M.S. degree in Computer Science from KAIST
in 2020. His research focuses on large-scale image search, deep learning, and
human-computer interaction.
---|---
|  Yuchi Huo is an assistant professor under the ”Hundred Talent Program” in
State Key Lab of CAD&CG, Zhejiang University. His research interests are in
rendering, deep learning, image search, and computational optics, which aim
for the realization of next-generation neural rendering pipelines and
physical-neural computation.
---|---
|  Sung-Eui Yoon (Senior Member, IEEE) received the B.S. and M.S. degrees in
computer science from Seoul National University, Seoul, South Korea, in 1999
and 2001, respectively, and the Ph.D. degree in computer science from the
University of North Carolina at Chapel Hill, Chapel Hill, NC, USA, in 2005\.
He is currently a Professor with the Korea Advanced Institute of Science and
Technology, Daejeon, South Korea. He was a Postdoctoral Scholar with Lawrence
Livermore National Laboratory, Livermore, CA, USA. He has authored or
coauthored more than 70 technical papers in top journals and conference
related to graphics, vision, and robotics, a monograph on real-time massive
model rendering with other three coauthors in 2008, and recently an online
book on Rendering in 2018\. His research interests include rendering, image
search, and motion planning spanning graphics, vision, and robotics. He also
gave numerous tutorials on ray tracing, collision detection, image search, and
sound source localization in premier conferences like ACM SIGGRAPH, IEEE
Visualization, CVPR, and ICRA. He was the conference Co-chair and Paper Co-
chair for ACM I3D 2012 and 2013 respectively. Some of his papers was the
recipient of the Test-of-Time Award, a distinguished Paper Award, and a few
invitations to IEEE Transaction on Visualization and Graphics. He is a Senior
Member of ACM.
---|---