Detection of lines in a point cloud

What are the best solutions to detect line in a point cloud? Comparison being made with and between Hough Transform, Radon Transform, RANSAC (see wikipedia) and Brute-Force Search (see wikipedia).
Which one is the most robust against the dispersion of points in point cloud?
Note:
1- The question is about 3D point cloud not image.
2- Points in point cloud are randomly dispersed (completely sparse locations).
3- There is no information about the object (line) being explored in terms of preferred orientation, size, etc.
4- A tolerance needs to be considered around the candidate line.
According to my experiments: RANSAC could miss easily some lines. It is good for quick detection of edges however the complexity of point dispersion could produce undesired outputs. Hough and Radon are very similar and I had not chance to try for 3D point cloud however they work well on 2D cases. There is a difficulty in extraction of segments of found lines. BFS is simply impractical for large data set.

• Radon and Hough would operate on volumetric data, not point clouds, as far as I know. The ideas can probably be adapted to point clouds, but I'm not sure if they'd still have the same name. Commented Dec 6, 2011 at 20:08
• What are your criteria? Brute force would definitely find a line if it's there, while RANSAC only "probably" finds the line. Commented Dec 6, 2011 at 22:36
• @endolith '...volumetric...': A good point. I think it is possible however to pixelate (map) the 3D points into 3D volume (3D matrix) with an acceptable tolerance referred to the resolution of matrix (i.e., number of cells). '...Brute-Force...' is absolutely accurate but not computationally practical for large set of points. 'RANSAC' as you mentioned could miss some candidates. The idea is to discuss and find some suggestions to deal with those problems: computation-cost and inexactness. Commented Dec 7, 2011 at 1:07
• Converting the point cloud to a volumetric matrix would probably be a step in the wrong direction. :) Better to use algorithms that operate on the point cloud and the Euclidean distance between points. Commented Dec 7, 2011 at 1:37
• I have given a proper list of resources: scicomp.stackexchange.com/questions/27649/… Commented Aug 29, 2017 at 19:20

It really depends, how will you measure the quality of the solutions? what are your requirements, real time, high accuracy? how large is the point cloud?

You mentioned valid, yet fancy signal processing based methods to address the problem.

Let me add three methods you have not mentioned that are classic and more statistical in nature: least squares, ridge regression and lasso.

• These are all optimization methods, but the trick is to find a good function to optimize. What is the function you're suggesting to optimize with respect to? Commented Feb 19, 2012 at 4:35

If you are really concerned about detection lines you can do a simplified approach.

Project your point cloud - on to at least two surfaces. Let say project them on XY plane and YZ plane. Basically start off with a blank canvas, and project each point based on some geometry criteria. So now you will have a finite 2D canvas which is all blank but white points which are present. Now you can apply hough transform on this canvases.

Based on hough, you will get lines $(r,\theta)$ and $(r,\phi)$ for two respective planes. Next step really is to associate these lines to identify single 3D line out of this.

As far as accuracy is concerned, when data is sparse, the score of the hough (i.e. strength) can be less. However, it will work if overall all lines are sparse. It is a problem when you are comparing a very long line against a short line.