# SA-LOAM: Semantic-aided LiDAR SLAM with Loop Closure

Lin Li1, Xin Kong1, Xiangrui Zhao1, Wanlong Li2, Feng Wen2, Hongbo Zhang2 and
Yong Liu1,∗ 1Lin Li, Xin Kong, Xiangrui Zhao, and Yong Liu are with the
Institute of Cyber-Systems and Control, Zhejiang University, Hangzhou 310027,
P. R. China. (*Yong Liu is the corresponding author, email:
yongliu@iipc.zju.edu.cn).2Wanlong Li, Feng Wen and Hongbo Zhang are with
Huawei Noah’s Ark Lab, Beijing, China.

###### Abstract

LiDAR-based SLAM system is admittedly more accurate and stable than others,
while its loop closure detection is still an open issue. With the development
of 3D semantic segmentation for point cloud, semantic information can be
obtained conveniently and steadily, essential for high-level intelligence and
conductive to SLAM. In this paper, we present a novel semantic-aided LiDAR
SLAM with loop closure based on LOAM, named SA-LOAM, which leverages semantics
in odometry as well as loop closure detection. Specifically, we propose a
semantic-assisted ICP, including semantically matching, downsampling and plane
constraint, and integrates a semantic graph-based place recognition method in
our loop closure detection module. Benefitting from semantics, we can improve
the localization accuracy, detect loop closures effectively, and construct a
global consistent semantic map even in large-scale scenes. Extensive
experiments on KITTI and Ford Campus dataset show that our system
significantly improves baseline performance, has generalization ability to
unseen data and achieves competitive results compared with state-of-the-art
methods.

##  I Introduction

Simultaneous Localization And Mapping (SLAM) has developed rapidly in recent
decades as one of the fundamental capabilities of robotics. Researchers have
proposed a large number of SLAM systems based on camera and LiDAR. Compared
with the camera, LiDAR can obtain accurate distance measurements directly and
is insusceptible from illumination changes, so LiDAR-based SLAM systems are
generally more stable and precise.

LOAM[1] is a state-of-the-art LiDAR-based SLAM system. Based on it, many
methods[2, 3, 4] were proposed to improve its performance. However, most of
them cannot eliminate the cumulative error and build a globally consistent map
due to the absence of a practical loop closure detection module. Moreover,
they operate at the low-level primitives, which is unsuitable for reliably
executing high-level instructions, such as “parking next to the pole/tree”.
The robots need to transform semantic concepts into a spatial representation,
maintaining a high-quality semantic map beyond the map typically built by
conventional SLAM.

Figure 1: Semantic map built by our semantic-aided LOAM on KITTI sequence 01.
Different color represents various semantics, and enlarged points are graph
nodes. It shows one example of loop closure based on the semantic graph.
Figure 2: The pipeline of our system. Raw input point cloud $P$ is input to
semantic segmentation to obtain semantic point cloud $S$. $S$ is sent to
motion estimation and loop closure module simultaneously. Pose graph is
updated when loop closure is detected and a global semantic map $M$ is
maintained gradually. Each semantic graph $G$ together constructs a graph map
for efficient loop closure detection.

With the development of deep learning, semantic information can be
conveniently acquired from images, which has been used to assist SLAM like
removing dynamic objects [5] or assisting pose estimation [6]. Unlike images,
LiDAR point clouds are sparse, unstructured and lack texture features, but
naturally have accurate 3D spatial representation. Thanks to the recent
development of point cloud semantic segmentation [7, 8, 9, 10, 11, 12, 13],
some works [3, 14] are capable introduce semantics into the pure LiDAR SLAM
system. SLOAM [3] is designed specially for forest inventory and SUMA++[14] is
a surfel-based method [15], achieving amazing accuracy in highway scenes by
dynamic removing. Moreover, semantics have shown great potential in loop
closure detection [16, 17] but not fully integrated into the LiDAR SLAM system
yet. There are still few complete LiDAR-based semantic SLAM systems, thus
deserve further exploration.

To tackle the above issues, we present SA-LOAM, a novel semantic-aided LOAM-
based SLAM system with loop closure. Specifically, we build a semantic-
assisted ICP and semantic graph-based loop closure detection module on an
open-source LOAM-based SLAM system called FLOAM [18]. In our semantic-assisted
ICP, semantic-based clustering, downsampling, and plane constraints are
implemented to reduce false matches, balance efficiency and accuracy, and
remove wrong planar features to improve the registration quality. Our loop
closure detection module is based on our previous work [16], which turns 3D
scenes into semantic graphs and obtains scenes similarity through a graph
matching network. We integrate it with loop candidates generation, geometric
verification, and maintain a lightweight semantic graph map for efficient and
robust loop closure detection. Fig. 1 is a demonstration of our result. We
hope to draw attention in exploiting semantic LiDAR system. Our contributions
are concluded as follows:

  * •

We propose a complete LiDAR-based semantic SLAM system that can construct a
global consistent semantic map even in large-scale scenes.

  * •

We present a semantic assisted ICP method based on LOAM, which makes full use
of semantics and improves the accuracy of the odometry.

  * •

We integrate a semantic-based loop closure detection method in our system and
maintain a graph map for efficiently detecting loop closures and eliminating
the accumulated error.

  * •

Experiments on the KITTI and Ford Campus dataset show that our system achieves
competitive performance compared with state-of-the-art methods and generally
promotes the accuracy of baseline to a large margin.

##  II Related Work

###  II-A LiDAR SLAM

To estimate the ego-motion, LOAM [1, 19] extracts edge and planar features
from the raw point cloud, then minimizes the distance of point-to-line and
point-to-plane. Though proposed in 2014, LOAM continually ranks the top-tier
on the KITTI Odometry Benchmark[20] among purely LiDAR-based approaches. LeGO-
LOAM [2] segments the raw point cloud, filters out small clusters, and
estimates pose by a two-step Levenberg-Marquardt optimization method. Though
it can filter out some dynamic objects, many stationary objects are removed
unwillingly, resulting in useful feature loss. IMLS-SLAM [21] uses a scan-to-
model framework, leveraging Implicit Moving Least Squares (IMLS) to
reconstruct the plane, and minimizes the distance of points to the IMLS
surface. However, it cannot achieve real-time performance due to the slow
process of calculating IMLS.

Recently, a few researchers combine semantic information to assist point cloud
registration. Zaganidis et al. [22] use semantic information to extend Normal
Distributions Transform (NDT) [23] and Generalized Iterative Closest Point
(GICP) [24]. SLOAM [3] uses semantic segmentation to detect trunks and ground,
then models them separately, achieving good results in forest scenes. SUMA
[15] is a surfel-based approach with loop closure, and SUMA++ [14] extends it
with semantics to filter out dynamic objects, achieving state-of-the-art
performance.

###  II-B LiDAR-based Loop Closure

Existing LiDAR-based loop closure detection methods can be divided into local,
global, and segment-based methods.

Local descriptor methods [25, 26, 27, 28] usually define a local reference
frame for each feature point, and then they use point distribution information
to describe features. FPFH [29] uses normal to construct histograms for key
points, effectively describing the local geometry around each key points.
However, such local features are not discriminative enough to distinguish
similar local structures.

Global descriptors are produced from the whole LiDAR scan. M2DP [30] projects
3D points to a series of 2D planes, generates signature matrixes and regards
the singular vectors as global features. Scan Context [31], LocNet [32], and
ISC [33] convert the 3D point cloud to a 2D image representation, then compare
those 2D images to find loops. PointNetVLAD [34], SeqLPD [35] and LPD-Net [36]
extract point features with PointNet [37, 38] and aggregate global features
via NetVLAD [39]. OverlapNet [17] projects the 3D points to a range image
including multiple clues (e.g., range, normal, intensity, and semantic), then
a siamese network is used to calculate the overlap score between input scans.
These methods are typically sensitive to view-point changes and partial loss
of points.

