Method and apparatus for image segmentation using Jensen-Shannon divergence and Jensen-Renyi divergence

• US 20040022438A1
• Filed: 08/02/2002
• Published: 02/05/2004
• Est. Priority Date: 08/02/2002
• Status: Active Grant

• Current Assignee: IMPAC Medical Systems, Inc. (Elekta AB)
• Original Assignee: Computerized Medical Systems, Inc. (Elekta AB)
• Inventors: Hibbard, Lyndon S.
• Granted Patent: US 7,187,800 B2
• Time in Patent Office: Days
• US Class Current: 382/199
• CPC Class Codes: G06T 2207/10081 Computed x-ray tomography [CT]
• CPC Class Codes: G06T 2207/30004 Biomedical image processing
• CPC Class Codes: G06T 7/0012 Biomedical image inspection
• CPC Class Codes: G06T 7/12 Edge-based segmentation

Abstract

A method of approximating the boundary of an object in an image, the image being represented by a data set, the data set comprising a plurality of data elements, each data element having a data value corresponding to a feature of the image, the method comprising determining which one of a plurality of contours most closely matches the object boundary at least partially according to a divergence value for each contour, the divergence value being selected from the group consisting of Jensen-Shannon divergence and Jensen-Renyi divergence. Each contour Cⁱ defines a zone Z_Iⁱ and a zone Z_Oⁱ, Z_Iⁱ representing the data elements inside the contour and Z_Oⁱ representing the data elements outside the contour, each zone having a corresponding probability distribution of data values for the data elements therein, and wherein the divergence value for each contour Cⁱ represents a measure of the difference between the probability distributions for the zones Z_Iⁱ and Z_Oⁱ. The boundary estimate is preferably a parametric contour. Further, the present invention supports the segmentation of multiple objects in a single data set simultaneously.

Claims

1. A method of identifying the boundary of an object in an image, the image being represented by a data set, the data set comprising a plurality of data elements, each data element having a data value corresponding to a feature of at least part of the image, the method comprising;

adjusting a boundary estimate at least partially according to one of the group consisting of a Jensen-Shannon divergence value corresponding to the boundary estimate and a Jensen-Renyi divergence value corresponding to the boundary estimate such that the boundary estimate substantially matches the object boundary.

2. The method of claim 1 wherein the divergence value represents a measure of the difference between the data values of the data elements located in a zone Z, and the data values of the data elements located in a zone Z_O, Z_I and Z_O being defined by the boundary estimate and representing, respectively, the data elements of the image located inside and outside the boundary estimate.

3. The method of claim 2 wherein each data value is any member of the data value set X′

, X′

comprising a plurality of possible data values x₁ through x_n, and wherein each data value x_i is the value of a random variable X drawn from X′

according to a probability law p(x_i)=Pr{X=x_i}, each zone having a corresponding probability law such that the probability of observing X with the specific value x_i in zone Z₀ is the conditional probability p(x_i|Z₀) and the probability of observing X with the specific value x_i in zone Z_I is the conditional probability p(x_i|Z_I), and wherein the divergence value represents a measure of the difference between a conditional probability distribution p(X|Z_I) and a conditional probability distribution p(X|Z_O).

4. The method of claim 3 wherein X′

comprises a finite plurality of possible data values.

5. The method of claim 3 wherein the boundary estimate is a contour C.

6. The method of claim 5 further comprising:

determining a contour that represents an approximation of the object boundary;

calculating one of the group consisting of the Jensen-Shannon divergence value and the Jensen-Renyi divergence for the contour; and

wherein the adjusting step comprises adjusting the approximate contour so as to increase its corresponding calculated divergence value.

7. The method of claim 6 further comprising:

receiving input from a user or from a programmed method corresponding to a polygon that represents an initial estimate of the object boundary;

mapping the received input to the image data set to thereby determine a pixel boundary corresponding to the polygon; and

wherein the approximate contour determining step comprises calculating the approximate contour from the determined pixel boundary.

8. The method of claim 6 wherein the divergence value calculating step comprises:

identifying which data elements are located in Z_I;

identifying which data elements are located in Z_O;

calculating the conditional probability distribution p(X|Z_I);

calculating the conditional probability distribution p(X|Z_O); and

