Invited talk by Dr. Paul Swoboda (IST Austria):
Message Passing for the Multicut Problem
Abstract. Convergent reweighted message passing belongs to the most efficient techniques for MAP inference in discrete graphical models. Exemplary solvers include TRW-S, SRMP and MPLP. Unfortunately, until now these techniques were restricted to standard low-arity graphical models. We present an efficient generalization enabling convergent message passing for the multicut problem. Comparison against state of the art shows significant improvement against cutting plane algorithms employing off the shelf LP-solvers for the multicut problem. We discuss generalizations and present initial computational results.
Invited talk by Emanuel Laude (TU Munich):
Sublabel Accurate Relaxation of Nonconvex Energies arising in Computer Vision Problems
Abstract. We propose a novel spatially continuous framework for convex relaxations based on functional lifting. Our method can be interpreted as a sublabel-accurate solution to multilabel problems. We show that previously proposed functional lifting methods optimize an energy which is linear between two labels and hence require (often infinitely) many labels for a faithful approximation. In contrast, the proposed formulation is based on a piecewise convex approximation and therefore needs far fewer labels. In comparison to recent MRF-based approaches, our method is formulated in a spatially continuous setting and shows less grid bias. Moreover, in a local sense, our formulation is the tightest possible convex relaxation. It is easy to implement and allows an efficient primal-dual optimization on GPUs. We show the effectiveness of our approach on several computer vision problems.
T. Möllenhoff, E. Laude, M. Moeller, J. Lellmann and D. Cremers.
Sublabel-Accurate Relaxation of Nonconvex Energies.
Int. Conf. on Computer Vision and Pattern Recognition (CVPR) 2016
Invited talk by Jan-Hendrik Lange (TU Darmstadt):
Integrality Aspects of Compressed Sensing
Abstract. Compressed Sensing is concerned with the reconstruction of inherently sparse signals from a small number of linear measurements. The associated sparse recovery problem is NP-hard in general. However, under certain conditions on the sensing matrix and the signal vector, this problem becomes efficiently solvable. In this talk, we discuss the impact of additional integrality assumptions on the signal. In particular, we inspect whether they allow for relaxing the recovery conditions.
Invited talk by Dr. Nicolas Bonneel (CNRS Lyon):
Mass Transport Principles for Computer Graphics
Abstract. Mass transportation theory studies a distance between probability distributions which can be understood as the minimum energy required to move a pile of sand representing the first distribution to a pile of sand representing the second distribution. This metric is known in differential geometry as the Wasserstein metric. In this talk, I will introduce the Wasserstein space briefly and otherwise concentrate on applications in computer graphics, in particular, color transformations in video via a curvature-flow method. Toward these applications, I will present an efficient approximation of the Wasserstein barycenter of probability measures using one-dimensional projections.
References. N. Bonneel, J. Rabin, G. Peyré and H. Pfister. Sliced and Radon Wasserstein Barycenters of Measures. Journal of Mathematical Imaging and Vision. 2015
|2014-02-21||Invited talk by Dr. Thorsten Bonato (U Heidelberg):
Lifting and Separation Procedures for the Cut Polytope
Abstract. The max-cut problem and the associated cut polytope on complete graphs have been extensively studied over the last 25 years. However, little research has been conducted for the cut polytope on arbitrary graphs. In this talk we present a new approach for generating valid, and sometimes facet defining, inequalities for the cut polytope on such graphs. Using specific graph transformations in combination with the subsequent projection and lifting of the separated inequalities, we are able to exploit algorithmic and structural results known for the cut polytope on complete graphs. Moreover, the graph transformations provide an efficient heuristic for separating so-called odd-cycle inequalities. Finally, we report some interesting computational results on a set of well-established benchmark problems.
References. T. Bonato, M. Jünger, G. Reinelt and G. Rinaldi. Lifting and Separation Procedures for the Cut Polytope. Mathematical Programming A. 2013