Jean-Baptiste Lamy

Rosy Tsopra

Alain Venot

Catherine Duclos

A semi-automatic semantic method for mapping SNOMED CT concepts to VCM icons

Keywords: Terminology as Topic, SNOMED CT, Computer Graphics, Nonverbal Communication. Materials and Methods . SNOMED CT includes many

VCM (Visualization of Concept in Medicine

) is an iconic language for representing key medical concepts by icons. However, the use of this language with reference terminologies, such as SNOMED CT, will require the mapping of its icons to the terms of these terminologies. Here, we present and evaluate a semi-automatic semantic method for the mapping of SNOMED CT concepts to VCM icons.

Both SNOMED CT and VCM are compositional in nature; SNOMED CT is expressed in description logic and VCM semantics are formalized in an OWL ontology. The proposed method involves the manual mapping of a limited number of underlying concepts from the VCM ontology, followed by automatic generation of the rest of the mapping.

We applied this method to the clinical findings of the SNOMED CT CORE subset, and 100 randomly-selected mappings were evaluated by three experts. The results obtained were promising, with 82 of the SNOMED CT concepts correctly linked to VCM icons according to the experts. Most of the errors were easy to fix.

Introduction

Standard medical reference terminologies, such as SNOMED CT, are highly useful for semantic interoperability between health information systems, making it possible to connect electronic health records to decision support systems, epidemiological monitoring systems, etc. However, these terminologies are complex and difficult for clinicians to use [START_REF] Chiang | Reliability of SNOMED-CT coding by three physicians using two terminology browsers[END_REF]. We have therefore developed VCM (Visualization of Concepts in Medicine), a compositional iconic language that represents the main concepts of medical terminologies through icons [START_REF] Lamy | Towards iconic language for patient records, drug monographs, guidelines and medical search engines[END_REF]. VCM is not designed to provide the same level of detail as a textual language. Instead, it provides the clinician with a broader overview, in the form of a graphical summary (e.g. from a list of patient problems), or helps the clinician to find the desired items (e.g. in a list of search results, after searching in a terminology browser). However, before it can be used with reference terminologies, VCM icons must be mapped to the terms of these terminologies.

H. Saitwal et al. [START_REF] Saitwal | Cross-terminology mapping challenges: a demonstration using medication terminological systems[END_REF] considered three methods for mapping medical terminologies: (1) linking together several existing mappings, e.g. combining the mappings from SNOMED CT to UMLS (Unified Medical Language System), and from UMLS to ICD10 (International Disease Classification release 10), to create a mapping from SNOMED CT to ICD10 [START_REF] Lamy | Towards iconic language for patient records, drug monographs, guidelines and medical search engines[END_REF] using lexical methods to search for identical or similar terms, and (3) manual mapping, possibly with the use of a specific tool, such as the one proposed by K. Giannangelo et al. to assist the experts for mapping SNOMED CT to ICD 10 [4]. H. Saitwal et al. [START_REF] Saitwal | Cross-terminology mapping challenges: a demonstration using medication terminological systems[END_REF] also discussed a fourth method, which they did not test, based on semantic ontology alignment or matching methods [START_REF] Shvaiko | Ontology matching: state of the art and future challenges[END_REF]; this approach can be used only when the two mapped terminologies are described in description logic (DL), and has therefore rarely been applied to medical terminologies. However, both SNOMED CT and VCM are described in DL, and lexical methods cannot be applied to VCM, due to the lack of textual terms. Y.R. Jean-Mary et al. [START_REF] Shironoshita | Ontology matching with semantic verification[END_REF] proposed an algorithm combining lexical and structural methods with semantic verification for mapping between two ontologies. S. Zhang et al. [START_REF] Zhang | Experience in aligning anatomical ontologies[END_REF] aligned several ontologies relating to anatomy. They generated a first set of mappings using lexical methods, and then used the already mapped concepts as "anchors" for mapping other concepts: two concepts from different ontologies having the same relationship with a given "anchor" concept are likely to be equivalent. A similar method was proposed by C. Bousquet et al. [START_REF] Bousquet | Method for mapping the French CCAM terminology to the UMLS metathesaurus[END_REF] for mapping the French CCAM (Classification Commune des Actes Médicaux, Common Classification of Medical Procedures) to UMLS. In CCAM, terms are defined by up to three descriptors of the anatomical sites involved, the action performed and the mode of access. These descriptors were mapped to UMLS by lexical methods, making it possible to use them as "anchors" for mapping the CCAM procedure terms, which are much more numerous than the descriptors.

The objective of the work presented here was to design a semi-automatic semantic method for mapping SNOMED CT concepts to VCM icons, and to evaluate this method through preliminary mapping for clinical findings. We briefly describe SNOMED CT and VCM, and propose a method for mapping SNOMED CT concepts to VCM icons. We then present the results obtained by applying this method to the SNOMED CT CORE subset, and the results of the review of 100 mappings by three experts. Finally, we discuss the advantages of the method. relationships between concepts, including "is a" relationships (e.g. hepatitis "is a" hepatic disorder), relationship between clinical findings and finding sites (e.g. the liver for hepatitis), associated morphologies (e.g. inflammation for hepatitis), and so on. These relationships can be organized into groups (e.g. to indicate that the inflammation is located in the liver), particularly for concepts with several finding sites or morphologies. We used the 2012 release of SNOMED CT provided by the National Library of Medicine.

SNOMED CT CORE Problem List (Clinical Observations

Recording and Encoding) is a subset of 6,286 SNOMED CT concepts. The CORE Problem List was selected to serve as an an appropriate subset for coding clinical information such as the list of patient problems (e.g. for discharge diagnosis or reason of encounter). In this study, we used the 2012 version of the CORE Problem List and focused on the 5,345 concepts of this list concerning disorders and clinical findings.

VCM [START_REF] Lamy | An iconic language for the graphical representation of medical concepts[END_REF] is an iconic language for representing the main clinical conditions of the patients. It includes representations of symptoms, diseases, physiological states (e.g. age class or pregnancy), risks and history of diseases, drug and non-drug treatments, laboratory tests and follow-up procedures. VCM includes a set of graphical primitives (colors, shapes, and pictograms), and a graphical grammar for combining these elements to create icons.

For the representation of clinical signs and disorders, the focus of this study, a VCM icon can be described in terms of its color, basic shape, set of shape modifiers and central pictogram. The color indicates the temporal aspect of the icon: red for current states of the patient, orange for a risk of future states, and brown for past states. The basic shape is a circle for physiological states or a square for pathological states (diseases or symptoms). The central pictogram indicates the anatomico-functional location (e.g. endocrine system) or the patient characteristic (e.g. pregnancy) involved; and special pictograms are available for a few specific disorders associated with a specific anatomicofunctional location (e.g. diabetes for endocrine system). Shapes modifiers can be added to specify (a) a general pathological processes (e.g. inflammation or tumor), and (b) a "transverse" anatomical structure that may be present at many anatomico-functional locations (e.g. blood vessels, which are present in most organs).

The VCM ontology was been designed to formalize the of VCM icons [START_REF] Lamy | Validating the semantics of a medical iconic language using ontological reasoning[END_REF]. It has three parts: (1) graphical concepts corresponding to VCM graphical primitives (i.e. the various shapes, colors and pictograms), (2) medical concepts (i.e. the main anatomical structures, biological functions, pathological processes, e.g. liver, hepatic function and inflammation, but not the various disorders, such as hepatitis), and (3) relationships between the graphical and medical concepts (e.g. the "liver" central pictogram is associated with both the liver (anatomic structure) and hepatic biological function).

Method for mapping SNOMED CT concepts to VCM icons

The proposed method for mapping SNOMED CT concepts to VCM icons is based on the compositional nature of both SNOMED CT and VCM. It has two parts: (1) the manual mapping of SNOMED CT concepts to the medical concepts of VCM ontology (n=370), and (2) automatic generation of a mapping of SNOMED CT clinical finding concepts (n=98,590) to VCM icons, using the concepts mapped at step 1 as "anchors" [START_REF] Zhang | Experience in aligning anatomical ontologies[END_REF], and making use of the relationships present in SNOMED CT and the VCM ontology.

We first generated a manual mapping of SNOMED CT concepts to the medical concepts in the VCM ontology. These medical concepts include the main anatomical structures, biological functions and pathological processes (e.g. liver, hepatic function and inflammation), but not the various disorders (such as hepatitis).

Due to multiple inheritance, some anatomical structures are classified in several branches of SNOMED CT. For example, ear ossicles are classified as both (a) a bone and (b) a part of the ear. The "bone" and "ear" concepts of SNOMED CT respectively map to the "bone" and "ear" concepts of the VCM ontology, which are themselves related to the "bone" and "ear" pictograms. As a VCM icon has only a single central pictogram, ear ossicle disorders would be represented by two icons: one with the "bone" pictogram and the other with the "ear" pictogram. This is problematic because VCM cannot represent the relationship between the two icons, and this may lead the clinician to think that there are two unrelated disorders. Furthermore, clinicians are more likely to associate ear ossicle disorders with the "ear" pictogram than the "bone" pictogram, because they learn about these disorders with auricular disorders in the ENT (Ear-Nose-Throat) specialty and not with bone disorders in rheumatology, as medical education is organized by medical specialty and each disorder is studied in only one specialty. We therefore considered no more than one pictogram per anatomical location and, thus, only disorders affecting several locations were represented by several icons (e.g. viral pharyngoconjunctivitis can be represented by an icon for the pharynx and an icon for the eye, because these two sites are different locations).

