Categories
research

Plane and Edge Detection by the Random Sample Consensus (RANSAC)  Algorithm

By SGI Fellows Xinwen Ding, Josue Perez, and Elshadai Tegegn

During the second week of SGI, we worked under the guidance of Prof. Yusuf Sahillioğlu to detect planes and edges from a given point cloud. The main tool we applied to complete this task is the Random Sample Consensus (RANSAC) algorithm.

Definition

We define a plane P as the dominant plane of a 3D point cloud if the number of points defined in the 3D point cloud located on the plane P is no less than the number of points on any other plane. For example, consider the following object defined by a 3D point cloud. If we assume the number of points on a face is proportional to the area of the face, then \(P_2\) is more likely to be the dominant plane than \(P_1\) since the area of \(P_2\) is greater than that of \(P_1\). So, compared with \(P_1\), there are more points on \(P_2\), which makes \(P_2\) the potential dominant plane.

An object that is defined by a point cloud, where P2 is more likely to be the dominant plane than P1.

Problem Description

Given a 3D point cloud as the input model, we aim to detect all the planes in the model. To obtain a decent detection result, we divide the problem into two separate parts:

  • Part 1: Find the dominant plane \(P\) from a given 3D point cloud. This subproblem can be solved by the RANSAC Algorithm.
  • Part 2: Find all other planes contained in the 3D point cloud. This subproblem can be successfully addressed if we iteratively repeat the following two steps: (1). remove all the points on plane \(P\) (obtained from Part 1) from the given point cloud. (2). repeat the RANSAC algorithm with respect to the remaining points in the point cloud.

The RANSAC Algorithm

An Introduction to RANSAC

The RANSAC algorithm is a learning technique that uses random sampling of observed data to best estimate the parameters of a model.
RANSAC divides data into inliers and outliers and yields estimates computed from a minimal set of inliers with the most outstanding support. Each data is used to vote for one or more models. Thus, RANSAC uses a voting scheme.

Workflow & Pseudocode

RANSAC achieves its goal by repeating the following steps:

  • Sample a small random subset of data points and treat them as inliers.
  • Take the potential inliers and compute the model parameters.
  • Score how many data points support the fitting. Points that fit the model well enough are known as the consensus set.
  • Improve the model accordingly.

This procedure repeats a fixed number of times, each time producing a model that is either rejected because of too few points in the consensus set or refined according to the corresponding consensus set size.

The pseudocode of the algorithm is recorded as below:

function dominant_plane = ransac(PC)
    n := number of points defined in point cloud PC

    max_iter := max number of iterations

    eps := threshold value to determine data points that are 
           fit well by model (a 3D plane in our case)

    min_good_fit := number of nearby data points required to 
                    assert that a model (a 3D plane in our 
                    case) fits well to data

    iter := current iteration

    best_err := measure of how well a plane fits a set of 
                points. Initialized with a large number

    % store dominant plane information
    % planes are characterized as [a,b,c,d], where
    % ax + by + cz + d = 0
    dominant_plan = zeros(1,4);

    while iter < max_iter
        maybeInliers := 3 randomly selected values from data 
        maybePlane := a 3D plane fitted to maybeInliers
        alsoInliers := [] 
        for every point in PC not in maybeInliers
            if point_to_model_distance < eps
                add point to alsoInliers
            end if
        end for

        if number of points in alsoInliers is > min_good_fit
            % the model (3D plane) we find is accurate enough

            % this betterModel can be found by solving a least 
            % square problem.
            betterPlane := a better 3D plane fits to all 
                        points in maybeInliers and alsoInliers
            err := sum of distances from the points in 
                   maybeInliers and alsoInliers to betterPlane
            if err < best_err
                best_err := err
                dominant_plane := betterPlane
            end if
        end if

        iter = iter + 1;
    end while
end

Detect More Planes

As mentioned before, to detect more planes, we may simply remove the points that are on the dominant plane \(P\) of the point cloud, according to what is suggested by the RANSAC algorithm. After that, we can reapply the RANSAC algorithm to the remaining points, and we get the second dominant plane, say \(P’\) of the given point cloud. We may repeat the process iteratively and detect the planes one by one until the remaining points cannot form a valid plane in 3D space.

The following code provides a more concrete description of the iterative process.

% read data from .off file
[PC, ~] = readOFF('data/off/330.off');

% A threshold eps is set to decide if a point is on a detected 
% plane. If the distance from a point to a plane is less than 
% this threshold, then we consider the point is on the plane.
eps = 2e-3;

while size(PC, 1) > 3
    % in the implementation of ransac, if the algorithm cannot 
    % detect a plane using the existing points, then the 
    % coefficient of the plane (ax + by + cz + d = 0) is a 
    % zero vector.
    curr_plane_coeff = ransac(PC);
    
    if norm(curr_plane_coeff) == 0
        % remaining points cannot lead to a meaningful plane.
        % exit loop and stop algorithm
        break;
    end

    % At this point, one may add some code to visualize the 
    % detected plane.

    % return the indices of points that are on the dominant
    % plane detected by RANSAC algorithm
    [~, idx] = pts_close_to_plane(PC, curr_plane_coeff, eps);

    % remove the points on the dominant plane.
    V(idx,:) = [];
end

Results

RANSAC algorithm gives good results with 3D point clouds that have planes made up of a good number of points. The full implementation is available on SGI’s Github. This method is not able to detect curves or very small planes. The data we used to generate these examples are the Mechanical objects (Category 17) from this database.

Successful Detections

Mech. Data Model NumberModel Object RANSAC Plane Detection Result
330
331
In the third column, red dots are points on the most dominant plane, followed by blue and green dots are points on the least dominant plane.

Unsuccessful Detections

Mech. Data Model NumberModel Object RANSAC Plane Detection Result
332
338
In the third column, red dots are points on the most dominant plane, followed by blue and green dots are points on the least dominant plane. White points are the ones that cannot be characterized as a plane by the RANSAC algorithm.

Limitations and Future Work

As one may observe from the successful and unsuccessful detections, the RANSAC algorithm is good at detecting planar surfaces. However, the algorithm usually fails to detect a curved surface, because we are fitting the three randomly selected points using a plane equation as our base model. If we change this model to be a curved surface, then theoretically speaking, the RANSAC algorithm should be able to detect a curved plane. We may apply a similar fix if we want to perform line detection.

Moreover, we may notice that the majority of surfaces in our test data can be represented easily by an analytical formula. However, this pre-condition is, in general, not true if we choose an arbitrary point cloud. If this is the case, the RANSAC algorithm is unlikely to output an accurate detection result, which leads to more extra work.