Method and apparatus for automatically identifying a representative image for an image group

• US 9,070,048 B2
• Filed: 10/17/2013
• Issued: 06/30/2015
• Est. Priority Date: 10/17/2013
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Sinha, Rishi Ranjan, Shrivastava, Swapnil, Dey, Sumit
• Primary Examiner(s): Carter, Aaron W
• Assistant Examiner(s): Zohrabyan, Narek
• Application Number:
  US14/056,451
• Publication Number:
  US 20150110407A1
• Time in Patent Office: 621 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06F 18/231 Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram
• CPC Class Codes: G06F 18/24 Classification techniques
• CPC Class Codes: G06F 18/245 relating to the decision surface
• CPC Class Codes: G06V 10/7625 Hierarchical techniques, i.e. dividing or merging patterns to obtain a tree-like representation; Dendograms
• CPC Class Codes: G06V 20/46 Extracting features or characteristics from the video content, e.g. video fingerprints, representative shots or key frames
• CPC Class Codes: G06V 30/242 Division of the character sequences into groups prior to recognition; Selection of dictionaries

Abstract

A computer implemented method and apparatus for automatically identifying a representative image for an image group. The method comprises dividing an image group into one or more clusters based on an average time gap of the image group, wherein the images in the image group are in sequential timestamp order wherein the average time gap is calculated using a time span calculated from the timestamp of a first image in the image group to the timestamp of a last image in the image group; recursively dividing a largest cluster in the one or more clusters to determine a resultant cluster, wherein the resultant cluster comprises no time gaps larger than the average time gap of the resultant cluster; and identifying a representative image from the resultant cluster as an image representative for the image group.

Claims

1. A computer implemented method comprising:

dividing an image group of time sequential images into a plurality of clusters based on an average time gap of the image group;

recursively dividing a largest cluster in the plurality of clusters to determine a resultant cluster, wherein the resultant cluster comprises no time gaps larger than an average time gap of the resultant cluster; and

identifying a representative image from the resultant cluster as an image representative for the image group.

2. The method of claim 1, wherein each image in the image group comprises a timestamp, and wherein the average time gap is calculated as the timestamp of a last image in the image group or resultant cluster minus the timestamp of a first image in the image group or resultant cluster, divided by a total number of gaps in the image group or resultant cluster.

3. The method of claim 1, wherein dividing the image group comprises:

sorting a plurality of images in the image group based on time;

calculating the average time gap for the plurality of images; and

dividing the plurality of images into clusters wherein the division occurs where the time gap between two images is greater than the average time gap.

4. The method of claim 1, wherein recursively dividing continues until only two images remain in the resultant cluster or when all remaining images in the resultant cluster are equidistant in terms of time.

5. The method of claim 1, wherein identifying the representative image when the resultant cluster includes an odd number of images comprises selecting an image at a center of the resultant cluster.

6. The method of claim 1, wherein identifying the representative image when the resultant cluster includes an even number of images comprises:

calculating a left side time gap (LSG) between a leftmost image in the resultant cluster and an image immediately preceding the leftmost image, wherein the image immediately preceding the leftmost image is outside of the resultant cluster, and

calculating a right side time gap (RSG) between a rightmost image in the resultant cluster and an image immediately following the rightmost image, wherein the image immediately following the rightmost image is outside of the resultant cluster.

7. The method of claim 6, further comprising selecting an image in a position immediate left of center of the resultant cluster when the LSG is less than the RSG and selecting an image in a position immediately right of center of the resultant cluster when the RSG is less than the LSG.

8. An apparatus for identifying a representative image for an image group comprising:

a computer having one or more processors and further comprising;

an image selection module for dividing an image group of time sequential images into a plurality of clusters based on an average time gap of the image group;

recursively dividing a largest cluster in the plurality of clusters to determine a resultant cluster, wherein the resultant cluster comprises no time gaps larger than an average time gap of the resultant cluster; and

identifying a representative image from the resultant cluster as an image representative for the image group.

9. The apparatus of claim 8, wherein each image in the image group comprises a timestamp, and wherein the average time gap is calculated as the timestamp of a last image in the image group or resultant cluster minus the timestamp of a first image in the image group or resultant cluster, divided by a total number of gaps in the image group or resultant cluster.

10. The apparatus of claim 8, wherein dividing the image group comprises:

sorting a plurality of images in the image group based on time;

calculating the average time gap for the plurality of images; and

dividing the plurality of images into clusters wherein the division occurs where the time gap between two images is greater than the average time gap.

11. The apparatus of claim 8, wherein recursively dividing continues until only two images remain in the resultant cluster or when all remaining images in resultant cluster are equidistant in terms of time.

12. The apparatus of claim 8, wherein identifying the representative image when the resultant cluster includes an odd number of images comprises selecting an image at a center of the resultant cluster.

13. The apparatus of claim 8, wherein identifying the representative image when the resultant cluster comprises an even number of images comprises:

calculating a left side time gap (LSG) between a leftmost image in the resultant cluster and an image immediately preceding the leftmost image, wherein the image immediately preceding the leftmost image is outside of the resultant cluster;

calculating a right side time gap (RSG) between a rightmost image in the resultant cluster and an image immediately following the rightmost image, wherein the image immediately following the rightmost image is outside of the resultant cluster; and

selecting an image in a position immediate left of center of the resultant cluster when the LSG is less than the RSG and selecting an image in a position immediately right of center of the resultant cluster when the RSG is less than the LSG.

14. A non-transient computer readable medium for storing computer instructions that, when executed by at least one processor causes the at least one processor to perform a method for identifying a representative image for an image group comprising:

dividing an image group of time sequential images into a plurality of clusters based on an average time gap of the image group;

recursively dividing a largest cluster in the plurality of clusters to determine a resultant cluster, wherein the resultant cluster comprises no time gaps larger than an average time gap of the resultant cluster; and

identifying a representative image from the resultant cluster as an image representative for the image group.

15. The computer readable medium of claim 14, wherein each image in the image group comprises a timestamp, wherein the average time gap is calculated as the timestamp of a last image in the image group or resultant cluster minus the timestamp of a first image in the image group or resultant cluster, divided by a total number of gaps in the image group or resultant cluster.

16. The computer readable medium of claim 14, wherein dividing the image group comprises:

sorting a plurality of images in the image group based on time;

calculating the average time gap for the plurality of images; and

dividing the plurality of images into clusters wherein the division occurs where the time gap between two images is greater than the average time gap.

17. The computer readable medium of claim 14, wherein recursively dividing continues until only two images remain in the resultant cluster or when all remaining images in the resultant cluster are equidistant in terms of time.

18. The computer readable medium of claim 14, wherein identifying the representative image when the resultant cluster includes an odd number of images comprises selecting an image at a center of the resultant cluster.

19. The computer readable medium of claim 14, wherein identifying the representative image when the resultant cluster comprises an even number of images comprises:

calculating a left side time gap (LSG) between a leftmost image in the resultant cluster and an image immediately preceding the leftmost image, wherein the image immediately preceding the leftmost image is outside of the resultant cluster, and

calculating a right side time gap (RSG) between a rightmost image in the resultant cluster and an image immediately following the rightmost image, wherein the image immediately following the rightmost image is outside of the resultant cluster.

20. The computer readable medium of claim 19, further comprises selecting an image in a position immediately left of center of the resultant cluster when the LSG is less than the RSG and selecting an image in a position immediately right of center of the resultant cluster when the RSG is less than the LSG.