Jun Xu
email: ajun.xu@hochschule-rhein-waal.de

Christophe Cudel
email: bchristophe.cudel@uha.fr

Sophie Kohler
email: csophie.kohler@uha.frd

Stephane Fontaine
email: stephane.fontaine@u-bourgogne.fre

Oliver Haeberle
email: olivier.haeberle@uha.fr

Marie-Louise Klotz
email: fmarie-louise.klotz@hochschule-rhein-waal.de

A New Method to Measure 3D Textile Defects by Using Dual-lens Camera

Keywords: textile defect, homography, stereovision, computer vision, glass fiber fabric, nonwoven

. In a previous work [2], we have proposed an original method to measure the height of the fiber based on variable homography. This measurement is based on a single camera acquiring two successive frames. This scheme is working well, but measurement depends on conveyor speed used for scrolling fabric. In this paper, we propose an improvement by using a new acquisition device based on two mini-lenses assembled as a dual-objective. With this device, variable homography modeling leads to 3-D online inspection whatever fabric speed with a simplified calibration procedure compared to classic stereovision approaches.

Introduction

Variable homography has been introduced by Zhang and Greenspan [START_REF] Zhang | Variable Homography Compensation of Parallax Along Mosaic Seams[END_REF] to improve image mosaicking, in order to overcome parallax between objects located at different depths. We have extended the concept of variable homography [START_REF] Xu | Original method to compute epipoles using variable homography: application to measure emergent fibers on textile fabrics[END_REF][START_REF] Xu | Textile emergent fibers length measurement system based on camera vision and variable homography[END_REF] for 3-D measurements. We have applied this model to measure emergent fibers on glass and non-woven fabrics, and we have validated the interest of this method. Even if uncertainty of measurement is lower than 10%, measurement quality would depend on the conveyor speed. To avoid being dependent of this speed, we have modified the acquisition setup by using two mini-lenses assembled in one camera. The idea is to obtain two projected images on a single CCD sensor. There are some advantages to model this tiny stereovision system with variable homography instead of simple triangulation as done most of time. Each projection system has its own intrinsic parameters, which are easy to integrate with variable homography modeling and calibration stage is simplified. Experimental results prove uncertainty of measurement to be lower than 5% on emergent fibers having a diameter of 100 µm and being 1 to 5 mm long. At this scale, this dual-lens setup fills the gap range between microscopy (µm-mm) and 3-D vision (cm-m) to perform 3-D measurements online.

Variable Homography

Fig. 1(a) give a representation of our system made out of 2 mini-lenses and a single image plane. This scheme corresponds to a parallel stereovision system, and a simple triangulation permits to compute Z B . Z B is then formulated with the p LB (u LB , v LB ) and p RB (u RB , v RB ) coordinates, the lens focal f and distance b x between lens optical centers:

= . ( ⁄ -) (1)
This relation works well if camera centers and focals are identical for both projections. In experimental conditions these intrinsic parameters are never strictly identical. Eq. ( 1) can be adapted to take them into account, but at this scale of measurement, a manual unfriendly calibration is necessary for their determination. Variable homography could be an alternate to simplify the calibration step.

Principle of Variable Homography

When two points have same X and Y coordinates, as points P A (X A ,Y A ,Z A ) and P B (X B ,Y B ,Z B ) on Fig. 1(a), the first result of variable homography gives a relation between their projections p LA and p LB onto the image plane:

= � 1 � = � 0 (1 -) 0 0 (1 -) 0 0 0 1 � � 1 � = .
(

) 2
where k=Z A /Z B and (u 0 , v 0 ) are the coordinates of focal point projection on image plane. By adding a second camera [START_REF] Zhang | Variable Homography Compensation of Parallax Along Mosaic Seams[END_REF], one can define homographies H A and H B , linking image projections of points contained within planes A and B, respectively:

= � 1 � = � 1 � = . = � 1 � = � 1 � = .
(

) 3
We consider plane A as a reference plane. If plane B is parallel to plane A and located at a variable height, the corresponding homography, noted H B (k), can be deduced from H A and K:

() = . . -1 (4)

Measurement Principle

For any emergent fiber having an intersection with the virtual plane B, we propose to measure the height of plane B through the horizontal distance between the projections p' RA and p RB . From Eq. ( 4) and analytic expression of homography H A [START_REF] Xu | Using variable homography to measure protruding fibers on textile fabrics[END_REF], this distance is given by:

() = ′ -= ( -1). . = ( -1).
(

) 5
where b x is the distance between the focal points and f the lens focal distance. During a measurement, d u (k) is proportional to (k-1), and plane B height, i.e. fiber height, is calculated with:

ℎ = -= - = () () + (6)
The measurement process can be resumed in four steps, as illustrated on Fig. 2: - This height measurement is depending on H A , C u and Z A . These three parameters can be determined by a simple calibration described in section Calibration.

Figure 2. Measurement process in four steps

Calibration

We propose a simple, two-step calibration process realized through chessboard acquisitions. The first acquisition is performed at the reference height Z A . The second one is done by elevating the pattern by dz. This second acquisition is then performed at height Z B =Z A -dz: k is therefore known. Step 1

Step 2

Step 3

Step 4

Left image Right image 1 st acquisition: H A Chessboard corners are detected on both images and are used to calculate homography H A . We note d A the distance in pixels between the top-left and bottom-right corners.

nd acquisition: Z A and C u

The second set of chessboard corners is detected. We note d B the distance in pixels between the top-left and bottom-right corners. Z A is obtained by triangulation and can be formulated as:

= . - (7)
This second acquisition is also used to estimate the constant C u . Corners detected on both images constitute a dataset of p LB and p RB points. By using H A computed at the previous step, the correspondences p' RA are then computed and C u is calculated from Eq. ( 5). This calibration method is well adapted for 3-D online measurement. Compared to a calibration process used to determine intrinsic parameters [START_REF] Zhang | A flexible new technique for camera calibration[END_REF], our method is easier to perform and can be executed without difficulty by an operator.

Experimental Results

In this part, we first evaluate the accuracy of our method and then present some results on textile fabrics.

Measurement performance

To evaluate performance and accuracy, we use as reference pattern a pyramidal object with five levels, each separated by 1 mm. Fig. 4 presents a typical measurement for each step when matching between p LB and p RB points is precise.

On this example, measurement error is below 1%. We must be careful with this excellent result because accuracy is strongly dependent of the matching process. With this pyramidal object and by using calibration parameters, it's possible to determine theoretical position of each correspondence by fixing k at Z A /(Z A -h), according to the selected level. On Fig. 5a, we have zoomed on two selected points in left image and located respectively at 3 and 4 mm elevation. Fig. 5b shows the corresponding right image, where the theoretical matching positions are represented with red crosses and selected positions for measurements with blue ones. At 3 mm level position, red and blue crosses are close and measurement based on the blue point gives a height of 3.08 mm. At 4 mm, we have forced a shifting of more than 3 pixels between theoretical position and measurement position. In this case the measured height is 3.56 mm instead of 4 mm. This example shows the importance of the correspondence matching process. With calibration parameters values, we can evaluate the influence of matching process. The uncertainty measurement is essentially function of d u (k) and can then be formulated from Eq. ( 6):

ℎ ( ()) = . ( () + ) 2 (8)
On this example, the calibration process gives Z A =3.81 cm and C u = -234 pixels. The uncertainty measurement on h is then 0.16 mm per pixel. Therefore, following the nature of the samples to be measured, the matching method must be adapted. By using sub-pixel matching algorithms ensuring a matching of ± 0.25 pixel, the uncertainty measurement is lower than ±0.04 mm or 4 % for a 1 mm height fiber.

Measurements on Textile Fabrics

This part presents some results obtained on textile fabrics to evaluate the height of emergent fibers. We use a laser line illumination to ensure good correspondences. This illumination skims the fabric surface. Interest for this application is to only highlight emergent fibers. From bright spots on left images, correspondences are searched in right images along the line (so-called epipolar line [START_REF] Xu | Original method to compute epipoles using variable homography: application to measure emergent fibers on textile fabrics[END_REF]) describing the theoretical positions for various k values (depicted as yellow lines visible on Fig. 5b).

It is then possible to select a set of points on the emergent fiber, and then compute its corresponding 3-D profile. Fig. 6 gives a first result on an analysis surface sizing approximately 4 cm 2 . This measurement is done on a glass fabric presenting a broken fiber. Fiber stands straight, which leads to the computed profile on the zoomed region. Other typical examples on glass and non-woven fabrics are presented on Fig. 7.

Conclusion

This work proposes an original 3-D measurement approach to inspect glass and non-woven fabrics.

Variable homography modeling allows for a simplified calibration process, which can easily be executed by an operator. The measurement principle has been validated on a reference pyramidal object. In our experimental acquisition conditions, we estimate the uncertainty measurement to stay below 5%. This method can be extended to other applications, the matching method being to be adapted to the characteristics of the images. At this scale, most of measurement processes need to sample part of glass fabric and realize offline measurements with a laboratory equipment. Our device with two associated mini-lenses and with this original measurement method should be able to work online in an industrial environment, and could be extended to a complete online 3-D surface fabric reconstruction.

Figure 1 .

 1 Figure 1. (a) configuration of dual-lens device ,views of experimental prototype. (b) the dual-lens device; (c) image acquisition of a glass fiber fabric

  Step 1 (left image): detection of point belonging to a fiber, noted p LB ; -Step 2: computation of p RA according: p' RA =H A .p LB ; -Step 3 (right image): detection of corresponding p LB point belonging to the fiber, noted p RB ; -Step 4: computation of h from d u .

Figure 3 .

 3 Figure 3. Calibration in two steps: reference plane acquisition (plane A); acquisition at height Z B

Figure 4 .Figure 5 .

 45 Figure 4. Measurements on a reference pyramidal object

Figure 6 .Figure 7 .

 67 Figure 6. Measurements of emergent glass fabric fibers


Dávid Hudák

František Kardoš

Borut Lužar

Roman Soták

Riste Škrekovski

Acyclic edge coloring of planar graphs with ∆ colors

Keywords: Acyclic edge coloring, Planar graph, Discharging method

