Finding iconic images

• US 8,542,950 B2
• Filed: 06/02/2009
• Issued: 09/24/2013
• Est. Priority Date: 06/02/2009
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Berg, Tamara L., Berg, Alexander
• Primary Examiner(s): Mehta, Bhavesh
• Assistant Examiner(s): Dunphy, David F
• Application Number:
  US12/476,711
• Publication Number:
  US 20100303342A1
• Time in Patent Office: 1,575 Days
• Field of Search: None
• US Class Current: 382/305
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content

Abstract

Iconic images for a given object or object category may be identified in a set of candidate images by using a learned probabilistic composition model to divide each candidate image into a most probable rectangular object region and a background region, ranking the candidate images according to the maximal composition score of each image, removing non-discriminative images from the candidate images, clustering highest-ranked candidate images to form clusters, wherein each cluster includes images having similar object regions according to a feature match score, selecting a representative image from each cluster as an iconic image of the object category, and causing display of the iconic image. The composition model may be a Naïve Bayes model that computes composition scores based on appearance cues such as hue, saturation, focus, and texture. Iconic images depict an object or category as a relatively large object centered on a clean or uncluttered contrasting background.

Claims

1. A method comprising:

receiving, at a computing device, a plurality of candidate images;

using, via the computing device, a learned probabilistic composition model to divide each candidate image in the plurality of candidate images into a most probable rectangular object region and a background region, wherein the most probable rectangular object region has a maximal composition score from possible composition scores computed according to the composition model for possible divisions of the candidate image into object and background regions, each possible composition score is based upon at least one image feature cue computed over the object and background regions, and the composition model is trained on a set of images independent of the plurality of candidate images;

ranking, via the computing device, the plurality of candidate images according to the maximal composition score of the most probable rectangular object region of each image determined using the learned probabilistic composition model;

removing, via the computing device, non-discriminative images from the plurality of candidate images;

clustering, via the computing device, a plurality of highest-ranked images from the plurality of candidate images ranked according to the maximal composition score of the most probable rectangular object region of each image determined using the learned probabilistic composition model to form a plurality of clusters, wherein each cluster includes a plurality of images selected from the plurality of highest-ranked images and having similar object regions according to a feature match score;

selecting, via the computing device, a representative image from each cluster as an iconic image representative of an object category; and

causing, via the computing device, display of the iconic image.

2. The method of claim 1, wherein removing non-discriminative images from the plurality of candidate images comprises:

comparing each candidate image in the plurality of candidate images to a plurality of highest-ranked images from the plurality of candidate images using a similarity measure based upon the feature match score, wherein the feature match score is spatially restricted to the object regions; and

removing each candidate image for which more than a predetermined percentage of images most similar to the candidate image are in another category different from the object category.

3. The method of claim 1, wherein the composition model is a Naive Bayes model.

4. The method of claim 1, wherein the at least one image feature cue comprises hue, saturation, value, focus, texture, or a combination thereof.

5. The method of claim 4, wherein the hue, saturation, value, or a combination thereof is modeled as at least one histogram with a predetermined number of uniformly-spaced bins.

6. The method of claim 4, wherein the focus is computed as a ratio of high pass energy to low pass energy.

7. The method of claim 4, wherein the texture is modeled as a histogram of total response to a predetermined number of bar and spot features.

8. The method of claim 1, wherein the composition model is trained using a plurality of hand-labeled training images, wherein a correct layout and an incorrect layout are labeled for each training image.

9. The method of claim 1, wherein probability models for both good and bad layouts are trained for each image cue.

10. The method of claim 9, wherein the probability models represent, for both good and bad layouts, the distribution over contrast values computed using Chi-Squared distance between object and background histograms, the distribution over object histograms, the distribution over background histograms, or a combination thereof.

11. The method of claim 1, wherein the features for possible divisions are computed using summed area tables.

12. The method of claim 1, wherein clustering comprises using a k-medoids clustering method based upon geometric blur features computed within the object regions to find similar-looking object regions from the plurality of highest-ranked images, and selecting the representative image from each cluster comprises selecting the medoid of the cluster.

13. The method of claim 1, wherein the plurality of highest-ranked images comprises a predetermined number of the highest-ranked images.

14. The method of claim 1, wherein the plurality of highest-ranked images comprises images having a maximal composition score greater than a predetermined value.

15. A computer system comprising:

a memory for storing computer-executable instructions; and

a processor for executing the instructions, the instructions for;

receiving a plurality of candidate images;

using a learned probabilistic composition model to divide each candidate image in the plurality of candidate images into a most probable rectangular object region and a background region, wherein the most probable rectangular object region has a maximal composition score from possible composition scores computed according to the composition model for possible divisions of the candidate image into object and background regions, each possible composition score is based upon at least one image feature cue computed over the object and background regions, and the composition model is trained on a set of images independent of the plurality of candidate images;

ranking the plurality of candidate images according to the maximal composition score of the most probable rectangular object region of each image determined using the learned probabilistic composition model;

removing non-discriminative images from the plurality of candidate images;

clustering a plurality of highest-ranked images from the plurality of candidate images ranked according to the maximal composition score of the most probable rectangular object region of each image determined using the learned probabilistic composition model to form a plurality of clusters, wherein each cluster includes a plurality of images selected from the plurality of highest-ranked images and having similar object regions according to a feature match score;

selecting a representative image from each cluster as an iconic image representative of an object category; and

