Method for improved image segmentation

• US 20070036436A1
• Filed: 01/09/2006
• Published: 02/15/2007
• Est. Priority Date: 01/10/2005
• Status: Active Grant

• Current Assignee: Cytyc Corporation (Hologic Incorporated)
• Original Assignee: Cytyc Corporation (Hologic Incorporated)
• Inventors: Zahniser, Michael
• Granted Patent: US 7,689,038 B2
• Time in Patent Office: Days
• US Class Current: 382/180
• CPC Class Codes: G06T 2207/10072 Tomographic images
• CPC Class Codes: G06T 2207/30024 Cell structures in vitro; Tissue sections in vitro
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06V 10/267 by performing operations on regions, e.g. growing, shrinking or watersheds
• CPC Class Codes: G06V 20/695 Preprocessing, e.g. image segmentation

Abstract

An improved image segmentation algorithm is provided that identifies each object in an image. Pixels of the image are sorted based on a range of attribute values of the image. These pixels are then added to a labeling image one by one starting with an extreme point in the range of attribute values. Features are calculated for each object located and these features are matched with pre-defined acceptance criteria. If there is a match, the object is output to an output image. The steps of adding pixels to the image, evaluating the features of the resulting objects and outputting the objects are repeated until a stopping point is reached.

Claims

1. ) A method to identify each object in an image, said method comprising steps of:

a) sorting pixels based on a range of attribute values of said image;

b) adding said sorted pixels, one by one, to a labeling image to locate objects in said labeling image, starting with an extreme point in said range of attribute values;

c) outputting said objects onto an output image if features of said objects match a pre-defined acceptance criteria; and

d) performing steps b and c repeatedly until a stopping point is reached, said stopping point representing another extreme point in said range of attribute values.

2. ) A method to identify each object in an image, as per claim 1, wherein said pixels are sorted based on any of the following attribute values:

brightness, hue, or gradient.

3. ) A method to identify each object in an image, as per claim 1, wherein said objects are located by adding pixels one by one to a labeling image to create a new object or an updated old object.

4. ) A method to identify each object in an image, as per claim 3, wherein said new object is created if said added pixel is not adjacent to another pixel or object already placed on said labeling image.

5. ) A method to identify each object in an image, as per claim 3, wherein said updated old object is created if said added pixel is adjacent to already existing said old object or if said added pixel joins two old objects already existing on said image.

6. ) A method to identify each object in an image, as per claim 1, wherein said objects are assigned labels and said labels are updated for each added pixel.

7. ) A method to identify each object in an image, as per claim 6, wherein said labels of said objects build on labels from a previously added pixel.

8. ) A method to identify each object in an image, as per claim 1, wherein said features of said objects are calculated from features of objects located when a pixel was previously added.

9. ) A method to identify each object in an image, as per claim 1, wherein said objects are output to said output image only if said object'"'"'s features calculated when said sorted pixel is added are a better match to said acceptance criteria than said object'"'"'s features calculated for all previously added pixels.

10. ) A method to identify each object in an image, as per claim 1, wherein said method is performed on two-dimensional or three-dimensional images from biological or non-biological applications.

11. ) A method to identify each object in an image, as per claim 10, wherein said objects in said biological applications are any of the following:

cells, nuclei, cytoplasms, nuclear or cytoplasmic inclusions, clustered cells, or objects within images produced by imaging devices such as x-rays, CAT scans or magnetic resonance imaging.

12. ) A method to identify each object in an image, as per claim 10, wherein said objects in said non-biological applications are any of the following:

components on a circuit board, or man-made or natural objects in a satellite image.

13. ) A method to identify each object in an image, as per claim 1, wherein said features are any of the following:

perimeter, area, object moment of inertia, eccentricity, elliptical axes, best fit to an ellipse, contrast, grey value, optical density mean, standard deviation, or texture.

14. ) A method to identify each object in an image, as per claim 1, wherein said acceptance criteria are any of the following:

size, shape, texture, color, or density.

15. ) A method to identify each object in an image, as per claim 1, wherein said method uses multiple acceptance criteria to identify different kinds of objects in said image simultaneously.

16. ) A method to identify each object in an image, as per claim 1, wherein said stopping point is a point representing background pixels values in said range of attribute values or a point representing pixel values not related to said objects being located.

