System and method for automatically learning flexible sprites in video layers

• US 7,113,185 B2
• Filed: 11/14/2002
• Issued: 09/26/2006
• Est. Priority Date: 11/14/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Frey, Brendan J., Jojic, Nebojsa
• Primary Examiner(s): Nguyen, Kimbinh T.
• Application Number:
  US10/294,211
• Publication Number:
  US 20040095374A1
• Time in Patent Office: 1,412 Days
• Field of Search: 345/420, 345/683, 345/423, 715/716, 715/700, 715/723, 382/159, 382/173
• US Class Current: 345/420
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/30196 Human being; Person
• CPC Class Codes: G06T 7/215 Motion-based segmentation

Abstract

A simplified general model and an associated estimation algorithm is provided for modeling visual data such as a video sequence. Specifically, images or frames in a video sequence are represented as collections of flat moving objects that change their appearance and shape over time, and can occlude each other over time. A statistical generative model is defined for generating such visual data where parameters such as appearance bit maps and noise, shape bit-maps and variability in shape, etc., are known. Further, when unknown, these parameters are estimated from visual data without prior pre-processing by using a maximization algorithm. By parameter estimation and inference in the model, visual data is segmented into components which facilitates sophisticated applications in video or image editing, such as, for example, object removal or insertion, tracking and visual surveillance, video browsing, photo organization, video compositing, etc.

Claims

1. A system for automatically decomposing an image sequence, comprising:

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

providing a preferred number of objects to be identified within the image sequence;

providing a preferred number of layers into which each frame of the image sequence is to be decomposed; and

automatically decomposing the first image sequence into the preferred number of objects and the preferred number of layers.

2. The system of claim 1 wherein providing the preferred number of objects comprises specifying the preferred number of objects via a user interface.

3. The system of claim 1 wherein providing the preferred number of objects comprises automatically determining an optimal number of objects from the first sequence of at least one image frame.

4. The system of claim 1 wherein providing the preferred number of layers comprises specifying the preferred number of layers via a user interface.

5. The system of claim 1 wherein providing the preferred number of layers comprises automatically determining an optimal number of layers from the first sequence of at least one image frame.

6. The system of claim 3 further comprising automatically determining of a dimensionality of object classes.

7. The system of claim 1 wherein decomposing the first image sequence into the preferred number of objects and the preferred number of layers comprises automatically learning a 2-dimensional flexible representation of each object and an image mask for each 2-dimensional flexible representation of each object.

8. The system of claim 1 wherein the objects are represented by flexible sprites.

9. The system of claim 8 wherein automatically decomposing the first image sequence into the preferred number of flexible sprites comprises performing an inferential probabilistic analysis of each image frame for identifying the preferred number of flexible sprites within the first image sequence.

10. The system of claim 9 wherein performing an inferential probabilistic analysis of each image frame comprises performing a variational generalized expectation-maximization analysis of each image frame of the first image sequence.

11. The system of claim 10 wherein an expectation step of the generalized expectation-maximization analysis maximizes a lower bound on a log-likelihood of an image frame by inferring variational approximations of variational parameters.

12. The system of claim 11 wherein a maximization step of the generalized expectation-maximization analysis automatically adjusts object model parameters in order to maximize the lower bound on the log-likelihood of the image frame.

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

14. The system of claim 11 wherein automatic computation of the expectation step is accelerated by using an FFT-based inference analysis.

15. The system of claim 14 wherein the FFT-based inference analysis is performed on variables that are converted into a coordinate system wherein transforms applied to those variables are represented by shift operations.

16. The system of claim 1 wherein automatically decomposing the first image sequence into the preferred number of objects and the preferred number of layers comprises performing a probabilistic variational expectation-maximization analysis.

17. The system of claim 16 wherein the variational expectation-maximization analysis comprises:

forming at least one probabilistic submodel having variational parameters representing posterior distributions;

forming at least one probabilistic model representing each image frame from a combination of the submodels, with two or more submodels sharing common interface variables in the model; and

iteratively evaluating the probabilistic model by iteratively evaluating the submodels using a variational generalized expectation-maximization analysis to optimize a lower bound on a posterior distributions of the submodels.

18. The system of claim 1 further comprising a generative model which includes a set of model parameters that represent the entire first image sequence.

19. The system of claim 16 wherein the model parameters include:

a prior probability of at least one object class;

means and variances of object appearance maps; and

means and variances of object masks.

20. The system of claim 19 further comprising observation noise variances.

21. The system of claim 18 further comprising automatically reconstructing a layered representation of the first image sequence from the generative model, wherein the layered representation comprises the preferred number of layers.

22. The system of claim 1 further comprising automatically decomposing at least one additional image sequence into a preferred number of objects and a preferred number of layers.

23. The system of claim 22 further comprising selecting specific objects from any of the image sequences.

24. The system of claim 23 further comprising automatically composing a layered image sequence from the specific objects selected from any of the image sequences.

25. A computer-implemented process for automatically generating a layered representation of at least one image sequence, comprising using a computer to:

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

automatically decompose each image sequence into a generative model, with each generative model including a set of model parameters that represent at least one image sprite and at least one image layer learned for each image sequence.

26. The computer-implemented process of claim 25 wherein the number of image sprites learned for each image sequence is equivalent to a desired number of image sprites input via a user interface.

27. The computer-implemented process of claim 25 wherein the number of image layers learned for each image sequence is equivalent to a desired number of image sprites input via a user interface.

28. The computer-implemented process of claim 25 wherein the number of image sprites and image layers learned for each image sequence is automatically determined.

