REPRESENTATIVE IMAGE SELECTION BASED ON HIERARCHICAL CLUSTERING

• US 20080205772A1
• Filed: 02/22/2007
• Published: 08/28/2008
• Est. Priority Date: 10/06/2006
• Status: Active Grant

• Current Assignee: Monument Peak Ventures, LLC (Dominion Harbor Enterprises, LLC)
• Original Assignee: Eastman Kodak Company
• Inventors: Loui, Alexander C., Blose, Andrew C.
• Granted Patent: US 7,869,658 B2
• Time in Patent Office: Days
• US Class Current: 382/225
• CPC Class Codes: G06F 16/51 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06V 20/40 in video content extracting overlay text G06V20/62; video retrieval G06F16/70; processing of video elementary streams in video servers H04N21/234; processing of video elementary streams in video clients H04N21/44

Abstract

In a computer-mediated method for providing representative images, image records are classified spatio-temporally into groups. In each group, image records are partitioned into clusters and the hierarchically highest cluster is ascertained. The partitioning is between a hierarchy of feature clusters and a remainder cluster, based on a predetermined plurality of saliency features. Feature clusters each have one or more of the saliency features. The remainder cluster lacks the saliency features. Feature clusters are each exclusive of the saliency features of any higher clusters in the hierarchy and non-exclusive of the saliency features of any lower feature clusters in the hierarchy. A representative image of each group is designated from respective image records based on: the respective saliency feature of the highest cluster when the highest cluster is a feature cluster and independent of the saliency features when the highest cluster is the remainder cluster.

Claims

1. A computer-mediated method for providing representative images in a collection, the image records each including one or more captured digital images, the method comprising the steps of:

classifying the image records spatio-temporally into groups;

partitioning said image records of each of said groups into a set of clusters, said partitioning being between a hierarchy of two or more feature clusters and a remainder cluster and being based on a predetermined plurality of saliency features, said feature clusters each having one or more of said saliency features, said remainder cluster lacking said saliency features, said feature clusters each being exclusive of the saliency features of any higher clusters in said hierarchy and non-exclusive of the saliency features of any lower feature clusters in said hierarchy;

ascertaining the hierarchically highest said cluster in each of said sets to provide highest clusters; and

designating a representative image of each of said groups from the respective image records, said designating being based on the respective said saliency feature of said highest cluster when said highest cluster is a feature cluster and independent of said saliency features when said highest cluster is said remainder cluster.

2. The method of claim 1 wherein said partitioning further comprises repeatedly two-way clustering said image records of each said group in a feature cluster and a non-feature cluster, wherein a final said non-feature cluster is said remainder cluster.

3. The method of claim 1 wherein when said highest cluster on one of said groups is said remainder cluster, said designating is from one or more respective image records at a spatio-temporal midpoint of said cluster.

4. The method of claim 1 wherein said classifying further comprises clustering the image records into events and said events into subevents, wherein said groups are said subevents.

5. The method of claim 4 wherein said method further comprises designating a representative image of each of said events from said designated representative images of the respective said subevents.

6. The method of claim 4 wherein said determining further comprises:

finding in each said event, one of the respective said subevents having a largest number of said image records; and

setting the representative image of said found subevent as the representative image of the respective said event.

7. The method of claim 4 wherein said saliency features are selected from the group consisting of:

presence of one or more people, presence of one or more faces, presence of a main subject, main subject colorfulness, main subject centrality, presence of duplicate image records, and image usage information.

8. The method of claim 4 wherein said clustering further comprises, in order, the steps of:

(a) clustering said image records of each of said subevents between a first said feature cluster and a first said non-feature cluster based on a face metric;

(b) when said first non-feature cluster includes one or more of said image records, clustering respective said image records of said first non-feature cluster between a second said feature cluster and a second said non-feature cluster based on a main subject metric;

(c) when said second non-feature cluster includes one or more of said image records, clustering respective said image records of said second non-feature cluster between a third said feature cluster and said remainder cluster based on a duplicate image records metric.

9. The method of claim 8 wherein said metrics are of the saliency features:

presence of one or more faces, presence of a main subject, and presence of duplicate image records, respectively, and said clustering steps each further comprise determining whether the respective said metric exceeds a respective predetermined threshold.

10. The method of claim 9 wherein, when said highest cluster is said first said feature cluster, said designating further comprises:

evaluating facial area of said faces in each of said image records of said highest cluster; and

selecting said representative image from one of said image records having a maximum facial area.

11. The method of claim 10 wherein, when said highest cluster is said first said feature cluster, said designating further comprises:

recognizing one or more of said faces in said image records of said highest cluster; and

selecting said representative image from one of said image records having one or more of said recognized faces.

12. The method of claim 11 wherein, when said highest cluster is said second said feature cluster, said designating further comprises:

determining relative sizes of said main subjects of respective said image records of said highest cluster; and

selecting said representative image from one of said image records having said main subject in a middle range of said relative sizes.

13. The method of claim 12 wherein said selecting steps each further comprise considering image quality of respective said image records.

14. The method of claim 12 wherein, when said highest cluster is said third said feature cluster, said designating further comprises:

identifying one or more sets of two or more duplicate image records in said highest cluster; and

selecting said representative image from one of said duplicate images.

15. The method of claim 14 wherein said one of said duplicate images is one of the images of the respective said set having a greatest number of said duplicate images in the respective said subevent.

16. The method of claim 14 wherein, when said highest cluster is said remainder cluster, said designating further comprises:

determining one or more of said image records at a spatio-temporal midpoint of said highest cluster; and

selecting said image record from said one or more image records at said spatio-temporal midpoint as said representative image of said remaining group.

17. A computer program product for providing representative images in a collection, the image records each including one or more captured digital images, the computer program product comprising computer readable storage medium having a computer program stored thereon for performing the steps of:

classifying the image records spatio-temporally into groups;

partitioning said image records of each of said groups into a set of clusters, said clustering being between a hierarchy of two or more feature clusters and a remainder cluster and being based on a predetermined plurality of saliency features, said feature clusters each having a different primary saliency feature of said plurality, said remainder cluster lacking said saliency features of said plurality, said feature clusters each being exclusive of said primary saliency features of any higher clusters in said hierarchy and non-exclusive of said primary saliency features of any lower feature clusters in said hierarchy;

ascertaining the hierarchically highest said cluster in each of said sets to provide highest clusters; and

designating a representative image of each of said groups from the respective image records, said designating being based on the respective said peak saliency feature of said highest cluster when said highest cluster is a feature cluster and independent of said saliency features when said highest cluster is said remainder cluster.

18. A system for indexing image records in a collection, the image records each including one or more digital images, comprising:

means for classifying the image records spatio-temporally into groups;

means for partitioning said image records of each of said groups into a set of clusters, said clustering being between a hierarchy of two or more feature clusters and a remainder cluster and being based on a predetermined plurality of saliency features, said feature clusters each having a different primary saliency feature of said plurality, said remainder cluster lacking said saliency features of said plurality, said feature clusters each being exclusive of said primary saliency features of any higher clusters in said hierarchy and non-exclusive of said primary saliency features of any lower feature clusters in said hierarchy;

means for ascertaining the hierarchically highest said cluster in each of said sets to provide highest clusters;

means for designating a representative image of each of said groups from the respective image records, said designating being based on the respective said peak saliency feature of said highest cluster when said highest cluster is a feature cluster and independent of said saliency features when said highest cluster is said remainder cluster; and

a display displaying said representative images as an index of said events and said subevents.