Abed Bounemoura

Stéphane Fischler

The classical KAM theorem for Hamiltonian systems via rational approximations

may come

The classical KAM theorem for Hamiltonian systems via rational approximations

Introduction

In this paper, we consider small perturbations of integrable Hamiltonian systems, which are defined by a Hamiltonian function of the form H(p, q) = h(p) + ǫf (p, q), (p, q) ∈ R n × T n , 0 ≤ ǫ < 1, where n ≥ 2 is an integer and T n = R n /Z n : the Hamiltonian system associated to this Hamiltonian function is then given by ṗ = -∂ q H(p, q) = -ǫ∂ q f (p, q), q = ∂ p H(p, q) = ∇h(p) + ǫ∂ p f (p, q). When ǫ = 0, the system associated to H = h is trivially integrable: all solutions are given by (p(t), q(t)) = (p(0), q(0) + t∇h(p(0)) [Z n ]), and therefore the sets T p 0 = {p 0 } × T n , p 0 ∈ R n , are invariant tori on which the dynamics is quasi-periodic with frequency ω 0 = ∇h(p 0 ) ∈ R n . Now for ǫ > 0, the system is in general no longer integrable, and one is interested to know whether such quasi-periodic solutions persist under an arbitrary small perturbation. It is not hard to see that if the frequency ω 0 ∈ R n is resonant, that is if there exists a vector k ∈ Z n \{0} such that k • ω 0 = 0, then the torus T p 0 is destroyed by a general perturbation. This goes back to Poincaré, who initiated the study of small perturbations of integrable Hamiltonian systems in his seminal work on Celestial Mechanics.

K for Kolmogorov

The fate of quasi-periodic solutions with non-resonant frequencies remained an open question for more than half a century, until it was solved by Kolmogorov. In [START_REF] Kolmogorov | On the preservation of conditionally periodic motions for a small change in Hamilton's function[END_REF], he proved that if H is real-analytic and if h is non-degenerate at some point p 0 ∈ R n in the sense that ∇h is a local diffeomorphism at p 0 , then, provided ω 0 = ∇h(p 0 ) satisfies a classical Diophantine condition, the torus T p 0 survives an arbitrary small perturbation. The condition on ω 0 is a strengthening of the non-resonance condition, namely one requires the existence of constants γ > 0 and τ ≥ n -1 such that for all k ∈ Z n \ {0},

|k • ω 0 | ≥ γ|k| -τ 1 ,
where

|k| 1 = |k 1 | + • • • + |k n | (
this is a generalization of a condition introduced by Siegel in [START_REF] Siegel | Iteration of analytic functions[END_REF] for the problem of linearization of a one-dimensional holomorphic map at an elliptic fixed point). Whereas classical Hamiltonian perturbation theory, as pioneered by Poincaré, only yields formal quasi-periodic solutions through an iterative procedure which may or may not converge, Kolmogorov's main idea was to focus on such a strongly non-resonant torus in order to use a modified and rapidly converging inductive scheme, similar to a Newton method, leading to the persistence of this torus.

A and M for Arnold and Moser

Kolmogorov's fundamental theorem was later revisited and improved by Arnold and Moser, leading to what is known as KAM theory.

In [START_REF] Arnol'd | Proof of a theorem of A.N. Kolmogorov on the invariance of quasiperiodic motions under small perturbations[END_REF], Arnold gave a more detailed and technically different proof, under a different non-degeneracy assumption on the integrable Hamiltonian, and in [START_REF]Small denominators and problems of stability of motion in classical and celestial mechanics[END_REF], he further improved the non-degeneracy assumption in order to apply the theorem to Celestial Mechanics.

In the meantime, in [START_REF] Moser | On Invariant curves of Area-Preserving Mappings of an Annulus[END_REF], Moser was able to replace the analyticity condition on the Hamiltonian by a mere finite differentiability condition, in the related context of invariant curves of area-preserving maps of the annulus. Moreover, in [START_REF]Convergent series expansions for quasi-periodic motions[END_REF], he introduced a powerful formalism for the perturbation theory (not necessarily Hamiltonian) of quasi-periodic solutions, which eventually led to many applications (see [START_REF] Broer | Quasi-periodic motions in families of dynamical systems[END_REF] for instance).

R for Rüssmann

Further important contributions to KAM theory are due to Rüssmann. Indeed, following works of Arnold and Pyartli, Rüssmann was able to find the most general non-degeneracy condition for the integrable Hamiltonian h: in the analytic case, it is sufficient to require that locally, the image of the gradient map ∇h is not contained in any hyperplane of R n (it is also necessary as shown by Sevryuk in [START_REF] Sevryuk | KAM-stable Hamiltonians[END_REF]). This was announced in [START_REF] Rüssmann | Non-degeneracy in the perturbation theory of integrable dynamical systems, Number theory and dynamical systems[END_REF], and details are given in [START_REF]Invariant tori in non-degenerate nearly integrable Hamiltonian systems[END_REF]. Also, he was able to greatly relax the condition imposed on the frequency, going beyond the classical Diophantine condition (see [START_REF]On the frequencies of quasi periodic solutions of analytic nearly integrable Hamiltonian systems[END_REF], [START_REF]Invariant tori in non-degenerate nearly integrable Hamiltonian systems[END_REF]). This condition, which generalizes a condition introduced by Bruno in the context of holomorphic linearization ( [START_REF] Bruno | Analytical form of differential equations I[END_REF], [START_REF]Analytical form of differential equations II[END_REF]), is now usually called Bruno-Rüssmann condition (see §2.2 for a definition), and is known to be optimal in one-dimensional problems following works of Yoccoz (see [START_REF] Yoccoz | Small divisors in dimension one (Petits diviseurs en dimension 1)[END_REF], [START_REF]Analytic linearization of circle diffeomorphisms, Dynamical systems and small divisors[END_REF]). This extension to more general frequency vectors also led to a different method of proof, in which no rapid convergence is involved ([Rüs94], [START_REF]Invariant tori in non-degenerate nearly integrable Hamiltonian systems[END_REF], see also [START_REF]KAM-iteration with nearly infinitely small steps in dynamical systems of polynomial character[END_REF] for the latest improvement of this method).

Other approaches to the classical KAM theorem

Apart from Rüssmann's modified iterative scheme, a number of other proofs have appeared in the literature.

First, the classical iterative scheme of Kolmogorov has been replaced by the use of an adapted implicit function theorem in a scale of Banach spaces (or in a Fréchet space), following works of Zehnder ([Zeh75], [START_REF]Generalized implicit function theorems with applications to some small divisor problems[END_REF]), Herman ( [START_REF] Bost | Tores invariants des systèmes dynamiques Hamiltoniens[END_REF]) and more recently Féjoz ([Féj12]).

Another proof, based on the Lagrangian formalism and that avoids any coordinate transformation, was presented in [START_REF] Levi | A Lagrangian proof of the invariant curve theorem for twist mappings[END_REF] in the case of invariant curves for area-preserving maps of the annulus, and in [START_REF] Salamon | KAM theory in configuration space[END_REF] for Hamiltonian systems in any number of degrees of freedom.

But perhaps the most striking proof is due to Eliasson. The classical theorem of Kolmogorov shows, a posteriori and in an indirect way, that some formal solutions of classical perturbation theory do converge. In [START_REF] Eliasson | Absolutely convergent series expansions for quasi periodic motions[END_REF], Eliasson managed to prove directly the convergence of these formal solutions, by adding suitable terms in the formal series in order to exhibit subtle cancellations yielding the absolute convergence.

At last, we should also point out that using a multi-dimensional continued fraction algorithm due to Lagarias, Khanin, Lopes Dias and Marklof gave a proof of the KAM theorem with techniques closer to renormalization theory (see [START_REF]Multidimensional continued fractions, dynamical renormalization and KAM theory[END_REF] for the case of constant vector fields on the torus, and [START_REF] Khanin | Renormalization of multidimensional Hamiltonian flows[END_REF] for the case of Hamiltonian systems).

Approach via rational approximations

The purpose of this article, which can be considered as a continuation of our previous work [START_REF] Bounemoura | A Diophantine duality applied to the KAM and Nekhoroshev theorems[END_REF], is to present yet another proof of the classical KAM theorem for Hamiltonian systems, which differs qualitatively from all other existing proofs as it does not involve any small divisors estimates and Fourier series expansions.

First we should recall that in the classical approach to the KAM theorem, as well as the other methods of proof we just mentioned, a central role is played by the following equation:

L ω 0 g = f -[f ], [f ] = T n f (θ)dθ, (1.1)
where g (respectively f ) is the unknown (respectively known) smooth function on T n , ω 0 is non-resonant and L ω 0 is the derivative in the direction of ω 0 . It is precisely in trying to solve Equation (1.1) that small divisors arise: geometrically, one needs to integrate along the integral curves t → θ + tω 0 [Z n ], and these curves are not closed (they densely fill the torus). Analytically, one needs to invert the operator L ω 0 acting on the space of smooth functions, and this operator is unbounded. Indeed, this operator can be diagonalized in a Fourier basis: letting e k (θ) = e 2πik•θ for k ∈ Z n and expanding in Fourier series g = k∈Z n g k e k and f = k∈Z n f k e k , the solution is given by

g 0 = 0, g k = (2πik • ω 0 ) -1 f k , k ∈ Z n \ {0}.
The quantities k • ω 0 , which enter in the denominators, can be arbitrarily small if the norm |k| 1 is arbitrarily large: these are called the small divisors, and are the main source of complications.

In this article, we will show how one can, using rational approximations, avoid solving Equation (1.1) and therefore avoid facing small divisors. Assume, without loss of generality, that the first component of ω 0 has been normalized to one. Using a Diophantine result deduced in [START_REF] Bounemoura | A Diophantine duality applied to the KAM and Nekhoroshev theorems[END_REF] from classical properties of geometry of numbers, we will approximate ω 0 by n rational vectors v 1 , . . . , v n ∈ Q n , with a control on their denominators q 1 , . . . , q n in terms of the quality of the approximation, and such that the integer vectors q 1 v 1 , . . . , q n v n form a Z-basis of Z n . This result will enable us to replace the study of Equation (1.1) with the study of the equations

L v j g j = f j -[f j ] v j , [f j ] v j (θ) = 1 0 f (θ + tq j v j )dt, 1 ≤ j ≤ n, (1.2)
where the f j are defined inductively by f 1 = f and f j+1 = [f j ] v j for 1 ≤ j ≤ n -1, and the g j are the unknown. Equations (1.2) are much simpler than Equation (1.1), they can be solved without Fourier expansions by the following simple integral formula