A preliminary mapping was produced, by considering all the medical concepts in the VCM ontology, and manually for the corresponding concepts in SNOMED CT, with a SNOMED CT browser. Each match was marked as either an exact match (i.e. the two concepts are equivalent) or a partial match (i.e. the SNOMED CT concept is narrower than the VCM concept, and thus not entirely represented by it). We then used a Python script to identify automatically all the anatomical structures in SNOMED CT associated with more than one VCM central pictogram through the ontology. For each of these anatomical structures, a new concept was added to the VCM ontology, and this concept was associated manually with a single VCM pictogram. The choice of pictogram was based on: (a) the medical specialty usually associated to the anatomical structure, (b) the position of the disorders of the anatomical structure, in monoaxial terminologies such as ICD10 (International Classification of Disease, release 10).

We then designed a method for associating one or more VCM icons to a SNOMED CT clinical finding concept. The method consisted in the following steps (see figure 1):

1. Creation of a list of SNOMED CT concepts, including the SNOMED CT concept for which we were generating icons, and each concept related to that concept by one of the following relationships: finding_site, associated_morphology, temporal_context, has_interpretation, interprets, has_definitional_manifestation, pathological_process, has_focus, causative_agent, associated_with, due_to.

2. Creation of a list of concepts from the medical part of the VCM ontology, by mapping each SNOMED CT concept in the list obtained in step 1 to the corresponding concepts (if any) in the manual mapping produced in the first part of the work. For each concept, if an exact match was found, we stopped there and moved on to the next concept. If a partial match or no match was found, we applied the same mapping process recursively to the concept's parents and "bigger-than" concepts (inverse part-of relationship, for anatomical structure: e.g. Entire heart for Cardiac valve structure).

3. Retention of only the most specific concepts from the list obtained in step 2.

4. Creation of a list of VCM primitives, by mapping each medical concept in the list obtained in step 3 to the corresponding VCM primitives, using the mapping present in the VCM ontology. primitives, and creation of a list of all possible subsets of these shape modifiers, (c) creation of the list of all possible icons, containing each possible combination of a central pictogram (from the list in step 5-a) and a set of shape modifiers (from the set in step 5-b), (d) removal of inconsistent icons, as determined by the VCM ontology, (e) removal of all icons for which there is a more specific icon in the list (e.g. if the list contains icons for "hepatic disorder" and "hepatitis", the "hepatic disorder" icon is removed because it is less specific that the "hepatitis" icon).

For SNOMED CT concepts described by several groups, each group was treated separately: we generated, in step 1, a list of SNOMED CT concepts for each group, including the relationships in the group and all relationships belonging to no group (group id 0). These lists were treated as described above, and the resulting icon sets were merged.

Methods for evaluating the mapping

For evaluation of the mapping of SNOMED CT concepts to VCM icons, we randomly selected 100 concepts from the clinical findings and disorders concepts in the SNOMED CT CORE Problem List. We generated VCM icons for each of these concepts, and three experts (AV, CD, RT) independently reviewed the icons associated with each concept. Experts were researchers in the field of medical informatics with a medical background (MD or PharmD). During this review, the relationships in SNOMED CT were considered to be the "gold standard", i.e. if a piece of information is missing or erroneous in SNOMED CT, it should be expected to be missing or erroneous in the icons. These relationships were extracted from SNOMED CT and made available to the experts.

For each concept, experts had to indicate: (a) whether the icons were acceptable, and (b) any additional comments.

Finally, disagreements between experts were resolved by seeking a consensus by collective discussion.

Results

CT CORE problem list mapping to VCM

All 5,345 concepts of the SNOMED CT CORE Problem List corresponding to disorders and clinical findings were associated with VCM icons. In total, 4,874 concepts (91.2%) were associated with a single icon, 435 concepts (8.1%) with 2 icons, 32 concepts (0.6%) with 3 icons, 3 concepts with 4 icons and 1 with 5 icons. There were 758 different VCM icons in the mapping, so each icon corresponded to a mean of 6.8 concepts. Table 1 shows examples of SNOMED CT concepts and the corresponding VCM icons.

Only 327 concepts (6.1%) from the CORE Problem List were associated with a VCM icon without a central pictogram and shape modifier (i.e. a very general icon indicating nothing more than "disorder"). These SNOMED CT concepts included mostly clinical findings (rather than disorders). Most were either (a) loosely defined clinical signs, e.g. "General symptom" (267022002), or (b) related to drug prescriptions, medical procedures or laboratory tests, e.g. "Already on aspirin" (405748007), "Transplant follow-up" (183655000), and "Lithium monitoring" (275917000). Although these concepts are classified as clinical findings in SNOMED CT, they fall beyond the scope of this study, which focused on clinical signs and disorders.

The manual mapping between the medical concepts of the VCM ontology and SNOMED CT involved 334 concepts from the ontology and 1,752 SNOMED CT concepts, a ratio of 5.2. During the design of the mapping process, 181 SNOMED CT anatomical structures were initially associated with more than one VCM central pictogram. For these concepts, 97 new concepts were added to the VCM ontology, and these concepts were then manually associated with a single central pictogram.

Evaluation results

The icons associated with 100 randomly selected SNOMED CT concepts were considered, by the three experts, to be acceptable for 82 icons, and the experts considered three of the concepts to be beyond the scope of the study (i.e procedures, laboratory tests or treatments, rather than clinical findings).

The erroneous icons generated for the 15 remaining concepts were analyzed and classified. Most related to missing associations in the manual mapping between the VCM ontology and SNOMED CT (8 errors, e.g. disorder of stature was not associated with the size concept in VCM ontology; it icons therefore did not include the size pictogram) or erroneous associations (2 errors, e.g. complication of procedure were wrongly associated with iatrogenic disorders). Two errors were related to the choice of medical specialty associated with a given anatomical structure (e.g. maxillary bone disorders are associated with the ENT specialty, and should therefore not be associated with the bone pictogram). Three errors were related to an absence of information in SNOMED CT for the pathological or abnormal status (e.g. for the Lung field abnormal (274710003) concept, no relationship in SNOMED CT made it possible to deduce that the concept was abnormal), and for hypo/hyperfunctioning.

Discussion and conclusion

We present here a semi-automatic method for mapping SNOMED CT concepts to VCM icons. This method involved manual mapping for a limited number of concepts (370 concepts from the VCM ontology) followed by automatic mapping to any SNOMED CT concept. The method was successfully applied to, and evaluated on, the clinical finding concepts from the SNOMED CT CORE subset.

The compositional structures of VCM and SNOMED CT are very similar, even though VCM was not based on SNOMED CT. Both describe disorders in terms of sites, morphologies and etiologies. Two main differences were encountered during manual mapping between the concepts of the VCM ontology and SNOMED CT: (1) VCM distinguishes pathological / abnormal patient conditions, versus physiological conditions, whereas, in SNOMED CT, the distinction is between disorders and clinical findings, and there is no concept for abnormal non disorder clinical findings; and (2) SNOMED CT has no concepts for describing disorders of biological functions, e.g. there is no "hyperfunction" concept associated with the "hyperthyroidism" concept (see table 1). These differences resulted in extra work during manual mapping and searching in the SNOMED CT browser: we searched for "abnormal" and various synonyms, and when we mapped a biological function, we searched for the function itself and for the associated hypo-and hyperfunction, e.g. for "thyroid function" we also searched for "hypothyroidism" and "hyperthyroidism".

A few more specific differences were encountered between VCM and SNOMED CT: (a) VCM represents pain as a symptom, with a specific shape modifier, whereas, in SNOMED CT, pain is considered as a sensory nervous system finding, (b) VCM considers the autoimmune aspect of a disorder as an etiology, whereas SNOMED CT considers autoimmune disorders as immune system disorders, (c) chromosomal abnormalities are considered as genetic diseases in VCM, whereas SNOMED CT classifies them as congenital malformations, (d) VCM considers muscles and bones to be separate structures, whereas SNOMED CT considers some skeletal muscles to be part of the skeletal system, e.g. the structure of the psoas major muscle (id We chose to restrict the mapping to one icon per anatomical location affected by the clinical finding, to limit the number of icons used and to stick to the medical specialties usually associated with particular conditions. This choice is debatable, but the importance of medical specialty for data presentation to clinicians has been highlighted elsewhere, by P. Massari et al. [START_REF] Massari | Use of super-concepts to customize electronic medical records data display[END_REF]. Relationships between a disorder and anatomical structures outside of the disorder's medical specialty (e.g. the relationship between ear ossicle disorders and bones) are ontologically true and useful for reasoning in a reference terminology, such as SNOMED CT, but they are not necessarily appropriate for presentation to clinicians in an interface terminology [START_REF] Rosenbloom | Interface terminologies: facilitating direct entry of clinical data into electronic health record systems[END_REF] or an iconic language, such as VCM.

The semi-automatic method we propose for mapping SNOMED CT concepts to VCM icons has several advantages over manual methods. Previous attempts to map VCM icons and medical terminologies manually have been based on MeSH, ICD10 and ATC. However, in manual validations of these mappings, the level of inter-expert agreement was low.

Most of the problems encountered by the experts were not directly related to VCM, instead relating to the definition of disorders "what are the anatomical structures affected by this disorder?"). In our semi-automatic method, many of these problems were solved automatically, by considering the relationships in SNOMED In addition, when a new version of VCM or SNOMED CT is available, it should be easier to update the mapping if this can be done semiautomatically.

