Petr Spacek
email: spacek@lirmm.fr

Christophe Dony
email: dony@lirmm.fr

Chouki Tibermacine
email: tibermacin@lirmm.fr

Luc Fabresse
email: luc.fabresse@mines-douai.fr

An Inheritance System for Structural & Behavioral Reuse in Component-based Software Programming

Keywords: D.1.0 [Programming techniques]: General-Component based programming technique; D.2.11 [Software Architectures]: Languages-Component Based Programming Language Component-based, Programming, Language Programming, Inheritance, Architectures, Substitutability

In the context of Component-based Programming, which addresses the implementation stage of a component-based software engineering development process, this paper describes a specification and an operational integration of an inheritance system into a self-contained new componentbased programming language named COMPO. Our proposal completes and extends related works by making it possible to apply inheritance to the full description of components, i.e. both to structural (description of provisions and requirements, of component architecture) and behavioral (full implementations of services) parts in component descriptions. Inheritance in COMPO is designed to be used in conjunction with composition to maximize reuse capabilities and expressive power. COMPO implementation proposes a clear operational solution for inheritance and for achieving and testing substitutions.

Introduction

Component-based software is made of off-the-shelf components, connected together into various kinds of architectures.

[Copyright notice will appear here once 'preprint' option is removed.] In this domain, several languages, using the component concept as a first class entity in organizing software, have been and are currently designed and prototyped, but some categories have emerged. Architecture Description Languages (ADLs) for models like Fractal [START_REF] Bruneton | The fractal component model and its support in java: Experiences with auto-adaptive and reconfigurable systems[END_REF] or SOFA [START_REF] Plásil | Sofa/dcup: Architecture for component trading and dynamic updating[END_REF] allow for business-oriented and implementation-independent components and architectures descriptions. Component-Based-Programming Languages (CBPLs) like ACOEL [START_REF] Sreedhar | Mixin'up components[END_REF], Arch-Java [START_REF] Aldrich | Archjava: connecting software architecture to implementation[END_REF], CLIC [START_REF] Bouraqadi | Clic: a component model symbiotic with smalltalk[END_REF], ComponentJ [START_REF] Seco | Componentj: A component-based programming language with dynamic reconfiguration[END_REF], Bichon [START_REF] Xu | Bichon: A new component-oriented programming language[END_REF], Comp-Java [START_REF] Schmid | Engineering a component language: Compjava. In Software and Data Technologies[END_REF] or SCL [START_REF] Fabresse | Foundations of a simple and unified component-oriented language[END_REF][START_REF] Fabresse | Filling the Gap between Design and Implementation with Components[END_REF] address the implementation stage of a component-based software engineering development process; they allow developers to express full descriptions of executable components.

Inheritance has proved to be one major cornerstone of software reuse, first for the ability it gives developers to organize their ideas on the base of concept classification (a list is a kind of collection, such architecture is a kind of visitor, ...) which is itself one key of human abstraction power and second for the calculus model that makes it possible to not only reuse but adapt software, by executing an inherited code in a new context (the receiver environment).

Many of the above quoted languages somehow propose inheritance mechanisms but they have various limitations (limitation to the architecture description side, limitation to the implementation side which is frequently not achieved with component-based languages, limitation to some part of components descriptions, etc). More generally, the question of the interest of inheritance-based reuse in the componentbased software development context is still discussed and has not yet been explicitly nor fully addressed. This papers aims at contributing to that question by proposing a specification and an operational integration of an inheritance system in the context of a component-based programming languages that supports reuse of descriptions of components' structure and behavior. By "structure", we mean provided and required ports together with internal architectural description; and by "behavior", we mean implementations of services that make them executable. Our language, COMPO, ranges in this category and proposes components as runtime entities, instances of descriptors. We introduce an inheritance link between descriptors on which we base an operational system to reuse, i.e. to inherit, extend and specialize descriptions. Descriptors are texts describing components' structure and behavior. Listings 1 and 2 are examples of component descriptors in COMPO.

We address the specific questions of stating what, among port declarations, composition architectures and services definitions, can be inherited, extended or specialized, and how. We notably discuss the rationale and interest of enabling requirements extension or specialization: we will consider various solutions, but will develop an answer to that question which goes in the direction of enabling covariant specialization, because it corresponds to the way human naturally think about concept classification [START_REF] Ducournau | real world" as an argument for covariant specialization in programming and modeling[END_REF] and it promotes expressive power. Our solution will thus propose simple support to help programmers achieve correct substitutions.

An alternative for reuse in the component-based software development context is to use sole composition (see [START_REF] Seco | A basic model of typed components[END_REF][START_REF] Xu | Bichon: A new component-oriented programming language[END_REF] and [START_REF] Weck | Do we need inheritance?[END_REF] for a good survey) and message redirection (or forwarding; or delegation1 ); it has the advantage of not introducing any additional mechanism. Our opinion is that composition and inheritance are complementary and that their combination is significantly more efficient especially when structural reuse is to be considered. The above alternative will be further discussed in the related work section, where we show some examples in which sole composition usage leads to code being too complex and reuse being difficult. Inheritance in COMPO is thus designed to be used in conjunction with composition to maximize software reuse capabilities and language expressive power.

The paper is organized as follows. Section 2 proposes an overview of COMPO essential constructions and syntax. Section 3 is a step-by-step (services definitions, requirements declarations, internal architecture description) discussion and presentation of our inheritance system specification illustrated with various examples. Section 4 gives some basic clues on the COMPO's implementation. Before concluding and discussing the future work, we present in Section 5 the related works.

A support Component-based programming language

Our proposition for inheritance is demonstrated and validated via its integration into a component-based language named COMPO. Although the language itself is not the subject of this paper, it is needed that we give an overview of its main constructs and syntax. COMPO is an ongoing work that aims at defining in an unified context (1) a component-based architecture description and modeling language that includes all standard component architectures concepts and constructs (eg. component, ports, interfaces, connections, constraints, etc) and (2) a component-based programming language making it possible to write executable applications, in which all the above concepts and constructs are available as first-class entities. This language overall goal is to allow standard applications or architecture verification and transformations applications to be written in the same language, via an integrated meta-level. COMPO is here used for our operational study on inheritance because, as far as we know, there exists no other language in which component architectures and services can be written in the same context and using the same high-level constructs for component-based development. Many component-based architecture are for example translated into Java template code and implemented in a world where concepts such as ports do not have a first-class status.

From a concrete point of view, within a component description (see e.g. listing 1), the p r ov i des, r equ i r es, i n t e r na l l y r equ i r es and a r ch i t ec t u r e sections are related to components modeling and architecture description. The se r v i ce section is related to services programming; this section can be omitted if the architecture is to be generated into another language.

Component descriptors.

COMPO applies the descriptor/instance dichotomy where components are instances of descriptors. A component descriptor is a text describing the structure (ports declarations and architecture description) and the behavior (set of services definition) of its instances.

As a first example, Listing 1 shows a version of a F r on t End component descriptor. F r on t End components can be used to build various kind of request servers. This descriptor defines : (1) an external provided port named de f au l t , providing services r un ( ) and i sL i s t en i ng ( ), (2) an external required port named backEnd through which an architect can connect a F r on t End to any other component providing the hand l eReques t service, (3) two internal required ports to achieve internal composition with a Reques t Hand l e r and with a TaskSchedu l e r (note that to satisfy requirements internally or externally is an architectural decision that has several possible solutions, any F r on t End in this example will come equipped with its Reques t Rece i ve r and TaskSchedu l e r). (4) the internal architecture of a F r on t End, (5) the public services of a F r on t End, only one ( i sL i s t en i ng ( )) being shown. Concepts and syntax used in this example are detailed in the following sub-sections also using the description of an HTTP Server (see listing 2) which uses a F r on t End.

Ports

In COMPO, a port is a connection point (components are connected through their ports) and a communication point (ser-c o m p o n e n t d e s c r i p t o r F r o n t E n d { p r o v i d e s { d e f a u l t : { r u n ( ) ; i s L i s t e n i n g ( ) ; } } r e q u i r e s { b a c k E n d : { h a n d l e R e q u e s t ( r ) } } i n t e r n a l l y r e q u i r e s { r R < : R e q u e s t R e c e i v e r ; s : T a s k S c h e d u l e r ; } a r c h i t e c t u r e { d e l e g a t e d e f a u l t t o r R@ . d e f a u l t ; c o n n e c t s t o ( T a s k S c h e d u l e r n e w ) . d e f a u l t ; c o n n e c t r R@ . s c h e d u l e r t o s @ . s c h e d u l e ; d e l e g a t e r R@ . h a n d l e r t o b a c k E n d ; } s e r v i c e i s L i s t e n i n g ( ) { ^r R i s R u n n i n g . } } Listing 1. The F r on t End descriptor vices invocations are transmitted via ports). A port is defined by a an owner component, a name, a list of service signatures, a visibility (external or internal) and a role (provided or required).

The role of a port is either required or provided with a standard semantics : a provided (resp. required) port lists, the signature of services offered (resp. required) by a component.

The list of services signatures associated to a provided port can be given :

• as an explicit list (we call such a list an anonymous interface) (the de f au l t port declaration in Listing 1 is an example).

• via a named interface (see Section 3.3 ),

The list of signature associated to a required port can be given as an explicit list or via a named interface, as above, or via a component descriptor name (e.g. cd); in this case, the list is the list of signatures of services associated to cd's default provided port (the sched port declaration in Listing 1 is an example).

The visibility of a port is either internal or external (the default is "external").

• An external port ep of a c component is visible and can be used by an architect to interconnect c into an englobing composition architecture. For example, the external required port backEnd of an instance of F r on t End can be connected to the external provided port de f au l t of an instance of BackEnd as shown in listing 2 and in figure 1 (we are developing both textual and graphical component definition interfaces).

Each component has a default external provided port (named de f au l t ) listing signatures of public services of its owner component, and has a default and unique internal provided port, named se l f (for obvious historical reasons), listing signatures of all services of its owner component and allowing any of its services to invoke another one.

