Color image segmentation method

• US 6,978,042 B1
• Filed: 04/24/2000
• Issued: 12/20/2005
• Est. Priority Date: 04/23/1999
• Status: Expired due to Fees

• Current Assignee: Samsung Electronics Co. Ltd., Regents of the University of California (University of California)
• Original Assignee: Samsung Electronics Co. Ltd., Regents of the University of California (University of California)
• Inventors: Choi, Yang-Lim, Deng, Yining, Shin, Hyun-doo, Manjunath, Bangalore S.
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): Kassa, Yosef
• Application Number:
  US09/556,328
• Time in Patent Office: 2,066 Days
• Field of Search: 382/162, 382/163, 382/164, 382/165, 382/166, 382/167, 382/169, 382/170, 382/171, 382/172, 382/180, 382/190, 382/218, 382/219, 382/220, 382/224, 382/251, 382/252, 382/269, 382/274, 382/275, 382/282, 358/2.1, 358/512, 358/515, 358/518, 358/3.26, 358/3.27, 358/463
• US Class Current: 382/164
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/90 Determination of colour characteristics

Abstract

A color image segmentation method is provided. The color image segmentation method includes the steps of: (a) calculating a first value representing the degree of difference between a pixel and the color of peripheral pixels based a plurality of pixel values of an input image; (b) obtaining a converted image by converting the first calculated value into a value of a predetermined scale; and (c) segmenting the converted image. According to the color image segmentation method, an effective and an automatic segmentation is possible, and a segmentation speed is high even when segmenting an image containing much noise.

Claims

1. A color image segmentation method for segmenting a color image into a plurality of regions, comprising the steps of:

(a) calculating a first value representing a degree of difference between a pixel and peripheral pixels from the color of peripheral pixels based on a plurality of pixel values of an input image, wherein the color includes levels of one color,

(b) obtaining a converted image by converting the first value into a value of a predetermined scale, and

(c) segmenting the converted image based on a region growing method.

2. The color image segmentation method according to at least one of claim 1, wherein prior to the step (a), said method further comprises the step of (p-a) quantizing pixel values of the input image into a predetermined number of representative quantized pixel values.

3. The color image segmentation method according to claim 2, wherein the representative pixel values consist of 10–

20 values.

4. The color image segmentation method according to claim 3, wherein the step (a) comprises the steps of:

(a-1) defining a window which is centered at a pixel p and has a size of d×

d when d is a positive integer, said window having a set of pixels Z; and

(a-2) classifying a pixel position of each pixel of set Z into one of a C number of classes when i is a number between I and C, and

(a-3) obtaining a J-value, as said first value, with respect to each pixel in a class-map as;

$J=\frac{S_B}{S_W}=\frac{S_T-S_W}{S_W}$

where m_i is an average of positions of N_i data points in class Z_i, i=1 to C, and $S_T=\underset{z\in <br><br>Z}{\overset{}{\sum <br><br>}}<br><br>{<br><br>z-m<br><br>}^2<br><br><br><br>\mathrm{and}<br><br><br><br>S_W=\underset{i=1}{\overset{C}{\sum <br><br>}}<br><br>S_i=\underset{i=1}{\overset{C}{\sum <br><br>}}<br><br>\underset{z\in <br><br>Z_i}{\sum <br><br>}<br><br>{<br><br>z-m_i<br><br>}^2.$

5. The color image segmentation method according to claim 4, wherein d is an integer inclusive of and between 3 and 10.

6. The color image segmentation method according to claim 5, wherein the predetermined scale is a gray scale having values between 0 and 255.

7. The color image segmentation method according to claim 4, wherein the predetermined scale is a gray scale having values between 0 and 255.

8. The color image segmentation method according to claim 3, wherein the predetermined scale is a gray scale having values between 0 and 255.

9. The color image segmentation method according to claim 3, wherein prior to the step (a), said method further comprises the steps of:

(p-a-1) defining a window containing a center pixel; and

wherein said step (a) further comprises calculating a second value representing the degree of difference between a pixel and peripheral pixels from the color of peripheral pixels with respect to pixels in the defined window.

10. The color image segmentation method according to claim 9, wherein in said step (p-a-1), said window has a size of d×

d when d is a positive integer, said window having a set of pixels Z, and the step (a) comprises the steps of;

