B Ricaud

Member, IEEE B Torrésani

Refined support and entropic uncertainty inequalities

Keywords: Uncertainty principles, support inequalities, Shannon entropy, Renyi entropy, lp norms, frames, mutual coherence

Generalized versions of the entropic (Hirschman-Beckner) and support (Elad-Bruckstein) uncertainty principle are presented for frames representations. Moreover, a sharpened version of the support inequality has been obtained by introducing a generalization of the coherence.

In the finite dimensional case and under certain conditions, minimizers of this inequalities are given as constant functions on their support. In addition, ℓ p -norms inequalities are introduced as byproducts of the entropic inequalities.

I. INTRODUCTION

The uncertainty principle is originally a quantum physics principle stating that some families of observable quantities cannot be measured simultaneously with infinite precision. The uncertainty principle can be turned into quantitative statements thanks to uncertainty inequalities, which provide bounds on precision of simultaneous measurements of such quantities.

The prototype of uncertainty inequality is the celebrated Heisenberg inequality, first formulated in [START_REF] Heisenberg | Über den anschaulichen inhalt der quantentheoretischen kinematik und mechanik[END_REF], which uses a variance measure as criterion for the measurement precision. Namely, for all x ∈ L 2 (R),

∞ -∞ t 2 |x(t)| 2 dt . ∞ -∞ ν 2 | x(ν)| 2 dν ≥ 1 16π 2 ,
where the Fourier transform is normalized in such a way that the Fourier transform of e -πt 2 equals e -πν 2 . Originally stated for position and momentum, the Heisenberg inequality has been extended to more general observable pairs, under the name of Robertson inequality [START_REF] Robertson | The uncertainty principle[END_REF], [START_REF] Robertson | An indeterminacy relation for several observables and its classical interpretation[END_REF]. Particular cases have been analyzed by various authors, see e.g. [START_REF] Dahlke | The affine uncertainty principle in one and two dimensions[END_REF], [START_REF] Dahlke | The uncertainty principle associated with the continuous shearlet transform[END_REF], [START_REF] Flandrin | Inequalities in mellin-fourier analysis[END_REF], [START_REF] Maass | Do uncertainty minimizers attain minimal uncertainty[END_REF] and references therein. The Robertson variance inequality has been criticized in the physics literature, mainly because the bound in the inequality sometimes depends explicitely on the left hand side, which has motivated to seek alternative formulations. Besides, Robertson-type inequalities do not generalize well to all situations: for example, the notion of variance is not necessarily easy to define in some contexts, such as for periodic sequences or functions, functions defined on compact manifolds or graphs, more generally in situations where the notion of spreading away from a reference point is not straightforward. Among the generalizations, entropic inequalities, that use entropy measures to quantize measurement precision have enjoyed renewed interest recently. In the particular case of the position-momentum situation, the corresponding entropic uncertainty inequality, called the Hirschman-Beckner inequality [START_REF] Hirschman | A note on entropy[END_REF], is intimately related to the sharp form of the Hausdorff-Young inequality, the so-called Babenko-Beckner inequality [START_REF] Beckner | Inequalities in Fourier analysis on Rn[END_REF]. In signal processing terms, this uncertainty principle limits the simultaneous concentration or sparsity of a function and its Fourier transform. The inequality provides a lower bound on the differential entropies of their respective square moduli.

Uncertainty inequalities have received a renewed interest in the context of sparse approximation and signal processing applications. Often in a finite-dimensional setting, ℓ p norms (with p < 2) are used to measure dispersion of signals. This provides some quantities in order to compare the sharpness of different representations (ℓ 2 vectors) of a signal x or probe the concentration of information inside them. For example, the signal itself and its Fourier transform are two representations of the same mathematical object.

More generally, any projection of x on a basis of the Hilbert space gives a representation of the signal. In this context, uncertainty bounds involving ℓ 0 quasi-norm and ℓ 1 norm DRAFT October 30, 2012 have been derived. A prototype of such bounds is the Elad-Bruckstein ℓ 0 inequality:

given two orthonormal bases in a finite-dimensional Hilbert space and any vector x in that space with set of coefficients a and b with respect to the two bases,

a 0 b 0 ≥ 1 µ 2 ,
where µ is a constant called mutual coherence, that depends on the two bases (and not on x). Such results have important implications for practical problems, as shown in the pioneering work of Donoho and Stark [START_REF] Donoho | Uncertainty principles and signal recovery[END_REF]. For instance, ℓ 0 bounds have been used to prove the equivalence of ℓ 0 and ℓ 1 -based sparse recovery algorithms, under suitable sparsity assumptions [START_REF] Donoho | Uncertainty principles and ideal atomic decomposition[END_REF], [START_REF] Elad | A generalized uncertainty principle and sparse representation in pairs of bases[END_REF]. Results of similar nature have also been obtained in the context of the Fourier transform on abelian groups (see for example [START_REF] Tao | An uncertainty principle for cyclic groups of prime order[END_REF], [START_REF] Krahmer | Uncertainty in time-frequency representations on finite abelian groups and applications[END_REF], [START_REF] Murty | The uncertainty principle and a generalization of a theorem of Tao[END_REF]). As is well known in information theory, and remarked also in [START_REF] Przebinda | Three uncertainty principles for an abelian locally compact group[END_REF], Shannon entropy and ℓ p norms are closely connected, through Rényi entropies. Inequalities involving Rényi entropies [START_REF] Maassen | A discrete entropic uncertainty relation[END_REF], [START_REF] Dembo | Information theoretic inequalities[END_REF] actually imply both Shannon entropy inequalities and ℓ p inequalities.

This study has been divided into two parts (Sec. II and Sec. III). In the first part, we analyze such support (ℓ 0 ) inequalities in the context of frame decompositions, as follows.

Given two frames U and V in a Hilbert space H, denote by U and V the corresponding analysis operator. Ux and Vx are the two representations of x with respect to the frames.

For any x ∈ H, we prove for example a bound of the form

Ux 0 Vx 0 ≥ 1 µ 2 *
, where µ * is a constant that only depends on the two frames. In the case of orthonormal bases, these inequalities yield refined forms for support inequalities (µ * ≤ µ), for which we can analyze conditions for equality. The refined inequalities involve cumulated coherence measures, instead of the standard coherence measures used classically. In the case of frame decompositions, the inequalities we obtain concern analysis coefficients, while most recent contributions (in the domain of sparse decompositions and approximation) focus on inequalities involving synthesis coefficients. Therefore, exact recovery results such as those derived in [START_REF] Elad | A generalized uncertainty principle and sparse representation in pairs of bases[END_REF], [START_REF] Ghobber | On uncertainty principles in the finite-dimensional setting[END_REF] do not apply directly to the new results. Though, given the renewed interest on analysis-based sparse decompositions and co-sparsity (see e.g. [START_REF] Nam | The cosparse analysis model and algorithms[END_REF]), we believe that these new inequalities are of interest, October 30, 2012 DRAFT as they can yield bounds for the performances of cosparse signal recovery methods.

Consider for instance the following signal separation problem: given two frames U and V, and some observed signal u ∈ H, we want to split u as a sum of two components whose respective analysis coefficients with respect to frames U and V are sparse. In other words, we want to solve min

x,y∈H

[ Ux 0 + Vy 0 ] under constraint u = x + y .
where U and V are the analysis operators of two frames under consideration. Given two such decompositions u = x + y = x ′ + y ′ , the above support inequality directly leads to

Ux 0 + Vy 0 + Ux ′ 0 + Vy ′ 0 ≥ U(x -x ′ ) 0 + V(y ′ -y) 0 ≥ 2 µ * .
Therefore, if one is given a splitting of the form u = x + y such that Ux 0 + Vy 0 < 1/µ * , this splitting is automatically the solution of the above optimization problem.

Besides support size estimates, we also obtain entropic inequalities for analysis coefficients with respect to frames, that explicitely involve the frame bounds. This is developed in the second part of the study. As a particular case, Shannon entropy bounds are derived, and it is shown that the latter are only informative for tight frames. In the latter case, the entropy inequalities take a fairly simple form; for example, denoting by S(a) the Shannon entropy of a vector a, we show that given two tight frames U and V, with respective analysis operators U and V, then

S(Ux) + S(Vx) ≥ -2 ln(µ * ) .
Such inequality also turns out to yield the above mentioned support inequalities as a byproduct. Finally, we also derive new ℓ p inequalities as consequences of Rényi entropic inequalities.

II. REFINED ELAD-BRUCKSTEIN ℓ 0 INEQUALITIES

A. Notations

We first introduce the general setting we shall be working with. Throughout this paper, we shall denote by U = {u k , k ∈ Λ} and V = {v ℓ , ℓ ∈ Λ} two countable DRAFT October 30, 2012 frames for the Hilbert space H (we refer to [START_REF] Christensen | An introduction to frames and Riesz bases[END_REF] for a self contained account of frame theory). Here, the index set Λ will be finite when H is finite-dimensional, and infinite otherwise. x also written x 2 is the norm of x in H. We denote by A U , B U and A V , B V the corresponding frame bounds, i.e. we have for all x ∈ H

A U x 2 ≤ ∑ k | x, u k | 2 ≤ B U x 2 , ( 1
)
A V x 2 ≤ ∑ ℓ | x, v ℓ | 2 ≤ B V x 2 . ( 2
)
Let U : H → ℓ 2 (Λ) and V : H → ℓ 2 (Λ) be the corresponding analysis operators, i.e.

a k ∆ = (Ux) k = x, u k , b ℓ ∆ = (Vx) ℓ = x, v ℓ , x ∈ H , (3)
and denote by T = VU † : a → b the change of frame operator (with U † the Moore-Penrose pseudo-inverse of U). We shall also denote by U and V corresponding (generic) dual frames, among which the canonical dual frames will be denoted by

U • = (U * U) -1 U and V • = (V * V) -1 V.
As is well known (see [START_REF] Christensen | An introduction to frames and Riesz bases[END_REF]), the corresponding frame bounds are

respectively A U • = 1/B U , B U • = 1/A U ,
and similarly for V. We recall that in the particular case where U and/or V are (Riesz) bases, U and/or V are the corresponding bi-orthogonal bases.

In the following, we shall make use of the following quantity:

Definition 1: Let r ∈ [1, 2]
, let r ′ be conjugate to r, i.e. such that 1/r + 1/r ′ = 1. The mutual coherence of order r of two frames U and V is defined by

µ r (U , V ) ∆ = sup ℓ ∑ k | u k , v ℓ | r ′ r/r ′ , (4)
In the case r = 1, this corresponds to the standard mutual coherence, simply denoted by µ(U , V ).

This quantity is clearly well-defined in finite-dimensional settings. Notice also that in infinite-dimensional situations (i.e. when Λ is an infinite index set), this quantity is

well-defined for all r ∈ [1, 2]. Indeed, µ 2 (U , V ) ≤ B U sup ℓ v ℓ 2 , and µ r ′ /r r (U , V ) ≤ µ 2 (U , V ) sup k,ℓ | u k , v ℓ | r ′ -2 , which is finite since r ′ ≥ 2.
In finite-dimensional situations, the notion of mutually unbiased bases has been introduced in the physics literature by Schwinger [START_REF] Schwinger | Unitary operator bases[END_REF] (see [START_REF] Wehner | Entropic uncertainty relations -a survey[END_REF] for a review).

