Patent US6157747A successfully refreshed from Google Patents.
US6157747A
Expired / Lapsed
US
⏱️ 0.0 years remaining
3-dimensional image rotation method and apparatus for producing image mosaics
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1997-08-01
•
Granted: 2000-12-05
•
Expires: 2017-08-01
Abstract
Abstract The invention aligns a set of plural images to construct a mosaic image. At least different pairs of the images overlap partially (or fully), and typically are images captured by a camera looking at the same scene but oriented at different angles from approximately the same location or similar locations. In order to align one of the images with another one of the images, the following steps are carried out: (a) determining a difference error between the one image and the other image; (b) computing an incremental rotation of the one image relative to a 3-dimensional coordinate system through an incremental angle which tends to reduce the difference error; and (c) rotating the one image in accordance with the incremental rotation to produce an incrementally warped version of the one image. As long as the difference error remains significant, the method continues by re-performing the foregoing determining, computing and rotating steps but this time with the incrementally warped version of the one image.
Inventors
- 👤 Richard Szeliski
- 👤 Heung-Yeung Shum
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 12:33
CPC Classifications
G; G06; G06T; G06T3/00; G06T3/14; G06T3/153; G06T3/40; G06T3/4038; G06V; G06V10/00; G06V10/10; G06V10/12; G06V10/14; G06V10/147; G06V10/20; G06V10/24; G06V10/16
Claims Analysis
Total Claims: 45
Claim 1
Independent Claim
81 words
A 3-dimensional rotational method for aligning a set of at least partially overlapping plural images to construct a mosaic image, comprising the following steps: for at least first and second images of said set of images, finding an incremental rotation of said second image relative to a 3-dimensional coordinate system tending to reduce registration error between overlapping portions of said first and second images; rotating said second image in accordance with said incremental rotation; and repeating said finding and rotating steps.
Claim 2
Dependent Claim
81 words
A 3-dimensional rotational method for aligning a set of at least partially overlapping plural images to construct a mosaic image, comprising the following steps: for at least first and second images of said set of images, finding an incremental rotation of said second image relative to a 3-dimensional coordinate system tending to reduce registration error between overlapping portions of said first and second images; rotating said second image in accordance with said incremental rotation; and repeating said finding and rotating steps.
Claim 3
Dependent Claim
44 words
The method of claim 1 wherein the step of repeating said finding and rotating steps produces successive incremental rotations of said second image, and wherein the method further comprises producing a final rotation representing a combination of successive incremental rotations of said second image.
Claim 4
Dependent Claim
47 words
The method of claim 2 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 5
Dependent Claim
71 words
The method of claim 3, 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 6
Dependent Claim
29 words
The method of claim 4 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 7
Dependent Claim
126 words
The method of claim 1 wherein said finding step comprises: computing a gradient of said first image, computing a Jacobian of a coordinate system of said second image with respect to said incremental rotation, and computing a product of said gradient and Jacobian; computing a registration error vector between said first and second 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.
Claim 8
Dependent Claim
18 words
The method of claim 6 wherein the step of solving said normal equations produces an incremental rotational vector.
Claim 9
Dependent Claim
21 words
The method of claim 7 wherein the step of finding further comprises computing said incremental rotation from said incremental rotational vector.
Claim 10
Dependent Claim
24 words
The method of claim 1 wherein said rotating step comprises resampling said second image with pixel coordinates warped in accordance with said incremental rotation.
Claim 11
Dependent Claim
51 words
The method of claim 1 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 second image by multiplying it by said incremental rotation.
Claim 12
Dependent Claim
14 words
A computer-readable medium having computer-executable instructions for performing the steps recited in claim 1.
Claim 13
Independent Claim
100 words
A method for aligning a set of plural images to construct a mosaic image, comprising carrying out the following steps for each one of said set of plural images: determining a difference error between said one image and an other one of said images of said set; computing an incremental rotation of said one image relative to a 3-dimensional coordinate system tending to reduce said difference error; rotating said one image in accordance with said incremental rotation to produce an incrementally warped version of said one image; and repeating said determining, computing and rotating steps with said incrementally warped version.
Claim 14
Independent Claim
100 words
A method for aligning a set of plural images to construct a mosaic image, comprising carrying out the following steps for each one of said set of plural images: determining a difference error between said one image and an other one of said images of said set; computing an incremental rotation of said one image relative to a 3-dimensional coordinate system tending to reduce said difference error; rotating said one image in accordance with said incremental rotation to produce an incrementally warped version of said one image; and repeating said determining, computing and rotating steps with said incrementally warped version.
Claim 15
Dependent Claim
41 words
The method of claim 12 wherein said re-performing step is repeated until said difference error has been reduced to a desired minimum, said method further comprising: producing a final rotation representing a combination of successive incremental rotations of said one image.
Claim 16
Dependent Claim
56 words
The method of claim 13 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 computed by said computing step.
Claim 17
Dependent Claim
50 words
The method of claim 14 further comprising the step of performing said determining, computing, rotating and re-performing steps for plural images in said set of images to produce final rotations of said images, whereby to produce a set of finally warped images from which a mosaic image may be constructed.
Claim 18
Dependent Claim
46 words
The method of claim 15, wherein each of said images comprises a planar array of image pixels in a two-dimensional image pixel coordinate system of that image, wherein said each respective rotation matrix relates the respective image's 2-dimensional pixel coordinate system to said 3-dimensional coordinate system.
Claim 19
Dependent Claim
29 words
The method of claim 16 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 20
Dependent Claim
30 words
The method of claim 12 wherein said determining step comprises: computing an error vector between said one image and said other image at each pixel coordinate of said one image.
Claim 21
Dependent Claim
84 words
The method of claim 18 wherein said one image is defined as individual pixels relative to a pixel coordinate system and said incremental rotation defines a warped version of said pixel coordinate system, and wherein the step of computing an incremental rotation comprises: determining for each pixel coordinate of said one image: (a) a gradient, (b) a Jacobian of said warped version of said pixel coordinate system of said one image relative to said incremental rotation, (c) a product of said gradient and Jacobian.
Claim 22
Dependent Claim
86 words
The method of claim 19 wherein the step of computing computing an incremental rotation further comprises: 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 pixels of said one image to produce residuals and Hessians, and solving normal equations with said residuals and Hessians.
Claim 23
Dependent Claim
18 words
The method of claim 20 wherein the step of solving said normal equations produces an incremental rotational vector.
Claim 24
Dependent Claim
23 words
The method of claim 21 wherein the step of computing an incremental rotation comprises computing said incremental rotation from said incremental rotational vector.
Claim 25
Dependent Claim
48 words
The method of claim 12 wherein said one image is defined by individual pixels in a pixel coordinate system and wherein said rotating step comprises: resampling said one image with a version of said pixel coordinate system of said one image warped in accordance with said incremental rotation.
Claim 26
Dependent Claim
14 words
A computer-readable medium having computer-executable instructions for performing the steps recited in claim 12.
Claim 27
Dependent Claim
102 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 performs successive iterations in that for each iteration the processor: for at least first and second images of said set of images, determines an incremental rotation of said second image relative to a 3-dimensional coordinate system which reduces registration error between overlapping portions of said first and second images; and rotates said second image in accordance with said incremental rotation.
Claim 28
Dependent Claim
102 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 performs successive iterations in that for each iteration the processor: for at least first and second images of said set of images, determines an incremental rotation of said second image relative to a 3-dimensional coordinate system which reduces registration error between overlapping portions of said first and second images; and rotates said second image in accordance with said incremental rotation.
Claim 29
Dependent Claim
83 words
The apparatus of claim 25 wherein said processor performs successive iterations in that the processor: determines a further incremental rotation of the warped second image which reduces registration error between the warped second image and the first image; further rotates the second image by said further incremental rotation; and performs the forgoing steps in repetitive cycles until the registration error has been reduced to a desired minimum, and produces a final rotation representing a combination of successive incremental rotations of said second image.
Claim 30
Dependent Claim
126 words
The apparatus of claim 25 wherein said processor determines said incremental rotation in that said processor: computes a gradient and a Jacobian of a warped version of a coordinate system of said second image and computes a product of said gradient and Jacobian; computes a registration error vector between said first and second images and multiplying said error vector by said product of said gradient and Jacobian, whereby to produce a residual error; computes a transpose of said product of said gradient and Jacobian and combining said transpose with said gradient and Jacobian to produce a matrix; sums said residual error and sums said matrix over the pixels of said second image to produce residuals and Hessians, and solves normal equations with said residuals and Hessians.
Claim 31
Dependent Claim
18 words
The apparatus of claim 27 wherein said processor, in solving said normal equations, produces an incremental rotational vector.
Claim 32
Dependent Claim
25 words
The apparatus of claim 28 wherein said processor computes said incremental rotation in that said processor computes said incremental rotation from said incremental rotational vector.
Claim 33
Dependent Claim
29 words
The apparatus of claim 25 said processor rotates said second image in that said processor resamples said second image with pixel coordinates warped in accordance with said incremental rotation.
Claim 34
Dependent Claim
58 words
The apparatus of claim 25 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, and wherein said processor, in response to the instructions stored in said memory, further updates the rotation matrix of said second image by multiplying it by said incremental rotation.
Claim 35
Dependent Claim
108 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 performs successive iterations in that the processor: determines a difference error between said one image and an other one of said images of said set; computes an incremental rotation of said one image relative to a 3-dimensional coordinate system tending to reduce said difference error; and rotates said one image in accordance with said incremental rotation to produce an incrementally warped version of said one image.
Claim 36
Dependent Claim
108 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 performs successive iterations in that the processor: determines a difference error between said one image and an other one of said images of said set; computes an incremental rotation of said one image relative to a 3-dimensional coordinate system tending to reduce said difference error; and rotates said one image in accordance with said incremental rotation to produce an incrementally warped version of said one image.
Claim 37
Dependent Claim
56 words
The apparatus of claim 32 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 processor, in further response to the instructions stored in said memory: updates the rotation matrix of said one image by multiplying it by said incremental rotation.
Claim 38
Dependent Claim
35 words
The apparatus of claim 32 wherein said processor determines said error in that said processor computes an error vector between said one image and said other image at each pixel coordinate of said one image.
Claim 39
Dependent Claim
85 words
The apparatus claim 34 wherein said one image is defined as individual pixels relative to a pixel coordinate system and said incremental rotation defines a warped version of said pixel coordinate system, and wherein said processor computes said incremental rotation in that said processor: determines for each pixel coordinate of said one image: (a) a gradient, (b) a Jacobian of said warped version of said pixel coordinate system of said one image relative to said incremental rotation, (c) a product of said gradient and Jacobian.
Claim 40
Dependent Claim
87 words
The apparatus of claim 35 wherein said processor computes said incremental rotation in that said processor further: multiplies said error vector by said product of said gradient and Jacobian, whereby to produce a residual error; computes a transpose of said product of said gradient and Jacobian and combines said transpose with said gradient and Jacobian to produce a matrix; sums said residual error and summing said matrix over pixels of said one image to produce residuals and Hessians, and solves normal equations with said residuals and Hessians.
Claim 41
Dependent Claim
18 words
The apparatus of claim 36 wherein said processor, in solving said normal equations, produces an incremental rotational vector.
Claim 42
Dependent Claim
25 words
The apparatus of claim 37 wherein said processor determines said incremental rotation in that said processor computes said incremental rotation from said incremental rotational vector.
Claim 43
Dependent Claim
46 words
The apparatus of claim 38, wherein each of said images comprises a planar array of image pixels in a two-dimensional image pixel coordinate system of that image, wherein said each respective rotation matrix relates the respective image's 2-dimensional pixel coordinate system to said 3-dimensional coordinate system.
Claim 44
Dependent Claim
29 words
The apparatus of claim 39 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 45
Dependent Claim
54 words
The apparatus of claim 32 wherein said one image is defined by individual pixels in a pixel coordinate system and wherein said processor rotates said one image in that said processor: resamples said one image with a version of said pixel coordinate system of said one image warped in accordance with said incremental rotation.
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-12-05 | 2004-06-05 | 2004-12-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-12-05 | 2008-06-05 | 2008-12-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-12-05 | 2012-06-05 | 2012-12-05 | $7700.00 | Window Closed / Lapsed |