Systems and methods for automatically editing a video

• US 20040085341A1
• Filed: 11/01/2002
• Published: 05/06/2004
• Est. Priority Date: 11/01/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Li, Mingjing, Hua, Xian-Sheng, Zhang, Hong-Jiang, Lu, Lie, Ma, Yu-Fei
• Granted Patent: US 7,127,120 B2
• Time in Patent Office: Days
• US Class Current: 345/723
• CPC Class Codes: G11B 27/034 on discs G11B27/036, G11B27/038 take precedence
• CPC Class Codes: G11B 27/28 by using information signals recorded by the same method as the main recording G11B27/22 takes precedence

Abstract

Systems and methods to automatically edit a video to generate a video summary are described. In one aspect, sub-shots are extracted from the video. Importance measures are calculated for at least a portion of the extracted sub-shots. Respective relative distributions for sub-shots having relatively higher importance measures as compared to importance measures of other sub-shots are determined. Based on the determined relative distributions, sub-shots that do not exhibit a uniform distribution with respect to other sub-shots in the particular ones are dropped. The remaining sub-shots are connected with respective transitions to generate the video summary.

Claims

1. A method for automatically editing a video data sequence to generate a video summary, the method comprising:

extracting sub-shots from the video data sequence;

calculating importance measures for at least a portion of the sub-shots;

identifying particular ones of the portion that have relatively higher importance measures as compared to importance measures of other sub-shots;

determining a relative distribution of each sub-shot in the particular ones;

based on relative distributions of each sub-shot of the particular ones, dropping sub-shots from the particular ones that do not have a uniform distribution with respect to other sub-shots in the particular ones; and

connecting remaining sub-shots in the particular ones with respective shot transitions to generate the video summary.

2. A method as recited in claim 1, wherein the portion of the sub-shots consists of substantially higher quality sub-shots of the sub-shots.

3. A method as recited in claim 1, wherein the operations of identifying, determining, and dropping are based on the following optimization:

min F(v,x)=β

I+γ

H s.t.Σ

_i=0<sup>N−

1</sup>x_i=M,x_iε

{0,1},

wherein I is the importance measure, H is the distribution uniformity measure, M is number of selected sub-shots.

4. A computer-readable medium comprising computer-program instructions for automatically editing a video data sequence to generate a video summary, the computer-program instructions being executable by a processor for:

extracting sub-shots from the video data sequence;

calculating importance measures for at least a portion of the sub-shots;

identifying particular ones of the portion that have relatively higher importance measures as compared to importance measures of other sub-shots;

determining a relative distribution of each sub-shot in the particular ones;

based on relative distributions of each sub-shot of the particular ones, dropping sub-shots from the particular ones that do not have a uniform distribution with respect to other sub-shots in the particular ones; and

connecting remaining sub-shots in the particular ones with respective shot transitions to generate the video summary.

5. A computer-readable medium as recited in claim 4, wherein the portion of the sub-shots consists of substantially higher quality sub-shots of the sub-shots.

6. A computer-readable medium as recited in claim 4, wherein the computer-program instructions for identifying, determining, and dropping are based on the following optimization:

min F(v,x)=β

I+γ

H s.t.Σ

_i=0<sup>N−

1</sup>x_i=M,x_iε

{0,1},

wherein I is the importance measure, H is the distribution uniformity measure, M is number of selected sub-shots.

7. A computing device for automatically editing a video data sequence to generate a video summary, the computing device comprising:

a processor; and

a memory coupled to the processor, the memory comprising computer-program instructions being executable by the processor for;

extracting sub-shots from the video data sequence;

calculating importance measures for at least a portion of the sub-shots;

identifying particular ones of the portion that have relatively higher importance measures as compared to importance measures of other sub-shots;

determining a relative distribution of each sub-shot in the particular ones;

based on relative distributions of each sub-shot of the particular ones, dropping sub-shots from the particular ones that do not have a uniform distribution with respect to other sub-shots in the particular ones; and