29. The computer-implemented process of claim 28 further comprising automatically learning a dimensionality of image sprite classes.

30. The computer-implemented process of claim 25, wherein each sprite represents a dynamic object appearance which was automatically learned from one of the image sequences.

31. The computer-implemented process of claim 30 wherein the model parameters of each generative model include an image sprite appearance map, an image sprite mask for each image sprite learned for each corresponding image sequence, and a prior probability of at least one image sprite class.

32. The computer-implemented process of claim 31 wherein the image sprite appearance map for each generative model includes means and variances of that image sprite appearance map, and wherein the image sprite mask for each generative model includes means and variances of that image sprite mask.

33. The computer-implemented process of claim 32 further comprising automatically regenerating a layered representation of each image sequence using the corresponding generative model.

34. The computer-implemented process of claim 33 further comprising automatically tracking at least one object through at least one image sequence by computing a position of a corresponding image sprite in at least one image sequence.

35. The computer-implemented process of claim 33 further comprising automatically removing electronics induced distortions in at least one frame of the automatically regenerated layered representation of at least one image sequence.

36. The computer-implemented process of claim 33 further comprising automatically removing noise in at least one frame of the automatically regenerated layered representation of at least one image sequence.

37. The computer-implemented process of claim 33 further comprising automatically removing background clutter in at least one frame of the automatically regenerated layered representation of at least one image sequence.

38. The computer-implemented process of claim 33 further comprising automatically centering at least one image sprite in at least one frame of the automatically regenerated layered representation of at least one image sequence.

39. The computer-implemented process of claim 33 further comprising automatically learning slant-invariant linear subspace models of handwritten characters and digits from at least one of the image sequences.

40. The computer-implemented process of claim 33 further comprising automatically removing at least one object from at least one frame of at least one image sequence by setting at least one image sprite to be transparent.

41. The computer-implemented process of claim 33 further comprising automatically inserting at least one image sprite from at least one image sequence into at least one frame of at least one automatically regenerated layered representation of at least one image sequence.

42. The computer-implemented process of claim 25 wherein automatically decomposing each image sequence into a generative model comprises performing a variational generalized expectation-maximization analysis of each image frame of each image sequence.

43. The computer-implemented process of claim 42 wherein an expectation step of the generalized expectation-maximization analysis maximizes a lower bound on a log-likelihood of each image frame by inferring approximations of variational parameters.

44. The computer-implemented process of claim 43 wherein a maximization step of the generalized expectation-maximization analysis automatically adjusts image sprite model parameters in order to maximize a lower bound on a log-likelihood of each image frame.

45. The computer-implemented process of claim 44 wherein the expectation step and the maximization step are sequentially iterated until convergence of the variational parameters and model parameters is achieved.

46. The computer-implemented process of claim 43 wherein automatic computation of the expectation step is accelerated by using an FFT-based inference analysis.

47. The computer-implemented process of claim 46 wherein the FFT-based inference analysis is performed on variables that are converted into a coordinate system wherein transforms applied to those variables are represented by shift operations.

48. A computer-readable medium having computer executable instructions for automatically learning layered flexible image sprites from an image sequence, comprising:

providing an input sequence of at least one image frame of a scene;

automatically learning a probabilistic number of image sprite classes to be identified within the image sequence;

automatically learning a probabilistic dimensionality of each image sprite class;

automatically learning a probabilistic number of layers for the image sprite classes; and

automatically learning at least one layered image sprite from the input sequence given the automatically learned number of image sprite classes, image sprite dimensionality, and image layers, wherein each image sprite represents an object in the input sequence.

49. The computer-readable medium of claim 48, further comprising computer executable instructions for reconstructing at least one sequential image frame from at least one of the automatically learned layered image sprites.

50. The computer-readable medium of claim 48 wherein the learned image sprites comprise 2-dimensional flexible representations of each object and an image mask for each 2-dimensional flexible representation of each object.

51. The computer-readable medium of claim 48 wherein automatically learning the at least one layered image sprites from the input sequence comprises performing an inferential probabilistic analysis of each image frame for identifying the image sprites within the input sequence.

52. The computer-readable medium of claim 51 wherein performing an inferential probabilistic analysis of each image frame comprises performing a variational generalized expectation-maximization analysis of each image frame.

53. The computer-readable medium of claim 52 wherein an expectation step of the generalized expectation-maximization analysis maximizes a lower bound on a log-likelihood of an image frame by inferring variational approximations of variational parameters.

54. The computer-readable medium of claim 53 wherein a maximization step of the generalized expectation-maximization analysis automatically adjusts object model parameters in order to maximize the lower bound on the log-likelihood of the image frame.

55. The computer-readable medium of claim 54 wherein the expectation step and the maximization step are sequentially iterated until convergence of the variational parameters and model parameters is achieved.

56. The computer-readable medium of claim 52 wherein the variational generalized expectation-maximization analysis comprises:

forming at least one probabilistic submodel having variational parameters representing posterior distributions;

forming at least one probabilistic model representing each image frame from a combination of the submodels, with two or more submodels sharing common interface variables in the model; and

iteratively evaluating the probabilistic model by iteratively evaluating the submodels using a variational generalized expectation-maximization analysis to optimize a lower bound on a posterior distributions of the submodels.

57. The computer-readable medium of claim 48 further comprising automatically constructing a generative model from the automatically learned layered image sprites, and wherein the generative model includes a set of model parameters that represent the entire image sequence.

58. The computer-readable medium of claim 57 wherein the model parameters include:

a prior probability of at least one object class;

means and variances of object appearance maps;

means and variances of object masks; and

observation noise variances.