A Damala
email: areti.damala@orange-ftgroup.com

I Marchal

P Houlier
email: pascal.houlier@orange-ftgroup.com

MERGING AUGMENTED REALITY BASED FEATURES IN MOBILE MULTIMEDIA MUSEUM GUIDES

Keywords: Augmented Reality, Cultural Heritage, Mobile Museum Guides, Assisted Learning, Education, Entertainment

Augmented Reality (AR), a computer science field considered by many as a subfield of the broader concept of Mixed Reality, could alter dramatically the way we interact not only with computers but also with the real environment surrounding us, as well as with other human beings. Augmented Reality has so far been used for applications linked with military training, medicine, maintenance, architecture and urban planning, tourism, and entertainment. This last category embraces museums, considered by many not only as research and exhibition spaces but also as important informal learning environments. Does Augmented Reality has the potential to break into museum and exhibition environments and revolutionize the way we see, approach and comprehend the exposed exhibits, alongside with more traditional interpretation and communication methods? This presentation examines both the state of the art in Augmented Reality Applications for Cultural Heritage and Mobile Multimedia Guides for the museum setting, proposing an Augmented Reality approach for the last. A taxonomy of augmented and non augmented functions is proposed, aspects of the development are presented and reasons that could favor or slow down the integration of Augmented Reality in mobile museum guides are tackled down. The potential mutual benefits both for the Augmented Reality community as well as for cultural heritage professional are also presented briefly.

INTRODUCTION 1.1 Defining Augmented and Mixed Reality

Augmented Reality is a relatively recent computer science field considered as a subfield of the broader concept of Mixed Reality. Though the use of the first head mounted display dates back in 1968, the term started to become widely used after 1993, the year that the ACM Communications magazine dedicated an entire issue to the subject [START_REF] Cohen | Special issue on computer augmented environments: back to the real world[END_REF]. One year later, Paul [START_REF] Milgram | Augmented Reality: A call of displays on the Reality-Virtuality continuum[END_REF], in their approach of classifying Augmented Reality displays, defined what was thereafter to be known as the "Reality -Virtuality Continuum" which greatly helped the understanding of the interrelations between virtual, mixed and augmented reality environments. Mixed Reality environments are characterized by the combination of the real with the virtual. If the real world occupies the left of the continuum, the virtual world stands on the other end. It is however possible to combine elements of the surrounding, real world, in a virtual environment (Augmented Virtuality) as well as to overlay virtual objects in a view of the real world, if the last is observed or seen by means of a video or see-through display (Augmented Reality). It is therefore pertinent to define Mixed Reality (MR) environments as environments in which "real world and virtual world objects are presented together within a single display, that is, anywhere between the extreme of the Reality -Virtuality continuum" (ibid, p.283).

Hypotheses about the advantages of Augmented Reality

Augmented Reality is thought to present certain advantages over more traditional ways of accessing information [START_REF] Anastassova | User-Centred Design and Evaluation of Augmented Reality Systems for Industrial Applications: Some deadlocks and breakthroughs[END_REF]. The co-existence of the real and the virtual could enhance productivity by facilitating comprehension of tasks to be performed, in industry, medicine or education. In education specifically, Augmented Reality has been praised for its potential in the comprehension of physical phenomena, as demonstrated by the European "Connect" project [START_REF] Horn | Wings of learning[END_REF].

In addition, as the user is assisted by supplementing the existing world instead of creating a new one, the limited level of immersion is thought to provoke fewer problems of cyber sickness. Applications have been so far developed in the domains of military and medical training, urban planning and architecture, as well as for industrial maintenance work (eg in automotive and aerospace industry), entertainment and lately also for cultural heritage.

Augmented Reality for Cultural Heritage

Augmented Reality visualizations can provide extremely meaningful insights when applied in archaeological or historical parks or museums, not only for the specialist or initiated visitor but also for the non specialist or first time visitor who has a difficulty imagining how a site could initially have looked like.

Fixed Augmented Reality applications have been tested at the Ename centre in Belgium [START_REF] Owen | Visitors' Evaluations of ICTs Used in Cultural Heritage[END_REF] as well as in Portugal, Brazil and China [START_REF] Thomasson | Augmented Reality: Get in touch with the past[END_REF], while experimentations with outdoor mobile Augmented Reality systems have been carried out in the ARCHEOGUIDE [START_REF] Vlahakis | A novel approach to context sensitive guided e-tours in Cultural sites: Light augmented reality on PDA's[END_REF][START_REF] Vlahakis | Location and context aware Augmented Reality Nomadic Devices for cultural heritage applications[END_REF][START_REF] Vlahakis | Design and Application of an Augmented Reality System for continuous, context sensitive guided tours of indoor and outdoor cultural sites and museums[END_REF] and LIFEPLUS [START_REF] Papagiannakis | LIFEPLUS: Revival of life in ancient Pompeii, Virtual Systems and Multimedia[END_REF] projects.

The complexity of cultural heritage related information is also apparent in the case of museums and other cultural heritage institutions where the visitor often needs to be aware of social, political, cultural, historical, economic or scientific related aspects in order to better approach and appreciate the exposed object. It is for this reason that museums provide visitors with a wide range of interpretation media -textual, visual or auditoryand propose complementary activities in order to help the public elucidate the narratives revealed by the objects composing an exhibition. Multimedia and information technologies have been also employed in this context in various forms among which fixed position Mixed and Augmented Reality installations. These systems were reported to generate enthusiasm among the public [START_REF] Ferris | Shaping experiences in the Hunt museum: a design case study[END_REF], encourage interaction and co-participation [START_REF] Hindmarsh | Creating Assemblies: Aboard the Ghost Ship[END_REF] and favor the social character of the museum visit [START_REF] Galani | Far away is close at hand:an ethnographic investigation of social conduct in mixed reality museum visits[END_REF]. However rare are still the mobile Augmented Reality applications tested and implemented in the museum setting [START_REF] Sparacino | The Museum Wearable: real-time sensordriven understanding of visitors' interests for personalized visually-augmented museum experiences, Museums and the Web[END_REF]. This is quite unfortunate as museums present certain advantages regarding the overall development of Augmented Reality applications. Unlike applications designed for outdoor use, the museum offers a controlled, laboratory like environment [START_REF] Damala | Crafting the Mobile Augmented Reality Museum Guide[END_REF]. Documentation, research and interpretation are among the missions of museums. Consequently there exist usually different kinds of resources and media that can be used to help the visitor approach the exposed object, a fact that would allow the Augmented Reality research community examine in depth the way different types of multimedia can be coupled with Augmented Reality applications.

