# Ramsey Numbers of Trails

Masatoshi Osumi The University of Electro-Communications

###### Abstract

We initiate the study of Ramsey numbers of trails. Let $k\geq 2$ be a positive
integer. The Ramsey number of trails with $k$ vertices is defined as the the
smallest number $n$ such that for every graph $H$ with $n$ vertices, $H$ or
the complete $\overline{H}$ contains a trail with $k$ vertices. We prove that
the Ramsey number of trails with $k$ vertices is at most $k$ and at least
$2\sqrt{k}+\Theta(1)$. This improves the trivial upper bound of $\lfloor
3k/2\rfloor-1$.

##  1 Introduction

Ramsey theory is one of the topics in discrete mathematics that has been
studied over the years [1, 3]. For graphs, the Ramsey number was first studied
for complete graphs, and later it was studied for other classes of graphs such
as paths, cycles, and trees. For graphs $G$ and $G^{\prime}$, the Ramsey
number of the pair $(G,G^{\prime})$ is the smallest number $n$ such that for
every graph $H$ with $n$ vertices, $H$ contains a copy of $G$ or the
complement $\overline{H}$ contains a copy of $G^{\prime}$. It is known that
for every pair $(G,G^{\prime})$ of finite graphs, the Ramsey number of
$(G,G^{\prime})$ exists, and the determination of the Ramsey number is the
ultimate goal. However, even for complete graphs, the exact Ramsey number is
not known: When $G=G^{\prime}=K_{5}$ we only know that the Ramsey number lies
between $43$ and $48$ [4].

In this paper, we initiate the study of Ramsey numbers for trails. Unlike
paths, trails may have a repetition of vertices. To study the Ramsey number of
trails, we first fix the number of vertices in a trail. Let $k$ and $\ell$ be
integers. Then, the Ramsey number of trails with $k$ vertices and $\ell$
vertices is defined as the smallest number $n$ such that for every graph $H$
with $n$ vertices, $H$ contains a trail with $k$ vertices or $\overline{H}$
contains a trail with $\ell$ vertices.

The ultimate goal is to determine the Ramsey number of trails. Unfortunately,
we are unable to provide a definite answer. Nonetheless, we give a progress
toward the ultimate goal. We concentrate on the diagonal case, i.e., the case
where $k=\ell$. Our main theorems give an improved upper bound of $k$, and
also a lower bound of roughly $2\sqrt{k}$. We note here that a trivial upper
bound is $\lfloor 3k/2\rfloor-1$, which will be sketched in the next section.

##  2 Preliminaries

In this paper, all graphs are finite, simple and undirected. A _graph_ $G$ is
defined as a pair $(V,E)$ of a finite set $V$ and $E\subseteq\\{\\{u,v\\}\mid
u,v\in V,u\neq v\\}$, where $V$ is the set of _vertices_ of $G$ and $E$ is the
set of _edges_ of $G$. The _degree_ of a vertex $v\in V$ is the number of
edges incident to $v$, i.e., $|\\{e\in E\mid v\in e\\}|$.

A graph $G^{\prime}=(V^{\prime},E^{\prime})$ is a _subgraph_ of a graph
$G=(V,E)$ if $V^{\prime}\subseteq V$, $E^{\prime}\subseteq E$ and $u,v\in
V^{\prime}$ for every $e=\\{u,v\\}\in E^{\prime}$. For a graph $G=(V,E)$, the
_complement_ of $G$, denoted by $\overline{G}$, is a graph with vertex set $V$
and edge set $\overline{E}=\\{\\{u,v\\}\mid u,v\in V,u\neq v,\\{u,v\\}\notin
E\\}$. Namely, $\overline{G}=(V,\overline{E})$. A pair $(G,H)$ of graphs is
called _complementary_ if $H=\overline{G}$.

A graph is A _complete_ if each pair of vertices is joined by an edge. The
complete graph with $n$ vertices is denote by $K_{n}$. A graph $P=(V,E)$ is a
_path_ if $V=\\{v_{1},v_{2},\dots,v_{n}\\}$, and $E=\\{\\{v_{i},v_{i+1}\\}\mid
i\in\\{1,2,\dots,n-1\\}\\}$. The path with $n$ vertices is denote by $P_{n}$.

A _walk_ is a sequence $v_{1}e_{1}v_{2}\dots e_{k-1}v_{k}$ of vertices $v_{i}$
and edges $e_{i}$ such that for $1\leq i\leq k$, the edge
$e_{i}=\\{v_{i},v_{i+1}\\}$. Here, $k$ is the number of vertices of the walk,
$v_{1}$ and $v_{k}$ are called endpoints. A _trail_ is a walk in which all the
edges are different from each other. A trail that satisfies $v_{1}=v_{k}$ is
called a _circuit_. A graph is _connected_ if it has a trail from any vertex
to any other vertex.

Let $G$ be a connected graph. An _Eulerian circuit_ of $G$ is a circuit of $G$
that passes every edge exactly once. If $G$ has an Eulerian circuit, then $G$
is called _Eulerian_. An _Eulerian trail_ of $G$ is a trail of $G$ that passes
every edge exactly once. If $G$ has an Eulerian trail but no Eulerian circuit,
then $G$ is called a _semi-Eulerian_. It is well-known and easy to prove that
a connected graph $G$ is Eulerian if and only if the degree of every vertex of
$G$ is even, and $G$ is semi-Eulerian if and only if the number of odd-degree
vertices is two.

For $k\geq 1$, we denote by $\mathcal{T}_{k}$ the set of connected graphs that
have an Eulerian circuit or an Eulerian trail with $k$ vertices. Note that in
our definitions, vertices in trails and circuits are counted multiple times if
they are passed multiple times. Therefore, some graphs in $\mathcal{T}_{k}$
may have less than $k$ vertices.

Figure 1: Graphs in $\mathcal{T}_{4}$. Note that the right graph has only
three vertices, but it has a trail with four vertices.

Let $\mathcal{C}$ and $\mathcal{C}^{\prime}$ be two graph classes, i.e.,
possibly infinite sets of graphs. Then, the _Ramsey number_ of $\mathcal{C}$
and $\mathcal{C}^{\prime}$ is the smallest number $n$ such that for every
graph $H$ with $n$ vertices, $H$ contains a graph in $\mathcal{C}$ or
$\overline{H}$ contains a graph in $\mathcal{C}^{\prime}$. The Ramsey number
of $\mathcal{C}$ and $\mathcal{C}^{\prime}$ is denoted by
$R(\mathcal{C},\mathcal{C}^{\prime})$. If $\mathcal{C}$ and
$\mathcal{C}^{\prime}$ are singletons (i.e., contain only one graph as
$\mathcal{C}=\\{G\\}$ and $\mathcal{C}^{\prime}=\\{G^{\prime}\\}$), then the
Ramsey number of $\mathcal{C}$ and $\mathcal{C}^{\prime}$ is denoted by
$R(G,G^{\prime})$.

Gerencsér and Gyárfás [2] determined the exact value of the Ramsey number of
paths, as in the following theorem.

######  Lemma 1 ([2]).

Let $k\geq\ell\geq 2$. Then, $R(P_{k},P_{\ell})=k+\lfloor\ell/2\rfloor-1$.

Since $P_{k}$ belongs to $\mathcal{T}_{k}$,
$R(\mathcal{T}_{k},\mathcal{T}_{k})\leq R(P_{k},P_{k})=k+\lfloor
k/2\rfloor-1=\lfloor 3k/2\rfloor-1$. This is the trivial upper bound mentioned
in the previous section.

To gain the first impression, we have conducted a computer search of the
Ramsey number $R(\mathcal{T}_{k},\mathcal{T}_{k})$ for small values of $k$.
This has been performed with the following procedure. For $2\leq n\leq 7$, we
generate all graphs $G$ with $n$ vertices. For each such $G$, we calculate
$\mathrm{t}(G)$, which is defined as the number of vertices in the longest
trail in $G$ or $\overline{G}$. Then, we determine $\mathrm{value}(n)$, which
is defined as the minimum value of $\mathrm{t}(G)$ for all $G$ with $n$
vertices. If $k$ satisfies $\mathrm{value}(n-1)<k\leq\mathrm{value}(n)$, then
we know that $R(\mathcal{T}_{k},\mathcal{T}_{k})$ is equal to $n$.

The result of the computer search is summarized in Table 1. We may observe
that the upper bound of $\lfloor 3k/2\rfloor-1$ should be improved.

Table 1: The values of $R(\mathcal{T}_{k},\mathcal{T}_{k})$. $k$ | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---|---|---|---|---|---|---|---|---|---
$R(\mathcal{T}_{k},\mathcal{T}_{k})$ | 2 | 3 | 4 | 5 | 6 | 6 | 6 | 7 | 7

##  3 Main Theorem: Lower Bound

We begin with a lower bound of $R(\mathcal{T}_{k},\mathcal{T}_{k})$.

######  Theorem 1.

Let $k$ be a positive integer. Then,

$\displaystyle R(\mathcal{T}_{k},\mathcal{T}_{k})\geq\begin{cases}k&\text{if
}k\leq 6,\\\
\displaystyle\left\lceil\frac{1+\sqrt{16k-7}}{2}\right\rceil&\text{if }k\geq
7.\\\ \end{cases}$

The rest of the section is devoted to the proof of Theorem 1. We first
consider the case when $k\leq 6$.

Let $k=2$. Then, there is no graph of $\mathcal{T}_{2}$ in the complete graph
$K_{1}$. Therefore, $R(\mathcal{T}_{2},\mathcal{T}_{2})\geq 2$.

Let $k=3$. Then, the complete graph $K_{2}$ has only one edge. So, there is no
graph of $\mathcal{T}_{3}$ in $K_{2}$. Thus,
$R(\mathcal{T}_{3},\mathcal{T}_{3})\geq 3$.

