System and method for adaptive video fast forward using scene generative models

• US 7,127,127 B2
• Filed: 03/04/2003
• Issued: 10/24/2006
• Est. Priority Date: 03/04/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Petrovic, Nemanja, Jojic, Nebojsa
• Primary Examiner(s): Alavi, Amir
• Application Number:
  US10/378,773
• Publication Number:
  US 20040175058A1
• Time in Patent Office: 1,330 Days
• Field of Search: 382/159, 382/162, 382/165, 382/172, 382/173, 382/181, 382/218, 382/219, 382/224, 382/228, 382/239, 382/243, 382/305, 345/716, 345/719, 345/720, 345/723, 375/240.01, 375/240.05, 375/240.06, 348/142, 348/153, 348/207, 715/723, 386/38, 386/117, 717/124
• US Class Current: 382/305
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• 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
• CPC Class Codes: G11B 27/105 of operating discs
• CPC Class Codes: G11B 27/28 by using information signals recorded by the same method as the main recording G11B27/22 takes precedence

Abstract

Computationally efficient searching, browsing and retrieval of one or more objects in a video sequence are accomplished using learned generative models. The generative model is trained on an automatically or manually selected query sequence from a sequence of image frames. The resulting generative model is then used in searching, browsing or retrieval of one or more similar or dissimilar image frames or sequences within the image sequence by determining the likelihood of each frame under the learned generative model. Further, this method allows for automatic separation and balancing of various causes of variability while analyzing the image sequence. The generative models are based on appearances of multiple, possibly occluding objects in an image sequence. Further, the search strategies used include clustering and intelligent fast forward through the image sequence. Additionally, in one embodiment, a fast forward speed is relative to the current frame likelihood under the learned generative model.

Claims

1. A system for automatically identifying image frames in an image sequence, comprising:

providing a first image sequence of at least one image frame;

automatically training a generative model on the first image sequence;

providing a second image sequence of at least one image frame; and

automatically determining a likelihood of at least one frame of the second image sequence under the generative model.

2. The system of claim 1 further comprising comparing the likelihood of the at least one frame of the second image sequence to a similarity threshold.

3. The system of claim 2 wherein image frames having a likelihood greater than the similarity threshold are determined to be similar to the first image sequence.

4. The system of claim 2 wherein image frames having a likelihood that is not greater than the similarity threshold are determined to be dissimilar to the first image sequence.

5. The system of claim 2 wherein the similarity threshold is adjustable.

6. The system of claim 2 further comprising an automatic likelihood-based variable speed playback of the second image sequence.

7. The system of claim 6 wherein the playback speed of the second image sequence decreases as the likelihood increases, and wherein the payback speed increases as the likelihood decreases.

8. The system of claim 1 wherein the generative model is based on color blobs for modeling objects in the first image sequence.

9. The system of claim 8 further comprising a predetermined number of color blobs to be used in learning the generative model.

10. The system of claim 8 wherein the number of color blobs to be used in learning the generative model is user adjustable.

11. The system of claim 8 wherein the number of color blobs to be used in learning the generative model is automatically probabilistically estimated.

12. The system of claim 8 wherein the generative model includes a set of model parameters that probabilistically represent the entire first image sequence.

13. The system of claim 12 wherein the model parameters include:

spatial covariance matrices of the blobs, with eigen values of the matrices controlling a size of each blob;

blob color distribution parameters; and

a scene background model.

14. The system of claim 1 wherein the generative model is capable of modeling multiple objects in the first image sequence.

15. The system of claim 14 wherein the generative model is capable of modeling occluding objects in the first image sequence.

16. The system of claim 1 wherein automatically training the generative model on the first image sequence comprises performing an inferential probabilistic analysis of each image frame in the first image sequence for learning a probabilistic explanation of the first image sequence.

17. The system of claim 16 wherein performing an inferential probabilistic analysis of each image frame comprises performing an iterative variational expectation-maximization analysis of each image frame of the first image sequence.

18. The system of claim 17 wherein the iterative variational expectation-maximization analysis of each image frame of the first image sequence is sequentially iterated until convergence of variational parameters of the generative model is achieved.

19. The system of claim 17 wherein the iterative variational expectation-maximization analysis of each image frame of the first image sequence is sequentially iterated until a predetermined number of iterations have been completed.

20. The system of claim 17 wherein the iterative variational expectation-maximization analysis of each image frame of the first image sequence is sequentially iterated until a user adjustable number of iterations have been completed.

21. The system of claim 16 wherein an expectation step of the expectation-maximization analysis maximizes a lower bound on a log-likelihood of each image frame of the first image sequence by inferring approximations of variational parameters.

22. The system of claim 21 wherein a maximization step of the generalized expectation-maximization analysis automatically adjusts generative model parameters in order to maximize a lower bound on a log-likelihood of each image frame of the first image sequence.

