# Incremental Semantic Localization using
Hierarchical Clustering of Object Association Sets

Lan Hu×,∗, Zhongwei Luo×, Runze Yuan×, Yuchen Cao×, Jiaxin Wei×,
Kai Wang+ and Laurent Kneip× ×Mobile Perception Lab, SIST, ShanghaiTech
University.
{hulan,luozhw,
yuanrz}<EMAIL_ADDRESS>Institute of Microsystem and Information Technology, Chinese Academy of
Sciences and University of Chinese Academy of Sciences. +Application Lab,
Huawei Incorporated Company, P.R. China.
<EMAIL_ADDRESS>
###### Abstract

We present a novel approach for relocalization or place recognition, a
fundamental problem to be solved in many robotics, automation, and AR
applications. Rather than relying on often unstable appearance information, we
consider a situation in which the reference map is given in the form of
localized objects. Our localization framework relies on 3D semantic object
detections, which are then associated to objects in the map. Possible pair-
wise association sets are grown based on hierarchical clustering using a merge
metric that evaluates spatial compatibility. The latter notably uses
information about relative object configurations, which is invariant with
respect to global transformations. Association sets are furthermore updated
and expanded as the camera incrementally explores the environment and detects
further objects. We test our algorithm in several challenging situations
including dynamic scenes, large view-point changes, and scenes with repeated
instances. Our experiments demonstrate that our approach outperforms prior art
in terms of both robustness and accuracy.

##  I Introduction

Visual localization estimates the 6 Degree-of-Freedom (DoF) pose of a camera
view observing a 3D scene. It plays an essential role in a wide range of
practical applications, such as robotics, augmented reality, and smart
vehicles. One of the major challenges behind localization revolves around the
reliable recognition of places under both a wide variety of environmental
conditions that non-uniformly affect the appearance of the scene, as well as a
wide range of viewpoints. For long-term outdoor autonomous navigation, there
are many disturbing factors such as seasonal changes or weather conditions,
natural or artificial illumination variations, and varying positions of for
example cars and persons. To deal with such challenges, the stability of
traditional, hand-crafted low-level features is generally deemed insufficient.

With the development of deep neural networks, there nowadays exist several
novel algorithms able to produce stable higher-level features [55] or directly
predict the camera pose [38]. Many such algorithms empower platforms with a
strong basis for long-term navigation and 3D scene understanding, and support
operation in both indoor and outdoor environments. Compared against outdoor
localization, the indoor localization problem is significantly easier owing to
the possibility of using a depth camera and thus further reduce the influence
of appearance changes. However, benefits in both environments may be obtained
from object detection [44, 43] or instance segmentation networks [8, 5, 25],
both of which produce rich and discriminative semantic information about the
environment. Compared against low-level point features, object landmark
detections are conceived to be much more stable under a variety of
illumination and viewpoint changes.

Human beings are excellent at place recognition and localization by utilizing
semantic landmarks and their relationships. For example, given a view of a
corridor and the respective arrangement of doors, we may easily know in which
part of a building we are located. The more landmarks are observed, the more
confidently and accurately we can locate ourselves. Our framework employs a
similar strategy and aims at localization by identifying a subset of objects
in a map with a semantically and spatially consistent pair-wise association to
a locally measured set of objects. The confidence of a pair-wise association
set depends on the similarity of the assigned object sets expressed in terms
of stable properties such as appearance-independent features and relative
spatial object arrangement. The considered information is invariant with
respect to viewpoint and illumination variations. The approach works
incrementally and expands the set of hypothesized association sets as the
camera explores the environment and detects new objects. Association sets are
furthermore grown based on hierarchical clustering using a merge metric that
depends on the said spatial compatibilities. Once a dominant pair-wise
association set has been confirmed, a subsequent alignment of the assigned
objects reveals the absolute camera position and orientation.

Our contributions are summarized as follows:

  * •

A light-weight, semantic landmark based relocalization solution for indoor
scenes.

  * •

The method constructs pair-wise association sets between local object
measurements and a prior given object-level map based on hierarchical
clustering. Confidence scores are given by considering consistency in terms of
semantics and spatial relative arrangements.

  * •

The method works incrementally and expands the association sets as more
objects are being detected.

  * •

A diverse set of experiments verifies the effectiveness of our proposed
solution as well as an obvious improvement over the previous state-of-the-art.

##  II Related Work

Point-level features for relocalization: The most common relocalization or
place recognition methods in SLAM exploit local invariant key-points such as
SIFT [39] or ORB [37]. The most straightforward solution is given by a direct
establishment of 2D-3D matches between a query image and 3D points in a map,
followed by the execution of a robust camera resectioning algorithm for
geometric verification [15]. Alternatively, the scalability of the place
recognition module may be increased by adding the bag-of-words approach [3],
likely in conjunction with an inverted index for efficient image retrieval
[40]. However, the approach remains highly sensitive to illumination or even
camera view-point changes, which may impact significantly on the appearance of
low-level features. In an aim to provide improved invariance over hand-
designed features, more recent works have proposed learned 2D feature point
extractors [48, 59, 12]. However, Jin et al. [24] point out that the
performance of traditional features such as SIFT is still much more robust and
stable than learned features in many practical situations. If available, depth
information can be used to extract 3D descriptors [27, 45, 60, 18, 26].
Sometimes, depth-supported approaches still fail in the presence of strong
viewpoint or appearance changes if lacking visual or structural overlap.