Let $k=4$. Consider the complementary pair of graphs with three vertices as
shown in Figure 2. Since those two graphs have at most two edges, no element
of $\mathcal{T}_{4}$ is contained in either graph. Therefore,
$R(\mathcal{T}_{4},\mathcal{T}_{4})\geq 4$.

Figure 2: A complementary pair of graphs that contain no elements of
$\mathcal{T}_{4}$.

Let $k=5$. Consider the complementary pair of graphs with four vertices as
shown in Figure 3. Since those two graphs have three edges, no element of
$\mathcal{T}_{5}$ is contained in either graph. Hence,
$R(\mathcal{T}_{5},\mathcal{T}_{5})\geq 5$.

Figure 3: A complementary pair of graphs that contain no elements of
$\mathcal{T}_{5}$.

Let $k=6$. Consider the complementary pair of graphs with five vertices as
shown in Figure 4. Those graphs have five edges. Hence, for an element of
$\mathcal{T}_{6}$ to be contained in either of the two graphs, one of the two
graphs must be Eulerian or semi-Eulerian. However, each graph has four odd-
degree vertices. Thus, these graphs are neither Eulerian nor semi-Eulerian,
and have no elements of $\mathcal{T}_{6}$.

Figure 4: A complementary pair of graphs that contain no elements of
$\mathcal{T}_{6}$.

Next, we consider the case where $k\geq 7$. To complete the proof, we use the
following two lemmas.

######  Lemma 2.

The number of vertices of a complete graph with $m\geq 0$ edges is
$(1+\sqrt{1+8m})/2$.

###### Proof.

Let $n\geq 1$ be the number of vertices of a complete graph with $m$ edges. In
this case, $m=n(n-1)/2$. Solving for $n\geq 1$, we have $n=(1+\sqrt{1+8m})/2$.
∎

######  Lemma 3.

Let $k\geq 7$ and let $n$ be such that the complete graph $K_{n}=(V,E)$ has at
most $2k-2$ edges. Then, there exists a subgraph $G=(V,E_{1})$ of $K_{n}$ such
that $G$ and $\overline{G}$ have no element of $\mathcal{T}_{k}$.

Before proving Lemma 3, we finish the proof of Theorem 1 using Lemmas 2 and 3.

###### Proof of Theorem 1 when $k\geq 7$..

Let $k\geq 7$ and let $n$ be the number of vertices of a complete graph with
at most $2k-1$ edges. Then, $R(\mathcal{T}_{k},\mathcal{T}_{k})\geq n$ from
Lemma 3. Therefore, by Lemma 2

$R(\mathcal{T}_{k},\mathcal{T}_{k})\geq\left\lceil\frac{1+\sqrt{1+8(2k-1)}}{2}\right\rceil=\left\lceil\frac{1+\sqrt{16k-7}}{2}\right\rceil.\qed$

Thus, it suffices to prove Lemma 3.

###### Proof of Lemma 3..

We distinguish the cases $|E|\leq 2k-4$, $|E|=2k-3$ and $|E|=2k-2$.

### Case 1: $|E|\leq 2k-4$.

Choose $G=(V,E_{1})$ as any subgraph with
$|E_{1}|=\left\lceil|E|/2\right\rceil$. Then, since
$|E_{1}|=\left\lceil|E|/2\right\rceil\leq
k-2,|E-E_{1}|=\left\lfloor|E|/2\right\rfloor\leq k-2$, it follows that $G$ and
$\overline{G}$ have no element of $\mathcal{T}_{k}$.

### Case 2: $|E|=2k-3$.

Consider a complete graph $K_{n}$ with $2k-3$ edges. Then,

$n=\frac{1+\sqrt{1+8(2k-3)}}{2}=\frac{1+\sqrt{16k-23}}{2}>5$

from Lemma 2. Let $v_{1},\dots,v_{n}$ be the vertices of $K_{n}$, and let
$E_{c}=\\{\\{v_{i},v_{i+1}\\}\mid i=1,2,\dots,n-1\\}\cup\\{v_{n},v_{1}\\}$.
Then, the graph $C=(V,E_{c})$ is a cycle contained in $K_{n}$. We construct an
Eulerian or a semi-Eulerian graph $S$ with $k+1$ edges that contains $C$.

Before constructing such $S$, we observe that this is enough for our purpose.
Since $S$ contains $C$ and $n\geq 6$, there exist two edges $e_{1},e_{2}$ of
$C$ such that $S^{\prime}=S-\\{e_{1},e_{2}\\}$ has exactly four odd-degree
vertices. Thus, $S^{\prime}$ is neither Eulerian nor semi-Eulerian. Since
$S^{\prime}$ has only $k-1$ edges, $S^{\prime}$ include no element of
$\mathcal{T}_{k}$. Further, $\overline{S^{\prime}}$ has only $k-2$ edges, and
$\overline{S^{\prime}}$ includes no element of $\mathcal{T}_{k}$, either.

To find a subgraph $S$ with the desired properties, we further distinguish two
cases according to the parity of $n$.

### Case 2-1: $n$ is odd.

Let $G=(V,E-E_{c})$. Then, $G$ is Eulerian since the degree of each vertex of
$G$ is even and $G$ is connected. Thus, $G$ contains a trail with
$|E|-n+1=2k-2-n\geq k+2-n$ vertices. Let $T$ be a subgraph of $G$ obtained by
the first $k+1-n$ edges of such a trail, and let $S=C\cup T$. Then, $S$ is
Eulerian or semi-Eulerian with $k+1$ edges.

### Case 2-2: $n$ is even.

Let $G=(V,E-E_{c}-\\{\\{v_{i},v_{n/2+i}\\}\mid i=1,2,\dots,n/2\\})$. Then, $G$
is Eulerian since the degree of each vertex of $G$ is even and $G$ is
connected.

Thus, $G$ contains a trail with $|E|-3n/2+1=2k-2-3n/2\geq k+2-n$ vertices
since $n>5$ and $n(n-1)/2=2k-3$. Let $T$ be a subgraph of $G$ obtained by the
first $k+1-n$ edges of such a trail, and let $S=C\cup T$. Then, $S$ is
Eulerian or semi-Eulerian with $k+1$ edges.

### Case 3: $|E|=2k-2$.

This case is analogous to Case 2 where $|E|=2k-3$. Note that for a complete
graph $K_{n}$ with $2k-2$ edges. we have
$n=(1+\sqrt{1+8(2k-2)})/2=(1+\sqrt{16k-15})/2>5$ from Lemma 2.

We have to take care of the argument after constructing $S$ because
$\overline{S^{\prime}}$ has $k-1$ edges and we need a different argument to
show that $\overline{S^{\prime}}$ includes no element of $\mathcal{T}_{k}$.
Remind that $S^{\prime}$ contains $k-1$ edges from a trail of $G$ and the
edges of $C$.

We distinguish two cases according to the parity of $n$. First, let $n$ be
odd. Then, the degree of every vertex of $K_{n}$ is even. Since $S^{\prime}$
has four odd-degree vertices, $\overline{S^{\prime}}$ has four odd-degree
vertices, too. Thus, $\overline{S^{\prime}}$ is neither Eulerian nor semi-
Eulerian. Since $\overline{S^{\prime}}$ has only $k-1$ edges,
$\overline{S^{\prime}}$ includes no element of $\mathcal{T}_{k}$.

Next, let $n$ be even. We first observe that $n\geq 8$. We already know that
$n\geq 6$, but if $n=6$, then the number of edges of $K_{n}$ is $15$, which is
not of the form $2k-2$: this is impossible. Therefore, $\overline{S^{\prime}}$
has at least four odd-degree vertices since $S^{\prime}$ has $n-4$ even-degree
vertices and $n-4\geq 4$. Thus, $\overline{S^{\prime}}$ is neither Eulerian
nor semi-Eulerian. Since $\overline{S^{\prime}}$ has only $k-1$ edges,
$\overline{S^{\prime}}$ includes no element of $\mathcal{T}_{k}$. ∎

##  4 Main Theorem: Upper Bound

We already observed that $R(\mathcal{T}_{k},\mathcal{T}_{k})\leq\lfloor
3k/2\rfloor-1$ as a trivial upper bound. Now, we improve the upper bound in
the next theorem.

######  Theorem 2.

For every integer $k\geq 2$,

$R(\mathcal{T}_{k},\mathcal{T}_{k})\leq k.$

To this end, for any graph $G$ with $k$ vertices, we prove either $G$ or its
complement $\overline{G}$ contains a trail with $k$ vertices.

We begin with the following lemma which will be used in the proof of the
theorem.

######  Lemma 4.

Let $G=(V,E)$ be a bipartite graph with partite sets $A$ and $B$, i.e., $A\cup
B=V$, $A\cap B=\emptyset$ and each edge of $G$ joins a vertex of $A$ and a
vertex of $B$. If $|A|=3$ and the degree of every vertex of $B$ is two, then
$G$ contains a trail such that both endpoints belong to $A$ and the number of
edges is $2|B|$.

###### Proof.

Denote the three elements of $A$ by $a_{1}$,$a_{2}$, and $a_{3}$. We
distinguish the following two cases according to the existence of an isolated
vertex (i.e., a vertex of degree zero) in $A$.

### Case 1: $A$ has an isolated vertex.

Without loss of generality, assume that $a_{3}$ is an isolated vertex. Since
each vertex in $B$ has degree two, it is adjacent to $a_{1}$ and $a_{2}$.
Hence, the bipartite graph $G^{\prime}=G-a_{3}$ is connected. Furthermore, the
number of odd-degree vertices in $G^{\prime}$ is zero or two since the degree
of $a_{1}$ and $a_{2}$ is $|B|$, and the degree of every vertex in $B$ is two.
Thus, $G^{\prime}$ is Eulerian or semi-Eulerian and has $2|B|$ edges. When
$G^{\prime}$ is Eulerian, $G^{\prime}$ contains a trail with $2|B|$ edges such
that both endpoints coincide with $a_{1}$. When $G^{\prime}$ is semi-Eulerian,
$G^{\prime}$ contains a trail with $2|B|$ edges such that one endpoint is
$a_{1}$ and the other endpoint is $a_{2}$.

