Method and apparatus for foreground segmentation of video sequences

• US 7,418,134 B2
• Filed: 05/12/2004
• Issued: 08/26/2008
• Est. Priority Date: 05/12/2003
• Status: Expired due to Fees

• Current Assignee: Princeton University
• Original Assignee: Princeton University
• Inventors: Schwartz, Stuart, Liu, Bede, Zhu, Juhua
• Primary Examiner(s): LAROSE, COLIN M
• Application Number:
  US10/843,953
• Publication Number:
  US 20040228530A1
• Time in Patent Office: 1,567 Days
• Field of Search: 382/103, 382/173, 382/236, 382/239, 382/243, 382/248, 382/250, 375/240.08, 375/240.18, 375/240.2
• US Class Current: 382/173
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 2207/20052 Discrete cosine transform [DCT]
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/174 involving the use of two or more images
• CPC Class Codes: G06T 7/194 involving foreground-background segmentation
• CPC Class Codes: G06T 7/262 using transform domain methods, e.g. Fourier domain methods
• CPC Class Codes: G06V 10/28 Quantising the image, e.g. histogram thresholding for discrimination between background and foreground patterns

Abstract

The present invention relates to a method and system for foreground segmentation in which frames of a video sequence are analyzed in the transform domain to determine one or more features. The features are used to model the background. The background can be modeled as a single Gaussian model with a mean and variance of the features. A current frame is segmented by determining if one or more features of the current frame analyzed in the foreground domain satisfy a threshold between the background model. The threshold value can be based on the mean and/or variance of features. During the segmentation, the mean and variance can be updated based on previous corresponding values and current features to adaptively update the background model. In one embodiment, the frames are divided into a plurality of blocks. A transform is used to analyze the blocks in the transform domain. For example, the transform can be a discrete cosine transform (DCT). The features can be a DC feature comprising the DC coefficient and an AC feature comprising a weighted sum of the AC coefficients. The weighted sum is determined with weights which are varied to emphasize different aspects of the present invention. Additional processing steps can be used to remove false positives, handle sudden global illumination changes, handle sudden local illumination changes and remove false negatives.

Claims

1. A method for a foreground segmentation of a video sequence of at least one frame comprising the steps of:

a. determining a background model from background model training;

b. analyzing said at least one frame in said video sequence in a discrete cosine transform (DCT), said at least one frame is divided into a plurality of blocks;

c. extracting one or more features of the analyzed at least one frame; and

d. segmenting said at least one frame in said video sequence by determining if said one or more features satisfy a threshold value between said background model to provide a segmentation result of one or more foreground objects wherein a first said feature is a DC feature comprising a DC coefficient of said DCT and a second said feature is an AC feature comprising a weighted sum of DCT coefficients of said plurality of blocks.

2. The method of claim 1 wherein said weighted sum is determined with weights which are varied to emphasize different aspects of said video sequence.

3. The method of claim 1 wherein said AC feature is represented by f_AC determined by:

$f_{A<br><br><br><br>C}=\underset{i=0}{\overset{3}{\sum <br><br>}}<br><br>\underset{j=0}{\overset{3}{\sum <br><br>}}<br><br>\left(i^2+j^2\right)·<br><br><br><br>\mathrm{DCT}<br><br>\left(i,j\right)<br><br>.$

4. The method of claim 3 wherein in step d., said block is segmented as a foreground block if said block meets a first said threshold value based on a difference of said AC feature and a mean of said AC feature in the background model and/or a second said threshold value based on a difference of said DC feature and mean of said DC feature in said background model.

5. The method of claim 3 further comprising the step of:

updating said background model based on either said DC feature and/or said AC feature.

6. The method of claim 5 wherein the blocks of said background model are updated as follows:

μ

_t=(1−

α

_μ

)μ

<sub>t−

1</sub>+α

_μ

·

x

σ

_t²=(1−

α

_σ

)σ

<sub>t−

1</sub>²+α

_σ

·

(x−

μ

_t)²,

where t and t−

