11institutetext: School of Science, Edith Cowan University, Australia
22institutetext: Department of Electrical Engineering, Chalmers University of
Technology 33institutetext: School of Computer Science, The University of
Adelaide, Australia

# Fast Semantic-Assisted Outlier Removal for Large-scale Point Cloud
Registration

Giang Truong 11 Huu Le 22 Alvaro Parra 33 Syed Zulqarnain Gilani 11 Syed M. S.
Islam 11 David Suter 11

###### Abstract

With current trends in sensors (cheaper, more volume of data) and applications
(increasing affordability for new tasks, new ideas in what 3D data could be
useful for); there is corresponding increasing interest in the ability to
automatically, reliably, and cheaply, register together individual point
clouds. The volume of data to handle, and still elusive need to have the
registration occur fully reliably and fully automatically, mean there is a
need to innovate further. One largely untapped area of innovation is that of
exploiting the semantic information of the points in question. Points on a
tree should match points on a tree, for example, and not points on car.
Moreover, such a natural restriction is clearly human-like - a human would
generally quickly eliminate candidate regions for matching based on semantics.
Employing semantic information is not only efficient but natural. It is also
timely - due to the recent advances in semantic classification capabilities.
This paper advances this theme by demonstrating that state of the art
registration techniques, in particular ones that rely on “preservation of
length under rigid motion” as an underlying matching consistency constraint,
can be augmented with semantic information. Semantic identity is of course
also preserved under rigid-motion, but also under wider motions present in a
scene. We demonstrate that not only the potential obstacle of cost of semantic
segmentation, and the potential obstacle of unreliability of semantic
segmentation; are both no impediment to achieving both speed and accuracy in
fully automatic registration of large scale point clouds. In particular, we
take a state of the art approach, that uses an (approximate) maximum clique
heuristic (a clique on edges encapsulating matches that preserve length), to
yield a version further enhanced with exploitation of semantic information. In
essence, cheaply and reliably (for the purposes required) pruning the data
that has to be dealt with.

###### Keywords:

Semantic Segmentation, 3D Point Cloud, Registration, Alignment, Maximum Clique

##  1 Introduction

Point cloud registration is an important problem underpinning a wide range of
computer vision applications: such as object recognition [1], real-time depth
fusion [2] and localization [3] among others. Given two sets of points in
three-dimensional (3D) space, the goal is to estimate a rigid-body
transformation, consisting of a rotation matrix $\mathbf{R}\in SO(3)$ and a
translation vector $\mathbf{t}\in\mathbb{R}^{3}$, that best aligns the two
input point sets. While a variety of methods exist in the literature to
address this problem [4, 5, 6], handling a large proportion of erroneous
matches (outliers) present in many large scale datasets, is still a difficult
challenge for existing methods. To address this problem, we propose a novel
method for fast outlier removal that can be used – as a data pre-processor –
to significantly boost the performance of existing state-of-the-art
algorithms.

The task of robust registration is typically done by employing randomized
strategies, where RANdom Sample Consensus (RANSAC) [4] and its variants [7, 8,
9] are often the tools of choice. RANSAC is an appealing choice due to its
simplicity, while providing relatively satisfactory results in problem
instances having low outlier ratios. However, as the number of outliers grows,
RANSAC can no longer sustain its performance, since it may require an
exponentially large number of iterations to produce acceptable results [4].
This in turn can prove to be a bottle-neck for real-time applications.

To achieve a high-quality estimate, within a reasonable amount of run-time, it
is beneficial if a fraction of outliers could be removed before executing the
core robust fitting algorithms. Along this line of research, several
approximate or exact methods have been developed for the outlier removal task,
e.g., [10, 11, 12, 13]. However, such methods require the evaluation for every
single pair in the initial putative correspondence set, where each pair
requires the execution of a costly branch-and-bound sub-problem. Note that in
large-scale applications, methods such as [11] are impractical.

The motivation behind our work comes from human vision, where the reasoning
process is guided by semantic information. For example, we would only attempt
to match key points that belong to the same semantic class (e.g., houses,
trees, cars, etc.). In recent years, semantic information for 2D images or 3D
point clouds can also be easily obtained in real-time. However, how to
effectively utilize the available semantic information to support classical
robust registration algorithms remains an interesting research question.

In this work, we propose novel techniques to partially address the above
question. Specifically, we investigate a novel combination between traditional
robust estimation techniques – in particular finding pairwise consistent
correspondences using maximum clique [5]– with semantic segmentation, which
can be extracted from any well-known semantic segmentation framework [14, 15,
16]. Maximum clique an ingredient of choice in our work, due to the fact that
it offers a convenient mechanism to exploit the available semantic information
to massively reduce the problem size. Moreover, the graph formulation
underlying maximum clique allows us, under the guidance of semantic labels, to
decompose the original problem into multiple sub-problems, each of which can
be solved efficiently. Maximum clique has been used previously for rigid
registration [17, 5], since the clique extracted is a set of pair-wise
consistent (under preservation of distance between points) correspondences,
which can be used to estimate the optimal transformation. However, existing
works focus on solving this problem on graphs larger than is actually
necessary, hence they are still impractical for large datasets. We show that
with a novel use of semantic information, one only needs to solve MC sub-
optimally and on smaller graphs.

The correspondence set generated by our method can then be processed by any
state-of-the-art robust registration algorithm, but with significantly faster
run-time since a large proportion of outliers have been effectively removed.
Experimental results show that we achieve competitive or even better
registration results, while our total run-time (semantic segmentation, outlier
removal + robust registration) is of orders of magnitude faster than existing
registration algorithms, including techniques that provide globally optimal
results [11].

It should be noted that our work differs from recent deep-learning approaches
[18, 19] for point cloud registrations, as the main work-horse behind our work
is still the well-known classical robust registration algorithm (i.e., based
on maximum clique) allowing us to achieve results that are close to globally
optimal solutions. Moreover, fully deep learned approaches usually require the
design of a new network architecture, which must be re-trained before they can
be used on any new dataset. Our method, on the other hand, only requires off-
the-shelf semantic classifiers that have been pre-trained. Moreover, our
underlying ideas are agnostic as to whether the semantic information comes
from 3D data, image data, or both.

##  2 Related Work

The task of robustly aligning two point sets has long been an active research
topic in computer vision. One of the most well-known methods is RANSAC [20],
which is based on repetitively sampling of points to generate model hypotheses
to discover the model with the largest consensus set. Variants [21] of RANSAC
seek to reduce computing time through guided sampling, and accelerating the
evaluation of a hypothesis. Although RANSAC and its variants are simple and
easy to implement, processing time, grows exponentially when dealing with the
high percentages of outliers. 4-Points Congruent Sets (4PCS) [22] and its
variant [23], have better sampling strategies. However, such methods are
sensitive to hyper-parameters, such as the approximate percentage of
overlapping points, etc.

