Non-convex relaxation of optimal transport for color transfer between images

28/10/2015
Publication GSI2015
OAI : oai:www.see.asso.fr:11784:14307

Résumé

Optimal transport (OT) is a major statistical tool to measure similarity between features or to match and average features. However, OT requires some relaxation and regularization to be robust to outliers. With relaxed methods, as one feature can be matched to several ones, important interpolations between different features arise. This is not an issue for comparison purposes, but it involves strong and unwanted smoothing for transfer applications. We thus introduce a new regularized method based on a non-convex formulation that minimizes transport dispersion by enforcing the one-to-one matching of features. The interest of the approach is demonstrated for color transfer purposes.

Non-convex relaxation of optimal transport for color transfer between images

Collection

application/pdf Non-convex relaxation of optimal transport for color transfer between images Julien Rabin, Nicolas Papadakis

Média

Voir la vidéo

Métriques

120
12
14.42 Mo
 application/pdf
bitcache://465f422ad7b36c600b362a2a1ccfc8e60aef4da9

Licence

Creative Commons Attribution-ShareAlike 4.0 International

Sponsors

Organisateurs

logo_see.gif
logocampusparissaclay.png

Sponsors

entropy1-01.png
springer-logo.png
lncs_logo.png
Séminaire Léon Brillouin Logo
logothales.jpg
smai.png
logo_cnrs_2.jpg
gdr-isis.png
logo_gdr-mia.png
logo_x.jpeg
logo-lix.png
logorioniledefrance.jpg
isc-pif_logo.png
logo_telecom_paristech.png
csdcunitwinlogo.jpg
<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/11784/14307</identifier><creators><creator><creatorName>Julien Rabin</creatorName></creator><creator><creatorName>Nicolas Papadakis</creatorName></creator></creators><titles>
            <title>Non-convex relaxation of optimal transport for color transfer between images</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2015</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><subjects><subject>Optimal transport</subject><subject>Relaxation</subject><subject>Color transfer</subject></subjects><dates>
	    <date dateType="Created">Sun 8 Nov 2015</date>
	    <date dateType="Updated">Wed 31 Aug 2016</date>
            <date dateType="Submitted">Fri 17 Aug 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">465f422ad7b36c600b362a2a1ccfc8e60aef4da9</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>24699</version>
        <descriptions>
            <description descriptionType="Abstract">
Optimal transport (OT) is a major statistical tool to measure similarity between features or to match and average features. However, OT requires some relaxation and regularization to be robust to outliers. With relaxed methods, as one feature can be matched to several ones, important interpolations between different features arise. This is not an issue for comparison purposes, but it involves strong and unwanted smoothing for transfer applications. We thus introduce a new regularized method based on a non-convex formulation that minimizes transport dispersion by enforcing the one-to-one matching of features. The interest of the approach is demonstrated for color transfer purposes.

</description>
        </descriptions>
    </resource>
.

