Meriem Belguidoum
email: meriem.belguidoum@enst-bretagne.fr

Fabien Dagnat
email: fabien.dagnat@enst-bretagne.fr

Thunderbird Mua

Formalization of Component Substitutability

Keywords: Component software, Safety, Substitutability, Upgrading AMAVIS.amavis PROCMAIL.AntiSpam

Component-Based Software Engineering (CBSE) is increasingly used to develop large scale software. In this context, a complex software is composed of many software components which are developed independently and which are considered as black boxes. Furthermore, they are assembled and often dependent from each other. In this setting, component upgrading is a key issue, since it enables software components to evolve. To support component upgrading, we have to deal with component dependencies which need to be expressed precisely. In this paper, we consider that component upgrade requires managing substitutability between the new and the old components. The substitutability check is based on dependency and context descriptions. It involves maintaining the availability of previously used services, while making sure that the effect of the new provided services do not disrupt the system and the context invariants are still preserved. We present here a formal definition and a verification algorithm for safe component substitutability.

Introduction

Component based software has gained recognition as the key technology for building high quality and large software. In this setting, sharing collections of components has become common practice for component oriented applications. These components are independently produced and developed by different providers and reused as black boxes making it necessary to identify component dependencies to guarantee interoperability.

According to Szyperski's definition [START_REF] Szyperski | Component Software: Beyond Object-Oriented Programming[END_REF], a component is a unit of composition with contractually specified interfaces and explicit dependencies. An interface describes the provided and the required services of a component. Software consists of the assembly of components in an architecture, by binding a required interface of one component to an offered interface of another component.

In this context, upgrading a component is difficult because this component may be used by several software applications. More generally, replacing a component C old with a component C new in a system S requires that it does not disrupt S. This property is often described as substitutability [START_REF] Brada | Specification-Based Component Substitutability and Revision Identification[END_REF].

Several techniques exist to ensure substitutability between components, see for example [START_REF] Vallecillo | Component interoperability[END_REF][START_REF] Zaremski | Specification matching of software components[END_REF]. All these approaches are built upon the substitution principle of Liskov introduced in [START_REF] Liskov | Behavioral subtyping using invariants and constraints[END_REF] in the context of object oriented programming. They use the interface type to define a subtyping relation between components and then authorize C new to replace C old only if C new is a subtype of C old . Various forms of those types exist, starting with the classical interface type [START_REF] Seco | A basic model of typed components[END_REF] and enhancing them with behavioral description such as automata for example [START_REF] Cerna | Component substituability via equivalencies of component-interaction automata[END_REF]. Some related research [START_REF] Vallecillo | Component interoperability[END_REF][START_REF] Zaremski | Specification matching of software components[END_REF] show that the resulting condition of pure subtyping ensures safety of the replacement but is too restrictive. Recent work [START_REF] Brada | Specification-Based Component Substitutability and Revision Identification[END_REF] has shown the limits of this approach and proposes a less restrictive notion of substitutability depending on the context. In this setting, C new may safely replace C old in certain systems. In fact, all interfaces not used in the context are ignored when ensuring the subtyping.

To extend our previous work on the formalization of safe component installation and deinstallation [START_REF] Belguidoum | Dependency management in software component deployment[END_REF], we tried to define contextual substitutability to build a safe replacement operation following the previously cited approaches. But it appeared that the resulting rule needs to be enhanced to reach safety. While in other work the new services provided by C new do not have to meet any requirement, in our setting they may conflict with the context requirements.

Generally, replacing a component C old by a new one C new has an effect on the context and to maintain safety, we have to check that effect will not break system invariants. In previously mentioned work, the only effect taken into account is the services that C new provides. Therefore, ensuring substitutability consist in ensuring compatibility of C new provided services with the component requirements that were previously using C old services. This compatibility can have different contract levels (syntactical, behavioral, synchronisation and quality of service) as described in [START_REF] Beugnard | Making components contract aware[END_REF]. This paper advocate adding the verification of component upgrading effects (upgrade) on the target system. In the deployment, it appears that upgrade effect must not disturb the target system. For this, we propose a substitution principle ensuring that (1) the new component still provides all the services used in the context (as usual) and that (2) new provided services do not conflict with this context (effect verification). The formalization of this substitutability enables us to provide a safe and flexible replacement operation for our deployment system.

The paper is organized as follows. Section 2 introduces our dependencies description and illustrates it with the example of a mail server in Linux GNU. In Section 3, we present our substitutability approach with a progressive refinement of substitutability definitions. Section 5 describes the substitutability checking algorithm. Section 4 illustrates some substitutability examples. Section 6 discusses related work. Finally, Section 7 concludes and discusses future work.

Dependency description

In this section, we present the precise definition of the relation between a required and a provided service, either of the same component or of two different components. Such a relation is called a dependency. Fig . 1 illustrates a simplified architecture of a mail server on a Linux system. It is composed of five components: POSTFIX, an SMTP server playing the role of a Mail Transport Agent (MTA), FETCHMAIL that recovers mails from a distant server like Pop or IMAP using a mail transport protocol, PROCMAIL, a Mail Deliver Agent (MDA) that manages received mail and enables, for example, mail to be filtered. THUNDERBIRD, a mail manager for reading and composing mail called a Mail User Agent (MUA). Finally, ORGANIZER is an inbox organizer, which allows mailing lists, web pages and users e-mails to be managed. Each component is represented in Fig. 1 by a rectangle with the required interfaces (half circles and square brackets on the left side) and the provided interfaces (black circles on the right side). Requirements in the left hand side of a component, may be of two kinds: (1) software requirements (i.e., services provided by other components), for example libraries (half-circles: lib1) or ( 2) system requirements expressed by comparison of variables with values represented by square brackets, for example requiring a certain amount of free disk space (F DS ≥ 1380Ko).

In this example 3 , the two forms of dependencies, respectively intradependencies and inter-dependencies, are represented respectively by lines inside components and links between components (like PROCMAIL and THUNDERBIRD, PROCMAIL provides MDA and THUNDERBIRD requires it). There are three main kinds of dependencies, either mandatory, optional or negative:

• a mandatory dependency (represented by a solid line) is a firm requirement.

If it is not fulfilled, installation is not possible. For example, POSTFIX needs a terminal with a specific libraries (lib1), an amount of free disk space (F DS ≥ 1380ko).

• an optional dependency (represented by a dashed line) specifies that the component may provide optional services. Such services may not be provided (if their requirements are not fulfilled) without preventing the installation. For example, POSTFIX may provide a service for scanning messages against viruses if the service amavis is available. Otherwise POSTFIX can be installed and provides the MTA service, but the service AntiV irus is not provided.

• a negative dependency (expressed by a negation) specifies a conflict forbidding installation. The conflict may be due to a service or a component. For example, as presented in Fig. 1, POSTFIX cannot be installed if the component SENDMAIL (another component providing MTA) is already installed in the target system.

Intra-dependencies are defined by the producer of the component and used to perform installation. Inter-dependencies result from installation and are used to perform deinstallation and replacement. The two notions are briefly presented below, more details on these concepts are given in [START_REF] Belguidoum | Dependency management in software component deployment[END_REF].

Intra-dependencies

The intra-dependency description language uses the concepts of dependency and predicate defined by the following grammar where s represents the name Fig. 2. Dependency graph of the mail server of Fig. 1 of a service and c the name of a component:

D ::= P ⇒ s | D • D | D # D | ? D P ::= true | P ∧ P | P ∨ P | R R ::= [v O val ] | ¬ s | ¬ c | c.s | s O::=> | ≥ | < | ≤ | = | =
The precise semantics of these operators is described in detail in [START_REF] Belguidoum | Dependency management in software component deployment[END_REF]. Intuitively, a dependency may be the conjunction • or the disjunction of two dependencies, an optional dependency ? or a simple dependency P ⇒ s specifying the requirements P of the service s. If these requirements are fulfilled the service s is available. The requirements are expressed in a first order predicate language with five conditions (R) expressing a comparison of an environment variable with a value ([v O val ]), a conflict with a service (¬ s), with a component (¬ c), the requirement of a service provided by a precise component (c.s) or any component (s). Examples of such predicates appear in Fig. 1 on the required interfaces represented in the left-hand side of a component. For exemple the dependency description of the component POSTFIX is :

