Surface Extraction by TIN-based Search space Minimization

  • What is SETSM
    • The DEM extraction algorithm, Surface Extraction with TIN-based Search-space Minimization (SETSM), is the first fully-automatic DEM extraction software specifically designed for sub-meter imagery over a range of terrain, including snow, ice and shadowed topography. The goal of SETSM is to automatically extract a stereo-photogrammetric DEM from pairs of images without any user-defined or a-priori information and using only the sensor Rational Polynomial Coefficients (RPC) for geometric constraints. Stereo-photogrammetric DEM extraction over mountainous and glaciated regions is particularly challenging due to low-contrast surfaces such as ice and snow and mountain shadows and steep slopes, resulting in large search areas for feature matching between stereo pairs. In this case, reducing the search space is critical for successful and efficient DEM extraction. The SETSM algorithm constructs a Triangular Irregular Network (TIN) in object-space domain in order to minimize the necessary search space. SETSM employs the coarse-to-fine and vertical line locus strategies described by Schenk (1999). The coarse-to-fine, or pyramid, strategy uses iteratively finer resolution TIN’s to minimize the search space. Once an initial TIN is produced, the vertical line locus provides additional geometric constraints for reducing the search space. SETSM uses Weighted Normalized Cross Correlation (WNCC) in object space as its basic matching engine and consists of the seven following steps in each coarse-to-fine iteration:
      1. Similarity measurement by rotation-invariant multi-patch WNCC combined with uncorrected and geometrically corrected NCC,
      2. First determination of the height of each grid in object space with WNCC peaks and adaptive WNCC coefficients,
      3. Outlier and blunder detection based on comparison between TIN’s for classifying anchor and candidate matching grids,
      4. Second determination of the optimal heights for candidate matching grids by triangle-patched GNCC
      5. Search space determination of each grid with intermediate TIN and WNCC peaks,
      6. Search space extension or reduction based on intermediate and current TINs
      7. Relative RPC update with parabolic adjustment of the WNCC solution.
    • An intermediate-level TIN is then created and used to re-weight the WNCC coefficients and set the adaptive threshold for matching. Finally, the search space is minimized and final heights determined. Since the geolocation accuracy of RPCs without ground control for WorldView-1 and 2 is 5m CE90 (DigitalGlobe, 2013), there is an offset between corresponding points projected by the vertical line locus. Where large enough, this offset can result in matching failure. Step 7 (relative RPC updating) provides an adaptive method for mitigating this error.
    • For any RPC-constrained DEM extraction algorithm there will be two common and dominant sources of error: blunders and RPC errors. Blunders are caused by incorrect matching of features between images, resulting in surface outliers. The iterative restriction of the search area in SETSM, as well as the blunder detection algorithm in step 3 above, substantially reduce blunders. Post-processing techniques can be employed to filter remaining blunders.
    • RPC errors are typically the result of errors in satellite positioning and look geometry, increasing with sensor look angle. These errors have two main effects: First, they result in misalignment of the stereo pair in the matching routine, resulting in poor match returns, which is mitigated in SETSM through iterative refinement of the search space. The second effect is a bias in DEM elevations. This bias can be reduced through GCP co-registration.
  • SETSM is designed for instant installation and user-friendly operation. SETSM is written entirely in the C programming language and requires no external libraries except libtiff. It requires no pre-existing terrain information or site-specific parameters, using only the information contained in the imagery metadata. SETSM is currently installed and running on HPC systems at the Ohio Supercomputer Center, NSF XSEDE and NASA.  Linux distributions of SETSM is now available for beta users.
  • Developers
    • Developer : Myoung-Jong (MJ) Noh, Byrd Polar & Climate Rsch Cntr, the Ohio State University.
    • Software engineering team: Judy Gardiner, the Ohio Supercomputer Center.
  • License
    • SETSM is released under the Apache 2.0 license, a copy of which is included in this website.
  • Download SETSM code
    • Installation instructions : SETSM is dependent on LibTIFF, version 4.0.3 or higher. Your system may already have LibTIFF installed. If not, you must download and install it separately. Download LibTIFF from and install it according to the instructions in the README file an SETSM manual. In addition, PROJ and LibGeoTIFF should be installed for SETSM output.
    • Makefiles are provided for building SESTSM with the Intel, PGI, GNU and Cray compilers. Select the appropriate Makefile.* based on the compiler you plan to use. Copy the selected file to Makefile and edit it if necessary to set the correct path to the TIFF library. SETSM can then be built simply by typing “make”. A CMake build is provided as an alternative to the Makefile method described above. The environment variable CC must be set to the compiler command to be used. If the TIFF library is in a nonstandard location its path must be provided using a -D flag.
    • Download : SETSM 4.3.0, SETSM user manual