Jérôme Jourde
email: jjourde@univ-lr.fr

Pierre-Guy Sauriau
email: pierre-guy.sauriau@univ-lr.fr

Stéphane Guenneteau
email: stephane.guenneteau@lpo.fr

Emmanuel Caillot
email: emmanuel.caillot@espaces-naturels.fr

Philippe Goulletquer

First record of Grandidierella japonica Stephensen, 1938 (Amphipoda: Aoridae) from mainland Europe

Keywords: alien species, Japan, shellfish farming activities, ballast water, Marennes-Oléron Bay, France

The non-native amphipod Grandidierella japonica Stephensen, 1938 is reported for the first time on the Atlantic coast of mainland Europe, specifically from Marennes-Oléron Bay, France. Likely vectors for this introduction include commercial shellfish transplants and ballast waters. A native of Japan, this species had previously only been reported twice outside the Pacific region; in both cases from coastal waters of England. Adults of both sexes, females carrying eggs, and juveniles were collected in Marennes-Oléron Bay, which suggests the species has become established.

Introduction

Grandidierella japonica [START_REF] Stephensen | Grandidierella japonica n. sp., a new amphipod with stridulating (?) organs from brackish water in Japan[END_REF] is an aorid amphipod species (Crustacea: Amphipoda: Aoridae) native to the Japanese archipelago [START_REF] Chapman | Diagnosis, systematics, and notes on Grandidierella japonica (Amphipoda: Gammaridea) and its introduction to the Pacific coast of the United States[END_REF]. Until recently, the species occurred exclusively in the Pacific region. Outside its native area, it was first reported in San Francisco Bay in 1966 [START_REF] Chapman | Diagnosis, systematics, and notes on Grandidierella japonica (Amphipoda: Gammaridea) and its introduction to the Pacific coast of the United States[END_REF] but is now found in intertidal and subtidal sediments of bays and estuaries of the western coast of North America from Mexico to British Columbia, Canada [START_REF] Greenstein | Reproduction and population dynamics of a population of Grandidierella japonica (Stephensen) (Crustacea: Amphipoda) in upper Newport Bay. California[END_REF][START_REF] Okolodkov | Especies acuáticas no indígenas en México[END_REF]). It has also been reported from Hawaii [START_REF] Coles | Historical and recent introductions of non-indigenous marine species into Pearl Harbor, Oahu, Hawaiian Islands[END_REF]) and New South Wales, Australia [START_REF] Myers | Taxonomic studies on the genus Grandidierella Coutière (Crustacea, Amphipoda). III. Fijian, Australian and Saudi Arabian species[END_REF]. Outside the Pacific region, the only known reports of this species are from Southampton (1997) and the Orwell Estuary (2007), south eastern England [START_REF] Smith | Two additions to the UK marine fauna: Desdemona ornata Banse, 1957 (Polychaeta, Sabellidae) and Grandidierella japonica Stephensen, 1938 (Amphipoda, Gammaridea)[END_REF][START_REF] Ashelby | Record of the introduced amphipod Grandidierella japonica Stephensen 1938 (Crustacea: Amphipoda: Gammaridea: Aoridae) from the Orwell estuary, Suffolk[END_REF][START_REF] Noël | Checklist of cryptogenic and alien crustacea of the European Atlantic coast[END_REF]). The species is not listed in recent checklists available at the national scale for France [START_REF] Dauvin | Les Crustacés Amphipodes des côtes françaises métropolitaines: bilan des connaissances[END_REF], at the regional scale of the Southern Bay of Biscay [START_REF] Bachelet | An updated checklist of marine and brackish water Amphipoda (Crustacea: Peracarida) of the southern Bay of Biscay (NE Atlantic)[END_REF], or anywhere on the coast of mainland Europe [START_REF] Goulletquer | Open Atlantic coast of Europe -A century of introduced species into French waters[END_REF][START_REF] Wolff | Non-indigenous marine and estuarine species in The Netherlands[END_REF]DAISIE 2009;[START_REF] Preisler | Invasions of Estuaries vs the Adjacent Open Coast: A Global Perspective[END_REF][START_REF] Haydar | Predicting invasion patterns in coastal ecosystems: relationship between vector strength and vector tempo[END_REF]. To the best of our knowledge, this study represents the first report of Grandidierella japonica, a reproducing population, in coastal waters of mainland Europe.

Methods

As part of a national benthic survey to monitor intertidal macrofauna species available in early autumn to wintering shorebirds (RNF "Littoral Shorebirds and Benthic Macrofauna" observa- tory), 13 stations have been sampled within the Pertuis Charentais Sea every autumn since 2009 (Figure 1). Specimens of Grandidierella japonica have only been collected from two stations: Bellevue (45°56'20.40"N, 01°13'04.80"W) and Ostrea (45°54'53.60"N, 01°12'56.60"W). Located along the Eastern coast of Oléron Island (Figure 1), these stations lie on sheltered muddy and sandy shores. They are located in the vicinity of large shellfish farming areas where Pacific oysters (Crassostrea gigas Thunberg, 1793) are reared in bags on metal trestles [START_REF] Goulletquer | Marine molluscan production trends in France: from fisheries to aquaculture[END_REF][START_REF] Gosling | Bivalve molluscs. Biology, ecology and culture[END_REF], and blue mussels (Mytilus edulis Linnaeus, 1758) are reared on bouchots [START_REF] Goulletquer | Marine molluscan production trends in France: from fisheries to aquaculture[END_REF][START_REF] Prou | The French mussel industry: present status and perspectives[END_REF][START_REF] Gosling | Bivalve molluscs. Biology, ecology and culture[END_REF].

During analysis of samples collected at Bellevue and Ostrea on 8 November 2010, we found two possible specimens of amphipods of the genus Grandidierella Coutière, 1904. Our preliminary identification was based on keys in [START_REF] Ruffo | The Amphipoda of the Mediterranean (Part 1) Gammaridea (Acanthonotozomatidae to Gammaridae)[END_REF] and [START_REF] Barnard | The families and genera of marine gammaridean Amphipoda (except marine gammaroids)[END_REF]. This aorid amphipod genus is, however, close to both the genera Microdeutopus Costa, 1853 and Unciolella Chevreux, 1911. It differs from the former mainly by the uniramous uropods 3 (Figure 2). It differs from the latter by: 1) the length of the uropod 3 rami, which is more than twice the length of the peduncle (Figure 2); 2) the third article of antenna 1, which is much less than half the length of the first article (Figure 3A); and 3) the carpochelate gnathopods 1 of the male (Figure 3A,4A). However, our identification remained tentative due to the poor condition of the female collected at Bellevue and the subadult male collected at Ostrea. Four additional specimens (females) were found in samples collected at the Bellevue station on 30 November 2011. Although the specimens were in good condition, identifying female aorid amphipods to species is difficult; mature males are generally required. To confirm the species identity, additional qualitative benthic samples were made at the Bellevue station on 20 August 2012.

Results

From samples collected at the Bellevue station on 20 August 2012, we obtained 70 specimens in good condition: 21 mature males (Figure 3A); 31 females including 8 brooding females (Figure 3B); and 18 undifferentiated juveniles.

Diagnosis: The mature males had transverse ridges on the carpus anterior margin of the gnathopods 1 (figure 4B). In the genus Grandidierella, only five species have such ridges: namely G. japonica, G. perlata Schellenberg, 1938, G. taihuensis Morino and Dai, 1990, G. vietnamica Dang, 1968[START_REF] Ariyama | Four species of the genus Grandidierella (Crustacea: Amphipoda: Aoridae) from Osaka Bay and the northern part of the Kii Channel, central Japan[END_REF] and G. chaohuensis [START_REF] Hou | A new species of the genus Grandidierella from Lake Chaohu, China[END_REF][START_REF] Hou | A new species of the genus Grandidierella from Lake Chaohu, China[END_REF][START_REF] Hou | A new species of the genus Grandidierella from Lake Chaohu, China[END_REF]. However, the specimens can be identified as G. japonica, because only G. japonica has three teeth on the carpus of the male gnathopod 1 (Figure 4C). In addition, morphological characters of the specimens agree well with the descriptions and figures of G. japonica provided by [START_REF] Stephensen | Grandidierella japonica n. sp., a new amphipod with stridulating (?) organs from brackish water in Japan[END_REF], [START_REF] Chapman | Diagnosis, systematics, and notes on Grandidierella japonica (Amphipoda: Gammaridea) and its introduction to the Pacific coast of the United States[END_REF], [START_REF] Hirayama | Taxonomic studies on the shallow water gammaridean Amphipoda of west Kyushu, Japan. II. Corophiidae[END_REF] and [START_REF] Ariyama | Four species of the genus Grandidierella (Crustacea: Amphipoda: Aoridae) from Osaka Bay and the northern part of the Kii Channel, central Japan[END_REF].

Discussion