g j (θ) = q j 1 0 (f j -[f j ] v j )(θ + tq j v j )tdt
and there are no small divisors: geometrically, the integral curves t → θ + tv j [Z n ] are q jperiodic hence closed, and analytically, the inverse operator of L v j is bounded (by q j , with respect to any translation-invariant norm on the space of functions on the torus).

In [START_REF] Bounemoura | A Diophantine duality applied to the KAM and Nekhoroshev theorems[END_REF], this approach was already used in the model problem of perturbations of constant vector fields on the torus; the aim of this article is therefore to explain how to adapt the arguments of [START_REF] Bounemoura | A Diophantine duality applied to the KAM and Nekhoroshev theorems[END_REF] to the context of real-analytic non-degenerate Hamiltonian systems close to integrable.

Acknowledgements:

The first author would like to thank the organizers of the conference "Geometry, Dynamics, Integrable Systems -GDIS 2013" in Izhevsk, Russia, for the invitation to give a talk on this topic, and IMPA, Rio de Janeiro, Brazil, for its hospitality during the preparation of this work. The second author is partially supported by Agence Nationale de la Recherche (project HAMOT, ref. ANR 2010 BLAN-0115), and thanks Michel Waldschmidt for his advice.

Statements

As explained in the Introduction, the result that we will prove here is not new, only the method of proof is. For convenience, we will follow the very nice survey [START_REF] Pöschel | A lecture on the classical KAM theory[END_REF] for the exposition of the statements. Compared to [START_REF] Pöschel | A lecture on the classical KAM theory[END_REF], we decided for simplicity to focus on the persistence of a single invariant torus instead of a Cantor family of invariant tori; on the other hand, our frequency will be assumed to satisfy the Bruno-Rüssmann condition, which is more general than the classical Diophantine condition.

Setting

Recall that n ≥ 2 is an integer, T n = R n /Z n and let D ⊆ R n be an open domain containing the origin. For a small parameter ǫ ≥ 0, we consider a Hamiltonian function

H : D × T n → R of the form H(p, q) = h(p) + ǫf (p, q), ∇h(0) = ω 0 = (1, ω0 ) ∈ R n , ω0 ∈ [-1, 1] n-1 . ( * )
Assuming that the vector ∇h(0) = ω 0 is non-zero, it can always be written as above, reordering its components and re-scaling the Hamiltonian if necessary. The integrable Hamiltonian h is said to be non-degenerate at the origin if the map ∇h : D → R n is a local diffeomorphism at the origin. Upon restricting D if necessary, we may assume that ∇h is actually a global diffeomorphism. The Hamiltonian H is said to be real-analytic on D × T n , where D denotes the closure of D in R n , if it is analytic on a fixed (that is, independent of ǫ) neighborhood of D × T n in R n × T n . This implies that H can be extended as a holomorphic function on a fixed complex neighborhood of D × T n in C n × T n C , where T n C = C n /Z n , which is real-valued for real arguments.

Bruno-Rüssmann condition

For Q ≥ 1, let us define the function Ψ = Ψ ω 0 by Ψ(Q) = sup{|k • ω 0 | -1 | k ∈ Z n , 0 < |k| 1 ≤ Q} ∈ [1, +∞].
(2.1)

Recall that the vector ω 0 is said to be non-resonant if k • ω 0 = 0 implies k = 0 ∈ Z n , which is equivalent to Ψ(Q) being finite for all Q ≥ 1. We say that ω 0 satisfies the Bruno-Rüssmann condition if it is non-resonant and

+∞ 1 Q -2 ln(Ψ(Q))dQ < ∞. (BR) Now let us define two other functions ∆ = ∆ ω 0 and ∆ * = ∆ * ω 0 by ∆(Q) = QΨ(Q) for Q ≥ 1, and ∆ * (x) = sup{Q ≥ 1 | ∆(Q) ≤ x} for x ≥ ∆(1). We obviously have ∆ * (∆(Q)) = Q and ∆(∆ * (x)) ≤ x. Moreover, it is not hard to check (see [BF13], Appendix A) that Ψ satisfies (BR) if and only if ∆ * satisfies +∞ ∆(1) (x∆ * (x)) -1 dx < ∞.
(2.2)

Classical KAM theorem

Consider the map Θ 0 : T n → D × T n given by Θ 0 (q) = (0, q): this is a real-analytic torus embedding such that Θ 0 (T n ) is invariant by the Hamiltonian flow of H 0 and quasi-periodic with frequency ω 0 . The classical KAM theorem states that this invariant quasi-periodic torus is preserved, being only slightly deformed, by an arbitrary small perturbation, provided h is non-degenerate, H analytic and ω 0 satisfies the Bruno-Rüssmann condition.

Theorem 2.1. Let H be as in ( * ), with h non-degenerate and H real-analytic, and assume that Ψ = Ψ ω 0 satisfies (BR). For ǫ small enough, there exists a real-analytic torus embedding

Θ ω 0 : T n → D × T n such that Θ ω 0 (T n
) is invariant by the Hamiltonian flow of H and quasiperiodic with frequency ω 0 . Moreover, Θ ω 0 converges uniformly to Θ 0 as ǫ goes to zero.

As in [START_REF] Pöschel | A lecture on the classical KAM theory[END_REF], Theorem 2.1 will be deduced from a KAM theorem for a Hamiltonian "with parameters", for which a quantitative statement is given below.

KAM theorem with parameters

Let us now consider a different setting. Given r, s, h real numbers such that 0

≤ r ≤ 1, 0 ≤ s ≤ 1, 0 ≤ h ≤ 1, we let D r,s = {I ∈ C n | |I| < r} × {θ ∈ T n C = C n /Z n | |Im(θ)| < s} and O h = {ω ∈ C n | |ω -ω 0 | < h}
be complex neighborhoods of respectively {0}×T n and ω 0 , where | . | stands for the supremum norm of vectors. For a small parameter ε ≥ 0, consider a function H, which is bounded and real-analytic on D r,s × O h , and of the form

H(I, θ, ω) = N (I, ω) + P (I, θ, ω), N (I, ω) = e(ω) + ω • I, |P | r,s,h ≤ ε, ( * * ) where |P | r,s,h = sup (I,θ,ω)∈Dr,s×O h |P (I, θ, ω)|.
The function H should be considered as a real-analytic Hamiltonian on D r,s , depending analytically on a parameter ω ∈ O h ; for a fixed parameter ω ∈ O h , when convenient, we will write

H ω (I, θ) = H(I, θ, ω), N ω (I) = N (I, ω), P ω (I, θ) = P (I, θ, ω). Let B = {I ∈ R n | |I| < r} so that B × T n
is the real part of the domain D r,s , and Φ 0 : T n → B × T n be the map given by Φ 0 (θ) = (0, θ). Then Φ 0 (T n ) is an embedded real-analytic torus in B × T n , invariant by the Hamiltonian flow of N ω 0 and quasi-periodic with frequency ω 0 . The next theorem states that this quasi-periodic torus will persist, being only slightly deformed, as an invariant torus not for the Hamiltonian flow of H ω 0 but for the Hamiltonian flow of H ω, where ω is a parameter close to ω 0 , provided ε is sufficiently small and ω 0 satisfies the Bruno-Rüssmann condition. Here is a more precise statement.

Theorem 2.2. Let H be as in ( * * ), with ∆ * = ∆ * ω 0 satisfying (2.2). Then there exist positive constants c 1 ≤ 1, c 2 ≤ 1, c 3 ≤ 1, c 4 ≥ 1 and c 5 ≥ 1 depending only on n such that if

εr -1 ≤ c 1 h ≤ c 2 (Q 0 Ψ(Q 0 )) -1 (2.3)
where Q 0 ≥ 1 is sufficiently large so that

Q -1 0 + (ln 2) -1 +∞ ∆(Q 0 ) dx x∆ * (x) ≤ c 3 s, (2.4)
there exist a real-analytic torus embedding Φ ω 0 : T n → B × T n and a vector ω ∈ R n such that Φ ω 0 (T n ) is invariant by the Hamiltonian flow of H ω and quasi-periodic with frequency ω 0 . Moreover,

Φ ω 0 is real-analytic on T n s/2 = {θ ∈ T n C | |Im(θ)| < s/2} and we have the estimates |W (Φ ω 0 -Φ 0 )| s/2 ≤ c 4 ε(rh) -1 , |ω -ω 0 | ≤ c 5 εr -1 , (2.5)
where W = Diag(r -1 Id, Q -1 0 Id). Theorem 2.1 follows directly from Theorem 2.2, introducing the frequencies ω = ∇h(p) as independent parameters and compensating the shift of frequency ω -ω 0 using the nondegeneracy assumption on h. This deduction is classical but for completeness we will repeat the details below, following [START_REF] Pöschel | A lecture on the classical KAM theory[END_REF].

3 Proof of Theorem 2.1 assuming Theorem 2.2

In this section, we assume Theorem 2.2 and we show how it implies Theorem 2.1.

Proof of Theorem 2.1. For p 0 ∈ D, we expand h in a small neighborhood of p 0 : writing p = p 0 + I for I close to zero, we get

h(p) = h(p 0 ) + ∇h(p 0 ) • I + 1 0 (1 -t)∇ 2 h(p 0 + tI)I • Idt.
Since ∇h : D → Ω is a diffeomorphism, instead of p 0 we can use ω = ∇h(p 0 ) as a new variable, and we write h(p) = e(ω)

+ ω • I + P h (I, ω)
with e(ω) = h(∇ -1 (ω)) and

P h (I, ω) = 1 0 (1 -t)∇ 2 h(∇ -1 (ω) + tI)I • Idt. Letting θ = q and P ǫ (I, θ, ω) = ǫf (p, q) = ǫf (p 0 + I, θ) = ǫf (∇ -1 (ω) + I, θ),
we can eventually define

H(I, θ, ω) = H(p, q) = e(ω) + ω • I + P h (I, ω) + P ǫ (I, θ, ω) = e(ω) + ω • I + P (I, θ, ω).
This Hamiltonian is obviously real-analytic in (I, θ, ω), hence we can fix some small 0 < s < 1 and 0 < h < 1 so that P is real-analytic on the complex domain D r,s × O h for all sufficiently small 0 < r < 1. Moreover, as Ψ = Ψ ω 0 satisfies (BR), ∆ * = ∆ * ω 0 satisfies (2.2), and choosing Q 0 = Q 0 (s) sufficiently large so that (2.4) is satisfied, we may assume, restricting h if necessary, that the second inequality of (2.3) holds true, namely c 1 h ≤ c 2 (Q 0 Ψ(Q 0 )) -1 . In the same way, we may also assume that the real part of O h is contained in Ω. Now since P (I, θ, ω) = P h (I, ω) + P ǫ (I, θ, ω), we have

