Filip Křikava
email: filip.krikava@inria.fr

Philippe Collet
email: philippe.collet@unice.fr

Robert B France
email: france@cs.colostate.edu

SIGMA: Scala Internal Domain-Specific Languages for Model Manipulations

Model manipulation environments automate model operations such as model consistency checking and model transformation.

A number of external model manipulation Domain-Specific Languages (DSL) have been proposed, in particular for the Eclipse Modeling Framework (EMF). While their higher levels of abstraction result in gains in expressiveness over general-purpose languages, their limitations in versatility, performance, and tool support together with the need to learn new languages may significantly contribute to accidental complexities. In this paper, we present Sigma, a family of internal DSLs embedded in Scala for EMF model consistency checking, model-to-model and modelto-text transformations. It combines the benefits of external model manipulation DSLs with general-purpose programming taking full advantage of Scala versatility, performance and tool support. The DSLs are compared to the state-of-the-art Epsilon languages in non-trivial model manipulation tasks that resulted in 20% to 70% reduction in code size and significantly better performance.

Introduction

Model manipulation languages and tools provide support for automating model operations such as model consistency checking, and model-to-model (M2M) and model-to-text (M2T) transformations [START_REF] Sendall | Model transformation: The heart and soul of modeldriven software development[END_REF]. A number of different model manipulation technologies have been proposed, particularly within the Eclipse Modeling Framework (EMF) [START_REF] Steinberg | EMF: Eclipse Modeling Framework (2nd Edition)[END_REF]. The EMF models can be manipulated directly in Java, however, a General Purpose Programming Language (GPL) such as Java does not conveniently express model manipulation concepts and the loss of abstraction can give rise to accidental complexities [START_REF] Schmidt | Guest Editor's Introduction: Model-Driven Engineering[END_REF]. Therefore, a number of external Domain-Specific Languages (DSLs) for EMF model manipulation have been proposed, e.g., the OMG standards including OCL [START_REF]Object Management Group: OMG Object Constraint Language (OCL)[END_REF] for navigating and expressing constraints on models, QVT [START_REF]Object Management Group: MOF TM Query / View / Transformation (QVT)[END_REF] and MOFM2T [START_REF]Object Management Group: MOF Model to Text Transformation Language (MOFM2T)[END_REF] for model transformation; the Epsilon project [START_REF] Paige | The Design of a Conceptual Framework and Technical Infrastructure for Model Management Language Engineering[END_REF] with an extensive family of model manipulation DSLs; Kermeta [START_REF] Muller | Weaving executability into objectoriented meta-languages[END_REF], a single, but more general imperative language for all model manipulation tasks; and ATL [START_REF] Jouault | Transforming Models with ATL[END_REF], a M2M transformation language. External model manipulation DSLs provide language constructs that allow developers to manipulate models using higher-level abstractions. This should result in higher expressiveness and ease of use in comparison to GPLs [START_REF] Mernik | When and how to develop domain-specific languages[END_REF].

However, there are several impediments to such approaches. Even for a simple model manipulation task users have to learn one or more new languages and tools, which may require considerable effort [START_REF] Akehurst | SiTra: Simple Transformations in Java[END_REF]. Users might feel limited by the more specific, but less versatile language constructs, by the language execution performance or by the provided support tools [START_REF] George | Type-Safe Model Transformation Languages as Internal DSLs in Scala[END_REF]. In most cases the languages build on a subset of OCL concepts for model navigation and model consistency checking. Despite that, there are well known inconsistencies, interoperability and reusability issues among these languages [START_REF] Kolovos | The Epsilon Transformation Language[END_REF][START_REF] Kolovos | The Epsilon Object Language (EOL)[END_REF]. Finally, the large dependency stacks associated with these languages can make their integration into existing software projects rather challenging.

A notable exception is the Epsilon project, which alleviates some of these issues. Epsilon provides an extensive family of model management languages and tools such as Epsilon Validation Language (EVL) [START_REF] Kolovos | On the Evolution of OCL for Capturing Structural Constraints in Modelling Languages[END_REF], Epsilon Transformation Language (ETL) [START_REF] Kolovos | The Epsilon Transformation Language[END_REF], and Epsilon Generation Language (EGL) [START_REF] Rose | The Epsilon Generation Language[END_REF]. These task-specific languages are based on a common OCL-like expression language called EOL [START_REF] Kolovos | The Epsilon Object Language (EOL)[END_REF]. While this currently makes it one of the most complete language workbenches for model manipulations, we identify several shortcomings. EOL is a dynamically typed language, providing little compile time checking. Consequently, IDE features such as content assists, static checking or refactoring are rather basic in comparison to what is provided by the other approaches that use static typing. EOL lacks certain programming constructs that makes the code unnecessary lengthy in particular in the case of non-trivial model manipulations. Moreover, Epsilon DSLs are interpreted and their performance is an order of magnitude slower than the compiled languages, but they are also slower than the Eclipse implementation of the OMG stack [START_REF] Krikava | Domain-Specific Modeling Language for Self-Adaptive Software System Architectures[END_REF]. As a result, these shortcomings also give rise to some accidental complexities, albeit of a different nature than those associated with GPLs.

These issues are not easy to alleviate. The need to provide a lot of GPLlike constructs together with the necessity of some level of Java interoperability make the external DSLs large and complex. Evolving and maintaining complex DSLs is known to be hard since it not only requires domain knowledge and language development expertise, but also involves significant language and tool engineering effort [START_REF] Mernik | When and how to develop domain-specific languages[END_REF][START_REF] Chafi | Language virtualization for heterogeneous parallel computing[END_REF]. In this paper we propose an alternative internal DSL approach whereby model manipulation constructs are embedded into a GPL. The intent is to provide an approach that developers can use to implement many of the practical EMF model manipulations within a familiar environment with reduced learning overhead and improved usability.

An internal DSL leverages the constructs and tools of its host language. For this approach to be effective, the host GPL must be flexible enough to allow definition of domain-specific constructs. We thus use Scala [START_REF] Odersky | An Overview of the Scala Programming Language[END_REF], a statically typed object-oriented and functional programming language, to implement a family of internal DSLs, called Sigma [START_REF] Krikava | Manipulating Models Using Internal Domain-Specific Languages[END_REF], for model consistency checking and model transformations. In this paper, our contribution is to evaluate the resulting DSLs, comparing their expressiveness and features to corresponding Epsilon DSLs in several non-trivial model manipulation tasks. We observe this results in 20% to 70% reduction in code size and significantly better performance.

The remainder of the paper is organized as follows. In Section 2 we give a quick overview of the Sigma languages family. Section 3 develops the common infrastructure for model navigation and modification. This is used for model consistency checking described in Section 4, M2M transformations described in Section 5 and M2T transformations described in Section 6. In Section 7, we overview the current implementation and provide an evaluation of Sigma. Finally Section 8 discusses related work and Section 9 concludes the paper.

SIGMA Overview

Sigma is a family of internal DSLs for model manipulation that were created with the aim to alleviate some of the main limitations of the currently proposed approaches. It is thus not proposing new concepts in model manipulation languages, but instead providing the existing concepts with the following main requirements: (1) Epsilon-like features and expressiveness, (2) competitive performance, (3) usable tool support, (4) simple testability with existing unit frameworks, and ( 5) simple integration into existing EMF projects. We chose Epsilon since it represents the state-of-the-art model manipulation languages with proven features essential for usable model manipulation. Furthermore, it is also presented as an approach that addresses most of the shortcomings of the other external model manipulation DSLs (details in Kolovos et al. [START_REF] Kolovos | The Epsilon Transformation Language[END_REF][START_REF] Kolovos | On the Evolution of OCL for Capturing Structural Constraints in Modelling Languages[END_REF][START_REF] Kolovos | The Epsilon Object Language (EOL)[END_REF] and Rose et al. [START_REF] Rose | The Epsilon Generation Language[END_REF]).

Sigma DSLs are embedded in Scala [START_REF] Odersky | An Overview of the Scala Programming Language[END_REF], a statically typed production-ready GPL that supports both object-oriented and functional style of programming. It uses type inference to combine static type safety with a "look and feel" close to dynamically typed languages. It is interoperable with Java and it has been designed to host internal DSLs [START_REF] Chafi | Language virtualization for heterogeneous parallel computing[END_REF]. Furthermore, it is supported by the major integrated development environments.