October 30, 2012 DRAFT Definition 2: Two orthonormal bases U and V in an N-dimensional Hilbert space H are mutually unbiased (MUB) if

| u k , v ℓ | = 1 √ N , ∀k, ℓ = 0, . . . N -1 .
U and V are blockwise mutually unbiased bases (BMUB) of H if U = {U (1) , . . . U (K) }, V = {V (1) , . . . V (K) }, where for all k = 1, . . . K, U (k) and V (k) span the same subspace

H (k)
, of dimension N k , and are MUBs for

H (k) , with k H (k) = H.
Notice that the coherence of a MUB in an N-dimensional Hilbert space equals µ(U , V ) =

1/ √ N, the corresponding r-coherence equals µ r (U , V ) = N r/2-1
, and the r-coherence

of a BMUB equals µ r (U , V ) = max k N r/2-1 k .

B. Refined Elad-Bruckstein inequality

The classical Elad-Bruckstein ℓ 0 inequality [START_REF] Elad | A generalized uncertainty principle and sparse representation in pairs of bases[END_REF] (a strong form of which has been given in [START_REF] Ghobber | On uncertainty principles in the finite-dimensional setting[END_REF]) gives a lower bound for the product of support sizes of two orthonormal basis representations of a single vector. The inequality can be extended to the frame case and generalized as follows.

Theorem 1: Let U and V be two frames of the Hilbert space H. For any x ∈ H, x = 0, denote by a = Ux and b = Vx the analysis coefficients of x with respect to these two frames.

1) For all r ∈ [1, 2], coefficients a and b satisfy the uncertainty inequality

a 0 . b 0 ≥ 1 µ r ( U , V )µ r ( V, U ) . (5) Therefore, a 0 . b 0 ≥ 1/µ * (U , U , V, V ) 2 ,
where

µ * (U , U , V, V ) ∆ = inf r∈[1,2] µ r ( U , V )µ r ( V, U ) . ( 6
)
2) For all r ∈ [1, 2], the inequality can only be sharp if the following three properties iii. for all k ∈ supp(a), ℓ ∈ supp(b), arg( ũk ,

v ℓ ) = arg(b ℓ ) -arg(a k ) = -arg( ṽℓ , u k ).
DRAFT October 30, 2012

Proof:

1) Let r ∈ [1, 2], let x ∈ H, x = 0. First remark that b ∞ = sup ℓ | x, v ℓ | = sup ℓ ∑ k a k ũk , v ℓ ≤ sup ℓ ∑ k |a k | | ũk , v ℓ | ,
and H ölder's inequality yields

b ∞ ≤ a r µ r ( U , V ) 1/r (7)
Similarly,

a ∞ ≤ b r µ r ( V, U ) 1/r . ( 8
)
Then, notice that

a r r ≤ a 0 a r ∞ ≤ a 0 b r r µ r ( V, U ) .
The same estimate on b r proves the first part of the theorem.

2) Assume first r = 1. As for the sharpness of the bound, notice first that the inequality a r r ≤ a 0 a r ∞ is sharp if and only if |a| is constant on its support (similarly, |b| has to be constant on its support). Now in the first inequality, H ölder's inequality is an equality if and only if the sequence k → | ũk , v ℓ | r ′ is proportional to |a| r , meaning that the sequence k → | ũk , v ℓ | is constant on its support, which coincides with the support of a. A similar reasoning is done for b and the sequence ℓ → | ṽℓ , u k |. The last inequality to be investigated is

|b ℓ | ≤ ∑ k |a k | | ũk , v ℓ |.
→ | ũk , v ℓ | is equal to a constant (namely, µ( U , V ))
on supp(a), and smaller outside the support. This does not change the conclusion. This concludes the proof. ♠

October 30, 2012 DRAFT Remark 1: 1) Clearly, by the arithmetic-geometric inequality, we also obtain the bound

a 0 + b 0 ≥ 2 µ * (U , U , V, V ) (9)
2) Using exactly the same techniques, the uncertainty inequality can be extended to K frames. Given K frames U (k) , k = 1, . . . K and denoting by a (k) the corresponding sequences of analysis coefficients of any x ∈ H, we readily obtain the bound

a (1) 0 . a (2) 0 . . . a (K) 0 ≥ K ∏ k=1 µ (k) * -1 (10)
where

µ (k) * = µ * (U (k) , U (k) , U (k+1modK) , U (k+1modK) ),
and again by the arithmetic-geometric inequality,

a (1) 0 + a (2) 0 + • • • + a (K) 0 ≥ K K ∏ k=1 µ (k) * -1/K . ( 11
)
Remark 2: We notice that when U and V are orthonormal bases the result generalizes the Elad-Bruckstein inequality. When U and V are non-orthonormal bases U and V are their respective biorthogonal bases and we obtain a straightforward generalization. In the case of frames, let us point out that the generalization we obtain concerns analysis coefficients rather than synthesis coefficients.

Remark 3: Notice finally that these bounds involve arbitrary dual frames U and V of U and V, not necessarily the canonical ones. Therefore the bound can be make more general, in the form

a 0 . b 0 ≥ 1/µ * * (U , V ) 2 , ( 12
)
where

µ * * (U , V ) ∆ = inf U , V inf r∈[1,2] µ r ( U , V )µ r ( V, U ) , (13)
the infimum running over the family of dual frames of U and V. A characterization of such families can be found in [START_REF] Christensen | An introduction to frames and Riesz bases[END_REF], Theorem 5.6.5.

DRAFT October 30, 2012

C. Examples and comments: the case of orthonormal bases

Consider first the case where U and V are two orthonormal bases in finite dimensional Hilbert spaces. First notice that the case r = 1 provides an elementary proof of the Elad-Bruckstein inequality (which involves 1/µ 1 (U , V ) 2 as a lower bound), together with explicit conditions for sharpness. In the particular case of mutually unbiased bases, i.e.

orthonormal bases such that

| u k , v ℓ | is constant, µ r (U , V ) = N r/2-1 is
r-coherence µ r (U , V ) = max k N r/2-1 k
, which means that again the optimal bound is provided by µ 1 .

In the case of orthonormal bases, the smallest possible value for the coherence is provided by the Welch bound: µ ≥ 1/ √ N. Therefore, we obtain Notice however that the case r ∈ [1, 2] constitutes a true generalization; indeed, for general pairs of orthonormal bases, it turns out that sup r [1/µ r (U , V )µ r (V, U )] >

1/µ 1 (U , V ) 2 . This is examplified in Figure 1, where are displayed the functions µ r (U , V ), µ r (V, U ) and µ r (U , V )µ r (V, U ) as a function of r, in a generic situation: the two bases U and V are random bases, obtained by diagonalization of random (Gaussian) symmetric matrices. As can be seen in this picture, the minimum of these three functions is not attained for r = 1 but for a larger value. For the sake of comparison, the case of mutually unbiased bases is also represented and exhibit a power law behavior as a function of r (represented as a straight line in the logarithmic plot). This shows that the coherence based bounds are not the best possible ones in general. Elementary infinitesimal calculus yields the following expression for the behavior of the r-coherence near r = 2:

µ r (U , V ) =1-(2-r) max ℓ -∑ k | u k , v ℓ | 2 ln | u k , v ℓ | 2 + O((2 -r) 2 ) ,
i.e. the slope of the tangent at r = 2 is given by the entropy-like expression

slope = -∑ k | u k , v ℓ | 2 ln | u k , v ℓ | 2
(see section below), which is known to be minimal (in finite dimensional situations, see [START_REF] Cover | Elements of Information Theory[END_REF] for more details) when the | u k , v ℓ | 2 are all equal.

More generally, we have the following result on r-coherences.

Proposition 1: Let {u k } k and {v l } l be two frames in the Hilbert space H of dimension

N.Fix l, let s l = max k | u k , v l | and denote by n l = ♯(| u k , v l | = s l
) the multiplicity of this maximal value. If max l n l s l < 1, then there exists r > 1 such that µ r < µ 1 .

Proof: It is enough to show that the derivative of µ r is negative at r = 1 under the stated conditions. Let us introduce the notation

S kl = | u k , v l | and L l (r) = ln ∑ k S r ′ kl r/r ′
, so that µ r = sup l L l (r). If for all l the derivative of L l is negative, so is the derivative of µ r . Since {u k } k and {v l } l are frames, ∑ k S kl > 0 for all l and L l is well-defined as well DRAFT October 30, 2012 . as its derivative near r = 1, r ≥ 1. This latter reads:

L ′ l (r) = ln n l s l + ∑ k∈Λ α r r-1 kl + ln s l r -1 ∑ k∈Λ α r r-1 kl + O   1 r -1 ∑ k∈Λ α r r-1 kl 2   , where α kl = | u k , v l |/n l s l and Λ is the set of k such that | u k , v l | = s l .
For r close to one, the dominant term is ln n l s l . In this case, if max l n l s l < 1, the derivative of µ r is negative.

♠ Remark 4: If two orthonormal bases have a high mutual coherence (µ 1 ), this implies that a single term is dominant and since in this case s l ≤ 1, Proposition 1 holds. However for frames with high coherence s l is large for some l, and it is highly probable that its October 30, 2012 DRAFT multiplicity be large as well. In this case, the conditions of the proposition are not satisfied and µ r may not be smaller than µ 1 . If there is too little coherence (like in MUB), n l may be large and again µ r may not be smaller than µ 1 . Finally, for MUB, n l s l = √ N, this is the slope of the curve plotted on Fig. 1.

III. ENTROPIC INEQUALITIES

The support inequalities described above can also be obtained as particular limits of entropic inequalities, which have been derived during the last 20 years in the mathematical physics and information theory communities.

A. Entropies

In information theory, the notion of entropy is often used to measure disorder, or information content of a random source; entropy measures are basically related to measures of dispersion of the probability density function of the random variables under consideration.

In the context of sparse analysis, the coefficients of the decomposition of any finitenorm vector with respect to a frame can be turned into a probability distribution, after suitable normalization. With the same notations as before, denote by a the sequence of analysis coefficients of x ∈ H (x = 0) with respect to the frame U , and we set ã = a/ a 2 . Given α ∈ [0, ∞] we introduce the corresponding Rényi entropy

R α (a) ∆ = 1 1 -α ln ã 2α 2α . (14)
Rényi entropies fulfill a number of simple properties, among which we will use the following two: monotonicity and limit to Shannon's entropy. More precisely, for a given coefficient sequence a,

α ≤ β =⇒ R α (a) ≥ R β (a) , (15)
and

lim α→1 R α (a) = -∑ n | ãn | 2 ln | ãn | 2 ∆ = S(a) . (16)
S(a) is the Shannon entropy of the coefficient sequence. Also, notice that R 0 (a) = ln a 0 .

This will lead to support inequalities as consequences of Rényi entropy inequalities.

DRAFT October 30, 2012

Uncertainty inequalities involving entropy measures have been derived in several different contexts (see [START_REF] Beckner | Inequalities in Fourier analysis on Rn[END_REF], [START_REF] Dembo | Information theoretic inequalities[END_REF], [START_REF] Maassen | Generalized entropic uncertainty relations[END_REF] for example). We derive below similar inequalities in a more general setting.

B. Entropic uncertainty inequalities for frame expansions

As above, let us consider two frames U and V. We use the same notations as in the previous section, and introduce the following additional constants: the geometric mean of the upper frame bounds ρ, the geometric mean of frame bounds ratios σ, and the normalized r-coherence ν r , written as

