fast graph-cuts for grids

Features

GridCut is high performance max-flow/min-cut solver for graphs with grid-like topologies. It is free for non-profit use and evaluation purposes. License permitting commercial use is available for purchase. It is written in portable C++ and thus can be easily integrated into existing systems on various platforms.

Fast, Compact & Parallel

GridCut combines current state-of-the-art in max-flow/min-cut computation on graphs with grid-like topologies. It is based on a popular Boykov-Kolmogorov  (BK) algorithm [1] featuring bidirectional search for augmenting paths and tree-reuse mechanism. In addition to that it implements two key improvements:

cf. Benchmark to see the improvement in terms of speed and memory consumption in contrast to publicly available implementation of BK.

Supported Topologies

GridCut supports following graph topologies:

however, it is not limited to them and can be extended upon request.

Feel free to Contact Us and discuss other possible improvements.

References

[1]Yuri Boykov and Vladimir Kolmogorov:
An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision
IEEE Transactions on Pattern Analysis and Machine Intelligence 26(9):1124-1137, 2004.
[2]Jiangyu Liu and Jian Sun:
Parallel Graph-cuts by Adaptive Bottom-up Merging
Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, pp. 2181-2188, 2010.
[3]Ondřej Jamriška, Daniel Sýkora, and Alexander Hornung:
Cache-efficient Graph Cuts on Structured Grids
Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, pp. 3673-3680, 2012.