Next Generation Multicuts for Semi-Planar Graphs

arXiv:1511.01994v1 [] 6 Nov 2015

Julian Yarkony
Experian Data Lab

Abstract
We study the problem of multicut segmentation. We introduce modified versions
of the Semi-PlanarCC based on bounding Lagrange multipliers. We apply our
work to natural image segmentation.

1

Introduction

In this work, we formulate image segmentation from the perspective of constructing a multicut [9]
over the set of image pixels/superpixels [13] that agrees closely with an input set of noisy pairwise
affinities. A multicut is a partition of a graph into an arbitrary number of connected components.
However the number of components is not a user defined hyper-parameter that must be hand tuned
but arises naturally as a function of the noisy pairwise affinities. Finding the optimal multicut is
NP-hard even on a planar graph [4] however there has been much successful work concerning the
application of multicuts despite this fundamental difficulty [11, 5, 2]. We focus on the case where
the input affinities are specified by a planar graph augmented with a specific class of long range
interactions which [3] calls repulsive. These interactions create hard constraints that require that
given pairs of non-adjacent nodes be in separate components.
Consider a planar graph G that is defined by a set of edges E and a set of nodes V . We index E
using e or ê. We refer to the nodes connected by an edge e as e1 and e2 respectively. We define
a partitioning (also called a multicut) of G into an arbitrary number of components using a vector
X̄ ∈ {0, 1}|E| and index X̄ using e. We use X̄e = 1 to indicate that the two nodes e1 and e2 are in
separate components and use X̄e = 0 otherwise. For short hand we refer to an edge e as “cut” if e1
and e2 are in separate components and otherwise refer to e as “uncut”.
We denote the set of X̄ that define a multicut using M CU T . We define M CU T using the following
notation. Let C denote the set of all cycles in G and index C with c. An element c ∈ C is itself
a set where its elements are the edges on the cycle c. We use c − ê to refer to the set of edges
in cycle c excluding edge ê. We express M CU T in terms of constraints as follows [1][2]. For
every cut edge ê and for every cycle c containing ê there must be a cut edge in addition to ê on the
cycle. Constraints of this form are
P called “cycle inequalities”. We formally describe M CU T below.
M CU T = {X̄ ∈ {0, 1}|E| :
e∈c−ê X̄e ≥ X̄ê ∀c ∈ C, ê ∈ c}
The LP relaxation of M CU T to the range [0,1] is denoted CY C. Multicuts are associated with a
cost using a real valued problem instance specific vector θ ∈ R|E| . We use the dot product of θ and
X or X̄ to define the cost of a multicut X or X̄. The objectives that are minimized over M CU T
and CY C respectively are minX̄∈M CU T θX̄ and minX∈CY C θX .

2

An Alternative Representation of Multicut: The Cut Cone

We represent multicuts in a different manner using the method of [17] which we now discuss. We
refer to the set of 2-colorable multicuts of G as C2 and index it with r. We use a matrix Z to
represent C2 where Z ∈ {0, 1}|E|×|C2 | . We use Zer = 1 to indicate that edge e is cut in multicut
r. Similarly Zer = 0 indicates that edge e is not cut in multicut r. We define γ to be a non-negative
1

real valued vector with cardinality |C2 | which we use to express a multicut. We use (Zγ)e to refer
to the value of Zγ for edge e. In [17] the following properties of Zγ are established.
M CU T = {Zγ; γ ≥ 0, (Zγ)e ∈ {0, 1}

∀e}

CY C = {Zγ; γ ≥ 0, (Zγ)e ∈ [0, 1] ∀e}
(1)

The cut cone is associated with an extension of the cut cone called the expanded cut cone [17] which
only restricts γ to be non-negative. The expanded cut cone is associated with a slack term β which
is used to provide a penalty for cutting edges more than once. That penalty is − min(0, θ), denoted
−θ− , is of cardinality |E| and is indexed by e. Here θe− = min(0, θe ). We write optimization over
the expanded cut cone below.
min θZγ − θ− β
γ≥0
β≥0

s.t.

