Method and apparatus for automatically summarizing video

• US 8,879,862 B2
• Filed: 02/18/2014
• Issued: 11/04/2014
• Est. Priority Date: 04/12/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Yagnik, Jay N.
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): HU, FRED H.
• Application Number:
  US14/183,070
• Publication Number:
  US 20140161351A1
• Time in Patent Office: 259 Days
• Field of Search: None
• US Class Current: 382/236
• 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/7834 using audio features
• CPC Class Codes: G06F 16/785 using colour or luminescence
• CPC Class Codes: G06F 2218/12 Classification; Matching
• 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

Abstract

One embodiment of the present invention provides a system that automatically produces a summary of a video. During operation, the system partitions the video into scenes and then determines similarities between the scenes. Next, the system selects representative scenes from the video based on the determined similarities, and combines the selected scenes to produce the summary for the video.

Claims

1. A method for automatically producing a summary of a video, comprising:

partitioning a video into scenes using a frame-similarity matrix, each element in the frame-similarity matrix representing a distance between feature vectors of a corresponding pair of frames;

generating a scene-similarity matrix comprising a plurality of elements based on the frame-similarity matrix, each element of the scene-similarity matrix representing a measure of similarity between different scenes of the video;

determining, by a processor, an importance score for each scene based on the scene-similarity matrix, motion data associated with the scene, and audio data associated with the scene, an importance score for a scene indicating a relative importance of the scene, wherein the importance score increases responsive to the scene having a high similarity with other scenes in the video and increases responsive to the scene having a high distance from a measure of a mean cohesiveness of the video;

selecting representative scenes from the video based on the determined importance scores; and

combining selected scenes to produce the summary for the video.

2. The method of claim 1, wherein each feature vector comprises a color histogram of a frame.

3. The method of claim 1, wherein an element in the frame-similarity matrix comprises a distance between two feature vectors F_A and F_B, wherein the distance is calculated as

4. The method of claim 1, wherein the scene-similarity matrix is generated by detecting shot boundaries using an adaptive-threshold technique which computes a distance between feature vectors for successive frames divided by a maximum distance between successive feature vectors in a preceding window of frames.

5. The method of claim 1, wherein selecting a scene from the video comprises clustering similar scenes together and selecting at most one scene from each cluster.

6. The method of claim 1, wherein selecting a representative scene from the video comprises using a dynamic-programming technique to select the scene.

7. The method of claim 1, wherein selecting representative scenes from the video comprises selecting the representative scenes based on a total importance score for the selected scenes subject to a time constraint.

21. The method of claim 1, wherein the distance from the measure of the mean cohesiveness of the video indicates how distinct the scene is from other scenes in the video.

8. A non-transitory computer-readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method for automatically producing a summary of a video, the method comprising:

partitioning a video into scenes using a frame-similarity matrix, each element in the frame-similarity matrix representing a distance between feature vectors of a corresponding pair of frames;

generating a scene-similarity matrix comprising a plurality of elements based on the frame-similarity matrix, each element of the scene-similarity matrix representing a measure of similarity between different scenes of the video;

determining an importance score for each scene based on the scene-similarity matrix, motion data associated with the scene, and audio data associated with the scene, an importance score for a scene indicating a relative importance of the scene, wherein the importance score increases responsive to the scene having a high similarity with other scenes in the video and increases responsive to the scene having a high distance from a measure of a mean cohesiveness of the video;

selecting representative scenes from the video based on the determined importance scores; and

combining selected scenes to produce the summary for the video.

9. The computer-readable storage medium of claim 8, wherein each feature vector comprises a color histogram of a frame.

10. The computer-readable storage medium of claim 8, wherein an element in the frame-similarity matrix comprises a distance between two feature vectors F_A and F_B, wherein the distance is calculated as

11. The computer-readable storage medium of claim 8, wherein the scene-similarity matrix is generated by detecting shot boundaries using an adaptive-threshold technique which computes a distance between feature vectors for successive frames divided by a maximum distance between successive feature vectors in a preceding window of frames.

12. The computer-readable storage medium of claim 8, wherein selecting a scene from the video comprises clustering similar scenes together and selecting at most one scene from each cluster.

13. The computer-readable storage medium of claim 8, wherein selecting a representative scene from the video comprises using a dynamic-programming technique to select the scene.

14. The computer-readable storage medium of claim 8, wherein selecting representative scenes from the video comprises selecting the representative scenes based on a total importance score for the selected scenes subject to a time constraint.

15. An apparatus that automatically produces a summary of a video, comprising:

a non-transitory computer readable storage medium storing instructions executable to perform steps comprising;

partitioning a video into scenes using a frame-similarity matrix, each element in the frame-similarity matrix representing a distance between feature vectors of a corresponding pair of frames;

generating a scene-similarity matrix comprising a plurality of elements based on the frame-similarity matrix, each element of the scene-similarity matrix representing a measure of similarity between different scenes of the video;

determining an importance score for each scene based on the scene-similarity matrix, motion data associated with the scene, and audio data associated with the scene, an importance score for a scene indicating a relative importance of the scene, wherein the importance score increases responsive to the scene having a high similarity with other scenes in the video and increases responsive to the scene having a high distance from a measure of a mean cohesiveness of the video;

selecting representative scenes from the video based on the determined importance scores; and

combining selected scenes to produce the summary for the video; and

a processor configured to execute the instructions.

16. The apparatus of claim 15, wherein each feature vector comprises a color histogram of a frame.

17. The apparatus of claim 15, wherein an element in the frame-similarity matrix comprises a distance between two feature vectors F_A and F_B, wherein the distance is calculated as

18. The apparatus of claim 15, wherein the scene-similarity matrix is generated by detecting shot boundaries using an adaptive-threshold technique which computes a distance between feature vectors for successive frames divided by a maximum distance between successive feature vectors in a preceding window of frames.

19. The apparatus of claim 15, wherein selecting a scene from the video comprises clustering similar scenes together and selecting at most one scene from each cluster.

20. The apparatus of claim 15, wherein selecting representative scenes from the video comprises selecting the representative scenes based on a total importance score for the selected scenes subject to a time constraint.