Method and apparatus for image segmentation

• US 6,707,940 B1
• Filed: 03/31/2000
• Issued: 03/16/2004
• Est. Priority Date: 03/31/2000
• Status: Expired due to Term

• Current Assignee: Beijing Xiaomi Mobile Software Co., Ltd. (Xiaomi Corp.)
• Original Assignee: Intel Corporation
• Inventors: Qian, Richard J.
• Primary Examiner(s): Au, Amelia M.
• Assistant Examiner(s): LAROSE, COLIN M
• Application Number:
  US09/541,061
• Time in Patent Office: 1,446 Days
• Field of Search: 382/263, 382/173, 382/308, 382/266, 382/264, 382/164, 382/199, 358/3.27, 348/586
• US Class Current: 382/173
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20192 Edge enhancement; Edge preservation
• CPC Class Codes: G06T 5/20 using local operators
• CPC Class Codes: G06T 5/50 using two or more images, e.g. averaging or subtraction
• CPC Class Codes: G06T 5/70 Denoising; Smoothing
• CPC Class Codes: G06T 7/194 involving foreground-background segmentation

Abstract

A method and apparatus is described that smoothes images within regions but not across boundaries. In one embodiment, a segmentation map is smoothed. Based on the color difference between pixels in an input frame and corresponding pixels in a background image, this segmentation map indicates the likelihood that each pixel in the input frame belongs to the foreground. The smoothed segmentation map may be processed further to reduce misclassification errors. Based on the segmentation map, the foreground portion of the image is superimposed over a new background image.

Claims

1. An apparatus comprising:

a gradient calculator configured and arranged to calculate (a) a gradient in each among a plurality of directions, including at least a vertical, a horizontal, and two diagonal directions, the directions being defined relative to a center pixel, and to calculate (b) smoothing factors, each smoothing factor corresponding to one among the gradients, wherein the center pixel has eight eight-neighbor pixels, and wherein, for each of the directions, the gradient calculator calculates a corresponding gradient as a difference of values of only two of the eight-neighbor pixels for a corresponding direction; and

a pixel value calculator configured and arranged to calculate a new value for the center pixel, the new value being expressed in terms of at least (c) a center pixel contribution and (d) a neighborhood contribution,

wherein the center pixel contribution is expressed at least in terms of an original value for the center pixel and at least one smoothing weight, the smoothing weight being expressed at least in terms of one of the smoothing factors, and

wherein the neighborhood contribution is expressed at least in terms of a smoothing product, wherein the smoothing product is expressed at least in terms of (e) one among the smoothing factors and (f) a value of a pixel that lies in the direction corresponding to the smoothing factor.

2. The apparatus according to claim 1, wherein the gradient calculator is further configured and arranged to calculate at least one among the smoothing factors at least in part by normalizing a magnitude of a corresponding gradient.

3. The apparatus according to claim 1, wherein at least one among the center pixel contribution and the neighborhood contribution is weighted by a factor related to the number of the corresponding plurality of directions.

4. The apparatus according to claim 1, wherein the new value for the center pixel is expressed in terms of at least the original value for the center pixel, the center pixel contribution, and the neighborhood contribution.

5. The apparatus according to claim 1, wherein a value of at least one among the gradients is independent of the original value of the center pixel.

6. The apparatus according to claim 1, wherein the directions include at least three directions that are not parallel to one another.

7. The apparatus according to claim 1, wherein the directions include at least two directions that are neither parallel nor orthogonal to one another.

8. An apparatus including a filter, said filter comprising:

a gradient calculator configured and arranged to calculate (a) a gradient in each among a plurality of directions, including at least a vertical, a horizontal, and two diagonal directions, the directions being defined relative to a center pixel having eight eight-neighbor pixels, the two diagonal directions being orthogonal to each other at the center pixel, and to calculate (b) smoothing factors, each smoothing factor corresponding to one among the gradients, wherein the center pixel has eight eight-neighbor pixels, and wherein, for each of the directions, the gradient calculator calculates a corresponding gradient as a difference of values of only two of the eight-neighbor pixels for a corresponding direction; and

a pixel value calculator configured and arranged to calculate a filtered value for the center pixel, the filtered value being expressed in terms of at least a center pixel contribution and a neighborhood contribution,

