Research and development

October 2009 | Research and development

Stereo image matching: breakthroughs in automated change detection

An NGATE analysis of a WorldView-1 satellite image of Beijing’s Bird’s Nest Stadium shows a DSM as cyan contours and a DEM as red contours (inset). Both are two-meter intervals. In the middle of the stadium, the DSM and DEM have blunders due to moving objects, which makes it difficult for a human operator to place an extraction cursor on the ground. In the upper left corner, the water body also causes DSM and DEM blunders. BAE Systems’ forthcoming automatic water body extraction will address this problem (Image courtesy of DigitalGlobe).

In a good stereo pair, humans readily fuse the two images and perceive a 3-D scene. The relief may be exaggerated, but our brains are comfortable with the presentation. Similarly, stereo correlation algorithms used for automatic terrain extraction operate nicely on good stereo pairs. But localized differences between stereo image pairs can cause headaches for humans and correlation software alike. For human observers, these differences confound our natural stereoscopic vision. It is immediately apparent that something isn’t right. The differences also confuse image-matching terrain-extraction software. The results include spikes, wells and other elevation anomalies that previously required manual editing to correct. BAE Systems recently developed an algorithm to automatically detect and remove false matches caused by moving vehicles as part of Next-Generation Automatic Terrain Extraction (NGATE) enhancements for the company’s SOCET SET and SOCET GXP photogrammetry software. The algorithm also provides an automated way to detect change between image pairs, including change caused by moving vehicles. Importantly, the method works well with either panchromatic or multispectral images. The two accompanying case studies illustrate the use of the NGATE stereo image matcher in moving vehicle change detection, and removal of digital terrain model (DTM) defects caused by change or motion. Read the complete study >>

December 2008 | Research and development

Simultaneous generation of DSM and DEM

Submitted by Dr. Bingcai Zhang, Engineering Fellow

NGATE can generate an accurate and dense digital surface model (DSM) that includes buildings, houses, trees, etc. from stereo images. In many applications, a digital elevation model (DEM) or bare-earth model is required. Transforming a DSM to a DEM is an expensive manual operation. In SOCET SET® v5.4.1, a number of new bare-earth tools were developed to speed up the DSM to DEM transformation. However, each tool is designed for a specific type of DSM and usually for a small area. Users still need to digitize a polygon to define an area. Most new bare-earth tools require a set of parameters and they are sensitive to these parameters. As a result, users may still need significant training and additional manual intervention for ideal results. In previous versions of NGATE, the “Eliminate Trees/Buildings/Other” option did not perform well.

Future development plans for NGATE in SOCET SET v5.5 and SOCET GXP v3.1 include capabilities for generating a DSM and DEM simultaneously. Initial tests based on three production projects indicate that the DSM is more accurate than the DSM generated with NGATE v5.4.1. Testing the NGATE v5.5 DEM shows that very few houses, buildings, and trees remained in the DEM while bare ground is preserved with high-quality and high-resolution images. The first project has 106 color images, 13824 by 7680 pixels, with a GSD of 0.248 feet. The project covers suburban areas of moderate terrain with many houses. Most houses and trees are removed from the DEM, while the DSM is more accurate than the DSM from v5.4.1 NGATE. The second project has 329 4-band images, 13824 by 7680 pixels, with a GSD of 0.2 meter. The project covers rural areas with many trees. Most of the trees are removed from the DEM while preserving the bare ground, even in very steep areas. The third project has 21 scanned color images, 19000 by 19000 pixels, with a GSD of 0.76 feet. It covers steep suburban areas with many buildings and houses. These are considered difficult areas for the DSM to DEM transformation.

Viewing these 3-D images requires red and blue anaglyph 3-D glasses. Cardboard anaglyph glasses can be purchased for about thirty cents from the following Web site: www.rainbowsymphony.com/freestuff.html

Figure 1. Project One. Top image is a DSM with two-foot contours; bottom image is a DEM with two-foot contours.

Figure 1. Project One. Top image is a DSM with two-foot contours; bottom image is a DEM with two-foot contours.

Figure 2. Project Two. Top image is a DSM with one-meter contours; bottom image is a DEM with one-meter contours.

Figure 2. Project Two. Top image is a DSM with one-meter contours; bottom image is a DEM with one-meter contours.

Figure 3. Project Three. DEM with five-meter contours.

Figure 3. Project Three. DEM with five-meter contours.

Research and development | September 2006

Next Generation Automatic Terrain Extraction (NGATE)

Next Generation Automatic Terrain Extraction (NGATE)

Next Generation Automatic Terrain Extraction (NGATE)

With MSN® Virtual Earth and Google Earth, 3D geospatial data is finding its way into daily life. A digital terrain model (DTM) is one of the most important 3D geospatial data types. One of the key automation technologies in softcopy photogrammetry is to generate a DTM automatically. The most reliable and widely used algorithm for DTM generation is normalized image correlation. However, this algorithm has limitations when dealing with elevation discontinuities such as building edges, because it is based on the assumption that elevation within a window hardly changes.

NGATE, a remarkable innovation invented by GXP’s Dr. Bingcai Zhang, provides automatic generation of DEMs and DSMs and, as far as we can judge from the experiments we have conducted to date, far outperforms ATE. The algorithms behind the NGATE technology are ingenious. NGATE uses both image correlation and edge matching. The edge matching algorithm can deal with building edges or elevation discontinuities well. The results from image correlation are used to constrain and guide the edge matching process. At the same time, the results from edge matching are used to assist image correlation.

We applied NGATE on 66 images (GSD = 0.14 feet = 1.68 inches = 4.3 cm) acquired with a Microsoft UltraCam-D digital airborne camera over an urban area. The resulting DTM with 21 million 3D points from NGATE has the following characteristics:

  • On natural terrain, the NGATE DTM has an RMS (root mean square) error of 0.4 feet in height
  • On streets and parking lots, NGATE DTM has an RMS error of 0.3 feet
  • On center points of flat roof buildings, NGATE DTM has an RMS error of 0.5 feet
  • On corner points of flat roof buildings, NGATE can capture 94% of corners with an RMS error of 0.9 feet
  • On center points, edge points, corner points, and ground points of complex buildings, NGATE DTM has an RMS error of 0.9 feet. 90% of these points have an RMS error of 0.4 feet
  • Building edges are well preserved
  • Streets are precisely modeled
  • Positions and shapes of residential houses are accurately depicted

The above results must be considered in perspective. No editing was conducted prior to the computation of the RMS values. Owing to the design of the flight mission, the parallactic angles subtended by many of the points were small, i.e., not all of the base-height ratios were optimal. And the RMS of 0.9 feet at building corners is impressive given that those are the most challenging points for traditional image matching.

DTMs from NGATE are very dense and accurate — similar to LIDAR data. We have used LIDAR data to extract 3D buildings with encouraging results and we expect that we may achieve similar success with DTM from NGATE as a part of our ongoing research.