• An internal port i p of a c component is a support for accessing c's internal composition architecture, i p and the component connected to it (that we call an internal component of c ) are invisible from the outside of c.

In Listing 2, it is shown how the two internal required ports of a HTTPSe r ve r are connected to its two internal components : a F r on t End and a BackEnd, allowing it to invoke their services (e.g. f E i sL i s t en i ng in service s t a t us).

• The list of external ports (provided and required) define the external contract of a component.

Connections

A connection establishes a dual referencing between two ports, making it possible to determine whether a port is connected or not and, if true, to which other port it is connected. When we sometimes write, in a somehow misleading but admitted way, that two components are connected, it is meant that one port of the former is connected to one port of the later.

• A regular connection is between a required and a provided port. We provide two equivalent syntax for connections : ( connec t | de l ega t e ) <po r t > t o <po r t >, or <po r t > = : = <po r t >, where <po r t > is any expression returning a port. An example of an expression establishing a regular connection is : connec t s t o ( TaskSchedu l e r new ) . de f au l t ; , (see. Listing 1).

• A delegation connection is between two ports having the same role and is used to delegate a service invocation from an external to an internal via the composite (provided to provided), or from an internal to an external via a composite (required to required). An example of a "provided to provided" delegation connection is de l ega t e de f au l t t o rR@ . de f au l t ; in Listing 1).

Internal architectures

