Morphological filtering on graphs

We study some basic morphological operators acting on the lattice of all subgraphs of an arbitrary (unweighted) graph GG. To this end, we consider two dual adjunctions between the edge set and the vertex set of GG. This allows us (i) to recover the classical notion of a dilation/erosion of a subset of the vertices of GG and (ii) to extend it to subgraphs of GG. Afterward, we propose several new openings, closings, granulometries and alternate filters acting (i) on the subsets of the edge and vertex set of GG and (ii) on the subgraphs of GG. The proposed framework is then extended to functions that weight the vertices and edges of a graph. We illustrate with applications to binary and grayscale image denoising, for which, on the provided images, the proposed approach outperforms the usual one based on structuring elements.

► Morphological operators acting on subgraphs of a graph GG are studied. ► Two dual adjunctions between edge and vertex sets of GG are considered. ► Classical dilations/erosions on vertices are recovered and extended to subgraphs. ► New granulometries and alternate filters are proposed. ► Applications to image denoising illustrates the proposed framework.