This argument leads to the next one: Unlike other Augmented Reality applications, destined for the experienced in a specific domain user, museums are open to a wide public, of different ages and backgrounds, often with little or no knowledge in the use of computers. Consequently, if Augmented Reality is to revolutionize the way we interact with computers, with the surrounding environment and with each other and exploit in full the benefits regarding the potential social impact, museums seem to offer an ideal workspace for experimentations on that field. The design and implementation of a successful prototype could then easily be tailored to be used under similar circumstances. As we will see in the next session, museums have also good reasons to encourage experimentations with Augmented Reality in their premises.

Mobile Multimedia Guides in the Museum Setting

Mobile guides, considered as one of the last descendants of digital, sophisticated audio guides, are becoming more and more popular throughout the world. Proctor provides a list of 101 projects from 1997 to 2005 (Proctor, 2005). Mobile guides present numerous advantages as they stand in the cross section between multimedia and Information Technologies used in the museum setting and interpretation and communication means (Damala, 2007). All kind of media can be incorporated in mobile museum guides' applications in meaningful ways to guide the visitor throughout the full visit. In addition, mobile guides are able to be personalized and taking advantage of geolocalisation capabilities, deliver the right information on the right spot. Live streaming, bookmarking and communication possibilities are also key features of mobile guides. In addition, museum professional can use the logs of visitors' actions to get meaningful information about the attracting and holding power of exposed objects as well as about the way the multimedia resources are used. Despite the fact that evaluation [START_REF] Damala | Evaluation strategies for mobile museum guides: a theoretical framework[END_REF] has proved these applications to be effective, some specific issues demand further attention:

1. The interaction surface is small and so selecting and manipulating objects might prove to be a difficult task especially for the elder or for visitors not acquainted with mobile technologies.

2. Geolocalisation is a very helpful feature but often proves to be not enough as it is not always easy for visitors to use floor plans of the exhibition space. In that case knowing the direction towards which the visitor is looking could be extremely helpful.

3. Creating links in between the real world and its digital counterpart is another challenge. Difficulties in associating a museum object with the available digital resources could perturb museum visitors that get easily frustrated when it comes to complex in use information and communication systems.

And though the above mentioned issues might constitute only a part of the challenges present in the domain of mobile multimedia guides used in the museum setting, they lie in the core of a successful integration of mobile guides in the museum setting and they are by no way trivial.

Figure 2: Augmenting the real world with digital overlays Because of a long tradition and history in the domain of virtual worlds and humans [START_REF] Bouville | Cultural Heritage Applications: An industrial perspective from France[END_REF] and having participated in the past in two mobile museum guides projects [START_REF] Brelot | Nomadic computing in indoor cultural settings: Intelligent connectivity, context awareness and the mobile museum experience[END_REF][START_REF] Damala | Mobile computing in the museum setting: Mobivisit, A field study in the Museum of Fine Arts[END_REF], our laboratory conceived the idea of a creation of a new mobile museum guide prototype, using Augmented Reality techniques. The fusion of the real with the virtual can transform in unexpected ways the available interaction surface and help create affinities between the commented objects and their digital counterparts. This task is very much helped by Augmented Reality as at every given moment, the system is aware not only of the geolocalisation of the visitor but also of his orientation. Mobile museum guides are dotted with a variety of functions in order to enable not only the visitor but also the museum staff and the curators to get the best out of their use in the museum setting. In the case of the Augmented Reality guide, it was obvious that apart a set of new functions, specifically made possible by the use of Augmented Reality techniques, other functions present in systems already implemented should be identified and included in the guide.

For this reason we created an inventory to which we added the Augmented Reality functions, that we thoroughly discussed with museum professionals so as to validate them. Some general remarks are that:

1. There are functions visible and invisible to the museum visitor. The actions activated by the visitor make part of the first category while functions such as logging visitors actions for use by museum curators and educators, or taking under account the number of terminals used in a specific space and the available bandwidth in order to optimize the visitor experience are present but not visible.

2. There exist a set of Augmented Reality functions.

Their main impact to already tried out non Augmented Reality functions is that they have the potential to change the way of interaction as the "scene" on which the action takes place can move from a tiny computer screen to the full environment surrounding as, through, for example the use of Augmented Reality goggles (Figure 3). The same is true for the input and output devices that can be used to interact with the system.

It was felt, however, that a consistent taxonomy that could be used to better classify the set of identified functions was missing. This led to a process of a more abstract functions' classification composed of four categories: Contextualization, communication, personalization and museum data management. It is not in the scope of this article to present the full set of functions we have identified but rather to give pertinent and adequate examples to establish the proposed taxonomy.

Contextualization

Contextualization is a term initially used in biblical studies but steadily adopted from the 70s onwards in cultural studies and archaeology. It is in this spirit that the term was chosen for our taxonomy, in order to express all functions that help a visitor situate a museum object in its original context. The visualization of images, slideshows, 3d models, animations and avatars used as virtual guides belong in this category as well as the audio function, the speech to text or text to speech function or the video function. Granting to more initiated visitors access to the museum data base and providing hyperlinks also belongs in this category as well as all functions allowing the manipulation of digital artifacts or 3d models.

Communication

Another distinct set of functions is related with the issue of communication. Communication functions can assist different kind of communication needs, between the museum and the visitors, the visitors with the museum, the visitors with other covisitors and eventually address the need of communicating parts or the full visit for later consultation, linking thus the pre, during and post visit experience for some visitors and strengthening the bonds of the museum with its public. The implementation of a function, that would allow visitors to spatially comment exhibits could enhance the public dialogue and engage more the public in the exhibition. Another example of function is the sending out of alerts regarding closing hours, or special events taking place in the museum.

Personalization

Personalization is another great advantage of the use of mobile guides in the museum setting and can be said to be a function of its own, composed by different sub functions. In this report we use the term personalization with its general meaning, including as well configuration, and without strictly drawing a line between customization or adaptability, thought to be triggered by the user itself, and personalization or adaptivity, which lets the system induce the visitors preferences [START_REF] Bowen | Personalization and the web from a museum perspective[END_REF][START_REF] Proctor | Access in hand: providing deaf and hard-ofhearing visitors with on-demand, independent access to museum information and interpretation through handheld computers[END_REF].

There are many criteria upon which personalization can occur, like age groups, learning styles (Damala, 2007), disabilities [START_REF] Proctor | Access in hand: providing deaf and hard-ofhearing visitors with on-demand, independent access to museum information and interpretation through handheld computers[END_REF], level of visitors initiation, available time for the visit [START_REF] Damala | Mobile computing in the museum setting: Mobivisit, A field study in the Museum of Fine Arts[END_REF], thematic tours, bookmarking, different visitors communities. In a more technical level personalization can also occur according to the terminal chosen and the available bandwidth.

Museum Data Management

