Romain Bourqui
email: bourqui@labri.fr

Helen C Purchase
email: helen.purchase@gla.ac.uk

Fabien Jourdan
email: fabien.jourdan@toulouse.inra.fr

Domain specific vs Generic Network Visualization: an evaluation with metabolic networks

Keywords: Metabolic networks, evaluation, graph drawing, bioinformatics

Metabolic networks have been drawn manually for many years, and over time have developed representational conventions that make them familiar to biologists. With increasing current biological discoveries, these networks need to be frequently updated and modified, and automatic visualization algorithms are thus becoming a necessity. Many existing automatic graph layout algorithms exist, and it is not known whether such generic algorithms are sufficiently useful for biologists, or whether algorithms that specifically consider the existing representational conventions are necessary. No prior task efficiency evaluation studies have been performed on biological network visualizations. This paper reports on an experiment comparing the task efficiency of biologically relevant motif-search tasks using three layouts, two of which were produced using existing generic graph layout algorithms (Force Directed, Hierarchical), and one which was specifically designed to take existing metabolic representation conventions into account (MetaViz). Despite the search task favouring the easy identification of node connectivity in the Force Directed layout, the results showed no efficiency difference between Force Directed and MetaViz. We conclude that embodying the representational conventions in an automatic algorithm is not an impediment to task efficiency, and that some minor improvements to MetaViz would enhance its usefulness for biologists even further. .

Introduction

Motivation

Providing a helpful visualization tool in biology often requires finding a balance between usability and user expectations in terms of representational conventions. As in other fields, (e.g. integrated circuits (VLSI)), biologists have over many years defined representational constraints for biological network drawings [START_REF] Michal | On representation of metabolic pathways[END_REF]. For instance, in Figure 1 [START_REF] Michal | On representation of metabolic pathways[END_REF], Gerhard Michel (who is best known for his wall chart of biochemical pathways [START_REF] Michal | Biochemical Pathways[END_REF]) defined some appropriate representational constraints and manually drew this view of a metabolic network. Representations of metabolic networks can be used to find sets of connected biochemical reactions (motifs) [START_REF] Lacroix | Motif search in graphs: application to metabolic networks[END_REF], to highlight quantitative values on nodes and edges [START_REF] Paley | The pathway tools cellular overview diagram and Omics Viewer[END_REF], or to follow metabolite fluxes. It is important to note that the representations like the one shown in Figure 1 were not designed specifically for any particular tasks.

Drawing these networks by hand has become impossible since automatic experiments and genome annotations currently generate networks containing hundreds of nodes and edges [START_REF] Karp | The ecocyc and metacyc databases[END_REF]. Biological network drawing algorithms have therefore been defined [START_REF] Becker | A Graph Layout Algorithm for Drawing Metabolic Pathways[END_REF][START_REF] Wegner | A new dynamical layout algorithm for complex biochemical reaction networks[END_REF][START_REF] Bourqui | Metabolic network visualization eliminating node redundance and preserving metabolic pathways[END_REF], in particular being designed to generate drawings in accordance with biologists' representational conventions.

Much work has also been done on the generation of visualizations of abstract networks within the graph drawing research community [START_REF] Battista | Graph Drawing Algorithms for the Visualization of Graphs[END_REF][START_REF] Kaufmann | Drawing Graphs[END_REF]. The issue addressed in this paper is whether such existing generic algorithms should be recommended to biologists for the display of metabolic networks, or whether domain-specific layout algorithms that respect the representational conventions familiar to biologists should be used instead. This is an important question: if it is the case that generic algorithms produce equivalent performance to domainspecific ones, this would indicate an advantage in developing methods that follow existing biologists' representational conventions. On the other hand, if generic algorithms produce better performance, biologists may abandon their commitment to these conventions in the interests of efficiency.

Fig. 1. Manual representation of a biochemical network (regulation mechanisms of cholesterol

synthesis [START_REF] Michal | On representation of metabolic pathways[END_REF]).

This paper reports on an empirical study which compared the effectiveness of three layout algorithms when used with a motif-search task. Two of the layouts (Force Directed, Hierarchical) are popular existing generic layout algorithms; the third (MetaViz) is a layout specifically designed to include representational conventions familiar to biologists.

Background

Our collaboration with biologists led us to focus on a particular biological research topic: metabolism. Metabolism is the set of biochemical reactions (figure 2.A) that are used to perform vital biological functions such as energy generation. Each metabolic function is modelled by a set of interconnected reactions corresponding to a small graph called a metabolic pathway (figure 2.B). Since the output of a pathway is often the input of another pathway it is possible to merge all these pathways into a single metabolic network (figure 2.C). Each organism has its own metabolic network. For instance, mammals and plants have different metabolic networks since only plants can generate energy using the photosynthesis pathway. Many metabolic networks exist and are updated regularly; automatic graph drawing algorithms for these pathways are therefore necessary. Most of the work on metabolism visualization has been done at the pathway level [START_REF] Becker | A Graph Layout Algorithm for Drawing Metabolic Pathways[END_REF], pp. 461-467, Schreiber 2003, pp. 105-110, Wegner & Kummer 2005). But in many metabolic studies it is necessary to visualize all the pathways and their connections at the same time (e.g. to put experimental data into context [START_REF] Paley | The pathway tools cellular overview diagram and Omics Viewer[END_REF]). Visualization is also necessary for topological analysis of metabolic networks, for example when looking for set of connected reactions (motifs) spanning over different pathways (Lacroix, et al., 2006, pp. 360-368). Simple pathway visualization is not sufficient for such tasks but neither is network visualization without pathway information. Indeed, to be useful for mapping experiments, it is necessary to represent the entire network structure while keeping the contextual information provided by its division into metabolic pathways. Note that this is one of the requirements for biological network visualization proposed by [START_REF] Saraiya | Visualizing biological pathways: requirements analysis, systems evaluation and research agenda[END_REF]. In the case of the motif search task, the drawing needs to provide a faithful image of the network structure. This is a challenging problem which we addressed by the development of the MetaViz layout method [START_REF] Bourqui | Metabolic network visualization eliminating node redundance and preserving metabolic pathways[END_REF].

MetaViz provides a domain specific solution for drawing the graph with its connected pathways. For our evaluation, we compared MetaViz with two generic layout methods.

To our knowledge, no prior work has been done on evaluation of biological networks layouts with respect to task efficiency. [START_REF] Saraiya | Visualizing biological pathways: requirements analysis, systems evaluation and research agenda[END_REF] performed an informal heuristic evaluation of five popular pathway analysis systems, from which they identified requirements for pathway visualization systems. They did not, however, conduct a task-based experiment producing performance data.

Layouts

In this article, we present an empirical comparison of three different algorithms. First, we chose two classical graph drawing algorithms: a force directed algorithm and a hierarchical layout. Finally, we used our own algorithm which was specifically designed for metabolic network visualization [START_REF] Bourqui | Metabolic network visualization eliminating node redundance and preserving metabolic pathways[END_REF].

Quotient graph modelling