Another popular strategy for point-based localization [29, 36, 51] leverages
semantic information to re-weight or discard ambiguous features [28] and
increase the quality of the 2D-3D correspondences. Similarly, bag-of-words
representations can be enhanced by combining semantic local features [3].
While there are many ways of including semantics as auxiliary information,
they will not change the fact that point-level features remain highly
sensitive to illumination or view-point changes.

High-level features for relocalization: Rather than using the features of key-
points, the community has proposed several alternative directions for place
recognition such as learning tailored representations of query data [36, 52,
1, 9, 2, 47, 50] or directly regressing the camera pose of the query data by a
neural network [6, 53, 41, 32, 38, 13]. The main drawback of these approaches
is that they need to be retrained for each dataset in order to get
satisfactory and stable results. Furthermore, these methods have insufficient
robustness for stand-alone operation as they depend on post-processing steps
to verify geometric or photometric consistency. Their preferred application
scenario is therefore given by outdoor long-term navigation with low accuracy
requirements. Indoor localization, on the other hand, requires much more
accurate estimation and may additionally suffer from challenges such as
differing sensors for the construction of the global map prior and the online
measurements.

Segmatch [14] adopts an object feature extraction and matching strategy to
find corresponding objects between the local and the global map. The
relocalization is finalized by calculating the camera-to-model pose from the
identified object correspondences. However, object shape differences caused by
camera viewpoint variations easily impact on the stability of the detected
features, and thus the overall relocalization quality. Further works that
treat objects as landmarks for relocalization are given by [30] and [31], who
rely on 3D semantic cube consistency. There are several more examples of works
relying on semantic information [14, 49, 16, 61]. However, as for previous
examples, they fail to exploit object-to-object relationships for
relocalization.

The most related work to ours is given by Liu et al. [33], who pose the
relocalization problem as a graph matching problem in which objects are taken
as nodes to build a graph topology [17]. They use a random walk method to
record a node’s semantic information as a descriptor for object association.
By counting the number of matched descriptors, they choose the top-k objects
from the global map and set them as potential correspondences. While highly
related, the purely semantic descriptor makes the algorithm easily fail if the
environment contains several repeated instances of semantically comparable
object clusters. In contrast to our method, the algorithm depends on a
predefined walk length which makes the algorithm unsuitable for the
incremental relocalization. It might fail with high probability in the
situations which contain multiple same category instances since that the
predefined walk length will limit the ability to accurately describe the
object spatial distribution.

##  III Preliminaries

Notations and problem definition: The global semantic map is represented by
the set $\mathbf{A}=\\{\mathbf{A}_{i}\\}_{i=1,\cdots,N_{A}}$, where
$\mathbf{A}_{i}=\\{\mathbf{P}^{A}_{i},s^{A}_{i},\mathbf{m}^{A}_{i}\\}$ are
object information bags and $N_{A}$ is the number of objects. $\mathbf{A}_{i}$
contains an object point set $\mathbf{P}^{A}_{i}$, semantic label $s^{A}_{i}$,
and object position $\mathbf{m}^{A}_{i}$. Similarly,
$\mathbf{B}=\\{\mathbf{B}_{i}\\}_{i=1,\cdots,N_{B}}$ contains the objects in
the local map. Let $\mathbf{D}=\\{\mathbf{D}_{k}|k=1,\cdots,K\\}$ denote the
set of all hypothesized object association sets. $K$ is the number of
association sets which has a predefined upper bound to limit computational
load. Each
$\mathbf{D}_{k}=\\{(\alpha_{i},\beta_{i})|_{i=1,\cdots,|\mathbf{D}_{k}|},v_{k}\\}$
contains a set of pair-wise correspondences indicating associations between
the $\alpha_{i}$-th global object and the $\beta_{i}$-th local object.
$|\mathbf{D}_{k}|$ is the number of pair-wise object correspondences, and
$v_{k}$ indicates the score (or vote) for a pair-wise association set. The
objective of our object-based localization is given by estimating the
transformation that aligns the current local observation with objects in the
global map, that is

$\mathbf{x}^{*}=\arg\max_{\mathbf{x}}p(\mathbf{B},\mathbf{D}|\mathbf{A},\mathbf{x}),$
(1)

where $\mathbf{x}$ is the camera pose parameter. It is difficult to solve this
problem directly, as the correspondences are a latent variable for which no
prior information is given. General techniques for semantic relocalization are
therefore given by first finding the association set $\mathbf{D}$ (i.e. the
correspondences), followed by estimating the camera pose.

Hierarchical clustering: Also known as hierarchical cluster analysis, the
algorithm groups compatible samples into clusters. Unlike k-means and GMM
clustering, it does not require prior knowledge about the number of clusters.
Strategies for hierarchical clustering generally fall into two categories:
agglomerative and divisive. Here we only use the agglomerative strategy. It
starts by treating each sample as a separate cluster. Then, it repeatedly
executes the following two steps: (1) identify two clusters that can be
merged, and (2) conditionally merge the two clusters if a merge criterion is
met. The iterative process continues until no more clusters can be merged. In
most hierarchical clustering methods, compatibility is expressed by a metric
such as the distance between pairs of samples. The linkage criterion then
decides if clusters should be merged based the value of the compatibility
metric. For more information about hierarchical clustering, please refer to
[34]. Note that in our case, clusters are given by association sets, and
samples are given by individual pair-wise associations.