Finally, there is a fourth category, completely invisible to the visitor that plays however a major role in the way the visitor will live the experience. A common point among all these functions is that they deal with data, either this is provided or comes from the surrounding environment or the use of the devoted visitor's terminal and is directed to the server, or data that comes as a response from the server to the dedicated terminal. It is for this reason that we chose to name this category "Museum data management", with the term management embracing the storage, transmission and processing of data. Registration of visitors terminals, that allows museum staff be aware of the number of visitors in each room as well as logs of visitors actions belongs in this category, as well as geolocalisation, orientation and live streaming. Modules for content creation, content management and content update can also fall under this category. The visitor enters the museum and heads for the kiosk where the guides are distributed. He registers together with his companions. This process will later enable him to communicate with co-visitors and know their exact position in the exhibition space. It is also required for storing the path visited so as to later provide the visitor with a unique and completely personal "souvenir". This very same information of visitor's path is also useful for the museum personnel. At this point the visitor is provided with information regarding the use of the terminal.

Different kind of terminals could be available like Tablet PCs, UMPCs (ultra mobile personal computers) and PDAs without excluding a future use of the visitors' self owned terminals, e.g. smartphones. Whatever the choice of the platform, it should include a camera which will capture in real time the scene the visitor is looking at so as to augment the viewed scene with meaningful information. The visitor's terminal is also equipped with single or double headphones and maybe a special pair of Augmented Reality see through glasses through which the visitor will observe the exhibits and the digital overlays instead of looking them through the screen display.

During the Visit

The visitor enters the exhibitions and points his device towards a painting or simply observes the exposed object through his glasses. The image is captured by the camera and processed by a special module of the application where the pose estimation is effectuated. Once this done, it is possible to correctly place the available information around the observed object in terms of images, menus, buttons or widgets that activated by the visitor will present him a wealth of multimedia information. The interaction device would depend on the terminal used and could be a stylus or the index. In the case of using special Augmented Reality glasses, it could be also very interesting to attempt to combine them with a "hand smart" solution, where the visitor's one palm is transformer in a virtual keyboard [START_REF] Antoniac | HandSmart Mediaphone, Advanced Interface for Mobile Services[END_REF]. During the visit, the visitor can communicate with his co-visitors or other visitors and leave spatial comments regarding exhibits that can be viewed by his co-visitors and/or other visitors. The museum can also communicate messages to the visitors during the guided visit. Personalization helps the adaptation of the content to the visitor's profile and specific interests.

After the Visit

In at least one mobile museum guide project personalized souvenirs were proposed to the visitor [START_REF] Sauer | Edutainment Environments. A Field Report on DinoHunter: Technologies, Methods and Evaluation Results[END_REF]. As all visitors actions are logged, useful data regarding the sessions can be retrieved and help in redesigning or better adapt to visitors' needs the guide. But there is also another possibility, already explored and published by the Cite des Sciences et d' Industrie in Paris [START_REF] Topalian | Cultural Visit Memory: The Visite+ System Personalization and Cultural Visit Tracking Site[END_REF]. As the visitor returns the terminal, he receives a postcard onto which there is a url printed. The visitor can access the content of the web pages once in front of a PC and visualize the objects he visited and the path he followed whilst in the museum premises. In that way the visit is extended beyond the museum and the visitor is given the chance to examine further specific objects or aspects of the exhibition.

Figure 5: Augmenting the painting with a detail

IMPLEMENTATION ASPECTS

As the scene that the visitor perceives is the real or the video scene of the surrounding environment augmented with digital objects, it is very important to cater for a proper alignment and registration of these last to the real world. Unfortunately and unlike virtual reality, in Augmented Reality even small errors are easily perceived by the human visual system. Another very important factor is the combined latency, else called transport delay, meaning the delay form the time the measurements are taken to the time the images appear in Augmented Reality display [START_REF] Azuma | Tracking Requirements for Augmented Reality[END_REF].

Both of these factors are crucial to the acceptance and success of the system but unfortunately no existing approach completely satisfies these requirements. A possible solution would be to combine marker tracking with sensor (inertial, ultrasonic, or radio ranging) and 3d model data. However for the time being the marker based approach is the most robust and reliable and that is the reason for which it was chosen for the first implementation. In any case, the challenge is to adopt the most appropriate solution in the more discrete and less obtrusive way for the museum visitor.

Opting for the marker based approach, the type of museum objects had to be defined. A decision was taken to proceed with three different types of museum objects. The first one is paintings. Apart from being one if the most usual museum objects, because of their two dimensional and rectangular forms they can be used as 2d markers, detectable by the Augmented Reality guide. The second type of objects resides behind museum transparent showcases. Though the cooperating museum agreed upon the inclusion of discreet markers in the showcases, in this case too it could be probable to use the objects geometry for registration and tracking. However that would require proper lighting conditions and a minimum of reflection on the transparent glass showcases. Finally a third case study will be provided by quadruped stands with a marker on each side, onto which the possibility of commenting pottery or statuettes will be explored. In this way the marker base experimentations will anticipate future improvements in estimation of camera position and orientation as well as in novel ways of interacting with Augmented Reality. This is why the goal of our implementation is not the creation of a fully fledged Augmented Reality prototype but rather the creation of numerous Augmented Reality demonstrators first, to assist museum professionals better comprehend the potential of the new approach and then adapt it to their specific needs and secondly to actively involve visitors in Augmented Reality assisted tasks. Evaluation will eventually prompt interesting issues regarding the use of mobile guides in the museum setting, the use of AR for interaction, entertainment and learning.

DISCUSSION OF THE AUGMENTED REALITY APPROACH

Current limitations of the Augmented Reality approach

Despite the innovative and promising character of Augmented Reality applications there are still lots of barriers to overcome in order to ensure consistency and efficacy of the Augmented Reality approach when it comes to mobile museum guides.

The lack of dedicated authoring tools renders the full chain of content creation, authoring, implementation and presentation a difficult task that can not be carried by museum professionals alone. The innovative character of the approach is often making bewildering the expression of the needs of museum curators, as they are not really aware of what to expect and consequently having a difficulty to express their needs. Technical constraints related with tracking and correct display as well as the lack of accurate, powerful and inexpensive equipment is another very important issue. Therefore, prototype applications are much more common than viable, ready to be commercialized applications. It is for the same reason that many Augmented Reality applications lack a "bottom-up" approach. Consequently, the process of development is often technology driven instead of user driven.

Conclusions

Because of the aforementioned limitations, trying to make abstraction of the technological constraints is of paramount importance for the development of Augmented Reality applications destined for the "museum sphere".

It is also important to remember that museums could provide an exciting environment for experimentations with Augmented Reality and one that could help the Augmented Reality community build in experience that could later be embedded in other Augmented Reality applications, especially because museums are extremely rich in content and socially inclusive as environments.