In contrast to heuristic methods, several globally optimal algorithms [24, 25]
have been introduced. These methods are mostly based on the branch-and-bound
(BnB) technique. Unfortunately, these methods are computationally very
expensive. To overcome these limitations, efforts have been made to remove a
large number of outliers before applying global optimal algorithms (e.g. BnB).
Parra et al.[11] proposed Guaranteed Outlier Removal (GORE) to remove as many
certain outliers as possible. Although GORE helps avoid using BnB on all
elements of initial match set, it is still computationally expensive as it
calculates complex bounding functions. Other work [17, 5] sought to quickly
discover the largest set of consistent correspondences from an initial match
set. Transformation parameters may be extracted easily and quickly from that
subset by applying robust algorithms (e.g. RANSAC [20]). However, these
methods are still computationally expensive when dealing with large-scale
datasets.

##  3 Background

###  3.1 Problem Definition

Consider two input point clouds
$\mathcal{M}=\\{\mathbf{m}_{i}\in\mathbb{R}^{3}\\}_{i=1}^{M}$ and
$\mathcal{N}=\\{\mathbf{n}_{i}\in\mathbb{R}^{3}\\}_{i=1}^{N}$.(in which the
number of points in each input point set can be in the ranges of $M,N>100,000$
points). As common, we assume that a set of putative correspondences
$\mathcal{P}$, has been obtained by any off-the-shelf key point extraction
techniques [26, 27], and are given as $\mathcal{P}=\\{p_{k}\\}_{k=1}^{D}$,
where each correspondence pair
$p_{k}=(\mathbf{m}_{k},\mathbf{n}_{k^{\prime}})$, out of the set of $D$
correspondences, contains $\mathbf{m}_{k}\in\mathcal{M}$ and
$\mathbf{n}_{k^{\prime}}\in\mathcal{N}$. Our goal is to estimate the optimal
6DOF rigid body transformation (i.e. $\mathbf{R}^{*}\in SO(3)$ and
$\mathbf{t}^{*}\in\mathbb{R}^{3}$) that maximizes the following objective
function:

$(\mathbf{R}^{*},\mathbf{t}^{*})=\arg\max_{\mathbf{R},\mathbf{t}}\sum_{k=1}^{D}\mathbb{I}(\|\mathbf{R}\mathbf{m}_{k}+\mathbf{t}-\mathbf{n}_{k^{\prime}}\|\leq\epsilon),\vspace{-3mm}$
(1)

where $\|\cdot\|$ denotes the $\ell_{2}$ Euclidean norm in $\mathbb{R}^{3}$.
The indicator function $\mathbb{I}(\cdot)$ returns 1 if its predicate
$(\cdot)$ is true and 0 otherwise. The maximum consensus objective function
(1) has been used widely e.g., [11, 13]. The hyper-parameter $\epsilon$
specifies the inlier threshold, which can be chosen based on prior knowledge
about the problem.

Due to the noisy characteristic of input sensors and the imperfection of
existing feature extraction techniques, $\mathcal{P}$ may contain a large
fraction of outliers (the KITTI dataset can contain up to $\rho=90\%$ of
outliers - please refer to the supplementary material). In order to estimate
$\mathbf{R}^{*}$ and $\mathbf{t}^{*}$, a subset $|\mathcal{I}^{*}|$ containing
$(1-\rho)D$ inliers must be identified, and vice versa (i.e., if the optimal
transformation $(\mathbf{R}^{*},\mathbf{t}^{*})$ is given, $\mathcal{I}^{*}$
can easily be obtained). In this work, we introduce a novel approach to
effectively remove outliers in $\mathcal{P}$ to obtain a subset
$\mathcal{P}^{\prime}\subset\mathcal{P}$, where the outlier ratio
$\rho^{\prime}$ of $\mathcal{P}^{\prime}$ is much lower than that of the
original set $\mathcal{P}$. Given $\mathcal{P}^{\prime}$, the optimal
transformation between the two point clouds can then be obtained by, e.g.,
running RANSAC.

In fact, our outlier removal approach is motivated by a class of registration
methods that attempt to solve point cloud alignment without putative
correspondences [5, 17], which uses pairwise length constraints to obtain the
optimal set of correspondences by searching for the maximum clique. However,
in practice, using all the points as input to such algorithms renders them
impractical hence we still use keypoints.

In the next section, we briefly introduce the Maximum Clique algorithm, which
serves as a backbone for our algorithm.

###  3.2 Maximum Clique (for preserved distance between point pairs)
Formulation

As previously discussed, when the set $\mathcal{I}^{*}$, containing the
highest number of inliers (set with maximum consensus) is achieved, the
optimal transformation $(\mathbf{R}^{*},\mathbf{t}^{*})$ can be obtained
using, e.g., SVD [28] or RANSAC[20]. Following [5, 17], outliers for such an
optimal subset can be removed by solving the maximum set of consistent pairs.
Specifically, we first define an undirected graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, where each vertex
$v_{k}\in\mathcal{V}$ corresponds to a pair of correspondences $p_{k}$ between
the two point clouds, i.e., $\mathcal{V}=\mathcal{P}$. The set of edges
$\mathcal{E}$ of $\mathcal{G}$ is defined as

$\mathcal{E}=\\{(p_{i},p_{j})\in\mathcal{P}\times\mathcal{P}\,|\,\,d(p_{i},p_{j})\leq
2\epsilon\\}\vspace{-2mm}$ (2)

where the function $d(p_{i},p_{j})$ specifies the distance between the two
correspondence pairs, $p_{i}=(\mathbf{m}_{i},\mathbf{n}_{i^{\prime}})$ and
$p_{j}=(\mathbf{m}_{j},\mathbf{n}_{j^{\prime}})$, which can be expressed as

$d(p_{i},p_{j})=|\|\mathbf{m}_{i}-\mathbf{m}_{j}\|-\|\mathbf{n}_{i^{\prime}}-\mathbf{n}_{j^{\prime}}\||,\vspace{-2mm}$
(3)

and $\epsilon$ is the user-defined inlier threshold. To assist further
discussion in later sections, we also define a clique
$\mathcal{C}=(\mathcal{V}^{\prime},\mathcal{E}^{\prime}),\mathcal{V}^{\prime}\subseteq\mathcal{V},\mathcal{E}^{\prime}\subseteq\mathcal{E}$
to be a sub-graph of $\mathcal{G}$ in which there exists a connection between
any two vertices. i.e.,

$\mathcal{E}^{\prime}=\\{(v_{i},v_{j})\in\mathcal{V}|\,(v_{i},v_{j})\in\mathcal{E},\,\forall
i,j\\}.\vspace{-2mm}$ (4)

For brevity, we define clique size $|\mathcal{C}|$ to be the number of
vertices in $\mathcal{C}$. A maximum clique $\mathcal{C}^{*}$ of $\mathcal{G}$
is the clique with the maximum number of vertices. For a vertex
$v_{i}\in\mathcal{V}$, let $\Gamma(v_{i})$ be a set that all elements are
adjacent to $v_{i}$, i.e., $\Gamma(v_{i})=\\{v_{j}\in
V\,|\,(v_{i},v_{j})\in\mathcal{E}\\}$. We call $|\Gamma(v_{i})|$ as the degree
of vertex $v_{i}$.

