Methods and apparatuses for generating thumbnail summaries for image collections

• US 8,599,219 B2
• Filed: 08/25/2010
• Issued: 12/03/2013
• Est. Priority Date: 09/18/2009
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Shechtman, Elya, Goldman, Daniel R., Jacobs, David E.
• Primary Examiner(s): Amini, Javid A
• Application Number:
  US12/868,540
• Publication Number:
  US 20130120454A1
• Time in Patent Office: 1,196 Days
• Field of Search: 345/635
• US Class Current: 345/635
• CPC Class Codes: G06F 16/54 Browsing; Visualisation therefor
• CPC Class Codes: G06T 11/00 2D [Two Dimensional] image generation
• CPC Class Codes: G06T 15/503 Blending, e.g. for anti-aliasing
• CPC Class Codes: G06T 3/04 Context-preserving transformations, e.g. by using an importance map panospheric to cylindrical image transformations G06T3/12
• CPC Class Codes: G06T 3/4038 Image mosaicing, e.g. composing plane images from plane sub-images

Abstract

Methods and apparatuses for generating thumbnail summaries for image collections are described. Thumbnails summaries may be representative of the image collection while being disjoint from each other. In some embodiments, a method may sample crops from some or all images in an image collection. From these candidate crops, the method may select representative but disjoint crops. In some embodiments, a desired representativeness and/or disjointedness of the candidate crops may be defined by a user. The method may then generate and/or select thumbnail summaries for the collection of images based at least in part on the selected candidate crops.

Claims

1. A method, comprising:

performing, by one or more computing devices;

sampling crops from images in a collection of images;

generating candidate crops from the sampled crops;

for each candidate crop;

determining a completeness metric; and

determining a disjointedness metric;

evaluating the completeness metric or the disjointedness metric of each candidate crop relative to the completeness metric or the disjointedness metric of another crop from among a set of candidate crops;

responsive to the evaluating, selecting an optimal set of representative but disjoint crops from the candidate crops; and

generating a set of summarizing thumbnails for the collection of images based on the selected optimal set of representative but disjoint crops.

2. The method of claim 1, further comprising computing a patch distance from at least one image in the collection of images to at least one candidate crop prior to the selecting operation.

3. The method of claim 1:

wherein for a given one of the candidate crops, the completeness metric indicates a degree of the given candidate crop to represent the visual information of the images in the collection;

wherein for the given candidate crop, the disjointedness metric indicates an unlikeness of the given candidate crop with respect to the another crop of the set of candidate crops; and

further comprising until a stopping criterion is satisfied;

adding a given candidate crop to the optimal set of representative but disjoint crops based, at least in part, on the given candidate crop'"'"'s completeness and disjointedness metrics.

4. The method of claim 3, wherein the stopping criterion includes a desired number of thumbnails within the set of summarizing thumbnails.

5. The method of claim 4, wherein the desired number of thumbnails is determined based on a number of images in the collection of images.

6. The method of claim 1, wherein the selecting comprises selecting a candidate crop that optimizes an energy function that combines completeness and disjointedness metrics.

7. The method of claim 1, wherein the sampling operation comprises sampling crops from images at varying scales.

8. The method of claim 7, wherein the varying scales are determined based, at least in part, on a desired thumbnail size for a thumbnail within the set of summarizing thumbnails.

9. A non-transitory computer-readable storage medium having instructions stored thereon that, upon execution by a computer system, cause the computer system to perform operations comprising:

identifying a set of summarizing thumbnails associated with a collection of images;

sampling subsets of pixels from a plurality of images within the collection of images;

generating a plurality of candidate crops based, at least in part, on the sampled subsets of pixels;

calculating, for each of the plurality of candidate crops, a value based on a representativeness metric and a distinctiveness metric of each of the plurality of candidate crops;

selecting a candidate crop among the plurality of candidate crops, based, at least in part, on the value based on the representativeness metric and the distinctiveness metric of each of the plurality of candidate crops; and

generating a new thumbnail based, at least in part, on the selected candidate crop.

10. The non-transitory computer-readable storage medium of claim 9, the operations further comprising:

determining a number of thumbnails to be added to the set of summarizing thumbnails; and

repeating at least the generating operation until the number of thumbnails to be added is reached.

11. The non-transitory computer-readable storage medium of claim 9, the operations further comprising calculating the representativeness metric for a candidate crop based, at least in part, on an additional completeness that the candidate crop provides with respect to the collection of images.

12. The non-transitory computer-readable storage medium of claim 11, the operations further comprising calculating the representativeness metric based, at least in part, on patch distance measurements, wherein at least one patch distance measurement receives a weight based, at least in part, on a face detection.

13. The non-transitory computer-readable storage medium of claim 9, the operations further comprising calculating the distinctiveness metric for a candidate crop based, at least in part, on an unlikeness that the candidate crop provides with respect to the set of summarizing thumbnails.

14. The non-transitory computer-readable storage medium of claim 13, the operations further comprising calculating the distinctiveness metric based, at least in part, on a patch distance measurement.

15. The non-transitory computer-readable storage medium of claim 9, wherein the calculating operation comprises combining the representativeness metric and distinctiveness metric of each of the plurality of candidate crops for each of the plurality of candidate crops.

16. The non-transitory computer-readable storage medium of claim 15, wherein the combining further comprises assigning a weight to the representativeness metric.

17. The non-transitory computer-readable storage medium of claim 16, the operations further comprising:

receiving a user-selected representativeness weight; and

applying the user-selected representativeness weight to the representativeness metric in connection with the combining operation.

18. The non-transitory computer-readable storage medium of claim 9, wherein the sampling operation comprises sampling each of the subsets of pixels with a size selected by a user.

19. The non-transitory computer-readable storage medium of claim 18, wherein the sampling operation comprises sampling more than one subset of pixels for each of the plurality of images within the collection of images.

20. A system comprising:

one or more processors; and

memory storing instructions that, responsive to execution by the one or more processors, cause the one or more processors to perform operations comprising;

sampling a first subset of pixels from a collection of images;

calculating, for the first subset of pixels, a first value representing a combination of a first completeness metric with a first disjointedness metric, the first completeness metric indicating the first subset of pixels representativeness relative to the collection of images and the first disjointedness metric indicating the first subset of pixels unlikeness relative to the collection of images;

sampling a second subset of pixels from the collection of images;

calculating, for the second subset of pixels, a second value representing a combination of a second completeness metric with a second disjointedness metric; and

responsive to the second value being greater than the first value, creating a thumbnail based, at least in part, on the second subset of pixels.

21. The system of claim 20, wherein the first subset of pixels comprises a first image within the collection of images and the second subset of pixels comprises a second image within the collection of images.

22. The system of claim 21, wherein the first subset of pixels comprises a cropped portion of a first image within the collection of images and the second subset of pixels comprises a cropped portion of a second image within the collection of images.

23. The system of claim 22, wherein the first subset of pixels comprises a cropped portion of a first image within the collection of images and the second subset of pixels comprises another cropped portion of the first image within the collection of images.

24. The system of claim 23, the operations further comprising:

sampling a third subset of pixels from the collection of images;

calculating, for the third subset of pixels, a third value representing a combination of a third completeness metric with third disjointedness metric; and

in response to the third value being greater than the first value, creating a third thumbnail based, at least in part, on the third subset of pixels.