Vincent Pilaud
email: vincent.pilaud@lix.polytechnique.fr

Francisco Santos
email: francisco.santos@unican.es

52b11

QUOTIENTOPES

same congruence class defines a complete fan. We prove that this fan is the normal fan of a polytope.

Introduction

Denote by S n the set of permutations of [n] := {1, . . . , n}. We consider the classical weak order on S n defined by inclusion of inversion sets. That is σ ≤ τ if and only if inv(σ) ⊆ inv(τ ) where inv(σ) := {(σ(i), σ(j)) | 1 ≤ i < j ≤ n and σ(i) > σ(j)}. The Hasse diagram of the weak order can be seen geometrically:

(1) as the dual graph of the braid fan of type A n-1 , i.e. the fan defined by the arrangement of the hyperplanes H ij := {x ∈ R n | x i = x j } for all 1 ≤ i < j ≤ n, directed from the region x 1 < • • • < x n to the opposite one, (2) or as the graph of the permutahedron Perm(n) := conv σ -1 (1), . . . , σ -1 (n) σ ∈ S n , oriented in the linear direction α := (-n + 1, -n + 3, . . . , n -3, n -1). See Figure 1 for illustrations when n = 4.

We aim at studying similar geometric realizations for lattice quotients of the weak order on S n . Recall that a lattice congruence of a lattice (L, ≤, ∧, ∨) is an equivalence relation on L that respects the meet and the join operations, i.e. such that x ≡ x and y ≡ y implies x ∧ y ≡ x ∧ y and x ∨ y ≡ x ∨ y . A lattice congruence ≡ automatically defines a lattice quotient L/≡ on the congruence classes of ≡ where the order relation is given by X ≤ Y iff there exists x ∈ X and y ∈ Y such that x ≤ y. The meet X ∧ Y (resp. the join X ∨ Y ) of two congruence classes X and Y is the congruence class of x ∧ y (resp. of x ∨ y) for arbitrary representatives x ∈ X and y ∈ Y .

Several examples of relevant combinatorial structures arise from lattice quotients of the weak order. The fundamental example is the Tamari lattice introduced by D. Tamari in [START_REF] Tamari | Monoides préordonnés et chaînes de Malcev[END_REF]. It can be defined on different Catalan families (Dyck paths, binary trees, triangulations, noncrossing partitions, etc), and its cover relations correspond to local moves in these structures (exchange, rotation, flip, etc). The Tamari lattice can also be interpreted as the quotient of the weak order by the sylvester congruence on S n defined as the transitive closure of the rewriting rule U acV bW ≡ sylv U caV bW where a < b < c are letters while U, V, W are words of [n]. See Figure 2 for an illustration when n = 4. This congruence has been widely studied in connection to geometry and algebra [START_REF] Loday | Realization of the Stasheff polytope[END_REF][START_REF] Loday | Hopf algebra of the planar binary trees[END_REF][START_REF] Hivert | The algebra of binary search trees[END_REF]. Among many other examples of relevant lattice quotients of the weak order, let us mention the (type A) Cambrian lattices [START_REF] Reading | Cambrian lattices[END_REF][START_REF] Chatel | Cambrian Hopf Algebras[END_REF], the boolean lattice, the permutree lattices [START_REF] Pilaud | Permutrees[END_REF], the increasing flip lattice on acyclic twists [START_REF] Pilaud | Brick polytopes, lattice quotients, and Hopf algebras[END_REF], the rotation lattice on diagonal rectangulations [START_REF] Law | The Hopf algebra of diagonal rectangulations[END_REF][START_REF] Giraudo | Algebraic and combinatorial structures on pairs of twin binary trees[END_REF], etc.

In his vast study of lattice congruences of the weak order, N. Reading observed that "lattice congruences on the weak order know a lot of combinatorics and geometry" [Rea16a, Sect. 10.7]. Geometrically, he showed that each lattice congruence ≡ of the weak order is realized by a complete fan F ≡ that we call quotient fan. Its maximal cones correspond to the congruence classes of ≡ and are just obtained by glueing together the cones of the braid fan corresponding to permutations that belong to the same congruence class of ≡. Although this result was stated in a much more general context (that of lattice congruences on lattice of regions of hyperplane arrangements), we restrict our discussion to lattice quotients of the weak order on S n .

VP was partially supported by the French ANR (grants SC3A 15 CE40 0004 01 and CAPPS 17 CE40 0018). FS was partially supported by the Spanish Ministry of Science (grants MTM2014-54207-P and MTM2017-83750-P), by the Einstein Foundation Berlin (grant EVF-2015-230), and by the NSF (grant DMS-1440140) while he was in residence at MSRI Berkeley in the fall of 2017. Figure 2. The Tamari lattice (right) is the quotient of the weak order by the sylvester congruence ≡ sylv (left). Each congruence class is given by a blue box on the left and corresponds to a binary tree on the right.

Theorem 1 ([Rea05]

). For any lattice congruence ≡ of the weak order on S n , the cones obtained by glueing together the cones of the braid fan that belong to the same congruence class of ≡ form a fan F ≡ whose dual graph coincides with the Hasse diagram of the quotient of the weak order by ≡. However, as observed by N. Reading in [START_REF] Reading | Lattice congruences, fans and Hopf algebras[END_REF], "this theorem gives no means of knowing when F ≡ is the normal fan of a polytope". For the above-mentioned examples of lattice congruences, this problem was settled by specific constructions of polytopes realizing the quotient fan F ≡ : J.-L. Loday's associahedron [START_REF] Loday | Realization of the Stasheff polytope[END_REF] for the Tamari lattice, C. Hohlweg and C. Lange's associahedra [START_REF] Hohlweg | Realizations of the associahedron and cyclohedron[END_REF][START_REF] Lange | Associahedra via spines[END_REF] for the Cambrian lattices, cubes for the boolean lattices, permutreehedra [START_REF] Pilaud | Permutrees[END_REF] for the permutree lattices, brick polytopes [START_REF] Pilaud | The brick polytope of a sorting network[END_REF] for increasing flip lattices on acyclic twists, Minkowski sums of opposite associahedra for rotation lattices on diagonal rectangulations [START_REF] Law | The Hopf algebra of diagonal rectangulations[END_REF], etc. Although these realizations have similarities, each requires an independent construction and proof. In particular, the intersection of the half-spaces defining facets of the classical permutahedron normal to the rays of F ≡ does not realize F ≡ in general, in contrast to the specific situation of [Lod04, HL07, LP18, PP18]. Our contribution is to provide a general method to construct a polytope P ≡ whose normal fan is the quotient fan F ≡ . We therefore prove the following statement.

Theorem 2. For any lattice congruence ≡ of the weak order on S n , the fan F ≡ obtained by glueing the braid fan according to the congruence classes of ≡ is the normal fan of a polytope. In particular, the graph of this polytope is the Hasse diagram of the quotient of the weak order by ≡.

We call quotientopes the resulting polytopes. Examples are illustrated in Figures 7, 8 and9.

2. Background 2.1. Polyhedral geometry. We briefly recall basic definitions and properties of polyhedral fans and polytopes, and refer to [START_REF] Günter | Lectures on Polytopes[END_REF] for a classical textbook on this topic.

A hyperplane H ⊂ R d is a supporting hyperplane of a set X ⊂ R d if H ∩ X = ∅ and X is contained in one of the two closed half-spaces of R d defined by H.

We denote by R ≥0 R := r∈R λ r r λ r ∈ R ≥0 the positive span of a set R of vectors of R d . A polyhedral cone is a subset of R d defined equivalently as the positive span of finitely many vectors or as the intersection of finitely many closed linear halfspaces. The faces of a cone C are the intersections of C with the supporting hyperplanes of C. The 1-dimensional (resp. codimension 1) faces of C are called rays (resp. facets) of C. A cone is simplicial if it is generated by a set of independent vectors.

A polyhedral fan is a collection F of polyhedral cones such that

• if C ∈ F and F is a face of C, then F ∈ F,
• the intersection of any two cones of F is a face of both. A fan is simplicial if all its cones are, and complete if the union of its cones covers the ambient space R d . For two fans F, G in R d , we say that F refines G (and that G coarsens F) if every cone of F is contained in a cone of G.

A polytope is a subset P of R d defined equivalently as the convex hull of finitely many points or as a bounded intersection of finitely many closed affine halfspaces. The dimension dim(P ) is the dimension of the affine hull of P . The faces of P are the intersections of P with its supporting hyperplanes. The dimension 0 (resp. dimension 1, resp. codimension 1) faces are called vertices (resp. edges, resp. facets) of P . A polytope is simple if its supporting hyperplanes are in general position, meaning that each vertex is incident to dim(P ) facets (or equivalently to dim(P ) edges).

The (outer) normal cone of a face F of P is the cone generated by the outer normal vectors of the facets of P containing F . In other words, it is the cone of vectors c such that the linear form x → c | x on P is maximized by all points of the face F . The (outer) normal fan of P is the collection of the (outer) normal cones of all its faces. We say that a complete polyhedral fan in R d is polytopal when it is the normal fan of a polytope of R d . A classical characterization of polytopality of complete simplicial fans can be obtained as a reformulation of regularity of triangulations of vector configurations, as introduced in the theory of secondary polytopes [GKZ08, Chap. 7], see also [START_REF] Loera | Triangulations: Structures for Algorithms and Applications[END_REF]Chap. 5]. Here, we present a reformulation of this characterization to deal with (not necessarily simplicial) fans that coarsen a complete simplicial fan. Proposition 3. Consider two fans F, G of R d , and let R ⊂ R d be a set of representative vectors for the rays of F. Assume that F is complete and simplicial, and that F refines G. Then the following assertions are equivalent:

