Variance-based event clustering

• US 20060126944A1
• Filed: 11/17/2004
• Published: 06/15/2006
• Est. Priority Date: 11/17/2004
• Status: Active Grant

• Current Assignee: Monument Peak Ventures, LLC (Dominion Harbor Enterprises, LLC)
• Original Assignee: Eastman Kodak Company
• Inventors: Loui, Alexander C., Kraus, Bryan D.
• Granted Patent: US 7,653,249 B2
• Time in Patent Office: Days
• US Class Current: 382/224
• CPC Class Codes: G06F 16/55 Clustering; Classification
• CPC Class Codes: G06F 16/5838 using colour

Abstract

In an image classification method, a plurality of grouping values are received. The grouping values each have an associated image. An average of the grouping values is calculated. A variance metric of the grouping values, relative to the average is computed. A grouping threshold is determined from the variance metric. Grouping values beyond the grouping threshold are identified as group boundaries. The images are assigned to a plurality of groups based upon the group boundaries.

Claims

1. An image classification method comprising the steps of:

receiving a plurality of grouping values, said grouping values each having an associated image;

calculating an average of said grouping values;

computing a variance metric of said grouping values, relative to said average;

determining from said variance metric a grouping threshold applicable to said grouping values;

identifying grouping values beyond said grouping threshold as group boundaries;

assigning said images to a plurality of groups based upon said group boundaries.

2. The method of claim 1 wherein said grouping values are based upon at least one of time differences and distances.

3. The method of claim 2 wherein said time differences or distances are relative to an adjoining image in a sequence.

4. The method of claim 2 wherein said time differences or distances are all relative to at least one of a temporal reference and a geographic reference.

5. The method of claim 4 wherein said temporal or geographic reference is constant as to all of said images.

6. The method of claim 1 wherein said grouping values are relative distances from a movable reference during capture of the respective images and said movable reference has different absolute spatial locations at times of capture of two or more of said images.

7. The method of claim 6 wherein said receiving further comprises capturing said images using a plurality of independently operated cameras.

8. The method of claim 1 wherein said receiving further comprises capturing said images using a plurality of independently operated cameras.

9. The method of claim 8 wherein said grouping values are times and said cameras are free of real-time clock synchronization.

10. The method of claim 8 further comprising designating one of said cameras as a movable reference and wherein said grouping values each represent the separation of a respective said camera from said movable reference at the time of capture of the respective image.

11. The method of claim 1 wherein said grouping values are block histogram differences.

12. The method of claim 11 wherein said block histogram differences are relative to an adjoining image of a chronological sequence.

13. The method of claim 1 wherein said average is an arithmetic mean.

14. The method of claim 1 wherein said variance metric is a standard deviation.

15. The method of claim 1 wherein said images each have a second-grouping value and said method further comprises, following said assigning:

calculating as to one or more of said groups, a group average of said second-grouping values of respective said images;

computing a variance metric of respective said second-grouping values relative to each said average;

determining from each said variance metric a respective second-grouping threshold applicable to the respective said group;

identifying ones of said second-grouping values beyond respective said second-grouping thresholds as subgroup boundaries of respective said groups;

assigning said images of each of said one or more groups to a plurality of subgroups based upon respective said subgroup boundaries.

16. The method of claim 15 wherein said grouping values are one of time differences and distances.

17. The method of claim 16 wherein said second-grouping values are the other of said time differences and said distances.

18. The method of claim 16 wherein said second-grouping values are based upon image content.

19. The method of claim 16 wherein said second-grouping values are block histogram differences.

20. The method of claim 1 further comprising analyzing content of said images of one or more of said groups and assigning said images of said one or more of said groups to subsets responsive to said analyzing.

21. The method of claim 1 further comprising, prior to said computing of said average, difference scaling said grouping values, wherein relatively large values are reduced and relatively small values are retained.

22. The method of claim 1 wherein said grouping threshold is expressed by the equation:

event threshold=0.2+8.159e<sup>(−

0.0002*(sˆ

2))</sup>

where

e is the natural logarithm, and

s is the standard deviation of said grouping values.

23. The method of claim 1 wherein said variance metric is one of standard deviation, variance, mean deviation, and sample variation.

24. The method of claim 1 wherein said images each have metadata representing a separation from a geographic or temporal reference at a time of capture of the respective image and said computing steps utilize said metadata.

25. The method of claim 1 wherein said computing steps further comprise preparing a time- or distance-difference histogram and applying a mapping function to said histogram.

26. An image classification method comprising the steps of:

receiving a plurality of grouping values, said grouping values each having an associated image, said grouping values each representing a separation from a geographic or temporal reference at a time of capture of the respective image;

calculating an arithmetic mean of said grouping values;

computing a standard deviation of said grouping values, relative to said average;

determining a grouping threshold applicable to said grouping values, said grouping threshold being a multiple of said standard deviation;

identifying grouping values beyond said grouping threshold as group boundaries;

assigning said images to a plurality of groups based upon said group boundaries.

27. 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:

receiving a plurality of grouping values, said grouping values each having an associated image;

calculating an average of said grouping values;

computing a variance metric of said grouping values, relative to said average;

determining from said variance metric a grouping threshold applicable to said grouping values;

identifying grouping values beyond said grouping threshold as group boundaries;

assigning said images to a plurality of groups based upon said group boundaries.

28. An image classification apparatus comprising:

means for receiving a plurality of grouping values, said grouping values each having an associated image;

means for calculating an average of said grouping values;

means for computing a variance metric of said grouping values, relative to said average;

means for determining from said variance metric a grouping threshold applicable to said grouping values;

means for identifying grouping values beyond said grouping threshold as group boundaries;

means for assigning said images to a plurality of groups based upon said group boundaries.