Graph Cuts, Caveat Utilitor, and Euler's Bridges of Konigsberg

Please use this identifier to cite or link to this publication:
Graph-based algorithms have enjoyed renewed interest for solving computer vision problems. These algorithms have been the subject of intense interest and research. In order to maintain the ITK library au courant, we developed a framework for graph-based methods of energy minimization in ITK which employ energy functions derived within a Markov Random Field (MRF) context. This required not only the implementation of the energy minimization methodology but also the more general requirement of introducing graph-related data structures into ITK which can be used for other graph-based algorithms pertinent to future extensions of the ITK library.

Please note that some of the algorithms described in this paper may be covered by patents and, as such, it is incumbent upon the user to seek licenses before building the binaries which utilize this code. Also note that “research use” is not exempt from acquiring such licenses. The only exemption from patent restrictions is “. . . amusement, to satisfy idle curiosity, or for strictly philosophical inquiry.”
There is no code review at this time.

minus Simple graph cuts are not demonstrated. by David Doria on 2009-09-14 09:45:34 for revision #1
starstarstarstarstar expertise: 2 sensitivity: 3

Before diving into the MRF inspired graph cuts for image segmentation, I decided to try some simple graph cuts on very simple (|V|=2, |E|=1 sized) graphs. It seems to me that this type of thing should definitely be possible with itkGraph, and if it was, this contribution would provide a much needed feature for ITK. However, I was unable to get even such a simple problem to work.

I think things like the following should be answered and demonstrated in the documentation:

1) How to construct a graph (create nodes, edges, edge weights, specify sources/sinks)

2) How to perform a cut.

3) How to get the results of the cut (which nodes are on which "side" of the graph after the cut)

4) If the graph is undirected, must all reverse edges be set to te same value anyway (I know this is the case with the boost graph cut functions)?

I understand this IJ submission was not addressing these things specifically, but I beleive this framework is clearly what the submission was built on, so exposing it to the users would be a huge service (and very easy!).

Free comment :

An example was provided that demonstrates BoykovAlphaExpansionMRFImageFilter, but not itkBoykovMinCutGraphFilter and itkGraph directly. An example such as the following (which I cannot get to give the correct output) would add tremendous value to this contribution.


#include <iostream>

#include "itkGraph.h"
#include "itkBoykovGraphTraits.h"
#include "itkBoykovMinCutGraphFilter.h"

int main( int argc, char * argv[] )
    //setup types
    typedef itk::BoykovGraphTraits<short, 3> GraphTraitsType;
    typedef itk::Graph<GraphTraitsType>           GraphType;
    typedef GraphType::NodePointerType      NodePointerType;
    typedef GraphType::EdgePointerType      EdgePointerType;
    //create a new graph
    GraphType::Pointer graph = GraphType::New();

      // Create graph nodes
    NodePointerType Nodes[3];
    for( unsigned int i = 0; i < 2; i++ )
        Nodes[i] = graph->CreateNewNode();
    //these lines don't change the behavior
    Nodes[0]->IsSink = true; //set node 0 to be a sink
    Nodes[1]->IsSink = false; //set node 1 to be a source
    //create an edge between nodes 0 and 1 with weight 2
    graph->CreateNewEdge( Nodes[0], Nodes[1], 2);
    //verify that the graph was created correctly
    std::cout << std::endl;
    std::cout << "Num Nodes: " << graph->GetTotalNumberOfNodes() << std::endl;
    std::cout << "Num Edges: " << graph->GetTotalNumberOfEdges() << std::endl;

    // Set the reverse edges (doesn't change the behavior)

    //perform the cut
    typedef itk::BoykovMinCutGraphFilter  <GraphType> FilterType;
    FilterType::Pointer CutFilter = FilterType::New();
    //see which nodes are sinks
    typedef GraphType::NodeIterator         NodeIteratorType;
    typedef GraphType::NodeIdentifierType   NodeIdentifierType;
    NodeIteratorType nit( graph );
    for( nit.GoToBegin(); !nit.IsAtEnd(); ++nit )
        NodePointerType node = nit.GetPointer();
        NodeIdentifierType Id = graph->GetNodeIdentifier( node );
        node = graph->GetNodePointer( Id );
            std::cout << "Node Id: " << Id << " is a sink." << std::endl;
            std::cout << "Node Id: " << Id << " is a source." << std::endl;
    //get the cut weight (min cut = max flow)
    typedef GraphType::NodeWeightType       NodeWeightType;
    NodeWeightType maxflow = CutFilter->GetMaxFlow();
    std::cout << "Max Flow: " << maxflow << std::endl;  //expected: 2, actual: 0
    return EXIT_SUCCESS;

