Data Processing Requirements
Considering the mission (You work for a utility company. Your team has been tasked with equipping an Unmanned Aerial Vehicle (UAV) for powerline and infrastructure inspection) your team chose and the commercially available products you identified in earlier modules, use this module’s reading assignments to create a report/presentation/proposal that provides an in-depth description of the following:
· The data processing strategies and software that are available for the proprioceptive and exteroceptive sensors you have selected (identify and justify the software package that you would choose for processing mission-specific data).
Remember that you are making a case to your company’s leadership and that your format can consist of 3-5 slides. Regardless of how you choose to present the content, please include an APA-compliant reference list. You do not need to use APA format, but you do need to be able to support whatever you say with external references.
Helpful information if you want to consider Lidar:
Basics of LiDAR Data Processing
3.1 INTRODUCTION As explained in Section 2.2 of Chapter 2, values of ranges and scan angles, differential global positioning system (DGPS) and inertial measurement unit (IMU) data, calibration data, and mounting parameters can be combined to derive (x, y, z) coordinates of LiDAR points. It is worth mentioning that since global positioning system (GPS) uses the World Geodetic System of 1984 (WGS84) datum, the originally derived three-dimensional (3D) coordinates are also georeferenced to the WGS84 datum and its ellipsoid (this means that z is ellipsoidal elevation). However, LiDAR users typically need orthometric elevation (i.e., elevation above mean sea level or a geoid model) for hydrological applications such as flooding or sea-level rise analysis. Moreover, each country or region often uses a horizontal datum that is more locally relevant (e.g., the NAD83 for the United States and Canada) in geographic information system (GIS) analysis. Therefore, a LiDAR vendor often needs to transform the original 3D coordinates of laser points from WGS84 to a new horizontal datum and/or a new vertical datum, especially upon the request of the end users. The processing and analysis methods for LiDAR data are usually applicationspecific (for example, multi-scale modeling for building extraction), and many new methods are being proposed. Therefore, it is difficult to provide a complete list of various LiDAR data processing and analysis methods. However, two basic steps are usually needed: (1) classification of laser points and (2) interpolation of discrete points into a continuous surface. For example, the generation of digital terrain model (DTM) requires the classification/extraction of ground returns and the interpolation of ground returns into raster or triangulated irregular network (TIN). The classification of laser points means identifying the type of earth surface materials or objects that generate the laser returns/points. For example, a laser pulse that is transmitted from an airplane to a tree may generate three returns: the first return from the tree crown surface, the second return from the branches and foliage below the surface, and the last return from the ground below the tree. Some users may only want to classify the points into ground versus non-ground returns because their purpose is to use the ground returns to generate a DTM. However, a forester who is interested in analyzing canopy vertical structure might want to separate the points into three categories: on canopy surface, within canopy, and on the ground. Therefore, the classification scheme used in different applications could vary substantially. Despite these, a common class that needs to be extracted is the ground returns. This is because (1) ground returns are needed to generate “elevation” models for topography (i.e., DTM), arguably the most widely used geospatial data, and (2) DTM is needed to produce different “height” products for surface objects above topography. For example, building height can be calculated as the difference between elevation of laser points on a building’s roof and DTM. Extracting ground returns from a point cloud is usually the first step of LiDAR data processing and the most important classification. Conventionally, this step is called “filtering” because the main driver of adopting airborne LiDAR data in its infancy stage (in the 1990s) was to generate DTM, which needs filtering out or removing non-ground returns. Because of its importance, filtering is introduced in Section 3.2 while classification of remaining non-ground returns is introduced in Section 3.3. Unlike optical or radar imagery, airborne LiDAR data do not continuously measure or map the earth’s surface. Each laser pulse and its returns are essentially samples of the environment, even at very high point density. Interpolation is needed to produce spatially continuous digital products or maps from these discrete points. For example, interpolating the ground returns and the highest returns will generate DTM and DSM (digital surface model), respectively. Although various interpolation methods exist in software, they have to be fast enough to process massive LiDAR points and intelligent enough to predict the elevation at the unsampled locations. Section 3.4 will discuss some common interpolation methods. Figure 3.1 is a typical flowchart showing the major steps for LiDAR point data processing. After collecting (x, y, z) coordinates of LiDAR points, sorting of the points can improve the efficiency of data rendering and processing (Auer and Hinz 2007, Scheiblauer 2014, Shen et al. 2016). In addition to geometric processing of LiDAR points, it should be noted that LiDAR intensity information can also be useful. A review of LiDAR radiometric processing can be found in the work of Kashani et al. (2015). In the remainder of this chapter, we will introduce filtering, classification of non-ground returns, and spatial interpolation, respectively. Two ArcGIS projects are then presented to (1) create a DTM, a DSM, and a digital height model (DHM) for an area in Indianapolis, IN (USA), and (2) create a terrain dataset for an area in St. Albans, VT (USA).
3.2 FILTERING Filtering is used to remove non-ground LiDAR points so that bare-earth digital elevation models can be created from the remaining ground LiDAR points. Over the past two decades, many filtering methods have been developed (Axelsson 2000, Sithole and Vosselman 2004, Arefi and Hahn 2005, Tóvári and Pfeifer 2005, Chen et al. 2007, Kobler et al. 2007, Liu 2008, Chang et al. 2008, Meng et al. 2010, Wang and Tseng 2010, Chen et al. 2013, Pingel et al. 2013, Zhang and Lin 2013, Lin and Zhang 2014, Zhang et al. 2016, Nie et al. 2017). Most filtering methods are unsupervised classifiers, which mean that users do not need to collect training data for ground and non-ground returns. However, they may have one or multiple parameters that need users to specify the values. The design of a filtering algorithm is usually based on two criteria: (1) the ground has the lowest elevation compared to the objects above it (e.g., Kobler et al. 2007), and (2) elevation and slope change more slowly for bare earth than for DSM (e.g., Chen et al. 2007). However, the specific techniques that implement these criteria differ so dramatically that it is not possible to explain the details of each. As a start, readers can refer to Sithole and Vosselman (2004), which summarized characteristics of filtering algorithms from different aspects including data structure, measure of discontinuity, and filtering concepts. Among the large variety of filtering algorithms that have been developed, surface-based approaches are probably the most popular and effective ones and have been implemented in many commercial or free software (e.g., Kraus and Pfeifer 1998, Axelsson 2000, Chen et al. 2007). Surface-based approaches usually start with an initial surface that approximates the bare earth and then generates another approximate surface of the bare earth that utilizes the information from the previous step. This process could be repeated iteratively until the next surface does not substantially differ from the previous one. This is similar to the process of k-means or ISODATA (Iterative Self-Organizing Data Analysis Technique) classification for which the algorithm stops when the classification results from the next round do not differ from the previous round (in other words, the algorithm stabilizes or converges). What is unique to LiDAR point cloud filtering is that an approximation of the bare earth surface has to be generated at each step, which is usually, but not always, implemented using interpolation methods. Surface-based approaches can be based on either TIN or raster.
3.2.1 TIN-Based Methods TIN is a vector-based data structure for representing continuous surface. Specifically, a TIN surface consists of a tessellated network of non-overlapping triangles, each of which is made of irregularly distributed points. TIN is well suited for constructing terrain surface from LiDAR points because: (1) LiDAR points are often irregularly distributed due to variations in scan angle, attitude (pitch, yaw, and roll) of the airplane, and overlaps between flight lines; (2) adding or removing points into TIN can be implemented locally without reconstructing the whole TIN; and (3) the speed of constructing a TIN is usually much faster than the grid-based interpolation methods.
They are many different triangulation networks, but the Delaunay triangulation is the standard choice. The algorithm proposed by Axelsson (2000) is probably the most famous TIN-based method, which works as follows: (1) the lowest points within a coarse grid are chosen as seed ground returns, which are used to construct an initial TIN. The grid size should be large enough (e.g., 50–100 m) to ensure that the lowest point within each grid cell are ground returns, (2) points are added into the TIN if they are close to the triangular facet and the angles to their overlaying triangular nodes are small, and (3) the densification of the TIN continues until no more ground returns can be added. The main idea of Axelsson (2000) is to start with a small set of ground returns and then iteratively add the remaining the ground returns. Different from such an “addition” strategy, ground returns can also be extracted via “subtraction”: start with all returns and then iteratively remove non-ground returns; the remaining points in the end of iteration are ground returns. For example, Haugerud and Harding (2001) first used all returns to generate a TIN surface, which was smoothed using a 3 × 3 moving window; then elevation difference was calculated between each laser return and the smoothed surface. If the difference was larger than a threshold, the point was removed. This process was repeated until a convergence threshold was reached. Note that their algorithm was designed for forest areas and it cannot efficiently remove large buildings with flat roofs. Because non-ground returns and their TIN facets appear as spikes on top of DTM, such “subtraction” algorithms are also called “despike” methods. The TIN-based method proposed by Axelsson (2000) has some limitations in removing points belonging to lower objects and preserving ground measurements in topographically complex areas. Nie et al. (2017) proposed a revised progressive TIN densification method for filtering airborne LiDAR data using three major steps (Figure 3.2): (1) specify key input parameters; (2) select seed ground points and construct an initial Delaunay TIN; and (3) iterative densification of the TIN. Both qualitative and quantitative analyses suggest that the revised progressive TIN densification method can produce more accurate results than the method proposed by Axelsson (2000)
3.2.2 Raster-Based Methods An alternative data structure for terrain surface is raster. Various interpolation methods (also called interpolators) can be used to generate raster grids from points. Interpolators can be exact or inexact, depending on whether the interpolated surface will go through the points or not. Interpolators can also be different depending on whether the interpolated elevations exceed the range of LiDAR point elevations. This is different from TIN because the interpolated values always go through the LiDAR points (an exact interpolator) and never exceed the range of LiDAR points. Therefore, using rasters to store terrain surface offers much flexibility for the algorithm developer to choose an appropriate interpolator. The interpolators that were often used are kriging, thin-plate spline (TPS), inverse distance weighting (IDW), and natural neighbors. Similar to TIN-based approaches, raster-based filtering algorithms can be designed based on either an “addition” or “subtraction” strategy. As an example of the “additive” method, Chen et al. (2013) developed a multiresolution hierarchical classification (MHC) algorithm for separating ground from non-ground LiDAR point clouds based on point residuals from the interpolated raster surface. The MHC algorithm uses three levels of hierarchy from coarse to high resolutions, and the surface is iteratively interpolated towards the ground using TPS at each level, until no ground points are classified. The classified ground points are then used to update the ground surface in the next iteration. Kraus and Pfeifer (1998) were among the first to develop a “subtractive” raster filtering algorithm. Using simple kriging (also called linear interpolator in their paper), they first fitted a surface using all returns. Then, points with large positive residuals are removed and the rest are assigned with weights according to their residuals: points with large negative residuals are more likely to be ground returns and therefore assigned with larger weights. The surfaces are iteratively refitted with remaining points with weights until convergence. Many algorithms interpolate raster grids and filter points at multiple spatial resolutions or scales. Some progress from fine to coarse scales. For example, Evans and Hudak (2007) implemented a raster-based “subtraction” algorithm, which modified the method of Haugerud and Harding (2001) to generate raster surfaces at three gradually decreasing resolutions using TPS interpolation to iteratively remove nonground returns. In contrast, some algorithms use gradually increasing spatial resolutions (Mongus and Žalik 2012). For example, Mongus and Žalik (2012) started with an interpolation at a spatial resolution of 64m × 64m and identified non-ground returns based on the interpolated surface; the interpolation and filtering processes gradually increased to 32, 16, …, and 1 m resolutions. One of the main challenges in interpolation from points to raster is the demanding computation involved because (1) a LiDAR file typically has several million points per square kilometer, and (2) interpolation usually involves the use of points within each point’s local neighborhood, which requires extra computation resources for indexing and searching. Therefore, an efficient algorithm would minimize the use of interpolation in its filtering process. For example, Chen et al. (2007) first created a fine-resolution (e.g., 1 m) raster grid that contains the elevation of the lowest points and then used image-based morphological operations (more specifically, opening) to remove aboveground objects such as buildings and trees. To identify buildings of different sizes, they used neighborhood windows of gradually increasing sizes for morphological opening. Their algorithm used the fact that buildings have abrupt elevation changes at their edges to separate buildings from small terrain bumps and thus is called edge-based morphological methods (Chen 2009). Ground points were identified by comparing each point with the final morphologically opened raster (which approximate the bare earth). Kriging was used finally to interpolate a smooth DTM. Since interpolation is used only once, the algorithm is fast and efficient.