Structural 3D Reconstruction of Indoor Space for 5G Signal Simulation with Mobile Laser Scanning Point Clouds

Abstract

3D modelling of indoor environment is essential in smart city applications such as building information modelling (BIM), spatial location application, energy consumption estimation, and signal simulation, etc. Fast and stable reconstruction of 3D models from point clouds has already attracted considerable research interest. However, in the complex indoor environment, automated reconstruction of detailed 3D models still remains a serious challenge. To address these issues, this paper presents a novel method that couples linear structures with three-dimensional geometric surfaces to automatically reconstruct 3D models using point cloud data from mobile laser scanning. In our proposed approach, a fully automatic room segmentation is performed on the unstructured point clouds via multi-label graph cuts with semantic constraints, which can overcome the over-segmentation in the long corridor. Then, the horizontal slices of point clouds with individual room are projected onto the plane to form a binary image, which is followed by line extraction and regularization to generate floorplan lines. The 3D structured models are reconstructed by multi-label graph cuts, which is designed to combine segmented room, line and surface elements as semantic constraints. Finally, this paper proposed a novel application that 5G signal simulation based on the output structural model to aim at determining the optimal location of 5G small base station in a large-scale indoor scene for the future. Four datasets collected using handheld and backpack laser scanning systems in different locations were used to evaluate the proposed method. The results indicate our proposed methodology provides an accurate and efficient reconstruction of detailed structured models from complex indoor scenes.

1. Introduction

Three-dimensional (3D) reconstruction of the indoor environment has received significant attention due to the development of smart cities. However, the automation of generating high-quality models remains to be a challenging issue due to the complexities of the indoor environment. The industry foundation classes (IFC) defines building information modelling (BIM) as having rich semantic information, 3D structural information, spatial relationships, and interoperable geometry [1]. BIM has been used in a number of applications, such as indoor navigation [2,3], space management [4,5], energy simulation [6] and real-time emergency response [7,8]. Primary indoor locations utilizing BIM include indoor offices, parking lots, and commercial establishments, which are commonly comprised of basic elements, such as the ceilings, floors, walls, windows, doors, and pillars, and not objects, such as furniture. 3D Indoor models are often generated manually by creating geometric representations using point cloud data and commercial software. This often requires significant investment in time and in training personnel [9]. To accelerate the efficiency of data acquisition and improve the automation of reconstructed models, various laser scanning technologies and automated modelling methods have been developed. Over the past few years, terrestrial laser scanning (TLS) has been used to obtain high-quality data in the indoor scene, but often suffers from low mapping efficiency due to laborious scan station resetting, protracted registration procedures, and high costs. Thus, its application has excluded large-scale indoor data acquisition. RGBD panorama is acquired by a camera and a depth sensor [10], with added advantages of affordability and convenience of use. However, the image distorted and noisy that lead to difficultly build accurate models in large scale scenes. With the development of the simultaneous localization and mapping (SLAM), various types of mobile laser scanning (MLS) devices have been used for data acquisition, such as handheld, backpack, push-cart and robot mobile laser scanners. MLS systems can obtain point clouds by moving from different spaces and measure from different locations. The easy-to-use and affordable indoor MLS systems are mostly used for data acquisition of large indoor scenes [11]. While MLS ensures good coverage for indoor environment mapping, the data can be affected by a number of factors (e.g., moving objects, multiple reflections, and dynamic occlusions) resulting in quality losses, which present serious challenges in model reconstruction.

Recently, numerous studies have focused on modelling the indoor environment. For example, some research [10,12,13,14,15,16,17,18,19,20,21,22] segmented the unstructured points clouds into individual rooms to provide a prior knowledge in building the indoor model. The over-segmentation often occurs in the spatial partition of long corridors [13,14], creating a substantial challenge when segmenting long corridors. Neoteric methods [9,15,22,23,24,25,26,27,28,29,30,31] have focused on extracting piecewise planar surfaces to construct the model. Although the results of room segmentation have been satisfactory, indoor models still are difficult to accurately reconstruct because of high levels of occlusion and noisy point cloud data, while still requiring interaction [22]. Large scale scene modelling based on surface elements has significant computational challenges. In order to increase computational efficiency, many line-based reconstructed methods have been proposed [32,33,34,35,36,37,38,39,40]. Their results have shown that line-based methods are efficient and effective, which can produce accurate and complete line segments. However, the reconstructed models are only represented in vector line structure without room semantic information, even when these elements are unconnected. Furthermore, a satisfactory solution for indoor interior reconstruction has not been developed due to the complexity of the indoor environment and unfiltered data noise.

In this study, a novel method is developed that combines line structures and 3D surface geometry to automatically build a 3D indoor model with detailed structural and semantic information using MLS point clouds. A fully automatic room segmentation was performed on unstructured point clouds via multi-label graph cuts, which can solve the over-segmentation in long corridors. Point cloud slices of individual rooms are transformed as a binary image, from which extraction, and regularization of line elements, aimed at improving the computational efficiency and structural accuracy. 3D structured models were reconstructed using multi-label graph cuts, and room segmentation and lines were used as semantic and structural constraints of 2D floorplan, with surfaces providing 3D geometric information. Finally, an innovative approach was employed using 5G signal simulation based on the reconstructed model, where the basic structural elements (e.g., windows, doors, pillars, walls, ceilings, and floors) have a critical effect on the signal transmission.

This study offers two major contributions. First, room segmentation was employed to semantically label the unstructured point clouds using multi-label graph cuts with semantic constraints of openings that can overcome the over-segmentation in corridors. Point cloud slices of individual rooms are transformed into images, which are then extracted and regularized into the floorplan lines. This innovation contributes to improving the efficiency and precision of extracting structural elements. Second, 3D structured models were reconstructed using multi-label graph cuts with room segmentation and 2D floorplan lines, and with 3D surfaces used as constraints. The resulting structured models provided room adjacency relationship, geometric characteristics, and semantic information, which are then applied to the signal simulation to provide the optimal location of the 5G small base station in indoor environment for future.

2. Related Work

In the last decade, various approaches designed for indoor modelling using 3D laser scanning have been developed, which mostly consisted of three fundamental steps: (1) room segmentation, (2) reconstruction of indoor space, and (3) indoor model application.

