Guillaume Touya

Lessons Learned From Research on Multimedia Summarization

Introduction

Map generalization is often is often considered as a cognitive task similar to text summary. Like text summary, generalization seeks to reduce the level of detail of initial data, highlighting the important features regarding a given need, and preserving the main characteristics of the initial data [START_REF] Ruas | Généralisation et représentation multiple[END_REF]. The automation of text summarization is key research topic for language processing scientists, and it should be interesting to verify if the similarities in the human cognitive process lead to similarities in the automation techniques.

Moreover, text summarization is a part of the multimedia summarization problem that also includes video and music summarization, and this complete literature is interesting to review. The aim of the paper is also to identify some guidelines for further map generalization research that can be derived from the multimedia summarization research community. This paper first identifies similarities and differences in both automation problems. Then, section 3 proposes ideas from multimedia summarization that could be beneficial for the map generalization community. Finally, the paper is concluded with some ideas for further research opportunities.

Similarities and Differences between Both Problems

Exhaustive reviews of techniques have been published for text summarization [START_REF] Mani | Advances in Automatic Text Summarization[END_REF][START_REF] Das | A survey on automatic text summarization[END_REF], video summarization [START_REF] Truong | Video abstraction: A systematic review and classification[END_REF], or music summarization [START_REF] Peeters | Deriving musical structures from signal analysis for music audio summary generation: "sequence" and "state" approach[END_REF][START_REF] Jun | Music segmentation and summarization based on self-similarity matrix[END_REF], to go into more details. Some of these techniques are presented here only to illustrate the similarities and differences between summarization and generalization. First, map generalization and text summarization are complex cognitive tasks that do not have any exact perfect solution. Different human cartographers may create different generalized maps from the same geographic data that can be considered as good. Similarly, human summarizers do not agree with each other with a same document and same rules to guide them. In both cases, it has been noted that the lack of metrics to globally evaluate a solution illustrates the difficulty of the task [START_REF] Das | A survey on automatic text summarization[END_REF], Stöter et al 2014). Most summarization techniques are based on the selection of the most important sentences in the document, which are extracted to create the summary. For instance, the seminal proposition from [START_REF] Luhn | The automatic creation of literature abstracts[END_REF] analysed the frequency of words and the position of sentences to extract the key sentences (Figure 1). The same mechanisms clearly drive the selection operation in map generalization [START_REF] Mcmaster | Generalization in Digital Cartography[END_REF]. So we should be able to use in selection processes some methods defined for text extraction. Furthermore, context is fundamental in both map generalization and summarization, as it helps brain to build the comprehension of the map or the text. An isolated building and a building in a dense city are not considered similarly in generalization, and in the sentence below, only the context of the preceding sentence helps to understand what "the hat" is [START_REF] Mckeown | Generating summaries of multiple news articles[END_REF].

Bob got a new Stetson. He loves the hat.

Enriching the initial cartographic data with implicit structures and patterns is essential in generalization in order to preserve or abstract the structures in the generalization process [START_REF] Mackaness | The importance of modelling pattern and structure in automated map generalisation[END_REF]. Text summarization has the same requirements, has grammatical structure is a key to text meaning. Thus, some text summarization methods first analyse the grammatical structures of sentences (Figure 2) before abstracting the document into a summary [START_REF] Mckeown | Towards multidocument summarization by reformulation: Progress and prospects[END_REF]. Other methods first classify the document to summarize into well-known sequences, such as verses and choruses in songs (Figure 3), prior to the summarization. Then, for instance, only one verse and one chorus are kept [START_REF] Peeters | Deriving musical structures from signal analysis for music audio summary generation: "sequence" and "state" approach[END_REF]. For instance, this can be seen as analogous to the classification of urban blocks in [START_REF] Gaffuri | Role of urban patterns for building generalisation: An application of AGENT[END_REF]) in order to use different AGENT parameters for each type of block. Added to that, many summarization methods use multiple document as input, for instance to summarize news using all the existing news channels, and their different point of view on an event. This process can be seen as similar to the conflation process required to make mashup maps out of several sources of geographical data. Despite these similarities, the automatic processes of map generalization and multimedia summarization are very different. The main difference lies in the nature of the input data. Vector geographical data requires computational geometry techniques to deal with two or three dimensions data, while text (one dimension) requires natural language processes and videos require image processing techniques. The need for generalization mainly derives from the legibility, or eye perception problems caused by scale reduction, so the generalization processes mainly seek to derive legible maps, where eyes are able to distinguish all details; keeping the main features of the map is only one of the objectives. Text summary has no such constraint, and only aims at the optimal number of words to grasp the meaning of a text. So, the multimedia summarization processes can only be compared to the selection processes in map generalization.