Zγ − 1 ≤ β

(2)

It is established that the introduction of β does not alter the value of the LP relaxation [17]. We use
min(1, Zγ) to refer to the element-wise minimum of 1 and Zγ. In [17] it is established that given
any solution γ that X = min(Zγ, 1) lies in CY C, Furthermore if X = min(Zγ, 1) ∈ {0, 1}|E|
then X ∈ M CU T . The expanded cut cone is useful in the setting in which we are unable to access
the full set of columns of Z. This additional flexibility allows for the application of efficient delayed
column generation algorithms [17, 18].
We now present our novel contribution. Consider a set of pairs of nodes in G denoted F which is
indexed by f . The nodes on pair f are denoted f1 and f2 and need not be adjacent in G. We require
that for each f that f1 and f2 are in separate components in any multicut. We refer to the set of all
paths between pairs in F as P and index it with p. Here each p is defined by a connected path of
edges in G. Each path p is associated with a pair f in F and the first and last nodes on the path
are f1 and f2 respectively. We now write a constrained optimization over the expanded cut cone to
enforce that pairs in F are in separate components.
min θZγ − θβ
γ≥0
β≥0

s.t.

Zγ − 1 ≤ β

X
(Zγ)e ≥ 1 ∀p ∈ P

(3)

e∈p

Inspired by the slack terms
P used in [17] which the authors denote α we introduce a set of slack terms
to assist in satisfying e∈p (Zγ)e ≥ 1. We allow any edge to be cut more than as described in Zγ
|E|

but at a cost. We denote the cost vector as θ+ ∈ R0+ where θe+ = max(0, θe ). We indicate the slack
|E|
term for cutting edges as κ ∈ R0+ . For notational ease we introduce a matrix S ∈ {0, 1}|P |×|E| .
Here S has one row for each path p ∈ P and is indexed by pe. Here Spe = 1 if and only if edge e is
on the path p. We write the modified LP below.
min

γ≥0,β≥0,κ≥0

θZγ − θβ + θ+ κ ;

Zγ − 1 ≤ β

;

SZγ + Sκ ≥ 1

(4)

We use X = min(1, Zγ + κ) to denote the element wise minimum of [1, Zγ + κ]. In Section B we
show that X = min(1, Zγ + κ) ∈ CY C for all optimizing solutions to the LP in Eq 4.

3

Dual Formulation

Solving the primal problem in Eq 4 is challenging because of the exponential number of primal
constraints and primal variables. Past work has employed cutting plane methods in the dual. Thus
we analyze the dual form of this objective which we write below using T to denote transpose.
max −1T λT + 1T ψ T
λ≥0
ψ≥0

s.t.

Z T θT ≥ Z T S T ψ T − Z T λT

;

θ+T ≥ S T ψ T

;

−θ−T ≥ λT
(5)

2

We rely on a column generation and cutting plane methods jointly to construct a sufficient subset
of the columns of S and Z so as to fully optimize the objective. We denote these subsets as Ŝ and
Ẑ. Observe that the introduction of β and κ results in bounds on the Lagrange multipliers λ and
ψ. We observe in experiments that without these bounds the optimization fails to converge on most
problems.
Observe that Z T θT ≥ Z T S T ψ T − Z T λT is defined on the planar graph G. We write the most
violated constraint of that form as the solution as to the following objective: minz∈C2 (λ+θ −ψ Ŝ)z.
Finding the lowest cost 2-colorable multicut of a planar graph is solvable in O(|E|3/2 log |E|) time
[14, 18, 6, 7, 8, 10]. In practice after computing z, all cuts isolating a component are added to Ẑ.
Naively finding violated primal constraints can be done by studying the solution to the primal problem. First we obtain the primal solution from the LP solver after solving the dual. We then find
violated paths in the primal solution X = min(1, Ẑγ + κ) via shortest path calculation [1] between
nodes in each pair f ∈ F .
3.1

Finding Better Primal Constraints via Path Pursuit