A typical way of embedding a shallow DSL into Scala is by designing a library that allows one to write fragments of code with domain-specific syntax. These fragments are woven within Scala own syntax so that it appears different [START_REF] Dubochet | Embedded Domain-Specific Languages using Libraries and Dynamic Metaprogramming[END_REF]. Next to Scala flexible syntax (e.g. omitting semicolons and dots in method invocations, infix operator syntax for method calls, etc.), it has a number of features simplifying DSL embedding such as implicit type conversions allowing one to extend existing types with new methods, mixin-class composition (i.e. reusing a partial class definition in a new class) [START_REF] Odersky | An Overview of the Scala Programming Language[END_REF], and lifting static source information with implicit resolutions to customize error messages in terms of the domain-specific extensions using annotations [START_REF] Moors | Scala-virtualized[END_REF]. Furthermore, Scala supports compile-time meta-programming allowing for code self-optimization and to reduce boilerplate code generation.

Figure 1 depicts the general organization of the Sigma DSLs. The use of EMF models in Sigma is facilitated by a dedicated support layer that underneath uses the default EMF generated Java classes and the EMF API (implementation details are given in Section 7.1). This layer provides a convenient model In the following sections we detail the common infrastructure and the different task-specific DSLs. We deliberately skip some technical details about how certain DSL constructs are implemented. The complete examples with further documentation are available at the project web site [START_REF]The SIGMA Project[END_REF]. For illustration purposes, in the following sections we consider a simplified Object-Oriented (OO) model (cf. companion web page [4]).

Common Infrastructure

Essentially, any model manipulation technique is based on a set of basic operations for model navigation (e.g. projecting information from models) and modification (e.g. changing model properties or elements) [START_REF] Kolovos | The Epsilon Object Language (EOL)[END_REF]. In this section we show their realization in Sigma for EMF based models. Implementation details are discussed in Section 7.1.

Model Navigation. The model navigation support provides OCL-like expressions for convenient model querying. For example, retrieving names of all OO package elements stereotyped as singletons can be expressed using the following OCL query: In Sigma, the very same query can be expressed almost identically to OCL:

val singletons = pkg.ownedElements .filter(e => e.stereotypes exists (s => s.name == "singleton")).map(e => e.name)

In both versions the singletons type is inferred from the expression.

While navigating models, one often need to filter the types of the objects to be kept during navigation. For example, selecting the operations of a package abstract classes corresponds to the following OCL expression: This is rather verbose with the recurring pattern of oclIsKindOf/oclAsType, which makes longer queries hard to read. Scala, on the other hand, provides support for pattern matching that can be used in combination with partial functions to obtain the following Sigma code4 :

pkg.ownedElements collect { case c: Class if c.abstract_ => c.operations }
In addition Sigma can also prevent null pointer exceptions when navigating over potentially unset references and attributes (0..1 multiplicity). It wraps them into Scala Option type, a container explicitly representing an optional value, which consequently forces one to always check for the presence of the value.

Model Modification. The model modification support provides facilities for seamless creation, updates and removal of model elements. By design, the OCL does not have model modification capabilities, but in Epsilon for example, an OO singleton class can be created using the code in Listing 1.1. Using Sigma the same model instance is created in Listing 1.2. These methods provide a convenient way to author complete EMF models directly in Scala. Additionally, Sigma provides support for delayed initialization in the cases an element initialization should only happen after its containment, and for lazy resolution of contained references5 .

Model Consistency Checking

Model consistency checking provides facilities to capture structural constraints as state invariants and to check model instances against these constraints. In OCL or EVL, a structural constraint is a boolean query that determines whether a model element or a relation between model elements satisfies certain restrictions.

For example, in the OO model, an invariant may represent a restriction that within one package, there cannot be two classes having the same name. In Sigma, such an invariant can be expressed as: Invariants are represented as regular Scala methods (line 4). They are organized into a validation context class (line 1) that specifies a context type (line 2), i.e., the type of instances the invariants can be applied to. As in OCL, self represents the current instance that is being checked. The OOPackageSupport trait (cf. Section 7.1) mixes-in the Sigma EMF to Scala support for model navigation and modification (line 1). By organizing invariants as methods in classes we can simply reuse them through inheritance. Furthermore, it allows one to easily test invariants using any of the Java unit testing frameworks.

Listing 1.3 shows an extended OO class validation with additional features. A validation context class can narrow its applicability by providing a context guard (line 4). Invariant violation can distinguish different severity levels such as errors and warnings (line 10). In order to prevent meaningless evaluation of constraints whose dependencies are not satisfied, invariants can also have guards (line 7). Finally, a user can be provided with a feedback including a meaningful message (line 10), as well as means to repair the inconsistency with change suggestions over the affected model elements (line 11). [START_REF] Czarnecki | Feature-based survey of model transformation approaches[END_REF] is already supported thanks to the common infrastructure layer described in Section 3. On the other hand, the lower level of abstraction of the imperative transformation style leaves users to manually address issues such as orchestrating the transformation execution and resolving target elements against their source counterparts [START_REF] Kolovos | The Epsilon Transformation Language[END_REF]. Therefore, inspired by ETL and ATL, we provide a dedicated internal DSL that combines the imperative features with declarative rule-based execution scheme into a hybrid M2M transformation language.

Transformation rules constitute the abstract syntax of the M2M transformation DSL. Similarly to ETL or ATL, a rule defines a source and a target element to which it transforms the source. It may optionally define additional targets, but there is always one primary source to the target relation. A rule can also be declared as lazy or abstract. Each non-lazy and non-abstract rule is executed for all the source elements it is applicable. Lazy rules have to be called explicitly. When a rule is executed, the transformation engine initially creates all the explicitly defined target elements and passes them to the rule that populates their content using arbitrary Scala code. Similarly to consistency checking constraints, transformation rules can optionally limit their applicability by defining a guard. Listings 1.4 illustrates the internal DSL using the traditional example of OO model to database schema transformation 6 . A M2M transformation is a Scala class that extends the M2M base class with the generated package support traits for model navigation and modification (line 1). Transformation rules are represented by methods. For example, the ruleClass2Table denotes a rule that, for a given class, produces a table and a column (line 3). Additional target elements can be constructed within the rule body, but in such a case a developer is responsible for their proper containment.

During the M2M transformation, there is often the need to relate the target elements that have been already (or can be) transformed from source elements. For this purpose, Sigma provides a set of operations. An example is shown on the line 6 where sTarget[Column] transforms class properties into columns. It does that by looking up a rule with property-to-column mapping, which in this case is the ruleProperty2Column rule. This operation can be applied both to a single instance as well as to a collection of model elements. Similarly, Sigma includes support for resolving source elements from their corresponding targets.

Model-to-Text Transformations

M2T transformations translate models into text by mapping source model elements into corresponding textual fragments. We focus on template-based approach whereby string patterns are extended with executable logic for code selection and iterative expansion [START_REF] Czarnecki | Feature-based survey of model transformation approaches[END_REF]. This approach is used by all the major M2T transformation languages including EGL and MOFM2T. In model-driven software development, the aim is to synthesize a running system implementation and therefore our primary focus is on generating source code artifacts.

Unlike EGL and Acceleo, our internal DSL for M2T transformation is using the code-explicit form, i.e., it is the output text instead of the transformation code that is escaped. This is one of the syntax limitations that cannot be easily overcome. On the other hand, from our experience, in non-trivial code generations, the quantity of text producing logic usually outweighs the text being produced. For the parts where there is more text than logic we rely on Scala multi-line string literals and string interpolations allowing one to embed variable references and expressions directly into strings. Listing 1.5 shows an example of OO class to Java transformation 7 . Following the same pattern, a M2T transformation is a Scala class extending from the M2T base class (line 1). Line 2 defines the type of model element, i.e., the transformation source. A M2T transformation consists in a set of templates that are represented as methods (lines 4 and 11). The execute method is the entry point, which will be invoked when the transformation is executed. Usually, from there, a transformation is split and logically organized into smaller templates in order to increase modularity and readability.

The most common operation in a M2T transformation is a text output. A convenient way to output text in our DSL is through a unary ! (bang) operator that is provided on strings (e.g. line 4). The prefix s right before the string double quote denotes an interpolated string, which can include Scala expressions in a type-safe way.

An important aspect of any M2T transformation language is the template readability, e.g., layout and indentation. The internal DSL maintains it through dedicated support for decorators, smart whitespace handling and relaxed newlines. Decorators are nestable string operations that reformat a given block. For example, on line 4 we use curlyIndent decorator, that wraps its body into a pair of curly brackets and indent each line. Smart whitespace handler removes extra whitespace from multi-line strings that are there only for the template readability. For example the whitespaces prefixing the text on lines 14 and 15 will be discarded. Relaxed newlines loosen the necessity to output new line characters by doing it automatically after every text output. Both smart whitespace and newlines handlers are enabled by default, but can be turned off.

Finally, the DSL also allows one to fork new text sections. This makes it possible to output text into different locations at the same time. All sections are appropriately merged in the final text at the end of the transformation. This is useful for example for handling imports while generating Java code, as they can be resolved one-by-one during the model traversal.

Evaluation

