Granted Patent B2

US 6,987,883 · App. 10/331,778 · Granted Jan 17, 2006

Abstract

Claims (115)

1. A method of video scene background maintenance for a sequence of video frames, comprising the steps of:

aligning the video frames;

building a statistical model for each pixel of the aligned video frames, comprising the steps of:

building a time series of chromatic data for each pixel;

determining zero or more candidate states for each pixel based on the time series for the pixel; and

computing statistical quantities for the states based on the time series; and

choosing a background state for each pixel of the aligned video frames.

2. The method according to claim 1 , wherein the step of determining zero or more candidate states comprises the steps of:

determining if there exists a seed point for a state in any portion of the time series for which a state has not yet been determined; and

if such a seed point does exist, growing a state description from the seed point.

3. The method according to claim 2 , wherein the step of determining if there exists a seed point comprises the steps of:

running a sliding window of a predetermined duration across the time series, thus producing a series of windowed regions;

computing a variance over the values in each windowed region, thus producing a time series of variances; and

determining a minimum point of the time series of variances; and

if the minimum point falls below a predetermined threshold, selecting a corresponding point in the original time series as a seed point.

4. The method according to claim 3 , further comprising the step of:

if the minimum point of the time series of variances exceeds the predetermined threshold, determining that there is no further seed point in the time series.

5. The method according to claim 2 , wherein the step of growing a state description from the seed point comprises the steps of:

determining a left delimiting value of the state; and

determining a right delimiting value of the state;

wherein each of the steps of determining a left or right delimiting value comprises the steps of:

selecting the next point in the time series in a respective left or right direction;

determining if the chromatic value of the next point differs from the seed point by more than a predetermined threshold amount;

if the chromatic value of the next point differs from the seed point by no more than the predetermined threshold amount, setting the value of the respective left or right delimiting value equal to the next point, and returning to the step of selecting a next point; and

if the chromatic value of the next point differs from the seed point by more than the predetermined threshold amount, ending the respective step of determining a left or right delimiting value.

6. The method according to claim 5 , further comprising the step of:

removing from further consideration for determining additional states all points of the time series between the left and right delimiting values.

7. The method according to claim 1 , wherein the statistical quantities for each state include a mean and a variance, and wherein the method further comprises the step of:

merging similar states.

8. The method according to claim 7 , wherein the step of merging similar states comprises, for each pair of states, the steps of:

comparing the means and the variances of the two states;

if the means and variances agree to within a predetermined tolerance, combining the states into a single state having a combined mean and variance and a list of temporal delimiters.

9. The method according to claim 7 , further comprising the steps of:

determining if there is at least one state; and

if not, taking the entire time series as a single state, having the mean and variance of the entire time series.

10. The method according to claim 1 , further comprising the step of:

building a background image based on the background statistical model.

11. The method according to claim 10 , wherein the step of building a background image comprises the step of:

taking a mean value of the background state for each pixel in the background statistical model and using the mean value as the chromatic value for that pixel of the background image.

12. The method according to claim 1 , further comprising the step of:

segmenting video frames into foreground and background regions based on the statistical background model.

13. The method according to claim 12 , wherein the step of segmenting comprises the steps of:

for each frame, finding a pixel p′ in the scene model that corresponds to each pixel p of the frame;

determining if pixel p is included in the background state of p′; and

if the result of the determining step is positive, deciding that p is a background pixel and, otherwise, deciding that p is a foreground pixel.

14. The method according to claim 13 , wherein the step of choosing a background state for each pixel includes the step of:

providing a temporal description of the background state of each pixel.

15. A computer-readable medium containing instructions that, when executed by a processor, cause the processor to perform the method according to claim 1 .

16. A computer system comprising:

a processor; and

the computer-readable medium according to claim 15 .

17. A method of video scene background maintenance for a sequence of video frames, comprising the steps of:

aligning the video frames;

building a statistical model for each pixel of the aligned video frames; and

choosing a background state for each pixel of the aligned video frames, comprising the

choosing a background state for each pixel of the aligned video frames, comprising the steps of:

choosing an initial guess for a background state of each pixel, comprising the steps of:

determining if the pixel has only a single state;

if so, setting the background state to that single state and labeling the pixel uncontroversial; and

if not, choosing one of multiple states of the pixel as the background state for the pixel and labeling the pixel controversial, comprising the steps of:

determining if a state transition between a pair of contiguous states for the pixel is slow or sudden;

if there is a sudden transition between the pair of contiguous states, performing the steps of:

computing variances of chromatic values in small windows to each side of the transition; and

determining the state on the side of the window having the higher variance to be not background and removing it from consideration as a background state; and

if there is a slow transition between the pair of contiguous states, performing the steps of:

computing the mean of the data between the two states; and

determining the state that is closest to the mean of the data between the two states to be not background and removing it from consideration as a background state; and

iteratively propagating the initial guesses spatially to neighboring pixels.

18. The method according to claim 17 , wherein the step of choosing one of multiple states of the pixel as the background state for the pixel and labeling the pixel controversial further comprises the steps of:

for pairs of remaining states, computing a variance of chromatic values in a small window at the end of each of the pair of states that is temporally closer to the other of the pair of states;