|P | r,s,h ≤ ε = M r 2 + F ǫ where M = sup p∈D |∇ 2 h(p)|, F = sup (p,q)∈D×T n |f (p, q)|.
Therefore we choose r = (M -1 F ǫ) 1/2 to have ε = 2F ǫ, and assuming ǫ ≤ (4M F ) -1 c 2 1 h 2 , we have

εr -1 = 2F ǫ(M F -1 ǫ -1 ) 1/2 = 2(M F ǫ) 1/2 ≤ c 1 h,
hence the first inequality of (2.3) is satisfied. So Theorem 2.2 can be applied: there exist a real-analytic torus embedding Φ ω 0 : T n → B × T n and a vector ω ∈ R n such that Φ ω 0 (T n ) is invariant by the Hamiltonian flow of H ω and quasi-periodic with frequency ω 0 . Moreover,

Φ ω 0 is real-analytic on T n s/2 = {θ ∈ T n C | |Im(θ)| < s/2}
and we have the estimates

|W (Φ ω 0 -Φ 0 )| s/2 ≤ c 4 ε(rh) -1 , |ω -ω 0 | ≤ c 5 εr -1 , (3.1)
where W = Diag(r -1 Id, Q -1 0 Id). Since ω is real and the real part of O h is contained in Ω, there exists Ĩ close to zero such that ∇h( Ĩ) = ω. Now observe that an orbit (I(t), θ(t)) for the Hamiltonian H ω corresponds to an orbit (p(t), q(t)) = ( Ĩ + I(t), θ(t)) for our original Hamiltonian. Hence, if we define T : B × T n → D × T n by T (I, θ) = ( Ĩ + I, θ) and

Θ ω 0 = T • Φ ω 0 : T n → D × T n ,
then Θ ω 0 is a real-analytic torus embedding such that Θ ω 0 (T n ) is invariant by the Hamiltonian flow of H and quasi-periodic with frequency ω 0 .

Moreover, as ǫ goes to zero, it follows from (3.1) that Φ ω 0 converges uniformly to Φ 0 and ω converges to ω 0 , hence T converges uniformly to the identity which eventually implies that Θ ω 0 converges uniformly to Θ 0 .

Proof of Theorem 2.2

This section is devoted to the proof of Theorem 2.2, in which we will construct, by an iterative procedure, a vector ω close to ω 0 and a real-analytic torus embedding Φ ω 0 whose image is invariant by the Hamiltonian flow of H ω. We start, in §4.1, by recalling the Diophantine result of [START_REF] Bounemoura | A Diophantine duality applied to the KAM and Nekhoroshev theorems[END_REF] which will be crucial in our approach. Then, in §4.2, we describe an elementary step of our iterative procedure, and finally, in §4.3, we will show one can perform infinitely many steps to obtain a convergent scheme.

In this section, for simplicity, we shall adopt the following notation: given positive real numbers u and v, we will write u <• v (respectively u •< v) if, for some constant C ≥ 1 which depends only on n and could be made explicit, we have u ≤ Cv (respectively Cu ≤ v).

Approximation by rational vectors

Recall that we have written ω 0 = (1, ω0 ) ∈ R n with ω0 ∈ [-1, 1] n-1 . For a given Q ≥ 1, it is always possible to find a rational vector v = (1, p/q) ∈ Q n , with p ∈ Z n-1 and q ∈ N, which is a Q-approximation in the sense that |qω 0 -qv| ≤ Q -1 , and for which the denominator q satisfies the upper bound q ≤ Q n-1 : this is essentially the content of Dirichlet's theorem on simultaneous rational approximations, and it holds true without any assumption on ω 0 . In our situation, since we have assumed that ω 0 is non-resonant, it is not hard to see that there exist not only one, but n linearly independent rational vectors in Q n which are Q-approximations. Moreover, one can obtain not only linearly independent vectors, but rational vectors v 1 , . . . , v n of denominators q 1 , . . . , q n such that the associated integer vectors q 1 v 1 , . . . , q n v n form a Zbasis of Z n . However, the upper bound on the corresponding denominators q 1 , . . . , q n is necessarily larger than Q n-1 , and is given by a function of Q that we can call here Ψ ′ = Ψ ′ ω 0 (see [START_REF] Bounemoura | A Diophantine duality applied to the KAM and Nekhoroshev theorems[END_REF] for more precise and general information, but note that in this reference, Ψ ′ was denoted by Ψ and Ψ, which we defined in (2.1), was denoted by Ψ ′ ). A consequence of the main Diophantine result of [START_REF] Bounemoura | A Diophantine duality applied to the KAM and Nekhoroshev theorems[END_REF] is that this function Ψ ′ is in fact essentially equivalent to the function Ψ.

Proposition 4.1. Let ω 0 = (1, ω0 ) ∈ R n be a non-resonant vector, with ω0 ∈ [-1, 1] n-1 . For any 1 •< Q, there exist n rational vectors v 1 , . . . , v n , of denominators q 1 , . . . , q n , such that q 1 v 1 , . . . , q n v n form a Z-basis of Z n and for j ∈ {1, . . . , n},

|ω 0 -v j | <• (q j Q) -1 , 1 ≤ q j <• Ψ(Q).
For a proof, we refer to [BF13], Theorem 2.1 and Proposition 2.3. Now given a q-rational vector v and a function P defined on D r,s × O h , we define

[P ] v (I, θ, ω) = 1 0 P (I, θ + tqv, ω)dt.
Given n rational vectors v 1 , . . . , v n , we let

[P ] v 1 ,...,v d = [• • • [P ] v 1 • • • ] v d . Finally we define [P ](I, ω) = T n P (I, θ, ω)dθ.
A consequence of the fact that the vectors q 1 v 1 , . . . , q n v n form a Z-basis of Z n is contained in the following proposition.

Proposition 4.2. Let v 1 , . . . , v n be rational vectors, of denominators q 1 , . . . , q n , such that q 1 v 1 , . . . , q n v n form a Z-basis of Z n , and P a function defined on D r,s × O h . Then

[P ] v 1 ,...,vn = [P ].
A proof of this proposition can be found in [START_REF] Bounemoura | Normal forms, stability and splitting of invariant manifolds I. Gevrey Hamiltonians[END_REF], Corollary 6.

KAM step

Now we describe an elementary step of our iterative procedure. To our Hamiltonian H, we will apply transformations of the form F = (Φ, ϕ) : (I, θ, ω) → (Φ(I, θ, ω), ϕ(ω)) which consist of a parameter-depending change of coordinates Φ and a change of parameters ϕ. Moreover, our change of coordinates will be of the form Φ = (U, V ), where U is affine in I and V is independent of I , and will be symplectic for each fixed parameter ω. It is easy to check that such transformations F = (Φ, ϕ) form a group under composition.

From now on, we fix a positive constant η sufficiently small (one could take, for instance, η = 1/66).

Proposition 4.3. Let H be as in ( * * ), with ω 0 = (1, ω0 ) ∈ R n non-resonant, consider 0 < σ < s and 1 •< Q, and assume that

εr -1 •< h •< (QΨ(Q)) -1 , 1 •< Qσ. (4.1)
Then there exists a real-analytic transformation

F = (Φ, ϕ) : D ηr,s-σ × O h/4 → D r,s × O h , such that H • F = N + + P + with N + (I, ω) = e + (ω) + ω • I and |P + | ηr,s-σ,h/4 ≤ ηε/8.
Moreover, we have the estimates

|W (Φ -Id)| ηr,s-σ,h <• (rσ) -1 Ψ(Q)ε, |W (DΦ -Id)W -1 | ηr,s-σ,h <• (rσ) -1 Ψ(Q)ε, |ϕ -Id| h/4 <• εr -1 , h|Dϕ -Id| h/4 <• εr -1 ,
where W = Diag(r -1 Id, σ -1 Id).

Proof. We divide the proof of the KAM step in six small steps. Except for the last one, everything will be uniform in ω ∈ O h , so for simplicity, in the first five steps we will drop the dependence on the parameter ω ∈ O h . Let us first notice that (4.1) implies the following five inequalities:

h •< (QΨ(Q)) -1 , ε •< σrΨ(Q) -1 , ε •< r(QΨ(Q)) -1 , 1 •< Qσ, εr -1 •< h. (4.2)
1. Affine approximation of P Let P be the linearization of P in I at I = 0; that is,

P (I, θ) = P (0, θ) + ∂ I P (0, θ) • I.
Using Cauchy's estimate, it is easy to see that | P | r,s <• ε. Moreover, using Lemma A.1, we have

|P -P | 2ηr,s ≤ (2η) 2 (1 -2η) -1 ε ≤ ηε/16 (4.3)
where we used in the second inequality that η is small enough.

Rational approximations of ω 0

Since ω 0 is non-resonant, given 1 •< Q, we can apply Proposition (4.1): there exist n rational vectors v 1 , . . . , v n , of denominators q 1 , . . . , q n , such that q 1 v 1 , . . . , q n v n form a Z-basis of Z n and for j ∈ {1, . . . , n},

|ω 0 -v j | <• (q j Q) -1 , 1 ≤ q j <• Ψ(Q).

Rational approximations of ω ∈ O h

For any ω ∈ O h , using the first inequality in (4.2) and q j <• Ψ(Q), we have

|ω -v j | ≤ |ω -ω 0 | + |ω 0 -v j | <• h + (q j Q) -1 <• (QΨ(Q)) -1 + (q j Q) -1 <• (q j Q) -1 .
(4.4)

Successive rational averagings

Let P 1 = P , and define inductively P j+1 = [P j ] v j for 1 ≤ j ≤ n. Let us also define F j , for 1 ≤ j ≤ n, by F j (I, θ) = q j 1 0 (P j -P j+1 )(I, θ + tq j v j )tdt and N j by N j (I) = e(ω) + v j • I. It is then easy to check, by a simple integration by parts, that the equations {F j , N j } = P j -P j+1 , 1 ≤ j ≤ n, (4.5) are satisfied, where { . , . } denotes the usual Poisson bracket. Moreover, we obviously have the estimates

|P j | r,s ≤ | P | r,s <• ε (4.6) and |F j | r,s ≤ q j |P j | r,s <• Ψ(Q)ε. (4.7)
Next, for any 0 ≤ j ≤ n, define r j = r -(2n) -1 jr and s j = s -n -1 jσ. Obviously r j > 0 whereas s j > 0 follows from σ < s. Using (4.7) and Cauchy's estimate, we have