Recently, some segmentation-based approaches have been proposed. SegMatch [40]
segments point clouds into distinct elements, extracts their features, and
matches corresponding elements by a random forest. SegMap [41, 42] uses 3D
CNNs to learn descriptors for 3D point cloud segments. Benefiting from the
robustness of semantics, our prior work [16] semantically segments the point
clouds and constructs them as semantic graphs, regarding semantic objects as
graph nodes. A graph similarity network is adopted to capture their
relationships and obtain the similarity scores for graph pairs. More similar
to human perception, operating at semantic or objects level is more robust to
occlusion and view-point changes, especially in reverse loop closure
detection.

##  III Methodology

###  III-A System Overview

In this part, we give an overall introduction to the proposed semantic-aided
LiDAR SLAM system. Different from the existing methods [14, 3], which focus on
fusing semantics in registration, we explore more usage of semantics in our
system, mainly including semantic-assisted ICP III-B and semantic graph-based
loop closure detection III-C.

Fig. 2 is the pipeline of our approach. The raw point cloud $P$ is first sent
into the off-the-shelf semantic segmentation methods [7, 8, 9, 10, 11, 12, 13]
to obtain semantic point cloud $S$ with point-wise class label $l\in L$, and
$L$ is the number of semantic categories. Then $S$ is sent to the odometry
estimation module to extract flat planar features and sharp edge features,
which are later used to estimate the odometry via registered with a local map.
At the same time, the semantic point cloud $S$ is converted to semantic graph
representation $G$, which is further input to the loop closure detection
module. When detecting a closed loop, we will update the pose graph and
optimize poses. Thus, we can incrementally obtain a high-quality global
semantic map $M$.

###  III-B Semantic Assisted ICP

LOAM uses edge and planar features to register point clouds, achieving
accurate and fast localization and mapping. We extend this method with
semantic information, and the specific improvements are as follows:

  * •

Firstly, inspired by SE-NDT[22], we divide the features by their semantic
labels and registration separately, reducing the probability of false matches.

  * •

Secondly, we downsample the point clouds separately according to their
semantic labels. Most of the existing methods downsample the point clouds
through voxel grid filtering for efficiency. However, some small objects
containing useful information will inevitably be filtered out. Our semantic-
based downsampling uses different sampling rates for different kinds of
objects and can effectively maintain the information of small objects,
depicted in Fig. 3.

  * •

Thirdly, we leverage semantics to constrain the plane fitting. Based on the
assumptions that the ground plane should be parallel to the horizontal surface
and be perpendicular to the building surface, we can remove the poorly fitted
plane.

Feature Extraction. We adopt the feature extraction strategies of LOAM[1].
Specifically, we extract edge and planar features from the point cloud and
calculate the roughness of each point by

$roughness=\frac{1}{n\cdot\Arrowvert
p_{i}\Arrowvert}\Arrowvert\sum_{j=1,j\neq{i}}^{n}(p_{j}-p_{i})\Arrowvert$ (1)

where $p_{i}$ represents the target point, and $p_{j}$ is in the same ring.
Then, a threshold $\alpha$ is used to divide those points into edge points
(roughness larger than $\alpha$) and plane points (roughness smaller than
$\alpha$). For uniform sampling, each ring is divided into $N_{r}$ parts. We
select $N_{e}$ sharpest points as edge features and $N_{p}$ flattest points as
planar features in each part. Finally, we get edge feature points $C_{e}$ and
planar feature points $C_{p}$ of the whole target frame.

Motion Estimation. To estimate the ego-motion of LiDAR, we minimize the
distance from the target edge feature point to its corresponding line and the
distance from the target planar feature point to its corresponding plane. As
different semantic classes have diverse meanings which are supposed to
contribute to the localization discriminatively, we attach a semantic-related
weight $w^{l}$ to each error term. Our total optimization goal is:

$r=\sum^{L}_{l}\\{\sum_{i}(w^{l}d^{l}_{ei})+\sum_{j}(w^{l}d^{l}_{pj})\\}$ (2)

where $d^{l}_{ei}$ is the distance from the $i$-th edge feature point
$c_{ei}^{l}\in{C_{e}}$ to its corresponding line, $d^{l}_{pj}$ is the distance
from the $j$-th planar feature point $c_{pj}^{l}\in{C_{p}}$ to its
corresponding plane, $l\in L$ is the semantic label of the target feature
point, $w^{l}$ is a semantically related weight.

We firstly use the most recent $N_{m}$ frames of edge feature points $C_{e}$
and planar feature points $C_{p}$ to establish an edge feature submap $M_{e}$
and a planar feature submap $M_{p}$. In order to speed up the registration, we
downsample the submap $M_{e},M_{p},$ and the target point cloud $C_{e},C_{p},$
according to their semantic labels. Fig. 3 depicts the visualization of our
downsampling strategy. Then the odometry is estimated by registering the
downsampled feature point cloud with the submap. Specifically, given an edge
feature point $c_{ei}^{l}\in{C_{e}}$ with it’s semantic label $l\in L$, we
choose a semantic edge submap {$M^{l}_{e}\mid M^{l}_{e}\subset M_{e},l\in L$}
which has the same semantic label $l$. We use a kd-tree to find the $N_{ne}$
points closest to the target point as the corresponding points. These $N_{ne}$
points are used to fit a line, and the distance from the target point to the
corresponding line is used as the optimization target. Supposing
$m_{e1}^{l},m_{e2}^{l}\in M^{l}_{e}$ are two different points on the line, the
distance from the target point to the line can be calculated as follows:

$d_{ei}^{l}=\frac{\Arrowvert(c_{ei}^{l}-m_{e1}^{l})\times(c_{ei}^{l}-m_{e2}^{l})\Arrowvert}{\Arrowvert
m_{e1}^{l}-m_{e2}^{l}\Arrowvert}$ (3)

(a) FLOAM

(b) Ours

Figure 3: Visualization of proposed semantic-based downsampling. Most methods
use voxel-grid downsampling, causing information loss for small objects while
ours effectively retain valuable small object points.

Similarly, given a planar feature point $c_{pi}^{l}\in C_{p}$, we find
$N_{np}$ closest points in its corresponding semantic submap $M^{l}_{p}$. Then
we use these $N_{np}$ points to fit a plane. We will reserve ground planes if
their normal is vertical and building planes if their normal is horizontal.
Through this constraint, the poorly fitted planes can be removed. Supposing
$m_{p1}^{l},m_{p2}^{l},m_{p3}^{l}\in M^{l}_{p}$ are three different points on
the plane, the distance from $c_{pi}^{l}$ to the plane is:

$d_{pi}^{l}=\frac{\Arrowvert(c_{pi}^{l}-m_{p1}^{l})^{T}((m_{p1}^{l}-m_{p2}^{l})\times(m_{p1}^{l}-m_{p3}^{l}))\Arrowvert}{\Arrowvert(m_{p1}^{l}-m_{p2}^{l})\times(m_{p1}^{l}-m_{p3}^{l})\Arrowvert}$
(4)

###  III-C Semantic Based Loop Closure Detection

Our loop closure detection module mainly consists of loop candidate
generation, similarity scoring, geometric verification, and pose graph
optimization. The candidate generation part proposes potential loop candidates
according to odometry. Similarity scoring is based on our prior work [16],
which quickly estimates the similarities of pair semantic graphs through a
graph similarity network, robust to occlusion and viewpoint changes. Then,
geometry verification uses ICP to exclude the possible wrong proposals, avoid
catastrophic false-positive loop closures. Finally, more accurate poses are
updated through pose graph optimization.

Loop Candidates Generation. Given the current frame point cloud, comparing it
with all other point cloud frames is extremely time-consuming. Therefore,
frames closer to the current position are preferred according to odometry.
Specifically, frames distance less than $\delta_{d}$ m from the current frame
are kept, which is defined as:

$\delta_{d}=max(\delta_{min},min(\delta_{max},\sigma d))$ (5)

