Optimality Bounds for a Variational Relaxation of the Image Partitioning Problem

Abstract

We consider a variational convex relaxation of a class of optimal partitioning and multiclass labeling problems, which has recently proven quite successful and can be seen as a continuous analogue of Linear Programming (LP) relaxation methods for finite-dimensional problems. While for the latter several optimality bounds are known, to our knowledge no such bounds exist in the infinite-dimensional setting. We provide such a bound by analyzing a probabilistic rounding method, showing that it is possible to obtain an integral solution of the original partitioning problem from a solution of the relaxed problem with an a priori upper bound on the objective. The approach has a natural interpretation as an approximate, multiclass variant of the celebrated coarea formula.

Appendix

Proof of Proposition 3

In order to prove the first assertion (88), note that the mapping w↦Ψ(νw ^⊤) is convex, therefore it must assume its maximum on the polytope Δ _l −Δ _l :={z ¹−z ²|z ¹,z ²∈Δ _l } in a vertex of the polytope. Since the polytope Δ _l −Δ _l is the difference of two polytopes, its vertex set is at most the difference of their vertex sets, V:={e ⁱ−e ^j|i,j∈{1,…,l}}. On this set, the bound Ψ(νw ^⊤)⩽λ _u holds for w∈V due to the upper-boundedness condition (25), which proves (88).

The second equality (90) follows from the fact that G:={b ^ik:=e ^k(e ⁱ−e ⁱ⁺¹)^⊤∣1⩽k⩽d,1⩽i⩽l−1} is a basis of the linear subspace W, satisfying Ψ(b ^ik)⩽λ _u , and Ψ is positively homogeneous and convex, and thus subadditive. Specifically, there is a linear transform T:W→ℝ^d×(l−1) such that w=∑ _i,k b ^ik α _ik for α=T(w). Then

(172)

(173)

(174)

Since (25) ensures Ψ(±b ^ik)⩽λ _u , we obtain

$$ \varPsi(w) \leqslant\lambda_u \sum_{i k} | \alpha_{i k} | \leqslant \lambda_u \|T\| \|w \|_2 $$

(175)

for any suitable operator norm ∥⋅∥ and any w∈W. □

Proof of Proposition 4

Denote $\mathcal{B}_{\delta} :=\mathcal{B}_{\delta}(x)$. We prove mutual inclusion:

“⊆”: From the definition of the measure-theoretic interior,

(176)

Since $|\mathcal{B}_{\delta} | \geqslant|\mathcal{B}_{\delta} \cap E| \geqslant|\mathcal{B}_{\delta} \cap E \cap F|$ (and vice versa for $|\mathcal{B}_{\delta} \cap F|$), it follows by the “sandwich” criterion that both $\lim_{\delta\searrow0} |\mathcal{B}_{\delta} \cap E| / |\mathcal{B}_{\delta} |$ and $\lim_{\delta\searrow0} |\mathcal{B}_{\delta} \cap F| / |\mathcal{B}_{\delta} |$ exist and are equal to 1, which shows x∈E ¹∩F ¹.

“⊇”: Assume that x∈E ¹∩F ¹. Then

(177)

(178)

(179)

We obtain equality,

(180)

(181)

(182)

from which we conclude that

$$ \lim_{\delta\searrow0} \sup\frac{|\mathcal{B}_{\delta} \cap E \cap F|}{|\mathcal{B}_{\delta} |} = \lim_{\delta\searrow0} \inf \frac{|\mathcal{B}_{\delta} \cap E \cap F|}{|\mathcal{B}_{\delta} |} = 1, $$

i.e., x∈(E∩F)¹. □

Proof of Proposition 5

First note that

(183)

(184)

(185)

(186)

(187)

