Method and apparatus for segmenting small structures in images

• US RE43,152 E1
• Filed: 09/12/2008
• Issued: 01/31/2012
• Est. Priority Date: 05/04/1998
• Status: Expired due to Fees

• Current Assignee: Johns Hopkins University
• Original Assignee: Johns Hopkins University
• Inventors: Bankman, Isaac N., Nizialek, Tanya
• Primary Examiner(s): Tabatabai, Abolfazl
• Application Number:
  US12/210,107
• Time in Patent Office: 1,236 Days
• Field of Search: 382128-134, 382/164, 382/170, 382/173, 382/179, 378/37, 378/62, 378/90, 378/92, 378/98.4, 378/98.6, 378/98.9, 600/300, 600/407, 600/410, 600/516, 128/920, 128/922, 128/916
• US Class Current: 382/128
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/10116 X-ray image
• CPC Class Codes: G06T 2207/20156 Automatic seed setting
• CPC Class Codes: G06T 2207/20168 Radial search
• CPC Class Codes: G06T 2207/30068 Mammography; Breast
• CPC Class Codes: G06T 2207/30096 Tumor; Lesion
• CPC Class Codes: G06T 2207/30212 Military
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/149 involving deformable models, e.g. active contour models
• CPC Class Codes: G06T 7/181 involving edge growing; involving edge linking
• CPC Class Codes: G06T 7/187 involving region growing; involving region merging; involving connected component labelling

Abstract

A method for segmenting a small feature in a multidimensional digital array of intensity values in a data processor computes an edge metric along each ray of a plurality of multidimensional rays originating at a local intensity extreme (local maximum or minimum). A multidimensional point corresponding to a maximum edge metric on each said ray is identified as a ray edge point. Every point on each ray from the local extreme to the ray edge point is labeled as part of the small object. Further points on the feature are grown by labeling an unlabeled point if the unlabeled point is adjacent to a labeled point, and the unlabeled point has a more extreme intensity than the labeled point, and the unlabeled point is closer than the labeled point to the local extreme. The resulting segmentation is quick, and identifies boundaries of small features analogous to boundaries identified by human analysts, and does not require statistical parameterizations or thresholds manually determined by a user.

Claims

1. A method for segmenting a small feature in a multidimensional digital array of intensity values in a data processor, the method comprising:

computing an edge metric along each ray of a plurality of multidimensional rays originating at a local intensity extreme;

identifying a multidimensional edge point corresponding to a maximum edge metric on each said ray;

labeling every point on each said ray from said local intensity extreme to said edge point; and

labeling an unlabeled point if the unlabeled point is adjacent to a labeled point and the unlabeled paint point has a more extreme intensity than the labeled point and the unlabeled point is closer than the labeled point to the local intensity extreme.

2. The method of claim 1 wherein intensity is a vector of values and an edge metric is a magnitude of a vector difference in intensities between two points along each said ray divided by a multidimensional distance between the same two points.

3. The method of claim 1 further comprising additionally labeling an unlabeled point if the unlabeled point is adjacent to a labeled point and has a more extreme intensity than the labeled point and is no farther from the local intensity extreme than the sum of a distance from the labeled point to the local intensity extreme plus an expansive tolerance distance less than the spacing between adjacent points.

4. The method of claim 1 further comprising also labeling an unlabeled point if the unlabeled point is adjacent to a labeled point and the unlabeled point has a less extreme intensity than the labeled point and the unlabeled point is closer than the labeled point to the local intensity extreme by an inclusion tolerance distance.

5. The method of claim 4, wherein the inclusion tolerance distance is about a spacing distance between adjacent points in the array or more.

6. The method of claim 1, wherein the edge metric at a ray point along each ray is computed as the quotient of the absolute value of an intensity difference between the local intensity extreme and the ray point divided by the absolute value of a distance between the ray point and the local intensity extreme.

7. The method of claim 1, wherein a ray length of each said ray is scaled by an expected size of a small feature.

8. The method of claim 1, wherein