What Can Be Learned for Map Generalization Research

This short review and the differences highlighted in section 2 show that multimedia summarization techniques cannot directly be applied to map generalization. However, some lessons can be learned from this research domain, and some are presented in this section.

A Massive Use of Machine Learning

Although the machine learning techniques have been tested to automate generalization (e.g. [START_REF] Weibel | Overcoming the knowledge acquisition bottleneck in map generalization: The role of interactive systems and computational intelligence[END_REF][START_REF] Mustière | Abstraction-Based machine learning approach to cartographic generalisation[END_REF][START_REF] Kilpelainen | Knowledge acquisition for generalization rules[END_REF][START_REF] Burghardt | Automated sequencing of generalisation services based on collaborative filtering[END_REF]), it appears that this technique has been under-used when compared to the diversity of learning techniques used in text summarization [START_REF] Das | A survey on automatic text summarization[END_REF]. For instance, the orchestration and the parametrization of generalization processes is one of the main difficulties remaining in generalization research, but is it possible to learn in already generalized maps how to guide the orchestration, or the parametrization of algorithms? [START_REF] Taillandier | Automatic revision of rules used to guide the generalisation process in systems based on a trial and error strategy[END_REF] used learning similarly to optimize the parametrization of the AGENT generalization model, but this could be made in a broader way. I believe that the community needs to look once again at the machine learning research, to see if their recent outcomes could help us (e.g. LeCun et al 2015).

The Notions of Importance and Redundancy

The parallel between text extraction and the selection operation highlighted in section 2 make the criteria used in text extraction interesting to study. Importance and redundancy are two key notions in the text extraction methods. Several proposals exist to infer importance and redundancy of words or expressions, and could be transferred through analogies to map generalization. [START_REF] Mackaness | The role of geography in automated generalisation[END_REF] pleaded for a better consideration of geographic saliency in map generalization, and such analogies could help us to do so. Road selection processes are an interesting case study for highlighting the usefulness of the notion of redundancy. Most main contributions in the domain tried to identify the main roads with graph theory based methods, and/or Gestalt based methods, and provide quite satisfying results. But thinking the other way round, i.e. removing the roads identified as redundant, would maybe improve the existing methods (Figure 5).

A Major Focus on Evaluation

The generalization research community has clearly neglected the evaluation step compared to the number of papers regarding algorithms for instance, and recent papers highlighted this lack of major contribution (Stöter et al 2014, [START_REF] Mackaness | The role of geography in automated generalisation[END_REF]. On the contrary, multimedia summarization research significantly focused on evaluation protocols, with standards for manual and automatic evaluation, and many metrics to evaluate a summary and compare alternative methods [START_REF] Lin | Rouge: A package for automatic evaluation of summaries[END_REF]). The agreement on standards to evaluate a text summary in comparison to one or several references greatly helped the development of automatic summarization techniques. I believe that the research presented in Stöter et al (2014) should pushed further and that the community should make similar agreements for standardizing the evaluation of automatic generalization, with for instance a standard set of constraints to satisfy to maximize legibility and a set of metrics to assess global readability.

Benchmarks to Allow Reproducible Science

Reproducible science is a key factor of scientific thinking [START_REF] Peng | Reproducible research in computational science[END_REF], as it allows scientists to compare each other methods with reproducible experiments. In map generalization, sharing algorithms in a web platform, such as the web services framework proposed in [START_REF] Foerster | Towards an interoperable web generalisation services framework -current work in progress[END_REF], would help comparing algorithms to each other. In order to promote reproducible science, to compare the large number of proposed methods, and also to provide datasets to academic researchers, the text summarization community soon organized workshops to develop evaluation competitions [START_REF] Das | A survey on automatic text summarization[END_REF]. TREC1 , DUC2 and MUC3 promoted evaluation baselines on chosen training datasets. For instance, guidelines for manual evaluation of summaries have been defined with such initiatives [START_REF] Lin | Manual and automatic evaluation of summaries[END_REF], and the same could be made for generalization benefiting from the knowledge of the cartographers working in the national mapping agencies. The need for such standard has been recently acknowledged by Stöter et al (2014). As mentioned earlier, such as generalization, there is not a unique good solution to multimedia summarization problems, but several. Text summarization benchmarks evolved to propose now several acceptable summaries for training texts, and this diversity of solutions is used by evaluation systems [START_REF] Lin | Rouge: A package for automatic evaluation of summaries[END_REF]). The EuroSDR project on the state-of-the-art of commercial software in generalization was a first step to the creation of benchmark datasets with sets of constraints related to each of the four datasets (Stöter et al 2010). We should now go further by providing open datasets with sets of constraints to satisfy, good results, and existing processes to compare to. The recent research on sharing the generalization knowledge in ontologies (Gould et al 2014) is also a step forward.