In the case of Grandidierella japonica introduction into Californian waters, the most likely hypothesis is commercial transplant of Crassostrea gigas spat from Japan [START_REF] Chapman | Diagnosis, systematics, and notes on Grandidierella japonica (Amphipoda: Gammaridea) and its introduction to the Pacific coast of the United States[END_REF]. The same vector may apply here because the Marennes-Oléron Bay is the most important area for shellfish farming along the French coast [START_REF] Goulletquer | Marine molluscan production trends in France: from fisheries to aquaculture[END_REF]. Oyster culture in this sheltered bay has been characterized by a series of flourishing and declining periods of activity, particularly over the last century when a complete collapse of the Portuguese oyster Crassostrea angulata industry occurred [C. angulata (Lamarck, 1819) is now considered as a junior synonym of C. gigas (WoRMS 2012)]. Large quantities of C. gigas were imported from British Columbia and Japan during the late 1960s and 1970s to counter both the disappearance of C. angulata populations and the decline in native flat oyster stocks (Ostrea edulis Linnaeus, 1758) due to disease and parasite outbreaks [START_REF] Grizel | Introduction into France of the Japanese oyster (Crassostrea gigas)[END_REF][START_REF] Goulletquer | Marine molluscan production trends in France: from fisheries to aquaculture[END_REF]. It is now well established that the movement of C. gigas between countries has led to establishment of numerous alien species into Northern Europe [START_REF] Goulletquer | Open Atlantic coast of Europe -A century of introduced species into French waters[END_REF][START_REF] Wolff | Oyster imports as a vector for the introduction of alien species into northern and western European coastal waters[END_REF]. Indeed, the oyster industry appears to be the main vector of introduction for more than 25% of the 104 alien species recorded along the French Atlantic coast [START_REF] Goulletquer | Open Atlantic coast of Europe -A century of introduced species into French waters[END_REF]. However, other vectors of introduction such as ballast waters and ship fouling cannot be excluded because G. japonica has become established in vicinity of major ports involved in international cargo transport [START_REF] Coles | Historical and recent introductions of non-indigenous marine species into Pearl Harbor, Oahu, Hawaiian Islands[END_REF][START_REF] Smith | Two additions to the UK marine fauna: Desdemona ornata Banse, 1957 (Polychaeta, Sabellidae) and Grandidierella japonica Stephensen, 1938 (Amphipoda, Gammaridea)[END_REF][START_REF] Ashelby | Record of the introduced amphipod Grandidierella japonica Stephensen 1938 (Crustacea: Amphipoda: Gammaridea: Aoridae) from the Orwell estuary, Suffolk[END_REF]). In the context of this study, there are two major seaports handling international cargo nearby: Port Atlantique La Rochelle, which is located North of Marennes-Oléron Bay; and the Port of Rochefort located 25 km upstream of the Charente estuary mouth (Figure 1). A 1993-1995 study analysing ships' traffic and ballast water estimated total annual ballast for both ports to be 1.2 million metric tons [START_REF] Masson | Les eaux de ballast des navires, sources d'introduction d'organismes nuisibles[END_REF].

The timing of introduction of G. japonica into Marennes-Oléron Bay is difficult to establish. For three decades, there have been no official commercial transplants of C. gigas because oyster imports from the Pacific ended by 1982 due to parasite infestation [START_REF] Grizel | Introduction into France of the Japanese oyster (Crassostrea gigas)[END_REF][START_REF] Wolff | Oyster imports as a vector for the introduction of alien species into northern and western European coastal waters[END_REF]. The species may have been present but not identified because the genus Grandidierella can be easily confused with other aorid genera, especially Microdeutopus. Moreover, neither the species nor the genus was described in the taxonomic works most commonly used for amphipod identification in French Atlantic waters [START_REF] Chevreux | Amphipodes[END_REF][START_REF] Lincoln | British marine amphipoda: Gammaridea. British Museum (Natural History[END_REF]. As already noted by [START_REF] Ashelby | Record of the introduced amphipod Grandidierella japonica Stephensen 1938 (Crustacea: Amphipoda: Gammaridea: Aoridae) from the Orwell estuary, Suffolk[END_REF], this may have led to the species being overlooked during the last decades. Even so, introduction of G. japonica into Marennes-Oléron Bay prior to the 1980s would seem unlikely because there were large scale benthic surveys of both intertidal and subtidal areas within Marennes-Oléron Bay during the 1980s and 1990s with no records of the genus [START_REF] Montaudouin | Contribution to a synopsis of marine richness in the Pertuis Charentais Sea with new insights in soft-bottom macrofauna of the Marennes-Oleron Bay[END_REF]. An alternative hypothesis is that this is a recent introduction similar to that in English waters [START_REF] Smith | Two additions to the UK marine fauna: Desdemona ornata Banse, 1957 (Polychaeta, Sabellidae) and Grandidierella japonica Stephensen, 1938 (Amphipoda, Gammaridea)[END_REF][START_REF] Ashelby | Record of the introduced amphipod Grandidierella japonica Stephensen 1938 (Crustacea: Amphipoda: Gammaridea: Aoridae) from the Orwell estuary, Suffolk[END_REF].

The current extent of the geographic range of G. japonica along the French Atlantic coast is unknown. For now, this appears to be an isolated occurrence because there is no evidence of its presence anywhere else in the Pertuis Charentais area or anywhere on coast of mainland Europe. As the presence of brooding females suggests a self-sustaining population exists in Marennes-Oléron Bay and, given the difficulty in identifying the species, it may well be present elsewhere in European waters. Now that a reproducing population of the species has been confirmed, special attention during all benthic monitoring programs would seem to be warranted to better define the species' geographic range in European waters. This would also allow an evaluation of species' invasiveness potential in European waters and permit measurement of significant effects on native fauna.

Figure 1 .

 1 Figure 1. Location of the 13 stations (crosses) sampled in the Pertuis Charentais Sea within the framework of the RNF "Littoral Shorebirds and Benthic Macrofauna" observatory in 2009, 2010 and 2011. Blue crosses show the stations where Grandidierella japonica was found (Bellevue and Ostrea). Gray shading indicates the areas of intense bivalve aquaculture.

Figure 2 .

 2 Figure 2. Grandidierella japonica, urosome showing uniramous uropods 3 (arrows). Alcohol preserved specimen collected at the Bellevue station on 20 August 2012. Photo by Jérôme Jourde.

Figure 3 .

 3 Figure 3. Grandidierella japonica, male (A) and brooding female (B). Arrows show articles 1 and 3 of the male antenna 1. Alcohol preserved specimens collected at the Bellevue station on 20 August 2012. Note: the eggs were greenish in colour before alcohol preservation. Photo by Jérôme Jourde.

Figure 4 .

 4 Figure 4. Grandidierella japonica, male gnathopod 1 left, inner surface (A), detail of anterior margin of the gnathopod 1 carpus, arrows show the transverse ridges (B), three teeth (arrows) on carpus distal part (C). Alcohol preserved specimen collected at the Bellevue station on 20 August 2012. Photo by Jérôme Jourde.

Acknowledgements

The authors are grateful to the League for Protection of Birds staff (LPO), especially S. Travichon, for funding this research through FEDER. The LPO staff performed the RNF sampling program. L. Jomat's help was particularly appreciated during the 2012 sampling session. Thanks are due to C. Curti for preparing the map and T. Worsfold for supplying some papers (Smith et al. 1999 andAshelby 2006). JJ was financially supported by the Région Poitou-Charentes through CPER funding, the Université de La Rochelle and CNRS. This study complied with the Moëze-Oléron nature reserve regulations and was supervised by Ph. Delapporte. Authors gratefully thank the three anonymous reviewers and Dr J.M. Hanson (Ed.) for their valuable comments that helped improve this short communication.


Antoine Manzanera
email: antoine.manzanera@etca.fr

Thierry M Bernard
email: thierry.bernard@ensta.fr

Fran Coise Prêteux
email: francoise.preteux@sim.int-evry.fr

Bernard Longuet
email: bernard.longuet@missiles.aerospatiale.fr

Ultra-fast skeleton based on an isotropic fully parallel algorithm

Keywords:

In this paper we introduce a new thinning algorithm, called MB, which is optimized with respect to the total number of elementary Boolean operators needed to perform it. We rst emphasize the sound foundations of the algorithm, which is built by expressing into the Boolean language the three following constraints: (1) homotopy, (2) median axis and (3) isotropy. The MB algorithm bene ts from both novel algorithmic ideas and systematic logic minimization. By hunting down any redundancy in the expressions of topological/geometrical features, we achieve a procedure that is: rstly, dramatically low-cost, as it is completely computed in 18 Boolean binary operators per iteration, and secondly, fully parallel, or one-single-pass, which guarantees that the number of iterations equals half the biggest object thickness.

Introduction

The process that consists in peeling iteratively a black object on a white background while preserving its topological properties has given rise to intensive international research activities for the last forty years with hundreds of published papers. The importance of such an investigation is due to the interest in digital skeletons (or image thinning), as a fundamental pre-processing step in pattern recognition and image analysis. Its duration is due to the fact that no de nitely satisfying solution has been found.

Properties required for a skeleton can vary slightly according to the applications under study. Let us mention the most usual ones, ranked by order of importance:

{ Homotopy: the skeleton must preserve the topology of the original image.

{ Median axis: the skeleton must contain the centres of maximal balls. { Isotropy: skeletonization and object rotation must commute, at least for rotation angles multiples of =2.

{ One-pixel Thickness: speaks for itself. { Noise Immunity: the skeleton must be fairly unsensitive to noise on the image (boundary pixels added or removed).

It is well-known, however, that theses requirements cannot be satis ed simultaneously, as some of them are contradictory. In particular, Noise Immunity is incompatible with keeping the whole median axis in the skeleton. Likewise, One-pixel Thickness is incompatible with Isotropy, but can be obtained by a low-cost post-processing step on two-pixel-thick lines. So we decide to restrict ourselves to the three former constraints, as they seem the most fundamental ones.

Thinning algorithms which are both iterative and local may be either sequential or parallel. In this paper, we consider only the parallel framework. We propose a dramatically fast thinning parallel algorithm called MB (after the names of its two creators). Indeed MB proves to be faster than all other algorithms we know of, in a fundamental sense: for us, the fastest possible algorithm is the one that minimizes the overall computational e ort required to achieve the desired image transformation. More precisely, whereas the cost of parallel algorithms is often de ned as the number of iterations before convergence 5], 4], we rather de ne it as the number of elementary operations performed per pixel during the complete execution of the algorithm.

The paper is organized as follows. In the next section, we simply present the MB algorithm as a recipe, and show some experimental comparative results. Section 3 introduces the complexity measure we use to quantify the computational cost of the MB algorithm and its competitors. Section 4 details the di erent issues of parallel thinning (according to the previously chosen criteria) and explains how the MB algorithm deals with them.

The MB algorithm

Let us rst introduce the formalism and related notations used in this paper.

Here, Z 2 is the discrete plane, represented by a square mesh. A binary image X is a subset of Z 2 . Considering X, a point p of Z 2 or pixel is characterized by its binary value x = 1 X (p), where 1 X is the characteristic function of the set X. The convention used to designate the value of an 8-neighbor is shown on Figure 1. The MB procedure appears in Table 1, including some hint comments to get the spirit of the algorithm at once (before reading Section 4). Computations therein only involve Boolean operators (i.e. Boolean functions of two binary variables).

Four of them are actually used, with the following notations: symbol ^stands for the conjunction (AND), symbol _ for the disjunction (OR), symbol n for the exception (AND NOT) and symbol for the inequality (XOR). The procedure uses intermediate pixel binary variables a, b and c that actually correspond to

NW X X N X NE X W X SW X E
X SE X S X Fig. 1. Pixels values in the 8-neighborhood.

Table 1. The MB procedure.

The following sequence is repeated for all pixels within a parallel framework, until stability:

( == removed pixels are those that belong to B but not to C binary images A, B and C. Figure 2 shows some results of the MB algorithm. On these various examples, the three criteria we have selected in the introduction are met. The two-pixel-thick segments that appear in the produced skeleton are a natural outcome of the isotropy of the MB procedure. Anyway, there exist arbitrary thick objects that must not be thinned, such as the one shown in the top right corner of the image, which is indeed preserved by the MB algorithm. Table 2 outlines the main characteristics of the MB algorithm, to be detailed in the next sections.

Complexity measure

Before going further into the MB algorithm, let us consider its complexity. Counting the number of symbols ^, _, and n in the MB procedure (cf. Table 1), leads to assign a computational cost of 18 to each iteration. This measure represents the number of two-input logic components that are needed for the computation, no matter if it is at the software or hardware level. This measure has actually been used since the early times of logic synthesis to de ne the complexity of Boolean functions, as recalled hereunder 17]:

De nition 1. Let f : f0; 1g n ! f0; 1g be a Boolean function of n variables. Let B 2 be the set of the Boolean functions of two variables ( and, or, xor : : :). A circuit over B 2 is a connected, acyclic oriented graph with nodes either having in-degree 2 and labeled by a function of B 2 (these nodes are called gates), or having in-degree 0 and labeled by variables (these nodes are called leaves).

Only one node has out-degree 0 and is called output. A node computes a value by applying its labeling function to the values computed by its preceeding nodes.

Thus a circuit with n distinct variables labeling its leaves computes a Boolean function f of n variables in its output. is called a syntax of f, whereas f is called the semantic of .

De nition 2. The Shannon complexity of a Boolean function is equal to the number of gates of its most compact syntax.

Here, due to the parallel expression of the MB algorithm, the Shannon measure represents the minimal execution time on a basic Cellular Automata machine, just as the one developed in our team, under the form of a Programmable Arti cial Retina 13]. However, the Shannon measure makes sense for any software or hardware implementation, as it is related to Area-Time complexity. It also represents the minimal amount of energy required to perform the computation of a given Boolean function, as every operation between two bits of information physically consumes some energy quantum, whatever the computation medium.

Computing digital skeletons

We now move to the algorithmic principles. Here, the MB algorithm is presented following a constructive approach. Using fully isotropic procedures, it is shown rst how to keep the medial axis in the skeleton, then how to preserve homotopy, even when pixels are removed in parallel. For each of these issues, some basic de nitions or results are recalled before a precise explanation of the MB algorithm operation is provided.

Distance map -Local maxima

In the discrete plane represented by the square mesh, two topologies can be de ned, depending on the neighborhood relation: either the 4-connectivity, where a pixel has one neighbor in each cardinal direction (N, E, W and S), or the 8connectivity, where a pixel has 4 more neighbors (NE, NW, SW, SE). This induces two basic distances in Z 2 : 4 , or diamond distance, and 8 , or square distance. De nition 3. Let be a distance in Z 2 . Let B x n = fy 2 Z 2 ; (x; y) ng be the ball of centre x 2 Z 2 and radius n 2 N. Let X Z 2 . The collection of the centres of maximal balls is the set: S(X) = n2N fx 2 Z 2 ; B x n X and 8y 2 Z 2 ; 8m 2 N; B y m X ) B x n 6 B y m g De nition 4. Let X Z 2 . The distance map associated with X is the function: This set is related to the notion of median axis. Historically, it has been the rst (and last !) sheer de nition of the skeleton 2]. However, it is not a satisfying shape descriptor, since it does not preserve topology. Anyway, we must guarantee that the set we are building by iterated passes of thinning contains the median axis. A natural idea is to compute explicitely the set of local maxima in order to impose its presence in the result 20], 3]. The simplest iterative parallel procedure that provides the local maxima for distance 4 is shown on Table 3. Lines 1 and 2 in Table 3 compute the eroded set of Table 3. Local maxima procedure.

