Jean-François Boulicaut

Jérémy Besson

Actionability and formal concepts: a data mining perspective

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Many application domains can provide possibly huge boolean matrices whose rows denote objects and columns denote attributes (see Table 1 for toy examples). Mining such binary data, or formal contexts in the terminology of Formal Concept Analysis (FCA) [START_REF]Formal Concept Analysis[END_REF], has been studied extensively. Indeed, popular data mining techniques have been designed for set pattern extraction (e.g., mining frequent itemsets or association rules, mining frequent closed itemsets or other condensed representations of frequent patterns [START_REF] Boulicaut | Inductive databases and multiple uses of frequent itemsets: the cInQ approach[END_REF][START_REF] Calders | A survey on condensed representations for frequent sets[END_REF]). We are interested in bi-set mining, i.e., the computation of local patterns that are sets of objects and sets of attributes being somehow "associated". Clearly, a formal concept is an interesting type of bi-set that satisfy a local constraint: its attribute set (or intent) is the maximal set of attributes that are true for each object of its associated supporting set of objects (or extent). Here, locality refers to the fact that checking whether a bi-set is a formal concept or not can be performed independently of the other patterns holding in the data. An example of a formal concept in r 1 from Table 1 is ({o 1 ,o 2 ,o 3 ,o 4 }, {p 1 ,p 2 }). Notice that this paper does not consider FCA as such and that, for instance, we are not really interested in the underlying concept lattice itself. Instead, we consider collections of formal concepts as collections of patterns. Also, we do not use formal concepts as condensed representations for collections of association rules (see [START_REF] Valtchev | Formal concept analysis for knowledge discovery and data mining: The new challenges[END_REF] for a recent survey covering such issues).

Table 1. r1 (left) -r2 (right) p1 p2 p3 p4 o1 1 1 0 0 o2 1 1 0 0 o3 1 1 0 0 o4 1 1 1 1 o5 0 0 1 1 o6 0 0 1 1 p1 p2 p3 p4 o1 1 1 0 0 o2 1 0 1 0 o3 1 1 0 1 o4 1 1 1 1 o5 0 0 1 0 o6 0 0 1 1

Let us introduce a couple of motivating applications for our perspective on formal concept mining (see, e.g., [START_REF] Besson | Constraint-based formal concept mining and its application to microarray data analysis[END_REF]). The objects can denote biological samples and the attribute can denote boolean gene expression properties, e.g., the fact that a given gene is over-expressed in a given sample. In such a case, the boolean properties have to be derived from the continuous values measured by, e.g., the microarray technology, and a formal concept provides an hypothesis on a maximal group of genes that have the same expression property in a given group of biological samples. A second example would be to consider that some transcription factors (i.e., the proteins which regulate gene expression) are the studied objects for which we record whether they can bind or not on the promoter sequence of some studied genes. Here again, a formal concept can be interpreted as an hypothesis on a maximal set of genes whose co-expression might be explained by its associated set of transcription factors. Clearly, one of the motivations for collecting gene expression data is indeed to be able to discover such hypothesis that correspond, from a biological perspective, to putative synexpression groups, transcription modules, regulation pathways, etc.

In this paper, we are interested in the various application domains for which, given a binary data set, one can consider that its formal concepts are a priori interesting statements about the data. In theory, computing formal concepts is exponential in the smallest dimension of the data matrix (i.e., the number of objects or the number of attributes). An important question concerns the tractability of their computation for practical applications. Given the major effort of the last decade, it turns out that computing collections of formal concepts that hold in large binary matrices can be feasible. Researchers have designed algorithms that compute complete collections of formal concepts [START_REF] Kuznetsov | Comparing performance of algorithms for generating concept lattices[END_REF]. Since these patterns are built on closed sets, the extensive research on (frequent) closed set extraction has inspired constraint-based mining of formal concepts (see, e.g., [START_REF] Stumme | Computing iceberg concept lattices with titanic[END_REF]): every formal concept which furthermore satisfies a size constraint on one of its components (e.g., a minimal size for its intent or its extent) can be extracted efficiently. This is however not really satisfactory when considering that our ultimate goal is to mine actionable patterns, i.e., relevant formal concepts that can indeed be interpreted by human experts to catalyze knowledge discovery. Real data sets can hold hundreds of thousands of formal concepts: it is clear that looking for actionable ones among the many spurious or irrelevant ones is extremely hard or even impossible. In fact, it is interesting to look at one fundamental limitation of Knowledge Discovery processes based on formal concepts. Within such local patterns, the strength of the association of the two set components is often too strong in real-life data. Indeed, errors of measurement and boolean encoding techniques can lead to "erroneous" zero or one values. Unexpected zero values give rise to a combinatorial explosion of the number of formal concepts because interesting patterns are split into less relevant ones. For example, let us consider the data from Table 1. Assume that r 1 is a reliable representation of a phenomenon but that data collection and preprocessing lead to r 2 instead (i.e., some noise has been introduced), the number of formal concepts in r 2 is approximately twice larger than in r 1 . While this concerns zero values that may be one values, we can also consider what happens in the reverse situation: the intuition is that when some zero values have been encoded as one values by error, many "small" formal concepts may hold. Therefore, we need to avoid computing too small patterns but also we have to somehow relax that no exception (zero value) can be accepted, i.e., what we call fault-tolerance. For instance, a bi-set like ({o 1 ,o 2 ,o 3 ,o 4 }, {p 1 ,p 2 }) is not a formal concept in r 2 but it may be considered as a relevant pattern: its objects and attributes are strongly associated (only one zero value) and, furthermore, its "outside" objects and attributes contain more than one zero value.

Our contribution here is to consider how some data mining researchers have designed more or less pragmatic methods to address these problems. We avoid to produce the technical details that are available from the referenced papers. We will discuss the DMiner proposal for constraint-based mining of formal concepts in the challenging case where, for instance, we want to "push" size constraints on both dimensions [START_REF] Besson | Constraint-based mining of formal concepts in transactional data[END_REF][START_REF] Besson | Constraint-based formal concept mining and its application to microarray data analysis[END_REF]. We will also consider different approaches for designing fault-tolerant patterns based on formal concepts [START_REF] Besson | Mining formal concepts with a bounded number of exceptions from transactional data[END_REF][START_REF] Pensa | From local pattern mining to relevant bi-cluster characterization[END_REF][START_REF] Besson | Mining a new fault-tolerant pattern type as an alternative to formal concept discovery[END_REF]. The survey paper [START_REF] Besson | Constraint-based mining of fault-tolerant patterns from boolean data[END_REF] is a discussion on the needed trade-off between extraction feasibility, completeness, relevancy, and ease of interpretation of such fault-tolerant pattern types. Notice also that [START_REF] Besson | Constraint-based mining of fault-tolerant patterns from boolean data[END_REF] contains empirical results on both synthetic and real data.

Section 2 discusses the DMiner solution for constraint-based mining of formal concepts. In Section 3, we consider the obstacles and present some available solutions for actionable pattern discovery based on formal concepts. Section 4 briefly concludes on some current open issues in that area.

Formal Concept Mining

Let O denotes a set of objects and P denotes a set attributes (or properties). In Table 1

, O = {o 1 , ••• ,o 6 } and P = {p 1 , ••• ,p 4 }.
A data set is the materialization of a binary relation r ⊆O×P.W ew r i t e( o i ,p j ) ∈ r to denote that property j holds for object i. Boolean matrices like r 1 and r 2 in Table 1 are classical representations for such relations.

Formal concepts can be considered as bi-sets, i.e., couples of sets (X, Y )f rom 2 O × 2 P that satisfy a constraint denoted C FC (X, Y ). The definition of such a constraint might be expressed in terms of Galois operators and closures. In this paper, let us specify it in terms of the conjunction of a density constraint (first conjunct) and a relevancy constraint (second and third conjuncts), following the presentation from [START_REF] Besson | Mining a new fault-tolerant pattern type as an alternative to formal concept discovery[END_REF].

Definition 1 (Formal Concept). Ab i -s e t(X, Y ) ∈ 2 O × 2 P is a formal con- cept in r if it satisfies the constraint C FC (X, Y ) ≡ (∀x ∈ X, ∀y ∈ Y (x, y) ∈ r) ∧ (∀x ∈O\X, ∃y ∈ Y s.t. (x, y) ∈ r) ∧ (∀y ∈P\Y, ∃x ∈ X s.t. (x, y) ∈ r).
Informally, it means that for a formal concept (X, Y ), if we perform permutations of rows and columns such that all the elements from X (resp. Y )a r e contiguous, we observe a maximal rectangle of true values (no zero value inside, at least one zero value outside). Another useful analogy to understand the semantics of formal concepts is to consider them as bi-cliques in the bi-partite graphs represented by the boolean matrix. Computing every formal concept that holds within a boolean matrix is NP-hard. As soon as none of the dimensions is small, this extraction task is not feasible. Furthermore, when the computation is tractable, we often get a huge amount of formal concepts (e.g., millions) even in rather small data sets. As we mentioned in our introduction, this is definitively not acceptable for actionable pattern discovery. Constraint-based mining is a partial but impressive solution to both problems, i.e., computational complexity and relevancy. The idea is that the analyst can often exploit some background knowledge to specify declarative constraints that may hold for the extracted formal concepts of interest. It happens that some of these user-defined constraints can be exploited (say "pushed deeply") by the mining algorithm to prune efficiently the search space. For example, we may need patterns with a minimal number of elements on both dimensions (a counterpart of the popular minimal frequency constraint for itemset mining [START_REF] Goethals | Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations FIMI 2003[END_REF]) and/or patterns covering at least a given number of elements of r (intuitively, a minimum area constraint for the associated "rectangle"). As a result, when considering knowledge discovery processes based on formal concepts, we are generally computing collections of bi-sets that satisfy not only C FC but also a user-defined constraint C UD :

{(X, Y ) ∈ 2 O × 2 P |C FC (X, Y ) ∧C UD (X, Y )}
Figure 1 provides examples of well-known user-defined constraints where α and β denote some thresholds, a ∈O, b ∈P, E ⊆O,a n dE ′ ⊆P are constraint parameters. For instance, C 1 size ∧C 2 size or C area are two different constraints to specify that patterns have to be "large enough". Also, C mean is just one example of a constraint which enforces that the average of an external positive value associated to each element of the extent is greater than a given threshold.

Not every constraint can be processed efficiently. We have a special interest for monotonic and anti-monotonic constraints (see Definition 2) that have nice Following a path in an enumeration tree for candidate patterns, an antimonotonic constraint is satisfied for all the patterns before a specific pattern and not satisfied afterwards. A popular example is the anti-monotonicity of a minimal frequency constraint which specifies that the size of the extent has to be greater than a given threshold (i.e., C 1 size ). This constraint can efficiently reduce the search-space and remove spurious patterns whose extent is too small. However, in the many applications where the data set is large on both dimens i o n sa n dw h e nt h ed e n s i t yi nt e r m so ft r u ev a l u e si sh i g h ,t h eo n l yw a yt o achieve tractability seems to be an increase of the minimal size threshold for the extent. Doing so, we clearly loose a priori interesting formal concepts (the larger the extent, the smaller the intent, and vice versa). Therefore, we may want to use other constraints like, for example, minimal size constraint on both the intents and the extents, i.e., conjunctions C 1 size ∧C 2 size . Unfortunately, using the standard enumeration on formal concepts (enumeration of the intent and computation of the extend), most algorithms can only exploit anti-monotonic constraints on the intent and monotonic constraints on the extent, i.e., a conjunction like |X| >α∧|Y | <β(say C 1 size ∧¬C 2 size ). Furthermore, it is not that simple to exploit constraints like C area , C mean , C member ,a n dC inter .E v e n though they can be used to capture important expectation from the analysts, these constraints are neither anti-monotonic nor monotonic.

