Miguel Couceiro
email: miguel.couceiro@inria.fr

Amedeo Napoli
email: amedeo.napoli@inria.fr

Elements about Exploratory, Knowledge-Based, Hybrid, and Explainable Knowledge Discovery

Knowledge Discovery in Databases (KDD) and especially pattern mining can be interpreted along several dimensions, namely data, knowledge, problem-solving and interactivity. These dimensions are not disconnected and have a direct impact on the quality, applicability, and efficiency of KDD. Accordingly, we discuss some objectives of KDD based on these dimensions, namely exploration, knowledge orientation, hybridization, and explanation. The data space and the pattern space can be explored in several ways, depending on specific evaluation functions and heuristics, possibly related to domain knowledge. Furthermore, numerical data are complex and supervised numerical machine learning methods are usually the best candidates for efficiently mining such data. However, the work and output of numerical methods are most of the time hard to understand, while symbolic methods are usually more intelligible. This calls for hybridization, combining numerical and symbolic mining methods to improve the applicability and interpretability of KDD. Moreover, suitable explanations about the operating models and possible subsequent decisions should complete KDD, and this is far from being the case at the moment. For illustrating these dimensions and objectives, we analyze a concrete case about the mining of biological data, where we characterize these dimensions and their connections. We also discuss dimensions and objectives in the framework of Formal Concept Analysis and we draw some perspectives for future research.

Introduction

Knowledge discovery in databases (KDD) consists in processing possibly large volumes of data in order to discover patterns that can be significant and reusable. It is usually based on three main steps: data preparation, data mining, and interpretation of the extracted patterns (Figure 1) [START_REF] Zaki | Data Mining and Analysis: Fundamental Concepts and Algorithms[END_REF][START_REF] Tan | Introduction to Data Mining[END_REF]. KDD is interactive and iterative, controlled by an analyst who is a specialist of the domain and is in charge of selecting data and patterns, setting thresholds (frequency, confidence), replaying the process at each step whenever needed, depending on the interpretation of the selected patterns.

In the following, we consider four main dimensions within KDD which are based on data, knowledge, problem-solving, and interactivity.

-The data dimension: knowledge discovery is data-oriented by nature.

This dimension is related to the input of knowledge discovery and involves data preparation, e.g. feature selection, dimensionality reduction, and data transformation. The exploration of the data space and of pattern space are main operations. Moreover, the diversity and quality of data have an influence on the whole KDD process. -The knowledge dimension [START_REF] Janowicz | Why the Data Train Needs Semantic Rails[END_REF]: data are related to a particular domain. Hence knowledge discovery is knowledge-oriented and depends on domain knowledge that can be expressed, e.g., as constraints, relations, and preferences. The knowledge dimension is also attached to the control of KDD, possibly involving "meta-mining" [START_REF] Brazdil | Metalearning -Applications to Data Mining[END_REF]. Moreover, the output of KDD, i.e. the discovered patterns, may be represented as actionable knowledge units. -The problem-solving dimension [START_REF] Blockeel | Data Mining: From Procedural to Declarative Approaches[END_REF]: knowledge discovery is intended to solve various tasks for human or software agents and may be guided by the task at hand. The problem-solving dimension is dependent on iteration and search strategies. It can be data-directed, pattern-directed or goal-directed, and it can rely on declarative or procedural approaches. -Interactivity [START_REF] Brachman | The Process of Knowledge Discovery in Databases[END_REF]: knowledge discovery is interactive as the analyst may integrate constraints and preferences for guiding the data exploration, especially for minimizing the exploration of the data and pattern spaces. Interaction plays also a role in the evaluation of the quality of the patterns and in the activation of the different replay loops.

These four dimensions are interconnected and correspondences between them can be made explicit, especially in the framework of pattern mining [START_REF] Charu | Frequent Pattern Mining[END_REF]. Such correspondences support the following objectives of KDD:

-KDD is exploratory: the data dimension is related to an interactive exploration of the data and pattern spaces. We should be able to identify "seeds" or "prototypes" for guiding the pattern and data space exploration. Moreover, this exploration should be consistent w.r.t. domain knowledge and associated constraints. Threshold issues w.r.t. analyst queries can be addressed thanks to a skyline analysis within the pattern space or by integrating preferences. -KDD is knowledge-based: domain knowledge is related to control, i.e. meta-mining, constraints and preferences, explanations, and production of knowledge, materializing the links between knowledge discovery and knowledge engineering. We should be able to define environments within which knowledge discovery and knowledge engineering can be combined in an efficient and operational way. -KDD is hybrid: and may rely on the combination of numerical and symbolic data mining algorithms for solving problems. In addition, supervised and unsupervised learning methods can interact and be combined as well. -KDD is expected to be explainable: the output of knowledge discovery may be of different types, e.g. rules and classes or concepts, which can be reused for solving problems and decision making. In this way, elements supporting a decision -and especially an algorithmic decisionshould be available [START_REF] Túlio Ribeiro | Explaining the Predictions of Any Classifier[END_REF][START_REF] Bilal Zafar | From Parity to Preference-based Notions of Fairness in Classification[END_REF][START_REF] Grgic-Hlaca | Beyond Distributive Fairness in Algorithmic Decision Making: Feature Selection for Procedurally Fair Learning[END_REF].

In the following sections, we survey in more detail these different objectives and discuss their importance and their materialization. In the last section of this paper, we propose a synthesis that illustrates how Formal Concept Analysis (FCA [START_REF] Ganter | Formal Concept Analysis -Mathematical Foundations[END_REF]) can, more or less, fulfill these objectives. The paper terminates with a large bibliography which illustrates the content of this paper and some relations existing between pattern mining and FCA.

KDD should be Exploratory

In the KDD loop, exploration is related to data mining where the data space is searched and the patterns are mined. Exploration is also related to the notions of interaction and iteration, involving "replay", which is of main importance within knowledge discovery. This is discussed under different names in the literature, e.g. "exploratory data mining" and the loop "Mine, Interact, Learn, and Repeat" in [START_REF] De | Subjective Interestingness in Exploratory Data Mining[END_REF][START_REF] Matthijs Van Leeuwen | Interactive Data Exploration Using Pattern Mining[END_REF], "interactive data mining" in [START_REF] Holzinger | Knowledge Discovery and interactive Data Mining in Bioinformatics -State-of-the-Art, future challenges and research directions[END_REF], "declarative approaches in data mining" [START_REF] Blockeel | Data Mining: From Procedural to Declarative Approaches[END_REF], and "exploratory knowledge discovery" in [START_REF] Alam | Exploratory Knowledge Discovery over Web of Data[END_REF] (this list is certainly not exhaustive).

All these approaches are based on interaction and go back to the ideas underlying "exploratory data analysis" (EDA [START_REF] Tukey | Exploratory Data Analysis[END_REF]). The goal of EDA is to improve data analysis and result interpretation, providing the analyst with suitable techniques based on computational power, data exploration and visualization methods.

In the context of KDD, exploration can be achieved in various ways, using either data-directed or pattern-directed methods [START_REF] Buzmakov | Fast Generation of Best Interval Patterns for Nonmonotonic Constraints[END_REF], particular interestingness measures [START_REF] Buzmakov | Scalable Estimates of Stability[END_REF], and visualization procedures [START_REF] Alam | Exploratory Knowledge Discovery over Web of Data[END_REF]. Nonetheless, the knowledge discovery process should be efficient and automated as much as possible, while keeping facilities for interaction and iteration.

In the same way, let us quote some recent variations about the current exploratory approaches in pattern mining, namely constraint-based pattern mining, subgroup discovery, and exceptional model mining. Constraintbased pattern mining is based on skylines in [START_REF] Ugarte | Skypattern mining: From pattern condensed representations to dynamic constraint satisfaction problems[END_REF] in which preferences are expressed w.r.t. a dominance relation.

The goal of subgroup discovery [START_REF] Lavrac | Subgroup Discovery with CN2-SD[END_REF][START_REF] Belfodil | Anytime Subgroup Discovery in Numerical Domains with Guarantees[END_REF] is to find particular descriptions of subsets of a population that are sufficiently large and statistically unusual, i.e. subsets of the population that deviate from the norm. Such deviations are measured in terms of a relatively high occurrence, e.g. frequent itemset mining, or an unusual distribution for one designated target attribute. The latter is the common use of subgroup discovery, which is, in turn, related to exceptional model mining. Exceptional Model Mining (EMM [START_REF] Wouter Duivesteijn | Exceptional Model Mining -Supervised descriptive local pattern mining with complex target concepts[END_REF][START_REF] Kaytoue | Exceptional contextual subgraph mining[END_REF][START_REF] Anes | Mining exceptional closed patterns in attributed graphs[END_REF]) is aimed at capturing a general notion of interestingness in subsets of a dataset. EMM can be considered as a supervised local pattern mining framework, where several target attributes are selected, and a model over these targets is chosen to be the target concept.

KDD should be Knowledge-Based

There are many links between knowledge discovery and knowledge engineering. At each step of KDD, domain knowledge can be used to guide and to complete the process given in Figure 1. Actually, a fourth step can be considered in the KDD process, where selected patterns are represented as "actionable knowledge units" (see Figure 2). This involves a knowledge representation (KR) formalism and, subsequently, actionable units can be reused -by human or software agents-in knowledge graphs or knowledge systems for problem-solving.

