Muhammad Ali Memon
email: muhammad-ali.memon@enit.fr

Agnès Letouzey
email: 2agnes.letouzey@enit.fr

Mohammed Hedi Karray
email: mohamed-hedi.karray@enit.fr

Bernard Archimède
email: 4bernard.archimede@enit.fr

Toulouse Archive Ouverte

Keywords: Interoperable and Distributed Scheduling, Multi-Agent Systems, Collaborative Transportation Planning, Third Party Logistics, Ontology

Today enterprises have to distribute their final products to far away consumers. It is difficult and not cost effective for these enterprises to manage their own transport vehicles. Thus, they outsource their transportation tasks to third party logistics (3PL) companies. These 3PL companies take transport orders from several clients and try to group them in the vehicles to utilize their resources at maximum. An issue of interoperability arises, when 3PL companies have to process different transport orders arriving from several clients in different formats and terminologies. Secondly, how 3PLS will collaborate with other 3PL companies following different working standards and also for collaboratively delivering transport orders which single 3PL cannot deliver alone due to its limited operational geographic area. Interoperability to achieve collaborative transportation planning is our concern in the context of this paper. Interoperability is a key issue for collaboration, especially in case of heterogeneous environment, when entities trying to collaborate have different ways of functioning and follow certain standards specific to their organizations. So the objective of this paper is to present a distributed and interoperable architecture for planning transportation activities of multiple logistics enterprises aiming at a better use of transport resources and by grouping transport orders of several manufacturers for each effective displacement.

Introduction

More often, companies wishing to reach the far away customers could not possibly purchase their own fleet of vehicles to transport their goods. These companies contact third party transportation companies to ship their products, same as a courier company. This need led emergence of Third Party Logistics enterprises (3PL) [START_REF] Marasco | Third-party logistics: A literature review[END_REF]. In that case, suppliers can outsource their complete transportation tasks to 3PL enterprises and then these 3PLs take charge of whole transportation process. To fulfil customers' demands and improve the performance of supply chains, 3PL must manage its own resources and collaborate with other 2PL (carriers) and 3PL companies to reach far away customers at lower price. Additionally these 3PLs will group together several transport orders sharing similar origins or destinations in vehicles to deliver them collectively. Eventually minimizing number of transport travels and minimizing environmental pollution. This collaboration involves a good understanding of exchanged information between clients and 3PL and between 3PLs, especially about locations, product constraints, vehicles type, etc. Clients will generate their transport orders by their own specific ways, which will not be understandable by 3PLs. There is a need of an interoperable mechanism which can transform the information for that 3PL in an understandable form. This transformation should deliver correct information and without any distortion. Similarly for communication in case of multiple 3PLs, they need an intermediate mechanism to understand each other's working methods in order to collaborate. One solution is to let each entity work in its own manner by using their terms, but defining them using their local ontologies and let interoperable service utilities (ISU) handle the transformations on the basis of common semantics [START_REF] Zbib | Interoperability Service Utility Model and its Simulation for Improving the Business Process Collaboration[END_REF][START_REF] Karray | A contextual semantic mediator for a distributed cooperative maintenance platform[END_REF]. Thus, the schedule of all transport orders has to be achieved by several interoperable scheduling systems. The work presented in this paper proposes ontology based interoperable framework to support collaborative transport planning for 3PL enterprises in distributed manner. The objective is to describe the I-POVES Interoperable (Path Finder, Order, Vehicle, Environment, and Supervisor) for improving collaboration and interoperability between 3PL enterprises and clients. After a state of the art on the latest research on interoperability for transportation planning, we describe the interoperable architecture of the POVES model and the associated ontologies. Finally, we conclude with future work.

State of the art

Several approaches have been proposed to solve transportation planning problem. Sauer and Appelrath [START_REF] Sauer | Integrating transportation in a multi-site scheduling environment[END_REF] proposed a centralized approach with a global scheduler, which schedules transportation planning activities. They model the problem by a 5-tuple (R, P, O, HC, SC), where R denotes the set of required resources, P the set of products, O the set of actual orders and HC and SC the sets of hard and soft constraints, respectively. They use a rule-based approach and heuristics to produce several scheduling strategies. This approach is centralized and is limited to the planning of transportation activities of a single enterprise. The need for confidentiality limits the scope of centralized approaches. Baykasoglu and Kaplanoglu [START_REF] Baykasoglu | A multi-agent approach to load consolidation in transportation[END_REF] proposed a multi-agent approach to address collaborative transportation problem. This approach is based on cooperation between transport order agents and truck agents, which proposes grouping multiple orders together in a vehicle. In this approach, transport order agent is bound to accept the proposition from one truck agent, which provides a nonstop delivery from origin to destination. However, in reality a truck rarely alone transports a transport order. A transport order requires, most often, several trucks.

Takoudjou R. et al [START_REF] Takoudjou | A Hybrid multistart heuristic for the pickup and delivery problem with and without transshipment 9th International Conference on Modeling[END_REF] propose a multi-agent heuristic to address the transport problem with transhipment. Their methodology is decomposed in four steps. In first step, they calculate PDP (pickup and delivery solution) without transhipment/ Cross Docking solution for all random requests. In second step, they try to optimize the PDP solution with VND (Variable Neighbourhood Descent method) using Path Relinking. In the third step, they calculate PDPT (PDP with transhipment) solution, compare it with PDP solution and keep the best one. This whole procedure is repeated to the number of iterations. This work makes an assumption that number of vehicles is not fixed and if no vehicle can satisfy a request because of the noncompliance with the constraints (vehicle capacity, time windows, etc.), a new route is created with a new vehicle to welcome the considered request. It is not realistic to create a new vehicle each time a transport order needs one. Moreover, this method calculates PDP solution without transhipment improves it by optimizing it and then destroys the PDP solution to obtain PDPT solution with transhipment. In further studies a simulation framework is presented by Sprenger and Mönch [START_REF] Sprenger | A simulation framework for assessing the performance of cooperative transportation planning algorithms[END_REF] for assessing the performance of cooperative transportation planning and isolated transportation planning. Mes et al. [START_REF] Mes | Interaction between intelligent agent strategies for realtime transportation planning[END_REF] study the interaction between intelligent agent strategies for realtime transportation planning. A multi-agent theoretical approach on dynamic transportation planning is given in [START_REF] Kozlak | Multi-agent environment for dynamic transport planning and scheduling[END_REF].