CUD(X, Y ) C 1 size ≡| X| >α C 2 size ≡| Y | >α Carea ≡| X|×|Y | >α Cmean ≡ i∈X Val + (i)/|X| >α C member ≡ a ∈ X ∧ b ∈ Y Cinter ≡| X ∩ E| >α∧|Y ∩ E ′ | <β
The DMiner algorithm is a depth-first search algorithm inspired by both Ganter's algorithm [START_REF] Ganter | Two basic algorithms in concept analysis[END_REF] and DualMiner [START_REF] Bucila | DualMiner: A dual-pruning algorithm for itemsets with constraints[END_REF]. The principle of Ganter's algorithm enables to identify from an extracted formal concept the smallest formal concept that may follow it. Doing so, we can avoid the generation of many sets that are not closed, i.e., which can not correspond to formal concepts. On the other hand, for efficiency purposes, we have to follow the order related to the standard set inclusion. Given the data from Table 2, it is far more efficient to generate the formal concept ({o

1 ,o 2 ,o 3 }, {p 1 ,p 2 ,p 3 ,p 4 }) from ({o 1 ,o 2 ,o 3 ,o 5 }, {p 1 ,p 3 })t h a nf r o m( {o 2 ,o 3 ,o 4 }, {p 9 ,p 10 }). The pattern ({o 1 ,o 2 ,o 3 ,o 5 }, {p 1 ,p 3 })
already contains a lot of information that can be used to Attributes p1 p2 p3 p4 p5 p6 p7 p8 p9 p10 o1 1 1 1 1 0 1 1 0 0 0 o2 1 1 1 1 0 0 0 0 1 1 o3 1 1 1 1 0 0 0 0 1 1 o4 0 0 0 0 1 1 1 1 1 1 o5 1 0 1 0 1 1 1 1 0

0 generate ({o 1 ,o 2 ,o 3 }, {p 1 ,p 2 ,p 3 ,p 4 }), e.g., we know that ({o 1 ,o 2 ,o 3 }, {p 1 ,p 3 }) holds in r 3 because it is "included" in ({o 1 ,o 2 ,o 3 ,o 5 }, {p 1 ,p 3 })whichisaformal concept.
It means that we do not have to scan all the data corresponding to the new patterns to be extracted. In our running example, we only need to scan the data corresponding to ({o 1 ,o 2 ,o 3 }, {p 2 ,p 4 }). It is even more crucial when large data sets are considered. Thus, we adopt a binary enumeration of the smallest set (O or P) and the other set is computed by means of the Galois connection. This enumeration combines both Ganter's principle and a prefix-based enumeration.

It is important to exploit constraints not only to increase the relevancy of the computed patterns but also to increase computational efficiency. Most of the available algorithms can push monotonic and/or anti-monotonic constraints according to set inclusion on one dimension. We however argued in the previous section that this is not enough. Unlike most of the formal concept mining algorithms, DMiner does not consider that each candidate is only represented by means of two sets, i.e., the intent and the extent. The enumerated set, let us say the intent, is split into two sets, the first one representing the set of elements that belong to any formal concept extracted from the current candidate and the second one containing the elements that still have to be enumerated (see the inspiring principle in [START_REF] Bucila | DualMiner: A dual-pruning algorithm for itemsets with constraints[END_REF]). The two sets are the bottom and the top of a lattice which represents the current search space. For example, we may have a candidate (o 1 o 2 o 3 o 5 , (p 1 ,p 1 p 2 p 3 )) where the intent is represented by two sets {p 1 } and {p 1 p 2 p 3 } instead of only one set {p 1 p 2 p 3 }. By this way during the enumeration we always know precisely which search-space is related to the current candidate and thus increase the number of constraints the algorithm can handle. In our example the candidate is supported by the extent {o 1 ,o 2 ,o 3 ,o 5 } and it represents all the attribute sets Y (intents

) such that {p1}⊆ L Y ⊆ L {p 1 ,p 2 ,p 3 } where (X, Y ) ⊆ L (X ′ ,Y ′ ) ⇒ X ⊂ X ′ ∧ Y ⊂ Y ′ , i.e.
, the attribut sets {p 1 }, {p 1 ,p 2 }, {p 1 ,p 3 } and {p 1 ,p 2 ,p 3 } in our example. Notice that a candidate of the form (O, (X, X)) denotes the bi-set (O, X).

This pattern representation enables to push a larger class of constraints than only the anti-monotonic constraints. Indeed, each candidate denotes a search space in the form of an attribute lattice with its associated object set. For example, let us consider candidate C =( o 1 o 2 o 3 o 5 , (p 1 ,p 1 p 2 p 3 p 4 )) in r 3 , each formal concept derived from C which contains p 1 contains at most the attributes from {p 1 ,p 2 ,p 3 ,p 4 } and its associated object set is included in {o 1 ,o 2 ,o 3 ,o 5 }.I t enables to push difficult constraints like C area and C mean which are neither monotonic nor anti-monotonic. Indeed, since we have an attribute lattice, we can compute bounds for some constraints. For instance, we can see that the area of

C is between |{o 1 ,o 2 ,o 3 ,o 5 }|×|{p 1 }| =4and|{o 1 ,o 2 ,o 3 ,o 5 }|×|{p 1 ,p 2 ,p 3 ,p 4 }| = 16.
If we are looking for formal concepts with an area of size at least 17 or of size at most 3, then pattern C can be pruned safely, i.e., it can not lead to acceptable formal concepts.

We adopted simple arrays as data structure to store the sets of objects and attributes. A time complexity analysis shows that it is as efficient as the other more complex data structures used in depth-first search algorithms. Finally, to check whether a set X is closed, DMiner does not have to scan all the sets from P\X. Indeed, only attributes which have been removed from the search space by enumeration have to be checked. Instead of going into much details, let us provide two DMiner executions (see Figure 2 and Figure 3) on the data sets given in Table 3. In Figure 2 To investigate the efficiency of DMiner, we studied its complexity using the time delay, i.e., the complexity to go from one solution to the next one [START_REF] Besson | Découvertes de motifs pertinents pour l'analyse du transcriptome: application à l'insulino-résistance[END_REF]. DMiner time delay is in the worst case equal to O(n 2 m)wheren is the size of the enumerated set and m is the size of the other one. This complexity is the same as Table 3. Extraction contexts r4 (left) and r5 (right) for Ganter's algorithm [START_REF] Ganter | Two basic algorithms in concept analysis[END_REF]. The time delay in average is O(n-log 2 (K)+1)O(mn) where K is the number of formal concepts in the data set. It is between O(nm) and O(n 2 m) according to K.T h i si sa ni n t e r e s t i n gr e sult when considering the use of DMiner on data sets in which many formal concepts hold.

p1 p2 o1 0 1 o2 1 1 o3 1 0 p1 p2 p3 o1 0 0 1 o2 0 1 0 o3 1 0 1 (o1o2o3,( ∅,p1p2)) p1 (o1o2o3, (∅,p2))
To refer to one concrete example, let us recall the application described in [START_REF] Besson | Constraint-based formal concept mining and its application to microarray data analysis[END_REF]. It concerns the analysis of a data set that records (a) the existence of putative binding sites of 94 transcription factors on the promoter sequences of 304 genes (selection of human genes), and (b) the over-expression property of these same genes in 10 biological simples (individuals). In other terms, the boolean context implies 104 objects (94 transcription factors and 10 biological situations, more precisely 5 for healthy individuals and 5 for diabetic patients) and 304 genes. Formal concept discovery from such a boolean context is already hard. Notice also that the obtained boolean context was rather dense in terms of true values (17% of the cells containing a true value). In such a situation, even efficient algorithms for mining frequent closed sets can turn to be intractable. This data set is particular: there are very few frequent formal concepts with a relative frequency threshold above 0.1 on genes (5 534 patterns) and then the number of formal concepts increases very fast. Without any constraint, we get more than five million formal concepts within a few minutes. In this context, extracting actionable formal concepts needs for a very low frequency threshold, otherwise almost no formal concept can be computed. Notice that actionable patterns corresponding to interesting biological hypothesis have been found by means of formal concepts holding in this data set [START_REF] Besson | Découvertes de motifs pertinents pour l'analyse du transcriptome: application à l'insulino-résistance[END_REF][START_REF] Besson | Constraint-based formal concept mining and its application to microarray data analysis[END_REF].

Figure 4 shows the running time of formal concepts extractions in the biological data set with varying the minimal frequency threshold. The competitors in the experiment are three different algorithms used for computing frequent closed sets, namely ac-miner [START_REF] Boulicaut | Free-sets: a condensed representation of boolean data for the approximation of frequency queries[END_REF], closet [START_REF] Pei | CLOSET an efficient algorithm for mining frequent closed itemsets[END_REF] and Charm [START_REF] Zaki | CHARM: An efficient algorithm for closed itemset mining[END_REF].

Looking for Actionable Patterns

Let us now come back on our main goal that is actionable pattern discovery based on collections of formal concepts. The challenge is to mine relevant formal concepts that can indeed be interpreted by human experts to catalyze knowledge discovery. In case this is not possible, we may also look for applicationindependent and/or application-dependent post-processing techniques that can be applied on formal concepts to support the discovery of actionable patterns.

-When, among other things, a data set captures correctly a phenomenon of interest, collections of formal concepts can be huge and they may contain large collections of spurious patterns (false positives) and/or irrelevant patterns w.r.t. domain knowledge. This is somehow inherent to (unsupervized) local pattern discovery techniques. The two main directions of research to improve this situation concern (a) the use of randomization techniques for statistical validity assessment for the extracted patterns (see, e.g., [START_REF] Gionis | Assessing data mining results via swap randomization[END_REF]) and (b) the use of user-defined constraints to specify subjective interestingness issues based on domain knowledge (e.g., using C member or C inter primitive constraints). -When considering the problem of erroneous true values (the property should not be satisfied but we record that it is satisfied), assuming that this is fundamentally rare, many "small" formal concepts may hold. Therefore, we need to avoid computing these too small patterns by using minimal size or minimal area constraints (See Section 2). In practice, using these constraints C 1 size , C 2 size and/or C area can be extremely efficient. -When considering the problem of erroneous false values (the property is satisfied but we record that it is not satisfied), assuming again that this can not be too frequent, the number of extracted formal concepts will increase fast w.r.t. what it should be if the data were correct. This is a clear need for fault-tolerance and we discuss several proposals hereafter (see Section 3.1). -The number of patterns, even if only relevant ones have been collected, is indeed a problem. Knowledge discovery needs for human expert assessment of patterns and browsing or inspecting thousands of patterns is definitively not possible. The solution can come from (a) the design of pattern databases and advanced querying tools, and (b) summarization techniques based on, for instance, clustering methods. Considering problems and solutions for pattern database management is related to the emergent topic of inductive databases and will not be discussed further in this paper. Considering summarization techniques has been successfully applied (see Section 3.2).

Introducing Fault-Tolerance

We first revisit the definition of formal concepts for a fairly natural introduction of fault-tolerance. In the following, we say that a bi-set (X,

Y ) is included in a bi-set (X ′ ,Y ′ ) denoted (X, Y ) ⊆ (X ′ ,Y ′ )i ff( X ⊆ X ′ ) ∧ (Y ⊆ Y ′ ).

