Graph Cuts on Markov Random Fields
|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|
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 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)