(1) G is the normal fan of a polytope in R d .

(2) There exists a map h : R → R >0 with the property that for any r, r ∈ R and S ⊂ R for which

C := R ≥0 (S ∪ {r}) and C := R ≥0 (S ∪ {r }) are two adjacent maximal cones of F, if α r + α r + s∈S β s s = 0
is the unique (up to rescaling) linear dependence with α, α > 0 among {r, r } ∪ S then

α h(r) + α h(r ) + s∈S β s h(s) ≥ 0,
with equality if and only if the cones C and C are contained in the same cone of G. Under these conditions, G is the normal fan of the polytope defined by

x ∈ R d r | x ≤ h(r) for all r ∈ R .
Proof. The proof is similar to that of [CFZ02, Lem. 2.1], and we just adapt it here for the convenience of the reader. Assume first that G is the normal fan of a polytope P ⊆ R d and define h : R → R >0 by h(r

) := max { r | x | x ∈ P }. Consider r, r ∈ R and S ⊂ R such that the cones C := R ≥0 (S ∪ {r}
) and C := R ≥0 (S ∪ {r }) are two adjacent maximal cones of F. Let v and v be the vertices of P whose normal cones contain C and C respectively. Then by definition,

h(r) = r | v , h(r ) = r | v and h(s) = s | v = s | v for all s ∈ S.
Therefore, applying the linear form s → s | v to the linear dependance α r + α r + β s s = 0 among the vectors of S ∪ {r, r }, we obtain

α r | v + α r | v + β s s | v = 0. If C and C belong to the same cone of G, then v = v and h(r ) = r | v , thus we obtain the equality α h(r) + α h(r ) + β s h(s) = 0. Otherwise, we have h(r ) = r | v > r | v and since α > 0 we obtain the inequality α h(r) + α h(r ) + β s h(s) > 0.
Reciprocally, assume that there exists a height function h : R → R >0 such that Condition (2) is satisfied and consider the polytope

P := x ∈ R d r | x ≤ h(r) for all r ∈ R . For each max- imal cone C = R ≥0 S of F, let v C be the intersection of the hyperplanes x ∈ R d s | x = h(s) for s ∈ S. Let r, r ∈ R and S ⊂ R for which C := R ≥0 (S ∪ {r}) and C := R ≥0 (S ∪ {r }) are two adjacent maximal cones of F. Condition (2) implies that r | v C ≥ r | v C with
equality if and only if C and C are contained in the same cone of G. Therefore, for any vector c ∈ R d located on the side of r of the hyperplane spanned by S, we can write c as a linear combination c = γ r r + s∈S γ s s with γ r > 0, and we obtain that

c | v C = γ r r | v C + s∈S γ s s | v C ≥ γ r r | v C + s∈S γ s s | v C = c | v C ,
with equality if and only if C and C are contained in the same cone of G. Consider now a vector c ∈ R d and a maximal cone C of F. For dimension reason, there exists a line segment L joining c with some interior point of C and not passing through any cone of codimension two or more in

F. Let C 1 , C 2 , . . . , C k = C denote the cones of F along L (with c ∈ C 1 ). By the previous observation, we obtain c | v C1 ≥ c | v C2 ≥ • • • ≥ c | v C
, with equalities if and only if C i and C i+1 are contained in the same cone of G. Therefore, the linear form x → c | x on P is maximized by v C if and only if c belongs to the cone of G containing the cone C. We conclude that for any maximal cone C of F, the point v C is a vertex of P whose normal cone is the cone of G containing C, which shows that G is the normal fan of P .

Braid fan. We consider the braid arrangement H

n := {H ij | 1 ≤ i < j ≤ n} consisting of the hyperplanes of the form H ij := {x ∈ R n | x i = x j }. The closures of the connected components of R n
H n (together with all their faces) form a fan. This fan is complete and simplicial, but not essential (all its cones contain the line R1 1 := R(1, 1, . . . , 1)). We call braid fan, and denote by F n , the intersection of this fan with the hyperplane

H := x ∈ R n i∈[n]
x i = 0 . For example, we have represented in Figures 3 (left) and 1 (middle) the braid fan when n = 3 and n = 4 respectively. As the 3-dimensional fan F 4 is difficult to visualize in Figure 1 (middle), we also use another classical representation in Figure 4 (left): we intersect F 4 with a unit sphere and we stereographically project the resulting arrangement of great circles from the pole 4321 to the plane. Each circle then corresponds to a hyperplane x i = x j with i < j, separating a disk where x i < x j from an unbounded region where x i > x j .

The cones of the braid fan F n are naturally labeled by ordered partitions of [n]: an or- {3, 4} and {2, 3, 4}, see Figures 3 (left) and 4 (left). Two permutations σ, σ are said to be adjacent when their cones C(σ) and C(σ ) share a facet, or equivalently when σ and σ differ by the exchange of two consecutive positions.

