Jean-Marie Le Yaouanc
email: leyaouanc@ecole-navale.fr

Éric Saux
email: saux@ecole-navale.fr

Christophe Claramunt
email: claramunt@ecole-navale.fr

A semantic and language-based representation of an environmental scene

Keywords: Spatial cognition, Landscape perception, Scene descriptions

The modeling of a landscape environment is a cognitive activity that requires appropriate spatial representations. The research presented in this paper introduces a structural and semantic categorization of a landscape view based on panoramic photographs that act as a substitute of a given natural environment. Verbal descriptions of a landscape scene provide the modeling input of our approach. This structure-based model identifies the spatial, relational and semantic constructs that emerge from these descriptions. Concepts in the environment are qualified according to a semantic classification, their proximity and direction to the observer, and the spatial relations that qualify them. The resulting model is represented in a way that constitutes a modeling support for the study of environmental scenes, and a contribution for further research oriented to the mapping of a verbal description onto a geographical information system-based representation.

Introduction

Early models of Geographical Information Systems (GIS) have been deeply influenced by quantitative models and geometrical representations of space [START_REF] Johnston | Geographical Information Systems: Principles, Techniques, Management and Applications[END_REF]. Despite the interest of these approaches for cartographical applications, they do not completely reflect the way a human being perceives and describes his/her environment since he/she preferably stores and processes qualitative information [START_REF] Kuipers | Modeling spatial knowledge[END_REF][START_REF] Freksa | Using Orientation Information for Qualitative Spatial Reasoning[END_REF][START_REF] Smith | Geographical categories: An ontological investigation[END_REF]. Qualitative terms arise from common sense, i.e. intuitive concepts we daily manipulate to interact with our environment. Over the past few years, naive geography has been established as the field of study that combines modeling concepts inspired from common sense and perception of space [START_REF] Egenhofer | Naive Geography[END_REF]. Naive geography addresses the modeling of space using concepts derived from daily experience and human knowledge. In particular, naive geography provides a conceptual framework for the study of verbal descriptions derived from the perception of natural landscapes. The perception of space encompasses cognitive principles that favor memorization of the properties of an environment, and communication of its salient properties to an external referent using natural language [START_REF] Herskovits | Language and Spatial Cognition: An Interdisciplinary Study of the Prepositions in English[END_REF][START_REF] Tversky | How space structures language[END_REF].

This paper extends an initial work in which the objective was to provide a linguistic analysis of a verbal description [START_REF] Le Yaouanc | A semantic and language based model of landscape scenes[END_REF]. Our approach addresses the modeling and the representation of the verbal description of a scenery by an observer perceiving it. It combines a conceptual analysis of the sentences and terms, and a structure-based study of the spatial and rhythmic properties that emerge from such descriptions. We consider the case of an observer located in an unknown natural environment, perceiving his/her 360 • surroundings, and who is asked to provide a description of his/her environment to an off-site addressee. The verbal description of a natural environment generally underlines salient entities, as well as the spatial relations binding them, and the overall structure of the environment. We introduce a conceptual modeling of a landscape description, supported by a semantic model that provides a bridge between the perception of a landscape and a qualitative representation. The aim of our research is to provide a representation resulting from the perception of a natural environment, that favors the search for a mapping between descriptions of sceneries and a GIS representation.

The paper is organized as follows. Section 2 briefly discusses related work on the cognitive representations of natural landscapes. Section 3 presents the experimental study, where a panel of observers are given the task of producing verbal descriptions of a natural environment. Section 4 provides a conceptualization of these verbal descriptions and introduces a conceptual model. Section 5 introduces the spatial views that reflect an environmental scene, while section 6 illustrates the potential of the approach. Finally, section 7 draws the conclusions and outlines further work.

Spatial perception and mental representations of space

An observer derives an egocentric perception of an environment that reflects his/her own body of knowledge and experience, and his/her interactions with the proximate environment [START_REF] Muller | Eléments d'une théorie du mouvement pour la formalisation du raisonnement spatio-temporel de sens commun[END_REF]. The resulting mental representation is not limited to a combination of spatial concepts, and the perception based on common sense not an exact replication of the real world [START_REF] Kuipers | Modeling spatial knowledge[END_REF]. This directly reflects the close relationship between common sense, cognitive and sensorial processes [START_REF] Tolman | Cognitive maps in rats and man[END_REF]. This entails several issues such as how spatial knowledge is acquired by human beings, what the range of linguistic constructs manipulated to define and characterize such an environment is, and to which degree the language people manipulate affects their ability to interact effectively with spatial information.

Cognitive studies make a distinction between the internal level oriented to the neuropsychological processes that generate a mental representation and the external level that reproduces the structure-based organization of the observed phenomenon. Our purpose concerns the latter, and it is oriented to the modeling of an environment based on a verbal description. As shown in previous studies, an observer acting in an environment organizes the perceived space according to proximities and senses [START_REF] Tversky | How space structures language[END_REF]. The "proximate environment" is defined as the area perceived by several senses, while the "landscape area" that extends to the horizon is perceived by sight alone [START_REF] Granö | Reine Geographie[END_REF]. The notion of mental space is defined as a cognitive space derived from cultural, pragmatic and linguistic concepts, and common sense-based reasoning [START_REF] Montello | The geometry of environmental knowledge[END_REF]. It has been schematized by "eliminating details and simplifying features around a framework consisting of elements and the relations among them" [START_REF] Mainwaring | Descriptions of simple spatial scenes in English and Japanese[END_REF]. Tversky categorizes four cognitive spaces defined by the actions achievable at different scales, the "space of the body" that integrates our proper actions and sensations, i.e. the area where entities can be touched ; a "space near the body", larger than the previous one, and conceptualized as a tridimensional environment where objects are located ; "the navigational space" i.e. the space in which the observer has to navigate to perceive it as a whole ; and the "space of graphics" made of graphical representations of space (cf. Fig. 1). Similar categorizations of cognitive spaces have been suggested where the identified categories characterize the different spaces according to the scale of entities and their relation to the observer: "figural space" is described as being the space smaller than the body and composed of small objects, "vista space" as the region visible from a single location, "environmental space" as the region accessible via displacement or navigation, and "geographic space" the space too large to be apprehended directly [START_REF] Montello | Scale and multiple psychologies of space[END_REF].

Space around the body

Space of the body

Navigational space

Space of graphics Fig. 1 Tversky's cognitive spaces A mental representation associated to the environmental knowledge is denoted as a cognitive map [START_REF] Tolman | Cognitive maps in rats and man[END_REF], elsewhere quoted as "map in the head" [START_REF] Kuipers | The "map in the head" metaphor[END_REF]. Cognitive maps result from acquisitions using various modalities and perspectives, and are "fragmented, schematized, incomplete and multimodal" [START_REF] Tversky | Cognitive maps, cognitive collages and spatial mental models[END_REF]. A "cognitive collage" aggregates sequences of cognitive maps from different scales and levels of abstraction. It is made of specific cognitive representations, including fragments with imprecise spatial information, particularly for distance or orientation metrics.

Landmarks and salient features are prominent objects used in mental representations of an environment. The role of these structural elements has been characterized by the contribution of Lynch, "The Image of the City" that refers to a cognitive representation where landmarks, nodes, paths, quarters and barriers are considered as primitive concepts of an urban environment [START_REF] Lynch | The Image of the City[END_REF]. These structural elements are typical of such an environment, but landmarks should also be considered as salient natural entities used for the orientation of an observer in a natural environment. Couclelis defines a landmark as a reference identifying a fixed point in the environment, and that helps a human for achieving orientating tasks [START_REF] Couclelis | Worlds of information: the geographic metaphor in the visualization of complex information[END_REF]. A landmark is not just useful for navigation as it can also help for the location of entities located in the vicinity of salient places [START_REF] Appleyard | Livable Streets[END_REF]. Landmarks are defined as spatial constructs with key characteristics that make them recognizable in the environment. Sorrows and Hirtle introduce three categories of landmarks either based on their visual properties that contrast with the other entities of the environment, physical characteristics when those play a prominent role or location in the environment, or cognitive qualities for which the meaning prevails [START_REF] Sorrows | The nature of landmarks for real and electronic spaces[END_REF]. Landmarks that play a prominent role for the qualification of a specific environment constitute key-references for the conceptualization of a natural scene.

Context and experimental study

The perception of natural landscapes can be directly experimented using in-situ observations or using various image-based alternatives. Photographs have been recognized as substitutes for in-situ landscape surveys as they facilitate the collection of verbal descriptions resulting from the perception of an environment. They have been largely used in studies oriented to the cross-comparison of similarities and differences resulting from the direct or indirect perception of landscapes [START_REF] Kaplan | Perception and Landscape: Conceptions and Misconceptions[END_REF][START_REF] Shuttleworth | The use of photographs as an environment presentation medium in landscape studies[END_REF][START_REF] Meitner | Scenic beauty of river views in the Grand Canyon: relating perceptual judgments to locations[END_REF]. It has been observed that although photographs entail some limitations for the precise identification of natural features, and some visual distortions due to the resulting planar projection of a three dimensional space, they provide a convenient alternative for the representation of visual environments [START_REF] Shafer | A comparison of viewer reactions to outdoor scenes and photographs of those scenes[END_REF][START_REF] Stewart | Judgments of photographs vs. field observations in studies of perception and judgment of the visual environment[END_REF]. This consequence is largely due to the high quality of digital photographs and the use of adapted lights and intensities.

