Method for improved image segmentation

• US 7,689,038 B2
• Filed: 01/09/2006
• Issued: 03/30/2010
• Est. Priority Date: 01/10/2005
• Status: Active Grant

• Current Assignee: Cytyc Corporation (Hologic Incorporated)
• Original Assignee: Cytyc Corporation (Hologic Incorporated)
• Inventors: Zahniser, Michael
• Primary Examiner(s): CHANG, JON CARLTON
• Application Number:
  US11/328,354
• Publication Number:
  US 20070036436A1
• Time in Patent Office: 1,541 Days
• Field of Search: 382/173, 382/180, 382/190, 382/128, 382/133, 382/171, 382/172
• 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 one of said sorted pixels to a labeling image to locate an object in said labeling image;

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

d. starting with one extreme point in said range of attribute values, performing steps b and c repeatedly utilizing a computer until another extreme point in said range of attribute values is reached.

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

brightness, hue, or gradient.

3. The method to identify each object in the image, as per claim 1, wherein said object is located by adding said one of said sorted pixels to the labeling image to create a new object or an updated old object.

4. The method to identify each object in the 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. The method to identify each object in the 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 labeling image.

6. The method to identify each object in the image, as per claim 1, wherein said object is assigned a label, wherein labels are updated for each added pixel.

7. The method to identify each object in the image, as per claim 6, wherein said label of said object builds on labels from a previously added pixel.

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

9. The method to identify each object in the image, as per claim 1, wherein said object is 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. The method to identify each object in the image, as per claim 1, wherein said method is performed on two-dimensional or three-dimensional images from biological or non-biological applications.

11. The method to identify each object in the image, as per claim 10, wherein said object in said biological applications is any of the following:

a cell, a nucleus, cytoplasm, a nuclear or cytoplasmic inclusion, clustered cells, or an object within images produced by imaging devices.

12. The method to identify each object in the image, as per claim 10, wherein said object in said non-biological applications is any of the following:

a component on a circuit board, or a man-made or natural object in a satellite image.

13. The method to identify each object in the 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. The method to identify each object in the image, as per claim 1, wherein said acceptance criteria are any of the following:

size, shape, texture, color, or density.

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

16. The method to identify each object in the image, as per claim 1, wherein steps b and c are performed repeatedly until a point representing background pixels values in said range of attribute values, or a point in said range of attribute values representing pixel values not related to said objects being located, is reached.

17. A computer readable medium having computer readable program code embodied therein for execution by a processor to perform a method comprising:

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

b. adding one of said sorted pixels to a labeling image to locate an object in said labeling image;

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

d. starting with one extreme point in said range of attribute values, performing steps b and c repeatedly until another extreme point in said range of attribute values is reached.

18. The computer readable medium having computer readable program code embodied therein for execution by the processor to perform the method, as per claim 17, wherein steps b and c are performed repeatedly until a point representing background pixels values in said range of attribute values, or a point in said range of attribute values representing pixel values not related to said objects being located, is reached.

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 one of said pixels to a labeling image to create a new object or update an old object;

c. calculating features of said created new object or said updated old object;

d. matching said calculated features of said created new object or said updated old object with a pre-defined criteria;

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

f. staffing with one extreme point in said range of attribute values, performing steps b through e repeatedly utilizing a computer until a stopping point is reached, said stopping point being selected from the group consisting of;

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

20. The method to identify each object in the image under the 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. The method to identify each object in the image under the plurality of threshold values, as per claim 19, wherein said plurality of threshold values is brightness, hue, or gradient.

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

23. The method to identify each object in the image under the plurality of threshold values, as per claim 19, 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 labeling image.

24. The method to identify each object in the image under the 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. The method to identify each object in the image under the plurality of threshold values, as per claim 24, wherein said object in said biological applications is any of the following:

a cell, a nucleus, cytoplasm, a nuclear or cytoplasmic inclusion, clustered cells or an object within images produced by imaging devices.

26. The method to identify each object in the image under the plurality of threshold values, as per claim 24, wherein said object in said non-biological applications is any of the following:

a component on a circuit board, or a man-made or natural object in a satellite image.

27. The method to identify each object in the image under the 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. The method to identify each object in the image under the plurality of threshold values, as per claim 19, wherein said acceptance criteria are any of the following:

size, shape, texture, color, or density.

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

30. The method to identify each object in the image under the plurality of threshold values, as per claim 19, wherein said created new object or said updated old object is assigned a label, wherein labels are updated for each added pixel.

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

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

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