causing display of the iconic image.

16. The system of claim 15, wherein the instructions for removing non-discriminative images from the plurality of candidate images comprise:

comparing each candidate image in the plurality of candidate images to a plurality of highest-ranked images from the plurality of candidate images using a similarity measure based upon the feature match score, wherein the feature match score is spatially restricted to the object regions; and

removing each candidate image for which more than a predetermined percentage of images most similar to the candidate image are in another category different from the object category.

17. The system of claim 15, wherein the composition model is a Naive Bayes model.

18. The system of claim 15, wherein the at least one image feature cue comprises hue, saturation, value, focus, texture, or a combination thereof.

19. The system of claim 18, wherein the hue, saturation, value, or a combination thereof is modeled as at least one histogram with a predetermined number of uniformly-spaced bins.

20. The system of claim 18, wherein the focus is computed as a ratio of high pass energy to low pass energy.

21. The system of claim 18, wherein the texture is modeled as a histogram of total response to a predetermined number of bar and spot features.

22. The system of claim 15, wherein the composition model is trained using a plurality of hand-labeled training images, wherein a correct layout and an incorrect layout are labeled for each training image.

23. The system of claim 15, wherein probability models for both good and bad layouts are trained for each image cue.

24. The system of claim 23, wherein the probability models represent, for both good and bad layouts, the distribution over contrast values computed using Chi-Squared distance between object and background histograms, the distribution over object histograms, the distribution over background histograms, or a combination thereof.

25. The system of claim 15, wherein the features for possible divisions are computed using summed area tables.

26. The system of claim 15, wherein the instructions for clustering comprises using a k-medoids clustering method based upon geometric blur features computed within the object regions to find similar-looking object regions from the plurality of highest-ranked images, and selecting the representative image from each cluster comprises selecting the medoid of the cluster.

27. The system of claim 15, wherein the plurality of highest-ranked images comprises a predetermined number of the highest-ranked images.

28. The system of claim 15, wherein the plurality of highest-ranked images comprises images having a maximal composition score greater than a predetermined value.

29. A computer readable storage medium comprising computer-executable instructions tangibly stored thereon, which when executed by a processor, perform a method comprising:

receiving a plurality of candidate images;

using a learned probabilistic composition model to divide each candidate image in the plurality of candidate images into a most probable rectangular object region and a background region, wherein the most probable rectangular object region has a maximal composition score from possible composition scores computed according to the composition model for possible divisions of the candidate image into object and background regions, each possible composition score is based upon at least one image feature cue computed over the object and background regions, and the composition model is trained on a set of images independent of the plurality of candidate images;

ranking the plurality of candidate images according to the maximal composition score of the most probable rectangular object region of each image determined using the learned probabilistic composition model;

removing non-discriminative images from the plurality of candidate images;

clustering a plurality of highest-ranked images from the plurality of candidate images ranked according to the maximal composition score of the most probable rectangular object region of each image determined using the learned probabilistic composition model to form a plurality of clusters, wherein each cluster includes a plurality of images selected from the plurality of highest-ranked images and having similar object regions according to a feature match score;

selecting a representative image from each cluster as an iconic image representative of the object category; and

causing display of the iconic image.

30. The computer readable storage medium of claim 29, wherein removing non-discriminative images from the plurality of candidate images comprises:

comparing each candidate image in the plurality of candidate images to a plurality of highest-ranked images from the plurality of candidate images using a similarity measure based upon the feature match score, wherein the feature match score is spatially restricted to the object regions; and

removing each candidate image for which more than a predetermined percentage of images most similar to the candidate image are in another category different from the object category.

31. The computer readable storage medium of claim 29, wherein the composition model is a Naive Bayes model.

32. The computer readable storage medium of claim 29, wherein the at least one image feature cue comprises hue, saturation, value, focus, texture, or a combination thereof.

33. The computer readable storage medium of claim 32, wherein the hue, saturation, value, or a combination thereof is modeled as at least one histogram with a predetermined number of uniformly-spaced bins.

34. The computer readable storage medium of claim 32, wherein the focus is computed as a ratio of high pass energy to low pass energy.

35. The computer readable storage medium of claim 32, wherein the texture is modeled as a histogram of total response to a predetermined number of bar and spot features.

36. The computer readable storage medium of claim 29, wherein the composition model is trained using a plurality of hand-labeled training images, wherein a correct layout and an incorrect layout are labeled for each training image.

37. The computer readable storage medium of claim 29, wherein probability models for both good and bad layouts are trained for each image cue.

38. The computer readable storage medium of claim 37, wherein the probability models represent, for both good and bad layouts, the distribution over contrast values computed using Chi-Squared distance between object and background histograms, the distribution over object histograms, the distribution over background histograms, or a combination thereof.

39. The computer readable storage medium of claim 29, wherein the features for possible divisions are computed using summed area tables.

40. The computer readable storage medium of claim 29, wherein clustering comprises using a k-medoids clustering computer readable medium based upon geometric blur features computed within the object regions to find similar-looking object regions from the plurality of highest-ranked images, and

selecting the representative image from each cluster comprises selecting the medoid of the cluster.

41. The computer readable storage medium of claim 29, wherein the plurality of highest-ranked images comprises a predetermined number of the highest-ranked images.

42. The computer readable storage medium of claim 29, wherein the plurality of highest-ranked images comprises images having a maximal composition score greater than a predetermined value.