Recently, efforts have been made to automate several tasks in KDD. Indeed, this is one main objective of meta-learning to design principles that can make algorithms adaptive to the characteristics of the data [START_REF] Brazdil | Metalearning -Applications to Data Mining[END_REF]. In [START_REF] Hilario | Ontology-Based Meta-Mining of Knowledge Discovery Workflows[END_REF][START_REF] Nguyen | Using Meta-mining to Support Data Mining Workflow Planning and Optimization[END_REF], authors consider meta-learning as the application of machine learning techniques to meta-data describing past learning experiences for adapting the learning process and improve the performance of the current model [START_REF] Hilario | Ontology-Based Meta-Mining of Knowledge Discovery Workflows[END_REF][START_REF] Nguyen | Using Meta-mining to Support Data Mining Workflow Planning and Optimization[END_REF] (a kind of "analogy"). Meta-learning is often related to the problem of dynamically solving or adjusting learning constraints. Most of the time, if there are no restrictions on the space of hypotheses to be explored by a learning algorithm and no preference criteria for comparing candidate hypotheses, then no inductive method can do better on average than random guessing. Authors in [START_REF] Hilario | Ontology-Based Meta-Mining of Knowledge Discovery Workflows[END_REF][START_REF] Nguyen | Using Meta-mining to Support Data Mining Workflow Planning and Optimization[END_REF] make a distinction between two main types of "biases", the representational bias restricts the hypothesis space whereas the preference-bias gives priority to certain hypotheses over others in this space. The most widely addressed meta-learning tasks are algorithm selection and model selection. Algorithm selection is the choice of the appropriate algorithm for a given task, while model selection is the choice of a specific parameter settings that produces a good performance for a given algorithm on a given task.

In the framework of KDD, meta-mining is not only meta-learning, since the KDD loop involves data preparation and pattern interpretation. Thus, the performance of the process and the quality of the discovered patterns and their usage are not only depending on the mining operation but also on data preparation -data selection, data cleaning, and feature selection-, pattern interpretation and possible pattern representation.

KDD should be Hybrid

Knowledge discovery should be able to work on various datasets with various characteristics, e.g. data can be either symbolic or numerical, or even more complex structured data such as sequences, trees, graphs, texts, linked data. . . The data management is based on different operations, including for example feature selection, dimensionality reduction, and noise reduction. Also, the mining approaches can be supervised or unsupervised, depending on the task at hand, and the availability of examples and counterexamples. As in every task, there is no universal approach which may be used alone to tackle and to solve all problems. Hence, a reasonable strategy is to design a hybrid process based on several tactics whose output is a combination of outputs of the involved procedures. Accordingly, in [START_REF] Grissa | A hybrid and exploratory approach to knowledge discovery in metabolomic data[END_REF], we aimed at discovering in metabolomic data a small set of relevant predictive features using a hybrid and exploratory knowledge discovery approach. This approach relies on adapted classification techniques which should deal with high-dimensional datasets, composed of small sets of individual and large sets of complex features. There are many possible classifiers that can be used and their application induces a bias on the results, calling for the simultaneous use of several classifiers. Hence, we adopted a kind of "ensemble approach" and we designed a set of classifiers instead of using a single one, to reach complementarity. The whole process is exploratory and hybrid as it combines numerical and symbolic classifiers. More details are given farther in Section 6.

To conclude, the combination of numerical and symbolic data mining algorithms remains rather rare, even if ensemble methods [START_REF] Thomas | Ensemble Methods in Machine Learning[END_REF][START_REF] Sagi | Ensemble Learning: A Survey[END_REF] are available without being always satisfactory.

KDD should be Explainable

Many recent progress in Machine Learning (ML) are mostly due to the success of Deep Learning methods in recognition tasks. However, Deep Learning and other numerical ML approaches are based on complex models, whose outputs and proposed decisions, as accurate as they are, cannot be easily explained to the layman [START_REF] Guidotti | A Survey of Methods for Explaining Black Box Models[END_REF]. Indeed, it is interesting to study hybrid ML approaches that combine complex numerical models with explainable symbolic models, in order to make ML methods more "interpretable". The objective is to attach what we could call "integrity constraints" -or kinds of "pre" and "post-conditions" to be fulfilled-to build and then deliver understandable explanations on the work of numerical ML models.

The objective of supervised ML is to learn how to perform a task (e.g. recognition) based on a sufficient number of training examples. The ML algorithm builds a model from the training examples which is then used on test examples. A model can be either symbolic, e.g. a set of rules or a hierarchy of concepts, or numerical, e.g. a set of weights associated with a structure as in neural networks. In practice, numerical models often prove to be more flexible and better suited to capture the complexity of some tasks such as recognition. However, symbolic ML models are more often used in pattern mining and in domains where the learning model should be understandable by human experts, or be related to domain ontologies for knowledge representation and reasoning purposes. Moreover, ML models approaches based on numerical models are more and more used for complex tasks such as decision making with a strong impact for human users, e.g. make a decision for a student orientation at university. In the latter case it can be very difficult to provide the necessary explanations justifying the decision using these numerical ML models, and especially models based on Deep Learning. Thus there is an emerging research trend whose goal is to provide interpretation and explanations about the decision of numerical ML algorithms such as Deep Learning.

Here, we are interested in understanding the different ways of providing explanations and facilitating interpretation of the outputs of numerical ML models [START_REF] Túlio Ribeiro | Explaining the Predictions of Any Classifier[END_REF]. There are several attempts to build explainable and trustable ML models. As mentioned above, one is to combine symbolic and numerical approaches and to build interactions between both approaches, as in [START_REF] Grissa | A Hybrid Knowledge Discovery Approach for Mining Predictive Biomarkers in Metabolomic Data[END_REF] which is based on a combination of numerical learning methods and Formal Concept Analysis [START_REF] Ganter | Formal Concept Analysis -Mathematical Foundations[END_REF], or in [START_REF] Sourek | Lifted Relational Neural Networks: Efficient Learning of Latent Relational Structures[END_REF] which is based on a combination of first-order logic and neural network learning.

There are also other initiatives, as in [START_REF] Hilario | Ontology-Based Meta-Mining of Knowledge Discovery Workflows[END_REF][START_REF] Nguyen | Using Meta-mining to Support Data Mining Workflow Planning and Optimization[END_REF], on the understandability of a mining process in terms of core components (modules), underlying assumptions, cost functions and optimization strategies being used. One subsequent idea is to understand how Deep Learning models can be decomposed w.r.t. such modules and then to integrate adapted explanation modules .

These are some other possible directions for analyzing a numerical ML model and provide plausible explanations about its output, as for example "neural-symbolic learning and reasoning" combinations [START_REF] Garcez | Neural-Symbolic Learning and Reasoning: Contributions and Challenges[END_REF][START_REF] Tran | Deep Logic Networks: Inserting and Extracting Knowledge From Deep Belief Networks[END_REF] that should be carefully examined and adapted.

An Application in the Mining of Metabolomic Data

In [START_REF] Grissa | A hybrid and exploratory approach to knowledge discovery in metabolomic data[END_REF], we presented a case study about the mining of metabolomic data using a combination of symbolic and numerical mining methods. Given a dataset composed of individuals described by features, the objective of the experiment is to discover subsets of features that can be discriminant and predictive. The discrimination power allows to build classes of individuals, where classes include similar individuals and separate dissimilar individuals at the best. The prediction power allows to determine the potential class membership of individuals, e.g. people who will develop the disease under study.

The classification process is split into two main procedures, one being supervised and the other unsupervised (see Figure 3). The supervised classification procedure is based on the design of N C numerical classifiers (including Random Forest and SVM in the present case) which are completed by preprocessing and postprocessing operations. This first procedure is applied to a bidimensional dataset composed of individuals and features. The output of this first procedure provides a set of ranked features RF for each of the N C classifiers.

Then the second procedure is based on a unsupervised mining operation applied to RF , the set of ranked features, for discovering the most frequent features, given a threshold set by the analyst. This second procedure is applied to a bidimensional dataset composed this time of |RF | features and N C numerical classifiers. The output of this second procedure provides a set F F of frequent features. These frequent features are the best candidates for becoming best discriminant features. Actually, there is a change of the representation space between the two classification procedures.

Following the classification process and the selection of most discriminant features, the latter are tested for evaluating their predictive capabilities using a ROC analysis [START_REF] Fawcett | An introduction to ROC analysis[END_REF].

For summarizing, this knowledge discovery strategy relies on two main steps: (i) a concurrent use of multiple classifiers producing a stable set of discriminant features, (ii) a classification of features based on FCA through a change of the problem space representation, where a small set of most relevant features is retained. In this classification process, we can distinguish the following elements:

-KDD is exploratory: two search strategies are run, the first on a data space individuals ˆf eatures and the second on a data space f eatures ˆclassif iers. The combination of these two exploration operations produces a set of most discriminant features which are then tested for prediction. -KDD is knowledge-based: the analyst is asked to control the process and the design of classifiers, to adjust the value of thresholds for dimensionality reduction and feature selection. The analyst plays also a similar role in the prediction analysis. -KDD is hybrid and involves numerical classifiers as well as more symbolic pattern mining methods. The latter are used for analyzing top-k ranked features w.r.t. discrimination and prediction. -KDD is explainable thanks to visualization. In particular, the pattern mining procedure involves FCA and the design of a concept lattice Fig. 3: A hybrid and exploratory approach to metabolomic data mining, with a classification process based on two procedures applied to two different bidimensional datasets. In addition, the "Replay" arrows show that the whole process is interactive and iterative.

where concepts represent classes of top-k ranked features. The distribution of the features within the lattice can be analyzed by the analyst for suggesting further test for prediction analysis.