##  IV Methodology

The operation of our algorithm is illustrated in Figure 1. Using the
continuous input of an RGBD camera and 3D object detections from RGB and depth
channels, a front-end module incrementally constructs a local object-level
map. The latter is expressed in the form of a fully connected graph where
nodes represent detected objects and edges encode relative spatial properties.
Starting from an initial graph, object classes and shape descriptors are used
in order to initialize association sets containing a single pairwise
association between a detected object and a corresponding landmark in the
global map. During hierarchical clustering, the relative spatial information
between pairs of measured objects and pairs of corresponding objects in the
global map is then used to construct a merge metric and merge criterion for
association sets. The hierarchical clustering is rerun when each time the
camera measures a new set of objects, thus causing the association sets to
grow further and become more distinctive.

In the following, we will introduce the absolute and relative object
information used during the initialization and clustering of the association
sets, followed by the details of the hierarchical clustering itself. We
conclude with details on the incremental update, the convergence criterion,
and the actual pose recovery.

###  IV-A Absolute and relative object properties

Absolute object position: In contrast to 2D feature point locations—which are
potentially very accurate—the 3D position of an object is largely impacted by
the partiality of the measurement. While we often set an object position
$\mathbf{m}_{i}$ to the mean of an object’s measured points, the
characterisation of its uncertainty remains a challenging problem. This is
especially true for large objects for which entire shape observations during
normal camera navigation rarely occur. Absolute position uncertainty has an
immediate impact on relative object properties such as the distance between
two objects, which will be used later to construct our merge metric. By
assuming a maximum object shape size, this uncertainty can be bounded by a
predefined threshold. Note that similar assumptions are common in related
work. TEASER[56] for example exploits a similar assumption in order to bound
the influence of outliers during 3D-3D registration.

Object descriptor: We extract an object shape descriptor from each object
point cloud $\mathbf{P}_{i}$, which maintains resilience against varying
appearance information. Obtaining accurate object descriptors is substantially
more difficult than point feature description and influenced by angles of
observation, depth or segmentation noise, and occlusions. Traditional hand-
crafted features cannot meet requirements in terms of expressiveness and
stability. We typically employ deep neural networks for object shape encoding,
such as DGCNN [54], Pointnet++[42] and VoxNet[35]. We choose VoxNet trained on
the Scan2CAD dataset owing to its strong noise mitigation abilities.
Representative and discriminative features—denoted $\mathbf{f}_{i}$—are
obtained by using the triplet loss. The object class $s_{i}$ is used along
with the object shape descriptor $\mathbf{f}_{i}$ in order to establish the
initial, singleton association sets.

Relative object position: We use object relative position information in order
to express the objects’ spatial distribution and construct a merge metric for
our hierarchical clustering algorithm. We simply use the relative distance
between two objects, which is invariant with respect to the camera pose or the
frame of reference. For two objects $\mathbf{B}_{i}$ and $\mathbf{B}_{j}$, the
relative distance is simply given by
$d^{B}_{i,j}=\|\mathbf{m}^{B}_{i}-\mathbf{m}^{B}_{j}\|$.

Figure 1: The Pipeline of the semantic incremental localization. We build the
instance-level map and construct the fully connected graph. For each new
observation, we first find its potential correspondences in the global, and
then add to the existing association set. For each new coming observation, we
implement the clustering algorithm to update the associations. Each
$\\{\cdot\\}$ in the figure is one association set.

###  IV-B Hierarchical clustering for association set growing

Initialization: Our purpose is to relocalize the camera, which we do by
associating the current object observations with object instances in the
global map. We start by creating a set of hypothetical singleton association
sets $\mathbf{D}^{0}=\\{\mathbf{D}^{0}_{k}|k=1,\cdots,K_{0}\\}$ by using
object classes and shape descriptors to find individual matches for each
detected object. For each potential match $(\alpha_{i},\beta_{i})$, the
semantic labels need to be the same (i.e. $s_{\alpha_{i}}=s_{\beta_{i}}$), and
the feature distance needs to be within a bound $\delta$ (i.e.
$\|f_{\alpha_{i}}-f_{\beta_{i}}\|<\delta$). In order to handle situations of
significant differences for example caused by severe partiality of an object’s
observation, $\delta$ is typically set to a relatively large value $0.5$. The
scores of each singleton association set will be initialized to $0$. Note
that—owing to potentially repeated occurrence of identical semantic labels—a
single local instance may initially form multiple singleton association sets.

Merge metric and merge criterion: After initialization, the algorithm will
start to merge and generate new association sets by hierarchical clustering.
The purpose of hierarchical clustering is to implicitly eliminate wrong
associations by recursively finding pairs of spatially compatible association
sets with maximum cardinality. All possible pairs of association sets will be
recursively explored. The quality of an association set is determined by
implementing a scoring mechanism alongside the clustering. In classical
clustering algorithms, one object node will only belong to one cluster center.
In our implementation, the same association set could merge multiple times
with other association sets if they satisfy the merge criterion.

