Method and apparatus for detecting a desired behavior in digital image data

• US 5,661,820 A
• Filed: 04/13/1995
• Issued: 08/26/1997
• Est. Priority Date: 11/30/1992
• Status: Expired due to Fees

• Current Assignee: Kegelmeyer W. Philip Jr
• Original Assignee: Kegelmeyer W. Philip Jr
• Inventors: Kegelmeyer, W. Philip Jr.
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US08/421,603
• Time in Patent Office: 866 Days
• Field of Search: 382/224, 382/225, 382/226, 382/228, 382/128, 382/133, 382/131, 382/260, 382/199
• US Class Current: 382/226
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

Abstract

A method for detecting stellate lesions in digitized mammographic image data includes the steps of prestoring a plurality of reference images, calculating a plurality of features for each of the pixels of the reference images, and creating a binary decision tree from features of randomly sampled pixels from each of the reference images. Once the binary decision tree has been created, a plurality of features, preferably including an ALOE feature (analysis of local oriented edges), are calculated for each of the pixels of the digitized mammographic data. Each of these plurality of features of each pixel are input into the binary decision tree and a probability is determined, for each of the pixels, corresponding to the likelihood of the presence of a stellate lesion, to create a probability image. Finally, the probability image is spatially filtered to enforce local consensus among neighboring pixels and the spatially filtered image is output.

Claims

1. An apparatus for detecting a desired behavior within digital image data of a plurality of pixels, comprising:

storage means for prestoring a plurality of reference images;

calculating means for calculating a plurality of features for each of a plurality of pixels for each of the reference images;

computing means for creating a binary decision tree from calculated features of random samples of pixels from each of the reference images, said calculating means further calculating a plurality of features for each of the pixels of the digital image data;

input means for inputting each of the plurality of features of each pixel of the digital image data into the binary decision tree;

determining means for determining a probability, corresponding to the likelihood of a presence of the desired behavior, for each of the pixels of the digital image data based upon binary decision tree results to create a probability image;

filtering means for spatial filtering the probability image to enforce local consensus among neighboring pixels within the probability image; and

output means for outputting the spatially filtered image, wherein at least one of the plurality of features for each of the pixels of the digital image data is calculated by a calculating means including,

accessing means for accessing, for each of a plurality of pixels of the digital image data, digital image data of each pixel and pixels surrounding each of the plurality of pixels in predetermined window dimensions,

orientation means for computing edge orientation values of the accessed digital image data, for each of the plurality of pixels,

histogramming means for histogramming, for each of the plurality of pixels, the computed edge orientation values, and

computing means for computing a standard deviation of each histogram to create a feature for identifying a probable presence of the desired behavior in each of the plurality of pixels in which the standard deviation of the orientation histogram indicates a characteristic degree of orientation heterogeneity.

2. The apparatus of claim 1, wherein the filtering means comprises:

threshold means for thresholding each of the pixels of digital image data based upon each of the determined probabilities; and

median filtering means for median filtering windows of pixels, each of the pixels being included in at least one window and each of the windows being of a predetermined size so as to include a plurality of pixels.

3. The apparatus of claim 1, wherein the filtering means comprises:

mean filtering means for mean filtering windows of pixels, based upon each of the determined probabilities, each of the pixels being included in at least one window and each of the windows being of a predetermined size so as to include a plurality of pixels; and

thresholding means for thresholding each of the mean filtered pixels of digital image data to enforce the local consensus among neighboring pixels.

4. The apparatus of claim 1, wherein the output means includes a display for displaying the spacially filtered image.

5. The apparatus of claim 1, wherein the determining means determines a probability, for each of the pixels of the digital image data, corresponding to detection of an abnormality.

6. The apparatus of claim 1, wherein the computing means further computes classification probabilities for terminal nodes of the binary decision tree based upon input of the features of each pixel of the references images through the binary decision tree.

7. The apparatus of claim 1, wherein the digital image data is prestored data accessed by the accessing means.

8. The apparatus of claim 1, further comprising input means for inputting the digital image data for subsequent calculation by the calculating means.

9. The apparatus of claim 8, wherein the input means includes a keyboard.

10. The apparatus of claim 8, wherein the input means includes a scanner for scanning an object to create the digital image data.

11. The apparatus of claim 8, wherein the computing means further creates a feature for identifying a probable absence of the desired behavior in each of the plurality of pixels in which the standard deviation of the orientation histogram fails to indicate a characteristic degree of orientation heterogeneity.

