Patent US5987164A successfully refreshed from Google Patents.
US5987164A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Block adjustment method and apparatus for construction of image mosaics
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1997-08-01
•
Granted: 1999-11-16
•
Expires: 2017-08-01
Abstract
Abstract The invention is embodied in a block adjustment method and apparatus which simultaneously aligns a set of overlapping images in order to construct an image mosaic. For each one of the images of the set, the invention performs the alignment by determining ray directions relative to a 3-dimensional coordinate system at plural predetermined pixel locations in the one image. For each one of the plural pixel locations in the one image, ray directions are determined relative to the 3-dimensional coordinate system of the corresponding pixel location in each one of the other images overlapping the one predetermined pixel location of the one image. Then, incremental deformations of the overlapping images are computed which simultaneously minimize differences between the ray directions of plural pairs of the overlapping images which include the one image. The foregoing is performed for each of the plural predetermined pixel locations of the one image simultaneously. The images are warped in accordance with the incremental deformations and the process is repeated.
Inventors
- 👤 Richard Szeliski
- 👤 Heung-Yeung Shum
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 17:33
CPC Classifications
G; G06; G06T; G06T3/00; G06T3/40; G06T3/4038; G06T7/00; G06T7/30; G06T7/33; G06V; G06V10/00; G06V10/10; G06V10/12; G06V10/14; G06V10/147; G06V10/16
Claims Analysis
Total Claims: 83
Claim 1
Independent Claim
113 words
A method for performing simultaneously alignment of a set of overlapping images, comprising: for each one of said images of said set, determining ray directions relative to a 3-dimensional coordinate system at plural predetermined pixel locations in said one image; for each one of said plural pixel locations in said one image: (a) determining ray directions relative to said 3-dimensional coordinate system of the corresponding pixel location in each one of the other images overlapping said one predetermined pixel location of said one image, and (b) computing incremental deformations of said overlapping images which simultaneously minimize differences between the ray directions of plural pairs of said overlapping images which include said one image.
Claim 2
Independent Claim
113 words
A method for performing simultaneously alignment of a set of overlapping images, comprising: for each one of said images of said set, determining ray directions relative to a 3-dimensional coordinate system at plural predetermined pixel locations in said one image; for each one of said plural pixel locations in said one image: (a) determining ray directions relative to said 3-dimensional coordinate system of the corresponding pixel location in each one of the other images overlapping said one predetermined pixel location of said one image, and (b) computing incremental deformations of said overlapping images which simultaneously minimize differences between the ray directions of plural pairs of said overlapping images which include said one image.
Claim 3
Dependent Claim
26 words
The method of claim 1 further comprising performing said determining and computing steps for each of said plural predetermined pixel locations of said one image simultaneously.
Claim 4
Dependent Claim
24 words
The method of claim 1 further comprising warping said images in accordance with said incremental deformations and then repeating said determining and computing steps.
Claim 5
Dependent Claim
29 words
The method of claim 1 wherein said one image is divided into plural patches and said plural predetermined pixel locations constitute one pixel in each of said plural patches.
Claim 6
Dependent Claim
21 words
The method of claim 4 wherein said one pixel in each of said patches comprises a center pixel of said patch.
Claim 7
Dependent Claim
19 words
The method of claim 1 wherein said deformations are defined by incremental 3-dimensional rotations relative to said coordinate system.
Claim 8
Dependent Claim
14 words
The method of claim 1 wherein said deformations are defined by planar perspective transformations.
Claim 9
Dependent Claim
19 words
The method of claim 1 wherein said ray directions are defined by 3-dimensional rotations relative to said coordinate system.
Claim 10
Dependent Claim
15 words
The method of claim 1 wherein said ray directions are defined by planar perspective transformations.
Claim 11
Dependent Claim
27 words
The method of claim 1 wherein each of said ray directions is a ray extending from an origin of said coordinate system to the corresponding pixel location.
Claim 12
Dependent Claim
40 words
The method of claim 1 wherein each of said ray directions is defined relative to at least one of (a) a pixel coordinate position, (b) a 3-dimensional rotational transformation relative to said coordinate system, and (c) an image focal length.
Claim 13
Dependent Claim
24 words
The method of claim 11 wherein said computing comprises computing at least one of an incremental rotation and an incremental change in focal length.
Claim 14
Dependent Claim
21 words
The method of claim 11 wherein said computing comprises computing both an incremental rotation and an incremental change in focal length.
Claim 15
Dependent Claim
37 words
The method of claim 1 wherein the steps of claim 1 are preceded by performing an initial sequential alignment of said images to establish a transformation of each image relating the respective image to said coordinate system.
Claim 16
Dependent Claim
14 words
The method of claim 14 wherein incremental deformations comprise incremental changes of said transformations.
Claim 17
Dependent Claim
24 words
The method of claim 15 wherein said performing said initial sequential alignment comprises minimizing differences between overlapping pixels of overlapping ones of said images.
Claim 18
Dependent Claim
28 words
The method of claim 16 further comprising determining which pairs of said images significantly overlap, and discarding other pairs of said images from said set of overlapping images.
Claim 19
Dependent Claim
24 words
The method of claim 17 wherein other pairs of said images are discarded unless at least a predetermined fraction of the pixels thereof overlap.
Claim 20
Dependent Claim
14 words
A computer-readable medium having computer-executable instructions for performing the steps recited in claim 1.
Claim 21
Independent Claim
97 words
A method for performing simultaneous alignment of a set of overlapping images, comprising: for each one of said images of said set, determining ray directions relative to a 3-dimensional coordinate system at plural pixel locations in a said one image; determining ray directions relative to said 3-dimensional coordinate system at corresponding pixel locations in the other images overlying said one image to form a bundle of rays at each of said corresponding pixel locations; and computing incremental deformations of said overlapping images which simultaneously minimize differences in ray directions in each of said bundles of ray directions.
Claim 22
Independent Claim
97 words
A method for performing simultaneous alignment of a set of overlapping images, comprising: for each one of said images of said set, determining ray directions relative to a 3-dimensional coordinate system at plural pixel locations in a said one image; determining ray directions relative to said 3-dimensional coordinate system at corresponding pixel locations in the other images overlying said one image to form a bundle of rays at each of said corresponding pixel locations; and computing incremental deformations of said overlapping images which simultaneously minimize differences in ray directions in each of said bundles of ray directions.
Claim 23
Dependent Claim
42 words
The method of claim 20 wherein the step of computing said incremental deformations comprises: defining a consensus ray direction at each of said corresponding pixel locations; and minimizing differences between each of said bundle of rays and the corresponding consensus ray direction.
Claim 24
Dependent Claim
24 words
The method of claim 21 wherein said consensus ray direction comprises a normalized sum of the ray directions in the corresponding bundle of rays.
Claim 25
Dependent Claim
26 words
The method of claim 20 further comprising performing said determining and computing steps for each of said plural predetermined pixel locations of said one image simultaneously.
Claim 26
Dependent Claim
24 words
The method of claim 20 further comprising warping said images in accordance with said incremental deformations and then repeating said determining and computing steps.
Claim 27
Dependent Claim
29 words
The method of claim 20 wherein said one image is divided into plural patches and said plural predetermined pixel locations constitute one pixel in each of said plural patches.
Claim 28
Dependent Claim
21 words
The method of claim 25 wherein said one pixel in each of said patches comprises a center pixel of said patch.
Claim 29
Dependent Claim
19 words
The method of claim 20 wherein said deformations are defined by incremental 3-dimensional rotations relative to said coordinate system.
Claim 30
Dependent Claim
14 words
The method of claim 20 wherein said deformations are defined by planar perspective transformations.
Claim 31
Dependent Claim
19 words
The method of claim 20 wherein said ray directions are defined by 3-dimensional rotations relative to said coordinate system.
Claim 32
Dependent Claim
15 words
The method of claim 20 wherein said ray directions are defined by planar perspective transformations.
Claim 33
Dependent Claim
27 words
The method of claim 20 wherein each of said ray directions is a ray extending from an origin of said coordinate system to the corresponding pixel location.
Claim 34
Dependent Claim
40 words
The method of claim 20 wherein each of said ray directions is defined relative to at least one of (a) a pixel coordinate position, (b) a 3-dimensional rotational transformation relative to said coordinate system, and (c) an image focal length.
Claim 35
Dependent Claim
24 words
The method of claim 32 wherein said computing comprises computing at least one of an incremental rotation and an incremental change in focal length.
Claim 36
Dependent Claim
21 words
The method of claim 32 wherein said computing comprises computing both an incremental rotation and an incremental change in focal length.
Claim 37
Dependent Claim
38 words
The method of claim 20 wherein the steps of determining and computing are preceded by performing an initial sequential alignment of said images to establish a transformation of each image relating the respective image to said coordinate system.
Claim 38
Dependent Claim
14 words
The method of claim 35 wherein incremental deformations comprise incremental changes of said transformations.
Claim 39
Dependent Claim
24 words
The method of claim 36 wherein said performing said initial sequential alignment comprises minimizing differences between overlapping pixels of overlapping ones of said images.
Claim 40
Dependent Claim
28 words
The method of claim 37 further comprising determining which pairs of said images significantly overlap, and discarding other pairs of said images from said set of overlapping images.
Claim 41
Dependent Claim
24 words
The method of claim 38 wherein other pairs of said images are discarded unless at least a predetermined fraction of the pixels thereof overlap.
Claim 42
Dependent Claim
14 words
A computer-readable medium having computer-executable instructions for performing the steps recited in claim 20.
Claim 43
Dependent Claim
145 words
Apparatus for use in performing simultaneous alignment of a set of overlapping 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: for each one of said images of said set, determines ray directions relative to a 3-dimensional coordinate system at plural predetermined pixel locations in said one image; for each one of said plural pixel locations in said one image: (a) determines ray directions relative to said 3-dimensional coordinate system of the corresponding pixel location in each one of the other images overlapping said one predetermined pixel location of said one image, and (b) computes incremental deformations of said overlapping images which simultaneously minimize differences between the ray directions of plural pairs of said overlapping images which include said one image.
Claim 44
Dependent Claim
145 words
Apparatus for use in performing simultaneous alignment of a set of overlapping 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: for each one of said images of said set, determines ray directions relative to a 3-dimensional coordinate system at plural predetermined pixel locations in said one image; for each one of said plural pixel locations in said one image: (a) determines ray directions relative to said 3-dimensional coordinate system of the corresponding pixel location in each one of the other images overlapping said one predetermined pixel location of said one image, and (b) computes incremental deformations of said overlapping images which simultaneously minimize differences between the ray directions of plural pairs of said overlapping images which include said one image.
Claim 45
Dependent Claim
30 words
The apparatus of claim 41 wherein said processor determines said ray directions and computes said incremental deformations for each of said plural predetermined pixel locations of said one image simultaneously.
Claim 46
Dependent Claim
18 words
The apparatus of claim 41 wherein said processor further warps said images in accordance with said incremental deformations.
Claim 47
Dependent Claim
29 words
The apparatus of claim 41 wherein said one image is divided into plural patches and said plural predetermined pixel locations constitute one pixel in each of said plural patches.
Claim 48
Dependent Claim
21 words
The apparatus of claim 44 wherein said one pixel in each of said patches comprises a center pixel of said patch.
Claim 49
Dependent Claim
20 words
The apparatus of claim 41 wherein said processor computes said deformations as incremental 3-dimensional rotations relative to said coordinate system.
Claim 50
Dependent Claim
14 words
The apparatus of claim 41 wherein processor computes said deformations as planar perspective transformations.
Claim 51
Dependent Claim
19 words
The apparatus of claim 41 wherein said ray directions are defined by 3-dimensional rotations relative to said coordinate system.
Claim 52
Dependent Claim
15 words
The apparatus of claim 41 wherein said ray directions are defined by planar perspective transformations.
Claim 53
Dependent Claim
27 words
The apparatus of claim 41 wherein each of said ray directions is a ray extending from an origin of said coordinate system to the corresponding pixel location.
Claim 54
Dependent Claim
40 words
The apparatus of claim 41 wherein each of said ray directions is defined relative to at least one of (a) a pixel coordinate position, (b) a 3-dimensional rotational transformation relative to said coordinate system, and (c) an image focal length.
Claim 55
Dependent Claim
28 words
The apparatus of claim 51 wherein said processor computes said incremental deformation by computing at least one of an incremental rotation and an incremental change in focal length.
Claim 56
Dependent Claim
21 words
The apparatus of claim 51 wherein said computes comprises computes both an incremental rotation and an incremental change in focal length.
Claim 57
Dependent Claim
37 words
The apparatus of claim 41 wherein said processor, in further response to said instructions, performs an initial sequential alignment of said images to establish a transformation of each image relates the respective image to said coordinate system.
Claim 58
Dependent Claim
14 words
The apparatus of claim 54 wherein incremental deformations comprise incremental changes of said transformations.
Claim 59
Dependent Claim
28 words
The apparatus of claim 55 wherein said processor performs said initial sequential alignment in that said processor minimizes differences between overlapping pixels of overlapping ones of said images.
Claim 60
Dependent Claim
35 words
The apparatus of claim 56 wherein said processor, in further response to said insturctions, determines which pairs of said images significantly overlap, and discards other pairs of said images from said set of overlapping images.
Claim 61
Dependent Claim
30 words
The apparatus of claim 57 wherein said processor, in response to said instructions, discards other pairs of said images unless at least a predetermined fraction of the pixels thereof overlap.
Claim 62
Dependent Claim
129 words
Apparatus for use in performing simultaneous alignment of a set of overlapping 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: for each one of said images of said set, determines ray directions relative to a 3-dimensional coordinate system at plural pixel locations in a said one image; determines ray directions relative to said 3-dimensional coordinate system at corresponding pixel locations in the other images overlyes said one image to form a bundle of rays at each of said corresponding pixel locations; and computes incremental deformations of said overlapping images which simultaneously minimize differences in ray directions in each of said bundles of ray directions.
Claim 63
Dependent Claim
129 words
Apparatus for use in performing simultaneous alignment of a set of overlapping 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: for each one of said images of said set, determines ray directions relative to a 3-dimensional coordinate system at plural pixel locations in a said one image; determines ray directions relative to said 3-dimensional coordinate system at corresponding pixel locations in the other images overlyes said one image to form a bundle of rays at each of said corresponding pixel locations; and computes incremental deformations of said overlapping images which simultaneously minimize differences in ray directions in each of said bundles of ray directions.
Claim 64
Dependent Claim
44 words
The apparatus of claim 59 wherein said processor computes said incremental deformations in that said processor: defines a consensus ray direction at each of said corresponding pixel locations; and minimizes differences between each of said bundle of rays and the corresponding consensus ray direction.
Claim 65
Dependent Claim
24 words
The apparatus of claim 60 wherein said consensus ray direction comprises a normalized sum of the ray directions in the corresponding bundle of rays.
Claim 66
Dependent Claim
36 words
The apparatus of claim 59 wherein said processor, in further response to said instructions, determines said ray directions and computes said incremental deformations for each of said plural predetermined pixel locations of said one image simultaneously.
Claim 67
Dependent Claim
30 words
The apparatus of claim 62 wherein said processor determines said ray directions and computes said incremental deformations for each of said plural predetermined pixel locations of said one image simultaneously.
Claim 68
Dependent Claim
18 words
The apparatus of claim 62 wherein said processor further warps said images in accordance with said incremental deformations.
Claim 69
Dependent Claim
29 words
The apparatus of claim 59 wherein said one image is divided into plural patches and said plural predetermined pixel locations constitute one pixel in each of said plural patches.
Claim 70
Dependent Claim
21 words
The apparatus of claim 65 wherein said one pixel in each of said patches comprises a center pixel of said patch.
Claim 71
Dependent Claim
20 words
The apparatus of claim 59 wherein said processor computes said deformations as incremental 3-dimensional rotations relative to said coordinate system.
Claim 72
Dependent Claim
14 words
The apparatus of claim 59 wherein processor computes said deformations as planar perspective transformations.
Claim 73
Dependent Claim
19 words
The apparatus of claim 59 wherein said ray directions are defined by 3-dimensional rotations relative to said coordinate system.
Claim 74
Dependent Claim
15 words
The apparatus of claim 59 wherein said ray directions are defined by planar perspective transformations.
Claim 75
Dependent Claim
27 words
The apparatus of claim 59 wherein each of said ray directions is a ray extending from an origin of said coordinate system to the corresponding pixel location.
Claim 76
Dependent Claim
40 words
The apparatus of claim 59 wherein each of said ray directions is defined relative to at least one of (a) a pixel coordinate position, (b) a 3-dimensional rotational transformation relative to said coordinate system, and (c) an image focal length.
Claim 77
Dependent Claim
28 words
The apparatus of claim 72 wherein said processor computes said incremental deformation by computing at least one of an incremental rotation and an incremental change in focal length.
Claim 78
Dependent Claim
21 words
The apparatus of claim 72 wherein said computes comprises computes both an incremental rotation and an incremental change in focal length.
Claim 79
Dependent Claim
37 words
The apparatus of claim 59 wherein said processor, in further response to said instructions, performs an initial sequential alignment of said images to establish a transformation of each image relates the respective image to said coordinate system.
Claim 80
Dependent Claim
14 words
The apparatus of claim 75 wherein incremental deformations comprise incremental changes of said transformations.
Claim 81
Dependent Claim
28 words
The apparatus of claim 76 wherein said processor performs said initial sequential alignment in that said processor minimizes differences between overlapping pixels of overlapping ones of said images.
Claim 82
Dependent Claim
35 words
The apparatus of claim 77 wherein said processor, in further response to said insturctions, determines which pairs of said images significantly overlap, and discards other pairs of said images from said set of overlapping images.
Claim 83
Dependent Claim
30 words
The apparatus of claim 78 wherein said processor, in response to said instructions, discards other pairs of said images unless at least a predetermined fraction of the pixels thereof overlap.
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) | 2002-11-15 | 2003-05-17 | 2003-11-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-15 | 2007-05-17 | 2007-11-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-15 | 2011-05-17 | 2011-11-16 | $7700.00 | Window Closed / Lapsed |