Mathematical Morphology on Hypergraphs Using Vertex-Hyperedge Correspondence

The focus of this paper is to develop computationally efficient mathematical morphology operators on hypergraphs. To this aim we consider lattice structures on hypergraphs on which we build morphological operators. We develop a pair of dual adjunctions between the vertex set and the hyperedge set of a hypergraph , by defining a vertex-hyperedge correspondence. This allows us to recover the classical notion of a dilation/erosion of a subset of vertices and to extend it to subhypergraphs of . This paper also studies the concept of morphological adjunction on hypergraphs for which both the input and the output are hypergraphs. 1. Introduction Mathematical morphology, appeared in 1960s, is a theory of nonlinear information processing [1–4]. It is a branch of image analysis based on algebraic, set-theoretic, and geometric principles [5, 6]. Originally, it is developed for binary images by Matheron and Serra. They are the first to observe that a general theory of mathematical morphology is based on the assumption that the underlying image space is a complete lattice. Most of the morphological theories at this abstract level were developed and presented without making references to the properties of the underlying space. Considering digital objects carrying structural information, mathematical morphology has been developed on graphs [7–10] and simplicial complexes [11], but little work has been done on hypergraphs [12–15]. When dealing with a hypergraph , we need to consider the hypergraph induced by the subset of vertices of (see Figures 1(a) and 1(b), where the blue vertices and edges in (b) represent ). We associate with the largest subset of hyperedges of such that the obtained pair is a hypergraph. We denote it by (see Section 3.1 and Figure 1(b)). We also consider a hypergraph induced by a subset of the edges of , namely, . Figure 1: Illustration of hypergraph dilation. Here we propose a systematic study of the basic operators that are used to derive a set of hyperedges from a set of vertices and a set of vertices from a set of hyperedges. These operators are the hypergraph extension to the operators defined by Cousty et al. [7, 8] for graphs. Since a hypergraph becomes a graph when for every hyperedge , all the properties of these operators are satisfied for graphs also. We emphasise that the input and output of these operators are both hypergraphs. The blue subhypergraph in Figure 1(c) is the result of the dilation of the blue subhypergraph in Figure 1(b) proposed in this paper. Here the resultant subhypergraph in Figure 1(c) is not induced by its