### Case 2: $A$ has no isolated vertex.

Without loss of generality, assume that there exists a vertex $b\in B$
adjacent to $a_{1}$ and $a_{2}$. Since there is no isolated vertex, there is a
vertex $b^{\prime}\in B$ adjacent to $a_{3}$. As the degree of $b^{\prime}$ is
two, $b^{\prime}$ is adjacent to either $a_{1}$ or $a_{2}$. Therefore, the
three vertices of $a_{1}$, $a_{2}$ and $a_{3}$ are connected by paths. This
implies that $G$ is connected since every vertex in $B$ is adjacent to one of
$a_{1}$, $a_{2}$ and $a_{3}$. Since $G$ is bipartite and the degree of every
vertex in $B$ is two, the sum of the degrees of $a_{1}$, $a_{2}$ and $a_{3}$
is even. If there are an odd number of odd-degree vertices in $A$, then the
sum of the degrees of $a_{1}$, $a_{2}$ and $a_{3}$ is odd, contradicting the
fact that the sum of the degrees of $a_{1}$, $a_{2}$ and $a_{3}$ is even.
Therefore, the number of odd-degree vertices is zero or two.

When there is no odd-degree vertex, then $G$ is Eulerian, and contains a trail
with $2|B|$ edges such that both endpoints coincide with $a_{1}$. When there
are two odd-degree vertices, let them be $a_{s}$ and $a_{t}$. Then, $G$ is
semi-Eulerian, and contains a trail with $2|B|$ edges such that one endpoint
is $a_{s}$ and the other endpoint is $a_{t}$. ∎

We are now ready for the proof of Theorem 2.

###### Proof of Theorem 2..

The proof uses the induction on $k$. When $k\leq 10$,
$R(\mathcal{T}_{k},\mathcal{T}_{k})$ holds from Table 1.

Now, fix an arbitrary integer $k\geq 11$ and suppose that the statement is
true for $k^{\prime}<k$. Consider a graph $G=(V,E)$ with $k$ vertices. For a
subgraph $G^{\prime}$ with $k-1$ vertices of $G$, by induction hypothesis,
either $G^{\prime}$ or $\overline{G^{\prime}}$ contains a trail $S$ with $k-1$
vertices. If $G^{\prime}$ contains $S$, then $G$ contains $S$ because
$G^{\prime}$ is a subgraph of $G$. If $\overline{G^{\prime}}$ contains $S$,
then $\overline{G}$ contains $S$ because $\overline{G^{\prime}}$ is a subgraph
of $\overline{G}$. Therefore, either $G$ or $\overline{G}$ contains $S$.
Without loss of generality, suppose $G$ contains $S$. Let
$S=u_{1}e_{1}u_{2}e_{2}\dots e_{k-2}u_{k-1}$ where $e_{i}=\\{u_{i},u_{i+1}\\}$
for all $i\in\\{1,2,\dots,k-2\\}$, $U=\\{u_{1},u_{2},\dots,u_{k-1}\\}$ be the
set of vertices in $S$, and $W=V-U$. Note that the size of $U$ can be smaller
than $k-1$ since some vertices can be identical.

If there exists a vertex $w\in W$ such that $\\{u_{1},w\\}\in E$, then $G$
contains the trail $w\\{w,u_{1}\\}S$ with $k$ vertices. Similarly, if there
exists a vertex $w\in W$ such that $\\{u_{k-1},w\\}\in E$, then $G$ contains
the trail $S\\{u_{k-1},w\\}w$ with $k$ vertices. If there is a vertex $u\in U$
such that $\\{u,u_{1}\\}\in E$ is not included in $S$, then $G$ contains the
trail $u\\{u,u_{1}\\}S$ with $k$ vertices. Similarly, if there is a vertex
$u\in U$ such that $\\{u,u_{k-1}\\}\in E$ is not included in $S$, then $G$
contains the trail $S\\{u_{k-1},u\\}u$ with $k$ vertices. In all of these
cases, $G$ contains a trail with $k$ vertices and we are done.

Hence, we only need to consider the cases where the following two conditions
are satisfied.

Condition 1.

For every $w\in W$, $\\{u_{1},w\\}\notin E$ and $\\{u_{k-1},w\\}\notin E$.
That is, $\\{u_{1},w\\}\in\overline{E}$ and $\\{u_{k-1},w\\}\in\overline{E}$.

Condition 2.

For every $u\in U$, if $\\{u,u_{1}\\}$ is not included $S$, then
$\\{u,u_{1}\\}\notin E$. That is, $\\{u,u_{1}\\}\in\overline{E}$. If
$\\{u,u_{k-1}\\}$ is not included $S$, then $\\{u,u_{k-1}\\}\notin E$. That
is, $\\{u,u_{k-1}\\}\in\overline{E}$.

We distinguish the cases according to the “shape” of $S$.

### Case 1: $S$ is a path.

Since $S$ is a path, $S$ contains no repeated vertex. Therefore, $|U|=k-1$ and
$|W|=1$. Let $w$ be the only vertex in $W$. Since $S$ contains no repeated
vertex, for $3\leq i\leq k-1$, the edges $\\{u_{i},u_{1}\\}$ are not included
in $S$. Also, for $1\leq i\leq k-3$, the edges $\\{u_{i},u_{k-1}\\}$ are not
included in $S$. From Condition 2, $\\{u_{1},u_{k-1}\\}\in\overline{E}$ and
for $3\leq i\leq k-3$, $\\{u_{1},u_{i}\\}\in\overline{E}$ and
$\\{u_{k-1},u_{i}\\}\in\overline{E}$. Consider a subgraph
$G^{\prime}=(V^{\prime},E^{\prime})$ of $\overline{G}$, where
$V^{\prime}=V-\\{u_{2},u_{k-2}\\}$ and
$E^{\prime}=\\{\\{u_{1},u_{i}\\},\\{u_{k-1},u_{i}\\}\mid
i\in\\{3,4,\dots,k-3\\}\\}\cup\\{\\{u_{1},w\\},\\{u_{k-1},w\\},\\{u_{1},u_{k-1}\\}\\}$.
Each vertex of $V^{\prime}$ except $u_{1}$ is adjacent to $u_{1}$. Hence,
$G^{\prime}$ is connected. Further, since the degree of each vertex in
$V^{\prime}$ except $u_{1}$ and $u_{k-1}$ is two, and the degrees of $u_{1}$
and $u_{k-1}$ are $|V|-3$, the number of odd-degree vertices in $G^{\prime}$
is zero or two. Therefore, $G^{\prime}$ is Eulerian or semi-Eulerian. Since
$G^{\prime}$ has $2k-7$ edges, $G^{\prime}$ contains a trail $T$ with
$2k-6\geq k$ vertices. Since $G^{\prime}$ is a subgraph of $\overline{G}$, we
conclude that $\overline{G}$ contains $T$.

### Case 2: $S$ is a circuit.

When $S$ is a circuit, $u_{1}=u_{k-1}$. Therefore, $|U|\leq k-2$ and
$|W|=k-|U|\geq 2$. Denote the elements of $W$ by $w_{1},w_{2},\dots,w_{|W|}$.

If there exist $w\in W$ and $u_{i}\in U$ such that $\\{w,u_{i}\\}\in E$, then
we have a trail

$T=w\\{w,u_{i}\\}u_{i}e_{i}u_{i+1}\dots u_{k-1}e_{1}u_{2}\dots u_{i}$

since $u_{1}=u_{k-1}$. Note that $T$ has $k$ vertices. Therefore, $G$ contains
a trail with $k$ vertices.

Hence, we only need to consider the situation where $\\{w,u\\}\notin E$, i.e.,
$\\{w,u\\}\in\overline{E}$ for every $w\in W$ and every $u\in U$. We
distinguish two cases according to the comparison of $|U|$ and $|W|$.

### Case 2-1: $|U|\geq|W|$.

Choose two vertices $w_{1},w_{2}\in W$ arbitrarily, and let
$V^{\prime}=U\cup\\{w_{1},w_{2}\\}$ and
$E^{\prime}=\\{\\{w_{1},u\\},\\{w_{2},u\\}\mid u\in
U\\}\subseteq\overline{E}$. Consider the subgraph
$G^{\prime}=(V^{\prime},E^{\prime})$ of $\overline{G}$. Then, $G^{\prime}$ is
connected since every vertex in $U$ is adjacent to $w_{1}$ and $w_{2}$. The
degree of every vertex in $U$ is two, and the degree of $w_{1}$ and $w_{2}$
are both $|U|$. Hence, the number of odd-degree vertices in $G^{\prime}$ is
zero or two. Therefore, $G^{\prime}$ is Eulerian or semi-Eulerian. Since
$G^{\prime}$ has $2|U|$ edges, $G^{\prime}$ contains a trail $T$ with
$2|U|+1\geq|U|+|W|+1=|U|+(k-|U|)+1=k+1$ vertices. Since $G^{\prime}$ is a
subgraph of $\overline{G}$, we conclude that $\overline{G}$ contains $T$.

### Case 2-2: $|U|\leq|W|$.

If $|U|<2$, then the number of vertices in $S$ is less than 1, which
contradicts the fact that the number of vertices in $S$ is $k-1\geq 10$.
Therefore, $|U|\geq 2$. Choose two vertices $a,b\in U$ arbitrarily, and let
$V^{\prime}=W\cup\\{a,b\\}$ and $E^{\prime}=\\{\\{w,a\\},\\{w,b\\}\mid w\in
W\\}\subseteq\overline{E}$. Consider the subgraph
$G^{\prime}=(V^{\prime},E^{\prime})$ of $\overline{G}$. Since every vertex in
$W$ is adjacent to $a$ and $b$, $G^{\prime}$ is connected. The degree of every
vertex in $W$ is two, and the degree of $a$ and $b$ are both $|W|$. Hence, the
number of odd-degree vertices in $G^{\prime}$ is zero or two. Therefore,
$G^{\prime}$ is Eulerian or semi-Eulerian. Since $G^{\prime}$ has $2|W|$
edges, $G^{\prime}$ contains a trail $T$ with
$2|W|+1\geq|U|+|W|+1=|U|+(k-|U|)+1=k+1$ vertices. Since $G^{\prime}$ is a
subgraph of $\overline{G}$, we conclude that $\overline{G}$ contains $T$.