. In this paper, we study simple planar graphs which need only ∆(G) colors for an acyclic edge coloring. We show that a planar graph with girth g and maximum degree ∆ admits such acyclic edge coloring if g ≥ 12, or g ≥ 8 and ∆ ≥ 4, or g ≥ 7 and ∆ ≥ 5, or g ≥ 6 and ∆ ≥ 6, or g ≥ 5 and ∆ ≥ 10. Our results improve some previously known bounds.

Introduction

An acyclic edge coloring of a graph G is a proper edge coloring with an additional condition that any pair of colors induces a linear forest (an acyclic graph with maximum degree two); in other words, there are no bichromatic cycles in G. The least number χ ′ a (G) of colors for which G admits an acyclic edge coloring is called acyclic chromatic index. Since graphs with parallel edges do not admit acyclic edge colorings, in this paper we consider only simple graphs.

The acyclic coloring was first introduced for vertices of graphs by Grünbaum [START_REF] Grünbaum | Acyclic coloring of planar graphs[END_REF] and has been later extended to edges. Since acyclic edge coloring is also proper, we have the inequality χ(G) ′ ≤ χ ′ a (G) for every graph G. It is well known that the chromatic index of graphs is at least ∆(G) and at most ∆(G) + 1, what was proved by Vizing [START_REF] Vizing | Critical graphs with a given chromatic number[END_REF]. For an acyclic chromatic index a similar bound is believed to be true.

Conjecture 1 ([6, 1]). For every graph G it holds that

∆(G) ≤ χ ′ a ≤ ∆(G) + 2 .
An analysis of cycles in graphs is a hard task, thus it is not surprising that the best known upper bound for an acyclic chromatic index is 16∆(G), which has been proved by Molloy and Reed [START_REF] Molloy | Further algorithmic aspects of the local lemma[END_REF]. However, Conjecture 1 has been verified for several classes of graphs. The first result is due to Burnstein [START_REF] Burnstein | Every 4-valent graph has an acyclic five-coloring[END_REF], who proved that every graph with maximum degree 4 has an acyclic vertex coloring with 5 colors. Since the maximum degree of a line graph L(G) of a subcubic graph G is at most 4, and since an acyclic edge coloring of a graph G is in fact an acyclic vertex coloring of L(G), it follows that for every subcubic graph G, we have χ ′ a (G) ≤ 5 = ∆ + 2. Note that χ ′ a (G) ≤ 3 if ∆(G) = 2. Furthermore, in [START_REF] Alon | Acyclic edge colorings of graphs[END_REF] Conjecture 1 has been proved for almost all d-regular graphs and for all d-regular graphs with girth at least c∆(G) log ∆(G), where c is a constant. Recently, Basavaraju and Chandran [START_REF] Basavaraju | A note on acyclic edge coloring of complete bipartite graphs[END_REF] proved that the conjecture also holds for complete bipartite graphs K p,p , where p is an odd prime.

Since 2008, the acyclic edge coloring of planar graphs has received a lot of attention. Fiedorowicz, Ha luszczak, and Narayanan [START_REF] Fiedorowicz | About acyclic edge colourings of planar graphs[END_REF] proved that χ ′ a (G) ≤ 2∆(G) + 29 for every planar graph G, and if the girth of G is at least 4, the bound reduces to ∆ + 6. In the same year, Sun and Wu [START_REF] Sun | Acyclic edge colorings of planar graphs without short cycles[END_REF] verified Conjecture 1 for planar graphs without k-cycles, where k ∈ {4, 5, 6, 7, 8}, and planar graphs without 4-and 5-cycles in which no two 3-cycles share a vertex. In 2009, Hou et al. [START_REF] Hou | Acyclic edge colorings of planar graphs and series-parallel graphs[END_REF] improved the bound for planar graphs to max{2∆(G) -2, ∆ + 22}. They also studied planar graphs with specified girth and maximum degree. They showed the following theorem.

Theorem 1 ([9]). Let G be a planar graph with maximum degree ∆ and girth g. Then

1. χ ′ a (G) ≤ ∆ + 2 if g ≥ 5; 2. χ ′ a (G) ≤ ∆ + 1 if g ≥ 7; 3. χ ′ a (G) = ∆ if g ≥ 16 and ∆ ≥ 3.
Moreover, they proved that ∆ + 1 color suffice for an acyclic edge coloring of a series-parallel graph G.

Cohen, Havet, and Müller [START_REF] Cohen | Acyclic edge-colouring of planar graphs[END_REF] proved another bound for acyclic chromatic index of planar graphs. They showed that χ ′ a (G) ≤ ∆(G) + 25. They also posed the following conjecture.

Conjecture 2 ([11]

). There exists an integer ∆ for which every planar graph G with maximum degree ∆(G) ≥ ∆ admits an acyclic edge coloring with ∆(G) colors. This is an analogue to the conjecture of Vizing [START_REF] Vizing | Critical graphs with a given chromatic number[END_REF] which says that all planar graphs with maximum degree at least 6 are ∆-edge colorable.

The upper bound for acyclic chromatic index of planar graphs has been recently improved by Basavaraju and Chandran [START_REF] Basavaraju | A note on acyclic edge coloring of complete bipartite graphs[END_REF]. They proved that χ ′ a (G) ≤ ∆ + 12 for every planar graph G.

Furthermore, the bounds for planar graphs with specified girth were improved by Yu, Hou, Liu, Liu, and Xu [START_REF] Yu | Acyclic edge coloring of planar graphs with large girth[END_REF]. They proved the two theorems below.

Theorem 2 ([14]

). Let G be a planar graph with girth g and maximum degree ∆. Finally, in 2010 Borowiecki and Fiedorowicz [START_REF] Borowiecki | Acyclic edge colouring of planar graphs without short cycles[END_REF] verified Conjecture 1 for planar graphs with girth at least 5. They also showed that χ ′ a (G) ≤ ∆(G) + 1 for every planar graph G with girth at least 6, which improves the previous result of Hou et al. [START_REF] Hou | Acyclic edge colorings of planar graphs and series-parallel graphs[END_REF].

In this paper we studied the acyclic edge colorings of planar graphs with ∆(G) colors and improved several previous results. Our results are the following. In Table 1 we present the best known bounds for planar graphs. Our results are marked with an asterisk. In the paper we use the standard notation. The degree of a vertex v (the size of a face f ) is denoted by

∆(G)

d(v) (resp. d(f )). A vertex with degree k (at least k, at most k) is called a k-vertex (a ≥ k-vertex, a ≤ k-vertex, respectively). The neighbor u of degree k of a vertex v is called a k-neighbor of v.
Given an edge coloring ϕ of G, we say that the color a is free at the vertex v if there is no edge incident to v colored with color a. On the other hand, a color a is used at v if there is some edge incident with v which is colored by a. A path induced by colors a and b is called an {a, b}-path.

Proof of Theorem 4.

We prove each claim of Theorem 4 separately. In all proofs we assume that there exists a minimal counterexample G to the claim and show that it cannot exist by studying its properties. First, we show that certain configurations cannot occur in the minimal counterexample. Then we assign charge to the vertices and faces of G. Using Euler's formula we compute that the total charge is negative. However, by redistributing the charge among vertices and faces, we show that it is nonnegative, reaching a contradiction. Hence, the minimal counterexample G does not exist. This approach is the well known discharging method which remains the only technique for proving the Four Color Theorem.

Reducible configurations

First, we prove some general properties of the minimal counterexample G. Throughout this section, we assume that the girth of G is at least 5 and the maximum degree of G is ∆ ≥ 3.

Claim 1. Minimum degree of G is at least 2.
Proof. Let v be a vertex of degree 1 in G. Then the graph G ′ = G -v is not a counterexample, thus it has an acyclic edge coloring using at most ∆ colors. This coloring can obviously be extended to a desired coloring of G, what is a contradiction with the assumption of G being a counterexample.

From now on we may assume that there are no 1-vertices in G.

d i ≥ ∆ + k. Proof. Let v be a k-vertex in G with neighbors v 1 , v 2 ,. . . , v k of degrees d 1 , d 2 ,. . . , d k such that d 1 + d 2 + • • • + d k ≤ ∆ + k -1.
Let ϕ be an acyclic edge coloring of G -v using at most ∆ colors. There are

d i -1 colors used at v i , i = 1, 2, . . . , k. Since (d 1 -1) + (d 2 -1) + • • • + (d k -1) ≤ ∆ -1,
there is a color, say c 1 , which is not used at any v i , i = 1, 2, . . . , k. We color the edge vv 1 with this color. For the edge vv i (2 ≤ i ≤ k) we use any color c i which does not appear on edges vv 1 , vv 2 ,. . . ,vv i-1 and which is not used at v i , v i+1 ,. . . ,v k . There are at most

i -1 + (d i -1) + • • • + (d k -1) ≤ k j=1 (d j -1) ≤ ∆ -1
forbidden colors, hence, such color c i exists. It is clear that we obtained a proper coloring of G using at most ∆ colors. To conclude the proof it suffices to prove that no bichromatic cycle could have arisen. Let vv i and vv j be a part of a cycle colored with colors c i and c j , 1 ≤ i < j ≤ k. Then the color c i must be used at v j , a contradiction with the choice of c i .

As a special case of Claim 2 we get the following statement:

Claim 3. There is no 2-vertex v in G incident with vertices v 1 and v 2 such that d(v 1 ) + d(v 2 ) ≤ ∆ + 1.
Consider the graph H induced by 2-vertices of G. Let vertices isolated in H be white, let the other 2-vertices be black. The previous claim immediately implies: Claim 4. There is no path of at least 3 black vertices in G. Moreover, each black 2-vertex is adjacent to a ∆-vertex.

It means that H consists of (isolated) white vertices and (isolated) pairs of black vertices. More detailed analysis yields: Let ϕ be an acyclic edge coloring of G ′ = G -f 1 using at most ∆ colors. We may assume that ϕ(e 1 ) = 1 and ϕ(e 2 ) = 2. If ϕ(f ′ 1 ) = 1, we can extend ϕ to an acyclic edge coloring of G easily. Hence, we may assume ϕ(f ′ 1 ) = 1. We may set ϕ(f 1 ) = 2, unless there is a {1, 2}-path in G ′ from v 1 to u 1 . If this is the case, we have ϕ(f 2 ) = 1 and ϕ(f ′ 2 ) = 2. Now we recolor the edges in the following way: we set ϕ(f 1 ) = 3, ϕ(e 1 ) = 2, ϕ(e 2 ) = 1, ϕ(f 2 ) = 3. It can be easily checked that no bichromatic cycle has been created.

