Method and apparatus for mosaic image construction

• US 6,075,905 A
• Filed: 07/18/1997
• Issued: 06/13/2000
• Est. Priority Date: 07/17/1996
• Status: Expired due to Term

• Current Assignee: Sarnoff Corporation (SRI International, Inc.)
• Original Assignee: Sarnoff Corporation (SRI International, Inc.)
• Inventors: Sawhney, Harpreet, Gendel, Gary A., Herman, deceased, Joshua Randy, Kumar, Rakesh, Paragano, Vincent, Peleg, Shmuel, Bergen, James Russell, Brill, Michael H., Burt, Peter J., Dixon, Douglas F.
• Primary Examiner(s): MEHTA, BHAVESH M
• Application Number:
  US08/896,887
• Time in Patent Office: 1,061 Days
• Field of Search: 382/154, 382/236, 382/284, 382/278, 382/293, 382/294, 382/162, 382/107, 345/423, 345/427, 345/435, 348/584, 348/588, 348/598, 358/450
• 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/16 using multiple overlapping images; Image stitching
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: H04N 19/23 with coding of regions that are present throughout a whole video segment, e.g. sprites, background or mosaic
• CPC Class Codes: H04N 19/597 specially adapted for multi-view video sequence encoding

Abstract

A method of constructing an image mosaic comprising the steps of selecting source images, aligning the source images, selecting source segments, enhancing the images, and merging the images to form the image mosaic is disclosed. An apparatus for constructing an image mosaic comprising means for selecting source images, means for aligning the source images, means for selecting source image segments, means for enhancing the images, and means for merging the images to form the image mosaic is also disclosed. The process may be performed automatically by the system or may be guided interactively by a human operator. Applications include the construction of photographic quality prints form video and digital camera images.

Claims

1. A computer implemented method of constructing an image mosaic comprising the steps of:

a) receiving a plurality of source images;

b) analyzing the received source images to select ones of the source images to use in the image mosaic and to form an initial alignment of the selected source images;

c) analyzing the selected source images to establish a coordinate system for the image mosaic;

d) aligning ones of the selected source images to the coordinate system, including the steps of

calculating an error function which includes alignment errors for at least two of the selected source images; and

warping the at least two of the selected source images to reduce the error function; and

e) merging the aligned images to form the image mosaic.

2. A method according to claim 1 wherein step b) includes the steps of:

b1) calculating an image coordinate transformation between one image of the received images and a previously selected image;

b2) identifying an overlap region between the one image and the previously selected image responsive to the transformation;

b3) determining a number of picture elements (pixels) in the overlap region; and

b4) selecting the one image to use in the image mosaic if the number of pixels in the overlap region is within a predetermined range of values.

3. A method according to claim 2 wherein the step b1) comprises the iterative steps of:

filtering the one image according to a selected filter characteristic;

generating a measure of correlation between the filtered one image and the previously selected image; and

comparing the measure of correlation to a threshold value and if the measure of correlation is less than the threshold value, selecting a different filter characteristic;

continuing the iterative steps until the measure of correlation is greater than the threshold value or no further filter characteristic is available for selection.

4. A method according to claim 1, wherein step b) includes the steps of:

calculating a measure of quality for each of the received images; and

excluding from selection any image having a measure of quality which less than a predetermined threshold value.

5. A method according to claim 1, wherein:

the received images are provided from a moving camera;

step b) includes the steps of;

determining motion of the moving camera; and

initiating the selection of received images responsive to a first change in the camera motion; and

terminating the selection of received images responsive to a second change in the camera motion.

6. A method according to claim 1 wherein:

step c) establishes the coordinate system for the image mosaic relative to one of the images that is centrally located in the initial alignment of the source images.

7. A method according to claim 1 wherein:

step b) selects images by correlating a portion of each image to a previously selected image to form an initial mosaic alignment; and

step c) selects multiple overlapping images from the initial mosaic and defines the coordinate system as a minimum mapping from all of the selected multiple images.

8. A method according to claim 1 wherein step d) includes the steps of

d1) forming an approximate alignment of all of the selected source images;

d2) calculating the error function which includes alignment errors at least for regions in which ones of the selected images overlap; and

d3) iteratively refining the approximate alignment to reduce the error function.

9. A method according to claim 8 wherein step dl) includes the steps of:

designating one of the selected images as being in the mosaic;

aligning each successive image to the mosaic;

incorporating each aligned image into the mosaic.

10. A method according to claim 8 wherein step dl) includes the steps of:

designating a first one of the selected images as being in the mosaic;

aligning a second one of the selected images to the first selected image to generate a first alignment transform which aligns the second image to the mosaic;

aligning a third one of the selected images to the second selected image to generate a second alignment transform; and

