Given an input set of $3$D point pairs, the goal of outlier-robust $3$D
registration is to compute some rotation and translation that align as many
point pairs as possible. This is an important problem in computer vision, for
which many highly accurate approaches have been recently proposed. Despite
their impressive performance, these approaches lack scalability, often
overflowing the $16$GB of memory of a standard laptop to handle roughly
$30,000$ point pairs. In this paper, we propose a $3$D registration approach
that can process more than ten million ($10^7$) point pairs with over $99\%$
random outliers. Moreover, our method is efficient, entails low memory costs,
and maintains high accuracy at the same time. We call our method TEAR, as it
involves minimizing an outlier-robust loss that computes Truncated Entry-wise
Absolute Residuals. To minimize this loss, we decompose the original
$6$-dimensional problem into two subproblems of dimensions $3$ and $2$,
respectively, solved in succession to global optimality via a customized
branch-and-bound method. While branch-and-bound is often slow and unscalable,
this does not apply to TEAR as we propose novel bounding functions that are
tight and computationally efficient. Experiments on various datasets are
conducted to validate the scalability and efficiency of our method.

在计算机视觉领域，针对具有异常数据的三维点对输入集合，我们提出了一种名为 TEAR 的方法，其旨在通过最小化一个鲁棒性强的损失函数来实现三维配准，该方法能够处理超过 1000 万个点对，并且具有高效性、低内存成本和高准确性。