Claim 5. Every vertex in G has at most one black 2-neighbor. Proof. Suppose a vertex v has two black 2-neighbors v 1 and v 2 in G. Let u i be the neighbor of v i distinct from v; let e i = vv i , f i = v i u i , i = 1, 2. Let f ′ i be the edge incident with u i distinct from f i , i = 1, 2. See Figure 1 for illustration. v v 1 v 2 u 1 u 2 f ′ 1 f ′ 2 f 1 e 1 e 2 f 2 1 1 2 1 2 -→ v v 1 v 2 u 1 u 2 f ′ 1 f ′ 2 f 1 e 1 e 2 f 2 1 3 2 1 3 2

Neighborhood of ∆-vertices

We say that vertices u and v are subadjacent, if there is a 2-vertex adjacent to both u and v.

Claim 6. Let v be a ∆-vertex subadjacent to a vertex u in G. Then the number of 2-neighbors of v is at most d(u).
Proof. If d(u) = ∆ there is nothing to prove, so we may assume that d

(u) = k < ∆. Suppose the number of 2-neighbors of v is at least k + 1. Let v 1 , v 2 ,. . . , v k+1 be 2- neighbors of v; let u i be the neighbor of v i different from v, let e i = vv i and f i = v i u i , i = 1, 2, . . . , k + 1. Assume u = u 1 . See Figure 2 for illustration.
Let ϕ be an acyclic edge coloring of G ′ = G -f 1 using at most ∆ colors. Let 1, 2, . . . , k -1 be the colors used at u. If ϕ(e 1 ) / ∈ {1, 2, . . . , k -1}, we color f 1 with any color free at u distinct from ϕ(e 1 ). This is always possible, since u has only k -1 < ∆-1 colored edges. It is clear that we obtain an acyclic edge coloring of G using at most ∆ colors. Hence, we may assume that ϕ(e 1 ) = 1. Consider now the colors of e 2 , . . . , e k+1 . At most k-1 of them are from {2, . . . , k -1}, hence, there are (at least) two edges colored with colors free at u. Without loss of generality we may assume that ϕ(e k ) = k and ϕ(e k+1 ) = k + 1.

v u v 1 v 2 v k v k+1 e 1 f 1 e 2 f 2 e k f k e k+1 f k+1 1 k 1 k + 1 1 1 k -1 -→ v u v 1 v 2 v k v k+1 e 1 f 1 e 2 f 2 e k f k e k+1 f k+1 1 k k + 1 1 k 1 1 k -1
If ϕ(f k ) = 1, then we set ϕ(f 1 ) = k and no bichromatic cycle arises. Similarly if ϕ(f k+1 ) = 1, then we set ϕ(f 1 ) = k + 1. Hence we may assume ϕ(f k ) = ϕ(f k+1 ) = 1. Moreover, we may assume that in the subgraph G ′ 1k of G ′ induced by the edges of colors 1 and k the vertices v 1 and u are the endvertices of the same {1, k}-path, another such path starts in v k . In this case we set ϕ(e k ) = k + 1 and ϕ(e k+1 ) = k. Clearly, we obtain an acyclic edge coloring of G ′ . Now, in G ′ 1k the {1, k}-path from u ends in v k , hence, we can set ϕ(f 1 ) = k without introducing a bichromatic cycle. Let ϕ be an acyclic edge coloring of G ′ = G -f 1 using at most ∆ colors. Let 1, 2, . . . , k -1 be the colors used at u. If ϕ(e 1 ) / ∈ {1, 2, . . . , k -1}, then we find a color c which is free at v (this is always possible since d(v) < ∆) and we set ϕ(f 1 ) = ϕ(e 1 ) and ϕ(e 1 ) = c. It is easy to see that we obtain an acyclic edge coloring of G.

Neighborhood of other vertices

f i = v i u i for i = 1, 2, . . . , ℓ. Assume u = u 1 . See Figure 3 for illustration. v u v 1 v 2 v ℓ-1 v ℓ e 1 f 1 e 2 f 2 e ℓ-1 f ℓ-1 e ℓ f ℓ 1 k 1 1 k -1 -→ v u v 1 v 2 v ℓ-1 v ℓ e 1 f 1 e 2 f 2 e ℓ-1 f ℓ-1 e ℓ f ℓ 1 k c 1 1 k -1
Hence, without loss of generality we may assume that ϕ(e 1 ) = 1. The colors k, k + 1, . . . , ∆ are free at u. If at least one of them is also free at v, we use this color on f 1 to extend ϕ to an acyclic edge coloring of G. Therefore, we may assume all the colors k, k + 1, . . . , ∆ are used at v. Since v has at most ∆ -k neighbors of degree greater than 2, one of the edges e 2 , . . . , e ℓ is colored with one of the colors k, k + 1 . . . , ∆. Without loss of generality assume that ϕ(e 2 ) = k.

Consider the color of f 2 . If ϕ(f 2 ) = 1, then we set ϕ(f 1 ) = k and we are done. If ϕ(f 2 ) = 1, then we find a color c which is free at v (recall that d(v) < ∆), and set ϕ(e 2 ) = c and ϕ(f 1 ) = k. It is clear that no bichromatic cycle was created.

As a corollary we get the following property of G:

Claim 8. There is no vertex v in G with d(v) < ∆ adjacent only to 2-vertices.

Planar graphs with girth 5

Let us reformulate the first statement of Theorem 4.

Lemma 5. Let ∆ ≥ 10. Every planar graph with girth at least 5 and maximum degree at most ∆ admits an acyclic edge coloring with ∆ colors.

Let G be a minimal counterexample to Lemma 5 with respect to the number of edges.

Discharging rules

Let the initial charge be set as follows:

• w(v) = 3d(v) -10 for each vertex v of G; • w(f ) = 2d(f ) -10 for each face f of G.
Using Euler's formula and handshaking lemma we can derive that the sum of the charge in whole graph is negative:

v∈V w(v) + f ∈F w(f ) = 3 • v∈V d(v) -10 • |V | + 2 • f ∈F d(f ) -10 • |F | = = 3 • 2 • |E| -10 • |V | + 2 • 2 • |E| -10 • |F | = 10 • (|E| -|V | -|F |) = -20.
It is clear that all the faces have nonnegative charge since g ≥ 5. Vertices of degree at least 4 have positive charge, 3-vertices have charge -1 and 2-vertices have charge -4.

We move the negative charge from 2-vertices and 3-vertices according to the following rules:

(R1) Let v be a 2-vertex with neighbors v 1 and v 2 . Let d = d(v 1 ) ≤ d(v 2 ). (R1a) If d ≤ 3, then v sends no charge to v 1 and -4 of charge to v 2 . (R1b) If d = 4, then v sends -1 2 of charge to v 1 and -7 2 of charge to v 2 . (R1c) If 5 ≤ d < 9, then v sends -3d-11 d-1 of charge to v 1 and -d+7 d-1 of charge to v 2 . (R1d) If d ≥ 9, then v sends -2 of charge both to v 1 and v 2 . (R2) Let v be a 3-vertex with neighbors v 1 , v 2 , and v 3 . Let d(v 1 ) ≤ d(v 2 ) ≤ d(v 3 ). Then v sends -1 of charge to v 3 .
Notice that for 5 ≤ d < 9 we have 3d-11 d-1 < 2 < d+7 d-1 and that for d = 9 rules (R1c) and (R1d) coincide. Observe that by Claim 3 in (R1a) we have

d(v 2 ) ≥ ∆-1 ≥ 9 > 3 ≥ d(v 1 ) and in (R1b) we have d(v 2 ) ≥ ∆ -2 ≥ 8 > 4 = d(v 2 ). In (R1c), if d(v 1 ) = d(v 2 ), we choose v 1 arbitrarily.
To make the proof complete we need to show that after the discharging rules are applied, the charge of all vertices is nonnegative. Observe that all 2-vertices send all their negative charge to their neighbors, moreover, only vertices of degree at least 4 receive some negative charge from 2-vertices.

Similarly, all 3-vertices send all their negative charge to some of their neighbors. By Claim 2 for each 3-vertex v with neighbors v 1 , v 2 , and

v 3 such that d(v 1 ) ≤ d(v 2 ) ≤ d(v 3 ) we have d 1 + d 2 + d 3 ≥ ∆ + 3 ≥ 13.
Therefore, d(v 3 ) ≥ 5 and only vertices of degree at least 5 receive some negative charge from 3-vertices.

Let v be a 4-vertex. Its initial charge is 2. By (R1b) it only receives -1 2 of charge from each 2-neighbor, hence, its charge is at least 2 -4 • 1 2 ≥ 0.

Vertices of degree ∆

Let v be a ∆-vertex. Its initial charge is 3∆ -10. It receives at most -1 of charge from each 3-neighbor, thus if it has no 2-neighbor its charge is at least 3∆ -10 -∆, which is clearly positive. Assume v has some 2-neighbors. It means it is subadjacent to some vertices; let k be the minimum degree of a vertex subadjacent to v. Then by Claim 6 the number of 2-neighbors of v is at most k.

Let k ≤ 3. Then v has at most three 2-neighbors which send at most -4 of charge to v by (R1a)-(R1d). The charge of v is at least 3∆ -10

-3 • 4 -(∆ -3) = 2∆ -19 which is positive since ∆ ≥ 10.
Let k = 4. Then v has at most four 2-neighbors which send at most -7 2 of charge to v by (R1b)-(R1d). The charge of v is at least 3∆ -10 -4 • 7 2 -(∆ -4) = 2∆ -20 which is nonnegative since ∆ ≥ 10.

Let 5 ≤ k ≤ 9. Then each 2-neighbor of v sends at most -k+7 k-1 of charge to v by (R1c) or (R1d). The number of 2-neighbors of v is at most k, thus the charge of v is at least

3∆ -10 -k • k + 7 k -1 -(∆ -k) = 2∆ -10 - 8k k -1 = 2∆ -18 - 8 k -1 .
This is nonnegative since k -1 ≥ 4 and ∆ ≥ 10. Let k ≥ 10. Then each 2-neighbor of v sends -2 of charge to v. Then the charge of

