Multi-tiered image clustering by event

• US 7,643,686 B2
• Filed: 08/04/2005
• Issued: 01/05/2010
• Est. Priority Date: 11/17/2004
• Status: Expired due to Fees

• Current Assignee: Monument Peak Ventures, LLC (Dominion Harbor Enterprises, LLC)
• Original Assignee: Eastman Kodak Company
• Inventors: Loui, Alexander C., Kraus, Bryan D.
• Primary Examiner(s): Mehta; Bhavesh M
• Assistant Examiner(s): ZARKA, DAVID PETER
• Application Number:
  US11/197,243
• Publication Number:
  US 20060104520A1
• Time in Patent Office: 1,615 Days
• Field of Search: 382/225
• US Class Current: 382/225
• CPC Class Codes: G06F 16/55 Clustering; Classification
• CPC Class Codes: G06F 16/58 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually

Abstract

In a method for classifying a sequence of records into events based upon feature values, such as time and/or location, associated with each of the records, feature differences between consecutive records are determined. The feature differences are ranked. A sequence of three or more clusters of feature differences is computed. The clusters are arranged in decreasing order of relative likelihood of respective feature differences representing separations between events. The records can be inclusive of images.

Claims

1. A method for classifying a sequence of digital records into events based upon feature values associated with each of said digital records, said method comprising using a processor to perform the steps of:

determining feature differences between consecutive said digital records;

ranking said feature differences to provide an unclustered feature difference set;

computing a sequence of three or more mutually exclusive feature difference clusters, each feature difference cluster corresponding to a different probability of representing separations between events, wherein at least one boundary between feature difference clusters is constrained to fall within a specified range, the feature difference clusters being computed using a 2-means event clustering algorithm to determine at least one of said feature difference clusters and using a different clustering algorithm based upon a variance metric to determine at least one other of said feature difference clusters; and

classifying the sequence of digital records into events using the feature differences that fall into one or more of the feature difference clusters.

2. The method of claim 1 further comprising designating respective said feature differences in the cluster lowest in said decreasing order as being within events and designating respective said feature differences in the feature difference cluster highest in said decreasing order as being between events.

3. The method of claim 2 further comprising designating each of said feature differences in one or more intermediate feature difference clusters between said lowest and highest feature difference clusters as being between events.

4. The method of claim 3 further comprising analyzing respective said feature differences in at least one of said intermediate feature difference clusters differently than respective said feature differences in said highest feature difference cluster.

5. The method of claim 2 further comprising designating respective said feature differences in at least one intermediate feature difference cluster between said lowest and highest feature difference clusters as being event subdivisions.

6. The method of claim 1 further comprising stopping said computing responsive to a predetermined stopping criterion.

7. The method of claim 1 further comprising, during said computing of said sequence:

repeatedly presenting event organizations associated with said feature difference clusters to a user; and

allowing said user to stop said computing following each said presenting when the user determines that the events have been sufficiently distinguished.

8. A computer program product for image classification, the computer program product comprising computer readable storage medium having a computer program stored thereon for performing the steps of claim 1.

9. A method for classifying a sequence of digital records into events based upon feature values associated with each of said digital records, said method comprising using a processor to perform the steps of:

determining differences between the feature values of consecutive said records to provide feature differences;

ranking said feature differences to provide an unclustered feature difference set;

sequentially partitioning a plurality of feature difference clusters of said feature differences from said unclustered feature difference set to form at least three feature difference clusters, said feature difference clusters being mutually exclusive, said partitioning being in decreasing order of relative likelihood of respective said feature differences representing separations between events, wherein at least one partition boundary between feature difference clusters is constrained to fall within a specified range, said partitioning comprising using a 2-means event clustering algorithm to partition at least one of said feature difference clusters and using a difference clustering algorithm based upon a variance metric to partition at least one other of said feature difference clusters; and

classifying the sequence of digital records into events using the feature differences that fall into one or more of the feature difference clusters.

10. The method of claim 9 further comprising designating each of said feature differences in at least two of said feature difference clusters as being between events.

11. The method of claim 10 further comprising analyzing respective said feature differences of said at least two feature difference clusters differently.

12. The method of claim 11 wherein said analyzing further comprises computing feature difference subclusters.

13. The method of claim 9 further comprising designating each of said feature differences in a first partitioned of said feature difference clusters as being between events and each of said feature differences in at least one other of said feature difference clusters as being event subdivisions.

14. The method of claim 9 further comprising continuing said partitioning until a predetermined stopping criterion is reached.

15. The method of claim 14 wherein said stopping criterion is a predetermined value of an event occurrence rate.

16. The method of claim 14 wherein said stopping criterion is a limit feature difference.

17. The method of claim 16 wherein said feature differences are time differences and said limit feature difference is a minimum time difference in the range of 8 to 60 minutes.

18. The method of claim 17 wherein said limit feature difference is a minimum time difference of 16 minutes.

19. The method of claim 9 wherein said digital records each have a single image or image sequence.

20. A method for classifying a database of digital records into events, said digital records each having an associated feature value, said features values being ordinal and having a dimensionality of one or more, said records being ranked in order of respective said feature values, said method comprising using a processor to perform the steps of:

determining feature value differences between consecutive said digital records;

ranking said feature value differences to provide an unclustered feature difference set;

calculating an boundary from said feature value differences of said unclustered feature difference set, said boundary defining a feature difference cluster of said differences of said unclustered feature difference set relatively more likely to represent separations between events, said boundary redefining said unclustered feature difference set to exclude said feature difference cluster, said boundary being constrained to fall within a specified range;

repeating said calculating at least once to form additional feature difference clusters; and

classifying the sequence of digital records into events using the feature differences that fall into one or more of the feature difference clusters,

wherein one of the boundaries is calculated using a 2-means event clustering algorithm to partition at least one of said feature difference clusters and at least one other boundary is calculated using a different clustering algorithm based upon a variance metric.

21. The method of claim 20 wherein said calculating is repeated until from 2 to 5 boundaries between feature difference clusters are provided.

22. The method of claim 21 wherein said feature differences are one of:

time differences, location differences, content similarity differences, and combinations of two or more of these differences.

23. The method of claim 20 wherein said feature differences are vectors of time and location differences.

24. The method of claim 20 wherein said repeating continues until a predetermined stopping criterion is reached.

25. The method of claim 20 further comprising designating each of said feature differences in a first defined of said clusters as being between events and each of said feature differences in all other of said clusters as being within events.

26. An apparatus for organizing a database of image files classified into events based upon date-time information associated with each of said image files, said apparatus comprising:

means for determining feature differences between consecutive said digital records;

means for ranking said feature differences to provide an unclustered feature difference set;

means for computing a sequence of three or more mutually exclusive feature difference clusters of said feature differences in decreasing order of relative likelihood of respective said feature differences representing separations between events, wherein at least one boundary between feature difference clusters is constrained to fall within a specified range, the feature difference clusters being computed using a 2-means event clustering algorithm to determine at least one of said feature difference clusters and using a different clustering algorithm based upon a variance metric to determine at least one other of said feature difference clusters; and

means for designating respective said feature differences in the feature difference cluster lowest in said decreasing order as being within events and designating respective said feature differences in the feature difference cluster highest in said decreasing order as being between events.