### Case 3: $S$ is not a path or a circuit.

Since $S$ is not a path, $|U|\leq k-2$. Since $S$ is not a circuit, $u_{1}\neq
u_{k-1}$. We distinguish cases according to the size of $U$.

### Case 3-1: $|U|=k-2$.

Since $S$ is a trail with $k-1$ vertices and $|U|=k-2$, there is only one
vertex $x$ that is used more than once in $S$. If $x\neq u_{1}$ and $x\neq
u_{k-1}$, then there are at most two vertices adjacent to either $u_{1}$ or
$u_{k-1}$ in $G$. If $x$ is $u_{1}$ or $u_{k-1}$, then there are at most four
vertices adjacent to either $u_{1}$ or $u_{k-1}$ in $G$.

Let $U^{\prime}$ be the set of elements of $U-\\{u_{1},u_{k-1}\\}$ that are
not adjacent to either $u_{1}$ or $u_{k-1}$ in $G$. Every vertex
$u^{\prime}\in U^{\prime}$ satisfies $\\{u^{\prime},u_{1}\\}\notin E$ and
$\\{u^{\prime},u_{k-1}\\}\notin E$, i.e.
$\\{u^{\prime},u_{1}\\}\in\overline{E}$ and
$\\{u^{\prime},u_{k-1}\\}\in\overline{E}$. Further,
$|U^{\prime}|\geq|U-\\{u_{1},u_{k-1}\\}|-4=|U|-2-4=k-8$. From Condition 1, for
each vertex $w\in W$, we have $\\{u_{1},w\\}\in\overline{E}$ and
$\\{u_{k-1},w\\}\in\overline{E}$. Let $V^{\prime}=U^{\prime}\cup
W\cup\\{u_{1},u_{k-1}\\}$, $E^{\prime}=\\{\\{w,u_{1}\\},\\{w,u_{k-1}\\}\mid
w\in W\\}\cup\\{\\{u_{1},u^{\prime}\\},\\{u_{k-1},u^{\prime}\\}\mid
u^{\prime}\in U^{\prime}\\}\subseteq\overline{E}$ and consider the subgraph
$G^{\prime}=(V^{\prime},E^{\prime})$ of $\overline{G}$. Since every vertex in
$U^{\prime}\cup W$ is adjacent to $u_{1}$ and $u_{k-1}$, $G^{\prime}$ is
connected. The degree of every vertex in $U^{\prime}\cup W$ is two, and the
degree of $u_{1}$ and $u_{k-1}$ are both $|U^{\prime}|+|W|$. Hence, the number
of odd-degree vertices in $G^{\prime}$ is zero or two. Therefore, $G^{\prime}$
is Eulerian or semi-Eulerian. Since $G^{\prime}$ has $2(|U^{\prime}|+|W|)$
edges, $G^{\prime}$ contains a trail $T$ with $2(|U^{\prime}|+|W|)+1\geq
2(k-8+2)+1=2k-11\geq k$ vertices. Since $G^{\prime}$ is a subgraph of
$\overline{G}$, we conclude that $\overline{G}$ contains $T$.

### Case 3-2: $|U|\leq\left\lfloor k/2\right\rfloor$.

From Condition 1, for each vertex $w\in W$, we have
$\\{u_{1},w\\}\in\overline{E}$ and $\\{u_{k-1},w\\}\in\overline{E}$. Let
$V^{\prime}=W\cup\\{u_{1},u_{k-1}\\}$,
$E^{\prime}=\\{\\{w,u_{1}\\},\\{w,u_{k-1}\\}\mid w\in
W\\}\subseteq\overline{E}$ and consider the subgraph
$G^{\prime}=(V^{\prime},E^{\prime})$ of $\overline{G}$. Since every vertex in
$W$ is adjacent to $u_{1}$ and $u_{k-1}$, $G^{\prime}$ is connected. The
degree of every vertex in $W$ is two, and the degree of $u_{1}$ and $u_{k-1}$
are both $|W|$. Hence, the number of odd-degree vertices in $G^{\prime}$ is
zero or two. Therefore, $G^{\prime}$ is Eulerian or semi-Eulerian. Since
$G^{\prime}$ has $2|W|$ edges, $G^{\prime}$ contains a trail $T$ with
$2|W|+1\geq 2\left\lceil k/2\right\rceil+1\geq k+1$ vertices. Since
$G^{\prime}$ is a subgraph of $\overline{G}$, we conclude that $\overline{G}$
contains $T$.

### Case 3-3: $\left\lfloor k/2\right\rfloor<|U|\leq k-3$.

By the induction hypothesis, in $G$ or $\overline{G}$, there exists a trail
$T$ with $|W|\geq 3$ vertices such that every vertex in $T$ is an element of
$W$. Let $T=w_{1}e^{\prime}_{1}w_{2}e^{\prime}_{2}\dots
e^{\prime}_{|W|-1}w_{|W|}$ with
$e^{\prime}_{i}=\\{w_{i},w_{i+1}\\},i\in\\{1,2,\dots,|W|-1\\}$ and
$W^{\prime}$ be the set of vertices used in $T$.

We further distinguish two cases according to the containment of $T$ in $G$ or
$\overline{G}$.

### Case 3-3-1: $T$ is included in $G$.

Assume that there exists a vertex $u_{i}\in U$ adjacent to two vertices
$w_{x},w_{y}\in W^{\prime}$ where $w_{x}\neq w_{y},x<y$. Then, we have a trail

$S^{\prime}=u_{1}e_{1}u_{2}e_{2}\dots u_{i}\\{u_{i},w_{x}\\}w_{x}\dots
w_{y}\\{w_{y},u_{i}\\}u_{i}e_{i}\dots e_{k-2}u_{k-1}.$

The number of vertices of $S^{\prime}$ is at least $k$. Thus, we only need to
consider the case where, for every vertex $u\in U$, there exists at most one
element of $W^{\prime}$ adjacent to $u$ in $G$.

Let $w^{\prime}_{1}$, $w^{\prime}_{2}$ and $w^{\prime}_{3}$ be any three
different vertices of $W^{\prime}$. For every vertex $u\in U$, there exists at
most one element of $W^{\prime}$ adjacent to $u$ in $G$. Then, $u$ is adjacent
to at least two vertices of $w_{1}$,$w_{2}$, and $w_{3}$ in $\overline{G}$.
Therefore, $\overline{G}$ has the following bipartite graph $G^{\prime}$ as a
subgraph:

  * •

The partite sets of $G^{\prime}$ are
$A=\\{w^{\prime}_{1},w^{\prime}_{2},w^{\prime}_{3}\\}$ and $B=U$;

  * •

The degree of each vertex in $B$ is two.

From Lemma 4, $G^{\prime}$ has a trail $X$ with $2|B|$ edges, i.e.,
$2|B|+1=2|U|+1>2\cdot\lfloor k/2\rfloor+1\geq k$ vertices. Since $G^{\prime}$
is a subgraph of $\overline{G}$, $\overline{G}$ also has $X$.

### Case 3-3-2: $T$ is included in $\overline{G}$.

Let $w^{\prime}_{1}$, $w^{\prime}_{2}$ and $w^{\prime}_{3}$ be any three
different vertices of $W^{\prime}$. First, assume that in $G$ there exist
three vertices $u_{x},u_{y},u_{z}\in U-\\{u_{1},u_{k-1}\\}$ that are adjacent
to at least two of the vertices $w^{\prime}_{1}$, $w^{\prime}_{2}$ and
$w^{\prime}_{3}$. Then, one of the graphs in Figure 5 always appears as a
subgraph of $G$. In both cases, there exists a cycle $C$ that has a vertex in
$U$. Therefore, we have a trail $S^{\prime}=u_{1}e_{1}u_{2}e_{2}\dots
e_{x-1}Ce_{x}\dots e_{k-2}u_{k-1}$, and the number of vertices of $S^{\prime}$
is at least $k$.

Figure 5: Two subgraphs of $G$ that can be constructed by
$w^{\prime}_{1},w^{\prime}_{2},w^{\prime}_{3},u_{x},u_{y}$ and $u_{z}$.

Second, assume there are at most two elements of $U-\\{u_{1},u_{k-1}\\}$ that
are adjacent to at least two vertices of $w^{\prime}_{1}$, $w^{\prime}_{2}$
and $w^{\prime}_{3}$ in $G$. Let $c$ and $d$ be those two vertices of
$U-\\{u_{1},u_{k-1}\\}$. Then, there is a subbipartite graph $G^{\prime}$ in
$\overline{G}$:

  * •

The partite sets of $G^{\prime}$ are
$A=\\{w^{\prime}_{1},w^{\prime}_{2},w^{\prime}_{3}\\}$ and
$B=U-\\{u_{1},u_{k-1},c,d\\}$;

  * •

The degree of each vertex in $B$ is two.

From Lemma 4, $G^{\prime}$ has a trail $X$ with $2|B|+1=2(|U|-4)+1$ vertices.
Let $s,t\in W^{\prime}$ be the endpoints of $X$. We now construct a trail
$T^{\prime}$ with $|W|$ vertices such that it only consists of the vertices
and edges used in $T$, and does not start at $t$. If $w_{1}\neq t$, then we
have $T^{\prime}=T$. If $w_{1}=t$ and $T$ is a circuit, then we have
$T^{\prime}=w_{2}e^{\prime}_{2}\dots
e^{\prime}_{|W|-1}w_{|W|}e^{\prime}_{1}w_{2}$ since $w_{1}=w_{|W|}$ and
$w_{1}\neq w_{2}$. If $w_{1}=t$ and $T$ is not a circuit, then we have
$T^{\prime}=w_{|W|}e^{\prime}_{|W|-1}w_{|W|-1}e^{\prime}_{|W|-2}\dots
e^{\prime}_{1}w_{1}$ since $w_{1}\neq w_{|W|}$. Therefore, $T^{\prime}$ can be
constructed.

