|
Automated and Interactive Processing of LiDAR Data:
A Discussion of Technical and Economic Aspects of 3D Feature Extractions
 Gerhard Sehnalek Technical Director Infotech Enterprises Limited India gerhard.sehnalek@infotech-enterprises.com Ch Raghu Babu Challagulla Infotech Enterprises Limited India Introduction Airborne LiDAR (light detection and ranging) technology provides geo-referenced 3D point measurements over a reflective surface of natural and man-made features (Wehr and Lohr, 1999). In order to utilize the LiDAR data for the generation of contours within geographic information system (GIS) applications, the data requires automated and interactive processing steps. The current advanced airborne LiDAR systems produce high point density with pulse repetition rate of over 150 kHz; in addition to, intensity data and additional parameters resulting in data accuracy of 15 cm absolute and relative accuracy from point-to-point within the dataset of 2-4 cm. Most modern lasers collect millions of 3D points per minute with ground point density of one point every square meter to 40 or more points per square meter, depending on flying height, air speed, equipment set-up, and other variables. LiDAR data is collected from everything the laser hits: the ground, buildings, trees, small structures, moving, standing cars, etc. These 3D data points are floating in space as a 3D model and this is what is referred to in LiDAR vernacular as a "point cloud." Since a digital terrain model (DTM) is generated by interpolating LiDAR measurements for the terrain, measurements for non-ground features, such as buildings, trees and vehicles have to be removed from the LIDAR dataset before interpolation.  Figure 1: LiDAR Returns When one views a LiDAR point cloud it is understandable that the discrimination of exactly what the LiDAR beam bounces off is not very obvious, but once classified the features can be identified. Spatial analysis alone is often inconclusive when attempting to determine whether a LiDAR point has hit a small bush, fire hydrant, boulder, or a ground surface anomaly. This is even more difficult when this process is based on automated filtering methods over the urban landscape. Conventional surface classification filters can only go so far when removing above ground phenomena, as natural and artificial objects may be spatially interpreted similarly and subjectively removed, and therefore inadvertently eliminating valid surface detail without differentiation. A quantitative and qualitative test of filtering methods conducted by the ISPRS WGIII/3 (Sithole and Vosselman, 2004) in 2004 has shown that while most of these methods handle most types of landscapes (as shown in figure 1) The importance and challenges associated with filtering LiDAR data are best manifested by the large number of algorithms that were developed over the years that can be found in a variety of software packages. Special algorithms were developed for specific targets and conditions; however, they displayed limited results when applied to diverse urban conditions (Cheng Qi,et.al., 2007). Rough classifications of these algorithms are shown in the following categories: morphological analysis; terrain densification; edge based, robust interpolation and segmentation based; which are further enhanced by multiple interactive settings of parameters (Keqi Zhang, 2005). Photogrammetric methods for DTM generation are very time consuming and labor intensive. A photogrammetric model needs to be formed using digital aerial imagery and orientation parameters. An experienced stereo-compiler manually digitizes geomorphic features such as, drainage, road edges, sides and bottom of ditches, stream bank, etc. These lines are called “hard breaklines” whereas the undulations in the topography mapped are called “soft breaklines” followed by spot heights at a regular or irregular interval. Afterwards the DTM is generated from these breaklines and spot heights by using sophisticated software and various algorithms, mostly by building a Triangular Irregular Network (TIN) and contours.  Figure 2: Section of Digital Orthophoto LiDAR data has been used as a source and a tool to produce accurate digital terrain models (DTMs). The data has been quickly accepted and established over the past decade and has resulted in the increased productivity in the field of DTM and contour generation. Initial thoughts were that LiDAR data alone could define the terrain but in many cases the requirement to supplement the terrain model with breaklines became apparent. In urban areas the development of a DTM from LiDAR points showed different challenges, mostly the elimination of above ground features and the need for breaklines, to clearly define the most man-madeterrain features - even with today’s high-repetition rate LiDAR sensors. In general, interactive methods applied to the identification and modeling of complex man-made terrain represent the highest cost of post processing, the DTM development and contour generation tasks. The dataset used for this presentation covered an urban area in the Borough of Staten Island, New York City, which included a large commercial structure, several apartment buildings with parking areas, and small residential buildings and structures. We randomly selected three commercial off-the-shelf (COTS) software packages; Merrick MARS™; Overwatch Geospatial LiDARAnalyst™ and Terrasolid TerraModel™ (listed in alphabetical order) for our study to see if the automatic processed LiDAR dataset of an urban area requires additional breakline collection for the contour generation. This paper discusses the results of the test over the same area to obtain bare earth information for high accurate digital terrain model that could be used for 2 foot (60 cm) contour generation. Terrain Filtering Methods With the inception of high pulse rate airborne LiDAR technology, the use of LIDAR for height measurement and the resulting elimination of above ground points has been enhanced and automated. The goal is to obtain only ground points that can be used for contour generation with the least amount of interactive editing. As a prerequisite for the DTM generation and contour development the ground points need to be separated from non-ground points. In general terms, a digital surface model (DSM) is generated from an original LiDAR point data then through a set of parameters and techniques bare earth elevation points are created. Relatively little is known about the various filtering methods and their accuracy, computation complexity, and sensitivity to filtering parameters, despite the many algorithms that have been created for the various software. Buildings and trees are separated based on surface roughness measured by differential geometric quantities. The software parameters (filters) are applied to maintain the fine details in the terrain. Filtering of laser data can be viewed as a classification problem with two classes, the bare earth and above ground features. This classification can be approached by point driven and area driven strategies. In general, a point driven classification will be more effective in vegetated areas, if terrain points are too sparse to be grouped into segments. An area driven classification will be more effective in urban areas that are generally smooth and where points tends to cluster into big segments (Sithole and Vosselmann, 2003). Like most feature extraction tasks, building extraction and non-ground points in general can be implemented in either semiautomatic or automatic strategies using data-driven and/or modeldriven techniques. Some algorithms process the raw LiDAR point clouds directly or develop grid-based images converted from LiDAR data; while others use different data structures at different processing stages. There are many papers and studies about the correct extraction of building outlines which will not be discussed. We were mainly interested in the correct elimination of these points from the dataset to obtain the best ground points within the vicinity of the buildings and structures. Figure 3 shows a bare- earth polygon generated by the LiDARAnalyst™ software combined with building points generated with TerraModel™ software.  Figure 3: Bare Earth Polygon with Building Points Regardless of the software used, the first task is to separate the ground and non-ground LiDAR measurements using different filters. For example a progressive morphological filter; or a filter is based on a maximum local slope filter where a ground measurement is defined by comparing local slopes between LiDAR points and its neighbors may be applied to the LiDAR dataset (Zhang & Whitmann, 2005). Other filtering methods are based on elevation threshold or point smoothing. The latter should not be used in urban areas where small elevation changes such as road curb lines are present and would be completely smoothed out. Afterwards, building measurements are identified from non-ground measurements using a region growing algorithm (i.e. based on the plane-fitting technique and finally all non-ground points are eliminated from the point cloud). Interactive Data Collection Due to the high density of the LiDAR points, the interactive data collection is limited to the editing of wrongly identified points and to the collection of breaklines to further enhance the DTM. The origin of the breaklines often is a matter of contention and will most likely distort the accuracy. Digital orthophotos commonly used as a source provide only 2D horizontal information and in most cases the accuracy is less than the LiDAR data, which introduces more error to the final surface. Traditional photogrammetric methods for breakline collection using digital images forming stereo models in a 3D environment are well described. In most cases, LiDAR data acquisition is not coincident with the image acquisition but is when using LiDAR data within the photogrammetric workflow, a concept called LiDARgrammetry which enables the production of traditional mapping products without the need for aerial photography. As a result, using LiDARgrammetry to process and classify LiDAR data has made DTMs and contours from LiDAR more inexpensive than from conventional photogrammetric compilation. LiDARgrammetry involves the use of synthetic stereo pairs created from LiDAR intensity images. Pre-processing the LiDAR data to create the stereo pairs is comparable to processing and editing digital images and aerial triangulation. Additionally, classifications of LiDAR data can be incorporated into the stereo pairs. The most common type of pair is the intensity pair from the first or last return of the LiDAR pulse. As with the photogrammetric process, these stereo pairs are used to see three dimensions in a soft-copy photogrammetric environment and allow a technician to review only the ground surface, allowing for obstruction free, building free, and vegetation free collection of breaklines. A second type of pair may be developed using intensity blended with classification. This colorized version of the intensity image provides opportunity to analyze the automated Classification and to manually edit the data or re-run the classification algorithms. The misclassification of LiDAR points falling on buildings and vegetation can be easily identified and corrected. In addition, a stereo operator can collect the breaklines for better terrain definition or collect a polygon around the area for the purpose of automated re-classification. Terrain Modeling Advancements in 3D terrain modeling software capabilities and user knowledge are the driving force behind the development and generation of DTMs suitable for contour generation from LiDAR data and accurate surface models. To create LiDAR-based contours that meet cartographic and geometric qualities, LiDAR data with modest post spacing of around 2 to 4 meters can be augmented with breaklines derived from image-based photogrammetry. If imagery is not available for breakline production, then a “LiDARgrammetry” approach is possible. Once the breaklines are collected the LiDAR points can be thinned depending on the complexity of the terrain. The thinned dataset is then merged with the breaklines to create a digital terrain model (DTM) which is required for generating the contours. In addition, all LiDAR points within a buffered distance without sacrificing accuracy. The issue of utilizing breaklines in modeling contours from around the breaklines should be removed to achieve acceptable contours LiDAR data often gets problematic when very dense and accurate LiDAR data is mixed with manually collected and possibly less accurate breaklines. In order to produce contours to the highest cartographic standards, the LiDAR points close to the breaklines need to be buffered or thinned. A good quality DTM for contour generation is achieved by having accurately modeled breaklines and minimum mass points outside the breaklines when necessary. Methods Used to Analyze Filtering Errors There are two basic errors in filtering LiDAR data. One is to classify non-ground measurements (data points) as ground points and the other is to select ground points as non-ground measurements. The former is called commission error (termed Type I error) and the later is omission error (Congalton, 1991) (termed Type II error). All filtering methods are subject to these two errors in various degrees. Based on this terminology, Type II errors have a greater effect than Type I errors, since missing a few terrain points is not equivalent to inserting nonterrain elements into the terrain representation. To compare the results of the three software solutions the results and/or errors need to be examined and because of practicality we selected qualitative and quantitative methods to examine the errors. The qualitative approach checks errors by comparing the completeness of removing features such as buildings, cars, trees, etc or preserving the bare earth points. The quantitative method examined errors by comparing unfiltered and filtered measurements. The resulting points were overlaid on digital orthophotos and classified visually as being ground or non-ground features. Color stereo images obtain from a digital camera were established to perform the tasks in a 3D environment by simultaneously displaying the images and the LiDAR points. Conclusion We can conclude with the following statement that all filters perform well in smooth rural landscapes, but produce errors in complex urban areas.(quote come from where?) Most filters perform poorly with ramps, bridges, and disconnected terrain (courtyards). The results presented show that no filter can be regarded as the universal “best filter algorithm”. LIDARgrammetry and photogrammetric methods are still necessary within urban landscapes to achieve high accurate DTMs and contours. A quantitative analysis showed that 85% of all points were classified correctly. Most importantly a quantitative analysis showed that the total of omission and commission errors for extracted footprints for both institutional and residential areas was about 12%. The preliminary results show that commissions and omission errors are quite few, and that omission errors (Type II errors) can be generally found for individual points around buildings where the definition of where the terrain ends is vague. Generally, no noticeable cluster of misclassifications can be noticed in the data. On an average, 90-100 sq. km. area can be measured in one hour using a high-peformance LiDAR system. A typical post-processing time for LiDAR is two to three hours for every hour of recorded flight data. Additional processing time required for more sophisticated analysis such as target classification, parameter setup, automatic classification and post processing of the LiDAR data as well as manual breakline collection/ data editing varies by terrain complexity and averages normally 1 hour/sq. km. The use of LiDAR data has shown us that significant cost savings can be achieved on contour projects covering large urban areas. References |