Bin Luo

Jean-Franc ¸ois Aujol

Yann Gousseau

Saïd Ladjal

Indexing of satellite images with different resolutions by wavelet features

As many users of imaging technologies, space agencies are rapidly building up massive image databases. A particularity of these databases is that they are made of images with different but known resolution. In this paper, we introduce a new scheme allowing to index and compare images with different resolution. This scheme relies on a simplified modeling of the acquisition process of satellite images and uses continuous wavelet decompositions. We establish a correspondance between scales that permits to compare wavelet decompositions of images having different resolutions. We validate the approach through several matching and classification experiments, and show that taking the acquisition process into account yields better results than just using scaling properties of wavelet features.

I. INTRODUCTION

Spatial agencies are very rapidly building up massive databases of images. For example, the CNES (the French spatial agency) is receiving from its satellites several terabytes of data each day. Like most users of large databases, these institutions need efficient tools to index and search their images. One particularity of satellite image databases, compared to e.g. natural images databases, is that they are made of images with different but known resolution 1 , depending on the satellite they originate from. In contrast, natural image databases are made of pictures with different resolutions but the relationship between the size of objects and pixels is unknown. Moreover, this quantity depends on the position of objects in the scene, so that the notion of resolution itself has little general meaning. This obvious fact made it necessary to develop scale invariant local features for many computer vision tasks, see e.g. [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. For the indexing of texture, it makes sense to assume a uniform resolution through the image. Since this resolution is usually unknown, many scale invariant indexing schemes have been developed, see e.g. [START_REF] Fernand | Classification of rotated and scaled textured images using gaussian markov random field models[END_REF], [START_REF] Zhang | Affine invariant texture signatures[END_REF], [START_REF] Pun | Log-polar wavelet energy signatures for rotation and scale invariant texture classification[END_REF], and [START_REF] Zhang | A brief review of invariant texture analysis methods[END_REF] for a review. Our purpose in this paper is quite different. First, the resolution of satellite images is usually a known parameter, at least if we neglect tilts of the optical device and assume that the scene being captured is approximately flat. Therefore, our goal is to be able to compare two images knowing their resolution difference. Second, a change in resolution is more complicated than just a scale change, since it usually involves an optical device and an imaging captor. In a previous work, [START_REF] Luo | Characteristic scale in satellite images[END_REF], [START_REF] Luo | Resolution independant characteristic scale dedicated to satellite images[END_REF], this process was modeled as a convolution followed by a sampling and its effect on the computation of a characteristic scale was B. Luo, Y. Gousseau and Saïd Ladjal are with GET/Télécom Paris, CNRS UMR 5141 CNES-DLR-ENST Competence Centre, 46, rue Barrault, 75634, Paris Cedex 13, France.

J-F. Aujol is with CMLA, ENS Cachan, CNRS, UniverSud, 61 Av. President Wilson, F-94230 Cachan, France. 1 By resolution, we mean the true pixel size in meter.

studied. In this paper, we make use of the same model and propose a scheme to compare features extracted from images at different resolutions. Observe that several works have been performed to extract image features that are invariant with respect to resolution changes [START_REF] Flusser | Degraded image analysis: An invariant approach[END_REF], [START_REF] Van De Weijer | Blur robust and color constant image description[END_REF]. Again, our purpose is quite different since we wish to be able to compare images with different but known resolution. Many features have been proposed to index satellite images [START_REF] Lorette | Texture analysis through a markovian modelling and fuzzy classification: Application to urban area extraction from satellite images[END_REF], [START_REF] Rellier | Texture feature analysis using a gauss-markov model in hyperspectral image classification[END_REF], [START_REF] Datcu | Spatial information retrieval from remote-sensing images. ii. information theoretical perspective[END_REF], [START_REF] Chen | Identifying the characteristic scale of scene variation in fine spatial resolution imagery with wavelet transform-based sub-image statistics[END_REF], [START_REF] Gevers | Robust photometric invariant region detection in multispectral images[END_REF]. In this work, we only consider mono-spectral images and classically choose to index them using texture features. In particular, wavelet features have been proved suitable for texture indexing or classification [START_REF] Van Dyck | Statistical texture characterization from discrete wavelet representations[END_REF], [START_REF] Do | Wavelet-based texture retrieval using generalized gaussian density and kullback-leibler distance[END_REF], [START_REF] Aujol | Wavelet-based level set evolution for classification of textured images[END_REF], [START_REF] Unser | Texture classification and segmentation using wavelet frames[END_REF], [START_REF] Choi | Multiscale image segmentation using wavelet-domain hidden markov models[END_REF], [START_REF] Van De Wouwer | Statistical texture characterisation from discrete wavelet representation[END_REF], [START_REF] Liu | Information-theoretic analysis of interscale and intrascale dependencies between image wavelet coefficients[END_REF], [START_REF] Chen | Rotation and gray scale transform invariant texture identification using wavelet decomposition and hidden markov model[END_REF]. Wavelet features have already been used for indexing remote-sensing images in [START_REF] Soe | Wavelets for urban spatial feature discrimination: Comparisons with fractal, spatial autocorrelation, and spatial co-occurence approaches[END_REF]. The aim of the proposed approach is to investigate the interplay between resolution and wavelet features and to propose a scheme for the comparison of images with different resolutions. Preliminary results of the present work were presented in [START_REF] Luo | Interpolation of wavelet features for satellite images with different resolutions[END_REF].

The plan of the paper is the following. In Section II a simplified model for the acquisition of satellite images is introduced. In Section III, we recall how the marginals of wavelet coefficients can be used for the indexing of images. In Section IV, a method is given to compare features extacted at different resolutions. In Section V, the dependence of features upon resolution is checked using satellite images from the CNES and the proposed scheme is validated through classification experiments. We then conclude in Section VI.

II. MODEL OF THE ACQUISITION PROCESS

A digital image f r at resolution r is obtained from a continuous function f (representing the scene under study) through an optical device and a digital captor. Neglecting contrast changes and quantization, the effect of the imaging device can be modeled as follows,

f r = Π Sr .(G * f ) + n,
where G is the convolution kernel, S r ⊂ Z 2 the sampling grid at resolution r, Π Sr the Dirac comb on S r and n the noise. In what follows, we will take interest in the effect of the acquisition model on the wavelet coefficients of f r . Therefore, and assuming that we will neglect coefficients at the smallest scales, we will assume that n = 0. Moreover, we will assume that S r = rZ 2 , that is a regular and square sampling grid with step r. We thus neglect the satellite vibrations and scan acquisition. Last and more importantly, according to [START_REF] Ellliott | Accuracy of gaussian approximation for simulating eo sensor response[END_REF], [START_REF] Zhang | Gaussian approximations of fluorescence microscope point-spread function models[END_REF], the response of an ideal optic aperture could be very accurately approximated by a Gaussian kernel. Therefore we will assume that G is an isotropic Gaussian kernel, thus neglecting the specificity of the satellite optics, the real response of the captor and motion blur. This is probably the strongest assumption made. The motivation behind it is mainly the tractability of forecoming computations, as will become clear soon. Last, we assume that the standard deviation of the kernel is proportional to the resolution. In the experimental section, we will check that these assumptions are not too restrictive by considering realistic satellite images. To summarize, we assume the following acquisition model :

f r = Π r .(f * k rp ), (1)
where

k σ (x, y) = 1 2πσ 2 exp - x 2 + y 2 2σ 2 , ( 2
)
Π r is the Dirac comb on rZ 2 , that is,

Π r = i,j∈Z δ (ir,jr) ,
and the parameter p is a characteristic of the acquisition process.

III. WAVELET FEATURES FOR TEXTURE INDEXATION

Based on empirical observations, Mallat [START_REF] Mallat | A theory for multiresolution signal decomposition: The wavelet representation[END_REF] proposed to model the marginals of wavelet coefficients of natural images by Generalized Gaussian Distributions (GGD). That is, writing h for the density of the distribution of coefficients at some scale and orientation,

h(u) = Ke -(|u|/α) β . (3)
It is shown in [START_REF] Van Dyck | Statistical texture characterization from discrete wavelet representations[END_REF], [START_REF] Do | Wavelet-based texture retrieval using generalized gaussian density and kullback-leibler distance[END_REF], [START_REF] Aujol | Wavelet-based level set evolution for classification of textured images[END_REF] that the parameters α and β of GGD can be used as efficient features for texture indexing and classification. It is possible to compute these parameters from the estimation of the first and second order moments of |u| [START_REF] Mallat | A theory for multiresolution signal decomposition: The wavelet representation[END_REF]: we denote them respectively by m 1 = |u|h(u)du and

m 2 = u 2 h(u)du. More precisely, m 1 = αΓ(2/β)Γ(1/β) -1 and m 2 = α 2 Γ(3/β)Γ(1/β) -1 .
In this paper, for simplicity, we address the problem of relating features m 1 and m 2 to resolution changes. Adapting the results to α and β is then straightforward. This can be useful when using the Kullback-Leibler distance in a classification task, see [START_REF] Do | Wavelet-based texture retrieval using generalized gaussian density and kullback-leibler distance[END_REF].

In order not to be restricted to dyadic resolution changes, continuous wavelet transform [START_REF] Mallat | A Wavelet Tour of Signal Processing[END_REF] is used instead of the more classical discrete wavelet transform. Moreover, we consider mother wavelets obtained as derivatives of a Gaussian kernel in horizontal, vertical and diagonal directions. This important assumption is motivated by the simplified model for resolution changes presented in the previous section, as will be shown by the computations of Section IV-A.

Figure 1 shows a histogram of absolute values of wavelet coefficients, illustrating the soundness of the use of GGDs to model such distributions.

IV. WAVELET FEATURES AND RESOLUTION CHANGES

A. Resolution Invariance a) Notations: The discrete version of the Gaussian kernel with standard deviation t (t being given in pixels) is denoted by kt . Let us define the discrete wavelet coefficient as (recall that the wavelets we use are derivatives of the Gaussian kernel):

