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:

• adaptive bottom-up merging [2] which allows parallel processing and thus additional speed-up on multi-core CPUs
• compact data structure with cache-efficient memory layout [3] which makes BK notably faster and memory efficient

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:

• 2D grids with 4-connected and 8-connected neighborhoods
• 3D grids with 6-connected and 26-connected neighborhoods

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.