Efficient Decomposition of Image and Mesh Graphs by Lifted Multicuts

1. Introduction

• MP solutions correspond one-to-one with graph decompositions, leave the component count to the solution, and do not favor a decomposition by definition.Source: §1 · p. 1
• For each graph edge, the MP takes a real-valued cost and outputs labels where 0 means join and 1 means cut.An example edge cost uses an estimated boundary probability and a prior probability of cuts.Source: §1 · p. 1
• Pixel-grid MP instances are difficult in practice because the MP is NP-hard and its objective cannot assign costs to separated non-neighboring pixels.The paper contrasts difficult local boundary estimates with sometimes easier estimates of whether distant pixels belong to distinct components.Source: §1 · p. 1
• The LMP extends the MP with real-valued costs for any node pair separated into distinct components while preserving a one-to-one correspondence between feasible solutions and graph decompositions.The paper notes that this objective capability had not previously been proposed.Source: §1 · p. 1
• The authors design and implement two efficient primal feasible heuristics for the MP and LMP, evaluating both on BSDS-500 images and the Princeton mesh benchmark.Source: §1 · p. 1

2. Related Work

• The MP is also known as Correlation Clustering in machine learning and theoretical computer science.Source: §2 · p. 2
• For complete graphs, the MP and LMP coincide; the HMP is more general, but equivalent instances have an impractical objective order, making HMP and LMP complementary in practice.Source: §2 · p. 2
• The authors compare their MP algorithms with the state of the art and their Kernighan-Lin extension with implementations in [4] [25].Source: §2 · p. 2
• The image experiments use boundary-detection results from, while the authors compare decomposition results quantitatively with the image-decomposition state of the art.Source: §2 · p. 2
• Prior mesh methods often use semantic-labeling unary terms, while the paper presents the first mesh decompositions based on multicuts.An earlier edge-probability method uses contour thinning and completion and snake movement as post-processing.Source: §2 · p. 2

3.1. Minimum Cost Lifted Multicut Problem

• Its feasible 0/1 labelings encode decompositions: edge labels indicate distinct components, while lifted-edge labels are constrained by paths in G.A lifted edge is labeled 0 exactly when its endpoints have a path in G whose edges are all labeled 0.Source: §3.1 · p. 2
• The LMP assigns costs to pairs in E∪F whose nodes are in distinct components, with feasible solutions corresponding one-to-one to decompositions of G.F connects non-neighboring nodes; instances also specify a cost for each edge in E∪F.Source: §3.1 · p. 2, §3.2 · p. 3

3.2. Properties

• With F empty, the LMP reduces to the MP; with F nonempty, it can assign costs to any pair in E∪F while preserving the decomposition correspondence.The solutions in the latter case are called lifted multicuts.Source: §3.2 · pp. 2–3
• For the instances considered, a cutting-plane algorithm is impractical because the number of constraints (4) is prohibitive and their facet-defining subset is unknown.The inequalities can be separated efficiently, but these two issues motivate using primal feasible heuristics.Source: §3.2 · p. 3

3.3. Probabilistic Model

• The probabilistic model extends the Bayesian Network for multicuts to estimate probabilities for non-neighboring node pairs as well as edges.The extension adds a random variable Y_f for each f∈F and constrains labelings to lifted multicuts.Source: §3.3 · p. 3
• For neighboring edges, the model uses boundary-probability estimation from image or mesh features, and maximizing its probability measure corresponds to solving an MP instance with suitable costs.The experiments build on recent boundary-estimation work.Source: §3.3 · p. 3
• For a non-neighboring pair, the experiments estimate its probability of separation using the maximum-probability path in G, which gives the largest single-path underestimate.The resulting negative log probability can be computed efficiently, for example with Dijkstra’s algorithm.Source: §3.3 · p. 3

4. Efficient Algorithms

• Both heuristics accept MP or LMP instances and maintain a graph decomposition, evaluating its objective on the graph augmented by lifted edges.KLj takes an initial decomposition and returns one with objective value no greater than the initial value.Source: §4 · p. 4

4.1. Greedy Additive Edge Contraction

• GAEC starts from singleton components and repeatedly joins neighboring components when the join most decreases the objective; its worst-case time is O(|V|^2 log |V|).It terminates when no join strictly decreases the objective.Source: §4.1 · p. 4

4.2. Kernighan-Lin Algorithm with Joins

• KLj tests node moves, creation of a new component, and component joins; its bipartition update greedily builds improving moves between neighboring components.Its implementation may temporarily allow disconnected components and estimate sequence gains incorrectly, then checks the objective difference before applying the selected sequence.Source: §4.2 · pp. 4–5

5.1. Image Decomposition

• Image experiments used 4-neighbor pixel-grid edges, varied p* from 0.05 to 0.95, and tested LMP lifting distances d* of 5, 10, and 20.Increasing d* from 5 to 10 improved VI, while increasing it to 20 brought no measurable further improvement.Source: §5.1 · p. 5, Figure 3 · p. 6
• GAEC and KLj ran in the order of 10^3 seconds per image instance, more than an order of magnitude faster than.KLj was also more than an order of magnitude faster than the KL implementation in [4] [25].Source: §5.1 · p. 5
• On images, MP solutions from GAEC gained little from local search, whereas LMP solutions from GAEC were improved effectively and efficiently by KLj.CGC exceeded 48 hours for every LMP image instance at p*=0.5.Source: §5.1 · p. 5
• LMP solutions improved by KLj were not significantly worse than the BSDS-500 image-decomposition state of the art, while MP solutions were significantly worse.For the tested image, and on average across images, the best decompositions used p*=0.5.Source: §5.1 · p. 5

5.2. Mesh Decomposition

• For mesh segmentation, a Random Forest learned edge-cut probabilities from ground truth using 28-dimensional edge features, and Alg. 2 was applied to the mesh dual graph with d*∈{60,70,80,100}.Median computation times per model were 51 seconds for lifting and 59 seconds for Alg. 2 on an Intel i7 Pentium laptop operating at 2.20 GHz.Source: §5.2 · pp. 7–8
• Mesh results were slightly better than and close to, with state-of-the-art decompositions reported for LMP.Unlike, the multicut formulation requires boundary information rather than semantic ground-truth labels.Source: §5.2 · pp. 5, 8

• LMP generalizes MP to address limitations in image and mesh segmentation applications.Source: §6 · p. 8
• In image and mesh decomposition, the solutions do not differ significantly from the state of the art.Source: §6 · p. 8
• Two efficient primal-feasible heuristics are assessed with MP and LMP on the BSDS-500 image and Princeton mesh benchmarks.Source: §6 · p. 8