Pathways are the building blocks of metabolic networks, and biologists need to visualize these features [START_REF] Bourqui | Metabolic network visualization eliminating node redundance and preserving metabolic pathways[END_REF]. Moreover some topological patterns like cycles are important since they correspond to particular biological processes (e.g. Krebs cycle for energy synthesis). Thus, a pre-processing step is defined before using any of the three layout algorithms; we applied a clustering algorithm [START_REF] Bourqui | Metabolic network visualization eliminating node redundance and preserving metabolic pathways[END_REF] to detect pathway and topological information. The result of this process is a quotient graph where nodes (metanodes) contain metabolic pathways or topological patterns. Two metanodes are linked by an edge (metaedge) if at least two nodes (one in each metanode) are linked in the original network. The main disadvantage of quotient graph visualization is that it is not possible to know how many edges are represented by a given metaedge and which nodes within the metanodes are linked. Quotient graphs were used as the input to the three layout algorithms. Force directed layouts are widely used since they provide visually pleasing results which show the structure of the graph clearly. They behave as simulated physical systems which try to map the path distance between nodes in the network to euclidean distance and thus produce intuitive representations. There are several variations of this approach (e.g. [START_REF] Eades | A heuristic for graph drawing[END_REF], Frick, et al., 2004[START_REF] Gajer | GRIP: Graph dRawing with Intelligent Placement[END_REF]. We chose GEM (Frick, et al., 2004) since it gives particularly good results in term of stretch (i.e. the ratio between graph and euclidean distances) and is computationally efficient for the size of graphs we wished to use. To prevent node-node overlap, we first modified the algorithm by setting the ideal length of an edge to the sum of half the size of its extremities, and then used an algorithm [START_REF] Dwyer | Fast node overlap removal[END_REF] to remove any remaining overlaps. Figure 3 shows an example of a quotient graph drawn using this method. The second type of algorithm we used is a hierarchical algorithm. This kind of algorithm embeds nodes on horizontal layers to highlight the hierarchical organization of data. This is followed by a heuristic which tries to minimize edge crossings by computing an ordering of the nodes on each layer. This type of algorithm is widely used in biological pathway drawings [START_REF] Dogrusoz | A compound graph layout algorithm for biological pathways[END_REF][START_REF] Karp | The Pathway Tools software[END_REF][START_REF] Schreiber | Comparison of metabolic pathways using constraint graph drawing[END_REF]. Like the force directed approach, many hierarchical algorithms exist (e.g. [START_REF] Sugiyama | Visualisation of structural information : Automatic drawing of compound digraphs[END_REF][START_REF] Auber | Tulip: A huge graph visualisation framework[END_REF][START_REF] Eiglsperger | An Efficient Implementation of Sugiyama's Algorithm for Layered Graph Drawing[END_REF]; we chose the algorithm proposed by [START_REF] Auber | Tulip: A huge graph visualisation framework[END_REF] which is an improvement of the well known Sugiyama algorithm [START_REF] Sugiyama | Visualisation of structural information : Automatic drawing of compound digraphs[END_REF]. Figure 4 shows the result of this hierarchical algorithm on a quotient graph.

Force directed layout

Hierarchical layout

MetaViz layout

Fig. 5 Result of the MetaViz layout on the quotient graph

MetaViz [START_REF] Bourqui | Metabolic network visualization eliminating node redundance and preserving metabolic pathways[END_REF] is based on the Mixed Model algorithm of [START_REF] Gutwenger | Planar Polyline Drawings with Good Angular Resolution[END_REF]. To adapt the Mixed Model algorithm to include metabolic network drawing conventions, we made three main modifications.

First, as we used the Mixed Model to draw the quotient graph, the algorithm was modified to take into account the varying sizes of metanodes.

Second, the Mixed Model is a planar graph drawing algorithm, so we needed to planarize the quotient graph. This problem is well-known and is NP-Hard [START_REF] Lui | On the deletion of nonplanar edges of a graph[END_REF]. Many techniques exist, either by augmentation or by deletion of edges or nodes [START_REF] Liebers | Planarizing Graphs -A Survey and Annotated Bibliography[END_REF]. The disadvantage of an augmentation based technique is that it may add up to |V| 4 nodes, with the drawing becoming difficult to understand. We therefore used the following heuristic: vertices of higher degree are removed one by one until the graph becomes planar. All removed nodes are then reinserted. Removed edges are re-added one by one as long as the graph is planar. The result of this process is then drawn by the modified Mixed Model algorithm. Finally, we add the edges removed during the planarization step. These edges are laid out on the external face of the drawing and with at most three bends per edge, in an orthogonal manner. This routing was inspired by hand-drawn representations of biological networks (e.g. Figure 1).

The third modification is related to the ordering of nodes. The Mixed Model algorithm has two steps: 1. The first step builds an ordered partition of the set of nodes. This partition is called shelling ordering. The principle used is that nodes that are on the external face of the graph are successively removed. 2. The second step is the recomposition of the graph according to the shelling ordering. To guarantee there is neither edge-edge crossing nor node-edge overlapping, the ordering is traversed in reverse order. One of the metabolic network drawing conventions is that a reaction (or a compound) of a given metabolic pathway is embedded close to the other reactions (and compounds) of the pathway. The third modification of the Mixed Model therefore was the addition of a pathway constraint to the decomposition phase. If SO = {V1,V2, ...,Vr} is the shelling ordering, where each Vi a set of nodes, when a vertex u is added into a set Vi , 1 ≤ i < r, we would like those nodes in the same pathways as u to be in Vi or Vi+1. However, the Mixed Model shelling ordering rules may prevent this. We therefore put these constrained nodes into the next possible Vj where j > i. Those nodes will then be more likely to be drawn next to each other. Figure 5 shows the result of the MetaViz layout on a quotient graph.

Methodology

Networks and tasks

We chose three different metabolic networks of different organisms. These networks are built with version 10.0 of the BioCyc database. Our collaborator, Ludovic Cottret, used perl scripts and pathway tools software [START_REF] Karp | The ecocyc and metacyc databases[END_REF][START_REF] Karp | The Pathway Tools software[END_REF][START_REF] Krummenacker | Querying and computing with biocyc databases[END_REF] to obtain information on the reactions, compounds and metabolic pathways involved in the metabolism of three different genus of bacteria called Buchnera: Buchnera APS (graph A), Buchnera aphidicola BP (graph B) and Buchnera aphidicola SG (graph C). We chose organisms with similar size metabolic networks (503 nodes/526 edges, 558 nodes/538 edges, and 562 nodes/559 edges) and similar topologies so that the experimental tasks would not be of widely differing complexity [START_REF] Bourqui | Metabolic network visualization eliminating node redundance and preserving metabolic pathways[END_REF] provide a more detailed description of the metabolic data). Clustering [START_REF] Bourqui | Metabolic network visualization eliminating node redundance and preserving metabolic pathways[END_REF] was applied on each of these three networks to create the quotient graph, and three versions of each network were created, one for each of the three layout conditions. This resulted in nine graph drawings in total: these are referred to by their graph identifier (A, B, C) and their layout condition (GEM, Hierarchical, MetaViz).

The task is a biologically relevant one: the identification of motifs in networks. A motif is an unordered set of reactions such that each reaction of the motif shares (at least) one of its reactant or product with (at least) another reaction of the motif. Figure 6 shows an example of occurrence of the motif 1.2.1.12, 4.1.2.13, 5.3.1.1. Finding repeated motifs often indicate that gene duplications occurred during organism evolution.

Using the algorithm provided by [START_REF] Lacroix | Motif search in graphs: application to metabolic networks[END_REF] we selected three motifs containing three reactions. To prevent our experimental participants being able to learn the answers, we chose motifs where the number of occurrences of the motif in the networks varied between 0 and 3 in the different organisms. We also selected motifs which could be found either within pathways or spanning over different pathways.

Table 1 shows the number of occurrences of each motif contained in each network (graph A, B and C), within a single metanode or shared by several metanodes.

Motifs #occurrences in graph A

#occurrences in graph B

#occurrences in graph C

Within Shared Within Shared Within Shared 0 2 0 2 0 0

1 1 1 1 1 1 0 1 0 1 0 0

Experimental Design

Our evaluation used three layout algorithms, three different networks and three different motifs. Each task was therefore a combination of network, layout, and motif, with 27 tasks in total. The tasks were presented in random order. Before commencing the experimental tasks, the participants completed 12 practice tasks chosen randomly from the 27 tasks. All participants preformed the same 12 practice tasks and therefore had the same experience at the beginning of the real experiment. During the first five practice tasks, the participants were helped by the experimenter and taught how to search for the relevant reactions. They were given feedback on their answers to these five tasks (Figure 7.( 5)). For the following seven tasks, the participants were not aware that these were practice tasks and did not form part of the experimental data collection. The 27 experimental tasks were then presented in random order, and user-controlled rest breaks were included regularly throughout the duration of the experiment to address any problems of fatigue.

Experimental task

Figure 7 shows a screenshot of the evaluation software.

The visualization panel is located on the right, with the motif to search for on the left. To help the participants in their search, three hint were highlighted in red in the network. These nodes were reactions potentially involved in the motif (e.g. all the nodes whose label starts with 6.3.4). The task consists in finding which of these hint nodes are part of (at least) one occurrence of the motif (here 6.3.4.*, 3.5.4.9, 6.3.2.17). The hints were necessary so as to prevent the user needing to search the whole of a very large network. Pilot tests revealed that the motif search task was still sufficiently challenging, despite the presence of these hints.

Using button 2 and clicking on a node automatically highlights in pink those nodes at distance of at most 2 from the selected node, and all edges and metaedges linking these nodes. Therefore to verify if a red highlighted hint reaction R is relevant, the participant had to click on it to see the reactions sharing at least one metabolite with R (Figure 8). It could be the case that only one other reaction R′ of the motif is found when looking at R's neighborhood. However, if R is the first reaction of a reaction cascade (a path), then the third reaction of the cascade would be at distance 4 from R. The participant would then need to look at the neighborhood of R′ to verify if R is relevant or not.

The participant then used the button 1 to select relevant reactions matching the motif (Figure 7). When the participants thought that they had found all the relevant nodes, the button 4 was used to validate this selection and to move on to the next task.

Experimental process

22 participants were recruited from Glasgow and Bordeaux Universities. Seven had some knowledge of bioinformatics; the others did not. The choice to exclude biologists from our sample was deliberate, and was motivated by an interview we had with 20 biologists.

They were asked to order the three layouts according to their aesthetic expectations of metabolic network drawings. In 71% of the cases MetaViz was ranked first, in 29% it was ranked second, and it was never ranked third. Those participants who chose MetaViz indicated that it was the layout most familiar to them. Since we were interested in differences in task performance using these three layouts, independent of any prior familiarity, we deliberately did not include any biologists in our sample, as we did not want to bias our results toward the MetaViz layout.

As this is a within-subject experiment, and participants' performance in one condition is compared with their own performance in another condition, any variation or similarity in the nature of participants does not affect the data analysis. The inclusion of practice tasks and task randomization helped counter any data bias due to the learning effect (whereby there is improved performance on the later tasks due to increasing task familiarity). Each experiment, including time spent at the beginning on the tutorial and the worked example, and on the questionnaire at the end, took approximately one hour. No problems were experienced during the experiments and all participants appeared to engage in the tasks seriously.

Results and analysis

The response time data for each task was measured as the time from the display of the network and the motif, to the time the participants pressed the "Validate" button to record that they had finished that task.

The error data was recorded as a 0 or 1, where 1 represents the case where the participant did not identify any of the present motifs correctly. Thus, a high value for both data measures (time and errors) implies poor performance. However, as the participants were allowed as much time as they wished to locate the motifs (or indicate an absence of motifs), there were very few errors in the responses. Hence, only the response time data is analyzed here.

Performance and results by Layout Condition

The average response time for the three layout conditions over all three networks and all three motifs is shown in Figure 9. A two-tailed ANOVA test revealed statistical significance in performance over all conditions (F=9.14>F(2,42,α=0.05)=3.23).

Tukey pair-wise comparisons at the 95% confidence level led to the following conclusions: 1. The Hierarchical layout produces worst time performance than both the MetaViz and GEM layouts: an average of 80.14s (Hierarchical) versus 71.8s (GEM) and 75.18s (MetaViz).

2. There is no statistical difference in performance between the MetaViz and GEM layouts, despite the average for Metaviz (75.18s) being greater than that of GEM (71.8s). There was no statistical difference in performance between the three networks A, B and C (F=0.72<F(2,42, α =0.05)=3.23): this is as expected, as we chose networks of similar size and complexity. There was difference in the performance between the three motifs (F=17.4>F(2,42,α=0.05)=3.23), with the first motif (6.3.4.*, 3.5.4.9, 6.3.2.17) being more difficult than both of the other two motifs. This is unsurprising, as this first motif included the most occurrences involving nodes shared between quotient nodes (see Table 1). No additional interesting results were obtained when the different layouts were compared within the data for each motif.

Preference results by Layout Condition

The post-task questionnaire asked the participants the following questions:

Q1. Which drawing is the best for the task? Q2. Which drawing is worst for the task? Q3. In which drawing is a highlighted edge easiest to follow?

Q4. In which drawing is a highlighted edge the most difficult to follow? Q5. In which drawing is the neighbourhood of a node easiest to identify? Q6. In which drawing is the neighbourhood of a node the most difficult to identify?

Participants were also invited to write textual comments on each of the three layouts. Figures 10 and 11 show the percentage of the 22 participants who selected the layout conditions as best and worst, according to the six questions asked. Representative open comments from the participants regarding each of these layouts are shown in Table 2 Table 2. Representative positive and negative comments about the three layouts.

We aggregated the quantitative preference data so that each participant effectively associated a score (between 1 and 3) to each of the three layouts. Using the time data for each participant for each layout, we performed a correlation analysis to see if there was any correspondence between preference and performance. There was no significance in this correlation data (0.051<r(20, α = 0.05)=0.4227), indicating that the participants' preferred layout was not the one that they performed best on (and vice versa for their least preferred layout).

Discussion

Our expectation was that the generic Force Directed layout [START_REF] Eades | A heuristic for graph drawing[END_REF][START_REF] Frick | A Fast Adaptive Layout Algorithm for Undirected Graphs[END_REF] would produce superior results in a motif-search task over both the other two algorithms because of the way in which it highlights connectivity.

Figure 12 shows three detailed views of the same metabolic network. Each view is obtained using one of the three algorithms, and is shown at the same zoom level. To highlight the connectivity of a node, we coloured all the paths of length two from that node. Using the same scaling factor (as in Figure 12), all the nodes at distance two from the focus node are visible under the GEM algorithm; this is not the case with the two other algorithms. With the Hierarchical and Metaviz algorithms, users would have to navigate the view (zoom in/out and pan) to view all the highlighted edges.

This example shows why we anticipated that for connectivity tasks GEM would provide better efficiency results. Force directed methods like GEM are designed to embed nodes that are close in terms of path length near to each other with respect to euclidean distance. In contrast, the Metaviz and Hierarchical layouts focus more on structuring the layout, node distributions, and avoiding edge crossings.

The data supports, to some extent, the hypothesis that GEM is superior, as the GEM layout results in better performance than the Hierarchical layout.

We were surprised, however, at the success of the MetaViz layout, whose performance was statistically as good as GEM. On looking at the MetaViz layout again, we believe this is because MetaViz as used with these networks has a clean appearance, with clear orthogonal lines and no edge or node overlaps. We also believe that the adaptation of the shelling ordering based on pathway constraints resulted in more compact node distributions, with higher information density in parts of the drawing. This is unlike the Hierarchical drawing, where the nodes are more dispersed. Thanks to our participant selection, we can affirm that the success of MetaViz cannot be attributed to prior biological knowledge or familiarity, as there were no biologists amongst our participants.

The preference data is the most telling when it comes to comparing the three layouts, as GEM is consistently rated the best (and never the worst), and Hierarchical is consistently rated the worst (and never the best). MetaViz is considered neither the best nor the worst.

There is an interesting anomaly in the reversal of the data between GEM and MetaViz for the overall "worst" question, Q2, where GEM is ranked the second worst (and therefore, by implication, the second best) by 31.8% versus 13.6%. Observation of the questionnaires showed that many of those participants who rated GEM the worst highlighted problems such as node/edge overlapping in their open comments.

The preference ranking order for the three layouts is therefore clearly GEM (best), MetaViz (middle), Hierarchical (worst). This contrasts with the performance data where GEM and MetaViz produce similar results.

We anticipated that GEM would be preferred because of the elegant layout aesthetics of the spring model and its depiction of close connections: this is supported by the textual remarks of the participants who commented favourably on the short edges and visual spread of nodes and edges.

However, our performance data shows that the MetaViz is just as effective as GEM, despite the fact that its layout does not appear to favour a connectivity task. Thus, as biologists typically prefer layouts similar to the MetaViz (which match the visualizations that they are familiar with), our data shows that doing so is not detrimental to their motif search efficiency when compared with the elegant GEM model favoured by researchers in graph layout.

Conclusions

When designing a metabolic network visualization tool the choice of the drawing algorithm is important since biologists expect particular representational conventions.

Existing graph drawing algorithms like Force Directed and Hierarchical may prove useful in such tools. Our hypothesis was that on connectivity tasks users would be more efficient using Force Directed drawings. However our experimental results show that there is no efficiency difference between a diagram designed with biological conventions (Metaviz) and a Force Directed layout. We can conclude from these results that the efforts spent on layout algorithms that conform to biological representational conventions are worthwhile, because not only will such representations match biologists' expectations, they can be as efficient as generic springlayout algorithms.

These results need, of course, to be interpreted within the context of this experiment and its limitations and parameters. The experiment used three networks of a particular size and three particular motifs. Using more than one network and more than one motif assists in producing generalizable results, but these are still constrained by the necessary limitations of the formal experimental method.

Using the formal experimental method allowed us to collect specific, measureable and controlled performance data associated with each of our three representations, thus enabling us to compare their effectiveness rigorously using statistical methods. While the experimental task we used may only be part of the activities typically performed on such visualisations, wider, more extensive exploration and communication tasks would not have been possible within this formal method. A more exploratory usability study could be envisaged which investigates these visualisations when used by experts with more extensive and richer real-world tasks: this would be an interesting further study. Such exploratory studies, however, do not produce clear and controlled data that can easily be analysed using statistical methods.

Since our aim was to evaluate the effect of drawing algorithms on user efficiency in a common biological motif searching task we chose non-biologist users: by removing the expectation of the participants having any domain knowledge, we could be sure that the performance data truly represented the complexity of the visual motif-search task, and was not influenced by any prior biological knowledge. We anticipate that the same evaluation with biologists would confirm these results, and may show that MetaViz is superior since it includes representational conventions biologists would expect.

In addition, this experiment has provided us with useful qualitative data in the form of positive and negative comments about MetaViz. Integrating the suggestions made in our next version would ensure a much improved algorithm. For example, increasing the information density, removing white space and reducing the overall area of the diagram would address many negative comments received. These improvements will lead to even better experimental results.

Fig. 2 .

 2 Fig. 2. The different abstractions of metabolic modelling. At the most detailed level, a metabolic reaction turns a metabolite (biochemical compound) into another one under the action of an enzyme (A). A set of metabolic reactions make up a metabolic pathway (B) which is a subgraph of the entire metabolic network (C).

Fig. 3 .

 3 Fig. 3. Result of the force directed layout on the quotient graph.

Fig. 4 .

 4 Fig. 4. Result of the hierarchical layout on the quotient graph.

Fig. 6 .

 6 Fig. 6. Example of a motif where reactions are ordered in different ways. All three sets represent the same motifs. A motif is not necessarily a path.

Fig. 7 .

 7 Fig. 7. Screenshot of the evaluation software. Buttons 1 and 2 allowed participants to select relevant reactions, with button 2 automatically highlighting the neighbourhood of the node in pink. Button 3 removed the pink highlighting. Button 4 was used to validate the answer and to move onto the next task. During the first five tasks, the participants had a feedback of their previous task, as a percentage of right answers (shown at 5).

Fig. 8 .

 8 Fig. 8. Using button 2 and clicking on the reaction labelled 6.3.4.3 automatically highlights nodes at distance of at most two, and the edges and metaedges linking them. Here the reaction 6.3.4.3 is a relevant reaction since the other reactions of the motif (3.5.4.9 and 6.3.2.17) are highlighted in pink.

Fig. 9 .

 9 Fig. 9. The average response time in seconds for the three layout conditions, over all networks, and over all motifs. Lines indicate statistical significance between conditions at the 95% confidence level.

Fig. 10 .

 10 Fig. 10. Preference responses to the three post-task "best" questions, as percentages.

Fig. 12 .

 12 Fig. 12. Detail of a metabolic network drawn using GEM, Hierarchical and MetaViz algorithms. All the paths of length two going out of the red node are highlighted in purple.

Table 1 : Number of occurrences of each motif contained by each network (graph A, B and C) within a single metanode or shared by several metanodes.

 1

  .

		Positive comments	Negative comments
			"short edges",		"node/edge
	GEM	17		9
			"edges spaced out"		overlaps"
					"long edges",
	Hierarchical	6	"no edge overlaps"	21
					"large graph area"
					"long edges",
	MetaViz	5	"orthogonal lines"	16	"edges close
					together"

Acknowledgements

We are grateful to: Ludovic Cottret for providing metabolic networks, the ANR-BBSRC funded project, Systryp, Glasgow Bioinformatics Research Centre and LaBRI, Bordeaux for hosting authors, and all the experimental participants. Ethical clearance for this study is covered by the student ethics protocol of the Department of Computing Science, University of Glasgow.


Guillaume Bonfante
email: bonfante@loria.fr

Bruno Guillaume
email: guillaum@loria.fr

Mathieu Morey
email: moreymat@loria.fr

Guy Perrier
email: perrier@loria.fr

Modular Graph Rewriting to Compute Semantics

Taking an asynchronous perspective on the syntax-semantics interface, we propose to use modular graph rewriting systems as the model of computation. We formally define them and demonstrate their use with a set of modules which produce underspecified semantic representations from a syntactic dependency graph. We experimentally validate this approach on a set of sentences. The results open the way for the production of underspecified semantic dependency structures from corpora annotated with syntactic dependencies and, more generally, for a broader use of modular rewriting systems for computational linguistics.

Introduction

The aim of our work is to produce a semantic representation of sentences on a large scale using a formal and exact approach based on linguistic knowledge. In this perspective, the design of the syntax-semantics interface is crucial.

Based on the compositionality principle, most models of the syntax-semantics interface use a synchronous approach: the semantic representation of a sentence is built step by step in parallel with its syntactic structure. According to the choice of the syntactic formalism, this approach is implemented in different ways: in a Context-Free Grammars (CFG) style framework, every syntactic rule of a grammar is associated with a semantic composition rule, as in the classical textbook by [START_REF] Heim | Semantics in generative grammar[END_REF]; following the principles introduced by Montague, Categorial Grammars use an homomorphism from the syntax to the semantics (Carpenter (1992)). HPSG integrates the semantic and syntactic representations in feature structures which combine by unification [START_REF] Copestake | Minimal Recursion Semantics -an Introduction[END_REF]). LFG follows a similar principle [START_REF] Dalrymple | Lexical Functional Grammar[END_REF]). In a synchronous approach, the syntax-semantics interface closely depends on the grammatical formalism. Building such an interface can be very costly, especially if we aim at a large coverage for the grammar.

