Systems and methods for automatically editing a video
View Patent ↗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.
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 N−1 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 N−1 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 N−1 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:
ρ
(
m
,
v
,
θ
)
=
ρ
(
mood
,
motion
(
θ
)
)
=
E
(
(
mood
-
mood
_
)
(
motion
(
θ
)
-
motion
(
θ
)
_
)
)
D
(
mood
)
D
(
motion
(
θ
)
)
;
and
wherein E(x) and D(x) respectively denote mean and variance values of sequence x, superscript θ representing a corresponding sequence that comprises a selected sub-sequence of an original sequence.
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:
H
(
m
,
v
,
x
)
=
k
1
[
-
1
log
K
(
SC
)
∑
i
=
0
K
(
SC
)
-
1
p
i
log
p
i
]
+
k
2
[
-
1
log
K
(
SH
)
∑
j
=
0
K
(
SH
)
-
1
q
j
log
q
j
]
,
wherein
p
i
=
∑
M
i
(
SC
)
M
i
+
1
(
SC
)
-
1
x
i
M
,
M
i
(
SC
)
=
{
s
∈
SC
,
s
<
i
}
,
q
j
=
∑
M
j
(
SH
)
M
j
+
1
(
SH
)
-
1
x
j
M
,
M
j
(
SH
)
=
{
s
∈
SH
,
s
<
j
}
,
and
wherein |•| denotes number of elements in a finite set.
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:
min
F
(
m
,
v
,
x
)
=
αρ
+
β
I
+
γ
H
s
.
t
.
∑
i
=
0
N
-
1
x
i
=
M
,
x
i
∈
{
0
,
1
}
.
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:
H
(
SC
)
(
m
,
v
,
θ
)
=
H
(
SC
(
θ
)
)
=
-
1
log
K
(
SC
)
∑
i
=
0
K
(
SC
)
-
1
p
i
log
p
i
where
p
i
=
#
of
selected
subshot
in
Scene
i
M
.
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 (θ) ).
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:
ρ
(
m
,
v
,
θ
)
=
ρ
(
mood
,
motion
(
θ
)
)
=
E
(
(
mood
-
mood
_
)
(
motion
(
θ
)
-
motion
(
θ
)
_
)
)
D
(
mood
)
D
(
motion
(
θ
)
)
;
and
wherein E(x) and D(x) respectively denote mean and variance values of sequence x, superscript θ representing a corresponding sequence that comprises a selected sub-sequence of an original sequence.
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:
min
F
(
m
,
v
,
x
)
=
αρ
+
β
I
+
γ
H
s
.
t
.
∑
i
=
0
N
-
1
x
i
=
M
,
x
i
∈
{
0
,
1
}
.
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 (θ) ).
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.