ρ(U , V ) ∆ = B V A U , σ(U , V ) ∆ = B U B V A U A V ≥ 1 , ν r (U , U , V ) = µ r ( U , V ) ρ(U , V ) r . ( 17
)
For the sake of simplicity, we shall drop the r index in the case r = 1, and set µ = µ 1 and ν = ν 1 . We then have the following theorem, which can be seen as a frame generalization of the Maassen-Uffink uncertainty inequality [START_REF] Maassen | Generalized entropic uncertainty relations[END_REF], [START_REF] Dembo | Information theoretic inequalities[END_REF]:

Theorem 2: Let H be a separable Hilbert space, let U and V be two frames of H, and let U and V denote corresponding dual frames. Let r ∈ [1, 2). For all α ∈ [r/2, 1], let

β = α(r -2)/(r -2α) ∈ [1, ∞].
For x ∈ H, denote by a and b the sequences of analysis coefficient of x with respect to U and V. Then the Rényi entropies satisfy the following bound:

(2 -r)R α (a) + rR β (b) ≥ -2 ln(ν r (U , Ũ , V )) - 2rβ β -1 ln(σ(U , V ))
Proof: the proof is both a refinement and a frame generalization of the proof in [START_REF] Maassen | Generalized entropic uncertainty relations[END_REF], [START_REF] Dembo | Information theoretic inequalities[END_REF]. Let T : a → b denote the linear operator of change of coordinate. From the frame bounds, we obviously have the inequalities

b 2 ≤ B V A U a 2 , a 2 ≤ B U A V b 2 ,
so that we have the estimate

T 2→2 ≤ B V A U = ρ(U , V ) . ( 18
)
October 30, 2012 DRAFT

A second bound is obtained as in [START_REF] Donoho | Uncertainty principles and ideal atomic decomposition[END_REF], and yields

T r→ ∞ = µ r ( Ũ , V ) 1/r . ( 19
)
Let p 0 = q 0 = 2, p 1 = r, q 1 = ∞, and set for θ ∈ [0, 1]

1 p = 1 -θ 2 + θ r , 1 q = 1 -θ 2 .
Clearly, 1θ = 2/q and θ = 1 -2/q = r(1/p -1/q), and the Riesz-Thorin lemma yields the following bound.

T p→q ≤ µ r ( U , V ) (1-2/q)/r ρ(U , V ) 2/q , ( 20
)
Using the definition of ã and b and the frame bounds, we deduce

b q ≤ ρ(U , V ) 2/q µ r ( U , V ) 1/p-1/q B U A V ã p ≤ σ(U , V )ν r (U , U , V ) 1/p-1/q ã p , (21)
where we have used the bound a 2 / b 2 ≤ ρ(V, U ) and the definition of ν r and σ in [START_REF] Maassen | Generalized entropic uncertainty relations[END_REF].

Set now p = 2α and q = 2β; taking logarithms, we get

1 -α 2α R α (a) - 1 -β 2β R β (b) ≥ - 1 2α - 1 2β ln(ν r (U , U , V )) -ln(σ(U , V )) , Since (β -1)/β = 1 -2/q = r(1/2α -1/2β), this implies β(1 -α) α(β -1) R α (a) + R β (b) ≥ - 2 r ln ν r (U , U , V ) -2 β -1 β ln(σ(U , V )) .
Finally, explicit calculations give α = βr/(r + 2(β -1)), so that

β(1 -α) α(β -1) = 2 -r r ∈ [0, 1] ,
which yields the desired result. ♠

Notice that since (2r)/r ∈ [0, 1], this implies the (generally non sharp) inequality

R α (a) + R β (b) ≥ - 2 r ln(ν r (U , U , V )) - 2β β -1 ln(σ(U , V )) DRAFT October 30, 2012
It is also worth noticing that in general, the limit α → 1 (which yields the sum of the Shannon entropies as left hand side) is non-informative, since the right hand side tends to -∞, unless σ = 1, i.e. U and V are tight. In that case the following simplified inequalities hold true:

Corollary 3: Assume U and V are tight frames, and let r ∈ [1, 2):

1) For all α ∈ [r/2, 1], with β = α(r -2)/(2α -r) ∈ [1, ∞] (2 -r)R α (a) + rR β (b) ≥ -2 ln(ν r (U , U , V )) . ( 22
)
2) the following inequalities between Shannon entropies hold true:

S(a) + S(b) ≥ -2 ln µ * (U , U , V, V ) , ( 23
)
where µ * is defined in [START_REF] Dembo | Information theoretic inequalities[END_REF].

Proof: the first item is a direct consequence of the previous theorem in the case of tight frames. For the second item, remark that from the monotonicity of the Rényi entropy, we

obtain (2 -r)S(a) + rS(b) ≥ (2 -r)R α (a) + rR β (b).
Remark also that for tight frames,

ν r (U , U , V )ν r (V, V, U ) = µ r ( U , V )µ r ( V, U ) σ(U , V ) r = µ r ( U , V )µ r ( V, U ) .
Symmetrizing the bound on Shannon entropies yield the desired result. ♠

Notice that owing to the monotonicity property of Rényi entropies, R 0 (a) = ln( a 0 ) ≥ S(a), and we recover the generalized Elad Bruckstein inequality

a 0 . b 0 ≥ 1 µ * (U , U , V, V ) 2 .
Similar results in the general case are discussed below.

C. Consequence: ℓ p inequalities for analysis frame coefficients

Let us start again from the modified entropic inequality in Theorem 2, and symmetrize it with respect to a and b. We obtain

(2 -r)(R α (a) + R α (b)) + r(R β (a) + R β (b)) ≥ -2 ln µ r ( U ,V )µ r ( V,U ) σ(U ,V ) r -4rβ β-1 ln(σ(U , V )) .
October 30, 2012 DRAFT Using the monotonicity of Rényi entropies, i.e. R α ≥ R β , we then get for all α ∈ [r/2, 1]

R α (a) + R α (b) ≥ -ln µ r ( U , V )µ r ( V, U ) -r β + 1 β -1 ln(σ(U , V )) , thus ln ã 2α . b 2α ≥ - 1 -α 2α ln µ r ( U , V )µ r ( V, U ) -r (β + 1)(1 -α) 2α(β -1) ln(σ(U , V )) ≥ 1 2 - 1 2α ln µ r ( U , V )µ r ( V, U ) -1- r 2 1+ r-2α αr-2α ln(σ(U , V )) finally yields the bound, for p ∈ [r, 2] a p . b p ≥ µ r ( U , V )µ r ( V, U ) 1 2 -1 p σ(U , V ) -(1-r 2 ) 1+ r-p p (1-r 2 ) a 2 . b 2 . ( 24
)
Also, using the fact that R 0 (a) = ln( a 0 ) ≥ R α (a) for all α ∈ [r/2, 1], and specifying to the sharpest bound α = r/2, we also obtain

ln ( a 0 . b 0 ) ≥ -ln µ r ( U , V )µ r ( V, U ) -r ln(σ(U , V )) , which yields a 0 . b 0 ≥ σ(U , V ) -r 1 µ r ( U , V )µ r ( V, U ) . ( 25
)
It is worth noticing that this bound is similar to the support inequalities obtained previously, except for the factor σ(U , V ) -r , which makes it weaker. Thus the bound is equivalent to the previous one if and only if the frames are tight. Notice also that sharper bounds are obtained, as before, by optimizing with respect to r and the dual frames U and V of U and V.

DRAFT October 30, 2012

D. Remark: necessary conditions for equality in the tight case

We now examine conditions for the entropic inequalities be saturated. Our aim is to make the connection with the constant on support property we already met in Theorem 1 and its proof. Since the entropic bounds we could prove are not sharp in generic situations, we limit the present discussion to the particular case of tight frames. Let U and V be two tight frames, denote by A U = B U and A V = B V the corresponding frame constants, and set

g kℓ = u ℓ , v k . ( 26
)
Straightforward calculations give and therefore the variational equations associated with the optimization of (2/r - Similar calculations on the Shannon entropy yield a comparable result.

∂ ∂a ℓ ln( a 2α 2α ) = α a ℓ |a ℓ | 2α a 2α
October 30, 2012 DRAFT

IV. CONCLUSIONS

We have examined in this paper entropic and ℓ p uncertainty principles in the framework of frame expansions. Our main results are extensions of support and entropic uncertainty principles to the case of frames, which turn out to generalize some known results when specializing to orthonormal bases. We showed in particular that in general situations, bounds involving the classical mutual coherence of the frames or bases under considerations are outperformed by the new bounds involving generalized coherences.

While ℓ p uncertainty principles have been mainly exploited in the framework of sparse expansion problems, i.e. synthesis based approaches, our results fit better into the so-called analysis frameworks (see e.g. [START_REF] Nam | The cosparse analysis model and algorithms[END_REF]), as shortly explained in the introduction. Practical consequences for co-sparse signal approximation and decomposition approaches are still to be investigated further. This is ongoing work by the authors of the present paper.

Let us mention that the finite dimensional case is by now fairly well understood, and the existence of optimizers for the uncertainty inequalities is closely connected to coefficient sequences that are constant on their support, as already remarked by [START_REF] Przebinda | Three uncertainty principles for an abelian locally compact group[END_REF].

In the infinite-dimensional case, such constant on support properties do not make much sense in general situations, and the optimization problem is still to be investigated much further.

  hold true: i. the sequences |a| and |b| are constant on their support, ii. for all k ∈ supp(a) (resp. ℓ ∈ supp(b)) the sequence ℓ → | ũk , v ℓ | (resp. k → | ṽℓ , u k |) is constant on supp(b) (resp. supp(a)).

  The latter becomes an equality if and only if the sum only involves positive numbers, i.e. iff arg( ũk , v ℓ ) = arg(b ℓ )arg(a k ). A similar reasoning yields the condition arg( ṽℓ , u k ) = arg(a k )arg(b ℓ ).

Finally

  , consider the case r = 1. The above argument can be reproduced exactly, except for the tightness argument for H ölder's inequality. The latter can now be an equality only if the sequence k

  monotone and minimal for r = 1, which yields the usual coherence µ = µ 1 = 1/ √ N, N being the dimension of the considered Hilbert space. An example of mutually unbiased bases is provided by the Kronecker and Fourier bases in R N , in which case the Elad-Bruckstein inequality coincides with the inequality derived before by Donoho and Huo [7]. For blockwise mutually unbiased bases, we also obtain a monotone function of r for the

Corollary 1 : 1 0. 1 0. 2 0. b 1

 11121 Assume U and V are orthonormal bases. The optimal bound for the refined Elad-Bruckstein uncertainty inequality is attained in the case of mutually unbiased bases, for r = 1. Consider now the case where the inequality is an equality, in the case r = 1. By Theorem 1, the analysis coefficients a and b of the corresponding optimizer are such that |a| and |b| are constant on their support. The proof of part 2. of the theorem also implies that for k ∈ supp(a), the sequence ℓ → | u k , v ℓ | vanishes outside supp(b) and equals a constant on supp(b); The latter constant equals necessarily b -1/2 0 , andµ r (U , V ) = b r/2-Similarly, µ r (V, U ) = a r/2-Assume finally that the inequality be an equality, the latter thus reads a 0 . b 0 = a 1-r/for nonzero signals x) a 0 . b 0 = 1, i.e. the two bases have at least one common element, and the signal is a multiple of one of these common elements.Corollary 2: Assume U and V are orthonormal bases. For r = 1, the corresponding refined Elad-Bruckstein inequality cannot be an equality, unless the two bases have a October 30, 2012 DRAFT common element.