2.1. Room Segmentation

Room segmentation is key semantic information used in model reconstruction. Ikehata et al. [10] proposed the segmentation method of rooms, which repeated k-medoids algorithm to cluster sub-sampled pixels, the distance metric for clustering is based on a binary visibility vector of scanning center. Mura et al. [12] presented an approach that established a global affinity measure between cells by diffusion maps, and partitioned rooms by clustering 2D cells iteratively. Ochmann et al. [13] proposed a method that segmented indoor point clouds into individual rooms by the visibility-based and class-conditional probabilities, which based on initial knowledge of scans and scan positions; however, the over-segmentation occurs in long corridors. Turner et al. [14] proposed an approach that triangulated a 2D sampling of wall positions and separated these triangles into interior and exterior domains. The room segmentation can be obtained by Graph-cut in the triangulated map. However, these methods of room partition are limited to depend on TLS the scanning position, but not for MLS point clouds. Wang et al. [17] employed the hierarchical clustering method for partitioning rooms, which established diffusion maps to merge the over-segmented spaces. The method uses scan trajectories instead of scanner positions. Díaz-Vilariño et al. [18] proposed a method that used the timestamp information to determine the visible point clouds of each trajectory point and constructed the energy minimization function for global spatial optimization to complete individual room segmentation. Their method relies heavily on data quality and integrity and has been shown effective in simple scenarios. Li et al. [19] proposed a comprehensive segmentation method that is created by a morphological erosion and connectivity analysis methods on the floor space, which overcomes over-segmentation in long corridors. Similarly, Ochmann et al. [22] proposed a fully automatic room segmentation that performed visibility tests by the ray casting between point patches on surfaces to build visibility graph, and then the nodes of this graph are clustered by the Markov Clustering method [21].

2.2. Reconstruction of Indoor Space

Current methods for the reconstruction of indoor spaces are mainly based on the extraction of surfaces [9,15,22,23,24,25,26,27,28,29,30,31] and lines [32,33,34,35,36,37,38,39,40].

(1) Surface-Based Reconstruction

The accuracy of reconstruction models mostly depends on the extraction of surfaces. Bassier and Vergauwen [9] proposed an innovative approach to segment walls using the Conditional Random Field and concluded that the generated wall clusters were better than traditional region growing. Other researchers have also extracted unconnected planes from 3D point clouds [23,24], but only enabled visualization and excluded the spatial topological relationship. Monszpart et al. [25] proposed an effective approach to extract Regular Arrangements of Planes (RAP) from unstructured point clouds in rebuilding man-made scenes. However, the method requires long computing time for the reconstruction of large scenes. Awrangjeb et al. [26] proposed a novel 3D roof reconstruction technique that constructs an adjacency matrix to define the topological relationships among the detected roof planes, in addition, used the generated building models to detect 3D change in buildings. Xiao and Furukawa [27] employed constructive solid geometry (CSG) operations to generate volumetric wall model, which focused on the large-scale reconstruction without semantic information. To overcome this deficiency, Ochmann et al. [15] extracted the piece planar surfaces by the RANSAC approach [28], constructed partitions based on the wall surfaces, utilized the global optimization to reconstruct wall elements, and then finally built the volumetric model of single room by extruding the walls. However, the thickness of model walls was assigned a fixed threshold that led to significant errors. Mura et al. [29] extracted the permanent components used in constructing adjacent relations and partitions of 3D polyhedral cells. The final general three-dimensional interior model was reconstructed using multi-label to optimize cell selection; however, this method was only applied to small-scale scenes. Ochmann et al. [22] extracted wall candidates and formulated the optimization method to arrange volumetric wall entities to build the structural model. Reconstructing the model presents latent difficulties due to occlusion and clutter point clouds in the indoor environment. While this approach can reshape the model manually, its main limitation includes slanted walls, ceilings and floors, and detailed pillar reconstruction.

(2) Line-Based Reconstruction

Many researchers have also studied indoor reconstruction based on lines. Lin et al. [32] proposed a method where line segments can accurately be extracted from unorganized point clouds. However, the line elements remained completely isolated and devoid of information about topological relations. Similarly, Xia and Wang [33], Lu et al. [34] extracted unstructured line elements from point clouds. Liu et al. [35] proposed the FloorNet where a deep neural architecture can automatically reconstruct the floorplan from RGBD videos with camera poses. Extracting initial line structures from labeled points, Wang et al. [37] proposed a conditional Generative Adversarial Nets (cGAN) deep learning method to optimize the detected lines to rebuild line frameworks with structural representation in the cluttered indoor environment. Bauchet et al. [38] proposed an approach that extract flexibility on polygon shape, which better recover geometric patterns but still lacks topological information. Sui et al. [39] introduced an automatic method for extracting floorplans from slices that correct both normal vector and position to obtain accurate boundaries, which are then used in propagating to the other floors. However, the reconstructed models are only applicable for visualization and cannot be used for geometric manipulation. For the underground infrastructure, Novakovic et al. [40] extracted the 2D profile from the point cloud data of tunnel, built the spatial parameter model and simulated cargo tunnel pass.

2.3. Indoor Model Application

Previous studies have investigated the various applications of the BIM model. Díaz-Vilariño et al. [3] proposed an approach based on the BIM model that determined the optimal scan positions in planning the shortest route for an automatic robot visit. Boyes et al. [4] proposed the combined use of BIM and GIS for spatial data management (e.g., location queries). Tomasi et al. [5] introduced the use of the BIM model in computing for the optimal coverage of Wireless sensor networks (WSNs). Rafiee et al. [6] applied the methods transforming BIM model with geometric and semantic information into geo-referenced vector model for view and shadow analyses, which are useful in urban spatial planning. Tang and Kim [7] introduced a dynamic fire simulation based on the Fire Dynamics Simulator (FDS) and BIM model, which included simulation control, fire and smoke modelling, and occupant evacuation in the indoor environment. Boguslawski et al. [8] introduced that the route planning of indoor fire emergency based on BIM model. Thus, the indoor model reconstruction has become extremely valuable in urban development.

2.4. Summary