|∂ θ F j | r j ,s j ≤ n(jσ) -1 |F j | r,s <• σ -1 Ψ(Q)ε, |∂ I F j | r j ,s j ≤ 2n(jr) -1 |F j | r,s <• r -1 Ψ(Q)ε,
and together with the second inequality of (4.1) with a suitable implicit constant, we can ensure that

|∂ θ F j | r j ,s j ≤ (2n) -1 r, |∂ I F j | r j ,s j ≤ n -1 σ.
This implies that for 1 ≤ j ≤ n, the time-one map X 1 F j of the Hamiltonian flow of F j defines a symplectic real-analytic embedding

X 1 F j = (U j , V j ) : D r j ,s j → D r j-1 ,s j-1 .
Moreover, as P is affine in I then so are the F j , for 1 ≤ j ≤ n, and therefore U j is affine in I and V j is independent of I, and we also have the estimates

|U j -Id| r j ,s j ≤ |∂ θ F j | r j ,s j <• σ -1 Ψ(Q)ε, |V j -Id| r j ,s j ≤ |∂ I F j | r j ,s j <• r -1 Ψ(Q)ε. (4.8)
The Jacobian of X 1 F j is given by the matrix

DX 1 F j = ∂ I U j ∂ θ U j 0 ∂ θ V j .
If we define r + j = r -(4n) -1 jr and s j = s -(2n) -1 jσ, then (4.7) and Cauchy's estimate also implies that

|∂ θ F j | r + j ,s + j <• σ -1 Ψ(Q)ε, |∂ I F j | r + j ,s + j <• r -1 Ψ(Q)ε,
and, as r + j -r j = (4n) -1 jr and s + j -s j = (2n) -1 jσ, a further Cauchy's estimate proves that

|∂ I U j -Id| r j ,s j <• (rσ) -1 Ψ(Q)ε, |∂ θ V j -Id| r j ,s j <• (rσ) -1 Ψ(Q)ε, |∂ θ U j | r j ,s j <• σ -2 Ψ(Q)ε.
The estimates (4.8) and the above estimates can be conveniently written as

|W (X 1 F j -Id)| r j ,s j <• (rσ) -1 Ψ(Q)ε, |W (DX 1 F j -Id)W -1 | r j ,s j <• (rσ) -1 Ψ(Q)ε, (4.9)
where W = Diag(r -1 Id, σ -1 Id). Let S j = ω • I -v j • I so that N = N j + S j , and let H j = N + P j . Writing H j = N + P j = N j + S j + P j and using the equality (4.5), a standard computation based on Taylor's formula with integral remainder gives

H j • X 1 F j = N + [P j ] v j + Pj = N + P j+1 + Pj with Pj = 1 0 {(1 -t)P j+1 + tP j + S j , F j } • X t F j dt
and where X t F j is the time-t map of the Hamiltonian flow of F j . Using (4.4), (4.6), (4.7), the definition of the Poisson bracket and Cauchy's estimate, on easily obtains

| Pj | r j ,s j <• (σr) -1 Ψ(Q)ε 2 + (Qσ) -1 ε <• (Qσ) -1 ε (4.10)
where the last inequality follows from the third inequality of (4.2).

Change of coordinates

For 1

≤ j ≤ n, let Φ j = X 1 F 1 • • • • • X 1 F j : D r j ,s j → D r,s .
Since H 1 = N + P , by a straightforward induction we have

H 1 • Φ j = (N + P ) • Φ j = N + P j+1 + P + j
where P + j is defined inductively by P + 1 = P1 and P + j+1 = Pj+1 + P + j • X 1 F j+1 for 1 ≤ j ≤ n -1. Let Φ = Φ n , and first note that Φ = (U, V ) where U is affine in I and V is independent of I, since each X 1 F j is of this form. Moreover, Φ : D r/4,s-σ → D r,s , so in particular Φ : D ηr,s-σ → D r,s as η is small enough, and using (4.9) and a classical telescopic argument, we have the estimates

|W (Φ -Id)| ηr,s-σ <• (rσ) -1 Ψ(Q)ε, |W (DΦ -Id)W -1 | ηr,s-σ <• (rσ) -1 Ψ(Q)ε.
Concerning P + n , using (4.10) and the fourth equality of (4.2) with a suitable implicit constant, we can ensure that

|P + n | ηr,s-σ <• (Qσ) -1 ε ≤ ηε/16
. Now as H = N + P = N + P + P -P = H 1 + P -P , this gives

H • Φ = H 1 • Φ + (P -P ) • Φ = N + P n+1 + P + n + (P -P ) • Φ.
We finally set P + = P + n + (P -P ) • Φ, and as

P n+1 = [• • • [ P ] v 1 • • • ] vn = [ P ] v 1 ,.
..,vn , by Proposition 4.2, P n+1 = [ P ], we arrive at

H • Φ = N + [ P ] + P + .
Using the second inequality of (4.2) with an appropriate implicit constant, we may assume that the image of Φ actually sends D ηr,s-σ into D 2ηr,s , and together with (4.3), we obtain the estimate

Iterations and convergence

Recall that η has been fixed before Proposition 4.3, and now we define, for i ∈ N, the following decreasing geometric sequences:

ε i = (η/8) i ε, r i = η i r, h i = (1/4) i h.
Next, for a constant Q 0 to be chosen below, we define ∆ i and Q i , i ∈ N, by

∆ i = 2 i ∆(Q 0 ), Q i = ∆ * (∆ i ) = sup{Q ≥ 1 | ∆(Q) ≤ ∆ i },
and then we define σ i , i ∈ N, by

σ i = CQ -1 i
where C ≥ 1 is a constant, depending only n, sufficiently large so that the last part of (4.1) is satisfied for σ = σ i and Q = Q i . Finally, we define s i , i ∈ N, by s 0 = s and s i+1 = s i -σ i for i ∈ N.

We claim that, assuming ∆ * satisfies (2.2), we can choose Q 0 sufficiently large so that lim

i→+∞ s i ≥ s/2 ⇐⇒ i∈N σ i ≤ s/2. Indeed, since Q i = ∆ * (∆ i ) = ∆ * 2 i ∆(Q 0 ) , we have i≥1 Q -1 i = i≥1 1 ∆ * (2 i ∆(Q 0 )) ≤ +∞ 0 dy ∆ * (2 y ∆(Q 0 )) = (ln 2) -1 +∞ ∆(Q 0 ) dx x∆ * (x) < +∞
where the last integral converges since ∆ * satisfies (2.2). Now as σ i = CQ -1 i , we have

i∈N σ i = C i∈N Q -1 i = CQ -1 0 + C i≥1 Q -1 i ≤ CQ -1 0 + C(ln 2) -1 +∞ ∆(Q 0 ) dx x∆ * (x)
≤ s/2 provided we choose Q 0 sufficiently large in order to have

Q -1 0 + (ln 2) -1 +∞ ∆(Q 0 ) dx x∆ * (x) ≤ (2C) -1 s. (4.11)
Proposition 4.4. Let H be as in ( * * ), with ∆ * = ∆ * ω 0 satisfying (2.2), and fix Q 0 sufficiently large so that (4.11) is satisfied. Assume that

εr -1 •< h •< ∆(Q 0 ) -1 .
(4.12)

Then, for each i ∈ N, there exists a real-analytic transformation

F i : D r i ,s i × O h i → D r,s × O h , such that H • F i = N i + P i with N i (I, ω) = e i (ω) + ω • I and |P i | r i ,s i ,h i ≤ ε i . Moreover, we have the estimates | W0 (F i+1 -F i )| r i+1 ,s i+1 ,h i+1 <• ε i (r i h i ) -1
where W0 = Diag(r -1 0 Id, σ -1 0 Id, h -1 0 Id).

Proof. For i = 0, we let F 0 be the identity and there is nothing to prove. The general case follows by an easy induction. Indeed, assume that the statement holds true for some i ∈ N, and let

H i = H • F i = N i + P i , defined on D r i ,s i × O h i .
We want to apply Proposition (4.3) to this Hamiltonian, with ε = ε i , r = r i , s = s i , h = h i , σ = σ i and Q = Q i . First, we need to check that 0 < σ i < s i and 1 •< Q i . The first condition is equivalent to i l=0 σ l < s, whereas the second condition is implied by 1 •< Q 0 , and it is easy to see that both conditions are satisfied by the choice of Q 0 in (4.11), as s < 1. Then we need to check that the conditions

ε i r -1 i •< h i •< ∆(Q i ) -1 , 1 •< Q i σ i , are satisfied. Since ∆(Q i ) = ∆(∆ * (∆ i )) ≤ ∆ i , (4.13)
it is sufficient to check the conditions

ε i r -1 i •< h i •< ∆ -1 i , 1 •< Q i σ i . (4.14)
The second condition of (4.14) is satisfied, for all i ∈ N, simply by the choice of the constant in the definition of σ i . As for the first condition of (4.14), it is satisfied for i = 0 by (4.12), and since the sequences ε i r -1 i , h i and ∆ -1 i decrease at a geometric rate with respective ratio 1/8, 1/4 and 1/2, the first condition of (4.14) is therefore satisfied for any i ∈ N. Hence Proposition (4.3) can be applied: there exists a real-analytic transformation

F i = (Φ i , ϕ i ) : D r i+1 ,s i+1 × O h i+1 → D r i ,s i × O h i ,
such that H i •F i = N i,+ + P i,+ with N i,+ (I, ω) = e i,+ (ω)+ ω •I and |P i,+ | r i+1 ,s i+1 ,h i+1 ≤ ε i+1 . Moreover, we have the estimates

|W i (Φ i -Id)| r i+1 ,s i+1 ,h i+1 <• (r i σ i ) -1 Ψ(Q i )ε i , |W i (DΦ-Id)W -1 i | r i+1 ,s i+1 ,h i+1 <• (r i σ i ) -1 Ψ(Q i )ε i , |ϕ i -Id| h i+1 <• ε i r -1 i , h i |Dϕ i -Id| h i+1 <• ε i r -1 i , where W i = Diag(r -1 i Id, σ -1 i Id). We just need to set F i+1 = F i • F i , N i+1 = N i,+ and P i+1 = P i,+ to have H • F i+1 = H i • F i = N i+1 + P i+1 with N i+1 (I, ω) = e i+1 (ω) + ω • I and |P i+1 | r i+1 ,s i+1 ,h i+1 ≤ ε i+1 . It remains to estimate F i+1 -F i . Setting Wi = Diag(r -1 i Id, σ -1 i Id, h -1 i Id), the estimates above implies | Wi (F i -Id)| r i+1 ,s i+1 ,h i+1 <• max{(r i σ i ) -1 Ψ(Q i )ε i , ε i (r i h i ) -1 } <• ε i (r i h i ) -1 (4.15) since σ -1 i Ψ(Q i ) = Q i Ψ(Q i ) •< h -1 i , and similarly | Wi (DF i -Id) W -1 i | r i+1 ,s i+1 ,h i+1 <• ε i (r i h i ) -1 . (4.16)
Using a classical telescoping argument, the fact that | Wi-1 Wi | ≤ 1 and the estimate (4.16), we get

