Method and apparatus for mosaic image construction

Claims

We claim:

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.

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.

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.

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.

BACKGROUND OF THE INVENTION

The invention relates to a method and apparatus for constructing mosaic images from multiple source images.

Video and digital cameras provide relatively low resolution images, covering a limited field of view. Both the lower resolution and the limited field of view problems can be overcome by combining several images into an extended image mosaic.

Mosaics can be created from a set of source images by aligning the images together to compensate for the camera motion, and merging them to create an image which covers a much wider field of view than each individual image. The two major steps in the construction of a mosaic are image alignment, and the merging of the aligned images into a large, seamless, mosaic image.

Various methods and systems for image alignment for constructing mosaics currently exist. Mosaic images have been constructed from satellite and space probe images for many years. In these cases the appropriate parameters for aligning images are known from careful measurements of the camera viewing direction or are determined by manually designating corresponding points in overlapped image regions. A method that makes use of careful measurement of camera orientation is described, for example, in Plenoptic Modeling: An Image-Based Rendering System", L. McMillan and G. Bishop, SIGGRAPH 95. In this approach the images are taken from a camera the motion of which is a highly controlled, complete circle rotation about the optical center. The constructed mosaic is created by projecting the images into a cylindrical imaging plane, thus avoiding the distortions that may be associated with mosaicing a complete circle on a single planar image.

More generally, alignment is achieved through image processing techniques that automatically find image transformations (e.g., translation, rotation, scale) that bring patterns in overlapping images into precise alignment. Methods based on image processing are described in U.S. patent application Ser. No. 08/339,491 "Mosaic Based Image Processing System", filed on Nov. 14, 1994 and in U.S. patent application Ser. No. 08/493,632, "Method and System for Image Combination Using A Parallax-Based Technique" filed Jun. 22, 1995, each of which is incorporated herein by reference in its entirety.

Systems now exist that can construct mosaics from video in real time using these image processing methods. Such a system is described in "Video Mosaic Displays", P. Burt, M. Hansen, and P. Anandan, SPIE Volume 2736: Enhanced and Synthetic Vision 1996, pp 119-127, 1996. and in "Real-time scene stabilization and mosaic construction", M. Hansen, P. Anandan, K. Dana, G, van der Wal, and P. Burt, ARPA Image Understanding Workshop, November 1994, pp. 457-465.

Various image processing methods currently exist for merging source images into a seamless mosaic. The simplest methods digitally feather one image into another by computing a weighted average of the two images within the zone in which they overlap. This method can result in an appearance of double images if the source images are not precisely aligned over entire the overlap region or in a visible but blurred seam, if the two differ significantly in such characteristics as mean intensity, color, sharpness, or contrast. A more general method of merging images to avoid seams makes use of an image pyramid to merge the images at many different scales simultaneously. This method was first described in "A Multiresolution Spline With Applications to Image Mosaics", P. J. Burt and E. H. Adelson, ACM Transactions of graphics, Vol. 2, No. 4, October 1983, pp. 217-236 (Burt I).

It is also desirable for the merging step in mosaic construction also to fill any holes in the mosaic that are left by lack of any source images to cover some portion of the desired mosaic domain. A method of filling holes in the mosaic that uses the multiresolution, pyramid image processing framework has been described in Moment Images, polynomial fit filters, and the problem of surface interpolation, P. J. Burt, ICPR 1988, pp. 300-302.

Image merging methods used in mosaic construction may also provide image enhancement. For example, image "noise" can be reduced within overlap zones by simply averaging the source images. If some source images are of better quality than others, or show aspects of objects in the scene more clearly than others, then non-linear methods are may be used to choose the "best" information from each source image. Such as method is described in Enhanced image capture through fusion, P. J. Burt and R. Kolczynski, ICCV 1993, pp 242-246.

