The Role of Digital Signal Processing in LIDAR

Abstract

Light Detection and Ranging (Lidar) is a surveying method that uses lasers to collect geospatial data on objects. Lidars emergence as a cost effective and efficient tool in cloud point data accusation has seen a growing body of peer-reviewed literature documentation in recent years. This paper aims to give an introductory overview of topical points in lidar signal processing and discuss the challenges and trends. Airborne Lidar ground filtering methods are compared and multiscale curvature classification is show to have performed well in rough terrain with vegetation. Models for surveying on and off road objects are discussed in part 2. Part three discussed a proposed method for the scalability of the of lidar processing involving a Hadoop based middleware.

Get Help With Your Assignment

If you need assistance with writing your assignment, our professional assignment writing service is here to help!

Assignment Writing Service

Introduction

[1]Lidar (Light Detection And Ranging) is a imaging technology that measures the reflected energy from laser pulses emitted. It uses controlled deflection to measure the time taken and differences in wavelengths of the originally unimodal laser pulses to create a model of it's target. Lidars small footprint, independence of sunlight, higher vertical accuracy, less missing data by occlusion, low redundancy and because it does not rely on the existence of textured surfaces have lead to it's increase in popularity in recent years. [2][3]Lidar technologies have long been used through the Global Navigation Satellite System (GNSS) but have been commercially used since the 1990's. Airbourne lidar, terrestrial LiDAR and more recently mobile lidar technologies have seen commercial use. These systems can be comprised of a variety of different components but all work on the same theoretical principle, as do all systems that use radiated electromagnetic energy for ranging. Light travels with a finite and constant velocity in a given medium. The amount of time the for emitted light from a source to a reflective target and back to the source allows you to quantify the range. This is know as time of flight measurement.[1] Multiple pulse echos can be captured when beam returns due to the target's reflective characteristics. Modern lidar sensors also measure the strength at which these pulses are returned. Hence, Lidar data is collected as a dense cloud of 3D points and their related intensity.

Airborne Lidar Filtering

[4]An important aspect to improve the quality of this data is filtering techniques. These techniques are used to remove the noise from the data set, removing any 3D-points that are reflected from unintended targets. The filtering techniques used depend on the intended use and a significate amount of research has focused on lidar point classification and created several filtering methods, such as interpolation-based ,slope-based, segmentation-based, and morphological methods. [8]Axelsson divided ground filtering methods into two major categories, point-based and raster-based method. Point based methods look at the point cloud directly while raster-based method take the point clouds and interpolate them onto a grid surface, the digital surface model (DSM). Rastering the data first allows you to take advantage of the image processing algorithms which run faster than point based operations but the this increase in speed tends to reduce the accuracy of the processing. Point based operations look at techniques like clustering analysis, local surface fitting, discrimination by slope/terrain difference/surface curvature ,active contours, and adaptive triangulated irregular networks whereas in raster-based methods approaches such image segmentation, edge detection, mathematical morphology repetitive interpolations, and analysis–synthesis framework are more common.

Methods in the first category classify directly the point cloud whereas methods in the second category first interpolate the point cloud onto a regular grid surface, namely, the digital surface model (DSM). Each approach has advantages and disadvantages. In general, rasterizing the data first allows to take advantage of digital image processing algorithms which run much faster than point-based operations, whereas point-based processing tends to be more accurate (Axelsson, 1999). Point-based methods tend to include techniques such as clustering analysis (Roggero, 2001), local surface fitting, discrimination by slope/terrain difference/surface curvature (Sithole, 2001), active contours, and adaptive triangulated irregular networks (Axelsson, 2000), whereas in raster-based methods approaches such image segmentation, edge detection (Brovelli, 2002), mathematical morphology (Zhang et al., 2003), repetitive interpolations, and analysis–synthesis framework are more common. The method presented in this chapter falls in the last category.

[5] A study by Sithole and Vossleman compared the performance or eight filtering methods both qualitatively and quantitatively. All filters performed well in smooth terrain and all produced errors in rough terrain and complex urban areas. This is possibly may be due to one of the assumptions of filtering algorithms: the bare-earth surface is smoother than the object's surface.

