Track Extraction from Point Clouds
About
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:
- If the tracks are straight lines, the iterative 3D Hough transform can be used.
- If the tracks are curved, TriplClust can be used.
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):
- C. Dalitz, T. Schramke, M. Jeltsch: Iterative Hough Transform for Line Detection in 3D Point Clouds. Image Processing On Line 7, pp. 184-196 (2017)
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:
- M. Jeltsch, C. Dalitz, R. Pohle-Fröhlich: Hough Parameter Space Regularisation for Line Detection in 3D . International Conference on Computer Vision Theory and Applications (VISAPP), pp. 345-352 (2016)
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 reference implementation is additionally available from github):
- C. Dalitz, J. Wilberg, L. Aymans: TriplClust: An Algorithm for Curve Detection in 3D Point Clouds. Image Processing On Line 9, pp. 26-46 (2019)
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:
- C. Dalitz, Y. Ayyad, J. Wilberg, L. Aymans, D. Bazin, W. Mittig: Automatic trajectory recognition in Active Target Time Projection Chambers data by means of hierarchical clustering. Computer Physics Communications 235, pp. 159-168 (2019)