In our work, we have chosen an asynchronous approach in the sense that we start from a given syntactic analysis of a sentence to produce a semantic representation. With respect to the synchronous approach, a drawback is that the reaction of the semantics on the syntax is delayed. On the other hand, the computation of the semantics is made relatively independent from the syntactic formalism. The only constraint is the shape of the output of the syntactic analysis.

In the formalisms mentioned above, the syntactic structure most often takes the form of a phrase structure, but the choice of constituency for the syntax makes the relationship with the semantics more complicated. We have chosen dependency graphs, because syntactic dependencies are closely related to predicate-argument relations. Moreover, they can be enriched with relations derived from the syntax, which are usually ignored, such as the arguments of infinitives or the anaphora determined by the syntax. One may observe that our syntactic representation of sentences involves plain graphs and not trees. Indeed, these relations can give rise to multiple governors and dependency cycles. On the semantic side, we have also chosen graphs, which are widely used in different formalisms and theories, such as DMRS [START_REF] Copestake | Invited Talk: Slacker semantics: Why superficiality, dependency and avoidance of commitment can be the right way to go[END_REF] or MTT (Mel'čuk (1988)) .

The principles being fixed, our problem was then to choose a model of computation well suited to transforming syntactic graphs into semantic graphs. The λ-calculus, which is widely used in formal semantics, is not a good candidate because it is appropriate for computing on trees but not on graphs. Our choice naturally went to graph rewriting. Graph rewriting is barely used in computational linguistics; it could be due to the difficulty to manage large sets of rules. Among the pioneers in the use of graph rewriting, we mention [START_REF] Hyvönen | Semantic Parsing as Graph Language Transformation -a Multidimensional Approach to Parsing Highly Inflectional Languages[END_REF]; [START_REF] Bohnet | On using a parallel graph rewriting formalism in generation[END_REF]; [START_REF] Crouch | Packed Rewriting for Mapping Semantics to KR[END_REF]; Jijkoun and de Rijke (2007); [START_REF] Bédaride | Semantic Normalisation : a Framework and an Experiment[END_REF]; [START_REF] Chaumartin | Une approche paresseuse de l'analyse sémantique ou comment construire une interface syntaxe-sémantique à partir d'exemples[END_REF].

A graph rewriting system is defined as a set of graph rewrite rules and a computation is a sequence of rewrite rule applications to a given graph. The application of a rule is triggered via a mechanism of pattern matching, hence a sub-graph is isolated from its context and the result is a local modification of the input. This allows a linguistic phenomenon to be easily isolated for applying a transformation.

Since each step of computation is fired by some local conditions in the whole graph, it is well known that one has no grip on the sequence of rewriting steps. The more rules, the more interaction between rules, and the consistency of the whole rule system becomes difficult to maintain. This bothers our ambition of a large coverage for the grammar. To solve this problem, we propose to organize rules in modules. A module is a set of rules that is linguistically consistent and represents a particular step of the transformation. For instance, in our proposal, there is a module transforming the syntactic arguments of verbs, predicative nouns and adjectives into their semantic arguments. Another module resolves the anaphoric links which are internal to the sentence and determined by the syntax.

From a computational point of view, the grouping of a small number of rules inside a module allows some optimizations in their application, thus leading to efficiency. For instance, the confluence of rewriting is a critical feature -one computes only one normal form, not all of them -for the performance of the program. Since the underlying relation from syntax to semantics is not functional but relational, the system cannot be globally confluent. Then, it is particularly interesting to isolate subsets of confluent rules. Second point, with a small number of rules, one gets much more control on their output. In particular, it is possible to automatically infer some invariant properties of graphs along the computation within a particular module. Thus, it simplifies the writing of the rules for the next modules. It is also possible to plan a strategy in the global evaluation process.

It is well known that syntactic parsers produce outputs in various formats. As a by-product of our approach, we show that the choice of the input format (that is the syntax) seems to be of low importance overall. Indeed, as far as two formats contain the same linguistic information with different representations, a system of rewrite rules can be designed to transform any graph from one format to another as a preliminary step. The same remark holds for the output formats.

To illustrate our proposal, we have chosen the Paris7 TreeBank (hereafter P7TB) dependency format defined by Candito et al. (2010) as the syntactic input format and the Dependency MRS format (hereafter DMRS) defined by [START_REF] Copestake | Invited Talk: Slacker semantics: Why superficiality, dependency and avoidance of commitment can be the right way to go[END_REF] as the semantic output format. We chose those two formats because the information they represent, if it is not complete, is relatively consensual and because both draw on large scale experiments: statistical dependency parsing for French1 on the one hand and the DELPH-IN project2 on the other hand.

Actually, in our experiments, since we do not have an appropriate corpus annotated according to the P7TB standard, we used our syntactic parser LEOPAR3 whose outputs differ from this standard and we designed a rewriting system to go from one format to the other.

The paper is organized as follows. In section 1, we define our graph rewriting calculus, the β-calculus. In Section 2, we describe the particular rewriting system that is used to transform graphs from the syntactic P7TB format into the DMRS semantic format. In Section 3, we present experimental results on a test suite of sentences.

The β-calculus, a graph rewriting calculus

Term rewriting and tree rewriting can be defined in a straightforward and canonical way. Graph rewriting is much more problematic and there is unfortunately no canonical definition of a graph rewriting system. Graph rewriting can be defined through a categorical approach like SPO or DPO [START_REF] Rozenberg | Handbook of Graph Grammars and Computing by Graph Transformations[END_REF]). But, in practice, it is much easier to use a more operational view of rewriting where modification of the graph (the "right-hand side" of a rule) is defined by means of a set of commands; the control of the way rules are applied (the "left hand-side") still uses pattern matching as this is done in traditional graph rewriting.