wherein the center pixel contribution is expressed at least in terms of an original value for the center pixel and at least one smoothing weight, the smoothing weight being expressed at least in terms of one of the smoothing factors,

wherein the neighborhood contribution is expressed at least in terms of a smoothing product, wherein the smoothing product is expressed at least in terms of (e) one among the smoothing factors and (f) a value of a pixel that lies in the direction corresponding to the smoothing factor,

wherein said filter is used to process each among substantially all of the pixels of an input image as a center pixel, and

wherein a filtered image comprises the filtered values calculated for said substantially all of the pixels of the input image.

9. The apparatus according to claim 8, said input image being a segmentation map.

10. The apparatus according to claim 9, said segmentation map being obtained by comparing at least a portion of an original image to a portion of a corresponding background image.

11. The apparatus according to claim 9, a value of each among substantially all of said pixels of said segmentation map being obtained at least in part by comparing a value of a pixel of an original image with a value of a corresponding pixel of an image of a background, wherein said background appears in at least a portion of the original image.

12. The apparatus according to claim 11, wherein said comparing includes applying one among a first function and a second function, wherein the first function is applied when an intensity of the pixel of the original image is below a predetermined threshold, and wherein the second function is applied when the intensity of the pixel of the original image is above the predetermined threshold.

13. The apparatus according to claim 12, at least one among said first function and said second function being based at least in part upon a distance in color space between a value of the pixel in the original image and a value,of the corresponding pixel in the image of the background.

14. The apparatus according to claim 11, said apparatus further including a spurious blob remover to receive the filtered image and to produce a refined image,

wherein said spurious blob remover identifies connected components in a binary image, said binary image being derived from the filtered image, and

wherein for each among substantially all of the pixels in a connected component in the binary image, the value of a corresponding pixel in the refined image depends at least in part on the size of the connected component.

15. The apparatus according to claim 14, said apparatus further including a pixel stabilizer to receive the refined image and to produce a stabilized image,

wherein said pixel stabilizer determines a value for a pixel in the stabilized image according to a classification history of a corresponding pixel in the refined image over a window of time.

16. The apparatus according to claim 15, wherein a first candidate for a value of a pixel in an output image is a value of a corresponding pixel in the original image, and

wherein a second candidate for the value of the pixel in the output image is a value of a corresponding pixel in a background image, and

wherein the value of the pixel in the output image is determined at least in part by a value of a corresponding pixel in the stabilized image.

17. A method comprising:

calculating a gradient in each among a plurality of directions, including at least a vertical, a horizontal, and two diagonal directions, the directions being defined relative to a center pixel, wherein the center pixel has eight eight-neighbor pixels, and wherein, for each of the directions, the gradient calculator calculates a corresponding gradient as a difference of values of only two of the eight-neighbor pixels for a corresponding direction;

for each among the gradients, calculating a corresponding smoothing factor; and

calculating a new value for the center pixel, the new value being expressed in terms of at least a center pixel contribution and a neighborhood pixel contribution,

wherein the center pixel contribution is expressed at least in terms of an original value for the center pixel and at least one smoothing weight, the smoothing weight being expressed at least in terms of one of the smoothing factors, and

wherein the neighborhood contribution is expressed at least in terms of a smoothing product, wherein the smoothing product is expressed at least in terms of (a) one among the smoothing factors and (b) a value of a pixel that lies in the direction corresponding to the smoothing factor.

18. The method according to claim 17, wherein calculating at least one among said smoothing factors comprises normalizing a magnitude of a corresponding gradient.

19. The method according to claim 17, wherein at least one among the center pixel contribution and the neighborhood contribution is weighted by a factor related to the number of the corresponding plurality.

20. The method according to claim 17, wherein the new value for the center pixel is expressed in terms of at least the original value for the center pixel, the center pixel contribution, and the neighborhood contribution.

21. A method comprising filtering an input image, said filtering comprising:

calculating a gradient in each among a plurality of directions, including at least a vertical, a horizontal, and two diagonal directions, the directions being defined relative to a center pixel, wherein the center pixel has eight eight-neighbor pixels, and wherein, for each of the directions, the gradient calculator calculates a corresponding gradient as a difference of values of only two of the eight-neighbor pixels for a corresponding direction;