As technological progress will finally address the need for light and reliable equipment, robust Augmented Reality algorithms and dedicated, easy to use authoring tools, Augmented Reality might provide a valid, intuitive and playful approach towards the appreciation and comprehensions of tangible and intangible cultural heritage, opening up the way for other learning or entertainment Augmented Reality applications.

Figure 1 :

 1 Figure 1: Milgram's et al. Mixed Reality Continuum (courtesy of Professor Paul Milgram)

Figure 3 :

 3 Figure 3: An example of a wearable Augmented Reality display

Figure 4 :

 4 Figure 4: An example of an Augmented Reality mobile museum guide


N Baskiotis
email: nicolas.baskiotis@lri.fr

O Teytaud

M Sebag

Inductive-deductive systems: a mathematical logic and statistical learning perspective

This paper has not been published with copyrighted proceedings and was only presented, in french, in a national conference.

The theorems about incompleteness of arithmetic have often been cited as an argument against automatic theorem proving and expert systems. However, these theorems rely on a worst-case analysis, which might happen to be overly pessimistic with respect to real-world domain applications. For this reason, a new framework for a probabilistic analysis of logical complexity is presented in this paper. Specifically, the rate of non-decidable clauses and the convergence of a set of axioms toward the target one when the latter exists in the language are studied, by combining results from mathematical logic and from statistical learning. Two theoretical settings are considered, where learning relies respectively on Turing oracles guessing the provability of a statement from a set of statements, and computable approximations thereof. Interestingly, both settings lead to similar results regarding the convergence rate towards completeness.

INTRODUCTION

Inspired by the "Learning to Reason" framework [START_REF] Khardon | Learning to reason[END_REF], this paper investigates the conditions for a hybrid inductive-deductive system (IDS). This system is provided with a set of axioms or statements (e.g. examples), and its goal is to determine the truth value of any further statement e. We consider a framework for dealing with undecidable theories as well; this is a main difference with many previous works ( [Shapiro, 1981]). We will often refer to arithmetic or set theory, but many other essentially undecidable theories could be considered instead of this. From a mathematical logic perspective, the question is whether i) the available set of statements is complete, and ii) the logical setting is complete. Under these assumptions, the truth value of e is determined using mathematical deduction; the algorithmic challenge is to provide an efficient search engine for constructing a proof of e or ¬e. When the set of statements is not complete, by definition there exists statements e which can neither be proved nor refuted; the famous Gödel's theorem (1931) states that sufficiently powerful logical settings (e.g. including arithmetic) are incomplete. When the set of statements is not sufficient for deciding relevant statements, inductive reasoning is needed to find additional axioms, consistent with the available ones and sufficient for determining the truth value of e. The challenge here is to compare the different natural methods available for adding new axioms. From a hybrid inductive-deductive perspective, the logical setting considered must thus be examined with respect to both its completeness (deduction-oriented performances), and its VC-dimension or PAC learnability (induction-oriented performances, Appendix A.2). Typically, statements C(1), C(3), C(5), C(7), ¬C(4), ¬C(6), ¬C(2), C(217), ¬C(200) do not allow deduction of ∀n C(2n + 1) ∧ ¬C(2n). In the meanwhile, inductive logic programming might learn the hypothesis ∀n C(2n + 1) ∧ ¬C(2n), which could in turn allow for many other deductions. This paper examines the convergence properties of an inductivedeductive system, i.e. the probability that the n + 1-st example can be proved from the axioms learned from the previous n examples. The originality of the work is to propose a probabilistic analysis of logical decidability and completeness, contrasting with the worst-case analysis and undecidability results used in the literature. Indeed, a worst-case perspective does not account for the fact that many relevant statements can yet be proved in an undecidable setting. The rest of this section describes the proposed framework, discusses the relevant work and introduces the results reported in the paper.

Formalisation. This paper considers a first order logic language, where the initial set of axioms Z is an essentially undecidable ( [Kleijnen, 1992, p277], [Tarski, 1949])1 set of axioms with finite description length2 such as the Zermelo-Fraenkel set of axioms.

Let us consider a sequence of examples or statements e i , independently and identically distributed from a probability distribution M . We further assume that M is consistent with Z, in the sense that Z ∪ {e s.t.M (e) > 0} is consistent. From each set of examples E n = {e 1 , ..., e n }, the system extracts a recursive set of axioms noted A n , which together with Z allows for proving every example in E n . Three types of induction are distinguished:

• in deduction, A n includes all examples in E n , except those examples e i which could be proved from the theory learned from the previous examples (i.e. all e i except those such that A i-1 , Z ⊢ e i ). A n thus is an independent axiom set.

• in pruned-deduction, A n is a minimal subset of E n , sufficient to prove every example in

E n (A n , Z ⊢ E n ).
• in induction-deduction, A n is a set of axioms, minimal wrt its description length, such that every example in E n can be proved from A n and Z. Contrasting with deduction and pruned-deduction, A n is no longer necessarily included in E n .

The theoretical case where (deductive, pruned-deductive and inductive-deductive) learning is based on Turing oracles will first be considered in sections 3 and 4, respec-tively devoted to the cases where the target set of axioms is finite and infinite. Section 5 extends the analysis, considering Turing-computable-approximations of Turing oracles, based on finite-length proofs.

Goals of the study. The behavior of an inductive-deductive system is examined with respect to three stochastic variables, modeling respectively the completeness, the accuracy and the compactness of the current axiom set (noted A n in the following instead of A n , Z for simplicity of notation):

• the incompleteness of A n refers to the probability L n that A n does not allow for deciding on further examples (L n = M ({e s.t. A n ⊢ e ∧ A n ⊢ ¬e})); in order to distinguish this incompleteness from the standard logical one, it will be refered to as the relative incompleteness;

• the error or falsity of A n is the probability that A n decides wrongly on further examples3 ;

• the compactness is measured as the description size DL(A n ) of the current axiom set (this is not related to other definitions of compactness, but we keep this notion as no ambiguity arises).

It must be noted that the behavior of the relative incompleteness rate L n is known in some specific cases:

• In case Z is a complete set of axioms, no learning is required ; A n = Z leads to L n = 0 as for any e, Z ⊢ e or Z ⊢ ¬e.

• Otherwise, if M is modified at each time step n by a malign adversary with unrestricted computational power, then after Gödel's first theorem, L n = 1 for all n, as the adversary can choose M concentrated on some undecided e.

Thus, our framework lies between the (too simple, unrealistic) complete case, and the (too difficult, pessimistic) straightforward application of essential undecidability.

