US6044181A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Focal length estimation method and apparatus for construction of panoramic mosaic images
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1997-08-01
•
Granted: 2000-03-28
•
Expires: 2017-08-01
Abstract
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
Inventors
- 👤 Richard Szeliski
- 👤 Heung-Yeung Shum
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 15:18
CPC Classifications
G; G06; G06T; G06T3/00; G06T3/40; G06T3/4038; G06T7/00; G06T7/30; G06T7/32; G06V; G06V10/00; G06V10/10; G06V10/12; G06V10/14; G06V10/147; G06V10/16
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
106 words
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.
Claim 2
Independent Claim
106 words
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.
Claim 3
Dependent Claim
55 words
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.
Claim 4
Dependent Claim
55 words
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.
Claim 5
Dependent Claim
14 words
The method of claim 1 wherein said planar perspective transformation is a 3-by-3 matrix.
Claim 6
Dependent Claim
21 words
The method of claim 4 wherein the 3-by-3 matrix of said planar perspective transformation has a bottom diagonal element of unity.
Claim 7
Dependent Claim
34 words
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.
Claim 8
Dependent Claim
61 words
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.
Claim 9
Dependent Claim
43 words
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.
Claim 10
Dependent Claim
47 words
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.
Claim 11
Dependent Claim
71 words
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.
Claim 12
Dependent Claim
29 words
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.
Claim 13
Dependent Claim
128 words
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.
Claim 14
Dependent Claim
36 words
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.
Claim 15
Dependent Claim
29 words
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.
Claim 16
Dependent Claim
29 words
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.
Claim 17
Dependent Claim
51 words
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.
Claim 18
Dependent Claim
14 words
A computer-readable medium having computer-executable instructions for performing the steps recited in claim 1.
Claim 19
Dependent Claim
135 words
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.
Claim 20
Dependent Claim
135 words
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.
Claim 21
Dependent Claim
54 words
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.
Claim 22
Dependent Claim
54 words
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.
Claim 23
Dependent Claim
14 words
The apparatus of claim 18 wherein said planar perspective transformation is a 3-by-3 matrix.
Claim 24
Dependent Claim
21 words
The apparatus of claim 21 wherein the 3-by-3 matrix of said planar perspective transformation has a bottom diagonal element of unity.
Claim 25
Dependent Claim
34 words
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.
Claim 26
Dependent Claim
57 words
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.
Claim 27
Dependent Claim
42 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-03-28 | 2003-09-27 | 2004-03-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-03-28 | 2007-09-27 | 2008-03-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-03-28 | 2011-09-27 | 2012-03-28 | $7700.00 | Window Closed / Lapsed |