#  Probabilistic Visual Place Recognition for Hierarchical Localization

Ming Xu, Niko Sünderhauf and Michael Milford Manuscript received: July, 24,
2020; Revised October, 8, 2020; Accepted November, 5, 2020.This paper was
recommended for publication by Editor Sven Behnke upon evaluation of the
Associate Editor and Reviewers’ comments. This work was supported by the QUT
Centre for Robotics and ARC grant CE140100016.The authors are with the QUT
Centre for Robotics, Queensland University of Technology, Brisbane, QLD 4000,
Australia<EMAIL_ADDRESS>2021 IEEE. Personal use of this material
is permitted. Permission from IEEE must be obtained for all other uses, in any
current or future media, including reprinting/republishing this material for
advertising or promotional purposes, creating new collective works, for resale
or redistribution to servers or lists, or reuse of any copyrighted component
of this work in other works.Digital Object Identifier (DOI): see top of this
page.

###### Abstract

Visual localization techniques often comprise a hierarchical localization
pipeline, with a visual place recognition module used as a coarse localizer to
initialize a pose refinement stage. While improving the pose refinement step
has been the focus of much recent research, most work on the coarse
localization stage has focused on improvements like increased invariance to
appearance change, without improving what can be loose error tolerances. In
this letter, we propose two methods which adapt image retrieval techniques
used for visual place recognition to the Bayesian state estimation formulation
for localization. We demonstrate significant improvements to the localization
accuracy of the coarse localization stage using our methods, whilst retaining
state-of-the-art performance under severe appearance change. Using extensive
experimentation on the Oxford RobotCar dataset, results show that our approach
outperforms comparable state-of-the-art methods in terms of precision-recall
performance for localizing image sequences. In addition, our proposed methods
provides the flexibility to contextually scale localization latency in order
to achieve these improvements. The improved initial localization estimate
opens up the possibility of both improved overall localization performance and
modified pose refinement techniques that leverage this improved spatial prior.

###### Index Terms:

Localization, Vision-Based Navigation

##  I Introduction

This letter addresses the long-term visual localization problem, where the aim
is to localize a camera within a pre-built map across varying levels of
appearance change induced by time of day, weather, seasonal or structural
changes. Recent work around 6DoF visual localization (VLoc) [1] takes steps
towards designing localization pipelines that are robust to appearance change
for indirect, feature-based visual SLAM (VSLAM). One of the objectives in VLoc
is to yield a precise 6DoF pose for a query image within a large-scale, point
cloud reconstruction of a scene built from a set of reference images. This
query image is captured under different appearance conditions to the reference
images. Hierarchical pipelines are commonly used [2, 3, 4] where first, a
Visual Place Recognition (VPR) [5] system is used as a coarse localizer to
retrieve relevant reference images and subsequently a pose refinement step is
applied to the query image and the subset of the point cloud corresponding to
the retrieved images to estimate the 6DoF pose.

Using this initial VPR retrieval step has been shown to both improve the
scalability of localization in large environments and furthermore, reduces the
occurrence of incorrect data associations between points in the query image
and the map [2, 3, 4]. One of the key factors determining performance is how
close the localization estimate provided by the initial retrieval step is to
the true query pose, motivating the development of more accurate place
recognition techniques. This observation doubly holds for pose refinement
steps based on direct image alignment, where aligning query and reference
images with large baseline shifts [6] can cause convergence to a suboptimal
solution.

Despite many significant advances in recent years around improving the
robustness of the pose refinement step [7, 8, 9], little research has
addressed improving the coarse localizer in this hierarchical context. While
there is an extensive literature around improving the invariance of place
recognition systems to appearance change [10, 5, 11, 12, 13], these systems
are not designed to localize at tight error tolerances (e.g. $\leq 5$m) more
suitable for hierarchical localization. The research described in this letter
sets out to address these current capability gaps.

Figure 1: Our proposed methods recursively update the posterior state estimate
of the robot given query images $\mathbf{z}_{t}$ and odometry
$\mathbf{U}_{t-1}$ in the case of our MCL algorithm. At each time step, we
check for convergence of the posterior and provide a pose estimate if it has
converged.

Our contributions are summarized below:

  1. 1.

We propose two novel approaches to large-scale global localization over
appearance change which involves adapting VPR methods based on image matching
to the Bayesian state estimation framework. For each approach, this is
achieved by specifying a suitable motion model and measurement model. The
first method is based on a discrete Bayes’ filter and localizes using
appearance only to a topological map. The second method is a Monte Carlo
Localization (MCL) algorithm which localizes using appearance and odometry. We
show in our experiments that the MCL algorithm yields substantially better
performance compared to the Bayes’ filter at the cost of computation time.

  2. 2.

For each approach, we introduce a convergence detection and pose estimation
method which is applied to the posterior state estimate at each time step.
This allows our proposed methods to automatically scale the required
localization latency (sequence length) based on the level of perceptual
aliasing in the environment for a given level of precision.

  3. 3.

We demonstrate that our proposed localization algorithms can successfully
localize sequences of query images with high recall and precision at
significantly tighter error tolerances across severe appearance change
compared to existing methods based on template matching. This allows the
possibility for our method to be used without following a full retrieval-
refinement pipeline.

We also make our code freely available
online111https://github.com/mingu6/ProbFiltersVPR.git.

##  II Related works

This section reviews relevant research on visual place recognition, Bayesian
state estimation for localization in robotics and finally, hierarchical visual
localization.

###  II-A Visual Place Recognition

The VPR problem is commonly treated as a template matching problem; we assume
the map consists of a set of “places”, and each place has an associated
template extracted from either single images [14, 15, 16, 17] or image
sequences [10, 12, 13, 18, 19, 20, 21]. Existing VSLAM systems already
incorporate viewpoint-invariant VPR systems for loop-closure and localization
[6, 22] and extending these systems to be robust to appearance change will
help enable map reuse over extended periods of operation.

One focus within VPR research is around designing methods that can
successfully match places across changing appearance conditions such as
day/night and seasonal changes [16, 17, 15, 23], as well as across viewpoint
changes [24, 14, 11]. In addition, these approaches can be further partitioned
into methods that perform matching using deep learning [17, 15, 23, 25] or
handcrafted visual features [16, 26, 27]. Common across many of these
approaches is a match scoring system; given a pair of images, a typical VPR
system outputs a “quality score” which indicates the likelihood of two images
being captured from the same place. Methods such as [15, 16, 25] first embed
the images into an embedding space and set the quality score as the Euclidean
distance between the embeddings; lower indicates a higher likelihood of a
match.

Our proposed approach treats the quality scores from a place recognition
algorithm as noisy sensor measurements and localizes using the Bayesian state
estimation framework. In principle, place recognition methods using
alternative sensor modalities such as LiDAR can also be used with our proposed
methods [28, 29, 30, 31].

###  II-B Bayesian state estimation-based localization

The Bayesian state estimation framework has been used extensively for
localization in the past, however much of the initial work in this area
involved measurement models designed for range-bearing sensors such as laser
scanners [32, 33, 34]. More recently, [35] used this framework to localize an
autonomous vehicle using visual odometry in a large-scale cartographic map
created using street segments. Furthermore, [36] extends Monte Carlo
Localization to multiple sensor modalities including vision.

In the context of VPR, FAB-MAP [14] formulates topological mapping and
localization as a Bayesian state estimation problem and uses handcrafted
visual features to represent a place. This base model has been extended to
include odometry and image sequences [37, 18]. In comparison, our approach
does not perform mapping, however unlike [14, 37, 18], it can successfully
localize in a large-scale map across severe appearance change when used in
conjunction with a condition invariant VPR method. Finally, [19, 20] also uses
a Bayesian state estimation framework for localization using VPR given by [16]
however they do not test their method across severe appearance change for
real-world datasets.

###  II-C Hierarchical visual localization

An increasing body of research addresses building hierarchical localization
pipelines [2, 3, 4] for sparse, indirect feature-based maps, where VPR
techniques form the initial coarse localizer. The pipeline typically involves
an image retrieval step where the top-$k$ most similar reference images for a
given query are retrieved. The pose refinement step is then performed on the
subset of 3D points corresponding to the retrieved images. This methodology
imposes a bottleneck on localization performance caused by the VPR system
because a failed retrieval step provides a poor initialization for the pose
refinement method.

