Patch-based alignment method and apparatus for construction of image mosaics

• US 6,018,349 A
• Filed: 08/01/1997
• Issued: 01/25/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: Szeliski, Richard, Shum, Heung-Yeung
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US08/905,100
• Time in Patent Office: 907 Days
• Field of Search: 345/418, 345/419, 345/425, 345/427, 345/429, 345/430, 345/117, 345/118
• US Class Current: 345/629
• CPC Class Codes: G06T 3/14 Transformations for image registration, e.g. adjusting or mapping for alignment of images
• 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 a patched based alignment method and apparatus which aligns a set of overlapping images to construct a mosaic image. The images are aligned by first finding an incremental deformation of one image relative to a 3-dimensional coordinate system tending to reduce registration error between overlapping portions of the pair of images, and then warping the one image in accordance with the incremental deformation. The incremental defornation is found by computing a difference error vector between the pair of images. First, the one image is divided into plural patches. Within each patch, gradients are computed at pixels within the patch and a single Jacobian is computed for the entire patch. The Jacobian is the Jacoian of a coordinate system of the one image with respect to the incremental deformation. The gradients are combined with the Jacobian to produce a matrix for the patch. The gradients are separately combined with the error vector and with the Jacobian to produce a residual for the patch. The matrix is summed over plural patches and the residual is also summed over plural patches to produce Hessians and residuals, respectively. Normal equations are defined with the residuals and Hessians and are solved to provide the desired incremental deformation.

Claims

1. A method for aligning a set of at least partially overlapping plural images to construct a mosaic image, comprising the following steps:

for at least first and second images of said set of images, finding an incremental 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) computing gradients at pixels within the patch and computing a single Jacobian within said patch of a coordinate system of said second image with respect to said incremental deformation,

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

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

(C) 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.

2. The method of claim 1 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.

3. The method of claim 2 wherein the step of combining said gradients with said error vector and with said Jacobian comprises:

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.

4. The method of claim 1 wherein said finding step is repeated until said registration error has been reduced to a desired minimum, and wherein said method further comprises:

producing a final warping representing a combination of successive incremental deformations of said second image.

5. The method of claim 4 further comprising the step of performing said finding, deforming and repeating steps for plural images in said set of images to produce final deformations therefor, whereby to produce a set of finally warped images from which a mosaic image may be constructed.

6. The method of claim 5, wherein each of said images comprises a planar array of image pixels in a two-dimensional image pixel coordinate system of that image, said method further comprising:

associating with each of said images a respective deformation matrix relating the respective image'"'"'s pixel coordinate system to said 3-dimensional coordinate system, wherein said deforming step comprises multiplying the respective deformation matrix of said second image by said incremental deformation.

7. The method of claim 6 wherein said set of finally warped images comprises, for each of said images, said planar array of image pixels and the respective deformation matrix.

8. The method of claim 1 wherein said deforming step comprises resampling said second image with pixel coordinates warped in accordance with said incremental deformation.

9. The method of claim 1 wherein said step of solving said normal equations produces a set of deformation matrix elements, and wherein said step of finding comprises inferring said incremental deformation from said deformation matrix elements.

10. The method of claim 1 wherein the step of solving normal equations produces an incremental rotation vector, and wherein the step of finding comprises computing said incremental deformation from said incremental rotation vector, said incremental deformation corresponding to an incremental rotation.

11. The method of claim 1 wherein the images of said set of images are associated with respective deformation matrices, said method further comprising the step of updating the deformation matrix of said second image by multiplying it by said incremental deformation.

12. The method of claim 1 wherein said incremental deformation is defined by a 3-dimensional rotation operation relative to a 3-dimensional coordinate system.

13. The method of claim 1 wherein said incremental deformation is defined by a planar perspective transformation.

14. A computer-readable medium having computer-executabLe instructions stored therein for performing a method for aligning a set of at least partially overlapping plural images to construct a mosaic image, the method comprising the steps of:

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

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

wherein said finding step comprises the steps of;

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