The goal is to examine the practical limitations of learning in a powerful language (e.g. including the axioms of set theory or arithmetic). The limitations of such languages regarding completeness and decidability issues are well known; these limitations have significant impact on inductive learning as well. For example, in languages including arithmetic there are always infinitely many theories proving a finite consistent set of statements; discussions around this fact are referred to as Quine's underdetermination thesis [START_REF] List | Craig's theorem and the empirical underdetermination thesis reassessed[END_REF][START_REF] Norton | Must evidence under-determine theory ?[END_REF], Shook, 2002]. However, it might be the case that the problems entailed by incompleteness and undecidability, though certain, are actually not frequent. And if there are an infinite number of solutions to a finite learning problem (Quine's underdetermination thesis), then it might be interesting to assess the average quality of these solutions. Therefore, our goal is to provide a statistical study of the relative incompleteness, compactness and falsity of learned theories, applying the statistical learning methodology and body of results to other learning criteria, namely the probability of facing an undecided example or introducing inconsistencies in the theory.

Related work. As far as we know, the simultaneous use of deduction and induction has not been studied yet in a statistical perspective though the three domains involved (automatic deduction, inductive and statistical learning, mathematical logic) have some intersections 4 . Along an inductive-deductive setting, the works related to Quine's underdetermination thesis [START_REF] List | Craig's theorem and the empirical underdetermination thesis reassessed[END_REF][START_REF] Norton | Must evidence under-determine theory ?[END_REF], Shook, 2002] focused on a worst case analysis; they do not integrate the statistical learning and generalization aspects. Other studies deal with some kinds of incomplete frameworks, e.g. involving recursion theory and referring to Turing machines with oracles or infinite-time Turing machines [Hamkins, 2002]. However, this work focuses on extending the set of decidable statements and the role of induction is not considered.

Overview of the paper. As an alternative to the worst-case analysis, the framework proposed in this paper is based on a logically consistent probability distribution M over the set of statements. In each step n, the system outputs a set of axioms A n from the first n statements, and one examines whether this set allows for proving further statements. As noted earlier on, if these further statements are selected in a worst-case manner, A n does not allow for deciding their truth value even with unbounded computational resources. However, a worst-case perspective often leads to overly pessimistic conclusions [START_REF] Cheeseman | Where the really hard problems are[END_REF]. The probabilistic setting proposed is inspired by the standard Probably Approximately Correct (PAC) framework [Valiant, 1984], and the study borrows the standard statistical learning tools (VC-dimension [START_REF] Vapnik | Theory of Pattern Recognition[END_REF]) in order to bound the relative incompleteness expectation

L n = M ({e s.t. A n ⊢ e ∧ A n ⊢ ¬e}).
The paper is organized as follows. Section 2 introduces general definitions and lemmas used in the rest of the paper. Section 3 presents results about the induction of a target theory with bounded description length, comparing the deductive, pruneddeductive and inductive-deductive learning settings. It is shown that (corollaries 1-4): i) in all cases, non-asymptotic performance depends on the underlying distribution M and it might be arbitrarily bad (as in the worst-case setting); ii) induction-deduction, and more generally restrictions on the description length entails faster convergence rates than deduction ; iii) for any algorithm with a faster completeness convergence rate than deduction, there exists a distribution such that the error or falsity is not almost surely zero (∃M, e s.t. ∀n, P (A n ⊢ ¬e) > 0 and M (e) > 0); iv) pruned learning can behave arbitrarily badly in the sense of an infinite asymptotic description length. Section 4 considers the case of a target theory with infinite description length, and presents negative results (corollaries 5-8): i) arbitrarily slow convergence rates can occur; ii) the length of the axiom set can increase fast. However, the completeness rate goes to 1 as the number of examples goes to infinity. While results presented in sections 3 and 4 are based on an oracle (axiomatic optimization or theorem proving with unbounded computational power), section 5 considers the case of Turing-computable approximations of such an oracle. Results similar to those of the oracle case are presented (with, unfortunately, a huge computational complexity). The paper ends with a discussion of the presented results; a short introduction to the terminology and state of the art is given in Appendix A.

For space limitations, some proofs are omitted in the paper, and can be found in [Baskiotis et al., 2007].

FORMAL BACKGROUND

Let Z denote a consistent essentially undecidable set of axioms (e.g. Zermelo-Fraenkel). We note DL(A) the description length of an axiom set A, and by abuse we use also DL(e) = DL({e}). Let T ′ denote the set of consistent theories including Z, and let T ⊂ T ′ be the set of consistent theories defined from an axiom set with finite description length (T = {t ∈ T ′ , ∃A s.t. A ⊢ t, DL(A) < ∞}). T and T ′ can be viewed as boolean mappings from the set of well-formed statements (t(e) = 1 iff t ⊢ e).

This section examines the VC-dimensions and shattering properties of both T and T ′ spaces.

Theorem 1 [Baskiotis et al., 2007]: T has infinite VC-dimension.

Although T and therefore T ′ both have infinite VC-dimensions, they differ by their shattering properties :

Theorem 2 [Baskiotis et al., 2007]: T ′ shatters an infinite set. The above theorem implies significant differences about learning in the search spaces T and T ′ . Specifically, in the case of T ′ there exists distributions leading to arbitrarily slow convergence rates, such as C/ log(log(log(n))) where n is the number of examples. In contrast, we shall see that a reasonable convergence rate is obtained within T , although the convergence can be delayed due to adverse distributions.

THE FINITE DESCRIPTION LENGTH CASE

Let M denote a probability distribution on the well-formed statements, such that the mass of M is restricted to a consistent theory t in T (∃t ∈ T s.t. M (t) = 1). A first negative result concerns the incompleteness convergence rate. We show that there exists a distribution M such that the incompleteness rate is bounded from below.

In the corollary below, as in corollary 5, we will use a link between supervised learning (i.e. learning statements with their truth values) and unsupervised learning (i.e. finding theories covering true statements). This link is based on the fact that stating e is exactly equivalent to stating ¬e. A distribution M on couples (x, y) = (e, true) or (x, y) = (e, f alse), where e is a statement, can be replaced by a distribution M such that M (e) is the probability of (e, true) plus the probability of (e, f alse), as well as we can identify sets of axioms with classifiers (the associated classifier separates theorems and non-theorems). This allows the use of counter-examples from learning in the framework of this paper. A family of classifiers (for supervised learning) such that for any learning algorithm EL n ≥ c for some distribution on these classifiers, is identified with a family of sets such that for any algorithm, for some distribution EL n ≥ c.

Corollary 1 : for any n > 0, for any δ > 0, for any method generating A n , there exists a generator of examples (distribution M ) such that E[L n ] ≥ 1 2exp(1) -δ. Remark : This result can be reformulated as: for any n > 0, for any δ > 0, there exists M such that after n examples the learned theory is at distance at least 1 2exp(1) -δ from the target one. Note that the above distribution M depends on n.

Proof of corollary 1 : Follows from theorem 1 and the lower bound cited in Appendix A.2.

