Correcting an epipolar axis for skew and offset

• US 6,674,892 B1
• Filed: 11/01/1999
• Issued: 01/06/2004
• Est. Priority Date: 11/01/1999
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Melen, Roger D.
• Primary Examiner(s): Couso, Yon J.
• Assistant Examiner(s): CARTER, AARON W
• Application Number:
  US09/431,418
• Time in Patent Office: 1,527 Days
• Field of Search: 382/154, 382/284, 382/285, 382/289, 345/419, 345/420, 348/43, 348/46, 348/42, 356/12
• US Class Current: 382/154
• CPC Class Codes: G06T 7/593 from stereo images
• CPC Class Codes: G06T 7/97 Determining parameters from multiple pictures depth or shape recovery from multiple images G06T7/55; stereo camera calibration G06T7/85
• CPC Class Codes: G06V 10/147 Details of sensors, e.g. sensor lenses fingerprint or palmprint sensors G06V40/13; vascular sensors G06V40/145; eye sensors G06V40/19
• CPC Class Codes: G06V 10/98 Detection or correction of errors, e.g. by rescanning the pattern or by human intervention; Evaluation of the quality of the acquired patterns
• CPC Class Codes: G06V 2201/12 Acquisition of 3D measurements of objects

Abstract

Cameras (10, 12) produce first and second images (14, 16) of an object (18) from different viewpoints. An image partitioning module (54) partitions the images (14, 16) into a plurality of vertically striped regions (70), such that each region (70) of the first image (14) corresponds to a region (70) of the second image (16). A region alignment module (55) vertically shifts a region (70) of the first image (14) in a direction calculated to vertically align a portion (30) of the region (70) with a substantially matching portion (32) of the corresponding region (70). A disparity calculation module (62) calculates at least one disparity value between at least a portion (30) of the vertically shifted region (70) and at least a portion (32) of the corresponding region (70).

Claims

1. A computer-implemented method for correcting an epipolar axis to approximate a horizontal axis, the epipolar axis associated with first and second images of a stereo image pair, where a first region of the first image corresponds to a second region of the second image, the method comprising:

partitioning the first and second images into a plurality of vertically striped regions, each region of the first image corresponding to a region of the second image;

vertically shifting a region of the first image in a direction calculated to vertically align a portion of the region with a substantially matching portion of the corresponding region;

identifying a portion of the second region that substantially matches a portion of the first region;

calculating a vertical offset between the portion of the first region and the substantially matching portion of the second region;

vertically shifting the first region according to the calculated vertical offset to vertically align the substantially matching portions of the first and second regions;

repeating the identifying and calculating steps for at least two portions of the first region in order to calculate at least two vertical offsets; and

determining an average of the at least two vertical offsets.

2. A computer-implemented method for correcting an epipolar axis to approximate a horizontal axis, the epipolar axis associated with first and second images of a stereo image pair, where a first region of the first image corresponds to a second region of the second image, the method comprising:

partitioning the first and second images into a plurality of vertically striped regions, each region of the first image corresponding to a region of the second image;

vertically shifting a region of the first image in a direction calculated to vertically align a portion of the region with a substantially matching portion of the corresponding region;

identifying a portion of the second region that substantially matches a portion of the first region;

calculating a vertical offset between the portion of the first region and the substantially matching portion of the second region; and

vertically shifting the first region according to the calculated vertical offset to vertically align the substantially matching portions of the first and second regions;

wherein each portion comprises a section of a vertically striped region.

3. A computer-implemented method for correcting an epipolar axis to approximate a horizontal axis, the epipolar axis associated with first and second images of a stereo image pair, where a first region of the first image corresponds to a second region of the second image, the method comprising:

partitioning the first and second images into a plurality of vertically striped regions, each region of the first image corresponding to a region of the second image;

vertically shifting a region of the first image in a direction calculated to vertically align a portion of the region with a substantially matching portion of the corresponding region;