[4]Montealegre, lamelas and de la Riva compare seven discrete return LiDAR filtering methods that are used in open source tools to create DEM(digital elevation models) in environmental surveying and planning in a Mediterranean forest environment. The algorithms compared are the progressive TIN densification algorithm (LAStools), the weighted linear leastsquares interpolation-based method (FUSION), the multiscale curvature classification (MCC), the interpolation-based filter (BCAL), the elevation threshold with expand window method (ETEW-ALDPAT), the progressive morphological filter (PMALDPAT), and the maximum local slope algorithm (MLSALDPAT). The study looked at two sites in north-eastern Spain and classified sample Lidar data sets manually using points selected were classified manually using a high spatial resolution ortophotography, the intensity image created from the LiDAR data, the 3-D visualization of the points and more difficult to classify points a field expedition was conducted. [5]The filtering was assessed using the quantitative and qualitative methods used by Sithole and Vosselman, where is to select ground points as nonground measurements(Type I error), non-ground measurements are classified as ground points(Type II error), the total error and a visual assessment. The study concluded each method has it's own strengths and weaknesses with all of the method being susceptible to both Type I and Type II errors. A High level of accuracy is achieved by the MCC algorithm 83.3%of success rate and Cohen's Kappa index of 0.67. LAStools algorithm had a 82.8% of success rate and Cohen's Kappa index of 0.66.

MCC is an iterative multiscale algorithm for classifying lidar returns that exceed positive curvature thresholds. The MCC model uses a thin-plate spline (TPS) interpolation, integration of a multiscale approach where the surface is interpolated at different resolutions and implements progressive curvature tolerance. TPS interpolation allows for adjustment of tension between points, providing adherence to input data and controlling the distance at which point samples affect the surface estimates effectively reducing noise in the dataset. Fig 1 shows the iterative method of the MCC algorithm. The dynamic scale and the curvature threshold work concurrently to interpret relationships and changes in the topology of returns. This allows the MCC algorithm to maintain a high level of ground returns while still removing the low level surface modulation. Negative blunders are also common in Lidar data sets. Negative blunders occur when photons are scattered in a returned laser pulse, increasing the calculation of distance travelled by the laser pulse and recording the surface elevation erroneously. The MCC algorithm addresses this in method described by Haugerud and Harding[7] setting the curvature tolerance parameter to four times the interpolated cell size and removing data returns that exceed this value. This however can prevent accurate recordings of sink holes and other valid returns so this parameter can be implemented at the users discretion. As the MCC module needs only inputs from the Lidar data set, X,Y,Z it is easily reproduced and has flexibility across data sets.

Figure 1 The iterative approach for the multiscale curvature classification algorithm[6]

Other studies have taken advantage of the smoothing that occurs in a scale-space to detect curvatures that occur at transitions between ground and non-ground points. [9]One such method, the multiscale Hermite transform (MHT) described by Cárdenas and Wang in 2006 and [1]later further developed to include a further iteration of an optional loop which the main processing steps can be seen in Fig 2. This method allowed for the repeat application of multiscale erosion operator with an estimated data terrain model (DTM). The assumption of maximally flat terrain was also relax to a 6N multiple, boundary cells where processed with a different MHT coefficient with an antisymmetric condition replacing the symmetric condition lead to an improved model of complex terrains.

Figure 2 Flow diagram of ground filtering method. Dashed line indicates optional loop for repeated processing[1]

Mobile Lidar Processing

Road Boundary Extraction

There have been rapid developments in the mobile laser scanning in the recent years in the attempt to create accurate mapping techniques for autonomous vehicles and geographical surveying. [10]A lidar sensor or multiple lidar sensors are incorporated with other mobile scanning technologies (e.g., GNSS antenna, an IMU, and a distance measurement indicator (DMI)), advanced digital cameras) are mounted on a terrestrial vehicle to capture the 3D geospatial information as the vehicle is in transit. This gives real-time information for an autonomous vehicle to make critical decisions. Large amounts of data are collected by theses systems and one of the challenges is to filter the dataset subsequently increasing the reliability and accuracy. [11] Kumar et al. describes one such system that is used for extracting the road and it's boundaries from lidar data. The algorithm uses a combination of a Gradient Vector Flow (GVF) and balloon parametric active contour models, to extract road edges. Lidar elevation and pulse width are converted into a 2-d raster surface to reduce computational expense. As point densities are negatively correlated with the shooting range of the lasers this makes it possible to filter put the non ground point by taking their point densities into consideration. Fig 2 shows the steps involved in the road edge extraction algorithm proposed by Kumar et al.[12] The extraction was validated on complex roads, including roundabouts with a high degrees of curvature and shown to negate the limitations of traditional approaches. The limitations of this method include urban areas where parked cars and pedestrians can create noise in the Lidar dataset. The authors present a solution based on hierarchal thresholding and modified balloon energy approaches that would require further study and validation.

Figure 3 Steps in the road edge extraction algorithm[11]

Road marking extraction

Road markings provide essential road information, guidance and warnings for drivers. Autonomous vehicles must be capable of effectively reading this information to safely navigate and prevent accidents in complex urban environments. Road markings tend to be highly reflective materials on low reflective surfaces so this creates a characteristic that can be extracted from geospatial point clouds. Multiple methods have been proposed for processing these point clouds including a Hough transform by Yang et al[14] and an [15]iterative approach based on Multi-Scale Tensor Voting and weighted neighbouring difference histogram based dynamic thresholding algorithms extracted road cracks from noisy datasets. [13] Kumar et al implemented an automated road marking extraction algorithm with 90.91% and 88.43% rates for the number and shape detection of the extracted road markings. The lidar points are first identified as belonging to the road surface using the previously mentioned road edge algorithm, the 2-D range and intensity raster surfaces are then generated form the lidar points. The algorithm uses a single optimal threshold value which in turn automatically estimates the multiple range dependent threshold values that are used to extract the road markings. Morphological operations and prior knowledge are then applied to complete the shapes of the extracted road markings and to remove noise from the dataset. Then the 3-d road markings are extracted.

Multiple object extraction

Other objects like light poles, road side tress, electric poles and pedestrians all have algorithms developed to be extracted from point cloud data, but there is also methods that extract multiple objects. [16]Wang et al. use the Hough forest framework for object detection and implement the implicit shape model to describe object categories. The algorithm can be broken down into two stages, the training shown in figure 4 and detection of objects shown in figure 5.

Spectral features, eigenvalues of covariance matrix, 3-D invariant moments, fast point feature histograms (FPFH) and median of reflectance intensities were used for finding a 3D local, which was then mapped to predict the approximate position of the object centre. The peak points in the 3D Hough voting space was used to classify objects. Circular voting strategy was used to maintain the invariance of objects. The result is a detection algorithm that is robust to overlapping, rotation and occlusion and easily integrated with other objects.

Figure 4 Training procedure for the prosed algorithm.

Figure 5 Detection procedure of the proposed algorithm

Scalability of Lidar Processing

As the applications of Lidar have increased recent years so has the volume of data being processed and the sources from which this data is coming from. A pre-requisite to scaling these applications is creating standards for the storage and management of the data. [17]Raw Lidar point clouds are usually stored in the LAS format which is the open standard for 3-D data storage. These files are efficient in store the necessary colour and classification information but prove difficult to cross reference , manage and disseminate. Also current point cloud processing applications are currently based on single machines making use of multi core CPU's. For the scalability of Lidar data processing to continue big data processing in cloud environments will need to occur. Hadoops efficient storage and computing ability has allowed it to be integrated in a number of these proposed modules. [18]Li, Z., et al proposes a framework using existing lidar tools like LAStools with Hadoop to handle large amounts of lidar data. [19]Wang et al proposes a Hadoop-based distributed framework that integrates point cloud library processing tools into MapReduce. This allows for multiple processing operations to occur on parallel. Figure 6 displays the architecture of the proposed framework. The Hadoop distribute file system (HDFS) middleware proposed poses the problem that large files may need to be spilt into multiple blocks and store in different nodes, causing issues with splitting metadata and increasing computational complexly. Hadoop block file data needs to be kept as large as the images to prevent this from occurring.

Figure 6 The architecture of the proposed Hadoop based framework for cloud point data processing

Conclusion

Lidar technology has gained wide attention in recent years as has the number of potential applications of lidar in increasing including [21]agriculture, [26]archelogy, [1015]autonomous vehicles, [20]geological surveying, [22]law enforcement, [24] military, [24]robotics, [25]astronomy, and [23]meteorology. With the price decreasing and availability of lidar scanning technology increasing, the popularity within commercial and academic communities enlarges. There are still challenges the processing of lidar faces. The large quantity of data being collected will need a cost effective and efficient data storage method, that is standardised across the industry to provide a scalable technology. New sensors with different calibration and recording conditions pose a inconsistency across collection of data. The large amount of data being analysed also creates the computationally expensive task of processing the data. [4]Algorithms are going down the trend of point to raster conversion to take advantage of the less computationally expensive image processing algorithms. This was proposed by [1]Weng to have an adverse effect on the accuracy of the models when compared to there point based operations.

To summarise, signal processing of lidar will play a role in the scalability and rapid commercialisation of lidar technology. A reduction in computational expense, improved industry standards and cloud based processing environment will play a part in the effective signal processing.

References

[1] J. Weng, Scale issues in remote sensing. John Wiley and Sons, 2014, pp. 241-244.

[2] G. Vosselman and H. Maas, Airborne and Terrestrial Laser Scanning. Whittles Publishing, 2010, pp. 1-42.

[3] H. Guan, J. Li, S. Cao and Y. Yu, "Use of mobile LiDAR in road information inventory: a review", International Journal of Image and Data Fusion, vol. 7, no. 3, pp. 219-242, 2016. Available: 10.1080/19479832.2016.1188860.

[4] A. Montealegre, M. Lamelas and J. de la Riva, "A Comparison of Open-Source LiDAR Filtering Algorithms in a Mediterranean Forest Environment", IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, vol. 8, no. 8, pp. 4072-4085, 2015. Available: 10.1109/jstars.2015.2436974.

[5] G. Sithole and G. Vosselman, "Experimental comparison of filter algorithms for bareEarth extraction from airborne laser scanning point clouds", ISPRS Journal of Photogrammetry and Remote Sensing, vol. 59, no. 1-2, pp. 85-101, 2004. Available: 10.1016/j.isprsjprs.2004.05.004.

[6] J. Evans and A. Hudak, "A Multiscale Curvature Algorithm for Classifying Discrete Return LiDAR in Forested Environments", IEEE Transactions on Geoscience and Remote Sensing, vol. 45, no. 4, pp. 1029-1038, 2007. Available: 10.1109/tgrs.2006.890412.

[7] R. Haugerud and D. Harding, "Some algorithms for virtual deforestation (VDF) of LiDAR topographic survey data", Int. Arch. Photogramm. Remote Sens., vol. -34, pp. 211–217, 2001. Available: http://pugetsoundlidar.ess.washington.edu/vdf4.pdf. [Accessed 17 November 2019].

[8] P. Axelsson, "Processing of laser scanner data—algorithms and applications", ISPRS Journal of Photogrammetry and Remote Sensing, vol. 54, no. 2-3, pp. 138-147, 1999. Available: 10.1016/s0924-2716(99)00008-8.

[9] J. Silván-Cárdenas and L. Wang, "A multi-resolution approach for filtering LiDAR altimetry data", ISPRS Journal of Photogrammetry and Remote Sensing, vol. 61, no. 1, pp. 11-22, 2006. Available: 10.1016/j.isprsjprs.2006.06.002.

[10]L. Ma, Y. Li, J. Li, C. Wang, R. Wang and M. Chapman, "Mobile Laser Scanned PointClouds for Road Object Detection and Extraction: A Review", Remote Sensing, vol. 10, no. 10, p. 1531, 2018. Available: 10.3390/rs10101531.

[11]P. Kumar, C. McElhinney, P. Lewis and T. McCarthy, "An automated algorithm for extracting road edges from terrestrial mobile LiDAR data", ISPRS Journal of Photogrammetry and Remote Sensing, vol. 85, pp. 44-55, 2013. Available: 10.1016/j.isprsjprs.2013.08.003.

[12]P. Kumar, P. Lewis, C. McElhinney, P. Boguslawski and T. McCarthy, "Snake Energy Analysis and Result Validation for a Mobile Laser Scanning Data-Based Automated Road Edge Extraction Algorithm", IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, vol. 10, no. 2, pp. 763-773, 2017. Available: 10.1109/jstars.2016.2564984.

[13]P. Kumar, C. McElhinney, P. Lewis and T. McCarthy, "Automated road markings extraction from mobile laser scanning data", International Journal of Applied Earth Observation and Geoinformation, vol. 32, pp. 125-137, 2014. Available: 10.1016/j.jag.2014.03.023.

[14]B. Yang, L. Fang, Q. Li and J. Li, "Automated Extraction of Road Markings from Mobile Lidar Point Clouds", Photogrammetric Engineering & Remote Sensing, vol. 78, no. 4, pp. 331-338, 2012. Available: 10.14358/pers.78.4.331.

[15]H. Guan et al., "Iterative Tensor Voting for Pavement Crack Extraction Using Mobile Laser Scanning Data", IEEE Transactions on Geoscience and Remote Sensing, vol. 53, no. 3, pp. 1527-1537, 2015. Available: 10.1109/tgrs.2014.2344714.

[16]Hanyun Wang et al., "Object Detection in Terrestrial Laser Scanning Point Clouds Based on Hough Forest", IEEE Geoscience and Remote Sensing Letters, vol. 11, no. 10, pp. 18071811, 2014. Available: 10.1109/lgrs.2014.2309965.

[17]"LAS SPECIFICATION VERSION 1.4 – R13", Asprs.org, 2019. [Online]. Available: http://www.asprs.org/a/society/committees/standards/LAS_1_4_r13.pdf. [Accessed: 18- Nov- 2019].

[18]Z. Li, M. Hodgson and W. Li, "A general-purpose framework for parallel processing of large-scale LiDAR data", International Journal of Digital Earth, vol. 11, no. 1, pp. 26-47, 2017. Available: 10.1080/17538947.2016.1269842.

[19]C. Wang, F. Hu, D. Sha and X. Han, "EFFICIENT LIDAR POINT CLOUD DATA MANAGING AND PROCESSINGIN A HADOOP-BASED DISTRIBUTED FRAMEWORK", ISPRS Annals of Photogrammetry, Remote Sensing and Spatial Information Sciences, vol. -42, pp. 121-124, 2017. Available: 10.5194/isprs-annals-iv-4-w2121-2017.

[20]W. Simonson, H. Allen and D. Coomes, "Effect of Tree Phenology on LiDAR Measurement of Mediterranean Forest Structure", Remote Sensing, vol. 10, no. 5, p. 659, 2018. Available: 10.3390/rs10050659.

[21]U. Weiss and P. Biber, "Plant detection and mapping for agricultural robots using a 3D LIDAR sensor", Robotics and Autonomous Systems, vol. 59, no. 5, pp. 265-273, 2011. Available: 10.1016/j.robot.2011.02.011.

[22]M. Fontaine, S. Schrock and G. Ullman, "Feasibility of Real-Time Remote Speed Enforcement for Work Zones", Transportation Research Record: Journal of the Transportation Research Board, vol. 1818, no. 1, pp. 25-31, 2002. Available: 10.3141/181804.

[23]M. Kavaya, S. Henderson, J. Magee, C. Hale and R. Huffaker, "Remote wind profiling with a solid-state Nd:YAG coherent lidar system", Optics Letters, vol. 14, no. 15, p. 776, 1989. Available: 10.1364/ol.14.000776.

[24]E. Shang, X. An, T. Wu, T. Hu, Q. Yuan and H. He, "LiDAR Based Negative Obstacle Detection for Field Autonomous Land Vehicles", Journal of Field Robotics, vol. 33, no. 5, pp. 591-617, 2015. Available: 10.1002/rob.21609.

[25]C. Gardner, "Sodium resonance fluorescence lidar applications in atmospheric science and astronomy", Proceedings of the IEEE, vol. 77, no. 3, pp. 408-418, 1989. Available: 10.1109/5.24127.

[26]J. Harmon, M. Leone, S. Prince and M. Snyder, "LiDAR for Archaeological Landscape Analysis: A Case Study of Two Eighteenth-Century Maryland Plantation Sites", American Antiquity, vol. 71, no. 4, pp. 649-670, 2006. Available: 10.2307/40035883.