Modeling connected regions in arbitrary planar point clouds by robust B-spline approximation

This paper presents an algorithm for robustly approximating the boundary of a domain, latent in a planar set of scattered points, by a B-spline curve. The algorithm is characterized by three key features: First, we propose a distance measure, called the Asymmetric Distance (AD), which allows for handling outliers inside the curve and finding the outer boundary or concave hull by specifying very natural parameters like smoothness and accuracy. Second, we provide a solution to the problem of unknown required degrees of freedom by Error-Adaptive Knot Insertion (EAKI). During the iterations of our re-weighted least-squares formulation, we check for regions of high error on the curve and locally increase the degrees of freedom if necessary. Third, we present a method to handle deep and narrow concavities, called Concavity Filling (CF). The curve is examined for areas of large distances to the closest data points. In these regions, we explicitly strap the curve to internal points to force it to bend inwards and fill the concavity. Compared with the state of the art, our method shows fundamental improvement in terms of robustness and applicability to real-world data. For 3D reconstruction of organized and unorganized point clouds, prevalent in robotic RGBD perception, we achieve higher robustness compared to state-of-the-art methods and compression rates up to a factor of 300. We have integrated our code into the Point Cloud Library (PCL) and created a tutorial that guides through the steps of the algorithm (see footnote 1). (C) 2015 Elsevier B.V. All rights reserved.