(a-1) classifying a pixel position of each pixel of set Z into one of a C number of s classes when i is a number between 1 and C, and

(a-2) obtaining a J-value, as said first value, with respect to each pixel in a class-map as;

$J=\frac{S_B}{S_W}=\frac{S_T-S_W}{S_W}$

where m_i as said second value is an average of positions of Ni data points in class Z_i, i=1 to C, and $S_T=\underset{z\in <br><br>Z}{\sum <br><br>}<br><br>{<br><br>z-m<br><br>}^2<br><br><br><br>\mathrm{and}<br><br><br><br>S_W<br><br>\underset{i=1}{\overset{C}{\sum <br><br>}}<br><br>S_i=\underset{i=1}{\overset{C}{\sum <br><br>}}<br><br>\underset{z\in <br><br>Z_i}{\sum <br><br>}<br><br>{<br><br>z-m_i<br><br>}^2.$

11. The color image segmentation method according to claim 10, wherein d is an integer inclusive of and between 3 and 10.

12. The color image segmentation method according to claim 11, wherein the predetermined scale is a gray scale having values between 0 and 255.

13. The color image segmentation method according to claim 10, wherein the predetermined scale is a gray scale having values between 0 and 255.

14. The color image segmentation method according to claim 9, wherein the predetermined scale is a gray scale having values between 0 and 255.

15. The color image segmentation method according to claim 2, wherein prior to the step (a), said method further comprises the steps of:

(p-a-1) defining a window containing a center pixel; and

wherein said step (a) further comprises calculating a second value representing the degree of difference between a pixel and peripheral pixels from the color of peripheral pixels with respect to pixels in the defined window.

16. The color image segmentation method according to claim 15, wherein in said step (p-a-1), said window has a size of d×

d when d is a positive integer, said window having a set of pixels Z, and the step (a) comprises the steps of;

(a-1) classifying a pixel position of each pixel of set Z into one of a C number of 26 classes when i is a number between 1 and C, and

(a-2) obtaining a J-value, as said first value, with respect to each pixel in a class-map as;

$J=\frac{S_B}{S_W}=\frac{S_T-S_W}{S_W}$

where m_i as said second value, is an average of positions of N_i data points in class Z_i, i=1 to C, and $S_T=\underset{z\in <br><br>Z}{\sum <br><br>}<br><br>{<br><br>z-m<br><br>}^2<br><br><br><br>\mathrm{and}<br><br><br><br>S_W<br><br>\underset{i=1}{\overset{C}{\sum <br><br>}}<br><br>S_i=\underset{i=1}{\overset{C}{\sum <br><br>}}<br><br>\underset{z\in <br><br>Z_i}{\sum <br><br>}<br><br>{<br><br>z-m_i<br><br>}^2.$

17. The color image segmentation method according to claim 16, wherein d is an integer inclusive of and between 3 and 10.

18. The color image segmentation method according to claim 17, wherein the predetermined scale is a gray scale having values between 0 and 255.

19. The color image segmentation method according to claim 16, wherein the predetermined scale is a gray scale having values between 0 and 255.

20. The color image segmentation method according to claim 15, wherein the predetermined scale is a gray scale having values between 0 and 255.

21. The color image segmentation method according to claim 2, wherein the step (a) comprises the steps of:

(a-1) defining a window which is centered at a pixel p and has a size of d×

d when d is a positive integer, said window having a set of pixels Z; and

(a-2) classifying a pixel position of each pixel of set Z into one of a C number of classes when i is a number between 1 and C; and

(a-3) obtaining a J-value, as said first value, with respect to each pixel in a class-map as;

$J=\frac{S_B}{S_W}=\frac{S_T-S_W}{S_W}$

where m_i is an average of positions of N_i data points in class Z_i, i=1 to C, and $S_T=\underset{z\in <br><br>Z}{\overset{}{\sum <br><br>}}<br><br>{<br><br>z-m<br><br>}^2<br><br><br><br>\mathrm{and}<br><br><br><br>S_W=\underset{i=1}{\overset{C}{\sum <br><br>}}<br><br>S_i=\underset{i=1}{\overset{C}{\sum <br><br>}}<br><br>\underset{z\in <br><br>Z_i}{\sum <br><br>}<br><br>{<br><br>z-m_i<br><br>}^2.$

22. The color image segmentation method according to claim 21, wherein d is an integer inclusive of and between 3 and 10.