!"#$%&' $()**+,"-."-/"-.01"(/'$'%/23(4 ((#5(0/60/'"7078 ((((0#*-%"9(:(;(<=($>(-%77078<(? ((((0#@$&/"9(:(;(<=($>(/'ABB"!<(? C #5(9(@-A7'57!

!"#$%&' -"D)$ E$1F57! E5(9(G$1F57! !"#$%&' -%723H /'$'%/23H -%723H 0/60/'"707823H I$7!&"J"D2I''BJ"D%"/'3H !"#$%#&'()$)*! Figure 1.
HTTPServer, the diagram shows a logical representation of an instance of the HTTPSe r ve r descriptor presented in Listing 2, after it has been created and initialized.

An internal architecture of a component is the set of its internal components (components connected to its internal required ports) together with their inter-connections. A component having internal component is as usual called a composite. Initialization (i.e. instantiation and connection) of internal components of a composite c is performed during c's instantiation if described in the c's descriptor architecture section.

For example, the internal ports and architecture sections of descriptor HTTPSe r ve r define the following internal architecture for its instances.

• The internal required port f E is connected to a F r on t End.

• The internal required port bE is connected to a BackEnd. Note that: bE < : BackEnd in the port section is a shortcut to avoid writing the following instruction in the architecture section : connec t bE t o (Backend new ) . de f au l t ).

• The internal required port name is connected to a S t r i ng. S t r i ng is a predefined component descriptor the role of which is to interface all basic types of the hosting language so that their elements can be used as standard components. Predefined descriptors expose a single provided port named de f au l t through which procedures or methods of basic types can be called in the form of a service invocation via the COMPO interpretor or virtual machine.

• a delegation connection is created between the provided port de f au l t and the de f au l t port of the f r on t End. • a regular connection is created between the required port backEnd of the component connected to the f E internal required port and the port de f au l t of the component connected to the bE internal required port: connec t f E@ . backEnd t o bE@ . de f au l t .

This connection is a good example of a situation in which architecture design requires that a refence be made to a component which is not yet created. Here we need to say that we want to connect the port backEnd of the component that will be be connected to port f E. The @ operator makes it possible, for any port p to reference the component that will later on be connected to p and subsequently to specify an architecture before descriptors are instantiated.

Services & Service invocations

Services implement the behavior of components. A service may have parameters and may return a value. Components communicate by service invocations made through required ports. A service invocation consists of a port name, a selector (the name of the requested service) and optional arguments. f E i s l i s t en i ng is an example of a service invocation made through the f E port in the context c o m p o n e n t d e s c r i p t o r H T T P S e r v e r { p r o v i d e s { d e f a u l t : { r u n ( ) ; s t a t u s ( ) } } i n t e r n a l l y r e q u i r e s { f E : F r o n t E n d ; b E < : B a c k E n d ; n a m e < : S t r i n g ; } a r c h i t e c t u r e { f E = : = ( F r o n t E n d n e w ) . d e f a u l t ; d e l e g a t e d e f a u l t t o f E@ . d e f a u l t ; c o n n e c t f E@ . b a c k E n d t o b E@ . d e f a u l t ; } s e r v i c e s t a t u s ( ) { f E i s L i s t e n i n g i f T r u e : [ ^n a m e p r i n t S t r i n g + ' i s r u n n i n g ' ] i f F a l s e : [ ^n a m e p r i n t S t r i n g + ' i s s t o p p e d ' ] . } } Listing 2. The HTTPSe r ve r descriptor.

of the s t a t us ( ) service of component HTTPSe r ve r. When a required port receives an invocation it transmits it to the port it is connected to. The receiving port then transfer the invocation to its owner component which is responsible for handling it (either executing a corresponding service or delegating the invocation via a delegation connection, full detail on this can be found in [START_REF] Fabresse | Foundations of a simple and unified component-oriented language[END_REF]).

Rationale and rules to reuse descriptions with inheritance

This section presents the rationale and the operational description of our descriptor-level inheritance embedded in our CBPL. Ports declarations, internal architecture definition and initializations, services definitions; and more generally all pieces of code specified at the descriptor level are subjects to inheritance, extension and redefinition.

For the sake of simplicity, we have limited our proposal to single inheritance relationship.

Descriptors and basic inheritance

Any descriptor can be defined as a sub-descriptor of an existing descriptor (D). In such a case, D's port declarations, internal architecture and service definitions are inherited. Every sub-descriptor has, by default, the supe r internal provided port. The port differs from regular provided ports in one small detail: services implementations demanded by service invocations sent to this port are looked up starting from the super-descriptor of the owning descriptor (not directly from the owning descriptor as it is in the case of regular provided ports).

Listing 3 show the Con t r o l ab l eF r on t End subdescriptor that extends the F r on t End descriptor (shown in Listing 1) with a new port named con t r o l . Ports declarations and internal architecture described in the F r on t End descriptor are inherited by the Con t r o l ab l eF r on t End descriptor, this is taken into account when creating an instance of the Con t r o l ab l eF r on t End descriptor whose structure will conform to what is described in the F r on t End descriptor.

In Listing 4 we show an another sub-descriptor named (Res t a r t ab l eF r on t End) which extends the Con t r o l ab l eF r on t End descriptor with a new service. Services defined in the F r on t End and Con t r o l ab l eF r on t End descriptors are inherited by the Res t a r t ab l eF r on t End descriptor. This is taken into account when instances of the Res t a r t ab l eF r on t End descriptor are created and receive services invocations (lookup algorithm). Listing 4. The Res t a r t ab l eF r on t End descriptor. Specializes the con t r o l port of Con t r o l ab l eF r on t End descriptor and service i sL i s t en i ng inherited from F r on t End

Extension & specialization of services

To be able to inherit, extend and specialize the behavior defined by a component descriptor, a sub-descriptor can introduce new services and its instances can access and reuse services defined by its super-descriptor. This gives us ability to define behavior that's specific to a particular sub-descriptor, i.e. achieve polymorphism of descriptors.

A service can be redefined in a sub-descriptor and can reuse the one it specializes by using the supe r internal provided port. Sending an invocation to supe r states that the service implementation should be looked for in the superdescriptor of the descriptor in which the current service in execution has been found. Listing 4 shows an example of specialization and extension of services, where the descriptor Res t a r t ab l eF r on t End extends the descriptor Con t r o l ab l eF r on t End with a new service r es t a r t ( ) and specializes service i sL i s t en i ng ( ) defined in Con t r o l ab l eF r on t End, supe r is used to access Con t r o l ab l eF r on t End's implementation of the i sL i s t en i ng ( ) service.

Extension & specialization of declarations of provided ports

The basic goal here is to be able to introduce a new provided port declaration and be able to specialize a declaration (i.e. a list of service signatures) of an inherited port. This capability leads to a higher expressive power. For example, sub-descriptors are able to export an internal behavior via newly added ports. Such an export does not break the encapsulation of the internal component, because it exports behavior which has already been public. Another use is definition of more viewpoints for a component, where each provided port represents a viewpoint on the component. Specialization of ports introduces more precise modeling possibilities for software architects. An example of extension and specialization of provided ports is illustrated in Listings 1, 3 and 4, where the Con t r o l ab l eF r on t End descriptor extends original F r on t End descriptor with a new port named con t r o l . The Res t a r t ab l eF r on t End descriptor specializes the inherited port con t r o l with a new service signature. The specialization of port roles makes sense only from the required role to the provided role. Indeed, this kind of role specialization can be performed simply by a delegation of a required port to a provided port of a component. Thus, there is no reason for allowing specialization of the roles of ports.

We extend a set of ports simply by introducing a new port in a sub-descriptor. A name of newly added port cannot clash with existing port names. In Listing 3 we extend the original F r on t End descriptor with a new port named con t r o l in order to export control behavior offered by the internal component connected to the rR internal required port.

There are two scenarios how to specialize the list of service signatures of an inherited port: (1) a specialization by adding new service signatures to its list of service signatures (i.e. extending an anonymous inherited interface). The Res t a r t ab l eF r on t End example in Listing 4 shows the specialization of the con t r o l port defined by the Con t r o l ab l eF r on t End super-descriptor. The specialization is used in order to provide the r es t a r t service defined by the descriptor Res t a r t ab l eF r on t End. (2) a specialization using a named interface. In this case the set of service signatures defined in the named interface has to be a super-set of the set of service signatures used to describe the original port. A specialization of a port named po r t A looks like: p r ov i des { po r t A : I spec}. In the super-descriptor, po r t A was declared by the statement: p r ov i des { po r t A : { se r 1 ( ) ; se r 2 ( ) }}. The I spec interface was defined with the statement i n t e r f ace I spec { se r 1 ( ) ; se r 2 ( ) ; se r 3 ( ) }. The named interface I spec defines a set of service signatures, which is a super-set of a set representing the anonymous interface of the original po r t A port. Therefore it can be used for the specialization.

!"#$$#"%&'()*+!,-.

Extension & specialization of declarations of external required ports

In our inheritance system, we enable adding new declarations of required ports to sub-descriptors and we allow for modification of a declaration of an inherited required port. Extension and specialization of required ports are needed to preserve expressive power of our language. For example, without such a capability, we will not be able to extend the Ema i l e r descriptor shown in Figure 2 with a new required port seman t i csChecke r or specialize its required port syn t axChecke r with a new required service signature g r amma rCheck i ng ( ). Syntactically these operations do not differ from extension and specialization of provided ports. Listing 5. An example of unsatisfied required port problem and its solution using the r econnec t and newCompa t i b l e support tools. The RandomReques t sQueue descriptor extends the Reques t Queue descriptor with an additional required port to which an instance of the RandomGene r a t o r descriptor should be connected.

Semantically the extension and specialization of required ports introduce a new issue, it breaks child-parent substitutability. In OOPLs, substitutability between sub-classes and super-classes is guaranteed. To be more precise, interface compatibility is guaranteed. Behavior compatibility is still not guaranteed, as pointed by [START_REF] Martin | Agile Software Development, Principles, Patterns, and Practices[END_REF]. In CBPL with the possibility to extend or specialize super-descriptor's require- ments creating a potentially non-substitutable sub-descriptor is possible. Additional required ports may became unsatisfied, when an instance of such a sub-descriptor is used where an instance of the super-descriptor is expected. This may break up the system. In other words, adding new required ports (or specializing a required port in a sub-descriptor) violates the Liskov's substitution principle [START_REF] Liskov | Programming with abstract data types[END_REF]. These operations change components dependencies and can lead to unspecified behavior. This is illustrated in Figure 3 and Listing 5, where an instance2 of the Reques t Queue descriptor is substituted with an instance of the RandomReques t sQueue descriptor. The RandomReques t sQueue descriptor extends the Reques t Queue descriptor with an additional required port to which an instance of the RandomGene r a t o r descriptor should be connected. At runtime, when an instance of the Reques t sQueue descriptor is substituted by an instance of the RandomReques t sQueue descriptor, the r andomGen required port may became unsatisfied.

This problem has three possible solutions: (1) forbid extending requirements, but requirements have been made explicit in components and they are considered as important entities to make it possible to introduce new connections. Therefore it is undesirable to limit expressive power of modeling by forbidding extension and specialization of requirements. For example, without possibility to add a required port it is complicated to design the Ema i l e r example shown in Figure 2; (2) constrain substitutions -define a rule saying that an original component can be substituted by a new one, only if the new one provides at least the same and requires at most the same as the original one; (3) allow additional requirements and delegate responsibility for additional re-quirements satisfaction to the language users, while providing verification support for substitutions.

With COMPO all alternatives are possible, but since the language is oriented toward modeling flexibility, we have experimented with the third alternative. We will thus support covariant specialization if and when needed because it corresponds to the way human naturally think differential description [START_REF] Ducournau | real world" as an argument for covariant specialization in programming and modeling[END_REF]. Our inheritance mechanism does not apply any restrictions to implicitly guarantee substitutability. Substitutions in COMPO are under the developer's control and responsibility.

We are providing three support methods: (1) the newCompatible method to return a component compatible with the super-descriptor of the component (the service is automatically created for each sub-descriptor which extends its parent with additional requirements); (2) the reconnect method (executed when a substitution is performed) to warn users about unsatisfied additional requirements (by an exception) and ( 3) the isCompatibleWith method to help developers to check the validity of a substitution. For an example of usage see Listing 5.

The first substitutions support comes in case when a sub-descriptor has an additional required port. Then our inheritance system automatically generates a method called newCompa t i b l e : The method has a unique parameter, an array of pairs port-component. The method is able to create an instance, which is substitutable with instances of the super-descriptor. That is all additional requirements are satisfied by connections to components given in the array argument.

The second support is the r econnec t : t o : method to achieve substitutions safely. This method takes two arguments, the first one is the name of an internal required port referencing the component which should be replaced and the second argument is the replacing component. r econnec t : t o : checks for compatibility between the original and the new component descriptor, i.e. checks if the new component provides and requires at least the same as the original one and checks if all requirements will be satisfied after substitution. If all requirements of the new component are satisfied, the replacement is performed, otherwise an exception is thrown. r econnec t : t o : reconnects all ports of the original component to corresponding ports of the new component and connects the new component to the corresponding internal required port of the composite to reference the new component.

For components compatibility checking purposes we provide i sCompa t i b l e method. The i sCompa t i b l e method is able to compare the external contracts of compared components and answer by true if they are compatible and false otherwise. The method is useful for the r econnec t : t o : method, which warns users in the case of unsatisfied requirements.

Extension & specialization of internal architectures

Internal architecture description and initialization is inherited by a sub-descriptor and it can be extended and specialized. When a large and complicated architecture needs to be reused, the language should support such a feature.

In COMPO, a sub-descriptor may extend a set of internal components by introducing a new internal required port. Usually this action implies extension and specialization of internal connections. These operations are illustrated in Figure 3, where the descriptor QueuedHTTPSe r ve r extends the descriptor HTTPSe r ve r with a new internal component named queue (described by Reques t sQueue). And it specializes the inherited connections in order to assemble the queue component into the architecture of its superdescriptor. COMPO code of QueuedHTTPSe r ve r is given in Listing 6.

Specialization of an inherited internal component in a sub-descriptor can be achieved by modifying the interface description of the internal required port associated with the internal component. The descriptor of Pr i o r i t yQueuedSe r ve r in Listing 6 specializes an inherited internal component queue by describing it with the Pr i o r i t yReques t sQueue descriptor .

The specialization of an inherited internal connection can be achieved by the combination of statements having the following syntax: d i sconnec t <po r t -name> f r om <po r t -name> and connec t <po r t -name> t o <po r t -name> (statements were explained in Section 2.5). i n t e r n a l l y r e q u i r e s { q u e u e < : R e q u e s t s Q u e u e } a r c h i t e c t u r e { d i s c o n n e c t f E@ . b a c k E n d f r o m b E@ . d e f a u l t ; c o n n e c t f E@ . b a c k E n d t o q u e u e @ . i n ; c o n n e c t q u e u e @ . o u t t o b E@ . d e f a u l t ; } } c o m p o n e n t d e s c r i p t o r P r i o r i t y Q u e u e d S e r v e r e x t e n d s Q u e u e d H T T P S e r v e r { i n t e r n a l l y r e q u i r e s { q u e u e < : P r i o r i t y R e q u e s t s Q u e u e } } Listing 6. Specialization and extension of an internal architecture.

Implementation

The current implementation of COMPO is used as a laboratory for exploring new ideas and is built in [START_REF] Black | Pharo by Example[END_REF] as an extension of the SCL [START_REF] Fabresse | Foundations of a simple and unified component-oriented language[END_REF][START_REF] Fabresse | Filling the Gap between Design and Implementation with Components[END_REF] implementation in the context of a global effort towards the development of efficient dynamic languages.. We have chosen Smalltalk because we are a part of the effort to bring component concept into the Pharo environment. Descriptors and sub-descriptors are implemented as subclasses of the CompoComponen t class. The CompoComponen t class contains the mechanism to store necessary inforation about ports and associated interfaces, internal components and connections. The inheritance mechanism uses Smalltalk's meta-model facilities to implement extension and specialization operations for both the structure and behavior of descriptors.

Readers can download a Pharo image of COMPO implementation here: http://www.lirmm.fr/∼spacek/compo/ In this section we give an overview of how inheritance is used in existing Component-based Programming Languages (CBPLs) and ADLs, and compare this with our proposal. We also compare our proposal based on a combination of inheritance and composition with inheritance-free proposal in which all reuse schemes are achieved using sole composition.

It is important to note, that none of these languages we have studied propose a complete specification of inheritance which concerns all main reuse aspects. Our knowledge about the behavior of their inheritance mechanism often had to be extracted from experiments conducted using these languages. The list of related works is not exhaustive; especially ADLs that do not support any form of descriptors inheritance are not included.

Inheritance in related CBPLs

Here, we compare how related CBPLs integrate inheritance aspects such as: the structure inheritance , the behavior inheritance and abilities to extend and specialize particular definitions in a component descriptor (i.e. ports, internal components and connections.) As related CBPLs we consider ACOEL [START_REF] Sreedhar | Mixin'up components[END_REF], ArchJava [START_REF] Aldrich | Archjava: connecting software architecture to implementation[END_REF], CLIC [START_REF] Bouraqadi | Clic: a component model symbiotic with smalltalk[END_REF] and CompJava [START_REF] Schmid | Engineering a component language: Compjava. In Software and Data Technologies[END_REF], because these languages combine implementation and architecture specification.

Structure inheritance is partially supported in all other languages. We say partially, because CompJava do not allow the reuse of internal components and connections spec-ification. Ports declarations can be reused via component type definition. Except that they use a different terminology, the languages define component type as a set of port names including interface references and roles specification. And then a component type can be defined as an extension of an existing component type

Behavior inheritance is fully supported only in CLIC and ArchJava languages. ACOEL model supports implementation inheritance by the extend statement, but a child cannot access any of the internals (implementation classes, methods) of a parent, except via the input ports of the parent, i.e. t h i s . <po r t name> . <se r v i cename> (composition-like approach). The advantage of this black-box approach is that it preserve encapsulation of parent components. We support white-box approach to be able to specialize services implementations which are not provided by a parent.

Ports specialization is not supported in ArchJava, because adding new provided methods to an existing port might cause ambiguities if these provided methods were required by a connected component, and provided by a different component. There would then be two components providing the same required method, breaking ArchJava's connection rules. Adding required methods to an existing port would make the component class non-substitutable for the component superclass, because connections made to the superclass might not provide the subclass's required methods. Required methods in a new port are also problematic, because the new port might not be connected at all.

An interesting solution comes with ACOEL model, which uses ports parametrized by mixins [START_REF] Bracha | Mixin-based inheritance[END_REF]. During instantiation a mixin can be passed as an argument of a component constructor and a parametrized port is then "decorated" with new behavior. In COMPO, ports are just descriptions of communication and connection points. Therefore, they should not carry any implementation of behavior or its specialization.

Ports extension is well supported. CLIC model does not support additional provided port, because this model allows components to have only one provided port. The idea of a single provided port is based on the observation that developers do not know beforehand, which services will be specified by each required port of a client component. Therefore it is hard to split component functionality over multiple ports. We see this as a unnecessary limitation of modeling power.

On the other hand, in the CompJava, a component type may extend another component type and it inherits all ports. It may extend the interface of inherited provided ports or may add provided ports. Extension of required ports is not allowed due to the substitutability policy of the CompJava model.

Architecture extension and specialization. ACOEL and ArchJava treat internal components as regular instance variables of classes and therefore there is no way to specialize inherited internal components. CompJava supports inheritance of component types only. Component types do not involve internal components and connections declarations, therefore architecture cannot be reused.

Substitutions. ACOEL, ArchJava and CompJava define sub-type relation as defined by Liskov [START_REF] Liskov | Programming with abstract data types[END_REF]. In general, a component type is a sub-type of another one if it provides at least the same and requires at most the same. To ensure ACOEL use a type system checking. CompJava and Arch-Java forbid additional requirements (in inherited types) and then they restrict substitutability by the sub-type relation.

In Table 1, we make a summary of this comparison.

Inheritance in related ADLs

Structure reuse is a primary inheritance property supported by ADLs [START_REF] Oplustil | Inheritance in architecture description language[END_REF], which operate mainly at design stage in the development process. They make it possible to design software using components and then convert them into a component framework written in OOPLs or other programming languages (but not CBPLs). ADLs generally do not support behavior inheritance, because behavior of components is specified either in programming languages they are implemented in, or using some formalisms where there is no inheritance.

For example Fractal and its Fractal ADL allow to extend one component definition with another one, then a subdefinition can add or override elements. It also extends component type definition with contingency (optional or mandatory) and cardinality for each port. It is possible to add connections but impossible to specialize an inherited connection.

SOFA Component Definition Language (CDL) uses the frame term for component types. One frame can inherit from another frame and then port declarations are reused. To compose several frames, SOFA introduce architecture construct, where an architecture implements a frame and may inherits from an another architecture. In this way, internal components and connections are reused. Ports are specialized using interface redefinition i.e. by the following statement f r ame Componen t Name i nhe r i t s I nhe r i t edCompName changes I n t e r f ace I ns t ance1 : : Or i g i na l I n t e r f aceType1 => New I n t e r f aceType1.

Specialization of inherited connections is supported by the statement:

newT i e1 , newT i e2 r ep l ac i ng o r i g i na l T i e subsume subcomp I ns t Name : i n t I ns t Name t o i n t I ns t Name exemp t : subcomp I ns t Name : i n t I ns t Name.

Other ADLs do not specify inheritance between descriptors, they usually use inheritance uniquely for creation of sub-interfaces. In UML, the component entity inherits from the structured class entity and therefore they can participate in generalization relationship in the same way as classes do.

Composition as a reuse mechanism

In ComponentJ [START_REF] Seco | Componentj: A component-based programming language with dynamic reconfiguration[END_REF] the authors state that all reuse schemes are achieved using sole composition. By nature, the composition concept allows only black-box reuse. Therefore it

!"#$%&' $()*+&! ,(-(.$/"0' !"#$%&' !"#$%&' !"#$!%%&'()*+'
,"-"()*+' The "lost of initial receiver" problem, when composition and invocations forwarding are used. The context pseudo variable se l f does not refer to the original receiver of service invocation when delegations are used. The m2 ( ) service of descriptor Ch i l d is never called cannot be used when an internal architecture of a descriptor needs to be reused. For example the reuse of a descriptor's internal architecture shown in Figure 3 cannot be performed with composition.

Achieving behavioral inheritance by using composition and message forwarding raises various issues including the well known "lost of initial receiver" problem [START_REF] Lieberman | Using Prototypical Objects to Implement Shared Behavior in Object Oriented Systems[END_REF]. The context reference se l f (or t h i s in some languages) does not refer to the original receiver of service invocation when forwarding is used. The problem and its solution are illustrated in Figure 4, where the m2 ( ) service of descriptor Ch i l d is never called.

ComponentJ proposal describes an operational solution to that problem. The solution is based on a connexion of the "self" port of the composed-component to the default provided port of the composite and on the service invocations forwarding from the composite to the composed-component (see the dashed arrow in the bottom of Figure 4).

The solution is operational but we argue that inheritance is preferred because it: (1) enables abstract description and conceptual description; (2) does not increases the complexity of the system and therefore preserve code maintainability of large systems, where hierarchical concept modeling is used; (3) copy the structure of an external contract of a super-descriptor (i.e. declaration of provided and required ports) automatically to sub-descriptors.

Conclusions

In this paper, we have proposed an original descriptorbased inheritance system for a component-based programming language taking into account in the same context the architecture modeling and coding aspects of components. We have motivated and described concrete solutions for creating new component descriptors by extending and specializing existing ones and for extending or specializing all key primary aspects of component modeling and programming: ports declarations, composition (or connection) architectures, services declarations and definitions. These solutions are implemented and can be tested with our prototype (http://www.lirmm.fr/∼spacek/compo/) implemented in Pharo Smalltalk [START_REF] Black | Pharo by Example[END_REF].

Among the various possible specialization options for inheritance, we have applied in our context the covariantoriented one, by allowing to add requirements on a subdescriptor, that promotes expressive power and reuse. We have implemented supports to help programmer achieving substitutions. Other well-known approachs can of course be considered. Besides, we have not yet discussed the multipleinheritance option. Inheritance in component-based development is useful for both "development-for-reuse" and "development-by-reuse". It helps, in combination with other composition techniques, in effortless production of new offthe-shelf components or new applications embedding complex components architectures.

There are various prospective for this work. The first one is to obviously to gain more experience on using inheritance in this context and to consider its use in designing Component Design Patterns [START_REF] Arnout | From patterns to components[END_REF]. Beside, our inheritance extension is currently used to build a reflective version of COMPO, the primary goal of which is, through a first-class representation of descriptors, components, ports and architecture, to write model-driven verifications or transformations of COMPO component-based applications in COMPO itself. We are applying it to constraint-based architecture verification, extending our earlier works [START_REF] Tibermacine | A family of languages for architecture constraint specification[END_REF][START_REF] Tibermacine | Component-based specification of software architecture constraints[END_REF] towards constraintcomponents hierarchies.

  c o m p o n e n t d e s c r i p t o r C o n t r o l a b l e F r o n t E n d e x t e n d s F r o n t E n d { p r o v i d e s { c o n t r o l : { s t a r t ( ) ; i s R u n n i n g ( ) ; s t o p ( ) } } a r c h i t e c t u r e { d e l e g a t e c o n t r o l t o r R@ . c o n t r o l ; } } Listing 3. The Con t r o l ab l eF r on t End descriptor. Extends the F r on t End descriptor with a new provided port named con t r o l . c o m p o n e n t d e s c r i p t o r R e s t a r t a b l e F r o n t E n d e x t e n d s C o n t r o l a b l e F r o n t E n d { p r o v i d e s { c o n t r o l : { r e s t a r t ( ) ; } } s e r v i c e r e s t a r t ( ) { r R s t o p . r R s t a r t } s e r v i c e i s L i s t e n i n g ( ) { s u p e r i s L i s t e n i n g i f T r u e : [ ^0 ] i f F a l s e : [ ^1 ] } }

Figure 2 .

 2 Figure 2. An example of an extension and specialization of required ports. Grayed parts of the figure illustrate inherited parts.

c o m p

  o n e n t d e s c r i p t o r R a n d o m R e q u e s t s Q u e u e e x t e n d s R e q u e s t s Q u e u e { r e q u i r e s { r a n d o m G e n : { g e t N e x t I n t ( ) ; } . . . } c o m p o n e n t d e s c r i p t o r R a n d o m i z e r { p r o v i d e s { g e n e r a t o r : { g e t N e x t I n t ( ) ; } . . . } s e r v e r : = Q u e u e d S e r v e r n e w . a s s o c P a i r : = ' r a n d o mG e n ' -> ( R a n d o m i z e r n e w ) . r a n d o m Q u e u e : = R a n d o m R e q u e s t s Q u e u e n e wC o m p a t i b l e : ( A r r a y w i t h : a s s o c P a i r ) . s e r v e r r e c o n n e c t : ' q u e u e ' t o : r a n d o m Q u e u e .

Figure 3 .

 3 Figure 3. Dynamic substitution with a sub-descriptor having additional required port may lead to unsatisfied requirement in the architecture. Grayed parts of the figure illustrate inherited parts.

  c o m p o n e n t d e s c r i p t o r Q u e u e d H T T P S e r v e r e x t e n d s H T T P S e r v e r {

Figure 4 .

 4 Figure 4. The "lost of initial receiver" problem, when composition and invocations forwarding are used. The context pseudo variable se l f does not refer to the original receiver of service invocation when delegations are used. The m2 ( ) service of descriptor Ch i l d is never called

Table 1 .

 1 Comparative table of inheritance in selected CB-PLs and in Fractal and SOFA models

	5. Related works
				CBPLs			ADLs
	criterium/model ACOEL ArchJava CLIC CompJava COMPO Fractal SOFA
	Structure inheritance yes	yes	yes	yes	yes	yes	yes
	Behavior inheritance yes	yes	yes	no	yes	no	no
	Extensions
	Provided ports	yes	yes	no	yes	yes	yes	yes
	Required ports	yes	yes	yes	no	yes	yes	yes
	Internal components yes	yes	yes	no	yes	yes	yes
	Connections	yes	yes	yes	no	yes	yes	yes
	Specialization
	Provided ports	yes	no	yes	yes	yes	yes	yes
	Required ports	yes	no	yes	no	yes	yes	no
	Internal components	no	no	yes	no	yes	yes	yes
	Connections	no	no	yes	no	yes	yes	yes
	Substitution:
	restrictive	yes	yes	yes	yes	yes	yes	yes
	with addit.reqs.	no	no	yes	no	yes	no	no

An Inheritance System for Structural & Behavioral Reuse in Component-based Software Programming 1 2012/5/4

Although delegation in prototype-based language is something different, we will use for message redirection the terms "message delegation" and corollary "delegation connector" and "service invocation delegation" with semantics as specified in UML[START_REF] Omg | UML 2.4.1 superstructure specification[END_REF]

An Inheritance System for Structural & Behavioral Reuse in Component-based Software Programming 4 2012/5/4

the instance is the internal component connected to the internal required port queue of an instance of the QueuedSe r ve r descriptor shown in Fig-

ure 3 and Listing 6.

An Inheritance System for Structural & Behavioral Reuse in Component-based Software Programming 7 2012/5/4

An Inheritance System for Structural & Behavioral Reuse in Component-based Software Programming 8 2012/5/4

An Inheritance System for Structural & Behavioral Reuse in Component-based Software Programming 9 2012/5/4

An Inheritance System for Structural & Behavioral Reuse in Component-based Software Programming 10 2012/5/4


M J Fadili

J.-L Starck

M Elad

D L Donoho

MCALab: Reproducible Research in Signal and Image Decomposition and Inpainting

Keywords: Reproducible research, sparse representations, signal and image decomposition, inpainting, Morphological Component Analysis

Morphological Component Analysis (MCA) of signals and images is an ambitious and important goal in signal processing; successful methods for MCA have many far-reaching applications in science and technology. Because MCA is related to solving underdetermined systems of linear equations it might also be considered, by some, to be problematic or even intractable. Reproducible research is essential to to give such a concept a firm scientific foundation and broad base of trusted results. MCALab has been developed to demonstrate key concepts of MCA and make them available to interested researchers and technologists. MCALab is a library of Matlab routines that implement the decomposition and inpainting algorithms that we previously proposed in [1], [2], [3], [4]. The MCALab package provides the research community with open source tools for sparse decomposition and inpainting and is made available for anonymous download over the Internet. It contains a variety of scripts to reproduce the figures in our own articles, as well as other exploratory examples not included in the papers. One can also run the same experiments on one's own data or tune the parameters by simply modifying the scripts. The MCALab is under continuing development by the authors;

I. INTRODUCTION

A. Reproducible research

Reproducibility is at the heart of scientific methodology and all successful technology development. In theoretical disciplines, the gold standard has been set by mathematics, where formal proof in principle allows anyone to reproduce the cognitive steps leading to verification of a theorem. In experimental disciplines, such as biology, physics or chemistry, for a result to be well-established, particular attention is paid to experiment replication. Of course, a necessary condition to truthfully replicate the experiment is that the paper has to describe it with enough detail to allow another group to mimic it.

Computational science is a much younger field than mathematics, but already of great importance for human welfare; however reproducibility has not yet become a rigorously-adhered to notion. The slogan 'reproducible research' is of relatively recent coinage, and tries to create a real gold standard for computational reproducibility; it recognizes that the real outcome of a research project is not the published article, but rather the entire environment used to reproduce the results presented in the paper, including data, software, documentation, etc [START_REF] Schwab | Making scientific computations reproducible[END_REF]. A closely-related concept to reproducible research is computational provenance. In scientific experiments, provenance helps interpret and understand results by examining the sequence of steps that led to a result. In a sense, potential uses of provenance go beyond reproducibility; see May/June 2008 CiSE issue on this subject [START_REF] Silva | Computational provenance[END_REF].

Inspired by Clearbout, Donoho in the early 1990's began to practice reproducible research in computational harmonic analysis within the now-proliferating quantitative programming environment Matlab; see the review paper [START_REF] Donoho | Reproducible research in computational harmonic analysis[END_REF] in the January/February 2009 CiSE special issue on reproducible research. In the signal processing community, the interest in reproducible research was revitalized in [START_REF] Barni | Pushing science into signal processing[END_REF]. At one of the major signal processing conferences, ICASSP 2007, a special session was entirely devoted to reproducible signal processing research.

B. This paper

In this paper, reproducible research is discussed in the context of sparse-representation-based signal/image decomposition and inpainting. We introduce MCALab, a library of Matlab routines that implements the algorithms proposed by the authors in [START_REF]Redundant multiscale transforms and their application for morphological component analysis[END_REF], [START_REF] Elad | Simultaneous cartoon and texture image inpainting[END_REF], [START_REF] Fadili | Inpainting and zooming using sparse representations[END_REF] for signal/image decomposition and inpainting. The library provides the research community with open source tools for sparse decomposition and inpainting, and may be used to reproduce the figures in this paper and to redo those figures with variations in the parameters.

Although Mathematics has it million-dollar problems, in the form of Clay Math Prizes, there are several Billion Dollar problems in signal and image processing. Famous ones include the phase problem (loss of information from a physical measurement) and the cocktail party problem (separate one sound from a mixture of other recorded sounds and background noises at a cocktail party). The "Billion Dollar" adjective refers to the enormous significance of these problems in the world economy if these problems were solved, as well as the extreme intellectual 'kick' a solution would necessarily entail. These signal processing problems seem to be intractable according to orthodox arguments based on rigorous mathematics, and yet they keep cropping up in problem after problem.

One such fundamental problem involves decomposing a signal or image into superposed contributions from different sources; think of symphonic music which may involve superpositions of acoustic signals generated by many different instruments -and imagine the problem of separating these contributions. More abstractly, we can see many forms of media content that are superpositions of contributions from different 'content types', and we can imagine wanting to separate out the contributions from each. We can easily see a fundamental problem; for example an n-pixel image created by superposing K different types offers us n data (the pixel values) but there may be as many as n • K unknowns (the contribution of each content type to each pixel).

Traditional mathematical reasoning, in fact the fundamental theorem of linear algebra, tells us not to attempt this: there are more unknowns than equations. On the other hand, if we have prior information about the underlying object, there are some rigorous results showing that such separation might be possible -using special techniques. We are left with the situation of grounds for both hope and skepticism.

The idea to morphologically decompose a signal into its building blocks is an important problem in signal and image processing. An interesting and complicated image content separation problem is the one targeting decomposition of an image to texture and piece-wise-smooth (cartoon) parts. Since the pioneering contribution of the French mathematician Yves Meyer [START_REF] Meyer | Oscillating patterns in image processing and in some nonlinear evolution equations[END_REF], we have witnessed a flurry of research activity in this application field. Successful methods for signal or image separation can be applied in a broad range of areas in science and technology including biomedical engineering, medical imaging, speech processing, astronomical imaging, remote sensing, communication systems, etc.

In [START_REF] Starck | Image decomposition via the combination of sparse representatntions and variational approach[END_REF], [START_REF]Redundant multiscale transforms and their application for morphological component analysis[END_REF] a novel decomposition method -Morphological Component Analysis (MCA) -based on sparse representation of signals. MCA assumes that each signal is the linear mixture of several layers, the socalled Morphological Components, that are morphologically distinct, e.g. sines and bumps. The success of this method relies on the assumption that for every signal atomic behavior to be separated, there exists a dictionary of atoms that enables its construction using a sparse representation. It is then assumed that each morphological component is sparsely represented in a specific transform domain. And when all transforms (each one attached to a morphological component) are amalgamated in one dictionary, each one must lead to sparse representation over the part of the signal it is serving, while being highly inefficient in representing the other content in the mixture. If such dictionaries are identified, the use of a pursuit algorithm searching for the sparsest representation leads to the desired separation. MCA is capable of creating atomic sparse representations containing as a by-product a decoupling of the signal content. In [START_REF] Elad | Simultaneous cartoon and texture image inpainting[END_REF], MCA has been extended to simultaneous texture and cartoon images inpainting. In [START_REF] Fadili | Inpainting and zooming using sparse representations[END_REF], the authors formalized the inpainting problem as a missing data estimation problem.

II. THEORY AND ALGORITHMS

Before describing of the MCALab library, let's first explain the terminology used throughout the paper, review the main theoretical concepts and give the gist of the algorithms.

A. Terminology

Atom: An atom is an elementary signal-representing template. Examples might include sinusoids, monomials, wavelets, Gaussians. Using a collection of atoms as building blocks, one can construct more complex waveforms by linear superposition.

Dictionary: A dictionary Φ is an indexed collection of atoms (φ γ ) γ∈Γ , where Γ is a countable set.

The interpretation of the index γ depends on the dictionary; frequency for the Fourier dictionary (i.e. sinusoids), position for the Dirac dictionary (aka standard unit vector basis, or kronecker basis), position-scale for the wavelet dictionary, translation-duration-frequency for cosine packets, position-scale-orientation for the curvelet dictionary in two dimensions. In discrete-time finite-length signal processing, a dictionary can be viewed as a matrix whose columns are the atoms, and the atoms are considered as column vectors. When the dictionary has more columns than rows, it is called overcomplete or redundant. We are mainly interested here in overcomplete dictionaries. The overcomplete case is the setting where the signal x = Φα amounts to an underdetermined system of linear equations.

Analysis and synthesis: Given a dictionary, one has to distinguish between analysis and synthesis operations. Analysis is the operation which associates to each signal x a vector of coefficients α attached to atom: α = Φ T x. Synthesis is the operation of reconstructing x by superposing atoms: x = Φα. Analysis and synthesis are very different linear operations. In the overcomplete case, Φ is not invertible and the reconstruction is not unique; see also subsection II-B for further details.

Morphological component: For a given n-sample signal or image x, we assume that it consists of a

sum of K signals or images (x k ) k=1,••• ,K , x = K k=1 x k , having different morphologies. Each x k is called a morphological component.
Inpainting: Inpainting is to restore missing image information based upon the still available (observed) cues from destroyed, occluded or deliberately masked subregions of the signal or image. Roughly speaking, inpainting is an interpolation of missing or occluded data.

B. Fast implicit transforms and dictionaries

Owing to recent advances in modern harmonic analysis, many novel representations, including the wavelet transform, curvelet, contourlet, steerable or complex wavelet pyramids, were shown to be very effective in sparsely representing certain kinds of signals and images. For decomposition purposes, the dictionary will be built by taking the union of one or several (sufficiently incoherent) transforms, generally each corresponding to an orthogonal basis or a tight frame.

From a practical point of view, given a signal x, we will need to compute its forward (or analysis) transform by multiplying it by Φ T . We also need to reconstruct any signal from its coefficients α. In fact, the matrix Φ and its adjoint Φ T corresponding to each transform are never explicitly constructed in memory. Rather they are implemented as fast implicit analysis and synthesis operators taking a signal vector x, and returning Φ T x = Tx (e.g. Fourier or wavelet transforms), or taking a coefficient vector α and returning Φα (e.g. inverse Fourier or wavelet transforms).

C. Signal and Image decomposition

Suppose that the n-sample signal or image x is the linear superposition of K morphological components.

The MCA framework aims at recovering the components (x k ) k=1,••• ,K from their observed linear mixture as illustrated by Fig. 1. This is obviously an ill-posed inverse problem. MCA assumes that a dictionary can be built by amalgamating several transforms (Φ 1 , • • • , Φ K ) such that, for each k, the representation α k of x k in Φ k is sparse and not, or at least not as sparse, in other Φ l , l = k. In other words, the sub-dictionaries

(Φ 1 , • • • , Φ K )
must be mutually incoherent. Thus, the dictionary Φ k plays a role of a discriminant between content types, preferring the component x k over the other parts.

Choosing an appropriate dictionary is then a key step towards a good sparse decomposition and inpainting. Thus, to represent efficiently isotropic structures, a qualifying choice is the wavelet transform [START_REF] Mallat | A Wavelet Tour of Signal Processing[END_REF]. The curvelet system [START_REF] Candès | Fast discrete curvelet transforms[END_REF] is a very good candidate for representing piecewise smooth (C 2 ) images away from C 2 contours. The ridgelet transform [START_REF] Candès | Ridgelets: the key to high dimensional intermittency?[END_REF] has been shown to be very effective for representing global lines in an image. The local DCT (discrete cosine transform) [START_REF] Mallat | A Wavelet Tour of Signal Processing[END_REF] is well suited to represent locally stationary textures. These transforms are also computationally tractable particularly in large-scale applications, and as stated above, never explicitly implement Φ and T. The associated implicit fast analysis and synthesis operators have typical complexities of O(n), with n the number of samples or pixels (e.g. orthogonal or bi-orthogonal wavelet transform) or O(n log n) (e.g. ridgelet, curvelet, local DCT transforms).

By definition, the augmented dictionary

Φ = [Φ 1 • • • Φ K ] will provide an overcomplete representation of
x. Again, because there are more unknowns than equations, the system x = Φα is underdetermined. Sparsity can be used to find a unique solution, in some idealized cases; see the comprehensive review paper [START_REF] Bruckstein | From sparse solutions of systems of equations to sparse modeling of signals and images[END_REF]. In [START_REF] Starck | Image decomposition via the combination of sparse representatntions and variational approach[END_REF], [START_REF]Redundant multiscale transforms and their application for morphological component analysis[END_REF], it was proposed to solve this underdetermined system of equations and estimate the morphological components (x k ) k=1,••• ,K by solving the following constrained optimization problem: where α p p = i |α(i)| p is the penalty quantifying sparsity (the most interesting regime is for 0 ≤ p ≤ 1), and α 0 = lim p→0 α p p is the ℓ 0 pseudo-norm, i.e. the number of nonzero components. The constraint in this optimization problem accounts for the presence of noise and model imperfection. If there is no noise and the linear superposition model is exact (σ = 0), an equality constraint can be substituted for the inequality constraint. This formulation is flexible enough to incorporate external forces that direct the morphological components to better suite their expected content, these forces will fine tune the separation process to achieve its task. As an example for such successful external force, [START_REF] Starck | Image decomposition via the combination of sparse representatntions and variational approach[END_REF] proposed to add a Total Variation (TV) penalty to the cartoon part in order to direct this component to fit the piecewise-smooth model. This leads to

min x1,••• ,xK K k=1 Φ T k x k p p , such that x - K k=1 x k 2 ≤ σ , (1)
min x1,••• ,xK K k=1 Φ T k x k p p + γ x s TV , such that x - K k=1 x k 2 ≤ σ , (2)
where s indexes the piecewise-smooth (cartoon) part, and γ the TV regularization parameter.

For the sake of completeness, the MCA algorithm proposed in [START_REF] Starck | Image decomposition via the combination of sparse representatntions and variational approach[END_REF] is summarized in Algorithm 1 below. It relies on an iterative thresholding scheme with varying threshold. In Algorithm 1, TH λ (α) denotes componentwise thresholding with threshold λ, hard thresholding (p = 0 in (2)) or soft-thresholding (p = 1 in (2)). As far as the thresholding decreasing strategy is concerned, there are several alternatives. For example, in [START_REF] Starck | Image decomposition via the combination of sparse representatntions and variational approach[END_REF],

[2], linear and exponential decrease were advocated. In [START_REF] Bobin | Morphological component analysis: An adaptive thresholding strategy[END_REF], a more elaborated strategy coined MOM (for mean-of-max) was proposed. In this paper and version 1.1.0 of MCALab toolbox, only linear and exponential decrease are implemented.

Algorithm 1 MCA component separation algorithm.

Task: Signal/image decomposition, solve [START_REF]Redundant multiscale transforms and their application for morphological component analysis[END_REF].

Parameters: The signal/image x, the dictionary Φ = [Φ 1 • • • Φ K ],
number of iterations N iter , γ and index of the cartoon part, stopping threshold λ min , threshold update schedule. Initialization:

• Initial solution x (0) k = 0, ∀k. • Initial residual r (0) = x. • Initial threshold: let k ⋆ = max k Φ T k x ∞ , set λ (0) = max k =k ⋆ Φ T k x ∞ . Main iteration: For t = 1 to N iter • For k = 1 to K, -Compute marginal residuals r (t) k = r (t) + x k . -Update k-th component coefficients by thresholding α (t) k = TH λ (t) Φ T k r (t) k . -Update k-th component x (t) k = Φ k α (t)
k . -If k is the cartoon part and γ = 0, apply TV penalty to

x (t) k . • Update the residuals r (t+1) = x -K k=1 x (t)
k .

• Update the threshold λ (t+1) according to the given schedule.

• If λ (t+1) ≤ λ min then stop. End iteration Output: Morphological components x (Niter) k k=1,••• ,K .
As suggested in [START_REF] Starck | Image decomposition via the combination of sparse representatntions and variational approach[END_REF], an approximation of the TV regularization is implemented in MCALab by softthresholding the undecimated Haar wavelet coefficients with threshold γ.

a) Handling bounded noise: MCA handles in a natural way data perturbed by additive noise ε with bounded variance σ 2 ε = Var[ε] < +∞. MCA is an iterative coarse-to-fine (in terms of coefficient amplitude in the dictionary) procedure and bounded noise can be handled just by stopping iterating when the residual is at the noise level. Assuming that the noise variance σ 2 ε is known, the algorithm may be stopped at iteration t when the ℓ 2 -norm of the residual satisfies r (t) 2 ≤ √ nσ ε . Alternatively, one may use a strategy reminiscent of denoising methods, by taking λ min = τ σ ε where τ is a constant, typically between 3 and 4.

D. Signal and Image inpainting

Let the original signal/image be defined on a bounded domain Ω. Suppose we partially observe a signal/image x on a compact domain

Ω o ⊂ Ω, n o = Card (Ω o )
, where some samples are missing (those indexed by Ω \ Ω o ). By "mask" M we mean the diagonal n × n matrix where the observed samples are indicated by ones and the missing ones by zeros.

1) Algorithm of Elad et al. [3]:

In [START_REF] Elad | Simultaneous cartoon and texture image inpainting[END_REF], the authors describe an inpainting algorithm which is a direct extension of MCA that is capable of filling in holes in images that are superposition of a texture and cartoon layers. Thus, (2) can be extended to incorporate missing data through the mask M by minimizing

min x1,••• ,xK K k=1 Φ T k x k p p + γ x s TV , such that x -M K k=1 x k 2 ≤ σ . (3)
In our approach to solving this optimization problem, we only need to adapt slightly the MCA Algorithm 1, modifying the residual update rule to

r (t+1) = x -M K k=1 x (t)
k to account for the masking matrix M. The other steps of the algorithm remain unchanged. See [START_REF] Elad | Simultaneous cartoon and texture image inpainting[END_REF] for more details.

2) Algorithm of Fadili et al. [START_REF] Fadili | Inpainting and zooming using sparse representations[END_REF]: When taking p = 1 and the TV-regularization term is dropped in (3), Fadili et al. [START_REF] Fadili | Inpainting and zooming using sparse representations[END_REF] formalized the inpainting problem as a missing data estimation problem. They formulated the problem as a maximum penalized likelihood estimator with missing data and sparsity-promoting penalties.

They carefully characterized it and solved it using tools from non-smooth convex optimization theory. A chief advantage of this algorithm is its ability to estimate the noise variance. Let's denote the relaxation parameter

0 < µ < 2/( k Φ k 2 2 )
, where Φ k 2 2 corresponds to the largest frame bound associated to Φ k . For a self-contained exposition, the main inpainting method of [START_REF] Fadili | Inpainting and zooming using sparse representations[END_REF] is summarized in Algorithm 2 below.

Algorithm 2 EM-inspired inpainting algorithm. Task: Signal/image inpainting. Parameters: Observed masked image x, the mask M, the dictionary

Φ = [Φ 1 • • • Φ K ], regularization parameter λ, initial σ (0) ǫ , convergence tolerance δ. Initialization: Initial solution α (0) k = 0, ∀k.

Main iteration: Repeat

• Update the residual r (t) = x -MΦα (t) .

• Update the coefficients α (t) α (t+1) = SoftThreshold λµ α (t) + µΦ T r (t) .

• If desired, update σ 2 (t+1) ε according to

σ 2 (t+1) ε = 1 n i∈Ωo x(i) -Φα (t) (i) 2 + (n -n o )σ 2 (t) ε . Until α (t+1) -α (t) 2 ≤ δ. Output: Inpainted image x = Φα (t) = k Φ k α (t) k .
Other variants are described in [START_REF] Fadili | Inpainting and zooming using sparse representations[END_REF] and the interested reader may refer to that paper for further details.

Let's conclude this subsection by noting some differences and similarities between the above two inpainting algorithms:

• Target: in the formulation of [START_REF] Elad | Simultaneous cartoon and texture image inpainting[END_REF], the targets are the morphological components x k , component separation is a by-product of the inpainting process. While in [START_REF] Fadili | Inpainting and zooming using sparse representations[END_REF] the problem is optimized with respect to the coefficients α k . This distinction obviously disappears when Φ is an orthobasis.

• Parameters: in the MCA-based inpainting [START_REF] Elad | Simultaneous cartoon and texture image inpainting[END_REF], the user provides the algorithm with a threshold-lowering schedule and a stopping threshold λ min , while in the second version [START_REF] Fadili | Inpainting and zooming using sparse representations[END_REF], the user must give a fixed regularization parameter λ. In practice, it may be more difficult to choose λ than the stopping threshold.

• Noise: both algorithms handle the presence of noise. The second formulation is able to estimate the noise variance along with inpainting.

• Optimization algorithms: despite apparent similarities, the two formulations use different optimization frameworks. MCA is an heuristic algorithm, formed by hybridizing matching pursuit with block-coordinate relaxation. The formulation of [START_REF] Fadili | Inpainting and zooming using sparse representations[END_REF] uses an iterative thresholding proximal iteration with a rigorous convergence analysis guaranteed when p ≥ 1.

III. MCALAB ARCHITECTURE

A. The MCALab distribution

MCALab is a library of Matlab routines that implements the algorithms described here-above for sig-

B. MCALab dependencies

As stated above, MCALab requires implementation of forward and inverse transforms. It turns out that many of them (orthogonal wavelet transform, discrete cosine and sine transforms, etc) are already implemented in WaveLab [START_REF] Buckheit | Wavelab and reproducible research[END_REF]. We then recommend that the users download and install WaveLab for MCALab to work properly.

For the user's convenience, MCALab also incorporates software for two other transforms not distributed with WaveLab. For instance the wrapping version of the Fast Discrete Curvelet Transform (FDCT) implemented in CurveLab [START_REF] Candès | Fast discrete curvelet transforms[END_REF], [START_REF] Curvelab | [END_REF], and the undecimated discrete wavelet transform (UDWT) implemented in RWT [START_REF]Rice wavelet toolbox[END_REF]. Note that the FDCT Matlab functions fdct wrapping.m and ifdct wrapping.m (not the Matlab Mex files) have been slightly modified to match our dictionary data structure, and to implement curvelets at the finest scale. We strongly recommend that the user downloads our modified

C. MCALab metadata generation

MCALab also generates metadata that indicate many information that facilitate reproducibility and reusability. This metadata is generated as a Matlab structure object with fields indicating (see Fig. 3):

• The version of Matlab and machine architecture.

• The version of third-party libraries that were used for the generation of a given result. For example, in this paper we used WaveLab 802, CurveLab 2.1.1 and RWT 1.2.

• All the options from MCALab including its version (1.1.0 in this paper), the task (decomposition or inpainting), parameters, inputs/outputs and dictionary description.

When To encourage users to reproduce our results from the metadata structure, we have also written an MCALab function firefrommetadata.m that is able to reproduce the results from metadata previously stored, together with as little extra information as possible. For the user convenience, MCALab includes two test scripts in MCALab110/xxx-D/Scripts that exemplify the use of firefrommetadata.m on some 1D

and 2D examples.

D. Documentation

MCALab is documented and each function in MCALab has help documentation. The README and INSTALL files provide some guidelines which will help you access and install the software on your machine and get started in exploring the resources contained in the MCALab package. The reader may also look at the MCALab webpage which contains the following information: authors with links to their websites, abstract of this paper, full references of the papers MCALab is concerned with, a zipped archive of MCALab package, and an email address for remarks and bug report. MCALab is under continuing development by the authors. We welcome your feedback and suggestions for further enhancements, and any contributions you might make.

E. Dictionaries and data structures

The functions in xxx-D/Dictionary subdirectory provide fast implicit analysis and synthesis operators for all dictionaries implemented in MCALab. It is worth noting that except for the FDCT with the wrapping implementation [START_REF] Candès | Fast discrete curvelet transforms[END_REF], all dictionaries provided in MCALab are normalized such that atoms have unit ℓ 2 -norm.

The FDCT implements a non-normalized Parseval tight frame. Thus, a simple rule to compute the ℓ 2 -norm of the atoms is √ redundancy of the frame. Normalization has an important impact on the thresholding step involved in the decomposition/inpainting engines. The thresholding functions coded in MCALab take care of these normalization issues for the dictionaries it implements.

The data structure as well as the routines are inspired from those of Atomizer [START_REF] Chen | About atomizer[END_REF]. The dictionaries are implemented in an object-oriented way. The top level routines are FastLA and FastLS. Each transform has a fast analysis and a fast synthesis function named respectively FasNAMEOFTRANSFORMAnalysis and FasNAMEOFTRANSFORMSynthesis. Four arguments (NameOfDict, par1, par2, par3) are used to specify a dictionary. The meaning of each parameter is explained in the corresponding routine. Each

FasNAMEOFTRANSFORMAnalysis computes the transform coefficients (i.e. application of Φ T ) of an image or a signal and stores them in a structure array. We also define the List data structure and corresponding functions, which allow to create and easily manipulate overcomplete merged dictionaries. The interested user can easily implement its own dictionary associated to a new transform following the above development rules.

F. Decomposition and inpainting engines

The routines in this directory perform either signal/image decomposition and inpainting using the MCAbased Algorithm 1, or signal and image inpainting using Algorithm 2 described above. This set of routines are for dictionaries with fast implicit operators. They are also designed so as to return a metadata object that can be saved or exported in HTML format to facilitate result reproducibility.

G. Scripts and GUI

The for each morphological component. The main window is invoked via the command MCA1Demo (signals)

or MCA2Demo (images). Upon initialization, one main window will appear with four plots, a menu and an interactive area on the right. Two additional pull-down menus on the top-bar are specific to MCALab GUI.

They allow to load data variables from the Matlab workspace. Thus, prior to using the GUI, the signals, images or masks of interest must be first read from disk and loaded to the workspace using any Matlab input data reading routine. Note that if your goal is to decompose and not to inpaint, it is sufficient to create a dummy variable of ones of the same size as the data. By default, the GUI assumes the trivial mask (all ones).

IV. REPRODUCIBLE EXPERIMENTS

Data description, dictionaries and algorithm parameters used in the experiments of this section are summarized in Table I and Table II.

A. 1D examples 1) Bumps + Local cosines:

The synthetic signal of Fig. 4(a) (dashed line) is a composite of two Gaussian bumps with different scales and two local cosine waves. In this synthetic signal, we know the ground truth decomposition. We also added white Gaussian noise with σ ε = 0.429 (PSNR=20dB). Based on the morphological content of this signal, we decomposed and denoised it using an overcomplete dictionary containing the local DCT and the undecimated wavelet transform (see Table I for the dictionary details). The standard deviation σ ε was not supplied but estimated from the noisy data by the algorithm using the MAD estimator [START_REF] Donoho | Ideal spatial adaptation via wavelet shrinkage[END_REF].

The results are displayed in Fig. 4(b)-(d). In (c) (resp. (d)) we can see the original (dashed line) and recovered (solid line) locally oscillating part (resp. localized bumps) recovered by MCA. The co-addition of both recovered components is plotted with a continuous line in Fig. 4(b) superimposed on the original signal (dashed line).

2) TwinSine + Diracs: The synthetic signal of Fig. 5(a) (dashed line) consists of three randomly located spikes and the TwinSine signal: two cosines with frequencies separated by less than the Rayleigh Distance.

The TwinSine appears in [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF]. We analyzed this signal with an overcomplete dictionary formed by merging a four-fold overcomplete DCT and a standard (Dirac) basis. The parameters chosen for this experiment are 3) EEG-fMRI: MCA was also applied to a real signal acquired during a multi-modal neuroimaging experiment. During such an experiment, electroencephalography (EEG) and functional magnetic resonance imaging (fMRI) data are recorded synchronously for the study of the spatio-temporal dynamics of the brain activity.