Conclusion

Although texts and maps are different kinds of information, the cognitive processes of summarization and generalization are similar. So it is interesting for the generalization research community to learn from the research on text/multimedia summarization. The main feedbacks are the under-use of machine learning in generalization, the lack for importance, saliency and redundancy definitions, the lack of focus on generalization evaluation, and finally the importance of benchmarks to allow reproducible research. Although the techniques used in multimedia summarization cannot be directly used in map generalization, I believe that generalization researchers should regularly review the summarization community outcomes in order to integrate major trends. More generally, the effort presented in this paper of reviewing a new field of science and relating it to map generalization could be done for other interesting domains. For instance, the research on visual search, tries to understand the mechanics the brain uses to optimize visual search (see Eckstein 2011 for a review). It would be useful to understand how the brain searches information in a map to better generalize it.

Figure 1 .

 1 Figure 1. Example of sentence extraction to derive an abstract from a newspaper article (Luhn 1958).

Figure 2 .

 2 Figure 2. Dependency tree structuring the sentence "McVeigh, 27, was charged with the bombing", example from (McKeown et al 1999).

Figure 3 .

 3 Figure 3. Characteristic sequences in the song "Smell Like Teen Spirit" from Nirvana, detected by the Peeters algorithm (2004).

  Finally, generalization seeks to convey more the geography behind the data, and its implicit spatial relations and structures, than to convey the precise positioning of objects. As a consequence, exaggeration operations (McMaster & Shea 1992) such as typification, dilatation, or parallelism enhancement are quite common in generalization (Figure4), while summaries remain faithful to the original source data. Nevertheless, this difference is slightly modified when text summary is less literal, and seeks to highlight the important aspects of a text like map caricature[START_REF] Mckeown | Towards multidocument summarization by reformulation: Progress and prospects[END_REF].

Figure 4 .

 4 Figure 4. Examples of caricature and exaggeration operations in generalization that cannot be related to summarization operations.

Figure 5 .

 5 Figure 5. Three redundant roads in a network as they provide neither shortcut nor additional connectivity.

http://trec.nist.gov

http://duc.nist.gov

http://www-nlpir.nist.gov/related_projects/muc/proceedings/muc_7_toc.html

Acknowledgments

I would like to thank the anonymous reviewer for his/her valuable comments.


Sandro Savino

Guillaume Touya

Automatic Structure Detection and Generalization of Railway Networks

Keywords: railway network, generalization, structures, strokes, Open-StreetMap

Unlike road or river networks, railway networks automatic generalization are missing to properly handle the detailed networks provided in current geo-datasets like OpenStreetMap. This paper proposes automatic methods to automatically identify key structures of railway networks, such as parallel main tracks, or fan and pack patterns inside large train stations. Then, algorithms based on the detected structures are proposed to generalize the railway networks. The algorithms are tested on real datasets, including OpenStreetMap data.

Introduction

As long as they were simply integrated into geographical databases, railway networks were quite easy to include in automated mapping systems: the networks were not very dense and the shapes were mostly straight so map generalization was easy. But railway networks are more and more modeled in a realistic ways, capturing in datasets all the tracks of the networks, such as OpenStreetMap requires for instance [START_REF] Touya | Generalising unusual map themes from Open-StreetMap[END_REF]. In order to include these complex railway networks into small scale maps, specific map generalization algorithms are necessary. The automatic generalization of geographical networks (e.g. roads, rivers…) has been tackled many times due to the importance on such features in maps, and more generally, in geographical datasets (Thomson & Brooks 2007[START_REF] Stanislawski | Generalisation of geographic networks[END_REF]). However, there has been very little focus on railway networks generalization [START_REF] Touya | Generalising unusual map themes from Open-StreetMap[END_REF]. Although some techniques extracted from previous work, like 'strokes' can be applied to the generali-zation of railway networks, algorithms dedicated to their specific geographical structures need to be developed. This paper proposes such dedicated techniques to identify the main structures of railway networks, and to generalize the network and its structures.

