Y Chen

L R G Dias

AND K Takeuchi

M Tibăr
email: tibar@math.univ-lille1.fr

R G Dias

INVERTIBLE POLYNOMIAL MAPPINGS VIA NEWTON NON-DEGENERACY

Keywords: 2010 Mathematics Subject Classification. 14D06, 58K05, 57R45, 14P10, 32S20, 58K15 singularities of real polynomial mappings, fibrations, bifurcation locus, Newton polyhedron, atypical values, regularity at infinity, semi-algebraic Sard type theorem. L

We prove a sufficient condition for the Jacobian problem in the setting of real, complex and mixed polynomial mappings. This follows from the study of the bifurcation locus of a mapping subject to a new Newton non-degeneracy condition.

Introduction

Unlike the local setting, the critical locus is not the only obstruction to produce diffeomorphisms in the global setting. A well-known example by Pinchuk [Pi] yields a polynomial mapping R 2 → R 2 with no singularities but which is not invertible, thus providing a counter-example to the strong Jacobian Conjecture over the reals. A natural question, also posed by Bivià-Ausina for real mappings in [Bi], would then be: given a polynomial mapping G : A n → A n with Sing G = ∅, where A = R or C, under what general enough conditions G becomes a diffeomorphism. For polynomial mappings over C, being a diffeomorphism (actually "injective" is enough by [BR]) ensures that G -1 is a polynomial map too (see [START_REF] Grothendieck | Éléments de géométrie algébrique. IV. Étude locale des schémas et des morphismes de schémas[END_REF]Proposition 17.9.6] and [CR]), but this fact is no more true over the reals.

We obtain here a new sufficient condition for the invertibility of G as a by-product of the study of the bifurcation locus of a polynomial mapping F : A n → A k , n ≥ k. This is the minimal set of points B(F ) ⊂ A k out of which the mapping is a locally trivial fibration. One has no complete knowledge over this set unless k = 1 and n = 2, see [Su], [HL] [Du], [START_REF] Tibăr | Regularity at infinity of real and complex polynomial functions[END_REF], [TZ]. In more variables, one may estimate B(F ) by some "reasonably good" superset B ⊃ B(F ) by using criteria of regularity at infinity. This was first done in case of complex polynomial functions f : C n → C with conditions like tameness [START_REF] Broughton | On the topology of polynomial hypersurface, Singularities[END_REF], Malgrange regularity [Pa], ρ-regularity [START_REF] Némethi | Milnor fibration at infinity[END_REF], [START_REF] Tibăr | Regularity at infinity of real and complex polynomial functions[END_REF], W-equisingularity [Ve], [ST] etc. Each of these conditions holds over R too and exhibits, in both settings, a finite subset of "non-regular values" containing the bifurcation set B(F ) (see e.g. [START_REF] Tibăr | Regularity at infinity of real and complex polynomial functions[END_REF], [START_REF] Tibăr | Polynomials and Vanishing Cycles[END_REF]). For k > 1, Rabier [Ra] considered an asymptotic regularity derived from a Palais-Smale type condition which extends the Malgrange regularity. This allows him to define a set of "asymptotically critical values" K ∞ (F ) and to prove that B(F ) ⊂ F (Sing F ) ∪ K ∞ (F ). In order to evaluate K ∞ (F ), we introduce here a new Newton non-degeneracy condition at infinity, see Definition 3.4. Besides real and complex polynomial mappings, we consider mixed mappings, which are mappings C n → C k in variables z and z. We first obtain the following bound of the asymptotical critical locus of F = (f 1 , . . . , f k ), in terms of two subsets of A k depending on the Newton polyhedra of the functions f i , denoted by N(F ) and A(F ) (see Definitions 3.5 and 3.8), the first of which is algebraic and the second, semi-algebraic:

Theorem 1.1. Let F : A n → A k , n ≥ k, be a real, complex or mixed polynomial mapping depending effectively on all the variables, such that F (0) = 0. If F is non-degenerate at infinity then:

K ∞ (F ) ⊂ N(F ) ∪ A(F ).
Using the inclusions B(F ) ⊂ F (Sing F ) ∪ S(F ) and S(F ) ⊂ K ∞ (F ) proved in [DRT] and discussed here in §2 and Proposition 2.4, we immediately get the following bound for the bifurcation locus:

Corollary 1.2. B(F ) ⊂ F (SingF ) ∪ N(F ) ∪ A(F ).
By Proposition 2.4, our Theorem 1.1 extends to mappings (real, complex or mixed) the result for complex polynomial functions proved by in the complex setting and more recently by Chen-Tibăr [START_REF] Chen | Bifurcation values of mixed polynomials[END_REF]Theorem 1.1(a)] in the mixed setting. Moreover, when applied to mixed mappings F : C n → C k , our Theorem 1.1 yields a better result than for the same underlying real mapping F : R 2n → R 2k . This is not only trivially visible in the first term of the union

N(F ) ⊂ A k \ (A * ) k since A = R is replaced by A = C,
but also in the second term since the involved Newton polyhedra turn out to be different. Moreover, the statement in the mixed setting cannot be deduced from the one in the real setting; its proofs is similar but needs specific notations and preliminaries. We give in §4 the proof of Theorem 1.1 and show the following significant consequence (cf. Definitions 3.1 and 3.4):

Corollary 1.3. Suppose that F is non-degenerate at infinity and that f i is convenient,

for any i = 1, . . . , k. Then K ∞ (F ) = ∅.
This provides an extension to mappings (which can be real, complex or mixed) of Broughton's classical result [START_REF] Broughton | On the topology of polynomial hypersurface, Singularities[END_REF]Proposition 3.4] which tells that if a complex polynomial function f : C n → C is convenient and Newton non-degenerate then F is "tame", thus K ∞ (F ) = ∅. The proof of our Corollary 1.3 will be given in §4).

With all these preparations, we may state and prove the announced result:

Theorem 1.4. Let F : A n → A n be a C 1 real semi-algebraic mapping such that Sing F = ∅. If K ∞ (F ) = ∅ then F is a global diffeomorphism.
In particular, if F = (f 1 , . . . , f n ) is a real, or a mixed, or a complex polynomial mapping with Sing F = ∅, non-degenerate at infinity, and if f i is convenient for all i = 1, . . . , n, then F is a global diffeomorphism.

Proof. Let J F denote the set of points at which F is not proper (see Definition 2.2 and [START_REF] Jelonek | Testing sets for polynomial mapping[END_REF]Definition 3.3]). By [START_REF] Kurdyka | Semialgebraic Sard theorem for generalized critical values[END_REF]Proposition 3.1], one has K ∞ (F ) = J F . Thus if K ∞ (F ) = ∅ then F is proper. It is moreover a submersion since Sing F = ∅ by hypothesis. A proper submersion is an open and closed mapping, a general topological fact. Thus F is a covering and it must be one-to-one since its image A n is simply connected. Our first assertion follows. Remark that the final part of this proof is actually Hadamard's theorem, see e.g. [vdE, p. 240]. Our second assertion then follows by Corollary 1.3.

One of the new issues of our paper is the non-degeneracy condition at infinity which appears to be a generic condition (Definition 3.4). This extends to mappings the definitions of "Newton non-degeneracy at infinity" for functions, both in the complex setting [Ku], [START_REF] Broughton | On the topology of polynomial hypersurface, Singularities[END_REF], [START_REF] Broughton | Milnor numbers and the topology of polynomial hypersurfaces[END_REF], [START_REF] Némethi | On the bifurcation set of a polynomial function and Newton boundary[END_REF] and in the more recently developed mixed setting [CT]. Moreover, this works over the reals too. Our Definition 3.4 is particularly designed to treat the case of non-convenient polynomial mappings (cf Definition 3.1) since bifurcation values at infinity appear only in this context, see Corollary 1.3. In the real setting, Bivià-Ausina considers in [Bi] a different Newton non-degeneracy condition for real polynomial mappings F : R n → R k and use it in case each component f i is convenient. He proves a result like the second statement of our Theorem 1.4 in case of a real polynomial mapping F : R n → R n . His proof aims to obtain the properness of F , necessary for the bijectivity of F , via an interpretation of his non-degeneracy condition in terms of Łojasiewicz exponents. The author observes in [START_REF] Bivià-Ausina | Injectivity of real polynomial maps and Łojasiewicz exponents at infinity[END_REF]p. 746] that the techniques used in his paper work only for real polynomial mappings. We show in §5 that in the real setting and for n = k, the two definitions are equivalent. However, Proposition 5.2 and Example 5.3 tell that, whenever n > k and f i is convenient for every i, our definition is strictly more general than the one considered in [Bi]. Our definition of non-degeneracy for mappings is new especially for mixed and complex mappings and in general for non-convenient mappings in all settings. The mixed setting is particularly interesting upon the real one by the fact that a mixed mapping may be convenient without the underlying real components to be convenient, whereas if all the real components are convenient then the mixed functions must be also convenient (see Example 5.4).

Asymptotic critical values

Let F = (f 1 , . . . , f k ) : A n → A k , n ≥ k, be a C 1 real semi-algebraic mapping with f i ≡ const., ∀i = 1, . . . , k.
The Milnor set of F , denoted by M(F ), is the critical locus of the mapping (F, ρ), where ρ : A n → R ≥0 denotes the Euclidean distance function. From its definition, it follows that M(F ) is a closed semi-algebraic subset of A n and that, in the case n = k, M(F ) coincides with the whole