12. The apparatus of claim 1, wherein the output means includes a display.

13. The apparatus of claim 1, wherein the output means includes a printer.

14. The apparatus of claim 3, wherein the desired behavior is an abnormality.

15. The apparatus of claim 14, wherein the abnormality is a stellate lesion and the digital image data is digitized mammographic image data.

16. The apparatus of claim 1, wherein the orientation means includes an edge operator to compute edge orientation values.

17. The apparatus of claim 16, wherein the edge operator is a Sobel edge operator which computes an arc-tangent of a ratio of vertical and horizontal derivatives.

18. The apparatus of claim 1, wherein at least one of the features calculated by the calculating means is a Laws texture feature.

19. The apparatus of claim 1, further comprising

sampling means for sampling, randomly, a plurality of pixels and for outputting the calculated features of the randomly sampled pixels to the computing means for creation of the binary decision tree.

20. The apparatus of claim 19, wherein at least one of the features calculated by the feature calculating means is a Laws texture feature.

21. A method for detecting a desired behavior within digital image data of a plurality of pixels, the method comprising the steps of:

(a) prestoring a plurality of reference images;

(b) calculating a plurality of features for each of a plurality of pixels for each of the reference images;

(c) creating a binary decision tree from calculated features of random samples of pixels from each of the reference images;

(d) calculating a plurality of features for each of the pixels of the digital image data;

(e) inputting each of the plurality of features of each pixel of digital image data into the binary decision tree;

(f) determining a probability, corresponding to the likelihood of a presence of the desired behavior, for each of the pixels of the digital image data based upon binary decision tree results to create a probability image;

(g) spatial filtering the probability image to enforce local consensus among neighboring pixels within the probability image; and

(h) outputting the spatially filtered image, wherein at least one of the plurality of features for each of the pixels of the digital image data is calculated, in at least one of steps (b) and (d), by the substeps of,

(i) accessing, for each of a plurality of pixels of the digital image data, digital image data of each pixel and pixels surrounding each of the plurality of pixels in predetermined window dimensions,

(ii) computing edge orientation values of the accessed digital image data, for each of the plurality of pixels,

(iii) histogramming, for each of the plurality of pixels, the computed edge orientation value, and

(iv) computing a standard deviation of each histogram to create a feature for identifying a probable presence of the desired behavior in each of the plurality of pixels in which the standard deviation of the orientation histogram indicates a characteristic degree of orientation heterogeneity.

22. The method of claim 21, wherein step (g) comprises the substeps of:

(i) thresholding each of the pixels of digital image data based upon each of the determined probabilities; and

(ii) median filtering windows of pixels, each of the pixels being included in at least one window and each of the windows being of a predetermined size so as to include a plurality of pixels.

23. The method of claim 21, wherein step (g) comprises the substeps of:

(i) mean filtering windows of pixels, based upon each of the determined probabilities, each of the pixels being included in at least one window and each of the windows being of a predetermined size so as to include a plurality of pixels; and

(ii) thresholding each of the mean filtered pixels of digital image data to enforce the local consensus among neighboring pixels.

24. The method of claim 21, wherein step (h) of outputting includes displaying the spacially filtered image.

25. The method of claim 21, wherein step (f) determines a probability, for each of the pixels of the digital image data, corresponding to detection of an abnormality.

26. The method of claim 21, further comprising the step of:

computing classification probabilities for terminal nodes of the created binary decision tree of step (c), based upon input of the features of each pixel of the reference images through the binary decision tree.

27. The method of claim 21, wherein the digital image data is accessed prestored data.

28. The method of claim 21, further comprising the substep of:

inputting the digital image data for subsequent calculation.

29. The method of claim 28, wherein the substep of inputting is done through a keyboard.

30. The method of claim 28, wherein the substep of inputting includes the further substep of scanning an object to create the digital image data.

31. The method of claim 28, wherein the computing step further creates a feature for identifying a probable absence of the desired behavior in each of the plurality of pixels in which the standard deviation of the orientation histogram fails to indicate a characteristic degree of orientation heterogeneity.

32. The method of claim 21, wherein the output step (h) includes displaying.

33. The method of claim 21, wherein the output step (h) includes printing.

34. The method of claim 21, wherein the desired behavior is an abnormality.