In this context, a rule is a pair of a pattern and a sequence of commands. We give below the formal materials about graphs, patterns, matchings and commands. We illustrate the section with examples of rules and of rewriting.

Graph definition

In the following, we suppose given a finite set L of edge labels corresponding to the kind of dependencies used to describe sentences. They may correspond to syntax or to semantics. For instance, we use L = {SUJ, OBJ, ARG1, ANT, . . .}.

To decorate vertices, we use the standard notion of feature structures. Let N be a finite set of feature names and A be a finite set of atomic feature values. In our example, N = {cat, mood, . . .} and A = {passive, v, n, . . .}. A feature is a pair made of a feature name and a set of atomic values. The feature (cat, {v, aux}) means that the feature name cat is associated to either the value v or aux. In the sequel, we use the notation cat = v|aux for this feature. Two features

f = v and f ′ = v ′ are compatible whenever f = f ′ and v ∩ v ′ = ∅.
A feature structure is a finite set of features such that each feature name occurs at most once. F denotes the set of feature structures. Two feature structures are compatible if their respective features with the same name are pairwise compatible.

A graph G is then defined by a 6-tuple (V, fs, E, lab, σ, τ ) with:

• a finite set V of vertices;

• a labelling function fs from V to F;

• a finite set E of edges;

• a labelling function lab from E to L;

• two functions σ and τ from E to V which give the source and the target of each edge.

Moreover, we require that two edges between the same couple of nodes cannot have the same label.

Patterns and matchings

Formally, a pattern is a graph and a matching φ of a pattern

P = (V ′ , fs ′ , E ′ , lab ′ , σ ′ , τ ′ ) into a graph G = (V, fs, E, lab, σ, τ
) is an injective graph morphism from P to G. More precisely, φ is a couple of injective functions: φ V from V ′ to V and φ E from E ′ to E which:

• respects vertex labelling: fs(φ V (v)) and fs ′ (v) are compatible;

• respects edge labelling: lab(φ E (e)) = lab ′ (e);

• respects edge sources: σ(φ E (e)) = φ V (σ ′ (e));

• respects edge targets: τ (φ E (e)) = φ V (τ ′ (e)).

Commands

Commands are low-level operations on graphs that are used to describe the rewriting of the graph within a rule application. In the description below, we suppose to be given a pattern matching φ : P → G. We describe here the set of commands which we used in our experiment so far. Naturally, this set could be extended.