These surface-based reconstruction methods [9,15,22,23,24,25,26,27,28,29,30,31] mostly depend on the accuracy of surface extraction. In complex indoor scenes, the efficiency of surface extraction is low and contains excessive noise. Line-based reconstruction methods [32,33,34,35,36,37,38,39,40] can be used to completely represent the geometric information; however, these do not contain semantic information and adjacency relationship of rooms, leaving the reconstructed models to be useful only for visualization. In order to address the above shortcomings, we propose an innovative approach combining the rich structure of 2D lines with 3D geometry of surfaces to automatically build 3D structured models using MLS point cloud data. The output structural model presents novel applications in signal simulation, including the capability of providing optimal locations for 5G small base stations in the future.

3. Methodology

The complete flowchart is illustrated in Figure 1, showing the four key steps in the proposed methodology: room segmentation, floorplan extraction and regularization, structural model reconstruction, and 5G signal simulation. For the room segmentation, the door position and the simulated visible point clouds of sample trajectories are used to establish the initial space, while the global optimization of the indoor space is solved by the energy minimization function via multi-label graph cuts. For the floor extraction and regularization, the line elements are processed, which included the following steps: (1) the 3D point cloud slices are transformed into a binary image, and the line elements are extracted from the image; (2) the correction of line elements are based on global optimization; and, (3) similar lines are clustered to remove redundant line elements. The three-dimensional structural models are reconstructed via multi-label graph cuts, with room segmentation, 2D line elements, and 3D surfaces as semantic constraints. Finally, the signal intensity of 5G small base station is simulated using the structural models in the indoor environment.

3.1. Room Segmentation

The input of our approach, consists of unstructured point clouds and trajectories acquired from the mobile laser scanner system. In the indoor scene, every room has at least one door, representing a transition from one indoor space to another. For room segmentation, the position of detected doors and the simulated visible point clouds of sample trajectories are used to establish the initial space, while the global optimization of the indoor space is solved using the energy minimization function via multi-label graph cuts.

3.1.1. Detection of Openings

Since openings are generally attached to wall surfaces and as holes in the point clouds of wall surfaces, the extraction of doors and windows is based on the hierarchical relationship of plane-contour. The surfaces are first extracted based on the previous plane segmentation [31] (see wall surfaces illustrated in Figure 2a). The 3D point clouds of wall surfaces are projected into a 2D plane using the following conversion:

$$\begin{array}{l}{X}_v=\frac{(0,0,1)\times (n_x,n_y,n_z)}{\left|(0,0,1)\times (n_x,n_y,n_z)\right|}\hspace{1em}{Y}_v=\frac{X_d\times (n_x,n_y,n_z)}{\left|X_d\times (n_x,n_y,n_z)\right|}\hspace{1em}{Z}_v={(n_x,n_y,n_z)}^T\\ T=(X_v,Y_v,Z_v)\hspace{1em}(x,y,z)·T=(x_2,y_2,z_2)\end{array}$$

(1)

where $(n_x,n_y,n_z)$ are normal vectors of 3D plane; $X_v,Y_v,Z_v$ are vectors of the 3D plane coordinate axis that constituted the transformation matrix $T$; $(x,y,z)$ are coordinates of 3D plane; $(x_2,y_2)$ are the 2D coordinates of the transformed plane; and, $z_2$ is depth.

The 2D projected points are converted into a binary image, as shown in Figure 2b. For every binary image, morphological corrosion transformation is used to remove noise. The find-contour method [41] is then applied during the extraction of plane outline to get sets of contour points, such that every contour is independent. Afterward, the bounding boxes of contours are calculated. Based on the size of the bounding box, the contours are categorized into doors, windows, invalid. The invalid consists of holes resulting from occlusion and undetected openings. In our study, the template match method, which is implemented in the OpenCV library [42], is applied to extract undetected openings. (In Figure 2c, an extracted opening as the template that encircled in red; in Figure 2d, the identified doors are shaded in green). Compared with the previous method [31], the extracted opening boundaries are visually more defined. As for the extraction of pillars, the technique is similar to extracting openings.

3.1.2. Room-Space Segmentation

The segmentation of rooms is accomplished by first simulating the visible point clouds from the MLS trajectory based on the line-of-sight. The position of doors is then used to limit the range of visible point clouds and to partition the trajectory segments in establishing the initial space. Finally, similar visible points between scanning trajectories are automatically clustering using global optimization based on multi-label graph cuts.

Inspired by the previous room segmentation [31], the visibility analysis is that simulating the visible point clouds along sample trajectory of the MLS and the grid cells’ center point based on the line-of-sight. Instead of being dependent on segmented planes, the original point clouds are divided into uniform grids and the sampled point is one of every 200 trajectory points from the original trajectories. Figure 3 shows the flowchart, which illustrates the intersections between rays and all the other cells found along the line-of-sight. The points in the target cell are only visible if the point number of the cell where the ray passes through is within the threshold. Figure 4a shows the simulated visible point clouds of the three sample trajectories, some points are collected by different rooms due to the openings. Thus, the position of doors can be used to separate different spaces by limiting the range of visible points, as shown in Figure 4b.

The location of doors plays an important role in room segmentation. In our proposed methodology, the location of doors is used to subdivide the trajectories into initialized subspaces. Figure 5b illustrates how the trajectories are segmented by each door. Each trajectory segment corresponds to only one room, but not all rooms are depicted by a single segment. Trajectories in the same space have similar visible point clouds, so the individual room can be segmented, which regard as automatic clustering of similar visible point clouds by the global optimized method.

The global optimization of indoor spaces is performed by solving an energy minimization function via multi-label graph cuts. The optimization function consists of a unary and smooth term, which is expressed as Equation (2), where weight parameters $\alpha ,\gamma$ are used in balancing the data term and the smooth term in the energy function. The initial trajectory is first segmented using the doors as positional constraints, then, its corresponding clustering spaces are determined by minimizing a predefined energy function.

$$\begin{array}{l}E=\min (E_{\mathrm{D}}+E_S)\\ E(l)=\min ({\displaystyle \sum _{v\in V}\alpha ·D_v(l_v)}+{\displaystyle \sum _{(v,w)\in E}\gamma ·B_{v,w}(l_v,l_w)})\end{array}$$