: Z 2 ! N x 7 ! (x) = (x; X c ) Property 1. S(X) = S fx
(

) a = xN ^xE (2) a = a ^aSW ^x (3) b = aN _ aE (4) b = b _ bSW _ a (5) x = x n b 1
image X, i.e. the set A of pixels of X whose 4-neighbors are all in X. Lines 3 and 4 compute the dilated set of A, i.e. the set B of pixels of Z 2 for which at least one 4-neighbor is in A. Finally the set-di erence of X and B is computed in line 5. This procedure removes every pixel x whose neighborhood matches the pattern shown on Figure 3.1, or one of its =2 rotated con guration. The hachured pixels have value 1, and at least one of the three pixels denoted by y has value 0. The computational cost is 7. What we compute in the MB algorithm is slightly di erent, and actually a bit more restrictive. Refering to Table 1, lines 1-3, together with line 8 (in which we temporarily forget about c), removes every pixel x whose neighborhood matches a pattern called ( ), shown on Figure 3.2, or one of its =2 rotated con guration. The hachured pixels have value 1, the white pixel has value 0. Thus it is obvious that a super-set of the local maxima will be produced by the MB algorithm: this makes the rst step of a proof. Matching pattern ( ) increases the cost up to 11 operations (instead of 7), but as we will see, it is worth the extra.

Homotopy

The notion of homotopy in the real plane R 2 is originally de ned between arcs, i.e. continuous functions from a real interval a; b] to R 2 . Two arcs are homotopic if there exists a continuous function mapping one to the other. This relation being an equivalence relation, it is said that 2 open subsets of R 2 are topologically equivalent if their sets of equivalence classes are isomorphic. In other words, two subsets of the plane are topologically equivalent (we may say homotopic) if there exists a one-to-one mapping between their connected components, and another one between the connected components of their complementary sets (the holes), both preserving the relation \is contained inside...". Indeed, a connected component (or a hole) Y is said to be contained inside the connected component X if there exists a closed arc in X that surrounds Y . This means that Y is completely contained in the interior of . The notion of homotopy is indeed sharply based on the Jordan theorem : a simple closed arc (or Jordan arc) divides the plane in two distinct regions : the interior and the exterior. As mentioned earlier, two kinds of topology can be used in the discrete plane. In both cases, however, the Jordan theorem is no longer valid, and so the notion of hole is not well-de ned. To cope with this problem, two distinct topologies must be used for the image and for its complementary. So homotopy will make sense if one always considers the 8-connectivity for the image and the 4-connectivity for its complementary (or vice-versa). We may now de ne the notion of simple point.

De nition 5. Simple point

Let X Z 2 be a binary image. Let a 2 X. Point a is simple i Xnfag is homotopic to X.

A well-known result is that the simplicity of a point can be determined by looking only at its 3x3 neighborhood. The forerunner in the search of a formula over the 3x3 neighborhood to characterize simplicity is Rutowitz 16]. The more elaborated notion of connectivity number was rst de ned by Yokoi 22], though it had been used earlier by Hilditch 7]. The 8-and 4-connectivity numbers are respectively de ned as follows:

De nition 6. Connectivity numbers

