François Khosravani

Nicot

R Wan

S Khosravani

F Nicot

Micromechanical analysis of

INTRODUCTION

Unsaturated soils represent an important three-phase system in which internal forces arise from the interaction of solid, liquid and gas phases. As such, in determining the behaviour and strength of unsaturated soils, it becomes difficult to choose the controlling stress variable that would substitute for the role of effective stress in the saturated case. [START_REF] Bishop | The principle of effective stress[END_REF] extended Terzaghi's effective stress principle to account for the presence of an air phase by intuitively introducing an average pore fluid pressure weighted over the pore air ( a u ) and water ( w u ) pressures, i.e.

[ ]

' ( 1 ) = ( ) ( ) w a a a w u u u u u σ σ χ χ σ χ = - + - - + - (1)
where σ and ' σ are the total and effective stresses respectively, and χ is the weighted parameter that is arbitrarily confounded with the degree of saturation, r S . Here, soil mechanics sign convention is used, i.e. positive stresses mean compression. Understanding the suction stress as a function of the difference between air and water pressures, as well as its dependency on the degree of saturation is a longstanding problem both theoretically and experimentally.

The present paper examines the notion of stress and its definition for a three-phase system composed of idealized soil particles and pore water menisci through a micromechanical analysis. By considering air and water pressures, surface tension, as well as interparticle forces within an assembly of spherical particles, the (Cauchy) stress tensor can be readily calculated as a volume average of the various constituents (phases) just like in the case of a solid body consisting of interacting point masses in a volume [START_REF] Love | Theory of Elasticity[END_REF]. The proposed derivation ultimately leads to a tensorial effective stress equation which can be viewed as a generalized Bishop's equation explicitly written as a function of the spatial distribution of water menisci and an anisotropic tensor describing the distribution of pore fluid around particle surfaces, including the effect of the contractile skin. It is noteworthy that the same formulation can be reached based on the theory of energy and thermodynamics.

One of the implications of this generalized formulation is that the stress tensor formulation engenders a suction based shear effect even under isotropic loading, which is fundamental to the understanding of the strength behaviour of unsaturated soils. Furthermore, as a by-product of this micromechanical derivation, an analytical expression is obtained for the weighting parameter χ . By considering regular spherical particle assemblies such as in two-particle or multi-particle configurations with tetrahedral and cubical packings, together with changing the geometry of the pore water meniscus to mimic filling, the relationship between χ and degree of saturation can be computed explicitly. The variation of χ as a material parameter with the degree of saturation on both water meniscus and particle packing is discussed in the light of experimental data already available for different types of soils. The work constitutes a rational approach within which the role of capillary forces and their distributions can be accounted for through the microscale physics that governs the state of stress in an unsaturated soil and its macroscopic engineering properties.

STRESS DERIVATION IN A THREE-PHASE SYSTEM

The stress tensor in a representative elementary volume (REV) comprising an ensemble of interacting solid particles in the presence of a water and air phase can be generally written as a volume average of each individual phase stress over the total volume V, i.e.

1 1 p w a N ij ij ij w ij a ij V V V V dV dV u u V V V V σ σ σ δ δ < >= = + + ∑ ∫ ∫ (2)
where , , , V p a w α α = represent solid particle, water and air phase volume respectively, N the number of particles, and ij δ the Kronecker delta. In Eq. ( 2), the stress in the water and air phases have been considered to be hydrostatic and equal to w u and a u respectively. As a result, the last two terms on the right in Eq. ( 2) simply refer to the partial pressures due to air and water phases with their respective volume fractions applied to each individual pressure.

Next, suppose the above system is idealized as an ensemble of mono-disperse spherical particles of radius R joined by independent concave liquid bridges with negligible interparticle contact area. Since we are primarily interested in the transport of forces in the REV, we will focus on the first term on the right in Eq. (2) related to particle interactions. Applying Gauss' divergence theorem to the latter term for the case of static and weightless media, the following so-called granular stress tensor is obtained:

1 1 p p N N ij g ij i j V dV x t d V V σ σ Γ < > = = Γ ∑ ∑ ∫ ∫ (3)
where p Γ is the surface of a particle, i x the spatial position of points on p Γ at which various surface tractions j t act. Among the various surface tractions exerted on an individual particle, we will find contributions from pair-wise particle contact forces due to external loading, actions of air and water pressures on dry ( p d Γ ) and wetted ( p w Γ ) surfaces respectively, and surface tension arising from air/water/solid interfaces formed by water menisci along contour m Γ as illustrated in Fig. 1.

Figure 1 Free body diagram for analysis of interparticle forces Furthermore, noting that

c i i i x x Rn = +
, where c i x is the position vector of the particle centroid, and considering equilibrium of forces on the closed surface of each particle, we finally get:

. 1

p p w m d N N N L N L a w ij g j i j i j i j i u R u R R f l nn d nn d Tn d V < > = + Γ + Γ - Γ ∑ ∑ ∑∑ ∑∑ ∫ ∫ ∫ (5)
where j n is the normal to the particle surface, j f αβ is the mutual contact force between particle pair α and β , i l αβ the so-called branch vector defining to the separation distance between the same two particles, j T the surface tension forces per unit length related to water menisci action on m Γ formed by the intersection of the water meniscus with the particle's surface, L the number of liquid bridges, p w Γ is the part of the particle wetted by the liquid bridge, whereas p d Γ is the union of all dry parts of the particle's surface (see Fig. 1).

Interestingly, the air/water interface at the particle's surface, seen as a contractile skin, allows the REV to withstand tensile stresses.