identifying a portion of the second region that substantially matches a portion of the first region by calculating a distance between a portion of the first region and at least two different portions of the second region, and identifying from among the at least two different portions the one having the least distance from the portion of the first region;

calculating a vertical offset between the portion of the first region and the substantially matching portion of the second region; and

vertically shifting the first region according to the calculated vertical offset to vertically align the substantially matching portions of the first and second regions.

4. The method of claim 3, wherein the distance comprises a Hamming distance.

5. A computer-implemented method for correcting an epipolar axis to approximate a horizontal axis, the epipolar axis associated with first and second images of a stereo image pair, where a first region of the first image corresponds to a second region of the second image, the method comprising:

partitioning the first and second images into a plurality of vertically striped regions, each region of the first image corresponding to a region of the second image;

vertically shifting a region of the first image in a direction calculated to vertically align a portion of the region with a substantially matching portion of the corresponding region;

identifying a portion of the second region that substantially matches a portion of the first region by calculating a similarity value between a portion of the first region and at least two different portions of the second region, and identifying from among the at least two different portions the one most similar to the portion of the first region;

calculating a vertical offset between the portion of the first region and the substantially matching portion of the second region; and

vertically shifting the first region according to the calculated vertical offset to vertically align the substantially matching portions of the first and second regions.

6. A computer-implemented method for correcting an epipolar axis to approximate a horizontal axis, the epipolar axis associated with first and second images of a stereo image pair, where a first region of the first image corresponds to a second region of the second image, and where the first and second images comprise data arrays including rows and columns of pixels, each row and each column having an associated number, the method comprising:

partitioning the first and second images into a plurality of vertically striped regions, each region of the first image corresponding to a region of the second image;

vertically shifting a region of the first image in a direction calculated to vertically align a portion of the region with a substantially matching portion of the corresponding region;

identifying a portion of the second region that substantially matches a portion of the first region;

calculating a vertical offset between the portion of the first region and the substantially matching portion of the second region by identifying a first row number associated with the portion of the first region, identifying a second row number associated with the portion of the second region, and subtracting the second row number from the first row number; and

vertically shifting the first region according to the calculated vertical offset to vertically align the substantially matching portions of the first and second regions.

7. A computer-implemented method for correcting an epipolar axis to approximate a horizontal axis, the epipolar axis associated with first and second images of a stereo image pair, where a first region of the first image corresponds to a second region of the second image, and where the first and second images comprise data arrays including rows and columns of pixels, the method comprising:

partitioning the first and second images into a plurality of vertically striped regions, each region of the first image corresponding to a region of the second image;

vertically shifting a region of the first image in a direction calculated to vertically align a portion of the region with a substantially matching portion of the corresponding region;

identifying a portion of the second region that substantially matches a portion of the first region;

calculating a vertical offset between the portion of the first region and the substantially matching portion of the second region; and

vertically shifting the first region according to the calculated vertical offset to vertically align the substantially matching portions of the first and second regions by vertically shifting the first region with respect to the second region by an integral number of pixel rows corresponding to the vertical offset.

8. A computer-implemented method for correcting an epipolar axis to approximate a horizontal axis, the epipolar axis associated with first and second images of a stereo image pair, the method comprising:

partitioning the first and second images into a plurality of vertically striped regions, each region of the first image corresponding to a region of the second image; and

vertically shifting a region of the first image in a direction calculated to vertically align a portion of the region with a substantially matching portion of the corresponding region calculating at least one disparity value between at least a portion of the vertically shifted region and at least a portion of the corresponding region; and

calculating at least one disparity value between at least a portion of the vertically shifted region and at least a portion of the corresponding region.

9. A system for correcting an epipolar axis to approximate a horizontal axis, the epipolar axis associated with first and second images of a stereo image pair, where a first region of the first image corresponds to a second region of the second image, the method comprising:

a partitioning module configured to partition the first and second images into a plurality of vertically striped regions, each region of the first image corresponding to a region of the second image;

an alignment module configured to vertically shift a region of the first image in a direction calculated to vertically align a portion of the region with a substantially matching portion of the corresponding region;

