## 3 Methodology
### Spaces Division and Extraction
#### 3.3.2 Generation of Wall Candidates  
The recognition of wall planes is a prerequisite for space reconstruction. A region growing plane segmentation method is used for plane detection. This algorithm merges points that are close enough in terms of the smoothness constraint. The work of the algorithm is based on the comparison of the angles between points normal. The points \(\{P\}\) are first sorted by their curvature value and the algorithm picks up the point with minimum curvature value and starts the growth of the region, because the point with the minimum curvature is always located in the flat area. In our solution (1) to estimate the normal of each point, the distribution of neighbor points is used and the principal direction is estimated through plane fitting with the least square algorithm; (2) to estimate the curvatures at each point on a discrete 3D point cloud, the distribution of neighbor points are also used. The main steps of this method included using the estimation of normal section lines for normal curvature and the optimization of all these normal curvatures. The principal curvatures and principal directions are estimated through the least square fitting of all normal curvatures related to all neighbor points. The picked point is added to the set called seeds \(\{S_{c}\}\). For each seed point, the algorithm finds neighboring points \(\{B_{c}\}\) and calculates their normals. If the angle between the normal of the seed point and the normal of  
Figure 4: Data of RGB-D sequences. the neighboring point is less than the defined angle threshold \(\theta_{th}\), the current point is added to the current region. After that, each neighbor is tested for the curvature value. If the curvature is less than threshold value \(c_{th}\) then this point is added to the seeds. Meanwhile, current seed is removed from the seeds. The seeds container iteratively grows until it is empty. If the seeds set becomes empty this means that the algorithms has grown the region and there is no new candidate seeds. The process is repeated from the beginning. As shown in Figure 5a, the output of the segmentation method is a set of segmented point cloud clusters. Based on the normal of the recognized planes, the surfaces are organized in the vertical and horizontal directions. Each plane is described by a cluster of points and plane parameters. We distinguish the types of planes by following the classification rules. Wall candidates are derived from vertical surfaces observed in the scans. In the first step, two constraints are used to determine the potential wall surfaces (Figure 5b): (a) The angle between the normal of the plane and the vertical direction is less than the defined normal threshold \(n_{th}\). (b) The maximum of the plane length is larger than the sufficiently large length \(l_{m}\). The plane length means the dimension of a plane, which can be calculated from the envelope of the point cloud. Similarly, the potential floor plane and ceiling plane can be identified based on the normal constraint and the height constraint (Figure 5c). In the second step, all of the horizontal planes are projected to the floor plane and a convexmhull algorithm is used to extract the 2D boundary of the horizontal planes. Figure 5d shows a sample of boundary extraction of horizontal planes. In the third step, to filter out the vertical planes of the interior elements, all of the vertical planes are projected to the floor plane. Therefore, we encounter the problem of determining the inclusion of dozens of point cloud clusters \(\left\{\text{P}\right\}\) in a 2D planar polygon. An interior elements filtering algorithm is used to separate the wall planes from the vertical planes (Algorithm 1). For each point cloud cluster \(P_{i}\), we adopt the RANSAC line fitting method to obtain the optimal fitted line \(L\left|\left\{y=ax+b\right\}\right.\). The RANSAC line fitting method iteratively computes the optimal line by minimizing the deviations \(R^{2}\) of a set of points, which are picked randomly (Equation (1)).