Video segmentation using statistical pixel modeling

• US 6,625,310 B2
• Filed: 03/23/2001
• Issued: 09/23/2003
• Est. Priority Date: 03/23/2001
• Status: Expired due to Term

• Current Assignee: Avigilon Fortress Corporation
• Original Assignee: Diamondback Vision, Inc.
• Inventors: Haering, Niels, Lipton, Alan J., Strat, Thomas M., Allmen, Mark, Severson, William
• Primary Examiner(s): Johns, Andrew W.
• Assistant Examiner(s): Alavi, Amir
• Application Number:
  US09/815,385
• Publication Number:
  US 20020159634A1
• Time in Patent Office: 914 Days
• Field of Search: 382/173, 382/180, 382/190, 382/199, 382/203, 382/205, 382/209, 382/210, 382/218, 382/219, 382/224, 382/236, 382/308, 375/240.29, 375/240.01, 375/240, 375/240.24, 375/240.02, 348/384.1, 348/700, 348/701, 348/702
• US Class Current: 382/173
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/30241 Trajectory
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/143 involving probabilistic approaches, e.g. Markov random field [MRF] modelling
• CPC Class Codes: G06T 7/194 involving foreground-background segmentation
• CPC Class Codes: G06T 7/277 involving stochastic approaches, e.g. using Kalman filters
• CPC Class Codes: G06V 10/26 Segmentation of patterns in the image field; Cutting or merging of image elements to establish the pattern region, e.g. clustering-based techniques; Detection of occlusion
• CPC Class Codes: G06V 10/28 Quantising the image, e.g. histogram thresholding for discrimination between background and foreground patterns
• CPC Class Codes: G06V 20/52 Surveillance or monitoring of activities, e.g. for recognising suspicious objects recognising microscopic objects G06V20/69
• CPC Class Codes: G06V 2201/01 Solutions for problems related to non-uniform document background
• CPC Class Codes: G08B 13/196 using television cameras
• CPC Class Codes: G08B 31/00 Predictive alarm systems characterised by extrapolation or other computation using updated historic data

Abstract

A method for segmenting video data into foreground and background portions utilizes statistical modeling of the pixels. A statistical model of the background is built for each pixel, and each pixel in an incoming video frame is compared with the background statistical model for that pixel. Pixels are determined to be foreground or background based on the comparisons.

Claims

1. A two-pass method of video segmentation, for differentiating between foreground and background portions of video, comprising the steps of:

obtaining a frame sequence from an input video stream;

executing a first-pass method for each frame of the frame sequence, the first-pass method comprising the steps of;

aligning the frame with a scene model; and

updating a background statistical model; and

finalizing the background statistical model;

executing a second-pass method for each frame of the frame sequence, the second-pass method comprising the steps of;

labeling each region of the frame; and

performing spatial/temporal filtering of the regions of the frame.

2. A computer system comprising:

a computer; and

a computer-readable medium containing software implementing the method of claim 1.

3. A computer-readable medium comprising software implementing the method of claim 1.

4. The method according to claim 1, wherein the step of updating a background statistical model comprises the steps of:

compiling values corresponding to the regions of the frames; and

computing a standard deviation for each region of the frames.

5. The method according to claim 1, wherein the step of finalizing the background statistical model comprises the step of:

for each region of the frames, determining a statistical mode based on the compiled values; and

assigning the statistical mode of each region as its value in the background statistical model.

6. The method according to claim 1, wherein the step of labeling each region of the frame comprises the steps of:

determining whether or not the region matches the background statistical model; and

assigning a label based on the result of the determining step.

7. The method according to claim 6, wherein the step of determining comprises the step of determining whether a value of the region of the frame falls within some range about a corresponding value of the region in the background statistical model;

and

wherein the step of assigning a label comprises the steps of;

assigning a first label if the value of the region of the frame does fall within the range; and

assigning a second label if the value of the region of the frame does not fall within the range.

8. The method according to claim 7, wherein said first label is background and said second label is foreground.

9. The method according to claim 6, wherein the step of determining comprises the steps of:

determining whether a value of the region of the frame falls within a first range about a corresponding value of the region in the background statistical model; and

if the value of the region of the frame does not fall within the first range, determining if it falls within a second range about said corresponding value of the region in the background statistical model; and

wherein the step of assigning a label comprises the steps of;

assigning a first label if the value of the region of the frame falls within the first range;

assigning a second label if the value of the region of the frame does not fall within the first range and does lie within the second range; and

assigning a third label if the value of the region of the frame does not fall within the second range.

10. The method according to claim 9, wherein said first label is background, said second label is foreground, and said third label is definite foreground.

11. The method according to claim 1, wherein the step of labeling each region of the frame comprises the steps of:

determining whether or not the region matches the background statistical model, comprising the step of performing determinations as to whether or not a value of the region of the frame falls within each of an arbitrary number of ranges about a corresponding value of the region in the background statistical model ; and

assigning a label based on the result of the determining step.

12. The method according to claim 1, wherein the step of spatial/temporal filtering comprises the steps of, for each region of the frame:

performing neighborhood filtering; and

performing spatial filtering, temporal filtering, or a combination thereof.

13. The method according to claim 12, wherein the step of performing spatial filtering, temporal filtering, or a combination thereof comprises the step of performing morphological erosions and dilations, wherein the morphological erosions and dilations are performed in two dimensions or in three dimensions.

14. The method according to claim 13, wherein said step of performing morphological erosions and dilations comprises the steps of:

performing a number, n, of erosions, wherein any region labeled definite foreground is not eroded;

following the step of performing n erosions, performing n dilations; and

following the step of performing n dilations, performing a second number, m, of dilations.

15. The method according to claim 12, wherein the step of performing neighborhood filtering comprises the steps of, for each region of the frame, P_i, not labeled background:

determining a location, P_m, in the scene model corresponding to P_i;

determining a neighborhood of regions, P′

_m around P_m;

determining if any of the P′

_m matches P_i;

if any of the P′

_m matches P_i, determining a neighborhood of regions P′

_i around P_i;

determining if any of the P′

_i matches P_m; and

if any of the P′

_m matches P_i, relabeling P_i background.

16. A one-pass method of video segmentation, for differentiating between foreground and background portions of video, comprising the steps of:

obtaining a frame sequence from a video stream; and

for each frame in the frame sequence, performing the following steps;

aligning the frame with a scene model;

building a background statistical model;

labeling the regions of the frame; and

performing spatial/temporal filtering.

17. A computer system comprising:

a computer; and

a computer-readable medium containing software implementing the method of claim 16.

18. A computer-readable medium comprising software implementing the method of claim 16.

19. The method according to claim 16, wherein the step of spatial/temporal filtering comprises the steps of, for each region of the frame:

performing neighborhood filtering; and

performing spatial filtering, temporal filtering, or a combination thereof.

20. The method according to claim 19, wherein the step of performing spatial filtering, temporal filtering, or a combination thereof comprises the step of performing morphological erosions and dilations, wherein the morphological erosions and dilations are performed in two dimensions or in three dimensions.

21. The method according to claim 20, wherein said step of performing morphological erosions and dilations comprises the steps of:

performing a number, n, of erosions, wherein any region labeled definite foreground is not eroded;

following the step of performing n erosions, performing n dilations; and

following the step of performing n dilations, performing a second number, m, of dilations.

22. The method according to claim 19, wherein the step of performing neighborhood filtering comprises the steps of, for each region of the frame, P_i, not labeled background:

determining a location, P_m, in the scene model corresponding to P_i;

determining a neighborhood of regions, P′

_m around P_m;

determining if any of the P′

_m matches P_i;

if any of the P′

_m matches P_i, determining a neighborhood of regions P′

_i around P_i;

determining if any of the P′

_i matches P_m; and

if any of the P′

_m matches P_i, relabeling P_i background.

23. The method according to claim 16, wherein said step of building a background statistical model comprises the steps of:

for each region of the frame, performing the steps of;

determining if the background statistical model is mature and stable;

if the background statistical model is mature and stable, determining if a value of the region matches a corresponding value of the background statistical model; and

if the value of the region matches the value of the background statistical model, updating the background statistical model using the value of the region.

24. The method according to claim 23, wherein the step of determining if the background statistical model is mature and stable comprises the steps of:

determining if the background statistical model is mature, and if it is not, updating the background statistical model using the value of the region;

if the background statistical model is determined to be mature, determining if the background statistical model is stable;

if the background statistical model is determined not to be stable, updating the background statistical model using the value of the region.

25. The method according to claim 24, wherein each step of updating the background statistical model using the value of the region comprises the steps of:

updating a running mean value for the region; and

updating a running standard deviation value for the region.

26. The method according to claim 23, wherein the step of updating the background statistical model using the value of the region comprises the steps of:

updating a running mean value for the region; and

updating a running standard deviation value for the region.

27. The method according to claim 23, wherein said step of building a background statistical model further comprises the step of finalizing the background statistical model.

28. The method according to claim 16, wherein said step of labeling the regions of the frame comprises, for each region of the frame, the steps of:

making determinations as to the maturity and stability of the background statistical model for that region;

determining if a value of the background statistical model for that region matches a value of the scene model for that region;

determining if a value of the region matches the value of the scene model for that region; and

determining to what extent the value of the region matches the value of the background statistical model for that region;

and wherein, based on the results of the making and determining steps, a label is assigned to the region.