Definition 4 (FC). Ab i -s e t(X, Y

) ∈ 2 O × 2 P is a formal concept in r iff (2.1) ∀x ∈ X, Z l (x, Y )=0 ∧∀ y ∈ Y, Z c (y, X)=0 (2.2) ∀x ∈O\X, Z l (x, Y ) ≥ 1 ∧∀ y ∈P\Y, Z c (y, X) ≥ 1
Sub-constraint 2.1 expresses that a formal concept contains only true values. Subconstraint 2.2 denotes that formal concept relevancy is enhanced by a maximality property. It is now straightforward to introduce a declarative specification of fault-tolerance.

Definition 5 (DRBS [START_REF] Besson | Mining a new fault-tolerant pattern type as an alternative to formal concept discovery[END_REF]). Given integer parameters δ and ǫ, a bi-set

(X, Y ) ∈ 2 O × 2 P is called a DRBS pattern (Dense and Relevant Bi-Set) in r iff (3.1) ∀x ∈ X, Z l (x, Y ) ≤ δ ∧∀ y ∈ Y, Z c (y, X) ≤ δ (3.2) ∀e ∈O\X, ∀x ∈ X, Z l (e, Y ) ≥Z l (x, Y )+ǫ ∧∀ e ′ ∈P\Y, ∀y ∈ Y, Z c (e ′ ,X) ≥Z c (y, X)+ǫ (3.3) It is maximal, i.e., ∃(X ′ ,Y ′ ) ∈ 2 O × 2 P s.t. (X ′ ,Y ′ ) is a DRBS pattern and (X, Y ) ⊆ (X ′ ,Y ′ ).
DRBS patterns have at most δ false values per object and per attribute (Subconstraint 3.1) and are such that each outside object (resp. attribute) has at least ǫ false values plus the maximal number of false values on the inside objects (resp. attributes) according to Sub-constraint 3.2 .T h es i z eo faDRBS pattern increases with δ such that, when δ>0, it happens that several bi-sets are included in each other. Only maximal bi-sets are kept (Sub-constraint 3.3). Notice that δ and ǫ can be chosen differently on objects and on attributes. It is clear that when δ =0andǫ =1,DRBS ≡ FC. 4). Columns p 1 , p 2 , p 6 and p 7 contain at least two false values on X,a n do 5 contains three false values on Y (see Table 5).

