Time-constrained keyframe selection method

• US 6,807,306 B1
• Filed: 05/28/1999
• Issued: 10/19/2004
• Est. Priority Date: 05/28/1999
• Status: Expired due to Term

• Current Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.), Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.), Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Girgensohn, Andreas, Boreczky, John S.
• Primary Examiner(s): Dastouri, Mehrdad
• Application Number:
  US09/322,842
• Time in Patent Office: 1,971 Days
• Field of Search: 382/224, 382/225, 382/226, 348/700, 348/701, 348/590, 345/328, 368/69, 368/121
• US Class Current: 382/225
• CPC Class Codes: G06F 16/785 using colour or luminescence
• CPC Class Codes: G06V 20/47 Detecting features for summarising video content
• CPC Class Codes: H04N 5/147 Scene change detection

Abstract

A method for candidate frame selection involves sampling the source frames of the source video at a predetermined fixed periodic interval. The largest frame differences represent candidate boundaries, and the frames before and after the N/2 largest candidate boundaries are selected as candidate frames. A method for selecting keyframes involves clustering all candidate frames into a hierarchical binary tree using a hierarchical agglomerative clustering algorithm. Optionally, the pairwise distances for the members of the two clusters is modified according to class membership of the members, which is preferably determined statistically from image class statistical models. A method for selecting M clusters from which keyframes are extracted involves splitting the M-1 largest clusters of a hierarchical binary tree of clusters. Optionally, clusters not having at least one uninterrupted sequence of frames of at least a minimum duration are filtered out. The source video duration is divided into equal duration intervals. If an interval has no keyframes, all other intervals having at least two keyframes are inspected in descending keyframe count order to attempt to find a keyframe within a cluster that has a member within the interval that does not have any keyframes. If such a keyframe is found, the member is substituted as the keyframe for the cluster. The minimum time between any two keyframes is determined. If this minimum time is less than a minimum time threshold, an attempt is made to find another keyframe from one or both of the two clusters which the two conflicting keyframe belong to. If a substitute cannot be found, one of the conflicting keyframes is deleted.

Claims

1. A method for selecting keyframes from selected clusters, the method comprising the steps of:

(a) for each selected cluster, determining a longest sequence of members that is not interrupted by members of another selected cluster; and

(b) for each selected cluster, selecting a frame closest to a center of the longest sequence of members as a keyframe for the selected cluster;

(c) dividing a source video duration into equal duration intervals;

(d) for each equal duration interval, counting a number of selected keyframes;

(e) checking an equal duration interval for a selected keyframe;

(f) if step (e) determined that the equal duration interval does not have any selected keyframes, checking other equal duration intervals having at least two keyframes in descending keyframe count order for a keyframe from a selected cluster which has a member in the equal duration interval that does not have any selected keyframes;

(g) if step (f) found the member in the equal duration interval that does not have any selected keyframes, removing the keyframe from the selected cluster which has the member in the equal duration interval that does not have any selected keyframes; and

(h) if step (f) found the member in the equal duration interval that does not have any selected keyframes, selecting the member in the equal duration interval that does not have any selected keyframes as a keyframe for the equal duration interval that does not have any selected keyframes; and

(i) returning to step (e) if step (e) has not been performed on all equal duration intervals.

2. A method as in claim 1, further comprising the steps of:

(j) finding a minimum time between two keyframes;

(k) comparing the minimum time between two keyframes to a minimum time threshold for keyframe separation; and

(l) if step (k) determines that the minimum time between two keyframes is less than a minimum time threshold for keyframe separation, for a corresponding two clusters that the keyframes belong to, attempting to select another member first for one cluster, then for the other cluster, and finally for both clusters simultaneously until frames are found that are separated at least by the minimum time threshold.

3. A method as in claim 2, further comprising the step of:

(m) if step (l) and does not find frames that are separated at least by the minimum time threshold, removing one of the two keyframes; and

(n) if step (l) is performed, returning to step (j).