The merge metric is formed as follows. For any two potential merge candidates
$\mathbf{D}_{k_{1}}=\\{(\alpha_{i},\beta_{i})|_{i=1,\cdots,|\mathbf{D}_{k_{1}}|},v_{k_{1}}\\}$
and
$\mathbf{D}_{k_{2}}=\\{(\alpha_{j},\beta_{j})|_{j=1,\cdots,|\mathbf{D}_{k_{2}}|},v_{k_{2}}\\}$,
we calculate the distance between each new pair of objects in both the local
and the global map. Note that new pairs of objects are defined by taking one
element from each set such that neither the first element is contained in the
second set, nor the second is contained in the first. We then take the
distance ratio

$h(\alpha_{i},\alpha_{j},\beta_{i},\beta_{j})=min\left(d^{B}_{\beta_{i},\beta_{j}}/d^{A}_{\alpha_{i},\alpha_{j}},d^{A}_{\alpha_{i},\alpha_{j}}/d^{B}_{\beta_{i},\beta_{j}}\right),$
(2)

where $\alpha_{i}$ and $\alpha_{j}$ are the object indices in the global map,
and $\beta_{i}$ and $\beta_{j}$ are the object indices in the local map.
$d^{A}_{\alpha_{i},\alpha_{j}}$ and $d^{B}_{\beta_{i},\beta_{j}}$ are the
object distances in the global and the local map, respectively. The merge
metric expresses compatibility within a new pair of objects and has an upper
bound of 1. The $D_{k_{1}}$ and $D_{k_{2}}$ are merged if

$l(D_{k_{1}},D_{k_{2}})==|D_{k_{1}}|*|D_{k_{2}}|,$ (3)

where

$l(D_{k_{1}},D_{k_{2}})=\sum_{(\alpha_{i},\beta_{i})\in
D_{k_{1}}(\alpha_{j},\beta_{j})\in
D_{k_{2}}}I(\gamma<h(\alpha_{i},\alpha_{j},\beta_{i},\beta_{j})).$ (4)

$I(\gamma<h(\alpha_{i},\alpha_{j},\beta_{i},\beta_{j}))$ is an indicator
function. If $\gamma<h(\alpha_{i},\alpha_{j}\beta_{i},\beta_{j})$, then
$I(\cdot)=1$, else $I(\cdot)=0$. In other words, association sets are only
merged if they are both free of outliers and all new object pairs have a
relative spatial arrangement that is consistent with their respective
associated objects from the global map. The score of the new association set
is

$v_{k_{1}}+v_{k_{2}}+\sum_{(\alpha_{i},\beta_{i})\in
D_{k_{1}}(\alpha_{j},\beta_{j})\in
D_{k_{2}}}h(\alpha_{i},\alpha_{j},\beta_{i},\beta_{j}).$ (5)

Update: As the camera keeps exploring the environment, new object detections
may occur. This will trigger a complete new iteration in which 1) the new or
redetected instances will again be used to form singleton association sets
that are added to the complete set of all association sets, and 2) another
round of hierarchical clustering will be issued.

Avoiding redundancy: By default, the original association sets are not
removed, even if they have been merged. This is because they could in
principle form new interesting clusters once new object detections come in.
However, in order to avoid redundant calculations, we mark clusters that have
already been merged such that they will no longer be considered for merging
during future updates. Note furthermore that one cluster may already contain
another cluster, in which case no new object pairs can be formed, and no
merging will be attempted. If a duplicate set is detected, we will manually
remove the one with smaller score. We will furthermore remove sets that have
not seen a single merge since more than two update steps. To conclude, we
speed up execution by only taking the first top $K=10*n$ association sets into
the next round of clustering, where $n$ is the number of instances in the
global map.

###  IV-C Camera pose recovery

Note that global localization may be considered unambiguous and successful as
soon as only a single association set with dominant score remains. We estimate
the pose of the camera by running globally optimal ICP [57] over the point-
sets obtained by individually concatenating the point sets from the local and
the global map for each corresponding object and then refine by using robust
ICP[21].

##  V Experimental results

In the following, we briefly introduce the baseline methods that we compare
against, the datasets on which we evaluate the relocalization, the evaluation
metric, as well as all experimental results.

###  V-A Baseline methods

####  V-A1 Feature-based methods.

For feature-based registration methods, we render several sub-maps from the
global map. We sample points with grid step of $0.3$m in the global map and
find their neighbors within a radius of $1.5$ meters to form one sub-map.

  * •

FPFH [45] and FCGF [10]: State-of-the-art hand-crafted and learned geometric
descriptors used for point cloud matching. We densely extract these
descriptors and train a custom shape vocabulary on the global map. We also
compare the traditional feature SIFT and use the corresponding depth points
for later camera pose recovering.

  * •

Semantic visual localization [47]: For simplicity, we denote this work SVL. We
reimplemented the method which uses a variational auto-encoder to learn the
representation of point observations. We randomly select 20 scenes from the
ScanNet dataset and fuse several key-frames to obtain local semantic maps for
training, and test its performance on other ScanNet scenes.

Note that, in comparison to object-level relocalization, the above algorithms
utilize the background information. As a result, they cannot be used if the
pre-built map does not store this information or if the map is built by
another sensor.

####  V-A2 Object-level relocalization.

Object-level relocalization is done by using object features such as shape
descriptors and—as done in our proposed method—relative object arrangements.

  * •