o1 1 0 1 0 1 0 0 o2 1 1 1 1 0 1 0 o3 0 1 1 1 1 1 1 o4 0 0 0 1 1 1 0 o5 1 0 0 0 0 1 0 o6 1 1 1 1 1 0 0 o7 1 1 1 1 1 0 0 Table 5. Permutations on r6 to illustrate Example 1 p1 p2 p3 p4 p5 p6 p7 o1 1 0 1 0 1 0 0 o2 1 1 1 1 0 1 0 o3 0 1 1 1 1 1 1 o4 0 0 0 1 1 1 0 o6 1 1 1 1 1 0 0 o7 1 1 1 1 1 0 0 o5 1 0 0 0 0 1 0 Example 1. If δ = ǫ =1 , (X, Y )=( {o 1 ,o 2 ,o 3 ,o 4 ,o 6 ,o 7 }, {p 3 ,p 4 ,p 5 }) is a DRBS pattern in r 6 (see Table
Collections of DRBS patterns can be computed in rather small data sets by using the correct and complete algorithm DR-Miner [START_REF] Besson | Mining a new fault-tolerant pattern type as an alternative to formal concept discovery[END_REF]. It is again based on the Dual-Miner principle [START_REF] Bucila | DualMiner: A dual-pruning algorithm for itemsets with constraints[END_REF]. Notice that a preliminary approach for specifying "symmetrical" fault-tolerant formal concepts had been introduced in [START_REF] Besson | Mining formal concepts with a bounded number of exceptions from transactional data[END_REF] (i.e., the so-called αβ-concepts) and that it has been compared with the DRBS pattern domain in [START_REF] Besson | Constraint-based mining of fault-tolerant patterns from boolean data[END_REF].

Let us now consider a rather different (and say pragmatic) extension of formal concepts which is not symmetrical. It has been designed thanks to the previous work on one of the few approximate condensed representations of frequent sets, the so-called δ-free sets [START_REF] Boulicaut | Free-sets: a condensed representation of boolean data for the approximation of frequency queries[END_REF]. δ-free sets are some kind of generators whose counted frequencies enable to infer the frequency of many sets (sets included in their so-called δ-closures) without further counting but with a bounded error. The δ-freeness constraint on attributes sets has been formalized in terms of the size of the supported sets of objects (this so-called frequency has to be different from the frequency of all its subsets by at least δ). Notice also that the so-called generators in [START_REF] Pasquier | Efficient mining of association rules using closed itemset lattices[END_REF] or key patterns in [START_REF] Bastide | Mining frequent patterns with counting inference[END_REF] are special cases of δ-free sets (δ =0). The 0-closure is the classical closure operator and applying it on each 0-free set is one way to produce every closed set and thus every formal concept.

The idea for the so-called FBS patterns (Free set Based Bi-Set) is to consider bi-sets built on the δ-closure of δ-free attribute sets associated to their supporting sets of objects [START_REF] Pensa | Towards fault-tolerant formal concept analysis[END_REF][START_REF] Pensa | From local pattern mining to relevant bi-cluster characterization[END_REF]. The intuition is that it will provide strong associations between sets of objects and sets of attributes. To avoid technical details, let us just comment an example.

Example 2. If δ =1, {p 2 } is a 1-free set and ({o 2 ,o 3 ,o 6 ,o 7 }, {p 1 ,p 2 ,p 3 ,p 4 ,p 5 }) is a FBS pattern in r 6 (see Table 6). The 1-closure of {p 2 } is {p 1 ,p 2 ,p 3 ,p 4 ,p 5 } because p 1 , p 3 , p 4 ,a n dp 5 are the attributes which are almost always true (1 exception is accepted) for the objects that have the property denoted by p 2 , i.e., objects o 2 , o 3 , o 6 ,a n do 7 .

When δ=0, attribute 0-free sets are the minimal elements of the equivalence classes of the relation "has the same supporting set of objects". Then, the 0closure provides a closed set of attributes that associated to its supporting set of object gives a formal concept. In other terms, when δ =0,FBS ≡ FC.

p1 p2 p3 p4 p5 p6 p7 o2 1 1 1 1 0 1 0 o3 0 1 1 1 1 1 1 o6 1 1 1 1 1 0 0 o7 1 1 1 1 1 0 0 o1 1 0 1 0 1 0 0 o4 0 0 0 1 1 1 0 o5 1 0 0 0 0 1 0
The extraction of FBS patterns can be extremely efficient thanks to δ-freeness anti-monotonicity. Notice that FBS patterns are bi-sets with a bounded number of exception per column but every bi-set with a bounded number of exception per column is not necessarily a FBS pattern.

One crucial issue that can explain the added-value of formal concepts is the ease of interpretation thanks to the Galois connection. What happens with these DRBS and FBS extensions? For each bi-set (X, Y ), do we have a function which associates X and Y ? If a function exists which associates to each set X (resp. Y ) at most a unique set Y (resp. X), the interpretation of each bi-set is much easier. Furthermore, if the two functions are monotonically decreasing, i.e. when the size of X (resp. Y ) increases, the size of its associated set Y (resp. X) decreases. This property is meaningful since the more we have objects inside a bi-set, the less there are attributes that can be associated to describe them (or vice versa).

In a FBS pattern, we have no function from 2 P to 2 O but we have a function from 2 O to 2 P . The definition of this pattern is indeed not symmetrical. In many data sets, including huge and dense ones, complete collections of FBS can be extracted efficiently but we need for a better characterization of more relevant FBS patterns which might remain easy to extract from huge databases, e.g., what is the impact of different δ values for the δ-f r e e -s e tp a r ta n dt h eδ-closure computation? How can we avoid an unfortunate distribution of the false values among the same objects?

By construction, a DRBS has been defined such that we have a bounded number of exceptions per object and per attribute. Two interesting properties have been proven [START_REF] Besson | Mining a new fault-tolerant pattern type as an alternative to formal concept discovery[END_REF][START_REF] Besson | Découvertes de motifs pertinents pour l'analyse du transcriptome: application à l'insulino-résistance[END_REF]. First, when ǫ>0, DRBS patterns are embedded by two functions φ (resp. ψ) which associate to X (resp. Y ) a unique set Y (resp. X). Then, for a fixed δ, we have monotonicity properties of φ and ψ. Unfortunately, the functions loose this property on the whole DRBS collection. Furthermore, we have not identified yet an intentional definition of these functions.

Notice that [START_REF] Besson | Constraint-based mining of fault-tolerant patterns from boolean data[END_REF] contains an empirical evaluation of these different pattern domains on both artificially noised data sets and a real-life medical data set. These extensions of formal concepts have been specified in a constraint-based mining framework, i.e., we have a declarative specification of the constraints on the patterns such that we can work on correct and complete implementations for computing them. Notice however that it is computationally challenging to work with the most elegant extension, i.e., DRBS. Other researchers have considered fault-tolerant pattern mining. To the best of our knowledge, most of the related work has concerned mono-dimensional patterns and/or the use of heuristic techniques [START_REF] Yang | Efficient discovery of error-tolerant frequent itemsets in high dimensions[END_REF][START_REF] Seppänen | Dense itemsets[END_REF]. [START_REF] Gionis | Geometric and combinatorial tiles in 0-1 data[END_REF] is one of the interesting proposal for geometrical tile mining (i.e., dense bi-sets which involve contiguous elements given orders on both dimensions). More recently, other attempts to relax closeness have been considered [START_REF] Cheng | Delta-tolerance closed frequent itemsets[END_REF][START_REF] Cheng | Ac-close: Efficiently mining approximate closed itemsets by core pattern recovery[END_REF]. Fault-tolerance in general and its application to closed sets and formal concepts in particular definitively appears as an important topic for real-life data mining. Let us now consider another pragmatic approach for finding actionable patterns based on collections of formal concepts.

Post-processing Collections of Formal Concepts

T h en u m b e ro ff o r m a lc o n c e p t sw h i c hh o l di nad a t as e ta n dw h i c hc a nb e computed thanks to, for instance, user-defined constraints, can be huge. We already pointed out that many factors can have a dramatic impact on the number of formal concepts. For instance, when an error of measurement or an intrinsic variability of the observed phenomenon lead to a zero value whereas the value true should be obtained, we have to face with an explosion of the number of formal concepts. The fault-tolerant extensions discussed above are definitively not the ultimate solution: indeed, when tractable, the extractions still provide too many patterns. One simple idea is to post-process the formal concepts and more generally the extracted bi-sets to group the ones which are similar enough. It is rather straightforward to design similarity measures between bi-sets and one can perform, for instance, a hierarchical clustering method to group formal concepts. These groups can be interpreted by computing some kind of "quasiformal concepts" that are in fact the bi-sets made of the union of the intents and the union of the extents of all the formal concepts that belong to a cluster [START_REF] Robardet | Using classification and visualization on pattern databases for gene expression data analysis[END_REF]. This has been applied successfully to a real application in the domain of human gene expression data analysis [START_REF] Blachon | Clustering formal concepts to discover biologically relevant knowledge from gene expression data[END_REF]. In this application, mining a 90× 5327 boolean gene expression matrix has given rise to 64 836 formal concepts. When considering size constraints that have enforced the formal concepts to imply at least five biological samples and five genes, only 1 669 patterns have been selected: this is however too much for a human interpretation for each of them. We applied the hierarchical clustering and then we have built about 50 quasisynexpression groups, i.e., sets of genes strongly associated to sets of biological samples. One of them has been carefully interpreted and this has given rise to interesting biological new hypothesis [START_REF] Blachon | Clustering formal concepts to discover biologically relevant knowledge from gene expression data[END_REF].

Following the same ideas, we can also consider the possibility to build clusters or co-clusters by exploiting the formal concepts. A co-clustering (see, e.g., [START_REF] Dhillon | Information-theoretic co-clustering[END_REF]) provides linked partitions on both dimensions (objects and attributes) and, in Boolean data, it tends to compute rectangles with mainly true (resp. false) values. Heuristic techniques (i.e., local optimization) enable to compute one bipartition. In fact, a bi-clustering provides a global structure over the data while fault-tolerant extensions of formal concepts are typical local patterns which can lead to the discovery of unexpected but yet relevant local associations. In [START_REF] Pensa | A bi-clustering framework for categorical data[END_REF], co-clusters are computed from collections of bi-sets like formal concepts: it is a KMeans like clustering that does not work on objects or attributes but on bisets. Notice also that once a bi-partition has been computed, by such a technique or with another co-clustering approach, we can again use the bi-sets for characterization purposes [START_REF] Pensa | From local pattern mining to relevant bi-cluster characterization[END_REF]. Notice that computing clusters or co-clusters based on formal concepts is different from selecting formal concepts that may constitute a collection of clusters or co-clusters (see, e.g., [START_REF] Durand | Ecclat: a new approach of clusters discovery in categorical data[END_REF]).

In a conceptual clustering framework, Mineau et al. [START_REF] Mineau | Simple pre-and post-pruning techniques for large conceptual clustering structures[END_REF] present simple prepruning and post-pruning techniques that can be applied in reasonable time on large classification structures. The paper presents three such techniques: one is based on the definition of constraints over the generalization language, the other two are based on discrimination metrics applied on links between classes or on the classes themselves.

Another interesting relationship that may be studied further is the formal analogies between tiling as considered in [START_REF] Geerts | Tiling databases[END_REF] and co-clustering. Also, the quite active area of subspace clustering is clearly related to local pattern detection and constraint-based mining of bi-sets (see [START_REF] Parsons | Subspace clustering for high dimensional data: a review[END_REF][START_REF] Madeira | Biclustering algorithms for biological data analysis: A survey[END_REF] for surveys).

4C o n c l u s i o n

We have discussed several aspects of actionable pattern discovery from collections of formal concepts. Thanks to constraint-based mining algorithms, computing complete collections of formal concepts that satisfy user-defined constraints is feasible for some useful constraints. This framework has been used to specify fault-tolerant extensions of formal concepts. This is definitively needed for mining large and noisy Boolean data sets. The DRBS pattern domain appears as a well-designed class but the price to pay is its computational complexity. The good news are that (a) DRBS pattern extractions may involve further user-defined constraints which can be used for efficient pruning, and (b) one can look for more efficient data structures and thus a more efficient DR-Miner implementation. A pragmatic usage could be to extract some bi-sets, e.g., formal concepts, and then select some of them (say B =(X, Y )) for further extensions towards faulttolerant patterns: the computation of a DRBS patterns (say B ′ =( X ′ ,Y ′ )) such that the constraint B ⊆ B ′ is enforced. We also mentioned post-processing techniques that, for instance, cluster patterns like formal concepts not only to decrease the number of hypothesis that have to be interpreted by human experts but also to enhance their relevancy, e.g., achieving some kind of fault-tolerance.

Let us now conclude this paper by introducing a few open questions related to both Formal Concept Analysis and constraint-based mining of patterns.

Constraints and formal concept mining. One important direction of research remains constraint-based mining of formal concepts for hard constraints, that is constraints that are neither monotonic nor anti-monotonic and for which new enumeration strategies have to be designed. Constraints that refer to statistical measures (e.g., based on standard deviation), are typical examples of such hard constraints. Even though some types of hard constraints have been studied on simple pattern domains like itemsets (e.g., optimization constraints that look for the best k patterns w.r.t. an objective measure), so far, few researchers have tried to upgrade these algorithms to the 2-dimensional case (i.e., for bi-set mining). New constraint types must be designed as well. For instance, [START_REF] Kléma | Mining plausible patterns from genomic data[END_REF] has proposed to increase the relevancy of set patterns by means of constraints that exploit textual resources in the context of biological data analysis. This is a promising direction of research.

Extensions of formal concepts. The constraint-based mining framework supports the exploitation of domain knowledge to increase a priori relevancy of patterns. We notice however that in more and more applications, the data can hardly be presented as a single binary relation. Let us take an example: assume that we have genes with a lot of information about them (e.g., functions, associated transcription factors), biological experiments enabling to measure the expression of these genes and finally details about the experiments. Consider now that we want to extract the sets of house-keeping genes that are over-expressed in the same biological experiments that are related to muscle tissues. The extraction task sounds like a formal concept extraction, same words same ideas, but here the data are structured into multiple n-ary relations (n>2). One hot topic is to revisit the principles of pattern mining in binary relation when considering n-ary relations. For instance, the counterpart of formal concepts in cubes (3-ary relations) has been recently investigated [START_REF] Jaschke | TRIAS: An algorithm for mining iceberg tri-lattices[END_REF][START_REF] Ji | Mining frequent closed cubes in 3D datasets[END_REF]. Also, extending the ideas of closed set and condensed representation mining in a multi-relational setting is a timely challenge. [START_REF] Godin | Formal concept analysis-based class hierarchy design in object-oriented software development[END_REF] presents a formal concept analysis-based class hierarchy design that can be viewed as normal forms for class hierarchies where each normal form addresses particular design goals. An overview of work in the area is presented by highlighting the formal concept analysis notions that are involved. [START_REF] Wille | Conceptual structures of multicontexts[END_REF] introduces a first formalization of a network of contexts, i.e., the data is represented by the means of several contexts. Descriptions of conceptual coherences within the formalized network of contexts are introduced.

Storing and querying collections of patterns. Following the inductive database perspective [START_REF] Imielinski | A database perspective on knowledge discovery[END_REF][START_REF] Boulicaut | Inductive databases and multiple uses of frequent itemsets: the cInQ approach[END_REF], patterns may be considered as first-class citizens and we have to design databases that not only contain data but also patterns like formal concepts or clustering results. Technically, many challenges concern the efficient management of large collections of set patterns because relational databases are not targeted towards this type of data. Also, the design of general-purpose query languages to support knowledge discovery by means of queries remains an open problem.

Local-to-Global. Many global patterns (e.g., classifiers, clusterings) can be considered as collections of local patterns that satisfy some kind of global constraints. These local patterns are themselves satisfying local constraints. The popular association-based classification approach [START_REF] Liu | Integrating classification and association rule mining[END_REF] is an obvious example of a Local to Global (L2G) scheme: standard association rules are the local patterns (i.e., local constraints are the minimal frequency and minimal confidence constraints). The various proposals for building classifiers from them are then based on different global constraints on these collections of association rules. Clustering can be considered within a L2G framework as well (see, e.g;, [START_REF] Pensa | A bi-clustering framework for categorical data[END_REF]). A better understanding of cross-fertilization between local pattern detection and global pattern discovery is an extremely active research direction that may deliver interesting insights in the next few years. Among others, the exciting challenge of constrained clustering may benefit from such a Local to Global approach (see, e.g., [START_REF] Pensa | Constraint-driven Co-Clustering of 0/1 Data[END_REF] for a constrained co-clustering based on formal concepts).

Fig. 1 .

 1 Fig. 1. Examples of interesting constraints on bi-sets

  , the algorithm starts with the candidate (o 1 o 2 o 3 , (∅,p 1 p 2 )) representing the set of all possible patterns of r 4 .T h e n the attribute p 1 is selected to proceed the enumeration. Two new candidates (o 1 o 2 o 3 , (∅,p 2 )) and (o 1 o 2 o 3 , (p 1 ,p 1 p 2 )) are generated. After enumerating the attribute p 2 , four formal concepts are extracted (o 1 o 2 o 3 , ∅), (o 1 o 2 ,p 2 ), (o 2 o 3 ,p 1 ) and (o 2 ,p 1 p 2 ).

Figure 3

 3 provides an other example of DMiner execution.

p2(Fig. 2 .Fig. 3 .

 23 Fig. 2. Formal concept extraction on r4

Fig. 4 .

 4 Fig.4. An application[START_REF] Besson | Constraint-based formal concept mining and its application to microarray data analysis[END_REF]

Definition 3 .

 3 Assume Z l (x, Y ) denotes the number of false values of an object x on the attributes in Y , i.e., |{y ∈ Y |(x, y) ∈ r}|. Similarly, let Z c (y, X)= |{x ∈ X|(x, y) ∈ r}| be the number of false values of an attribute y on the objects in X.

Table 2 .

 2 Ab o o l e a nc o n t e x tr3

Table 4 .

 4 Ab o o l e a nc o n t e x tr6

	p1 p2 p3 p4 p5 p6 p7

Table 6 .

 6 A permutation on r6 to illustrate Example 2

Acknowledgements. The authors thank Céline Robardet and Ruggero G. Pensa for their participation to most of the research results discussed in this paper. This research is partially funded by EU contract IST-FET IQ FP6-516169.


Florent Dupont
email: fdupont@ligim.univ-lyon1.fr

Benjamin Gilles

Atilla Baskurt

PROGRESSIVE TRANSMISSION OF 3D OBJECT BASED ON BALLS AND CONES UNION FROM MEDIAL AXIS TRANSFORMATION

3D discretized objects become more and more present in many applications for computer graphics. The need to store and transmit these data grows permanently. This paper introduces a new scheme of 3D object progressive transmission. It is based on an union of cone sections and balls selected from the medial axis and optimized for a better scalability in terms of bit rates and quality. This representation of a 3D object is a lossless approach and is very efficient for compression and progressive transmission, as shown in the results presented in this paper.

INTRODUCTION

Usually, polygonal meshes are used for visualizing 3D data. Several methods have been proposed on 3D surface mesh compression, mesh simplification and detail approximation in order to reduce the transmission time of 3D objects [7] [8].

This paper deals with compression and transmission of 3D discrete data. For voxelized objects, skeletons and medial axis (MA) are often used in order to characterize shapes, and some works concern the generation of graphs to describe objects [START_REF] Kresch | Skeleton-Based Morphological Coding of Binary Images[END_REF] [START_REF] Reinders | Skeleton Graph Generation for Feature Shape Description[END_REF]. Borgefors and Nyström [START_REF] Borgefors | Efficient shape representation by minimizing the set of centres of maximal discs / spheres[END_REF], Nilsson and Danielsson [START_REF] Nilsson | Finding the Minimal Set of Maximum Disks for Binary Objects[END_REF] present methods to have an efficient shape representation with medial axis. Giblin and Kimia [START_REF] Giblin | A Formal Classification of 3D Medial Axis Points and their Local Geometry[END_REF] propose an hypergraph skeletal representation based on a local analysis of the MA. For the reconstruction part, Amenta [START_REF] Amenta | The medial axis of a union of balls[END_REF] computes the interior of the union of balls with continuous methods.

In this study, we propose an efficient and scalable representation of a 3D object from the medial axis. Section 2 presents the MA computation based on the discrete distance map and the local maxima determination. We show in Section 3 how to optimize the number of points of the MA in order to reduce the transmission time on a network. We also present the coding scheme in order to have rapidly a good quality for the reconstructed object. In Section 4 we propose an other method based on "cone sections". We define these "cone sections" and how to use them in order to reduce the number of transmitted elements. Section 5 presents the results for the evaluation of both the compression performance (the quantified results of the compression rates obtained compared to other methods) and the quality of the progressivity.

MEDIAL AXIS

Discrete Distance Map

To compute the MA, one way is to obtain first a discrete distance map where each voxel of the 3D object has the value of the minimal distance from the edge [START_REF] Borgefors | Distance Transformation in Arbitrary Dimension"s[END_REF]. This method is reversible but does not guarantee the connectivity preservation (this point is not important for a compression purpose). Discrete distances are considered [START_REF] Remy | Medial Axis for chamfer distances: computing look-up tables and neighborhoods in 2D or 3D[END_REF] and they are based on 3D voxels neighborhoods. We have implemented four different configurations that lead to four different distances: D6, D18, D26 and chamfer distance with 3-4-5 parameters.

Local Maxima

The MA is the set of centers of the maximal balls included in the object and is obtained from the distance map by computing the local maxima in the neighborhood considered with the chosen distance.

"BALLS" METHOD

Medial Axis optimization

The idea is to transmit medial axis balls, decomposing the object, for compression and progressive transmission purposes. The medial axis is redundant because associated balls overlap. The aim of our optimization method is to suppress the biggest number of balls while ensuring an exact reconstruction. Our method consists in computing for each medial axis point the number of voxels that belong to the associated ball and not to others. We call this characteristic the "intrinsic volume". The list of medial axis points is sorted by increasing radius. Then the intrinsic volume is computed for the first point of the list. If this value is null the point called « Zero volume » is suppressed from the list. This procedure is repeated while there are still unprocessed points. Characteristics of all points have to be updated at the end of the algorithm because of their mutual influence. The sorting stage allows a huge reduction of the number of points from the medial axis (small balls are preferentially suppressed from the medial axis).

The optimized medial axis is a list of points (X,Y,Z coordinates) with associated radius. The list is sorted by decreasing radius in order to achieve rapidly a good quality of the reconstructed object.

Coding Scheme

Coordinates and radii are coded into a binary file with the minimum number of bits dedicated to each coordinate and radius. Then, the decoding is performed in real time. Every transmitted ball is also reconstructed in real time. Hence, the number of LOD (Levels Of Detail) is very high. A more efficient entropic coder could be implemented to reduce the size of the transmitted file.

The two optimization phases are very important for the progressive transmission aim. They are successively applied on data. The medial axis computation and the optimization stages can be computed for all the norms (Section 2) and the better one can be retained. This leads to the smallest binary file even if computation time is higher (compression can be processed offline).

CONE SECTIONS

Representing a volume with medial axis points is equivalent to decompose it with a union of balls. The thicker and smoother the volume is, the more efficient in terms of compression of information, the method is. For stringy objects, the method is less efficient. To remedy this, the idea consists to use other primitives than balls. Here, we propose a reversible method that uses cones sections to decrease the size of data to be transmitted whilst ensuring exact reconstruction. For thin and smooth objects, the number of medial axis points can be very large. However, the number of cone sections to decompose them exactly is generally small. This point has been well depicted by Reinders, and al [START_REF] Reinders | Skeleton Graph Generation for Feature Shape Description[END_REF]. Decomposing an object into a minimal set of cone sections is almost impossible by looking to all possible solutions. However, by combining medial axis balls, which are included in cone sections, it is possible to create cone sections describing well the object. For example, a cylinder is represented with only one cone section which links two extreme balls. We define cone sections as the set of the balls between two balls where radius are linearly interpolated (Figure 1).

Figure 1. An example of cone section with chamfer metric

The proposed algorithm, by taking as the input the medial axis balls, intents to select the best links between these balls in order to describe the object in the most compact way. The computation of the optimal solution would be too heavy as the number of spatial and temporal combinations to look at is very large. To make the problem computationally feasible, we assumed that transmitting the biggest volume, for each level of detail, would give a good solution in order to minimize the slope of the distortion/time curve.

First, we compute an exhaustive list of cone sections which are totally included in the object: every pair of medial axis balls is tested to see if the cone section linking them belongs to the object. Then, volumes of primitives (balls and cones sections) are computed, in number of voxels, and stored into a list. This is the initialization step (See Figure 2). Then, the loop aims to select, for each iteration, the primitive that brings the biggest volume to the object, until the object is totally reconstructed. The selection is made by taking the biggest volume from the volumes list.

Medial axis calculation

Listing of totally included cone sections (CS)

CS and balls volumes computation

Selection of the biggest added volume

Selected primitives coding Transmission

Unselected volumes updating

Null yes no

As soon as a primitive is selected, its volume has to be subtracted from the others. So the list is updated and then corresponds to the list of added volume. Furthermore, when it contains only null volumes, it means that any voxel cannot be added to the object; the union of selected primitives is at that time exactly the object.

The coding of the list of primitives is quite straightforward because we just need to transmit balls and links. For a ball, we code its coordinates, its radius, and any number of links to other balls. They are represented by relative indexes interleaved by 1-bit separators. We have chosen an arithmetic coding for indexes in order to profit from the non-uniform distribution of relative indexes.

RESULTS

Results given in this section were obtained with different volumes (See Table 1). We expect two kinds of results from this study: the compression efficiency with the comparison to standard encoders and the quality of the progressive method.

Data compression

After coding balls and/or cone sections, the size of the binary file obtained can be compared to the one given by classical encoders like GZIP and JBIG. We have implemented the progressive 2D compression scheme JBIG in 3D by considering a volume as a succession of 2D slices. A drawback is the necessity to have at least one dimension as a power of 2. Figure 3 shows the compression factors (the size of raw file over the size of compressed one) for our methods (the best norm is used for each object), also for GZIP and JBIG.

For the compression of natural objects, our methods are a bit weaker than the two others, especially for thin objects. However, they present the progressive transmission functionality of 3D objects, which makes them interesting, i.e. for web 3D applications. In Figure 4, the corresponding curves for the JBIG method, for our "balls" and "cones" methods are shown. With our "cones" method, even if the transmission is a bit longer than JBIG in some cases, we have a very good approximation of the volume earlier (at about 20% of transmitted data) as seen in Figure 5. This figure illustrates these results with reconstructed images for the different methods at regular interval time. For Figures 4 and5, the time or percentage of transmitted data is normalized with the "cones" method. The point called 100% corresponds to the total transmission of the file obtained with the "cones" method but not for others (the transmission for the "balls" method is complete at 180%).

Progressive transmission

To compare these two methods (and the JBIG one as well), a good criterion is to consider the area under the distortion/time curve (S in Figure 4). As we want to reduce the transmission time and the distortion, we want to minimize this area. The quality of the method is calculated with this criterion and results are presented in Figure 6. In all cases, our "cones" method gives better results than JBIG and our "balls" method.

S

CONCLUSION AND FUTURE WORK

This paper presents a new method for transmitting progressively 3D binary volumes. This method is able to give quickly a good approximation of a 3D object to the end-user. For complex volumes, the compression rates are better than the ones obtained with classic encoders. The use of data which contains 3D topological information will permit to compute 3D transformations and geometric properties easily. It opens perspectives for volume animation using transformations applied on MA and for indexing and retrieval volumes in large databases. For an on-line demonstration, the web site [5] can be consulted.

Figure 2 .

 2 Figure 2. Coding scheme of the "cone sections" method

Figure 3 .

 3 Figure 3. Compression factors

Figure 4 Figure 4 .

 44 Figure4shows the distortion's evolution in function of the percentage of transmitted data, which is proportional to the time at a fixed network's rate. The distortion is the error on the reconstructed volume from received data in comparison to the original one. Distortion is calculated using the metric adopted by MPEG-4: D = (nb of pixels in error) / (nb of pixels into object)

FigureFigure 6 .

 6 Figure 5. Reconstructed images

Table 1 . Test images

 1

ACKNOWLEDGMENTS

Our thanks to Bertrand Marmond for the demonstration web site and to Florence Denis for the 3D hand image.


Samira Hammiche
email: shammich@liris.univ-lyon1.fr

Salima Benbernou
email: sbenbern@liris.univ-lyon1.fr

Athena Vakali
email: avakali@csd.auth.gr

A Logic Based Approach for the Multimedia Data Representation and Retrieval

Nowadays, the amount of multimedia data is increasing rapidly, and hence, there is an increasing need for efficient methods to manage the multimedia content. This paper proposes a framework for the description and retrieval of multimedia data. The data are represented at both the syntactic (structure, metadata and low level features) and semantic (the meaning of the data) levels. We use the MPEG-7 standard, which provides a set of tools to describe multimedia content from different viewpoints, to represent the syntactic level. However, due to its XML Schema based representation, MPEG-7 is not suitable to represent the semantic aspect of the data in a formal and concise way. Moreover, inferential mechanisms are not provided. To alleviate these limitations, we propose to extend MPEG-7 with a domain ontology, formalized using a logical formalism. Then, the semantic aspect of the data is described using the ontology's vocabulary, as a set of logical expressions. We enhance the ontology by a rules layer, to describe more complex constraints between domain concepts and relations.

User's queries may concern the syntactic and/or semantic features. The syntactic constraints are expressed using XQuery language and evaluated using an XML query engine; whereas the semantic query constraints are expressed using a rules language and evaluated using a specific resolution mechanism.

Introduction

Usually, the multimedia content is studied in two parallel dimensions : the syntax (structure and low level features) and the semantic (the meaning of the data). In multimedia data representation and retrieval models, these two dimensions have not only to be taken into account, but also require that each of them be dealt by the the most appropriate tools to it, and these sets of tools have to be integrated in a complimentary way in order to respond user's queries.

The Moving Picture Experts Group (MPEG) published the standard MPEG-7 1 , in February 2002 which aims to describe the multimedia content from different viewpoints. This standard is based on XML Schema [START_REF]XML Schema Part 1: Structures, W3C recommandation[END_REF] and focuses on the structural and low-level features, then it is suitable for the representation of the syntactic dimension of the multimedia content. However, XML Schema displays some limitations when there is a need to extract implicit information. This is due to the fact that there is neither formal semantics nor inference capabilities associated with the elements of an XML document. Consequently, MPEG-7 cannot represent the meaning (semantics) of the multimedia content. Then, another formalism has to be considered for the semantic dimension, where the following issues are required:

• formally define the semantics of MPEG-7 terms and multimedia content;

• express these definitions in a machine understandable language;

• and provide inferential mechanisms to allow reasoning over the multimedia content.

Logical formalisms, which are rather appropriate for the above requirements, are considered in our framework.

To take into account the two dimensions (syntactic and semantic) in the same framework and to alleviate the limitation of MPEG-7 description, we propose to extend MPEG-7 with domain ontology to provide a shared and formal vocabulary for the specification of the semantics. As description logic languages are usual to represent ontologies, we use a specific description logic (DL) language to describe the semantic of the multimedia content. However, if most of the DL languages are very expressive to describe the concepts (i.e. conceptual entities of the domain), they don't pay so much attention to the role expressions (relations between concepts). Moreover, DLs formalisms have rather weak query languages. The simple and existing ones are mostly based on concepts satisfiability. This technique cannot be used directly for queries involving roles and variables. To cope with these limitations, we enhance the ontology by a rules layer (represented using Datalog rules) which provide a powerful query langauge. Therefore, a unified and adequate formalism integrating rules and DLs is used to represent the semantic dimension of the multimedia data.

The semantic query processing is done in two steps, first the query is rewritten using the Datalog rules and the DL reasoning mechanism, then an evaluation strategy is applied to the rewritten queries, which is based on first order logic resolution algorithm.

To summarize, we present a formal framework where the standard MPEG-7 and an hybrid language (DL and rules) are used to capture the syntactic and semantic dimensions respectively, of the multimedia data. These two dimensions are related using XPath expressions. For the retrieval, we use XQuery [START_REF]An XML Query Language[END_REF] and a resolution algorithm to answer user's queries in a complimentary way.

This paper is organized as follows: in Section 2, we give a case study scenario and some preliminaries concerning the MPEG-7 standard and the hybrid language (DL and Datalog rules languages). Section 3 presents the logical based framework architecture used for the representation and retrieval of the multimedia data. Section 4 introduces an application example. In Section 5, we relate our work to the existing ones and we conclude in Section 6.

Preliminaries 2.1 A case study scenario

In our proposal, we consider soccer game videos. Then, the data dealt with are video data and the ontology is a soccer game ontology. The soccer game ontology involves many concepts and relations. An extract of the soccer game ontology and the rules is given in Table 1. Our DL knowledge base is a set of axioms using two forms. The first is C ⊑ D, which states that every instance of the concept C must be an instance of the concept D; and the second form R ⊑ C × D states that the role R has the domain C and the range D.

We introduce a Datalog rules layer on the top of the DL to cope with the DL limitations about roles and query language. Then, it is possible to define n-ary predicates such as the predicate introduced in the rule R 1 , which captures an event in a video segment and its actors (for example, the goal event has a specific player as agent and a goalkeeper as patient); and the predicate of the rule R 2 , which gives the conditions to have two players in the same team.

Semantic queries are posed in term of the domain ontology vocabulary and the ordinary predicates defined using Datalog rules. For example, if a query is to obtain the video ,E,X) ←-P erson(P 1 ), P erson(P 2 ), Event(E), V ideo(X), AgentOf (P 1 ,E), P atientOf (P 2 ,E), EventOccur(X, E) R 2 : SameT eam(P 1 ,P 2 ,T) ←-P layer(P 1 ),Player(P 2 ), T eam(T ), M emeberOf (P 1 ,T), M emberOf (P 2 ,T) segment where the player "Ronaldo'" scores a goal against the goalkeeper "Khan". This query can be expressed in the Datalog query language as follows: Q(x) ←-Eventactors(Ronaldo, Khan, goal, x).

To answer this query, we should first rewrite it using the ontology vocabulary and the intentional Datalog rules, then evaluate the resulting queries. The rewriting is done in two steps: the first is to expand the Datalog intentional rule. Q will be rewritten into the query Q ′ as follows: Q ′ (x) ←-P erson(Ronaldo), P erson(Khan), Event(goal), V ideo(x), AgentOf (Ronaldo, goal), P atientOf (Khan, goal), EventOccur(x, goal).

The second step is to reason over the domain ontology to infer concepts that are subsumed by the concepts in the query. Then, the query Q ′ will be rewritten into a disjunction of queries Q 1 , ..., Q n . Each of these queries is semantically equivalent to the initial query Q ′ .

The MPEG-7 standard

MPEG-7, formally called "Multimedia Content Description Interface", specifies a standard set of description tools, which are applicable for all kinds of multimedia content independent of its format and coding. These tools are [START_REF] Vakali | Mpeg-7 based description schemes for multi-level video content classification[END_REF]:

• A set of Descriptors (Ds), to represent the features of audio-visual material, (e.g. color histogram).

• A set of Description Schemes (DSs), which define the structure and the semantics of the relationships between elements, which include Ds and DSs.A ne xample is the hierarchical structure of a video represented by the VideoSegment DS.

• A Description Definition Language (DDL), which provides a syntax to combine, express, extend and refine Ds as well as DSs. It is XML Schema based with some MPEG-7 specific extensions.

• System Tools, to support efficient binary encoding multiplexing, synchronization and transmission of the descriptions.

<Mpeg7> <Description xsi:type="ContentEntityType"> <MultimediaContent xsi:type="VideoType"> <video id="Video">  <CreationInformation> <Creation> <Title>Spain vs Sweeden (July 199) </Title> <Creator> BBC </Creator> </Creation> <Classification> <Genre Type="main"> Sport </Genre> </Classification> </CreationInformation>  <MediaLocator><MediaUri>soccer.mpg</MediaUri></MediaLocator> <MediaTime><MediaTimePoint>T00:00:00</MediaTimePoint> <MediaDuration>PT1M30S</MediaDuration> </MediaTime>   <TemporalDecomposition gap="false" overlap="false"> <VideoSegment id="ID-V1">  <SpatioTemporalDecomposition gap="false" overlap="false">  </SpatioTemporalDecomposition> <Semantic> <Name>Foul event and players relationships </Name> <SemanticBase xsi:type="EventType" id="Foul-EV"> <Name>Foul</Name> <Relation type="cs:SemanticRelationCS:2001:agent" source="#Player1-MR" target="#Player2-MR"/> </SemanticBase> <Graph><Relation type="cs:SpatialRelationCS:2001:left" source="#Player1-MR" target="#Player2-MR"/> <Relation type="cs:SpatialRelationCS:2001:touch" source="#Player2-MR" target="#Ball-MR"/> </Graph></Semantic></VideoSegment> <VideoSegment id="ID-V2">  </VideoSegment></TemporalDecomposition> </Video></MultimediaContent></Description></Mpeg7>

Figure 1. Example of an MPEG-7 description

Figure 1 is an MPEG-7 description of a soccer game video extract. This description includes Creation Information (e.g. title, creator, classification), Media Information (e.g. media time, media location), Structural Aspects (segment decomposition) and Semantic Aspects (e.g. text annotation, semantic entities such as objects and events, semantic attributes and semantic relations). The two first features, supplied by Usage Information (e.g. access rights, distributor), address information related to the management of the content (content management information), whereas the last two are mainly devoted to the description of perceivable information in term of structure and semantics (content description information).

The semantic descriptions have advantages over syntactic descriptions, because of their proximity to human understanding of multimedia information. They need a formalism which provides flexible representation (graph structure rather than the XML tree structure), formal and shared vocabulary, methods for expressing rules (the rule of inverse property for example), constraints and axioms as well as support of inferential mechanisms. The combination of DL and rules languages provides an interesting angle to deal such requirements.

Ontologies, Description Logic and Rules

As mentioned in Section 1, we extend the MPEG-7 standard with domain ontology supplied by a rules layer. In the following, we present the three notions implied: ontologies, DL and rules.

a) Ontologies

