Résumé

A primal-dual approach for a total variation Wasserstein flow

Métriques

105
6
571.94 Ko
 application/pdf
bitcache://43dca8ca271a83f1a2342498ab6e6b6e6689fc8e

Licence

Creative Commons Aucune (Tous droits réservés)

Sponsors

Sponsors scientifique

logo_smf_cmjn.gif

Sponsors financier

logo_gdr-mia.png
logo_inria.png
image010.png
logothales.jpg

Sponsors logistique

logo-minesparistech.jpg
logo-universite-paris-sud.jpg
logo_supelec.png
Séminaire Léon Brillouin Logo
logo_cnrs_2.jpg
logo_ircam.png
logo_imb.png
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/2552/4874</identifier><creators><creator><creatorName>Martin Benning</creatorName></creator><creator><creatorName>Luca Calatroni</creatorName></creator><creator><creatorName>Bertram Düring</creatorName></creator><creator><creatorName>Carola-Bibiane Schönlieb</creatorName></creator></creators><titles>
            <title>A primal-dual approach for a total variation Wasserstein flow</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2013</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Mon 16 Sep 2013</date>
	    <date dateType="Updated">Mon 25 Jul 2016</date>
            <date dateType="Submitted">Fri 20 Apr 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">43dca8ca271a83f1a2342498ab6e6b6e6689fc8e</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>25091</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

