Method and apparatus for segmenting an image in order to locate a part thereof

• US 20050134587A1
• Filed: 01/14/2005
• Published: 06/23/2005
• Est. Priority Date: 09/23/1999
• Status: Active Grant

• Current Assignee: New York University
• Original Assignee: New York University
• Inventors: Ishikawa, Hiroshi, Geiger, Davi
• Granted Patent: US 7,893,939 B2
• Time in Patent Office: Days
• US Class Current: 345/423
• CPC Class Codes: G06F 18/2323 based on graph theory, e.g. minimum spanning trees [MST] or graph cuts
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 2200/04 involving 3D image data
• CPC Class Codes: G06T 2207/10072 Tomographic images
• CPC Class Codes: G06T 2207/20072 Graph-based image processing
• CPC Class Codes: G06T 2207/30004 Biomedical image processing
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/162 involving graph-based methods
• CPC Class Codes: G06V 10/267 by performing operations on regions, e.g. growing, shrinking or watersheds
• CPC Class Codes: G06V 10/7635 based on graphs, e.g. graph cuts or spectral clustering

Abstract

A method is disclosed to automatically segment 3D and higher-dimensional images into two subsets without user intervention, with no topological restriction on the solution, and in such a way that the solution is an optimal in a precisely defined optimization criterion, including an exactly defined degree of smoothness. A minimum-cut algorithm is used on a graph devised so that the optimization criterion translates into the minimization of the graph cut. The minimum cut thus found is interpreted as the segmentation with desired property

Claims

1-14. -14. (canceled)

15. A method for associating particular data in a three-dimensional space, comprising the steps of:

receiving first data corresponding to at least one first point in the three-dimensional space, the first data for each one of the at least one first point including first information indicative of a likelihood of an association of the first data with at least a first part of the respective first point;

receiving second data corresponding to at least one second point in the three-dimensional space, the second data for each one of the at least one second point including second information indicative of a likelihood of an association of the second data with at least a second part of the respective second point; and

associating the first and second points to the respective first and second parts based on the first and second information.

16. The method of claim 15, wherein the first data corresponds to the a first voxel.

17. The method of claim 15, wherein the first information includes first weights, and wherein the second information includes second weights.

18. The method of claim 17, wherein the first point is associated with the first part if the first weight indicates a higher likelihood for such association.

19. The method of claim 17, wherein the second point is associated with the second part if the second weight indicates a higher likelihood for such association.

20. The method of claim 15, wherein a connection between the at least one first point and the at least one second point provides a particular weight which is indicative of the at least one first point belonging with the at least one second point.

21. The method of claim 20, wherein the particular weight influences whether the at least one first point can be placed separately into the first part from the at least one second point.

22. The method of claim 17, wherein the at least one first point is associated with the first part if the first weight is greater than a predetermined threshold.

23. The method of claim 17, wherein the at least one second point is associated with the second part if the second weight is greater than a predetermined threshold.

24. The method of claim 20, wherein the associating step comprises determining whether the at least one first point is to be associated with the first part made based on the first weight and a particular weight provided by a connection between the at least one first point and the at least one second point.

25. The method of claim 24, wherein the associating step comprises determining whether the at least one second point is to be associated with the second part made based on the second weight and the particular weight.

26. The method of claim 17,

wherein the at least one first point is associated with the first part if the first weight is greater than a first threshold,

wherein the at least one second point is associated with the second part if the second weight is greater than a second threshold,

wherein the associating step comprises determining whether the at least one first point is to be associated with the first part made based on the first weight and the third weight, and

wherein the associating step comprises determining whether the at least one second point is to be associated with the second part made based on the second weight and the third weight.

27. The method of claim 26,

wherein a first possibility is a possibility that the first and second points are associated with the first part,

wherein a second possibility is a possibility that the first and second points are associated with the second part,

wherein a third possibility is a possibility that the at least one first point is associated with the first part, and the at least one second point is associated with the second part, and

wherein a fourth possibility is a possibility that the at least one first point is associated with the second part, and the at least one second point is associated with the first part.

28. The method of claim 27, wherein the first possibility is associated with a first cost data which is obtained by adding the first and second thresholds,

wherein the second possibility is associated with a second cost data which is obtained by adding the first and second weights,

wherein the third possibility is associated with a third cost data which is obtained by adding the first threshold, the second weight and the third weight, and

wherein the fourth possibility is associated with a fourth cost data which is obtained by adding the first weight, the second thresholds and the third weight.

29. The method of claim 28,

wherein the first possibility is prevalent when the first cost data is smaller than the second, third and fourth cost data,

wherein the second possibility is prevalent when the second cost data is smaller than the first, third and fourth cost data,

wherein the third possibility is prevalent when the third cost data is smaller than the first, second and fourth cost data, and

wherein the fourth possibility is prevalent when the fourth cost data is smaller than the first, second and third cost data.