SegMatch: SegMatch[14] is a place recognition algorithm based on the matching
of 3D semantic segments. One-to-one correspondences are notably found by
object classification. The code is obtained from an open-source framework and
applied to indoor environments.

  * •

Random walk descriptors: Random walk descriptors make use of local topological
graphs of object instances [33]. The main shortcoming of the method is the
requirement for a predefined walk length which is not suitable for the
incremental relocalization. We denote our re-implementation of this method as
random-walk, and use the original parameters of [33].

Figure 2: Visualization of clustering results on two different global maps.
Owing to the existence of a unique semantic object in the global scannet map,
using the latter leads to immediate convergence at $t_{0}$. For the CAD based
map, the ambiguity needs further updates to be resolved.

###  V-B Datasets and evaluation

For the sake of a fair comparison, all algorithms use the same, previously
outlined pose recovery technique. Common assumption with known ground
plane[20, 58, 46] is made to alleviate the computation of camera pose
estimation. A successful retrieval is defined if the rotation and translation
errors are below $15^{\circ}$ and $0.5$ meters, respectively. We test our
algorithm on the ScanNet[11] and SSS[7] datasets. ScanNet is a dataset with
real images observing various indoor scenes. SSS provides indoor scenes in day
and night situations which are rendered by Blender. Both SSS and ScanNet have
two global maps: a geometrical object-level reconstruction, and a semantic
model map in which the objects are replaced by their corresponding CAD models.
The ground truth CAD models of ScanNet are taken from the Scan2CAD [4]
dataset. Models of the SSS dataset are exported from Blender.

It is intuitively clear that owing to the robustness of instance-level
segmentation, object-level relocalization is much less affected by view-point
or illumination changes than key-point feature-based relocalization. We
validated this statement on the SSS dataset room5, a relatively large indoor
scene that extends over two rooms. We rendered both day and night sequences
and defined orbiting camera trajectories in each room that capture an
abundance of views of an identical place but under very different viewing
angles. Through our tests, we were able to verify that instance-level
segmentation results are much more robust than feature point detections.

###  V-C Front-end

We use BlendMask [8] to provide instance-level semantic segmentation from RGBD
images. Note however that RGB information is not used during any later stages
of our relocalization pipeline, which is why the use of other instance-level
segmentation networks suitable for pure depth data [23] could easily extend
our approach to scenarios in which no regular images are being captured. Our
local instance-level map is built using an approach inspired by the works of
Grinwald et al. [19] and Hu et al. [22]. While instance-level segmentation
frameworks generally have good robustness against illumination or view-point
variations, they still pose challenges in the form of occasionally unstable
performance, wrong or even missing detections, and bad segmentation masks. The
influence of the segmentation quality on semantic relocalization is well
documented in Liu et al. [33].

###  V-D Visualizing the effect of hierarchical clustering

Our hierarchical clustering algorithm grows and scores association sets. Its
inherent functionality makes it suitable to gradually account for the results
of incremental local mapping, and thereby identify an association set with
high confidence. To confirm its ability to gradually localize the camera with
higher confidence, let us see the scores of the top two association sets.
Figure 2 visualizes incremental association sets on ScanNet scene
scene0475_00, which contains multiple instances of the same object.

As indicated in Figure 2, the scores for the possible association set will
become increasingly discriminative as more objects are being observed. In
particular, the correct association set will be quickly identified if the
camera observes an object that is unique in one of the maps.

Figure 3: Ablation study. Here we analysis the performance influence from
clustering threshold, the object number in the local map and their
corresponding time costing.

###  V-E Ablation study

Both the number and the position uncertainty of objects will impact on the
relocalization quality. Results are further depending on the chosen value for
$\gamma$. We therefore perform an ablation study over $\gamma$ and the number
of objects on ScanNet scene0247_01 and scene0365_01.

Success is given if one of the choosen top-k association sets for camera pose
recovering is the correct location, where top-k $\in[1,5,10,15,20]$. The
larger top-k will bring higher success rate. Figure 3 shows the experiment
results. The first row indicates the relocalization success ratio, while the
second row analyses the computational cost. Choosing only the top-1
association set for pose recovering will obviously lead to the lowest success
ratio, whereas as soon as top-k $\geq 10$, results become very identical. As
the left column shows, a tighter $\gamma$-threshold will generally lead to
higher localization success ratio, thought if the threshold is too tight, the
success ratio will again decrease. The threshold should be set smaller than
0.9, and—to take more potential associations into account—it is set to $0.8$
in all remaining experiments. Note that the indicated time cost contains the
time for both the hierarchical clustering and pose recovery. The time depends
on the number of considered association sets, and is lowest if top-k $=1$. It
is furthermore obvious that as the threshold $\gamma$ becomes tighter, the
time cost will decrease as fewer association sets are generated. The right
column of Figure 3 presents the analysis on how the number of objects
influences the success rate and the computational cost. More objects will
clearly increase the relocalization success rate at the cost of higher
computational demands.

Figure 4: Comparison against alternative methods.

###  V-F Comparison against alternative methods