connecting remaining sub-shots in the particular ones with respective shot transitions to generate the video summary.

8. A computing device as recited in claim 7, wherein the portion of the sub-shots consists of substantially higher quality sub-shots of the sub-shots.

9. A computing device as recited in claim 7, wherein the instructions for identifying, determining, and dropping are based on the following optimization:

min F(v,x)=β

I+γ

H s.t.Σ

_i=0<sup>N−

1</sup>x_i=M,x_iε

{0,1},

wherein I is the importance measure, H is the distribution uniformity measure, M is number of selected sub-shots.

10. A method for automatically editing a video data sequence with respect to an independent music source, the method comprising:

extracting metadata from the video data sequence and the independent music source, the metadata comprising sub-shots and sub-musics;

calculating importance measures for at least a portion of the sub-shots;

identifying particular ones of the portion that have relatively higher importance measures as compared to importance measures of other sub-shots;

identifying respective moods for each of the sub-musics;

matching sub-shot motion intensity to sub-music moods to identify particular ones of the sub-shots;

aligning the particular ones with corresponding sub-musics; and

fusing aligned sub-shots with corresponding sub-musics to generate an auto-edited video.

11. A method as recited in claim 10, wherein extracting further comprises generating a frame difference curve to identify sub-shots in the video data sequence.

12. A method as recited in claim 10, wherein extracting further comprises:

analyzing the video data sequence in a first direction to identify shots and sub-shots; and

analyzing the video data sequence in a second direction to merge detected shots and sub-shots into one or more scenes.

13. A method as recited in claim 10, wherein aligning is based on sub-shot boundary and music beat alignment criteria, sub-shot boundary and sentence alignment criteria, and matching music mood with motion intensity alignment criteria.

14. A method as recited in claim 10, wherein extracting further comprises:

identifying shots, scenes, motion intensity and color entropy for sub-shots, and speech data from an audio channel of the video data sequence;

detecting sentence boundaries from the speech data; and

segmenting the independent music source into the sub-musics according to locations of respective beats.

15. A method as recited in claim 10, wherein after extracting and before matching, the method further comprises:

dropping low-quality sub-shots from the sub-shots to leave substantially higher quality sub-shots;

calculating importance measures for the substantially higher quality sub-shots;

calculating mood values for the sub-musics; and

wherein matching particular ones of the sub-shots to the sub-musics is further based on the importance measures, such that the particular ones are selected to be sub-shots with relatively higher importance measures as compared to importance measures of sub-shots not represented in the particular ones.

16. A method as recited in claim 10, wherein aligning further comprises changing lengths of one or more sub-shots so that corresponding sub-shot and sub-music lengths are substantially the same.

17. A method as recited in claim 10, wherein aligning is performed such that a sentence having a beginning and an end is not clipped, the sentence being detected in one or more sub-shots of the particular ones.

18. A method as recited in claim 10, wherein fusing is performed such that a sentence in an aligned sub-shot is not rendered in-audible with respect to a corresponding sub-music.

19. A method as recited in claim 10, wherein the video data sequence comprises video frames, and wherein after extracting and before matching, the method further comprises:

detecting visual quality of the video frames and/or sub-shots; and

dropping low-quality video frames and/or sub-shots to leave substantially higher quality video frames and/or sub-shots.

20. A method as recited in claim 19, wherein dropped frames and/or sub-shots comprise a dropped sequence of frames and/or sub-shots, and wherein low quality frames and/or sub-shots correspond to any combination of the following attributes:

poor color-entropy and abnormal motion analysis results.

21. A computer-readable medium comprising computer-executable instructions for editing a video data sequence with respect to an independent music source, the computer-executable instructions comprising instructions for:

extracting metadata from the video data sequence and the independent music source, the metadata comprising sub-shots and sub-musics;

calculating importance measures for at least a portion of the sub-shots;

identifying particular ones of the portion that have relatively higher importance measures as compared to importance measures of other sub-shots;

identifying respective moods for each of the sub-musics;

