Focal length estimation method and apparatus for construction of panoramic mosaic images

• US 6,044,181 A
• Filed: 08/01/1997
• Issued: 03/28/2000
• Est. Priority Date: 08/01/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Shum, Heung-Yeung, Szeliski, Richard
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): MEHTA, BHAVESH M
• Application Number:
  US08/905,102
• Time in Patent Office: 970 Days
• Field of Search: 382/154, 382/255, 382/284, 382/294, 382/296, 345/419, 345/425, 345/427, 345/429, 345/433-438, 348/42, 348/263, 348/580
• US Class Current: 382/284
• CPC Class Codes: G06T 3/4038 Image mosaicing, e.g. composing plane images from plane sub-images
• CPC Class Codes: G06T 7/32 using correlation-based methods
• 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/16 using multiple overlapping images; Image stitching

Abstract

The focal length estimation method and apparatus claimed in this application aligns plural overlapping images with one another for constructing an image mosaic. This is accomplished by computing a planar perspective transformation between each overlapping pair of the images, computing from the planar perspective transformation a focal length of each image of the pair, computing from the focal length of each image a focal length transformation, computing a rotational transformation for each of the pair of images whereby a combination of the rotational transformation and the focal length transformation relates the respective image to a three-dimensional coordinate system. Registration errors between the pair of images are reduced by incrementally deforming the rotational transformation of one of the pair of images. The planar perspective transform is a matrix of warp elements, and the focal length is computed as a function of the warp elements, the function being derivable by constraining a first two rows or the first two columns of the matrix to have the same norm and to be orthogonal. The focal length of one image of a pair of images is found by applying the constraint on the matrix columns, while the focal length of the other image of the pair is found by applying the constraint on the matrix rows

Claims

1. A method for aligning plural overlapping images useful in constructing a mosaic, comprising:

computing a planar perspective transformation between each overlapping pair of said images;

computing, from said planar perspective transformation, a focal length of each image of said pair;

computing from said focal length of each image a focal length transformation;

computing a rotational transformation for each of said pair of images whereby a combination of said rotational transformation and said focal length transformation relates the respective image to a three-dimensional coordinate system; and

reducing registration errors between said pair of images by incrementally deforming said rotational transformation of one of said pair of images.

2. The method of claim 1 wherein said planar perspective transformation comprises a matrix of warp elements, and wherein the step of computing a focal length comprises computing a function of said warp elements, said function being derivable by constraining a first two rows of said matrix to have the same norm and to be orthogonal.

3. The method of claim 1 wherein said planar perspective transformation comprises a matrix of warp elements, and wherein the step of computing a focal length comprises computing a function of said warp elements, said function being derivable by constraining a first two columns of said matrix to have the same norm and to be orthogonal.

4. The method of claim 1 wherein said planar perspective transformation is a 3-by-3 matrix.

5. The method of claim 4 wherein the 3-by-3 matrix of said planar perspective transformation has a bottom diagonal element of unity.

6. The method of claim 1 wherein said focal length transformation is a 3-by-3 matrix whose top diagonal elements are said focal length, whose bottom diagonal element is unity and whose non-diagonal elements are zeroes.

7. The method of claim 1 wherein the step of incrementally deforming said rotational transformation comprises:

finding an incremental rotation of one image of said pair of images relative to a 3-dimensional coordinate system tending to reduce registration error between overlapping portions of said pair of images;

rotating said one image in accordance with said incremental rotation and repeating said finding step.

8. The method of claim 7 wherein said finding step is repeated until said registration error has been reduced to a desired minimum, and wherein said method further comprises:

producing a final rotation representing a combination of successive incremental rotations of said one image.

9. The method of claim 8 further comprising the step of performing said finding, rotating and repeating steps for plural images in said set of images to produce final rotations therefor, whereby to produce a set of finally warped images from which a mosaic image may be constructed.