To conclude, we compare our algorithm against all baseline algorithms on
several datasets including different illumination conditions and three
different types of global map: the geometrically reconstructed map, the cad
model map, and an extended cad model map in which objects have been moved
(denoted dynamic map). To obtain the dynamic map, we take two steps. First, we
delete some objects from the global map. Second, we randomly move some of the
remaining objects to new positions. We make sure that at least $30\%$ of the
objects are moved to new places. A total of $7$ different sequences with
multiple same objects are analyzed, which are room5 day and room5 night for
our day-night experiments, and $5$ ScanNet sequences (scene0475_00,
scene0365_01, scene0247_01, scene0603_01 and scene0250_01) for all other
experiments. Results are averaged over more than $3000$ relocalization
attempts. Relocalization attempts are started from uniform randomly picked
key-frames along each sequence. For each starting point, we will generate
three relocalization attempts. The first one happens as soon as more than $2$
objects are observed. The second and third localization attempts happen by
taking an additional $15$ or $30$ key-frames into account.

Figure 4 shows the average results for the correct localization rate or recall
over the tolerated translation error (row 1, top-$k$=10), as well as the
considered number $k$ of top-ranked association sets (row 2, error tolerance:
$0.5$ m and $15^{\circ}$). The first column shows the relocalization result
during night where the global map has been reconstructed during the day. As
can be observed, our method performs very well while traditional point-feature
based methods such as SIFT are unable to deal with the variation. Here we did
not present the result of 3D feature-based methods, but we show in the second
column, because they will not be affected by the illumination changes. The
next three columns are the results referring to the different types of global
map. Overall, we can observe that our object-level relocalization has better
performance:

  * •

As expected, the hand-designed FPFH feature performs worse. The 3D point map
contains many repeated, similar local structures, which causes the hand-
designed feature FPFH to be not representative enough for relocalization. FPFH
perform even worse when the global map is represented by a CAD model, which
typically leads to differing point distributions in the locally observed map.

  * •

Our experimental results indicate that SegMatch is troubled by multiple
similar instances and the lack of shape differences, since it extracts several
features for each instance and then uses a random forest to find an instance
association between the local observation and the global map. Such strategy is
easily influenced by the camera view and the object class, where different
camera views will result in feature dissimilarities, and multiple same-class
objects hold the ability to confuse the algorithm and cause the wrong final
association decisions.

  * •

Learning-based methods, such as SVL and FCGF, have very close performance and
FCGF obtains better performance than our algorithm when top-k is less than $4$
(cf. fourth column of Figure 4, which occurs in the dynamic situation). This
may be because SVL and FCGF rely on a lot of background information rather
than just object information. However, compared against our light-weight
algorithm, the learning-based alternative needs larger computation resources
and will thus be limited by the platform.

  * •

The most related work to ours is random-walk, which also exploits object-
related spatial distributions. However, it depends on a predefined walk length
and does not score each association set. Our algorithm on the other hand
adopts an incremental clustering strategy, and scores all association sets.
The more observations, the more certain the correct association will be.

The dynamic situation is exposed in the fourth column. Most algorithms perform
worse in this scenario. However, our algorithm still provides competitive
performance especially when the local observed object number is larger.

##  VI Conclusion

We present a novel global localization framework that is conceptually simple
and relies on object detections and associations with objects in a global map.
The overall success rate of the method is high and it easily outperforms
existing methods as soon as sufficiently many objects can be detected,
irrespectively of their class. The method operates very fast and is
particularly well suited in conjunction with incremental, object-level mapping
front-ends. We believe it could be of broad interest in object-level SLAM
frameworks.