Above mentioned papers are interested only for transportation planning and do not take into account the interoperability aspect. Following papers discuss the interoperability for exchanging information. Niarki and kim [START_REF] Niaraki | Ontology based personalized route planning system using a multi-criteria decision making approach[END_REF] propose an ontology based personalized route planning system which uses multi-criteria decision making from user/ decision maker. Whether, a certain route is better than other strongly depends on environmental situations and user preferences. In addition to these criteria, the impedance of road plays a very important role in route planning. Impedance factors involved in determining the travel time are the volume of the traffic, the type of the road, the road width, number of junctions and turns etc. This approach models the decision making criteria using ontology and apply an impedance function in route finding algorithm to find the personalized route for the user(s).

Paul Davidson et al [START_REF] Davidsson | Inter-Organization Interoperability in Transport Chains Using Adapters Based on Open Source Freeware[END_REF] have developed an adapter based open source freeware to exchange information between business systems. System was tested on two case studies for improving transport activities for small medium enterprises, based in Sweden. S. Smith and M.Becker [START_REF] Becker | An Ontology for Multi-modal Transportation Planning and Scheduling[END_REF][START_REF] Smith | Using a Scheduling Domain Ontology to Compute User-Oriented Explanations[END_REF] propose an ontology based toolkit for constraint based scheduling system called ozone. The ozone ontology provides a framework for analysing the information requirement of a given target domain, and a structural foundation for constructing an appropriate domain model. We here are interested to use the aspect of interoperability for solving collaboration problem in transport planning domain.

P.O.V.E.S. MULTI-AGENT MODEL 1.3.1 Description of model

The POVES multi-agent model (Fig. 1.1) is developed for collaborative transportation planning activities. It is inherited from SCEP multi-agent model, which is being used with success for manufacturing planning since years. Limitations restricted SCEP for transportation planning [START_REF] Memon | Towards a distributed framework for transportation planning: A food supply chain case study[END_REF], due to that POVES emerged after overcoming these limitations. POVES introduces an indirect cooperation between two communities of agents, Order agents called (O) and vehicle agents called (V), leading to a high level of co-operation. Each order agent manages one transport order from first party logistics (1PL). Each vehicle agent manages one vehicle of the organization. A supporting agent "Path Finder" elaborates for a transport order the traveling route between pickup and delivery locations. The cooperation between order agents and vehicle agents is performed synchronically through the background environment agent E. The supervisor agent S controls the model functioning. The detail working procedures and functioning of POVES model is given in [START_REF] Ali | A Multi-Agent Distributed Framework for Collaborative Transportation Planning[END_REF].

Fig. 1.1 POVES model

Limitations of the model

This model is well suited for transportation planning in case of only single 3PL enterprise with a fleet of its own vehicles. However a single 3PL enterprise operates in a limited region and it is unlikely possible that it can fulfil TO entirely. It is more often that, TOs have to be delivered to faraway clients in a region outside the reach of this 3PL. It must collaborate with other 3PL enterprises that operate in other regions to make the delivery of the products to faraway clients. Moreover, if more than one 3PLs operating in the same region entirely or partly, they will increase the chance of TO delivery on time, as one of either must have a vehicle available to deliver the order on time. Additionally in POVES, TOs arrive from several clients, but these TOs should be in the same format that should be compliant with the format understandable by Path Finder agent to find the elementary activities. In reality, customers generate their TOs in different formats that are not interoperable by the 3PL enterprises, because each of the customers has its own way of interpreting and representing locations, paths, etc. Similarly, each of 3PL enterprises defines their elementary activities and vehicle parameters according to their own methods and formats. There is need of some intermediary mechanism that could understand all the formats in order to produce better results, which is currently not available in the POVES previously presented. For these reasons POVES model must be evolved.

Interoperable-POVES

In order to take into account limitations in the preceding section, we propose an evolved version of POVES model shown in Fig 1 .2. In this model, we add ontologies and interoperable service utilities (ISU) in order to achieve interoperability to treat different formats. Ontology provides a shared vocabulary (terminologies), which can be used to model a knowledge domain. Each customer who generates TOs, defines them using the terminologies from their local ontology. Similarly, each transporter (3PL) has also its local ontology to define its elementary activities and vehicle parameters, which is comprehensible only by this transporter. In addition to that, we add a global ontology, which provides a federation of concepts. Those concepts map with the concepts of all the local ontologies on the basis of common semantics [START_REF] Karray | A contextual semantic mediator for a distributed cooperative maintenance platform[END_REF]. Global ontology has consistent and coherent information and has standard and shared terminologies.

Furthermore, in order to work on that global ontology standard terminologies, we require interoperable service utilities, which will be used for matching and translation of terminologies from local ontologies to global ontology and vice versa. In I-POVES, virtual customer presents an ISU that will match and translate the enterprise's "Customers local ontologies" terminologies to global ontologies' terminologies and then communicate with Path Finder to find the route. Path Finder finds a route based on the terminologies of global ontology. Then, virtual customer will send computed route tasks to environment for planning. Similarly, virtual 3PL is also an ISU that will retrieve the tasks from environment. Those tasks are represented in the form of global ontology standard and translated and sent into the format of local ontologies for respective 3PLs by ISU. After 3PL planning, virtual 3PL sends back to the environment propositions received by 3PLs after translating them from transporter's local terminologies to global ontologies. Virtual 3PL will also translate the elementary activities of each 3PL and their vehicle parameters and send them to Path Finder to update its database before commencement of the planning process, each time Path Finder agent is activated. Ontologies presented in this paper are loosely inspired from the Ozone ontology developed by S.Smith and al [START_REF] Becker | An Ontology for Multi-modal Transportation Planning and Scheduling[END_REF][START_REF] Smith | Using a Scheduling Domain Ontology to Compute User-Oriented Explanations[END_REF]. Transporters even following the same standards but residing in different countries will express locations differently as each country has its specific way of defining geographical divisions. For example in France there are regions and departments and in Pakistan there are provinces, divisions and districts. Furthermore, transporters operating even in the same region to their clients have heterogeneous way of using locations name. In our example transporter defines TAR and TOU as abbreviations of Tarbes and Toulouse, which may not be understandable by the client placing the order. This antagonism generates the need of a global ontology. It represents the concepts that are semantically similar used in local ontologies to follow a single standard during the planning process.