| W0 DF i W -1 i | r i+1 ,s i+1 ,h i+1 <• i l=0 1 + ε l (r l h l ) -1 <• 1 (4.17)
as ε l (r l h l ) -1 decreases geometrically. Then, from the mean value theorem, we have

| W0 (F i+1 -F i )| r i+1 ,s i+1 ,h i+1 = | W0 (F i • F i -F i )| r i+1 ,s i+1 ,h i+1 ≤ | W0 DF i W -1 i | r i+1 ,s i+1 ,h i+1 | Wi (F i -Id)| r i+1
,s i+1 ,h i+1 , and this estimate, together with (4.15) and (4.17), implies

| W0 (F i+1 -F i )| r i+1 ,s i+1 ,h i+1 <• ε i (r i h i ) -1
which is the required estimate.

We can finally conclude the proof of Theorem 2.2.

Proof of Theorem 2.2. Recall that we are given ε, r, s, h and that we fixed η small enough to define the sequences ε i , r i , h i , and then we chose Q 0 ≥ 1 satisfying (4.11) to define the sequences ∆ i , Q i , σ i and s i . Moreover, we have lim

i→+∞ ε i = lim i→+∞ r i = lim i→+∞ h i = 0, lim i→+∞ s i ≥ s/2. (4.18)
Now the condition (2.3) implies the condition (4.12) and Proposition 4.4 can be applied: for each i ∈ N, there exists a real-analytic transformation

F i : D r i ,s × O h i → D r,s × O h ,
such that H • F i = N i + P i with N i (I, ω) = e i (ω) + ω • I and |P i | r i ,s i ,h i ≤ ε i . Moreover, we have the estimates

| W0 (F i+1 -F i )| r i+1 ,s i+1 ,h i+1 <• ε i (r i h i ) -1 . (4.19)
As ε i (r i h i ) -1 decreases geometrically, these estimates and (4.18) show that the transformations F i = (Φ i , ϕ i ) converge uniformly, as i goes to infinity, to a map from which one deduces that

|W (Φ ω 0 -Φ 0 )| s/2 <• ε(rh) -1 , |ϕ(ω 0 ) -ω 0 | <• εr -1 ,
where W = Diag(r -1 Id, Q -1 0 Id), since r 0 = r and σ 0 = CQ -1 0 . To conclude, fix i ∈ N and ω ∈ O h i . Then, denoting X Hω , X N i ω and X P i ω the Hamiltonian vector fields associated to H ω , N i ω and P i ω , we have

X H ϕ i (ω) • Φ i ω -DΦ i ω X N i ω = DΦ i ω (Φ i ω ) * X H ϕ i (ω) -X N i ω = DΦ i ω X H ϕ i (ω) •Φ i ω -X N i ω = DΦ i ω X P i ω (4.20)
where we used the fact that Φ i ω is symplectic in the second equality, and the relation

H ϕ i (ω) • Φ i ω -N i ω = P i ω
in the last equality. Using the inequality |P i | r i ,s i ,h i ≤ ε i together with Cauchy's estimate, one obtains that, as i goes to infinity, X P i ω converges to zero uniformly on D 0,s/2 , whereas DΦ i ω is uniformly bounded by the estimate (4.17). Hence the right-hand side of (4.20) converges uniformly to zero, and so does the left-hand side: at the limit we obtain the equality

X H ω • Φ ω 0 = DΦ ω 0 .X ω 0
since X N i ω converges to the constant vector field X ω 0 = ω 0 on T n . From this equality it follows that the embedded torus Φ ω 0 (T n ) is invariant by the Hamiltonian flow of H ω and quasi-periodic with frequency ω 0 , and this ends the proof.

A Technical lemmas

In this appendix, we state two technical lemmas that were used in the proof of Propostion 4.3. The first one deals with the estimate of the remainder of the Taylor's expansion at order one of an analytic function. For a proof, we refer to [START_REF] Pöschel | A lecture on the classical KAM theory[END_REF], Lemma A.3.

  |P + | ηr,s-σ ≤ |P + n | ηr,s-σ +|(P -P )•Φ| ηr,s-σ ≤ |P + n | ηr,s-σ +|P -P | 2ηr,s-σ ≤ ηε/16+ηε/16 = ηε/8.6. Change of frequenciesAs P is affine in I, [ P ] is independent of θ and of the form [ P ](I, ω) = c(ω) + ν(ω) • I, with c(ω) ∈ C and ν(ω) ∈ C n , and therefore(N + [ P ])(I, ω) = e(ω) + c(ω) + (ω + ν(ω)) • I = e + (ω) + (ω + ν(ω)) • I. Since ν = ∂ I [ P ],Cauchy's estimate together with the fifth inequality of (4.2) implies that the map ν satisfy the estimate|ν| h <• εr -1 ≤ h/4.Setting f (ω) = ω + ν(ω), we can apply Lemma A.2 to find a real-analytic inverse ϕ :O h/4 → O h to f satisfying the estimates |ϕ -Id| h/4 <• εr -1 , h|Dϕ -Id| h/4 <• εr -1 .Eventually, we setN + = (N + [ P ]) • ϕ and F = (Φ, ϕ) : D ηr,s-σ × O h/4 → D r,s × O h ,and we obtainH • F = N + + P + as wanted, with the desired estimates on F and on P + .

F

  = (Φ ω 0 , ϕ) : {0} × T n s/2 × {ω 0 } = D 0,s/2 × O 0 → D r,s × O h which consists of a real map ϕ : {ω 0 } = O 0 → O h and a real-analytic embedding Φ ω 0 : T n s/2 → D r,s where, for simplicity, we identified D 0,s/2 = {0} × T n s/2 with T n s/2 . Note that by reality, ϕ(ω 0 ) = ω ∈ R n and Φ ω 0 (T n ) ⊆ B × T n . Moreover, from the estimate (4.19) and a usual telescopic argument, | W0 (F -Id)| s/2 <• ε(rh) -1

Lemma A. 1 .

 1 Let P be an analytic function defined on D r,s andP (I, θ) = P (0, θ) + ∂ I P (0, θ) • I.Then, for any 0 < c < 1, we have the estimate|P -P | cr,s ≤ c 2 (1 -c) -1 |P | r,s .For a proof (of a more general statement), we refer to [Alb07], Lemma A.5. Then we need a quantitative version of the implicit function theorem for a real-analytic map.Lemma A.2. Let f : O h → C n be a real-analytic map satisfying |f -Id| h ≤ δ ≤ h/4. Then f has a real-analytic inverse ϕ : O h/4 → O h which satisfies |ϕ -Id| h/4 ≤ δ, h/4|Dϕ -Id| h/4 ≤ δ.


Fuzhang Wu
email: fuzhangwu@ia.ac.cn

Weiming Dong
email: weiming.dong@ia.ac.cn

Yan Kong

Xingmei

Jean-Claude Paul

Xiaopeng Zhang
email: xiaopeng.zhang@ia.ac.cn

Content-Based Colour Transfer

Keywords: color transfer, scene content analysis, progressive transfer ACM CCS: Computing methodologies-Image processing

This paper presents a novel content-based method for transferring the colour patterns between images. Unlike previous methods that rely on image colour statistics, our method puts an emphasis on high-level scene content analysis. We first automatically extract the foreground subject areas and background scene layout from the scene. The semantic correspondences of the regions between source and target images are established. In the second step, the source image is re-coloured in a novel optimization framework, which incorporates the extracted content information and the spatial distributions of the target colour styles. A new progressive transfer scheme is proposed to integrate the advantages of both global and local transfer algorithms, as well as avoid the over-segmentation artefact in the result. Experiments show that with a better understanding of the scene contents, our method well preserves the spatial layout, the colour distribution and the visual coherence in the transfer process. As an interesting extension, our method can also be used to re-colour video clips with spatially-varied colour effects.

Introduction

Colour transfer is a practical method to change the appearance of a source image/video according to the colour pattern of a target image. It has various applications in movie post-production, artistic design and photo enhancement. An ideal image colour transfer algorithm should keep the scene of the source image and accurately apply all the dominant colour styles of the target. In many cases, the spatial distribution of the target image should also be presented in the result.

In automatic colour transfer techniques such as [RAGS01, TJT05, PKD07, PR11], they extract various colour statistics from both images and establish specific mapping functions, such that the recoloured source scene shares similar colour theme with the target. In many cases, the low-level colour statistic information cannot fully describe the real content of the image and some regions may be incorrectly coloured during the mapping process. To avoid such visual artefacts, some interactive methods utilize user-specified colour strokes to ensure correct colour transfer between different image regions, therefore achieve desirable results [LWX07, AP10, LSZ12]. However, it can be difficult for an amateur to specify those strokes in a compatible and perceptually coherent manner. Another problem with previous methods is that they do not consider the spatial distribution characteristics when transferring colours, which might damage the specific visual coherence (Figures 1d ande) or even lose important colour styles of the target image (Figures 2d ande) in the result.

To accurately transfer colours between images with minimal manual labour, we present a system which benefits from the image content analysis. The basic inspirations of our method is that the transfer process should be performed between image regions with similar semantic contents, especially when the obviously different colour patterns appear in different regions of the target image (Figure 1). Moreover, previous methods will easily fail if the number of dominant colour styles of the source image is much less than the one of the target image (Figure 2). To address those problems, in this paper, we present a content-based colour transfer technology. We first perform scene analysis to detect the subject areas (salient objects or clarity areas) and recover the background surface layout (sky, ground, vertical). With this content information, the system transfers colours between the corresponding regions on a super-pixel level. For example, our system will separately transfer the sky colours of the target to the sky in the source (if exists) without affecting the colour patterns of other regions. For such corresponding regions, we present a novel local colour transfer algorithm that integrates spatial distribution of target dominant colours in an optimization framework. We also develop a new progressive transfer scheme to integrate the (a) Source Image (b) TargetImage (c) Our Result (d) [START_REF] Pouli | Progressive color transfer for images of arbitrary dynamic range[END_REF] (e) [START_REF] Efros | Using color compatibility for assessing image realism[END_REF] Figure 1: Our method firstly automatically analyses the scene content structure and divide it into different regions such as salient objects, sky and ground. After that, a novel distribution-aware colour transfer process is performed on the corresponding pairs (e.g. transfer the colour style from target sky to source sky). Our method well preserves the colour spatial distribution and the visual coherence in the result (c). We can see that the colour layer effect of the target sky is lost in (d) and (e). advantages of both global and local transfer algorithms. That can also avoid the over-segmentation artefact which often occurs in the results of local colour transfer methods. As a result, all the obvious colour styles, as well as their corresponding spatial distribution in the target image, can be reproduced in the output image without damaging scene contents. To the best of our knowledge, our method is the first trial to challenge this kind of problems in colour transfer research, especially for the example like Figure 2. Moreover, our image colour transfer approach can be efficiently extended to re-colour videos to generate spatially varied colour patterns.

