Graph Cuts on Markov Random Fields
| Binary | Multi-label | |
|---|---|---|
| Submodular | Exact polynomial-time solution via min-cut/max-flow | Exact polynomial-time solution via min-cut/max-flow |
| Metric | N/A | NP-hard, polynomial-time alpha-expansion reaches local-min within a factor of 2 of global min |
| Neither | NP-hard, polynomial-time quadratic pseudo-boolean optimization can produce an exact partial solution | NP-hard, polynomial-time alpha-beta swap reaches local-min |
Submodularity
Binary submodular cost functions satisfy:
Cost(a,b) + Cost(b,a) - Cost(a,a) - Cost(b,b) >= 0
Multi-label submodular cost functions satisfy:
Cost(b,c) + Cost(a,d) - Cost(b,d) - Cost(a,c) >= 0, where b > a and d > c
From a set theory perspective, a cost function is submodular if adding an element x to set S incurs a cost increase α, which is less than or equal to the cost increase β incurred by adding element x to set T, where T is any subset of S. In other words, submodularity implies a diminishing-costs effect.
Convex cost functions (where smoothness is preferred and larger label differences have larger costs) are a common class of submodular costs.
Metric costs
Metric cost functions satisfy the following criteria:
Cost(a,a) = 0
Cost(a,b) > 0
Cost(a,b) = Cost(b,a)
Cost(a,c) <= Cost(a,b) + Cost(b,c)