calculating the divergence value between p(X|Z_I) and p(X|Z_O).

9. The method of claim 6 wherein the adjusting step further comprises adjusting the approximate contour so as to substantially maximize its calculated divergence value.

10. The method of claim 9 wherein each contour is a parametric contour C defined by functions of a plurality N of ordered contour coefficients c₁ through C_N, each contour coefficient c_i having a numeric value, and wherein the adjusting step further comprises adjusting the numeric value of at least one contour coefficient c_i.

11. The method of claim 10 wherein the adjusting step further comprises determining a numeric value for c_i of the approximate contour for which the divergence value of the approximate contour is substantially maximum.

12. The method of claim 11 wherein the adjusting step comprises performing the numeric value determining step for c_i before performing a numeric value determining step for c_i+1.

13. The method of claim 10 wherein the adjusting step further comprises individually adjusting the numeric values of at least a plurality of approximate contour coefficients starting from c₁ and continuing through successively higher order approximate contour coefficients until the approximate contour'"'"'s divergence value is substantially maximized.

14. The method of claim 13 wherein the individually adjusting step comprises individually adjusting the numeric values of each approximate contour coefficient starting from c₁ and continuing through successively higher order approximate contour coefficients to c_N until the approximate contour'"'"'s divergence value is substantially maximized.

15. The method of claim 13 wherein the coefficients correspond to the terms of a finite-length trigonometric series, wherein the number N of the contour coefficients is 4K+2, and wherein K is a programmably-determined number of harmonics of the trigonometric series.

16. The method of claim 2 wherein the divergence value is a Jensen-Shannon divergence value.

17. The method of claim 2 wherein the divergence value is a Jensen-Renyi divergence value.

18. The method of claim 2 wherein the image is a medical image of an interior portion of a body, wherein the data set comprises a plurality of pixels, each pixel having a pixel value corresponding to image intensity.

19. The method of claim 18 wherein the medical image is an X-ray computed tomography (CT) image.

20. The method of claim 18 wherein the medical image is an X-ray image.

21. The method of claim 18 wherein the medical image is a magnetic resonance image.

22. The method of claim 2 wherein the image comprises a plurality of objects, each object having a boundary, the method further comprising performing the adjusting step simultaneously for at least two of the image objects.

23. The method of claim 2 wherein the data set is a two-dimensional data set.

24. The method of claim 2 wherein each data element has a plurality of data values corresponding to different features of at least part of the image.

25. The method of claim 24 wherein the data values for each data element are conditionally dependent.

26. The method of claim 24 wherein the data values for each data element are mutually independent.

27. An apparatus for identifying the boundary of an object in an image, the image being represented by a data set, the data set comprising a plurality of data elements, each data element having a data value corresponding to a feature of at least part of the image, the apparatus comprising;

a processor configured to adjust a boundary estimate at least partially according to one of the group consisting of a Jensen-Shannon divergence value corresponding to the boundary estimate and a Jensen-Renyi divergence value corresponding to the boundary estimate such that the boundary estimate substantially matches the object boundary.

28. The apparatus of claim 27 wherein the divergence value represents a measure of the difference between the data values of the data elements located in a zone Z, and the data values of the data elements located in a zone Z_O, Z_I and Z_O being defined by the boundary estimate and representing, respectively, the data elements of the image located inside and outside the boundary estimate.

29. The apparatus of claim 28 wherein each data value is any member of the data value set X′

, X′

comprising a plurality of possible data values x_i through x_n, and wherein each data value x_i is the value of a random variable X drawn from X′

according to a probability law p(x_i)=Pr{X=x_i}, each zone having a corresponding probability law such that the probability of observing X with the specific value x_i in zone Z_O is the conditional probability p(x_i|Z_O) and the probability of observing X with the specific value x_i in zone Z_I is the conditional probability p(x_i|Z_I), and wherein the divergence value represents a measure of the difference between a conditional probability distribution p(X|Z_I) and a conditional probability distribution p(X|Z_O).

30. The apparatus of claim 29 wherein X′

comprises a finite plurality of possible data values.

31. The apparatus of claim 29 wherein the boundary estimate is a contour C.

32. The apparatus of claim 31 wherein the processor is further configured to:

determine a contour that represents an approximation of the object boundary;

calculate one of the group consisting of the Jensen-Shannon divergence value and the Jensen-Renyi divergence for the contour; and

adjust the approximate contour so as to increase its corresponding calculated divergence value.

33. The apparatus of claim 32 wherein the processor is further configured to:

receive input from a user or from a programmed method corresponding to a polygon that represents an initial estimate of the object boundary;

map the received input to the image data set to thereby determine a pixel boundary corresponding to the polygon; and

determine the approximate contour by calculating the approximate contour from the determined pixel boundary.

34. The apparatus of claim 32 wherein the processor is configured to calculate the divergence value by:

identifying which data elements are located in Z_I;

identifying which data elements are located in Z_O;

calculating the conditional probability distribution p(X|Z_I);

calculating the conditional probability distribution p(X|Z_O); and

calculating the divergence value between p(X|Z_I) and p(X|Z_O).

35. The apparatus of claim 32 wherein the processor is further configured to adjust the approximate contour so as to substantially maximize its calculated divergence value.

36. The apparatus of claim 35 wherein each contour is a parametric contour C defined by functions of a plurality N of ordered contour coefficients c₁ through c_N, each contour coefficient c_i having a numeric value, and wherein the processor is further configured to adjust the approximate contour by adjusting the numeric value of at least one contour coefficient c_i.

37. The apparatus of claim 36 wherein the processor is further configured to adjust the approximate contour by determining a numeric value for c₁ of the approximate contour for which the divergence value of the approximate contour is substantially maximum.

38. The apparatus of claim 37 wherein the processor is further configured to adjust the approximate contour by performing the numeric value determining step for c_i before performing a numeric value determining step for c_i+1.

39. The apparatus of claim 36 wherein the processor is further configured to adjust the approximate contour by individually adjusting the numeric values of at least a plurality of approximate contour coefficients starting from c₁ and continuing through successively higher order approximate contour coefficients until the approximate contour'"'"'s divergence value is substantially maximized.

40. The apparatus of claim 39 wherein the processor is further configured to adjust the approximate contour by individually adjusting the numeric values of each approximate contour coefficient starting from c₁ and continuing through successively higher order approximate contour coefficients to C_N until the approximate contour'"'"'s divergence value is substantially maximized.

41. The apparatus of claim 39 wherein the coefficients correspond to the terms of a finite-length trigonometric series, wherein the number N of the contour coefficients is 4K+2 and wherein K is a programmably-determined number of harmonics of the trigonometric series.

42. The apparatus of claim 28 wherein the divergence value is a Jensen-Shannon divergence value.

43. The apparatus of claim 28 wherein the divergence value is a Jensen-Renyi divergence value.

44. The apparatus of claim 28 wherein the image is a medical image of an interior portion of a body, wherein the data set comprises a plurality of pixels, each pixel having a pixel value corresponding to image intensity.

45. The apparatus of claim 44 wherein the medical image is a computed tomography (CT) image.

46. The apparatus of claim 44 wherein the medical image is an X-ray image.

47. The method of claim 44 wherein the medical image is a magnetic resonance image.

48. The apparatus of claim 28 wherein the image comprises a plurality of objects, each object having a boundary, and wherein the processor is further configured to perform the contour adjustment simultaneously for at least two of the image objects.

49. The apparatus of claim 28 wherein the data set is a two-dimensional data set.

50. The apparatus of claim 28 wherein each data element has a plurality of data values corresponding to different features of at least part of the image.

51. The apparatus of claim 50 wherein the data values for each data element are conditionally dependent.

52. The apparatus of claim 50 wherein the data values for each data element are mutually independent.

53. The apparatus of claim 28 wherein the processor is a workstation.

54. The apparatus of claim 28 wherein the processor is a digital signal processor (DSP).

55. The apparatus of claim 28 wherein the processor is an application-specific integrated circuit (ASIC).

56. The apparatus of claim 28 wherein the processor is a multi-processor computer.

57. The apparatus of claim 28 further comprising a medical imaging device in communication with the processor for generating the data set.

58. A method of approximating the boundary of an object in an image, the image being represented by a data set, the data set comprising a plurality of data elements, each data element having a data value corresponding to a feature of at least part of the image, the method comprising:

