The leaves are one of the most important main sources used for plant identi cation. Because of this the ImageCLEF 2011 proposed a challenge based on leaf analysis for plant identi cation. This paper reports the experiment results of the IFSC/USP team in participating of this task. The main goal is investigate the performance of Complex Network method for feature extraction and classi cation of plant species. The achieved results are promising and can help the botanists in the future.
In the world is estimated that there are 400,000 species, of which only 270,000 have been named and identi ed by botanists. The Plant Taxonomy is the responsible science for survey of the fauna and your consequent classi cation. Although we have many researches in this eld, the taxonomy of species is still a hard task. One of reasons for this is the fact of the owers and fruits (the main sources used for diagnostic of characteristics) are not available for studies throughout the year, but only at certain times. Although available throughout most of the year, the leaves do not have su cient visible characteristics to di erentiate between many species. Methods of computer vision can help in this point. The main idea is extract more good characteristics of the leaves, using computer vision methods, than traditional manual inspection.
The ImageCLEF series use this idea and propose an ongoing campaign's on plant identi cation task. The main goal of this task is provide a forum for researchers that work on image analysis and arti cial intelligence methods, share ideas and compare their systems in order to help the taxonomic process with leaves information.
Our group, which has already been working on plant identi cation in recent
years, accepts this challenge. In this year we use a new method of shape analysis,
based on Complex Network theory [
The following Section 2 describes the materials and methods utilized. In Section 3, we explain the experiments and obtained results. Finally, conclusions are presented in Section 4. 2 2.1
The experiments are performed over Pl@antLeaves dataset [
Those images have uniform background but with some luminance variations, optical distortions, shadows and color derivations. 3. Free natural photos: contains 1469 photos taken directly on the trees. No acquisition protocol is used, which results in a non-uniform background, rotated and bad-scaled images, among others problems.
Each image has an xml le associated that contain the date, type (single leaf, single dead leaf or foliage), name of the author and GPS coordinates of the observation among others information. But we do not use any of this information in classi cation process. Just characteristics of the images are used to make our recognition system.
The full database is split in training and test dataset. The training dataset have 4004 images (2329 scans, 686 scan-like photos, 989 natural photos) and de test dataset have 1432 images (741 scans, 211 scan-like photos, 480 natural photos). 2.2
All images of both test and training dataset are rstly segmented. For Scan
and Scan-like photos a simple Otsu [
In sequence, we apply a contour detection method to extract only contour of leaves. We do not bother to treat open or imperfect contours, because the method of shape analysis that we will use is robust to such problems.
W =
W maxwij2W
A complete graph is obtained from this. So, relevant properties are extracted from the posterior transformation of this network using a set of thresholds T = ft1; t2; : : : ; tLg:
ATl 8w 2 W aij = 0; if wij tl aij = 1; if wij < tl
In this experiments we use T = f0:025; 0:050; 0:075; : : : ; 0:925g, totaling 13 thresholds (jT j = 13). We measure, for each threshold, the mean degree and maximum degree, given respectively by: 2.3
To apply the Complex Network method [
N i=1 k = max ki
i ki =
N X aij j=1 where the degree ki of a node i is the number of edges directly connected to node, and it is de ned in terms of the adjacency matrix A as:
An normalization of the vertices degree by the number of vertices in the network is necessary before computing these measurements. This normalization is performed in order to reduce the in uence of the network size in the computed descriptors, and it is performed as follows: wij = q (xi xj )2 + (yi yj )2
Therefore, the network G is represented by the N
normalized into the interval [0; 1],
N weight matrix W
(1)
(2)
(3)
(4)
(5)
(6)
The Fourier descriptors consist of the sum of the main components of the
normalized power spectrum. It was used here 40 frequencies. These frequencies are
then called Fourier descriptors and make up the feature vector x.
Functional Data Analysis (FDA) [
j (f ) j ;
The above transform turns possible the expression of the original data on the basis functions algebraic space. In this way, it becomes a richer analysis tool emphasizing the global relevant aspect of the original data. 3
With a single feature vector for each leaf we have chosen to use the Naive Bayes as classi er. In addition, we have used a 10-fold cross validation. For g groups, the Bayes rule assigns an object to the group i when: (8) (9) (10) (11) (12) (13) being P (xji) the probability of obtaining a particular set of features x, given that the object belongs to the group i and P (i) is the probability a priori, that is the probability of choosing the group i without any feature of the known object. where are the basis functions and are the basis coe cients.
In this work, we used B-splines basis. Then, we extract features from the
Complex Network or Fourier descriptors by applying a transform to the coe
cients (alpha = x) [
k; l > : where:
In this case, assuming the hypothesis of independence, we have for the random variables:
P (ijx) > P (jjx); f or 8j 6= i P (ijx) =
P (i) Qn
k=1 P (xkji) Qn
k=1 P (xk) P (xkji) =
1 p2 2 ik e (xi2 i2kik)2
In addition to Naive Bayes we use the Canonical Discriminant Analysis [
N X(xi i=1 )(xi
)0 Si =
X (xi i2Ci i)(xi
i)0 Sintra = K X Ni( i i=1
K X Si i=1 Sinter = )( i )0 and the matrix Si indicating the dispersion of objects of Ci: we can de ne the intra-class variability Sintra (indicating the combined dispersion within each class) and interclass variability Sinter (indicating the dispersion of the classes in terms of their centroids) as:
where K is the number of classes, N , the number of samples, Ni, the number of objects in class i, Ci, the set of samples of class i, , the global average, and i, the average of objects in class i. For these measures of dispersion we have necessarily:
S = Sintra + Sinter Thus, the i-th canonical discriminant function is given by:
Zi = ai1X1 + ai2X2 + + aipXp where p is the number of features of the model and aij are the elements of the eigenvector ai = (ai1; ai2; : : : ; aip) of matrix C given by:
C = Sinter
Sin1tra
In general a reduction in the number of features is desired. Thus, the system of random variability of the original vector with p-original variables is approximated by the variability of the random vector containing the k-principal components. 4
We submitted 3 di erent runs to the plant identi cation task. The main di erences between those 3 runs can be seen in Fig. 1.
In the rst run we apply the Complex Network method in shapes of the leaves. In sequence the methods of Canonical Discriminant Analysis followed by (14) (15) (16) (17) (18) (19) (20) Naive Bayes classi er are employed. For that, only 10 canonical variables are used in the Naive Bayes classi er. These 10 main components represent 99.99% of total variance.
For the second run, the FDA method is employed over Complex Network descriptors. The new obtained descriptors by FDA method are then used as input to the CDA method.
The third run is exactly equal of the second run, except that, in this we use Fourier descriptors in replace of Complex Network descriptors.
The results are showed in Table 1. We see that Complex Network descriptors obtain best results than Fourier descriptors. You can also observe that the FDA method make a small improving on the success rate.
Is important emphasize here that, though both methods aims improve the quality of descriptors, each one acts in a di erent way on these. On Canonical Discriminant Analysis the objective is maximize the separation of classes, while the Functional Data Analysis aims highlight some features of the original feature vector.
It is important to emphasize that the method of Complex Networks do not
need a closed contour, since the method is invariant to rotation and scale,
problems that we have in the dataset. We also have a good robustness against noise
and spurious contour points [
Is not surprising the good success rate achieved by the photo images (if compared with scan and scan-like images). This is probably due to the manual segmentation performed on these images. 5
Although we have obtained good results, they are still far from ideal. We perceived as the main problem to lack of standardization of the images, especially images of free natural photos. For these images we do not have a good generic method to make the correct segmentation of all the images.
It is important to remember that other relevant information contained in the associated XML was not used. Such information can help achieve better success rates.
Is important to note that there are other diagnostic keys that can be used
to leaf identi cation, texture [
Thus, there are good prospects to achieve a good system of leaf identi cation with the use of these variables. Such a system would be very helpful to botanists and other professionals.