23. The system of claim 22 wherein the expectation step and the maximization step are sequentially iterated until convergence of the variational parameters and generative model parameters is achieved.

24. The system of claim 1 wherein parameters of the generative model are updated incrementally without iterating as each frame of the first image sequence is processed.

25. The system of claim 16 wherein performing an inferential probabilistic analysis of each image frame comprises:

performing an iterative variational expectation-maximization analysis of each image frame of the first image sequence; and

updating the generative model after each variational expectation-maximization analysis of each image frame of the first image sequence.

26. A computer-implemented process for automatically identifying similar image frames in one or more image sequences, comprising:

acquire at least one image sequence, each image sequence having at least one image frame;

select a query sample consisting of at least one image frame from one of the at least one image sequences;

input a desired number of blobs to be modeled in generative model of the query sample;

automatically learn a generative model from the query sample, wherein the generative model includes a set of model parameters that represent the desired number of blobs; and

compare the frames in each image sequence to the generative model to determine a likelihood of each frame under the generative model.

27. The computer-implemented process of claim 26, wherein the generative model accounts for camera shake by modeling image pixel displacements in the generative model.

28. The computer-implemented process of claim 26 wherein the likelihood of each frame under the generative model is compared to an adjustable similarity threshold.

29. The computer-implemented process of claim 28 wherein image frames that have a likelihood greater than the similarity threshold are similar to the at least one image frame of the query sample, and wherein all other image frames are dissimilar to the at least one image frame of the query sample.

30. The computer-implemented process of claim 26 further comprising an automatic likelihood-based variable speed playback of at least one of the image sequences, and wherein a playback speed the at least one image sequence is inversely proportional to the likelihood of each image frame.

31. The computer-implemented process of claim 30 wherein the playback speed decreases as the likelihood increases, and wherein the payback speed increases as the likelihood decreases.

32. The computer-implemented process of claim 26 wherein the desired number of blobs is predetermined.

33. The computer-implemented process of claim 26 wherein the desired number of blobs is user adjustable.

34. The computer-implemented process of claim 26 wherein the model parameters include:

spatial covariance matrices of the blobs;

blob color distribution parameters;

blob sizes controlled by eigen values of the spatial covariance matrices; and

a scene background model.

35. The computer-implemented process of claim 26 wherein the generative model models multiple objects in the query sample as blobs, and wherein the generative model is capable of modeling occluding objects in the query sample.

36. The computer-implemented process of claim 26 wherein automatically learning the generative model from the query sample comprises performing an variational expectation-maximization (EM) analysis of each image frame in the query sample for learning a probabilistic explanation of the query sample.

37. The computer-implemented process of claim 36 wherein the variational EM analysis of each image frame of the query sample is sequentially iterated through the query sample until convergence of variational parameters of the generative model is achieved.

38. The computer-implemented process of claim 36 wherein the variational EM analysis of each image frame of the query sample is sequentially iterated through the query sample until a user adjustable number of iterations have been completed.

39. A computer-readable medium having computer executable instructions for automatically determining a playback speed for an image sequence, comprising:

selecting a query sample consisting at least one image frame;

automatically learning a generative model from the query sample;

providing at least one image sequence for playback;

comparing the frames in the at least one image sequence provided for playback to the generative model to determine a likelihood of each frame under the generative model; and

automatically varying a playback speed of the at least one image sequence in inverse proportion to the likelihood of each frame.

40. The computer-readable medium of claim 39 wherein the playback speed the at least one image sequence decreases as the likelihood increases, and wherein the payback speed increases as the likelihood decreases.

41. The computer-readable medium of claim 40 wherein the playback speed the at least one image sequence is determined by a combined likelihood of one or more adjacent image frames in the at least one image sequence.

42. The computer-readable medium of claim 39, wherein camera shake is modeled by the generative model by modeling image pixel shifts.

43. The computer-readable medium of claim 39 wherein the generative model is based on a user definable number of color blobs for modeling multiple objects represented in the query sample.

44. The computer-readable medium of claim 43 wherein the generative model is capable of modeling occluding objects.

45. The computer-readable medium of claim 39 further comprising comparing the likelihood of each frame under the generative model to a similarity threshold.

46. The computer-readable medium of claim 45 wherein image frames that have a likelihood greater than the similarity threshold are identified as being similar to the at least one image frame of the query sample, and wherein image frames that do not have a likelihood greater than the similarity threshold are identified as being dissimilar to the at least one image frame of the query sample.

47. The computer-readable medium of claim 45 wherein the similarity threshold is user adjustable.

48. The computer-readable medium of claim 39 wherein automatically learning the generative model from the query sample comprises performing an variational expectation-maximization (EM) analysis of each image frame in the query sample for learning a probabilistic explanation of the query sample.

49. The computer-readable medium of claim 48 wherein the variational EM analysis of each image frame of the query sample is sequentially iterated through the query sample until a user adjustable number of iterations have been completed.