Section 2 deals with the modeling of railway network structures and their automatic detection in datasets where each track is captured. Section 3 describes new algorithms to generalize railway networks. Experiments on several real datasets are presented in section 4. Finally, section 5 draws some conclusions and proposes further research.

Modeling Railway Networks

Modeling Railway Networks as Complex Objects

Inspecting railway networks quickly shows that they are composed of two very different parts: there are mostly tracks where trains run, composed by one or more lines running parallel, and areas where trains stop, as a train yard or a train station, composed by a big number of tracks crossing, diverging and stopping (Figure 1). Generalization-wise, this distinction is not that sharp: main tracks are not very different from small train stations as they both are composed of parallel lines; big stations instead, are very different, because of the very big number of tracks, patterns and structures in them, requiring to use different techniques be generalized. In this paper, we will split the railroad network in main tracks and sidetrack areas: the first object corresponds to small groups of parallel tracks, pre-sent in train lines and small stations while the latter corresponds to big groups of tracks, present in stations or train yards. Each object is separately modeled as it will require specific generalization; a method to automatically differentiate main tracks from sidetracks is proposed in Section 2.2. When multiple parallel railway tracks are abstracted into a single railway route in most classical geographic datasets, highly detailed railway networks contain each track represented as a line. The standard distance between two parallel tracks is less than 10 meters, which does not allow the display of all these parallel tracks in most cartographic representations. In order to abstract parallel tracks as a single railway route, we propose to model railway main tracks into Parallel Rails Groups (Figure 3). This model is firstly based on the computation of strokes, i.e. perceptual complex entities that gather tracks that follow each other like a pen stroke [START_REF] Thomson | The "good continuation" principle of perceptual organization applied to the generalization of road networks[END_REF]. Strokes are commonly used to identify salient routes in geographical networks (Thomson & Brooks 2007). A Parallel Rails Group is composed of a center stroke to which parallel smaller strokes are aggregated. The way parallelism ends between a parallel stroke and its central stroke is also identified with three types of endings: converging points (i.e. points where two parallel tracks meet), diverging points (i.e. points where two parallel tracks follow different directions), and dangling points (Figure 4). A position number is associated to each parallel stroke: 1 means that the stroke is directly on the right of the center stroke, 2 means that the stroke is on the right of a parallel stroke with a position of 1, -1 means that the stroke is on the left of the center stroke, etc. The structure of the network changes dramatically in the surrounding of a train yard or a train station: the tracks composing the main line split in different directions and are sided by multiple parallel tracks (see zoomed areas in Figure 1); tracks can converge, diverge, cross each other and also stop in a dead end. We call such a group of tracks a sidetrack group. It's important to note that main tracks are interrupted by the presence of a sidetrack group: due to the complexity of the line work inside these structures, it is often not possible to identify a single track or stroke entering and exiting the sidetrack group. Different characteristic structures can be identified in a sidetrack group (Figure 5):

 tracks diverging from a group of switches, running parallel and then converging in another group of switches,  dead ends, where multiple parallel tracks are used to store freight cars,  switch groups, where many tracks meet and cross each other.

Sidetrack groups capture important feature of the rail network (e.g. a logistic center, a major train station) and represent a characteristic that should be preserved in the generalized data; their large number of tracks (up to hundreds) makes them a prominent feature of the network but at the same time makes them very hard to generalize. In order to succeed, it is necessary to reduce the complexity of the generalization task by identifying some objects into which to decompose each group.

The objects described before are well defined, independent one from each other and they are present, in different size and numbers, in every big station. In our strategy we decided then to model sidetrack groups as composed by packs, fans and free tracks. The UML class diagram in Figure 6 shows the relation between these components, while section 2.3 will describe further each of them.

Automatic Detection of Main Tracks and Sidetracks

The most prominent difference between main tracks and sidetracks is the amount of tracks that compose each one. The differentiation technique implemented draws a line segment for each track, placed in the middle of it and orthogonal to its direction. The algorithm then counts how many tracks each segment crosses.

