Random Points: How Dense Are You, Anyway?

A 1.023Mb PDF of this article as it appeared in the magazine complete with images is available by clicking HERE

You may be noticing a race to high density (points per unit area) in point clouds obtained in aerial acquisition, whether they are obtained from direct laser scanning (LIDAR) or by correlating 3D points from imagery such as point clouds from small unmanned aerial systems.

Point density is a very important yet globally difficult to quantify aspect of a point cloud data set. Directly related to point density is Nominal Point Spacing (NPS), the "representative" distance between points in the point cloud. NPS determines the spatial resolution of information that can be extracted from the point cloud.

Figure 1 is a section of a point cloud from a helicopter scan of transmission lines. Of course, I have "zoomed in" so close to the cloud that we no longer can recognize features. Assume that the box in Figure 1 is 1 meter on each edge. This makes the area of the box 1 square meter (1 m2). The point density is then just the number of points in this box. Most LIDAR processing software (such as our own LP360) contain tools that allow you to compute the local point density within arbitrary shapes in the point cloud.

We usually measure point densities of different categories in the data. For example, the points in Figure 1 contain two dominate classes, ground (in orange) and unclassified (in grey). I could report the density of the ground class by "filtering" the data to only allow ground class points and then count the number of points in this class. Most LIDAR data acquisition specifications require a minimum density by class.

The Nominal Point Spacing (NPS) is the distance between points in the cloud. An examination of Figure 1 shows the problem with the NPS metric. Where would you measure the data to determine NPS? Due to the very nature of a point cloud (semirandom distribution of the points), the space between points is variable. In the example of Figure 1, there are point spacings ranging from just a few centimeters to over 50 cm.

The LIDAR Division of the American Society for Photogrammetry and Remote Sensing (you should join if you are not a member–www.asprs.org) has wrestled with defining NPS for years. Proposals have ranged from a simple sampling technique to a sophisticated method based on Voronoi diagrams ("LIDAR Density and Spacing" Ty Naus, 2009).

Though we have yet to create a formal definition of NPS, it seems the industry has settled on the averaging method. The average NPS at a localized area within the point cloud is related to the density at that area by the reciprocal square root; NPS = 1/Sqrt(Point Density) and, by reversing the expression, Local Point Density = 1/NPS2. You will note that Version 1.0 United States Geological Society "LIDAR Base Specification" specifies these parameters in terms of Nominal Point Density (2 meters) but the method of assessment is a gridded, density-based approach. As far as I am concerned, a satisfying approach to specifying and measuring point cloud density remains an open topic.

A related concern is that of nonuniform point spacing. This is nicely illustrated in Figure 2. Here the flight direction was from west to east (left to right in the diagram) so the "along track" direction is left to right and the "cross track" direction is up/down. For most aerial laser scanners at a given altitude, the cross track point spacing is determined by the scanner frequency (pulses per second) whereas the along track (or "in track") spacing is determined by the speed of the aircraft. Note in Figure 2 the considerable imbalance of these two parameters; either the scan frequency needed to be decreased or the aircraft speed increased. The version 1.0 USGS LIDAR Specification addresses the uniformity of point spacing although tools to specifically quantify this attribute are lacking in the industry.

You may recall that in a previous edition of Random Points, I discussed the Nyquist Sampling Criteria. This rule, from digital sampling theory, says that we can extract information from a digitized signal that has a spatial frequency that is half the sampling frequency (given some other constraints such as frequency limiting the data set). Basically this means that if I have an NPS of 1 meter in the X direction, the smallest features that I can accurately model within the data set are features with spatial extents above 2 meters (half the sampling frequency). These conditions apply in an orthogonally independent way which means that I can consider X, Y and Z independently.

We see an artifact of this in data sets with long but narrow linear features such as road paint stripes and electric wires. While the cross-wire sampling density is far from being small enough to adequately model the wire, the alongwire point spacing is fine. Consider the image in Figure 3 of a helicopter LIDAR scan of transmission lines. The point density is about 36 points per meter2 which yields a nominal point spacing of about 16.6 cm. This is far too coarse to detect a wire yet due to the along line dimension, we have a solid representation of the wires.

NPS is critically important when generating derivative products such as gridded elevation models. The Nyquist criteria says that we cannot generate an accurate sampled model with a point spacing less than twice that of the original sampling data. This means that if I have 2 meter NPS LIDAR data, the minimum spacing in a gridded model derived from these data must be 4 meters. It is always accurate to go larger (for example, a 5 meter gridded model from 2 meter NPS data) but a special subsampling technique must be used (called "spatial frequency filtering"). Of all of the technical errors that I see in point cloud data processing, this violation of the Nyquist criteria is the most common. For example, I have seen specifications for 0.7 meter LIDAR acquisitions with a grid product of 1 meters spacing as a required deliverable.

The bottom line here is that you should plan point cloud collections (whether from laser scanners or image correlation) with uniform sample spacing with a resolution of at least twice the derivative product requirement. This may be one of the few cases where the denser you are, the better!

Lewis Graham is the President and CTO of GeoCue Corporation. GeoCue is North America’s largest supplier of LIDAR production and workflow tools and consulting services for airborne and mobile laser scanning.

A 1.023Mb PDF of this article as it appeared in the magazine complete with images is available by clicking HERE