The inequality (∗) is a consequence of the definition of $w^{\pm}_{\mathcal{F}E}$ and [2, Theorem 3.77], and (∗∗) follows directly from w(x),w(y)∈Δ _l a.e. on Ω. The upper bound (187) permits applying [2, Theorem 3.84] on w, which provides $w \in\operatorname{BV} (\varOmega)^{l}$ and (94). Due to [2, Proposition 3.61], the sets (E)⁰,(E)¹ and $\mathcal{F}E$ form a (pairwise disjoint) partition of Ω, up to an $\mathcal{H}^{d - 1}$-zero set. Therefore, since $\varPsi(D u) \ll|D u| \ll\mathcal{H}^{d - 1}$ by construction, from [2, Theorem 2.37, 3.84] we obtain, for any Borel set A,

(188)

(189)

Since w(x)∈Δ _l a.e. by assumption, we conclude that $w^{+}_{\mathcal{F}E}$ and $w^{-}_{\mathcal{F}E}$ must have values in Δ _l as well, see [2, Theorem 3.77]. Therefore we can apply Proposition 3 to obtain

(190)

(191)

(192)

We rewrite Ψ(Dw) using (94),

(193)

From [2, Proposition 2.37] we obtain that Ψ is additive on mutually singular Radon measures μ,ν, i.e., if |μ|⊥|ν|, then

(194)

for any Borel set B⊆Ω. This holds in particular for the three measures in (193), therefore

(195)

Since Du⌞(E)¹≪|Du⌞(E)¹|=|Du|⌞(E)¹, we conclude Ψ(Dw)⌞(E)¹=Ψ(Du)⌞(E)¹ and Ψ(Dw)⌞(E)⁰=Ψ(Dv)⌞(E)⁰. Substitution into (192) proves the remaining assertion,

(196)

 □

Proof of Proposition 6

We first show (98). It suffices to show that

(197)

This can be seen by considering the precise representative $\widetilde{1_{E}}$ of 1 _E [2, Definition 3.63]: Starting with the definition,

(198)

the fact that $\lim_{\delta\searrow0} \frac{| \varOmega\cap\mathcal {B}_{\delta} (x) |}{|\mathcal{B}_{\delta} (x) |} = 1$ implies

(199)

(200)

(201)

Substituting E by Ω∖E, the same equivalence shows that $x \in(E)^{0} \Leftrightarrow\widetilde{1_{\varOmega\setminus E}} (x) = 1 \Leftrightarrow\widetilde{1_{E}} (x) = 0$. As $\mathcal{L}^{d} (\varOmega \setminus((E)^{0} \cup(E)^{1})) = 0$, this shows that $1_{E^{1}} = \widetilde{1_{E}}$ $\mathcal{L}^{d}$-a.e. Using the fact that $\widetilde {1_{E}} = 1_{E}$ [2, Proposition 3.64], we conclude that $1_{(E)^{1}} = 1_{E}$ $\mathcal{L}^{d}$-a.e., which proves (197) and therefore the assertion (98).

Since the measure-theoretic interior (E)¹ is defined over $\mathcal{L}^{d}$-integrals, it is invariant under $\mathcal{L}^{d}$-negligible modifications of E. Together with (197) this implies

(202)

To show the relation (Du)⌞(E)¹=(Dv)⌞(E)¹, consider

(203)

(204)

The equality (∗) holds due to the assumption (96), and due to the fact that Df=Dg if f=g $\mathcal{L}^{d}$-a.e. (see, e.g., [2, Proposition 3.2]). We continue from (204) via

(205)

(206)

(207)

(208)

(209)

Therefore Du⌞(E)¹=Dv⌞(E)¹. Then,

(210)

(211)

In the equality (∗) we used the additivity of Ψ on mutually singular Radon measures [2, Proposition 2.37]. By definition of the total variation, |μ⌞A|=|μ|⌞A holds for any measure μ, therefore |Du⌞(Ω∖(E)¹)|=|Du|⌞(Ω∖(E)¹) and |Du⌞(Ω∖(E)¹)|((E)¹)=0, which together with (again by definition) Ψ(μ)≪|μ| implies that the second term in (211) vanishes. Since all observations equally hold for v instead of u, we conclude

(212)

(213)

(214)

Equation (97) follows immediately. □