However, this simultaneous acquisition of EEG and fMRI data faces a major difficulty because of currents induced by the MR magnetic fields yielding strong artifacts that generally dominate the useful EEG signal. In a continuous acquisition protocol, both modalities are able to record data. But a post-processing step for EEG artifact reduction is necessary for the EEG signal to be exploitable.

An example of such a signal 1 is depicted in in Fig. 6(a). The periods where the MR sequence is switched on are clearly visible inducing strong oscillations on the EEG signal with an amplitude 10 to 20 times higher that the expected EEG amplitude. This locally oscillating behavior is expected because of the shape of the magnetic field gradients of the MR scanner. Therefore, to get rid off of the MR component and clean the EEG signal from these artifacts, we decomposed it using an overcomplete dictionary of local DCT (for the MR 1 With courtesy of GIP Cyceron, Caen, France. part) and the UDWT (for the EEG smooth and localized component). The parameters of this experiment are detailed in Table I. The results are displayed in Fig. 6(c)-(d). As a by-product, the signal was also cleaned from measurement noise.

B. 2D examples 1) Decomposition:

Boy + Texture: In this experiment, we generated a synthetic image composed of a natural scene and a texture, where we have the ground truth parts to compare against. This image was also used in [START_REF] Starck | Image decomposition via the combination of sparse representatntions and variational approach[END_REF], [START_REF] Elad | Simultaneous cartoon and texture image inpainting[END_REF]. We I for the experiment details. used the MCA decomposition Algorithm 1 with the curvelet transform for the natural scene part, and a global DCT transform for the texture; see Table II for details. The TV regularization parameter γ was fixed to 0.1.