1 are the frame numbers, x represents either the AC feature or the DC feature, and α

is a learning parameter controlling the learning speed.

7. The method of claim 5 further comprising the steps of:

determining if a global change has occurred in a current said frame;

if a global change occurred, increasing the learning parameter which is used with said DC feature or said AC feature for updating said background model after step d.

8. The method of claim 7 wherein the learning parameter is increased by the steps of:

determining if the foreground objects were detected in a previous frame;

if no foreground objects were detected in step d., declaring the at least one frame as background in the background model and increasing said learning parameter;

or

if foreground objects were detected in the previous frame,

dilating the segmentation result and using the dilated segmentation result as a current segmentation result;

modeling illumination changes for the blocks of background blocks in the background model;

modeling a complete background model using interpolation and/or extrapolation;

re-segmenting a current frame in said video sequence by determining if one or more features of said current frame analyzed in the transform domain satisfy a threshold value between said background model; and

increasing the learning parameter.

9. The method of claim 5 wherein after step d., further comprising the steps of removing a false alarm by the step of size filtering.

10. The method of claim 9 wherein the step of size filtering is performed by the steps of:

e. determining if a blob size of a blob of the one or more foreground objects is less than a predetermined first threshold value;

f. if the blob size is less than the predetermined first threshold value, removing the blob;

g. if the blob size is greater than the first threshold value, determining if a ratio of a number of AC blocks representing the AC feature to a number of DC blocks representing the DC feature is less than a predetermined second threshold value;

h. if the ratio of the number of AC blocks to the number of DC blocks is less than the second threshold value, removing the blob;

or

i. if the ratio of the number of AC blocks to the number of DC blocks is not less than the second threshold value, determining if the ratio of the number of AC blocks to the number of DC blocks is greater than a predetermined third threshold value;

if a ratio of the number of AC blocks to the number of DC blocks is greater than the third threshold value, removing the blob, or if the ratio of the number of AC blocks to the number of DC blocks is not greater than the third threshold value, repeating steps e. through i. for all blobs.

11. The method of claim 5 wherein after step d., further comprising the step of:

detecting sudden local illumination changes or moved background objects; and

updating said background model to remove false ones of said one or more foreground objects.

12. The method of claim 11 wherein said step of detecting sudden local illumination changes or moved background objects comprises the steps of:

e. determining if a blob of the foreground object matches roughly to a previous blob of the foreground object;

if the blob does not match roughly with the previous blob of the foreground object, adding the blob to a record and setting a corresponding counter to one or if the blob matches roughly to a previous blob of the foreground object increasing a corresponding counter by one;

f. determining if the counter is greater than a predefined threshold k;

g. if it is determined that the counter goes to the predefined threshold k, removing the blob and increasing a value of a learning parameter which is used for updating said background model after step d.; and

repeating steps e. through g. for all blobs.

13. The method of claim 5 wherein after step d., further comprising the step of filling said background model by the step of:

labeling blocks near said one or more foreground objects with similar features as said respective one or more said foreground objects.

14. The method of claim 13 wherein said filling step comprises the steps of:

e. labeling connected components of said background model;

f. determining if a blob size of the background model is less than a threshold value;

g. if it is determined that the blob size is less than the threshold value, labeling the blob as the foreground object;

repeating steps e. through g. for all blobs of the background model.

15. The method of claim 13 wherein said filling step comprises the steps of:

dilating blobs of the current frame to include one or more surrounding blocks; and

adding the surrounding blocks exceeding a DC threshold to the segmentation result.

16. The method of claim 13 wherein said filling step comprises the steps of:

e. determining if the DC feature of one of the blocks of the current frame is close to a neighboring block of respective one or more said foreground objects;

f. if it is determined that the DC feature of one of the blocks of the current frame is close to the neighboring foreground block, classifying the block as foreground; and

repeating steps e. through f. for all neighboring blocks.

17. The method of claim 1 wherein in step a., background model training comprises the step of:

estimating said background model from one or more features extracted from a training sequence, said features extracted from said training sequence being determined by analyzing said training sequence in a transform domain.

