US6535639B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Automatic video summarization using a measure of shot importance and a frame-packing method
Assignee: Fujifilm Business Innovation Corp
•
Filing: 1999-03-12
•
Granted: 2003-03-18
•
Expires: 2019-03-12
Abstract
Abstract A measure of importance is calculated for segmented parts of a video. The segmented parts are determined by segmenting the video into component shots and then merging by iteration the component shots based on similarity or other factors. Segmentation may also be determined by clustering frames of the video, and creating segments from the same cluster ID. The measure of importance is calculated based on a normalized weight of each segment and on length and rarity of each shot/segmented part. The importance measure may be utilized to generate a video summary by selecting the most important segments and generating representative frames for the selected segments. A thresholding process is applied to the importance score to provide a predetermined number or an appropriate number generated on the fly of shots or segments to be represented by frames. The representative frames are then packed into the video summary. The sizes of the frames to be packed are predetermined by their importance measure and adjusted according to space availability. Packing based on a grid and an exhaustive search of frame combinations to fill each row in the grid. A cost algorithm and a space-filling rule are utilized to determine the best fit of frames. The video summary may be presented on either a paper interface referencing or a web page linking the frames of the summary to points of the video.
Inventors
- 👤 Shingo Uchihachi
- 👤 Jonathan T. Foote
- 👤 Lynn Wilcox
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 09:43
CPC Classifications
G; G06; G06V; G06V20/00; G06V20/40; G11; G11B; G11B27/00; G11B27/02; G11B27/031; G06F; G06F16/00; G06F16/70; G06F16/73; G06F16/738; G06F16/739; G06F16/78; G06F16/783; G06F16/7847; G06V20/46; G06V20/47; G11B27/10; G11B27/19; G11B27/28; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99941; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 46
Claim 1
Independent Claim
93 words
A method of determining the importance of segments in a video, comprising the steps of: dividing the video into segments, each segment comprising at least one related frame of the video; clustering segments of the video based on at least one of a common attribute and a matching criteria to produce at least one segment cluster; calculating a weight for each segment cluster; and calculating an amount of importance for each segment in the video based on the length of the segment and the inverse weight of the segment cluster containing the segment.
Claim 2
Independent Claim
93 words
A method of determining the importance of segments in a video, comprising the steps of: dividing the video into segments, each segment comprising at least one related frame of the video; clustering segments of the video based on at least one of a common attribute and a matching criteria to produce at least one segment cluster; calculating a weight for each segment cluster; and calculating an amount of importance for each segment in the video based on the length of the segment and the inverse weight of the segment cluster containing the segment.
Claim 3
Dependent Claim
77 words
The method according to claim 1 , wherein: said step of clustering segments of the video comprises the steps of, placing each frame of the video on a leaf of a hierarchical tree, wherein a root node of the tree is a maximal cluster containing all frames in the video, and joining related frames into segments based on at least one of a common attribute and matching criteria to create intervening nodes, clusters, of said hierarchal tree.
Claim 4
Dependent Claim
55 words
The method according to claim 1 , wherein said step of clustering segments of the video comprises the steps of: evaluating at least one of proximity in time, proximity in space, proximity in color, minimum distance, color-histogram distances, and transform-coefficient distance between each segment; and combining segments matching a predetermined threshold of the evaluating step.
Claim 5
Dependent Claim
81 words
The method according to claim 1 , wherein said step of calculating a weight of each cluster, comprises the step of: determining a weight Wi of a cluster based on at least a formula comprising, W i = S i ∑ j = i c S j wherein W i is the calculated weight of the cluster i, S i is a total length of all segments in cluster i, and C is a number of clusters in the video.
Claim 6
Dependent Claim
71 words
The method according to claim 1 , wherein said step of calculating comprises the step of: calculating an amount of importance of each segment based on at least a formula comprising, I j =L j log(1/W k ); wherein I j is the importance of segment j; L j is a length of segment j; and W k is the calculated weight of the cluster k to which segment j belongs.
Claim 7
Dependent Claim
76 words
The method according to claim 1 , wherein said step of calculating comprises the step of: calculating an amount of importance of each segment based on at least a formula comprising, I j =L j log(α/W k ); wherein I j is the importance of segment j; L j is a length of segment j; α is a weighting factor, and W k is the calculated weight of the cluster k to which segment j belongs.
Claim 8
Dependent Claim
94 words
The method according to claim 1 , wherein said step of calculating comprises the step of: calculating an amount of importance of each segment based on at least a formula comprising, I j =(Σ t A t P t (S j ))L j log(1/W k ); wherein A t is an amplification factor, P t (S j ) is a probability estimate, I j is the importance of segment j; L j is a length of segment j, and W k is the calculated weight of the cluster k to which segment j belongs.
Claim 9
Dependent Claim
94 words
The method according to claim 1 , wherein said step of calculating comprises the step of: calculating an amount of importance of each segment based on at least a formula comprising, I j =L j log(Σ t A t P t (S j )/W k ); wherein A t is an amplification factor, P t (S j ) is a probability estimate, I j is the importance of segment j; L j is a length of segment j, and W k is the calculated weight of the cluster k to which segment j belongs.
Claim 10
Independent Claim
112 words
A method of determining the importance of segments in a video, comprising the steps of: dividing the video into segments, each segment comprising at least one related frame of the video; clustering segments of the video based on at least one of a common attribute and a matching criteria to produce at least one segment cluster; and calculating an amount of importance for each segment based on at least a formula comprising, I j =L j log(1/W k ); wherein I j is the importance of segment j; L j is a length of segment j; and W k is the calculated weight of the cluster k to which segment j belongs.
Claim 11
Independent Claim
112 words
A method of determining the importance of segments in a video, comprising the steps of: dividing the video into segments, each segment comprising at least one related frame of the video; clustering segments of the video based on at least one of a common attribute and a matching criteria to produce at least one segment cluster; and calculating an amount of importance for each segment based on at least a formula comprising, I j =L j log(1/W k ); wherein I j is the importance of segment j; L j is a length of segment j; and W k is the calculated weight of the cluster k to which segment j belongs.
Claim 12
Independent Claim
114 words
A method of summarizing content of a video, comprising the steps of: dividing the video into segments, each segment comprising at least one related frame of the video; clustering segments of the video based on at least one of a common attribute and a matching criteria to produce at least one segment cluster; calculating an importance for each segment based on the length of the segment and the inverse weight of the cluster containing the segment; selecting a representative frame from each segment; and generating a summary of the representative frames, wherein the presentation of each representative frame in the summary is based on the importance of the segment from which it was selected.
Claim 13
Independent Claim
114 words
A method of summarizing content of a video, comprising the steps of: dividing the video into segments, each segment comprising at least one related frame of the video; clustering segments of the video based on at least one of a common attribute and a matching criteria to produce at least one segment cluster; calculating an importance for each segment based on the length of the segment and the inverse weight of the cluster containing the segment; selecting a representative frame from each segment; and generating a summary of the representative frames, wherein the presentation of each representative frame in the summary is based on the importance of the segment from which it was selected.
Claim 14
Dependent Claim
26 words
The method according to claim 10 , further comprising the step of: thresholding the segments of the video based on the importance of the respective segment.
Claim 15
Dependent Claim
48 words
The method according to claim 11 wherein said step of thresholding comprises the steps of: selecting at least one of a predetermined number of segments having an importance level higher than any non-selected segments and segments having at least a predetermined importance value; and discarding all non-selected segments.
Claim 16
Dependent Claim
80 words
The method according to claim 10 , wherein said step of selecting comprises the step of: selecting a representative frame from a respective segment based on a formulation comprising at least one of a first frame of the respective segment, a frame that characterizes the respective segment, a frame nearest a centroid of all frames of the respective segment, a frame having a presence of a face, and a frame having any one of an absence and indicia of motion.
Claim 17
Dependent Claim
54 words
The method according to claim 10 , wherein said step of generating a summary comprises the steps of: sizing each representative frame based on an importance of the frame and an amount of space in a predetermined bounded area for display of the summary; and packing the representative frames into the predetermined bounded area.
Claim 18
Dependent Claim
53 words
The method according to claim 14 , wherein said step of sizing comprises the steps of: sizing each representative frame based on the importance of the segment from which it was extracted; and adjusting the size of each frame to fit into an open space of a predetermined bounded area of said summary.
Claim 19
Dependent Claim
60 words
The method according to claim 10 , wherein said summary comprises a paper interface, comprising: a printout of said summary; and a set of at least one code, each code associated with at least one representative frame of the video; wherein each code provides an index to at least one of a segment and a starting marker in the video.
Claim 20
Dependent Claim
57 words
The method according to claim 10 , wherein said summary comprises a web interface, comprising: a display of said summary; and a set of at least one link, each link associated with at least one of the selected representative frames; wherein each link accesses at least one of a segment and a starting marker in the video.
Claim 21
Dependent Claim
69 words
The method according to claim 10 , wherein said step of calculating comprises the step of: calculating an importance for each segment based on at least a formula comprising, I j =L j log(1/W k ); wherein I j is the importance of segment j; L j is a length of segment j; and W k is the calculated weight of the cluster k to which segment j belongs.
Claim 22
Dependent Claim
74 words
The method according to claim 10 , wherein said step of calculating comprises the step of: calculating an importance for each segment based on at least a formula comprising, I j =L j log(α/W k ); wherein I j is the importance of segment j; L j is α length of segment j; a is a weighting factor, and W k is the calculated weight of the cluster k to which segment j belongs.
Claim 23
Dependent Claim
92 words
The method according to claim 10 , wherein said step of calculating comprises the step of: calculating an importance for each segment based on at least a formula comprising, I j =(Σ t A t P t (S j ))L j log(1/W k ); wherein A t is an amplification factor, P t (S j ) is a probability estimate, I j is the importance of segment j; L j is a length of segment j, and W k is the calculated weight of the cluster k to which segment j belongs.
Claim 24
Dependent Claim
92 words
The method according to claim 10 , wherein said step of calculating comprises the step of: calculating an importance for each segment based on at least a formula comprising, I j =L j log(Σ t A t P t (S j )/W k ); wherein A t is an amplification factor, P t (S j ) is a probability estimate, I j is the importance of segment j; L j is a length of segment j, and W k is the calculated weight of the cluster k to which segment j belongs.
Claim 25
Dependent Claim
76 words
The method according to claim 10 , wherein said step of calculating comprises the step of: determining a weight Wi of a cluster based on at least a formula comprising, W i = S i ∑ j = i c S j wherein W i is the calculated weight of the cluster i, S i is a total length of all segments in cluster i, and C is a number of clusters in the video.
Claim 26
Independent Claim
137 words
A method of packing a set of frames into a bounded area, comprising the steps of: fitting frame sequences to the bounded area; calculating a cost d(q,b,e) of each frame sequence utilizing a formula comprising: d ( q , b , e ) = 1 e - b + 1 ∑ j = b e c ( f j , q j - b + 1 ) + w ( q ) and selecting a frame sequence having a least cost for the bounded area; where, q is a frame sequence (q i is the ith element of frame sequence q), b is a starting frame, e is an ending frame, j is a summation marker, c is a cost function, f is a frame size, and w is an importance function.
Claim 27
Independent Claim
137 words
A method of packing a set of frames into a bounded area, comprising the steps of: fitting frame sequences to the bounded area; calculating a cost d(q,b,e) of each frame sequence utilizing a formula comprising: d ( q , b , e ) = 1 e - b + 1 ∑ j = b e c ( f j , q j - b + 1 ) + w ( q ) and selecting a frame sequence having a least cost for the bounded area; where, q is a frame sequence (q i is the ith element of frame sequence q), b is a starting frame, e is an ending frame, j is a summation marker, c is a cost function, f is a frame size, and w is an importance function.
Claim 28
Dependent Claim
65 words
The method according to claim 23 , wherein said step of fitting, comprising the steps of: assigning a row height (r) from a set of row heights; dividing the bounded area into rows having a height (r); generating frame sequences fitting the bounded area of row height (r); and repeating said steps of assigning, dividing, and generating for each of said set of row heights.
Claim 29
Dependent Claim
57 words
The method according to claim 24 , wherein: said step of fitting includes the step of, placing a lowest cost frame sequence generated for each row height (r) into a low cost frame sequence set; and said step of selecting includes the step of selecting a lowest cost frame sequence from said low cost frame sequence set.
Claim 30
Dependent Claim
41 words
The method according to claim 24 , wherein said step of dividing, comprises: dividing the bounded area into a grid having a row height (r) being a multiple of a height of a smallest of frames in said set of frames.
Claim 31
Dependent Claim
59 words
The method according to claim 23 , wherein: said step of fitting, comprises the steps of, dividing the bounded area into a set of at least one grid, and fitting a least cost frame sequence into each grid; and said step of selecting comprises, selecting the bounded area frame sequence based on the least costframe sequence from each grid.
Claim 32
Dependent Claim
132 words
The method according to claim 27 , wherein said step of fitting a least cost frame sequence comprises the steps of: selecting a grid of said set of grids; assigning a row height (r) of the selected grid from a set of row heights; generating frame sequences fitting the selected grid with row height (r); placing a generated frame sequence having a least cost for the selected grid with row height (r) into a set of least cost frame sequences; performing said steps of generating and placing for each remaining row height in the set of row heights; selecting a lowest cost frame sequence from the set of least cost frame sequences; and repeating, for each remaining grid, said steps of assigning, generating, placing, performing, and selecting a lowest cost frame sequence.
Claim 33
Dependent Claim
43 words
The method according to claim 28 , wherein said step of generating frame sequences comprises the step of: maintaining a number and order of frames across the lowest cost frame sequences consistent with a number and order of frames in said frame set.
Claim 34
Dependent Claim
35 words
The method according to claim 28 , wherein said step of generating includes the step of: maintaining an order of frames in said frame sequences equivalent to an order in which the frames were created.
Claim 35
Dependent Claim
38 words
The method according to claim 28 , wherein said step of generating includes the step of: altering a size of each frame to fit within a first instance of white space of the row in the selected grid.
Claim 36
Dependent Claim
63 words
The method according to claim 28 , wherein: said step of dividing comprises, dividing the bounded area into a set of at least one grid having a grid spacing of W; and said step of generating includes the step of, altering a size of each frame to fit within a first instance of white space of a grid space in the selected grid.
Claim 37
Dependent Claim
61 words
The method according to claim 23 , further comprising the steps of: displaying the selected frame sequence on a web page; and linking at least one frame of the selected frame sequence to one of a segment, starting point, and menu options for display of at least one of display of a video and other information related to the linked frame.
Claim 38
Dependent Claim
50 words
The method according to claim 23 , further comprising the steps of: transferring the selected frame sequence to a tablet consisting of at least one of paper and other media; linking at least one frame of the selected frame sequence to a code referencing information related to the linked frame.
Claim 39
Independent Claim
109 words
A method of determining the importance of segments in a video, comprising the steps of: creating a hierarchy of video segment selections, each level of the hierarchy segmenting the video using different criteria; choosing a preferred video segment selection from the hierarchy; clustering segments of the video segment selection based on at least one of a common attribute and a matching criteria to produce at least one segment cluster; and calculating an amount of importance for each segment in the preferred video segment selection, the importance of each segment is calculated based on the length of the segment and the inverse weight of the segment cluster containing that segment.
Claim 40
Independent Claim
109 words
A method of determining the importance of segments in a video, comprising the steps of: creating a hierarchy of video segment selections, each level of the hierarchy segmenting the video using different criteria; choosing a preferred video segment selection from the hierarchy; clustering segments of the video segment selection based on at least one of a common attribute and a matching criteria to produce at least one segment cluster; and calculating an amount of importance for each segment in the preferred video segment selection, the importance of each segment is calculated based on the length of the segment and the inverse weight of the segment cluster containing that segment.
Claim 41
Dependent Claim
57 words
The method according to claim 35 , wherein said step of clustering segments of the video segment selection comprises the steps of: evaluating at least one of proximity in time, proximity in space, proximity in color, minimum distance, color-histogram distances, and transform-coefficient distance between each segment; and combining segments matching a predetermined threshold of the evaluating step.
Claim 42
Dependent Claim
80 words
The method according to claim 35 , wherein said step of calculating comprises the step of: calculating a weight Wi of a segment cluster based on at least a formula comprising, W i = S i ∑ j = i c S j wherein W i is the calculated weight of the segment cluster i, S i is a total length of all segments in segment cluster i, and C is a number of segment clusters in the video.
Claim 43
Dependent Claim
69 words
The method according to claim 35 , wherein said step of calculating comprises the step of: calculating an importance of each segment based on at least a formula comprising, I j =L j log(1/W k ); wherein I j is the importance of segment j; L j is a length of segment j; and W k is the calculated weight of the cluster k to which segment j belongs.
Claim 44
Dependent Claim
74 words
The method according to claim 35 , wherein said step of calculating comprises the step of: calculating an importance of each segment based on at least a formula comprising, I j =L j log(α/W k ); wherein I j is the importance of segment j; L j is a length of segment j; α is a weighting factor, and W k is the calculated weight of the cluster k to which segment j belongs.
Claim 45
Dependent Claim
92 words
The method according to claim 35 , wherein said step of calculating comprises the step of: calculating an importance of each segment based on at least a formula comprising, I j =(Σ t A t P t (S j ))L j log(1/W k ); wherein A t is an amplification factor, P t (S j ) is a probability estimate, I j is the importance of segment j; L j is a length of segment j, and W k is the calculated weight of the cluster k to which segment j belongs.
Claim 46
Dependent Claim
92 words
The method according to claim 35 , wherein said step of calculating comprises the step of: calculating an importance of each segment based on at least a formula comprising, I j =L j log(Σ t A t P t (S j )/W k ); wherein A t is an amplification factor, P t (S j ) is a probability estimate, I j is the importance of segment j; L j is a length of segment j, and W k is the calculated weight of the cluster k to which segment j belongs.
References Cited (Backward Citations)
US5210799A
Cited
US5243149A
Cited
US5325449A
Cited
US5488674A
Cited
US5606655A
Cited
US5664227A
Cited
US5708767A
Cited
US5821945A
Cited
US5920856A
Cited
US6061603A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-03-17 | 2006-09-16 | 2007-03-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-03-17 | 2010-09-16 | 2011-03-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-03-17 | 2014-09-16 | 2015-03-18 | $7700.00 | Window Closed / Lapsed |