Method of and apparatus for segmenting a pixellated image

• US 6,819,796 B2
• Filed: 12/26/2000
• Issued: 11/16/2004
• Est. Priority Date: 01/06/2000
• Status: Expired due to Fees

• Current Assignee: Sharp Kabushiki Kaisha (Hon Hai Precision Industry Co., Ltd.)
• Original Assignee: Sharp Kabushiki Kaisha (Hon Hai Precision Industry Co., Ltd.)
• Inventors: Hong, Qi He, Holliman, Nicolas Steven
• Primary Examiner(s): Wu, Jingge
• Application Number:
  US09/748,751
• Publication Number:
  US 20020037103A1
• Time in Patent Office: 1,421 Days
• Field of Search: 382/166, 382/173-178, 358/462-466
• US Class Current: 382/173
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• 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

Abstract

This invention relates to a method for segmenting a pixellated image, comprising: (a) selecting at least one first region from a first reference image; (b) deriving from values of pixels of the at least one first region a first threshold such that a first predetermined proportion of the pixels have values on a first side of the first threshold; (c) forming a difference image as a difference between each pixel of the image and a corresponding pixel of an image of a non-occluded background; and (d) allocating each difference image pixel to at least one first type of region if the value of the difference image pixel is on the first side of the first threshold and the values of more than a first predetermined number of neighboring difference image pixels are on the first side of the first threshold. An apparatus for performing the foregoing method is disclosed.

Claims

1. A method of segmenting a pixellated image, comprising the steps of:

(a) selecting at least one first region from a first reference image;

(b) deriving from values of pixels of the at least one first region a first threshold such that a first predetermined proportion of the pixels have values on a first side of the first threshold;

(c) forming a difference image as a difference between each pixel of the image and a corresponding pixel of an image of a non-occluded background; and

(d) allocating each difference image pixel to at least one first type of region if the value of the difference image pixel is on the first side of the first threshold and the values of more than a first predetermined number of neighbouring difference image pixels are on the first side of the first threshold.

2. A method as claimed in claim 1, characterised in that the first predetermined proportion is between 0.5 and 1.

3. A method as claimed in claim 2, characterised in that the first predetermined proportion is substantially equal to 0.75.

4. A method as claimed in claim 2, characterised in that the first predetermined number is substantially equal to half the number of neighbouring difference image pixels.

5. A method as claimed in claim 1, characterised in that each of the at least one first region and the at least one first type of region comprises at least one background region and the first side of the first threshold is below the first threshold.

6. A method as claimed in claim 5, characterised in that the first reference image comprises the difference between two images of the non-occluded background and the at least one first region comprises substantially the whole of the first reference image.

7. A method as claimed in claim 1, characterised in that the at least one first region is automatically selected.

8. A method as claimed in claim 7, characterised in that the at least one first region comprises at least one side portion of the first reference image.

9. A method as claimed in claim 1, characterised in that the at least one first region is manually selected.

10. A method as claimed in claim 1, characterised in that the neighbouring pixels in the step (d) are disposed in an array with the difference image pixel location substantially at the centre of the array.

11. A method as claimed in claim 1, characterised by repeating the steps (a) to (d) for a sequence of images having a common background.

12. A method as claimed in claim 11, characterised in that the first reference image is the preceding difference image.

13. A method as claimed in claim 12, characterised in that the at least one first region comprises the at least one first type of region of the preceding step (d).

14. A method as claimed in claim 13, characterised in that each step (d) comprises forming a first initial histogram of values of the difference image pixels allocated to the at least one first type of region and the step (b) derives the first threshold from a first resulting histogram which comprises the sum of the first initial histogram formed in the preceding step (d) and a first predetermined fraction less than one of the first resulting histogram of the preceding step (b).

15. A method as claimed in claim 14, characterised in that the first predetermined fraction is a half.

16. A method as claimed in claim 1, characterised by the steps of:

(e) selecting at least one second region from a second reference image;

(f) deriving from values of pixels of the at least one second region a second threshold such that a second predetermined proportion of the pixels have values on a second side opposite the first side of the second threshold; and

(g) allocating each difference image pixel, which is not allocated to the at least one first type of region, to at least one second type of region if the value of the difference image pixel is on the second side of the second threshold and the values of more than a second predetermined number of neighbouring difference image pixels are on the second side of the second threshold.

17. A method as claimed in claim 16, characterised in that the second predetermined proportion is between 0.5 and 1.

18. A method as claimed in claim 17, characterised in that the second predetermined proportion is substantially equal to 0.75.

19. A method as claimed in claim 16, characterised in that the second predetermined number is substantially equal to half the number of neighbouring difference image pixels.

20. A method an claimed in claim 16, characterised in that each of the at least one second region and the at least one second type of region comprises at least one foreground region and the second side of the second threshold is above the second threshold.

21. A method as claimed in claim 16, characterised in that the at least one second region is automatically selected.

22. A method as claimed in claim 21, characterised in that the at least one second region comprises a middle portion of the second reference image.

23. A method as claimed in claim 16, characterised in that the at least one second region is manually selected.

24. A method as claimed in claim 16, characterised in that the second reference image comprises the first reference image.

25. A method as claimed in claim 16, characterised in that the neighbouring pixels in the step (g) are disposed in an array with the difference image pixel location substantially at the centre of the array.

26. A method as claimed in claim 16, characterised by repeating the steps (e) to (g) for a sequence of images having a common background.

27. A method as claimed in claim 26, characterised in that the second reference image is the preceding difference image.

