# Three travel time inverse problems on simple Riemannian manifolds

Joonas Ilmavirta  Department of Mathematics and Statistics
University of Jyväskylä, Jyväskylä, FI-40014, Finland
<EMAIL_ADDRESS>,  Boya Liu  Department of Mathematics, North
Carolina State University, Raleigh, NC 27695, USA<EMAIL_ADDRESS>and  Teemu
Saksala  Department of Mathematics, North Carolina State University, Raleigh,
NC 27695, USA<EMAIL_ADDRESS>
###### Abstract.

We provide new proofs based on the Myers–Steenrod theorem to confirm that
travel time data, travel time difference data and the broken scattering
relations determine a simple Riemannian metric on a disc up to the natural
gauge of a boundary fixing diffeomorphism. Our method of the proof leads to a
Lipschitz-type stability estimate for the first two data sets in the class of
simple metrics.

##  1\. Introduction

We study three geometric inverse problems. The task is to reconstruct a simple
Riemannian manifold from (1) travel time data, (2) travel time difference
data, or (3) the broken scattering relations. A compact Riemannian manifold is
called simple if the boundary is strictly convex and the exponential map is a
global diffeomorphism.

The third problem has been solved previously for dimension three and higher in
general geometry, and we extend the result to dimension 2 in simple geometry.
For the other problems previous results give Hölder or similar stability in
great generality, and we show that in simple geometry we improve this to
Lipschitz. In many previously known cases (e.g. uniqueness on simple manifolds
for problems 1 and 2) our proofs are elementary due to simple geometry.

If the Earth is modeled as a Riemannian manifold (which is a popular albeit
not exactly accurate choice; cf. [1, 3]), these problems correspond simplified
versions of problems arising from seismology. The Earth is full of small-scale
inhomogeneities that cause seismic waves to scatter. Seen on the scale of the
whole planet, these inhomogeneities such as rocks are best seen as point-like
objects of zero size even though a single point is irrelevant from the point
of view of the elastic wave equation. The model for scattering is mesoscopic:
the scatterers are big enough to cause the waves to scatter but small enough
to be considered mere points on the global scale that fill the planet densely.
For the first two problems no such considerations are needed, and the point
sources can be either natural (e.g. earthquakes) or artificial (e.g. produced
by focusing waves). Seismic ray paths correspond to geodesics. We will focus
on the geometric problems in this paper and ignore details of the physical
model. We introduce the inverse problems in physical terms below and in
mathematical terms in the following subsections.

In the first and second inverse problems we record the arrival times of
seismic waves, initiated by a dense set of point sources going off at some
unknown origin times, measured on a dense set of receivers on the surface of
the planet. The arrival time of a wave is the difference of the _travel time_
(distance from the source to receiver) and the origin time. In our first main
result (Theorem 9), we assume that origin times are known and show that the
collection of travel times stably determine the isometry class of a simple
Riemannian metric. If the origin time of a seismic event is unknown and we
have measured the corresponding arrival times, then by computing the
difference of arrival times we obtain a _travel time difference_. In our
second main result (Theorem 13), we show that the travel time differences
stably determine a simple metric up to a Riemannian isometry.

In our third inverse problem, the data consists of the knowledge of ingoing
directions on the boundary of the planet and for each such direction the set
of all outcoming directions and the associated travel times of all single-
scattered geodesics. This data is encoded in the _broken scattering
relations_. Our third main result (Theorem 15) shows that this data determines
a simple metric up to a Riemannian isometry.

###  1.1. Inverse problem 1: Travel time data

Let $(M,g)$ be a compact, connected, oriented, and smooth Riemannian manifold
with smooth boundary $\partial M$. For any points $x,y\in M$, we use the
notation $d(x,y)$ for the Riemannian distance between them. The first data set
we study in this paper is the _travel time data_.

######  Definition 1.

For every point $p\in M$ its _travel time function_ $r_{p}:\partial
M\to\mathbb{R}$ is defined by the formula $r_{p}(z)=d(p,z)$. _The travel time
map_ of the Riemannian manifold $(M,g)$ is then given by the formula

$\mathcal{R}:(M,g)\to(C(\partial M),\|\cdot\|_{\infty})$ (1)

with $\mathcal{R}(p)=r_{p}$. The image set $\mathcal{R}(M)\subset C(\partial
M)$ of the travel time map is called the travel time data of the Riemannian
manifold $(M,g)$.

######  Remark 2.

The travel time data of a Riemannian manifold is an unlabelled collection of
travel time functions. The locations of point sources related to these
functions are unknown.

It was showed in [8, Section 3.8] and [10] that the travel time data
determines any compact, connected, oriented, and smooth Riemannian manifold up
to an isometry. A corresponding uniqueness result for a partial travel time
data of a compact manifold with strictly convex boundary was established in
[15]. If the metric is Finslerian, then the travel time data can be used to
determine the metric, up to a natural obstruction, in the directions of the
tangent bundle corresponding with distance minimizing geodesics that reach the
boundary [1]. The authors also verified that this is the largest set in which
a Finsler metric can be determined from its travel time data. Approximate
reconstruction of the Riemannian manifold and Hölder-stability of the travel
time data, under certain geometric bounds, have been studied in [2, 9].

In the present paper we study the uniqueness and Lipschitz-stability of the
travel time data on simple Riemannian manifolds. It is important for our
proofs that on a simple manifold there are no conjugate points, and
consequently any two points on the manifold, including the boundary, are
joined by a unique geodesic depending smoothly on the endpoints.

We will make use of the Myers–Steenrod theorem: “Every distance-preserving map
between two connected Riemannian manifolds is actually a smooth isometry of
Riemannian manifolds [13, 14].” This result is true also on simple manifolds
with boundary [2, Lemma 29]. In Proposition 6 of this paper we use this
theorem to show that the travel time map on simple Riemannian manifolds is a
metric isometry and provide a new, short proof for Proposition 8 for the
aforementioned uniqueness result in the class of simple Riemannian manifolds.
Our first main result (Theorem 9) is a Lipschitz-type stability result for the
travel time data on simple Riemannian manifolds.

###  1.2. Inverse problem 2: Travel time difference data

The second data set studied in this paper is the _travel time difference
data_.

######  Definition 3.

The travel time difference function of a point $p\in M$ is the function

$\begin{split}&D_{p}\colon\partial M\times\partial M\to\mathbb{R},\\\
&D_{p}(z,w)=d(p,z)-d(p,w).\end{split}$

Then the _travel time difference map_ and the travel time difference data of
the Riemannian manifold $(M,g)$ are

$\mathcal{D}\colon(M,g)\to(C(\partial M\times\partial M),\|\cdot\|_{\infty})$

with $\mathcal{D}(p)=\frac{1}{2}D_{p}$, and its image set

$\mathcal{D}(M)\subset C(\partial M\times\partial M),$

respectively.

The factor $\frac{1}{2}$ in $\mathcal{D}(p)=\frac{1}{2}D_{p}$ is convenient in
making the map $\mathcal{D}$ an isometry.

This data was introduced in [12], where instead of doing boundary
measurements, the travel time difference $D_{p}(z,w)$ was measured for every
source point $p\in N$ between any receiver points $z,w\in F$, where $F\subset
N$ contains an open subset of a closed Riemannian manifold $(N,g)$. The
authors showed that the knowledge of the metric on $F$, in conjunction with
the travel time difference data, determine the isometry type of $(N,g)$. This
result was later extended for the boundary measurements on compact manifolds
in [4]. On complete manifolds the uniqueness and a non-quantitative stability
of the travel time difference data was obtained in [6, 7].

In the present paper we revisit the travel time difference data on simple
Riemannian manifolds. We provide a new short proof for the uniqueness of the
geometry from this data (Proposition 12) by utilizing the Myers–Steenrod
Theorem. Our second main result is a Lipschitz-type stability for the travel
time difference data on simple manifolds (Theorem 13).

###  1.3. Inverse problem 3: Broken scattering relations

Our third main result is the uniqueness result for the _broken scattering
relations_ on simple manifolds. Let $TM$ and $SM$ be the tangent and the unit
sphere bundles of $(M,g)$, respectively. The geodesic flow of $(M,g)$ is
denoted by

$\phi\colon SM\times\mathbb{R}\to
SM,\quad\phi_{t}(\eta)=(\gamma_{\eta}(t),\dot{\gamma}_{\eta}(t)),$

and $\gamma_{\eta}$ is the geodesic of $(M,g)$ given by the initial conditions
$(\gamma_{\eta}(0),\dot{\gamma}_{\eta}(0))=\eta\in SM.$

Let $\pi\colon TM\to M$ be the canonical projection to the base points given
by $\pi(z,v)=\pi(v)=z$, and let $\nu$ be the inward pointing unit normal
vector field on the boundary of $M$. The boundary of the sphere bundle is the
set

$\partial SM=\\{v\in SM:\pi(v)\in\partial M\\}.$

We call the set

$\partial_{\mathrm{in}}SM=\\{v\in\partial SM:\langle v,\nu\rangle_{g}>0\\}$

the inward pointing bundle at the boundary. Similarly, we define the outward
pointing bundle as

$\partial_{\mathrm{out}}SM{}=\\{v\in\partial SM:\langle
v,\nu\rangle_{g}<0\\}.$

The unit ball bundle of $\partial M$ is then defined by

$B\partial M=\\{\xi\in T\partial M;\left\lvert\xi\right\rvert<1\\}.$ (2)

There are natural diffeomorphisms

$\begin{split}N_{\mathrm{in}}&\colon\partial_{\mathrm{in}}SM\to B\partial
M\quad\text{and}\\\ N_{\mathrm{out}}&\colon\partial_{\mathrm{out}}SM{}\to
B\partial M\end{split}$

given by the fiberwise projection
$N_{\mathrm{in/out}}(\xi)=\xi-\langle\xi,\nu\rangle_{g}\nu$ in the direction
of the normal vector $\nu$. The point of these maps is to identify the bundle
$B\partial M$, which is intrinsic to $\partial M$, with the bundles
$\partial_{\mathrm{in}}SM$ and $\partial_{\mathrm{out}}SM{}$ which in
principle carry information of how the boundary sits within the unknown
manifold $M$.

We are ready to define the broken scattering relations.

######  Definition 4.

For each $T>0$, the _broken scattering relation_ $\mathcal{B}_{T}$ on
$B\partial M$ is such that the vectors $v_{1},v_{2}\in B{\partial M}$ satisfy
$v_{1}\mathcal{B}_{T}v_{2}$ if and only if there exist two numbers
$t_{1},t_{2}>0$ for which $t_{1}+t_{2}=T$ and
$\pi(\phi_{t_{1}}(N_{\mathrm{in}}^{-1}v_{1}))=\pi(\phi_{t_{2}}(N_{\mathrm{in}}^{-1}v_{2}))$.

The family $\\{\mathcal{B}_{T}:\>T>0\\}$ of relations is called the broken
scattering relations of Riemannian manifold $(M,g)$.

######  Remark 5.

We emphasize that a study of broken scattering relations requires the
knowledge of the unit ball bundle, which is equivalent to knowing the first
fundamental form of $\partial M$.

Our third main result (Theorem 15) shows that the broken scattering relations
determine any simple Riemannian manifold up to a Riemannian isometry. A
stronger version of this result (for $\dim(M)\geq 3$) has been presented
originally in [11], where the authors only assumed that $(M,g)$ is a smooth
compact Riemannian manifold with smooth boundary. In [3] this result was
extended to cover reversible Finsler metrics that satisfy a convex foliation
condition.

Up to our best knowledge, Theorem 15 of this paper is novel in the two
dimensional case. As in [11], our proof is based on a reduction step
(Proposition 14) to the travel time data. Due to simplicity, we can provide a
new proof for the reduction. This and our Proposition 8 yield a novel
streamlined proof for the uniqueness of the broken scattering relations for
simple metrics of all dimensions.

###  1.4. Outline of the paper

In Sections 2, 3 and 4 of this paper, we consider the travel time data, travel
time difference data, and broken scattering relations, respectively. In
Section 5 we consider a diffeomorphism invariant travel time and travel time
difference data and provide a stability result for them.

### Acknowledgements

JI was supported by the Academy of Finland (projects
351665 and 351656). TS was supported by the National Science Foundation under
grant DMS-2204997. We thank Jonne Nyberg and Antti Kykkänen for discussions.

##  2\. Uniquenss and Stability of the Travel Time Data

We recall that every simple Riemannian manifold is diffeomorphic to the closed
unit ball $\mathbb{D}^{n}$ of $\mathbb{R}^{n}$. Thus, from here onwards we
study simple metrics on $\mathbb{D}^{n}$.

######  Proposition 6.

Let $g$ be a simple Riemannian metric on $\mathbb{D}^{n}$. The travel time map
$\mathcal{R}$, given by formula (1), is a metric isometry.

###### Proof.