A n . Definition 2.1. Let F : A n → A k be a C 1 non-constant real semi-algebraic mapping.
The set of asymptotic non ρ-regular values of F is defined as

S(F ) := c ∈ A k | ∃ {x l } l∈N ⊂ M(F ), lim l→∞ x l = ∞ and lim l→∞ F (x l ) = c . Definition 2.2. [Je1, Definition 3.3] Let F : A n → A k be a continuous mapping. We say that F is proper at a point c ∈ A k if there exists an open neighbourhood U of c such that the restriction F |F -1 (U ) : F -1 (U) → U
is a proper mapping. We denote by J F the set of points at which F is not proper.

One also has the set of generalised critical values K(F ) := F (Sing F ) ∪ K ∞ (F ), where: Definition 2.3. [START_REF] Rabier | Ehresmann's fibrations and Palais-Smale conditions for morphisms of Finsler manifolds[END_REF]p. 670], [START_REF] Kurdyka | Semialgebraic Sard theorem for generalized critical values[END_REF]p. 68] The set of asymptotic critical values of a real semi-algebraic mapping F : A n → A k is defined as:

K ∞ (F ) := {c ∈ A k | ∃{x l } l∈N ⊂ A n , lim l→∞ x l = ∞, lim l→∞ F (x l ) = c and lim l→∞ (1 + x l )ν(dF (x l )) = 0}, where ν(B) := inf ϕ =1 B * (ϕ) , for B ∈ L(A n , A k ).
In the context of semi-algebraic F : R n → R p , Kurdyka, Orro and Simon showed in [KOS] that K ∞ (F ) is a semi-algebraic set of dimension at most k -1. Gaffney [Ga] defined a generalised Malgrange condition in the setting of complex polynomial mappings

C n → C k and proved that this condition yields a set A G (F ) of non-regular values such that B(F ) ⊂ F (Sing F ) ∪ A G (F ).
Then Jelonek [START_REF] Jelonek | On asymptotic critical values and the Rabier theorem[END_REF] showed that the asymptotic conditions employed in [KOS] and in [Ga] are equivalent, i.e. that K ∞ (F ) = A G (F ).

More recently, [DRT] proved, in the setting of semi-algebraic mappings, the inclusion B(F ) ⊂ F (SingF ) ∪ S(F ) and that S(F ) and F (SingF ) ∪ S(F ) are closed semi-algebraic sets of dimension ≤ k -1 (more precisely, [START_REF] Dias | Regularity at infinity of real mappings and a Morse-Sard theorem[END_REF]Theorem 5.7] in the case n > k and [KOS, Theorem 3.1 and Proposition 3.1] in the case n = k).

From the above definitions we get the inclusions S(F

) ⊂ J F and K ∞ (F ) ⊂ J F . In the case n = k one has J F = K ∞ (F ) by [KOS, Proposition 3.1], hence S(F ) = J F = K ∞ (F ).
For n ≥ k, the inclusion S(F ) ⊂ K ∞ (F ) was shown in [CT, Proposition 2.2] for a mixed polynomial, and in the more general real setting in [START_REF] Dias | Regularity at infinity of real mappings and a Morse-Sard theorem[END_REF]Corollary 5.8]. Here we offer a new and direct proof of this inclusion.

Proposition 2.4. Let F = (f 1 , . . . , f k ) : A n → A k be a C 1 non-constant real semi- algebraic mapping with n ≥ k. Then S(F ) ⊆ K ∞ (F ).
Proof. We give the proof over R. Then the statement over C can be obtained from the one over R by using the identification C n with R 2n .

In the case n = k, as explained just above, we have equality. We concentrate in the following to the case n > k.

Let c = (c 1 , . . . , c k ) ∈ S(F ). Since M(F ) is semi-algebraic, one can use the Curve Selection Lemma at infinity to find an analytic path φ