Let us first consider the fine learning case, restricting the description length of the induced axiom set. By abuse of notation, in the following the description length of a theory derived from an axiom set A is set to DL(A).

Theorem 3 [Baskiotis et al., 2007]: Let T s denote the set of theories in T which can be generated from a set of axioms with description length less than s, and let V s denote the VC-dimension of T s . V s is finite as T s is finite. For each theory t, let V (t) be defined by

V (t) = inf {V s |t ∈ T s }.
Let V denote V (t * ) where t * is the target theory, assuming it is finite. Let t n denote the theory extracted along induction-deduction after n examples.

Then the following results hold :

1. Convergence rate : if n > V , P (L n > ǫ) ≤ 2(2 exp(1)n/V ) V 2 -nǫ/2
2. Asymptotic behavior : almost surely, there exists n 0 such that n ≥ n 0 ⇒ L n = 0 3. T does not shatter any infinite set.

4. V (t n ) ≤ V .

Let us now consider the deduction and pruned-deduction learning settings.

Theorem 4 [Baskiotis et al., 2007]: Consider the deduction or pruned-deduction settings. For any decreasing sequence a n bounded by 1/2 and converging to 0, there exists a probability distribution M such that i) ∀n, L n ≥ a n ; ii) there exists t ∈ T (i.e. DL(t) < ∞) such that M (t) = 1 .

Corollary 2 : In the deduction or pruned-deduction framework, for any decreasing sequence a n upper bounded by 1/2, there exists M such that for any n the relative incompleteness of A n is bounded from below by a sum of n independent binary random variables X i , where X i takes value 1/0 with probability (a i , 1 -a i ). In particular, under distribution M , the relative incompleteness of A n is greater than i≤n a i .

Corollary 3 : Theorem 4 and corollary 2 can be extended to any learning method producing a minimal (wrt set inclusion) theory such that it covers examples e 1 , . . . , e n .

Proof : This is a direct corollary of the proof of theorem 4. Corollary 4 : Any method which does not incur the limitations stated by theorem 4 or corollary 2, can with non-zero probability select a theory A n which is strictly larger (wrt set inclusion) than the minimal theory generated from {e 1 , ..e n }. In particular, for some distribution, there is a positive probability of generating a theory inconsistent with some statement of non-zero measure.

Proof : Reformulation of corollary 3.

THE INFINITE DESCRIPTION LENGTH CASE

Removing the finite length assumption has significant impact on the convergence results obtained in the previous section, notably in relation to the lower bounds on the convergence rate (see Appendix A.2). In the proof of the following corollary, we use the same correspondence as explained before corollary 1.

Corollary 5 : for any decreasing sequence (a n ) running to 0 and upper-bounded by 1/16, there exists a distribution of examples such that E(L n ) ≥ a n .

Proof : Direct consequence of the lower bound on the convergence rate in Appendix A.2.

Corollary 6 : for the deduction or pruned-deduction settings,

E[DL(A n )] ≥ i≤n a i .
Corollary 7 : In all learning cases such that the empirical error rate is null, L n goes to 0 (in the sense that for any ǫ > 0, P (L n > ǫ) → 0).

Corollary 8 : For all learning methods such that A n is consistent and proves all statements e 1 , . . . , e n , there exists a distribution M such that the compactness DL(A n ) goes to infinity.

Proof : Consider M a distribution which support is a consistent non-recursively axiomatizable set of statements. For any axiom set A let M (A) be the measure for M of all statements proved from A (M (A) = e s.t. A⊢e M (e)). Consider K(ǫ), the minimal description length over all axiom sets A such that M (A) greater than 1 -ǫ. K(ǫ) is non-decreasing, and

lim ǫ→0 K(ǫ) = ∞. It is sufficient to see that L n < ǫ implies that DL(A n ) > K(ǫ).
These results show that although the error rate goes to 0 as the number of examples increases, the convergence rate can be arbitrarily low. Moreover, the description length of the induced theory cannot be bounded, as showed above.

TURING-COMPUTABLE ALGORITHMS : PROOFS OF BOUNDED LENGTH

By definition, deduction, pruned-deduction and induction-deduction all rely on Turing machines with oracles. As a first step toward a practical analysis, this section considers instead approximate learning, based on Turing machines without oracles and bounded length reasoning5 . The approximation is considered from an algorithmic complexity perspective.

Section 5.1 is devoted to a complexity analysis of axiomatic optimization. This result is used in section 5.2 to provide a bound on the convergence of pruned-deductive and deductive-inductive learning toward the target theory, in the case where the latter is finite.

Algorithmic complexity

Let us consider as hypothesis space the sets of axioms with finite description length (possibly including axiom schemas; proofs using axiom schemas are allowed as well). Let us define the k-deduction as follows: statement e is k-proved from the set of axioms A, noted A ⊢ k e, if there exists a proof of e from A with description length less than k. The algorithmic complexity of k-deduction (i.e. the complexity required to decide the fact that a statement e is k-proved from A) is upper bounded by a function noted Complexity(DL(A), k, DL(e)). In the arithmetic setting considered, Complexity(DL(A), k, DL(e)) is dominated by a 2 k term (considering all 2 k strings of length k and determining whether they are proofs of A ⊢ e). Along the same lines, the k-consistency of a set of axioms is defined as follows: A is k-consistent, noted A ⊢ k ⊥ if there is no proof with length smaller than k that A is inconsistent. Similarly, the algorithmic complexity of k-consistency is upper bounded by Complexity(DL(A), k, DL(⊥)). Therefore, the generality and consistency tests (respectively, B ⊢ k A and B ⊢ k ⊥) can be performed with complexity e∈A Complexity(DL(B), k, DL(e)), over all statements or axiom schemas e in A.

The following proposition is then straightforward.

Proposition : Complexity of axiomatic optimization Assume that there are at most 2 n sets of axioms with description length less than n. Given a set A of statements, axiomatic optimization aims at a set of axioms B with minimal description length such that it entails all statements in A :

Find Arg min B {DL(B)|B ⊢ k A, B ⊢ k ⊥}. Its complexity is upper bounded by O 2 DL(A) × DL(A) × Complexity(DL(A), k, DL(A))

Axiomatic optimization

Given a set E n of statements, the point here is to find a minimal set A n of axioms, using a finite number δ n of computation steps to check A n consistency and completeness wrt E n . We show that if δ n increases sufficiently fast, there exists an algorithm with essentially same convergence results as in the oracle-based analysis (section 3). Practically, let δ 1 , . . . , δ n denote a sequence of integers. Then:

• Let T n+1 be the set of statements that can be proved with proofs of length at most δ n from A n ;

• A n is a6 minimal description length set of axioms such that: i) A n proves all examples in E n with proof of length at most δ n ; ii) A n does not prove ⊥ with proof of length at most δ n .