(2)

Data term. $E_{\mathrm{D}}$ is the sum of unary functions; and, $D_v(l_v)$ is the difference in visual area between trajectory $i$ and every trajectory segment ${\varphi }_v$, which is expressed in Equation (3):

$$\begin{array}{l}{r}_o=\frac{o_i\cap G_{{\varphi }_v}}{G_{{\varphi }_v}}\\ D_v(l_v)=I_v-r_o\end{array}$$

(3)

where $l_v$ is the label for the trajectory $i$ belonging to trajectory segment ${\varphi }_v$; $I_v$ is the ideal value for the label $l_v$; $r_o$ is the ratio of the overlapping area between trajectory $i$ and each trajectory segment ${\varphi }_v$; $o_i$ is the visual area of trajectory $i$, and $G_{{\varphi }_v}$ is the visual area of trajectory segment ${\varphi }_v$; $\left\{{\varphi }_1,\dots {\varphi }_v\dots {\varphi }_{\theta }\right\}$ are the set of initial trajectory segments, where ${\varphi }_v$, $v\in \left\{1,\dots ,\theta \right\}$. Lower $D_v(l_v)$ values mean less penalty when assigning the sample trajectory point $i$ to the trajectory segment ${\varphi }_v$. The overlap between the visible area of two trajectory points is calculated using the number of the same index for visible cells.

Smoothness term.$E_S$ is the sum of binary functions $B_{v,w}(l_v,l_w)$ and is used to regularize label by penalizing the assignment of different labels to adjacent trajectories, as defined by Equation (4):

$$\begin{array}{l}{B}_{v,w}(l_v,l_w)=\{\begin{array}{ll}(\frac{1}{2}{e}^{(-\frac{dis(i,j)}{\Delta d})}+\frac{1}{2}{e}^{-(1-o_{(i,j)})})& if (l_v\ne l_w)\\ 0& otherwise\end{array}\\ o_{(i,j)}=\frac{1}{2}(\frac{o_i\cap o_j}{o_i}+\frac{o_i\cap o_j}{o_j})\end{array}$$

(4)

where $i$ is the sampled trajectory point; and let $i$ be as center point and get its k-nearest neighbor (KNN) trajectory points, $j\in K$; $o_i,o_j$ are visible area of trajectory points $i$ and $j$, respectively; $dis(i,j)$ is the distance between trajectory points $i$ and $j$, $O_{(i,j)}$ is the overlapping ratio of visual area of trajectory points $i$ and $j$; $\Delta d$ is a distance threshold. The smoothness term indicates the penalty between adjacent trajectory points. If a pair of neighboring trajectory points belong to the same space, the smooth cost between them is 0; otherwise, this value is closer to 1 as the overlapping ratio is greater and the distance of the adjacent trajectory points is smaller. The smooth term can reduce the number of redundant spaces, thus solving the over-segmentation problem in long corridors for complex indoor environment. Again, the global optimization of the indoor space is solved by an energy minimization function via multi-label graph cuts [43,44,45] to automatically cluster similar visible point clouds. The room segmentation results are shown in Figure 6b.

3.2. Floorplan Extraction and Regularization

These methods [15,22,27,29] extracted mainly the piecewise planar surfaces to reconstruct indoor models. However, due to the complexity of the indoor environment, the quality of point clouds can suffer significantly from a number of factors such as moving objects, multiple reflections, and occlusions. Building high-accuracy indoor model automatically becomes complex, which may require interaction. Since lines are commonly used in expressing key information in modelling, line-based reconstruction ensures the efficiency and precision of the model. In this study, our method combines lines and surfaces in building the 3D structured model of the indoor scene. The extraction and regularization of lines are conducted prior to the reconstruction of the vector model with more detailed features.

3.2.1. Floorplan Line Extraction

The horizontal slices of the point clouds with individual room are determined based on certain heights from the ceiling. Connectivity analysis is performed to filter outliers from the point cloud slicing (results are shown in Figure 7a). Line segments are then extracted based on the image gradient, which recovers detailed structural features and greatly improves computational efficiency. The point clouds of horizontal slices are converted into a binary image, as shown in Figure 7b, with a pixel size of 5 cm. We use the Line-Segment-Detector (LSD) [46] method to extract lines from the binary image, which region-growing method is applied to the image gradient clustering. The larger gradient is used as the seed point, while the given angle threshold is used as the growing condition. The line extraction results are shown in Figure 7c with the line elements of different rooms presented in varying colors.

3.2.2. Line Global Optimization

Figure 7c shows that the extracted initial lines are able to preserve detailed features. However, due to laser point clouds with information loss, holes, noise, etc., the extracted results mainly have four kinds of errors: angle deviation, distance deviation, excessive redundancy, and incomplete boundaries. Inspired the method [38], the angle and distance deviations of the line-segments are corrected by global optimization, as shown in Figure 8a,b. The problem is expressed as an energy function, as shown in Equation (5), which is minimized by g2o that called a general framework for graph optimization [47]. The weight parameter $\lambda$ is used for balancing the different terms.

$$E(x)=(1-\lambda )·D(x)+\lambda ·B(x)$$

(5)

For angle correction, the data term $D(x)$ is used to correct the angle deviations corresponding to the initial orientation, as expressed by:

$$D(x)=\frac{1}{n}{\displaystyle \sum _{i=1}^n{\left(\frac{x_i}{{\theta }_{\max }}\right)}^2}$$

(6)

where the correction value $x_i\in \left[-{\theta }_{\max },{\theta }_{\max }\right]$ can be added to the initial orientation of the line $i$ with respect to its center; clockwise direction indicates positive value; ${\theta }_{\max }$ is the angle threshold adjustable based on the quality of point clouds; and $n$ is the number of extracted initial lines.

The smooth term $B(x)$ is used to correct the geometric relationship of the adjacent lines, as expressed by:

$$B(x)=\frac{1}{{\displaystyle {\sum }_{i=1}^n{\displaystyle {\sum }_{j=1}^k{u}_{ij}}}}{\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^k{u}_{ij}\frac{\left|{\theta }_{ij}-(\left|x_j\right|+\left|x_i\right|)\right|}{4{\theta }_{\max }}}}$$