This experiment shows how and why the different dimensions and objectives of KDD are contributing to deliver a more complete and qualitative analysis of metabolomic data.

7 Discussion: What about FCA?

We have introduced dimensions on which KDD is based, and objectives associated with these dimensions that may characterize KDD. Below we discuss how FCA could be considered w.r.t. these dimensions and objectives.

Starting from a binary table or context "object ˆattributes", FCA allows the discovery of concepts, where each concept materializes two interrelated views. Concepts have an extent which is composed of a set of objects and which stands for a class of individuals. Concepts have an intent which is composed of a set of attributes and which stands for a (class) description. Moreover, concepts can be organized within a poset, actually a concept lattice, based on subsumption relation. Thanks to the double view of concepts, the concept lattice can be related to a hierarchy of concepts in Description Logics [START_REF]The Description Logic Handbook[END_REF]. In addition, from the set of concepts, implications and association rules can be discovered and reused for knowledge discovery, representation and explanation purposes (see practical examples, e.g., in [START_REF] Bertet | Lattices, closures systems and implication bases: A survey of structural aspects and algorithms[END_REF][START_REF] Carpineto | Concept Data Analysis: Theory and Applications[END_REF][START_REF] Duquenne | Latticial Structures in Data Analysis[END_REF][START_REF]Formal Concept Analysis, Foundations and Applications[END_REF][START_REF] Ganter | Conceptual Exploration[END_REF]). Now, when it is necessary to deal with complex structured data, pattern structures [START_REF] Ganter | Pattern Structures and Their Projections[END_REF][START_REF] Kaytoue | Mining Gene Expression Data with Pattern Structures in Formal Concept Analysis[END_REF] extend the capabilities of FCA, while keeping the good properties of FCA. Many applications are based on pattern structures where object descriptions are intervals, sequences, trees and graphs [START_REF] Kaytoue | Pattern Structures and Concept Lattices for Data Mining and Knowledge Processing[END_REF]. Another extension of FCA, namely Relational Concept Analysis [START_REF] Rouane-Hacene | Relational concept analysis: mining concept lattices from multi-relational data[END_REF], allows to explicitly deal with relations between objects and to build object intents with relational attributes.

Hence FCA is naturally exploratory and exploration is based on the concept lattice structure. The exploration is often data-directed but there are some attempts to design pattern-directed processes [START_REF] Buzmakov | Fast Generation of Best Interval Patterns for Nonmonotonic Constraints[END_REF]. The exploration is also aimed at selecting concepts of interest w.r.t. interestingness measures such as stability for example [START_REF] Buzmakov | Scalable Estimates of Stability[END_REF][START_REF] Kuznetsov | On interestingness measures of formal concepts[END_REF]. More recently, there is a trend of research on exploration directed by the MDL principle [START_REF] Vreeken | Interesting Patterns[END_REF][START_REF] Makhalova | A First Study on What MDL Can Do for FCA[END_REF], exhibiting the links existing with subgroup discovery and exceptional model mining. In particular the selection of initial seeds and the construction of good object coverings are important questions.

Continuing on exploration and interaction, there is a whole line of work on the use of graphical tools for interacting with the lattice structure, for visualizing concepts, and selecting concepts of interest [START_REF] Eklund | A Survey of Hybrid Representations of Concept Lattices in Conceptual Knowledge Processing[END_REF][START_REF] Alam | Exploratory Knowledge Discovery over Web of Data[END_REF]. Visualization has always been a main concern for FCA practitioners as the lattice structure can be rather easily understood and interpreted. In the same way, the exploration of the concept lattice allows different types of information retrieval [START_REF] Codocedo | Formal Concept Analysis and Information Retrieval -A Survey[END_REF][START_REF] Codocedo | A semantic approach to concept lattice-based information retrieval[END_REF] and related operations such as recommendation and biclustering [START_REF] Kaytoue | Biclustering meets triadic concept analysis[END_REF][START_REF] Kaytoue | Three interrelated FCA methods for mining biclusters of similar values on columns[END_REF].

But FCA is also knowledge-based as it allows, especially in the case of pattern structures and RCA, to take into account domain knowledge under different forms. For example there is a number of studies on the use of attribute hierarchies within a context (this was initiated in [START_REF] Carpineto | Concept Data Analysis: Theory and Applications[END_REF], actualized in [START_REF] Ganter | Pattern Structures and Their Projections[END_REF], and then in [START_REF] Alam | Exploratory Knowledge Discovery over Web of Data[END_REF]). Furthermore, there are also other attempts for discovering definitions in the web of data that can be reused as concept definitions in ontologies and knowledge graphs [START_REF] Alam | Mining Definitions from RDF Annotations Using Formal Concept Analysis[END_REF].

Furthermore, FCA shows many links with knowledge engineering, while, until now, there does not exist any type of meta-level in FCA. Such a metalevel could take several forms, for example introducing a kind of metaconcepts for providing knowledge about the management of the concepts, or meta-rules for generating or controlling implications and association rules. Still on knowledge construction, we should mention attribute exploration [START_REF] Ganter | Conceptual Exploration[END_REF] which enables the completion of a context and the exploration of rule sets and concept sets among others. However, FCA is not hybrid and does not offer any explanation facility strictly speaking. There are some experiments already mentioned showing that FCA can be combined with numerical machine learning methods for performing knowledge discovery tasks. In [START_REF] Grissa | A Hybrid Knowledge Discovery Approach for Mining Predictive Biomarkers in Metabolomic Data[END_REF] the concept lattice is also used in an interactive way for concept selection and in a certain sense for providing plausible explanations. Other attempts on hybridization can be found in [START_REF] Hristoskova | An Integrative Clustering Approach Combining Particle Swarm Optimization and Formal Concept Analysis[END_REF][START_REF] Yoneda | Learning graph representation via formal concept analysis[END_REF].

To conclude, let us mention some research topics that have not received too much attention within FCA, and that we think should deserve more attention in the future, namely the construction of a meta-level, the hybridization with numerical methods, and the production of explicit explanations. This is a vast program, and a series of articles will hopefully emerge in a near future to tackle these open subjects.

Fig. 1 :

 1 Fig. 1: The KDD loop.

Fig. 2 :

 2 Fig. 2: The augmented KDD loop.


Yessine Ayed

Guénaël Germain

Anna-Maria Pubill Melsio

Pierre Kowalewski

• G Germain

• A Pubill Melsio

• P Kowalewski

• D Locufier

Impact of supply conditions of liquid nitrogen on tool wear and surface integrity when machining the Ti-6Al-4V titanium alloy

Keywords: Tool wear, Cryogenic-assisted machining, Liquid nitrogen, Titanium alloy

come

Impact of supply conditions of liquid nitrogen on tool

wear and surface integrity when machining the Ti-6Al-4V titanium alloy

Introduction

Titanium alloys present very interesting assets in the aerospace, marine, and biomedical fields especially due to Y. Ayed yessine.ayed@ensam.eu their excellent mechanical characteristics, their corrosion resistance, and their low density. However, the machining of these alloys is particularly challenging [START_REF] Ezugwu | Titanium alloys and their machinability-a review[END_REF][START_REF] Jawaid | Tool wear characteristics in turning of titanium alloy ti-6246[END_REF]. This is mainly due to their good mechanical properties (resulting in high cutting forces), their very high chemical reactivity (resulting in high cutting forces) with most cutting materials. The temperatures reached in the cutting zone are very high and accelerate certain wear phenomena, which greatly reduce the tool life. All these constraints limit the range of possible cutting conditions. The tool must therefore be strongly cooled. Among the solutions that have been developed to overcome these problems is machining assistance such as laser-assisted machining [START_REF] Rashid | An investigation of cutting forces and cutting temperatures during laser-assisted machining of the ti-6cr-5mo-5v-4al beta titanium alloy[END_REF][START_REF] Rashid | The response of the high strength ti-10v-2fe-3al beta titanium alloy to laser assisted cutting[END_REF][START_REF] Ayed | Experimental and numerical study of laser-assisted machining of ti6al4v titanium alloy[END_REF][START_REF] Xi | Numerical modeling of laser assisted machining of a beta titanium alloy[END_REF], high pressure lubrication-assisted machining [START_REF] Da Silva | Tool life and wear mechanisms in high speed machining of ti-6al-4v alloy with pcd tools under various coolant pressures[END_REF][START_REF] Ayed | Degradation modes and tool wear mechanisms in finish and rough machining of ti17 titanium alloy under high-pressure water jet assistance[END_REF][START_REF] Ayed | Tool wear analysis and improvement of cutting conditions using the high-pressure water-jet assistance when machining the ti17 titanium alloy[END_REF][START_REF] Yunlu | Taguchi doe analysis of surface integrity for high pressure jet assisted machining of inconel 718[END_REF][START_REF] Braham-Bouchnak | Influence of high-pressure coolant assistance on the machinability of the titanium alloy ti555-3[END_REF], and cryogenic assisted machining, the subject of this study.

The cryogenic cooling consists of injecting a low temperature liquefied gas (liquid nitrogen or CO 2 ) into the cutting zone, which improves the dissipation of the heat generated in this area, causing the temperature to drop. This reduction in temperature reduces the effect of certain wear mechanisms, increases tool life, and may improve the surface integrity [START_REF] Krishnamurthy | Increasing efficiency of Ti-alloy machining by cryogenic cooling and using ethanol in MRF[END_REF][START_REF] Dhar | Machining of aisi 4140 steel under cryogenic cooling-tool wear, surface roughness and dimensional deviation[END_REF][START_REF] Hong | New cooling approach and tool life improvement in cryogenic machining of titanium alloy ti-6al-4v[END_REF]. In addition, machining with cryogenic assistance is similar to a dry machining in that the chips are not contaminated by the cutting fluid, simplifying recycling. The entire lubrication processing chain, which is very expensive, can thus be removed. Hence, this type of assistance has a significant ecological, environmental, and economic impacts.