determining the state with the higher variance near the end to be not background and removing it from consideration as a background state; and

repeating the previous two steps until there is only one state remaining, which state is taken as the initial guess background state for the pixel and is labeled controversial.

19. The method according to claim 17 , wherein the step of iteratively propagating the initial guesses spatially to neighboring pixels comprises the steps of:

selecting a neighborhood of pixels around a controversial pixel;

for each pixel in the neighborhood of pixels, selecting a number of votes for a background state of the controversial pixel based on a background state of the pixel in the neighborhood;

selecting a background state of the controversial pixel based on the votes.

20. The method according to claim 19 , wherein the step of iteratively propagating the initial guesses spatially to neighboring pixels further comprises the step of:

for each pixel in the neighborhood of pixels, weighting the number of votes selected for a background state of the controversial pixel based on whether the pixel in the neighborhood is controversial or not.

21. The method according to claim 19 , wherein the step of selecting a background state of the controversial pixel comprises the step of choosing the background state of the controversial pixel to be a state having the greatest number of votes among all pixels in the neighborhood of pixels.

22. The method according to claim 21 , further comprising the steps of:

testing to determine if the number of votes for the chosen background state exceeds a predetermined number; and

if the number of votes exceeds the predetermined number, relabeling the controversial pixel as uncontroversial.

23. The method according to claim 22 , further comprising the step of performing further iterations, beginning with the step of selecting a neighborhood of pixels around a controversial pixel, until there are no pixels labeled controversial.

24. The method according to claim 22 , further comprising the step of performing further iterations, beginning with the step of selecting a neighborhood of pixels around a controversial pixel, until the lesser of the number of iterations needed so that no pixels are labeled controversial and a predetermined number of iterations is reached.

25. The method according to claim 19 , wherein said neighborhood of pixels is a spatial neighborhood of pixels.

26. A method of video scene background maintenance for a sequence of video frames, comprising the steps of:

aligning the video frames;

building a statistical model for each pixel of the aligned video frames; and

choosing a background state for each pixel of the aligned video frames, comprising the steps of:

choosing an initial guess for a background state of each pixel, comprising the steps of:

determining if the pixel has only a single state;

if so, setting the background state to that single state and labeling the pixel uncontroversial; and

if not, choosing one of multiple states of the pixel as the background state for the pixel and labeling the pixel controversial; and

iteratively propagating the initial guesses spatially to neighboring pixels, comprising the steps of:

iteratively propagating the initial guesses spatially, resulting in iteratively spatially propagated guesses; and

iteratively propagating the iteratively spatially propagated guesses temporally, comprising the steps of:

selecting a first spatial neighborhood of pixels around a given pixel;

comparing the iteratively spatially propagated guess corresponding to the given pixel to each of the iteratively spatially propagated guesses corresponding to the pixels in the first spatial neighborhood; and

if the iteratively spatially propagated guess corresponding to the given pixel does not temporally overlap any of the iteratively spatially propagated guesses corresponding to the pixels in the first spatial neighborhood, labeling the given pixel temporally controversial, and otherwise labeling the given pixel temporally uncontroversial.

27. The method according to claim 26 , further comprising, for each temporally controversial pixel, the steps of:

selecting a second spatial neighborhood of pixels surrounding the temporally controversial pixel;

for each pixel in the second spatial neighborhood of pixels, selecting a number of votes for a background state of the temporally controversial pixel, based on whether or not the background state of the pixel in the second spatial neighborhood of pixels maximally overlaps with the background state of the temporally controversial pixel; and

selecting a background state of the temporally controversial pixel based on the votes.

28. The method according to claim 27 , wherein the step of selecting a number of votes further comprises the steps of:

selecting a first number of votes if the pixel in the second spatial neighborhood is temporally controversial; and

selecting a second number of votes if the pixel in the second spatial neighborhood is temporally uncontroversial.

29. The method according to claim 28 , wherein the step of selecting a number of votes comprises the steps of:

selecting the number of votes to be one of the first number of votes and the second number of votes if the background state of the pixel in the second spatial neighborhood of pixels maximally overlaps with the background state of the temporally controversial pixel; and

selecting the number of votes to be zero if the background state of the pixel in the second spatial neighborhood of pixels does not maximally overlap with the background state of the temporally controversial pixel.

30. The method according to claim 27 , wherein the step of selecting a background state of the temporally controversial pixel comprises the step of choosing the background state of the temporally controversial pixel to be a state having the greatest number of votes among all pixels in the second neighborhood of pixels.

31. The method according to claim 30 , further comprising the steps of:

testing to determine if the number of votes for the chosen background state exceeds a predetermined number; and

if the number of votes exceeds the predetermined number, relabeling the temporally controversial pixel as temporally uncontroversial.

32. The method according to claim 31 , further comprising the step of performing further interations, beginning with the step of selecting a second spatial neighborhood of pixels around a temporally controversial pixel, until there are no pixels labeled temporally controversial.

33. The method according to claim 31 , further comprising the step of performing further iterations, beginning with the step of selecting a second spatial neighborhood of pixels around a temporally controversial pixel, until the lesser of the number of iterations needed so that no pixels are labeled temporally controversial and a predetermined number of iterations is reached.

Assignments (9)