Image mosaic construction system and apparatus with patch-based alignment, global block adjustment and pair-wise motion-based local warping

• US 6,097,854 A
• Filed: 08/01/1997
• Issued: 08/01/2000
• 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): MEHTA, BHAVESH M
• Application Number:
  US08/905,023
• Time in Patent Office: 1,096 Days
• Field of Search: 382/107, 382/154, 382/282, 382/284, 382/294, 382/296, 345/419, 345/425-438, 348/42, 348/263, 348/580, 348/584, 348/598
• US Class Current: 382/284
• CPC Class Codes: G06T 3/4038 Image mosaicing, e.g. composing plane images from plane sub-images
• CPC Class Codes: G06V 10/147 Details of sensors, e.g. sensor lenses fingerprint or palmprint sensors G06V40/13; vascular sensors G06V40/145; eye sensors G06V40/19
• CPC Class Codes: G06V 10/16 using multiple overlapping images; Image stitching

Abstract

The system of the invention aligns a set plural overlapping images useful in constructing a mosaic by performing patch-based alignment of the set of overlapping images to produce a set of warped images, performing block adjustment of the set of warped images to produce a set of block-adjusted images, and then performing pair-wise motion-based local warping of the set of block-adjusted images.

Claims

1. A method for aligning a set of plural overlapping images useful in constructing a mosaic, comprising:

performing patch-based alignment of said set of overlapping images to produce a set of warped images;

performing block adjustment of said set of warped images to produce a set of block-adjusted images; and

performing pair-wise motion-based local warping of said set of block-adjusted images.

2. The method of claim 1 wherein the step of performing patch-based alignment comprises:

for at least first and second images of said set of images, finding an incremental deformation 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;

warping said second image in accordance with said incremental deformation and repeating said finding step;

wherein said finding step comprises;

(A) computing a difference error vector between said first and second images,

(B) dividing said second image into plural patches and for each patch;

(1) first computing a per-patch least squares minimization computation quantity and a set of per-pixel least squares minimization computation quantities for a set of pixels in said patch; and

(2) second computing said incremental deformation from the per-patch and per-pixel least squares minimization computation quantities of plural ones of said patches and from said difference error vector.

3. The method of claim 2 wherein:

said per-patch least squares minimization computation quantity comprises a Jacobian within said patch of a coordinate system of said second image with respect to said incremental deformation; and

said set of per-pixel least squares minimization computation quantities comprises gradients computed at said pixels.

4. The method of claim 3 wherein said second computation step comprises:

(1) combining said gradients with said Jacobian to produce a matrix for said patch,

(2) combining said gradients with said error vector and with said Jacobian to produce a residual for said patch,

(3) summing said matrix over plural patches and summing said residual over plural patches to produce Hessians and residuals, respectively, and solving normal equations with said residuals and Hessians.

5. The method of claim 2 wherein the step of combining said gradients with said Jacobian comprises:

multiplying said gradient by a transpose of said gradient to produce a gradient-transpose product and summing said gradient-transpose product over plural pixels of said patch to produce a gradient-transpose sum, and

computing a product of said Jacobian and said gradient-transpose sum and multiplying said product by a transpose of said Jacobian.

6. The method of claim 2 wherein said warping step comprises resampling said second image with pixel coordinates warped in accordance with said incremental deformation.

7. The method of claim 1 wherein the step of performing block adjustment comprises:

for each one of said images of said set of warped images, 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.

8. The method of claim 7 further comprising performing said determining and computing steps for each of said plural predetermined pixel locations of said one image simultaneously.

9. The method of claim 7 further comprising warping said images in accordance with said incremental deformations and then repeating said determining and computing steps.

10. The method of claim 7 wherein said one image is divided into plural patches and said plural predetermined pixel locations constitute one pixel in each of said plural patches.

11. The method of claim 10 wherein said one pixel in each of said patches comprises a center pixel of said patch.

12. The method of claim 1 wherein the step of performing pair-wise motion-based local warping comprises:

selecting one image from said set of block adjusted images;

determining, at plural predetermined pixel locations of said one image, motions between said one image and other images of said set of block adjusted images;

combining said motions to produce an estimated motion at each of said plural predetermined pixel locations of said one image; and

finally warping said one image in accordance with the estimated motions.

13. The method of claim 12 wherein the determining step is preceded by determining which of said images of said set of block adjusted images overlies said one image.

14. The method of claim 13 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.

15. The method of claim 14 further comprising:

initially resampling said images in accordance with said alignment transformations.

16. The method of claim 12 wherein the step of finally warping comprises:

constructing a mapping of warped pixel locations from said estimated motions; and

resampling said one image at said warped pixel locations.

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

18. The method of claim 16 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.