Fig. 1 .

 1 Fig. 1. Logarithm of r-coherence functions as a function of r. µ r (U , V ) (dashed), µ r (V, U ) (dash-dotted) and µ r (U , V )µ r (V, U ) (full); straight line: mutually unbiased bases. Top: random bases U and V. Bottom: MDCT bases with different window sizes.

1 ) 1 |a ℓ | 2 Remark 5 :

 1125 R α (a) + R β (b) under constraint x = 1 = a / λ is a Lagrange multiplier. Now remark that β/(1β) = -α(2r)/r(1α);multiplying both sides with a k and summing over k, the constraint x = a / √ A U = 1 gives λ = 0, so that the variational equations take the form, for α = From the above expression, we can observe that |a| is constant on its support if and only if |b| is, since ∑ k g kℓ b k = a l . In this situation, we have|a k | = A U / a 0 for all k ∈ supp(a) and |b k | = A V / b 0 for all k ∈ supp(b), so that R α (a) + R β (b) = ln ( a 0 . b 0 ) ,which therefore saturates the inequalities.

ACKNOWLEDGEMENTS

This work was supported by the UNLocX project of the Future Emerging Technologies programme of the European Union (FET-Open grant number: 255931). B. Torrésani also acknowledges partial support from the Metason project of the french Agence Nationale de la Recherche CONTINT programme (ANR ANR-10-CORD-010).


Mehmet Türkan

Christine Guillemot

LOCALLY LINEAR EMBEDDING BASED TEXTURE SYNTHESIS FOR IMAGE PREDICTION AND ERROR CONCEALMENT

Keywords: Template matching, average template matching, non-local means, locally linear embedding, image prediction, error concealment

The template matching algorithm is a simple extension to exemplarbased texture synthesis. Average of template matching predictors or non-local means based approaches can be seen as heuristic extensions to template matching. These methods which linearly combine several texture patches have been shown to be more robust in synthesis and to give better results when compared to simple template matching. However, they do not search to minimize an approximation error on the known pixel values in the template. They are rather heuristic methods for calculating the linear weighting coefficients. This paper proposes a neighbor embedding based texture synthesis method by formulating the problem as a least-squares optimization using locally linear embedding. By this means, one calculates the linear weighting coefficients by solving a constrained optimization for approximating the template. The proposed texture synthesis framework has first been applied to the image prediction (predictive coding) problem. It has then been extended to a loss concealment application for transmission errors. Experimental results demonstrate the effectiveness of the proposed method for both image compression and error concealment.

INTRODUCTION

Texture synthesis is a key component of various image and video processing applications such as inpainting, restoration, (predictive) coding, and so on. Existing texture synthesis methods can be classified into two main categories. The first category relies on either the use of partial differential equations [START_REF] Bertalmio | Navier-stokes, fluid dynamics, and image and video inpainting[END_REF] or variational approaches [START_REF] Chan | Local inpainting models and TV inpainting[END_REF]. The ideas presented in this type basically try to propagate via diffusion both geometric and photometric information that hits the border of the region to be synthesized. These methods are known to work relatively well for synthesizing small regions in an image. However, they tend to introduce blur for large regions, and the results are highly dependent on the input parameters. The second category of texture synthesis concerns exemplar-based methods [START_REF] Efros | Texture synthesis by non-parametric sampling[END_REF][START_REF] Wei | Fast texture synthesis using tree-structured vector quantization[END_REF][START_REF] Ashikhmin | Synthesizing natural textures[END_REF] which sample texture patches (or pixels) from an other image (or from the image itself) in order to synthesize new textures. Exemplar-based methods are known to work well in cases of regular textures, and they have widely been used in a large variety of applications because of their simplicity and efficiency. Moreover, these methods can compute a priority for the different patches to be synthesized so that the algorithm can start by first propagating important structures in the image. For example, the authors in [START_REF] Criminisi | Region filling and object removal by examplar-based image inpainting[END_REF] introduce an exemplarbased method in which a filling order is defined by a priority function which depends on the angle between the isophote direction and the normal direction of the local filling front. The goal of this priority function is to ensure that the linear structures are propagated before texture filling.

Exemplar-based methods usually copy a single patch (or a pixel) from an input texture sample (exemplar) to the output texture according to the known local neighboring set of pixels of the current patch (or pixel) to be synthesized. The well-known template matching (TM) algorithm operates as an extension to exemplar-based texture synthesis, and has been shown to be an effective method for several applications including intra and inter prediction [START_REF] Tan | Intra prediction by template matching[END_REF][START_REF] Sugimoto | Inter frame coding with template matching spatio-temporal prediction[END_REF], and inpainting [START_REF] Criminisi | Region filling and object removal by examplar-based image inpainting[END_REF][START_REF] Bertalmio | Simultaneous structure and texture image inpainting[END_REF]. A so-called template is formed by the known pixels in a close neighborhood of the unknown patch to be synthesized. The best match between the template and the candidate texture patch neighborhood (of the same shape as template), either within a search window or in the whole image, allows finding the predictor of the unknown pixel values.

One can even combine several image patches instead of using a single "best" patch. The simplest way of combining several patches is to assign uniform weights for each patch. This method is the same with the average of multiple template matching (ATM) predictors as proposed in [START_REF] Tan | Intra prediction by averaged template matching predictors[END_REF]. Recently, non-local means (NLM) based approaches [START_REF] Wong | A nonlocal-means approach to exemplarbased inpainting[END_REF][START_REF] Mairal | Non-local sparse models for image restoration[END_REF] have also been proposed for different texture synthesis problems. These methods which combine several patches have been shown to be more robust in estimating the unknown values and producing better synthesis results. However, the approaches ATM and NLM do not search to minimize an approximation error on the template signal. They are rather heuristic methods to calculate the linear weighting coefficients.

In this paper, we propose a texture synthesis method based on the locally linear embedding (LLE) technique [START_REF] Roweis | Nonlinear dimensionality reduction by locally linear embedding[END_REF]. The underlying motivation can be thought of as finding a best linear combination of a number of "texture primitives" (texture patches) to approximate the input patch using a neighbor embedding optimization rather than a heuristic calculation of weighting coefficients. In LLE, the goal is to reconstruct each input signal from its K nearest neighbors (K-NN).

We focus particularly on texture synthesis for two different image processing problems: (i) predictive coding (image prediction) and (ii) error concealment. Although there is a strong similarity between the prediction problem and the error concealment problem, there are at the same time important differences. In concealment, the known samples are not restricted to be in a causal neighborhood and the texture patches can be treated in a different order than the raster scan. However, in prediction, the processing order is the raster scan, the known samples are located only in a causal neighborhood of the block to be predicted. The priority order as used in error concealment can not be used as such (or not with as much freedom) for the prediction problem. On the other hand, in an error concealment application, errors in texture synthesis are very critical and can propagate very easily. The rest of the paper is organized as follows. In Sec. 2 we start with the image prediction problem by revisiting the background approaches including TM, ATM, and NLM. We then introduce the LLE based texture synthesis framework for image prediction. In Sec. 3 we extend the proposed texture synthesis method for an error concealment application. We give then experimental results obtained for image prediction 1 and error concealment in Sec. 4. Finally, Sec. 5 concludes this work with a brief conclusion.

LOCALLY LINEAR EMBEDDING FOR PREDICTION

Background approaches: TM, ATM, NLM

The main idea of TM consists in estimating the unknown pixel values using image patches in a local search window where all the pixel values are known and available for processing. More precisely, the values of each pixel to be predicted are determined by comparing their spatial neighboring pixels (template) with all candidate neighborhoods in the search window, and assigning the candidate pixel values as a predictor for the unknown sample values by minimizing a distance between the template and the candidate neighborhood. The distance measures used are usually classical ones such as the sum of squared error (SSE). Fig. 1 demonstrates a simple illustration of the TM algorithm for block-based intra image prediction.

Let S denote a region in the image containing the unknown block of size n × n and its template as shown in Fig. 1. The region S contains 4 blocks hence of size N = 2n × 2n pixels for running the TM algorithm. Suppose that the columns am of a matrix A ∈ R N×M are constructed by stacking the luminance values of all possible patches, of size 2n × 2n pixels, in a given causal search window W in the reconstructed image region. Here the matrix A will be referred to as the dictionary. Assume also that the N sample values of the region S are stacked in a column vector b.

For the first step, that is the search for a best match of the known pixel values in the template, the matrix A is modified by masking its rows corresponding to the spatial location of the pixels of the unknown block. A compacted dictionary Ac of size 3n 2 × M is obtained in which actually the columns ac m correspond to the possible 1 This study analyses particularly the performance of ATM, NLM, and LLE for image prediction. A more general performance comparison between TM-based prediction and standard prediction (e.g., H.264/AVC intra) with advantages and disadvantages is available in [START_REF] Turkan | Image prediction based on neighborembedding methods[END_REF].

where the operator DIST denotes a distance metric such as SSE. The prediction signal bt is simply assigned by the sample values of the candidate block as bt = at m opt . The columns at m of At correspond to the possible candidate blocks in the search window, where the matrix At is obtained by masking the rows of the dictionary A corresponding to the spatial location of the pixels of the template. Starting with the above definition of simple TM, a weighted linear combination of multiple TM predictors can be a possible extension since there might be more than one candidate block which are equally important, or with a varying degree of importance but useful to be used in the prediction process. Let the vector bt be predicted as a weighted average of the candidate blocks at m k , k = 1...K, where the corresponding candidate neighborhoods ac m k taken from the search window are the K-NN of the template bc. A simple consideration ATM is of the weighting coefficients which are all equal to each other. The prediction follows by

bt = A K t α (2)
where A K t is the matrix containing at m k in its columns and the elements α k of the weighting vector α are all equal to 1/K.

Similar to ATM, the NLM based method tries to aggregate multiple image patches as a weighted linear combination but the weighting coefficients are calculated in a different way. The idea here is to express the weights in terms of the amount of similarity between the candidate neighbor patches and the template, i.e., the contribution weights are calculated with a patch similarity based kernel function in order to give more weight to the neighboring patches which are more similar to the template than the others. By using an exponential kernel, the elements α k of the weighting coefficients vector α can be calculated as α k = exp -DIST bc,ac m k h where h is a decay coefficient. The calculated weights are normalized to sum-to-one, i.e., α = α/sum(α), in order to avoid a possible overflow in the predicted values of the pixels. Finally, the prediction follows Eqn. 2.

Prediction based on LLE

In this study, we propose to use LLE for calculating the weighting coefficients in the vector α. We thus search for an approximation of the template by a linear combination of its K-NN, and then keep the same weighting coefficients in the linear combination of the colocated pixels in order to estimate the unknown values of the block to be predicted. In terms of LLE, this optimization can be written as

arg min α ||bc -A K c α|| 2 2 subject to 1 T α = 1 (3)
and the optimal weighting coefficients in α are computed as

α = G -1 1 1 T G -1 1 . ( 4
)
Here A K c is the matrix containing ac m k , k = 1...K, in its columns, G denotes the Gram matrix of A K c in reference to bc, and 1 is the column vector of ones. In practice, instead of an explicit inversion of the matrix G, the linear system of equations Gα = 1 is solved, then the weights are rescaled so that they sum to one. Note that the sum-to-one constraint of weights forces the reconstruction of each patch to lie in the subspace spanned by its neighbors. Since the input texture patch samples are all non-negative, the predicted block will also be non-negative. However, the calculated weights can be positive or negative. Finally, the prediction follows Eqn. 2.