w q,r,t = ∆ q kt * f r = kt * ∆ q f r (4)
where q ∈ {0, 1, 2, 3}, ∆ q stands for the difference between adjacent pixels in the horizontal (q = 0), vertical (q = 1) or diagonal (q = 2, 3) direction, and * stands for the discrete convolution operation. b) Resolution invariance: Recall that the image f r at resolution r is obtained by f r = Π r .(k rp * f ). From Equation (4) , we therefore have:

w q,r,t = kt * ∆ q Π r (k rp * f ) (5) ≈ kt * Π r {r∂ q (k rp * f )}.
The last approximation will be detailed in the appendix.

Next, we assume that the inversion between convolution and sub-sampling is licit for non-aliased images such as k σ * f when σ is at least, say, r/2. The validity of this assumption on real images has been checked in [START_REF] Luo | Resolution independant characteristic scale dedicated to satellite images[END_REF]. Assuming that kt ≈ k rt (see [START_REF] Luo | Resolution independant characteristic scale dedicated to satellite images[END_REF]), and that the continuous and discrete convolutions are equivalent, we have:

w q,r,t ≈ rΠ r .(k rt * k rp * ∂ q f ). (6)
Using the semi-group property of the Gaussian kernel, it can be deduced that:

w q,r,t r ≈ Π r .(k r √ t 2 +p 2 * ∂ q f ). (7)
The accuracy of this approximation will be computed in the appendix.

Assume now that we have two images f r1 and f r2 of the same scene at resolutions r 1 and r 2 . ¿From [START_REF] Luo | Resolution independant characteristic scale dedicated to satellite images[END_REF], we deduce that if we choose scales t 1 and t 2 such that:

r 1 t 2 1 + p 2 = r 2 t 2 2 + p 2 (8)
we have:

m 1 (q, r 1 , t 1 )/r 1 ≈ m 1 (q, r 2 , t 2 )/r 2 (9) m 2 (q, r 1 , t 1 )/r 2 1 ≈ m 2 (q, r 2 , t 2 )/r 2 2 (10) with m 1 (q, r, t) = 1 n r |w q,r,t |, m 2 (q, r, t) = 1 n r |w q,r,t | 2 ,
where n r is the size of the discrete image f r and the sum is taken over the image domain (notice that, since we use a continuous wavelet transform, w has the same size as f r ). These equalities (Formula ( 9) and ( 10)) will permit to compare wavelet features originating from f 1 and f 2 . In what follows, we denote by Θ q,r,t = {m 1 (q, r, t), m 2 (q, r, t)} the wavelet features at scale t and direction q extracted from f r . c) Remark about the naive choice p = 0.0: A naive assumption could be drawn that for the same scene f , if we keep

r × t = C ( 11
)
where C is a constant, the parameter set will also be constant (after the correct normalization). However, this assumption is not sufficient because it approximates the resolution change by a simple zoom, which is not consistent with the acquisition process modeled in Section II. We will see in Section V that such a naive choice leads to poor numerical results compared with the use of Equation [START_REF] Flusser | Degraded image analysis: An invariant approach[END_REF]. In what follows, we will call "naive choice" the use of p = 0 in Equation ( 8). d) Tuning of p: To use Equation ( 8), one needs to know the value of p. This is a characteristic of the acquisition process (see Equation ( 1)). This can therefore be tabulated once for each satellite. Observe that if one considers two images f r1 and f r2 with different resolutions, it is very likely that they originate from different satellites and that the corresponding values of p be different. In this case, writing p i for the value of p corresponding to resolution r i (i = 1, 2) it is straightforward to show that Equation ( 8) can be generalized to

r 1 t 2 1 + p 2 1 = r 2 t 2 2 + p 2 2 . (12)
This equality again ensures that approximations ( 9) and [START_REF] Lorette | Texture analysis through a markovian modelling and fuzzy classification: Application to urban area extraction from satellite images[END_REF] will hold and permits the comparison of wavelet features from f r1 and f r2 . In what follows, for the sake of simplicity, we will assume that p 1 = p 2 and therefore use Equation [START_REF] Flusser | Degraded image analysis: An invariant approach[END_REF].

B. Wavelet features and resolution

As explained in the introdution, the aim of this paper is to propose a way to compare the features originating from two images with different and known resolutions. One way to achieve this is to modify the features (i.e. the first and second order moments m 1 and m 2 ) extracted at resolution r 1 to compare them (depending on r 2 and r 1 ) with the features extracted at resolution r 2 . Assume that we have f r1 the image at resolution r 1 of a given scene, and that we want to predict its features at resolution r 2 . From Equations ( 7)- [START_REF] Lorette | Texture analysis through a markovian modelling and fuzzy classification: Application to urban area extraction from satellite images[END_REF], we deduce the following scheme:

• Compute the wavelet coefficients for f r1 at scales t i , i = 1, 2, 3, . . . , N ; • Estimate the parameters Θ q,r1,ti from the wavelet coefficients at scales t i for resolution r 1 ;

• For resolution r 2 , compute the scales t i corresponding to t i according to (see Equation ( 8))

t i = r 2 1 r 2 2 (t 2 i + p 2 ) -p 2 (13)
• Define Θq,r2,t i = Θ q,r1,ti at scales t i . By using such an algorithm, it is now possible to compare images taken at different resolutions and, for instance, to train classification methods on a set of images at only one resolution and to apply the recognition criteria to images at different resolutions.

V. EXPERIMENTS AND RESULTS

A. Image database

In the following sections, we experimentally validate the proposed scheme for comparing wavelet features. These experiments are carried on an image database provided by the CNES (the French spatial agency). This database is made of various scenes (such as fields, forests and cities). Each scene has been acquired as an aerial image at resolution 0.25m. Then, for each scene, the CNES has simulated images at various resolutions, using realistic satellite modeling. The available resolutions range from 0.5m to 4m, according to a geometric progression with ratio 2 1/6 . In Figure 2 some examples of the images from the database are shown. It is important at this point to note that convolution kernels used by the CNES are not Gaussian. However, we will see that the approximate acquisition model of Section II yields good numerical results. In what follows, we will use the acquisition model (1) with a value p = 1.3. This value has been chosen as the value yielding the best numerical results (among values ranging from 1 to 2 by steps of 0.1) and also corresponds to a rough approximation of the kernel used by the CNES.

B. Validity of the prediction scheme

First, we check the validity of Formula ( 8), ( 9) and (10) by plotting numerical values of features m 1 and m 2 .