a block matching module configured to identify a portion of the second region that substantially matches a portion of the first region;

an offset calculation module configured to calculate a vertical offset between the portion of the first region and the substantially matching portion of the second region, to calculate a second vertical offset between a second pair of substantially matching portions of the first and second regions, and to determine an average of the vertical offsets; and

a region shifting module configured to vertically shift the first region according to the calculated vertical offset to vertically align the substantially matching portions of the first and second regions.

10. A system for correcting an epipolar axis to approximate a horizontal axis, the epipolar axis associated with first and second images of a stereo image pair, where a first region of the first image corresponds to a second region of the second image, the method comprising:

a partitioning module configured to partition the first and second images into a plurality of vertically striped regions, each region of the first image corresponding to a region of the second image;

an alignment module configured to vertically shift a region of the first image in a direction calculated to vertically align a portion of the region with a substantially matching portion of the corresponding region;

a block matching module configured to identify a portion of the second region that substantially matches a portion of the first region;

an offset calculation module configured to calculate a vertical offset between the portion of the first region and the substantially matching portion of the second region; and

a region shifting module configured to vertically shift the first region according to the calculated vertical offset to vertically align the substantially matching portions of the first and second regions,

wherein each portion comprises a section of a vertically striped region.

11. A system for correcting an epipolar axis to approximate a horizontal axis, the epipolar axis associated with first and second images of a stereo image pair, where a first region of the first image corresponds to a second region of the second image, the method comprising:

a partitioning module configured to partition the first and second images into a plurality of vertically striped regions, each region of the first image corresponding to a region of the second image;

an alignment module configured to vertically shift a region of the first image in a direction calculated to vertically align a portion of the region with a substantially matching portion of the corresponding region;

a block matching module configured to identify a portion of the second region that substantially matches a portion of the first region and to calculate a distance between a portion of the first region and at least two different portions of the second region, and identify from among the at least two different portions the one having the least distance from the portion of the first region;

an offset calculation module configured to calculate a vertical offset between the portion of the first region and the substantially matching portion of the second region; and

a region shifting module configured to vertically shift the first region according to the calculated vertical offset to vertically align the substantially matching portions of the first and second regions.

12. The system of claim 11, wherein the distance comprises a Hamming distance.

13. A system for correcting an epipolar axis to approximate a horizontal axis, the epipolar axis associated with first and second images of a stereo image pair, where a first region of the first image corresponds to a second region of the second image, the method comprising:

a partitioning module configured to partition the first and second images into a plurality of vertically striped regions, each region of the first image corresponding to a region of the second image;

an alignment module configured to vertically shift a region of the first image in a direction calculated to vertically align a portion of the region with a substantially matching portion of the corresponding region;

a block matching module configured to identify a portion of the second region that substantially matches a portion of the first region and to calculate a distance between a portion of the first region and at least two different portions of the second region and identify from among the at least two different portions the one having the least distance from the portion of the first region;

an offset calculation module configured to calculate a vertical offset between the portion of the first region and the substantially matching portion of the second region; and

a region shifting module configured to vertically shift the first region according to the calculated vertical offset to vertically align the substantially matching portions of the first and second regions.

14. A system for correcting an epipolar axis to approximate a horizontal axis, the epipolar axis associated with first and second images of a stereo image pair, where a first region of the first image corresponds to a second region of the second image, and where the first and second images comprise data arrays including rows and columns of pixels, each row and column having an associated number, the method comprising:

a partitioning module configured to partition the first and second images into a plurality of vertically striped regions, each region of the first image corresponding to a region of the second image;

an alignment module configured to vertically shift a region of the first image in a direction calculated to vertically align a portion of the region with a substantially matching portion of the corresponding region;

a block matching module configured to identify a portion of the second region that substantially matches a portion of the first region;

an offset calculation module configured to calculate a vertical offset between the portion of the first region and the substantially matching portion of the second region and to identify a first row number associated with the portion of the first region, identify a second row number associated with the portion of the second region, and subtract the second row number from the first row number; and

