Video structuring by probabilistic merging of video segments

• US 7,296,231 B2
• Filed: 08/09/2001
• Issued: 11/13/2007
• Est. Priority Date: 08/09/2001
• Status: Expired due to Term

• Current Assignee: Monument Peak Ventures, LLC (Dominion Harbor Enterprises, LLC)
• Original Assignee: Eastman Kodak Company
• Inventors: Loui, Alexander C., Gatica-Perez, Daniel
• Primary Examiner(s): Lo; Weilun
• Assistant Examiner(s): ENGLAND, SARA M
• Application Number:
  US09/927,041
• Publication Number:
  US 20030058268A1
• Time in Patent Office: 2,287 Days
• Field of Search: 345/726, 345/723, 345/719, 345/328, 382/173, 382/236, 382/272, 382/226, 382/228, 382/284, 715/723, 348/584, 348/598
• US Class Current: 715/723
• CPC Class Codes: G06F 16/745 the internal structure of a single video sequence
• CPC Class Codes: G06F 16/785 using colour or luminescence
• 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

A method for structuring video by probabilistic merging of video segments includes the steps of obtaining a plurality of frames of unstructured video; generating video segments from the unstructured video by detecting shot boundaries based on color dissimilarity between consecutive frames; extracting a feature set by processing pairs of segments for visual dissimilarity and their temporal relationship, thereby generating an inter-segment visual dissimilarity feature and an inter-segment temporal relationship feature; and merging video segments with a merging criterion that applies a probabilistic analysis to the feature set, thereby generating a merging sequence representing the video structure. The probabilistic analysis follows a Bayesian formulation and the merging sequence is represented in a hierarchical tree structure.

Claims

1. A method for structuring video by probabilistic merging of video segments, said method comprising the steps of:

a) obtaining a plurality of frames of unstructured video;

b) generating video segments from the unstructured video by detecting shot boundaries based on color dissimilarity between consecutive frames;

c) extracting a feature set by processing pairs of said segments, said extracting generating an inter-segment color dissimilarity feature and an inter-segment temporal relationship feature of each said pair of segments, said inter-segment temporal relationship feature including metrics of temporal separation between the segments of the respective said pair and accumulated duration of the segments of the respective said pair; and

d) merging video segments with a merging criterion that applies a probabilistic analysis to the features of the feature set, thereby generating a merging sequence representing the video structure.

2. The method as claimed in claim 1 wherein the processing of pairs of segments for visual dissimilarity in step c) comprises the steps of computing a mean color histogram for each segment and computing a visual dissimilarity feature metric from the difference between mean color histograms for pairs of segments.

3. The method as claimed in claim 1 wherein representing the merging sequence is represented in a hierarchical tree structure.

4. The method as claimed in claim 1 wherein step b) comprises the steps of:

generating color histograms from the consecutive frames;

generating a difference signal from the color histograms that represents the color dissimilarity between consecutive frames; and

thresholding the difference signal based on a mean dissimilarity determined over a plurality of frames, thereby producing a signal that indicates an existence of a shot boundary.

5. The method as claimed in claim 4 wherein the difference signal is based on a mean dissimilarity determined over a plurality of frames centered on one of the consecutive frames.

6. The method as claimed in claim 4 further including the step of morphologically transforming the threshold difference signal with a pair of structuring elements that eliminate the presence of multiple adjacent shot boundaries.

7. The method as claimed in claim 1 wherein said extracting of said inter-segment temporal relationship feature of each said pair of segments including determining a number of frames separating the respective said pair of segments and determining an accumulated number of frames in said segments of the respective said pair of segments.

8. The method as claimed in claim 1 wherein step d) comprises the steps of:

generating parametric mixture models to represent class-conditional densities of inter-segment features of the feature set, said parametric mixture models being statistical models; and

applying the merging criterion to the parametric mixture models.

9. The method as claimed in claim 8 wherein step d) is performed in a hierarchical queue and comprises the steps of:

initializing the queue by introducing each feature into the queue with a priority equal to the probability of merging each corresponding pair of segments;

depleting the queue by merging the segments if the merging criterion is met; and

updating the model of the merged segment and then updating the queue based upon the updated model.

10. A method for structuring video by probabilistic merging of video segments, said method comprising the steps of:

a) obtaining a plurality of frames of unstructured video;

b) generating video segments from the unstructured video by detecting shot boundaries based on color dissimilarity between consecutive frames;

c) extracting a feature set by processing pairs of said segments, said extracting generating an inter-segment color dissimilarity feature and an inter-segment temporal feature of each said pair of segments, said inter-segment temporal feature including metrics of temporal seperation between the segments of the respective said pair and accumulated duration of the segments of the respective said pair; and

d) merging video segments with a merging criterion that applies a probabilistic analysis to the features of the feature set, thereby generating a merging sequence representing the video structure;

wherein step d) comprises the steps of;

generating parametric mixture models to represent class-conditional densities of inter-segment features of the feature set, said parametric mixture models being statistical models; and

applying the merging criterion to the parametric mixture models.

11. The method as claimed in claim 10 wherein the processing of pairs of segments for their temporal relationship in step c) comprises the processing of pairs of segments for a temporal separation between pairs of segments and for an accumulated temporal duration of pairs of segments.

12. The method as claimed in claim 10 wherein step d) is performed in a hierarchical queue and comprises the steps of:

initializing the queue by introducing each feature into the queue with a priority equal to the probability of merging each corresponding pair of segments;

depleting the queue by merging the segments if the merging criterion is met; and

updating the model of the merged segment and then updating the queue based upon the updated model.

13. A computer storage medium having instructions stored therein for causing a computer to perform the acts of:

generating video segments from unstructured video by detecting shot boundaries based on color dissimilarity between consecutive frames;