composing the first and second alignment transforms to generate a composite alignment transform which aligns the third image to the mosaic.

11. A method according to claim 8 wherein step d2) employs multiresolution alignment techniques.

13. A method according to claim 8, wherein:

step d2) includes the steps of;

calculating a global alignment error as the error function over the aligned mosaic image;

defining respective match error surfaces for all pairs of overlapping frames; and

step d3) includes the steps of;

calculating a set of transforms over all pairs of overlapping frames which tends to reduce the error function; and

warping ones of the image frames that are affected by the calculated transforms to obtain a refined aligned mosaic image.

14. A method according to claim 1, further including, between steps d) and e), the step of defining respective regions of the selected images to be used in the mosaic image.

15. A method according to claim 14, wherein the step of defining respective regions of the selected images to be used in the mosaic image includes the steps of:

identifying sets of mutually overlapping images;

defining a measure of quality of each image of the set of mutually overlapping images;

for each region in which overlap exists, identifying one of the images containing the overlap region in which has the overlap region has the greatest measure of quality and selecting a region which includes the overlap region from the identified image.

16. A method according to claim 14, wherein the step of defining respective regions of the selected images to be used in the mosaic image includes the steps of:

defining a Voronoi tessellation for the image mosaic;

selecting respective images having a common vertex in the Voronoi tessellation to contribute regions to the image mosaic.

17. A method according to claim 14, wherein the step of defining respective regions of the selected images to be used in the mosaic image includes the steps of:

identifying sets of mutually overlapping images;

calculating, at a picture element (pixel) level, a measure of misalignment across all of the overlapping images;

for each overlap region, defining a cut-line as a locus of pixels having a minimal measure of misalignment;

defining the regions in the respective images relative to the cut-lines.

18. A method according to claim 1, wherein step e) includes the steps of:

applying a reversible transform to all picture elements (pixels) of the image mosaic;

merging the pixels of the image mosaic using multiresolution merging techniques;

reversing the transform on the merged mosaic.

19. A method according to claim 18 wherein the multiresolution merging techniques use only Laplacian pyramids.

20. A method according to claim 1, wherein the source images are color images and the image mosaic is a color image having a luminance component and at least one chrominance component, wherein, steps a), b), c) and d) are performed using only the luminance component and step e) is performed using the luminance component and the chrominance component.

21. A method according to claim 19, wherein step e) includes the steps of:

converting the luminance and chrominance components to primary color signal components;

identifying a reference image;

identifying portions of the reference image which overlap ones of the selected images;

defining an objective function representing a measure of difference among respective color signal vectors of each of the overlapping images at each corresponding point in the overlapping portions of the images;

calculating an affine color space transformation which mimimizes the objective function;

performing multiresolution merging separately on each of the primary signal components.

12. A method according to claim 81, wherein the multiresolution alignment techniques include the steps of:

defining respective pyramid representations of overlapping portions of the aligned mosaic image;

processing image data in the overlap region using respective pyramid levels which are at a level that is higher than a predetermined pyramid level in pyramid representation to provide an initial transformation;

transforming the mosaic according to the initial transformation;

generating pyramid representations of sub-mosaic images representing respective portions of the overlap regions;

processing image data of the sub-mosaic images using the pyramid levels to provide a refined transformation.

22. A computer implemented method of aligning a plurality of source images comprising the steps of:

a) analyzing the source images to select ones of the source images to align and to form an initial alignment of the source images;

b) analyzing the selected source images to establish a coordinate system for the image mosaic;

c) aligning ones of the selected source images to the coordinate system including the steps of;

calculating an error function which includes alignment errors for all of the selected source images with respect to the coordinate system; and

warping ones of the selected source images to reduce the error function.

23. A method according to claim 22 wherein step a) includes the steps of:

a1) calculating an image coordinate transformation between one image of the received images and a previously selected image;

a2) identifying an overlap region between one image of the source images and a previously selected image responsive to the transformation;

a3) determining a number of picture elements (pixels) in the overlap region; and

a4) selecting the one image to use in the image mosaic if the number of pixels in the overlap region is within a predetermined range of values.

24. A method according to claim 23 wherein the step al) comprises the iterative steps of:

filtering the one image according to a selected filter characteristic;

generating a measure of correlation between the filtered one image and the previously selected image; and

comparing the measure of correlation to a threshold value and if the measure of correlation is less than the threshold value, selecting a different filter characteristic;

continuing the iterative steps until the measure of correlation is greater than the threshold value or no further filter characteristic is available for selection.

25. A method according to claim 22, wherein step a) includes the steps of:

calculating a measure of quality for each of the received images; and

excluding from selection any image having a measure of quality which is less than a predetermined threshold value.

26. A method according to claim 22 wherein step b) establishes the coordinate system for the image mosaic relative to one of the images that is centrally located in the initial alignment of source images.