Our experimental study has been conducted in the context of several semi-natural landscapes located in France. The experimentation was performed using a panel of 23 participants (18 males and 5 females), non-experts in GIS, and with no previous knowledge of the considered landscapes. The principles of the experiment are as follows. Several 360 • panoramic images were displayed on a computer screen. Photographs were presented in an interactive manner using a Java interface, and the observers were able to explore the scenery by rotating a given view, as they would have done by rotating their body in a natural environment. Photographs were displayed in a large size in order to limit the restriction due to the difference of accuracy between an environment perceived in situ, and that perceived through a photograph. Participants were also able to zoom in on a specific area or entity in order to minimize depth-of-field errors. Sceneries were selected in order to favor an unbiased perception and orientation of the observer, since they were composed of entities with a high structural role (e.g., a footpath crossing the scenery from left to right of the observer, a lake nearby the observer or a footpath running along the seaside that clearly makes the distinction between land and the ocean). After a quick overview of the panoramic photograph using a dynamic interface1 , the panelists were asked to perform a virtual tour of the scene, viewing an observer-centered photograph, and spontaneously describe this photograph in order to favor recognition of the site by an off-site addressee. Participants were also asked to specify when they were rotating the photograph (on the left or right) and ideally use relative relations to translate this movement as they would have done when rotating in situ. Verbal descriptions were recorded using a data storage device and were not to exceed 5 minutes.

Fig. 2 Experimental panorama of a semi-natural environment

An example of description resulting from the perception of the scenery presented in Fig. 2 is as follows: "I'm on a footpath that runs along a castle that was certainly constructed during the Middle Ages, and a pond. In front of me, there is a little valley with the castle on the left of it and at the horizon, I can distinguish a mountain range. Behind me, there is the pond with a large meadow behind and a forest far away"

The verbal descriptions generated by the panelists have led to the following results. Most of the participants describe the panoramic photograph from left to right, taking a reference point to begin their description. Most verbal descriptions are implicitly organized with a hierarchy. 60 % of the participants first describe the scene as a whole with sentences like "I am in a mountainous region". The salient concepts structuring the scene are first mentioned but not located. Next, participants describe the content of the landscape, and the way these concepts are related to the others. This shows evidence of a hierarchical perception of space where the landscape is first perceived and described as a whole, before being specifically described, which confirms previous studies and evidence of hierarchies in the perception of spatial information [START_REF] Hirtle | Evidence of hierarchies in cognitive maps[END_REF]. When observing the environment, humans perceive distinct concepts that are part of the landscape. Most descriptions contain entities directly related to the observer's cultural and ontological background, and his/her common sense. A scene description encompasses salient entities, as their role is prominent in the structure and organization of the environment. Participants identified human-made (50%), relief (30%) and vegetation (15%) entities.

These entities are qualitatively associated to others using spatial relations. The observers interpret photographs of an environmental scene by using spatial relations to qualify the location of the concepts such as "behind the mountain", "in front of the house", "in the background", "in the foreground", "in the long distance", proximity adjectives such as "near", "close to", "far from", "further", directional relations such as "to the right of" and a few constructs that generate a tridimensional representation of the scenery such as "above" or "below". Most of these terms are relative constructs associated to the location of another entity identified in the landscape. It also appears that the roles played by the entities selected by the observer are determined by their contribution to the hierarchical organization of the environment. This confirms Tversky's intuition on the organization of environment that impacts on the structure of a verbal description and precedes its linear structure [START_REF] Tversky | How space structures language[END_REF]. The location of these concepts depends on their proximity to the observer. The proximity spaces that emerge from these descriptions, vary according to the terms used.

The experiment also highlighted the prominent role played by directional relations (50%) which are used twice as often as proximity (30%) and topological constructs (20%). This stresses the fact that directional relations are among the most appropriate for structuring a panoramic view. It is also worth noting the trivial role played by quantitative measurements in the descriptions although two participants used metric data in their description to specify a proximity. This may have been caused by the use of photographs which lack the depth-of-field of three-dimentional space to prompt the descriptions. Moreover, these quantitative measurements are widely associated to an imprecise linguistic term such as "about 500 meters from my position" or "around 400 meters from the house".

In order to describe their environment, the observers took a perspective that depended on the frame of reference used [START_REF] Taylor | Perspective in spatial descriptions[END_REF]. Levinson distinguishes three frames of reference that are intrinsic, absolute or relative depending on the point of view of the observer and the described entities [START_REF] Levinson | Frames of reference and Molyneux's question: cross-linguistic evidence[END_REF]. The intrinsic frame of reference is a binary relation in which the location of an entity is defined in relation to another one. The absolute frame of reference is also a binary relation where the location of a given entity is defined by a fixed support (e.g., cardinal directions). Last but not least, the relative frame of reference is a ternary system since the location of an entity is given both from the point of view of the observer, and the location of another entity of the environmental scene. Experiments show that observers mainly combine two frames of reference, the relative and intrinsic ones, depending on the location of the entities. However, participants are most likely to use a relative frame of reference to locate salient entities. This confirms previous work on the prominent role played by relative frames of reference [START_REF] Taylor | Perspective in spatial descriptions[END_REF].

Conceptual model of an environmental scene

We define an environmental scene as the 360 • environment, perceived and described by an observer from a static point of view. It is associated to an anthropocentric description, i.e., what an observer perceives from his/her location. As humans tend to perceive their environment using different levels of spatial perception [START_REF] Granö | Reine Geographie[END_REF], an environmental scene is qualitatively structured using the concept of proximity spaces respectively defined according to the actions an observer is able to achieve in them. They are defined as follows :

-The space of the body as introduced by Tversky [START_REF] Tversky | Cognitive maps, cognitive collages and spatial mental models[END_REF]. It corresponds to the space that integrates our own actions and sensations. It contains easily accessible and recognizable objects.

-The experienced space that can be easily apprehended by moving around the space of the body. -The distant space is the environment located between the experienced space and the space at the horizon, and is hardly accessible without a significant displacement. -The space at the horizon is made of silhouettes that constitute the boundaries of the forms of relief, i.e. the boundary between land and sky [START_REF] Chevriaux | A landform-based approach for the representation of terrain silhouettes[END_REF].

Cognitive spaces reflect different levels of interaction that vary with the scale of the entities composing them [START_REF] Montello | Scale and multiple psychologies of space[END_REF]. They are influenced by the field of vision of the observer, i.e., their distance from the observer [START_REF] Granö | Reine Geographie[END_REF], and the actions the observer is able to perform in them [START_REF] Tversky | Cognitive maps, cognitive collages and spatial mental models[END_REF]. Similarly, proximity spaces are determined by the actions the observer is able to perform in them, and their distance from him/her. The way the boundaries of proximity spaces are conceptualized by an observer depends on the landscapes studied. They might be materialized by fiat regions of space, i.e., with non-well defined boundaries as there is an uncertainty on the location of their boundaries. Alternatively, they can be revealed by qualitative discontinuities that correspond to a physical reality, and are then considered as bona fide boundaries [START_REF] Smith | Fiat and bona fide boundaries: Towards an ontology of spatially extended objects[END_REF].

The description of an environmental scene can be considered as a one-dimensional semantic time-line [START_REF] Levelt | Linearization in describing spatial networks. Processes, Beliefs, and Questions[END_REF]. This timeline is rhythmed by the succession of sentences, forms, landmarks and relations that structure the environment. This reflects the fact that space is structured through the use of periodic, recognizable signs and rhythmed by similarities and observable changes [START_REF] Deleuze | Mille Plateaux. Critique[END_REF].

From a conceptual point of view, two definitions of space coexist. On the one hand, Newton argues that the existence of space is independent from the existence of entities composing it. On the other hand, Leibniz argues that space is purely relative, never empty and that it is defined by the entities composing it. Our position is close to the latter as we argue that an environmental scene cannot be defined without specification of the location of entities composing the environmental scene, and the relationships that relate them.

Observable entities are materialized by geographical lexemes, i.e., abstract units of morphological analysis in linguistics that correspond to a set of forms taken by a single word [START_REF] Beard | Handbook of Word-Formation[END_REF]. These units include vegetal entities such as meadows or forests, structural and geomorphological features such as mountains or valleys, water bodies such as lakes or marshlands, and human-made features such as roads or buildings. These geographical entities are closely related to common-sense concepts. Geographical entities that are commonly used in everyday discourse are essential for the apprehension of our daily natural environment. They often appear in cartographic symbols, but geographers or cartographers do not always provide a formal definition of them. Since they are mainly used for the description of an application domain, their physical existence cannot be questioned [START_REF] Smith | Do Mountains Exist? Towards an Ontology of Landforms[END_REF]. However, the formalization of these concepts requires an ontology in order to clearly reflect their semantics.

