US5956026A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for hierarchical summarization and browsing of digital video
Assignee: Sharp Corp
•
Filing: 1997-12-19
•
Granted: 1999-09-21
•
Expires: 2017-12-19
Abstract
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.
Inventors
- 👤 Krishna Ratakonda
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 10:07
CPC Classifications
H; H04; H04N; H04N5/00; H04N5/14; H04N5/147; G; G06; G06F; G06F16/00; G06F16/70; G06F16/73; G06F16/738; G06F16/739; G06F16/78; G06F16/783; G06F16/7847; G06F16/785; G06F16/786; G11; G11B; G11B27/00; G11B27/02; G11B27/031; G11B27/034; G11B27/10; G11B27/102; G11B27/19; G11B27/28; G11B27/32; G11B27/326
Claims Analysis
Total Claims: 31
Claim 1
Independent Claim
186 words
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 =1, where t 0 =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 1 by 1 and go to said defining; and identifying keyframes including starting from the second keyframe positioned at k 2 by the largest consecutive difference criteria.
Claim 2
Independent Claim
186 words
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 =1, where t 0 =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 1 by 1 and go to said defining; and identifying keyframes including starting from the second keyframe positioned at k 2 by the largest consecutive difference criteria.
Claim 3
Dependent Claim
43 words
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.
Claim 4
Dependent Claim
18 words
The method of claim 2 which includes, after said generating, browsing the keyframes using the hierarchical keyframe summary.
Claim 5
Dependent Claim
15 words
The method of claim 2 which, after said inputting, includes detecting and removing dissolve events.
Claim 6
Dependent Claim
42 words
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.
Claim 7
Dependent Claim
15 words
The method of claim 5 which includes detecting pan events and building an image mosaic.
Claim 8
Dependent Claim
23 words
The method of claim 5 which includes detecting zoom events, estimating the degree of zoom in the event, and compiling a zoom summary.
Claim 9
Dependent Claim
16 words
The method of claim 5 which includes excluding global motion events from the hierarchical summarization process.
Claim 10
Dependent Claim
19 words
The method of claim 1 which includes browsing the keyframes by a user after selecting a specific level summary.
Claim 11
Dependent Claim
23 words
The method of claim 1 wherein keyframes in the keyframe hierarchical summary may be spatially sub-sampled into thumbnails for storage, retrieval or display.
Claim 12
Dependent Claim
23 words
The method of claim 1 wherein said generating a hierarchical keyframe summary includes clustering keyframes and generating keyframes of a coarser level summary.
Claim 13
Dependent Claim
22 words
The method of claim 11 wherein said clustering includes producing a compaction ratio in the number of keyframes at the coarser level.
Claim 14
Dependent Claim
11 words
The method of claim 11 wherein said clustering includes pairwise clustering.
Claim 15
Dependent Claim
22 words
The method of claim 11 wherein said generating keyframes of a coarser level summary includes generating keyframes using largest consecutive difference criteria.
Claim 16
Dependent Claim
26 words
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 .
Claim 17
Dependent Claim
16 words
The method of claim 1 wherein said identifying includes selecting every (n/K)th frame as a keyframe.
Claim 18
Dependent Claim
21 words
The method of claim 1 wherein said identifying includes detecting uninteresting shots and eliminating their keyframes from the hierarchical keyframe summary.
Claim 19
Dependent Claim
34 words
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.
Claim 20
Dependent Claim
17 words
The method of claim 18 wherein said allocating keyframes within each shot includes fully decoding the keyframe.
Claim 21
Dependent Claim
33 words
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.
Claim 22
Dependent Claim
25 words
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.
Claim 23
Dependent Claim
17 words
The method of claim 18 wherein said partially decoding includes decoding only keyframes and their reference frames.
Claim 24
Dependent Claim
14 words
The method of claim 18 wherein said decoding includes decoding by a decoder manager.
Claim 25
Dependent Claim
32 words
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.
Claim 26
Dependent Claim
35 words
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.
Claim 27
Dependent Claim
26 words
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.
Claim 28
Dependent Claim
23 words
The method of claim 26 where only those keyframes that are consecutive in time are allowed to be included in the same cluster.
Claim 29
Dependent Claim
15 words
The method of claim 27 where clustering is performed using a pairwise K-means clustering algorithm.
Claim 30
Dependent Claim
34 words
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.
Claim 31
Dependent Claim
27 words
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.
References Cited (Backward Citations)
US5099322A
Cited
US5513306A
Cited
US5339166A
Cited
US5537528A
Cited
EP0615245A2
Cited
US5642294A
Cited
US5550965A
Cited
US5606655A
Cited
US5521841A
Cited
US5635982A
Cited
US5600775A
Cited
US5485611A
Cited
US5821945A
Cited
US5708732A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-09-20 | 2003-03-22 | 2003-09-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-09-20 | 2007-03-22 | 2007-09-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-09-20 | 2011-03-22 | 2011-09-21 | $7700.00 | Window Closed / Lapsed |