Video browser for navigating linear video on small display devices using a similarity-based navigation hierarchy of temporally ordered video keyframes with short navigation paths

• US 20090199099A1
• Filed: 02/04/2008
• Published: 08/06/2009
• Est. Priority Date: 02/04/2008
• Status: Active Grant

• Current Assignee: Fujifilm Business Innovation Corp. (Fujifilm Holdings Corporation)
• Original Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Inventors: Girgensohn, Andreas, Wilcox, Lynn D., Shipman, Frank M. III
• Granted Patent: US 8,117,204 B2
• Time in Patent Office: Days
• US Class Current: 715/719
• CPC Class Codes: G11B 27/28 by using information signals recorded by the same method as the main recording G11B27/22 takes precedence
• CPC Class Codes: G11B 27/34 Indicating arrangements indicating means incorporated in magazine or cassette G11B23/046 and G11B23/0875; indicating measured values in general G01D

Abstract

A computer-based method is provided for enabling navigation of video using a keyframe-based video browser on a display device with a limited screen size, for a video segmented into video shots. The video shots are clustered by similarity, while temporal order of the video shots is maintained. A hierarchically organized navigation tree is produced for the clusters of video shots, while the path lengths of the tree are minimized.

Claims

1. A computer-based method for enabling navigation of video using a keyframe-based video browser on a display device with a limited screen size and larger for a video segmented into video shots, the computer-based method comprising:

clustering the video shots by similarity, while maintaining temporal order of the video shots; and

producing a hierarchically organized navigation tree for the clusters of video shots, while minimizing the path lengths of the tree.

2. The computer-based method of claim 1, wherein clustering the video shots comprises determining the maximum number of leaves in the tree as b^h,

wherein a branching factor b comprises the maximum number of keyframes displayed to the display device;

and

wherein a height of the tree h comprises the smallest height such that b^h is greater than or equal to the number of video shots.

3. The computer-based method of claim 2, wherein clustering the video shots further comprises:

merging pairs of clusters that have temporally adjacent elements and skipping pairs where the merged cluster has more than a limit of b^h-1 elements; and

stopping merging once there are b clusters.

4. The computer-based method of claim 3, wherein clustering the video shots further comprises:

recursively clustering the elements of the subclusters and reducing the maximum number of cluster elements by a factor of b before each level of recursion.

5. The computer-based method of claim 4, wherein producing a hierarchically organized navigation tree comprises:

if subclustering a cluster produces more than b subclusters because there are no more subclusters that can be merged, then

marking the cluster as undesirable;

backtracking in the clustering at the higher level to the point where the undesirable cluster was created; and

repeating clustering while treating undesirable clusters like clusters that would exceed the limit of elements.

6. The computer-based method of claim 5, wherein if the root of the tree has more than b subclusters, incrementing the maximum height of the tree and repeating clustering from the start of clustering.

7. The computer-based method of claim 1, further comprising displaying a hierarchically-organized video to the display device via keyframes of the most important shot in the cluster overlaid with the first shot in the cluster.

8. The computer-based method of claim 1, further comprising:

displaying a timeline to the display device, showing a portion of the video associated with each cluster; and

displaying context-sensitive help to the display device to aid the user in navigation through the tree.

9. A system to enable navigation of video using a keyframe-based video browser on a display device with a limited screen size for a video segmented into video shots, the system comprising:

video shots clustered by similarity, while temporal order of the video shots is maintained; and

a hierarchically organized navigation tree is produced from the clustered video shots, while the path lengths of the tree are minimized.

10. The system of claim 9, wherein clustered video shots comprise a determination of the maximum number of leaves in the tree as b^h,

wherein a branching factor b comprises the maximum number of keyframes displayed to the display device;

and

wherein a height of the tree h comprises the smallest height such that b^h is greater than or equal to the number of video shots.

11. The system of claim 10, wherein the clustered video shots further comprise:

a merge of pairs of clusters that have temporally adjacent elements and a skip of pairs where the merged cluster has more than a limit of b^h-1 elements; and

a stop of the merge once there are b clusters.

12. The system of claim 11, wherein the clustered video shots further comprise:

a recursive cluster of the elements of the subclusters and a reduction of the maximum number of cluster elements by a factor of b before each level of recursion.

13. The system of claim 12, wherein if a cluster contains more than b subclusters because there are no more subclusters that can be merged, then

the cluster comprises being marked as undesirable;

the point in the clustering is determined by a backtrack in the clustering at the higher level to the point where the undesirable cluster was created; and

a repeat of the cluster of the elements from the point in the clustering is performed, while undesirable clusters are treated like clusters that would exceed the limit of elements.

14. The system of claim 13, wherein if the root of the tree has more than b subclusters, the maximum height of the tree is incremented and the clustering is repeated from the start of the clustering.

15. The system of claim 14, further comprising a display of hierarchically organized video to the display device via keyframes of the most important shot in the cluster overlaid with the first shot in the cluster.

16. The system of claim 15, further comprising:

a display of a timeline to the display device, showing a portion of the video associated with each cluster; and

a display of context-sensitive help to the display device to aid the user in navigation through the tree.

17. A program of instructions executable by a computer to perform a function for enabling navigation of video using a keyframe-based video browser on a display device with a limited screen size for a video segmented into video shots, the function comprising the steps of:

clustering the video shots by similarity, while maintaining temporal order of the video shots; and

producing a hierarchically organized navigation tree for the clusters of video shots, while minimizing the path lengths of the tree.