US5986668A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Deghosting 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 deghosting method and apparatus which locally aligns individual images in a set of overlapping images of a mosaic. This is accomplished by determining, at plural predetermined pixel locations of each one of the images, motions between the one image and other images of the set, combining the motions to produce an estimated motion at each of the plural predetermined pixel locations of the one image, and then warping the one image in accordance with the estimated motions. Preferably, it is first which of the images of the set overlies the one image. This determination is made by determining alignment transformations relating the images to a 3-dimensional coordinate system and then inferring mutual overlap between images from the transformations. The images are resampled in accordance with these alignment transformations. The warping of each image is accomplished by constructing a mapping of warped pixel locations from the estimated motions and then resampling the one image at the warped pixel locations. The mapping is preferably a reverse mapping of pixels in an unwarped version of the one image.
Inventors
- 👤 Richard Szeliski
- 👤 Heung-Yeung Shum
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 10:16
CPC Classifications
G; G06; G06T; G06T3/00; G06T3/40; G06T3/4038; G06T7/00; G06T7/30; G06T7/33
Claims Analysis
Total Claims: 69
Claim 1
Independent Claim
74 words
A method for locally aligning individual images in a set of overlapping images of a mosaic, comprising: selecting one of said images; determining, at plural predetermined pixel locations of said one image, motions between said one image and other images of said set; combining said motions to produce an estimated motion at each of said plural predetermined pixel locations of said one image; and warping said one image in accordance with the estimated motions.
Claim 2
Independent Claim
74 words
A method for locally aligning individual images in a set of overlapping images of a mosaic, comprising: selecting one of said images; determining, at plural predetermined pixel locations of said one image, motions between said one image and other images of said set; combining said motions to produce an estimated motion at each of said plural predetermined pixel locations of said one image; and warping said one image in accordance with the estimated motions.
Claim 3
Dependent Claim
24 words
The method of claim 1 wherein the determining step is preceded by determining which of said images of said set overlies said one image.
Claim 4
Dependent Claim
39 words
The method of claim 2 wherein the step of determining which of said images overlies said one image comprises: determining alignment transformations relating said images to a 3-dimensional coordinate system; and inferring mutual overlap between images from said transformations.
Claim 5
Dependent Claim
17 words
The method of claim 3 further comprising: initially resampling said images in accordance with said alignment transformations.
Claim 6
Dependent Claim
18 words
The method of claim 3 wherein the step of determining alignment transformations comprises performing an incremental alignment process.
Claim 7
Dependent Claim
15 words
The method of claim 5 wherein said incremental alignment process comprises a patch-based alignment process.
Claim 8
Dependent Claim
20 words
The method of claim 6 wherein said a patch-based alignment process comprises computing an incremental deformation of said one image.
Claim 9
Dependent Claim
14 words
The method of claim 7 wherein said incremental deformation comprises a planar perspective transform.
Claim 10
Dependent Claim
14 words
The method of claim 7 wherein said incremental deformation comprises a 3-dimensional rotational transform.
Claim 11
Dependent Claim
32 words
The method of claim 1 wherein the step of warping comprises: constructing a mapping of warped pixel locations from said estimated motions; and resampling said one image at said warped pixel locations.
Claim 12
Dependent Claim
22 words
The method of claim 10 wherein said mapping comprises a reverse mapping of pixels in an unwarped version of said one image.
Claim 13
Dependent Claim
58 words
The method of claim 10 wherein said plural predetermined pixels are a sparse set of pixel locations of said one image and wherein the step of constructing a mapping comprises: computing an estimated motion for a dense set of pixel locations in said one image based upon the estimated motions of said sparse set of predetermined pixel locations.
Claim 14
Dependent Claim
34 words
The method of claim 12 further comprising dividing said one image into plural patches, and assigning a center pixel location in each patch to be a corresponding one of said plural predetermined pixel locations.
Claim 15
Dependent Claim
20 words
The method of claim 13 wherein said dense set of pixel locations comprise all pixel locations in said one image.
Claim 16
Dependent Claim
58 words
The method of claim 12 wherein the step of computing an estimated motion for said dense set of pixel locations comprises: computing, for each pixel location of said dense set of pixel locations, an average of estimated motions of neighboring ones of said plural predetermined pixel locations weighted in accordance with their proximity to the one pixel location.
Claim 17
Dependent Claim
25 words
The method of claim 1 wherein the step of combining said motions to produce an estimated motion comprises computing a normalized average of said motions.
Claim 18
Dependent Claim
27 words
The method of claim 16 further comprising downweighting said motions in said average by a fraction proportional to the number n of said motions in said average.
Claim 19
Dependent Claim
10 words
The method of claim 17 wherein said fraction is 1/(n+1).
Claim 20
Dependent Claim
21 words
The method of claim 1 wherein said steps of determining, combining and warping are performed for all of said images simultaneously.
Claim 21
Independent Claim
75 words
A system for locally aligning individual images in a set of overlapping images of a mosaic, comprising: a set of relative motion estimators which estimate relative motions between respective pairs of said images; for each one of said images, an averager which computes an average of a set of said relative motions said one image; and for each one of said averagers, a local warper which warps said one image in accordance with said average.
Claim 22
Independent Claim
75 words
A system for locally aligning individual images in a set of overlapping images of a mosaic, comprising: a set of relative motion estimators which estimate relative motions between respective pairs of said images; for each one of said images, an averager which computes an average of a set of said relative motions said one image; and for each one of said averagers, a local warper which warps said one image in accordance with said average.
Claim 23
Dependent Claim
30 words
The system of claim 20 wherein said averager comprises summer which adds said relative motions to produce a sum; and a divider which divides said sum by a normalization factor.
Claim 24
Dependent Claim
21 words
The system of claim 21 wherein said normalization factor is proportional to the number n of images comprising said respective pairs.
Claim 25
Dependent Claim
10 words
The system of claim 22 wherein said fraction is 1/(n+1).
Claim 26
Dependent Claim
43 words
The system of claim 23 wherein said sparse data interpolator comprises a weighter which weights said relative motions in accordance with the proximities of the corresponding sparse set of pixel locations to the one pixel location of said dense set of pixel locations.
Claim 27
Dependent Claim
21 words
The system of claim 20 wherein said relative motions are of a sparse set of pixel locations in said one image.
Claim 28
Dependent Claim
60 words
The system of claim 25 further comprising: a sparse data interpolator for computing, from said relative motions of said sparse set of pixel locations, a motion estimate for each one of a dense set of pixel locations, and wherein said local warper receives as its input the motion estimates for said dense set of pixel locations and said one image.
Claim 29
Dependent Claim
34 words
The system of claim 26 wherein said one image is divisible into contiguous patches and wherein each pixel location of said sparse set of pixel locations lies in a respective one of said patches.
Claim 30
Dependent Claim
28 words
The system of claim 27 wherein each pixel location of said sparse set of pixel locations is a center pixel location of a respective one of said patches.
Claim 31
Independent Claim
44 words
A method for aligning individual images in a set of overlapping images of a mosaic, comprising: determining pair-wise estimates of motions between said one image and other images of said set; and warping said one image in accordance with said pair-wise estimates of motions.
Claim 32
Independent Claim
44 words
A method for aligning individual images in a set of overlapping images of a mosaic, comprising: determining pair-wise estimates of motions between said one image and other images of said set; and warping said one image in accordance with said pair-wise estimates of motions.
Claim 33
Dependent Claim
34 words
The method of claim 29 wherein the warping step comprises: combining said motions to produce an estimated motion of said one image; and computing a warp of said one image from said estimate motion.
Claim 34
Dependent Claim
38 words
The method of claim 30 wherein the step of computing a warp comprises: constructing a mapping of warped pixel locations from said estimated motion of said one image; and resampling said one image at said warped pixel locations.
Claim 35
Dependent Claim
22 words
The method of claim 36 wherein said mapping comprises a reverse mapping of pixels in an unwarped version of said one image.
Claim 36
Dependent Claim
25 words
The method of claim 30 wherein the step of combining said motions to produce an estimated motion comprises computing a normalized average of said motions.
Claim 37
Dependent Claim
27 words
The method of claim 33 further comprising downweighting said motions in said average by a fraction proportional to the number n of said motions in said average.
Claim 38
Dependent Claim
10 words
The method of claim 34 wherein said fraction is 1/(n+1).
Claim 39
Dependent Claim
24 words
The method of claim 29 wherein the determining step is preceded by determining which of said images of said set overlies said one image.
Claim 40
Dependent Claim
39 words
The method of claim 36 wherein the step of determining which of said images overlies said one image comprises: determining alignment transformations relating said images to a 3-dimensional coordinate system; and inferring mutual overlap between images from said transformations.
Claim 41
Dependent Claim
17 words
The method of claim 37 further comprising: initially resampling said images in accordance with said alignment transformations.
Claim 42
Dependent Claim
18 words
The method of claim 37 wherein the step of determining alignment transformations comprises performing an incremental alignment process.
Claim 43
Dependent Claim
14 words
The method of claim 39 wherein said incremental deformation comprises a planar perspective transform.
Claim 44
Dependent Claim
14 words
The method of claim 39 wherein said incremental deformation comprises a 3-dimensional rotational transform.
Claim 45
Dependent Claim
24 words
The method of claim 39 wherein said incremental alignment process comprise dividing said one image into plural patches and performing a patch-based alignment process.
Claim 46
Dependent Claim
48 words
The method of claim 42 wherein the step of determining motions between said one image and other images of said set determines said motions at plural predetermined pixel locations of said one image, said plural predetermined pixel location being center pixel locations in respective ones of said patches.
Claim 47
Dependent Claim
32 words
The method of claim 43 wherein the step of warping comprises: constructing a mapping of warped pixel locations from said estimated motions; and resampling said one image at said warped pixel locations.
Claim 48
Dependent Claim
41 words
The method of claim 44 wherein the step of constructing a mapping comprises: computing an estimated motion for a dense set of pixel locations in said one image based upon the estimated motions of said sparse set of predetermined pixel locations.
Claim 49
Dependent Claim
21 words
The method of claim 45 wherein said dense set of pixel locations comprise substantially all pixel locations in said one image.
Claim 50
Dependent Claim
58 words
The method of claim 45 wherein the step of computing an estimated motion for said dense set of pixel locations comprises: computing, for each pixel location of said dense set of pixel locations, an average of estimated motions of neighboring ones of said plural predetermined pixel locations weighted in accordance with their proximity to the one pixel location.
Claim 51
Dependent Claim
60 words
The apparatus of claim 45 wherein said processor computes an estimated motion for said dense set of pixel locations in that said processor: computes, for each pixel location of said dense set of pixel locations, an average of estimated motions of neighbors ones of said plural predetermined pixel locations weighted in accordance with their proximity to the one pixel location.
Claim 52
Dependent Claim
20 words
The method of claim 29 wherein the steps of determining and warping are performed for all of said images simultaneously.
Claim 53
Dependent Claim
66 words
Apparatus for use in aligning individual images in a set of overlapping images of a mosaic, comprising: a processor; memory having executable instructions stored therein; and, wherein the processor, in response to the instructions stored in the memory: determines pair-wise estimates of motions between said one image and other images of said set; and warps said one image in accordance with said pair-wise estimates of motions.
Claim 54
Dependent Claim
66 words
Apparatus for use in aligning individual images in a set of overlapping images of a mosaic, comprising: a processor; memory having executable instructions stored therein; and, wherein the processor, in response to the instructions stored in the memory: determines pair-wise estimates of motions between said one image and other images of said set; and warps said one image in accordance with said pair-wise estimates of motions.
Claim 55
Dependent Claim
25 words
The apparatus of claim 50 wherein said processor warps said one image by: combining said motions to produce an estimated motion of said one image.
Claim 56
Dependent Claim
32 words
The apparatus of claim 50 wherein the processor, in further response to said instructions, determines which of said images of said set overlies said one image prior to determining said pair-wise estimates.
Claim 57
Dependent Claim
41 words
The apparatus of claim 52 wherein said processor determines which of said images overlies said one image in that said processor: determines alignment transformations relating said images to a 3-dimensional coordinate system; and infers mutual overlap between images from said transformations.
Claim 58
Dependent Claim
24 words
The apparatus of claim 53 wherein said processor in further response to said instructions: initially resamples said images in accordance with said alignment transformations.
Claim 59
Dependent Claim
37 words
The apparatus of claim 50 wherein said processor warps said one image in that said processor: constructs a mapping of warped pixel locations from said estimated motions; and resamples said one image at said warped pixel locations.
Claim 60
Dependent Claim
22 words
The apparatus of claim 55 wherein said mapping comprises a reverse mapping of pixels in an unwarped version of said one image.
Claim 61
Dependent Claim
24 words
The apparatus of claim 50 wherein said processor combines said motions to produce an estimated motion by computing a normalized average of said motions.
Claim 62
Dependent Claim
34 words
The apparatus of claim 57 wherein said processor in further response to said instructions downweights said motions in said average by a fraction proportional to the number n of said motions in said average.
Claim 63
Dependent Claim
14 words
The apparatus of claim 58 wherein said fraction compensates for overcorrection in said average.
Claim 64
Dependent Claim
10 words
The apparatus of claim 59 wherein said fraction is 1/(n+1).
Claim 65
Dependent Claim
36 words
The apparatus of claim 50 wherein said processor in further response to said instructions selects a next one of said images and, for said next one image, determines said pair-wise motions and warps said one image.
Claim 66
Dependent Claim
32 words
The apparatus of claim 50 said processor determines motions between said one image and other images of said set by determining said motions at plural predetermined pixel locations of said one image.
Claim 67
Dependent Claim
37 words
The apparatus of claim 62 wherein said processor warps said one image in that said processor: constructs a mapping of warped pixel locations from said estimated motions; and resamples said one image at said warped pixel locations.
Claim 68
Dependent Claim
40 words
The apparatus of claim 63 wherein said processor constructs a mapping by computing an estimated motion for a dense set of pixel locations in said one image based upon the estimated motions of said sparse set of predetermined pixel locations.
Claim 69
Dependent Claim
21 words
The apparatus of claim 64 wherein said dense set of pixel locations comprise substantially all pixel locations in said one image.
References Cited (Backward Citations)
US5553221A
Cited
US5708826A
Cited
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 |