Algorithms to extract trajectory lines out of 3D point clouds

Question

I am looking for different approaches to extract 3D polylines out of Point Clouds.

We are able to create these point clouds out of different data sources of real world surveys (LIDAR, RADAR, etc...) and to classify points (as metallic in common soil for example). What I am looking for is academic work/papers on algorithms with the purpose of extracting polylines out of linear features in classified Point Clouds. I am asking for academic work especially, as this is a first shot to possibly kick off my own thesis if the topic shows further potential.

Any suggestions?

Answer 1

I will summarize a couple of possibilities:

1. As a baseline, I would begin with a Hough transform kind of approach:

Iterative Hough Transform for Line Detection in 3D Point Clouds Christoph Dalitz, Tilman Schramke, Manuel Jeltsch

There is also an online demo as well as source code. Here is another paper of the same Hough-approach:

Hough Parameter Space Regularisation for Line Detection in 3D Manuel Jeltsch, Christoph Dalitz and Regina Pohle-Frohlich

2. A topological approach to detect structure lines: https://www.int-arch-photogramm-remote-sens-spatial-inf-sci.net/XXXIX-B3/143/2012/isprsarchives-XXXIX-B3-143-2012.pdf

Structure Line Detection from LIDAR Point Clouds using Toplogical Elevation Analysis. C. Y. Loa, L. C. Chen

3. It is possible to detect the contours in the point clouds, using e.g. this algorithm. Next step would be to cluster the points which are co-linear. This can be achieved for instance, using RANSAC.

4. Some algorithms try to find some linear structures using geometric analysis: Edge Detection and Feature Line Tracing in 3D-Point Clouds by Analyzing Geometric Properties of Neighborhoods

5. If you have a multi-view setting, then this link would also be of interest.

I hope these resources help get you in the right direction.

---

UPDATE: Recently I have come across this work that seems to generate a visually pleasing outcome in a reasonable amount of time:

Lu, Xiaohu and Liu, Yahui and Li, Kai. "Fast 3D Line Segment Detection From Unorganized Point Cloud." arXiv preprint arXiv:1901.02532 (2019). https://arxiv.org/pdf/1901.02532.pdf

Answer 2

When the points belong to more than one curve, it will first be necessary to cluster them into curves. A possible approach is described together with a reference implementation in

Dalitz, Wilberg, Aymans: TriplClust: An Algorithm for Curve Detection in 3D Point Clouds. IPOL 2019.234 (2019)

When your points have an implicit parameter representing an approximate time of the point on the x(t) curve, Moving Least Squares might be applicable (beware that the algorithm commonly associated with this term is not applicable for 1D manifolds, i.e. curves):

Amirfakhrian, Mafikandi: "Approximation of parametric curves by Moving Least Squares method." Applied Mathematics and Computation 283, pp. 290-298 (2016)

When no time is knwon, a possible option is to select some representative points and fit a perfect spline through this representative points:

Rupniewski: "Curve Reconstruction from Noisy and Unordered Samples." ICPRAM, pp. 183-188 (2014)

In any case, I would greatly apprciate, if you keep me informed which method works for you and how you have solved your problem.