Figures 3 (d)-(f) (resp. (g)-(i)) graphs of m 1 (q, r, t)/r (resp. m 2 (q, r, t)/r 2 ) as functions of r are presented when rt is kept constant (that is when using the naive normalization of Equation ( 11)) and when r t 2 + p 2 (here p = 1.30) is kept constant (see Equation ( 8)). The resolution r ranges from 0.50m to 4m. For the image at resolution 0.50m (the highest available resolution), m 1 and m 2 are computed at scale 16 in the horizontal direction. It may be seen that using Equation [START_REF] Rellier | Texture feature analysis using a gauss-markov model in hyperspectral image classification[END_REF] (that is forgetting the convolution step in the model of resolution change) does not yield a constant parameter set, especially when the resolution change is large. In such cases, one must use Equation ( 8) to compare features.

Next, and for various scales, we compare values of m 1 and m 2 computed on an image with resolution 3.175m to values of m 1 and m 2 computed on a image of the same scene with resolution 1m and then predicted for a resolution of 3.175m. Figures 4 (a graphs of m 1 (q, r, t)/r (with q = 0) as a function of r; (g)-(i) graphs of m 2 (q, r, t)/r 2 (with q = 0) as a function of r. On all these graphs, solid lines correspond to the case where r 2 p t 2 + p 2 is kept constant (with p = 1.3), and dashed lines correspond to the case the case where rt is kept constant. On the same figure, m 1 (resp. m 2 ) predicted from a resolution of 1m for a resolution of 3.175m according to the scheme presented in Section IV-B are displayed by a solid red line.

(c) (d) (e) (f) (g) (h) (i) (j) (k) (l) (m) (n) (o) (p) (q) (r) (s) (t)
The two solid lines almost perfectly coincide. In dashed line, are plotted the values of m 1 (respectively m 2 ) predicted from a resolution of 1m for a resolution of 3.175m by the same scheme of Section IV-B, except that Equation ( 13) is replaced

t i = r 1 t i /r 2 .
This corresponds to what we called the naive choice, neglecting convolutions in the resolution change. It can be seen that in this case, the guessed values of m 1 and m 2 are less accurate, especially for small scales. These experiments validate the scheme proposed in Section IV-B and suggests that it is necessary to take into account the convolution step in resolution changes to be able to compare features computed on images with different resolution. The next section investigates how the accuracy of the proposed scheme permits the of images at different resolutions. features extracted from the images at a resolution of 4m over 21 scales (t = {2 i/6 , i = 0, 1, . . . , 20}) are used to train the classifier. Therefore the dimension of the feature space is 2 × 4 × 21 = 168. The features extracted from the other resolutions are predicted for 4m by using the scheme presented in Section IV-B. For comparison, we set the value p respectively equal to 1.3 (using the acquisition model) and 0.0 (the naive approach). We then classify the images at resolutions other than 4m with the predicted features.

The classifier we used is simply the nearest neighbor classification algorithm. For a given image A, the classifier search for its nearest neighbor B in the training set and affect to A the class of B. As a distance between features, we use the Euclidean distance, after normalizing each coordinate by its variance. c) Results: The classification results are shown in Tab. I. It can be observed that with the naive approach, the classification errors increase rapidly when the resolution gets away from 4m. This shows numerically that the naive approach (p = 0) is not a good choice for classification purpose. On the contrary, when the acquisition model is taken into consideration (i.e. p = 1.3), there is no error. This is due to the that the prediction scheme is very accurate, as we have shown in Section V-B. Errors are small enough to switch from one class to another when changing the resolution.

d) Influence of the number of features:

The classification results presented in Table I are obtained from features in a space with relatively large dimension (168 values for each image). We therefore study the effect of a dimension reduction. In Table II are shown the classification results obtained when performing the same experiment as in Table I, using the wavelet features (m 1 and m 2 ) at only 3 scales (t = 1, 2, 4). In this case the dimension of the feature space is 2 × 4 × 3 = 24 and it can be observed that the errors remain similar. e) Comparison with other features: In order to further investigate the effect of resolution changes on classification tasks, we perform an experiment using Haralick features. Haralick [START_REF] Haralick | Textural features for image classification[END_REF] has proposed features based on the statistics of co-occurrence matrices of images. These features are proved to be very efficient for indexing textures. Co-occurence matrices are defined as the empirical joint distribution of the gray values of pixels in some direction θ and at some distance d. The considered directions are horizontal, vertical and two diagonal directions. The distance between the pixel pairs can be considered as a scale parameter. For images at different resolutions, it is therefore natural to compute co-occurrence matrices with different distances. In our experiment, we set d = 3, 4, 6, 12, 24 respectively for images at resolutions 4m, 3.175m, 2m, 1m and 0.5m. These values ensure that d×r is a constant. The Haralick features are composed of 13 statistical values calculated from each matrix and the mean and standard deviation values through the four directions. Therefore the total feature dimension is (4 + 2) × 13 = 78.

Figure III shows the classification results obtained with Haralick features. Our purpose here is not to compare directly these results with the results obtained in the previous section. Indeed, results obtained with wavelet features are better, but we did not take full advantages of co-occurrence matrices since only one scale is used for each image. The interesting point is to notice how fast the classification results decrease with the change of resolution, therefore showing the inability of Haralick features to handle such changes. Observe that the approach taken here is similar to the naive choice of previous sections (approximating a resolution change through a zoom). Due to the non-linear nature of co-occurrence matrices, the approach proposed in the case of wavelet features is not adaptable to Haralick features.

D. Image Matching

In this subsection, we carry out a more difficult experiment than in the previous subsections. For each image at a resolution of 4m, we want to find the exact same scene from the images at other resolutions with the help of wavelet features. The features are extracted and predicted as presented in Section IV-B. For an image at a resolution different from 4m, we search its nearest neighbor in the feature space among the set of images at 4m. If the two images are of the same scene, it is a correct match, otherwise it is an error. This is the same classification task as before, except that we consider each scene to be a class in itself.

In Table IV are displayed the matching results when using features over 21 scales (t i = 2 i/6 , i = 0, 1, ,20) and 4 orientations. In Figure V are displayed the matching results when using only 3 scales (t i = 2 i , i = 0, 1, 2). It can be observed that:

• The errors increase considerably when compared to the classification results of the previous subsection, especially when p = 0.0. This is due to the fact that in the image database, there are many scenes of the same class which are very similar one to another. Therefore the points representing these images in the feature space are close one to another. As a consequence, a small error in the prediction causes an error in the image matching, in contrast with the classification case of Section V-C. • The small errors in the case p = 1.3 confirm the accuracy of the scheme.

VI. CONCLUSIONS AND PERSPECTIVES

In this paper, we have proposed a scheme for comparing wavelet features from images taken at different resolutions.

The acquisition of images is modeled by a convolution followed by a sampling. The scheme to compare wavelet features is based on this model and the semi-group property of the Gaussian kernel. We first checked experimentally the validity of this scheme and showed that the numerical accuracy is significantly improved compared to a naive approach where resolution change is simply modeled by a zoom. This approach is then applied for the classification of satellite images at several resolutions simulated by the CNES. Our approach improves significantly the accuracy of the classification. This fact is confirmed trough an image matching experiment.

The method presented in Section IV-B to compare wavelet features between images with different resolution is quite general. We applied it to images classification, but other tasks could benefit from this approach. For instance, the scale invariance of wavelet transformations has been applied to the fusion of aerial images having different resolutions [START_REF] Thierry | Remote sensing and image fusion methods: A comparison[END_REF][31] [START_REF] Núnez | Multiresolution-based image fusion with additive wavelet decomposition[END_REF]. None of these works takes into account the influence of the optics and captors on the change of resolution. We believe that the approach presented in Section IV could improve the precision of such fusions of images. Acknowledgements: We thank Mihai Datcu, Alain Giros and Henri Maître for their advices and comments.

APPENDIX

In this appendix, we detail the approximation made in Equation [START_REF] Zhang | A brief review of invariant texture analysis methods[END_REF] and compute the error functions of the approximation made in Equation [START_REF] Luo | Characteristic scale in satellite images[END_REF].

