Obtaining economical and accurate point clouds from semi-global matching.

In the old days, mappers were thrilled with 30 meter USGS digital elevation models (DEMs). These were available for almost everywhere in the United States. Years later they started producing 10m DEMs, and life was really good. We had one elevation point “on the ground” every 10 to 30m. This three-dimensional model of the Earth’s surface was sufficient to produce orthophotography from stereo aerial photography and meet many map accuracy standards.

SGM Advantages

Semi-global matching allows high-density point clouds of the first reflective surface to be rapidly and automatically extracted from stereo-imagery. In practice, it is not able to produce a point cloud for every pixel in the source imagery but only about every third pixel, which is still amazing. SGM is now commonly implemented in a variety of desktop mapping applications such as SimActive, Hexagon, Pix4D, and many others, including open-source versions like OpenCV.

SGM is now possible because of enabling computing technologies like GPUs (Graphics Processing Unit) and FPGA (Field Programmable Gate Array). These have enabled SGM especially for small images like those used in self-driving vehicles. But for creating point clouds in large batches of large images common in aerial photography, nothing short of Thor’s hammer in a PC is adequate for punching out SGM point clouds.

One advantage of SGM is that these point clouds look and feel much like lidar point clouds. SGM models can be colorized from the available imagery just like lidar and are generally available in LAS format. They are typically processed much like lidar data.

SGM Limitations

Semi-global matching suffers from two very important practical limitations. First, it can assign an elevation to only pixels in the image (that is, only those things photographed). Aerial photography is taken from above, so only the tops and sides of things are visible. The ground under a vegetative canopy or dark shadow is obscured. So our SGM DSM will contain only points on the surface of things, not the ground.

This point cloud cannot depict the Earth’s surface unless the bare earth is photographed, like at a gravel pit. One of the great advantages of USGS DEMs or stereo-compiled DEMs (“elevation” models) was that we were able to model the Earth’s surface. SGM point clouds cannot do this.

The second limitation is that a coordinate cannot be assigned to a pixel unless that same pixel is “found” in a second or third overlapping image. Imagery that contains scenes with very uniform texture (think fields of grass or corn, dense forest canopies, blacktop parking lots, dark shadows, etc.) cannot be modeled. SGM finds it nearly impossible to reliably find a second pixel that “matches” the first one in such “texture-less” areas. In these areas the SGM point cloud will contain holes, a void of points.

There is considerable work being done to improve SGM and better model these scenes, but it may never be possible until the resolution (GSD) of these areas improves. At much higher resolutions the canopy or parking lot that looks uniform green or black will have much more “texture,” and SGM will be able to better model those surfaces.

Fifteen years ago we could produce even better 3D Earth models by pulling up these stereomodels in our stereoplotters and digitizing a point on the ground every 5 to 10’. These were much more dense and could be used to produce more accurate mapping and orthos. Although accurate, they were, however, expensive because it took a human sitting at a stereoplotter plopping one point down on the ground every 5’ or so. On a typical project, there may have been two to three dozen stereomodels covering a few hundred acres, and it would take many hours of manual labor. 

Imagine if we could look at each pixel in a stereopair and assign an elevation to it. We could take our 6” GSD (ground sample distance) imagery and put an elevation point every 6” across our project area. That would be cool! 

That’s actually a not-so-new process (developed in 2005) called semi-global matching (SGM), aka photo-correlated digital surface models (DSM). (It is easy to miss the subtle distinction between “surface” models [DSMs] and “elevation” models [DEMs]. They are not the same, and important distinctions are discussed below.)

UAVs and SGM Point Clouds

Unmanned aerial vehicles (UAV) are an important consideration here. Today, I’m unable to photograph a parking lot from a manned aircraft at high enough resolution to improve its texture and model it with SGM. But I can fly much lower using a UAV and produce 1” or better GSD.

At these resolutions the “texture” of many surfaces is much better, and SGM modeling improves. This is one reason Pix4d and other software packages developed for UAV mapping include SGM-produced point clouds as an output. Unfortunately, UAV camera lenses are typically of such low quality that they make SGM more difficult and even less accurate.

So Why Do I Need Lidar?

How does SGM differ from lidar? Can I just produce 6” point clouds using SGM from my aerial photography instead of paying extra for lidar? Yes, but with limitations.

First, the SGM point cloud is a 3D model of the surface of things on the Earth, not the actual surface of the Earth (“bare earth”). If your application requires a bare earth point cloud, and you are not photographing the bare earth, forget it. SGM is not your tool. For mapping applications that require high positional accuracy of the ground, SGM will not work.

Second, as mentioned earlier, the SGM point cloud will have holes in it where the scenes have insufficient texture to model a surface. Even UAVs flying at 400’ AGL and taking photos with 1” GSD still cannot reliably produce good point clouds of many crop canopies because of the uniform carpet of low-texture pixels.

So there are limitations to SGM. But if your application can tolerate these limitations then these point clouds have an important application in your business. It is far less expensive to acquire aerial imagery and produce orthos, mapping, and a point cloud from them than flying it a second time using lidar to model the scene.

Lidar’s distinct advantages are wholly owned by lidar and will never be shared by SGM. First, lidar is an active sensor. It produces its own light. It is not measuring the reflectance of sunlight off objects like photography. It measures its own pulses of light and calculates distance (and position and elevation) of every reflected pulse.

Second, texture of the scene is irrelevant. Lidar does not require a second or third point reflected from an object to determine its precise location like SGM. One pulse will do. This is a huge advantage.

Third, lidar can penetrate canopies and reflect off the ground. This amazing attribute of lidar enables the mapping professional to model both the ground and the surface of things.

Last, lidar is generally more accurate than SGM for all these reasons.

At right is an orthomosaic from UAV data at 5cm; at left is corresponding DSM at 25cm. The typical noisy signature of the waterbody in the DSM is clear; the difficulty comes from the mirror effect of the lake when seen from above. Thus the basic assumption behind autocorrelation—that an object will not differ significantly in appearance from one viewpoint to another—is not valid.

Applications for SGM

Semi-global matching is a robust stereo method that has proven its usefulness in various applications ranging from aerial image matching to driver assistance systems. It is an important tool in the mapping professional’s arsenal of remote sensing tools and is a complement to lidar. It has important applications to the professional. When astutely applied it provides significant economic benefits. These tools help squeeze every penny of economy out of our projects and deliver meaningful solutions to clients that benefit our society.

Today, SGM has found many practical applications in city modeling, 3D visualization, volumetrics for mines and quarries, and site mapping for archaeology, to name a few. For the practitioner, looking for software from vendors that supports distributed processing and flexible licensing is an important consideration, especially for projects with thousands of images to process, because SGM requires such tremendous computer processing. Replacing the hard drive in your workstation or server with an SSD can improve SGM performance up to 10 times.

Acknowledgements to Philippe Simard of SimActive and Chris Ogier of Spicer for valuable input and imagery for this article.