# Painting Path Planning for a Painting Robot with a RealSense Depth Sensor
## 4 Wall Extraction Algorithm
### Detailed Explanation of the Segmentation Algorithm Steps  
In this section, an explanation of the steps in the developed segmentation algorithm are summarized. The segmentation algorithm uses a 3D point cloud (with \(X\), \(Y\), \(Z\) dimensions) and performs the following steps:  
1. Apply a statistical filter [30] on the 3D point cloud to remove outlier points, based on the thresholded standard deviation calculated on neighboring points. The number of neighbors used to analyze for each point is set to 50 and the standard deviation multiplier is set to 3.5. This means that all points with a distance larger than 3.5 standard deviations of the mean distance to the query point will be marked as outliers and removed;
2. Perform the plane clustering step using the iterative RANSAC algorithm, with the \"distance threshold\" set to 0.03 m, which determines how close a point the model must be in order to be considered an inlier. The RANSAC [28; 29] algorithm selects the greatest plane from the remaining point cloud in each iteration, where the points of selected planes are removed before the next iteration. Each plane receives a new cluster id or label (using integers). The cycles are stopped when the remaining cloud is smaller than 0.5% of the original or the maximum iteration number of 20 is reached;
3. Resample the 3D cluster label cloud to a 2D cluster label with a predefined resolution on the plane of the wall. The output is a 2 \(\times\) 2 m rectangle in the plane of the wall, gridded equally in both directions (\(GY\) = height by direction \(Y\), \(GX\) = width by direction \(X\)) at 0.01 m, i.e., 1 cm. This produces a 200 \(\times\) 200 cluster label image (\(C2d\)) along with the depth in the \(Z\) direction (\(Z2d\)). The algorithm first collects all available points (\(X,Y,Z\)) belonging to each 1 \(\times\) 1 cm pixel (\(x,y\)); the set of these pixels is denoted \(S_{x,y}\) (4). Secondly, it selects the closest point to its average \(Z\) distance (\(\overline{Z}\)) from this small set and inherits the cluster label and \(Z\) axis for the selected point (5). \[S_{x,y}=\left\{\forall s:\left|\sqrt{X(s)+Y(s)}-\sqrt{GX(x)+GY(y)}\right|\leq 0.01\sqrt{2}/2\right\}\] (4) \[C2d(x,y)=C(i^{*}),Z2d(x,y)=X(i^{*}),\;i^{*}=\underset{i\in S_{x,y}}{\text{ argmin}}\Big{(}\left|Z(i)-\overline{Z}_{S_{x,y}}\right|\Big{)}\] (5) (4) Disconnect regions within clusters based on two criteria:1. Separate regions based on Euclidean distance clustering with a distance tolerance of 0.08 m [44]. This step uses the cluster method and k-dimensional tree search method to separate clusters [45; 46; 47; 48]. K-d trees are very useful for range and nearest neighbor searches, which are the best for separating possible regions. This process also takes into account the depth information (\(z\) axis); 2. Separate regions based on adjacent criteria in the 2D plane (if the cluster consists of more than one region or when the region is a subset containing only adjacent pixels). The algorithm checks the adjacency of pixels within one cluster, and if more than one is region found, these are separated and labeled differently. This process does not take into account the depth information (\(z\) axis); 3. Erase small-area clusters that are highly likely to be noise or outliers. The algorithm first calculates the area for each cluster and selects \"tiny\" clusters smaller than 0.005 m\({}^{2}\) (50 cm\({}^{2}\)). The pixels of tiny clusters inherit cluster labels from the nearest neighbor pixels belonging to non-tiny clusters. The nearest neighbor criteria are checked on the 2D plane of the wall (\(X/Y\) plane) independently from the depth (\(z\) axis). This process filters out any remaining bad pixels, i.e., any clusters with only one pixel; 4. Sort the cluster labels by area, whereby each of the remaining clusters get a new sorted label, with the first belonging to the largest area. Typically, the largest cluster is the wall, but this is checked using the expected wall distance (in the \(Z\) direction) too.