In the few recent years, cryogenic assistance has became an interesting and a growing field of research. Hong et al. [START_REF] Hong | New cooling approach and tool life improvement in cryogenic machining of titanium alloy ti-6al-4v[END_REF][START_REF] Hong | Friction and cutting forces in cryogenic machining of ti-6al-4v[END_REF] compared different cryogenic cooling strategies; it has been evidenced that the cryogenic cooling allows a remarkable increase of tool life. However, cutting forces become higher due to the increase of material strength and hardness. A significant reduction of the cutting temperature and an improved tool life have been obtained when machining AISI 4140, Inconel, Tantalum, silicon nitride ceramic, and titanium [START_REF] Dhar | Machining of aisi 4140 steel under cryogenic cooling-tool wear, surface roughness and dimensional deviation[END_REF][START_REF] Wang | Cryogenic machining of tantalum[END_REF][START_REF] Wang | Cryogenic machining of hard-to-cut materials[END_REF]. Venugopal et al. [START_REF] Venugopal | Tool wear in cryogenic turning of ti-6al-4v alloy[END_REF][START_REF] Venugopal | Growth of tool wear in turning of ti-6al-4v alloy under cryogenic cooling[END_REF] showed that tool life has been enhanced from 7 min under dry machining to 24 min under cryogenic cooling; the use of the cryogenic cooling results in a reduction of tool wear on both crater and flank faces. According to studies carried out by Dhar et al. [START_REF] Dhar | Cutting temperature, tool wear, surface roughness and dimensional deviation in turning aisi-4037 steel under cryogenic condition[END_REF] and Khan et al. [START_REF] Khan | Improving tool life using cryogenic cooling[END_REF], cryogenic cooling presents various advantages when machining AISI 4037 and 304L stainless steel. Indeed, better surface finish and a considerable increase of tool life (four times) are obtained. It has been noted that cryogenic assistance is more effective at high cutting speeds and high feed rates. Bicek et al. [START_REF] Bicek | Cryogenic machining as an alternative turning process of normalized and hardened aisi 52100 bearing steel[END_REF] reported that cryogenic assistance enhance tool life of about 370% when machining AISI 52100 bearing steel. The residual stresses become 300-400% more compressive and the white layer is supressed. The turning of AISI 304 stainless steel using the MQL+cryogenic cooling results in doubling tool life according to Pereira et al [START_REF] Pereira | Cryogenic and minimum quantity lubrication for an eco-efficiency turning of aisi 304[END_REF]. The machining of Ti-6Al-4V using the liquid nitrogen lubrication seems to give good results compared to the conventional machining [START_REF] Dhananchezian | Cryogenic turning of the ti-6al-4v alloy with modified cutting tool inserts[END_REF][START_REF] Bermingham | New observations on tool life, cutting forces and chip morphology in cryogenic machining ti-6al-4v[END_REF]; the cutting temperature decreases of about 60% and tool wear is significantly reduced. Shokrani et al. [START_REF] Shokrani | Investigation of the effects of cryogenic machining on surface integrity in end milling of ti-6al-4v titanium alloy[END_REF] reported that the cryogenic cooling has improved surface roughness when machining Ti-6Al-4V titanium alloy. According to Jerold and Kumar [START_REF] Jerold | Experimental investigation of turning aisi 1045 steel using cryogenic carbon dioxide as the cutting fluid[END_REF], the cryogenic cooling using liquid CO 2 is more effective at high cutting speeds and feed rates. Machai and Biermann [START_REF] Machai | Machining of β-titanium-alloy ti-10v-2fe-3al under cryogenic conditions: Cooling with carbon dioxide snow[END_REF] demonstrated that tool life can be increased over two times when machining Ti-10V-2Fe-3Al titanium alloy. They have also remarked that the chemical reactivity of this β titanium alloy is not affected by the liquid CO 2 cooling. The cryogenic turning of ZK60 Mg alloy permits a reduction in cutting temperature of about 60% and the improvement of the micro-hardness of the machined surface by about 40% [START_REF] Dinesh | Effect of cryogenic cooling on machinability and surface quality of bio-degradable zk60 mg alloy[END_REF]. The study carried out by Bordin et al. [START_REF] Bordin | Analysis of tool wear in cryogenic machining of additive manufactured ti6al4v alloy[END_REF][START_REF] Bordin | Experimental investigation on the feasibility of dry and cryogenic machining as sustainable strategies when turning Ti6Al4V produced by additive manufacturing[END_REF] showed that cryogenic assistance allows a significant increase in tool life when machining additive manufactured Ti6Al4V alloy. However, the adhesive wear remains the main tool wear mechanism. Krolczyk et al. [START_REF] Krolczyk | Dry cutting effect in turning of a duplex stainless steel as a key factor in clean production[END_REF] and Maruda et al. [START_REF] Maruda | The influence of the cooling conditions on the cutting tool wear and the chip formation mechanism[END_REF] discussed the environmentally friendly cutting processes (dry, MQCL and MQCL+EP/AW) and their impacts on cutting forces, surface roughness, and tool wear. An interesting investigation carried out by Iturbe et al. [START_REF] Iturbe | Surface integrity analysis when machining inconel 718 with conventional and cryogenic cooling[END_REF] has demonstrated that tool life decreases when machining Inconel 718 using the cryo-genic+MQL assistance. As reported by the authors, this is due to a deep hardened layer formed under the action of the cryogenic liquid. These constatations are in agreement with the results found by Tebaldo et al. [START_REF] Tebaldo | Sustainability in machining: "eco-friendly" turning of inconel 718. surface characterisation and economic analysis[END_REF].

Most of these studies were focused on the impact of the cryogenic assistance on tool life, surface integrity, and cutting temperature. They have been conducted using standard tools and without taking into account lubrication parameters. The objective of this study is therefore to investigate the impact of the flow rate and the pressure of the cryogenic fluid on tool life, wear mechanisms, and surface integrity.

Experimental setup

Turning tests have been carried out on Leadwell LTC25iL (2500 rev/min, 24kw) CNC lathe. The liquid nitrogen has been conditioned in a 180 liter ranger and it has been supplied to the tool through thermally insulated pipes. The dimensions of the Ti-6Al-4V workpiece are respectively D = 180 mm and L = 250 mm. Due to the high chemical reactivity of titanium alloys, uncoated H13A carbide inserts have been used (CCMT 12-04-08KM). The evolution of tool wear has been tracked using a stereo microscope and a scanning electron microscope (SEM) according to the standard 3685:1993. The critical value of the flank wear V B is set to 0.3 mm. In addition, in order to investigate tool wear mechanisms, energy-dispersive X-ray spectroscopy (EDS) analysis has been carried out. Concerning the surface integrity, it has been checked out basing on X-ray diffraction and surface roughness measurement. Finally, the cutting forces have been measured using a measuring chain composed of a Kistler 9257B piezoelectric dynamometer, a HBM CD600 charge amplifier and a HBM MX440A 24 bit A/D converter. The experimental setup is illustrated by In order to measure the mass flow rate, the liquid nitrogen ranger has been suspended and attached to a HBM S9M/5KN load cell. Indeed, the loss of weight at the level of the ranger makes it possible to calculate the mass flow rate. Figure 2 shows the measuring system. First of all, preliminary tests have been carried out in order to determine the correspondence of the flow rate with the nozzle diameter, for a given pressure. The tests have been carried out as follows:

-Select the nozzle diameter.

Tool wear

The first series of tests consists in varying the flow rate of the liquid nitrogen while maintaining the pressure constant. Figure 3 shows the results of these trials. First of all, it could be remarked that the cryogenic assistance allows a significant increase of tool life compared to dry machining or to conventional lubrication (emulsion). It allows, in the worst case, to increase the tool life of about four times compared to the dry machining. This is mainly due to the drop of the cutting temperature, which results in a slowdown of certain wear mechanisms evolution. Moreover, these tests demonstrate that the LN2 flow rate has a great impact on tool life. Indeed, the obtained results with a flow rate of 3.0 l/min are better than those obtained with a flow rate of 1.6 l/min whatever the pressure of the liquid nitrogen. Figure 3a shows that after 15 min of machining, the flank wear does not exceed 0.2 mm with a flow rate of 3.0 l/min.

The second series of tests consists in varying the pressure of the liquid nitrogen while maintaining the flow rate constant (low pressure LP and high pressure HP). Figure 4 spotlights the impact of LN2 pressure on tool wear. On the one hand, in the low flow rate condition (LFR), tool life has been multiplied by 3. The high pressure condition results in the best tool performance. On the other hand, in the high flow rate condition (HFR), the impact of the LN2 pressure is more pronounced. Tool life has been multiplied by 4.8 at low pressure condition. Hence, it could be noted that the results obtained from LFR+HP and HFR+LP are very close; this is very interesting especially in order to optimize the LN2 consumption. Overall, the best results have been obtained at high pressure and at high flow rate.