EXTENSION TO ERROR CONCEALMENT

Error concealment is very similar to the image inpainting problem where one can compute a priority for different patches so the algorithm proceeds according to a given priority function. In this work, we use the priority function which is defined in [START_REF] Criminisi | Region filling and object removal by examplar-based image inpainting[END_REF]. At each step of the algorithm, the border (fill front) of the missing region is identified, and the priority P (p) of each pixel p located on the fill front is calculated. An n × n patch φ p centered on the highest priority pixel p located on the fill front is selected for synthesis. In the patch φ p, there are known values and unknown values to be synthesized. A template is assumed to be formed with the known pixel values in the input patch φ p (see Fig. 2). The rest is very similar to image prediction case where we search for an optimized approximation of the template by a linear combination of its K-NN taken from the known image region, and then keep the same weighting coefficients in the linear combination of the co-located pixels in order to estimate the unknown values. After estimating the unknown sample values in φ p, we update the fill front and the algorithm repeats the next steps until all unknown samples in missing region are synthesized.

EXPERIMENTAL RESULTS

For the experimental validation, we have first placed the proposed prediction method into an image compression scheme. In order to initialize the prediction/compression process, the top 4 rows and left 4 columns of blocks of size 4 × 4 are predicted with H.264/AVC intra modes. Once a block has been predicted with the respective prediction method (ATM, NLM, or LLE), the 4 × 4 residual block is DCT transformed, quantized, and encoded similar to JPEG. In this coding structure, a uniform quantization matrix with Δ = 16 is weighted by a quality parameter ranging between 10 and 90. Image blocks are processed in the raster scan order, and the reconstructed image is obtained by adding the quantized residue to the prediction. A skip mode has also been included into the encoder to avoid coding the blocks of prediction residue in which all the transformed and quantized coefficients are zero. The corresponding flag is arithmetically encoded. Nine possible forms of approximation supports (templates) are considered as shown in Fig. 3. The optimum template type, which is Huffman encoded, is selected by minimizing a rate- Two sets of tests have been carried out. The first one makes use of approximations with a smaller number of patches considered in the K-NN search, where K is varied from 1 to 8. RD optimized K value is signaled to the decoder in addition to the template type. Fig. 5 demonstrates the encoding PSNR/bit-rate performance for Foreman (CIF), Barbara (512 × 512), and Roof (512 × 512) images. The coding cost of the optimum value of K as well as the optimal template type have been included into total bit-rate. One can observe that ATM outperforms the other methods, however LLE has a closer performance than NLM. The second set of experiments relaxes the K value, and takes as K = 100. In this case, there is no need to signal the value of K since it is fixed and assumed to be known also at the decoder. Fig. 6 shows the encoding performance results obtained for the same test images. The first observation one can make is that the method based on LLE outperforms the other methods. The significant performance gain can clearly be seen when the image contains more complex and non-periodic texture areas (like in Barbara and Roof). This gain has been achieved because of the bit-rate savings of signaling cost of K (note that this is the same for all methods considered), and of the better optimization solutions of LLE on calculating the weighting coefficients. The second observation is the increase in the performance of NLM in reference to ATM. Apparently, with the increasing number of used image patches, NLM becomes an effective alternative to ATM since the weighting coefficients have been calculated in a wise manner which prevents over-smoothing effects of simply averaging K = 100 patches.

We have then placed the proposed texture synthesis method for assessing the performance in a simple loss concealment application. Fig. 4 shows the images (referred to as barb1, barb2, and lena) which have been tested with ATM, NLM, and LLE. Table 1 demonstrates the obtained PSNR results of texture synthesis methods with different K values where K = {1, 10, 25, 50, 100}. Notice that for the special case when K = 1, all of the methods reduce to a simple TM. In terms of PSNR, the effectiveness of LLE method can clearly be observed especially for synthesizing highly textural regions. A linear combination of several texture patches always produce better performance when compared to using only one single "best" patch as in TM. Please note that here the tested missing regions are larger than a macroblock size conventionally used for image or video coding, hence one can expect even better results for macroblock size missing regions.

CONCLUSION

In this paper, we proposed a new texture synthesis method based on LLE. This method can be seen as a generalization of TM, in the sense that it searches to approximate the template signal via a constrained optimization in contrary to heuristic methods such as ATM and NLM. Experimental validation shows that the proposed method offers better performance when compared to TM, ATM, and NLM.

  candidate neighborhoods in the search window. The vector b is also compacted in bc with the known pixels in the template of size 3n 2 values. The TM algorithm then proceeds by calculating mopt = arg min m∈[1...M] {dm : dm = DIST (bc, ac m )}

Fig. 2 .

 2 Fig. 2. Error concealment. The patch φ p is centered on the highest priority pixel p located on the fill front. The template information of φ p (blue) is used for selecting the patches from the known image region and then filling-in the unknown values of φ p (red).

Fig. 3 .

 3 Fig. 3. Nine possible forms of approximation support (template). The best type is selected by minimizing the RD cost function.

Fig. 4 .

 4 Fig. 4. Test images for error concealment: (left) barb1 (21.25 dB), (middle) barb2 (18.62 dB), (right) lena (21.85 dB).

Fig. 5 .

 5 Fig. 5. Encoding performance for (left) Foreman, (middle) Barbara, and (right) Roof using LLE in comparison to ATM and NLM (Optimized K ∈ [1, 8]).

Fig. 6 .

 6 Fig. 6. Encoding performance for (left) Foreman, (middle) Barbara, and (right) Roof using LLE in comparison to ATM and NLM (Fixed K = 100).

  Block-based intra prediction based on template matching. A template is formed by previously encoded pixels in the close neighborhood of the unknown block. The best match between the template and the candidate neighborhood, within the search window W, allows finding the predictor (candidate block) of the unknown block.

	Fig. 1.
	978-1-4673-2533-2/12/$26.00 ©2012 IEEE	3009	ICIP 2012

Table 1 .

 1 .41 32.41 31.98 31.07 31.09 31.09 31.00 34.77 34.46 36.34 36.36 barb2 33.70 37.24 37.41 37.68 36.73 36.35 36.41 36.70 36.71 38.05 36.21 35.19 37.78 lena 31.16 35.60 35.78 35.28 34.20 35.31 35.14 35.32 35.52 35.32 34.11 34.86 34.89 PSNR (in dB) results for test images after concealment.

		TM		ATM				NLM				LLE
	Image K = 1	10	25	50	100	10	25	50	100	10	25	50	100
	barb1	32.89	34.59 34


Marco Bevilacqua

Aline Roumy

Christine Guillemot

Marie - Line

Alberi Morel

Marie-Line Alberi

Neighbor embedding based single-image super-resolution using Semi-Nonnegative Matrix Factorization

Keywords: Super-resolution, neighbor embedding, Semi-nonnegative Matrix Factorization

published or not. The documents may come   L'archive ouverte pluridisciplinaire

INTRODUCTION

Super-resolution (SR) refers to the task of producing a highresolution (HR) image from one or more low-resolution (LR) images. In this work we focus on the single-image problem, whose aim is to synthesize an "enhanced" enlargement of a target image with possibly better results than traditional interpolation techniques.

Single-image Super-Resolution is often referred to as Example-based Super-Resolution [START_REF] Freeman | Example-Based Super-Resolution[END_REF][START_REF] Kwang | Example-Based Learning for Single-Image Super-Resolution[END_REF], as the prior information required in order to estimate the missing HR details is given in the form of examples, i.e. learned pairs of LR and HR patches (sub-windows of image) that compose a dictionary. The learned pairs of patches are usually taken from external HR images and degraded (blurred and conveniently downsized) versions of them. As a first step of any example-based SR algorithm, the target image is divided into patches of the same size of the LR patches in the dictionary; then, each LR input patch is compared to the stored LR patches and, once the nearest patch among these is found, the corresponding HR patch is finally taken as the output. A variation to this procedure is presented in [START_REF] Chang | Super-Resolution Through Neighbor Embedding[END_REF] and in some other SR methods based on sparse representations (e.g. [START_REF] Yang | Image Super-Resolution as Sparse Representation of Raw Image Patches[END_REF][START_REF] Wang | Resolution enhancement based on learning the sparse association of image patches[END_REF]): instead of selecting from the dictionary only one patch, several patches are taken into account and contribute simultaneously to the generation of a single HR output patch. In particular, in [START_REF] Chang | Super-Resolution Through Neighbor Embedding[END_REF] the authors propose a single-image SR algorithm, based on the concept of neighbor embedding and originally inspired by a method for data dimensionality reduction called Locally Linear Embedding (LLE) [START_REF] Roweis | Nonlinear Dimensionality Reduction by Locally Linear Embedding[END_REF]. The basic assumption is that a patch in the LR target image and the corresponding HR unknown patch share similar neighborhood structures: as a consequence of that, once the LR patch is expressed as the linear combination of a certain number of its neighbors taken from the dictionary, the output patch can be reconstructed by using the HR patches in the dictionary corresponding to the neighbors selected, and combining them in the same way. This algorithm is shown to be suitable for the SR problem, but its performance is sensitive to the number of neighbors chosen, that appears as a parameter difficult to properly set.

We propose a new neighbor embedding method based on Semi-nonnegative Matrix Factorization (SNMF) [START_REF] Ding | Convex and Semi-Nonnegative Matrix Factorizations[END_REF]. In LLE the weights are constrained to sum up to one, but no constraint is specified for their sign. This might explain the unstable results observed in [START_REF] Chang | Super-Resolution Through Neighbor Embedding[END_REF], since possible negative weights can lead to having subtractive combinations of patches, which is counterintuitive. Instead, we suggest to compute the weights with a non-negative constraint, to be compatible with the intuitive notion of "combining parts to form a whole" (from [START_REF] Lee | Learning the parts of objects by non-negative matrix factorization[END_REF]). In neighbor embedding based SR, both the LR and the HR patches are represented by feature vectors, given by the concatenation of some, possibly different, features of their pixels, and all the SR steps are performed by using these vectors. We thus discuss the issue of the choice of the features, and propose to use the centered luminance values of the pixels to represent the LR patches, instead of the gradient as in [START_REF] Chang | Super-Resolution Through Neighbor Embedding[END_REF].

The paper is organized as follows. Section 2 presents neighbor embedding as a possible approach for super-resolution. Then, Section 3 describes our algorithm, particularly the new method for computing the neighbor combination and the choice of the features. In sections 4 and 5, experimental results are finally reported and commented.

SUPER-RESOLUTION VIA NEIGHBOR EMBEDDING

The Neighbor Embedding (NE) algorithm of Chang et al. [START_REF] Chang | Super-Resolution Through Neighbor Embedding[END_REF] is the starting point for this work. As said, its peculiarity is that several patches are taken from the dictionary to represent a single input patch; it follows that multiple patches, i.e. their HR counterparts in the dictionary, are combined together to generate an output HR patch. In the algorithm, each patch is represented by a feature vector: we extract from any single pixel of the patch one or more features; the patch vector is then obtained by the simple concatenation of the features of its pixels. The neighbor search, the weight computation and the HR patch reconstruction steps are all performed with respect to the feature spaces chosen: once the HR feature vectors are reconstructed, we finally "reverse" the features, so obtaining the actual HR output patches. In [START_REF] Chang | Super-Resolution Through Neighbor Embedding[END_REF], for instance, a 4-value gradient and the centered luminance pixel values are used as features, respectively for the LR and HR patches. In Table 1 the notations used in the paper for the corresponding feature vectors are reported.

