Areski Flissi
email: areski.flissi@lifl.fr

Christophe Gransart
email: christophe.gransart@inrets.fr

Philippe Merle
email: philippe.merle@inria.fr

A Service Discovery and Automatic Deployment Component-Based Software Infrastructure for Ubiquitous Computing 1

Software applications running on mobile devices are more and more needed. These applications have strong requirements to address: device heterogeneity, limited resources, networked communications, and security. Moreover it is required to have appropriate application design, discovery, deployment, and execution paradigms. These requirements are similar to those of any ubiquitous computing application. In this paper, we present a component-based software infrastructure to design, discover, deploy, and execute ubiquitous computing contextual applications. Applications are designed as assemblies of distributed software components. These assemblies are dynamically discovered according to end-users' physical location and device capabilities. Then appropriate assemblies are automatically deployed on users' devices. Ubiquitous contextual services and our software infrastructure are built on top of the OMG's CORBA Component Model (CCM) and are implemented using the OpenCCM platform. As illustration, a service to get information about departure trains is described in detail.

Introduction

Software applications running on mobile devices are more and more required. This new challenge is now called ubiquitous computing. Lot of problems must be taken into account during development of these ubiquitous computing applications.

Terminals used are generally heterogeneous: users can achieve their tasks using a laptop with wireless network card or using a PDA or a smart phone. These terminals have different operating systems and limited hardware resources like RAM or CPU. Moreover mobility is difficult to take into account in applications. Very often, when user goes out of the wireless network coverage, this event generates an error in the application. Last but not least, security in wireless distributed applications is also a big challenge.

Currently, there is no global solution to build ubiquitous contextual applications. Indeed, existing solutions only address the problems of service discovery and deployment. Service design and implementation must be done separately with another technology than that used to build the discovery and deployment functionalities. In this paper, we present a global solution through a component-based software infrastructure to easily design, discover, deploy and execute applications on mobile devices. However, we only focus on applications running in contextual environments like a railway station. Security, disconnection and lost of connectivity are not considered in this paper.

In our approach, a service is deployed on a distributed architecture and running on several equipments (mobile and fixed). Services are designed as assemblies of distributed software components. These assemblies are dynamically and contextually discovered according to end-users' physical location and device capabilities thanks to a service registry. Then appropriate assemblies are automatically deployed to users' devices using a service activator. At runtime, interactions between the components are done using distributed middleware. Ubiquitous contextual services and our software infrastructure are designed on top of the OMG's CORBA Component Model (CCM) [START_REF]Object Management Group: CORBA Components Specification, version 3.0. OMG TC Document[END_REF]. A prototype is implemented using the OpenCCM [START_REF]The OpenCCM Project[END_REF] platform, an open source Java-based CCM implementation.

The reminder of this paper is organized as follows. Section 2 describes an example which will be realized with our platform and the challenges to address in the context of ubiquitous computing. Section 3 presents the design principles to develop a ubiquitous contextual service with distributed software components. These principles are illustrated on the departure train example. Section 4 details the ubiquitous computing software infrastructure composed of discovery and deployment functionalities, especially service registry and activator components. Section 5 describes the implementation of our software infrastructure and discusses about the current limitations. Section 6 presents some related works. Finally, Section 7 concludes this paper and gives some future work perspectives.

The context

This section presents an example of applications that we want to realize. Next, we present several problems related with ubiquitous contextual applications.

An example of contextual applications

To illustrate ubiquitous contextual services, let us take the following example. A commuter with a wireless PDA is arriving into a railway station. When he/she is inside of the hall, his/her PDA automatically knows where his/her owner is and launches services to obtain some information about the departure platform, train schedule, etc. This service can be used with several user interfaces (see Figure 1): with a GUI or with a text to speech interface.

The challenges

To realize this simple scenario, we must take into account several issues related to ubiquitous and contextual applications:

-

Heterogeneity of devices

Devices which could be used are various: user can access to services from a laptop, a PDA or a smart phone. These devices run different operating systems (Windows, Linux, WinCE, PalmOS, Symbian, etc.). Concerning the wireless link, several technologies are also available as Wi-Fi (IEEE 802.11a/b/g) or Bluetooth for short/medium range network, GPRS or UMTS for national coverage.

-Low Resources

Power consumption is a major problem with mobile devices. Moreover, PDA and smart phones have less memory and smaller processor than laptops. Network connectivity is not always available. These points will modify the way to design applications.

-Distributed Applications

The service to get information about the departure platform is distributed on several computers. The graphical user interface is running on the PDA and the process to extract data from the train operator information system is running on fixed computers. Communication between fixed part and mobile part is achieved through the wireless network. Service implementation can be achieved using a communication middleware (CORBA, messaging, etc.).

-Security Security is also a major issue in this kind of applications. All the actors (mobile terminals, infrastructure, and servers) are concerned. To achieve security, several solutions based on authentication and cryptography need to be integrated.

-Service Discovery

The next problem is how a user knows that some services are available in a particular location. Moreover, code of available services to deploy will be different if the computer is a black and white PDA or a color laptop for instance. To make this choice, the system needs some information about the client terminal. According to this information, it can present a subset of services which can potentially run on the user's terminal.

The discovery process can be done by the user: he/she explicitly sends a request to the environment to check if some services are available. The opposite solution is that the environment sends periodically information about available services. Then the user is automatically notified that some services exist.

-Service Deployment

Once the user knows that an interesting service is available then the infrastructure must deploy the code on the user's device. Deployment consists to fetch software components from a repository, to download them, to instantiate, configure, and interconnect components. In our context, applications must be incrementally deployed: components running on fixed computers are deployed in a preliminary step, and then components running on user's terminal are deployed on user's demand.

When a user comes back to a location where he/she used previously a service, does he/she have to redo the discovery and deployment process? It would be interesting that its terminal maintains information about services previously used and create a kind of service information profile.

The Model for Ubiquitous Contextual Services

This section presents our model for designing ubiquitous contextual services. Firstly, the principles of the underlying software component model used in our approach are discussed. Then the component-based design of the train service is presented.

The distributed software component model

In our model, a ubiquitous contextual service is a composition of distributed and interconnected software components. The underlying component model is based on the definition given by Clemens Szyperski in [START_REF] Szyperski | Component Software: Beyond Object-Oriented Programming (Second Edition)[END_REF]: "A software component is a unit of composition with contractually specified interfaces and explicit context dependencies only. A software component can be deployed independently and is subject to composition by third parties". In this definition, an interface means a set of method signatures. A signature captures a method name, a set of parameter types, a set of exceptions, and a result type. Context dependencies encompass all metadata describing the required context to run the component, e.g. binary libraries and other components required by the implementation of the component. However we enhance this definition with the notions of distribution and interconnection.

A ubiquitous contextual service is deployed and run on a distributed system composed of several fixed and mobile computers. Then its components are distributed over the system: Each software component is assigned on a node in the system. In order to support component interactions, data exchanges and component behavior synchronization, two kinds of distributed interaction patterns are needed at least2 : 1to-1 synchronous invocations and 1-to-many asynchronous notifications. With the first interaction pattern, a client component calls methods provided by a server component in a synchronous way, i.e. the client waits until the server replies. For instance, this allows a client component to obtain a data stored or computed by a server component (e.g. get the list of departure trains) or to request the execution of some behavior of a server component (e.g. add a new arrival train). With the second interaction pattern, a producer component sends data to consumer components in an asynchronous way, i.e. the producer and consumers work in parallel. For instance, this allows a producer to broadcast the new value of a data to all interested consumers or to notify a new event like an alarm (e.g. notify the departure or arrival of a train).

In order to support these two interaction patterns, the components need to be interconnected. For this purpose, each component provides interaction ports. Four kinds of ports are available3 : facet identifying an interface provided by a server component and its methods are invoked synchronously by client components, receptacle identifying an interface required by a client component and provided by another component, event source identifying a channel used by a producer component to send events asynchronously, and event sink identifying the interface allowing a consumer component to receive asynchronous events. Moreover each component provides a base reference interface offering management and control methods, i.e. to configure attributes, to connect facets to receptacles and event sinks to event sources. This management interface is mainly used during deployment and reconfiguration of distributed software component applications.

The different concepts discussed previously, i.e. component, reference interface, attribute, synchronous interaction via facet and receptacle ports, and asynchronous interaction via event sink and source ports, are illustrated in Figure 2. These principles are used to design and build both ubiquitous contextual services and our service discovery and deployment infrastructure discussed in Section 4.