In this example as for the example of Barbara to be described hereafter, we got better results if the very lowfrequencies were ignored in the textured part. The reason for this is the evident coherence between the two dictionaries elements at low frequencies -both consider the low-frequency content as theirs. Fig. 7 shows the original image (addition of the texture and the natural parts), the reconstructed cartoon (natural) component and the texture part.

Barbara: We have also applied the MCA decomposition Algorithm 1 to the Barbara image. We used the curvelet transform for the cartoon part, and a local DCT transform with a smooth sine window and a window size 32 × 32 for the locally oscillating texture. The TV regularization parameter γ was set to 2. Fig. 8 displays the Barbara image, the recovered cartoon component and the reconstructed texture component.

Risers:

The goal of this experiment is to illustrate the usefulness of MCA in a real-life application such as studying the mechanical properties of composite risers used in the oil industry [START_REF] Tschumperlé | Wire structure pattern extraction and tracking from x-ray images of composite mechanisms[END_REF]. The top image of Fig. 9 displays a riser made of many layers that was recorded using a digital X-ray camera [START_REF] Tschumperlé | Wire structure pattern extraction and tracking from x-ray images of composite mechanisms[END_REF]. The riser is made of a composite material layer, a layer of steel-made fibers having opposite lay angles, and lead-made markers used as a reference to calibrate the X-ray camera. The structures of interest are the curvilinear fibers. But, the markers that appear as black isotropic structures on the image, hide the fiber structures that exist behind them. Our goal is to decompose this X-ray image into two components: one containing the curvilinear fiber structures and the other with the lead-made markers and the smooth background. Therefore, natural candidate dictionaries would be the curvelet transform for the fibers, and the UDWT for the isotropic markers and the piecewise smooth background component. The TV penalty will be added to direct the image with the lead markers to fit the piecewise smooth model with γ = 3. The image was also denoised by setting λ min = 3σ ε . Fig. 9 illustrates the separation provided by the MCA. The top row depicts the original image, the middle and bottom rows give the two components recovered by MCA. One can clearly see how it managed to get rid of the lead-made markers while preserving the curvilinear fibers structure, and even reconstructing the unobserved fibers parts that were behind the markers.