Despite recent advances around the pose refinement stage [7, 8, 9], to the
best of our knowledge there is minimal research on improving the VPR back-
end’s achievable error tolerances in this hierarchical context. We fill this
gap with our proposed sequence-based back-ends and demonstrate high precision-
recall performance at error tolerances suitable for initializing a pose
refinement technique. Finally, we note that there is limited literature in the
VLoc literature (as opposed to topological mapping) around localizing image
sequences in general. [1] showed substantial performance gains using image
sequences and/or multiple camera views in the pose refinement stage and [38]
explores using image sequences in the absolute pose regression context.

##  III Bayesian state estimation for localization

###  III-A Notation

A camera pose is given by a rigid-body transformation
$\mathbf{T}\in\text{SE(3)}$ between the world reference frame and the camera,
represented by the $4\times 4$ homogeneous matrix

$\mathbf{T}=\begin{pmatrix}\mathbf{R}&\mathbf{t}\\\
\mathbf{0}&1\end{pmatrix},$

where $\mathbf{R}\in\text{SO(3)}$ and $\mathbf{t}\in\mathbb{R}^{3}$. We
represent linearized pose increments as Lie algebra elements
$\bm{\epsilon}\in\mathfrak{se}(3)$ which are in turn represented directly as
vectors $\bm{\epsilon}\in\mathbb{R}^{6}$ for convenience. We define the usual
composition operator

$\circ:\text{SE(3)}\times\mathfrak{se}(3)\rightarrow\text{SE(3)},\quad\mathbf{T}\circ\bm{\epsilon}=\mathbf{T}\cdot\exp\hat{\bm{\epsilon}}.$

###  III-B Overview

In this section, we provide an overview around using Bayesian state estimation
for localization. Suppose we have a sequence of noisy sensor measurements
given by a query image sequence $\\{\mathbf{z}_{s}\\}_{s=1}^{t}$ generated
from corresponding unknown poses $\\{\mathbf{T}_{s}\\}_{s=1}^{t}$, potentially
with odometry estimates $\\{\mathbf{U}_{s}\\}_{s=1}^{t-1}$ between
measurements (e.g. from stereo visual odometry). For the purpose of this
letter, we let $\mathbf{T}_{s},\mathbf{U}_{s}\in\text{SE(3)}$, and
$\mathbf{z}_{s}\in\mathbb{R}^{D}$ be the query image embedding returned by a
VPR system (e.g. NetVLAD [15]). Also, let the pre-built map of the environment
be given by
$\mathcal{M}=\\{(\mathbf{T}_{s}^{r},\mathbf{z}_{s}^{r})\\}_{s=1}^{N}$ which
consists of reference image embeddings $\mathbf{z}_{s}^{r}$ and corresponding
poses $\mathbf{T}_{s}^{r}$. Bayesian state estimation seeks to estimate the
posterior distribution over the current pose $\mathbf{T}_{t}$ given the map
and the full sequence of sensor measurements and odometry through the
recursion

$\displaystyle
p(\mathbf{T}_{t}|\mathbf{z}_{1:t},\mathbf{U}_{1:t},\mathcal{M})\propto p($
$\displaystyle\mathbf{z}_{t}|\mathbf{T}_{t},\mathcal{M})p(\mathbf{T}_{t}|\mathbf{T}_{t-1},\mathbf{U}_{t-1})$
$\displaystyle
p(\mathbf{T}_{t-1}|\mathbf{z}_{1:t-1},\mathbf{U}_{1:t-1},\mathcal{M}).$ (1)

The implementation of this recursion depends on the underlying motion and
measurement models which are given by
$p(\mathbf{T}_{t}|\mathbf{T}_{t-1},\mathbf{U}_{t-1})$ and
$p(\mathbf{z}_{t}|\mathbf{T}_{t},\mathcal{M})$, respectively. The motion model
encodes the dynamics of the robot and can be conditioned on an odometry
estimate while the measurement model scores the likelihood of an observation
given a robot pose. In this letter, we propose two algorithms using different
model formulations: A Topological Localizer based off of a discrete Bayes
filter which localizes using appearance information only (Section IV), and a
Monte Carlo Localization (MCL) algorithm which utilizes appearance and
odometry during localization (Section V). Figure 1 illustrates the full
localization pipeline for our proposed methods.

Figure 2: Demonstration of our proposed methods with our topological
localizer; green represents the ground truth pose, blue represents the top 5
image retrieval candidates from VPR (NetVLAD) and magenta represents the model
proposal. Darker shades of red indicate a higher posterior belief. Top: Query
sequence with perceptual aliasing where VPR yields inconsistent retrievals for
the first 10 timesteps, causing the posterior to not converge and consequently
not localize (left, middle). After more iterations, more consistent retrieval
candidates concentrates the posterior in the correct region in the map,
yielding a correct pose estimate upon localization (right). Bottom: In this
case, VPR works extremely well and our method converges to the correct pose
estimate almost immediately.

###  III-C Convergence detection and pose estimation

For each of our two proposed algorithms, we estimate the full posterior
distribution over the robot pose. A desirable capability of a localization
system is to yield a single pose estimate from the posterior, which can then
be used either as a final pose estimate or to initialize a pose refinement
technique. We introduce a heuristic to detect convergence of the posterior to
a single mode for both methods, which in practice yields extremely accurate
localization performance, even before resorting to pose refinement. Figure 2
demonstrates our system running where VPR fails as well as when VPR works
well, showing how our system scales localization latency to achieve state-of-
the-art localization performance.

##  IV Topological localizer

In this section, we introduce our first proposed method, the topological
localizer. We will first introduce the model formulation which is based off of
a discrete Bayes filter and subsequently introduce the full localization
algorithm.

###  IV-A Model formulation

In our topological localizer, we assume the robot can only assume a finite set
of poses which are given by the reference poses, formally
$\mathbf{T}_{t}\in\\{\mathbf{T}_{s}^{r}\\}_{s=1}^{N}$. Consequently, our
posterior at time $t$ is a probability vector $\mathbf{p}_{t}$. In addition,
we assume the reference images are captured in sequence; reference poses
captured at nearby indices correspond to nearby poses. From this, we can
define our motion model using discrete state transitions and use the forward
algorithm for Hidden Markov Models to recursively update the posterior.

###  IV-B Motion model

We use a simple motion model for our topological localizer which does not
require odometry estimates between query images. We assume the robot can
transition to nearby poses corresponding to nearby frames in the video
sequence with uniform probability at each time step. Formally,

$p(\mathbf{T}_{i}^{r}|\mathbf{T}_{j}^{r})\propto\begin{cases}1&w_{l}\leq
i-j\leq w_{u}\\\ 0&\text{otherwise}\end{cases},$ (2)

where $w_{u}$ and $w_{l}$ are the upper and lower bounds for state
transitions. Having sufficiently wide bounds allows for variations in velocity
between query and reference traverses.

###  IV-C Measurement model

We can score the likelihood of observing a query image embedding
$\mathbf{z}_{t}$ at one of the finite valid poses $\mathbf{T}_{s}^{r}$ using
the Euclidean distance between the reference and query embeddings. Formally,
our measurement model is given by

$p(\mathbf{z}_{t}|\mathbf{T}_{s}^{r},\mathcal{M})\propto
g(\mathbf{z}_{t},s,\mathcal{M})=\exp(-\lambda_{1}\|\mathbf{z}_{t}-\mathbf{z}_{s}^{r}\|_{2}),$
(3)

where $\lambda_{1}$ is set automatically upon initialization given a user-set
parameter $\delta>0$. $\delta$ sets the intensity of the effect of sensor
measurements on the posterior. At $t=1$, we set

$\lambda_{1}=\frac{\log\delta}{d_{0.975}-d_{0.025}},$

where $d_{q}$ is the $q^{th}$ quantile of the set of distances between the
first query embedding $\mathbf{z}_{1}$ and all reference embeddings. Setting
$\lambda_{1}$ in this way ensures the likelihoods in (3) are consistently
scaled (in a relative sense) across embedding choice and query/reference
conditions. In principle, alternative VPR methods that directly score image
pairs without an intermediate embedding stage such as [11] can also be used in
place of the Euclidean distance between embeddings.