Since $T$ is included in $\overline{G}$, $T^{\prime}$ is also included in
$\overline{G}$. Let $w,x$ be the endpoints of $T^{\prime}$. Then, we have a
trail $Y=X\\{t,u_{1}\\}u_{1}\\{u_{1},w\\}T^{\prime}\\{x,u_{k-1}\\}u_{k-1}$
with $2|U|+|W|-5$ edges. Hence, $Y$ is a trail with
$2|U|+|W|-4=2|U|+(k-|U|)-4=k+|U|-4>k+\lfloor k/2\rfloor-4\geq k$ vertices. ∎

##  5 Conclusion

From Theorems 1 and 2, we conclude that $R(\mathcal{T}_{k},\mathcal{T}_{k})=k$
when $k\leq 6$ and $2\sqrt{k}+\Theta(1)\leq
R(\mathcal{T}_{k},\mathcal{T}_{k})\leq k$ when $k\geq 7$.

Future work is to find stricter upper and lower bounds. Another challenge is
to find upper and lower bounds of $R(\mathcal{T}_{k},\mathcal{T}_{\ell})$ for
any $k$ and $\ell$.

## References

  * [1] R. L. Graham, B. L. Rothschild, J. H. Spencer, _Ramsey Theory_ , Wiley, 1990.
  * [2] L. Gerencsér, A. Gyárfás, On Ramsey-type problems, _Annales Universitatis Scientiarum Budapestinensis, Eötvös Sect. Math._ , 10 (1967): pp. 167–170.
  * [3] M. Katz, J. Reimann, _An Introduction to Ramsey Theory: Fast Functions, Infinity, and Metamathematics_. AMS, 2018.
  * [4] S. Radziszowski, Small Ramsey numbers, _The Electronic Journal of Combinatorics_ , DS1, Version 16 (2021).


[fieldsource=url, match={
_}—{_}—
_, replace=_] [fieldsource=url, match={$
sim$}—{}̃—$
sim$, replace=~] [fieldsource=url, match={
26}, replace=26]

# Single-Shot Global Localization via
Graph-Theoretic Correspondence Matching

Shigemichi Matsuzaki1, Kenji Koide2, Shuji Oishi2, Masashi Yokozuka2, and
Atsuhiko Banno2 *This work was supported in part by a project commissioned by
the New Energy and Industrial Technology Development Organization (NEDO). This
work was also supported by JSPS KAKENHI (Grant Number 22K12214). 1S. Matsuzaki
is with Department of Computer Science and Engineering, Toyohashi University
of Technology, Hibarigaoka 1-1, Tenpaku-cho, Toyohashi, Aichi, Japan
<EMAIL_ADDRESS>K. Koide, S. Oishi, M. Yokozuka, and A. Banno are
with the Department of Information Technology and Human Factors, the National
Institute of Advanced Industrial Science and Technology, Umezono 1-1-1,
Tsukuba, 3050061, Ibaraki, Japan<EMAIL_ADDRESS>
###### Abstract

This paper describes a method of single-shot global localization based on
graph-theoretic matching of instances between a query and the prior map. The
proposed framework employs correspondence matching based on the maximum clique
problem (MCP). The framework is potentially applicable to other map and/or
query modalities thanks to the graph-based abstraction of the problem, while
many of existing global localization methods rely on a query and the dataset
in the same modality. We implement it with a semantically labeled 3D point
cloud map, and a semantic segmentation image as a query. Leveraging the graph-
theoretic framework, the proposed method realizes global localization
exploiting only the map and the query. The method shows promising results on
multiple large-scale simulated maps of urban scenes.

##  I Introduction

Global localization is a problem to estimate a sensor pose in a prior map
given a sensor observation or a sequence of observations, which is referred to
as a query, and without prior information of its initial pose. It is a
fundamental ability of mobile robots and autonomous vehicles for reliable and
safe operation. For the task of global positioning, Global Navigation
Satellite System (GNSS) is widely used. It is known, however, that the utility
of GNSS is limited to open space without obstacles such as buildings, trees
etc. that cause multi-path effect.

Various approaches to global localization have been proposed in a last few
decades. In traditional Bayesian estimation such as Monte Carlo Localization
(MCL) [1], a match between sensor readings and the prior map is evaluated
through the observation model and incorporated as likelihood in iterative
computation of the belief score on the robot pose. Single-shot methods such as
global descriptor matching [2, 3] and local geometry matching [4, 5] instead
calculate the most likely pose given a single query. In the former, a single
global descriptor for the query is computed and used to retrieve from a
database the most similar descriptor associated with a pose. The latter
computes a set of descriptors that describe the local structure of the query,
and find their correspondence with pre-computed feature points in the map to
compute the pose via error minimization.

Overall, the global localization methods essentially require matching between
the query and the map. Regardless of the approaches, many of the existing
global localization methods assume the query and the map in the same modality,
i.e., the prior map must store data in the same representation as the query.
This fact limits the applicability of the methods to a wide variety of
different sensor and map modalities available. Recently, various map
representations have emerged, such as point cloud maps, high-definition vector
maps (HD maps), tagged maps like Google Map, etc. If those cross-modal data
can be handled by a unified method in global localization, more flexible
choices on the sensor and the map will be available for the global
localization problem.

Figure 1: Global localization is solved by estimating true correspondences
between instances in a query and those in the prior map. The proposed graph-
theoretic framework is potentially applicable to various query and map
modalities.

With such a prospect, we propose a framework of single-shot global
localization, formulating it as instance correspondence matching between the
query and the prior map and finding a pose in the map that best explains the
correspondences. For the correspondence matching, we employ a graph-theoretic
method that reduces the problem to the maximum clique problem (MCP).
Specifically, we construct a graph called a consistency graph that represents
local consistency between correspondence candidates, and find the most likely
set of correspondences via MCP on the consistency graph, similarly to [6] etc.
The motivation behind the formulation is to abstract the problem to a general
graph problem so that it is not constrained on a specific modality of the
query and the map. The proposed method can potentially be applied to cross-
modal global localization problems as long as a proper consistency criteria
can be defined.

In the present work, we implement the framework using 3D semantic point cloud
maps as a prior map and a semantic segmentation image as a query for
correspondence matching. The consistency of the correspondences are evaluated
based on the closeness in appearance from the pose calculated by a
correspondence pair. Thanks to the graph-theoretic framework, global
localization is realized with a combination of simple consistency criteria
that does not require additional data for training. The method thus exploits
only a 3D semantic map and a semantic segmentation query, in contrast to
recent existing methods [5, 7] that depend on data-driven descriptors for
correspondence matching. Our method can, therefore, be easily applied to
various environments.

##  II Related Work

###  II-A Global localization

There have been various approaches with different techniques and sensor
modalities.

Iterative methods Traditionally, global localization has been solved in
iterative algorithm such as Monte Carlo localization (MCL) [1] where the
belief on the robot’s pose gradually converges by incorporating a temporal
sequence of observations as the robot moves. This approach inherently requires
motion of the robot, which limits the use case of the methods. In the present
work, we opt for a single-shot global localization approach.

Global descriptor matching Global descriptor-based methods learn a
discriminative descriptor per scene from the sensor observations. The pose is
then estimated by matching the descriptor for the observation and pre-computed
set of descriptors associated with a pose. This line of work includes Visual
Place Recognition (VPR) [2, 3], geometry-based methods [8, 9], and hybrid
methods [10, 11].

Local geometry matching In visual global localization, another popular
approach is matching local visual features such as SIFT [12] and SURF [13]
between a query image and a pre-computed map and optimizing the pose based on
the feature correspondences [4, 14]. In 3D LiDAR-based geometry matching,
local point descriptors such as [15] and point segments [5, 7] are often used.

Semantics-based localization Following the recent progress of semantic
segmentation based on DNNs, global localization methods based on visual
semantic information have also been actively studied. Results of semantic
segmentation are reported to be more robust to appearance changes than low-
level visual information such as feature points [16]. Semantic information has
been, therefore, exploited to realize localization methods that are robust to
appearance changes over time and viewpoint changes [17].

DNN-based pose regression DNNs are also exploited to directly estimate a
sensor pose. Kendal et al. [18] first proposed to regress a 6 DOF pose
directly from an image. Feng et al. [19] jointly trained the descriptors for
2D images and 3D points to match data in those different modalities. This
approach, again, is specialized to the data on which the network is trained
and hard to apply to various scenes.

Problems in existing work and novelties of our work Regardless of the
approaches, most of the conventional methods use a query and a map in the same
modality. On the other hand, the proposed method does not strictly assume the
same modality. Our method, therefore, is potentially applicable to various
types of maps such as point cloud maps and HD vector maps.

Although some recent works use DNNs to learn a strong global/local descriptor
[2, 5], or to embed data from different modalities in a common feature space
[19], such methods require a huge amount of training data. Moreover, pose
regression using DNN is specialized to the data on which the model is trained,
and difficult to apply to various scenes.

Our primary purpose is to develop a novel unified framework for global
localization applicable to cross-modal settings. The pose is efficiently
estimated using the graph-theoretic correspondence matching and simple
criteria of appearance similarity. We show the effectiveness in an
implementation using a semantic point cloud map and a semantic segmentation
image.

###  II-B Correspondence matching