17. ) An article of manufacture comprising a computer readable medium having computer readable program code embodied therein which identifies each object in an image, said medium comprising:

computer readable program code sorting pixels based on a range of attribute values of said image;

computer readable program code adding said sorted pixels, one by one, to a labeling image to locate objects in said labeling image, starting with an extreme point in said range of attribute values;

computer readable program code outputting said objects onto an output image if features of said objects match a pre-defined acceptance criteria; and

computer readable program code performing steps b and c repeatedly until a stopping point is reached, said stopping point representing another extreme point in said range of attribute values.

18. ) An article of manufacture comprising a computer readable medium having computer readable program code embodied therein which identifies each object in an image, as per claim 17, wherein said stopping point is a point representing background pixels values in said range of attribute values or a point representing pixel values not related to said objects being located.

19. ) A method to identify each object in an image under a plurality of threshold values, said method comprising steps of:

a) sorting pixels in said image based on a range of attribute values of said pixels, wherein said range of attribute values correspond to said plurality of threshold values;

b) adding pixels, one by one, to a labeling image to create new objects or update old objects, starting with an extreme point in said range of attribute values;

c) calculating features of said created new objects and said updated old objects;

d) matching said calculated features of said created new objects and said updated old objects with a pre-defined criteria;

e) outputting said created new objects and said updated old objects on an output image if an acceptance criteria is satisfied for said features; and

f) performing step b-e repeatedly until a stopping point is reached, said stopping point chosen from any of the following;

another extreme point in said range of values, a point representing background pixels values in said range of attribute values or a point representing pixel values not related to said new objects and said updated old objects.

20. ) A method to identify each object in an image under a plurality of threshold values, as per claim 19, wherein said pixels are sorted based on any of the following attribute values:

brightness, hue, or gradient.

21. ) A method to identify each object in an image under a plurality of threshold values, as per claim 19, wherein said plurality of threshold values is brightness, hue, or gradient.

22. ) A method to identify each object in an image under a plurality of threshold values, as per claim 19, wherein said new objects are created if said added pixel is not adjacent to another pixel or object already placed on said labeling image.

23. ) A method to identify each object in an image under a plurality of threshold values, as per claim 19, wherein said updated old objects are created if said added pixel is adjacent to already existing said old objects or if said added pixel joins any of said old objects.

24. ) A method to identify each object in an image under a plurality of threshold values, as per claim 19, wherein said method is performed on two-dimensional or three-dimensional images from biological or non-biological applications.

25. ) A method to identify each object in an image under a plurality of threshold values, as per claim 24, wherein said objects in said biological applications are any of the following:

cells, nuclei, cytoplasms, nuclear or cytoplasmic inclusions, clustered cells or objects within images produced by imaging devices such as x-rays, CAT scans, magnetic resonance imaging.

26. ) A method to identify each object in an image under a plurality of threshold values, as per claim 24, wherein said objects in said non-biological applications are any of the following:

components on a circuit board, or man-made or natural objects in a satellite image.

27. ) A method to identify each object in an image under a plurality of threshold values, as per claim 19, wherein said features are any of the following:

perimeter, area, object moment of inertia, eccentricity, elliptical axes, best fit to an ellipse, contrast, grey value, optical density mean, standard deviation, or texture.

28. ) A method to identify each object in an image under a plurality of threshold values, as per claim 19, wherein said acceptance criteria are any of the following:

size, shape, texture, color, or density.

29. ) A method to identify each object in an image under a plurality of threshold values, as per claim 19, wherein said method uses multiple acceptance criteria to identify different kinds of objects in said image simultaneously.

30. ) A method to identify each object in an image under a plurality of threshold values, as per claim 19, wherein said created new objects and said updated old objects are assigned labels and said labels are updated for each added pixel.

31. ) A method to identify each object in an image under a plurality of threshold values as per claim 30, wherein said labels build on labels from a previously added pixel.

32. ) A method to identify each object in an image under a plurality of threshold values, as per claim 19, wherein said features of said created new objects and said updated old objects are calculated from features of objects located when a pixel was previously added.

33. ) A method to identify each object in an image under a plurality of threshold values, as per claim 19, wherein said updated old objects are output to said output image only if features of said updated old objects calculated when said sorted pixel is added are a better match to said acceptance criteria than features of said updated old objects calculated for all previously added pixels.