v is at least 3∆ -10 -k • 2 -(∆ -k) = 2∆ -10 -k.
This is nonnegative since ∆ ≥ 10 and k ≤ ∆.

Other vertices of degree at least 5

Let v be a d-vertex, 5 ≤ d < ∆. Its initial charge is 3d -10. It receives at most -1 of charge from each 3-neighbor, thus if it has no 2-neighbor its charge is at least 3d-10-d, which is clearly nonnegative for d ≥ 5. Assume v has some 2-neighbors. It means it is subadjacent to some vertices; let k be the minimum degree of a vertex subadjacent to v. By Claim 4 we have k ≥ 3. By Claim 3 for each subadjacent vertex u i we have

d(u i ) ≥ ∆ + 2 -d. Therefore, k ≥ ∆ + 2 -d, thus, d ≥ ∆ + 2 -k. Recall that by Claim 7 the number of 2-neighbors of v is at most d + k -∆ -1 = k -1 -(∆ -d) ≤ k -2.
Now, consider several cases regarding k: k-1 of charge to v by (R1c) or (R1d). So the charge of v is at least

If k = 3, then d ≥ ∆ -1 ≥ 9,
3d -10 -(d + k -∆ -1) • k + 7 k -1 -(∆ + 1 -k) = 2(kd -9k -5d + 4∆ + 9) k -1 ≥ ≥ 2(kd -9k -5d + 49) k -1 = 2[(k -5)(d -9) + 4] k -1 .
This is nonnegative since k -5 ≥ 0 and d -9 ≥ -4. If 9 ≤ k and k ≤ d, then each 2-neighbor of v sends -2 of charge to v by (R1d). Then the charge of v is at least

3d -10 -(d + k -∆ -1) • 2 -(∆ + 1 -k) = d -9 + ∆ -k.
-10 -(d -1) • 3d -11 d -1 -1 = 0.
Since all the vertices of G have nonnegative charge, we obtain a contradiction which completes the proof.

Planar graphs with girth 6

Lemma 6. Let ∆ ≥ 6. Every planar graph with girth at least 6 and maximum degree at most ∆ admits an acyclic edge coloring with ∆ colors.

Suppose G is a minimal counterexample to Lemma 6.

Discharging rules

Let the initial charge be set as follows:

• w(v) = 2d(v) -6 for each vertex v of G; • w(f ) = d(f ) -6 for each face f of G.
By Euler's formula we have that the sum of charges of vertices and faces is -12.

It is clear that since g ≥ 6 all the faces have nonnegative charge. Vertices of degree at least 4 have positive charge, 3-vertices have no charge and 2-vertices have charge -2.

We redistribute the charge among vertices by the following rules: It is easy to see that 2-vertices send all their negative charge to their neighbors. Since ∆ ≥ 6, by Claim 3 for each 2-vertex with neighbors with degrees d 1 and d 2 we have d 1 + d 2 ≥ ∆ + 2 ≥ 8, therefore, only vertices of degree at least 4 can receive negative charge. Hence, 3-vertices neither send nor receive any charge, so they retain chargeless.

(R3) Let v be a 2-vertex with neighbors v 1 and v 2 such that d(v 1 ) ≤ d(v 2 ). (R3a) If d(v 1 ) ≤ 3, then v sends -2 of charge to v 2 . ( R3b

4-vertices

Let v be a 4-vertex in G. Its initial charge is 2. If it has no 2-neighbors, its charge does not change. By Claim 3 it cannot be subadjacent to a 3-vertex. If it is subadjacent to a 4-vertex, by Claim 7 the number of 2-neighbors of v is at most 4+ 4-∆ -1 = 7-∆ ≤ 1, hence, it has only one 2-neighbor from which it receives -1 of charge by (R3b). Its final charge is (at least) 2 -1 = 1.

If it is only subadjacent to vertices of degree at least five, it can have at most three 2-neighbors by Claim 8. By (R3c) it receives -2 3 of charge from each 2-neighbor, hence, its charge is at least 2 -3 • 2 3 = 0.

5-vertices

Let v be a 5-vertex in G.

Its

Other vertices

Let v be a d-vertex, where d ≥ 6. Its initial charge is 2d -6 ≥ 6. If it has no 2neighbors, it does not receive any negative charge. Suppose v has some 2-neighbors; let k be a minimum degree of a vertex subadjacent to v.

If k ≤ 3, then by Claims 6 and 7 the vertex v has at most three 2-neighbors, and each has sent at most -2 of charge. Hence, the charge of v is nonnegative.

If k = 4, then v has at most four 2-neighbors, and each has sent at most -4 3 of charge. Hence, the charge of v is at least 6 -4

• 4 3 = 2 3 > 0. If k ≥ 5, then v receives at most -1 of charge from each neighbor, hence its charge is at least 2d -6 -d = d -6 ≥ 0.
All the vertices of G have nonnegative charge, a contradiction which establishes the lemma.

Planar graphs with girth 7

Lemma 7. Let ∆ ≥ 5. Every planar graph with girth at least 7 and maximum degree at most ∆ admits an acyclic edge coloring with ∆ colors.

If ∆ ≥ 6, then the statement follows from Lemma 6. Therefore, we may assume that ∆ = 5 and ∆(G) ≤ 5. Suppose G is a minimal counterexample to Lemma 7.

Planar graphs with girth 8

Lemma 8. Let ∆ ≥ 4. Every planar graph with girth at least 8 and maximum degree at most ∆ admits an acyclic edge coloring with ∆ colors.

If ∆ ≥ 5, then the statement follows from Lemma 7. Therefore, we may assume that ∆ = 4 and ∆(G) ≤ 4. Suppose G is a minimal counterexample to Lemma 8.

Before setting discharging rules, we prove several additional properties of G.

More reducible configurations

Let a 3-vertex with two 2-neighbors be blue. We focus on the neighborhood of blue vertices.

Claim 9. Each blue 3-vertex is subadjacent to two 4-vertices.

Proof. Let v be a blue 3-vertex with 2-neighbors v 1 and v 2 ; let u i be the neighbor of v i distinct from v, i = 1, 2. If d(u i ) ≤ 3, then by Claim 7 there are at most

d(v) + d(u i ) -∆ -1 ≤ 3 3 -4 -1 = 1
2-vertices adjacent to v in G, however, both v 1 and v 2 are 2-vertices, a contradiction.

Claim 10. Each blue 3-vertex is adjacent to a 4-vertex.

Proof. Let v be a blue 3-vertex with neighbors

v 1 , v 2 , v 3 . Let d(v 1 ) = 2, d(v 2 ) = 2, d(v 3 ) = 3; let e i = vv i , i = 1, 2, 3. Let f i be the edge incident with v i different from e i , i = 1, 2. Let f 3 , f 4 be edges incident with v 3 different from e 3 .
Let G ′ be the graph obtained from G by deletion of the edges e 1 , e 2 , and e 3 . Let ϕ be an acyclic edge coloring of G ′ using at most 4 colors. Consider the colors of f 1 , f 2 , f 3 , and f 4 . We distinguish all possible cases up to symmetry and permutation of colors. See Figure 4 for illustration. Let ϕ(f 1 ) = ϕ(f 2 ) = 1. If 1 / ∈ {ϕ(f 3 ), ϕ(f 4 )}, then we set ϕ(e 1 ) = ϕ(f 3 ) and ϕ(e 2 ) = ϕ(f 4 ); for the edge e 3 we use the fourth color. If 1 = ϕ(f 3 ), then we set ϕ(e 1 ) = ϕ(f 4 ); for the edges e 2 and e 3 we use the othe two colors. Now, we may assume that ϕ(f 1 ) = 1 and ϕ(f 2 ) = 2. Let the four edges f 1 , f 2 , f 3 , and f 4 be colored by four colors, say ϕ(f 3 ) = 3, ϕ(f 4 ) = 4. Then we set ϕ(e 1 ) = 2, ϕ(e 2 ) = 3, and ϕ(e 3 ) = 1.

Let the four edges f 1 , f 2 , f 3 , and f 4 be colored by three colors, say ϕ(f 3 ) = 1, ϕ(f 4 ) = 3. Then we set ϕ(e 1 ) = 2, ϕ(e 2 ) = 3, and ϕ(e 3 ) = 4.

Let the four edges f 1 , f 2 , f 3 , and f 4 be colored by two colors, say ϕ(f 3 ) = 1, ϕ(f 4 ) = 2. Then we set ϕ(e 1 ) = 2, ϕ(e 2 ) = 3, and ϕ(e 3 ) = 4. It is easy to see that ϕ is now an acyclic edge coloring of G using at most 4 colors, a contradiction. Claim 11. Let v be a 4-vertex subadjacent to two 3-vertices. Then the number of 2neighbors of v is two.

v v 1 v 2 v 3 1 1 2 3 2 3 4 v v 1 v 2 v 3 1 1 1 2 2 3 4 v v 1 v 2 v 3 1 2 3 4 2 3 1 v v 1 v 2 v 3 1 2 1 3 2 3 4 v v 1 v 2 v 3
Proof. Let v be a 4-vertex subadjacent to u 1 , u 2 , u 3 such that d(u 1 ) = d(u 2 ) = 3. Let v i be the common neighbor of v and u i , i = 1, 2, 3. Let v 4 be the other neighbor of v. Let e i = vv i , i = 1, 2, 3, 4, f i = v i u i , i = 1, 2, 3. See Figure 5 for illustration.

Let ϕ be an acyclic edge coloring of G ′ = G -f 1 using at most 4 colors. Assume ϕ(e 1 ) = 1.

There are two colors free at u 1 . If 1 is free at u 1 , then we use the other free color for f 1 to extend ϕ to an acyclic edge coloring of G. Hence, we may assume that 1 is used at u 1 . Let 3 and 4 be the colors free at u 1 .

We can use the color 3 (or 4) for f 1 unless we introduce a bichromatic cycle. Therefore, we may assume that in G ′ , there is a {1, 3}-path from v 1 to u 1 and also a {1, 4}-path from v 1 from u 1 .

Consider the color of e 2 . Suppose first that ϕ(e 2 ) = 3. Since there is a {1, 3}-path from v 1 to u 1 , we have ϕ(f 2 ) = 1 and we know that 3 is used at u 2 . Hence, there is a color c ∈ {2, 4} free at u 2 . In this case we set ϕ(e 1 ) = 3, ϕ(f 1 ) = 4, ϕ(e 2 ) = 1, and ϕ(f 2 ) = c, see Figure 5(a). It is easy to see that no bichromatic cycle arises. We can use the same argument if ϕ(e 2 ) = 4. Hence, we may assume that ϕ(e 2 ) = 2; without loss of generality let ϕ(e 3 ) = 3 and ϕ(e 4 ) = 4. Then ϕ(f 3 ) = 1.

Consider the color of f 2 . Suppose first that ϕ(f 2 ) = 1. In this case, we set ϕ(f 1 ) = 3, ϕ(e 1 ) = 2, and ϕ(e 2 ) = 1. It is easy to see that no bichromatic cycle is created, since the {2, 3}-path containing v 1 ends at v 3 , the {1, 2}-path and {1, 3}-path containing v 2 ends at v 1 , and {1, 4}-path containing v 2 ends at u 1 , see Figure 5(b).

Finally, suppose that ϕ(f 2 ) = 1. Then there is a color, say c = 1, free at u 2 . In this case, we set ϕ(f 1 ) = 3, ϕ(e 1 ) = 2, ϕ(e 2 ) = 1, and ϕ(f 2 ) = c, see Figure 5(c). Again, no bichromatic cycle arises.

Discharging rules

Let the initial charge be set as follows:

• w(v) = 3d(v) -8 for each vertex v of G; • w(f ) = d(f ) -8 for each face f of G.
By Euler's formula we have that the sum of charges of vertices and faces is -16.

It is clear that since g ≥ 8 all the faces have nonnegative charge. Vertices of degree 4 have charge 4, vertices of degree 3 have charge 1, and vertices of degree 2 have charge -2.

We redistribute the charge among vertices by the following rules:

(R5a) Each white 2-vertex divides its charge (-2) equally among its two neighbors.

(R5b) Each black 2-vertex sends all its charge (-2) to the neighbor which is not a 2vertex.

After this phase all 2-vertices have charge 0. However, some other vertices can have become negative.

Consider a 3-vertex v in G. Its initial charge is 1. By Claim 3 it cannot have a black 2-neighbor. By Claim 8 it can have at most two (white) 2-neighbors. If v has at most one 2-neighbor, then it receives at most -1 of charge, so its charge is at least 0. Thus, only 3-vertices with precisely two 2-neighbors -blue 3-vertices -have negative charge. Let v be a blue 3-vertex. It is subadjacent to two vertices u 1 and u 2 via 2-vertices v 1 and v 2 . By Claim 9 both u 1 and u 2 are 4-vertices. Moreover, by Claim 10 the third neighbor v 3 of v is also a 4-vertex. The charge of v is now 1 + 2 • (-1) = -1.

a) u 1 v 1 v v 2 u 2 v 4 v 3 u 3 f 1 e 1 e 2 f 2 e 4 e 3 f 3 13 1 3 1 1 2 2 3 -→ u 1 v 1 v v 2 u 2 v 4 v 3 u 3 f 1 e 1 e 2 f 2 e 4 e 3 f 3 13 4 3 1 4 1 2 2 3 (b) u 1 v 1 v v 2 u 2 v 4 v 3 u 3 f 1 e 1 e 2 f 2 e 4 e 3 f 3 14 13 1 2 4 3 1 1 2 -→ u 1 v 1 v v 2 u 2 v 4 v 3 u 3 f 1 e 1 e 2 f 2 e 4 e 3 f 3 14 13 3 2 1 4 3 1 1 2 (c) u 1 v 1 v v 2 u 2 v 4 v 3 u 3 f 1 e 1 e 2 f 2 e 4 e 3 f 3 14 13 1 2 1 4 3 1 1 2 a b -→ u 1 v 1 v v 2 u 2 v 4 v 3 u 3 f 1 e 1 e 2 f 2
(R6) Each blue 3-vertex v with two 2-neighbors v 1 and v 2 sends -1 2 of charge to the face incident both with v 1 and v 2 ; it sends -1 4 of charge to the other two incident faces.

