Best way to group 3d points into planes, if any

If I have some 3d points, how can I discover parallel planes within them (not just arbitrary planes).

I want to know how many "levels" or "floors" something can travel within, after it has done so, so I want to cluster the positions into planes.

Some of them might not be in a plane, most of them are noisy (not perfectly planar), and I have no knowledge of the world orientation, so the planes aren't necessarily orthogonal to some known axis.

I know one way is a 3d-hough transform, but is there something better?

• Do you know anything more about the structure? E.g. are there just a handful of planes, or are there many planes but just a few points per plane? Are the planes equidistant? Are the points within a plane closer to eachother than to the points of the other planes? – flawr May 20 '17 at 13:03
• Also do you have an upper bound of the number of planes? – flawr May 20 '17 at 14:53
• If the points are noisy and some are not in a plane, could you clarify how much deviation from a plane due to noise is permitted, before a point is no longer regarded as being in that plane? For an approximate solution you would need to explain what your priorities are. – trichoplax Jun 5 '17 at 12:08

A reasonable approach is a continuous sample consensus method. The hough transform can be though of as a discrete sample consensus method, and so becomes intractable for some problems. Sample consensus is nice, because we can impose arbitrary constraints, and handle even the most horrific noise.

Getting Planes: Sample Consensus

The idea is determine the minimum number of observations needed to form a hypothesis, and then check how many observations agree with that hypothesis. We'll call those observations "inliers".

1. Three point determine a plane. Select three points (deterministically, at random, whatever) from your dataset, fit a plane to them.

2. Check how many points in your point cloud "support" the plane. Meaning that the plane existing in the world could explain what the sensor saw; the observations "support" the conclusion that the plane exists. For your case, a reasonable metric for "support" would be perpendicular distance to the plane.

3. In postprocessing, you might cull planes that don't have sufficient width.

Extracting Parallel Planes: Normal Binning

If you don't have a prior on the structure of your data other than "has parallel planes", then you're likely trapped trying to discover as many planes as possible and then filtering for parallel ones.

One might consider a "binning" approach

1. Start with the first plane, and say its normal belongs to $bin_0$
2. For each discovered plane, check the angle it makes with every existing bin
3. If the angle is less than $\epsilon$, add that plane to $bin_n$
4. If the angle is greater than (or equal, for completeness) to $\epsilon$, create a new bin, $bin_{n+1}$

Presumably the largest bin is the thing you want if you have culled small planes.

Other Notes

Sample consensus will generally perform better if, after fitting to data and finding points that agree, you run a quick optimization to fit a plane to all of the inlier points. Then recompute inliers, and re-run the optimization. After all, it's quite unlikely that the three points you happened to choose were exactly the true plane. Much more likely is that varying plane parameters to minimize point-to-plane error over all of the inlier observations will yield a nice plane, with the noise averaged out.