X d = {x j d } N d j=1 LR patches in the dictionary X t = {x i t } Nt i=1 patches in the LR target image Y d = {y j d } N d j=1 HR patches in the dictionary Y t = {y i t } Nt i=1
patches in the HR target image (Note: all patches are intended as patch feature vectors.) The NE-based SR approach proceeds as follows.

1. For each LR patch feature vector x i t ∈ X t (a) Find its K nearest neighbors (NN) in X d in terms of Euclidean distance:

N i = arg min x j d ∈X d K x i t -x j d 2 .
(b) Compute according to some criteria the weights of the linear combination that approximates x i t with the selected neighbors, i.e. the K weights {w ij } K j=1 such that:

x i t ≈ x j d ∈Ni w ij x j d .
In [START_REF] Chang | Super-Resolution Through Neighbor Embedding[END_REF], for instance, the original Neighbor Embedding algorithm takes from LLE the method used to "embed" the neighbors. For each input patch, the weights related to its neighbors are found by solving the following minimization problem:

w i = arg min w x i t -X i d w 2 s.t. 1 T w = 1 , (1)
where w i is the K × 1 weight vector related to the input patch x i t , and X i d is a matrix with all its neighbors disposed as columns. (1) can be seen as a Constrained Least Squares (LS) problem, whose solution is provided in [START_REF] Chang | Super-Resolution Through Neighbor Embedding[END_REF][START_REF] Roweis | Nonlinear Dimensionality Reduction by Locally Linear Embedding[END_REF]. Therefore, in this paper we refer to the weights in [START_REF] Chang | Super-Resolution Through Neighbor Embedding[END_REF] as the "LS weights".

(c) Apply the same weights for the reconstruction of the output HR patch feature vector y i t with the corresponding neighbors in Y d :

y i t = y j d ∈H(Ni) w ij y j d .
where H(N i ) indicates the corresponding set of the neighborhood N i in the HR dictionary Y d .

2. Once all the HR patch feature vectors are generated, we reverse the features and combine the obtained pixel-based patches to form the output image. Since the LR patches are taken from the input image with some overlap, also the LR patches will be mutually overlapped: the final image is then obtained by simply averaging the pixel values in the common regions.

The key points of the neighbor embedding scheme are the criterion chosen to compute the weights of each neighbor combination and the features used to represent the patches. Results from the original Neighbor Embedding SR algorithm, which is characterized by the so-called LS weights and gradient-based features, show that the error between the super-resolved image and the ground-truth reaches a minimum value for a certain number of neighbors K (see Figure 8 in [START_REF] Chang | Super-Resolution Through Neighbor Embedding[END_REF]). However, this minimum is not always reached for the same K but seems to depend on the target image. This might be due to the constraint used in [START_REF] Chang | Super-Resolution Through Neighbor Embedding[END_REF]. In fact, in [START_REF] Chang | Super-Resolution Through Neighbor Embedding[END_REF] the weights are constrained to sum to one in order to make the reconstruction independent of a frame of reference. This can lead to have negative weights, i.e. the final output HR patches are obtained from both additive and subtractive combinations of patches. We believe that having a non-negativity constraint on the computed weights can help in having a more regular behavior of the performance of the neighbor embedding algorithm, i.e. an error strictly decreasing with K.

In Section 3.1 we derive from SNMF another method to compute the neighbor embedding, that assures the weights to be non-negative. In Section 3.2 we discuss the issue of the features and the other parameters of the algorithm.

OUR SNMF-BASED ALGORITHM

Non-negative weight computation

As we look for non-negative weights, (1) can be changed as follows:

w i = arg min w x i t -X i d w 2 s.t. w ≥ 0 . (2)
(2) can be efficiently approximated by Semi-nonnegative Matrix Factorization (SNMF) [START_REF] Ding | Convex and Semi-Nonnegative Matrix Factorizations[END_REF]. In fact, SNMF is a method to perform a factorization of a matrix, where, differently from "full" Nonnegative Matrix Factorization (NMF) [START_REF] Lee | Learning the parts of objects by non-negative matrix factorization[END_REF], only one factor is constrained to have positive values. The aimed factorization is in the form:

X ≈ F G T , (3)
where we restrict G to be nonnegative, while placing no restriction on the signs of F . In the neighbor embedding case, we can reformulate (3) as x i t ≈ X i d w i , where the matrix to be approximated is a patch of the LR target image, the unconstrained factor is the matrix formed by its neighbors, and the nonnegative factor is the weight vector we want to compute.

In [START_REF] Ding | Convex and Semi-Nonnegative Matrix Factorizations[END_REF] an iterative solution to [START_REF] Chang | Super-Resolution Through Neighbor Embedding[END_REF], that is proved to converge to a local minimum of the Euclidean distance X -F G T 2 , is found. The iterative solution consists of two multiplicative update rules, both for F and G elements. In our case, however, the matrix F , formed by the actual LR patches in the dictionary, is fixed and no update rule is needed for it. We implement then only the rule regarding the weight vector, which, with our notation, can be rewritten in the following way:

w ij ← w ij x j d T X i d + j + w i T X i d T X i d - j x j d T X i d - j + w i T X i d T X i d + j , (4)
where the positive and negative parts of a matrix A are defined respectively as

A + ik = (|A ik | + A ik )/2 and A - ik = (|A ik | - A ik )/2.
The convergence of the formula, i.e. the non-increase of the approximation error x i t -X i d w 2 while updating only the weight vector, can be proved in the same way as in [START_REF] Ding | Convex and Semi-Nonnegative Matrix Factorizations[END_REF]. Thus, (4) can be used as an iterative formula to obtain nonnegative weights for each patch combination.

Features and other parameters

As pointed out in [START_REF] Su | Neighborhood issue in Single-frame Image Super-Resolution[END_REF], the hypothesis of similarity in the neighborhood structures between LR and HR patches, seen as vectors in two possibly distinct feature spaces, does not generally stand. In [START_REF] Chang | Super-Resolution Through Neighbor Embedding[END_REF] a 4-value gradient representation (we call it "Feature 1") is used for the LR patches; for the HR patches, instead, the mean-subtracted luminance values (we call this representation "Feature 2") are used as features: after all HR patch feature vectors are recovered, the features are reversed by simply adding the average luminance value of the corresponding LR input patches. We keep the same scheme for the HR patches and test also Feature 2 as a possible feature representation for LR patches. In fact, by using the same features for LR and HR patches, we think that we can better achieve the assumption of similarity on the neighborhood structures.

After choosing the method for computing the weights of the neighbor embedding and the features, we still have an important parameter to set in the neighbor embedding scheme: the patch size. We experimentally found that the optimal patch size for a LR patch is 3 × 3 with a 2-pixel overlap. The size of the HR patches comes as a consequence of the magnification factor.

EXPERIMENTAL RESULTS

In order to make a comparison between the original LLEbased SR algorithm in [START_REF] Chang | Super-Resolution Through Neighbor Embedding[END_REF] and our SNMF-based algorithm, we report the results for two images. In both cases, we start from an original HR image, which plays as the "groundtruth", and we get the LR input image, by downsizing it. The external dictionaries, "relatively small" in size, are built from the same HR example images. Each example image is downsized by a factor equal to the magnification factor we want to achieve, and blurred by using a Gaussian filter, so obtaining a corresponding LR image. The patch pairs of the dictionaries are then obtained by cutting the LR and HR example images according to the patch sizes chosen (3 × 3 patches with a 2-pixel overlap in the LR case). The data on the dimensions of the two images are reported in Table 2. The dictionary size for the second test is larger, while using the same example images, because the LR example images were obtained by downsizing them by a smaller factor, so generating more patches.

Image HR size

Factor LR size Dict. size "head" To evaluate the performance of the algorithm we used the PSNR (Peak Signal-to-Noise Ratio) as the measure of how close the super-resolved image is from the ground-truth. Fig. 1 and Fig. 2 show the results for the two methods for neighbor embedding, the one used in [START_REF] Chang | Super-Resolution Through Neighbor Embedding[END_REF] (LS) and our SNMF-based method, in terms of PSNR against the number of neighbors (K), respectively using Feature 1 (gradient representation) and Feature 2 (luminance values mean-subtracted) to create the LR patch feature vectors. As we can see from the figures, SNMF behaves much more regularly than LS, with a sligthly increasing curve in both cases, and generally outperforms it. On the other hand, the behavior of LS is diametrically opposite, depending on which feature we choose. In the case of gradient features (Feature 1), the PSNR values reach a maximum and then rapidly decreases; for Feature 2, instead, we have a fall in the performance for medium-range values of neighbors selected and then the PSNR starts to rise again. We can also see that with Feature 2 we have higher PSNR values.

In Fig. 3

CONCLUSION

In this paper we described a new method for single-image SR, that uses an external dictionary and is based on the neighbor embedding approach. With respect to the LLE-based algo-rithm present in the literature, we proposed a different way to embed the neighbors of each patch, so that the corresponding weight coefficients turn out to be non-negative. We derived it from an algorithm designed to perform semi-nonnegative matrix factorizations (SNMF), i.e. with only one factor constrained to have all positive values. Moreover, we used centered pixel values as the features to represent each patch (both LR and HR), differently from the LLE-based algorithm where a gradient-based representation is used for LR patches. We showed that our new SNMF-based SR algorithm has more regular performance as the number of neighbors varies, and generally higher PSNR values on the output image. In particular, by using the new features and choosing a number of neighbors relatively large (e.g. K ≥ 10) we have constantly good results. Visual results also confirm this evaluation.

Fig. 2 :

 2 Fig.2: Comparison between LS and SNMF (PSNR against the number of neighbor) using Feature 2.

Fig. 3 :

 3 Fig. 3: Visual comparison on the head and bird images between simple bicubic interpolation (a), the LLE-based Neighbor Embedding algorithm (b) in a "standard" configuration (Feature 1, K = 5), and our SNMF-based algorithm (c) with Feature 2 and K = 10.

Table 1 :

 1 Notation used for different types of patch feature vectors.

Table 2 :

 2 Dimensions of the two experimental images.

  Comparison between LS and SNMF (PSNR against the number of neighbor) using Feature 1.

		30			30.5
					30
		29.5
					29.5
		29
	PSNR [dB]	28.5	LS SNMF	PSNR [dB]	28.5 29	LS SNMF
					28
		28
					27.5
		27.5
					27
		27	1 2 Fig. 1: 1 2 4 28.3 28.4 28.5 28.6 28.7 28.8 28.9 29 29.1 29.2 PSNR [dB] 4 6 8 10 12 14 16 18 20 22 24 No. of neighbors (K) 1 2 4 6 8 10 12 14 16 18 20 22 24 26.5 No. of neighbors (K) head image bird image	6	8 head image 10 12 14 16 No. of neighbors (K)	18	20 LS SNMF	22	24	PSNR [dB]	27.6 27.8 28 28.2 28.4 28.6 28.8 29 29.2 29.4 29.6	1 2	4	6	8 bird image 10 12 14 16 No. of neighbors (K)	18	20 LS SNMF	22	24


Marco Bevilacqua
email: marco.bevilacqua@inria.fr

Aline Roumy
email: aline.roumy@inria.fr