Inspired by the cycle pursuit approach of [16, 15] we introduce an approach that we call “path
pursuit” designed to find paths that increase the dual objective as quickly as possible. We apply the
approximation that all paths cross a 2-colorable multicut cut no more than once. We now consider a
set of slack variables ν of cardinality |E| which is indexed by e and defined as follows.
νe = min[θe+ − (S T ψ T )e ,

min

(Ẑ:r )T θT − (Ẑ:r )T S T ψ T + (Ẑ:r )T λT ]

(6)

r; s.t. Ẑer =1

Consider any path p. We can increase ψp greedily by the smallest νe on the path without violating
identified constraints. Finding the path that maximizes the minimum slack is called the widest path
problem which solvable in time equal to shortest path calculation. Once this path is identified we
set ψp to the maximum value allowed given that all other dual variables are fixed. If no path of non
zero width exists then we use the naive approach. We now formalize our approach in Algorithm 1.
Algorithm 1 Dual Optimization
Ŝ ← {}, Ẑ ← {}
while Violated constraints exist do
[λ, ψ, γ, κ] ← Solve Eq 4, 5 given Ẑ, Ŝ
z ← minz∈C2 (θ + λ + ψ Ŝ)z {z1 , z2 . . .} ← isocuts(z) Ẑ ← Ẑ ∪ {z1 , z2 . . .}
for f ∈ F do
if there exists a violated path for pair f1 ,f2 then
Compute a row p and add it to Ŝ for pair f using either widest and/or shortest path
calculation. Widest path calculation allows for multiple rows to be computed
end if
end for
end while
If widest path computation is used we refer to the algorithm as Alg 1 and otherwise as Alg 2.
3.2

Computing Upper and Lower Bounds

At any time one can identify an upper bound on the optimal multicut. First one produces an X =
min(Ẑγ +κ). This is obtained for “free” because the CPLEX LP solver provides the primal solution
γ, β, κ whenever it solves for λ, ψ. Next for unique value µ in X set X̄ ← X ≥ µ. Then uncut all
edges in the middle of a component. Next check for all f ∈ F that f1 , f2 are in separate components.
If this is satisfied compute the value θX̄ and retain the solution X̄ if it is the lowest value solution
computed so far. In practice we only use a few values of µ such as {0.2, 0.4, 0.6, 0.8}
In Section A we establish that at any time a lower bound on the optimal integer solution is equal to
the value of the LP plus 23 times the the value of minz∈C2 (θ + λ + ψ Ŝ)z.
3

Figure 1: Top: We display the relative speed of convergence of our two novel algorithms. We show
as a function of time the proportion of problem instances that are not solved up to GAP =2−3,−5,−7
from left to right. (Blue) represents Alg 1 while (red) represents Alg 2. Timing experiments are
ongoing but thousands of data points define these plots. Bottom: We show qualitative outputs of
Alg 1. Each group corresponds to a particular image. We show segmentations of increasing fineness
from left to right with different numbers of random ground truth long range interactions inserted;
[28,58,508] from top to bottom .

4

Experiments

We evaluate our two algorithms on the Berkeley segmentation data set (BSDS)[12]. For each image
in the BSDS test set we are provided with superpixels, and potentials θ defined between adjacent
superpixels by the authors of [18]. For each image we then select a number of random pairs of
superpixels that are in separate components according to at least two ground truth annotators. We
constructed examples with [28, 58, 208, 308, 408, 508] pairs. For a baseline we employed the original Semi-PlanarCC algorithm of [3] but it does not converge on most of our problems so we did not
plot it. This is interesting because the major difference between our algorithm with naive addition
of constraints (not widest path calculation) is simply the introduction of κ which thus establishes the
value of the κ term.
Hence we simply compare our two approaches and demonstrate that our algorithms are able to solve
the problems in our data set. We demonstrate the convergence of the upper bound as a function of
time in Fig 1. For each algorithm we produce as a function of time the proportion of the problems
that algorithm has solved up to a satisfactory level. This level is computed as follows. We first
compute the maximum lower bound between the two algorithms for a given problem which we
denote as LB. We denote the least upper bound produced as a function of time as U B(t) . We
. We show
create a measure called the normalized gap which we define as GAP (t) = (U B(t)−LB)
|LB|
rapid convergence and that widest path computation helps improve performance.
We now study some qualitative results from Alg 1 on various problems. For any given problem
instance we produce the lowest cost multicut during optimization. Next for each component in the
multicut we compute the mean color of the pixels in that component and color each pixel in the component with that color. Results are displayed in Fig 1. We observe large qualitative improvements
in the results. However when smaller numbers of pairs are used we also often see tiny components
created. However these often disappear and better boundaries emerge as more pairs are used.