= (φ 1 , . . . , φ n ) :]0, ǫ[→ M(F ) ⊂ R n such that lim t→0 φ(t) = ∞ and lim t→0 F (φ(t)) = c. Since φ(t) ∈ M(F ) if and only if rank dF (φ(t)) < k+1, there exist curves λ(t), b 1 (t), . . . , b k (t) such that (λ(t), b 1 (t), . . . , b k (t)) = (0, . . . , 0)
, ∀t, and one has the equality:

(1)

λ(t)(φ 1 (t), . . . , φ n (t)) = b 1 (t) ∂f 1 ∂x (φ(t)) + . . . + b k (t) ∂f k ∂x (φ(t))
,

where ∂f i ∂x (φ(t)) = ∂f i ∂x 1 (φ(t)), . . . , ∂f i ∂xn (φ(t)) , for i = 1, . . . , k. Consider b(t) = (b 1 (t), . . . , b k (t)).
From the equality (1) and by the statements that (λ(t), b 1 (t), . . . , b k (t)) = (0, . . . , 0), ∀t, and lim t→0 φ(t) = ∞, we have b(t) = 0, ∀t and consequently, from (1), we obtain:

(2)

λ(t) b(t) (φ 1 (t), . . . , φ n (t)) = b 1 (t) b(t) ∂f 1 ∂x (φ(t)) + . . . + b k (t) b(t) ∂f k ∂x (φ(t));
and we will denote λ 0 (t) := λ(t) b(t) and a(t) := b(t) b(t) . So, a(t) = 1 and one obtains the following equalities:

(3)

k i=1 a i (t) d dt f i (φ(t)) = k i=1 a i (t) ∂f i ∂x (φ(t)), φ ′ (t) = 1 2 λ 0 (t) d dt φ(t) 2 ,
where the later follows from (2), i.e., from the equality k i=1 a i (t) ∂f i ∂x (φ(t)) = λ 0 (t)φ(t). On the other hand, since

lim t→0 f i (φ(t)) = c i , it follows that ord t d dt f i (φ(t)) ≥ 0, i = 1, . . . , k.
This and the equality (3) imply:

(4) 0 ≤ ord t λ 0 (t) d dt φ(t) 2 < ord t λ 0 (t) φ(t) 2 .
Now, from (2) one obtains:

(5)

ord t φ(t) a 1 (t) ∂f 1 ∂x (φ(t)) + . . . + a k (t) ∂f k ∂x (φ(t)) = ord t |λ 0 (t)| φ(t) 2 ,
which is positive by (4). This implies:

lim t→0 φ(t) a 1 (t) ∂f 1 ∂x (φ(t)) + . . . + a k (t) ∂f k ∂x (φ(t)) = 0,
which, in turn, implies lim t→0 φ(t) ν(dF (φ(t))) = 0. This shows that c ∈ K ∞ (F ).

Newton polyhedra and the non-degeneracy at infinity

Let f : A n → A be a non-constant polynomial function, A = R or C. We write:

f (x) = ν c ν x ν , where ν = (ν 1 , • • • , ν n ) ∈ N n and x ν = x ν 1 1 • • • x νn n .
In the mixed case, we write:

f (z, z) = ν,µ c ν,µ z ν zµ , where ν = (ν 1 , • • • , ν n ), µ = (µ 1 , • • • , µ n ) ∈ N n , z ν = z ν 1 1 • • • z νn n and zµ =z µ 1 1 • • • zµn n .
Mixed polynomials is a much larger class than complex polynomials and have been introduced by Oka, who studied several aspects of their local topology in [START_REF] Oka | Topology of polar weighted homogeneous hypersurfaces[END_REF], [START_REF] Oka | Non degenerate mixed functions[END_REF] and some other more recent articles. In [CT] we have used the mixed Newton polyhedron at infinity of a polynomial function.

Definition 3.1. Let f : A n → A be a non-constant polynomial function (resp. mixed function) such that f (0) = 0. We call supp (f ) = {ν ∈ N n | c ν = 0} (resp. supp (f ) = {ν + µ ∈ N n | c ν,µ = 0}
) the support of f . We say that f is convenient if the intersection of supp (f ) with each coordinate axis is non-empty. We denote by supp(f ) the convex hull of the set supp(f ). The Newton polyhedron of f , denoted by Γ 0 (f ), is the convex hull of the set {0} ∪ supp(f ). The Newton boundary at infinity of f , denoted by Γ + (f ), is the union of the faces of the polyhedron Γ 0 (f ) which do not contain the origin. By "face" we mean face of any dimension. Let ∆ be such a face of supp(f ). The restriction of f

to ∆ ∩ supp(f ), denoted by f ∆ , is defined as follows f ∆ (x) := ν∈∆∩supp(f ) c ν x ν (resp. f ∆ (z, z) := ν+µ∈∆∩supp(f ) c ν,µ z ν z µ ).
Let us consider in the following a real, mixed or complex mapping F = (f 1 , . . . , f k ) :

A n → A k , n ≥ k with F (0) = 0.
Definition 3.2. For some vector p = (p 1 , . . . , p n ) ∈ Z n with p := min 1≤i≤n p i < 0, let l p (v) := n i=1 p i v i be the linear form defined by p. Let then ∆ j p be the maximal face of Γ 0 (f j ) (maximal with respect to the inclusion of faces) where l p (v) takes its minimal value on Γ 0 (f j ). We consider the following equivalence relation on the set of vectors p as above:

p ′ ∼ p ⇐⇒ ∆ j p ′ = ∆ j p , for all 1 ≤ j ≤ k. The equivalent classes yield a partition of R n \ R n
+ into finitely many locally closed (and not necessarily convex) cones. We may however subdivide each equivalence class into a finite number of convex polyhedral cones.

Let C(F ) denote the finite set of cones obtained in this way. We call it the dual subdivision associated to F .

It follows from the above definition that, for any j, the face ∆ j p of Γ 0 (f j ) is independent of the defining vector p in its equivalence class. We therefore use the notations ∆ j σ for σ ∈ C(F ), instead of ∆ j p for some p ∈ σ. The following sets are therefore well defined:

I σ = {1 ≤ j ≤ k | 0 ∈ ∆ j σ }, J σ = {1 ≤ j ≤ k | ∆ j σ = {0}}. Remark 3.3. Let d j
p ∈ Z denote the minimum value of the restriction of l p to supp(f ). We have the following relations which follow directly from the definitions:

(a) j ∈ I σ ⇐⇒ d j p < 0 for any p ∈ σ ⇐⇒ ∆ j σ is a face of Γ + (f j ). (b) j ∈ J σ ⇐⇒ Γ 0 (f j ) \ {0} is included into the positive half-space defined by the hyperplane {l p = 0} in R n with normal vector p, for any p ∈ σ.

The following definition of non-degeneracy is inspired from Oka's work [START_REF] Oka | Non-degenerate complete intersection singularity[END_REF] on complex local complete intersections and from the definition used by Matsui-Takeuchi [MT] and Esterov-Takeuchi [ET] in the global setting of complex polynomials. It was proved in [START_REF] Oka | Non-degenerate complete intersection singularity[END_REF] that, in the complex context, this is a generic condition. Definition 3.4. We say that the polynomial mapping F = (f 1 , . . . , f k ) : A n -→ A k is non-degenerate at infinity if, for any σ ∈ C(F ) such that I σ = ∅ and J σ = ∅, the subvariety:

(6) G σ = {x ∈ (A * ) n | f ∆ j σ (x) = 0 for any j ∈ I σ } of (A * ) n is a non-degenerate complete intersection (i.e. Sing (f ∆ j σ ) j∈Iσ ∩ G σ = ∅)
, where f ∆ j σ is a short notation for the restriction of f j to ∆ j σ . Definition 3.5. Let C(F ) ex := {σ ∈ C(F ) | J σ = ∅} be called the set of exceptional cones. Let N σ = {(z 1 , . . . , z k ) ∈ A k | z j = 0 for any j ∈ J σ }. We then define the following algebraic subset of A k of A-codimension ≥ 1:

N(F ) := ∪ σ∈C(F )ex N σ .
Remark 3.6. The above definition implies that we have the inclusion N(F ) ⊂ A k \ (A * ) k . Whenever k ≥ 2, one can characterise the situations when this inclusion is strict, as follows. Let C i denote the set of hyperplanes H ⊂ R n through the origin such that H ∩ Γ 0 (f i ) = {0}. Then: N(F ) A k \ (A * ) k if and only if there exists j ∈ {1, . . . , k} such that C j ⊂ ∪ i =j C i . Indeed, the condition C j ⊂ ∪ i =j C i is equivalent to the fact that there is no σ ∈ C(F ) such that J σ = {j}.

Remark 3.7. From the definition of N(F ) we immediately get the equivalence:

N(F ) = ∅ ⇐⇒ for any i ∈ {1, . . . , k}, f i is convenient. If all the cones R + Γ 0 (f i ) coincide but are different from (R ≥0 ) n , then N(F ) = {0}.
In particular, in case k = 1 we get N(f ) = {0} for any non-convenient polynomial f . Let us remark that the set {0} appears as a component in the union of sets which occur as bound for the bifurcation set of a polynomial map B(f ) in the formula by and also in the one by Chen-Tibăr [CT].

Consider now cones σ ∈ C(F ) \ C(F ) ex and let I c σ := {1, 2, . . . , k} \ I σ . Definition 3.8. Let C(F ) aty := {σ ∈ C(F ) \ C(F ) ex | I c
σ = ∅} be called the set of atypical cones. For some ordered set J := {j 1 , . . . , j r } ⊂ {1, . . . , k}, let π J : A k → A |J| denote the projection (x 1 , . . . , x k ) → (x j 1 , . . . , x jr ). We consider the following restriction of F :

F σ := (f ∆ j σ ) j∈I c σ : G σ -→ A |I c σ | , its discriminant set Disc F σ ⊂ A |I c σ | and its inverse image A σ := π -1 I c σ (Disc F σ ) ⊂ A k .
We then define the following semi-algebraic subset of A k , of A-codimension ≥ 1:

A(F ) := ∪ σ∈C(F )aty A σ .
Remark 3.9. In case k = 1, F = f , one has the notion of "bad faces" of suppf in [START_REF] Némethi | On the bifurcation set of a polynomial function and Newton boundary[END_REF] and [CT]. Let us then remark that the "bad faces" are among the faces ∆ σ ∩ suppf for σ ∈ C(f ) aty , and that the σ ∈ C(F ) aty such that ∆ σ ∩ suppf is not a "bad face" yields A σ = ∅. Definition 3.10. We say that F depends effectively on all the variables, if for every variable z i there exists some j(i) ∈ {1, . . . , k} such that f j(i) depends effectively on z i . This condition is natural since if it is not satisfied then our polynomial map depends on less than n variables.

Proof of Theorem 1.1 and some consequences

For I ⊂ {1, . . . , n}, we define

A I := {z = (z 1 , . . . , z n ) | z i = 0, i / ∈ I}, (A * ) I := {z = (z 1 , . . . , z n ) | z i = 0 ⇐⇒ i /
∈ I} and F I := F |A I , the restriction of F on A I . The proof will be given in the mixed setting only, since the proof in the real setting follows faithfully the same pattern and only needs adapted notations.

Let c = (c 1 , . . . , c k ) ∈ K ∞ (F ) \ N(F ). We may apply the Curve Selection Lemma at infinity (see [START_REF] Némethi | On the bifurcation set of a polynomial function and Newton boundary[END_REF] and [CT]), namely there exists an analytic path z(t) = (z 1 (t), . . . , z n (t)) defined on a small enough interval ]0, ε[, such that lim t→0 z(t) = ∞, lim t→0 F (z(t), z(t)) = c and ( 7)

lim t→0 z(t) ν(dF (z(t))) = 0.
We have F : R 2n → R 2k where z j = x j + iy j , f l = g l + ih l . By the proof of [CT, Lemma 2.1] one has:

(a i + ib i ) ∂ fl ∂z j + (a i -ib i ) ∂f l ∂z j = a i ∂g l ∂x j + b i ∂h l ∂x j + i(a i ∂g l ∂y j + b i ∂h l ∂y j ),
which shows that: ν(dF

(z)) = inf k i=1 (µ i df i (z, z) + µ i df i (z, z)) , for µ i ∈ C with k i=1 |µ i | 2 = 1
. Therefore (7) yields, for any i ∈ {1, . . . , n}:

(8) lim t→0 z i (t) µ 1 (t) ∂f 1 ∂z i (z(t), z(t))+µ 1 (t) ∂f 1 ∂z i (z(t), z(t))+• • •+µ k (t) ∂f k ∂z i (z(t), z(t)) = 0,
where µ j (t) ∈ C and k j=1 |µ j (t)| 2 = 1, since the left hand side of ( 8) is less than or equal to z(t) ν(dF (z(t))) . Let L = {l ∈ {1, . . . , n} | z l (t) ≡ 0}. Observe that L = ∅ since lim t→0 z(t) = ∞, and write:

(9) z l (t) = z l t p l + h.o.t., where z l ∈ C * , p l ∈ Z, ∀l ∈ L.
Consider the expansion of F (z(t), z(t)) for all i = 1, . . . , k, we have either:

f i (z(t), z(t)) ≡ c i or (10) f i (z(t), z(t)) = c i + h.o.t..
One may assume (eventually after a change of coordinates) that L = {1, . . . , m} and p = p 1 ≤ p 2 ≤ • • • ≤ p m . Notice that, since lim t→0 z(t) = ∞, one has p = min i∈L {p i } < 0, which was an assumed condition in the definition of the set C(F ) in the preceding section. Let z 0 := (z 1 , . . . , z m , 0, . . . , 0) ∈ (C * ) L and consider the linear function l p (v) = m i=1 p i v i + n j=m+1 gv j , where p := (p 1 , . . . , p m , g, . . . , g) ∈ Z n with g ∈ N big enough. Let ∆ iL p be the maximal face of supp(f L i ) where l p restricted to supp(f L i ) takes its minimal value, which we denote by d iL p . We observe that, by definition of the vector p and by definition of

f L i , one has ∆ iL p = ∆ i p , d iL p = d i p , and consequently f L i∆ iL p = f i∆ i p (in fact, for any (v 1 , . . . , v n ) ∈ supp(f i ) \ supp(f L i ), the value of m i=1 p i v i + g n i=m+1 v i is greater than d iL p , ∀i = 1, . . . ,
f i (z(t), z(t)) = f L i (z(t), z(t)) = f L ∆ i p (z 0 , z 0 )t d i p + h.o.t.
Since lim t→0 F (z(t), z(t)) = c ∈ C k \ N(F ), one has d i p ≤ 0 for all i = 1, . . . , k. We write: (12) µ i (t) = µ i t q i + h.o.t., where µ i ∈ C * and q i ≥ 0.

If µ i ≡ 0, we put q i = ∞ in (12). Let I = i ∈ {1, . . . , k} | q i + d i p = min 1≤i≤k (q i + d i p ) . As k i=1 µ i (t) 2 = 1, we have min 1≤i≤k q i = 0. Hence I = ∅ and µ i (t) ≡ 0 for i ∈ I. We therefore conclude q i + d i p ≤ 0, ∀i ∈ I. Then (8) yields, for any l ∈ L:

(13) i∈I (µ i z l ∂f L ∆ i p ∂z l (z 0 , z 0 ) + µ i z l ∂f L ∆ i p ∂z l )(z 0 , z 0 )t q i +d i p + h.o.t. → 0.
Comparing the orders of the two sides in the above formula, we obtain, for any l ∈ L:

(14) i∈I (µ i ∂f L ∆ i p ∂z l (z 0 , z 0 ) + µ i ∂f L ∆ i p ∂z l (z 0 , z 0 )) = 0.
Let z 1 := (z 1 , . . . , z m , 1, . . . , 1). By ( 14), by the definitions of the vectors z 0 and z 1 , and by the equality f L

∆ i p = f ∆ i
p explained in the paragraph before equation ( 11), one concludes that z 1 ∈ Sing F ∆p ∩ (C * ) n . Notice that we have the equivalence: d j p < 0 ⇔ j ∈ I σ for σ ∋ p. By ( 10) and ( 11), and since d j p < 0, we must have f ∆ j p (z 1 , z 1 ) = 0. Therefore z 1 belongs to the set Sing (f

∆ j p ) k j=1 ∩ {z ∈ (C * ) n | f ∆ j p (z, z) = 0, ∀j ∈ I σ }
c i = f ∆ i σ (z 1 , z 1 ) ∈ f ∆ i σ (Sing F σ )
. This completes our proof. Remark 4.1. In [CDT] we have proved an inclusion similar to the one in Theorem 1.1 but for a different definition of non-degeneracy at infinity. The first difference is that instead of the set N(F ) above there occurs the larger set A n \ (A * ) n , and the inclusion N(F ) ⊂ A n \ (A * ) n might be strict, see Remarks 3.6 and 3.7. The second difference is between the non-degeneracy conditions. Our above definition of non-degeneracy concerns a much smaller number of faces than that in [CDT]. It yields genericity, therefore it is more natural.

Here we get however a larger number of "atypical faces" and therefore a larger set A(F ) than that obtained in [CDT]. However it is of the same nature and has the same minimal codimension one.

Another similar result, obtained recently by Nguyen in the complex setting only [Ng], appears to be weaker than the one in [CDT] since it uses an even stronger definition of non-degeneracy at infinity than [CDT].

4.1. Proof of Corollary 1.3. Since f i is convenient for every i, we have that N(F ) = ∅ (see Remark 3.7), and moreover C(F ) aty = ∅, which implies A(F ) = ∅. Then our statement follows from Theorem 1.1.

Non-degeneracy at infinity and examples

The non-degeneracy condition formulated in the real setting by Bivià-Ausina's [START_REF] Bivià-Ausina | Injectivity of real polynomial maps and Łojasiewicz exponents at infinity[END_REF]Definition 3.5] appears to be equivalent to the following: Definition 5.1. The mapping F : R n → R k is non-degenerate at infinity if the following condition is satisfied for any p = (p 1 , . . . , p n ) ∈ Z n such that p = min 1≤i≤n p i < 0:

(15)

x ∈ (R * ) n | f ∆ j p (x) = 0, for all j = 1, . . . , k = ∅. Indeed, in our constructions we have used the minimal value of the linear function l p (v) = n i=1 p i v i on supp(f i ), since we have considered analytic curves depending on t → 0, while in [Bi] the author used the maximal value of the linear function l p (v) = n i=1 p i v i on supp(f i ) since he considered analytic curves of variable t → ∞. Modulo this difference, the original definition in [Bi] coincides to the above.

Let us first prove the relations between our non-degeneracy condition and Bivià-Ausina's. Next we give several examples illustrating the fact that our definition applies to a larger class of mappings.

Proposition 5.2. Suppose that F = (f 1 , . . . , f k ) : R n → R k , k ≤ n is a polynomial mapping and that f i is convenient, for all i = 1, . . . , k. If F is non-degenerate at infinity after Bivià-Ausina's definition Definition 5.1, then it is also non-degenerate at infinity after our Definition 3.4.

This becomes an equivalence whenever k = n.

Proof. We use the notations of the previous section. Let us fix a vector p = (p 1 , . . . , p n ) ∈ Z n with p = min 1≤i≤n p i < 0. Since f i is convenient for any i = 1, . . . , k, the minimal value d i p of l p (v) must be strictly negative on supp(f i ) and therefore J σ = ∅ and I σ = {1, . . . , k} for σ ∋ p, in other words I c σ = ∅. The first conclusion of our proposition follows by comparing the condition (15) with the non-degeneracy condition Definition 3.4.

In the case n = k, let us assume that F is degenerate at infinity under Definition 5.1. Then there exists x ∈ (R * ) n and a vector p = (p 1 , . . . , p n ) ∈ Z n \ {0} with min 1≤i≤n p i < 0 such that f ∆ i p (x) = 0, for every i. This means that I c σ = ∅ and that x ∈ G σ for σ ∋ p. By the Euler relation for weighted-homogeneous functions, we have df ∆ i σ (x), px = d i p f ∆ i σ (x) = 0, for i = 1, . . . , n,where px := (p 1 x 1 , . . . , p n x n ) = 0. This implies that (df ∆p ) k i=1 (x) px = 0, which yields x ∈ Sing (df ∆p ) k i=1 . Thus F is degenerate after Definition 3.4. Together with the first statement of our Proposition, this establishes the equivalence of the two definitions in the case n = k.

The following example shows that the first implication in above proposition is not an equivalence in general.

Example 5.3. Let f : A 2 → A, f (x, y) = x 2y 2 . Then f is convenient, f is nondegenerate at infinity after Definition 3.4, but degenerate after Definition 5.1.

Let us give two types of examples where our Theorem 1.4 applies beyond the results in [Bi].

Example 5.4. Let G = (G 1 , G 2 ) : C 2 → C 2 , G(z 1 , z 2 , z 1 , z 2 ) = (z 1 + z 2 , z 1z 2 ), be a mixed polynomial mapping. Then Sing G = ∅, G is non-degenerate at infinity, and G 1 , G 2 are convenient. Hence Theorem 1.4 applies showing that G a diffeomorphism (which is already clear since G is invertible). However, if one considers the associated real mapping of G, one has G(x 1 , x 2 , y 1 , y 2 ) = (x 1 +x 2 , y 1 -y 2 , x 1 -x 2 , y 1 +y 2 ) and consequently f 1 , . . . , f 4 are not convenient and therefore Bivià-Ausina's results do not apply in this situation.

Example 5.5. Let F = (f 1 , f 2 , f 3 ) : A 3 → A 3 be a polynomial mapping defined by F (x, y, z) = (x + yz + xy 2 , y, xy + z), where A = R or A = C. None of the functions f i is convenient. However we find Sing F = ∅ and K ∞ (F ) = ∅ by direct computations, inspite the fact that N(F ) is not empty. The first part of our Theorem 1.4 applies to show that F is a diffeomorphism, whereas Bivià-Ausina's results do not apply in such a situation.

  and notice that this set is equal to Sing F σ defined in the preceding section, by the non-degeneracy Definition 3.4 and since J σ = ∅. If I c σ = ∅ then Sing F σ = ∅ by the same non-degeneracy condition, and if I c σ = ∅ then Disc F σ contributes to the set A(F ) of Definition 3.8. Indeed, whenever J σ = ∅, we have the equivalence i ∈ I c σ ⇔ d i p = 0 for σ ∋ p, and therefore

acknowledges the Brazilian grants CAPES-Proc. 2929/10-04 and FAPESP-Proc. 2008/10563-4. M. Tibăr acknowledges the support of the French Agence Nationale de la Recherche, grant ANR-08-JCJC-0118-01.


Noura Dridi

Yves Delignon

Wadih Sawaya

Christelle Garnier

EM-Based joint symbol and blur estimation for 2D barcode

Decoding a severely blurred 2D barcode can be considered as a special case of blind image restoration issue. In this paper, we propose an appropriate system model which includes the original image with the particularities related to barcode, the blur and the observed image. We develop an unsupervised algorithm that jointly estimates the blur and detects the symbols using the maximum likelihood (ML) criterion. Besides, we show that when taking into account the spatial properties of the barcode, the prohibitive complexity of the ML algorithm can be reduced without degrading its performance. Simulation results show that the algorithm performs accurate estimation of the blur and achieves good performance for symbol detection which is close to that obtained with supervised algorithm.

I. INTRODUCTION

Introduced in 1952 [START_REF] Silver | Classifying apparatus and method[END_REF], barcode is an effective means for automatic data identification and is used in many fields such as transport, mail, trade,... [?]. The success of this technology is due to the simplicity of data representation and its low cost. Originally, barcodes represent data through the width and the spacing of parallel lines, and are referred to as 1D barcodes. Binary data can also be depicted as geometric patterns such as dots or squares within images known as 2D barcodes. The latters are progressively flooding the markets of electronic tickets and the traceability of transactions. In comparison with their predecessors, 2D barcodes have a bigger capacity of information storage and a more robust code error correction. However, when the barcode acquisition is imperfect, both the bad focalisation and the camera movement give rise to blur which severely degrades the performance of the reader cf. fig 1. Therefore an algorithm for blur identification and image restoration is necessary to recover the initial transmitted information. Many algorithms [START_REF] Delignon | Estimation of generalized mixtures and its application in image segmentation[END_REF]- [START_REF] Kundur | Blind image deconvolution[END_REF] deal with blind restoration of image and depend both on estimation methods and on hypotheses aggregated in a stochastic model of the pair (hidden image, observed image). Some of them deal with interpixel interference coming from blur and are referred as blind deconvolution algorithms [START_REF] Molina | Blind deconvolution using a variational approach to parameter, image, and blur estimation[END_REF], [START_REF] Kundur | Blind image deconvolution[END_REF]. Unlike barcode case, most are concerned by a continuous hidden process modeling degraded photos for instance. On the other hand, amongst works dedicated to barcodes, let's mention the work proposed by Pavlidis et al. [?] who have published a study related to information theory fundamentals outlining the process for barcode design using error detection and correction techniques. Tsi et al. [?] have developed a method that allows the calculation of the working range in case of a CCD-based reader. Houni et al [?] have studied the performance in the framework of information theory. Furthermore, for decoding 2D barcode works mainly focus on preprocessing techniques and consist of simple threshold detectors which can't overcome significant blurs [START_REF] Xu Liu | Vcode-pervasive data transfer using video barcode[END_REF]. However, in [START_REF] Ouldbarikalla | New algorithm for 2d barcode detection[END_REF] an iterative structure based on a factor graph representation has been developed, this algorithm is suitable for strongly blurred acquisition but has the drawback of assuming the filter impulse response of the blur known. In the framework of 1D barcode technologies, we have proposed in [START_REF] Dridi | Blind detection of severely blurred 1d barcode[END_REF] a joint blur and symbol estimator that takes advantage of the cyclostationnarity of the hidden process to estimate. The extension of this algorithm to 2D barcode is the main goal of this paper. Its significant bottlenecks are the modeling of the 2D data and the induced complexity of the estimation algorithms. Then, the main contributions of the proposed work consist in: i) Modeling the observed image as a Hidden Markov Model and covering the image with a one dimensional path by preserving the Markovien property . ii) Taking into account the spatial properties of the 2D barcode, which induces a cyclo-stationary hidden Markov process iii) This cyclo-stationarity reduces significantly the cardinality of the states set, with trivial state transition probabilities into one period. iv) In consequence, a near optimal reception with low complexity based on the EM algorithm is proposed. This algorithm performs the maximum likelihood estimates of the blur and the noise power and the maximum marginal a posteriori when decoding the data symbols. The rest of the paper is organized as follows: the model of the blurred 2D barcode is presented in section 2. Section 3 describes the Expectation-Maximization algorithm used for the blur identification. The symbol detection criterion is detailed in section 4. In section 5, performances of the proposed algorithm are illustrated via simulations and compared to supervised algorithms (knowing the blur). Finally a conclusion is drawn in section 6.