Multiple source images may be combined in ways that improve image resolution within the overlap regions. Such a methods is described in "Motion Analysis for Image Enhancement: Resolution, Occlusion, and Transparency", M. Irani and S. Peleg, Vision Communications and Image Representation Vol. 4, December 1993, pp. 324-335.

These existing methods for mosaic construction lack several capabilities that are provided by the present invention:

An effective image processing means for simultaneously aligning all source images to obtain a best overall alignment for use in the mosaic. Current methods align only pairs of images. In constructing a mosaic from a sequence of video frames, for example, each image is aligned to the previous image in the sequence. Small alignment errors can accumulate that result in poor alignment of overlapping image frames that occur at widely separated times in the sequence.

An effective image processing means for merging all source image to obtain a best overall mosaic. Current methods merge image only two at a time. A mosaic composed of many image is constructed by merging in one new image at a time. This method may not provide best overall quality, and may entail unnecessary computation.

An effective image processing means for merging source images that differ dramatically in exposure characteristics.

An effective image processing means for automatically selecting region of each source image to be included in the mosaic from the overlapped regions

A system implementation that is practical for commercial and consumer applications.

SUMMARY OF THE INVENTION

The invention is a method of constructing an image mosaic comprising the steps of selecting source images, aligning the source images, selecting source image segments, enhancing the images, and merging the images to form the image mosaic.

The invention is also 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.

BRIEF DESCRIPTION OF THE DRAWING

The teachings of the present invention can be readily understood by considering the following detailed description in conjunction with the accompanying drawings, in which:

FIG. 1 is a block diagram the overall system; and

FIG. 2 is a flow diagram which illustrates the source image selection.

FIG. 3A is a flow-chart diagram which shows an exemplary image alignment method.

FIG. 3B is an image diagram which is useful for describing the alignment process shown in FIG. 3A.

FIG. 4 is an image diagram which depicts the region selection.

FIG. 5 is a flow diagram which shows an image enhancement process.

FIG. 6 is a data structure diagram which illustrates a pyramid construction for image merging.

FIG. 7 is a block diagram which is useful for describing an exemplary embodiment of the invention.

FIG. 8 is a flow-chart diagram of a process which is suitable for use as the front-end alignment process shown in FIG. 7.

FIG. 9 is a diagram illustrating images that are processed by the system which is useful for describing the front-end alignment process shown in FIG. 7.

FIGS. 10A and 10B are image diagrams which are useful for describing the operation of the front-end alignment process shown in FIG. 7.

FIG. 11A is a flow-chart diagram of a process which is suitable for use as the correlation process shown in FIG. 8.

FIG. 11B is a graph of an acceptance region which is useful for describing

the operation of the correlation process shown in FIG. 11A.

FIG. 12 is a diagram of images which is useful for describing the back-end alignment process shown in FIG. 7.

FIG. 13 is a diagram of images which is useful for describing a first alternative back-end alignment process suitable for use in the block diagram shown in FIG. 7.

FIG. 14 is a diagram of images which is useful for describing a second alternative back-end alignment process suitable for use in the block diagram shown in FIG. 7.

FIG. 15 is a flow-chart diagram of a process suitable for use as the back-end alignment process shown in FIG. 7.

To facilitate understanding, identical reference numerals have been used, where possible, to designate identical elements that are common to the figures.

DETAILED DESCRIPTION

The invention relates to apparatus and a method for constructing a mosaic image from multiple source images. The invention provides a practical method for obtaining high quality images, having a wide field of view, from relatively lower quality source images. This capability can have important uses in consumer and professional "photography," in which a video camera or digital camera is used to provide photographic quality prints. It can also be used to enhance the quality of displayed video.

A general process for forming a mosaic image is shown in FIG. 1. This comprises a image source 101, a sequence of processing steps 102 to 106, and a mosaic output means 108. There is also an optional means 109 for a human operator to view the results of the processing steps and interactively control selected steps.

Image Source 101