19. The method of claim 18 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.

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

21. The method of claim 18 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.

22. The method of claim 12 wherein the step of combining said motions to produce an estimated motion comprises computing a normalized average of said motions.

23. The method of claim 22 further comprising downweighting said motions in said average by a fraction proportional to the number n of said motions in said average.

24. The method of claim 23 wherein said fraction is 1/(n+1).

25. 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 patch-based alignment of said set of overlapping images to produce a set of warped images,

performs block adjustment of said set of warped images to produce a set of block-adjusted images; and

performs pair-wise motion-based local warping of said set of block-adjusted images.

26. The apparatus of claim 25 wherein said processor performs said patch-based alignment in that said processor:

for at least first and second images of said set of images, determines an incremental deformation 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

warps said second image in accordance with said incremental deformation;

wherein said processor determines said incremental deformation by;

(A) computing a difference error vector between said first and second images,

(B) dividing said second image into plural patches and for each patch;

(1) computing a per-patch least squares minimization computation quantity and a set of per-pixel least squares minimization computation quantities for a set of pixels in said patch; and

(2) computing said incremental deformation from the per-patch and per-pixel least squares minimization computation quantities of plural ones of said patches and from said difference error vector.

27. The apparatus of claim 26 wherein

said per-patch least squares minimization computation quantity comprises a Jacobian within said patch of a coordinate system of said second image with respect to said incremental deformation;

and

said set of per-pixel least squares minimization computation quantities comprises gradients computed at said pixels.

28. The apparatus of claim 27 wherein said second processor computes said incremental deformation by:

(1) combining said gradients with said Jacobian to produce a matrix for said patch,

(2) combining said gradients with said error vector and with said Jacobian to produce a residual for said patch,

(3) summing said matrix over plural patches and summing said residual over plural patches to produce Hessians and residuals, respectively, and solving normal equations with said residuals and Hessians.

29. The apparatus of claim 28 wherein said processor combines said gradients with said Jacobian by:

multiplying said gradient by a transpose of said gradient to produce a gradient-transpose product and summing said gradient-transpose product over plural pixels of said patch to produce a gradient-transpose sum, and

computing a product of said Jacobian and said gradient-transpose sum and multiplying said product by a transpose of said Jacobian.

30. The apparatus of claim 29 wherein said processor combines said gradients with said error vector and with said Jacobian by:

multiplying said error vector by said gradient for pixels inside said patch, summing the resulting product over the pixels inside said patch and multiplying the resulting sum by the Jacobian for said patch, whereby to produce a residual error for said patch.

31. The apparatus of claim 28 wherein the step of solving normal equations produces an incremental rotation vector, and wherein said processor computes said incremental deformation from said incremental rotation vector, said incremental deformation corresponding to an incremental rotation.

32. The apparatus of claim 25 wherein said processor performs said block adjustment in that said processor:

for each one of said images of said set of warped images, 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 warped images which simultaneously minimize differences between the ray directions of plural pairs of said warped images which include said one image.

33. The apparatus of claim 32 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.

34. The apparatus of claim 33 wherein said processor further warps said images in accordance with said incremental deformations.

35. The apparatus of claim 34 wherein said one image is divided into plural patches and said plural predetermined pixel locations constitute one pixel in each of said plural patches.

36. The apparatus of claim 35 wherein said one pixel in each of said patches comprises a center pixel of said patch.

37. The apparatus of claim 36 wherein said processor computes said deformations as incremental 3-dimensional rotations relative to said coordinate system.

38. The apparatus of claim 37 wherein processor computes said deformations as planar perspective transformations.

39. The apparatus of claim 25 wherein said processor performs said pair-wise motion-based local warping in that said processor:

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.

40. The apparatus of claim 39 wherein said processor warps said one image by combining said motions to produce an estimated motion of said one image.

41. The apparatus of claim 40 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.

42. The apparatus of claim 41 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.

43. The apparatus of claim 42 wherein said processor in further response to said instructions:

initially resamples said images in accordance with said alignment transformations.

44. The apparatus of claim 43 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.

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

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

47. The apparatus of claim 46 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.

48. The apparatus of claim 47 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.

49. The apparatus of claim 48 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.

50. The apparatus of claim 49 wherein said processor warps said one image in that said processoor:

constructs a mapping of warped pixel locations from said estimated motions; and

resamples said one image at said warped pixel locations.

51. The apparatus of claim 50 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.

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

53. The apparatus of claim 52 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.

54. The apparatus of claim 53 wherein said fraction compensates for overcorrection in said average.

55. The apparatus of claim 54 wherein said fraction is 1/(n+1).

56. A method for aligning a set of at least partially overlapping plural images useful in constructing a mosaic, comprising:

performing incremental 3-dimensional rotational alignment of said set of overlapping images to produce a set of warped images; and

performing block adjustment of said set of warped images to produce a set of block-adjusted images.

57. The method of claim 56 further comprising:

performing pair-wise motion-based local warping of said set of block-adjusted images.

58. The method of claim 56 wherein the step of performing incremental 3-dimensional rotational alignment comprises:

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; and

rotating said second image in accordance with said incremental rotation whereby to produce a warped image.

59. The method of claim 58 further comprising:

repeating said finding and rotating steps to produce successive incremental rotations of said second image; and

producing a final rotation representing a combination of successive incremental rotations of said second image.

60. The method of claim 58 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.

61. The method of claim 58 wherein said rotating step comprises resampling said second image with pixel coordinates warped in accordance with said incremental rotation.

62. The method of claim 60 wherein the step of solving said normal equations produces an incremental rotational vector.

63. The method of claim 62 wherein the step of finding further comprises computing said incremental rotation from said incremental rotational vector.

64. The method of claim 58 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.

65. The method of claim 57 wherein the step of performing block adjustment comprises:

for each one of said images of said set of warped images, 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.

66. The method of claim 65 further comprising performing steps (a) and (b) of claim 65 for each of said plural predetermined pixel locations of said one image simultaneously.

67. The method of claim 65 further comprising warping said images in accordance with said incremental deformations and then repeating said determining and computing steps.

68. The method of claim 65 wherein said one image is divided into plural patches and said plural predetermined pixel locations constitute one pixel in each of said plural patches.

69. The method of claim 68 wherein said one pixel in each of said patches comprises a center pixel of said patch.

70. The method of claim 65 further comprising performing pair-wise motion-based local warping of said set of block-adjusted images, wherein the step of performing pair-wise motion-based local warping comprises:

selecting one image from said set of block adjusted images;

determining, at plural predetermined pixel locations of said one image, motions between said one image and other images of said set of block adjusted images;

combining said motions to produce an estimated motion at each of said plural predetermined pixel locations of said one image; and

finally warping said one image in accordance with the estimated motions.

71. The method of claim 70 wherein the determining step of claim 70 is preceded by determining which of said images of said set of block adjusted images overlies said one image.

72. The method of claim 71 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.

73. The method of claim 72 further comprising:

initially resampling said images in accordance with said alignment transformations.

74. The method of claim 70 wherein the step of finally warping comprises:

constructing a mapping of warped pixel locations from said estimated motions; and

resampling said one image at said warped pixel locations.

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

76. The method of claim 74 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.

77. The method of claim 76 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.

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

79. The method of claim 76 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.

80. The method of claim 70 wherein the step of combining said motions to produce an estimated motion comprises computing a normalized average of said motions.

81. The method of claim 80 further comprising downweighting said motions in said average by a fraction proportional to the number n of said motions in said average.

82. The method of claim 81 wherein said fraction is 1/(n+1).

83. The method of claim 56 wherein each of said block-adjusted images is associated with an image transform which maps between pixel locations in said image and said three-dimensional coordinate system, said method further comprising constructing, from said set of block-adjusted images and from the image transforms associated with said set of block-adjusted images, a texture map divisible into plural faces.

84. The method of claim 65 wherein each of said block-adjusted images is associated with an image transform which maps between pixel locations in said image and said three-dimensional coordinate system, said method further comprising constructing, from said set of block-adjusted images, a texture map divisible into plural faces, said constructing step comprising:

for each one of said plural faces, computing a texture mapping transform which maps between pixel locations in said texture map and a three-dimensional coordinate system;

for each image of said set of block-adjusted images, combining said texture mapping transform and said image transform to produce a texture map-to-image space transform mapping between pixel locations in said image and pixel locations in said texture map;

for each image of said set of block-adjusted images and for each one of the pixel locations in said one face of said texture map, computing from said texture map-to-image space transform a pixel value of a pixel location in said image corresponding to said one pixel location in said one face of said texture map, to produce a set of image pixel values from said set of overlapping images for said one pixel location in said texture space; and

blending said set of image pixel values to produce a composite pixel value for said one pixel location in said one face of said texture map.

85. The method of claim 84 further comprising:

obtaining a user-defined mapping between plural object faces in said three-dimensional coordinate system and said plural faces of said texture map;

defining space vectors locating said plural object faces in said three-dimensional coordinate system and texture vectors locating said plural faces in said texture map; and

wherein the step of computing said texture map transform comprises;

concatenating the texture vectors of said one face of said texture map to form a first matrix,

concatenating the space vectors of a corresponding face of said three-dimensional space to form a second matrix, and

combining said first matrix and said second matrix.