After this phase all 2-and 3-vertices have nonnegative charge. Some negative charge was sent to 4-vertices and faces.

Consider a 4-vertex v in G. Its initial charge is 4. If v has a black 2-neighbor, then by Claim 6 it has at most two 2-neighbors. Moreover, by Claim 5 at most one of them is black, thus, in this case it receives at most -3 units of charge, so its charge is at least 1. If v has only white 2-neighbors, its charge is at least 4 -4 • 1 ≥ 0. However, if has at most three white 2-neighbors, its charge is at least 1. Let 4-vertices with four 2-neighbors be called red. Observe that by Claim 6 a red 4-vertex cannot be subadjacent to a ≤ 3-vertex, hence, each red 4-vertex is subadjacent to four 4-vertices.

(R7) Each 4-vertex v divides all its charge equally to the four faces it is incident with. Now all vertices have nonnegative charge. Some of the negative charge can have been moved from blue 3-vertices to faces. On the other hand, observe that each face receives at least 1 4 of charge from each incident 4-vertex which is not red.

Big faces

Let f be a face of size k. Its initial charge is k -8; it receives -

Theorem 4 .

 4 Let G be a planar graph with girth g and maximum degree ∆. Then χ ′ a (G) = ∆ if one of the following conditions holds: 1. ∆ ≥ 3 and g ≥ 12, or 2. ∆ ≥ 4 and g ≥ 8, or 3. ∆ ≥ 5 and g ≥ 7, or 4. ∆ ≥ 6 and g ≥ 6, or 5. ∆ ≥ 10 and g ≥ 5.

Claim 2 .

 2 Let v be a vertex of degree k in G, let d 1 , d 2 ,. . . ,d k be the degrees of the neighbors of v. Then k i=1

Figure 1 :

 1 Figure 1: Reducing a vertex v with two black 2-neighbors.

Figure 2 :

 2 Figure 2: Reducing a ∆-vertex v subadjacent to a k-vertex u and having at least k + 1 2-neighbors.

Claim 7 .

 7 Let u and v be a pair of subadjacent vertices. If d(v) < ∆, then the number of 2-vertices adjacent to v is at most d(v) + d(u) -∆ -1. Proof. Let d(v) = d and d(u) = k. Suppose that v has at least d(v)+d(u)-∆ = d+k-∆ neighbors of degree 2. It means v has at most ∆ -k neighbors of degree greater than 2. Let v 1 , v 2 ,. . . , v ℓ be 2-neighbors of v, where ℓ = d + k -∆; let u i be the neighbor of v i different from v, let e i = vv i and

Figure 3 :

 3 Figure 3: Reducing a d-vertex v subadjacent to a k-vertex u and having at least d + k -∆ 2-neighbors.

  moreover, v has one 2-neighbor. The charge of v is at least 3d -10 -4 -(d -1) = 2d -13 which is positive for d ≥ 9. If k = 4, then d ≥ ∆ -2 ≥ 8, moreover, v has at most two 2-neighbors. The charge of v is at least 3d -10 -2 • 7 2 -(d -2) = 2d -15 which is positive for d ≥ 8. If 5 ≤ k ≤ 8 and k ≤ d, then each 2-neighbor of v sends at most -k+7

  This is nonnegative since d ≥ 9 and k ≤ ∆. If 5 ≤ k and d < k, then each 2-neighbor of v sends -3d-11 d-1 of charge to v by (R1c). By Claim 8 the number of 2-neighbors of v is at most d -1. The charge of v is at least 3d

  ) If d(v 1 ) = 4 and d(v 2 ) = 4, then v sends -1 of charge to both v 1 and v 2 . (R3c) If d(v 1 ) = 4 and d(v 2 ) ≥ 5, then v sends -2 3 of charge to v 1 and -4 3 of charge to v 2 . (R3d) If d(v 1 ) ≥ 5, then v sends -1 of charge to both v 1 and v 2 .

Figure 4 :

 4 Figure 4: Reducing a 3-vertex with neighbors of degrees 2, 2, 3, respectively.