###  IV-D Posterior update

Let $\mathbf{E}\in\mathbb{R}^{N\times N}$ be the transition matrix, where the
$i^{th}$ row and $j^{th}$ column entry is given by
$\mathbf{E}_{ij}=p(\mathbf{T}_{j}^{r}|\mathbf{T}_{i}^{r})$. Let
$\mathbf{O}_{t}\in\mathbb{R}^{N\times N}$ be a diagonal matrix where
$\mathbf{O}_{t,ii}=g(\mathbf{z}_{t},i,\mathcal{M})$. The recursive update on
the posterior from (III-B) is given by

$\mathbf{p}_{t}\propto\mathbf{O}_{t}\mathbf{E}^{\top}\mathbf{p}_{t-1}.$

The banded diagonal structure of $\mathbf{E}$ implied by (2) ensures that this
operation is linear with $N$.

###  IV-E Convergence detection and pose estimation

Finally, we can use the posterior distribution to determine convergence of the
filter and subsequently yield a single pose estimate. Our convergence
detection measure $\tau_{t}\in(0,1]$ is given by the total probability mass in
a neighborhood around the maximum a-posteriori (MAP) state estimate. Let
$s^{*}=\operatorname*{arg\,max}_{s}p(\mathbf{T}_{s}^{r}|\mathbf{z}_{1:t},\mathcal{M})$
and from this,

$\tau_{t}=\sum_{s\in\mathcal{W}}p(\mathbf{T}_{s}^{r}|\mathbf{z}_{1:t},\mathcal{M}),\quad\mathcal{W}=\\{s^{*}-w,\dots,s^{*}+w\\}.$
(4)

If $\tau_{t}>\tau_{thres}$, then our pose estimate is
$\widehat{\mathbf{T}}_{t}=\mathbf{T}_{\hat{s}}^{r}$ where

$\hat{s}=\Biggl{\lfloor}\sum_{s\in\mathcal{W}}sp(\mathbf{T}_{s}^{r}|\mathbf{z}_{1:t},\mathcal{M})\Biggr{\rfloor}.$

We found empirically that averaging over a neighborhood of the MAP performed
better than using the MAP directly.

##  V 6DoF Monte Carlo Localization

In this section, we introduce our second proposed method, the Monte Carlo
Localization (MCL) algorithm. In addition to appearance, it utilizes odometry
estimates between query images to localize and in our experiments,
demonstrates improved localization performance at the cost of computation
time. We will first introduce the model formulation, followed by the posterior
update steps. Next, we will outline the model components required to perform
the posterior update and finally the convergence detection and pose estimation
method given the estimated posterior.

###  V-A Model formulation

As opposed to the topological localizer, our MCL algorithm assumes the robot
pose is continuous and can span all of SE(3). Particle filters estimate the
posterior distribution over the robot pose
$p(\mathbf{T}_{t}|\mathbf{z}_{1:t},\mathbf{U}_{1:t-1},\mathcal{M})$ using a
finite set of weighted samples
$\mathcal{X}_{t}=\\{w^{(i)}_{t},\mathbf{T}^{(i)}_{t}\\}_{i=1}^{M}$.

###  V-B Posterior update

After particle initialization, the recursion given in (III-B) is now
implemented by first updating the particles by sampling from the motion model
(motion update) and subsequently reweighting the particles using the
measurement model (measurement update). To prevent sample degeneracy, we use a
heuristic where systematic resampling [39] is applied to particles after the
update steps if the Effective Sample Size (ESS) given by
$\text{ESS}=1/\sum_{i=1}^{M}{w^{(i)}_{t}}^{2}$ is below a threshold
$p\in(0,1)$. We use $p=0.3$ in our work.

###  V-C Motion model

We apply a motion update to each particle given by

$\operatorname{motion\\_update}(\mathbf{U}_{t-1},\mathbf{T}^{(i)}_{t-1})=\mathbf{U}_{t-1}\cdot\mathbf{T}^{(i)}_{t-1}\circ\bm{\epsilon},$

where $\bm{\epsilon}\sim\mathcal{N}(\mathbf{0},\bm{\Sigma}_{odom})$. This is a
simple, platform agnostic motion model that perturbs the screw motion given by
the raw odometry reading with independent Gaussian noise.

###  V-D Measurement model

The measurement model updates a particle weight $w^{(i)}_{t-1}$ using the
likelihood of observing the current query descriptor $\mathbf{z}_{t}$ at the
pose $\mathbf{T}^{(i)}_{t}$. Our measurement update incorporates VPR
measurements similarly to (3), but also includes the physical distance between
the particle and nearby reference images. From this, we introduce our
measurement update as

$\displaystyle\operatorname{mment\\_update}(\mathbf{z}_{t},\mathbf{T}^{(i)}_{t};\mathcal{M})=$
$\displaystyle\sum_{k=1}^{K}\exp\bigl{(}-\lambda_{1}\|\mathbf{z}_{t}-\mathbf{z}_{n_{k}}^{r}\|_{2}$
$\displaystyle-\lambda_{2}d(\mathbf{T}^{(i)}_{t},\mathbf{T}_{n_{k}}^{r})\bigr{)},$
(5)

where $\lambda_{1}$ is as per (3) and $\lambda_{2}>0$ is set by the user and
controls the impact of map deviation on the particle weight. Furthermore, $d$
is a metric on SE(3) given by

$d(\mathbf{T}_{1},\mathbf{T}_{2})=\|\mathbf{t}_{1}-\mathbf{t}_{2}\|_{2}+\alpha\|\log(\mathbf{R}_{1}^{\top}\mathbf{R}_{2})\|_{2},$
(6)

where $\|\log(\mathbf{R}_{1}^{\top}\mathbf{R}_{2})\|_{2}$ is the minimum
rotation angle between $\mathbf{R}_{1}$ and $\mathbf{R}_{2}$ and $\alpha$ is a
scaling weight. $K$ is the number of nearest neighbor map reference images to
retrieve for each particle and $n_{k}$ is the index of the $k^{th}$ nearest
reference image according to (6) to the particle pose. For (6), fast nearest-
neighbor search algorithms are available [40].

###  V-E Particle Initialization

We initialize our $M$ particles from the set of reference image poses
$\\{\mathbf{T}_{i}^{r}\\}_{i=1}^{N}$ with probability proportional to the
visual similarity from $\mathbf{z}_{1}$ and perturb the poses with Gaussian
noise. Formally, for
$\bm{\epsilon}\sim\mathcal{N}(\mathbf{0},\bm{\Sigma}_{\text{init}})$, let

$\mathbf{T}^{(i)}_{1}=\mathbf{T}_{n}^{r}\circ\bm{\epsilon},\quad
n\sim\text{Cat}(N,\mathbf{p})\quad$

where $\text{Cat}(N,\mathbf{p})$ is the categorical distribution over the
integers from 1 to $N$ with probability vector $\mathbf{p}$ where
$\mathbf{p}_{i}=\eta\exp(-\lambda_{1}\|\mathbf{z}_{t}-\mathbf{z}_{i}^{r}\|_{2})$
and $\eta$ is a normalizing constant.

###  V-F Convergence detection and pose estimation

To determine convergence of the filter from the particle set
$\widehat{\mathbf{T}}_{t}$, we follow the same process as in Section IV-E
where we compute the total probability mass in a neighborhood around the MAP
state estimate. Let $i^{*}=\operatorname*{arg\,max}_{i}w^{(i)}_{t}$,
$\mathcal{W}=\\{i:d(\mathbf{T}^{(i)}_{t},\mathbf{T}^{(i^{*})}_{t})<r\\}$ and
$\tau_{t}=\sum_{i\in\mathcal{W}}w^{(i)}_{t}$. If $\tau_{t}>\tau_{thres}$, then
we assume the filter has converged and estimate the final pose
$\widehat{\mathbf{T}}_{t}=\begin{pmatrix}\widehat{\mathbf{R}}&\hat{\mathbf{t}}\\\
\mathbf{0}&1\end{pmatrix}$, where

