Automatic video summarization using a measure of shot importance and a frame-packing method

• US 6,535,639 B1
• Filed: 03/12/1999
• Issued: 03/18/2003
• Est. Priority Date: 03/12/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: Uchihachi, Shingo, Wilcox, Lynn, Foote, Jonathan T.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Mariam, Daniel G.
• Application Number:
  US09/267,529
• Time in Patent Office: 1,467 Days
• Field of Search: 382/173, 382/224, 382/225, 382/226, 382/240, 382/284, 382/103, 382/164-165, 382/171, 382/305, 382/168, 382/176, 382/232, 382/233, 382/254, 348/700, 348/169, 707/3, 707/2, 707/5, 707/10, 707/104.1, 707/500.1, 707/501.1, 707/514, 707/516, 345/440, 341/79
• US Class Current: 382/225
• 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/7847 using low-level visual features of the video content
• CPC Class Codes: G06V 20/40 in video content extracting overlay text G06V20/62; video retrieval G06F16/70; processing of video elementary streams in video servers H04N21/234; processing of video elementary streams in video clients H04N21/44
• CPC Class Codes: G06V 20/47 Detecting features for summarising video content
• CPC Class Codes: G11B 27/031 Electronic editing of digitised analogue information signals, e.g. audio or video signals
• 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: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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=\frac{S_i}{\underset{j=i}{\overset{c}{\sum <br><br>}}<br><br>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.

5. 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,

6. 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,

7. 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,

8. 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,

9. 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,

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. 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,

19. 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,

20. 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,

21. 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,

22. 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=\frac{S_i}{\underset{j=i}{\overset{c}{\sum <br><br>}}<br><br>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.

23. 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<br><br>\left(q,b,e\right)=\frac{1}{e-b+1}<br><br>\underset{j=b}{\overset{e}{\sum <br><br>}}<br><br>c<br><br>\left(f_j,q_{j-b+1}\right)+w<br><br>\left(q\right)$

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.

24. 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.

25. 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.

26. 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.

27. 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.

28. 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.

29. 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.

30. 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.

31. 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.

32. 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.

33. 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.

34. 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.

35. 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.

36. 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.

37. 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=\frac{S_i}{\underset{j=i}{\overset{c}{\sum <br><br>}}<br><br>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.

38. 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,

39. 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,

40. 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,

41. 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,