2) Inpainting:

Barbara: Fig. 10 shows the Barbara image and its inpainted results for three random masks of 20%, 50%, and 80% missing pixels. The unstructured random form of the mask makes the recovery task easier which is intuitively acceptable using a compressed sensing argument [START_REF] Candès | Near optimal signal recovery from random projections: Universal encoding strategies ?[END_REF], [START_REF] Donoho | Compressed sensing[END_REF]. Again, the dictionary contained the curvelet and local DCT transforms. The algorithm is not only able to recover the geometric part (cartoon), but particularly performs well inside the textured areas.

Lines + Gaussians: We applied the two inpainting algorithms given in Algorithm 1-Section II-D.1 and Algorithm 2-Section II-D.2 to a synthetic image which is a composite of three Gaussians and three lines, see Lena: We repeated the same experiment with Lena 512 × 512. The masked image is depicted in Fig. 12 top-right, where 80% pixels were missing, with large gaps. The dictionary contained the curvelet transform.

The parameters chosen for each algorithm are given in Table II. Despite the challenging difficulty of this example (large gaps), both inpainting algorithms performed well. They managed to recover most important details of the image that are hardly distinguishable by eye in the masked image. The visual quality is confirmed by measures of the PSNR as reported in Fig. 12.

Fig. 1 .

 1 Fig. 1. Illustration of the image decomposition problem with sparse representations.

  nal/image decomposition and inpainting. The MCALab library provides the research community with open source tools for sparse decomposition and inpainting, and may be used to reproduce the figures in this paper and to redo those figures with variations in the parameters. The library is available free of charge over the Web at the address: http://www.morphologicaldiversity.org/mcalab.html The current version of MCALab is 1.1.0. It has been successfully tested under Unix Solaris/Linux/MACOSX PPC and Intel under Matlab 6.x and 7.x. MCALab is distributed under the CECILL license [15], so that advance permission is not required for non-commercial use. The structure of the MCALab package is depicted in Fig. 2. MCALab has two main directories, one for 1D signals and the second for 2D images. Each of these directories has the same architecture and contains the following subdirectories: • Dictionaries: A directory MCALab110/xxx-D/Dictionaries containing various fast implicit analysis and synthesis transforms including those discussed in subsection II-C. • Decomposition: A directory MCALab110/xxx-D/Decomposition containing the implementation of Algorithms 1-2.• Datasets: A directory MCALab110/xxx-D/Datasets containing signal and image datasets used to illustrate decomposition and inpainting. MCALab110/One-D/Datasets also contains a Matlab function that generates many artificial signals, and reads some real signals. • DemoGUI: A directory MCALab110/xxx-D/DemoGUI containing a Graphical User-friendly Interface (GUI) to decompose and inpaint the user own data or data supplied with MCALab. -4A52-":F(2<:A"(5A9"A8-3#,-.

