Auto collage

• US 7,529,429 B2
• Filed: 10/24/2006
• Issued: 05/05/2009
• Est. Priority Date: 11/12/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rother, Carsten, Hamadi, Youssef, Blake, Andrew, Bordeaux, Lucas
• Primary Examiner(s): Kassa; Yosef
• Application Number:
  US11/552,312
• Publication Number:
  US 20070058884A1
• Time in Patent Office: 924 Days
• Field of Search: 382/284, 382/294, 382/302, 358/540, 358/448, 358/450
• US Class Current: 382/284
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06V 10/426 Graphical representations

Abstract

It is required to provide an automated process for forming a visually appealing digital collage (also referred to as a tapestry or photomontage) from a plurality of input images. Input images and a collage are labeled. Labels in the collage specify which regions of the input images are used to form those collage regions. An energy function is created for the labeling which contains terms that take into account various criteria to produce a collage. For example, those criteria may relate to the amount of information in the images, similarity of the images, entropy in the images or object class information. A multi-stage optimization process is applied to the energy function which is fast and enables large numbers of input images to be used to produce a collage.

Claims

1. A method comprising:

(i) receiving a plurality of input images from which it is required to automatically form a collage;

(ii) specifying formation of the collage from the input images as a labeling problem;

(iii) forming an energy function for the labeling problem, that energy function comprising a plurality of terms each relating to one or more criteria to be used in forming the collage;

(iv) specifying one or more constraints to be applied to the energy function;

(v) using a multi-stage optimization process to optimize the energy function taking into account the specified constraints such that at least one possible labeling is found for the collage;

(vi) using the labeling found for the collage to form the collage using an image blending process and outputting the collage.

2. A method as claimed in claim 1 wherein the multi-stage optimization process comprises:

selecting a region of interest for each input image; and

applying an optimization process in order to pack as many of the regions of interest as possible within a width and height of the collage provided that as many collage pixels as possible are covered by some input image and provided that as few of the regions of interest as possible overlap in the collage.

3. A method as claimed in claim 2 wherein the multi-stage optimization process comprises a constraint satisfaction process.

4. A method as claimed in claim 1 wherein the multi-stage optimization process comprises ranking the input images on the basis of textural information in those images and an indication of similarity of the images.

5. A method as claimed in claim 1 wherein the multi-stage optimization process comprises selecting a region of interest for each input image.

6. A method as claimed in claim 3 wherein the constraint satisfaction process of the multi-stage optimization process comprises a branch and bound step and a local search step.

7. A method as claimed in claim 2 wherein the multi-stage optimization process further comprises, for any input image areas which overlap in the collage, applying an optimization process to fix pixel identity in those areas.

8. A method as claimed in claim 6 which further comprises applying a blending process to blend those input images packed in the collage.

9. A method as claimed in claim 1 which further comprises obtaining object class information and using the object class information during the process of forming the energy function.

10. A method as claimed in claim 5 wherein the regions of interest are selected such that, for a given image, at least a specified amount of the image information is present in the region of interest.

11. A method as claimed in claim 1 wherein specifying one or more constraints comprises specifying that a given input image may appear in the collage with only one displacement of that input image with respect to the collage.

12. A method as claimed in claim 1 wherein specifying one or more constraints comprises specifying that each plurality of collage pixels drawn from the same input image should preferably form a connected region.

13. A method comprising:

(i) receiving a plurality of input images from which it is required to automatically form a collage;

(ii) specifying formation of the collage from the input images as a labeling problem;

(iii) forming an energy function for the labeling problem, that energy function comprising a plurality of terms each relating to one or more criteria to be used in forming the collage;

(iv) specifying at least one of the terms of the energy function to relate to amounts of information available in the input images and to similarity of input images;

(v) using an optimization process to optimize the energy function such that at least one possible labeling is found for the collage;

(vi) using the labeling found for the collage to form the collage using an image blending process and outputting the collage.

14. A method as claimed in claim 13 which further comprises specifying another of the terms of the energy function to penalize transitions between images on the basis of a measure of mismatch across the boundary between two input images.

15. A method as claimed in claim 13 which further comprises receiving information about objects of class sky in the input images.

16. A method as claimed in claim 13 which further comprises specifying another of the terms of the energy function to take object class information into account.

17. A method as claimed in claim 16 which comprises receiving information about objects of class face and specifying the term of the energy function which takes object class information into account such that that term tends to ensure that if a face is included, it is included as a whole.

18. A method as claimed in claim 13 which further comprises specifying another of the terms of the energy function to take into account a local entropy measure for regions of input images.

19. One or more device-readable media with device-executable instructions for performing a method, the method comprising:

(i) receiving a plurality of input images from which it is required to automatically form a collage;

(ii) specifying formation of the collage from the input images as a labeling problem;

(iii) forming an energy function for the labeling problem, that energy function comprising a plurality of terms each relating to one or more criteria to be used in forming the collage;

(iv) specifying one or more constraints to be applied to the energy function;

(v) using a multi-stage optimization process to optimize the energy function taking into account the specified constraints such that at least one possible labeling is found for the collage;

(vi) using the labeling found for the collage to form the collage using an image blending process and outputting the collage.

20. One or more device-readable media as claimed in claim 19 wherein the multi-stage optimization process comprises:

selecting a region of interest for each input image; and

applying an optimization process to pack as many of the regions of interest as possible within a width and height of the collage provided that as many collage pixels as possible are covered by some input image and provided that as few of the regions of interest as possible overlap in the collage.