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)