<figure><img src="image_1.png" /></figure>

HAL
open science

# Data Reduction of Indoor Point Clouds

Stephan Feichter, Helmut Hlavacs

► To cite this version:

Stephan Feichter, Helmut Hlavacs. Data Reduction of Indoor Point Clouds. Esteban Clua; Licinio Roque; Artur Lugmayr; Pauliina Tuomi. 17th International Conference on Entertainment Computing (ICEC), Sep 2018, Poznan, Poland. Springer International Publishing, Lecture Notes in Computer Science, LNCS-11112, pp.277-283, 2018, Entertainment Computing – ICEC 2018. 10.1007/978-3-319-99426-0_29. hal-02128604

HAL Id: hal-02128604

https://inria.hal.science/hal-02128604

Submitted on 14 May 2019

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Data Reduction of Indoor Point Clouds

Stephan Feichter and Helmut Hlavacs

University of Vienna, Austria
Entertainment Computing Research Group
helmut.hlavacs@univie.ac.at

**Abstract.** The reconstruction and visualization of three dimensional point cloud models, obtained by terrestrial laser scanners is interesting to many research areas such as gaming, engineering and robotics. We present an algorithm to decimate redundant information in real-world indoor point clouds scenes. The key idea is to recognize planar segments from the point cloud and decimate the inlier points by the triangulation of its shape describing boundary. To achieve this RANSAC, normal vector filtering, statistical clustering, alpha shape boundary recognition and the constrained Delaunay triangulation are used. The algorithm is tested on large dense point clouds and is capable of reduction rates from approximately 75-95%.

**Keywords:** point cloud · decimation · plane detection · triangulation

## 1 Introduction

The use of digital three-dimensional models of real-world environments has become popular in a variety of fields including environment-based game design, serious gaming, robot navigation, professional civil engineering, architecture, documentation of historical structures or interior design. Terrestrial Laser Scanner (TLS) measure distances by laser, with a very high precision. For indoor environments the TLS can efficiently produce complete high quality scans, using and combining only a few scan positions [11, 10]. The output of a TLS is a dense point cloud (x,y,z) spanning large areas or entire floors that exceed millions of points. Due to the sheer amount of data, these large datasets lead to difficulties in processing, visualization and real-time use [7, 2]. In indoor scenes a lot of redundant information is captured in planar surfaces, they end up being over-represented by thousands of points, when they could be represented more efficiently by primitive shapes [7, 8]. This paper explores a way to reduce point cloud data size by plane segmentation, normal vector based filtering, statistical clustering and alpha shape triangulation. The proposed approach is evaluated on six different real-world 3D scans of indoor environments.

## 2 Related Work

Data segmentation is defined as a grouping of elements into regions with similar properties. There are three main segmentation approaches from point clouds:
region growing, clustering of features and model fitting. The region growing algorithm method is achieved by identifying a seed and growing it, within some specific distance and patterns in the data [1]. On the other hand, the clustering of features method identifies patterns in the data based on attributes and combining them into clusters. In the model fitting method a mathematical model is estimated to fit the data (i.e. geometric primitive shapes such as planes) [1]. Two widely used model fitting algorithms are Random Sample Consensus (RANSAC) and hough-transform. For the accurate representation of indoor environments in games or virtual reality the following works have been found: In the paper of Shui et al. [11], the point-cloud first is coarse segmented by a gaussian map region growing, then it is fine segmented using RANSAC, followed by boundary generation. At the end a semantic graph structure for the segments is created. This is then imported in Unity3D and enhanced with textures. Ma et al. in [6] describe a hybrid reconstruction solution. Planar surfaces are segmented by a flatness based region growing method, then the planes and residual objects get reconstructed differently. The objects are reconstructed by Greedy Projection Triangulation, the planes get reconstructed with a Quad-Three-Based algorithm. At the end object meshes and plane meshes get combined for the full reconstruction of the point cloud.

# 3 System Overview