Fig. 2 .

 2 Fig. 2. MCALab package architecture.

Fig. 3 .

 3 Fig. 3. Example of metadata generated by MCALab in HTML for the experiment of Fig. 10. The black rectangle represents the corresponding Matlab structure of metadata object.

  makeup of /MCALab110/xxx-D/Scripts and /MCALab110/xxx-D/DemoGUI is the whole raison d'être of the MCALab toolbox. The subdirectory /MCALab110/xxx-D/Scripts contains a variety of scripts, each of which contains a sequence of commands, datasets and parameters generating some figures in our own articles, as well as other exploratory examples not included in the papers. One can also run the same experiments on his own data or tune the parameters by simply modifying the scripts. By studying these scripts one can quickly learn the practical aspects of sparse-representation-based image decomposition and inpainting, and one can learn how to use the MCALab software library. The routines in /MCALab110/xxx-D/DemoGUI implement a point-and-click GUI that allows the user to select data and masks (signals or images), and then decompose or inpaint them using MCA Algorithm 1. Only signals and images with two morphological components, hence two dictionaries, can be processed with this GUI. It is possible to select the type of dictionaries and their associated parameters par1, par2, par3

Fig. 4 .

 4 Fig. 4. Decomposing and denoising Local sines + Bumps signal. See TableIfor the experiment details.