• del edge(α, β, ℓ) removes the edge labelled ℓ between α and β. More formally, we suppose that α ∈ V P , β ∈ V P and P contains an edge e from α to β with label ℓ ∈ L. Then, del edge(α, β, ℓ)(G) is the graph G without the edge φ(e). In the following, we give only the intuitive definition of the command: thanks to injectivity of the matching φ, we implicitly forget the distinction between x and φ(x).

• add edge(α, β, ℓ) adds an edge labelled ℓ between α and β. Such an edge is supposed not to exist in G.

• shift edge(α, β) modifies all edges that are incident to α: each edge starting from α is moved to start from β; similarly each edge ending on α is moved to end on β;

• del node(α) removes the α node in G. If G contains edges starting from α or ending on α, they are silently removed.

• add node(β) adds a new node with identifier β (a fresh name).

• add feat(α, f = v) adds the feature f = v to the node α. If α already contains a feature name f , it is replaced by the new one.

• copy feat(α, β, f ) copies the value of the feature named f from the node α to the node β. If α does not contain a feature named f , nothing is done. If β already contains a feature named f , it is replaced by the new value.

Note that commands define a partial function on graphs: the action add edge(α, β, ℓ) is undefined on a graph which already contains an edge labelled ℓ from α to β.

The action of a sequence of commands is the composition of actions of each command. Sequences of commands are supposed to be consistent with the pattern:

• del edge always refers to an edge described in the pattern and not previously modified by a del edge or a shift edge command;

• each command refers only to identifiers defined either in the pattern or in a previous add node;

• no command refers to a node previously deleted by a del node command.

Finally, we define a rewrite rule to be a pair of a pattern and a consistent sequence of commands.

A first example of a rule is given below with the pattern on the left and the sequence of commands on the right. This rule called INIT PASSIVE is used to remove the node corresponding to the auxiliary of the passive construction and to modify the features accordingly.

INIT PASSIVE

α cat = v voice = active β cat = v voice = unk

Rewriting

We consider a graph G and a rewrite rule r = (P, [c 1 , . . . , c k ]). We say that G ′ is obtained from G by a rewrite step with the r rule (written G -→ r G ′ ) if there is a matching morphism φ : P → G and G ′ is obtained from G by applying the composition of commands c k • . . . • c 1 .

Let us now illustrate two rewrite steps with the rules above. Consider the first graph below which is a syntactic dependency structure for the French sentence "Marie est considérée comme brillante" [Mary is considered as bright]. The second graph is obtained by application of the INIT PASSIVE rewrite rule and the last one with the PASSIVE ATS rewrite rule.

Marie cat = np lemma = MARIE est cat = v lemma = ÊTRE voice = active tense = present considérée cat = v lemma = CONSID ÉRER voice = unk comme cat = prep lemma = COMME brillante cat = adj lemma = BRILLANT SUJ AUX PASS ATS OBJ Marie cat = np lemma = MARIE est considérée cat = v lemma = CONSID ÉRER voice = passive tense = present comme cat = prep lemma = COMME brillante cat = adj lemma = BRILLANT SUJ ATS OBJ ǫ Marie cat = np lemma = MARIE est considérée cat = v lemma = CONSID ÉRER voice = active tense = present comme cat = prep lemma = COMME brillante cat = adj lemma = BRILLANT SUJ OBJ ATO OBJ

Modules and normal forms

A module contains a set of rewrite rules but, in order to have a finer control on the output of these modules, it is useful to declare some forbidden patterns. Hence a module is defined by a set R of rules and a set P of forbidden patterns. For a given module M = (R, P), we say that G ′ is an M-normal form of the graph G if there is a sequence of rewriting steps with rules of

R from G to G ′ : G -→ r 1 G 1 -→ r 2 G 2 . . . -→ r k G ′ , if no rule of R can be applied to G ′ and no pattern of P matches in G ′ .
In our experiment, forbidden patterns are often used to control the subset of edges allowed in normal forms. For instance, the NORMAL module contains the forbidden pattern: AUX PASS . Hence, we can then safely suppose that no graph contains any AUX PASS edge afterward.

2 From syntactic dependency graphs to semantic graphs Linguistic theories diverge on many issues including the exact definition of the linguistic levels and the relationships between them. Our aim here is not to commit to any linguistic theory but rather to demonstrate that graph rewriting is an adequate and realistic computational framework for the syntaxsemantics interface. Consequently, our approach is bound to neither the (syntactic and semantic) formats we have chosen nor the transformation modules we have designed; both are mainly meant to exemplify our proposal.

Representational formats

Our syntactic and semantic formats both rely on the notion of linguistic dependency. The syntactic format is an enrichment of the one which was designed to annotate the French Treebank [START_REF] Abeillé | Enriching a french treebank[END_REF]) with surface syntactic dependencies (Candito et al. (2010)). The enrichment is twofold:

• if they are present in the sentence, the deep arguments of infinitives and participles (from participial subordinate clauses) are marked with the usual labels of syntactic functions,

• the anaphora relations that are predictable from the syntax (i.e. the antecedents of relative, reflexive and repeated pronouns) are marked with a special label ANT.

This additional information can already be provided by many syntactic parsers and is particularly interesting to compute semantics. The semantic format is Dependency Minimal Recursion Semantics (DMRS) which was introduced by Copestake ( 2009) as a compact and easily readable equivalent to Robust Minimal Recursion Semantics (RMRS), which was defined by [START_REF] Copestake | Semantic composition with (robust) minimal recursion semantics[END_REF]. This underspecified semantic formalism was designed for large scale experiments without committing to fine-grained semantic choices. DMRS graphs contain the predicate-argument relations, the restriction of generalized quantifiers and the mode of combination between predicates. Predicate-argument relations are labelled ARGi, where i is an integer following a fixed order of obliqueness SUJ, OBJ, ATS, ATO, A-OBJ, DE-OBJ. . . . Naturally, the lexicon must be consistent with this ordering. The restrictions of generalized quantifiers are labelled RSTR ; their bodies are not overtly expressed but can be retrieved from the graph. There are three ways of combining predicates:

• EQ when two predicates are elements of a same conjunction;

• H when a predicate is in the scope of another predicate; it is not necessarily one of its arguments because quantifiers may occur between them;

• NEQ for all other cases.

Modular rewriting system

Graph rewriting allows to proceed step by step to the transformation of a syntactic graph into a semantic one, by associating a rewrite rule to each linguistic rule. While the effect of every rule is local, grouping rules in modules allows a better control on the global effect of all rules. We do not have the space here to propose a system of rules that covers the whole French grammar. We however propose six modules which cover a significative part of this grammar (cleft clauses, coordination, enumeration, comparatives and ellipses are left aside but they can be handled by other rewrite modules):

• NORMAL handles the regular syntactic transformations involving predicates: it computes tense and transforms all redistributions of arguments (passive and middle voices, impersonal constructions and the combination of them) to the active canonical form. This reduces the number of rules required to produce the predicate-argument relations in the ARG module below.

• PREP removes affixes, prepositions and complementizers.

• ARG transforms the verbal, nominal and adjectival predicative phrases into predicate-argument relations.

• DET translates the determiner dependencies (denoted DET) to generalized quantifiers.

• MOD interprets the various modifier dependencies (denoted MOD), according to their specificity: adjectives, adverbs, adjunct prepositional phrases, participial clauses, relative clauses, adjunct clauses.

• ANA interprets all anaphoric relations that are determined by the syntax (denoted ANT).

Modules provide an easy way to control the order in which rules are fired. In order to properly set up the rules in modules, we first have to fix the global ordering of the modules. Some ordering constraints are evident: for instance, NORMAL must precede PREP, which must precede ARG. The rules we present in the following are based on the order NORMAL, PREP, ARG, DET, MOD, ANA.

Normalization of syntactic dependencies

The NORMAL module has two effects: it merges tense and voice auxiliaries with their past participle and brings all the argument redistributions back to the canonical active form. This module accounts for the passive and middle voices and the impersonal construction for verbs that are not essentially impersonal. The combination of the two voices with the impersonal construction is naturally expressed by the composition of the corresponding rewrite rules. The two rules given in section 1.4 are part of this module. The first rule (INIT PASSIVE) merges the past participle of the verb with its passive auxiliary.

The auxiliary brings its mood and tense to the verb, which is marked as being passive. The second rule (PASSIVE ATS) transforms a passive verb with a subject and an attribute of the subject into its active equivalent with a semantically undetermined subject, an object (which corresponds to the subject of the passive form) and an attribute of the object (which corresponds to the attribute of the subject of the passive form).

Erasure of affixes, prepositions and complementizers

The PREP module removes affixes, prepositions and complementizers. For example, the rule given here merges prepositions with the attribute of the object that they introduce. The value of the preposition is kept to compute the semantics.

PREP ATO

α voice = active β cat = prep prep = * γ ATO OBJ c 1 = copy feat(β, γ, prep) c 2 = del edge(β, γ, OBJ) c 3 = shift edge(β, γ) c 4 = del node(β)

From lexical predicative phrases to semantic predicates

The ARG module transforms the syntactic arguments of a predicative word (a verb, a common noun or an adjective) into its semantic arguments. Following DMRS, the predicate-argument relations are not labelled with thematic roles but only numbered. The numbering reflects the syntactic obliqueness.

ARG OBJ

α β cat = n|np|pro OBJ c 1 = del edge(α, β, OBJ) c 2 = add edge(α, β, ARG2) c 3 = add edge(α, β, NEQ)
2.2.4 From determiners to generalized quantifiers DET reverts the determiner dependencies (labelled DET) from common nouns to determiners into dependencies of type RSTR from the corresponding generalized quantifier to the nominal predicate which is the core of their restriction.