In order to investigate tool wear mechanisms, the cutting edges have been observed firstly using a scanning electron microscope. Figure 5a shows the formation of a built-up-edge (BUE), a built-up layer (BUL), and the early formation of a crater. All these observations are the symptoms of different tool wear mechanism, particularly diffusion and adhesion. In order to have more extensive investigation, EDS analysis has been carried out and has permitted to draw a distribution map of the existing elements on the tool rake face. Figure 5b shows the material adhesion zones on the tool rake face. Indeed, the entire area tool/chip is coated with titanium deposits (red). This is mainly due to the strong chemical affinity of the titanium alloy, the high cutting temperature and the high contact pressures. In fact, in some cases, the formation of adherent layers may protect tool. However, when their formation reaches a stagnation level, adhesive occurs. This involves the pulling-out of deposits and consequently the tearing-off of the stacked carbide grains.

In the case of the cryogenic machining, the phenomenon of adhesion is slightly less important as demonstrated by Fig. 6a,b. Hence, it can be concluded that remains the main tool wear mechanism in both cases. Indeed, even if cryogenic assistance can significantly reduce the temperature in the cutting zone (which slows some tool wear mechanisms) and thus increases tool life, the liquid nitrogen can not access the contact area tool/chip. Temperature levels at tool tip still important and wear continue to involve even if it has been slowed down by the action of the liquid nitrogen [START_REF] Krishnamurthy | Increasing efficiency of Ti-alloy machining by cryogenic cooling and using ethanol in MRF[END_REF][START_REF] Dhar | Machining of aisi 4140 steel under cryogenic cooling-tool wear, surface roughness and dimensional deviation[END_REF][START_REF] Hong | New cooling approach and tool life improvement in cryogenic machining of titanium alloy ti-6al-4v[END_REF].

a b

Surface integrity

The surface integrity of a workpiece is a crucial and a critical parameter that requires special monitoring. Indeed, it integrates surface roughness, residual stresses, and microstructure. Regarding the residual stresses, they are mainly due to the combination of mechanical and thermal loads. The question that arises now concerns the influence of the cryogenic assistance on surface integrity. To respond to this question, different types of measurements have been performed. First of all, the cutting forces (F f : feed force, F c : cutting force, F p : passive force) have been measured for all tests (with

F = F f 2 + F c 2 + F p 2 )
. Figure 7a shows an increase of efforts levels with the increase of the flow rate (15% maximum). This might be due to the fact that the liquid nitrogen jet cools not only the cutting area but also a part of the workpiece. Hence, the hardness and the mechanical characteristics of the material increase which subsequently induces an increase of the cutting forces. Cryogenic assistance does not seem to influence the surface roughness as demonstrate by Fig. 7b. The evolution of R a does not appear significant. These measurements have been carried out using MarSurf PS1 with a cutoff of 0.8 mm. All tests have been repeated three times at least.

After that, the residual stress measurements have been carried out using PROTO iXRD. Analysis results showed a significant improvement of the residual stress using the cryogenic assistance. Compared to the dry machining condit ion, the compressive residual stress level has been doubled (from -200 to -430 MPa). It can also be pointed out a significant influence of the liquid nitrogen flow rate and pressure as shown by Fig. 8. At the same pressure (HP), the increase of the flow rate from 1.6 l to 3.0 l/min has permitted to increase the compressive residual stress of about 120 MPa (40%). However, at the same flow rate (3.0 l/min), the pressure decrease (from 10 to 5 bar) has caused a degradation of the residual stress of about 27% as illustrated by Fig. 8b.

As the mechanical loads induce compressive stresses while the thermal loads induce tensile stresses, the observed differences could be due to the attenuation of the thermal effects and the cutting forces increase. In fact, an effective cryogenic cooling of the cutting area permits to reduce temperature as reported by many authors [START_REF] Dhar | Machining of aisi 4140 steel under cryogenic cooling-tool wear, surface roughness and dimensional deviation[END_REF][START_REF] Wang | Cryogenic machining of tantalum[END_REF][START_REF] Wang | Cryogenic machining of hard-to-cut materials[END_REF][START_REF] Dhananchezian | Cryogenic turning of the ti-6al-4v alloy with modified cutting tool inserts[END_REF][START_REF] Bermingham | New observations on tool life, cutting forces and chip morphology in cryogenic machining ti-6al-4v[END_REF][START_REF] Dinesh | Effect of cryogenic cooling on machinability and surface quality of bio-degradable zk60 mg alloy[END_REF]; this will reduce the contribution of tensile stresses and the overall residual stress become more compressive. In addition, the increase in cutting forces will lead to an increase in residual stresses of mechanical origin. Thus, the combination of these effects could explain the great improvement of the compressive residual stresses.

Discussion

