Follow this link to skip to the main content

JPLV Stereo Ranging

Algorithm Name: Stereo visual ranging Date: Sep 19 2007
Tech Provider: Andrew Howard
Steve Goldberg
 Institution: JPL
Tech Integrator: Andrew Howard
 Integration Level: I
NOTE: this module extracted from the JPLV Vision Package, whose primary sources and documentation can be found on the JPLV web-site: http://helios/~vision/jplv/index.shtml

Algorithm Summary

Purpose of algorithm:

To provide a 3D range image (or a depth map) of a scene captured through a pair of stereo images acquired from cameras that have been a priori calibrated

Inputs:

  1. Two images (left and right)
  2. Two camera models (left and right)
  3. Tuning parameters to include: correlation window sizes, sub-sampling level (pyramid level), max disparity and noise filtering parameters

Outputs:

  1. Depth image (each pixel measures corresponding depth)
  2. Range image (each pixel measuring 3D (x,y,z) location of the point relative to a world frame)

Assumptions:

  1. Camera models for each camera obtained through an a priori calibration procedure. Camera model include both intrinsic and extrinisic parameters. The intrinsic parameters are a systematic description of the internal geometry of each camera as it relates to image formation. The extrinsic parameters represent the precise placement and orientation of the camera with respect to some fixed 3D coordinate system.

Computational Requirements:

  1. On a P4 3.4 GHZ 1MB cache processor, generating a range image for a 512x384 color stereo image pair requires 250 ms.
  2. For proper operation, the stereo calibration error should not exceed 1/3 pixel RMS

Figure 1: JPL Stereo vision pipeline

Algorithm Description

The stereo vision aglorithm uses the camera models to generate a 3D point for every pixel in the 2D image. The 3D point can be mathematically associated with a 2D image coordinates with a ray in space containing the points which project to it. The JPL stereo vision software supports the Yakimovsky-Cunningham linear camera model, CAHV, and its extensions, CAHVOR and CAHVORE. CAHV is functionally equivalent to any perspective projection model. CAHVOR includes nonlinear distortions, modeled as polynomial distortion of 3D points symmetric about an axis nearly coincident with the optical axis of the camera. CAHVORE adds an additional modification for use with fisheye lenses to admit a variable nodal point or center of projection. Given a stereo pair, the camera models of the two cameras provide precise information on their relative geometry.

(include picture to illustrate differences in camera models)

Implementation Details

The JPL stereo vision implementation matches points between left and right images and computes the disparity between each corresponding pixel. Prior to generating a disparity image or a range image, the JPL stereo vision requires the calibration of each camera using a calibration target with a fixed and known pattern. There are two procedures for calibration: one that uses a fixed corner cube with three plates mutual perpendicular, and another that uses a single lightweight plate and a total station. In the latter case, the target plate is moved around in front of the cameras and target location relative to a fixed frame is captured using the total station.

The stereo algorithm has the following steps after the calibration files have been produced: (Figure 2)

  • Align Cameras - the two non-linear camera models (CAHVOR or CAHVORE) are converted to linear (CAHV) models without changing the camera baseline (see Figure 1). These models will be used to rectify images.
  • Rectify Images - using the aligned camera models generate rectified images where the rows of one image correspond to the rows of the second image. This reduces the stereo matching problem from a 2D to a 1D search problem
  • Bandpass Filter - use the Laplacian of the Gaussian ideally, but in practice, use the Difference of Gaussian (DoG) to filter out the DC effect and the high frequency noise components of the image signal retaining the stable portion of the signal.
  • Stereo match - compute the sub-pixel disparity between corresponding pixels from the left and right images. The algorithm is implemented such that for each integer disparity (up to the max disparity), a score is computed for the entire image. To obtain sub-pixel disparities the results of this operation are interpolated using parabolic fits. The matching operation uses a window averaging scheme for each pixel with the sum of absolute differences to as a dissimilarity computational measure.(see Figure 2)
  • Verify match - use a left to right correspondence and verify that the right to left correspondence has a close value, otherwise, report no depth information for that pixel.
  • Eliminate discontinuities - a.k.a blob filtering, remove dephts that present strong discontinuities from their neigbhoring pixels.

Figure 2: Example of images processed using JPL Stereo vision pipeline

Figure 3: Stereo correlation

Figure 4: Sliding sum optimization

The stereo vision algorithm uses a number of optimization techniques to improve the overall processing speed

  • Sliding Sums - the algorithm uses the sliding sum optimization that computes pixel intensity averages over a window. Computing such average for the next pixel only requires the adding the next column and the subtracting the previous column (see Figure 4). This optimization is used in many parts of the algorithm
  • Combined operations - depending on the requested subsampling of the original image (pyramid level), the algorithm improves efficiency by combining operations such as smoothing and decimation into a single step or combining Difference of Gaussian (DoG) and decimation into a single step. Such combined operations also take advantage of the sliding sum optimization

Download/Run

To check out and build this algorithms:

  • Set up your environment
    yam checkout -d <sandbox> jpl_vision
    cd <sandbox>
    make all
  • To run the stand-alone command-line stereo application against test data, type:
    $ ./run jplv-stereo
  • To run the stand-alone command-line stereo application against other data, type:
    $ ./run jplv-stereo
  • To build your own applications against the JPLV library, inspect the sample code in stereo_example.c

Known Bugs/Issues

  • None.

Bug Reporting

Please return all feedback and bug reports to: jplv-users@helios.jpl.nasa.gov.

Related Links

New Technology Report (NTR) or Patent Numbers

  • NTR 18593, 21093, 40813

Change Log

  • [Sep 19 2007]: initial version