23. The color image segmentation method according to claim 22, wherein the predetermined scale is a gray scale having values between 0 and 255.

24. The color image segmentation method according to claim 21, wherein the predetermined scale is a gray scale having values between 0 and 255.

25. The color image segmentation method according to claim 2, wherein the predetermined scale is a gray scale having values between 0 and 255.

26. The color image segmentation method according to claim 1, wherein prior to the step (a), said method further comprises the steps of:

(p-a-1) defining a window containing a center pixel; and

wherein said step (a) further comprises calculating a second value representing the degree of difference between a pixel and peripheral pixels from the color of peripheral pixels with respect to pixels in the defined window.

27. The color image segmentation method according to claim 26, wherein in said step (p-a-1), said window has a size of d×

d when d is a positive integer, said window having a set of pixels Z, and the step (a) comprises the steps of;

(a-1) classifying a pixel position of each pixel of set Z into one of a C number of classes when i is a number between 1 and C, and

(a-2) obtaining a J-value, as said first value, with respect to each pixel in a class-map as;

$J=\frac{S_B}{S_W}=\frac{S_T-S_W}{S_W}$

where m;

as said second value is an average of positions of Ni data points in class Z_i, i=1 to C, and $S_T=\underset{z\in <br><br>Z}{\sum <br><br>}<br><br>{<br><br>z-m<br><br>}^2<br><br><br><br>\mathrm{and}<br><br><br><br>S_W<br><br>\underset{i=1}{\overset{C}{\sum <br><br>}}<br><br>S_i=\underset{i=1}{\overset{C}{\sum <br><br>}}<br><br>\underset{z\in <br><br>Z_i}{\sum <br><br>}<br><br>{<br><br>z-m_i<br><br>}^2.$

28. The color image segmentation method according to claim 27, wherein d is an integer inclusive of and between 3 and 10.

29. The color image segmentation method according to claim 28, wherein the predetermined scale is a gray scale having values between 0 and 255.

30. The color image segmentation method according to claim 27, wherein the predetermined scale is a gray scale having values between 0 and 255.

31. The color image segmentation method according to claim 26, wherein the predetermined scale is a gray scale having values between 0 and 255.

32. The color image segmentation method according to claim 1, wherein the step (a) comprises the steps of:

(a-1) defining a window which is centered at a pixel p and has a size of d×

d when d is a positive integer, said window having a set of pixels Z; and

(a-2) classifying a pixel position of each pixel of set Z into one of a C number of classes when i is a number between 1 and C; and

(a-3) obtaining a J-value, as said first value, with respect to each pixel in a class-map as;

$J=\frac{S_B}{S_W}=\frac{S_T-S_W}{S_W}$

where m_i is an average of positions of Ni data points in class Z;

, i=1 to C, and $S_T=\underset{z\in <br><br>Z}{\overset{}{\sum <br><br>}}<br><br>{<br><br>z-m<br><br>}^2<br><br><br><br>\mathrm{and}<br><br><br><br>S_W=\underset{i=1}{\overset{C}{\sum <br><br>}}<br><br>S_i=\underset{i=1}{\overset{C}{\sum <br><br>}}<br><br>\underset{z\in <br><br>Z_i}{\sum <br><br>}<br><br>{<br><br>z-m_i<br><br>}^2.$

33. The color image segmentation method according to claim 32, wherein d is an integer inclusive of and between 3 and 10.

34. The color image segmentation method according to claim 33, wherein the predetermined scale is a gray scale having values between 0 and 255.

35. The color image segmentation method according to claim 32, wherein the predetermined scale is a gray scale having values between 0 and 255.

36. The method according to claim 32 further comprising:

(d) checking for effectiveness of segmentation of step (c) according to a result of $\stackrel{\_}{J}=\frac{1}{N}<br><br>\underset{k}{\sum <br><br>}<br><br>M_k<br><br>J_k$

where J_k is the J value of a region k,

M_k is a number of pixel points in region k, and

N is a total number of pixel points in the window.

37. The color image segmentation method according to at least one of claim 1, wherein the predetermined scale is a gray scale having values between 0 and 255.

38. An object-based color image processing method for processing a color image according to a color image segmentation method, wherein the color image segmentation method comprises the steps of:

(a) calculating a first value representing a degree of difference between a pixel and peripheral pixels from the color of peripheral pixels based on a plurality of pixel values of an input image, wherein the color includes levels of one color;