(7)

$$\begin{array}{l}{\theta }_{ij}=\{\begin{array}{ll}{\theta }_{ij}\pm 2\pi & if (\frac{7}{4}\pi \le \left|{\theta }_{ij}\right|\le 2\pi )\\ {\theta }_{ij}\pm \frac{3}{2}\pi & if (\frac{5}{4}\pi \le \left|{\theta }_{ij}\right|\le \frac{7}{4}\pi )\\ {\theta }_{ij}\pm \pi & if (\frac{3}{4}\pi \le \left|{\theta }_{ij}\right|\le \frac{5}{4}\pi )\\ {\theta }_{ij}\pm \frac{1}{2}\pi & if (\frac{1}{4}\pi \le \left|{\theta }_{ij}\right|\le \frac{3}{4}\pi )\\ {\theta }_{ij}& otherwise\end{array}\\ u_{ij}=\{\begin{array}{ll}1& if (\left|{\theta }_{ij}\right|<2{\theta }_{\max })\\ 0& otherwise\end{array}\end{array}$$

(8)

where ${\theta }_{ij}$ is the angle between adjacent lines $s_i,s_j$ (such that ${\theta }_{ij}\in [-2\pi ,2\pi ]$). The adjacent lines are encouraged which are nearly-parallel or nearly-orthogonal or nearly-themselves. The angle ${\theta }_{ij}$ is adjusted to close to the coordinate axis, as expressed by Equation (8). In addition, the following conditions are satisfied: if $\left|{\theta }_{ij}\right|<2\ast {\theta }_{\max }$, $u_{ij}=1$, otherwise $u_{ij}=0$. $k$ is the number of lines adjacent to line $s_i$; which can be obtained that $s_i$ is as the center and search its KNN from all other lines. The distance correction is similar to the angle, as expressed by:

$$\begin{array}{l}D(x)=\frac{1}{n}{\displaystyle \sum _{i=1}^n{\left(\frac{x_i}{d_{\max }}\right)}^2}\\ B(x)=\frac{1}{{\displaystyle {\sum }_{i=1}^n{\displaystyle {\sum }_{j=1}^k{u}_{ij}}}}{\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^k{u}_{ij}\frac{\left|d_{ij}-(\left|x_j\right|+\left|x_i\right|)\right|}{4d_{\max }}}}\\ u_{ij}=\{\begin{array}{ll}1& if (\left|d_{ij}\right|<2d_{\max })\\ 0& otherwise\end{array}\end{array}$$

(9)

where $x_i\in \left[-d_{\max },d_{\max }\right]$ is added on the line $s_i$ along its normal direction; and, $d_{ij}$ is the distance between adjacent parallel lines $s_i,s_j$. If $\left|d_{ij}\right|<2\ast d_{\max }$, then $u_{ij}=1$, otherwise $u_{ij}=0$. The global optimization results for the lines are shown in Figure 8c, which contains the correct geometric information.

3.2.3. Clustering Similar Lines

After optimization, the whole scene consists of a set of small lines with different labels requiring further refinement. Inspired by [46], the following region growing algorithm incrementally merges adjacent basic units with similar features into a set of main lines. The number of line similar with each line is estimated, which is qualified to meet the user-defined angle and distance thresholds between lines. Seed lines with more similar line number are tested first as they are more likely to belong to the mainline. Each line region starts primarily with just a seed line. The orientation and distance of other lines from the seed line are estimated whether they meet the certain threshold, given by:

$$\begin{array}{ll}\Delta D=s_{nx}·x_m+s_{ny}·y_m+s_{offset}& \Delta D<d_{threshold}\\ \Delta A=a\cos (\frac{s_n·s_{on}}{\left|s_n\right|\left|s_{on}\right|})& \Delta {A<a}_{threshold}\end{array}$$

(10)

where $(s_{nx},s_{ny},s_{offset})$ are the seed line parameters, $s_n$ is its normal vector; $(x_m,y_m)$ is the midpoint coordinate of other line, $s_{on}$ is its normal vector. The lines that meet the threshold are then added to the seed line.

Lastly, the main lines consist of line groups. A mainline is determined at least by a starting point, an endpoint, an offset, and a normal vector. The normal vector of the seed line and the mean offset serve as the final parameters for the mainline. The line groups with different labels are then projected onto the mainline to find the endpoints and create the bounding boxes (see Figure 9a). The final main lines are presented in Figure 9b.

3.3. Structured Model Reconstruction

3.3.1. Model Reconstruction

Figure 9b shows the line segments are incomplete due to missing point clouds. The lines are extended to form the enclosed floorplans (shown in green lines in Figure 10). Lines in the enclosed floorplans have topology and the point clouds in the segmented rooms have semantic information. Thus, the line segments and point clouds with individual rooms are can be used as constraint conditions in building the two-dimensional floorplan using multi-label graph cuts. The labelled Point clouds are projected on the 2D polygon floorplan is shown in Figure 10. Each cell is assigned a label from set $\left\{l_1,\dots ,l_{Nrooms},l_{out}\right\}$, which includes one label for each room plus an additional label $l_{out}$ for the outer space. Each line cell is assigned a label from the initial $\left\{l_1,\dots ,l_{Nrooms},l_{out}\right\}$. The labelled line segments are used to segregate cells from adjacent region, of which cell labels should be different. Our approach differs from Ochmann’s work [15,22] such that the line segments are projected directly on the floorplan and divided into 2D line cells to improve the accuracy and efficiency of the model. With the approach expressed as an energy minimization function [31], the 2D polygons and lines are globally optimized to build the floorplan model, which are then extended to the estimated the floor and ceiling heights from segmented surfaces to build 3D room models. Figure 11 shows that the reconstructed model can better retain the details of indoor scene.

3.3.2. Room Structured Connection

The above reconstructed models are expressing room semantic and geometric information, but still lacks room topological connection types. In the last step, the room’s structural connection is recreated. For indoor scenes, the space created by a door is a type of connection space. Thus, the door’s position is used to analyze the room connection types. In this study, the doors were extracted based on the segmented surfaces, and the model reconstruction is based on the horizontal slice of the segmented rooms. To correct some distance errors introduced during reconstruction, the detected door are attached to the walls if the following conditions must be satisfied: (a) the door must be parallel to a wall; (b) the distance along the normal should be less than the threshold of 0.2 m; and, (c) the door completely overlaps with the walls. The door connecting adjacent rooms is a subspace with thickness. Figure 12 shows the structured model with the reconstituted doors.

Every room is associated with geometry elements that ceiling, floor, walls, doors and windows. In our work, openings between neighboring rooms are detected to obtain a room connectivity graph, in addition, for each wall of the room, we search a matching, approximately parallel surface with opposing normal orientation within user-defined distance and angle thresholds. Each matching pair of wall surfaces forms adjacent rooms. According to these rules, a building’s room topology graph is constructed. If a space that is connected to more than three rooms and has many doors that is labeled a corridor. The rooms with topological relationship are shown in Figure 13, which can be applied to a service application in an indoor environment.

3.3.3. G Signal Intensity Simulation

In the 5G era, 5G devices have design features that support higher signal frequency and the shorter wavelength to generate faster transmission speed; however, this leads to diminished capability of penetrating through walls [48]. With 80% of today’s businesses occurring indoors, setting up large-scale small base stations to increase signal intensity has become a common occurrence. However, due to the complexities of the indoor environment (e.g., occlusion problems), network construction has become a challenging undertaking.

In this study, the output structured models have three properties: semantic, geometric, and connection types. These models are made up of basic building elements, such as the ceilings, floors, walls, windows, doors and pillars, which have direct effect on signal propagation in the real world. Thus, the structured model can become an important tool in analyzing 5G signal simulation.

According to the standard of 3GPP [49], the non-line-of-sight signal propagation loss model of indoor space is expressed:

$$L_{fs,dB}=32.4+31.9·\lg (d_p)+20·\lg (f)$$

(11)

where $L_{fs,dB}$ is the propagation loss; $d_p$ is the max propagation distance $(100m)$; and, $f$ is frequency of the electromagnetic wave $(0.5GHz-100GHz)$. The formula suggests that greater propagation loss occurs with larger wave frequency or with longer propagation distance. In an ideal indoor environment (no attenuation losses), when the frequency remains constant, the propagation loss increases with increasing distance, which then decreases the power received by the receiver.

The indoor environment is comprised of open cubicles, walled offices, open areas, corridors, etc. In this study, the 5G base stations were assumed to be located at the height of 2 m, near the ceilings. The ray-tracing solution is adopted to provide a detailed multipath and accurately simulate the spatial variation. Figure 14 illustrates the principle of single signal propagation, where the intensity multipath results from the reflection of walls and transmission of openings.

In our experiment, the signal propagation intensity was simulated in the structured model. Three base stations were mounted at the corridor and a room, as shown in Figure 15a. Every base station was assumed to be at the center of a sphere, randomly launching 150 rays. Using a frequency of 100 GHz, the intensity was calculated within a range of 100 m using the signal propagation loss model (see Figure 15b). The profile provided an effective means of measuring the changes of signal intensity and became a useful tool in visualization and inspection of 3D interpolation results. Therefore, the interpolation method of Inverse Distance Weight method (IDW) used in simulating the intensity profile can be calculated with:

$$P={\displaystyle \sum _{i=1}^n{\epsilon }_i}{P}_i\hspace{1em}\hspace{1em}{\epsilon }_i=\frac{\frac{1}{{(D_i)}^m}}{{\displaystyle \sum _{i=1}^n\frac{1}{{(D_i)}^m}}}$$

(12)

where the intensity value $P$ of the interpolation point is defined as the weighted average value of known point intensity value $P_i$; $D_i$ is the Euclidean distance from interpolation point to its nearest sampling point; and, $m$ is the power exponent. Finally, the profile result is shown in Figure 15c.

4. Experiment

4.1. Datasets

The proposed method was tested on four datasets acquired by MLS in different indoor scenes, as shown in Figure 16.

Table 1. Technical specifications of the laser scanning system.

Sensor	ZEB REVO	BLS (Shenzhen University)	BLS (Xiamen University)
Max range	30 m	100 m	100 m
Speed (points/sec)	43 × 103	300 × 103	300 × 103
Horizontal Angular Resolution	0.625°	0.1–0.4°	0.1–0.4°
Vertical Angular Resolution	1.8°	2.0°	2.0°
Angular FOV	270 × 360°	30 × 360°	2 × 30 × 360°

lists the technical specifications of system, and the

Table 2. Specifications of point clouds.

Dataset	Benchmark Data	Corridor (Shenzhen University)	Corridor (Xiamen University)	Parking lot (Xiamen University)
Number of points	21.560.263	1.980.911	2.098.634	7.683.766
Clutter	Low	High	Low	High

details the specifications of the point clouds. The first dataset, the ISPRS Benchmark Data [50], was captured using a handheld scanner, Zeb-Revo, in one of the buildings at the Technical University of Braunschweig, Germany. The data were acquired from across two floors connected via a staircase. The point clouds and trajectories are shown in Figure 16a. The walls had different thicknesses, the ceilings were of different heights, and the level of point cloud quality was high. The second dataset was captured in the 14th floor of the Technology Building of Shenzhen University, using our own developed backpack laser scanning (BLS), which contains a 16-beam 3D laser scanner. The location was in a corridor with glass walls and contains a number of moving objects; the collected point clouds had a high level of noise, as shown in Figure 16b. The third and fourth datasets were acquired on a corridor and a parking lot by the backpack mapping system of Xiamen University (shown in Figure 16c,d). This laser scanning system [37] contains two 16-beam laser scanners and can obtain higher quality 3D point cloud data.

4.2. Parameters

The parameters of the proposed indoor structural model method for four datasets are listed in

Table 3. Parameters of the proposed indoor structural model method.

Parameters	Values	Descriptions
Extracting Openings
$C_{2D}$	$0.05m$	The size of the pixel (point clouds transform into image)
$w_d/h_d$	$\begin{array}{l}0.7m\le w_d\le 1.5m\\ 1.8m\le h_d\le 2.2m\end{array}$	The width and height of regularized door
$w_w/h_w$	$\begin{array}{l}0.5m\le w_w\le 1.5m\\ 0.5m\le h_w\le 1.5m\end{array}$	The width and height of the regularized window
Segmentation of Rooms
$C_{3D}$	$0.1m$	The size of the 3D grid (point clouds transform into 3D grid)
$\alpha ,\gamma$	$1.0/0.5$	Parameters of data term and smooth term of the energy function
Line Global Optimization
${\theta }_{\max }$	$0^{\circ }\le {\theta }_{\max }\le {45}^{\circ }$	Angle correction of lines
$d_{\max }$	$0\le d_{\max }\le 0.1m$	Distance correction of lines
$K$	$50$	k-nearest of lines
$\lambda$	$0.9$	The weight parameter of line global optimization
Cluster Similar Lines
$a_{thread}$	$5^{\circ }$	Angle threshold of merging similar lines
$d_{thread}$	$0.1m$	Distance threshold of merging similar lines
5G Signal Intensity Simulation
$d_p$	$100m$	The signal propagation distance
$f$	$100GHz$	The frequency of the electromagnetic wave
$m$	$1$	The power exponent by IDW interpolation

. Based on preliminary findings from the experiments, proposed methods showed robustness, and most of the parameters were insensitive to point cloud data in various indoor scenes and did not require manual modification. For opening extraction, the point clouds were transform into 2D image, where $C_{2D}$ is the pixel size, $w_d$ and $h_d$ are the width and height of the regularized door; and, $w_w$ and $h_w$ are the width and height of the regularized window. For room segmentation, the point clouds were transformed into 3D grids, where $C_{3D}$ is the size of 3D grid; and, $\alpha ,\gamma$ are weight parameters used for balancing importance between data term and smooth term in the energy function. For the line global optimization, the ${\theta }_{\max }$ and $d_{\max }$ were used to correct the angle and distance value of line; $K$ is the nearest neighbor number of every line; and, $\lambda$ is weight parameter used for balancing different terms in the energy function. For clustering similar lines, $a_{thread}$ and $d_{thread}$ were the angle and distance threshold. In 5G signal intensity simulation, $d_p$ is the signal propagation distance, $f$ is the frequency of the electromagnetic wave, and $m$ is the power exponent by IDW interpolation method. These parameters can be depended on the point cloud data from different indoor scenes with similar characteristics.

4.3. Results

The algorithm was implemented in C++, edited by Microsoft Visual Studio 2017. All experiments were performed with a Window 10, 64-bit operating system with an Alienware Intel (R) Core (TM) i7-7700HQ CPU @ 2.80 GHz and a 16GB RAM.

Preliminary visual results of the structured model showed correctness and completeness of the model. For the benchmark data (shown in Figure 17a), the width and length of the extracted doors (green) and windows (yellow) were close to the true value. The room segmentation results of the first and second floors (as shown in Figure 17b) showed that the unstructured point clouds were correctly partitioned based on the multi-label graph cuts. In order to ensure the model accuracy, the structural model was reconstructed using visible point clouds, which eliminated the error from wall thickness estimation. Figure 17c,d show the reconstructed models to have detailed wall information. The doors (yellow) and windows (red) were correctly positioned and completely embedded within the walls, and the adjacent rooms had different heights. The structured model and original point clouds were well-matched, as shown in Figure 17e.

For the corridor data of Shenzhen University, the acquired point clouds suffered from multiple reflections and refraction due to the glass walls, which resulted in the dramatic challenges during model reconstruction. Figure 18a shows the structured models, while Figure 18b shows that the detailed vector models of walls, pillars, the doors (green). The closed-loop polyhedron was created using the constrained Delaunay triangulation [51], which the detected closed polygons are as boundary rings. Figure 18c,d illustrate that the reconstructed models and point clouds are well matched. For the Xiamen University corridor, a high accuracy indoor structured model was obtained. Figure 19a,b show the structural models and the wall models, which are presented with detailed regularization information and accurate room representation with uneven ceiling heights. The doors (green) and windows (red) were correctly detected and completely embedded within the walls. The point clouds and the reconstructed model are well-matched, as presented in Figure 19c,d.

For the parking lot in Xiamen University, the point clouds showed an excessively high level of noise. However, our proposed framework is still well-built even with incomplete data caused by severe occlusion (see Figure 20a,b). Our approach can auto-complete and generate closed-loop polyhedrons, and also correctly reconstruct the slant ceiling, floor, vertical walls, and regularized pillars. However, some curved walls are represented by many small polygons. The reconstructed models matched well with the original point clouds, as shown in Figure 20c,d.

More details of the results are displayed in Figure 21, despite the presence of noises and incomplete in the point clouds, our reconstructed models are of high correctness and well fit to the original point clouds.

For 5G signal intensity simulation, we tested our method on the structural model reconstructed from the benchmark data, as shown in Figure 22. The signal intensity is shown to drastically decrease from the base stations when three were mounted on the first floor, as illustrated by the changing colors of intensity (red to blue) in Figure 22a. In order to visualize the trend of signal intensity loss, a horizontal intensity profile was generated using the IDW interpolation method and is shown in Figure 22b. Similarly, the results from the multipath signal propagation and horizontal profile from the second floor are shown in Figure 22c,d. In Figure 22e, the received energy value is shown to significantly decrease with increasing distance under the path loss model.

5. Evaluation and Discussion

Four real-world datasets captured using MLS were used to test our proposed methodology. Field experiments were used to analyze the visualization results and correctness of the semantic information and the spatial and topological relations of reconstructed models, as shown in Figure 17, Figure 18, Figure 19, Figure 20 and Figure 21. The quantitative evaluation of the model included basic element extraction, running time, and geometric errors, as shown in

Table 4. Results of basic element extraction.

Description	Number of Points	Actual/Detected Doors	Actual/Detected Windows	Actual/Detected Rooms	Actual/Detected Pillars
Benchmark data	11,628,186	51/42	21/8	25/25	0/0
Corridor (Shenzhen University)	1,980,911	4/4	0/0	1/1	6/6
Corridor (Xiamen University)	7,683,766	8/8	11/11	1/1	0/0
Parking Lot (Xiamen University)	2,098,634	0/0	0/0	1/1	23/18

,

Table 5. Running time for different scenes.

Description	Surface Extraction (s)	Opening Detection (s)	Room Segmentation (s)	Line Regularization and Model Reconstruction (s)	Total Time (s)
Benchmark data	80	19	287	49	435
Corridor (Shenzhen University)	9	4	0	24	37
Corridor (Xiamen University)	7	6	0	20	33
Parking Lot (Xiamen University)	28	0	0	32	60

and

Table 6. Euclidean distance deviation for different scenes.

Error/m	0.05	0.10	0.15	0.20	0.25	0.30	0.35	0.40	0.45	0.50	0.55	0.60	0.65	0.70	0.75	0.80	0.85	0.90	0.95
Benchmark first floor (%)	51.50	27.68	12.92	3.26	1.73	1.61	0.28	0.21	0.20	0.11	0.10	0.09	0.07	0.07	0.08	0.05	0.02	0.01	0.01
Benchmark second floor (%)	52.31	30.09	9.36	3.20	2.41	2.11	0.31	0.07	0.01	0.02	0.02	0.01	0.01	0.02	0.01	0.01	0.01	0.01	0.01
Corridor, Shenzhen University (%)	25.10	25.81	22.02	7.45	5.51	3.81	3.02	2.55	1.10	0.81	0.82	0.40	0.51	0.50	0.14	0.12	0.21	0.01	0.11
Corridor, Xiamen University (%)	75.83	15.49	4.81	1.75	0.62	0.60	0.11	0.11	0.41	0.10	0.02	0.01	0.02	0.05	0.02	0.02	0.01	0.01	0.01
Parking lot, Xiamen University (%)	32.82	20.87	15.71	10.92	5.38	3.30	2.62	2.01	1.37	1.23	1.06	0.91	0.44	0.26	0.27	0.23	0.20	0.25	0.15

and Figure 23.

5.1. Quantitative Evaluation

Table 4 and Table 5 enumerate key properties of the reconstructed model, including the number of points, actual and extracted basic elements, and runtime. For the statistical analysis of geometric errors, the reconstructed results with real data did not contain ground-truth data, so we used the distance from each original point cloud to its corresponding model plane as geometric error. The summary is presented in Table 6 and Figure 23.

In Table 4, for the benchmark data, 42 doors and 8 windows were correctly detected: 20 doors and 1 window on the first floor and 22 doors and 7 windows on the second floor. The closed doors cannot be detected. The detection failure for the other windows was due to high sparsity and noise in the wall point clouds. However, all rooms and corridors were correctly segmented and had no under-segmentation or over-segmentation. The Shenzhen corridor dataset had high levels of noise and sparsity due to multiple reflections of moving objects and refraction from the glass wall. However, the structured information of pillars and doors were accurately extracted. For the Xiamen corridor dataset with high-quality point clouds, all openings were correctly detected. For the Xiamen parking lot dataset, 18 pillars were correctly detected. In terms of time efficiency, the reconstruction of the four real-world datasets required little runtime (see Table 5), with only the room segmentation taking relatively more processing time. The results indicate our proposed methodology has high modelling efficiency with wide-ranging applications in different indoor scenes.

The summary of Euclidean distance deviation and diagram are shown in Table 6 and Figure 23. The reconstruction accuracy from the Xiamen corridor was highest, having 75.83% of point distance deviation within the 0.05 m range. The two floors from the benchmark showed comparable results with 51.50% (1st floor) and 52.31% (2nd floor) of deviations coming from the 0.05 m range. For the Shenzhen Corridor and Xiamen parking lot, the percentage of deviation within 0.05 m reached 25.10% and 32.82% respectively. This indicates that when using our approach, the reconstruction quality is heavily dependent on the quality of point clouds. Nevertheless, our method shows it can provide reliable and accurate reconstruction of indoor scenes within the 0.10 m range without the need for manual intervention.

5.2. Limitations

A major technical limitation of our method is that the detection of openings are highly dependent on the geometric quality of point clouds, which for indoor scenes with high amount of noise, could be very problematic. Also, the curved walls are represented with many small polygons, indicating that irregular structures could not be expressed as meshes. Then, the output results in this study are surface models; however, BIM standard models are often represented as volumetric building entities with walls, floors, ceilings, and topological information, thus, the surface models will lead to limit the expression of model thickness in practice. Lastly, in 5G signal simulation, the type of wall materials, which could create varying degrees of signal loss, was ignored for simplification, which results in some errors with actual situation.

6. Conclusions and Outlook

The current bottleneck in 3D indoor reconstruction is the low level of automation and accuracy in the reconstruction of the complex indoor environment. To address this problem, we proposed a novel method that combines the rich structures of lines and 3D geometric information of surfaces to automatically build a three-dimensional structured model from MLS point clouds. First, a fully automatic room segmentation is performed on the unstructured point clouds via multi-label graph cuts to overcome over-segmentation problems. The floorplan lines are then extracted and regularized from the image to obtain detail structural information. Finally, the segmented room, line, and surface elements are used as semantic information, and the 3D structured models are reconstructed by multi-label graph cuts. We showed how our proposed approach is able to accurately reconstruct real-world datasets without requiring manual operation. Also, the signal intensity simulation for 5G small base station was conducted using the results of our 3D model, which showed how our proposed technique can be very useful in such an application.

We tested our method on four real-world datasets acquired using the MLS. In analyzing the results, we included the assessment of the geometric elements, time-efficiency, and geometric errors in the evaluation. Experimental results show that the reconstructed structured models, including ceilings, floors, walls, doors, windows, and pillars, etc. The Combination of linear structures with 3D geometric surfaces to reconstruct structured models, which improve the computational efficiency and structural accuracy. The resulting models show that the geometric error of is within 0.1m for different indoor scenes. The detection of geometric elements is highly dependent on the geometric quality of point clouds. For our future endeavors, we will try to combine image and point clouds to further enrich the model results, which could help improve opening detection and compensate for poor point cloud quality. We will also reconstruct the full volumetric models using the extracted geometric elements, and further close to the requirements for Building Information Modeling. Finally, we will be investigating further the use of our approach in optimal location for 5G small base stations and other similar technologies, as well as considering other applications that may benefit from our approach.