matching respective sub-shot motion intensities to the respective moods to identify particular ones of the sub-shots to align and fuse with the independent music source;

aligning the particular ones with corresponding sub-musics; and

fusing aligned sub-shots with corresponding sub-musics to generate an auto-edited video.

22. A computer-readable medium as recited in claim 21, wherein the instructions for extracting further comprise computer-program instructions for merging detected shots and sub-shots into one or more scenes.

23. A computer-readable medium as recited in claim 21, wherein after the instructions for extracting and before the instructions for matching, the computer-program instructions further comprise instructions for dropping low-quality sub-shots from the sub-shots to leave substantially higher quality sub-shots.

24. A computer-readable medium as recited in claim 21, wherein aligning is based on sub-shot boundary and music beat alignment criteria, sub-shot boundary and sentence alignment criteria, and matching music mood with motion intensity alignment criteria.

25. A computer-readable medium as recited in claim 21, wherein the instructions for aligning further comprise instructions for changing lengths of one or more sub-shots so that corresponding sub-shot and sub-music lengths are substantially the same.

26. A computer-readable medium as recited in claim 21, wherein aligning is performed such that a sentence having a beginning and an end is not clipped, the sentence being detected in one or more sub-shots of the particular ones.

27. A computer-readable medium as recited in claim 21, wherein the instructions for matching further comprise instructions for determining the respective moods according to:

28. A computer-readable medium as recited in claim 21, wherein the instructions for matching further comprise instructions for selecting the particular ones via use of mean deviation instead of entropy to measure distribution uniformity.

29. A computer-readable medium as recited in claim 21, wherein the instructions for matching further comprise instructions for selecting the particular ones such that they are uniformly distributed according to:

30. A computer-readable medium as recited in claim 21, wherein the instructions for matching further comprise instructions for selecting the particular ones according to:

31. A computer-readable medium as recited in claim 21, wherein the instructions for matching further comprise instructions for:

calculating respective importance measures for at least a portion of the sub-shots, each of the respective importance measures being based on corresponding sub-shot color entropy and camera motion type and speed; and

wherein the particular ones have respectively higher importance values as compared to sub-shots that are not one of the particular ones.

32. A computer-readable medium as recited in claim 31, wherein each of the respective importance measures are further based on whether speech was detected in the corresponding sub-shot.

33. A computer-readable medium as recited in claim 21, wherein the instructions for fusing further comprise generating a transition between two of the particular ones, the transition being based on a similarity of the two, the transition having a length.

34. A computer-readable medium as recited in claim 33, wherein the length is based on strength of beat in a corresponding sub-music of the sub-musics.

35. A computer-readable medium as recited in claim 21, wherein the video data sequence comprises video frames, and wherein after extracting and before matching, the method further comprises:

detecting visual quality of the video frames and/or sub-shots; and

dropping low-quality video frames and/or sub-shots to leave substantially higher quality video frames and/or sub-shots.

36. A computer-readable medium as recited in claim 35, wherein the dropped frames and/or sub-shots comprise a dropped sequence of frames and/or sub-shots, and wherein low quality frames and/or sub-shots correspond to any combination of the following attributes:

poor color-entropy and abnormal motion analysis results.

37. A computer-readable medium as recited in claim 21, wherein the instructions for matching further comprise instructions for selecting the particular ones such that they are uniformly distributed across a scene and/or a shot composed of multiple ones of the particular ones.

38. A computer-readable medium as recited in claim 37, wherein the instructions for selecting the particular ones such that they are uniformly distributed across the scene is based on the following:

39. A computer-readable medium as recited in claim 37, wherein the instructions for selecting the particular ones such that they are uniformly distributed across the shot is based on the following:

H^(SH)(m,v,θ

)=H(SH<sup>(θ

)</sup>).

40. A computing device for editing a video data sequence with respect to an independent music source, the computing device comprising:

a processor; and

a memory coupled to the processor, the memory comprising computer-program instructions executable by the processor for;