Nc 8 = 3 X i=0 (x 2i+1 _ x 2i+2 ) n x 2i : Nc 4 = 3 X i=0 x 2i n (x 2i+1 ^x2i+2 ) :
where the x j represent the 8-neighbors of x in the following way: x 0 = x E , and so on in a counter-clockwise sense until x 7 = x SE . Sign + within indices stands for the addition modulo 8. The N-connectivity 1 number of a pixel x within its 8-neighborhood V (x) is exactly equal to the number of N-connected components of V (x)nfxg, except for N-interior points (points of the image for which all their N-neighbors are also in the image). The N-connectivity number provides an easy way to characterize the N-simplicity. A point is N-simple if and only if its Nconnectivity number equals one.

1 N = 4 or 8.

We can compute the 8-simplicity of pixels by using the procedure shown on Table 4, to be read column after column. It computes exactly the formula of De nition 6 and the related cost is 15 operations. The 8-simplicity can also be Table 4. Hilditch procedure.

(1) a = x _ xE (6) a = x _ xN [START_REF] Lam | Thinning methodologies : A Comprehensive Survey[END_REF] [START_REF] Lam | An Evaluation of Parallel Thinning Algorithms for Character Recognition[END_REF]

b = aSE n xS (2) d = aN n xE (7) b = aW n xN
c = c _ (d ^b) == c = 1 () Nc8 > 1 (3) a = aSW n xW (8) c = c _ (d ^b) (12) d = d _ b == d = 1 () Nc8 1 (4) c = d ^a (9) d = d _ b (5) d = d _ a (13) a = d n c == a = 1 () Nc8 = 1
expressed under the following pattern-matching form. A pixel x is neither an interior nor a simple point if its neighborhood matches one of the two patterns represented in Figure 4, along with their =2 rotated con gurations. The con- verse is also true, except if V (x) does not contain more than two points. By the way, this is the property that was used by Arcelli 1] for the computation of his skeleton. Here it reveals some redundancy between the computations of local maxima and simple points. Indeed, if a pixel x is considered as removable by the rst part of the MB algorithm (because it matches pattern ( )), then its neighborhood may match pattern ( ), but never pattern ( ). This fact makes it possible to save operations, by computing only the pattern matching of ( ), as performed by the end of the MB procedure (lines 4-7).

x x (γ) (β)
So, knowing which pixels match pattern ( ) (or a =2 rotated con guration) reduces to 6 (instead of 15 !) the number of operations required for the computation of simplicity. This a posteriori justi es the enigmatic choice of ( ) in the previous section. Anyway, we have now shown that the points removed by the MB algorithm are neither local maxima nor simple points. This is still not sucient as a proof, since we must now consider the last but not least characteristic of the MB algorithm: the parallel removal.

Parallel computing of the skeleton

As a matter of fact, simplicity according to De nition 5 is an individual characteristic. In general, the parallel removal of simple points leads to disconnection, with the disappearance of the two-pixel-thick lines. To cope with this major di culty, three di erent approaches have been devised:

Directional sub-iterations: Rosenfeld 9] proved that simple points could be removed in parallel without changing topology if one allows the pixels to be removed in one direction only (e.g. east border simple points). In this kind of algorithms, that we now denote DS-algorithms, the thinning process peels the image removing border pixels in one direction after the other. The most e cient of these algorithms operate in two passes (e.g. N and W, followed by S and E) 19]. The characterization of the skeletal points is in general simpli ed 8], but the number of iterations multiplied by two. Note that, in such a case the skeleton is by nature non isotropic, since the result depends on the order in the processing directions.

Semi-parallel sub-iterations: by degenerating the parallelism according, for example, to the respective parity of the lines and columns, one may clusterize the pixels, and compute a parallel iteration of the skeleton by processing as much passes as there are pixels in the cluster 12]. The result of these algorithms (SPalgorithms) is also sensitive to the choice of the order in the sub-iterations, and furthermore, it produces zigzagging artifacts on straight lines, as pointed out in 10].

Fully parallel: removing non-skeletal pixels in all directions without changing the topology is possible provided that larger neighborhoods are examined 6]. As a consequence, if the number of iterations is reduced in comparison to multi-subiterations algorithms, the computational cost of one iteration is always larger, to such a point that their speed may be smaller in some cases. See for example, 18], 21], and 5]. A general scheme to prove the soundness of FPalgorithms is provided by Ronse 15], who extended the notion of simplicity to sets of points, and proved that the parallel notion of set-simplicity is equivalent to the existence of an order according to which all points in the set can be removed sequentially, every point being simple when it is removed 14]. Now the good news is that the MB algorithm proves to belong to the FPclass: points that match pattern ( ) but not ( ) actually form a simple set! In 15], Ronse gave minimal conditions for checking connectivity preservation of parallel thinning algorithms. Theorem 3.5 together with Proposition 3.6 of this paper leads to the following property: A parallel thinning algorithm preserves 8-connectivity if: [START_REF] Arcelli | A condition for digital points removal[END_REF] The pixels removed are simple, (2) A connected component contained in a 2x2 square cannot be completely removed, and (3) Two 4-connected pixels removed at the same time would have been removed as well if treated sequentially. Condition (1) has been proven in Section 4.2. Condition (2) is obviously met, as a pixel is removed only if it is 4-connected to an interior pixel. To see that Condition (3) is also satis ed, let us notice that two 4-adjacent pixels are simultaneously removed only if they match the pattern showed on Figure 5, in which none of the two pixels belongs to the pattern ( ) of the other. This proves Fig. 5. Case of two pixels 4-connected.

that the MB algorithm is an FP one. As such, its number of iterations before convergence equals the maximum of the distance map (cf. De nition 4), i.e. half the thickness of the biggest object in the image. Finally, removing simple sets, but as big as possible, while preserving the median axis, through such a compact isotropic procedure is the remarkable achievement of the MB algorithm. Its superiority can be appreciated on Table 5 which shows a comparison with several (fully or not) parallel algorithms: MB is nearly twice as fast as the fastest known algorithm ! Table 5. Comparing the cost of parallel thinning algorithms. d stands for the maximal object thickness (i.e. the diameter of the biggest ball contained in the image). The number of elementary operations given for the other algorithms is sometimes only an estimation, as the quoted papers did not always provide a logic minimization of their algorithm. Note that 5] was ranked second among ten algorithms in

Isotropy and One-pixel Thickness

The MB algorithm computes the skeleton by logical operations that are based on the matching of patterns ( ) and ( ), with all their =2 rotated con gurations. Then these operators are completely symmetrical. As the algorithm is fully parallel (no spatial subiteration), this guarantees isotropy. Then the presence of two-pixel-thick lines in the skeleton is expected. If required, one-pixel thickness can be obtained by using two directional passes at a very low extra cost. For example, if we compute a North, then a West point deletion with the Jang & Chin algorithm, the post-processing has a cost of 16 operations (whereas an MB iteration costs 18).

Conclusion

We have presented a new parallel iterative thinning algorithm which computes the skeleton of an image in what we believe to be the purest form. This skeleton must (a) contain the median axis for the diamond distance, (b) preserve topology and (c) be obtained through a purely isotropic procedure.

To remove pixels from the original image, the MB algorithm ful ls the three former requirements by checking two pixel conditions that we may call \de nitely not a local maximum" (i.e. matching ) and \semi-simple" (i.e. not matching ). While extremely simple to compute, the combination of these two conditions allows a most e cient fully parallel (or one-pass) operation of the MB algorithm. With the help of systematic logic minimization, this results into a dramatically low computational cost in terms of logical operations needed for the complete execution of the algorithm.

In spite of its (much) faster computation, the MB skeleton is comparable in quality to those produced by other algorithms, as shown by the experimental results. While its preferred implementation is on SIMD machines that compute binary logic, the speed advantage of the MB algorithm should remain on most computers, parallel or not, due to the fundamental character of the Shannon measure.

  1) a = xN ^xE (2) a = a ^aSW ^x == A = eroded set of X (3) b = (aS n xN) _ (aN n xS) _ (aE n xW ) _ (aW n xE) == B = fpixels between a point in A and a point in X g (4) c = x xE (5) c = c ^cN ^(x xN) (6) c = c _ cW (7) c = c _ cS == C = fpixels that belong to pattern ( ) of section 4.3 g (8) x = x n (b n c)

Fig. 2 .

 2 Fig. 2. Experimental results. Image (a) is the original one, whereas image (b) is the result of the convergence of the MB algorithm, reached after 6 iterations. Images (d) to (h) show a detail for the 4 rst iterations (the grey pixels are the removed ones) and image (i) represents the overall process. For comparison purposes, image (c) shows the result obtained by the Jang and Chin algorithm 8] on the same image.

  2 X; 8y 2 B x 1 ; (y) (x)g: In other words, the collection of the centres of maximal balls corresponds to the set of local maxima of the distance map.

Fig. 3 . ( 1 )

 31 Fig. 3. (1) Non local maximum pattern and (2) Pattern ( ).

Fig. 4 .

 4 Fig. 4. Gap patterns.