It should be noted that the decomposition of surface tractions as laid out in Fig. 1 and which enters Eq. ( 5) leads to the well-known result that capillary forces arising from a concave liquid bridge between two spherical particles have two sources. The first source comes from the pressure difference between air and water described by the Young-Laplace equation, whereas the second source originates from the surface tension force acting on the boundary of the wetted area on the particle surfaces where solid, air and water coexist (e.g. see [START_REF] Megias-Alguacil | Capillary forces between two solid spheres linked by a concave liquid bridge: regions of existence and forces mapping[END_REF].

The tensor moment of force, defined by the first term to the right of Eq. ( 5) as a dyadic product between f and l , is easily identified as the effective stress tensor ij σ ′ used in the fully saturated case. Therefore, further rearrangement of Eq. ( 5) and substitution into Eq. ( 2) finally leads to the form of a generalized Terzaghi's effective stress relation:

( ) ( ) ( ) g w m N L N L ij ij a ij a w r ij a w j i j i R R u u u S u u nnd Tnd V V σ σ δ φ δ Γ Γ ′ = - + - + - Γ+ Γ ∑∑ ∑∑ ∫ ∫ (6)
in which φ is the porosity, r S is the degree of saturation, whereas the last two terms relate to distributional descriptions of liquid bridges (menisci) and contractile skin effects respectively as surface integrals of dyadic products of contact normals and surface tension forces as illustrated in Fig. 2. These integrals over each pair of particles can be readily calculated and as their contributions are assembled over the entire REV, we get the following general relationships distinguishing isotropic from deviatoric components: 2 (

) and sin ( ) 3

p w m N L N L j i ij ij j i ij ij R n n d A T n d R B π ωδ πγ α ϖδ Γ Γ Γ = + Γ = + ∑∑ ∑∑ ∫ ∫ (7)
in which γ is the surface tension, ij A and ij B are deviatoric so-called fabric tensors with respect to liquid bridge arrangements, whereas ω and ϖ are parameters corresponding to their isotropic part respectively. Finally, substituting Eq. ( 7) into (6) and after rearranging leads to some form of equation that is recognizable as a generalized Bishop's equation, i.e.

( ) ( ) ij ij a ij a w ij ij ij u u u G σ σ δ χ δ κδ ′ = - + - + + (8)
where

V R V R S G u u A B V V V V π π χ φ ω κ γϖ α γ α = + = = - + (9)
in which α is the filling angle attached to a water meniscus.

As discussed earlier, the current derivation inherently accounts for capillary forces that arise from the pressure difference between air and water, and surface tension force acting on the wetted surface on the surface of grains, i.e. the contractile skin. Therefore, referring to Eq. ( 9), the term κ refers to the isotropic part of the distribution of surface tension forces with its anisotropic (deviatoric) part represented by the second term of the tensor G . It turns out that the latter term is of second order (since 2 / R V γ is small) relative to the first term of G which describes the anisotropic distribution of capillary forces due to pressure difference between air and water. In other words, the effect of capillary forces in unsaturated soils is mostly controlled by the contribution due to air-water pressure difference. Accordingly, Eq. ( 8) can be simply written as

( ) ( ) , with ( ) 4 p ij ij a ij a w ij ij ij a w ij V u u u G G u u A V σ σ δ χ δ ′ = - + - + = - (10)
The micromechanically derived Eq. ( 8) shows that the effective stress in unsaturated soil is governed by not only two independent state variables: net normal stress ( )

ij a ij u σ δ
and matric suction ( )

a w u u -
including a material variable χ as in [START_REF] Bishop | The principle of effective stress[END_REF], but also by distributions of contractile skin surface tension and matric suction. Since the latter distribution can be anisotropic depending on liquid bridge spatial distribution and particle packing, effective stresses can also be affected by deviatoric loading. Turning to Eq. ( 9), the derived effective stress parameter χ emerges as a function of degree of saturation as well as distributional quantities such as particle packing and number of meniscus per unit volume of REV. This will be investigated in the next section as to the capturing of the dependency of χ on the degree of saturation and other parameters.

EFFECTIVE STRESS COEFFICIENT FOR SIMPLE PACKINGS

The effective stress parameter χ , as a function of degree of water saturation r S , is theoretically evaluated for two limiting cases, namely simple cubic (SC) simple packing (loosest state) and tetrahedral (TH) packing (densest state) in idealized soil comprised of mono-sized spherical particles. Figures 2a,b show simple cubic and tetrahedral packing geometries respectively with liquid bridges between each pair of particles. The water meniscus is assumed to be a surface of revolution with constant curvature and circular in section so as to form a toroid. In all subsequent calculations, a small wetting angle ( 0.5 ) θ = °is chosen to maximize the filled volume of menisci and hence achieve high degrees of saturation in the pendular regime. The effect of contact angle could be explored, but this is not the focus of this paper.

Calculation of χ

Referring back to Eqs. ( 6) & ( 7), the effective stress parameter χ emerges as the isotropic part of the integral giving the distribution of liquid bridges. For each meniscus connecting a pair of particles, we readily compute the fabric tensor as

1 2 3 2 2 1 2 2 0 0 = 0 0 ; 2(1 cos ) and (1 cos ) (2 cos ) 3 0 0 p w ij j i R F n nd λ π λ λ α λ α α λ Γ ⎡ ⎤ ⎢ ⎥ = Γ = - = - + ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ∫ (11)
According to Eq.( 11), ij F is a symmetric tensor with its first invariant, ( ) ij trace δ F , being independent of the rotation of the coordinate system. Thus, referring to Eq. ( 7) and summing contributions of the fabric tensors over all liquid bridges on all particles, and then taking into account the isotropic part of the resultant tensor we finally find

1 2 = 2 ( 2 ) / 3 L ω λ λ
+ for different packings. Furthermore, noting Eq. ( 9), the explicit expression of the effective stress parameter for different packings of spherical particles can be thus derived, i.e.

3 1 2 1 2 2 ( 2 ) (1 ) ( 2 ) 9 6 r r R L S L S V N π χ φ λ λ φ φ λ λ = + + = + - + (12)
which depends on the filling angle α , among others.

Using a toroidal meniscus geometry, the volume of the liquid bridge between two contacting spherical particles can be readily calculated based on α at equilibrium conditions during saturation, see [START_REF] Megias-Alguacil | Capillary forces between two solid spheres linked by a concave liquid bridge: regions of existence and forces mapping[END_REF]. Therefore, χ as given in Eq.

(12) can be readily calculated as a function of r S . The maximum degree of saturation is reached whenever the filling angle reaches its maximum and the curvature of the meniscus decreases to a minimum so that the toroid degenerates into a cylinder. For example for a packing of two particles, this would give a value of 28% r S = . Furthermore, the maximum degree of saturation for SC and TH cases can be reached without any of the liquid bridges overlapping, which can be readily calculated based on the maximum filling angle. Table 1. summarizes the results for the these packings.

DISCUSSIONS AND CONCLUSIONS

Figure 4 shows the computed effective stress values as a function of degree of saturation with the line r S χ = also plotted here as a reference. All simulations produce a curve that plots above the r S χ = line showing a perceptible bend with a break in slope at some characteristic degree of saturation when the water meniscus reaches its maximum filling angle max α .

Subsequent filling would then proceed at fixed wetting points on the particle while the curvature of the meniscus (dotted lines in Fig. 2) continues to decrease towards reaching a larger water volume.

The simulations reveal that both packing and the number of liquid bridges influence the shape of the vs. r S χ curve. For instance, the tetrahedral packing gives much lower χ values than those associated with the simple cubic packing for the same degree of saturation. Also, as one would expect for the same packing with decreasing number of liquid bridges, lower values of χ are predicted for the same degree of saturation because of a decrease in overall suction. We recall that overall suction depends on χ as is evident in Eq. ( 10) or in Bishop's original equation.

Experimental data for various types of soils are shown in Fig. 5 for comparison with the numerical results of Fig. 4. It should be noted that the range of degree of saturation, examined in the numerical computations based on idealized mono-sized spheres, is well below 30% since the menisci are not allowed to merge to give full saturation. The restriction of the packing to rather simple configurations with mono-sized spherical particles could plausibly account for the difference between experimental and computed data. This matter will require a more detailed investigation. At any rate, it is also not evident that the experimental data in the range of small degree of saturation investigated (less than 30%) is accurate and reliable, given known difficulties in measuring low suction in soils.

The theory developed in this paper is being extended to poly-disperse and non-spherical particles, which should give more realistic vs. r S χ curves. Given the limited experimental data for low to extremely low suctions on soils, discrete element simulations is an alternative means for exploring, among other things, the validity of the proposed theory. Another interesting outcome of this work arising from Eq. ( 10) is that the contribution of the matric suction to the effective stress is by no means isotropic, but is generally anisotropic as dictated by the spatial distribution of liquid bridges and fabric of the solid skeleton during deformation history. It is thought that this issue becomes particularly relevant in the pendular regime where material instabilities in the form of skeleton collapse are common. (ref). Indeed, discrete element numerical simulations may be of great value for elucidating volume changes in unsaturated soils as a result of increase or decrease in water saturation and also for formulating constitutive models for unsaturated soils. (After Bishop, 1961?)

Figure 2 .

 2 Figure 2. Geometry of meniscus and surface tension forces for a pair of spherical particles

Figure 2 .

 2 Figure 2. Loosest and densest packings with interconnecting water menisci

Figure 4 .

 4 Figure 4. Computed relationship between degree of saturation Sr and effective stress parameter χ

Table 1 .

 1 Expressions of χ for various packings

	Packing	Porosity φ	μ =	/ L N	χ													Maximum α	Maximum r S
	A pair of particles	0.4764	1/2=0.5	φ	S	r	+	2 π 9 V R	3	(	1 λ	+	2 2 ) λ	90°	28%
	Tetrahedral (TH)	0.1285	6/4=1.5	φ	S	r	+	6	⎛ ⎜ ⎝	2 π 9 V R	3	⎞ ⎠ ⎟	(	1 λ	+	2 2 ) λ	30°	25%
	Simple Cubic (SC)	0.4764	12/8=1.5	φ	S	r	+	12	⎛ ⎜ ⎝	2 π 9 V R	3		⎞ ⎠ ⎟	(	1 λ	+	2 2 ) λ	45°	17%

V V V αβ αβ αβ σ Γ Γ Γ

Second International Symposium on Computational Geomechanics (ComGeo II), 27/04/2011, Cavtat-Dubrovnik, HRV

ACKNOWLEDGEMENTS

The first two authors are grateful to funding provided by the Natural Science and Engineering Science Research Council and Computer Modelling Foundation. The third author is grateful for funding provided by the CEMAGREF in the form of a research visit fellowship to Calgary in summer 2010.


Guillaume Cerutti

Laure Tougne

Antoine Vacavant

Didier Coquin

A Parametric Active Polygon for Leaf Segmentation and Shape Estimation

In this paper we present a system for tree leaf segmentation in natural images that combines a first, unrefined segmentation step, with an estimation of descriptors depicting the general shape of a simple leaf. It is based on a light polygonal model, built to represent most of the leaf shapes, that will be deformed to fit the leaf in the image. Avoiding some classic obstacles of active contour models, this approach gives promising results, even on complex natural photographs, and constitutes a solid basis for a leaf recognition process.

Introduction

Over the past years of progress and urbanization, the world of plants has lost the part it formerly had in our everyday life, and the names and uses of the many trees, flowers and herbs that surround us now constitute a knowledge accessible only to botanists. But nowadays, with the rising awareness that plant resources and diversity ought to be treasured, the will to regain some touch with nature never felt so present. And what better tool to achieve this than the ubiquitous mobile technology, that has the opportunity of placing a flora book in everyones pocket? Botanists traditionally rely on the aspect and composition of fruits, flowers and leaves to identify species. But in the context of a widespread nonspecialist-oriented application, the predominant use of leaves, which are possible to find almost all year long, simple to photograph, and easier to analyze, is the most sensible and widely used approach in image processing. Considering the shape of a leaf is then the obvious choice to try to recognize the species. Starting by tree leaves which are the easiest to spot, our goal is to build a system to retrieve relevant geometric criteria to classify a leaf, in a photograph taken by a smartphone camera.

In this paper we present a method to achieve a first part of this process, estimating the general shape of a leaf that will guide the segmentation process. In Section 2 we present the related publications. Section 3 expounds the model used to represent the general shape of a leaf, and Section 4 the so-called parametric active polygon segmentation algorithm we use. In Section 5, we show how this system could be used for leaf shape classification. Section 6 relates the results of experiments.

Related work

Plant recognition has recently been a subject of interest for various works. Few of them though consider acquiring images of leaves or flowers in a complex, natural environment, thus eluding most of the hard task of segmentation.

Plant recognition and segmentation

Nilsback and Zisserman [START_REF] Nilsback | Delving into the whorl of flower segmentation[END_REF] adressed the problem of segmenting flowers in natural scenes, by using a geometric model, and classifying them over a large number of classes. Saitoh and Kaneko [START_REF] Saitoh | Automatic recognition of blooming flowers[END_REF] focus also on flowers, but in images with hard constraints on out-of-focus background. Such approaches are convenient for flowers, but lose much of their efficiency with leaves.

Many works on plant leaf recognition tend to avoid the problem by using a plain sheet of paper to make the segmentation easy as pie. Their recognition systems are then based on either statistical or geometric features : Centroid-Contour Distance (CCD) curve [START_REF] Wang | Leaf image retrieval with shape features[END_REF], moments [START_REF] Wang | Classification of plant leaf images with complicated background[END_REF][START_REF] Wang | Leaf image retrieval with shape features[END_REF], histogram of gradients, or SIFT points [START_REF] Nilsback | Delving into the whorl of flower segmentation[END_REF]. Some more advanced statistical descriptors, such as the Inner Distance Shape Context [START_REF] Belhumeur | Searching the world's herbaria: A system for visual identication of plant species[END_REF], or the Curvature Scale Space representation [START_REF] Mokhtarian | Matching shapes with self-intersections: Application to leaf classification[END_REF] that allows taking self-intersections into account, have also been applied to the context of leaf classification, while developed in a general purpose.

As a matter of fact, isolating green leaves in an overall not less green environment seems like a much tougher issue, and only some authors have designed algorithms to overcome the difficulties posed by a natural background. Teng, Kuo and Chen [START_REF] Teng | Leaf segmentation, its 3d position estimation and leaf classification from a few images with very close viewpoints[END_REF] used 3D points reconstruction from several different images to perform a 2D/3D joint segmentation using 3D distances and color similarity. Wang [START_REF] Wang | Classification of plant leaf images with complicated background[END_REF] performed an automatic marker-based watershed segmentation, after a first thresholding-erosion process. All these approaches are complex methods that seem hardly reachable for a mobile application. In the case of weed leaves, highly constrained deformable templates have been used [START_REF] Manh | Weed leaf image segmentation by deformable templates[END_REF] to segment one single species, providing good results even with occlusions and overlaps.

Active contour models

The concept of active contours, or snakes, have been introduced by Kass, Witkin and Terzopulos [START_REF] Kass | Snakes: Active contour models[END_REF] as a way to solve problems of edge detection. They are splines that adjust to the contours in the image by minimizing an energy functional. This energy is classically composed of two terms, an internal energy term considering the regularity and smoothness of the desired contour, and an external or image energy accounting for its adequation with the actual features in the image, based on the intensity gradient.

To detect objects that are not well defined by gradient, Chan and Vese [START_REF] Chan | Active contours without edges[END_REF] for instance based the evolution of their active contour on the color consistency of the regions, using a level set formulation. Another region-based approach, relying this time on texture information, was proposed by Unal, Yezzi and Krim [START_REF] Unal | Information-theoretic active polygons for unsupervised texture segmentation[END_REF] who also introduced a polygonal representation of the contour.

But to include some knowledge about complex objects, a deformable template [START_REF] Yuille | Feature extraction from faces using deformable templates[END_REF] can be used, with the asset of lightening the representation and storage space of the contour by the use of parameters. Felzenszwalb [START_REF] Felzenszwalb | Representation and detection of deformable shapes[END_REF] represents shapes by deformable triangulated polygons to detect precisely described objects, including maple leaves, and Cremers [START_REF] Cremers | Diffusion snakes: introducing statistical shape knowledge into the mumford-shah functional[END_REF] includes shape priors into level set active contours to segment a known object, but both approaches lack the flexibility needed to include knowledge about the shape of any possible leaf. In our case, the similarity between the background and the object of interest, and the difficulty to avoid adjacent and overlapping leaves constitute a prohibitive obstacle to the use of unconstrained active contours (Figure 1). The idea of using a template to represent the leaves is complicated by the fact that there is much more variety in shapes than for eyes or mouths. The only solution to overcome the aforementioned problems is however to take advantage of the prior knowledge we may have on leaf shapes to design a very flexible time-efficient model to represent leaves.

A polygonal model for simple tree leaves

Despite the large variety in leaf shapes, even when considering only the trees, it is necessary to come up with some kind of template that can rather accurately be fitted to basically any kind of leaf. We considered in a first time only trees with simple, non-palmate leaves, which represent about 80% of French broad-leaved tree species [START_REF] Coste | Flore descriptive et illustrée de la France de la Corse et des contrées limitrophes[END_REF] and roughly the same proportion in all European species.

Describing botanic leaf shapes

Botanists have a specialized vocabulary to describe leaf shapes, among which around 15 terms are used to characterize the global shape of a leaf. Examples of such shapes are diplayed in Figure 2. The interesting point is that these terms are also the ones used in flora books to describe the lobes of palmate leaves and the leaflets of compounded leaves, making them the base element to describe all the leaf shapes. Knowing this general shape is a key component of the process of identifying a leaf, though non sufficient. However, given the high variability within a single species, floras often reference a species with two or three leaf shapes, making this notion overall blurry. This impression is reinforced by the difficulties in seeing where exactly a denomination ends and the other one begins.

It is yet possible to derive a basic model to sketch all the shapes used in botany. The idea is then to use a light polygonal model, suitable for a time and space effective mobile implementation. It is only assumed to have a vertical axis of symmetry joining the base and the tip, and from this, by playing on a set of parameters, one should be able to describe the whole set of shape types.

This kind of representation has two main advantages. First the parameters that define the construction of the model can later be directly used as descriptors for the leaf, and using such representation in segmenting leaves is a way to create a cooperation between the two classically unconnected processes of segmentation and feature extraction. Additonally, working on numeric values allows us to slightly reduce the uncertainty produced by the hard classification into not-welldefined botanical terms of natural objects, which intrinsically bear a part of variability.

The parametric polygonal leaf template

The chosen model relies on two points, base B and tip T , that define the main axis of the leaf. From this axis, we construct the 10 points defining the polygon, using 4 numeric integer parameters :

α B , the opening angle at the base α T , the opening angle at the tip w, the relative maximal width p, the relative position where this width is reached

The model is then built as follows. In the next steps, we will call a the direction vector of the line segment [BT ], n its normal vector, and h its length, so that -→ BT = h.a. The construction of the model is illustrated in Figure 3.

----→ C l C lB = -(1 -2|p -0.5|) h 5 .
a, and the same is done for the right tangent. 3. At the tip and at the base, we build two isosceles triangles, with a top angle respectively of α T and α B and with equal sides of fixed length relatively to the height. This creates 6 additional points T l , T r and T T for the tip and B l , B r and B B for the base. The points at the tip are defined by

--→ T T l = h 5 sin α T 2 .n, --→ T T r = -h 5 sin α T 2 .n and --→ T T T = h 5 cos α T 2 .
a and the points at the base are defined identically. 4. Finally, the polygon is obtained by linking the 10 points

B B , B l , C l B , C l T , T l , T T , T r , C r T , C r B and B r .
This model proves to cover, with a very restraint set of parameters, the major part of the shapes used by botanists to describe leaves. It is then possible to adjust the parameters to recreate models that visibly correspond to most of the archetypal leaf shapes, as depicts Figure 4. Other parameters could have been added to account for deformations that occur in real images, but it would have compromised the lightness of the model. As mentioned earlier, using a deformable template approach based on this model has the advantage of encapsulating some prior knowledge on the shape of the object in the very definition of the model. It is also a great benefit in terms of computation time to have a parametric representation, as there will be only a few elementary deformations, making the exploration of the possible variations easier.

Elementary deformations

The values that can be changed to deform the model are very few since the considered polygon is entirely defined by the indication of the 2 points defining the main axis and the 4 integer parameters. Consequently, a given model will have only 16 neighbours in the model space, corresponding to a variation in one direction or the other of a parameter (8 deformations) and the move of a point to one of its neighbours in the image in the sense of 4-connectivity (8 deformations).

This results in a very limited set of elementary variations to be considered when deforming the model, compared with a classic active contour that can be moved pointwise locally.

Representing the color

The polygonal model being an approximation of a shape, we can not expect it to fit edges in the image. That is why we use a region-based approach, using color information inside the region rather than gradient information on its contour. But formulating an a priori model for color, that would be accurate whatever the leaf, season and lighting is likely an impossible task.

It is therefore an absolute necessity to learn the particular model for the leaf we want to segment from the image. And this can obviously only be achieved with some constraints on the position of the leaf, that will allow us to know where to evaluate a color model. In the following, we assume that the leaf is roughly centered and vertically-oriented, so that an initialization of our template in the middle of the image contains almost only leaf pixels. Typically, a leaf in the image taken on purpose by a user will be large enough to ensure the correctness of the initialization.

We considered then that the color of a leaf can be modelled by a 2-component GMM estimated in the initial region, accounting for shaded and lighted or shiny areas, and defined by the parameters (µ 1 , σ 2 1 , α 1 ) and (µ 2 , σ 2 2 , α 2 ), respectively the mean, variance and weight of each gaussian distribution. Then the distance of a pixel x to the color model, in a 3-dimensional colorspace, is defined by a Mahalanobis 1-norm distance, considering the variance matrices are diagonal, written as following :

d(x, µ 1,2 , σ 1 , µ 2 , σ 2 ) = min g=1,2 3 i=1 |xi-µg,i| σg,i
Based on this formulation, we can compute for every pixel in the image its distance to the color model, resulting in a distance map, where leaf pixels should appear in black and background pixels in gray-white. Based on the aspect of this map for different leaves and different color spaces, we chose to work in the Lab colorspace, for which leaves were standing out best in distance maps.

Energy functional

The internal energy term that classically appears in the energy formulation can be considered as implicit here, as it is included in the construction rules of our model, giving it already some kind of rigidity. The remaining term is the external energy, representing the image forces, and it will be based on the distance map discussed above, as we ultimately want the final polygon to contain only pixels with as small distance to the leaf color model as possible. The energy the model strives to minimize throughout its evolution is then expressed as :

E(M ) = x∈M (d(x, µ 1 , σ 1 , µ 2 , σ 2 ) -d max ) (1)
The value d max actually represents a balloon force, that will push the model to grow as much as possible. It can also be seen as a threshold, the distance to the color model for which a pixel will be costly to add into the polygon. The expected outcome is to produce the biggest region with as little color-distant pixels as possible.

At each step, the algorithm will then select, among the 16 possible elementary variations, the one that leads to the most important decrease of the energy, until no deformation can bring it any lower. As such, this method has the major drawback of getting stuck in local energy minima, that most certainly do not correspond to the searched leaf. To get around this problem, we use a heuristic close to simulated annealing.

Evolution constraints

Even if the polygonal template models quite accurately most of the leaf shapes, it has the unwanted counterpart of being slightly too flexible, and thus able to model shapes that are not likely to ever be reached by leaves. This has negative consequences when the model is let to evolve freely, at will undergo any possible deformation to minimize its energy, often resulting in unnatural, yet surprising, optimal shapes.

It is necessary then to constraint the evolution of the template to make sure it keeps an acceptable leaf shape. To achieve this, the model is forced to have its parameters within an authorized range. This range have been learned by manually adjusting the model to leaves from a database5 . A template can then be told as leaf or non-leaf by estimating its distance to the empiric leafmodel in the parameter space. Only the variations that give a leaf template are then examinated in the evolution process, ensuring the final polygon will show a satisfactory shape. The Figure 5 shows sample results of the whole process.

Shape Classification

To measure with more accuracy the performance of our approach, we use the parameters returned by the algorithm as descriptors to estimate the global leaf shape. It is important to keep in mind though that the final goal is to recognize a plant species, and that the numeric parameter values convey more information than a rigid classification into rather unclear terms. These constitute actually global descriptors that will later be combined with local geometric features and other heteregenous data such as date or GPS coordinates to recognize species. This shape classification step will consequently not even be a middle step in our process, but it appeared as the best way to evaluate the behaviour of our algorithm.

Learning leaf shapes

The first step is to learn the different classes of leaf shapes and the parameter values they correspond to. As discussed earlier, the problem is that the botanic classification is a very subjective and uncertain work, the boundaries between classes being vaguely defined, and a tree species impossible to associate with a single class. It is then judicious to let an almost unsupervised learning algorithm determine the best classification, based of the set of parameters manually extracted from the leaf database 5 . This is simply performed by a k-Means clustering algorithm that classifies points in the parameters space, and returns k classes, each one represented by its centroid and its variance for each parameter. The value of k that produced the best, visibly identifiable, models was k = 10. The clustering was however guided by initializing the centroids on hand-designed leaf shape archetypes, but was then left free to evolve. This way, we obtain ten canonical models, displayed in Figure 6 that can later be labeled by the name of the botanic class(es) they match best.

k-Means classification

The model resulting from the parametric active polygon algorithm can then be compared to each of the class centroids, by computing a 1-norm distance in the parameters space. As illustrated in Figure 7 the model is labeled with the closest

* M -M k 1 < β. min k M -M k 1 (β > 1).
It is actually frequent that the shape of a leaf can not be assigned to one class only, even by an experimented botanist. Returning often 2 canonical shapes as a classification result is therefore not strictly speaking approximative, but rather complying with a natural reality.

Experiments & Results

Experimental procedure

Tests were performed on two databases : a white-background leaf database6 and a set of natural scene leaf images, centered and rotated to fit the desired conditions. Unfortunately, we have not yet collected images from smartphone cameras, taken by users from a prototypal interface, which would correspond best to the images the algorithm was designed to work on.

Each image is then set to roughly the same size and the model launched on it, to estimate the shape of the leaf. A ground-truth class labeling was first performed by a group of about 15 specialists and non-specialists provided with the images and the 10 class models. Each image was then associated with one or two ordered classes depending on the votes of the labelers, and the classification in turn responds with one or two classes.

Performance measure

Measuring the accuracy of such answers, consisting most of the time in an ordered pair of classes to be compared with an other ordered pair, is not a common problem, and there does not seem to be a standard procedure to do so. We tried however to build simply a confusion matrix estimating how fitting the answer is.

If the first actual class is present among the two predicted ones, 2 points are placed on the corresponding diagonal cell. If the second actual class is present, 1 point is placed on the corresponding diagonal cell, and if the first class was not recognized, 1 point is placed on the cell from the line of the first class, in the column of the other recognized class. And finally, if none on the classes are present, 1 point is placed on each of the cells from the lines corresponding to the actual classes, in the columns corresponding to the predicted classes. The points are then normalized to have their total equal to 1.

Table 1. Confusion matrix for 99 white background images M0 M1 M2 M3 M4 M5 M6 M7 M8 M9 M0 100 0 0 0 0 0 0 0 0 0 M1 6 93 0 0 0 0 0 0 0 0 M2 0 0 92 5 0 0 0 0 0 2 M3 0 0 1 94 0 0 0 2 0 2 M4 0 0 0 0 100 0 0 0 0 0 M5 0 0 3 0 0 96 0 0 0 0 M6 0 0 0 0 0 0 93 0 3 3 M7 0 0 0 0 0 0 0 100 0 0 M8 0 0 3 0 0 0 3 0 92 0 M9 0 0 0 0 0 0 0 4 0 95 In the case of white background images (Table 1) the model shows a very good classification rate, and recognizes one of the classes in almost every case. Some classes already seem hard to discriminate like the M2 (Ovate) and the M3 (Elliptic) as it is a problem even for humans when to say ovate or elliptic. Another tendency is to label Cordate (M8) some Triangular leaves (M6). This may come from the very definition of the polygonal model that has difficulties fitting exactly round shapes, and sometimes, a heart-shaped base allows it to get closer to the actual border of a triangular leaf. This issue results in a wrong classification but remains close to the truth in terms in terms of segmentation.

For natural images (Table 2) the overall performance is obviously lower, but remains acceptable. The main problem is the variability of the color inside the leaf, factor that does not exist on white background images thanks to uniform controlled lighting. This often leads the model to segment accurately part of the leaf but not to enter in the areas that are too far from the color model, resulting in a bad classication though the segmentation result would still be exploitable. The same tendencies appear, notably the difficulty to discriminate between Elliptic and Ovate, Ovate and Triangular, or Triangular and Orbicular (M9).

Comparison with standard active contours

The main advantage our model proves to have over a regular snake algorithm based on the same energy term is that it is not sensitive to overflowing. The hard constraints contained in the definition and the evolution of the model impose that it remains in an acceptable shape and forbids any attemps of exploring unwanted regions. This is a guarantee that the final shape will not have outgrown out of the leaf in some places, and is a substantial condition for the robustness of the rest of the process.

It will also be more robust with respect to holes or spots inside the leaf that will not change the shape as much as it would with a contour that could go around them. Such irregularities are smoothed by the fact that we consider a whole region of fixed shape.

Conclusions

We have presented a method to perform a first segmentation of a leaf in a natural scene, based on the optimization of a polygonal leaf model whose parameters constitute also a first set of descriptors with an eye to species identification. The model is flexible and covers most of the simple tree leaf shapes, and is a good base for the segmentation of lobed and compound leaves. It is however rigid enough to avoid classic problems of active contour approaches, that allow for instance overflows to adjacent similar regions, and make use of a color model that is robust to uncontrolled lighting conditions.

Improvements are to be considered. In some cases, relying only on color information does not seem to be the best choice ; the model could benefit from the use of an additional texture model of the leaf. As for the color model, 2 gaussians may not be enough to represent the diversity of the colors in a single leaf. A model with an adaptive number of gaussians is a possible enhancement.

The next step is then to refine the contour of the obtained polygon to fit the actual contour of the leaf in the image. The idea would be to use an active contour this time, constraining it to remain within a certain distance to the polygon. With a more accurate segmentation, we will be able to extract the local geometric features that characterize leaves, and to begin classifying leaf images into species. The model should also be extended to take into account lobed and compound tree leaves, and even non-tree leaves, and be tested over images from smartphone cameras.

Nevertheless, it constitutes as such a good approach to estimate the shape of a leaf in a natural environment, without performing a thorough segmentation, and to associate the corresponding terms used by botanists to describe leaves.

Fig. 1 .

 1 Fig. 1. Segmentation issues with classic region-based active contour model

Fig. 2 .

 2 Fig. 2. Examples of leaf shapes used by botanists : Lanceolate, Ovate, Oblong, Obovate, Cordate and Spatulate. Images taken from [15].

Fig. 3 .

 3 Fig. 3. Building the leaf model in 4 steps

Fig. 4 .

 4 Fig. 4. Main leaf shapes and their corresponding hand-tuned models

Fig. 5 .

 5 Fig. 5. Initialization, distance map and resulting polygon on two natural images

Fig. 6 .Fig. 7 .

 67 Fig. 6. The 10 models representing the classes of leaf shapes used for classification

Fig. 8 .

 8 Fig.8. Comparison between our polygonal model and standard active contour[START_REF] Mille | Narrow band region-based active contours and surfaces for 2d and 3d segmentation[END_REF]

Table 2 .

 2 Confusion matrix for 113 natural scene images

LEAF -Tree Leaf Database, Inst. of Information Theory and Automation ASCR, Prague, Czech Republic, http://zoi.utia.cas.cz/tree_leaves

Database collected by P.-Y. Landouer on his website http://www.lesarbres.fr

This work has been supported by the French National Agency for Research with the reference ANR-10-CORD-005 (REVES project).


Guillaume Cerutti

Laure Tougne

Julien Mille

Antoine Vacavant
email: antoine.vacavant@iut.u-clermont1.fr

Didier Coquin
email: didier.coquin@univ-savoie.fr

Guiding Active Contours for Tree Leaf Segmentation and Identification

In the process of tree identification from pictures of leaves in a natural background, retrieving an accurate contour is a challenging and crucial issue. In this paper we introduce a method designed to deal with the obstacles raised by such complex images, for simple and lobed tree leaves. A first segmentation step based on a light polygonal leaf model is first performed, and later used to guide the evolution of an active contour. Combining global shape descriptors given by the polygonal model with local curvature-based features, the leaves are then classified over nearly 50 tree species.

Introduction

In our everyday more urbanized and artificial world, the knowledge of plants, that used to constitute our most immediate environment, has somehow been lost, except for a handful of specialists. What is allegedly seen as unquestionable progress also scattered away the names and uses of so many trees, flowers and herbs. But nowadays, with a certain resurgence of the idea that plant resources and diversity ought to be treasured, the will to regain some touch with nature feels more and more tangible. And making it possible, for whoever feels the need, to identify a plant species, to learn its history and properties, is as much a way to transmit a vanished knowledge, as to allow people to get a glance at nature's unfathomable richness.

The identification of species is the first and essential key to understand the plant environment. Botanists traditionally rely on the aspect and composition of fruits, flowers and leaves to identify species. But in the context of a widespread non-specialist-oriented application, the predominant use of leaves, which are possible to find almost all year long, simple to photograph, and easier to analyze from two-dimensional images, is the most sensible and widely used approach in image processing. Considering the shape of a leaf is then the obvious choice to try to recognize the species. Our system intends then to classify a photograph of a leaf, which should be roughly centered and vertically-oriented as shown in Figure 1, over around 50 different tree species.

In this paper we present a method to classify simple and lobed leaves, using a polygonal modeling of leaf shapes and geometric botany-inspired descriptors. In Section 2 we will present related publications. Section 3 expounds the first segmentation step using a parametric active polygon, and Section 4 the refinement leading to the actual segmentation. The process of classification is then detailed in Section 5 and Section 6 relates the results of experiments both on white-background leaf images and natural scenes.

Related work

Plant recognition has recently been a subject of interest for various works. Few of them though consider acquiring images of leaves or flowers in a complex, natural environment, thus eluding most of the hard task of segmentation.

Nilsback and Zisserman [START_REF] Nilsback | Delving into the whorl of flower segmentation[END_REF] adressed the problem of segmenting flowers in natural scenes, by using a geometric model, and classifying them over a large number of classes. Saitoh and Kaneko [START_REF] Saitoh | Automatic recognition of blooming flowers[END_REF] focus also on flowers, but in images with hard constraints on out-of-focus background. Such approaches are convenient for flowers, but lose much of their efficiency with leaves.

Many works on plant leaf recognition tend to avoid the problem by using a plain sheet of paper to make the segmentation easy as pie. Their recognition systems are then based on either statistical or geometric features: Centroid-Contour Distance (CCD) curve [START_REF] Wang | Leaf image retrieval with shape features[END_REF], moments [START_REF] Wang | Classification of plant leaf images with complicated background[END_REF][START_REF] Wang | Leaf image retrieval with shape features[END_REF], histogram of gradients, or SIFT points [START_REF] Nilsback | Delving into the whorl of flower segmentation[END_REF]. Some more advanced statistical descriptors, such as the Inner Distance Shape Context [START_REF] Belhumeur | Searching the world's herbaria: A system for visual identication of plant species[END_REF], or the Curvature Scale Space representation [START_REF] Mokhtarian | Matching shapes with self-intersections: Application to leaf classification[END_REF] that allows taking self-intersections into account, have also been applied to the context of leaf classification, while developed in a general purpose.

As a matter of fact, isolating green leaves in an overall not less green environment seems like a much tougher issue, and only some authors have designed algorithms to overcome the difficulties posed by a natural background. Teng, Kuo and Chen [START_REF] Teng | Leaf segmentation, its 3d position estimation and leaf classification from a few images with very close viewpoints[END_REF] used 3D points reconstruction from several different images to perform a 2D/3D joint segmentation using 3D distances and color similarity. Wang [START_REF] Wang | Classification of plant leaf images with complicated background[END_REF] performed an automatic marker-based watershed segmentation, after a first thresholding-erosion process. All these approaches are complex methods that seem hardly reachable for a mobile application. In the case of weed leaves, highly constrained deformable templates have been used [START_REF] Manh | Weed leaf image segmentation by deformable templates[END_REF] to segment one single species, providing good results even with occlusions and overlaps.

The concept of active contours, or snakes, have been introduced by Kass, Witkin and Terzopulos [START_REF] Kass | Snakes: Active contour models[END_REF] as a way to solve problems of edge detection. They are splines that adjust to the contours in the image by minimizing an energy functional. This energy is classically composed of two terms, an internal energy term considering the regularity and smoothness of the desired contour, and an external or image energy accounting for its adequation with the actual features in the image, based on the intensity gradient.

To detect objects that are not well defined by gradient, Chan and Vese [START_REF] Chan | Active contours without edges[END_REF] for instance based the evolution of their active contour on the color consistency of the regions, by using a level set formulation. Another region-based approach, relying this time on texture information, was proposed by Unal, Yezzi and Krim [START_REF] Unal | Information-theoretic active polygons for unsupervised texture segmentation[END_REF] who also introduced a polygonal representation of the contour.

But to include some knowledge about complex objects, a deformable template [START_REF] Yuille | Feature extraction from faces using deformable templates[END_REF] can be used, with the asset of lightening the representation and storage space of the contour by the use of parameters. Felzenszwalb [START_REF] Felzenszwalb | Representation and detection of deformable shapes[END_REF] represents shapes by deformable triangulated polygons to detect precisely described objects, including maple leaves, and Cremers [START_REF] Cremers | Diffusion snakes: introducing statistical shape knowledge into the mumford-shah functional[END_REF] includes shape priors into level set active contours to segment a known object, but both approaches lack the flexibility needed to include knowledge about the shape of any possible leaf. In our case, the similarity between the background and the object of interest, and the difficulty to avoid adjacent and overlapping leaves constitute a prohibitive obstacle to the use of unconstrained active contours (Figure 1). The idea of using a template to represent the leaves is complicated by the fact that there is much more variety in shapes than for eyes or mouths. The only solution to overcome the aforementioned problems is however to take advantage of the prior knowledge we may have on leaf shapes to design a very flexible time-efficient model to represent leaves.

Parametric Polygonal Leaf Model

Even when considering trees only, leaves show an impressively wide variety in shapes. It is however necessary to come up with a representation of what a leaf is, that is accurate enough to be fitted to basically any kind of leaf. In a first time, we consider only simple leaves, including lobed and palmate ones, which covers already 90% of French broad-leaved tree species [START_REF] Coste | Flore descriptive et illustrée de la France de la Corse et des contrées limitrophes[END_REF] and roughly the same proportion in all European species.

A polygon to describe leaf shapes

The general shape of a leaf is a key component of the process of identifying a leaf. Botanists have a whole set of terms describing either the shape of a simple leaf, of the lobes of a palmate leaf, or of the leaflets of a compound leaf. Examples of such shapes are diplayed in Figure 3. The problem being that the borders between the different terms are not well defined, since leaves can naturally have non-canonical, intermediate shapes.

To sketch the shapes used in botany, we propose a light polygonal model based on a set of 4 parameters [START_REF] Cerutti | A parametric active polygon for leaf segmentation and shape estimation[END_REF] The idea of defining a simple parametric model to represent all these various shapes has the double advantage of turning an imprecise, blurry and quite subjective classification into numerical parameter values, and producing in the same time some descriptors accounting for the general shape of the leaf.

The chosen model relies on two points, base B and tip T , that define the main symmetry axis of the leaf. From this axis, we construct the 10 points defining the polygon, as displayed in Figure 2, using 4 numeric integer parameters:

α B , the opening angle at the base α T , the opening angle at the tip w, the relative maximal width p, the relative position where this width is reached This model is then able to cover correctly, with a very concise set of parameters, almost every shape used in botany. Figure 3 illustrates how, by changing manually the values of the parameters, it is possible to create shapes that visibly correspond to the different canonical shapes.

Fig. 3. Main leaf shapes and their corresponding hand-tuned models

The case of palmately lobed leaves is slightly more complex, but our hypothesis is that a palmate leaf can be seen as a superposition of several identical simple leaf shapes, joining at the base of the leaf. This is justified by the descriptions that can be found in flora books, where palmate leaves are characterized by the shape of their lobes using the same previously mentioned terms.

Concretely, we model a palmate leaf by overlaying an odd number of simple polygonal models, symmetrically arranged in pairs, and varying only in length and angle: a main lobe whose axis is defined by the points B and T , and several symmetric pairs of secondary lobes, whose axes all radiate from the actual base of the main lobe, the point B B . Such representation implies the addition of a number of new parameters to make the construction represented in Figure 4 possible. In addition to the 4 parameters determining the shape of the lobes, we have to introduce:

n L , the number of pairs of lobes (1 means simple, 2 means 3-lobed)

for each pair of lobes, L(l), the relative length of the two symmetric lobes for each pair of lobes, α(l), the angle of the lobes with the main axis

Fig. 4. Construction of the palmately lobed leaf model

The idea is then to apply a deformable template approach on this model, using the variations of the different parameters as elementary deformations, to make it fit best the leaf in the image. This has the major advantage of encapsulating some prior knowledge on the shape of the object, in the very definition of the model. The final polygon we obtain can later be used as a shape prior for a refined segmentation.

Color representation

A polygonal model inevitably being an approximation of the actual contour of the leaf, it is not relevant to base its evolution on the edge information, contained in the gradient. This is why we use only the color information to make the model fit the leaf in the image.

It is however impossible to come up with an a priori model for what the color of a leaf is, that would be accurate whatever the leaf, season and lighting. It is then absolutely necessary to estimate, for each new leaf we want to segment, the particular color model, which can only be performed with some rough idea of where the leaf lies in the image, implying constraints on its position. In the following, we assume that the leaf is roughly centered and vertically-oriented, so that an initialization of our template in the middle of the image contains almost only leaf pixels. Typically, a leaf in the image taken on purpose by a user will be large enough to ensure the correctness of the initialization.

We considered then that the color of a leaf can be modelled by a 2-component GMM estimated in the initial region, accounting for shaded and lighted or shiny areas, and defined by the parameters (µ 1 , σ 2 1 , α 1 ) and (µ 2 , σ 2 2 , α 2 ), respectively the mean, variance and weight of each gaussian distribution. Then the distance of a pixel x to the color model, in a 3-dimensional colorspace, is defined by a normalized 1-norm distance, written as following:

d(x, µ 1,2 , σ 1 , µ 2 , σ 2 ) = min g=1,2 3 i=1 |x i -µ g,i | σ g,i (1)
Based on this formulation, we can compute for every pixel in the image its distance to the color model, resulting in a map that measures the dissimilarity of pixels to the leaf, and where leaf pixels should appear in black and background pixels in gray-white. Based on the aspect of this map for different leaves and different color spaces, we chose to work in the L*a*b* colorspace, for which leaves were standing out best in distance maps.

Parametric Active Polygon

With an iterative process similar to active contours, the initial model will undergo a series of deformations, whose goal is to minimize an energy functional based on the afore described leaf dissimilarity map. The internal energy term that traditionnally appears in the energy formulation can be considered as implicit here, as it is included in the construction rules of our model. The remaining external term is then expressed as:

E(Ω) = x∈Ω (d(x, µ 1 , σ 1 , µ 2 , σ 2 ) -d max ) (2)
The value d max actually represents a balloon force, that will push the model to grow as much as possible. It can also be seen as a threshold, the distance to the color model for which a pixel will be costly to add into the polygon. The expected outcome is to produce the biggest region with as little leaf-dissimilar pixels as possible.

At each step, all the possible elementary variations of the parameters and of the base and tip points are examined, and the one leading to the greatest decrease of the energy is applied, until no deformation can bring it any lower. As such, this method presents the risk of getting stuck in local energy minima, this is why a heuristic close to simulated annealing is used. It is also necessary to constrain the model, that is basically flexible enough to take shapes that are not likely to ever be reached by leaves. To achieve that, actual leaf shapes were learned, and at every moment, the model has to remain within a certain distance to one of these reference shapes.

Collapsing lobes

The only parameter that has to be treated separately is the number of lobes n L . Considering it on the same level as the other parameters does not make much sense, given the drastic changes in shape a modification of its value would induce. A way to solve the problem could have been to estimate in a preliminary step the number of lobes, and have this parameter fixed for the evolution of the model. But such an estimation, that would ultimately require some equivalent of a segmentation to be accurate, would just seem like going round in circles.

The method we kept treats the number of lobes in the same optimization process that fits the model to the leaf, but in a different way. After the color model has been estimated on the simple polygonal initalization shown in Figure 5 an excessive number of lobes is added to the model, typically resulting in a 11lobed leaf model. The deformable template algorithm runs then freely on all the parameters, except for the number of lobes. The expected result is that lobes will group together inside the actual lobes of the leaf. The key is then to eliminate the overlapping lobes until there remains only as many lobes as necessary.

This elimination step is performed between two temperature rises in the simulated annealing process. For each secondary pair of lobes, we evaluate an overlapping ratio with the previous one, expressed as:

r(l) = w 2 .L(l -1) sin(θ) . 1 L(l)
. cos(θ)

where θ = α(l) -α(l -1). Figure 6 illustrates the origin of this formula where polygonal models are approximated by rectangles. This value can be seen as the ratio between the blue area (estimating the overlapped part of the considered lobe) and the whole lobe, weighed by a cosinus to favour more large angles between lobes. The actual result is the ratio between the lengths of the two red lines.

Fig. 6. Estimating the overlapping ratio between two lobes

Lobes that have a overlapping ratio greater than a given threshold (typically, 70%) are eliminated. In addition, a second pass is performed to ensure that the remaining lobes have a plausible repartition, which could correspond to a leaf. If a lobe makes a naturally unlikely angle with its predecessor (typically, more than 60 degrees) it is suppressed too. The result is that the perceived number of lobes will emerge from the very process that approximates the leaf by a model (as in Figure 7) and this even for the case of simple leaves, where all the lobes should eventually collapse into one.

Fig. 7. Sample result of lobe suppression, before suppression and after evolution

The resulting model gives a good clue of what the shape of the leaf is, but it is not enough to carry out species identification, and the first resulting contour has to be later enhanced to hug the boundary of the leaf.

As initially mentioned, unconstrained active contours applied to the complex natural images we aim at dealing with would produce unsatisfying contours, that would try and make their way through every possible gap and flaw in the border of the leaf. The solution we propose is to use the polygonal model obtained after the first step not only as an initial leaf contour but also as a shape prior that will guide its evolution towards the real leaf boundary.

Energy formulation

We chose to use the active contour model defined by Kass et al. [START_REF] Kass | Snakes: Active contour models[END_REF], including a guiding constraint and using leaf dissimilarity, both under the form of additional terms in the energy functional the contour strives to minimize. The general energy term, for a contour Γ delineating a region Ω(Γ ), can be expressed as:

E(Γ ) = αE Leaf (Γ )+βE Shape (Γ )+γE Gradient (Γ )+δE Smooth (Γ )-ωE Balloon (Γ ) (4
) Instead of having an external energy term based on color consistency, or distance to a mean, we decided to reuse the dissimilarity map from the previous step, considering we have already an efficient measure of how well a pixel should fit in the leaf, in terms of color. The corresponding energy term is then based on the dissimilarity function d detailed in Section 3 and can be written as:

E Leaf (Γ ) = Ω(Γ ) d(x, µ 1 , σ 1 , µ 2 , σ 2 )dx
The guiding constraint term relies on a so-called stencil function K Shape increasing with the distance to the polygonal contour Π, which is explicited in 4.2. It guarantees that contour points that are distant from the polygon that will be pushed back towards it, when neither the color nor the gradient would be strong enough to retain it. It has then the following form:

E Shape (Γ ) = Γ K Shape (Γ (s), Π)ds
However this is obviously not enough, and the contribution of the gradient computed on the image I is here essential, as it may allow the contour to stick to the actual boundaries of the leaf (which is ultimately the main objective) even when the color information would not be relevant enough. The gradient energy is expressed in order to penalize curve points located on pixels with low gradient magnitude and is simply formulated as:

E Gradient (Γ ) = Γ -∇I(Γ (s)) ds
Although the final contour has to be precise, to capture points and teeth on the leaf margin essentially, some moderate smoothing is still necessary to prevent the contour from being too noisy. And finally the balloon energy is here to counterbalance and stabilize the other energies by adding a constant force towards the outside of the contour:

E Smooth (Γ ) = Γ dΓ ds 2 ds E Balloon (Γ ) = Ω(Γ ) dx
The final variation of E is determined using calculus of variations, and the resulting evolution equation is implemented on a parametric curve following [START_REF] Mille | Narrow band region-based active contours and surfaces for 2d and 3d segmentation[END_REF].

Guided by a stencil

The function we use is asymmetric with respect to the polygonal contour Π, as shown in Figure 8. The reason is that, our basic energy already using a balloon force, we want the force pushing the contour to the polygon to be stronger on the outside of the polygon, where it has to compete with the balloon, than on the inside, where the two resulting forces will push towards the same direction. We also introduce a margin ∆ around the polygon where the contour should be free to evolve, i.e. where the shape energy is equal to 0. For a given pixel, located at a distance d from the polygonal contour, the cost function is then:

k(d) = max(d -∆, 0
) on the inside of the polygon max((d -∆) 2 , 0) on the outside of the polygon (5)

A small improvement to this basic formulation is a slight elongation of the polygonal contour at the base and the tip of the leaf before the evaluation of the distance, resulting in the two round black areas on the map of Figure 8. This is justified by the fact that the shape of the leaf in these areas is really discriminant, and the contour absolutely has to be able to reach such determinant parts of the leaf. Since the polygonal model is by definition not well suited to account for local particular shapes, the contour needs a larger freedom around those crucial points.

Ebb and flow

As such however, the various energies, though having all their role to play, are hard to harmonize into a coherent whole, efficient regardless of the image. Some of them may have conflicting interactions, the leaf dissimilarity term impeding for instance that the contour reaches the edge where the gradient term would make it stay. This is the reason why, rather than trying to find the optimal way of making those disparate forces cooperate smoothly, we decided to split the process into two phases where each will be able to express freely.

Starting from a contracted version of the polygon, to try to make sure that most of the points are located inside the leaf, the contour will undergo a first expansion step, where the coefficients of the balloon and gradient are preeminent, and the margin ∆ is rather tolerant. The contour should swell with no concern for the color, sometimes getting outside of the leaf, but constrained to be blocked when it crosses strong gradients or when it gets quite far from the reference polygon.

Fig. 9. Initial polygon, contour after expansion, and final contour after contraction

The second phase has for purpose to bring back the contour from non-leaf areas where it might have wandered, with at the same time hanging on to the strong edges and not going back inside the leaf even when the dissimilarity would claim so. The coefficient of the leaf dissimilarity energy is this time very high while the balloon is reduced and enough gradient preserved to stick to the boundary of the leaf. The distance map to the polygon is recomputed with a smaller ∆, again in this perspective of shrinking the contour to the leaf and no further. Those two steps and the final contour we obtain are illustrated in Figure 9.

Geometric Features and Classification

Our purpose is then to classify new leaf images into one of the 50 species of non-compound-leaved trees of the ImageCLEF Plant Images Classification task database [START_REF] Goau | The clef 2011 plant images classification task[END_REF]. We made the choice of basing our classification on explicit morphological descriptors inspired by those used by botanists. These geometric criteria are those used to build the determination keys that have proved some skills when it comes to helping with species identification.

Global shape features

As stated earlier, the global shape of a leaf is one of the most relevant characteristics for its identification, even if it has to be completed by local details. We already presented a way of dealing with global shape features, by means of the parametric polygonal described in 3.1. As a matter of fact, the parameters resulting from the final evolution of polygon can directly be used as descriptors accounting for the global shape of the leaf, since it is actually the very purpose they were designed for.

Among them, we chose to keep only those who appeared to be the most discriminating ones: the four simple shape parameters w, p, α B and α T , and the two lobe parameters for the first pair of secondary lobes L(1) and α(1), these two being respectively set to 100 and 0 when the number of lobes is 1.

Contour characterization

The margin of the leaf is also a very important feature to spot. Its shape can be determining when trying to discriminate two species that have more or less the same global shape. It may consist of teeth of various sizes and frequencies, regularly arranged or not, from large spiny points, to small regular saw-like teeth, or even to a smooth entire border.

In order to cover these numerous possibilities, we based our contour descriptors by a measure of the curvature, using the osculating circle method [START_REF] Vacavant | A framework for dynamic implicit curve approximation by an irregular discrete approach[END_REF][START_REF] Hermann | A comparative study on 2d curvature estimators[END_REF] estimated at 1, 3, 5, and 10 points, for each point of the contour. Then we simply computed the means and variances of the resulting vectors, and used those 8 values to characterize how large and how regular the teeth of the margin are.

There is however a lot more to do to measure this crucial feature accurately, and if the descriptors we use are visibly performing satisfyingly, they are still very correlated, and do not account efficiently for the regularity of the teeth, or for doubly serrated leaves. Such basic measures also fail in representing the local shape at the base and the tip of the leaf, which are both essential elements for species identification.

Normalized classification

The learning base was built by extracting the aforementioned descriptors on 2101 white-background images of non-compound leaves of the ImageCLEF training database. Once computed, the base was normalized by adjusting all the values for each parameter, in order that their mean becomes 0 and their variance 1. Then for the k-th species among the 50 we treat, the specific mean and variance of each parameter are computed resulting in a model Φ k = (µ k , σ k ) representing the species.

For a new image, the parameters extracted during and after the segmentation form a feature vector φ that has to be compared with every of the 50 species models. For each one of them we compute a normalized Euclidean distance in the parameters space, with the only particularity that the features are weighted differently, by a constant coefficient denoted by w i for the i-th feature. The formulation of the distance is then:

d(φ, Φ k ) = i w i (φ(i)-µ k (i)) 2 σ k (i) 2
The species corresponding to the model Φ * achieving the smallest distance is the one that is picked if we have to give one single answer. But when multiple answers are possible, we associate them with a confidence score, measuring how probable the species are. The only species that are to be displayed in a final list are the ones with a confidence score not equal to zero. If we designate by Φ * * the model corresponding to the second best distance, our recipe of a confidence measure is given by: C

(φ, Φ k ) = max 1 - d(φ,Φ k ) d(φ,Φ * )+d(φ,Φ * * ) , 0
Our final classification result presents a list of species, in decreasing order with respect to the confidence we allow to each species.

Results

Segmentation results

To measure the accuracy of our segmentation process, we compare the binary mask representing the final contour with a hand-made binary segmentation of the same image. Segmentations were hand-performed on more than 200 photographs of the ImageCLEF Database [START_REF] Goau | The clef 2011 plant images classification task[END_REF]

Scan and pseudoscan images

As said previously, the training of our classifier was performed on these easier plain-background images. We used cross-validation during the learning base, by using 30% of the base as a testing base to get a reliable performance measure. Our typical classification scores for scan and pseudoscan images over 50 classes lie around 70% on the training base and 67% on the testing base, with respectively 97% and 94% of presence of the real class in the 5 first answers.

On the plant identification task proposed for ImageCLEF 2011 [START_REF] Goau | The clef 2011 plant images classification task[END_REF] our method achieved a classification score of 53.8 ± 0.8% on scan images and 52.6 ± 1.8% on scan-like images.

Natural background images

When using the same classifier for the photograph images of the training base, that contained only 26 of the 50 species, we reach only a score of 29%, with the good answer being in the top 5 species in 63% of cases. This can of course be explained by the fact that returning one of 50 possible classes when there are actually only 26 increases the risk of making bad choices.

There is also the fact that we use the plain-background images as our reference, considering that the contours we obtained on these easier cases would be more trustworthy. However, by making this choice, we prevent our system from learning the defaults it may have on more complicated images, and consequently adapting to them, making it extremely less robust to the noisy, sometimes inaccurate contours obtained on such difficult pictures.

On the ImageCLEF pland identification task, we performed a score of 18.7 ± 6.4 % on such natural scene photographs.

Conclusions and Perspectives

We have presented a method designed to perform the segmentation of a leaf in a natural scene, based on the optimization of a polygonal leaf model used as a shape prior for an exact active contour segmentation. It also provides a set of global geometric descriptors that, later combined with local curvature-based fatures extracted on the final contour, make the classification into tree species possible.

The segmentation process is based on a color model that is robust to uncontrolled lighting conditions. But a global color model for a whole image may sometimes not be enough, for leaves that are not well defined by color only. The use of an additional texture model, or of an adaptive color model could lead to a good improvement.

There is also a need for better local contour descriptors, always keeping in mind what years of botany have found to be the most discriminative places to look at. These descriptors would also have to be more robust to the change from white-background images to real natural scenes, or to little flaws in the contour natural objects inevitably carry.

Nevertheless, it constitutes already a promising way of dealing with images of leaves in a complex background, giving promising results in terms of segmentation correctness, and proposing interesting descriptors relying on the criteria used by botanists to discriminate leaves.

Fig. 1 .

 1 Fig. 1. Segmentation issues with unconstrained region-based active contours

Fig. 2 .

 2 Fig. 2. Building the simple leaf model in 4 steps

Fig. 5 .

 5 Fig. 5. Initialization, distance map and resulting polygon on two natural images

Fig. 8 .

 8 Fig. 8. Polygonal model, modified polygon, cost function, and stencil map

Fig. 10 .

 10 Fig. 10. Overlap curves for the polygonal model (dotted) and the final contour (plain) Figure 10 displays the results for 226 segmentations, showing for each overlapping factor value the percentage of images in the database for which this score is reached. Both the polygonal model (dotted line) and the active contour result (plain line) are presented. The results show a mean overlap of 80,3% for the polygonal model and 85,8% for the final contour, with an overlapping score of 80% being reached for more than 78% of the images in the database.

Acknowledgements

We would like to thank Hung Duong Viet for the work on leaf segmentation he performed during his Master internship.

This work has been supported by the French National Agency for Research with the reference ANR-10-CORD-005 (REVES project).