System and method for background maintenance of an image sequence

• US 7,136,525 B1
• Filed: 09/20/1999
• Issued: 11/14/2006
• Est. Priority Date: 09/20/1999
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Toyama, Kentaro, Krumm, John C., Meyers, Brian R., Brumitt, Barry L.
• Primary Examiner(s): Wu, Jingge
• Assistant Examiner(s): LE, BRIAN Q
• Application Number:
  US09/400,346
• Time in Patent Office: 2,612 Days
• Field of Search: 382/173, 382/190, 382/125, 382/194, 382/199, 382/284, 382/203, 345/629, 345/611, 345/612, 345/630, 345/636, 345/641, 345/150
• US Class Current: 382/173
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20016 Hierarchical, coarse-to-fine, multiscale or multiresolution image processing; Pyramid transform
• CPC Class Codes: G06T 2207/20081 Training; Learning
• 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: G06V 10/28 Quantising the image, e.g. histogram thresholding for discrimination between background and foreground patterns

Abstract

The present invention is embodied in a system and method for maintaining a background model of an image sequence by processing on multiple spatial scales. These multiple spatial scales include a pixel scale, a regional scale and a frame scale. The image sequence undergoes pixel processing that determines a current background model and provides an initial pixel assignment as either a background or a foreground pixel. Region processing further refines the initial pixel assignments by considering relationships between pixels and possibly reassigning pixels. Frame processing further refines the current background model by determining whether a substantial change has occurred in the actual background and, if so, providing a more accurate background model.

Claims

1. A method for processing a current image frame of an image sequence to classify a pixel in the current image frame as a foreground pixel or a background pixel, comprising:

storing a list of actual history pixel values representing a history of actual pixel values for the pixel as determined in previous image frames;

predicting what value the pixel will have in a next frame of the image sequence using the list of actual history pixel values to generate a first pixel value prediction;

storing a list of predicted history pixel values representing a history of predicted pixel values for the pixel as determined in previous image frames;

predicting what value the pixel will have in a next frame in the image sequence using the list of predicted history pixel values to generate a second pixel value prediction;

determining an actual value of the pixel in the next frame of the image sequence; and

classifying the pixel as a foreground pixel if the actual value of the pixel in the next frame of the image sequence differs from any one of the first and second pixel value predictions by more than a threshold value.

2. The method of claim 1, wherein predicting what value the pixel will have in a next frame of the image sequence using the list of actual history pixel values to generate a first pixel value prediction further comprises using the formula:

$s_{\mathrm{tp}}=\underset{k=1}{\overset{p}{\sum <br><br>}}<br><br><br><br>a_k<br><br>s_{t-k}$

wherein s_tp is the first pixel value prediction at time t, s_t-k are the list of actual history pixel values, a_k are linear prediction coefficients, and p is a number of the prediction coefficients.

3. The method of claim 1, wherein predicting what value the pixel will have in a next frame of the image sequence using the list of predicted history pixel values to generate a second pixel value prediction further comprises using the formula:

$s_{\mathrm{tp}}=\underset{k=1}{\overset{p}{\sum <br><br>}}<br><br><br><br>a_k<br><br>s_{t-k}$

wherein s_tp is the second pixel value prediction at time t, s_t-k are the list of predicted history pixel values, a_k are linear prediction coefficients, and p is a number of the prediction coefficients.

4. The method of claim 2, further comprising computing the threshold value using the formula:

4.0*√

{square root over (E[e_t²)}]

wherein the expected squared prediction error E[e_t²] is given by the formula;

$E<br><br>\left[e_t^2\right]=E<br><br>\left[S_t^2\right]+\underset{k=1}{\overset{p}{\sum <br><br>}}<br><br><br><br>a_k<br><br>E<br><br>\left[S_t<br><br>S_{t-k}\right],$

wherein s_t is a pixel value prediction at time t.