Image tapestry

• US 7,653,261 B2
• Filed: 08/26/2005
• Issued: 01/26/2010
• Est. Priority Date: 11/12/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kumar, Sanjiv, Kolmogorov, Vladimir, Rother, Carsten Curt Eckard, Blake, Andrew
• Primary Examiner(s): Kassa; Yosef
• Application Number:
  US11/213,080
• Publication Number:
  US 20060104542A1
• Time in Patent Office: 1,614 Days
• Field of Search: 382/284, 382/294, 382/305, 358/540, 358/450, 358/453
• 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

An output image formed from at least a portion of one or more input images may be automatically synthesized as a tapestry image. To determine which portion or region of each input image will be used in the image tapestry, the regions of each image may be labeled by one of a plurality of labels. The multi-class labeling problem of creating the tapestry may be resolved such that each region in the tapestry is constructed from one or more salient input image regions that are selected and placed such that neighboring blocks in the tapestry satisfy spatial compatibility. This solution may be formulated using a Markov Random Field and the resulting tapestry energy function may be optimized in any suitable manner. To optimize the tapestry energy function, an expansion move algorithm for energy functions may be generated to apply to non-metric hard and/or soft constraints.

Claims

1. A method comprising:

a) receiving at least one input image;

b) identifying at least two input image regions of the at least one input image, each input image region including a portion of the at least one input image;

c) determining an objective function including a quality of each of the at least two input image regions;

d) optimizing the objective function with respect to a tapestry image containing the at least two input image regions based on the optimizing;

e) storing the optimized tapestry image in a data store of a computing device; and

f) displaying an output image comprising the optimized tapestry image on a display of the computing device.

2. The method of claim 1, wherein the objective function includes a measure of spatial coherence in the tapestry image based on a likelihood of placement of one or more neighboring input image regions as tapestry neighboring regions in the tapestry image.

3. The method of claim 1, wherein the objective function includes a measure of region uniqueness for reducing redundant input image regions in the tapestry image.

4. The method of claim 1, wherein the objective function includes a measure of localization of placement of an input image region in the tapestry image based on a preference for placing a depicted scene in the input image region at a predetermined area of the tapestry image.

5. The method of claim 1, wherein the objective function includes a measure of appearance coherence for placing a first input image region next to a second input image region based on an image characteristic of both the first input image region and the second input image region.

6. The method of claim 1, wherein the objective function includes a measure of image-shift uniqueness for preventing the placement of two input image regions in the tapestry which are from the same input image and have an identical shift.

7. The method of claim 1, wherein the objective function includes a measure of a detected object within an input image region.

8. The method of claim 1, wherein the objective function includes a measure of an image characteristic class uniqueness of an input image region for reducing a plurality of input image regions from different input images and having similar image characteristics.

9. The method of claim 1, wherein forming the objective function includes using a Markov random field.

10. The method of claim 1, wherein optimizing includes using a graph cut based expansion move algorithm.

11. The method of claim 10, wherein the objective function includes at least one non-metric hard term.

12. The method of claim 10, wherein the objective function includes at least one non-metric soft term.

21. One or more computer readable storage media having computer executable instructions causing a computer to perform the method of claim 1.

13. A method comprising:

a) receiving at least two unregistered input images;

b) identifying at least two input image regions of the at least two unregistered input images, each input image region including a portion of one of the at least two input images;

c) determining an objective function for evaluating a quality of each of the at least two input image regions;

d) optimizing the objective function with respect to a tapestry image containing the at least two input image regions based on the optimizing;

e) storing the optimized tapestry image in a data store of a computing device; and

f) displaying an output image comprising the optimized tapestry image on a display of the computing device.

14. The method of claim 13, wherein the objective function includes a measure of region coherence for forming a cluster of two or more input image regions from a single input image for placement in the tapestry image and includes a measure of region uniqueness for reducing redundant input image regions in the tapestry image.

15. The method of claim 13, wherein the objective function includes one of a group comprising a measure of localization of placement of an input image region in the tapestry image based on a preference for placing a depicted scene in the input image region at a predetermined area of the tapestry image, a measure of appearance coherence for placing a first input image region next to a second input image region based on an image characteristic of both the first input image region and the second input image region, a measure of image-shift uniqueness for placing a first input image region from a first input image and a second input image region from the first input image with an identical image shift in the tapestry image, a measure of a detected object within an input image region, a measure of an image characteristic class uniqueness of an input image region for reducing a plurality of input image regions from different input images and having similar image characteristics.

16. The method of claim 15, wherein optimizing includes using a graph cut based expansion move algorithm, and the objective functions includes a non-metric hard term and/or a non-metric soft term.

22. One or more computer readable storage media having computer executable instructions causing a computer to perform the method of claim 13.

17. One or more computer readable storage media having computer executable instructions for performing steps comprising:

a) receiving a plurality of input images;

b) dividing each input image of the plurality of input images into a plurality of regions;

c) selecting at least two salient regions from the plurality of regions;

d) applying a region coherence constraint to at least one of the at least two salient regions to cluster a plurality of salient image regions from a single input image;

e) applying a region uniqueness constraint to the at least two salient regions to reduce duplication of an input image region; and

f) optimizing a tapestry image containing the at least two salient regions based on the application of the region coherence constraint and the region uniqueness constraint.

18. The computer readable storage media of claim 17, wherein applying the region coherence constraint includes using a Markov random field to create a cluster of two or more regions for placement together in the tapestry image.

19. The computer readable storage media of claim 18, further comprising applying an additional constraint, the additional constraint being member of a group consisting essentially of a localization constraint on placement of at least one salient region based on a color of the at least one salient region;

an appearance dependent Markov random field to the at least two salient regions to place the at least two salient regions in the tapestry image;

an image-shift uniqueness constraint to place the at least two salient regions in the tapestry image;

a detected object constraint for detecting an object depicted in at least one of the salient regions and in an adjacent region of an input image to form the tapestry image; and

a class uniqueness constraint on the at least two salient regions to form the tapestry image.

20. The computer readable storage media of claim 19, wherein optimizing the tapestry image includes using a graph cut algorithm.