An ontology is defined as an explicit specification of a conceptualization [START_REF] Gruber | A translation approach to portable ontology specifications[END_REF] and it consists by several components of which the most important are concepts, relations and attributes, instances (or individuals) and axioms. It defines precisely and formally the semantics of concepts and their inter-relationships for a specific domain, and thus, it provides a shared and common understanding of a domain that can be communicated between people and application systems.

b) Description Logic : Syntax, Semantic and Knowledge Base

The use of description logics (DLs) as ontological language has been highlighted by the recent explosion of interest in the so-called "Semantic Web". OWL-DL [START_REF] Baader | The description logic handbook: theory, implementation, and applications[END_REF] is a W3C recommendation language for ontology representation in the Semantic Web. It is a syntactic variant of the SHOIN(D) DL, offering a high level of expressivity while still being decidable. We use the DL SHIQ (a subset of the SHOIN(D) DL), which is enough expressive to represent the domain ontology that we consider (soccer game ontology). The syntax of the concepts and roles expressions is given in the following [START_REF] Motik | Query answering for OWL-DL with rules[END_REF].

Let N R be the set of role names. The set of SHIQ roles is the set A SHIQ knowledge base KB is a triple of the form (KB R ,KB T ,KB A ), where KB R is an RBox, KB T is a TBox, and KB A is an ABox.