Our aim is to propose an approach that improves the overall usability of model manipulations through DSLs. However, defining usability of a DSLs and associated tool support tend to be subjective, since it largely depends on the preferences and background of its users [START_REF] Sendall | Model transformation: The heart and soul of modeldriven software development[END_REF] and its improvement cannot be measured directly. Therefore, we structure the evaluation as follows. First we give details about the implementation and current applications. Next, we compare Sigma DSLs to their corresponding Epsilon counterparts with regard to implementation effort measured in terms of code size, performance and features. Finally, we discuss the limitations of the approach and threats to validity.

Implementation

Sigma is implemented as a Scala library which is available from the project website [START_REF]The SIGMA Project[END_REF]. Its task-specific languages are all relying on a common infrastructure.

Common infrastructure. The common infrastructure aligns EMF generated Java classes with Scala to enable use of model navigation and modification notation similar to OCL and EOL. This involves (1) model navigation without "get noise" (e.g. getSuperPackage.getName becomes superPackage.name), and (2) promoting EMF collections to corresponding Scala collections to benefit from convenient first-order logic operations (e.g., map, filter, collect) similar to OCL. Both issues are addressed by generating extension traits8 that make EMF model elements interoperable with Scala. These traits implicitly extend all model classes with property accessors without the get prefix and convert EMF collections into the corresponding Scala ones. The conversion only happens at the interface level leaving the underlying data storage unchanged. In the same way, existing Scala types are extended with missing OCL operations (e.g. implies). These traits are either generated by provided Sigma M2T transformation executed explicitly by a user or implicitly using the experimental Scala macro annotations [START_REF] Burmako | Scala macros: let our powers combine![END_REF].

Task-specific languages. The model consistency checking and M2M transformation have similar abstract syntax (i.e. constraints and rules) to EVL and ETL respectively, and their execution semantics is the same as defined in Epsilon. The M2T transformation is a purely imperative DSL and as such it does not contain any particular execution engine. All DSLs are implemented following the same pattern, i.e. organizing task-specific concerns into Scala classes that extend from a task-specific base class. The main constructs such as invariants, rules and templates are expressed as methods in order to foster reuse and extensibility.

Applications

Sigma has been used in the SALTY project [7] to develop a modeling environment for developing self-adaptive software systems [START_REF] Krikava | ACTRESS: Domain-Specific Modeling of Self-Adaptive Software Architectures[END_REF]. The main motivations were the shortcomings of OCL used for the initial implementation [START_REF] Krikava | On the Use of an Internal DSL for Enriching EMF Models[END_REF]. Sigma has been also adopted by the Yourcast project [10] for M2T transformations replacing Velocity [START_REF]Apache Velocity[END_REF] and plain Java templates, gaining 20% reduction in code size, mainly thanks to more expressive model navigation and more compact text outputting constructs.

Code Comparison

In order to evaluate the overall usability of our approach we re-implemented larger Epsilon model manipulation tasks for each of the Sigma DSLs. As suggested by the Epsilon community 9 , we chose Eugenia [START_REF] Eugenia | [END_REF] GMF Ecore constraints for model consistency checking, Unicaneer2sql [START_REF]The Unicaneer2sql Project[END_REF] (an ER to relational model transformation) for M2M transformation, and Egldoc [START_REF]Epsilon Egldoc[END_REF] (an Epsilon tool for generating Ecore documentation in HTML including Graphviz diagram) for M2T transformation. The Eugenia and Egldoc comes directly from Epsilon, which should guarantee certain quality of the source code. The complete implementation is available from the paper companion web page [4].

Table 1 summarizes the implementation effort in terms of Source Lines of Code (SLOC) for the three scenarios, for both Epsilon and Sigma. Interpreting SLOC metrics is always problematic. The issue of what is the right level of "verbosity" in a language is complex and should not be reduced naively to just counting SLOC. Our assumption, however, is that usability is not achieved by having fewer lines of code, but instead, by having more expressive and concise code, which is beneficial to writers as well as to readers. On the other hand, code bloat resulting from code duplication and from lack of constructs that enable the building of more concise but expressive statements, is not desirable. Most of the code reduction comes from the fact that Scala contains more general programming constructs than EOL. In particular, pattern matching and inheritance helped to reduce many of the code duplications. In the case of model consistency checking, the code reduction is the least significant one since Sigma contains the same constraints constructs as EVL and the invariant expressions were mostly simple first-order logic queries. The EVL code is therefore almost identical to the Sigma one and the only reduction was in the EOL helper methods. They can be expressed more concisely in Scala primarily thanks to pattern matching.

The case of M2M transformation led to a similar situation. Sigma supports the same M2M transformation rules and thus the ETL code is very close to the Sigma one. However, the M2M transformation involved a lot of imperative EOL code which could be reduced by using more expressive Scala statements. Furthermore, about 15% of the transformation generates text for which we could use Sigma M2T constructs reducing the code even further.

The M2T transformation scenario involved generating both HTML code and Graphviz code. Generally, code-explicit forms of M2T transformation are not particularly suitable for generating HTML code since in this case the quantity of text outweighs the text producing logic. However, despite this, the code has been reduced by 70%. The main reason is that, by the use of inheritance, a lot of code duplication present in the EGL templates was avoided.

We do not provide a comparison of the coding time. First we do not have the measures of the Epsilon versions. Second it is always easier to port an existing code to a new language than to write it from scratch. However, we expect some strong points of the Sigma DSLs to reduce coding time. Static type safety prevents runtime typing errors. The highly usable tool support provided by the Scala IDE [START_REF]Scala IDE[END_REF] with a code completion and a debugger and the ability to easily run and test the transformations should facilitate development.

Performance Comparison

The performance of Sigma is determined by the host language one and the overhead of the Sigma API. Sigma compiles directly into Java byte-code and thus it significantly outperforms Epsilon and other interpreted DSLs. For example, generating QVT meta-model (159 classifiers) documentation using Egldoc takes on average 8 times more time than using the Sigma version.

However one of the concerns is related to the extensive use of implicit type conversions and other Scala constructs that might have negative performance impact. Therefore, as a part of the performance evaluation, we have implemented the same M2T transformation in Sigma and the related M2T languages10 . In addition, we have also implemented it in pure Java and Scala with no additional libraries. The Java version is used as a performance baseline. The Scala version is used to measure the overhead of Scala in comparison to Java and the performance penalty caused by Sigma. The implementation in the other languages aims at evaluating our requirement of competitive performance. The M2T transformation has been chosen because (1) it uses many Scala constructs that might cause performance issues (e.g., implicit conversions, string interpolation), (2) M2T transformation is one of the most often used model manipulation tasks [START_REF] Kelly | Domain-Specific Modeling: Enabling Full Code Generation[END_REF], and (3) the implementation in the other languages was straightforward, limiting the possibility of misusing some features. As a concrete transformation we chose our simple OO model to Java transformation, since nearly all the listed languages provide an example that is based on it. Table 2 shows the median of 20 consecutive runs for two different model sizes, (A) corresponds to 250 classes with 50 methods and properties each, while (B) is 500 classes with 100 methods and properties each.

Scenario Java Sigma EGL Acceleo Xtend Kermeta Scala A 1.0 1.0 18.6 11.9 0.9 1.0 0.9 B 1.0 1.8 48.1 16.4 1.0 1.0 1.0 As expected, the performance of Sigma together with the other compiled languages is close to Java, while the interpreted ones are an order of magnitude higher (also their memory footprint is double). The decrease in Sigma performance in the case of the larger model is caused by the whitespace handling decorator. Every appended string is checked for whitespaces to be removed, and its complexity increases with the indent level. Without this decorator, the performance is again close to Java (A: 0.9, B: 1.0).

Evaluation of Requirements

In the previous section we evaluated the competitive performance requirement. The following is the evaluation of the other requirements identified in Section 2:

(1) Epsilon-like features and expressiveness. In Table 3, we evaluate the requirement stating that our DSL should contain similar features as in Epsilon languages, i.e. EOL, EVL, ETL and EGL. The listed Epsilon features are taken from the Epsilon website [START_REF]The Epsilon Project Documentation[END_REF]. (2) Usable tool support. One of the advantages of an internal DSL is that it can directly reuse the tool support provided for the host language. As mentioned above, the recent versions of the Scala IDE [START_REF]Scala IDE[END_REF] provide solid tools facilitating Scala development. Moreover, additional tools operating on the JVM class level such as profilers can be directly used. (3) Simple testability with existing unit frameworks. The method-based styles of all the three languages allows to cherry-pick the fragments of model manipulation to be tested by any Java-based unit testing framework, which is especially useful for larger model transformations. (4) Simple integration into existing EMF projects. Executing a model manipulation task in Sigma is no different from executing a regular JVM-based application and therefore it can be included in many building tools.