Interpretation of different kinds of modification

MOD deals with the modifier dependencies (labelled MOD, MOD REL and MOD LOC), providing rules for the different kinds of modifiers. Adjectives and adverbs are translated as predicates whose first argument is the modified entity. The modifier and modified entities are in a conjunction (EQ), except for scopal adverbs which take scope (H) over the modified predicate. Because only lexical information enables to differentiate scopal from non-scopal adverbs, we consider all adverbs to be systematically ambiguous at the moment. Adjunct prepositional phrases (resp. clauses) have a similar rule except that their corresponding predicate is the translation of the preposition (resp. complementizer), which has two arguments: the modified entity and the noun (resp. verb) which heads the phrase (resp. clause). Participial and relative clauses exhibit a relation labelled EQ or NEQ between the head of the clause and the antecedent, depending on the restrictive or appositive type of the clause.

Resolution of syntactic anaphora

ANA deals with dependencies of type ANT and merges their source and their target. We apply them to reflexive, relative and repeated pronouns.

Experiments

For the experimentation, we are interested in a test suite which is at the same time small enough to be manually validated and large enough to cover a rich variety of linguistic phenomena. As said earlier, we use the P7 surface dependency format as input, so the first attempt at building a test suite is to consider examples in the guide which describes the format. By nature, an annotation guide tries to cover a large range of phenomena with a small set of examples.

The latest version4 of this guide (Candito et al. (2010)) contains 186 linguistic examples. In our current implementation of the semantic constructions, we leave out clefts, coordinations and comparatives. We also leave out a small set of exotic sentences for which we are not able to give a sensible syntactic structure. Finally, our experiment runs on 116 French sentences. Syntactic structures following P7 specifications are obtained with some graph rewriting on the output of our parser. Each syntactic structure was manually checked and corrected when needed. Then, graph rewriting with the modules described in the previous section is performed.

For all of these sentences, we produce at least one normal form. Even if DMRS is underspecified, our system can output several semantic representations for one syntactic structure (for instance, for appositive and restrictive relative clauses). We sometimes overgenerate because we do not use lexical information like the difference between scopal and non-scopal adverbs.

The result for three sentences is given below and the full set is available on a web page5 .

[012] "Le franc ¸ais se parle de moins en moins dans les conférences.

Conclusion

In this paper, we have shown the relevance of modular graph rewriting to compute semantic representations from graph-shaped syntactic structures. The positive results of our experiments on a test suite of varied sentences make us confident that the method can apply to large corpora. The particular modular graph rewriting system presented in the paper was merely here to illustrate the method, which can be used for other input and output formats. There is another aspect to the flexibility of the method: we may start from the same system of rules and enrich it with new rules to get a finer semantic analysis -if DMRS is considered as providing a minimal analysis -or integrate lexical information. The method allows the semantic ambiguity to remain unsolved within underspecified representations or to be solved with a rule system aiming at computing models of underspecified representations. Moreover, we believe that its flexibility makes graph rewriting a convenient framework to deal with idiomatic expressions.

  copy feat(α, β, mood) c 2 = copy feat(α, β, tense) c 3 = add feat(β, voice = passive) c 4 = del edge(β, α, AUX PASS) c 5 = shift edge(α, β) c 6 = del node(α) Our second example (PASSIVE ATS) illustrates the add node command. It is used in a passive construction where the semantic subject of the verb is not realized syntactically. del edge(α, β, SUJ) c 2 = add edge(α, β, OBJ) c 3 = del edge(α, γ, ATS) c 4 = add edge(α, γ, ATO) c 5 = add feat(α, voice = active) c 6 = add node(δ) c 7 = add edge(α, SUJ, δ)

  del edge(β, α, DET) c 2 = add edge(α, β, RSTR) c 3 = add edge(α, β, H)

  " [The French language is less and less spoken in conferences.] "J'encourage Marie à venir." [I invite Mary to come.] "La série dont Pierre connaît la fin" [The story Peter knows the end of]

								SUJ							MOD_LOC		OBJ
				DET					AFF_MOYEN				MOD			DET
			le cat=det		français cat=n	se cat=pro	parle cat=v mood=ind voice=unk tense=pres		de moins en moins cat=adv	dans cat=prep prep=loc	les cat=det	conférences cat=n
										/de moins en moins/ cat=adv	/dans/ cat=prep prep=loc		/les/ cat=det
										ARG1		EQ	EQ ARG1	NEQ ARG2	H RSTR
							/le/ cat=det				/parle/ cat=v mood=ind tense=pres voice=active			/conférences/ cat=n
							H	RSTR	ARG2 NEQ	ARG1 NEQ
								/français/ cat=n					//
	[057] je cat=pro	encourage cat=v mood=ind tense=pres voice=unk SUJ OBJ	A-OBJ Marie cat=np		SUJ à cat=prep prep=à	OBJ	cat=v mood=inf voice=unk venir		/je/ cat=pro ARG1	NEQ	/encourage/ cat=v mood=ind tense=pres voice=active ARG2 cat=np NEQ ARG3 EQ /venir/ cat=v mood=inf prep=à voice=active /Marie/ ARG1 NEQ
	cat=det [106] la	DET	série cat=n	ANT	dont cat=pro	Pierre cat=np MOD_REL	SUJ	connaît cat=v mood=ind voice=unk tense=pres DE-OBJ	la cat=det OBJ	DET	fin cat=n	/la/ cat=det RSTR H	cat=n /série/ EQ	/Pierre/ cat=np /connaît/ cat=v mood=ind tense=pres voice=active NEQ ARG1 ARG1	/fin/ cat=n NEQ ARG2 NEQ	/la/ cat=det RSTR H

http://alpage.inria.fr/statgram/frdep/fr_stat_dep_parsing.html

http://www.delph-in.net/

http://leopar.loria.fr

version 1.1, january 2010

http://leopar.loria.fr/doku.php?id=iwcs2011


Antoine Vacavant
email: antoine.vacavant@iut.u-clermont1.fr

Tristan Roussillon
email: tristan.roussillon@liris.cnrs.fr

Bertrand Kerautret
email: kerautre@loria.fr

Unsupervised Polygonal Reconstruction of Noisy Contours by a Discrete Irregular Approach

In this paper, we present an original algorithm to build a polygonal reconstruction of noisy digital contours. For this purpose, we first improve an algorithm devoted to the vectorization of discrete irregular isothetic objects. Afterwards we propose to use it to define a reconstruction process of noisy digital contours. More precisely, we use a local noise detector, introduced by Kerautret and Lachaud in IW-CIA 2009, that builds a multi-scale representation of the digital contour, which is composed of pixels of various size depending of the local amount of noise. Finally, we compare our approach with previous works, by considering the Hausdorff distance and the error on tangent orientations of the computed line segments to the original perfect contour. Thanks to both synthetic and real noisy objects, we show that our approach has interesting performance, and could be applied in document analysis systems.

Introduction

The representation of graphical objects (such as symbols, line drawings, characters, etc.) with line segments is an important task for various document and image analysis applications. This vectorization stage has been widely studied since the 90's, and many algorithms have been designed [START_REF] Cordella | Symbol Recognition in Documents: a Collection of Techniques?[END_REF][START_REF] Hilaire | Robust and Accurate Vectorization of Line Drawings[END_REF][START_REF] Wenyin | From Raster to Vectors: Extracting Visual Information from Line Drawings[END_REF]. Discrete or digital contours are natural outputs of image segmentation algorithms or digitization processes (e.g. document scanning). In most cases, digital contours are not perfect digitizations of ideal shapes but present noise and irregularities. In this case, classical approaches of contour detection generally need a parameter, and the output has to be filtered and post-processed. The following floating figure illustrates the Canny edge detector applied on two images with two sets of paremeters. For image (a), even if we could obtain an interesting result, a post-process is necessary to filter the output of the detector in order to compute a linear contour. A very noisy image (b) cannot be efficiently handled by this detector, even with various parameters Lately, two different ap-(a) (b)

proaches have been proposed in the digital geometry community. (i) The noisy digital contour (or a thick digital curve around it) is partitioned into thick (or blurred) segments [START_REF] Debled-Rennesson | Optimal Blurred Segments Decomposition of Noisy Shapes in Linear Time[END_REF][START_REF] Faure | Linear Decomposition of Planar Shapes[END_REF]. This last approach requires a global thickness parameter and thus cannot handle noises that are not uniform. (ii) To cope with this problem an adaptive pixel resizing method has been proposed in [START_REF] Rodriguez | Adaptive Pixel Resizing for Multiscale Recognition and Reconstruction[END_REF]. The idea is interesting but its implementation (as described in [START_REF] Rodriguez | Adaptive Pixel Resizing for Multiscale Recognition and Reconstruction[END_REF]) has several drawbacks. Firstly, the resizing function (which is not explicitly given) is based on the length of the symmetric tangents computed on the digital contour at the initial scale. Second, the resized pixels overlap so that the polygonalization is performed by a complex generalized preimage algorithm. Finally, the set of resized pixels may not be homotopic to the input digital contour and the topological control process proposed by the authors requires a skeleton computation.

In this paper, we propose a novel approach to compute a polygonal reconstruction from a noisy digital contour. For this purpose, we compute a set of resized pixels from a noisy digital contour thanks to a local noise detector [START_REF] Kerautret | Multi-Scale Analysis of Discrete Contours for Unsupervised Noise Detection[END_REF]. The idea is to locally look at the length of the maximal digital straight segments lying on the input digital contour at decreasing resolutions. The resolution beyond which we observe that the evolution of the length of the maximal segments is similar to the theoretical behavior for digitizations of smooth shapes does not contain any noise. The pixels at this resolution corresponds to bigger pixels at the initial resolution so that the higher the amount of noise is, the biggest the pixels are.