(b) obtaining a converted image by converting said first value into a value of a predetermined scale; and

(c) segmenting the converted image based on a region growing method.

39. The color image processing method according to claim 38, wherein the color image processing method complies with the MPEG-7 standard.

40. A color image segmentation method for segmenting a color image into a plurality of regions, comprising the steps of:

(a) quantizing pixel values of an image into a number of representative pixel values;

(b) calculating a first value representing a degree of difference between a pixel and peripheral pixels from the color of pixels in a predetermined size window using quantized representative pixel values, wherein the color includes levels of one color;

(c) obtaining a converted image by converting said first value into a value of a predetermined scale; and

(d) segmenting the converted image using a segmentation method based on a region to growing method.

41. The color image segmentation method according to claim 40, wherein the step (b) comprises the steps of:

(b-1) defining a window B which is centered at a pixel p and has a size of d×

d when d is a positive integer, said window having a set of pixels Z; and

(b-2) classifying a pixel position of each pixel of set Z into one of a C number of classes when i is a number between 1 and C, and

(b-3) obtaining a J-value as said first value with respect to each pixel in a class-map as;

$J=\frac{S_B}{S_W}=\frac{S_T-S_W}{S_W}$

where m_i is the average of positions of N_i data points in class Z_i, i=1 to C, and $S_T=\underset{z\in <br><br>Z}{\sum <br><br>}<br><br>{<br><br>z-m<br><br>}^2<br><br><br><br>\mathrm{and}<br><br><br><br>S_W<br><br>\underset{i=1}{\overset{C}{\sum <br><br>}}<br><br>S_i=\underset{i=1}{\overset{C}{\sum <br><br>}}<br><br>\underset{z\in <br><br>Z_i}{\sum <br><br>}<br><br>{<br><br>z-m_i<br><br>}^2.$

42. The color image segmentation method according to claim 41, wherein d is an integer inclusive of between 3 and 10.

43. The color image segmentation method according to one of claim 40 to claim 42, wherein the predetermined scale is a gray scale having values between 0 and 255.

44. A medium for storing program codes performing a color image segmentation method for segmenting a color image into a plurality of regions, wherein the medium comprises computer readable code means for:

(a) quantizing pixel values of an image into a number of representative pixel values;

(b) calculating a first value representing a degree of difference between a pixel and peripheral pixels from the color of pixels in a predetermined size window using quantized representative pixel values, wherein the color includes levels of one color;

(c) obtaining a converted image by converting said first value into a value of a predetermined scale; and

(d) segmenting the converted image using a segmentation method based on a region growing method.

45. The medium according to claim 44, wherein means (b) comprises computer readable code means for:

(b-1) defining a window which is centered at a pixel p and has a size of d×

d when d is a positive integer and Z is a set of all pixels in said window; and

(b-2) classifying each pixel position of the set of pixels Z into one of a C number of classes when i is a number between I and C, and

(b-3) obtaining a J-value, as said first value, with respect to each pixel in a class-map as;

$J=\frac{S_B}{S_W}=\frac{S_T-S_W}{S_W}$

where m;

is the average of positions of N_i data points in class Z_i, i=1 to C, and $S_T=\underset{z\in <br><br>Z}{\sum <br><br>}<br><br>{<br><br>z-m<br><br>}^2<br><br><br><br>\mathrm{and}<br><br><br><br>S_W<br><br>\underset{i=1}{\overset{C}{\sum <br><br>}}<br><br>S_i=\underset{i=1}{\overset{C}{\sum <br><br>}}<br><br>\underset{z\in <br><br>Z_i}{\sum <br><br>}<br><br>{<br><br>z-m_i<br><br>}^2.$

46. The medium according to claim 45, wherein d is set as an integer inclusive of and between 3 and 10.

47. The medium according to one of claim 44 to claim 46, wherein the predetermined scale is a gray scale having values between 0 and 255.

48. The medium of claim 44 further comprising a computer readable means for:

(e) checking for effectiveness of segmentation of provided by means (d) according a result $\stackrel{\_}{J}=\frac{1}{N}<br><br>\underset{k}{\sum <br><br>}<br><br>M_k<br><br>J_k$

where J_k is the J value of a region k,

M_k is a number of pixel points in region k, and

N is a total number of pixel points in the window.