To decimate the noise, as the first step in the pipeline, an algorithm that detects and removes sparse outliers, proposed from Rusu et al. [5], is used. The algorithm is based on statistical techniques and excludes outliers by computing the mean $\mu$ and standard deviation $\sigma$ of nearest neighbor distances. Those points which fall outside the $\mu \pm \alpha \cdot \sigma$ are considered as noise. The second step in the pipeline is the segmentation process. Man-made structures are dominated by planar surfaces, to detect these the concept of RANdom SAmple Consensus (RANSAC) [3] is used [12]. To describe a plane, three points are needed. RANSAC selects these randomly and in all orientations, then detects all points belonging to the plane within a given threshold (plane thickness). This gets repeated until the best-fit plane in the 3D point cloud is found. This is where the highest score (number of points) fit the plane. Due to the plane thickness, our obtained point cloud segment may contain points, belonging to other objects or planes. These points generally occur at the borders of the planes and have a different normal vector direction than the plane models normal vector. We first estimate the normal vector of each point in the point cloud by an algorithm proposed by Hoppe et al. [4]. Then we calculate the angle between each point normal vector and the plane normal vector. The angle is used to filter each point by a defined threshold. The filtered plane segments of the point cloud may contain different disconnected surfaces. To further process these areas separately, a clustering technique is applied. As every extracted segment has a diverse topology, an algorithm that works with no a priori knowledge of the number of clusters is necessary. The algorithm used is k-means clustering, which separates the data
points into k different clusters. With the help of the elbow method and gap statistics, the used cluster algorithm can choose the optimal number of clusters automatically. The initial number of clusters is randomly generated, then the algorithm will evaluate and converge to several results with a different number of clusters [9, 5]. To decimate the inlier points of each planar cluster, the boundary points of each cluster, containing all necessary information of its shape, get calculated. To achieve this, an alpha-shape-based boundary algorithm is used [6]. The algorithm repeats to assign a polygon around the points, using a set of circles with varying radii. The edge points are then connected with straight edges and are considered as the boundary [8]. The obtained boundary points get then triangulated to form a connected mesh. This is achieved by using the ordered boundary vertices as the constraint for the Constrained Delaunay Triangulation (CDT). At this point the proposed algorithm has processed one plane segment. The loop gets repeated on the residual point cloud, as long the next found segment of RANSAC contains a number of points above a given minimum. When the segmentation process ends, a ply output file is generated, containing the generated meshes and the points of the residual point cloud.

## 4 Results

The sample set to evaluate the proposed system contains six different dense point clouds of TLS scanned environments. All experiments were performed on an Intel Core i5 laptop with 3.1 GHz and 16 GB RAM. The pipeline was implemented in MATLAB R2017b, due to its ease of use and that it can easily be used cross platform. Each sample was fed into the pipeline with predefined parameters. Without user interaction, the pipeline processes the sample and saves the output files. The algorithm achieves acceptable results for every sample, resulting in reduction ratios from 73.15% to 96.50%. Table 1 gives a quantitative overview of the plane segments found, the amount of the residual point cloud points and triangulated faces, the processing time and the reduction rate for each sample.

<table><caption>Table 1: Point cloud reduction results</caption><thead><tr><th>Nr.</th><th>Name</th><th>#Planes</th><th>#Total pts.</th><th>#Residual pts.</th><th>Faces</th><th>Duration [h]</th><th>Reduction</th></tr></thead><tbody><tr><td>1</td><td>Ballroom</td><td>11</td><td>25,793,831</td><td>5,189,432</td><td>33,360</td><td>20:03</td><td>79.88 %</td></tr><tr><td>2</td><td>Bedroom</td><td>11</td><td>20,133,594</td><td>2,834,338</td><td>13,036</td><td>6:53</td><td>85.92%</td></tr><tr><td>3</td><td>Loft</td><td>7</td><td>13,500,000</td><td>2,973,802</td><td>7,358</td><td>5:46</td><td>77.97%</td></tr><tr><td>4</td><td>Boardroom</td><td>8</td><td>13,476,844</td><td>3,618,515</td><td>12,654</td><td>5:14</td><td>73.15 %</td></tr><tr><td>5</td><td>Constr. s.</td><td>10</td><td>11,686,367</td><td>1,161,448</td><td>7,284</td><td>4:11</td><td>90.06 %</td></tr><tr><td>6</td><td>Officeroom</td><td>9</td><td>8,550,825</td><td>299,445</td><td>9,593</td><td>5:45</td><td>96.50 %</td></tr></tbody></table>
<figure><img src="image_3.png" /><figcaption>Fig. 1: Point cloud sample set (top view).</figcaption></figure>