With the basic set of Scala skills necessary to use Sigma, we consider that the DSLs are rather small and thus less learning effort is likely to be required in comparison to language such as OCL or EOL. Finally, being an internal DSL is notably reflected in the code size of the implementation. Sigma is currently implemented in 3500 lines of Scala code, which is an order of magnitude less than just EOL, which is an order of magnitude less than Eclipse OCL.

Limitations

Apart from the syntax limitations, an internal DSL is in general a leaky abstraction [START_REF] Siek | General purpose languages should be metalanguages[END_REF]. For example an implementation of guards and structural constraints can contain arbitrary code and by default. There is no simple way to make sure they are side-effect free without employing an external checker such as IGJ [START_REF] Zibin | Object and reference immutability using java generics[END_REF], which brings additional overhead. Traditionally, the support for domain-specific analysis, error checking and optimization has been difficult to realize in internal DSLs. However, Scala offers some more advanced methods for DSL embedding, using language virtualization and lightweight modular staging [START_REF] Rompf | Lightweight modular staging: a pragmatic approach to runtime code generation and compiled DSLs[END_REF][START_REF] Chafi | Language virtualization for heterogeneous parallel computing[END_REF].

Depending on the target audience, the use of Scala can be seen as a drawback rather than a merit. It is a new language that has not yet reached the popularity of some of the mainstream programming languages. It might be hard to justify learning a language such as Scala solely for the purpose of model manipulation. Finally, there is a small compile-time overhead of generating the common infrastructure.

Threats to Validity

There are few potential threats to validity of the evaluation presented in Sections 7.3 and 7.4. First, the implemented model manipulation tasks represent only a small subset of possible scenarios. To the best of our knowledge, we do not know about other publicly available larger model manipulations implemented in Epsilon. In some parts, the Epsilon code itself could be improved which, would result in more concise solutions, nevertheless, we believe that this would not make a major difference. As for the performance evaluation, it is a form micro benchmark and as such it should be considered with all the validity threats micro benchmarking brings. We have implemented only a small model manipulation task, yet, we already see the trends of the different approaches whose performance will likely remain in the same order of magnitude even for other model manipulations.

Cuadrado et al. [START_REF] Cuadrado | RubyTL: A Practical, Extensible Transformation Language[END_REF] developed RubyTL, a Ruby internal DSL for ATL-like M2M transformations. Later, they used it for a comparison on the effort of building an internal DSL and an external one. They concluded that the success of an internal DSL highly depends on the selection of the host language, its support for DSL embedding, execution performance, tool support, and popularity [START_REF] Sánchez Cuadrado | Comparison between internal and external DSLs via RubyTL and Gra2MoL[END_REF]. The main difference with Sigma is that using a dynamic language prevents any compile type checking. Also RubyTL relies on its own EMF model parser facilities and is not directly interchangeable with the mainstream EMF.

George et al. [START_REF] George | Type-Safe Model Transformation Languages as Internal DSLs in Scala[END_REF] used Scala to build a M2M transformation DSL for the EMF platform that resembles ATL. Since we use the same host language, their DSL is fully interoperable with ours, e.g. the common infrastructure (Section 3) can be directly used in the transformation rules. However their internal DSL is not completely type safe and they represent transformation rules directly as anonymous classes, which limits their modularity and reusability. Wider [START_REF] Wider | Towards combinators for bidirectional model transformations in scala[END_REF] presents an interesting approach to bidirectional model transformations by embedding lenses (a combinator-based approach to bidirectional term-transformations) into Scala and showed how they can be used in an MDE context. Akehurst et al. [START_REF] Akehurst | SiTra: Simple Transformations in Java[END_REF] developed a Java library for simple imperative M2M transformations. Being based on Java gives it performance and tool support advantages, as well as a wider audience. On the other hand, there is no particular support for improving the expressiveness of model navigation and modification, resulting in rather verbose and complicated code.

Conclusion

In this paper we have presented an alternative internal DSL approach for model manipulation whereby the supporting constructs are embedded into a GPL. We used Scala as the host language to design and fully implement Sigma, a family of type-safe internal DSLs for EMF model consistency checking, M2M and M2T transformations. We have shown that the resulting DSLs have similar expressiveness and features found in external model manipulation DSLs, while providing competitive performance, compact implementation, and the ability to take advantage of the advanced Scala tool support.

Non-trivial model manipulation tasks often involve a lot of general purpose programming. By using a GPL such as Scala with rich general purpose programming constructs, we were able to significantly reduce the code size of the model manipulation tasks implemented in our evaluation process, without jeopardizing their readability.

Current work in progress around Sigma consists in carrying out more evaluations to further assess the usability of the proposed DSLs. Sigma has notably participated in the 2014 edition of the Transformation Tools contest [START_REF] Horn | 7th Transformation Tools Contest[END_REF]. For the future we first want to apply the Scala advanced DSL embedding techniques to address identified limitations such as the problem of leaky abstraction. We also plan to tackle DSL composition issues by exploring appropriate ways to couple Sigma with other DSLs in different case studies.

Fig. 1 .

 1 Fig. 1. Sigma EMF to Scala Support

  let singletons = pkg.ownedElements ->select(e | e.stereotypes->exists(s | s.name = 'singleton'))->collect(e | e.name)

  pkg.ownedElements ->select(e | e.oclIsKindOf(Class) and e.oclAsType(Class).abstract = true) ->collect(e.oclAsType(Class).operations)

  var cls = new Class; cls.name = "MyClass"; var singleton = new Stereotype; singleton.name = "singleton"; cls.stereotypes.add(singleton); var op = new Operation; op.name = "getInstance"; op.returnType = cls; cls.operations.add(author); Listing 1.1. EOL val cls = Class(name = "MyClass") val singleton = Stereotype(name = "singleton") cls.stereotypes += singleton val op = Operation(name = "getInstance", returnType = cls) cls.features += op Listing 1.2. Sigma

