Scalable video summarization and navigation system and method

• US 20030210886A1
• Filed: 05/07/2002
• Published: 11/13/2003
• Est. Priority Date: 05/07/2002
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Zhang, Tong, Li, Ying, Tretter, Daniel R.
• Granted Patent: US 7,035,435 B2
• Time in Patent Office: Days
• US Class Current: 386/46
• 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/784 the detected or recognised objects being people
• CPC Class Codes: G06F 16/786 using motion, e.g. object motion or camera motion
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A method and system for automatically summarizing a video document. The video document is decomposed into scenes, shots and frames, and an importance value is assigned to each scene, shot and frame. Keyframes are allocated among the shots based on the importance value of each shot. The allocated number of keyframes are then selected from each shot. The number of keyframes may be altered for greater or lesser detail in response to user input.

Claims

1. A method for automatically summarizing a video document comprising the steps of:

decomposing the video document into scenes, shots and frames;

assigning an importance value to each scene, shot and frame;

allocating a number of keyframes among the shots based on the importance value of each shot;

selecting the allocated number of keyframes from each shot; and

altering the number of keyframes in response to user input.

2. The method of claim 1, wherein the number of keyframes allocated among the shots is a predetermined number of keyframes.

3. The method of claim 1, wherein assigning an importance value to each scene, shot and frame includes the steps of defining a scene importance algorithm, a shot importance algorithm and a frame importance algorithm and computing the importance value of the scenes, shots and frames, respectively, with the algorithms.

4. The method of claim 3, wherein computing a scene importance value includes the steps of measuring a length of the scene, quantifying the activity level of the scene, and counting the number of shots in the scene.

5. The method of claim 3, wherein computing a scene importance value includes the step of measuring a length of the scene.

6. The method of claim 5, wherein measuring a length of the scene includes the step of counting the number of frames in the scene.

7. The method of claim 3, wherein computing a scene importance value includes the step of quantifying the activity level of the scene.

8. The method of claim 7, wherein quantifying the activity level of the scene includes the steps of computing a color histogram difference for each consecutive frame pair within the scene and using their average to indicate the scene activity level.

9. The method of claim 3, wherein computing a scene importance value includes the step of counting the number of shots in the scene.

10. The method of claim 3, wherein computing a shot importance value includes the steps of measuring a length of the shot, quantifying the activity level within the shot, and quantifying camera motion within the shot.

11. The method of claim 3, wherein computing a shot importance value includes the step of measuring a length of the shot.

12. The method of claim 11, wherein measuring a length of the shot includes the step of counting the number of frames in the shot.

13. The method of claim 3, wherein computing a shot importance value includes the step of quantifying the activity level within the shot.

14. The method of claim 13, wherein quantifying the activity level within the shot includes the steps of computing the amount of motion between every referenced frame pair within the shot and using their average to indicate the shot activity level.

15. The method of claim 3, wherein computing a shot importance value includes the step of quantifying camera motion within the shot.

16. The method of claim 15, wherein quantifying camera motion within the shot includes the steps of categorizing the direction motion vectors of each frame into a discrete number of directions and computing a motion vector histogram, and computing a directional motion ratio and an average magnitude of the directional motion vectors.

17. The method of claim 3, wherein computing a frame importance value includes the steps of determining the percentage of skin-colored pixels in the frame, and counting the number of detected human faces in the frame.

18. The method of claim 17, wherein computing a frame importance value further includes the step of calculating the edge energy distribution of the frame

19. The method of claim 17, wherein computing a frame importance value further includes the step of quantifying the amount of motion activity contained in the frame.

20. The method of claim 1, wherein selecting the allocated number of keyframes from each shot includes the step of selecting the keyframes with the highest importance value.

21. The method of claim 1, wherein selecting the allocated number of keyframes from each shot comprises selecting the keyframes using time-constrained keyframe selection.

22. The method of claim 1, wherein selecting the allocated number of keyframes from each shot comprises selecting the keyframes using importance-adapted keyframe selection.

23. The method of claim 2, wherein altering the number of keyframes in response to user input includes the step of removing one or more keyframes from the predetermined number of selected keyframes.

24. The method of claim 23, wherein removing one or more keyframes from the predetermined number of selected keyframes includes the step of removing the least important keyframe in the least important shot.

25. The method of claim 2, wherein altering the number of keyframes in response to user input includes the step of adding one or more keyframes to the predetermined number of selected keyframes.

26. The method of claim 1, wherein allocating a number of keyframes among the shots includes the steps of assigning the keyframes among the scenes based on the importance value of the scenes, and within each scene, distributing the assigned keyframes to the component shots of each scene.

27. The method of claim 1, further comprising the step of displaying the selected keyframes on a display device.

28. A video summarization system comprising:

a processor for selecting keyframes from a video document to create a video summary;

a data storage system, wherein the video processor stores the video summary in the data storage system;

a display system for displaying the video summary; and

a user interface operably coupled to the video processor, wherein the video processor is responsive to the user interface for altering the video summary by adding or subtracting keyframes.

29. The video summarization system of claim 28, wherein the data storage system includes random access memory.

30. The video summarization system of claim 28, wherein the data storage system includes a hard disk drive or other persistent storage device.

31. The video summarization system of claim 28, wherein the display system comprises a video monitor.

32. The video summarization system of claim 28, wherein the display system comprises a printer.

33. A computer readable medium containing instructions for controlling a computer system to perform a method for summarizing a video document comprising the steps of:

decomposing the video document into scenes, shots and frames;

assigning an importance value to each scene, shot and frame;

allocating a number of keyframes among the scenes based on the importance value of each scene;

allocating a number of keyframes among the shots based on the importance value of each shot;

selecting the allocated number of keyframes from each shot; and

altering the number of keyframes in response to user input.

34. A method for summarizing and navigating a video document comprising the steps of:

decomposing the video document into a hierarchal tree of scenes, shots and frames;

assigning an importance value to each scene, shot and frame;

allocating a predetermined number of keyframes among the scenes;

assigning the allocated keyframes in each scene among the shots of each scene;

selecting the assigned number of keyframes from each shot; and

altering the number of keyframes in response to user input.

35. The method of claim 34, wherein altering the number of keyframes in response to user input includes the step of removing one or more keyframes from the predetermined number of selected keyframes.

36. The method of claim 34, wherein altering the number of keyframes in response to user input includes the step of adding one or more keyframes to the predetermined number of selected keyframes.