In order to confirm the obtained results, a complementary series of tests has been carried out with a flow rate around 1.4 l/min (Fig. These tests showed that at very low flow rate the LN2 pressure does not have a remarkable impact on tool wear. It should be noted that under these conditions, the jet of nitrogen is no longer liquid but rather a mixture of gas and liquid which considerably reduces its cooling capacity [START_REF] Pusavec | Analysis of the influence of nitrogen phase and surface heat transfer coefficient on cryogenic machining performance[END_REF]. The cryogenic lubrication permits to slow down the evolution of certain wear mechanisms that are activated at high temperatures and thus slowing down the tool wear evolution. The SEM and EDS analysis showed that the main tool wear mechanism is adhesion. Despite the cryogenic cooling, wear continues to evolve; this evolution is very sensitive to the liquid nitrogen flow rate and pressure. The liquid nitrogen jet that cools the better the tool/chip contact zone ensures the longest tool life by reducing and slowing down the evolution of these mechanisms. Moreover, under these conditions, cutting forces increase has been recorded. It could be due to the workpiece hardness increase at cryogenic temperatures.

Residual stresses are also highly impacted by lubrication conditions. The best results are obtained with the best cooling conditions; the fact of reducing cutting temperature, reduces the contribution of thermal loads responsible of traction residual stresses. Moreover, the contribution of the mechanical loads becomes more important due to the cutting forces increase. The reduction of the thermal loads and the increase of the mechanical loads may explain the recorded improvements of the compressive residual stresses.

It is thus crucial to optimize lubrication condition and in particular (pressure, flow rate) couple. In a first approach, it seems that the LN2 pressure has more impact on tool wear than the flow rate. It would be interesting in this case, and in order to reduce LN2 consumption and subsequently costs, to have to highest possible pressure and then to optimize flow rate. In the light of this study, it would be interesting to focus the research not only on the processes but also on the lubrication parameters: liquid nitrogen delivery system, the number and the diameter of nozzles, reducing the loss of load inside the tool holder, etc. It is thus necessary to re-concept the existing tool holders for a better cutting performance.

a b

Conclusion

This study has allowed to investigate the impact of the pressure and the flow rate of the liquid nitrogen on tool life and surface integrity. Based on the different tests and analysis, it has been demonstrated that cryogenic cooling can significantly increase tool life, at least four times. Tool wear evolution strongly depends on lubrication parameters notably the flow rate. The best tool performance has been obtained at high flow rate and high pressure. Under these conditions, the flank wear has not exceed 0.2 mm after 15 min of machining. According to the EDS analyses, adhesive wear remains the most influential wear mechanism. The cutting effort is slightly increased with cryogenic assistance.

Concerning the residual stresses, a great improvement has been noticed especially at high flow rates, which would mainly due to the attenuation of thermal loads. However, the surface roughness does not significantly vary using the cryogenic assistance.

Hence, it seems that the cryogenic assistance presents an interesting alternative to conventional machining from an ecological and technical point of view. Finally, it is necessary to point out that this study has permitted to respond to some scientific inquiries but it has raised other challenges which open up many perspectives to optimize this process.

Fig. 1 aFig. 2 aFig. 1 .

 121 Fig. 1 a Experimental setup. b High-speed camera acquisition

Fig. 3

 3 Fig. 3 Evolution of tool wear (V c = 80 m/min, a p = 1 mm f , f = 0.2 mm/rev). a High pressure (HP). b Low pressure (LP)

Fig. 4

 4 Fig. 4 Evolution of tool wear (V c 80 m/min, a p = 1 mm f , f = 0.2 mm/rev). a High flow rate. b Low flow rate

Fig. 5

 5 Fig. 5 Tool wear analysis (dry machining; T = 2.5 min; VB = 0.31 mm). a SEM analysis. b EDS analysis

Fig. 6 Fig. 7 a

 67 Fig. 6 Tool wear analysis (HP; 3.0 l/min; T = 15 min; VB = 0.19 mm). a SEM analysis. b EDS analysis

Fig. 8 Fig. 9

 89 Fig. 8 Surface residual stress. a Flow rate influence. b Pressure influence

Table 1

 1 Calibration of the flow rate and the pressure

	Liquid nitrogen pressure 8-10 bar Liquid nitrogen pressure 4-5 bar
	Nozzle diameter Flow rate	Nozzle diameter Flow rate
	(mm)	(l/min)	(mm)	(l/min)
	1.6	1.6 ± 0.2	2.2	1.6 ± 0.2
	2.5	3.2 ± 0.2	3.0	3.0 ± 0.2

-Open the nitrogen valve and measure the weight loss of the ranger. -Calculate the mass flow rate.

Table

1

summarizes the results of these tests.


R Fablet
email: rfablet@irisa.fr

P Bouthemy
email: bouthemy@irisa.fr

P P Rez
email: perez@irisa.fr

Statistical Motion-Based Video Indexing and Retrieval

We propose an original approach for the characterization of video dynamic content with a view to supplying new functionalities for motion-based video indexing and retrieval with query by example. We have designed a statistical framework for motion content description without any prior motion segmentation, and for motion-based video classi cation and retrieval. Contrary to other proposed methods, we do not extract from a given video s e quence a set of motion features but we identify a global probabilistic model, expressed as a temporal Gibbs random eld. This leads to de ne a e cient statistical motion-based similarity measure, relying on the computation of conditional likelihoods, to discriminate various motion contents. We have carried out experiments on a set of 100 video sequences, representative of various motion situations temporal textures as re and crowd motions, sport videos, car sequences, low motion activity examples. We have obtained promising results both for the video classi cation step and for the retrieval process.

Introduction

Archiving video information is of growing importance in various application elds. Reliable and convenient access to visual information is then of major interest for an e cient use of these databases. This implies indexing and retrieval of visual documents by their content. A great deal of research amount is currently devoted to image and video database management, AZP96,BMM99 . Nevertheless, it remains hard to easily identify relevant information with regards to a given query, due to the complexity of dynamic scene analysis.

Another important aspect of video database management lies in the de nition of appropriate similarity measures associated to the description of video content. It should provide users with e cient tools for the classi cation of video sequences into various types sports, news, movies, commercials, . . . FLE95,NKFH98,VL98 , for the retrieval of examples similar to a given video query FB99,JVX99 , or for e cient video browsing using high-level structuring such as macrosegmentation RHM99,YYL96 .

Once the video has been segmented into shots BGG99,ZWZS97 , the issue is to deliver an interpretation and a representation of the shot content. 1 Most approaches rely on the selection of a set of key-frames and on their description using texture or color features FT98 . However, motion information should not be neglected and is part of the cues to be considered in the context of video indexing, in particular for activity classi cation or action recognition. In this paper, we focus on this aspect and we aim at providing a statistical scheme for shot description based on dynamic content analysis and the associated measure of motion-based shot similarity.

To cope with motion information, two main categories of approaches can bedistinguished. The rst one exploits segmentation, tracking and characterization of moving elements in order to determine a spatio-temporal representation of the video shot Courtney97,FTM98,GB98 . To this end, they use either parametric motion models or dense optical ow elds. Then, the description of motion content generally relies either on the extraction of qualitative pertinent features for the entities of interest e.g., related to the direction of the displacement GB98 , or to the the trajectory of the center of gravity of the tracked objects DAKGK00 , or on the computation of global histograms of estimated dense optical ow elds AC97,JVX99 . However, some kinds of video cannot be handled in such a way. For instance, when considering complex dynamic contents involving motion of rivers, ames, foliages in the wind, or crowds, it reveals impossible to extract and track relevant stable local primitives. Furthermore, as far as video indexing is concerned, the entities of interest may not be single objects but rather groups of objects, in particular when dealing with sport videos. No tool currently exists to automatically extract such entities.

These remarks led to consider another category of methods providing attractive analysis of motion information in the context of content-based video indexing. Our goal is to cope with the interpretation of dynamic contents without any explicit prior motion segmentation. Primary work in that direction NP92 results in the de nition of temporal textures which include for instance motions of rivers, foliages, ames, or crowds. Di erent techniques for temporal texture feature extraction have been proposed BF98,FB99,NP92,OHSF98,SP96 . In OHSF98 , descriptors are extracted from the characterization of surfaces derived from spatio-temporal trajectories. In NP92 , features issued from spatial cooccurrences of normal ows are exploited to classify sequences either as simple motions rotation, translation, divergence or as temporal textures. In previous work BF98,FB99 , we have considered global features extracted from temporal cooccurrence distributions of local motion-related information more reliable than the normal velocity. In this paper, we propose to extend the latter work in order to deliver in an uni ed way a probabilistic modeling of dynamic content and an associated statistical scheme for motion-based video indexing and retrieval.

The paper is organized as follows. The general ideas underlying our work are presented in Section 2. Section 3 describes the local non-parametric motion-related information that we use. In Section 4, we introduce the probabilistic modeling associated to the spatio-temporal distribution of local motion-related quantities. The proposed statistical framework for motionbased indexing and retrieval is presented in Section 5. Section 6 contains classi cation results and retrieval examples over a set of video sequences. Concluding remarks are reported in Section 7.

Problem statement

As pointed out above, proposed approaches for temporal texture analysis mainly rely on the extraction of a set of numerical descriptors. As a consequence, the comparison of shot content is performed in the feature space according to a given metric such as the Euclidean distance or more appropriate measures SJ99 . Besides, to deal with video databases involving various dynamic contents, it is necessary to determine an optimal set of features and the associated similarity measure, using either principal component analysis MSP96 or some feature selection techniques JZ97 . Nevertheless, feature space is usually of high dimension, and the considered distance is likely not to capture properly uncertainty attached to feature measurements.

To cope with these issues, it seems more relevant to adopt a statistical point of view which may deliver a uni ed view for learning and classi cation. We introduce a motion classi cation approach for video indexing which relies on a statistical analysis of the spatio-temporal distribution of local non-parametric motion-related information. We aim at identifying probabilistic models corresponding to di erent dynamic content types to be discriminated. We exploit a correspondence between cooccurrence measurements and Markov Random Field MRF models established in the context of spatial texture analysis in Gimelfarb96 , and we propose an extension to temporal textures see Section 4. We consider only temporal models, which allows us to easily compute the involved likelihood functions. This property leads to de ne a general statistical framework for video indexing and retrieval see Section 5. In particular, we have designed a technique for hierarchical video classi cation based on an approximated Kullback-Liebler divergence see subsection 5.1. The retrieval process is stated as a Bayesian inference issue conducted through the extracted video hierarchy see subsection 5.2.

Motion information

The rst step of our approach is to de ne appropriate motion-related measurements whose spatio-temporal distributions will be interpreted. Since we aim at characterizing the actual dynamic content of the scene, we need to get rid of camera motion. Consequently, we rst estimate the dominant image motion between two successive images, which is assumed to be due to camera motion. Then, we cancel it by wrapping the successive images to the rst image of the shot through the combination of the successive estimated elementary dominant motions.

Dominant motion estimation

To model the transformation between two successive images, we consider a 2d a ne motion model. The velocity w r, at pixel r, related to the a ne motion model parameterized by is given by: w r = a 1 + a 2 x + a 3 y a 4 + a 5 x + a 6 y ! 1 with r = x; y and = a 1 a 2 a 3 a 4 a 5 a 6 . The computation is achieved with the gradient-based multi-resolution incremental estimation method described in OB95 . The following minimization problem is solved : where DFDr; = I t+1 s + w r , I t r and is Tukey's biweight function. The use of a robust estimator ensures the motion estimation not to be sensitive to secondary motions due to mobile objects in the scene. Criterion 2 is minimized by means of an iterative reweighted leastsquare technique embedded in a multiresolution framework and involving appropriate successive linearizations of the DFD expression.

Local motion-related measurements

In order to characterize the distribution of residual motion in the motion compensated image sequence, we aim at de ning some local motion-related measurements. Dense optic ow eld provides such local information. Nevertheless, as stressed previously, the relevance of the estimation cannot always beguaranteed in case of complex motion situations and the required computational load remains prohibitive in the context of video indexing involving large databases. As a consequence, we prefer considering a local motion-related measure directly computed from the spatio-temporal derivatives of the intensity function in the image.

By assuming intensity constancy along motion trajectories, the well-known image motion constraint relating the 2d apparent motion and the spatio-temporal derivatives of the intensity function can be expressed as follows : vr r I r + @ I r @ t = 0 where v is the 2D motion vector in the image, and I p the intensity function at point p in the wrapped image. Then, we can infer the normal velocity v n in the compensated sequence :

v n r = ,I t krI rk 4 with I t r = @ I r @ t is the temporal derivative of the intensity function I . I t r is approximated by a simple nite di erence. Although this expression is explicitly related to apparent motion, it can benull whatever the motion magnitude, if the motion direction is perpendicular to the spatial intensity gradient. Moreover, the normal velocity estimate is also very sensitive to noise attached to the computation of the intensity derivatives.

As for example pointed out in OB97 , the module of the spatial gradient krI rk can represent, to a certain extent, a pertinent measure of the reliability of the computed normal velocity. Furthermore, if the spatial intensity gradient is su ciently distributed in terms of direction in the vicinity of point r, a weighted average of v n in an appropriate neighborhood forms a relevant motion-related quantity. More precisely, w e consider the following expression :

v obs r = X s2Fr krI sk 2 j v n ssj max 2 ; P s2Fr krI sk 2 5
where Fr is a small window centered on r, 2 a predetermined constant related to the noise level in uniform areas. I t p is approximated by a simple nite di erence. This motion-related measurement forms a more reliable quantity than the normal ow, yet simply computed from the intensity function and its derivatives. This motion information was successfully exploited for the detection of mobile objects in compensated sequences OB97,FBG99 .

Obviously, the information relative to motion direction has been lost, which prevents from discriminating for instance two opposed translations with the same magnitude. However, this is not a real shortcoming, since we are interested in interpreting the type of dynamic situations observed in the considered video shot and not a speci c motion value.

Besides, the computation of cooccurrence measurements for the spatio-temporal distribution of motion-related information v obs r requires to quantize these continuous values. To cope with erroneous values, we apply a quantization on a prede ned interval. It indeed appears relevant to introduce a limit beyond which measures are no more regarded as usable. In practice, we will use N levels of quantizations in the interval 0; 4 . In the sequel, we will note the quantized range of variations of v obs r and x k these discretized motion-related measurements for the k th image of the processed video sequence.

Temporal Gibbsian modeling

In previous work FB99 , we exploit the measurement of temporal cooccurrences of these motion-related quantities to extract the global motion-based features. This led to encouraging results. On the other hand, a relationship between Markov random elds and cooccurrence distributions Gimelfarb96 , and more generally, with ltering-based feature extraction techniques ZWM98 , have been established. Therefore, we aim at developing a probabilistic modeling framework to characterize the spatio-temporal distributions of the local motion-related quantities attached to a shot.

Compared to the extraction of a set of numerical features for motion-based content characterization, this probabilistic modeling supplies a more accurate description of the uncertainty attached to motion information. Besides, it enables to deliver tools for video classi cation and retrieval embedded in a statistical framework, which should ease user interaction relevance feedback and the combination of di erent kinds of content description motion, color, texture or shape for instance.

Temporal Gibbs random elds

We consider a purely temporal modeling approach for two main reasons. First, analyzing the temporal evolution of the local motion information allows us to handle certain kinds of nonstationarity while being su cient t o c haracterize the motion classes of interest. Second, it makes feasible the computation of the conditional likelihood of a sequence of motion-related quantities w.r.t. a model. This property leads rst to a simple and straightforward model estimation see subsection 4.2, and, secondly, to de ne a well-funded statistical indexing and retrieval framework see Section 5.

More precisely, a sequence of motion quantities x k k=0;::;L is assumed to be the realization of a sequence of random elds X = X 0 ; : : : ; X K , where X is a rst-order Markov c hain of length K + 1 :

P V X = P V X 0 K Y k=1 P V X k jX k,1 6
V refers to the underlying interaction potentials to be de ned later. In addition, since we consider only purely temporal interaction, we assume that conditional probabilities are expressed by:

P V X k jX k,1 = Y r2R P V X k rjX k,1 r 7
where R is the image grid. The latter local conditional probabilities are equivalently expressed using a Gibbs formulation:

P V X k rjX k,1 r exp V X k r; X k,1 r 8
where V ; are the prior parameters attached to the model V . Besides, it leads to the de nition of the local normalization constant Z k r at position r in image k of the sequence:

Z k r = X !2 exp V !;X k,1 r 9
The likelihood P V X is then given by:

P V X = P V X 0 K Y k=1 Y r2R exp V X k r; X k,1 r Z k r 10
This temporal modeling can bede ned equivalently as a Markov random eld with temporal neighborhoodstructure GG84 . In addition, the following normalization constraint is imposed in order to guarantee the uniqueness of the potentials of the temporal Gibbs random eld: 8! 0 2 ; X !2 exp V a !;! 0 = 1 11 which implies : 8r; k 2 R 1; K ; Z k r = 1 . As a consequence, contrary to Markov random eld in the general case, the global likelihood function P V X can behere simply decomposed as a product of local temporal transitions:

P V X = P V X 0 K Y k=1 Y r2R exp V X k rjX k,1 r 12
For given P V X 0 and V , w e h a ve n o w a complete knowledge of P V law. This property will be exploited to derive a statistical framework for video indexing and retrieval in Section 5. Hereafter, the law P V X 0 is supposed to be uniform.

At last, similarly to Gimelfarb96,ZWM98 , the global likelihood function can beexpressed using an exponential formulation involving a dot product between cooccurrences measurements HX and the potentials of the model V :

P V X = P V X 0 exp h V HX i 13
where HX is the set of temporal cooccurrence measurements de ned by: 8!;! 0 2 2 ; H!;! 0 jX = k=K X k=1 X r2R ! , X k r ! 0 , X k,1 r 14 with is the Kronecker symbol, and the dot product between cooccurrences measurements HX and the potentials of the model V is given by:

V HX = X !;! 0 2 2 H!;! 0 jX V !;! 0 15 4.2 Maximum Likelihood Estimation
Given a realization x of X, w e aim at identifying the model V associated to X. To this end, we consider the Maximum Likelihood ML criterion. Thus, we aim at solving: b

V = arg max V LF V 16
where V stands for fV !;! 0 ; !;! 0 2 2 g and LF V = l n P V x.

In fact, this temporal modeling consists in a product of jRj independent Markov chains de ned by their transition matrix exp V ; :

P V X k rjX k,1 r exp V X k r; X k,1 r 17
As a consequence, the ML estimate is readily determined from the empirical estimation of the transition probability P V X k rjX k,1 r. Thus, potentials b V ; are given by: 8!;! 0 2 2 ; b V !;! 0 = l n fk;r : x k r = !;x k,1 r = ! 0 g fk;r : x k,1 r = ! 0 g 18 Equivalently, using cooccurrence measurements, we obtain:

8!;! 0 2 2 ; b V !;! 0 = l n 0 B B B @ H!;! 0 jx X 2 H ;! 0 jx 1 C C C A 19
where the cooccurrence matrix Hx is given by Eq.14.

Model complexity reduction

As far as video indexing is concerned, a crucial point is to supply informative representations of content description while remaining parsimonious. To this end, we perform a selection of relevant potentials after the ML estimation of the model.

In fact, as stressed by Eq.13, informative potentials are associated to high cooccurrence values. Therefore, we perform a ranking of the estimated potentials according to the associated cooccurrences, and, we consider an iterative procedure to select the proper model complexity.

Exploiting the determined ranking, potentials of b V are introduced one by one in a model Ṽ initially set to the constant model. We use the normalization constraint of Eq.11 to determine the values of potentials of Ṽ which h a ve not been introduced yet. In order to quantify the amount of information captured by Ṽ , w e e v aluate the likelihood ratio corresponding to the comparison of the reduced model Ṽ with the estimate b V and given by:

LR x Ṽ ; b V = P xj Ṽ =P xj b V 20
As soon as LR x Ṽ ; b

V exceeds a user-speci ed threshold LR accounting for the amount of information to be relevant, the procedure is stopped and the obtained reduced model Ṽ is stored as the model attached to the sequence x.

Statistical motion-based indexing and retrieval

In the context of video indexing, we focus on retrieval operation. Our goal is to retrieve i n a video database examples similar to a video query w.r.t. terms of motion content. To this end, we exploit the statistical modeling approach described above. In the same manner than in VL99 , the retrieval process is embedded in a B a yesian framework. Furthermore, since in case of large databases direct search reveals untractable, we propose a hierarchical motion-based structuring of the considered video database using a statistical similarity measure.

Statistical hierarchical indexing

We aim at determining an e cient indexing structure to make the retrieval task easier. Visual-content search trees have proven to bewell-suited to still image database management as shown in CBD00,MSP96,Schweitzer99 . It involves the construction of a binary tree whose nodes are attached to subsets of elements of the base. To a c hieve this hierarchical structuring, two main categories of approaches can be considered. Top-down techniques Schweitzer99 consist in successively splitting nodes of the tree, processing from the root to the leaves. As a consequence, an element misclassi ed in the rst steps of the procedure appears in an undesirable branch of the nal binary tree. Therefore, we prefer to use bottom-up techniques which seem to o er better performance in terms of classi cation accuracy, CBD00,MSP96 . In practice, we consider an ascendant hierarchical classi cation procedure, DGLS81 .

Given a similarity measure, this classi cation scheme successively forms from the leaves to the root pairs of elements minimizing the similarity measure. In addition, a threshold D max is introduced to prevent from merging nodes which are too far from each other. In our case, we want to take advantage of the statistical point of view introduced above to de ne an appropriate similarity measure. When considering two probabilistic distributions, the Kullback-Liebler KL divergence appears to provide relevant characterization of similarity of these two distributions BV98 . In practice, we will use a easily tractable approximation of the KL distance.

We rst assume that a temporal Gibbsian model V n has been estimated for each sequence n in the video database. The Kullback-Liebler KL divergence K L p; q is given by:

K L pkq = Z ln p q dp 21
It can be viewed as the expectation of the log-likelihood ratio ln p q w.r.t. the distribution p. This expectation can be approximated using a Monte-Carlo procedure. In our case, if we consider an element n of the database, the sequence of motion-related quantities x n represents a sample associated to the distribution modeled by V n . More precisely, a t e a c h k;r 2 0; K R , the transition from x n k,1 r to x n k r is a sample of the Markov c hain attached to model V n . As a consequence, when considering two elements of the database n 1 and n 2 , their associated models V n 1 and V n 2 , and the sequences of computed motion-related quantities x n 1 and x n 2 , the KL divergence K L n 1 kn 2 is approximated as the empirical average of the logarithm of the ratio of the likelihood of the transitions from x n k,1 r to x n k r computed respectively w.r.t. V n 1 and V n 2 :

K L n 1 kn 2 K X k=1 X r2R ln 0 @ P V n 1 , x n 1 k rjx k,1 r P V n 2
x n 1 k rjx n 1 k,1 r 1 A 22 This leads to approximate the KL divergence K L n 1 kn 2 by the logarithm of the ratios of the likelihoods of the sequence of motion-related quantities n 1 computed respectively for the Gibbsian models V n 1 and V n 2 : K L n 1 kn 2 ln P x n 1 jV n 1 P x n 1 jV n 2 23 It indeed quanti es the loss of information occurring when considering V n 2 instead of V n 1 to model the distribution attached to n 1 . Finally, in order to deal with a symmetric similarity measure, we consider the similarity measure Dn 1 ; n 2 between elements n 1 and n 2 given by:

Dn 1 ; n 2 = 1 2 K L n 1 kn 2 + K L n 2 kn 1 24
We need to de ne this similarity measure not only between elements of the video database, but also between two clusters C 1 and C 2 . D is then de ned by:

DC 1 ; C 2 =max n 1 ;n 2 2C 1 C 2 Dn 1 ; n 2 25
Exploiting this similarity measure, we a c hieve an ascendant hierarchical classi cation as follows. At each step, a pair is formed by merging the closest clusters according to D. If a cluster C is too far from all the others, i.e. min C 0 DC;C 0 D max , i t i s k ept alone to form a single cluster. D max can be easily set since D is directly related to log-likelihood ratios. As initialization, each element of the video database forms a leave of the binary tree. Besides, a model has to be attached to each created cluster. Since our temporal modeling is directly determined from temporal cooccurrence measurements, the model associated to the merging of two clusters is simply estimated using Eq.19. More precisely, when considering a set of sequence, the cooccurrence measurements de ned in Eq.14 are the sum of the cooccurrence measurements computed for each sequence of the considered group. Therefore, when merging two clusters C 1 and C 2 , w e rst compute the cooccurrence matrix HC 1 ; C 2 as the sum of the cooccurrence matrices HC 1 and HC 2 , and second, exploiting Eq.19, we estimate the potentials of the associated model.

Statistical retrieval

In case of direct search in the video database, retrieval operations can be achieved according to a MAP criterion VL99 . Given a video query q, w e w ant to determine the best match n : n = arg max n2N P njq = arg max n2N P qjnP n 26

Let us note that this criterion also supplies a ranking of the elements of the database according to P njq. In our case, we introduce no a priori: P n is uniform over the database elements and equal to a constant. Besides, to each element n of the base is attached a temporal Gibbsian model V n . We compute the sequence of motion-related measures x q for the video query q and the conditional likelihood P qjn is expressed as P V n x q see Eq.6. Then, we infer: n = arg max n P V n x q 27

In practice, a direct search reveals time-consuming for large databases. The resolution of criterion 27 is conducted through the hierarchy determined in subsection 5.1. We cannot ensure to nd the best match, but this provides a compromise between computational time and retrieval accuracy. More precisely, we proceed as follows. We explore the binary tree from the root to the leaves. At each step s, given a parent cluster C s , w e select the best child node C s+1 according to the MAP criterion:

C s+1 = arg max c2NC s P V c x q 28
where NC s is the set of children nodes of the cluster C s in the hierarchy. This process is run until the selected cluster contains the desired number of elements answers than desired or until a given similarity threshold precision is reached.

Results

We h a ve carried out experiments on a set of real image sequences. We h a ve paid a particular attention to choose a video set representative of various motion situations : temporal textures ames, crowds, sport videos basket, rugby..., rigid motion situations cars, train, ..., and low motion activity examples. Finally, we consider a database of 100 video sequences. Typically, each sequence is composed of about 10 images.

For each element of the database, we perform the estimation of the associated temporal Gibbsian model as described in Section 4. In practice, we consider 16 levels of quantization i.e. N = 1 6 .The proposed scheme for model complexity reduction allows us to keep only from 10 to 20 of the 256 ML estimates of the Gibbsian potentials.

At a second stage, we exploit this temporal modeling to determine an hierarchical representation of the database which expresses similarities in terms of motion content. In the subsequent, we present t wo t ypes of experiments. First, in order to provide a comprehensive visualization of the extracted binary tree, we h a ve also performed a classi cation on a smaller set of 20 sequences involving various types of dynamic content. Second, we display four results of retrieval operation with query by example. In both cases, we provide a comparison with the feature-based approach described in FB99 . Mainly, for a given sequence x, this technique extracts a set of features from the temporal cooccurrence matrix Hx and exploits the Euclidean norm in this featurespace as the similarity measure. To provide a more quantitative evaluation of the comparison, we will note D F this feature-based similarity measure. Hereafter, we will refer to the statistical technique presented in this paper as the model-based statistical technique, and to the approach described in FB99 as the feature-based geometrical technique.

Hierarchical motion-based classi cation:

The set of 20 sequences used to visualize an example of hierarchal classi cation is depicted in Fig. 1. It is composed as follows. It includes two static shots of anchors, anchor 1 and anchor 2 , from news program displaying a very weak motion activity. In addition, two other examples of low motion activity, hall and belle, ile, are also in the processed video set. Otherwise, four examples of rigid motion situations are introduced referring either to road tra c sequence, road 1 and road 2 , or to landing or take-o in airport sequence, airport 1 and airport 2 . At last, we add twelve sport video sequences involving football game, football 1 and football 2 , hockey game, hockey 1 , hockey 2 , hockey 3 and hockey 4 , basketball game, basketball 1 , basketball 2 and basketball 3 , and windsur ng, windsurfing 1 and windsurfing 2 .

For this video set, we perform the automatic unsupervised construction of the hierarchy both using the statistical technique presented in this paper and the feature-based approach described in FB99 . The obtained classi cation tree are displayed respectively in Fig. 2 for the model-based statistical technique and in Fig. 2 for the feature-based geometrical approach. In addition, we depict for the leaves of the tree the name of the associated element of the video set and for the other nodes the value of the maximum intra-cluster similarity measure.

The hierarchy obtained using the model-based statistical technique discriminates correctly the di erent kinds of dynamic contents. Tra c sequences, road 1 and road 2 , airport videos, airport 1 and airport 2 , and low motion activity situations, anchor 1 anchor 2 , hall and belle,ile, constitute a separate cluster in which relevant subclusters are formed associated to these four types of motion content. In addition, all sport video are properly grouped. In this group of sequences, subgroups have also been identi ed such as basketball sequences, basketball 1 , basketball 2 and basketball 3 , displaying very high motion activity, and hockey samples, hockey 1 , hockey 2 , hockey 3 and hockey 4 . The classi cation tree resulting from the feature-based geometrical scheme appears slightly less relevant. In fact, the two airport sequences, airport 1 and airport 2 , are not accurately classi ed.

Statistical motion-based retrieval: In Fig. 4 and Fig. 5, we display four examples of retrieval operation involving di erent t ypes of video query. The rst query is expressed as a news program consisting of a static shot on an anchor. A rigid motion situations is proposed as the second query. The third and fourth retrieval operations involve sport videos. A global view of the game eld is considered in the third query, whereas the fourth one is a close-up shot on a basket player tracked by the camera during the shot.

For these four examples of retrieval with query by example, we display the three best replies obtained, on on hand, using the model-based statistical framework, and on the other hand, the feature-based geometrical scheme. Besides, in both cases, we also give the values of the measure of the relevance of each reply. More precisely, for the rst framework, we give the values of the log-likelihood ln P V n x q corresponding to video query q and, in order to a posteriori evaluate the relevance of the replies, we have also estimated the model V q associated to the query and we report the distances D between V q and the di erent retrieved models V n . For the second approach, we give the values of the feature-based geometrical similarity measure D F .

For video query one and three, the results obtained with the two di erent techniques are equivalent end provide relevant answers with regards to motion content. In case of video query two and four, the video replies provided by the model-based statistical framework are visually more relevant. In both cases, the third reply proposed using the feature-based g e ometrical scheme would be not regarded as relevant b y the user.

As a consequence, from these di erent results which remain partial, it seems that the use of a statistical framework improves both the classi cation operation and the retrieval process.

Conclusion

We h a ve presented an original approach for dynamic content description in video sequences with a view to coping with motion-based indexing and retrieval with query by example. The proposed scheme exploits a temporal Gibbsian modeling of the cooccurrence distributions of local motion-related measurements computed along an image sequence from the spatio-temporal derivatives of the intensity function. To remain independent from camera work and to really handle scene motion, this analysis is performed in the reconstructed sequence compensated resulting from cancelling the dominant image motion assumed to be due to camera movement. This probabilistic modeling framework results rst in a statistical hierarchical motion-based structuring of the video database using an approximated version of the Kullback-Liebler distance, and, second, in a Bayesian retrieval scheme based on the MAP criterion and performed through the extracted hierarchy. We have obtained promising results both for the classi cation stage and retrieval operations.

In future work, we plan to evaluate our approach on a still larger video database. We could also exploit our statistical modeling approach to characterize dynamic contents attached to speci c entities of interest, such as moving objects extracted in an automatic FBG99 or semi-automatic GBD99 way. Considering the rst approach, we give for each reply n the value LF of the log-likelihood ln P V n x q corresponding to video query q. In addition, to a posteriori evaluate the relevance of the replies, we h a ve also estimated the model V q associated to the query and we report the distances D between V q and the di erent retrieved models V n . Besides, for the second technique, we give the value D F of the Euclidean distance in the feature space between the video query and the replies. Considering the rst approach, we give for each reply n the value LF of the log-likelihood ln P V n x q corresponding to video query q. In addition, to a posteriori evaluate the relevance of the replies, we h a ve also estimated the model V q associated to the query and we report the distances D between V q and the di erent retrieved models V n . Besides, for the second technique, we give the value D F of the Euclidean distance in the feature space between the video query and the replies.

Figure 1 :Figure 2 :

 12 Figure 1: Set of the 20 processed video shots used to visualize an example of motion-based hierarchal classi cation. For each video, we display the median image of the sequence.

Figure 3 :

 3 Figure 3: Feature-based geometrical classi cation: example of motion-based hierarchical classi cation for the set of 20 video sequences presented in Fig.1with D max = 1 0 . At each leave of the tree, we report the name of the video sequence. For the other nodes of the tree, we display the maximum intra-cluster distance evaluated using the geometrical distance D F in the feature space.

  Example of retrieval operations involving three replies using the model-based statistical and feature-based geometrical techniques.

In the sequel we will also use the term of sequence to designate an elementary shot.