N R ∪{R -|R ∈ N R }.F o rR ∈ N R , let Inv(R) denote R -and let Inv(R -) denote R.A nRBox R over N R is
For the semantic of the SHIQ DL, we utilize the recent research results of [START_REF] Motik | Query answering for OWL-DL with rules[END_REF] about the transformation of OWL-DL KB into disjunctive Datalog KB. The transformation is based on the fact that OWL-DL is a subset of first order logic. Then, the semantic of SHIQ KB is given by a mapping π which transforms the KB axioms into a set of first order logic (FOL) formulae, so that the SHIQ DL KB is satisfiable if π(KB) is satisfiable.

c) Datalog Rules

Let N P be a set of predicate symbols such that N C ∪ N R ⊆ N P . A term is either a constant (denoted by a,b,c) or variable (denoted by x,y,z). An atom has the form P (s 1 , ..., s n ), where P is a predicate symbol and s i are terms; a rule has the form H ←-B 1 , ..., B n , where H and B i are atoms; H is called the rule head, and the set of all B i is called the rule body. A Datalog program P is a finite set of horn rules with the following restrictions: Datalog allows only safe rules, i.e. every variable occurring in the head of a rule must also occur in the body of the rule and Datalog disallows the use of function symbols. For the semantics, the rule H ←-B 1 , ..., B n is equivalent to the clause H ∨¬B 1 ∨ .. ∨¬B n .

Multimedia Framework

Architecture of the framework

Figure 2 illustrates the multimedia framework architecture, where the levels of data description and data retrieval are represented. The data description level uses metadata annotation component, ontologies, rules, the MPEG-7 database and the knowledge base; and the retrieval level uses

-Terminology -Rules + Facts ✁ ✂ ✄ ☎ ✆ ✝ ✞ ☎ ✄ Ontologies Segment MPEG-7 CMI ☛ ✍ ✎ ✏ ✑ ✑ ✒ ✍ ✑ ☛ ✓ ✎ ✔ ✕ ✖ ☛ ✗ ✎ ✏ ✒ ✍ ✔ ✘ ✙ ✚ ✛ ✜

Syntactic and Semantic queries

Query Processor

✢ ✁ ✝ ✣ ✤ ✝ ✦ ✁ ✂ ✄ ✦ Metadata Annotation Component ✧ ★ ✩ ✪ ✫ ✬ ✭ ✩ ✪ ✮ ✯ ✛ ✩ ✪ ✰ ✚ ✱ ✩ ✲ ✳ ✴ ✵ ✂ ✝ ✞ ✶ ✝ ✷ ✦ ✝ ✸ ✹ ✺ ✻ ✼ ✄ ✽ ✦ ✝ Rules ✾ ✿ ❀ ✿ ✾ ❁ ❂ ❃ ❄ ❅ ❆ ❀ ❅ ❇ ❈ ✾ ✿ ❀ ✿ ❉ ❁ ❀ ❄ ❅ ❁ ❊ ✿ ❋ ✎ ✖ • ✑ ✎ • ✖ ☛ ❍ ■ ❏ ❑ ▲ ▼ ◆ ❖ ■ Figure 2.
Framework Architecture the query interface, query processor and the storage system composed of a knowledge base and the MPEG-7 database. In the sequel, we detail these different components and their inter-relationships.

Metadata Annotation Component

The metadata annotation component is used to annotate the multimedia data and produce the corresponding MPEG-7 description. It contains the structure (segment decomposition) of the multimedia data, the Content Management Information (CMI) as well as the low level information. For example, the annotation of a video data is done as follows: first the video is segmented with respect to the MPEG-7 V ideSegment DS (we obtain a video segment hierarchy), then; media time, creation, location and annotation information are associated to each structural unit (for example : video, video segment, moving region and still image). For the semantic part, we associate a set of logical assertions, expressed in term of the ontology vocabulary, to each structural unit considered as interesting and meaningful to the user. To deal with spatial and temporal relation between the different objects and/or media, we use a predefined set, mainly based on the MPEG-7 SpatialRelation CS and T emporalRelation CS, and use this set in the spatiotemporal annotation of the data.