Fig. 5 . 1 ) 1 )

 511 Fig. 5. Decomposing TwinSine + Diracs signal. See TableIfor the experiment details.

Fig. 6 .

 6 Fig.[START_REF] Silva | Computational provenance[END_REF]. Decomposing and denoising the EEG-MRI real signal. See TableIfor the experiment details.

Fig. 11

 11 Fig. 11 top-left. Based on this morphological content, the UDWT and the curvelet transforms were chosen as candidate dictionaries. The parameters chosen for each algorithm are summarized in TableII. The masked and filled-in images are portrayed in Fig.11. Both inpainting algorithm performed well, although the result of Algorithm 2 is somewhat smoother.

Fig. 9 .Fig. 10 .

 910 Fig. 9. Decomposing Risers image. See Table II for the experiment details.

  version, or at least use our fdct wrapping.m and ifdct wrapping.m. Both of these transforms are available in a version of MCALab named MCALabWithUtilities; see dashed rectangle in Fig. 2. They are in the subdirectories MCALabWithUtilities/CurveleToolbox and MCALabWithUtilities/UDWT. The user may read Contents.m in MCALabWithUtilities/ for further details. The user also is invited to read carefully the license agreement details of these transforms softwares on their respective websites prior to any use. As MCALab has external library dependencies, this legitimately poses the problem of reproducibility and sensitivity to third-party libraries. However, the dependencies are essentially on the transforms, and given our implementation of the dictionaries (see section III-E), these transforms are called as external functions from MCALab. No modification is then necessary on the MCALab code if such transforms are corrected or modified. Moreover, to robustify the behavior of MCALab to these transforms, we have tested MCALab with both WaveLab 802 and 805, and CurveLab from version 1.0, 2.0, 2.1.1 and 2.1.2 and obtained exactly the same results.

  MCALab is launched upon call of MCAPath.m, this metadata object is initialized with Matlab version, machine architecture and external libraries versions. The object is then stored in the Utils/ directory. The MCALab decomposition and inpainting routines load and add additional information to this object. Beside the resulting signals and images, the test scripts can either store this object or export it in HTML format using the MCALab function metaoptions2html.m, see the example of Fig. 3. Examples of metadata Matlab structure objects stored by the test scripts are available in the toolbox in the .mat Matlab format (version 5 for compatibility with older Matlab versions). Another interesting alternative that would be worth investigating in a future version would be to exploit the XML Publish function offered by Matlab but only available with versions 7.x and later.

TABLE I EXPERIMENTAL

 I SETUP FOR THE 1D EXAMPLES.

  Fig. 7. Decomposing Boy-Texture image. See Table II for the experiment details.

	Original Barbara	MCA Barbara
	Original Texture + Boy	Recovered MCA
	Barbara Cartoon	Barbara Texture
	Original Cartoon part	MCA Cartoon
	Original Texture	MCA Texture

Fig. 8. Decomposing Barbara image. See Table II for the experiment details.

  Table II for the experiment details.

	Original Lines + Gaussians	Masked PSNR=30.9 dB
	Inpainted EM (Alg. 2) PSNR=32 dB	Inpainted MCA (Alg.1) PSNR=40 dB

Fig. 11. Inpainting Lines + Gaussians image. See

Table II for the experiment details. Original Lena Masked PSNR=6.44 dB Inpainted EM (Alg. 2) PSNR=19.9 dB Inpainted MCA (Alg. 1) PSNR=19.9 dB Fig. 12. Inpainting Lena image. See Table II for the experiment details.

June 19, 2009 DRAFT

contributions by interested researchers.

Image