Search code examples
algorithm3dgeometrypoint-cloudsransac

RANSAC for cuboid

I have been able to successfully implement RANSAC on a 3D point cloud for the usual models, i.e. a sphere, line, plane. However, I'm having a hard time wrapping my head around how to do it for a cuboid, specifically just a 3d box. I'm unsure how to parameterize the box using points.

Ideally I would like to obtain length, width, height, and center as my parameters (Theta). I am confused in how to fit these parameters using a minimum-ish number of points from a 3D point cloud of the surface of a cube. (I will also have access to point normals).

For example, I eventually want to estimate the 6 faces of the cube. I could just estimate three and take their parallel mirrors to get all 6. Each face will be presumably represented as a plane, which needs a point and a normal to define (or alternatively 3 points). However, there are constraints on the normals of each plane, since they all need to be orthogonal to each other. I am unsure of how to include constraints in the model estimation, or if this is even the right way to go about it.

Any ideas would be greatly appreciated. I'm currently using Marco Zuliani's "RANSAC for Dummies" Toolbox implementation, if that's relevant at all.

Solution

  • If I were to devise an algorithm to solve this problem (fitting a cube to a point cloud of a cube) I would divide it into two steps:

    1. Use some clustering algorithm to find six clusters, one for each face. During the algorithm excution, I would need six "candidate" regions, and each point would be considered to be pertaining to one of the face clusters, or to be an outlier. Some modified form of DBSCAN seems to be a suitable option;
    2. Apply some fitting to each face, most probably RANSAC since it's what you are already using.

    If the expected size of the cube is known, you can insert every point into a KDTree, and query spheric vicinities with radious just below the size of one face, checking for planarity (principal components come to mind). Then you would eventually find good approximate candidates for the six face centers.