18. The method of claim 17 wherein said training sequence comprises one or more training frames of the video sequence, said training frames without foreground objects.

19. The method of claim 18 wherein in step a., said background model is determined as a Gaussian distribution with mean μ

and variance σ

² of said one or more features estimated from said training sequence.

20. The method of claim 19 wherein initial values of said mean μ

and variance σ

² of said one or more features are determined using a Maximum Likelihood Estimation.

21. The method of claim 18 wherein in step a., said background model is determined with mean μ

and variance σ

² of said one or more features estimated from said training sequence.

22. The method of claim 21 wherein initial values of said mean μ

and variance σ

² of said one or more features are determined using a Maximum Likelihood Estimation.

23. The method of claim 1 wherein in step a., said background model training comprises determining said background model from one or more features extracted from one or more frames in said video sequence.

24. The method of claim 23 wherein in step a., said background model is determined as a Gaussian distribution with mean μ

and variance σ

² of said one or more features estimated from said training sequence extracted from one or more frames in said video sequence.

25. The method of claim 23 wherein in step a., said background model is determined with mean μ

and variance σ

² of said one or more features estimated from said training sequence extracted from one or more frames in said video sequence.

26. A system for foreground segmentation of a video sequence of at least one frame comprising:

means for determining a background model from background model training;

means for analyzing said at least one frame in said video sequence in a transform wherein said transform is the discrete cosine transform (DCT) domain said at least one frame is divided into a plurality of blocks;

means for extracting one or more features of the analyzed at least one frame; and

means for segmenting said at least one frame in said video sequence by determining if one or more features satisfy a threshold value between said background model to provide a segmentation result of one or more foreground objects wherein a first said feature is a DC feature comprising a DC coefficient of said DCT and a second said feature is an AC feature comprising a weighted sum of DCT coefficients of said plurality of blocks.

27. The system of claim 26 wherein said weighted sum is determined with weights which are varied to emphasize different aspects of said video sequence.

28. The system of claim 26 wherein said AC feature is represented by f_AC determined by:

$f_{A<br><br><br><br>C}=\underset{i=0}{\overset{3}{\sum <br><br>}}<br><br>\underset{j=0}{\overset{3}{\sum <br><br>}}<br><br>\left(i^2+j^2\right)·<br><br><br><br>\mathrm{DCT}<br><br>\left(i,j\right)<br><br>.$

29. The system of claim 28 wherein said block is segmented as a foreground block if said block meets a first said threshold value based on a difference of said AC feature and a mean of said AC feature in the background model and/or a second said threshold value based on a difference of said DC feature and mean of said DC feature in said background model.

30. The system of claim 28 further comprising:

means for updating said background model based on either said DC feature or said AC feature and a learning parameter.

31. The system of claim 30 wherein the blocks of said background model are updated as follows:

μ

_t=(1−

α

_μ

)μ

<sub>t−

1</sub>+α

_μ

·

x

σ

_t²=(1−

α

_σ

)σ

<sub>t−

1</sub>²+α

_σ

·

(x−

μ

_t)²,

where t and t−

1 are the frame numbers, x represents either the AC feature or the DC feature, and α

is a learning parameter controlling the learning speed.

32. The system of claim 31 further comprising:

means for determining if a global change has occurred in said current frame;

if a global change occurred, increasing the learning parameter which is used with said DC feature or said AC feature for updating said background model.

33. The system of claim 32 wherein the learning parameter is increased by:

means for determining if the foreground objects were detected in a previous frame;

if no foreground objects were detected, means for declaring the at least one frame as background in the background model and increasing said learning parameter;

or

if foreground objects were detected in the previous frame,

means for dilating the segmentation result and using the dilated segmentation result as a current segmentation result;

means for modeling illumination changes using the blocks of background blocks in the background model;

means for modeling a complete background model using interpolation and/or extrapolation;

means for re-segmenting a current frame in said video sequence by determining if one or more features of said current frame analyzed in the transform domain satisfy a threshold value between said background model; and

