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

Patent metadata

Field	Value
Publication number	US-9582891-B2
Application number	US-201414507268-A
Country	US
Kind code	B2
Filing date	Oct 6, 2014
Priority date	Sep 23, 1999
Publication date	Feb 28, 2017
Grant date	Feb 28, 2017

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.

First claim

We claim:

1. A non-transitory computer-accessible medium having stored thereon computer-executable instructions for segmenting at least one image, wherein, when a computer arrangement executes the instructions, the computer arrangement is configured to perform procedures, comprising:
receiving data associated with the at least one image;
generating a plurality of nodes based on the data;
assigning at least one weight based on information associated with the nodes; and
segmenting the at least one image based on the nodes and the at least one weight using a minimum cut procedure.

2. The computer-accessible medium of claim 1 , wherein the computer arrangement is further configured to determine at least one edge between at least two of the nodes.

3. The computer-accessible medium of claim 2 , wherein the computer arrangement is further configured to assign the at least one weight to the at least one edge based on a distance between the at least two of the nodes.

4. The computer-accessible medium of claim 3 , wherein the computer arrangement is further configured to merge the at least two nodes based on a substantially large weight for at least one of the at least one edge in both directions between the nodes or at least one undirected edge in one direction between the at least two of the nodes.

5. The computer-accessible medium of claim 3 , wherein the computer computer-arrangement is further configure to remove the at least one edge if the at least one weight assigned to the at least one edge is 0.

6. The computer-accessible medium of claim 3 , wherein the computer arrangement is further configured to generate at least one graph based on the nodes and the at least one edge.

7. The computer-accessible medium of claim 6 , wherein the computer arrangement is further configured to map at least one of at least one pixel or at least one voxel to at least one of the nodes of the graph.

8. The computer-accessible medium of claim 6 , wherein the computer arrangement is further configured to (i) segment the at least one graph into at least two parts, and (ii) place each of the nodes in a single part of the graph.

9. The computer-accessible medium of claim 8 , wherein the computer arrangement is further configured to cut or remove the at least one edge if the at least two of the nodes belong to different parts of the at least one graph.

10. The computer-accessible medium of claim 9 , wherein at least one edge includes a plurality of edges, and wherein the segmenting is performed with a particular minimum cut of the minimum cut procedure based on a sum of a plurality of weights of the edges that have been cut.

11. The computer-accessible medium of claim 10 , wherein the computer arrangement is further configured to segment at least one of a plurality of pixels or a plurality of voxels based on the particular minimum cut.

12. The computer-accessible medium of claim 8 , wherein the computer arrangement is further configured to keep the at least one edge if the at least two of the nodes belong to a same part of the at least one graph.

13. The computer-accessible medium of claim 8 , wherein the computer arrangement is further configured to assign at least one label to each of the nodes based on the single part of the graph that a particular node of the nodes is placed in.

14. The computer-accessible medium of claim 6 , wherein the at least one graph is a directed edge graph.

15. The computer-accessible medium of claim 1 , wherein the at least one weight is non-negative.

16. The computer-accessible medium of claim 1 , wherein the at least one weight is a double precision floating point number greater than or equal to 0.

17. The computer-accessible medium of claim 1 , wherein the segmenting procedure is further based on a sum of a plurality of weights.

18. The computer-accessible medium of claim 1 , wherein the segmentation procedure is further based on at least one segmentation of the image having a minimum sum equation substantially equal to 1.

19. A method for segmenting at least one image, comprising:
receiving data associated with the at least one image;
generating a plurality of nodes based on the data;
assigning at least one weight based on information associated with the nodes; and
using a computer hardware arrangement, segmenting the at least one image based on the nodes and the at least one weight using a minimum cut procedure.

20. A system for segmenting at least one image, comprising:
a computer hardware arrangement:
receive data associated with the at least one image;
generate a plurality of nodes based on the data;
assign at least one weight based on information associated with the nodes; and
segment the at least one image based on the nodes and the at least one weight using a minimum cut procedure.

Assignees

• Univ New York

Inventors

• Geiger Davi
• Ishikawa Hiroshi

Classifications

• G06V10/7635

  based on graphs, e.g. graph cuts or spectral clustering · CPC title

• G06F18/2323

  based on graph theory, e.g. minimum spanning trees [MST] or graph cuts · CPC title

• G06V10/267

  by performing operations on regions, e.g. growing, shrinking or watersheds · CPC title

• G06K9/6224

  Physics · mapped topic

• G06K9/342

  Physics · mapped topic