Related Work

Automatic colour transfer algorithm was firstly presented by Reinhard et al. Interactive methods made colour transfer more controllable in the photo editing process. Luan et al. [START_REF] Luan | Color transfer brush[END_REF] introduced a brush by which the user specifies the source and destination image regions for colour transfer. Wen et al. [START_REF] Hsieh C.-H | Example-based multiple local color transfer by strokes[END_REF] used strokes in both the source and target image for multiple local transfers. An and Pellacini [START_REF] Pellacini | User-controllable color transfer[END_REF] used a non-linear constrained parametric model to transfer colours between image regions defined by pairs of strokes. Liu et al. [START_REF] Liu | Selective color transferring via ellipsoid color mixture map[END_REF] presented ellipsoid colour mixture map to realize selective colour transfers. Compared with those interactive frameworks, our image content structure extraction technology can help to maximize the automation.

The concept of colour transfer was extended to other applications. Ya n g et al. [START_REF] Peng L.-K | Automatic mood-transferring between color images[END_REF] presented a mood-transferring method between colour images by using histogram-matching to preserve spatial coherence. Xue et al. [XWT*08] tried to transfer the weathering effects between the input images instead of transferring colour. Murray et al. [START_REF] Skaff | Towards automatic concept transfer[END_REF] modified the colour content of an input image given only a concept specified by a user in natural language. Data-driven methods were presented for image colour enhancement by quantifying image-colour theme difference [WYW*10] and non-rigid dense correspondence [START_REF] Hacohen | Non-rigid dense correspondence with applications for image enhancement[END_REF]. Recently, Chia et al. [CZG*11] proposed a semantic colourization system that leverages the image content on the Internet.

Overview

A block diagram of our system framework is shown in Figure 3. To transfer the colour patterns between the source and target image, we first detect the subject area(s) in both images and recover the surface layout of the backgrounds (Section 4). The content information is then used to guide the colour transfer process. A novel distribution-aware colour transfer algorithm is presented to transfer the colour styles between the corresponding regions of the source and target image (Section 5). The spatial distribution and visual details of the target colours can also be preserved in the result. Furthermore, an extension of the method is proposed to transfer spatial colour distribution features to the video clips (Section 6).

Scene Content Analysis

Understanding the content structures of the input images will facilitate the colour transfer process to generate a natural looking result. For each input image, we detect the subject area(s) and recover the surface layout of the background.

Subject area detection

The detection of subject area depends on the image content. In our system, we set a composition-based detection method as the default operator to automatically extract the subject areas from the input images. The user can also choose another two operators to get a more accurate result when the input images contain defocus effects or faces.

Salient object detection

For normal images with clear backgrounds, the salient objects are the subject areas. We first use a composition-based method [FWT*11] to detect the windows which contain the salient objects. Based on these windows, we then apply Grabcut method [START_REF] Rother | grabcut": Interactive foreground extraction using iterated graph cuts[END_REF] to extract the contour of the objects. Figure 4(a) shows a salient object detection result by our method.

Clarity based detection

For a low depth of field image or close-up photo with blurred background, we always treat the clear area(s) as the subject content. We provide a clarity-based method to help obtain the clear area(s) in an image. We first use the method in [START_REF] Luo | Photo and video quality evaluation: Focusing on the subject[END_REF] to obtain a clarity mask which labels each pixel as clear or blur. Then, the image is over-segmented by applying mean shift segmentation [START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF]. We label a super-pixel as clear if more than half of its pixels are labelled as clear in the clarity mask. An example of our method is shown in Figure 4(b). Disjoint clear areas are treated as different subject areas in our system.

Face detection

Faces are special salient objects in an image, especially for portrait photos. We provide a face detector [START_REF] Zhu | Dynamic cascades for face detection[END_REF] to help locate the windows which contain the faces. Graph-cut [START_REF] Rother | grabcut": Interactive foreground extraction using iterated graph cuts[END_REF] is also employed to extract the contours. Figure 4(c) shows a face detection result.

Background layout recovery

After detecting the subject area(s) in an image, we further segment the background into different semantic regions. We use the method in [START_REF] Hoiem | Recovering surface layout from an image[END_REF] to recover the surface layout of the background. As a result, every pixel in the image is categorized into one of three classes: support (ground), vertical and sky. Based on this categorization, we get a semantic label mask that indicates the pixels' types (e.g. label = 1meansground). Specifically, we treat the pixels with the same label as a whole semantic region in our following transfer method, no matter if these pixels are locate in different disjoint areas or not (Figure 5). This treatment ensures that the disjoint sub-regions with identical semantic label are formed together in the transfer process so as to generate an integrated view in the result, which can avoid the possible discontinuity of the colour patterns. Therefore, the background image is segmented into three parts: sky region, ground region and vertical region, as shown in Figure 4(d) as examples.

In most cases, the segmentation results obtained from both the subject detection and the surface layout recovery are sufficient for our colour transfer framework. If the automatic segmentation is not satisfied, paint selection technique [START_REF] Liu | Paint selection[END_REF] is used to refine the segmentation results.

Semantic regions matching

After extracting the content structures of the input images, we match the semantic parts together and transfer the colour styles between each pair. For the image backgrounds, we separately match the source sky (vertical, ground) to the corresponding target sky (vertical, ground) if they both exist according to the label masks (e.g. Figure 4d, 'red' vertical is matched to 'red' vertical). The matching is straightforward since the semantic regions in the background are unique.

For the salient objects, we can directly construct the matching if there is only one object in both of the input images. However, it will be more complex if there are multiple salient objects in the images. Denote N s and N t as the number of objects extracted from the source and target image separately. If N s >N t , we first randomly sample N t objects from the source image and then find a matching target object t i for each sampled object s i by optimizing the metric:

min {t i } Nt i c s i -c t i ,t i = t j if s i = s j , (1)
where c s(t) i is the centroid of the objects in relative coordinates (normalized to [0, 1] according to its position in the image). We use the one-to-one EMD mapping framework in [START_REF] Bao | Fast local color transfer via dominant colors mapping[END_REF] to optimize the metric. For those unsampled source objects, we set the matching target objects to be the same as their nearest sampled objects in the source image.

For the case N s ≤ N t , we instead sample N s objects from the target image and reformat Equation (1) as min {t i } Ns i c s ic t i to find the optimal matching target objects for all of the source objects. Since we use a location constraint, the object matching can guarantee our final colour transfer result to preserve the spatial distribution of the target colours in object level. A multiple objects transfer result produced by our method is shown in Figure 10.

Based on these matched semantic regions, we perform our colour transfer operations (Section 5) for each pair separately. Moreover, we consider the content structures of input images are different if there is any semantic region in either of the input images that cannot find a matching region in the other image. To solve this problem, we first globally transfer the luminance of the target image to the source by using the method in [START_REF] Ashikhmin | Color transfer between images[END_REF]. Based on this result, we then perform our colour transfer operations between the existing pairs and leaving the other regions unchanged, as shown in Figure 16.

Distribution-Aware Colour Transfer

Utilizing the content structure information of input images, we separately transfer the colour style of each semantic region in the target image to the corresponding one in the source. We present a novel distribution-aware colour transfer algorithm to preserve the spatial distribution of target colours in the result. For each matched pair, we first segment the regions into super-pixels, where the colour and spatial information are used together to measure the pixels' similarity during the segmentation process. Since the colour spatial distribution is represented in the segmentation results, we consider it as an additional constraint in the colour transfer process to preserve the colour spatial consistency. CIE L * a * b * colour model is used in all our experiments.

Segmentation

For each region (composed by the pixels with the same semantic label got in Section 4), we use Mean Shift [START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF] to segment it into super-pixels, which will keep the spatial consistency in the segmentation process. The following features are calculated for each super-pixel P i :

P ={p, c, µ, σ, S}, (2)
where p is the percentage of pixels in the image, c is the centroid of the super-pixel, µ and σ are the colour mean and standard deviation value of the pixel colours and S is a set containing all the pixel colours in a super-pixel. Since the corresponding semantic regions in source and target images may locate in different positions and appear in different geometrical shapes, we calculate their bounding boxes (denote P ul as the upper left position) and align the regions by setting P ul to be the origins of their local coordinate systems. We then set the centroid of each super-pixel as a relative position:

c = c e -P ul , (3)
where c e is the exact centroid of the super-pixel. We normalize c, µ and σ all to the range [0, 1].

Soft mapping construction

Based on the segmented super-pixels, we build a connection between the colour patterns of the matched source and target semantic regions. Unlike the one-to-one mapping scheme in [START_REF] Bao | Fast local color transfer via dominant colors mapping[END_REF], we instead build a soft many-to-many mapping between the two superpixel sets, which can generate more natural results in most cases. Denote f ij as the probability of the ith source super-pixel maps to the j th target super-pixel, and c ij as the mapping cost between them, the total cost of the mapping is optimized by the metric:

min {fij} Ns i=1 Nt j =1 f ij c ij , (4)
where N s denotes super-pixel number of the source image and N t denotes target one. The probability f ij is subject to the following constraints:

Nt j =1 f ij = p s i ,i = 1, 2,...,N s , Ns i=1 f ij = p t j ,j = 1, 2,...,N t ,
where p s i and p t j denote the percentage of pixels in the image corresponding to the super-pixel (labels s and t denote the source and target image, respectively). We set a same percentage p i = 1 N to all the super-pixels, which means that they have equal importance in the transfer process. In previous works [FK10, LE07, DBZP10], only colour difference is used to measure the mapping cost. In order to preserve the spatial distribution of the target colour styles, we modify the mapping cost function c ij by adding the spatial location information as a constraint, which is formulated as

c ij = exp µ s i -µ t j 2 δ c • exp c s i -c t j 2 δ s , (5)
where c = (x, y) is the super-pixel centroid (Equation 3), µ = (µ L ,µ a ,µ b ) is the colour mean value, and δ c and δ s are the parameters to control the contributions of colour and spatial features, respectively. We set δ c = 0.95 and δ s = 0.6 as default.