Christine Guillemot
email: christine.guillemot@inria.fr

Marie - Line

Alberi Morel

Marie-Line Alberi
email: marie_line.alberi-morel@alcatel-lucent.com

Morel Low-Complexity

Marie-Line Alberi Morel

Low-Complexity Single-Image Super-Resolution based on Nonnegative Neighbor Embedding

come   L'archive ouverte pluridisciplinaire

Introduction

Single-image super-resolution (SR) refers to a family of techniques that map an input low resolution (LR) image into a single high resolution (HR) image. Depending on the way this mapping is obtained, SR techniques can be broadly classified into two main approaches: inverse problem methods (e.g. [START_REF] Dai | SoftCuts: A Soft Edge Smoothness Prior for Color Image Super-Resolution[END_REF][START_REF] Farsiu | Fast and Robust Multi-Frame Super-Resolution[END_REF][START_REF] Mohammad-Djafari | Super-Resolution: A Short Review, A New Method Based on Hidden Markov Modeling of HR Image and Future Challenges[END_REF]), where SR is seen as an ill-posed problem and regularization tools are used to solve it, and machine learning (ML) methods, that use a dictionary and aim at learning the mapping.

In ML techniques, as said, the mapping from the LR image to the HR image is learned by using a dictionary. Example-based SR algorithms belong to this family: the learning process is performed locally, by trying to infer the local HR details through the use of small "examples". For general SR purposes the examples used consist of patches (sub-windows of image) and the dictionary is therefore formed by pairs of LR and HR patches. Examplebased SR algorithms can differ in the number of candidates taken from the dictionary and used as predictors (single or several candidates) and the way the patches are combined in order to generate the HR outputs. Another difference is given by the nature of the dictionary: external (derived from a set of training images) or internal (the patch correspondences are derived from the image itself, exploiting self-similarities, e.g. [START_REF] Freedman | Image and Video Upscaling from Local Self-Examples[END_REF][START_REF] Glasner | Super-Resolution from a Single Image[END_REF]).

Example-based SR algorithms can further be divided into two approaches. In local learning methods, the mapping from a LR patch to a HR patch is inferred by using Support Vector Regression [START_REF] Ni | Image Superresolution Using Support Vector Regression[END_REF], linear or Kernel Ridge Regression [START_REF] Tang | Single-image super-resolution via local learning[END_REF]. The other approach is Neighbor Embedding (NE) [START_REF] Chan | Neighbor embedding based super-resolution algorithm through edge detection and feature selection[END_REF][START_REF] Chang | Super-Resolution Through Neighbor Embedding[END_REF][START_REF] Fan | Image Hallucination Using Neighbor Embedding over Visual Primitive Manifolds[END_REF], that first learns the local neighborhood of a LR patch and assumes that this is the best estimate for the local neighborhood of the corresponding HR patch. More precisely, the basic assumption is that the LR and HR patches lie on manifolds with similar local geometries: as a consequence of that, once the LR input patch is expressed as the linear combination of a certain number of its neighbors taken from the dictionary, the HR output patch can be reconstructed by using the HR patches in the dictionary corresponding to the neighbors selected, and combining them in the same way. The way to compute the local neighbor embedding is derived from a manifold learning method for dimensionality reduction called locally linear embedding (LLE) [START_REF] Roweis | Nonlinear Dimensionality Reduction by Locally Linear Embedding[END_REF]. LR and HR patches are expressed as "feature vectors" and the whole SR procedure is carried out in the feature space.

In the wake of these NE-based algorithms, we propose a new single-image SR algorithm, that achieves better performance and a low complexity target. With respect to the LLEbased weight computation method, we propose a new method, based on a Least Squares (LS) approximation of the LR patches with a non-negativity constraint, and prove the effectiveness of the choice of having non-negative weights. Moreover, we discuss the issue of the feature representation and propose to use centered luminance values as unique "low-cost" features for both LR and HR patches. As the low-complexity is one of the targets of the algorithm, we focus on a one-step procedure that directly produces the desired upscaled image, showing that, for the sake of this choice, using an external dictionary is preferable.

The rest of the paper is organized as follows. Section 2 briefly describes the NE-based approach to SR. Then, in Section 3, we provide the details of our algorithm, motivating the choice of the feature representation and the weight computation method adopted: a performance analysis and a complete description of the final procedure are given. In Section 4 some visual results are showed. Finally, Section 5 gives some concluding remarks and outlines for future work.

Neighbor embedding approach to super-resolution

In the NE approach we have a dictionary D = (X d , Y d ), formed by several LR/HR patch co-occurrences, where

X d = {x j d } N d
j=1 is a set of LR patch vectors and

Y d = {y j d } N d
j=1 is the set related to their HR counterparts. The basic idea is that we can express a LR input patch as the weighted combination of its LR K nearest neighbors (K-NN) selected from the dictionary, and then apply the same weighted combination to the corresponding HR patches in the dictionary to reconstruct the HR output patch. All patches, both from the dictionary and the target images, are transformed into feature vectors, by concatenating some features computed on the pixels of the patches. For convenience, in order not to introduce other notations, in this paper all the vectors representing patches are intended as their related feature vectors. The first step is to divide the LR input image X into patches of the same size of the LR patches in the dictionary, and convert them into feature vectors, so obtaining the set of LR feature vectors X t = {x i t } N t i=1 . The algorithm then proceeds as follows:

1. For each LR patch feature vector x i t ∈ X t (a) Find its K-NN in X d in terms of Euclidean distance:

N i = arg min x j d ∈X d K x i t -x j d 2 . (1)
(b) Find a weighted combination that approximates x i t with the selected neighbors, i.e. compute the K weights w i j K j=1 such that:

x i t ≈ ∑ x j d ∈N i w i j x j d . (2)
(c) Apply the same weights for the reconstruction of the output HR patch feature vector y i t with the corresponding neighbors in Y d :

y i t = ∑ y j d ∈H(N i ) w i j y j d . ( 3
)
where H(N i ) indicates the set of HR feature vectors in the dictionary corresponding to the LR neighborhood N i .

2. Once all the HR patch feature vectors are generated, reverse them back to pixel-based patches, and combine the obtained patches to form the output image.

In previous NE-based SR algorithms [START_REF] Chan | Neighbor embedding based super-resolution algorithm through edge detection and feature selection[END_REF][START_REF] Chang | Super-Resolution Through Neighbor Embedding[END_REF][START_REF] Fan | Image Hallucination Using Neighbor Embedding over Visual Primitive Manifolds[END_REF], the weights of each linear combination (Step 1b) are computed by minimizing the approximation error of the related LR patch,

ε i = x i t -∑ x j d ∈N i w i j x j d 2 = x i t -X i d w i 2
, subject to the condition that they sum up to one. Namely, they are the result of the following constrained least squares (LS) minimization problem (SUM1-LS):

w i = arg min w x i t -X i d w 2 s.t. 1 T w = 1 . (4)
A solution to (4) can be found through the method of Lagrange multipliers.

In the following section we propose an alternative criterion to compute the weights of the neighbor embedding and study the issue of the feature representation. This will lead us to the formulation of a new NE-based SR algorithm.

3 Proposed algorithm

Feature representation

As mentioned before, the entire neighbor embedding SR procedure is carried out in a feature space: LR and HR patches are represented by vectors of features, namely some transformations of the luminance values of the pixels of the patch. The role of the features is double: 1) to catch the most relevant part of the LR information in order to have a good "predictor" for the HR patch reconstruction; 2) to possibly enforce the similarity between the LR and HR patch structures.

In order to pursue the first purpose, several algorithms in the literature propose to preprocess the LR images according to the idea that the middle and high-frequency content of the LR patches is the most helpful information to learn the LR-HR patch correspondences. In the original NE-based algorithm [START_REF] Chang | Super-Resolution Through Neighbor Embedding[END_REF], e.g. simple features derived from the first and secondorder gradient are taken into account. As for the representation of the HR training patches, the common solution in the literature is to straightly use the luminance values of the HR training images, possibly after doing an operation of contrast normalization or mean removal. In our implementation of the neighbor embedding approach, we test three simple feature configurations for the LR patches. In order to pursue the second purpose, we would like to keep the same feature space for the LR and HR patches. However, at the end of the SR algorithm we have to reverse the features back to pixel-based patches. This reversion step is not feasible in the case of gradient feature vectors (more "unconstrained" equations than unknowns); we can reverse the centered features, instead, by simply adding the mean value of the corresponding LR patches in the input image. Therefore, F2 is the only possible choice for the the HR features.

Among the 3 possible options for the LR features (F1, F2, F1+F2), we expect centered luminance values (F2) to be the most intuitive solution, as the representation for LR and HR patches would be unique. Moreover, this is the "cheapest" solution in terms of computational time, as the feature vectors contain less entries than for the other feature representations. In [START_REF] Chan | Neighbor embedding based super-resolution algorithm through edge detection and feature selection[END_REF] a performance analysis of the feature representations is given, including gradient features and centered luminance values ("norm luminance"): the authors conclude that the best solution for the LR features is a weighted concatenation of norm luminance and first-order gradient values, while purely centered luminance values representing the fourth or fifth choice (see Figure 3 in [START_REF] Chan | Neighbor embedding based super-resolution algorithm through edge detection and feature selection[END_REF]). However, this analysis is not performed by considering variations of K (number of neighbors). Figure 1 evaluates for two test images ("head" and "bird") the performance of the algorithm (PSNR of the super-resolved image) versus K, for the chosen LR features and the standard SUM1-LS method used to compute the weights.

head bird Figure 1 shows that the performance of the algorithm is highly dependent on the number of neighbors K. For all the feature representations, we observe that the curves present an "up-down-up" behavior; the fall in the case of centered features appears even dramatic. We explain this behavior with the "blindness" of the NE approach: the weights of the patch combinations are computed on the LR feature vectors and then blindly applied to the corresponding HR vectors. As we observe, a problem arises at a certain critical point that depends on d. For F2, we can make the following observations. Observation 3.1. Let d be the dimension of the LR vectors, K the number of neighbors, and r i the rank of the ith neighborhood matrix X i d . Then, the neighbors (centered) vectors lie on a d -1-dimensional hyperplane, and the rank of the neighborhood matrix is upper-bounded as follows: r i ≤ min(d -1, K). For the dictionary built as in Section 3.3, we observe that the upper bound is tight. More precisely, r i = min(d -1, K) with high probability.

Observation 3.2. For K = d the SUM1-LS problem is assimilable to the solution of a square linear system, as we have d equations (the d -1 linearly independent equations of x i t ≈ X i d w i plus the one given by the equality constraint) in K = d unknowns. Here, experimentally we have a "critical point" in the performance.

Intuitively, we explain this criticality with the fact that the LS solution is "too fitted" on the LR data and thus generates undesired bad HR reconstructions. In Figure 1 this point is, in case of F2, at K = d = 9, as we use 3 × 3 LR patches.

Nevertheless, we observe that outside the fall region, centered luminance features outperform the other feature representations, thus showing the expected potential. Therefore, we decide to use F2 as unique features for LR and HR patches. In the following section we propose a new criterion for the weight computation, in order to avoid the irregular performance with K and fully exploit the common features.

Non-negative embedding

In the previous section we pointed out that, for any feature chosen, we have a fall of the performance for a certain critical point, by using SUM1-LS as a NE method.