Notation: : ⌊x⌋ returns the nearest integer less than or equal to x. ⌈x⌉ returns the nearest integer greater than or equal to x. x i:j = (x i , x i+1 , ..., x j )

T . x T is the classical matrix transpose.

x i,: designs the vector (x i,0 , ..., x i,L-1 ) T . The cardinal of a set Ω is denoted |Ω|. 0 L,L ′ is the zero matrix of L rows and L ′ columns. I L is the Lidentity matrix. i mod j is the reminder of the division of i by j.

II. SYSTEM MODEL Let x ′ 0,0 , ..., x ′ 0,N ′ -1 , x ′ 1,0 , ..., x ′ M ′ -1,N ′ -1 be a set of M ′ × N ′ bits to transmit. Each bit is represented by a dot of size r x × r y in a 2D barcode. So each pixel of the barcode is given by x m,n = x ′ ⌊ m rx , n ry ⌋ , (m, n) ∈ {0, ..., M -1} × {0, ..., N -1}, with M = r x M ′ and N = r y N ′ .
During acquisition, the barcode is degraded by blur coming from both the optical block and the camera movement which is modeled by a 2D finite impulse response filter of size L×L. Besides, an additive white Gaussian noise takes into account the residual stochastic imperfections of the model. In order to simplify the presentation, we assume here that the image as well as the dot are square matrices, that is r x = r y = r and M = N . Using matrix notation, the observed image Y = [y mn ] obeys to the following equation:

y m,n = H T X m,n + w m,n ∀ (m, n) ∈ {0, ..., M -1} 2 (1)
where H = h T 0,: , h T 1,: , ..., h T L-1,:

T is the impulse response vector made of rows of the 2D impulse response filter h.

Because the blur is the result of the bad focalisation and the camera motion, it belongs to the class of symmetric and concave blur [START_REF] Katsaggelos | Maximum likelihood blur identification and image restoration using the em algorithm[END_REF], [START_REF] Cannon | Blind deconvolution of spatially invariant image blurs with phase[END_REF], [START_REF] Moghaddam | A mathematical model to estimate out of focus blur[END_REF], so the problem of phase ambiguity is avoided in statistical estimation. w m,n is a white Gaussian noise with variance σ 2 .

X m,n = x T m,n:n-L+1 , x T m-1,n:n-L+1 , ..., x T m-L+1,n:n-L+1
T is the interfering pixel vector at the site (m, n). X m,n verifies the two following equations:

X m,n = BX m-1,n + V m,n (2)
X m,n = B ′ X m,n-1 + V ′ m,n (3)
with,

B = 0 L,L 2 I L 2 -L 0 L 2 -L,L , V m,n = x T m,n:n-L+1 , 0 1,L(L-1) T B ′ is a block diagonal matrix formed by L elementary matrices 0 1,L I L-1 0 L-1,1 , V ′ m,n = (x m,n , 0 1,L-1 , ..., x m-L+1,n , 0 1,L-1 )
T Equations ( 2) and (3) govern respectively vertical and horizontal path in the displayed 2D barcode. It is clear from equations

(2) and ( 3) that (X s ) s∈S , with s = (m, n) and S the designed path, is a Markov chain whose transition matrix depends on the direction of the move from a pixel to another (cf.fig 2). Any decoder based on these equations can be constructed and will keep the Markovian property. A path in the image could simply be a column by column path, row by row path and also more general path such as the Hilbert Peano one. On the other hand, when considering the barcode spatial properties (the dot resolution r > 1), (X s ) s∈S is cyclo-stationary Markov process for which the states and the transitions probabilities depend on the direction of the path and the location relative to a dot (cf.fig 2 ).

P θ (Y, X) = P (X 0 ) |S|-1 s=1 P (X s |X s-1 ) |S|-1 s=0 f Ys|Xs,θ (y s ) (4) where Y s |X s ∼ N (H T X s , σ), θ = σ 2 , H
T and P (X 0 ) is the initial probability.

States can be represented in a trellis whose intricacy conditions computation complexity. We evaluate complexity as the number of multiplicative operations needed to compute forward or backward probabilities for all states in a given position (m, n) in the the trellis. In our case this number is simply equal to number of states in the trellis. For standard application, i.e without considering the dot resolution (r = 1), detection is very hard to perform, almost impossible, due to the prohibitive complexity of the trellis which contains 2 L 2 states. However, when taking into account the resolution r > 1, the number of states is not the same for each position (m, n) and depends on the position in the dots. The complexity is then evaluated as the mean number of states among one dot. In general, if L r x and L r y , the complexity is given by

C = 1 r x r y ry j=1 rx i=1 2 (1+⌈ L-i rx ⌉) 1+⌈ L-j ry ⌉ (5)
It is clear that the complexity is reduced, for images which have the same size it is a decreasing function of r L (cf. table I). Therefore the number of paths in the trellis decreases and the detection of the optimal sequence is more robust to noise [START_REF] Dridi | Blind detection of severely blurred 1d barcode[END_REF].

III. CHANNEL ESTIMATION

Channel estimation is performed using maximum likelihood criterion which is given by :

θ = arg max θ f Y,θ (y) (6)
where f Y,θ is the likelihood of the observation. The evaluation of the likelihood is not tractable, therefore the maximum is approximated using the Expectation-Maximisation algorithm (EM) [?]. At the i th iteration, the two following steps are performed:

E step Q(θ, θ (i-1) ) = E X|Y,θ (i-1) [log(P θ (X, Y ))] M step θ (i) = arg max θ Q(θ, θ (i-1)
) For 1D detection and a resolution r = 1, X s is a stationary Markov process and the estimation algorithm of (H, σ 2 ) has been proposed by Kaleh et al [START_REF] Kaleh | Joint parameter estimation and symbol detection for linear or nonlinear unknown channels[END_REF]. The algorithm has been extended to a larger resolution in [START_REF] Dridi | Blind detection of severely blurred 1d barcode[END_REF]. For 2D detection and when considering the dot resolution r > 1, the hidden Markov process is a cyclo-stationary process whose states belong to the set ξ = {ξ 0 , ..., ξ P -1 }. At the i th iteration the channel coefficients and the noise variance estimates are respectively given by these two equations:

   |S|-1 s=0 P -1 p=0 P θ (i-1) (X s = ξ p |Y ) ξ p T ξ p    H (i) = |S|-1 s=0 P -1 p=0 P θ (i-1) (X s = ξ p |Y ) y s ξ p T (7) σ 2 (i) = 1 |S| -1 |S|-1 s=0 P -1 p=0 P θ (i-1) (X s = ξ p |Y ) × |y s -H (i) ξ p | 2 (8)
The marginal a posteriori probability P θ (i-1) (X s = ξ p |Y ) is calculated using the Forward Backward algorithm [START_REF] Bahl | Optimal decoding of linear codes for minimizing symbol error rate (corresp)[END_REF].