Fig. 1 .

 1 Fig. 1.2 I-POVES modelThe use of local and global ontologies will provide liberty to customers and transporters to work on their own standards without bothering of everybody else. Similarly intermediary ISUs will provide interoperability between them to work together in order to provide collaborative transportation planning.Ontologies presented in this paper are loosely inspired from the Ozone ontology developed by S.Smith and al[START_REF] Becker | An Ontology for Multi-modal Transportation Planning and Scheduling[END_REF][START_REF] Smith | Using a Scheduling Domain Ontology to Compute User-Oriented Explanations[END_REF]. Fig 1.3 presents an example of a local ontology of a transporter. Blue circles represent domain classes, red rectangles represent properties and green rectangles represent class instances and orange rectangle represents class attributes. Transporter owns fleet of vans represented by class 'Van'. These vans have facilities, which are represented by a class 'Facility' which have five instances to represent facilities type: 'Freezer', 'Freezer+Ice', 'Normal', 'Refrigerated' and 'Validated'. Association between class 'Van' and class 'Facility' is represented by a property called 'Has-Facility'. Vans with compartments are used to transport different type of products with different temperature requirements. There is another class called 'Van-Type', which has two instances called 'With-Compartment' and 'Without-Compartment'. Relation between class 'Van' and 'Van-Type' is represented by property 'Has-Type'. Each van is associated with certain nonstop trajectories assigned by transporter. Each trajectory has location of departure and location of arrival. Each location lies in certain region, where transporter provides its logistics services. Class 'Van' has a relation called 'Has A' with class 'Trajectory'. Class 'Location' is associated with class 'Region' with the property 'Lies-In'. V1 represents one of the instances of Van which has facility of 'Freezer-Ice' and is of type 'Without-Compartment'. 'TAR-TOU' is an instance of class 'Trajectory' which has Tarbes as location of departure and Toulouse as location of arrival. Instance V1 is associated with this trajectory and is represented by the property 'Has-A'.

  Fig 1.3 presents an example of a local ontology of a transporter. Blue circles represent domain classes, red rectangles represent properties and green rectangles represent class instances and orange rectangle represents class attributes. Transporter owns fleet of vans represented by class 'Van'. These vans have facilities, which are represented by a class 'Facility' which have five instances to represent facilities type: 'Freezer', 'Freezer+Ice', 'Normal', 'Refrigerated' and 'Validated'. Association between class 'Van' and class 'Facility' is represented by a property called 'Has-Facility'. Vans with compartments are used to transport different type of products with different temperature requirements. There is another class called 'Van-Type', which has two instances called 'With-Compartment' and 'Without-Compartment'. Relation between class 'Van' and 'Van-Type' is represented by property 'Has-Type'. Each van is associated with certain nonstop trajectories assigned by transporter. Each trajectory has location of departure and location of arrival. Each location lies in certain region, where transporter provides its logistics services. Class 'Van' has a relation called 'Has A' with class 'Trajectory'. Class 'Location' is associated with class 'Region' with the property 'Lies-In'. V1 represents one of the instances of Van which has facility of 'Freezer-Ice' and is of type 'Without-Compartment'. 'TAR-TOU' is an instance of class 'Trajectory' which has Tarbes as location of departure and Toulouse as location of arrival. Instance V1 is associated with this trajectory and is represented by the property 'Has-A'.

Fig. 1 . 3

 13 Fig. 1.3 Example of transporter local ontology

  Fig 1.5 illustrates the global ontology.

Fig. 1 . 4

 14 Fig. 1.4 Example of client local ontology Similarly Fig 1.4 represents an example of client local ontology. Client generates set of TOs represented by a class 'Transport-Order' which is created to deliver a product P1 of type 'Has-Type' Live animal of quantity 'Quantity'. TOs have city of pickup and delivery in global, which are then decomposed into elementary nonstop travels called 'Tasks' by Path Finder agent. Client attaches objective to each TO in order to define its priority which needs to be fulfilled. Here 'Objective' class have three instances; 'Less Costly','Urgent','Less Distance'. Client proposes requested start date and requested end date for these tasks and in return receives potential dates and effective dates from transporter.

There have to be matching criteria between local ontologies and global ontologies embedded in ISU of both the sides; clients and transporters. Table 1.1 shows the concepts of alignment between local client ontology and global ontology, while table 1.2 shows the alignment of transporter local and global ontology. The alignment mechanism used here is constructed manually but can be automatized using approach proposed by Song Fugi in [START_REF] Song | An ontology-driven framework towards building enterprise semantic information layer[END_REF]. He developed an ontology alignment technique to contribute federated enterprise data interoperability approach at semantic level. ISU will use this matching mechanism to make the transformation possible from local ontologies concepts to global concepts and vice versa. Local ontologies are subjected to evolve when new vehicles and new travels are added or clients progress from local to global. This evolution will cause the enrichment of these local ontologies, also forcing the enrichment of global ontology at the same time in order to continue keeping the compliance. This evolution is independent of the planning mechanism making this framework of distributed nature. Additionally transporters and clients joining or leaving the model do not affect its interoperable nature. It will require only the enrichment of the global ontology and updating the matching and transformation mechanisms in ISUs of POVES model.

Conclusion and future work

