Method for hierarchical summarization and browsing of digital video

• US 5,956,026 A
• Filed: 12/19/1997
• Issued: 09/21/1999
• Est. Priority Date: 12/19/1997
• Status: Expired due to Term

• Current Assignee: Sharp Kabushiki Kaisha (Hon Hai Precision Industry Co., Ltd.)
• Original Assignee: Sharp Laboratories of America Incorporated (Hon Hai Precision Industry Co., Ltd.)
• Inventors: Ratakonda, Krishna
• Primary Examiner(s): Bayerl, Raymond J.
• Assistant Examiner(s): Luu, Sy D.
• Application Number:
  US08/994,558
• Time in Patent Office: 641 Days
• Field of Search: 345/328, 345/348-349, 386/52, 386/4, 386/64, 369/83
• US Class Current: 715/723
• CPC Class Codes: G06F 16/739 in form of a video summary, e.g. the video summary being a video sequence, a composite still image or having synthesized frames
• CPC Class Codes: G06F 16/785 using colour or luminescence
• CPC Class Codes: G06F 16/786 using motion, e.g. object motion or camera motion
• CPC Class Codes: G11B 27/034 on discs G11B27/036, G11B27/038 take precedence
• CPC Class Codes: G11B 27/102 Programmed access in sequence to addressed parts of tracks of operating record carriers access by moving the head G11B3/08, G11B5/54, G11B7/085, G11B21/022; by moving the record carrier G11B15/005, G11B17/005, by driving of both record carrier and head G11B15/1816
• 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/326 used signal is a video-frame or a video-field (P.I.P.)
• CPC Class Codes: H04N 5/147 Scene change detection

Abstract

A method of hierarchical digital video summarization and browsing includes inputting a digital video signal for a digital video sequence and generating a hierarchical summary based on keyframes of the video sequence. Additional steps may include computing histograms for the digital video sequence; detecting shot boundaries within the digital video sequence; determining the number of keyframes to be allocated within each shot; locating the actual position of each keyframe within each shot; identifying keyframe locations by the largest consecutive difference criteria; pruning keyframes for an shot without meaningful action; extracting keyframes efficiently in the case of compressed video; and browsing the shots using the hierarchical keyframe summary.

Claims

1. A method of hierarchical digital video summarization and browsing comprising:

inputting a digital video signal for a digital video sequence; and

generating a hierarchical keyframe summary, including dividing the hierarchical keyframe summary into multiple level summaries, including a most compact level summary, a coarse level summary, and a finest level summary, and

identifying keyframes by setting k₁ =1, where t₀ =0 and the second frame is chosen as a candidate for being the first keyframe;

defining, for i=1 through K-1, and t_i =2 k_i -t_i-1, k_i+1 to be the first video frame for which 2C(t_i)-C(k_i)≦

C(k_i+1) holds; and

for i=K, computing t'"'"'_K =2k_K -t_K-1, and unless t_K >

2 k_K -t_K-1 =t'"'"'_K, keeping the results of the previous iteration, add an offset to all k_i s so that t_K =t'"'"'_K, and stopping, otherwise, increment k₁ by 1 and go to said defining; and

identifying keyframes including starting from the second keyframe positioned at k₂ by the largest consecutive difference criteria.

2. The method of claim 1 which includes, after said inputting, computing histograms for the digital video sequence;

detecting shot boundaries within the digital video sequence;

determining the number of keyframes allocated within each shot; and

pruning keyframes for a shot without meaningful action.

3. The method of claim 2 which includes, after said generating, browsing the keyframes using the hierarchical keyframe summary.

4. The method of claim 2 which, after said inputting, includes detecting and removing dissolve events.

5. The method of claim 4 which, after said detecting and removing dissolve events includes detecting global motion events by detecting frames within the digital video sequence that include events taken from the group of events consisting of pan events and zoom events.

6. The method of claim 5 which includes detecting pan events and building an image mosaic.

7. The method of claim 5 which includes detecting zoom events, estimating the degree of zoom in the event, and compiling a zoom summary.

8. The method of claim 5 which includes excluding global motion events from the hierarchical summarization process.

9. The method of claim 1 which includes browsing the keyframes by a user after selecting a specific level summary.

10. The method of claim 1 wherein keyframes in the keyframe hierarchical summary may be spatially sub-sampled into thumbnails for storage, retrieval or display.

11. The method of claim 1 wherein said generating a hierarchical keyframe summary includes clustering keyframes and generating keyframes of a coarser level summary.

12. The method of claim 11 wherein said clustering includes producing a compaction ratio in the number of keyframes at the coarser level.

13. The method of claim 11 wherein said clustering includes pairwise clustering.

14. The method of claim 11 wherein said generating keyframes of a coarser level summary includes generating keyframes using largest consecutive difference criteria.

15. The method of claim 1 wherein said computing includes locating the last keyframe of the shot adjacent the midpoint between t_k-1 and t_K.

16. The method of claim 1 wherein said identifying includes selecting every (n/K)th frame as a keyframe.

17. The method of claim 1 wherein said identifying includes detecting uninteresting shots and eliminating their keyframes from the hierarchical keyframe summary.

18. The method of claim 1 wherein said inputting includes inputting a compressed digital video sequence and generating a bitstream index table, wherein said computing histograms includes only partially decoding the compressed digital video sequence.

19. The method of claim 18 wherein said allocating keyframes within each shot includes fully decoding the keyframe.

20. The method of claim 19 wherein said fully decoding the keyframe includes decoding the keyframe without parsing the video bitstream and without completely decoding the video bitstream by using a bitstream index table.

21. The method of claim 18 wherein said partially decoding a DCT-based compressed video includes using the DC value of DCT coefficients to compute a histogram.

22. The method of claim 18 wherein said partially decoding includes decoding only keyframes and their reference frames.

23. The method of claim 18 wherein said decoding includes decoding by a decoder manager.

24. The method of claim 23 wherein said decoding by a decoder manager includes using a bitstream index table to decode the keyframes with minimal decoding and parsing of the entire video bitstream.

25. The method of claim 24 wherein said decoding by the decoder manager includes generating a pruned bitstream index table and storing only the information needed to decode keyframes without parsing and decoding the entire bitstream.

26. The method of claim 1 which further includes generating one or more coarser-level summaries from a given keyframe summary by statistical clustering histogram vectors of keyframes.

27. The method of claim 26 where only those keyframes that are consecutive in time are allowed to be included in the same cluster.

28. The method of claim 27 where clustering is performed using a pairwise K-means clustering algorithm.

29. The method of claim 28 which includes selecting keyframes to represent keyframe clusters and choosing keyframes as those frames within the clusters whose histogram vectors are closest to the centroid vectors of the clusters.

30. The method of claim 28 wherein said selecting includes selecting the keyframes in the second and existing subsequent clusters on the basis of largest consecutive difference criterion.