where $\sigma$ is a constant representing the drift rate of the odometry, and
$d$ represents the travel distance between the candidate frame and current
frame. $\delta_{max}$ and $\delta_{min}$ are the upper and lower bounds of
$d$, as $d$ is continually increasing through the movement. We select a
maximum of $N_{candi}$ candidates. If the number of candidates filtered by Eq.
5 is greater than $N_{candi}$, we will randomly select $N_{candi}$ candidates
from them. Random selection is more reasonable than selecting the frames
closest to the current frame due to the existence of the cumulative error.
Surely, more sampling strategies can also be tried.

TABLE I: Parameters in Our System Parameter | $\alpha$ | $N_{r}$ | $N_{e}$ | $N_{p}$ | $N_{m}$ | $N_{ne}$ | $N_{np}$ | $\sigma$ | $\delta_{min}$ | $\delta_{max}$ | $N_{candi}$ | $\zeta$ | $N_{loop}$ | $\delta_{r}$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Value | 0.1 | 6 | 20 | 50 | 20 | 5 | 5 | 0.05 | 15 | 100 | 64 | 0.95 | 5 | 100

Similarity Scoring. We adopt our previous semantic graph-based place
recognition method [16] to calculate the similarity scores among scene pairs,
which runs quickly and is lightweight and robust. We firstly cluster the
semantic point cloud $S$ to semantic graph representation $G$, which is saved
with its corresponding pose in the global semantic graph map for reuse. Note
that each semantic graph only occupies 100x4 floats at most (maximum 100 nodes
per frame with center coordinate x, y, z, and semantic label) [16], which can
be stored and read efficiently. According to the candidates proposed by loop
candidates generation, we handily index all corresponding semantic graphs in
the semantic graph map and create a batch of semantic graph pairs. Those graph
pairs are processed in parallel by the graph matching network [16] to obtain
similarity scores. We keep pairs with scores greater than $\zeta$ and choose
the $N_{loop}$ with the highest scores from the retained pairs as the final
candidates.

Geometric Verification. Usually, the candidate loop picked out based on
similarity is not necessarily correct. Therefore, we need to check the
consistency between the current and the candidate point cloud. Similar to the
odometry module III-B, we use continuous scans near the candidate point cloud
to construct a submap and use the semantic assisted ICP to register the
current point cloud with the submap. If the ICP loss $r$ in Eq. 2 is larger
than $\delta_{r}$, we consider this candidate a false positive and discard it.

Pose Graph Optimization. When we find a loop closure, we build a pose graph
and optimize it with g2o[43]. Assume that the poses corresponding to each
frame of point clouds are $\\{T_{0},T_{1},\cdots,T_{n}|T_{i}\in SE3\\}$, the
error function between frame $i$ and frame $j$ is:

$e_{i,j}=Z^{-1}_{ij}(T^{-1}_{i}\cdot T_{j})$ (6)

where $Z_{ij}$ represents the measured relative pose between frame $i$ and
frame $j$, obtained from the Geometric Verification module. After
optimization, we get a more accurate pose for each frame, and they contribute
to constructing a globally consistent semantic map $M$.

TABLE II: Relative Pose Error on KITTI Odometry

Sequence | LOAM* | FLOAM | ISC-LOAM | SUMA | SUMA++ | Ours-ODOM | Ours-LOOP
---|---|---|---|---|---|---|---
00* | -/0.78 | 0.43/0.92 | 0.42/1.02 | 0.32/0.77 | 0.22/0.65 | 0.25/0.59 |  0.18/0.59
01 | -/1.43 | 0.60/2.80 | 0.63/2.92 | 0.76/11.15 |  0.47/1.63 | 0.48/1.89 | 0.48/1.89
02* | -/0.92 | 0.52/1.56 | 0.54/1.67 | 0.93/2.93 |  0.14/3.54 | 0.28/0.77 | 0.27/0.79
03 | -/0.86 | 0.66/1.09 | 0.72/1.15 | 0.61/1.25 | 0.47/0.67 |  0.46/0.87 |  0.46/0.87
04 | -/0.71 | 0.52/1.43 | 0.56/1.50 |  0.27/0.86 |  0.27/0.34 | 0.35/0.59 | 0.35/0.59
05* | -/0.57 | 0.36/0.79 | 0.37/0.81 | 0.32/0.56 | 0.19/0.40 | 0.24/0.45 |  0.16/0.37
06* | -/0.65 | 0.39/0.72 | 0.41/0.76 | 0.51/0.64 | 0.27/0.47 | 0.25/0.52 |  0.24/0.52
07* | -/0.63 | 0.39/0.54 | 0.43/0.56 | 0.37/0.47 | 0.28/0.39 | 0.22/0.41 |  0.18/0.41
08* | -/1.12 | 0.46/1.11 | 0.50/1.20 | 0.40/1.06 | 0.34/1.01 | 0.27/0.85 |  0.25/0.84
09* | -/0.77 | 0.55/1.28 | 0.59/1.40 | 0.41/0.79 |  0.20/0.58 | 0.28/0.68 | 0.25/0.77
10 | -/0.79 | 0.58/1.77 | 0.62/1.87 | 0.44/0.99 |  0.30/0.67 | 0.35/0.78 | 0.35/0.78
Average | -/0.84 | 0.49/1.27 | 0.52/1.35 | 0.48/1.95 |  0.28/0.94 | 0.31/0.76 |  0.28/0.76

  * •

Mean relative pose error over trajectories of 100 to 800 m: relative
rotational error in degrees per 100 m / relative translational error in %.
Sequences marked with * contain loop closures. Bold numbers indicate the best
performance in terms of translational error and rotation error. The results of
LOAM marked with * is from the original paper [19].

Figure 4: Trajectories and semantic maps on test sequence 19 of the KITTI
dataset.

##  IV Experiments

In this section, we design experiments to prove that (1) our semantic assisted
ICP can effectively improve the odometry accuracy, (2) our semantic-based loop
closure detection module can efficiently reduce the cumulative error and help
establish a globally consistent map, (3) and our system has generalization
ability to unseen data.

###  IV-A Dataset and Implementation Details

We evaluate our approach on KITTI Odometry Benchmark [20] and Ford Campus
Vision and Lidar Dataset [44]. The KITTI Odometry Benchmark consists of 11
sequences (00-10) with ground truth trajectories, and the Ford Campus dataset
contains two sequences (01-02). Though both datasets were collected with a
Velodyne HDL-64E, the data distribution of the two data sets is quite
different, as KITTI was collected in Germany and Ford was collected in the
United States.

We choose the open-source work FLOAM[18] as our system baseline. In the
semantic segmentation, we use the pre-trained
model111https://github.com/PRBonn/lidar-
bonnetal/tree/master/train/tasks/semantic of RangeNet++[7] to perform semantic
segmentation in line with SUMA++[14] for a fair comparison. Both RangeNet++
and the semantic-graph-based loop closure detection method [16] we adopted are
implemented on PyTorch [45]. RangeNet++ is trained on SemanticKITTI [46],
outputting 19 semantic classes, and we reserve 12 classes according to [16] as
shown in Fig. 1, getting rid of useless semantics like the person, pedestrian.
We test our method on an Intel Core i7-9750H @3.00GHz with 16 GB RAM and an
Nvidia GeForce GTX1080 GPU with 8 GB RAM. The parameters we set are listed in
Tab. I. Semantic-related weight $w^{l}$ is defined equally in our experiment,
and we wish to find a reasonable automatic way for weights setting in the
future. Note that we have no intention of exhaustive parameter choosing, and
we believe fine-tuning will bring certain improvements.

To evaluate how each of the proposed components contributes to improving the
performance, we present poses based on semantic assisted odometry III-B (Ours-
ODOM) and poses after further optimization by loop closure III-C (Ours-LOOP),
respectively. Besides, We compare our approach with several state-of-the-art
pure LiDAR-based SLAM methods such as LOAM [1, 19], FLOAM [18] (our baseline),
SUMA [15], SUMA++ [14] and ISC-LOAM [33]. As the code of LOAM [19] is
unavailable, we directly quote its results from paper, while the results of
FLOAM222https://github.com/wh200720041/floam, ISC-
LOAM333https://github.com/wh200720041/iscloam,
SUMA444https://github.com/jbehley/SuMa, and
SUMA++555https://github.com/PRBonn/semantic_suma are obtained by using their
open-source codes.