Ontology is the branch of metaphysics that addresses the nature of spatial characteristics of beings and things that exist [START_REF] Williams | On the elements of being[END_REF]. Conceptual models applied to information systems provide a more pragmatic meaning defining ontologies by their main functions as "a specification of a conceptualization" [START_REF] Gruber | A translation approach to portable ontology specifications[END_REF]. One of the interests of these approaches is to infer facts that were previously unknown by the system [START_REF] Guarino | Formal ontology in information systems[END_REF]. The main objective of these approaches is to precisely describe the concepts of the application, and to formalize them through a theoretical framework, in order to convey the semantics and syntax appropriate for a specific domain or application. The design of an application ontology consists in a systematic description of the features that characterize this application, and the relations between them and the features specific to the domain.

Since GIS databases rest on ontological commitments [START_REF] Frank | Spatiotemporal Databases: The Chorochronos Approach, chap. Ontology for Spatio-Temporal Databases[END_REF] and the descriptions of landscapes need to be semantically well-structured, we associate a semantic meaning to the terms of the description using an ontology. The construction of our application ontology is based on the knowledge resulting from a taxonomy derived from a topographic database provided by the French Institut Géographique National. This vector database covers the French territory, at a scale of 1:10 000. One third of the collected descriptions are used for the design of the application ontology. A top -down approach is applied for the modeling process, since the entities identified by the description, and referencing geographical entities of the environment are associated to semantic categories, either anthropomorphic or natural [17]. The application ontology is also composed of spatial relations that are categorized by their type, e.g., topologic, orientation and distance (Fig. 3).

Schematization of a verbal description

We introduce a schematization approach the objective of which is to facilitate the understanding of the concepts and spatial structures that emerge from the verbal description of a scenery. A verbal description is made of a corpus of sentences. A sentence contains several concepts associated using relations that underline the structure of the scene. We characterize a sentence by concepts, i.e., forms and landmarks modeled as entities, and relationships that relate them. We consider that an environmental scene is ordered by two orthogonal dimensions: the rhythm produced by the timeline of the sentences generated by the observer [START_REF] Hohne | On temporal alignment of sentences of natural and synthetic speech[END_REF],

and proximity spaces that locate the entities relatively to his/her location. The rhythm of the verbal description is modeled by a linguistic view, and proximity spaces by a proximity spaces view. The approach is completed by a semantic view that takes into account the ontological characteristics of the represented scene, and directional properties modeled using a directional cones view. The principles and properties of these views are developed in the following subsections.

Linguistic view

The linguistic view provides a semantic schematization oriented to the modeling of the properties of the entities that appear in a verbal description. Concepts and spatial relations are represented by their corresponding lexemes, and associated to semantics derived from the application ontology. The linguistic view combines a conceptual diagram with a framework structured by proximity spaces and the rhythm of the description.

The linguistic view gives a representation of the verbal description of the environment, composed of entities related by relationships, and associated to lexemes of the verbal description (Fig. 4). This view is structured by two dimensions, the temporal and spatial ones. The temporal dimension is given by the ordering of the entities and relationships, and the ordering of sentences represented by the vertical bars that illustrate the end of a sentence and the beginning of another one. The spatial dimension is delineated by the limits of the proximity spaces. The linguistic view models the entities identified in the verbal description according to the temporal ordering of the sentences in which they appear, and materializes the spatial relations between them. This timeline reflects a cognitive order of importance, i.e. important or salient entities are firstly perceived and quoted [START_REF] Landragin | La saillance comme point de départ pour l'interprétation et la génération[END_REF][START_REF] Mainwaring | Descriptions of simple spatial scenes in English and Japanese[END_REF].

The semantics exhibited by the verbal description of a scenery can be closely schematized by a musical score composed of several spatial entities the layout of which constitutes rhythm. According to Bar Yosef, the properties of the musical time organizations and the space concepts are analogous when time is conceived as an axis that transforms time organization and space concept into an analogy between two spaces, the first one-dimensional and the second two-or three-dimensional [START_REF] Bar-Yosef | Musical time organization and space concept: A model of cross-cultural analogy[END_REF]. In the eyes of what is achieved in the musical domain, the interest of such a metaphor is to better understand the phenomenon of rhythm of a verbal description, and its harmony that reveals the respective role of the entities of the scenery. This representation can be analyzed along a melodic dimension that follows the timeline. This should favor the study of the entities that compose a verbal description and the spatial arrangements that emerge.

The representation of a verbal description by a linguistic view is achieved by a semiautomated data processing that retains the sentence structure. This process is achieved with the Tinki parser, a semi-automatic parser used in natural language processing [START_REF] Ligozat | From language to pictorial representations[END_REF]. The text resulting from the verbal description of an environmental scene is filtered in order to keep the relevant information only. Let us consider the example of the sentence "I'm on a footpath that runs along a castle that was certainly constructed during the Middle Ages". Since the noun phrase qualifying the "castle" is not directly pertinent for our modeling purposes, it is not retained. A linguistic analysis is applied, taking into account co-references. A coreference corresponds to a relation between a pronoun and its antecedent. Let us consider the following sentence "On the left, we can see a castle and a valley on the right of it" which becomes "On the left, there is a castle. A valley is on the right of the castle" after processing. This representation outlines the entities quoted several times in the description (or entities with initial co-references such as the one labelled "castle" in the previous example), this reinforcing their role in the scene description. This confirms previous studies that outline the fact that linguistic salience is generally linked to physical or visual salience [START_REF] Landragin | La saillance comme point de départ pour l'interprétation et la génération[END_REF][START_REF] Carlson | On the "whats" and "hows" of "where": The role of salience in spatial descriptions[END_REF].

Once the linguistic process is achieved, the identified entities are associated to one-tomany proximity spaces. This implies a specification of the distance and directional relations that qualify the location of entities. Let us consider the example "I'm on a footpath. In front of me, there is a little valley with the castle on the left of it and at the horizon, I can distinguish a mountain range". As the space of the body corresponds to the area where entities can be directly apprehended, the "footpath" is directly located in the space of the body. On the contrary, as language can generate several interpretations, the "valley" and the "castle" can be located into either the experienced or distant proximity spaces. Lastly, specific terms such as "at the horizon, I can distinguish" illustrate specific cases where the entities are located in the space at the horizon. Since the application ontology also integrates distance relations and the associated linguistic terms used by the panel of participants, the allocation of a particular proximity space to an entity is semi-automatically computed.

The principles of the modeling approach being introduced, we hereafter present its formal representation. Let P be the set of sentences composing a verbal description, D the set of verbal descriptions, U the set of elementary units composing a sentence, E the set of entities of an environmental scene, and R the set of spatial relations including the null element / 0. A verbal description D is formalized as an ordered set of sentences p i ∈ P, i.e., D = [p 1 , p 2 , . . . , p n ] where D ∈ D and n ≥ 1. A sentence p i is an ordered set of elementary units u i ∈ U , i.e., ∀i ∈ [1, . . ., m] with m ≥ n, p i = [u 1 , u 2 , . . . , u m ]. An elementary unit u i is a triplet such as u i = [e j , r k , e l ] with e j , e k ∈ E , and r k ∈ R.

As the observer implicitly acts as a spatial reference, he/she refers to his/her location at least once during the description of the surroundings, i.e., ∀D ∈ D, ∃e i ∈ E , e i = observer. Three classes of spatial relations are used by the panelist to locate entities. Let T = {directional, distance, topological} be the set of possible types for the relations, then the function f relation that associates a type to a relation is given by

f relation : R { / 0} → T r i → type (1)
Spatial entities are linked by relationships, the function h that models the relation r k associating two entities e i and e j is given by

h : E 2 → R (e i , e j ) → r k , such as [e i , r k , e j ] ∈ U . (2)
Let S = {body, acc, dist, hor} be the set of proximity spaces, P(S ) the power set of S i.e. the set of subsets of S , and e i ∈ E . The function f space (e i ) that locates the entities is given by

f space : E → P(S ) {} e i → {s i } such as s i ∈ S (3)
With respect to the example given by Fig. 4, we have f space ( f oot path) = {obs} and f space (castle) = {acc, dist}. It is immediate to note that at most four proximity spaces can be associated to a given entity, i.e., ∀i, 1 ≤ Card( f space (e i )) ≤ 4 where Card() is the cardinality operator. Also, when an entity is located over several proximity spaces, this entity fulfils a contiguity constraint defined as follows

2 ≤ Card( f space (e i )) ≤ 4 ⇒ f space (e i ) = / 0 (4)
Let us denote f occurrence (e i , j) the function that returns the number of occurrences of an entity e i in the sentence j f occurrence : E * N * → N, with N * the set of natural numbers excluding 0

(e i , j) → k (5)
It is also immediate to note that each entity quoted in the verbal description appears at least one time in a sentence, i.e. ∀e i ∈ E , ∃ j ∈ N such as f occurrence (e i , j) ≥ 1. Finally, f sentence is defined as the function that associates a set of ordering sentence numbers { j} to an entity e i . A non-empty set corresponds to the presence of the entity e i in the sentence(s) { j}