From (3), a pair of correspondences $p_{i}$ and $p_{j}$ are said to be
_consistent_ if $d(p_{i},p_{j})\leq 2\epsilon$. The graph $\mathcal{G}$
defined above is therefore referred to as _consistency graph_. Intuitively, if
$p_{i}$ and $p_{j}$ both belong to the optimal inlier set $\mathcal{I}^{*}$,
it is expected that the difference in lengths between the two segments
$\overline{\mathbf{m}_{i}\mathbf{m}_{j}}$ and
$\overline{\mathbf{n}_{i^{\prime}}\mathbf{n}_{j^{\prime}}}$ must not exceed
$2\epsilon$ (in noise-free settings, $\epsilon=0$).

The task of removing (not necessarily all) outliers in $\mathcal{P}$ can be
addressed by solving for the optimal set $\mathcal{I}^{*}$ that contains the
maximum number of consistent correspondence pairs. Since every pair of inliers
$i,j\in\mathcal{P}$ must satisfy $d(p_{i},p_{j})\leq 2\epsilon$, we can remove
outliers by solving

$\max_{\mathcal{I}\subseteq\\{1,...,D\\}}|\mathcal{I}|\;\;\text{s.t.}\,\,\,\,d(p_{i},p_{j})\leq
2\epsilon,\forall i,j\in\mathcal{I}.\\\ \vspace{-2mm}$ (5)

Together with the introduction of the consistency graph $\mathcal{G}$ as
discussed above, maximizing Eq. (5) is equivalent to searching for the maximum
clique on $\mathcal{G}$, which will be discussed in the following section.
Interested readers are referred to [5] and supplementary material for more
details.

###  3.3 Solving Maximum Clique

Removing outliers by finding the maximum clique in the consistency graph Eq.
(5) is still computationally challenging as maximum clique is a well-known NP-
hard problem. The majority of optimal algorithms are based on BnB For
instance, Parra et al. [5] introduced an efficient algorithm by deriving an
efficient bounding function. However, such algorithms can only handle input
data with modest sizes, while large-scale datasets are still considered
impractical. To assist in the introduction of our algorithm and for the sake
of completeness, in this section, we quickly summarize the general BnB
approach to tackle Eq. (5). Our novel modification will be introduced in
Section 4.

A general strategy for solving maximum clique using BnB is traversing the
input graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ in a depth-first-search
manner. At the beginning of the algorithm, all the vertices in $\mathcal{V}$
are pushed into a set $\mathcal{S}$, i.e., $\mathcal{S}=\mathcal{V}$. A node
$v_{i}\in\mathcal{S}$ is selected and its adjacent nodes are extracted into a
set $\mathcal{S}^{\prime}$ for further exploration. During the traversal, the
optimal clique size $R^{*}$ obtained so far is recorded. When a node $v_{i}$
is considered for expansion, a bounding function $\text{UB}(v_{i})$ is
computed, which provides the upper-bound for the maximum clique containing
$v_{i}$. The computation of UB usually involves solving for $c(v_{i})$, which
is an approximate version of graph-coloring. The upper bound is then computed
as $\text{UB}(v_{i})=c(v_{i})+l(v_{i})$, where $l(v_{i})$ is the current level
of $v_{i}$ with respect to the current search tree. If
$\text{UB}(v_{i})>R^{*}$, the search recursively continues from $v_{i}$ to
deeper levels. Otherwise, the exploration for $v_{i}$ is terminated, $v_{i}$
is removed from $\mathcal{S}^{\prime}$, and the process continues from other
nodes in the queue $\mathcal{S}^{\prime}$ until
$\mathcal{S}^{\prime}=\emptyset$. The search is then back-tracked to
investigate the remaining nodes in $\mathcal{S}$. More details about BnB
algorithm for maximum clique can be found in [5]. It is well-known that BnB
has exponential complexity [29], thus real-time applications rarely employ
such techniques, unless the problem size is relatively small.

While BnB is a standard framework, deriving a tight bounding function
$\tilde{R}(v)$ is crucial in determining the execution time. Most of the
existing research relies on approximate graph-coloring to obtain the lower
bound. In addition, other techniques such as ranking the nodes by their
degrees, or [5] can also be used to speed up the algorithms. However, to the
best of our knowledge, most algorithms are still slow for large-scale
problems, especially when the graph $\mathcal{G}$ is dense.

##  4 Proposed Method

Figure 1: Overall block diagram of the proposed approach.

A schemetic of our proposed approach is depicted in Fig 1 while the following
sections show how integrating semantic information on approximating the
maximum clique problem addresses the challenges discussed above. In
particular, we first discuss the correspondence pruning using semantic labels.
Next, using the provided semantic information containing $L$ different
classes, we propose to decompose the graph into $L$ sub-graphs, and solve
maximum clique for each of the sub-graphs. The solutions from the sub-problems
are then combined in an hierarchical manner. Notably, we also demonstrate a
novel use of information obtained from the solved sub-graphs to accelerate the
computation of lower-bounding functions during optimizing the remaining sub-
graphs. This technique allows us to achieve real-time performance on very
large datasets containing an extremely high proportion of outliers.

###  4.1 Correspondence Pruning with Semantic Labels

We use semantic labels to prune the set of input putative correspondences
$\mathcal{P}$. Specifically, for each 3D point $\mathbf{m}\in\mathbb{R}^{3}$,
let $l(\mathbf{m})\in\\{1,\dots,L\\}$ denote the semantic label (of the $L$
semantic classes) assigned to $\mathbf{m}$. Based on such a labelling, we
prune $\mathcal{P}$ by removing correspondences
$p_{k}=(\mathbf{m}_{k},\mathbf{n}_{k^{\prime}})$ where $l(\mathbf{m}_{k})\neq
l(\mathbf{n}_{k^{\prime}})$. Formally, after pruning, we obtain a new set
$\mathcal{S}\subseteq\mathcal{P}$:

$\mathcal{S}=\\{(\mathbf{m}_{k},\mathbf{n}_{k^{\prime}})\in\mathcal{P}\,|\,\,l(\mathbf{m}_{k})=l(\mathbf{n}_{k^{\prime}})\\}.\vspace{-2mm}$
(6)

After this pruning procedure, due to the inevitable errors caused by the
underlying semantic classifiers, two problems may arise:

  * •

True inliers may be incorrectly removed, and

  * •

The set $\mathcal{S}$ can still contain a large fraction of outliers.

For the former problem, our empirical experiments (please refer to the
supplementary material) show that our method incorrectly removes an
insignificant fraction of correspondences in $\mathcal{I}^{*}$. Moreover, this
does not cause a significant impact on the final estimated transformation
compared to ground-truth (See Section 5, for performance results).

The latter problem, on the other hand, is still challenging. One would expect
that after pruning $|\mathcal{P}|$, since $|\mathcal{S}|<|\mathcal{P}|$,
applying any state-of-the-art robust fitting algorithm to $\mathcal{S}$ would
be trivial than the original problem of applying it to $\mathcal{P}$. However,
merely pruning the dataset based on semantic class matching still leaves a
large number of outliers (please refer to the supplementary material).

