Combining digital images based on three-dimensional relationships between source image data sets

• US 6,249,616 B1
• Filed: 05/30/1997
• Issued: 06/19/2001
• Est. Priority Date: 05/30/1997
• Status: Expired due to Term

• Current Assignee: Hanger Solutions, LLC (IP Investments Group LLC)
• Original Assignee: Enroute Incorporated
• Inventors: Hashimoto, Roy T.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): SHERALI, ISHRAT I
• Application Number:
  US08/865,840
• Time in Patent Office: 1,481 Days
• Field of Search: 382/284-286, 382/294, 382/154, 382/276, 382/131-133, 382/115-119, 382/139, 382/421, 382/425-427, 382/435-437, 358/450, 358/540, 358/453, 345/115-120, 345/440, 345/427-435, 348/36-44, 348/47-50, 348/584-601, 378/22, 378/23
• US Class Current: 382/284
• CPC Class Codes: G06T 7/35 using statistical methods

Abstract

A computer-implemented method combines related source images, each represented by a set of digital data, by determining three-dimensional relationships between data sets representing related source images and creating a data set representing an output image by combining the data sets representing the source images in accordance with the determined three-dimensional relationships.

Claims

1. A computer-implemented method for combining two-dimensional source images that have overlapping portions and are taken from a substantially common camera location, each source image represented by a corresponding digital data set of three-dimensional camera parameters that define a position of the camera relative to the source image that is viewed from the camera, the method comprising:

for each pair of overlapping source images to be combined;

determining three-dimensional transformation parameters defining a mapping between a first image space corresponding to one of the source images'"'"' digital data set and a second image space corresponding to the other of the source images'"'"' digital data set, the mapping describing a reorienting of the camera from one of the source images to the other of the source images; and

creating an output data set representing a two-dimensional output image by combining the digital data sets representing the pair of source images in accordance with the determined three-dimensional transformation parameters and by transforming the source images into a common output space by finding a path from a source image space to an output image space based on the determined three-dimensional transformation parameters;

in which finding a path includes choosing a path that is more accurate than other paths.

2. The method of claim 1, wherein the source images overlap by at least around 20%.

3. The method of claim 1, wherein the three-dimensional transformation parameters describe a camera orientation, distances between the camera and the source images, and a distance between the camera and the output image.

4. The method of claim 1 further comprising projecting the created data set into an output image space.

5. The method of claim 4 in which the output image space corresponds to one of the source image spaces.

6. The method of claim 4 in which the output image space corresponds to a space different from the source image spaces.

7. The method of claim 1 further comprising correcting one or more of the source images to improve matching of overlapping portions of the source images.

8. The method of claim 7 in which image correction comprises correcting for nonuniform magnification.

9. The method of claim 7 in which image correction comprises correcting for nonuniform scaling.

10. The method of claim 7 in which image correction comprises normalizing brightness.

11. The method of claim 7 in which image correction comprises varying a focus.

12. The method of claim 7 in which image correction comprises correcting for vignetting.

13. The method of claim 1 in which determining three-dimensional transformation parameters comprises creating a Gaussian pyramid for each pair of source images.

14. The method of claim 1 in which determining three-dimensional transformation parameters comprises performing non-linear optimization corresponding to an alignment of source images.

15. The method of claim 14 in which non-linear optimization comprises minimizing an error function.

16. The method of claim 1 in which the common output space comprises any of a planar, cylindrical, azimuthal, cubical, or spherical space.

17. The method of claim 1 in which transforming the source images into a common output space comprises selecting, from among a plurality of paths, a path from a source image space to an output image space based on the determined three-dimensional transformation parameters.

18. The method of claim 1 in which a determined three-dimensional transformation between first and second source image spaces and an output space comprises no more than five degrees of freedom.

19. The method of claim 1 in which the created output data set is constrained to be physically realizable.

20. A memory device storing computer readable instructions for aiding a computer to combine two-dimensional source images that have overlapping portions and are taken from a substantially common camera location, each source image represented by a corresponding set of digital data of three-dimensional camera parameters that define a position of the camera relative to the source image that is viewed from the camera, the memory device comprising instructions to perform the following operations:

for each pair of overlapping source images to be combined;

determine three-dimensional transformation parameters defining a mapping between a first image space corresponding to one of the source images'"'"' digital data set and a second image space corresponding to the other of the source images'"'"' digital data set, the mapping describing a reorienting of the camera from one of the source images to the other of the source images; and

create an output data set representing a two-dimensional output image by combining the digital data sets representing the pair of source images in accordance with the determined three-dimensional transformation parameters and by transforming the source images into a common output space by finding a path from a source image space to an output image space based on the determined three-dimensional transformation parameters;

in which finding a path includes choosing a path that is more accurate than other paths.

21. An apparatus to combine two-dimensional source images that have overlapping portions and are taken from a substantially common camera location, the apparatus comprising:

a storage medium to store overlapping source images, each source image represented by a corresponding set of digital data of three-dimensional camera parameters that define a position of the camera relative to the source image that is viewed from the camera; and

a processor operatively coupled to the storage medium and configured to perform the following operations;

for each pair of overlapping source images to be combined;

determine three-dimensional transformation parameters defining a mapping between a first image space corresponding to one of the source images'"'"' digital data set and a second image space corresponding to the other of the source images'"'"' digital data set, the mapping describing a reorienting of the camera from one of the source images to the other of the source images; and

create an output data set representing a two-dimensional output image by combining the digital data sets representing the pair of source images in accordance with the determined three-dimensional transformation parameters and by transforming the source images into a common output space by finding a path from a source image space to an output image space based on the determined three-dimensional transformation parameters;

in which finding a path includes choosing a path that is more accurate than other paths.

22. A computer-implemented method for combining two-dimensional source images that have overlapping portions and are taken from a substantially common camera location, each source image represented by a corresponding digital data set of three-dimensional camera parameters that define a position of the camera relative to the source image that is viewed from the camera, the method comprising:

for each pair of overlapping source images to be combined;

determining three-dimensional transformation parameters defining a mapping between a first image space corresponding to one of the source images'"'"' digital data set and a second image space corresponding to the other of the source images'"'"' digital data set, the mapping describing a reorienting of the camera from one of the source images to the other of the source images; and

creating an output data set representing a two-dimensional output image by combining the digital data sets representing the pair of source images in accordance with the determined three-dimensional transformation parameters and by transforming the source images into a common output space by finding a path from a source image space to an output image space based on the determined three-dimensional transformation parameters;

in which finding the path comprises constraining parameters of the source images.

23. A computer-implemented method for combining two-dimensional source images that have overlapping portions and are taken from a substantially common camera location, each source image represented by a corresponding digital data set of three-dimensional camera parameters that define a position of the camera relative to the source image that is viewed from the camera, the method comprising:

for each pair of overlapping source images to be combined;

determining three-dimensional transformation parameters defining a mapping between a first image space corresponding to one of the source images'"'"' digital data set and a second image space corresponding to the other of the source images'"'"' digital data set, the mapping describing a reorienting of the camera from one of the source images to the other of the source images; and

creating an output data set representing a two-dimensional output image by combining the digital data sets representing the pair of source images in accordance with the determined three-dimensional transformation parameters and by transforming the source images into a common output space by finding a path from a source image space to an output image space based on the determined three-dimensional transformation parameters;

in which finding the path comprises generating a minimum spanning tree.