Comment by Otertonbibi Vigorda: yellow

Comment by Otertonbibi Vigorda: yellow

Comment by Otertonbibi Vigorda: yellow

Comment by Nsmanrich Vigorda: yellow

Comment by Nsmanrich Vigorda: yellow

Comment by Nsmanrich Vigorda: yellow

Comment by Eunicerosa Vigorda: yellow

Comment by Eunicerosa Vigorda: yellow

Comment by Eunicerosa Vigorda: yellow

Comment by Mwangmajor Holland: yellow

minus Good Contribution by Subrahmanyam Gorthi on 2008-11-19 10:43:56 for revision #1
starstarstarstarstar expertise: 2 sensitivity: 3

The authors presented ITK implementation of the basic data structures for handling the graph cut problems, along with the Boykov alpha-expansion algorithm.They provided 2-D and 3-D examples of segmentation using the graph cuts algorithm. This is a significant contribution to ITK in the area of computer vision.


Not Applicable.


2-D and 3-D segmentation examples are given.

Appropriate references are given.

Open Science:

This submission conformed to all my expectations of open science.i.e.,

  • The authors provided the source code of their implementation.

  • They provided the input images that they used.

  • They provided enough details to be able to replicate their work.

Code Quality :

The code is easy to read and the necessary documentation is provided.


The data structures and algorithms presented are general. Hence, they can be applied to a wide range of problems in computer vision.

Free comment :

This is a significant contribution to ITK.

Minor comments:

  1. The phrase: "Caveat Utilitor", which is present in the paper title, is nowhere else mentioned in the paper. A brief description of it will be helpful.

  2. It seems there are two mismatches between the file-names mentioned in the paper, and the actual file-names in the "Source" directory. (i) In Page number:5 of the paper, under the "Testing" heading, a file with the name: "itkBoykovAlphaExpansionFilterTest.cxx" is mentioned. But, that file is not present in the "Source directory" of the code. (ii) Same is with the file-name under the "Examples" heading.

  3. It will be nice if the approximate times taken for segmentation of the images considered in the paper can be tabulated. Although they are not very exact, they can give a feel of approx. time taken, to the reader.

Thank you very much for this wonderful contribution.

Add a new review
Quick Comments
Comment by Mesut Ozdag yellow
Here is an example I tried to execute.

I am creating my graph as follows:

Instead of having 2 source nodes 4 sink nodes and 9 maxflow
I am having all nodes source and maxflow 0.

for( unsigned int i = 0; i 6; i++ )
Nodes[i] = graph-CreateNewNode();
for( unsigned int i = 0; i 6; i++ )
Nodes[i] = graph-GetNodePointer( i );

//create edges between nodes with weights
graph-CreateNewEdge( Nodes[0] Nodes[1] 5);
graph-CreateNewEdge( Nodes[1] Nodes[2] 6 );
graph-CreateNewEdge( Nodes[2] Nodes[3] 6 );
graph-CreateNewEdge( Nodes[4] Nodes[3] 6 );
graph-CreateNewEdge( Nodes[5] Nodes[4] 1 );
graph-CreateNewEdge( Nodes[0] Nodes[5] 5 );
graph-CreateNewEdge( Nodes[5] Nodes[2] 3 );
graph-CreateNewEdge( Nodes[1] Nodes[4] 3 );
Comment by Mesut Ozdag yellow
Can you please provide us an example for how to use itkBoykovMinCutGraphFilter?

Download All
Download Source code

Statistics more
Global rating: starstarstarstarstar
Review rating: starstarstarstarstar [review]
Code rating:
Paper Quality: plus minus

Information more
Categories: Data Representation, Segmentation
Keywords: Graph Cuts, Graphs, Min-Cut, Max Flow, Graph Data Structure
Toolkits: ITK
Export citation:


Linked Publications more
Reader/Writer for Analyze Object Maps for ITK Reader/Writer for Analyze Object Maps for ITK
by Hawley J., Johnson H.
Diffeomorphic Demons Using ITK's Finite Difference Solver Hierarchy Diffeomorphic Demons Using ITK's Finite Difference Solver Hierarchy
by Vercauteren T., Pennec X., Perchant A., Ayache N.

View license
Loading license...

Send a message to the author
Powered by Midas