A Point Cloud Contour Extraction Method based on Plane Segmentation

The problem

Extracting contour features from point clouds is used in industrial inspection, robot operation and related fields. Point clouds from real devices contain noise and carry no topological relationships between points, which makes contours hard to detect. Plane detection has been approached with Hough transforms, region growing and iterative RANSAC; boundary extraction with triangular meshes, breakline sorting with B-spline fitting, and the alpha shape algorithm. Alpha shapes can extract the inner and outer contour points of polygons, but for point clouds with a large data volume its time complexity is high.

Plain RANSAC has a weak spot of its own: it tolerates obvious noise, but points just off the plane, such as those of an adjacent plane, fall within the distance threshold and introduce errors. The paper targets the contours of the surfaces of an object, here the contours of the chips on a circuit board.

How it works

The method has two stages. Plane segmentation fuses RANSAC with PCA to split the cloud into planar point sets. Contour extraction then turns each plane into a 2D image, finds its boundary from the image gradient, and maps the boundary points back into 3D space.

1. RANSAC proposes planes. Three far-apart points are drawn at random and a plane is fitted through them; points within a distance threshold d_th of the plane join its set. After N_iterate iterations the largest set is kept as the current plane and removed from the cloud, and the search repeats until fewer than N_minnum points remain.
2. PCA refines and cleans the planes. Each set is refitted by PCA: the plane passes through the centroid, and its normal is the eigenvector of the covariance matrix with the smallest eigenvalue. Two planes whose normals differ by less than 15° are merged if more than 90% of their points lie within d_th of the other plane; plane pairs with too few points are removed. This repeats until no plane can be merged or removed.
3. Flatten each plane into an image. A rotation matrix turns the planar point cloud parallel to the XOY plane, and a projection with focal lengths and offsets maps it into a 2D image. Pixels holding object points are set to 0, all others to 1.
4. Find the boundary from gradients. The image is smoothed with a Gaussian filter, and the gradient magnitude and direction are computed. A preliminary edge pixel is kept as a boundary point only if its value is the largest among its neighbours along the gradient direction.
5. Map back to 3D. The boundary pixels are transformed back through the projection and the inverse rotation, giving the contour points in 3D space.

Results

The experiments extract the contours of the chips on a circuit board, running on an Intel i7-12700 CPU with 16 GB of memory. For plane segmentation, the method is compared with region growing and conventional RANSAC on the same data. On the chip shown below, region growing also takes in a neighbouring region and RANSAC a strip attached below the chip, whereas PCA-RANSAC returns the chip surface alone; the paper describes its result as the one least affected by noise.

For boundary extraction the method is compared with the alpha shape algorithm. On a single chip, alpha shapes returns a sparse, broken outline, while the proposed method returns a denser, continuous one in less time.