([F DS ≥ 1380] ∧ (sendmail) ∧ lib ⇒ MT A)•?(Amavis ⇒ AV )

Inter-dependencies

When a component is installed in a system S, each of its requirements is fulfilled by binding it to any existing component of S satisfying the requirement. This binding is what we call an inter-dependency. It is the result of installation and is required to ensure safe deinstallation and replacement. We have chosen to represent inter-dependencies by a dependency graph (see [START_REF] Belguidoum | Dependency management in software component deployment[END_REF] for more details). A node of a dependency graph is an available service s with its provider (c.s) and an edge is a pair of nodes n 1 -→ n 2 meaning that n 2 requires n 1 . Each edge is labeled (above the arrow) by the kind of dependency, either mandatory M or optional O. Fig. 2 presents the dependency graph of the mail server of Fig. 1. We can see that some solid (resp. dashed) lines inside components in the Fig. 1 (intra-dependencies) are reflected in Fig. 2 by solid (resp. dashed) edges. For example, POSTFIX depends on lib1 which is provided by a component C1, so the used service is C1.lib1. This dependency is a mandatory one (solid edge in Fig. 2 C1.lib -→ P OST F IX.MT A). POSTFIX has also an optional dependency, it can provide an Anti virus (POSTFIX.AntiV irus) if a service amavis provided by a component (for example AMAVIS) is available. This dependency is represented in the graph by a dashed edge. The system requirements (like F DS ≥ 1380) and negative dependencies (SENDMAIL) are not represented in the graph. The inter-dependencies between components in Fig. 1 are represented in the graph as mandatory edges between services, for example the service popclient provided by FETCHMAIL is linked with service popclient required by PROCMAIL, the corresponding edge in Fig. 2 is F ET CHM AIL.popclient -→ P ROCMAIL.MDA.

What is substitutability?

In this section, we present and analyze progressively the substitutability problem, we propose definitions and rules to check the correctness and safety of substitutability. In general, two forms of compatibility between components can be defined: vertical compatibility and horizontal compatibility. The vertical compatibility is called substitutability, it expresses the requirements that allow the replacement of one component by another (C old by C new in Fig. 3). The horizontal compatibility expresses connexion between a provided service of a component and a required service of another component (C old used by C client in Fig. 3). When substituting the component C old for the component C new , we have to ensure that the component C client can use the services provided by C new as it used previously those provided by C old and the new provided services do not conflict with C client and all other client components.

Substitutability definitions

Following the current trend, we define two kinds of substitutability, one addressing substitutability in a particular context and the other independent of the context. The definitions of strict and contextual substitutability are given below and are inspired by those of Brada in [START_REF] Brada | Specification-Based Component Substitutability and Revision Identification[END_REF]. Contextual substitutability is related to the context which represents the resources and the architecture of the target system. Ideally, it could be the union of the dependencies of all components (part of the system). The resulting description of the context would be a huge logical term. Its manipulation when deciding whether to authorize a deployment operation would be difficult and expensive (in calculation). Thus, we have chosen instead a safe approximation of the context description. The context definition is presented in [START_REF] Belguidoum | Dependency management in software component deployment[END_REF]. It is summarized as follows:

Definition 3.3 (Context)
The Context is composed of (1) an environment E storing the values of environment variables (OS, disk space, etc.), (2) a set C of four-tuples (c, P s , F s , F c ) storing for each installed component c its provided services P s , forbidden services F s and forbidden components F c 4 and (3) a dependency graph G storing the dependencies (the required and the provided services of each component and the relation between them).

Component substitutability

To decide whether a component C new can substitute a component C old , it is necessary to compare what they provide and what they require. Indeed, the provided (or required) services of C new can be the same or different from those of C old . We therefore have to study all the possibilities. Fig. 4 depicts the different possible relations between the old and the new set of provided (resp. required) services:

• case 1: the set of provided (resp. required) services of C new is included in the set of provided (resp. required) services of C old ;

• case 2: the set of provided (resp. required) services of C new and C old are equal;

• case 3: the set of provided (resp. required) services of C old is included in the set of provided (resp. required) services of C new ;

• case 4: the two sets are different from each other and can have some services in common. There are four cases for provided services combining with four cases for required services leading to sixteen possibilities. To illustrate these cases, we suppose that the component C old provides the services P S 1 and P S 2 and requires the services RS 1 and RS 2 . Table 1 represents the different forms that the component C new may have, depending on its provided and required services. Each cell of the table corresponds to numerous possible components and is here represented by one possible component for illustrative purposes only.

In fact, the sixteen possible cases can be refined to table 2 below, containing eight possibilities combining only three conditions:

• ensure new requirements (NR) of C new . For example, in line 1, is RS 3 satisfied? • ensure no conflicts (NC) between the new services of C new and the system.

h h h h h h h h h h h

Requires

For example, in column 1, is P S 3 in conflict with the system?

• ensure that all previously provided services which are not provided by C new are not necessary for the system (NON). For example, in column 3, is P S 2 (previously provided by C old and not provided by C new ) necessarily used?

X X X X X X X X X X X X This table shows the different substitutability conditions on the context. The only cell corresponding to strict substitutability is the empty one. The condition is then that C new requires the same thing or less than C old and provides the same services. The seven other cells represent contextual substitutability. Necessary and sufficient conditions (NSC) for strict and contextual substitutability are defined as follows:

NSC 1 (Strict substitutability) A component C old is strictly substitutable for a component C new iff they provide the same services and C new has the same or fewer requirements than C old .

NSC 2 (Contextual substitutability)

A component C old is substitutable for a component C new in a context Ctx iff:
• all the new requirements of C new are satisfied in Ctx (NR).

• none of the new provided services is in conflict with Ctx (NC).

• none of the services provided by C old not provided by C new is used necessarily within Ctx (NON).

Compared to existing substitutability approaches, the condition (NC) is original because it enables to take into account various form of component effects on the context (potential conflicts that can occur due to the new component) and maintaining the safety of the system. In an extension of our system not presented here, we have the specification of non-functional properties. Replacing a component by another may have an impact on the system properties and therefore may be forbidden. An example of a such substitution is further discussed in Section 6.

Ensuring substitutability in our context

To ensure substitutability in our system, it is necessary to :

• determine which case is examined,

• evaluate the corresponding conditions among NR, NC and NON.

Using our dependency descriptions presented in section 2 it is easier to calculate and compare provided services than required ones. In our approach, we do not consider requirements because the conditions are described in predicate logic and it is rather complex to compare requirements for each provided service. Therefore, we check substitutability according to provided services only as follows:

(i) NR and NC: to check the new requirements (NR) and prevent new conflicts (NC), we reassess the installability condition of the new component C new . This condition ensures, on the one hand, that all the component requirements are fulfilled (NR) and, on the other hand, that the provided services are not in conflict with context (NC). Therefore, the NR and NC conditions correspond to ensuring installability as presented in [START_REF] Belguidoum | Dependency management in software component deployment[END_REF]: (Ctx C new : D new ).

(ii) NON: this condition is based on the calculation of provided services from the right-hand member of the dependencies. So, for each provided service of C old which is not provided by C new we have to check that it has no mandatory dependency (i.e., it is a leaf in the dependency graph) or it is only used (directly or indirectly) by optional services (in the graph, all paths coming from it must be optional, see definition 3.4). In fact, it corresponds to the deinstallation requirements of [START_REF] Belguidoum | Dependency management in software component deployment[END_REF].

Definition 3.4 (Mandatory dependencies (MD))

