Detection and removal of image occlusion errors

• US 6,865,289 B1
• Filed: 02/07/2000
• Issued: 03/08/2005
• Est. Priority Date: 02/07/2000
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Berestov, Alexander
• Primary Examiner(s): Miriam, Daniel
• Assistant Examiner(s): GORADIA, SHEFALI DINESH
• Application Number:
  US09/500,181
• Time in Patent Office: 1,856 Days
• Field of Search: 382/154, 382/294, 382/209, 356 12- 14, 356/611, 356/623, 356/631, 250/559.23, 250/559.31, 348/47, 600/116
• US Class Current: 382/154
• CPC Class Codes: G01C 11/06 by comparison of two or more pictures of the same area
• CPC Class Codes: G06T 7/593 from stereo images

Abstract

A system, method, and computer-readable medium for detecting and eliminating correspondence errors associated with image occlusions. In a first embodiment of the invention, the method applies traditional correspondence methods for matching points in two images, a left image (FIG. 1A) and a right image (FIG. 1B), taken of the same scene. The method applies the correspondence method to locate a matching a point (310) in the right image (FIG. 1B) with a “best match” point (320) in the left image (FIG. 1A). A set of matching points (310, 320) is generated. A second search is then performed by using the best match point (320) in the right image (FIG. 1B) as the basis for an additional correspondence search in the left image (FIG. 1A). The range of match candidates in the second search is such that points to the left of the starting point (310) are not tested as match candidates. The point (330) generated in the second search may be the same point (310) that was used in the first search or may be a different point altogether. The results of the second search are selected as the match candidates.

Claims

1. A method for locating matching points in two original images of a scene, a left image and a right image, such that the images have at least some overlap area, said method comprising:

selecting a first point within the overlap area in the right image;

running a first correspondence search using the first point to find a first matching point in the left image;

running a second correspondence search using the first matching point found by the first correspondence search to find a second matching point in the right image, wherein the second correspondence search is not run on any points to the left of the first point in the right image, and wherein a range of the second correspondence search is narrower than a range of the first correspondence search; and

selecting a match point comprising the first matching point and second matching point.

2. The method of claim 1, wherein the step of selecting a match point comprises selecting only those match points in which the second matching point is the same as the first matching point.

3. The method of claim 1, wherein the step of running a first correspondence search comprises running a classic stereo correspondence search.

4. The method of claim 3, wherein the second correspondence search uses a different matching algorithm than the algorithm used in the first correspondence search.

5. The method of claim 1, wherein the step of running a first correspondence search comprises running a correlation-based matching algorithm.

6. The method of claim 1, wherein the step of running a first correspondence search comprises running a feature-based matching algorithm.

7. The method of claim 1, wherein the step of running a first correspondence search comprises running a phase-based matching algorithm.

8. The method of claim 1, wherein the step of running the first correspondence search comprises running the search in a first direction, and the step of running the second correspondence search comprises running the search in a second direction opposite the first direction.

9. A method for locating matching points in two original images of a scene, a left image and a right image, such that the images have at least some overlap area, said method comprising:

splitting the left image and the right image into left subimages and right subimages, respectively, wherein each subimage comprises the values of only one of the color coordinates used to define the image with which it is associated;

pairing each left subimage with the right subimage which uses the same color coordinate values;

running a first correspondence search using a first point in the right subimage to find a first matching point in the left subimage;

running a second correspondence search on the first matching point found by the first correspondence search to find a second matching point in the right subimage, wherein the second correspondence search is not run on any points to the left of the first point in the right subimage and wherein a range of the second correspondence search is narrower than a range of the first correspondence search;

selecting match points using the first matching point and the second matching point; and

storing each selected match point in a list of match points.

10. The method of claim 9, further comprising, for each given point in the right subimage used in the correspondence search:

comparing the matching points stored in the list of match points that correspond to the given point across each subimage pair; and

responsive to the matching points in the list of matching points being different for each subimage pair, removing the matching point from the list of match points.

11. The method of claim 10 further comprising the steps of:

retrieving a distance value which represents the distance between the camera location used to capture the right image and the camera location used to capture the left image; and

creating a disparity map of the scene captured by the images by determining a disparity value for each point in the image, wherein values in the disparity map are calculated by using the distance between the match points that correspond to the point in the disparity distance map in the list of match points in conjunction with the retrieved value.

12. The method of claim 11, wherein the step of creating a disparity map further comprises the substep of, responsive to a given disparity map point not having any corresponding match points in the list of match points, using the first calculated disparity value to the right of the disparity map point as the disparity value.

13. The method of claim 12, wherein the substep of using the first calculated disparity value comprises the substep of, responsive to the images being stored in a color coordinate system that includes a brightness value, reducing the brightness value of the given disparity map point.

14. The method of claim 9, wherein the step of running a first correspondence search comprises running a classic stereo correspondence search.

15. The method of claim 14, wherein the second correspondence search uses a different matching algorithm than the algorithm used in the first correspondence search.

16. The method of claim 9, wherein the step of running a first correspondence search comprises running a correlation-based matching algorithm.

17. The method of claim 9, wherein the step of running a first correspondence search comprises running a feature-based matching algorithm.

18. The method of claim 9, wherein the step of running a first correspondence search comprises running a phase-based matching algorithm.

19. The method of claim 9, wherein the step of running the first correspondence search comprises running the search in a first direction, and the step of running the second correspondence search comprises running the search in a second direction opposite the first direction.

20. A system for locating matching points in two original images of a scene, a left image and a right image, such that the images have at least some overlap area, the system comprising:

a storage device for storing the images and executable code;

coupled to the storage device, means for selecting a first point within the overlap area in the right image;

coupled to the storage device, means for running a first correspondence search using the first point to find a first matching point in the left image;

coupled to the storage device, means for running a second correspondence search using the first matching point found by the first correspondence search to find a second matching point in the right image wherein the second correspondence search is not run on any points to the left of the first point in the right image and wherein a range of the second correspondence search is narrower than a range of the first correspondence search; and

means for selecting match points using the first matching point and the second matching point.

21. The system of claim 20, wherein the means for running the first correspondence search comprises running the search in a first direction, and the means for running the second correspondence search comprises running the search in a second direction opposite the first direction.

22. A computer-readable medium containing a computer program for creating a list of match points in two images, said program containing instructions for directing the computer to execute the steps of:

splitting the left image and the right image into left subimages and right subimages, respectively, wherein each subimage comprises the values of only one of the color coordinates used to define the corresponding image;

pairing each left subimage with the right subimage which uses the same color coordinate values;

running a first correspondence search using a first point in the right subimage to find a first matching point in the left subimage;

running a second correspondence search on the first matching point found by the first correspondence search to find a second matching point in the right subimage, wherein the second correspondence search is not run on any points to the left of the first point in the right subimage and wherein a range of the second correspondence search is narrower than a range of the first correspondence search;

selecting match points using the first matching point and second matching point; and

storing each selected match point in a list of match points.

23. The computer-readable medium of claim 22, wherein the step of running the first correspondence search comprises running the search in a first direction, and the step of running the second correspondence search comprises running the search in a second direction opposite the first direction.