GraphCutOptimization

https://vision.cs.uwaterloo.ca/code/, section "Multi-label optimization" (gco-v3.0 library)

Code with my fixes (commit d7477e9): https://github.com/LIHPC-Computational-Geometry/validity-first-polycube-labeling/tree/main/ext/GraphCutOptimization

Also take a look at what Marco Livesu did: https://github.com/mlivesu/GraphCuts

Note

Their README mentions the US patent forbidding commercial use:

This software can be used only for research purposes. For commercial purposes, be aware that there is a US patent on the main algorithm itself: R. Zabih, Y. Boykov, O. Veksler, "System and method for fast approximate energy minimization via graph cuts", United Stated Patent 6,744,923, June 1, 2004

On Google Patents, US6744923 is marked as expired, since 2022-03-07.

Problem formulation

In the most general case (see GeneralGraph_DArraySArraySpatVarying() in their example.cpp), given a set of connected sites and a set of labels, the problem is to assign a label to each site, depending on:

the data cost, the cost of assigning each site to each label
the smooth cost, the adjacency cost of pairs of labels
the neighborhood cost, the proximity of two sites, encouraging the same label for both or not