A primal-dual approach for a total variation Wasserstein flow Martin Benning 1 , Luca Calatroni 2 , Bertram D¨uring 3 , Carola-Bibiane Sch¨onlieb 4 1 Magnetic Resonance Research Centre, University of Cambridge, UK 2 Cambridge Centre for Analysis, University of Cambridge, UK 3 Department of Mathematics, University of Sussex, UK 4 Department of Applied Mathematics and Theoretical Physics, University of Cambridge, UK Geometric Science of Information 2013 Ecole des Mines, Paris, 28-30 August 2013. Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 1 / 24 Outline 1 The problem 2 Primal-dual formulation of the problem A relaxed optimality system of PDEs The numerical approach 3 Numerical results The 1-D case The 2-D case with applications to denoising 4 Conclusions Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 2 / 24 A highly nonlinear fourth-order PDE For a regular domain Ω ⊂ Rd , d = 1, 2 we consider: The problem ut = · (u q), q ∈ ∂|Du|(Ω), in Ω × (0, T), u(0, x) = u0(x) ≥ 0 in Ω where Ω u0 dx = 1 and the total variation of u over Ω is defined as: |Du|(Ω) = sup p∈C∞ 0 (Ω;Rd ), p ∞≤1 Ω u · p dx. Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 3 / 24 A highly nonlinear fourth-order PDE For a regular domain Ω ⊂ Rd , d = 1, 2 we consider: The problem ut = · (u q), q ∈ ∂|Du|(Ω), in Ω × (0, T), u(0, x) = u0(x) ≥ 0 in Ω where Ω u0 dx = 1 and the total variation of u over Ω is defined as: |Du|(Ω) = sup p∈C∞ 0 (Ω;Rd ), p ∞≤1 Ω u · p dx. Subgradients of TV can be characterised such that: q ∈ ∂|Du|(Ω) ⇒ q = − · u | u| if | u| = 0, which makes the problem above a nonlinear fourth-order PDE with severe restrictions and constraints for its numerical solution. . . Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 3 / 24 An L2 -Wasserstein flow for density smoothing An equivalent problem has been investigated by Burger, Franek, Sch¨onlieb (2012). Therein, a smoothed version u of a given probability density u0 was computed as a minimiser of: 1 2 W2(u0Ld , uLd )2 L2−Wasserstein distance + α E(u) smoothing term for different choices of E(u) (Dirichlet energy, Log-entropy, Fisher information, Total Variation...), e.g. u0 could be a noisy MRI image or represent some real-world data (earthquakes or fires measurements). Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 4 / 24 An L2 -Wasserstein flow for density smoothing An equivalent problem has been investigated by Burger, Franek, Sch¨onlieb (2012). Therein, a smoothed version u of a given probability density u0 was computed as a minimiser of: 1 2 W2(u0Ld , uLd )2 L2−Wasserstein distance + α E(u) smoothing term for different choices of E(u) (Dirichlet energy, Log-entropy, Fisher information, Total Variation...), e.g. u0 could be a noisy MRI image or represent some real-world data (earthquakes or fires measurements). Previous work in imaging by means of Wasserstein distance: S. Haker , L. Zhu and A. Tannenbaum (2004) for image registration; G. Peyr´e et al. (2013) for image color transfer; X. Bresson, T. Chan et al. (2009) for image segmentation; L. P. S. Demers et al. (2010) for particle image velocimetry; . . . Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 4 / 24 The L2 -Wasserstein metric Let (Ω, d) be a metric space. The L2 -Wasserstein distance between two probability measures µ1 , µ2 ∈ P2(Ω) (the space of all probability measures on Ω with µ-integrable second moment) is defined by W2(µ1 , µ2 )2 := min Π∈Γ(µ1,µ2) Ω×Ω d(x, y)2 dΠ(x, y). Here Γ(µ1 , µ2 ) denotes the space of pairings γ ∈ P(Ω × Ω) such that: µ1 is the first marginal of γ, µ2 is the second marginal of γ. The definition can be extended to (p-th)-Wasserstein distances. . . Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 5 / 24 Why TV-Wasserstein? Compared to smoother regularisers: Capability of preserving discontinuities and structures when regularising densities (Rudin, Osher, Fatemi ‘92). Interest in Image Processing: discontinuities are the edges of the image = characteristic features in many imaging applications (bone density and brain images. . . ). Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 6 / 24 Why TV-Wasserstein? Compared to smoother regularisers: Capability of preserving discontinuities and structures when regularising densities (Rudin, Osher, Fatemi ‘92). Interest in Image Processing: discontinuities are the edges of the image = characteristic features in many imaging applications (bone density and brain images. . . ). The combination of TV and the Wasserstein fidelity term gives you: Mass conservation! u0 initial probability measure ⇒ regularised probability density u. Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 6 / 24 Why TV-Wasserstein? Compared to smoother regularisers: Capability of preserving discontinuities and structures when regularising densities (Rudin, Osher, Fatemi ‘92). Interest in Image Processing: discontinuities are the edges of the image = characteristic features in many imaging applications (bone density and brain images. . . ). The combination of TV and the Wasserstein fidelity term gives you: Mass conservation! u0 initial probability measure ⇒ regularised probability density u. Introduces a higher-order smoothing that reduces TV-artifacts. Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 6 / 24 The minimisation problem and our PDE The problem: 1 2 W2(u0Ld , uLd )2 + αE(u) has to be interpreted as a time discrete approximation of a solution of the gradient flow of E with respect to the L2 -Wasserstein metric: it represents one timestep of De Giorgi’s minimising movement scheme. Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 7 / 24 The minimisation problem and our PDE The problem: 1 2 W2(u0Ld , uLd )2 + αE(u) has to be interpreted as a time discrete approximation of a solution of the gradient flow of E with respect to the L2 -Wasserstein metric: it represents one timestep of De Giorgi’s minimising movement scheme. Solving: 1 2 W2(uk Ld , uLd )2 + (tk+1 − tk )E(u) → argminu =: uk+1 provides an iterative approach (JKO scheme) to approximately solve diffusion equations of the type: ut = · (u E (u)) Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 7 / 24 The minimisation problem and our PDE The problem: 1 2 W2(u0Ld , uLd )2 + αE(u) has to be interpreted as a time discrete approximation of a solution of the gradient flow of E with respect to the L2 -Wasserstein metric: it represents one timestep of De Giorgi’s minimising movement scheme. Solving: 1 2 W2(uk Ld , uLd )2 + (tk+1 − tk )E(u) → argminu =: uk+1 provides an iterative approach (JKO scheme) to approximately solve diffusion equations of the type: ut ∈ · (u ∂|Du|(Ω)) ⇒ our PDE! Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 7 / 24 Previous results and our goal In their work Burger, Franek, Sch¨onlieb have shown: Existence results (by standard technique in Calculus of Variations); Self-similarity properties of the solutions; Numerical results: augmented Lagrangian schemes solving the minimisation problem (for a fixed α, this means computing one timestep of the minimising movement scheme). Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 8 / 24 Previous results and our goal In their work Burger, Franek, Sch¨onlieb have shown: Existence results (by standard technique in Calculus of Variations); Self-similarity properties of the solutions; Numerical results: augmented Lagrangian schemes solving the minimisation problem (for a fixed α, this means computing one timestep of the minimising movement scheme). We want to study the dynamics of the corresponding gradient flow (multiple timesteps), finding a numerical scheme providing its discrete approximation. Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 8 / 24 Outline 1 The problem 2 Primal-dual formulation of the problem A relaxed optimality system of PDEs The numerical approach 3 Numerical results The 1-D case The 2-D case with applications to denoising 4 Conclusions Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 9 / 24 Outline 1 The problem 2 Primal-dual formulation of the problem A relaxed optimality system of PDEs The numerical approach 3 Numerical results The 1-D case The 2-D case with applications to denoising 4 Conclusions Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 10 / 24 An alternative approach The original equation we consider is: ut = · (u q), q ∈ ∂|Du|(Ω). Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 11 / 24 An alternative approach The original equation we consider is: ut = · (u q), q ∈ ∂|Du|(Ω). Can we formulate the problem differently? Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 11 / 24 An alternative approach The original equation we consider is: ut = · (u q), q ∈ ∂|Du|(Ω). Can we formulate the problem differently? By definition of sudifferential: q ∈ ∂|Du|(Ω) ⇐⇒ |Du|(Ω) − Ω qu dx ≤ |Dv|(Ω) − Ω qv dx, ∀v ∈ L2 (Ω). So, if u ∈ BV(Ω) ⊂ L2 (Ω) is the solution of: min u∈BV(Ω) |Du|(Ω) − Ω qu dx ⇒ q ∈ ∂|Du|(Ω) Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 11 / 24 An alternative approach The original equation we consider is: ut = · (u q), q ∈ ∂|Du|(Ω). Can we formulate the problem differently? By definition of sudifferential: q ∈ ∂|Du|(Ω) ⇐⇒ |Du|(Ω) − Ω qu dx ≤ |Dv|(Ω) − Ω qv dx, ∀v ∈ L2 (Ω). So, if u ∈ BV(Ω) ⊂ L2 (Ω) is the solution of: min u∈BV(Ω) sup p∈C∞ 0 (Ω;R2), p ∞≤1 Ω u · p dx − Ω qu dx ⇒ q ∈ ∂|Du|(Ω) Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 11 / 24 An alternative approach The original equation we consider is: ut = · (u q), q ∈ ∂|Du|(Ω). Can we formulate the problem differently? By definition of sudifferential: q ∈ ∂|Du|(Ω) ⇐⇒ |Du|(Ω) − Ω qu dx ≤ |Dv|(Ω) − Ω qv dx, ∀v ∈ L2 (Ω). So, if u ∈ BV(Ω) ⊂ L2 (Ω) is the solution of: min u∈BV(Ω)    sup p∈C∞ 0 (Ω;R2), p ∞ ≤ 1 Ω u · p dx − Ω qu dx    ⇒ q ∈ ∂|Du|(Ω) Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 11 / 24 An alternative approach The original equation we consider is: ut = · (u q), q ∈ ∂|Du|(Ω). Can we formulate the problem differently? By definition of sudifferential: q ∈ ∂|Du|(Ω) ⇐⇒ |Du|(Ω) − Ω qu dx ≤ |Dv|(Ω) − Ω qv dx, ∀v ∈ L2 (Ω). So, if u ∈ BV(Ω) ⊂ L2 (Ω) is the solution of: min u∈BV(Ω) sup p∈C∞ 0 (Ω;R2)    Ω u · p dx − 1 ε F(|p| − 1) penalty term − Ω qu dx    ⇒ q ∈ ∂|Du|(Ω) where 0 < ε 1 measures the weight of the penalisation (Benning, M¨uller). Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 11 / 24 The relaxed problem Merging the original equation we started from with the optimality conditions with respect to u and p we get:    ut = · (u q), q = · p, 0 = − u − 1 ε F (|p| − 1) and the nonlinearity now is encoded in the penalty term F . A typical choice for F is: F(|p| − 1) = 1 2 max{|p| − 1, 0}2 , F (|p| − 1) = 1{|p|≥1}sgn(p)(|p| − 1). We can now linearise F via its first-order Taylor approximation. . . Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 12 / 24 Outline 1 The problem 2 Primal-dual formulation of the problem A relaxed optimality system of PDEs The numerical approach 3 Numerical results The 1-D case The 2-D case with applications to denoising 4 Conclusions Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 13 / 24 A damped Newton method to solve the system We discretise the differential operators and compute the numerical approximation of the solution u using the following scheme:    Un+1 − Un ∆t = · (Un Qn+1) Qn+1 = · Pn+1, 0 = − Un+1 − 1 ε F (Pn ) − 1 ε F (Pn )(Pn+1 − Pn ). Outer iterations (n subscripts) for the time evolution; Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 14 / 24 A damped Newton method to solve the system We discretise the differential operators and compute the numerical approximation of the solution u using the following scheme:    U (k) n+1 − Un ∆t = · (Un Q (k) n+1) Q (k) n+1 = · P (k) n+1, 0 = − U (k) n+1 − 1 ε F (P (k−1) n+1 ) − 1 ε F (P (k−1) n+1 )(P (k) n+1 − P (k−1) n+1 ). Outer iterations (n subscripts) for the time evolution; Inner process (k superscripts) producing approximations of Un+1, Qn+1 and Pn+1 via Newton method; Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 14 / 24 A damped Newton method to solve the system We discretise the differential operators and compute the numerical approximation of the solution u using the following scheme:    U (k) n+1 − Un ∆t = · (Un Q (k) n+1) Q (k) n+1 = · P (k) n+1, 0 = − U (k) n+1 − 1 ε F (P (k−1) n+1 ) − 1 ε F (P (k−1) n+1 )(P (k) n+1 − P(k−1) )−τk (P (k) n+1 − P (k−1) n+1 ). Outer iterations (n subscripts) for the time evolution; Inner process (k superscripts) producing approximations of Un+1, Qn+1 and Pn+1 via Newton method; The damping sequence τk guarantees the invertibility of the operators defining the system: it starts from a large τ0 and decreases to ensure quick convergence. Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 14 / 24 Outline 1 The problem 2 Primal-dual formulation of the problem A relaxed optimality system of PDEs The numerical approach 3 Numerical results The 1-D case The 2-D case with applications to denoising 4 Conclusions Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 15 / 24 Numerical ingredients 1 Discretisations of the differential operators using forward differences (for ) and backward differences (for ·), thus preserving adjointness; 2 Neumann boundary conditions; 3 Computational domains: closed and bounded (cartesian product of) interval(s); 4 The matrix defining the linear system in each Newton step has block-structure ⇒ numerical inversion of the operators by using Schur complement; 5 Stopping criterion for the inner Newton loop: U (k) n+1 − U (k−1) n+1 2 U (k) n+1 2 ≤ tol , Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 16 / 24 Outline 1 The problem 2 Primal-dual formulation of the problem A relaxed optimality system of PDEs The numerical approach 3 Numerical results The 1-D case The 2-D case with applications to denoising 4 Conclusions Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 17 / 24 Some 1-D examples We compare the TV-Wasserstein approach with the standard TV one: −0.5 0 0.5 1 1.5 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 x y TV/TV−Wasserstein comparison Initial condition TV result TV−Wasserstein result (a) Gaussian in. cond. −1 −0.5 0 0.5 1 1.5 2 0.2 0.4 0.6 0.8 1 1.2 1.4 x y Comparison TV/TV−Wasserstein Initial condition TV solution TV−Wasserstein solution (b) χ[a,b] in. cond. −1 −0.5 0 0.5 1 1.5 2 0.1 0.2 0.3 0.4 0.5 0.6 0.7 x y TV/TV−Wasserstein comparison Initial condition TV result TV−Wasserstein result (c) Stair in. cond. Figure : Solutions for TV and TV-Wasserstein flows. ε = 10−5 , τ0 = 1. Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 18 / 24 Some 1-D examples We compare the TV-Wasserstein approach with the standard TV one: −0.5 0 0.5 1 1.5 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 x y TV/TV−Wasserstein comparison Initial condition TV result TV−Wasserstein result (a) Gaussian in. cond. −1 −0.5 0 0.5 1 1.5 2 0.2 0.4 0.6 0.8 1 1.2 1.4 x y Comparison TV/TV−Wasserstein Initial condition TV solution TV−Wasserstein solution (b) χ[a,b] in. cond. −1 −0.5 0 0.5 1 1.5 2 0.1 0.2 0.3 0.4 0.5 0.6 0.7 x y TV/TV−Wasserstein comparison Initial condition TV result TV−Wasserstein result (c) Stair in. cond. Figure : Solutions for TV and TV-Wasserstein flows. ε = 10−5 , τ0 = 1. Features: Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 18 / 24 Some 1-D examples We compare the TV-Wasserstein approach with the standard TV one: −0.5 0 0.5 1 1.5 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 x y TV/TV−Wasserstein comparison Initial condition TV result TV−Wasserstein result (a) Gaussian in. cond. −1 −0.5 0 0.5 1 1.5 2 0.2 0.4 0.6 0.8 1 1.2 1.4 x y Comparison TV/TV−Wasserstein Initial condition TV solution TV−Wasserstein solution (b) χ[a,b] in. cond. −1 −0.5 0 0.5 1 1.5 2 0.1 0.2 0.3 0.4 0.5 0.6 0.7 x y TV/TV−Wasserstein comparison Initial condition TV result TV−Wasserstein result (c) Stair in. cond. Figure : Solutions for TV and TV-Wasserstein flows. ε = 10−5 , τ0 = 1. Features: Similar with TV: Preservation of structure (i.e. discontinuities); Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 18 / 24 Some 1-D examples We compare the TV-Wasserstein approach with the standard TV one: −0.5 0 0.5 1 1.5 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 x y TV/TV−Wasserstein comparison Initial condition TV result TV−Wasserstein result (a) Gaussian in. cond. −1 −0.5 0 0.5 1 1.5 2 0.2 0.4 0.6 0.8 1 1.2 1.4 x y Comparison TV/TV−Wasserstein Initial condition TV solution TV−Wasserstein solution (b) χ[a,b] in. cond. −1 −0.5 0 0.5 1 1.5 2 0.1 0.2 0.3 0.4 0.5 0.6 0.7 x y TV/TV−Wasserstein comparison Initial condition TV result TV−Wasserstein result (c) Stair in. cond. Figure : Solutions for TV and TV-Wasserstein flows. ε = 10−5 , τ0 = 1. Features: Similar with TV: Preservation of structure (i.e. discontinuities); Different with TV: * Decreasing of intensity ↔ enlarging of the support (because of the mass conservation); * Constant background = TV solutions: convergence to their mean. Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 18 / 24 Outline 1 The problem 2 Primal-dual formulation of the problem A relaxed optimality system of PDEs The numerical approach 3 Numerical results The 1-D case The 2-D case with applications to denoising 4 Conclusions Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 19 / 24 2-D results Solution of the TV-Wasserstein flow: (a) Initial condition. (b) TV result. (c) TV-Wasserstein result. The intensity of the square decreases, but the intensity of the background stays constant (different from TV!); As the intensity of the square decreases, the support enlarges due to the mass conservation property. Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 20 / 24 2-D results: applications to denoising Solution of the TV-Wasserstein flow: (a) Original pyramid. (b) Noisy pyramid. (c) TV-Wasserstein. Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 21 / 24 2-D results: applications to denoising Solution of the TV-Wasserstein flow: (a) Original pyramid. (b) Noisy pyramid. (c) TV-Wasserstein. (d) TV. Reduced staircasing! Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 21 / 24 2-D results: applications to denoising (cont.) Solution of the TV-Wasserstein flow for real-world images: (a) Noisy LEGO. (b) TV result. (c) TV-Wasserstein result. Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 22 / 24 2-D results: applications to denoising (cont.) Solution of the TV-Wasserstein flow for real-world images: (a) Noisy LEGO. (b) TV result. (c) TV-Wasserstein result. Applications in MRI: the images of interest are densities restored from undersampled measurements and/or corrupted by noise or blur.. Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 22 / 24 Outline 1 The problem 2 Primal-dual formulation of the problem A relaxed optimality system of PDEs The numerical approach 3 Numerical results The 1-D case The 2-D case with applications to denoising 4 Conclusions Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 23 / 24 Recap and future directions Tackling directly the non-smoothness of the higher-order TV-subgradients and relaxing via a penalty term leads to a system of nonlinear PDEs; The numerical solution is computed efficiently by using a nested damped Newton method that computes the numerical approximation of the solution in each time iteration; The results preserve the mass-conservation property and show good results in density smoothing (e.g. denoising in imaging), reducing artifacts compared to lower-order models; Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 24 / 24 Recap and future directions Tackling directly the non-smoothness of the higher-order TV-subgradients and relaxing via a penalty term leads to a system of nonlinear PDEs; The numerical solution is computed efficiently by using a nested damped Newton method that computes the numerical approximation of the solution in each time iteration; The results preserve the mass-conservation property and show good results in density smoothing (e.g. denoising in imaging), reducing artifacts compared to lower-order models; Q1 Rigorous analysis of the scheme? Barrier term? Stability properties? Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 24 / 24 Recap and future directions Tackling directly the non-smoothness of the higher-order TV-subgradients and relaxing via a penalty term leads to a system of nonlinear PDEs; The numerical solution is computed efficiently by using a nested damped Newton method that computes the numerical approximation of the solution in each time iteration; The results preserve the mass-conservation property and show good results in density smoothing (e.g. denoising in imaging), reducing artifacts compared to lower-order models; Q1 Rigorous analysis of the scheme? Barrier term? Stability properties? Q2 From the analysis of the 1-D case, more insights on the theory underlying the TV-Wasserstein gradient flow (joint work with M. Burger, D. Matthes). Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 24 / 24 Recap and future directions Tackling directly the non-smoothness of the higher-order TV-subgradients and relaxing via a penalty term leads to a system of nonlinear PDEs; The numerical solution is computed efficiently by using a nested damped Newton method that computes the numerical approximation of the solution in each time iteration; The results preserve the mass-conservation property and show good results in density smoothing (e.g. denoising in imaging), reducing artifacts compared to lower-order models; Q1 Rigorous analysis of the scheme? Barrier term? Stability properties? Q2 From the analysis of the 1-D case, more insights on the theory underlying the TV-Wasserstein gradient flow (joint work with M. Burger, D. Matthes). Thanks for listening! e-mail: l.calatroni@maths.cam.ac.uk Benning, Calatroni, D¨uring, Sch¨onlieb (CCA) A primal-dual approach for a TV-Wasserstein flow GSI 2013, Paris, August 2013 24 / 24