# Indoor Building Reconstruction from Occluded Point Clouds Using Graph-Cut and Ray-Tracing
## 3 Indoor Reconstruction Methodology
### Indoor Component Reconstruction  
Starting from the detected and the guessed 'pending' wall derived from the planar primitive extraction phase (Figure 4a), the indoor building model is derived by applying a decomposition and labelling procedure based on cell complex labelling. To this end, the floorplan is decomposed into adjacent cells creating a 2D arrangement [37] which is set up by using both 'detected' and 'pending' walls. The cells are then labelled as 'indoor' and 'outdoor' by solving an energy minimization problem by using graph cut optimization [38]. The cell decomposition technique has been widely used in building ground plane generalization [39]. In particular, starting from the detected and 'pending' walls identified in the previous step the ground plan is partitioned into a set of cells generating a partitioning of the original space domain into convex polygonal cells (Figure 4b). After the cell decomposition, we obtain a 2D arrangement composed of a set of cells \(T=\{T_{k}\,|\,K=1,\,\ldots\,,\,k\}\), which are labelled as 'occupied' (within the room) and 'empty' (outside the room) cells. Once having derived the cell complex, the floor plan reconstruction problem may be formulated as an optimal binary labelling of cells in the complex. Each cell is labeled as 'empty' or 'occupied' and the floor plan can be extracted as the union of all facets separating an 'occupied' cell from an 'empty' one. In this way an intersection-free boundary may be obtained. Graph cut is an optimization method for solving this type of binary labelling problem through a minimum cost cut on a graph [40]. An energy minimization score function is defined and the minimization problem can be handled using global graph cut optimization. A unidirectional graph \(G=(V,E)\) is defined as a set of nodes and a set of unidirectional edges to encode the set of cells \(T\) and the label set \(L=\{L_{empty}\) and \(L_{occupied}\}\). The set of decomposition cells  
Figure 4: Example of cell complex construction: (**a**) detected and ‘pending’ walls and (**b**) induced cell complex. \(\{T_{k}\,|\,K=1,\,\ldots,\,k\}\) can be assigned to a set of vertices \(V=\{V_{k}\,|\,K=1,\,\ldots,\,k\}\) connected with weighted edges. Each edge in the graph is assigned with a non-negative weight \(W_{e}\). The set of edges \(E\) is composed of two parts: \(n\)-links (neighborhood links) and t-links (terminal links). Therefore, the set of edges may be expressed as \(E=N\,\,U_{p}\in V\) {[\(v\),\(S\)],[\(v\),\(T\)]} where \(N\) is the set of neighborhood links, while \(S\) and \(T\) represent the \"source\" and the \"sink\" model expressing foreground and background in the graph cut respectively. In particular, the source node is labelled as the empty space \(L_{empty}\) while the sink is the occupied space \(L_{occupied}\). In other words, the vertices V are the cells of the polygonal cell complex and the edges \(E\) link adjacent cells, i.e., they correspond to the facets of the complex augmented with two additional seeds, a source \(s\) and a sink \(t\), with edges from s to each cell and from each cell to \(t\). All edges have non-negative weights \(W\). A \(s-t\) cut (\(S\),\(T\)) is a partition of \(V\) into two disjoint sets \(S\) and \(T\) such that \(s\in S\) and \(t\in T\). The cost of an \(s-t\) cut is the sum of the weights of the edges from \(S\) to \(T\). An efficient algorithm with low-polynomial complexity exists to find the \(s-t\) with minimal cost, allowing a global minimization of the energy. The graph partitioning (\(S\),\(T\)) corresponds to a binary labelling of cells (Figure 5), where cells in \(S\) and \(T\) are respectively empty and occupied, and the cost of the cut corresponds to the energy of the associated surface. Weights of those edges joining the source or the sink penalize the associated cells, while weights of those edges between two cells penalize the associated facets.