{'fraction_non_alphanumeric': 0.04725132225022948, 'fraction_numerical': 0.006410910203546399, 'mean_word_length': 4.044021459542883, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Generalized Morphology using Sponges

Abstract Mathematical morphology has traditionally been grounded in lattice theory. For non-scalar data lattices often prove too restrictive, however. In this paper we present a more general alternative, sponges, that still allows useful definitions of various properties and concepts from morphological theory. It turns out that some of the existing work on “pseudo-morphology” for non-scalar data can in fact be considered “proper” mathematical morphology in this new framework, while other work cannot, and that this correlates with how useful/intuitive some of the resulting operators are.


Introduction
Lattice theory has brought mathematical morphology very far when it comes to processing binary and greyscale images. However, for vector-and tensor-valued images lattice theory appears to be overly restrictive [7,15,32,43]: vectors and tensors simply do not seem to naturally t a lattice structure. For example, we cannot have a lattice that is compatible with a vector space structure while also behaving in a rotationally invariant manner [32]. And having a lattice that can deal with periodic structures is equally impossible (due to it being based on an order relation).
Some attempts have been made to still apply mathematical morphology to vector-and tensor-valued images by letting go of the lattice structure while still having something resembling the in mum and supremum operations [2,4,5,9,10,13,14,27,48]. However, over the years, mathematical morphology has developed a host of concepts that (in their usual formulation) rely on a lattice structure. Take away the lattice structure and all these concepts make very little sense any more. For example, a dilation is de ned as an operator that commutes with the supremum of the lattice. And some pseudo-morphological operators can indeed lead to unintuitive (and undesired) behaviour [31].
Recently, we introduced a novel theoretical framework which generalizes lattices [33], while retaining some crucial properties of in ma and suprema. This more exible structure, which we call a "sponge", is inspired by the vector levelings of Zanoguera and Meyer [48] and the tensor dilations/erosions by Burgeth et al. [9,12,14], and is e ectively a variant of what is known as a "weakly associative lattice" or "trellis" [24,25,44]. We also show that sponges are closely related to preorders (also known as reduced orderings or R-orderings).
In this paper, the relation between sponges and lattices, and the earlier generalizations, are discussed and examples are shown of existing and new methods that are not interpretable in a traditional lattice theoretic framework, but that do lead to sponges. The method proposed by Burgeth et al. [9], on the other hand, is shown not to lead to a sponge (which can be linked to the issue we raised earlier [31,Fig. 5]). We hope this new framework will be useful in guiding future developments in non-scalar morphology, and that it will provide more insight into the properties of operators based on such schemes. 1. A partial order in which every pair of elements has a unique greatest lower bound (in mum) and a unique least upper bound (supremum). 2. A set with two (binary) operators called meet (denoted by '∧') and join ('∨') such that the operators are commutative and associative, and satisfy the absorption property: the join of an element with the meet of that same element with any (other) element is always equal to that rst element (the dual statement should also hold).
It is well-known that these de nitions are equivalent. Also, it can be shown that one can always extend the join and meet to nite sets. A lattice is complete if one can determine the join and meet of every subset of the lattice (including the empty set and the entire lattice). A conditionally complete lattice is one in which the join (meet) can be determined of every non-empty subset that has a common upper (lower) bound. A commonly used type of a lattice is a so-called function lattice Fun(E, L) [36,Ex. 2.10], where L is a lattice, and E some set. Such a lattice contains all functions whose domain is E and whose range is L. The join and meet are computed point-wise: for all f , g ∈ Fun(E, L) and x ∈ E Given an operator ψ on a lattice L, we say this operator is anti-extensive if ψ(a) ≤ a for all a ∈ L, extensive if a ≤ ψ(a) for all a ∈ L, idempotent if ψ(ψ(a)) = ψ(a) for all a ∈ L, and increasing if a ≤ b =⇒ ψ(a) ≤ ψ(b) for all a, b ∈ L.
The rst three are readily generalized to sponges, the last one will prove to be more problematic. An operator (on a lattice) is called an erosion if it commutes with taking the meet (ψ(a ∧ b) = ψ(a) ∧ ψ(b)), a dilation if it commutes with taking the join (ψ(a ∨ b) = ψ(a) ∨ ψ(b)), an opening if it is anti-extensive, idempotent, and increasing, and a closing if it is extensive, idempotent, and increasing.
Bereitgestellt von | University of Groningen Angemeldet Heruntergeladen am | 06.11.17 16:15 An important class of erosions (dilations) is formed by the so-called structural erosions (dilations). Such operators are de ned on function lattices, for which the domain E has some sort of neighbourhood structure; they compute the minimum (maximum) within the neighbourhood for each point in the domain E. For every erosion there is a complementary dilation [36, §3.2], such that rst applying the erosion and then the dilation constitutes an opening (and the converse process a closing).

Related work
If we step away from lattices, what options do we have? Some attempts at developing speci c methods that still behave much like a traditional lattice include non-separable vector levelings by Zanoguera and Meyer [48], morphology for hyperbolic-valued images by Angulo and Velasco-Forero [4,5], and the Loewner-order based operations by Burgeth et al. [9]. All these methods support the concepts of upper and lower bounds, as well as some sort of join and meet (in mum and supremum), but do not rely on a lattice structure. The framework presented in this work will be shown to encompass some of these methods, but not all.
Below we will present a generalization of a partial order that will be called an oriented set, as a starting point for our generalization of a lattice. An oriented set is so named because it can also be considered an oriented graph¹ and vice versa. Also, if all elements in some subset of an oriented set are comparable, this subset can be called a tournament (analogous to a chain). This structure was already used, under di erent names, as the basis for a subtly di erent generalization of a lattice: a weakly associative lattice (WAL), trellis, or T-lattice [24,25,44].
Based on oriented sets we will introduce a generalization of a lattice called a sponge, which supports (partial) join and meet operations on sets of elements. A sponge is a lattice if the orientation is transitive and the join and meet are de ned for all pairs (as a consequence of being a lattice they must then also be de ned for all nite sets). If the latter condition does not hold the result would still be a partially ordered set with a join and meet de ned for all nite subsets that have an upper/lower bound (which is a bit more speci c than the concept of a partial lattice used by [29,Def. 12]). On the other hand, a weakly associative lattice [24,25,44] is de ned in almost the exact same way as a sponge. The di erence is that a weakly associative lattice requires the join and meet of every pair of elements to be de ned, while not guaranteeing that the existence of an upper/lower bound implies the existence of the join/meet of a ( nite) set of elements [23]. The concept of a partial weakly associative lattice seems to be no more powerful than that of an oriented set [26, Imagine a variant of a sponge where the join and meet only need to be de ned for all pairs (rather than all nite sets) with upper/lower bounds. If (against our better judgement, since the concept is more general than a sponge) we call such structures 2-sponges, then (as captured in Fig. 1 and proven in Appendix A) -WALs, sponges and partially ordered sets generalize lattices, -there are WALs that are not sponges (and vice versa), -a WAL that is also a partial order is a lattice (and thus also a sponge), -a partially ordered set that is also a 2-sponge is a sponge, -there are partially ordered sets that are not 2-sponges (and vice versa), -2-sponges are strictly more general than both WALs and sponges, -oriented sets are strictly more general than 2-sponges and partial orders.
Since many morphological operators and concepts are based on joins and meets of sets, sponges provide a much more natural framework for generalized morphology than WALs. Also, WALs require the join and meet to be de ned for all pairs of elements, and all our examples violate this property. Partial WALs on the other hand provide too few guarantees to really be useful. As a consequence, we believe sponges are the right choice in the current context.

Sponges
We will rst give two (equivalent) de nitions of what a sponge is. Roughly speaking, sponges are lattices that let go of transitivity, or, equivalently, the associativity of the join and meet.

. Sponges as oriented sets
We de ne a (partially) oriented set³ to be a set with a binary relation ' ' -a (partial) orientation⁴ -that is both re exive and antisymmetric. An orientation that is also transitive is thus a partial order. If an orientation is total, the set is said to be totally oriented and is called a tournament. We also write A B for subsets A and B of S if and only if [∀a ∈ A, b ∈ B : a b]. We sometimes omit braces around explicitly enumerated sets to be able to write a b, c instead of {a} {b, c}. Also, for reasons of simplicity, we will say that a is less than or equal to b (or a lower bound of b) if a b, even though the relation need not be a (partial) order.
We now de ne a sponge as an oriented set in which there exists a supremum/in mum for every nonempty and nite subset of S which has at least one common upper/lower bound. Here a supremum a of a subset P of S is de ned as an element in S such that P {a} and a b for all b such that P {b}; the in mum is de ned analogously. Note that antisymmetry guarantees that if a supremum/in mum exists, it is unique.⁵

. Algebraic de nition of sponges
Analogous to the algebraic de nition of a lattice, we now de ne a sponge as a set S with partial functions J (join) and M (meet) de ned on non-empty nite subsets of the set S, satisfying the properties (with a, b ∈ S and P a non-empty nite subset of S) 3 Fried [23] called an oriented set a partial tournament. 4 Rachůnek [42] called an orientation a semi-order, while Skala [44] and Fried and Grätzer [26] called it a pseudo-order. 5 In fact, Fried [23] already showed that in any orientation the set of "least upper bounds" of a set is either empty or a set of just one element.
Bereitgestellt von | University of Groningen Angemeldet Heruntergeladen am | 06.11.17 16:15 idempotence: M({a}) = a, absorption: if M(P) is de ned, then ∀a ∈ P : J({a, M(P)}) = a , part preservation: ∀a ∈ P : M({a, b}) = b =⇒ M({M(P), b}) = b, and the same properties with J substituted for M and vice versa. Since J and M are operators on (sub)sets, they preserve the commutativity of lattice-based joins and meets, but not necessarily their associativity. In a lattice L, idempotence follows from absorption: a ∧ a = a ∧ (a ∨ (a ∧ b)) = a for all a, b ∈ L. In a sponge, on the other hand, the join and meet need not be de ned for all pairs of elements in the sponge, and this argument breaks down (but we still need it, so it is included as a separate property). Part preservation⁶ is essentially "half" of associativity, in the sense that if the implication was replaced by a logical equivalence, J and M would be associative. In some cases we wish to write down M(P) or J(P) without worrying about whether or not it is actually de ned for the set P. We then consider M or J to return a special value when the result is unde ned. This value propagates much like a NaN: if it is part of the input of M or J, then the output takes on this "unde ned" value as well.
It is important to note that if a ( nite) subset P of a sponge has a common lower (upper) bound b, the premise of part preservation is true, and P must then have a meet (join), or the left-hand side of the conclusion would be unde ned.
From now on, we will omit braces around explicitly enumerated sets whenever this need not lead to any confusion (as this greatly enhances readability). So we will write M(a, b) and P a rather than M({a, b}) and P {a}.

. Equivalence of de nitions
We now proceed to show that both de nitions above are, in fact, equivalent. For example, part preservation can be interpreted as: b P implies b M(P).

Theorem 1.
An oriented set-based sponge gives rise to an algebraic sponge, in which the partial functions J and M recover precisely the suprema and in ma in the oriented set.
Proof. Since the supremum is unique whenever it is de ned, we can construct a partial function J that gives the supremum of a ( nite) set of elements; we construct M analogously. Due to re exivity the resulting J and M must be idempotent. Part preservation also follows, as by de nition any upper bound of a set of elements is an upper bound of the supremum of those elements (note that by de nition, if there is an upper bound, there must also be a supremum). To see that our candidate sponge also satis es the absorption laws, suppose that the set P has a common lower bound, so its in mum inf(P) is de ned. By de nition, a a as well as inf(P) a for any a ∈ P.
Since the two elements share an upper bound (a), the supremum of a and inf(P) must be de ned. Again by de nition, we must have that a sup(a, inf(P)), but also that sup(a, inf(P)) a (since a is an upper bound for all of the arguments). Due to the antisymmetry of the orientation sup(a, inf(P)) must thus equal a. Since the same can be done in the dual situation, the J and M induced by ' ' must give rise to an algebraic sponge, in which J and M recover the suprema and in ma in the oriented set. Since M is idempotent, the induced relation ' ' must be re exive. Also, as M is a (partial) function, a b and a ≠ b together imply b ̸ a (a function cannot take on two values at the same time). In other words: the relation ' ' is antisymmetric, and we can thus conclude that ' ' is an orientation.
We will now show that every nite set with a common upper (lower) bound (according to ' ') has a supremum (in mum) if and only if J (M) is de ned for that set, and that if it exists, the supremum (in mum) is given by J (M). Due to the absorption and part preservation properties, the join provides every nite set that has a common upper bound with a supremum. Thus, the relation ' ' induced by J and/or M is a sponge. Furthermore, we cannot have any nite subsets for which J (M) is not de ned but a supremum (in mum) does exist, as J and M must be de ned for all nite subsets with a common upper/lower bound (due to the part preservation property). This concludes our proof. We can also conclude that a ∈ L(b) and b ∈ L(a) together imply a = b.

. Lower/upper bounds and preorders
Suppose that we have a sponge S such that the transitive closure of the corresponding orientation is a partial order relation '≤' (that is, antisymmetry is preserved). Clearly, we have a b ⇒ a ≤ b and a ≺ b ⇒ a < b. Now consider equivalence classes of elements, based on Here '↔' is used to denote the "if and only if" relation used within a statement, as opposed to ' ⇐⇒ ', which is used to denote the logical equivalence of two statements. In other words, two elements are in the same equivalence class if they are incomparable and from the point of view of all other elements they are the same in terms of the partial order '≤'. Note that it can be seen that the transitive closure of a sponge's orientation preserves antisymmetry if and only if the sponge is acyclic (that is, there are no cycles in the orientation other than self-loops). Denoting the equivalence class containing a as [a], we de ne Note that this is perfectly consistent, since any two elements in an equivalence class are indistinguishable in their comparisons to elements outside the equivalence class. Instead of de ning a partial order on equivalence classes, we can consider a preorder on the elements of the sponge. We will call this preorder the preorder induced by the orientation of the sponge (or orientation preorder), and denote it by '≤ * ': We can conclude that a b ⇒ a ≤ * b, and thus that M(a, b) ≤ * a, b. In fact, Corollary 1 shows that in any sponge, the meet and join can be de ned in terms of sets of lower/upper bounds and the induced preorder. Proof. Given any a ∈ S and b ∈ L(a) di erent from a, we note that b < a must hold (due to b ≺ a), and as a consequence they cannot be in the same equivalence class. This then leads us to conclude that [b] must be strictly smaller than [a], and by extension b < * a. This concludes the proof.

Corollary 1. Given an acyclic sponge S and two elements a and b in S, M(a, b) (when de ned) is the unique maximum in L(a) ∩ L(b) with respect to the preorder induced by the orientation of the sponge.
Proof. If M(a, b) is de ned, it is located in the (non-empty) intersection of L(a) and L(b), and its set of lower bounds is a superset of this intersection. Given Proposition 1 we can clearly conclude that M(a, b) is the unique maximum in L(a) ∩ L(b) with respect to the preorder.
There are two reasons the above is relevant. The rst is that the orientation preorder turns out to be fairly intuitive for two of the examples given below (it boils down to a preorder on radius or height). The second is that preorders are well-understood compared to sponges, and might aid in proving certain convergence properties. In particular, if one has a sequence of anti-extensive operators, their composition might not be anti-extensive from the point of view of the orientation relation, but it will be anti-extensive from the point of view of the preorder.

. Tournaments and the reduction operator
Chains are totally ordered sets [8, p. 2], and typically subsets of some lattice or partial order. These are of particular interest in the study of (hyper)connectivity [47]. Since we are ultimately interested in developing a similar theory for sponges, we will now show some potentially useful properties of totally oriented sets: tournaments. Finite tournaments by themselves were studied in some detail by Harary and Moser [35]. We start by replicating one of their results (part of Corollary 5a) in the current (more general) context.

Proposition 2. An acyclic tournament is a chain.
Proof. First note that a tournament is a total orientation, so it is re exive, antisymmetric, and total. Now, if a b and b c, with a, b, and c elements of the tournament, then we must have a c. This is because a and c must be comparable, and c a would create a cycle. This means the tournament is a re exive, antisymmetric, transitive, and total relation: a total order or chain.
We now proceed to show some statements where maximality plays a role. It is important to note that some care should be taken in applying Proposition 3 to tournaments that are part of a larger orientation or sponge. The statement shows that the maximal element (if it exists), is a supremum in the tournament, not necessarily in the larger orientation or sponge. In the lattice context this type of issue is often addressed by considering sublattices: sets of elements closed for joins/meets (in the original lattice). In fact, it should be clear that if the tournament is a "subsponge", then the supremum in the tournament coincides with the supremum in the sponge.

Proposition 3. A tournament never has more than one maximal (minimal) element, and if it has a maximal (minimal) element it is the supremum (in mum) of the tournament.
Proof. We will prove the statement for maximal elements, the minimal case can be shown analogously. Assume that a tournament has more than one maximal element. Then there are two (distinct) elements that are not less than any other elements (including each other). However, this cannot be, since in a tournament any two elements must be comparable, so one of the elements must be less than the other (note that due to antisymmetry they cannot be equal in the relation). There can thus be at most one maximal element. If there is a maximal element, it must be an upper bound for all of the elements in the tournament. Furthermore, there cannot be any other element (in the tournament) that is an upper bound for all of the elements in the tournament, so it is indeed a supremum. This concludes the proof.
We now proceed to give a generalization of (a particular formulation of) a "Hausdor 's Maximal Principle" [8,§VIII.7]. The original principle tells us that any chain contained in a partially ordered set can be extended to a maximal chain. We will use "totally oriented subset" to denote a tournament whose elements are a subset Bereitgestellt von | University of Groningen Angemeldet Heruntergeladen am | 06.11.17 16:15 of a (larger) orientation, in which the relation is given by the larger orientation. In the proof we will assume the original principle holds (it is equivalent to the axiom of choice [8, §VIII.14]).

Proposition 4 (Hausdor 's Maximal Principle for orientations). Every totally oriented subset T of an orientation O is contained in a maximal (in the sense of set inclusion) totally oriented subset M.
Proof. Consider the set A = {R | T ⊆ R ⊆ O and R totally oriented} of totally oriented subsets of O that contain T. This set is partially ordered by set inclusion. As such, because of the original Hausdor 's maximal principle, it must contain a maximal chain P of totally oriented subsets. If we take M = P, then clearly M contains T. Also, M can be seen to be totally oriented. In addition, it must be maximal, since if there was a larger subset of O that was totally oriented, it would have been in A, and by extension P. This concludes the proof.
A subset A of a sponge S is tournament-sup complete (A ∈ P tsc (S)) if and only if J(T) ∈ A for every non-empty tournament T ⊆ A for which J(T) exists. Although this not completely analogous to the usual de nition of chain-sup completeness (which requires that the join of any non-empty chain in A exists and is in A), the current formulation makes some of our analysis easier (or at least a lot less verbose), and the di erence is relatively benign, as it disappears whenever the sponge (or lattice) is complete, which is the usual setting. We now get the following result.

Proposition 5. A maximal totally oriented subset of a tournament-sup complete subset of a sponge contains its supremum, if it exists (in the sponge).
Proof. If the supremum of a totally oriented subset exists, adding it to this totally oriented subset gives another (larger) totally oriented subset. Hence, if we have a maximal totally oriented subset of a tournament-sup complete subset of sponge, then its supremum must be in the tournament-sup complete subset, and as a result in the maximal totally oriented subset. This concludes the proof.
We are now in a position to introduce the concept of non-redundancy and the so-called reduction operator used by Wilkinson [47] in the context of (hyper)connected openings. In sponges it turns out this is useful even for other types of openings.

De nition 1 (Non-redundancy). Any subset A of a sponge S is said to be non-redundant if
Equivalently (using Proposition 4), A is non-redundant if all maximal totally oriented subsets contained in A have cardinality one. The set of all non-redundant subsets of S is denoted by N(S).
De nition 2 (Re nement relation). The re nement relation (re exive, not antisymmetric or transitive) on P(S) for some sponge S is denoted by ' ' and is de ned by De nition 3 (Reduction operator). The reduction operator ψ N : Note that in a complete lattice, one also has J(A) = J(ψ N (A)) if A is chain-sup complete. In a sponge, the analogous statement need not be true, but there do appear to be situations in which it does hold. For example, Theorem 7 can be seen to imply something to this e ect for the set Q used in the proof. Similarly, although in general we cannot assume that A ψ N (A) holds (even for tournament-sup complete A), Theorem 8 shows that there are non-trivial sets for which it does hold. It remains to be seen whether these results are related and what properties of sponges and sets are relevant. Also, it may be possible to de ne alternative notions of non-redundancy and/or alternative reduction operators.

Proposition 6. In a conditionally complete sponge, the set of lower bounds L(a) is tournament-sup complete for any a in the sponge.
Proof. Suppose we have a tournament T contained in L(a), this tournament has a common upper bound (a), so it must have a supremum J(T). Due to part preservation, the join of T must be a lower bound of a. This concludes the proof. Proposition 7. The intersection of two tournament-sup complete subsets of a sponge is tournament-sup complete.
Proof. Suppose the statement is not true. We then have two tournament-sup complete subsets A and B of a sponge, such that there is a totally oriented subset of A ∩ B which does not have a supremum in A ∩ B. However, this tournament is clearly also contained in A and B, so its supremum (according to the original sponge) must be in both A and B, meaning that it is also contained in A ∩ B, proving the statement.

. Further properties
The property shown to hold in sponges in Proposition 8, is related to associativity in the sense that if a sponge is associative, the inequality would become an equality. The property itself could be interesting in the context of semisponges (discussed below), but it is also of interest when we would like to compute the meet of a set based on taking many meets of smaller sets. In particular it can be used to show that we would not overshoot our goal. In a sponge the join of a nite set exists if (and only if) there is a common upper bound of that set. Like with lattices, a conditionally complete sponge guarantees that this is true for all non-empty sets ( nite or otherwise) that have at least one common upper bound, and similarly for the meet. A complete sponge would be a sponge for which all sets are guaranteed to have a join and a meet. All of the examples given in Section 5 are conditionally complete, and most of them have a smallest element (so all non-empty meets exist). We expect conditionally complete sponges with a least element to play a role analogous to that of complete lattices in traditional morphological theory. In such a sponge the meet of any set is well-de ned, as is the join of any set with a common upper bound, making something similar to a structural opening well-de ned (see Section 6). Analogous to semilattices, we can de ne semisponges: a meet-semisponge is an oriented set such that any nite set with a lower bound has an in mum (a join-semisponge can be de ned analogously). We can consider a meet-semisponge to have an operator M (the meet) that gives the in mum of a set. As the in mum is de ned as the unique lower bound that is an upper bound of all lower bounds, M would still satisfy the part preservation property, as well as a modi ed form of the absorption property: if M(P) is de ned, then ∀a ∈ P : M(a, M(P)) = M(P) . Note that at this point we do not give a (complete) algebraic characterization of a semisponge.

Theorem 3. If S is a conditionally complete meet-semisponge it is a conditionally complete sponge (by duality the same holds for a conditionally complete join-semisponge).
Bereitgestellt von | University of Groningen Angemeldet Heruntergeladen am | 06.11.17 16:15 Proof. If S is a conditionally complete meet-semisponge, this means that the meet is de ned for all (nonempty) sets that have a lower bound. We can now de ne J as giving the meet of the set of all upper bounds of a given set. For any non-empty set with a common upper bound, the set of all (common) upper bounds is again non-empty, and bounded from below by the original set, so its in mum is well-de ned. As a consequence, if this construction turns S into a sponge, then this sponge is conditionally complete. Due to part preservation, the meet of the set of all upper bounds of a set is still an upper bound of the original set, and due to the absorption property it must also be a lower bound of all the upper bounds of the original set. In other words, J can indeed be interpreted as giving the supremum of any (non-empty) subset of S with an upper bound. We can thus conclude that S is a conditionally complete sponge.
If a conditionally complete meet-semisponge has a least element we can give meaning to the meet of all nonempty subsets, as well as the join of the empty set (which would give the least element).
Another interesting property that sponges can have is that the meet of a set of lower bounds is still a lower bound (and dually for upper bounds/joins). It is possible to construct sponges that do not have this property, but the examples given in Section 5 do all have this property. An immediate consequence is that in these sponges the join and meet preserve both upper and lower bounds: a P and P b imply a M(P) and M(P) b (and similarly for the join). A property that seems related (but not equivalent) to sets of lower bounds being closed for meets -in the sense that it is related to transitivity -is the property that guarantees that (for all a, b in some sponge and all P in the power set of that sponge) The property clearly holds in any lattice, but it does not hold in every sponge. As Theorem 7 shows, it is an important ingredient in making openings work. In Proposition 9 it will be shown that the inner product sponge satis es this property in 2D (but not in higher dimensions).

Examples . Inner product sponge
Inspired by the vector levelings developed by Zanoguera and Meyer [48], we can consider a vector a in some Hilbert space as "less" than (or equal to) another vector b if and only if a · (b − a) ≥ . This does not give rise to a partial order, or even a preorder, as the relation is not transitive. However, it can be checked that it does give an orientation, and we will show that it even gives rise to a sponge ( Fig. 2 illustrates the orientation and a meet and join in a toy example). The relation a b ⇐⇒ a · (b − a) ≥ implies that the set of upper bounds of some element a is the half-space de ned by a · b ≥ a . We now de ne the meet of a set of elements as the element closest to the origin in/on the closed convex hull of the set. If the convex hull includes the origin, this is the origin itself (and in this case there is indeed no other lower bound of the entire set). If the origin is outside the convex hull, the meet is still well-de ned (minimization of a strictly convex function over a convex set) and must lie on the boundary of the convex hull. It is possible to see that the original points must thus be upper bounds of the meet. Also, since the meet is in the closed convex hull of the original points, and the set of upper bounds of any element is closed and convex, any element which was a lower bound of all of the original points must still be a lower bound of the meet. Based on Theorem 3, we can now conclude that -based on the meet described above -we have a conditionally complete sponge with the origin as its least element. It is interesting to note that, if we ignore the origin, the inner product sponge allows for a negation (an involutive dual automorphism, [36,Def. 2.29]): the mapping a → a/ a reverses the orientation in the sense that a b ⇐⇒ b/ b a/ a (as long as a and b have non-zero norm). We can verify that it is equivalent We will now see that the inner product sponge satis es Eq. (2) in 2D, allowing for anti-extensive and idempotent "openings" (Theorem 7). Proof. We will rst prove the statement for the meet: M(P) a and b P implies b a or [∃p ∈ P : p a].
The dual statement then follows through using the negation developed above. If M(P) = , b must be zero as well, and the statement is trivially true, so from now on we assume that M(P) is non-zero. Also, if M(P) = p for some p ∈ P, the statement is again trivially true, so we will assume M(P) is on some segment of the boundary of the convex hull of P. Something similar can be concluded for the segment of the line beyond p , covering the entire line. We can now conclude that the statement holds for the meet. The dual statement now follows: a J(P) and P b ⇒ M(P C ) a C and b C P C ⇒ b C a C or ∃p ∈ P : p C a C ⇒ a b or [∃p ∈ P : a p] .
This concludes the proof.
Note that it is possible to give a counter example (violating Eq. (2)) for an inner product sponge on a 3D Hilbert space on the reals, so the restriction to 2D in Proposition 9 is necessary.
Bereitgestellt von | University of Groningen Angemeldet Heruntergeladen am | 06.11.17 16:15 . . Deriving the inner product sponge The inner product sponge described above was originally proposed [48] on heuristic grounds. That is, although using a "box" for the set of lower bounds might have led to a (semi)lattice, it was suggested that using a sphere might be advantageous, as it gives rotation-invariant results. Here we demonstrate that (in hindsight), the sphere-based approach can be derived from the "box-based" approach in a principled manner by enforcing rotation invariance.
The box-based approach is based on saying that a ≤r b (or that a separates r and b) if and only if a ∈ BoxOp(r, b), where BoxOp(r, b) is the smallest axis-aligned box containing r and b (or, equivalently, the axisaligned box having the line segment rb as diagonal). This de nition assumes the value space is a vector space V with an orthogonal basis {e k } k∈K . It can be seen that this de nition is equivalent to saying that a separates r and b if and only if each coe cient a k is closer to r k than b k for all k ∈ K. More generally, we can regard this as a particular instance of the meet-semilattice approach described by Heijmans and Keshet [37, p. 63]. It is worth noting that in the current context '≤r' is (indeed) a partial order giving rise to a meet-semilattice for any r in the vector space. In the remainder we will assume the value space is not just any vector space, but a nite-dimensional Hilbert space on the real numbers.
Proof. First note that for all k ∈ K, b k ≤ a k ≤ r k or r k ≤ a k ≤ b k . As a consequence, a k − r k has the same sign as b k − a k for all k ∈ K. Now, since the basis used for the vector space is assumed to be orthogonal, the inner product (a − r) · (b − a) can be written as the sum (over all k ∈ K) of the products (a k − r k )(b k − a k ).
Combining the last two observations we see that the inner product must indeed be non-negative, concluding the proof.
In other words: ρ rotates a − r to be parallel toê. As a consequence, the coe cients of ρ(a) are the same as those of ρ(r), except for the one corresponding toê. Observe that since (a − r) · (b − a) ≥ , we also have (ρ(a) − ρ(r)) · (ρ(b) − ρ(a)) = λê · (ρ(b) − ρ(a)) ≥ , with λ a positive scalar. We can now see that the coe cients of b must all be farther from the corresponding coe cients of r than those of a. This concludes the proof.

Theorem 4. We have (a − r) · (b − a) ≥ if and only if there is some rotation ρ ∈ SO(V) such that ρ(a) ≤ ρ(r) ρ(b). The set of upper bounds of an element a in the inner product sponge can be described by ρ∈SO(V) {b | ρ(a) ≤ ρ( ) ρ(b)}, and the set of lower bounds by ρ∈SO
Proof. This follows from Lemma 2 and Lemma 1, observing that, due to the rotation invariance of the inner product, the latter indeed allows us to conclude that if there is some rotation ρ such that ρ(a) ≤ ρ(r) ρ(b), then

. Hyperbolic sponge
The "upper half-plane geodesic ordering" (an orientation in our terminology) of the hyperbolic upper halfplane given by Angulo and Velasco-Forero [5, §12.4.4] [4] considers a point less than another point if they are both on the same half of the semicircle through those two points (whose center is on the horizontal axis), and the rst point is higher. The semicircle represents the geodesic through those two points. It can be seen that this is not a transitive relation, and thus not a partial order (nor a preorder). It is, however, re exive and antisymmetric, and thus an orientation.
The meet of a set of points can be de ned as the top of the smallest semicircle (centered on the horizontal axis) that encloses all of the points. We can verify that this gives rise to a conditionally complete meet-semisponge (essentially along the same lines as in the previous example, except that the "origin" lies at in nity, and instead of the convex hull we have the intersection of all x-axis centered closed semidisks that contain the given points). Again, we can de ne the corresponding join as the meet of all common upper bounds of a set, resulting in a proper sponge.
This sponge could be useful for images where each value corresponds to a normal probability distribution [5,19]. Also, if it can be altered to have a di erent point of reference, it could be interesting for ltering values in the chromatic plane as well [21].

. Spherical sponge
Consider the set of "lower bounds" of a point a on a (hyper)sphere to be the set of points on that sphere as close to the midway point between a and whatever we consider the reference point as a is. The antipode of the chosen reference point will be considered to have all points as lower bounds, just like the reference point has all points as upper bounds. This gives rise to a binary relation S , which is at least re exive. It is also not too di cult to see that the relation is antisymmetric, but instead of showing this relation is an orientation and a sponge from the ground up, we will simply show that it is isomorphic to the inner product sponge under stereographic projection.
A set of "lower bounds" as just described corresponds to a so-called spherical cap: the intersection of the sphere with a half space (whose boundary always goes through the chosen reference point). The point whose lower bounds are described by such a spherical cap is the point farthest from the reference point. Note that the largest spherical caps we consider cover less than one hemisphere, considering the set of lower bounds of the point opposite the reference point to be the entire sphere. This is not unlike the structure of the inner product sponge, where for every point the set of upper bounds is a half space, except for the origin, which is a lower bound for the entire space.
Consider the (generalized) stereographic projection (see Fig. 3) and its inverse P(s) = s − (s · r) r + s · r , and P − (a) = (a + r) where r is the chosen reference point on the unit (hyper)sphere in some ( nite-dimensional) Hilbert space, s an arbitrary unit vector, and a a vector on the hyperplane of points orthogonal to r. Clearly, P projects the hypersphere onto a hyperplane, such that P(r) equals the origin (P(−r) can be considered the point at in nity).

Lemma 3. Distance from r on the hypersphere is a strictly increasing function of distance from the origin in the hyperplane (and vice versa).
Proof. We note that the distance on the hypersphere from r is a strictly decreasing function of the inner product with r. The statement now follows from inspecting the de nitions of P and P − .

Theorem 5.
Under the stereographic projection, the set of lower bounds of an element s on the hypersphere projects to the set of lower bounds in the hyperplane (using the inner product sponge) of P(s).
Proof. Let us rst examine the representation in the plane of a general (hyper)spherical cap de ned by s·c ≥ λ: with R = r·c−λ r·c+λ + c ′ , and c ′ = P(c)/(r·c+ λ). Note that in our context λ = r·c, so R = c ′ , and c ′ = P(c)/( λ), so sets of lower bounds on the sphere project to "hyperdisks" in the hyperplane with the origin on their boundary. By Thales' theorem we can see that the latter correspond to sets of lower bounds in the inner product sponge. It now remains to show that the projection of s indeed has the set of lower bounds that corresponds to the projection of the set of lower bounds of s. The easiest way to see that this is true is to consider that in both domains a point has the largest distance to the reference point/origin of all its lower bounds, and then invoking Lemma 3. This concludes the proof.
In other words, since P is a bijection (ignoring the antipode of the reference point at least), s S t ⇐⇒ P(s) I P(t). Here ' S ' is the relation just de ned on the sphere, while I indicates the relation de ning the inner product sponge. The relation ' S ' thus gives rise to a sponge that is isomorphic to the inner product sponge (augmented with a point at in nity). This means that the spherical sponge inherits all of the properties of the inner product sponge.
Note that we have mostly glossed over what happens with the antipode of the reference point. In the inner product sponge this point can be considered to be the "point at in nity", being an upper bound for all elements. Also, we note that if the antipode (rather than the reference point itself) sits on the boundary of a spherical cap, we have −r · c = λ, in which case c ′ is ill-de ned. By a limiting process we can see that such a spherical cap in fact corresponds to a half space in the hyperplane. Conversely, sets of upper bounds on the sphere are spherical caps, just like sets of lower bounds. This can also be seen by considering the analogue of re ecting in the hyperplane orthogonal to r in the inner product sponge: In the last step we make use of the fact that a · r = . This means a re ection in the hyperplane orthogonal to r is a negation in the spherical sponge.

. Hemispherical sponge
Now suppose we are only interested in the (open) hemisphere Hr de ned by s · r > for some reference point r on the (hyper)sphere (the construction is not limited to 3D). Now consider s t ⇐⇒ log s (r) · log s (t) ≤ , where log s (t) gives the tangent vector at s of the (shortest) geodesic connecting s and t. This condition can be seen to be analogous to the one used for the inner product sponge, but we cannot immediately assume that this relation forms a sponge as well. For example, if we consider the earth a sphere, with the north pole as the reference point, then we can see that any point on the equator is "less than or equal to" any other point on the equator. Using the above relation, the set of upper bounds of an element s on the hemisphere is the intersection of the hemisphere with the half space de ned by t·n(s) ≥ (so it is an intersection of two di erent hemispheres), with n(s) = (s − r) − ((s − r) · s) s.

It can be veri ed that n(s) is orthogonal to s (meaning that s is on the boundary of the set of upper bounds).
In fact, one can see that n(s) is opposite to the tangent vector at s pointing towards r.
We can now again see that the relation de ned above is isomorphic to the inner product sponge, this time through the gnomonic projection (see Fig. 4): Note that this projection is only valid for the (open) hemisphere Hr.

Theorem 6. Under the gnomonic projection, the set of upper bounds associated with s on the open hemisphere Hr projects to the set of upper bounds (using the inner product sponge) associated with P(s).
Proof. The set of upper bounds associated with s is the intersection of Hr and the hemisphere de ned by t · n(s) ≥ . We note that the restriction to Hr is no restriction at all, since the projection only establishes a bijection precisely between this hemisphere and the hyperplane. Now, consider the hemisphere de ned by t · n ≥ . Its projection on the hyperplane can be de ned by P − (a) · n ≥ ⇐⇒ a + r a + r · n ≥ ⇐⇒ (a + r) · n ≥ ⇐⇒ a · n ≥ −r · n ⇐⇒ a · P(n) ≥ −r · n.
This shows that any set of upper bounds on the sphere projects to a half-space on the hyperplane. If we set n = n(P − (a)), and using a · P(n) ≥ −r · n ⇐⇒ n · (a + r) ≥ , we can see that a is on the boundary of the half-space: n · (a + r) = ( a + r a + r − r) · (a + r) − (( a + r a + r − r) · a + r a + r ) a + r a + r · (a + r) Given that the direction of the orthogonal projection of a vector onto the hyperplane is not a ected by gnomonic projection, and that the direction of the orthogonal projection of s is the same as that of n(s), we can see that the boundary of the gnomonic projection of the set of upper bounds on the sphere of P − (a) coincides with the boundary of the set of upper bounds of a. Since the projection of the reference point cannot be in the set of upper bounds (for any a ≠ ), we conclude that the two half-spaces are in fact equal. Since P is a bijection on the (open) hemisphere Hr, this concludes the proof.
This means we again have a sponge that is isomorphic to the inner product sponge. We expect this sponge might be useful in the context of barycentric coordinates encoding probabilities [22] (translated to a hypersphere through the mapping discussed by Gromov [30, p. 14], also see [20]), possibly through an extension of n-ary mathematical morphology [16].
Bereitgestellt von | University of Groningen Angemeldet Heruntergeladen am | 06.11.17 16:15 The original 1D angle-valued signal (the grey arrows plus noise), the result of a structural pseudo-erosion, the result of a structural "opening", the result of the corresponding "closing", and the average of the two. The empty circle and lack of arrow in one of the circles on the second row indicate that for that position no angle could be given as the meet, resulting in a special "bottom" value instead. The operators were computed using a flat structuring element consisting of three adjacent positions, using periodic boundary conditions. Source code available at http://bit.ly/ 1Rz8SVp.

. Angle sponge
Another problem area for the lattice formalism is that of periodic value spaces, like angles. Several solutions [3,6,34,41,45] have been proposed to deal with angles, but none of them really deal with the inherent periodicity of angles. This is not by accident: it is impossible to have a periodic lattice.
Interestingly, we can create a periodic sponge: consider an angle a to be less than an angle b -both considered to be in the interval [ , π) -if and only if b − π < a ≤ b or b − π < a − π ≤ b. In other words: a is less than b if and only if a is less than 180 • clockwise from b. It is clear that the above gives an orientation (the relation is re exive and antisymmetric). Furthermore, if a set of angles has a common upper bound, all angles must lie on some arc of less than 180 degrees, and there must be a unique supremum (similarly for the in mum). We can thus conclude that we have de ned a (periodic) conditionally complete sponge on angles. It can be veri ed that Eq. (2) holds in this sponge (since J(P), when de ned, is always an element of P), so due to Theorem 8, the "opening" and "closing" demonstrated in Fig. 5 are idempotent (interestingly, applying a closing after having applied an opening also seemed to have no e ect).
In practice, it might be objectionable not to be able to deal with sets of angles spanning more than 180 • . An easy method for making this work is to add a "smallest" and a "largest" element that are given as meet or join when the angles do span more than 180 • , e ectively encoding the lack of a clear smallest or largest angle.

. A non-sponge: The Loewner order
The Loewner order [9] considers a (symmetric) matrix A less than or equal to another (symmetric) matrix B if the di erence B − A is positive semide nite. This is a partial order compatible with the vector space structure of (symmetric) matrices, but it does not give rise to a lattice, or even a sponge. Any join/meet based on the Loewner order cannot satisfy both the absorption property and part preservation at the same time (we gave an example where part preservation breaks down in previous work [31]). As a partial x, Burgeth et al. originally [12] computed the meet as the matrix inverse of the join of the inverses, so at least positive semide niteness Bereitgestellt von | University of Groningen Angemeldet Heruntergeladen am | 06.11.17 16:15 would be preserved. However, matrix inversion does not reverse the order, and this still does not solve the problem that no upper bound of two matrices can be a lower bound of all common upper bounds.
In later work Burgeth et al. compute both the join and meet in a way that is compatible with the Loewner order [10,11], but as a result they have to be careful not to get values outside the original range. The resulting structure is likely to be a χ-lattice [38], but it is not yet clear how important this is from a morphological perspective. Similarly, perhaps it is possible to (for example) design proper openings and closings through some other means than directly translating the traditional lattice-based de nitions. However, based on the arguments presented by Pasternak et al. [40] and some preliminary experimentation, we expect it could be interesting to simply use the inner product sponge directly on the vector space of symmetric tensors (which would still preserve positive semide niteness).

Operators
One of the main advantages of the lattice-theoretical framework is that it allows us to classify operators into various categories based on certain lattice-related properties, and that these classes often have useful and intuitive interpretations. Although it remains to be seen to what extent existing classes carry over to the sponge case, here we show that at least one crucial property is preserved when we directly translate so-called "structural openings" (and in the process, that we can reason about such things for sponges in general). We also consider levelings.

. Openings
We can try to translate structural dilations and erosions on images de ned on a (translation-invariant) domain E to the sponge case. We then get a dilation-like operator de ned by δ A (f )(x) = J({f (y) | x ∈ Ay}) and an erosion-like operator ε A (f )(x) = M({f (y) | y ∈ Ax}) (where x ∈ E and Ay is taken to be the structuring element translated by y). These operators need not commute with taking the join or meet, respectively, nor do they need to satisfy δ A (f ) = M({g | f ≤ ε A (g)}) like in a complete lattice [36,Prop. 3.14]. It is an open question whether there exist di erent de nitions that recover a bit more of the traditional properties (while remaining compatible with the lattice case). Nevertheless, we can use these operators to de ne an operator that behaves a bit like a lattice-based structural opening (and is a structural opening if the sponge is a lattice): It is immediately obvious that the resulting operator is still guaranteed to be anti-extensive (due to each of the M({f (z) | z ∈ Ay}) being a lower bound of f (x)), something which is not guaranteed by Loewner-based operators [31]. The operator may no longer be idempotent though. Increasingness is also potentially violated, but this is mostly due to the meet and join not necessarily being increasing in a sponge, so it may make sense to look for a di erent property. In any case, the above shows that for any image, the set of lower bounds that can be written as a dilation of some other image is non-empty, so it should be possible to implement some sort of projection onto this set, giving an operator that would clearly be anti-extensive and idempotent.
A slightly more promising avenue of attack might be de ning an opening in terms of root signals. Suppose γ is an opening on a complete lattice L. Its invariance domain is the set of all elements of L that are xed under application of γ (also known as root signals): Inv(γ) = {a | a ∈ L and γ(a) = a}. We then have [36,Th. 3.23]: Conversely, given some subset I of L, the operator γ ′ (a) = {b | b ∈ I and b ≤ a} is clearly anti-extensive and increasing. It is also idempotent, as the subset of I that is less than γ ′ (a) clearly contains at least all the elements that were used for γ ′ (a), and we already concluded that γ ′ is anti-extensive. γ ′ is thus an opening (although its invariance domain need not be equal to I).
Bereitgestellt von | University of Groningen Angemeldet Heruntergeladen am | 06.11.17 16:15 So what if we take the above as the de nition of an opening? We would then have the following spongebased (candidate) opening (with I ⊆ S): I and b a). (3) The sponge-based "opening" γ I de ned above is clearly anti-extensive (J(a, γ I (a)) = a), due to part preservation and the fact that we take the join of elements that are all lower bounds of the argument. Also, for any b ∈ I we have b a ⇒ b γ I (a), because of the de nition above and the absorption laws. As a consequence γ I (γ I (a)) must be the join of a superset of the elements in the join used to compute γ I (a). Based on the absorption laws and subassociativity, we have J(P ∪ Q) J(P) and thus γ I (γ I (a)) γ I (a). However, we also already showed that γ I is anti-extensive. We can thus conclude that γ I as given above is both idempotent and anti-extensive. Again, increasingness in its original form may not hold. However, there might be alternatives. For example, Proposition 10 shows that for identifying openings, γ(a) b ⇒ γ(a) γ(b) could replace increasingness as a criterion, and this property is only slightly stronger than the property of γ I that for any Proposition 10. In a lattice L, the combination of anti-extensivity, idempotence, and increasingness is equivalent to the combination of anti-extensivity, idempotence, and γ(a) ≤ b ⇒ γ(a) ≤ γ(b).
Proof. First assume that γ is anti-extensive, idempotent, and increasing. We then have γ(a) ≤ b ⇒ γ(γ(a)) = γ(a) ≤ γ(b) (for all a, b ∈ L). This proves the rst half of the statement. Now assume that γ is anti-extensive and idempotent, and satis es γ(a) . This concludes the proof.
The above shows that we can de nitely de ne something that has all (most of) the hallmarks of an opening, but having to compute the join over all elements in I that are a lower bound of the input might be a bit too much, both because in a general sponge it might be hard to identify this set, and because it might not be powerful enough (see Fig. 6). Instead, it might be more natural/convenient to use the maximal elements of I ∩ L(a). This is well-de ned as long as the sponge is conditionally complete and I is tournament-sup complete. In a (complete) lattice the join of the maximal elements of a chain-sup complete set is the same as the join of the original set [47,Prop. 1]. In a general sponge, the analogous statement is not necessarily true, leading us to explicitly de ne γ N I (a) = J(ψ N ({b | b ∈ I and b a})). (4) Here we assume that I is tournament-sup complete, and the underlying sponge conditionally complete. We should also have that for every element a of the sponge, there is some lower bound of a in I. It can be veri ed that γ N I is (still) anti-extensive, and Theorem 7 shows that under certain conditions it is also idempotent. However, in general it is de nitely di erent from γ I . Proof. Clearly, i ∈ I ∩ L(i), and since i is also an upper bound of I ∩ L(i), it must be the only maximal element in I ∩ L(i).
We warn the reader not to assume that I is precisely the set of invariant elements (this need not even hold in the lattice context), nor to assume that γ I = γ Inv(γ I ) (which is the case when the sponge is a lattice). It is currently not clear whether the last equality only holds when the sponge is a lattice, or whether it holds more generally, but for the moment we cannot assume that it holds in a general sponge. ). We will prove that ψ N (Q) = P, and by extension that γ N I (γ N I (a)) = γ N I (a). Clearly, P ⊆ Q and P a. Furthermore, for all q ∈ Q, we have q J(P). Since we assumed Eq. (2) holds in this sponge, we now have q a or [∃p ∈ P : q p]. If q a, then q ∈ I ∩ L(a), and as a result q ∈ P or q ∉ ψ N (Q), since it is bounded from above by some element in P (due to the last condition on I).
Alternatively, if q ̸ a, there must be some p ∈ P (p ≠ q) such that q p, in which case q cannot be in ψ N (Q). Summarizing, every q ∈ Q must be either in P, or not in ψ N (Q): ψ N (Q) ⊆ P. Conversely, since P ⊆ Q, ψ N (Q) cannot possibly be a strict subset of P, so we have ψ N (Q) = P. This concludes the proof.
The last condition on I in Theorem 7 may look at little strange, but Theorem 8 shows that there are in fact (non-trivial) sets that do have this property. Also, Wilkinson [47,Prop. 1] has shown that it always holds in a lattice. It remains to be seen whether this is the best way to generalize openings to sponges, but at least we can see that it neatly generalizes a lattice-based de nition, and that there are non-trivial sponges (that are not lattices) and sets I to which Theorem 7 applies. Theorem 8 (Structural "openings"). Take E to be some vector space and S a conditionally complete sponge with a least element . Consider Ay to be the set {x + y | x ∈ A} for a (strict) subset A of E and all elements y of E. The operator γ A on Fun(E, S) given by γ A (f )(x) = J({M({f (z) | z ∈ Ay}) | x ∈ Ay}) can be expressed as γ N I for a set I that can be used in Theorem 7. Here A ⊂ E is a so-called " at" structuring element.
Proof. In a slight abuse of notation, we write (with a ∈ S and x, y ∈ E) (a Ay)(x) = a x ∈ Ay, and otherwise. Now, consider the set I = {a Ay | y ∈ E and a ∈ S}. Clearly, I ⊆ Fun(E, S), and since it contains x → ( Ay for any y ∈ E), it contains a lower bound for every element of Fun(E, S). To see that I is also tournamentsup complete, suppose that two elements a Ax and b Ay are comparable. Then either Ax = Ay, a = or b = must hold. In the latter two cases we can assume the rst condition holds without loss of generality.
We thus have that Ax = Ay for any two elements a Ax and b Ay in a tournament contained in I. This means the supremum (if it exists) of such a tournament is simply Ax weighted by the supremum of the weights (if it exists) of the elements in the tournament. Clearly (if it exists) this is again an element in I, proving that I must be tournament-sup complete. It now just remains to show that I ∩ L(f ) ψ N (I ∩ L(f )) holds for all f in the sponge Fun(E, S). This follows from the analysis below, which essentially shows that I ∩ L(f ) is y∈E {a Ay | a ∈ S and a Ay f }, whose maximal elements can neatly be given by {M({f (z) | z ∈ Ay}) Ay | y ∈ E}. It can be checked that the latter indeed contains an upper bound for every element of the former. I is thus suitable for use in Eq. (4).
Bereitgestellt von | University of Groningen Angemeldet Heruntergeladen am | 06.11.17 16:15 We now note that γ A (f ) = δ A (ε A (f )) is a join of elements from I: Note that the above proof does not rely on Eq. (2). However, the "opening" is not (necessarily) idempotent unless Eq. (2) holds. Also note that even though in some sponges structural "openings" are idempotent, we still do not (necessarily) have

. Levelings
Another interesting kind of operator is a "leveling". This term is used both for the operator and the result of applying such an operator. Formally, if L is a modular lattice, then g ∈ L is a leveling of f ∈ L if and only if g = ε(g)∨(f ∧δ(g)) [39] (or, equivalently, g = (ε(g)∨f )∧δ(g)).
Here ε and δ are assumed to be an anti-extensive erosion and its corresponding extensive dilation, such that together they form an adjunction. Following Zanoguera and Meyer [48], consider g to be an A-leveling of f if and only if g = ε A (g), where A is a structuring element, and ε A the corresponding structural pseudo-erosion. Here the sponge is assumed to be set up in such a way that f is the lowest possible value. This construction can be justi ed by going through a meet-semilattice like the one developed by Heijmans and Keshet [37]. As an example, consider a vectorvalued image f : E → V, with V a Hilbert space. We could then set up a sponge that uses the inner product sponge per position x ∈ E, with f (x) as the origin: This precisely recovers the vector levelings de ned by Zanoguera and Meyer [48]. We can now de ne levelings for any situation in which we can de ne a family of sponges such that for each possible value there is a (unique) sponge that has that value as smallest element.

Conclusion
There is a need for mathematical morphology beyond what can be done with lattices. To this end, we have proposed a novel algebraic structure (closely related to the notion of a weakly associative lattice). This structure generalizes lattices not by forgoing (unique) meets and joins, but rather by letting go of having a (transitive) order. It preserves the absorption property though, as well as a property called "part preservation". These properties are important in the intuitive interpretation of joins and meets: absorption guarantees that the meet of a set is a lower bound of the set, while part preservation guarantees that a meet is truly the "greatest" lower bound, in the sense that it is an upper bound of all other lower bounds.
To demonstrate the potential relevance of sponges, some existing methods are shown to fall within this new framework, while the Loewner-order is shown to fall outside it (correlating with some of the issues it has). All in all, we present the following (kinds of) sponges: Inner product Based on a previously existing vector leveling scheme [48], this type of sponge is applicable to any Hilbert space, and provides rotation-and scale-invariant joins and meets. Hyperbolic Previously presented as a pseudo-morphological method for ltering images whose pixel values are normal distributions [4,5], we show that it is in fact a sponge, and suggest it may also be interesting for colour images if a di erent reference point can be used. Spherical We present a new sponge that can be used on any (hyper)sphere, as long as we can pick a particular point as the minimal point. This sponge turns out to be isomorphic to the inner product sponge.
Bereitgestellt von | University of Groningen Angemeldet Heruntergeladen am | 06.11.17 16:15 Hemispherical Also isomorphic to the inner product sponge, this type of sponge might be useful wherever the value space consists of (discrete) probability distributions. Angle Our simplest sponge is arguably the sponge on angles. It demonstrates that sponges can be periodic, something which is utterly impossible with lattices.
One advantage of recognizing these as sponges rather than ad-hoc constructions is that sponges guarantee relatively intuitive interpretations of joins and meets. Also, sponges allow us to reason about the structure itself. For example: we can recognize conditionally complete semisponges and see that any conditionally complete semisponge is a full (conditionally complete) sponge. It may also be possible to give characterizations of certain classes of sponges, as has been done for weakly associative lattices [42].
A start is made in showing how sponges might allow reasoning about operators, similar to how this is typically done in lattice-based morphology. So far, especially openings and levelings appear to be reasonably compatible with sponges, while erosions and dilations may require some rethinking. In particular, openings allow generalization to sponges in the sense that certain de nitions of openings in the lattice context give rise to operators that are anti-extensive on all sponges, and idempotent on some sponges (in particular the 2D inner product sponge). We suspect these operators may also satisfy a property that can replace increasingness. It may also be possible to de ne "openings" in terms of projections onto certain sets.
In terms of future work, the eld is wide open: are sponges the "right" generalization of lattices? What kinds of sponges give what opportunities? What classes of operators can be de ned?
The list of open questions is endless. Also, it would be interesting to see if additional (useful) sponges can be constructed or found in the literature. For example, one may wonder whether some of the more algebraic methods given by Angulo [2], Burgeth et al. [13] give rise to sponges. In addition, it would be useful to establish "recipes" for constructing sponges that agree with a given preorder, as an alternative to a lexicographical cascade or other disambiguation methods [1,6,17,18,46]. It may even be interesting to combine the concept of h-adjunctions [28] with sponges.

A Algebraic structures
In this appendix we give an extended motivation for the statements and accompanying Euler diagram (Fig. 1) in Section 3.

Proposition 12.
WALs, sponges and partially ordered sets generalize lattices. Bereitgestellt von | University of Groningen Angemeldet Heruntergeladen am | 06.11.17 16:15 Proof. That partially ordered sets generalize lattices is well-known. That WALs generalize lattices is fairly straightforward, since they satisfy the same properties as lattices, except for associativity, which is replaced by weak associativity or, equivalently, part preservation. It is fairly straightforward to check that part preservation is implied by associativity.

Proposition 13. There are WALs that are not sponges (and vice versa).
Proof. Figure 7a provides an example of a WAL that is not a sponge. The orientation is set up such that any two elements have a join (being one of the elements, and that the set of three elements in the leftmost cycle has three common upper bounds, but no join. As a consequence, it is a WAL but not a sponge. Conversely, the inner product sponge is a clear example of a sponge that is not a WAL (not every pair of elements has a join).

Proposition 14.
A WAL that is also a partial order is a lattice (and thus also a sponge).
Proof. This follows from the fact that a WAL guarantees that any pair has a join/meet. Since a lattice is precisely a partial order with that guarantee, a WAL that is also a partial order must be a lattice (and thus also a sponge, since sponges generalize lattices).

Proposition 15. A partially ordered set that is also a 2-sponge is a sponge.
Proof. If a partially ordered set is a 2-sponge, any pair of elements with a common upper bound must have a join. Now consider a nite set of more than two elements (with a common upper bound): P={a , a , . . . , an}. Assume j = jn, with j = a and j i = J(j i− , a i ) for < i ≤ n. If we have p ≤ u for all p ∈ P, then, by a similar reasoning as in Proposition 8, j i ≤ u for all i between and n. This also means j is well-de ned. And due to transitivity, j must be an upper bound of every element in the set P. It is now clear that j is the supremum (or join) of P. As in ma can be shown to exist analogously, we have now shown that any partially ordered set that is also a 2-sponge is in fact a sponge.
It should be noted that a "partially ordered 2-sponge" need not be a lattice, as not all pairs of elements necessarily have a join.

Proposition 16.
There are partially ordered sets that are not 2-sponges (and vice versa).
Proof. It is easy to construct a partial order in which two elements have precisely two common upper bounds, neither of which is an upper bound of the other. Clearly this is not a 2-sponge. Conversely, any 2-sponge (or sponge in general, which is also a 2-sponge) whose orientation lacks transitivity is clearly not a partial order.

Proposition 17. 2-sponges are strictly more general than both WALs and sponges.
Proof. Consider an oriented set with three elements a, b, and c, such that a b, b c, but nothing else (apart from the relations implied by re exivity) holds. For any pair of elements with a common upper bound there exists a supremum (and likewise for the in mum), but there is no supremum for the pair (a, c), and there is also no supremum for the entire set of three elements.

Proposition 18.
Oriented sets are strictly more general than 2-sponges and partial orders.
Proof. That oriented sets are strictly more general than partial orders can be seen from the example used in Proposition 17 (in a partial order we would necessarily also have a c). The orientation shown in Fig. 7b demonstrates that an orientation need not be a 2-sponge: the two elements on the left clearly have common upper bounds, but no supremum.

Proposition 19.
There are sponges that are also a WAL, but not a lattice.

Proposition 20. Not all sponges have sets of lower bounds that are closed for meets (so a, b c ⇒ M(a, b) c may not hold).
Proof. Figure 7c provides an example of a sponge that violates the mentioned property.