10. The method of claim 9, wherein each of said images comprises a planar array of image pixels in a two-dimensional image pixel coordinate system of that image, said method further comprising:

associating with each of said images a respective rotation matrix relating the respective image'"'"'s pixel coordinate system to said 3-dimensional coordinate system, wherein said rotating step comprises multiplying the respective rotation matrix of said second image by said incremental rotation.

11. The method of claim 10 wherein said set of finally warped images comprises, for each of said images, said planar array of image pixels and the respective rotation matrix.

12. The method of claim 7 wherein said finding step comprises:

computing a gradient of said one image, computing a Jacobian of a coordinate system said one image with respect to said incremental rotation, and computing a product of said gradient and Jacobian;

computing a registration error vector between said pair of images and multiplying said error vector by said product of said gradient and Jacobian, whereby to produce a residual error;

computing a transpose of said product of said gradient and Jacobian and combining said transpose with said gradient and Jacobian to produce a matrix;

summing said residual error and summing said matrix over the pixels of said second image to produce residuals and Hessians, and solving normal equations with said residuals and Hessians for said incremental rotation.

13. The method of claim 12 wherein said step of solving said normal equations produces a set of deformation matrix elements, and wherein said step of finding comprises inferring said incremental rotation from said deformation matrix elements.

14. The method of claim 13 wherein said step of inferring comprises computing elements of an angle from said deformation matrix elements and computing said incremental rotation from said angle.

15. The method of claim 7 wherein said rotating step comprises resampling the second one of said pair of images with pixel coordinates warped in accordance with said incremental rotation.

16. The method of claim 7 wherein the images of said set of images are associated with respective rotation matrices defining their respective orientations relative to said 3-dimensional coordinate system, said method further comprising the step of updating the rotation matrix of said one image by multiplying it by said incremental rotation.

17. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 1.

18. Apparatus for use in aligning a set of plural images from which a mosaic image can be produced, said apparatus comprising:

a processor;

memory having executable instructions stored therein; and

wherein the processor, in response to the instructions stored in the memory;

computes a planar perspective transformation between each overlapping pair of said images;

computes, from said planar perspective transformation, a focal length of each image of said pair;

computes from said focal length of each image a focal length transformation;

computes a rotational transformation for each of said pair of images whereby a combination of said rotational transformation and said focal length transformation relates the respective image to a three-dimensional coordinate system; and

reduces registration errors between said pair of images by incrementally deforming said rotational transformation of one of said pair of images.

19. The apparatus claim 18 wherein said planar perspective transformation comprises a matrix of warp elements, and wherein said processor computes said a focal length by computing a function of said warp elements, said function being derivable by constraining a first two rows of said matrix to have the same norm and to be orthogonal.

20. The apparatus of claim 18 wherein said planar perspective transform comprises a matrix of warp elements, and wherein said processor computes a focal length by computing a function of said warp elements, said function being derivable by constraining a first two columns of said matrix to have the same norm and to be orthogonal.

21. The apparatus of claim 18 wherein said planar perspective transformation is a 3-by-3 matrix.

22. The apparatus of claim 21 wherein the 3-by-3 matrix of said planar perspective transformation has a bottom diagonal element of unity.

23. The apparatus of claim 18 wherein said focal length transformation is a 3-by-3 matrix whose top diagonal elements are said focal length, whose bottom diagonal element is unity and whose non-diagonal elements are zeroes.

24. The apparatus of claim 18 wherein the step of incrementally deforming said rotational transformation comprises:

finding an incremental rotation of said one image relative to a 3-dimensional coordinate system tending to reduce registration error between overlapping portions of said pair of images;

rotating said one image in accordance with said incremental rotation and repeating said finding step.

25. The apparatus of claim 24 wherein said finding step is repeated until said registration error has been reduced to a desired minimum, and wherein said apparatus further produces:

a final rotation representing a combination of successive incremental rotations of said one image.