Realtime stereo and motion analysis on passive video images using an efficient image-to-image comparison algorithm requiring minimal buffering

• US 7,194,126 B2
• Filed: 09/19/2003
• Issued: 03/20/2007
• Est. Priority Date: 06/28/1996
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: SRI International, Inc.
• Inventors: Konolige, Kurt
• Primary Examiner(s): Bali, Vikkram
• Application Number:
  US10/665,881
• Publication Number:
  US 20050100207A1
• Time in Patent Office: 1,278 Days
• Field of Search: 382/154, 348 42- 43, 348/47, 348 49- 50, 345418-419
• US Class Current: 382/154
• CPC Class Codes: G06T 2207/10012 Stereo images
• CPC Class Codes: G06T 2207/10021 Stereoscopic video; Stereoscopic image sequence
• CPC Class Codes: G06T 7/20 Analysis of motion motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51
• CPC Class Codes: G06T 7/579 from motion
• CPC Class Codes: G06T 7/593 from stereo images
• CPC Class Codes: H04N 13/10 Processing, recording or transmission of stereoscopic or multi-view image signals
• CPC Class Codes: H04N 13/189 Recording image signals; Reproducing recorded image signals
• CPC Class Codes: H04N 13/194 Transmission of image signals
• CPC Class Codes: H04N 13/221 using the relative movement between cameras and objects
• 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 13/296 Synchronisation thereof; Control thereof
• CPC Class Codes: H04N 13/30 Image reproducers optical systems for producing stereoscopic or other three-dimensional effects G02B30/00
• CPC Class Codes: H04N 2013/0081 Depth or disparity estimation from stereoscopic image signals
• CPC Class Codes: H04N 2013/0085 Motion estimation from stereoscopic image signals

Abstract

A compact, inexpensive, real-time device for computing dense stereo range and motion field images, which are fundamental measurements supporting a wide range of computer vision systems that interact with the real world, where objects move through three-dimensional space includes a novel algorithm for image-to-image comparison that requires less storage and fewer operations than other algorithms. A combination of standard, low-cost and low-power components are programmed to perform algorithm and performs realtime stereo and motion analysis on passive video images, including image capture, digitization, stereo and/or motion processing, and transmission of results.

Claims

1. An apparatus for performing area correlation on a first feature image and a second feature image, each feature image including a plurality of lines, the apparatus comprising:

one or more buffers capable of storing at least part of each feature image;

a window summation buffer; and

a processor capable of;

obtaining a line from each feature image;

computing a correlation of the two lines at a plurality of disparities;

storing the results of the correlation in the window summation buffer;

using the information stored in the window summation buffer to compute a new line in a disparity image; and

obtaining successive lines of each of said feature images and updating said window summation buffer.

2. The apparatus of claim 1, wherein the processor is further capable of computing two minimum values from the information stored in the window summation buffer to perform a left/right consistency check.

3. The apparatus of claim 1, wherein the processor is further capable of computing fractional pixel disparities.

4. The apparatus of claim 1, wherein the processor is further capable of computing a confidence value.

5. An apparatus as recited in claim 1, wherein said processor is further capable of rectification and feature extraction, and wherein said rectification and feature extraction proceed in parallel with said correlation.

6. An apparatus as recited in claim 1, wherein said window summation buffer has size N×

(D+1), where D is the number of different disparities that are checked for each pixel in said feature images, where for each disparity 0<

=d<

D there is a line of size N in said window summation buffer, where each value in said line is the correlation of said window centered on a corresponding pixel in said first feature image to said window centered on a corresponding pixel offset by the disparity d in said second feature image.

7. An apparatus for performing area correlation on a first and a second feature images using a first and a second correlation windows of size X pixels by Y lines, where Y is less than 10% of the total number of lines in either feature image, and X is less than 10% of the total number of pixels in a line of either feature image, the apparatus comprising:

a first buffer capable of storing more than Y but less than 3Y lines of the first feature image;

a second buffer capable of storing more than Y but less than 3Y lines of the second feature image;

a window summation buffer; and

a processor capable of;

correlating, at a plurality of disparities, corresponding lines in the first and the second correlation windows;

storing the results of the correlation in the window summation buffer;

using the information stored in the window summation buffer to compute a new line in a disparity image; and

obtaining successive lines of each of said feature images and updating said window summation buffer.

8. The apparatus of claim 7, wherein the processor is further capable of computing two minimum values from the information stored in the window summation buffer to perform a left/right consistency check.

9. The apparatus of claim 7, wherein the processor is further capable of computing fractional pixel disparities.

10. The apparatus of claim 7, wherein the processor is further capable of computing a confidence value.

11. A method for performing area correlation on a first feature image and a second feature image using a window summation buffer to cache partial results, each feature image including a plurality of lines, the method comprising the steps of:

obtaining a line from each feature image;

computing a correlation of the two lines at a plurality of disparities;

storing the results of the computing in the window summation buffer;

using the information stored in the window summation buffer to compute a new line in a disparity image; and

obtaining successive lines of each of said feature images and updating said window summation buffer.

12. The method of claim 11, further comprising the step of computing two minimum values from the information stored in the window summation buffer to perform a left/right consistency check.

13. The method of claim 11, further comprising the step of computing fractional pixel disparities.

14. The method of claim 11, further comprising the step of computing a confidence value.

15. A method for performing area correlation on a first and a second feature images using a first and a second correlation windows of size X pixels by Y lines, where Y is less than 10% of the total number of lines in a feature image, and X is less than 10% of the total number of pixels in a line of a feature image, the method comprising the steps of:

storing more than Y but less than 3Y consecutive lines of the first feature image in a first buffer;

storing more than Y but less than 3Y consecutive lines of the second feature image in a second buffer;

correlating, at a plurality of disparities, corresponding lines in the first and the second correlation windows;

storing the results of the correlating in a window summation buffer;

using the information stored in the window summation buffer to compute a new line in a disparity image; and

obtaining successive lines of each of said feature images and updating said window summation buffer.

16. The method of claim 15 further comprising the step of computing two minimum values from the information stored in the window summation buffer to perform a left/right consistency check.

17. The method of claim 15, further comprising the step of computing fractional pixel disparities.

18. The method of claim 15, further comprising the step of computing a confidence value.

19. A computer readable medium encoded with a computer program for performing area correlation on a first feature image and a second feature image using a window summation buffer to cache partial results, each feature image including a plurality of lines, the computer program comprising for:

obtaining a line from each feature image;

computing a correlation of the two lines at a plurality of disparities;

storing the results of the computing in the window summation buffer;

using the information stored in the window summation buffer to compute a new line in a disparity image; and

obtaining successive lines of each of said feature images and updating said window summation buffer.