Since, the identification attribute (ID) is required in each MPEG-7 segment, we exploit it to connect the semantic description to the MPEG-7 description, which provide links to the raw data segment (using the MPEG-7 MediaLocator element). Therefore, the coupling of ontologies and rules based knowledge with metadata enriched MPEG-7 multimedia files is achieved and then, multimedia retrieval techniques should be considered for this hybrid representation.

The MPEG-7 Database

The MPEG-7 database is a set of MPEG-7 descriptions which represent the segment decomposition of the described data, the metatdata information (creator, location, duration) and may contain also a set of low level features of the data (color histogram, dominant color, texture, shape, etc.). This base is used to respond the syntactic queries.

Ontologies, rules and knowledge base components

The domain ontology is expressed using the DL SHIQ. Then, according to the approach of [START_REF] Motik | Query answering for OWL-DL with rules[END_REF], the SHIQ KB is translated into disjunctive Datalog KB using the following steps: elimination of the transitivity axioms, translation of SHIQ KB axioms into the clausal form, saturation of the TBox and RBox, elimination of function symbols, elimination of irrelevant rules and conversion to disjunctive Datalog rules.

The approach uses the DL-SafeRules formalism where the following conditions have to be satisfied: concepts and roles are allowed to occur in the antecedent and consequent of the Datalog rules and each variable in a rule is required to occur in a non-DL atom in the rule body. After the translation of SHIQ DL KB to a Disjunctive Datalog KB, the rules KB is added to this DL SHIQ KB. The algorithm developed for query answering in this approach is decidable for SHOIN(D) DL without nominals (SHIQ(D)).

In the sequel, we give two translation examples of the DL axioms ⊑ (for concepts and roles) and the transitive property of roles to first order logic formulae. The translation is done using the mapping function π. π(C ⊑ D)=∀x : π y (C, x) -→ π y (D, x), where C and D are concepts π(R ⊑ S)=∀x, y : R(x, y) -→ S(x, y), where R and S are roles. π(T rans(R)) = ∀x, y, z : R(x, y) ∧ R(y, z) -→ R(x, z) For the inverse role property, the mapping of the SHIQ KB to first order formulae add automatically the clause ∀x, y : R(x, y) ←→ R -(y, x) to the Datalog KB. This means that all the inverse of relations are deduced and added to the Datalog KB. For example, if we have a predicate left(x, y) then, right(x, y) is deduced and added to the Datalog KB.

Query Interface and Query Processor

The user submit his queries through a query interface. The query constraints may be semantic and/or syntactic. Then, the query processor separates the query conditions (syntactic constraints) that could be answered by the MPEG-7 database from those that could be answered by the knowledge base (semantic constraints). The query processor is also responsible for retrieving and responding the user's queries.

We use XQuery to specify the syntactic constraint of queries. XQuery is defined as a superset of XPath [START_REF]XPath: XML Path Language[END_REF]. The overall design of XQuery is based on a language proposal called Quilt [START_REF]Quilt : an XML Query Language[END_REF]. XQuery is defined to deal with the features of XML (hierarchical, ordered, textual and potentially schema less structure). It consists of FLWR (For-Let-Where-Return) expressions that support iteration and binding of variables to intermediate results. Therefore, users must understand and know the XML schema and the FLWR expression to write queries in XQuery.

Semantic queries are expressed using Datalog query language i.e single horn rule which has the following form:

Q(x) ←-E 1 (x 1 ),E 2 (x 2 ), ..., E n (x n )
where E 1 , ..., E n are concepts, roles and/or ordinary predicates, x i represent a tuple of variables and constant. The atom Q(x) is the head of the query, and the result of the query is a set of tuples, each giving a binding for every variable in x. The evaluation of a Datalog query can be done bottom-up (called also forward chaining); or top-down (called also backward chaining). The semantic queries are processed in two steps:

1. Rewrite the query, where the Datalog intentional rule are expanded to the body concepts and roles. Then, reason on domain ontology to infer concepts that are subsumed by the concepts in the query.

2. Evaluate the rewritten query with respect to the Disjunctive Datalog KB. We choose to use the top-down (backward chaining) approach to evaluate the semantic queries which based on resolution algorithm.

Syntactic queries, which may concern content management and/or low level information, are expressed using XQuery [START_REF]An XML Query Language[END_REF] language which is the standard language, defined by W3C, to deal with the features of XML documents.

To answer a user query, the semantic part is used to search the portion of the MPEG-7 description (the XPath expression) and the variable values that satisfy the semantic specifications. From the MPEG-7 description portion, we can access the raw data (using the MPEG-7 MediaLocator descriptor) and since we get the MPEG-7 description, XQuery can be used to filter the data with respect to the syntactic constraints such as duration, creator and metadata.

Example Application

Domain ontology and individuals

We consider the domain ontology introduced in the Section 2.1. We recall that we consider the concept video as a concept where at least one event takes place and at least one person appears (player, referee, etc.). We suppose that the video segmentation is driven by events. The name of the concept Video is the XPath expression that allow to capture the video segment in the MPEG-7 description. For spatial and temporal relation between the different concepts, due to the space limitation, we consider just the spatial relation "right" (that will be used in the illustration example). Its inverse role is "left". These two relation are defined in the DL component as follows: right ⊑ (P erson ⊔ Object) × (P erson ⊔ Object); left ⊑ (P erson ⊔ Object) × (P erson ⊔ Object);