Recall that w q,r,t are the wavelet (Gaussian derivative) coefficients extracted from f r at scale t and in direction q, where f r is the digital image at resolution r obtained from the continuous scene f . For clarity, we only consider the 1D case. Recall Formula (5): w q,r,t = ∆ q kt * Π r (k rp * f ) = kt * ∆ q Π r (k rp * f ).

In the 1D case, we have w r,t = kt * ∆ x Π r (k rp * f ).

Writing g(x) = (k rp * f )(x), we have w r,t (x) = kt * ∆ x Π r (g(x)) = kt * (Π r (g(x + r) -g(x))), and since g ∈ C 1 , we have g(x + r) = g(x) + rg (x) + o(r). Therefore w r,t ≈ kt * Π r (g(x) + rg (x) -g(x))

= kt * Π r (rg (x)) ≈ r kt * Π r (k rp * f (x)). This is the approximation made in Equation [START_REF] Zhang | A brief review of invariant texture analysis methods[END_REF]. Next, we compute the error energy of the approximation made in Equation [START_REF] Luo | Characteristic scale in satellite images[END_REF]. For simplicity, we consider the resolution r = 1. We want to show that the energy of the error is small.

E = |∆ x kt * Π 1 (g) -Π 1 (k t * g )| 2 = |F T ∆ x kt * Π 1 (g) -Π 1 (k t * g ) | 2 dω
where F T (f ) is the Fourier transform of f . With the approximation k t ≈ Π r (k rt ), we have

E ≈ |F T {∆ x Π 1 (k t * g) -Π 1 (k t * g )} | 2 dω = |F T {Π 1 (k t * g(x + 1) -k t * g(x)) -Π 1 (k t * g )} | 2 dω = |F T {Π 1 (k t * g(x + 1) -k t * g(x) -k t * g )} | 2 dω
We suppose that the image is not aliased, (i.e. k t * g is band Recall that t ≥ 1 and p = 1.3 in all our numerical experiments. Since the power spectrum of the image f is generally decreasing, and ω 4 2 is increasing, the worst case (which yields the largest error) is therefore |F T {f }| 2 = 1 for all ω, where we have

E ≈ π 0 ω 4 2 |F T {k √ 1 2 +1.3 2 }| 2 dω and E |w r,t | 2 ≈ 0.035
Figure 5 shows a plot of E and the power spectrum of wavelet coefficients w r,t in the frequency domain for the case where |F T {f }| 2 = 1. In the worst case, the approximation made in Equation ( 6) yields an energy error of 3.5% when compared to the energy of the original wavelet coefficients.

Fig. 1 .

 1 Fig. 1. (a) Image of Marseille at resolution 0.707m ( c CNES); (b) Histogram (blue bars) of wavelet coefficients of image (a) at scale 5 (horizontal) and the approximation by GGD (red curve).

  )-(c) (resp. (d)-(f)) show the values of m 1 (respectively m 2 ) at various scales (scale is on the horizontal axis) in solid blue line for three different scenes.

Fig. 2 .Fig. 3 .

 23 Fig. 2. Image samples from the database provided by the CNES: (a)-(d) Images at resolution 0.5m; (e)-(h) Images at resolution 1.0m; (i)-(l) Images at resolution 2.0m; (m)-(p) Images at resolution 3.175m; (q)-(t) Images at resolution 4.0m; ¿From left to right, classes of the images are: city, field, forest and sea.

Fig. 4 .

 4 Fig. 4. Values of m 1 ((a)-(c)) and of m 2 ((d)-(f)) for various scales (scale corresponds to the horizontal axis). In solid red line are displayed the values computed directly on images with resolution 3.175m (the ground truth in this experiment). In solid blue line, are displayed the values first computed on the images with resolution 1m and then predicted using the scheme presented in Section IV-B. Both solid lines almost perfectly coincide, showing the accuracy of the scheme. Dash lines show the results obtained by using the scheme proposed in Section IV-B but replacing Equation (13) with t i = r 1 t i /r 2 (the naive normalization).

  database: We have manually built a classified database based on the sequences of images provided by the CNES. This database contains 366 scenes observed on urban areas (Marseille and Toulouse), rural areas (Roujan), forests (Didrai) and the sea. For each scene, there are 5 different images corresponding to 5 different resolutions (0.5m, 1m, 2m, 3.175m and 4m). The scenes are manually divided into 4 sets: city (199 scenes), fields (134 scenes), forests (23 scenes) and sea (10 scenes). b) Experiment: The first experiment carried out on this database is classification. Images at the resolution of 4m are used as a learning set for training the classifier. The aim is to find the classes of the images at resolutions other than 4m. Wavelet features (m 1 and m 2 ) are at first extracted from all the images by applying Gaussian derivatives at different scales in 4 directions (horizontal, vertical and diagonal). The