Our method is similar to the "anchor"-based semantic mapping methods proposed by S. Zhang et al. [START_REF] Zhang | Experience in aligning anatomical ontologies[END_REF]. Semantic methods were possible given the ontological nature of both SNOMED CT and VCM. These semantic methods should be more accurate than lexical methods, because DL descriptions of concepts are more expressive than textual labels [START_REF] Cornet | Usability of expressive description logics-a case study in UMLS[END_REF], e.g. in textual label, "and" sometimes means a logical AND but frequently means a logical OR, such as in the term "structural and functional abnormalities of the kidney".

The evaluation of 100 random mappings yielded promising results. Most of the errors encountered were related to elements missing from the manual mapping. These errors were not serious as they generated icons that were too generic, but nevertheless appropriate (e.g. the icon for cardiac disorders instead of the icon for heart rhythm disorders), and were easy to fix by complementing the manual mapping. The evaluation we presented was limited to clinical findings, however it would also be interesting to evaluate the coverage of the various SNOMED CT axes (such as anatomy or morphology) by the corresponding pictograms in VCM.

In conclusion, we present here a semi-automatic method for mapping the concepts of SNOMED CT, a reference terminology, to the VCM icons. Future perspectives of this work include: (a) the mapping of the laboratory tests, procedures or drug treatment concepts of SNOMED CT to VCM icons by the same method, (b) an analysis of the expressiveness of VCM with respect to SNOMED CT and, possibly, the extension of VCM to improve coverage, (c) mapping of terminologies to VCM, e.g. VANDF-RT (Veteran Administration's National Drug File Reference Terminology) for drugs, either by a similar method or by combining the SNOMED CT to VCM mapping with the existent mappings in UMLS, and (d) the use of VCM icons to display elements of electronic patient records coded in SNOMED CT.

Figure 1 :

 1 Figure1: Example of the method used to associate VCM icons with a SNOMED CT clinical finding concept, applied to the concept of "uveitis". The five steps correspond to those described in the text.

5 .

 5 Assembly of the VCM primitives obtained in step 4 into one or more VCM icons, as follows: (a) extraction of the list of central pictograms from the list of VCM primitives, (b) extraction of shape modifiers from the list of VCM

Table 1 -

 1 Examples of SNOMED CT concepts and their associated VCM icons glioma (disorder) associated morphology: Glioma finding site: Brain structure is a: Disease Tumor in the central nervous system 186675001 Viral pharyngoconjunctivitis (disorder) causative agent: Virus finding site: Conjunctival structure finding site: Pharyngeal structure is a: Disease Ocular viral infection ENT viral infection 57240007) is (recursively) a part of the skeleton system structure (id 113192009); this might be a problem in SNOMED CT.

Acknowledgments

This work was partly supported by the French National Research Agency (ANR) through the TecSan program (project L3IM n°ANR-08-TECS-007).


René Donner
email: rene.donner@meduniwien.ac.at

Bjoern H Menze

Horst Bischof

Georg Langs

Fast Anatomical Structure Localization Using Top-down Image Patch Regression

Keywords: Anatomical structure localization, nearest neighbor regression, image patch codebooks

Fully automatic localization of anatomical structures in 2D and 3D radiological data sets is important in both computer aided diagnosis, and the rapid automatic processing of large amounts of data. We present a simple, accurate and fast approach with low computational complexity to find anatomical landmarks, based on a multi-scale regression codebook of informative image patches and encoded landmark contexts. From a set of annotated training volumes the method captures the appearance of landmarks over several scales together with relative positions of neighboring landmarks and a spatial distribution model. During multi-scale search in a target volume, starting from the coarsest level, each landmark model predicts all landmark positions it has encoded, with the median of all predictions yielding the final prediction for each scale. We present results on two challenging data sets (hand radiographs and hand CTs), where our method achieves comparable accuracy to the state of the art with substantially improved run-time.

Introduction

The accurate localization of anatomical landmarks in medical imaging data is a challenging problem, due to rich variability and frequent ambiguity of their appearance. Among the reasons for the difficulties are noise (including local and global intensity changes), cluttered image data (overlapping structures in 2D projections, highly structured background in 3D organ segmentation), and anatomical structures that exhibit a high degree of similarity (e.g., fingers or vertebrae). We propose an algorithm that copes with these challenges and offers a general approach to accurately localize landmarks without initialization or subsequent refinement. The method constructs a multi-level regression codebook which associates image patches with the corresponding positions of anatomical landmarks depicted in the patch. During search the scale-pyramid is traversed, finding the most similar patch for each landmark using k-nearest neighbor search. The localization of anatomical structures is crucial for several areas of medical imaging analysis: Segmentation approaches such as Level-Sets [START_REF] Cremers | A Review of Statistical Approaches to Level Set Segmentation: Integrating Color, Texture, Motion and Shape[END_REF] and Appearance Models [START_REF] Cootes | Active Appearance Models[END_REF], typically require at least a coarse initial localization, while registration approaches can exploit spatial initialization to avoid local minima. The automatic localization of anatomical structures is fundamental for the field of Computer Aided Diagnosis [START_REF] Doi | Computer-aided diagnosis in medical imaging: Historical review, current status and future potential[END_REF] and for structuring image information in image retrieval, since it allows the algorithms to focus on target regions in the data and subsequently invoke more specialized analysis stages. Landmark localization can also be regarded as a form of semantic parsing [START_REF] Seifert | Hierarchical Parsing and Semantic Navigation of Full Body CT Data[END_REF] when point-wise rather than regional information is required.

State of the art

Several approaches to anatomical structure localization exist in recent literature. They mainly differ in the type of semantic representation that is obtained to describe the image data. We thus distinguish between approaches that either 1) indicate the positions of individual landmarks, 2) provide bounding boxes for entire organs, 3) result in model parameters which describe the position and shape of the object or 4) provide voxel-wise labels for different organs.

Localizing anatomical landmarks using the positions of selected interest points has been the objective of [START_REF] Donner | Localization of 3D Anatomical Structures Using Random Forests and Discrete Optimization[END_REF][START_REF] Bergtholdt | A Study of Parts-Based Object Class Detection Using Complete Graphs[END_REF]. The methods learn interest point detectors on training data, estimate positions of landmark candidates in the target volume and finally disambiguate these candidates through a model matching step. Both methods rely on the classification of the entire volume. [?] reduces this computational burden by performing a low-resolution step and a refinement step using Hough regressors. Reducing the complexity by working on axial slices, [START_REF] Seifert | Hierarchical Parsing and Semantic Navigation of Full Body CT Data[END_REF] parse whole body CT data in a hierarchical fashion, but are concerned with finding larger organs. While substantially speeding up the localization this only works for objects which are rather large in respect to the overall volume size, since the objects have to be visible in at least one of the three central orthogonal slices. Using Random Forests for the localization of organs in thorax CTs through bounding boxes has been been proposed in [START_REF] Criminisi | Regression forests for efficient anatomy detection and localization in ct studies[END_REF]. An extension using Hough ferns was presented in [START_REF] Pauly | Fast Multiple Organ Detection and Localization in Whole-Body MR Dixon Sequences[END_REF] to predict the bounding boxes of multiple organs at once in full-body MR data. Relying on stochastic optimization instead of ensemble classification or regression, Marginal Space Learning [START_REF] Zheng | Marginal Space Learning for Efficient Detection of 2D/3D Anatomical Structures in Medical Images[END_REF] tries to find the parameters of a bounding box or a parametric and data-driven shape model [START_REF] Cootes | Active Shape Models -Their Training and Application[END_REF] to localize and segment anatomical structures. This allows for fast localization, but instead of representing a global search algorithm, iterative approaches have to be used to cope with repetitive structures [START_REF] Kelm | Detection of 3D Spinal Geometry Using Iterated Marginal Space Learning[END_REF]. The task of assigning voxel-wise labels to segment entire organs or organ structures has been approached by [START_REF] Criminisi | Decision Forests with Long-Range Spatial Context for Organ Localization in CT Volumes[END_REF] and [START_REF] Montillo | Entangled Decision Forests and Their Application for Semantic Segmentation of CT Images[END_REF] using Random Forest classification.

