Laurence Rideau

Bernard Serpette

Cédric Tedeschi

Formalization and Concretization of Ordered Networks

Keywords: Formalization, peer-to-peer systems, routing Formalisation, systèmes pair-à-pair, routage

Overlay networks have been extensively studied as a solution to the dynamic nature, scale and heterogeneity of large computing platforms, and are a fundamental layers of most existing peer-to-peer networks. The basic mechanism offered by an overlay network, is routing, i.e., the mechanism enabling the delivery of messages from any node to any other node in the network. On top of routing are built crucial functionalities of peer-to-peer networks, such as networks maintenance (nodes joining and leaving the network) and information distribution and retrieval. Over the years, different topologies and routing mechanisms have been proposed in literature. However, there is a lack of formal works unifying these different designs and establishing their correctness. This paper proposes a formal common basis, partially validated with the Coq theorem prover, with the nice property of only requiring the definition of a total order on the nodes. We investigate how such a basic design can be used to build deadlock/livelock-free algorithms for routing, node insertion, and node deletion in the fault-free environment. The genericity of our design is then explored through the construction of orders on nodes corresponding to different topologies commonly encountered in the peer-to-peer domain. To validate the methodology proposed, a simulator tool was developed. This tool is able, given the definition of an order and the definition of shortcuts, to simulate the corresponding overlay network and to explore its performance.

Introduction

Overlay networks, whose primary advantage is to abstract out the difficulties of physical routing, is a crucial element of the leveraging of the emerging distributed systems, which are infinitely large and heterogeneous. Peer-to-peer systems make an extensive use of it [START_REF] Park | A survey on peer-to-peer overlay network schemes[END_REF].

A fundamental building block characterizing an overlay network is its routing mechanism. Routing is meant to deliver a message emitted at any node to any other node in the overlay. An important requirement is that this routing process should remain correct, in spite of nodes joining and leaving the networks, making the overlay grow and shrink over time.

A class of overlay networks broadly used over the years, is based on oriented rings [START_REF] Stoica | Chord: A Scalable Peer-to-Peer Lookup service for Internet Applications[END_REF][START_REF] Rowstron | Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems[END_REF]. A lot of work went into enhancing such overlays with different optimizations and extensions, related to both functional and performance issues. Such examples include load balancing [START_REF] Karger | Simple efficient load-balancing algorithms for peer-topeer systems[END_REF] or the support for complex queries [START_REF] Schmidt | Squid: Enabling Search in DHT-Based Systems[END_REF]. Besides ring overlay networks, different topologies have been proposed, such as cartesian spaces [START_REF] Ratnasamy | A Scalable Content-Adressable Network[END_REF] and hypercubes [START_REF] Schlosser | Hypercup -hypercubes, ontologies, and efficient search on peer-to-peer networks[END_REF]. While the routing processes in these overlays all typically grows logarithmically with the size of the network, their design significantly differs.

Each overlay follows a particular topology and routing mechanism; each overlay has its own way to define shortcuts, i.e., a set of distant links, maintained by each node in a routing table, for the routing efficiency. Although these overlays share a common goal (physical network abstraction and efficient message delivery) and common features (routing, node insertion, node deletion), very few works attempted to give them a common formal basis.

Existing works

We can find a lot of recent works aiming at maintaining overlay networks in faulty or adversarial settings [START_REF] Hayes | The forgiving tree: a self-healing distributed data structure[END_REF][START_REF] Clouser | Tiara: A self-stabilizing deterministic skip list[END_REF][START_REF] Hayes | The Forgiving Graph: a Distributed Data Structure for Low Stretch under Adversarial Attack[END_REF][START_REF] Jacob | A Self-stabilizing and Local Delaunay Graph Construction[END_REF][START_REF] Jacob | A distributed polylogarithmic time algorithm for self-stabilizing skip graphs[END_REF][START_REF] Bansal | A scalable algorithm for maintaining perpetual system connectivity in dynamic distributed systems[END_REF][START_REF] Kniesburges | Re-chord: a self-stabilizing chord overlay network[END_REF]. Hayes et al. proposed the Forgiving Tree [START_REF] Hayes | The forgiving tree: a self-healing distributed data structure[END_REF], a distributed structure that maintains, under periodic adversarial deletion of one of its node, strong guarantees on its diameter and degree. Upon each adversarial deletion, both the time needed to recover and the number of messages sent are constant. The authors have extended their work to adversarial insertions of nodes in [START_REF] Hayes | The Forgiving Graph: a Distributed Data Structure for Low Stretch under Adversarial Attack[END_REF], but still with one adversarial move at a time. In [START_REF] Bansal | A scalable algorithm for maintaining perpetual system connectivity in dynamic distributed systems[END_REF], a spanning tree maintenance algorithm is proposed, also providing strong guarantees about the degree and the diameter, but under an infinite arrival model with bounded concurrency (the number of concurrently active nodes at a given time is bounded). However, all these algorithms assume that the processes are reliable.

A recent series of work proposed self-stabilizing overlay structures. In [START_REF] Clouser | Tiara: A self-stabilizing deterministic skip list[END_REF], a self-stabilizing skip list is proposed. In [START_REF] Jacob | A distributed polylogarithmic time algorithm for self-stabilizing skip graphs[END_REF], a variant of the skip graph distributed structure is made selfstabilizing, with the main advantage of achieving a sublinear convergence time, which represents an improvement over the earlier self-stabilizing dynamic network structures. In [START_REF] Jacob | A Self-stabilizing and Local Delaunay Graph Construction[END_REF], the same authors came up with a similar result for Delaunay graphs. Recently, they proposed a selfstabilizing version of the famous Chord protocol [START_REF] Kniesburges | Re-chord: a self-stabilizing chord overlay network[END_REF].

All these works are based on repair mechanisms ensuring a quick recovery after a set of transient faults or attacks. Only few works have the goal of formally establishing the full continuity of the basic features of the overlay (routing, insertion, deletion) in a fault-free, non-adversarial setting. This paper follows this path, as maintaining the topology in the fault-free environments appears to be, in itself, a non trivial task. Also, as argued in [START_REF] Li | Concurrent maintenance of rings[END_REF], which exposes some formally-proved results for ring-based networks, and thus constitutes our closest related works, the fault-free setting remains a very relevant area to be explored, as the design of fault-tolerant protocols could naturally build upon formally proven results in fault-free environments. Note that, in the work in [START_REF] Li | Concurrent maintenance of rings[END_REF], the protocols proposed still suffer from livelocks. We can find a CCS formalization/verification of the lookup process in [START_REF] Borgström | Verifying a structured peer-to-peer overlay network: The static case[END_REF], but the dynamic insertion and deletion of nodes were not considered. In [START_REF] Lynch | Atomic data access in distributed hash tables[END_REF], Lynch et al. propose an interesting approach for ensuring atomic data access in the Chord overlay network. However, with such a protocol, there is no insurance that some message will not be sent to a node that already left the network. Our approach aims also at suppressing this drawback.

Contributions of this report

Our goal is to extract a minimal formal basis on top of which can be constructed and compared different overlays. Our contribution presents two facets. [START_REF] Asano | Space-Filling Curves and their Use in the Design of Geometric Data Structures[END_REF] We give, based on the minimal requirement of a total order over the nodes, formal generic deadlock/livelock-free algorithms for routing, inserting and deleting nodes. For the sake of correctness, this specification was tested with the Coq theorem prover [START_REF] Bertot | Interactive Theorem Proving and Program Development. Coq'Art: The Calculus of Inductive Constructions[END_REF]. [START_REF] Bansal | A scalable algorithm for maintaining perpetual system connectivity in dynamic distributed systems[END_REF] We show how this generic formalization can be used to build different topologies, subject to a dedicated order and a way to define shortcuts. To validate and illustrate the methodology, we finally discuss results obtained with a simulation tool that, given these order and shortcuts, automatically builds the corresponding overlay and gives some performance indicators about it.

Outline. Section 2 details the formal minimal definition of a ordered network. Section 3 discusses the linearization process of any topology into a ring, and compares by simulation, several of the most commonly encountered topologies. Section 4 summarizes the paper and gives hints on future work.

Preliminaries. Programs written in the paper use a light Java style where "new F oo(. . . f ield i = E i . . .)" creates an object of type F oo which implicitly has a field f ield i and this field, for the created object, will have the value computed by E i . Implicitly, variables of Type F oo are named f oo. Methods of F oo are declared as "f oo.method(. . . , arg i , . . .) = . . ." where f oo may be used as the classical this in the body of the method. Methods can be overridden. Field access and method invocation are used with the classical dotted notation (obj.f ield and obj.method(. . .)).

Inria 2 Formal Specification of Ordered Networks

A network is a graph of nodes where edges represent (physical or logical) connections. We denote by W the set of nodes of a network. The main role of the network is to dispatch messages between nodes, based on a mechanism known as the routing process. To locate the destination of a message, each node has a unique identifier, e.g., IP addresses are the identifiers for the Internet. In the considered logical networks, each node is also responsible for the management of a set of identifiers (also known as keys), i.e., a specific portion of the identifiers space. Thus, such a network does not resolve only queries such as "send a message to the node whose identifier is id", but supports more general queries such as "send a message to the node managing the identifier (or key) id". Note that, when nodes manage their own identifier, the second style of queries encompasses the first one. In the networks studied in this paper, we will force, by construction, the uniqueness of identifiers : an identifier is managed by one and only one node. We denote by T the domain of identifiers, and by n.id the particular identifier used to identify node n. One important property to be tackled is that networks are dynamic: nodes can join and leave the network at anytime. Moreover, we are attached to guarantee that messages reach their destinations, i.e. that the network does not lose messages during the routing process.