29. The method according to claim 28, wherein the step of making determinations as to the maturity and stability of the background statistical model comprises the steps of:

determining whether or not the background statistical model is mature;

determining whether or not the background statistical model is stable; and

if the background statistical model is not stable, determining if it was ever previously stable.

30. The method according to claim 29, wherein the step of determining if the background statistical model is stable is executed only if the background statistical model is determined to be mature;

and wherein, if the background statistical model is determined not to be mature, the step of determining if a value of the region matches the value of the scene model for that region is executed.

31. The method according to claim 29, wherein, if the background statistical model is determined to be stable, the step of determining if a value of the background statistical model for that region matches a value of the scene model for that region is executed.

32. The method according to claim 29, wherein, if the step of determining if the background statistical model was ever previously stable returns an affirmative result, the step of determining if a value of the region matches the value of the scene model for that region is executed;

and wherein, if the step of determining if the background statistical model was ever previously stable returns a negative result, then the region is labeled definite foreground.

33. The method according to claim 28, wherein if the step of determining if a value of the region matches the value of the scene model for that region returns an affirmative result, the region is labeled background, and if it returns a negative result, the region is labeled foreground.

34. The method according to claim 28, wherein, if the step of determining if a value of the background statistical model for that region matches a value of the scene model for that region returns an affirmative result, the step of determining to what extent the value of the region matches the value of the background statistical model for that region is executed;

and wherein, if the step of determining if a value of the background statistical model for that region matches a value of the scene model for that region returns a negative result, then the step of determining if a value of the region matches the value of the scene model for that region is executed.

35. The method according to claim 28, wherein the step of determining to what extent the value of the region matches the value of the background statistical model for that region comprises the steps of:

determining if the value of the region matches the value of the background statistical model for that region;

if the step of determining if the value of the region matches the value of the background statistical model for that region, labeling the region background; and

if the step of determining if the value of the region matches the value of the background statistical model for that region returns a negative result, determining if the value of the region falls far from the background statistical model.

36. The method according to claim 35, wherein the step of determining if the value of the region falls far from the background statistical model comprises the step of performing a threshold comparison;

and wherein;

if the step of determining if the value of the region falls far from the background statistical model returns an affirmative result, labeling the region definite foreground, and

if the step of determining if the value of the region falls far from the background statistical model returns a negative result, labeling the region foreground.

37. A one-pass method of video segmentation, for differentiating between foreground and background portions of video, comprising the steps of:

obtaining a frame sequence from a video stream; and

for each frame in the frame sequence, performing the following steps;

aligning the frame with a scene model;

building a background statistical model and a secondary statistical model;

labeling the regions of the frame; and

performing spatial/temporal filtering.

38. A computer system comprising:

a computer; and

a computer-readable medium containing software implementing the method of claim 37.

39. A computer-readable medium comprising software implementing the method of claim 37.

40. The method according to claim 37, wherein the step of spatial/temporal filtering comprises the steps of, for each region of the frame:

performing neighborhood filtering; and

performing spatial filtering, temporal filtering, or a combination thereof.

41. The method according to claim 40, wherein the step of performing spatial filtering, temporal filtering, or a combination thereof comprises the step of performing morphological erosions and dilations, wherein the morphological erosions and dilations are performed in two dimensions or in three dimensions.

42. The method according to claim 41, wherein said step of performing morphological erosions and dilations comprises the steps of:

performing a number, n, of erosions, wherein any region labeled definite foreground is not eroded;

following the step of performing n erosions, performing n dilations; and

following the step of performing n dilations, performing a second number, m, of dilations.

43. The method according to claim 40, wherein the step of performing neighborhood filtering comprises the steps of, for each region of the frame, P_i, not labeled background:

determining a location, P_m, in the scene model corresponding to P_i;

determining a neighborhood of regions, P′

_m around P_m;

determining if any of the P′

_m matches P_i;

if any of the P′

_m matches P_i, determining a neighborhood of regions P′

_i around P_i;

determining if any of the P′

_i matches P_m; and

if any of the P′

_m matches P_i, relabeling P_i background.

44. The method according to claim 37, wherein said step of building a background statistical model comprises the steps of:

for each region of the frame, performing the steps of;

determining if the background statistical model is mature and stable;

if the background statistical model is mature and stable, determining if a value of the region matches a corresponding value of the background statistical model;

if the value of the region matches the value of the background statistical model, updating the background statistical model using the value of the region; and

if the value of the region does not match the value of the background statistical model, updating the secondary statistical model using the value of the region.

45. The method according to claim 44, wherein the step of determining if the background statistical model is mature and stable comprises the steps of:

determining if the background statistical model is mature, and if it is not, updating the background statistical model using the value of the region;

if the background statistical model is determined to be mature, determining if the background statistical model is stable;