**5 Conclusion**

In this paper, we have developed an automatic system for 3D point cloud pro-
cessing, which is capable to reduce the number of points of real-world indoor
environments produced by terrestrial laser scanner. After denoising, planar seg-
ments of the point cloud get extracted. By normal vector filtering and clustering
the segments, a number of planar clusters can be obtained. The boundary points,
which describe the shape of the planar clusters, get triangulated, reducing the
number of interior points and simplifying the output mesh, but preserving its
geometry. The experiments on six different TLS scanned indoor scenes with 8 to
<figure><img src="image_4.png" /><figcaption>Fig. 2: Result set (top view).</figcaption></figure>

25 million points and varying characteristics, show that approximately 75-95% of the points are removed in the planar segments.

References

1. Awwad, T.M., Zhu, Q., Du, Z., Zhang, Y.: An improved segmentation approach for planar surfaces from unstructured 3d point clouds. The Photogrammetric Record **25**(129), 5–23 (2010)

2. Deschaud, J.E., Goulette, F.: A fast and accurate plane detection algorithm for large noisy point clouds using filtered normals and voxel growing. In: Proceedings of the 5th International Symposium on 3D Data Processing, Visualization and Transmission (3DPVT’10) (2010)
3. a Fischler, M., Bolles, R.C.: Random sample consensus: A paradigm for model fitting with. Communications of the ACM 24, 381–395 (1981)

4. Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., Stuetzle, W.: Surface reconstruction from unorganized points, vol. 26. ACM (1992)

5. Liu, X., Zhang, X., Cheng, S., Nguyen, T.B.: A novel algorithm for planar extracting of 3d point clouds. In: Proceedings of the International Conference on Internet Multimedia Computing and Service. pp. 142–145. ACM (2016)

6. Ma, L., Favier, R., Do, L., Bondarev, E., de With, P.H.: Plane segmentation and decimation of point clouds for 3d environment reconstruction. In: Consumer Communications and Networking Conference (CCNC), 2013 IEEE. pp. 43–49. IEEE (2013)

7. Ma, L., Whelan, T., Bondarev, E., de With, P.H., McDonald, J.: Planar simplification and texturing of dense point cloud maps. In: Mobile Robots (ECMR), 2013 European Conference on. pp. 164–171. IEEE (2013)

8. Michailidis, G.T., Pajarola, R.: Bayesian graph-cut optimization for wall surfaces reconstruction in indoor environments. The Visual Computer 33(10), 1347–1355 (2017)

9. Nguyen, A., Le, B.: 3d point cloud segmentation: A survey. In: Robotics, Automation and Mechatronics (RAM), 2013 6th IEEE Conference on. pp. 225–230. IEEE (2013)

10. Sahin, C.: Planar segmentation of indoor terrestrial laser scanning point clouds via distance function from a point to a plane. Optics and Lasers in Engineering 64, 23 – 31 (2015). https://doi.org/10.1016/j.optlaseng.2014.07.007, http://www.sciencedirect.com/science/article/pii/S0143816614001791

11. Shui, W., Liu, J., Ren, P., Maddock, S., Zhou, M.: Automatic planar shape segmentation from indoor point clouds. In: Proceedings of the 15th ACM SIGGRAPH Conference on Virtual-Reality Continuum and Its Applications in Industry-Volume 1. pp. 363–372. ACM (2016)

12. Yang, M.Y., Förstner, W.: Plane detection in point cloud data. In: Proceedings of the 2nd int conf on machine control guidance, Bonn. vol. 1, pp. 95–104 (2010)