By triangle inequality the map $\mathcal{R}$ is easily seen to be
$1$-Lipschitz. To prove the reverse estimate, let $x,y\in\mathbb{D}^{n}$.
Since $g$ is simple, there exists a unique distance minimizing geodesic
$\gamma$ connecting the points $x$ and $y$ to some boundary point
$z\in\mathbb{S}^{n-1}$.

Since $\gamma$ exits $\mathbb{D}^{n}$ at $z$, and all three points $x,y,z$ are
on the same distance minimizing curve $\gamma$, we have

$|r_{x}(z)-r_{y}(z)|=|d(x,z)-d(y,z)|=d(x,y).$

Thus we have verified the equality

$\|\mathcal{R}(x)-\mathcal{R}(y)\|_{\infty}=d(x,y)\quad\text{ for all
}x,y\in\mathbb{D}^{n}.$

The proof is complete. ∎

Since $\mathbb{D}^{n}$ is compact, the previous proposition yields that
$\mathcal{R}(\mathbb{D}^{n})$ is a compact subset of the Banach space
$(C(\mathbb{S}^{n-1}),\|\cdot\|_{\infty})$. In order to compare two such image
sets, we next define a notion of distance between them.

######  Definition 7.

We set the distance of travel time data of two simple Riemannian metrics
$g_{1}$ and $g_{2}$ on $\mathbb{D}^{n}$ to be

$d_{H}^{C(\mathbb{S}^{n-1})}(\mathcal{R}_{1}(\mathbb{D}^{n}),\mathcal{R}_{2}(\mathbb{D}^{n}))\geq
0,$

where $d_{H}^{C(\mathbb{S}^{n-1})}$ is the Hausdorff distance of
$C(\mathbb{S}^{n-1})$ and the travel time maps $\mathcal{R}_{i}$ are as in
formula (1).

Moreover, we say that the travel time data of the simple Riemannian metrics
$g_{1}$ and $g_{2}$ on $\mathbb{D}^{n}$ coincide if

$d_{H}^{C(\mathbb{S}^{n-1})}(\mathcal{R}_{1}(\mathbb{D}^{n}),\mathcal{R}_{2}(\mathbb{D}^{n}))=0.$

If $\Phi\colon\mathbb{D}^{n}\to\mathbb{D}^{n}$ is a diffeomorphism whose
restriction on $\mathbb{S}^{n-1}$ is the identity map and $g_{1}$ is any
simple metric of $\mathbb{D}^{n}$, then the pullback metric
$g_{2}:=\Phi^{\ast}g_{1}$ is a simple metric on $\mathbb{D}^{n}$ isometric to
$g_{1}$. Thus the equality

$d_{2}(p,z)=d_{1}(\Phi(p),\Phi(z))=d_{1}(\Phi(p),z)$

(valid for all $p\in\mathbb{D}^{n}$ and $z\in\mathbb{S}^{n-1}$) yields the
equations $\mathcal{R}_{2}(\mathbb{D}^{n})=\mathcal{R}_{1}(\mathbb{D}^{n})$
and
$d_{H}^{C(\mathbb{S}^{n-1})}(\mathcal{R}_{1}(\mathbb{D}^{n}),\mathcal{R}_{2}(\mathbb{D}^{n}))=0$.

In other words, the travel time data is invariant under boundary fixing
diffeomorphisms. This is the natural gauge of the problem of determining the
metric from its travel time data. In the following proposition we confirm that
this is the only obstruction.

######  Proposition 8.

If the travel time data of simple Riemannian metrics $g_{1}$ and $g_{2}$ on
$\mathbb{D}^{n}$ coincide, then the map

$\mathcal{R}_{2}^{-1}\circ\mathcal{R}_{1}\colon(\mathbb{D}^{n},g_{1})\to(\mathbb{D}^{n},g_{2}),$

is a Riemannian isometry whose boundary restriction is the identity map.

###### Proof.

Due to Definition 7 we have

$\mathcal{R}_{2}(\mathbb{D}^{n})=\mathcal{R}_{1}(\mathbb{D}^{n}).$ (3)

Then by Proposition 6, the map

$\Psi:=\mathcal{R}_{2}^{-1}\circ\mathcal{R}_{1}\colon(\mathbb{D}^{n},d_{1})\to(\mathbb{D}^{n},d_{2})$

is a well defined bijective metric isometry. Thus by the Myers–Steenrod
theorem, the map $\Psi$ is a smooth Riemannian isometry.

We get from equation (3) that for every $z\in\mathbb{S}^{n-1}$ we have

$\begin{split}d_{2}(\Psi(z),z)=d_{1}(z,z)=0,\end{split}$

which ensures that $\Psi$ is the identity at the boundary. ∎

To measure how close two compact metric spaces $X$ and $Y$ are to each other,
we use the _Gromov–Hausdorff distance_

$\begin{split}d_{GH}(X,Y):=&\inf\\{d_{H}^{Z}(f(X),g(Y));\\\ &\qquad Z\text{ is
a metric space},\\\ &\qquad f\colon X\to Z\text{ and }g\colon Y\to Z\\\
&\qquad\text{ are isometric embeddings}\\}.\end{split}$ (4)

This distance is zero if and only if the metric spaces $X$ and $Y$ are
isometric (see [5]). We are ready to formulate and prove our first main
result:

######  Theorem 9 (Stability of the Travel Time Data).

Let $n\geq 2$, and let $g_{1}$ and $g_{2}$ be two simple Riemannian metrics of
$\mathbb{D}^{n}$. Then

$d_{GH}((\mathbb{D}^{n},g_{1}),(\mathbb{D}^{n},g_{2}))\leq
d_{H}^{C(\mathbb{S}^{n-1})}(\mathcal{R}_{1}(\mathbb{D}^{n}),\mathcal{R}_{2}(\mathbb{D}^{n})).$
(5)

In particular, if the travel time data for two metrics coincide, then they
agree up to a boundary fixing isometry.

###### Proof.

Inequality (5) follows from Proposition 6 and the definition of
Gromov–Hausdorff distance. ∎

##  3\. Uniqueness and Stability of the Travel Time Difference Data

######  Proposition 10.

If $g$ is a simple metric on $\mathbb{D}^{n}$, then its travel time difference
map $\mathcal{D}$, given in Definition 3, is a metric isometry.

###### Proof.

First we observe that by triangle inequality the map $\mathcal{D}$ is
$1$-Lipschitz. For the reverse estimate, let $x,y\in\mathbb{D}^{n}$. Since $g$
is a simple metric, there exists a unique globally distance minimizing
geodesic $\gamma$ that goes through $x$ and $y$, having some endpoints
$z,w\in\mathbb{S}^{n-1}$. Since all four points $x,y,z,w$ are on the same
distance minimizing curve, we have

$|(\mathcal{D}(x)-\mathcal{D}(y))(z,w)|=\frac{1}{2}|d(x,z)-d(y,z)+d(y,w)-d(x,w)|=d(x,y).$

Thus the map $\mathcal{D}$ is a metric isometry as claimed. ∎

######  Definition 11.

We set the distance of the travel time difference data of two simple
Riemannian metrics $g_{1}$ and $g_{2}$ on $\mathbb{D}^{n}$ to be

$d_{H}^{C(\mathbb{S}^{n-1}\times\mathbb{S}^{n-1})}(\mathcal{D}_{1}(\mathbb{D}^{n}),\mathcal{D}_{2}(\mathbb{D}^{n}))\geq
0,$

where $d_{H}^{C(\mathbb{S}^{n-1}\times\mathbb{S}^{n-1})}$ is the Hausdorff
distance of the Banach space
$(C(\mathbb{S}^{n-1}\times\mathbb{S}^{n-1}),\|\cdot\|_{\infty})$ and the
travel time difference maps $\mathcal{D}_{i}$ are as in Definition 3.

Moreover, we say that the travel time difference data of the simple Riemannian
metrics $g_{1}$ and $g_{2}$ on $\mathbb{D}^{n}$ coincide if

$d_{H}^{C(\mathbb{S}^{n-1})}(\mathcal{D}_{1}(\mathbb{D}^{n}),\mathcal{D}_{2}(\mathbb{D}^{n}))=0.$

Clearly the travel time difference data is invariant under boundary fixing
diffeomorphisms. In the following proposition we show that this is the only
obstruction of determining the metric from its travel time difference data.

######  Proposition 12.

If the travel time difference data of simple Riemannian metrics $g_{1}$ and
$g_{2}$ on $\mathbb{D}^{n}$ coincide, then the map

$\mathcal{D}_{2}^{-1}\circ\mathcal{D}_{1}\colon(\mathbb{D}^{n},g_{1})\to(\mathbb{D}^{n},g_{2}),$

is a Riemannian isometry whose boundary restriction is the identity map.

###### Proof.

By Definition 11 we have

$\mathcal{D}_{1}(\mathbb{D}^{n})=\mathcal{D}_{2}(\mathbb{D}^{n})$ (6)

as subsets of the Banach space $C(\mathbb{S}^{n-1}\times\mathbb{S}^{n-1})$.
Therefore, Proposition 10 implies that the map

$\Theta:=\mathcal{D}_{2}^{-1}\circ\mathcal{D}_{1}\colon(\mathbb{D}^{n},d_{1})\to(\mathbb{D}^{n},d_{2})$

is a well defined bijective metric isometry. By the Myers–Steenrod theorem,
the map $\Theta$ is a smooth Riemannian isometry.

For every $z\in\mathbb{S}^{n-1}$, equation (6) yields

$d_{2}(\Theta(z),z)=d_{2}(\Theta(z),z)-d_{2}(\Theta(z),\Theta(z))=d_{1}(z,z)-d_{1}(z,\Theta(z))=-d_{1}(\Theta(z),z),$

and so $\Theta$ is the identity on the boundary as claimed. ∎

Our second main result is as follows.

######  Theorem 13 (Stability of the Travel Time Difference Data).

Let $n\geq 2$, and let $g_{1}$ and $g_{2}$ be two simple Riemannian metrics of
$\mathbb{D}^{n}$. Then

$d_{GH}((\mathbb{D}^{n},g_{1}),(\mathbb{D}^{n},g_{2}))\leq
d_{H}^{C(\mathbb{S}^{n-1}\times\mathbb{S}^{n-1})}(\mathcal{D}_{1}(\mathbb{D}^{n}),\mathcal{D}_{2}(\mathbb{D}^{n})).$
(7)

In particular, if the travel time difference data for two metrics coincide,
then they agree up to a boundary fixing isometry.

###### Proof.

Inequality (7) follows from Proposition 10 and the definition of
Gromov–Hausdorff distance. ∎

##  4\. Uniqueness of the Broken Scattering Relations

Suppose that $g_{1}$ is a simple metric on $\mathbb{D}^{n}$ and $g_{2}$ is the
pullback metric of $g_{1}$ under some boundary fixing diffeomorphism $\Phi$ of
$\mathbb{D}^{n}$. Then the first fundamental forms of these metrics on
$\mathbb{S}^{n-1}$ are the same. The broken scattering relations of these
metrics also coincide.

In this section we show that two simple metrics of $\mathbb{D}^{n}$ whose
first fundamental forms on $\mathbb{S}^{n-1}$ and broken scattering relations
coincide, agree up to a diffeomorphism fixing $\mathbb{S}^{n-1}$. This is
obtained via the following reduction step to the travel time data.

######  Proposition 14.

Let $g_{1}$ and $g_{2}$ be two simple Riemannian metrics on $\mathbb{D}^{n}$
whose first fundamental forms agree on $\mathbb{S}^{n-1}$. If the broken
scattering relations of these metric coincide, then their travel time data
also agree.

Proposition 14 will be proved at the end of this section with the help of
auxiliary lemmas. We will first present and prove our third main result.

######  Theorem 15 (Uniqueness of the Broken Scattering Relations).

Let $n\geq 2$, and let $g_{1}$ and $g_{2}$ be two simple Riemannian metrics of
$\mathbb{D}^{n}$ whose first fundamental forms on $\mathbb{S}^{n-1}$ agree. If
the broken scattering relations of these metric coincide, then there exists a
smooth Riemannian isometry
$\Psi\colon(\mathbb{D}^{n},g_{1})\to(\mathbb{D}^{n},g_{2})$ whose boundary
restriction $\Psi\colon\mathbb{S}^{n-1}\to\mathbb{S}^{n-1}$ is the identity
map.

###### Proof.

By Proposition 14 the travel time data of the metrics $g_{1}$ and $g_{2}$
coincide, and we can choose the Riemannian isometry $\Psi$ as in Proposition
8. ∎

The _exit time function_ $\tau_{\mathrm{exit}}\colon
S\mathbb{D}^{n}\to[0,\infty]$ of $(\mathbb{D}^{n},g)$ is defined so that the
maximal domain of definition for the geodesic with initial conditions $\eta\in
S\mathbb{D}^{n}$ is
$[-\tau_{\mathrm{exit}}(-\eta),\tau_{\mathrm{exit}}(\eta)]$. If $g$ is a
simple metric, the exit time is always finite and continuous in $\eta\in
S\mathbb{D}^{n}$ (see e.g. [3, Lemma 13]). Moreover, the boundary point
$\gamma_{v}(\tau_{\mathrm{exit}}(\eta))$ is the first point where the geodesic
$\gamma_{v}$ hits the boundary.