class

  ClassInvs extends ValidationContext with OOPackageSupport { type Self = Class // context type def invUniqueNamesWithinPackage = self.pkg.ownedElements forall (e => e != self implies e.name != self.name) }

class

  ClassInvs extends ValidationContext with OOPackageSupport { type Self = Class // context type override def guard = self.annotations exists (_.name == "ignore") // context guard def invUniqueNamesWithinPackage = guardedBy { self satisfies invHasValidName // invariant guard } check { // invariant body self.pkg.ownedElements find (e => e != self && e.name == self.name) match { case Some(c) => Error(s"Class $c has the name") .quickFix("Rename '${self.name}' to '${self.name}_2'") { self.name += "_2" } case None => Passed } } def invHasValidName = // ... } Listing 1.3. Example of model consistency checking 5 Model-to-Model Transformations M2M transformations provide necessary support for translating models into other models, essentially by mapping source model elements into corresponding target model elements. An imperative style of M2M transformation

  class OO2DB extends M2M with OOPackageSupport with DBPackageSupport { def ruleClass2Table(cls: Class, tab: Table, pk: Column) { // standard Scala tab.name = cls.name tab.columns += pk pk.name = "Id" pk.type_ = "Int" // SIGMA specific: target elements resolution tab.columns ++= cls.properties.sTarget[Column] } def ruleProperty2Column(prop: Property, col: Column) = guardedBy { !prop.multi // prevent transformation of multi-valued properties } transform { col.name = prop.name.toUpperCase col.type_ = prop.type_.name } } Listing 1.4. Example of M2M transformation

classListing 1 . 5 .

 15 OO2Java extends M2T with OOPackageSupport { type M2TSource = Class // input type for transformation def execute = !s"public class ${root.name}" curlyIndent { for (o <-root.operations) { genOperation(o) // call to another template !endl // extra new line } } def genOperation(o: Operation) = !s"public ${o.retType.name} ${o.name}()" curlyIndent { !s""" // TODO: should be implemented throw new UnsupportedOperationException("${o.name}"); Example of M2T transformation

Table 1 .

 1 SLOC comparison

	Scenario	Epsilon Sigma difference
	Model consistency checking 364 EVL 286	22%
	M2M transformation	733 ETL 389	47%
	M2T transformation	1400 EGL 412	70%

Table 2 .

 2 Performance of different M2T languages normalized to Java version

Table 3 .

 3 Supported Epsilon features.

(+) supported, (-) unsupported, (0) partially supported

The _ suffix to abstract is automatically added by the Sigma EMF support since it is a Scala keyword.

Technical details at http://bit.ly/18javEY

While it is a worn example, it enables one to easily compare to similar examples provided by ETL and ATL cf. companion web page [4].

Similar examples are provided for both EGL and Acceleo cf. companion web page [4].

Technical details at http://bit.ly/18javEY

Kermeta version was put together by Didier Vojtisek, a Kermeta committer. All the source code is available from the companion web page [4].

Acknowledgments. This work is partially supported by the Datalyse project www.datalyse.fr.


Pierre Formont

Miguel Angel Veganzones

Joana Frontera-Pons

Frédéric Pascal

Jean-Philippe Ovarlez

Jocelyn Chanussot

J Frintera-Pons

J.-P Ovarlez

CFAR Hierarchical Clustering of Polarimetric SAR Data

come   L'archive ouverte pluridisciplinaire

INTRODUCTION

In [START_REF] Formont | Statistical classification for heterogeneous polarimetric sar images[END_REF], authors propose a general approach for high-resolution polarimetric SAR (POLSAR) data classification in heterogeneous clutter, based on a statistical test of equality of covariance matrices. The proposed method generalizes several distance measures used in standard classification methods and it can be applied to both homogeneous and heterogeneous clutter models without any a priori physical interpretation to the classification process.

The heterogeneous clutter was described by a Spherically Invariant Random Vector (SIRV) model. The Fixed Point (FP) estimate [START_REF] Pascal | Covariance structure maximum-likelihood estimates in compound gaussian noise: Existence and algorithm analysis[END_REF] of the covariance matrix was used to describe the POLSAR data set. FP estimate is independent of the texture pdf and is an Asymptotically Maximum Likelihood (AML) estimator for many stochastic processes obeying the SIRV model. Moreover, it is asymptotically Wishart distributed. Such an approach provides a threshold over which This work was supported by the Delegation Generale de l'Armement (DGA) under contract PDE12C2009. pixels are rejected from the image, meaning they are not sufficiently "close" from any existing class.

The statistical test distribution can be approximated by a χ 2 distribution, giving raise to a Constant False Alarm Ratio (CFAR) property. We take advantage of this CFAR property to modify the Hierarchical clustering algorithm. The CFAR property allows us to decide the optimal number of clusters in the Hierarchical clustering by setting a False Alarm threshold that forces the algorithm to stop at some level of the hierarchy.

The proposed algorithm is tested on a high-resolution polarimetric data set acquired by the ONERA RAMSES system. Section 2 reviews the statistical test of equality of covariance matrices. Section 3 introduces the CFAR hierarchical clustering algorithm. Section 4 describes the experimental design and results. Finally, in section 5 we give some conclusions.

TEST OF EQUALITY OF COVARIANCE

MATRICES

This section is devoted to the study of statistical test for equality of covariance matrices and its application to POLSAR data classification. A statistical approach to the problem of POL-SAR data classification has many advantages:

• It can be applied to both homogeneous and heterogeneous clutter models.

• There is no a priori physical interpretation to the classification process.

• It is a very general approach which particularly contain previous methods.

First, a Gaussian context will be assumed and later, an approach under SIRV assumption will be derived. Let X 1 and X 2 be independent random vectors, such that X 1 ∼ L(0, T 1 ) and X 2 ∼ L(0, T 2 ) where L stands for any distribution with the two first moments existing. The goal is to decide if their covariance matrices T 1 and T 2 are equal.

The resulting binary hypothesis test can be written as:

H 0 : T 1 = T 2 H 1 : T 1 = T 2 et x 1 (resp. x 2 ) be a sample of N 1 (resp. N 2 ) indepen-
dent and identically distributed m-dimensional random vectors, and N = N 1 + N 2 . Under Gaussian assumption, the test statistic can easily be derived as the following equation [START_REF] Formont | Statistical classification for heterogeneous polarimetric sar images[END_REF]:

λ = T 1 N 1 2 T 2 N 2 2 T N 2 (1)
Notice the exponents are the size of the samples. Bartlett [START_REF] Bartlett | Properties of sufficiency and statistical tests[END_REF] proposed alternative exponents for the univariate case, replacing the samples size by the degree of freedom of the estima-tors T i . Eq. (1) then becomes:

t = | T 1 | ν 1 2 | T 2 | ν 2 2 | T t | ν t 2 (2)
where ν i = N i -1 are the degrees of freedom of T i and ν t = N -2, the degree of freedom of T.

Box [START_REF] Box | A general distribution theory for a class of likelihood criteria[END_REF][START_REF] Box | Problems in the analysis of growth and linear curves[END_REF] proposed a χ 2 approximation for the distribution of t. The statistic he proposed is:

u = -2(1 -c 1 ) ln(t) ∼ χ 2 ( 1 2 (k -1)m(m + 1)) (3)
where c 1 depends on some parameters of the samples and χ 2 (a) denotes the χ 2 distribution with a degrees of freedom.

The critical region of the test is

u > χ 2 ( 1 2 (k -1)m(m + 1), P FA ) (4)
where P FA is the type I error, or false-alarm rate. In our case, we set the type I error (accepting the null hypothesis when it is not true i.e. rejecting the equality of the matrices of the two populations when they are actually equal) to be very low.

The same procedure can be applied in the SIRV case, considering that it was demonstrated by Pascal et al. in [START_REF] Pascal | Performance analysis of covariance matrix estimates in impulsive noise[END_REF] that the FP estimate asymptotically has a Wishart distribution behaviour with m m + 1 N degrees of freedom. This is a very important property of the FP estimate since all results obtained with the SCM remain valid for the FP estimate due to an asymptotical justification. The SCM estimators T 1 and T 2 can be replaced by the FP estimates M 1 and M 2 of the same N-samples x 1 and x 2 with the correct degrees of freedom.

CFAR HIERARCHICAL CLUSTERING

Hierarchical clustering [START_REF] Ward | Hierarchical grouping to optimize an objective function[END_REF] returns a hierarchy of clusters built by merging smaller components into bigger clusters (agglomerative clustering) or by splitting the whole image into smaller regions (divisive clustering). In order to do that a similarity function between any two components is necessary, i.e. the Euclidean distance, to compare each pair of components. Then, a linkage function indicates which of any possible pair of components is merged to (or split from) a bigger cluster, i.e. the pair with minimum similarity. Anyway, the result is a hierarchy of clusters that can be represented as a dendrogram. Two components merging (obtained by splitting from) any cluster (node) in the dendrogram are linked by a similarity value. A common criterion to stop merging (splitting) is to a priori set the number k of clusters one is looking for.

In our case, we define the pairwise similarity function between any two components as the results of the test of equality of covariance matrices (3), u. The CFAR property of (4)

allows us to define a stopping criterion that automatically detects the number of clusters for a given False Alarm probability, P FA . We simply stop merging (dividing) once the similarity function, u, goes over (under) the threshold value, u FA , corresponding to equation ( 4) for a given P FA .

EXPERIMENTS AND RESULTS

Dataset

The POLSAR dataset was acquired by the ONERA RAMSES system in Brtigny, France. The acquisition was made in Xband, with a spatial resolution of 1.32m in range and 1.38m in azimuth. The resulting image is 501 × 501 pixels. Fig. 2 shows the power representation image of the dataset.

Hierachical clustering results

In order to build the hierarchical clustering of the POLSAR dataset, we first downsampling the image by taking one of each three pixels, in order to reduce the computational burden.

We estimated the covariance matrices for each pixel using a 7×7 window by the sample covariance matrix (SCM) and the Fixed Point (FP) estimators. Fig. 1 shows the distribution of the pairwise distances between the nodes of the hierarchical clustering, given by four different linkage functions: Minimum, Maximum, Unweighted Pair Group Method with Arithmetic Mean (UPGMA) and Weighted PGMA (WPGMA) 1 .

The linkage distances distribution for the SCM fits better the six degrees of freedom χ 2 distribution than the ones obtained using the FP estimator. This was expected as the χ 2 distribution assumes Gaussianity. However, the FP estimation is closed enough to assume the χ 2 distribution as the basis for the CFAR property. The minimum linkage function fits poorly in both cases.

Fig. 3 shows the hierarchical clustering maps of the POL-SAR dataset using the UPGMA linkage function for P FA = 10 -4 . It can be observed that the SCM-based map presentes some oversegmentation due to the big tail observed in its linkage distances distribution (see Fig. 1). In the FP-based map, it can be observed that the pixels are grouped in differentiated areas comprising buildings, fields, roads, etc. These preliminary results support the CFAR hierarchical clustering of POLSAR data images.

Fig. 1 .

 1 Fig. 1. Comparison of the non-parametric distribution estimation of the linkage distances respect to the actual χ 2 distribution with six degrees of freedom.

Fig. 2 .

 2 Fig. 2. power representation image of the POLSAR dataset.

Fig. 3 .

 3 Fig. 3. Hierarchical clustering of the POLSAR data using the average linkage function and setting P FA = 10 -4 . Covariance matrix estimators are: (a) SCM and (b) FP.

5 .

 5 CONCLUSIONS AND FURTHER WORK In this work, we have used the statistical test of equality of covariance matrices, defined for high resolution POLSAR images classification, to propose a CFAR hierarchical clustering method. The proposed method takes advantage of the statistical test CFAR property to automatically detect the correct number of clusters for a given probability of false alarm. The preliminary experimental results over a real dataset encourages us to follow this research avenue. Further work will focus on extend the benefits of the CFAR property to other clustering algorithms such as the k-Means clustering algoritm, and to the statistical classification of POLSAR data.

http://www.mathworks.fr/fr/help/stats/linkage.html

Acknowledgements M.A. Veganzones was supported by the Delegation Generale de l'Armement (DGA) under contract PDE2012600079.


R Omar Chavez-Garcia

Trung-Dung Vu

Olivier Aycard

Fusion at Detection Level for Frontal Object Perception

Intelligent vehicle perception involves the correct detection and tracking of moving objects. Taking into account all the possible information at early levels of the perception task can improve the final model of the environment. In this paper, we present an evidential fusion framework to represent and combine evidence from multiple lists of sensor detections. Our fusion framework considers the position, shape and appearance information to represent, associate and combine sensor detections. Although our approach takes place at detection level, we propose a general architecture to include it as a part of a whole perception solution. Several experiments were conducted using real data from a vehicle demonstrator equipped with three main sensors: lidar, radar and camera. The obtained results show improvements regarding the reduction of false detections and mis-classifications of moving objects.

I. INTRODUCTION

Intelligent Vehicle Perception (IVP) relies on sensor data to model the static and moving parts of the environment. IVP is composed of two main tasks: simultaneous localization and mapping (SLAM) deals with modeling static parts; and detection and tracking moving objects (DATMO) is responsible for modeling dynamic parts of the environment. In SLAM, when vehicle location and map are unknown the vehicle generates a map of the environment while simultaneously localizing itself in the map given all the measurements from its sensors. DATMO aims at detecting and tracking the moving objects surrounding the vehicle in order to predict their future behaviors [START_REF] Vu | Vehicle Perception : Localization , Mapping with Detection , Classification and Tracking of Moving Objects[END_REF], [START_REF] Baig | Multisensor Data Fusion for Detection and Tracking of Moving Objects From a Dynamic Autonomous Vehicle[END_REF].

Usually, the tracking process assumes that its inputs correspond uniquely to moving objects. However, in most of the real outdoor scenarios, inputs include non-moving detections, such as noisy measurements or static obstacles. Sensors technical limitations contribute to these impressions. Accurate detection of moving objects is a critical aspect of a moving object tracking system. Therefore, many sensors are part of a common intelligent vehicle system.

Multiple sensor fusion has been a topic of research since long; the reason is the need to combine information from different views of the environment to obtain a more accurate model. This is achieved by combining redundant and complementary measurements of the environment. Inside the DATMO component, fusion can be performed at two *This work was also supported by the European Commission under in-teractIVe (http://www.interactive-ip.eu), a large scale integrating project part of the FP7-ICT for Safety and Energy Efficiency in Mobility. The authors would like to thank all partners within interactIVe for their cooperation and valuable contribution. Laboratoire d'Informatique de Grenoble, University of Grenoble1, Grenoble, France { 1 ricardo.chavez-garcia, 2 trung-dung.vu, 3 olivier.aycard}@imag.fr levels [START_REF] Baig | Multisensor Data Fusion for Detection and Tracking of Moving Objects From a Dynamic Autonomous Vehicle[END_REF]. At object detection level, sensor processes provide lists of moving object detections, then these lists are combined to get an enhanced list. At tracking level, lists of tracks of moving objects are fused to produce an enhanced list of tracks. Classification of moving objects is needed to determine the possible behavior of the objects surrounding the vehicle, and it is usually performed at tracking level. Knowledge about the class of moving objects at detection level can help to improve their tracking, reason about their behavior and decide what to do according to their nature [START_REF] Baig | Multisensor Data Fusion for Detection and Tracking of Moving Objects From a Dynamic Autonomous Vehicle[END_REF], [START_REF] Wang | Simultaneous localization, mapping and moving object tracking[END_REF].

Labayrade et al. presented a fusion technique between laser and stereo vision for obstacles detection [START_REF] Labayrade | Cooperative fusion for multi-obstacles detection with use of stereovision and laser scanner[END_REF]. This technique is based on stereo vision segmentation and lidar data clustering.Redundant positions in both sensor detections are considered real moving objects. Detections having no matching counterparts are taken as false alarms and are ignored. We believe that this is a strong assumption and that position information could not be enough to decide if an object is real.

Fayad et al. have proposed an evidential fusion technique based on the Dempster-Shafer (DS) theory [START_REF] Fayad | Detection and Recognition confidences update in a multi-sensor pedestrian tracking system[END_REF]. This technique is a mixture of object detection and tracking level fusion. Their work focuses only on the detection of pedestrians using multiple sensors by maintaining an score for each detection. Although the results are promising, this work only considers class information to perform object fusion, leaving out location information. Moreover, the extension to detect multiple moving objects classes is not straightforward.

Fusion at object detection level can enrich the object representation, allowing the tracking process to rely on this information to make better association decisions and obtain better object estimates. However, when combining different sensor inputs, we must take into account the classification precision of each sensor [START_REF] Vu | Vehicle Perception : Localization , Mapping with Detection , Classification and Tracking of Moving Objects[END_REF], [START_REF] Baig | Multisensor Data Fusion for Detection and Tracking of Moving Objects From a Dynamic Autonomous Vehicle[END_REF].

In this paper, we propose a fusion approach at detection level based on DS theory. We use all the detection information provided by the sensors (i.e., position, shape and class information) to build a composite object representation. Given several lists of object detections, the proposed approach performs an evidential data association method to decide which detections are related and then fuses their representations. We use lidar and radar sensor to provide an approximate detection's position; and we use shape, relative speed and visual appearance features to provide a preliminary evidence distribution of the class of the detected objects. The proposed method includes uncertainty from the sensor detections without discarding non-associated objects. Multiple objects of interest are detected: pedestrian, bike, car and truck. Our method takes place at an early stage of DATMO component but we present it inside a complete realtime perception solution.

In order to evaluate our approach we used real data from highways and urban areas. The data were obtained using a vehicle demonstrator from the interactIVe(Accident Avoidance by Active Intervention for Intelligent Vehicles) European project. Our experiments aim at evaluating the degree of improvement in DATMO results when early combination of class information is performed.

The rest of the paper is organized as follows. Next section describes the vehicle demonstrator and its sensor configuration. Section III reviews some concepts of the DS theory. In Section IV, we define our fusion framework at detection level. The implementation of this fusion framework is done using the architecture define in Section V. Experimental results are shown in Section VI. Finally, Section VII presents the conclusions.

II. VEHICLE DEMONSTRATOR

The CRF vehicle demonstrator we used is part of the interactIVe European project. The demonstrator is a Lancia Delta car equipped from factory with electronic steering systems, two ultrasonic sensors located on the side of the front bumper, and with a front camera located between the glass and the central rear mirror. Moreover, the demonstrator vehicle has been equipped with an scanning laser (lidar) and a mid-range radar on the front bumper for the detection of obstacles ahead, as depicted in Figure 1.

III. DEMPSTER-SHAFER THEORY BACKGROUND

DS theory is considered a generalization of the Bayesian theory of subjective probability. Whereas the Bayesian theory requires probabilities for each question of interest, DS theory allows us to base degrees of belief for one question on probabilities for a related question [START_REF] Smets | The Transferable Belief Model for Belief Representation[END_REF]. This theory is highly expressive, allows to represent different levels of ignorance, does not require prior probabilities, and manage conflict situations when opposite evidence appears.

DS theory represents the world in a set of mutually exclusive propositions known as the frame of discernment (Ω). It uses belief functions to distribute the evidence about the propositions over 2 Ω . The distribution of mass beliefs is done by the function m : 2 Ω → [0, 1] , also known as the Basic Belief Assignment (BBA), which is described in [START_REF] Vu | Vehicle Perception : Localization , Mapping with Detection , Classification and Tracking of Moving Objects[END_REF]. DS representation allows scenarios where there is uncertain evidence about all the proposition. Besides, a BBA can support any proposition A ⊆ Ω without supporting any sub-proposition of A, which allows to express partial knowledge.

m(∅) = 0; A⊆Ω m(A) = 1 (1)
We can represent the evidence from two sources as belief functions over the same frame of discernment. A combination rule takes these two belief distributions and combine them into a new one. Dempster's rule of combination is one of the most widely used [START_REF] Smets | The Transferable Belief Model for Belief Representation[END_REF]. It assumes independence and reliability of both sources of evidence:

m 12 (A) = B∩C=A m 1 (B)m 2 (C) 1 -K 12 ; A = ∅ K 12 = B∩C=∅ m 1 (B)m 2 (C) (2)
where K 12 is known as the degree of conflict. Dempster's rule analyses each piece of evidence to find conflict and uses it to normalize the masses in the set. However, in scenarios with high conflict values this normalization leads to counter intuitive scenarios. A possible solution is to avoid this normalization by moving the conflict evidence K 12 to all the possible elements of the frame of discernment Ω.

m 12 (A) = B∩C=A m b (B)m c (C); A = ∅ K 12 = B∩C=∅ m b (B)m c (C) m 12 (Ω) =m ′ 12 (Ω) + K 12 (3)
where m ′ r (Ω) is the combined evidence for the ignorance hypothesis. This modified Dempster's rule is known as Yager's combination rule.

IV. FUSION AT DETECTION LEVEL

Our work proposes a sensor fusion framework placed at detection level. Although this approach is presented to work with three main sensors, it can be extended to work with more sources of evidence. Figure 2 shows the general architecture of the proposed fusion approach. The inputs of this method are several lists of detected objects. Each detection is represented by its position and an evidence distribution of its class represented as a BBA. The reliability of the sources of evidence is encoded inside the BBAs. Class information is obtained from the shape, relative speed and visual appearance of the detections. The final output of the fusion method comprises a fused list of object detections, represented by a composite representation that includes: position, shape and an evidence distribution of class hypotheses.

A. Object detection representation

Usually, object detections are represented by their position and shape features. We believe that class information can be important to consider at detection level. However, at this level there is not enough certainty about the class of the object. Hence, keeping only one class hypothesis per detection disables the possibility of rectifying a premature decision.

Our composite object representation is defined by two parts. First, it includes position and shape information in a two dimensional space. Second, it includes an evidence distribution m c for all possible class hypotheses 2 Ωc , where Ω c is the frame of discernment representing the classes of moving objects of interest.

B. Data association

Let us consider two sources of evidence S 1 and S 2 . Each of these sources provides a list of detections denoted by A = a 1 , a 2 , .., a b and B = b 1 , b 2 , ..b n respectively. In order to combine the information of these sources we need to find the associations between the object detections in A and B. All possible associations can be expressed as a matrix M A,B of magnitude |AxB|, where each cell represents the evidence m ai,bj about the association of the elements a i and b j for i < |A| and j < |B|. We can define three propositions regarding the association of the detections in A and B:

• P (a i , b j ) = 1 : if a i and b j are the same object • P (a i , b j ) = 0 : if a i and b j are not the same object • P (a i , b j ) = Ω : ignorance about the association of the detections a i and b j Let us define Ω = {1, 0} as the frame of discernment of each m ai,bj , where {1} means that detection a i and b j belong to the same object, and {0} otherwise. Therefore, m ai,bj ({1}) and m ai,bj ({0}) quantify the evidence supporting the proposition P (a i , b j ) = 1 and P (a i , b j ) = 0 respectively; and m ai,bj ({1, 0}) stands for the ignorance, i.e., the evidence that can not support the other propositions. The three different propositions can be addressed by representing the similarity of the detections in A and B. This means, m ai,bj can be defined based on similarity measures between detections a i and b j .

Sensors S 1 and S 2 can provide detections of different kind. These detections can be represented by a position, shape or appearance information, such as class. Hence, m ai,bj has to be able to encode all the available similarity information. Let us define m ai,bj in terms of its similarity value as follows.

m ai,bj ({1}) =α i,j m ai,bj ({0}) =β i,j m ai,bj ({1, 0}) =1 -α i,j -β i,j (4)
where α i,j and β i,j quantify the evidence supporting the singletons in Ω for the detections a i and b j , i.e., the similarity measures between them.

We can define m ai,bj as the fusion of all possible similarity measures to associate detections a i and b j . Therefore, we can assume that individual masses of evidence carry specific information about these two detections. Let us define m p as the evidence measure about the position similarity between detections in A and B provided by sources S 1 and S 2 respectively; and m c as the evidence measure about the appearance similarity. Following the analysis made in Section III, we used Yagers's combination rule to represent m ai,bj in terms of m p ai,bj and m c ai,bj as follows:

m ai,bj (A) = B∩C=A m p ai,bj (B)m c ai,bj (C) K ai,bj = B∩C=∅ m p ai,bj (B)m c ai,bj (C) m ai,bj ({Ω}) =m ′ ai,bj ({Ω}) + K ai,bj (5)
where m p ai,bj and m c ai,bj represent the evidence about the similarity between detections a i and b j taking into account the position information and the class information, respectively.

Once the matrix M A,B is built, we can analyze the evidence distribution m ai,bj for each cell to decide if there is an association (m ai,bj ({1})), there is not (m ai,bj ({0})) or we have not enough evidence to decide (m ai,bj ({1, 0})), which is probably due to noisy detections. In the next sections we will describe how to calculate the fused evidence distributions using similarity evidence from the detections.

The fused representation is obtained by combining the evidence distributions between the associated objects by applying the combination rule from (3). This representation is passed as an input to the tracking stage to be considered in the motion model estimation of the moving objects. Nonassociated objects detections are passed as well expecting to be deleted by the tracking process if they are false detections or to be verified as real objects in case that more evidence confirms these detections.

C. Position similarity

According to the position of two detections a i and b j , we encode their similarity evidence in m p ai,bj . Based on their positions we can define the function d ai,bj as a distance function that satisfies the properties of a pseudo-distance metric. We choose Mahalanobis distance due to its ability to include the correlations of the set of distances [START_REF] Bellet | A Survey on Metric Learning for Feature Vectors and Structured Data[END_REF]. Therefore, a small value of d ai,bj indicates that detections a i and b j are part of the same object; and a large value indicates the opposite. Hence, the BBA for m p ai,bj is described as follows:

m p ai,bj ({1}) =αf (d ai,bj ), m p ai,bj ({0}) =α(1 -f (d ai,bj )), m p ai,bj ({1, 0}) =1 -α, (6)
where α ∈ [0, 1] is an evidence discounting factor and f (d ai,bj ) → [0, 1]. The smaller the distance, the larger value given by function f .

D. Class dissimilarity

Contrary to the evidence provided by position, class information does not give evidence that supports the proposition P (a i , b j ) = 1. This means that even if two detections are identified with the same class, one can not affirm that are the same object. This is due to the fact that there can be multiple different objects of the same class, e.g., in a real driving scenario many cars or pedestrians can appear. However, it is clear that if two detections have different class it is more likely that they belong to different objects. Hence, we use the class information to provide evidence about the dissimilarity of detections and place it in m c ai,bj . The frame of discernment for the class evidence distribution is the set Ω c of all possible classes. The frame of discernment for detections association is Ω and was described in Section IV-B. Hence, we propose to transfer the evidence from in Ω c to Ω as follows.

m c ai,bj ({1}) =0 m c ai,bj ({0}) = A∩B=∅ m c ai (A)m c bj (B), ∀A, B ⊂ Ω c m c ai,bj ({1, 0}) =1 -m c ai,bj (0) (7)
which means that we fuse the mass evidences where no common class hypothesis is share between detections in lists A and B. m c ai and m c bj represent the BBAs for class hypotheses of detections in lists A and B. However, as we have no information about the possible relation of detections with the same class, we place the rest of the evidence in the ignorance hypothesis {1, 0}.

V. FRONTAL OBJECT PERCEPTION APPLICATION

Figure 3 shows the general architecture of a frontal object perception application developed in the interactIVe project for the vehicle demonstrator described in Section II. The purpose of this architecture is to detect, classify and track a set of possible objects (pedestrian, bike, car and truck) in front of the vehicle demonstrator. Our proposed work is embedded in the fusion component of this architecture. It takes object detections from three sensors: radar, lidar and camera. Although there are three sensors, only two lists of object detections are provided as inputs to the fusion module.

A. Lidar object detection

Raw lidar scans and vehicle state information are processed to built a static map and detect moving objects. We employed the probabilistic grid-based approach presented in [START_REF] Vu | Vehicle Perception : Localization , Mapping with Detection , Classification and Tracking of Moving Objects[END_REF] to incrementally integrate discrete lidar scans into a local 2D occupancy grid. Inconsistencies through time in the occupancy grid allow the method to detect moving obstacles. The points observed in free space are classified as moving whereas the rest are classified as static. Using a clustering process we identify groups of points that could describe moving objects.

Once the clusters of possible moving objects are built, a bounding-box representation is drawn for each cluster, allowing to extract a visible shape-based description of each moving object. Shape information allows to have a first clue of the class of the detected object. First of all, we need to define the frame of discernment for the class hypotheses Ω c = {pedestrian, bike, car, truck}. According to the size of the object, we assign evidence to certain class hypotheses. We follow a fix-size model to do so. However, no precise classification decision can be made due to the temporary visibility of the moving objects. If the width of the bounding box is less than a threshold ω w we can think the object is a pedestrian or a bike but we can not be sure of the real size of the object. If the width of the object is greater than ω w the object is less likely to be a pedestrian or bike, but it can be either a car or a truck. We follow the initial evidence mass distribution and the discounting factors proposed in [START_REF] Chavez-Garcia | Fusion framework for moving-object classification[END_REF] to incorporate uncertainty about the classification evidence.

B. Camera based object classification

Lidar processing detection provides a rough classification of the detected moving objects. This classification relies on the visible shape of the detection which is a strong assumption in a highly dynamic environment. We believe that an appearance based classification could provide more certainty about the class of the detected objects. Therefore, we use the lidar detections to generate regions of interest (ROIs) in the camera images. Moreover, lidar detections give a better estimation of the real shape of the object. The ROIs are taken by vehicle and pedestrian classifiers to perform the camerabased classification. A modified version of histogram of oriented gradients (called sparse-HOG) features, which focus on important areas of the samples, powers the pedestrian and vehicle visual descriptor at training and detection time. Given computed descriptors for positive and negative samples, we use the discrete Adaboost approach proposed in [START_REF] Schapire | Improved boosting algorithms using confidence-rated predictions[END_REF] to train the vehicle and pedestrian classifiers. Its trade-off between performance and classification precision makes it suitable for real-time requirements.

Pedestrian and Vehicle classifiers are used to built another mass evidence distribution with the same frame of discernment described in Section V-A. Following the same basic belief assignment proposed in [START_REF] Chavez-Garcia | Fusion framework for moving-object classification[END_REF] we built a camerabased evidence distribution over the frame of discernment Ω c = {pedestrian, bike, car, truck}. Afterwards, using (3) we combine camera based class distribution with the lidar based distribution mentioned in Section V-A to obtain our first input for our fusion approach.

C. Radar target detection

Radar sensors have a good range resolution and a crude azimuth estimation. They usually provide an estimation of the position of moving targets and their relative speed. We use this estimation to built a second list of object detections as we did for the lidar data. However, the lack of shape information makes difficult to have clues about the object class at detection level. Although an estimate, the relative speed can give clues about the nature of the object. An detection with a high relative speed is most likely to be a motor-based vehicle such as car or truck. Nonetheless, no class assumption can be made about a low-speed object. Following the same idea and frame of discernment from Section V-A, we built a BBA by placing evidence in the vehicle hypothesis ({car, truck}) when the relative speed of a detection is greater than a speed threshold s rel (fixed a priori). In other cases, we put the evidence in the ignorance hypothesis {Ω}. Discounting factors are applied to take into account the uncertainty from radar detections.

D. Fusion considerations

Once we have performed moving object detection using lidar processing, the proposed approach obtains a preliminary description of the object position and object class encoded in m c lidar . Afterwards, taking advantage of the accuracy of the ROIs obtained by lidar and executing the camera based classifiers, a second evidence class distribution m c camera is obtained. These two evidence distributions are combined using [START_REF] Wang | Simultaneous localization, mapping and moving object tracking[END_REF] to form m c a . Radar processing provides already a list of detections identified by their position and relative speed. Following the method describe in Section V-C, we built the class distribution for radar detections m c b . Finally, both lists of object representations are processed in order to identify their associations and fuse their evidence distributions using ( 5), ( 6) and [START_REF] Bellet | A Survey on Metric Learning for Feature Vectors and Structured Data[END_REF].

E. Moving object tracking

Moving object tracking has to be performed in order to deliver the final output of a perception system. We follow the moving object tracking approach proposed by Vu [START_REF] Vu | Vehicle Perception : Localization , Mapping with Detection , Classification and Tracking of Moving Objects[END_REF]. We adapted this work to represent not only the lidar measurements but the composite representation obtained by our proposed fusion approach. Tracking mechanism interprets the composite representations sequence by all the possible hypotheses of moving object trajectories over a sliding window of time. Generated object hypotheses are then put into a top-down process taking into account all object dynamics models, sensor models and visibility constraints. We use the class evidence distribution to reduce the number of generated hypotheses by considering only class hypotheses with the highest mass evidence in 2 Ωc .

VI. EXPERIMENTS AND RESULTS

Using the vehicle demonstrator described in Section II, we gathered four datasets from real scenarios: two datasets from urban areas; and two datasets from highways. As a comparison approach we use our fusion approach at tracking level described in [START_REF] Chavez-Garcia | Fusion framework for moving-object classification[END_REF] which takes as inputs the same datasets. The goal of these experiments was to analyze the degree of improvement achieved by early inclusion of class information within the DATMO component.

We follow the general architecture from Section V to build our a complete perception system and test it using the gathered datasets. Among the 2D position state for each object detection, we define the frame of discernment Ω c = {pedestrian, bike, car, truck} for its evidence class distribution. Therefore, 2 Ω represents all the possible class hypothesis for each detection.

Figure 4 (a) shows three vehicles in front of the vehicle demonstrator. However, only two radar detections (from several spurious detections) are correct. In this situation, lidar based detection and camera based classification evidence placed in m c lidar and m c camera correctly complement the information about the farthest vehicle. Besides, moving object class is determined sooner than in the fusion approach at tracking level due to the early fused evidence about the object's class. False moving object detections are not deleted when fusion is performed, but they are passed to the tracking approach which will discard them after few non-associations.

Figure 4 (b) shows a cross road situation in a urban scenario. All the moving objects are detected but one car in the very front of the waiting line. Although the car is sensed by radar, there is not enough evidence from lidar detection and camera-based classification to verify its moving state. Moreover, the car is barely seen by lidar and few frames have passed to determine if it is moving or not. This car is consider a static unclassified object and appears in the top view. The car just behind this unrecognized car is as well consider static but it is identified and classified due to the previous detections that allowed to determine its moving nature.

Tables I and II show a comparison between the results obtained by the proposed fusion approach at detection level and our previous fusion approach at tracking level taking into account the mis-classifications of moving objects. Regarding the pedestrian classification, the obtained reduction in the number of mis-classifications does not seem to be as relevant as the other results. However, the classification of moving objects (not only pedestrians) in our proposed approach takes in average less sensor scans than the fusion approach described in [START_REF] Chavez-Garcia | Fusion framework for moving-object classification[END_REF] due to the early integration of the knowledge about the class of the objects placed in m c a and m c b . Table III shows the number of false detections obtained by the fusion at detection level and by the fusion approach at tracking level. In our experiments, a false detection occurs when a detection is identified as moving when it is not. This false detections occur due to noisy measurements and wrong object associations which are directly related to the lack detection data, e.g., position, size and class. The obtained results show that combining all the available information from detections at detection level reduces the number of mis-detections and therefore provides a more accurate list of objects to the tracking process, which ultimately improve the final result of the frontal object perception system. Furthermore, the implementation of our proposed fusion scheme complies with the real-time constrain required for real automotive applications.

VII. CONCLUSIONS

In this paper, we presented a multiple sensor fusion framework at detection level based on DS theory to represent class hypotheses, associate object detections and combine evidence from their position and appearance. Even if we use a specific set of sensors to feed our proposed fusion approach, it can be extended to include several sources of evidence. The proposed method includes uncertainty from the evidence sources and from the object classification.

Several experiments were conducted using datasets from real driving scenarios. We showed a quantitative comparison between the presented fusion approach at detection level and a fusion approach at tracking level. These experiments showed improvements in the reduction of mis-classifications and false detections of moving objects.

Fig. 1 .

 1 Fig. 1. Left: images of the CRF vehicle demonstrator. Right: Field of view of the three frontal sensors.

Fig. 2 .

 2 Fig. 2. Schematic of the proposed fusion architecture.

Fig. 3 .

 3 Fig. 3. General architecture of the FOP module for the CRF demonstrator.

Fig. 4 .

 4 Fig. 4. Frontal object perception results for (a) highway scenario and (b) urban area. Left side of each figure shows the image from camera sensor and the identified moving objects. Yellow boxes represent moving objects, red dots represent lidar hits and red circles represent radar detections. Right side of each figure shows the top view of the scene show in the image. Objects classes are shown by tags close to each object.

TABLE II PEDESTRIAN

 II AND BIKE MIS-CLASSIFICATIONS OBTAINED BY THE FUSION APPROACHES. HIGHWAY DATASETS CONTAIN ONLY VEHICLES.

				Number of pedestrian mis-classifications
	Dataset	Number of	Tracking level	Detection level
		pedestrians
		and bikes
	urban 1	21		6	5
	urban 2	23		8	6
				TABLE III
	MOVING OBJECTS FALSE DETECTIONS OBTAINED BY THE FUSION
				APPROACHES.
				Number of object false detections
	Dataset	Tracking level	Detection level
	highway 1	7		4
	highway 2	8		5
	urban 1	18		10
	urban 2	19		9