This article was originally published in Geomatics World.
Terrestrial Lidar data has great potential to produce measurements for as-built building information modelling (BIM). Unfortunately, processing hundreds of millions of points, often contaminated by substantial noise, can be tedious and time-consuming. Normal variation analysis (Norvana) segmentation is an automatic method that can segment large terrestrial Lidar point clouds containing hundreds of millions of points within minutes.
Thanks to the high speed, point density and accuracy of modern terrestrial laser scanning (TLS), as-built BIM can be conducted with a high level of detail. But TLS captures not only useful geometric information but also unwanted objects, such as people, animals or vehicles moving across the scene (Figure 1). These unwanted points have to be removed and the data cleaning can be a tedious and time-consuming process, not least because of the use of 2D interfaces to interact with 3D data and the high point density. One of the most fundamental challenges is the discreteness of the points, because each point is an independent data record with limited information by itself. A point does not directly contain semantic information (i.e. what it is) or topological information (i.e. who its neighbours are). A common solution to reduce point cloud complexity is ‘segmentation’, i.e. the grouping together of neighbouring points into segments, because it is less complex to model and analyse segments than it is to process individual points.
Point cloud segmentation can be straightforward as long as the assumptions can be mathematically modelled. For example, a flat floor can simply be extracted by using an elevation threshold. However, it is not always possible to make such simple assumptions, and the more assumptions that are made, the less generally applicable the approach becomes. Moreover, complex analysis can be time-consuming or the computation can even crash when large datasets of hundreds of millions of points are involved. In this case, the research goal was to come up with a solution that can serve as a general pre-processing framework without specific assumptions so that the approach can be applied more widely.
Many algorithms and software packages are able to segment point clouds reasonably well. In many of these approaches, however, processing several million TLS points can be very time-consuming. Norvana exploits the scan pattern for organizing the data and performing analysis. In the implementation, the time required to traverse the data is limited while the program has also been optimized to be more cache-friendly by aligning the data storage in the memory (RAM) with the search order for the processing and analysis. The Norvana segmentation method consists of two steps. First, the edges between objects are extracted based on a rapid change in surface orientation. This is done by performing an evaluation of the variance in normal vectors observed between the point and eight surrounding neighbours on the scan pattern grid. Then the points enclosed by these edges are grouped into single segments (Figure 2). Because the algorithm is designed as a pre-processing step, only the segments smaller than 10cm in any dimension have been removed to demonstrate the effectiveness in Figure 2. Because all of the points belonging to one segment can be processed as a single object, the following process and analysis can be performed in an object-based manner, which leads to higher efficiency and robustness. For example, for those points captured on any people walking across the scene, one can select the corresponding segments manually and delete or mask them without having to tediously draw a fence to remove each unwanted object in the scene. Technical details can be found in Che and Olsen (2018).
In Figure 2, the floor and walls are segmented appropriately and the ceiling is segmented into the individual panels. The top of Figure 3 shows a close-up of a display case embedded in the wall containing objects of different shapes, orientations and sizes that are segmented with a very high level of detail. A frame and a chair, both on the left of the display case, are correctly separated from the wall and floor, respectively. On the right of the display case, a vertical wide-flange column is segmented into different parts (web and flanges). Because Norvana considers the scanner location when estimating the normals, each side of the same flange is isolated as an individual segment instead of being merged into a single plane, even when the flanges are thin (which is a common failing of many existing algorithms). This robust approach to thin objects enables solid models to be generated for a wide variety of objects. The staircase is another important structure. The stairs are properly segmented into treads and risers (Figure 3, bottom). Compared with a planar surface, cylindrical objects require a more complex mathematical model. Regular and irregular-shaped smooth surfaces are readily segmented (Figure 4) because the normals still vary evenly across the surface. In the example, the points on the straight pipe have been correctly extracted and could subsequently be modelled as a cylinder. Also, complex objects such as the elbow have been segmented. Notably, pipes of different sizes and orientations are extracted using the same parameters. However, a limitation of this algorithm is that very rough surfaces cannot be extracted as a single segment.
Structuring of the data in the scan pattern grid enables the use of parallel programming so that multiple threads on the CPU can process different portions simultaneously. The approach was benchmarked on an outdoor dataset down-sampled at different rates with a different number of threads using a desktop computer with a low-end CPU (Intel Xeon CPU E5620 @ 2.40GHz, released in 2010). Efficiency is not significantly affected by the number of points at the scales tested (Figure 5). The performance is consistent at over one million points per second using eight threads during the processing of nearly 400 million points.
In the future, the plan is to increase the functionality of Norvana by including classification, modelling and other modules.
- Che, E., Olsen, M.J., 2018. Multi-scan segmentation of terrestrial laser scanning data based on normal variation analysis. ISPRS Journal of Photogrammetry and Remote Sensing. 143, pp. 233-248.