Method and apparatus for segmenting small structures in images

• US RE43,894 E1
• Filed: 12/07/2011
• Issued: 01/01/2013
• 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:
  US13/314,021
• Time in Patent Office: 391 Days
• Field of Search: 382/128, 382/129, 382/130, 382/131, 382/132, 382/133, 382/134, 382/164, 382/171, 382/173, 382/177, 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/916, 128/920, 128/922
• 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 extreme to said edge point; and

labeling an unlabeled point if the unlabeled point is adjacent to a labeled point and the unlabeled paint has a more extreme intensity than the labeled point and the unlabeled point is closer than the labeled point to the local 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 extreme than the sum of a distance from the labeled point to the local 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 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 extreme and the ray point divided by the absolute value of a distance between the ray point and the local 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 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 extreme to said edge point;

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; 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 extreme than the sum of a distance from the labeled point to the local 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 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 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 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 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 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 extreme.

23. A method of labeling points of a multi-dimensional array so as to designate portions of the multi-dimensional array that are associated with an object, the method comprising:

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

determining that a second point that is distanced from the first point has a maximum edge metric, wherein the second point has an intensity that is smaller in magnitude than the intensity of the first point;

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

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

labeling the third point as belonging to the object.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

instructions for determining that a second point that is distanced from the first point has a maximum edge metric, wherein the second point has an intensity that is smaller in magnitude than the intensity of the first point;

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

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

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

38. The non-transitory computer-readable medium of claim 37, wherein the predetermined criterion comprises:

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

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

39. The non-transitory computer-readable medium of claim 37, wherein the predetermined criterion comprises:

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

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

40. A data processing apparatus 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; and

a processor configured to;

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

determine that a second point that is distanced from the first point has a maximum edge metric, wherein the second point has an intensity that is smaller in magnitude than the intensity of the first point;

label the second point as an edge point that lies on an edge of the object;

determine that a third point that is adjacent to the second point satisfies a predetermined criterion relative to one or more of the first and second points; and

label the third point as belonging to the object.

41. The data processing apparatus of claim 40, wherein the edge metric comprises a slope quotient that compares a difference between intensities of the first point and a point that is being evaluated to a distance between the first point and the point that is being evaluated.

42. The data processing apparatus of claim 40, wherein the predetermined criterion comprises the third point being disposed along a substantially straight line between the first and second points.