86. The method of claim 85 wherein said faces in said texture map and said object faces have plural vertices, and wherein said texture vectors locate the vertices of said faces in said texture map and said space vectors locate the vertices of said object faces.

87. The method of claim 86 wherein said faces of said texture map and said object faces have the same number of vertices n, wherein n is an integer, and wherein:

the step of defining space vectors comprises defining n space vectors each locating a corresponding one of said n vertices of said object faces; and

the step of defining texture vectors comprises defining n texture vectors each locating a corresponding one of said n vertices of said faces of said texture map.

88. A method for aligning a set of at least partially overlapping plural images useful in constructing a mosaic, comprising:

performing incremental 3-dimensional rotational alignment of said set of overlapping images to produce a set of warped images; and

performing pair-wise motion-based local warping of said set of warped images to produce a set of de-ghosted images.

89. The method of claim 88 wherein the step of performing incremental 3-dimensional rotational alignment comprises:

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; and

rotating said second image in accordance with said incremental rotation whereby to produce a warped image.

90. The method of claim 89 further comprising:

repeating said finding and rotating steps to produce successive incremental rotations of said second image; and

producing a final rotation representing a combination of successive incremental rotations of said second image.

91. The method of claim 89 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.

92. The method of claim 89 wherein said rotating step comprises resampling said second image with pixel coordinates warped in accordance with said incremental rotation.

93. The method of claim 88 wherein each of said set of de-ghosted images is associated with an image transform which maps between pixel locations in said image and said three-dimensional coordinate system, said method further comprising constructing, from said set of de-ghosted images and from the image transforms associated with said set of de-ghosted images, a texture map divisible into plural faces.

94. The method of claim 89 wherein each of said set of de-ghosted images is associated with an image transform which maps between pixel locations in said image and said three-dimensional coordinate system, said method further comprising constructing, from said set of de-ghosted images, a texture map divisible into plural faces, said constructing step comprising:

for each one of said plural faces, computing a texture mapping transform which maps between pixel locations in said texture map and a three-dimensional coordinate system;

for each image of said set of de-ghosted images, combining said texture mapping transform and said image transform to produce a texture map-to-image space transform mapping between pixel locations in said image and pixel locations in said texture map;

for each image of said set of de-ghosted images and for each one of the pixel locations in said one face of said texture map, computing from said texture map-to-image space transform a pixel value of a pixel location in said image corresponding to said one pixel location in said one face of said texture map, to produce a set of image pixel values from said set of overlapping images for said one pixel location in said texture space; and

blending said set of image pixel values to produce a composite pixel value for said one pixel location in said one face of said texture map.

95. The method of claim 94 further comprising:

obtaining a user-defined mapping between plural object faces in said three-dimensional coordinate system and said plural faces of said texture map;

defining space vectors locating said plural object faces in said three-dimensional coordinate system and texture vectors locating said plural faces in said texture map; and

wherein the step of computing said texture map transform comprises;

concatenating the texture vectors of said one face of said texture map to form a first matrix,

concatenating the space vectors of a corresponding face of said three-dimensional space to form a second matrix, and

combining said first matrix and said second matrix.

96. The method of claim 95 wherein said faces in said texture map and said object faces have plural vertices, and wherein said texture vectors locate the vertices of said faces in said texture map and said space vectors locate the vertices of said object faces.

97. The method of claim 96 wherein said faces of said texture map and said object faces have the same number of vertices n, wherein n is an integer, and wherein:

the step of defining space vectors comprises defining n space vectors each locating a corresponding one of said n vertices of said object faces; and

the step of defining texture vectors comprises defining n texture vectors each locating a corresponding one of said n vertices of said faces of said texture map.

98. 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 incremental 3-dimensional rotational alignment of said set of overlapping images to produce a set of warped images, and

performs block adjustment of said set of warped images to produce a set of block-adjusted images.

99. The apparatus of claim 98 wherein said processor, in further response to said instructions:

performs pair-wise motion-based local warping of said set of block-adjusted images.

100. The apparatus of claim 98 wherein said processor performs incremental 3-dimensional rotational alignment by:

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; and

rotating said second image in accordance with said incremental rotation whereby to produce a warped image.

101. The apparatus of claim 100 wherein said processor performs said block adjustment in that said processor:

for each one of said images of said set of warped images, 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 warped images which simultaneously minimize differences between the ray directions of plural pairs of said warped images which include said one image.

102. The apparatus of claim 101 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.

103. The apparatus of claim 101 wherein said processor, in further response to said instructions, performs pair-wise motion-based local warping in that said processor:

determines pair-wise estimates of motions between said one image and other images of said set of block-adjusted images; and

warps said one image in accordance with said pair-wise estimates of motions, whereby to produce a set of de-ghosted images.