(B) dividing said second image into plural patches, wherein the dividing step comprises the steps, for each of the patches, of;

(1) computing gradients at pixels within the patch and computing a single Jacobian within said patch of a coordinate system of said second image with respect to said incremental deformation;

(2) combining said gradients with said Jacobian to produce a matrix for said patch; and

(3) combining said gradients with said difference error vector and with said Jacobian to produce a residual for said patch; and

(C) 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.

15. A method for aligning a set of plural images to construct a mosaic image, comprising carrying out the following steps for each one of said set of plural images:

determining a difference error between said one image and an other one of said images of said set;

computing an incremental deformation of said one image tending to reduce said difference error;

defoaming said one image in accordance with said incremental deformation to produce an incrementally warped version of said one image;

wherein the step of computing an incremental deformation comprises;

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

(1) computing gradients at pixels within the patch and computing a single Jacobian within said patch of a coordinate system of said second image with respect to said incremental deformation,

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

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

(B) 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.

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

17. The method of claim 16 wherein the step of combining said gradients with said error vector and with said Jacobian comprises:

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.

18. The method of claim 15 further comprising:

re-performing said determining, computing and deforming steps with said incrementally warped version of said one image.

19. The method of claim 18 wherein said re-performing step is repeated until said difference error has been reduced to a desired minimum, said method further comprising:

producing a final deformation representing a combination of successive incremental deformations of said one image.

20. The method of claim 19 wherein the images of said set of images are associated with respective deformation matrices defining their respective orientations relative to a 3-dimensional coordinate system, said method further comprising the step of updating the deformation matrix of said one image by multiplying it by said incremental deformation computed by said computing step.

21. The method of claim 20 further comprising the step of performing said determining, computing, deforming and re-performing steps for plural images in said set of images to produce final deformations of said images, whereby to produce a set of finally warped images from which a mosaic image may be constructed.

22. The method of claim 21 wherein said step of solving said normal equations produces a set of deformation matrix elements, and wherein said step of computing further comprises:

inferring said incremental deformation from said deformation matrix elements.

23. The method of claim 21 wherein the step of solving normal equations produces an incremental rotation vector, and wherein the step of finding comprises computing said incremental deformation from said incremental rotation vector, said incremental deformation corresponding to an incremental rotation.

24. The method of claim 18, wherein each of said images comprises a planar array of image pixels in a two-dimensional image pixel coordinate system of that image, wherein said each respective deformation matrix relates the respective image'"'"'s 2-dimensional pixel coordinate system to said 3-dimensional coordinate system.

25. The method of claim 24 wherein said set of finally warped images comprises, for each of said images, said planar array of image pixels and the respective deformation matrix.

26. The method of claim 15 wherein said determining step comprises:

computing an error vector between said one image and said other image at each pixel coordinate of said one image.

27. The method of claim 15 wherein said one image is defined by individual pixels in a pixel coordinate system and wherein said deforming step comprises:

resampling said one image with a version of said pixel coordinate system of said one image warped in accordance with said incremental deformation.

28. A computer-readable medium having computer-executable instructions stored therein for performing a method for aligning a set of plural images to construct a mosaic image, the method comprising the steps, for each one of said set of plural images, of:

determining a difference error vector between said one image and another one of said images of said set;

computing an incremental deformation of said one image tending to reduce said difference error vector; and

deforming said one image in accordance with said incremental deformation to produce an incrementally warped version of said one image;

wherein the step of computing an incremental deformation comprises the steps of;

(A) dividing said second image into plural patches, wherein the dividing step comprises the steps, for each of the patches, of;

(1) computing gradients at pixels within the patch and computing a single Jacobian within said patch of a coordinate system of said second image with respect to said incremental deformation;

(2) combining said gradients with said Jacobian to produce a matrix for said patch; and

(3) combining said gradients with said difference error vector and with said Jacobian to produce a residual for said patch; and

(B) 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. 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;

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 gradients at pixels within the patch and computing a single Jacobian within said patch of a coordinate system of said second image with respect to said incremental deformation,

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

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