In order to build services, it is needed to compose a set of distributed software components. For this purpose, components must be packaged into component archives containing both the component binary implementation and metadata describing context dependencies at least. Moreover, a same component could have different implementations (e.g. a GUI for small PDA screens, another for laptops, etc.). Then a component archive must allow one to store different implementations and metadata for each that describes the appropriate running context. Then component archives could be assembled together to form assemblies of distributed software components. These assemblies must identify the component instances to create at deployment time, the configuration of their business attributes, the interconnections between their ports, and finally the physical assignment to nodes. This description could be expressed via an Architecture Definition Language (ADL) or any other metadata formats. Then assembly descriptions and component archives could be packaged together into assembly archives. Then these assembly archives could be deployed automatically as they contain all the required information.

The component-based design of the train service

The composition of distributed software components used in our train service is depicted in Figure 2. This service is composed of three main components: -The Database Train Schedule Component (DTSC) encapsulates the back office information system of the railway operator. It could be deployed on one main frame or replicated over a cluster of servers 4 . -The Railway Station Component (RSC) extracts data related to a specific railway station from the previous component, and it sends them to the user terminals. A railway station component must be deployed on each railway station, it is configured appropriately, e.g. with the railway station identifier used to query the back office information system, and it is connected by a receptacle port to the DTSC. This component provides a facet for querying local contextual railway station information, and an event source to notify user terminals of recent updates of this contextual information.

-A Train Graphical User Interface (GUI) component presents to end-users the trains which will soon leave from or arrive to the contextual railway station where the user is. For this purpose, this component has two ports -a receptacle and a event sink -to receive data from the contextual TSC, respectively in a synchronous and an asynchronous way. This component is the mobile part of the train service: One instance is deployed and running on each user's mobile terminal. The deployment is done automatically on user's demands. The implementation on the deployed instance depends of the terminal capabilities -e.g. black and white or color screen, and screen size -and user's preferences -e.g. interface language. Then several heterogeneous instances could be simultaneously present in the whole system.

These three components are deployed at different times in the life cycle of the train service. The two first components must be deployed in a preliminary step and will run during the whole life time of the service. On the other hand, Train GUI components are deployed dynamically on user's demands and are instantiated in the system during short periods of times. Then to address this, two different assemblies must be built: One containing the two components running on the fixed computers, and one packaging the mobile part of the service. In order to interconnect Train GUI components to the contextual Railway Station component, it is required that the first assembly exports the RSC reference into a naming or trader registry, and then the second assembly could import the RSC reference from the used registry. In order to allow these incremental deployments and interconnections of assemblies, it is required that the assembly description format provides constructions to express exportations and importations.

The Ubiquitous Computing Software Infrastructure

This section describes our software infrastructure dedicated to ubiquitous computing. This infrastructure especially focuses on the problems of service discovery, automatic deployment and execution on users' devices according to their contextual information. We have chosen to model this infrastructure using the distributed component-based approach presented in Section 3. Part of it, i.e. a set of components composing the software infrastructure, is dedicated to the discovery of contextual services, whereas some components are responsible of the deployment and the execution of services (i.e. the instantiation on the user's device of the client part of the application). These two aspects are discussed in detail respectively in Section 4.1 and 4.2.

Dynamic discovery of contextual services

The dynamic discovery of contextual services concerns problems raised in Section 2 about the way a user entering a specific area is informed on available services and also if these services are adapted to his/her device. Indeed, considering our example of service providing information on trains, the questions raised are:

-How and when a user arriving in a railway station is informed about the existence of a service providing information on trains, and -How and when the GUI showing the information could be adapted to the user's device capabilities.

The Service Registry and Service Activator Components

To address the problem of the discovery of contextual services, we first introduce a component in our software infrastructure named Service Registry. The Service Registry (SR) component is a "server-side" component of the infrastructure architecture. By this we mean that this component will be instantiated on fixed computers of the ubiquitous environment (e.g. a server in the railway station). It is in charge of the following main points:

1. Manage the list of available services: the SR component maintains a list of services and offers a way for service provider administrators/operators to register, update and remove services. 2. Transmit its unique identifier: every SR has a unique ID allowing the differentiation of multiple service providers. Indeed, ubiquitous environments can co-exist from user point of view in some particular cases. Actually, this happens in our example of application if the railway station is near a museum offering ubiquitous services too (like information on current exhibitions, etc.) for instance. 3. Be able to compute the appropriate mobile assembly and/or component implementations of services according to the user's device contextual information (hardware and software capabilities), also called "user profile". 4. Transmit the list of registered services: the list sent to a user should reference only services that are adapted to the device.

Secondly, a component named Service Activator represents the "client-side" component of the infrastructure and, as such, has to be started on mobile devices. The Service Activator (SA) component interacts with the SR as follows:

1. Receive SR ID: from it, users will be able to access the list of available services registered in the corresponding SR. 2. Transmit the user profile: this information is sent by the SA component to the SR that has been selected by the user. 3. Receive and display a list of available contextual services: from the list, the user can choose and request the deployment of a service.

Discovery of Service Registry and Negotiation Protocol