######  Lemma 16.

Let $g$ be a simple Riemannian metric of $\mathbb{D}^{n}$. Let
$v_{1},v_{2}\in\partial_{\mathrm{in}}S\mathbb{D}^{n}$ be such that the
geodesics $\gamma_{v_{1}}$ and $\gamma_{v_{2}}$ do not have exactly the same
endpoints on the boundary. There exists
$v_{3}\in\partial_{\mathrm{in}}S\mathbb{D}^{n}$ such that $\gamma_{v_{3}}$
intersects $\gamma_{v_{1}}$ but not $\gamma_{v_{2}}$.

###### Proof.

Let $z\in\mathbb{S}^{n-1}$ be and endpoint of $\gamma_{v_{1}}$ that is not an
endpoint of $\gamma_{v_{2}}$. Therefore short geodesics with both endpoints
sufficiently close to $z$ will not meet $\gamma_{v_{2}}$. (These geodesics can
be thought of as being almost tangent to the boundary.) By strict convexity of
the boundary at $z$ such geodesics exist, and some of them meet
$\gamma_{v_{1}}$. We simply let $v_{3}$ to be the initial data of one of these
geodesics. ∎

######  Remark 17.

Lemma 16 may fail if the boundary is not strictly convex. On the closed
hemisphere of $\mathbb{S}^{2}$ every pair of geodesics intersects each other.
This follows easily from geodesics being great circles, i.e., intersections of
the sphere and a plane through the origin. The claim of the lemma is, however,
true for hemispheres of higher dimension.

######  Lemma 18.

Let $g$ be a simple Riemannian metric on $\mathbb{D}^{n}$. Let
$v_{1},v_{2}\in\partial_{\mathrm{in}}S\mathbb{D}^{n}$. The following two
statements are equivalent:

  1. (1)

We have $V(v_{1})=V(v_{2})$, where

$V(v_{i}):=\\{w\in B\mathbb{S}^{n-1}:\text{there is }T>0\text{ for which
}N_{\mathrm{in}}(v_{i})\mathcal{B}_{T}w\\}.$ (8)

  2. (2)

Either $v_{1}=v_{2}$ or $v_{2}=-\phi_{\tau_{\mathrm{exit}}(v_{1})}(v_{1})$.

###### Proof.

Clearly (2) implies (1), and it suffices to prove the implication from (1) to
(2). Suppose, towards contradiction, that condition (2) is not true, so that
the traces of geodesics $\gamma_{v_{1}}$ and $\gamma_{v_{2}}$ are not the
same. Since $g$ is simple, these geodesics cannot have the same endpoints.
Whence, by Lemma 16, there exists
$v_{3}\in\partial_{\mathrm{in}}S\mathbb{D}^{n}$ such that $\gamma_{v_{3}}$
intersects $\gamma_{v_{1}}$ but does not intersect $\gamma_{v_{2}}$. This
contradicts condition (1). ∎

The broken scattering relations a priori record the information whether two
geodesics, starting at the boundary, intersect. Next we show that in the case
of simple metrics, more geometric information can be easily extracted from the
broken scattering relations.

For us the _scattering relation_ is the map
$\partial_{\mathrm{in}}S\mathbb{D}^{n}\ni\eta\mapsto-\phi_{\tau_{\mathrm{exit}}(\eta)}(\eta)\in\partial_{\mathrm{in}}S\mathbb{D}^{n}$.
The negative sign makes the relation map inward pointing vectors to inward
pointing vectors. In the subsequent lemma, we show that the broken scattering
relations determine the exit time function and the scattering relation on
$\partial_{\mathrm{in}}S\mathbb{D}^{n}$.

######  Lemma 19.

Let $g$ be a simple Riemannian metric of $\mathbb{D}^{n}$. The broken
scattering relations determine the scattering relation and exit time function
on $\partial_{\mathrm{in}}S\mathbb{D}^{n}$.

###### Proof.

First we observe that the broken scattering relations determine the exit time
function via the equation

$\tau_{\mathrm{exit}}(v)=\frac{1}{2}\sup\\{T>0:(N_{\mathrm{in}}v)\mathcal{B}_{T}(N_{\mathrm{in}}v)\\},\quad\text{
for any }v\in\partial_{\mathrm{in}}S\mathbb{D}^{n}_{.}$

Then we use these relations to find the set $V(v)$, as in equation (8), for
every $v\in\partial_{\mathrm{in}}S\mathbb{D}^{n}$. Let
$v_{1},v_{2}\in\partial_{\mathrm{in}}S\mathbb{D}^{n}$. Then by Lemma 18 we
have $V(v_{1})=V(v_{2})$ if and only if $v_{2}=v_{1}$ or
$v_{2}=-\phi_{\tau_{\mathrm{exit}}(v_{1})}(v_{1})$. Thus, the broken
scattering relations determine the scattering relation. ∎

######  Remark 20.

After we have recovered the scattering relation and the exit time function on
$\partial_{\mathrm{in}}S\mathbb{D}^{n}$, together known as the _lens relation_
, we could reduce the proof of Theorem 15 to the classical _boundary rigidity
problem_ , which has been solved on simple 2-manifolds [16] and for generic
simple metrics in dimensions three and higher [17]. As the broken scattering
relations carry more information than the lens relation, we can provide an
easier proof for Theorem 15 via Proposition 14.

######  Lemma 21.

Let $g$ be a simple Riemannian metric on $\mathbb{D}^{n}$. Let $v_{1},v_{2}\in
B\mathbb{S}^{n-1}$. Suppose that there exist a number $T>0$ such that
$v_{1}\mathcal{B}_{T}v_{2}.$ Then the broken scattering relations determine
the travel times $t_{1},t_{2}>0$ that satisfy the equations

$T=t_{1}+t_{2},\quad\text{ and
}\quad\gamma_{N_{\mathrm{in}}^{-1}(v_{1})}(t_{1})=\gamma_{N_{\mathrm{in}}^{-1}(v_{2})}(t_{2}).$

###### Proof.

Since $g$ is simple, each pair of distinct geodesics can intersect at most
once, and for any two distinct $v,w\in B\mathbb{D}^{n}$ the sets

$\mathcal{T}(v,w):=\\{T>0;\>v\mathcal{B}_{T}w\\}$

are either empty or singleton sets. Thus the function $T\colon
B\mathbb{S}^{n-1}\times B\mathbb{S}^{n-1}\to\mathbb{R}\cup\\{\infty\\}$
defined by

