Track Extraction from Point Clouds


It is often necessary to automatically identify tracks or curves in point clouds, e.g. particle tracks in TPC (time projection chamber) data from physical experiments, vehicle tracks in dynamic vison data, or superstructures in LIDAR data.

At the iPattern institute, we have worked on different algorithms that address this problem. Depending on the kind of curves, the following algorithms can be tried:

Both algorithms work with unstructured 3D point clouds. They can, however, also be applied to 2D point clouds by simply setting the third component to zero. Time information is neither required nor used by the algorithms.

Straight tracks

The Iterative Hough Transform finds straight lines that approximately pass through a large number of points from the point cloud. A reference implementation in C++ and a detailed description with examples from TPC data can be found in the following publication (the reference implementation is additionally available from github):

The quantization method for the Hough parameter space and an application to roof ridge detection in LIDAR data was first described in the following publication:

Curved tracks

Unlike the Hough transform, TriplClust does not yield a parametric description of curves, but partitions ("clusters") the point cloud into point sets representing different tracks. Points at track intersections obtain several labels, and points identified as belonging to no track are labelled as "noise". A reference implementation in C++ and a detailed description with examples different types of data can be found in the following publication:

The algorithm was originally devised to analyze ATTPC experiments. It was first presented together with an evaluation on ATTPC data contianing both straight an curved lines in the following publication: