Generate Digital Elevation Models Using Laser Altimetry (LIDAR) Data Christopher Weed Final Report EE 381K Multidimensional Digital Signal Processing December 11, 2000 Abstract A Laser Altimetry (LIDAR) system aboard an aircraft can yield highly accurate data about the ground surface and vegetation below. Raw LIDAR points must be processed to generate a digital elevation model (DEM), i.e. a digital map of the terrain surface. A number of techniques can be used to generate the DEM, and in this report I investigate several of these including a new algorithm based on recovering the lower envelope of a signal using amplitude demodulation. The default and most widely used technique consists of a series of thresholds based on local mean and variance measures. The amplitude demodulation technique runs much faster than the default technique and should be robust for flat and varying ground surfaces. Visual inspection of the entire image suggests that the amplitude demodulation technique achieves good results.Introduction Capable of achieving decimeter-level accuracy, laser altimeters are quickly becoming an indispensable tool for generating high-resolution topographic maps. Laser altimetry (LIDAR) data is collected by flying a laser over the area to be mapped. The laser is shot at the earth and the elapsed time to the first and last return pulse is recorded. The LIDAR system uses the elapsed time, GPS location, and other positioning information to create a set of 3-dimensional points of the surface below. In addition to achieving a high level of accuracy, the ability of the laser to penetrate the vegetation canopy opens the possibility of accurately mapping the ground surface underneath. A map of the ground surface, also called a digital elevation model (DEM), is an invaluable tool for hydrological purposes, such as studying water flow, erosion, and flooding. Unfortunately, the laser does not always penetrate the canopy, and it is necessary to process the data to produce a DEM. Another difficulty necessitated by the high accuracy of the LIDAR system is the volume of data produced by the system. Regions less than 100 km2 in area can produce greater than 25 gigabytes of data points. Therefore, data reduction and algorithm order are very important factors in any algorithm used for processing the data. Objective The objective of this project is to produce an accurate DEM for non-flat ground surfaces. The DEM should remove all vegetation while maintaining natural changes in elevation. Important factors for comparing algorithms include level of user interaction, accuracy of result, and speed of computation. The level of user interaction pertains to how much human input is necessary, including assumptions about the data, adjusting parameters, and post-processing results. Accuracy can be tested by comparing the results to ground truth where it is known, and visual inspection where ground truth is unavailable. The speed of computation pertains to the amountof time needed to produce a 1 m by 1 m DEM starting from the raw LIDAR data points. A reasonable test of computation time is whether a new algorithm is faster than the widely accepted default algorithm. Background The first step in many techniques for generating a DEM is to create a digital image by gridding the data points. This will drastically reduce the amount of data that needs to be processed from multiple data points in a grid cell to a single statistic per grid cell. The data points in a grid cell can be modeled as observations from a uniform random variable with the ground as the lower bound and the vegetation top as the upper bound. The first order statistic, i.e. the minimum, is an unbiased estimate of the lower bound [5]. Therefore, the data is gridded by assigning the elevation value of the minimum data point in a grid cell to that cell. In each grid cell, if the laser actually reflected off of the ground, the image value will be very close to the actual ground height. Otherwise, the image pixel will have some value above the ground surface. The default technique for generating a DEM is generally the commercial implementation included with the LIDAR processing system. The software from different companies vary, but many are based on the same set of operations [1]. These programs start with the minimum-gridded image and threshold values based on the minimum and variance within a moving window. The thresholding is repeated several times with different size windows and different thresholds. Pixels above the thresholds correspond to vegetation pixels, and pixels below the thresholds are considered ground pixels. The elevations of the ground pixels are used to interpolate values to replace the values of the vegetation pixels. Another useful technique for creating a DEM from LIDAR data is to grid the data and then segment different regions for processing. Anisotropic Diffusion Pyramids (ADP) can beuseful for segmenting regions with steep edges, often found around man-made features. Anisotropic Diffusion was developed to maintain edge transitions while smoothing homogenous regions [2]. This is achieved by changing the amount of smoothing according to the magnitude of the local gradient. The pyramid structure allows multiscale segmentation for varying sized regions [3]. Once the regions are segmented by ADP or any number of other possible algoriths, statistics about the regions and boundaries can be used to apply specialized techniques. Waveform Decomposition uses the actual LIDAR data values in a small region to select ground points [4]. A waveform is generated by binning the height value of points within a circular area (diameter of ~25 m). Generally, the waveform will have multiple peaks related to the ground and reflecting surfaces. Each peak is identified by fitting a Gaussian function to it. The gaussian component with the lowest mean represents the lowest reflecting surface and is assumed to be the ground surface. Proposed Method First, the data is gridded into a 1 m by 1 m grid based on the minimum data point in each grid cell. If the laser is able to penetrate to the ground, the minimum data value will accurately reflect the elevation of the ground surface. If all of the laser points in a grid cell reflect off of some part of the vegetation, the minimum data value will be higher than the elevation of the ground surface at that location. The grid cell value will not