The set of mandatory dependencies (MD) of a service s provided by a component c (c.s) in a dependency graph (G) is the set of nodes which use necessarily this service. It is defined as :

MD(G, c.s) = {{c .s } ∪ MD(G, c .s ) | c.s M -→ c .s ∈ G}
The condition NON can be expressed as follows:

{(MD(G, C old .s) | s ∈ (C old .P s \ C new .P s )} = ∅
We summarize the different substitution conditions for the four cases illustrated in Fig. 4 and table 2 as follows:

• providing more (case 3): C new is installable (NR+NC);

• providing the same (case 2): C new is installable (NR);

• providing less (case 1): C new is installable (NR) and services from C old .P s \ C new .P s are not used necessarily (NON);

• different (case 4): C new is installable (NR+NC) and services from C old .P s \ C new .P s not used necessarily (NON).

How substitutability is checked?

The substitutability handled in our system is only a contextual one. We Ctx without the set of all provided services of C old and without its forbidden services and forbidden components. Then, we check whether the new component can be installed using installability rules in the new context, i.e., all C new requirements are fulfilled in Ctx and its provided services does not conflict with Ctx (the rules are described in [START_REF] Belguidoum | Dependency management in software component deployment[END_REF]). Once the installation of the new component is possible in the new context, we calculate the effect of its installation in the context from its dependency description using installation rules described in [START_REF] Belguidoum | Dependency management in software component deployment[END_REF], i.e., its provided services, forbidden services, forbidden component and the new dependency graph (it is illustrated in the diagram of the Fig. 5 by the calculation of C new .P s ). Since the set of provided services depends on the availability of services in the context, we need to use installation rules to calculate it. The two main phases of substitutability are the installability and the calculation of provided services (installation) which depend on the context description and the component dependency description (D 1 • D 2 , D 1 D 2 , or ?D). The calculation of provided services is not obvious without evaluating the dependency description in the context. Even if the component is installable the provided services depend on fulfilled dependency conditions in the context. Therefore, we present the calculation of provided services depending on the dependency descriptions (D 1 • D 2 , D 1 D 2 , or ?D):

• For D 1 • D 2 , D 1 and D 2 must be verified in Ctx , and the set of provided services is the union of the provided services of D 1 and those of D 2 . For example, considering the following description:

((C1.S 1 ⇒ S 2 ) • (S 3 ∧[F DS ≥ 10
]) ⇒ S 4 ), the installability conditions are :

• S 1 belongs to the set of provided services of C 1 and S 2 is not forbidden in the context and • S 3 belongs to the set of available services of the context, the condition [F DS ≥ 10] is verified and S 4 is not forbidden in the context. Thus, the provided services are

C.P s = {S 2 , S 4 } or ∅ • D 1 D 2 is verified if D 1 is verified in Ctx or D 2 is verified in Ctx. For exam- ple, for: ((C1.S 1 ⇒ S text ) (S 3 ∧ [F DS ≥ 10
]) ⇒ S graph ), the installability conditions are :

• S 1 belongs to the set of provided services of C 1 and S text is not forbidden in the context else • S 3 belongs to the set of available services of the context, the condition [F DS ≥ 10] is verified and S graph is not forbidden in the context. The set of provided services is C.P s = {S text } else {S graph } else ∅

• ?D is always installable, for example: ?(C1.S 1 ⇒ S 2 ), the set of provided services is

C.P s = {S 2 } if S 1 ∈ C 1 .P s and S 2 is not forbidden else ∅
Next, we compare the provided services of C old with those of C new . C old is substitutable in two cases: either the set of previously provided services which are no longer provided by C new is empty or each of these services are not necessarily used by other components in the context.

Example

Let us illustrate component substitutability by examining two substitutability scenarios. First, the new component provides fewer services. Second, the new component provides more services. The first case may happen for optimizing purposes by replacing one component by another which requires fewer resources and provides fewer services. For example, we replace THUNDERBIRD by SYLPHEED. We suppose that the service THUNDERBIRD.corrector (a spell checker) is the only service which is not provided by SYLPHEED. The system must ensure the condition NON i.e., this service is not used by another component. According to the dependency graph of the mail server represented in Fig. 2 of section 2, the service THUNDERBIRD.corrector is a leaf in the graph. Thus, THUNDERBIRD.corrector is not used by another component and NON condition is ensured. The component THUNDERBIRD can be substituted by SYLPHEED which provides fewer services if SYLPHEED is installable, i.e., its required services are available in the context. The required services here are the libraries (C6.lib6) which means the libraries lib6 provided by any component, for example C6 (see Fig. 6).

The second example addresses the substitution of a component providing Checking substitutability corresponds to ensuring the requirements of SEAMONKEY (C7.lib7, IRC.ircclient, SPELL.spell -Dict, etc.) which are different from those of THUNDERBIRD and ensuring that the additional provided services do not disrupt the context. The related dependency graph is presented in Fig. 8. Now, let's illustrate our main contribution, the two substitution examples of THUNDERBIRD presented above may not be possible even if conditions on provided services are fulfilled (C old .P s \ C new .P s = ∅ and NON). Indeed, according to the diagram of Fig. 5, we have to verify firstly the installability conditions of SEAMONKEY and SYLPHEED. One of the most important part in the installability condition is the verification of the effect of the component in the context. If we suppose that the service chat is forbidden in the context, then the condition of the installability of SEAMONKEY is not verified. Therefore the substitution is not possible before comparing provided services of each component.

Finally, we can have invariants in the context that we need to preserve. For example, we may have to preserve the security level of a system by forbidding the installation of any service that can decrease the security level of the system (like the service ftp for example). Let's suppose a component C new which provides the service ftp and someone want to replace component C old by C new . The fact that the service ftp decreases the security level will forbid the replacement of C old by C new even if it provides all necessary services and does not require too much.

Related work

The issue of component substitutability has already been addressed in literature. We mention here only those which are the closest to our work and summarize the most common approaches dealing with the substitutability problem.

In oriented object programming, the substitution principle of Liskov is a particular definition of subtype which was introduced in [START_REF] Liskov | Behavioral subtyping using invariants and constraints[END_REF]. This concept of subtype is founded on the concept of substitutability, i.e., if S is a subtype of T then we can substitute objects of the type S for objects of the type T without deteriorating the desirable properties of a program. However, although the concept of subtype is approved in [START_REF] Seco | A basic model of typed components[END_REF], the rules based on typing are rather restrictive. We therefore choose a more flexible approach that allows us to make choices according to the system and user requirements.

Substitutability is presented in [START_REF] Legond-Aubry | Assembling contracts for components[END_REF] as a relation between the types of the old and the new components. This approach is based on a contract definition which is a consequence of the definition of the component type [START_REF] Champagnoux | Typage pour des composants coopératifs[END_REF][START_REF] Champagnoux | Cooperative abstract data type : A stack exemple[END_REF]. Substitutability is based on the definition of the compatibility between the component and all the elements with which it interacts. Compatibility is defined in terms of syntactic, semantic, and pragmatic contracts for operations, interfaces, ports and components. Thus, a component A is substitutable for another component B if its compatibility with other components is preserved after the substitution and the new required properties are checked. Our work follows the same principle but it is done on the interface signature only.

The concept of substitutability in [START_REF] Brada | Specification-Based Component Substitutability and Revision Identification[END_REF] is defined for black box components. The principle is to check that the substitution of the component preserves the consistency of the preliminary configuration. The concepts of context of deployment, strict substitutability and contextual substitutability are defined. The representations of component specifications and the deployment context are based on the ENT model (Export, Needs, Ties). The definition of strict substitution is different from ours because it considers that the new component must provide at least the same thing and requires at most the same thing as the old component (generalization of the needs and specialization of the requirements). In the case of "strict" substitutability there is no check for new required interfaces since those are not supposed to exist and they are "forbidden" by the strict subtyping case. Nevertheless, new provided interfaces are allowed and therefore checked. However, in our work, the verification is done for the new requirements as well as for the new provided services without using subtyping rules. We think that the strict substitutability is not really interesting because the component needed functionalities depend on the environment in which it is used and it does not verify the effects on the context and its invariants.

Despite enhancements in substitutability specification at signature, semantics and protocol levels, we believe that these works do not take into account the effect of the component. Indeed, they do not verify potential conflicts that can occur after substitution, due to new services. Therefore, in our approach we impose more constraints on the new provided services and ensure that they do not conflict with the existing context and its invariants are preserved. For example, when we want to substitute a component which provides http with another providing http and ftp services and the system forbid non-secure services like ftp, such a substitution cannot occur. Furthermore, taking into account the potential effect of the new component on the system can be generalized. It is applied not only to conflicts but also to other kinds of effect. For example, the substitutability verification of non-functional properties needs such a mechanisms as the new component may conflicts with the system invariants. Another example of use is the resource consumption. The new component despite being functionally equivalent may not work because it consumes too much resources for the system. For this reason, we have to control the effect of the new component on the context.

Conclusion and Future work

In this work, we have presented a formalization of component substitutability. Our formalization is based on dependencies and context descriptions which are also used for installation and deinstallation phases in [START_REF] Belguidoum | Dependency management in software component deployment[END_REF]. It aims at providing a safe and flexible component upgrade. The key concept is the comparison between dependency descriptions of the new and the old component. The comparison concerns provided services and does not take into account required services. We have defined the strict and the contextual substitutability and we have concentrated only on contextual one. We have presented an analysis of different substitutability cases and summarized them into three key conditions. These conditions involve checking the installability rule of the new component (verifying requirement and ensuring that provided services will not conflict with the context of the system) and checking the effect of deinstallation of the old component using the dependency graph. A prototype implementing our proposal has been developed in Ocaml. Our objective is to ensure the safety of substitutability without being restrictive by authorizing all cases of substitutability. For example, replacing a component which has a lot of unused services with another which has fewer provided services (only those which are useful) is possible. This substitutability can also depends on a system policy or property models as described in [START_REF] Belguidoum | Dependability in software component deployment[END_REF]. We focus on ensuring the safety of the system, i.e., verifying the requirements, the effect of the substitution and preserving context invariants, component and service properties. Now, we aim to parametrize the substitutability check by policies and properties (for example, if the policy tries to optimize resources we cannot replace a component by another one which requires a lot of resources). Furthermore, we are working on a dependency description extension to express properties on services and components. As future work we aim at extending our system to overcome its two main limitations, which are:

• to substitute a component assembly, we have to calculate the dependency of a composite component using the dependencies of its sub-component.

• in our current approach, components and services are identified by their names. This identity must be extended to include interface type and property information. This means changing from name equivalence to a form of subtyping when determining dependencies between services. In such an approach, we could reuse behavioral substitutability such as [START_REF] Cerna | Component substituability via equivalencies of component-interaction automata[END_REF] for example.

Fig. 1 .

 1 Fig. 1. A mail server assembly

Fig. 4 .

 4 Fig. 4. Comparison according to the old and the new service sets

Fig. 6 .Fig. 7 .

 67 Fig.6. Substitution of THUNDERBIRD by SYLPHEED more services. For instance, replacing THUNDERBIRD with the mail user agent of SEAMONKEY which has numerous enhancements, for example: a Chat service. (see Fig.7).

  C old is C old compatible with C client ?

			C client
	P 1	S 2	P 1	S 3
	P 2
	P 3	S 1	P 2
	P 1	S 2
	P 2	S 4
	P 3	S 1

Cnew is Cnew substitutable for C old ? Fig. 3. Vertical and horizontal compatibility Definition 3.1 (Strict substitutability) A component C old is strictly substitutable for a component C new , if the latter can replace C old in all contexts. Definition 3.2 (Contextual substitutability) A component C old is substitutable in a context Ctx for a component C new if the latter can replace C old in the context Ctx.

Table 1 Substitutability possibilities

 1possibilities

	Provides	more		same		fewer		different
		RS 1	P S 1	RS 1	P S 1	RS 1	P S 1	RS 1	P S 1
	more	RS 2	P S 2	RS 2	P S 2	RS 2		RS 2	P S 4
		RS 3	P S 3	RS 3		RS 3		RS 3
		RS 1	P S 1	RS 1	P S 1	RS 1	P S 1	RS 1	P S 1
	same	RS 2	P S 2	RS 2	P S 2	RS 2		RS 2	P S 4
		RS 3	P S 3			RS 3		RS 3
		RS 1	P S 1	RS 1	P S 1	RS 1	P S 1	RS 1	P S 1
	fewer	RS 2	P S 2	RS 2	P S 2	RS 2		RS 2	P S 4
		RS 3	P S 3	RS 3		RS 3		RS 3
		RS 1	P S 1	RS 1	P S 1	RS 1	P S 1	RS 1	P S 1
	different	RS 4	P S 2	RS 4	P S 2	RS 4		RS 4	P S 4
			P S 3

Table 2 Substitutability conditions

 2conditions

  all provided services of C old which are not provided by C new (C old .P s \ C new .P Substitutability is checked as depicted in the diagram of Fig. 5. First, the new context Ctx is calculated without the old component C old . So, Ctx is Calculation of Ctx = Ctx \ c old C new installable in Ctx ? Calculation of C new .P s C old .P s C old not substitutable C old .P s \ C new .P s = ∅

	yes		no
	yes	no
		NON	no
	yes
	C old is substitutable
	Fig. 5. Substitutability phases

have to calculate the context denoted Ctx without C old (Ctx \ C old ), i.e., simulate the effect of removing from the context the component C old with its four-tuple (C old , P s , F s , F c ). Then, we have to check the installability of C new in the resulting context (Ctx \ C old ). The formal definition of contextual substitutability is presented below:

Theorem 4.1 Contextual substitutability A component C old is substitutable for a component C new in a context Ctx if: • C new is installable in Ctx \ C old ; • s ) must not

be used necessarily in the context (NON condition): {(MD(G, C old .s) | s ∈ (C old .P s \ C new .P s )} = ∅

The required services of a component are stored in the dependency graph not in the component tuple.


M De Meuleneire

H Taddei

D Pastor

ALGEBRAIC QUANTIZATION OF TRANSFORM COEFFICIENTS FOR EMBEDDED AUDIO CODING

Keywords: embedded coding, transform coding, algebraic quantization

This paper proposes a new quantization for transform coefficients based on algebraic quantization. The coefficients are represented by a few pulses multiplied by a unique amplitude. The coefficients to be transmitted are selected by optimizing an error criterion, that determines the signs, positions and amplitudes of the pulses. This simple quantization has been implemented in a wavelet-based wideband scalable coder, and has been proved to provide a perceptually better quality than SPIHT on speech signal and music.

INTRODUCTION

An embedded, or scalable, codec organizes the bitstream in layers, where each layer can be decoded independently from the upper layers. The first layer, called core layer, contains the necessary data to synthesize a signal with a minimal quality and bandwidth. Upper layers called enhancement layers are meant to improve the quality and/or increase the bandwidth of the reconstructed signal. According to the network traffic, the decoder can adapt the bitrate on the fly by dropping packets of the upper layers, favoring the delivery of core layer packets. Moreover, the bitrate can also fit the terminal capacity. Besides, scalable coding easily enables premium access, where the user can access the highest quality of a multimedia content after payment.

Embedding coding has been widely investigated in speech and audio coding techniques. As the sampling frequency and the bitrate increase, transform coding is usually preferred over time-domain techniques such as Linear Predictive Coding. Transform coding involves the quantization of the time-frequency transform of the input frame. Usual time-frequency transforms are FFT, DCT, wavelet transform [START_REF] Mallat | A Wavelet Tour of Signal Processing[END_REF] or MDCT [START_REF] Princen | Analysis/Synthesis Filter Bank Designed Based on Time-Domain Aliasing Cancellation[END_REF]. Many coding techniques exist to transmit the coefficients. The simplest one is the scalar quantization of each coefficient. The redundancies can be reduced by using an entropy coder such as Huffman coding. Vector Quantization [START_REF] Gersho | Vector Quantization and Signal Compression[END_REF] might perform better at the expense of complexity increase. More sophisticated methods such as Spherical Vector Quantization [START_REF]Based Embedded Variable Bit-Rate Coder: An 8-32 kbit/s Scalable Wideband Coder Bitstream Interoperable with G.729[END_REF] or Scalar Quantized Vector Huffman coding [START_REF]Low-Complexity Coding at 24 and 32 kbit/s for Hands-Free Operation in Systems with Low Frame Loss[END_REF] allow a substantial reduction of the bitrate.

Using transform coding in a scalable coder implies a smart way to quantize the coefficients. The quantizer should be able to produce an embedded bitstream with a representation of the coefficients getting closer to their original values as the bit rate increases. Moreover, the bitstream should be organized in such a way that the most perceptually important coefficients, often the largest ones, are transmitted first. It is for example the case in the ITU-T G.729.1 [START_REF]Based Embedded Variable Bit-Rate Coder: An 8-32 kbit/s Scalable Wideband Coder Bitstream Interoperable with G.729[END_REF], where the energy of each band is transmitted to the decoder. From these values, the encoder and decoder can compute the bit allocation and the band ordering, from the most significant band to the least one. The more important the band, the higher number of allocated bits. However, all the bits of a codeword corresponding to a band are required to reconstruct coefficients. Incomplete codewords are simply discarded since they can not help to reconstruct coefficients. To take every single bit into account, bit-plane coding may be applied.

Algorithms such as Embedded Zerotree Wavelet (EZW) [START_REF] Shapiro | Embedded Image Coding Using Zerotrees of Wavelet Coefficients[END_REF] or Set Partioning In Hierarchical Trees (SPIHT) [START_REF] Said | A New Fast and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees[END_REF] achieve this bit granularity. Originally developed for the progressive transmission of still images, i.e. for 2-dimensional signals, they are also used in audio coding, e.g. [8][9]. By organizing the transform coefficients into trees and using a parentchildren relation, they produce an embedded bitstream where the first bits represent the most important bits of the most important coefficients, the next bits encode smaller coefficients while refining the quantization of the former quantized ones, and the last bits correspond to the least important coefficients. However, the resulting scalability might be a drawback for low target bitrate, as more coefficients could have been transmitted with a rougher quantization. This paper presents an algebraic quantization for transform coefficients. On a frame basis, the coefficients are gathered in bands. In each band, a factor related to the energy of the coefficients is computed. Positions and signs of the coefficients worthy of transmission are determined and simply quantized by a variable length codeword, that allows a partial decoding. The rest of the paper is organized as follows. The principles of the quantization are detailed and illustrated in Sec. 2. In Sec. 3, experiments to evaluate the quantization performance are presented. Sec. 4 concludes this paper.

ALGEBRAIC QUANTIZATION

The proposed quantization is inspired by the algebraic codebook search in Algebraic Code-Excited Linear Predictive coding (ACELP) [START_REF] Adoul | Fast CELP Coding Based on Algebraic Codes[END_REF]. In ACELP coding, the innovation is only quantized with a few pulses, multiplied by a gain. The pulse positions are determined with an analysis-by-synthesis scheme minimizing an error criterion. With our method, a group of transform coefficients, gathered in bands, worthy of transmission are also selected by optimizing an criterion and coded according to their position, sign and amplitude. The coefficients within the group are transmitted progressively, so that only a part of the coefficients within a band can be decoded. Sec. 2.1 presents the principles of the method. Determination of the coefficients to be transmitted is described in Sec. 2.2.

Principles

Let y(i), i ∈ {0, . . . , N -1} be the coefficients to be quantized, N is the number of coefficients per frame. In the general case, the input coefficients are divided into M bands. The band k comprises N k coefficients, such that:

M -1 k=0 N k = N (1)
The first coefficient of band

k is noted b(k). For example, b(0) = 0, b(1) = N 0 , b(2) = N 0 + N 1 , b(M -1) = M -2
k=0 N k , and by default, b(M ) = N . The coefficient within band k is indexed by j. The coefficient at position j in band k has position b(k) + j in the frame.

Our method aims at reducing at most the Mean Square Error (MSE) between the original and the reconstructed coefficients:

M SE (y, ŷ) = 1 N N -1 i=0 (y i -ŷi ) 2 (2)
Before decoding, the reconstructed coefficient are set to zero, ŷi = 0, i = 0, . . . , N -1. The MSE is then equal to

N -1 i=0 y 2 i N .
If a coefficient y i is perfectly decoded (i.e. y i = ŷi ), the MSE decreases by y 2 i N . In this sense, the most significant coefficients are the biggest ones. It should be a priority to quantize and transmit those coefficients first.

The following model has been investigated to quantize the coefficients. In a band k, the coefficients are estimated by:

ỹ(b(k) + j) = m k c(b(k) + j), j ∈ {0, . . . , N k -1} (3)
where c(b(k)+j) = ±1 or 0, and m k > 0. If c(b(k)+j) = 0, it is called a pulse. m k is the pulse amplitude. The coefficients are estimated by multiplying the pulses with their respective amplitude. In band k, the encoder has to determine how many pulses must be sent, their position, their sign, and which value m k is given. The pulse signs are given by the signs of their respective coefficients.

Minimization of an error criterion

The determination of the pulses and of m k is done by minimizing the MSE between the original and the estimated coefficients:

e k = N k -1 j=0 (y(b(k) + j) -m k c(b(k) + j)) 2 (4)
The optimal value of m k is given by the solution of ∂e k ∂m k = 0, i.e.

m k = N k -1 j=0 (y(b(k) + j)c(b(k) + j)) N k -1 j=0 c 2 (b(k) + j) (5)
Replacing m k by this expression in Eq. ( 4) yields:

e k = N k -1 j=0 x 2 (b(k)+j)- N k -1 j=0 y(b(k) + j)c(b(k) + j) 2 N k -1 j=0 c 2 (b(k) + j) (6
d k = N k -1 j=0 y(b(k) + j)c(b(k) + j) 2 N k -1 j=0 c 2 (b(k) + j) (7)
At each position, there is either a pulse or no pulse, i.e. two possibilities (the sign is always set as in sec. 2.1). The number of possible combinations is then 2 N k . Afterwards, the amplitude m k is computed by Eq. ( 5). Once the pulse combination that maximizes d k and the corresponding amplitude m k are found, they are sent to the decoder.

For N k large, the search can become very complex. However, it is actually not necessary to test all combinations. If the search is restricted to finding the best combination of ℓ pulses among N k pulses, ℓ < N k , the number of combination to be tested is

C ℓ N k = N k ! ℓ!(N k -ℓ)! .
The criterion d k becomes:

d ℓ k = N k -1 j=0 y(b(k) + j)c(b(k) + j) 2 ℓ (8)
For ℓ constant, maximizing the criterion Eq. ( 8) is equivalent to maximizing d ℓ k numerator. As y(b(k) + j)c(b(k) + j) > 0, with k = 0 . . . M -1 and j = 0, . . . , N k -1, maximizing the criterion d ℓ k is equivalent to maximizing

N k -1 j=0 y(b(k) + j)c(b(k) + j) (9)
A sum of positive values is maximal when every term of the sum is maximal. Consequently, the criterion d ℓ k is maximal when the ℓ pulses correspond to the ℓ biggest coefficient absolute values. The criterion may only be tested for N k combinations (i.e. ℓ = 1, . . . , N k ).

The optimal pulse combination is selected as follows. For ℓ = 1, . . . , N k , the criterion d ℓ k is computed according to Eq. ( 8) with the ℓ biggest absolute values. Finally, the optimal number ℓ opt is found by maximizing d ℓ k over ℓ:

d ℓopt k = arg max l∈1...N k d ℓ k ( 10
)
The optimal combination is given by the ℓ opt pulses at the position of the ℓ opt biggest absolute values.

The search complexity might be slightly reduced by taking into account the following assumption. The value of the criterion d ℓ k increases with ℓ until the maximal value d

d ℓ+1 k = ℓd ℓ k + |y(b(k) + j ℓ+1 )| 2 ℓ + 1 (11)
where j ℓ is the indice within band k of the coefficient with ℓ th biggest absolute value. A new pulse is added if its contribution increases the criterion. Otherwise d ℓ k > d ℓ+1 k , the search is stopped, ℓ opt = ℓ. The amplitude m k is computed and sent together with the selected pulse combination. This assumption proves to be true in about 95% of the cases. The 5% left corresponds generally to periods of weak energy like speech pauses.

EXPERIMENTS

The proposed algebraic quantization is very simple, as it is equivalent to a sorting algorithm (sorting the coefficient absolute values within a band in decreasing order). In the following, we illustrate our quantization with two examples that underline in which cases it could be applied. In Sec. 3.1, the quantization is applied to transform coefficients of the original signal. The quantization is then applied in Sec. 3.2 to a difference signal and compared to the SPIHT algorithm.

Experiment n • 1

Let us consider the following codec. A 4-level Wavelet Packet Decomposition (WPD) divides a wideband (8 kHz bandwidth) input signal into 16 Wavelet Packets (WP). The wavelet filter is the 24-tap Vaidyanathan filter and the convolution is performed using the "full convolution" in [START_REF] Leslie | A Wavelet Packet Algorithm for 1-D Data With No Block End Effects[END_REF]. The 2 WPs corresponding to the frequencies above 7 kHz are not taken into account. Consequently, 14 WPs are transmitted. Each WP is quantized using the procedure presented in Sec. 2.2. The mean of the 14 amplitudes is quantized in the log 2 domain using a 32-step (5 bits) non-uniform scalar quantizer. The ratio of each amplitude to the quantized mean is quantized in the log 2 domain by a 16-step (4 bits) non-uniform scalar quantizer. The quantized mean is transmitted first. Then, the amplitude and the pulses for each packet are transmitted following the frequency order. When all the packets are transmitted (at around 28 kbit/s), the same coding technique is applied to the error between the original and quantized WP coefficients.

Segmental SNR (SSNR) was used as an objective measure. It gives a measure of the distortion between the original signal s(n) and the reconstructed signal ŝ(n). The SSNR is computed for 8 different speech files at bitrates ranging from 16 to 48 kbit/s, with a 2 kbit/s step progression. The SSNR are averaged over the speech files. The average SSNR are depicted in Fig. 1. The plot shows that the SSNR increases with the bitrate, that is to say that the distortion decreases. Hence the quality improves. One can also notice a gap around 30 kbit/s. At this point, the codec starts to transmit information about the error signal. The WP coefficients in low frequencies are transmitted first. Since they are the largest, their transmission contribute greatly to reduce the distortion. This pattern could also be observed in the case of a multi-stage quantization, i.e. the error between the original and quantized coefficients from the previous stages is transmitted. Nevertheless, informal listening test showed that the quality at low bitrates (up to 32 kbit/s) is poor. The quantization of the low frequency WPs with our method seems to have an impact on the quality. Indeed, when the quantized coefficients between 0 and 2 kHz (the 4 first WPs) are substituted with the original ones, the perceptual quality is heavily improved. Conversely, replacing the coefficients above 2 kHz by the original ones does not have an influence. The problem disappears above 60 kbit/s, when the quantization of the low frequency WPs is sufficiently improved. The proposed method does not seem to be adapted to the quantization of original signal coefficients in low frequencies. A mechanism that transmit information to increase the SSNR as much as possible might helpful, for instance, transmitting first information about the frequencies up to 2 kHz, quantized WP coefficients and then the quantized error.

Experiment n • 2

This quantization has also been implemented in a modified version of the codec described in [START_REF] De Meuleneire | A CELP-Wavelet Scalable Wideband Speech Coder[END_REF]. This wideband speech codec provides an embedded bitstream that can be decoded at bitrates ranging from 8 to 32 kbit/s. The codec works on a 10 ms frame basis. The codec structure comprises three layers. First, a split band structure separates the Lower Band (LB) part and the Higher Band (HB) part of the input signal. The core layer encodes the LB part of the input signal. This layer makes use of the ITU-T G.729 coder at 8 kbit/s. Afterwards, the first enhancement layer utilizes bandwidth extension techniques relying on a wavelet filter bank to reproduce artificially the HB part, with an additional bitrate of 2 kbit/s. Finally, the last enhancement layer progressively encodes the wavelet coefficients of the difference between the original signal and the G.729 output in the LB part, and encodes the wavelet coefficients of the original signal in the HB part. The WPD provides 14 WPs to be transmitted. The WPs are transmitted according to the decreasing order of the energy of the 10 kbit/s output (G.729+bandwidth extension). The amplitude is quantized in the log 2 domain by a 16-step (4 bits) non-uniform scalar quantizer.

An A-B listening test has been performed to compare the proposed quantization with SPIHT. For this test, SPIHT has been optimized to fit with the codec structure and give the best results. Eight english sentences and four music pieces were presented to four non-native english speakers (the results have clearly shown that more listeners are not necessary). The samples are encoded with two versions of the codec at 32 kbit/s, one with SPIHT and the other with the proposed quantization. The results are presented in Tab. 1. At 32 kbit/s, the coefficient quantization are allocated 22 kbit/s. At this bitrate, it is not possible to transmit all the coefficients. For both codecs, the missing coefficients are replaced by the corresponding coefficients coming from the bandwidth extension. As the results show that the proposed quantization performed perceptually better, a rougher quantization than SPIHT that transmits more coefficients is preferable.

CONCLUSION

We proposed a new algebraic quantization for transform coefficients. The coefficients are estimated by a few pulses mul- tiplied by an amplitude. The amplitude, the sign and position of the pulses are determined by optimizing the error between the original coefficients and the estimated coefficients. This quantization has the advantage of being very simple, because it is equivalent to the sorting of a few values. Moreover, it also allows a progressive decoding of the coefficients. This method is well adapted for encoding an error signal for frequencies up to 2 kHz, and the original signal afterwards.

  ) Whatever the number of pulses and their position are, the first termN k -1 j=0 x 2 (b(k) + j) is always constant. Thus the minimization of e k is strictly equivalent to the maximization of the term d k defined by:

.

  d ℓ k decreases. ℓ opt is the first value of ℓ such as d There exists a recursive relation between d ℓ k and d ℓ+1 k :

Fig. 1 .

 1 Fig. 1. SSNR vs. bitrate.

Table 1 .

 1 SPIHT vs. algebraic quantization.

	Signal	SPIHT Algebraic quantization
	Speech	12.5 %	87.5 %
	Music	18.75 %	81.25 %


Abdourrahmane M Atto

Dominique Pastor

Grégoire Mercier

Gregoire Mercier

Smooth sigmoid wavelet shrinkage for non-parametric estimation

Keywords: Estimation, Wavelet transforms, Gaussian noise, Image enhancement, Image restoration

come

INTRODUCTION

This paper addresses the choice of the shrinkage function in nonparametric estimation of a signal according to the WaveShrink procedure described in [START_REF] Donoho | Ideal spatial adaptation by wavelet shrinkage[END_REF]. The method involves projecting the observed noisy signal on a wavelet basis, estimating the signal coefficients with a thresholding or shrinkage function, and reconstructing an estimate of the signal by means of the inverse wavelet transform of the shrinked wavelet coefficients. In Additive, White and Gaussian Noise (AWGN), such estimation is very efficient for smooth signals because the wavelet transform of such signals is sparse: these signals are characterized by few large wavelet coefficients [START_REF] Donoho | Ideal spatial adaptation by wavelet shrinkage[END_REF].

The contribution of this work is a whole family of smooth and non zero-forcing WaveShrink functions. These functions depend on a parameter that allows for a very flexible adjustment of the shrinkage. The new functions presented in this paper derive from the sigmoid function and, thus, are called Smooth Sigmoid-Based Shrinkage (SSBS) functions. SSBS is an adjustable shrinkage thanks to a parameter that controls the attenuation degree imposed to the wavelet coefficients.

Due to the smoothness of the SSBS functions, the shrinkage is performed with less variability so that the statistical properties of the signal are better preserved than when using standard thresholding functions. Since the SSBS functions introduce little variability among coefficients with closed amplitudes, they achieved an almost artifact-free denoising, which is relevant in many applications. Moreover, the performance of the proposed shrinkage is comparable to that obtained with the BLS-GSM method, introduced in [START_REF] Portilla | Image denoising using scale mixtures of gaussians in the wavelet domain[END_REF] and considered as the best parametric method.

SMOOTH SIGMOID-BASED SHRINKAGE

SSBS functions

This section introduces a new family of shrinkage functions for wavelet coefficient estimation of a signal corrupted by AWGN. Before that, let us describe very briefly, the limitations of some popular thresholding and shrinkage functions met in the literature on the topic. The standard WaveShrink functions considered are the hard and soft thresholding functions (proposed in [START_REF] Donoho | Ideal spatial adaptation by wavelet shrinkage[END_REF]); the Non-Negative Garrote (NNG) function (proposed for wavelet shrinkage in [START_REF] Gao | Waveshrink shrinkage denoising using the nonnegative garrote[END_REF]) and the Smoothly Clipped Absolute Deviation (SCAD) function of [START_REF] Antoniadis | Regularization of wavelet approximations[END_REF]). The graphs of these functions are given in figure 1. On the first hand,

Hard

Soft NNG SCAD Fig. 1. Some standard WaveShrink functions.

the hard thresholding function is not everywhere continuous and its discontinuities generate a high variance in the estimated signal; on the other hand, the soft thresholding function is continuous, but creates an attenuation on large coefficients, which results in an oversmoothing and an important bias for the estimated signal [START_REF] Gao | Waveshrink shrinkage denoising using the nonnegative garrote[END_REF]. The NNG and SCAD functions achieve a certain compromise between the hard and the soft thresholding functions as can be seen in figure 1. However, all the standard WaveShrink functions presented above include zero-forcing. This zero-forcing induces singularities of the thresholding function. As a consequence, this results in a significant variance of the estimation due to the sensitivity of the inverse wavelet transform. In addition, thresholding rules assume that the wavelet representation is sparse. Note that smooth signals yield sparse wavelet representations in the sense given by [START_REF] Donoho | Ideal spatial adaptation by wavelet shrinkage[END_REF]: for such signals, large coefficients are very few in number. In contrast, wavelet representations of natural images, which tend to be piecewise regular rather than smooth, fail to be sparse enough since large coefficients are not very few. This justifies the introduction of more flexible WaveShrink methods for correcting the drawbacks of thresholding rules. As an example, a WaveShrink parametrisation such as that proposed in [5] results in non zero-forcing and is shown to be more efficient than soft thresholding estimation.

Therefore, a suitable shrinkage function should satisfy the following two properties. (P1) Smoothness: a smooth shrinkage function induces small variability among coefficients with close values. (P2) Penalized shrinkage: a strong (resp. a weak) attenuation for small (resp. large) coefficients is required because small (resp. large) coefficients contain less (resp. more) information about the signal. Now, consider the family of real-valued functions:

δ t ,τ,λ (x) = sgn(x)(|x| -t ) + 1 + e -τ(|x|-λ) , (1)
for x ∈ R and where

(t , τ, λ) ∈ R + × R * + × R + .
Basically, these functions are suitable shrinkage functions in the sense given above since they satisfy properties (P1) and (P2). Each δ t ,τ,λ is the product of the soft thresholding function with a sigmoidlike function. As such, the functions δ t ,τ,λ will hereafter be called Smooth Sigmoid-Based Shrinkage (SSBS) functions.

The hard and soft thresholding functions can be regarded as functions δ t ,τ,λ for degenerated values of parameter τ. In fact, for fixed t = λ > 0, the function δ t ,τ,t (x) tends to the soft thresholding function sgn(x)(|x|-t ) + when τ tends to +∞. Now, put t = 0 and let τ tends to +∞. Then, δ 0,τ,λ (x) tends to δ 0,∞,λ (x), which is a hard thresholding function defined by:

δ 0,∞,λ (x) = x1 {|x|>λ} if x ∈ R \ {-λ, λ}, ±λ/2 if x = ±λ.
(

) 2
For fixed values of t , τ and λ, δ t ,τ,λ (x) behaves as the soft thresholding function sgn(x)(|x|t ) + when x → ∞. It follows that parameter t imposes an attenuation of t . Such an attenuation may be undesirable when t is large since, in this case, soft thresholding is known to over-smooth the estimate. For instance, this will occur if t is either the universal or the minimax threshold, which both tend to ∞ when the sample size tends to ∞. Therefore, we now restrict our attention to the particular case where t = 0, the following property being satisfied for this case. (P3) Vanishing attenuation at infinity: to avoid over-smoothing of the estimate, the attenuation decreases to zero when the amplitude of the coefficient tends to infinity. In the sequel, we put δ τ,λ = δ 0,τ,λ . Therefore, we have

δ τ,λ (x) = x 1 + e -τ(|x|-λ) . (3)
The functions δ τ,λ not only satisfy properties (P1) and (P2) but also guarantee vanishing attenuation (property (P3)). From now on, we only consider the SSBS functions δ τ,λ .

The role played by the SSBS parameters

This section provides an interpretation of the SSBS parameters. First, note that λ plays the role of a threshold since δ ∞,λ is a hard thresholding function with threshold height λ (see section 2.1 above). For every given λ, it is easy to see that, in Cartesian-coordinates, A = (λ, λ/2), O = (0, 0) and A = (-λ, -λ/2) belong to the curve of every function (δ τ,λ ) τ>0 . According to Eq. (3), we have δ τ,λ (±λ) = ±λ/2 and δ τ,λ (0) = 0 for any τ > 0. As an illustration, some SSBS graphs are plotted in figure 2, for different values of τ. It follows that τ parameterizes the curvature of the arc A O A, that is, the arc of the SSBS function in the interval ] -λ, λ[. This curvature directly relates to the attenuation degree we want to apply to the wavelet coefficients. Consider the graph of figure 3, where a SSBS function is plotted in the positive half plan. Due to the antisymmetry of the SSBS function, we only focus on the curvature of arc O A. Let C be the intersection between the abscissa axis and the

cos θ = --→ O A. --→ C A || --→ O A||.|| --→ C A|| = 10 + τλ 5(20 + 4τλ + τ 2 λ 2 ) . (4)
It easily follows from Eq. ( 4) that θ ∈]0, arccos 5/5[; when θ = arccos 5/5, then τ = +∞ and δ τ,λ is the hard thresholding function of Eq. ( 2). From Eq. ( 4), we derive that τ can be written as a function of θ and λ as follows:

τ(θ, λ) = 10 λ sin 2 θ + 2 sin θ cos θ 5 cos 2 θ -1 . (5)
In practice, when λ is fixed, the foregoing makes it possible to control the attenuation degree we want to impose to the data in ]0, λ[ by choosing θ, which is rather natural, and calculating τ according to Eq. ( 5). Since we can control the shrinkage by choosing θ, δ θ,λ = δ τ(θ,λ),λ henceforth denotes the SSBS function where τ(θ, λ) is given by Eq. (5).

EXPERIMENTAL RESULTS

In this section, Hard λ , Soft λ , NNG λ and SCAD λ denote the Hard, Soft, NNG, and SCAD thresholding functions with threshold height λ, respectively. Similarly, SSBS θ,λ will stand for SSBS with parameters θ and λ. The Stationary (also call shift-invariant or redundant) Wavelet Transform (SWT) is used for the wavelet decomposition. The analyzing wavelet is the Haar wavelet, and the shrinkage concerns the detail coefficients of the first four decomposition levels. Many experimental tests show that SSBS achieves better Peak Signal-to-Noise Ratios (PSNRs) than standard thresholding shrinkages and PSNRs close to those attained with BLS-GSM. The PSNR, often used to assess the quality of a compressed image, is given by PSNR = 10 log 10 d 2 /MSE , where d gives the dynamics of the signal (d = 255 in the standard case of 8 bit-coded images).

More specifically, we consider the 512 × 512 'Lena' image corrupted by AWGN. Table 1 presents the average PSNRs obtained by SSBS as well as hard, soft, NNG and SCAD thresholdings. Each PSNR is computed over 10 noise realizations. The threshold used is either the minimax or the universal threshold. In table 1, the universal (resp. minimax) threshold will be denoted by λ u (resp. λ m ). The different values considered for the AWGN standard deviation σ are 5, 15, 25, and 35. Parameter τ is obtained from Eq.

(5) by setting θ = π/6 and θ = π/4 respectively. This table shows that SSBS outperforms standard shrinkages. In addition, the performance measurements presented in table 1 suggest comparing the non-parametric SSBS to the parametric BLS-GSM presented in [START_REF] Portilla | Image denoising using scale mixtures of gaussians in the wavelet domain[END_REF]. The latter models neighborhoods of coefficients with Gaussian vectors multiplied by random positive scalars. BLS-GSM also takes into account the orientation and the interscale dependencies of the wavelet coefficients. It is computationally expensive but the results are very good. As mentioned above, BLS-GSM is regarded as the best parametric denoising method. For example, the results obtained by BLS-GSM for the same input PSNRs as those used in the preceding tests are given in table 2 for a comparison to SSBS.

Table 1. Average PSNRs computed over 10 AWGN realizations. PSNR 0 denotes the input PSNR.

σ = 5 σ = 15 σ = 25
Method PSNR 0 = 34.15 PSNR 0 = 24.61 PSNR 0 = 20.17 According to these results, SSBS is about 1.5 dB less efficient than BLS-GSM in terms of PSNR. In fact, it is very easy to improve the PSNRs of SSBS by introducing some level dependency, interscale dependency or block-thresholding procedures. For instance, if we proceed by adjusting the SSBS method at every decomposition level j with the threshold value λ/2 ( j -1)/2 , the PSNRs obtained with this Level Dependent SSBS (LD-SSBS) are those given in table 2.

λ = λ u , λ = λ m λ = λ u , λ = λ m λ = λ u , λ =
At this stage, it is now relevant to consider and assess the visual quality of denoised images obtained via the different shrinkage methods considered in this paper. Denoised images obtained via BLS-GSM, SSBS and LD-SSBS are given in figure 4. The 512×512 'Lena' image is corrupted by AWGN with standard deviation σ = 35. For the SSBS method, the thresholds are again the universal and the minimax thresholds computed over the whole original image. As far as LD-SSBS is concerned, these thresholds are adjusted at each decomposition level as described above. Parameter τ is obtained from Eq. (5) by setting θ = π/6.

We observe that SSBS denoising achieves a good trade-off between noise reduction, texture/edge enhancement and computational load and is almost free of artifacts. In contrast, LD-SSBS and BLS-GSM better restore textures and edges but introduce artifacts that are easily visible in figure 4.

In addition, the following experimental results suggest that SSBS better preserves the statistical properties of the signal of interest than standard thresholding functions, because SSBS yields coefficients that are approximately distributed as the signal coefficients.

Consider the Generalized Gaussian Distribution (GGD) with parameters α and β, defined for every real value x by: p α,β (x)

= β 2αΓ(1/β) e -(|x|/α) β
, where Γ is given for z > 0 by Γ(z) = ∞ 0 e -t t z-1 dt. The GGD models are sometimes suitable for describing distributions of wavelet coefficients of real-world signals. For instance, the horizontal detail coefficients located at the first decomposition level of the SWT of the 'Lena' image can be approximately modeled by the GGD with α = 1.1 and β = 0.56 (see figure 5 (a)).

Now, consider at the same decomposition level, the horizontal detail SWT coefficients of a noisy 'Lena' image; noise being AWGN with standard deviation σ = 35. The histogram of these coefficients is plotted in figure 5 (b). The flexibility of the SSBS function makes it possible to obtain distributions of the shrinked coefficients close to the distribution of the original wavelet coefficients, as can be seen in figure 5 (c-d). In contrast, this could not be achieved with standard shrinkage functions. In fact, the distributions obtained for the hard, soft, NNG and SCAD shrinkages deviate significantly from the distribution of the original image wavelet coefficients since these shrinkages force to zero too many small coefficients. Figure 5 (eh) gives the histograms of the coefficients resulting from the hard, soft, NNG and SCAD shrinkages. The threshold is set to σ so as to emphasize the effect of the zero-forcing on the distribution of the shrinked coefficients. The minimax and the universal thresholds being larger than σ, the results are even worse with these standard thresholds: a very high peak at zero and very few large coefficients scattered on both sides of this peak.

CONCLUSION

In this work, we have introduced a whole family of shrinkage functions, the SSBS functions. The SSBS functions are smooth and perform penalized and very regular wavelet shrinkage. This shrinkage is non-parametric because no prior information about the signal is taken into account. The SSBS method is simple and flexible in the sense that SSBS functions allow for a fine tuning of the shrinkage.

The experimental results of section 3 show that SSBS achieves almost artifact-free denoising and good PSNRs, even in comparison to BLS-GSM. We can reasonably expect to improve SSBS performance by taking the intrascale and interscale dependencies into account.

Extension of this work involves addressing the influence and the optimization of the three parameters t , τ and λ. In particular, Stein's unbiased risk estimate or its variant stated in [5, Theorem 1] could be used as a criterion to optimize the choice of these parameters.

Fig. 2 .

 2 Fig. 2. The SSBS functions δ τ,λ for different values of τ.

Fig. 3 .

 3 Fig. 3. Graph of δ τ,λ in the positive half plan.

Fig. 4 .

 4 Fig. 4. BLS-GSM and SSBS denoising of 'Lena' image corrupted by AWGN with standard deviation σ = 35. (a) Original image (b) Noisy image (c) SSBS π/12,σ (d) SSBS π/7.3,λ m

Fig. 5 .

 5 Fig. 5. (a-b) Histograms of the detail coefficients located at the first decomposition level of the 'Lena' image and a noisy 'Lena' image; noise is AWGN with σ = 35. The histograms are fitted with Generalized Gaussian densities. (c-h) Histograms of the shrunken noisy detail SWT coefficients located at the first decomposition level of the SWT of 'Lena' image.

Table 2 .

 2 λ m PSNRs computed when denoising the 'Lena' image corrupted by AWGN. The SSBS θ,λ PSNRs given are the best PSNRs achieved when θ = π/6, π/4 and λ = λ u , λ m .

	Hard λ	35.37 36.31	30.41 31.50	28.18 29.31
	Soft λ	31.57 32.97	27.03 28.20	25.33 26.34
	NNG λ	33.76 35.16	28.56 29.92	26.50 27.72
	SCAD λ	33.03 34.50	27.87 29.21	25.87 27.05
	SSBS π 6 ,λ SSBS π 4 ,λ	36.34 37.38 35.77 36.90	31.09 31.83 30.68 31.94	28.75 29.12 28.40 29.63
		σ = 5	σ = 15	σ = 25
	Method	PSNR 0 = 34.15	PSNR 0 = 24.61	PSNR 0 = 20.17
	SSBS	37.38	31.94	29.63
	LD-SSBS	37.72	32.57	30.26
	BLS-GSM	38.22	33.52	31.28