In this paper we presented ontology based a collaborative and interoperable framework called "I-POVES" for transportation planning problem In I-POVES, each order agents has its own local ontology and describes its transport orders using the concepts from local ontology. Similarly vehicle agents also have their own local ontologies to describe their vehicles and activities. We used a federated approach based on global ontology that maps all shared concepts used by local ontologies on both the sides. There are two ISUs, one on the order agents' side and one the vehicle agent side, to perform transformation between local and global ontologies. In I-POVES, firstly Path Finder Agent elaborates, when solicited for each order the traveling routes between pickup and delivery locations. Secondly Order agents offer transport jobs through sequential auctions and vehicle agents compete with each other to serve those jobs. Vehicle agents propose grouping these jobs together to execute them simultaneously. Multiple 3PL enterprises collaborate through this framework to propose the delivery of transport orders together. One of the future directions is, in case when 3PLs have their own planning mechanism and they just want to use I-POVES for collaboration with other 3PLS. How much transport ISU will be capable to handle not only ontology transformations but also the transformation from I-POVES planning mechanism and 3PL's local planning mechanism and vice versa.


Salma Essafi

Georg Langs

Jean-François Deux

Guillaume Bassez

Alain Rahmouni

Nikos Paragios

François Deux

Local Appearance Knowledge and Shape Variation Models for Muscle Segmentation

Keywords: MRI, Diffusion wavelet, Segmentation, Human skeletal muscle IRM, Ondelettes de diffusion, Segmentation, Muscle squelettique

In this report, we present a novel prior knowledge representation of shape variation using diffusion wavelets and applied for medical image segmentation. One of the major advantage of our approach is that it can reflect arbitrary and continuous interdependencies in the training data. In contrast to state-of-the-art methods our framework during the learning stage optimizes the coefficients as well as the number and the position of landmarks using geometric (reconstructed surface) constraints. Saliency is encoded in the model and segmentation is expressed through the extraction of the corresponding features in a new data-set. The resulting paradigm supports hierarchies both in the model and the search space, can encode complex geometric and photometric dependencies of the structure of interest, and can deal with arbitrary topologies. In another hand, our report deals with a different model search methodology where we apply an approach related to active feature models; the location of landmarks is updated iteratively, using local features, and the canonical correlation analysis. We report promising results on two challenging medical data sets, that illustrate the potential of our method.

Introduction

Myopathies are diseases that affect the muscle system, and lead to a severe deterioration of the motoric abilities. These pathologies affect 4 to 6% of the population, i.e 25 to 30 million Europeans [START_REF] Fernandez | An anatomically based patient-specific finite element model of patella articulation: towards a diagnostic tool[END_REF]. Diagnosis, as well as follow up for a given therapeutic strategy are often performed through biopsy. Magnetic resonance imaging (MRI) allows a noninvasive observation of the muscle fibers, their texture, and their global structure. It has the potential to replace biopsies (by e.g. diffusion tensor imaging (DTI)) and has the advantage of encompassing a section of the entire leg as opposed to small local samples. This enables the analysis of local properties, as well as understanding the global structural change of muscles affected by a disease. A crucial first step in this analysis is the accurate segmentation of individual muscles.

Shape models state of the art Model based segmentation and localization approaches are of prime interest, due to their ability to repeatably identify positions in the anatomy, and to learn and apply properties of large and representative populations. Of particular importance is the accurate representation of subtle local shape variation and the correct parameterization of the associated interdependencies between parts of the anatomical structures. This cannot be performed manually, but has to be learnt from the data, in order to avoid a bias that would compromise the model efficiency, and result accuracy. A second aspect that becomes prevalent when exploring large anatomical regions, is the highly heterogeneous nature of their appearance, but existing local consistency across patients. State of the art segmentation methods mainly rely on a clearly defined topology, and an object boundary characterized by salient features (e.g, edges). An example for accurate segmentation achieved through deformable models combined with shape modeling as shown in [START_REF] Cremers | Deformable Models.Theory and Biomaterial Applications, chapter Efficient Kernel Density Estimation Of Shape And Intensity Priors For Level Set Segmentation[END_REF]. Statistical Shape Models (SSM), proposed by Cootes [START_REF] Cootes | Active shape models-their training and application[END_REF], are used to capture and represent the shape variation in a training sets. Active Shape Model (ASM) [START_REF] Cootes | Active appearance models[END_REF], build a point distribution model, which allows for global scale analysis of shape variation by applying principal component analysis (PCA) to the positions of the boundary points, while using local appearance to fit the model to new data. These methods depend heavily on the accuracy of the inter-subject registration for group comparison and the parameterization of the shape.

The majority of work on anatomy segmentation is focused on brain, liver or heart data [START_REF] Duncan | Medical image analysis: progress over two decades and the challenges ahead[END_REF]. Muscle-compounds (see Fig. 1) pose a rather different and new challenge to segmentation algorithms because there is no prominent difference of tissue-properties between neighboring muscles. Border tissues in between muscles are only visible on specific locations, distributed in a very sparse and heterogeneous manner. Indeed muscle surfaces are only partially visible, while parts exhibit a structure, that can change dramatically between patients, or during the course of follow-up examinations. Related work on muscle segmentation includes simplex meshes [START_REF] Gilles | Anatomical modelling of the musculoskeletal system from mr[END_REF], or atlas-based models which are deformed using a free-form deformation [START_REF] Fernandez | An anatomically based patient-specific finite element model of patella articulation: towards a diagnostic tool[END_REF]. The main challenge of calf T1-MRI segmentation is the total absence of conventional image support. Edges between classes are almost invisible while at the same INRIA time the global intensity characteristics of the muscle regions are almost identical. Consequently prior models based on conventional image-based search approaches will fail to separate the muscles regions. An alternative would be the explicit use of the image support during the construction of the model. In fact selective active shape models for example [START_REF] Cootes | The use of active shape models for locating structures in medical images[END_REF] use only a small portion of the landmarks during the search, while sparse models [START_REF] Essafi | Sparsity, redundancy and optimal image support towards knowledge-based segmentation[END_REF] aim to optimize shape representation by proposing a sparse representation that encodes sparsity and exploits geometric redundancy.