References
[1] B. Andres, J. H. Kappes, T. Beier, U. Kothe, and F. A. Hamprecht. Probabilistic image segmentation
with closedness constraints. In Proceedings of the Fifth International Conference on Computer Vision
(ICCV-11), pages 2611–2618, 2011.

4

[2] B. Andres, T. Kroger, K. L. Briggman, W. Denk, N. Korogod, G. Knott, U. Kothe, and F. A. Hamprecht.
Globally optimal closed-surface segmentation for connectomics. In Proceedings of the Twelveth International Conference on Computer Vision (ECCV-12), 2012.
[3] B. Andres, J. Yarkony, B. S. Manjunath, S. Kirchhoff, E. Turetken, C. Fowlkes, and H. Pfister. Segmenting
planar superpixel adjacency graphs w.r.t. non-planar superpixel affinity graphs. In Proceedings of the
Ninth Conference on Energy Minimization in Computer Vision and Pattern Recognition (EMMCVPR-13),
2013.
[4] Y. Bachrach, P. Kohli, V. Kolmogorov, and M. Zadimoghaddam. Optimal coalition structures in graph
games. CoRR, abs/1108.5248, 2011.
[5] S. Bagon and M. Galun. Large scale correlation clustering. In CoRR, abs/1112.2903, 2011.
[6] F. Barahona. On the computational complexity of ising spin glass models. Journal of Physics A: Mathematical, Nuclear and General, 15(10):3241–3253, april 1982.
[7] F. Barahona. On cuts and matchings in planar graphs. Mathematical Programming, 36(2):53–68, november 1991.
[8] F. Barahona and A. Mahjoub. On the cut polytope. Mathematical Programming, 60(1-3):157–173,
September 1986.
[9] M. Deza and M. Laurent. Geometry of cuts and metrics, volume 15. Springer Science & Business Media,
1997.
[10] M. E. Fisher. On the dimer solution of planar ising models. Journal of Mathematical Physics, 7(10):1776–
1781, 1966.
[11] S. Kim, S. Nowozin, P. Kohli, and C. D. Yoo. Higher-order correlation clustering for image segmentation.
In Advances in Neural Information Processing Systems,25, pages 1530–1538, 2011.
[12] D. Martin, C. Fowlkes, D. Tal, and J. Malik. A database of human segmented natural images and its
application to evaluating segmentation algorithms and measuring ecological statistics. In Proceedings of
the Eighth International Conference on Computer Vision (ICCV-01), pages 416–423, 2001.
[13] X. Ren and J. Malik. Learning a classification model for segmentation. In Ninth IEEE International
Conference on Computer Vision and Pattern Recognition (CVPR 2003), pages 10–17 vol.1, Oct 2003.
[14] W.-K. Shih, S. Wu, and Y. Kuo. Unifying maximum cut and minimum cut of a planar graph. Computers,
IEEE Transactions on, 39(5):694–697, May 1990.
[15] D. Sontag, D. K. Choe, and Y. Li. Efficiently searching for frustrated cycles in MAP inference. In
Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence (UAI-12), pages
795–804, Corvallis, Oregon, 2012. AUAI Press.
[16] D. Sontag, T. Meltzer, A. Globerson, T. Jaakkola, and Y. Weiss. Tightening lp relaxations for map using
message passing. In Proceedings of the Twenty-Fourth Conference Annual Conference on Uncertainty in
Artificial Intelligence (UAI-08), pages 503–510, july 2008.
[17] J. Yarkony and C. Fowlkes. Planar ultrametrics for image segmentation. In Neural Information Processing
Systems, 2015.
[18] J. Yarkony, A. Ihler, and C. Fowlkes. Fast planar correlation clustering for image segmentation. In
Proceedings of the 12th European Conference on Computer Vision(ECCV 2012), 2012.