$\hat{\mathbf{t}}=\frac{1}{\tau_{t}}\sum_{i\in\mathcal{W}}w^{(i)}_{t}\mathbf{t}^{(i)}_{t},\quad\widehat{\mathbf{R}}_{t}=\operatorname*{arg\,min}_{\mathbf{R}}\sum_{i\in\mathcal{W}}\|\mathbf{R}-\frac{w^{(i)}_{t}}{\tau_{t}}\mathbf{R}^{(i)}_{t}\|_{F}.$

##  VI Experimental setup

This section details the experimental setup and localization performance of
our proposed methods.

###  VI-A Datasets

We use the Oxford RobotCar dataset [41], which is comprised of traverses of
Oxford city during different seasons, time of day and weather conditions. We
use the forward facing camera for four overlapping traverses spaced months
apart over a wide range of appearance conditions; three for query and one for
reference, each approximately 10km in length. The pose estimates for images in
the reference traverse are given by the RTK GPS [42] and subsampled at
approximately 0.5m increments yielding 13,595 images. We performed 500 trials
where for each trial we localize a short query sequence with a randomly
selected starting location within the full query traverse. Each short query
sequence contains 30 images spaced approximately 3m apart. We use the stereo
visual odometry (VO) provided with the RobotCar dataset as odometry. Finally,
we use the implementation of NetVLAD [15] found in [43] and DenseVLAD [16] as
image embeddings and extracted these from full resolution images. Table I
summarizes the datasets used and Figure 3 shows example images in the RobotCar
dataset.

Figure 3: Sample images from the RobotCar dataset illustrating levels of condition change and baseline shifts for selected error tolerances. Left: Reference images. Middle/Right: Images from query traverses furthest from reference image that are still within the given metric error tolerance. TABLE I: Traverses used in the experiments Name | Conditions | Traverse
---|---|---
2015-03-17-11-08-44 | Overcast | Reference
2015-10-29-12-18-17 | Rain | Query
2014-11-21-16-07-03 | Dusk, Rain | Query
2014-12-16-18-44-24 | Night | Query

###  VI-B Model Comparisons

For our experiments, we use precision-recall (PR) curves to compare our
proposed methods with state-of-the-art sequence-matching methods [10, 13] as
well as a single image matching baseline. Parameter tuning was performed and
modifications were applied to all comparison methods to maximize their
competitiveness with our proposed approach to make the comparison as relevant
as possible.

Precision and recall are computed across all 500 trials. For each trial, we
note whether or not a method successfully localizes (e.g. the convergence
criteria is met for our methods). A successfully localized trial is defined to
be a true positive if the ground truth error falls within a specified error
tolerance and a false positive if the error falls outside of the tolerance. A
false negative is recorded if localization failed. In this work, we use two
error tolerances; one with 3 meters translation and 15 degrees orientation
error more suitable for initializing direct image alignment and the other with
5 meters translation and 30 degrees orientation error more suitable for
indirect, feature-based methods. Both tolerances ensure that query and matched
reference images have high covisibility necessary for pose refinement,
maximizing the relevance of the results to hierarchical localization methods.
We define the translation error as $\|t_{p}-t_{gt}\|_{2}$ and orientation
error for each trial to be $\|\log(\mathbf{R}_{p}^{\top}\mathbf{R}_{gt})\|$
when measuring error between proposals and the ground truth pose.

####  VI-B1 Proposed Approaches

For our proposed approaches if $\tau_{t}>\tau_{\text{thres}}$ at time $t$,
then we evaluate the error between the RTK query image pose and the pose
estimate provided by our methods. PR curves are generated by varying
$\tau_{\text{thres}}$.

####  VI-B2 Single Image Matching

Our single image matching baseline localizes a trial by retrieving the
reference image closest in appearance to the first query image in the
sequence. Ground truth error is calculated using the RTK poses of the two
images. Precision-recall (PR) curves are generated by varying a non-matching
threshold; matches are accepted only if the embedding distance is lower than
this threshold.

####  VI-B3 Sequence Matching

We compare against a customized version (to maximize performance) of the
sequence matching method in [10] and compute an image-to-image distance matrix
between a query sequence and reference traverse from our image embeddings. A
linear search for coherent sequence matches is performed within this matrix to
allow for changes in velocity between and within traverses. Ground truth error
is calculated between the pose of the first images of both the query and the
successfully matched reference sequence. PR curves are generated by varying a
quality score; see [10] for details. Furthermore, a fixed sequence length of
10 was found to maximize performance across all traverses. Contrast
normalization of the distance matrix used in [10] was not applied, resulting
in further significant performance gains.

####  VI-B4 Graph-based Matching

We also compare against the online, graph-based sequence matching approach
from [13], which removes the constraint of the linear search of the previous
sequence matching method. In addition, the online nature of their method
allows a more direct comparison to our methods compared to fixed-length
sequence matching. We found that the expansion rate parameter $\alpha=0.98$
yielded an optimal balance between computation time and performance across all
traverses.

At each time step, the graph-based approach yields the best match within the
reference images for the current query image in the sequence. A non-matching
score $\hat{w}$ similar to the single image matching case is used to
accept/reject this match. Ground truth error is calculated between the pose of
the query and reference images corresponding to the first accepted match. PR
curves are generated by varying $\hat{w}$.

####  VI-B5 MCL Ablations

We test our MCL algorithm replacing odometry from VO with the RTK GPS ground
truth to show how higher quality odometry estimates affect localization
performance. In another test, we discarded the visual similarity term in
(V-D), using proximity to reference images poses only but observed that
localization consistently failed.

###  VI-C Parameter Values

For the topological filter, we used $\delta=5$, $w_{l}=-2$, $w_{u}=10$ and the
window parameter in (4) set to $w=6$. We list the parameter values used for
our MCL algorithm in Table II. The same parameter values were used across all
query/reference/embedding combinations.

TABLE II: MCL parameter values Parameter | Section | Value
---|---|---
$M$ | V | 6000
$\delta$ | IV-C | 5
$\operatorname*{diag}(\bm{\Sigma}_{init})$ | V-C | $[2.0^{2},0.5^{2},0.5^{2},0.05^{2},0.05^{2},0.1^{2}]$
$\operatorname*{diag}(\bm{\Sigma}_{odom})$ | V-C | $[0.8^{2},0.3^{2},0.3^{2},0.04^{2},0.04^{2},0.08^{2}]$
$\lambda_{2}$ | V-D | 0.2
$K$ | V-D | 3
$\alpha$ | V-D | 15
$r$ | V-F | 10

##  VII Experimental results

###  VII-A Localization Performance

Figure 4: Precision-recall curves for all experiments. For the MCL-based
algorithms, we shade in the region between the max and min precision values
for each recall to account for variability for our MCL algorithm over 5
trials. The proposed topological filter and MCL methods substantially
outperform all other methods in all cases. In addition, the inclusion of
quality odometry estimates improved performance substantially, especially at
the finer tolerance. In some cases, the topological filter outperformed the
MCL algorithm with VO, suggesting some sensitivity of performance to the
quality of the odometry.

We measure performance using PR curves because they capture the performance
characteristics of a coarse localizer. We present the generated PR curves in
Figure 4. Recall at 99% precision and area under the curve metrics for all
methods are also presented for a more direct numerical comparison in Tables
III, IV and V.

Our proposed methods perform substantially better overall compared to the
comparison methods, especially across severe appearance change. This is
achieved in part due to our Bayesian state-estimation formulation because we
choose to localize query sequences only when the posterior belief converges.
For query sequences with higher levels of perceptual aliasing with
inconsistent VPR retrievals, the posterior converges more slowly but as a
consequence yields more accurate and reliable pose estimates. In contrast,
linear or greedy sequence matching used in the comparison approaches tend to
fail under these circumstances.