Contribution We present a simple, fast method for the global, accurate localization of anatomical structures in 2D/3D data based on an appearance codebook, and location predictors that capture sub-configurations of a landmark set. It demonstrates that a top-down nearest neighbor matching strategy of image patches drastically reduces the number of required feature computations and yields localization results comparable to the state of the art.

Paper structure The paper is structured as follows: Sec. 2.1 details the construction of the codebook, with the localization on a target volume described in Sec. 2.2. Sec. 3 introduces the experiments, with the results presented in Sec. 3.3. A discussion and an outlook can be found in Sec. 3.4 and Sec. 4.

Methods

The approach is divided into a training phase and a localization phase as shown in Fig. 2 and Fig. 3. During localization a multi-scale codebook of image patches and landmark positions is constructed, which is traversed during the localization phase to obtain increasingly accurate landmark estimates at each scale.

I 1

Training for Landmark

I i s=1 … … … … … … … s=2 s=3 s=4 s=5 s=6 s=7
Fig. 2. Construction of the regression codebooks during training. For each landmark and scale patches at various offsets and the corresponding relative landmark positions are recorded, using all training images/volumes.

Training -Constructing the landmark regression codebook

The training phase requires a set of N training images or volumes I i with corresponding annotations. The annotations represent the coordinates x i x of the x ∈ {1, . . . , L} landmarks of the anatomical structure in question. Each landmark is present in each of the training volumes.

Codebook construction to connect local appearance and landmark information

Our aim is to build multi-scale regression codebooks C of image patches and corresponding relative landmark positions -one codebook per scale s ∈ 1, . . . , S and landmark x. The patches stored in the codebook are extracted around the landmarks with varying offsets and scaling, capturing the typical visual appearance around each landmark. For each patch the positions of all landmarks visible in the patch are recorded, relative to the patch's center. Each of the P N entries in the codebook C s,x consists of the tuple P p , L p of the patch P p and the corresponding relative D × L landmark coordinates L p which are visible in the patch. L p specifies the coordinates of the landmarks x ∈ 1 . . . L relative to the center of the given patch1 . Landmarks which are outside of the patch are denoted as not visible.

The construction of the codebook proceeds as follows: At the top-most scale s = 1 each image or volume is represented by an an-isotropically downscaled miniature of size m × m × m (similarly m × m for images). At each scale s the volume is considered to possess an edge length of √ 2(s -1)m. This re-sampling of the entire image is never actually computed, it simply forms the reference frame for each scale of the codebook generation. At each scale s, patches P are extracted from the image or volume data using linear interpolation for each landmark x from all training volumes N . The patches are of size m × m × m, i. e. at scale s = 1 they correspond to the entire image, and for scales s > 1 the patches zoom in on the landmark, as illustrated in Fig. 2. Parts of patches which would be sampled from outside of the volume are set equal to the closest voxel on the volume's border. The gray values of each patch is normalized to zero mean and unit variance.

To explore the image information in the vicinity of a landmark the entries in the codebook C s,x at a certain scale s and landmark x, are constructed by extracting several patches around the landmark with, empirically chosen, 7 offsets in the range of [-6, 6] voxels for each dimension, along with scaling factors of {0.9, 1, 1.1}, resulting in P = 1029 patches for one landmark in one training volume at one scale (P = 147 for images). To considerably reduce the memory requirements and computational complexity for the codebook lookup, dimensionality reduction of each codebook is performed using PCA, retaining 90% of variance, resulting in PCA coefficients P P CA and final codebook tuples P p P CA , L p . This training scheme results in the S × L regression codebooks C s,x .

Shape model to regularize the localization

To be able to regularize the intermediate solutions during the prediction phase, a model of the spatial distribution of the landmarks s = x i 1 , . . . , x i L in the training data is learned. We compute a point distribution model S = s, S using an eigen-decomposition of the covariance matrix of the training landmarks x x as proposed in [START_REF] Cootes | Active Shape Models -Their Training and Application[END_REF], retaining all eigenvectors and thus the entire shape variance observable in the training set, where the shapes s in the model can be constructed through a parameter vector b such that: s = s + Sb

Localization -Regularized top-down matching

Similar to the training phase the localization is performed in a multi-scale fashion, shown in Fig. 3. The D × L landmark localization matrix L * s=1 is initialized with all landmarks starting at the center of the test volume I target . Starting with scale s = 1, a patch P x for each landmark x is extracted (without additional offsets or scaling variations). The patch is normalized and projected onto the patch PCA model of C s,x , resulting in P x P CA . The most similar patch p x * in the codebook is found using euclidean nearest neighbor search -leading to the tuple P x * P CA , L x * p and thus the landmark coordinate predictions L x * p as estimated by landmark x. Repeating this codebook lookup for all landmarks yields the D × L × L prediction tensor M d,i,j with position estimates from each landmark i to all landmarks that are visible in the same patch. The median over all predictions j which are not marked as not-visible yields the updated landmark localization matrix L * s . This procedure is repeated through all scales, resulting in the final localization result L * S .

Localization on Test Image

Shape regularization

The position estimates L * s are regularized by projecting them onto the shape PCA model S and reconstructing them again thereafter. This enforces landmark positions which can be modeled by a linear combination of the shapes observed in the training data. This regularization is performed for scales s ≤ S -3, to allow for landmark positions which can not be modeled though the shape model at scales s > S -3.

Experiments

Data sets

We evaluated the proposed approach on the two separate data sets shown in Fig. 1: 20 hand radiographs and 12 high resolution hand CTs.

Data set 1: Hand Radiographs N = 20 hand radiographs with an average size of 460 × 260 pixels with a resolution of 0.423mm/pixel were annotated with L = 24 landmarks. The landmarks include the five finger tips, as well as the distal interphalangeal (DIP), proximal interphalangeal (PIP), metacarpophalangeal (MCP) and carpometacarpal (CMC) joints for each finger.

Data set 2: Hand CTs The 3D hand CTs have a voxel size of 0.5mm × 0.5mm × 0.66mm resulting in an average size of 256×384×330 voxels. They are annotated with the same 24 landmarks as the hand radiographs, with three additional landmarks placed around the carpus at the radiocarpal, radioulnar, and ulnocarpal joints, totaling in L = 27.

Setup

The experiments were run using four-fold cross validation, learning the landmark regression codebook on 75% of the N images / volumes and performing the localization on the remaining images / volumes. The main measure of interest for each landmark is the residual distance between the position of the predicted landmark position and the corresponding ground truth. The parameter settings are identical for the experiments on the two data sets, except for the size of the patches: 32 × 32 in the 2D case and 32 × 32 × 32 for the 3D data. The results are compared with the recently proposed pre-filtered Hough regression Random forests [?], which in turn showed to outperform alternative approaches such as classification-based landmark candidate estimation with graph-based optimization [START_REF] Bergtholdt | A Study of Parts-Based Object Class Detection Using Complete Graphs[END_REF] and classification + mean-shift based approaches [START_REF] Shotton | Real-Time Human Pose Recognition in Parts from a Single Depth Image[END_REF].

Results

The results of the evaluation of the landmark localization are presented in Tab. 1, which shows the aggregated localization performance for the two data sets. The accuracy on the 2D radiograph data set is very high with a median residual of 0.63 mm and a mean/std of 0.77/0.64 mm. This result compares favorably with the results reported and methods tested on the same data in [?]. The result on the 3D hand CT data set show a median residual of 1.43 mm and a mean/std of 1.96/1.80 mm. It can be seen that despite a similar median residual, the proportion of localizations with higher error is slighty larger in this case. The run-times of the proposed approach were in the order of 0.6sec for the 2D data set and 4.5sec for the 3D data set on a single core of a 2009 Xeon MacPro. The method was entirely implemented in Matlab -we expect a potential speed-up by a factor of 10 to 100 through a more optimized implementation.

Discussion -Feature computation complexity

The main contribution of this work is the demonstration of a feature computation scheme which requires significantly less memory accesses then existing methods. scale with the number of voxels, while pre-filtered Hough regression [?] works on strongly downsampled volumes. In constrast to this, the proposed approach is indepedent of the number of voxels and scales with the number of landmarks.

Voxel-wise classification / prediction approaches such as those proposed in [START_REF] Bergtholdt | A Study of Parts-Based Object Class Detection Using Complete Graphs[END_REF][START_REF] Montillo | Entangled Decision Forests and Their Application for Semantic Segmentation of CT Images[END_REF] scale with the number of voxels, while pre-filtered Hough regression [?] reduces computational complexity by working on strongly down-sampled volumes. A typical number of 400 memory accesses to compute the classification for a single voxel was assumed in the calculation, corresponding to e. g. 20 individual features in an ensemble of 20 individual classifiers.

In contrast to this, the proposed approach is independent of the number of voxels and only depends on the number of landmarks, with m × m × m voxels sampled for the patch at each landmark and scale. The proposed approach thus requires one to four orders of magnitude less image/volume accesses, allowing for fast localization even in unoptimized implementations or cheap commodity hardware.