If the number of crosses is above a threshold, the track is candidate to be part of a sidetrack group. Candidates are then clustered by proximity: if a cluster of candidates is composed by only a few tracks, it does not qualify as a sidetrack group and its tracks are flagged as main tracks. The thresh-olds were chosen experimentally and were set to 60 meters for the segment length, and 10 for the cluster group number. Once the group of tracks composing a sidetrack group has been identified, the main tracks connecting the rail network to the group are flagged as in-out tracks.

Automatic Structure Detection

Parallel Railway Groups

The first step of the detection process is to compute strokes within the main tracks. Then, strokes are ordered regarding their length, and the longest one is used as the first center stroke for a new parallel railway group. Then, the remaining strokes that are within a 10 meter proximity area (computed with a dilatation operator) for a significant distance (empirically set to 100 m) are considered as parallel strokes. Then, strokes parallel to each of the new parallel strokes are searched recursively. Once parallel railway groups have been identified, the types of parallelism endings are characterized for each parallel track, in order to ease the reconnections after the collapse of the parallel tracks (see section 3.1). When the parallel geometries intersect, it is a converging point, when they do not intersect but always stay within the minimum distance, it is a dangling point, and when the parallel geometry leaves the minimum distance area, it is a diverging point. A final step checks if the collapse altered the connections between the selected railway routes. Figure 8 shows a case where the connection between two railway routes is made only with the parallel track, and once this track is removed, the connection is lost. In such cases, the lost connections are restored by extending the lines to the nearest selected railway. The parallel railway groups detection is not carried out on tracks that are part of a sidetrack group because such tracks are characterized, and then generalized differently (see next sections).

Figure 8. The connection between the railway lines is not between the center strokes so the removal of the parallel stroke alters the connection.

Detection of Structures inside Sidetrack Groups

The most important structures in a sidetrack group are packs and fans. Tracks belonging to a sidetrack group that are neither part of a fan nor of a pack, are classified as cluster tracks or free tracks.

Fans are basically formed by dead end tracks; what differs them from standard dangling edges is the fact that they are formed by groups of parallel, evenly spaced tracks that merge into each other (usually two by two), forming a comb or tree like structure with many branches. The detection algorithm developed is able to detect the whole tree structure up to the stem by walking the network starting from the dangling edges, and giving a score to each track visited. The score of each edge is a function of the score of the edges surrounding it; a dangling edge has a score of 100, his children have 50; if the value of an edge is 100, it becomes part of the fan and can propagate the selection to his children. At the end of the process, all edges having score of 100 are flagged as fan tracks.

Since fans are a "local" structure, a length threshold is used to stop the propagation on long tracks (the threshold was set to 100 meters). Once the process is finished, the tracks flagged as fan track are grouped into fans by clustering them on proximity (Figure 9).

Another very important structure in sidetrack groups are packs. Packs have some trait in common with fans, as they both are a group of parallel tracks stemming from the same area of the network, but they do not branch and, very important, they converge to another part of the network. The edges composing a pack are called r-edges, as redundant edges, because they form a link between two areas of the network that are connected by many tracks. A pack is composed of all the tracks that connect the same two areas of the network. Generalization-wise, redundant edges are very important to detect as they are good candidates for selection since they can be eliminated without altering the connectivity of the network [START_REF] Wiley | Data enrichment for road generalization through analysis of morphology in the CARGEN project[END_REF]. To detect r-edges it is necessary first to cluster the nodes of the network: these clusters are useful to find those areas where the tracks of a pack converge. Clustering is performed on proximity and connection: two nodes are in the same cluster if they are closer than a threshold and they are directly connected by an edge. A unique identifier is assigned to each cluster and to each node that is not part of any cluster. The algorithm then calculates a connection code for each edge of the network: this code uniquely identifies the two nodes connected by each edge; the code is based on the identifier of each node or, if a node is part of a cluster, on the identifier of the cluster the node belongs to. Finally, the packs are created by grouping the edges by their connection code (Figure 10).The edges that connect two nodes that are part of the same cluster are flagged as cluster tracks: these tracks represent switch groups and play an important role in the topology of the network as they usually link packs connecting different clusters.

All the edges that are not part of fans or packs or are not cluster tracks, are classified as free tracks. These tracks cannot be further characterized: they have different direction and length and they roam "freely" between the other structures defined above. These tracks also play an important role in a sidetrack group as they connect all the different structures together.

