3-dimensional image rotation method and apparatus for producing image mosaics

• US 6,157,747 A
• Filed: 08/01/1997
• Issued: 12/05/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/904,922
• Time in Patent Office: 1,222 Days
• Field of Search: 382/154, 382/284, 382/294, 382/296, 382/282, 345/419, 345/425-438, 348/42, 348/263, 348/580, 348/36, 348/37
• US Class Current: 382/284
• CPC Class Codes: G06T 3/153 using elastic snapping
• 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
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image

Abstract

The invention aligns a set of plural images to construct a mosaic image. At least different pairs of the images overlap partially (or fully), and typically are images captured by a camera looking at the same scene but oriented at different angles from approximately the same location or similar locations. In order to align one of the images with another one of the images, the following steps are carried out: (a) determining a difference error between the one image and the other image; (b) computing an incremental rotation of the one image relative to a 3-dimensional coordinate system through an incremental angle which tends to reduce the difference error; and (c) rotating the one image in accordance with the incremental rotation to produce an incrementally warped version of the one image. As long as the difference error remains significant, the method continues by re-performing the foregoing determining, computing and rotating steps but this time with the incrementally warped version of the one image.

Claims

1. A 3-dimensional rotational 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 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;

rotating said second image in accordance with said incremental rotation; and

repeating said finding and rotating steps.

2. The method of claim 1 wherein the step of repeating said finding and rotating steps produces successive incremental rotations of said second image, and wherein the method further comprises producing a final rotation representing a combination of successive incremental rotations of said second image.

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

4. The method of claim 3, 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 rotation matrix relating the respective image'"'"'s pixel coordinate system to said 3-dimensional coordinate system, wherein said rotating step comprises multiplying the respective rotation matrix of said second image by said incremental rotation.

5. The method of claim 4 wherein said set of finally warped images comprises, for each of said images, said planar array of image pixels and the respective rotation matrix.

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

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

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

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

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

11. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 1.

12. 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 rotation of said one image relative to a 3-dimensional coordinate system tending to reduce said difference error;

rotating said one image in accordance with said incremental rotation to produce an incrementally warped version of said one image; and

repeating said determining, computing and rotating steps with said incrementally warped version.

13. The method of claim 12 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 rotation representing a combination of successive incremental rotations of said one image.

14. The method of claim 13 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 one image by multiplying it by said incremental rotation computed by said computing step.

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

16. The method of claim 15, 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 rotation matrix relates the respective image'"'"'s 2-dimensional pixel coordinate system to said 3-dimensional coordinate system.

17. The method of claim 16 wherein said set of finally warped images comprises, for each of said images, said planar array of image pixels and the respective rotation matrix.

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

19. The method of claim 18 wherein said one image is defined as individual pixels relative to a pixel coordinate system and said incremental rotation defines a warped version of said pixel coordinate system, and wherein the step of computing an incremental rotation comprises:

determining for each pixel coordinate of said one image;

(a) a gradient,

(b) a Jacobian of said warped version of said pixel coordinate system of said one image relative to said incremental rotation,

(c) a product of said gradient and Jacobian.

20. The method of claim 19 wherein the step of computing computing an incremental rotation further comprises:

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 pixels of said one image to produce residuals and Hessians, and solving normal equations with said residuals and Hessians.

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

22. The method of claim 21 wherein the step of computing an incremental rotation comprises computing said incremental rotation from said incremental rotational vector.

23. The method of claim 12 wherein said one image is defined by individual pixels in a pixel coordinate system and wherein said rotating step comprises:

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

24. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 12.

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 successive iterations in that for each iteration the processor;

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

rotates said second image in accordance with said incremental rotation.

26. The apparatus of claim 25 wherein said processor performs successive iterations in that the processor:

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

27. The apparatus of claim 25 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.

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

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

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

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

32. 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 successive iterations in that the processor;

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

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

rotates said one image in accordance with said incremental rotation to produce an incrementally warped version of said one image.

33. The apparatus of claim 32 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 processor, in further response to the instructions stored in said memory:

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

34. The apparatus of claim 32 wherein said processor determines said error in that said processor computes an error vector between said one image and said other image at each pixel coordinate of said one image.

35. The apparatus claim 34 wherein said one image is defined as individual pixels relative to a pixel coordinate system and said incremental rotation defines a warped version of said pixel coordinate system, and wherein said processor computes said incremental rotation in that said processor:

determines for each pixel coordinate of said one image;

(a) a gradient,

(b) a Jacobian of said warped version of said pixel coordinate system of said one image relative to said incremental rotation,

(c) a product of said gradient and Jacobian.

36. The apparatus of claim 35 wherein said processor computes said incremental rotation in that said processor further:

multiplies 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 combines said transpose with said gradient and Jacobian to produce a matrix;

sums said residual error and summing said matrix over pixels of said one image to produce residuals and Hessians, and solves normal equations with said residuals and Hessians.

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

38. The apparatus of claim 37 wherein said processor determines said incremental rotation in that said processor computes said incremental rotation from said incremental rotational vector.

39. The apparatus of claim 38, 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 rotation matrix relates the respective image'"'"'s 2-dimensional pixel coordinate system to said 3-dimensional coordinate system.

40. The apparatus of claim 39 wherein said set of finally warped images comprises, for each of said images, said planar array of image pixels and the respective rotation matrix.

41. The apparatus of claim 32 wherein said one image is defined by individual pixels in a pixel coordinate system and wherein said processor rotates 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 rotation.