AUTOMATIC IMAGE SEGMENTATION USING CONTOUR PROPAGATION

• US 20090324078A1
• Filed: 06/27/2008
• Published: 12/31/2009
• Est. Priority Date: 06/27/2008
• Status: Active Grant

• Current Assignee: MAKO Surgical Corporation (Stryker Corporation)
• Original Assignee: MAKO Surgical Corporation (Stryker Corporation)
• Inventors: Wu, Min, Arata, Louis K.
• Granted Patent: US 8,249,345 B2
• Time in Patent Office: Days
• US Class Current: 382/173
• CPC Class Codes: G06T 2207/10072 Tomographic images
• CPC Class Codes: G06T 2207/30004 Biomedical image processing
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/149 involving deformable models, e.g. active contour models

Abstract

Described are computer-based methods and apparatuses, including computer program products, for automatic image segmentation using contour propagation. A path metric of a candidate piece of a contour in a cross-sectional image is calculated to generate a three dimensional model using a plurality of cross-sectional images of an object. Data indicative of the cross-sectional image is stored. A cost of each of a plurality of pixels associated with the candidate piece is calculated using the data, wherein the cost is representative of a likelihood the pixel is on the contour and the cost is based on one or more templates. An orientation change value is calculated for each of the plurality of pixels associated with the candidate piece based on an initial pixel of the candidate piece and the pixel. A ratio of pixels is calculated. The path metric of the candidate piece of the contour is stored, the value of the stored path metric being based on the calculated cost, the calculated orientation change value, and the calculated ratio.

Claims

1. A computerized method for calculating a path metric of a candidate piece of a contour in a cross-sectional image to generate a three dimensional model using a plurality of cross-sectional images of an object, the method comprising:

storing data indicative of the cross-sectional image;

calculating a cost of each of a plurality of pixels associated with the candidate piece using the data, wherein the cost is representative of a likelihood the pixel is on the contour and the cost is based on one or more templates;

calculating an orientation change value for each of the plurality of pixels associated with the candidate piece based on an initial pixel of the candidate piece and the pixel;

calculating a ratio of pixels; and

storing the path metric of the candidate piece of the contour, the value of the stored path metric being based on the calculated cost, the calculated orientation change value, and the calculated ratio.

2. The method of claim 1, further comprising calculating the path metric based on a summation of the calculated cost, the calculated orientation change value, the calculated ratio, or any combination thereof.

3. The method of claim 1, wherein calculating the cost of each pixel comprises, for each template of the one or more templates, calculating a template value by weighting the pixel and a plurality of neighboring pixels.

4. The method of claim 3, wherein the weight of each template pixel, the weight of the pixel, the weight of the plurality of neighboring pixels, or any combination thereof comprises minus one, zero, or one.

5. The method of claim 3, wherein the cost for the pixel is the highest template value associated with one of the one or more templates.

6. The method of claim 1, wherein calculating the orientation change value is based on an angular change factor.

7. The method of claim 6, wherein determining the angular change factor comprises:

determining an orientation change between the initial pixel and the pixel is less than ninety degrees and assigning the orientation change value one;

determining the orientation change between the initial pixel and the pixel is greater than or equal to ninety degrees but less than one hundred and thirty-five degrees and assigning the orientation change value of zero;

or

determining the orientation change between the initial pixel and the pixel is greater than or equal to one hundred and thirty-five degrees and assigning the orientation change value of negative one.

8. The method of claim 1, further comprising calculating a second ratio of one minus the first ratio over one plus the first ratio.

9. The method of claim 1, further comprising determining whether each pixel of the plurality of pixels is an edge point based on an intensity value.

10. The method of claim 1, wherein calculating a ratio of pixels further comprises calculating a ratio of pixels using a number of non-edge pixels over a total number of the plurality of pixels.

11. A computerized method for calculating an optimal candidate piece of a contour in a cross-sectional image to generate a three dimensional model using a plurality of cross-sectional images of an object, the method comprising:

receiving data indicative of a first cross-sectional image and a second cross-sectional image adjacent to the first cross-sectional image, the first cross-sectional image and second cross-sectional image being in the plurality of cross-sectional images;

using the data, calculating a plurality of paths between a first point and a second point in the second cross-sectional image based on a lowest cost function;

calculating a path metric for each path in the plurality of paths based on a path metric function, the path metric function being different from the lowest cost function;

determining the optimal candidate piece from the plurality of paths, the optimal candidate path having a highest path metric among the plurality of paths; and

storing data indicative of the optimal candidate piece of the contour.

12. The method of claim 11, wherein the data is indicative of a plurality of edge points for the first cross-sectional image.

13. The method of claim 12, further comprising calculating the first point of the second cross-sectional image based on a first edge point for the first cross-sectional image from the plurality of edge points for the first cross-sectional image.

14. The method of claim 12, further comprising determining the second point of the second cross-sectional image based on a second edge point from the plurality of edge points for the first cross-sectional image.

15. The method of claim 11, wherein each path in the plurality of paths extends from the first point to a third point, the third point being based on the first point and the second point.