Correspondence matching is a crucial task for some of the aforementioned
methods. Random sample consensus (RANSAC) is traditionally used to extract
correspondences out of candidates including outliers [14, 4]. Although it
shows a high robustness against false positive matches, the number of
iterations to achieve a reasonable result increases exponentially as a noise
ratio increases due to its stochasticity, and thus is not applicable to cases
of high outlier rates.

Graph-theoretic correspondence extraction has been recently shown effective
under a high outlier rate where RANSAC fails to extract correspondences [6].
Bailey et al. [20] was one of the earliest to frame data association as MCP.
The point association via MCP has been applied to global registration of point
cloud [6] [21]. Koide et al. [22] proposed an automatic localization of
fiducial tags on a 3D prior map using MCP-based data association.

To the best of our knowledge, this work is the first attempt to employ MCP-
based correspondence matching for global localization. The proposed method
leverages the graph-theoretic approach to efficiently find the most likely
instance correspondences and carries out stable global localization.

##  III Global Localization via Correspondence Matching by MCP

The general algorithm of the proposed framework of global localization is
shown in Algorithm 1. The core of the framework is to estimate the
correspondences between the query instances and the map instances to calculate
the pose that matches the correspondences the best. To this end, we employ
graph-theoretic correspondence matching.

First, we generate candidates for correspondences between a query instance and
a map instance. Here, we treat all possible pairs of an instance in the query
and one in the map as valid candidates for correspondences.

Once the correspondence candidates are generated, we build a consistency
graph, a node of which represents a candidate of correspondence between an
instance in the query and one in the map, and an edge indicates consistency
between two candidates represented by the nodes connected by the edge. All
possible pairs of two correspondence candidates are evaluated based on certain
consistency criteria, and if two candidates are evaluated as consistent, an
edge is added between the nodes.

The correspondences are then estimated by solving MCP on the consistency
graph, and the robot pose is calculated using the extracted correspondences so
that it best satisfies the observations of the instances.

Algorithm 1 Global localization via graph-theoretic correspondence matching

0: Map instance set $\mathcal{M}=\left\\{m_{i}\right\\}^{N_{m}}_{i=1}$, query
instance set $\mathcal{Q}=\left\\{q_{j}\right\\}^{N_{q}}_{j=1}$

0: 3-DOF robot pose $\left(x,y,\theta\right)$

1: Correspondence candidate set $\mathcal{C}=\mathcal{M}\times\mathcal{Q}$

2: Vertex set $\mathcal{V}=\mathcal{C}$

3: Edge set $\mathcal{E}=\mathbb{0}$

4: for every combination of $c_{i},c_{j}\in\mathcal{C}$ do

5: if is_consistent$\left(c_{i},c_{j}\right)$ then

6: $\mathcal{E}\leftarrow\mathcal{E}\cup\left\\{e_{ij},e_{ji}\right\\}$

7: end if

8: end for

9:
$\mathcal{C}^{\ast}\leftarrow$max_clique$\left(\mathcal{V},\mathcal{E}\right)$

10:
$\left(x,y,\theta\right)\leftarrow$calculate_pose$\left(\mathcal{C}^{\ast}\right)$

11: return $\left(x,y,\theta\right)$

##  IV Implementation on 3D Semantic Map and a Semantic Segmentation Image

Figure 2: Overview of the proposed framework. As pre-processing, the map
instances are clustered, and the grid histogram descriptors (see 4) are
computed, and stored as a database. Given a query image, instances are
clustered and correspondence candidates are generated as all possible
combinations of a query and a map instances. For every pair of the candidates,
a pose is calculated (IV-B1) and the consistency is evaluated based on two
criteria 1) background similarity, and 2) instance proximity to construct a
consistency graph (IV-B2). The most likely set of correspondences is yielded
by solving MCP on the consistency graph, and the pose is calculated based on
it (IV-C).

Here, we implement the proposed framework using 3D labeled point cloud map as
a prior map, and a semantic segmentation image as a query. We consider
estimation of a 3 DOF pose $(x,y,\theta)$ of the ground robot. We assume a
robot with a camera facing forward and that its transformation relative to the
robot’s base is known, and a semantic segmentation image for an image taken by
the camera is available. The overview of the workflow is shown in Fig. 2.

###  IV-A Clustering the map and the query instances

The instances of the 3D map are clustered and individually saved before the
localization process. Here, the following four object classes are used for
correspondence matching: pole, traffic sign, traffic light, static.

The map points are simply clustered based on their object class and spacial
closeness. For the query image, the instances are clustered based on the
connectivity. This may wrongly extract multiple instances overlapping in the
image as one. We, however, treat such “connected” instances as an individual
instance, expecting that they will be rejected in the subsequent process while
there still remain sufficient correspondences for pose estimation. Candidates
of instance correspondences are all patterns of pairs of instances with the
same object class between the map and the image.

###  IV-B Consistency evaluation

For every combination of two correspondence candidates, a pose is calculated
so that it matches the size and the location of image instances and
reprojection of the corresponding map instances. The consistency of the pair
is then evaluated based on the similarity of the appearance between the query
and the map reprojection from the calculated pose.

####  IV-B1 Pose calculation using a correspondence pair

((a)) Angle defined by image instances  ((b)) Circle $C$ defined by inscribed
angle $\alpha$

Figure 3: The candidate regions of the robot pose based on the inscribed angle
and the size of the instance. (b) The translation of the camera
$(X_{m},Y_{m})$ in the map frame is determined as a point on $C$ where the
distance to an object is $D=\sqrt{X_{c}^{2}+Z_{c}^{2}}$.

Given two image instances, an angle $\alpha$ formed by two vectors to each
image instance from the origin of the camera frame is determined. The region
of the pose is then constrained to a circle $C$ that has an inscribed angle
$\alpha$ as shown in Fig. 3. Since there are two such circles, we determine
$C$ based on the positional relationship of the instances.

To determine the pose, we use the scale information of one of the
correspondences. The relationship of the size in the 3D space $s_{m}$ and that
of its projection $s_{i}$ is written as:

$\displaystyle s_{i}=\frac{f\cdot s_{m}}{Z_{c}},$ (1)

where $f$ denotes the focal length of the camera and $Z_{c}$ denotes the $Z$
coordinate of the instance in the camera frame. Since the sizes of both image
instance and the map instance in a correspondence are known, $Z_{c}$ can be
estimated as:

$\displaystyle Z_{c}=\frac{f\cdot s_{m}}{s_{i}}.$ (2)

The set of points that satisfy eq. (2) also forms a circle with a radius
$D=\sqrt{X_{c}^{2}+Z_{c}^{2}}$. The camera pose can, therefore, be calculated
as an intersection of circle $C$ and a circle that centers at the location of
the map instance and has radius $D$. In this way, at most two intersections
are yielded. In such a case, we calculate the expected size of the projection
of another map instance using eq. (1) from the two poses, and compare them
with the size of the corresponding image instance. The pose that provides a
smaller error of the size is selected as the solution.

####  IV-B2 Consistency criteria

The consistency is evaluated based on two criteria, background similarity and
instance proximity. The latter is relevant to the spacial consistency, which
is often employed in MCP-based correspondence matching such as [6] and [22].
In our problem, however, this criterion is not sufficient because there may be
many wrong correspondences that happen to satisfy it. The background
similarity criterion is, therefore, employed before the instance proximity to
filter out unlikely correspondences based on the appearance similarity. Using
the two criteria, we effectively evaluate consistency of the correspondences.

((a)) Grid histogram  ((b)) Instance proximity

Figure 4: Consistency criteria. (a) The grid histogram descriptor is a
normalized vector of the local histograms of object classes. (b) The instance
proximity evaluates a spacial relationship between the bounding boxes around
the image instance and the projection of the map instance.

Background similarity The purpose of the background similarity criterion is
not to strictly detect images similar to the query, but to quickly filter out
obvious outliers. To this end, we employ a simple histogram descriptor.

Fig. 4(a) shows an overview. First, the bottom of the image is cut off as this
part does not convey much information. The remaining part of the image is
divided into grids with a fixed size. For each grid, a histogram of the object
classes is generated and L2-normalized. We chose nine background object
classes: building, fence, road line, road, sidewalk, vegetation, wall, bridge,
terrain. The normalized histograms from the grids are concatenated into
($h\times w\times 9$)-dimensional vector, where $h$ and $w$ denotes the number
of grid in the vertical and the horizontal axis, respectively. The vector is
then L2-normalized again to form a descriptor. Similarity of two descriptors
are given as a dot product, or equivalently a cosine similarity with a value
range of $[0,1]$.

For fast evaluation, we pre-compute the descriptors for the map by projecting
the 3D map from the poses uniformly sampled in the map.

Instance proximity The instance proximity is evaluated by the distance and the
size differences of bounding boxes around the projected map instance and the
image instance (see Fig. 4(b)). The distance between them are defined as the
Euclidean distance between the centroids of the bounding boxes. The size
differences are calculated with height and width lengths of the bounding
boxes. If the distance, the height and the width difference are all less than
a threshold for both of the correspondences in the given pair, the pair of
correspondence candidates is considered consistent.

Here, we set the threshold adaptively to the $Z$ coordinate value $Z_{c}$ of
each map instance in the camera frame. We empirically define the distance
threshold $\theta_{d}$ and the size threshold $\theta_{s}$ as follows:

$\displaystyle\theta_{d}$
$\displaystyle=\min\left(m_{d},\max\left(m_{min},dm_{d}/Z_{c}\right)\right)$
(3) $\displaystyle\theta_{s}$
$\displaystyle=\min\left(m_{s},\max\left(m_{min},dm_{s}/Z_{c}\right)\right),$

where $m_{d}$ and $m_{s}$ denote the maximum possible threshold of the
instance distance and the size in pixel, respectively. The idea behind these
definitions is to set the thresholds of objects at $d$ [m] from the sensor to
$m_{d}$ [px] and $m_{s}$ [px], and decrease it as $Z_{c}$ becomes larger. The
thresholds are clipped with the minimum value of $m_{min}$ [px] and the
maximum value of $m_{d}$ and $m_{s}$. Here, we set $d$ to 8 and $m_{min}$ to
5.