104. The apparatus of claim 98 wherein each of said set of block-adjusted images is associated with an image transform which maps between pixel locations in said image and said three-dimensional coordinate system, and wherein said processor, in further response to said instructions:

constructs, from said set of block-adjusted images and from the image transforms associated with said set of de-ghosted images, a texture map divisible into plural faces.

105. The apparatus of claim 101 wherein each of said set of block-adjusted images is associated with an image transform which maps between pixel locations in said image and said three-dimensional coordinate system, and wherein said processor, in further response to said instructions:

constructs, from said set of block-adjusted images and from the image transforms associated with said set of de-ghosted images, a texture map divisible into plural faces, in that said processor;

for each one of said plural faces, computes a texture mapping transform which maps between pixel locations in said texture map and a three-dimensional coordinate system;

for each image of said set of de-ghosted images, combines said texture mapping transform and said image transform to produce a texture map-to-image space transform mapping between pixel locations in said image and pixel locations in said texture map;

for each image of said set of de-ghosted images and for each one of the pixel locations in said one face of said texture map, computes from said texture map-to-image space transform a pixel value of a pixel location in said image corresponding to said one pixel location in said one face of said texture map, to produce a set of image pixel values from said set of overlapping images for said one pixel location in said texture space; and

blends said set of image pixel values to produce a composite pixel value for said one pixel location in said one face of said texture map.

106. A method for aligning a set of at least partially overlapping plural images useful in constructing a mosaic, comprising:

performing block adjustment of said set of overlapping images to produce a set of block-adjusted images, wherein each of said block-adjusted images is associated with an image transform which maps between pixel locations in said image and a three-dimensional coordinate system; and

constructing, from said set of block-adjusted images and from the image transforms associated with said set of block-adjusted images, a texture map divisible into plural faces.

107. The method of claim 106 further comprising:

performing pair-wise motion-based local warping of said set of block-adjusted images prior to carrying out the constructing step.

108. The method of claim 106 wherein the step of constructing a texture map comprises:

for each one of said plural faces, computing a texture mapping transform which maps between pixel locations in said texture map and a three-dimensional coordinate system;

for each image of said set of block-adjusted images, combining said texture mapping transform and said image transform to produce a texture map-to-image space transform mapping between pixel locations in said image and pixel locations in said texture map;

for each image of said set of block-adjusted images and for each one of the pixel locations in said one face of said texture map, computing from said texture map-to-image space transform a pixel value of a pixel location in said image corresponding to said one pixel location in said one face of said texture map, to produce a set of image pixel values from said set of overlapping images for said one pixel location in said texture space; and

blending said set of image pixel values to produce a composite pixel value for said one pixel location in said one face of said texture map.

109. The method of claim 108 wherein the step of performing block adjustment comprises:

for each one of said images of said set of warped images, 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.

110. The method of claim 109 further comprising performing steps (a) and (b) of claim 109 for each of said plural predetermined pixel locations of said one image simultaneously.

111. The method of claim 108 further comprising:

obtaining a user-defined mapping between plural object faces in said three-dimensional coordinate system and said plural faces of said texture map;

defining space vectors locating said plural object faces in said three-dimensional coordinate system and texture vectors locating said plural faces in said texture map; and

wherein the step of computing said texture map transform comprises;

concatenating the texture vectors of said one face of said texture map to form a first matrix,

concatenating the space vectors of a corresponding face of said three-dimensional space to form a second matrix, and

combining said first matrix and said second matrix.

112. The method of claim 111 wherein said faces in said texture map and said object faces have plural vertices, and wherein said texture vectors locate the vertices of said faces in said texture map and said space vectors locate the vertices of said object faces.

113. The method of claim 112 wherein said faces of said texture map and said object faces have the same number of vertices n, wherein n is an integer, and wherein:

the step of defining space vectors comprises defining n space vectors each locating a corresponding one of said n vertices of said object faces; and

the step of defining texture vectors comprises defining n texture vectors each locating a corresponding one of said n vertices of said faces of said texture map.

114. The method of claim 109 further comprising performing pair-wise motion-based local warping of said set of block-adjusted images, wherein the step of performing pair-wise motion-based local warping comprises:

selecting one image from said set of block adjusted images;

determining, at plural predetermined pixel locations of said one image, motions between said one image and other images of said set of block adjusted images;

combining said motions to produce an estimated motion at each of said plural predetermined pixel locations of said one image; and

finally warping said one image in accordance with the estimated motions.

115. The method of claim 114 wherein the determining step of claim 114 is preceded by determining which of said images of said set of block adjusted images overlies said one image.

116. The method of claim 115 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.