TABLE III: Recall (%) at 99% precision (5m, 30 deg) Model | Rain | Dusk | Night
---|---|---|---
NV | DV | NV | DV | NV | DV
Single | 65.8 | 70.8 | 4.0 | 9.4 | 1.2 | 4.8
SeqM | 83.1 | 83.5 | 31.1 | 47.4 | 6.2 | 22.2
Graph | 88.3 | 89.7 | 14.0 | 42.6 | 6.0 | 30.7
Topological | 91.7 | 93.6 | 92.0 | 90.9 | 57.6 | 80.0
MCL | 97.2 | 96.6 | 80.0 | 80.2 | 55.8 | 47.3
MCL (RTK) | 96.2 | 96.0 | 100.0 | 100.0 | 76.1 | 86.4
TABLE IV: Area-under-curve (NetVLAD) Model | Rain | Dusk | Night
---|---|---|---
3m | 5m | 3m | 5m | 3m | 5m
Single | 0.974 | 0.988 | 0.627 | 0.827 | 0.392 | 0.535
SeqM | 0.980 | 0.994 | 0.736 | 0.905 | 0.538 | 0.737
Graph | 0.990 | 0.996 | 0.728 | 0.912 | 0.581 | 0.737
Topological | 0.990 | 0.997 | 0.893 | 0.996 | 0.850 | 0.975
MCL | 0.998 | 0.999 | 0.928 | 0.993 | 0.844 | 0.981
MCL (RTK) | 0.998 | 0.999 | 0.953 | 1.000 | 0.925 | 0.992
TABLE V: Area-under-curve (DenseVLAD) Model | Rain | Dusk | Night
---|---|---|---
3m | 5m | 3m | 5m | 3m | 5m
Single | 0.958 | 0.987 | 0.717 | 0.824 | 0.506 | 0.651
SeqM | 0.980 | 0.993 | 0.835 | 0.965 | 0.714 | 0.870
Graph | 0.985 | 0.996 | 0.857 | 0.956 | 0.760 | 0.876
Topological | 0.990 | 0.997 | 0.905 | 0.997 | 0.881 | 0.983
MCL | 0.994 | 0.999 | 0.909 | 0.994 | 0.875 | 0.987
MCL (RTK) | 0.996 | 0.999 | 0.972 | 1.000 | 0.917 | 0.995

###  VII-B Automatic scaling of localization latency

We display the average number of steps to localize for each method in Table VI
at the 99% precision level. We can see that for our methods, lower levels of
perceptual aliasing require fewer steps to localize on average which is not
possible for the fixed length sequence matching approach.

TABLE VI: Avg steps to localize at 99% precision (5m, 30 deg) Model | Rain | Dusk | Night
---|---|---|---
NV | DV | NV | DV | NV | DV
Single | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0
SeqM | 10.0 | 10.0 | 10.0 | 10.0 | 10.0 | 10.0
Graph | 5.3 | 4.6 | 12.2 | 9.4 | 10.7 | 11.5
Topological | 6.4 | 6.1 | 9.8 | 9.9 | 17.5 | 12.9
MCL | 5.5 | 5.6 | 13.9 | 12.3 | 18.2 | 16.1
MCL (RTK) | 5.6 | 5.6 | 8.9 | 7.4 | 17.4 | 13.8

###  VII-C Computation Time

Finally, we benchmark the computation time per iteration for each of our
methods at 99% precision. All methods were implemented in Python using the
Numpy library, and all computations were vectorized as much as possible within
a single trial. Benchmarks were run on a desktop with a Intel® Core™ i7-7700K
CPU, 32Gb RAM running Ubuntu 20.04 and the results are shown in Table VII for
the 5m, 30 deg error tolerance, where reasonable recall performance was
achieved across all methods.

On a cost per iteration level, our proposed MCL algorithm is the most
expensive. This is mostly attributed to the nearest neighbor search from (V-D)
as well as the particle motion update. In contrast, our topological localizer
is comparable to both single image matching and the linear sequence matching
approach due to the simple, parallel and vectorizable nature of the underlying
computations. Finally, graph-based matching is a serial algorithm, resulting
in more expensive iterations overall compared to our topological localizer.

TABLE VII: Compute time per iteration (ms) at 99% precision (5m, 30 deg) Model | Rain | Dusk | Night
---|---|---|---
NV | DV | NV | DV | NV | DV
Single | 9 | 9 | 9 | 9 | 9 | 9
SeqM | 9 | 9 | 9 | 9 | 9 | 9
Graph | 35 | 39 | 15 | 21 | 11 | 15
Topological | 9 | 9 | 9 | 9 | 9 | 9
MCL | 60 | 61 | 48 | 51 | 46 | 47
MCL (RTK) | 58 | 60 | 66 | 70 | 47 | 54

###  VII-D Overall performance

We have presented two methods; a method that yields localization performance
which outperforms existing state-of-the-art methods for comparable computation
effort as well as another method which yields vastly superior performance
given additional computation time and odometry estimates.

##  VIII Discussion and Conclusion

We presented two new online, probabilistic sequence-based VPR back-ends that
provide the tight error tolerances suitable for initializing a subsequent pose
refinement step within a hierarchical localization system while achieving
state-of-the-art results across various levels of appearance change on real-
world datasets. The work here prompts a number of interesting avenues for
future research. The question of how the localization load is optimally shared
between the coarse localizer and the subsequent pose refinement step remains
open; investigating how to determine this balance with respect to key factors
such as performance and computational cost will likely yield further advances.

In addition, one potential future application area for our proposed methods is
within the visual teach and repeat literature [44, 45, 46], specifically
around vision-only localization in GPS denied environments [47]. Our method
may allow vision-only localization possible across severe appearance change
with a single mapping run, as opposed to resorting to an experience-based
system [48].

