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  featuring bidirectional search for augmenting paths and tree-reuse mechanism. In addition to that it implements two key improvements:
- adaptive bottom-up merging  which allows parallel processing and thus additional speed-up on multi-core CPUs
- compact data structure with cache-efficient memory layout  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.
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.
|||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.
|||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.
|||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.