TABLE III:  Absolute Trajectory Error on KITTI Odometry with Loop-closure

Sequence | ISC- | SUMA | SUMA++ | Ours- | Ours- | Improve
---|---|---|---|---|---|---
LOAM | ODOM | LOOP
(m) | (m) | (m) | (m) | (m)
00* | 1.60 | 1.14 | 1.17 | 5.14 | 0.99 | 80.7%
02* | 4.77 | 44.13 | 12.99 | 9.71 | 9.24 | 4.8%
05* | 2.49 | 0.86 | 0.64 | 3.04 | 0.75 | 75.3%
06* | 1.03 | 0.68 | 0.56 | 0.69 | 0.64 | 7.2%
07* | 0.56 | 0.40 | 0.37 | 0.53 | 0.36 | 32.0%
08* | 4.88 | 2.09 | 2.44 | 3.61 | 3.24 | 10.2%
09* | 2.31 | 3.88 | 1.19 | 1.74 | 1.20 | 31.0%
Average | 2.52 | 7.59 | 2.76 | 3.49 | 2.34 | 32.9%

  * •

The last column represents the improvements of Our-LOOP compared to Ours-ODOM.

###  IV-B KITTI Odometry Benchmark

Relative Pose Error. To evaluate the accuracy improvement of odometry, we test
on KITTI Odometry Benchmark and use mean Relative Pose Error (mRPE) as the
metric.

Tab. II shows the experimental results on KITTI Odometry Benchmark. Compared
with the baseline method FLOAM, our method greatly improves the odometry
accuracy. LOAM has the highest accuracy among the existing LOAM-based methods,
and our method exceeds LOAM on most sequences. SUMA and SUMA++ are surfel-
based, and SUMA++ is the state-of-the-art semantic-based method. Compared with
SUMA++, our method has better performance on long-distance sequences such as
00, 02, 05, 08. Note that sequences 00, 02, 05, 06, 07, 08, 09 have loops, and
Ours-LOOP performs generally better than Ours-ODOM without surprise. Moreover,
we find that loop closure optimization can significantly reduce the relative
rotational error on most sequences, while has less impact on the relative
translational error, which means rotational error have a greater impact on the
inconsistency of the trajectory.

Absolute Trajectory Error. To evaluate the ability of reducing the cumulative
error and establishing a globally consistent map, we further evaluate the
Absolute Trajectory Error (ATE) and give qualitative results.

In Tab. III, we find that Ours-LOOP has a great improvement in ATE compared to
Ours-ODOM on every sequence, especially on sequences 00 and 05, where Ours-
LOOP reduces the ATE by 80.7% and 75.3% , respectively. Compared with state-
of-the-art LiDAR-based methods with loop closure detection that are ISC-LOAM,
SUMA, SUMA++, Ours-LOOP has a smaller ATE on most sequences and outperforms
other methods in average.

Fig. 4 shows trajectories and semantic maps on test sequence 19 of the KITTI
dataset before and after loop closure. There are global closure loops between
the start and end of this trajectory. Due to the accumulated error of the
odometry, the trajectory generated by Ours-ODOM is inconsistent near the start
and end points. By contrast, Ours-LOOP can detect those loops and eliminate
the accumulated error of the odometry to produce a globally consistent map
that is depicted clearly in Fig. 4.

TABLE IV: Absolute Trajectory Error on Ford Campus Algorighm | Seq01 | Seq02 | Average
---|---|---|---
(m) | (m) | (m)
FLOAM | 1.61 | 7.63 | 4.62
ISC-LOAM | 2.30 | 10.38 | 6.34
SUMA | 4.45 | 75.65 | 40.05
SUMA++ | 4.22 | 63.27 | 33.75
Ours-ODOM | 1.35 | 9.02 | 5.18
Ours-LOOP | 1.35 | 6.97 | 4.16

###  IV-C Ford Campus Vision and Lidar Dataset

In order to verify the generalization ability to unseen data, we conduct
experiments on the Ford Campus dataset [44] and evaluate RTE as well as ATE.
All models used in our method are pre-trained on KITTI and have never seen
Ford’s data during the training phase.

Figure 5: Relative translational error on sequence 01 of Ford dataset. Our
method has a smaller relative error than others.

Fig. 5 shows the relative translational error on sequence 01 of the Ford
dataset. As all methods’ parameters are tuned on KITTI, they generally perform
worse on Ford. However, the SUMA-based methods are more severely affected as
we find the projection images are sparser than on KITTI due to the different
sensor settings. Among all the methods, Ours-LOOP achieves the smallest
relative error.

Figure 6: Trajectories on sequsence 02 of Ford dataset. Only Ours-LOOP
correctly finds closed loops.

Tab. IV shows the ATE, and Ours-LOOP outperforms others on both sequences.
What’s more, among all the methods, only Ours-LOOP successfully correct the
loop closures shown in Fig. 6. Note that the semantic segmentation on Ford is
much worse than on KITTI, shown in Fig. 7, which will inevitably affect the
subsequent performance. SUMA++ and our methods use the same semantics while
ours perform more consistently, benefiting from semantic graph representation.

(a) KITTI sequence 13

(b) Ford sequence 01

Figure 7: Semantic segmentation results on KITTI and Ford.

##  V Conclusion

In this paper, we present a semantic-aided LiDAR SLAM system with loop
closure. We exploit semantic information to improve the accuracy of point
cloud registration and design a semantic-graph-based loop closure detection
module to eliminate the accumulated error. The evaluation results on KITTI
Odometry Benchmark show that our semantic-based ICP can effectively improve
the odometry accuracy, and our semantic-based loop closure detection is
crucial for constructing a globally consistent map even in large-scale scenes.
Experiments on Ford Campus Dataset indicate that our method can generalize to
unseen 3D scenes, achieving state-of-the-art performance. We hope this work
can draw researchers’ attention in further integrating semantics with the
LiDAR SLAM system. In future work, we intend to investigate more applications
based on semantic graph maps.