Introduction 1 / 30 Adaptive color transfer with relaxed optimal transport Julien Rabin1 , Sira Ferradans2 and Nicolas Papadakis3 1 GREYC, University of Caen, 2 Data group, ENS, 3 CNRS, Institut de Mathématiques de Bordeaux Conference on Geometric Science of Information J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Introduction 2 / 30 Optimal transport on histograms Monge-Kantorovitch (MK) discrete mass transportation problem: Map µ0 onto µ1 while minimizing the total transport cost ������������� The two histograms must have the same mass. Optimal transport cost is called the Wasserstein distance (Earth Mover’s Distance) Optimal transport map is the application mapping µ0 onto µ1 J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Introduction 3 / 30 Applications in Image Processing and Computer Vision Optimal transport as a framework to define statistical-based tools Applications to many imaging and computer vision problems: • Robust dissimilarity measure (Optimal transport cost): Image retrieval [Rubner et al., 2000] [Pele and Werman, 2009] SIFT matching [Pele and Werman, 2008] [Rabin et al., 2009] 3D shape recognition, Feature detection [Tomasi] Object segmentation [Ni et al., 2009] [Swoboda and Schnorr, 2013] • Tool for matching/interpolation (Optimal transport map): Non-rigid shape matching, image registration [Angenent et al., 2004] Texture synthesis and mixing [Ferradans et al., 2013] Histogram specification and averaging [Delon, 2004] Color transfer [Pitié et al., 2007], [Rabin et al., 2011b] Not to mention other applications (physics, economy, etc). J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Introduction 4 / 30 Color transfer Target image (µ) Source image (ν) Optimal transport of µ onto ν Target image after color transfer Limitations: • Mass conservation artifacts • Irregularity of optimal transport map J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Introduction 5 / 30 Outline Outline: Part I. Computation of optimal transport between histograms Part II. Optimal transport relaxation and regularization Application to color transfer J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Optimal transport framework 6 / 30 Part I Wasserstein distance between histograms J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Optimal transport framework 7 / 30 Formulation for clouds of points Definition: L2 -Wasserstein Distance Given two clouds of points X, Y ⊂ Rd×N of N elements in Rd with equal masses 1 N , the quadratic Wasserstein distance is defined as W2(X, Y)2 = min σ∈ΣN 1 N N i=1 Xi − Yσ(i) 2 (1) where ΣN is the set of all permutations of N elements. J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Optimal transport framework 7 / 30 Formulation for clouds of points Definition: L2 -Wasserstein Distance Given two clouds of points X, Y ⊂ Rd×N of N elements in Rd with equal masses 1 N , the quadratic Wasserstein distance is defined as W2(X, Y)2 = min σ∈ΣN 1 N N i=1 Xi − Yσ(i) 2 (1) where ΣN is the set of all permutations of N elements. ⇔ Optimal Assignment problem, can be computed using standard sorting algorithms when d = 1 J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Optimal transport framework 8 / 30 Exact solution in unidimensional case (d = 1) for histograms Histograms may be seen as clouds of points with non-uniform masses, so that µ(x) = M i=1 mi δXi (x), s.t. i mi = 1, mi ≥ 0 ∀i Computing the Lp -Wasserstein distance for one-dimensional histograms is still simple for p ≥ 1. Optimal transport cost writes [Villani, 2003] Wp(µ, ν) = H−1 µ − H−1 ν p = 1 0 H−1 µ (t) − H−1 ν (t) p dt 1 p where Hµ(t) = t −∞ dµ = Xi t mi is the cumulative distribution function of µ and H−1 µ (t) = inf {s \ Rµ(s) t} its pseudo-inverse. Time complexity: O(N) operations if bins are already sorted. J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Optimal transport framework 9 / 30 Exact solution in unidimensional case (d = 1) for histograms J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Optimal transport framework 9 / 30 Exact solution in unidimensional case (d = 1) for histograms J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Optimal transport framework 9 / 30 Exact solution in unidimensional case (d = 1) for histograms J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Optimal transport framework 9 / 30 Exact solution in unidimensional case (d = 1) for histograms J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Optimal transport framework 9 / 30 Exact solution in unidimensional case (d = 1) for histograms J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Optimal transport framework 9 / 30 Exact solution in unidimensional case (d = 1) for histograms J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Optimal transport framework 9 / 30 Exact solution in unidimensional case (d = 1) for histograms J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Optimal transport framework 9 / 30 Exact solution in unidimensional case (d = 1) for histograms Can not be extended to higher dimensions as the cumulative function Hµ : x ∈ Rd → Hµ(x) ∈ R is not invertible for d > 1 J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Optimal transport framework 10 / 30 Exact solution in general case (d>1) Transport cost between normalized histograms µ and ν, where µ = M i=1 mi δXi , ν = N j=1 nj δYj , mi , nj ≥ 0 and i mi = j nj = 1. • mi , nj are the masses at locations Xi , Yj It can be recasted as a linear programming problem: linear cost + linear constraints W2(µ, ν)2 = min P∈Pµ,ν    P , C = i,j Pi,j Xi − Yj 2    = min A·p=b pT c • C is the fixed cost assignment matrix between histograms bins: Ci,j = d k=1 ||Xk i − Yk j ||2 • Pµ,ν is the set of non negative matrices P with marginals µ and ν, ie P(µ, ν) =    P ∈ RM×N , Pi,j 0, i,j Pi,j = 1, j Pi,j = mi , i Pi,j = nj    J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Optimal transport framework 11 / 30 Illustration in unidimensional case (d = 1) for histograms Two histograms µ = {1 3 , 2 3 } and ν = {1 3 , 1 6 , 1 2 } Example: µi is the production at plant i and νj is the storage capacity of storehouse j Matrix C defines the transport cost from i to j: C11 = 22 C21 = 62 C12 = 12 C22 = 52 C13 = 52 C23 = 12 The set of admissible matrices P is µ1 = 1/3 µ2 = 2/3 P11 P21 ν1 = 1/3 P12 P22 ν2 = 1/6 P13 P23 ν3 = 1/2 Pij is the mass that is transported from µi to νj . J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Optimal transport framework 11 / 30 Illustration in unidimensional case (d = 1) for histograms Two histograms µ = {1 3 , 2 3 } and ν = {1 3 , 1 6 , 1 2 } Example: µi is the production at plant i and νj is the storage capacity of storehouse j Matrix C defines the transport cost from i to j: C11 = 22 C21 = 62 C12 = 12 C22 = 52 C13 = 52 C23 = 12 The set of admissible matrices P is µ1 = 1/3 µ2 = 2/3 1/9 2/9 ν1 = 1/3 1/18 1/9 ν2 = 1/6 1/6 1/3 ν3 = 1/2 Pij is the mass that is transported from µi to νj . The transport cost is W(µ, ν) = ij Pij Cij = 15 J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Optimal transport framework 11 / 30 Illustration in unidimensional case (d = 1) for histograms Two histograms µ = {1 3 , 2 3 } and ν = {1 3 , 1 6 , 1 2 } Example: µi is the production at plant i and νj is the storage capacity of storehouse j Matrix C defines the transport cost from i to j: C11 = 22 C21 = 62 C12 = 12 C22 = 52 C13 = 52 C23 = 12 The set of admissible matrices P is µ1 = 1/3 µ2 = 2/3 1/3 0 ν1 = 1/3 0 1/6 ν2 = 1/6 0 1/2 ν3 = 1/2 Pij is the mass that is transported from µi to νj . The transport cost is W(µ, ν) = ij Pij Cij = 6 J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Optimal transport framework 12 / 30 Optimal transport solution illustration in 1D Histograms µ and ν (on uniform grid Ω) Optimal flow P J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Optimal transport framework 12 / 30 Optimal transport solution illustration in 1D Histograms µ and ν (on uniform grid Ω) Optimal flow P Remark: Masses can be splitted by transport J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Optimal transport framework 12 / 30 Optimal transport solution illustration in 1D Histograms µ and ν (on uniform grid Ω) Optimal flow P Remark: Masses can be splitted by transport J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Optimal transport framework 13 / 30 Optimal transport solution with linear programming method Discrete mass transportation problem for histograms can be solved with standard linear programming algorithms (simplex, interior point methods). Dedicated algorithms are more efficient for optimal assignment problem (e.g Hungarian and Auction algorithms in O(N3 )) Computation can be (slightly) accelerated when using other costs than L2 (e.g. L1 [Ling and Okada, 2007], Truncated L1 [Pele and Werman, 2008]) Advantages Complexity does not depend on feature dimension d Limitation Intractable for signal processing applications where N 103 (considering time complexity & memory limitation) J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Relaxation Regularization Conclusion 14 / 30 Part II Relaxation and regularization J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Relaxation Regularization Conclusion 15 / 30 Problem Statement Histogram specification exhibits strong limitations of optimal transport when dealing with image processing: • Color artifacts due to the exact specification (histograms can have very different shapes) • Irregularities: Transport map is not consistent in the color domain It does not take into account spatial information Histogram equalization + Filtering Proposed solution • Relax mass conservation constraint • Promote regular transport flows (color consistency) • Include spatial information (spatial consistency) J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Relaxation Regularization Conclusion 16 / 30 Constraint Relaxation Idea 1: Relaxation of mass conservation constraints [Ferradans et al., 2013] We consider the transport cost between normalized histograms µ and ν, µ(x) = M i=1 mi δXi (x), s.t. i mi = 1, mi ≥ 0 ∀i Relaxed Formulation : P ∈ arg min P∈Pκ(µ,ν)    P, C = 1 i N,1 j M Pi,j Ci,j    • with Ci,j = Xi − Yj 2 , where Xi ∈ Ω ⊂ Rd is bin centroid of µ for index i; • with new (linear) constraints: P(µ, ν) =    Pi,j 0, i,j Pi,j = 1, j Pi,j = mi , i Pi,j = nj    J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Relaxation Regularization Conclusion 16 / 30 Constraint Relaxation Idea 1: Relaxation of mass conservation constraints [Ferradans et al., 2013] We consider the transport cost between normalized histograms µ and ν, µ(x) = M i=1 mi δXi (x), s.t. i mi = 1, mi ≥ 0 ∀i Relaxed Formulation : P ∈ arg min P∈Pκ(µ,ν)    P, C = 1 i N,1 j M Pi,j Ci,j    • with Ci,j = Xi − Yj 2 , where Xi ∈ Ω ⊂ Rd is bin centroid of µ for index i; • with new (linear) constraints: Pκ(µ, ν) =    Pi,j 0, i,j Pi,j = 1, j Pi,j = mi , κnj ≤ i Pi,j ≤ Knj    where capacity parameters are such that κ ≤ 1 ≤ K: hard to tune J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Relaxation Regularization Conclusion 17 / 30 Proposed relaxed histogram matching Idea 2: Use capacity variables as unknowns {P , κ } ∈ arg min P∈Pκ(µ,ν) κ∈RN ,κ≥0, κ, n =1 P, C + ρ||κ − 1||1 where Pκ(µ, ν) =    Pi,j 0, i,j Pi,j = 1, j Pi,j = mi , i Pi,j = κj nj    ⇒ Still a linear program J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Relaxation Regularization Conclusion 18 / 30 Illustration of relaxed transport Optimal transport J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Relaxation Regularization Conclusion 18 / 30 Illustration of relaxed transport Relaxed optimal transport J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Relaxation Regularization Conclusion 19 / 30 Relaxed color transfer: comparison with raw OT Target Raw OT Relaxed OT Source No color or spatial regularization J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Relaxation Regularization Conclusion 20 / 30 Proposed relaxed and regularized histogram matching Idea 3: Add regularization prior {P , κ } ∈ arg min P∈Pκ(µ,ν) κ∈RN ,κ≥0, κ, n =1 P, C + ρ||κ − 1||1 + λR(P). where Pκ(µ, ν) =    Pi,j 0, i,j Pi,j = 1, j Pi,j = mi , i Pi,j = κj nj    and R(P) models some regularity priors ⇒ Still a linear program J. Rabin, S. Ferradans, N. Papadakis Adaptive color transfer with relaxed optimal transport Relaxation Regularization Conclusion 21 / 30 Regularity of transport map • Global regularization: Defining the regularity of the flow matrix is a NP-hard problem • Average transport map Instead, we use the Posterior mean to estimate a one-to-one transfer function T between µ and ν T(Xi )