Thanks to this component-based architecture, the challenge of contextual services discovery can be reformulated as follows: how the SR is discovered by the SA components? Different scenarios at this stage exist, depending on who -the user/device or the server hosting the SR -is initiating the service discovery. Using a protocol based on multicast, the first case, i.e. the services search is initiated by user, implies the user's device being in a "transmit" mode (TX), which means to start a periodically sending of search requests. The second case, i.e. the user's device is in a "receive" mode (RX), implies that the server is in charge of the periodical sending of requests through the network. This case is more interesting if we take into account several aspects. First of all, considering energy aspect, just let us have a look at power consumption provided by some IEEE 802.11x wireless cards specifications [START_REF]WL 110 Wireless Card User Manual[END_REF][START_REF]WLI-CB-G54A User Manual[END_REF][START_REF]DWL-AG660 User Manual[END_REF]. Table 1 simply shows that the device power consumption is reduced by 25 to 35 percents in the RX mode. This mode will then be implemented in our software infrastructure. Also, this leads us to the following question: which period for requests transmission from server to devices must be used? This period depends on both the mobile device moving speed and the wireless network coverage surface. More the moving speed is important more the period must be short. On the other hand, if the coverage surface is large then the period could be longer. Next, having one emitter (the service provider server) and several receivers (users' devices) that are waiting for requests generates less network traffic than the opposite. This has to be pointed out in the context of ubiquitous applications as the number of devices involved can be potentially important. At last, the RX mode allows a transparent discovery of the SR from users' point of view and updates are automatically and immediately notified to devices.

Once the SR is discovered, the user is able to send requests to get the list of contextual services that are adapted to the device. For instance, many implementations of the GUI for the train service are available: GUI for white and black or color screens, text to speech interfaces, resolution, French or English language interfaces, etc. So, depending on the device hardware and software characteristics but also on user's concerns (e.g. for the choice of the language of the interface), different component assemblies of the client service part can be proposed. That's the reason why a "negotiation protocol" has been defined between the user's mobile device and the SR's host for the contextual services list discovery. The first step of this protocol concerns the ability of the client service part (the mobile assembly of the service) to be conform to the user/device profile. The hardware/software device information is sent by the SA to the SR once this last is detected by the user's device. Then, the SR computes a list of mobile assemblies that are adapted to the device characteristics and sends it. The SA receives this list and the user can then choose among the list of available contextual services displayed. Also, for each service, many assemblies could be available. Indeed, if the SR computes that the device can instantiate both color and text to speech interfaces, the user can select between many configurations: color and text to speech interfaces, just the text to speech interface, etc. What's more, other configurations of the service assembly can be considered, not just in term of component implementation choices but also in term of application architecture. To illustrate this point, we can imagine that the user is a non-French speaker arriving in a French railway station, so that, if exists, a functional component realizing the French-to-user's language translation of the user interface has to be expressed in the alternate configuration.

Finally, all steps of the different interactions between components of our software infrastructure are illustrated in Figure 3, from the SR discovery by SA (1) to the available contextual services list receiving, including user profile sending (2) and computation of appropriate configuration of mobile assemblies (3).

Automatic Deployment and Execution of Services

Once the user has selected a service, the software infrastructure has to deploy the code on the device. In the context of component-based applications, deployment consists of many steps that we can classify in three important phases:

-Component binaries downloading from a repository to devices, -Instantiation of these components (e.g. the GUI) on the user's device, and -Interconnection them with the components that belong to the fixed part of the service.

For this purpose, we introduce a third component in our architecture that we call Deployer (DP). As for the SA component, it is a "client-side" component and, as such, is instantiated on users' devices. Figure 4 completes our architecture of a software infrastructure for ubiquitous computing and details steps from the service choice by user (4) to deployment of the client part of the application (5, 6a and 6b). The components of the service that are running on fixed computerse.g. the component that extracts information on trains to send to users in our example -have been deployed and instantiated in a preliminary step and according to the same deployment process. Assembly that is downloaded on device only contains mobile components to be instantiated on user's terminal and interconnected to previously instantiated fixed components if necessary. The repository of assemblies mentioned in Figure 4 can be located on the service provider server or on a remote HTTP or FTP (or anything else) server.

Service Activator

Once all these steps achieved, end-user can use features provided by the contextual service, that is, in our case, accessing details on trains on departure. Nevertheless, the role of the DP component is not limited to deploy and instantiate selected services. In fact, this component is in charge of the entire life cycle of the application. In the context of ubiquitous computing, users arrive and go outside of ubiquitous environments. For instance, the user has taken his train which has started. When users will come in the railway station again, as they know (if they remember) that the "trains" service exists, they would like to use it immediately. That means not having to select one of the displayed SR ID, next waiting for the user's profile transmission, choosing the appropriate service and so on. The idea then is to keep in cache mobile assemblies of services that users would be likely to reuse. The DP component of our architecture allows that. If the user goes outside the network coverage zone, the DP component manages the different scenarios, depending on the type of service:

-The service is available in a "disconnected" state -This case has no consequence for the user (e.g. the "mailbox" example). -The service isn't available in a disconnected state (e.g. our "trains" example) -The DP asks if the user wants to completely remove the service from device or if he/she wants to keep assembly's archive of the service. In this last case, the mobile assembly is put in a cache (stored in the device flash memory) so that the user will be able to reuse it in future by just instantiating the client part of the application (i.e. only from step (6) in our architecture illustrated in Figure 6), obviously if the service is ever available. Service's versions management is done thanks a unique identifier attached to each service.

Implementation

To realize our component-based software infrastructure dedicated to ubiquitous computing, we choose the OMG CORBA Component Model (CCM). This section previously briefly describes this component model and the OpenCCM platform, which is an open-source implementation of this standard. Next, we detail implementation of the architecture of our software infrastructure defined in Section 4, especially the CORBA components of this architecture and their interactions. Then the implementation of the train service is discussed.

The OMG CORBA Component Model and OpenCCM

The CORBA Component Model is the first vendor neutral open standard for Distributed Component Computing supporting various programming languages, operating systems, networks and CORBA products seamlessly [START_REF]Object Management Group: CORBA Components Specification, version 3.0. OMG TC Document[END_REF]. This model is a specification defined by the Object Management Group (OMG) consortium for creating distributed, server-side scalable, component-based, language-neutral, transactional, multi-user and secure applications. Software components enhance the object paradigm. Moreover, the CCM defines an architecture dedicated to software engineering and more exactly to the life cycle of software development process: design, implementation, packaging, assembling, deployment, and execution. A CORBA component consists of a reference interface, a set of interaction ports and business attributes. Ports allow one to describe how a component is "communicating" with other components. As previously discussed in Section 3.1, the CCM defines four types of ports: facets, receptacles, event sinks and event sources. Finally, CCM provides an XML-based packaging and assembling facility coupled to an automatic distributed deployment process. The OpenCCM platform [START_REF]The OpenCCM Project[END_REF] is the first public available and open source implementation of the CCM specification. Since 2002, OpenCCM is hosted by the ObjectWeb consortium, an international consortium promoting open source middleware. The OpenCCM platform is fully written in Java and supports most of available Java-based CORBA products, i.e. JacORB, OpenORB, ORBacus or Borland Enterprise Server. OpenCCM is not only a CCM middleware platform for executing CCM applications but it also offers a methodology for building distributed applications including UML-based designing, packaging, assembling, deployment, and management tools. OpenCCM works on various operating systems like Linux, Solaris, Windows NT/2000/XP, and also Windows CE and Linux Familiar for PDA.

The Software Infrastructure Implementation

First of all, two CORBA components have been defined to respectively model the SR and the SA components specified in our architecture. The SR component provides a facet allowing users to get the list of available services. Also, it is represented by a GUI allowing administrators to manage this list. The SA component is represented by a GUI instantiated on user's device to display, firstly a list of SR that have been "detected", secondly the list of available services registered on each SR selected by user. What's more, a third CORBA component named Multicast has been defined to implement the interactions between the SA and the SR components during the services discovery phase (Figure 5). The generic Multicast component provides a facet implementing a "Send/Receive" service of multicast requests and is instantiated on each nodes (i.e. on all devices and servers). SA and SR components are both bound to the Multicast component (but not the same instance). SR uses the "Send" service to send its ID whereas SA uses the "Receive" one to get it. Using of multicast requests is well suited for the implementation of the discovery protocol in the context of a ubiquitous environment. Indeed, SA and SR components are not directly connected (from a CCM point of view), which was the original goal as user/device is not supposed to know about its environment before discovering it! As far as the deployment is concerned, a CORBA component implements the DP component. It provides a facet used by the SA component receptacle. This facet offers many operations for deploying the service. More precisely, the DP component is connected, through a receptacle, to the OpenCCM Distributed Component Infrastructure (DCI). The DCI infrastructure is designed as a set of CORBA components to manage the deployment phase of CCM applications [START_REF] Hoffmann | Specification of the Deployment and Configuration[END_REF]. Components of the DCI provide facets offering deployment operations as install an assembly by downloading it from a repository to the device, instantiate it or tear down it. Also, the DP's facet implements cache management of assemblies. Finally, the following figure shows the assembly of SA, SR, Multicast and Deployer CORBA components, connected to the OpenCCM DCI infrastructure: To experiment our infrastructure, we have also implemented the "trains" service using two CORBA components. A Server component is responsible of getting, from service provider's information system (SP-IS), and sending, through an event source, information on trains. A Client component, deployed on users' devices, receives these data through an event sink and displays a table using a GUI. Figure 6 illustrates on a PDA this example of service at work, i.e. after the service's dynamic discovery and its automatic deployment. A laptop has been used to host the Server component and the SP-IS and the network used is an IEEE 802.11b wireless network. Fig. 6. An example of service at work on a communicating PDA.

Limitations

The implementation of our software infrastructure for ubiquitous computing based on the CCM and the OpenCCM platform allows us to address the problems of the contextual services discovery and automatic deployment on user's device according to hardware/software capabilities. Nevertheless, some limitations should be emphasized:

-The size of assembly archives may cause some download time problems during the installation step of the deployment. This is due to the limited throughput of current wireless networks, and the way containers are generated in OpenCCM which implies component binary archives being in some case very large. A dynamic generation of container classes at execution time could address this problem by reducing the size and downloading time of assembly archives. -The multicast protocol had to be implemented using a specific hand-written component (Multicast). This component would be useless if multicast communications between CORBA components will be directly supported by the CCM platform. -Infrastructure's components (but also many ubiquitous services) use threads.

Management of these threads is done in the component business implementation code. This point can be avoided if the component's container will able to manage threads. -Security during service discovery, automatic deployment, and execution is not currently addressed in our infrastructure. This firstly requires the integration of security mechanisms like SSL secure communications at the ORB level, and access control at the OpenCCM container level. Secondly, security policies dedicated to our infrastructure must be defined and enforced. Some security integration works have been already prototyped for next OpenCCM versions. -Finally, this approach supposes the client part of the infrastructure (the SA, Multicast and DP components, with the OpenCCM application server and DCI components) being previously installed on devices. Currently, this is done manually. Solutions, as partnerships with device manufacturers for instance, should be considered.

Related Works

The OMG/ISO trader [START_REF]Object Management Group: Trading Object Service Specification, verion 1.0. OMG TC Document[END_REF] and the RM-ODP [START_REF] Leydekkers | Multimedia Services in Open Distributed Telecommunications Environments[END_REF] trader mediate advertisement and discovery of services. The implementation of our service registry could use such technologies. JINI [START_REF] Edwards | Core Jini Introduction[END_REF] from Sun Microsystems offers several ways to discover services. The Multicast Request Protocol permits to user's terminal to send a multicast request to a lookup service. The response is sent via a TCP unicast message. The opposite solution, named Multicast Announcement Protocol, is used by lookup services to announce their presence to any interested parties that may be listening and "in range" of the multicast scope of the lookup service.

The Appear Provisioning Server [START_REF]AppearNetworks: The Appear Provisioning Server[END_REF] from AppearNetworks is an infrastructure dedicated to service discovery and deployment. This allows deployment of wireless infrastructure in which applications and documents are available on users' terminal on dedicated places. Applications are developed independently of the infrastructure. In this sense, they do not provide a seamless solution for both infrastructure and services.

The AMPROS project [START_REF] Ayed | Deployment and Reconfiguration of Component-based Applications in AMPROS[END_REF] aims to study and develop a middleware for mobile environment. As our proposal, it is based on CCM and the OpenCCM platform. They are developing a set of tools to adapt the applications at runtime.

Conclusion

Ubiquitous and context aware applications are one of the new challenges in distributed computing area. Until now, there is no global solution from the design step to the execution step to build such applications. To address this challenge, we have presented in this paper a global solution based on distributed software components to build both ubiquitous context aware applications and the required discovery and automatic deployment infrastructure. This solution has been designed on top of the OMG's CORBA Component Model and implemented using the OpenCCM platform. A sample train service example has been designed, prototyped and already run on top of PDA devices and wireless networks.

Our future works will go in two directions. Firstly, we want to experiment our approach on other service scenarios in order to define a model-driven methodology to build ubiquitous contextual services independently of underlying execution platforms. Secondly, according to the current limitations listed in Section 5.3, we will enhance the OpenCCM platform in several directions: dynamic container generation to reduce the size of assembly archives and improve downloading time on slow wireless networks, integrate multicast communications in the CCM model, integrate a threading service inside CCM containers, and address security at the different required levels (i.e. in underlying CORBA middleware, in runtime containers, and in discovery and deployment components).

Fig. 1 .

 1 Fig. 1. The Train Service Use Case.

Fig. 2 .

 2 Fig. 2. The train service as a composition of distributed software components.

Fig. 3 .

 3 Fig. 3. The negotiation protocol steps of the contextual services list discovery.

( 4 )Fig. 4 .

 44 Fig. 4. Service selection and deployment on user's devices.

Fig. 5 .

 5 Fig. 5. The CORBA Components Assembly of the Service Discovery and Automatic Deployment Infrastructure.

Table 1 .

 1 Power consumption of some IEEE 802.11x wireless cards

		TX Mode	RX Mode	RX/TX
	802.11b Compaq WL110 [4]	280 mA	180 mA	65 %
	802.11b/g Buffalo AirStation G54 [5] 550 mA	350 mA	64 %
	802.11a/b/g Dlink DWL-AG660 [6]	500 mA	379 mA	75 %

Other interaction patterns could be considered as continuous data flow, asynchronous invocations with wait-by-necessity, etc. However these patterns are not currently needed for our prototyped services.

Here we reuse the terminology defined in the CORBA Component Model.

Replication of components is out of the scope of this paper.

 [START_REF]Object Management Group: CORBA Components Specification, version 3.0. OMG TC Document[END_REF]This work is completed with the support of Nord/Pas-de-Calais Regional Council and the Regional Management of Research and Technology of Nord/Pas-de-Calais within the framework of the "Contrat Plan Etat/Région".


Alexis Conesa

MULTISCALE NETWORK IN A METROPOLITAN REGION Accessibility indicators to estimate territory structuring in Nord-Pas-de-Calais

Keywords: Multiscale network system, Metropolitan region, territory structuring, accessibility, Service modelling

In the thematic of relations between transport networks and territorial processes, in particular that of metropolisation, we locate as spatial planners. Thus, we tend to consider transport networks as a tool for territory planning and construction. According to this point of view, this essay lies in an analysis of transport service in a metropolitan region. Applied to the case of Lille metropolitan region, the work address for opportunities of territorial and metropolitan construction offered by transportation service. Furthermore, the goal is to work out proposals of organization improvements, in an action-oriented approach.

To do so, measures of accessibility are used. They are developed in software which models transport networks in a scheduled graph, using graph theory and shortest path algorithms. This equipment allows simulations, part of a forecasting approach.

INTRODUCTION

We currently consider that demographic growth and spatial spreading of larger cities inside their own region gave birth to "metropolitan regions". These ones are multifunctional, containing both dense centretowns and less dense areas, but keep a kind of cohesion [START_REF] Ferrier | De l'urbain au post-urbain : théorie géographique de la métropolitain et prospective pour une habitation durable des territoires[END_REF]. The process of metropolisation involves the combination of several phenomena: concentration, linking of different places, appropriation of the territory by people and mobilization of private and public territorial players. These processes are strongly linked with increasing spatial mobility possibilities. If one can agree that car is one of the main factors involved in the metropolisation processes, we can nevertheless consider the opportunity of a development of collective transport. Indeed, on the one hand urban flows are generally channelled and concern masses of people, and on the other hand, car showed its limits (congestion…).

The main aim of this communication is to relate the development of public transportation service with the metropolisation process.

PROBLEM STATEMENT

The study object is conceptualized as the metropolitan collective transport network system. Although this system is reticular, it is also territorial, possessing some thickness ("épaisseur") [START_REF] Pucci | Interconnexion et rôle des noeuds d'infrastructures : du sectoriel au général[END_REF]. That is why we refer to the territorial system and its three aspects defined by Maryvonne LeBerre [START_REF] Leberre | Territoires[END_REF]: shape of the networks ("matérialité physique"), running by interactions between different components ("organisation") and appropriation of the territory by networks practices, from people and institutional players ("entité territoriale").

In fact, this object is distinguished by its multiscalar nature. These transport networks can indeed serve territories at different scales, from communal networks to international railways. These scale-different networks are superimposed, entangled, and sometimes overlapped in order to better answer to the explosion of mobility.

Yet transport network planning is not conceived the same way whether one wants to connect city boroughs or to link urban areas in a region.

Our position here is to understand transports like a tool of territorial construction [START_REF] Dupuy | L'urbanisme des réseaux[END_REF]. Thus, the criterion to estimate opportunities offered by transport service, and further to propose hypotheses of improvement, will be the potential to help building a metropolitan region. More precisely, the services must allow concentration in urban poles, link places together and incite territorial appropriation. In fact, the transport service must allow the metropolitan region to work in a coherent way, which means linking places according to type and scale of the urban functions they foster. By linking a polarity to another complementary polarity at an appropriate period, transport services structures territory. This structuring includes hierarchy, appropriation and economical and social working.

To deal with this issue with an action-orientated approach, the study is applied to the Lille metropolitan region in the Nord-Pas-de-Calais, France. The main issue concerns the use of high speed at a regional level through TER-GV (Train Express Régional à Grande Vitesse, High speed regional express train) and weakness of the links between secondary poles.

METHODOLOGIES

According to the works of spatial planners modelling transport networks in a territorial perspective [START_REF] L'hostis | Cadencement et intermodalité de l'offre en transport collectif en Nord-Pas-de-Calais-Analyse et propositions d'amélioration[END_REF] [7] [START_REF] Stathopoulos | Performance territoriale des réseaux de transport[END_REF], we use the concept of accessibility to estimate territorial results of transport networks. Accessibility, representing the more or less high easiness of moving from one place to another in order to carry out an activity, can be defined as a measure of spacing or gap between places, "une généralisation et une particularisation du concept de distance" (a generalization and a particularization of the concept of distance) [START_REF] Dumolard | Accessibilité et diffusion spatiale[END_REF]. However, accessibility introduces also a notion of opportunity, because of the goal of the trip. Indeed, in this meaning [START_REF] Bavoux | Géographie des transports[END_REF], we can measure accessibility to a function and not simply a place; this function is the attractor of the trip. So, here the choice is made to measure accessibilities at places fostering a metropolitan function. Doing this we attempt to address directly the capacity of the multiscale transport network system to permit metropolitan good running. The general idea is that a network permitting good access to metropolitan functions can strengthen region's organization and cohesion. Plus, if this access is made possible daily and relatively continuously in time, we can make the hypothesis that it would contribute to develop some habits and so a potential appropriation from population. This method does therefore not focus on spatial processes but rather on space-time organization. In consequence modelling is directly following the subjects of Time-Geography. Accordingly, transport supply is modelled in a scheduled graph, which is a graph (nodes and edges) representing transport networks, but taking into account departure and arrival schedules, instead of usual costs attributed to the edges. MapNod software offers, through accessibility indices (with shortest path algorithm), an action-oriented simulation tool, valuing at a disaggregated level. Therefore, it avoids a set of simplifications that could lead to some mistakes, because transport supply includes components of demand [START_REF] Baptiste | Evaluation multimodale des systèmes de transport en Nord-Pas-de-Calais et en Languedoc-Roussillon. Enjeux pour l'aménagement de territoires régionaux -Approche par analyse de la qualité des services de transports en commun et de l'accessibilité routière[END_REF]. In addition, this tool gives some possibilities in valuing adequacy to urban rhythms, through «arrival schedule constraint», which is for example a nine o'clock arrival at some given working place.

EXPECTED RESULTS

Evaluation through accessibility measures toward metropolitan functions would allow us to test different possibilities, representing spatial planning choices. Inspired by Vodoz's territorial organization principles (mixing, density, polycentricity) [START_REF] Vodoz | Les territoires de la mobilité -L'aire du temps[END_REF], introduced like recommendations in territorial planning, which aim to reduce energetic consumptions, we can bring in three scenarios. These suit to the will to promote collective transports in metropolitan regions present here. More precisely in proposing an efficient service at different scales, adequate with urban rhythms and organized according to a spatial planning principle. Results would show an organization principle designed to promote territorial construction, particularly in the case of Lille metropolitan area.

FURTHER DEVELOPMENTS

In order to include new components of metropolitan collective transport network system, we can propose to link accessibility indices with morphological indices, relating shape with function.

CONCLUSIONS

Aiming at analysing transport service in a metropolitan region and furthermore at proposing a territorialized action designed to deal with metropolitan construction, we develop a forecasting approach based on simulations and scenarios. To do so modelling software is mobilized. The methodology is based on scheduled graph modelling, departing from the classical gap between supply and demand (Four step models…). Moreover, scheduled accessibility measures offer an alternative to the simple average travel time measure, which doesn't vary in time or only distinguishes peak and off-peak periods.

AUTHORS INFORMATION

Alexis CONESA conesa@inrets.fr Theoretical Geography University


Jean-Sébastien Franco

LJK Edmond Boyer

Learning Temporally Consistent Rigidities

We present a novel probabilistic framework for rigid tracking and segmentation of shapes observed from multiple cameras. Most existing methods have focused on solving each of these problems individually, segmenting the shape assuming surface registration is solved, or conversely performing surface registration assuming shape segmentation or kinematic structure is known. We assume no prior kinematic or registration knowledge except for an over-estimate k of the number of rigidities in the scene, instead proposing to simultaneously discover, adapt, and track its rigid structure on the fly. We simultaneously segment and infer poses of rigid subcomponents of a single chosen reference mesh acquired in the sequence. We show that this problem can be rigorously cast as a likelihood maximization over rigid component parameters. We solve this problem using an Expectation Maximization algorithm, with latent observation assignments to reference vertices and rigid parts. Our experiments on synthetic and real data show the validity of the method, robustness to noise, and its promising applicability to complex sequences.

Introduction

The problem of spatio-temporal modeling from multiple images has gained a lot of attention from researchers in recent years. The topic is becoming increasingly popular for applications related to shape acquisition, shape analysis, thanks to emerging technologies in the industry such as 3D television, entertainment based on 3D and full-body interaction. This is creating an ever increasing demand for robust space-time shape acquisition methods, for offline and real-time 3D content production.

The problem remains challenging for the vision community. Historically shape acquisition has first been addressed in a temporally independent manner, using sets of images of a single instant. This however leaves out an important source of redundancy and improvement in the case of temporal sequences. In recent years various surface deformation and tracking models have become very popular Figure 1. Convergence of the method in fitting frame 30 of Lock sequence (courtesy U. Surrey [START_REF] Starck | Correspondence labelling for widetimeframe free-form surface matching[END_REF]), using frame 20 as reference (left). Target observation points are shown in blue, color lines show probabilistic associations from observations to reference vertices. The method estimates rigid clusters coherent with both the spatial and motion characteristics of the model, in particular recovering the correct partition and motion of arm and forearm.

to leverage temporal information of multi-video sequences.

A number of such approaches treat surface acquisition as the fitting of a deformable surface model based on image cues or 3D points obtained from stereo or visual hull techniques [START_REF] Laurentini | The visual hull concept for silhouette-based image understanding[END_REF][START_REF] Seitz | A comparison and evaluation of multi-view stereo reconstruction algorithms[END_REF]. This gives positive results with little prior knowledge of the surfaces, on the other hand it leaves out important cues about the scene such as rigidity, as it usually uses only surface smoothness and continuity criteria for space-time reconstruction, yielding generally underconstrained methods. On the other end of the spectrum, one can constrain reconstructions by using specific prior models such as a kinematic structure, through a reduced parameterization of surface movement. This however comes at the cost of genericity, often yielding specific, overconstrained methods that hardly handle the variability of real surface data. To lift this limitation and find a middle ground between genericity and efficient priors, researchers have sought to automatically identify rigid parts and kinematic structures in a pre-processing step. The main trend in the computer vision community has been to deal with the problem in 2D images, where occlusion discontinuity modeling is mandatory, or for the case of 3D point clouds, without a strong modeling of spatial coherence. Meanwhile the main trend in the graphics community has been to focus on kinematic segmentation of 3D surfaces from prominent spatial characteristics of the surface in a static pose [START_REF] Shamir | A survey on mesh segmentation techniques[END_REF], with the intrinsic limitations of not observing the actual rigidity in motion.

The method we propose has two contributions with respect to these existing research trends. First we show that segmentation and surface tracking stages need not be separated and can be efficiently performed simultaneously, through the online discovery, adaptation and alignment of rigidities. Second we propose a principled model to take advantage of both the spatial and temporal cues meaningfully for the segmentation ( §3). We cast the problem as a Bayesian estimation of spatial and temporal rigid cluster parameters, over a given reference mesh of the observed scene. We assume the surface is subsequently observed through a set of unaligned sparse 3D points obtained from vision systems. We solve the estimation problem using an Expectation Maximization algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the em algorithm[END_REF], while estimating distributions over latent variables modeling both the probabilistic segmentation of the surface into rigid parts, and the noisy matching of observed points to the reference mesh ( §4). The model automatically estimates the position and temporal transforms of each cluster ( §4.1), while dealing with noise and outliers among the 3D observations ( §4.2). The main benefits sought with this approach is to simultaneously increase genericity and robustness of methods through common estimation of rigidity segmentation and shape tracking. Implementation details, experimental validation, and future work are discussed in §5, §6 and §7.

Related Work

Deformable Surface Tracking Deformable surface tracking is one of the most active trends to tackle the spatio-temporal modeling problem [START_REF] De Aguiar | Markerless deformable mesh tracking for human shape and motion capture[END_REF][START_REF] De Aguiar | Performance capture from sparse multi-view video[END_REF][START_REF] Vlasic | Articulated mesh animation from multi-view silhouettes[END_REF][START_REF] Cagniart | Probabilistic deformable surface tracking from multiple videos[END_REF][START_REF] Furukawa | Dense 3d motion capture from synchronized video streams[END_REF]. The topic has been addressed both in the computer vision and graphics communities, either with weakly constrained surfaces not taking advantage of rigidities [START_REF] De Aguiar | Markerless deformable mesh tracking for human shape and motion capture[END_REF][START_REF] Furukawa | Dense 3d motion capture from synchronized video streams[END_REF] or including a strong rigidity prior [START_REF] De Aguiar | Performance capture from sparse multi-view video[END_REF][START_REF] Vlasic | Articulated mesh animation from multi-view silhouettes[END_REF], such as an underlying kinematic skeleton, which is not learned but imposed at initialization. The most recent successful approaches opt for a more flexible model of rigidity based on patches [START_REF] Cagniart | Probabilistic deformable surface tracking from multiple videos[END_REF], in fact casting the problem as an EM, but still leaving aside the problem of rigidity learning. We propose to take this family of approaches one step further, in simultaneously addressing both mesh tracking and segmentation cast as a single, cooperative learning problem.

Shape Segmentation and Matching Static shape segmentation has received considerable attention in the computer graphics community [START_REF] Shamir | A survey on mesh segmentation techniques[END_REF], only considering the spatial aspect. They are fundamentally limited for the problem of rigidity detection, as rigidity itself is a dynamic notion. Some recent works in the graphics community have considered the rigid segmentation of dynamic meshes, but mainly with the limitation that the meshes are pre-aligned, e.g [START_REF] Lee | Segmenting a deforming mesh into near-rigid components[END_REF]. There is a growing interest in both vision and graphics communities for spectral clustering methods [START_REF] Jain | Non-rigid spectral correspondence of triangle meshes[END_REF], sometimes applied to shape segmentation [START_REF] Sharma | Learning shape segmentation using constrained spectral clustering and probabilistic label transfer[END_REF], but the emphasis in these methods is more on the continuous matching problem between general static poses than the temporal evolution aspect. A goal of our method is to leverage both the spatial and dynamic cues of spatio-temporal sequences for segmentation and tracking.

Motion Segmentation and Factorization A large body of work exists in the vision community for segmenting motion in 2D images using various cues such as color, and optical flow [START_REF] Brox | Object segmentation by long term analysis of point trajectories[END_REF]. This comes with intrinsic image-domain problems, such as occlusions, light perception, with less than ideal image domain specific solutions such as occlusion boundary detection or image domain smoothing. The latter is a way of using spatial coherence, but is best performed in 3D as soon as 3D information or multiple views are available. Indeed 3D rigid segmentation has been addressed in the vision community [START_REF] Tron | A benchmark for the comparison of 3-d motion segmentation algorithms[END_REF], including the analysis of kinematic chains [START_REF] Yan | A general framework for motion segmentation: Independent, articulated, rigid, non-rigid, degenerate and nondegenerate[END_REF], but mainly for the case of sparse set of 2D feature points, sometimes lifted in 3D through matching, if multiple views are available. Again we see benefit in taking this type of approach further, by using spatial continuity together in surface matching and tracking.

Modeling

Model Overview

We assume an object of interest is observed moving through a set of 3D point clouds, obtained from a vision system. We wish to identify the rigid parts of the object, and their motion over time. Given a reference mesh of the object, these two goals translate to two association problems. First, associate each reference vertex to a rigid part, determining a rigid segmentation of the reference mesh. Second, associate each 3D observation at each time t to a vertex of the reference mesh, thus determining the motion of reference mesh vertices at time t. A key difficulty here is that both problems are considered simultaneously and intertwined, as shown in the proposed graphical model Fig. 2.

Let X = {X v } v∈V be the set of 3D coordinates associated to each vertex of reference mesh, with V the set of vertices. Let O = {O t o } t∈T ,o∈O t , be the sets of sparse 3D surface points observed, where T is the time span considered and O t the set of observations at time t.

The segmentation problem is governed by a set of parameters C = {C k } k∈K describing the distribution of rigid parts over the reference mesh, and a set k k k v of unobserved rigidity selection variables per-vertex v of the reference

v ∈ V o ∈ O t k k k v X v C k T t k v v v t o O t o π k α t k ∈ K t ∈ T

Motion associations

Rigid segment associations

Figure 2. "Naive" model mesh, describing an association hypothesis of v to a rigid cluster. As a modeling simplification, in this paper we consider that the reference mesh points are to be classified according to their 3D coordinates X v using a Gaussian Mixture Model, where C = {C k } k∈K are the parameters (mean and covariance matrices of the GMM), with mixing coefficients π k . This simple model discriminates rigidities as quasi-convex subvolumes, which is sufficient to validate the method.

The motion problem is parameterized by a set of rigid transforms T = {T t k } k∈K,t∈T , for each rigid cluster k ∈ K and time t ∈ T , and a set of discrete vertex selection variables v v v t o describing the reference vertex association hypothesis for each observation o at time t. v v v t o can take any value in {V ∪ ∅}, including a garbage association ∅ for the case where the o'th observation is an outlier. The prior proportion of outliers at time t is noted α t , to be learned by our model. Importantly, a given observed 3D point O t o is treated as the noisy measurement of a reference vertex coordinate X v , once displaced by the transform T t k k kv associated to that vertex's cluster k k k v . k k k v is thus required to make this prediction, inducing the bold causal link represented in the graph.

Resolution and Tractability

The full problem can be cast as a likelihood maximization over C k and T t k , given the knowledge of the reference mesh X and all observations O. Because of the presence of latent variables, the solution can be found using Expectation Maximization (EM) [START_REF] Dempster | Maximum likelihood from incomplete data via the em algorithm[END_REF]. The segmentation and motion association problems are interrelated through the variable group k k k v : in other words, for a cluster k to have a high likelihood, it needs to cluster spatially consistent points on the reference mesh, while simultaneously predicting a subset of each t's observations from these points with a single rigid transform T t k . This problem is thus significantly harder to solve than anyone of the association problems alone.

The difficulty materializes for the E-step of the full problem, which needs to compute a distribution over the selection possibilities

k k k = {k k k v } v∈V and v v v = {v v v t o } t∈T ,o∈O t
given the current parameter estimates (i.e. the full posterior p(k k kv v v|XOCT π)). The current model implies that probabilities over rigid associations k k k and vertex association v v v are interdependent, because of the bold causal link in Fig. 2: the posterior p(k k kv v v|XOCT π) doesn't factorize as a product of simpler distributions, and thus yields an intractable Estep. Favorable factorization is identified to occur when the selection variables satisfy the D-separability criterion [START_REF] Bishop | Pattern Recognition and Machine Learning (Information Science and Statistics)[END_REF], i.e. when a clearly separated subset of selection variables is used to predict separate measurements, as is the case e.g. for simple GMMs.

Tractable Model

To obtain a tractable EM algorithm, we assign each observation o with a local duplicate of the segmentation problem, as shown in Fig. 3. Thanks to this duplicate, the causal links involving segmentation and motion associations in the model will now be contained as per-observation terms, as opposed to Fig. 2 where observation predictions needed potentially arbitrary rigid segment selection variables k k k v .

In other words, each observation o is given its own independent set of rigidity selection variables {k k k t o } t∈T ,o∈O t , governed by the same rigidity mixing priors π k . The method thus partitions not only static reference mesh vertices among rigid GMM clusters, but also the 3D observations themselves through this set of redundant selection variables. The set of reference mesh coordinates is also locally duplicated as X t o,v . We write the predictive distributions over X t o,v so as to allow only the associated coordinate

X t o,v v v t o of the reference mesh vertex v v v t
o to be predicted by the GMM's k k k t o 'th component. This allows each observation o to contribute an additional sample to the static segmentation GMM, as selected by its selection variables k k k t o and v v v t o .

k ∈ K v ∈ V o ∈ O t t ∈ T k k k v X v C k π k T t k α t k k k t o v v v t o O t o X t o,v v ∈ V Figure 3. Complete model
For readability, we introduce Θ = πα} the set of method parameters to be estimated, Z = {v v vk k k} the set of latent variables, and M = {OX} set of known We can then write model likelihood as follows:

p(M Z|Θ) = v∈V p(k k k v |π) p(X v |C k k k v ) (1) o,t p(v v v t o |α) p(k k k t o |π) p(O t o |X v T t v v v t o k k k t o ) v∈V p(X t o,v |C k k k t o v v v t o ) Note that v∈V p(X t o,v |C k k k t o [v v v t o = ∅]) simplifies to p(X t o,v v v t o |C k k k t o [v v v t o = ∅]) in this expression, by choosing ref- erence coordinates for v = v v v t
o to be predicted uniformly in space regardless of C, and thus discarded, which effectively enables to select the v v v t o 'th coordinate as a rigid GMM sample, as previously mentioned. To account for the outlier selection case, we set p(

X t o,v |v v v t o = ∅) = U(X t o,v , S) = 1 V
regardless of other parameter values, that is, uniform spatial prediction over the reference bounding volume.

Choosing parametric distributions

Selection distributions p(k k k v |π), p(k k k t o |π) and p(v v v t o |α t ).
The rigidity selection variables are drawn from their corresponding mixture prior :

p(k k k v = k|π) = π k , resp. p(k k k t o = k|π) = π k . p(v v v t o |α t
) models the expected proportion of outliers in the data governed by

α t : p(v v v t o = ∅|α t ) = α t , p(v v v t o = ∅|α t ) = 1-α t |V| = ᾱt .
Note that there is no outlier class in K: we assume the reference mesh is not noisy, as such all of its vertices should be classified according to static clusters C.