A

Computing Any Time Lower Bounds

In this section we construct a lower bound on the value of the optimal integer multicut that obeys all
of the path inequalities. This lower bound is a function of λ and ψ. Let KM CU T denote the set
of integer multicuts that obey all path inequalities. We use X k to denote a member of this set. We
write KM CU T formally below, along with the optimization over KM CU T .
KM CU T = {X k ∈ M CU T : SX k ≥ 1}

(7)

k

(8)

min

X k ∈KM CU T

θX

We now insert Lagrange multipliers corresponding to the constraints in the primal objective in Eq 5.
Eq 8 =

min

max θX k + λ(X k − 1) + ψ(1 − SX k )

X k ∈KM CU T ψ≥0
λ≥0

(9)

Observe that since X k must lie in KMCUT these multipliers have their global optimum at zero
value. Let any particular setting of ψ, λ be chosen and denoted ψ̂,λ̂. Notice that this produces a
lower bound on the true objective written below.
5

Eq 9 ≥

min

X k ∈KM CU T

θX k + λ̂(X k − 1) + ψ̂(1 − SX k )

(10)

We now relax the constraint that the solution lie in KM CU T to instead lie in the expanded space
M CU T .
Eq 10 ≥

min

θX̄ + λ̂(X̄ − 1) + ψ̂(1 − X̄)

X̄∈M CU T

=

min

−λ1 + ψ̂1 + (θ + λ̂ − ψS)X̄

X̄∈M CU T

= −λ̂1 + ψ̂1 +

min

(θ + λ̂ − ψS)X̄

(11)

X̄∈M CU T

Solving for minX̄∈M CU T (θ + λ̂ − ψS) is exactly Planar Correlation Clustering which is known to
be NP hard [4]. However [18] establishes that the 32 times the value of the minimum 2-colorable
multicut lower bounds the value of the optimal multicut. We use this fact to construct a lower bound
on Eq 11 below.

Eq 11 ≥ −λ̂1 + ψ̂1 +

3
min (θ + λ̂ − ψS)z
2 z∈C2

(12)

Since computing the minimum 2-colorable multicut is solvable in O(N 3/2 log N ) we can produce
a lower bound on the true objective given any setting of λ̂ and ψ̂ which is written below.
3
Eq 8 ≥ −λ̂1 + ψ̂1 + min (θ + λ̂ − ψS)z
∀ [λ̂ ≥ 0, ψ̂ ≥ 0]
(13)
2 z∈C2
Observe that at convergence of Alg 1,2 the value of minz∈C2 (θ + λ̂ − ψS)z = 0 and hence the value
of the lower bound is exactly equal to that of the LP relaxation in Eq 5. During Alg1,2 we are able
to produce a lower bound on our objective each time the dual LP solver produces a new setting of
λ, ψ.

B

Proof Cut

We now establish that at termination of Alg 1,2 min(1, Ẑγ + κ) lies in CY C. First observe that
given Ẑγ from Alg 1,2 we can greedily decrease values in κ, β until each κe and βe is a term in a
tight constraint or is zero valued. This operation only effects terms associated with zero value in the
primal objective.
We use these reduced κ and β terms in the remainder of the proof. We call property that each κ and
β term is involved in a tight constraint or is zero valued P rop1.
To establish that min(1, Ẑγ + κ) ∈ CY C we must establish the following for all cycles c and edges
ê in c.
X

min(1, (Ẑγ)e + κe ) ≥ min(1, (Ẑγ)e + κe )

(14)

e∈c−ê

