{"id":278,"date":"2022-07-29T21:15:53","date_gmt":"2022-07-29T21:15:53","guid":{"rendered":"http:\/\/summergeometry.org\/sgi2022\/?p=278"},"modified":"2022-08-14T22:30:27","modified_gmt":"2022-08-14T22:30:27","slug":"plane-and-edge-detection-by-the-random-sample-consensus-ransac-algorithm","status":"publish","type":"post","link":"https:\/\/summergeometry.org\/sgi2022\/plane-and-edge-detection-by-the-random-sample-consensus-ransac-algorithm\/","title":{"rendered":"Plane and Edge Detection by the Random Sample Consensus\u00a0(RANSAC)\u00a0 Algorithm"},"content":{"rendered":"\n<p class=\"has-text-align-center wp-block-paragraph\"><em>By SGI Fellows Xinwen Ding, Josue Perez, and Elshadai Tegegn<\/em><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">During the second week of SGI, we worked under the guidance of  <a href=\"https:\/\/user.ceng.metu.edu.tr\/~ys\/\">Prof. Yusuf Sahillio\u011flu<\/a> to detect planes and edges from a given point cloud. The main tool we applied to complete this task is the Random Sample Consensus\u00a0(RANSAC)\u00a0algorithm.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Definition<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">We define a plane P as the&nbsp;<strong>dominant plane of a 3D point cloud<\/strong>&nbsp;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.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"http:\/\/summergeometry.org\/sgi2022\/wp-content\/uploads\/2022\/07\/image-1-1024x761.png\" alt=\"\" class=\"wp-image-283\" width=\"610\" height=\"453\" srcset=\"https:\/\/summergeometry.org\/sgi2022\/wp-content\/uploads\/2022\/07\/image-1-1024x761.png 1024w, https:\/\/summergeometry.org\/sgi2022\/wp-content\/uploads\/2022\/07\/image-1-300x223.png 300w, https:\/\/summergeometry.org\/sgi2022\/wp-content\/uploads\/2022\/07\/image-1-768x571.png 768w, https:\/\/summergeometry.org\/sgi2022\/wp-content\/uploads\/2022\/07\/image-1-1536x1141.png 1536w, https:\/\/summergeometry.org\/sgi2022\/wp-content\/uploads\/2022\/07\/image-1-1200x892.png 1200w, https:\/\/summergeometry.org\/sgi2022\/wp-content\/uploads\/2022\/07\/image-1.png 1599w\" sizes=\"auto, (max-width: 610px) 100vw, 610px\" \/><figcaption>An object that is defined by a point cloud, where P2 is more likely to be the dominant plane than P1.<\/figcaption><\/figure>\n<\/div>\n\n\n<h2 class=\"wp-block-heading\">Problem Description<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">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: <\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Part 1: Find the dominant plane \\(P\\) from a given 3D point cloud. This subproblem can be solved by the RANSAC Algorithm.<\/li><li>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.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">The RANSAC Algorithm<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>An Introduction to RANSAC<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The RANSAC algorithm is a learning technique that uses random sampling of observed data to best estimate the parameters of a model.<br>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.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Workflow &amp; Pseudocode<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">RANSAC achieves its goal by repeating the following steps:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Sample a small random subset of data points and treat them as inliers.<\/li><li>Take the potential inliers and compute the model parameters.<\/li><li>Score how many data points support the fitting. Points that fit the model well enough are known as the consensus set.<\/li><li>Improve the model accordingly.<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">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.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The pseudocode of the algorithm is recorded as below:<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: matlabkey; title: ; notranslate\" title=\"\">\nfunction dominant_plane = ransac(PC)\n    n := number of points defined in point cloud PC\n\n    max_iter := max number of iterations\n\n    eps := threshold value to determine data points that are \n           fit well by model (a 3D plane in our case)\n\n    min_good_fit := number of nearby data points required to \n                    assert that a model (a 3D plane in our \n                    case) fits well to data\n\n    iter := current iteration\n\n    best_err := measure of how well a plane fits a set of \n                points. Initialized with a large number\n\n    % store dominant plane information\n    % planes are characterized as &#091;a,b,c,d], where\n    % ax + by + cz + d = 0\n    dominant_plan = zeros(1,4);\n\n    while iter &lt; max_iter\n        maybeInliers := 3 randomly selected values from data \n        maybePlane := a 3D plane fitted to maybeInliers\n        alsoInliers := &#091;] \n        for every point in PC not in maybeInliers\n            if point_to_model_distance &lt; eps\n                add point to alsoInliers\n            end if\n        end for\n\n        if number of points in alsoInliers is &gt; min_good_fit\n            % the model (3D plane) we find is accurate enough\n\n            % this betterModel can be found by solving a least \n            % square problem.\n            betterPlane := a better 3D plane fits to all \n                        points in maybeInliers and alsoInliers\n            err := sum of distances from the points in \n                   maybeInliers and alsoInliers to betterPlane\n            if err &lt; best_err\n                best_err := err\n                dominant_plane := betterPlane\n            end if\n        end if\n\n        iter = iter + 1;\n    end while\nend\n<\/pre><\/div>\n\n\n<h2 class=\"wp-block-heading\">Detect More Planes<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">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&#8217;\\) 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.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The following code provides a more concrete description of the iterative process.<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: plain; title: ; notranslate\" title=\"\">\n% read data from .off file\n&#091;PC, ~] = readOFF(&#039;data\/off\/330.off&#039;);\n\n% A threshold eps is set to decide if a point is on a detected \n% plane. If the distance from a point to a plane is less than \n% this threshold, then we consider the point is on the plane.\neps = 2e-3;\n\nwhile size(PC, 1) &gt; 3\n    % in the implementation of ransac, if the algorithm cannot \n    % detect a plane using the existing points, then the \n    % coefficient of the plane (ax + by + cz + d = 0) is a \n    % zero vector.\n    curr_plane_coeff = ransac(PC);\n    \n    if norm(curr_plane_coeff) == 0\n        % remaining points cannot lead to a meaningful plane.\n        % exit loop and stop algorithm\n        break;\n    end\n\n    % At this point, one may add some code to visualize the \n    % detected plane.\n\n    % return the indices of points that are on the dominant\n    % plane detected by RANSAC algorithm\n    &#091;~, idx] = pts_close_to_plane(PC, curr_plane_coeff, eps);\n\n    % remove the points on the dominant plane.\n    V(idx,:) = &#091;];\nend\n<\/pre><\/div>\n\n\n<h2 class=\"wp-block-heading\">Results<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">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 <a href=\"https:\/\/github.com\/SGI-2022\/plane-edge-detection\">SGI&#8217;s Github<\/a>. 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 <a href=\"https:\/\/segeval.cs.princeton.edu\/public\/VisualizeMain.html#ManualSegmentations\">this<\/a> database.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Successful Detections<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>Mech. Data Model Number<\/td><td>Model Object <\/td><td>RANSAC Plane Detection Result<\/td><\/tr><tr><td>330<\/td><td><img decoding=\"async\" src=\"http:\/\/summergeometry.org\/sgi2022\/wp-content\/uploads\/2022\/07\/330-2.jpg\" alt=\"\" style=\"width: 1200px\"><\/td><td><img decoding=\"async\" src=\"http:\/\/summergeometry.org\/sgi2022\/wp-content\/uploads\/2022\/07\/good_of1-2-1024x768.png\" alt=\"\" style=\"width: 1200px\"><\/td><\/tr><tr><td>331<\/td><td><img decoding=\"async\" src=\"http:\/\/summergeometry.org\/sgi2022\/wp-content\/uploads\/2022\/07\/331-1.jpg\" alt=\"\" style=\"width: 1200px\"><\/td><td><img decoding=\"async\" src=\"http:\/\/summergeometry.org\/sgi2022\/wp-content\/uploads\/2022\/07\/good_of2-1-1024x769.png\" alt=\"\" style=\"width: 1200px\"><\/td><\/tr><\/tbody><\/table><figcaption>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.<\/figcaption><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Unsuccessful Detections<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>Mech. Data Model Number<\/td><td>Model Object <\/td><td>RANSAC Plane Detection Result<\/td><\/tr><tr><td>332<\/td><td><img decoding=\"async\" src=\"http:\/\/summergeometry.org\/sgi2022\/wp-content\/uploads\/2022\/07\/332.jpg\" alt=\"\" style=\"width: 1200px\"><\/td><td><img decoding=\"async\" src=\"http:\/\/summergeometry.org\/sgi2022\/wp-content\/uploads\/2022\/07\/bad_of1-1024x763.png\" alt=\"\" style=\"width: 1200px\"><\/td><\/tr><tr><td>338<\/td><td><img decoding=\"async\" src=\"http:\/\/summergeometry.org\/sgi2022\/wp-content\/uploads\/2022\/07\/338-1.jpg\" alt=\"\" style=\"width: 1200px\"><\/td><td><img decoding=\"async\" src=\"http:\/\/summergeometry.org\/sgi2022\/wp-content\/uploads\/2022\/07\/bad_of2-1024x770.png\" alt=\"\" style=\"width: 1200px\"><\/td><\/tr><\/tbody><\/table><figcaption>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.<\/figcaption><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">Limitations and Future Work<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">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.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Moreover, we may notice that the majority of surfaces in our <a href=\"https:\/\/segeval.cs.princeton.edu\/public\/VisualizeMain.html#ManualSegmentations\">test data<\/a> 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.<\/p>\n\n\n<p><!-- \/wp:post-content --><\/p>","protected":false},"excerpt":{"rendered":"<p>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\u011flu to detect planes and edges from a given point cloud. The main tool we applied to complete this task is the Random Sample Consensus\u00a0(RANSAC)\u00a0algorithm. Definition We define a plane P [&hellip;]<\/p>\n","protected":false},"author":12,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[45],"tags":[109,110],"class_list":["post-278","post","type-post","status-publish","format-standard","hentry","category-research","tag-plane-detection","tag-ransac"],"_links":{"self":[{"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/posts\/278","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/users\/12"}],"replies":[{"embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/comments?post=278"}],"version-history":[{"count":10,"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/posts\/278\/revisions"}],"predecessor-version":[{"id":762,"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/posts\/278\/revisions\/762"}],"wp:attachment":[{"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/media?parent=278"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/categories?post=278"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/tags?post=278"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}