Near real-time stereo vision system

• US 5,179,441 A
• Filed: 12/18/1991
• Issued: 01/12/1993
• Est. Priority Date: 12/18/1991
• Status: Expired due to Term

• Current Assignee: The Government of The US As Represented By The Secretary of The Navy
• Original Assignee: United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration
• Inventors: Matthies, Larry H., Anderson, Charles H.
• Primary Examiner(s): Britton, Howard W.
• Application Number:
  US07/812,901
• Time in Patent Office: 391 Days
• Field of Search: 358/88, 358/133
• US Class Current: 348/43
• CPC Class Codes: G06T 2207/10012 Stereo images
• CPC Class Codes: G06T 2207/20016 Hierarchical, coarse-to-fine, multiscale or multiresolution image processing; Pyramid transform
• CPC Class Codes: G06T 2207/20076 Probabilistic image processing
• CPC Class Codes: G06T 2207/30252 Vehicle exterior; Vicinity of vehicle
• CPC Class Codes: G06T 7/593 from stereo images
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: H04N 13/239 using two 2D image sensors having a relative position equal to or related to the interocular distance H04N13/243 takes precedence
• CPC Class Codes: H04N 19/597 specially adapted for multi-view video sequence encoding
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 2013/0081 Depth or disparity estimation from stereoscopic image signals
• CPC Class Codes: H04N 7/0806 the signals being two or more video signals H04N7/0803, H04N7/081 take precedence

Abstract

Apparatus and methods for near real-time stereo vision system for use with a robotic vehicle comprises two cameras mounted on three-axis rotation platforms, image-processing boards, a CPU, and specialized stereo vision algorithms. Bandpass-filtered image pyramids are computed, stereo matching is performed by least-squares correlation, and confidence ranges are estimated by means of Bayes'"'"' theorem. In particular, Laplacian image pyramids are built and disparity maps are produced from the 60×64 level of the pyramids at rates of up to 2 seconds per image pair. The first autonomous cross-country robotic traverses (of up to 100 meters) have been achieved using the stereo vision system of the present invention with all computing due aboard the vehicle. The overall approach disclosed herein provides a unifying paradigm for practical domain-independent stereo ranging.

Claims

1. A near real-time stereo vision apparatus comprising:

first videocamera means for producing a first video output image responsive to light from an object scene;

second videocamera means for producing a second video output image responsive to light from said object scene;

first digitizing means for digitizing said first video image, having an input connected to an output of said first videocamera means, and having an output at which digital representations of said first video image appear;

second digitizing means for digitizing said second video image, having an input connected to an output of said second videocamera means, and having an output at which digital representations of said second video image appear;

videoprocessing means for successively producing sequential left and right stereo Laplacian pyramid images from said digital representations of said first and second video signals, having first and second inputs connected to said outputs of said first and second digitizing means; and

disparity map calculating means for calculating a disparity map of said object scene, operatively connected to said videoprocessing means and having storage means for storing an array of numerical values corresponding to the disparity at each pixel of a digital representation of said object scene;

wherein said disparity map can be used to generate control signals for semi-autonomous operation of a robotic vehicle or the like.

2. The near real-time stereo vision apparatus of claim 1 wherein said disparity map calculating means includes stereo correlation means for correlating said left and right stereo Laplacian pyramid images.

3. The near real-time stereo vision apparatus of claim 2 additionally comprising an output confidence image means for calculating an output confidence image of said object scene, operatively connected to said stereo correlation means and having storage means for storing an array of numerical values corresponding to said output confidence image.

4. The near real-time stereo vision apparatus of claim 3 wherein said stereo correlation means comprises:

shifting means for shifting said left Laplacian pyramid image over a selected range of disparity values from d_min to d_max to produce a series of shifted Laplacian pyramid images;

subtracting means for subtracting said shifted Laplacian pyramid images from said right Laplacian pyramid image to give a difference image consisting of a plurality of difference values;

sum-of-squared-differences (SSD) means for calculating a sum-of-squared-differences (SSD) image for each value of shift d from d_min to d_max to produce a plurality of such SSD images, including squaring means for squaring said difference values of a particular difference image to produce a plurality of squared difference values, and summing means for summing, over a local window of predetermined width, said plurality of squared difference values;

minimum finding means for finding the minimum over d for said SSD; and

disparity image output means for using said minimum over d for said SSD to output a disparity image consisting of a plurality of individual disparity values.

5. The near real-time stereo vision apparatus of claim 4 wherein said output confidence image means comprises:

posterior probability calculation means for carrying out a posterior probability calculation, operatively connected to said sum-of-squared-differences (SSD) means;

selection means for using said minimum over d for said SSD and said posterior probability calculation to select the probability of the best d, operatively connected to said posterior probability calculation means and to said minimum finding means; and

confidence image output means for using said best d to output a confidence image.

6. The near real-time stereo vision apparatus of claim 5 wherein said minimum finding means is replaced with dynamic programming optimization means for estimating disparity jointly over a row of pixels in a scanline, operatively connected to said sum-of-squared-differences (SSD) means.