Orders and Alignments

The approach we have followed is to consider a hamiltonian cycle over the network : a cycle which traverses all nodes of the graph once and only once.

Ordered nodes. Hamiltonian cycles are generally extracted from an existing graph, which is known to be an NP-complete problem. In our case, the cycle is established at the beginning, when the network is initiated with a first node, and preserved during insertion and deletion of nodes. As we consider oriented graphs, each node is only required to maintain its successor in the cycle. If n is a node of the network, we will denote by n.succ the identifier of the successor of n in the cycle, i.e., nodes are created with something resembling: "new N ode(id = . . . , succ = . . . )". It is particularly convenient to consider a strict order < over T . Given this order, a finite set of nodes can be sorted, thus giving a Hamiltonian path. The cycle is achieved by artificially connecting the two bounds of the path. To ensure the uniqueness of identifiers, we also assume an equality relation (=) on T . We have abstracted both relations < and = (and implicitly ≤) with a unique function ((T, T, bool) → bool), denoted x < b y, which considers the case of equality of x and y via the boolean b. If < and = are known, we can define this function by :

x < b y = x < y ∨ (b ∧ (x = y)) (1)
The strict order properties of < and the equivalence properties of = are reported on < ? with the following definition :

< ? is a conditional order ⇔    (ref lexivity) x < b x = b (symetry) x < b y = y < b x (transitivity) x < b y ∧ y < c z ⇒ x < b∧c z
It is easy to check that Definition 1 introduces a conditional order. Reciprocally, conditional orders are strong enough to define an order with x ≤ y = x < true y, a strict order with x < y = x < f alse y and an equivalence with x = y = x < true y ∧ y < true x.

Alignments. Considering the hamiltonian cycle, the main property we will consider is the alignment of three nodes a, b and c. Informally, these three nodes are said to be aligned if, starting from a and following the cycle, we reach b before c. As for conditional orders, we have to consider the possibility of equalities between these three nodes. Using < ? , this predicate can be expressed by a function ((T, T, T, bool, bool, bool) → bool) defined by :