## References

  * [1] J. Zhang and S. Singh, “Loam: Lidar odometry and mapping in real-time.,” in Robotics: Science and Systems, vol. 2, 2014.
  * [2] T. Shan and B. Englot, “Lego-loam: Lightweight and ground-optimized lidar odometry and mapping on variable terrain,” in 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 4758–4765, IEEE, 2018.
  * [3] S. W. Chen, G. V. Nardari, E. S. Lee, C. Qu, X. Liu, R. A. F. Romero, and V. Kumar, “Sloam: Semantic lidar odometry and mapping for forest inventory,” IEEE Robotics and Automation Letters, vol. 5, no. 2, pp. 612–619, 2020.
  * [4] J. Zhang and S. Singh, “Visual-lidar odometry and mapping: low-drift, robust, and fast,” in 2015 IEEE International Conference on Robotics and Automation (ICRA), pp. 2174–2181, 2015.
  * [5] B. Bescos, J. M. Fácil, J. Civera, and J. Neira, “Dynaslam: Tracking, mapping, and inpainting in dynamic scenes,” IEEE Robotics and Automation Letters, vol. 3, no. 4, pp. 4076–4083, 2018.
  * [6] K.-N. Lianos, J. L. Schönberger, M. Pollefeys, and T. Sattler, “Vso: Visual semantic odometry,” in Computer Vision – ECCV 2018 (V. Ferrari, M. Hebert, C. Sminchisescu, and Y. Weiss, eds.), (Cham), pp. 246–263, Springer International Publishing, 2018.
  * [7] A. Milioto, I. Vizzo, J. Behley, and C. Stachniss, “Rangenet++: Fast and accurate lidar semantic segmentation,” in Proc. of the IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems (IROS), 2019.
  * [8] Q. Hu, B. Yang, L. Xie, S. Rosa, Y. Guo, Z. Wang, N. Trigoni, and A. Markham, “Randla-net: Efficient semantic segmentation of large-scale point clouds,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11108–11117, 2020.
  * [9] H. Thomas, C. R. Qi, J.-E. Deschaud, B. Marcotegui, F. Goulette, and L. J. Guibas, “Kpconv: Flexible and deformable convolution for point clouds,” Proceedings of the IEEE International Conference on Computer Vision, 2019\.
  * [10] H. Zhou, X. Zhu, X. Song, Y. Ma, Z. Wang, H. Li, and D. Lin, “Cylinder3d: An effective 3d framework for driving-scene lidar semantic segmentation,” arXiv preprint arXiv:2008.01550, 2020.
  * [11] F. Zhang, J. Fang, B. Wah, and P. Torr, “Deep fusionnet for point cloud semantic segmentation,”
  * [12] H. Tang, Z. Liu, S. Zhao, Y. Lin, J. Lin, H. Wang, and S. Han, “Searching efficient 3d architectures with sparse point-voxel convolution,” in European Conference on Computer Vision, 2020.
  * [13] T. Cortinhal, G. Tzelepis, and E. E. Aksoy, “Salsanext: Fast, uncertainty-aware semantic segmentation of lidar point clouds for autonomous driving,” arXiv preprint arXiv:2003.03653, 2020.
  * [14] X. Chen, A. Milioto, E. Palazzolo, P. Giguère, J. Behley, and C. Stachniss, “Suma++: Efficient lidar-based semantic slam,” in 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 4530–4537, IEEE, 2019.
  * [15] J. Behley and C. Stachniss, “Efficient surfel-based slam using 3d laser range data in urban environments.,” in Robotics: Science and Systems, 2018.
  * [16] X. Kong, X. Yang, G. Zhai, X. Zhao, X. Zeng, M. Wang, Y. Liu, W. Li, and F. Wen, “Semantic graph based place recognition for 3d point clouds,” arXiv preprint arXiv:2008.11459, 2020.
  * [17] X. Chen, T. Läbe, A. Milioto, T. Röhling, O. Vysotska, A. Haag, J. Behley, C. Stachniss, and F. Fraunhofer, “Overlapnet: Loop closing for lidar-based slam,” in Proc. of Robotics: Science and Systems (RSS), 2020\.
  * [18] W. Han, “Fast loam.” Website, 2020.  https://github.com/wh200720041/floam.
  * [19] J. Zhang and S. Singh, “Low-drift and real-time lidar odometry and mapping,” Autonomous Robots, vol. 41, no. 2, pp. 401–416, 2017.
  * [20] A. Geiger, P. Lenz, C. Stiller, and R. Urtasun, “Vision meets robotics: The kitti dataset,” The International Journal of Robotics Research, vol. 32, no. 11, pp. 1231–1237, 2013.
  * [21] J.-E. Deschaud, “Imls-slam: scan-to-model matching based on 3d data,” in 2018 IEEE International Conference on Robotics and Automation (ICRA), pp. 2480–2485, IEEE, 2018.
  * [22] A. Zaganidis, L. Sun, T. Duckett, and G. Cielniak, “Integrating deep semantic segmentation into 3-d point cloud registration,” IEEE Robotics and Automation Letters, vol. 3, no. 4, pp. 2942–2949, 2018.
  * [23] P. Biber and W. Straßer, “The normal distributions transform: A new approach to laser scan matching,” in Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003)(Cat. No. 03CH37453), vol. 3, pp. 2743–2748, IEEE, 2003.
  * [24] A. Segal, D. Haehnel, and S. Thrun, “Generalized-icp.,” in Robotics: science and systems, vol. 2, p. 435, Seattle, WA, 2009.
  * [25] A. E. Johnson and M. Hebert, “Using spin images for efficient object recognition in cluttered 3d scenes,” IEEE Transactions on pattern analysis and machine intelligence, vol. 21, no. 5, pp. 433–449, 1999.
  * [26] S. Salti, F. Tombari, and L. Di Stefano, “Shot: Unique signatures of histograms for surface and texture description,” Computer Vision and Image Understanding, vol. 125, pp. 251–264, 2014.
  * [27] F. Tombari, S. Salti, and L. Di Stefano, “A combined texture-shape descriptor for enhanced 3d feature matching,” in 2011 18th IEEE international conference on image processing, pp. 809–812, IEEE, 2011.
  * [28] J. Guo, P. V. Borges, C. Park, and A. Gawel, “Local descriptor for robust place recognition using lidar intensity,” IEEE Robotics and Automation Letters, vol. 4, no. 2, pp. 1470–1477, 2019.
  * [29] R. B. Rusu, N. Blodow, and M. Beetz, “Fast point feature histograms (fpfh) for 3d registration,” in 2009 IEEE international conference on robotics and automation, pp. 3212–3217, IEEE, 2009.
  * [30] L. He, X. Wang, and H. Zhang, “M2dp: A novel 3d point cloud descriptor and its application in loop closure detection,” in 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 231–237, IEEE, 2016\.
  * [31] G. Kim and A. Kim, “Scan context: Egocentric spatial descriptor for place recognition within 3d point cloud map,” 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 4802–4809, 2018.
  * [32] H. Yin, L. Tang, X. Ding, Y. Wang, and R. Xiong, “Locnet: Global localization in 3d point clouds for mobile vehicles,” in 2018 IEEE Intelligent Vehicles Symposium (IV), pp. 728–733, 2018.
  * [33] H. Wang, C. Wang, and L. Xie, “Intensity scan context: Coding intensity and geometry relations for loop closure detection,” in 2020 IEEE International Conference on Robotics and Automation (ICRA), pp. 2095–2101, 2020\.
  * [34] M. Angelina Uy and G. Hee Lee, “Pointnetvlad: Deep point cloud based retrieval for large-scale place recognition,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 4470–4479, 2018.
  * [35] Z. Liu, C. Suo, S. Zhou, F. Xu, H. Wei, W. Chen, H. Wang, X. Liang, and Y.-H. Liu, “Seqlpd: Sequence matching enhanced loop-closure detection based on large-scale point cloud description for self-driving vehicles,” in 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 1218–1223, IEEE, 2019.
  * [36] Z. Liu, S. Zhou, C. Suo, P. Yin, W. Chen, H. Wang, H. Li, and Y.-H. Liu, “Lpd-net: 3d point cloud learning for large-scale place recognition and environment analysis,” in Proceedings of the IEEE International Conference on Computer Vision, pp. 2831–2840, 2019.
  * [37] C. R. Qi, H. Su, K. Mo, and L. J. Guibas, “Pointnet: Deep learning on point sets for 3d classification and segmentation,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 652–660, 2017\.
  * [38] C. R. Qi, L. Yi, H. Su, and L. J. Guibas, “Pointnet++: Deep hierarchical feature learning on point sets in a metric space,” in Advances in neural information processing systems, pp. 5099–5108, 2017.
  * [39] R. Arandjelovic, P. Gronat, A. Torii, T. Pajdla, and J. Sivic, “Netvlad: Cnn architecture for weakly supervised place recognition,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 5297–5307, 2016.
  * [40] R. Dubé, D. Dugas, E. Stumm, J. Nieto, R. Siegwart, and C. Cadena, “Segmatch: Segment based place recognition in 3d point clouds,” in 2017 IEEE International Conference on Robotics and Automation (ICRA), pp. 5266–5272, IEEE, 2017.
  * [41] R. Dubé, A. Cramariuc, D. Dugas, J. Nieto, R. Siegwart, and C. Cadena, “SegMap: 3d segment mapping using data-driven descriptors,” in Robotics: Science and Systems (RSS), 2018.
  * [42] R. Dubé, A. Cramariuc, D. Dugas, H. Sommer, M. Dymczyk, J. Nieto, R. Siegwart, and C. Cadena, “Segmap: Segment-based mapping and localization using data-driven descriptors,” The International Journal of Robotics Research, p. 0278364919863090, 2019.
  * [43] R. Kümmerle, G. Grisetti, H. Strasdat, K. Konolige, and W. Burgard, “G2o: A general framework for graph optimization,” pp. 3607 – 3613, 06 2011.
  * [44] G. Pandey, J. R. McBride, and R. M. Eustice, “Ford campus vision and lidar data set,” The International Journal of Robotics Research, vol. 30, no. 13, pp. 1543–1552, 2011.
  * [45] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, et al., “Pytorch: An imperative style, high-performance deep learning library,” in Advances in Neural Information Processing Systems, pp. 8024–8035, 2019.
  * [46] J. Behley, M. Garbade, A. Milioto, J. Quenzel, S. Behnke, C. Stachniss, and J. Gall, “Semantickitti: A dataset for semantic scene understanding of lidar sequences,” in Proceedings of the IEEE International Conference on Computer Vision, pp. 9297–9307, 2019.