IV. SYMBOL DETECTION

Symbol detection is based on the maximisation of the marginal a posteriori probability (MAP). For each symbol x ′ s , it consists in choosing the value {0, 1} which maximises P θ (x ′ s |Y ). We denote {X s } the sequence which includes all vectors of interpixel interference related to the symbol x ′ s .

Let {ϑ} be a realisation of this sequence, and Ω is the set of all the realisations of {X s } .

P θ (x ′ s = 0|Y ) = {ϑ}∈Ω P θ (x ′ s = 0, {X s } = {ϑ}|Y ) = {ϑ}∈Ω P θ ({X s } = {ϑ}|Y )P θ (x ′ s = 0|Y, {X s } = {ϑ}) = {ϑ}∈Ω/x ′ s =0 P θ ({X s } = {ϑ}|Y )
The sequence {X s } = {X s 0 , ..., X s |X s |-1 }, and its realisation {ϑ} = {ϑ 0 , ..., ϑ |X s |-1 }. Since X is Markovian, then P θ ({X s } = {ϑ}|Y ) is given by:

P θ ({X s } = {ϑ}|Y ) = P θ (X s 0 = ϑ 0 |Y ) × |X s |-1 g=1 P (X s g+1 = ϑ g+1 |X s g = ϑ g , Y ) (9)
where, P (X s g+1 = ϑ g+1 |X s g = ϑ g , Y ) is obtained in the channel estimation step.

CHANNEL AND SYMBOL DETECTION ALGORITHM

From previous sections, we deduce the algorithm of joint channel estimation and symbol detection (CESD):

Algorithm 1 Channel Estimation and Symbol Detection algorithm

1: Calculate the number of states and the transition probability matrices. 2: Initialisation, H (0) , (σ 2 ) (0) .

We denote by ε a predetermined threshold

3: while | Q(θ, θ (i) ) -Q(θ, θ (i-1) ) Q(θ, θ (i-1) ) | > ε do 4:
Calculate the marginal posterior probability using the Forward Backward algorithm [START_REF] Bahl | Optimal decoding of linear codes for minimizing symbol error rate (corresp)[END_REF].

5:

Estimation of H and σ 2 from ( 7) and ( 8). 6: end while 7: Detection of symbol as described in section IV.

V. SIMULATION RESULTS

The performances of the proposed algorithm are illustrated through numerical simulations. In the following, a set of binary symbols {0, 1} have been considered and the results have been obtained with N s = 1000 Monte Carlo runs. For each run, we generate a new image of size M ×M , M = 35 with a barcode resolution r = 2 and a new channel of size L × L, L = 2. The threshold of the EM algorithm is fixed to ε = 10 -4 .

Here we propose to study the impact on symbol detection of the model described in section II, the resolution of the barcode, the estimator bias and the choice of the path in the image. Therefore we consider:

• A supervised algorithm for which θ is perfectly known, and symbol detection is made using the MAP criterion. It is called Supervised MAP ans it provides benchmark performance for unsupervised algorithms.

• Two algorithms constructed without considering the cyclo-stationary of the hidden Markov process, r is supposed to be equal to 1. Both of them are based on the MAP for the symbol detection. The first algorithm a priori knows the blur and the noise power, it is called Supervised MAP-1. Named EM-MAP-1 the second algorithm includes a channel estimator based on the EM.

• An algorithm taking into account the dot resolution, however a row by row path is considered. Each row is treated separately: symbol detection is performed as described in section IV with the difference that the marginal a posteriori probability is calculated given observation y m,: = (y m,0 , ..., y m,M-1 ) that is P θ (X g = ξ g |Y ) is replaced with P θ (X g = ξ g |y m,: ). Besides, the parameters are supposed to be known, then the algorithm is called Supervised MAP-RR.

• The CESD algorithm described in previous sections, it jointly estimates the channel and the symbols, and takes into account the spatial properties of the barcode. Besides, it used a path that recovers the whole image.

In simulations, E b /N 0 is the energy per bit to noise power spectral density ratio, with the energy per bit defined as:

E b = r 2 H T E X k X T k H (10)

Channel estimation

The Normalised Root Mean Squared Error (NRMSE), which assesses the quality of the estimation of the channel, is defined as:

N RM SE = (H -Ĥ) T (H -Ĥ) H T H
where H and Ĥ are respectively the true channel coefficients vector and the estimated one. Fig. 3 shows the performance of Fig. 4 shows the Bit Error Rate (BER) performance versus E b /N 0 . Supervised MAP and Supervised MAP-1 refer respectively to the algorithms with and without considering the dot resolution. As illustrated in Fig. 4, when taking into account that the dot resolution r is larger than 1 the BER decreases. Indeed, in this case the number of paths in the trellis is reduced so that the detection of the optimal sequence becomes more robust to noise. Moreover, the gain of performance obtained with the CESD when comparing to the supervised MAP-RR is explained by the fact that the latter is constructed without considering the dependence between rows i.e each row is treated separately. Indeed, decision on symbol x ′ m,i is based on the posterior probability using information of the row y m,: , that is P (x ′ m,i |y m,: ). In contrast with the CESD algorithm, symbol detection is based on a posteriori probability exploiting information given by the whole image P (x ′ m,i |Y ). This clearly illustrates the relevancy of considering a path that covers the whole image and takes into account the dependence between rows and columns. Finally, it is clear that the BER performance for the proposed algorithm is close to that obtained with a non blind decoder, (CESD and Supervised MAP).

VI. CONCLUSION

In this paper, we have proposed a joint channel and symbol blind estimator for severely degraded 2D barcode. The algorithm takes advantage of both the spatial properties of the 2D barcode and the Markovian property of the interfering pixel vectors. We have shown that these properties enable the calculation of the maximum likelihood of the blur, the noise power and the symbols. They also reduce the complexity of the algorithm. Simulations assess the efficiency of the algorithm and, in particular, they point out the gain obtained by taking into account the spatial properties of the 2D barcode. Besides, results attest the impact of taking into account the dependency between rows and columns in the image. Finally, performances of the proposed unsupervised algorithm are close to those obtained by a supervised one, which illustrates the precision of parameter estimation.

Fig. 1 .

 1 Fig. 1. (a):Original image (b): Blurred image

Fig. 2 .

 2 Fig. 2. A path in a displayed 2D barcode

Fig. 3 .

 3 Fig. 3. NRMSE vs E b /N 0the estimation of the channel impulse response in term of the NRMSE, with and without considering the dot resolution. The difference between curves is explained by the fact that when taking into account the original image structure, the quality of the estimation of the marginal a posteriori probability P θ (i-1) (X s = ξ p |Y ) is improved, which directly improves the estimation of the channel H (cf. equation 7).

Fig. 4 .

 4 Fig. 4. BER performance


Noura Dridi

Yves Delignon

Wadih Sawaya

Franc ¸ois Septier

D Barcode Blind Detection in Severe Environment

In this paper, we present a joint blind channel estimation and symbol detection for decoding a blurred and noisy 1D barcode captured image. From an information transmission point of view, we show that the channel impulse response, the noise power and the symbols can be efficiently estimated by taking into account the signal structure such as the cyclostationary property of the hidden Markov process to estimate. Based on the Expectation-Maximisation method, we show that the new algorithm offers significative performance gain compared to classical ones pushing back the frontiers of the barcode technology.

I. INTRODUCTION

Barcode is an essential element of electronic data interchange. Since its birth in 1948, this technology is continuously growing up. Its success comes from the simplicity of the binary data representation and the efficiency of the reading device in a controlled acquisition environment. Originally, barcodes represent data through the width and the spacing of parallel lines, and may be referred to as 1D barcodes. Binary data can also be depicted in geometric patterns such as dots or squares within images known as 2D barcodes. When shooted, the original barcode is degraded by blur caused by a bad focalisation and/or a camera movement, in addition to noise, the whole resulting in a blurred noisy received signal, Fig. 1. In fact, two main types of blur can affect the received signal; the optical blur owing to bad focus and diffraction phenomena and the motion blur coming from the camera mobility with respect to the barcode. Many models have been proposed for these two kinds of blur such as parametric models [START_REF] Moghaddam | A mathematical model to estimate out of focus blur[END_REF], Gaussian models [START_REF] Chen | An empirical identification method of gaussian blur parameter for image deblurring[END_REF] and models based on the global transfer function [START_REF] Cannon | Blind deconvolution of spatially invariant image blurs with phase[END_REF] and [START_REF] Grennery | Determination of optical transfer function by inspection of frequency-domain plot[END_REF]. In the scientific literature few works are related to 1D and 2D barcode coding. Pavlidis et al. [START_REF] Pavlidis | Fundamentals of barcode information theory[END_REF] have published a study related to information theory fundamentals outlining the process for barcode design using error detection and correction techniques. Tsi et al. [START_REF] Tsi | System analysis of ccd-based bar code readers[END_REF] have developed a method that allows the calculation of the working range in case of a CCDbased reader. Houni et al [START_REF] Houni | One-dimensional barcode reading : an information theoretic approach[END_REF] have studied the performance in the framework of the information theory and they have proposed two new measures: the theoretical depth of field and the theoretical resolution. In [START_REF] Muniz | A robust software barcode reader using the hough transform[END_REF], a method of reading linear barcodes using the Hough transform is proposed. The algorithm is designed to a particular type of barcode (Code39). Recently Ould Barikalla et al [START_REF] Ouldbarikalla | New algorithm for 2d barcode detection[END_REF] have proposed a 2D barcode decoder using an iterative structure based on a factor graph representation. In all these works, decoders take into account the prior knowledge of the channel at the receiver. In practice, a training sequence enables the channel to be estimated but the estimation error leads to performance degradation of the decoder. In this paper, we consider the decoding problem of barcode without training sequence. In particular, we propose a blind decoder that jointly estimates the channel and the symbols. This joint channel estimation and symbol detection can be performed, using probabilistic algorithm based on maximum likelihood criterion [START_REF] ¸ois Septier | Blind channel estimation and data detection using hidden markov models[END_REF], [START_REF] Feder | Algorithms for joint channel estimation and data recovery-application to equalization in underwater communications[END_REF], [START_REF] Fonollosa | Application of hidden markov models to blind channel characterization and data detection[END_REF] and [START_REF] Kaleh | Joint parameter estimation and symbol detection for linear or nonlinear unknown channels[END_REF]. Here, we show that the channel state of a barcode is a cyclostationary process and we propose a new joint channel estimator and symbol detector based on the Expectation Maximisation algorithm which takes advantage of this property. By exploiting the cyclostationarity property, the number of paths of the channel state in the lattice diagram is reduced. As a consequence, the detector is more robust to noise and the detector performances are significantly improved. The paper is organised as follow. In Section 2, both the barcode and the channel are modeled respectively, by a cyclostationary process and by a finite impulse response filter with an additive white Gaussian noise. Section 3 describes the Expectation -Maximisation algorithm used for the channel estimation. Section 4 is focused on the symbol detection. Section 5 presents the results of a simulation study that has been conducted to assess the new algorithm's performance. Conclusions are given in Section 6.