Conclusion and Outlook

We present an approach for localizing complex, partly repetitive anatomical structures in 2D and 3D data. We demonstrate that a top-down nearest neighbor matching strategy of image patches drastically reduces the number of required feature computations and that the prediction of relative landmark positions using codebook regression is feasible.

The results on the two data sets clearly demonstrate the ability of the proposed approach to find the landmark positions in the target volume with accuracy comparable to the state of the art, with the consistent localization of detailed anatomical structures with a median residual of 1.7 to 2.7 pixels/voxels.

We consider the results to be very promising for such a simple method, and will focus on several topics in upcoming work: A detailed analysis of the parameters involved, namely the patch size and the perturbation strategy during codebook generation, as well as approximations of the nearest neighbor search through random subspaces.

Fig. 1 .

 1 Fig. 1. Examples from the two data sets employed in this paper. a) Hand radiographs and b) high resolution hand CTs. The objective of the proposed method is to localize the depicted anatomical landmarks in an unseen target image or volume.

Fig. 3 .

 3 Fig. 3. The localization of three landmarks on a test image/volume descends the scale pyramid. At each level regression based on the image patch generates not only a position estimate for the primary landmak, but also for other landmarks visible in the patch. When progressing to a finer scale, for each landmark these estimates vote for the next estimate and center of the finer patch.

Fig. 4 .

 4 Fig.[START_REF] Cremers | A Review of Statistical Approaches to Level Set Segmentation: Integrating Color, Texture, Motion and Shape[END_REF]. Number of image/volume accesses necessary to compute the features required during the localization phase. Voxel-wise classification / prediction approaches[START_REF] Bergtholdt | A Study of Parts-Based Object Class Detection Using Complete Graphs[END_REF][START_REF] Montillo | Entangled Decision Forests and Their Application for Semantic Segmentation of CT Images[END_REF] scale with the number of voxels, while pre-filtered Hough regression [?] works on strongly downsampled volumes. In constrast to this, the proposed approach is indepedent of the number of voxels and scales with the number of landmarks.

Table 1 .

 1 Experimental results, localization accuracy in mm: Residual distances of the localization result to the ground truth annotation for the proposed method, in comparison with a state of the art approach.

	Residual in mm	MRF-based graph-matching	Proposed Patch-Regression Method
		Median Mean	Std	Median	Mean	Std
	Hand Radiographs	0.80	0.99	0.82	0.63	0.77	0.64
	Hand CTs	1.19	1.45	1.13	1.43	1.96	1.80

The necessary transformations between image coordinates and patch coordinates are omitted for clarity throughout the text.

⋆ This work was partly supported by the European Union FP7 Project KHRESMOI (FP7-257528), by the Austrian National Bank grants BIOBONE (13468) and AOR-TAMOTION (13497) and the Austrian Sciences Fund grant PULMARCH (P 22578-B19).


Benjamin Camus
email: benjamin.camus@loria.fr

Christine Bourjot
email: christine.bourjot@loria.fr

Vincent Chevrier
email: vincent.chevrier@loria.fr

Multi-level Modeling as a Society of Interacting Models

Keywords: multi-level, multi-model, multi-agent, collective motion

We propose to consider a multi-level representation from a multi-modeling point of view. We define a framework to better specify the concepts used in multi-level modeling and their relationships. This framework is implemented through the AA4MM meta-model, which benefits from a middleware layer. This meta-model uses the multi-agent paradigm to consider a multi-model as a society of interacting models. We extend this meta-model to consider multi-level modeling and present a proof of concept of a collective motion example where we show the ability of this approach to rapidly change from one pattern of interaction to another one by reusing some of the meta-model's components.

INTRODUCTION

In this article, we are interested in the design of complex systems. Simulation is an important tool for the study of such systems because it allows testing different alternatives and different scenarios while limiting experimentation costs.

Complex systems naturally involve at least two levels of representation: local and collective. The former corresponds to the micro level while the latter corresponds to the macro level of the phenomenon. Let us consider the example of pedestrians walking in a street. At the micro level, each of them moves individually, according to his/her personal goal, but the trajectory he/she takes is influenced by other pedestrians' behaviors. When these pedestrians evolve and interact at micro level, they can form a collective motion phenomenon of a crowd at macro level. This macro structure can be considered in its own with its proper attributes (common goal, average density, speed) and behaviors [START_REF] Musse | A Model of Human Crowd Behavior: Group Inter-Relationship and Collision Detection Analysis[END_REF]. In fact, when describing this phenomenon, one can consider both levels: the micro level (pedestrians walking in the street) or the macro level (crowd or groups formation, extinction, evolution and interaction between macro level entities).

In order to study such phenomena (with individual and collective representations), multi-level modeling is a good approach as it explicitly represents these different levels. In this perspective, the different levels can coexist and influence each other. This multi-level approach could be used, for instance, when there is a lack of expressiveness of one level and a second one is needed; when available data explicitly refers to different levels of representation; or when the modeling question is explicitly to study the mutual influences between levels whose dynamics have to be coupled.

Each level of description may correspond to a model. In that case, we propose to consider a multi-level representation with a multi-modeling point of view. The question becomes how to integrate these models, which may describe the phenomenon at different spatial and/or temporal scales and possibly with different formalisms. Such integration isn't trivial as it underlies issues about the consistency of the resulting representation like: How to manage the different formalisms? How to have a sufficiently rigorous multi-modeling process to guarantee some validity of the obtained multi-model? In case where the models are already implemented in simulators the question is also: how to reuse the models with their simulators and make them interoperate?

The AA4MM (Agents and Artifact for Multi Modeling) meta-model [START_REF] Siebert | Agents and Artifacts for Multiple Models Co-evolution. Building Complex System Simulation as a set of Interacting Models[END_REF] answers to this integration issue of heterogeneous models and their simulators. It relies on a multi-agent perspective where each model is seen as an agent and the interactions between agents correspond to data exchanges between models. The multi-model is seen as a multi-agent system (MAS). Using a meta-model is a mean to bring some rigor in the modeling process by adding constraints in the multimodel's design that prevent ill-formed models (in that sense our approach can be related to FURM [START_REF] Ropella | Using Heuristic Models to Bridge the Gap Between Analytic and Experimental Models in Biology[END_REF]) and to allow automating the generation and evaluation of a multi-model.

In the next part, we present different facets of multi-level modeling that involve different kind of interactions between levels and that corresponds to different modeling objectives. Based on similarities between them, we propose a generic framework for multi-level dynamics coupling. We detail the implementation of this framework in the AA4MM meta-model. As multilevel representation were not included in AA4MM's original specifications we explain how AA4MM is extended to multilevel modeling with constraints specific to that kind of representation. Finally, we present our approach's advantages through the implementation of variations of a multi-level modeled collective motion phenomenon.

MULTI-LEVEL REPRESENTATIONS

In this section, we present different approaches (Section 2.1) and different examples (Section 2.2) of multi-level representations in order to show the different facets of the multi-level modeling. We present then a framework describing in a generic way some of these approaches.

Different approaches of multi-level modeling

Different approaches of multi-level modeling exist depending on the relation between the levels and the level-changing policies. Each of them answers to different representational need.

Multi-resolution modeling (MRM) is a model, or a family of models managing several levels of resolution [START_REF] Davis | Families of models that cross levels of resolution: Issues for design, calibration and management[END_REF]. A level is said to be at low resolution when it represents the phenomenon with a coarse description (with respect to a high resolution level).

Different kinds of MRM can be considered. In a selective viewing model, the simulation takes place only at the highresolution level for precision need. The low-resolution level is obtained a posteriori for presentation or data analysis purpose. (Klir 2004). In the aggregation-disaggregation approach, two kinds of entities are considered: the High Resolution Entity (HRE), which corresponds to a micro representation of the phenomenon and the Low Resolution Entity (LRE), which corresponds to a macro representation. Here an entity is only represented at one level of resolution at a time. Aggregation (from HRE to LRE) and Disaggregation (from LRE to HRE) operations are used in order to change of level of resolution. The policy for level changing is determined by the separation of the global modeled space into different areas called play-box. Entities inside a play-box are all represented at the same level of resolution. Aggregation-Disaggregation operations are also used to put entities interacting together at the same levels of resolution.

In a concurrent representation model, the different levels of resolution are concurrently maintained and can influence each other. Here an entity is simultaneously represented at different levels and is called a Multi-Resolution Entity (MRE) [START_REF] Natrajan | To disaggregate or not to disaggregate, that is not the question[END_REF]. The MRE uses a mapping function in order to translate from one level to another [START_REF] Reynolds | Consistency maintenance in multiresolution simulation[END_REF]. The interest of such approach is that it is possible to study the mutual influences between levels.

In a holonic multi-agent system [START_REF] Rodriguez | An analysis and design concept for self-organization in holonic multi-agent systems[END_REF], agents organize themselves into holons that can then group themself into holon (a super-holon) according to pre-defined criteria that can be based for instance on simulation performance [START_REF] Demange | Un modèle d'environnement pour la simulation multiniveau : application à la simulation de foules[END_REF]. The advantage of such approach is that, despite the previous approaches represent the relationships between different levels of resolution, the holonic approach focuses on the formation/separation of higher-level structures.