7. The near real-time stereo vision apparatus of claim 6 wherein said first and second digitizing means and said videoprocessing means include image processing VME boards comprising:

first and second A/D digitizer boards;

a frame store board for storing three video frames, operatively connected to said first and second A/D digitizer boards;

first and second region-of-interest (ROI) eight-frame store boards for doing subsampling, operatively connected to said first and second A/D digitizer boards and to said frame store board;

a video finite impulse response (VFIR) board capable of lowpass filtering at video rates, operatively connected to said first and second region-of-interest (ROI) eight-frame store boards; and

a general purpose arithmetic and logic (ALU) board for doing subtractions, operatively connected to said first and second region-of-interest (ROI) eight-frame store boards and to said video finite impulse response (VFIR) board.

8. The near real-time stereo vision apparatus of claim 7 additionally comprising mounting means including two three-axis rotation platforms, for mounting said first and second videocameras so that said cameras can be adjustably mounted on a robotic vehicle or the like with parallel optical axes and appropriate roll about the optical axis.

9. A method of near real-time stereo vision comprising:

producing a first video output signal responsive to light from an object scene;

producing a second video output image responsive to light from said object scene;

digitizing said first video image to produce digital representations of said first video image;

digitizing said second video image to produce digital representations of said second video image;

videoprocessing said digital representations by successively producing sequential Laplacian stereo image pyramid pairs from said digital representations of said first and second video images; and

calculating a disparity map of said object scene and storing an array of numerical values corresponding to the disparity at each pixel of a digital representation of said object scene.

10. The method of claim 9 wherein said calculating of said disparity map includes the stereo correlation of said left and right stereo Laplacian pyramid images from said digital representations of said first and second video images, comprising:

shifting said left Laplacian pyramid image over a selected range of disparity values from d_min to d_max to produce a series of shifted Laplacian pyramid images;

subtracting said shifted Laplacian pyramid images from said right Laplacian pyramid image to give a difference image consisting of a plurality of difference values corresponding to individual pixel values;

squaring said difference values of a particular difference image to produce a plurality of squared difference values;

summing, over a local window of predetermined width, said plurality of squared difference values;

calculating a sum-of-squared-differences (SSD) image for each value of shift d from d_min to d_max to produce a plurality of such SSD images;

finding the minimum over d for said SSD and carrying out a posterior probability calculation;

using said minimum over d for said SSD and said posterior probability calculation to select the probability of the best d; and

using said minimum over d for said SSD to output a disparity image, consisting of a plurality of individual disparity values.

11. The method of claim 10 wherein said finding said minimum is replaced by dynamic programming optimizing, and wherein said calculating of said disparity map includes estimating disparity jointly over a row of pixels in a scanline.

12. The method of claim 9 additionally comprising:

calculating an output confidence image of said object scene, and

storing an array of numerical values corresponding to said output confidence image of said object scene, and

storing an array of numerical values corresponding to said output confidence image.

13. The method of claim 12 wherein said calculating an output confidence image of said object scene comprises:

using said minimum over d for said SSD and said posterior probability calculation to select the probability of the best d.

14. The method of claim 9 wherein said videoprocessing operates on said digital representations of said first and second video images in the form of digitized image arrays (G₀)_left and (G₀)_right, comprising:

(a) low-pass filtering said (G₀)_left to produce an image (G₁)_left ;

(b) subtracting said (G₁)_left from (G₀)_left to produce an image (L₀)_left which retains high-frequency information of (G₀)_left ;

(c) subsampling said (G₁)_left, by taking every other pixel in every other line to remove the total number of pixels in the image by a factor of four and produce a subsampled (G₁)_left ;

(d) lowpass-filtering said subsampled (G₁)_left to produce a filtered image (G₂)_left ;

(e) subtracting said (G₂)_left from said subsampled (G₁)_left to produce an image (L₁)_left which retains high-frequency information of (G₁)_left ;

(f) subsampling said (G₂)_left, by taking every other pixel in every other line to remove the total number of pixels in the image by a factor of four and produce a subsampled (G₂)_left ;

(g) lowpass-filtering said subsampled (G₂)_left to produce a filtered image (G₃)_left ;

(h) subtracting said (G₃)_left from subsampled (G₂)_left to produce an image (L₂)_left which retains high-frequency information of (G₂)_left ; and

(i) performing steps (a) through (h) as described above starting with (G₀)_right.

15. The method of claim 14 wherein in terms of an inverse frame rate of said videocameras, the following sequence of events occurs;

during a first frametime said stereo pair (G₀)_left and (G₀)_right are acquired, during a second frametime said (L₀)_left and (G₁)_left are calculated, during a third frametime said (L₀)_right and (G₁)_right are calculated, and during a fourth frametime and subsequently the remaining Laplacian pyramid images are calculated.

16. The method of claim 14, additionally comprising further recursion of steps (a) through (i) to give left and right Laplacian pyramid imaged L₃, L₄, and so forth ad libitum.