We adopt the EMD framework [START_REF] Rubner | The earth mover's distance as a metric for image retrieval[END_REF] to solve the linear program Equation (4). After that, we formulate the following transform functions to construct the mappings between the features of the source and target super-pixels:

(µ s i ) = Nt j =1 f ij µ t j Nt j =1 f ij , (σ s i ) = Nt j =1 f ij σ t j Nt j =1 f ij . (6)
Apparently, the transform functions softly map each source superpixel to multiple target super-pixels by a weighted average scheme. The weight f ij is solved from Equation (4).

We illustrate our soft mapping scheme between the source and target super-pixels of the corresponding regions in Figure 8. There are eight super-pixels in the source and seven in the target, while the number of colours in the source is less than the one of the target. We can see that after optimizing Equation (4), each source super-pixel is mapped to the target ones by a weighted average formulation. The spatial constraint in Equation (5) helps to preserve the spatial distribution of the target colour styles in the result. 5), so the spatial feature of the target colours is lost.

We use soft boundaries for the source image to avoid the artefacts caused by segmentation. When transforming the pixel colour I (x, y), we also consider the influence from its neighbouring superpixels. In the source image, denote P i as the super-pixel which pixel I (x, y) belongs to the set of neighbouring super-pixels of a pixel I (x, y)isdefinedas

N(x, y) ={P i }∪{P i ′ |∃I (x, y) ∈ S i ,I(x ′ ,y ′ ) ∈ S i ′ : |x -x ′ |+|y -y ′ |=1}. ( 7
)
For each neighbouring super-pixel P k ∈ N(x, y), we calculate the probability that the pixel colour I (x, y) belongs to it as:

p ′ k (x, y) = 1 Z D(I (x, y),P k ), (8)
where Z = P k ∈N(x,y) D(I (x, y),P k ) is the normalization factor. D(I (x, y),P k ) is the similarity between the pixel colour I (x, y) and its neighbouring super-pixel P k . We adopt the bilateral filter to simultaneously smooth the colour and spatial similarity:

D(I (x, y),P k ) = exp - I (x, y) -µ s k 2 δ ′ c • exp - (x, y) -c s k 2 δ ′ s .
We set δ ′ s = 0.4a n dδ ′ c = 0.95 in all our experiments. Users can properly increase the range of neighbourhood in Equation ( 7) if the input images are large.

Pixel colour transform

For an output pixel I o (x, y), we utilize the probability p ′ k (x, y)t o smooth the contributions of the neighbouring super-pixels N(x, y), which is computed as

I o (x, y) = k p ′ k (x, y) σ s k σ s k (I (x, y) -µ s k ) + µ s k , (9)
where p ′ k (x, y) is the probability that the pixel I (x, y) belongs to the neighbouring super-pixel P k (Equation 8), (µ s k )and (σ s k )are the new mapped mean and standard deviation of region P k ,respectively (Equation 6). Since the smoothing operation only involves the neighbouring super-pixels, our algorithm is very efficient. In some cases, the local gradient of the source image may be not In (h), we show the result without using soft mapping and soft boundaries, segmentation-like artefacts occur.

well preserved in the result and causes scene fidelity problem. To address this problem, we use our output as the intermediate image and apply the gradient-preserving method [START_REF] Ma | Gradient-preserving color transfer[END_REF] to generate the final result, so as to preserve the scene details of the source image.

Progressive transfer

To be more robust, we build an iterative framework. The target colour pattern is progressively transferred to the source image by modifying the minimum super-pixel size M k in each step. After the scene content analysis, we first transfer the colour styles between the source and target images at the largest scale by segmenting each content region into one super-pixel. The result is used as the source image in the next step. Then, we progressively reduce the minimum super-pixel size at each iteration by setting M k = 0.2 • M k-1 and update the pixel colour with the following formulations:

I o ′ k (x, y) = (1 -α k ) • I o ′ k-1 (x, y) + α k • I o k (x, y), (10)
α k = 1.0 - 1.0 1.0 + exp(0.5 • (k -1))
,

where I o k (x, y) is the result produced by Equation ( 9) with current super-pixel size and α k is a weight parameter to control the contribution of each scale. In the first iteration (k = 1), the source image is used as the initial value of I o ′ k-1 (x, y). We update the resultant image based on this multi-scale framework until the super-pixel is small enough. In our experiment, we stop this iteration when M k < 300. Users can properly increase the size of M k if the input images are large.

Our progressive approach performs both global and local colour transfer during the iteration, which can preserve the global colour styles as well as the local details in the result. Figures 9(c)-(e) show the intermediate results of our progress transfer process. We can see that the initial results in Figures 9(c) and (d) tend to access the target colour styles globally, while the final fine scale result in Figure 9(f) preserves the local details. Since this progressive framework enables the finer scale transfer to begin with a source image that has the similar global colour styles with the target, it can also avoid undesirable over-segmentation artefacts that often occur when colour transfer is performed only in a fine scale. For example, in Figure 9(g), over-segmentation artefacts occur in the left haystack and lower part of the sky, which is inconsistent with smooth appearance in the source image. Compared with the results in Figures 9(i) and (j), our method better preserves the colour patterns of the target image by presenting the sunset glow effect mainly in the middle part of the result. The sunset glow excessively appears in [START_REF] Ia | Local color transfer via probabilistic segmentation by expectation-maximization[END_REF] and is almost lost in [START_REF] Pouli | Progressive color transfer for images of arbitrary dynamic range[END_REF].

Extension to Videos

In this section, we extend our framework to videos. An intuitive way is applying the colour styles in the target image to the source video frame by frame. However, this direct operation will cause a perceptible flicker due to the motions in the frame sequences. Moreover, it is more reasonable to preserve the spatial distribution of the target colour styles in the whole video scene rather than in each of the single frame.

In order to keep the colour coherence of the video frame sequences during the transfer process, we first stitch the video frames and restore the scene structure of the video. The SIFT-based stitching algorithm [START_REF] Brown | Automatic panoramic image stitching using invariant features[END_REF] is used to create a panoramic image by combining the source video frames. Then, we use our colour transfer framework to apply the target colour styles to the panoramic image. Since there is a projective transformation between each of the video frame and the panoramic image, we can update the frame's colour depending on the transferred panorama as follows:

I o (x, y, t) = k p ′ k (x ′ ,y ′ ) σ s k σ s k (I (x, y)-µ s k )+ µ s k , (x ′ ,y ′ , 1) T = H t • (x, y, 1) T , (11)
where I (,t)isthetth image from the source video frame sequence, H t is the homography matrix representing the projective transformation between the tth image and the panorama, and (x ′ ,y ′ , 1) T is the corresponding homogeneous coordinates in the panoramic image. This function guarantees that the overlapping pixel between two successive frames will present in coherent colour styles since they are projected to the same panoramic super-pixel. The examples of video colour transfer are shown in the supplemental video, we can see that the colour spatial distribution of the target image is separately transferred to different frame sequences to make a coherent visual effect.

Results and Discussions

We implement our method on a machine with an Intel Core 7 Quad 2.66 GHz processor and 4 GB RAM. The amount of time of the subject area detection and background surface layout is typically about 20-30 s in total for the images (from 500 × 333 to 500 × 500) used in this work. The layout recovery results are generated by the code subscribed by the authors of [START_REF] Hoiem | Recovering surface layout from an image[END_REF]. We achieve real-time performance at our distribution-aware colour transfer process after the scene content analysis.

Figure 1 shows a typical example that benefits from our method. The colour features of the salient objects (the man and the dog), the sky and the ground of the target image are separately transferred to the corresponding regions of the source image. This scheme is very helpful in accurately presenting the desired visual appearance in the resultant image.