Some examples of multi-level modeling

In the simulation of the evacuation of Nha Trang City [START_REF] Vo | An Operational Meta-model for Handling Multiple Scales in Agent-based Simulations[END_REF], the major issue is to deal with a huge number of citizen agents evolving on the roads, which considerably slows down the simulation. To increase simulation's performance, roads are divided into two kinds of patches: crossroad patches, and segments of the road patches. In the former, citizen agents are simulated individually while the later used a macro model of pedestrian flow in order to simulate their moves. Each patches is represented by a road agent. An organizational meta-model for multi-scale modeling is used in order to ensure transitions between patches. Road agents use "capture" and "release" operations on citizen agents. A road agent manages execution of all of its captured citizen agents. A captured citizen doesn't have an autonomous behavior anymore. When a citizen agent is released by a road agent, it recovers its autonomous behavior. A road agent captures citizens when they reach the segments of the road patch's borders. Then, captured citizens are considered as pedestrians in the macro model of pedestrian flow. Road patches determine the movements of captured citizens according to the macro model, and releases them when they exit patches' borders.

In the 3D real-time multi-agent pedestrians simulation of [START_REF] Gaud | Holonic Multilevel Simulation of Complex Systems: Application to Real-time Pedestrians Simulation in Virtual Urban Environment[END_REF], the major issue is to deal with computation cost in order to ensure an acceptable performance for the 3D visualization of the simulation while managing a large number of agents. The solution is to dynamically change the level of description in order to have the best trade-off between the accuracy of the simulation and the computation performance. A holonic model is used in order to organize and dynamically change the level of description. Then, in a low level of the holarchy, perceptions and actions of pedestrian holons are aggregated in a pedestrian super holon. Physics based indicators are used in order to determine whether pedestrians should be grouped or considered individually.

In SIMPOP3 (Gil-Quijano 2010), a micro model SIMPOPNano, describing the evolution of a city, is coupled with a mesoscopic model, SIMPOP2, describing the evolution of a system of cities in order to study their mutual interactions. The challenge here is to ensure an ontological translation between levels: the concepts of urban function (from macro to micro) and spatial efficiency (from micro to macro) are used to ensure the passage from a level to another.

In simulBogota (Gil-Quijano 2010), the challenge is to model the evolution of the city of Bogotá when having a lack of information on the behaviors of basic entities (household and housing). In order to deal with this issue, mesoscopic entities are considered (household and housing groups) with an arbitrary defined behavior. Then, groups are dynamically detected and reified at mesoscopic level at each simulation step using an automated classification mechanism of the micro entities. When reified, household groups share housing with an auction mechanism and the micro population evolves based on global rules.

In [START_REF] El | Macro-Micro Simulation of Traffic Flow[END_REF], the hybrid traffic flow approach is to jointly use macroscopic and microscopic models of a traffic flow in order to take advantage of each kind of representation. The space is divided into several areas that are not modeled at the same level. A macro model describing in a global and aggregated way the phenomenon is used for areas that don't necessitate a high level of detail. At the opposite, areas where the traffic flow is more subject to abrupt changes are represented by a micro (multi-agent) model. The challenge here is to ensure transition between models that are not of the same nature, between agents and aggregated values. An upward agent (from micro to macro) and a downward one (from macro to micro) are defined to fill these roles.

All these examples use two models to describe the same phenomenon at different levels of representation (micro and macro) and mapping functions to translate a state from one level to another [START_REF] Natrajan | To disaggregate or not to disaggregate, that is not the question[END_REF]. They can be related to the problem of multi-perspective modeling where each sub-model of the multi-model represents a perspective of the phenomenon (here a macro and a micro perspective) [START_REF] Yilmaz | Requirements and Design Principles for Multisimulation with Multiresolution, Multistage Multimodels[END_REF]. In order to reconcile these different perspectives a bridge model can be used [START_REF] Seck | Multi-perspective Modelling of Complex Phenomena[END_REF]). This bridge model links the different perspectives as it represents how the modeled entities are related in the different models. Therefore, the bridge model can be in charge of the interactions between these perspectives as it makes conceptual translations between them by transforming the exchanged data between the models. However, the nature of relationships between levels don't convey the same constraints. The approaches or examples have to be considered separately according to the kind of representation of one state of the phenomenon. Some of them (concurrent representation, selective viewing) represent simultaneously the same states at two levels of representation whereas others (aggregation-disaggregation, holonic) consider only one level of representation at a time.

A framework for multi-level modeling

The framework we propose is a rephrasing of [START_REF] Bourgine | Distributed Problem Solving in Natural and Artificial Complex Systems[END_REF]. It makes explicit the relationships between the two levels (micro and macro). This framework explicitly represents all features common to the multi-level modeling cases we described in previous sections. In this article we specify how to implement it in order to consider simultaneously two levels of representation.

When representing an upward relationship (e.g. pedestrians are forming groups), we consider the following elements (see Figure 1):

• X t is the set of information describing the state of the target system at time t at micro level. • Y t' is the set of information describing the state of the target system at time t' at macro level. As the macro level is a coarser description of the target system than the micro one, we can state:

(1) card(Y t' ) < card(X t ). • f is a function describing the micro dynamics. It specifies how to pass from X t to X t+dt . • g is a function describing the macro dynamics. It specifies how to pass from Y t' to Y t'+dt' .

•

u is an upward function of integration of X t ensuring the passage to Y t' . According to constraint (1), it does an aggregation of information describing the phenomenon. This function fills the role of a bridge model as it is a translator between two perspectives of a phenomenon (micro and macro views).

Time representations at macro and micro levels are respectively t and t'. This means that the simulations may a priori have different execution policies or time steps. By using two notations, we explicitly ask the question of time correspondence between models. This means that u has also to manage the temporal mapping between levels. This way of representing the different levels is sufficiently generic to be mapped with some of the cases of section 2.2. Indeed, the different elements are expressed in a generic way and then can describe several multi-level modeling example.

Table 1 illustrates how this framework can be mapped on some of the previous cases. Moreover, as the framework is modular, it can be adaptated to different approaches of Section 2.1. (see Figure 3). One can note here that our definition of multi-level coupling can't describe for example direct interactions between entities represented at different levels and approaches considering only one level of representation at a time. The models coupling doesn't have the same semantic for these cases and specifications have to be defined at the conceptual level in order to keep a rigorous modelling process.

If our framework seems to fit these cases in the realm of discourse, we have to investigate further with a concrete implementation. The next section describes how this framework can be instantiated with the AA4MM meta-model.

The AA4MM meta-model

The AA4MM's modeling paradigm

AA4MM [START_REF] Siebert | Agents and Artifacts for Multiple Models Co-evolution. Building Complex System Simulation as a set of Interacting Models[END_REF]) considers a complex phenomenon as a set of interacting event-based models. It relies on the multiagent paradigm: each model corresponds to an agent that is associated with its simulator, and the interactions are instantiated by artifacts [START_REF] Ricci | Give Agents their Artifacts: the A&A Approach for Engineering Working Environments in MAS[END_REF]. The global dynamics of the phenomenon is simulated thanks to the interactions between the models. Originality toward other multi-model approaches is to consider interactions in an indirect way, supported by an environment, and then to explicitly model the sharing of information between models.

The multi-agent paradigm richness of expression offers two advantages here:

• It is sufficiently flexible in term of representation, to be transposed to a multi-modeling point of view.

• The diversity of concepts (Agent & Artifact [START_REF] Ricci | Give Agents their Artifacts: the A&A Approach for Engineering Working Environments in MAS[END_REF], Organization, Role [START_REF] Ferber | Aalaadin: a meta-model for the analysis and design of organizations in multi-agent systems[END_REF])) is useful to convey the diversity of multi-modeling [START_REF] Yilmaz | Dynamic model updating in simulation with multimodels: A taxonomy and a generic agent-based architecture[END_REF]).

The AA4MM's modeling paradigm manages and links the two kinds of dynamics of a multi-model:

• The models' dynamics: It relies on the execution of the simulators implementing each model.

• The multi-model dynamics: the co-evolution of the different models. This dynamics is made explicit thanks to the behavior of the agents associated with each model.

This two dynamics organization allows reusing previously independent models while keeping the simulators they are implemented in, with only a small number of modifications to make.

This paradigm is formalized by the AA4MM's meta-model. The advantage of a meta-model for multi-modeling is that it allows directly manipulating the meta-modeling's concepts. These concepts have semantics that put constraints on the design process preventing the creation of ill-formed multi-model [START_REF] Sprinkle | Metamodelling State of the Art and Research Challenges[END_REF][START_REF] Cetinkaya | A metamodel and a DEVS implementation for component based hierarchical simulation modeling[END_REF]). Moreover when these concepts have operational specifications, they can be then translated in executable software. This meta-modeling approach allows passing from the rigorous design of a multi-model to its implementation as a middleware with a clear separation of the different levels of question. In the next section, we detail the meta-models' concepts. The coupling artifact has a direction, its functioning is illustrated by Figure 5. An interface artifact contains primitives allowing manipulation of its simulator. It allows the following operations on the model: initialization, updating of the individual characteristics, execution for a time step and collecting information about individuals.