Table 2 .

 2 Main characteristics of the MB algorithm

	{ Fully Parallel thinning algorithm. { Number of iterations before convergence equals half the maximal thickness. { 18 elementary Boolean operations per iteration.


Thierry M Bernard
email: tbernard@ensta.frmanzaner@etca.fr

Antoine Manzanera

Improved Low Complexity Fully Parallel Thinning Algorithm

A fully parallel iterative thinning algorithm called MB2 is presented. It favourably competes with the best known algorithms regarding homotopy, mediality; thickness, rotation invariance and noise immunity, while featuring a speed improvement by a factor two or more owing to a smaller number of operations to perform. MB2 is grounded on a simple physics-based thinning principle that conveys both quality, efficiency and conceptual clarity. It is particularly suited to data parallel execution.

-Introduction

Machine vision has often to deal with elongated shapes, of which the length is much larger than the thickness. Exemplary applications are found in character recognition or medical imaging. It is often worth representing these elongated objects by simple lines, i.e. onepixel-thick connected sets of pixels. This allows a lighter representation easing further pattern analysis. Hence, the notion of skeleton has been introduced, which most usually applies to binary images.

. This is all the more surprising that there are only a few readily understandable requirements that a skeleton should fulfil. Then one could expect a rigorous characterisation of any skeletonisation algorithm with respect to them. Here are the usual ones: • Homotopy: the skeleton must preserve the topology of the original image (any hole must remain). • One-pixel-thickness: the skeleton should be made of curves, i.e. one-pixel-thick objects. • Mediality: the skeleton should lie in the middle of the shape, with every point of the skeleton the same distance from the two closest borders of the object. • Rotation invariance: skeletonisation and object rotation should commute. Due to spatial discretisation, this can only be true for rotation angles multiples of π/2. But this should also be approximately satisfied for arbitrary rotation angles. • Noise immunity: the skeleton should be fairly insensitive to noise on the image (boundary pixels added or removed).

It is well-known that some of these requirements are contradictory. But this must not be an excuse for lack of clarity and precision in the characterisation of a skeletonisation algorithm. Furthermore, these antagonisms are not that strong. We will actually explain in section 2 how to get away with them.

Beside intrinsic quality and characterisation clarity, computational speed is another important matter. As a low level image processing operator, skeletonisation can take advantage of parallelism. The most common way to do so is to implement skeletonisation as a thinning procedure that iteratively peels objects. Then massive data parallelism [START_REF] Arcelli | Parallel thinning of binary pictures[END_REF] proves particularly suitable due to the locality of the thinning procedure: only the values of the closest neighbours are necessary to decide whether a pixel can be removed or not. The number of iterations is determined by the maximal object thickness (the radius of the largest ball contained in the image). Another key advantage of data parallelism is that it allows an intrinsic isotropy of the thinning procedure, which is most important to ensure mediality. This is a point where many sequential algorithms fail.

As will be detailed in section 3.6, we measure the speed of a parallel iterative algorithm (such as thinning) by the total number of Boolean operations performed per pixel before convergence. We call it the Shannon measure due to its obvious relationship to circuit complexity. Its main advantage is its universality.

In this paper, we present a parallel iterative thinning algorithm called MB2 which favourably competes with the best known algorithms regarding the five above criteria, while featuring a speed improvement by a factor two or more. Like its predecessor MB [START_REF] Manzanera | Ultra-fast skeleton based on isotropic fully parallel algorithm[END_REF] which was even faster but with limited rotation invariance, MB2 is grounded on a unified thinning principle that conveys both efficiency and clarity. Section 2 recalls some preliminaries before exposing our strategy to get a rational trade-off between the different skeletonisation criteria. The MB2 algorithm is presented in section 3 under both pattern matching and procedural forms. Then it is analysed formally and experimentally.

-Which skeleton ?

Several properties are desirable for a skeleton, which have been previously listed. The present section recalls definitions and results related to them before discussing their compatibility. This discussion leads to strategic choices that allow to best satisfy all criteria.

-Basics

Let us first recall that binary images can be considered as subsets of Z 2 (Z is the set of integers). These subsets are always supposed finite (this formally corresponds to images that have pixels with value 1 only in a finite window). A digital topology on Z 2 is defined by adjacency relationships between pixels. For k=4 or 8, the "k-topology" designates the topology for which a pixel is adjacent to its k closest neighbours (for the Euclidean distance). Expressions like k-adjacent or k-neighbour directly follow from this definition. The k-topology induces a distance δk: δ4 is called the square distance on Z 2 and δ8 the diamond distance, owing to the ball shape they induce (cf. Def.2 in §2.3). δ4 is also known as the Manhattan distance. Adjacency relationships are readily extended from points (pixels) to subsets of Z 2 (images). A⊂Z 2 and B⊂Z 2 are said k-adjacent if there exist a∈A and b∈B such that a and b are k-adjacent. X⊂Z 2 is said to be a k-CC (k-connected component) if there does not exist any partition of X into two non k-adjacent subsets. x∈X⊂Z 2 is said k-interior to X if all its k-neighbours belong to X.

-Homotopy (connectivity preservation)

Homotopy is a concept which is more naturally defined in the continuous real plane R 2 than in the discrete integer plane Z 2 . In particular, in R 2 , Jordan's theorem tells that a simple closed arc partitions the plane into two unconnected regions: the interior and the exterior. In Z 2 , this important result no longer holds. To overcome this difficulty and most of its harmful consequences, the most appropriate and common solution is to use the k-topology (k=4 or 8) for the foreground of the image (the objects) and the k'-topology for the background, with k'=12-k. In the rest of this paper, and in particular for the MB2 algorithm, the choice is k=8 and k'=4. The 8/4 notation will recall this fact.

Two (finite) subsets of Z 2 are homotopic if there exists a one-to-one mapping F between their respective k-CCs and another one B between the respective k'-CCs of the background, such that the tuple (F,B) preserves the adjacency relationships between connected components. Calling C∞ the only k'-CC that extends to infinity in the background of any finite subset, a supplementary condition is B(C∞)=C∞.

An image and its skeleton must be homotopic. Since skeletonisation only removes points from the foreground, this implies inclusion relationships which actually make homotopy simpler to express: when removing points, k-CCs of the foreground must neither split nor be erased and k'-CCs of the background must neither merge nor be created. A point (respectively a set of points) which can be removed while meeting these criteria is called a simple point (respectively a simple set). A parallel algorithm will preserve connectivity iff (if and only if) the several points it removes simultaneously at each iteration form a simple set. A well-known difficulty is that reunions of simple points are generally not simple sets. Here are some formal characterisations of simple points and sets. Notations: Logical and arithmetic operators are represented using the C-language syntax. Signs &, |, ^respectively stand for the logical AND, OR and XOR.

Sign + designates standard arithmetic addition. Following a usual set theory notation, sign \ stands for ANDNOT. Given a binary image X, x stands for the binary value of an arbitrary pixel and x N , x NE , x E , x SE , x S , x SW , x W , x NW stand for the values of its eight closest neighbours (designated using the cardinal points). Definition 1: Given an image X, the connectivity number (for k=8 and k'=4) of a pixel is C8/4

(x) = (x N |x NE )\x E +(x E |x SE )\x S + (x S |x SW )\x W + (x W |x NW )\x N Theorem 1 [4]: A point x is simple iff C8/4(x) = 1.
But how to guarantee that a thinning algorithm removes only simple sets ? Here is an answer. Theorem 2 (adapted from [START_REF] Ronse | Minimal test patterns for connectivity preservation in parallel thinning algorithms for binary digital images[END_REF]): For a parallel thinning algorithm to preserve 8/4 connectivity, it is sufficient to simultaneously respect the three following conditions:

(a) all pixels removed are simple;

(b) an 8-CC contained in a 2× 2 square cannot be completely deleted;

(c) any pair of 4-adjacent pixels removed simultaneously would also be removed sequentially.

-Mediality

Mediality is a geometrical notion which can only be based on the choice of a distance δ. For the sake of rotation invariance, the Euclidean distance δe would be the best choice. However the square and diamond distances δ4 and δ8 come out much more naturally within the frame of iterative thinning procedures. Here are now a few classical definitions and results that precise the notion of mediality. Definition 2: Let δ a distance. The δ-ball B(x,r) of centre x and radius r is the set { y∈Z 2 ; δ(x,y)≤r }.

For δ= δ4 (respectively δ8) we will simply note 4-ball (respectively 8-ball). Now, let X⊂Z 2 a binary image. Definition 3: Let δ a distance. A maximal δ-ball in X is a δ-ball B⊂X with no other δ-ball B' (but itself) such that B⊂B'⊂X.

The centres of maximal δ-balls are the points that lie in the middle of the shape from the viewpoint of distance δ.

The following results tell how to find them. Definition 4: Let δ a distance. The distance map associated with X is the function Φδ from Z 2 to N (or R + ) such that Φδ(x) = δ(x,X c ) = min{ δ(x,y) ; y∉X }.

For δ= δ4 (respectively δ8), we will simply note Φ4 (respectively Φ8). Theorem 3: The centres of the maximal k-balls (k=4 or 8) in X are the local maxima of Φ k over their k-neighborhood, i.e. the set { x∈X / ∀y∈Bk(x,1) Φk(x) ≥ Φk(y) }

-Homotopy versus one-pixel-thickness and mediality

Figure 1a shows a binary image (each square is a pixel) from which no black pixel can be deleted without creating a white 4-CC or merging two. It is an exemplary case which shows that homotopy may imply arbitrary large thickness. Figure 1b presents another case where thinning could produce a one-pixel-thick skeleton but would violate mediality. The skeleton is actually meaningless for such images. Fortunately, these unwanted pathological situations can be characterised and even detected. But this goes beyond the scope of the present paper, in which we will simply not apply our thinning algorithm on such pathological images.

-Mediality and rotation invariance versus one-pixel-thickness

Even in the absence of pathological configurations, mediality is in itself an obstacle to one-pixel-thickness. Considering a square-shaped object of size 2×2, each of the 4 pixels are local maxima. Therefore, none should be removed, as is also dictated by rotation invariance. Actually, mediality and rotation invariance only allow two-pixel-thickness. Requiring one-pixel-thickness everywhere would amount to force the thinning algorithm to make arbitrary choices. We think that a more rational approach is to accept the two-pixel-thickness limitation as an inherent characteristics of a skeleton. By the way, this is perfectly consistent with the implicit isotropy that only a data parallel thinning algorithm may feature, like MB2. Passing from two-pixel-thickness to one-pixel-thickness is then only a matter of simple post-processing (simpler than a single thinning iteration).

-Homotopy, mediality, noise immunity

Homotopy and mediality are fundamentally antagonistic with noise immunity. A single pixel added or removed may completely alter the connectivity and therefore the skeleton. Likewise, a single pixel added at the boundary of an object featuring a simple shape will often be a local maxima far from any other, therefore deeply changing a skeleton subject to the mediality constraint. Still MB2 proves experimentally (for understood reasons) to be more noise-immune than other highquality algorithms. But for a large part, we believe that noise immunity cannot be the responsibility of a thinning algorithm. It is rather the matter of some applicationdependent pre-, post-or concurrent processing.

-Putting it all together

The goal of section 2 was to determine the best possible trade-off between the different desirable properties of a skeleton. A main concern was genericity, which goes with conceptual clarity and hopefully efficiency. It turns out that homotopy, mediality and 2-or-1-pixel-thickness are the three prime compatible constraints once some peculiar and meaningless configurations are excluded. Then mediality is governed by the explicit or implicit choice of a distance, which also affects rotation invariance and, to a lesser extent, noise immunity. This strategy proves fully consistent with a data parallel framework, from which both isotropy and speed are expected. The MB2 algorithm is a parallel iterative algorithm that deletes points corresponding to certain neighborhood conditions. The latter are based on patterns displayed on figure 2. In these patterns, black and grey pixels belong to the foreground and white pixels to the background. Given an image, it is said that pixel x matches some pattern if, putting that pattern on the image with the black pixel on x, there is an exact coincidence of the image with the whole pattern. It is also considered that each pattern may be rotated by any multiple of π/2.

-The MB2 thinning algorithm

Definition 5:

The MB2 iteration consists in removing simultaneously all pixels that match α1 or α2, but not β. The MB2 algorithm repeats the MB2 iteration until stability is reached.

Considering the αi patterns (i=1 or 2), it appears that a point is removed by the MB2 iteration if it lies exactly between the background and a 4-interior point in the foreground to which it is n-adjacent, with n=4 for α1 and n=8 for α2. Actually, the αi patterns convey the physics of the thinning action and this is the strong conceptual originality of the algorithm. We believe this is responsible for the remarkable behavior of the algorithm as the next sections will show.

Another unusual feature of the MB2 patterns is their size. As α1 and α2 rotate around their origin (the black point), the whole centered 5×5 neighbourhood, but its four corners, is described. This contrasts with the other algorithms which attempt to minimise the size of this working neighbourhood [START_REF] Hall | Optimally Small Operator Supports for Fully Parallel Thinning algorithms[END_REF]. This is certainly crucial for computations performed using look-up tables, but meaningless otherwise. For us, the point was to choose the patterns that minimise computational complexity (cf. section 3.6).

-MB2 procedure

Let B4=B4(o,1) be the unity 4-ball (o is the origin of Z 2 ), as shown on figure 3. Note that B4 (translated) appears in the foreground part of both α1 and α2. Let us also recall a basic notion of mathematical morphology: the erosion of an image X by B⊂Z 2 , denoted XΘB, is the set of all points x∈Z 2 such that the translated set of B by x (acting as a vector) is completely included in X.

Table 1 presents an optimised procedure that performs the MB2 iteration in a data parallel framework: any computation with the local binary variables a1, a2, b, etc., is performed on the whole corresponding images A1, A2, B, etc. The notations used are those presented in section 2.2. Variable names have been chosen to be as explicit as possible, as explained in the table caption.

e4 = x N & x E ; e4 = e4 & e4 SW & x ; a1 = (e4 W \x E ) | (e4 E \x W ) | (e4 N \x S ) | (e4 S \x N ) ; d1 = x | x SW ; d2 = x | x SE ; a2 = (e4 SE \d1 N ) | (e4 NW \d1 E ) | (e4 SW \d2 N ) | (e4 NE \d2 W ) ; b = x ^ x N ; b = b & b E & (x ^ x E ) ; b = b | b S ; b = b | b W ; x = x \ ( ( a1 | a2 ) \ b ) ;
Table 1: A data parallel procedure that performs the MB2 iteration. Variable names correspond to the following outcomes of the procedure: E4 = XΘB4 while A1∩ X, A2∩ X and B∩X respectively contain the points of X that match α1, α 2 and β. Those points are removed from X in the last line.

The compactness of the MB2 procedure results from different features of the MB2 patterns: (a) their small number, (b) their simplicity, (c) their regularity, which allows the use of spatial decomposition techniques to compute them. Also, some redundancy between the patterns has been removed. In particular, the upper-left white point in pattern α2 is useless since pattern β would reject a black point there. Finally, the number of Boolean operations required by an MB2 iteration is as low as 28. Before comparing with the cost of other algorithms, quality is first to be examined, as the next sections do. As far as the memory requirement is concerned, the MB2 procedure uses 7 binary variables per pixel for readability purposes; but some of them could have been reused, thus lowering their number to 5 including image X.

-Homotopy

MB2 removes points in parallel all around the image. It is therefore called a fully parallel (FP) algorithm. This contrasts with a large family of thinning algorithms which remove points in several (4 or 2) directional (D) subiterations [START_REF] Jang | Analysis of thinning algorithms using mathematical morphology[END_REF][START_REF] Cardoner | Residuals + Directional Gaps = Skeletons[END_REF] (only pixels located on a particular side of the objects are removed at a time). For the latter algorithms, satisfying homotopy is a simpler issue [START_REF] Kong | Digital Topology : Introduction and Survey[END_REF]. On the other hand, MB2 needs Theorem 2 to prove that it preserves homotopy.

Condition (a) of Theorem 2 asks that every pixel removed is simple. Considering Theorem 1 and Definition 1, it can be shown that a point which is not simple necessarily matches either of the three patterns shown on figure 3 (or their rotated versions). But MB2 forbids β while α1 and α2 prevent points from matching B4 or γ. Condition (c) requires three cases to be examined: • If the two 4-adjacent pixels simultaneously removed both match α1 (respectively α2), then the only possible situation is that of figure 4a (respectively 4b) with all its rotations. It appears that if one is removed first, the other remains removable. • If one point matches α2 and the other α1, then the only possible situation is that of figure 4c. In that case, if the point that matches α 2 is removed first, the other remains removable. This ends the proof that MB2 is homotopic. From the details of the proof, it turns out that much of the homotopy is inherently conveyed by patterns αi. For us, this is yet another virtue of their physical meaning.

(a £ ) (b ¤ ) (c ¥ )

-Rotation invariance and mediality

The MB2 algorithm is 4-isotropic: the thinning action is exactly the same in the four cardinal directions (N, E, S, W). This results from the perfectly symmetrical expressions used in the MB2 procedure and from the full parallellism of the algorithm (no anisotropy induced through the order in which pixels are examined). Then exact rotation invariance is guaranteed for angles multiples of π/2. This 4-isotropy is also the reason why the MB2 skeleton is 2-pixel-thick in some places.

Actually, these nice properties were already featured by the predecessor of MB2, namely MB [START_REF] Manzanera | Ultra-fast skeleton based on isotropic fully parallel algorithm[END_REF] of which sample outputs are presented on figure 6b and7b. MB is only based on patterns α1 and β. As illustrated on figure 6, MB preserves all centres of maximal 4-balls. Thus the skeleton produced by MB is medial from the viewpoint of distance δ4. However, δ4 is not the ideal distance. Neither is δ8, on which the JC algorithm [START_REF] Jang | Analysis of thinning algorithms using mathematical morphology[END_REF] (cf. figure 7a) is based. In order to improve rotation invariance, it is desirable to be less biased by either of these two distances. The additional pattern α2 used concurrently with α1 by MB2 was introduced for this purpose. As a first outcome, MB2 -unlike MB -reduces 4-balls as well as 8-balls to their centres. Actually, all shapes shown on figure 5 (where each black square is a pixel) are reduced to a single point (superimposed in white). We call them fuzzy balls. Here are some more precise definitions and results. Theorem 4 (note the difference with theorem 3) and theorem 5 explain why MB2 does not preserve all centres of maximal 4-balls, but only those of maximal fuzzy balls (cf. figure 6abde). However, this results into a better isotropy, though the influence of δ4 is still predominant (the MB2 skeleton is included in the MB skeleton).

Figure 7 allows to appreciate the different characteristics of the MB2 algorithm versus some renowned thinning algorithms proposed within the last ten years: "JC" stands for the Jang & Chin algorithm [START_REF] Jang | Analysis of thinning algorithms using mathematical morphology[END_REF], "St" for the Stewart algorithm [START_REF] Stewart | A one-pass thinning algorithm with interference guards[END_REF] and "AFP3" is the best of 3 algorithms jointly presented in [START_REF] Guo | Fast Fully Parallel Thinning Algorithms[END_REF].

-Noise immunity and reconstructibility

Thanks to theorem 5, MB2 features significant noise immunity. Figure 8 shows the behavior of several algorithms on an elementary shape which is noise corrupted (right) or not (left). MB2 proves to feature levels of immunity comparable to that of AFP3. The main difference between them lies in the thickness, which is arbitrarily forced to 1 in the case of AFP3. However noise immunity implies information loss. Now, for some applications, the skeleton is expected to allow the reconstruction of the shape. For this purpose, every point in the skeleton is weighted with the iteration number at which it has been reached by the thinning process. For a point which is a local maximum, this gives the radius of the maximal ball it is the centre of. On figure 6cf, the radius of a skeleton point is represented by its grey level. In the case of MB2, it is not possible however to know if the ball to be regenerated from a skeleton point is for the δ4 or δ8 distance. A solution is to use octagonal balls as intermediate shapes between squares and diamonds. This provides an approximate reconstruction shown on figure 6f

-Speed

As mentioned in section 3.2, an MB2 iteration needs 28 Boolean operations with two binary operands. In practice, we have just counted the number of symbols &, |, ^ and \ that appear in table 1. This measure of computational complexity represents the number of two-input logic components that are needed to perform the computation. It has actually been proposed by Shannon [START_REF] Shannon | The synthesis of two-terminal switching circuits[END_REF] in the early times of logic synthesis to define the complexity of Boolean functions. It is still the reference in the field of Boolean complexity. The Shannon complexity of a data parallel procedure represents its minimal execution time on a basic cellular automata machine, such as the one developed in cooperation with the authors, under the form of a Programmable Artificial Retina [START_REF] Paillet | Making the most of 15k lambda2 silicon area for a digital retina PE[END_REF]. However, the Shannon measure makes sense for any software or hardware implementation as it is related to Area-Time complexity. It also represents the minimal amount of energy required to perform the computation of a digital function, as every operation between two bits of information physically consumes some energy quantum, whatever the computation medium.

Table 2 compares the complexity of several parallel algorithms. However, some of them are directional (D) and it takes them 2 to 4 passes to do the same work as fully parallel (FP) algorithms. This is often a source of confusion when comparing algorithm speed. To avoid that, table 2 gives the Shannon complexity per pixel of the overall skeletonisation process as a function of R, i.e. the radius of the biggest ball contained in the image. The MB and MB2 algorithms feature the best computational efficiency. In fact they are the first fully parallel algorithms to beat directional ones.

Algorithm

Refe

-Conclusion

We have described a fully parallel thinning algorithm which features the quality of AFP3 [START_REF] Guo | Fast Fully Parallel Thinning Algorithms[END_REF], one of the best algorithms, at the speed of JC [START_REF] Jang | Analysis of thinning algorithms using mathematical morphology[END_REF], the fastest one we were aware of before MB [START_REF] Manzanera | Ultra-fast skeleton based on isotropic fully parallel algorithm[END_REF]. Furthermore, MB2 is based on a clear thinning principle that follows a strategy defined at the beginning of the paper. Thanks to the algorithm genericity, recent work by the authors has allowed to extend it to 3D [START_REF] Manzanera | Medial faces from a concise 3D thinning algorithm[END_REF] and even to nD [START_REF] Manzanera | A unified mathematical framework for a compact and fully parallel n-D skeletonisation procedure[END_REF]. Ongoing work should lead to a formal characterisation of the algorithm.

Figure 1 :

 1 Figure 1: Pathological images.

Figure 2 :

 2 Figure 2: The MB2 patterns (which come with all their π/2 rotated versions).

4 Figure 3 :

 43 Figure 3: Non simple patterns Condition (b) is met since the foreground parts of α1 and α2 extend beyond a 2×2 square.Condition (c) requires three cases to be examined: • If the two 4-adjacent pixels simultaneously removed both match α1 (respectively α2), then the only possible situation is that of figure4a(respectively 4b) with all its rotations. It appears that if one is removed first, the other remains removable. • If one point matches α2 and the other α1, then the only possible situation is that of figure 4c. In that case, if the point that matches α 2 is removed first, the other remains removable.

Figure 4 :

 4 Figure 4: Simultaneous removal of a pair of 4-adjacent pixels.

Figure 5 :Figure 6 :

 56 Figure 5: Fuzzy balls.Notation: Given two points a and b of Z 2 , let BB(a,b) be their bounding box, i.e. the smallest rectangular area (with vertical and horizontal edges) including a and b. Definition 6: X is a fuzzy ball iff (∃x∈Z 2 )(∃r∈N) B4(x,r) ⊂ X ⊂ B8(x,r) and (∀y∈X) BB(x,y) ⊂ X. If so, point x is called its centre, and r its radius.Then the notion of maximal ball (cf. definition 3) may be straightforwardly extended to fuzzy balls with direct application to the characterization of the MB2 algorithm. Theorem 4: The centres of maximal fuzzy balls in X is the set { x∈X / ∀y∈B8(x,1) Φ 4 (x) ≥ Φ 4 (y) }. Theorem 5 : MB2 reduces any fuzzy ball to its centre.

Figure 7 :

 7 Figure 7: Comparison of 5 thinning algorithms on simple rotated shapes.

Figure 8 :

 8 Figure 8: Comparative noise immunity.

Table 2 : Computational complexity for several parallel thinning algorithms. Some complexities are only estimations as the quoted papers did not always provide a minimal Boolean expression of their algorithm.

 2


David T Drumm
email: ddrumm@ecoanalysts.com

Jérôme Jourde

Pierrick Bocher

A new species of the genus Monokalliapseudes (Crustacea: Tanaidacea: Kalliapseudidae) from French Guiana

Keywords: Tanaidacea, Kalliapseudes, Monokalliapseudes, French Guinea

A new species, Monokalliapseudes guianae, is described from French Guianese estuaries. It is distinguishable from its only congener most notably by lacking an exopodite on pereopod 1 and by the nature of the basal article of the uropod. The inner distal corner of the basal article is only slightly produced and lacks a rounded lobe. The bases of pereopods 2 and 3 lack numerous long setae. Sexual dimorphism is observed in the antennule, cheliped, and pereopod 1. Depending on size, males can exhibit two forms of chelae. A new diagnosis is presented for the genus Monokalliapseudes.

The ECOCOT project has been implemented in order to explore French Guiana intertidal mudflat ecosystem structure and functioning. As part of this project, the monitoring survey of benthic communities from intertidal mudflats led to the discovery of a new species of Monokalliapseudes, in addition to the only two local tanaid species, Halmyrapseudes spansii [START_REF] Băcescu | A new genus (Discapseudes n. g.) and three new species of Apseudidae (Crustacea, Tanaidacea) from the northeastern coast of South America[END_REF] Discapseudes surinamensis [START_REF] Băcescu | A new genus (Discapseudes n. g.) and three new species of Apseudidae (Crustacea, Tanaidacea) from the northeastern coast of South America[END_REF]. We herein provide an illustrated description of the new species and present a new diagnosis for the genus. The genus is restricted to waters of the southwest Atlantic off South America.

Materials and Methods

Samples were collected in the infralittoral area of a bare mudflat bordered by mangroves and the Sinnamary River (Fig. 1) at low level of spring tide using a sediment hand-corer (150 mm diameter) at 20 cm depth, sieved on a 0.5 mm mesh size and preserved in 70% ethanol solution. Specimens were examined and dissected in glycerol. All drawings were prepared using a drawing tube on a Wild M12 microscope. Specimens were measured from the tip of the rostrum to the posterior end of the pleotelson. Body width was measured on the widest part of the carapace.

Terminology follows [START_REF] Larsen | Proposed new standardized terminology for tanaidacean Crustacea[END_REF]. Type material is deposited at the National Left mandible (Fig. 2E) incisor process and lacinia mobilis each with seven teeth; spine row with at least eight pectinate setae. Right mandible (Fig. 3A) incisor process with six teeth; spine row with about 10 pectinate setae. Palp uniarticulated with row of long plumose setae. Molar process (not illustrated) with typical grinding surface. Labium (Fig. 3B) with hair-like setae on anterior and outer margins. Palp about 2.5 times as long as broad, with long hair-like setae on margins.

Maxillule (Fig. 3C) inner endite bearing three setulate setae and one short simple seta, hair-like setae distally on outer and inner margins. Outer endite with 11 long and one short spiniform setae, one pectinate subterminal seta and dense rows of hair-like setae on outer margin. Maxilla (Fig. 3D,E Carpus with two ventrodistal and one dorsodistal spiniform setae and with several simple setae. Propodus shorter than carpus, with seven ventral and two dorsodistal spiniform setae; outer surface with several simple setae; inner surface with one subdistal pectinate seta; one broom seta on middorsal margin. Dactylus with numerous distal 'sensory' setae and inner surface with two proximal simple setae.

Pereopod 2 (Figs. 4E,5A) basis approximately 2.3 times as long as broad, one broom and several short simple setae on dorsal margin, three ventral simple setae. Ischium with one simple ventrodistal seta. Merus same length as carpus, with several simple setae and one spiniform seta distally on inner surface. Carpus approximately 1.9 times as long as broad, with four spiniform setae on outer surface and one spiniform seta on inner surface; several simple setae. Propodus shorter than carpus, with five spiniform setae on outer and inner surfaces, several simple setae, and one broom seta midway on outer surface. Dactylus long and slender, shorter than basis, with one subdistal seta and two setae two-thirds length of dactylus; proximal lobe present, with ten setae. Pereopod 3 (Fig. 5B,C) similar to pereopod 2. Ischium with two setae.

Carpus with eight spiniform setae. Dactylus with three subdistal and one proximal setae; proximal lobe with six setae.

Pereopod 4 (Fig. 5D,E) basis approximately 2.2 times as long as broad with two proximal broom setae and three short subdistal simple setae. Ischium with three simple setae. Merus subequal to carpus, with two spiniform and several simple setae. Carpus with eight spiniform setae on outer and inner surfaces; four simple setae. Propodus with seven inner and seven outer spiniform setae and one terminal spiniform seta; one terminal pectinate seta; two simple setae and one broom seta proximally on outer surface. Dactylus with 15 distal setae.

Pereopod 5 (Fig. 5F,G) similar to pereopod 4. Carpus with six outer and nine inner spiniform setae.

Pereopod 6 (Fig. 5H) smaller than the other pereopods. Basis approximately 3.8 times as long as broad, with 14 long plumose setae on dorsal margin and eight plumose setae on ventral margin. Ischium with four ventrodistal simple setae. Merus shorter than carpus, with three plumose setae on dorsal margin and five plumose setae on ventral margin. Carpus subequal to propodus, with six plumose setae on dorsal margin and seven plumose setae on ventral margin. Propodus with seven thick spiniform setae and about 24 smaller pectinate setae. Dactylus short, similar to dactylus of pereopods 4 and 5, with 11 distal setae.

Pleopod (Fig. 6A) basal articles with five plumose setae. Exopodite with 22 and endopodite with 25 plumose setae. Uropod (Fig. 6B) basal article approximately 2.1 times as long as broad, with inner distal corner slightly produced and bearing one simple seta. Exopodite with three articles, last article longest and bearing three simple setae. Endopodite with 13 articles.

Male.---Very similar to female but with following differences: Antennule (Fig. 6C) first peduncle article long and narrow, approximately four times as long as broad. Outer flagellum with nine articles and six aesthetascs.

Cheliped (Fig. 6D,F) basis massive, with two short simple setae on ventral margin. Carpus approximately 2.8 times as long as broad, with double row of plumose setae ventrally and several simple setae on dorsal margin. Cheliped of male 7.6 mm in length (Fig. 6D) merus with large distal projection; propodus approximately 2.7 times as long as broad, with one large proximal and distal tooth on cutting edge; distal claw absent. Cheliped of male 6.3 mm in length (Fig. 6F) with distal projection of merus not as large; propodus approximately 1.7 times as long as broad; cutting edge with one large proximal tooth and seven spinules; distal claw present.

Pereopod 1 (Fig. 6E) basis, merus, and carpus with dorsal row of long plumose setae.

Etymology.---The specific name refers to the region where it was collected, Guiana.

Distribution.---French Guiana estuaries (Fig. 1).

Discussion

The new species is placed in the genus Monokalliapseudes, even though it lacks an exopodite on the first pereopod, because this character was shown to be homoplastic [START_REF] Drumm | Systematic revision of the family Kalliapseudidae (Crustacea: Tanaidacea)[END_REF]. It also shares several synapomorphies with Monokalliapseudes schubarti; for example, a pleotelson with simple setae along the lateral and posterior margins, a long and narrow labium palp, an inner endite of the maxillule with three setulate setae and one simple seta, the short dactylus of pereopod 6, and the male cheliped with a massive basis. The clypeus (plate-like structure of cephalon, anterior to labrum) is rarely described in tanaidacean taxonomy, but its systematic importance has been shown in Kalliapseudidae [START_REF] Drumm | Systematic revision of the family Kalliapseudidae (Crustacea: Tanaidacea)[END_REF]. The genera Cristapseudes [START_REF] Băcescu | Contributions to the knowledge of some Kalliapseudidae (Crustacea, Tanaidacea) from the NW of the Indian Ocean[END_REF]Phoxokalliapseudes Drumm &[START_REF] Drumm | Systematic revision of the family Kalliapseudidae (Crustacea: Tanaidacea)[END_REF] Since M. guianae also occupies similar habitats and is common and abundant, it is reasonable to suspect that it also plays a similarly important role. A, cheliped (outer). B, chela (inner). C, pereopod 1 (outer). D, pereopod 1 distal articles or carpus, propodus and dactylus (inner). E, pereopod 2 (outer). Scale bars = 0.1 mm. A, carpus and propodus of pereopod 2 (inner); B, pereopod 3 (inner); C, pereopod 3 (outer); D, pereopod 4 (inner); E, pereopod 4 (outer); F, pereopod 5 (outer); G, pereopod 5 (inner); H, pereopod 6 (outer). Scale bars = 0.1 mm. A, pleopod; B, uropod (ventral). Large male. C, antennule; D, cheliped (outer); E, pereopod 1 (inner). Small male. F, cheliped (outer). Scale bars: A--C, E, F = 0.1 mm; D = 0.2 mm.

  Figs.2--6

  ) with inner lobe of fixed endite bearing one posterior pectinate spiniform seta and with long anterior row of 20 plumose setae. Outer lobe of fixed endite with five thick pectinate setae, one long simple seta, several blunt-tipped setae, and one pectinate seta proximally on posterior face. Inner lobe of moveable endite with several blunt-tipped setae. Outer lobe of moveable endite with three pectinate and two setae bearing proximal setules and distal denticles. Outer margin with short hair-like setae. Maxilliped (Fig. 3F) basal article fringed with plumose and hair-like setae on outer margin, inner margin naked. First article of palp with one subdistal simple seta. Second article with one simple seta on outer distal corner. Last three articles of palp with double row of long plumose setae on inner margin. Endite with several pappose setae, hair-like setae on distal margin, inner margin with three coupling hooks. Epignath not illustrated. Cheliped (Fig. 4A, B) exopodite absent. Basis with two short simple setae on ventral margin. Merus longer than broad, with three simple setae. Carpus approximately 3.3 times as long as broad, with double row of long plumose setae ventrally and a row of simple setae dorsally. Propodus approximately 1.4 times as long as broad (excluding fixed finger), with diagonal row of plumose setae on inner face, several simple setae distally on inner and outer surfaces and near dactylus insertion; fixed finger with two ventral simple setae; cutting edge with about 18 spinules. Dactylus with three long pectinate setae on inner face and several short simple setae on inner and outer faces; cutting edge with eight teeth. Pereopod 1 (Fig. 4C, D) exopodite absent. Basis with four simple setae. Ischium naked. Merus approximately two times as long as broad, approximately 1.8 times as long as carpus, with several simple setae ventrally and dorsally.

  possess cusps on the clypeus (erroneously stated as on the labrum in Drumm & Heard 2011). The clypeus of M. guianae has a pair of long simple setae. If shown to be present in M. schubarti, this would be another synapomorphy of the genus. Besides lacking an exopodite on the first pereopod, Monokalliapseudes guianae can be distinguished from M. schubarti by the inner distal corner of the basal article of the uropod being only slightly produced and lacking a rounded lobe, and the bases of pereopods 2 and 3 lacking numerous long setae. Aspects of the biology and ecology of Monokalliapseudes schubarti have been intensively studied and have been shown to play an important ecological role in estuarine environments (Freitas-Júnior et al. 2013 and references therein).

Fig. 1 .

 1 Fig. 1. Map showing collection sites and type locality (star) of Monokalliapseudes guianae.

Fig. 2 .

 2 Fig. 2. Monokalliapseudes guianae. Ovigerous female. A, Holotype (USNM 1273026), habitus, dorsal (only setae bases are shown for pleopods 2-4); paratype, (USNM 1273028), B, antennule; C, antenna; D, clypeus and labrum; E, left mandible. Scale bars: A = 0.5 mm; B-D = 0.01 mm; E = 0.05 mm.

Fig. 3 .

 3 Fig. 3. Monokalliapseudes guianae. Ovigerous female. (USNM 1273028A). A, right mandible; B, labium; C, maxillule; D, maxilla (anterior); E, maxilla (posterior). F, maxilliped. Scale bars: A, F = 0.1 mm; B--E = 0.05 mm.

Fig. 4 .

 4 Fig. 4. Monokalliapseudes guianae. Ovigerous female, (USNM 1273028).

Fig. 5 .

 5 Fig. 5. Monokalliapseudes guianae. Ovigerous female. (USNM 1273028).

Fig. 6 .

 6 Fig. 6. Monokalliapseudes guianae. Ovigerous female. (USNM 1273028).

Figure 1

 1 Figure 1

Figure 6

 6 Figure 6

Acknowledgments

This is part of the program ECOCOT (Fonctionnement de l'écosystème côtier guyanais) funded by the Europe community and the Région Guyane through FEDER funding. The OBIONE Biodiversity Observatory is financially supported by the Région Poitou-Charentes through CPER funding, University of La Rochelle and CNRS. We are grateful to Antoine Gardel and the CNRS Guyane for providing facilities for sampling on French Guiana mudflats. We gratefully thank Céline Artero, Vietkuong (Toni) Bui, Alexandre Carpentier, Christine Dupuy, Christel Lefrançois, and Pierre-Yves Pascal for their help during sampling. We are also grateful to Brendan "Chip" Barrett (EcoAnalysts, Inc.) for reviewing an early draft of the manuscript.