In the following section, we show how semantic information can further be
utilized to devise a fast algorithm, which can precisely remove outliers in
$\mathcal{S}$.

###  4.2 Hierarchical Maximum Clique

Approximating the maximum clique up to a constant factor has been shown to be
NP-complete [30], unless P=NP. Therefore, most of the research involving
maximum clique resort to heuristic mechanisms and approximate maximum clique.
Inspired by recent works on maximum clique for very large graphs [31, 32, 33],
where graph decomposition plays a major role, we propose a hierarchical
maximum clique algorithm for outlier removal.

Our heuristic algorithm stems from the special structure of rigid-body point
cloud registration. Recall that, in order to roughly estimate the rotation and
translation from the two given point clouds, only a subset of inliers are
sufficient. The rest of the inliers can be obtained after applying the
estimated $\mathbf{R}$ and $\mathbf{t}$. Therefore, it is adequate for an
algorithm to approximate the set of inliers. In addition, in the context of
point cloud registration, it is expected that matching points should belong to
the same semantic class. Therefore, we propose to approximate this set of
inliers by first using semantic information to decompose the original graph,
then combine the solutions in a hierarchical manner. The algorithms are
discussed in detail as follow.

Figure 2: Illustrations of Semantic Graph Decomposition. We have three
semantic classes with three different vertex colors (red, yellow and green).
(a) The original graph with semantic information after correspondence pruning
with semantic labels. (b) Maximum cliques of sub-graphs. (c) The combined
maximum cliques of sub-graphs. (d) Final maximum clique.

####  4.2.1 Semantic Graph Decomposition

After executing the semantic pruning procedure (Section 4.1) to obtain the set
$\mathcal{S}$, let us consider the graph
$\mathcal{G}_{S}=(\mathcal{V}_{S},\mathcal{E}_{S})$ built from $\mathcal{S}$
based on the technique discussed in Section 3.2. Since the labels assigned to
points in each correspondence
$p_{k}=(\mathbf{m}_{k},\mathbf{n}_{k^{\prime}})\in\mathcal{S}$ are identical,
with the abuse of notation, we also use $l(p_{k})$ to denote the label
associated with points belonging to $p_{k}$, i.e.,
$l(p_{k})=l(\mathbf{m}_{k})=l(\mathbf{n}_{k^{\prime}})$. Also, for a graph
vertex $v_{k}\in\mathcal{V}_{S}$, we denote by $l(v_{k})$ the label of the
associated correspondence $p_{k}$.

Now, define $L$ sub-graphs
$\\{\mathcal{G}_{i}=(\mathcal{V}_{i},\mathcal{E}_{i})\\}_{i=1}^{L}$ extracted
from $\mathcal{G}_{S}$, where $\mathcal{V}_{i}$ comprises correspondences
having label $i$, i.e.,
$\mathcal{V}_{i}=\\{v_{k}\in\mathcal{V}_{S}\,|\,\,l(v_{k})=i\\}$, and
$\mathcal{E}_{i}=\\{(p_{p},p_{q})\in\mathcal{E}_{S}\,|\,\,l(p_{p})=l(p_{q})\\}$.
Note that by decomposing the original graph $\mathcal{G}_{S}$ into $L$ sub-
graphs, the total number of vertices remains the same, while some edges that
connect vertices having different labels are temporarily removed. Therefore,
the number of edges in each sub-graph can be massively reduced compared to the
original graph, i.e., $|\mathcal{E}_{i}|\ll|\mathcal{E}_{S}|\;,\forall
i=1,\dots\,L$, allowing us to solve maximum clique efficiently on each
$\mathcal{G}_{i}$ (see Fig. 2 for an illustration of graph decomposition).
Moreover, note that based on the sub-graph definitions, in order to obtain the
sub-graphs, instead of constructing the original graph $\mathcal{G}_{S}$ and
perform the decomposition, it is sufficient to just construct
$\mathcal{G}_{i}$ based on a subset of vertices having label $i$.

After decomposing the original graph into $L$ sub-graphs, it is natural to
execute the maximum clique algorithm on the sub-graphs. For each sub-graph
$\mathcal{G}_{i}$, we denote by $\mathcal{I}^{*}(\mathcal{G}_{i})$ the optimal
inliers after solving maximum clique for graph $\mathcal{G}_{i}$. Certainly,
if $\mathcal{I}^{*}(\mathcal{G})$ denotes the optimal inliers of the original
graph $\mathcal{G}$, it can be seen that
$\bigcup_{i=1}^{L}\mathcal{I}^{*}(\mathcal{G}_{i})\neq\mathcal{I}^{*}(\mathcal{G})$.
In other words, combining the inlier sets obtained after solving each sub-
problem does not guarantee to recover the optimal solution for the original
problem. However, our empirical experiments show that combining the solutions
$\bigcup_{i=1}^{L}\mathcal{I}^{*}(\mathcal{G}_{i})$ in most cases is
sufficient to recover the optimal transformation.

####  4.2.2 Combining sub-optimal solutions

After solving the sub-problems to obtain the set
$\mathcal{J}=\bigcup_{i=1}^{L}\mathcal{I}^{*}(\mathcal{G}_{i})$, $\mathcal{J}$
may still contain outliers. One of the possible reasons is the presence of
moving objects. For instance, the same car can be located at two different
positions in the two input point clouds. In this scenario, points belong to
such car become “outliers” w.r.t. the remaining points. Moreover, the noisy
set of putative correspondences may contain correspondences that are not
meaningful to the underlying point cloud structure, but may still form a
maximum clique. Therefore, to remove the remaining outliers in $\mathcal{J}$,
the final stage in our algorithm is to solve for maximum clique on the set
$\mathcal{J}$.

###  4.3 Faster Tree-Pruning with Tight Initial Lower Bound

Recall that, in classical maximum clique solvers, when each vertex $v_{i}$ is
visited, a bounding function $\text{UB}(v_{i})$ is computed (see Section 3.3),
which determines if the vertex $v_{i}$ should be expanded. For our particular
problem, we show that while solving for $\mathcal{I}^{*}(\mathcal{G}_{i})$, an
initial lower bound $\text{LB}(\mathcal{G}_{i})$ can be used in combination
with $\tilde{R}(v_{i})$ to effectively prune the search tree.