Concepts

AA4MM relies on operational specifications and proved algorithms related to temporal coherence between models which allow implementing the multi-model and simulating it with only a selected number of functions specific to the application to define. Conceptual proofs of this approach with the coupling of Netlogo simulators have been done [START_REF] Siebert | Approche Multi-agent pour la Multi-modélisation et le Couplage de Simulations. Application à l'étude des Influences entre le Fonctionnement des Réseaux Ambiants et le Comportement de leurs Utilisateurs[END_REF]. We applied AA4MM to study the mutual influences between mobility models and routing algorithms in mobile ad-hoc networks [START_REF] Leclerc | Multi-modeling and Co-simulation-based Mobile Ubiquitous Protocols and Services Development and Assessment[END_REF].

The original AA4MM's concepts have specifications for a structural coupling of models [START_REF] Siebert | Agents and Artifacts for Multiple Models Co-evolution. Building Complex System Simulation as a set of Interacting Models[END_REF]). The structural coupling is defined as the evolution of a constant number of entities simultaneously involved in several dynamics, each dynamics being managed by a model. AA4MM manages the evolution of the entities' attributes.

In the following, we describe the implementation of a multi-model with AA4MM (Section 3.3) and how we extend the original specifications to implement multi-level coupling (Section 3.4).

Implementation of a multi-model in AA4MM

When implementing a multi-model with AA4MM we make the hypothesis that there are pre-existing simulators implementing each sub-model. In the following, we suppose a multi-model composed of two models m 1 and m 2 implemented respectively by two different simulators sim 1 and sim 2 .

The preexisting AA4MM middleware consists of:

• The m-agent behavior corresponding to a proved multi-simulation algorithm.

• The coupling artifact.

In order to operationalize the multi-model, the interface artifacts have to be defined. Each simulator needs a specific interface artifact.

Features specific to the application have also to be defined:

• The data types of the application: the data exchanged between the m-agents (through the coupling artifacts) and the data to be collected from and injected in each simulator. • Transformation functions between simulators (for example matching time and spatial dimensions). The proved algorithm of AA4MM needs these functions to ensure the consistency between the simulators' executions.

Figure 6 describes the coupling of two models (m 1 and m 2 ) implemented respectively with the simulators sim 1 and sim 2 .

Starting with an interaction graph between models (Figure 6a), a first step is to build its equivalent with the AA4MM metamodel (Figure 6b). The meta-model implementation starts from existing elements: the AA4MM middleware and the two simulators (Figure 7). They have to be completed with an interface artifact for each simulation software, with data types and dimensions matching functions between models (Figure 8). Figure 9 shows the complete implementation of a multi-model with AA4MM.

Figure 9. The complete implementation of a multi-model with AA4MM. Each little grey square represents a data type to be defined.

Multi-level within AA4MM

The framework for multi-level representation presented in section 2.3 is instantiated as follows in the AA4MM's metamodel. As described above, several steps are needed to create a multi-model with AA4MM.

The first step is to define the interaction graph between models where the exchanged data are specified. In our case, each level is associated with a model (m for micro and M for macro). The interactions are the upward relation from micro to macro (u) and the downward relation from macro to micro (d) (see Figure 10a). The next step is to describe this graph with the concepts of AA4MM. Each model is associated with a m-agent and an interface artifact. The A m m-agent manages the micro model and the A M m-agent manages the macro model. Each relation between models corresponds to a coupling artifact between the m-agents (Figure 10b). We define upward and downward artifacts in order to represent the same named functions. The upward artifact (resp. downward) receives data from the A m (resp. A M ) m-agent; these data are modified by the upward (resp. downward) function and send to A M (resp. A m ).

We extended the original AA4MM's specifications in order to develop the corresponding middleware for multi-level modeling. Therefore, we added constraints specific to multi-level representation in respect of the original AA4MM's hypothesis allowing enabling the deployment and implementation of a multi-level model.

The upward and downward functions of our multi-level framework (Section 2.3) are respectively implemented by the transformation functions of the upward and downward artifact with the following new specifications. In a structural coupling between two models, i and i* are lists of values of the same length, therefore length(i) = length(i*). In a upward relations, there is reduction of information, and therefore length(i m ) > length(i m *). For example, i corresponds to pedestrians and i* corresponds to groups of pedestrians. Similarly, the downward relation d is such that length(i m ) < length(i m *).

Moreover, to represent the appearance and disappearance of macro entities in a multi-level modeling, we extend the m-agent specifications in order to allow creation and suppression of entities in addition of the updating operation.

An advantage of this framework's instantiation is that, as each conceptual elements of the framework is instantiated by one AA4MM's component, we can use the modularity of the framework in the AA4MM's meta-model in order to rapidly implement the different configurations of Fig. 3. This point is developed in the following section.

PROOF OF CONCEPTS

In this section, we illustrate through a collective motion example how to implement different patterns of interactions between levels.

The micro level corresponds to moving entities. The micro dynamics corresponds to the flocking model of Netlogo [START_REF] Wilensky | NetLogo Flocking Model[END_REF]. A micro entity is defined by an identifier, a position, an orientation and a color. Its behavior [START_REF] Reynolds | Flocks, Herds and Schools: A Distributed Behavioral Model[END_REF]) is determined by three rules: cohere, align and separate toward other micro entities. The micro entities move at constant speed and have initially the same color that remains unchanged during movements.

The macro level corresponds to moving groups. A group is defined as a set of "close enough" micro entities with similar orientations. In the macro model, a group has an identifier, a position, an orientation, a size and a color (different for each group). We arbitrarily define the group behavior by three rules: cohere, align and separate toward other macro entities (the same as the ones from micro level).

In the experiments, the f and g functions are each implemented by a Netlogo instance simulating the dynamics. The advantage of the AA4MM meta-model here is that, as an interface artifact is specific to a simulator, we only had to define once the interface artifact for all the following cases.

For sake of clarity, we describe multi-level modeling where spatial scale is the same at the micro and macro levels. Details for the management of heterogeneous spatial and temporal scales with AA4MM can be found in [START_REF] Siebert | Agents and Artifacts for Multiple Models Co-evolution. Building Complex System Simulation as a set of Interacting Models[END_REF]).

In the next parts, we implement different patterns of interactions between these two levels. Each pattern is expressed in a generic way as a graph using the functions u, d, f, g. Based on this graph, the corresponding AA4MM diagram is systematically described. Then, the software implementation of this graph is performed thanks to the AA4MM middleware in which we add the domain specific functions.