determining which one of a plurality of contours most closely matches the object boundary at least partially according to a divergence value for each contour, the divergence value being selected from the group consisting of Jensen-Shannon divergence and Jensen-Renyi divergence.

59. The method of claim 58 wherein each contour C′

defines a zone Z₁ⁱ and a zone Z_O^I, Z_Iⁱ representing the data elements inside the contour and Z_Oⁱ representing the data elements outside the contour, each zone having a corresponding probability distribution of data values for the data elements therein, and wherein the divergence value for each contour Cⁱ represents a measure of the difference between the probability distributions for the zones Z_Iⁱ and Z_oⁱ.

60. The method of claim 59 wherein each data value is any member of the data value set X′

, X′

comprising a plurality of possible data values x₁ through x_n, and wherein each data value is the value of a random variable X drawn from X′

according to a probability law p(x_i)=Pr{X=x_i}, each zone having a corresponding probability law such that the probability of observing X with the specific value x_i in zone Z₀ is the conditional probability p(x_i|Z₀) and the probability of observing X with the specific value x_i in the zone Z_I is the conditional probability p(x_i|Z_I), the method further comprising;

determining a first contour C¹;

calculating a conditional probability distribution p(X|Z_I¹);

calculating a conditional probability distribution p(X|Z_O^I);

calculating the difference between p(X|Z_I¹) and p(X|Z_O¹) according one of the group consisting of the Jensen-Shannon divergence and the Jensen-Renyi divergence;

determining a second contour C²;

calculating a conditional probability distribution p(X|Z_I²);

calculating a conditional probability distribution p(X|Z_O²);

calculating the difference between p(X|Z_I²) and p(X|Z_O²);

according to the one of the group consisting of Jensen-Shannon divergence and Jensen-Renyi divergence that was selected in the first difference calculating step; and

wherein the match determining step comprises selecting the contour, C¹ or C², having a larger divergence value as the contour that most closely matches the object boundary.

61. The method of claim 60 wherein each contour Cⁱ is defined by a plurality N of ordered contour coefficients c₁ⁱ through c_Nⁱ, each contour coefficient having a numeric value, and wherein the C² determining step comprises creating C² from C¹ by adjusting the numeric value of a C¹ contour coefficient.

62. The method of claim 61 wherein the C² determining step comprises creating C² from C¹ by adjusting the numeric value of each C¹ contour coefficient such that the divergence value of C² is greater than the divergence value for C¹.

63. The method of claim 62 further comprising repetitively performing the method steps until the difference between divergence values for

C¹ and C² is less than a programmably-defined threshold, and

wherein C² becomes C¹ on each new iteration of the method steps.

64. The method of claim 63 wherein, on a first iteration of the method steps, the C¹ determining step comprises creating C¹ from a user-specified pixel boundary.

65. The method of claim 63 wherein, on a first iteration of the method steps, the C¹ determining step comprises creating C¹ from a programmably-defined pixel boundary.

66. The method of claim 59 wherein the image is a medical image of an interior portion of the body.

67. The method of claim 59 wherein each difference calculating step comprises calculating the Jensen-Shannon divergence value.

68. The method of claim 59 wherein each difference calculating step comprises calculating the Jensen-Renyi divergence value.

69. The method of claim 59 wherein each data element has a plurality of data values corresponding to different features of the image.

70. The method of claim 69 wherein the data values for each data element are conditionally dependent.

71. The method of claim 69 wherein the data values for each data element are mutually independent.

72. A method of segmenting an object from its background in an image, the image being represented by a data set, the data set comprising a plurality of data elements, each data element having a data value corresponding to a feature of at least part of the image, the method comprising:

associating the data elements of the data set with either a zone Z_I or a zone Z_O, Z_I being an estimation of the object in the image, Z_O being an estimation of the background in the image; and

adjusting Z_I and Z_O at least partially according to one of the group consisting of a Jensen-Shannon divergence value and a Jensen-Renyi divergence value such that Z_I substantially matches the object.

73. The method of claim 72 wherein the divergence value is a measure of the divergence between a probability distribution of the data values of the data elements associated with Z_I and a probability distribution of the data values of the data elements associated with Z_O.

