Sebastian Tramp

Henry Story
email: henry.story@bblfish.net

Andrei Sambra
email: andrei.sambra@it-sudparis.eu

Philipp Frischmuth

Michael Martin

Sören Auer

Extending the WebID Protocol with Access Delegation

The WebID protocol enables the global identication and authentication of agents in a distributed manner by combining asymmetric cryptography and Linked Data. In order to decide whether access should be granted or denied to a particular WebID, the authenticating web server may need to retrieve other proles and linked resources to work out e.g. if the requesting agent is member of an authorized group. If these resources are required to be publicly available for the server to access it, then this would be a major privacy limitation on a linked Social Network. In this paper we explore dierent ways in which an agent can act as a user and we propose an extension to the WebID protocol which allows for delegation of access authorization from a WebID to a third party, e.g. allowing a server to be able to act on behalf of its users. This extends the range of application scenarios where WebID authentication can be eciently deployed while increasing privacy.

Introduction

The World Wide Web is a peer to peer communication system designed from the outset to work in a global space, between agents distributed around the world and acting in parallel, with no center of control, in a space where new agents can at any point join and there is no complete overview of the whole system. These agents need know nothing of each other up to the point of their interaction. This is the force that leads the web to its declarative functional architecture, with its emphasis on naming and a logic of unalterability of the meaning of names (URIs).

Agents on the web communicate with each other through a limited number of actions: by making requests for resources (GET), by creating resources (POST or PUT), or even by deleting resources. Creation or deletion of resources usually require authentication of the agent making the request, and so in many cases do requests for information.

The WebID protocol enables the global identication of agents using asymmetric cryptography in a way that ts cleanly with this architecture: namely in such a way that agents can verify each others identity without having had any previous interactions and in such a way as to allow trust to build up in a decentralized manner.

A WebID is a URI that refers to an agent -person, robot, group or other thing that can have intentions. The WebID should be a URI which when dereferenced returns a representation whose description uniquely identies the agent as the controller of a public key [START_REF] Sporny | WebID 1.0: Web Identication and Discovery[END_REF][START_REF] Story | FOAF+SSL: RESTful Authentication for the Social Web[END_REF] The WebID protocol is used currently mostly for client authentication 4 . It is worth noting that the host serving the WebID proles controls the identity of every agent whose URI is within that server's namespace. This service is known as the origin server [START_REF] Barth | The Web Origin Concept[END_REF]. It is the origin of all resources served by it.

We can easily think of the origin server as not only able to respond to requests, but also as an agent able to make requests. Indeed WebID authentication requires the server to make WebID prole requests to other servers in order to verify the identity of agents making a request to it. The WebID specication describes this task as being accomplished by a separate agent, the WebID verier -which could indeed be done by another service on the web (WebID proxy authentication servers). But it can also be so closely tied to the web service that it would be natural to think of it as part of that same service. The WebID prole furthermore could be served by the same agent as the one making the request, in which case we have a minimal case of a peer to peer communication. Note that fetching a WebID prole for WebID authentication should be done anonymously, for fear of authentication deadlocks 5 .

Things get more interesting in the authorization space. Consider a very natural application of WebID: allowing friends of one's friends access to some resources. This authorization rule will require the web server to fetch each of its users' friends proles, in order to build up the list of authorised users. But there is a privacy issue involved here: not everyone wants to make all of their social network publicly visible, and some may not want to make any of it publicly visible. Those people may then protect their FOAF prole with access control rules such as only allowing friends of their friends access to it. How can a server that needs access to these FOAF proles in order to apply its own access control rules get access to the information? Would the server itself need to be listed as 4 Server authentication using IETF DANE follows much the same logic, except that the lookup for the identity is not done using the HTTP protocol but DNSSEC [START_REF] Homan | The DNS-Based Authentication of Named Entities (DANE) Transport Layer Security (TLS) Protocol: TLSA. Internetdraft[END_REF]. 5 For example one can imagine an agent S with prole Ps requesting a resource on server R which requires authentication. S would send R its certicate, thereby requiring R to dereference a friend of a friend by each of the users friends? Should the server take on the identity of the user it is fetching resources for? How would it be able to do so? What other solutions are there? These are the questions we will try to answer in this paper. The rest of the paper is organized in the following way: Section 2 describes preliminary requirements which we had in mind for our solution, Section 3 goes into detail with the WebID specication and adds support for authorization delegation, in Section 4 we describe our reference implementations based on two web applications which is followed by Section 5 where we compare our proposal with two other protocols, namely CORS and OAuth. Finally, we conclude our work in Section 6 and give directions for future work.

Preliminary Requirements

In order to make discussion of the problems easier, we distinguish the following roles in the access delegation process:

1. The secretary acts in the name of another agent, the principal. 2. The principal is the agent who has a secretary that acts on its behalf.

The solution we propose will be based on the following general principles: Distinguish secretary from principal -Identity should as far as possible be transparent. A secretary should have it's own WebID. The motivation for this is: (1) It allows resource guards to permit or deny requests based on this information.

(2) Secretary that have many principals do not need to switch their certicate between requests. (3) It makes it possible to describe the relation between a principal and its secretary using Linked Data.

Easy to use -The one and only place to describe which secretary are allowed to operate for a principal should be the principal's WebID prole. To grant delegated access to a secretary agent, no other actions than adding 1 triple to the WebID prole should be needed. Retracting this grant should involve simply removing it from the WebID prole.

Minimal protocol footprint -By using HTTP and working declaratively by placing statements in documents, we make adoption of the delegation easier and avoid complex protocol developments. We believe that this is a crucial feature of Linked Data in general.

Eciency -Finally, the proposed solution should scale with growing number of users and connections. In our context this means that an Social Web application should be able to act in the name of thousands of users. This section is organized in subsections which build up step by step to the proposed protocol, adding and validating the need at each step for the next one, the nal proposed protocol satisfying the previous principles. ] .

Listing 1. Prole allowing three dierent agents to act as Romeo Any server requiring authentication of an agent using WebID must implicitly trust the origin server [START_REF] Barth | The Web Origin Concept[END_REF] hosting the WebID prole, since the prole hosting server can change any information in the prole.

When the user owns the origin server and there is a one-to-one relation between the two, as it is the case in a personal FreedomBox 6 , then the origin server is just an extension of the user, and in that case trusting the server is the same as trusting the user.

It should be noted that each device can still be distinguished by servers in case of a problem by logging the exact public key that was used to connect to a service. It should be possible then to track down which device's private key had been compromised in case of unusual behaviour .

Things become more interesting when an origin server agent A is serving a number of dierent proles P 1 . . . P n each identifying respectively users U 1 . . . U n and needs to act on behalf of each of these users. This would be the situation for company servers, government agencies, educational institutions, charities, football clubs, etc. This brings up two issues that need to be taken into account, an issue of data perspective and an issue of eciency.

Keeping views distinct -First whenever A connects as U 1 to a remote resource R it has to place the data received in a separate graph from the one it stores public non authenticated data in, and to the one it stores a representation to the same resource R seen when connected as the dierent user U 2 . This is because the resource may return dierent representations depending on who is connecting to it -one representation for close friends of the owner of R perhaps, and one for more distant ones. This can be illustrated using N3 graphs, by specifying a relation between a view on a resource (using a yet to be settled on vocabulary), and a graph which is the log:semantics of that view (cf. Listing 2). It is very important that the agent receiving information from dierent users not merge the information that was destined to dierent users, or else information leakage will severely reduce the trust other agents have in that server A. This requires carefully keeping identied information that was aimed at dierent users separate, perhaps by creating dierent graph stores: one for public -non authenticatedinformation, and one graph store for each user the server needs to authenticate as. Eciency -Secondly, whenever the Origin Server needs to act as U 1 to a remote server R it will need to open a new TLS connection to that server using the cer-ticate C u1 for that user. This could require N parallel connections to the same server S. Opening TLS connections is somewhat expensive, as it requires expensive asymmetric key cryptographic computations. When N becomes large, this ineciency will be perceived as a serious drawback between two organisations. Conclusion It is possible for any number of software agents to act AS the user by creating themselves a public key as described above. This does require a very strong trust relation to exist between the agent acting as the user and the user herself, as the two will be mostly indistinguishable in the linked web of trust. This method also becomes inecient the greater the number of dierent users an agent is working for. In order to reduce the number of open connections to any server down to a minimum, it would be useful if the origin server could identify itself directly when making a request and specify on behalf of which of its users it was acting on per request so as to be able to make multiple requests on the same TLS connection. One way would be for the origin server acting as client to simply use the same public key as the origin server acting as server -that is it could use the same public key as the one used by the TLS server. It could even use the same certicate. This would make clear to any server it was connecting to, that it could rely on this server as much as it could on the identity of any resource, and in particular any WebID proles served by that server. Still, such an agent connecting to a remote service on behalf of one of its users would then need to identify which user it was acting on behalf of, or the remote service receiving a request would not know which access control rule to apply to the requesting origin server. For example in our previous example in the Romeo and Juliet story we showed how the Capulet family FreedomBox only shows Juliet as knowing Romeo, when Romeo makes the request on the resource, but not when the request is made by Romeo's father, lord Montague. That was an easy access control rule for the Capulet FreedomBox to make when the request was using the WebID protocol, since there it would know via the WebID authentication process exactly which identity the user was making the request as. But if it is the Origin Server connecting to the Capulet (FreedomBox), identied as their Montague Origin Server, then what representation should the Capulet FreedomBox return? Should it return the reduced version available to Lord Montague? Or should it return the more complete version available to Romeo and his close friends?