f sentence : E → P(N) e i → { j} such as f occurrence (e i , j) ≥ 1. (6)
The verbal description of Fig. 4 has three sentences with f sentence ( f oot path) = {1} and f sentence (castle) = {1, 2}. The constraint ∀i, 1 ≤ Card( f sentence (e i )) ≤ n, where n is the number of sentences of the verbal description, illustrates the fact that a given entity exists at least in one sentence, and at most in all sentences of the verbal description. The example illustrated in Fig. 4 shows evidence of a progressive description from nearby to distant spaces. A landmark, the castle, is present in two different sentences, thus playing a prominent role on the relative location of the other landmarks of the description. This example confirms that the boundaries between the distant and the experienced spaces are difficult to evaluate in most cases.

Semantic view

The objective of the semantic view is to provide a summarized representation of the entities and spatial relations identified in a verbal description. A semantic view is defined by a finite and connected graph G where nodes model named entities, and edges the named relations (Fig. 5). The semantic graph makes the difference between the node referencing the observer, and the ones that reference spatial entities quoted in the verbal description and represented by the linguistic view. More formally, the semantic graph G of the scene description is given by the pair of elements G = (V, E). The elements of V are the nodes of the graph G, the elements of E are the labelled edges. Each triplet u i corresponds to a subgraph G i where e j and e k are the vertices and r k the edge. This view outlines the entities that play a central role in the description (e.g., observer, pond and footpath) and the outliers (e.g., forest). It also reveals the diversity of the terms used for the entities and relations from the ontology, and thus the variety of the elements identified in the landscape. The integration of proximity spaces within the semantic view gives another interpretation of a scene description (cf. Fig. 6). Let E body be the set of entities located in the space of the body, E exp the set of entities located in the experienced space, E dist the set of entities located in the distant space, and E hor the set of entities located in the space at the horizon. The proximity spaces are defined as E body = {e i such as f space (e i ) = {s j such as ∃s k such as s k = body}} E exp = {e i such as f space (e i ) = {s j such as ∃s k such as s k = exp}} E dist = {e i such as f space (e i ) = {s j such as ∃s k such as s k = dist}} E hor = {e i such as f space (e i ) = {s j such as ∃s k such as s k = hor}} [START_REF] Deleuze | Mille Plateaux. Critique[END_REF] The proximity spaces view illustrates a summarized representation of the entities associated to the proximity spaces. Fig. 6 illustrates the prominent role of the distant and It is also worth noting the relations that connect entities between different proximity spaces (e.g., footpath), or within a given proximity space (e.g., pond). Overall, this view provides a representation of the structure of the landscape that results from the verbal description, of the respective importance of the proximity spaces identified, and the relative depth of field of the image of the landscape perceived by the observer.

Directional cones view

Humans also tend to structure space using bodily directions that relate the perceived entities to their location in space. The way these directional relations organize space implicitly generates a partition of space, often represented using conceptual directional cones [33]. A cone-based partition emerges from the directional relations identified. The proximity spaces view is enriched by the directional relations and an orientation-based structure of space. We retain a cone-based partition with four possible directions : front, back, right, and left (cf. Fig. 8).

