Automatic digital image grouping using criteria based on image metadata and spatial information

• US 7,580,952 B2
• Filed: 02/28/2005
• Issued: 08/25/2009
• Est. Priority Date: 02/28/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Logan, Ronald K., Uyttendaele, Matthew T., Szeliski, Richard S.
• Primary Examiner(s): Alam; Hosain T
• Assistant Examiner(s): Yen; Syling
• Application Number:
  US11/069,662
• Publication Number:
  US 20060195475A1
• Time in Patent Office: 1,639 Days
• Field of Search: 707/100, 707/101, 707/102, 707/10, 707/205, 707/104.1, 382/108, 382/100, 382/254, 382/275, 345/424, 345/419, 348/45, 348/65
• US Class Current: 1/1
• CPC Class Codes: G06F 16/58 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/587 using geographical or spatial information, e.g. location
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

An automatic digital image grouping system and method for automatically generating groupings of related images based on criteria that includes image metadata and spatial information. The system and method takes an unordered and unorganized set of digital images and organizes and groups related images into image subsets. The criteria for defining an image subset varies and can be customized depending on the needs of the user. Metadata (such as EXIF tags) already embedded inside the images is used to extract likely image subsets. This metadata may include the temporal proximity of images, focal length, color overlap, and geographical location. The first component of the automatic image grouping system and method is a subset image stage that analyzes the metadata and generates potential image subsets containing related images. The second component is an overlap detection stage, where potential image subset is analyzed and verified by examining pixels of the related images.

Claims

1. A computer-implemented method for automatically grouping related images, comprising:

using a general-purpose computing device to perform the following method;

inputting a set of unordered images containing a collection of unordered and unorganized images;

analyzing metadata associated with each image in the unordered image set to determine the related images;

generating a potential image subset containing the related images based on results of the metadata analysis;

analyzing and verifying the potential image subset by opening each image of the potential image subset and examining each pixel of each image to determine a type of spatial relationship between the pixels and an amount of spatial overlap of pixels in images of the potential image subset; and

automatically determining whether the potential image subset is a panorama, which contains a significant amount of motion between images, has spatial overlap, and contains images that cover different portions of a scene;

if the potential image subset is a panorama, then grouping the images in the potential image subset that are panoramas for processing by a first image processing technique comprising;

an image stitching technique that is used to stitch the images in the potential image subset together and create a panorama;

automatically determining whether the potential image subset is a true image stack, which contains images having spatial overlap and capturing the same scene but has little or no camera motion between images;

if the potential image subset is a true image stack, then grouping the images in the potential image subset that are true image stacks for processing by a second image processing technique comprising;

(a) a best picture selection technique or an image merging technique, if the potential image subset is a true stack;

(b) a high-dynamic range technique, if the potential image subset is a multiple exposure stack;

(c) a photomontage technique that takes a collection similar images and creates a single composite image, if images of the potential image subset have similar exposure.

2. The method of claim 1, further comprising using a pairwise technique to analyze and verify the potential image subset.

3. The method of claim 1, further comprising selecting an image processing technique to process the potential image subset based on whether the potential image subset is a panoramas or a true image stack.

4. The method of claim 1, further comprising selecting at least one collection recognizer as criteria for generating the potential image subset.

5. The method of claim 4, wherein the collection recognizer is at least one of:

(a) similar temporal proximity;

(b) similar focal length;

(c) similar geographical location;

(d) thumbnail images.

6. The method of claim 1, wherein analyzing metadata associated with each image further comprises obtaining the metadata in an exchangeable image file (EXIF) associated with each image without opening the image.

7. A computer-implemented process for automatically examining pixels and metadata associated with each image in an unordered image set to determine which images are related, comprising using a computer to perform the following:

a first selection step for selecting collection recognizers that are criteria for which metadata to examine, the collection recognizers including temporal proximity and focal length;

a metadata analysis step for analyzing the metadata of each image in the unordered image set based on the collection recognizers;

an image grouping step for grouping each image based on similar collection recognizers to generate potential image subsets containing groupings of related images;

a verification step for analyzing and verifying the potential image subsets using a pairwise technique that opens each image of the potential image subsets and performs a pixel analysis of pixels in each image to determine a type of spatial relationship between the pixels and an amount of spatial overlap of the pixels in images of the potential image subsets to generate verified image subsets;

a first determination step for automatically determining whether the images of the verified image subsets are panoramas, which contain images that have a significant amount of motion between image and have spatial overlap but that cover different portions of a scene;

if the images of the verified image subsets are panoramas, then a second selection step for selecting a first image processing technique comprising;

an image stitching technique that is used to stitch the images of the verified image subsets together and create a panorama;

a second determination step for automatically determining whether the images of the verified image subsets are true image stacks, which contain images that have spatial overlap and that capture the same scene but have virtually no camera motion between images;

if the images of the verified image subsets are true image stacks, then a third selection step for selecting a second image processing technique comprising;

(a) a best picture selection technique or an image merging technique, if the images of the verified image subsets are a true stack;

(b) a high-dynamic range technique, if the images of the verified image subsets are a multiple exposure stack;

(c) a photomontage technique that takes a collection similar images and creates a single composite image, if images of the images of the verified image subsets have similar exposure; and

an image processing step for processing the verified image subsets using the selected image processing technique.

8. The computer-implemented process as set forth in claim 7, wherein the collection recognizers include at least one of:

(a) color overlap using thumbnail images;

(b) geographical location, including the location on earth of where an image was captured and a direction that the image is facing.

9. The computer-implemented process as set forth in claim 7, further comprising analyzing the metadata of each image without opening the image to examine its pixels.

10. An automatic image grouping system for discovering a related group of images, comprising:

a general purpose computing device;

a computer program comprising program modules executable by the computing device, the computer program further comprising;

an unordered image set containing a plurality of unorganized digital images;

a metadata analysis module that analyzes metadata associated with each of the plurality of digital images;

a metadata relation module located on the metadata analysis module that determines which of the plurality of digital images is related based on collection recognizers, the collection recognizers being criteria that dictates which metadata to analyze;

a potential image subset that contains the related group of images;

a verification module that analyzes and verifies the potential image subset using a pairwise technique by opening each image of the potential image subset and examining each pixel of each image to determine a type of spatial relationship between the pixels and an amount of spatial overlap of pixels in images of the potential image subset, and automatically determining whether;

(a) the potential image subset is a panorama that contains a significant amount of motion between images and spatial overlap and having images that cover different portions of a scene to provide the panorama, and using a first imaging processing technique to process the potential image subset;

or (b) a true image stack that contains images having spatial overlap and capturing the same scene but have little or no camera motion between images, and using a second image processing technique to process the potential image subset;

a first user interface displayed on a display device for presenting to a user of the system which image groupings were used to form the potential image subset and which images were not used;

a second user interface displayed on the display device for informing the user whether the potential image subset contains images that form a panorama or a true image stack;

the first image processing technique that is used to process the image groupings if the potential image subset is a panorama, where the first image processing technique is a technique comprising;

an image stitching technique that is used to stitch the images in the potential image subset together and create a panorama; and

the second image processing technique that is used to process the image groupings if the potential image subset is a true image stack, where the second image processing technique is a technique comprising;

(a) a best picture selection technique or an image merging technique, if the potential image subset is a true stack;

(b) a high-dynamic range technique, if the potential image subset is a multiple exposure stack;

(c) a photomontage technique that takes a collection similar images and creates a single composite image, if images of the potential image subset have similar exposure.

11. The automatic image grouping system of claim 10, further comprising a collection recognizer selection module that determines which collection recognizers to use by the metadata relation module.