# Graph-cut (max-flow/min-cut) (`medpy.graphcut`

)¶

Provides functionalities to efficiently construct nD graphs from various sources using arbitrary energy functions (boundary and regional terms). The graph can then be saved in the Dimacs graph standard [R28] and/or processed (i.e. cut) using 3rd party graph-cut [R24] algorithms.

This module makes use of a custom *Boost.Python* [R25] wrapper written for a modified
version of Boykov and Kolmogorovs max-flow/min-cut algorithm (v3.01) [R27] that can be found at [R26].

Supports voxel- as well as label/region-based graph-cuts.

See below for examples.

## Directly generate graphs from image `medpy.graphcut.generate`

¶

Provides functions to generate graphs efficiently from nD images.
Use together with an energy term from `energy_voxel`

respectively `energy_label`

,

`graph_from_voxels` (fg_markers, bg_markers[, …]) |
Create a graph-cut ready graph to segment a nD image using the voxel neighbourhood. |

`graph_from_labels` (label_image, fg_markers, …) |
Create a graph-cut ready graph to segment a nD image using the region neighbourhood. |

## Energy terms for voxel-based graph-cuts `medpy.graphcut.energy_voxel`

¶

Run-time optimized energy functions for the graph generation. Voxel based [R30].

### Boundary energy terms¶

`boundary_maximum_linear` (graph, …) |
Boundary term processing adjacent voxels maximum value using a linear relationship. |

`boundary_difference_linear` (graph, …) |
Boundary term processing adjacent voxels difference value using a linear relationship. |

`boundary_maximum_exponential` (graph, …) |
Boundary term processing adjacent voxels maximum value using an exponential relationship. |

`boundary_difference_exponential` (graph, …) |
Boundary term processing adjacent voxels difference value using an exponential relationship. |

`boundary_maximum_division` (graph, …) |
Boundary term processing adjacent voxels maximum value using a division relationship. |

`boundary_difference_division` (graph, …) |
Boundary term processing adjacent voxels difference value using a division relationship. |

`boundary_maximum_power` (graph, xxx_todo_changeme7) |
Boundary term processing adjacent voxels maximum value using a power relationship. |

`boundary_difference_power` (graph, …) |
Boundary term processing adjacent voxels difference value using a power relationship. |

### Regional energy terms¶

`regional_probability_map` (graph, …) |
Regional term based on a probability atlas. |

## Energy terms for label-based graph-cuts `medpy.graphcut.energy_label`

¶

Run-time optimized energy functions for the graph generation. Label/Superpixel based [R29].

### Boundary energy terms¶

`boundary_difference_of_means` (graph, …) |
Boundary term based on the difference of means between adjacent image regions. |

`boundary_stawiaski` (graph, label_image, …) |
Boundary term based on the sum of border voxel pairs differences. |

`boundary_stawiaski_directed` (graph, …) |
Boundary term based on the sum of border voxel pairs differences, directed version. |

### Regional energy terms¶

`regional_atlas` (graph, label_image, …) |
Regional term based on a probability atlas. |

## Persist a graph `medpy.graphcut.write`

¶

Functions to persist a graph in file formats like Dimacs [R28], which can be read by external graph-cut algorithms.

`graph_to_dimacs` (g, f) |
Persists the supplied graph in valid dimacs format into the file. |

## Graph `medpy.graphcut.graph`

¶

Graph objects that can be used to generate a custom graph and execute a graph-cut over it.

`GCGraph` (nodes, edges) |
A graph representation that works directly with the maxflow.GraphDouble graph as base. |

`Graph` () |
Represents a graph suitable for further processing with the graphcut package. |

## Maxflow `medpy.graphcut.maxflow`

¶

C++ wrapper around the max-flow/min-cut implementation of [R27] using Boost.Python.
Do not use these directly, but rather the graph objects supplied by `medpy.graphcut.graph`

.

`GraphDouble` |
Graph template intance with double for flowtype, tcaptype and captype. |

`GraphFloat` |
Graph template intance with float for flowtype, tcaptype and captype. |

`GraphInt` |
Graph template intance with int for flowtype, tcaptype and captype. |

## Wrapper `medpy.graphcut.wrapper`

¶

Wrappers for executing graph cuts in a memory-friendly way and other convenience functions.

`split_marker` (marker[, fg_id, bg_id]) |
Splits an integer marker image into two binary image containing the foreground and background markers respectively. |

`graphcut_split` (graphcut_function, regions, …) |
Executes a graph cut by splitting the original volume into a number of sub-volumes of a minimal edge length. |

`graphcut_subprocesses` (graphcut_function, …) |
Executes multiple graph cuts in parallel. |

`graphcut_stawiaski` (regions[, gradient, …]) |
Executes a Stawiaski label graph cut. |

### Example of voxel based graph cut¶

Import the necessary methods

```
>>> import numpy
>>> from medpy.io import load, header
>>> from medpy.graphcut import graphcut_from_voxels
>>> from mdepy.graphcut.energy_voxel import boundary_difference_exponential
```

Loading the images and setting the parameters. Assuming that *image.nii* contains
the image on which to execute the graph-cut, *fgmarkers_image.nii* a binary image
of the same size with True values for the foreground markers and *bgmarkers_image.nii*
respectively for the background markers.

```
>>> image_data, image_header = load("image.nii")
>>> fgmarkers_image_data, _ = load("fgmarkers_image.nii")
>>> bgmarkers_image_data, _ = load("bgmarkers_image.nii")
>>> sigma = 15.
>>> spacing = header.get_pixel_spacing(image_header)
```

Building the graph.

```
>>> gcgraph = graph_from_voxels(fgmarkers_image_data,
bgmarkers_image_data,
boundary_term = boundary_difference_exponential,
boundary_term_args = (image_data, sigma, spacing))
```

Executing the graph-cut (depending on the image size, this might take a while).

```
>>> maxflow = gcgraph.maxflow()
```

Building the resulting segmentation image, with True values for foreground and False values for background voxels.

```
>>> result_image_data = numpy.zeros(image_data.size, dtype=numpy.bool)
>>> for idx in range(len(result_image_data)):
result_image_data[idx] = 0 if gcgraph.termtype.SINK == gcgraph.what_segment(idx) else 1
>>> result_image_data = result_image_data.reshape(image_data.shape)
```

### References¶

[R24] | http://en.wikipedia.org/wiki/Graph_cuts_in_computer_vision |

[R25] | http://www.boost.org/doc/libs/1_55_0/libs/python/doc/ |

[R26] | http://vision.csd.uwo.ca/code/ |

[R27] | (1, 2) Boykov Y., Kolmogorov V. “An Experimental Comparison of Min-Cut/Max-Flow
Algorithms for Energy Minimization in Vision” In IEEE Transactions on PAMI, Vol. 26,
No. 9, pp. 1124-1137, Sept. 2004 |

[R28] | (1, 2) http://lpsolve.sourceforge.net/5.5/DIMACS_maxf.htm |

[R29] | Stawiaski J., Decenciere E., Bidlaut F. “Interactive Liver Tumor Segmentation Using Graph-cuts and watershed” MICCAI 2008 participation |

[R30] | Kolmogorov, Vladimir, and Ramin Zabin. “What energy functions can be minimized via graph cuts?.” Pattern Analysis and Machine Intelligence, IEEE Transactions on 26.2 (2004): 147-159. |