In addition, the local complexity writes

$\displaystyle\frac{\int_{\mathbf{R}^{d}}R(\theta)e^{-\beta
R(\theta)/2}\pi(\mathrm{d}\theta)}{\int_{\mathbf{R}^{d}}e^{-\beta
R(\theta)/2}\pi(\mathrm{d}\theta)}$
$\displaystyle=\int_{\mathbf{R}^{d}}R(\theta)\pi_{\beta}(\mathrm{d}\theta)$
$\displaystyle=R(\theta^{\star})+\int_{\mathbf{R}^{d}}\langle\Sigma(\theta-\theta^{\star}),\theta-\theta^{\star}\rangle\pi_{\beta}(\mathrm{d}\theta)$
$\displaystyle=R(\theta^{\star})+\lVert{\theta_{\lambda}-\theta^{\star}}\rVert_{\Sigma}^{2}+\operatorname{Tr}\bigg{\\{}\Sigma\int_{\mathbf{R}^{d}}(\theta-\theta_{\lambda})(\theta-\theta_{\lambda})^{\mathsf{T}}\pi_{\beta}(\mathrm{d}\theta)\bigg{\\}}$
$\displaystyle=R(\theta_{\lambda})+\beta^{-1}\,\operatorname{Tr}[(\Sigma+\lambda
I_{d})^{-1}\Sigma].$

We conclude with the proof of the two inequalities of Proposition 3. Let
$\lambda_{1}\geqslant\dots\geqslant\lambda_{d}\geqslant 0$ denote the ordered
eigenvalues of $\Sigma$, counted with multiplicity, so that
$\lambda_{1}=\|{\Sigma}\|_{\mathrm{op}}$ and

$\displaystyle\operatorname{Tr}\big{[}(\Sigma+\lambda
I_{d})^{-1}\Sigma\big{]}$
$\displaystyle=\sum_{i=1}^{d}\frac{\lambda_{i}}{\lambda_{i}+\lambda}=\sum_{i=1}^{d}u_{i},$
$\displaystyle\log\det\big{(}I_{d}+\lambda^{-1}\Sigma\big{)}$
$\displaystyle=\sum_{i=1}^{d}\log\big{(}1+\lambda_{i}/\lambda\big{)}=\sum_{i=1}^{d}-\log(1-u_{i}),$

where $u_{i}=\lambda_{i}/(\lambda_{i}+\lambda)\in[0,1)$. The bound
$\operatorname{Tr}[(\Sigma+\lambda
I_{d})^{-1}\Sigma]\leqslant\log\det(I_{d}+\lambda^{-1}\Sigma)$ then follows
from the inequality $u_{i}\leqslant-\log(1-u_{i})$; the reverse inequality
follows from the fact that, by convexity of $u\mapsto-\log(1-u)$ and since
$u_{i}\leqslant u_{1}\leqslant 1/2$ (by the assumption
$\lambda\leqslant\lambda_{1}$)

$\frac{-\log(1-u_{i})}{u_{i}}\leqslant\frac{-\log(1-u_{1})}{u_{1}}\leqslant-2\log(1-u_{1})=2\log\bigg{(}1+\frac{\lambda_{1}}{\lambda}\bigg{)}.$

The claim follows. ∎

####  A.8.2 Proof of Proposition 2

By the representer theorem (Proposition 5), there exist
$a_{1},\dots,a_{n},b_{1},\dots,b_{n},c_{0}\in\mathbf{R}$ such that

$\frac{\mathrm{d}\rho_{n}}{\mathrm{d}\theta}(\theta)=\frac{\mathrm{d}\pi}{\mathrm{d}\theta}(\theta)\frac{\mathrm{d}\rho_{n}}{\mathrm{d}\pi}(\theta)=(2\pi\gamma^{-1})^{-d/2}\exp\bigg{\\{}-\frac{\gamma\lVert{\theta}\rVert^{2}}{2}+\sum_{i=1}^{n}\big{(}a_{i}\langle\theta,X_{i}\rangle^{2}+b_{i}\langle\theta,X_{i}\rangle\big{)}+c_{0}\bigg{\\}}$

so that $\widehat{\rho}_{n}$ is a Gaussian distribution on $\mathbf{R}^{d}$.
We write $\widehat{\rho}_{n}=\mathcal{N}(\mu_{n},\Gamma_{n})$ for
$\mu_{n}\in\mathbf{R}^{d}$ and $\Gamma_{n}\in\mathbf{R}^{d\times d}$ a
positive symmetric matrix.

Now, for a Gaussian distribution $\rho=\mathcal{N}(\mu,\Gamma)$, we have
$f_{\rho}=f_{\mu}$ (by linearity of $f_{\theta}$ in $\theta$ and since
$\int_{\mathbf{R}^{d}}\theta\rho(\mathrm{d}\theta)=\mu$), so that

$R_{n}(\rho)=R_{n}(\mu).$

In addition, since $R_{n}$ is quadratic, we have

$\langle\rho,R_{n}\rangle=\int_{\mathbf{R}^{d}}\big{\\{}R_{n}(\mu)+\langle\nabla
R_{n}(\mu),\theta-\mu\rangle+\langle\widehat{\Sigma}_{n}(\theta-\mu),\theta-\mu\rangle\big{\\}}\rho(\mathrm{d}\theta)=R_{n}(\mu)+\operatorname{Tr}(\widehat{\Sigma}_{n}\Gamma).$

Finally, the Kullback-Leibler divergence writes:

$\mathrm{KL}({\rho},{\pi})=\frac{1}{2}\big{\\{}-\log\det(\gamma\Gamma)+\operatorname{Tr}(\gamma\Gamma)-d+\gamma\lVert{\mu}\rVert^{2}\big{\\}}.$

Since $\widehat{\rho}_{n}$ minimizes the $Q$-aggregation functional (with
inverse temperature $\beta/2$) over Gaussian measures, by the previous
computations and the definition (14) we have

$\displaystyle(\mu_{n},\Gamma_{n})$
$\displaystyle=\mathop{\mathrm{arg}\,\mathrm{min}}_{\mu,\Gamma}\Big{\\{}(1-\alpha)\big{[}R_{n}(\mu)+\operatorname{Tr}(\widehat{\Sigma}_{n}\Gamma)\big{]}+\alpha
R_{n}(\mu)+$
$\displaystyle\qquad+\frac{1}{2\cdot\beta/2}\big{\\{}-\log\det(\gamma\Gamma)+\operatorname{Tr}(\gamma\Gamma)-d+\gamma\lVert{\mu}\rVert^{2}\big{\\}}\Big{\\}}$
$\displaystyle=\mathop{\mathrm{arg}\,\mathrm{min}}_{\mu,\Gamma}\Big{\\{}R_{n}(\mu)+(1-\alpha)\operatorname{Tr}(\widehat{\Sigma}_{n}\Gamma)+\beta^{-1}\big{\\{}-\log\det(\gamma\Gamma)+\operatorname{Tr}(\gamma\Gamma)+\gamma\lVert{\mu}\rVert^{2}\big{\\}}\bigg{\\}}.$

Since the terms in $\mu$ and $\Gamma$ are decoupled, we have, recalling that
$\lambda=\gamma/\beta$,