the local intensity extreme is a point with the maximum intensity among a subarray of the multidimensional digital array of intensity values, the subarray having a certain multidimensional size, and

the intensity of the local intensity extreme exceeds a bright threshold intensity.

9. The method of claim 8, wherein the certain multidimensional size is an expected size of a small feature.

10. The method of claim 1, wherein

the local intensity extreme is a point with the minimum intensity among a subarray of the multidimensional digital array of intensity values, the subarray having a certain multidimensional size, and

the intensity of the local intensity extreme is less than a dark threshold intensity.

11. The method of claim 10, wherein the certain multidimensional size is an expected size of a small feature.

12. The method of claim 1, wherein the multidimensional array is a digital image, and each point is a pixel.

13. The method of claim 12, wherein the digital image is a digitized mammogram and the small feature is a microcalcification candidate.

14. The method of claim 12, wherein the digital image is a video frame of a military scene and the small feature is a candidate target of a tiring firing system.

15. The method of claim 1, wherein said labeling continues until no further unlabeled point can be labeled.

16. The method of claim 15, further comprising relabeling a labeled point as a feature edge point if an adjacent point is an unlabeled point.

17. The method of claim 16, further comprising joining a plurality of small features into a composite feature when a feature edge point from one small feature of the plurality of small features is within a join distance of a feature edge point of another small feature of the plurality of small features.

18. A method for segmenting a small feature in a multidimensional digital array of intensity values in a dataprocessor, the method comprising:

computing an edge metric along each ray of plurality of multidimensional rays originating at a local intensity extreme;

;

identifying a multidimensional edge point corresponding to a maximum edge metric on each said ray;

;

labeling every point on each said ray from said local intensity extreme to said edge point;

labeling an unlabeled point if the unlabeled point is adjacent to a Labeled labeled point and the unlabeled point has a more extreme intensity than the labeled point and the unlabeled point is closer than the labeled point to the local intensity extreme;

;

and

additionally labeling an unlabeled point if the unlabeled point is adjacent to a labeled point and has a more extreme intensity than the labeled point and is no farther from the local intensity extreme than the sum of a distance from the labeled point to the local intensity extreme plus an expansive tolerance distance less than the spacing between adjacent points;

wherein

an expected size of a small feature is twice an integral number N times a spacing distance between adjacent points in the array,

N is greater than 1,

the maximum value of the difference in distances between the labeled point and the unlabeled point to the local intensity extreme (Gmax)=−

N+√

{square root over (N²+2))}, and

the expansive tolerance distance is less than about Gmax.

19. A data processing apparatus for segmenting a small feature in a multidimensional digital array of intensity values comprising:

an input for a plurality of intensity values arranged along regular increments in each of a plurality of dimensions;

a memory medium for storing the plurality of intensity values as a multidimensional digital array;

a processor configured to detect a local intensity extreme in the multidimensional digital array, to identify points along a plurality of rays originating at the total local intensity extreme, to identify one edge point on each ray of said plurality of rays, said edge point associated with a maximum edge metric along said ray, to label each point on each ray from the local intensity extreme to the edge point, and to label an unlabeled point adjacent to a labeled point if the unlabeled point has a more extreme intensity than the labeled point and the unlabeled point is closer than the labeled point to the local intensity extreme until no more unlabeled points can be labeled; and

an output for providing the labeled points for subsequent processing.

20. The apparatus of claim 19, wherein the plurality of intensity values arranged along regular increments in each of a plurality of dimensions is at least one digital image, and each point is a pixel.

21. The apparatus of claim 20, wherein the digital image is a digitized mammogram and the small feature is a microcalcification candidate.

22. A computer program embodied in a non-transitory computer readable medium for performing the steps of:

computing an edge metric along each ray of a plurality of multidimensional rays originating at a local intensity extreme, identifying a multidimensional edge point corresponding to a maximum edge metric on each said ray, labeling every point on each said ray from said local intensity extreme to said edge point, and labeling an unlabeled point if the unlabeled point is adjacent to a labeled point and the unlabeled point has a more extreme intensity than the labeled point and the unlabeled point is closer than the labeled point to the local intensity extreme.

