In the process of tree identi cation 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 rst segmentation step based on a light polygonal leaf model is rst 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 classi ed over nearly 50 tree species.
In our everyday more urbanized and arti cial 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, owers 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 identi cation of species is the rst and essential key to understand the plant environment. Botanists traditionally rely on the aspect and composition of fruits, owers 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 nd 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 ? This work has been supported by the French National Agency for Research with the reference ANR-10-CORD-005 (REVES project). 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 di erent 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 rst segmentation step using a parametric active polygon, and Section 4 the re nement leading to the actual segmentation. The process of classi cation is then detailed in Section 5 and Section 6 relates the results of experiments both on white-background leaf images and natural scenes. 2
Plant recognition has recently been a subject of interest for various works. Few of them though consider acquiring images of leaves or owers in a complex, natural environment, thus eluding most of the hard task of segmentation.
Nilsback and Zisserman [
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:
CentroidContour Distance (CCD) curve [
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 di culties posed by a natural background. Teng,
Kuo and Chen [
The concept of active contours, or snakes, have been introduced by Kass,
Witkin and Terzopulos [
To detect objects that are not well de ned by gradient, Chan and Vese [
But to include some knowledge about complex objects, a deformable
template [
In our case, the similarity between the background and the object of interest, and the di culty 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 exible time-e cient model to represent leaves. 3
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 tted to basically any kind of leaf. In a rst
time, we consider only simple leaves, including lobed and palmate ones, which
covers already 90% of French broad-leaved tree species [
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 lea ets of a compound leaf. Examples of such shapes are diplayed in Figure 3. The problem being that the borders between the di erent terms are not well de ned, 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 [
The chosen model relies on two points, base B and tip T , that de ne the main symmetry axis of the leaf. From this axis, we construct the 10 points de ning 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 di erent canonical shapes. 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 justi ed by the descriptions that can be found in ora 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 de ned 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 BB. 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: { nL, 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
The idea is then to apply a deformable template approach on this model, using the variations of the di erent parameters as elementary deformations, to make it t 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 de nition of the model. The nal polygon we obtain can later be used as a shape prior for a re ned segmentation. 3.2
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 t 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 de ned by the parameters ( 1; 12; 1) and ( 2; 22; 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 de ned by a normalized 1-norm distance, written as following: 3 X jxi g;ij i=1 g;i
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 di erent leaves and di erent color spaces, we chose to work in the L*a*b* colorspace, for which leaves were standing out best in distance maps.
d(x; 1;2; 1; 2; 2) = min g=1;2 (1) 3.3
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) dmax) (2) x2
The value dmax 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 exible 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. The only parameter that has to be treated separately is the number of lobes nL. Considering it on the same level as the other parameters does not make much sense, given the drastic changes in shape a modi cation 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 xed 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 ts the model to the leaf, but in a di erent 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) = w2 :L(l 1) : 1 : cos( ) (3)
sin( ) L(l) 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.
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.
The resulting model gives a good clue of what the shape of the leaf is, but it is not enough to carry out species identi cation, and the rst 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 aw in the border of the leaf. The solution we propose is to use the polygonal model obtained after the rst step not only as an initial leaf contour but also as a shape prior that will guide its evolution towards the real leaf boundary.
We chose to use the active contour model de ned by Kass et al. [
ELeaf ( ) = R ( ) d(x; 1; 1; 2; 2)dx The guiding constraint term relies on a so-called stencil function KShape 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:
EShape( ) = R
KShape( (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:
EGradient( ) = R krI( (s))kds Although the nal 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 nally the balloon energy is here to counterbalance and stabilize the other energies by adding a constant force towards the outside of the contour:
ESmooth( ) = R
d k ds k2 ds
EBalloon( ) = R ( ) dx
The nal variation of E is determined using calculus of variations, and the
resulting evolution equation is implemented on a parametric curve following [
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 justi ed 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 de nition not well suited to account for local particular shapes, the contour needs a larger freedom around those crucial points. If we call the extension of the original polygonal contour at the base and at the tip, the nal expression for our stencil function is: KShape(x; ) = k(d (x)) where d (x) = miny2 kx yk represents the Euclidean distance of a pixel to the contour . As such however, the various energies, though having all their role to play, are hard to harmonize into a coherent whole, e cient regardless of the image. Some of them may have con icting 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 nd 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 rst expansion step, where the coe cients 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.
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 coe cient 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 nal contour we obtain are illustrated in Figure 9. 5
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 Classi cation task
database[
As stated earlier, the global shape of a leaf is one of the most relevant characteristics for its identi cation, 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 nal 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 rst pair of secondary lobes L(1) and (1), these two being respectively set to 100 and 0 when the number of lobes is 1. 5.2
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 [
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 e ciently 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 identi cation. 5.3
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 speci c 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 di erently, by a constant coe cient denoted by wi for the i-th feature. The formulation of the distance is then: d( ; k) = qPi wi ( (i) k(ik)2(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 con dence score, measuring how probable the species are. The only species that are to be displayed in a nal list are the ones with a con dence score not equal to zero. If we designate by the model corresponding to the second best distance, our recipe of a con dence measure is given by: C( ; k) = max 1 d( ; d()+;d(k); ) ; 0
Our nal classi cation result presents a list of species, in decreasing order with respect to the con dence we allow to each species. 6.1
To measure the accuracy of our segmentation process, we compare the binary
mask representing the nal contour with a hand-made binary segmentation of
the same image. Segmentations were hand-performed on more than 200
photographs of the ImageCLEF Database[
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 nal contour, with an overlapping score of 80% being reached for more than 78% of the images in the database. As said previously, the training of our classi er 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 classi cation 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 rst answers.
On the plant identi cation task proposed for ImageCLEF 2011 [
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 di cult pictures.
On the ImageCLEF pland identi cation task, we performed a score of 18.7 6.4 % on such natural scene photographs. 7
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 nal contour, make the classi cation 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 de ned 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 aws 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.
We would like to thank Hung Duong Viet for the work on leaf segmentation he performed during his Master internship.