$\displaystyle\mu_{n}$
$\displaystyle=\mathop{\mathrm{arg}\,\mathrm{min}}_{\mu\in\mathbf{R}^{d}}\big{\\{}R_{n}(\mu)+\lambda\lVert{\mu}\rVert^{2}\big{\\}}=\widehat{\theta}_{\lambda}$
(158) $\displaystyle\Gamma_{n}$
$\displaystyle=\mathop{\mathrm{arg}\,\mathrm{min}}_{\Gamma}\beta^{-1}\big{\\{}-\log\det(\gamma\Gamma)+\operatorname{Tr}\big{[}\big{(}(1-\alpha)\beta\widehat{\Sigma}_{n}+\gamma
I_{d}\big{)}\Gamma\big{]}\big{\\}}$
$\displaystyle=\big{(}(1-\alpha)\beta\widehat{\Sigma}_{n}+\gamma
I_{d}\big{)}^{-1}\cdot\mathop{\mathrm{arg}\,\mathrm{min}}_{\Gamma^{\prime}}\big{\\{}-\log\det\Gamma^{\prime}+\operatorname{Tr}(\Gamma^{\prime})-d\big{\\}}$
$\displaystyle=\big{(}(1-\alpha)\beta\widehat{\Sigma}_{n}+\gamma
I_{d}\big{)}^{-1}$ (159)

where the penultimate inequality is obtained by making the change of variable
$\Gamma=\big{(}(1-\alpha)\beta\widehat{\Sigma}_{n}+\gamma
I_{d}\big{)}^{-1}\Gamma^{\prime}$ (and ignoring the $\log\det$ term that
appears that does not depend on $\Gamma^{\prime}$), while the last equation
follows from the fact that
$\operatorname{Tr}(\Gamma^{\prime})-d-\log\det(\Gamma^{\prime})\geqslant 0$
for any symmetric positive matrix, with equality if and only if
$\Gamma^{\prime}=I_{d}$ (by applying the corresponding scalar inequality to
each of the eigenvalues of $\Gamma^{\prime}$).

In particular, since $f_{\widehat{\rho}_{n}}=f_{\mu_{n}}$, the identity (158)
implies that $f_{\widehat{\rho}_{n}}=f_{\widehat{\theta}_{n}}$ corresponds to
ridge regression (irrespective of $\alpha\in[0,1]$). The claim follows. ∎

####  A.8.3 Proof of Theorem 4

Let $(X_{1},Y_{1}),\dots,(X_{n+1},Y_{n+1})$ be $n+1$ i.i.d. samples from $P$.
For any regression procedure
$f_{n}:(\mathbf{R}^{d}\times\mathbf{R})^{n}\times\mathbf{R}^{d}\to\mathbf{R}$
and $1\leqslant i\leqslant n+1$, denote
$\widehat{f}_{n}^{(i)}(x)=f_{n}\big{(}(X_{j},Y_{j})_{1\leqslant j\leqslant
n+1,j\neq i},x\big{)}$; in particular, let
$\widehat{f}_{n}=\widehat{f}_{n}^{(n+1)}$. By exchangeability of the
distribution of the sample $(X_{1},Y_{1}),\dots,(X_{n+1},Y_{n+1})$, we have

$\displaystyle{\mathbf{E}}[R(\widehat{f}_{n})]$
$\displaystyle={\mathbf{E}}[(\widehat{f}_{n}^{(n+1)}(X_{n+1})-Y_{n+1})^{2}]={\mathbf{E}}\bigg{[}\frac{1}{n+1}\sum_{i=1}^{n+1}(\widehat{f}_{n}^{(i)}(X_{i})-Y_{i})^{2}\bigg{]}.$

In addition, define
$R_{n+1}(f)=(n+1)^{-1}\sum_{i=1}^{n+1}(f(X_{i})-Y_{i})^{2}$ for
$f:\mathbf{R}^{d}\to\mathbf{R}$, and $R_{n+1}(\theta)=R_{n+1}(f_{\theta})$ for
$\theta\in\mathbf{R}^{d}$. Letting
$\widehat{\theta}_{\lambda,n+1}=\mathop{\mathrm{arg}\,\mathrm{min}}_{\theta\in\mathbf{R}^{d}}\\{R_{n+1}(\theta)+\lambda\lVert{\theta}\rVert^{2}\\}$,
we have

$\displaystyle\inf_{\theta\in\mathbf{R}^{d}}\big{\\{}R(\theta)+\lambda\lVert{\theta}\rVert^{2}\big{\\}}$
$\displaystyle=R(\theta_{\lambda})+\lambda\lVert{\theta_{\lambda}}\rVert^{2}$
$\displaystyle={\mathbf{E}}\big{[}R_{n+1}(\theta_{\lambda})+\lambda\lVert{\theta_{\lambda}}\rVert^{2}\big{]}$
$\displaystyle\geqslant{\mathbf{E}}\big{[}R_{n+1}(\widehat{\theta}_{\lambda,n+1})+\lambda\lVert{\widehat{\theta}_{\lambda,n+1}}\rVert^{2}\big{]}$
$\displaystyle\geqslant{\mathbf{E}}\big{[}R_{n+1}(\widehat{\theta}_{\lambda,n+1})\big{]}.$

Combining the previous two inequalities gives

${\mathbf{E}}[R(\widehat{f}_{n})]-\inf_{\theta\in\mathbf{R}^{d}}\big{\\{}R(\theta)+\lambda\lVert{\theta}\rVert^{2}\big{\\}}\leqslant{\mathbf{E}}\bigg{[}\frac{1}{n+1}\sum_{i=1}^{n+1}\big{\\{}(\widehat{f}_{n}^{(i)}(X_{i})-Y_{i})^{2}-(\langle\widehat{\theta}_{\lambda,n+1},X_{i}\rangle-
Y_{i})^{2}\big{\\}}\bigg{]}.$ (160)

Now, for $i=1,\dots,n+1$, denoting

$h_{i}=\left\langle\left(\sum\nolimits_{j=1}^{n+1}X_{j}X_{j}^{\mathsf{T}}+\lambda(n+1)I_{d}\right)^{-1}X_{i},X_{i}\right\rangle$

and $\theta_{i}=\widehat{\theta}_{\lambda^{\prime}}^{(i)}$, we have by Lemma 6
below (with $A=\sum_{j\neq i}X_{j}X_{j}^{\mathsf{T}}+\lambda(n+1)I_{d}$,
$\theta=\theta_{i}$ and $(x,y)=(X_{i},Y_{i})$) that

$(\langle\widehat{\theta}_{\lambda,n+1},X_{i}\rangle-
Y_{i})^{2}=(1-h_{i})^{2}(\langle\theta_{i},X_{i}\rangle-Y_{i})^{2}.$ (161)

We now separately analyze the estimators
$\widehat{f}_{\lambda},\widehat{g}_{\lambda,b}$ and $\widehat{g}_{\lambda}$.

We start with $\widehat{f}_{\lambda}$ which satisfies
$\widehat{f}_{\lambda}^{(i)}(X_{i})=(1-h_{i})^{2}\langle\theta_{i},X_{i}\rangle$.
One therefore has, by (161) and using that $0\leqslant h_{i}\leqslant 1$,

$\displaystyle(\widehat{f}_{n}^{(i)}(X_{i})-Y_{i})^{2}-(\langle\widehat{\theta}_{\lambda,n+1},X_{i}\rangle-
Y_{i})^{2}$ $\displaystyle=\big{[}(1-h_{i})^{2}\langle\theta_{i},X_{i}\rangle-
Y_{i}\big{]}^{2}-(1-h_{i})^{2}\big{[}\langle\theta_{i},X_{i}\rangle-
Y_{i}\big{]}^{2}$
$\displaystyle=-(1-h_{i})^{2}\big{\\{}1-(1-h_{i})^{2}\big{\\}}\langle\theta_{i},X_{i}\rangle^{2}+\big{\\{}1-(1-h_{i})^{2}\big{\\}}Y_{i}^{2}$
$\displaystyle\leqslant\big{\\{}2h_{i}-h_{i}^{2}\big{\\}}Y_{i}^{2}\leqslant
2b^{2}h_{i}.$

Plugging this inequality into (160) gives:

