Predicting the Future by Mapping the Past
Article

Predicting the Future by Mapping the Past

Pushing the Limits on Lidar Change Detection at Regional Scales

Lidar change detection (LCD) is one of the most capable techniques for mapping changing terrain through time. It can be applied in billion-dollar decisions to design, build and operate tunnels, bridges, highways, railways, pipelines or subdivisions, which require engineers to evaluate how the earth will behave for decades to come. Predicting morphological change involves a deep understanding and appreciation of geology, geological processes, climate change and knowledge as to what physical changes have happened in the past or may occur in the future. This article presents how utilizing a graphics processing unit (GPU) and digital delivery of results can improve the LCD process by a factor of a thousand, opening up previously unthinkable applications.

LCD is the numerical process of comparing multiple Lidar datasets with overlapping coverage from different points in time. Airborne Lidar scanning (ALS) LCD is used by engineers and geoprofessionals to identify and track changing ground conditions commonly associated with geohazards such as landslides, flooding, bank erosion, debris slides, subsidence and rockfalls/avalanches, as well as assets such as embankments, highway pavement, bridges, open pits and dams. Conducting LCD analysis is typically completed using one of three general approaches:

  • Digital elevation model (DEM) differencing. DEM differencing calculates the vertical change between two DEMs at each raster cell, typically at a resolution of 1m. This LCD method is the most efficient and simplest to run, facilitating its use on geographically expansive datasets. However, the results of this approach are generally an order of magnitude less accurate than a fully optimized 3D solution (see point 3 below).
  • 3D point-based normal or shortest distance-based differencing (M3C2). 3D point-based LCD calculates the difference between two bare earth point cloud datasets along vectors representing the local normal of each individual point in the dataset, or the shortest distance between multiple datasets. This method is computationally expensive and requires ALS datasets to be subdivided into smaller zones (typically less than 30 million points per dataset) for processing. This method produces enhanced results over DEM differencing (see point 1 above) as the results represent a true 3D change based on the full resolution of the point-cloud data.
  • ICP pre-aligned 3D point-based normal or shortest distance-based. Iterative Closest Point (ICP) pre-alignment with 3D change measurement is a modification of point 2 above that utilizes advanced 3D error reduction algorithms to reduce the spatial noise between the ALS datasets prior to conducting the LCD. This spatial noise often presents itself as a systematic difference between the two datasets due to ground control and georeferencing at the time of data collection. The ICP process adds considerable computational expense and the use of advanced algorithms to the processing chain to spatially adjust the data while not introducing further errors. This is the most accurate approach to conducting LCD.

Figure 1: Change detection results for a slope without any ICP alignment, at a +/-15cm limit of detection.

In the case of applied earth science applications, a 3D point-based approach with ICP pre-alignment captures the mechanics of the changing ground in the most accurate way, given that purely vertical changes resulting from the DEM differencing approach rarely represent the true mechanism of ground movement, and errors from the georeferencing misalignments are significantly reduced.

The example in Figure 1 and Figure 2 highlights a case in which computing a 3D point cloud-based change detection without ICP (Figure 1) would not have allowed the detection of an active landslide that is immediately evident in the results of the change detection using ICP 3D point-based LCD (Figure 2).

Figure 2: Change detection results for the same slope as in Figure 1, but with ICP processing, at a +/-15cm limit of detection.

US Highway 101

To demonstrate the various LCD methods and power of advanced LCD processing, ALS data procured by the California Department of Transportation (CalTrans) in Northern California along US Highway 101, in an area known as Last Chance Grade, is presented below. At this location, the highway traverses steep slopes and ocean bluffs which are actively eroding and engaged in landslide processes.

LCD results comparing ALS data collected in 2016 and 2020 are presented in Figure 3. LCD results are typically presented as colour-contoured datasets overlain on the bare earth topography model. Model differences greater than the limit of detection (LoD) are typically filtered out of the results. The LoD is calculated based on a 95% confidence interval and is dependent on the quality of the spatial alignment between the two Lidar datasets. Blue colours represent zones of negative change (material loss or subsidence) and red colours represent zones of positive change (material accumulation, bulging or aggradation).

Switching from the DEM-based approach to a 3D point cloud-based approach at Last Chance Grade resulted in a reduction of the limit of detection by 3 to 4cm, and using the ICP combined with 3D point cloud-based approach resulted in a further reduction of the limit of detection by 4 to 8cm. This is an overall reduction in the LoD of 40%. The impact of the error reduction on infrastructure monitoring is significant, and the ability to detect these small changes is extremely valuable. This allows owners and engineers to act sooner and be more proactive in managing assets to reduce overall lifecycle costs.

Figure 3: Lidar change detection for Last Chance Grade utilizing a ICP pre-aligned point cloud normal-based change detection.

The vision and the problem with LCD

