Bernhard Schmitzer -> Publications

(SemiDiscreteUnbalanced'18) David P. Bourne, Bernhard Schmitzer, Benedikt Wirth: Semi-discrete unbalanced optimal transport and quantization, (2018) [arxiv] [details]

We combine the concepts of semi-discrete transport with unbalanced transport and generalize the `tessellation' formulations for semi-discrete classical optimal transport. The intrinsic length scale of unbalanced transport leads to interesting effects. Finally, we study the unbalanced quantization problem and its asymptotic behaviour in the limit of infinitely many points.

(GraphTransport'17) Matthias Erbar, Martin Rumpf, Bernhard Schmitzer, Stefan Simon: Computation of Optimal Transport on Discrete Metric Measure Spaces, (2017) [arxiv] [details]

On a discrete metric space the Wasserstein-2 distance does not induce a geodesic space. This implies that there is no displacement interpolation and no notion of a gradient flow. Jan Maas proposed a modified distance by modifying the Benamou--Brenier formula for discrete spaces, based on a Markov kernel. In this article we propose a consistent time-discretization of the optimization problem and a corresponding optimization scheme based on proximal splitting. This allows, for instance, to numerically simulate the heat equation with respect to the Markov kernel as a gradient flow with respect to the new distance.

(SparseScaling'16) Bernhard Schmitzer: Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems, (2016) [arxiv] [details]

This article builds on (UnbalancedScaling'16) and discusses some adaptions to the scaling algorithms for entropy regularized transport problems, for more robust and efficient numerical implementation. A log-domain stabilization and epsilon-scaling remedy diverging scaling factors and slow convergence as regularization approaches zero; adaptive truncation of the kernel and a coarse-to-fine scheme similar to (ShortCuts'16) reduce the requied memory. A new complexity analysis of the Sinkhorn algorithm, based on a comparison to the auction algorithm is developed. Numerical examples demonstrate that the modified algorithm can solve a variety of large transport-type problems with small regularization.
Code available

(UnbalancedW1'18-2) Bernhard Schmitzer, Benedikt Wirth: Dynamic Models of Wasserstein-1-Type Unbalanced Transport, to appear in ESAIM: Control, Optimisation and Calculus of Variations (2018) [arxiv] [details]

This article relates (StaticWFR'18) with (UnbalancedW1'18): static and dynamic formulations for unbalanced Wasserstein-1-type transport models are given. In particular it is shown that under suitable assumptions every dynamic model can be rewritten as a (computationally more attractive) static model. Conversely, we study which static models have a dynamic interpretation.

(UnbalancedW1'18) Bernhard Schmitzer, Benedikt Wirth: A Framework for Wasserstein-1-Type Metrics, to appear in Journal of Convex Analysis (2018) [arxiv] [details]

In (WFR'16), (StaticWFR'18) and (UnbalancedScaling'16) models for unbalanced transport were studied, where mass can be created or annihilated, with a focus on Wasserstein-2-type transport models. In this article we develop an analogous framework for the Wasserstein-1 metric. The extended models allow to combine the W-1 distance with other local similarity measures. In particular the reformulation as a min-cost flow problem is preserved, which can be solved efficiently. Numerical examples illustrate the robustness of the resulting unbalanced discrepancy measures on noisy data.

(StaticWFR'18) Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, François-Xavier Vialard: Unbalanced Optimal Transport: Dynamic and Kantorovich Formulations, to appear in Journal of Functional Analysis (2018) [arxiv] [details]

This article is a direct continuation of the work in (WFR'16). We study the geometry of the Wasserstein-Fisher-Rao 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.

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

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 (StaticWFR'18)), 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.

(EntropicOT'17) Guillaume Carlier, Vincent Duval, Gabriel Peyré, Bernhard Schmitzer: Convergence of Entropic Schemes for Optimal Transport and Gradient Flows, SIAM Journal on Mathematical Analysis 49 (2), 1385-1418 (2017) [web] [arxiv] [details]

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.

(ImageAssignment'17) Freddie Åström, Stefania Petra, Bernhard Schmitzer, Christoph Schnörr: Image Labeling by Assignment, Journal of Mathematical Imaging and Vision 58 (2), 211-238 (2017) [web] [arxiv] [details]

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.

(WFR'16) Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, François-Xavier Vialard: An Interpolating Distance between Optimal Transport and Fisher-Rao Metrics, Foundations of Computational Mathematics, Online First (2016) [web] [arxiv] [details]

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 56 (2): 238-259 (2016) [web] [arxiv] [details]

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.
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] [details]

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] [details]

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'17) Jan Henrik Fitschen, Friederike Laus, Bernhard Schmitzer: Optimal Transport for Manifold-Valued Images, Proceedings of the 6th International Conference on Scale Space and Variational Methods in Computer Vision (2017) [pdf] [web] [details]

An extension of optimal transport to non-scalar signals such as color images is constructed by lifting the original signals to non-negative measures on a higher dimensional space. It is natural to use unbalanced transport in this setting. Numerical optimization is handled with the algorithms developed in (UnbalancedScaling'16) and (SparseScaling'16). We give examples for interpolation between color images in different color spaces as well as a simple classification example on the MNIST dataset.

(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] [details]

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] [details]

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] [details]

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] [details]

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] [details]

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]