## References

  * [1] T. Sattler, W. Maddern, C. Toft, A. Torii, L. Hammarstrand, E. Stenborg, D. Safari, M. Okutomi, M. Pollefeys, J. Sivic, F. Kahl, and T. Pajdla, “Benchmarking 6DOF Outdoor Visual Localization in Changing Conditions,” in _IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018, pp. 8601–8610.
  * [2] P. Sarlin, C. Cadena, R. Siegwart, and M. Dymczyk, “From Coarse to Fine: Robust Hierarchical Localization at Large Scale,” in _IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * [3] P.-E. Sarlin, F. Debraine, M. Dymczyk, R. Siegwart, and C. Cadena, “Leveraging Deep Visual Descriptors for Hierarchical Efficient Localization,” in _Conference on Robot Learning (CoRL)_ , 2018.
  * [4] H. Germain, G. Bourmaud, and V. Lepetit, “Sparse-To-Dense Hypercolumn Matching for Long-Term Visual Localization,” in _International Conference on 3D Vision (3DV)_ , 2019.
  * [5] S. Lowry, N. Sünderhauf, P. Newman, J. J. Leonard, D. Cox, P. Corke, and M. J. Milford, “Visual Place Recognition: A Survey,” _IEEE Transactions on Robotics_ , vol. 32, no. 1, pp. 1–19, 2016.
  * [6] J. Engel, T. Schöps, and D. Cremers, “LSD-SLAM: Large-Scale Direct Monocular SLAM,” in _European Conference on Computer Vision (ECCV)_ , September 2014.
  * [7] D. DeTone, T. Malisiewicz, and A. Rabinovich, “SuperPoint: Self-Supervised Interest Point Detection and Description,” in _IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW)_ , 2018, pp. 337–33 712.
  * [8] L. von Stumberg, P. Wenzel, Q. Khan, and D. Cremers, “GN-Net: The Gauss-Newton Loss for Multi-Weather Relocalization,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 2, pp. 890–897, 2020.
  * [9] M. Dusmanu, I. Rocco, T. Pajdla, M. Pollefeys, J. Sivic, A. Torii, and T. Sattler, “D2-Net: A Trainable CNN for Joint Detection and Description of Local Features,” in _IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * [10] M. J. Milford and G. F. Wyeth, “SeqSLAM: Visual route-based navigation for sunny summer days and stormy winter nights,” in _IEEE International Conference on Robotics and Automation (ICRA)_ , 2012.
  * [11] S. Garg, N. Suenderhauf, and M. Milford, “Don’t Look Back: Robustifying Place Categorization for Viewpoint- and Condition-Invariant Place Recognition,” in _IEEE International Conference on Robotics and Automation (ICRA)_ , 2018, pp. 3645–3652.
  * [12] S. Hausler, A. Jacobson, and M. Milford, “Multi-Process Fusion: Visual Place Recognition Using Multiple Image Processing Methods,” _IEEE Robotics and Automation Letters_ , 2019.
  * [13] O. Vysotska and C. Stachniss, “Lazy data association for image sequences matching under substantial appearance changes,” _IEEE Robotics and Automation Letters_ , vol. 1, no. 1, pp. 213–220, 2016.
  * [14] M. Cummins and P. Newman, “FAB-MAP: Probabilistic Localization and Mapping in the Space of Appearance,” _The International Journal of Robotics Research_ , vol. 27, no. 6, pp. 647–665, 2008.
  * [15] R. Arandjelović, P. Gronat, A. Torii, T. Pajdla, and J. Sivic, “NetVLAD: CNN architecture for weakly supervised place recognition,” in _IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016\.
  * [16] A. Torii, R. Arandjelović, J. Sivic, M. Okutomi, and T. Pajdla, “24/7 place recognition by view synthesis,” in _2015 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2015.
  * [17] N. Sünderhauf, S. Shirazi, F. Dayoub, B. Upcroft, and M. Milford, “On the performance of convnet features for place recognition,” in _2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2015, pp. 4297–4304.
  * [18] W. Maddern, M. Milford, and G. Wyeth, “Towards persistent localization and mapping with a continuous appearance-based topology,” in _Robotics: Science and Systems VIII_ , 2012.
  * [19] A.-D. Doan, Y. Latif, T.-J. Chin, Y. Liu, T.-T. Do, and I. Reid, “Scalable Place Recognition Under Appearance Change for Autonomous Driving,” in _2019 IEEE/CVF International Conference on Computer Vision (ICCV)_ , 2019\.
  * [20] A.-D. Doan, Y. Latif, T.-J. Chin, Y. Liu, S. F. Ch’ng, T.-T. Do, and I. Reid, “Visual localization under appearance change: A filtering approach,” in _Digital Image Computing: Techniques and Applications (DICTA)_. IEEE, 2019, pp. 1–8.
  * [21] J. M. Facil, D. Olid, L. Montesano, and J. Civera, “Condition-invariant multi-view place recognition,” _arXiv preprint arXiv:1902.09516_ , 2019.
  * [22] R. Mur-Artal, J. M. M. Montiel, and J. D. Tardós, “ORB-SLAM: A Versatile and Accurate Monocular SLAM System,” _IEEE Transactions on Robotics_ , vol. 31, no. 5, pp. 1147–1163, 2015.
  * [23] D. Olid, J. M. Facil, and J. Civera, “Single-view place recognition under seasonal changes,” _arXiv preprint arXiv:1808.06516_ , 2018.
  * [24] D. Galvez-López and J. D. Tardos, “Bags of binary words for fast place recognition in image sequences,” _IEEE Transactions on Robotics_ , vol. 28, no. 5, pp. 1188–1197, 2012.
  * [25] J. Revaud, J. Almazan, R. Rezende, and C. de Souza, “Learning with Average Precision: Training Image Retrieval with a Listwise Loss,” in _2019 IEEE/CVF International Conference on Computer Vision (ICCV)_ , 2019.
  * [26] N. Dalal and B. Triggs, “Histograms of oriented gradients for human detection,” in _IEEE/CVF Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2005.
  * [27] R. Arandjelovic and A. Zisserman, “All About VLAD,” in _IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2013, pp. 1578–1585.
  * [28] Ş. Săftescu, M. Gadd, D. De Martini, D. Barnes, and P. Newman, “Kidnapped radar: Topological radar localisation using rotationally-invariant metric learning,” _arXiv preprint arXiv:2001.09438_ , 2020.
  * [29] M. Gadd, D. De Martini, and P. Newman, “Look around you: Sequence-based radar place recognition with learned rotational invariance,” in _2020 IEEE/ION Position, Location and Navigation Symposium (PLANS)_ , 2020, pp. 270–276.
  * [30] G. Kim and A. Kim, “Scan context: Egocentric spatial descriptor for place recognition within 3d point cloud map,” in _2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2018, pp. 4802–4809.
  * [31] G. Kim, Y. S. Park, Y. Cho, J. Jeong, and A. Kim, “MulRan: Multimodal range dataset for urban place recognition,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_ , 2020, pp. 6246–6253.
  * [32] F. Dellaert, D. Fox, W. Burgard, and S. Thrun, “Monte Carlo Localization for Mobile Robots,” in _IEEE International Conference on Robotics and Automation (ICRA)_ , May 1999.
  * [33] S. Thrun, D. Fox, W. Burgard, and F. Dellaert, “Robust monte carlo localization for mobile robots,” _Artificial Intelligence_ , vol. 128, no. 1, pp. 99 – 141, 2001.
  * [34] S. Thrun, W. Burgard, D. Fox, and R. Arkin, _Probabilistic Robotics_ , ser. Intelligent Robotics and Autonomous Agents series. MIT Press, 2005.
  * [35] M. A. Brubaker, A. Geiger, and R. Urtasun, “Map-based probabilistic visual self-localization,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 38, no. 4, pp. 652–665, 2016.
  * [36] R. Clark, S. Wang, H. Wen, N. Trigoni, and A. Markham, “Increasing the efficiency of 6-dof visual localization using multi-modal sensory data,” in _2016 IEEE-RAS 16th International Conference on Humanoid Robots (Humanoids)_ , 2016, pp. 973–980.
  * [37] W. Maddern, M. Milford, and G. Wyeth, “CAT-SLAM: probabilistic localisation and mapping using a continuous appearance-based trajectory,” _The International Journal of Robotics Research_ , vol. 31, no. 4, pp. 429–451, 2012\.
  * [38] R. Clark, S. Wang, A. Markham, N. Trigoni, and H. Wen, “Vidloc: A deep spatio-temporal model for 6-dof video-clip relocalization,” in _IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2017, pp. 2652–2660.
  * [39] A. Doucet and A. M. Johansen, “A tutorial on particle filtering and smoothing: Fifteen years later,” in _The Oxford Handbook of Nonlinear Filtering_. Oxford University Press, 2011\.
  * [40] J. Ichnowski and R. Alterovitz, “Fast Nearest Neighbor Search in SE(3) for Sampling-Based Motion Planning,” in _Algorithmic Foundations of Robotics XI (WAFR 2014)_. Springer, 2014\.
  * [41] W. Maddern, G. Pascoe, C. Linegar, and P. Newman, “1 Year, 1000km: The Oxford RobotCar Dataset,” _The International Journal of Robotics Research_ , vol. 36, no. 1, pp. 3–15, 2017.
  * [42] W. Maddern, G. Pascoe, M. Gadd, D. Barnes, B. Yeomans, and P. Newman, “Real-time kinematic ground truth for the oxford robotcar dataset,” _arXiv preprint arXiv: 2002.10152_ , 2020.
  * [43] T. Cieslewski, S. Choudhary, and D. Scaramuzza, “Data-efficient decentralized visual SLAM,” _IEEE International Conference on Robotics and Automation (ICRA)_ , May 2018.
  * [44] P. Furgale and T. D. Barfoot, “Visual teach and repeat for long-range rover autonomy,” _Journal of Field Robotics_ , 2010.
  * [45] T. Krajník, P. Cristóforis, K. Kusumam, P. Neubert, and T. Duckett, “Image features for visual teach-and-repeat navigation in changing environments,” _Robotics and Autonomous Systems_ , 2017.
  * [46] D. Dall’Osto, T. Fischer, and M. Milford, “Fast and Robust Bio-inspired Teach and Repeat Navigation,” _Manuscript submitted for publication_ , 2020\.
  * [47] M. Warren, M. Greeff, B. Patel, J. Collier, A. P. Schoellig, and T. D. Barfoot, “There’s no place like home: Visual teach and repeat for emergency return of multirotor uavs during gps failure,” _IEEE Robotics and Automation Letters_ , vol. 4, no. 1, pp. 161–168, 2019.
  * [48] M. Paton, K. MacTavish, M. Warren, and T. D. Barfoot, “Bridging the appearance gap: Multi-experience localization for long-term visual teach and repeat,” in _2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2016, pp. 1918–1925.