Fig. 5 . 2 π 0 2( 1 -ω 2 |F T {k t * g}| 2 dω ≈ π 0 ω 4 2 π 0 ω 4 2 |F T {k √ p 2

 52012222 Fig. 5. Error function (E) and power spectrum of wavelet coefficients wr,t in the frequency domain.

TABLE I CLASSIFICATION

 I RESULTS OBTAINED WITH WAVELET FEATURES EXTRACTED IN 4 DIRECTIONS AT 21 SCALES (t = {2 i/6 |i = 0, 1, . . . , 20}). THE LEARNING SET IS MADE OF IMAGES AT RESOLUTION 4m.

	Resolution	error (p = 1.3)	error (p = 0)
	0.5m	0.00%	21.86%
	1m	0.00%	19.95%
	2m	0.00%	10.66%
	3.175m	0.00%	1.91%

TABLE II CLASSIFICATION

 II RESULTS OBTAINED WITH WAVELET FEATURES EXTRACTED IN 4

	DIRECTIONS AT 3 SCALES (t = 1, 2, 4). THE LEARNING SET IS MADE OF IMAGES AT
		RESOLUTION 4m.
	Resolution	error (p = 1.3)	error (p = 0)
	0.5m	0.55%	26.50%
	1m	0.00%	24.59%
	2m	0.00%	12.84%
	3.175m	0.27%	4.92%

TABLE III CLASSIFICATION

 III RESULTS OBTAINED WITH HARALICK FEATURES. THE DISTANCE PARAMETER FOR CALCULATING CO-OCCURRENT MATRICES VARIES ACCORDING TO THE RESOLUTION OF IMAGE. THE LEARNING SET IS MADE OF IMAGES AT RESOLUTION 4m.

	Resolution	distance	error
	0.5m	24	31.9%
	1m	12	22.4%
	2m	6	13.6%
	3.175m	4	10.1%

TABLE IV MISMATCHING

 IV PERCENTAGES WHEN USING WAVELET FEATURES EXTRACTED AT 21

	SCALES WITH 4 ORIENTATIONS.
	resolution	0.5	1.0	2.0	3.175
	p=1.3	4.1	0.27	0	1.64
	p=0	81.97 79.51 65.57 34.97
			TABLE V
	MISMATCHING PERCENTAGES WHEN USING WAVELET FEATURES EXTRACTED AT 3
	SCALES WITH 4 ORIENTATIONS
	resolution	0.5	1.0	2.0	3.175
	p=1.3	11.2	4.64	1.09	9.29
	p=0	95.90 96.45 92.62 62.02


Peggy Cellier

Sébastien Ferré

Olivier Ridoux

Mireille Ducassé

A Parameterized Algorithm for Exploring Concept Lattices

Formal Concept Analysis (FCA) is a natural framework for learning from positive and negative examples. Indeed, learning from examples results in sets of frequent concepts whose extent contains only these examples. In terms of association rules, the above learning strategy can be seen as searching the premises of exact rules where the consequence is fixed. In its most classical setting, FCA considers attributes as a non-ordered set. When attributes of the context are ordered, Conceptual Scaling allows the related taxonomy to be taken into account by producing a context completed with all attributes deduced from the taxonomy. The drawback, however, is that concept intents contain redundant information. In this article, we propose a parameterized generalization of a previously proposed algorithm, in order to learn rules in the presence of a taxonomy. The taxonomy is taken into account during the computation so as to remove all redundancies from intents. Simply changing one component, this parameterized algorithm can compute various kinds of concept-based rules. We present instantiations of the parameterized algorithm for learning positive and negative rules.

Introduction

Learning from examples is a fruitful approach when it is not possible to a priori design a model. It has been mainly tried for classification purposes [START_REF] Mitchell | Machine Learning[END_REF]. Classes are represented by examples and counter-examples, and a formal model of the classes is learned by a machine.

Formal Concept Analysis (FCA) [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] is a natural framework for learning from positive and negative examples [START_REF] Kuznetsov | Machine learning and formal concept analysis[END_REF]. Indeed, learning from positive examples (respectively negative examples) results in sets of frequent concepts with respect to a minimal support, whose extent contains only positive examples (respectively negative examples). In terms of association rules [AIS93,AS94], the above learning strategy can be seen as searching the premises of exact rules where the consequence is fixed. When augmented with statistical indicators like confidence and support it is possible to extract various kinds of concept-based rules taking into account exceptions [START_REF] Pasquier | Discovering frequent closed itemsets for association rules[END_REF][START_REF] Zaki | Mining non-redundant association rules[END_REF].

The input of FCA is a formal context that relates objects and attributes. FCA considers attributes as a non-ordered set. When attributes of the context are ordered, Conceptual Scaling [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] allows the attribute taxonomy to be taken into account by producing a context completed with all attributes deduced from the taxonomy. The drawback is that concept intents contain redundant information. In a previous work [START_REF] Cellier | An algorithm to find frequent concepts of a formal context with taxonomy[END_REF], we proposed an algorithm based on Bordat's algorithm [START_REF] Bordat | Calcul pratique du treillis de Galois d'une correspondance[END_REF] to find frequent concepts in a context with taxonomy. In that algorithm, the taxonomy is taken into account during the computation so as to remove all redundancies from intents.

There are several kinds of association rules, and several related issues: e.g. find all association rules with respect to some criteria, compute all association rules with a given conclusion or premise. We propose a generic algorithm to address the above issues. It is a parameterized generalization of our previous algorithm. It learns rules and is able to benefit from the presence of a taxonomy. The advantage of taking a taxonomy into account is to reduce the size of the results. For example, the attributes of contexts about Living Things are intrinsically ordered1 . For a target such as "suckling", a rule such as "Living Things"∧ "Animalia" ∧ "Chordata" ∧ "Vertebrata" ∧ "Mammalia" → "suckling" is less relevant than the equivalent rule "Mammalia" → "suckling" where elements redundant with respect to the taxonomy have been eliminated. The presented algorithm can compute various kinds of concept-based rules by simply changing one component. We present two instantiations which find positive and negative rules. Positive rules predict some given target (e.g. predict a mushroom as poisonous), while negative rules predict its opposite (e.g. edible).

The contributions of this article are twofold. Firstly, it formally defines FCA with taxonomy (FCA-Tax) using the Logical Concept Analysis (LCA) framework [START_REF] Ferré | An introduction to logical information systems[END_REF], where the taxonomy is taken into account as a specific logic. Secondly, it specifies a generic algorithm which facilitates the exploration of frequent concepts in a context with taxonomy. Quantitative experiments show that taking a taxonomy into account does not introduce slowdowns. Furthermore, the pruning implemented by our algorithm related to the taxonomy can often improve efficiency.

In the following, Section 2 formally defines FCA with taxonomy (FCA-Tax). Section 3 presents the generalization of the algorithm described in [START_REF] Cellier | An algorithm to find frequent concepts of a formal context with taxonomy[END_REF] to filter frequent concepts in a formal context with taxonomy. Section 4 shows how to instantiate the algorithm to learn different kind rules. Section 5 discusses experimental results.

A Logical Framework for FCA with Taxonomy

In this section, we formally describe Formal Concept Analysis with Taxonomy (FCA-Tax) using the Logical Concept Analysis (LCA [START_REF] Ferré | An introduction to logical information systems[END_REF]) framework. We first present an example of context with taxonomy. Then we briefly introduce LCA, concept-based rules, and we instanciate LCA to FCA-Tax. A taxonomy describes how the attributes of the context are ordered and thus a taxonomy is a kind of logic where the subsumption relation represents this order relation. The context given Table 1 represents the observations of threatened and endangered bird families. Data come from the web site of USFWS2 (U.S Fish and Wildlife Service). The objects are bird families and each family is described by a set of states and regions where specimens have been observed and by a status: threatened or endangered . Note that in this context objects are elements of what could be a taxonomy in another context. Figure 1 shows the taxonomy of states and regions of USA.

Example of Context with a Taxonomy

• • Alcedinidae • • Alcidae • • • • Anatidae • • Cathartide • • Charadriidae • • • • • Corvidae • • Drepanidinae • • Emberizidae • • Gruidae • • • Icteridae • • Muscicapidae • • Strigidae • • • • • • Tyrannidae • • • • • Vireonidae • •
The context given in Table 1 is the straightforward transcription of the information found on the USFWS site. Note that it is not completed with respect to FCA. For example object Accipitridae which has in its description the attribute Florida has not the attribute Southeast. The information that an object has the attribute Florida implies that it has the attribute Southeast is implicitly given by the taxonomy. We have observed that this situation is quite common.

Logical Concept Analysis (LCA)

In LCA the description of an object is a logical formula instead of a set of attributes as in FCA.

-∀f ∈ L ext(f ) = {o ∈ O | d(o) f } -∀O ⊆ O int(O) = o∈O d(o)
Definition 4 (logical concept). Let K = (O, L, d) be a logical context. A logical concept is a pair c = (O, f ) where O ⊆ O, and f ∈ L, such that int(O) ≡ f and ext(f ) = O. O is called the extent of the concept c, i.e. ext c , and f is called its intent, i.e. int c .

The set of all logical concepts is ordered and forms a lattice: let c and c be two

concepts, c ≤ c iff ext c ⊆ ext c . Note also that c ≤ c iff int c int c . c is called a subconcept of c .
The fact that the definition of a logic is left so abstract makes it possible to accommodate non-standard types of logics. For example, attributes can be valued (e.g., integer intervals, string patterns), and each domain of value can be defined as a logic. The subsumption relation allows to order the terms of a taxonomy.

Concept-Based Rules

Definition 5 (concept-based rules). Concept-based rules consider a target W ∈ L such that W is a logical formula which represents a set of objects, ext(W ), that are positive (respectively negative) examples. Concept-based rules have the form X → W , where X is the intent of a concept. A rule can have exceptions. These exceptions are measured with statistical indicators like support and confidence, defined below.

Neither FCA nor LCA take into account the frequency of the concepts they define. An almost empty concept is as interesting as a large one. Learning strategy, however, is based on the generalization of frequent patterns. Thus, statistical indicators must be added to concept analysis. There exists several statistical measures like support, confidence, lift and conviction [START_REF] Brin | Dynamic itemset counting and implication rules for market basket data[END_REF]. In the following, support and confidence are used to measure the relevance of the rules, because they are the most widespread. However, the algorithm presented in this article does not depend on this choice.

Definition 6 (support). The support of a formula X is the number of objects described by that formula. It is defined as:

sup(X) = ext(X)
where Y denotes the cardinal of a set Y.

The support of a rule is the number of objects described by both X and W . It is defined as:

sup(X → W ) = ext(X) ∩ ext(W )
Definition 7 (confidence). The confidence of a rule X → W describes the probability for objects that are described by X to be also described by W . It is defined as:

conf (X → W ) = ext(X) ∩ ext(W ) ext(X)
The support applies as well to concepts as to rules. In the case of concept it introduces the notion of frequent concept as formalized by Definition 8.

Definition 8 (frequent concept).

A concept is called frequent with respect to a min sup threshold if sup(int c ) is greater than min sup.

Formal Concept Analysis with Taxonomy

FCA-Tax is more general than FCA because the attributes of the context are ordered. It can be formalized in LCA.

Definition 9 (taxonomy). A taxonomy is a partially ordered set of terms

T AX =< T, ≤ >
where T is the set of terms and ≤ is the partial ordering. Let x and y be attributes in T , x ≤ y means that y is more general than x.

Example 1. In Figure 1, Hawai ≤ Pacific ≤ USA.

Definition 10 (predecessors, successors, Min tax ). Let T AX =< T, ≤ > be a taxonomy and X in T be a set of terms. The predecessors of X in the taxonomy T AX are denoted by

↑ tax (X) = { t ∈ T | ∃x ∈ X : x ≤ t }
The successors of X in the taxonomy T AX are denoted by

succ tax (X) = { t ∈ T | ∃x ∈ X : x > t ∧ ( ∃t ∈ T : x > t > t) }
The successors represented by succ tax (X) are immediate ones only. succ + tax (X) is the transitive closure of succ tax (X), i.e. all successors of X in the taxonomy.

M in tax (X) is the set of minimal elements of X with respect to T AX. M in tax (X) = { t ∈ X | ∃x ∈ X : x < t }
In fact, M in tax (X) is X minus its elements that are redundant with respect to T AX.

Example 2. On the context of Table 1, with the taxonomy of Figure 1, examples of predecessors, successors and M in tax are as follows:

-

↑ tax ({Mississipi, Arizona }) = {Mississipi, Southeast, Arizona, Southwest, USA} -succ tax ({USA}) = {Pacific, Southeast, GreatLakes/BigRivers, Southwest, Northeast, Mountains/Prairie, Region7 , Region8 } -M in tax ({Florida, Southeast, USA}) = {Florida} Definition 11 (L tax ). Let T AX =< T, ≤ > be a taxonomy. L tax = (L tax , tax , tax , tax , tax , ⊥ tax )
is the logic of FCA-Tax, related to T AX:

-L tax = 2 T where T is the set of terms, -tax such that X Y iff ↑ tax (X) ⊇ ↑ tax (Y ), -tax is ∪ tax such that X ∪ tax Y = M in tax (X ∪ Y ), -tax is ∩ tax such that X ∩ tax Y = M in tax (↑ tax (X) ∩ ↑ tax (Y )), -tax = {x ∈ T | ext({x}) = O} -⊥ tax =M in tax (T ). L = {{Hawai }, {Oregon}, {Pacific}, {Southwest }, ..., {USA}, (1) {Hawai
, Southwest }, ...} {Michigan, Florida} {Michigan, Southeast } (2) {Michigan, Southeast } {Florida} = {Michigan, Florida} (3) {Mississipi } {Florida} = {Southeast } (4) = {USA} (5) ⊥ = {Hawai, Washington, Oregon, Arizona, Michigan, Mississipi, (6)
Florida, Utah, Alaska, California, Nevada } Fig. 2. Examples of operations on the attributes of the taxonomy of Figure 1.

and follow the usage of description logics, where (resp. ) corresponds to intersection (resp. union) over sets of objects.

Example 3. Figure 2 shows examples of operations on the context of bird families. The language, L is the powerset of attributes (1). Florida implies Southeast in the taxonomy, thus all bird families observed in Michigan and Florida can also be said to have been observed in Michigan and Southeast (2). To be observed in Florida is an information more precise than to be observed in Southeast, thus only the attribute Florida is kept in (3). The fact that birds are observed in Michigan or Florida can be generalized by birds which are observed in Southeast (4). The top concept contains only one attribute USA (5), and the bottom concept all minimal attributes (6).

All notions defined in LCA apply in FCA-Tax, in particular extent, intent, and concept lattice. Note that the intents of two ordered concepts c < c differ because one or more attributes are added in int(c), or because an attribute of int(c ) is replaced in int(c) by a more specific attribute in the taxonomy, or a combination of both. FCA-Tax differs from FCA in that the intents of concepts in FCA-Tax are without redundancy (see the use of M in tax in the definition of ). In a previous article [START_REF] Cellier | An algorithm to find frequent concepts of a formal context with taxonomy[END_REF] we described an algorithm for finding frequent concepts in a context with taxonomy. The algorithm is a variant of Bordat's algorithm [START_REF] Bordat | Calcul pratique du treillis de Galois d'une correspondance[END_REF] which takes care of the taxonomy for avoiding redundant intents. In this section, a generalization of this algorithm is described in order to search concept-based rules. In a first step, the relation between frequent concepts and rules is presented. In a second step, the parameterized algorithm with this filter function is described.

From Frequent Concepts to Rules

Relevant rules are rules that are frequently observed. In the general case, see for example [START_REF] Pasquier | Discovering frequent closed itemsets for association rules[END_REF], all frequent rules are searched, without any constraint on the premises and conclusions. However, in the learning case, either the premise or the conclusion is fixed by the learning target. So, one searches for frequent rules where conclusions or premises match the target. For instance, learning sufficient conditions for a target W is to search frequent rules like X → W . For example, in a context describing mushrooms it can be relevant to search properties implying that a mushroom is poisonous, i.e. X → poisonous.

As explained in Section 2, the frequency of a rule is evaluated by a statistical measure: the support. A rule cannot be more frequent than its premise or its conclusion. Indeed, let c be a concept then sup(int c ) ≥ sup(int c ∪ W ) = sup(int c → W ). This implies that only the intents of frequent concepts are good candidates to be the premises of the searched rules. Therefore, in order to learn rules, the frequent concepts that are computed by the algorithm presented in [START_REF] Cellier | An algorithm to find frequent concepts of a formal context with taxonomy[END_REF] need to be filtered. Only most frequent concepts that form relevant rules with respect to statistical measures are kept. Some statistical measures like the support, are monotonous. For instance, given two concepts c and c , c < c ⇒ sup(c) < sup(c ) holds. It means that if the support of a concept c is lower than min sup, all subconcepts of c have a support lower than min sup. Thus, it is not relevant to explore subconcepts of c.

A filter function, called FILTER, is defined in order to take into account these observations. FILTER takes two parameters, two sets of objects: ext c and ext(W ). These two parameters are sufficient to compute all statistical measures like support, confidence, lift and conviction as it is illustrated in Figure 3. Using ext c and ext(W ), we can compute ext c ∪ ext(W ), ext c ∩ ext(W ), and all complements like O \ ext c , O \ (ext c ∪ ext(W )). FILTER(ext c , ext(W )) returns two booleans: KEEP and CONTINUE. KEEP tells whether int c → W is a relevant rule with respect to statistical measures. CONTINUE allows monotonous properties to be considered. Indeed, CONTINUE tells whether there may be some subconcept c of c such that int c → W is a relevant rule. Thus FILTER gives four possibilities: 1) keep the current concept and explore subconcepts, 2) keep the current concept and do not explore subconcepts, 3) do not keep the current concept and explore subconcepts, 4) do not keep the current concept