Algorithms to Generalize Railway Networks

Parallel Railway Tracks Collapse

Touya & Girres ( 2014) proposed an algorithm to collapse two parallel tracks into a center track that handles converging and diverging endpoints. So, when parallel tracks groups contain only two railway strokes, it can be used to collapse the group. However, Section 2 showed that parallel tracks groups are often composed of more than two parallel tracks, and the collapse algorithm cannot be directly extended to collapse more than two tracks. The proposed collapse algorithm is based on the parallel tracks group model described in the previous section. Only the railway tracks that belong to the center stroke are kept, and all parallel tracks are eliminated, while diverging tracks are reconnected to the center stroke (Figure 11). The diverging points of parallel tracks do not necessarily correspond to the extremity of a track feature geometry, so the geometry are cut to only keep the diverging part. Then, the first (or last) segment of the remaining geometry is extended to snap to the center stroke, which preserves the divergence angle, and avoids unnatural connections. Once parallel tracks have been collapsed, classical stroke-based selection algorithms can be applied to select only the important railway strokes (Thomson & Brooks 2007).

Sidetrack Groups Typification

Because of the different type of tracks that are present in a sidetrack group, it is difficult to find a generalization technique able to handle all the existing situations. In our approach we manage to generalize sidetrack groups by decomposing them in the previously described structures.

The strategy that we devised to generalize sidetrack groups is quite simple: each single structure is generalized independently and the final result is obtained by connecting every generalized structure to the network. As a design choice, the generalization is performed using only the selection operator; this limits the need to recreate the connectivity among the generalized features; on the other hand, it also poses some constraints on the shape of the resulting network. The first structures to be generalized are packs and fans. The most prominent characteristic of packs and fans is the parallelism of their tracks: the typification algorithm developed uses this characteristic to both select the tracks and maintain their initial pattern.

The algorithm calculates the direction of the group of tracks and then traces a line, orthogonal to the direction and centered on the centroid of the group; the intersection points between each track and this line are calculated: these points are used to measure the width of the group and calculate, on the base of the required minimum distance between tracks, which tracks should be selected (Figure 12). Analyzing the distance between the intersection points, the algorithm is able also to detect whether the tracks are regularly spaced or they can be clustered in sub-groups: in the latter case, selection is applied to every single sub-group. This typification technique is used to generalize packs; because of the treelike structure, though, it cannot be applied directly to fans: not all the fan edges have the same direction, and not all the fan edges would intersect the orthogonal line. For these reasons, the selection algorithm is applied only to the dangling edges of a fan; after the selection a special routine deletes all the fan tracks that are not needed anymore because they end up in a dangling edge that has been removed (Figure 13). Most of the packs are connected to cluster of nodes: after r-edges have been selected, cluster tracks are generalized accordingly, removing those tracks that are connected to redundant edges that have been deleted. The final part of the process is the generalization of free tracks. Once they are separated from the other structures, free tracks, to some extent, resemble a main track and they can be both generalized using a similar stroke-based technique. To create the strokes, cluster tracks are added to the free tracks, in order to restore the connectivity in the areas where a stroke passes through a cluster. Furthermore, the in-out tracks (i.e. the edges of the main tracks connected to the sidetrack group) are also added to the set of edges that are used to create the strokes. The strokes are then generalized by detecting those too short and those too close to other strokes and either removing them or collapsing the shorter ones in the longer ones, with the collapse technique proposed for main tracks. Once the strokes have been generated and the free tracks generalized, the connection between the structures and the free tracks is restored; as a last step, cluster tracks that are not used are removed, together with single dangling edges that did not qualify as fan.

Experiments

Experiments have been carried out on two types of highly detailed railway networks: one depicting a whole French region (30,000 km²) was extracted from OpenStreetMap, and the other depicts an Italian region (18,000 km²) and was extracted from the regional database produced by the local gov-ernment of the region of Venezia. Both datasets contain a big variety of data: small railroads composed by single lines, bigger lines composed by more tracks running parallel, small, medium and very big train stations.

