## 3 Methodology
### Room Segmentation
#### 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. Figure 3: The diagram of visible point clouds of simulated trajectory points. (**a**) Original point clouds. (**b**) Original point clouds divided into uniform grids. (**c**) Sample trajectory points. (**d**) Visibility analysis based on line-of-sight. 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. Figure 4: Simulating visible point clouds of sample trajectories. (**a**) The visible points of the three trajectory points 26, 30, and 33. (**b**) Visible points limited by door. Figure 5: Position of doors subdivide trajectory segments. (**a**) Sample trajectory points. (**b**) Partition of trajectory segments. \[ \begin{split}& E=\min(E_{\text{D}}+E_{S})\\ & E(l)=\min(\sum\limits_{v\in V}\alpha\text{-}D_{v}(l_{v})+\sum \limits_{(v,u)\in E}\gamma\text{-}B_{v,uv}(l_{v},l_{w}))\end{split}  \tag{2}\]  
**Data term**. \(E_{\text{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 \(\phi_{v}\), which is expressed in Equation (3):  
\[ \begin{split}& r_{o}=\frac{\phi_{v}\cap G_{\phi_{v}}}{G_{\phi_{v}}} \\ & D_{v}(l_{v})=I_{v}-r_{o}\end{split}