27. A method according to claim 22 wherein:

step a) selects images by correlating a portion of each image to a previously selected image to form an initial mosaic alignment; and

step b) selects multiple overlapping images from the initial mosaic and defines the coordinate system as a minimum mapping from all of the selected multiple images.

28. A method according to claim 22 wherein step c) includes the steps of

c1) forming an approximate alignment of the selected source images;

and

c2) iteratively refining the approximate alignment to reduce the error function at least in regions in which ones of the selected source images overlap.

29. A method according to claim 28 wherein step c1) includes the steps of:

designating one of the selected images as being in the mosaic;

aligning each successive image to the mosaic;

incorporating each aligned image into the mosaic.

30. A method according to claim 28 wherein step c1) includes the steps of:

designating a first one of the selected images as being in the mosaic;

aligning a second one of the selected images to the first selected image to generate a first alignment transform which aligns the second image to the mosaic;

aligning a third one of the selected images to the second selected image to generate a second alignment transform; and

composing the first and second alignment transforms to generate a composite alignment transform which aligns the third image to the mosaic.

31. A system for constructing an image mosaic comprising:

means for receiving a plurality of source images;

selecting means for analyzing the received source images to select ones of the source images to use in the image mosaic and to form an initial alignment of the source images;

referencing means for analyzing the selected source images to establish a coordinate system for the image mosaic;

aligning means for aligning ones of the selected source images to the coordinate system including;

means for calculating an error function which includes alignment errors for all of the selected source images with respect to the coordinate system; and

means for warping ones of the selected source images to reduce the error function; and

means for merging the aligned images to form the image mosaic.

32. A system according to claim 31 wherein the selecting means includes:

means for calculating an image coordinate transformation between one image of the received images and a previously selected image;

means, responsive to the coordinate transformation, for identifying an overlap region between one image of the received images and a previously selected image;

means for determining a number of picture elements (pixels) in the overlap region; and

means for selecting the one image to use in the image mosaic if the umber of pixels in the overlap region is within a predetermined range of values.

33. A system according to claim 32 wherein the means for selecting comprises:

means for filtering the one image according to a selected one of a set of respectively different filter characteristics;

means for generating a measure of correlation between the filtered one image and the previously selected image; and

means for comparing the measure of correlation to a threshold value.

34. A system for aligning a plurality of source images comprising:

a) selection means for analyzing the source images to select ones of the source images to align and to form an initial alignment of the source images;

b) reference means for analyzing the selected source images to establish a coordinate system for the image mosaic;

c) aligning means for aligning ones of the selected source images to the coordinate system including

means for calculating an error function which includes alignment errors for all of the selected source images with respect to the coordinate system; and

means for warping ones of the selected source images to reduce the error function.

35. A system according to claim 34 wherein the selection means includes:

means for calculating an image coordinate transformation between one image of the received images and a previously selected image;

means, responsive to the coordinate transformation, for identifying an overlap region between one image of the received images and a previously selected image;

means for determining a number of picture elements (pixels) in the overlap region; and

means for selecting the one image to use in the image mosaic if the number of pixels in the overlap region is within a predetermined range of values.

36. A system according to claim 35 wherein the means for selecting comprises:

means for filtering the one image according to a selected one of a set of respectively different filter characteristics;

means for generating a measure of correlation between the filtered one image and the previously selected image; and

means for comparing the measure of correlation to a threshold value.

37. A computer readable medium containing a program which causes a computer to generate an image mosaic of aligned source images, the program causing the computer to perform the steps of:

a) analyzing the source images to select ones of the source images to align and to form an initial alignment of the source images;

b) analyzing the selected source images to establish a coordinate system for the image mosaic;

c) aligning ones of the selected source images to the coordinate system including the steps of;

calculating an error function which includes alignment errors for all of the selected source images with respect to the coordinate system; and

warping ones of the selected source images to reduce the error function.

38. A computer readable medium according to claim 37 wherein step a) includes the steps of:

a1) calculating an image coordinate transformation between one image of the received images and a previously selected image;

a2) identifying an overlap region between one image of the source images and a previously selected image responsive to the coordinate transformation;

a3) determining a number of picture elements (pixels) in the overlap region; and

a4) selecting the one image to use in the image mosaic if the number of pixels in the overlap region is within a predetermined range of values.

39. A computer readable medium according to claim 38 wherein the step a1) comprises the iterative steps of:

filtering the one image according to a selected filter characteristics during each iteration;

generating a measure of correlation between the filtered one image and the previously selected image; and

comparing the measure of correlation to a threshold value and if the measure of correlation is less than the threshold value, selecting a different filter characteristic;

until the measure of correlation is greater than the threshold value or no further filter characteristic is available for selection.