Structural analysis of videos with hidden markov models and dynamic programming

• US 6,865,226 B2
• Filed: 12/05/2001
• Issued: 03/08/2005
• Est. Priority Date: 12/05/2001
• Status: Expired due to Fees

• Current Assignee: Trustees Of Columbia University In The City Of New York (Columbia University), Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Xie, Lexing, Chang, Shih-Fu, Sun, Huifang, Divakaran, Ajay
• Primary Examiner(s): PHILIPPE, GIMS S
• Application Number:
  US10/005,623
• Publication Number:
  US 20030103565A1
• Time in Patent Office: 1,189 Days
• Field of Search: 375/240.08, 375/240.24, 375/240.23, 375/240.04, 348/397.1, 348/699, 348/700, 348/722, 386/68, 386/52, 386/69, 382/243, 382/103
• US Class Current: 375/240.08
• CPC Class Codes: G06F 16/745 the internal structure of a single video sequence
• CPC Class Codes: G06F 16/7847 using low-level visual features of the video content
• CPC Class Codes: G06F 16/786 using motion, e.g. object motion or camera motion
• 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: G06V 20/52 Surveillance or monitoring of activities, e.g. for recognising suspicious objects recognising microscopic objects G06V20/69

Abstract

A method analyzes a high-level syntax and structure of a continuous compressed video according to a plurality of states. First, a set of hidden Markov models for each of the states is trained with a training video segmented into known states. Then, a set of domain specific features are extracted from a fixed-length sliding window of the continuous compressed video, and a set of maximum likelihoods is determined for each set of domain specific features using the sets of trained hidden Markov models. Finally, dynamic programming is applied to each set of maximum likelihoods to determine a specific state for each fixed-length sliding window of frames of the compressed video.

Claims

1. A method for analyzing a continuous compressed video according to a plurality of states, comprising:

extracting a set of domain specific features from fixed-length sliding windows of frames of the continuous compressed video;

determining a set of maximum likelihoods for each set of domain specific features using a plurality of sets of trained hidden Markov models; and

applying dynamic programming to each set of maximum likelihoods to determine a specific state for each fixed-length sliding window of frames of the continuous compressed video.

2. The method of claim 1 wherein the extracting further comprises:

determining a dominant color ratio from each frame; and

determining an average motion intensity from each frame.

3. The method of claim 2 wherein the dominant color ratio is ${\eta }_{}$

c=|Pd||P|,

where P is a set of all pixels in each frame, and P_d is a set of pixels with a dominant color in each frame.

4. The method of claim 2 wherein the average motion intensity is $m=\frac{1}{|\Phi }$

|⁢

∑

Φ

⁢

vx2+⁢

vy2,

where Φ

represents a number of macro-blocks in each frame, and {right arrow over (ν

)}=[ν

_x, ν

_y] is a motion vector for each macro-block.

5. The method of claim 1 wherein a length of the window is in the range of one to five seconds.

6. The method of claim 1 wherein the window slides forward in one second steps.

7. The method of claim 1 further comprising:

smoothing the set of domain specific features with a temporal low-pass filter; and

normalizing the set of domain specific features with regard to a mean and variance of the entire set of domain specific features.

8. The method of claim 1 wherein the plurality of sets of hidden Markov models are trained with a training video having frames with known states.

9. The method of claim 1 wherein each set includes six hidden Markov models.

10. The method of claim 1 wherein the states are P and B, and the sets of hidden Markov models are

Ω

{circumflex over (=)}Ω

_P∪

Ω

_B={P1 . . . Pn;

B1 . . . Bn}.

11. The method of claim 10 wherein the set of maximum likelihood for each set of domain specific features is

Q_P(t)=max {Q_Pi(t)}, Q_B(t)=max {Q_Ni(t)}, i=1, . . . , 6.

12. The method of claim 1 wherein the domain specific features are modeled as a mixture of Gaussian distributions.

13. The method of claim 1 wherein each set of the maximum likelihoods form a trellis grid, and the specific state corresponds to an optimal path through the lattice grid.

14. The method of claim 13 wherein the trellis grid corresponds to states of the sets of hidden Markov models and state transitions of the hidden Markov models.

15. The method of claim 1 further comprising:

segmenting the continuous compressed video according to the specific states.

16. The method of claim 1 wherein the continuous compressed video is of a sporting event, and a dominant color ratio for each frame is determined from a color of a playing field, and an average motion intensity is determined from motion vectors of macro blocks of each frame.

17. The method of claim 16 wherein the sporting event is a soccer game, and the color is green.

18. The method of claim 16 wherein the states are play and break.

19. The method of claim 10 wherein the continuous compressed video is of a soccer game, and a dominant color ratio for each frame is determined from a green color of a playing field, and an average motion intensity is determined from motion vectors of macro blocks of each frame, and the states P and B are play and break in the soccer game.