Algebraic method to speed up robust algorithms: example of laser-scanned point clouds

摘要

Surface reconstruction from point clouds generated by laser scanning technology has become a fundamental task in many fields of geosciences, such as robotics, computer vision, digital photogrammetry, computational geometry, digital building modelling, forest planning and operational activities. Point clouds produced by laser scanning, however, are limited due to the occurrence of occlusions, multiple reflectance and noise, and off-surface points (outliers), thus necessitating the need for robust fitting techniques. In this contribution, a fast, noniterative and data invariant algebraic algorithm with constant O(1) complexity that fits planes to point clouds in the total least squares sense using Gaussian-type error distribution is proposed. The maximum likelihood estimator method is used, resulting in a multivariate polynomial system that is solved in an algebraic way. It is shown that for plane fitting when datasets are affected heavily by outliers, the proposed algebraic method can be embedded into the framework of robust methods like the Danish or the RANdom SAmple Consensus methods and computed in parallel to provide rigorous algebraic fitting with significantly reduced running times. Compared to the embedded traditional singular value decomposition and principal component analysis approaches, the performance of the proposed algebraic algorithm demonstrated its efficiency on both synthetic data and real laser-scanned measurements. The evaluation of a symbolic algebraic formula is practically independent of the values of its coefficients; however, the computation of the coefficients depends on the complexity of the data. Since the main advantage of the symbolic solution is its nonrequirement of numerical iteration, the data complexity will have weak influence on the speedup. The novelty of the proposed method is the use of algebraic technique in a robust plane fitting algorithm that could be applied to remote sensing data analysis/ delineation/ classification. In general, the method could be applied to most plane fitting problems in the geoscience field.