###  IV-C Pose estimation

A consistency graph is constructed based on the aforementioned consistency
criteria, and the most likely set of correspondences are yielded by solving as
described in IV. The final pose is then calculated by minimizing the
reprojection error of representation points of the correspondences. A
representation point of an image instance is a point that has the largest y
value in the image coordinate, and that of a map instance is the point with
the smallest z value in the map coordinate, representing their bottom point.
Although this way does not provide exact matching of the parts of the
instances, it does not affect much the calculation of the camera pose. An
initial pose is given as an average of poses calculated by the correspondences
in the clique during the phase of building the consistency graph (see IV-B1).
The Levenberg-Marquardt algorithm [23, 24] with Huber kernel [25] is applied
to the pose optimization.

###  IV-D Pose verification via correspondence check

Ideally, the maximum clique of the consistency graph represents a set of
correct correspondences. In practice, however, we found that it is often not
the case due to rejection of the correct correspondences mainly caused by
error in pose calculation, while evaluating wrong ones as consistent.

To mitigate the problem, we introduce a verification step. After constructing
the consistency graph, we calculate multiple correspondence set by iteratively
applying MCP solver, calculating a pose with each set, and removing edges
between the vertices corresponding to the members of the found maximum clique.
To verify each correspondence set, we count the number of image instances that
have a map instance projected close to it from the calculated pose based on
the proximity criterion. The correspondence set with the maximum count is
treated as the result. Top N results are yielded by taking results with five
largest counts.

##  V Experiments

###  V-A Experimental setup

The experiments were conducted on a laptop with an Intel Core i7-10750H (12
threads) and 16 GB of RAM.

We used simulated point cloud maps of Town01 to 05 from CARLA simulator [26]
for evaluation. The description of the environments is shown in Table 1. We
created point cloud maps using the scripts shared by the authors of [27]. For
each map, descriptors are pre-computed from the poses uniformly sampled with a
stride of 2 m in the x and the y axes of the map frame and $30^{\circ}$ in the
yaw angle.

The samples of query were generated from the spawn points of vehicles defined
in CARLA. A camera was mounted on the simulated vehicle at the height of
approx. 1.5 m from the robot’s base. Since the proposed method estimates a 3
DOF pose and assumes fixed height of the camera, we choose the poses with the
height between 1.46 m and 1.90 m as the samples. We use ground truth semantic
segmentation images generated by CARLA.

TABLE I: Descriptions of the CARLA Towns111The descriptions are from https://carla.readthedocs.io/en/latest/core_map/ Town | Summary
---|---
01 |  | A basic town layout consisting of ”T junctions”.
---
02 |  | Similar to Town01, but smaller.
---
03 |  | The most complex town, with a 5-lane junction,
---
a roundabout, unevenness, a tunnel, and more.
04 |  | An infinite loop with a highway and a small town.
---
05 |  | Squared-grid town with cross junctions and a bridge.
---
It has multiple lanes per direction.

The thresholds of the background similarity (BS), the instance distance and
the instance size in the instance proximity (IP) are empirically set to 0.9,
110, 50, respectively.

###  V-B Baselines

As baselines, we use brute-force descriptor search (BF) and RANSAC-based
correspondence matching. The former searches for the pre-computed descriptor
that has the highest similarity score with the query and returns the
discretized pose that the descriptor is associated with. In the latter, RANSAC
is used for correspondence finding instead of the proposed graph-theoretic
approach. For a randomly sampled pair of correspondences, a pose is calculated
as described in IV-B1 and the number of the correspondences consistent with
the pose is counted. We use the same background similarity threshold as the
proposed method to reject the pair, and the instance proximity threshold to
find the correspondences. The number of iteration is set to 50000.

###  V-C Evaluation conditions

We evaluate the localization performance using three conditions: $\pm$5,
$\pm$10, and front drift. For all of the conditions, the threshold of yaw
error is $\pm 30^{\circ}$. $\pm$5 denotes the case where the lateral and
longitudinal errors are within $\pm 5$ m. Likewise, $\pm$ 10 means within
$\pm$ 10 m of lateral and longitudinal errors. Front drift denotes the case
where the error in the x axis of the robot’s frame is within $\pm 200$ m and
$\pm 5$ m in the y axis. This is typically the case when the estimated pose is
on the same road as the ground truth and facing the same direction, but is
drifted in the longitudinal direction in the robot frame.

###  V-D Localization results

TABLE II: Results of global localization

Town |  |  01 |  02 |  03 |  04 |  05
---|---|---|---|---|---|---
Samples |  |  254 |  101 |  197 |  259 |  234
$\pm$5 |  T1 |  133 |  60 |  63 |  36 |  76
|  |  (52.4%) |  (59.4%) |  (32.0%) |  (13.7%) |  (32.5%)
|  T3 |  157 |  68 |  73 |  45 |  93
|  |  (61.8%) |  (67.3%) |  (37.1%) |  (17.4%) |  (39.7%)
|  T5 |  167 |  71 |  79 |  48 |  98
|  |  (65.7%) |  (70.3%) |  (40.1%) |  (18.5%) |  (41.9%)
$\pm$10 |  T1 |  142 |  65 |  72 |  49 |  81
|  |  (55.9%) |  (64.4%) |  (36.5%) |  (18.9%) |  (34.6%)
|  T3 |  170 |  74 |  85 |  62 |  100
|  |  (66.9%) |  (73.3%) |  (43.1%) |  (23.9%) |  (42.7%)
|  T5 |  183 |  77 |  94 |  67 |  106
|  |  (72.0%) |  (76.2%) |  (47.7%) |  (25.9%) |  (45.3%)
FD |  T1 |  175 |  75 |  95 |  53 |  87
|  |  (68.9%) |  (74.3%) |  (48.2%) |  (20.5%) |  (37.2%)
|  T3 |  196 |  81 |  104 |  76 |  110
|  |  (77.2%) |  (80.2%) |  (52.8%) |  (27.8%) |  (47.0%)
|  T5 |  207 |  86 |  114 |  82 |  123
|  |  (81.5%) |  (85.1%) |  (57.9%) |  (30.1%) |  (52.6%)

  * •

* T1, T3, and T5 denote Top 1, Top 3, and Top 5, respectively. FD denotes Front drift. Green: $>70$ %, Red: $<30$ %

Table II shows the results of global localization. The values indicate the
number of samples that resulted in fulfilling the evaluation conditions in Top
1, Top 3, and Top 5 results calculated as described in IV-D. In Town01 and 02,
Top 5 estimation for approximately 65 to 70 % of the samples fulfilled $\pm$5,
and more than 80 % of them fulfilled front drift. In Town 03 and 05, Top 5
results of approximately 40 % samples fulfilled $\pm$5. The result of Town04
was significantly worse than the other maps, with 18.5 % of $\pm$5 and 30.1 %
of front drift in Top 5 results, respectively. We discuss the cause of the low
performance in V-G.

###  V-E Comparison with the baselines

Table III shows the comparative results with the baselines. The values are the
number of Top 1 results of $\pm$5 and $\pm$10. The proposed method surpassed
the baseline methods in all conditions but $\pm$10 of BF in Town05. It is
worth noting that the brute-force search did not result in accurate pose
estimation in most of the environments. Nevertheless, combined with our
framework, it resulted in better performance. RANSAC was also resulted in
worse results than the proposed method. This is an expected result as most of
the correspondence candidates are outliers in the tasks, and RANSAC struggles
with finding a consistent pair via random sampling. In contrast, the proposed
method efficiently found the correspondences leveraging the graph-theoretic
approach.

TABLE III: Comparison with the baselines | Town no. | 01 | 02 | 03 | 04 | 05
---|---|---|---|---|---|---
| Samples | 254 | 101 | 197 | 259 | 234
BF |  $\pm$5 | 99 | 35 | 49 | 32 | 70
$\pm$10 | 107 | 34 | 62 | 47 | 98
RANSAC |  $\pm$5 | 17 | 7 | 5 | 2 | 6
$\pm$10 | 22 | 10 | 17 | 11 | 12
Proposed |  $\pm$5 | 133 | 60 | 63 | 36 | 76
$\pm$10 | 142 | 65 | 72 | 49 | 81

###  V-F Ablation studies on the consistency criteria

TABLE IV: Ablation on the consistency criteria

Town no. | 01 | 02 | 03 | 04 | 05
---|---|---|---|---|---
Samples | 254 | 101 | 197 | 259 | 234
BS(0.9) | 40 | 18 | 6 | 1 | 8
IP/IP+BS(0.5) | 18* | 8 | 4 | 11 | 15
IP+BS(0.9) | 133 | 60 | 63 | 36 | 76

  * *

Only IP

Table IV shows the results of an ablation study on the consistency criteria to
examine their contribution. To test IP for Town02 to 05, we loosened BS
threshold to 0.5 (denoted as IP+BS(0.5)) instead of using only IP, because we
found disabling BS significantly slowed down the computation speed due to
increased number of transformation of map instances in IP computation.

As a result, the performance was significantly worse in BS and IP (Town01) /
IP+BS(0.5) (02-05). The combination of those simple consistency criteria
resulted the best to effectively find the correspondences and calculate the
pose.

###  V-G Discussion

We saw promising results of the proposed framework especially in Town01 and
02. Notably, the proposed method requires only the semantic 3D map and
semantic segmentation query. Although the building blocks for consistency
evaluation are simple, our system provided reasonable results. We suppose this
is thanks to the graph-theoretic correspondence matching approach which is
capable of effectively extracting correspondences under high outlier rate.