are currently investigating this curious appearance of partition combinatorics
in various aspects of Wronskian polynomials.

$\color[rgb]{0.55,0.55,0.55}\definecolor[named]{pgfstrokecolor}{rgb}{0.55,0.55,0.55}\pgfsys@color@gray@stroke{0.55}\pgfsys@color@gray@fill{0.55}{1}$$2$$\color[rgb]{0.55,0.55,0.55}\definecolor[named]{pgfstrokecolor}{rgb}{0.55,0.55,0.55}\pgfsys@color@gray@stroke{0.55}\pgfsys@color@gray@fill{0.55}{3}$$\searrow$$\searrow$$\searrow$$4$$\color[rgb]{0.55,0.55,0.55}\definecolor[named]{pgfstrokecolor}{rgb}{0.55,0.55,0.55}\pgfsys@color@gray@stroke{0.55}\pgfsys@color@gray@fill{0.55}{5}$$\searrow$$\searrow$$\color[rgb]{0.55,0.55,0.55}\definecolor[named]{pgfstrokecolor}{rgb}{0.55,0.55,0.55}\pgfsys@color@gray@stroke{0.55}\pgfsys@color@gray@fill{0.55}{5}$$\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}{4}$$\color[rgb]{0.55,0.55,0.55}\definecolor[named]{pgfstrokecolor}{rgb}{0.55,0.55,0.55}\pgfsys@color@gray@stroke{0.55}\pgfsys@color@gray@fill{0.55}{3}$$4$$\color[rgb]{0.55,0.55,0.55}\definecolor[named]{pgfstrokecolor}{rgb}{0.55,0.55,0.55}\pgfsys@color@gray@stroke{0.55}\pgfsys@color@gray@fill{0.55}{3}$$\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}{2}$$\color[rgb]{0.55,0.55,0.55}\definecolor[named]{pgfstrokecolor}{rgb}{0.55,0.55,0.55}\pgfsys@color@gray@stroke{0.55}\pgfsys@color@gray@fill{0.55}{3}$$2$$\color[rgb]{0.55,0.55,0.55}\definecolor[named]{pgfstrokecolor}{rgb}{0.55,0.55,0.55}\pgfsys@color@gray@stroke{0.55}\pgfsys@color<EMAIL_ADDRESS>Figure 8.9: The hooks on the $j^{\rm th}$ diagonal of the Young diagram of
$T_{2,3}^{(\mu)}$ encode the behaviour of the roots that coalesce at the
origin at $\mu=-n-j-\epsilon$ through the polynomials in Conjecture 8.12. When
$j=3$ the polynomial is $(z^{5}-1)(z^{3}+1)(z-1)$ and when $j=3$ or $j=5$ the
polynomial is $z^{3}-1.$

## Acknowledgements

We thank David Gómez-Ullate, Davide Masoero and Bryn Thomas for helpful
comments and illuminating discussions.

