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

• US 7,893,939 B2
• Filed: 01/14/2005
• Issued: 02/22/2011
• Est. Priority Date: 09/23/1999
• Status: Active Grant

• Current Assignee: New York University
• Original Assignee: New York University
• Inventors: Ishikawa, Hiroshi, Geiger, Davi
• Primary Examiner(s): Abdulselam; Abbas I
• Application Number:
  US11/035,711
• Publication Number:
  US 20050134587A1
• Time in Patent Office: 2,230 Days
• Field of Search: 345/424, 345/156, 345/419, 700/98, 700/153, 707/101, 382/173
• US Class Current: 345/424
• 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. A method for associating particular data in a three-dimensional space provided in or on a computer accessible medium and being executable by a processing arrangement, 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 at least one 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 at least one second point; and

associating the at least one first point and the at least one second points to the respective first and second parts based on the first and second information.

2. The method of claim 1, wherein the first data corresponds to a first voxel, and wherein the second data corresponds to a second voxel.

3. The method of claim 1, wherein the first information includes first weights, and wherein the second information includes second weights.

4. The method of claim 3, wherein the at least one first point is associated with the first part if the first weight indicates a higher likelihood for such association.

5. The method of claim 3, wherein the at least one second point is associated with the second part if the second weight indicates a higher likelihood for such association.

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

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

8. The method of claim 3,

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.

9. The method of claim 8,

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

wherein a second possibility is a possibility that the at least one first point and the at least one 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.

10. The method of claim 9, 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.

11. The method of claim 10,

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.

12. The method of claim 1, 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.

13. The method of claim 12, 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.

14. The method of claim 12, 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.

15. The method of claim 14, 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.

16. The method of claim 1, wherein the at least one first point and the at least one second points are connected to one another via edges so as to form a graph structure.

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

18. The method of claim 17, further comprising the step of:

assigning weights for the edges between the at least one first point and the at least one second points, wherein a first one of the weights is provided for a first edge of the edges connecting the at least one 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 at least one second point to a second nonnegative number.

19. The method of claim 1, 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 at least one third point, wherein the associating step includes the substep of associating the at least one third point with the at least one first point and the at least one second points based on the first, second and third information.

20. 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 at least one 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 at least one second point, and

associate the at least one first point and the at least one second points to the respective first and second parts based on the first and second information.

21. The system of claim 20, wherein the at least one first point and the at least one second points are connected to one another via edges so as to form a graph structure.

22. A software storage medium, which is non-transitory 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 at least one 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 at least one second point, and

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

23. The software storage medium of claim 22, wherein the at least one first point and the at least one second points are connected to one another via edges so as to form a graph structure.

24. An image editing system, comprising:

an input device configured to inputting an image containing at least one portion with image data of at least three dimensions;

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

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

25. The image editing system of claim 24, wherein nodes of the graph represent portions of the image.

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

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

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

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

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

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

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

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

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

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

36. The image editing system of claim 24, wherein the at least one portion includes voxels.

37. A method for editing an image provided in or on a computer accessible medium and being executable by a processing arrangement, 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, wherein the image contains at least one portion with image data of at least three dimensions.

38. The method of claim 37, wherein nodes of the graph represent portions of the image.

39. The method of claim 38, wherein the portions of the image are one of pixels and voxels.

40. The method of claim 38, wherein the edges of the graph represents neighborhood relationships among the nodes.

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

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

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

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

45. The method of claim 44, wherein the function uses first and second positions associated with the respective first and second data.

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

47. The method of claim 37, further comprising the step of displaying the segmented image.

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

49. The method of claim 37, wherein the at least one portion includes voxels.

50. 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, wherein the image contains at least one portion with image data of at least three dimensions.

51. The program storage device of claim 50, wherein the at least one portion includes voxels.

52. A software storage medium, which is non-transitory which, when executed by a processing arrangement, is configured to edit a video, the software storage medium comprising:

a software program comprising,

a first module which, when executed by the processing arrangement, receives data corresponding to the video, the video comprising at least one first image and at least one second image;

a second module which, when executed by the processing arrangement, generates at least one first graph associated with the at least one first image and at least one second graph associated with the at least one second image, the at least one first graph having nodes and edges associated with the at least one first image and the at least one second graph and having nodes and edges associated with the at least one second image; and

a third module which, when executed by the processing arrangement, segments the video into segments by applying a graph cut procedure to the at least one first graph and the at least one second graph.

53. The software storage medium of claim 52, wherein the software program further comprises a fourth module which, when executed by the processing arrangement, associates the segments of the at least one first graph with the segments of the at least one second graph.

54. The software storage medium of claim 53, wherein the software program further comprises a fifth module which, when executed by the processing arrangement, displays the segmented video.

55. The software storage medium of claim 52 , wherein the at least one first image and the at least one second image are three dimensional images.

56. The software storage medium of claim 52, wherein the at least one first image and the at least one second image are sequential images in the video.

57. The software storage medium of claim 52, wherein the video is for a moving object, the moving object being present in the at least one first image and the at least one second image.

58. The software storage medium of claim 57, wherein the third module, when executed by the processing arrangement, segments the video into a first portion and a second portion, the first portion corresponding to the moving object and the second portion corresponding to an area immediately adjacent to the moving object.

59. An image editing system, comprising:

an input device configured to input an image;

a graphical user interface configured to select first data and second data for the image; and

an image processor configured to edit the image, the image processor including a segmentation routine that is configured to build a graph associated with the image and uses a graph cut algorithm to cut the graph into segments, wherein the graph comprises nodes and edges having weights, and wherein (i) the nodes comprise at least one first node, at least one second node and a plurality of voxel nodes, and (ii) the edges comprise;

at least one first edge connecting the at least one first node to at least one of the voxel nodes,

at least one second edge connecting at least one of the voxel nodes to the at least one second node, and

at least one third edge connecting at least one of the voxel nodes to another one of the voxel nodes.

60. An image editing system, comprising:

an input device configured to input an image;

a graphical user interface configured to select first data and second data for the image; and

an image processor configured to edit the image, the image processor including a segmentation routine that is configured to build a graph associated with the image and uses a graph cut algorithm to cut the graph into segments, wherein the graph contains a plurality of neighbor voxel edges for a k^th nearest neighbor structure, and k is a value of at least 2.