extracting a feature set by processing pairs of segments, said extracting generating an inter-segment color dissimilarity feature and an inter-segment temporal feature of each said pair of segments, said inter-segment temporal feature including metrics of temporal separation between the segments of the respective said pair and accumulated duration of the segments of the respective said pair; and

merging video segments with a merging criterion that applies a probabilistic analysis to the features of the feature set, thereby generating a merging sequence representing the video structure;

wherein said merging further comprises the steps of;

generating statistical models of the feature set; and

applying the merging criterion to the statistical models.

14. A method for structuring video by probabilistic merging of video segments, said method comprising the steps of:

a) obtaining a plurality of frames of unstructured video;

b) generating video segments from the unstructured video by detecting shot boundaries based on color dissimilarity between consecutive video frames;

c) extracting a feature set by processing pairs of segments, said extracting generating an inter-segment color dissimilarity feature and an inter-segment temporal feature of each said pair of segments, said inter-segment temporal feature including metrics of temporal separation between the segments of the respective said pair and accumulated duration of the segments of the respective said pair;

d) generating a parametric mixture model of the inter-segment features comprising the feature set, said parametric mixture model being a statistical model; and

e) merging video segments with a merging criterion that applies a probabilistic Bayesian analysis to the parametric mixture model, thereby generating a merging sequence representing the video structure.

15. The method as claimed in claim 14 wherein the processing of pairs of segments for visual dissimilarity in step c) comprises the steps of computing a mean color histogram for each segment and computing a visual dissimilarity feature metric from the difference between mean color histograms for pairs of segments.

16. The method as claimed in claim 14 wherein the processing of pairs of segments for their temporal relationship in step c) comprises the processing of pairs of segments for a temporal separation between pairs of segments and for an accumulated temporal duration of pairs of segments.

17. The method as claimed in claim 14 wherein the parametric mixture model generated in step d) represents class-conditional densities of the inter-segment features comprising the feature set.

18. The method as claimed in claim 14 wherein step e) is performed in a hierarchical queue and comprises the steps of:

initializing the queue by introducing each feature into the queue with a priority equal to the probability of merging each corresponding pair of segments;

depleting the queue by merging the segments if the merging criterion is met; and

updating the model of the merged segment and then updating the queue based upon the updated model.

19. The method as claimed in claim 14 wherein the merging sequence is represented in a hierarchical tree structure that includes a frame extracted from each segment and displayed at each node of the tree.

20. A computer storage medium having instructions stored therein for causing a computer to perform acts for structuring video by probabilistic merging of video segments, the acts including:

obtaining a plurality of frames of unstructured video;

generating video segments from the unstructured video by detecting shot boundaries based on color dissimilarity between consecutive video frames;

extracting a feature set by processing pairs of segments, said extracting generating an inter-segment color dissimilarity feature and an inter-segment temporal feature of each said pair of segments, said inter-segment temporal feature including metrics of temporal separation between the segments of the respective said pair and accumulated duration of the segments of the respective said pair;

generating a parametric mixture model of the inter-segment features comprising the feature set, said parametric mixture model being a statistical model; and

merging video segments with a merging criterion that applies a probabilistic Bayesian analysis to the parametric mixture model, thereby generating a merging sequence representing the video structure.

21. A method for structuring video by probabilistic merging of video segments, said method comprising the steps of:

a) obtaining a plurality of frames of unstructured video;

b) generating video segments from the unstructured video by detecting shot boundaries based on color dissimilarity between consecutive video frames;

c) extracting a feature set by processing pairs of segments, said extracting generating an inter-segment color dissimilarity feature and an inter-segment temporal feature of each said pair of segments, said inter-segment temporal feature including metrics of temporal separation between the segments of the respective said pair and accumulated duration of the segments of the respective said pair;

d) merging adjacent video segments with a merging criterion that applies a probabilistic Bayesian analysis to parametric mixture models derived from the feature set, said parametric mixture models being statistical models, thereby generating a merging sequence; and

e) representing the merging sequence in a hierarchical tree structure.

22. The method as claimed in claim 21 wherein representing the merging sequence in a hierarchical tree structure includes displaying a frame extracted from each segment.

23. A computer storage medium having instructions stored therein for causing a computer to perform probabilistic merging of video segments, said instructions performing the acts of:

a) obtaining a plurality of frames of unstructured video;

b) generating video segments from the unstructured video by detecting shot boundaries based on color dissimilarity between consecutive video frames;

c) extracting a feature set by processing pairs of segments, said extracting generating an inter-segment color dissimilarity feature and an inter-segment temporal feature of each said pair of segments, said inter-segment temporal feature including metrics of temporal separation between the segments of the respective said pair and accumulated duration of the segments of the respective said pair;

d) merging adjacent video segments with a merging criterion that applies a probabilistic Bayesian analysis to parametric mixture models derived from the feature set, said parametric mixture models being a statistical models, thereby generating a merging sequence; and

e) representing the merging sequence in a hierarchical tree structure.

24. A method for structuring video by probabilistic merging of video segments, said method comprising the steps of:

generating video segments from a plurality of frames of unstructured video by detecting shot boundaries based on color dissimilarity between consecutive frames;

computing an inter-segment color dissimilarity feature and an inter-segment temporal relationship feature of each said pair of segments, said inter-segment temporal relationship feature including metrics of temporal separation between the segments of the respective said pair and accumulated duration of the segments of the respective said pair; and

d) merging video segments with a merging criterion that applies a probabilistic analysis to said features, thereby generating a merging sequence representing the video structure.

25. The method of claim 24 wherein said computing of said inter-segment temporal relationship feature of each said pair of segments further comprises determining a number of frames separating the respective said pair of segments and determining an accumulated number of frames in said segments of the respective said pair of segments.