117. A method for aligning a set at least partially overlapping plural images useful in constructing a mosaic, comprising:

performing pair-wise motion-based local warping of said set of images to produce a set of de-ghosted images, wherein each of said de-ghosted images is associated with an image transform which maps between pixel locations in said image and a three-dimensional coordinate system; and

constructing, from said set of de-ghosted images and from the image transforms associated with said set of block-adjusted images, a texture map divisible into plural faces.

118. The method of claim 117 wherein the step of constructing a texture map comprises:

for each one of said plural faces, computing a texture mapping transform which maps between pixel locations in said texture map and a three-dimensional coordinate system;

for each image of said set of de-ghosted images, combining said texture mapping transform and said image transform to produce a texture map-to-image space transform mapping between pixel locations in said image and pixel locations in said texture map;

for each image of said set of de-ghosted images and for each one of the pixel locations in said one face of said texture map, computing from said texture map-to-image space transform a pixel value of a pixel location in said image corresponding to said one pixel location in said one face of said texture map, to produce a set of image pixel values from said set of overlapping images for said one pixel location in said texture space; and

blending said set of image pixel values to produce a composite pixel value for said one pixel location in said one face of said texture map.

119. The method of claim 118 wherein the step of performing pair-wise motion-based local warping comprises:

selecting one image from said set of block adjusted images;

determining, at plural predetermined pixel locations of said one image, motions between said one image and other images of said set of block adjusted images;

combining said motions to produce an estimated motion at each of said plural predetermined pixel locations of said one image; and

finally warping said one image in accordance with the estimated motions.

120. The method of claim 118 further comprising:

obtaining a user-defined mapping between plural object faces in said three-dimensional coordinate system and said plural faces of said texture map;

defining space vectors locating said plural object faces in said three-dimensional coordinate system and texture vectors locating said plural faces in said texture map; and

wherein the step of computing said texture map transform comprises;

concatenating the texture vectors of said one face of said texture map to form a first matrix,

concatenating the space vectors of a corresponding face of said three-dimensional space to form a second matrix, and

combining said first matrix and said second matrix.

121. The method of claim 120 wherein said faces in said texture map and said object faces have plural vertices, and wherein said texture vectors locate the vertices of said faces in said texture map and said space vectors locate the vertices of said object faces.

122. The method of claim 121 wherein said faces of said texture map and said object faces have the same number of vertices n, wherein n is an integer, and wherein:

the step of defining space vectors comprises defining n space vectors each locating a corresponding one of said n vertices of said object faces; and

the step of defining texture vectors comprises defining n texture vectors each locating a corresponding one of said n vertices of said faces of said texture map.

123. 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 block adjustment of said set of overlapping images to produce a set of block-adjusted images, wherein each of said block-adjusted images is associated with an image transform which maps between pixel locations in said image and a three-dimensional coordinate system, and

constructs, from said set of block-adjusted images and from the image transforms associated with said set of block-adjusted images, a texture map divisible into plural faces.

124. The apparatus of claim 123 wherein said processor, in further response to said instructions:

performs pair-wise motion-based local warping of said set of block-adjusted images prior to carrying out the constructing step.

125. The apparatus of claim 123 wherein said processor constructs a texture map in that said processor:

for each one of said plural faces, computes a texture mapping transform which maps between pixel locations in said texture map and a three-dimensional coordinate system;

for each image of said set of block-adjusted images, combines said texture mapping transform and said image transform to produce a texture map-to-image space transform mapping between pixel locations in said image and pixel locations in said texture map;

for each image of said set of block-adjusted images and for each one of the pixel locations in said one face of said texture map, computes from said texture map-to-image space transform a pixel value of a pixel location in said image corresponding to said one pixel location in said one face of said texture map, to produce a set of image pixel values from said set of overlapping images for said one pixel location in said texture space; and

blends said set of image pixel values to produce a composite pixel value for said one pixel location in said one face of said texture map.

126. The apparatus of claim 125 wherein said processor performs said block adjustment in that said processor:

for each one of said images of said set of warped images, 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.

127. The apparatus of claim 125 wherein said processor constructs said texture map in that said processor further:

obtains a user-defined mapping between plural object faces in said three-dimensional coordinate system and said plural faces of said texture map;

defines space vectors locating said plural object faces in said three-dimensional coordinate system and texture vectors locating said plural faces in said texture map; and

wherein said processor computes said texture map by;

concatenating the texture vectors of said one face of said texture map to form a first matrix,

concatenating the space vectors of a corresponding face of said three-dimensional space to form a second matrix, and

combining said first matrix and said second matrix.

128. The apparatus of claim 127 wherein said faces in said texture map and said object faces have plural vertices, and wherein said texture vectors locate the vertices of said faces in said texture map and said space vectors locate the vertices of said object faces.