calculating smoothing factors, each smoothing factor corresponding to one among the gradients; and

calculating a filtered value for the center pixel, the filtered value being expressed in terms of at least a center pixel contribution and a neighborhood contribution,

wherein the center pixel contribution is expressed at least in terms of an original value for the center pixel and at least one smoothing weight, the smoothing weight being expressed at least in terms of one of the smoothing factors, and

wherein the neighborhood contribution is expressed at least in terms of a smoothing product, wherein the smoothing product is expressed at least in terms of (a) one among the smoothing factors and (b) a value of a pixel that lies in the direction corresponding to the smoothing factor,

wherein said filtering is performed to process each among substantially all of the pixels of an input image as a center pixel, and

wherein a filtered image comprises the filtered values calculated for said substantially all of the pixels of the input image.

22. The method according to claim 21, said input image being a segmentation map.

23. The method according to claim 21, said segmentation map being obtained by comparing at least a portion of an original image to a portion of a corresponding background image.

24. The method according to claim 22, a value of each among substantially all of said pixels of said segmentation map being obtained at least in part by comparing a value of a pixel of an original image with a value of a corresponding pixel of an image of a background, wherein said background appears in at least a portion of the original image.

25. The method according to claim 24, wherein said comparing includes applying one among a first function and a second function,

wherein the first function is applied when an intensity of the pixel of the original image is below a predetermined threshold, and

wherein the second function is applied when the intensity of the pixel of the original image is above the predetermined threshold.

26. The method according to claim 25, at least one among said first function and said second function being based at least in part upon a distance in color space between a value of the pixel in the original image and a value of the corresponding pixel in the image of the background.

27. The method according to claim 24, said method further including removing spurious blobs from the filtered image to produce a refined image,

wherein said removing spurious blobs comprises identifying connected components in a binary image, said binary image being derived from the filtered image, and

wherein for each among substantially all of the pixels in a connected component in the binary image, the value of a corresponding pixel in the refined image depends at least in part on the size of the connected component.

28. The method according to claim 27, said method further including stabilizing pixels of the refined image to produce a stabilized image,

wherein said stabilizing pixels comprises determining a value for a pixel in the stabilized image according to a classification history of a corresponding pixel in the refined image over a window of time.

29. The method according to claim 28, wherein a first candidate for a value of a pixel in an output image is a value of a corresponding pixel in the original image, and

wherein a second candidate for the value of the pixel in the output image is a value of a corresponding pixel in a background image, and

wherein the value of the pixel in the output image is determined at least in part by a value of a corresponding pixel in the stabilized image.

30. A data storage medium having machine-readable code stored thereon, the machine-readable code comprising instructions executable by an array of logic elements, the instructions defining a method comprising filtering an input image, said filtering comprising:

calculating a gradient in each among a plurality of directions, including at least a vertical, a horizontal, and two diagonal directions, the directions being defined relative to a center pixel, wherein the center Pixel has eight eight-neighbor pixels, and wherein, for each of the directions, the gradient calculator calculates a corresponding gradient as a difference of values of only two of the eight-neighbor pixels for a corresponding direction;

calculating smoothing factors, each smoothing factor corresponding to one among the gradients; and

calculating a filtered value for the center pixel, the filtered value being expressed in terms of at least a center pixel contribution and a neighborhood contribution,

wherein the center pixel contribution is expressed at least in terms of an original value for the center pixel and at least one smoothing weight, the smoothing weight being expressed at least in terms of one of the smoothing factors, and

wherein the neighborhood contribution is expressed at least in terms of a smoothing product, wherein the smoothing product is expressed at least in terms of (a) one among the smoothing factors and (b) a value of a pixel that lies in the direction corresponding to the smoothing factor,

wherein said filtering is performed to process each among substantially all of the pixels of an input image as a center pixel, and

wherein a filtered image comprises the filtered values calculated for said substantially all of the pixels of the input image.

31. A method according to claim 30, said method further comprising producing an output image,

wherein the input image is a segmentation map of an original image, and

wherein a first candidate for a value of a pixel in the output image is a value of a corresponding pixel in the original image, and wherein a second candidate for the value of the pixel in the output image is a value of a corresponding pixel in a background image, and wherein the value of the pixel in the output image is determined at least in part by a value of a corresponding pixel in the filtered image.