$T(v,w)=\left\\{\begin{array}[]{lll}\mathcal{T}(v,w),&v\neq
w,&\mathcal{T}(v,w)\neq\emptyset\\\ \infty,&v\neq
w,&\mathcal{T}(v,w)=\emptyset\\\
\tau_{\mathrm{exit}}(N^{-1}_{\mathrm{in}}(v)),&v=w,&\end{array}\right.$

can be found by using the broken scattering relations. In particular
$T=T(v_{1},v_{2})$.

As the broken scattering relations determine the scattering relation, we know
the directions
$\eta_{i}=N_{\mathrm{in}}(-\phi_{\tau_{\mathrm{exit}}(N_{\mathrm{in}}^{-1}v_{i})}(N_{\mathrm{in}}^{-1}v_{i}))\in
B\mathbb{S}^{n-1}$. Thus, there are some numbers $t_{1},t_{2},s_{1},s_{2}\geq
0$ that satisfy the equations

$\begin{split}\gamma_{N_{\mathrm{in}}^{-1}(v_{1})}(t_{1})&=\gamma_{N_{\mathrm{in}}^{-1}(v_{2})}(t_{2})=\gamma_{N_{\mathrm{in}}^{-1}(\eta_{1})}(s_{1})=\gamma_{N_{\mathrm{in}}^{-1}(\eta_{2})}(s_{2}),\\\
t_{1}+t_{2}&=T(v_{1},v_{2}),\qquad t_{1}+s_{1}=T(v_{1},\eta_{1}),\\\
t_{2}+s_{2}&=T(v_{2},\eta_{2}),\qquad
t_{1}+s_{2}=T(v_{1},\eta_{2}).\end{split}$

Since the linear system has a unique solution we obtain

$\begin{split}t_{1}&=\frac{1}{2}\left(T(v_{1},v_{2})-T(v_{2},\eta_{2})+T(v_{1},\eta_{2})\right)\quad\text{and}\\\
t_{2}&=T(v_{1},v_{2})-t_{1}.\end{split}$

This completes the proof. ∎

We are ready to prove Proposition 14.

###### Proof of Proposition 14.

First we assume that $g$ is a simple metric on $\mathbb{D}^{n}$. Recall that
$\nu$ is the inward pointing unit normal vector field on $\mathbb{S}^{n-1}$
with respect to this metric. We define the set

$\mathcal{D}:=\\{(s_{0},z_{0})\in\mathbb{R}\times\mathbb{S}^{n-1}:\>s_{0}\in[0,\tau_{\mathrm{exit}}(\nu(z_{0}))]\\},$

and the map

$E\colon\mathcal{D}\to\mathbb{D}^{n},\quad
E(s_{0},z_{0})=\exp_{z_{0}}(s_{0}\nu(z_{0})).$ (9)

Let $(z_{0},s_{0})\in\mathcal{D}$. We define the set $V(\nu(z_{0}))$ as in
equation (8). Since for each $v\in V(\nu(z_{0}))$ there exists a unique $T>0$
that satisfies the relation $N_{\mathrm{in}}(\nu(z_{0}))\mathcal{B}_{T}v$, we
can apply Lemma 21 to find two functions $t_{z_{0}},s_{z_{0}}\colon
V(\nu(z_{0}))\to\mathbb{R}$ that satisfy the equation
$\gamma_{\nu(z_{0})}(s_{z_{0}}(v))=\gamma_{v}(t_{z_{0}}(v))\>\text{ for every
}v\in V(\nu(z_{0})).$ Then we study the subset

$V(s_{0},z_{0})=\\{v\in V(\nu(z_{0})):\>s_{z_{0}}(v)=s_{0}\\},$

and note that by simplicity this set is an embedded submanifold of
$B\mathbb{S}^{n-1}$, and the restriction of the canonical projection
$\pi\colon B\mathbb{S}^{n-1}\to\mathbb{S}^{n-1}$ on $V(s_{0},z_{0})$ is a
diffeomorphism onto $\mathbb{S}^{n-1}$. Moreover, we have

$t_{z_{0}}(\pi|_{V(s_{0},z_{0})}^{-1}(q))=d(E(s_{0},z_{0}),q)\quad\text{ for
every }q\in\mathbb{S}^{n-1}.$

Since $(s_{0},z_{0})\in\mathcal{D}$ was arbitrary and the map $E$ is onto, we
have

$\\{t_{z_{0}}\circ\pi|^{-1}_{V(s_{0},z_{0})}\colon\mathbb{S}^{n-1}\to\mathbb{R}:\>(z_{0},s_{0})\in\mathcal{D}\\}=\mathcal{R}(\mathbb{D}^{n}).$

Let the metrics $g_{1}$ and $g_{2}$ be as in the assumption of this theorem.
Since the first fundamental forms of these metric agree on $\mathbb{S}^{n-1}$,
they have the same unit normal vector fields on $\mathbb{S}^{n-1}$. Since the
broken scattering relations of these metrics also coincide, all the objects
constructed in this and the preceding proofs are the same for both of these
metrics. Therefore the travel time data of these metrics coincide. The proof
is complete. ∎

##  5\. Diffeomorphism Invariant Data

If $\Phi\colon\mathbb{D}^{n}\to\mathbb{D}^{n}$ is a diffeomorphism that does
not need to be an identity on the boundary $\mathbb{S}^{n-1}$, and $g_{1}$ is
a simple metric on $\mathbb{D}^{n}$, then the simple pullback metric
$g_{2}:=\Phi^{\ast}g_{1}$ satisfies the equation

$d_{2}(p,q)=d_{1}(\Phi(p),\Phi(q))$

for all $p,q\in\mathbb{D}^{n}$. However, the equation
$\mathcal{R}_{1}(\mathbb{D}^{n})=\mathcal{R}_{2}(\mathbb{D}^{n})$ does not
need to be true and in general the travel time data of Definition 1 is not
fully diffeomorphism invariant.

For instance, set $z=(1,0)$ and let $\Phi$ be a diffeomorphism of
$\mathbb{D}^{2}$ for which $\Psi(-z)\neq-\Psi(z)$. Let $g_{1}$ be the
Euclidean metric and $g_{2}=\Psi^{*}g_{1}$. There are many such
$q\in\mathbb{D}^{2}$ that the travel time function
$d_{1}(q,\cdot)|_{\mathbb{S}}$ has its extreme values at $\pm z$, but only one
$p\in\mathbb{D}^{2}$ (namely, $p=\Phi^{-1}(0)$), for which $\pm z$ are both
extreme points of $d_{2}(p,\cdot)|_{\mathbb{S}}$. Therefore
$\mathcal{R}_{1}(\mathbb{D}^{n})\neq\mathcal{R}_{2}(\mathbb{D}^{n})$.

If we set a diffeomorphism $\psi\colon\mathbb{S}^{n-1}\to\mathbb{S}^{n-1}$ to
be the restriction of $\Phi^{-1}$ on $\mathbb{S}^{n-1}$, we obtain

$\mathcal{R}_{1}(\mathbb{D}^{n})=\\{d_{2}(q,\psi(\cdot))\colon\mathbb{S}^{n-1}\to\mathbb{R}|\>q\in\mathbb{D}^{n}\\}=:\mathcal{R}_{2,\psi}(\mathbb{D}^{n})$

and

$\mathcal{D}_{1}(\mathbb{D}^{n})=\\{d_{2}(q,\psi(\cdot))-d_{2}(q,\psi(\cdot))\colon\mathbb{S}^{n-1}\times\mathbb{S}^{n-1}\to\mathbb{R}|\>q\in\mathbb{D}^{n}\\}=:\mathcal{D}_{2,\psi}(\mathbb{D}^{n}).$

These suggest the following diffeomorphism invariant definitions for the
difference of the travel time and of the travel time difference data.

######  Definition 22.

Let $g_{1}$ and $g_{2}$ be two simple Riemannian metrics on $\mathbb{D}^{n}$.
We set the distance of their travel time data to be the number

$\mathcal{R}(g_{1},g_{2}):=\inf_{\psi}\\{d_{H}^{C(\mathbb{S}^{n-1})}(\mathcal{R}_{1}(\mathbb{D}^{n}),\mathcal{R}_{2,\psi}(\mathbb{D}^{n}))|\>\>\psi\text{
is a diffeomorphism of }\mathbb{S}^{n-1}\\}.$

The distance of the travel time difference data of the metrics $g_{1}$ and
$g_{2}$ is

$\mathcal{D}(g_{1},g_{2}):=\inf_{\psi}\\{d_{H}^{C(\mathbb{S}^{n-1})}(\mathcal{D}_{1}(\mathbb{D}^{n}),\mathcal{D}_{2,\psi}(\mathbb{D}^{n}))|\>\>\psi\text{
is a diffeomorphism of }\mathbb{S}^{n-1}\\}.$

The last theorem of this paper is a diffeomorphism invariant version of
Theorems 9 and 13.

######  Theorem 23 (Stability of the Diffeomorphism Invariant Data).

Let $n\geq 2$, and let $g_{1}$ and $g_{2}$ be two simple Riemannian metrics of
$\mathbb{D}^{n}$. Then

$\begin{split}d_{GH}((\mathbb{D}^{n},g_{1}),(\mathbb{D}^{n},g_{2}))&\leq\mathcal{R}(g_{1},g_{2})\quad\text{and}\\\
d_{GH}((\mathbb{D}^{n},g_{1}),(\mathbb{D}^{n},g_{2}))&\leq\mathcal{D}(g_{1},g_{2}).\end{split}$
(10)

In particular, $\mathcal{R}(g_{1},g_{2})=0$ or $\mathcal{D}(g_{1},g_{2})=0$ if
and only if the metrics $g_{1}$ and $g_{2}$ are isometric.

###### Proof.

We only provide the proof for the travel time data since the proof for the
travel time difference data is analogous. For every $\varepsilon>0$ there
exists a diffeomorphism $\psi\colon\mathbb{S}^{n-1}\to\mathbb{S}^{n-1}$
satisfying the inequality

$d_{H}^{C(\mathbb{S}^{n-1})}(\mathcal{R}_{1}(\mathbb{D}^{n}),\mathcal{R}_{2,\psi}(\mathbb{D}^{n}))<\mathcal{R}(g_{1},g_{2})+\varepsilon.$

If we define a map $\Psi\colon C(\mathbb{S}^{n-1})\to C(\mathbb{S}^{n-1})$ by
the formula $\Psi(f)=f\circ\psi,$ then Proposition 6 yields that the maps

$\begin{split}\mathcal{R}_{1}&\colon(\mathbb{D}^{n},d_{1})\to(C(\mathbb{S}^{n-1}),\|\cdot\|_{\infty})\quad\text{and}\\\
\Psi\circ\mathcal{R}_{2}&\colon(\mathbb{D}^{n},d_{2})\to(C(\mathbb{S}^{n-1}),\|\cdot\|_{\infty})\end{split}$

are metric isometries whose image sets are $\mathcal{R}_{1}(\mathbb{D}^{n})$
and $\mathcal{R}_{2,\psi}(\mathbb{D}^{n})$, respectively. Since
$\varepsilon>0$ can be chosen arbitrarily, the definition of Gromov–Hausdorff
distance gives the inequality (10).

If $\mathcal{R}(g_{1},g_{2})=0$, then by the inequality (10) the metric spaces
$(\mathbb{D}^{n},d_{1})$ and $(\mathbb{D}^{n},d_{2})$ are isometric. Whence,
the last claim follows from the Myers–Steenrod theorem. ∎

## References

  * [1] M. V. de Hoop, J. Ilmavirta, M. Lassas, and T. Saksala.  Determination of a compact Finsler manifold from its boundary distance map and an inverse problem in elasticity.  Communications in Analysis and Geometry, to appear, 2021.  arXiv:1901.03902.
  * [2] M. V. de Hoop, J. Ilmavirta, M. Lassas, and T. Saksala.  Stable reconstruction of simple Riemannian manifolds from unknown interior sources.  arXiv preprint arXiv:2102.11799, 2021.
  * [3] M. V. de Hoop, J. Ilmavirta, M. Lassas, and T. Saksala.  A foliated and reversible Finsler manifold is determined by its broken scattering relation.  Pure and Applied Analysis, 3(4):789–811, 2022.
  * [4] M. V. de Hoop and T. Saksala.  Inverse problem of travel time difference functions on a compact Riemannian manifold with boundary.  The Journal of Geometric Analysis, 29(4):3308–3327, 2019.
  * [5] M. Gromov.  Metric structures for Riemannian and non-Riemannian spaces.  Springer Science & Business Media, 2007.
  * [6] S. Ivanov.  Distance difference representations of Riemannian manifolds.  Geometriae Dedicata, 207(1):167–192, 2020.
  * [7] S. Ivanov.  Distance difference functions on nonconvex boundaries of Riemannian manifolds.  St. Petersburg Mathematical Journal, 33(1):57–64, 2022.
  * [8] A. Katchalov, Y. Kurylev, and M. Lassas.  Inverse boundary spectral problems, volume 123 of Monographs and Surveys in Pure and Applied Mathematics.  Chapman & Hall/CRC, Boca Raton, FL, 2001.
  * [9] A. Katsuda, Y. Kurylev, and M. Lassas.  Stability of boundary distance representation and reconstruction of Riemannian manifolds.  Inverse Problems & Imaging, 1(1):135, 2007.
  * [10] Y. Kurylev.  Multidimensional Gel’fand inverse problem and boundary distance map.  Inverse Problems Related with Geometry (ed. H. Soga), pages 1–15, 1997.
  * [11] Y. Kurylev, M. Lassas, and G. Uhlmann.  Rigidity of broken geodesic flow and inverse problems.  American journal of mathematics, 132(2):529–562, 2010.
  * [12] M. Lassas and T. Saksala.  Determination of a Riemannian manifold from the distance difference functions.  Asian journal of mathematics, 23(2):173–200, 2019.
  * [13] S. B. Myers and N. E. Steenrod.  The group of isometries of a Riemannian manifold.  Annals of Mathematics, 40(2):400–416, 1939.
  * [14] R. S. Palais.  On the differentiability of isometries.  Proc. Amer. Math. Soc., 8:400–416, 1957.
  * [15] E. Pavlechko and T. Saksala.  Uniqueness of the partial travel time representation of a compact Riemannian manifold with strictly convex boundary.  Inverse Problems & Imaging, to appear, 2022.  arXiv:2201.01887.
  * [16] L. Pestov and G. Uhlmann.  Two dimensional compact simple Riemannian manifolds are boundary distance rigid.  Annals of mathematics, pages 1093–1110, 2005.
  * [17] P. Stefanov and G. Uhlmann.  Boundary rigidity and stability for generic simple metrics.  Journal of the American Mathematical Society, 18(4):975–1003, 2005\.


# SLAM with Objects using a Nonparametric Pose Graph

Beipeng Mu  Laboratory for Information and Decision Systems  Shih-Yuan Liu
Laboratory for Information and Decision Systems  Liam Paull  Computer Science
and Artificial Intelligence Laboratory  John Leonard  Computer Science and
Artificial Intelligence Laboratory  Jonathan P. How  Laboratory for
Information and Decision Systems

###### Abstract

Mapping and self-localization in unknown environments are fundamental
capabilities in many robotic applications. These tasks typically involve the
identification of objects as unique features or landmarks, which requires the
objects both to be detected and then assigned a unique identifier that can be
maintained when viewed from different perspectives and in different images.
The data association and simultaneous localization and mapping (SLAM) problems
are, individually, well-studied in the literature. But these two problems are
inherently tightly coupled, and that has not been well-addressed. Without
accurate SLAM, possible data associations are combinatorial and become
intractable easily. Without accurate data association, the error of SLAM
algorithms diverge easily. This paper proposes a novel nonparametric pose
graph that models data association and SLAM in a single framework. An
algorithm is further introduced to alternate between inferring data
association and performing SLAM. Experimental results show that our approach
has the new capability of associating object detections and localizing objects
at the same time, leading to significantly better performance on both the data
association and SLAM problems than achieved by considering only one and
ignoring imperfections in the other. 111software is available at
https://github.com/BeipengMu/objectSLAM.git 222video is available at
https://youtu.be/YANUWdVLJD4

##  I Introduction

In many robotics applications, such as disaster relief, planetary exploration,
and surveillance, robots are required to autonomously explore unknown spaces
without an accurate prior map or a global position reference (e.g. GPS). A
fundamental challenge faced by the robot is to effectively localize itself
using only the information extracted from the environment. For example, the
capability of recognizing instances of objects and associating them with
unique identifiers will enable the robot to build maps of the environment and
localize itself within. The problem of constructing a global map and
localizing the robot within is referred as simultaneously localization and
mapping (SLAM).

SLAM with various representations of the world and different sensors has been
thoroughly studied in the literature. Occupancy grid map with LiDAR or laser
range finders is among the early successes that dates back to the 1980s [1, 2,
3, 4]. In occupancy based approaches, the world is represented by 2D/3D grids
composed of free spaces and occupied spaces. New scans from the LiDAR or laser
range finders are compared and matched with previous scans to incrementally
build such maps. This simplified representation of the world facilitates
efficient computation, and thus real-time performance can be achieved on
relatively large scenes with a single CPU. However, The successful matching of
two scans relies on geometric features such as corners. In places that lack
such features, like long hallways, SLAM using occupancy grid maps tends to
fail. In recent years, SLAM with 3D dense mapping and RGB-D cameras has become
more and more popular [5, 6, 7]. This line of work is able to utilize both the
geometric information from depth cameras and the color information from RGB
cameras to reconstruct environments in dense 3D maps. Incoming depth and color
images are converted into volumes or deformation surfaces [5], then matched
with previously constructed volumes or surfaces to incrementally build the
map. 3D dense maps provide photographic details of the environment with
millions of volumes or surfaces. However, they rely heavily on parallel
computation enabled by GPUs, and do not scale very well.

Figure 1: In object SLAM, each object class has multiple instances, data
association (associate detect objects to unique object idnetifiers) is
ambiguous. Data association and SLAM (localize objects) are inherently
coupled: good data association guarantees the convergence of SLAM, and good
SLAM solution gives good initialization of data association.

A factor graph is a different representation of the SLAM problem [8, 9, 10,
11]. Instead of using small units, such as grids, volumes, or surfaces, to
represent the space, a factor graph encodes the poses of the robot and the
observed landmarks along the trajectory. In a factor graph, each factor
represents a constraint on the relative poses either between two consecutive
robot poses or between a robot pose and a landmark. The robot poses and
landmark positions are modeled as random variables, and they are optimized by
maximizing the joint likelihood. Mechanisms can be designed such that new
factors are only added when there are significant pose updates or new object
measurements to facilitate concise representation. As a result, Factor graph
SLAM scales much better than SLAM with occupancy grid maps or 3D dense maps.
However, the convergence of factor graph SLAM algorithms relies heavily on
correct data association of the landmarks. Even a single false association can
cause the algorithm to diverge [12, 13].

The focus on of this work is on SLAM in unknown environment by recognizing
objects and utilizing their positions (object SLAM). A factor graph is the
natural representation, as objects can be easily represented as landmarks. A
map represented by objects is desirable, as objects are very rich in semantic
meanings. By using objects, robots can interact with other agents and perform
tasks at semantic level, such as searching for people in a forest, grasping
objects, and detecting moving cars on streets. Object SLAM requires the robot
to be able to detect objects, generate measurements, and associate these
measurements to unique identifiers. In this work, object detection refers to
the problem of identifying the occurrence of objects of some predefined object
classes within an image. An object measurement is a 3D location of the
detected object with respect to the robot pose. Data association refers to the
problem of associating object measurements to unique identifiers across
images. The problem of object detection has been an important topic in the
computer vision community. Deep learning approaches have achieved significant
success on object detections within individual images [14, 15, 16, 17, 18].
These approaches also have the ability to generalize: once a detector is
trained to recognize a object class, such as chairs, the detector can detect
different instances of the same class even in different shape, color, and
background settings. Some recent work on Region-based Convolutional Neural
Networks [15, 19] gained significant success on training deep learning models
to detect multiple objects instances within a single image. However, object
detections only suggest the existence of objects of certain predefined object
classes in an image, but provide no data association between images. given
that an object of a certain class is detected in two images, the object
detector provides no information on whether or not the detected objects in the
two images are the same object. This is problematic for SLAM especially when
there are multiple objects of the same object class in an environment. How
reliably SLAM can be achieved using only these ambiguous object detections
remains an open question. As illustrated in Figure 1, there are multiple
instances of the same object class, such as chairs. The robot would need to
establish the data association of object detections across images from
different views. Note that data association and SLAM are inherently coupled
problems: good data association guarantees the convergence of SLAM algorithms,
and good SLAM solution gives good initialization of data association.

This paper proposes a novel world representation, the nonparametric pose
graph, to jointly perform data association and SLAM. In the proposed model,
factor graphs are used to localize robots and objects, while a Dirichlet
process (DP) – a nonparametric model prior – is used to associate detections
to unique object identifiers in the scene. The inference of the data
associations and the optimization of the the robot and object poses are
performed alternatively in this algorithm. This coupled framework achieves
better performance for both data association and SLAM.

The contributions of this work are:

  * •

Creating a nonparametric pose graph model that couples data association and
SLAM.

  * •

Proposing an algorithm that jointly infers data associations and optimizes
robot poses/object locations over nonparametric pose graphs.

  * •

Developing an approach to generate object measurements from RGB and depth
images in 3D space via deep learning object detection.

  * •

Demonstrating the performance of the proposed approach via both simulated and
real-world data.

##  II Related Work

Data association of objects and SLAM are typically solved as decoupled
problems in the literature. Pillai and Leonard [20] showed that when the SLAM
solution is known, and thus there is no uncertainty in robot poses, robot
poses provide good prior information about object locations and can achieve
better recalls than frame by frame detections. Song et al. [21] used a SLAM
solver to build a 3D map of a room, and then fixed the map and manually
labeled objects in the room. On the other hand, object detection can improve
localization as well. Atanasov et al. [22] pre-mapped doors and chairs as
landmarks. During the navigation stage, these pre-mapped objects are detected
online and their location information is used to localize the robot.

However, in the scenario considered here, neither data association of objects
nor robot poses are perfectly known. The algorithm must associate objects
detections and perform SLAM simultaneously. Algorithms that solve object
detection and SLAM jointly can be categorized into front-end approaches and
back-end approaches.

###  II-A Front-end Data Association

In front-end approaches, objects detected in new images are compared with
previous images. If matches between new and old images are found, then
corresponding objects are associated to the same unique identifier. These
matches are typically reliable as the disparity between two consecutive images
are usually small. When the robot come back to a previously visited place
after traversing a long distance, costly global optimization must be performed
to achieve global loop closures. These data associations by front-end
procedures are taken as reliable and true, and then passed to a SLAM solver
[23, 24]. SLAM++ [23] is one such front-end approach. Full 3D scans of chairs
and tables are created and used as templates. When new point clouds are
observed during testing, they are matched to pre-built templates. Successfully
matched detections are often of high credibility. A SLAM solver is then run on
these reliable detections to optimize object locations and camera poses. In
semantic SLAM [24], Civera et al. created a library of six objects, used SURF
features to detect these objects, and then ran an EKF to simultaneously
localize robot and map objects.

In this work, instead of creating exact templates for objects, deep learning
is used to detect objects in the environment. Deep learning generalizes much
better than template-based approaches. It can leverage open source software
(millions of images already exist online to create models), scales easily to
hundreds of object classes instead of a handful of pre-tuned templates, and
does not require the objects in the scene to be exactly the same as the
templates. However, the detections have significant ratio of false positives
and partial occlusions, thus are very challenging for front-end algorithms to
produce reliable data associations.

###  II-B Back-end Robust SLAM

Robust SLAM is a line of research that explicitly use back-end approaches to
deal with outliers in the data [25, 9, 26]. In robust SLAM, most of the object
measurements are already correctly associated to unique identifiers. when some
measurement is incorrectly associated, it will be inconsistent with other
object measurements of the same identifier. Robust SLAM instead maximizes a
set of measurements that are consistent with each other in both identifiers
and predicted locations. Only the consistent measurements are plugged into a
SLAM solver to recover the robot poses and landmark locations.

By nature robust SLAM relies on the assumption that inlier measurements with
unique identifier associations are the majority compared to outlier
measurements. Under this assumption, eliminating outliers can still give good
SLAM results. However, in object SLAM, it is often the case that there are
multiple instances of the same object class. If all object measurements with
same class are associated to the same identifier, different object instances
will always give inconsistent measurements. In other words, in object SLAM,
outliers are pervasive. If only one set of consistent measurements for each
object class is kept, the algorithm will eliminate the majority of the data
and fail to identify any repetitive instances of the same class.

The algorithm presented in this paper is a back-end approach where there are
multiple instances of the same object class. The data association of object
measurements to unique identifiers are considered unknown and must be
established while doing SLAM. We exploit the coupling between data association
and SLAM, jointly optimize both, and achieve better performance on both.

##  III Object Measurements via Deep Learning

This section sets up the approach to generate object measurements via deep
learning. The limitations of such an approach are discussed at the end of the
section, which highlights the necessity of back-end data association and SLAM
algorithms.

###  III-A Deep Learning Based Object Detection

Object detection refers to the problem of identifying the existence of objects
of certain classes and find bounding boxes for them in single images. Object
detection in the past decade was mainly based on the use of SIFT and HOG
features. Although researchers have developed algorithms that demonstrated
good performance for single class object detection (e.g. pedestrians), the
multi-class object detection problem remains difficult. In particular, prior
to 2012, the state-of-the-art method (deformable part models) achieved 33.4%
accuracy on the PASCAL VOC 2010 dataset [15], which contains 20 object
classes.

Region-based convolutional neural network (R-CNN) [15] was among the first
works on object detection using a CNN. This algorithm uses the selective
search [27] algorithm to generate bounding box proposals, and then crops an
image patch using each proposal. The image patches are subsequently scaled and
run through a CNN model for object detection. This approach achieved 53.7%
accuracy on the PASCAL VOC dataset. R-CNN is extremely slow (13 seconds per
image) because all patches need to run through the CNN individually.

In Faster R-CNN [19], Ren et. al. ran the full image through the CNN only
once, and they only use features in top layer in each bounding box patch for
object detection. They further proposed a region proposal network (RPN) that
learns how to generate bounding box proposals by looking at the top layer
features. This new algorithm achieves 76% accuracy and an average speed of 100
milliseconds per image.

Faster R-CNN [19] uses the VOC dataset for training. Most of the object
classes in the VOC dataset [14] are rare in urban or indoor settings, such as
cows, horses, sheeps, airplanes, and boats. Our work trained a faster R-CNN
model on the ImageNet 2014 dataset [17], which contain categories that are
more relevant to indoor/urban settings, including cars, motorcycles, bicycles,
traffic lights, televisions, chairs, flowerpots, cups, and keyboards. Note
that this framework can be easily modified to parse out any other subset of
classes from the ImageNet dataset that are relevant to the specific
applications.

(a) Object detection with RGB image.

(b) The depth image corresponding to the RGB image.

(c) Object localization in 3D space

Figure 2: Deep learning based object detection

###  III-B Object Measurements

An object measurement refers to a labeled 3D location with respect to the
robot pose. To generate such measurements, location information relative to
the robot is required in addition to object detection. In this paper, this is
done by inquiring the corresponding pixels in the depth images: (1) Crop
bounding boxes in the depth image in correspondence with the RGB bounding box.
(2) Filter out background pixels that are too far away. (3) Generate point
cloud from RGB and depth pairs. (4) Compute the centroid of the point cloud as
center of the object.

Figure 2(a) shows the detected object with faster R-CNN from a single image of
an office environment. Figure 2(b) shows the corresponding depth image, and
Fig. 2(c) shows the four point clouds for the four detected objects in 3D
space.

It is clear from Fig. 2(a) that object SLAM with deep learning object
detection has two major challenges. First, there are multiple instances of the
object class, such as “chair” in Fig. 2(a). Without correct data association,
it is hard to distinguish different object instances. Standard pose-graph SLAM
algorithms can only optimize poses with exact data association, such as
g2o[28], isam[10], gtsam[29]. The second challenge is high false positive
rates. As the chair detected in Fig. 2(a), deep learning algorithms report
objects now and then when there are actually none. Blindly using these
unfiltered detections in standard SLAM algorithms will lead to “non-exist”
nodes and cause loop closure failures.

Notice that the centroid is used as the center of objects in this case. When
objects are looked at from different views, and be partially occluded,
centroids would not be a consistent measure of the object locations. In our
experience, the error could be 10-20cm. However, we will show that in office
settings, our algorithm still converges even under significant occlusion and
view point noise.

##  IV Pose Graph Background

This section sets up the background on graphical models used in SLAM problems.
The next section will extend the current pose graph to a novel nonparametric
pose graph and introduce an algorithm to perform inference on it.

###  IV-A Factor Graphs

A graphical model is a probabilistic model that expresses the conditional
dependence structure between random variables. Graphical models use a graph-
based representation to encode a complete distribution over a high-dimensional
space [30]. Commonly used graphical models include Bayesian networks, Markov
Random Fields, and factor graphs. Fig. 3 gives an example of such a factor
graph. Circles represent random variables and squares represent factors. A
factor graph is a graphical model widely used in SLAM problems. Denote
$\mathbf{X}=\\{X_{1},\cdots,X_{n}\\}$ as the random variables. Denote
$\psi_{a}(X_{\\{a\\}})$ as a factor among random variable in set $\\{a\\}$.
The the joint probability can be expressed as a product of factors:

$p(\mathbf{X}=x)\propto\prod_{a\in\mathcal{A}}\psi_{a}\left(X_{\\{a\\}}=x_{\\{a\\}}\right)$
(1)

where $\mathcal{A}$ is the set of all factors. Each factor
$\psi_{a}(x_{\\{a\\}})$ maps the values of random variables to a strictly
positive real number representing the likelihood of the variables. It also
represents probabilistic dependences among the variables in the factor.

Factor graph is an efficient representation in that it captures sparsity among
variables: two variables are independent of each other given all other
variables if and only if they do not belong to the same factor. The log
likelihood, $\log p(x)$, can be written in a sum of factors: $\log
p(x)\propto\sum_{a\in\mathcal{A}}\phi_{a}\left(x_{\\{a\\}}\right)$, where
$\mathcal{A}$ is the set of all factors. Each factor $\phi_{a}(x_{\\{a\\}})$
maps the values of random variables to a strictly positive real number
representing the log likelihood of the variables. With graphical models, there
exist fast algorithms to compute statistical properties such as
marginalization, expectation, maximum likelihood [30].

$X_{1}$$X_{2}$$X_{3}$$X_{4}$$X_{5}$$\psi_{12}$$\psi_{13}$$\psi_{23}$$\psi_{34}$$\psi_{45}$

Figure 3: Factor graph. Squares denote factors: $\psi_{12}(X_{1},X_{2})$,
$\psi_{23}(X_{2},X_{3})$, $\psi_{13}(X_{1},X_{3})$, $\psi_{34}(X_{3},X_{4})$,
and $\psi_{45}(X_{4},X_{5})$.

###  IV-B Factor Graph for SLAM

Factor graphs have gained a lot of success and popularity for SLAM problems
[10, 29] due to their efficiency. Fist assume that there exist static
landmarks that the robot can identify to localize itself.

###### Assumption 1

There exists a library of static landmarks to localize the robot in the
environment. The number and locations of these landmarks is not known a
priori.

With the landmark assumption, when moving in the environment, the robot can
obtain measurements of these landmarks. Given a dataset, the robot trajectory
is represented as a discrete sequence of poses. Denote $T$ as the total number
of time steps, and denote $\mathbf{X}_{0:T}=\\{X_{0},\cdots,X_{T}\\}$ as the
robot’s trajectory from the start to the end. Each robot pose consists of a
position and an orientation. Denote $SE(2)$ as the space of 2D poses and
$SE(3)$ as the space of 3D poses. Then $X_{t}\in SE(2)$ for 2D cases and
$X_{t}\in SE(3)$ in 3D cases. In GPS-denied environments these poses are not
directly observable. However, the robot can always measure the incremental
change between two sequential poses via an IMU or wheel encoder, which is
referred to as odometry. Denote $o_{t}$ as the odometry measurement between
pose $x_{t}$ and pose $x_{t-1}$. Under the standard assumption that $o_{t}$ is
corrupted by additive Gaussian noise, the odometry measurement at time $t$ can
be represented as:

$\displaystyle o_{t}=X_{t}\ominus X_{t-1}+v,\quad v\sim\mathcal{N}(0,Q),$ (2)

where $\ominus$ represents an operator that takes two pose and return the
relative pose between them in $SE(2)$ or $SE(3)$, and $Q$ is the odometry
noise covariance matrix. The likelihood of $o_{t}$ given the two poses is
then:

$p(o_{t};X_{t},X_{t-1})\sim\mathcal{N}(X_{t}\ominus X_{t-1},Q)$ (3)

During navigation, the robot also observes landmarks from the environment.
Assuming that there exist $M$ landmarks in the environment, which might be
unknown ahead of time. The positions of the landmarks are denoted as
$\mathbf{L}=\\{L_{1},\cdots,L_{N}\\}$. In the 2D case
$L_{i}\in\mathbb{R}^{2}$, and in the 3D case $L_{i}\in\mathbb{R}^{3}$. At time
$t$, the robot obtains $K_{t}$ landmark measurements, denoted as
$\mathbf{z}_{t}=\\{z_{t}^{1},z_{t}^{2},\cdots,z_{t}^{K_{t}}\\}$. Each
measurement is associated to a unique landmark identifiers, the associations
are denoted as $\mathbf{y}_{t}=\\{y_{t}^{1},y_{t}^{2},\cdots
y_{t}^{K_{t}}\\}$, where $y_{t}^{i}\in\\{1,\cdots,M\\}$. For example, at time
0, the robot obtained two measurements, $z_{0}=\\{z_{0}^{1},z_{0}^{2}\\}$. And
these 2 measurements are from landmark 5 and 7, then
$y_{0}=\\{y_{0}^{1},y_{0}^{2}\\}=\\{5,7\\}$.

Using the standard model that object measurements $z_{t}^{k}$ are corrupted by
additive Gaussian noise:

$z_{t}^{k}=L_{y_{t}^{k}}\ominus X_{t}+w,\quad w\sim\mathcal{N}(0,R)$ (4)

where $R$ is the measurement noise matrix. The likelihood of $z_{t}^{k}$ given
the robot pose, the landmark association and landmark pose is then:

$\displaystyle
p(z_{t}^{k};X_{t},L_{y_{t}^{k}})\sim\mathcal{N}(L_{z_{t}^{k}}\ominus X_{t},R)$
(5)

Combining Equation 2 and and Equation 4, the joint log likelihood of odometry
and landmark measurements is:

$\displaystyle\log
p(\mathbf{o}_{1:T},\mathbf{z}_{0:T};\mathbf{X}_{0:T},\mathbf{L})$
$\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\phi(o_{t};X_{t-1},X_{t})+\sum_{t=0}^{T}\sum_{k=1}^{K_{t}}\phi(z_{t}^{k};X_{t},L_{y_{t}^{k}})$
(6)

where $\phi(o_{t};X_{t-1},X_{t})$ and $\phi(z_{t}^{k};X_{t},L_{y_{t}^{k}})$
are odometry and landmark factors respectively. Using the probability
distribution formula for Gaussian noise, it can be shown that each factor
follows a quadratic form:

$\displaystyle\phi(o_{t};X_{t-1},X_{t})$ $\displaystyle=$
$\displaystyle-\frac{1}{2}\left(X_{t}\ominus
X_{t-1}-o_{t}\right)Q^{-1}\left(X_{t}\ominus X_{t-1}-o_{t}\right)$
$\displaystyle\phi(z_{t}^{k};X_{t},L_{y_{t}^{k}})$ $\displaystyle=$
$\displaystyle-\frac{1}{2}\left(L_{y_{t}^{k}}\ominus
X_{t}-z_{t}^{k}\right)R^{-1}\left(L_{y_{t}^{k}}\ominus X_{t}-z_{t}^{k}\right)$
(7)

The pose graph SLAM problem optimizes robot poses $\mathbf{X}_{0:T}$ and
object locations $\mathbf{L}$ such that the log likelihood is maximized:

$\max_{\mathbf{X}_{0:T},\mathbf{L}}\log
p(\mathbf{o}_{1:T},\mathbf{z}_{0:T};\mathbf{X}_{0:T},\mathbf{L}).$ (8)

Note that the log likelihood is nonlinear in $X_{t}$ and $L_{t}$ as $\ominus$
is a nonlinear operation in Equation 2 and Equation 4.

A factor graph representation for SLAM is also referred to as a pose graph.
Figure 4 illustrates such a pose graph. Variables represent either a robot
pose or a landmark. And factors are either odometry or landmark measurements.

$X_{0}$$X_{1}$$X_{2}$$X_{3}$$X_{4}$$L_{1}$$L_{2}$$L_{3}$$o_{01}$$o_{12}$$o_{23}$$o_{34}$$z_{0}^{1}$$z_{1}^{1}$$z_{1}^{2}$$z_{2}^{1}$$z_{2}^{2}$$z_{3}^{1}$$z_{4}^{1}$

Figure 4: Pose Graph for SLAM. $X_{t}$ denote robot poses, $L_{i}$ denote
landmarks, blue edges denote odometry and red edges denote landmark
measurements.

##  V Nonparametric Pose Graph

This section sets up the joint data association and SLAM problem by extending
the current pose graph to a novel nonparametric pose graph that tightly
couples object association with robot poses. A new algorithm is also
introduced to jointly infer the data association and perform SLAM with this
new model.

###  V-A Factor Graph with Multi-class Objects

Before we move into nonparametric factor graph for imperfect data association,
first notice in object SLAM, except for measuring the 3D location of objects,
we also observe an object class. The observed object class is not always
reliable, thus we first establish the probabilistic model for object classes.
Assume there are $N$ object classes in total. For object $i$, denote $u$ as an
observation of the object class. The likelihood of $u$ is modeled with a
Categorical distribution:

$\displaystyle p(u=j)=\pi_{i}(j),\quad j=1,\cdots,N$ (9)

Denote $\pi_{i}=\\{\pi_{i}(0),\cdots,\pi_{i}(N)\\}$,
$\sum_{n=0}^{N}\mathbf{\pi}_{i}(n)=1$. And if the true object class is $j$, we
have $\pi(j)\gg\pi(k)$ for $k\neq j$.

Notice $1\leq u\leq N$, but we especially design $\pi_{i}(0)$ to represent the
probability of false positives. This design would help the algorithm to filter
non-exist object detections in real-world experiments.

In order to have closed form updates, we apply Dirichlet prior to $\pi_{i}$
for object $i$:

$\displaystyle\pi_{i}\sim\text{Dir}(\beta_{i}).$ (10)

when there is an observation of class $j$, $u=j$, the posterior distribution
of $\pi_{i}$ is:

$\displaystyle\pi_{i}|u\sim\text{Dir}(\beta_{i}+e_{j}).$ (11)

where $e_{j}$ represents a unit vector with $j$th element to be 1.

Notice $\beta_{i}(0)$ represents the initial likelihood of object $i$ to be a
false positive. Since observations cannot be 0, when there are more and more
observations of object $i$ being obtained, the posterior $\beta_{i}(0)$ will
monotonically decrease. This is consistent with the intuition that if repeated
observations are obtained from some object, then it has lower chance to be a
false positive.

Combine the multi-class probabilistic setting with the original SLAM problem:
each object measurement would be a pair $\\{z_{t}^{k},u_{t}^{k}\\}$, where
continuous variable $z_{t}^{k}$ represents the 3D location measurement, and
discrete variable $u_{t}^{k}$ represents the observed object class. Recall
that $y_{t}^{k}=i\in\\{1,\cdots,M\\}$ represents that the $k$-th measurement
at time $t$ is from object $i$. Then $u_{t}^{k}$ is a sample from the
posterior distribution $\pi_{y_{t}^{k}}$.

$\displaystyle p(u_{t}^{k}=j)=\pi_{y_{t}^{k}}(j),\quad j\in\\{1,\cdots,N\\}$
(12)

The joint log likelihood becomes:

$\displaystyle\log
p(\mathbf{o}_{1:T},\mathbf{z}_{0:T},\mathbf{u}_{0:T};\mathbf{X}_{0:T},\mathbf{L})$
$\displaystyle=$ $\displaystyle\sum_{t=1}^{T}p(o_{t};X_{t-1},X_{t})+$
$\displaystyle\sum_{t=0}^{T}\sum_{k=1}^{K_{t}}\left(p(z_{t}^{k};X_{t},L_{y_{t}^{k}})+\log\pi_{y_{t}^{k}}(u_{t}^{k})\right)$
$\displaystyle=$
$\displaystyle\sum_{t=1}^{T}p(o_{t};X_{t-1},X_{t})+\sum_{t=0}^{T}\sum_{k=1}^{K_{t}}p(z_{t}^{k};X_{t},L_{y_{t}^{k}})$
$\displaystyle+\sum_{t=0}^{T}\sum_{k=1}^{K_{t}}\log\pi_{y_{t}^{k}}(u_{t}^{k})$
(13)

The new optimization problem is then

$\max_{\mathbf{X}_{0:T},\mathbf{L},\pi}\log
p(\mathbf{o}_{1:T},\mathbf{z}_{0:T},\mathbf{u}_{0:T};\mathbf{X}_{0:T},\mathbf{L},\mathbf{\pi}).$
(14)

Compared to (8), the observed data in problem (14) further includes object
class observations $\mathbf{u}_{0:T}$, and the variables to be estimated
further include the class of objects $\pi$. From (V-A), given data association
$\mathbf{y}_{0:T}$, the joint likelihood can be factorized into the sum of
likelihood of $\mathbf{z}_{0:T}$ and $\mathbf{o}_{0:T}$, and the likelihood of
$\mathbf{u}_{0:T}$. Therefore, the class classes $\mathbf{\pi}_{0:T}$ is
independent of the robot poses $X_{0:T}$ and object positions $\mathbf{L}$.
Optimizing (14) is equivalent to solving problem (8) and computing the object
class posterior $\pi$ independently.

###  V-B Nonparametric Pose Graph

Now we move to the case that the data association $y_{t}^{k}$ is unknown and
must be established. Deep learning-based algorithms label each object to be of
some class, but do not distinguish between different objects of the same
class. When there are multiple instances of the same object class, such as
multiple chairs in a room, possibilities for data association become
combinatorial and thus challenging. Instead of relying on a reliable front-end
procedure to associate objects, we use a back-end framework to jointly infer
the data association and object locations. Note that Because of the ambiguous
data association, the total number of objects $M$ is unknown ahead of time,
and needs to be established as well. Nonparametric models are a set of tools
that adapt the model complexity to data. It has the embedded mechanism that
the model parameters could grow when there are new data being observed. In
particular, Dirichlet Process (DP) is such a nonparametric stochastic process
that models discrete distributions but with flexible parameter size. It can be
taken as the generalization of a Dirichlet distribution with infinite
dimension. Same as Dirichlet distribution is the conjugate prior for a
categorical distribution, DP can be viewed as the conjugate prior for
infinite, nonparametric discrete distributions [31]. In this work, we use a
Dirichlet Process (DP) as the prior for data associations $y_{t}^{k}$. In
particular, assume at any point, there are $M$ objects being detected in
total, the probability of $y_{t}^{k}$ belongs to object $i$:

$\displaystyle
p(y_{t}^{k}=i)=\text{DP}(i)=\left\\{\begin{array}[]{ll}\frac{m_{i}}{\Sigma_{i}m_{i}+\alpha}&1\leq
i\leq M,\\\ \frac{\alpha}{\Sigma_{i}m_{i}+\alpha}&i=M+1.\end{array}\right.$
(17)

where $m_{i}$ is the number of measurements of object $i$, and $\alpha$ is the
concentration parameter of DP prior that determines how likely it is to create
a new object. The intuition behind this model is that the probability
$y_{t}^{k}$ is from some existing object $i\leq M$ is proportional to the
number of measurements of object $i$, and the probability $y_{t}^{k}$ is from
a new object $M+1$ is proportional to $\alpha$.

The joint log likelihood of odometry $\mathbf{o}_{0:T}$, object measurement
$\mathbf{z}_{0:T}$ and object classes $\mathbf{u}_{0:T}$ given data
association $\mathbf{y}_{0:T}$ is

$\displaystyle\log
p(\mathbf{o}_{1:T},\mathbf{z}_{0:T},\mathbf{u}_{0:T};\mathbf{X}_{0:T},\mathbf{y}_{0:T},\mathbf{L},\mathbf{\pi})$
$\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\phi(o_{t};X_{t-1},X_{t})+\sum_{t=0}^{T}\sum_{k=1}^{K_{t}}\left(\pi_{y_{t}^{k}}(u_{t}^{k})+\phi(z_{t}^{k};X_{t},L_{y_{t}^{k}})\right).$

The joint log likelihood (V-B) has the same form as (V-A). However, in (V-B),
the likelihood of object measurements $\mathbf{z}_{0:T}$ and object classes
$\mathbf{u}_{0:T}$ are correlated through data association $\mathbf{y}_{0:T}$.

The new optimization problem is then over The joint log likelihood of odometry
$\mathbf{o}_{0:T}$, object measurement $\mathbf{z}_{0:T}$ and object classes
$\mathbf{u}_{0:T}$ given data association $\mathbf{y}_{0:T}$:

$\max_{\mathbf{X}_{0:T},\mathbf{L},\mathbf{y}_{0:T},\pi}\log
p(\mathbf{o}_{1:T},\mathbf{z}_{0:T},\mathbf{u}_{0:T};\mathbf{X}_{0:T},\mathbf{L},\mathbf{y}_{0:T},\pi).$
(18)

Compared with Equation 8, the new optimization problem Equation 18 is more
challenging in that data associations $\mathbf{y}_{0:T}$ are unknown. As a
result, log probabilities of object measurements no longer have a simple form,
and the problem Equation 18 becomes a mixed integer nonlinear problem.
Secondly, the number of true objects in the environment $M$ is not necessarily
known a priori, problem Equation 18 must infer $M$ at the same time.

$X_{0}$$X_{1}$$X_{2}$$\dots$$X_{T}$$y_{0}$$y_{1}$$y_{2}$$\dots$$y_{T}$$\mathbf{L}$,
$\pi$

Figure 5: Factor graph for SLAM with imperfect data association. $y_{t}$
represents the data association: the measurement at time $t$ is from object
$y_{t}$. In SLAM with imperfect data association, $y_{t}$ is unknown and must
be established at the same time.

###  V-C Nonparametric SLAM

From the last section, for $t=1,\cdots,T,k=1,\cdots,K_{t}$, the generative
model for our problem is

$\displaystyle y_{t}^{k}$ $\displaystyle\sim\text{DP}(\alpha),$ (19a)
$\displaystyle\pi_{y_{t}^{k}}$
$\displaystyle\sim\text{Dir}(\beta_{y_{t}^{k}}),$ (19b) $\displaystyle o_{t}$
$\displaystyle\sim\mathcal{N}(X_{t}\ominus X_{t-1},Q),$ (19c) $\displaystyle
u_{t}^{k}$ $\displaystyle\sim\text{Cat}(\pi_{y_{t}^{k}}),$ (19d)
$\displaystyle z_{t}^{k}$ $\displaystyle\sim\mathcal{N}(L_{y_{t}^{k}}\ominus
X_{t},R),$ (19e)

where $\alpha$, $\beta$, $Q$, and $R$ are given parameters. Robot poses
$\mathbf{X}_{0:T}$, landmark locations $\mathbf{L}$, object class
distributions $\mathbf{\pi}_{1:M}$ and object associations $\mathbf{y}_{0:T}$
are variables to be estimated. The odometry $\mathbf{o}_{1:T}$ and object
measurements $\mathbf{z}_{0:T},\mathbf{u}_{0:T}$ are observed data.

Different from a canonical DP mixture model, the observed data
$\mathbf{z}_{0:T}$, $\mathbf{u}_{0:T}$, and $\mathbf{o}_{0:T}$ are not
independent samples given variables $\mathbf{X}_{0:T}$, $\mathbf{L}$, and
$\pi$, but are correlated through the factor graph. Therefore, the inference
involves computing maximum likelihood over factor graphs. When both
associations and variables are to be established, standard approaches
alternate between assigning data and optimizing variables. In the case of
known object number $M$, K-means has a deterministic data association, while
expectation-maximization associates data in a probabilistic way [30]. When the
number of objects is not known a priori and DP is used as prior, Markov Chain
Monte Carlo methods (e.g. Gibbs sampling) or variational inference algorithms
are widely used [30]. However, in these algorithms, the likelihood of each
label $y_{t}^{k}$ to be any underlying object $\mathbf{L}$ needs to be
computed and tracked all the time. The algorithm will need to go through all
of the data multiple times to converge to a steady state distribution. The
large scale and strong dependence of data in our problem make such approaches
inappropriate.

It is shown in [32] that under the small variance assumptions, Gibbs sampling
can be simplified to DPmeans. Instead of sampling the posterior distribution,
$y_{t}$ is assigned to be the maximum likelihood object if the likelihood is
within some certain threshold, otherwise it is assigned to a new object.
Intuitively, in this case, small variance means that the noise in odometry,
object measurement and object class is relative small, so that the posterior
distribution of $y_{t}$ is peaky.

###### Assumption 2

Variance in odometry, object measurement and object class is small, so that
the posterior distribution of data association has small variance and a unique
maximal likelihood value.

The DPmeans algorithm alternates between two steps: maximize likelihood on
variables $\mathbf{X}_{0:T},\mathbf{L},\pi$, and assign data association
$\mathbf{y}_{0:T}$ to their maximum likelihood objects. Algorithm 1 shows the
overall flow of the approach. And the following explains the algorithm step by
step.

#### Initialization (line 3)

In initialization, all $y_{t}^{k}$ are set to be an object by its own. Robot
poses $\mathbf{X}_{0:T}$ and object locations $\mathbf{L}$ are initialized by
their open loop estimation. The Dirichlet distribution prior for object class
are set to be some initial value $\beta_{0}$.

#### Optimizing data association (line 5)

While executing the main loop, the algorithm alternates between optimizing
associations $\mathbf{y}_{0:T}$, and variables $\mathbf{X}_{0:T}$,
$\mathbf{L}$, and $\mathbf{\beta}$. When optimizing object association, fix
$\mathbf{X}_{0:T}$, $\mathbf{L}$ and $\beta$, and compute the posterior of
$y_{t}^{k}$ as the product of its DP prior (17) and likelihood of measurements
$(u_{t}^{k},z_{t}^{k})$ (see (2) and (12)).

$\displaystyle
p_{i}\propto\text{DP}(i)p(u_{t}^{k};\pi_{i})p(z_{t}^{k};X_{t},L_{i}).$ (20)

Then $y_{t}^{k}$ is assigned to the maximum likelihood object

$\displaystyle y_{t}^{k}=\arg\max_{i}p_{i}.$ (21)

#### Optimizing poses (line 12)

When optimizing poses, object associations $y_{t}^{k}$ are fixed. The
posterior parameters for the Dirichlet distribution of object class can be
updated with

$\displaystyle\beta_{i}(j)\leftarrow\beta_{0}(j)+\sum_{t,k}\mathbb{I}_{y_{t}^{k}=i}\mathbb{I}_{u_{t}^{k}=j},$
(22)

where $\beta_{i}$ is the hyper parameter for the Dirichlet prior on $\pi_{i}$.
Notation $\mathbb{I}_{a=b}$ represents indicators whether quantity $a$ equals
quantity $b$. Then $\sum_{k,t}\mathbb{I}_{y_{t}^{k}=i}$ is the total number of
object detections assigned to object $i$, and
$\sum_{k,t}\mathbb{I}_{y_{t}^{k}=i}\mathbb{I}_{u_{t}^{k}=j}$ represents from
the detections of object $i$, how many are class $j$. With Dirichlet prior
$\text{Dir}(\beta_{i})$, the maximum likelihood(ML) of each object class $i$
is proportional to parameters $\beta_{i}$:

$\displaystyle\pi_{i}=\text{ML}(\text{Dir}(\beta_{i})).$ (23)

The maximum likelihood value of robot poses $\mathbf{X}_{0:T}$ and object
locations $\mathbf{L}$ can then be obtained by standard SLAM solvers (see
(8)).

#### Remove false positive (line 20)

Recall that we set $\pi_{i}(0)$ to be the probability that object $i$ is a
false positive. In initialization, $\beta_{i}(0)$ is set to be some positive
number. When new measurements of object $i$ are obtained and accumulated,
$\beta_{i}$ gets updated such that $\beta_{i}(j)$, $j>0$ becomes bigger
compared to $\beta_{i}(0)$. As a result, $\pi_{i}(0)$ decrease monotonically.
In the last step, we filter out false positives by simply putting a threshold
$\epsilon$ on $\pi_{i}(0)$.

Algorithm 1 Nonparametric SLAM

1:Odometry measurements $o_{1:T}$, Object measurements $\mathbf{u}_{0:T}$,
$\mathbf{z}_{0:T}$

2:Poses $\mathbf{X}_{0:T}$, number of objects $M$, object association
$\mathbf{y}_{0:T}$, object locations and classes $\mathbf{L}$, $\beta$

3:Initialize $\mathbf{X}_{0:T}$, $\mathbf{L}$ with open loop prediction,
initialize $\beta_{i}=\beta_{0}$. Initialize each $y_{t}^{k}$ to be an object
of its own

4:while not converged do

5: Fix $\mathbf{X}_{0:N}$, $\mathbf{L}$, $\beta$

6: for Each measurement $y_{t}^{k}$ do

7: Computer posterior $p_{i}$ of being object $i$:

8: $p_{i}\propto\text{DP}(i)p(u_{t}^{k};\pi_{i})p(z_{t}^{k};X_{t},L_{i})$

9: Assign $y_{t}^{k}$ to be maximum likelihood association:

10: $y_{t}^{k}=\arg\max_{i}p_{i}$

11: end for

12: Fix $\mathbf{y}_{0:T}$

13: for each object $i$ do

14: update class $\pi$:

15:
$\beta_{i}(j)\leftarrow\beta_{i}(j)+\sum_{t,k}\mathbb{I}_{y_{t}^{k}=i}\mathbb{I}_{u_{t}^{k}=j}$

16: $\pi_{i}=\text{ML}(\text{Dir}(\beta_{i}))$

17: end for

18: optimize $\mathbf{X}_{0:T}$, $\mathbf{L}$ with standard SLAM solver with
(8)

19:end while

20:Remove false positive

21: $\forall i$, delete object $i$ if $\pi_{i}(0)>\epsilon$

##  VI Experiment

###  VI-A Simulated Dataset

In the simulation, 15 objects are randomly generated in a 2D plane. They are
randomly assigned into 5 different object classes: red diamonds, blue circles,
green triangles, yellow stars, and magenta squares. The robot trajectory is
manually designed and passes through the environment several times. Figure
7(a) shows the ground truth of the generated dataset. At each pose $X_{t}$,
the robot observes the relative position $o_{t}^{k}$ and class $u_{t}^{k}$ of
the objects that are within its field of view. Gaussian noise are added to the
odometry measurements as well as object measurements, see (2), and (4). The
parameters of the dataset are listed in Table I.

TABLE I: Simulated Dataset Overview Distance Traveled | 72.7m
---|---
field of view | 4m, 120 degree
no. of odometry measurements | 766
no. of object measurements | 1098
odometry noise | $\mathcal{N}(0,0.02^{2})$
measurement noise | $\mathcal{N}(0,0.1^{2})$

(a) Iteration 0, 1098 objects

(b) Iteration 1, 33 objects

(c) Iteration 2, 20 objects

(d) Iteration 3, 15 objects

Figure 6: Result of nonparametric pose graph at different iterations.
Initially there are 1098 object detections. The number reduces to 33 after the
first iteration, reduces to 20 after the second iteration, and converges to
the ground truth 15 after 3 iterations.

Figure 6(a) shows the object predictions based purely on open-loop odometry.
There is significant amount of variance and drift in the distribution of these
predicted object locations, which obscures the determination of exactly how
many objects there actually are in the environment. The result after the first
iteration is shown in figure 6(b); the nonparametric pose graph clusters the
measurements and uses it to correct robot poses. The total number of objects
is reduced to 33. The result after the second iteration is shown in figure
6(c); the algorithm further reduces the total number of objects to 20. After
three iterations(figure 6(d)), the algorithm converges to the true underlying
number of objects, which is 15.

The performance of the proposed nonparametric graph (NP-Graph) is compared to
three existing methods:

  1. 1.

Frame by frame detection (FbF): each object in each frame is taken as new, and
there are neither SLAM nor data association (see Fig. 6(a)).

  2. 2.

Open-loop Object Detection (OL): use robot odometry to perform data
association across images, but do not use data association results to correct
robot poses (see Fig. 7(c)).

  3. 3.

Robust SLAM (R-SLAM): back-end algorithm that finds the maximal set of
consistent measurements, but eliminate inconsistent measurements (see Fig.
7(b)).

Figure 7 and Table II compare the SLAM performance results of four different
algorithms. Figure 8 shows the cumulative position error of the robot
trajectory compared to ground truth, while Figure 9 compares the number of
objects identified and their localization error with a variety of parameter
settings for the R-SLAM and OL approaches. FbF and OL purely rely on odometry
and do not correct robot poses, therefore have the biggest error. R-SLAM uses
a subset of object measurements to close loops on robot poses, thus the error
is smaller. Our NP-graph based approach make use of all the object
measurements, thus has the smallest error on both robot poses and object
positions. FbF does not do any data association, thus significantly over
estimate the number of objects. The OL approach does not optimize robot poses.
When the robot comes back to a visited place, the odometry has drifted
significantly thus the OL approach could not associate the objects to the same
one observed before. As a result, the OL approach also over estimate the total
number of objects. R-SLAM only keeps one set of consistent measurements for
each object class, therefore it is only able to detect one instance for each
object class, and significantly underestimate the total number of objects. NP-
Graph, on the other hand, utilize all of the object measurements and jointly
infers both robot poses and the data associations, thus can correctly infer
the right number of objects.

TABLE II:  Performance Comparison on Simulated Dataset | mean | cumulative | percent of | number | mean
---|---|---|---|---|---
| pose | trajectory | measurements | of | object
| error | error | used | objects | error
NP-Graph | 0.07 | 55.1 | 100 | 15 | 0.05
OL | 0.42 | 320.6 | 100 | 39 | 0.39
R-SLAM | 0.20 | 150.5 | 20.2 | 5 | 0.20
FbF | 0.42 | 320.6 | 100 | 1098 | 0.49

(a) Ground Truth

(b) R-SLAM

(c) OL

(d) NP-Graph

Figure 7: Simulation. Black line represents the robot trajectory. Each marker
color/shape represent an object class. FbF does neither data associate nor
SLAM. OL associate object detection across images but does not optimize robot
poses. R-SLAM only uses a subset of consistent object measurements to optimize
robot poses. Our approach NP-graph optimizes both robot poses and data
association.  Figure 8: Cumulative robot pose error along the trajectory. NP-
graph is able to use noisy label to close loops, thus has magnitude less error
than other approaches. Figure 9: Comparison of number of objects and mean
error on objects over multiple-trials. Both FbF and OL have big location error
and overestimate number of objects. R-SLAM has much smaller location error,
but always underestimate number of objects. NP-graph jointly infers object
labels and locations, thus is closest to ground truth in both number of
objects and location accuracy.

###  VI-B Office Environment

To test the performance in real-world scenarios, we collected a dataset of an
office environment and used deep learning to detect objects, such as chair,
screen, cups etc. The statistics about the office dataset is shown in Table
III.

TABLE III: Office Dataset image resolution | 640$\times$480
---|---
distance traveled | 28.06m
during | 167s
no. of odometry | 696
no. of objects | 30
no. of object detections | 1588
odometry noise | $\mathcal{N}(0,0.1))$
measurement noise | $\mathcal{N}(0,0.5)$

Table IV and Figure 10 compare the performance of FbF, R-SLAM, OL and our
approach NP-Graph. While the ground truth for object positions is not
available for this dataset, we compare the performance on the number of valid
objects, the number of inlier measurements and the variance on object
positions. An object is defined as valid when its false positive probability
$\pi_{i}(0)$ is below a threshold ($\epsilon=2\%$), otherwise it is marked as
a false positive. A measurement is denoted as an inlier when it is associated
with a valid object. The object variance is determined from the uncertainty in
the predicted location of the object from its associated measurements. From
Table IV, the NP-Graph has the highest percentage of inlier measurements, the
closest number of objects to truth, and the smallest variance on the object
locations.

While the ground truth for robot poses is not available, either, we compare
the performance qualitatively. Figure 1 shows the floor map of the environment
as well as the robot trajectory. Figure 10 compares the results of 4
approaches. FbF and OL estimation are open-loop approaches and over estimate
total number of objects. R-SLAM only uses a subset of the object measurements.
It can only identify one instance for each object class, and has bad estimates
even it closes loops on robot poses. On the other hand, NP-Graph is able to
close loops on robot poses and recover the turnings at corners. While there is
no ground truth in the office dataset for computing object localization
errors, it is worth noting that there is a sweater hanging on the shelf in the
far bottom left corner, our algorithm is able to recover its distance while
other approaches failed to.

Figure 11 shows a few examples of the detected and well associated objects,
which includes chair, screen, keyboard, toy car and the sweater hanging in the
back corner. These figures are extracted from point cloud of a single bounding
box that is associated to the corresponding object. Note that these point
clouds are only for illustration purposes, but not maintained in the
algorithm. The algorithm only uses the centroid of these point clouds as
object measurements.

TABLE IV: Performance Comparison on Office Dataset | percentage of | number of | number of | variance
---|---|---|---|---
| measurement | inlier | false positive | on
| inliers | objects | objects | objects
NP-Graph | 88.0 | 31 | 88 | 0.058
OL | 82.2 | 36 | 175 | 0.121
R-SLAM | 22.5 | 7 | 0 | 0.225
FbF | 0 | 0 | 1588 | -

(a) FbF

(b) R-SLAM

(c) OL

(d) NP-Graph

Figure 10: Office Dataset. Black line represent robot trajectory. Markers
represent objects. Each color represent an object class. FbF approach does not
do data association nor SLAM. R-SLAM does SLAM but not data association. OL
approach does data association, but not SLAM. NP-Graph jointly infers data
association and does SLAM. It has the least number of objects, data localize
the objects, and closes loop thus has least error on robot trajectory.

Figure 11: Example of detected objects, plotted from a single frame point
cloud. From left to right, top to down are chair, sweater in the corner,
screen, keyboard and toy car.

##  VII conclusion

Object SLAM is challenging as data association is ambiguous and location
measurements unknown. Data association and SLAM are inherently coupled
problems. This work proposed a novel nonparametric pose graph that tightly
couples these two problems, and developed an algorithm to alternative between
inferring data association and performing SLAM. Both simulated and real-world
datasets show that our new approach has the capability of doing data
association and SLAM simultaneously, and achieves better performance on both
associating object detections to unique identifiers and localizing objects.

## ACKNOWLEDGMENTS

This research is supported in part by ARO MURI grant W911NF-11-1-0391, ONR
grant N00014-11-1-0688 and NSF Award IIS-1318392.

## References

  * [1] A. Elfes.  Occupancy grids: A stochastic spatial representation for active robot perception.  In Sixth Conference on Uncertainty in AI, pages 7–24, 1990.
  * [2] A. Elfes.  Using occupancy grids for mobile robot perception and navigation.  Computer, 22(6):46–57, june 1989.
  * [3] S. Thrun.  Learning occupancy grids with forward sensor models.  Autonompous Robots, 15:111–127, 2003.
  * [4] S. Thrun, W. Burgard, and D. Fox.  Probabilistic Robotics.  The MIT press, Cambridge, Massachusetts, USA, 2005.
  * [5] T. Whelan, S. Leutenegger, R. S. Moreno, B. Glocker, and A. Davison.  Elasticfusion: Dense slam without a pose graph.  In Proceedings of Robotics: Science and Systems, Rome, Italy, July 2015.
  * [6] M. Keller, D. Lefloch, M. Lambers, S. Izadi, T. Weyrich, and A. Kolb.  Real-time 3d reconstruction in dynamic scenes using point-based fusion.  In 3D Vision - 3DV 2013, 2013 International Conference on, pages 1–8, June 2013.
  * [7] R. A. Newcombe, S. Izadi, O. Hilliges, D. Molyneaux, D. Kim, A. J. Davison, P. Kohli, J. Shotton, S. Hodges, and A. Fitzgibbon.  Kinectfusion: Real-time dense surface mapping and tracking.  In IEEE ISMAR. IEEE, October 2011.
  * [8] I. Mahon, S.B. Williams, O. Pizarro, and M. Johnson-Roberson.  Efficient view-based SLAM using visual loop closures.  Robotics, IEEE Transactions on, 24(5):1002–1014, Oct. 2008.
  * [9] M.C. Graham, J.P. How, and D.E. Gustafson.  Robust incremental slam with consistency-checking.  In Intelligent Robots and Systems (IROS), 2015 IEEE/RSJ International Conference on, pages 117–124, Sept 2015.
  * [10] D.M. Rosen, M. Kaess, and J.J. Leonard.  An incremental trust-region method for robust online sparse least-squares estimation.  In Robotics and Automation (ICRA), 2012 IEEE International Conference on, pages 1262–1269, May 2012.
  * [11] M. Kaess, H. Johannsson, R. Roberts, V. Ila, J. J. Leonard, and F. Dellaert.  iSAM2: Incremental smoothing and mapping using the Bayes tree.  The International Journal of Robotics Research, 31(2):216–235, 2012\.
  * [12] Michael Montemerlo and Sebastian Thrun.  Simultaneous localization and mapping with unknown data association using fastslam.  In Robotics and Automation, 2003. Proceedings. ICRA’03. IEEE International Conference on, volume 2, pages 1985–1991. IEEE, 2003.
  * [13] M.C. Graham, J.P. How, and D.E. Gustafson.  Robust incremental slam with consistency-checking.  In Intelligent Robots and Systems (IROS), 2015 IEEE/RSJ International Conference on, pages 117–124, Sept 2015.
  * [14] M. Everingham, L. Van Gool, C. K. I. Williams, J. Winn, and A. Zisserman.  The pascal visual object classes (voc) challenge.  International Journal of Computer Vision, 88(2):303–338, June 2010\.
  * [15] R. Girshick, J. Donahue, T. Darrell, and J. Malik.  Rich feature hierarchies for accurate object detection and semantic segmentation.  In Computer Vision and Pattern Recognition (CVPR), 2014 IEEE Conference on, pages 580–587, 2014.
  * [16] Christian Szegedy, Alexander Toshev, and Dumitru Erhan.  Deep neural networks for object detection.  In C.j.c. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.q. Weinberger, editors, Advances in Neural Information Processing Systems 26, pages 2553–2561. 2013.
  * [17] O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, A. C. Berg, and F. Li.  ImageNet Large Scale Visual Recognition Challenge.  International Journal of Computer Vision (IJCV), 115(3):211–252, 2015.
  * [18] Dumitru Erhan, Christian Szegedy, Alexander Toshev, and Dragomir Anguelov.  Scalable object detection using deep neural networks.  In Proceedings of the 2014 IEEE Conference on Computer Vision and Pattern Recognition, CVPR ’14, pages 2155–2162, Washington, DC, USA, 2014\. IEEE Computer Society.
  * [19] S. Ren, K. He, R. Girshick, and J. Sun.  Faster R-CNN: Towards real-time object detection with region proposal networks.  In Advances in Neural Information Processing Systems (NIPS), 2015\.
  * [20] S Pillai and J. Leonard.  Monocular slam supported object recognition.  In Proceedings of Robotics: Science and Systems, Rome, Italy, July 2015.
  * [21] S. Song, L. Zhang, and J. Xiao.  Robot in a room: Toward perfect object recognition in closed environments.  CoRR, abs/1507.02703, 2015.
  * [22] N. Atanasov, M. Zhu, K. Daniilidis, and G. Pappas.  Semantic localization via the matrix permanent.  In Proceedings of Robotics: Science and Systems, Berkeley, USA, July 2014.
  * [23] R.F. Salas-Moreno, R.A. Newcombe, H. Strasdat, P.H.J. Kelly, and A.J. Davison.  Slam++: Simultaneous localisation and mapping at the level of objects.  In Computer Vision and Pattern Recognition (CVPR), 2013 IEEE Conference on, pages 1352–1359, June 2013.
  * [24] J. Civera, D. Galvez-Lopez, L. Riazuelo, J.D. Tardos, and J. M. Montiel.  Towards semantic slam using a monocular camera.  In Intelligent Robots and Systems (IROS), 2011 IEEE/RSJ International Conference on, pages 1277–1284, Sept 2011.
  * [25] N. Sunderhauf and P. Protzel.  Towards a robust back-end for pose graph slam.  In Robotics and Automation (ICRA), 2012 IEEE International Conference on, pages 1254–1261, May 2012.
  * [26] Y. Latif, C. Cadena, and J. Neira.  Robust loop closing over time for pose graph slam.  The International Journal of Robotics Research, 2013.
  * [27] Jasper RR Uijlings, Koen EA van de Sande, Theo Gevers, and Arnold WM Smeulders.  Selective search for object recognition.  International journal of computer vision, 104(2):154–171, 2013\.
  * [28] g2o: A general framework for graph optimization.  https://openslam.org/g2o.html.
  * [29] F. Dellaert.  Factor graphs and gtsam: A hands-on introduction.  Technical Report GT-RIM-CP&R-2012-002, GT RIM, Sept 2012.
  * [30] C. M. Bishop.  Pattern Recognition and Machine Learning (Information Science and Statistics).  Springer, 1st edition, 2007.
  * [31] T. Ferguson.  A Bayesian Analysis of Some Nonparametric Problems.  The Annals of Statistics, 1(2):209–230, 1973.
  * [32] B. Kulis and M. I. Jordan.  Revisiting k-means: New algorithms via bayesian nonparametrics.  In Proceedings of the 29th International Conference on Machine Learning (ICML), pages 513–520, 2012.