Annotating video segments using feature rhythm models

• US 8,126,262 B2
• Filed: 06/18/2007
• Issued: 02/28/2012
• Est. Priority Date: 06/18/2007
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kender, John R.
• Primary Examiner(s): DULANEY, KATHLEEN YUAN
• Application Number:
  US11/764,473
• Publication Number:
  US 20080310709A1
• Time in Patent Office: 1,716 Days
• Field of Search: 382/156, 382/159, 382/190, 715/723, 706/12, 706/20, 700/47, 348/700
• US Class Current: 382/156
• CPC Class Codes: G06F 16/70 of video data
• 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
• CPC Class Codes: H04N 5/147 Scene change detection

Abstract

Each video segment in a plurality of video segments is annotated with an indicator of the likelihood that the respective video segment shows a particular feature. The plurality of video segments forms an episode of interest from a given video domain. Initial feature probabilities are calculated for respective ones of the plurality of video segments using a machine learning algorithm. Each initial feature probability indicates the likelihood that its respective video segment shows the particular feature. Refined feature probabilities are determined for respective ones of the plurality of video segments by finding the most probable state sequence in a finite state machine. This is accomplished at least in part using the determined initial feature probabilities. Finally, each of the video segments in the plurality of vides segments is annotated with its respective refined feature probability.

Claims

1. A method of annotating each video segment in a plurality of video segments with an indicator of the likelihood that the respective video segment shows a particular feature, the plurality of video segments forming an episode of interest from a given video domain, the method comprising the steps of:

determining initial feature probabilities for respective ones of the plurality of video segments using a machine learning algorithm, an initial feature probability for a given video segment indicating the likelihood that the given video segment shows the particular feature;

determining refined feature probabilities for respective ones of the plurality of video segments, the refined feature probabilities determined by finding the most probable state sequence in a finite state machine comprising a plurality of states, a given state in the plurality of states specifying whether the particular feature is shown in each of two or more of the plurality of video segments, wherein the determined initial feature probabilities are applied as incoming probabilities to the finite state machine; and

annotating each of the video segments in the plurality of video segments with the refined feature probability for the respective video segment.

2. The method of claim 1, wherein the machine learning algorithm comprises a Neural Network.

3. The method of claim 1, wherein the machine learning algorithm comprises a Bayesian Network.

4. The method of claim 1, wherein the machine learning algorithm comprises a Support Vector Machine.

5. The method of claim 4, wherein the step of determining initial feature probabilities for respective ones of the video segments comprises converting results derived from the one or more machine learning algorithms to probabilities.

6. The method of claim 1, wherein the particular feature belongs to a predetermined ontology of features.

7. The method of claim 1, wherein the finite state machine comprises a plurality of transition probabilities determined by applying an n-th order Markov dependency to a manner in which the particular feature is shown in one or more training episodes, the one or more training episodes from the same video domain as the episode of interest, and n being an integer.

8. The method of claim 7, wherein n is greater than one.

9. The method of claim 7, wherein n is equal to three.

10. The method of claim 1, wherein the step of determining the most probable state sequence in the finite state machine comprises applying a Viterbi Algorithm to the finite state machine.

11. The method of claim 1, wherein the given state has a corresponding representation comprising:

at least a first portion indicative of whether the particular feature is shown in at least a first one of the plurality of video segments; and

at least a second portion indicative of whether the particular feature is shown in at least a second one of the plurality of video segments.

12. The method of claim 1, wherein the given state has a corresponding representation comprising a plurality of bits, each of the plurality of bits being indicative of whether the particular feature is shown in a corresponding one of the plurality of video segments.

13. The method of claim 1, further comprising the step of detecting at least one of repetition of the particular feature and alternation of the particular feature.

14. The method of claim 1, wherein at least a first state in the plurality of states is associated with repetition of the particular feature and wherein at least a second state in the plurality of states is associated with alternation of the particular feature.

15. An article of manufacture comprising a non-transitory processor-readable storage medium storing one or more programs for annotating each video segment in a plurality of video segments with an indicator of the likelihood that the respective video segment shows a particular feature, the plurality of video segments forming an episode of interest in a given video domain, wherein the one or more programs, when executed by a data processing system comprising a memory and a processor coupled to the memory, cause the data processing system to perform at least the steps of:

determining initial feature probabilities for respective ones of the plurality of video segments using a machine learning algorithm, an initial feature probability for a given video segment indicating the likelihood that the given video segment shows the particular feature;

determining refined feature probabilities for respective ones of the plurality of video segments, the refined feature probabilities determined by finding the most probable state sequence in a finite state machine comprising a plurality of states, a given state in the plurality of states specifying whether the particular feature is shown in each of two or more of the plurality of video segments, wherein the determined initial feature probabilities are applied as incoming probabilities to the finite state machine; and

annotating each video segment in the plurality of video segments with the refined feature probability for the respective video segment.

16. The article of manufacture of claim 15, wherein the finite state machine comprises a plurality of transition probabilities determined by applying an n-th order Markov dependency to a manner in which the particular feature is shown in one or more training episodes, the one or more training episodes from the same video domain as the episode of interest, and n being an integer.

17. The article of manufacture of claim 15, wherein the step of determining the most probable state sequence in the finite state machine comprises applying a Viterbi Algorithm to the finite state machine.

18. A data processing system comprising a memory and a data processor coupled to the memory for annotating each video segment in a plurality of video segments with an indicator of the likelihood that the respective video segment shows a particular feature, the plurality of video segments forming an episode of interest in a given video domain, wherein the data processing system performs the steps of:

determining initial feature probabilities for respective ones of the plurality of video segments using a machine learning algorithm, an initial feature probability for a given video segment indicating the likelihood that the given video segment shows the particular feature;

determining refined feature probabilities for respective ones of the plurality of video segments, the refined feature probabilities determined by finding the most probable state sequence in a finite state machine comprising a plurality of states, a given state in the plurality of states specifying whether the particular feature is shown in each of two or more of the plurality of video segments, wherein the determined initial feature probabilities are applied as incoming probabilities to the finite state machine; and

annotating each video segment in the plurality of video segments with the refined feature probability for the respective video segment.

19. The data processing system of claim 18, wherein the data processing system receives at least a portion of the finite state machine from hardware external to the data processing system.

20. The data processing system of claim 18, wherein the finite state machine comprises a plurality of transition probabilities determined by applying an n-th order Markov dependency to a manner in which the particular feature is shown in one or more training episodes, the one or more training episodes from the same video domain as the episode of interest, and n being an integer.