16. The method of claim 11, wherein the first point is based on a line from a centroid of a second contour on the second cross-sectional image.

17. The method of claim 11, wherein the first point corresponds to a point with a maximal edge cost.

18. The method of claim 11, wherein the path metric for each path is based on an edge cost function, an orientation change, and a number of pixels of the respective path not on the contour.

19. The method of claim 18, wherein the edge cost function is based on a weighting for each pixel of a plurality of pixels for each respective path for each template of one or more templates.

20. The method of claim 18, wherein the orientation change is based on an angular change factor.

21. A system for calculating a path metric of a candidate piece of a contour in a cross-sectional image to generate a three dimensional model using a plurality of cross-sectional images of an object, the system comprising:

a processor configured to;

calculate a cost of each of a plurality of pixels associated with the candidate piece using data indicative of the cross-sectional image, wherein the cost is representative of a likelihood the pixel is on the contour and is based on one or more templates;

calculate an orientation change value for each of the plurality of pixels associated with the candidate piece based on an initial pixel of the candidate piece and the pixel; and

calculate a ratio of pixels; and

a storage device configured to;

store the data; and

store the path metric of the candidate piece of the contour, the value of the stored path metric being based on the calculated cost, the calculated orientation change value, and the calculated ratio.

22. A system for calculating an optimal candidate piece of a contour in a cross-sectional image to generate a three dimensional model using a plurality of cross-sectional images of an object, the system comprising:

a storage device configured to receive data indicative of a first cross-sectional image and a second cross-sectional image adjacent to the first cross-sectional image, the first cross-sectional image and second cross-sectional image being in the plurality of cross-sectional images; and

store data indicative of the optimal candidate piece of the contour; and

a processor configured to;

using the data, calculate a plurality of paths between a first point and a second point in the second cross-sectional image based on a lowest cost function;

calculate a path metric for each path in the plurality of paths based on a path metric function, the path metric function being different from the lowest cost function;

determine the an optimal candidate piece from the plurality of paths, the optimal candidate path having a highest path metric among the plurality of paths.

23. A computer program product, tangibly embodied in a computer readable medium for calculating a path metric of a candidate piece of a contour in a cross-sectional image to generate a three dimensional model using a plurality of cross-sectional images of an object, the computer program product including instructions being operable to cause a data processing apparatus to:

store data indicative of the cross-sectional image;

calculate a cost of each of a plurality of pixels associated with the candidate piece using the data, wherein the cost is representative of a likelihood the pixel is on the contour and the cost is based on one or more templates;

calculate an orientation change value for each of the plurality of pixels associated with the candidate piece based on an initial pixel of the candidate piece and the pixel;

calculate a ratio of pixels; and

store the path metric of the candidate piece of the contour, the value of the stored path metric being based on the calculated cost, the calculated orientation change value, and the calculated ratio.

24. A computer program product, tangibly embodied in a computer readable medium for calculating an optimal candidate piece of a contour in a cross-sectional image to generate a three dimensional model using a plurality of cross-sectional images of an object, the computer program product including instructions being operable to cause a data processing apparatus to:

receive data indicative of a first cross-sectional image and a second cross-sectional image adjacent to the first cross-sectional image, the first cross-sectional image and second cross-sectional image being in the plurality of cross-sectional images;

using the data, calculate a plurality of paths between a first point and a second point in the second cross-sectional image based on a lowest cost function;

calculate a path metric for each path in the plurality of paths based on a path metric function, the path metric function being different from the lowest cost function;

determine the optimal candidate piece from the plurality of paths, the optimal candidate path having a highest path metric among the plurality of paths; and

store data indicative of the optimal candidate piece of the contour.

25. A system for calculating a path metric of a candidate piece of a contour in a cross-sectional image to generate a three dimensional model using a plurality of cross-sectional images of an object, the system comprising:

means for storing data indicative of the cross-sectional image;

means for calculating a cost of each of a plurality of pixels associated with the candidate piece using the data, wherein the cost is representative of a likelihood the pixel is on the contour and the cost is based on one or more templates;

means for calculating an orientation change value for each of the plurality of pixels associated with the candidate piece based on an initial pixel of the candidate piece and the pixel;

means for calculating a ratio of pixels; and

means for storing the path metric of the candidate piece of the contour, the value of the stored path metric being based on the calculated cost, the calculated orientation change value, and the calculated ratio.

26. A system for calculating an optimal candidate piece of a contour in a cross-sectional image to generate a three dimensional model using a plurality of cross-sectional images of an object, the system comprising:

means for receiving data indicative of a first cross-sectional image and a second cross-sectional image adjacent to the first cross-sectional image, the first cross-sectional image and second cross-sectional image being in the plurality of cross-sectional images;

means for, using the data, calculating a plurality of paths between a first point and a second point in the second cross-sectional image based on a lowest cost function;

means for calculating a path metric for each path in the plurality of paths based on a path metric function, the path metric function being different from the lowest cost function;

means for determining the optimal candidate piece from the plurality of paths, the optimal candidate path having a highest path metric among the plurality of paths; and

means for storing data indicative of the optimal candidate piece of the contour.