# Painting Path Planning for a Painting Robot with a RealSense Depth Sensor
## 4 Wall Extraction Algorithm
### Random Sample Consensus Model: RANSAC Algorithm  
Since the statistical filter made huge quality improvements [30], the next step was the obstacle and window detection, which resulted in a wall extraction being painted by the robot. Since the wall mainly differed in depth from the obstacles and the window, it was essentially located in a separate parallel plane from the obstacles and the window. Therefore, the goal was to separate the wall plane from the other planes that were parallel to the wall plane in point cloud data. The most popular planar segmentation algorithms are based on the RANSAC algorithm. RANSAC is a general parameter estimation approach designed to cope with a large proportion of outliers in input data. This is a resampling technique that generates candidate solutions by using the minimum number of observations and data points required to estimate underlying model parameters. Unlike conventional sampling techniques that use as much of the data as possible to obtain an initial solution and then proceed to prune outliers, RANSAC uses the smallest set possible and proceeds to enlarge this set with consistent data points [28; 29]. The RANSAC algorithm process can be described as follows:  
1. Randomly select the minimum number of points required to determine the model parameters, i.e., all free parameters of the model reconstructed from the inliers;
2. Test all data for the parameters of the determined model;
3. Determine how many points from the set fit with a predefined tolerance (this is defined through the probability);
4. If the fraction of the number of inliers over the total number of points in the set exceeds a predefined threshold \(T\), re-estimate the model parameters using the identified inliers and terminate the algorithm;
5. Otherwise, repeat steps 1-4 a maximum of \(N\) times [28; 29]. The number of iterations \(N\) should be high enough to ensure that the probability \(p\) at least has one set of random samples that does not include an outlier [28; 29]. The value for the probability is usually set to 0.99, but this is not mandatory. Let \(a\) represent the probability that any selected datum point is an inlier and \(b=1-a\) the probability of observing an outlier. Then, the \(N\) iterations of the minimum number of points denoted as \(m\) are required, where [28; 29]:  
\[1-p=(1-a^{m})^{N}. \tag{2}\]  
After the reorganization of the previous expression, one can obtain the following [28; 29]:  
\[N=\frac{\log(1-p)}{\log(1-(1-v)^{m})} \tag{3}\]  
The steps of the algorithm are repeated a fixed number of times, each time producing either a model that is rejected because too few points are classified as inliers or a refined model together with a corresponding error measure. In the latter case, the refined model should be kept if its error is lower than the last saved model [28]. An advantage of RANSAC is its ability to perform robust estimation of the model parameters, because it can estimate the parameters with a high degree of accuracy even when a significant number of outliers are present in the data set. A disadvantage of RANSAC is that there is no upper limit on the time it takes to compute the model parameters. When the number of iterations computed is limited, the solution obtained may not be optimal and it may not fit the data well. In this way, RANSAC offers a trade-off; by computing a greater number of iterations, the probability of a reasonable model being produced is increased. Another disadvantage of RANSAC is that it requires the setting of problem-specific thresholds. In addition, RANSAC can only estimate one model for a particular data set. For any single-model approach, when two or more models exist, RANSAC may fail to find either one. This problem can be solved by adding particular conditions; for example, if the largest object of the given geometry is sought in the point cloud data, the assumption is that the wall represents the largest plane in the image. This optimization will overcome the problem related to estimating incorrect model parameters [28; 29].