(C) 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.

30. The apparatus of claim 29 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 gradieni-transpose sum and multiplying said product by a transpose of said Jacobian.

31. The apparatus of claim 30 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.

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

determines a further incremental deformation of the warped second image which reduces registration error between the warped second image and the first image;

further warps the second image by said further incremental deformation; and

performs the foregoing steps in repetitive cycles until the registration error has been reduced to a desired minimum, and produces a final deformation representing a combination of successive incremental deformations of said second image.

33. The apparatus of claim 29 said processor warps said second image in that said processor resamples said second image with pixel coordinates warped in accordance with said incremental deformation.

34. The apparatus of claim 29 wherein said processor, in solving said normal equations, produces a set of deformation matrix elements, and wherein said processor determines said incremental deformation in that said processor computes said incremental deformation from said deformation matrix elements.

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

36. The apparatus of claim 29 wherein the images of said set of images are associated with respective deformation 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 deformation matrix of said second image by multiplying it by said incremental deformation.

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

determines a difference error between said one image and an other one of said images of said set;

computes an incremental deformation of said one image relative to a 3-dimensional coordinate system tending to reduce said difference error;

warps said one image in accordance with said incremental deformation to produce an incrementally warped version of said one image;

wherein said processor computes said incremental deformation by;

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

(1) computing gradients at pixels within the patch and computing a single Jacobian within said patch of a coordinate system of said second image with respect to said incremental deformation,

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

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

(B) 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.

38. The apparatus of claim 37 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.

39. The apparatus of claim 38 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.

40. The apparatus of claim 37 wherein the images of said set of images are associated with respective deformation matrices defining their respective orientations relative to a 3-dimensional coordinate system, said processor, in further response to the instructions stored in said memory:

updates the deformation matrix of said one image by multiplying it by said incremental deformation.

41. The apparatus of claim 40, wherein each of said images comprises a planar array of image pixels in a two-dimensional image pixel coordinate system of that image, wherein said each respective deformation matrix relates the respective image'"'"'s 2-dimensional pixel coordinate system to said 3-dimensional coordinate system.

42. The apparatus of claim 37 wherein said one image is defined by individual pixels in a pixel coordinate system and wherein said processor warps said one image in that said processor:

resamples said one image with a version of said pixel coordinate system of said one image warped in accordance with said incremental deformation.

43. The apparatus of claim 42 wherein said set of finally warped images comprises, for each of said images, said planar array of image pixels and the respective deformation matrix.

44. The apparatus of claim 37 wherein said processor, in solving said normal equations, produces a set of deformation matrix elements, and wherein said processor computes said incremental deformation in that said processor:

determines said incremental deformation from said deformation matrix elements.

45. The apparatus of claim 37 wherein the step of solving normal equations produces an incremental rotation vector, and wherein the step of finding comprises computing said incremental deformation from said incremental rotation vector, said incremental deformation corresponding to an incremental rotation.

46. The apparatus of claim 37 wherein said incremental deformation is defined by a planar perspective transformation.

47. The apparatus of claim 37 wherein said incremental deformation is defined by a 3-dimensional rotation relative to a 3-dimensional coordinate system.

48. A method for aligning a set of at least partially overlapping plural images to construct a mosaic image, comprising the following steps:

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

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

50. The method of claim 49 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.

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

52. The method of claim 51 wherein the step of combining said gradients with said error vector and with said Jacobian comprises:

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.

53. The method of claim 50 wherein said step of solving said normal equations produces a set of deformation matrix elements, and wherein said step of finding comprises inferring said incremental deformation from said deformation matrix elements.

54. The method of claim 50 wherein the step of solving normal equations produces an incremental rotation vector, and wherein the step of finding comprises computing said incremental deformation from said incremental rotation vector, said incremental deformation corresponding to an incremental rotation.

55. The method of claim 48 wherein said finding step is repeated until said registration error has been reduced to a desired minimum, and wherein said method further comprises:

producing a final warping representing a combination of successive incremental deformations of said second image.