a region shifting module configured to vertically shift the first region according to the calculated vertical offset to vertically align the substantially matching portions of the first and second regions.

15. A system for correcting an epipolar axis to approximate a horizontal axis, the epipolar axis associated with first and second images of a stereo image pair, where a first region of the first image corresponds to a second region of the second image, and where the first and second images comprise data arrays including rows and columns of pixels, the method comprising:

a partitioning module configured to partition the first and second images into a plurality of vertically striped regions, each region of the first image corresponding to a region of the second image;

an alignment module configured to vertically shift a region of the first image in a direction calculated to vertically align a portion of the region with a substantially matching portion of the corresponding region;

a block matching module configured to identify a portion of the second region that substantially matches a portion of the first region;

an offset calculation module configured to calculate a vertical offset between the portion of the first region and the substantially matching portion of the second region; and

a region shifting module configured to vertically shift the first region according to the calculated vertical offset to vertically align the substantially matching portions of the first and second regions and to vertically shift the first region with respect to the second region by an integral number of pixel rows corresponding to the vertical offset.

16. A system for correcting an epipolar axis to approximate a horizontal axis, the epipolar axis associated with first and second images of a stereo image pair, where a first region of the first image corresponds to a second region of the second image, the method comprising:

a partitioning module configured to partition the first and second images into a plurality of vertically striped regions, each region of the first image corresponding to a region of the second image;

an alignment module configured to vertically shift a region of the first image in a direction calculated to vertically align a portion of the region with a substantially matching portion of the corresponding region; and

a disparity calculation module configured to calculate at least one disparity value between at least a portion of the vertically shifted region and at least a portion of the corresponding region.

17. An article of manufacture comprising a program storage medium readable by a processor and embodying one or more instructions executable by the processor to perform a method for correcting an epipolar axis to approximate a horizontal axis, the epipolar axis associated with first and second images of a stereo image pair, where a first region of the first image corresponds to a second region of the second image, the method comprising:

partitioning the first and second images into a plurality of vertically striped regions, each region of the first image corresponding to a region of the second image;

vertically shifting a region of the first image in a direction calculated to vertically align a portion of the region with a substantially matching portion of the corresponding region;

identifying a portion of the second region that substantially matches a portion of the first region;

calculating a vertical offset between the portion of the first region and the substantially matching portion of the second region;

vertically shifting the first region according to the calculated vertical offset to vertically align the substantially matching portions of the first and second regions;

repeating the identifying and calculating steps for at least two portions of the first region in order to calculate at least two vertical offsets; and

determining an average of the at least two vertical offsets.

18. An article of manufacture comprising a program storage medium readable by a processor and embodying one or more instructions executable by the processor to perform a method for correcting an epipolar axis to approximate a horizontal axis, the epipolar axis associated with first and second images of a stereo image pair, where a first region of the first image corresponds to a second region of the second image, the method comprising:

partitioning the first and second images into a plurality of vertically striped regions, each region of the first image corresponding to a region of the second image;

vertically shifting a region of the first image in a direction calculated to vertically align a portion of the region with a substantially matching portion of the corresponding region;

identifying a portion of the second region that substantially matches a portion of the first region;

calculating a vertical offset between the portion of the first region and the substantially matching portion of the second region;

vertically shifting the first region according to the calculated vertical offset to vertically align the substantially matching portions of the first and second regions

wherein each portion comprises a section of a vertically striped region.

19. An article of manufacture comprising a program storage medium readable by a processor and embodying one or more instructions executable by the processor to perform a method for correcting an epipolar axis to approximate a horizontal axis, the epipolar axis associated with first and second images of a stereo image pair, where a first region of the first image corresponds to a second region of the second image, the method comprising:

partitioning the first and second images into a plurality of vertically striped regions, each region of the first image corresponding to a region of the second image;

vertically shifting a region of the first image in a direction calculated to vertically align a portion of the region with a substantially matching portion of the corresponding region;

