Code
From Computer Vision at Western
The following code libraries are freely available for research purposes only.
Check each download for documentation, usage requirements (what to cite), and licensing information.
Planar Graph Cut
The PlanarCut-v1.0 library computes max-flow/min-s-t-cut on planar graphs. It implements an efficient algorithm, which has almost linear running time. The library also provides for several easy-to-use interfaces in order to define planar graphs that are common in computer vision applications. The code was implemented by Eno Töppe and Frank R. Schmidt
Note: This code only works for planar graphs (including the terminal nodes). For more general problems, please use maxflow or gco (see below).
Downloads:
- Source code: PlanarCut-v1.0.zip – September 22, 2011 (LGPL)
- Relevant papers: CVPR2009.
Max-flow/min-cut
The maxflow-v3.01 library computes max-flow/min-cut on arbitrary graphs. It implements the Boykov-Kolmogorov algorithm, which tends to be is fast for computer vision problems. The B-K algorithm and its first implementation were developed while the authors were at Siemens Corporate Research, but we cannot distribute the original version. The code here was independently re-implemented by Vladimir Kolmogorov based on published materials.
Downloads:
- Source code: maxflow-v3.01.zip – January 26, 2010
- Relevant papers: PAMI2004.
Multi-label optimization
The gco-v3.0 library is for optimizing multi-label energies via the α-expansion and α-β-swap algorithms. It supports energies with any combination of unary, pairwise, and label cost terms. Written in C++, it comes bundled with a MATLAB wrapper. The code was developed by Olga Veksler and Andrew Delong.
New in version 3.0 – older versions here
- Label cost support in α-expansion, including costs on subsets of labels ("category costs").
- Sparse data cost support, for when each label is feasible for only a small fraction of sites; a fast special case!
- Adaptive cycles for α-expansion are used by default; often faster, but sometimes slower, so try both.
Downloads:
- Source code: gco-v3.0.zip – Apr 28 2010 – patched Apr 12, 2011
- Relevant papers: PAMI2001, PAMI2004a, PAMI2004b, and (if using label costs) IJCV2012.
Requirements:
- Visual C++ 2005 (VC8); GCC 4.03 (warning: not well-tested with GCC)
- MATLAB 7.4 (R2007a) for 32-bit wrapper; MATLAB 7.6 (R2008) for 64-bit wrapper
Max-flow/min-cut for massive grids
The regionpushrelabel-v1.07 library computes max-flow/min-cut on huge N-dimensional grid-graphs in graphics, vision, and medical imaging. The C++ implementation is designed specifically for multi-core systems and graphs larger than available memory. Besides nearest-neighbour graphs, the library also supports more complex regular structures to speed up things like QPBO, cell complexes, and Ishikawa-like constructions. The public implementation was developed by Sameh Khamis who is now at the University of Maryland.
Downloads:
- Source code: regionpushrelabel-v1.07.zip – March 25, 2011 – updated April 21, 2012
- Relevant papers: CVPR2008
Requirements:
- Visual C++ 2008 (VC9) or GCC 4.4.1
- Boost C++ libraries version 1.39 or later
Max-flow/min-cut for shape fitting
The TouchExpand library efficiently computes globally optimal max-flow on a special type of graph. The touch-expand algorithm relies on sparse unary terms (source/sink arcs) to solve max-flow in a memory-efficient manner. Such sparse unary terms arise, for example, in shape-from-points problems. The algorithm works within a narrow band, growing it in an on-demand fashion, until a global optimum of the full problem is guaranteed. The code is by Victor Lempitsky and is based on the maxflow-v3.0 library.
Downloads:
- Source code: TouchExpand.zip
- Relevant papers: CVPR2007 + TECHREPORT.