74. The method of claim 73 wherein each data value is any member of a data value set X′

, X′

comprising a plurality of possible data values x₁ through x₀, and wherein each data value x_i is the value of a random variable X drawn from X′

according to a probability law p(x_i)=Pr{X=x_i}, each zone having a corresponding probability law such that the probability of observing X with the specific value x_i in zone Z₀ is the conditional probability p(X_i|Z₀) and the probability of observing X with the specific value x_i in zone Z_I is the conditional probability p(x_i|Z_I), and wherein the method further comprises;

calculating a conditional probability distribution p(X|Z_I);

calculating a conditional probability distribution p(X|Z_O);

calculating the divergence value as the divergence between P(X|Z_I) and p(X|Z_O).

75. The method of claim 74 wherein the adjusting step comprising adjusting Z_I and Z_O such that the calculated divergence value is substantially maximum.

76. The method of claim 75 further comprising:

determining a boundary estimate, the boundary estimate defining Z_I and Z_O;

and wherein the adjusting step comprises adjusting the boundary estimate.

77. The method of claim 76 wherein the boundary estimate is a parametric contour C comprising a plurality N of ordered contour coefficients c₁ through C_N, each contour coefficient having a numerical value, and wherein the adjusting step comprises adjusting the contour coefficients so as to maximize the divergence value for C.

78. The method of claim 77 wherein the adjusting step comprises first adjusting only contour coefficient c₁ until the calculated divergence value for the adjusted contour is substantially maximum.

79. The method of claim 78 wherein the adjusting step further comprises next adjusting only contour coefficient c₂ until the calculated divergence value for the adjusted contour is substantially maximum.

80. The method of claim 79 wherein the adjusting step further comprises performing the contour coefficient adjusting step for successively higher ordered contour coefficients until the calculated divergence value does not differ from a previous calculated divergence value by more that a predetermined threshold value.

81. The method of claim 73 wherein the divergence value is the Jensen-Shannon divergence value.

82. The method of claim 73 wherein the divergence value is the Jensen-Renyi divergence value.

83. The method of claim 73 wherein the image is a medical image.

84. A method of segmenting an object in an image through optimization of a segmentation estimate, the image being represented by a data set, the data set comprising a plurality of pixels, each pixel having a value corresponding to a feature of at least part of the image, each pixel value being any member of the pixel value set X′

, X′

comprising a plurality of possible pixel values x₁ through x_n, the segmentation estimate defining a zone Z_I representing a set of pixels corresponding to the object and a zone Z_O representing a set of pixels not corresponding to the object, wherein a plurality of pixels are located in Z_I and a plurality of pixels are located in Z_O, the method comprising using one of the group consisting of (1) a Jensen-Shannon divergence value representing the difference between a probability distribution p(X|Z_I) and a probability distribution p(X|Z_O) and (2) a Jensen-Renyi divergence value representing the difference between a probability distribution p(X|Z_I) and a probability distribution p(X|Z_O) as a criterion for optimizing the segmentation estimate to substantially match the object boundary.

85. The method of claim 84 wherein the divergence value criterion is the Jensen-Shannon divergence value.

86. The method of claim 84 wherein the divergence value criterion is the Jensen-Renyi divergence value.

87. The method of claim 84 wherein the image is a medical image of an interior portion of the body.

88. The method of claim 84 wherein the segmentation estimate corresponds to a contour C that represents an approximation of the object boundary.

89. A combination region-based and edge-based method of approximating the boundary of an object in an image, the image being represented by a data set, the data set comprising a plurality of pixels, each pixel having a pixel value corresponding to a feature of the image, each pixel value being any member of a pixel value set X′

, X′

comprising a finite plurality of possible pixel values, the method comprising;

maximizing one of the group consisting of a total Jensen-Shannon divergence corresponding to a boundary estimate and a total Jensen-Renyi divergence value corresponding to a boundary estimate, wherein the total divergence value represents both a regional divergence value and an edge divergence value, wherein the total divergence value is a sum of the regional divergence value multiplied by a regional weight and the edge divergence value multiplied by an edge weight, and wherein the boundary estimate for which the total divergence value is maximized represents a matching boundary.