We compare our method with some commonly used colour transfer algorithms in Figures 2,6, 7(a), and 12-14. The results of [START_REF] Ia | Local color transfer via probabilistic segmentation by expectation-maximization[END_REF] are generated by the code subscribed by the authors of [START_REF] Xu | Performance evaluation of color correction approaches for automatic multi-view image and video stitching[END_REF] (http://ia.cs.colorado.edu/wxu/color_correction.htm). The results of [START_REF] Pitié | Automated colour grading using colour distribution transfer[END_REF], [START_REF] Efros | Using color compatibility for assessing image realism[END_REF] , [START_REF] Ma | Gradient-preserving color transfer[END_REF] and [START_REF] Pouli | Progressive color transfer for images of arbitrary dynamic range[END_REF] are generated from codes which are subscribed by the authors. Results show that our method can both re-produce the local details and global spatial distribution of the target colour pattern, while the other methods fail in most cases. The main reason is that the methods based on GMM [START_REF] Ia | Local color transfer via probabilistic segmentation by expectation-maximization[END_REF][START_REF] Efros | Using color compatibility for assessing image realism[END_REF] or histogram re-shaping [PKD07, PR11] usually tend to categorize the similar colours in the source image as a whole and transform them together during the transfer process, without considering their spatial information. Therefore, the similar colours of the source image will also appear to be a similar colour style in the result. However, when the number of colour styles in the source image is much less than the one of the target image, that scheme will cause the result to be assigned the average of the dominant colour styles of the target image, as shown in Figures 1(d In Figure 18, we use the results generated by using one source image and multiple target images to show the robustness of our method. We can see that our results well preserve the spatial distribution of the target colour styles in all results, while also avoiding the sky colour bleeding in [PKD07]'s results and colour distortion in [START_REF] Ma | Gradient-preserving color transfer[END_REF] and [PR11]'s results.

In Figure 19, we extract the clear regions from the close-up input images and separately transfer the colour styles between the source and target foreground objects, as well as the blur backgrounds. The top parts of the flowers in the result image appear green styles because they inherit the colour feature of the clear leaves in the target image, which is benefited from our distribution-aware colour transfer scheme.

To further evaluate our method, we perform a user study to compare the results from different methods. One hundred four users from different ages and backgrounds attended the comparison of 17 sets of the colour transfer images. All the stimuli are shown in the supporting information. In the experiment, we show the source image, the target image, our result and the images of the competitors. For each group, the results are randomly displayed in two rows within one page. In order to avoid the interference of the similar quality results to the statistic data, we ask the participants to choose maximum two images they like from each group. Table 1 shows the statistics. Each row shows the percentages of our method and the competitors been chosen by the participants. From the statistics, our method generally outperforms all competitors.

Conclusion and Future Work

We propose a novel colour transfer scheme that utilizes subject area detection and surface layout recovery to minimize user effort and generate accurate results. A new local colour transfer algorithm is presented, which integrates spatial distribution of target colour styles in the optimization process. An iterative framework is proposed to increase the robustness of the method, which can ensure the transferring of both the global and local colour styles, while also eliminating the over-segmentation artefacts. Our method can achieve a good and reasonable result even though the number of the source dominant colour styles is much less than the target one.

The spatial distribution of the target dominant colour styles are also nicely preserved in the output image. We also extend our algorithm to handle video-image colour transfer. The special colour distribution of the target image can be reproduced in an panoramic-like video.

There are limitations of our content-based colour transfer framework that we plan to investigate in future work. One is that the subject area detection methods may be inaccurate with fine-scale structure and unapparent boundary. For example, in Figures 10(a) and (c), we need to use Paint Selection to help to extract some small haystacks and ice creams. The surface layout recovery method is not accurate enough for some examples which contain complex scene structures. As shown in Figure 20, the road and the grass in the target image are both categorized as 'ground', so the colour styles of the road are also transferred to the grass of the source image. However, the image semantic segmentation is still an open problem and we believe that our system will be more robust by using some more precise image understanding algorithms. Our distribution-aware colour transfer scheme may break the wholeness of the clustered objects. As shown in Figure 21(b), sometimes, different colour styles appear in one single flower. Therefore, from the user study, we can see that many participants also choose Figure 21(d) as a favourite result. Some of the target colours may be lost in the result if the content of the source image is 'less' than the target, especially when the salient objects in the source image are less than the ones of the target (e.g. Figure 10e). Another is that colour transfer for background regions will not always exactly reproduce the spatial distribution of the target colour styles in the result, especially when the corresponding region of the source image contains an apparently different spatial colour distribution (an example is shown in the supporting information). However, in most cases, those results are actually more semantic reasonable than simply duplicating the colour distribution from the target image. Moreover, videos with large dynamic objects are generally less accurate than for static scenes, since the motion of dynamic objects will affect the accuracy of panoramic stitching. Additionally, we also plan to extend our algorithm to incorporate with internet photos which can subscribe more information to the input images.

  (a) Source Image (b) Target Image (c) Our Result (d) [TJT05] (e) [PKD07]

Figure 2 :

 2 Figure 2: Our result accurately presents the spatial distribution of the colourful tulips in the target image.

  [START_REF] Ashikhmin | Color transfer between images[END_REF]. The pixel colour values of the source image are transformed by matching the global colour mean and standard deviation of the target in an uncorrelated colour space lαβ. Chang et al.[START_REF] Aito S | Example-based color stylization of images[END_REF] proposed a perception-based scheme for transferring colours based on the basic colour categories, which are derived through a psychophysical experiments. This framework was extended to stylize the video frame sequences in[START_REF] Aito S | Example-based color transformation of image and video using basic color categories[END_REF]. Neumann and Neumann[START_REF] Neumann | Color style transfer techniques using hue, lightness and saturation histogram matching[END_REF] used 3D histogram matching to transfer the colour style of a source image into an arbitrary given target image having a different distribution. Tai et al.[START_REF] Ia | Local color transfer via probabilistic segmentation by expectation-maximization[END_REF] modelled the image colour distribution as Gaussian mixture models and solved the regional colour transfer problem by expectation maximization. Pitié et al.[START_REF] Pitié | Automated colour grading using colour distribution transfer[END_REF] proposed automated colour grading method by transferring an N -dimensional probability distribution function to another. Dong et al.[START_REF] Bao | Fast local color transfer via dominant colors mapping[END_REF] extracted the same number of dominant colours (DCD) from the two input images and find an optimal one-to-one mapping between the dominant colour sets. Pouli and Reinhard[START_REF] Pouli | Progressive color transfer for images of arbitrary dynamic range[END_REF] presented a histogram reshaping technique which allowed users to select how well the colour palette of the source image should be matched to that of the target. To further optimized the scene details in the result, Xiao and Ma[START_REF] Ma | Gradient-preserving color transfer[END_REF] employed Poisson compositing[START_REF] Pérez | Poisson image editing[END_REF] to preserve the gradients of the source image. However, as shown in Figure2, the commonly used colour transfer algorithms fail to generate a satisfied result if the number of source dominant colours is much less than the target one, especially when the colour styles are transferred between images having similar contents.

Figure 3 :

 3 Figure 3: System pipeline. We separately transfer the colour patterns between the corresponding semantic regions.

Figure 4 :

 4 Figure 4: Image scene content analysis. In (d), we use different colours to indicate different semantic regions, here green for support (ground) and red for vertical surfaces.

  Target (c) Our result (d)[START_REF] Pitié | Automated colour grading using colour distribution transfer[END_REF]

Figure 5 :

 5 Figure 5: The disjoint sky (the two sub-regions outlined by red boundaries) in (a) is treated as a whole semantic region in the matching and transfer process.

Figure 6 :Figure 7 :

 67 Figure 6: Our method better preserves the global brightness and local contrast of the original scene. The target colour patterns are also better depicted in the result (no blue colour bleeding on the buildings and street). The reason is that the colour styles in the target sky are only transferred to the source sky and do not affect the other regions (e.g. the roads in (d) and (e)).

Figure 8 :

 8 Figure 8: Illustration of soft mapping between super-pixels. (b) is generated by ignoring the spatial constraint in Equation (5), so the spatial feature of the target colours is lost.

  Result (k = 1) (d) Result (k = 2) (e) Result (k = 3) (f) Final Result (k = 4) (g) Without progressive (h) Without soft mapping (i) [TJT05](j)[START_REF] Pouli | Progressive color transfer for images of arbitrary dynamic range[END_REF]

Figure 9 :

 9 Figure 9: The iterative results of our progressive colour transfer process. The upper right images in (c)-(f) are the corresponding super-pixels. In (h), we show the result without using soft mapping and soft boundaries, segmentation-like artefacts occur.

Figure 10 :

 10 Figure 10: The colour spatial distribution of the ice cream in (c) is transferred to both the haystacks in (a) and the flowers in (b). We use Paint Selection to extract the haystacks in (a) and separate the ice creams in (c), as shown in (f).

  (a) Source Image (b) Target Image (c) Our Result (d) [LSZ12]

Figure 11 :

 11 Figure 11: Our method automatically generate more natural result without any user interaction. The sand in our result depicts the colour of the bottom part of the Sphinx in (b), without causing the colour distortion artefact in (d).

Figure 12 :

 12 Figure 12: The two buildings separately present the colour styles of the two trees in (b). The colour spatial information is lost in (d), while the red style is disappeared in (e). Our result also better preserves the brightness and contrast of the scene than (d).

Figure 13 :

 13 Figure 13: Our result better preserves both the target colour pattern structure and the source scene details.

  ), 1(e), 2(d), 2(e), 21(d), 15(d) and 15(e). The inte-gration of spatial constraint in our algorithm can solve the above problem. The similar colours are classified into different categories according to their geometric location, so they can depict different colour styles of the target image in the result. On the other hand, our progressive framework combines the advantages of both the global and local colour transfer schemes and avoids the over-segmentation artefact in the result which often occurs in most local transfer algorithms.

Figure 14 :Figure 15 :

 1415 Figure 14: The colour styles of the faces are separately transferred with the help of our face detection operator.

Figure 16 :

 16 Figure 16: When the input content structures are different, we first globally transfer the luminance and then perform local transfer operation between the skies. The sky in our result is more consistent with the target and the real natural phenomena.

Figure 17 :

 17 Figure 17: Our method better depicts both the sky (especially the spatial layer of the colours) and the grass (the yellow-green effect caused by the sunlight) colour patterns of (b) than other ones. Our result also avoids the segmentation-like artefact in (e).

Figure 10 shows

 10 Figure10shows two examples containing multiple salient objects, we can see that the spatial distribution of the target object colour styles are well represented in our results. In Figure11, we compare our method with the manually selective colour transfer

Figure 18 :

 18 Figure 18: Results produced by one source image and different target images. Our algorithm is robust in all examples.

Figure 19 :

 19 Figure 19: In our result, colour styles are separately transferred between clear and smooth regions.

Figure 20 :

 20 Figure 20: Our algorithm may generate an unnatural result if the scene content is not precisely extracted. (c) is generated by manually removing the road from the 'ground' region of the target and only transfer the colour styles of the grass to the corresponding 'ground' region (the grass) of the source image.

  (a) Input (b) Our result (c) [PKD07](d)[START_REF] Ma | Gradient-preserving color transfer[END_REF]

Figure 21 :

 21 Figure 21: The spatial feature of target flowers is preserved. However, different colour styles may appear in a single flower.

Table 1 :

 1 User study.

		Ours [PR11] [TJT05] [LE07] [PKD07] [XM09]
	Figure 1	65.3% 15.3%	5.77% 17.3%	23%	25%
	Figure 2	57.6% 1.92%	17.3% 11.5%	15.3%	13.4%
	Figure 6	61.5% 17.3%	5.77%	0%	11.5%	21.2%
	Figure 7	59.6% 1.92%	3.8%	23%	34.6%	5.77%
	Figure 9	50% 1.92%	9.6% 19.2%	28.5%	11.5%
	Figure 12	55.7%	0%	3.85%	25%	15.3%	21.1%
	Figure 13	75% 1.92%	1.92% 9.62%	17.3%	19.2%
	Figure 14	67.3%	0%	1.92% 32.6%	5.77%	23%
	Figure 15	50% 21.1%	5.77% 13.4%	15.3%	15.3%
	Figure 16	40.3% 11.5%	3.85% 28.8%	9.6%	26.9%
	Figure 17	80.7% 13.4%	0%	3.85%	17.3%	1.92%
	Figure 18-1 53.8%	3.8%	1.92% 40.3%	15.3%	1.92%
	Figure 18-2 61.5% 5.77%	13.4% 3.85%	25%	19.2%
	Figure 18-3 57.6% 3.85%	0%	23%	25%	9.6%
	Figure 19	71.6% 1.92%	0%	11.5%	15.3%	19.6%
	Figure 20	46.1% 3.85%	7.69%	25%	15.3%	36.5%
	Figure 21	48%	0%	11.5% 13.4%	48%	23%

Acknowledgements

We thank anonymous reviewers for their valuable input. We thank Tania Pouli for helping to make some results. We thank some flickr members (listed in the supporting information) who kindly allow us to use their images under Creative Commons License. This work is supported by National Natural Science Foundation of China under No. 61172104, 61271430, 61201402 and 61202324, by Beijing Natural Science Foundation (Content-Aware Image Synthesis and Its Applications, No. 4112061), and by SRF for ROCS, SEM.