129. The apparatus of claim 128 wherein said faces of said texture map and said object faces have the same number of vertices n, wherein n is an integer, and wherein:

said processor defines said space vectors by defining n space vectors each locating a corresponding one of said n vertices of said object faces; and

said processor defines said texture vectors by defining n texture vectors each locating a corresponding one of said n vertices of said faces of said texture map.

130. The apparatus of claim 129 wherein said processor, in further response to said instructions:

performs pair-wise motion-based local warping of said set of block-adjusted images, in that said processor;

selects one image from said set of block adjusted images;

determines, at plural predetermined pixel locations of said one image, motions between said one image and other images of said set of block adjusted images;

combines said motions to produce an estimated motion at each of said plural predetermined pixel locations of said one image; and

finally warps said one image in accordance with the estimated motions.

131. 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 pair-wise motion-based local warping of said set of images to produce a set of de-ghosted images, wherein each of said de-ghosted images is associated with an image transform which maps between pixel locations in said image and a three-dimensional coordinate system; and

constructs, from said set of de-ghosted images and from the image transforms associated with said set of de-ghosted images, a texture map divisible into plural faces.

132. The apparatus of claim 131 wherein said processor constructs said texture map in that said processor:

for each one of said plural faces, computes a texture mapping transform which maps between pixel locations in said texture map and a three-dimensional coordinate system;

for each image of said set of de-ghosted images, combines said texture mapping transform and said image transform to produce a texture map-to-image space transform mapping between pixel locations in said image and pixel locations in said texture map;

for each image of said set of de-ghosted images and for each one of the pixel locations in said one face of said texture map, computes from said texture map-to-image space transform a pixel value of a pixel location in said image corresponding to said one pixel location in said one face of said texture map, to produce a set of image pixel values from said set of overlapping images for said one pixel location in said texture space; and

blends said set of image pixel values to produce a composite pixel value for said one pixel location in said one face of said texture map.

133. The apparatus of claim 132 wherein said processor performs said pair-wise motion-based local warping in that said processor:

selects one image from said set of block adjusted images;

determines, at plural predetermined pixel locations of said one image, motions between said one image and other images of said set of block adjusted images;

combines said motions to produce an estimated motion at each of said plural predetermined pixel locations of said one image; and

finally warps said one image in accordance with the estimated motions.

134. The apparatus of claim 132 wherein said processor in further response to said instructions:

obtains a user-defined mapping between plural object faces in said three-dimensional coordinate system and said plural faces of said texture map;

defines space vectors locating said plural object faces in said three-dimensional coordinate system and texture vectors locating said plural faces in said texture map; and

wherein said processor computes said texture map transform by;

concatenating the texture vectors of said one face of said texture map to form a first matrix,

concatenating the space vectors of a corresponding face of said three-dimensional space to form a second matrix, and

combining said first matrix and said second matrix.

135. The apparatus of claim 134 wherein said faces in said texture map and said object faces have plural vertices, and wherein said texture vectors locate the vertices of said faces in said texture map and said space vectors locate the vertices of said object faces.

136. The apparatus of claim 135 wherein said faces of said texture map and said object faces have the same number of vertices n, wherein n is an integer, and wherein:

said processor defines said space vectors by defining n space vectors each locating a corresponding one of said n vertices of said object faces; and

said processor defines said texture vectors by defining n texture vectors each locating a corresponding one of said n vertices of said faces of said texture map.

137. A method for aligning a set of at least partially overlapping plural images useful in constructing a mosaic, comprising:

performing incremental 3-dimensional rotational alignment of said set of overlapping images to produce a set of warped images, wherein each of said warped images is associated with an image transform which maps between pixel locations in said image and said three-dimensional coordinate system; and

constructing, from said set of warped images and from the image transforms associated with said set of warped images, a texture map divisible into plural faces.

138. The method of claim 137 wherein said constructing step comprises:

for each one of said plural faces, computing a texture mapping transform which maps between pixel locations in said texture map and a three-dimensional coordinate system;

for each image of said set of block-adjusted images, combining said texture mapping transform and said image transform to produce a texture map-to-image space transform mapping between pixel locations in said image and pixel locations in said texture map;

for each image of said set of block-adjusted images and for each one of the pixel locations in said one face of said texture map, computing from said texture map-to-image space transform a pixel value of a pixel location in said image corresponding to said one pixel location in said one face of said texture map, to produce a set of image pixel values from said set of overlapping images for said one pixel location in said texture space; and

blending said set of image pixel values to produce a composite pixel value for said one pixel location in said one face of said texture map.

139. The method of claim 138 further comprising:

obtaining a user-defined mapping between plural object faces in said three-dimensional coordinate system and said plural faces of said texture map;

defining space vectors locating said plural object faces in said three-dimensional coordinate system and texture vectors locating said plural faces in said texture map; and

wherein the step of computing said texture map transform comprises;

concatenating the texture vectors of said one face of said texture map to form a first matrix,

concatenating the space vectors of a corresponding face of said three-dimensional space to form a second matrix, and

combining said first matrix and said second matrix.

140. The method of claim 139 wherein said faces in said texture map and said object faces have plural vertices, an d wherein said texture vectors locate the vertices of said faces in said texture map and said space vectors locate the vertices of said object faces.

141. The method of claim 140 wherein said faces of said texture map and said object faces have th e same number of vertices n, wherein n is an integer, and wherein:

the step of defining space vectors comprises defining n space vectors each locating a corresponding one of said n vertices of said object faces; and

the step of defining texture vectors comprises defining n texture vectors each locating a corresponding one of said n vertices of said faces of said texture map.

142. The method of claim 138 wherein the step of performing incremental 3-dimensional rotational alignment comprises:

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; and

rotating said second image in accordance with said incremental rotation whereby to produce a warped image.

143. The method of claim 142 further comprising:

repeating said finding and rotating steps to produce successive incremental rotations of said second image; and

producing a final rotation representing a combination of successive incremental rotations of said second image.

144. The method of claim 142 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.

145. The method of claim 142 wherein said rotating step comprises resampling said second image with pixel coordinates warped in accordance with said incremental rotation.

146. The method of claim 144 wherein the step of solving said normal equations produces an incremental rotational vector.

147. The method of claim 146 wherein the step of finding further comprises computing said incremental rotation from said incremental rotational vector.

148. The method of claim 138 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.

149. 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 incremental 3-dimensional rotational alignment of said set of overlapping images to produce a set of warped images, wherein each of said warped images is associated with an image transform which maps between pixel locations in said image and a three-dimensional coordinate system, and

constructs, from said set of warped images and from the image transforms associated with said set of warped images, a texture map divisible into plural faces.

150. The apparatus of claim 149 wherein said processor constructs a texture map in that said processor:

for each one of said plural faces, computes a texture mapping transform which maps between pixel locations in said texture map and a three-dimensional coordinate system;

for each image of said set of block-adjusted images, combines said texture mapping transform and said image transform to produce a texture map-to-image space transform mapping between pixel locations in said image and pixel locations in said texture map;

for each image of said set of block-adjusted images and for each one of the pixel locations in said one face of said texture map, computes from said texture map-to-image space transform a pixel value of a pixel location in said image corresponding to said one pixel location in said one face of said texture map, to produce a set of image pixel values from said set of overlapping images for said one pixel location in said texture space; and

blends said set of image pixel values to produce a composite pixel value for said one pixel location in said one face of said texture map.

151. The apparatus of claim 150 wherein said processor performs incremental 3-dimensional rotational alignment by:

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; and

rotating said second image in accordance with said incremental rotation whereby to produce a warped image.

152. The apparatus of claim 151 wherein said processor constructs said texture map in that said processor further:

obtains a user-defined mapping between plural object faces in said three-dimensional coordinate system and said plural faces of said texture map;

defines space vectors locating said plural object faces in said three-dimensional coordinate system and texture vectors locating said plural faces in said texture map; and

wherein said processor computes said texture map by;

concatenating the texture vectors of said one face of said texture map to form a first matrix,

concatenating the space vectors of a corresponding face of said three-dimensional space to form a second matrix, and

combining said first matrix and said second matrix.

153. The apparatus of claim 152 wherein said faces in said texture map and said object faces have plural vertices, and wherein said texture vectors locate the vertices of said faces in said texture map and said space vectors locate the vertices of said object faces.

154. The apparatus of claim 153 wherein said faces of said texture map and said object faces have the same number of vertices n, wherein n is an integer, and wherein:

said processor defines said space vectors by defining n space vectors each locating a corresponding one of said n vertices of said object faces; and

said processor defines said texture vectors by defining n texture vectors each locating a corresponding one of said n vertices of said faces of said texture map.

155. The apparatus of claim 152 wherein said processor, in further response to the instructions stored in the memory:

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

156. The apparatus of claim 155 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.

157. The apparatus of claim 152 said processor rotates said second image in that said processor resamples said second image with pixel coordinates warped in accordance with said incremental rotation.

158. The apparatus of claim 156 wherein said processor, in solving said normal equations, produces an incremental rotational vector.

159. The apparatus of claim 158 wherein said processor computes said incremental rotation in that said processor computes said incremental rotation from said incremental rotational vector.

160. The apparatus of claim 152 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.