The mosaic construction process begins with a set of source images. These may include "live" images from various types of imaging sensors, such as video cameras, digital still cameras, and image scanners, images from various storage media, such as video tape (VCR), computer files, synthetically generated images, such as computer graphics, and processed images, such as previously constructed mosaics.

The mosaic construction process comprises five basic steps:

Step 1: Source Image Selection 102

A set of images to be combined into a mosaic is selected from the available source images. This may be done manually or automatically.

The selection process finds a set of good quality images that cover the intended domain and content of the mosaic.

When the mosaic is built from a sequence of video frames, this selection step may comprise indicating the first and last frames to be included in the mosaic. This selection indicates that all intermediate frames should be used. The start and stop frames may be selected through control of the video camera itself, as by starting or stopping systematic sweeping motions of the camera, motions that are then automatically detected by the system.

When a mosaic is to built from a collection of snapshots, it may be desirable for the user to interactively select each source image.

Source selection may also include cutting sub images out of larger images. For example, a user may cut out a picture of a person in one source image so that it may be merged into a new location in another image of the mosaic.

Step 2: Image Alignment 103

The selected source images are desirably aligned with one another so that each is in registration with corresponding portions of neighboring images. Alignment entails finding a geometrical transformation, or a "warping," which, after being applied to all of the selected images, brings them into a common coordinate system. The geometric transform is typically defined in terms of a set of parameters. These may be shift, rotate, dilate, projective, high order polynomial, or general flow (e.g., piece wise polynomial, with a different set of parameters at each sample point). Warping techniques are disclosed in U. S. Provisional Patent Application Ser. No. 60/015,577 filed Apr. 18, 1996 and entitled "Computationally Efficient Digital Image Warping" which is incorporated herein by reference in its entirety.

Alignment can be done interactively through the user interface 109, by having the user indicate corresponding points, then finding the transform parameters that bring these points into registration (or most nearly into registration according to some least error criterion), or by specifying the transformation parameters interactively (e.g., with a mouse or other pointing device).

Alignment can also be done automatically by various image processing methods that determine the warp parameters that provide a best match between neighboring images. Alignment may combine manual and automatic steps. For example, an operator may bring the images into rough alignment manually, then invoke an automatic process to refine the warp parameters to provide precise alignment.

The alignment process may interact with the source image selection process 102. Alignment provides information on the degree of overlap and, in the case of video, on the velocity of camera motion. Images may be discarded if their overlap is too large, or new images may be added if the degree of overlap is too little. Images may be discarded if camera motion is too large, and thus likely to result in motion blur. Abrupt changes in camera motion may be used to signal the intended start and stop of video sequence used in mosaic construction.

This invention presents image alignment methods that take all frames into account simultaneously. Rather than the traditional alignment approaches that align two images by minimizing some error function between them, this disclosure proposes a method to align all images simultaneously, or to align any subset of images, by minimizing the error function which is the summation of all errors between any overlapping pair of images.

Step 3. Region Selection 104

Subregions of the overlapping aligned source images are selected for inclusion in the mosaic. The selection process effectively partitions the domain of the mosaic into subregions such that each subregion represents the portion of the mosaic taken from each source image. Selection may be done manually or automatically. Manual selection may be done interactively through the user interface 109, by drawing boundary lines on a display of neighboring overlapped images using a pointing device such as a mouse. Automatic selection finds the appropriate cut lines between neighboring images based on location (e.g., distance to the center of each source image) or quality (such as resolution or motion blur).

In a more general approach to selection, some overlapped portions of may be combined through averaging or pattern selective fusion.

Step 4. Image Enhancement 105

Individual images may be further processed prior to merging to improve their contrast or sharpness or to adjust these characteristics to be similar to the corresponding characteristics of their neighboring images. Enhancement is based on the intensity, color and filtering operations. Parameters of these operations may be determined manually or automatically.

Step 5. Merging 106

In this step, the selected source images are combined into a single mosaic. This is desirably done in a way that yields a resul