35. The method of claim 34, wherein the abnormality is a stellate lesion and the digital image data is digitized mammographic image data.

36. The method of claim 21, wherein the substep (ii) of at least one of steps (b) and (d) includes computing edge orientation values with an edge operator.

37. The method of claim 36, wherein the substep (ii) of at least one of steps (b) and (d) includes computing an arc-tangent of a ratio of vertical and horizontal derivatives with the edge operator which is a Sobel edge operator.

38. The method of claim 21, wherein at least one of the features calculated in at least one of steps (b) and (d) is a Laws texture feature.

39. The method of claim 21, further comprising the steps of:

sampling, randomly, a plurality of pixels of each of the reference images; and

outputting a plurality of features for each of the sampled pixels for creation of the binary decision tree in step (c).

40. The method of claim 39, wherein at least one of the features calculated in at least one of steps (b) and (d) is a Laws texture feature.

41. An apparatus for detecting a desired behavior within digital image data of a plurality of pixels, comprising:

storage means for prestoring a plurality of reference images;

calculating means for calculating a plurality of features for each of a plurality of pixels for each of the reference images;

computing means for creating a binary decision tree from calculated features of random samples of pixels from each of the reference images, said calculating means further calculating a plurality of features for each of the pixels of the digital image data;

input means for inputting each of the plurality of features of each pixel of the digital image data into the binary decision tree;

determining means for determining a probability, corresponding to the likelihood of a presence of the desired behavior, for each of the pixels of the digital image data based upon binary decision tree results, to create a probability image;

filtering means for spatial filtering the probability image to enforce local consensus among neighboring pixels within the probability image; and

output means for outputting the spatially filtered image, wherein at least one of the plurality of features for each of the pixels of the digital image data is calculated by a calculating means including,

accessing means for accessing, for each of a plurality of pixels of the digital image data, digital image data of each pixel and pixels surrounding each of the plurality of pixels in predetermined window dimensions,

orientation means for computing edge orientation values of the accessed digital image data, for each of the plurality of pixels,

histogramming means for histogramming, for each of the plurality of pixels, the computed edge orientation values, and

detecting means for detecting a probable presence of the desired behavior in each of the plurality of pixels for which the orientation histogram indicates a characteristic degree of orientation heterogeneity.

42. The apparatus of claim 41, wherein the detecting means further is for detecting an absence of the desired behavior in each of the plurality of pixels for which the orientation histogram fails to indicate a characteristic degree of orientation heterogeneity.

43. The apparatus of claim 42, further comprising:

indicating means for indicating, for each of the plurality of pixels, the detected probable presence or absence of the desired behavior.

44. A method for detecting a desired behavior within digital image data of a plurality of pixels, the method comprising the steps of:

(a) prestoring a plurality of reference images;

(b) calculating a plurality of features for each of a plurality of pixels for each of the reference images;

(c) creating a binary decision tree from calculated features of random samples of pixels of each of the reference images;

(d) calculating a plurality of features for each of the pixels of the digital image data;

(e) inputting each of the plurality of features of each pixel of digital image data into the binary decision tree;

(f) determining a probability, corresponding to the likelihood of a presence of the desired behavior, for each of the pixels of the digital image data based upon binary decision tree results to create a probability image;

(g) spatial filtering the probability image to enforce local consensus among neighboring pixels within the probability image; and

(h) outputting the spatially filtered image, wherein at least one of the plurality of features for each of the pixels of the digital image data is calculated, in at least one of steps (b) and (d), by the substeps of,

(i) accessing, for each of a plurality of pixels of the digital image data, digital image data of each pixel and pixels surrounding each of the plurality of pixels in predetermined window dimensions,

(ii) computing edge orientation values of the accessed digital image data, for each of the plurality of pixels,

(iii) histogramming, for each of the plurality of pixels, the computed edge orientation values; and

(iv) detecting a probable presence of the desired behavior in each of the plurality of pixels for which the orientation histogram indicates a characteristic degree of orientation heterogeneity.

45. The method of claim 44, wherein the identifying substep step (iv) further includes detecting an absence of the desired behavior in each of the plurality of pixels for which the orientation histogram fails to indicate a characteristic degree of orientation heterogeneity.

46. The method of claim 44, further comprising the substep of:

(v) indicating, for each of the plurality of pixels, the detected probable presence or absence of the desired behavior.