Figure 14 shows some results of the main tracks collapse into one single track. The algorithm performs well on all types of parallelism endings and is able to quickly collapse large datasets. In Figure 15, Figure 16 and Figure 17 the results of our generalization algorithm applied to some stations of different complexity are shown. Packs are represented in blue, fans in yellow, free tracks in red, cluster edges in black, and the edges added to reconstruct the connectivity in green. In general, the tests show that our algorithm performs well in detecting the different structures composing the network and, by dividing the problem in smaller generalization tasks, is able to handle also very complex stations. From the topological point of view, our algorithm guarantees that the generalized data is correct as no connectivity is lost due to the edge removal. The quality of the generalized data is in general good but leaves space to some improvements. In packs and fans, the use of selection as the main generalization operator, constrains the possible solutions for the typification of the tracks. Despite the ability of the algorithm to detect and handle patterns in the input, due to the layout of the original tracks the output can still present tracks that do not respect the minimum distance threshold. The typification technique adopted, however, makes it easy to compute displacement vectors that can be used to obtain a more uniform distribution of the generalized tracks.

In order to evaluate our proposals, the sidetracks generalization is compared to the algorithm proposed by [START_REF] Touya | Generalising unusual map themes from Open-StreetMap[END_REF]. Figure 18 shows some results on the big station in the Venezia area: the typification is good because the density decreased while the general pattern is preserved. However, the specific patterns of fans and packs are altered by this algorithm, with particularly some local loss of connections. This proves the need for an algorithm that handles such structures.

Conclusion

This paper presented an exhaustive approach for the generalization of large scale railroad networks. The input data is divided in two categories: parallel main tracks and sidetrack groups, i.e. train stations, composed by up to hundreds of tracks. The paper proposes for each of these objects a model, identifying for each object its components or structures that can be detected using automatic spatial analysis techniques. The paper also proposes generalization algorithm based on the previously detected structures.

To go further, we believe that most of the proposed algorithm, for detection and generalization, can be improved. For instance, regarding the generalization of neighboring packs, since packs are generalized independently, there is no guarantee that the generalized edges will respect the minimum distance threshold across different packs. This is also true for free tracks near packs or running between two of them.Testing them on more datasets will help identifying particular cases where the algorithms do not perform as intended. There is also a need for a displacement/deformation operator to move the remaining tracks inside a station or a triage area apart [START_REF] Bader | Building displacement over a ductile truss[END_REF]. Such an operator would allow the reduction of the selection that can be too drastic.

Figure 1 .

 1 Figure 1. Railway network extracted from OpenStreetMap: it is mainly composed of main tracks with spare sidetrack areas.

Figure 2 .

 2 Figure 2. Number of tracks and patterns in train stations can vary dramatically: this requires a flexible algorithm able to cope with the different complexity.

Figure 3 .

 3 Figure 3. UML class diagram of railway main tracks modeled as complex objects.

Figure 4 .

 4 Figure 4. Three types of parallelism endings inside parallel railway groups.

Figure 5 .

 5 Figure 5. Structures that can be recognized in a train station.

Figure 6 .

 6 Figure 6. UML Class diagram of the sidetrack group model and its components.

Figure 7 .

 7 Figure 7. parallel railway tracks that are automatically groups around the longest stroke (in red).

Figure 9 .

 9 Figure 9. Detection of fan edges (above, in orange) and grouping of fan edges in fans (below, each color represent a different fan). Dashed lines represent fan tracks that have been filtered out and classified as single dangling edges.

Figure 10 .

 10 Figure 10. Detection of r-edges (in blue) and their grouping in packs (below, each color represents a different pack).

Figure 11 .

 11 Figure 11. The collapse of parallel tracks group: only the center track is kept and diverging tracks are reconnected.

Figure 12 .

 12 Figure 12. Pack generalization: a line orthogonal to the pack (left, in red) is used to characterize the pack and to select the tracks to keep (right, in blue).

Figure 13 .

 13 Figure 13. Fan generalization: same as packs, but applied to dangling edges (left, in purple); the edges connecting the deleted dangling edges are removed.

Figure 14 .

 14 Figure 14. Two examples of parallel main tracks from OpenStreetMap collapsed into one with reconnections.

Figure 15 .

 15 Figure 15. Generalization of a train station of medium complexity (input data above, generalized data below).

Figure 16 .

 16 Figure 16. Generalization of a train station of little complexity (input data on the left, generalized data on the right)

Figure 17 .

 17 Figure 17. Generalization of a very complex train station.

Figure 18 .

 18 Figure 18. Results obtained on the Venezia area with the typification algorithm from (Touya & Girres 2014).