Representative image selection based on hierarchical clustering

• US 7,869,658 B2
• Filed: 02/22/2007
• Issued: 01/11/2011
• Est. Priority Date: 10/06/2006
• Status: Expired due to Fees

• Current Assignee: Monument Peak Ventures, LLC (Dominion Harbor Enterprises, LLC)
• Original Assignee: Eastman Kodak Company
• Inventors: Loui, Alexander C., Blose, Andrew C.
• Primary Examiner(s): Ahmed; Samir A.
• Assistant Examiner(s): HU, FRED H.
• Application Number:
  US11/677,617
• Publication Number:
  US 20080205772A1
• Time in Patent Office: 1,419 Days
• Field of Search: 382/224, 382/225, 382/228
• US Class Current: 382/224
• 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:

using a computer to provide the steps of;

classifying the image records spatio-temporally into groups wherein the classifying further comprises clustering the image records into events and then into subevents, wherein the groups are the subevents;

partitioning the image records of each of the groups into a set of clusters, the partitioning being between a hierarchy of three feature clusters and a remainder cluster and being based on a predetermined plurality of saliency features, the feature clusters each having one of the saliency features, and the remainder cluster lacking the saliency features, the clustering further comprises, in order the steps of;

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

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

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

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

designating a representative image of each of the groups from the respective image records, the designating being 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.

2. 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.

3. The method of claim 1 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.

4. The method of claim 3 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.

5. The method of claim 4 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.

6. The method of claim 5 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.

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

8. The method of claim 6 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.

9. The method of claim 8 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.

10. The method of claim 8 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.