28. A method as claimed in claim 27, characterised in that the at least one second region comprises the at least one second type of region of the preceding step (g).

29. A method as claimed in claim 28, characterised in that each step (g) comprises forming a second initial histogram of values of the difference image pixels allocated to the at least one second type of region and the step (f) derives the second threshold from a second resulting histogram which comprises the sum of the second initial histogram formed in the preceding step (g) and a second predetermined fraction less than one of the second resulting histogram of the preceding step (f).

30. A method as claimed in claim 29, characterised in that the second predetermined fraction is a half.

31. A method as claimed in claim 16, characterised by allocating each difference image pixel, which is not allocated to the at least one first type of region and which is not allocated to the at least one second type of region, as a candidate first type of pixel if a value of the difference image pixel is less than a third threshold.

32. A method as claimed in claim 31, characterised in that the third threshold is between the first and second thresholds.

33. A method as claimed in claim 32, characterised in that the third threshold is the arithmetic mean of the first and second thresholds.

34. A method as claimed in claim 31, characterised by allocating each difference image pixel, which is not allocated to the at least one first type of region and which is not allocated to the at least one second type of region, to the at least one first type of region if more than a third predetermined number of the neighbouring pixels are allocated to the at least one first type of region or as candidate first type of pixel.

35. A method as claimed in claim 34, characterised in that the neighbouring pixels comprise an array of pixels with the difference image pixel location substantially at the centre of the array.

36. A method as claimed in claim 34, characterised in that the third predetermined number is half the number of neighbouring difference image pixels.

37. A method as claimed in claim 34, characterised by allocating each difference image pixel, which is not allocated to the at least one first type of region and which is not allocated to the at least one second type of region, to the at least one second type of region.

38. A method as claimed in claim 1, characterised in that the or each image and the background image are grey level images and the step (c) forms the difference between each image pixel and the corresponding background pixel as the difference between the grey level of each image pixel and the grey level of the corresponding background pixel.

39. A method as claimed in claim 1, characterised in that the step (c) comprises performing a moving window averaging step on the or each difference image.

40. A method as claimed in claim 1, characterised in that the or each image and the background image are colour images and the step (c) forms the difference between each image pixel and the corresponding background pixel as a colour distance between the colour of each image pixel and the colour of the corresponding background pixel.

41. A method as claimed in claim 40, characterised in that the colour distance is formed as:

$\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>{\mathrm{\alpha <br><br>}}_i<br><br><br><br>I_i-B_i<br><br>$

where n is the number of colour components of each pixel, I_i is the ith colour component of an image pixel, B_i is the ith colour component of a background pixel and α

₁ is a weighting factor.

42. A method as claimed in claim 41, characterised in that each α

₁ is equal to one.

43. A method as claimed in claim 41, characterised in that n is equal to 3, I₁ and B₁ are red colour components, I₂ and B₂ are green colour components and I₃ and B₃ are blue colour components.

44. A method as claimed in claim 41, characterised in that the step (c) forms colour component difference images I_i−

B_iand performs a moving window averaging step on each of the colour component difference images.

45. A method as claimed in claim 39, characterised in that the window has a size of 3×

3 pixels.

46. A method as claimed in claim 44, characterised in that the window has a size of 3×

3 pixels.

47. A method as claimed in claim 1, characterised by forming a binary mask whose elements correspond to difference image pixels, each element having a first value if the corresponding difference image pixel is allocated to the at least one first type of region and a second value different from the first value if the corresponding difference image pixel is allocated to the at least one second type of region.

48. A method as claimed in claim 5, characterised by replacing the value of each pixel of the or each image corresponding to a difference image pixel allocated to the at least one background region with the value of a corresponding background image pixel.

49. A method as claimed in claim 5, characterised by replacing the value of each pixel of the or each image corresponding to a difference image pixel allocated to the at least one background region with the value of a corresponding pixel of a different background.

50. A method as claimed in claim 49, characterised by replacing the value of each pixel of the or each image corresponding to a difference image pixel allocated to a boundary of at least one foreground region with a linear combination of the value of the image pixel and the value of the corresponding different background pixel.

51. A method as claimed in claim 50, characterised in that the linear combination comprises the arithmetic mean of the or each pair of corresponding pixel component values.

52. A method as claimed in claim 5, characterised by, for each colour component, forming a distribution of the differences between the colour component values of the pixels allocated to the at least one background region and the corresponding pixels of the non-occluded background image, determining a shift in the location of a peak in the distribution from a predetermined location, and correcting the colour component values of the pixels allocated to the at least one background region in accordance with the shift.

54. An apparatus for segmenting a pixellated image, characterised by a programmable data processor and a storage medium containing a program for controlling the data processor to perform a method as claimed in claim 1.

55. A storage medium containing a program for controlling a data processor to perform a method as claimed in claim 1.

56. A program for controlling a data processor to perform a method as claimed in claim 1.

58. An image capture device characterised by including an apparatus as claimed in claim 54.

53. An apparatus for segmenting a pixellated image, characterised by means for selecting at least one first region from a first reference image, means for deriving from values of pixels of the at least one first region a first threshold such that a first predetermined proportion of the pixels have values on a first side of the first threshold, means for forming a difference image as a difference between each pixel of the image and a corresponding pixel of an image of a non-occluded background, and means for allocating each difference image pixel to at least one first type of region if the value of the difference image pixel is on the first side of the first threshold and the values of more than a first predetermined number of neighbouring difference image pixels are on the first side of the first threshold.

57. An image capture device characterised by including an apparatus as claimed in claim 53.