The proposal here is for the Origin Server to add to each HTTP request (made over TLS) an On-Behalf-Of header identifying the user on behalf of which the request is being made with that user's WebID, as shown below: The Capulet FreedomBox Guard having veried that this request does indeed come from the origin server of Romeo's prole <https://montague.net/romeo> would then be able to accept that since the requesting server could in any case act as Romeo whenever it chose to do so, this protocol making exchange between the Montague and Capulet houses more ecient without making it less secure, this be justication enough for it (the Capulet FreedomBox) to serve the representation that Romeo would have received had he connected to the server directly. In Section 5 we will argue that this is very similar to the way CORS deals with access control, namely by adding a header to a request in order to clarify what agent is making the request. This On-Behalf-Of header makes it possible for the secretary to open only one TLS connection to a remote server and be able to specify for each request on behalf of whom it is making it. The Montague FreedomBox could make a request to the Capulet Freedom Box On-Behalf-Of Romeo, a few milliseconds later On-Behalf-Of Lord Montague, and so on. Again as explained in the previous section it is the responsibility of the Montague FreedomBox to keep the returned information separate, and act with discretion whenever it is acting on behalf of one or the other of the users. As such it's role is not unlike the role of Friar Laurence in the play -dedication to people's private matters requires tact and discretion.

Limitations Using the same cryptographic key between the server acting as client and as server risks making the keys available to a wider audience, and so increases the risk of key compromise. It may be useful if it were possible to decouple the identity of the agent acting on behalf of another user -the secretary -from the Origin Server.

Solution 3: Secretary acting on Behalf of a User

The origin server acting as a client on behalf of a user can then be thought of as a keeper of secrets for that user. It should know how to distinguish what remote servers tell it when it is acting on behalf of one user, from what a remote server tells it when it is acting on behalf of another user. The role of the keeper of secrets for a person is known as the secretary role -a prestigious role taken on for example by gures such as the Secretary of State, Hillary Clinton.

If we now identify the secretary that can act on behalf of a user using a WebID, we can generalise the protocol somewhat. That is, when an agent -such as the Montague FreedomBox Laurence with WebID <http://montague.net/fb #laurence> -authenticates to a remote server it can use its own WebID. This would allow the secretary to have her own public key, and so to reduce the risk of her private key being compromised aecting the server public key.

But how would the remote server know that it can trust that secretary to be acting on behalf of a particular user? It can no longer just compare the TLS keys of the requesting agent to see if it comes from the same Origin Server. We need to make this relation explicit by use of a special RDF relation provisionally called :secretary 7