A promising line of research was initiated by a method [START_REF] Davatzikos | Hierarchical active shape models, using the wavelet transform[END_REF] to build hierarchical active shape models of 2-D anatomical objects using 1-D wavelets, which are then used for shape based image segmentation. A further extension is performed in [START_REF] Nain | Shape-driven 3d segmentation using spherical wavelets[END_REF] [START_REF] Nain | Multiscale 3-d shape representation and segmentation using spherical wavelets[END_REF], where spherical wavelet can characterize shape variation in a local fashion in both space and frequency, in contrast to spherical harmonics that have a global basis set. Indeed this representation aims to learn a shape prior of 3-D objects by applying PCA to the clusters of correlated diffusion wavelet coefficients, and to exploit this prior for image segmentation based on the diffusion wavelets presentation. A more recent work by Zhu & al. [23] presents an approach based on the diffusion wavelet however just applied for the matching of 3D shapes.

Therefore it would be useful to consider a framework in which, for a given data set, similarities are given only between very similar points, and where it would be possible to organize local information by diffusion into global parameterizations. Therefore we present a method that provide for building a generative model of shape variation, and use it for segmentation in new data, including the use of orthomax to obtain an optimal subdivision of the shape. Beyond pre-defined manifolds The shape model approach proposed in this report accounts for the systematic behavior of shape variation and image support in the anatomical structure. It obtains an accurate delineation of the partially visible muscle surfaces, that cannot be achieved with registration based methods, by accounting for local statistical modeling and appearance behavior. The shape representation is based on a finite set of landmarks, that are repeatedly identified and exhibit significant differentiation to the background on different examples of the anatomical structure.

Essafi & al.

In contrast to conventional shape modeling approaches that rely on a pre-defined topology, and parameterize the surface of an object with regard to an according manifold like a sphere, the method learns the appropriate topology from the training data, and uses an according shape representation based on diffusion wavelets to model its variation. For this we need two mechanisms: 1. A way to determine the intrinsic topology of a shape for which multiple examples are available, and 2. a means to represent the shape variation with regard to this topology, i.e., a way to exploit arbitrary topologies. In this report we present an approach, that tackles both aspects. First we learn the intrinsic topology of training data by means of shape maps. Then we represent the shape variation by diffusion wavelets. This representation can cope with arbitrary topologies that are defined by a diffusion kernel. In contrast to e.g. spherical wavelets [START_REF] Nain | Shape-driven 3d segmentation using spherical wavelets[END_REF] they are not confined to a spherical reference manifold. Therefore they can represent the variation of training examples in a much more efficient and natural way. Our work is motivated by the highly heterogeneous distribution of visual information, and the locally confined deformation behavior in calf MRI data (Fig. 1), where standard segmentation methods fail, due to the ambiguous texture and the sparse distribution of salient leg image information. The differentiation between individual muscles is very subtle, the distribution of reliable image information at the boundaries is un-even, and this parts can only be estimated from prior shape knowledge.

An innovative research direction lies on connecting computational harmonic analysis to a broad range of issues facing the need of exploiting high-dimensional data. Diffusion wavelets generalize standard wavelets, allowing for multi-scale analysis on general structures, such as manifolds, graphs and point clouds in Euclidean space. Indeed diffusion maps [START_REF] Coifman | Diffusion maps[END_REF] and diffusion wavelets [START_REF] Coifman | Diffusion wavelets[END_REF], both derived from the wavelet concept, provide a significant new tool for describing complicated architecture of high-dimensional data, since they encapsulate all the common advantages of wavelets. We apply our method to anatomical object segmentation, and more specifically to CT heart data and MRI calf muscle, and for the latter of interest in the study of Myopathies. We will present experimental results that underline, the superior efficiency that a model based on diffusion wavelets can achieve as opposed to existing approaches. We will also evaluate the effect of this model representation on the search performance.

The remainder of the report is organized as follows: in Sec. 2, the shape representation based on diffusion wavelets is presented, and in Sec. 3 we focus on the search in new data. In Sec. 4 we report experimental results and quantitative validation. Finally Sec. 5 concludes with a discussion.

INRIA 2 Shape Representation

We parameterize the shape variation observed in the training data by means of diffusion wavelets. The topology of the structure that is modeled is defined by a diffusion kernel. It can be viewed as a generalization of standard parameterizations, e.g.: the diffusion kernel for a triangulated spherical surface would be the adjacency matrix weighted by the mutual distances. Defining the topology by a diffusion kernel instead of a fixed genus-0 manifold allows us to learn and incorporate more complex interaction patterns observed in the training data.

In the following we will first outline diffusion wavelets, then will explain the associated shape representation, and finally will note how the orthomax principle can be used to separate coherent sub-regions of the shape.

Properties of Diffusion Wavelets

Wavelets represent a robust mathematical tool for hierarchically decomposing functions. The theory is described extensively in [START_REF] Meyer | Wavelets -Algorithms and applications[END_REF]. Through wavelets decomposition, a function can be described in terms of a coarse overall shape, that is enriched by details that range from coarse to fine. They provide an elegant technique for representing the levels of detail regardless of the interest function type, e.g. an image, a curve, or a surface. Besides the major advantage of the wavelets remains on the compact support of basis functions in one hand, and on the inherently hierarchical representation since it is based on multi-resolution modeling of processes at different spatial and temporal scales. Thus with appropriately selected eigenfunctions or scaling functions of Markov matrices, we are able to optimally describe local variations in muscles shapes comparing to conventional approaches like PCA [START_REF] Coifman | Diffusion wavelets[END_REF]. Diffusion Wavelet conveniently reshape many of the ideas of multi-scale analysis that have proven so useful in study of 1-D signals and 2-D images, making it possible to describe the complex nature of high-dimensional phenomena. Finally they provide an interesting alternative to global Fourier eigenfunctions for value function approximation.

To get meaningful geometric descriptions of data sets, one should refer to diffusion process, where it's shown that eigenfunctions of the Markov matrix corresponding to the kernel of the diffusion process provide coordinates, called diffusion maps, for generating efficient representations of complex geometric structures.

