Deghosting method and apparatus for construction of image mosaics

• US 5,986,668 A
• Filed: 08/01/1997
• Issued: 11/16/1999
• 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): Nguyen, Phu K.
• Application Number:
  US08/905,103
• Time in Patent Office: 837 Days
• Field of Search: 345/433, 345/435, 345/437, 345/438, 345/474, 345/475, 345/113, 345/114
• US Class Current: 345/634
• CPC Class Codes: G06T 3/4038 Image mosaicing, e.g. composing plane images from plane sub-images
• CPC Class Codes: G06T 7/33 using feature-based methods

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.

Claims

1. 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.

2. The method of claim 1 wherein the determining step is preceded by determining which of said images of said set overlies said one image.

3. 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.

4. The method of claim 3 further comprising:

initially resampling said images in accordance with said alignment transformations.

5. The method of claim 3 wherein the step of determining alignment transformations comprises performing an incremental alignment process.

6. The method of claim 5 wherein said incremental alignment process comprises a patch-based alignment process.

7. The method of claim 6 wherein said a patch-based alignment process comprises computing an incremental deformation of said one image.

8. The method of claim 7 wherein said incremental deformation comprises a planar perspective transform.

9. The method of claim 7 wherein said incremental deformation comprises a 3-dimensional rotational transform.

10. 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.

11. The method of claim 10 wherein said mapping comprises a reverse mapping of pixels in an unwarped version of said one image.

12. 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.

13. 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.

14. The method of claim 13 wherein said dense set of pixel locations comprise all pixel locations in said one image.

15. 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.

16. 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.

17. 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.

18. The method of claim 17 wherein said fraction is 1/(n+1).

19. The method of claim 1 wherein said steps of determining, combining and warping are performed for all of said images simultaneously.

20. 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.

21. 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.

22. The system of claim 21 wherein said normalization factor is proportional to the number n of images comprising said respective pairs.

23. The system of claim 22 wherein said fraction is 1/(n+1).

24. 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.

25. The system of claim 20 wherein said relative motions are of a sparse set of pixel locations in said one image.

26. 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.

27. 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.

28. 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.

29. 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.

30. 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.

31. 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.

32. The method of claim 36 wherein said mapping comprises a reverse mapping of pixels in an unwarped version of said one image.

33. 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.

34. 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.

35. The method of claim 34 wherein said fraction is 1/(n+1).

36. The method of claim 29 wherein the determining step is preceded by determining which of said images of said set overlies said one image.

37. 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.

38. The method of claim 37 further comprising:

initially resampling said images in accordance with said alignment transformations.

39. The method of claim 37 wherein the step of determining alignment transformations comprises performing an incremental alignment process.

40. The method of claim 39 wherein said incremental deformation comprises a planar perspective transform.

41. The method of claim 39 wherein said incremental deformation comprises a 3-dimensional rotational transform.

42. 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.

43. 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.

44. 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.

45. 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.

46. The method of claim 45 wherein said dense set of pixel locations comprise substantially all pixel locations in said one image.

47. 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.

48. 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.

49. The method of claim 29 wherein the steps of determining and warping are performed for all of said images simultaneously.

50. 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.

51. 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.

52. 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.

53. 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.

54. The apparatus of claim 53 wherein said processor in further response to said instructions:

initially resamples said images in accordance with said alignment transformations.

55. 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.

56. The apparatus of claim 55 wherein said mapping comprises a reverse mapping of pixels in an unwarped version of said one image.

57. The apparatus of claim 50 wherein said processor combines said motions to produce an estimated motion by computing a normalized average of said motions.

58. 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.

59. The apparatus of claim 58 wherein said fraction compensates for overcorrection in said average.

60. The apparatus of claim 59 wherein said fraction is 1/(n+1).

61. 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.

62. 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.

63. 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.

64. 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.

65. The apparatus of claim 64 wherein said dense set of pixel locations comprise substantially all pixel locations in said one image.