The remote server can then verify that the identied agent is the secretary of the agent he wishes to act on behalf of (as specied in the On-Behalf-Of header, by dereferencing that user's prole and verifying that the user species the :secretary relation there, as it would if Romeo had the FOAF proles as shown in Listing 3. <https ://montague. net/romeo#m> a foaf : Person ; foaf : name " Romeo ";

: key [ : modulus " cb24 ... ed85 " ^^xsd : hexBinary ; : exponent 65537 ];

: secretary <https ://montague. net/fb#laurence>. The following enumeration describes each authentication step of Figure 1 in detail but concentrates on the context of access delegation: (1) The secretary opens a TLS connection with the server of the protected resource. (2) Once TLS is set up, the HTTP request is sent to the server (e.g. a HTTP GET), with an additional On-Behalf-Of header, which thereby denes the requesting agent as a secretary and the referred to agent as the principal (3) The guard intercepts this request, and in turn requests client authentication using TLS session renegotiation. The secretary authenticates as itself by sending a Certicate containing a WebID referring to it. The TLS-Light service veries that the secretary really is in possession of the private key corresponding to the public key sent in the certicate. This is dened in the TLS protocol [START_REF] Dierks | The Transport Layer Security (TLS) Protocol Version 1.2[END_REF]. [START_REF] Dierks | The Transport Layer Security (TLS) Protocol Version 1.2[END_REF] The guard ask the verication agent to verify the secretary WebID which is named in the certicate (5a). This process is exactly as described in the WebID protocol [START_REF] Story | FOAF+SSL: RESTful Authentication for the Social Web[END_REF]. The guard also asks the verier agent to check the secretary claim implied by the On-Behalf -Of header. (5b) The principal agent's relation to the secretary is veried by dereferencing the principal's WebID Prole, and verifying it responds with a true to the SPARQL ASK query ASK { ?principal :secretary ?secretary . } where the ?principal and ?secretary variables have been bound to the correct URIs. ( 6) The authentication and verication process having succeeded, the authorization process checking if the principal would get access to the requested resource. [START_REF] Kagal | conjunction with the 4th International Semantic Web Conference[END_REF] The resource representation can then be returned or not depending on the access control rules.

Implementation and Evaluation

As two real-world examples we describe two dierent implementations where WebID delegation is deployed and needed. MyProle is a WebID identity service application and OntoWiki a semantic data wiki.

MyProle8 is a web service demonstrating how easy it is to create a WebID prole, and also building up distributed social web applications upon it. Its main purpose is to provide a unied user account, or simply user prole. Currently these are tied to the MyProle project web site, but it has been designed from the ground up to work with distributed Linked Data, making it then easy to dissociate the software stack from the MyProle project domain name, allowing it to be deployed on a machine under the user's control, preferably even a device located within the user physical reach.

In the case of MyProle, it is very important to be able to oer WebID access delegation, because a single MyProle server instance can host multiple users, and must fetch resources for each user asynchronously in order to be able to provide a seamless and rapid user experience. To improve user experience and overall performance, a caching mechanism is used to refresh local copies or "views" of external data. Due to multiple users coexisting on the same server, the caching mechanism needs to be able to distinguish views of remote resources as seen by dierent users, as they are served by remote servers depending on their access control and resource ltering policies.

Let's take for example the following case: Ann and Barry are both local users on a single MyProle server. Charley is an external user with access control policies set up on his private server. When Ann requests to view Charley's prole data, a personalized view of the prole is displayed, corresponding to access control policies by Barry for requests made by Ann. When Barry requests to view Charley's prole, dierent prole data is displayed, since there are dierent access control policies for Barry. The caching mechanism needs to be able to cache two dierent prole views, each corresponding to access control policies specic for the user requesting the data. As the number of users on MyProle grows this has to be done as eciently as possible, and so re-using TLS connections where possible is a laudable aim.

OntoWiki [START_REF] Auer | OntoWiki -A Tool for Social, Semantic Collaboration[END_REF] is a web application, which allows publication, exploration as well as manipulation of arbitrary RDF knowledge bases in distributed scenarios. We refer to it as a data wiki, since it adopts the wiki philosophy (ease of editing, tracking of changes, integrated discussions) on the one hand, while focussing on structured information on the other hand. Furthermore OntoWiki is an adaptable application framework, which supports the creation of Linked Data based applications on the web [START_REF] Heino | Developing Semantic Web Applications with the OntoWiki Framework[END_REF]. In addition to the usual features of wikis, OntoWiki provides a sophisticated extension system, such that it can be adapted for a variety of use-cases. Although the wikis usually enable anyone to edit everything, numerous real-world applications require access-control mechanisms. OntoWiki has built-in support for authorization on graph and action level. Furthermore several authentication protocols can be employed, including amongst others the WebID protocol.

A rst use-case for WebID access delegation within OntoWiki arises from an important functionality within OntoWiki, namely import of external data. Since WebID proles can contain personal information that is in need of protection, access to such data should be restricted with the WebID protocol. Although a user may (or may not in the case of a periodically executed automatic synchronization process) initiate the import procedure manually via the OntoWiki user interface, the actual fetching is done in the background. An OntoWiki instance does not know of any private keys of users of the system. Thus the system is not able to use that information when requesting data. With WebID access delegation though, the prole can be fetched on behalf of the user instead.

Another use-case where access delegation can be employed is within the Semantic Pingback protocol [START_REF] Tramp | Weaving a Social Data Web with Semantic Pingback[END_REF]. With Semantic Pingback owners of resources can be notied when for example a link to such a resource is created elsewhere on the web. In order to protect the protocol against spam attacks, a Pingback server will fetch the desired resource and check, whether the stated link is indeed contained in the data. The source resource that links to the target resource and thus is fetched by a Pingback server might be access restricted, for example in a scenario where a friending process is initiated [START_REF] Story | Friending On The Social Web[END_REF]. For privacy reasons the owner of the WebID proles will very likely hide the triples in question (e.g. foaf:knows) on anonymous access attempts. With WebID access delegation again, the resources can be fetched by the Pingback server on behalf of the resource owner.

This will require some further changes to the delegation protocol discussed up to now. Specically the :secretary relation currently does not distinguish what kind of responsibilities the principal wishes to give to the secretary. It is currently assumed that the secretary has full rights. For ontowiki knowing the social network may be all that is needed to make access control decisions. Full delegation powers may not be needed. The ability to describe more limited secretary relations could be very helpful here.

Related Work

OAuth 2.0 [START_REF] Hardt | The OAuth 2.0 Authorization Framework[END_REF] is the latest version of the OAuth protocol, which is being presented as an access delegation protocol, enabling users to grant access to thirdparty services to their personal resources, instead of sharing their passwords with those third-party services. OAuth includes two main parts: obtaining an access token by asking the resource owner (i.e. the user) to grant access, and then using the tokens to access protected resources. The advantage here is that Ann only had to use her Twitter credentials to log into Flattr. However, the disadvantage is that Flattr requires an existing trust relationship with Twitter, thus limiting the number of supported services. Even if OAuth provides authentication as a by-product of having the resource owner authorize a third-party client to her resource server, its main focus is on resource authorization rather than on federated identity. The conclusion is that OAuth is used to provide access for external services to local user resources without disclosing the user's credentials. Or in other words: OAuth is used to allow an agent to request a users resources while WebID delegation is used to allow an agent to request resources the user could request herself.

Cross Origin Resource Sharing (CORS) In this paper we proposed to add an On-Behalf-Of header to each HTTP request made by a secretary in order to be able to identify the principal she is working for in that particular request. This is quite a major semantic addition to HTTP, but for which there is a widely adopted precedent, namely CORS 9 , the Cross Origin Resource Sharing specication at the W3C. CORS identies the remote principal with an Origin header, and uses any HTTP authentication method to identify the secretary which is the browser.

Let us look at this in more detail. CORS has two agents, one acting on behalf of the other, and these are: (1) The Browser: it takes the role of the secretary as it is acting on behalf of JavaScript agents -the principals. (2) JavaScript code: hosted on the internet and identied by the Origin Server that hosted the JavaScript. This JavaScript agent requests resources from the Browser, but it is unable to do it directly.

The use cases for CORS are slightly dierent from the ones for our delegation proposal. In CORS the browser is using its own identity credentials when connecting to remote servers (e.g. a bank), as it needs to alert the remote service that the request originates from a particular agent. The browser also needs to make sure the remote server understands this, especially when authentication is required, to allow the remote server to evaluate the strength of the JavaScript trust relation. In the Section 3 use cases, the remote site trusts the principal, but may not be aware of the secretary. In our proposal, the identication of the agent in the On-Behalf-Of header is much more precise. Combined with the ability of the secretary to also identify herself with a WebID, it builds an explicit trust relation between the principal and the secretary. The vagueness of the Origin identity of the principal in CORS makes a lot of this more dicult.

It is a topic of further research to evaluate in which circumstances it is important for the secretary to also make sure that the remote server is aware that the connection being made is On-Behalf-Of the specied principal. For otherwise it is possible that the secretary herself be made liable for the actions she is making on behalf of her principal, especially were she to make PUT, POST or DELETE requests. The CORS protocol determines this by requiring an initial HEAD request to a resource to be made, which will determine whether the server understands CORS. With the help of TLS the server hosting the remote resource could have a WebID Prole describing it to be an understander of the On-Behalf-Of header, making the protocol a lot more ecient and secure once more.

Conclusion and Future Work

In this paper we discussed dierent ways in which an agent, such as a Social Web application, can act on behalf of a user and request as well as manipulate resources on the Web in the name this user. Our proposal for supporting such a communication schema involves an extension to the WebID protocol, which allows for delegation of access authorization from one agent to another agent, both identied by their WebID. The technical solution for this concept annotates HTTP requests by adding the On-Behalf-Of header eld which refers to the WebID of the user in whose name the agent acts. This distinguish the identities of the user and the agent and allows for creation of policy descriptions which use both WebIDs to specify the relations between the agent and the user in order to setup the access rules for this agent. Since the protocol footprint is minimal, the main information entropy to decide whether an agent has the right to request a specic resource or not is available as part of the content of a WebID prole which can be requested as Linked Data. We believe that such an shift of the entropy from a protocol endpoint (such as in OAuth) to a machine readable document is a crucial feature of Linked Data in general and WebID in detail.

However, at this point we postpone the answer to the question of how we should describe the access control rules in a users WebID prole. There already exists rst attempts from the Linked Data / Semantic Web and the Read Write Web communities such as the WebAccessControl vocabulary10 , dg FOAF [START_REF] Schwagereit | Representing Distributed Groups with dgFOAF[END_REF] as well as dierent projects on policy creation and management [START_REF] Kagal | conjunction with the 4th International Semantic Web Conference[END_REF]. In our future work we will try to close the gap between the policy and access control vocabularies on the one hand and WebID authentication on the other hand. A rough abstract in which direction this should be elaborated is presented in Listing 2 and we hope that we can sensitize others to take up this challenge too.

3 . 2

 32 Solution 2: Origin Server acting on Behalf of a User

Listing 3 .Fig. 1 .

 31 Fig. 1. Extended WebID authentication sequence

  S's prole Ps in order to verify the WebID. If Ps itself requires authentication of R and if R sends a certicate containing a WebID with its prole Pr, and if Pr itself requires authentication then it looks like we have a deadlock.

  The simplest solution for any user agent A wishing to act as the user U , is for it to create a public/private key pair, and with the public key thus generated create a certicate C u with U 's WebID in the Subject Alternative Name position and add the public key to the user U 's prole P u (seeListing 1). Having done this the agent A can then connect using the certicate C u and its associated private key, to any service it wishes to, when it wants to work for/as the user U . This has the advantage of requiring no change to the WebID protocol. It does give the agent A all powers of the user U and so this type of privilege should be limited to agents which are either extensions of U or ones U can or must fully trust anyway.

	3.1	Solution 1: Acting as the user
	<http ://montague. net/romeo#m> a foaf : Person ; foaf : name " Romeo ";
	cert : key [ a cert : RSAPublicKey ;
	rdfs : label " August 2 2012 at 10 am CET , in Firefox laptop browser ";
	cert : modulus " cb24 ... ed85 " ^^xsd : hexBinary ; cert : exponent 65537;
	],
	[ a cert : RSAPublicKey ;
		rdfs : label " August 2, 2012 at 14:30 CET by Montague Family FB Laurence ";
		cert : modulus "2 e34 ... aa24 " ^^xsd : hexBinary ; cert : exponent 65537;
	],
	[ a cert : RSAPublicKey ;
		rdfs : label " August 10 , 2012 at 14:30 Rome time with Nokia Cell Phone ";

cert : modulus " 77 e5 ... c342 " ^^xsd : hexBinary ; cert : exponent 65537;

  Views on Juliet's FOAF prole by Freedom Box Laurence, when acting as Romeo and when acting as Lord Montague

	[ a subj : View ; subj : of <https :// capulet . org/ juliet /friends> ; subj : by <https ://montague. net/romeo#me> ; subj : using [ : modulus "2 e34 ... aa24 " ^^xsd : hexBinary ; : exponent 65537 ]
	] log : semantics { <https :// capulet . org/ juliet#ms> foaf : knows <https ://montague. net/romeo#m>, <https :// capulet . org/fb#john>, <http ://montague. net/fb#laurence> . } .
	# view that the F .B Laurence has as Lord Capulet of Juliet 's friends
	# notice that the relationship of Juliet knowing Romoe is missing here
	[ a subj : View ; subj : of <https :// capulet . org/ juliet /friends> ; subj : by <https ://montague. net/father#lord> ; subj : using [ : modulus " ec224 ...532 " ^^xsd : hexBinary ; : exponent 65537 ]
	] log : semantics { <https :// capulet . org/ juliet#ms> foaf : knows <https :// capulet . org/fb#john>, <http ://montague. net/fb#laurence> . } .
	Listing 2.

# view that the F .B Laurence has as Romeo of Juliet 's friends

http://www.freedomboxfoundation.org/

A object property with a domain and range as foaf:Agent which we will provisionally place in the cert: namespace, though it may be more appropriately placed in the auth: namespace.

http://myprofile-project.org/

http://www.w3.org/TR/cors/

http://www.w3.org/wiki/WebAccessControl


Sylvain Prigent

Xavier Descombes

Didier Zugaj

Laurent Petit

Anne-Sophie Dugaret

Philippe Martel

Josiane Zerubia

† Morphème

Classication of skin hyper-pigmentation lesions with multi-spectral images

Keywords: skin, hyper-pigmentation, SVM, data reduction, multi-spectral images * Morphème / Ayin peau, hyper-pigmentation, SVM, réduction de dimension, imagerie multi-spectrale Contents

According to clinical protocols, skin diseases are quantied by dermatologists throughout a treatment period, and then a statistical test on these measures allows to evaluate a treatment ecacy. The rst step of this process it to classify pathological interest areas.

This task is challenging due to the high variability of the images in one clinical data set. In this report, we rst review algorithms that exist in the literature and adapt them to our problem. Then we choose the more appropriate algorithm to design a classication strategy. Thereby, we propose to use data reduction combined with SVM to do a rst classication of the disease. Then we associate the obtained classication map with a segmentation map in an interactive classication tool in order to compromise between operator dependency and algorithm robustness.

In dermatology, one of the last steps to validate a new treatment is to test it on a sucient number of patients and assess if its ecacy is statistically better than a standard treatment or a placebo. Nowadays, for such a study, dermatologists have to clinically measure the severity of all the patients along the treatment period. Then, statistical tests such as the t-test [START_REF] Mood | Introduction to the theory of statistics[END_REF] are applied on the dermatologist measures to determine if the treatment is statistically ecient. In practice, specialists do not use an absolute measure to quantify the severity evolution of the studied treatment using a statistical test but, on the contrary, a relative measure with respect to a reference treatment or a placebo. Let's call this reference a comparator. For example, in the clinical study we consider in this report, patients are selected to present the same severity degree on the two cheeks. Then, one cheek receives the tested treatment that we will call active whereas the second cheek receives the comparator. It is the severity on the active treated area normalised by the comparator treated area that is used for the statistical test.

In order to automatise as much as possible the treatment evaluation process and to make it more objective, we propose to use images associated with a processing methodology. Images we use are multi-spectral. They consist of a collection of monochrome images taken at dierent wavelengths. With these images, we have both spatial and spectral informations of the skin.

Indeed, spectral information is crucial to analyse the skin. Figure 1 shows the theoretical absorptions of melanin and haemoglobin. In this gure, it appears clearly that without the spectral information it is dicult to unmix these two components.

To employ images for skin hyper-pigmentation evaluation, we propose the following scheme.

First, the pathological areas have to be segmented on images at the baseline visit. Then, a severity criterion has to be drawn and estimated to quantify the severities of pathological areas at each measurement time. These severity measurements can be used by clinicians to evaluate treatment ecacy or patient evolution. In this report, we focus on the classication part.

In the literature, methods have been proposed to segment skin lesions on color or spectral images [START_REF] Weatherall | Skin color measurements in terms of CIELab color space value[END_REF][START_REF] Stamatas | Non-invasive measurements of skin pigmentation in situ[END_REF][START_REF] Stamatas | In vivo measurement of skin erythema and pigmentation: new means of implementation of diuse reectance spectroscopy with a commercial instrument[END_REF]5,6,7,[START_REF] Schmid | Segmentation of digitized dermatoscopic images by two-dimensional color clustering[END_REF] A theoretical absorbency spectrum of the components of the skin is presented on gure 1. The simplest method to evaluate the pigmentation of a skin area is to select only one spectral value in an area of interest or to compute a ratio between two spectral measurements [START_REF] Stamatas | Non-invasive measurements of skin pigmentation in situ[END_REF]. Stamatas et al.

proposed an algorithm [START_REF] Stamatas | In vivo measurement of skin erythema and pigmentation: new means of implementation of diuse reectance spectroscopy with a commercial instrument[END_REF] to analyse the spectrum and determine the proportion of the principal skin components which are melanin and haemoglobin. The method consists in modelling the melanin absorbency as linear in the spectrum range of 630-700 nm:

A m (λ) = aλ + b, (1)
where A m represents melanin absorbance, a and b are linear coecients and λ is the wavelength.

Then, the spectrum can be corrected by subtracting the inuence of the estimated melanin:

A c (λ) = A(λ) -A m (λ). (2)
Concentrations of oxy-hemoglobin and deoxy-hemoglobin can be calculated by solving a system given by the Beer-Lamber law applied to two specied wavelengths (λ 1 = 560 nm , λ 2 = 580 nm):

A c (λ) = [oxy_Hb] * oxy_Hb (λ) + [deoxy_Hb] * deoxy_Hb (λ), (3)
where oxy_Hb and deoxy_Hb represent extinction coecients which are tabulated values. Finally, corrected melanin concentration cartography can be extracted by correcting the ane estimation of melanin concentration taking into account the deoxy-hemoglobin inuence in the 630-700 nm range: we propose to use a data reduction and classication scheme that we compare to the Stamatas et al. algorithm. We perform data reduction, and classication using Support Vector Machine (SVM). A lot of algorithms have been proposed to reduce the data dimension. The most popular are unmixing ones like PCA [START_REF] Jollie | Principal Component Analysis[END_REF], Kernel PCA [START_REF] Fauvel | Spectral and spatial methods for the classication of urban remote sensing data[END_REF], Diusion maps [START_REF] Lafon | Diusion maps and coarse-graining: a unied framework for dimensionality reduction, graph partitioning, and data set parameterization[END_REF], ICA [START_REF] Comon | Independent Component Analysis, a new concept ? Signal Processing[END_REF], endmember extraction [START_REF] Bioucas-Dias | A variable splitting augmented lagrangian approach to linear spectral unmixing[END_REF]. These algorithms tend to combine the spectral data into a new lower dimensional space by minimizing a criterion. Another family of algorithms aim to partition the spectrum and combine neighbouring spectral bands. This can be done manually by selecting spectral areas of interest and averaging neighbouring redundant bands or automatically with algorithms like the projection pursuit (PP) [START_REF] Mallat | Matching pursuit with time-frequency dictionaries[END_REF]. Both types of techniques have been tested in this study.

[M elanin] c = [M elanin] -[deoxy_Hb] * a[ deoxy_Hb ] + b[ deoxy_Hb ] , (4)
This report is organized as follows: section 2 describes the chosen algorithm to classify the skin areas of interest and shows results on real data validated by experts. In section 3 we propose a classication strategy that tends to compromise between operator dependency and robustness.

Finally, in section 4, we conclude about the proposed method and obtained results.

Data reduction with Projection Pursuit

The projection pursuit (PP) approach was originally proposed in [START_REF] Mallat | Matching pursuit with time-frequency dictionaries[END_REF]. An adaptation to multispectral images or hyper-spectral data has been proposed in [START_REF] Jimenez | Hyperspectral data analysis and supervised feature reduction via projection pursuit[END_REF][START_REF] Rellier | Texture feature analysis using a Gauss-Markov model in hyperspectral image classication[END_REF]. The PP method can be decomposed in two steps.

The rst step consists in partitioning the spectrum into groups. Originally each group contained the same number of bands. In [START_REF] Rellier | Texture feature analysis using a Gauss-Markov model in hyperspectral image classication[END_REF] a method that partitions the spectrum into various band number groups is proposed. It tends to minimize the variance σ inside each group. Such a partitioning is important in our application since we want to keep an interpretation of the spectral data due to the absorbency of melanin or haemoglobin (see Figure 1). The method in [START_REF] Rellier | Texture feature analysis using a Gauss-Markov model in hyperspectral image classication[END_REF] requires the input parameter K (number of groups). In [START_REF] Prigent | Spectral analysis and unsupervised SVM classication for skin hyper-pigmentation classication[END_REF] we proposed an alternative method. From an index I such as the Kullback-Leibler divergence, we measure the deviation between consecutive bands. It results in a function F I which describes the spectrum variations:

F I (k) = I(k -1, k), k = 2, ..., N b , (5)
with N b the number of bands. F I (k) is low if the bands k -1 and k are redundant and high if the bands k -1 and k exhibits less redundancy. Thresholding F I (k) with a threshold T [START_REF] Prigent | Spectral analysis and unsupervised SVM classication for skin hyper-pigmentation classication[END_REF] allows to select the most signicant local maxima of F I . The location of these maxima gives the spectral bands to be chosen to partition the spectrum. The advantage of the parameter T is that it can be interpreted as the degree of redundancy accepted between each group.

The second step is the estimation of the vectors that allow to project each group into one band. These vectors are estimated by maximising a distance between groups [START_REF] Jimenez | Hyperspectral data analysis and supervised feature reduction via projection pursuit[END_REF]. To estimate RR n°8105

D kb (a, b) = H kb (a, b) + H kb (b, a) 2 , (6)
such as

H kb (a, b) = f a (x)ln f a (x) f b (x) dx, (7)
where a and b are the projected groups of bands and f the density function of the distribution a (respectively b).

Data reduction with ICA

ICA is one of the most famous unmixing algorithm. It had been detailed in [START_REF] Comon | Independent Component Analysis, a new concept ? Signal Processing[END_REF]. For skin hyper-pigmentation application, we expect that a source will be representative of the melanin concentration. Mathematically, ICA models the unmixing problem as linear:

X i,j = AS i,j + N i,j , (8)
where X i,j is a single pixel at the spatial position (i, j). This pixel X i,j is considered as a linear combination of independent components given by A. S i,j is the vector containing the linear mixing coecients (i.e. proportion of each component per pixel). The noise is modelled as additive by the vector N i,j . The coecients are quantities that should be positive and the sum of the proportions of all the components have to be equal to 1:

∀k ∈ [0.N b ], S i,j (k) ≥ 0 (9)
and

N k=1 S i,j (k) = 1 (10)
The unmixing model of equation ( 8) shows one indetermination. In fact, each permutation of the columns of matrix A gives a dierent result. Nevertheless, this indetermination only changes the order of the sources.

In order to solve the unmixing problem for the skin hyper-pigmentation with multi-spectral images, we compare two algorithms. FastICA [START_REF] Hyvarinen | Fast and robust xed-point algorithms for independent component analysis[END_REF] and JADE [START_REF] Cardoso | High-order contrasts for independent component analysis[END_REF]. The goal of these algorithms is to lter the noise N i,j , and then to nd  (an estimate of A). The proportion of each component per pixel (i, j) is then obtained by the inverse product:

S i,j = P X d i,j , (11)
where X d i,j represents the denoised X i,j , and P the pseudo-inverse matrix of Â. FastICA performs the estimation of A in a similar way to the projection pursuit. In [START_REF] Hyvarinen | Fast and robust xed-point algorithms for independent component analysis[END_REF], the author proposes to get the component by maximazing the non-Gaussianity through a negentropy index. This index aims at measuring the deviation between the studied signal X and the entropy of a Gaussian distribution with the same correlation matrix. Indeed, each component (i.e. each column of A) is iteratively estimated with the constraint that each component has to Inria be orthogonal to all the other ones. To compare the data to a Gaussian distribution with the same correlation matrix, whitening is used in order to make the data covariance matrix equal to the identity matrix:

E(XX T ) = Id N b (12)
To compute the data whitening, the Principal Component Analysis (PCA) is used:

Z i,j = W X i,j , (13)
with W the whitening matrix obtained by W = √ D -1 E T , where D is the diagonalized covariance matrix (X X T ) by PCA and E the eigen-vector matrix. At this step, one can keep only the rst components that give enough explained variance. This allows to reduce the data and the noise which is contained in low variance PCA obtained bands.

The JADE (Joint Approximate Diagonalisation of Eigenmatrices) algorithm proposed in [START_REF] Cardoso | High-order contrasts for independent component analysis[END_REF] consists in minimizing the fourth order cumulants in order to solve the linear ICA problem.

The author demonstrates that minimizing cumulants of order 1,2 and 4 (i.e. mean, covariance and fourth order cumulants) is mathematically equivalent to maximize the neg-entropy between components. JADE algorithm starts with a data whitening using PCA. Then, the problem can be written as follows:

Z i,j = W AS i,j (14)
Where W is the whitening matrix and Z i,j the whitened data. The new mixing matrix W A is a rotation matrix since it links two white data. The last part of the JADE algorithm is to perform this rotation transformation optimizing the criterion:

φ(z) = ilkj =iikl (Q Z i,j,k,l ) 2 (15)
where Q z i,j,k,l is the fourth order cumulant of Z:

Q Z i,j,k,l = E(Z i Z j Z k Z l ) -E(Z i )E(Z j )E(Z k )E(Z l )- E(Z i Z k )E(Z j Z l ) -E(Z i Z l )E(Z j Z k ) (16)

SVM classication

SVM [START_REF] Vapnik | Statistical learning theory[END_REF] is the most wildly used method for classication on multi-spectral images. SVM classify a data set into two classes by computing a separating hyperplane. A class is associated to each pixel depending on its position w.r.t the hyperplane. This algorithm is widely used in various domains to classify images (see for instance [START_REF] Fauvel | Spectral and spatial methods for the classication of urban remote sensing data[END_REF][START_REF] Zammit | Burnt area mapping using support vector machines[END_REF][START_REF] El-Naqa | A support vector machine approach for detection of microcalcications[END_REF][START_REF] Padilla | Nmf-svm based cad tool applied to functional brain images for the diagnosis of alzheimer's disease[END_REF][START_REF] Rojo-Álvarez | Support vector analysis of color-doppler images: A new approach for estimating indices of left ventricular function[END_REF]). The condition for a good classication is to nd the optimal hyperplane that separates at best two classes dened by training pixels. To do this, we seek to maximize the margin between the separating hyperplane and the points of the two training sets. If we denote the margin 2 || ω|| , the hyperplane equation is:

ω. x + b = 0. ( 17
)
To estimate the hyperplane separator (i.e. estimate ω and b), a label y = -1 or y = +1 is associated to each training pixel depending on its class. Then the hyperplane estimation problem reduces to minimize || ω|| 2 such that:

ω. x + b ≥ +1 if y i = +1 ω. x + b ≤ -1 if y i = -1 (18)

RR n°8105

It is not straightforward to minimize the expression of equation [START_REF] Prigent | Spectral analysis and unsupervised SVM classication for skin hyper-pigmentation classication[END_REF]. Nevertheless, the transformation into the dual space with Lagrange multipliers makes it a quadratic problem easy to solve:

max λ W (λ) = - 1 2 Np i=1 λ i λ j x i . x j + Np i=1 λ i . (19)
with Np i=1

λ i y i = 0, 0 ≤ λ i , ∀i ∈ [1, N ] ( 20
)
where N is the number of training pixels.

In order to classify non linear problem, a kernel is introduced in the equation ( 20):

max λ W (λ) = - 1 2 Np i=1 λ i λ j K( x i , x j ) + Np i=1 λ i (21)
We choose the Gaussian kernel because, in our experiments [START_REF] Prigent | Multi-spectral image analysis for skin pigmentation classication[END_REF], it outperforms linear, polynomial or angular kernels [START_REF] Zammit | Burnt area mapping using support vector machines[END_REF]. Whatever the classication method we use, it needs an additional lter to compensate the volumes of the face. The literature proposes several minimisation methods to solve the shape from shading inverse problem [START_REF] Zheng | Estimation of illuminant direction, albedo, and shape from shading[END_REF][START_REF] Bichsel | A simple algorithm for shape from shading[END_REF][START_REF] Crouzil | A multiresolution approach for shape from shading coupling deterministic and stochastic optimization[END_REF] introduced by Horn in [START_REF] Horn | Shape from shading: A method for obtaining the shape of a smooth opaque object from one view[END_REF]. Most of these methods tend to solve the eikonal equation. For image processing, with the Lambertian surface hypothesis the eikonal equation for a pixel at the position x, y is:

Face volume compensation

I(x, y) = I 0 (x, y) p 2 (x, y) + q 2 (x, y) + 1 (22)
where p 2 and q 2 are the derivatives of the Lambertian surface in x and y directions respectively, I 0 the albedo and I the image intensity.

In our application, we need to compensate the shading on multi-spectral data. Then, the idea is to analyse the spectrum to nd which spectral area is better adapted to estimate the shading variations. Figure 2 shows the ve bands obtained after the reduction of an 18 spectral band data cube. As one can see the last band depicted on 2(e) mainly contains the shading variations. In fact, it is justied by Figure 1. For near infra-red wavelengths (900nm), melanin and haemoglobin absorptions are very low. So the main skin components do not react to this wavelength and then the obtained image contains mainly the shading. If we assume the skin in the near infra-red image to react as a Lambertian surface, equation [START_REF] Vapnik | Statistical learning theory[END_REF] gives that we can compensate the spectral band shading by the near infra-red image. Consider that the light illuminating the skin is partly reected by the surface and partly penetrates the skin before being reected. The signal reected by the skin surface can be used as a model of the shading. The interference theory states that in this case, the signal amplitudes exhibit the following relationship:

A 2 0 = A 2 01 + A 2 02 + 2A 01 A 02 cos(φ 1 -φ 2 ), (23)
where A 0 is the amplitude of the global signal, A 01 and A 02 the amplitudes of the two reected light rays, and cos(φ 1 -φ 2 ) the phase angle between the two light rays. As a rst approximation, if we neglect the phasing angle, the relation between the shading and the skin absorption information is additive. This is why we propose to compensate the shading by subtracting the near infra-red band to all the others bands:

I c λ = I λ + z[max(I IR ) -I IR ] (24)
with

z = max(I λ ) -min(I λ ) max(I IR ) -min(I IR ) (25)
where I c λ and I λ denote respectively the compensate band and the band at the wavelength λ, and I IR the near infra-red band. The factor z allows to take into account how deep the light penetrates the skin depending on the wavelength. So the interference term that we neglect is partially taken into account in this z term. Figure 3(c) shows the eect of the subtraction based compensation on a spectral band. With this method, both shadows on the border of the image and the face volume shading are compensated. Then, when we apply this method in the PP and SVM scheme or on the ICA and thresholding classication, we have an accurate detection both on the at areas and on areas where artefacts are caused by the volume shading.

Experimental results

The proposed classication methods have been tested on 96 images. These are multi-spectral images that contain 18 spectral bands of 1000*1000 pixels. On this data set the PP plus SVM method and the ICA based method are competitive and give equivalent quality results. The main dierence between these two methods is the operator dependency. In fact SVM ask the operator to select training pixels whereas the ICA thresholding ask the operator to choose the value of the threshold. The second method is easier for an operator to use but include subjectivity.

To evaluate the classication on these 96 images, we partition them into 3 groups. The rst one contains 27 images that are qualied as easy in the sense that these images contain mainly skin in the at area of the cheek. The second group qualied as intermediate contains more artefacts like eye, hair or nose. This group represents 37 of the 96 images. The third group contains 31 images with a lot of artefacts.

As the Stamatas et al. algorithm and the ICA based methods are equivalent from an operator input point of view, we propose to compare them rst. For both method, we estimate the threshold that maximizes the correspondence with the dermatologist analysis in term of surface. Now, we compare the surface evaluation of ICA based method and SVM on the whole set (ie. 96 images). Table 1 shows the percentage of correspondence between the dermatologist area estimation in a scale from 0 to 6 and the algorithm surface estimation in percentage for both the ICA based method and PP-SVM. It is natural in the table 1 that the percentages for the ICA based method are better since this method use the dermatologist clinical analysis to calculate the pathological area size. Although the correspondence between obtained classications and dermatologist measurement is quite satisfactory, some over-estimation of the pathological area appears mainly for the groups 2 and 3 where the correspondence percentage decrease.

Finally, experiments show that the ICA based method and the PP-SVM suit well our problem.

However, these techniques are not robust enough to the data variability appearing in a clinical 3 Generalisation to a complete study

The classication scheme proposed in the previous section is not usable on a full study. First, the algorithms are not robust enough to image set variability. Second, for the ICA based method, the operator has to select a source and a threshold for this source. For the SVM, the operator has to select training pixels on each image. This is not compatible with a practical use on a whole study, containing about 100 subjects. In this section, we propose a protocol that allows both to automatize the algorithms as much as possible and improves the robustness of the classication.

We focus on the SVM based method since it is the one that seems to be the easier to automatize.

To this end, we propose a scheme to train a SVM once for all the images, and then, we add a interactive classication step to avoid possible over or miss-classication.

RR n°8105

Global training

To make a global training for all the images, we rst need to normalize them. Images have more or less shading and non skin elements. Moreover, natural skin darkness is dierent from one patient to another. Let's detail the two steps:

Fourier ltering

In order to remove as many artefacts as possible in all the images, we propose to add a Fourier ltering step between the projection pursuit and the face volume compensation. Indeed, in our images, we observe that the main undesired parts are in the low frequencies areas. The eyes, the nose, or the lips are inside the face volume (in opposition to the at area of the cheek), and the face volume represents low frequency variations in our images. Another remaining artefact not Inria completely corrected by the face volume compensation step is the lighting inhomogeneity which is also contained in low frequency in our images. To make the Fourier ltering, let's consider I R a reduced image by projection pursuit. We rst apply a Hamming 2D window to each band I R (b) of I R to avoid oscillations [START_REF] Gonzalez | Digital image processing[END_REF]:

∀b ∈ [0, n b ], HI R (b) = I R (b).HW, (26)
with n b the total number of bands of I R , and

HW (i, j) = 0.54 -0.46 * cos   π * i -n l 2 n l 2 + i -nc 2 n c 2   (27)
where n l and n c are respectively the number of lines and columns of I R . Then, we apply a 2D Fourier transform to each band b of HI R [START_REF] Gonzalez | Digital image processing[END_REF]:

F (HI R )(u, v, b) = 1 nl * nc nl x=1 nc y=1 HI R (x, y, b)e -2iπ( ux nl + vy nc ) (28)
Finally we apply a low frequency mask M in the Fourier space and compute the Fourier inverse transform to obtain I R F [START_REF] Gonzalez | Digital image processing[END_REF]:

∀b ∈ [0, nb], I R F (b) = F -1 (F (HI R )(b).M ) , (29)

Global training

In this section, we propose to use SVM with a single training for the whole studies. SVM is applied on the ltered images obtained with the method described in section 3.1.1. To this end, each band has to be radiometrically normalized. In fact, the SVM will dene a single separator for the whole data set. To perform this normalization, we use a histogram specication [START_REF] Gonzalez | Digital image processing[END_REF] that makes each band of I R F having a at histogram. An example of a ltered and normalized band is shown in Figure 7(d). The image 7(e) shows how important the Fourier ltering is. If there is not such a ltering, the histogram specication doesn't eliminate enough shading. When images are ltered and normalized, we train the SVM on selected training images. These images have to be selected carefully. The images must not be too atypical otherwise the SVM will not be able to generalize to the whole study. Then, on each chosen image, an operator species healthy and pathological areas. Finally, all the marked pixels are concatenated and used to train a SVM. All the images can then be classied with this SVM.

RR n°8105

Interactive classication tool

The classication proposed in the previous section can still fail for non typical images. If there are too many artefacts in an image or if the contrast between healthy and pathological area is to low, the trained separator will not be adapted to classify correctly the image. Furthermore, the SVM classier has a non zero over or miss-classication rate. In our application, we need to be sure that the classied areas are pathological to correctly evaluate a treatment. This is why we propose a protocol that we call interactive classication to allow an operator to easily make corrections w.r.t the classication.

There are two types of corrections that can be chosen by the operator: remove over-segmentation and add miss-classication.

To enable the operator to remove over-segmentation, we perform a connected component analysis [START_REF] Gonzalez | Digital image processing[END_REF] on the SVM classication map. Then the operator can click on a component he/she wants to add or remove from the nal classication.

If the SVM miss-classies an area, a segmentation map is needed to allow the operator to add a segment to the classication. For our application we perform the segmentation on I R F . In the literature a lot of segmentation algorithms have been proposed to deal with multi-spectral images [START_REF] Tarabalka | Spectral-spatial classication of hyperspectral imagery based on partitional clustering techniques[END_REF]. The two main methods are split and merge segmentation or unsupervised classication associated with connected component analysis [START_REF] Gonzalez | Digital image processing[END_REF]. To reduce the computation time as much as possible we use the second approach. We use the Gaussian mixture classication algorithm as proposed in [START_REF] Tarabalka | Spectral-spatial classication of hyperspectral imagery based on partitional clustering techniques[END_REF]. We rst perform a classication on I R F with a Gaussian mixture model. Each obtained component is partitioned with connected component analysis. The nal segmentation map is obtained by concatenation of the segments of each Gaussian component on a single map.

The global classication scheme is drown in Figure 8. Figure 9 and Figure 10 show screen-shots of the classication GUI we developed. To maximize the chance to segment the area of interest, Inria and the interactive selection tool. In fact, for the rst study we got 58.7% of correlation between the SVM algorithm (see table 1) and the clinical analysis. For the second study (see Figure 13)

we got only 45.1% of correlation between the SVM algorithm and the clinical analysis. Let add two remarks about the presented results. An important point is that the interactive classication tool makes the operator work at the output of the algorithm. This insure a minimisation of over and miss classication not possible with the SVM algorithm alone. A second remark is that, even though the correlation curves in Figure 6 seems better than the one in Figure 12, the classication in the second case ts better the pathology. This dierence is due to the method used to compute the threshold to obtain the results in Figure 6 knowing the dermatologist analysis.

Conclusion

In this report, we have proposed a new scheme that allows to classify hyper-pigmentation lesions of skin using multi-spectral images. The obtained results on two clinical studies tend to show that the method is robust. The fact that the operator interacts at the last step of the classication can be seen as a positive thing. It allows both to make a miss or over-classication control and avoid the classication to be based only on machine learning techniques which are often contested Inria in medical applications. From the obtain classication, severity criteria can be designed to characterize the disease and evaluate a patient evolution or a treatment ecacy. For example, we designed a contrast criterion in [START_REF] Prigent | Estimation of an optimal spectral band combination to evaluate skin disease treatment eciency using multi-spectral images[END_REF] and are currently working on spatial and homogeneity criteria. (a) [7] B.F. Jones. A reappraisal of the use of infrared thermal image analysis in medicine. IEEE Inria

  . The most popular solution is to transform the RGB representation of a color image to the standard CIE L * a * b representation. Then the luminance band L * or the RR n°8105 IT A index [2, 3] computed with the L * and b * bands of the CIE L * a * b representation can be thresholded to give a classication map of the disease. Concerning the spectral analysis of the skin, several methods have been proposed to evaluate the quantity of a skin component. This problem can be referred to as unmixing or source separation, applied on the measured spectrum.

  where a[ deoxy_Hb ] and b[ deoxy_Hb ] are coecients from the linear model of the deoxy-hemoglobin absorbance in the range 630-700 nm. Considering the problem of pigmentation, with multispectral data, this algorithm provides a quantication map of the melanin. Thresholding this map gives a classication map of the pigmentation. Other algorithms, initially proposed within the signal processing community, can provide unmixing on multi-spectral data. In this report,

Figure 1 :

 1 Figure 1: Theoretical absorption of melanin and haemoglobin (Y-axe) depending on the wavelength (X-axe)

  An example of classication by PP and SVM is shown in Figure4(b), and a reference manual classication is shown in Figure2(f ). As one can see, the classication is quite accurate in the at areas whereas there is no detection of the pathology in areas corrupted by the volumes of the face.Concerning ICA, experimentations show that a single component is suciently representative of the melanin concentration in the skin. This is the reason why we perform a classication in a single component. This classication can be done by SVM. Nevertheless, we observe that thresholding this component provides accurate results. In Figure5(b) the classication is accurate in the at areas, but there are a lot of false detections in areas concerned by shading.

  Figure 7(a) shows the second band of the reduced data cube. Figure 3(b) shows the result obtained when dividing the second Inria band of the reduced cube by the near infra-red band of the reduced cube. As one can see, shading on the border of the image are well compensated. They became white in the compensated image and are now not interfering with the dark gray of the pathological areas. But the compensation is not ecient in the areas where the shading is caused by the volume of the face. If we perform such a compensation and compute a classication we obtain false classication (see Figure 4(c) and Figure 5(c))We thus have rejected the Lambertian assumption.

Figure 6 (

 6 Figure 6(b) shows the correlation curves between the dermatologist estimation of the pathological

Figure 2 :

 2 Figure 2: Spectral bands of the reduced data cube by projection pursuit (a-e), and a manual classication of the hyper-pigmentation (f ).

(a) 2 Figure 3 :

 23 Figure 3: Inuence of the shading compensation on the second band of the reduced data cube

  SVM segmentation with shading compensation by the division based method (d) SVM segmentation with shading compensation by the substraction based method

Figure 4 :

 4 Figure 4: Classication results with projection pursuit depending on the shading compensation method

  (a) Reconstructed color image (b) ICA based segmentation (c) ICA based segmentation with shading compensation by the division based method (d) ICA based segmentation with shading compensation by the substraction based method

Figure 5 :Figure 6 :

 56 Figure 5: Classication results with the ICA based method depending on the shading compensation method

withF - 1 (F

 1 I (u, v)e 2iπ( ux nl + vy nc )[START_REF] Crouzil | A multiresolution approach for shape from shading coupling deterministic and stochastic optimization[END_REF] where I represents a monochrome image and F I its Fourier transform. An example of the ltered image is shown in Figure7(c). As one can see, the surrounding of the eye and the nose are better ltered than with the face volume compensation method alone shown in Figure7(b).

  (a) Initial band (b) Band with infra-red compensation (c) Band with infra-red compensation and Fourier ltering (d) Band with infra-red compensation, Fourier ltering and histogram specication (e) Band with infra-red compensation and histogram specication

Figure 7 :

 7 Figure 7: Inuence of ltering on one band.

Figure 9 :

 9 Figure 9: Screenshot of the software that allows to do the interactive classication, rst example. Top left: segmentation obtained with the Fourier lter that cut 20% of the low frequencies, top right: segmentation obtained with the Fourier lter that cut 40% of the low frequencies, bottom left one band of the original image, bottom right SVM chosen component

Figure 10 :

 10 Figure 10: Screenshot of the software that allows to do the interactive classication, rst example. Top left: segmentation obtained with the Fourier lter that cut 20% of the low frequencies, top right: segmentation obtained with the Fourier lter that cut 40% of the low frequencies, bottom left one band of the original image, bottom right nal classication. The nal classication has been obtained by clicking two regions in the segmentations map (regions in white on the top quadrants).

Figure 11 :

 11 Figure 11: Images used for the global training. The rst row shows color reconstructions of the initial images. The second row shows a ltered band with the location of the training areas. Red rectangles show training pathological areas, and blue rectangles show training healthy areas.

Figure 12 :

 12 Figure 12: Correlation between the clinician and algorithm measurements on (a) rst study containing 48 patients and (b) the second study containing 44 patients.

Figure 13 :

 13 Figure 13: Correlation between the clinician and surface measurements based on a SVM algorithm trained on each images of the second study containing 44 patients.

  Data reduction with ICA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3 SVM classication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.4 Face volume compensation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.5 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Global training . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.1.1 Fourier ltering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

	1 Introduction	3
	2 classication	4
	2.1	Data reduction with Projection Pursuit . . . . . . . . . . . . . . . . . . . . . . .	5
	2.2
			9
	3 Generalisation to a complete study	11
	3.1

3.1.2 Global training . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 Interactive classication tool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.3 Obtained results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1 Introduction

Table 1 :

 1 Correspondence of surface measurement between dermatologist and algorithms

		ICA PP-SVM
	Group 1	81.5%	63%
	Group 2	75.7%	62.2%
	Group 3	62.5%	52%
	Total	73%	58.7%
	study.

Conclusion 16

Prigent & Descombes & others

classicationIn order to classify pathological areas on multi-spectral images we use the classical scheme which consists in rst, reducing the spectrum and then classifying the reduced data with a supervised Inria

Prigent & Descombes & others this distance, the most common indices are the Bhattacharyya distance and the Kullback-Leibler divergence[START_REF] Rellier | Texture feature analysis using a Gauss-Markov model in hyperspectral image classication[END_REF]. For classication purpose more specic indices can be used. For example, an index based on histogram analysis is proposed in[START_REF] Gomez | Precise acquisition and unsupervised segmentation of multi-spectral images[END_REF]. Nevertheless, such indices require manual parameter specication, and do not improve signicantly the classication accuracy. This is why we prefer to use the symmetrical Kullback-Leibler deviation:

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Acknowledgment

S. Prigent, X. Descombes and J. Zerubia would like to thank Galderma R&D for partial funding this research work and for providing the data. Material presented in this report has been partially published earlier in [27,18].

we perform twice the segmentation: one with a Fourier high-pass lter that cut 20% of the low frequencies and one with a Fourier high-pass lter that cut 40% of the low frequencies. The operator can click on the segment of these two maps to add it in the nal classication, or chose the SVM classication. On the Figure 9

Obtained results

We use the proposed classication approach on two clinical studies. The rst one contains 48 patients, with two images per patient. The second one contains 44 patients, with two images per patient. We trained the SVM only once for both studies with three patients selected from these studies. These three patients (see Figure 11


Mourad Amziani

Tarek Melliti

Samir Tata

A Generic Framework for Service-based Business Process Elasticity in the Cloud

Cloud computing is a new model for the provisioning of dynamically elastic and often virtualized resources at the levels of infrastructures, platforms and software. Cloud platforms are being increasingly used for the deployment and execution of service-based business processes (SBPs). Nevertheless, the provisioning of elastic infrastructures and/or platforms is not sufficient to provide users with elasticity at the level of SBPs. Therefore, there is a need to provide SBPs with mechanisms to scale their resource requirements up and down whenever possible. This can be achieved using mechanisms for duplicating and consolidating business services that compose the SBPs. In this paper, we propose a formal model and a generic framework for elasticity of SBPs.

Introduction

Cloud computing is a new delivery model for IT services based on Internet protocols. It typically involves provisioning of dynamically scalable and often virtualized resources at the infrastructure, platform and software levels. Cloud environments are being increasingly used for deploying and executing business processes and particularly service-based business processes (SBPs) that are made up of components that provide business services. One of the expected facilities of cloud environments is elasticity at different levels.

At the platform as a service (PaaS) level, the deployed processes should be provided with platform mechanisms that can scale up and down whenever needed. In this context, we have conducted studies of existing application servers and SBP engines. These classical platforms are not elastic [START_REF] Mohamed | Web service micro-container for service-based applications in cloud environments[END_REF]. For that reason, we have developed a new model for service deployment called micro-container [START_REF] Yangui | Scalable service containers[END_REF]. Our approach was based on a simple idea that consists in dedicating a microcontainer with minimal and personalized functionalities to manage the life cycle of each deployed services. With this idea we have shown the elasticity of services deployed at the PaaS level can be ensured [START_REF] Yangui | Scalable service containers[END_REF]. In addition, we have shown that elastic micro-containers can be used to host service-based application.

Nonetheless, provisioning of elastic platforms, e.g. based on micro-containers, is not sufficient to provide users with elasticity of the deployed business process (at the Software as a Service (SaaS) level). Therefore, SBPs should be provided with elasticity so that they would be able to adapt to the workload changes while ensuring the desired functional and non-functional properties. In this paper we address elasticity at the level of SBPs that mainly raises the following questions.

-What mechanisms should be developed to perform elasticity of SBPs? -How to evaluate elasticity strategies of SBPs? Performing elasticity consists in providing cloud environments with mechanisms that allow deployed SBPs to scale up or down. To scale up a SBP, elasticity mechanisms have to create, as many copies as necessary, of some business services (part of the considered SBP). To scale down a SBP, elasticity mechanisms have to remove unnecessary copies of some services.

Many strategies that decide on when SBP elasticity is performed can be proposed. It would be useful for a Cloud provider to have an evaluation framework in order to make a better decision on the elasticity strategy to adopt.

In this paper, we propose a formal model for SBP elasticity and a framework to evaluate elasticity strategies.

Model for SBPs elasticity

We are interested in this paper in modelling elasticity of SBPs. A SBP is a business process that consists in assembling a set of elementary IT-enabled services. These services realise the business activities of the considered SBP. Assembling services into a SBP can be ensured using any appropriate service composition specifications (e.g. BPEL). Elasticity of a SBP is the ability to duplicate or consolidate as many instances of the process or some of its services as needed to handle the dynamic of received requests. Indeed, we believe that handling elasticity does not only operate at the process level but it should operate at the level of services too. It is not necessary to duplicate all the services of a considered SBP while the bottleneck comes from some services of the SBP.

SBP modeling

We model the SBP using Petri nets. Many approaches model SBPs using petri nets, but instead of focusing on the execution model of processes and their services, we focus on the dynamic (evolution) of loads on each basic service participating in the SBP's composition. In the proposed model, each service is represented by a place. The transitions represent calls transfers between services. Definition 1. A SBP load model is a petri net N =< P, T, P re, P ost >:

-P : a set of places (represents the set of services involving in a SBP).

-T : a set of transitions (represents the call transfers between services according to the SBP behavioural specification). -P re : P × T → {0, 1} -P ost : T × P → {0, 1} For a place p and a transition t we give the following notations:

-p • = {t ∈ T |P re(p, t) = 1}. • p = {t ∈ T |P ost(t, p) = 1} -t • = {p ∈ P |P ost(t, p) = 1}. • t = {p ∈ P |P re(p, t) = 1} Definition 2.
Let N be a Petri net, we define a net system S = N, M with M : P → N a marking that associates to each place an amount of tokens.

The marking of a Petri net represents a distribution of calls over the set of services that compose the SBP. A Petri net system models a particular distribution of calls over the services of a deployed SBP. Definition 3. Given a net system S = N, M we say that a transition t is fireable in the marking M , noted by The transition firing represents the evolution of the load distribution after calls transfer. The way that calls are transferred between services depends on the behaviour specification (workflow operators) of the SBP.

M [t iff ∀p ∈ • t : M (p) ≥ 1.

Elasticity operations

Place duplication

As noted before places represent services deployed on containers. The marking of a place denote the number of the current instances (or requests) of the service. Each service has a maximal capacity over what the QoS of the service decrease and can leads to the stuck of the container and by the same way the crash of the service. Giving to the container more memory and/or more CPU time will not change the issue of the problem [START_REF] Yangui | Scalable service containers[END_REF]. A solution to this problem is to duplicate the service without changing underlying SBP. Definition 5. Let S = N, M be a net system and let p ∈ P , the duplication of p in S by a new place p c ( ∈ P ), noted as D(S, p, p c ), is a new net system S ′ = N ′ , M ′ s.t

-P ′ = P ∪ {p c } -T ′ = T ∪ T ′′ with T ′′ = {t c |t ∈ ( • p ∪ p • )} -P re ′ : P ′ × T ′ → {0, 1} -P ost ′ : T ′ × P ′ → {0, 1} -M ′ : P ′ → N with M ′ (p ′ ) = M (p ′ ) if p ′ = p c
and 0 otherwise. The P re ′ (respectively P ost ′ ) functions are defined as follow:

P re ′ (p ′ , t ′ ) =        P re(p ′ , t ′ ) p ′ ∈ P ∧ t ′ ∈ T P re(p ′ , t) t ∈ T ∧ t ′ ∈ (T ′ \ T ) ∧ p ′ ∈ (P \ {p}) P re(p, t) t ∈ T ∧ t ′ ∈ (T ′ \ T ) ∧ p ′ = p c 0 otherwise. P ost ′ (t ′ , p ′ ) =        P ost(t ′ , p ′ ) p ′ ∈ P ∧ t ′ ∈ T P ost(t, p ′ ) t ∈ T ∧ t ′ ∈ (T ′ \ T ) ∧ p ′ ∈ (P \ {p}) P ost(t, p) t ∈ T ∧ t ′ ∈ (T ′ \ T ) ∧ p ′ = p c 0 otherwise.

Place consolidation

When a service has few calls, the containers that host its instances use more resources than required for the same QoS. As a dual operator to duplication we define the consolidation or merging operator that removes a copy of a service. Definition 6. Let S = N, M be a net system and let p, p c be two places in N with p = p c , the consolidation of p c in p, noted as C(S, p, p c ), is a new net system S ′ = N ′ , M ′ s.t

-N ′ : is the net N after removing the place p c and the transitions

(p c ) • ∪ • p c -M ′ : P ′ → N with M ′ (p) = M (p) + M (p c ) and M ′ (p ′ ) = M (p ′ ) if p ′ = p. Example 1. Figure 1-(a)
shows an example of nets system that represents an SBP. Figure 1-(b) is the resulted system from the duplication of s2 1 in (a). Figure 1(c) is the consolidation of the place s2 1 in its copy s2 2.

A generic framework for SBPs elasticity

Usually in the Cloud, a set of policies is implemented to guarantee some SLA properties to the deployed applications. These policies are implemented in what is usually called controller. In our case, we are interested in elasticity policies of services that compose a SBP. In order to achieve this, we want to develop a controller to provide an optimal ratio QoS and allocated resources of a SBP. The proposed controller (Figure 2)-(a) is able to perform three actions:

-Routing: Routing decision is about the way a load of services is routed over the set of their copies. It determines under which condition a given transition (call transfer) is fired. One can think of routing as a way to define a strategy to control the flow of load according to some rules e.g. a call is transferred iff the resulted marking does not violate the capacity of the services. If we consider the three actions that can be performed by an elasticity controller, any combination of conditions associated with a decision of routing, duplication and consolidation is an elasticity strategy. The strategy is responsible of making decisions on the execution of elasticity mechanisms i.e. deciding when and how to use these mechanisms. Several strategies can be used to manage the SBP elasticity [START_REF] Ghanbari | Exploring alternative approaches to implement an elasticity policy[END_REF]. The abundance of possible strategies requires evaluating these strategies before implementing them. Our goal here is not to propose an additional elasticity strategy, but a framework, called generic controller that allows the implementation and evaluation of SBPs elasticity strategies.

We model the controller as a high level Petri net (HLPN). The structure of the controller is shown in Figure 2-(b). The controller HLPN contains one place (BP) of type net systems (SBPs). The marking of this place is modified by three transitions that represent the three elasticity mechanisms (Routing, Duplication and Consolidation). Each of these transitions is guarded by a generic condition. Implementing a strategy consists then in instanciating the three generic conditions. The reachability graph resulted from the instanciated controller represents the different evolutions of the SBP according to the strategy. Using HLPN analysis tools, the evaluation of the strategy can be processed by model-checking its reachability graph.

Related Work

The elasticity in the Cloud has been studied in the past. Proposed approaches use generally sets of rules to make decisions about the elasticity of the infrastructure. In this kind of approaches, several techniques have been used. In [START_REF] Duong | A framework for dynamic resource provisioning and adaptation in iaas clouds[END_REF] the authors propose to add or remove VMs according to demands. In [START_REF] Han | A deployment platform for dynamically scaling applications in the cloud[END_REF][START_REF] Bi | Dynamic provisioning modeling for virtualized multi-tier applications in cloud data center[END_REF] the authors propose to calculate the optimal number of VMs to be deployed according to variations of demands.

The use of duplication/consolidation mechanisms to provide elasticity have been considered in the area of dynamic service deployment [START_REF] Chrysoulas | A decision making framework for dynamic service deployment[END_REF][START_REF] Weissman | A framework for dynamic service adaptation in the grid: Next generation software program progress report[END_REF]. The proposed mechanisms allow the duplication/consolidation of the entire SBP (and so, of all its services) while the bottleneck may come from some services of the SBP.

At the best of our knowledge the approaches for elasticity are interested in the infrastructure level of cloud environments (IaaS). As stated before, ensuring elasticity at the IaaS level is not sufficient to provide users with elasticity of deployed SBPs. Similarly, ensuring elasticity at the PaaS level is not enough to ensure elasticity of deployed SBPs. We believe that elasticity should be handled and tuned at different levels of cloud environments. The work we present in this paper is novel in the sense that it (1) tackles the problem of elasticity at the SaaS level and (2) proposes a generic framework for evaluating SBPs elasticity.

Conclusion

This paper addresses the problem of elasticity of service-based business processes (SBPs) deployed in cloud environments. Unlike existing work, the proposed approach tackles the elasticity at the level of SBPs. To perform elasticity we proposed using Petri nets tow operations: duplication and consolidation. In addition, we have proposed a framework to evaluate SBPs elasticity. As perspectives of this work, we are working on the implementation of the elasticity operations into CloudServ (a PaaS under development within the French FUI CompatibleOne project).

Definition 4 .

 4 The firing of a transition t in marking M changes the marking of the net system to M ′ s.t. ∀p : M ′ (p) = M (p) + (P ost(t, p) -P re(p, t)), we note the transition by M [t M ′ .

Fig. 1 .

 1 Fig. 1. Example of the elasticity of a SBP

Fig. 2 .

 2 Fig. 2. General architecture of the controller