Analysing 3D point clouds: detecting and measuring objects

Image Processing

A 3D scanner above a conveyor belt delivers a point cloud: many thousands of points in space, unordered, noisy and with gaps. What is lying there – a cylinder, a box, a sphere? How large is it, and what is its volume?

The processing chain

1. Filtering: crop the region, thin it out with a voxel grid and remove outliers – in the Point Cloud Library (PCL) with CropBox, VoxelGrid and StatisticalOutlierRemoval.
2. Removing the background: find the conveyor belt or floor as a plane and subtract it.
3. Segmentation: split the remaining points into individual objects by proximity, for example with EuclideanClusterExtraction.
4. Shape recognition: fit models such as plane, cylinder or sphere and take the one with the most matching points.
5. Measurement: determine dimensions, bounding box and volume.

RANSAC: robust against outliers

RANSAC (Random Sample Consensus) is the workhorse of point cloud analysis. It repeatedly picks the smallest possible random sample – three points for a plane –, computes the model and counts the points within the tolerance band. The model with the most hits wins; outliers never find enough support.

The required number of iterations is N = log(1 − p) / log(1 − w^s), with confidence p, inlier share w and sample size s. With 30% of the points on the belt, about 170 iterations suffice for 99% confidence.

The minimum bounding box

For packaging, storage space or sorting, what often matters is the smallest box around an object. The axis-aligned box depends on how the object is lying, and the box along the principal axes (PCA) is only an approximation. For objects on a belt there is an elegant shortcut, because the box stands on the belt plane. You project the object points onto this plane and look for the smallest rectangle around the footprint. According to Freeman and Shapira, one side of this rectangle always lies on an edge of the convex hull. So it is enough to check one rectangle per hull edge – which is exactly what rotating calipers do. In Python, cv2.minAreaRect does this search:

import numpy as np
import cv2


def plane_ransac(points, threshold=2.0, iterations=200):
    """Plane with the most points closer than 'threshold' (mm)."""
    rng = np.random.default_rng(1)
    best, best_count = None, 0
    for _ in range(iterations):
        p1, p2, p3 = points[rng.choice(len(points), 3, replace=False)]
        n = np.cross(p2 - p1, p3 - p1)
        if np.linalg.norm(n) < 1e-9:  # three points on a line
            continue
        n /= np.linalg.norm(n)
        count = np.count_nonzero(np.abs((points - p1) @ n) < threshold)
        if count > best_count:
            best, best_count = (n, -n @ p1), count
    return best


def measure_object(points, threshold=2.0):
    n, d = plane_ransac(points, threshold)
    distance = points @ n + d
    if np.median(distance) < 0:  # normal should point away from the belt
        n, distance = -n, -distance
    above = distance > 3 * threshold
    # Span two axes in the plane and project the object points onto them
    u = np.cross(n, [1.0, 0, 0] if abs(n[0]) < 0.9 else [0, 1.0, 0])
    u /= np.linalg.norm(u)
    footprint = np.column_stack((points[above] @ u, points[above] @ np.cross(n, u)))
    _, (a, b), _ = cv2.minAreaRect(footprint.astype(np.float32))
    return max(a, b), min(a, b), np.percentile(distance[above], 99)

For a simulated box of 120 × 80 × 50 mm on a tilted belt with 0.5 mm noise, the code returns 120.5 × 80.4 × 50.9 mm. The 99th percentile for the height dampens individual outliers.

Volume: box, hull or height map

The volume of the box is only an upper bound: a cylinder fills just over three quarters of its box, a sphere just over half. The convex hull is more accurate, but still too large for concave objects. Since a scanner looking from above only sees the top, the volume is often calculated as a height map: for each cell of the footprint, area times height above the belt.

From our projects

For an international sensor manufacturer, we developed software that detects objects in the point clouds of its 3D scanners, classifies their shape – cylinder, box, sphere – and then quickly calculates their volume. The methods included RANSAC, minimum bounding box, rotating calipers and eigenvalue calculations. We first pre-computed and verified each algorithm in MATLAB before implementing it in C++ with PCL, OpenCV, Halcon and Eigen. We tested in the lab with scanners in different positions, with data from a production line and with a scan data simulation for which we modelled the setup in 3D.

Typical mistakes

• Computing without filters. Outliers and multiple reflections inflate every box.
• Choosing a RANSAC tolerance smaller than the measurement noise – the method then fails to find the plane reliably.
• Reporting the volume of the box as the real volume.
• Testing only with clean lab data. Data from the line and simulated edge cases belong in the tests too.

From our projects: object recognition in point clouds and calibration of 3D scanners for an international sensor manufacturer. Further reading: M. A. Fischler, R. C. Bolles, “Random Sample Consensus”, Communications of the ACM 24(6), 1981; H. Freeman, R. Shapira, Communications of the ACM 18(7), 1975; Point Cloud Library.