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 / 168 Views

DOWNLOAD

REPORT


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.