Imaging device with improved image segmentation

• US 7,881,532 B2
• Filed: 02/24/2010
• Issued: 02/01/2011
• 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:
  US12/712,023
• Publication Number:
  US 20100150443A1
• Time in Patent Office: 342 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. An automated imaging device for identifying an object in an image, wherein the device includes a processor configured to process pixel data representing the image by performing the steps of:

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

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

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

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

2. The automated imaging device of claim 1, wherein the pixels are sorted based on any of the following attribute values:

brightness, hue, or gradient.

3. The automated imaging device of claim 1, wherein the object is located in step b by adding a respective one of the sorted pixels to the labeling image to create a new object or an updated old object.

4. The automated imaging device of claim 3, wherein the new object is created if the respective added pixel is not adjacent to another pixel or object already placed on the labeling image.

5. The automated imaging device of claim 3, wherein the updated old object is created if the respective added pixel is adjacent to the already existing old object or if the added pixel joins two old objects already existing on the labeling image.

6. The automated imaging device of claim 1, wherein the object is assigned a label, and wherein labels are updated for each added pixel.

7. The automated imaging device of claim 6, wherein the label of the object builds on respective labels of one or more previously added pixels.

8. The automated imaging device of claim 1, wherein the features of the object are calculated from features of an object located when a pixel was previously added.

9. The automated imaging device of claim 1, wherein the object is output to the output image only if the object'"'"'s features when calculated when the respective sorted pixel is added are a better match to the acceptance criteria than the object'"'"'s features when calculated for all previously added pixels.

10. The automated imaging device of claim 1, wherein the processor is configured to process two-dimensional and three-dimensional images.

11. The automated imaging device of claim 1, wherein the object 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 automated imaging device of claim 1, wherein the object is any of the following:

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

13. The automated imaging device of claim 1, wherein the 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 automated imaging device of claim 1, wherein the acceptance criteria comprises any of the following:

size, shape, texture, color, or density.

15. The automated imaging device of claim 1, wherein the processor employs multiple acceptance criteria to identify different kinds of objects in the labeling image simultaneously.

16. The automated imaging device of claim 1, wherein steps b and c are performed repeatedly by the processor until a point representing background pixels values in the range of attribute values, or a point in the range of attribute values representing pixel values not related to the objects being located, is reached.

17. An automated imaging device for identifying an object in an image, comprising:

a processor; and

a computer readable medium associated with the processor, the computer readable medium having computer readable program code embodied therein that, when executed by the processor, causes the processor to process pixel data representing the image, including performing the steps of;

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

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

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

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

18. The automated imaging device of claim 17, wherein the computer readable program code embodied in the computer readable medium, when executed by the processor, causes the processor to perform steps b and c repeatedly, until a point representing background pixels values in the range of attribute values, or a point in the range of attribute values representing pixel values not related to the objects being located, is reached.

19. An automated imaging device for identifying an object in an image, wherein the device includes a processor configured to process pixel data representing the image by performing the steps of:

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

b. adding one of the pixels to a labeling image to create a new object or update an old object;

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

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

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

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

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

20. The automated imaging device of claim 19, wherein the pixels are sorted based on any of the following attribute values:

brightness, hue, or gradient.

21. The automated imaging device of claim 19, wherein the plurality of threshold values is brightness, hue, or gradient.

22. The automated imaging device of claim 19, wherein the new object is created if the added pixel is not adjacent to another pixel or object already placed on the labeling image.

23. The automated imaging device of claim 19, wherein the updated old object is created if the added pixel is adjacent to already existing the old object or if the added pixel joins two old objects already existing on the labeling image.

24. The automated imaging device of claim 19, wherein the processor is configured to process two-dimensional and three-dimensional images.

25. The automated imaging device of claim 19, wherein the object 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 automated imaging device of claim 19, wherein the object is any of the following:

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

27. The automated imaging device of claim 19, wherein the 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 automated imaging device of claim 19, wherein the acceptance criteria comprises any of the following:

size, shape, texture, color, or density.

29. The automated imaging device of claim 19, wherein the processor employs multiple acceptance criteria to identify different kinds of objects in the labeling image simultaneously.

30. The automated imaging device of claim 19, wherein the created new object or the updated old object is assigned a label, and wherein labels are updated for each added pixel.

31. The automated imaging device of claim 30, wherein the labels build on labels from a previously added pixel.

32. The automated imaging device of claim 19, wherein the features of the created new object or the updated old object are calculated from features of an object located when a pixel was previously added.

33. The automated imaging device of claim 19, wherein the updated old object is output to the output image only if features of the updated old object calculated when the sorted pixel is added are a better match to the acceptance criteria than features of the updated old object calculated for all previously added pixels.