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 [5] and/or processed (i.e. cut) using 3rd party graph-cut [1] algorithms.

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

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 [7].

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 [6].

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 [5], 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 [4] 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#

[4] (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

[6]

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

[7]

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.

On this page