Observed vertex displacement p(O t o |X T t v v v t o k k k t o
). We assume that each T t k = {R t k , σ k }, with R t k a rigid transformation matrix from the canonical pose to the curent pose. As in other similar methods [START_REF] Cagniart | Probabilistic deformable surface tracking from multiple videos[END_REF], we assume that the predicted position is perturbed by Gaussian noise. The noise in this case is better modelled as isotropic, as we expect no dominant noise orientation in the way displaced vertices can predict each observed datum. Thus, when v v v t o = ∅:

p(O t o |X T t [v v v t o = ∅] k k k t o ) = N (O t o |R t k k k t o (X v v v t o ), σ 2 k k k t o I). (2) When v v v t o = ∅,
we use a spatial uniform distribution over R 3 to model outliers predictions (they don't depend on model parameters T and C):

p(O t o |v v v t o = ∅) = U(O t o , V ) = 1 V , ( 3
)
where V is the reference mesh bounding volume.

Mesh

classification terms p(X v |C k k k v ) and p(X t o,v v v t o |C k k k t o ). With the GMM parameterization we note C k = {µ k , Σ k } over R 3 : p(X v |C k k k v ) = N (X v |µ k k kv , Σ k k kv ), (4)
p(X t o,v v v t o |C k k k t o ) = N (X t o,v v v t o |µ k k k t o , Σ k k k t o ), (5)
where µ and Σ are the centroid and covariances modeling the cluster shape. Note that we keep the full covariance matrix description in this case as we expect spatial clusters to have a variety of shapes over the reference mesh, not necessarily circular. Other more complex prediction models could be explored in future work.

Final likelihood expression

By substituting the different terms, and using an indicator variable δ v v v t o with value 1 if v v v t o = ∅ and 0 otherwise, and

δ v v v t o = 1 -δ v v v t
o , we obtain:

p(M Z|Θ) = v∈V π k k kv N (X v |µ k k kv , Σ k k kv ) (6)
o,t

{ᾱ t π k k k t o N (X t o,v v v t o |µ k k k t o , Σ k k k t o ) N (O t o |R t k k k t o (X v v v t o ), σ 2 k k k t o I)} δv v v t o {α t U(X t o,v , S) U(O t o , V )} δ v v v t o

Inference

Finding the optimal clustering and rigid parameters translates to maximizing the following log likelihood:

Θ * = max Θ ln p(M |Θ) (7)
The following EM helper function Q(Θ|Θ j ) can be defined to solve this goal with the latent variables Z [START_REF] Bishop | Pattern Recognition and Machine Learning (Information Science and Statistics)[END_REF], by substitution of the different variable groups (state, latent, observed) in the generic definition:

Q(Θ|Θ j ) = E Z|M Θ j {ln p(M Z|Θ)} = Z p(Z|M Θ j ) ln p(M Z|Θ). (8)
The associated E-and M-steps are as follows:

E-Step: Compute p(Z|M Θ j ), (9)
M-Step:

Θ j+1 = max Θ Q(Θ|Θ j ). (10)

E-step updates

Let us analyse the expression of p(Z|M Θ j ). First let us note that, by construction, the groups of selection variables {k k k v } v∈V and {k k k t o , v v v t o } o∈O t ,t∈T are now D-separable according to the complete graphical model (Fig. 3) and thus independent under this posterior distribution:

p(Z|M Θ j ) = v∈V p(k k k v |M Θ j ) t∈T ,o∈O t p(k k k t o v v v t o |M Θ j ). (11)
The E-step consists in tabularizing these two sets of distributions, seen as functions of k k k v , and (k

k k t o ,v v v t o ): β(k k k v ) = p(k k k v |M Θ j ) = π j k k kv N (X v |µ j k k kv , Σ j k k kv ) k k kv π j k k kv N (X v |µ j k k kv , Σ j k k kv ) (12) γ(k k k t o , v v v t o = ∅) = p(k k k t o v v v t o |M Θ j ) (13) = 1 w π j k k k t o ᾱt,j v v v t o N (X t o,v v v t o |µ j k k k t o , Σ j k k k t o ) N (O t o |R t,j k k k t o (X v v v t o ), σ j k k k t o 2 I), γ(k k k t o , v v v t o = ∅) = 1 w α t,j U(X t o,v , S) U(O t o , V ), ( 14
)
where w is a normalization constant ensuring γ is a distribution over (k k k t o , v v v t o ). Note that the β-functions correspond to the usual E-step for GMMs, as applied here to reference mesh point clustering, while the γ-functions can be seen as a variant accounting for the transformation coherence and outlier rate, for each pair

(k k k t o , v v v t o ).
The state space for each γ-function is quite large, thus we shall compute it sparsely, with the most likely

(k k k t o , v v v t o )
pairs. An algorithm to retrieve the best pairs will be discussed in §5.

M-step Updates

Substituting the definitions of β(k k k v ) and γ(k k k t o , v v v t o ), the expression of Q(Θ|Θ j ) can be written as a sum of terms each involving only one of the maximization variables:

Q(Θ|Θ j ) = Z v∈V β(k k k v ) t∈T ,o∈O t γ(k k k t o , v v v t o ) ln p(M Z|Θ) = v k k kv β(k k k v ){ln π k k kv + ln N (X v |µ k k kv , Σ k k kv )} (15)
+ o,t k k k t o ,v v v t o =∅ γ(k k k t o , v v v t o ){ln π k k k t o + ln N (X t o,v v v t o |µ k k k t o , Σ k k k t o )} + o,t k k k t o ,v v v t o =∅ γ(k k k t o , v v v t o ){ln ᾱt + ln N (O t o |R t k k k t o (X v v v t o ), σ 2 k k k t o I)} + o,t k k k t o ,v v v t o =∅ γ(k k k t o , v v v t o ) ln α t + const.(Θ).
Q(Θ|Θ j ) can be maximized by maximizing separately the group of sum terms corresponding to each of the parameters in Θ = {CT πα}. Fortunately, most of the updates can be computed in closed form, yielding a set of update equations for the M-step presented below. For concision and clarity, the complete derivations have been omitted in this paper, but will be made available as technical report.

Updating π k , the mixing coefficients. Defining N and N k as follows, the π k update can be written:

N = |V| + t∈T |O t |, (16)
N k = v∈V β v (k) + o,t,v∈V γ t o (k, v), (17)
π j+1 k = N k N . ( 18
)
Updating (µ k , Σ k ), the spatial cluster parameters. It can be shown that the update equations maximizing (µ k , Σ k ) are as follows:

µ j+1 k = 1 N k   v∈V β v (k)X v + o,t,v∈V γ t o (k, v)X t o,v   , (19)
Σ j+1 k = 1 N k v∈V β v (k)(X v -µ j+1 k )(X v -µ j+1 k ) (20) + 1 N k o,t,v∈V γ t o (k, v)(X t o,v -µ j+1 k )(X t o,v -µ j+1 k ) .
The form of these updates (including π k ) make sense considering the form of the classical GMM Gaussian update equations, by noting that in fact the samples of our Gaussian updates are given by all reference mesh coordinates X v on one hand, and the coordinates X t o,v , as selected through the various vertex and rigidity matching hypotheses for each observation, on the other hand. This explains the form of our mean and covariance updates, a weighted combination of these terms in two summation groups.

Updating α t , the outlier rate for each time step. Setting the partial derivative to 0 for each α t , we obtain:

α t,j+1 = 1 |O t | o,k γ t o (k, ∅), (21)
which corresponds quite naturally to summing the (already normalized) weights of outlier observation assignments for each time step considered.

Updating T t k , the transform parameters. Obtaining the transform parameters for each instant and rigid part can be obtained by maximizing the corresponding terms in

Q(Θ|Θ j ) with respect to R t k : R t,j+1 k = max R t k o,v∈V γ t o (k, v) ln N (O t o |R t k (X v ), σ 2 k I) = max R t k o,v∈V γ t o (k, v) O t o -R t k (X v ) 2 . ( 22
)
The latter can be recognized as a weighted orthogonal Procrustes problem. Only a subset of pairs (k, v) ∈ P yield non-zero γ t o (k, v) values. We collect these values in a size-|P| diagonal matrix W , and collect the X v and O t o coordinates appearing in the corresponding sum terms in (22) in two 3 × |P| matrices x and o. The rotational and translational components (R t) of R t,j+1 k can then be retrieved using the SVD of a 3 × 3 matrix defined as follows:

x = xW -x, (23) ô
= oW -ō, (24)
R = V U with the SVD of xô = U DV , (25)
t = ō -Rx, (26)
where x and ô are reweighted, zero-centered versions of x and o.

Updating the rigidity variances σ k . To update σ k , we differentiate (22) w.r.t. σ 2 k , obtaining:

σ j+1 k 2 = o,v γ t o (k, v) O t o -R t,j+1 k (X v ) 2 o,v γ t o (k, v) . ( 27
)
5. Implementation

Computing sparse γ-tables

To compute each γ table sparsely for a given observation o, we need to identify the best set of hypotheses (k, v). γ can be seen as a function attributing a matching weight to each vertex-cluster pair. To retrieve the best candidate matches, we solve a series of K-Nearest Neighbor problems, by constructing a search space with |K| × |V| candidates, corresponding to each (k, v) hypothesis, i.e. each reference vertex transformed with each cluster transform. Each candidate is normalized using the respective cluster covariances to retrieve nearest neighbors in the sense of Mahalanobis distances. Then, for each observation in O t , we look for the K-nearest neighbors where K is a supplied parameter (in practice fixed to 5 or 10), to keep the K-best γ values. Nearest Neighbor structures thus need to be built only once per EM iteration. Note that as a result, every update sum and expression involving (k, v) can be sparsely evaluated.

Processing Time Sequences

The proposed framework can be used to process sequences of input observations with proper incremental initialization. Because EM converges to local minima and is initialization dependent, the framework is best used in sequence, starting from a position close to the reference mesh. With such starting conditions, the algorithm easily finds correct solutions, with a simple initialization strategy for all experiments, e.g. Fig. 1. We initialize cluster parameters with centroids on a randomly selected reference mesh vertex, with covariance matrices randomly generated with the order of magnitude of the bounding box. Cluster transforms are initialized to identity, and mixing coefficients to uniform. Sequences can then be processed using a chosen sliding window of size W , where each new observation set entering the window is initialized with the transforms and cluster parameters computed at the previous time step with some random perturbation. We obtain promising results with these simple strategies; arguably better initializations could be explored in future work.

Experimental Results

We validate the approach using two synthetic datasets and several real datasets, also shown in the supplemental video 1 . Between datasets, only values of the sliding window size and expected number of rigidities |K| are to be set manually, although strategies to infer |K| could be applied from existing EM literature in future work. Best and more stable results were obtained by estimating identical variances for all transforms T . The computed parameters and E-step tables encode a continuous mesh deformation defined by the spatial clusters C, the β-tables which encode class probabilities with respect to C, and the transforms T . This deformed position can be computed for each reference vertex v as the expectancy of its transformed position under β(k k k v ), or k k kv β(k k k v )X v , where β-tables are analog to skinning weights. Computation times on a single 2.53Ghzcore range from 100msec per iteration for simple datasets (CYLINDER) to a second per iteration (LOCK). The number of iterations before convergence is usually 10-40, with occasionally higher numbers (80-100) for the larger configuration changes within a sequence.

Validation on synthetic datasets

We validate the approach on synthetic datasets to evaluate performance of the method under controlled conditions. The first dataset used is a deformable cylinder with 1300 vertices, comprised of three rigid subcomponents (Fig. 4) folding over 22 frames. The first joint folds over frames 1 -10, then both joints fold subsequently. We process the dataset with a purely vertical reference position, so as to test the ability of the method to retrieve rigid parts unbiased 1 See http://hal.inria.fr/inria-00583131/en 2)-( 9), the method places the red and blue clusters correctly and puts the third cluster in the axis of the folding on frame [START_REF] Laurentini | The visual hull concept for silhouette-based image understanding[END_REF], which is a plausible solution reducing error in the fold. From frame [START_REF] Lee | Segmenting a deforming mesh into near-rigid components[END_REF] to ( 22), the method properly identifies the three rigid segments. Note how the RMS error drops from frame (11) on as soon as the new joint is solicited, when setting k ≥ 3 : this shows that the method did indeed detect the new rigidity upon occurrence, reducing positional error with respect to using only two rigidities. We use a second synthetic sequence with 200 frames, DANCER, to test the longer term behavior of the method. The sequence is tracked and segmented using 10 rigid parts. The human model in the sequence has 3000 vertices, only 1000 of which are samples randomly at each frame to simulate missing data. Despite the scarce number of parts, the method adapts the location of rigidities to observed degrees of freedom being solicited (e.g. a single rigid movement per leg often is sufficient to model the deformation). The method was able to track the model up to frame 120, despite large body motions and rotations such as shown frame 35 in Fig. 5.

Real datasets

We have processed various real datasets, LOCK (Fig. 1), BALL, DOG, and CRANE (Fig. 6). These mesh sequences were obtained from vision systems using visual hulls (BALL, DOG) or silhouettes and photoconsistency methods (CRANE, LOCK) [START_REF] Starck | Correspondence labelling for widetimeframe free-form surface matching[END_REF]. All datasets use a sliding window of size W = 2, keeping observations 5 frames apart for better coverage of observations on different poses. In all sequences the reference mesh used was the first model in the sequence, reduced to 3000 vertices for faster computation. Observations point clouds were constructed by extracting 1000 random unaligned points from sequence meshes, to illustrate method resilience to sparser data. All sequences were processed with k = 15 except for ball which was processed with k = 10. It was observed during experiments that the method performs better with lower rigidity counts: the convergence is better constrained in those cases. The method is able to process about 20 to 30 frames in motion for each sequence before significant artifacts occur. It finds rigid segmentations plausible with the shape and motion observed in the sequences, including arms, legs, forearms and forelegs for all sequences where they are observed moving. For example in the BALL sequence in Fig. 6(a), the main moving parts are the adult's upper body, and both person's forearms, which is consistent with the segmentation found. Results show that outliers are identified, such as the shadow volume in the BALL sequence or the small ball tossed in the DOG, which was not part of the reference mesh.

Limitations and Future Work

The method yields very encouraging results. Further improvement of the method is still possible. First the number of rigidities could be themselves learned with various strategies. The algorithm could easily monitor rigidity mixing weights and assignments, and their contribution to the total log-likelihood, to remove, split or merge rigidities. Second, although the simple initialization strategy used works in most cases, it doesn't guarantee systematic escapes of local maxima of the log-likelihood function, which sometimes translates to suboptimal segmentations being transferred from one frame to another. A hierarchical strategy could be explored to improve convergence properties. Third, terms related to surface regularization could be added. The fact that clusters softly partition the reference mesh into rigidities, does yield a weak form of surface regularization; this is not always enough to prevent folds and loss of tracking on complex sequences. Specific additional terms related to surface and inter-cluster regularization could be added to improve long-term robustness of the method. Finally, our proof-of-concept implementation is single-core, but virtually all update equations involve only individual variables and could be massively parallelized (GPU), bringing this method within reach for real-time applications.

Discussion

We have presented a novel learning technique to simultaneously address spatio-temporal mesh tracking and rigid segmentation. The framework developed is based on a principled graphical model and EM maximization algorithm, which performs unsupervised matching of unaligned observed point clouds sequences to a reference mesh, detects outliers, while segmenting the reference mesh and computing its rigid parameters. Resolution is done with simple, efficient and highly parallelizable EM updates. We are con- fident that the framework opens a new direction to cooperatively segment and track spatio-temporal mesh sequences.

FrameFigure 4 .

 4 Figure 4. Various frames of the cylinder dataset. Mesh vertices are colored according to the most likely rigidity according to its β table.Color lines are drawn from each observation to most probable matching reference positions and rigidity hypothesis (color) according to its γ-table. Observation points are shown in blue.

Figure 5 .

 5 Figure 5. Frames 1,5,20 and 35 of the dancer synthetic dataset.

Figure 6 .

 6 Figure 6. (a) BALL and (b) DOG sequence, courtesy 4drepository.inrialpes.fr. [1] (c) CRANE sequence, courtesy CSAIL-MIT [17]. Observation points are shown in blue if inlier, red if outlier (such as points on the ball's shadow in (a) or the ball tossed by the person in (b)). The method sometimes exhibits artifacts such as top (c) on the leg, due to an occasionally misfitted rigidity.

Acknowledgements

This work has been partially funded by grant ANR-10-BLAN-0206 of the French National Research Agency.