Scalable 3D Registration via Truncated Entry-wise Absolute Residuals

• URL: http://arxiv.org/abs/2404.00915v2
• Date: Tue, 9 Apr 2024 09:16:29 GMT
• Title: Scalable 3D Registration via Truncated Entry-wise Absolute Residuals
• Authors: Tianyu Huang, Liangzu Peng, René Vidal, Yun-Hui Liu,
• Abstract summary: A $3$D registration approach can process more than ten million ($107$) point pairs with over $99%$ random outliers. We call our method TEAR, as it involves minimizing an outlier-robust loss that computes Truncated Entry-wise Absolute Residuals.
• Score: 65.04922801371363
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• Robust Single Rotation Averaging Revisited [14.533304890042361]
  We propose a novel method for robust single rotation averaging that can efficiently handle an extremely large fraction of outliers. Our method is robust against up to 99% outliers given a sufficient number of accurate inliers, outperforming the current state of the art.
  arXiv  Detail & Related papers  (2023-09-11T11:35:17Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching. Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
  arXiv  Detail & Related papers  (2022-10-14T01:42:05Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  We show that our method computes a solution with cost at most $O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$, where $epsilon$ is the privacy guarantee. Although the worst-case guarantee is worse than that of state of the art private clustering methods, the algorithm we propose is practical.
  arXiv  Detail & Related papers  (2022-06-17T09:24:41Z)
• List-Decodable Mean Estimation via Iterative Multi-Filtering [44.805549762166926]
  We are given a set $T$ of points in $mathbbRd$ with the promise that an unknown $alpha$-fraction of points in $T$ are drawn from an unknown mean and bounded covariance distribution $D$. We output a small list of hypothesis vectors such that at least one of them is close to the mean of $D$. In more detail, our algorithm is sample and computationally efficient, and achieves information-theoretically near-optimal error.
  arXiv  Detail & Related papers  (2020-06-18T17:47:37Z)
• FANOK: Knockoffs in Linear Time [73.5154025911318]
  We describe a series of algorithms that efficiently implement Gaussian model-X knockoffs to control the false discovery rate on large scale feature selection problems. We test our methods on problems with $p$ as large as $500,000$.
  arXiv  Detail & Related papers  (2020-06-15T21:55:34Z)
• Robust estimation via generalized quasi-gradients [28.292300073453877]
  We show why many recently proposed robust estimation problems are efficiently solvable. We identify the existence of "generalized quasi-gradients" We show that generalized quasi-gradients exist and construct efficient algorithms.
  arXiv  Detail & Related papers  (2020-05-28T15:14:33Z)
• Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization [6.037383467521294]
  We present a new exact MIP framework for $ell_0$ regularized regression. Our framework can scale to $p sim 107$, achieving speedups of at least $5000$x. We open source the implementation through our toolkit L0BnB.
  arXiv  Detail & Related papers  (2020-04-13T18:45:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.