Accepted Manuscript

A graph-based mathematical morphology reader

Laurent Najman, Jean Cousty

PII: S0167-8655(14)00154-8

DOI: http://dx.doi.org/10.1016/j.patrec.2014.05.007

Reference: PATREC 6016

To appear in: Pattern Recognition Letters

Accepted Date: 6 May 2014

Please cite this article as: Najman, L., Cousty, J., A graph-based mathematical morphology reader, Pattern

Recognition Letters (2014), doi: http://dx.doi.org/10.1016/j.patrec.2014.05.007

This is a PDF file of an unedited manuscript that has been accepted for publication. As a service to our customers we are providing this early version of the manuscript. The manuscript will undergo copyediting, typesetting, and review of the resulting proof before it is published in its final form. Please note that during the production process errors may be discovered which could affect the content, and all legal disclaimers that apply to the journal pertain. 1

Pattern Recognition Letters journal homepage: www.elsevier.com

A graph-based mathematical morphology reader

Laurent Najman, Jean Cousty

Universite´ Paris-Est, Laboratoire d’Informatique Gaspard-Monge, E´quipe A3SI, ESIEE Paris.

E-mail: {laurent.najman, jean.cousty}@esiee.fr

The two authors contributed equally to this work which received funding from the Agence Nationale de la Recherche, contract ANR-2010-BLAN-0205-03.

ARTICLE INFO ABSTRACT

Article history:

Graphs

Mathematical Morphology

Computer Vision

Image Analysis

Filtering

Segmentation

This survey paper aims at providing a “literary” anthology of mathematical morphology on graphs. It describes in the English language many ideas stemming from a large number of different papers, hence providing a unified view of an active and diverse field of research. c© 2014 Elsevier Ltd. All rights reserved. 1. Introduction

Mathematical morphology was born almost 50 years ago (Serra, 1982), initialy an evolution of a continuous probabilistic framework (Matheron, 1975). Historically, this was the first consistent non-linear image analysis theory which from the very start included not only theoretical results, but also many practical aspects, including algorithmic ones (Soille, 1999).

Despite its continuous origin, it was soon recognized that the roots of this theory were in algebraic theory, notably the framework of complete lattices (Heijmans, 1994). This allows the theory to be completely adaptable to non-continuous spaces, such as graphs. For a survey of the state of the art in mathematical morphology, we recommend (Najman and Talbot, 2010).

Graphs are generic data structures that have a long history in mathematics and have been applied in almost every scientific and engineering field, notably image analysis and computer vision (Le´zoray and Grady, 2012; Grady and Polimeni, 2010).

Because of their many interesting properties, a current trend is to develop the classical continuous tools from signal processing onto this kind of structures (Shuman et al., 2013).

The usefulness of graphs for mathematical morphology has long been recognized (Vincent, 1989), and the same trend as in the signal processing community can be observed here (Najman and Meyer, 2012). The objective of this paper is to offer an overview of the advantages of graphs for mathematical morphology. To reach a wider audience, we decided to express all the ideas with the least possible mathematical jargon, if possible without any equation whatsoever. We emphasize that point by using the word reader in the title. This paper aims at being a “literary” anthology of papers using graph in the field of mathematical morphology, describing in the English language the main ideas of many papers, pointing out where the interested researcher can find more details.

This paper is organized as follows. Section 2 describes what is a graph, what type of graphs can be encountered, and how we can build them. Section 3 explains the basis of algebraic morphology and what are the adjunctions that are used on graphs for defining elementary morphological operators. One of the most basic problem in graphs is finding paths, and section 4 gives an overview of what has been done with paths in the field. The next section 5 is divided in three parts. In the first part (section 5.1), two major morphological tools for segmentation, namely the watershed and the flat zone approach, are reviewed. The second part (section 5.2) deals with their close cousin, connective filtering. Combining these two parts togethers provide hierarchical segmentation and filtering, which is the object of section 5.3.

Section 6 exhibits some links between graph-morphology and discrete calculus. Before concluding the paper, a penultimate section 7 describes several interesting structures that generalize graphs. 2 2. What is a graph and some examples of graphs for morphological processing

A graph is a representation of a set of data where some pairs of data are connected by links. Once a graph representation is adopted, the (abstraction of) interconnected data are called vertices or nodes of the graph and the links that connect vertices are called edges. An edge of the graph is then simply a pair of connected vertices. Thus, a graph is made of a set of vertices and of a set of edges. If needed, we can also associate to each vertex and/or to each edge a weight that represents some kind of measure on the data, leading to weighted graphs. Once a graph is specified, the neighbors of a data point can be obtained by considering the edges that link this data point to others in the graph. Conversely, if we know the neighbors of each data point, then we can obtain edges by considering all pairs of neighbors.

Thus, another common (and equivalent) way to define a graph is to consider the sets of neighbors of each vertex instead of a set of edges; in this case, the neighbourhood relation is symmetrical.

In image processing, the first (historically) example is the case of an image itself: indeed, an image is a set of pixels with integer coordinates and color information. These pixels are often structured in a grid thanks to the classical pixel adjacency relation (i.e., 4- or 8- adjacency in 2D (Kong and Rosenfeld, 1989), see Figs. 1(a) and (b)). For example, a pixel is connected to the 4 or 8 closest pixels according to the Euclidean distance between the integer coordinates. In the associated graph representation, pixels are vertices, and if two pixels are connected for the given grid-adjacency, they are linked by an edge of the graph. In the literature, the set of vertices is often denoted by V (for vertices) or N (for nodes); the set of edges is generally denoted by E. The weight of a vertex can be as simple as the gray value of the corresponding pixel, or as complex as a measure combining color information and other cues, etc., taken on a patch around the pixel. The weight of an edge is generally a kind of distance between the data of the pixels linked by the given edge. For example, in the case of a gray-scale image, the edge weight can be a gradient of intensity such as the absolute difference between pixel intensities.