Background estimation and segmentation based on range and color

• US 7,317,830 B1
• Filed: 11/07/2003
• Issued: 01/08/2008
• Est. Priority Date: 12/04/1998
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Vulcan Patents LLC
• Inventors: Darrell, Trevor, Harville, Michael, Woodfill, John, Gordon, Gaile
• Primary Examiner(s): SHERALI, ISHRAT I
• Application Number:
  US10/703,393
• Time in Patent Office: 1,523 Days
• Field of Search: 382/173, 382162-167, 382/106, 382/103, 382/168, 382/171, 382/118, 382/154, 348 1401- 1415, 348 42- 60, 345/589, 345/593, 356/602
• US Class Current: 382/173
• CPC Class Codes: G06T 2207/10021 Stereoscopic video; Stereoscopic image sequence
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 2207/20224 Image subtraction
• 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/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

Segmentation of background and foreground objects in an image is based upon the joint use of range and color data. Range-based data is largely independent of color image data, and hence not adversely affected by the limitations associated with color-based segmentation, such as shadows and similarly colored objects. Furthermore, color segmentation is complementary to range measurement in those cases where reliable range data cannot be obtained. These complementary sets of data are used to provide a multidimensional background estimation. The segmentation of a foreground object in a given frame of an image sequence is carried out by comparing the image frames with background statistics relating to range and normalized color, using the sets of statistics in a complementary manner. A background model is determined by estimating using a multidimensional histogram, recording pixel values, configuring the pixel values into a cluster, and selecting a largest cluster as representing the background model.

Claims

1. A method for distinguishing between background and foreground objects in an image, comprising the steps of:

i) determining respective range values for pixels in each of a plurality of related images;

ii) determining respective intensity values for pixels in each of said plurality of related images;

iii) establishing a multi-dimensional background model for at least some of said pixels on the basis of said range values and said intensity values;

iv) comparing the range value for a particular pixel in a given image with the background model for that pixel, and labeling the pixel as a foreground pixel if the range value differs from the background model by a range threshold; and

v) comparing the intensity value for said particular pixel in a given image with the background model for that pixel, and labeling the pixel as a foreground pixel if the intensity value differs from the background model by an intensity threshold.

2. The method of claim 1 further including the step of determining whether the range value for said particular pixel is valid, and performing said comparing step (iv) only if said range value is valid.

3. The method of claim 2 wherein determining whether the range value for said particular pixel is valid further includes:

computing a confidence value; and

comparing said confidence value to a threshold to determine if the range value for said particular pixel is valid.

4. The method of claim 2 further including the step of determining whether background range data for said particular pixel is valid, and if said background range data is not valid, labeling the particular pixel as a foreground pixel in response to the comparing step (iv) for neighboring pixels if a range gradient associated with said particular pixel is less than a gradient threshold.

5. The method of claim 1 further including the step of determining whether the luminance of said particular pixel is greater than a designated minimum value, and performing said comparing step (v) only if the luminance is greater than said minimum value.

6. The method of claim 1 further including the step of determining the ratio of the intensity value for said particular pixel to the background intensity value for that pixel, and labeling the pixel as a foreground pixel if said ratio is less than a first predetermined value.

7. The method of claim 6 wherein said first predetermined value is based upon a decrease in luminance due to shadows in an image.

8. The method of claim 6 further including the step of labeling the pixel as a foreground pixel if said ratio is greater than a second predetermined value.

9. The method of claim 8 wherein said second predetermined value is based upon an increase in luminance due to interreflections in an image.

10. The method of claim 1 further including the step of alternatively labeling the pixel as a foreground pixel if the luminance of the pixel is greater than a designated minimum value by a predetermined factor.

11. The method of claim 10 wherein said factor is at least 2.

12. The method of claim 10 wherein said alternative labeling step is performed only if the luminance of the background texture model for the pixel is less than said designated minimum value.

13. The method of claim 1 further including the step of updating said background model on the basis of range values and intensity values obtained from a sequence of N images.

14. The method of claim 13 further including the steps of detecting image-to-image changes in said range values and intensity values, and effectively adjusting the value of N in accordance with the detected changes.

15. The method of claim 14 wherein the value of N is effectively increased when the magnitude of detected changes increases.

16. The method of claim 1 wherein said intensity values are one-dimensional values corresponding to the luminance of pixels.

17. The method of claim 1 wherein said intensity values are two-dimensional values which are invariant to luminance.

18. The method of claim 1 wherein said intensity values represent a three-dimensional color space.

19. The method of claim 18 further including the step of normalizing said intensity values according to luminance.

20. A system for identifying foreground objects in an image comprising:

a sensor which determines intensity values for pixels within an image;

a range processor which determines distance values for pixels within said image;

a background estimator which computes a multi-dimensional background model for said pixels on the basis of said intensity values and said distance values; and

a discriminator which compares intensity and distance values for pixels in an image to said background model and determines whether said pixels represent a foreground object.

21. The system of claim 20 wherein said background estimator generates a multi-dimensional histogram of intensity and distance values for a pixel within a plurality of related images, and computes a background model for said pixel by means of a clustering technique.

22. The system of claim 20 wherein said discriminator determines the differences between the intensity and distance values for a pixel in an image and the background model for that pixel, and compares said differences to respective intensity and distance thresholds.

23. The system of claim 22 wherein said discriminator selectively adjusts said intensity threshold in accordance with the result of a comparison based upon said distance threshold.

24. The system of claim 22 wherein said discriminator increases said intensity threshold if the difference between the distance value for a pixel in an image and the background model for that pixel is less than said distance threshold.

25. The system of claim 20 wherein said intensity values are one-dimensional values corresponding to the luminance of pixels.

26. The system of claim 20 wherein said intensity values are two-dimensional values which are invariant to luminance.

27. The system of claim 20 wherein said intensity values represent a three-dimensional color space.

28. The system of claim 20 further including an intensity processor which normalizes said intensity values according to luminance.