Image segmentation using isoperimetric trees

1. A computer readable medium embodying instructions executable by a processor to perform a method of graph partitioning comprising:

deriving a tree from input data; and

using the tree as a setting for use of a isoperimetric graph partitioning algorithm, wherein using the tree as the setting for use of the isoperimetric graph partitioning algorithm comprises:

producing a no-fill ordering of a matrix, the matrix representing the tree;

solving a system of linear equations with respect to the matrix, obtaining a solution;

using the solution to define a family of segmentations; and

selecting a segmentation from the family of segmentations based on a metric of segment quality.

2. The computer readable medium of claim 1 , wherein the tree is a distance tree.

3. The computer readable medium of claim 1 , wherein the tree is a function tree.

4. The computer readable medium of claim 3 , wherein the function is a function of interest, the function of interest defining what is important in the data.

5. A computer readable medium embodying instructions executable by a processor to perform a method of image segmentation comprising:

deriving a tree from input data;

producing a no-fill ordering of a matrix, the matrix representing the tree;

solving a system of linear equations with respect to the matrix, obtaining a solution;

using the solution to define a family of segmentations; and

selecting a segmentation from the family of segmentations based on a metric of segment quality.

6. The computer readable medium of claim 5 , wherein the input data comprises either pixels or voxels, and wherein a segmentation is specified by associating the pixels or voxels with either one of a foreground or a background.

7. The computer readable medium of claim 6 , wherein pixels with a solution value less than or equal to a threshold are associated with the foreground and pixels with a solution value greater than the threshold are associated with the background.

8. The computer readable medium of claim 7 , wherein there are n−1 thresholds, n being the number of pixels.

9. The computer readable medium of claim 5 , wherein the metric of segment quality is an isoperimetric ratio, the isoperimetric ratio being defined as the ratio of the perimeter of a node set to the volume of the node set.

10. The computer readable medium of claim 9 , wherein the volume of the node set is computed based on at least one of the sum of weighted degrees of the nodes in the set or the number of nodes in the set.

11. The computer readable medium of claim 5 , further comprising obtaining a foreground point, wherein obtaining a foreground point comprises either one of automatically obtaining a foreground point or interactively obtaining a foreground point.

12. The computer readable medium of claim 5 , wherein the tree is a distance tree.

13. The computer readable medium of claim 5 , wherein the tree is a function tree.

14. The computer readable medium of claim 13 , wherein the function is a function of interest, the function of interest defining what is important in an image.

15. The computer readable medium of claim 14 , wherein the function of interest is at least one of grayscale, gradient, or distance.

16. The computer readable medium of claim 5 , wherein the input data is a mask of pre-selected voxels.

17. The computer readable medium of claim 5 , wherein deriving a tree from input data comprises:

obtaining a mask from the input data;

computing a distance map on the mask; and

computing a distance tree.

18. The computer readable medium of claim 5 , wherein user interaction is not required.

19. A computer readable medium embodying instructions executable by a processor to perform a method of medical image segmentation comprising:

obtaining a mask from a medical image dataset;

computing a distance map on the mask;

obtaining a foreground point;

computing a maximal spanning tree with weights on a neighborhood structure of an image, the weights being a function of the distance map;

producing a no-fill ordering of a matrix, the matrix representing the maximal spanning tree;

solving a system of linear equations with respect to the matrix, obtaining a solution; using the solution to define a family of segmentations; and

selecting a segmentation from the family of segmentations based on a metric of segment quality.

20. The computer readable medium of claim 19 , wherein the image comprises pixels or voxels, and wherein a segmentation is specified by associating pixels or voxels with either one of a foreground or a background.

21. The computer readable medium of claim 20 , wherein pixels or voxels with a solution value less than or equal to a threshold are associated with the foreground and pixels or voxels with a solution value greater than the threshold are associated with a background.

22. The computer readable medium of claim 21 , wherein there are n−1 thresholds, n being the number of pixels.

23. The computer readable medium of claim 19 , wherein the metric of segment quality is an isoperimetric ratio, the isoperimetric ratio being defined as the ratio of the perimeter of a node set to the volume of the node set.

24. The computer readable medium of claim 23 wherein the volume of the node set is computed based on at least one of the sum of weighted degrees of the nodes in the set or the number of nodes in the set.

25. The computer readable medium of claim 19 , wherein the medical image dataset comprises at least one of 3D medical datasets, 2D medical datasets, or higher-dimensional medical datasets.

26. The computer readable medium of claim 19 , wherein the neighborhood structure is a lattice.

27. The computer readable medium of claim 19 , wherein obtaining a foreground point comprises obtaining a problem-specific foreground point.

28. The computer readable medium of claim 27 , wherein obtaining the problem-specific foreground point comprises obtaining a user-specified foreground point.

29. The computer readable medium of claim 19 , wherein user interaction is not required.

30. A system for performing a method of image segmentation comprising:

a computer readable medium including computer code for image segmentation

a processor in communication with the computer readable medium for executing the computer code of the computer readable medium, wherein the system performs the method of image segmentation comprising,

deriving a tree from input data;

producing a no-fill ordering of a matrix, the matrix representing the tree;

solving a system of linear equations with respect to the matrix, obtaining a solution;

using the solution to define a family of segmentations; and

selecting a segmentation from the family of segmentations based on a metric of segment quality.