The semantic description of the data is done by the instantiation of the different predicates (concepts, roles and the predicates). It can be seen as a conjunction of concept and roles individuals. We suppose that the MPEG-7 description introduced in Figure 1 is stored as an XML document called "soccer.xml". We denote by P ath 1 the XPath expression which allows to accede the first video segment (document(soccer.xml)//V ideoSegment[@id =" ID-V1"]) . Then the semantic part of the document will be represented with the following assertion on individuals A (notice that some concepts and roles are not defined in Section 2.1 since we gave just an extract. A = {V ideo(P ath 1 ), Event(F oul), EventOccur(P ath 1 , F oul),Player(P layer1), Appear(P ath 1 ,Player1), AgentOf (P layer1, F oul), P layer(P layer2), Appear(P ath 1 ,Player2), P atientOf (P layer2, f oul), lef t(P layer1,Player2), Object(Ball), T ouch(P layer2, Ball)}

Query evaluation

✁ ✂ ✄ ☎ ✆ ✝ ✞ ✟ ✠ ✡ ☛ ✍ ✎ ✁ ☎ ✄ ✏ ✑ ☛ ☎ ✍ ✒ ✄ ✓ ✌ ✔ ✑ ✄ ✂ ✆ ✄ ✍ ✕ ✖ ✗ ✡ ✁ ✏ ✑ ☛ ☎ ✟ ✍ ✒ ✄ ☎ ✆ ✘ ✙ ✚ ✛ ✜ ✢ ✚ ✣ ✛ ✤ ✥ ✤ ✦ ✧ ✙ ★ ✤ ✦ ✧ ✥ ✩ ✚ ✛ ✙ ✪ ✚ ✢ ✫ ✏ ✍ ✎ ✁ ☎ ✆ ✄ ✏ ✟ ✍ ✎ ✌ ✠ ✁ ✏ ✑ ☛ ☎ ✟ ✍ ✒ ✆ ✄ ✝ ✞ ✟ ✠ ✡ ✁ ✓ ✌ ✔ ✑ ✆ ✄ ✬ ✕ ✭ ✟ ✌ ✁ ✂ ✆ ✄ ✮ ✖ ✟ ✠ ✡ ✯ ✰ ✁ ☎ ✄ ✓ ✌ ✔ ✑ ✆ ✄ ✏ ☛ ✡ ✕ ✟ ✠ ✡ ✯ ✰ ✁ ✏ ✑ ☛ ☎ ✟ ✍ ✒ ✄ ✓ ✌ ✔ ✑ ✆ ✄ ✝ ✞ ✟ ✠ ✡ ✯ ☞ ☞ ✔ ✍ ✁ ✂ ✄ ✓ ✌ ✔ ✑ ✆ ✄ ✍ ✕ ✖ ✗ ✡ ✁ ✏ ✑ ☛ ☎ ✟ ✍ ✒ ✄ ☎ ✆ ✘ ✙ ✚ ✛ ✜ ✢ ✚ ✣ ✛ ✤ ✥ ✤ ✦ ✧ ✙ ★ ✤ ✦ ✧ ✥ ✩ ✚ ✛ ✚ ✱ ★ ✲ ✦ ✤ ✦ ✧ ✲ ✦ ✥ ✩ ✚ ✲ ✦ ✥ ✲ ✪ ✲ ✧ ✜ ✳ ✢ ✚ ✣ ✛ ✤ ✥ ✚ ✴ ✚ ✛ ★ ✲ ✦ ✙ ★ ✤ ✦ ✧ ✤ ✥ ★ ★ ✙ ✵ ✶ ✲ ✦ ✶ ✚ ✷ ✥ ✴ ✪ ✱ ✜ ✚ ✛ ✸ ✏ ✑ ☛ ☎ ✟ ✍ ✁ ☎ ✆ ✄ ✏ ✑ ☛ ☎ ✟ ✍ ✁ ✏ ✑ ☛ ☎ ✟ ✍ ✒ ✆ ✄ ✝ ✞ ✟ ✠ ✡ ✁ ✓ ✌ ✔ ✑ ✆ ✄ ✬ ✕ ✭ ✟ ✌ ✁ ✂ ✆ ✄ ✮ ✖ ✟ ✠ ✡ ✯ ✰ ✁ ☎ ✄ ✓ ✌ ✔ ✑ ✆ ✄ ✏ ☛ ✡ ✕ ✟ ✠ ✡ ✯ ✰ ✁ ✏ ✑ ☛ ☎ ✟ ✍ ✒ ✄ ✓ ✌ ✔ ✑ ✆ ✄ ✝ ✞ ✟ ✠ ✡ ✯ ☞ ☞ ✔ ✍ ✁ ✂ ✄ ✓ ✌ ✔ ✑ ✆ ✄ ✍ ✕ ✖ ✗ ✡ ✁ ✏ ✑ ☛ ☎ ✟ ✍ ✒ ✄ ☎ ✆ ✹ ✺ ✷ ✷ ✪ ✜ ✥ ✩ ✚ ✛ ✚ ★ ✲ ✪ ✙ ✥ ✤ ✲ ✦ ✱ ✪ ✧ ✲ ✛ ✤ ✥ ✩ ✻ ✼ ✹ ✜ ✽ ✴ ✪ ✱ ✜ ✚ ✛ ✾ ✳ ★ ✙ ✵ ★ ✥ ✤ ✥ ✙ ✥ ✤ ✲ ✦ ✲ ✿ ✥ ✩ ✚ ❀ ✱ ✛ ✤ ✱ ✵ ✪ ✚ ☎ ✙ ★ ✤ ✦ ✧ ✥ ✩ ✚ ✤ ✦ ★ ✥ ✱ ✦ ✶ ✚ ✏ ✑ ☛ ☎ ✟ ✍ ❁ ✸ ✬ ✕ ✭ ✟ ✌ ✁ ✂ ✆ ✄ ✝ ✞ ✟ ✠ ✡ ✯ ☞ ☞ ✔ ✍ ✁ ✂ ✄ ✰ ✌ ✔ ✑ ✆ ✄ ✍ ✕ ✖ ✗ ✡ ✁ ✏ ✑ ☛ ☎ ✟ ✍ ✒ ✄ ✏ ✑ ☛ ☎ ✍ ❁ ✆ ✹ ❂ ✽ ✴ ✱ ✥ ✩ ✾ ✳ ★ ✙ ✵ ★ ✥ ✤ ✥ ✙ ✥ ✤ ✲ ✦ ✲ ✿ ✥ ✩ ✚ ❀ ✱ ✛ ✤ ✱ ✵ ✪ ✚ ✂ ✙ ★ ✤ ✦ ✧ ✏ ☛ ✡ ✗ ❁ ✸ ✹ ❃ ✚ ❄ ✙ ✶ ✚ ✍ ✕ ✖ ✗ ✡ ✁ ✏ ✑ ☛ ☎ ✟ ✍ ✒ ✄ ✏ ✑ ☛ ☎ ✟ ✍ ❁ ✆ ★ ✤ ✦ ✶ ✚ ✑ ✟ ✰ ✡ ✁ ✏ ✑ ☛ ☎ ✟ ✍ ❁ ✄ ✏ ✑ ☛ ☎ ✟ ✍ ✒ ✆ ✤ ★ ✛ ✚ ✷ ✛ ✚ ★ ✚ ✦ ✥ ✚ ❄ ❅ ✩ ✚ ✶ ✲ ✻ ✷ ✙ ✥ ✚ ❄ ✱ ✦ ★ ✣ ✚ ✛ ❆ ❂ ✽ ✴ ✱ ✥ ✩ ✾ ❇ ✜ ✽ ✴ ✪ ✱ ✜ ✚ ✛ ✾ ❈

Figure 3. Query rewriting and resolution steps

Let's consider the following query: "find video segment where there is a foul on the Player2, which appear in the right of another player". This may be expressed with the intensional Datalog predicate "Eventactors" as follows:

Q(x, y) ←-Eventactors(y, P layer2, F oul, x), right(P layer2,y). The steps of the query answering are illustrated in Figure 3. We recall that we use the assertion on individuals A presented in the Section 4.1. The relation right(P layer2,Player1) was already added to the Datalog KB since we have a horn rule in the KB which express the inverse property of the roles left and right.

The result of the query is the substitution {x/P ath 1 , y/P layer1}. P ath1 is the XPath expression which allow to accede the MPEG-7 description from where we can have the raw data (the location of video segment) and other information like metadata and content management information.

Related Work

Our work is related with two main topics: querying MPEG-7 description and adding semantic to the multimedia data.

There are few querying techniques proposed for multimedia content retrieval described by MPEG-7. Some approaches use directly XQuery as the retrieval language. Others define new query languages or adapt the existing ones. In [START_REF] Graves | Video retrieval using an MPEG-7 based inference network[END_REF], access methods based on an inference network model, that allows deduction of semantic and implicit information, are developed for searching MPEG-7 video descriptions. While in [START_REF] Liu | Queries of digital descriptions in MPEG-7 and MPEG-21 XML documents[END_REF], a specification of crucial query issues in MPEG-7 XML queries is proposed and a logic formalism called Path Predicate Calculus is illustrated to handle the limitations in current text-oriented XML query languages for multimedia XML queries. Spatial, temporal and visual datatypes and relationships can be described in this formalism for content retrieval. Notice that since the semantic aspects are not directly expressible in XQuery, these two approaches [START_REF] Graves | Video retrieval using an MPEG-7 based inference network[END_REF][START_REF] Liu | Queries of digital descriptions in MPEG-7 and MPEG-21 XML documents[END_REF] proposes their own specialized query language. However, in [START_REF] Fatemi | An XQuery adaptation for MPEG-7 documents retrieval[END_REF] an XQuery adaptation for MPEG-7 document retrieval called SVQL (Sematic Views Query Language), was proposed. SVQL is a high level query language that allows users to express their requirements following the semantic view model (PhysicalView, ProductionView, ThematicView, VisualView and AudioView) in a concise, abstract and precise way.

Our approach is complimentary to the existing ones, since we provide and hybrid query language where we combine the power of XQuery, to search the MPEG-7 descriptions, with the Datalog query language, to retrieve the multimedia data using the semantic aspect. The combination is done in a complimentary way in order to respond the user's queries.

The idea of adding semantic to multimedia data has been studied in several works. In [START_REF] Hunter | Adding multimedia to the semantic web -building an MPEG-7 ontology[END_REF], Hunter has proposed to employ RDF, RDF Schema (RDFS) and DAML+OIL to express the semantics of the MPEG-7 DSs and Ds in order to add multimedia to the semantic web. This work doesn't consider the multimedia content and the query language for the data. In [START_REF] Ch | An Ontology-Driven Framework for the Management of Semantic Metadata Describing Audiovisual Information[END_REF], a multimedia framework is developed for the support of ontology-based semantic indexing and retrieval of audiovisual content following the MPEG-7 and TV-Anytime standard specifications for metadata descriptions. The domain ontology is described using the MPEG-7 abstract tools which are not provided with reasoning mechanisms, then it's not possible to infer implicit information. In [START_REF] Troncy | Formalisation des connaissances documentaires et des connaissances conceptuelles l'aide d'ontologies : application la description de documents audiovisuels[END_REF], a framework which combine a knowledge representation language (OWL) and structural (XML Schema) was proposed to represent audiovisual documents. The content is expressed in OWL language whereas the structure is an MPEG-7 description. In [START_REF] Dasiopoulou | An Ontology Framework for Knowledge Assisted semantic Video Analysis and Annotation[END_REF], an ontology based approach for the knowledge assisted domain specific semantic video analysis. In this paper, the main goal was to reduce the gap between the low level features and the object layer. They didn't exploit the reasoning mechanisms provided by the DL language used to represent the knowledge. Moreover, they didn't deal with the query language of the descriptions.

Our work is quite similar to the work of [START_REF] Ch | An Ontology-Driven Framework for the Management of Semantic Metadata Describing Audiovisual Information[END_REF] and [START_REF] Troncy | Formalisation des connaissances documentaires et des connaissances conceptuelles l'aide d'ontologies : application la description de documents audiovisuels[END_REF], but we deal the representation of the multimedia data from a new point of view. Our contribution is the combination of the MPEG-7 and OWL-DL enhanced by rules to describe the multimedia content and the use of logical conjunctive queries and XQuery query languages for the query specification. The hybrid language (OWL-DL and Datalog rules) used provides a decidable reasoning algorithm to answer conjunctive queries. These combinations have not been considered in previous works.

Conclusion

In this paper, a framework of multimedia enriched domain ontologies have been presented, to be used in several tasks including content description and reasoning, as well as content retrieval. Our aim was to exploit the MPEG-7 abilities to represent the syntactic dimension of the multimedia data, and introduce a logical formalism, based on OWL-DL supplied by Datalog rules and more adequate, to represent the semantic dimension. XQuery is used to specify the metadata and structural part of the queries, whereas the Datalog query language is used to specify the semantic constraints. The MPEG-7 database is used to answer XQuery queries, whereas the knowledge base is used to answer the semantic queries.

For future work, we plan to explore this framework in an a real application and study the performances of the hybrid retrieval language (recall and precision). We plan also to in-vestigate the query relaxation and/or rewriting and consider query optimization techniques to get neighboring queries. Another direction of this work, is to formalize the structure of the MPEG-7 description in order to provide reasoning over the structure and the content of multimedia. We plan also to consider the framework in a distributed system, where the data are stored in different data sources.

  a finite set of transitivity axioms T rans(R) and role inclusion axioms R ⊑ S, where R and S are roles, such that if R ⊑ S ∈R , then Inv(R) ⊑ Inv(S) ∈Ras well. The reflexive transitive closure of the role inclusion relationship is denoted with ⊑ * . A role not having transitive subroles is called simple role. Let N C be a set of atomic concepts names. The set of SHIQ concepts over N C and N R is defined inductively as the smallest set for which the following holds: ⊤ and ⊥ are concepts, each atomic concept name A ∈ N C is a concept, if C and D are concepts and R is a role, then C ⊓D (concept conjunction), C ⊔ D (concept disjunction), ¬C (concept negation), ∀R.C (universal quantification), ∃R.C (existential quantification) are also concepts, and if C is a concept, R a simple role and n an integer, then ≥ nR.C and ≤ nR.C (number restriction) are concepts also. A TBox T over N C and R is a finite set of concept inclusion C ⊑ D or concept equivalence axioms C ≡ D, where C and D are concepts terms. Let N I be a set of individual (or instance) names. An ABox A is a set of assertions of concepts and role membership axioms C(a) and R(a, b), where C is concept term, R is a role, and a and b are individual symbols.

Table 1 . Extract of Soccer game ontology Ontology Concepts Actor roles hierarchy

 1 P erson ≤⊤, P layer ⊑ P erson ⊓∃play.T eam AreaP layer ⊑ P layer, Goalkeeper ⊑ AreaP layer Substitute ⊑ P layer, AreaP layer ⊓ Substitute ⊑⊥

	Game event hierarchy
	Event ≤⊤
	Ref ereeAction ⊑ Event ⊓∃r action.Ref eree
	GameAction ⊑ Event ⊓∃g action.P layer
	M iscellneous ⊑ Event ⊓∃m action¬(Referee ⊓ P layer)
	The concept Video
	V ideo ⊑ (≥ 1EventOccur.Event) ⊓(≥ 1Appear.P erson)
	Ontology roles
	AgentOf ⊑ P erson × Event
	P atientOf ⊑ P erson × Event
	M emberOf ⊑ P erson × T eam
	ResultOf ⊑ Event × Event
	play ⊑ P layer × M atch
	EventOccur ⊑ V ideo × Event
	Appear ⊑ V ideo × P erson
	Datalog rules
	R 1 : Eventactors(P 1 ,P

  [START_REF]XML Schema Part 1: Structures, W3C recommandation[END_REF]

http://www.chiariglione.org/mpeg/standards/mpeg-7/mpeg-7.htm


Ali Rahimi Khojasteh

Dominique Heitz

Sylvain Laizet

Lagrangian structure-function using stationarised fluid trajectories in the wake of a smooth cylinder

Lagrangian structure-function using stationarised fluid trajectories in the wake of a smooth cylinder Ali Rahimi Khojasteh a , Dominique Heitz b and Sylvain Laizet c

We present here a statistical study to determine the Lagrangian structure function in the anisotropic and inhomogeneous wake behind a smooth cylinder.

Figure 1 :

 1 Figure 1: Lagrangian second order structure function of the streamwise direction at four downstream locations. (a) As a function of non-dimensional timescale. (b) Re-dimensionalised structure function representing the C0 constant.

  Based on the extension of the stationary Lagrangian diffusion theory to self-similar flows, we stationarise velocity components in order to obtain Lagrangian statistics.Viggiano et al. (2011) 1 have shown how to obtain fundamental Lagrangian statistics from the anisotropic and inhomogeneous dynamics of a jet flow by normalizing the trajectories based on local Eulerian scales. In particular, computing the Lagrangian structurefunction scaling constant C0 is a crucial parameter in modelling turbulent transport. A similar role is played by the C0 constant in the Lagrangian framework as a Kolmogorov constant in the Eulerian framework. We performed direct numerical simulations (DNS) and time-resolved particle tracking velocimetry (4D-PTV) experimental analyses in the wake behind a smooth cylinder for Reynolds numbers between 300 to 3900. Details of the tracking algorithm used in the present study are addressed inKhojasteh et al. (2021) 2 . Preliminary results of the experiments indicated reasonable agreement between the stationarised Lagrangian trajectories of the wake flow and the hypothesis of Lagrangian self-similarity at inertial scales (see Fig.1).

	a INRAE, OPAALE, 35044 Rennes, France
	b Department of Aeronautics, Imperial College London, London, United Kingdom
	1 Viggiano et al., J. Fluid Mech. 918, 25 (2021).
	2 Khojasteh et al., Phys. Fluids 33, 095113 (2021).