extracting metadata from the video data sequence and the independent music source, the metadata comprising sub-shots and sub-musics;

calculating importance measures for at least a portion of the sub-shots;

identifying particular ones of the portion that have relatively higher importance measures as compared to importance measures of other sub-shots;

calculating respective moods for each of the sub-musics based on respective sub-music beats;

matching respective sub-shot motion intensities to the respective moods to identify particular ones of the sub-shots to align and fuse with the independent music source;

aligning the particular ones with corresponding sub-musics such that the particular ones are uniformly distributed across shots and/or scenes represented by the particular ones; and

fusing aligned sub-shots with corresponding sub-musics to generate an auto-edited video.

41. A computing device as recited in claim 40, wherein aligning is based on sub-shot boundary and music beat alignment criteria, sub-shot boundary and sentence alignment criteria, and matching music mood with motion intensity alignment criteria.

42. A computing device as recited in claim 40, wherein the instructions for aligning further comprise instructions for changing lengths, while not clipping detected sentences, of one or more sub-shots so that corresponding sub-shot and sub-music lengths are substantially the same.

43. A computing device as recited in claim 40, wherein the instructions for matching further comprise instructions for determining the respective moods according to:

44. A computing device as recited in claim 40, wherein the instructions for matching further comprise instructions for selecting the particular ones via use of mean deviation instead of entropy to measure distribution uniformity.

45. A computing device as recited in claim 40, wherein the instructions for matching further comprise instructions for selecting the particular ones according to:

46. A computing device as recited in claim 40, wherein the instructions for matching further comprise instructions for:

calculating respective importance measures for at least a portion of the sub-shots, each of the respective importance measures being based on corresponding sub-shot color entropy and camera motion type and speed; and

wherein the particular ones have respectively higher importance values as compared to sub-shots that are not one of the particular ones.

47. A computing device as recited in claim 46, wherein each of the respective importance measures are further based on whether speech was detected in the corresponding sub-shot.

48. A computing device as recited in claim 40, wherein the instructions for fusing further comprise generating a transition between two of the particular ones, the transition being based on a similarity of the two, the transition having a length.

49. A computing device as recited in claim 48, wherein the length is based on strength of beat in a corresponding sub-music of the sub-musics.

50. A computing device as recited in claim 40, wherein the instructions for matching further comprise instructions for selecting the particular ones such that they are uniformly distributed across a scene and/or a shot composed of multiple ones of the particular ones.

51. A computing device as recited in claim 50, wherein the instructions for selecting the particular ones such that they are uniformly distributed across the shot is based on the following equation:

H^(SH)(m,v,θ

)=H(SH<sup>(θ

)</sup>).

52. A computing device as recited in claim 40, wherein the video data sequence comprises video frames, and wherein after extracting and before matching, the computer-program instructions further comprise instructions for:

detecting visual quality of the video frames and/or sub-shots; and

dropping low-quality video frames and/or sub-shots to leave substantially higher quality video frames and/or sub-shots.

53. A computing device as recited in claim 52, wherein dropped frames and/or sub-shots comprise a dropped sequence of frames and/or sub-shots, and wherein low quality frames and/or sub-shots correspond to any combination of the following attributes:

poor color-entropy and abnormal motion analysis results.

54. A computing device for editing a video data sequence with respect to an independent music source, the computing device comprising:

means for extracting metadata from the video data sequence and the independent music source, the metadata comprising sub-shots and sub-musics;

means for calculating importance measures for at least a portion of the sub-shots;

means for identifying particular ones of the portion that have relatively higher importance measures as compared to importance measures of other sub-shots;

means for calculating respective moods for each of the sub-musics based on respective sub-music beats;

means for matching respective sub-shot motion intensities to the respective moods to identify particular ones of the sub-shots to align and fuse with the independent music source;

means for aligning the particular ones with corresponding sub-musics such that the particular ones are uniformly distributed across shots and/or scenes represented by the particular ones; and

means for fusing aligned sub-shots with corresponding sub-musics to generate an auto-edited video.