Stereo matching method and disparity measuring method

• US 5,719,954 A
• Filed: 06/02/1995
• Issued: 02/17/1998
• Est. Priority Date: 06/07/1994
• Status: Expired due to Fees

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Onda, Katsumasa
• Primary Examiner(s): Johns, Andrew
• Assistant Examiner(s): Davis, Monica S.
• Application Number:
  US08/460,712
• Time in Patent Office: 991 Days
• Field of Search: 382/154, 382/190, 382/199, 382/201, 382/291, 356/376, 356/2
• US Class Current: 382/154
• CPC Class Codes: G06T 2207/10012 Stereo images
• CPC Class Codes: G06T 7/593 from stereo images
• CPC Class Codes: G06V 10/10 Image acquisition document image scanning and transmission H04N1/00; control of digital cameras H04N23/60
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: G06V 2201/12 Acquisition of 3D measurements of objects
• CPC Class Codes: H04N 2013/0081 Depth or disparity estimation from stereoscopic image signals
• CPC Class Codes: H04N 2013/0092 Image segmentation from stereoscopic image signals
• CPC Class Codes: H04N 2013/0096 Synchronisation or controlling aspects

Abstract

A method for measuring stereo image disparity between right and left stereo images for each of two-dimensional blocks having a rectangular shape. In particular, the method includes the steps of deciding a level of each pixel in the right and left stereo images according to a ternary value, sequentially setting a one-dimensional window having a size of N pixels along a horizontal direction in one of the right and left stereo images by overlapping N/2 pixels, determining the disparity for each one-dimensional window by determining a portion in the other of the right and left stereo images corresponding to each one-dimensional window on the basis of the ternary value obtained through the deciding step to generate a histogram of the disparities, and determining the stereo image disparity for each of the two-dimensional blocks on the basis of the histogram of the disparities.

Claims

1. A method for taking correspondence between right and left stereo images imaged by two imaging devices arranged at a predetermined horizontal distance therebetween, comprising the steps of:

extracting horizontal edges from the right and left stereo images by using differentiation;

deciding a level of each pixel of the extracted horizontal edges into a ternary value by using a first threshold value and a second threshold value; and

determining a position in one of the right and left stereo images corresponding to that in the other of the right and left stereo images on the basis of the ternary values obtained through said deciding step,

wherein said determining step includes setting a one-dimensional window having a size of N pixels along a horizontal direction in one of the right and left stereo images.

2. The method according to claim 1, further comprising the step of:

reducing noise components of the right and left stereo images by using a low-pass filter before said extracting step.

4. The method according to claim 1, wherein said determining step includes the step of:

searching, in the other of the right and left stereo images, an area having a pattern of N ternary values which is analogous to that of said one-dimensional window.

5. The method according to claim 2, wherein said determining step includes the step of:

searching, in the other of the right and left stereo images, an area having a pattern of N ternary values which is analogous to that of said one-dimensional window.

7. The method according to claim 4, wherein said determining step includes the step of:

evaluating a degree of coincidence of said pattern of N ternary values between the right and left stereo images by using a coincidence evaluation factor E=Np+Nz+Nm for each one-dimensional window, where Np is a number of pixels each having a level not less than the first threshold value in both the right and left stereo images. Nz is a number of pixels each having a level less than the first threshold value and not less than the second threshold value in both the right and left stereo images, and Nm is a number of pixels each having a level less than the second threshold value in both the right and left stereo images.

8. The method according to claim 5, wherein said determining step includes the step of:

evaluating a degree of coincidence of said pattern of N ternary values between the right and left stereo images by using a coincidence evaluation factor E=Np+Nz+Nm for each one-dimensional window, where Np is a number of pixels each having a level not less than the first threshold value in both the right and left stereo images. Nz is a number of pixels each having a level less than the first threshold value and not less than the second threshold value in both the right and left stereo images, and Nm is a number of pixels each having a level less than the second threshold value in both the right and left stereo images.

10. The method according to claim 7, wherein said evaluating step includes the step of:

determining that the coincidence of said pattern of N ternary values between the right and left stereo images is valid when Np+Nm is not less than a predetermined number.

11. The method according to claim 8, wherein said evaluating step includes the step of:

determining that the coincidence of said pattern of N ternary values between the right and left stereo images is valid when Np+Nm is not less than a predetermined number.

13. The method according to claim 1, wherein said determining step includes the steps of:

searching, in the other of the right and left stereo images, an area of the highest degree of coincidence with a pattern of N ternary values in said one-dimensional window and an area having the next highest degree of coincidence with the pattern of N ternary values in said one-dimensional window;

designating disparity in the area having the highest degree of coincidence as the first candidate disparity and disparity in the area having the next highest degree of coincidence as the second candidate disparity; and

determining disparity of the right and left stereo images by using said first candidate disparity and said second candidate disparity.

14. The method according to claim 2, wherein said determining step includes the steps of:

setting a one-dimensional window having a size of N pixels along a horizontal direction in one of the right and left stereo images;

searching, in the other of the right and left stereo images, an area of the highest degree of coincidence with a pattern of N ternary values in said one-dimensional window and an area having the next highest degree of coincidence with the pattern of N ternary values in said one-dimensional window;

designating disparity in the area having the highest degree of coincidence as the first candidate disparity and disparity in the area having the next highest degree of coincidence as the second candidate disparity; and

determining disparity of the right and left stereo images by using said first candidate disparity and said second candidate disparity.

16. The method according to claim 4, wherein:

said setting step includes the step of sequentially setting the one-dimensional window having a size of N pixels by overlapping N/2 pixels while scanning the whole screen on scanning lines; and