identifying a portion of the second region that substantially matches a portion of the first region by calculating a distance between a portion of the first region and at least two different portions of the second region, and identifying from among the at least two different portions the one having the least distance from the portion of the first region;

calculating a vertical offset between the portion of the first region and the substantially matching portion of the second region; and

vertically shifting the first region according to the calculated vertical offset to vertically align the substantially matching portions of the first and second regions.

20. The article of manufacture of claim 19, wherein the distance comprises a Hamming distance.

21. An article of manufacture comprising a program storage medium readable by a processor and embodying one or more instructions executable by the processor to perform a method for correcting an epipolar axis to approximate a horizontal axis, the epipolar axis associated with first and second images of a stereo image pair, where a first region of the first image corresponds to a second region of the second image, the method comprising:

partitioning the first and second images into a plurality of vertically striped regions, each region of the first image corresponding to a region of the second image;

vertically shifting a region of the first image in a direction calculated to vertically align a portion of the region with a substantially matching portion of the corresponding region;

identifying a portion of the second region that substantially matches a portion of the first region by calculating a similarity value between a portion of the first region and at least two different portions of the second region, and identifying from among the at least two different portions the one most similar to the portion of the first region;

calculating a vertical offset between the portion of the first region and the substantially matching portion of the second region; and

vertically shifting the first region according to the calculated vertical offset to vertically align the substantially matching portions of the first and second regions.

22. An article of manufacture comprising program storage medium readable by a processor and embodying one or more instructions executable by the processor to perform a method for correcting an epipolar axis to approximate a horizontal axis, the epipolar axis associated with first and second images of a stereo image pair, where a first region of the image corresponds to a second region of the second image, and where the first and second images comprise data arrays including rows and columns of pixels, each row and column having an associated number, the method comprising:

partitioning the first and second images into a plurality of vertically striped regions, each region of the first image corresponding to a region of the second image;

vertically shifting a region of the first image in a direction calculated to vertically align a portion of the region with a substantially matching portion of the corresponding region;

identifying a portion of the second region that substantially matches a portion of the first region;

calculating a vertical offset between the portion of the first region and the substantially matching portion of the second region by identifying a first row number associated with the portion of the first region, identifying a second row number associated with the portion of the second region, and subtracting the second row number from the first row number; and

vertically shifting the first region according to the calculated vertical offset to vertically align the substantially matching portions of the first and second regions.

23. An article of manufacture comprising a program storage medium readable by a processor and embodying one or more instructions executable by the processor to perform a method for correcting an epipolar axis to approximate a horizontal axis, the epipolar axis associated with first and second images of a stereo image pair, where a first region of the first image corresponds to a second region of the second image, and where the first and second images comprise data arrays including rows and columns of pixels, the method comprising:

partitioning the first and second images into a plurality of vertically striped regions, each region of the first image corresponding to a region of the second image;

vertically shifting a region of the first image in a direction calculated to vertically align a portion of the region with a substantially matching portion of the corresponding region;

identifying a portion of the second region that substantially matches a portion of the first region;

calculating a vertical offset between the portion of the first region and the substantially matching portion of the second region;

vertically shifting the first region according to the calculated vertical offset to vertically align the substantially matching portions of the first and second regions by vertically shifting the first region with respect to the second region by an integral number of pixel rows corresponding to the vertical offset.

24. An article of manufacture comprising a program storage medium readable by a processor and embodying one or more instructions executable by the processor to perform a method for correcting an epipolar axis approximate a horizontal axis, the epipolar axis associated with first and second images of a stereo image pair, where a first region of the first image corresponds to a second region of the second image, the method comprising:

partitioning the first and second images into a plurality of vertically striped regions, each region of the first image corresponding to a region of the second image;

vertically shifting a region of the first image in a direction calculated to vertically align a portion of the region with a substantially matching portion of the corresponding region; and

calculating at least one disparity value between at least a portion of the vertically shifted region and at least a portion of the corresponding region.