ext c O ext(W ) conf (int c → W ) = ext c ∩ ext(W ) ext c conv(int c → W ) = ext c * O \ ext(W ) ext c ∩ (O \ ext(W )) sup(int c → W ) = ext c ∩ ext(W ) lif t(int c → W ) = ext c ∩ ext(W ) ext c * ext(W )
Fig. 3. Computing measures using the extents of a concept c and a target W .

and do not explore subconcepts. Section 4 illustrates on examples how these four possibilities are used.

Algorithm Parameterized with Function FILTER

In the first part of this subsection, the data structures used in the algorithm are briefly introduced. In the second part, the algorithm is described. In the last part, the difference with the previous algorithm is given.

The algorithm uses two data structures: incr c of a concept c and Exploration. incr c contains increments of a concept c. Apart from the top concept, each concept s is computed from a concept p(s), called the predecessor of s. Let s be a concept and p(s) be the predecessor of s then there exists a set of attributes, X, such that ext s = ext p(s) ∩ ext(X). We call X an increment of p(s), and we say that X leads from p(s) to s. All known increments are kept in a data structure incr p(s) which is a mapping from subconcepts to increments: s maps to X iff X leads to s. Notation incr p(s) [s → X] means that the mapping is overridden so that s maps to X.

Exploration contains frequent subconcepts that are to be explored. In Exploration, each concept s to explore is represented by a triple: (ext s → X, int p(s) , incr p(s) ) where ext s = ext(int p(s) ∪ X) = ext p(s) ∩ ext(X) and ext s ≥ min sup, which means that X is an increment from p(s) to s. An invariant for the correction of the algorithm is

∀c concept : incr c ⊆ {s → X | ext s = ext c ∩ ext(X) ∧ ext s ≥ min sup} .
Thus, all elements of incr c are frequent subconcepts of c. An invariant for completeness is