A Diffusion Operator Reflecting The Topology

Diffusion wavelets [START_REF] Coifman | Diffusion wavelets[END_REF] and the closely related diffusion maps [START_REF] Coifman | Diffusion maps[END_REF], relate computational harmonic analysis to a broad range of dimensionality reduction questions. Both are derived from the wavelet concept, and provide a significant new tool for describing complicated architecture of high-dimensional data.

All anatomical shapes are aligned by Procrustes alignment [START_REF] Luo | Iterative procrustes alignment with the em algorithm iterative procrustes alignment with the em algorithm[END_REF], which produces the series of volumes V p i , before calculating the mean shape V p . Results of this alignment on heart data can be seen in figure 2. After this registration, we can calculate the mean shape of the RR n 6821 muscles/hearts as in the equation ( 2)

V p = 1 N N i=1 V p i (1)
S i = V p i -V p (2)
We build our diffusion operator T on a cloud of points embedded in a metric space . A matrix of graph weights for the point cloud is constructed by building a local bump function centered at each point and then the weight matrix is normalized through the symmetric Laplace-Beltrami to form the diffusion operator T.

Diffusion Wavelet Modeling of Shape Variations

Given this diffusion operator T defining the manifold, we use the corresponding hierarchical diffusion wavelets, to represent the shape variation.

First we build a hierarchical wavelet structure, the diffusion wavelet tree: We call upon a general multi resolution construction for efficiently computing, representing and compressing T 2j , for j > 0. Indeed during the down-sampling process, and throughout a recursive sparse QR decomposition we aim to obtain the orthonormal bases of scaling functions, Φ = {φ j }, the wavelets W j , and compressed representation of T 2j on φ j , for j in the requested range. Giving K maximum number of levels to compute, we will obtain after K steps in this fashion, a representation of T 2j onto a basis φ j , with 1 ≤ j ≤ K. For more calculation details please refer to [START_REF] Coifman | Diffusion wavelets[END_REF].

Once the construction of the diffusion wavelet tree Φ is accomplished, we use it to represent the individual training shapes. In fact we calculate the diffusion wavelet coefficient Γ on the deviation from the mean of the aligned shapes, and obtain the following diffusion wavelet coefficient:

Γ Si = Φ -1 .S i (3)

INRIA

Thus the shape representation of the muscles could be written:

V p i = V p + ΦΓ Si (4)
Once we have generated the diffusion wavelet coefficients for all training examples, we build our model as follows:

i Consider the coefficient level by level,

ii Computing covariance matrix of diffusion wavelet coefficient, and

iii Apply PCA to each level of coefficients in order to obtain variation of the shape at a specific scale.

At this stage we have the diffusion wavelets coefficients which in the lowest level provide an overall approximation, whereas localized variations are captured hierarchically by the higher-level coefficients. Consequently we conduct our PCA study over each frequency level of the diffusion wavelets coefficients separately, instead of taking into the consideration all the points , with {σ j } j=1...K are the subset of eigenvectors corresponding to eigenvalues {λ j } j=1...K of the covariance matrix of the diffusion wavelets coefficients at each level j, (1 ≤ j ≤ K), which will call Γ level j (see eq. 5)

Γ level j = Γ Si/level=j i=1...N (5)
and Γ level * j as the deviation from the mean of the latter; so at each level the coefficients would be expressed such as:

Γ level j = Γlevelj + σ j σ ′ j .Γ level * j (6)
We can afterward gather together the coefficients of each shape at all level (Γ Si Rec ), and consequently get the reconstruction of our initial data.

V p i = V p + Φ.Γ Si Rec (7)

Modeling Using the Orthomax Criterion

In order to separate parts of the data with low correlation, we use the orthomax criterion [START_REF] Browne | An overview of analytic rotation in exploratory factor analysis[END_REF] in the coefficient space of the wavelets. More especially we explore the varimax version [START_REF] Leung | Localized shape variations for classifying wall motion in echocardiograms[END_REF] for optimizing sparsity corresponding to new variables being associated to localized modes of variation. Indeed orthomax rotations represents re parameterizations of the PCA space producing a simple basis. Let R be an orthonormal rotation matrix in R k where R i,j represents R elements, and where k implies the number of eigenvectors with the largest eigenvalues λ i . Besides σ denotes as

Essafi & al.
previously in the report the p × N eigenvectors matrix. The orthogonal orthomax rotation matrix R is calculated as follow: Orthomax rotation effects are illustrated in Fig. 3, where one can easily notice that while the PCA modes demonstrate several spatially distributed effects within each mode, the varimax modes in the other hand show nicely isolated effects.

R = arg max R   k j=1 p i=1 (σR) 4 ij - 1 p k j=1 p i=1 (σR) 2 ij 2   , (8)
Furhtermore Fig. 4 shows the 'flattening' of the eigenvalue spectrum carried out by the varimax rotation where the respective modes as well as variances are plotted. So this simple, yet powerful modification of PCA had enabled us to optimize sparsity leading to localized modes of variation, and which is more suitable for applications with sparse parameterizations as the pathologies we are working on.

In Fig. 5 the resuming scheme of our pipeline model is depicted. In fact, once we succeeded to separate our data variations through the wavelet level space, we can then get the shape prior by projecting back the selected orthomax eigenvectors of the diffusion coefficients level into the right dimensions. So the equation 6 would be expressed with the orthomax componants. Thus our pipeline allows to capture variations at every levels without discriminating higher variations beyond lower ones. Our final shape reconstruction will be therefore defined as following:

Γ i * level = Γ level i * 1 Γ level i * 2 . . . Γ level i * K (9)
V p i = V p + Φ. Γlevelj + σ j orthomax σ ′ j orthomax .Γ i * level ( 10
)
INRIA iterative manner, starting from a coarse initialization obtained by atlas registration. Similar to a standard shape model inference approach, the positions of landmarks in new data are estimated by an energy minimization that involves both shape prior and appearance costs:

1. The landmark positions of V are updated according to a local appearance model. For each landmark the position with highest probability of the corresponding local texture patch being consistent with regard to the learnt texture model b i is chosen along a line orthogonal to the model surface. Let b(x j i ) be the learned texture patch at the correct landmark position x i in the training example I j , and for landmark positions in a local neighborhood N let Q j i (x) be the correlation between the patch b(x) and b(x j i ) normalized within the neighborhood, i.e.

x∈N Q j i (x) = 1, then the image support is

g i = mean j=1,...,n   Q j i (x) x∈N \x j i Q j i (x)   . ( 11
)
That is, for a landmark in V the image support is calculated from the local appearance behavior at the corresponding positions in the training set. 2. The shape is constrained by either a local or global statistical shape model. In our work we use diffusion wavelet shape model. This procedure is iterated. During each iteration, the corresponding V ′ is reconstructed to re-estimate the surface normals. After convergence the final reconstruction V ′ is an estimate of the true muscle surface inferred from the data, and the prior model.

Appearance Feature Model

Appearance Representation Using Local Features

We employ a search framework related to Active Feature Models (AFM) proposed in [START_REF] Langs | Active feature models[END_REF]. The approach is related to Active Appearance Models (AAM) [START_REF] Cootes | A comperative evaluation of active appearance model algorithms[END_REF], with the main difference that AFMs describes appearance by means of local features, and infers model updates during search by means of canonical correlation analysis (CCA), which has advantages given noisy data. The benefit of the method is considerable in the presence of complex data, like muscle data, where large parts of the variation within the muscles have low relevance for landmark localization and a small training set has to compromise a decent representation of the texture in the model.

For the calf muscle segmentation, we utilize a Gabor jet with frequencies {0.3, 0.6, 0.9} and directions {0, π/4, π/2, 3π/4, } to describe the local texture at the landmark positions.

During training we learn the relation between landmark displacements and the corresponding texture feature change by CCA. Still during this phase, model parameters are perturbed randomly generating a large number of displaced model instances. A functional relation is then learned from the resulting feature vectors describing local texture and the corresponding model parameter displacement by Canonical Correlation Analysis (CCA) [START_REF] Donner | Fast active appearance model search using canonical correlation analysis[END_REF].

INRIA

Search by canonical correlation analysis

During search local features are extracted at the current landmark position estimates. Based on the relation learnt by CCA, according model parameter updates are performed . This results in an iterative search approach, that converges to the landmark positions, based on the local appearance, and constraint by the diffusion wavelet shape model.

Results

Experimental Set-Up

In order to evaluate the performance of the proposed method, we have considered two different data set: 25 calf muscles divided into two groups: 20 healthy control patients and 5 unhealthy cases. For each volume there are 90 slices of 4mm thickness, and with voxel spacing of 0.7812x0.7812x4 mm acquired with a 1.5 T Siemens scanner. Standard of reference annotation by experts for the Medial Gastrocnemius (MG) muscle, was available (Fig. 6.b). Correspondences for a set of 895 landmarks on the surfaces were obtained by an MDL based optimization [START_REF] Langs | Robust autonomous model learning from 2d and 3d data sets[END_REF].We performed a leave-one-out cross validation on the whole data-sets, i.e., models were trained on 24 examples, and search was performed on the remaining example.

25 CT volumes of the heart, with an approximate voxel spacing of 1.5 mm, for which 90 anatomical standard of reference landmarks, and a set of 1451 control points for the left ventricle was available, in addition to the ground truth segmentation (Fig. 6.a) from experts concerning the diastole as well as the systole.

Experimental Validation

Evaluating model reconstruction performance To assess the model representation of our framework, we model the shapes of the structures by diffusion wavelet shape models in a leave-one-out cross validation strategy. To evaluate the diffusion modeling approach, we assess two measures: 1. reconstruction error, and 2. search performance. We compared the reconstruction error for gaussian shape models, and the proposed diffusion wavelet modeling. We tried two different diffusion wavelet kernels: 1. just utlizing the spacial proximity of landmarks, and 2. a kernel based on the shape map distance of the landmarks [START_REF] Langs | Modeling the structure of multivariate manifolds: Shape maps[END_REF], where shape maps were built with kernel size k = 3 and ǫ = 500 for both data sets. The goal is to see how far our model is able to detect the local shape variations based on different kernels. As a first comparison , we show in the Fig. 8 the reconstructed surfaces for our heart data set using projected wavelet coefficients on the set of principal components at level 1, where the surfaces are representing the ±3sqrt(λ i ) from left to right. Moreover the reconstruction error between the diffusion wavelet model and the reference model is calculated as an average surface error for all test shapes in table 1, where we also establish rate errors. In Fig 7 the reconstruction of the projected shape model (heart/muscle) is depicted, this reconstruction starts from the projection of the diffusion wavelet coefficients in respectively the first and the last level, and then extracting a new subset of coefficients from the eigenvectors that constitutes 99% of the variation in the correspondant level. To keep the variation in reasonable limits, the shape parameters are also restricted to ±3 √ λ i . During the reconstruction experiments we were also able to check the effects of each eigenvector of any scale on the rate error.

INRIA

Heart

Evaluating search performance To evaluate the search behavior we compared the proposed method with a standard shape model search in an active shape model manner, based on an even sampling of the object surface, and gradients in the volumes, and a spare shape model proposed in [START_REF] Essafi | Sparsity, redundancy and optimal image support towards knowledge-based segmentation[END_REF] The latter uses a similar appearance model, and allows for the assessment of the effect of replacing the multivariate Gaussian landmark model, with the diffusion wavelet shape model. The error measure evaluated is the mean distance of the model landmarks between standard of reference and segmentation result (Tab.2). The latter gives also an indication of the displacement along the surface, which is relevant if the result is used for navigation. Models were initialized with minimal overlap to the target shape, and the accuracy of the final result was quantified by the mean landmark error between ground truth annotation and search result. As far as quantitative comparison is concerned, (Tab.2) results clearly show how the diffusion wavelet model outstands the sparse model and that for both anatomical data sets, with for example 6.97 voxels for DW model over 8.72 error voxels for the sparse model through the challenging calf data sets. Results The diffusion wavelet model was able to recover the shape with superior accuracy.

