Fast epipolar line adjustment of stereo pairs

• US 6,671,399 B1
• Filed: 10/27/1999
• Issued: 12/30/2003
• Est. Priority Date: 10/27/1999
• Status: Expired due to Term

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Berestov, Alexander
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Lu, Tom Y.
• Application Number:
  US09/428,286
• Time in Patent Office: 1,525 Days
• Field of Search: 382/154, 382/209, 382/286, 382/287, 382/288, 382/289, 382/218, 345/419-427, 356/12, 348/42
• US Class Current: 382/154
• CPC Class Codes: G06T 7/593 from stereo images
• 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

Abstract

A method (500) adjusts the epipolar lines associated with two or more images (110,120) taken of the same scene such that the images (110,120) are and vertically aligned. The method (500) creates two or more search columns on the first image. The images (110,120) are split into grayscale sub-images corresponding to each color coordinate used to describe the color of a point in the image. A matching algorithm is applied to each point in the search column in each sub-image pair to calculate the vertical shift between the matched points. The shift values calculated for the matched points are then extrapolated across the entire image and used to align the points in the first (110) and second (120) image.

Claims

1. A method for aligning two original images of a scene, such that the images have at least some overlap area, said method comprising:

creating a left and a right search column on at least one of the original images, such that at least one of the columns includes at least part of the overlap area;

creating two sets of gray-scale sub-images, one set of sub-images for each of the two original images;

pairing the sub-images generated from the first original image with sub-images from the second original image such that a sub-image pair shares the same assigned color coordinate;

running a matching algorithm on each point in the right and left search column of each sub-image pair;

calculating vertical shift between points identified as matching by the matching algorithm;

selecting points with identical vertical shift values; and

aligning the points that were not selected in the image by extrapolating the resulting calculated vertical shift values for each column.

2. The method of claim 1, wherein the step of creating search columns, comprising the sub-steps of:

creating one search column in a middle of the first image;

running the matching algorithm on at least one point within the search column such that the points are matched with at least one point in the second image;

calculating an average horizontal shift for the matched points;

responsive to a calculated horizontal shift value that matches points in the middle of the first image with points to the left of the middle of the second image, creating two search columns on the first image such that the left column is shifted by at least the calculated horizontal shift value from the edge of the first image and the right column is created to the right of the first column; and

responsive to a calculated horizontal shift value that matches points in the middle of the first image with points to the right of the middle of the second image, creating two search columns on the first image such that the right column is shifted by at least the calculated horizontal shift value from the right edge of the first image and the left column is created anywhere to the left of the right column.

3. The method of claim 1, wherein running the matching algorithm comprises running a matching algorithm as described with reference to FIG. 2.

4. The method of claim 1, wherein running the matching algorithm comprises running a correlation-based matching algorithm.

5. The method of claim 1, wherein running the matching algorithm comprises running a feature-based matching algorithm.

6. The method of claim 1, wherein running the matching algorithm comprises running a phase-based matching algorithm.

7. The method of claim 1, wherein the step of aligning the remaining points comprises using an equation to calculate the shift values.

8. The method of claim 7, wherein the equation is linear.

9. The method of claim 7, wherein the equation is non-linear.

10. The method of claim 7, wherein one portion of the image is aligned using a linear equation and one portion of the image is aligned using a non-linear equation.

11. The method of claim 1, wherein the step of aligning the remaining points further comprises the steps of:

calculating a linear equation of the from mx+b, where m is equal to the difference between the shift values calculated for the left and right search columns divided by the number of points between the right and left search column and where b is equal to the calculated shift for the left column;

calculating a shift value for each column of the image using the calculated linear equation by replacing x with the number of columns between the left column and the column being shifted, such that columns to the left of the left column are assigned a negative x value;

shifting the points corresponding to that column by the value generated by the linear equation.

12. A system for aligning two original images of a scene, such that the images have at least some overlap area, said system comprising:

means for creating a left and a right search column on at least one of the original images such that at least one of the created columns includes at least part of the overlap area;

coupled to the means for creating a left and right search column, means for creating two sets of gray-scale sub-images, one set of sub-images for each of the two original images;

coupled to the means for creating two sets of grayscale images, means for pairing the sub-images generated from the first original image with sub-images from the second original image such that a sub-image pair shares the same assigned color coordinate;

coupled to the means for pairing, means for running a matching algorithm on each of the points in the search column of each sub-image pair;

coupled to the means for running the matching algorithm, means for calculating vertical shift between points between points identified by the matching algorithm;

coupled to the means for calculating, means for selecting points with identical calculated vertical shift values; and

coupled to the means for selecting, means for aligning the points in the image that were not selected by the means for selecting by extrapolating the resulting calculated vertical shift values for each column.

13. The system of claim 12, wherein the means for creating search columns comprises:

means for creating one search column in a middle of the first image;

coupled to the means for creating, means for executing the matching algorithm on at least one point within the search column such that the point is matched with at least one point in the second image;

coupled to the means for executing the algorithm, means for calculating at least one average horizontal shift value for points located by the matching algorithm; and

coupled to the means for calculating, means for using the calculated value to generate a linear equation.

14. The system of claim 12, wherein means for running the matching algorithm comprises means for running a matching algorithm as described with reference to FIG. 2.

15. The method of claim 12, wherein means for running the matching algorithm comprises means for running a correlation-based matching algorithm.

16. The system of claim 12, wherein the means for running the matching algorithm comprises means for running a feature-based matching algorithm.

17. The system of claim 12, wherein running the matching algorithm comprises means for running a phase-based matching algorithm.

18. The system of claim 12, wherein the means for aligning the remaining points comprises means for generating an equation to calculate the shift values.

19. The system of claim 18, wherein means for generating an equation comprises means for generating a linear equation.

20. The system of claim 18, wherein means for generating an equation comprises means for generating a non-linear equation.

21. The system of claim 18, wherein means for aligning comprises means for aligning one portion of the image using a linear equation and aligning the remaining portion of the image using a non-linear equation.

22. A computer-readable medium containing a computer program for aligning two images, said program containing instructions for directing the computer to execute the steps of:

creating a left and a right search column on at least one of the original images, such that at least one of the columns includes at least part of the overlap area;

creating two sets of gray-scale sub-images, one set of sub-images for each of the two original images;

pairing the sub-images generated from the first original image with sub-images from the second original image such that a sub-image pair shares the same assigned color coordinate;

running a matching algorithm on each point in the right and left search column of each sub-image pair;

calculating vertical shift between points identified as matching by the matching algorithm;

selecting points with identical vertical shift values; and

aligning the points that were not selected in the image by extrapolating the resulting calculated vertical shift values for each column.