On any cycle inequality we refer to the edge on the right side of the inequality as the pivot edge.
For short hand we use Q to refer to the set of all pairs of cycle and edge contained in the cycle.
A member of Q is written as [c, ê] which denotes the cycle and pivot edge. We associate Q with
non-overlapping subsets Q+ and Q0 whose union is Q. An element of Q denoted [c, ê] is in Q+ if
and only if κê > 0.
We now establish that all cycle inequalities are obeyed by first considering an cycle inequalities in
Q0 and then in Q+ .
6

B.1

For [c, ê] ∈ Q0

To establish that the cycle inequality associated with every pair [c, ê] ∈ Q0 we use proof by contradiction. Consider a violated cycle inequality over pair [c, ê] ∈ Q0 . We write this below.
X

min(1, (Ẑγ)e + κe ) < min(1, (Ẑγ)ê + κê )

(15)

e∈c−ê

Since [c, ê] ∈ Q0 then κê = 0. Therefore we write Eq 15 without κê .
X

min(1, (Ẑγ)e + κe ) < min(1, (Ẑγ)ê )

(16)

e∈c−ê

Recall that [17] establishes that min(1, Ẑγ) ∈ CY C for all γ thus the following is true.
X

min(1, (Ẑγ)e ) ≥ min(1, (Ẑγ)ê )

(17)

e∈c−ê

Since κ is non-negative then the following is true which establishes a contradiction with Eq 16.
X

X

min(1, (Ẑγ)e + κe ) ≥

e∈c−ê

min(1, (Ẑγ)e ) ≥ (Ẑγ)ê

(18)

e∈c−ê

Therefor the cycle inequalities over members of Q0 are satisfied.
B.2

For [c, ê] ∈ Q+

To establish that the cycle inequality associated with every pair [c, ê] ∈ Q+ is satisfied we use proof
by contradiction. Consider a violated cycle inequality over pair [c, ê] ∈ Q+ . We write this below.
X

min(1, (Ẑγ)e + κe ) < min(1, (Ẑγ)ê + κê )

(19)

e∈ĉ−ê

Observe that (Ẑγ)ê + κê ≤ 1 otherwise κê would cause a violation of P rop1. We now alter Eq 19
based on the observation that (Ẑγ)ê + κê ≤ 1.
X

(Ẑγ)e + κe < (Ẑγ)ê + κê

(20)

e∈ĉ−ê

Clearly there must be a path inequality including edge ê that is tight otherwise P ROP 1 is violated.
Denote this path as p and let it connect pair (f1 , f2 ) ∈ F . We now write the expression for that path
inequality and alter it.
X
min[1, (Zγ + κ)e ] = 1
(21)
e∈p

= min[1, (Zγ + κ)ê ] +

X

min[1, (Zγ + κ)e ] = 1

e∈p−ê

= (Zγ)ê + κê +

X

min[1, (Zγ + κ)e ] = 1

e∈p−ê

= (Zγ)ê + κê +

X
e∈p−ê

7

(Zγ)e + κe = 1

(22)

We now substitute the left hand side of Eq 20 for (Ẑγ)ê + κê in Eq 22.

1 = (Zγ)ê + κê +

X

(Zγ)e + κe >

e∈p−ê

X

(Ẑγ)e + κe +

e∈ĉ−ê

X

(Zγ)e + κe

(23)

e∈p−ê

Observe that the union of ĉ and p − ê is itself a path between a pair f1 , f2 ∈ F though one which
may include edges multiple times. We denote this path as p̄. Now observe the following.
X
1 = (Zγ)ê + κê +
(Zγ)e + κe
(24)
e∈p−ê

>

X

(Ẑγ)e + κe +

e∈ĉ−ê

X

(Zγ)e + κe

e∈p−ê

≥

X
(Zγ)e + κe
e∈p̄

However since path p̄ connects a pair f1 , f2 ∈ F then the sum of the edges on the path must be
greater than or equal to one. Thus we have established a contradiction and therefore the pair ê, c is
not associated with a violated cycle inequality.
B.3

Conclusion

Since every pair [c, ê] ∈ Q+ ∪Q0 the associated cycle inequality is satisfied then all cycle inequalities
are satisfied and thus min(1, Ẑγ + κ) ∈ CY C.

8

