Method and apparatus for automatically summarizing video

• US 8,699,806 B2
• Filed: 06/15/2006
• Issued: 04/15/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:
  US11/454,386
• Publication Number:
  US 20070245242A1
• Time in Patent Office: 2,861 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:

in a computer system, performing the operations of;

receiving the video;

partitioning the video into scenes comprising a plurality of frames, wherein

partitioning the video into scenes comprises;

extracting feature vectors for sampled frames in the video;

detecting shot boundaries based on distances between feature vectors for successive sampled frames

producing a frame-similarity matrix, wherein each element in the frame-similarity matrix represents a distance between feature vectors for a corresponding pair of sampled frames;

using the frame-similarity matrix and the detected shot boundaries to compute a shot-similarity matrix, wherein each element in the shot-similarity matrix represents a similarity between a corresponding pair of shots; and

determining scene boundaries by selectively merging successive shots together based on the computed similarities between the successive shots;

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

determining an importance score for each scene based on the scene-similarity matrix and a distance from the scene to an average scene of the video, the importance score for a scene indicating a relative importance of the scene and wherein the importance score is increased responsive to the scene having a high similarity with other scenes in 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 extracting a feature vector for a sampled frame involves producing a color histogram for the sampled frame.

3. The method of claim 1, wherein the distance between two feature vectors F_A and F_B is

4. The method of claim 1, wherein detecting the shot boundaries involves 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 scene from the video comprises using a dynamic-programming technique to select the scene.

14. The method of claim 1, wherein selecting the representative scenes comprises selecting the representative scenes based o n a total importance score for the selected scenes subject to a time constraint.

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

receiving the video at the computer;

partitioning the video into scenes comprising a plurality of frames, wherein

partitioning the view into scenes comprise;

extracting feature vectors for sampled frames in the video;

detecting shot boundaries based on distances between feature vectors for successive sampled frames;

producing a frame-similarity matrix, wherein each element in the frame-similarity matrix represents a distance between feature vectors for a corresponding pair of sampled frames;

using the frame-similarity matrix and the detected shot boundaries to compute a shot-similarity matrix, wherein each element in the shot-similarity matrix represents a similarity between a corresponding pair of shots; and

determining scene boundaries by selectively merging successive shots together based on the computed similarities between the successive shots;

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

determining an importance score for each scene based on the scene-similarity matrix and a distance from the scene to an average scene of the video, the importance score for a scene indicating a relative importance of the scene and wherein the importance score is increased responsive to the scene having a high similarity with other scenes in 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.

8. The computer-readable storage medium of claim 7, wherein extracting a feature vector for a sampled frame involves producing a color histogram for the sampled frame.

9. The computer-readable storage medium of claim 7, wherein the distance between two feature vectors F_A and F_B is

10. The computer-readable storage medium of claim 7, wherein detecting the shot boundaries involves 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.

11. The computer-readable storage medium of claim 7, wherein selecting the representative scenes involves clustering similar scenes together and selecting a scene from the video comprising clustering similar scenes together and selecting at most one scene from each cluster.

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

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

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

partitioning the video into scenes comprising a plurality of frames, wherein partitioning the video into scenes comprises;

extracting feature vectors for sampled frames in the video;

detecting shot boundaries based on distances between feature vectors for successive sampled frames;

producing a frame-similarity matrix, wherein each element in the frame-similarity matrix represents a distance between feature vectors for a corresponding pair of sampled frames;

using the frame-similarity matrix and the detected shot boundaries to compute a shot-similarity matrix, wherein each element in the shot-similarity matrix represents a similarity between a corresponding pair of shots; and

;

determining scene boundaries by selectively merging successive shots together based on the computed similarities between the successive shots;

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

determining an importance score for each scene based on the scene-similarity matrix and a distance from the scene to an average scene of the video, the importance score for a scene indicating a relative importance of the scene and wherein the importance score is increased responsive to the scene having a high similarity with other scenes in 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 executable instructions.