Note that A n is not necessarily a minimal set of axioms in the usual sense, e.g. one of the axioms could be proved from the others (but its presence makes it feasible to prove k-completeness). We note A * the shortest axiom set capable of proving any e in the target theory (i.e. such that M (e) > 0). Let L n here denote L n = M ({e; e ∈ T n+1 ∨ (¬e) ∈ T n+1 }).

Theorem 5 [Baskiotis et al., 2007]: Consider e a random variable on statements with probability law M and assume that the mean and the variance of the shortest proof of e from A * are finite, and assuming further that δ n = Ω(n 3 ), then ,

1. P (DL(A n ) ≥ DL(A * ) + ǫ) ≤ p n,ǫ with p n,ǫ is O(1/n 2 ), as soon as n = Ω(1/ √ ǫ).
2. A n reaches A * almost surely, and thus is consistent for n sufficiently large.

3. L n ≤ ǫ ′ with probability at least 1 -p n,ǫ -2 S 2 -nǫ ′ /2 for any ǫ, ǫ ′ > 0, where S is the number of axioms sets with description length bounded by DL(A * ) + ǫ.

This result shows that the theory extracted by induction-deduction (using Turing machines with no oracle and bounded-deduction) is consistent, for sufficiently large number of examples; that its description length converges toward the optimal one, and finally, that its relative incompleteness goes to 0 as O(1/ √ n).

In summary, Theorem 5 shows that a Turing-machine algorithm with no oracle can implement an inductive-deductive system, with essentially the same performances and limitations regarding consistency and completeness as in the theoretical case. Indeed the complexity of this algorithm is exponential in n.

DISCUSSION

A probabilistic relational setting has been proposed in this paper to study inductivedeductive systems (IDS). Precisely, from a random generator providing statements and their truth values, the IDS extracts a set of axioms via one among three settings: the deduction one corresponds to a purely deductive algorithm; the pruned-deduction one extracts a minimal excerpt of the statements, sufficient to prove all seen statements; and the inductive-deductive setting selects the set of axioms with minimal description length such that it proves all seen statements. Two cases are distinguished: the "finitely describable" (FDR) and "non-finitely describable" (NFDR) realities respectively correspond to the case where the target set of axioms has a finite (resp. infinite) description length. FDR and NFDR cases are confronted to deduction, pruned-deduction and induction-deduction settings, considering two criteria: relative incompleteness (proportion of statements which cannot be proved from the current theory) and compactness (description length of the current theory). Though relative incompleteness always goes to 0 as the number of examples goes to infinity, its convergence rate can be arbitrarily low in all cases, except when reality is finitely describable and in a inductive-deductive setting, in other words, when the system actually performs induction. In this favorable case, the target concept is reached almost surely in finite time. Along the same lines, the description length of the extracted theory is unbounded (for adverse distributions) in all cases, except again when reality is finitely describable and in a inductive-deductive setting. This result provides additional precisions related to Quine's under-determination thesis. Despite the multiplicity of theories consistent with a finite set of statements, if the IDS system extracts the theory consistent with the statements already seen, that is minimal wrt its description length (as opposed to, wrt its set inclusion), then a fast convergence in terms of both incompleteness and length can occur granted that the reality is "finitely describable". Interestingly, there exists some distributions in the latter case which entail errors and not only undecidabilities; i.e. there are cases such that the event ∃n; A n ⊢ ¬e has strictly positive probability. This result can be interpreted in the light of Popper's notion of falsifiability, central to the history of science; as shown by the very general corollary 4, if one abstains from producing hypotheses which can be falsified by examples, the convergence rate of the IDS is not better than that of rote learning. The last part of this paper has shown that the above theoretical results, obtained for Turing machines with oracles, essentially hold for Turing machines without oraclesalthough the considered algorithms are indeed of limited use due to their huge computational complexity. In summary, the main ambition of this paper is to contribute to a less pessimistic view of inductive-deductive systems in relational logic, than allowed by a worst-case analysis and based on undecidability results.

A STATE OF THE ART AND DEFINITIONS

This appendix briefly summarizes the notations and learnability results used in the paper. Notation sup X, where X is a real-valued random variable, denotes the (possibly infinite) supremum of the x such that P (X > x) > 0.

A.1 Logical notations

A theorem is a statement which can be proved, which depends on both the logical setting and the axiom set considered. The paper only considers classical logic. Each axiom set A includes Z and has finite description length. After Gödel's theorem, there exists thus e such that neither e nor ¬e can be proved from A. For the feasibility of the study, it is assumed that Z is consistent, although in many cases of interest, this has not been proved (and cannot be, e.g. for Zermelo Fraenkel, after Gödel's theorem). Notation A ⊢ e (respectively A ⊢ k e) denotes the fact that e be proved from A (resp. with proof of description length less than k). In the whole paper, the description length DL(•) (of sets of axioms or proofs) refers to a standard logic coding (with no compression).

A.2 Statistical learning theory

The interested reader is referred to [START_REF] Devroye | A probabilistic Theory of Pattern Recognition[END_REF], [Vidyasagar, 1997] for an exhaustive presentation. Let Z denote the example space, and let F denote the hypothesis space, where each hypothesis is viewed as a subset of Z. A set X of examples is said to be shattered by F if for any subset X ′ of X there exists f ∈ F such that f ∩ X = X ′ . The VC-dimension of F is the cardinal of the largest finite set that is

A set of axioms is essentially undecidable if any recursive extension of this set is undecidable.

In all the paper, the description length refers to any classical mathematical notation of statements or proofs. Note that a set of axioms with finite description length can include an infinite axiom schema.

Note that in the deduction or pruned-deduction cases, An cannot be inconsistent with e n+1 since An ⊆ En and distribution M is assumed to be consistent with Z.

Some advances in mathematical logic have been exploited for automatic theorem proving, for instance Craig's interpolation theorem is used to design a "partition-based" logic[START_REF] Amir | Partition-based logical reasoning for first-order and propositional theories[END_REF].

Since recursion theory provides negative results in the case of proofs with arbitrary length (ie, the set of statements that can be proved, in many cases, is not recursive but only recursively enumerable), we restricted this study to proofs with bounded length.

In case of equality, the first axiom set in lexicographic order is retained.

shattered by F . If arbitrarily large such sets exists, then the VC-dimension is said infinite. Hypothesis h is consistent with a set of examples X iff h∩X = h * ∩X, where h * denotes the target concept. A learning algorithm associates a consistent hypothesis h n to each training set X n made of n iid examples drawn according to some probability distribution M . Accordingly, the loss variable L n stands for the error expectation of h n (M {z, z ∈ Z, h n (z) = h * (z)}). Fundamental results in the statistical learning theory can be summarized as: if the VC-dimension is finite, then the error expectation goes to 0 reasonably fast as the number of examples goes to infinity.

