System for automatically aligning images to form a mosaic image

• US 5,649,032 A
• Filed: 11/14/1994
• Issued: 07/15/1997
• Est. Priority Date: 11/14/1994
• Status: Expired due to Term

• Current Assignee: Sarnoff Corporation (SRI International, Inc.)
• Original Assignee: David Sarnoff Research Center, Inc.
• Inventors: Hansen, Michael W., Hsu, Stephen Charles, Anandan, Padmanabhan, Irani, Michal, Burt, Peter J.
• Primary Examiner(s): JOHNS, ANDREW W
• Application Number:
  US08/339,491
• Time in Patent Office: 974 Days
• Field of Search: 382/100, 382/284, 382/294, 358/450, 348/564, 348/588, 345/115, 395/111, 395/135, 395/153
• US Class Current: 382/284
• CPC Class Codes: G06T 11/00 2D [Two Dimensional] image generation
• 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/20 using video object coding
• 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/30 using hierarchical techniques, e.g. scalability H04N19/63 takes precedence
• CPC Class Codes: H04N 19/503 involving temporal prediction adaptive coding with adaptive selection between spatial and temporal predictive coding H04N19/107; adaptive coding with adaptive selection among a plurality of temporal predictive coding modes H04N19/109
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 5/781 on disks or drums
• CPC Class Codes: H04N 5/85 on discs or drums
• CPC Class Codes: H04N 9/8047 using transform coding

Abstract

A system for automatically generating a mosaic from a plurality of input images. The system sequentially executes an image alignment process, an editing process, and a combining process such that, from a sequence of images, the system automatically produces a seamless mosaic for various applications. Illustrative applications for the mosaic include: (1) a mosaic based display system including an image printing system, (2) a surveillance system and (3) a mosaic based compression system. The mosaic based display system permits a system user to display, manipulate and alter a mosaic. The mosaic based compression system exploits the temporal and spatial redundancy in image sequences and efficiently compresses the image information. The compression system can be used for compressing image information for storage in a storage device or can be used for compressing image information for transmission through a band-limited transmission channel. The surveillance system combines the mosaic construction system, the compression system and the display system into a comprehensive system for remote motion detection.

Claims

1. A system for automatically generating a mosaic from a single sequence of images comprising:

means for automatically aligning image information in each of said images in said single sequence of images with common image information in at least one other image in said single sequence of images;

means, connected to said aligning means, for composing said aligned images into a mosaic.

2. The system of claim 1 wherein said aligning means further includes means for selecting a reference coordinate system within which the images are aligned.

3. The system of claim 2 wherein said selected reference coordinate system is the coordinate system of one of the images.

4. The system of claim 2 wherein said selected reference coordinate system is the coordinate system of the mosaic.

5. The system of claim 2 wherein said selected reference coordinate system is a fixed reference coordinate system.

6. The system of claim 2 wherein said selected reference coordinate system is an arbitrary reference coordinate system.

7. The system of claim 1 wherein said aligning means further comprises:

defining means for defining a transformation for aligning the images to a reference coordinate system; and

performing means for performing said transformation whereby the images are aligned with the reference coordinate system.

8. The system of claim 1 wherein said composing means further comprises means for masking or cropping at least one of said images.

9. The system of claim 1 wherein said aligning means further comprises means for generating an image pyramid for each of said images.

10. The system of claim 9 wherein said aligning means further comprises means for performing a course-to-fine alignment using the image pyramids for each of said images.

11. A method for generating a dynamic mosaic by combining a previously generated mosaic with an input image from a single sequence of input images, comprising the steps of:

(a) aligning said input image with said previously generated mosaic, where the alignment is performed with respect to a reference coordinate system and image information contained in said input image is aligned with common image information in said previously generated mosaic, where a portion of said input image containing said common image information overlaps a portion of said previously generated mosaic containing said common image information;

(b) selecting said portion of said input image and said portion of said previously generated mosaic to be combined to form an updated mosaic;