## References

  * [1] V.E. Adler, Nonlinear chains and Painlevé equations, Physica, D73 (1994) 335–351.
  * [2] T. Amdeberhan, Discriminants of Umemura polynomials associated to Painlevé III, Phys. Lett A., 354 (2006) 410–413.
  * [3] H. Aratyn, J.F. Gomes, G.V. Lobo and A.H. Zimerman, On Rational Solutions of Dressing Chains of Even Periodicity, Symmetry, 15 (2023) 249.
  * [4] E. Basor, P. Bleher, R. Buckingham, T. Grava, A. Its, E. Its and J.P. Keating, A representation of joint moments of CUE characteristic polynomials in terms of Painlevé functions, Nonlinearity, 32 (2019) 4033–4078.
  * [5] N. Bonneux, Asymptotic behavior of Wronskian polynomials that are factorized via p-cores and p-quotients, Math. Phys., Anal. and Geom., 23 (2020) 36.
  * [6] N. Bonneux, C. Dunning and M. Stevens, Coefficients of Wronskian Hermite polynomials, Stud. Appl. Math., 144 (2020) 245–288.
  * [7] N. Bonneux and A.B.J. Kuijlaars, Exceptional Laguerre polynomials, Stud. Appl. Math., 141 (2018) 547–595.
  * [8] N. Bonneux and M. Stevens, Recurrence relations for Wronskian Laguerre polynomials, Integral Transforms Spec. Funct., 32 (2021) 39–406.
  * [9] P.A. Clarkson, The third Painlevé equation and associated special polynomials, J. Phys. A, 36 (2003) 9507–9532.
  * [10] P.A. Clarkson, The fouth Painlevé equation and associated special polynomials, J. Math. Phys., 44 (2003) 5350–5374.
  * [11] P.A. Clarkson, Special polynomials associated with rational solutions of the fifth Painlevé equation, J. Comp. Appl. Math., 178 (2005) 111–129.
  * [12] P.A. Clarkson, Painlevé equations – nonlinear special functions, in: Orthogonal Polynomials and Special Functions: Computation and Application, F. Màrcellan and W. Van Assche (Editors), Lect. Notes Math., vol. 1883, Springer-Verlag, Berlin, pp. 331–411, 2006.
  * [13] P.A. Clarkson, Special polynomials associated with rational solutions of the Painlevé equations and applications to soliton equations, Comput. Methods Funct. Theory, 6 (2006) 329–401.
  * [14] P.A. Clarkson, Recurrence coefficients for discrete orthonormal polynomials and the Painlevé equations, J. Phys. A, 46 (2013) 185205.
  * [15] P.A. Clarkson, Classical solutions of the degenerate fifth Painlevé equation, J. Phys. A, 56 (2023) 134002.
  * [16] R. Conti and D. Masoero, Counting monster potentials, J. High Energ. Phys., 02 (2021) 059.
  * [17] C.L. Dodgson, IV. Condensation of determinants, being a new and brief method for computing their arithmetical values, Proc. R. Soc. Lond., 15 (1866) 150–155.
  * [18] A.J. Durán, Exceptional Charlier and Hermite orthogonal polynomials, J. Approx Theory, 182 (2014) 29–58.
  * [19] A.J. Durán, Exceptional Meixner and Laguerre orthogonal polynomials, J. Approx Theory., 184 (2014) 176–208.
  * [20] A.J. Durán and M. Pérez, Admissibility condition for exceptional Laguerre polynomials, J. Math. Anal. Appl., 424 (2015) 1042–1053.
  * [21] A.S. Fokas and M.J. Ablowitz, On a unified approach to transformations and elementary solutions of Painlevé equations, J. Math. Phys., 23 (1982) 2033–2042.
  * [22] P.J. Forrester and N.S. Witte, Application of the $\tau$-function theory of Painlevé equations to random matrices: PIV, PII and the GUE, Commun. Math. Phys., 219 (2001) 357–398.
  * [23] P.J. Forrester and N.S. Witte, Application of the $\tau$-function theory of Painlevé equations to random matrices: PV, PIII, the LUE, JUE, and CUE, Comm. Pure Appl. Math, 55 (2002) 679–727.
  * [24] D. Gómez-Ullate, Y. Grandati and R. Milson, Shape invariance and equivalence relations for pseudo-Wronskians of Laguerre and Jacobi polynomials, J. Phys. A, 51 (2018) 345201.
  * [25] D. Gómez-Ullate, Y. Grandati and R. Milson, Rational solutions of Painlevé systems, in: Nonlinear Systems and Their Remarkable Structures. Vol. 2, N. Euler and M.C. Nucci (Editors), Chapman and Hall/CRC Press, Boca Raton, FL, USA, pp. 249–293, 2019. [arXiv:2009.11668]
  * [26] D. Gómez-Ullate, Y. Grandati, S. Lombardo and R. Milson, Rational solutions of dressing chains and higher order Painlevé systems, arXiv:1811.10186 [math-ph].
  * [27] V.I. Gromak, I. Laine and S. Shimomura, Painlevé Differential Equations in the Complex Plane, _Studies in Math._ , vol. 28, de Gruyter, Berlin, New York, 2002.
  * [28] V.I. Gromak and N.A. Lukashevich, Special classes of solutions of Painlevé’s equations, Diff. Eqns., 18 (1982) 317–326.
  * [29] G. James and A. Kerber, The Representation Theory of the Symmetric Group, Vol. 16, Encyclopedia of Mathematics and its Applications, Addison-Wesley Publishing Co., Reading, Mass, 1981.
  * [30] M. Jimbo and T. Miwa, Monodromy preserving deformations of linear ordinary differential equations with rational coefficients. II, Physica, D2 (1981) 407–448.
  * [31] E.L. Ince, Ordinary Differential Equations, Dover, New York, 1956.
  * [32] K. Iwasaki, H. Kimura, S. Shimomura and M. Yoshida, From Gauss to Painlevé: a Modern Theory of Special Functions, Aspects of Mathematics E, vol. 16, Vieweg, Braunschweig, Germany, 1991.
  * [33] K. Kajiwara and T. Masuda, A generalization of determinant formulae for the solutions of Painlevé II and XXXIV equations, J. Phys. A, 32 (1999) 3763–3778.
  * [34] K. Kajiwara and T. Masuda, On the Umemura polynomials for the Painlevé III equation, Phys. Lett. A, 260 (1999) 462–467.
  * [35] K. Kajiwara and Y. Ohta, Determinantal structure of the rational solutions for the Painlevé II equation, J. Math. Phys., 37 (1996) 4393–4704.
  * [36] K. Kajiwara and Y. Ohta, Determinant structure of the rational solutions for the Painlevé IV equation, J. Phys. A, 31 (1998) 2431–2446.
  * [37] K. Kajiwara, Y. Ohta, J. Satsuma, B. Grammaticos and A. Ramani, Casorati determinant solutions for the discrete Painlevé-II equation, J. Phys. A, 27 (1994) 915–922.
  * [38] K. Kajiwara, K. Yamamoto and Y. Ohta, Rational solutions for the discrete Painlevé II equation, Phys. Lett. A, 232 (1997) 189–199.
  * [39] A.V. Kitaev, C.K. Law and J.B. McLeod, Rational solutions of the fifth Painlevé equation, Diff. Int. Eqns., 7 (1994) 967–1000.
  * [40] K. Koike, On the decomposition of tensor products of the representations of the classical groups: By means of the universal characters, Adv. Math., 74 (1989) 57–86.
  * [41] A.B.J. Kuijlaars, and K.T.R. McLaughlin, Riemann-Hilbert Analysis for Laguerre Polynomials with Large Negative Parameter, Comput. Methods Funct. Theory, 1 (2001) 205-233.
  * [42] I.G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford Mathematical Monographs, Oxford University Press, Oxford, 1995.
  * [43] T. Masuda, Classical transcendental solutions of the Painlevé equations and their degeneration, Tohoku Math. J., 56 (2004) 467–490.
  * [44] T. Masuda, Special polynomials associated with the Noumi-Yamada system of type $A_{5}^{(1)}$, Funkcial. Ekvac., 48 (2005) 231–246.
  * [45] T. Masuda, Y. Ohta and K. Kajiwara, A determinant formula for a class of rational solutions of Painlevé V equation, Nagoya Math. J., 168 (2002) 1–25.
  * [46] T. Muir, A Treatise on the Theory of Determinants (Revised and enlarged by William H. Metzler), Dover, New York, 1960.
  * [47] M. Noumi, Painlevé Equations through Symmetry, Trans. Math. Mono., vol. 223, Amer. Math. Soc., Providence, RI, 2004.
  * [48] M. Noumi, Notes on Umemura polynomials, Ann. Fac.Sci. Toulouse Maths., 5 (2020) 1091–1118.
  * [49] M. Noumi and Y. Yamada, Affine Weyl groups, discrete dynamical systems and Painlevé equations, Commun. Math. Phys., 199 (1998) 281–295.
  * [50] M. Noumi and Y. Yamada, Umemura polynomials for the Painlevé V equation, Phys. Lett. A, 247 (1998) 65–69.
  * [51] M. Noumi and Y. Yamada, Higher order Painlevé equations of type $A^{(1)}_{\ell}$, Funkcial. Ekvac., 41 (1998) 483–503.
  * [52] M. Noumi and Y. Yamada, Symmetries in the fourth Painlevé equation and Okamoto polynomials, Nagoya Math. J., 153 (1999) 53–86.
  * [53] M. Noumi and Y. Yamada, Symmetries in Painlevé equations, Sugaku Expositions, 17 (2004) 203–218.
  * [54] K. Okamoto, Polynomial Hamiltonians associated with Painlevé equations. I, Proc. Japan Acad. Ser. A Math. Sci., 56 (1980) 264–268; 367–371.
  * [55] K. Okamoto, Studies on the Painlevé equations III. Second and fourth Painlevé equations, PII and PIV, Math. Ann., 275 (1986) 221–255.
  * [56] K. Okamoto, Studies on the Painlevé equations. II. Fifth Painlevé equation PV, Japan. J. Math., 13 (1987) 47–76.
  * [57] K. Okamoto, Studies on the Painlevé equations I. Sixth Painlevé equation PVI, Ann. Mat. Pura Appl., 146 (1987) 337–381.
  * [58] K. Okamoto, Studies on the Painlevé equations IV. Third Painlevé equation PIII, Funkcial. Ekvac, 30 (1987) 305–332.
  * [59] K. Okamoto and Y. Ohyama, Mathematical works of Hiroshi Umemura, Ann. Fac. Sci. Toulouse Math. (6), 29 (2020) 1053–1062.
  * [60] F.W.J. Olver, A.B. Olde Daalhuis, D.W. Lozier, B.I. Schneider, R.F. Boisvert, C.W. Clark, B.R. Miller, B.V. Saunders, H.S. Cohl, and M.A. McClain (Editors), NIST Digital Library of Mathematical Functions, http://dlmf.nist.gov/, Release 1.1.9 (March 3, 2023).
  * [61] D.P. Roberts, Discriminants of some Painlevé polynomials, in: Number Theory for the Millennium, III, M.A. Bennett, B.C. Berndt, N. Boston, H.G. Diamond, A.J. Hildebrand and W. Philipp (Editors), pp. A K Peters, Natick, MA, pp. 205–221, 2003.
  * [62] R.P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Studies in Advanced Mathematics, 62, Cambridge University Press, Cambridge, 1999.
  * [63] J.J. Sylvester, Sur une classe nouvelle d’equations differéntielles et déquations aux differences finies d’une forme intégrable, Compt. Rend. Acad. Sc., 54 (1862) 129–170.
  * [64] T. Tsuda, Universal characters, integrable chains and the Painlevé equations, Adv. Math., 197 (2005) 587–606.
  * [65] H. Umemura, Painlevé equations and classical functions, Sugaku Expositions, 11 (1998) 77–100.
  * [66] H. Umemura, Painlevé equations in the past 100 Years, A.M.S. Translations, 204 (2001) 81–110.
  * [67] H. Umemura, Special polynomials associated with the Painlevé equations I, Ann. Fac. Sci. Toulouse Math. (6), 29 (2020) 1063–1089.
  * [68] P.R. Vein and P. Dale, Determinants and Their Applications in Mathematical Physics, Springer-Verlag, New York, 1999.
  * [69] A.P. Veselov and A.B. Shabat, A dressing chain and the spectral theory of the Schrödinger operator, Funct. Anal. Appl., 27 (1993) 1–21.
  * [70] A.P. Vorob’ev, On rational solutions of the second Painlevé equation, Diff. Eqns., 1 (1965) 58–59.
  * [71] H. Watanabe, Solutions of the fifth Painlevé equation I, Hokkaido Math. J., 24 (1995) 231–267.
  * [72] M. Wildon, Counting partitions on the abacus, Ramanujan J., 17 (2008) 355–367.
  * [73] Y. Yamada, Special polynomials and generalized Painlevé equations, in: Combinatorial Methods in Representation Theory, K. Koike, M. Kashiwara, S. Okada, I. Terada and H.F. Yamada (Editors), Adv. Stud. Pure Math., 28, Kinokuniya, Tokyo, Japan, pp. 391–400, 2000.
  * [74] A.I. Yablonskii, On rational solutions of the second Painlevé equation, Vesti Akad. Navuk. BSSR Ser. Fiz. Tkh. Nauk., 3 (1959) 30–35.