A directional cone is detected when at least one directional relation exists between the observer and an entity of the environmental scene. The number of directional cones can vary from two (front -back or right -left) to four (front, back, right and left), depending on the directional relations used between the observer and an entity or a group of entities to describe the surroundings. More formally, let < t be a temporal ordering operator of the terms of the description, i.e. entities and relations of elementary units, E f ront the set of entities located in the directional cone in front of the observer, E back the set of entities located in the back cone, E le f t the set of entities located in the left cone, E right the set of entities located in the right cone, and x a directional relation such as x ∈ { f ront, back, le f t, right} ⊂ R. We define E x such as E x = {e m such as e n < t e i ≤ t e m with ( f relation (h(e n , e i )) = directional∧ e n = observer) ∧ ((h(e n , e i )) = x} [START_REF] Egenhofer | Naive Geography[END_REF] Since the application ontology makes the distinction between the directional relations and the others, the process of detection of a new directional cone is automatically done when a directional relation is specified between the observer and an entity or a group of entities. The user should finally manually adjust the number of directional cones and their composition. The example of Fig. 7 illustrates the roles played by directional relations in the verbal descriptions. It appears here that directional relations tend to reference distant entities in order to make their location more precise. Conversely, they are barely used for nearby entities. This directional-based view clearly makes a difference between the spaces in front and behind the observer. It provides another characterization of the verbal description. This allows a preliminary spatialization of the identified entities thanks to an observer-centered structure of the scenery. The scene that results from the perception of an environmental scene is then structured by the proximity spaces, and the directional cones that provide an observer-centered reference for the location of entities.

Conceptual map of an environmental scene

The successive views provide a semantic foundation for the derivation of a conceptual map that should reconcile them within a representation that integrates the proximity spaces, directional cones, entities, relationships and sentences of the verbal description. We define such a "conceptual map" as an abstraction that characterizes the mental mapping of a verbal description. It should provide a bridge between the linguistic characteristics of a verbal description, its mental abstraction, and the semantics of the scene observed.

Fig. 9 gives an example of such a conceptual map where space is structured into two areas, i.e. the front and back of the observer. The conceptual map that results from this example shows evidence of a close relationship between the different sentences described and the entities identified. This reflects and generates a sort of continuity of the description, this being reflected by the intertwining of the salient features that emerge. These conceptual maps allow comparison of descriptions either made by different observers, or resulting from different landscapes. Let us consider another example of verbal description, the one of an observer walking along a seacoast of Brittany, France and illustrated by Fig. 10: "Behind me, there is a huge lighthouse and four houses nearby. I'm on a footpath, and on my right there is a grassy hill. On my left is the Ocean". The conceptual map that emerges from this verbal description shows a clear separation between the different parts of the scene. The observer mainly uses bodily-centered directions to qualify the location of the entities such as the "footpath", the "lighthouse" and the "ocean". There are a few connections between the entities, this reflecting a landscape with a clear separation between the different entities identified by the observer, the sentences and the entities, and the conebased regions of the scene. It is also worth noting the small number of entities identified, this illustrating the relative flatness of the landscape. Last, the "lighthouse" clearly denotes a salient role as several entities are spatially related to it.

Conclusion

The research presented in this paper introduces a language-based and cognitive approach that models the verbal description of a landscape scene. A verbal description is modeled by a qualitative, structural and proximity-based representation that reflects its semantics. The structural properties of a verbal description are linked to several semantic views that attempt to reflect the user's perception, and rely on a semantic-based analysis. Semantics, proximity-spaces and directional cone-based views together provide a step towards a "conceptual map", conceived as an abstraction that characterizes an environmental scene from its verbal description. The model is based on the spatial structure, the rhythmic organization In front of me, there is a little valley with the castle on the left, and at the horizon, I can distinguish a mountain range.

Behind me, there is a pond with a large meadow behind, and the forest far away.

Fig. 9 Conceptual map of a semi-natural landscape of space, the diversity, ordering and salience of the entities identified by the observer, and reflect the main characteristics and entities of the environment. Such a model qualifies and characterizes natural landscapes, and provides a framework for the analysis of the properties of the verbal descriptions made by different observers, and cross-comparisons of different landscape descriptions. Although experienced in natural landscapes, this modeling approach could potentially be applied to urban environments.

Further work concerns an evaluation of the properties of the salient entities identified in a description of a given landscape and the design of a prototype that should provide a preliminary resource for the development of a mapping between a scenery description of an observer and a conventional GIS representation. It should provide a support for the georeferencing of the observer from the analysis of the salient and structural components of a scenery description.

Sentence n°1

Sentence n°2 Sentence n°3

Fig. 3

 3 Fig. 3 Top level concepts of the application ontology

Fig. 4

 4 Fig. 4 Linguistic view of a verbal description

Fig. 5

 5 Fig. 5 Semantic view of a verbal description

Fig. 6

 6 Fig. 6 Proximity spaces representation

Fig. 7

 7 Fig. 7 Directional cones search

Fig. 8

 8 Fig. 8 Directional cones representation

Fig. 10

 10 Fig. 10 Conceptual map of a maritime environment

The experimental setup is available at http://experimentation.yaou.org/

Acknowledgements

The authors gratefully thank the anonymous reviewers for their helpful comments, and Alcino Ferreira for his careful language reviewing and comments.


Jean-Marie Le Yaouanc
email: leyaouanc@ecole-navale.fr

Éric Saux
email: saux@ecole-navale.fr

Christophe Claramunt
email: claramunt@ecole-navale.fr

A Visibility and Spatial Constraint-based Approach for Geopositioning

Keywords: Landscape perception, place descriptions, scene-finding approach, geopositioning

Over the past decade, automated systems dedicated to geopositioning have been the object of considerable development. Despite the success of these systems for many applications, they cannot be directly applied to qualitative descriptions of space. The research presented in this paper introduces a visibility and constraint-based approach whose objective is to locate an observer from the verbal description of his/her surroundings. The geopositioning process is formally supported by a constraint-satisfaction algorithm. Preliminary experiments are applied to the description of environmental scenes.

Introduction

Geopositioning is a process whose objective is to relate a geographic location to a given entity, activity or person. This is supported by qualitative references to locations we employ in everyday discourse, e.g. place-names, and quantitative representations used in many activities based on coordinates-based navigation. Early geopositioning systems have been widely applied to quantitative models and geometrical representations of space. Despite the interest of these approaches for cartographical applications, they do not completely reflect the way a human perceives and describes his/her environment since he/she preferably stores and processes qualitative information. This is particularly relevant for natural environments since they do not have well-defined emerging structures similar to those present in an urban environment. Perception encompasses cognitive principles that favor memorization of the main properties of an environment, and potentially communication of these properties to an external addressee using natural language [START_REF] Herskovits | Language and Spatial Cognition: An Interdisciplinary Study of the Prepositions in English[END_REF][START_REF] Tversky | How space structures language. Spatial Cognition: An Interdisciplinary Approach to Representing and Processing Spatial[END_REF]. These descriptions are essentially qualitative and based on common sense, i.e., intuitive concepts we daily manipulate to interact with our environment [START_REF] Kuipers | Modeling spatial knowledge[END_REF][START_REF] Freksa | -Temporal Reasoning on Theories and Methods of Spatio-Temporal Reasoning in Geographic Space[END_REF][START_REF] Smith | Geographical categories: An ontological investigation[END_REF].

While the interpretation of spatial relations for the location of entities has long been studied, they have been hardly considered for the geopositioning of an observer perceiving his environment. The objective of the research presented in this paper consists in developing a model suitable with perception and spatial cognition, but also appropriated for the processing of quantitative spatial data. We consider the case of an observer located at a fixed vantage in a natural landscape, perceiving his/her 360 • surroundings, and who is asked to provide a description of his environment to an external addressee. The description of such an environment underlines the salient entities of space, the spatial relations between them, and the structural properties of the environment. Entities are identified according to a semantic categorization, their proximity and orientation with respect to the observer [START_REF] Le Yaouanc | A semantic and language-based representation of an environmental scene[END_REF]. The research presented in this paper extends this modeling approach by identifying the possible locations of the observer from the interpretation of the description of his surroundings. It is supported by a visibility and constraint-based approach. This provides a support for search and rescue approaches by bridging the gap between a qualitative map resulting from the direct perception of a scene, and a quantitative representation of the environment given by a GIS database.

The remainder of the paper is organized as follows. Section 2 presents the modeling background of the approach and a conceptual representation of an environmental scene. Section 3 introduces the context of this research and develops the modeling approach, based on the concept of visibility of salient entities and the interpretation of spatial relations as spatial constraints. Lastly, Section 4 draws the conclusions and outlines further work.

Modeling background

In a previous work, we have introduced a structural model of a scene generated from the interpretation of a verbal description. It identifies the salient entities, spatial relations between them, and spatial constructs of the landscape [START_REF] Le Yaouanc | A semantic and language-based representation of an environmental scene[END_REF]. The spatial description is schematized by a representation that constitutes a modeling support for the study of environmental scenes, i.e., 360 • scenes perceived by an observer from a fixed vantage viewpoint. The perception of an environment is closely associated to a cognitive organization that reflects different levels of perception [START_REF] Montello | Scale and multiple psychologies of space[END_REF]. Since humans tend to structure space using distance and bodily directions, an environmental scene is structured by four proximity spaces determined by their distance from the observer, and a directional cone-based partition [START_REF] Peuquet | An algorithm to determine the directional relationship between arbitrarily-shaped polygons in the plane[END_REF] whose number can vary from two (front/back or right/left) to four (front, back, right and left). Let us consider an example of scene description given by an observer to a distant addressee who is asked to consider the described environment: " I am on a footpath that runs along a castle and a pond. In front of me, there is a little valley with the castle on the right of it and at the horizon, I can distinguish a mountain range. On my right is the farm of the castle. Behind me, there is the pond with a meadow behind, and a forest far away ". In order to promote communication and cooperation, the observer contribution should be informative enough [START_REF] Grice | Logic and conversation[END_REF]. We assume that the resulting scene description can result from a preliminary complex dialogue between the observer and the addressee for the settlement of inconsistencies and vagueness problems. In order to keep the relevant information, the description is first parsed and semi-automatically filtered by the Tinky parser [START_REF] Ligozat | From language to pictorial representations[END_REF]. Co-references are identified and resolved, and the description is modeled as a set of triplets u i such as u i = [e j , r k , e l ] with e j , e l ∈ E the set of entities of an environmental scene, and r k ∈ R the set of spatial relations. Distance and directional relations are interpreted with the use of an application ontology, and the identified entities are associated to one-tomany proximity spaces and directional cones. No matter the nature, prominence or familiarity of the considered objects, the spatial relations are interpreted in order to favor their relative ordering.

The resulting conceptual map of Figure 1 illustrates the spatial structure, diversity and relative ordering of the entities. Such a model qualifies and characterizes natural landscapes, and provides a framework for the analysis of the properties of the verbal descriptions made by different observers, and crosscomparisons of different landscape descriptions. However, the salient entities of the scene are not always clearly revealed. This has motivated the integration of salience scores, supported by a mutual reinforcement algorithm. It reflects the particularities of the entities that emerge from a scene description such as their linguistic properties, i.e., the richness of information associated to each term, and their structural characteristics, i.e., the degree of spatial isolation [START_REF] Le Yaouanc | A salience-based approach for the modeling of landscape descriptions[END_REF].

Geopositioning approach

Recent years have witnessed significant geopositioning developments, particularly when locations are not available using global positioning systems. This has been applied to search-and-rescue operations where the location of a human (usually lost) should be retrieved. The ability of lost persons to precisely describe their perceived environment is essential to a successful identification of their location. The way people and particularly children behave and model their environment has been studied by cognitive studies, while cognitive distortions and reasons for retrieval failures have been qualified [START_REF] Cornell | The problem of lost children[END_REF]. Preliminary experiments have explored the potential of GIS for the management of search teams [START_REF] Heth | A Geographic Information System for Managing Search for Lost Persons[END_REF], or the behavior of a lost person regarding her initial displacement plans, goals and own abilities [START_REF] Ferguson | GIS for wilderness search and recue[END_REF]. However, GIS have not been used to the best of our knowledge for geopositioning an observer from a qualitative description and interpretation of his environment.

The description of the surroundings of the lost person is used as the only input of our approach. No assertion is made on their background, will, route, the reason why they planned the excursion, etc. The methodology used for the search of the observer results from the analysis of the verbal description. This is based on the interpretation of the entities and landmarks identified in the description, the spatial structure emerging from the proximity spaces that illustrate a relative ordering between the entities, and direction relations between the entities. The geopositioning approach searches for the possible locations of the observer, and is applied as follows:

1. For each entity identified by the observer, computation of the viewsheds i.e., places for which each quoted entity can be perceived by the observer. 2. Interpretation of the direction relations derived from the directional cones and identification of a new set of candidate solutions for the observer location. 3. Interpretation of the distance relations derived from the proximity spaces and identification of a new set of candidate solutions for the observer location.

4. Interpretation of the direction relations given relatively to entities, and identification of a new set of candidate solutions for the observer location.

Visibility-based approach

Viewshed computation and analysis have long been applied in landscape and urban studies [START_REF] De Floriani | Line-of-sight communication on terrain models[END_REF][START_REF] Fisher | Extending the applicability of viewsheds in landscape planning[END_REF][START_REF] Fogliaroni | A qualitative approach to localization and navigation based on visibility information[END_REF]. The main principle of a viewshed analysis is commonly determined by defining one location as the viewing point, and then calculating the line-of-sight to every other point within the region of interest. When the surface rises above the line of sight the target is out of sight, otherwise it is considered as in-sight [START_REF] De Floriani | Algorithms for visibility computation on terrains: a survey[END_REF][START_REF] Lee | Analyses of visibility sites on topographic surfaces[END_REF]. The range of application is relatively large, from architectural studies where visibility represents a qualitative parameter for a site selection to minimize or maximize [START_REF] Smardon | Foundations for Visual Project Analysis[END_REF], to the distribution of forest-fire observation towers in natural environments [START_REF] Travis | VIEWIT: computation of seen areas, slope, and aspect for land-use planning[END_REF].

The modeling approach should identify the possible locations of the entities quoted in the description. Let us assume that the described entities are directly visible from the fixed viewpoint of the observer. The visibility-based approach mainly focusses on the area from which the location of the entities can be viewed, as opposed to the visible area that is not equivalent because the height of the object at the viewing point may be different from the height of the viewed object [START_REF] Fisher | Extending the applicability of viewsheds in landscape planning[END_REF]. Our objective is not to precisely locate the observer but rather the area the observer is supposed to be located at. Without loss of generality, we consider as equivalent the regions seen from a given entity and the ones visible from the observer.

Let us introduce the formal representation of the visibility-based approach. Let E be the set of entities e i identified in a verbal description D, S denotes the ordered set of salient entities e i ∈ E, i.e., S = [e 1 , e 2 , . . . , e n ] and n denotes the cardinality of set S. Let B be the set of objects of a GIS database considered as the repository of the region of interest. These objects and the relations materialized in this GIS database are organized into a lattice of classes and sub-classes, that result from a classification provided by the French Institut Géographique National (Fig. 2).

f class : B → C b j → c. (1)
Similarly, the function g class that associates the class c ∈ C to an entity e i ∈ S is given by

g class : S → C e i → c. (2)
Let e i ∈ S a salient entity of the verbal description. Since entity e i is visible by the observer, the visibility-based approach should select all objects b j of the database that correspond to the class of objects identified in the description as all could potentially be perceived by the observer. Let R denote the set of m objects b j ∈ B whose class fits that of entity e i , i.e., g class (b j ) = f class (e i ), and i ∈ [0, . . . , m], j ∈ [0, . . . , n].

Let v be the function dedicated to the visibility computation. Let t be a digital terrain model, i.e. a triangulated irregular network that describes the topography of the region of interest. Given an object b j located on terrain t, the viewshed of b j is the set of points p of t from which b j is visible. We consider that two points are defined as being visible to each other if a straight line can be drawn between the points without intersecting any part of the terrain surface between them, i.e., v(b j , t) = { p ∈ t / [b j , p] ∩ t = ∅ }. Let h vis (e i ) be the function that corresponds to the set of areas from which objects b j , j ∈ [1, . . . , m] of a similar class than entity e i are visible. Then, h vis (e i ) = {v(b 1 , t), . . . , v(b m , t)}.

Let S vis be a function that computes the possible locations of the observer that result from the visibility-based approach. S vis is defined by the intersection of the different viewsheds associated to each salient entity, i.e., S vis = {h vis (e i )}, where i ∈ [1, . . . , n]. It is worth noting that the saliencebased approach enables to consider only the most salient entities rather than considering all of them. Afterwards, we shall however take into account all entities.

Let us consider the example of description " I am on a footpath that runs along a castle and a pond. In front of me, there is a little valley with the castle on the right of it " and the resulting ordered set of salient entities S={"castle", "footpath", "pond", "valley"}. Firstly, the m objects b j of the database whose class is "castle" are selected and each viewshed v(b j , t) is computed. If object "castle" is the one considered, a solution for the possible location region of the observer is given by the set of viewsheds of b j 's, i.e. h vis (castle) = {v(b 1 , t), . . . , v(b m , t)}. The same method is applied to objects "footpath", "pond" and "valley", and the visibility-based solution is provided by the intersection of the viewsheds associated to each salient entity, i.e., S vis = {h vis ("castle ′′ ) ∩ h vis ("f ootpath ′′ ) ∩ h vis ("pond ′′ ) ∩ h vis ("valley ′′ )}. The candidate objects are those that can be perceived directly from the area given by the visibilitybased solution, i.e., {b j , c j , d j , e j such as b j ∈ "castle ′′ , c j ∈ "f ootpath ′′ , d j ∈ "pond ′′ , e j ∈ "valley ′′ and (h vis (b j ), h vis (c j ), h vis (d j ), h vis (e j )) = ∅}.

The visibility-based approach identifies the possible location areas where the observer can be located. Figure 3 summarizes the principle of this approach. This first step also identifies a set of physical objects of the environment that could potentially be observed from the location regions S vis . This preliminary filtering of the solution area will be refined in the following sub-sections by the interpretation of spatial relations between these objects and illustrated by the proximity spaces and directional cones.

Spatial relations as spatial constraints

Spatial relations are interpreted as spatial constraints that refine the possible locations of the observer. These spatial constraints are derived from the interpretation of linguistic expressions, and supported by the use of directional cones and proximity spaces of the conceptual map. This can be considered as a specific application of declarative modeling that is commonly applied to the automatic generation of an environment that corresponds to some linguistic descriptions. In particular, text-to-scene modeling has been used in many applications such as architectural design [START_REF] Larive | Automatic generation of urban zones[END_REF], and for the generation of virtual urban landscapes and animated scenes from road accident reports [START_REF] Aakerberg | CarSim: an automatic 3D text-to-scene conversion system applied to road accident reports[END_REF]. These modeling approaches are based on the interpretation of spatial constraints and semantic knowledge [START_REF] Le Roux | Using Constraint Satisfaction Techniques in Declarative Modelling[END_REF]. This is equivalent to a constraint satisfaction problem applied to the linguistic relations identified in an environment description [START_REF] Desmontils | Expressing constraint satisfaction problems in declarative modeling using natural language and fuzzy sets[END_REF]. A constraint-solver algorithm analyses the coherence or incoherence of the linguistic description in order to derive a possible representation of the scene.

The interpretation of the spatial relations quoted in the description is supported by the directional cones and proximity spaces that structure the conceptual map (Fig. 1). The principle consists in finding the limits of the location of the observer for which:

-The entity locations in the directional cones fulfill the linguistic description properties (Cases 1 and 2). -Distance relations given relatively to the observer are geometrically interpreted and supported by the use of proximity spaces (Case 3). -Relative direction relations between two entities are geometrically interpreted (Case 4).

Case 1. Entities in opposite directional cones Let us consider two entities located into two opposite directional cones (front/back or right/left), i.e., entities related to the observer by two opposite direction relations. The algorithm identifies the possible locations of the observer by computing the limits where object B is in front of the observer and object A is behind him, with a space segmented by two straight lines t A and t B that define the four directional cones, i.e. front, back and right, left. Objects A and B of the database are fixed, and the principle illustrated by Figure 4 consists in identifying the limits of the solution that satisfies the directional constraints by moving the directional cones along the whole boundary of object B. This generates a relative displacement of object A while retaining its location in the back cone, and object B in the front cone.

In order to get an exhaustive solution without losing possible locations due to approximation errors, we consider that an object that intersects the boundary of a directional cone is in that directional cone. In such a case, t A (resp. t B ) is tangent to object A (resp. B). The difference with polylines is given by the intersection between t B and B (resp. t A and A) that can then be a segment rather than a point.

Figure 5 illustrates the possible observer locations with respect to two objects A and B, when considering their relative locations to the observer. The solutions presented to the left and right of the figure show the range of the observer positions that fulfill the direction constraints. This algorithm is applied to all object pairs of the geographical database whose classes correspond to those of the entities located in two opposite directional cones. Let us consider the following example " the castle is in front of me, and the valley behind ", the previous algorithm is then applied to all object pairs ("castle", "valley") of the geographical database that also belong to the previous solution S vis . Let E C1 be the set of entities of the verbal description that are in a directional cone (e.g. E f ront ), and E C2 the set of entities of the verbal description that are in the opposite cone (e.g. Let N B and M B denote the intersections of the interior tangents t A and t B with object B. When space is partitioned by two subspaces, i.e., front/back or right/left, the solution is given by uniformly moving point P B along the boundary of object B from points N B to M B (Fig. 6). For each P B , a solution S i P B given by the half space behind object B fulfills the constraint for which B is in front of the observer (i.e., the observer is behind B). A similar method is applied to object A. For each P A , a solution S i P A given by the half space is front of object A. S dir corresponds to the intersection of the two sub-constraints, i.e., S dir = ∩(S i P B , S i P B ). Case 2. Entities in an identical cone Let us consider a second case where two entities are located in a same directional cone, i.e., entities related to the observer in a similar way. An equivalent algorithm is applied with the difference that it identifies the possible locations of the observer by computing the limits for which objects A and B are in a same cone. The solution region S dir_cone is the complement of solution given by Case 1.

When space is partitioned by two directional cones (front/back or right/left), the solution is constructed by uniformly moving point P B (resp. P A ) along the boundary of object B (resp. A) from points N B to M B (resp. N A to M A ) that constitutes the intersection of the exterior tangents t A and t B to object B (resp. A). The solution is given by the exterior region bounded by the convex hull between A and B. interpretation is given by the use of the proximity spaces that structure the conceptual map. When some entities are located in an identical directional cone, they can be located in different or similar proximity spaces with respect to the location of the observer. Figure 7 illustrates an example of distance constraint satisfaction where object A is in front of the observer, and B is behind A. The space S distance that satisfies the two constraints also refers to the possible locations of the observer. The principle consists in finding the limits of the observer's location with respect to the following constraints:

-Entities A and B are in an identical directional cone.

-Their distances relatively to the observer correspond to those supported by the conceptual map.

When searching for a candidate location of the observer relatively to objects A and B as illustrated in the previous example, the search method is as follows. Space is uniformly discretized by uniformly moving point P B (resp. P A ) along the boundary of object B (resp. A). For each location of point P B (resp. P A ), tangents t B and t A are constructed. The relative ordering of the different entities composing the environmental scene is then defined by projecting entities A and B on the median line that bisects angle t A , t B (Fig. 7). The interval endpoints are compared one to the other, as applied elsewhere in unidimensional spaces Fig. 8. Relative direction constraint [START_REF] Mukerjee | A representation for modeling functional knowledge in geometric structures[END_REF]. We consider that B is behind A when their endpoint beginnings (relatively to the observer) coincide. This search algorithm is similarly applied when the observed entities are represented as polylines. The difference is given by the fact that the intersection between t B and B (resp. t A and A) can be a segment line rather than just a point. However, it is worth noting that a partition of space based on two directional cones does not enable the identification of a candidate solution.

Case 4. Ternary direction relations Let us consider the case of a ternary relation using an observer-centered frame of reference [START_REF] Levinson | Frames of reference and Molyneux's question: cross-linguistic evidence[END_REF], i.e., "on the left of " or "on the right of " between two distinct entities of an identical directional cone.

If the observer identifies object A as being on the left of B, it means that he/she is in a half-space defined relatively to the location of A and B. Let t AB and t ′ AB the exterior tangents of objects A and B, and (M, -→ i , -→ j ) and (N, -→ k , -→ l ) the basis as illustrated by Figure 8. On the one hand, if "A is on the left of B", a solution is provided by the half-space such as S ternary = { -→ j < 0} .On the other hand, if "A is on the right of B", a solution is provided by the half-space such as S ternary = { -→ l < 0}. The algorithm is similar when entities A and/or B are modeled as polylines or points.

Integration of the successive results

The successive constraints can be summarized as follows:

-S dir is the space for which opposite direction constraints given relatively to the observer between two entities are satisfied. -S dir_cone is the space for which location constraints between two entities of a similar directional cone are satisfied. -S distance is the space for which distance constraints between two entities of a same cone are satisfied. -S ternary is the space for which direction constraints given relatively to two entities are satisfied.

Overall, the final solution, i.e. the areas that correspond to the possible observer's locations are given by the intersection of the solutions provided by each of these constraints. Since the geopositioning algorithm successively applies these complementary constraints, it significantly reduces the size of the solution space. Let us consider the spatial configuration given by the verbal description " I am in front of a meadow and the castle is behind me. The drawbridge is behind the castle " and illustrated by the conceptual map of figure 3. The application of the parser leads to the identification of three triplets, e.g., [meadow, in-front-of, observer], [castle, behind, observer] and [drawbridge, behind, castle]. The visibility algorithm identifies a first solution region S vis and the corresponding object candidates. Four spatial constraints emerge from the previous example and are applied to each candidate object:

the first case where entities are in opposite directional cones is applied both on pairs ("meadow", "castle") and ("meadow", "drawbridge"). -the second case where entities are in an identical cone is applied on the pair ("castle", "drawbridge"). -the third case that characterizes a distance relations between entities of a same cone is applied on the pair ("castle", "drawbridge").

Consequently, four possibles solution spaces S dir _1, S dir _2, S dir_cone and S distance emerge. The final solution is given by their intersection including the previous solution S vis (Fig. 9).

Conclusion

Early models of geopositioning processes have been widely influenced by quantitative representations of space. However, these approaches do not completely reflect the way humans perceive and describe their environment since they preferably process qualitative information. This paper introduces a method for geopositioning an observer from the verbal description of his/her surroundings. A constraint-satisfaction algorithm is applied by successively refining the candidate locations of the observer. The first case of the approach considers some visibility constraints on the entities identified in the verbal description with respect to some candidate objects of the geographical database. The second case considers direction and distance relations as spatial constraints, i.e. relative directions between entities and the observer, as well as distance relations are interpreted.

Overall the geopositioning approach provides a set of possible locations for the observer. The algorithm still deserves integration of additional spatial relations, such as non-visibility constraints that can be derived from entities and landmarks not identified by the observer, but present in the geographical database.

The approach is currently being implemented as an extension of the GvSIG software.

Fig. 1 .

 1 Fig.1. Conceptual map of a scene[START_REF] Le Yaouanc | A semantic and language-based representation of an environmental scene[END_REF]

Fig. 2 .

 2 Fig. 2. Top-level concepts of the application taxonomy

Fig. 3 .

 3 Fig. 3. Visibility principle

Fig. 4 .Fig. 5 .

 45 Fig. 4. Orientation constraint principleLet us consider two surface objects A and B (Fig.5), and P B (resp. P A ) the tangent point to B and tangent line t B (resp. t A ). In order to identify the observer location for which object B is in front of him, and object A behind, space is discretized by uniformly moving point P B (resp. P A ) along the boundary of object B (resp. A). For each location of point P B (resp. P A ), 1. Construction of tangent t B (resp. t A ). 2. Construction of the exterior tangent t A to object A (resp. t B to object B) that is also perpendicular to t B (resp. t A ) 1 .

  E back ), E C1/2 the set of combinations of entity pairs (e i , e j ) of the verbal description with e i ∈ C1 and e j ∈ C2, O C1 , O C2 , O C1/2 the corresponding set of objects and combinations of objects (o m , o n ) of the GIS, and A(o m , o n ) the solution region with o m ∈ O C1 and o n ∈ O C2 . The solution region S opposite_rel for which some objects are in a cone (e.g. front) and others in the opposite one (e.g. back) is the union of regions A(o m , o n ). When space is partitioned with four directional cones, a possible solution S dir is given by the intersection of the two sub-solutions regions that correspond to the solutions front/back and right/left.

Fig. 6 .

 6 Fig. 6. Orientation constraint (two cones)

Case 3 .Fig. 7 .

 37 Fig. 7. Distance constraint

Fig. 9 .

 9 Fig. 9. Constraint-based approach

The interior tangent is not necessary since the resulting points are included in the solution.


Jean-Marie Le Yaouanc
email: leyaouanc@ecole-navale.fr

Éric Saux
email: saux@ecole-navale.fr

Christophe Claramunt
email: claramunt@ecole-navale.fr

A salience-based approach for the modeling of landscape descriptions

Keywords: H.4 [Information Systems Applications]: Miscellaneous; I.2.7 [Artificial intelligence]: Natural Language Processing Human factors, Algorithms Spatial cognition, landscape modeling, salience

While conventional GIS maps have long been a privileged way for the integration and diffusion of geographical information, novel forms of representation and description of urban and natural environments are nowadays emerging. In particular, verbal and textual descriptions of landscapes are progressively considered as alternative modeling resources for GIS. The research presented in this paper introduces a salience-based approach whose objective is to identify the noticeable entities of a natural landscape description. The model is based on a structural analysis of a given description, where salient entities are identified at the linguistic and structural levels. Salient entities are also spatially qualified according to their relative location with respect to a given observer.

INTRODUCTION

Landscape perception encompasses cognitive principles that favor the memorization of the main properties of an environment, and potentially the communication of its salient properties to an external addressee using natural language [START_REF] Herskovits | Language and Spatial Cognition: An Interdisciplinary Study of the Prepositions in English[END_REF]. We consider the case of an observer located in a landscape, perceiving its 360 • surroundings, and who is asked to provide a description of its environment to an external addressee. The verbal description of such a natural environment should underline the salient entities that compose space, the spatial relations relating them, and the structural properties of the environment [START_REF] Tversky | How space structures language. Spatial Cognition: An Interdisciplinary Approach to Representing and Processing Spatial Knowledge[END_REF]. In a previous work, an analysis of the spatial and structural properties that emerge from such descriptions was developed [START_REF] Le Yaouanc | A semantic and language based model of landscape scenes[END_REF]. Entities in the environment are identified according to a semantic categorization, their proximity and orientation with respect to the observer. The research presented in the present paper extends this modeling approach, by identifying the salient concepts that result from a linguistic analysis of a verbal description, and a study of its spatial properties.

Salience can be informally defined as an emphasize of an element or a set of elements distinguishable from the whole [START_REF] Landragin | Taking situational factors into account when resolving anaphora: an approach based on events and salience[END_REF]. Salience is related to naturalness, i.e., the natural order of constituents in a sentence that usually reflects the natural order of the events, and to vividness, i.e., the semantics or visual properties of the entities [START_REF] Pattabhiraman | Aspects of salience in natural language generation[END_REF]. This point of view generally comes to consider as salient what is natural, simple and clear. The aim of our research is to contribute to the specification of the linguistic and spatial salience involved in scenery descriptions. The salience-based approach evaluates the authority of terms contained in sentences of a scenery description, but also the degree of spatial prominence of the related entities in the landscape. It is based on a mutually reinforced approach where the concept of salience is recursively specified. Overall, this approach provides a conceptual and spatial specification of a landscape description whose final aim is to facilitate the analysis of the described environment for its georeferencing.

The remainder of the paper is organized as follows. Section 2 presents the modeling background of our approach and a conceptual representation of an environmental scene. Section 3 develops our modeling approach of salience implemented by a mutual reinforcement algorithm, and the experimental results. Finally, section 4 draws the conclusions and outlines further work.

MODELING BACKGROUND

We have introduced a structural categorization of a landscape view based on panoramic photographs that act as a substitute of a given natural environment. Verbal descriptions of a landscape scene provide the modeling input of the approach [START_REF] Le Yaouanc | A semantic and language based model of landscape scenes[END_REF]. The structural-based model identifies the spatial, relational and semantic constructs that emerge from these descriptions. Concepts in the environment are qualified according to a semantic classification, their proximity and orientation to the observer, and the spatial relations that qualify them. The resulting model is schematized by a representation that constitutes a modeling support for the study of environmental scenes (Fig. 2). Let us consider an example of description given by the landscape presented in figure 1: "I'm on a footpath that runs along a castle and a pond. In front of me, there is a valley with the castle on the left of it and at the horizon, I can distinguish a mountain range. Behind me, there is the pond with a large meadow behind and a forest far away".

Humans tend to structure space using distance and bodily directions that relate the spatial entities to their own location. The way these distance and directional relations organize space implicitly generates a partition of space that can be modeled using proximity spaces and directional cones. We introduce a schematization approach that takes into account these principles, and whose objective is to facilitate the understanding of the spatial structures that emerge from the verbal descriptions of a natural landscape.

We define an environmental scene as the 360 • environment, perceived by an observer from a static point of view. An environmental scene that provides an observer-centered reference for the location of entities, is ordered by the boundaries of four proximity spaces, and a cone-based partition whose number can vary from two (front-back or right-left) to four (front, back, right and left).

The conceptual map of figure 2 that results from the previous example clearly makes the difference between the space in front and behind the observer. This example shows evidence of a close relationship between the sentences and the location of the entities described.

Such a model qualifies and characterizes natural landscapes, and provides a framework for the analysis of the properties of verbal descriptions made by different observers, and crosscomparisons of different landscape descriptions. However, the salient entities of the scene are not always clearly revealed by the resulting conceptual map. This motivates an extension and analysis of the semantic and structural properties of the entities identified in the scenery.

SALIENCE COMPUTATION

The salience-based model integrates the properties of the linguistic description, and the structural characteristics of an environmental scene. Salience should reflect the particularities of the entities that result from a scenery description such as their linguistic properties, i.e., the richness of information associated to each term, and their structural characteristics, i.e., their degree of spatial isolation. We introduce a bipartite and oriented graph representation of a verbal description, where vertices represent sentences, entities, and cones, and edges the relations between them (Fig. 3). That graph supports a mutual reinforcement algorithm that derives the linguistic and spatial salience scores associated to each entity, sentence and directional cone of the environmental scene.

Linguistic salience

Early research in Natural Language Processing, i.e., automatic text retrieval and automatic summarization has largely raised the issues of salience related to the formal content and semantics of the data, focussing on recency and repetition [START_REF] Pattabhiraman | Aspects of salience in natural language generation[END_REF][START_REF] Hajicová | Issues of sentence structure and discourse patterns, volume 2 of Theoretical and Computational Linguistics[END_REF]. Recency is a relevant characteristic when scoring the importance of terms in documents, whether textual or verbal. Recency is based on the assumption that the more entities are recently quoted, the more they are salient [START_REF] Salton | Term weighting approaches in automatic text retrieval[END_REF]. This syntactic salience is related to the appearance order of the terms in each sentence. The number of occurrences of a term should also be considered as a relevant information for salience quantification. This assumption is based on the fact that a term mentioned more often than the others should receive a higher salience score [START_REF] Spärck | A statistical interpretation of term specificity and its application in retrieval[END_REF]. We consider that the informative value of a short sentence is higher than the one of a long sentence that should have the default of drowning information. A sentence containing few entities should then be more salient than the others. The algorithm is defined as "a salient entity is an entity that occurs in a lot of sentences and a salient sentence is a sentence that contains few, but salient entities". Consequently, the more entities there are in the sentence, the lesser the score of each entity. Since the entity with the highest authority usually influences and structures the sentence, the score of each sentence is weighted by the highest entity authority.

Let N be the number of sentences of the verbal description, and nj the number of entities in sentence sj, then ∀ej, ling entity (ej, 0) = 1, ∀si, ling sentence (si, 0) = 1.

∀ei, k ≥ 1, ling entity (ei, k) = N X j=1 s j e i ling sentence(sj , k -1). ∀si, k ≥ 1, ling sentence (si, k) = 1 P n i j=1 e j ∈s i ling entity (tj, k) * M ax(ling entity (ej, k)).
Considering that the recency score of each entity ei exponentially decreases with the total number of entities of the description, the recency of each term is given by

Recency(ti) = exp -λ * Card(E)-Index of t i E , λ ∈ R.
The resulting linguistic score ling entity of each entity ei is then given by ∀ei, ling entity (ei, k) = N X j=1 s j e i ling sentence (sj, k -1) * Recency(ei).

Spatial salience

Salient entities constitute a reference for the orientation and the description of an environmental scene [START_REF] Lynch | The Image of the City[END_REF]. The study of visual salience generally begins by physiological considerations, resulting from the perception of specific entities that are identified by their physical characteristics, ontological categories, and spatial location, i.e., their isolation or membership to a group that makes them salient [START_REF] Winter | Route adaptive selection of salient feature[END_REF].

The salience of an entity is intrinsically linked to the environmental context in which it is embedded in [START_REF] Edmonds | A computational model of collaboration on reference in direction-giving dialogues[END_REF]. An entity is particularly considered as salient when it is spatially isolated from other entities. The spatial isolation of an entity is calculated on the basis of the directional cones that structure an environmental scene. We consider that a salient entity is an entity that occurs in a lot of salient cones, and a salient cone is made up of few, but salient entities. Consequently, the more entities there are in the cone, the lesser the score of each entity. Since the term with the highest authority usually structures the cone, the score of each cone is weighted by the highest term authority.

The computational model of spatial salience is valued by two functions, struc cone(ci, k) that values the score of a cone ci, and struc entity (ej, k) that values the score of an entity ej, with k the index of the iteration. Let Nc be the number of cones of the conceptual map, and nj the number of entities in cone cj , then ∀ci, struc cone(ci, 0) = 1, ∀ej, struc entity (ej, 0

) = 1. ∀ei, k ≥ 1, struc entity (ei, k) = Nc X j=1 c j e i struc cone(cj , k -1). ∀ci, k ≥ 1, struc cone(ci, k) = 1 P n i j=1 e j ∈c i struc entity (ej, k) * M ax(struc entity (ej, k)).
The spatial isolation of an entity can also be calculated relatively to the proximity spaces. The algorithm is then enriched by the fact that "a salient proximity space is a space that contains few, but salient entities".

Experimental results

Let us consider the example of description introduced in section 2. Figure 4 shows the computation of the algorithm that evaluates the linguistic salience of the entities, ling entity . Entities "pond" and "castle" that are the only ones quoted twice in the verbal description are the most salient. As a result, their significant score affects the sentences in which they are, and particularly the first sentence that is composed of both entities. Consequently, sentence one that obtains the lowest score influences the score of the last entity of the sentence, i.e. "footpath". Finally, sentences two and three are both composed of one salient entity, respectively "castle" and "pond", and two other entities that are only quoted one time in the verbal description. These two last sentences get the same structure, and do not really influence entities "valley", "mountain range", "meadow", and "forest" that obtain a middle salience score.

CONCLUSION

The preliminary research presented in this paper introduces a salience-based approach of a verbal description of a natural landscape. The model is qualified by the linguistic and spatial measures of salience that characterize both verbal descriptions and natural landscapes, and provide a framework for the analysis of their properties. This approach reflects the main structure of a natural scenery perceived by an observer possibly lost in a natural environment, but also its Further work will be oriented toward an extension of the approach using ontological attributes for the characterization of entities, and a mapping of these conceptual maps towards a GIS representation in order to locate a given observer. The objective is to bridge the gap between the resulting conceptual map that identifies the salient entities and spatial relations, and locations within a scenery.

Figure 1 :

 1 Figure 1: Natural landscape of a mountainous region -scenery 1

Figure 2 :

 2 Figure 2: Conceptual map -scenery 1

Figure 3 :

 3 Figure 3: Graph representation -scenery 1

Let

  S be the set of sentences composing a verbal description, D the set of verbal descriptions, U the set of elementary units composing a sentence, E the set of entities of an environmental and R the set of spatial relations including the null element ∅. A verbal description D is modeled as an ordered set of sentences si ∈ S, i.e., D = [s1, s2, . . . , sN ] where D ∈ D and N ≥ 1. A sentence si is an ordered set of elementary units ui ∈ U, i.e., ∀i ∈ [1, . . . , M ] with M ≥ N, si = [u1, u2, . . . , uM ]. An elementary unit ui is a triplet such as ui = [ej , r k , e l ] with ej, e l ∈ E , and r k ∈ R. The computational model of linguistic salience is valued by two functions, ling sentence (si, k) that values the score of a sentence si, and ling entity (ej, k) that values the authority score of an entity ej, with k the index of the iteration.

Figure 4 :Figure 5

 45 Figure 4: Linguistic salience of entities

Figure 5 :

 5 Figure 5: Spatial salience of entities