said determining step includes the step of determining a position in one of the right and left stereo images corresponding to that in the other of the right and left stereo images for each one-dimensional window thus set.

17. The method according to claim 4, wherein:

said setting step includes the step of sequentially setting the one-dimensional window having a size of N pixels by overlapping N/2 pixels while scanning a whole screen on one of odd-numbered scanning lines and even-numbered scanning lines; and

said determining step includes the step of determining a position in one of the right and left stereo images corresponding to that in the other of the right and left stereo images for each one-dimensional window thus set.

3. A method for taking correspondence between right and left stereo images imaged by two imaging devices arranged at a predetermined horizontal distance therebetween, comprising the steps of:

reducing out-of-band frequency components of the right and left stereo images by using a band-pass filter to extract horizontal edges having in-band frequency components from the right and left stereo images;

deciding a level of each pixel of the extracted horizontal edges into a ternary value by using a first threshold value and a second threshold value; and

determining a position in one of the right and left stereo images corresponding to that in the other of the right and left stereo images on the basis of the ternary values obtained through said deciding step,

wherein said determining step includes setting a one-dimensional window having a size of N pixels along a horizontal direction in one of the right and left stereo images.

6. The method according to claim 3, Wherein said determining step includes the step of:

searching, in the other of the right and left stereo images, an area having a pattern of N ternary values which is analogous to that of said one-dimensional window.

9. The method according to claim 6, wherein said determining step includes the step of:

evaluating a degree of coincidence of said pattern of N ternary values between the right and left stereo images by using a coincidence evaluation factor E=Np+Nz+Nm for each one-dimensional window where Np is a number of pixels each having a level not less than the first threshold value in both the right and left stereo images. Nz is a number of pixels each having a level less than the first threshold value and riot less than the second threshold value in both the right and left stereo images, and Nm is a number of pixels each having a level less than the second threshold value in both the right and left stereo images.

12. The method according to claim 9, wherein said evaluating step includes the step of:

determining that the coincidence of said pattern of N ternary values between the right and left stereo images is valid when Np+Nm is not less than a predetermined number.

15. The method according to claim 3, wherein said determining step includes the steps of:

searching, in the other of the right and left stereo images, an area of the highest degree of coincidence with a pattern of N ternary values in said one-dimensional window and an area having the next highest degree of coincidence with the pattern of N ternary values in said one-dimensional window;

designating disparity in the area having the highest degree of coincidence as the first candidate disparity and disparity in the area having the next highest degree of coincidence as the second candidate disparity; and

determining disparity of the right and left stereo images by using said first candidate disparity and said second candidate disparity.

18. A method of measuring the stereo image disparity between right and left stereo images, said method comprising the steps of:

deciding a level of each pixel in the right and left stereo images into a ternary value;

dividing a whole screen of one of the right and left stereo images into two-dimensional blocks each having a size of N×

M pixels;

sequentially setting a one-dimensional window having a size of N pixels along a horizontal direction in one of the right and left stereo images;

searching in the other of the right and left stereo images an area having the highest degree of coincidence with a pattern of N ternary values in said one-dimensional window and an area having the next highest degree of coincidence with the pattern of N ternary values in said one-dimensional window;

designating disparity in an area having the highest degree of coincidence as the first candidate disparity and disparity in an area having the next highest degree of coincidence as the second candidate disparity in each one-dimensional window;

generating a histogram of disparities by using at least one of said first candidate disparity and said second candidate disparity; and

determining disparity at a peak of the histogram of the disparities as the stereo image disparity for each of said two-dimensional blocks.

19. The method according to claim 18 further comprising the step of:

evaluating a degree of coincidence of said pattern of N ternary values between right and left stereo images by using a coincidence evaluation factor E=Np+Nz+Nm for each one-dimensional window, where Np is a number of pixels each having a level not less than the first threshold value in both the right and left stereo images, Nz is a number of pixels each having a level less than the first threshold value and not less than the second threshold value in both the right and left stereo images, and Nm is a number of pixels each having a level less than the second threshold value in both the right and left stereo images.

wherein said generating step includes the step of generating a histogram of the disparities by using Np+Nm in N/2 pixels of an area where the degree of coincidence is evaluated as maximum in the other of the right and left stereo images and Np+Nm in N/2 pixels of a right-half of said area.

20. The method according to claim 18 further comprising:

evaluating a degree of coincidence of said pattern of N ternary values between right and left stereo images by using a coincidence evaluation factor E=Np+Nz+Nm for each one-dimensional window, where Np is a number of pixels each having a level not less than the first threshold value in both the right and left;

stereo images. Nz is a number of pixels each having a level less than the first threshold value and not less than the second threshold value in both the right and left stereo images, and Nm is a number of pixels each having a level less than the second threshold value in both the right and left stereo images.

wherein said generating step includes the step of generating a histogram by using Np+Nm in N/2 pixels of a left half of the one-dimensional window and Np+Nm in N/2 pixels of a right-half of the one-dimensional window.

21. A method for measuring stereo image disparity between right and left stereo images for each of a plurality of two-dimensional blocks having a rectangular shape, said method comprising the steps of:

deciding a level of each pixel in the right and left stereo images into a ternary value;

sequentially setting a one-dimensional window having a size of N pixels along a horizontal direction in one of the right and left stereo images by overlapping N/2 pixels;

determining disparity for each one-dimensional window by determining a portion in the other of the right and left stereo images corresponding to each one-dimensional window on the basis of the ternary value obtained through said deciding step, thereby generating a histogram of the disparities; and

determining the stereo image disparity for each of said two-dimensional blocks on the basis of the histogram of the disparities.