We make use of the decomposed structure in our problem and utilize the
solutions obtained from $\bigcup_{i=1}^{k}\mathcal{I}^{*}(\mathcal{G}_{i})$
(where $k$ is the number of classes out of $L$ classes processed so far) to
compute during the process of solving for $\mathcal{I}^{*}(\mathcal{G}_{i})$.
Our new strategy is motivated by the fact that in order to obtain an
acceptable transformation, only a small subset of correspondences
$\hat{\mathcal{I}}\subset\mathcal{I}^{*}$, where $|\hat{\mathcal{I}}|\geq 3$
is required. Therefore, after obtaining the set
$\bigcup_{i=1}^{k}\mathcal{I}^{*}(\mathcal{G}_{i})$, we aim to seek
$(R_{i-1},t_{i-1})$ from this subset using RANSAC. Because the fraction of
outliers in $\bigcup_{i=1}^{k}\mathcal{I}^{*}(\mathcal{G}_{i})$ is relatively
low and $|\bigcup_{i=1}^{k}\mathcal{I}^{*}(\mathcal{G}_{i})|$ is small, the
run-time required by RANSAC, in most of the cases, is very fast. Then, based
on $(R_{i-1},t_{i-1})$, we compute approximate number of inliers $|I_{i}|$ and
use it as initial lower bound for solving $\mathcal{I}^{*}(\mathcal{G}_{i})$:

$\text{LB}(\mathcal{G}_{i})=|I_{i}|\leq|\mathcal{I}^{*}(\mathcal{G}_{i})|\vspace{-2mm}$
(7)

At any given node $v$, it is expected that
$\text{LB}(\mathcal{G}_{i})\leq\mathcal{I}^{*}(\mathcal{G}_{i})\leq\text{UB}(v)$.
Consequently, at a particular node $v$, if
$\text{UB}(v)<\text{LB}(\mathcal{G}_{i})$, it can be concluded that the node
$v$ can be pruned.

$|I_{i}|$ may become a tight initial lower bound because, firstly, the maximum
clique may have some, but not many outliers. As a result, $|I_{i}|$ is quite
close to $|\mathcal{I}^{*}(\mathcal{G}_{i})|$. Secondly, the run-time to
calculate $|I_{i}|$ is significantly fast.

Algorithm 1 Fast Semantic-Assisted Outlier Removal.

1:A set of putative correspondences $\mathcal{P}$

2:Prune $\mathcal{P}$ to obtain semantic consistent set
$\mathcal{S}=\\{p_{k}=(\mathbf{m}_{k},\mathbf{n}_{k^{\prime}})\in\mathcal{P}|l(\mathbf{m}_{k})=l(\mathbf{n}_{k^{\prime}})\\}$.

3:Build L sub-graphs
$\\{\mathcal{G}_{i}=(\mathcal{V}_{i},\mathcal{E}_{i})\\}_{i=1}^{L}$

4:for $i=1,...,L$ do

5: if ($i>1$) then

6: $\text{LB}(\mathcal{G}_{i})\leftarrow|I_{i}|$

7: end if

8: Calculate $\mathcal{I}^{*}(\mathcal{G}_{i})$ using PMC with
$\text{LB}(\mathcal{G}_{i})$.

9: if ($|\bigcup_{1}^{i}\mathcal{I}^{*}(\mathcal{G}_{i})|>3$) then

10: Estimate ($\mathbf{R}^{*}_{i}$, $\mathbf{t}^{*}_{i}$) using RANSAC on
$\bigcup_{1}^{i}\mathcal{I}^{*}(\mathcal{G}_{i})$.

11: end if

12: Calculate initial lower bound for next class $I_{i+1}$

13:end for

14:Combine sub-optimal solutions from L sub-graphs
$\mathcal{J}=\bigcup_{i=1}^{L}\mathcal{I}^{*}(\mathcal{G}_{i})$

15:Run PMC again on $\mathcal{J}$ to get $\mathcal{I}^{*}(\mathcal{J})$

16:Estimate ($\mathbf{R}^{*}$, $\mathbf{t}^{*}$) using robust registration
algorithm (e.g. RANSAC) on $\mathcal{I}^{*}(\mathcal{J})$.

##  5 Experiments

In this section, we test our proposed method on both synthetic and real-world
dataset. All experiments are executed on Intel Core 3.70GHz i7 CPU with 32Gb
RAM, and Geforce GTX 1080Ti GPU.

Benchmark Dataset. We evaluate the performance of our proposed method using
KITTI odometry dataset [34]. This dataset contains point clouds captured from
a moving car, equipped with a Velodyne HDL64 LiDAR, around the city of
Karlsruhe, Germany. The original point clouds contains around 120,000 points.
Since the ground truth error in the original KITTI odometry dataset is large,
we utilize the ground truth poses from Semantic KITTI [35] instead.

Baseline Algorithms. To show the significant performance of our method, we
compare it against the following state-of-the-art pipelines or approaches on
the same dataset:

  * •

GORE [11]: Guaranteed Outlier Removal for point cloud registration. The code
was provided by the authors.

  * •

Practical Maximum Clique with Pairwise Constraints (PMC) [5]. The code was
provided by the authors.

  * •

Keypoint-based 4PCS (K4PCS)[23]: A variant of 4PCS, which is applied on key
points.

We down-sample the input point clouds using a voxel size of 0.1m. We then
apply Intrinsic Shape Signature (ISS)[26] to detect keypoints and Fast Point
Feature Histogram (FPFH)[36] to compute local geometric features of each
point. Finally, we generate initial correspondences based on these features
using K nearest neighbors (K = 10) while setting the inlier threshold to 0.1.

Evaluation Criteria The evaluation is based on calculating the angular and
translational error of the estimated transformation ($R,T$) against the ground
truth ($\overline{R},\overline{T}$). The angular error is calculated as
$angErr=2\arcsin{\frac{\|R-\overline{R}\|}{2\sqrt{2}}}$. The translational
error is calculated by the Euclidean distance between $T$ and $\overline{T}$.

###  5.1 Results on the Semi-synthetic Data

We first show the performance of our method on semi-synthetically generated
data. The point cloud “000001.bin” from sequence 00 of KITTI dataset is loaded
and considered as source point cloud $M$. In this experiment, we use ground-
truth semantic information. Motivated by [37], to produce target point cloud
$N$, we apply a random 6DOF transformation and a small Gaussian noise (with
zero mean and variance of 0.01) to $N$. We randomly select and remove $k$%
points in $N$ to simulate overlapping rate. We conduct the experiments with k
= 10%, 15%,…, 50%.

Fig. 3 shows the median values (angular error, translation error, optimization
run-time, and total run-time) in 100 runs for all methods. In this stage, as
we use the ground-truth for semantic information, the total time does not
include the run-time for semantic predictions. (The semantic prediction run-
time is reported in section 5.2). As shown in the Fig. 3, it is evident that
our algorithm outperforms the above methods in term of run-time with better
(or comparable) errors to the others. The performance of K4PCS is unstable
because it is sensitive to input parameters such as approximate overlapping,
etc.

Figure 3: Performance of the proposed method on semi-synthetic data in
comparison to other methods. Table 1: Number of putative correspondences
before and after semantic pruning step, and the number of inliers.

Overlapping rate (%) | 50 |  55 |  60 | 65 |  70 |  75 | 80 |  85 |  90
---|---|---|---|---|---|---|---|---|---
Putative Correspondences (Before semantic pruning) | 2384 |  2899 |  3393 | 4023 |  4728 |  5162 | 5800 |  6402 |  7041
Putative Correspondences (After semantic pruning) | 809 |  1054 |  1274 | 1735 |  2087 |  2427 | 2771 |  3416 |  4027
Number of inliers | 39 |  46 |  73 | 109 |  164 |  193 | 287 |  362 |  495