(

Figure 5 :

 5 Figure 5: Reducing a 4-vertex v subadjacent to two 3-vertices u 1 , u 2 and another vertex u 3 .

Figure 7 :• 2 3 -3d 5 • 1 = 2d 3 -

 7513 Figure 7: Reducing a path with degrees 2, 2, 3, 2, 3, 2, 2.

Table 1 :

 1 Overview of known and new results.

		3	4	5	6 . . . 10	11	12
	3 ∆ + 12
	4 ∆ + 6
	5 ∆ + 2			∆ * ∆ + 1
	6 ∆ + 1			∆ *
	g(G) 7			∆ *			∆
	8		∆ *		∆
	10			∆
	12	∆ *	∆
	16	∆

  1 4 or -1 2 of charge from each blue 3-vertex it is incident with. Let v 1 , . . . , v k be the vertices incident with f in

														f 5																f 5
	(a)	e 0 1	v 1	e 1	v 2	v 3 f 3 e 2 1 3	e 3 2	v 4	e 4 1	v 5	e 5	v 6	e 6	v 7	e 7	-→	e 0 1	v 1	e 1 3	v 2	v 3 f 3 e 2 2 3	e 3 1	v 4	e 4 1	v 5	e 5	v 6	e 6	v 7	e 7
					13																			13
											12																		12
	(b)	e 0 1	v 1	e 1 3	v 2	e 2 2	v 3	e 3 1	v 4	e 4 1	v 5 f 5 e 5 2 3	v 6	e 6 1	v 7	e 7 2	-→	1 e 0	v 1	3 e 1	v 2	2 e 2	v 3	1 e 3	v 4	2 e 4	v 5 f 5 1 e 5 3	v 6	3 e 6	v 7	2 e 7
						f 3	3																	f 3	3
					13																			13
							12																		12
	(c)	e 0 1	v 1	e 1 3	v 2	v 3 f 3 e 2 2 3	e 3 1	v 4	e 4 1	v 5 f 5 e 5 3 2	v 6	e 6	v 7	e 7 = 2	-→	1 e 0	v 1	3 e 1	v 2	v 3 3 f 3 2 e 2	1 e 3	v 4	3 e 4	v 5 f 5 1 e 5 2	v 6	2 e 6	v 7	= 2 e 7
					13																			13
							12
	(d)	e 0 1	v 1	e 1 3	v 2	e 2 2	v 3		e 3 1	v 4	e 4 1	v 5 f 5 e 5 3 2	v 6	e 6 1	v 7	e 7 2	-→	e 0	v 1	e 1	v 2	e 2	v 3	e 3	v 4	e 4	v 5	e 5	v 6	e 6	v 7	e 7
						f 3	3
					13

Preprint series, IMFM, ISSN 2232-2094, no. 1123, August 04, 2010

Supported in part by bilateral project SK-SI-0007-08 between Slovakia and Slovenia, by VVGS grant No. 617-B (I-10-032-00) (D. Hudák), and by Slovak Research and Development Agency under contract No. APVV-0007-07 (F. Kardoš and R. Soták). † Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia. Operation part financed by the European Union, European Social Fund. . Partially supported by Ministry of Science and Technology of Slovenia, Research Program P1-0297.

Discharging rules

Let the initial charge be set as follows:

• w(v) = 5d(v) -14 for each vertex v of G;

• w(f ) = 2d(f ) -14 for each face f of G. By Euler's formula we have that the sum of charges of vertices and faces is -28.

It is clear that since g ≥ 7 all the faces have nonnegative charge. Vertices of degree 5 have charge 11, vertices of degree 4 have charge 6, vertices of degree 3 have charge 1, and vertices of degree 2 have charge -4.

We redistribute the charge among vertices by the following rules:

(R4) Let v be a 2-vertex with neighbors v 1 and v 2 such that d(v 1 ) ≤ d(v 2 ).

(R4a) If d(v 1 ) = 2, then v sends 0 of charge to v 1 and -4 of charge to

Since ∆ = 5, by Claim 3 for each 2-vertex with neighbors with degrees d 1 and d 2 we have d 1 + d 2 ≥ ∆ + 2 = 7. It is easy to see that 2-vertices send all their negative charge to their neighbors of degree at least 3.

3-vertices

Let v be a 3-vertex in G. Its initial charge is 1. By (R4b) it receives - 1 3 of charge from each its 2-neighbor, hence its charge is at least 1 -3 • 1 3 = 0.

4-vertices

Let v be a 4-vertex in G. Its initial charge is 6. If it has no 2-neighbors, its charge does not change. By Claim 3 it cannot be subadjacent to a 2-vertex. If it is subadjacent to a 3-vertex, by Claim 7 the number of 2-neighbors of v is at most 3 + 4 -∆ -1 = 1, hence, it has only one 2-neighbor from which it receives -11 3 of charge by (R4b). Its charge is clearly nonnegative.

If v is not subadjacent to any ≤ 3-vertex, then by Claim 8 it can have at most three 2-neighbors, from which it receives -2 of charge by (R4c). Its charge is (at least) 6 -3 • 2 = 0.

5-vertices

Let v be a 5-vertex in G. Its initial charge is 11. If it has no 2-neighbors, its charge does not change.

If v is subadjacent to a 2-vertex, then by Claim 6 it has at most two 2-neighbors, which send at most -4 of charge each. The charge of v is at least 11 -2 • 4 = 3 > 0.

If v is not subadjacent to any 2-vertex and v is subadjacent to a 3-vertex, by Claim 6 it has at most three 2-neighbors, which send at most - 11 3 of charge each. The charge of v is at least 11 -3

All the vertices of G have nonnegative charge, a contradiction which establishes the lemma. a cyclic order. Let v 1 be a blue 3-vertex which sends -1 4 of charge to f . According to (R6), we may assume d(v k ) = 4 and d(v 2 ) = 2, and d(u 1 ) = 2, where u 1 is the neighbor of v 1 not incident with f . By Claim 9 we have d(v 3 ) = 4. It means there is a facial path of length 3 beginning and ending in a 4-vertex, containing the blue 3-vertex v 1 .

Let v 1 be a blue 3-vertex which sends -1 2 of charge to f . According to (R6), we may assume d(v k ) = d(v 2 ) = 2. Again, by Claim 9 we have d(v k-1 ) = d(v 3 ) = 4. It means there is a facial path of length 4 beginning and ending in a 4-vertex, containing the blue vertex v 1 .

Altogether, there can be at most k 3 blue vertices incident with f . The charge of

, which is nonnegative for k ≥ 10.

9-faces

Let f be a 9-face. Its initial charge is 9 -8 = 1. If it is incident with at most two blue 3-vertices, its charge is at least 1-2• 1 2 = 0. Therefore we may assume it is incident with three blue 3-vertices. This can only happen if all the three blue 3-vertices are contained in paths of length 3. Hence, they send 3 • (-1 4 ) of charge to f , and so the final charge of f is clearly nonnegative.

8-faces

Let f be an 8-face. Its initial charge is 0. If it is incident with no blue 3-vertices, it does not receive negative charge.

Let f have received -1 4 of charge from a blue 3-vertex v 1 ; let v 8 be a 4-vertex, v 2 be a white 2-vertex and let v 3 be a 4-vertex. Since the 4-vertex v 8 is adjacent to a 3-vertex v 1 , it is not red; by (R7) it sends at least 1 4 of charge to f . The charge of f is at least

2 of charge from a blue 3-vertex v 1 ; let v 8 and v 2 be white 2-vertices and let v 7 and v 3 be 4-vertices. Since v 3 and v 7 are subadjacent to a 3-vertex v 1 , they are not red; by (R7) the vertices v 3 and v 7 send at least 1 4 of charge to f . The charge of f is at least -1 2 + 2 • 1 4 = 0. Let f have received -1 4 of charge from two blue 3-vertices. There are five possibilities for their position up to symmetry, see Figure 6, the first five images. In all thee cases there are at least two 4-vertices which are not red (recall that a red 4-vertex cannot be adjacent or subadjacent to a ≤ 3-vertex); hence they send at least 1 4 of charge to f each. It means the charge of f is nonnegative. Let f have received - 1 2 of charge from a blue 3-vertex v 1 and -1 4 of charge from another blue 3-vertex. There are two possibilities for its position up to symmetry, see Figure 6, the last two images. In both cases there are three 4-vertices which send at least 1 4 of charge to f , hence, its charge is nonnegative.

Let f have received -1 2 of charge from two blue 3-vertices v 1 and v 5 . Then v 2 , v 4 , v 6 , v 8 are white 2-vertices and v 3 and v 7 are 4-vertices. The 4-vertex v 3 is subadjacent to two 3-vertices v 1 and v 5 , thus by Claim 11 it is not subadjacent to any other vertex. Hence, it only receives -2 of charge from its 2-neighbors by (R5a), and then it sends 1 2 of charge to all incident faces by (R7). Since the same holds for v 7 , the face f receives 1 2 of charge from both v 3 and v 7 , thus its charge in nonnegative.

All the vertices and faces of G have nonnegative charge, a contradiction which establishes the lemma.

Planar graphs with girth 12

Lemma 9. Let ∆ ≥ 3. Every planar graph with girth at least 12 and maximum degree at most ∆ admits an acyclic edge coloring with ∆ colors.

If ∆ ≥ 4, then the statement follows from Lemma 8. Therefore, we may assume that ∆ = 3 and ∆(G) ≤ 3. Suppose G is a minimal counterexample to Lemma 9.

Before setting discharging rules, we prove one more structural property of G.

Claim 12. There is no path

; let e 0 be the edge incident with v 1 distinct from e 1 , let e 7 be the edge incident with v 7 distinct from e 6 ; let f 3 (resp. f 5 ) be the edge incident with v 3 (resp. v 5 ) distinct from e 2 and e 3 (resp. e 4 and e 5 ). Since we assume g ≥ 12 all considered edges are pairwise distinct. Let ϕ be an acyclic edge coloring of G ′ = G -e 1 using colors 1, 2, 3. Let ϕ(e 2 ) = 1, ϕ(e 3 ) = 2, ϕ(f 3 ) = 3. We may assume ϕ(e 0 ) = 1, otherwise we can extend the coloring easily. We also may assume ϕ(e 4 ) = 1, otherwise we can set ϕ(e 1 ) = 2. See Figure 7(a) for illustration.

Let G ij be a subgraph of G ′ induced by edges colored i and j, {i, j} ⊂ {1, 2, 3}. If v 1 and v 2 are not endvertices of the same path in G 13 , we set ϕ(e 1 ) = 3. Hence, we may assume there is a {1, 3}-path from v 1 to v 2 in G ′ . If v 1 and v 2 are not endvertices of one path in G 12 , we set ϕ(e 1 ) = 2. Hence, we may assume there is a {1, 2}-path from v 1 to v 2 in G ′ . We set ϕ(e 1 ) = 3, ϕ(e 2 ) = 2 and ϕ(e 3 ) = 1. Now the edges e 3 and e 4 both have color 1. We now look at the end of the {1, 2}-path from v 1 to v 2 :

• Let ϕ(e 5 ) = 2, ϕ(e 6 ) = 1, and ϕ(e 7 ) = 2. Then ϕ(f 5 ) = 3. In this case we recolor the path in the following way: ϕ(e 4 ) = 2, ϕ(e 5 ) = 1, and ϕ(e 6 ) = 3, see It can be checked easily that in all the cases no bichromatic cycle can arise.

Discharging rules

Let the initial charge be set as follows:

• w(v) = 4d(v) -10 for each vertex v of G;

• w(f ) = d(f ) -10 for each face f of G.


Keywords: Telemonitoring, e-Health, ontology, decision support system, PCG signal, time-frequency analysis, E-care project

Thinks to its level of care and its economic aspect in recent years, telemonitoring is increasingly used. Telemonitoring aims to monitor the patient's health in the comfort of its own home. For this, all patient data that can be useful are collected, and represented in the most appropriate mode; after that, a decision support system is used to detect unsafe situations. E-care is a project of telemonitoring for people suffering of heart failure. It is based on a generic and extensible platform to expand the data and integrate other sources of information. E-care platform is based on the use of ontologies for knowledge representation and decision support system to detect dangerous situations. Adding other sources of information such as auscultation, allows us to have more knowledge on the patient and more efficient decision support system; this can be performed by extracting relevant features from the heart sounds which reveal the mechanical activity of the heart.

I. INTRODUCTION

With the advancement of life expectancy, chronic diseases are becoming increasingly ubiquitous, with an increasing cost of hospitalization. This is why many countries are interested in medical telemonitoring, to keep patients in the comfort of their own home, with a higher level of care, and all this with reduction costs.

Several studies have been done on telemonitoring, to treat chronic diseases such as heart failure, diabetes, renal failure...etc. Other studies have demonstrated the need for telemonitoring, and its benefits in all areas, economic, level of care and well-being of patients. On the other hand, medical monitoring reduces unnecessary travel, which becomes a crucial point, because patients do not necessarily live near to a specialized care center, and travel is expensive and tiring for vulnerable people.

Telemonitoring is based on the transmission and interpretation of medical indicators (clinical, radiological or biological) [START_REF] Lasbordes | La telesante : un nouvel atout au service de notre bien-être : Un plan quinquennal éco-responsable pour le déploiement de la télésanté en France[END_REF]. These data are taken with specialized sensors then transmitted from the patient's home to a central server. Data will be interpreted by the physicians, or an intelligent system.

In the first system, the data were interpreted by physicians; it became very tedious, especially when the number of patients started to increase. Thereafter platforms and intelligent systems have been developed to interpret these data, and up alerts to physicians when detecting dangerous situations.

E-care (www.projet-e-care.fr) is a project of medical monitoring for patients with heart failure. The goal is to achieve early detection of dangerous situations by taking into account all the patient data, and use a methodology to represent and best use of these data. Alerts are lifts to doctors who can at any time access to the data and the patient's profile.

To better interpret the data reported from physiological sensors, we must also take into account other information concerning the patient as its environment and its diseases and medications history ...etc. But this is not sufficient to have a reliable system, because representation of these data also takes a crucial role in alert detecting. Data must be represented in an intuitive manner that facilitates treatment. For this, ontologies are widely accepted as an appropriate form for the conceptualization of knowledge.

E-care platform is based on the use of ontologies to represent knowledge and decision support system to detect alerts. This platform is open and extensible to integrate other data sources, to complete the patient knowledge which will help in diagnostic and anomalies detection.

One of the additional data sources is the PhonoCardioGram (PCG) signal acquired by an electronic stethoscope. PCG and auscultation are noninvasive, low-cost and accurate for diagnosing some heart diseases. The analysis of the cardiac sounds, solely based on the human ear, remains insufficient for a reliable diagnosis of cardiac pathologies, and for a clinician to obtain all the qualitative and quantitative information about cardiac activity. Advanced signal processing tools are applied on the PCG signal to extract relevant features that can be integrated in the E-care ontology.

In Part II of this work, related works are presented, then, we talk about knowledge representation in part III. In part IV, generalities on ontologies and their advantages are presented. Part V presents E-care project and its architecture. Part VI presents briefly the PCG signal processing module, and in part VII these signals are integrated in the E-care platform. Finally we conclude.

II. RELATED WORK

There are a lot of works and studies on telemonitoring in the literature. Comparative study has been done in [START_REF] Benyahia | Ontological architecture for management of telemonitoring system and alerts detection[END_REF]. In what follows, the most important studies are presented.

Adding ontologies based on PCG analysis in E-care project

Amine AHMED BENYAHIA on home telemonitoring for elderly people. Their system uses location sensors to see where the patient has spent his time during the day. After that, data are compared by Hamming measure, to know how long the patient spends in each room. Other studies in the same context as [START_REF] Hadidi | A Predictive Analysis of the Night-Day Activities Level of Older Patient in a Health Smart Home. Ambient Assistive Health and Wellness Management in the Heart of the City[END_REF], [START_REF] Franco | Perspectives in home TeleHealthCare system: Daily routine nycthemeral rhythm monitoring from location data[END_REF] and [START_REF] Fleury | SVM-Based Multi-Modal Classification of Activities of Daily Living in Health Smart Homes: Sensors, Algorithms and First Experimental Results[END_REF] use sensors location of the patient. These studies are based on classification methods to analyze the patient's daily activities.

[7] propose a telemonitoring system with architecture of three levels: the sensor network, the patient server that collects and transmits the information, and the hospital server that processes information and makes them available to physicians. This system uses data mining to detect anomalies.

These systems are based only on data mining, and need constant interaction with physicians. Also, due to the probabilistic characteristic of data mining, alerts detection module is imprecise.

[8] propose a decision support system for telemonitoring of patients with heart failure. The system includes patient data: posture, pulse sensor, physical activities and alerts. This system does not take into account physiological measures related to the heart failure like blood pressure and weight, nor the patient's environment such as temperature and humidity.

[9] propose a system based on multiple ontologies: the personal data of the patient, the house context, social context and alarms. The system uses the rule-based inference of first order, these rules are very dependent on the parameters (eg if temperature> 40 then alert) making them non generic and non-scalable. The rules do not take into account changes in health state of the patient.

[10] detail the design and implementation of a platform for reasoning to anticipate and react intelligently in telemonitoring situations. The system manages intelligent agents, whose behavior is defined and validated by ontologies and rules. [START_REF] Latfi | Ontology-based management of the telehealth smart home, dedicated to elderly in loss of cognitive autonomy[END_REF] propose an ontological architecture for modeling a system Smart Home e-health. The goal is to provide an adaptive system for extending the home support of an aging person with diminished cognitive autonomy.

Each one of these studies deals with a part of telemonitoring, with very limited information about the patient. Also, the technologies used to describe the patient profile are very old with a limited semantic, which reduces their performance and making them difficult to share and evolve.

III. KNOWLEDGE

To have a reliable alert detecting system, we must use the most robust inference system. Inference system needs a knowledge base and inference rules to work on this knowledge. More our knowledge base is completed and includes all patient's information, more our system is efficient.

We can collect lot of data and information about the patient:

• Medical information: antecedents, diseases, medical history ...etc. • Contextual information: pregnancy, smoke cigarette, alcohol and drug dependencies ...etc.

• Physiological information: heart rate, blood pressure, oximetry, temperature, weight ...etc. • Environmental data: like ambient temperature, humidity ...etc. • Behavioral data: like if the patient is sleeping or standing or climbing stairs ...etc.

Every field of these information is very important to understand and compute the medical state of the patient. All systems and studies in the literature don't take into account all these fields. In this case, alert detection isn't accurate, for example, if the heart rate of 70 isn't dangerous for a normal patient, this will be dangerous if we know that the patient is alcohol dependent. In other words, if we don't use all patient's information, the system is unreliable.

Even if we take into account all patient's information, this is insufficient to have a reliable system, because this depend also on the knowledge representation and the technologies used to handle them.

The increasing use of terminologies and thesaurus, in health information systems encourages the use of methodologies and technologies from the Semantic Web community. In other words, machines have to understand the knowledge representation.

Ontologies are accepted as the best semantic knowledge representation. For that, we use ontologies to represent every field of patient's information, to have a shared definition of all our domain's concepts.

IV. ONTOLOGIES

The first accepted definition for ontology is that of [START_REF] Gruber | Towards principals for the design of ontologies used for knowledge sharing[END_REF], "explicit specification of a conceptualization". This definition has also been clarified by [START_REF] Studer | Knowledge Engeeneering : Principles and Methods[END_REF] to be: "Ontology is an explicit formal specification and a shared conceptualization".

In this definition, it is necessary to correctly interpret each used term. Formal: the machine can understand. Explicit: the concepts, relationships, individuals and axioms are explicitly defined. Shared: knowledge representations are shared by a community. Conceptualization: abstract model of a part of the world that we want to represent.

Ontologies provide a common semantics. This means that all individuals and concepts involved can be explicitly defined in terms of their relationships and attributes. Ontologies are interpreted by a machine, so make an automatic system is much easier. This facilitates and improves the quality of diagnosis and the process of decision support. Also, ontologies share knowledge between several people, so they can work together without any ambiguity or loss of information.

Analyze knowledge about a domain is possible when specifying the terms of the domain is made. Formal analysis of terms is extremely valuable when we want to reuse existing ontologies, or when we want to extend an ontology.

The construction of ontology is through consensus, it represents the shared understanding of a group or community, instead, as is the case in most systems, based on a meaning given by a few individuals, to which all must adjust.

The definition of ontology is oriented by the use, as understood by a group or community to serve their needs directly. That differs from a system that, at best, can be thought of depending on users. Also, ontologies provide a model of high level abstraction of daily workflow; this model can be adapted to each organization. In other words, any organization can have an ontology adapted to its particular situation.

Allowing the reuse of knowledge in a domain was one of the major reasons of research on ontologies in recent years. For example, models of several areas needed to represent the notion of time. This representation includes the notions of time intervals, specific moments in time, on time measurements …etc. When a group of researchers develops such an ontology in detail, other groups can simply reuse it for their own ontology. Moreover, if it is necessary to build a larger ontology, it is possible to integrate several existing ontologies describing portions of a domain. We can also reuse a general ontology and expand it to allow describing a specific domain of interest. All this, due ontologies are very easy to maintain and with very minimal cost.

Especially in the medical field, there are a lot of classification like WHO Classifications of diseases and drugs (www.who.int), going from theses classification, we can construct domain ontologies and used them in our system in the field of cardiology. There are also a lot of medical ontologies constructed by other systems that we can integrate directly in our system.

Ontologies can be classified along several dimensions. Among these, we focus on the typology based on the object of conceptualization; ontologies can be classified as follows:

• Top level ontology [START_REF] Sowa | Top-level ontological categories[END_REF], this type of ontology is the most generic and describes very general concepts or common sense knowledge such as space, time, event, action, etc. These concepts are independent of a problem or a particular domain; • Domain ontology [START_REF] Mizoguchi | Construction and Deployment of a Plant Ontology[END_REF], this ontology governs a set of vocabularies and concepts describing an application domain or the target world. Most existing ontologies are domain ontologies; • Task ontology [START_REF] Mizoguchi | Construction and Deployment of a Plant Ontology[END_REF], this type of ontology is used to conceptualize specific tasks in systems. It governs a set of vocabularies and concepts describing a structure of performing the tasks domain-independent; • Application ontology [START_REF] Maedche | Ontology Learning for the Semantic Web[END_REF], this ontology is the most specific. The concepts in the application ontology are very domain specific and particular application.

V. E-CARE PLATFORM E-care project is a telemonitoring system for patient with heart failure. Actually they account for France about 1 million patients with heart failure with more than 120,000 new cases per year.

E-care scheme (Fig 1), use medical and environmental sensors to take measures then transmit them via the Internet to a central server. The central server processes these measures within the patient profile and sends alerts to physicians if dangerous situations are detected. E-care architecture is based on ontologies for knowledge representation and a decision support system for detecting dangerous situations. We use two types of ontologies, one task ontology and several domain ontologies.

The task ontology is central to the system. It describes the patient profile and how measures, alerts and data can be associated to a patient. It describes also all users of the system (physician, nurse, administrator ...etc.), their tasks and how they operate together. It contains also definition of all used equipment (sensors, tablets ...etc.).

The task ontology is generic and extensible, so we can integrate other domain ontologies that can add semantic to our system. These ontologies provide a controlled vocabulary, as for diseases, symptoms and medications. These ontologies can provide a language for sharing and communicating between different actors in the system. With the semantics of these ontologies, our system can interact easily with other systems or integrate other systems like auscultations system. Thus, data and information processed are generic and can be introduced into other systems.

Fig 2: Exemple of integration of domain ontology

There are different manners to build a domain ontology, depending on the available resources. In the medical domain, there are a lot of classifications and ontologies in the literature, for example we can use WHO classifications: International Classification of Diseases (ICD) and Anatomical Therapeutic Chemical Classification System (ATC/DDD). This makes the task of building ontologies much easier, rather than from a plain text.

Task ontology and domain ontologies are described and formalized by knowledge engineers and medical experts to meet their need. The W3C recommends OWL (Web Ontology Language) to build ontologies, and using tools like "Protégé" (protege.stanford.edu), this becomes very simple.

The E-Care platform is based on a decision support system that detects anomalies and changes in patient's health status. It is based on an inference engine that uses facts base and inference rules. Facts base is composed of the task ontology that contain all patient data, and domain ontologies.

Inference rules should be as generic as possible, and must evolve with the patient's state. Medical experts define these rules and can change them over time. Then knowledge engineers construct theme in a formal language compliant with the description of ontologies like SWRL.

Inference must lead to provide recommendations to the patient if necessary. If anomalies are detected, the system sends alerts to the physician. Inferred data can help physicians to diagnose the patient by providing information concerning the evolution of his health.

VI. PCG ANALYSIS MODULE

Advanced methods and techniques of signal processing and artificial intelligence will be applied to extract relevant features from the heart sound after the acquisition of the PCG signal. The heart sounds are non-stationary by nature. The classic Fourier transform analyzes the frequency content of signal without any time information. Therefore, the importance of time-frequency transforms (Fig 3) to detect the frequency changes of signal over time and to extract pertinent features form the heart sound. These features will then be transmitted to a central server in order to be integrated in the global ontology (Fig 4).

One of the first and most important phases in the analysis of heart sounds, is the segmentation of heart sounds which is part of the feature extraction block. Heart sound segmentation partitions the PCG signals into cardiac cycles and further into S1 (first heart sound), systole, S2 (second heart sound) and diastole. Identification of the two phases of the cardiac cycle and of the heart sounds with robust differentiation between S1 and S2 even in the presence of additional heart sounds (S3 or S4) and/or murmurs is a first step in this challenge. Then there is a need to measure accurately S1 and S2 allowing the progression to automatic diagnosis of heart murmurs with the distinction of ejection and regurgitation murmurs.

Features, such as the temporal localization of the heart sounds, the duration of the first and the second heart sounds could be extracted directly after the segmentation process. Then, the number of internal components of the first and second heart sounds, their frequency content, and the significance of diastolic and systolic murmurs, could also be studied and extracted directly from the PCG signal. Performing a robust segmentation method enable to perform a targeted feature extraction phase at each segmented part.

After the acquisition part, we will present briefly the proposed segmentation algorithm integrated in the E-care project.

A. Acquisition

Several factors affect the quality of the acquired signal, above all, the type of the electronic stethoscope, its mode of use, the patient's position during auscultation, and the surrounding noise. In the E-care project we use the Littman electronic stethoscope produced by 3M Corporation, with a Bluetooth connection to transmit sounds in real time. The sounds are recorded with 16 bits accuracy and 8000Hz sampling frequency in a wave format. At first, the original signal is decimated by factor 4 from 8000 Hz to 2000 Hz sampling frequency and then the signal is filtered by a high-pass filter with cut-off frequency of 30 Hz. The filtered signal is refiltered in the reverse direction so that there is no time delay in the resulting signal. Then, the Normalization is applied by setting the variance of the signal to a value of 1. The resulting signal is expressed by:

( ) ( ) ( ) ( ) max xt xt xt = (1)

B. Segmentation of heart sounds

The SSE method [START_REF] Moukadem | A Robust Heart Sound Segmentation based on S-Transform[END_REF] is used to segment the heart sounds. The SSE method is a time-frequency based method where the Stockwell transform (S-transform) is used [START_REF] Stockwell | Localization of the complex spectrum: the S-transform[END_REF]; it uses the S-matrix and it calculates the Shannon Energy (SE) of the local spectrum calculated by the S-transform for each sample of the signal x(t). Then, the extracted envelope is smoothed by applying an average filter (Fig 5).

Fig 5: Block Diagram of SSE Method

The S-transform of a time series x(t) is defined as [START_REF] Stockwell | Localization of the complex spectrum: the S-transform[END_REF]:

2 (, ) () ( ) ift S f x t w t e dt π τ τ ∞ - -∞ =-∫ (2)
Where the window function () wt τis chosen as:

1 (, ) ()2 t f wt f e f σ σπ - = (3)
And s(f) is a function of frequency as:

1 () f f σ = (4)
The proposed method calculates the Shannon energy of each the local spectrum in order to extract the envelope of the signal (Fig 6). The SSE envelope can be given as:

VII. INTEGRATION INTO E-CARE ONTOLOGY

To integrate the PCG Analysis Module into E-care platform, we have to represent collected data in the E-care Ontology. In other words, we represent a PCG signal in an ontological language going from its markers and attributes extracted by the PCG Analysis Module and validated by the expert (cardiologist). After the representation, relationships with other concepts of the E-care ontology are added; like a patient may have multiples PCG signals, and a PCG signal is specific to one patient.

Another important part of integration is the definition of inference rules concerning PCG signals, and rules combining PCG signals and other type of measurements (blood pressure, weight, temperature, blood oxygen saturation, etc.) or patient profile. Domain ontologies on PCG signals and auscultation sounds can be integrated to add semantic, so we can work in a collaborative manner with the cardiologists, and share information without ambiguities. We can integrate existing ontologies, or construct ontologies going from classifications or at worst from medical reports. To construct a domain ontology, we have to gather terms and concepts on PCG signals, then we give definition to each concept; finally, work on the semantics of these terms by seeking relationships that may exist between them. [START_REF] Sovijarvi | Definition of terms for applications of respiratory sounds[END_REF] have attempted to collect definitions of terms relating to respiratory sounds and have arrived at a collection of 162 terms commonly used in the «Computer Respiratory Sound Analysis» (CORSA). Nevertheless, it still doesn't allow physician to have a common definition of terms that are used.

VIII. CONCLUSION

In this paper we present the E-care project, a telemonitoring system for patients with heart failure.

E-care platform relies on the use of different ontologies; one task ontology to manage the system, and several domain ontologies to add semantic and sharable vocabulary in the medical field. This platform is based also on a decision support system to detect dangerous situations. The decision support system is based on an inference engine that needs both ontologies as knowledge base, and inference rules on these ontologies validated by the cardiologist. By adding other fields of knowledge, our system will be more reliable. Because that gives decision support system more information about patient's health state, so the taken decision is more precise and specific.

In this paper we present a PCG Analysis Module. This module, based on time-frequency domain, analyzes PCG signals and generates pertinent features. The PCG features are then integrated in the E-care task ontology. After that, inference rules and domain ontologies on PCG signals are added, if necessary.

Our perspective is to add other systems that provide other knowledge and complete the patient's profile.

Fig 1 :

 1 Fig 1: E-care project architectureSolutions and systems found in the literature use only a part of the knowledge on the patient, which makes their decision support system not very accurate. The representation of knowledge plays an important role in a system of telemonitoring, in these systems, some do not use ontologies, and use old technology that makes the task of detecting alerts very complex and knowledge sharing almost impossible.E-care architecture is based on ontologies for knowledge representation and a decision support system for detecting dangerous situations. We use two types of ontologies, one task ontology and several domain ontologies.The task ontology is central to the system. It describes the patient profile and how measures, alerts and data can be associated to a patient. It describes also all users of the system (physician, nurse, administrator ...etc.), their tasks and how they operate together. It contains also definition of all used equipment (sensors, tablets ...etc.).The task ontology is generic and extensible, so we can integrate other domain ontologies that can add semantic to our system. These ontologies provide a controlled vocabulary, as for diseases, symptoms and medications. These ontologies can provide a language for sharing and communicating between different actors in the system. With the semantics of these ontologies, our system can interact easily with other systems or integrate other systems like auscultations system. Thus, data and information processed are generic and can be introduced into other systems.

Fig 4 :

 4 Fig 4: The PCG module to be integrated in E-care project.

Fig 3 :

 3 Fig 3: The S-transform (bottom) of a normal heart sounds (top).

Fig 6 :

 6 Fig 6: The SSE envelope for a normal heart sound.

Fig 7 :

 7 Fig 7: Segmentation module applied on normal heart sound (top) and pathological heart sound (bottom).

1,2 , Ali MOUKADEM 3 , Alain DIETERLEN 3 , Amir HAJJAM 1 , Samy TALHA 4 and Emmanuel ANDRES 4 1Irtes, Université de Technologie Belfort Montbéliard,90010 Belfort, France. 2Newel, 36 rue Paul Cezanne, 68200 Mulhouse, France. 3MIPS Laboratory, University of Haute Alsace, 61 rue Albert Camus, 68093 Mulhouse, France 4Hôpital Civil, 1 place de l'hôpital, 67000 Strasbourg, France amine.ahmed-benyahia@utbm.fr, ali.moukadem@uha.fr

2