We propose the first fast and certifiable algorithm for the registration of
two sets of 3D points in the presence of large amounts of outlier
correspondences. We first reformulate the registration problem using a
Truncated Least Squares (TLS) cost that is insensitive to a large fraction of
spurious correspondences. Then, we provide a general graph-theoretic framework
to decouple scale, rotation, and translation estimation, which allows solving
in cascade for the three transformations. Despite the fact that each subproblem
is still non-convex and combinatorial in nature, we show that (i) TLS scale and
(component-wise) translation estimation can be solved in polynomial time via
adaptive voting, (ii) TLS rotation estimation can be relaxed to a semidefinite
program (SDP) and the relaxation is tight, even in the presence of extreme
outlier rates, and (iii) the graph-theoretic framework allows drastic pruning
of outliers by finding the maximum clique. We name the resulting algorithm
TEASER (Truncated least squares Estimation And SEmidefinite Relaxation). While
solving large SDP relaxations is typically slow, we develop a second fast and
certifiable algorithm, named TEASER++, that uses graduated non-convexity to
solve the rotation subproblem and leverages Douglas-Rachford Splitting to
efficiently certify global optimality.
For both algorithms, we provide theoretical bounds on the estimation errors,
which are the first of their kind for robust registration problems. Moreover,
we test their performance on standard, object detection, and the 3DMatch
benchmarks, and show that (i) both algorithms dominate the state of the art and
are robust to more than 99% outliers, (ii) TEASER++ can run in milliseconds,
and (iii) TEASER++ is so robust it can also solve problems without
correspondences, where it largely outperforms ICP and it is more accurate than
Go-ICP while being orders of magnitude faster.

提出了一个名为 TEASER 的算法，它使用 TLS 成本和图论框架来解决 3D 点集之间的快速且可靠的配准问题，能够在存在大量离群值的情况下有效地工作。该算法还提供了理论误差界限，并且在标准和 3DMatch 基准测试中都表现出跨越式的性能优势。

TEASER：快速且可认证的点云配准

TEASER: Fast and Certifiable Point Cloud Registration

Early time series classification (eTSC) is the problem of classifying a time
series after as few measurements as possible with the highest possible
accuracy. The most critical issue of any eTSC method is to decide when enough
data of a time series has been seen to take a decision: Waiting for more data
points usually makes the classification problem easier but delays the time in
which a classification is made; in contrast, earlier classification has to cope
with less input data, often leading to inferior accuracy. The state-of-the-art
eTSC methods compute a fixed optimal decision time assuming that every times
series has the same defined start time (like turning on a machine). However, in
many real-life applications measurements start at arbitrary times (like
measuring heartbeats of a patient), implying that the best time for taking a
decision varies heavily between time series. We present TEASER, a novel
algorithm that models eTSC as a two two-tier classification problem: In the
first tier, a classifier periodically assesses the incoming time series to
compute class probabilities. However, these class probabilities are only used
as output label if a second-tier classifier decides that the predicted label is
reliable enough, which can happen after a different number of measurements. In
an evaluation using 45 benchmark datasets, TEASER is two to three times earlier
at predictions than its competitors while reaching the same or an even higher
classification accuracy. We further show TEASER's superior performance using
real-life use cases, namely energy monitoring, and gait detection.

TEASER 是一种新算法，它将早期时间序列分类建模为两个级别的分类问题，并在使用 45 个基准数据集进行评估时比竞争对手提前两至三倍地预测，同时达到相同或更高的分类准确性。