RR n 6821

In the muscle data the standard search approach failed due to the ambiguous texture in large regions of the target shape. In Fig. 10 examples for standard, sparse model [START_REF] Essafi | Sparsity, redundancy and optimal image support towards knowledge-based segmentation[END_REF], and muLtiscale diffusion wavelet based search are depicted. In fact one of the important points that distinguishes our methodology from robust ASMs, is that we learn the distribution of both image and shape information during the training phase to optimally exploit the anatomical properties of the data. This is not the case with of robust ASMs which for a given sampling they consider a subset of the control points according to the observed image support.

AFM Search Regarding the muscle data our approach was able to recover the shape with superior accuracy, in the meanwhile the standard search approach failed due to the ambiguous texture in large regions of the target shape. In

Conclusion

We present a multiscale shape prior based on diffusion wavelets shape representation and segmentation. Diffusion wavelet shape models are able to take advantage of the subtle inter dependencies in training data, by clustering coefficients based on correlation, and representing the topology of the structure by a diffusion kernel, instead of a fixed pre defined manifold. Furthermore we are using the orthomax criterion which is established to be suitable for building sparse representations -as it's the case of the current pathologies studied in the report-with relative ease leading to localized modes of variation. We have shown that in the context of anatomical structures, the diffusion wavelet transformation is able to accurately and efficiently detect the locations and spatial scales of shape variations. The INRIA validation on detecting patterns on two complex data sets shows promising results indicating the advantage of using a learnt model parameterization. Also we want to point out that contrary to the standard AAM's model, we are introducing a substantially more flexible and powerful shape model (hierarchical diffusion wavelets vs. global PCA on point coordinates), a local appearance description and according search paradigm. As for the work of Spherical wavelets by Nain & al [START_REF] Nain | Shape-driven 3d segmentation using spherical wavelets[END_REF], we are extending the representative power: complete freedom of object topology defined by a diffusion kernel in our case, vs. a sphere in the case of [START_REF] Nain | Shape-driven 3d segmentation using spherical wavelets[END_REF] and the orthomax criterion to allow for a 'soft' subdivision, vs. n-Cuts in Nain & al. work. Future work includes the integration of model learning approaches that learn the locations in non-annotated data in a weakly-or unsupervised manner. The prime goal remains to achieve the segmentation accuracy necessary for a clinical application in myopathy diagnosis and follow up monitoring, to allow for a non-invasive analysis of the muscle structure.

Figure 1 :

 1 Figure 1: Calf MRI: (a) healthy (b) manual expert annotation and (c) zoom on AT, EDL and PL muscle groups.

  Essafi & al.

Figure 2 :

 2 Figure 2: Heart CT data: (a) shapes before alignment (b) after alignment and (c) Mean heart shape.

Figure 3 :

 3 Figure 3: Data reconstruction through global PCA (a) and localized orthomax (b) rotated modes of the DW coefficients models.The surfaces representing the ±3sqrt(λ i )

Figure 4 :

 4 Figure 4: Comparaison between PCA and Orthomax DW eigenvalues

Figure 5 :

 5 Figure 5: Scheme of Diffusion Wavelet Coefficient Process

  (a) Ground truth segmentation of papillary muscles (b) T-1 MRI slice supervised segmentation of a human calf

Figure 6 :

 6 Figure 6: Standard reference segmentation of respectively the calf muscle and the left ventricle

Figure 7 :

 7 Figure 7: Diffusion Wavelets Model reconstruction. First row for Heart results and second for Calf muscle. Data, green: standard of reference segmentation, red: reconstruction result for a. first scale and b. last wavelet scale.

Figure 8 :

 8 Figure 8: Reconstructed surfaces for Heart CT data using projected wavelet coefficients on the set of principal components that represent 99% of the total variance at level 1. The surfaces representing the ±3sqrt(λ i ) from left to right. The figure is dedicated to the axial view.

Figure 9 :

 9 Figure 9: Results of the segmentation using the DW-AFM model. (a) Boxplots of the Dice Similarity Coefficients Measure and (b) landmark error (voxel) after finishing the search phase over the whole data set, with (1) our current approach and (2) standard model.

Figure 10 :

 10 Figure 10: Model search result for Heart muscle(upper row) and Calf muscles(down row). data, green: standard of reference segmentation, red: search results for (a, d, g) standard gradient search approach, and uniform sampling, ( b, e, h) sparse shape models and ( c, f, i) diffusion wavelet model.

  Properties of Diffusion Wavelets . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 A Diffusion Operator Reflecting The Topology . . . . . . . . . . . . . . . . . 2.3 Diffusion Wavelet Modeling of Shape Variations . . . . . . . . . . . . . . . . . 2.4 Modeling Using the Orthomax Criterion . . . . . . . . . . . . . . . . . . . . . Sparse Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Appearance Feature Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Appearance Representation Using Local Features . . . . . . . . . . . . 3.2.2 Search by canonical correlation analysis . . . . . . . . . . . . . . . . .

	Contents
	1 Introduction
	2 Shape Representation
	2.1 3 Data Search
	3.1

4 Results 4.1 Experimental Set-Up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Experimental Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Conclusion

Table 1 :

 1 Full Landmark Reconstruction Error (in voxel) with regard to three different shape models for heart and calf data sets.

		Data	Calf Data
	Gaussian model	1.6154	2.1277
	DW Model with	0.0755	0.1485
	spatial kernel
	DW Model with	0.1100	0.1796
	Shape Map kernel

Table 2 :

 2 Heart/Calf Search for Segmentation. Landmark Reconstruction Error (in voxel) comparison between three different search models.

	INRIA

RR n 6821

Essafi & al.

Acknowledgments

This work was supported by Association Française contre les Myopathies (AFM: http://www.afm-france.org) under the DTI-MUSCLE project.

INRIA