30. The method of claim 15, wherein the first and second points are connected to one another via edges so as to form a graph structure.

31. The method of claim 15, wherein the first data and the second data form a graph data structure which comprises nodes and edges.

32. The method of claim 31, further comprising the step of:

assigning weights for the edges between the first and second points, wherein a first one of the weights is provided for a first edge of the edges connecting the first point with a voxel node to a first nonnegative number, and wherein a second one of the weights is provided for a second edge of the edges connecting the voxel node with the second point to a second nonnegative number.

33. The method of claim 15, further comprising the step of:

receiving third data corresponding to at least one third point in the space, the third data for each one of the at least one third point including third information indicative of a likelihood of an association of the third data to at least a third part of the respective third point, wherein the associating step includes the substep of associating the at least one third point with the first and second points based on the first, second and third information.

34. A system for associating particular data in a three-dimensional space, comprising:

a processing arrangement which, when executing the computer program, is configured to;

receive first data corresponding to at least one first point in the three-dimensional space, the first data for each one of the at least one first point including first information indicative of a likelihood of an association of the first data with at least a first part of the respective first point,

receiving second data corresponding to at least one second point in the three-dimensional space, the second data for each one of the at least one second point including second information indicative of a likelihood of an association of the second data with at least a second part of the respective second point, and

associate the first and second points to the respective first and second parts based on the first and second information.

35. The system of claims 34, wherein the first and second points are connected to one another via edges so as to form a graph structure.

36. A software storage medium which, when executed by a processing arrangement, is configured to associate particular data in a three-dimensional space, the software storage medium comprising:

a software program including;

a first module which, when executed, receives first data corresponding to at least one first point in the three-dimensional space, the first data for each one of the at least one first point including first information indicative of a likelihood of an association of the first data with at least a first part of the respective first point,

a second module which, when executed, receives second data corresponding to at least one second point in the three-dimensional space, the second data for each one of the at least one second point including second information indicative of a likelihood of an association of the second data with at least a second part of the respective second point, and

a third module which, when executed, associates the first and second points to the respective first and second parts based on the first and second information.

37. The software storage medium of claims 36, wherein the first and second points are connected to one another via edges so as to form a graph structure.

38. An image editing system, comprising:

an input device for inputting an image;

a graphical user interface for selecting first data and second data for the image; and

an image processor for editing the image, the image processor including a segmentation routine that builds a graph associated with the image and uses a graph cut algorithm to cut the graph into segments.

39. The image editing system of claim 38, wherein nodes of the graph represent portions of the image.

40. The image editing system of claim 39, wherein the portions of the image are one of pixels and voxels.

41. The image editing system of claim 39, wherein the edges of the graph represents neighborhood relationships among the nodes.

42. The image editing system of claim 39, wherein the graph includes a first terminal node and an second terminal node.

43. The image editing system of claim 42, wherein each of the non-terminal nodes of the graph is connected to both the first terminal node and the second terminal node.

44. The image editing system of claim 43, wherein the edges of the graph are each assigned a particular value.

45. The image editing system of claim 44, wherein the particular values are determined according to a function that is defined in terms of boundary and region properties.

46. The image editing system of claim 45, wherein the function uses first and second positions associated with the respective first and second data.

47. The image editing system of claim 44, wherein the graph is cut such that the total particular value of severed edges is minimized.

48. The image editing system of claim 38, further comprising an output device for displaying the segmented image.

49. The image editing system of claim 38, wherein the graphical user interface allows additional first and second data to be input.

50. A method for editing an image, comprising the steps of:

selecting first data and second data for the image; and

segmenting the image by building a graph associated with the image and using a graph cut algorithm to cut the graph into segments.

51. The method of claim 50, wherein nodes of the graph represent portions of the image.

52. The method of claim 51, wherein the portions of the image are one of pixels and voxels.

53. The method of claim 51, wherein the edges of the graph represents neighborhood relationships among the nodes.

54. The method of claim 50, wherein the graph includes a first terminal node and a second terminal node.

55. The method of claim 54, wherein each of the non-terminal nodes of the graph is connected to both the first terminal node and the second terminal node.

56. The method of claim 55, further comprising the step of assigning a particular value to each of the edges of the graph.

57. The method of claim 56, wherein the particular values are determined according to a function that is defined in terms of boundary and region properties.

58. The-method of claim 57, wherein the function uses first and second positions associated with the respective first and second data.

59. The method of claim 56, wherein the graph is cut such that the total value of severed edges is minimized.

60. The method of claim 50, further comprising the step of displaying the segmented image.

61. The method of claim 50, further comprising the step of selecting additional first data and second data.

62. A program storage device readable by a machine, tangibly embodying a program of instructions executable on the machine to perform method steps for editing an image, comprising the method steps of:

selecting first data and second data for the image; and

segmenting the image by building a graph associated with the image and using a graph cut algorithm to cut the graph into segments.