## References

  * [1] M. Angelina Uy and G. Hee Lee.  Pointnetvlad: Deep point cloud based retrieval for large-scale place recognition.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4470–4479, 2018.
  * [2] R. Arandjelovic, P. Gronat, A. Torii, T. Pajdla, and J. Sivic.  Netvlad: Cnn architecture for weakly supervised place recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5297–5307, 2016.
  * [3] R. Arandjelović and A. Zisserman.  Visual vocabulary with a semantic twist.  In Asian Conference on Computer Vision, pages 178–195. Springer, 2014.
  * [4] A. Avetisyan, M. Dahnert, A. Dai, M. Savva, A. X. Chang, and M. Nießner.  Scan2cad: Learning cad model alignment in rgb-d scans.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2614–2623, 2019.
  * [5] D. Bolya, C. Zhou, F. Xiao, and Y. J. Lee.  Yolact: Real-time instance segmentation.  In Proceedings of the IEEE international conference on computer vision, pages 9157–9166, 2019.
  * [6] E. Brachmann, A. Krull, S. Nowozin, J. Shotton, F. Michel, S. Gumhold, and C. Rother.  Dsac-differentiable ransac for camera localization.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 6684–6692, 2017.
  * [7] Y. Cao, L. Hu, and L. Kneip.  Representations and benchmarking of modern visual slam systems.  Sensors, 20(9):2572, 2020.
  * [8] H. Chen, K. Sun, Z. Tian, C. Shen, Y. Huang, and Y. Yan.  Blendmask: Top-down meets bottom-up for instance segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8573–8581, 2020.
  * [9] Z. Chen, O. Lam, A. Jacobson, and M. Milford.  Convolutional neural network-based place recognition.  arXiv preprint arXiv:1411.1509, 2014.
  * [10] C. Choy, J. Park, and V. Koltun.  Fully convolutional geometric features.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 8958–8966, 2019.
  * [11] A. Dai, A. X. Chang, M. Savva, M. Halber, T. Funkhouser, and M. Nießner.  Scannet: Richly-annotated 3d reconstructions of indoor scenes.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5828–5839, 2017.
  * [12] D. DeTone, T. Malisiewicz, and A. Rabinovich.  Superpoint: Self-supervised interest point detection and description.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pages 224–236, 2018.
  * [13] M. Ding, Z. Wang, J. Sun, J. Shi, and P. Luo.  Camnet: Coarse-to-fine retrieval for camera re-localization.  In Proceedings of the IEEE International Conference on Computer Vision, pages 2871–2880, 2019.
  * [14] R. Dubé, D. Dugas, E. Stumm, J. Nieto, R. Siegwart, and C. Cadena.  Segmatch: Segment based loop-closure for 3d point clouds.  arXiv preprint arXiv:1609.07720, 2016.
  * [15] M. A. Fischler and R. 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.
  * [16] V. Gaudillière, G. Simon, and M.-O. Berger.  Camera relocalization with ellipsoidal abstraction of objects.  In 2019 IEEE International Symposium on Mixed and Augmented Reality (ISMAR), pages 8–18. IEEE, 2019.
  * [17] A. Gawel, C. Del Don, R. Siegwart, J. Nieto, and C. Cadena.  X-view: Graph-based semantic multi-view localization.  IEEE Robotics and Automation Letters, 3(3):1687–1694, 2018.
  * [18] Z. Gojcic, C. Zhou, J. D. Wegner, and A. Wieser.  The perfect match: 3d point cloud matching with smoothed densities.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5545–5554, 2019.
  * [19] M. Grinvald, F. Furrer, T. Novkovic, J. J. Chung, C. Cadena, R. Siegwart, and J. Nieto.  Volumetric instance-aware semantic mapping and 3d object discovery.  IEEE Robotics and Automation Letters, 4(3):3037–3044, 2019.
  * [20] L. Hu and L. Kneip.  Globally optimal point set registration by joint symmetry plane fitting.  Journal of Mathematical Imaging and Vision, pages 1–19, 2021.
  * [21] L. Hu, J. Wei, L. Kneip, et al.  Point set registration with semantic region association using cascaded expectation maximization.  2021\.
  * [22] L. Hu, W. Xu, K. Huang, and L. Kneip.  Deep-slam++: Object-level rgbd slam based on class-specific deep shape priors.  arXiv preprint arXiv:1907.09691, 2019.
  * [23] L. Jiang, H. Zhao, S. Shi, S. Liu, C.-W. Fu, and J. Jia.  Pointgroup: Dual-set point grouping for 3d instance segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4867–4876, 2020.
  * [24] Y. Jin, D. Mishkin, A. Mishchuk, J. Matas, P. Fua, K. M. Yi, and E. Trulls.  Image matching across wide baselines: From paper to practice.  arXiv preprint arXiv:2003.01587, 2020.
  * [25] J. W. Johnson.  Adapting mask-rcnn for automatic nucleus segmentation.  arXiv preprint arXiv:1805.00500, 2018.
  * [26] W. Junyi and Q. Yue.  Camera relocalization using deep point cloud generation and hand-crafted feature refinement.  In 2021 IEEE International Conference on Robotics and Automation (ICRA), pages 5891–5897. IEEE, 2021.
  * [27] M. Khoury, Q.-Y. Zhou, and V. Koltun.  Learning compact geometric features.  In Proceedings of the IEEE International Conference on Computer Vision, pages 153–161, 2017.
  * [28] J. Knopp, J. Sivic, and T. Pajdla.  Avoiding confusing features in place recognition.  In European Conference on Computer Vision, pages 748–761. Springer, 2010.
  * [29] N. Kobyshev, H. Riemenschneider, and L. Van Gool.  Matching features correctly through semantic understanding.  In 2014 2nd International Conference on 3D Vision, volume 1, pages 472–479. IEEE, 2014.
  * [30] J. Li, D. Meger, and G. Dudek.  Semantic mapping for view-invariant relocalization.  In 2019 International Conference on Robotics and Automation (ICRA), pages 7108–7115. IEEE, 2019.
  * [31] J. Li, Z. Xu, D. Meger, and G. Dudek.  Semantic scene models for visual localization under large viewpoint changes.  In 2018 15th Conference on Computer and Robot Vision (CRV), pages 174–181. IEEE, 2018.
  * [32] Y. Lin, Z. Liu, J. Huang, C. Wang, G. Du, J. Bai, and S. Lian.  Deep global-relative networks for end-to-end 6-dof visual localization and odometry.  In Pacific Rim International Conference on Artificial Intelligence, pages 454–467. Springer, 2019.
  * [33] Y. Liu, Y. Petillot, D. Lane, and S. Wang.  Global localization with object-level semantics and topology.  In 2019 International Conference on Robotics and Automation (ICRA), pages 4909–4915. IEEE, 2019.
  * [34] O. Maimon and L. Rokach.  Data mining and knowledge discovery handbook.  2005\.
  * [35] D. Maturana and S. Scherer.  Voxnet: A 3d convolutional neural network for real-time object recognition.  In 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 922–928. IEEE, 2015.
  * [36] A. Mousavian, J. Košecká, and J.-M. Lien.  Semantically guided location recognition for outdoors scenes.  In 2015 IEEE International Conference on Robotics and Automation (ICRA), pages 4882–4889. IEEE, 2015.
  * [37] R. Mur-Artal, J. M. M. Montiel, and J. D. Tardos.  Orb-slam: a versatile and accurate monocular slam system.  IEEE transactions on robotics, 31(5):1147–1163, 2015.
  * [38] T. Naseer and W. Burgard.  Deep regression for monocular camera-based 6-dof global localization in outdoor environments.  In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 1525–1530. IEEE, 2017.
  * [39] P. C. Ng and S. Henikoff.  Sift: Predicting amino acid changes that affect protein function.  Nucleic acids research, 31(13):3812–3814, 2003.
  * [40] D. Nister and H. Stewenius.  Scalable recognition with a vocabulary tree.  In 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’06), volume 2, pages 2161–2168. Ieee, 2006.
  * [41] E. Parisotto, D. Singh Chaplot, J. Zhang, and R. Salakhutdinov.  Global pose estimation with an attention-based recurrent network.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pages 237–246, 2018.
  * [42] C. R. Qi, L. Yi, H. Su, and L. J. Guibas.  Pointnet++: Deep hierarchical feature learning on point sets in a metric space.  arXiv preprint arXiv:1706.02413, 2017.
  * [43] J. Redmon, S. Divvala, R. Girshick, and A. Farhadi.  You only look once: Unified, real-time object detection.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 779–788, 2016.
  * [44] S. Ren, K. He, R. Girshick, and J. Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  In Advances in neural information processing systems, pages 91–99, 2015.
  * [45] R. B. Rusu, N. Blodow, and M. Beetz.  Fast point feature histograms (fpfh) for 3d registration.  In 2009 IEEE international conference on robotics and automation, pages 3212–3217. IEEE, 2009.
  * [46] R. F. Salas-Moreno, R. A. Newcombe, H. Strasdat, P. H. Kelly, and A. J. Davison.  Slam++: Simultaneous localisation and mapping at the level of objects.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1352–1359, 2013.
  * [47] J. L. Schönberger, M. Pollefeys, A. Geiger, and T. Sattler.  Semantic visual localization.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 6896–6906, 2018.
  * [48] K. Simonyan, A. Vedaldi, and A. Zisserman.  Learning local feature descriptors using convex optimisation.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(8):1573–1585, 2014.
  * [49] P. Speciale, D. P. Paudel, M. R. Oswald, H. Riemenschneider, L. Van Gool, and M. Pollefeys.  Consensus maximization for semantic region correspondences.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 7317–7326, 2018.
  * [50] H. Taira, M. Okutomi, T. Sattler, M. Cimpoi, M. Pollefeys, J. Sivic, T. Pajdla, and A. Torii.  Inloc: Indoor visual localization with dense matching and view synthesis.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 7199–7209, 2018.
  * [51] C. Toft, E. Stenborg, L. Hammarstrand, L. Brynte, M. Pollefeys, T. Sattler, and F. Kahl.  Semantic match consistency for long-term visual localization.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 383–399, 2018.
  * [52] I. Ulrich and I. Nourbakhsh.  Appearance-based place recognition for topological localization.  In Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No. 00CH37065), volume 2, pages 1023–1029. Ieee, 2000.
  * [53] F. Walch, C. Hazirbas, L. Leal-Taixe, T. Sattler, S. Hilsenbeck, and D. Cremers.  Image-based localization using lstms for structured feature correlation.  In Proceedings of the IEEE International Conference on Computer Vision, pages 627–637, 2017.
  * [54] Y. Wang, Y. Sun, Z. Liu, S. E. Sarma, M. M. Bronstein, and J. M. Solomon.  Dynamic graph cnn for learning on point clouds.  Acm Transactions On Graphics (tog), 38(5):1–12, 2019.
  * [55] J. Wu, C. Zhang, T. Xue, W. T. Freeman, and J. B. Tenenbaum.  Learning a probabilistic latent space of object shapes via 3d generative-adversarial modeling.  In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 82–90, 2016.
  * [56] H. Yang, J. Shi, and L. Carlone.  Teaser: Fast and certifiable point cloud registration.  IEEE Transactions on Robotics, 37(2):314–333, 2020.
  * [57] J. Yang, H. Li, D. Campbell, and Y. Jia.  Go-icp: A globally optimal solution to 3d icp point-set registration.  IEEE transactions on pattern analysis and machine intelligence, 38(11):2241–2254, 2015.
  * [58] S. Yang and S. Scherer.  Cubeslam: Monocular 3d object detection and slam without prior models.  arXiv preprint arXiv:1806.00557, 2018.
  * [59] K. M. Yi, E. Trulls, V. Lepetit, and P. Fua.  Lift: Learned invariant feature transform.  In European Conference on Computer Vision, pages 467–483. Springer, 2016.
  * [60] A. Zeng, S. Song, M. Nießner, M. Fisher, J. Xiao, and T. Funkhouser.  3dmatch: Learning local geometric descriptors from rgb-d reconstructions.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1802–1811, 2017.
  * [61] J. Zhang, M. Gui, Q. Wang, R. Liu, J. Xu, and S. Chen.  Hierarchical topic model based object association for semantic slam.  IEEE transactions on visualization and computer graphics, 25(11):3052–3062, 2019.