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

• US 7,212,201 B1
• Filed: 09/20/2000
• Issued: 05/01/2007
• 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): Hjerpe; Richard
• Assistant Examiner(s): Abdulselam; Abbas I.
• Application Number:
  US09/666,371
• Time in Patent Office: 2,414 Days
• Field of Search: 345/156, 345/183, 345/782, 345/502, 345/424, 345/426, 345/427, 345/419, 345/421, 345/420, 716/7, 382/173, 382/177, 382/151, 382/154, 382/174, 382/228, 700/93, 700/98, 702/153, 702/152, 707/101
• US Class Current: 345/420
• 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 software storage medium which, when executed by a processing arrangement, is configured to associate particular data in a space which has at least three dimensions, 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 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 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, 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.

2. The software storage medium of claim 1, 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.

3. The software storage medium of claim 1, wherein the third module, when executed, associates the first and second points by 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.

4. The software storage medium of claim 3, wherein the third module, when executed, associates the first and second points by 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.

5. A software storage medium which, when executed by a processing arrangement, is configured to associate particular data in a space which has at least three dimensions, 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 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 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, wherein the first information includes first weights, and wherein the second information includes second weights, and wherein the at least one first point is associated with the first part if the first weight is greater than a predetermined threshold.

6. A software storage medium which, when executed by a processing arrangement, is configured to associate particular data in a space which has at least three dimensions, 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 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 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, wherein the first information includes first weights, and wherein the second information includes second weights, and wherein the at least one second point is associated with the second part if the second weight is greater than a predetermined threshold.

7. A software storage medium which, when executed by a processing arrangement, is configured to associate particular data in a space which has at least three dimensions, 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 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 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,

wherein the first information includes first weights, and wherein the second information includes second weights,

wherein a connection between the at least one first point and the at least one second point provides a third weight which is indicative of the at least one first point belonging with the at least one second point,

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, and

wherein the third module, when executed, associates the first and second points by (i) 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

(ii) 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.

8. The software storage medium of claim 7,

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.

9. The software storage medium of claim 8, 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.

10. The software storage medium of claim 9,

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.

11. A software storage medium which, when executed by a processing arrangement, is configured to associate particular data in a space which has at least three dimensions, 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 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 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, wherein the first data and the second data form a graph data structure which comprises nodes and edges.

12. The software storage medium of claim 11, further comprising:

a fourth module which, when executed, assigns 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.

13. A software storage medium which, when executed by a processing arrangement, is configured to associate particular data in a space which has at least three dimensions, 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 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 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;

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; and

a fourth module which, when executed, receives 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.

14. A software storage medium which, when executed by a processing arrangement, is configured to segment input data representing an image in order to locate a part of said image, said input data comprising voxels, said software storage medium comprising:

a software program including;

a first module which, when executed, stores a graph data structure in the memory arrangement, said graph data structure comprising nodes and edges having weights, wherein

(i) said nodes comprise at least one first node s, at least one second node t, and a plurality of voxel nodes, and

(ii) said edges comprise;

(A) at least one first edge connecting said first node s to at least one of said voxel nodes,

(B) at least one second edge connecting at least one of said voxel nodes to said second node t, and

(C) at least one neighbor edge connecting at least one of said voxel nodes to another one of said voxel nodes;

a second module which, when executed, designates one of said voxel nodes as corresponding voxel node for each of said voxels,

a third module which, when executed, partitions said nodes into at least two groups, one including said first node s and another one including said second node t, by a minimum-cut algorithm, and

a fourth module which, when executed, partitions said voxels into at least two segments by assigning each of said voxels to the segment corresponding to the group to which said corresponding voxel node for the voxel belongs.

15. The software storage medium of claim 14 wherein:

said input data further comprises a neighborhood structure, and

at least one of said neighbor edges is between two of said voxel nodes designated as said corresponding voxel nodes for said two of said voxels that are neighbors to one another according to said neighborhood structure.

16. The software storage medium of claim 15, wherein said voxels comprise at least one of a portion of or an entire DIM-dimensional array of data.

17. The software storage medium of claim 16, wherein said neighborhood structure comprises a k-th nearest neighborhood structure.

18. The software storage medium of claim 17, wherein at least one part of said array of data represents one or more physical properties of said voxels at regular grid positions within an interior of solid bodies.

19. The software storage medium of claim 16, wherein at least one part of said array of data represents one or more physical properties of said voxels at regular grid positions within an interior of solid bodies.

20. The software storage medium of claim 16, wherein a size of the DIM is at least 3.

21. The software storage medium according to claim 14, wherein the first module segments said nodes and said edges, and wherein the third module implements said minimum-cut algorithm on said segmented nodes and edges.

22. The software storage medium of claim 14, wherein said input data further comprises a likelihood number for each of said voxels, and further comprising:

a fourth module which, when executed, sets weights for said first, second and neighbor edges for each voxel node by setting;

(i) a weight for said first edge connecting said first node s with said voxel node to a first nonnegative number w1, and

(ii) a weight for said second edge connecting said voxel node with said second node t to a second nonnegative number w2 so that the first non-negative number minus the second non-negative number equals the sum of likelihood numbers for all of said voxels to which said voxel node is designated as said corresponding voxel node.

23. The software storage medium of claim 22, wherein:

said input data further comprises a neighborhood structure, and

at least one of said neighbor edges is between two of said voxel nodes designated as said corresponding voxel nodes for two of said voxels that are neighbors according to said neighborhood structure.

24. The software storage medium of claim 23, wherein said voxels comprise at least one of a portion of or an entire a DIM-dimensional array of data.

25. The software storage medium of claim 24, wherein said neighborhood structure comprises a k-th nearest neighborhood structure.

26. The software storage medium of claim 25, wherein at least one part of said array of data represents one or more physical properties at regular grid positions within an interior of solid bodies.

27. The software storage medium of claim 24, wherein at least one part of said array of data represents one or more physical properties at regular grid positions within an interior of solid bodies.

28. The software storage medium of claim 24, wherein a size of the DIM is at least three.

29. A software storage medium which, when executed by a processing arrangement, is configured to associate particular data in a space which has at least three dimensions, 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 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 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,

wherein the first and second points are connected to one another via edges so as to form a graph structure.

30. The software storage medium of claim 29, wherein the first data corresponds to the a first voxel, and wherein the second data corresponds to second voxel.

31. The software storage medium of claim 29, wherein the first information includes first weights, and wherein the second information includes second weights.

32. The software storage medium of claim 31, wherein the first point is associated with the first part if the first weight indicates a higher likelihood for such association.

33. The software storage medium of claim 31, wherein the second point is associated with the second part if the second weight indicates a higher likelihood for such association.

34. A software storage medium which, when executed by a processing arrangement, is configured to associate particular data in a space which has at least three dimensions, 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 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 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,

wherein the first data and the second data form a graph data structure which comprises nodes and edges.