(c) combining the selected portion of the input image with selected portion of the previously generated mosaic to produce an updated mosaic; and

(d) repeating steps (a), (b) and (c) for each input image in said single sequence of input images to continuously update the updated mosaic with at least a portion of each input image in said single sequence of input images.

12. The method of claim 11 wherein said aligning step further comprises the steps of:

defining a transformation for aligning said input image to the reference coordinate system; and

performing said transformation whereby said input image is aligned with the reference coordinate system.

13. The method of claim 11 wherein said selecting step further comprises the step of masking or cropping said previously generated mosaic.

14. The method of claim 11 wherein said selecting step further comprises the step of removing selected images from said previously generated mosaic.

15. The method of claim 11 wherein said aligning step further comprises the step of generating an image pyramid for both said input image and said previously generated mosaic.

16. The method of claim 15 wherein said aligning step further comprises the step of performing a course-to-fine alignment using the image pyramid for said input image and the image pyramid of said previously generated mosaic.

17. The method of claim 16 wherein said aligning step further comprises the steps of:

coarsely aligning said input image and said previously generated mosaic at a selected pyramid resolution level by;

tiling said previously generated mosaic to produce a plurality of mosaic tiles;

selecting plurality of windows containing landmarks having a highest image energy within the input image;

selecting a mosaic tile from said plurality of mosaic tiles; and

correlating said input image windows with said selected mosaic tile, where a correlation peak indicates a coarse alignment of said input image and said previously generated mosaic.

18. The method of claim 17 wherein said step of selecting a mosaic tile further comprises the step of selecting a tile containing at least a portion of an image that occurred sequentially prior to the input image.

19. The method of claim 17 wherein said aligning step further comprises the steps of:

finely aligning said input image to said previously generated mosaic by;

selecting relatively small patches of the input image having a highest resolution; and

correlating said relatively small patches of the input image with said selected tile of said mosaic, where a correlation peak indicates a fine alignment of said input image and said previously generated mosaic.

20. The method of claim 11 further comprising the step of displaying said updated mosaic.

21. The method of claim 20 further comprising the step of adding ancillary information as an overlay upon a displayed updated mosaic.

22. The method of claim 21 wherein said adding step further comprises the steps of highlighting portions of the updated mosaic, color enhancing portions of the updated mosaic, and outlining portions of the updated mosaic.

23. The method of claim 20 wherein said displaying step further comprises the step of image processing said updated mosaic.

24. A method for generating a static mosaic from a single sequence of input images comprising the steps of:

aligning a plurality of said input images with one another, where the alignment is performed with respect to a reference coordinate system;

selecting portions of said input images to be combined to form a static mosaic; and

combining the selected portions of the input images to produce a static mosaic.

25. The method of claim 24 wherein said aligning step further comprises the steps of:

defining a transformation for aligning the selected portions of the input images to the reference coordinate system; and

performing said transformation whereby the input images is aligned with the reference coordinate system.

26. The method of claim 24 wherein said selecting step further comprises the steps of masking or cropping said input images.

27. The method of claim 24 wherein said aligning step further comprises the step of generating an image pyramid for each of said input images.

28. The method of claim 27 wherein said aligning step further comprises the steps of performing a course-to-fine alignment using the image pyramid for each of said input images.

29. The method of claim 28 wherein said aligning step further comprises the steps of:

coarsely aligning the input images at a selected pyramid resolution level by;

tiling each of said images;

selecting a plurality of windows within said input images containing landmarks having a highest image energy;

selecting a tile from an input image; and

correlating said plurality of windows with said selected tile, where a correlation peak indicates a coarse alignment of said selected input image with a second image that contains the landmark.

30. The method of claim 29 wherein said aligning step further comprises steps of:

finely aligning said input images by;

selecting relatively small patches of a selected input image having a highest available resolution within said image pyramid for said selected input image; and

correlating said relatively small patches of the selected input image with a selected tile of a second input image, where a correlation peak indicates a fine alignment of said selected input image with the second input image.