if the background statistical model is determined not to be stable, updating the background statistical model using the value of the region.

46. The method according to claim 45, wherein each step of updating the background statistical model using the value of the region comprises the steps of:

updating a running mean value for the region; and

updating a running standard deviation value for the region.

47. The method according to claim 44, wherein the step of updating the background statistical model using the value of the region comprises the steps of:

updating a running mean value for the region; and

updating a running standard deviation value for the region.

48. The method according to claim 44, wherein said step of updating the secondary statistical model comprises the steps of:

determining if the secondary statistical model is mature;

if the secondary statistical model is not mature, updating the secondary statistical model using the value of the region;

if the secondary statistical model is mature, determining if the secondary statistical model is stable;

if the secondary statistical model is not stable, updating the secondary statistical model using the value of the region; and

if the secondary statistical model is stable, replacing the background statistical model for the region with the secondary statistical model for the region.

49. The method according to claim 44, wherein said step of building a background statistical model further comprises the step of finalizing the background statistical model.

50. The method according to claim 37, wherein said step of labeling the regions of the frame comprises, for each region of the frame, the steps of:

making determinations as to the maturity and stability of the background statistical model for that region;

determining if the value of a background statistical model for that region matches a value of the scene model for that region;

determining if a value of the region matches the value of the scene model for that region; and

determining to what extent the value of the region matches the value of the background statistical model for that region;

and wherein, based on the results of the making and determining steps, a label is assigned to the region.

51. The method according to claim 50, wherein the step of making determinations as to the maturity and stability of the background statistical model comprises the steps of:

determining whether or not the background statistical model is mature;

determining whether or not the background statistical model is stable; and

if the background statistical model is not stable, determining if it was ever previously stable.

52. The method according to claim 51, wherein the step of determining if the background statistical model is stable is executed only if the background statistical model is determined to be mature;

and wherein, if the background statistical model is determined not to be mature, the step of determining if a value of the region matches the value of the scene model for that region is executed.

53. The method according to claim 51, wherein, if the background statistical model is determined to be stable, the step of determining if a value of the background statistical model for that region matches a value of the scene model for that region is executed.

54. The method according to claim 51, wherein, if the step of determining if the background statistical model was ever previously stable returns an affirmative result, the step of determining if a value of the region matches the value of the scene model for that region is executed;

and wherein, if the step of determining if the background statistical model was ever previously stable returns a negative result, then the region is labeled definite foreground.

55. The method according to claim 50, wherein if the step of determining if a value of the region matches the value of the scene model for that region returns an affirmative result, the region is labeled background, and if it returns a negative result, the region is labeled foreground.

56. The method according to claim 50, wherein, if the step of determining if a value of the background statistical model for that region matches a value of the scene model for that region returns an affirmative result, the step of determining to what extent the value of the region matches the value of the background statistical model for that region is executed;

and wherein, if the step of determining if a value of the background statistical model for that region matches a value of the scene model for that region returns a negative result, then the step of determining if a value of the region matches the value of the scene model for that region is executed.

57. The method according to claim 50, wherein the step of determining to what extent the value of the region matches the value of the background statistical model for that region comprises the steps of:

determining if the value of the region matches the value of the background statistical model for that region;

if the step of determining if the value of the region matches the value of the background statistical model for that region, labeling the region background; and

if the step of determining if the value of the region matches the value of the background statistical model for that region returns a negative result, determining if the value of the region falls far from the background statistical model.

58. The method according to claim 57, wherein the step of determining if the value of the region falls far from the background statistical model comprises the step of performing a threshold comparison;

and wherein;

if the step of determining if the value of the region falls far from the background statistical model returns an affirmative result, labeling the region definite foreground, and

if the step of determining if the value of the region falls far from the background statistical model returns a negative result, labeling the region foreground.

59. A two-pass method of video segmentation, for differentiating between foreground and background portions of video, comprising the steps of:

obtaining a frame sequence from an input video stream;

executing a first-pass method for each frame of the frame sequence, the first-pass method comprising the steps of;

aligning the frame with a scene model; and

updating a background statistical model, the background statistical model comprising values corresponding to regions of frames of the frame sequence and variances for the regions;

finalizing the background statistical model; and

executing a second-pass method for each frame of the frame sequence, the second-pass method comprising the steps of;

labeling each region of the frame; and

performing spatial/temporal filtering of the regions of the frame.

60. A one-pass method of video segmentation, for differentiating between foreground and background portions of video, comprising the steps of:

obtaining a frame sequence from a video stream; and

for each frame in the frame sequence, performing the following steps;

aligning the frame with a scene model;

building a background statistical model, the background statistical model comprising values corresponding to regions of frames of the frame sequence and variances for the regions;

labeling the regions of the frame; and

performing spatial/temporal filtering.