Limitations Despite the powerful graph-theoretic approach, there were also
many failure cases. They mainly stem from the error in the pose estimation
using a pair of correspondences. The current pose calculation is sensitive to
noise in instance clustering because it exploits the relationship of the
scales of instances to estimate the distance from the robot pose to the map
instances, and assumes that both the image instance and the map instance are
complete. In reality, however, the assumption often does not hold. This
problem will also affect real-world application because, in practice, the
query semantic segmentation will be provided by an estimator based on DNNs
etc., which inevitably has estimation noise. To deal with it, we should
introduce pose calculation that is more robust to such noise.

The causes of the low accuracy for Town04 are twofold. First, the number of
image instances are fewer than other Towns. Due to the unstable pose
calculation, a few image instances in an image are generally rejected in MCP,
and it is thus more possible to result in no correct correspondences detected
when an image has few instances. Second, the mountains and terrains seen far
away in the query were not mapped due to the limited range of the point cloud
map, and the descriptors of the query and the map had a large difference in
many samples. This effect was especially significant in Town04 consisting of
open highway scenes with mountains. Although the simple descriptor provided
reasonable results in tandem with the proposed framework, we should reconsider
its design to mitigate such a problem.

##  VI Conclusion

We proposed a framework for global localization based on graph-theoretic
matching of instance correspondences between a query and a prior map. We
implemented the framework on semantically labeled point cloud maps and
semantic segmentation images as queries. Leveraging the efficient graph-
theoretic correspondence matching with the simple consistency criteria, we
presented promising preliminary results on the global localization task in
simulated urban environments. This research direction will lead to
localization ability of robots with more flexibility of of the map and sensor
modalities.

## References

  * [1] Frank Dellaert, Wolfram Burgard, Dieter Fox and Sebastian Thrun  “Using the CONDENSATION algorithm for robust, vision-based mobile robot localization”  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition_ IEEE, 1999, pp. 588–594  DOI: 10.1109/CVPR.1999.784976
  * [2] Relja Arandjelovic, Petr Gronat, Akihiko Torii, Tomas Pajdla and Josef Sivic  “NetVLAD: CNN Architecture for Weakly Supervised Place Recognition”  In _IEEE Transactions on Pattern Analysis and Machine Intelligence_ 40.6, 2018, pp. 1437–1451  DOI: 10.1109/TPAMI.2017.2711011
  * [3] Ahmad Khaliq, Michael Milford and Sourav Garg  “MultiRes-NetVLAD: Augmenting Place Recognition Training with Low-Resolution Imagery”  In _IEEE Robotics and Automation Letters_ 7.2 Institute of ElectricalElectronics Engineers Inc., 2022, pp. 3882–3889  DOI: 10.1109/LRA.2022.3147257
  * [4] Marcel Geppert, Peidong Liu, Zhaopeng Cui, Marc Pollefeys and Torsten Sattler  “Efficient 2D-3D matching for multi-camera visual localization”  In _IEEE International Conference on Robotics and Automation_ , 2019, pp. 5972–5978  DOI: 10.1109/ICRA.2019.8794280
  * [5] Renaud Dubé, Andrei Cramariuc, Daniel Dugas, Hannes Sommer, Marcin Dymczyk, Juan Nieto, Roland Siegwart and Cesar Cadena  “SegMap: Segment-based mapping and localization using data-driven descriptors”  In _International Journal of Robotics Research_ 39.2-3, 2020, pp. 339–355  DOI: 10.1177/0278364919863090
  * [6] Heng Yang, Jingnan Shi and Luca Carlone  “TEASER: Fast and Certifiable Point Cloud Registration”  In _IEEE Transactions on Robotics_ 37.2, 2021, pp. 314–333  DOI: 10.1109/TRO.2020.3033695
  * [7] Andrei Cramariuc, Florian Tschopp, Nikhilesh Alatur, Stefan Benz, Tillmann Falck, Marius Bruhlmeier, Benjamin Hahn, Juan Nieto and Roland Siegwart  “SemSegMap – 3D Segment-based Semantic Localization”  In _IEEE/RSJ International Conference on Intelligent Robots and Systems_ IEEE, 2021, pp. 1183–1190  DOI: 10.1109/IROS51168.2021.9636156
  * [8] Huan Yin, Li Tang, Xiaqing Ding, Yue Wang and Rong Xiong  “LocNet: Global Localization in 3D Point Clouds for Mobile Vehicles”  In _IEEE Intelligent Vehicles Symposium_ IEEE, 2018, pp. 728–733  DOI: 10.1109/IVS.2018.8500682
  * [9] Konrad P. Cop, Paulo V K Borges and Renaud Dube  “Delight: An Efficient Descriptor for Global Localisation Using LiDAR Intensities”  In _IEEE International Conference on Robotics and Automation_ IEEE, 2018, pp. 3653–3660  DOI: 10.1109/ICRA.2018.8460940
  * [10] Johannes L. Schonberger, Marc Pollefeys, Andreas Geiger and Torsten Sattler  “Semantic Visual Localization”  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition_ IEEE, 2018, pp. 6896–6906  DOI: 10.1109/CVPR.2018.00721
  * [11] Sebastian Ratz, Marcin Dymczyk, Roland Siegwart and Renaud Dube  “OneShot Global Localization: Instant LiDAR-Visual Pose Estimation”  In _IEEE International Conference on Robotics and Automation_ , 2020, pp. 5415–5421  DOI: 10.1109/ICRA40945.2020.9197458
  * [12] David G Lowe  “Distinctive Image Features from Scale-Invariant Keypoints”  In _International Journal of Computer Vision_ 60.2, 2004, pp. 91–110  DOI: 10.1023/B:VISI.0000029664.99615.94
  * [13] Herbert Bay, Tinne Tuytelaars and Luc Van Gool  “SURF: Speeded Up Robust Features”  In _European Conference on Computer Vision_ , 2006, pp. 404–417  DOI: 10.1007/11744023˙32
  * [14] Stephen Se, David G. Lowe and James J. Little  “Vision-based global localization and mapping for mobile robots”  In _IEEE Transactions on Robotics_ 21.3, 2005, pp. 364–375  DOI: 10.1109/TRO.2004.839228
  * [15] Radu Bogdan Rusu, Nico Blodow and Michael Beetz  “Fast Point Feature Histograms (FPFH) for 3D registration”  In _IEEE International Conference on Robotics and Automation_ IEEE, 2009, pp. 3212–3217  DOI: 10.1109/ROBOT.2009.5152473
  * [16] Semih Orhan, Jose J. Guerrero and Yalin Bastanlar  “Semantic Pose Verification for Outdoor Visual Localization with Self-supervised Contrastive Learning”  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops_ IEEE, 2022, pp. 3989–3998  arXiv:2203.16945
  * [17] Xiyue Guo, Junjie Hu, Junfeng Chen, Fuqin Deng and Tin Lun Lam  “Semantic Histogram Based Graph Matching for Real-Time Multi-Robot Global Localization in Large Scale Environment”  In _IEEE Robotics and Automation Letters_ 6.4 IEEE, 2021, pp. 8349–8356  DOI: 10.1109/LRA.2021.3058935
  * [18] Alex Kendall, Matthew Grimes and Roberto Cipolla  “PoseNet: A Convolutional Network for Real-Time 6-DOF Camera Relocalization”  In _IEEE International Conference on Computer Vision_ IEEE, 2015, pp. 2938–2946  DOI: 10.1109/ICCV.2015.336
  * [19] Mengdan Feng, Sixing Hu, Marcelo H. Ang and Gim Hee Lee  “2D3D-Matchnet: Learning To Match Keypoints Across 2D Image And 3D Point Cloud”  In _IEEE International Conference on Robotics and Automation_ 2019-May IEEE, 2019, pp. 4790–4796  DOI: 10.1109/ICRA.2019.8794415
  * [20] T. Bailey, E.M. Nebot, J.K. Rosenblatt and H.F. Durrant-Whyte  “Data association for mobile robot navigation: a graph theoretic approach”  In _IEEE International Conference on Robotics and Automation_ IEEE, 2000, pp. 2512–2517  DOI: 10.1109/ROBOT.2000.846406
  * [21] Jingnan Shi, Heng Yang and Luca Carlone  “ROBIN: a Graph-Theoretic Approach to Reject Outliers in Robust Estimation using Invariants”  In _IEEE International Conference on Robotics and Automation_ IEEE, 2021, pp. 13820–13827  DOI: 10.1109/ICRA48506.2021.9562007
  * [22] Kenji Koide, Shuji Oishi, Masashi Yokozuka and Atsuhiko Banno  “Scalable Fiducial Tag Localization on a 3D Prior Map via Graph-Theoretic Global Tag-Map Registration”  In _IEEE/RSJ International Conference on Intelligent Robots and Systems_ IEEE, 2022  arXiv:2207.11942
  * [23] Kenneth Levenberg  “A method for the solution of certain non-linear problems in least squares”  In _Quarterly of Applied Mathematics_ 2.2 Brown University, 1944, pp. 164–168  DOI: 10.1090/qam/10666
  * [24] Donald W Marquardt  “An Algorithm for Least-Squares Estimation of Nonlinear Parameters”  In _Journal of the Society for Industrial and Applied Mathematics_ 11.2, 1963, pp. 431–441  DOI: 10.1137/0111030
  * [25] Peter J. Huber  “Robust Estimation of a Location Parameter”  In _The Annals of Mathematical Statistics_ 35.1, 1964, pp. 73–101  DOI: 10.1214/aoms/1177703732
  * [26] Alexey Dosovitskiy, German Ros, Felipe Codevilla, Antonio Lopez and Vladlen Koltun  “CARLA: An Open Urban Driving Simulator”  In _Conference on Robot Learning_ PMLR, 2017, pp. 1–16  arXiv:1711.03938
  * [27] Jean Emmanuel Deschaud, David Duque, Jean Pierre Richa, Santiago Velasco-Forero, Beatriz Marcotegui and François Goulette  “Paris-carla-3d: A real and synthetic outdoor point cloud dataset for challenging tasks in 3d mapping”  In _Remote Sensing_ 13.22, 2021, pp. 1–24  DOI: 10.3390/rs13224713