Figures 1, 2, and 3 illustrate the advantage of utilizing an ICP pre-alignment, point-based change detection approach for LCD. As ALS data is collected more frequently and at higher densities than ever before, the use case for advanced LCD is increasing. The ability to provide engineers, geoprofessionals and asset owners with a method to assess and communicate 3D spatial change across vast scales is a powerful tool to understand the past, predict future behaviour and manage associated risks. LCD applications span several industries and applications such as monitoring highway, rail and pipeline networks, reservoir slopes and shorelines, and changing coastlines. Until recently, however, the ability to apply advanced numerical methods (specifically method 3 above) for LCD at scales beyond specific project sites has been extremely limited to due computational resources required for data execution, subject matter expertise to conduct the analysis, and digital platforms for visualization and interrogation of results.

To scale up 3D ICP LCD from single sites to regional networks, three R&D projects were undertaken:

  • Custom-built 3D ICP LCD algorithms written using native GPU compute shaders
  • Collaborative multi-user 3D environment for analysis and visualization of cloud-hosted LCD results, ortho images and terrain data
  • Integration with geospatial asset management software for storage, access and interrogation of LCD data with all other geospatial information.

Moving to the GPU and the world of compute shaders

Over the last 20 years, GPUs have evolved from fixed-function systems for 3D rendering to general-purpose computation units. Modern GPUs can execute thousands of calculations in parallel, provided that those operations are independent. This contrasts with CPUs which can only execute dozens of operations in parallel but handle general-purpose code and conditional logic well. As a result, GPUs offer huge speed gains in cases where calculations can be performed in parallel. For example, deep learning and 3D rasterization are hugely accelerated on a GPU because they mostly involve performing independent calculations on each element in large buffers of data.

With point-cloud change detection, it is more difficult to realize these speed gains since a point-cloud change algorithm consists of two types of operation:

  • Calculations, such as:
    1. solving for an alignment transformation
    2. calculating normals
    3. computing change values.
  • Spatial queries, such as determining which points:
    1. are likely correspondences between two clouds
    2. represent the local surface around a point
    3. should be considered during change detection around a point.

Often, GPU implementations of systems are performed by porting existing code using frameworks like nVidia CUDA. Unfortunately, with point cloud processing, this approach results in a GPU implementation that is entirely bound by query performance since data structures commonly used for spatial queries access memory randomly and have lots of conditional logic. In fact, the result can be slower on a GPU than the same code on a CPU!

The suggested implementation performs all GPU calculations using compute shaders – the lowest level of code natively exposed by a GPU, which provides direct control over execution and parallelism which is used to achieve high performance. The authors use a chain of compute shaders for normal calculation, ICP and the change detection itself.

Figure 4: Screenshot from video fly-through of LCD results along US Highway 101.

The authors also perform all spatial queries on the GPU, using compute shaders and linear data structures optimized for GPU hardware. Their query algorithms favour speed and returning conservative results over returning a minimal set of points. Additional points returned by the queries during calculation are then rejected. This is still faster overall, because the GPU performs calculations on redundant points faster than it can execute a more precise query.

These compute shaders are driven by a parallelized CPU framework which marshals data to and from the GPU, handles disk access and performs decompression for Lidar formats such as LAZ. The result is a system that is able to process multi-billion-point datasets in orders of magnitude faster than the fastest CPU implementations.

Visualization and collaboration

ALS data are 3D by nature, and ICP 3D point-based LCD results are best analysed in a 3D environment. BGC developed a multi-user collaborative 3D environment that allows users to ‘fly’ around the Lidar data with LCD results or walk across the terrain. The 3D environment, built on Unity-based technology, facilitates the integration of high-resolution ortho imagery, vector data and dynamic controls over the LCD results. A screenshot from a video of three separate users interacting in the collaborative space is presented in Figure 4.

Conclusion

The ability to conduct ICP 3D point-based LCD at a regional scale utilizing GPU processing, delivering results in an interactive, collaborate 3D environment, at speeds upwards of three orders of magnitude faster than CPU-based processing, is revolutionizing the usability of ALS data. In the past year, BGC has processed over 40,000 linear kilometres of LCD data, serving up tens of billions of LCD points in digital platforms to clients, globally. Being able to extract additional value from ALS data to better understand the morphological changes and behaviour of assets over time greatly enhances an engineer’s ability to make informed decisions and design resilient infrastructure.

Acknowledgements

The authors would like to thank Jaime Matteoli and Eric Wilson from CalTrans for agreeing to the use of ALS data collected along US Highway 101 and showcase the LCD results which are currently being used by the expert review panel to assist in the redesign of the highways. The authors appreciate the help of Dr Scott Anderson, Alex Graham, Matt Williams, Cole Christiansen and Luke Weidner at BGC for support in processing and interpreting the LCD results. The methods discussed in this article are patent-pending: Application #17/371,337.

Make your inbox more interesting.Add some geo.

Keep abreast of news, developments and technological advancement in the geomatics industry.

Sign up for free

Keep abreast of developments in the geospatial industry

We encourage you to subscribe to our weekly newsletter. Subscribers also receive a digital copy of our bi-monthly magazine.