∀c, s concepts : (ext s ⊂ ext c ∧ ext s ≥ min sup ∧ ¬∃X ⊂ T : s → X ∈ incr c ) =⇒ (∃s a concept : ext s ⊂ ext s ⊂ ext c ∧ ∃X ⊂ T : s → X ∈ incr c ) .
Thus, all frequent subconcepts of c that are not in incr c are subconcepts of a subconcept of c which is in incr c . Algorithm Explore concepts allows frequent concepts of a context with taxonomy to be filtered with the generic function FILTER previously introduced. Some examples of instantiation of the function FILTER are given in section 4.

Algorithm 1 Explore concepts

Require: K, a context with a taxonomy TAX; and min sup, a minimal support Ensure: Solution, the set of all frequent concepts of K with respect to min sup, and FILTER 1: Solution := ∅ 2: Exploration.add(O → , ∅, ∅) 3: while Exploration = ∅ do 4:

let (exts → X, int p(s) , incr p(s) ) = maxext(Exploration) in 5:

(KEEP, CONTINUE) := FILTER(exts, ext(X)) 6:

if KEEP or CONTINUE then 7:

ints := (int p(s) ∪tax X) The concept lattice is explored top-down, starting with the top of the lattice, i.e. the concept labelled by all objects (i.e. the concept) (line 2). At each iteration of the while loop, an element of Exploration with the largest extent is selected (line 4): (ext s → X, int p(s) , incr p(s) ). This element represents a concept s which is tested with the function FILTER (line 5). At line 7, the intent of s is computed by supplementing (int p(s) ∪ tax X) with successors of X in the taxonomy. The redundant attributes are eliminated thanks to ∪ tax .

∪tax {y ∈ succ + tax (X) | exts ⊆ ext({y})} 8: if CONTINUE then 9: incrs := {c → X | ∃c : c → X ∈ incr p(s) ∧ c = exts ∩ c ∧ c ≥
Then the increment of s are computed; incr s is computed by exploring the increments of p(s) (step 9) and the successors of the attributes of X in the taxonomy (steps 10-15). Note that increments of p(s) can still be increments of s. For instance, if p(s) > s, p(s) > s , and s > s , the increment of p(s) which leads to s is also an increment of s that leads to s . If these increments are relevant with respect to FILTER, they are added to Exploration (lines 16-18).

Finally if s is relevant with respect to FILTER, it is added to Solution (line 21).

The difference between the algorithm in [START_REF] Cellier | An algorithm to find frequent concepts of a formal context with taxonomy[END_REF] and the algorithm presented here is the addition of the function FILTER that allows frequent concepts to be filtered and exploration to be stopped. If function FILTER always returns (KEEP = true, CONTINUE=true), then all frequent concepts are eventually computed.

Example 5. Illustration of the computation of Exploration is as follows. The taxonomy is presented in Figure 4; Figure 5 shows the explored lattice. We assume min sup=3. The first 2 steps of computation are explained. Initially, Exploration is:

-Exploration = {(O → , ∅, ∅)}.
First step: the top of the lattice is explored, i.e. s=c 0 . Increments of s are computed from the taxonomy only, as there is no predecessor concept: Second step: an element of Exploration with the largest possible extent is explored: s = c 2 , p(s) = c 0 . In order to compute incr c2 , we have to consider the elements of incr c0 and the elements in the taxonomy.

-incr c0 = { {o 3 , o 4 , o 7 , o 8 , o 9 , o 10 } → {b}, {o 1 , o 2 , o 7 , o 8 , o 10 } → {a},
-

incr c2 = { {o 7 , o 8 , o 10 } → {a}, {o 7 , o 9 , o 10 } → {c, d}, {o 8 , o 10 } → {e}} /////////////// -Exploration = {( {o 1 , o 2 , o 7 , o 8 , o 10 } → {a}, ∅, incr c0 ), ({o 5 , o 6 , o 7 , o 9 ,
o 10 } → {c}, ∅, incr c0 ), ({o 7 , o 9 , o 10 } → {c,d}, {b}, incr c2 ), ({o 7 , o 8 , o 10 } → {a}, {b}, incr c2 )}.

In the second step, attributes d and e are introduced as successors of attributes b, and attributes a and c are introduced as increments of c 0 , the predecessor of c 2 .

Increment {e} is eliminated because it leads to an unfrequent concept. Attributes c and d are grouped into a single increment because they lead to the same subconcept. This ensures that computed intents are complete.

Comparison with Bordat's algorithm

The algorithm presented in the previous section is based on Bordat's algorithm. Like in Bordat's version, our algorithm starts by exploring the top concept. Then for each concept s explored, the subconcepts of s are computed; this corresponds to the computation of incr s . Our algorithm uses the same data structure to represent Solution, i.e. a trie. The differences between our algorithm and Bordat's are: 1) the strategy of exploration, 2) the data structure of Exploration and 3) taking into account the taxonomy.

In our algorithm, 1. we first explore concepts in Exploration with the largest extent. Thus, it is a top-down exploration of the concept lattice, where each concept is explored only once. Contrary to Bordat, it avoids to test if a concept has already been found when it is added to Solution. 2. Whereas in Bordat's algorithm Exploration is represented by a queue that contains subconcepts to explore, in our version the data structure of Exploration elements is a triple: (ext s → X, int p(s) , incr p(s) ) where incr p(s) avoids to test all attributes of the context when computing increments of s. Indeed, if an increment X is not relevant for p(s) it cannot be relevant for s, because ext s ⊂ ext p(s) and thus (ext s ∩ ext(X)) ⊂ (ext p(s) ∩ ext(X)). Thus, the relevant increments of the predecessor of s are stored in incr p(s) and are potential increments of s. In Exploration, a concept cannot be represented several times. When a triple representing a concept c is added to Exploration, if c is already represented in Exploration, the new triple erases the previous one. 3. The attributes can be structured in a taxonomy. This taxonomy is taken into account during the computation of the increments and the intents. Using ∪ tax instead of the plain set-theoretic union operation allows computed intents to be without redundancy. Another benefit is that it makes computation more efficient. For instance, when the taxonomy is deep, a lot of attributes can be pruned without testing.

Instantiations of the Parameterized Algorithm

In the previous section, the presented algorithm is parameterized with a filter function in order to permit the computation of concept-based rules in FCA-Tax.

In this section, we show two instantiations of the filter function to learning. The first one allows sufficient conditions to be computed. Sufficient conditions are premises of rules where the conclusion (the target), W , represents the positive examples. In other words, the searched rules are of the form X → W .

The second one allows incompatible conditions to be computed. Incompatible conditions are premises of rules where the conclusion (the target), W , is the negation of the intent of positive examples. In other words, the searched rules are of the form X → ¬W .

Computing sufficient conditions

In the generation of sufficient conditions, the learning objective, W , is the target of the rules to be learned. For computing sufficient conditions, one must determine what conjunctions of attributes, X, implies W , i.e. the intents X of concepts such that the rule X → W has a support and a confidence greater than the thresholds min sup and min conf . Sufficient conditions can be computed with the algorithm described in Section 3 that filters all frequent concepts of a context, by instantiating the filter function with:

FILTER sc (ext s , ext(W )) = (KEEP = sup(int s → W ) ≥ min sup ∧ conf (int s → W ) ≥ min conf, CONTINUE = sup(int s → W ) ≥ min sup)
It implies three possible behaviours of the algorithm.

1. The concept s is relevant, i.e. the rule int s → W has a support and a confidence greater than the thresholds. s is a solution and has to be kept, and its subconcepts are potential solutions and have to be explored. Thus FILTER sc (ext s ) returns (true, true). 2. The concept s has a support greater than min sup but a confidence lower than min conf . s is not a solution but the confidence is not monotonous and thus subconcepts of s can be solutions. FILTER sc (ext s ) returns (f alse, true). 3. The concept s has a support lower than min sup. s is not a solution. As the support is monotonous, i.e. the support of a subconcept of s is lower than the support of s, subconcepts of s cannot be solutions. FILTER sc (ext s ) returns (f alse, f alse).

FILTER sc (ext s , ext(W )) can be expressed in terms of extent by simply applying the definitions of support and confidence seen in Section 2. The filter function can therefore be defined by :