${\mathbf{E}}[R(\widehat{f}_{\lambda})]-\inf_{\theta\in\mathbf{R}^{d}}\big{\\{}R(\theta)+\lambda\lVert{\theta}\rVert^{2}\big{\\}}\leqslant\frac{2b^{2}}{n+1}\,{\mathbf{E}}\bigg{[}\sum_{i=1}^{n+1}h_{i}\bigg{]}.$

In addition, denoting
$\widehat{\Sigma}_{n+1}=(n+1)^{-1}\sum_{i=1}^{n+1}X_{i}X_{i}^{\mathsf{T}}$,

$\displaystyle{\mathbf{E}}\bigg{[}\sum_{i=1}^{n+1}h_{i}\bigg{]}$
$\displaystyle={\mathbf{E}}\bigg{[}\sum_{i=1}^{n+1}\bigg{\langle}\bigg{(}\sum_{j=1}^{n+1}X_{j}X_{j}^{\mathsf{T}}+\lambda(n+1)I_{d}\bigg{)}^{-1}X_{i},X_{i}\bigg{\rangle}\bigg{]}$
$\displaystyle={\mathbf{E}}\,\operatorname{Tr}\bigg{\\{}\bigg{(}\sum_{j=1}^{n+1}X_{j}X_{j}^{\mathsf{T}}+\lambda(n+1)I_{d}\bigg{)}^{-1}\sum_{i=1}^{n+1}X_{i}X_{i}^{\mathsf{T}}\bigg{\\}}$
$\displaystyle={\mathbf{E}}\,\operatorname{Tr}\big{\\{}\big{(}\widehat{\Sigma}_{n+1}+\lambda
I_{d}\big{)}^{-1}\widehat{\Sigma}_{n+1}\big{\\}}$
$\displaystyle\leqslant\operatorname{Tr}\big{[}(\Sigma+\lambda
I_{d})^{-1}\Sigma\big{]},$ (162)

where the last step is by convexity of $A\mapsto\operatorname{Tr}(A^{-1})$
over positive semi-definite matrices [15, Lemma 2.7], together with
${\mathbf{E}}[\widehat{\Sigma}_{n+1}]=\Sigma$. This implies the bound (30).

We now consider the truncated ridge estimator $\widehat{g}_{\lambda}$, such
that
$\widehat{g}_{\lambda}^{(i)}(X_{i})=\psi_{b}(\langle\theta_{i},X_{i}\rangle)=U_{i}\in[-b,b]$.
Note that since $-b\leqslant Y_{i}\leqslant b$, we have
$(Y_{i}-U_{i})^{2}\leqslant(Y_{i}-\langle\theta_{i},X_{i}\rangle)^{2}$ and
thus

$\displaystyle(\widehat{g}_{\lambda,b}^{(i)}(X_{i})-Y_{i})^{2}-(\langle\widehat{\theta}_{\lambda,n+1},X_{i}\rangle-
Y_{i})^{2}$
$\displaystyle=(U_{i}-Y_{i})^{2}-(1-h_{i})^{2}\big{(}\langle\theta_{i},X_{i}\rangle-
Y_{i}\big{)}^{2}$
$\displaystyle\leqslant(U_{i}-Y_{i})^{2}-\big{[}(1-h_{i})(U_{i}-Y_{i})\big{]}^{2}$
$\displaystyle=h_{i}(2-h_{i})(U_{i}-Y_{i})^{2}$ $\displaystyle\leqslant
8b^{2}h_{i}~{},$

as $|U_{i}-Y_{i}|\leqslant 2b$. Plugging this into the bound (160) together
with (162) establishes (31).

Finally, we conclude with the adaptive truncated ridge estimator
$\widehat{g}_{\lambda}$. Let $b_{i}=\max_{1\leqslant j\leqslant n+1,\,j\neq
i}|Y_{j}|$, so that
$\widehat{g}^{(i)}_{\lambda}(X_{i})=\psi_{b_{i}}(\langle\theta_{i},X_{i}\rangle)$.
Let $E_{i}$ denote the event $\\{|Y_{i}|>b_{i}\\}$, such that
$\mathbf{P}(E_{i})\leqslant 1/(n+1)$ by exchangeability. Under $E_{i}^{c}$, we
have
$(Y_{i}-\psi_{b_{i}}(\langle\theta_{i},X_{i}\rangle))^{2}\leqslant(Y_{i}-\langle\theta_{i},X_{i}\rangle)^{2}$,
and the same argument as before shows that

$(\widehat{g}_{\lambda,b}^{(i)}(X_{i})-Y_{i})^{2}-(\langle\widehat{\theta}_{\lambda,n+1},X_{i}\rangle-
Y_{i})^{2}\leqslant 8b_{i}^{2}h_{i}\leqslant 8b^{2}h_{i}^{2}.$

Under $E_{i}$, one can always bound
$(\widehat{g}_{\lambda,b}^{(i)}(X_{i})-Y_{i})^{2}\leqslant 4b^{2}$. The
constant can be improved as follows: if $\langle\theta_{i},X_{i}\rangle$ and
$Y_{i}$ are of opposite signs, then again
$(Y_{i}-\psi_{b_{i}}(\langle\theta_{i},X_{i}\rangle))^{2}\leqslant(Y_{i}-\langle\theta_{i},X_{i}\rangle)^{2}$
so the bound $8b^{2}h_{i}^{2}$ still holds; if they are of the same sign, then
$(Y_{i}-\psi_{b_{i}}(\langle\theta_{i},X_{i}\rangle))^{2}\leqslant b^{2}$. As
a result, we have in all cases:

$(\widehat{g}_{\lambda,b}^{(i)}(X_{i})-Y_{i})^{2}-(\langle\widehat{\theta}_{\lambda,n+1},X_{i}\rangle-
Y_{i})^{2}\leqslant 8b^{2}h_{i}^{2}+b^{2}\bm{1}_{E_{i}}.$

Plugging this into the bound (160), together with the inequality (162) and the
bound $\mathbf{P}(E_{i})\leqslant 1/(n+1)$ gives the claimed guarantee (32).

######  Lemma 6.

Let $A$ be a symmetric positive $d\times d$ matrix, $b\in\mathbf{R}^{d}$ and
$\theta=A^{-1}b$. Let $(x,y)\in\mathbf{R}^{d}\times\mathbf{R}$, and define
$b^{\prime}=b+yx$, $A^{\prime}=A+xx^{\mathsf{T}}$ and
$\theta^{\prime}=A^{\prime-1}b^{\prime}$. Define $h=\langle
A^{\prime-1}x,x\rangle$. Then, we have

$\langle\theta^{\prime},x\rangle-y=(1-h)\big{(}\langle\theta,x\rangle-y\big{)}.$
(163)

###### Proof.

It follows from the Sherman-Morrison identity that

$A^{\prime-1}x=\Big{(}A^{-1}-\frac{A^{-1}xx^{\mathsf{T}}A^{-1}}{1+\langle
A^{-1}x,x\rangle}\Big{)}x=\frac{A^{-1}x}{1+\langle A^{-1}x,x\rangle},$ (164)

so that, in particular, $h=\langle A^{\prime-1}x,x\rangle=\langle
A^{-1}x,x\rangle/(1+\langle A^{-1}x,x\rangle)$ (or alternatively $\langle
A^{-1}x,x\rangle=h/(1-h)$), and thus (164) writes as
$A^{\prime-1}x=(1-h)A^{-1}x$. This implies that

$\displaystyle\langle\theta^{\prime},x\rangle-y$ $\displaystyle=\langle
A^{\prime-1}b^{\prime},x\rangle-y$ $\displaystyle=\langle
A^{\prime-1}x,b+yx\rangle-y$ $\displaystyle=(1-h)\langle
A^{-1}x,b+yx\rangle-y$ $\displaystyle=(1-h)\langle
A^{-1}b,x\rangle+(1-h)\langle A^{-1}x,x\rangle y-y$
$\displaystyle=(1-h)(\langle\theta,x\rangle-y).$

The claim follows. ∎