Sublabel-Accurate Convex Relaxation of Vectorial Multilabel Energies
Convex relaxations of multilabel problems have been demonstrated to produce provably optimal or near-optimal solutions to a variety of computer vision problems. Yet, they are of limited practical use as they require a fine discretization of the label spac
- PDF / 2,681,706 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 4 Downloads / 205 Views
echnical University of Munich, Munich, Germany [email protected] 2 University of L¨ ubeck, L¨ ubeck, Germany
Abstract. Convex relaxations of multilabel problems have been demonstrated to produce provably optimal or near-optimal solutions to a variety of computer vision problems. Yet, they are of limited practical use as they require a fine discretization of the label space, entailing a huge demand in memory and runtime. In this work, we propose the first sublabel accurate convex relaxation for vectorial multilabel problems. Our key idea is to approximate the dataterm in a piecewise convex (rather than piecewise linear) manner. As a result we have a more faithful approximation of the original cost function that provides a meaningful interpretation for fractional solutions of the relaxed convex problem. Keywords: Convex relaxation
1
· Optimization · Variational methods
Introduction
1.1
Nonconvex Vectorial Problems
In this paper, we derive a sublabel-accurate convex relaxation for vectorial optimization problems of the form min ρ x, u(x) dx + λ T V (u), (1) u:Ω→Γ
Ω
where Ω ⊂ R , Γ ⊂ R and ρ : Ω × Γ → R denotes a generally nonconvex pointwise dataterm. As regularization we focus on the total variation defined as: u, Div q dx, (2) T V (u) = sup d
n
q∈Cc∞ (Ω,Rn×d ),q(x)S ∞ ≤1
Ω
E. Laude and T. M¨ ollenhoff—These authors contributed equally. Technical University of Munich—This work was supported by the ERC Starting Grant “Convex Vision”. Electronic supplementary material The online version of this chapter (doi:10. 1007/978-3-319-46448-0 37) contains supplementary material, which is available to authorized users. c Springer International Publishing AG 2016 B. Leibe et al. (Eds.): ECCV 2016, Part I, LNCS 9905, pp. 614–627, 2016. DOI: 10.1007/978-3-319-46448-0 37
Sublabel-Accurate Convex Relaxation of Vectorial Multilabel Energies
615
where · S ∞ is the Schatten-∞ norm on Rn×d , i.e., the largest singular value. For differentiable functions u we can integrate (2) by parts to find ∇u(x)S 1 dx, (3) T V (u) = Ω
where the dual norm · S 1 penalizes the sum of the singular values of the Jacobian, which encourages the individual components of u to jump in the same direction. This type of regularization is part of the framework of Sapiro and Ringach [19]. 1.2
Related Work
Due to its nonconvexity the optimization of (1) is challenging. For the scalar case (n = 1), Ishikawa [9] proposed a pioneering technique to obtain globally optimal solutions in a spatially discrete setting, given by the minimum s-t-cut of a graph representing the space Ω × Γ . A continuous formulation was introduced by Pock et al. [15] exhibiting several advantages such as less grid bias and parallelizability. In a series of papers [14,16], connections of the above approaches were made to the mathematical theory of cartesian currents [6] and the calibration method for the Mumford-Shah functional [1], leading to a generalization of the convex relaxation framework [15] to more general (in particular nonconvex) regularizers.
Data Loading...