23. A method of labeling pixels of an image so as to designate portions of the image that are associated with an object, the method comprising:

identifying a first pixel as belonging to an object due to the first pixel having an intensity that is a local intensity extreme, wherein the first pixel is at an interior of the object;

determining that a second pixel that lies on a ray that emanates from the first pixel has a maximum edge metric on the ray, wherein the second pixel has an intensity that is smaller in magnitude than the intensity of the first pixel;

labeling the second pixel as an edge pixel that lies on an edge of the object;

determining that a third pixel that is adjacent to the second pixel satisfies a predetermined criterion relative to one or more of the first and second pixels; and

labeling the third pixel as belonging to the object.

24. The method of claim 23, wherein the intensity of the first pixel is greater than the intensities of all pixels immediately adjacent to the first pixel.

25. The method of claim 23, wherein the intensity of the first pixel is less than the intensities of all pixels immediately adjacent to the first pixel.

26. The method of claim 23, wherein the edge metric comprises a slope quotient that compares a difference between intensities of the first pixel and a pixel that is being evaluated to a distance between the first pixel and the pixel that is being evaluated.

27. The method of claim 23, wherein the predetermined criterion comprises the third pixel being disposed along a substantially straight line between the first and second pixels.

28. The method of claim 23, wherein the predetermined criterion comprises:

an intensity of the third pixel being less than an intensity of the second pixel; and

a distance between the first and third pixels being smaller than a distance between the first and second pixels by no less than an inclusion tolerance distance.

29. The method of claim 23 wherein the predetermined criterion comprises an intensity of the third pixel being greater than an intensity of the second pixel.

30. The method of claim 23 wherein the predetermined criterion comprises:

an intensity of the third pixel being no less than an intensity of the second pixel; and

the third pixel being closer to the first pixel than the second pixel is to the first pixel.

31. The method of claim 23 wherein the predetermined criterion comprises:

an intensity of the third pixel being no greater than an intensity of the second pixel; and

the third pixel being closer to the first pixel than the second pixel is to the first pixel.

32. The method of claim 23 wherein the predetermined criterion comprises:

an intensity of the third pixel being no less than an intensity of the second pixel; and

a distance between the first and third pixels being no more than an expansive tolerance distance greater than a distance between the first and second pixels.

33. The method of claim 23 wherein the predetermined criterion comprises:

an intensity of the third pixel being no greater than an intensity of the second pixel; and

a distance between the first and third pixels being no more than an expansive tolerance distance greater than a distance between the first and second pixels.

34. The method of claim 23 wherein the predetermined criterion comprises:

an intensity of the third pixel being no less than an intensity of the second pixel; and

no less than an inclusion portion of the third pixel being on a side of a substantially straight inclusion line closest to the first pixel, the inclusion line intersecting the second pixel and being substantially perpendicular to a substantially straight line that intersects the first and second pixels.

35. The method of claim 23 wherein the predetermined criterion comprises:

an intensity of the third pixel being no greater than an intensity of the second pixel; and

no less than an inclusion portion of the third pixel being on a side of a substantially straight inclusion line closest to the first pixel, the inclusion line intersecting the second pixel and being substantially perpendicular to a substantially straight line that intersects the first and second pixels.

36. The method of claim 23, further comprising identifying as part of the edge of the object a fourth pixel that is immediately adjacent to at least one pixel that is identified as part of the object and that is immediately adjacent to at least four other pixels that are outside of the object.

37. A method of labeling a subset of pixels of an image, the method comprising:

labeling pixels of an image as belonging to a first object that is encompassed by a first edge;

labeling pixels of the image as belonging to a second object that is encompassed by a second edge; and

assembling the first and second objects into a third object that is larger than either of the first and second objects if a distance between the first and second edges is no more than a join distance.

