# Indoor Building Reconstruction from Occluded Point Clouds Using Graph-Cut and Ray-Tracing
## 3 Indoor Reconstruction Methodology
### Planar Primitive Extraction  
Once the point cloud is consolidated and for each point \(p_{i}\) its local normal \(n_{i}\) is computed, a planar primitive detection is carried out to identify potential planar room surfaces (walls, roofs, and ceilings). This stage is accomplished by using the segmentation strategy described in [33] (see also Figure 2, part a). In particular, the planar primitive detection is carried out by using a hybrid technique combining RANSAC algorithm [34] and region growing. In this implementation, major attention is paid to the reduction of so called 'bad segmentation' problems. Indeed, spurious results may be due to the fact that points constituting the maximum consensus to RANSAC planes are derived from differentobjects. To reduce the effect of outliers and fine structures such as bumps and craters, the consensus to the RANSAC score function F takes into account the following aspects:  
* the number of points that fall within the \(\varepsilon\)-band around the plane; and
* to ensure that the points inside the band roughly follow the direction of a given plane, only those points inside the band whose normal do not deviate from the normal of the plane more than the defined angle \(\alpha\) are considered as inliers for the guessed plane. More formally, given a candidate shape \(C\) whose fidelity is to be evaluated, \(F\) is defined as follows:  
\[F(C)=\left\lvert P_{\psi}\right\rvert \tag{3}\]  
i.e., \(F(C)\) counts the number of points in \(P_{\psi}\). which is defined as:  
\[P_{\psi}=\left\{p\left\lvert p\in P\wedge\left\lvert d(\psi,p)\right\rvert \right\rvert<\varepsilon\wedge arcos\left[n(p)\cdot n(\psi,p)\right]<\alpha\right\} \tag{4}\]  
where \(d(\psi,p)\) is the signed distance of point \(p\) to the plane \(\psi\), \(n(p)\) is the normal in p and \(n(\psi,p)\) is the normal of \(\psi\) in \(p\)'s projection on \(\psi\). In particular, the signed distance function for a plane is given by:  
\[d(x)<n,x-p>=<n,x>-<n,p> \tag{5}\]  
where \(n,\left\lvert n\right\rvert=1\) is the normal to the plane and \(p\) is an arbitrary point in the plane. The intuitive threshold value \(\varepsilon\) for the Euclidean distance between a point and an estimated plane can be easily found  
Figure 2: Workflow for planar primitive extraction: the two main steps are the segmentation of the point cloud using Random Sample Consensus (RANSAC) (**a**) and the semantic classification of detect surfaces into walls, floor, and ceiling (**b**). by the user according to the instrumental noise and minimum point density for the acquired point clouds. All plane primitives whose supporting points are less than a threshold \(n_{r}\) are directly discarded. The developed strategy tries to minimize spurious objects by refining the detected elements including topology information into the process. Indeed, points belonging to the same object should be sufficiently close while groups of points belonging to different objects should have a gap area. For this reason, a topology measure is introduced in the segmentation process by identifying objects supported by a connected component point data set. Similarly, once all objects are detected, over-segmented parts are combined together considering the topology properties of the extracted planes (i.e., similarity of normal vectors, perpendicular distance between planes and planes' intersection). Clustering of detected elements is performed by using mean shift clustering [35]. Once the point cloud segments have been detected, a first semantic classification is operated to detect surfaces which constitute the 'room box' including walls, floor, and ceiling, see also Figure 2, part b. Indeed, detected segments may also include planar pieces of furniture (e.g., tables) that have to be excluded from the indoor modelling. In Figure 3 some steps related to the contour extraction for one room of the dataset used in the paper (see also Section 3) are shown. In particular, roof and ceiling surfaces can be easily detected looking for horizontal elements.