To evaluate the robustness of our method, we add noise to the semantic labels
in the target point cloud. In particular, we randomly select and change $h$%
point labels. We conduct the experiments with h = 10%, 20%,…, 90%. Table 2
shows the median values (angular error, translation error, and optimization
run-time) in 100 runs for our method. As shown in the table, our method is
robust to noise in semantic label. We report the results with the noise rate
up to 70%. Our method fails when the noise rate is over 80%. However, most of
the recent deep learning networks [14, 15, 16] for point cloud semantic
segmentation can achieve over 70% average accuracy. As a result, our pipeline
is flexible such that practitioners can use any deep learning network suited
to their application.

Table 2: Accuracy and run-time of our pipeline when adding noise to semantic
segmentation.

| Noise rate (% | 10 | 20 | 30 | 40 | 50 | 60 | 70
---|---|---|---|---|---|---|---|---
HSMC + RANSAC | AngErr (deg) |  0.007 |  0.011 |  0.013 |  0.036 |  0.124 |  0.279 |  0.166
| TrErr (m) | 0.015 |  0.013 |  0.026 | 0.018 |  0.037 |  0.037 | 0.017
| Run-time (s) | 0.149 |  0.046 |  0.025 | 0.011 |  0.007 |  0.005 | 0.005

###  5.2 Results on the Real Data

To demonstrate the practicality of our method, we evaluate the performance on
the KITTI odometry benchmark. Based on the benchmark, we use 11 sequences
(from 11 to 21) for testing. Motivated by DeepVCP [18] experiment setting, we
sample the input source from every 150 frame intervals and register with all
target scans within 4m translation. To extract semantic information, we
utilize predictions from a state-of-the-art deep learning model RangeNet53++
[16]. The mean Intersection over Union (mIoU) and average accuracy obtained
are 0.52 and 0.89 respectively.

Figure 4: Performance of the proposed method on the KITTI dataset in
comparison to other methods.

Fig. 4 reports the angular error, translation error, optimization run-time and
total run-time of all methods. Note: there are few cases where some methods
have failed, which has impacted on the mean values. To be fair, we report
median values which are less influenced, as well as mean (that is, median,
mean, standard deviation) in Table 5.2 and show the comparison between median
values of all methods in Fig. 4. The total run-time includes the run-time for
extracting key points, generating initial correspondences, semantic
information prediction (for only our methods), and optimization run-time. Note
that the run-time for semantic prediction was taken from the original paper
RangeNet53++ [16]. As shown in Fig. 4, our methods achieve better (or
comparable) accuracy with extremely faster run-time than others. Compared to
PMC, the optimization run-time of HSMC is significantly faster (up to 99
times). In particular, our pipeline is flexible, practitioners can replace PMC
with any maximum clique solver, and RangeNet53++ with any state-of-the-art
deep learning model.

Table 3: Comparison on KITTI dataset. Our method performance achieve
comparable accuracy with much faster run-time.

|  | GORE | K4PCS | PMC + RANSAC | HSMC + RANSAC |  |  |  |  |
---|---|---|---|---|---|---|---|---|---|---
|  |  |  |  | (Ours) |  |  |  |  |
|  | Median | Mean | Std | Median | Mean | Std | Median | Mean | Std | Median | Mean | Std |  |  |  |  |
Seq.11 | angErr (deg) | 0.15 |  0.17 |  0.13 | 0.40 |  6.64 |  32.59 | 0.14 | 0.17 |  0.14 |  0.16 | 0.21 |  0.17 |  |  |  |  |
58 pairs | trErr (m) | 0.03 |  0.09 |  0.39 | 3.79 |  6.38 |  7.09 | 0.34 | 0.49 |  0.54 |  0.04 | 0.04 |  0.02 |  |  |  |  |
| run-time (s) | 36.52 |  42.69 |  27.99 | 8.57 |  11.98 |  10.10 | 3.21 | 4.10 |  3.49 |  0.12 | 0.15 |  0.11 |  |  |  |  |
| total time (s) | 38.83 |  45.11 |  27.93 | 10.93 |  14.39 |  10.09 | 5.63 | 6.51 |  3.43 |  2.83 | 2.74 |  0.28 |  |  |  |  |
1-1[1pt/1pt]  Seq. 12 |  angErr (deg) |  0.05 | 0.12 | 0.15 |  0.05 |  0.18 | 0.23 |  0.03 |  0.08 | 0.12 | 0.03 |  0.33 |  1.48
46 pairs | trErr (m) | 0.02 |  0.59 |  1.16 | 3.78 |  4.57 |  2.50 | 0.71 | 1.34 |  1.51 |  0.01 | 0.51 |  1.07 |  |  |  |  |
| run-time (s) | 121.55 |  116.45 |  51.82 | 37.72 |  37 |  12.99 | 43.63 | 48.52 |  36.16 |  1.71 | 1.64 |  0.73 |  |  |  |  |
| total time (s) | 123.99 |  119.27 |  51.39 | 40.25 |  39.82 |  12.54 | 46.17 | 51.34 |  35.82 |  4.52 | 4.64 |  0.53 |  |  |  |  |
Seq. 13 | angErr (deg) | 0.18 |  0.23 |  0.20 | 0.32 |  1.27 |  12.16 | 0.18 | 0.26 |  0.23 |  0.20 | 0.28 |  0.28 |  |  |  |  |
209 pairs | trErr (m) | 0.03 |  0.06 |  0.27 | 4.99 |  6.16 |  4.59 | 0.35 | 0.55 |  0.57 |  0.03 | 0.04 |  0.04 |  |  |  |  |
| run-time (s) | 33.21 |  41.80 |  30.51 | 10.92 |  11.32 |  5.46 | 3.88 | 29.19 |  150.77 |  0.13 | 0.31 |  0.73 |  |  |  |  |
| total time (s) | 35.25 |  44.00 |  30.76 | 13.07 |  13.53 |  5.72 | 6.16 | 31.40 |  150.88 |  2.50 | 2.69 |  0.94 |  |  |  |  |
Seq. 14 | angErr (deg) | 0.16 |  0.18 |  0.11 | 0.36 |  9.54 |  37.21 | 0.16 | 0.21 |  0.18 |  0.18 | 0.34 |  0.57 |  |  |  |  |
67 pairs | trErr (m) | 0.05 |  0.11 |  0.41 | 4.30 |  6.10 |  4.05 | 0.12 | 0.17 |  0.14 |  0.05 | 0.07 |  0.07 |  |  |  |  |
| run-time (s) | 56.80 |  58.58 |  23.05 | 25.53 |  27.36 |  11.31 | 24.49 | 24.83 |  7.97 |  2.82 | 2.78 |  1.00 |  |  |  |  |
| total time (s) | 59.60 |  61.89 |  23.21 | 29.11 |  30.67 |  11.47 | 27.73 | 28.14 |  8.12 |  6.11 | 6.27 |  1.27 |  |  |  |  |
Seq. 15 | angErr (deg) | 0.16 |  0.20 |  0.14 | 0.44 |  4.48 |  25.76 | 0.16 | 0.20 |  0.14 |  0.21 | 0.29 |  0.22 |  |  |  |  |
137 pairs | trErr (m) | 0.04 |  0.11 |  0.43 | 5.13 |  6.23 |  5.05 | 0.32 | 0.47 |  0.45 |  0.03 | 0.04 |  0.03 |  |  |  |  |
| run-time (s) | 33.08 |  38.25 |  22.40 | 8.09 |  10.06 |  5.80 | 3.45 | 6.80 |  7.46 |  0.09 | 0.11 |  0.05 |  |  |  |  |
| total time (s) | 36.09 |  41.04 |  22.37 | 10.88 |  12.85 |  5.81 | 6.50 | 9.60 |  7.46 |  3.01 | 3.08 |  0.31 |  |  |  |  |
Seq. 16 | angErr (deg) | 0.17 |  0.20 |  0.10 | 0.31 |  0.35 |  0.25 | 0.17 | 0.21 |  0.14 |  0.19 | 0.24 |  0.18 |  |  |  |  |
116 pairs | trErr (m) | 0.03 |  0.03 |  0.02 | 5.14 |  6.54 |  4.53 | 0.20 | 0.36 |  0.46 |  0.03 | 0.03 |  0.02 |  |  |  |  |
| run-time (s) | 62.27 |  68.62 |  36.78 | 17.84 |  18.29 |  7.36 | 15.46 | 19.46 |  18.80 |  0.18 | 0.18 |  0.06 |  |  |  |  |
| total time (s) | 64.90 |  71.21 |  36.74 | 20.50 |  20.88 |  7.31 | 18.05 | 22.05 |  18.76 |  2.95 | 2.95 |  0.16 |  |  |  |  |
Seq. 17 | angErr (deg) | 0.10 |  0.11 |  0.04 | 0.28 |  0.68 |  1.3 | 0.11 | 0.12 |  0.06 |  0.14 | 0.17 |  0.10 |  |  |  |  |
14 pairs | trErr (m) | 0.08 |  1.04 |  1.35 | 9.86 |  9.05 |  4.73 | 1.18 | 1.69 |  1.64 |  0.07 | 1.04 |  1.34 |  |  |  |  |
| run-time (s) | 57.34 |  59.36 |  17.45 | 41.94 |  40.68 |  8.13 | 35.61 | 32.44 |  7.16 |  1.72 | 2.15 |  1.06 |  |  |  |  |
| total time (s) | 59.34 |  61.57 |  17.60 | 43.94 |  42.89 |  7.76 | 37.37 | 34.65 |  6.66 |  4.10 | 4.54 |  1.16 |  |  |  |  |
Seq.18 | angErr (deg) | 0.31 |  0.42 |  0.33 | 0.50 |  2.13 |  15.75 | 0.30 | 0.45 |  0.37 |  0.37 | 0.52 |  0.39 |  |  |  |  |
121 pairs | trErr (m) | 0.04 |  0.04 |  0.02 | 5.94 |  6.66 |  4.22 | 1.17 | 1.57 |  1.52 |  0.04 | 0.05 |  0.04 |  |  |  |  |
| run-time (s) | 24.98 |  32.82 |  24.37 | 5.62 |  7.65 |  4.97 | 2.54 | 26.28 |  169.89 |  0.10 | 0.49 |  1.50 |  |  |  |  |
| total time (s) | 26.62 |  34.63 |  24.49 | 7.42 |  9.46 |  5.23 | 4.41 | 28.10 |  169.93 |  2.12 | 2.48 |  1.61 |  |  |  |  |
Seq. 19 | angErr (deg) | 0.15 |  0.18 |  0.12 | 0.32 |  2.01 |  16.67 | 0.15 | 0.20 |  0.19 |  0.18 | 0.24 |  0.22 |  |  |  |  |
340 pairs | trErr (m) | 0.03 |  0.03 |  0.02 | 5.78 |  6.58 |  4.50 | 0.96 | 1.51 |  2.41 |  0.03 | 0.03 |  0.02 |  |  |  |  |
| run-time (s) | 55.39 |  61.21 |  36.90 | 14.20 |  16.41 |  9.14 | 12.02 | 23.19 |  48.57 |  0.19 | 0.32 |  0.83 |  |  |  |  |
| total time (s) | 58.00 |  63.64 |  36.97 | 16.88 |  18.83 |  9.19 | 14.62 | 25.61 |  48.56 |  2.88 | 2.92 |  0.91 |  |  |  |  |
Seq. 20 | angErr (deg) | 0.09 |  0.11 |  0.08 | 0.18 |  0.24 |  0.29 | 0.08 | 0.12 |  0.17 |  0.09 | 0.16 |  0.19 |  |  |  |  |
63 pairs | trErr (m) | 0.08 |  0.16 |  0.20 | 3.32 |  3.54 |  2.66 | 0.21 | 0.53 |  0.67 |  0.08 | 0.15 |  0.20 |  |  |  |  |
| run-time (s) | 32.95 |  40.28 |  23.27 | 20.55 |  19.77 |  7.09 | 10.18 | 11.52 |  6.38 |  0.61 | 0.80 |  0.46 |  |  |  |  |
| total time (s) | 36.11 |  43.16 |  23.31 | 23.27 |  22.66 |  7.14 | 12.90 | 14.41 |  6.38 |  3.99 | 3.86 |  0.39 |  |  |  |  |
Seq. 21 | angErr (deg) | 0.11 |  0.13 |  0.09 | 0.24 |  0.30 |  0.21 | 0.10 | 0.14 |  0.11 |  0.13 | 0.19 |  0.20 |  |  |  |  |
40 pairs | trErr (m) | 0.11 |  0.54 |  0.85 | 3.92 |  4.48 |  3.16 | 2.36 | 4.25 |  4.80 |  0.10 | 0.39 |  0.72 |  |  |  |  |
| run-time (s) | 60.96 |  64.85 |  26.24 | 25.21 |  29.06 |  10.02 | 17.69 | 19.38 |  5.38 |  1.50 | 1.53 |  0.64 |  |  |  |  |
| total time (s) | 63.46 |  67.71 |  26.17 | 28.04 |  31.93 |  10.07 | 20.35 | 22.24 |  5.39 |  4.48 | 4.57 |  0.78 |  |  |  |  |

(a) Initial match set

(b) Maximum clique

(c) Alignment

Figure 5: Examples visualization of our results.

##  6 Conclusion

We have demonstrated that one can employ semantic constraints, in addition to
pairwise conserved distance constraints, to reduce the number of putative
matches (remove outliers in those) sufficiently well to make a post-processing
step (by RANSAC or other standard technique) computationally attractive even
on large data sets.

## References

  * [1] Chua, C.S., Jarvis, R.:  Point signatures: A new representation for 3d object recognition.  International Journal of Computer Vision 25(1) (1997) 63–85
  * [2] Newcombe, R.A., Izadi, S., Hilliges, O., Molyneaux, D., Kim, D., Davison, A.J., Kohi, P., Shotton, J., Hodges, S., Fitzgibbon, A.:  Kinectfusion: Real-time dense surface mapping and tracking.  In: 2011 10th IEEE International Symposium on Mixed and Augmented Reality, IEEE (2011) 127–136
  * [3] Elbaz, G., Avraham, T., Fischer, A.:  3d point cloud registration for localization using a deep neural network auto-encoder.  In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. (2017) 4631–4640
  * [4] Fischler, M.A., Bolles, R.C.:  Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography.  Communications of the ACM 24(6) (1981) 381–395
  * [5] Parra, Á., Chin, T.J., Neumann, F., Friedrich, T., Katzmann, M.:  A practical maximum clique algorithm for matching with pairwise constraints.  arXiv preprint arXiv:1902.01534 (2019)
  * [6] Bergström, P., Edlund, O.:  Robust registration of point sets using iteratively reweighted least squares.  Computational Optimization and Applications 58(3) (2014) 543–561
  * [7] Torr, P.H., Zisserman, A.:  Mlesac: A new robust estimator with application to estimating image geometry.  Computer vision and image understanding 78(1) (2000) 138–156
  * [8] Chum, O., Matas, J., Kittler, J.:  Locally optimized ransac.  In: DAGM, Springer (2003)
  * [9] Chum, O., Matas, J.:  Matching with prosac-progressive sample consensus.  In: 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05). Volume 1., IEEE (2005) 220–226
  * [10] Parra Bustos, Á., Chin, T.J.:  Guaranteed outlier removal for rotation search.  In: Proceedings of the IEEE International Conference on Computer Vision. (2015) 2165–2173
  * [11] Parra, Á., Chin, T.J.:  Guaranteed outlier removal for point cloud registration with correspondences.  TPAMI 40(12) (2018) 2868–2882
  * [12] Svarm, L., Enqvist, O., Oskarsson, M., Kahl, F.:  Accurate localization and pose estimation for large 3d models.  (06 2014) 532–539
  * [13] Truong, G., Gilani, S.Z., Islam, S., Suter, D.:  Fast point cloud registration using semantic segmentation.  In: DICTA. (2019)
  * [14] Wu, B., Wan, A., Yue, X., Keutzer, K.:  Squeezeseg: Convolutional neural nets with recurrent crf for real-time road-object segmentation from 3d lidar point cloud.  ICRA (2018)
  * [15] Wu, B., Zhou, X., Zhao, S., Yue, X., Keutzer, K.:  Squeezesegv2: Improved model structure and unsupervised domain adaptation for road-object segmentation from a lidar point cloud.  In: ICRA. (2019)
  * [16] Milioto, A., Vizzo, I., Behley, J., Stachniss, C.:  RangeNet++: Fast and Accurate LiDAR Semantic Segmentation.  In: IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems (IROS). (2019)
  * [17] Enqvist, O., Josephson, K., Kahl, F.:  Optimal correspondences from pairwise constraints.  In: 2009 IEEE 12th International Conference on Computer Vision. (Sep. 2009) 1295–1302
  * [18] Lu, W., Wan, G., Zhou, Y., Fu, X., Yuan, P., Song, S.:  Deepvcp: An end-to-end deep neural network for 3d point cloud registration.  In: IEEE ICCV. (2019)
  * [19] Yew, Z.J., Lee, G.H.:  3dfeat-net: Weakly supervised local 3d features for point cloud registration.  In: ECCV. (2018)
  * [20] Fischler, M.A., Bolles, R.C.:  Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography.  Commun. ACM 24(6) (June 1981) 381–395
  * [21] Choi, S., Kim, T., Yu, W.:  Performance evaluation of ransac family.  In: BMVC 2009
  * [22] Aiger, D., Mitra, N.J., Cohen-Or, D.:  4-points congruent sets for robust surface registration.  ACM Transactions on Graphics 27(3) (2008) #85, 1–10
  * [23] Theiler, P.W., Wegner, J.D., Schindler, K.:  Keypoint-based 4-points congruent sets – automated marker-less registration of laser scans.  ISPRS Journal of Photogrammetry and Remote Sensing 96 (2014) 149 – 163
  * [24] Olsson, C., Kahl, F., Oskarsson, M.:  Branch-and-bound methods for euclidean registration problems.  IEEE Transactions on Pattern Analysis and Machine Intelligence 31(5) (May 2009) 783–794
  * [25] Campbell, D., Petersson, L.:  Gogma: Globally-optimal gaussian mixture alignment.  In: 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). (June 2016) 5685–5694
  * [26] Zhong, Y.:  Intrinsic shape signatures: A shape descriptor for 3d object recognition.  In: IEEE ICCV. (2009)
  * [27] Tombari, F., Salti, S., Di Stefano, L.:  Performance evaluation of 3d keypoint detectors.  International Journal of Computer Vision 102 (2019) 198–220
  * [28] Horn, B.K.P.:  Closed-form solution of absolute orientation using unit quaternions.  Journal of the Optical Society of America A 4 (1987) 629–642
  * [29] Horst, R., Tuy, H.:  Global optimization: Deterministic approaches.  Springer Science & Business Media (2013)
  * [30] Feige, U., Goldwasser, S., Lovász, L.:  Approximating clique is almost np-complete
  * [31] Pelofske, E., Hahn, G., Djidjev, H.:  Solving large maximum clique problems on a quantum annealer.  In: International Workshop on Quantum Technology and Optimization Problems, Springer (2019) 123–135
  * [32] Lu, C., Yu, J.X., Wei, H., Zhang, Y.:  Finding the maximum clique in massive graphs.  Proceedings of the VLDB Endowment 10(11) (2017) 1538–1549
  * [33] Kurita, K., Wasa, K., Arimura, H., Uno, T.:  Constant amortized time enumeration of independent sets for graphs with forbidden subgraphs on fixed number of vertices.  arXiv preprint arXiv:1906.09680 (2019)
  * [34] Geiger, A., Lenz, P., Urtasun, R.:  Are we ready for Autonomous Driving? The KITTI Vision Benchmark Suite.  In: IEEE CVPR. (2012) 3354–3361
  * [35] Behley, J., Garbade, M., Milioto, A., Quenzel, J., Behnke, S., Stachniss, C., Gall, J.:  SemanticKITTI: A Dataset for Semantic Scene Understanding of LiDAR Sequences.  In: IEEE ICCV. (2019)
  * [36] Rusu, R.B., Blodow, N., Beetz, M.:  Fast point feature histograms (FPFH) for 3d registration.  In: 2009 IEEE ICRA. (2009)
  * [37] Le, H.M., Do, T., Hoang, T., Cheung, N.:  Sdrsac: Semidefinite-based randomized approach for robust point cloud registration without correspondences.  In: 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). (June 2019) 124–133