Abstract

Robust estimation is essential in computer vision, robotics, and navigation, aiming to minimize the impact of outlier measurements for improved accuracy. We present a fast algorithm for Geman-McClure robust estimation, FracGM, leveraging fractional programming techniques. This solver reformulates the original non-convex fractional problem to a convex dual problem and a linear equation system, iteratively solving them in an alternating optimization pattern. Compared to graduated non-convexity approaches, this strategy exhibits a faster convergence rate and better outlier rejection capability. In addition, the global optimality of the proposed solver can be guaranteed under given conditions. We demonstrate the proposed FracGM solver with Wahba's rotation problem and 3-D point-cloud registration along with relaxation pre-processing and projection post-processing. Compared to state-of-the-art algorithms, when the outlier rates increase from 20% to 80%, FracGM shows 53% and 88% lower rotation and translation increases. In real-world scenarios, FracGM achieves better results in 13 out of 18 outcomes, while having a 19.43% improvement in the computation time.

Method

The Geman-McClure robust estimation problem is a special case of fractional program, where the numerators and denominators are all convex (assuming that all square of residuals are convex). We introduce upper bound variables and Lagrange multipliers to reformulate the fractional program to a dual problem. We then alternatively solve the dual problem by a convex program and a linear system. Note that the linear system is part of the KKT conditions of the convex dual problem. In addition, we develop conditionally global optimality for the propose solver with the help of fractional programming techniques.

We demonstrate FracGM on point cloud registration problems. In order to apply FracGM, we first relax the rotational constraint to align our assumptions (all square of residuals are convex). The dual problem is now a convex quadratic program with linear constraints only. Therefore, both the convex program and the linear system has closed-form solutions. At last, since the solution does not satisfy the rotational constraint, we project the solution back to the rotation group by singular value decomposition.

Results

(a) Point cloud registration with synthetic Bunny dataset. FracGM is truly robust even with extreme outlier rates.

(b) Point cloud registration with 3DMatch dataset. FracGM achieves the best results in 13 out of 18 outcomes.

BibTeX

@article{Chen24FracGM,
  author={Chen, Bang-Shien and Lin, Yu-Kai and Chen, Jian-Yu and Huang, Chih-Wei and Chern, Jann-Long and Sun, Ching-Cherng},
  journal={IEEE Robotics and Automation Letters},
  title={FracGM: A Fast Fractional Programming Technique for Geman-McClure Robust Estimator},
  year={2024},
  volume={9},
  number={12},
  pages={11666-11673},
  doi={10.1109/LRA.2024.3495372}
}