We believe that this problem can be avoided by replacing the sum-to-one equality constraint by a more "relaxed" inequality constraint. Therefore, we propose another method for computing the neighbor embedding, derived from a LS problem equivalent to (4), but with a non-negativity inequality constraint, according to "the intuitive notion of combining parts to form a whole" [START_REF] Lee | Learning the parts of objects by non-negative matrix factorization[END_REF] (only additive combinations of patches are allowed):

w i = arg min w x i t -X i d w 2 s.t. w ≥ 0 . ( 5
)
The problem in [START_REF] Fan | Image Hallucination Using Neighbor Embedding over Visual Primitive Manifolds[END_REF] is known in the literature as non-negative least squares (NNLS); an iterative solution is provided in [START_REF] Hanson Charles | Solving Least Squares Problems[END_REF]Ch. 23,p. 161]. The formula experimentally turns out to converge after an average of 2 iterations.

In Figure 2 the weight distributions of the two NE criteria are compared, using the box plot representation. Each box is delimited by the 25th (Q1) and 75th percentile (Q3). Values that exceed the boxes by 2 × (Q3 -Q1) are considered outliers and not drawn. Interestingly, the values for SUM1-LS weights get larger in the proximity of the critical points; instead, the values of the NNLS weights regularly decrease with K.

To further evaluate the goodness of the new nonnegative NE criterion, compared to SUM1-LS, we used the distance (in terms of MSE) between the LR weights, resulted by SUM1-LS NNLS the approximation of a LR test vector with its LR neighbors, and the HR weights, obtained by approximating the corresponding HR test vector with the HR vectors related to the LR neighbors found. This is an index of how the LR weights, what we can actually compute, reflect the ideal HR weights. We averaged the error over 1000 randomly selected test vectors (Figure 3). F1 F2 F1 + F2 Figure 3 shows that the new nonnegative embedding method is much more suitable for computing the weights of a common embedding, as the MSE error between the weight vectors is, in any case, below the corresponding one for SUM1-lS. The results are confirmed in Figure 4, where a comparison between different features (in terms of ouput PSNR), while using NNLS, is presented.

Compared to Figure 1, Figure 4 presents a much more stable performance, as K varies: the PSNR curve is monotonically increasing. Moreover, the PSNR values are generally higher and F2 are clearly the winning features.

Dictionary design

From the analysis undertaken in the previous sections, we can derive a new feature-based NE-based SR algorithm: centered luminance values (F2) are taken as features for both LR and HR patches, and the new NE method with nonnegative weights is chosen to compute the patch combinations. An important issue for example-based SR algorithms is represented by the choice of the dictionary. To pursue the aim of realizing a low-complexity algorithm, we decide to adopt head bird a one-step upscaling procedure, whereas other algorithms (e.g. [START_REF] Freedman | Image and Video Upscaling from Local Self-Examples[END_REF][START_REF] Glasner | Super-Resolution from a Single Image[END_REF]) achieve the desired magnification factor by several upscalings with smaller scale factors (the SR procedure is thus iterated several times). For the dictionary, we have then two possibilities: 1) build an external dictionary from a set of training images (from the original HR images, generate the LR versions, and extract HR and LR patches, respectively); 2) learn the patch correspondences in a pyramid of recursively scaled images, starting from the LR input image, in the way of [START_REF] Glasner | Super-Resolution from a Single Image[END_REF]. In Table 1 results from the pyramid internal dictionary and two external dictionaries are reported; NNLS with K = 12 is used as the NE method. For both the external dictionaries, a small number of natural images is taken. As we can see from the table, the external dictionary performs significantly better, since the number of pairs of patches we can derive from the internal pyramid is insufficient. On the other hand, the size of the external dictionary can be tuned to any value, by conveniently choosing the training images. In this paper, we choose a dictionary s.t. the upscaling of a 70 × 70 image by a factor of 4 takes about 5 seconds.

There is one important parameter left to set in the algorithm: the size of the LR patches taken from the LR input image. From our experiments we found that the optimal size is 3 × 3 with a 2-pixel overlap. As we perform a one-step upscaling, the size and the overlap degree of the HR patches come as consequences of the magnification factor: e.g. with a factor of 4 we will have 12 × 12 HR patches with a 8-pixel overlap. The reason for choosing largely overlapping HR patches is due to the fact that at the end of the NE algorithm (see Step 2 of the general procedure in Section 2) we combine the patches together by simply averaging the related pixel values in the overlapping regions. By having big overlaps, we can in fact implicitly impose smooth properties on the output image. Moreover, as an additional tool used by several SR algorithms (e.g. [START_REF] Glasner | Super-Resolution from a Single Image[END_REF]), we implement a final check to assure the superresolved image to be consistent with the LR input image: an iterative back projection (IBP). Note that [START_REF] Glasner | Super-Resolution from a Single Image[END_REF] uses IBP, that stops on average after 3 iterations, at each step; we use it only once instead.

Results

In this section some visual results and comparisons with other methods are presented. In particular, our algorithm is compared to the original LLE-based NE algorithm of Chang et al. [START_REF] Chang | Super-Resolution Through Neighbor Embedding[END_REF], to [START_REF] Glasner | Super-Resolution from a Single Image[END_REF] (using a third party implementation), which is currently considered among the most advanced single-image SR algorithms, and to the KRR method of Tang et. al [START_REF] Tang | Single-image super-resolution via local learning[END_REF]. Table 2 summarizes the results for several images and magnification factors, reporting the output PSNR and the running time in seconds as an indication of the complexity of the algorithm. Figure 5 offers a few visual results for two images; more results can be found in http://www.irisa.fr/prive/Aline.Roumy/results/SR_BMVC12.html.

When comparing our algorithm to Chang et al. [START_REF] Chang | Super-Resolution Through Neighbor Embedding[END_REF] the visual improvements are evident: our algorithm is able to super-resolve finer details, whereas the results of [START_REF] Chang | Super-Resolution Through Neighbor Embedding[END_REF] are often affected by ringing artifacts. The impression is confirmed by reading the PSNR values. With respect to the local learning method of Tang et al. [START_REF] Tang | Single-image super-resolution via local learning[END_REF], too, the PSNR achieved by our algorithm are always higher. As for the running time, this turns to be in favor of our algorithm in both comparisons, thanks to the low-complexity choice of the features (F2 instead of gradient features). The comparison with the method of Glasner et al. [START_REF] Glasner | Super-Resolution from a Single Image[END_REF] is also satisfying: [START_REF] Glasner | Super-Resolution from a Single Image[END_REF] gives generally higher values of PSNR, although our method is better performing for a magnification factor equal to 2. Nevertheless, the visual results are fairly comparable. What represents an issue for [START_REF] Glasner | Super-Resolution from a Single Image[END_REF] is the complexity, as the algorithms involves several steps and the dictionary is iteratively updated by taking patches from the image "pyramid": although the values provided only serve to give an idea of the complexity, the algorithm clearly requires much more time than ours and the running time grows exponentially with the size of the input image.

Conclusion and future work

In this paper we proposed a novel algorithm for single-image SR, based on neighbor embedding. With the double target of low complexity and good performance, we handled with three aspects: the representation of the patches, the weight computation method, and the dictionary design. We chose to use centered luminance values as unique "low-cost" solution for both the LR and HR feature-based patch representations, and proposed a new method for computing the weights based on nonnegative LS. We chose, then, to use an external dictionary, showing that this solution is more convenient than having an internal dictionary, when a single-step magnification is performed. The algorithm so designed, when compared to other single-image SR methods, is shown to give good visual results and to present a much reduced time complexity, thanks to the one-step upscaling procedure adopted and the feature representation chosen. As for the future work, we believe that the NE-based procedure can be improved in the neighbor selection step: different metrics than the Euclidean distance with the LR candidate can be taken into account in order to select neighbors more suitable for the HR reconstruction. In the flavor of [START_REF] Tang | Single-image super-resolution via local learning[END_REF], we also plan to investigate methods based on the local learning of the LR-HR mapping function, and to consider in this case too the issue of the features. In fact, as we can see from the last column of Table 2, by applying our features (centered luminance values) to a simple linear regression model, we already obtain promising results.

F 1

 1 First order gradient: first-order derivatives in both directions are computed for each pixel of the patch (2 values per pixel), by applying to the luminance matrix g 1 = [-1, 0, 1] and g 2 = g T 1 as 1-D filters. Let N be the number of pixels in a patch and d the dimension of the LR feature vectors, then d = 2N. F 2 Centered luminance values: the features are obtained by taking the luminance values and subtracting the mean value. This corresponds to remove the DC component of the patch; we can therefore see also this method as providing a low-cut filtered version of the LR patch. In this case, d = N. F 3 F1+F2: concatenation of F1 and F2 (thus, d = 3N) as considered as in [1].

Figure 1 :

 1 Figure 1: Comparison between LR feature representations, SUM1-LS used as NE method.

Figure 2 :

 2 Figure 2: Distribution of the weights for each value of K; F2 used as LR features.

Figure 3 :

 3 Figure 3: Comparison between SUM1-LS and NNLS in terms of MSE of the LR/HR weight vectors.

Figure 4 :

 4 Figure 4: Comparison between LR feature representations, NNLS used as NE method.

Figure 5 :

 5 Figure 5: Results for the "baby" (×4) and the "bird" (×3) images: (a) Our algorithm -(b) Chang et al. [2] -(c) Glasner et al. [8] (7 steps for "baby", 5 steps for "bird").

Table 1 :

 1 Final PSNR and DB size (i.e. number of pairs of patches) for different dictionaries.

			Internal DB	Ext DB "esa"	Ext DB "wiki"
	Image	Magn. Factor PSNR DB size PSNR DB size PSNR DB size
	Baby	4	27.95 2179	30.62 56514	30.32 218466
	Bird	3	27.72 2256	31.37 100966 31.42 389232
	Woman 2	27.29 15044	30.91 229096 30.44 880440

Table 2 :

 2 Results (PSNR and running time in sec.) for different images.

			Our algorithm	Chang et al.	Glasner et al.	Tang et al.	Lin. Regr. + F2
	Image	Scale PSNR	Time PSNR Time PSNR	Time PSNR	Time PSNR Time
	baby	2	34.64	58	33.42	339	34.66	4083	33.72	425	34.76	30
	bird	2	34.69	18	32.94	110	34.42	406	33.31	132	34.91	9
	butterfly	2	27.54	17	25.90	77	26.83	265	26.05	82	27.66	7
	head	2	32.88	18	32.34	145	32.68	367	32.43	151	32.88	8
	woman	2	30.91	15	29.43	114	30.61	410	29.64	128	31.01	8
	baby	3	32.44	27	31.00	116	32.94	2188	31.47	111	32.59	12
	bird	3	31.37	9	29.71	47	32.16	281	30.07	42	31.57	5
	butterfly	3	24.31	9	22.58	34	25.66	232	22.72	25	24.47	4
	head	3	31.46	12	30.82	68	31.69	370	30.95	54	31.55	4
	woman	3	27.98	12	26.45	37	28.79	248	26.66	37	28.12	4
	baby	4	30.62	22	29.27	86	31.41	4381	29.70	81	30.76	13
	bird	4	28.99	6	27.37	21	30.07	475	27.84	22	29.12	3
	butterfly	4	22.05	7	20.50	18	23.94	315	20.61	13	22.06	3
	head	4	30.26	6	29.57	26	30.86	379	29.83	28	30.43	3
	woman	4	25.66	5	24.25	17	26.79	401	24.46	20	25.69	3