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,
|
Create a graph-cut ready graph to segment a nD image using the voxel neighbourhood. |
|
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 term processing adjacent voxels maximum value using a linear relationship. |
|
Boundary term processing adjacent voxels difference value using a linear relationship. |
|
Boundary term processing adjacent voxels maximum value using an exponential relationship. |
|
Boundary term processing adjacent voxels difference value using an exponential relationship. |
|
Boundary term processing adjacent voxels maximum value using a division relationship. |
|
Boundary term processing adjacent voxels difference value using a division relationship. |
|
Boundary term processing adjacent voxels maximum value using a power relationship. |
|
Boundary term processing adjacent voxels difference value using a power relationship. |
Regional energy terms#
|
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 term based on the difference of means between adjacent image regions. |
|
Boundary term based on the sum of border voxel pairs differences. |
|
Boundary term based on the sum of border voxel pairs differences, directed version. |
Regional energy terms#
|
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.
|
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.
|
A graph representation that works directly with the maxflow.GraphDouble graph as base. |
|
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.
Graph template intance with double for flowtype, tcaptype and captype. |
|
Graph template intance with float for flowtype, tcaptype and captype. |
|
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.
|
Splits an integer marker image into two binary image containing the foreground and background markers respectively. |
|
Executes a graph cut by splitting the original volume into a number of sub-volumes of a minimal edge length. |
|
Executes multiple graph cuts in parallel. |
|
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#
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
Stawiaski J., Decenciere E., Bidlaut F. “Interactive Liver Tumor Segmentation Using Graph-cuts and watershed” MICCAI 2008 participation
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.