This set of resized pixels is transformed into an irregular isothetic object composed of rectangular cells and whose topology is stored into a Reeb graph [START_REF] Vacavant | Topological and Geometrical Reconstruction of Complex Objects on Irregular Isothetic Grids[END_REF]. For the reconstruction, each arc is vectorized into a polygonal line. The polygonal lines are then linked together so that the resulting polygonal structure reflects the topology of the irregular isothetic object.

In [START_REF] Vacavant | Topological and Geometrical Reconstruction of Complex Objects on Irregular Isothetic Grids[END_REF], arcs are vectorized following a visibility cone approach. Even if this reconstruction method has a linear-time complexity, it is a greedy approach that may induce an increasing error that leads to some very short segments and very acute turn angles. In this paper, we segment each arc into straight parts in lineartime using O'Rourke's algorithm [START_REF] O'rourke | An on-line Algorithm for Fitting Straight Lines between Data Ranges[END_REF], which is much simpler than the generalized preimage approach of [START_REF] Rodriguez | Adaptive Pixel Resizing for Multiscale Recognition and Reconstruction[END_REF]. We then propose two different reconstructions: (i) the first one takes into account the shape of the preimage of each straight part so that the resulting polygon lies within the irregular isothetic object, (ii) the second one is a simpler method, more convenient for objects that contain straight parts, but the resulting polygon may not completely lie within the irregular isothetic object.

In the next section, we recall definitions about irregular isothetic objects, and the previous work of [START_REF] Vacavant | Topological and Geometrical Reconstruction of Complex Objects on Irregular Isothetic Grids[END_REF]. We then describe our polygonalization methods and use it in order to reconstruct a noisy digital contour. Finally, we present several experiments and comparisons.

Preamble and Previous Work

Definitions

In this section, we first recall the concept of irregular isothetic grids (I-grids) in 2-D, with the following definition [START_REF] Coeurjolly | Supercover Model, Digital Straight Line Recognition and Curve Reconstruction on the Irregular Isothetic Grids[END_REF][START_REF] Vacavant | Fast Distance Transformation on Two-Dimensional Irregular Grids[END_REF].

Definition 1 (2-D I-grid). Let R be a closed rectangular subset of R 2 . A 2-D I-grid G is a tiling of R with non overlapping rectangular cells whose edges are parallel to the X and Y axes. The position of each cell R is given by its center point (x R , y R ) ∈ R 2 and its length along X and Y axes by

(l x R , l y R ) ∈ R * + 2 .
We say that two cells R 1 and R 2 are ve-adjacent if they share either a vertex or an edge, and e-adjacent if they share an edge. In a more general way, we say that R 1 and R 2 are k-adjacent, and k may be interpreted as e or ve in the following definitions. A set of cells E is a k-arc iff for each element of E = {R i } 1≤i≤n , R i has exactly two k-adjacent cells, except R 1 and R n . A set of cells E is a k-object iff for each couple of cells (R 1 , R 2 ) ∈ E × E, there exists a k-arc between R 1 and R 2 in E (Fig. 1, left)).

We consider an order relation based on the cells borders. We denote the left, right, top and bottom borders of a cell R respectively R L , R R , R T and R B . The abscissa of R L , for example, is equal to x R -(l x R /2) and for sake of clarity we write it R L = x R -(l x R /2). Definition 2 (Order relation on an I-grid). Let R 1 and R 2 be two cells of an I-grid G. We define the total order relation L , based on the cells borders:

∀R 1 , R 2 ∈ G, R 1 L R 2 ⇔ R L 1 < R L 2 ∨ R L 1 = R L 2 ∧ R T 1 ≤ R T 2 .
This order relation is of great importance either for the Reeb graph computation or for the segmentation of each k-arc into straight parts using O'Rourke algorithm, which requires that the input ranges have increasing x-coordinate.

Previous Algorithm for Irregular Object Vectorization

The work of Vacavant et al. [START_REF] Vacavant | Topological and Geometrical Reconstruction of Complex Objects on Irregular Isothetic Grids[END_REF] aimed to develop an algorithm that vectorizes a k-object with line segments. This method is divided into two main steps. Representation of the Topology of an Irregular Object. The Reeb graph [START_REF] Reeb | Sur les Points Singuliers d'une Forme de Pfaff Complétement Intégrable ou d'une Fonction Numérique[END_REF] of the input irregular k-object E is a way of representing the topology of E. The k-object E is scanned from left to right according to the order induced by L , given in Definition 2 (see Fig. 1 for an example). At the beginning, the intersection between E and the scanning vertical line has only one connected part and the Reeb graph is created with one edge between two nodes (b for begin and e for end). If a connected part splits into several parts, we add a node (s for split) from which start as many edges as there are parts. Conversely, if two connected parts merge, we link the corresponding edges to a node (m for merge) (see Fig. 1).

Moreover, the initial set of cells is recoded into a new one (without changing the shape of the object however) so that each edge of the Reeb graph corresponds to a k-arc having cells of increasing left border. This is done during the scan. We merge with the cell having the smallest left border, all its k-adjacent cells by using the following update procedure.

Update procedure. Let A be a k-arc, and R 1 and

R 2 two adjacent cells of E such that R 1 ∈ A, R L 1 < R L 2
, and R 2 adjacent to A (and thus should be added to A). If R L 2 = R R 1 , one just add R 2 to A, else the procedure updates the k-arc A with R 2 , and may recode A. For that, it first builds the greatest common rectangle (GCR) F 2 of R 1 and R 2 . This GCR is the greatest rectangle that can be contained in R 1 ∪R 2 [START_REF] Vacavant | Topological and Geometrical Reconstruction of Complex Objects on Irregular Isothetic Grids[END_REF]. Then, Vacavant et al.

consider the rectangles R 1 -F 2 and R 2 -F 2 . If R R 1 < R R 2 , they denote R 1 -F 2 = F 1 and R 2 -F 2 = F 3 .
The k-arc A is finally updated with respect to five main configurations (see Fig. 2).

Polygonal Reconstruction of an Irregular Object. The construction of the polygonal structure of E is performed by reconstructing each k-arc that recodes E. This stage is driven thanks to a visibility cone approach inspired from [START_REF] Sivignon | Discrete Analytical Curve Reconstruction without Patches[END_REF]

If R R 1 = R L 2 , F2 = ∅, when R R 1 = R R 2 , F3 = ∅ and finally F1 = ∅ in the case R L 1 = R L 2 .
(see also Fig. 3). Even if this algorithm is linear-time, it is a greedy approach that could leads to some very short segments and acute angles.

Fig. 3. The visibility cone approach incrementally produces a polygonal reconstruction with a partial preimage (left). In our contribution, we use the O'Rourke's algorithm in order to obtain a complete preimage representation (right). We also show an example of reconstruction that we describe in the section 3.

Unsupervised Polygonalization of Noisy Digital Contours

A Novel Approach to Vectorize Irregular Isothetic Objects

The polygonal reconstruction of E is again performed by reconstructing each karc that recodes E. Though, instead of decomposing a given k-arc A into segments lying into a visibility cone like in [START_REF] Vacavant | Topological and Geometrical Reconstruction of Complex Objects on Irregular Isothetic Grids[END_REF], we decompose it into straight k-arcs, i.e. sets of k-adjacent cells that can cover a straight line and whose preimage is thus not empty. In Fig. 3 (right), we present the result of this kind of process on a simple k-arc decomposed into four straight parts. Originally, O'Rourke's algorithm [START_REF] O'rourke | An on-line Algorithm for Fitting Straight Lines between Data Ranges[END_REF] aimed to solve a linear inequality system. Given n ranges {[α k , ω k ]} k=1,n ordered by time t k , with t 1 < . . . < t n , this approach computes all the lines u = mt + b that pass through each range, i.e. all pairs (m, b) such that α k ≤ mt k + b ≤ ω k . In our case, the input ranges are the intersections between two successive cells of A. These intersections are vertical straight segments (possibly degenerated as a point) whose the extremity of greatest (resp. smallest) y-coordinate is called upper (resp. lower) input point. Due to the construction of the k-arc, the vertical straight segments are of increasing x-coordinate and O'Rourke's algorithm can thus be applied in order to compute the preimage of each straight part of A.

Even if O'Rourke originally explains its algorithm in the dual plane (m, b) [START_REF] O'rourke | An on-line Algorithm for Fitting Straight Lines between Data Ranges[END_REF], we can avoid explicit transformations and only work in the primal plane (u, t). The preimage is implicitely described by some consecutive vertices of the lower (denoted by L) and upper (denoted by U) convex hull of respectively the upper and lower input points.

We now describe a first algorithm that takes into account the shape of the preimage of each straight parts (Algorithm 1-C2, lines 7-25). It computes a polygonal line that completely lies within the k-arc.

In Fig. 4, we depict several iterations of this algorithm on a straight part. Points p a and p c are initialized as the first two points of U, while p b and p d as the ones of L (Fig. 4-(a)). If p c .x > p d .x (i), we move forward p b and p d , whereas if p c .x < p d .x (ii), we move forward p a and p c . If p c .x = p d .x (ii), we move both pairs of points. In either case, the middle of the intersection between a vertical line passing by p c .x in case (i) (Fig. 4-(c)) or p d .x in case (ii) (Fig. 4-(b)) and the preimage is the new vertex of the polygonal reconstruction. The process is linear-time and the resulting polygonal line lies inside the k-arc. We also develop an other algorithm (Algorithm 1-S2, lines 4-6) that constructs one straight line per k-arc passing through the middle of the first and last input range. Even if the resulting polygonal line may be partly out of the k-object, this is an interesting way of decomposing an irregular object into a few line segments.