38. The method of claim 37 wherein assembling the first and second objects into the third object comprises identifying as part of the third object a pixel that is disposed between the first and second edges.

39. The method of claim 37 wherein assembling the first and second objects into the third object comprises identifying as part of the third object a pixel that is disposed between the first and second edges and that is no farther than the join distance from the first edge and from the second edge.

40. A non-transitory computer-readable medium having instructions stored thereon, the instructions comprising:

instructions for labeling pixels of an image as belonging to a first object that is encompassed by a first edge;

instructions for labeling pixels of the image as belonging to a second object that is encompassed by a second edge; and

instructions for assembling the first and second objects into a third object that is larger than either of the first and second objects if a distance between the first and second edges is no more than a join distance.

41. A method of labeling pixels of an image so as to designate portions of the image that are associated with an object, the method comprising:

identifying a first pixel as belonging to an object due to the first pixel having an intensity that is a local intensity extreme, wherein the first pixel is spaced from an edge of the object;

identifying as belonging to the object a second pixel that lies on a first substantially straight line on which the first pixel also lies;

identifying a third pixel as belonging to the object after having identified the second pixel as belonging to the object, wherein the third pixel lies on the line at a position that is closer to the first pixel than is the second pixel; and

labeling each of the first, second, and third pixels as belonging to the object.

42. The method of claim 41, wherein the intensity of the first pixel is greater than the intensities of all pixels immediately adjacent to the first pixel.

43. The method of claim 41, wherein the intensity of the first pixel is less than the intensities of all pixels immediately adjacent to the first pixel.

44. The method of claim 41, wherein identifying the second pixel as belonging to the object comprises:

calculating respective slope quotients of respective differences between intensities of the first pixel and other pixels that are intersected by the line and respective distances between the first pixel and the other pixels, wherein the second pixel is one of the other pixels; and

determining that a magnitude of the slope quotient of the second pixel is larger than the magnitudes of the slope quotients for the remainder of the other pixels.

45. The method of claim 41, further comprising identifying as belonging to the object at least a fourth pixel that intersects a second line that also intersects the first pixel but that does not intersect the second and third pixels, the fourth pixel being identified before any pixel other than one or more of the first, second, and third pixels is identified as belonging to the object.

46. The method of claim 41, wherein the object comprises an edge and the second pixel forms at least a portion of the edge.

47. The method of claim 41, wherein the second and third pixels are identified before any pixel other than the first pixel is identified as belonging to the object.

48. The method of claim 41, wherein one or both of the second and third pixels have respective intensities that are smaller in magnitude than the intensity of the first pixel.

49. The method of claim 48, wherein the intensity of the third pixel is less than the intensity of the second pixel.

50. A non-transitory computer-readable medium having instructions stored thereon, the instructions comprising:

instructions for identifying a first pixel as belonging to an object due to the first pixel having an intensity that is a local intensity extreme, wherein the first pixel is spaced from an edge of the object;

instructions for identifying as belonging to the object a second pixel that lies on a first substantially straight line on which the first pixel also lies;

instructions for identifying a third pixel as belonging to the object after having identified the second pixel as belonging to the object, wherein the third pixel lies on the line at a position that is closer to the first pixel than is the second pixel; and

instructions for labeling each of the first, second, and third pixels as belonging to the object.

51. A non-transitory computer-readable medium having instructions stored thereon, the instructions comprising:

instructions for identifying a first pixel as belonging to an object due to the first pixel having an intensity that is a local intensity extreme, wherein the first pixel is at an interior of the object;

instructions for determining that a second pixel that lies on a ray that emanates from the first pixel has a maximum edge metric on the ray, wherein the second pixel has an intensity that is smaller in magnitude than the intensity of the first pixel;

instructions for labeling the second pixel as an edge pixel that lies on an edge of the object;

instructions for determining that a third pixel that is adjacent to the second pixel satisfies a predetermined criterion relative to one or more of the first and second pixels; and

instructions for labeling the third pixel as belonging to the object.