Fig. 1: Original and blurred barcode Notation ⌊x⌋ returns the smallest integer value greater than or equal to x. x(i : j) = (x i , x i+1 , ..., x j ). x T is the classical matrix transpose.

II. SYSTEM MODEL

Let x ′ 0 , x ′ 1 ..., x ′ N -1 be a sequence of N bits to transmit. Each bit is represented by a bar of width r x . So the barcode is given by

x k = x ′ ⌊ k rx ⌋ , k ∈ {0, ..., K -1} with K = N r x .
When shooted, the barcode is degraded by a blur coming from both the optical block and the movement of the camera which are modeled by a finite impulse response filter of length L. Besides, an additive white Gaussian noise takes into account the residual stochastic imperfections. Using matrix notation, the observed sequence Y = (y 0 ...y K-1 )

T is given by:

y k = H T X k + w k ∀k ∈ {0, ..., K -1} (1)
where H = (h 0 ...h L-1 ) T is the channel coefficients vector, H is symmetric and decreasing from central maximum. Indeed, the blur is the result of the bad focalisation and the camera motion, which belongs to the class of this symmetric blur [START_REF] Cannon | Blind deconvolution of spatially invariant image blurs with phase[END_REF], [START_REF] Chen | An empirical identification method of gaussian blur parameter for image deblurring[END_REF], [START_REF] Moghaddam | A mathematical model to estimate out of focus blur[END_REF] and [START_REF] Grennery | Determination of optical transfer function by inspection of frequency-domain plot[END_REF].

X k = (x k ...x k-L+1
) T is the displayed symbol vector and w k is an additive white Gaussien noise with variance σ 2 . X k verifies the equation :

X k = BX k-1 + V k (2) With B =    0 0 ••• 0 1 . . . . . . . . . . . . 0 0 ••• 1 0    and V k = (x k 0...0) T .
From (2), we deduce that X k is a Markovian process which belongs to a set ξ 0,rx , ..., ξ M-1,rx in which the cardinal number M and the states are relied to both the channel length L and the bar width r x . Specifically, the number of states M follows the equation :

M =    2L if L ≤ r x rx-1 i=0
2 (1+⌊(L-1)/rx⌋) -2 (r x -1) otherwise

(3) Let's point out from equation (3) that M is decreasing with r x which is an interesting property when dealing with the recovery of the information carried by the barcode. The distance between the various states becomes larger so that detection is less sensitive to the noise. By denoting A k = (a mn (k)) 0≤m,n≤M-1 , the transition matrix of X k is given by :

a mn (k) = P (X k = ξ n,rx |X k-1 = ξ m,rx ) (4) = 1 2 δ (ξ n,rx (1 : L -1) -ξ m,rx (0 : L -2)) if k -1 rx ∈ N δ (ξ n,rx (1 : L -1) -ξ m,rx (0 : L -2)) otherwise
with δ (.) the Kronecker symbol. As shown in equation ( 4), if X k is at the border of the bar, two transitions are possible, otherwise only one transition is allowed.

From equation ( 1) and the Markovian properties of X = (X 0 ...X K-1 ), we deduce the distribution of (X, Y ):

P θ (Y, X) = P (X 0 ) K-1 k=1 P (X k |X k-1 ) K-1 k=0 f Y k |X k ,θ (y k ) (5)
where

f Y k |X k ,θ (y k ) = 1 √ 2πσ 2 exp - 1 2 y k -H T X k σ 2 , P (X k |X k-1
) is given by equation ( 4) and θ = H, σ 2 , r x T is the parameter vector of the model. From the described model, X k can be represented in a trellis diagram. Since the Markov process is cyclostationary, the lattice is cyclic so that the number of paths is reduced. As a consequence, the detection of the optimal sequence is simplified and more robust to noise.

III. PARAMETER ESTIMATION

A. EM algorithm

The maximum likelihood of θ is given by :

θ = arg max θ f Y,θ (y) (6)
where f Y,θ is the likelihood of the observation. Nevertheless in our application the likelihood maximisation is not tractable. On the other hand, when considering the complete data (X, Y ), the maximum likelihood estimation can be closely approximated by the Expectation-Maximisation algorithm (EM). This recursive algorithm consists of an iterative maximization of the auxilliary function Q(θ, θ (i-1) ).

At the i eme iteration, the two following steps are performed: E step

Q(θ, θ (i-1) ) = E X|Y,θ (i-1) [log(P θ (X, Y ))] (7)
M step

θ (i) = arg max θ Q(θ, θ (i-1) ) (8)
In order to proceed to the estimation of the three components of θ, Q is first maximised with regards to H, σ 2 and the result is maximised relatively to the width r x .

max θ Q θ, θ (i-1) = max rx max H,σ 2 Q θ, θ (i-1) (9)
When considering the special case where the width r x = 1, X k is a stationary Markov process and the estimation algorithm of (H, σ 2 ) has been proposed by Kaleh et al. [START_REF] Kaleh | Joint parameter estimation and symbol detection for linear or nonlinear unknown channels[END_REF]. In general case, i.e. whatever the value of r x , we show that the channel coefficients and the noise variance estimates are respectively given by these two equations:

K-1 k=0 M-1 m=0 P θ (i) (X k = ξ m,rx |Y ) ξ m,r T x ξ m,rx H (i+1) rx = K-1 k=0 M-1 m=0 P θ (i) (X k = ξ m,rx |Y ) y k ξ m,r T x ( 10
)
and

σ 2 (i+1) rx = 1 K K-1 k=0 M m=0 P θ (i) (X k = ξ m,rx |Y ) × |y k -H (i+1) rx ξ m,rx | 2 (11)
where P θ (i) (X k = ξ m,rx |Y ) is obtained by the forward backward algorithm [START_REF] Bahl | Optimal decoding of linear codes for minimizing symbol error rate (corresp)[END_REF]. We propose to consider the estimation of the width r x as well as the estimation of the channel impulse response. Moreover, the cyclostationarity of X k is exploited to optimise the accuracy of the estimates.

B. Joint estimation of H and σ 2 given r x For a given r x , the estimates of H rx and σ 2 rx are obtained by solving the equations ( 10) and [START_REF] Muniz | A robust software barcode reader using the hough transform[END_REF], where the marginal posterior probability P θ (i) (X k = ξ m,rx |Y ) is recursively calculated by the forward backward algorithm adapted to the cyclostationarity of the hidden process X k . When r x > 1, the algorithm chooses the optimal sequence in a reduced set of paths in the lattice diagram, since some transitions are not possible. Let us note

γ m (k) = P θ (X k = ξ m,rx |Y ) (12) ∀m ∈ {0, • • • , M -1} ∀k ∈ {0, • • • , K -1}
, the marginal posterior distribution of X k . One shows that :

γ m (k) = α m (k) β m (k) M-1 n=0 α n (k) β n (k) (13)
where α n (k) and β n (k) are respectively the forward and the backward probabilities defined as follow :

α m (k) = P θ (Y 1 = y 0 , ..., Y k = y k , X k = ξ m,rx ) (14)
β m (k) = P θ (Y k+1 = y k+1 , ..., Y K-1 = y K-1 |X k = ξ m,rx ) (15
) These probabilities can be calculated recursively by :

α m (k + 1) = [ M-1 n=0 α n (k)a nm (k)]f m (y k+1 ) (16)
β m (k) = M-1 n=0 β n (k + 1)a mn (k) f n (y k+1 ) (17)
where 1), the Gaussian density with mean ξ n,rx and variance σ 2 is deduced. • a mn (k) is the transition probability (4). The initialisation step of the forward and the backward algorithm are:

• f n (y k ) is the density probability function of Y given X k = ξ n,rx . From equation (
α m (1) = π m f m (y 0 ) and β m (K) = 1, ∀m ∈ {0, • • • , M -1} C. Estimation of r x r x is estimated using the maximum likelihood criterion rx = arg max rx g(H rx , σ 2 rx , r x ) ( 18
)
with g is the pesudo likelihood

g(H rx , σ 2 rx , r x ) = max H,σ 2 Q θ, θ (i-1) (19)
H rx and σ 2 rx are the estimates obtained using equations (10) and [START_REF] Muniz | A robust software barcode reader using the hough transform[END_REF]. Maximisation of g with regard to r x is equivalent to maximisation of the likelihood. Since, explicit expression of the estimator rx can not be identified, g is calculated for all possible value of r x ∈ {1, ..., K -1}. Next, we choose ( Ĥrx , σ2 rx , rx ) that gives the highest likelihood.

IV. SYMBOL DETECTION

The optimal decision on symbol is obtained using the Marginalised Posterior Mode (MPM) criterion, which is based on the maximisation of the marginal posterior probability. For symbol x ′ k from the transmitted sequence of length N , the decision is taken by:

P θ (x ′ k = 0|Y ) x′ k =1 ≶ x′ k =0 P θ (x ′ k = 1|Y ) (20)
Let Ω j be the set of realisations ξ = ξ 0 , ..., ξ rx-1 of X krx:(k+1)rx-1 such as x ′ k = j. Since, there is a one to one relation between x ′ k and X krx:(k+1)rx-1

P θ (x ′ k = j|Y ) = P θ (X krx:(k+1)rx-1 ∈ Ω j |Y ) (21)
With,

P θ (X krx:(k+1)rx-1 ∈ Ω j |Y ) = ξ∈Ω j P θ X k = ξ 0 |Y × l=rx-1 l=1 P (X k+l = ξ l+1 |X k+l-1 = ξ l ) (22)
Where, P θ X k = ξ 0 Y ) is obtained by the forward backward algorithm (III-B) and the transition probabilities are given by equation ( 4). This criterion takes into account the structure of the barcode signal, via the marginal probability and the transition probability matrix. Calculate the number of state and the transition probability matrix using equations ( 3) and (4).

V. JOINT CHANNEL AND RESOLUTION

3:

Initialisation, H (0) , (σ 2 ) (0) . We denote by ε a predetermined threshold 4:

while |H k rx -H k+1 rx | > ε do 5:
Calculate the marginal posterior probability using equations ( 16), ( 17) and ( 13).

6:

Estimation of Hr x and σ 2 rx from ( 10) and [START_REF] Muniz | A robust software barcode reader using the hough transform[END_REF].

7:

end while 8:

Given Hr x and σ 2 rx , calculate the pseudo likelihood using equation (19). 9: end for 10: Select the parameter θ = Ĥrx, σ2 rx , rx that maximises the pseudo likelihood (19). 11: Detection of symbol using equations (20), ( 21) and (22).

VI. SIMULATIONS RESULTS

In this section, the performance of the proposed algorithm is illustrated through numerical simulations. 2 shows the observed signal degraded by blur and noise distortion versus the initial transmitted signal. It confirms that the received signal can not be directly decoded. Indeed, a joint blur identification and symbol detection algorithm is required to efficiently recover the original signal. In the following, a set of binary symbol {0, 1} have been considered and the results have been obtained with N s = 1000 Monte Carlo runs. For each run, a new sequence of length N = 100 has been generated with a barcode resolution barcode r x = 3 and a new simulated channel of length L = 3, the treshold ε = 10 -5 . To analyse the performances of the proposed algorithm, we consider three cases:

• The Kaleh's algorithm [START_REF] Kaleh | Joint parameter estimation and symbol detection for linear or nonlinear unknown channels[END_REF], constructed without exploiting the cyclostationarity of the hidden Markov process.

• The CRESD algorithm, described in Algorithm1.

• A simple algorithm which does not take into account the channel model ( 1), but assumes known the resolution. The decision rule is:

  1 r x (k+1)rx i=krx y i   x′ k =0 ≶ x′ k =1 1 2 (23)
∀k ∈ {0, ..., N -1} In the experiments, E b /N 0 is the energy per bit to noise power spectral density ratio, with energy per bit defined as:

E b = r x H T E X k X T k H (24)
Estimation of the resolution r x to r x /L, is reduced when r x /L > 1. Obviously, for the same value of E b /N 0 , estimation performance is better for r x /L > 1.

Channel estimation

The Root Mean Squared Error (RMSE), assessing the quality of the estimation of the channel, is defined as:

RM SE = (H -Ĥ) T (H -Ĥ) H T H
With H and Ĥ are respectively the true channel coefficients vector and the estimated one. Fig. 3 shows the superiority of CRESD algorithm, in term of RMSE. This clearly illustrates the benefit of exploiting the cyclostationarity of the hidden Markov process in the trellis diagram. This leads to a more accurate estimation of the marginal posterior probability, which directly impacts the channel estimation equation [START_REF] Moghaddam | A mathematical model to estimate out of focus blur[END_REF]. Besides, when the barcode resolution r x is estimated, the RMSE is larger for E b /N 0 < 4dB, but becomes identical to the one when r x is known for

E b /N 0 ≥ 4dB.
For the estimation of the noise variance, we note the same behavior. The RM SE = 6.7710 -2 for the CRESD algorithm and it is equal to the double for the Kaleh's one RM SE = 13.0510 -2 , for E b /N 0 = 5dB. Indeed, as channel coefficients, the estimation of the noise variance depends on the marginal posterior probability equation( 11) which takes into account the true sequence structure of the barcode. Now, the rapidity of convergence of the estimation is assessed. Fig. 4 shows that the CRESD is both more accurate and faster than the Kaleh's one. In this exemple,the convergence has been achieved at the 4 th iteration, while the Kaleh's algorithm requires twice as much iterations. 5 illustrates Bit Error Rate (BER) performance, curves with solid and dashed line correspond respectively to the CRESD algorithm and Kaleh's method. When r x is known, we note that BER performance is significantly improved using CRESD algorithm, and this performance gain increases with E b /N 0 . This result is explained by the fact that, with the CRESD algorithm, decision is taken in a trellis diagram constructed with respect of the original signal structure. When r x is estimated, the resolution and channel estimation error lead to an increase of the BER for E b /N 0 < 4dB for the CRESD algorithm. For the Kaleh's one, r x is supposed to be known. Nevertheless, the CRESD algorithm still performs better for E b /N 0 > 4dB, and the estimation of r x does not really degrades the overall performance. For E b /N 0 > 4dB, the curve obtained with and without estimation of r x are the same. On the other hand, the poor performances of the method based on the decision without channel estimation confirms the need of a more accurate algorithm to ensure correct reconstruction of the original signal.

VII. CONCLUSION

In this paper, we have proposed a blind channel estimation and symbol detection algorithm. Blur identification has been performed using the EM algorithm. Besides, given that the received signal is modeled as a hidden Markov chain, a version of the forward-backward algorithm, suitable to the cyclostationarity of the Markov process, has been proposed to estimate the marginal posterior probability. We have shown that, when the barcode structure is taken into account in the lattice, the estimation of the marginal posterior probability is easier and more accurate. This advantage directly impacts both the channel estimation and the symbol detection. Simulation results show a fast convergence, a large gain for the parameter estimation and a smaller symbol error rate compared to existing approaches. As a consequence, the CRESD algorithm can be efficiently used with larger intersymbol interference, thus enabling to read more compact barcode and to allow higher mobility between the barcode and the camera.

Algorithm 1

 1 ESTIMATION ALGORITHM From, subsections (III-A), (III-B), (III-C) and (IV), we deduce the algorithm to joint channel and barcode resolution estimation and symbol detection (CRESD): Joint channel and resolution estimation and symbol detection algorithm 1: for rx = 1, . . . , K -1 do 2:

Fig. 2 :

 2 Fig. 2: Blurred signal with blur length L=10, r x = 3 and N = 100

Fig.

  Fig.2shows the observed signal degraded by blur and noise distortion versus the initial transmitted signal. It confirms that the received signal can not be directly decoded. Indeed, a joint blur identification and symbol detection algorithm is required to efficiently recover the original signal. In the following, a set of binary symbol {0, 1} have been considered and the results have been obtained with N s = 1000 Monte Carlo runs. For each run, a new sequence of length N = 100 has been generated with a barcode resolution barcode r x = 3 and a new simulated channel of length L = 3, the treshold ε = 10 -5 . To analyse the performances of the proposed algorithm, we consider three cases:

Fig. 3 :

 3 Fig. 3: RMSE vs E b /N 0 , for N=100, L=3 and r x = 3

Fig. 4 :Fig. 5 :

 45 Fig. 4: Evolution of the RMSE with iterations, with L = 3, r x = 3 and N = 100

Table ( I

 ( ) illustrates the performance of estimation of r x . We calculate for different value of r x the error rate defined as ρ = n b N s , where n b is the number of false detection and N s the number of trials. As shown in Table (I) the error rate decreases rapidly, with E b /N 0 . In fact, the error rate is due to noise distortion and interference intersymbol. The later, related

	E b P P P P P P P rx N 0	2dB	4dB	6dB	8dB	10dB
	rx=2	0.218	0.032	0.008	0.002	0.001
	rx=3	0.169	0.019	0.002	0.001	0
	rx=4	0.083	0.005	0	0	0
	rx=5	0.057	0.006	0	0	0

TABLE I :

 I r x error rate for channel length L = 3 and block length N = 100