means for increasing the learning parameter.

34. The system of claim 33 wherein size filtering is performed by:

means for determining if a blob size of a blob of the one or more foreground objects is less than a predetermined first threshold value;

if the blob size is less than the predetermined first threshold value, means for removing the blob;

or

if the blob size is greater than the first threshold value, means for determining if a ratio of a number of AC blocks representing the AC feature to a number of DC blocks representing the DC feature is less than a predetermined second threshold value;

or

if the ratio of the number of AC blocks to the number of DC blocks is less than the second threshold value, means for removing the blob;

or

if the ratio of the number of AC blocks to the number of DC blocks is not less than the second threshold value, means for determining if the ratio of the number of AC blocks to the number of DC blocks is greater than a predetermined third threshold value;

if a ratio of the number of AC blocks to the number of DC blocks is not greater than the third threshold value, means for removing the blob, or if the ratio of the number of AC blocks to the number of DC blocks is not greater than the third threshold value means for repeating said size filtering for all blobs.

35. The system of claim 30 further comprising means for removing a false alarm by size filtering.

36. The system of claim 30 further comprising:

means for detecting sudden local illumination changes or moved background objects; and

means for updating said background model to remove false ones of said one or more foreground objects.

37. The system of claim 36 wherein said means for detecting sudden local illumination changes or moved background objects comprises:

means for determining if a blob of the foreground object matches roughly to a previous blob of the foreground object;

if the blob does not match roughly with the previous blob of the foreground object, means for adding the blob to a record and setting a corresponding counter to one or if the blob matches roughly to a previous blob of the foreground object, means for increasing a corresponding counter by one;

means for determining if the counter is greater than a predefined threshold k;

if it is determined that the counter goes to the predefined threshold k, means for removing the blob and increasing a value of a learning parameter which is used for updating said background model.

38. The system of claim 30 further comprising means for filling said background model by labeling blocks near said one or more foreground objects with the same value as said respective one or more said foreground objects.

39. The system of claim 38 wherein said means for filling comprises:

means for labeling connected components of said background model;

means for determining if a blob size of the background model is less than a threshold value;

if it is determined that the blob size is less than the threshold value, means for labeling the blob as the foreground object.

40. The system of claim 38 wherein said filling comprises:

means for dilating blobs of the current frame to include one or more surrounding foreground blocks; and

means for adding the surrounding blocks exceeding a DC threshold to the segmentation result.

41. The system of claim 38 wherein said means for filling comprises:

means for determining if the DC feature of one of the blocks of the current frame is close to a neighboring block of respective one or more said foreground objects; and

if it is determined that the DC feature of one of the blocks of the current frame is close to the neighboring foreground block, means for classifying the block as foreground.

42. The system of claim 26 wherein said background model training comprises:

means for estimating said background model from one or more features extracted from a training sequence, said features extracted from said training sequence being determined by analyzing said training sequence in a transform domain.

43. The system of claim 42 wherein said training sequence comprises one or more training frames of the video sequence, said training frames without foreground objects.

44. The system of claim 43 wherein said background model is determined as a Gaussian distribution with mean μ

and variance σ

² of said one or more features estimated from said training sequence.

45. The system of claim 44 wherein initial values of said mean μ

and variance σ

² of said one or more features are determined using a Maximum Likelihood Estimation.

46. The system of claim 43 wherein said background model is determined with mean μ

and variance σ

² of said one or more features estimated from said training sequence.

47. The system of claim 46 wherein initial values of said mean μ

and variance σ

² of said one or more features are determined using a Maximum Likelihood Estimation.

48. The system of claim 26 wherein said background model training comprises means for determining said background model from one or more features extracted from a one or more frames in said video sequence.

49. The system of claim 26 wherein said background model is determined as a Gaussian distribution with mean μ

and variance σ

² of said one or more features estimated from said training sequence extracted from one or more frames in said video sequence.

50. The system of claim 26 wherein said background model is determined with mean μ

and variance σ

² of said one or more features estimated from said training sequence extracted from one or more frames in said video sequence.