FILTER sc (ext s , ext(W )) = (KEEP = ext s ∩ ext(W ) ≥ min sup ∧ ext s ∩ ext(W ) ext s ≥ min conf, CONTINUE = ext s ∩ ext(W ) ≥ min sup)
Note that it is easy to use other statistical indicators like lift or conviction, by adding conditions in the evaluation of KEEP.

Computing incompatible conditions

In the case of incompatible conditions, the learning objective, W , is the negation of the target of the rules to be learned. For computing incompatible conditions, one must determine what conjunctions of attributes, X, implie ¬W . In other words, one looks for the intents X of concepts such that the rule X → ¬W has a support and a confidence greater than the thresholds min sup and min conf .

Incompatible conditions can be computed with the algorithm described in Section 3 by instantiating the filter function with:

FILTER ic (ext s , ext(W )) = (KEEP = sup(int s → ¬W ) ≥ min sup ∧ conf (int s → ¬W ) ≥ min conf, CONTINUE = sup(int s → ¬W ) ≥ min sup)
As for sufficient conditions, this can be expressed in terms of extents, using the definitions of support and confidence. The filter function to compute incompatible conditions can thus be defined by :

FILTER ic (ext s , ext(W )) = (KEEP = ext s ∩ (O \ ext(W )) ≥ min sup ∧ ext s ∩ (O \ ext(W )) ext s ≥ min conf, CONTINUE = ext s ∩ (O \ ext(W )) ≥ min sup)
5 Experiments

Experimental settings. The algorithm is implemented in CAML (a functional programming language of the ML family) inside the Logic File System LISFS [START_REF] Padioleau | A logic file system[END_REF]. LISFS implements the notion of Logical Information Systems (LIS) as a native Linux file system. Logical Information Systems (LIS) are based on LCA. In LISFS, attributes can be ordered to create a taxonomy (logical ordering). The data structures which are used allow taxonomies to be easily manipulated. For more details see [START_REF] Padioleau | A logic file system[END_REF]. We ran experiments on an Intel(R) Pentium(R) M processor 2.00GHz with Fedora Core release 4, 1GB of main memory.

We tested the parameterized algorithm with two contexts: "Mushroom" and "Java". The Mushroom benchmark3 contains 8 416 objetcs which are mushrooms. The mushrooms are described by properties such as whether the mushroom is edible or poisonous, the ring number, or the veil color. The context has 127 properties. The Java context4 taken from [START_REF] Sigonneau | Indexation multiple et automatisée de composants logiciels[END_REF], contains 5 526 objects which are the methods of java.awt. Each method is described by its input and output types, visibility modifiers, exceptions, keywords extracted from its identifiers, and keywords from its comments. The context has 1 624 properties, and yields about 135 000 concepts.

Quantitative Experiments. Many efficient algorithms computing association rules exist5 . None of them allow a taxonomy to be taken into account. We do not pretend that our algorithm is faster. The objectives of this section are rather to show 1) that our algorithm is reasonably efficient, 2) that given an algorithm which searches for association rules, the additional mechanisms described in Sections 3 and 4 do not cause any significant slowdown in the presence of a taxonomy, and 3) that they can even improve efficiency in certain cases.

We evaluate our algorithm on the mushroom benchmark, computing frequent concepts. It enables us to compare our algorithm's performance with Pasquier et al.'s CLOSE algorithm, using the figures published in Pasquier's PhD thesis [START_REF] Pasquier | Data Mining : Algorithmes d'extraction et de réduction des règles d'association dans les bases de données[END_REF]. For the same task, execution times are of the same order for both algorithms. For instance, with min sup = 5% CLOSE computation time is about 210s and our algorithm computation time is 290.8s; with min sup = 20% CLOSE computation time is about 50s and our algorithm computation time is only 26.2s. Hence, even without a taxonomy our algorithm does not introduce any slowdown.

On the Java context, we measured the computation time of the frequent concepts, in order to show the impact of the taxonomy on the computation. The taxonomy is derived, for the largest part, from the class inheritance graph, and, for a smaller part, from a taxonomy of visibility modifiers that is predefined in Java. The result is given in Table 2. The third column of that table contains the execution times in seconds of algorithm when the taxonomy is taken into account. The fourth column corresponds to the execution times when the context is a priori completed with the elements of the taxonomy. When min sup = 5%, 189 frequent concepts are computed in 8s with taxonomy, whereas they are computed in 16s without taxonomy. When min sup = 2.5%, 2300 frequent concepts are computed in 55s with taxonomy, whereas they are computed in 54s without taxonomy. It is explained by the fact that the Java context has few very frequent concepts. Thus pruning using the taxonomy when min sup is greater than 5% occurs very early in the traversal of the concept lattice. For min sup = 2.5%, pruning are less impact, computation time is therefore equivalent with or without taxonomy.

Note that from a qualitative point of view, with this context, using the taxonomy allows the number of irrelevant attributes in the intents to be reduced by 39% for min sup = 5%.

Conclusion

In this article we have proposed an algorithm parameterized by a filter function to explore frequent concepts in a context with taxonomy in order to learn association rules. We have described how to instantiate the filter function in order to find premises of rules where the target are positive examples (sufficient conditions) and negative examples (incompatible conditions). Quantitative experiments have shown that, in practice, taking a taxonomy into account does not negatively impact the performance and can even make the computation more efficient.

The advantage of the presented method is to avoid the redundancies that a taxonomy may introduce in the intents of the frequent concepts.

  Example 4. ext(Oregon, Calif ornia) = {Alcidae, Strigidae} int(Alcedinidae, Corvidae) = {P acif ic, Endangered} sup(Oregon, Calif ornia → T hreatened) = 2 conf (Calif ornia → T hreatened) = 0.5 Note in the example about the computation of intent that Corvidae has not explicitly the property P acif ic but the property Hawai. But in the taxonomy the property Hawai implies the property P acif ic.

Fig. 4 .

 4 Fig. 4. Taxonomy of the example. Fig. 5. Concept lattice.

Table 1 .

 1 Context of threatened or endangered bird families in the USA

  Definition 3 defines the logical versions of extent and intent. The extent of a logical formula f is the set of objects in O whose description is subsumed by f . The intent of a set of objects O is the most precise formula that subsumes all descriptions of objects in O. Definition 4 gives the definition of a logical concept.

					USA
		Pacific	Southwest	Great Lakes Big Rivers	Southeast	Northeast	Mountain Prairie	Region 7	Region 8
			Arizona	Mississipi	Florida	Utah	Alaska
	Hawai	Washington	Oregon	Michigan				California	Nevada
			Fig. 1. Taxonomy of USA states and regions.
	Definition 1 (logical context). A logical context is a triple (O, L, d) where O is a set of objects, L is a logic (e.g. proposition calculus) and d is a mapping from O to L that describes each object by a formula.
	Definition 2 (logic). A logic is a 6-tuple L = (L, , , , , ⊥) where
	-L is the language of formulas,
	-	is the subsumption relation,
	-	and are respectively conjunction and disjunction,
	-	and ⊥ are respectively tautology and contradiction.
	Definition 3 (extent, intent). Let K = (O, L, d) be a logical context. The definition of extent and intent are:

  {o 5 , o 6 , o 7 , o 9 , o 10 } → {c}} -Exploration = {({o 3 , o 4 , o 7 , o 8 , o 9 , o 10 } → {b}, ∅, incr c0 ), ({o 1 , o 2 , o 7 , o 8 ,

o 10 } → {a}, ∅, incr c0 ), ({o 5 , o 6 , o 7 , o 9 , o 10 } → {c}, ∅, incr c0 )}.

Table 2 .

 2 Number of concepts and execution times (in seconds) for different values of min sup.

	min sup Number of concepts Execution time	Execution time
			(with taxonomy) (without taxonomy)
	(%)		(s)	(s)
	20	35	4.5	12.2
	15	48	4.8	13.2
	10	54	5.2	13.6
	7.5	86	5.8	14.8
	5	189	7.9	16.3
	2.5	2300	55.0	54.1

http://anthro.palomar.edu/animal/table humans.htm

http://ecos.fws.gov/tess public/CriticalHabitat.do?listings=0&nmfs=1

Available at ftp://ftp.ics.uci.edu/pub/machine-learning-databases/mushroom/

Available at http://lfs.irisa.fr/demo-area/awt-source/,

some of them are available on the FIMI web site http://fimi.cs.helsinki.fi/src