dered partition π = π 1 |π 2 | . . . |π k of [n] into k parts corresponds to the (k -1)-dimensional cone C(π) := {x ∈ H | x u ≤ x v for all i ≤ j, u ∈ π i and v ∈ π j } . In particular, the fan F n has • a maximal cone C(σ) := x ∈ H x σ(1) ≤ x σ(2) ≤ • • • ≤ x σ(n) for each permutation σ ∈ S n , • a ray C(R) for each subset R of [n] distinct from ∅ and [n]. Namely, if R = {r 1 , . . . , r p } and [n] R = {s 1 , . . . , s n-p } then C(R) := x ∈ H x r1 = • • • = x rp ≤ x s1 = • • • = x sn-p . This is illustrated in Figures 3 (left
To understand the geometry of F n , we need to choose convenient representative vectors in H for the rays of F n . We denote by ∆ := {α 1 , . . . , α n-1 } the root basis (where α i := e i+1 -e i ) and by ∇ := {ω 1 , . . . , ω n-1 } the fundamental weight basis (i.e. the dual basis of the root basis ∆). A subset ∅ = R [n] corresponds to the ray r(R) of F n whose kth coordinate in the fundamental weight basis is 1 1 k∈R -1 1 k+1∈R (where 1 1 X = 1 if the property X holds and 0 otherwise). For example, the rays of the fundamental chamber are the rays r([k]) = ω k for 0 < k < n.

Lemma 4. Let σ, σ be two adjacent permutations. Let ∅ = R [n] (resp. ∅ = R

[n]) be such that r(R) (resp. r(R )) is the ray of C(σ) not in C(σ ) (resp. of C(σ ) not in C(σ)). Then the linear dependence among the rays of the cones C(σ) and C(σ ) is given by

r(R) + r(R ) = r(R ∩ R ) + r(R ∪ R )
where we set r(∅) = r([n]) = 0 by convention.

Proof. Since σ and σ are adjacent permutations of S n , there is i ∈

[n-1] such that σ(i) = σ (i + 1) and σ(i + 1) = σ (i) while σ( ) = σ ( ) for any / ∈ {i, i + 1}. Let R := σ([i]) and R := σ ([i]) and observe that R ∩ R = σ([i -1]) = σ ([i -1]) and R ∪ R = σ([i + 1]) = σ ([i + 1]). Since 1 1 k∈R +1 1 k∈R = 1 1 k∈R∩R +1 1 k∈R∪R for any k ∈ [n] and r(R) = k∈[n-1] (1 1 k∈R -1 1 k+1∈R )ω k , we obtain the linear dependence r(R) + r(R ) = r(R ∩ R ) + r(R ∪ R ), where we use the conven- tion r(∅) = 0 if R ∩R = ∅ and r([n]) = 0 if R ∪R = [n]. Moreover, we have r(R) ∈ C(σ) C(σ ) and r(R ) ∈ C(σ ) C(σ) while r(R ∩ R ) ∈ C(σ) ∩ C(σ ) and r(R ∪ R ) ∈ C(σ) ∩ C(σ ).
Therefore, we have identified the unique (up to rescaling) linear dependence of the rays of the cones C(σ) and C(σ ).

For example, the linear dependence among the rays in the adjacent cones C(123) and C(213) of F 3 is r({1}) + r({2}) = r({12}), while the linear dependence among the rays in the adjacent cones C(123) and C(132) of F 3 is r({1, 2}) + r({1, 3}) = r({1}). See Figure 3 (left). The first non-degenerate linear dependencies (i.e. where R ∩ R = ∅ and R ∪ R = [n]) arise in F 4 : for instance, the linear dependence among the rays in the adjacent cones C(4132) and C(4312) of F 4 is r({3, 4}) + r({1, 4}) = r({4}) + r({1, 3, 4}). See Figure 4 (left).

2.3. Shards. We now briefly present shards, a powerful tool to deal with lattice quotients of the weak order with a geometric perspective. Shards were introduced by N. Reading [START_REF] Reading | Lattice and order properties of the poset of regions in a hyperplane arrangement[END_REF], see also his recent survey chapters [START_REF] Reading | Lattice theory of the poset of regions[END_REF][START_REF] Reading | Finite Coxeter groups and the weak order[END_REF]. For any 1 ≤ i < j ≤ n, let [i, j] := {i, . . . , j} and ]i, j[ := {i + 1, . . . , j -1}. For any S ⊆ ]i, j[, the shard Σ(i, j, S) is the cone

Σ(i, j, S) := {x ∈ R n | x i = x j , x i ≥ x k for all k ∈ S, x i ≤ x k for all k ∈ ]i, j[ S} .
x 1 <x 2

x 3 <x 4

x 2 <x 3

x 1 >x 3 x 2 >x 4

x The hyperplane H ij is decomposed into the 2 j-i-1 shards Σ(i, j, S) for all subsets S ⊆ ]i, j[. The shards thus have to be thought of as pieces of the hyperplanes of the braid arrangement. Let

Σ n := {Σ(i, j, S) | 1 ≤ i < j ≤ n and S ⊆ ]i, j[}
denote the collection of all shards of the braid arrangement in R n .

We have illustrated the shard decomposition in Figures 3 (middle) and 4 (middle). In what follows, we use a convenient notation borrowed from N. Reading's work on arc diagrams [Rea15]: the shard Σ(i, j, S) is labeled by an arc joining the ith dot to the jth dot and passing above (resp. below) the kth dot when k ∈ S (resp. when k / ∈ S). For instance, the arc represents the shard Σ(1, 4, {2}).

Before going further, we state two technical lemmas connecting rays and shards.

Lemma 5. For any ∅ = R

[n], any 1 ≤ i < j ≤ n and any S ⊆ ]i, j[, the ray r(R) lies in the shard Σ(i, j, S) if and only if either {i, j} ⊆ R and

S ⊆ ]i, j[ ∩ R, or {i, j} ⊆ [n] R and ]i, j[ ∩ R ⊆ S.

Proof. Recall that

• the ray r(R) lies on the open half-line

x ∈ H x r1 = • • • = x rp < x s1 = • • • = x sn-p where R = {r 1 , . . . , r p } and [n] R = {s 1 , . . . , s p }, • Σ(i, j, S) := {x ∈ R n | x i = x j , x i ≥ x k for all k ∈ S, x i ≤ x k for all k ∈ ]i, j[ S}. If |{i, j} ∩ R| = 1, then r(R) i = r(R) j so that r(R) / ∈ Σ(i, j, S). Assume now that {i, j} ⊆ R. Then we have r(R) i = r(R) k for any k ∈ ]i, j[ ∩ R and r(R) i < r(R) k for any k ∈ ]i, j[ R. Therefore, r(R) ∈ Σ(i, j, S) if and only if S ⊆ ]i, j[ ∩ R. Assume finally that {i, j} ⊆ [n] R. Then we have r(R) i = r(R) k for any k ∈ ]i, j[ ∩ R and r(R) i > r(R) k for any k ∈ ]i, j[ ∩ R. Therefore, r(R) ∈ Σ(i, j, S) if and only if ]i, j[ ∩ R ⊆ S.
For example, the shard Σ(1, 3, ∅) contains the rays r({1, 3}), r({1, 2, 3}), r({1, 3, 4}) and r({4}). See Figure 4 (middle) where Σ(1, 3, ∅) is labeled by the arc .

Lemma 6. Let σ, σ be two adjacent permutations, let

∅ = R [n] (resp. ∅ = R [n]) be such that r(R) (resp. r(R )) is the ray of C(σ) not in C(σ ) (resp. of C(σ ) not in C(σ)),
R ∩ R ⊂ σ([ ]) so that r(σ([ ])) belongs to Σ(k, k , R ∩ R ∩ ]k, k [) by Lemma 5. For any < i, we have {k, k } ⊆ [n] σ([ ]) and σ([ ]) ⊆ R ∩ R so that r(σ([ ])) belongs to Σ(k, k , R ∩ R ∩ ]k, k [) by Lemma 5.
We conclude that all rays of the cone

C(σ) ∩ C(σ ) are in the shard Σ(k, k , R ∩ R ∩ ]k, k [),
and thus all the cone C(σ) ∩ C(σ ) is by convexity.

For example, the common facet of the cones C(4132) and C(4312) of F 4 is supported by the shard Σ(1, 3, ∅). See Figure 4 (middle) where Σ(1, 3, ∅) is labeled by the arc .

It turns out that the shards are precisely the pieces of the hyperplanes of H n needed to delimit the cones of the quotient fan F ≡ for any lattice congruence ≡ of the weak order on S n . Conversely, to understand which sets of shards can be used to define a quotient fan, we need the forcing order between shards. A shard Σ(i, j, S) is said to force a shard Σ(k, , T ) if k ≤ i < j ≤ and S = T ∩ ]i, j[. We denote this by Σ(i, j, S) Σ(k, , T ). For example, the forcing order on Σ 4 is represented on Figure 5 together with one of its upper ideals. All its upper ideals containing its three maximal elements are represented in Figure 6. The following statement uses shards to describe the lattice quotients of the weak order on S n .

Theorem 7 ([Rea16a, Sect. 10.5]). For any lattice congruence ≡ of the weak order on S n , there is a subset Σ ≡ of the shards of Σ n such that the interiors of the maximal cones of the fan F ≡ are precisely the connected components of H Σ ≡ . Moreover, Σ ≡ is an upper ideal of the forcing order ≺ and the map ≡ → Σ ≡ is a bijection between the lattice congruences of the weak order on S n and the upper ideals of the forcing order ≺.

For example, we have represented in Figures 3 (right) and4 (right) the quotient fans F ≡ sylv corresponding to the sylvester congruences ≡ sylv on S 3 and S 4 respectively. It is obtained

• either by glueing together the chambers C(σ) of the permutations in the same sylvester class. These classes are given in Figure 2 for n = 4. • or by cutting the space with the shards of Σ ≡ sylv . These shards are precisely the upper shards Σ(i, j, ]i, j[), whose arcs pass above all dots in between their endpoints. They form the ideal Σ ≡ sylv of Σ 4 represented in Figure 5 (right).

Remark 8. We have already mentioned that we represent a shard Σ(i, j, S) by the arc with endpoints i and j and passing above the vertices of S and below those of ]i, j[ S. Each region C of F ≡ then corresponds to a unique noncrossing arc diagram [START_REF] Reading | Noncrossing arc diagrams and canonical join representations[END_REF]: a collection of arcs that pairwise do not intersect or share a common left endpoint or a common right endpoint. Namely, the noncrossing arc diagram of a region C is given by the shards containing a down facet of C. This correspondence provides the canonical join representation of C. See [START_REF] Reading | Noncrossing arc diagrams and canonical join representations[END_REF] for precise definitions and details. We also refer to N. Reading's surveys [START_REF] Reading | Lattice theory of the poset of regions[END_REF][START_REF] Reading | Finite Coxeter groups and the weak order[END_REF] for further technology on the geometry of lattice quotients (see also Remark 13).

Figure 6. The lattice of (essential) lattice congruences of the weak order on S 4 . Each lattice congruence ≡ is represented by its upper ideal of shards Σ ≡ , and each shard Σ(i, j, S) is represented by an arc with endpoints i and j and passing above the vertices of S and below those of ]i, j[ S.

We only consider lattice congruences whose shards include all basic shards Σ(i, i + 1, ∅), since otherwise their fan is not essential.

Quotientopes

This section is devoted to the proof of Theorem 2. We say that a function f :

Σ n → R >0 is forcing dominant if f (Σ) > Σ ≺Σ f (Σ )
for any shard Σ ∈ Σ n . Such a function clearly exists, take for example f (Σ(i, j, S)) to be n -(j-i) 2 . For the remaining of the paper, we fix a forcing dominant function f . For a shard Σ = Σ(i, j, S) ∈ Σ n and a subset R ⊆ [n], we define the contribution γ(Σ, R) of Σ to R to be 1 if |R ∩ {i, j}| = 1 and S = R ∩ ]i, j[, and 0 otherwise. It is crucial to observe that the definition of γ(Σ, R) only depends on R ∩ [i, j]. Note also that γ(Σ, ∅) = γ(Σ, [n]) = 0 for every shard Σ ∈ Σ n . For a geometric interpretation of this definition, let H ij n denote the arrangement of the hyperplanes H ik and H kj for all k ∈ ]i, j[. Then Σ(i, j, S) contributes to a subset ∅ = R [n] if the ray r(R) lies in the (closed) region of H ij n containing Σ(i, j, S), but not on Σ(i, j, S). We consider a lattice congruence ≡ of the weak order on S n . For a subset R [n], we define the height h f ≡ (R) ∈ R >0 to be

h f ≡ (R) := Σ∈Σ≡ f (Σ) γ(Σ, R).
Note that h f ≡ (∅) = h f ≡ ([n]) = 0 by definition. This height function fulfills the following property.

Lemma 9. Let σ, σ be two adjacent permutations.

Let ∅ = R [n] (resp. ∅ = R [n]) be such that r(R) (resp. r(R )) is the ray of C(σ) not in C(σ ) (resp. of C(σ ) not in C(σ)). Then h f ≡ (R) + h f ≡ (R ) ≥ h f ≡ (R ∩ R ) + h f ≡ (R ∪ R
) with equality if and only if the common facet of C(σ) and C(σ ) belongs to a shard of Σ ≡ .

Proof. Let k, k be such that R {k} = R {k }. Assume without loss of generality that k < k . We consider a shard Σ = Σ(i, j, S) ∈ Σ ≡ and evaluate its contributions to R, R , R∩R and R∪R . Since γ(Σ, R) only depends on R ∩ [i, j], observe that

• if {k, k } ∩ [i, j] = ∅, then γ(Σ, R) = γ(Σ, R ) = γ(Σ, R ∩ R ) = γ(Σ, R ∪ R ); • if {k, k } ∩ [i, j] = {k}, then γ(Σ, R) = γ(Σ, R ∪ R ) and γ(Σ, R ) = γ(Σ, R ∩ R ); • if {k, k } ∩ [i, j] = {k }, then γ(Σ, R) = γ(Σ, R ∩ R ) and γ(Σ, R ) = γ(Σ, R ∪ R ). Note also that γ(Σ, R) = γ(Σ, R ) = γ(Σ, R ∩ R ) = γ(Σ, R ∪ R ) = 0 if S {k, k } = R ∩ R ∩ ]i, j[ by definition of the contributions. We conclude that γ(Σ, R) + γ(Σ, R ) = γ(Σ, R ∩ R ) + γ(Σ, R ∪ R ) for any shard Σ = Σ(i, j, S) for which {k, k } ⊆ [i, j] or S {k, k } = R ∩ R ∩ ]i, j[.
Therefore, we are left with the contributions of the shards Σ(i, j, S) such that {k, k } ⊆ [i, j] and S {k, k } = R ∩ R ∩ ]i, j[. By definition of the forcing order, all these remaining shards are forced by the shard Σ

• := Σ(k, k , R ∩ R ∩ ]k, k [).
Hence, we obtain that,

h f ≡ (R) + h f ≡ (R ) -h f ≡ (R ∩ R ) + h f ≡ (R ∪ R ) = h f ≡ (R) + h f ≡ (R ) -h f ≡ (R ∩ R ) + h f ≡ (R ∪ R ), where h f ≡ (R) := Σ∈Σ≡ Σ≺Σ• f (Σ) γ(Σ, R).
Finally, according to Lemma 6 and Theorem 7, Σ • is a shard of Σ ≡ if and only if the cones C(σ) and C(σ ) belong to distinct cones of F ≡ . We therefore distinguish two cases. (i) Assume first that C(σ) and C(σ ) belong to the same cone of F ≡ . Then Σ • is not in Σ ≡ . Since Σ ≡ is an upper ideal of the forcing order, it implies that Σ ≡ contains no shard Σ with Σ ≺ Σ • . Therefore (ii) Assume now that C(σ) and C(σ ) belong to distinct cones of

h f ≡ (R) = h f ≡ (R ) = h f ≡ (R ∩ R ) = h f ≡ (R ∪ R ) = 0 and we obtain h f ≡ (R) + h f ≡ (R ) = h f ≡ (R ∩ R ) + h f ≡ (R ∪ R ).
F ≡ . Then Σ • is in Σ ≡ . Since γ(Σ • , R) = γ(Σ • , R ) = 1, this implies that h f ≡ (R) ≥ f (Σ • ) and h f ≡ (R ) ≥ f (Σ • ). Moreover, since γ(Σ • , R ∩ R ) = γ(Σ • , R ∪ R ) = 0, we have h f ≡ (R ∩ R ) ≤ Σ≺Σ• f (Σ ) and h f ≡ (R ∪ R ) ≤ Σ≺Σ• f (Σ ). We conclude that h f ≡ (R) + h f ≡ (R ) -h f ≡ (R ∩ R ) -h f ≡ (R ∪ R ) ≥ 2 f (Σ • ) -2 Σ≺Σ• f (Σ) > 0.
since f is forcing dominant. This concludes the proof.

We finally obtain the proof of Theorem 2.

Corollary 10. For any lattice congruence ≡ of the weak order on S n , and any forcing dominant function f : Σ n → R >0 , the quotient fan F ≡ is the normal fan of the polytope

P f ≡ := x ∈ R n r(R) | x ≤ h f ≡ (R) for all ∅ = R [n] .
In particular, the graph of P f ≡ oriented in the linear direction α := (-n + 1, -n + 3, . . . , n -3, n -1) is the Hasse diagram of the quotient of the weak order by ≡.

Proof. We just combine the polytopality criterion of Proposition 3 with the statements of Lemmas 4 and 9, to obtain the polytopality of the quotient fan F ≡ . The end of the statement then follows from Theorem 1.

Note that the inequality description of Corollary 10 is in general redundant. More precisely, the inequalities corresponding to the rays of F n that are not rays of F ≡ are irrelevant.

We call quotientope the resulting polytope P f ≡ . See Figures 7,8 and 9 for illustrations. Note that not all quotientopes are simple since not all quotient fans are simplicial.

Remark 11 (Forcing dominance). Note that the forcing dominance condition could even be weakened to depend on the lattice congruence ≡. More precisely, the construction and the proof of Lemma 9 and thus of Corollary 10 still work for any function f :

Σ n → R >0 such that for any shard Σ ∈ Σ ≡ , f (Σ) > Σ ∈Σ≡ Σ ≺Σ f (Σ ).
Remark 12 (Insidahedra, outsidahedra and removahedra). By definition, the quotientopes are generalized permutahedra [START_REF] Postnikov | Permutohedra, associahedra, and beyond[END_REF][START_REF] Postnikov | Faces of generalized permutohedra[END_REF] as their normal fans coarsen the braid fan. This means in particular that they are obtained by gliding inequalities of the permutahedron orthogonally to their normal vectors. Note that in our construction, the inequalities are glided inside the permutahedron. More precisely, if F ≡ refines F ≡ , then P f ≡ contains P f ≡ . For example, the cube (quotientope of the coarsest congruence so that F ≡ is essential) is contained in all quotientopes such that F ≡ is essential, while the permutahedron (quotientope of the finest congruence) contains all quotientopes. See Figure 9 for illustration. This construction thus contrasts with the classical Figure 8. All 3-dimensional quotientopes up to symmetries. There are 47 (essential) lattice congruences on S 4 represented in Figure 6, but only 20 up to horizontal and vertical symmetry. Each lattice congruence ≡ is represented by its upper ideal of shards Σ ≡ , and each shard Σ(i, j, S) is represented by an arc with endpoints i and j and passing above the vertices of S and below those of ]i, j[ S.

Figure 9. The quotientope lattice for n = 4: all quotientopes ordered by inclusion (which corresponds to refinement of the lattice congruences). We only consider lattice congruences whose shards include all basic shards Σ(i, i + 1, ∅), since otherwise their fan is not essential. construction of the associahedron [START_REF] Loday | Realization of the Stasheff polytope[END_REF] and its generalizations [HL07, LP18, Pil13, PP18], which are all obtained by gliding inequalities outside the permutahedron. More precisely, the classical associahedron is obtained by removing certain inequalities from the facet description of the classical permutahedron. Note that the similar construction does not work in general: for example, the fan F ≡ of the top right congruence of Figure 8 is not realized by the intersection of the half-spaces defining facets of the classical permutahedron normal to the rays of F ≡ .

Remark 13 (Towards quotientopes for arbitrary hyperplane arrangements?). As already mentioned, Theorem 1 actually holds in much more generality (see [START_REF] Reading | Lattice theory of the poset of regions[END_REF] for a detailed survey). Consider a central hyperplane arrangement H defining a fan F, and let B be a distinguished chamber of F. For any chamber C of F, define its inversion set to be the set of hyperplanes of H that separate B from C. The poset of regions Pos(H, B) is the poset whose elements are the chambers of F ordered by inclusion of inversion sets. A. Björner, P. Edelman and G. Ziegler discuss in [START_REF] Björner | Hyperplane arrangements with a lattice of regions[END_REF] some conditions for this poset of regions to be a lattice: Pos(H, B) is always a lattice when the fan F is simplicial, and the chamber B must be a simplicial for Pos(H, B) to be a lattice. In [START_REF] Reading | Lattice congruences, fans and Hopf algebras[END_REF], N. Reading proves that when Pos(H, B) is a lattice, any lattice congruence ≡ of Pos(H, B) defines a complete fan F ≡ obtained by glueing together the cones of the fan F that belong to the same congruence class of ≡. The polytopality of this quotient fan F ≡ however remains open in general. Although the polytopality criterion of Proposition 3 seems a promising tool to tackle this problem when F is simplicial, the general case seems much more intricate. Let us observe that we benefited from three specific features of the Coxeter arrangement of type A:

• we used the simpliciality of the arrangement,

• we used the action of S n to transport our understanding of the linear dependencies from the initial chamber to any other chamber, • these linear dependencies are very simple in type A (only 3 or 4 terms and 0/1 coefficients). These properties hold for any finite Coxeter group (for the last property though, the linear dependencies can get up to 5 terms, and some coefficients equal to 2 appear in non-simply-laced types). This suggests that the strategy of this paper could produce polytopal realizations when the hyperplane arrangement is the Coxeter arrangement of a finite Coxeter group.

Figure 1 .

 1 Figure 1. The Hasse diagram of the weak order on S 4 (left) can be seen as the dual graph of braid fan (middle) or as an orientation of the graph of the permutahedron Perm(4) (right).

Figure 3 .

 3 Figure3. The braid fan F 3 (left), the corresponding shards (middle), and the quotient fan given by the sylvester congruence ≡ sylv (right).

Figure 4 .

 4 Figure 4. A stereographic projection of the braid fan F 4 (left) from the pole 4321, the corresponding shards (middle), and the quotient fan given by the sylvester congruence ≡ sylv (right).

Figure 5 .

 5 Figure5. The forcing order on Σ 4 (left) and its upper ideal consisting of up arcs corresponding to the sylvester congruence ≡ sylv (right).

Figure 7 .

 7 Figure 7. Permutahedron (left), associahedron (middle) and cube (right) as quotientopes.

Acknowledgements

We thank N. Reading for comments on a preliminary version of this paper and an anonymous referee for many relevant suggestions that greatly improved the presentation.


Anatole Chessel
email: achessel@ifremer.fr

Ronan Fablet
email: rfablet@ifremer.fr

Frederic Cao
email: fcao@irisa.fr

Charles Kervrann
email: ckervran@irisa.fr

ORIENTATION INTERPOLATION AND APPLICATIONS

Psychovision have shown that many grouping laws come into play to structure human vision. They use informations of different kinds, not only gray (or color)-level values. Here we will show how an orientation interpolation operator working in S 1 (angle in [0, 2π[) can be used to recover geometrical information in images. The operator is presented and is used to produce fields that drive a Fast Marching contour extraction algorithm and a LIC-based smoothing method. Experiment on real images are reported to validate the proposed approach.

INTRODUCTION

The human vision is known for its ability to use global and heterogeneous visual cues. Psychovisual experiments, in particular from the Gestaltists [START_REF] Kaniza | La grammaire du voir[END_REF] indeed show that our vision is structured by a number of grouping laws using different kind of features: contrast change but also direction, spatial proximity, global shape prior or specific structuring pattern like T-junction and X-junction.

One important grouping law among those is the good continuation principle, which states that if two edgels (edge element, i.e. a point together with the orientation of the curve which should pass through it) are not too far apart and share compatible directions, we tend to see the curve to which they are both tangent as an edge. A lot of work has been done towards a digital implementation of that phenomenon [START_REF] Parent | Trace inference, curvature consistency, and curve detection[END_REF][START_REF] Zweck | Euclidian group invariant computation of stochastic completion fields using shiftable-twistable basis function[END_REF]. They rely on extracting edges as curves, contrary to pointwise extraction algorithm like the Canny-Deriche filter [START_REF] Deriche | Using canny's criteria to derive a recursively implemented optimal edge detector[END_REF]. To this end, data of different nature needs to be integrated. In particular, to cope with curves one need the orientation (an element of S 1 = {v ∈ R 2 / |v| = 1}, the unit circle of R 2 ) of the tangent to that curve. It is with this idea in mind that this work investigates orientation-driven image processing.

In [START_REF] Chessel | Orientation interpolation : an axiomatic approach[END_REF] is presented an axiomatic approach for orientation interpolation in which two operators are singled out: the curvature and the Absolutely Minimizing Lipschitz Extension (AMLE). The second one is well known in scalar computer vision [START_REF] Caselles | An axiomatic approach to image interpolation[END_REF] and will allow us here to compute smooth and dense orientation fields that follow the extracted orientation information. We show here how those fields, which capture the geometrical features of the image, can be taken advantage of for orientation driven image processing, namely contour extraction and selective smoothing.

Section 2 briefly presents the AMLE operator for angle data. Application to the extraction of subjective contour via minimal path implemented by Fast Marching is presented in section 3 and selective smoothing of image presenting strong geometrical properties via Line Integral Convolution is described in section 4.

EXTENSION OPERATOR ON ANGLE

Extracting Relevant Points

The first step is to extract a sparse edgel field from the image. The direction of the geometrical structure that passes through a point is given by the vector orthogonal to the gradient, possibly smoothed. Numerous edge point extraction algorithms exist. In the experiments presented here we used the Canny-Deriche filter [START_REF] Deriche | Using canny's criteria to derive a recursively implemented optimal edge detector[END_REF], thresholded so as to keep only the strongest edges.

Axiomatic of Orientation Interpolation

In [START_REF] Chessel | Orientation interpolation : an axiomatic approach[END_REF] an axiomatic approach similar to [START_REF] Caselles | An axiomatic approach to image interpolation[END_REF] was developed to find sound interpolation operator by laying out the properties it should follow. It leads to the Absolutely Minimizing Lipschitz Extension (AMLE), a well studied operator for which existence and unicity results are known. ( [START_REF] Caselles | An axiomatic approach to image interpolation[END_REF] and reference therein). In particular it satisfies a maximality principle which guarantee that the solution is oscillation free.

Let Ω ⊂ R 2 . Let S 1 be parametrized by angles in [0, 2π[. Let D ⊂ Ω be a set of curves and/or points and θ 0 :

D → S 1 . Then θ : Ω → S 1 is the AMLE of θ 0 in Ω if: D 2 θ(Dθ, Dθ) = 0 in Ω, θ| D = θ 0 on D, (1)
i.e. if the second derivative in the direction of the gradient is null. The mathematical theory only hold if the data θ 0 is not surjective, i.e. if it take value in S 1 minus one point. If it is not the case, singularities are bound to which the operator, looking for Lipschitz solutions, cannot handle. The AMLE is a laminar flow orientation operator, not a turbulent flow one. In practice we are interested in geometric structures, which give rise to regular orientation field. Thus this necessary condition will be locally fulfilled. This equation has been implemented using the associated evolution problem combined to a finite difference scheme. Due to the specificity of angular data and the iterative nature of such a scheme, a multiresolution procedure was used to initialise the numerical resolution [START_REF] Chessel | Orientation interpolation : an axiomatic approach[END_REF]. Typical computational time is about a minute for 512x512 images on Pentium IV 2.5Ghz, and the interpolation process is parameter-less .

In Figure 1(a) the computed field is shown for the Lena image. The extracted points are in black, and the field obtained by extending their associated orientations is visualised via its flow line using LIC [START_REF] Cabral | Imaging vector field using line integral convolution[END_REF]. It follows when possible the geometry of the image. As stated, for topological reason, singularities are unavoidable. Thus in absence of clear constraints or if they conflict with each other, chaotic zones akin to turbulence flows are created.

EXTRACTING CURVES FROM ORIENTATION FIELD AS GEODESICS

We now are provided with a smooth orientation field θ, extending some extracted data. Let us assume that those initial orientations extracted in section 2.1 can be considered as edgels, i.e. they are tangent to an edge; it is the case in the experiments shown in Fig. 1(a) as they originate from a Canny-Deriche filter. The dense orientation field θ is then expected to be tangent to the full edge which the initial edgels are part of.

The edges could then be extracted as the integral curves Γ x of θ, defined as ∂Γx(λ) ∂λ = u, Γ x (0) = x, with u = (cos θ, sin θ) and λ an euclidean parametrisation of Γ x .

Unfortunately, in practice orientation field θ does not follows exactly the edges, and will only be close to being tangent to the edges. Thus the curves of interest cannot be extracted as integral lines, but we just know they will be close to being integral lines. Hence given two points we aim at determining the line as tangent as possible to θ that join them. This leads to formulating the problem of extracting edges as the computation of geodesics. Such a formulation is well known in the computer vision field [START_REF] Caselles | Geodesic active contours[END_REF][START_REF] Laurent | Minimal paths and fast marching methods for image analysis[END_REF].

Using minimal path formulation [START_REF] Laurent | Minimal paths and fast marching methods for image analysis[END_REF], given two point M 0 and M 1 and vector field u the extraction of the looked after curve Γ M0,M1 is stated as minimizing a given metric F (u, Γ).

Let us set E F (u,Γ) (M 0 , M 1 ) = M1 M0 F (u, Γ). The curve Γ M0,M1 is defined by Γ M0,M1 = arg min Γ∈C(M0,M1) E F (u, Γ) (M 0 , M 1 ), (2)
with C(M 0 , M 1 ) the set of continuous curves from M 0 to M 1 .

To solve for it, we compute

E M0 (x) = min Γ∈C(M0,x) E F (u, Γ) (M 0 , x), x ∈ Ω. E M0 (x)
is a convex function whose only minimum is in M 0 , thus it leads to Γ M0,M1 by a simple gradient descent on E M0 from M 1 to M 0 .

To actually compute E M0 , the Fast Marching algorithm [START_REF] Sethian | Level Set Methods and Fast Marching Methods[END_REF] is used. It is based on a front propagation of equation

∂C ∂t (C(λ, t)) = 1 F (u, Γ M0,C(λ,t) ) n(C(λ, t)), (3)
with C the front, initially an infinitesimal circle around M 0 , λ an euclidean parametrization of C and n the outward normal to the front. E M0 (x) is then defined as the arrival time of the front at each point. Thus at any given time, minimal paths have been computed from M 0 to all the points already visited by the front at that time, they can then be used to further propagate it.

The proposed function F is

F (u, Γ)(y) =< ∂Γ(λ) ∂λ (y), u ⊥ (y) > 2 ,
with λ an Euclidean parametrisation of Γ, u ⊥ the orthogonal of u and < ., . > the usual scalar product of R 2 . It is by definition nul if u is tangent to Γ and maximum if it is orthogonal.

A similar problem was stated in [START_REF] Parker | Estimating distributed anatomical connectivity using fast-marching methods and tensor diffusion imaging[END_REF] but the authors proposed a function F that did not depend on the curve but on the propagating front C at the time of it's crossing. This however led to non intrinsic curves which depended on the front propagation process itself. This appears as an undesirable property. This function F can be considered the only parameter for the edge extraction.

In Figures 1(a) and 1(b), the results for real images are displayed. On the Lena image (Fig. 1(a)), using the field computed in section 2, we have recovered the top of the hat and the left jaw, which both were not contrasted enough to be extracted by our point-wise thresholded edge extraction filter. This is a typical case of modal completion, also called illusory contour, where the background and the edge have in part the same color. The Figure 1(b) shows two examples of images with low contrast: in both cases the presence of a structure is clearly recognized while continuous contours or edges are either very faint or not actually present. Thus the use of orientation informations allow us to tackle problem on which method purely based on image intensity would encounter difficulties.

SMOOTHING ALONG ORIENTATION

In [START_REF] Tschumperlé | LIC-based regularization of multi-valued images[END_REF] is described an anisotropic smoothing algorithm based on the Line Integral Convolution (LIC) of Cabral and Leedom [START_REF] Cabral | Imaging vector field using line integral convolution[END_REF]. Given an image I 0 and a vector field u, if Γ x is the integral line of u going through x with λ an euclidean parametrization of Γ x , the unidimensional heat equation constrained the integral curves of u,

∀x ∈ Ω ∂I(Γ x (λ)) ∂λ (x) = ∂ 2 I(Γ x (λ)) ∂λ 2 (x), (4)
is equivalent to a trace based differential operator on the full image. As it is well known that heat equation is equivalent to a Gaussian convolution, ( 4) is in turn equivalent to

∀x ∈ Ω I(t)(x) = +∞ -∞ I 0 (Γ x (λ))G t (λ)dλ, (5)
with G t the Gauss function of standard deviation

√ t: G t (x) = 1 √ 4πt exp(-x 2 4t
). This is the continuous formulation of the LIC visualization algorithm [START_REF] Cabral | Imaging vector field using line integral convolution[END_REF], which is used to visualize the vector field in Fig. 1

(a) (left image).

The main issue is that no vector field u is straightforwardly available for a given image. Beside, the extraction of such a field is in the general case not obvious, as images do not necessarily have everywhere strong oriented geometrical features. In [START_REF] Tschumperlé | LIC-based regularization of multi-valued images[END_REF], the local geometrical information of the image was captured into a diffusion tensor based on the structure tensor [START_REF] Weickert | Anisotropic Diffusion in Image Processing[END_REF] which was decomposed into vectors to apply the described LIC-based regularisation.

We have described above a method to compute dense orientation fields as the extension of extracted geometrical structures. While in the general case it would be relevant only on edges (see Sec. 3), in some particular cases it might be an accurate description of the whole image. Images displayed in Fig. 1(c) are accurately described by a set of linear or curvilinear parallel lines. For such images the AMLE orientation field can then be used to implement the LIC-based regularization defined by Eq. 5.

More precisely, for a given image, we proceed as follows. Relevant points are extracted by a thresholded Canny-Deriche filter and the corresponding orientation is computed as the orthogonal to the gradient. The AMLE operator is then applied to obtain a dense orientation field which follows the geometrical features of the image. A Gaussian smoothing constrained to the integral lines as per equation 5 is then applied. Once the initial point are extracted (see section 2.1 ), the only parameter is the smoothing strength, which is the length of the Gaussian kernel, or equivalently the length on the integral curve.

The image in the left part of figure 1(c) is a patch of sand. This is a natural image with no artificial noise, and the geometry of the image underlying it's grainy natural aspect is reccovered. On the right is a wood texture image with Gaussian noise of standard deviation 20 added. It exhibits vertical cracks, which were captured in the computed orientation field. As illustrated, the orientation based filtering leads to an efficient restoration. Thus, when strong geometrical structures are available, the use of such orientation fields is an elegant and intuitive alternative to the diffusion tensor [START_REF] Tschumperlé | LIC-based regularization of multi-valued images[END_REF].

CONCLUSION

Thanks to the AMLE interpolation operator we were able, given a sparse edgel field, to build a dense orientation field having good mathematical properties in its laminar part. If the edgels represent geometrical data from an image, we showed that this field is a way of recovering geometrical informations. It can be used to extract subjective contours, thus supplying information where the contrast information is low, and smooth strongly geometrical images while fully retaining their structures. While those algorithm are almost parameter-less, they are obviously very dependent on the edgels originally extracted. While the method used here of thresholded Canny-Deriche filter is efficient, more sophisticated method might be investigated, for example by using adaptative multiscale thresholding method or orientation based point-wise extraction algorithm.

In the presented algorithms only the orientation is taken into account. It worked well to take advantage of the geometry of the image in an orientation plane, but both methods could benefit from a coupling with intensity or contrast based information, to extend them to a larger class of image.

Fig. 1 .

 1 Fig. 1.


Frédéric Cao
email: fcao@irisa.fr

Ronan Fablet
email: rfablet@ifremer.fr

Automatic morphological detection of otolith nucleus

This paper deals with the automation of the acquisition of age and growth data from the analysis of otolith images.

One of the key component of such a system is the automatic detection of the growth center, which serves as the basis for further processing (2D ring segmentation, age and growth estimation,...). To this end, we develop a new and well-founded approach combining a morphological analysis of image level sets to the a contrario detection principle.

This approach leads to a robust parameterless scheme, whose efficiency is demonstrated by an evaluation carried out for a set of several hundred of plaice otoliths.

Problem statement

Age and growth data from fish otoliths are key information for a broad range of issues in fisheries science: for instance, the determination of age-length keys from the interpretation of fish otoliths for marine stock assessments [START_REF] Panfili | Manual of Fish Sclerochronology[END_REF] or the analysis of fish otolith growth patterns for marine ecology [START_REF] Hare | Effect of age, growth rate, and ontogeny on the otolith size -fish size relationship in bluefish, pomatomus saltatrix, and the implications for back-calculation of size in fish early life history stages[END_REF][START_REF] Panfili | Manual of Fish Sclerochronology[END_REF]. These applications require large collections of age and growth data to carry out a consistent analysis. The acquisition of age and growth information is routinely performed by experts from the interpretation of concentric growth rings observed on fish otoliths as illustrated by Fig. 1 for a plaice otolith. Typically, several thousands of fish otoliths per year, species and stock are routinely interpreted by experts for marine stock assessment issues. Worldwide, it is currently estimated that several millions of otoliths are routinely interpreted each year for fisheries management issues. Given the associated interpretation cost, automation and quality assurance are major issues and digital imaging systems are of key interest through the creation of bases of otolith images. Hence, the development of computer-aided or automated tools for the interpretation of otolith images [START_REF] Small | Computer-assisted age and growth pattern recognition of fish scales using a digitizing tablet[END_REF][START_REF] Guay | Morphing technology applied to digital tree ring density measurement[END_REF][START_REF] Morison | An integrated system for production fish aging: image analysis and quality insurance[END_REF]. The automatic determination of the otolith growth center is of key importance both for ageing automation and computer-assisted otolith interpretation since it serves as the reference point for further analysis (automated extraction of interpretation axis, 2D ring segmentation, age and growth estimation,...). However, previous work targeted at otolith imaging [START_REF] Fablet | Robust time-frequency model estimation in otolith images for fish age and growth analysis[END_REF][START_REF] Guillaud | Autonomous agents for edge detection and continuity perception on otolith images[END_REF][START_REF] Robertson | Development of an artificial neural network for automated age estimation[END_REF][START_REF] Traodec | Use of deformable templates for otolith 2D growth ring detection by digital image processing[END_REF][START_REF] Welleman | Automatic ageing of Plaice otoliths by means of image analysis[END_REF] has mainly focused on ring detection and segmentation issues, generally assuming that the otolith nucleus (also referred as the otolith center in the subsequent) is known. The detection of otolith nucleus has only been considered in [START_REF] Guillaud | Autonomous agents for edge detection and continuity perception on otolith images[END_REF][START_REF] Welleman | Automatic ageing of Plaice otoliths by means of image analysis[END_REF]. The solution proposed in [START_REF] Welleman | Automatic ageing of Plaice otoliths by means of image analysis[END_REF], which simply resorts to the detection of the darkest point within a predefined area of interest set a priori, is not robust. In [START_REF] Guillaud | Autonomous agents for edge detection and continuity perception on otolith images[END_REF], the detection of the otolith center is a byproduct of the extraction of 2D growth rings. Though interesting, it involves an overcomplex parametrization of the underlying multi-agent system, which needs to be tuned appropriately. Conversely, in this paper, we design a robust and parameterless detection of otolith nucleus relying on a well-founded combination of morphological features to the a contrario decision. The presentation and the evaluation of this new approach is organized as follows. Section 2 details the proposed morphological approach. Experiments, including a quantitative evaluation including a comparison to previously proposed approaches [START_REF] Guillaud | Autonomous agents for edge detection and continuity perception on otolith images[END_REF][START_REF] Welleman | Automatic ageing of Plaice otoliths by means of image analysis[END_REF] for a large set of plaice otoliths, are presented in Section 3.

Morphological nucleus detection

Topographic map

In the following, we shall use the topographic map as a complete, contrast invariant representation of a grey level image. We briefly recall the main ingredients of this representation in this section.

Let u be a grey level image. Its upper (resp. lower) level set at value [START_REF] Matheron | Random Sets and Integral Geometry[END_REF][START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF] that these level sets give a complete representation of u. Indeed, the two following reconstruction formulae hold:

λ is χ λ (u) = {x ∈ R 2 , u(x) ≥ λ} (resp. χ λ (u) = {x ∈ R 2 , u(x) ≤ λ}). It is a classical result of Mathematical Morphology
u(x) = sup{λ, x ∈ χ λ (u)} = inf{λ, x ∈ χ λ (u)}. (1)
Moreover, this representation is invariant with respect to global contrast change. Indeed, if v = g(u) where g is an increasing continuous function, then u and v have the same family of level sets (obviously differently indexed).

Conversely, if two images have the same family of level sets, then they differ by a monotone contrast change (possibly not continuous). Level lines are the topological boundaries of connected components of level sets, and the topographic map is the collection of all level lines. The topographic map also characterizes the image, up to an increasing contrast change. Since level sets are nested, they can be embedded in a tree structure, computed by an efficient algorithm due to Monasse and Guichard [START_REF] Monasse | Fast computation of a contrast invariant representation[END_REF]. They call shape the interior of any level line. There are superior (resp. inferior) shapes, following whether they are obtained from an upper (resp. lower) level set. The denomination of shapes is due to the fact that they often correspond to shapes or part of shapes in real images [START_REF] Caselles | Topographic maps and local contrast changes in natural images[END_REF]. This is consistent with the accepted fact that edges are normal to the gradient, and so locally follow level lines. For a smooth image, (say of class C 1 ), in the neighborhood of a point where the gradient is not equal to zero, a level line coïncide with an isophote (a line on which the grey level is constant). As a consequence, all level lines are everywhere parallel to edges, implying that edges are included in pieces of level lines. Now, contrary to edge points as given by Canny's detector [START_REF] Canny | A computational approach to edge detection[END_REF], level lines are curves, and no connecting procedure is needed to retrieve curves.

Nucleus detection

Let us first remark that the otolith itself can be easily extracted as the largest shape in the image, that we shall denote by S 0 . This is not very strict an hypothesis, since the acquisition of otolith images is well controlled, and the otolith is usually observed as it lies on a nearly constant background. Moreover, a few level lines still contain the greatest part of visual information. This can be easily checked (for instance) by quantizing the grey level at some few values. In about 99% of the cases we observed, the nucleus delimited by at least one level line. Other level lines give the position of growth rings, but they may be cut into a few parts. In fact, this is always the case in plaice otoliths, which exhibit a "blind part" containing nearly no structure. In order to detect the nucleus, we propose to select the best shape with respect to a few criteria.

Let us state the following qualitative facts: otoliths are vaguely elliptic, and nucleui correspond to a dark region close to the longest principal axis of the otolith. This region is also basically elliptic and no too excentric. From these qualitative description, we have to make quantitative arguments.

We proceed as follows: we start by removing shapes that definitely cannot be nucleus (it was checked on 100%

of the observed images). We then introduce features measuring the previous qualitative properties. This will allow us to define a functional, and we will keep the shape that minimizes this functional. But contrarily to usual variational methods, this functional will have a quantitative meaning. It will tell how likely a shape will satisfy our geometric criteria only by chance. We will then see that it is possible to fix a robust automatic threshold to validate the detection.

Besides, we will detail in section 3.2 a refinement of the proposed approach based on a priori information on nucleus position. The proposed approach is summarized in Fig. 2.

Maxima removal

Let us first express the fact that the nucleus corresponds to a dark region. Let E 0 be the shapes included in S 0 (that is, part of the otolith). We also denote by E 1 the set of shapes in E 0 that do not contain any superior shape. In other terms, shapes in E 1 do not contain any local maxima. Of course, this is a bit strict, since noise creates lots of them.

Thus, we first apply a grain filter [START_REF] Monasse | Morphological Representation of Digital Images and Application to Registration[END_REF][START_REF] Vincent | Grayscale area openings and closings, their efficient implementation and applications[END_REF] to the image, which consists in removing shapes whose area is less than a given threshold. This scale parameter is the unique parameter of our method. Its value is not sensitive since the size of the nucleus is always of few hundreds pixels. The size of the grain filter was set to the same value 400 for all our experiments. Grain filter and maxima elimination leave of few dozens candidate shapes.

Principal axis proximity

Let us now denote by ∆ the first principal axis of the otolith. Let D be a perpendicular axis to ∆, and (X i ) i∈I be a finite family of connected compact sets. Let X be one of the X i . We say that X has a minimal distance to ∆ on D if

N F A(S) f 1 (S) f 4 (S) f 2 (S) f 3 (S)
Otolith extraction

S a

Grain filter with area a S closest to principal axis

S = argmin X N F A(X)
S does not contain local minima

Position distribution

d(D ∩ ∆, D ∩ X) = min i∈I d(D ∩ ∆, D ∩ X i ). (2)
In (2), we measure the distance between the point (D ∩ ∆) and the set (D ∩ X i ). This condition simply means that if we restrict the observation on D, then X is the closest to ∆ among the x i .

Finally, we say that S ∈ E if S ∈ E 1 and if for any axis D, perpendicular to ∆ such that S ∩ D = ∅, then there exists S ∈ E 1 such that S has a minimal distance to ∆ on D among the shapes of E 1 and S ⊂ S .

The interpretation is much simpler that this formal geometrical definition: basically, if we start from ∆ and move along its normal, then the first dark shape that we encounter must contain S.

While the first step remove bright shapes, this second one removes elongated shapes that turn around the nucleus. (See

Fig. 3.) ∆ S 0
Figure 3: Proximity to principal axis. The black-filled shape is in E since in any direction orthogonal to ∆, it is contained in the shape which is the closest to ∆ (the white one). For the same reason, the white shape belongs to E. On the contrary, one can find a normal to ∆ such that the grey-filled shape is not the closest to ∆ (since the white one is closer). Thus it does not belong to E.

Geometrical statistical selection

The two preceding steps are only qualitative, and avoid any threshold. They are also quite general and experimentally very stable. We now aim at:

1. finding the best nucleus candidate.

2. giving a reliability measure to this detection.

is the area:

f 1 (S) = |S|. (3)
The second one is:

f 2 (S) = |S| max x∈S d(x, ∆) 2 . ( 4
)
This function is scale invariant and measure how S is close to ∆, relatively to its size.

Let us now denote by D(S, ∆ ⊥ ) the diameter of the projection of S on the orthogonal direction to ∆. We define

f 3 (S) = |S| D(S, ∆ ⊥ ) 2 .
(

) 5
This value is also dimensionless, and describes the "flatness" of S with respect to the direction ∆. Let us remark that a good nucleus candidate will simultaneously yield large values of the f i , in the case our geometrical qualitative assumptions hold. However, fixing thresholds for the f i may be a numerically sensitive. To avoid this, let us make the a contrario hypothesis that the f i are statistically independent. This assumption is reasonable for any shape except the nucleus. Indeed, the size, the proximity to the axis and the flatness of the nucleus have a common cause, which is that the otolith grows in any direction from the nucleus. In classical hypothesis testing, this amounts to test the hypothesis H 0 defined by "the f i are independent" against an alternative hypothesis H 1 that they are not. The likelihood of H 1

is not easy to compute, and requires a "good" model of otolith. In what follows, the decision will only be based on the null hypothesis H 0 . A natural way to detect this independence violation is as follows: let us fix some values λ i and compute, under the independence assumption, the expected number of shapes assuming values of the f i larger than λ i . Whenever this value is lower than 1 and a shape S satisfies f i (S) ≥ λ i , then chance alone cannot explain the observation. This is related to the Helmholtz principle, introduced by Desolneux, Moisan and Morel [START_REF] Desolneux | A grouping principle and four applications[END_REF]. The ideal situation would be to find a set of statistically independent features that give a complete description of what a nucleus should be. Since we are not capable to find such a precise model, we only keep three features, whose independence is plausible in a set or random shapes. For i = 1, 2, 3, let us define H i the empirical inverse repartition function of f i :

H i (µ) = #{S ∈ E, f i (S) > µ} #{S ∈ E} . ( 6
)
where # denotes the cardinality.

Definition 1 Let S ∈ E and

E 1 (S) = max i=1,2,3 H i (f i (S)) 3 . ( 7
)
We define the nucleus N as the shape in E such that

E 1 (N ) = min S∈E E 1 (S). (8)
Remark that E 1 is nothing but the empirical probability to observe the event "for all i', f i ≥ f i (S)", under the a contrario independence hypothesis. Thus, this definition means that the best candidate is the less probable under the independence assumption. In practice, we learn the histogram on a set of about 100 shapes, yielding positive marginals greater than 10 -2 . In practice, the minimizer of E in our experiments assumes a value between 10 -4 and 10 -5 . Remark that contrarily to Bayesian method where we look for the most probable candidate given a model, we detect the less probable candidate with respect to an a contrario independence assumption. Now, how can we assert that a probability is actually small? Otherwise said, can we find a natural threshold on the likelihood under the independence assumption? Let us first define number of false alarms.

Definition 2 We call number of false alarms (NFA) of S the number

N F A(S) = #E • E 1 (S). (9)
We also say that S is ε-meaningful if N F A(S) < ε.

The additivity of expectation immediately gives the following result (see [START_REF] Desolneux | A grouping principle and four applications[END_REF]).

Proposition 1

The expectation of the number of ε-meaningful shapes in the independence model is smaller than ε.

Proof. Let X S the binary variable equal to 1 if S is ε-meaningful and 0 else. The expected number of ε-meaningful shapes is nothing but E ( S X S ), where E denotes the expectation. By linearity,

E S X S = S∈E E(X S ). (10)
But E(X S ) is the probability that S is meaningful. Let Y i = f i (S). The a contrario assumption is that the Y i are independent, and their inverse repartition function is H i . Then

P (X S = 1) = P max i H i (Y i ) 3 < ε #E = P ∀i, H i (Y i ) < ε #E 1/3 = 3 i=1 P H i (Y i ) < ε #E 1/3 by independence ≤ ε #E .
The last inequality follows P (H i (Y i ) < t) ≤ t, because H i is the inverse repartition function of Y i . Thus, the expectation in Eq.10 is a sum of #E terms, all less than ε #E . Hence, it is less than ε. As a consequence, let us choose ε < 1 and assume that we observe that a shape has a NFA less than ε. We know that, in average, there is less than one such a shape under the a contrario hypothesis. We conclude that the independence is certainly false and detect the shape as meaningful. Since in practice, we obtain NFA of magnitude 10 -2 , this means that we can expect 1% false alarms, which is coherent with the empirical results.

Experimental results and refinement of the proposed approach

Results

We first display two examples of the detection of the nucleus within otolith images for plaice samples. Fig. 4 reports these two detections, respectively for a 3 years and a 10 years old otolith. The red line outlines the shape selected by our morphological approach, the blue star the estimated position of the nucleus and the magenta circle its actual position manually pointed out. The second row zooms in around the otolith center. In both cases, the selected shape is actually located within the first translucent ring. Consequently, an accurate estimation of the position of the otolith center is deduced. An important feature stresses by these two examples is the robustness of the morphological detection to the increase in image complexity in terms of the number of concentric seasonal rings.

We have carried out an evaluation of the proposed technique on a set of 250 images of plaice otoliths from age groups 1 to 13. For each image, the position of the nucleus as well as the position of the first translucent ring have been manually pointed out by the expert to provide the ground truth. To achieve a quantitative analysis of the detection performance, we define the rate of correct detection w.r.t. the threshold value α as follows. Let is denote by D the -distance between the detected nucleus and the actual one. Rather than straightforwardly setting a threshold on D, we prefer accounting for the variations of the width of the first translucent ring. This will lead to a more relevant accuracy measure. Hence, the detection of the otolith center is considered as correct w.r.t. α if distance D is lower than α times the distance from the actual nucleus center to the first translucent ring. In average, the first translucent ring is about 100 pixels wide. Setting α to 0.3 then roughly comes to retain only the detections for which the distance to the actual position is below 30 pixels. Besides, for α = 1, it indicates whether or not the estimated position of the nucleus is within the first translucent ring. In actual applications such as computer-aided acquisition of bases of interpreted otolith images or ring segmentation for automated ageing [START_REF] Fablet | Automated fish age estimation from otolith images using statistical learning[END_REF][START_REF] Traodec | Use of deformable templates for otolith 2D growth ring detection by digital image processing[END_REF], a detection accuracy α below 0.3 is satisfactory. In the subsequent, this value will then be used as the reference value. Fig. 5 reports the results obtained using criterion [START_REF] Hare | Effect of age, growth rate, and ontogeny on the otolith size -fish size relationship in bluefish, pomatomus saltatrix, and the implications for back-calculation of size in fish early life history stages[END_REF]. We obtain good results with an overall detection rate of 95.1% for a threshold value α of 0.3.

Detection refinement

The use of criterion E 1 (N ) (cf. Eq. 8), defined from purely geometrical features, leads to 2% misdetections outside of the first growth ring as illustrated by Fig. 7. For these samples, candidate areas corresponding to the nucleus however appear within the three best E 1 (S) scores. As detailed below, these results can be improved by a two-pass scheme. In order to improve the detection performances, additional information on the location of the nucleus can be exploited to refine its detection. This information is provided by the result of the method described above, and not by the user.

Otoliths are known to generally grow asymmetrically. As an illustration, Fig. 6 displays the distribution of the nucleus detections issued from our morphological detection. Note that, in general, the horizontal orientation of the otolith is unknown, i.e. we cannot distinguish the right from the left. We arbitrarily decide that the otolith is oriented such that the detected nucleus is at the right of the otolith center. The observed distribution is clearly unimodal and conveys relevant information to refine the nucleus detection. For instance, regarding this global distribution, some points appear as outliers likely to correspond to false detections.

We then perform a second pass as follows. Given the detections issued from criterion (8), we compute the median location of the extracted regions. This median position is exploited as an a priori prediction within our a contrario framework. It resorts to the introduction of feature within the geometrical statistical selection. This feature evaluates the distance between the center of the candidate region and the predicted position and is defined as follows:

f 4 (S) = -C S -P ( 11
)
where P is the predicted nucleus position and C S the center of the candidate zone S. Given that, in general, the horizontal orientation of the otolith is unknown, f 4 (S) is computed as:

f 4 (S) = -min ( C S -P L , C S -P R ) (12)
where P L and P R are respectively the predicted position of the nucleus towards the left and the right in the frame of the principal axis of the otolith. For this second pass, similarly to Eq. 8, we define the nucleus N as the shape S such that:

E 2 (N ) = min S∈E E 2 (S) with E 2 (S) = max i=1,3,4 H i (f i (S)) 3 . ( 13
)
Let us stress that the considered criterion is not (max i=1,2,3,4 H i (f i (S))) 4 . As a matter of fact, the a contrario principle relies on the detection of independence violations for the considered features, whereas f 2 (S) and f 4 (S) are obviously dependent. On the contrary, for a random set of shapes, the independence between f 1 (S), f 3 (S) and f 4 (S) is a sound assumption, which permits to apply the a contrario detection. Fig. 7 illustrates the gain brought by the proposed refinement. The use of criterion [START_REF] Panfili | Manual of Fish Sclerochronology[END_REF] further constrains the nucleus detection with some information on the position of the nucleus region to extract correct detections. These results are confirmed by the evaluation of the detection performance for the dataset of 250 plaice otolith images. We report in Fig. 8 the comparison of the one-pass and two-pass schemes. For a threshold value of 0.3, the detection performances increase from 95.1% to 98.0%. Besides, there are only 0.7% of false detections outside the first growth ring compared to 2.0% with the one-pass algorithm. We also report in Fig. 8 the histogram of the distances between the actual nucleus position and the estimated one, reported for the two-pass scheme: the mean distance equals 11.8 pixels (versus 15 pixels for the one-pass scheme) and 98.1% (versus 95% for the one-pass scheme) for the one-pass scheme of the detections are associated to a distance below 30 pixels. The results stress the improvement brought by the proposed refinement in terms of detection accuracy and demonstrate that we reach a satisfactory accuracy for actual applications. To further illustrate the practicability of the proposed approach, we report in Fig. 9 a subset of the analyzed images with the associated detections.

Comparison to previous work

In order to stress the efficiency of our morphological approach, we have carried out an experimental comparison in detection accuracy w.r.t. previous ones proposed in [START_REF] Guillaud | Autonomous agents for edge detection and continuity perception on otolith images[END_REF] and [START_REF] Welleman | Automatic ageing of Plaice otoliths by means of image analysis[END_REF]. Fig. 10 depicts the overall evaluation. Compared to previously proposed approaches, the morphological scheme largely outperforms the heuristic one used in [START_REF] Welleman | Automatic ageing of Plaice otoliths by means of image analysis[END_REF], which simply consists in retrieving the darkest point within a predefined window, and the multi-agent technique proposed in [START_REF] Guillaud | Autonomous agents for edge detection and continuity perception on otolith images[END_REF] (respectively, 98.1% 84% and 84% of correct detection for α = 0.3). Whereas multi-agent systems are known to involve quite complex parameterization, the proposed morphological method can be regarded as parameterless. It only requires to set the parameter value of the grain filter, used to filter out small regions. In our experiments, this value was set to 400 and the detection performances were shown to remain stable for a grain parameter within [100, 600].

Conclusion

We have developed a morphological approach for the detection of the nucleus region in otolith images. The reported evaluation and the comparison to previous work demonstrate the relevance of the chosen parameterless framework combining topographic representation of otolith images to an a contrario detection. In future work, we will further investigate this methodology to define robust and parameterless tools for extraction of geometrical structures in particular for the images of biological tissues depicting growth rings such as otoliths, tree trunks, coral sections, sea shells,..... Besides, the proposed method provides us with a key component to develop a fully automated system for the acquisition of age and growth data from otolith images. the multi-agent technique introduced in [START_REF] Guillaud | Autonomous agents for edge detection and continuity perception on otolith images[END_REF] (blue -line) and the scheme used in [START_REF] Welleman | Automatic ageing of Plaice otoliths by means of image analysis[END_REF] (cyan -. line). in terms of difference between the true and predicted positions of the otolith center. Markers + refer to the results supplied by the scheme used in [START_REF] Welleman | Automatic ageing of Plaice otoliths by means of image analysis[END_REF], while the detections performed by our approach are displayed by markers o. The three methods need a CPU time about 1s per image.

Figure 1 :

 1 Figure 1: Illustration of plaice otolith interpretation for a 4 year old individual : image of the plaice otolith acquired under a binocular with transmitted light. The interpretation of the winter translucent rings is displayed by the markers set on the radial drawn on the main reading axis.

Figure 2 :

 2 Figure 2: Diagram of the nucleus detection algorithm. The first step is the otolith extraction. Local extrema are filteredout by a grain filter with area parameter a. Shapes that contain local maxima or that are not the closest to the principal axis cannot be the nucleus. (This is only heuristic, but was satisfied for nearly all the images of the database.) Then three features f 1 , f 2 , f 3 allow to compute the NFA (Number of False Alarm). The best candidate is the one with the lowest NFA. In dashed lines, an optional loop: the position of the detections for a large database can be learned. It permits to propose a refinement of the proposed method using a feature f 4 which is more accurate than f 2 , and leads to another NFA which experimentally gives better result.

Figure 4 :

 4 Figure 4: Two examples of the detection of otolith center using our morphological approach: the line superimposed to the image depicts the contour of the selected shape, marker • (black) the estimated position of the otolith center, and marker * (white) its true position. The first row displays the image of the whole otolith, while the second row zooms in to the region close to the otolith center.

Figure 5 :

 5 Figure 5: Detection performance on a set of 250 Plaice otolith images. We evaluate the rate of correct detection for a range of values of the threshold α (see text for details) using criterion (8).

Figure 6 :

 6 Figure 6: Distribution of the positions of the regions selected using criterion (8) for the processed dataset of right sagittae otoliths of plaice. The positions are computed in the frame of the principal axis of the otoliths, normalized w.r.t. the lengths of the otolith in these two directions, such that the selected region is at the right of the otolith center.

Figure 7 :

 7 Figure 7: Refinement of the detection of the nucleus: the first row displays examples of misdetections using criterion (8) based on geometrical and photometric features; the second row reports the results obtained for same otoliths by the two-pass scheme using additional information on nucleus position. The shape N selected as the nucleus shape (cf. Eq.8 is superimposed to the image as a gray region. Besides, marker * (white) refers to the actual nucleus position, whereas marker • (black) refers to the estimated one.

Figure 8 :

 8 Figure 8: Detection performance on a set of 250 Plaice otolith images. The left plot displays the rates of correct detections for a range of values of the threshold α (see text for details) using the method proposed in this paper with (solid line) or without (dashed line) the use of a priori information on the nucleus position. The right plot depicts the histogram of the distances between the actual nucleus position and the estimated one for the two-pass scheme.

Figure 9 :

 9 Figure 9: Illustration of the practicability of the two-pass scheme approach for a subset of the base of 250 otolith images. Marker * (white) refers to the actual nucleus position, whereas marker • (black) refers to the detected one.

Figure 10 :

 10 Figure 10: Detection performance on a set of 250 Plaice otolith images. We evaluate the rate of correct detection for a range of values of the threshold α (see text for details) for three techniques: the morphological approach presented in this paper (red line),