In section 4.1, we describe how the micro level dynamics influences the macro level: groups form, move and separate according to micro entities configurations (corresponding to the framework's configuration of Fig. 3a). In section 4.2, we add an influence from the macro level to the micro one: groups determine the color of their composing entities (corresponding to the framework's configuration of Fig. 3b). In section 4.3, we introduce mutual influences between the macro and micro levels: micro entities form groups (as previously) but groups have their own behavior and impose their movement to their composing entities (corresponding to the framework's configuration of Fig. 3d). In section 4.4, contrarily to three previous examples, the models don't have the same time scale: one time step at the macro level equals four time steps at the micro one. In section 5, we discuss what are the advantages of this modular approach for the study of multi-level phenomena.

Micro dynamics and upward relationship

The first example is a selective viewing case (corresponding to the framework's configuration of Fig. 3a), where we want to study the formation/separation of groups over time.

Micro entities (X) move (f) and form groups. X and f correspond to a Netlogo instance. An interpretation function u detects groups. It transforms micro entities (X) into groups (Y). Since groups haven't their own behaviors at the macro level, we only need to represent the different states of the macro level but not their evolution: we don't need a simulator instance. Figure 11a shows the corresponding diagram of relations between the levels in our framework. Each level corresponds to a m-agent (Figure 11b). A m manages the micro model m in order to simulate the micro dynamics thanks to a Netlogo instance. The upward function is implemented as a cluster identification algorithm [START_REF] Ankerst | OPTICS: Ordering Points to Identify the Clustering Structure[END_REF]. It transforms, at each time step, a list of individuals' position and orientation into groups. This function takes two parameters: proximity and orientation thresholds.

At macro level, A M collects the number of groups detected by the upward artifact at each time step. This way, we can study the evolution of the number of groups as a function of time (Figure 12).

Micro dynamics, upward and downward relationships

In order to visually identify what are the entities that compose the detected groups, we assign different colors to the micro entities according to the group they belong to. The macro entities have now an influence on the micro level.

Similarly to section 4, micro entities (X) move (f) and form groups. These groups are detected (Y) with an upward function (u). As the macro level has an influence on the micro level, a downward function (d) is required. The corresponding diagram of relations between the levels of representation and the temporal evolution of the phenomenon can be seen in Figure 13a.

A M receives data on detected groups from the upward artifact. It assigns each detected group to a color and provides a list of groups and colors to the downward artifact (Figure 13b). The downward function is implemented in the downward artifact. It assigns groups' color to their composing micro entities and makes this information available to A m , which changes the color of the micro entities accordingly (Figure 14).

Micro and macro dynamics, with upward and downward relationships.

We want to model simultaneously the macro and micro dynamics. The micro entities and the groups have their own behaviors, but when a micro entity belongs to a group, the macro dynamics determines its movement: a micro entity moves with the same vector and has the same orientation as its group. If a micro entity is not in a group, its behavior is the same as in section 4.1 and 4.2.

As previously, micro entities (X) move (f) and form groups. These groups are detected with an upward function (u). The detected groups are reified (Y) and move (g). Y and g are implemented by another NetLogo simulator. d is an interpretation function of groups' mouvements. It transforms Y (movements of groups) to X (movements of entities belonging to groups). The corresponding diagram of relations between the levels of representation and the temporal evolution of the phenomenon can be seen in Figure 15a. Figure 15b is the corresponding representation in the AA4MM meta-model. A m manages the micro model m and simulates its dynamics.

The upward function of section 4.1 and 4.2 is extended. It sets detected groups' attributes by aggregating micro data as follow: position is the gravity center of the micro cluster, orientation corresponds to the average direction of its constituent micro entities and size refers to the dispersion.

A M manages the macro model M and its dynamics. It receives detected groups from the upward artifact and adds, removes or updates them in M, executes one step of simulation, collects data and sends group's vectors and orientation to the downward artifact.

The downward function transforms groups' movements into entities' movements. It is implemented in the transformation function of the downward artifact.

A m receives from this artifact the movements of some entities (those that belong to a group). It modifies the states of these entities accordingly. For the entities not belonging to a group, it asks for a simulation step in order to update their states.

Figure 16 is a snapshot of the multi-model execution. Figure 17 shows an example of use of this pattern of interactions.

Different time scales.

In this section we describe how AA4MM's framework manages different temporal scales between the two simulators. In this case, one macro simulator's time step corresponds to four micro simulator's time steps. This difference of temporal scale implies that, for the same simulation time period, while the macro model produces one data, the micro model produces four ones. Thanks to the modularity of AA4MM, only the downward artifact has to be changed when taking the previous configurations back: the downward function linearly decomposes now groups' movement vectors it received in four parts. The AA4MM's proved decentralized algorithm automatically managed the models synchronization in this case: only the last of the four micro data received by the upward artifact is considered by the macro model.

Discussions

We can see with the different examples of use (Figure 12, 14 and 17) that our approach preserves the advantages of a multilevel representation. We can study the formation of higher-level structures (Figure 12), enhance the visualization of the phenomenon (Figure 14), and make explicit new phenomenon, for instance group's crossing (Figure 17). This modular vision of multi-level modeling facilitates the study of the multi-level phenomenon. As levels' relationships are reified in an AA4MM multi-level coupling, we can test hypothesis about the level's influences by comparing different multilevel representations of the same phenomenon. It is then possible to study the mutual influence of levels, for instance the mutual influence of individuals and groups. As shown in section 4, we can rapidly switch from a pattern of interaction to another with well-focused efforts. Figure 18 shows a comparison of the number of groups detected in simulations using different level's dynamics (described by Table 2) and influences. Table 2. Values of the parameters of the different models being compared. m correspond to the micro model and M i to models of the macro dynamics. The AA4MM's advantages are also preserved with a multi-level coupling. Thanks the modular approach and a clear separation of the different levels of questions, we can change the simulator implementing one model with only changing the interface artifact. It is then possible to compare different implementations of the same model. AA4MM can also be the support to an incremental modeling process as it is possible to test different versions of the same model and check their interoperability in the multi-model.

CONCLUSION

In this article, we proposed to consider a multi-level model as a multi-model. This approach relies on a multiagent vision of a multi-model. We used the AA4MM meta-model to design and instantiate the multi-model.

We defined a framework that organizes the multi-level's concepts and their relations. This framework specifies the patterns of interaction between levels. We translated this framework into the AA4MM while respecting the semantic constraints specific to the simultaneous representation of two levels.

As a proof of concept, we used a collective motion phenomenon to detail different kinds of multi-level representation.

Since we extended AA4MM, we can benefit of its advantages for multi-level representations (reuse of simulators, of meta model component, ease to switch from one pattern to another, ...).

Models

Cohere parameter Align parameter Separate parameter m 3 5 1.50 M 1 3 5 1.50 M 2 0 0 10 M 3 14,25 14,25 0

Figure 1 .

 1 Figure 1. Upward relationship between levels of representation and temporal evolution of the phenomenon.When representing macro dynamics having an influence on the micro one (e.g. groups influence pedestrians), it is needed to add a new relationship (see Figure2):• d is a downward function ensuring the translation of Y t' in terms of influences on f, and f has to integrate this influence. Then the arity of f changes as this function takes two arguments: the micro states of the phenomenon (X t ) and the macro influences (d(Y t' )). According to the (1) constraint, d does an augmentation of information. As u, d is also in charge of the temporal mapping between levels. This function can also be considered as a bridge model.

Figure 2 .

 2 Figure 2. Upward and downward relationships between levels of representation and temporal evolution of the phenomenon.

  Different configurations of the framework. (a) A simple upward relationships corresponding to a selective viewing modeling. (b) A concurrent representation case (without macro dynamics) (c) A concurrent representation case with macro dynamics.

Figure 4 .

 4 of the meta-model. AA4MM relies on three concepts to describe a multi-model: • The m-agent manages a model and is in charge of interactions of this model with the other ones (Symbol in figure 4a), • Each of these interactions (between m-agents) is reified by a coupling artifact (Symbol in figure 4b), • Finally, the interface artifact reifies interactions between a m-agent and its model (Symbol in figure 4c), Symbols of the AA4MM components (a) m-agent, (b) coupling artifact, (c) interface artifact and its model m. A m-agent's behavior corresponds to the cycle: • Read data from the coupling artifact, • Update the individual characteristics and execute one time step of its model via the interface artifact, • Write data to the coupling artifact, A coupling artifact proposes three functions : • write : a m-agent managing a model m 1 writes data i 1 to be transferred. i 1 is a list of values, for example pedestrians' positions in a model, • transform (scaling operation for example) : it changes i 1 data into transformed data i 1 *, • read : a m-agent reads transformed data i 1 *,

Figure 5 .

 5 Figure 5. The three functions of the coupling artifacts.

  (a) Interaction graph between models m 1 and m 2 , (b) AA4MM corresponding meta-model diagram.

Figure 7 .

 7 Figure7. The starting components: the models (here m 1 and m 2 ) implemented in their simulators (here sim 1 and sim 2 ), the magents and the coupling artifacts.

Figure 8 .

 8 Figure 8. Features specific to the application: data types and the interface artifacts specific to a simulator.

  Multi-level within AA4MM. (a) Graph of relations between models. (b) The corresponding AA4MM diagram of multi-level representation.

  Figure 11. A simple upward relation case. (a) Graph of relation between levels of representation and temporal evolution (b)The corresponding multi-level coupling in AA4MM.

Figure 12 .

 12 Figure 12. An example of use: studying the number of groups detected in a flocking phenomenon according to simulation time (average over hundred simulations). Error bars indicate standard deviation.

  A case of micro dynamics with upward and downward relations. (a) Graph of relation between levels of representation and temporal evolution (b) The corresponding multi-level coupling.

Figure 14 .

 14 Figure 14. An example of use: visualization of groups on a snapshot of micro level with colors.

  A case of micro dynamics, macro dynamics, upward and downward relations. (a) Graph of relations between levels of representation and temporal evolution (b) Corresponding multi-level coupling.

Figure 16 .Figure 17 .

 1617 Figure 16. Snapshot of the multi-model execution in a micro and macro dynamics, with upward and downward relationships case. (left: micro level, right: macro level)

Figure 18 .

 18 Figure 18. Number of groups detected according to simulation time (average over hundred simulations) in different AA4MM configuration. Error bars indicate standard deviation.

Table 1 .

 1 Description of some multi-level modeling cases through our framework.

	Multi-level
	modeling	X	Y	f	g	u	d
	cases
	Nha Trang City	Individual citizen in crossroad	Aggregated values	MAS	Equations of pedestrian flow	Capture operation	Release operation
		patches
						Determine the
	SIMPOP3	City's districts and micro urban functions	Cities and macro urban functions	MAS. Micro urban functions localize selves in districts	MAS. Agents localize themselves in cities	spatial performance indicator based on district	Determine cities' micro urban function attribute
						relationship
							Relocation of
	SimulBogota	Household and housing	Household and housing groups	Population evolution rules	Auction mechanism	Classification mechanism	household based on auction mechanism
							result

We limited to two simultaneaous levels in this article. In future works, two directions can be addressed: representing several levels simultaneouly or representing a phenomenon with several levels but considering only one at a time.