# Automatic 2D Floorplan CAD Generation from 3D Point Clouds
## 3 Proposed Method
### Wall Detection  
Detecting walls is a more complex process than detecting floors and ceilings. After removing floors and ceilings, 3D point clouds contain points belonging to walls as well as points belonging to clutter, such as furniture (e.g., desks, chairs and bookshelves). Detecting a wall is highly sensitive in cluttered data. In order to solve this problem, wall proposals are conducted by removing most of the clutter from the 3D point clouds. As shown in Figure 2, wall proposals, \(W_{p}=\{w_{p1},...,w_{pn}\}\), are calculated based on the assumption that walls are vertical and parallel to \(y\)-\(z\) or \(x\)-\(z\) planes. Therefore, all possible planes are extracted using a parallel model of the RANSAC algorithm. Then, our proposed algorithm retains the planes with altitudes higher than a threshold, as follows:  
\[w_{pi\_height}>\mathit{thres}*(Ceiling_{minZ}-Floor_{maxZ}) \tag{1}\]  
Here, \(w_{pi\_height}\) is the height of the \(i\)-th plane, \(\mathit{thres}\) is a constant value that describes the minimum plane height, \(Ceiling_{minZ}\) is the minimum point of the \(z\)-axis for a ceiling, \(Floor_{maxZ}\) is the maximum point of the \(z\)-axis for the floor. Therefore, \((Ceiling_{minZ}-Floor_{maxZ})\) becomes the height of the current floor. After the wall proposals, walls are detected with two steps. In the first step, we create depth image based on points of wall proposal planes that are projected onto the \(x\)-\(y\) plane using Algorithm 1. The expected result is described in Figure 3a. Algorithm 1 works as follows:  
- Inputs are 3D point clouds of wall proposals and the grid size (default value for the grid size: 0.01 m). - 3D point clouds are projected into the \(x\)-\(y\) plane (lines 1 and 3), meaning we set all \(z\)-axis points to zero. - Create a grid structure from projected 3D point clouds (lines between 4 and 12). The projected 3D point clouds are initially sliced on the \(x\)-coordinate with range [\(i\), \(i\)+_gridSize_] and then on the \(y\)-coordinate with range [\(j\), \(j\)+_gridSize_], where \(i\) is an \(x\)-coordinate value of \(i\)-th point and \(j\) is a \(y\)-coordinate value of the \(j\)-th point. Then, the point density of each grid cell is then saved in a _grid_. - Create an empty image with the height and width of the _grid_ (line 13). - Calculate the image intensity based on the described _grid_ (line 14). In an image, intensity defines the pixel value; i.e., the pixel can have a value from 0 to 255 in a grayscale image. Figure 2: Result of wall proposal for seventh floor of the Robot Convergence Building at Korea University: (**a**) 3D point clouds after removing the floor and ceiling, and (**b**) 3D point clouds of wall proposal planes. ```
Input: 3D point clouds \(pt\), size of grid \(gridSize\) Output: Depth image \(depth1 mg\)
1 for each \(i\) in \(pt\).pointsdo
2 pt.points[i].z=0;
3
4 end for
5 Create an empty array \(grid\);
6 for each coordinate \(i\in[pt.minX,pt.maxX]\) in \(pt.x\)do
7\(i=i+gridSize\);
8 Set \(colX\) to slice points from 3D point clouds \(pt\) in given range \([i,i+gridSize]\);
9 for each coordinate \(j\in[pt.minY,pt.maxY]\) in \(pt.y\)do
10 Set \(gridCell\) to slice points from sliced points \(colX\) in given range \([j,j+gridSize]\);
11 Push size of \(gridCell\) points to \(grid\);
12
13 end for
14
15 end for
16
17 Create an empty image \(depthImg\) with the same size of \(grid\);
18 Set depth image intensity \(depthImg[i][j]=(grid[i][j]/maxValueOfGrid)*255\); return\(depthImg\)
```  
**Algorithm 1**Create Depth Image from 3D Point Clouds. In the second step, walls are detected using the created depth image with Algorithm 2. To solve the problem of missing 3D points when the building is scanned by a LIDAR, we propose an efficient line-detection algorithm from the created depth image. The proposed algorithm finds all horizontal and vertical lines in the depth image if a line contains at least one point. All possible wall candidates are defined in each horizontal and vertical line, as presented in Figure 2(b).