Theorem, case of null empirical error (see [START_REF] Vapnik | Theory of Pattern Recognition[END_REF], [Devroye et al., 1997, Th. 12.7, p202]) :

Define L(P ) = 1 s s i=1 χ P (xi) =yi and L(P ) = Eχ P (X) =Y , with the (x i , y i ) a sample of size s iid according to the law of the random variable (X, Y ).

Consider F a family of boolean functions on a domain X and let V be its VCdimension. Then, for any ǫ > 0 if s > V , P ( sup

where (2 exp(1)s/V ) V can be replaced by the 2s-shattering coefficient of F. Lower bound : ([Devroye et al., 1997, p239], theorem 14.3). Assume that the VCdimension of F is infinite. Then for any n > 0, for any δ > 0, for any classification rule, there exists at least one distribution such that EL n ≥ 1 2 exp(1) -δ and F contains at least a function f such that L(f ) = 0.

Lower bound on the convergence rate : Assume that F shatters an infinite set. Then for any sequence (a n ) decreasing to 0 and upper bounded by 1 16 , for any classification rule, there exists at least one distribution such that ∀n EL n ≥ a n whereas F contains f such that L(f ) = 0.

Mainly, the difference with the previous result is that the distribution does not depend upon n.

Lemma : learning on countable domains Consider learning on a countable domain with a distribution and an algorithm ensuring that the empirical error L is zero. Then, the generalization error almost surely converges toward 0.


F Tavard

A Simon

C Leclercq

P Mabo

A Hernandez

M Garreau

Data Fusion of Left Ventricle Electro-Anatomic Mapping and Multislice Computerized Tomography for Cardiac Resynchronisation Therapy Optimization

Cardiac Resynchronization Therapy is a treatment for bi-ventricular asynchronism. It can be optimized by the identification of the most effective pacing sites. The aim of this study is to provide a helpful tool to perform this identification by the fusion of electrical and anatomical information resulting from Electro-Anatomic Mapping (EAM) data and Multislice Computerized Tomography (MSCT) imaging. EAM data provide an approximation of the left ventricle (LV) 3D-surface (S EAM ). Left cardiac chambers are segmented from MSCT imaging and surfaces are reconstructed (S CT ).

In order to represent this information in a unified framework, a three steps method is proposed: (1) the LV is separated from the left auricle on S CT providing S ′ CT ;

(2) a semi-automatic rigid registration method is applied to S EAM and S ′ CT ;

(3) activation time delays are estimated on S ′ CT from the EAM data. This method results in a graphical interface offering to clinicians means to identify abnormal electrical activity sites.

Introduction

Nowadays, Cardiac Resynchronization Therapy (CRT) is accepted as a therapeutic option in heart failure patients who remain highly symptomatic despite optimized medical treatment [START_REF] Chung | Results of the predictors of response to CRT (PROSPECT) trial[END_REF]. However, one third of the patients do not respond to the therapy. The IMOP project (IMaging for Optimisation of biventricular Pacing) aims for CRT optimization using anatomical, mechanical and electrical data which are acquired in pre, per and post-intervention. Two complementary ways lead to the CRT biventricular optimization: the identification of the most effective pacing sites and the search for a transvenous path to access the pacing sites. The pacing sites are myocardium regions with abnormal mechanical or electrical activity. Clinicians therefore need a representation of the myocardium com-bining electrical and anatomical informations. Our goal is to achieve it by combining Electro-Anatomic Mapping data and Multislice Computerized Tomography imaging.

The fusion of informations is one of the most challenging task in cardiac imaging to improve diagnosis and therapy. Indeed, informations provided by cardiac modalities are very different in terms of resolution (spatial and temporal) or nature (anatomical, mechanical or electrical). On one hand, the data obtained by EAM include: (i) a 3D surface reconstruction from points located inside the LV chamber, (ii) anatomical landmarks and (iii) points where the electrical activity has been measured. On the other hand, MSCT gives the opportunity to precisely represent the Left Ventricle (LV), the myocardium and also the coronary venous network (which is significant in the search of the transvenous path).

The proposed method for the fusion of EAM and MSCT data relies on three steps: (1) from MSCT data: cardiac left chambers segmentation and left ventricle separation from other geometrical structures; (2) spatial 3D surface registration in order to get the two modalities in the same spatial referential; (3) combined electrical and anatomical data representation to give an adapted tool to clinical routine.

3D-registration methods can be divided into two groups: methods based on geometric image features and methods based on voxel similarity measures [START_REF] Mäkelä | A review of cardiac image registration methods[END_REF]. EAM provides sparse data, therefore the first set of methods will be considered. The Iterative Closest Point (ICP) [START_REF] Besl | A method for registration of 3D shapes[END_REF] is the most popular algorithm for a rigid matching of two 3D surfaces. The ICP algorithm inspired other methods for rigid [START_REF] Du | An extension of the ICP algorithm considering scale factor[END_REF] or non-rigid [START_REF] Bâty | Model based and iconic multimodal registration to merge gated cardiac PET, CT and MR sequences[END_REF] 3D surfaces registration. In this work a rigid registration method is developed.

Several works have been proposed for the multimodal fusion of cardiac data including EAM [START_REF] Dong | Integrated electroanatomic mapping with three-dimensional computed tomography images for real-time guided ablations[END_REF][START_REF] Reddy | Integration of cardiac magnetic resonance imaging with three-dimensional electroanatomic mapping to guide left ventricular catheter manipulation feasibility in a porcine model of healed myocardial infarction[END_REF][START_REF] Mäkelä | A 3D model-based registration approach for the PET, MR and MCG cardiac data fusion[END_REF]. They all first apply a rigid Landmark Registration considering either external landmarks (fixed during the clinical routine) or landmarks manually fixed during data processing. The to extract the LV from the MSCT reconstructed surface were developed. It provides the clinician with 3D anatomical and electrical maps with the anatomical precision of MSCT imaging. For CRT optimization, the localization of the most delayed sites is possible, providing powerfull means for a better detection and localization of pacing sites.

Further works will aim to apply automatic registration method to other EAM data, to combine other modalities from the same patients (MRI for instance), to take into account mechanical considerations, and also to incorporate the venous coronary network.

Figure 4 .

 4 Figure 4. Results of the fusion of activation time delays on the CT-surface for two different patients. First patient: (a) Initial position before rotation. (b) S ′ EAM and S ′ CT after interactively choosing θ. EAM activation time delays mapped on S ′ CT after LV extraction: (c) for LV stimulation, (d) for sinusal stimulation. (e) and (f) same as (c) and (d) for the second patient. Activation time delays in color (ms).

Acknowledgements

This work, part of the IMOP research project n • 04 T 187-188-189-190 CITH, is supported by the French Research Ministry.