align(a, b, c, ab, bc, ca) =        match a < ab b, b < bc c with | true, true ⇒ true | f alse, f alse ⇒ f alse | _, _
⇒ c < ca a The two first booleans ab and bc tell if the interval is open or closed, for example align(a, b, c, true, f alse, _) has a meaning similar to b ∈ [a, c[. An ambiguity can appear when a and c are equal, as the interval [a, a[ can be either considered as the empty set or as the whole set T . The role of the last boolean ca is to give a meaning to the alignment in these particular cases. To consider [a, a[ as the empty set, ac should be f alse, to consider it as T , ac should be true. Hence, align(a, x, a, true, f alse, true) is true for all a and x. We now devise four main properties of align : (i) The three nodes can be freely rolled : align(a, b, c, ab, bc, ca) = align(b, c, a, bc, ca, ab) (ii) The reflexivity of the conditional order implies a second property, which generalizes the previous discussion about the equality of bounds : align(a, b, a, ab, ab, aa) = aa (iii) Following the symetry property of conditional order, the third property shows the consequence of exchanging two nodes : align(a, b, c, ab, bc, ca) = align(a, c, b, ca, bc, ab) (iv) Finally, the last main property is a consequence of transitivity : align(a, b, c, ab, bc, ca) ∧ align(a, c, d, ca, cd, da) ⇒ align(a, b, d, ab, bc ∧ cd, da) Topologic invariants. With the align definition, we can formalize the invariant needed for structuring the network: (i) each node has a unique identifier, (ii) each node has a successor belonging to the network, (iii) a node manages identifiers (keys) between itself and its successor 1 and each identifier is managed by one and only one node :

W is well f ormed ⇔        (uniqueness) ∀a, b ∈ W ; a.id = b.id ⇒ a = b (successor) ∀a ∈ W ; ∃b ∈ W ; a.succ = b.id (keys) ∀k ∈ T ; ∃!a ∈ W ; align(a.id, k, a.succ, true, f alse, true)
The last property can be reformulated by : ∀a, b ∈ W ; align(a.id, a.succ, b, true, true, true)

1 Such a simple consistent hashing scheme is for instance used in the Chord protocol, but others have been proposed in literature.

Inria

Routing

All messages received by a node are stored in a dedicated queue on this node. The main job of a node is to extract and analyze messages from this queue, one message at a time. An extracted message may either have reached its destination or must be forwarded to another node. This can be modeled by the following pseudo-code of the analyze method :

node.analyze(message) =    if message.arrived(node.id, node.succ) then message.eval(node) else node.f orward(message)
where the arrived method tests if the message whose target is, let's say, the key k, has reached its destination :

message.arrived(a, b) = align(a, k, b, true, f alse, true)

Therefore, by the third (keys) invariant, the eval method (evaluating the content of a message) will be called on the correct node. We will see later that specific messages use a different arrived method.

If a message is in transit on a node, it must be forwarded to another node. The simplest way to do so is to send this message to the successor of the node. In this way the message will traverse the cycle until reaching its destination. However, to avoid a long traversal (linear in the number of nodes), we give a chance to this message to find a shortcut :

node.f orward(message) = let link = node.shortcut(message) in link.send(message) (3)
The shortcut method is a collaboration between the node and the message. The node proposes to the message all nodes it knows of2 and the message selects those that are shortcuts in its own point of view. Finally, the node returns the furthest one (the locally best shortcut) :

node.shorcut(msg) =        result = node.succLink foreach link in node.knownLinks() do if msg.isShortcut(result.id, link.id) then result = link
To allow for such shortcuts, we need to define the links properly. A link is the association of (i) an identifier, (ii) a contact, which is the minimal and transmissible (serializable) information required for opening a connection (e.g., an IP address and a port number), and (iii) a connection, i.e., all information needed to communicate with this node (e.g., sockets). Thus a link is created with :

new Link(id = . . . , contact = . . . , connection = null) Note that the communication, and so the use of the connection field, is abstracted by the link.send(message) invocation as well as in the f orward method definition. node.succLink is the link a node maintains to its successor (node.succ is equivalent to node.succLink.id.) A link is initially created without the physical connection which will be started by the contact. At this stage, we do not specify when this physical connection is established -an eager version will do it when the link is created, a lazy version will wait for the first invocation of a send to create this physical connection.

Quite similarly to Definition 2 of message.arrived, for a message whose purpose is to contact the node managing the identifier k, the isShortcut method should be defined as : Figure 1 illustrates one routing step when a node a receives a message for the identifier k. Let us assume that n 2 is the node which manages k. Dashed lines represent the succLink variables. Among all links known by a, pictured with thick arrows, the furthest one but still before the destination k is chosen. Thus, for the example, Node n 1 is returned by the invocation of the shortcut method. The message will be sent to n 1 and, if no insertion/deletion occurs around n 1 , this message will reach its destination after its transit in n 1 . (n 2 is the successor of n 1 .)

message.isShortcut(a, b) = align(a, b, k, f alse, true, f alse) (4)

Insertion

The routing process relies on invariants to ensure that all destinations are reachable. Pursuing our formalization effort, we now have to ensure that these invariants are preserved by insertion/deletion of nodes. Figure 2 shows the informal behavior of insertion/deletion. To preserve the invariant, when inserting b between a and c, we must ensure align(a.id, b.id, c.id, f alse, f alse, true). The two f alse values ensure the uniqueness of identifiers.

Inria

For the insertion of node (known by its contact information) with a given identifier, a particular insertion message should be created with : new Insert(id = . . . , contact = . . .)

On receipt, the evaluation of this message can be described as follows :

insert.eval(node) =                        if align(node.id, insert.id, node.succ, f alse, f alse, true) then let link = node.succLink in node.succLink = new Link(id = insert.id, contact = insert.contact) node.succLink.send( new Start( id = insert.id, succ = link.id, contact = link.contact))
Following the definition of the method analyze on nodes discussed above, when an eval method is called on a message, this message has reached its destination. The only difference between Definition 2 of message.arrived and the precondition to insert a node, is the first boolean of align, which is set to f alse. With this restriction, we prevent a node with an already used identifier to be inserted, thus ensuring the uniqueness of identifiers in the network.

Once the invariant is ensured, the evaluation of an insert message consists in: (i) creating a new link with the given contact, thus initiating a connection between the creator node and the new node, and (ii) sending a message to the new node with the required information, i.e., its identifier and the identifier and contact to its successor.

The eval method of a Start message consists only in setting the identifier and the link to the successor : start.eval(node) = node.id = start.id node.succLink = newLink(start.succ, start.contact)

Figure 3, depict the insertion steps. When b is inserted between a and c, the insertion proceeds in two steps. First, on receipt of the insert message, the link between a and b is created and the start message is sent to b. Second, on receipt of this start message, the link between b and c is established. Note that, between these two instants, the invariant is not clearly preserved. From a's point of view, b is active (i.e., considered in W ) as soon as the insert method is completed. After that, a can start to forward some messages to b. From b's point of view, it becomes active only on receipt of its start message. This hardly shows that we assume that the order in which messages are sent must be preserved on the receiver's side : if a message overtakes the start message during the connection between a and b, this message will not read the valid values of identifier and successor of b, leading to potential incorrect routing.

Deletion

Compared to insertion, even if at a first glance only one link needs to be updated, as shown in Figure 2, deleting a node is far more complicated. As we devise in details in the following, a node can not simply leave the network without potentially inducing inconsistencies in the routing process and losing messages. Roughly speaking, as illustrated in Figure 4, four steps are required for a proper deletion. Firstly, when node b decides to leave the network (we assume it does so on receipt of a quit message from its application layer), b first requests the collaboration of its predecessor (a on Figure 4) by initiating a particular message delete(b.id). Secondly, after the routing process, when a receives this message, it sends a last message leave(a.contact) to b and closes the connection with b. This last message contains the information to call back a when necessary. Thirdly, on receipt of the leave(contact) message, b flushes all its pending messages, closes the connection to its successor and calls its predecessor back with the identifier and contact of c. Finally, on receipt of the exited(id, contact) message, a ends the deletion steps by setting its successor with the message's arguments.

Deletion's flow. Let us now review in detail the message exchanges involved in a node's deletion. As mentioned above, the deletion process starts when a node b receives a quit message from its application layer. Since only the predecessor of b can perform the deletion, this quit message is transformed into a delete(b.id) message whose informal meaning is : if your successor is identified by b.id, then delete it. It would clearly be an improvement for each node to have a direct access to its predecessor, so it could contact it directly on deletion. However, if one looks back to Figure 3, during insertion, the predecessor of a node is not always clearly defined. This requires for the delete message to follow the general routing process : If the notion of predecessor (e.g., x-1 for natural numbers) is defined for Type T , we can keep the standard definition of arrived and isShortcut by sending a message delete(pred(node.id)) to reach the predecessor. However, not every type T necessarily supports a pred operator. This is the case, for instance, of rational numbers and strings of arbitrary length (e.g., the predecessor of "foo" is "fonzzzz. . . " with an undefined number of 'z').

As expected, a node evaluating a Delete message transmits a Leave message to its successor and closes the connection. Note that, since this message will be the last one sent with this connection, some improvements are possible in the close protocol (for example, some steps for closing a TCP connection can be removed). Even if the essential meaning of a Leave method is to reply with the current successor to the sender, the main problem is then to ensure that the leaving node will not receive further messages. As mentioned in the eval method of Delete messages, the predecessor closes its link, but all others links to the leaving node, open for shortcut purposes, are still alive. The first action a node has to do on a Leave arrival is to close all incoming links. We assume that a closeIncomings() method is provided for this. At this stage, if the node refuses all new connection, the queue of incoming messages may be non-empty, but cannot grow anymore. Finally, to exit, the leaving node can send to itself a specific Shutdown message : leave.eval(node) = node.closeIncomings() node.send(new Shutdown(contact = leave.contact));

Due to the previous closeIncomings(), a Shutdown message is necessarily the last message to be received on a leaving node. In other words, when a node evaluates a Shutdown message, its queue of incoming messages is empty. The only thing that remains to be done then is advising its predecessor, with an Exited message, giving the necessary information to set its new succLink :

shutdown.eval(node) =            let link = shutdown.contact.open() in link.send( new Exited(id = node.succ, contact = node.succLink.contact)) node.succLink.close()
The deletion process ends when the predecessor evaluates the Exited message whose purpose is only to set the link to its new successor : exited.eval(node) = node.succLink = new Link(id = exited.id, contact = exited.contact))

Deletion automata. The deletion process shown on Figure 4 is correct only if no other messages are sent to the leaving node concurrently. For instance, let us assume node a receives an insert message after sending the leave message, then a must clearly wait for the receipt of the exited message before performing the insertion, otherwise it is unable to provide the correct successor information to the inserting node. To be more accurate, let us provide a state to each node of the network. The state of a node changes depending of the message it receives. Figure 5 shows the state automaton of nodes. Vertices represent the possible states of nodes, and edges are the possible transitions between states. Edges are labelled with m 1 (code) → m 2 representing the fact that, on transition, the node receives the message m 1 , executes code and sends the message m 2 . At the beginning of its lifetime, i.e., on receipt of the first start message, a node's state is set to Run. It remains so until receiving either a quit (from its application layer) or a delete message (from its successor). In the Quit state, a node waits for the leave message but may itself be requested to delete its successor (via the reception of the dedicated delete message.) W ait and W aitQuit states are similar except that in the W ait state, a node is deleting its successor, but may be requested to leave (by the reception of a quit message from its application layer). (Note that this may occur only once in a node's lifetime). If a is in W ait state, it waits for the actual termination of its old successor b. As long as the new successor c is not established, messages involving the old successor b, i.e., the node to be deleted, must be memorized. Once the exited message is received, all memorized messages can be pushed back in a's queue for future analysis.

This memorization also concerns insert messages. An insert message can not be processed in this state since we do not have a properly established successor to send to the inserted node in its start message. Nevertheless, all other messages can be either evaluated if they do not concern insertion, or forwarded to their next hop, as far as b is not the target. In the same way, in a W aitQuit state, an incoming leave message will be memorized until the node goes back to the Quit state, as a node has to establish its new successor before leaving the network (delete before leaving). In a W aitQuit state, an exited message sent after receiving a leave message would Inria contain information on the successor which is not valid.

Finally, note that the memorized messages can not be directly forwarded to the new successor c when the exited acknowledgment is received: some of these messages may concern a itself, since, by receiving the exited acknowledgment, a now manages the identifiers of the deleted node b.

Chains of deletions. If some of successive nodes decide to leave the network at the same time, it may appear a chain of nodes all with the state W aitQuit, all waiting for the exited acknowledgment of their successor. Only the rightmost node can start sending the acknowledgment. In other words, the chain is destroyed by the right. Figure 6 shows another automaton where chains of leaving nodes are destroyed by the left. This automaton is a simplification of the one pictured in Figure 5. Similarly, a quit message is memorized in a W ait state, and a Quit state prevents a leave message to be emitted on receipt of a delete message by memorizing it. Note that, with this new automaton, a node in a Quit state can receive only one delete message. A boolean is sent in the exited message indicating if a delete message was received. Thus, when a node in W ait state receives an exited(true) message, it has to stay alive to delete its new successor. In contrary, on receipt of an exited(f alse) message, a node can freely return to its Run state, having the opportunity to (re)evaluate a quit message memorized during its W ait state.

Solving the deletion deadlock. Unfortunately, both automata in Figures 5 and6 contain deadlocks. In the first one, it appears when all nodes of network reach the W aitQuit state at the same time.

Figure 7 shows a simple sequence of messages leading to a deadlock in a network of two nodes a and b following the automaton depicted by and b decide to leave the network. So both of them emit their delete message and move to a Quit state. If they receive this delete at the same time, they both emit a leave and move to W aitQuit state. But those leave will be memorized and never analyzed. For the second automaton, the deadlock appears more quickly since the delete messages will not be analyzed.

It is easy to check that in a network of two nodes a and b, if a behaves according to one automaton, and b according to the other, then no deadlock can occur. The property remains true for any network, as long as it exists at least one node that acts according to one automaton and one node according to the other. This constraint can be easily preserved on insertion/deletion if exactly one node, named the leader, acts according to one of the two automata (all the other nodes acting according to the other one). A network with only one node must contain the leader.

There are two ways to determine the leadership. The first way is to elect as leader the node which satisfies the property node.id ≥ node.succ. This node is unique : it is the node with the highest identifier with respect to the order. In this case, the leadership may change on insertion/deletion: (1) If the leader inserts a node with a higher identifier, it releases its leadership to the new node. (2) Any node deleting the leader becomes the new leader. But, looking closer to this second rule, we can check that it is sufficient to ensure the uniqueness of the leader: a leader can remain the leader until it is deleted, and the node deleting it becomes the new leader. The only drawback of this second method is that another boolean must be sent in exited message stating if the deleted node was the leader or not.

Concretization of Ordered Networks

As our specification and algorithms are generic and provable for an oriented ring overlay network, it gives the opportunity to formally study any topology that can be mapped onto an oriented ring, or as we already mentioned, that contains a Hamiltonian cycle, which appears to be the case for many topologies commonly encountered in P2P systems (cartesian spaces, hypercubes, butterflies, trees, etc.) To apply our specification to a given topology T , we need to consider two things, namely mapping and shortcut.

Mapping. The first thing needed is to find a mapping of T onto an oriented ring, i.e., determine a function associating a node to a unique id reflecting its location on the hamiltonian cycle. In other words, we have to find an order on the nodes. Once the topology is mapped, the previously presented algorithms can be apply, except those related to the order itself.

Inria

Shortcuts. As we specified in Section 2, each node maintains a set of routing links. Then, for each topology having its own properties (diameter, symmetry, . . . ), we need to find relevant links allowing to route queries efficiently in T . Sometimes, these links are intrinsically offered by T . Consider for instance the hypercube. Routing in the hypercube can be achieved using the neighbors of nodes (neighbors of n are all nodes having an identifier differing from n.id on one and only one bit.)

Landmarks. However, we need to take into account the fact that only a subset of possible nodes are effectively in the network. (The set of ids is larger than the set of actual nodes.) Moreover, this subset is changing as nodes are joining and leaving the network. Thus, we need to define the set of ids considered as perfect potential shortcuts. These perfect shortcuts represent the ideal configuration towards which the set of actual links should tend. This set is referred to as landmarks henceforth. When starting, a node n computes its landmarks. Then, during its lifetime, a node maintains the best link possible for each id in landmarks.

Learning. Now, we can define the shortcut which is the association of a landmark id and a link. Recall that a link is a pair (link.id, link.contact) where shortcut = (landmark, link). As nodes will exchange messages for routing, they can include in these messages some information about their own set of links in order to improve shortcuts of other nodes. On receipt of such a message, a node may replace the current link of one of its shortcut by one link included in the incoming message if link.id is closer to shortcut.landmark than shortcut.link.id, applying the following algorithm : shortcut.learn(newlink) =    if align(shortcut.link.id, newlink.id, shortcut.landmark, f alse, true, f alse) then shortcut.link = newlink

In the following, we discuss several orders implemented on top of our model, using a Javabased simulation tool we developed, that, given an order and a set of landmarks, is able to build the corresponding overlay and to simulate its behavior in regard to some key performance indicators (mainly the routing complexity). The first order, ring, introduces some general notions and notations that may be reused in the following orders. For all models, N denotes the number of nodes.

Ring

Natural numbers are obvious candidates to order things. Our first topology is based on positive integers with the natural order based on them. The landmarks maintained for routing purpose are directly inspired by the Chord approach, i.e., exponentially distant of the considered node [START_REF] Stoica | Chord: A Scalable Peer-to-Peer Lookup service for Internet Applications[END_REF]. More precisely, a node n has a set of landmarks with identifiers p.id + 2 i for i > 0 (the case i = 0 is redundant with succLink). The only remaining question is : how many shortcuts a node is supposed to maintain ? If, at the application layer, inserted nodes have bounded identifiers, say for example that all identifiers fit in a 64-bit integer, then all nodes have to reserve space for 64 shortcuts. Otherwise, during its learning process, a node can memorize the highest identifier encountered. If the approximation of highest identifier is kept in the node's local variable max, the number of shortcuts must follow dynamically the value log 2 (max) .

A natural measure of the efficiency of networks is the average of node a message must traverse before reaching its final destination. This number is correlated to the latency of the network, and is commonly referred to as the diameter of the network, or the number of hops. The distribution of nodes' identifiers and the insertion/deletion of nodes influence it deeply. Nevertheless, it makes sense to compute a theoretical value when the network is saturated (W = T and card(T ) = 2 k ) and stable (no insertion/deletion). We will note µ this theoretical value, which depends only on N . For networks based on natural numbers, the natural order and the shortcuts presented above, it is easy to verify that µ = log2(N ) 2 .

Hypercube

Another topology explored to build overlay networks is the hypercube, or more generally the [START_REF] Schlosser | Hypercup -hypercubes, ontologies, and efficient search on peer-to-peer networks[END_REF]. As previously mentioned, identifiers of nodes in a hypercube are binary identifiers, and the neighbors of a node n are every node having an identifier differing by only one bit to the identifier of n.id. These identifiers are used as landmarks for the node. As a consequence, natural candidates to find a hamiltonian cycle in a hypercube are the Gray codes [START_REF] Gilbert | Gray Codes and Paths on the n-Cube[END_REF]. Similarly, a gray code is a binary numeral system where two successive values differ by only one bit. The gray code can be recursively obtained through the following definition (n-ary Gray Code) :

A i = {0 • A i-1 , 1 • A i-1 -1 }
where A is a sequence of binary strings, A -1 denotes the same sequence in reverse order, and a • A concatenates the bit a to every element of the sequence A. Following this definition, the initial sequence A 1 = 0, 1 is refined into A 2 = 00, 01, 11, 10, and then into A 3 = 000, 001, 011, 010, 110, 111, 101, 100 at step 3. The mapping obtained through the gray code is illustrated on Figure 8. Following the gray code generation previously given, we need to write the algorithm ordering two identifiers. Let a.x denotes the concatenation of the bit a to the strings representing the value x, ε is the empty string, x the size of the strings representing the value x, moreover, before calling the order predicate, we assume that all the leading zeros of both arguments are removed. As a consequence, all values, except zero, start with a "1". This leads to the following Inria recursive algorithm :

x < b y =                    x < y if x = y b if x = ε x < b y if x = 0.x ∧ y = 0.y T rue if x = 0.x ∧ y = 1.y F alse if x = 1.x ∧ y = 0.y y < b x if x = 1.x ∧ y = 1.y
Note that, starting from hypercube and Gray code originally defined on a set of 2 k elements, we end up here with a general definition of a conditional order using bit-string of arbitrary length. The n-cube intrinsically allows logarithmic routing by using neighbors of nodes, at each step decrementing the number of differing bits between current node and destination. The previous discussion about dynamically setting the number of shortcuts in a ring topology also holds for n-cubes.

For this topology we have computed the theoretical latency which is : µ 3 4 (log 2 (N )-1)+ 1 N .

Cartesian Space

Another topology commonly used by P2P systems is the cartesian space, such as in the early CAN approach [START_REF] Ratnasamy | A Scalable Content-Adressable Network[END_REF]. Moreover, cartesian spaces are good candidates to support more complex queries (such as range queries) than the usual lookup for a fixed key. Note that an interesting formalization of CAN through π-calculus can be found in [START_REF] Iftene | Formalizing peer-to-peer systems based on content addressable network[END_REF].

Linearizing the space. In a cartesian space, each node is a point determined by a set of coordinates. As illustrated by Figure 9, ordering points can be obtained through space filling curves (SFCs) [START_REF] Asano | Space-Filling Curves and their Use in the Design of Geometric Data Structures[END_REF] which give a continuous mapping from a d-dimensional space to a 1-dimensional space. Imagine for instance a d-dimensional cube with the SFC passing through each point in the cube volume, and entering and exiting the cube only once. Given a point of a d-dimensional space, the SFC returns a real value between 0 and 1, while preserving the locality, i.e., close points in the d-dimensional space will obtain close values when projected on the unit vector. Among SFCs, the Hilbert SFC has been proven to be the one that preserves proximity of nodes the most [START_REF] Asano | Space-Filling Curves and their Use in the Design of Geometric Data Structures[END_REF]. The mapping process is illustrated by Figure 9, Each node, by its coordinates, owns one small square. The 1-dimensional indexes are obtained recursively, by refining the curve. The index is then the number of squares traversed starting from square zero (bottom left).

Each refinemenet step follows a strict scheme. The curve is made of a succession of four patterns, each one being refined in a precise way. The refinement of the four patterns are illustrated by Figure 10. One way to perceive the refinement step is the following. For clarity, we number them 0, 1, 2, and 3. For instance, one refinement step of Pattern 0 produces a new partial curve being the concatenation of patterns 1, 0, 0, 2, in this order. As illustrated by Figure 10, the other refinements are very similar : only a rotation is needed.

Following these patterns and their sub-patterns, we can design an order on points. Let A = (x A , y A ) and B = (x B , y B ) two points whose both coordinates have the same number of bits. If necessary, the shortest of the two can be left-padded with zeros. x A denotes A's abscissa and y A denotes its ordinate. Let x a (resp. y a ) be the leftmost bit of x A (resp y A ).

Let us take the convention, adopted on Figure 9, that the first refinement (creating a square of size 2) follows pattern 0. As pictured in Figure 10, the first pattern in the refinement of determine the next pattern. This is obtained through the nextP at function whose parameters are the current pattern and the leftmost bits of coordinates of A and B. This function can be easily written looking at Figure 10. For instance, if we are in the pattern 2 and x a = y a = 1, then A and B are in the up-right sub-square and nextP at(2, 1, 1) returns 3. A' (resp. B') is constructed by removing the leftmost bit of the coordinates of A (resp. B). These new coordinates are the one relative to the sub-square.

Finally, the third case is when A and B do not belong to the same sub-square (either x a = x b or y a = y b ). In this case, the answer can be computed with the current pattern and these bits, through the resP at function. For example, if the current pattern is 2, A is in the up-right sub-square (x a = y a = 1) and B is in the down-left sub-square (x b = y b = 0), then A is before B in the linearization : resP at(2, 1, 1, 0, 0) = true. Once again, the values returned by resP at can be extracted by a simple reading of Figure 10. Note that, as for the ring and hypercube topologies, we have defined an order independent of the sizes of coordinates.

Landmarks in the space. In CAN, each node is responsible for a square portion of the space, and maintains a link to all nodes responsible for a square contiguous to its own square. This routing scheme was shown to be efficient (with a logarithmic complexity) only if the number of dimension of the space is fixed to log(N ). However, this requires to be able to dynamically determine the number of nodes in the network, and reset the number of dimensions when nodes are joining or leaving the network, which can be very costly at large scale. Instead, we will here try to use the nature of cartesian space to determine good routing links for the basic topology, i.e., when d = 2, for which case CAN's routing is not logarithmic. • We can first choose to change only some of the bits x i and y i , for example, for the landmark in the same column, we can take (X, Y h • y i • Y l ). In this case, the landmarks have the same position as A, but inside their respective sub-squares. This set of links is pictured on Figure 11 with solid arrows.

• Instead of leaving X l and Y l as it is, we can reverse all these bits, then for the landmarks in the same column we have (X, Y h • y i • Y l ). In this case the landmarks take place at some symmetric position relatively to the horizontal median, the vertical median, or the central point. This second possibility is pictured on Figure 11 with dashed arrows.

• At each level, we can also choose a random point in the sub-square.

Simulation results

To compare the three topologies described above we have chosen to analyse stable and well distributed networks, i.e., where no insertion/deletion of nodes occurs and when each node manages the same number of identifiers. Note that our goal here, is not compare the performance of the topologies we describe before, as they already have been well-studied, but more to present the results of the use of our java-based tool whose goal is to construct and simulate overlays based on an ordering function and a set of landmarks.

In the following, if N is not a power of two, the number of managed identifiers may differ by one between two nodes. We have chosen a domain of identifiers with a size of 4K, i.e., , integers on 12 bits for Ring and Hypercube, and a Cartesian Space with coordinates on 6 bits. For each number of nodes N ranging from 1 to 2048, i.e., until the network is half-saturated, we compute the average number of hops. Figure 12 shows the results for the orders presented in this section. The best one is the ring, the associated spline is 1/2 * log 2 (x), confirming the theoretical result obtained for a saturated ring. In the middle, we find the cartesian space (here following the symmetric way of setting landmarks), which seems to follow 9/16 * log 2 (x). The worst result is for Hypercube which is just under the 3/4 * log 2 (x) function.

Conclusion

This paper studied some results that can be applied for families of networks relying only on an order on nodes' identifiers. The protocols for nodes' insertion and deletion were reviewed in details to ensure the absence of deadlocks and livelocks. All this first part of the work, presented in Section 2, was specified in Coq, a formal proof management system [START_REF] Bertot | Interactive Theorem Proving and Program Development. Coq'Art: The Calculus of Inductive Constructions[END_REF]. We have reached some strong lemmas on alignments, on topologic invariants and for the correctness of the routing process. However, we have not yet fully finished the deadlock/livelock free theorem (termination of the routing process for one message, in other words, that all messages will reach their final destination). Note that the deletion's deadlock was discovered during the attempt of solving the termination's theorem.

We have also shown, in Section 3, some concretizations of the abstract order described in Section 2. These concretizations, and thus the underlying abstract model, was implemented in Java : 750 lines for the abstract model and 750 lines for the specification of some 10 different orders. This implementation was the indispensable tool for computing the results given in Figure 12. We have also used this tool for studying different strategies for learning, i.e., the way a node computes more accurate shortcuts when nodes join and leave dynamically.

Figure 1 :

 1 Figure 1: One routing step.

Figure 2 :

 2 Figure 2: Insertion and deletion.

Figure 3 :

 3 Figure 3: Insertion steps.

Figure 4 :

 4 Figure 4: Deletion steps.

  Inriaquit.eval(node) = node.analyze(new Delete(id = node.id))A delete message does not implement the general arrived and isShortcut methods described in Definitions 2 and 4. It traverses the ring until it reaches a node whose successor's identifier is the node to be deleted : delete.arrived(a, b) = (b = delete.id) delete.isShortcut(a, b) = align(a, b, delete.id, f alse, f alse, f alse) delete.eval(node) = node.succLink.send(new Leave(contact = node.contact))

Figure 5 :

 5 Figure 5: Node state automaton.

Figure 6 :

 6 Figure 6: Node state automaton (left).

Figure 5 .Figure 7 :

 57 Figure 7: Deadlock in a network of two nodes.

Figure 8 :

 8 Figure 8: Linearizing a 3-cube.

Figure 11 :

 11 Figure 11: Routing links in a 2-dimensional space.

Figure 12 :

 12 Figure 12: Number of hops Vs number of nodes.

RR n°8172

In practice, nodes commonly store information about distant nodes using one or several tables.RR n°8172

Inria

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

(0,0) [START_REF] Asano | Space-Filling Curves and their Use in the Design of Geometric Data Structures[END_REF][START_REF] Bertot | Interactive Theorem Proving and Program Development. Coq'Art: The Calculus of Inductive Constructions[END_REF] (5,4) [START_REF] Hayes | The forgiving tree: a self-healing distributed data structure[END_REF][START_REF] Gilbert | Gray Codes and Paths on the n-Cube[END_REF] Figure 9: Linearizing a tore.

The first case is trivial (ε < p b ε = b). Otherwise, if A and B are in the same sub-square (second line), we cannot give an answer now and we have to make a recursion. We need then to Inria


Laurent Mennillo

Jean Cousty

Laurent Najman

Morphological filters for OCR: a performance comparison

In this article is compared the ability of several morphological operators to improve OCR performance when used as preprocessing filters. An experiment on binary and greyscale images using the Tesseract OCR engine and morphological filters acting in complex, graph and vertex spaces has thus been performed and results in a good overall performance of complex and area filters. MSE measures have also been performed to evaluate the denoising ability of these filters, which again shows the good performance of both complex and area filters on this aspect.

Introduction

This article presents an OCR performance comparison obtained through the use of several morphological filters on degraded documents. First, section 2 will present the degradation models used to alter the documents to be analysed, section 3 will then introduce morphological filters partially restoring the image quality of such degraded documents, section 4 will describe the detailed test protocols of this experiment and the last sections will finally discuss the results and conclude.

Document degradation models

Document degradation models are designed to simulate local distortions that are introduced during the processes of document scanning, printing and photocopying. In the context of this experiment, some of these models have the ability to generate realistic degradations that are appropriate for OCR performance evaluation. Besides, increasing levels of such degradations can also be produced by adjusting the models parameters, thus allowing a proper leveled comparison.

Binary document degradation

The binary document degradation model used in this experiment has been described by Kanungo et al. in [3]. This local model, which only applies to binary images, accounts for two types of document degradation, which are pixel inversion and blurring. Pixel inversion simulates image noise usually generated by light intensity variations, sensor sensitivity and image thresholding, while blurring simulates the point-spread function of the scanner optical system. Pixel inversion probability of a background (resp. foreground) pixel is modelled following an exponential function of its distance from the nearest foreground (resp. background) pixel as: p(0|1, d, α 0 , α) = α 0 e -αd 2 + η p(1|0, d, β 0 , β) = β 0 e -βd 2 + η Parameter d is thus the 4-neighbor distance of each background (resp. foreground) pixel from its nearest foreground (resp. background) pixel, parameter α 0 (resp. β 0 ) is the amount of generated noise related to background (resp. foreground) pixels, parameter α (resp. β) is the decay speed, relatively to distance d, of background (resp. foreground) pixels flipping probability and parameter η is the constant flipping probability of all pixels. Finally, Blurring is produced by a morphological closing operation using a disk structuring element of diameter k. The described model with parameters Θ = (η, α 0 , α, β 0 , β, k) is thus used to degrade any binary document by computing the distance map of each pixel, then independently flip them following their respective probability and finally perform a morphological closing operation.

Greyscale document degradation

The document degradation model described in 2.1 can also be used to process greyscale images.

For this purpose, the image to degrade is first thresholded with value t ∈ [0; 255] to binary images B t . These images are then degraded with the binary document degradation model. Thereafter, greyscale images G t are generated by setting the black pixels of images B t to their respective tresholding value t. The degraded image D, initialized with white pixels, is finally reconstructed from white to black values (t = 255 . . . 0) by processing the minimum value at each pixel of images D and G t (D i,j = min(D i,j , G t,i,j )). In this experiment, a faster but less realistic greyscale document degradation is achieved by adding impulsional Gaussian noise to the original image with parameters Ω = (σ, p), where σ and p, respectively denote the standard deviation and proportion of pixels to alter.

Morphological filtering

Morphological filters can be used to restore or improve the image quality of digitally converted documents and thus increase OCR performance. This section presents the four morphological filters compared in this experiment.

Morphological operators in simplicial complex spaces

Morphological operators defined in simplicial complex spaces have been presented by Dias et al.

in [START_REF] Dias | Some morphological operators on simplicial complex spaces[END_REF]. The following paragraphs will introduce these morphological operators and describe their implementation.

Definitions

Lattice A lattice is a partially ordered set that have a unique lowest greater bound called supremum and a greatest lower bound called infimum. An example of lattice, given in figure 1, is the power set P(X) of set X = {a, b, c}, whose supremum and infimum are respectively the union and the intersection.

Adjunction Let L 1 and L 2 be two lattices whose order relations are denoted by ≤ 1 and ≤ 2 . Two operators α :

L 2 → L 1 and α A : L 1 → L 2 form an adjunction (α A , α) if, ∀a ∈ L 2 and ∀b ∈ L 1 , α(a) ≤ 1 ⇔ a ≤ 2 α A (b).
Simplex An (abstract) simplex of dimension n ∈ N, or n-simplex, is a finite nonempty set. The dimension of a simplex x is denoted by dim(x). Geometrically, 0-simplices can be represented as Simplicial complex An (abstract) simplicial complex, or complex, is a set X of simplices such that, for any set x ∈ X, any nonempty subset of x also belongs to X. Its dimension n ∈ N is equal to the greatest dimension of its simplices. In the following, C denotes a nonempty complex of dimension n, or n-complex. The complement of a subset X of C is X = C \ X, while the set of all subsets of C, equipped with the inclusion relation and denoted by P(C), is a lattice, which is complemented. Figures 3a, 3b and 3c respectively presents a complex of dimension 2, or 2-complex, a subset X and its complement X. Subcomplex, star and cell Any subset X of C that is also a complex is called a subcomplex.

(a) C (b) X (c) X (d) C (e) S
A star is a subset X of C whose complement X is a subcomplex. The set of all subcomplexes and stars of C are respectively denoted by C and S. Note that the sets C and S, equipped with the inclusion relation, are sublattices of P(C) that are closed under union and intersection, but not complemented. A subcomplex X of C is called a cell if there exists a simplex x ∈ X such that X is exactly the set of all subsets of x. Following this definition, cells can be considered as the elementary building blocks of simplicial complexes. Illustrations of a subcomplex, a star and a cell are respectively given in figures 3d, 3e and 2d.

Closure and star of a set The closure of a set X of C, denoted Cl(X), is the smallest subcomplex of C that contains each simplex in X. The star of a set X of C, denoted St(X), is the set of all simplices in C that intersect with X. Figures 4a, 4b and 4c present respectively a set X, its closure Cl(X) and its star St(X).

(a) X (b) Cl(X) (c) St(X)
Figure 4: Closure and star of a set.

Dimensional operators

Dimensional operators are designed to add or remove simplices from a set by taking into account their dimension. Let X ∈ C and let i ∈ [0; n], n being the dimension of C. The set of all i-simplices of X is

X i = {x ∈ X | dim(x) = i}.
In particular, C i is the set of all i-simplices of C and P(C i ) is the set of all subsets of C i , P(C i ) being complemented. Now, let i, j ∈ N such that i ≤ j ≤ n. The operators δ + i,j and ǫ + i,j act from P(C i ) into P(C j ) and the operators δ - j,i and ǫ - j,i act from P(C j ) into P(C i ) as:

P(C i ) → P(C j ) P(C j ) → P(C i ) X → δ + i,j (X) such that δ + i,j (X) = {x ∈ C j | ∃y ∈ X, y ⊆ x} X → δ - j,i (X) such that δ - j,i (X) = {x ∈ C i | ∃y ∈ X, x ⊆ y} X → ǫ + i,j (X) such that ǫ + i,j (X) = {x ∈ C j | ∀y ∈ C i , y ⊆ x ⇒ y ∈ X} X → ǫ - j,i (X) such that ǫ - j,i (X) = {x ∈ C i | ∀y ∈ C j , x ⊆ y ⇒ y ∈ X}
Note that the pair of operators (ǫ - j,i , δ + i,j ) and (ǫ + i,j , δ - j,i ) are adjunctions acting between P(C i ) and P(C j ) and that operators δ + i,j and ǫ + i,j (resp. δ - j,i and ǫ - j,i ) are dual w.r.t. the complement. These dimensional operators are illustrated in figure 5, where green simplices are the original set and red simplices are the resulting set.

(a) δ + 0,1 (b) δ + 0,2 (c) δ + 1,2 (d) δ - 1,0 (e) δ - 2,0 (f) δ - 2,1 (g) ǫ + 0,1 (h) ǫ + 0,2 (i) ǫ + 1,2 (j) ǫ - 1,0 (k) ǫ - 2,0 (l) ǫ - 2,1

Closure and star operators

Dimensional operators previously described allow for the creation of ⋄ : S → C and ⋆ : C → S operators, defined by:

∀X ∈ S, ⋄(X) = i∈[0;n],j∈[0;n] δ - j,i (X) ∀X ∈ C, ⋆(X) = i∈[0;n],j∈[0;n] δ + i,j (X)
Note that ⋄ (resp. ⋆) operator, acting as Cl (resp. St) on S (resp. C), produce subcomplexes (resp. stars). In words of mathematical morphology, these operators are dilations, meaning that they commute with the supremum. Their adjunct erosions, ⋄ A : C → S and ⋆ A : S → C operators, commuting with the infimum, are dual w.r.t. the complement and thus defined by:

∀X ∈ C, ⋄ A (X) = ⋄(X) ∀X ∈ S, ⋆ A (X) = ⋆(X)
Note that ⋄ A (resp. ⋆ A ) operators, acting on C (resp. S), produce stars (resp. subcomplexes). These operators, acting on the subcomplex X and the star Y , are illustrated in figure 6.

(a) X (b) ⋆(X) (c) ⋄ A (X) (d) Y (e) ⋄(Y ) (f) ⋆ A (Y )
Figure 6: Closure and star operators.

Dilation and erosion operators

Composition of closure and star operators lead to δ : C → C and ǫ : C → C operators, defined by:

∀X ∈ C, δ(X) = ⋄ • ⋆(X) ∀X ∈ C, ǫ(X) = ⋆ A • ⋄ A (X)
Note that δ is a dilation, ǫ an erosion and that the pair (ǫ, δ) is an adjunction. δ and ǫ operators acting on the subcomplex X shown in figure 7a are respectively illustrated in figures 7b and 7c.

(a) X (b) δ(X) (c) ǫ(X)

Closing and opening filters

A filter is an operator β : L → L that is increasing:

X ⊆ Y ⇒ β(X) ⊆ β(Y ) and idempotent: β • β(X) = β(X).
Composition of dilation and erosion operators lead to φ : C → C and γ : C → C filters, defined by:

∀X ∈ C, φ(X) = ǫ • δ(X) ∀X ∈ C, γ(X) = δ • ǫ(X)
In words of mathematical morphology, φ filter is a closing operation, which is extensive: X ⊆ φ(X), while γ filter is an opening operation, which is anti-extensive: γ(X) ⊆ X. These two filters are illustrated in figure 8.

(a) X (b) φ(X) (c) γ(X)
∀X ∈ C, φ d/(n+1) (X) = {X i | i ∈ [0; n -d -1]} ∪ {ǫ + n-d,j (X d ) | j ∈ [n -d; n]} ∀X ∈ C, γ d/(n+1) (X) = {δ - j,i (X j ) | j ∈ [d; n], i ∈ [0; j]}
In other words, φ d/(n+1) is a closing operation which adds to the set X the cells of C whose i-

simplices, i ∈ [0; n -d],
belong to X, while γ d/(n+1) is an opening operation which removes from the set X the cells of C whose dimension is less than d. Besides, note that φ d/(n+1) and γ d/(n+1) filters satisfy the granulometric properties φ d1/(n+1) (X) ⊆ φ d2/(n+1) (X) and

γ d2/(n+1) (X) ⊆ γ d1/(n+1) (X), if d 1 ≤ d 2 , ∀d 1 , d 2 ∈ [0; n -1]. These filters are illustrated in figure 9. (a) X (b) φ 1/3 (X) (c) φ 2/3 (X) (d) γ 1/3 (X) (e) γ 2/3 (X)
Figure 9: Dimensional-closing and dimensional-opening filters.

Granulometries

Closing and opening filters can be extended to granulometries by composing them with dimensional filters. Let α be an operator defined on a lattice L and let i be a nonnegative integer. The operator α i (L) is defined by the identity when i = 0 and by (α • α i-1 )(L) otherwise. Now, let parameters i and d respectively be the quotient and the remainder of the division k/(n + 1). Granulometric-closing filter Φ k/(n+1) : C → C and granulometric-opening filter Γ k/(n+1) : C → C are then defined by:

∀X ∈ C, Φ k/(n+1) = ǫ i • φ d/(n+1) • δ i (X) ∀X ∈ C, Γ k/(n+1) = δ i • γ d/(n+1) • ǫ i (X)

Alternating sequential filter

The alternating sequential filter ASF k/(n+1) : C → C can be defined using the granulometric closing and opening filters by:

∀X ∈ C, ASF k/(n+1) (X) = identity if k = 0 Γ k/(n+1) • Φ k/(n+1) • ASF k-1/(n+1) (X) otherwise 3.1.

Implementation

The simplicial complex space used in this experiment is the hexagonal grid C shown in figure 3a and initialized in figure 10c, on which each vertex is 6-connected. In order to work on square grids illustrated in figure 10a, which is the case of two-dimensional images, an other structure merging these two representations, as shown in figure 10b, has been used for complex filtering. Additionally, working with greyscale values is done by respectively computing the maximum and minimum value for union and intersection, while the complement of a simplex x is defined by the maximum value of the greyscale space minus the value of x. As for initialization, the set X 0 is initialized with the image pixels values, any 1-simplex x ∈ X 1 is set to the minimum value of its corresponding 0-simplices

x 1 , x 2 ∈ P(C 0 ) | x 1 , x 2 ⊂ x with x 1 = x 2
, and any 2-simplex y ∈ X 2 is also set to the minimum value of its corresponding 0-simplices y 1 , y 2 , y 3 ∈ P(C 0 ) | y 1 , y 2 , y 3 ⊂ y with y 1 = y 2 = y 3 . Following this initialization, the initial set is thus always a subcomplex, which is coherent given the filters used in this experiment, all acting on set C. One can note, however, that in the case of binary images, such initialized sets are invariant to dimensionalclosing filter φ d/(n+1) . This particular property means that ASF k/(n+1) filter applied on such sets will not produce the expected result in this particular case, as the outcome of this operation will appear to be similar to the closing of an opening rather than the opening of a closing. Figure 10 illustrates the used data structure and its initialization.

Morphological operators in graph spaces

Morphological operators defined in graph spaces have been presented by Cousty et al. in [START_REF] Cousty | Some morphological operators in graph spaces[END_REF]. These operators being very similar to those used in simplicial complex spaces, a large part of the following is thus based on the theory already covered.

Definitions

Graph A graph G is a complex of dimension 1. 0-simplices of a graph are usually denoted as its vertex set, while 1-simplices are usually denoted as its edge set. Such graph is presented in figure 11a along with a subset, also denoted as a subgraph, in figure 11b.

Important notations In the following, the set of all subsets of G, or P(G), is denoted by G.

Similarly, the set of all vertices (resp. edges) of G, or P(G 0 ) (resp. P(G 1 )), is denoted by G 0 (resp. G 1 ). The sets G 0 and G 1 are respectively illustrated in figures 11c and 11d.

(a) G (b) X (c) G 0 (d) G 1

Dimensional operators

As in simplicial complex spaces, dimensional operators in graph spaces are designed to add or remove vertices and edges from a set. These operators in graphs are exactly the same operators as those defined in complexes, excepted that their dimension d is in the interval [0; 1].

Dimensional dilation and erosion operators

In graphs, one is often interested by operators whose input and output are a set of vertices (resp. edges). Composing the dimensional operators defined above lead to δ : G 0 → G 0 and ǫ : G 0 → G 0 operators, acting on vertices and defined by:

∀X ∈ G 0 , δ(X) = δ - 1,0 • δ + 0,1 (X) ∀X ∈ G 0 , ǫ(X) = ǫ - 1,0 • ǫ + 0,1 (X)
Similarly to δ and ǫ operators, ∆ : G 1 → G 1 and ε : G 1 → G 1 operators, acting on edges, are defined by:

∀X ∈ G 1 , ∆(X) = δ + 0,1 • δ - 1,0 (X) ∀X ∈ G 1 , ε(X) = ǫ + 0,1 • ǫ - 1,0 (X)
Note that δ and ∆ operators are dilations, while ǫ and ε are erosions.

Dilation and erosion operators

Composing dimensional dilation and erosion operators lead to graph dilation and erosion operators. (δ ∨ ∆) : G → G and (ǫ ∨ ε) : G → G operators are defined by:

∀X ∈ G, (δ ∨ ∆)(X) = δ(X 0 ) ∪ ∆(X 1 ) ∀X ∈ G, (ǫ ∨ ε)(X) = ǫ(X 0 ) ∪ ε(X 1 )
Note that (δ ∨ ∆) is a dilation, while (ǫ ∨ ε) is an erosion. These operators are illustrated in figure 12.

(a) X (b) (δ ∨ ∆)(X) (c) (ǫ ∨ ε)(X)
Figure 12: Graph dilation and erosion operators.

Closing and opening filters

Composition of δ, ∆, ǫ and ε operators lead to (φ ∨ Φ)

1 : G → G and (γ ∨ Γ) 1 : G → G filters, defined by: ∀X ∈ G, (φ ∨ Φ) 1 (X) = (ǫ ∨ ε) • (δ ∨ ∆)(X) ∀X ∈ G, (γ ∨ Γ) 1 (X) = (δ ∨ ∆) • (ǫ ∨ ε)(X)
Note that (φ ∨ Φ) 1 is a closing operation, while (γ ∨ Γ) 1 is an opening operation. These filters are illustrated in figure 13.

(a) X (b) (φ ∨ Φ) 1 (X) (c) (γ ∨ Γ) 1 (X)
Figure 13: Graph closing and opening filters.

Half-closing and half-opening filters

Half opening and closing filters can also be created using dimensional operators. (φ ∨ Φ) 1/2 : G → G and (γ ∨ Γ) 1/2 : G → G filters are defined by:

∀X ∈ G, (φ ∨ Φ) 1/2 (X) = (ǫ + 0,1 ∨ ǫ - 1,0 ) • (δ + 0,1 ∨ δ - 1,0 )(X) ∀X ∈ G, (γ ∨ Γ) 1/2 (X) = (δ + 0,1 ∨ δ - 1,0 ) • (ǫ + 0,1 ∨ ǫ - 1,0 )(X)
Note that (φ ∨ Φ) 1/2 is a closing operation, while (γ ∨ Γ) 1/2 is an opening operation. These filters are illustrated in figure 14.

(a) X (b) (φ ∨ Φ) 1/2 (X)(c) (γ ∨ Γ) 1/2 (X)
Figure 14: Half-closing and half-opening filters.

Granulometries

Given parameters i and j, respectively being the quotient and the remainder of the division k/2, granulometric-closing filter (φ∨Φ) k/2 : G → G and granulometric-opening filter (γ∨Γ) k/2 : G → G are defined by:

∀X ∈ G, (φ ∨ Φ) k/2 = (ǫ ∨ ε) i • (φ ∨ Φ) j 1/2 • (δ ∨ ∆) i (X) ∀X ∈ G, (γ ∨ Γ) k/2 = (δ ∨ ∆) i • (γ ∨ Γ) j 1/2 • (ǫ ∨ ε) i (X)

Alternating sequential filter

The alternating sequential filter ASF k/2 : G → G can be defined using the granulometries defined above, by:

∀X ∈ G, ASF k/2 (X) = identity if k = 0 (γ ∨ Γ) k/2 • (φ ∨ Φ) k/2 • ASF k-1/2 (X) otherwise

Implementation

The graph space used in this experiment is the hexagonal grid presented in figure 11a and initialized in figure 15c, while figures 15a and 15b respectively show the image pixels and the used data structure for graph filtering. The set G 0 is initialized with the image pixels values, while any edge e ∈ G 1 is set to the minimum value of its corresponding vertices

v 1 , v 2 ∈ G 0 | v 1 , v 2 ⊂ e with v 1 = v 2 .
Figure 15 illustrates the used data structure and its initialization.

Morphological operators in vertex spaces

Dilation and erosion operators defined in vertex spaces on an hexagonal grid act as dilation and erosion operators defined in graph spaces, projected from G to G 0 . More precisely, the graph structure isn't implemented in these operators, as they directly act on the pixels neighbors. Besides, in this space, half-closing and half-opening operators doesn't exist and ASF filter is thus a composition of dilation and erosion operators.

Morphological area opening and closing filters

Morphological area opening and closing filters for binary and greyscale images have been presented by Vincent in [START_REF] Vincent | Morphological area openings and closings for greyscale images[END_REF]. These filters respectively remove light and dark regions of the image whose area is superior to a parameter λ ∈ N. In order to compute the morphological area opening γ a λ (resp. closing φ a λ ) of a greyscale image, the regional maxima (resp. minima) of the image are first extracted and labelled. Then, 4-neighboring pixels of each maximum (resp. minimum) are progressively added relatively to their intensity, from light (resp. dark) to dark (resp. light) pixels, until the area of the broadened regions reaches λ. Pixels of the created regions are finally set to the intensity value of their last added pixel.

Test protocols 4.1 First test protocol

Tesseract OCR engine, presented in [START_REF] Smith | An overview of the tesseract ocr engine[END_REF], has been used to perform optical character recognition in this experiment. This powerful system has been evaluated by UNLV-ISRI in 1995 (refer to [START_REF] Nartker | Ocr accuracy: Unlv's fourth annual test[END_REF]) along with other commercial OCR engines and proved its top-tier performance at the time. In order to get OCR performance results from this engine on preprocessed documents, the test data and software tools from UNLV-ISRI presented in [START_REF] Nartker | Software tools and test data for research and testing of page-reading ocr systems[END_REF] have been used. Most of the documents in this test data being available in binary format at 300 DPI resolution, the tests have been conducted on a selection of this particular set of documents (100). An other set of two generated greyscale documents has been used to evaluate the performance of each filter on greyscale values. The test procedure is basically the iteration of degradation, filtering, OCR analysis and MSE measure of each document, repeated for each couple (d, f ) of degradation and filtering parameters. Note, however, that the used binary documents are scanned versions of real documents, meaning that they are imperfect and consequently contain noise. Degradation performed on these documents simply allow for a better comparison of the filters efficiency in critical conditions.

Filtering

The filters used in this experiment are the ASF filters in simplicial complexes, graphs and vertices, as well as a combination of area closing and area opening filters. The tests have been conducted on both regular and inverse versions of each document, in particular to evaluate the impact of the proposed initialization in simplicial complex spaces on binary documents. Furthermore, ASF filters in gaphs and vertices have also been evaluated with document resolution scaling of respectively 3/1 and 3/2 (Usc), in order to preserve the same number of iterations between each filter. In the case of binary document filtering, the corresponding upscaled documents were then binarized with a threshold value of 128 (Thr1), downscaled to their original size after filtering (Dsc) and binarized again with a threshold value of 128 (Thr2) in order to preserve the characters size for OCR processing. As for greyscale documents, they were also scaled but not thresholded. Filtering levels were specified for each morphological filter with parameter f ∈ N. Detailed settings are described in table 1. One can note that binarization after upscaling (Thr1) is not performed in the case of vertices filtering. This is simply due to the fact that these documents are already in binary form after an exact upscaling of 3/1. Character and word accuracy obtained from OCR processing of each document, as well as 95% confidence intervals of the obtained accuracy for each set of documents processed with a unique couple of parameters (d, f ) were then computed with the accuracy, wordacc, accci and wordaccci tools provided in [START_REF] Nartker | Software tools and test data for research and testing of page-reading ocr systems[END_REF].

ID

MSE measure

Mean squared error has been measured for each processed image I of dimensions w * h, relatively to its unprocessed counterpart O, following:

M SE = 1 w * h h-1 i=0 w-1 j=0 [I(i, j) -O(i, j)]

Second test protocol

Some observations can be stated about the first test protocol. One can note that MSE measures performed from binary documents that already contain noise cannot be considered as a proper evaluation of the filters denoising ability. In addition, OCR analysis and MSE measures are also affected by document scaling, which produce a slight smoothing effect that can impact the results in this situation. This second test protocol has been performed to address these two problems. However, as the characters size is a crucial factor of OCR analysis, this second test protocol is only focused on MSE performance and has thus been performed on noise-free, binary and greyscale documents that were not downscaled at all. Binary document size is 397×249 pixels while greyscale document is 481×321 pixels. The test procedure is the iteration of degradation, filtering and MSE measure of each document, repeated for each pair (d, f ) of degradation and filtering parameters.

Results

First test protocol

In this section are shown the results of the first test protocol in the most critical tested conditions, to better compare the efficiency of each filtering setting. In figures 16, 17, 18 and 19, only the best performing setting is shown for each filter among regular and inverted document filtering.

Binary documents As can be observed in figure 16, complex filtering on non inverted documents produces better accuracy results than any other filter at original resolution. Figure 17 shows, however, that vertex filtering at triple resolution on inverted documents outperforms complex filtering for word accuracy only, but a close look at computational times reveals that this filtering method is nearly two times slower than the other. Finally, MSE results of figure 17 clearly shows that complex filtering, vertex filtering at scaled resolution and area filtering are very close, but also that graph filtering at scaled resolution is significantly outperformed on this aspect. A summary of OCR results obtained in this experiment can be observed in table 2, where ID column corresponds to the filtering parameters defined in table 1

Greyscale documents

In opposition to binary document filtering, grayscale document filtering is better performed on non inverted images for graph and vertex filtering and on inverted images for area filtering, as can be observed in figure 18. From a hierarchical point of view, complex filtering performs better than graph and vertex filtering at original resolution, with area filtering being slightly better in this conditions. Processing scaled images leads to a clear advantage of graph filtering, followed by vertex filtering, area filtering and complex filtering, but looking at computational times of vertex filtering shows that this solution has a worse performance over time ratio than complex filtering. Again, a summary of OCR results obtained in this experiment can be observed in table 3.

Second test protocol

In this section are shown the results of the second test protocol in the most critical tested conditions, to better compare the efficiency of each filtering setting.

Discussion

It is clear that morphological operators are good tools to improve OCR accuracy performance when used as preprocessing filters. The different results shown in this experiment are potent indicators of their efficiency in the context of OCR. Indeed, preprocessing using such filters leads to an increase of respectively up to 59.34% and up to 65.12% in character and word accuracy on binary documents, while these figures are even higher in the case of greyscale documents, with respectively up to 97.63% and up to 90.09%. However, a few remarks can be stated to further explain the results obtained in this experiment. First, regarding the impact of inverted documents filtering, one can note that a general trend emerges from the results of the first test protocol. Indeed, binary document filtering is best performed in non inverted documents for complex and area filters, while graph and vertex filters performs better on inverted documents. As for greyscale document filtering, complex, graph and vertex filters are more efficient on non iverted documents, while area filter performs better on inverted documents. Second, what can also be stated is the impact of the thresholding operations done in the first test protocol on upscaled binary documents. It is clear, for instance, that graph filtering on such documents is severely impacted by these thresholds, as it is the only situation where this filter has a lower performance at a higher resolution. Third, a notable difference in the relative performance of area filtering can be observed in MSE measures of the second test protocol, when compared with complex, graph and vertex filtering. This result can be explained by the size difference of the structures in the processed documents. Indeed, as defined in section 3, morphological operators in complex, graph and vertex spaces tend to alter image contours, while it is not the case of area filters. The first group of filters is thus best performing when image contours are large and easily reconstructible, as can be observed in figure 20, while area filters are best suited for small structures that suffer from strong contour alteration (figure 21). Finally, as a concluding remark and following the previous statement, each filter have its own strengths and weaknesses. Nevertheless, complex filtering seems to be a good choice when preprocessing binary documents with fairly large structures, while area filtering performs better on greyscale documents with small structures.

Figure 1 :Figure 2 :

 12 Figure 1: Power set P(X) of set X = {a, b, c}.

Figure 3 :

 3 Figure 3: Complex, subset, complement, subcomplex and star.

Figure 5 :

 5 Figure 5: Dimensional operators.

Figure 7 :

 7 Figure 7: Dilation and erosion operators in complexes.

Figure 8 :

 8 Figure 8: Closing and opening filters in complexes.

Figure 10 :

 10 Figure 10: Used data srtucture and initialization in complexes.

Figure 11 :

 11 Figure 11: Graph, subgraph, vertices and edges.

Figure 15 :

 15 Figure 15: Used data srtucture and initialization in graphs.

4. 1 . 1 Degradation

 11 Degradation levels are specified with parameter d ∈ N, which acts on the binary document degradation model parameters Θ = (η, α 0 , α, β 0 , β, k) and the impulsional Gaussian noise parameters Ω = (σ, p) as follows: Θ(d) = (d * 0.02, d * 0.1, 1, d * 0.1, 1, 0) Ω(d) = (128, d * 0.1)

2

 2

Figure 16 :

 16 Figure 16: OCR accuracy, MSE and time measured in first test after filtering of 100 binary documents at original resolution. Solid lines represent word accuracy while dashed lines represent character accuracy.

Figure 17 :Figure 18 :

 1718 Figure 17: OCR accuracy, MSE and time measured in first test after filtering of 100 binary documents at scaled resolution for graphs and vertices filters. Solid lines represent word accuracy while dashed lines represent character accuracy.

Figure 19 :

 19 Figure 19: OCR accuracy, MSE and time measured in first test after filtering of 2 greyscale documents at scaled resolution for graphs and vertices filters. Solid lines represent word accuracy while dashed lines represent character accuracy.

Figure 22 :Figure 23 :

 2223 Figure 22: First test protocol sample on binary documents. Original and degraded images with binary degradation model, along with best filtering results obtained on image 22f, under the form [ID : f ].

Figure 24 :

 24 Figure 24: Second test protocol sample on binary document. Original and degraded images with binary degradation model, along with best filtering results obtained on image 24f (d = 4), under the form [ID : f : MSE].

Figure 25 :

 25 Figure 25: Second test protocol sample on greyscale document. Original and degraded images with impulsional Gaussian noise, along with best filtering results obtained on image 25f (d = 4), under the form [ID : f : MSE].

Table 1 :

 1 Filtering parameters.

		Filter	Inverse Usc	Thr1	Dsc	Thr2
	1	Complex ASF f /3
	2	Complex ASF f /3	×
	3	Graph ASF f /2
	4	Graph ASF f /2	×
	5	Graph ASF f /2		3/2 Binary docs only 2/3 Binary docs only
	6	Graph ASF f /2	×	3/2 Binary docs only 2/3 Binary docs only
	7	Vertices ASF f
	8	Vertices ASF f	×
	9	Vertices ASF f		3/1		1/3 Binary docs only
	10	Vertices ASF f	×	3/1		1/3 Binary docs only
	11 12	φ a f • γ a f φ a f • γ a f	×

4.1.3 OCR analysis

OCR analysis has been performed by the Tesseract OCR engine in its latest version (3.02).

Table 2 :

 2 . Best OCR results of first test protocol on 100 binary documents (d = 4).

	ID	Filter	d f Char acc (%) Word acc (%) Time (s)
	1	Complexes	4 5	59.36	61.60	1354.04
	2	IComplexes 4 3	13.51	32.13	879.94
	3	Graphs	4 2	14.81	33.77	453.41
	4	IGraphs	4 3	50.68	56.89	670.95
	5	Graphs3/2	4 2	13.82	30.23	1083.59
	6	IGraphs3/2 4 5	48.54	47.53	2766.04
	7	Vertices	4 1	13.84	31.59	239.06
	8	IVertices	4 1	40.52	50.34	342.42
	9	Vertices3/1 4 2	50.79	60.72	2065.41
	10 IVertices3/1 4 3	54.59	65.13	2662.26
	11	Area	4 6	47.10	44.82	385.20
	12	IArea	4 6	45.66	44.09	426.99

Table 3 :

 3 Best OCR results of first test protocol on 2 greyscale documents (d = 4). 24g, complex filtering of the binary image shown in figure24fproduces better MSE results than any other filter tested in this conditions. What can also be noticed is the good performance of graph filtering at scaled resolution in these conditions, a result contrasting with the first test protocol on binary documents. Now regarding the results obtained on the greyscale image shown in figure25f, the combination of area closing and area opening filters outperforms all other filters, as can be observed in figures 21 and 25r.

	As shown in figures 20 and