56. The method of claim 48 wherein said deforming step comprises resampling said second image with pixel coordinates warped in accordance with said incremental deformation.

57. The method of claim 48 wherein the images of said set of images are associated with respective deformation matrices, said method further comprising the step of updating the deformation matrix of said second image by multiplying it by said incremental deformation.

58. The method of claim 57 further comprising the step of performing said finding, deforming and repeating steps for plural images in said set of images to produce final deformations therefor, whereby to produce a set of finally warped images from which a mosaic image may be constructed.

59. The method of claim 58, wherein each of said images comprises a planar array of image pixels in a two-dimensional image pixel coordinate system of that image, said method further comprising:

associating with each of said images a respective deformation matrix relating the respective image'"'"'s pixel coordinate system to said 3-dimensional coordinate system, wherein said deforming step comprises multiplying the respective deformation matrix of said second image by said incremental deformation.

60. The method of claim 59 wherein said set of finally warped images comprises, for each of said images, said planar array of image pixels and the respective deformation matrix.

61. The method of claim 48 wherein said incremental deformation is defined by a 3-dimensional rotation operation relative to a 3-dimensional coordinate system.

62. The method of claim 48 wherein said incremental deformation is defined by a planar perspective transformation.

63. A computer-readable medium having computer-executable instructions stored therein for performing a method for aligning a set of at least partially overlapping plural images to construct a mosaic image, the method comprising the steps of:

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

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

wherein said finding step comprises the steps of;

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

(B) dividing said second image into plural patches, wherein the dividing step comprises the steps, for each of the patches, of;

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

64. A method for aligning a set of plural images to construct a mosaic image, comprising carrying out the following steps for each one of said set of plural images:

determining a difference error between said one image and an other one of said images of said set;

computing an incremental deformation of said one image tending to reduce said difference error;

deforming said one image in accordance with said incremental deformation to produce an incrementally warped version of said one image;

wherein the step of computing an incremental deformation comprises;

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

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

66. The method of claim 65 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 difference error 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.

67. The method of claim 66 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.

68. The method of claim 67 wherein the step of combining said gradients with said error vector and with said Jacobian comprises:

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.

69. The method of claim 64 further comprising:

re-performing said determining, computing and deforming steps with said incrementally warped version of said one image.

70. The method of claim 69 wherein said re-performing step is repeated until said difference error has been reduced to a desired minimum, said method further comprising:

producing a final deformation representing a combination of successive incremental deformations of said one image.

71. The method of claim 70 wherein the images of said set of images are associated with respective deformation matrices defining their respective orientations relative to a 3-dimensional coordinate system, said method further comprising the step of updating the deformation matrix of said one image by multiplying it by said incremental deformation computed by said computing step.

72. The method of claim 71 wherein each of said images comprises a planar array of image pixels in a two-dimensional image pixel coordinate system of that image, wherein each respective deformation matrix relates the respective image'"'"'s two-dimensional pixel coordinate system to said 3-dimensional coordinate system.

73. The method of claim 72 wherein said set of finally warped images comprises, for each of said images, said planar array of image pixels and the respective deformation matrix.

74. The method of claim 69 further comprising the step of performing said determining, computing, deforming and re-performing steps for plural images in said set of images to produce final deformations of said images, whereby to produce a set of finally warped images from which a mosaic image may be constructed.

75. The method of claim 74 wherein said step of solving said normal equations produces a set of deformation matrix elements, and wherein said step of computing further comprises:

inferring said incremental deformation from said deformation matrix elements.

76. The method of claim 74 wherein the step of solving normal equations produces an incremental rotation vector, and wherein the step of finding comprises computing said incremental deformation from said incremental rotation vector, said incremental deformation corresponding to an incremental rotation.

77. The method of claim 64 wherein said determining step comprises:

computing an error vector between said one image and said other image at each pixel coordinate of said one image.

78. The method of claim 64 wherein said one image is defined by individual pixels in a pixel coordinate system and wherein said deforming step comprises:

resampling said one image with a version of said pixel coordinate system of said one image warped in accordance with said incremental deformation.

79. A computer-readable medium having computer-executable instructions stored therein for performing a method for aligning a set of plural images to construct a mosaic image, comprising the steps, for each one of said set of plural images, of:

determining a difference error between said one image and another one of said images of said set;

computing an incremental deformation of said one image tending to reduce said difference error; and

deforming said one image in accordance with said incremental deformation to produce an incrementally warped version of said one image;

wherein the step of computing an incremental deformation comprises the steps of;

(A) dividing said second image into plural patches, wherein the dividing step comprises the steps, for each of the patches, of;

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

80. 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;

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.

81. The apparatus of claim 80 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.

82. The apparatus of claim 81 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.

83. The apparatus of claim 82 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.

84. The apparatus of claim 83 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.

85. The apparatus of claim 82 wherein said processor, in solving said normal equations, produces a set of deformation matrix elements, and wherein said processor determines said incremental deformation in that said processor computes said incremental deformation from said deformation matrix elements.

86. The apparatus of claim 82 wherein the step of solving normal equations produces an incremental rotation vector, and wherein the processor computes said incremental deformation from said incremental rotation vector, said incremental deformation corresponding to an incremental rotation. sum by the Jacobian for said patch, whereby to produce a residual error for said patch.

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

determines a further incremental deformation of the warped second image which reduces registration error between the warped second image and the first image;

further warps the second image by said further incremental deformation; and

performs the foregoing steps in repetitive cycles until the registration error has been reduced to a desired minimum, and produces a final deformation representing a combination of successive incremental deformations of said second image.

88. The apparatus of claim 80 wherein said processor warps said second image in that said processor resamples said second image with pixel coordinates warped in accordance with said incremental deformation.

89. The apparatus of claim 80 wherein the images of said set of images are associated with respective deformation 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 deformation matrix of said second image by multiplying it by said incremental deformation.

90. 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;

determines a difference error between said one image and an other one of said images of said set;

computes an incremental deformation of said one image relative to a 3-dimensional coordinate system tending to reduce said difference error;

warps said one image in accordance with said incremental deformation to produce an incrementally warped version of said one image;

wherein said processor computes said incremental deformation by;

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.

91. The apparatus of claim 90 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.

92. The apparatus of claim 91 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 difference error 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.

93. The apparatus of claim 92 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.

94. The apparatus of claim 93 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.

95. The apparatus of claim 92 wherein said processor, in solving said normal equations, produces a set of deformation matrix elements, and wherein said processor computes said incremental deformation in that said processor:

determines said incremental deformation from said deformation matrix elements.

96. The apparatus of claim 92 wherein the step of solving normal equations produces an incremental rotation vector, and wherein the step of finding comprises computing said incremental deformation from said incremental rotation vector, said incremental deformation corresponding to an incremental rotation.

97. The apparatus of claim 92, wherein each of said images comprises a planar array of image pixels in a 2-dimensional image pixel coordinate system of that image, wherein said each respective deformation matrix relates the respective image'"'"'s 2-dimensional pixel coordinate system to said 3-dimensional coordinate system.

98. The apparatus of claim 97 wherein said set of finally warped images comprises, for each of said images, said planar array of image pixels and the respective deformation matrix.

99. The apparatus of claim 90 wherein the images of said set of images are associated with respective deformation matrices defining their respective orientations relative to a 3-dimensional coordinate system, said processor, in further response to the instructions stored in said memory:

updates the deformation matrix of said one image by multiplying it by said incremental deformation.

100. The apparatus of claim 90 wherein said one image is defined by individual pixels in a pixel coordinate system and wherein said processor warps said one image in that said processor:

resamples said one image with a version of said pixel coordinate system of said one image warped in accordance with said incremental deformation.

101. The apparatus of claim 90 wherein said incremental deformation is defined by a planar perspective transformation.

102. The apparatus of claim 90 wherein said deformation is defined by a 3-dimensional rotation relative to a 3-dimensional coordinate system.