Bernhard Schmitzer -> Publications

(UnbalancedScaling'16) Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, François-Xavier Vialard: Scaling Algorithms for Unbalanced Transport Problems, (2016) [arxiv]

A family of scaling algorithms for entropy regularized transport-type problems is introduced, that generalize the well-known Sinkhorn algorithm for standard optimal transport. Applications involve unbalanced transport problems (in a formulation given by [Liero, Mielke, Savaré], related to the formulation given in (OT-FR'15-2)), JKO-type gradient flow schemes and (unbalanced) barycenters. The article provides an analysis of the algorithms in a continuous setting, comments on practical implementation for discretized problems and several numerical examples.

(ImageAssignment'16) Freddie Åström, Stefania Petra, Bernhard Schmitzer, Christoph Schnörr: Image Labeling by Assignment, (2016) [arxiv]

This article introduces a non-convex framework for the image labelling problem. A (fuzzy) labelling of an image pixel is represented by a discrete probability distribution. Starting from the completely undecided fuzzy labelling, the final image labelling is obtained by following a Fisher-Rao gradient flow, where the energy is determined by the discrepancy of a pixel labelling from its local expectation (determined by the observed data) and the labels of the neighbouring pixels. The flexible mathematical formulation allows for application to rather different problems.

(EntropicOT'15) Guillaume Carlier, Vincent Duval, Gabriel Peyré, Bernhard Schmitzer: Convergence of Entropic Schemes for Optimal Transport and Gradient Flows, (2015) [arxiv]

Entropy regularization has recently been re-introduced as an efficient numerical method for approximately solving problems involving optimal transport. In this article we investigate the convergence to the unregularized problem. We show that the regularized transport functional Gamma-converges to the standard functional in the limit of vanishing regularization. Analogously, we show that the implicit time-discrete Wasserstein gradient flow scheme for non-linear diffusion, with a regularized transport functional, converges to the same PDE-limit as the unregularized scheme, if regularization decreases sufficiently fast with decreasing time-step size.

(OT-FR'15-2) Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, François-Xavier Vialard: Unbalanced Optimal Transport: Geometry and Kantorovich Formulation, (2015) [arxiv]

This draft is a direct continuation of the work in (OT-FR'15). We study the geometry of the OT-FR interpolation and in particular provide a Kantorovich-like static reformulation of the dynamic problem. Since the proof of equivalence between the two formulations hinges only on rather general properties of the functional, we generalize the results to cover a large class of dynamic extensions of optimal transport. This may be an important step in finding efficient numerical solvers to generalizations of dynamic optimal transport.

(OT-FR'15) Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, François-Xavier Vialard: An Interpolating Distance between Optimal Transport and Fisher-Rao, accepted for publication at Foundations of Computational Mathematics (2015) [arxiv]

Based on the dynamic formulation of optimal transport due to Benamou and Brenier, this paper introduces an interpolation between the classical L2 optrimal transport distance and the Fisher-Rao metric. For this a source term is added to the continuity equation which allows for generation and removal of mass. We analyze the corresponding optimization problem in the context of convex optimization and study in particular geodesics between Dirac measures. Finally, a numerical scheme is presented and some examples illustrate the usefulness of this particular growth term for image interpolation.

(ShortCuts'16) Bernhard Schmitzer: A Sparse Multi-Scale Algorithm for Dense Optimal Transport, Journal of Mathematical Imaging and Vision, Online First (2016) [web] [arxiv]

This is an extension of (SSVM'15). Analogous to continuous optimal transport, a framework for locally verifying global optimality of a given coupling is developed, leveraging the geometric structure of the underlying cost function. This leads to a sparse multi-scale algorithm for large dense problems. Various cost functions (including the squared Euclidean distance and the squared geodesic distance on the sphere) and noisy variants thereof are detailed explicitly. Numerical experiments demonstrate a substantial decrease in memory requirements and a speed-up of around two orders of magnitude compared to the naive dense approach.
New: Code available

(WassersteinModes'15) Bernhard Schmitzer, Christoph Schnörr: Globally Optimal Joint Image Segmentation and Shape Matching based on Wasserstein Modes, Journal of Mathematical Imaging and Vision 52 (3): 436-458 (2015) [pdf] [web] [arxiv]

This is a more detailed analysis of the ideas developed in (EMMCVPR'13) for object segmentation and matching with a prototype template. Based on the relation developed in (ShapeMeasures'13) we use contour-based statistical learning methods to obtain a set of non-isometric Wasserstein modes to describe typical deformations of the template. Locally adaptive appearance models are studied and different optimization schemes are discussed in detail.

(JMIV'12) Bernhard Schmitzer, Christoph Schnörr: Modelling convex shape priors and matching based on the Gromov-Wasserstein distance, Journal of Mathematical Imaging and Vision 46 (1): 143-159 (2012) [pdf] [web]

Representing shapes by so called metric measure-spaces (mm-spaces) and comparing them by the Gromov-Wasserstein distance has proven to be an elegant way to overcome issues like reparametrization ambiguity and to abstract from transformations that a shape can undergo while still remaining basically the same shape. However the involved optimization problems are highly non-convex. In this paper we present a series of suitable approximations to the Gromov-Wasserstein functional and arrive at a modified linear optimal transport problem for finding a registration between a given shape template and its most probable instance within the query image. To our knowledge this is the first time that a shape prior functional is presented, that is both convex and invariant under various geometric transformations.

(SSVM'15) Bernhard Schmitzer: A sparse algorithm for dense optimal transport, Proceedings of the 5th International Conference on Scale Space and Variational Methods in Computer Vision (2015) [pdf] [web]

This is a continuation of the work started in (SSVM'13) to develop sparse algorithms for solving dense discrete optimal transport problems. In (SSVM'13) the structure of the cost function is only exploited implicitly, hoping that only few hierarchical consistency checks are necessary. Here on the other hand, the structure is explicitly used, resulting in `truely' sparse algorithms. Compared to (SSVM'13) this approach is less flexible in terms of cost functions, but more flexible in terms of which algorithms one can accelerate, resulting in lower running-times.

(EMMCVPR'13) Bernhard Schmitzer, Christoph Schnörr: Object Segmentation by Shape Matching with Wasserstein Modes, Proceedings of the 9th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition (2013) [pdf] [web]

In (JMIV'12) we used optimal transport to compute an assignment between a reference template and its most likely counterpart in a query image. Geometric invariance was obtained by a particular cost function, computed in a pre-processing step, based on an approximation to the Gromov-Wasserstein distance. In this paper we explicitly optimize over the embeddings of the reference template into the image domain. Standard squared Euclidean distance is used as cost function, making the rich Monge theory of optimal transport applicable. Using the manifold structure of measures, equipped with optimal transport, we can describe isometries and non-isometric deformations in a unified way. Global optimality of the non-convex model is obtained via a branch and bound scheme, based on locally adaptive convex relaxations.

(SSVM'13) Bernhard Schmitzer, Christoph Schnörr: A Hierarchical Approach to Optimal Transport, Proceedings of the 4th International Conference on Scale Space and Variational Methods in Computer Vision (2013) [pdf] [web]

The linear assignment and optimal transport problem are not only important tools in our own line of research but pervade models in computer vision and machine learning. Practical problems often come with a cost function which is far from arbitrary, but in fact rather regular. Unfortunately efficient solvers that exploit the structure of cost functions are rare (except for the squared Euclidean distance, of course). In this paper we discuss an extension of the famous auction algorithm, to turn large, dense optimal transport problems into sparse subproblems, guaranteeing global optimality by a hierarchical consistency check. We observe a significant gain in performance on a wide range of test problems (in particular beyond squared Euclidean distance in real vector spaces).

(SSVM'11) Bernhard Schmitzer, Christoph Schnörr: Weakly Convex Coupling Continuous Cuts and Shape Priors, Proceedings of the 3rd International Conference on Scale Space and Variational Methods in Computer Vision (2011) [pdf] [web]

In this paper we demonstrate that enhancing binary foreground/background segmentation by the aid of a shape prior is in principle possible in a convex variational framework. Two simple shape models, both represented by Markov random fields (MRF), are considered. The segmentation problem is formulated in a convex variational way via the famous continuous cuts functional. A convex shape prior functional is obtained from the shape model through the local polytope relaxation of the underlying MRFs. The two components are coupled by a quadratic term yielding a convex overall functional which we optimize globally with a recent algorithm from convex optimization.

(ShapeMeasures'13) Bernhard Schmitzer, Christoph Schnörr: Contour Manifolds and Optimal Transport, (2013) [arxiv]

In (EMMCVPR'13) we represented shapes by measures with indicator functions as densities, using the pseudo-Riemannian structure of the Wasserstein space of measures for modelling isometries and statistical variations. In this paper we provide a mathematical study of the shape measure representation and its relation to the contour description. It turns out that both representations are equivalent in the sense that the two corresponding manifolds are diffeomorphic. We claim that this can be used to combine the usefulness of the natural linear structures on indicator functions as well as on tangent-space approximations to contour manifolds for image processing tasks.

Bernhard Schmitzer: Isometry Invariant Shape Priors for Variational Image Segmentation, Universität Heidelberg (2014) [web]

Dionigi M. T. Benincasa, Fay Dowker, Bernhard Schmitzer: The Random Discrete Action for 2-Dimensional Spacetime, Class. Quantum Grav. 28 105018 (2011) [web] [arxiv]

Bernhard Schmitzer, Wolfgang Kinzel, Ido Kanter: Pulses of chaos synchronization in coupled map chains with delayed transmission, Phys. Rev. E 80, 047203 (2009) [web]