We show in Fig. 5 an example of the use of our contribution (computation of the complete preimage and reconstruction into line segments with Algorithm 1-Algorithm 1: Polygonal reconstruction of a straight k-arc based on its preimage.

input : a preimage P computed from a straight k-arc A, represented with its upper convex hull points U of size nU and the lower convex hull points L of size nL, and the version selected output: a polygonal structure computed inside P, stored in the list of points R u ← 0, l ← 0 ;

1 pa ← U [u], pc ← U [u + 1], p b ← L[l], p d ← L[l + 1] ; 2 d ← pc.x -p d .x ; 3 if version = S2 then {Version S2: Simple and Straight reconstruction} 4 p1 ← middle(L[0], U [0]) ; 5 p2 ← middle(L[nL -1], U [nU -1]) ; 6 R ←
23 u ← u + 1, l ← l + 1 ; 24 pa ← pc, pc ← U [u], p b ← p d , p d ← L[l] ; 25 d ← pc.x -p d .
x ; 26 while u < nU ∨ l < nL ; 27 return R ; 28 C2) on an irregular object, result of a quadtree decomposition. In the following, we show how to use these algorithms to vectorize noisy digital contours.

Polygonalization of Noisy Contours by an Irregular Discrete Approach

We now propose to analyze noisy digital contour by using Kerautret and Lachaud's local noise detector [START_REF] Kerautret | Multi-Scale Analysis of Discrete Contours for Unsupervised Noise Detection[END_REF]. This a method for estimating locally if the digital contour is damaged, what is the amount of noise and what are the highest resolution at which a part of the contour should be considered as noise-free. Depending on the selected resolution, a part of the contour is covered by a pixel of a given size at the initial resolution. The higher the amount of noise is, the biggest the pixels are. In Fig. 6-(b), we show an example of the output of this parameter-free algorithm applied to the noisy digital object depicted in Fig. 6-(a).

As shown in Fig. 6-(b), the resized pixels overlap and thus cannot be viewed as an irregular isothetic object (Definition 1). However each resized pixel contain a given number of pixels (at the initial resolution) so that set of resized pixels cover a subset of the input image. This subset, which is an irregular isothetic object, is the input of our reconstruction method described in the previous sections.

The input digital contour is always homotopic to a ring (one connected component and one hole). However, as in [START_REF] Rodriguez | Adaptive Pixel Resizing for Multiscale Recognition and Reconstruction[END_REF], the set of resized pixels may not be homotopic to the input digital contour. We can imagine that the set of resized pixels may not contain any hole or may contain more than one hole.

Thanks to the Reeb graph, which encodes the topology of the input object, we can decide whether we are in a general case (one cycle) or not (none or more than one cylce).

Moreover, in the general case, we can choose to not process the k-arcs that do not belong to the cycle so that the polygonal reconstruction is a simple polygon (Algorithm 2). For instance, only reconstructing the cycle linking nodes s, m, m, m in Fig. 6-(d) is a way of avoiding extra polygonal lines pointed by arrows in Fig. 6-(c). Algorithm 2: Filtering of the k-arcs and the Reeb graph encoding a noisy object.

input : the set of k-arcs recoding it A and its associated Reeb graph G output: the sets A, G are filtered in order to obtain a polygonal contour foreach k-arc a ∈ A do 1

x: the associated edge of a in G ;

2 if x = b -m ∨ x = b -s ∨ x = s -e ∨ x = m -e then 3
remove x from G ; 4 remove a from A ; 5 return A, G ; 6

Experimental Results

To experiment the quality of the proposed approach, we first consider a polygonal shape that was perturbed by a Gaussian noise, with different standard deviations (σ 0 = 0, σ 1 = 75, σ 2 = 125, σ 3 = 175). These images were generated with two different grid sizes h = 1 and 0.5 (Fig. 7 (a,c)). The resized pixels (illustrated on images of Fig. 7 (b,d)) were obtained from the digital contours extracted by using a simple threshold (set to 128) (images (e,i)). The quality measures were given by the total number of points (n), the mean minimal euclidean distance (E d ) between the source contour points P i to the resulting polygon, and the error on tangent orientations (θ 2 err ). The measure E d was obtained after associating each contour points P i of the initial shape (non noisy) to the nearest consecutive vertex pair V k , V k+1 . These associations were also used to determine the tangent error θ 2 err where θ err is the angle between the tangent vector defined from V k , V k+1 and the tangent provided by the λ -M ST estimator [START_REF] Lachaud | Fast, accurate and convergent tangent estimation on digital contours[END_REF] applied on the source discrete contour.

The experiments confirm the awaited improvements provided by the Algorithm 1-C2 (Alg1-C2 in short) in comparison with the use of the algorithm based on visibility cone [START_REF] Vacavant | Topological and Geometrical Reconstruction of Complex Objects on Irregular Isothetic Grids[END_REF] (denoted as Alg-VC). It is visible especially for the tangent error measure θ 2 err but also for the distance error E d . The second variant Algorithm 1-S2 (Alg1-S2 in short) produces a more compact representation while preserving a moderate tangent error θ 2 err . However this last algorithm is less convenient on the point of view of the E d error.

The Algorithm 1-C2 was also experimented on real images of characters, acquired from a photographed document. A given threshold was used to extract the digital contours on which the resized pixels were computed (as illustrated on the second row Fig. 8). We thus show that our vectorization algorithm could be applied in document analysis systems.

Finally, we compare our methods with algorithms developed by Nguyen and Rennesson [START_REF] Nguyen | Parameter-free method for polygonal representation of the noisy curves[END_REF] which are based on a global optimization scheme in association with the Marji's criteria (MC) or another one proposed by the authors (NC). In Fig. 9, we present the polygonal contour obtained from our methods, and from the NC and MC algorithms which are both parameter free approaches. For each experiment, we measure the Hausdorff error (δ H ) and the previously described errors. The comparisons show that the proposed approaches are less compact than both the NC or MC but provide better precision for the δ H and E d errors.

On the point of view of the tangent orientation error θ 2 err our approaches with Alg1-C2 or Alg1-S2 are comparable with the one of the NC algorithm.

Conclusion and Future Works

In this paper, we address the problem of reconstruction of noisy digital contours. We transform the resized pixels obtained by Kerautret and Lachaud's algorithm [START_REF] Kerautret | Multi-Scale Analysis of Discrete Contours for Unsupervised Noise Detection[END_REF] into an irregular isothetic object recoded in a set of k-arcs whose topology is stored into a Reeb graph. We then vectorize it with two different linear-time methods that improve a previous work of Vacavant et al. [START_REF] Vacavant | Topological and Geometrical Reconstruction of Complex Objects on Irregular Isothetic Grids[END_REF].

As a future work, we plan to use the Reeb graph to deal with degenerate cases. We also want to consider the possibility to improve the reconstruction by using information of flat and curved parts of the processed noisy objects, since this information can be extracted from the meaningful scale detection [START_REF] Kerautret | Multi-Scale Analysis of Discrete Contours for Unsupervised Noise Detection[END_REF].

Fig. 1 .

 1 Fig. 1. (a) An example of an irregular object E (left), the final recoded structure with arcs, the obtained polygonalization (right) and the Reeb graph associated to the order defined on E (bottom) [16]. In (b), we show the recognized k-arcs and the associated Reeb graph for some iterations of this algorithm, in respect to the L order.

Fig. 2 .

 2 Fig. 2. Description of rectangles F1, F2 and F3 in the update procedure. When R R 1 < R R 2 (a and b), R1 -F2 = F1 and R2 -F2 = F3, else R1 -F2 = {F1, F3} (c, d and e).If R R 1 = R L 2 , F2 = ∅, when R R 1 = R R 2 , F3 = ∅ and finally F1 = ∅ in the case R L 1 = R L 2 .

Fig. 4 .

 4 Fig. 4. Illustration of Algorithm 1-C2 on a preimage obtained from O'Rourke process. (a) is the initialization step, (b) is an update step of the reconstruction implying a lower input point, (c) a upper one, and (d) is the obtained polygonal reconstruction of the underlying straight k-arc. Algorithm 1-S2 consists in joining the first and the last point of this reconstruction.

Fig. 5 .

 5 Fig. 5. Illustration of our contribution on an object digitized with a quadtree (a). (b)is the complete preimage computed on each k-arc encoding the object. One could note that the k-arc at the bottom is decomposed into two straight k-arcs. In (c), we present the reconstruction of a single k-arc, and the associated preimage and upper/lower convex hull points. We also depict the complete polygonal reconstruction of the object, constructed inside the preimage (d), and the final contour obtained with our filtering procedure explained in Section 3.2

Fig. 6 .

 6 Fig.6. From a noisy contour (a), we build a set of resized pixels (b). Then, we filter the result of our vectorization algorithm by removing k-arcs that do not belong to the polygonal minimal contour (the ones pointed by arrows). To do so, we remove their associated edges in the Reeb graph (d).

Fig. 7 .

 7 Fig. 7. Illustration of the reconstruction algorithms. The first row shows the multiscale levels obtained from the source contours (e,i). The second and third rows show error measures for algorithms Alg1-VC (that uses previous work), Alg1-C2 and Alg1-S2 described in this article. These results were obtained with resp. the scale h = 1 and 0.5

Fig. 8 .

 8 Fig. 8. The meaningful boxes extracted from scanned characters (center), and the final reconstruction we propose with Alg1-C2 (bottom).

Fig. 9 .

 9 Fig.9. Comparisons of the proposed approaches with others recent parameter free approaches[START_REF] Nguyen | Parameter-free method for polygonal representation of the noisy curves[END_REF].

⋆ This work has been supported by the French National Agency for Research with the reference ANR-10-CORD-005 (REVES project).