Fundamenta Informaticae - Volume 41, issue 1-2

Authors: Goutsias, John | Heijmans, Henk

Article Type: Other

DOI: 10.3233/FI-2000-411209

Citation: Fundamenta Informaticae, vol. 41, no. 1-2, pp. i-ii, 2000

Authors: Goutsias, John | Heijmans, Henk J.A.M.

Article Type: Research Article

Abstract: Mathematical morphology is a geometric approach in image processing and analysis with a strong mathematical flavor. Originally, it was developed as a powerful tool for shape analysis in binary and, later, grey-scale images. But it was soon recognized that the underlying ideas could be extended naturally to a much wider class of mathematical objects, namely complete lattices. This paper presents, in a bird's eye view, the foundations of mathematical morphology, or more precisely, the theory of morphological operators on complete lattices.

Keywords: adjunction, alternating sequential filter, Boolean function, closing, complete lattice, connectivity, connected operator, dilation, erosion, flat operator, fuzzy set, grain operator, granulometry, grey-scale image, idempotence, mathematical morphology, morphological filter, morphological operator, multivalued image, opening, thresholding

DOI: 10.3233/FI-2000-411201

Citation: Fundamenta Informaticae, vol. 41, no. 1-2, pp. 1-31, 2000

Authors: Keshet(Kresch), Renato

Article Type: Research Article

Abstract: This work extends the scope of mathematical morphology from complete lattices to complete semilattices, and presents some applications of this extension. More specifically, we first define and briefly analyze basic morphological operators in complete inf-semilattices. Then, difference and reference semilattices are introduced. Finally, some video processing applications in these semilattices are presented, namely: Detection of fast motion, innovation extraction, and contour compression for segmentation-based coding.

Keywords: complete semilattices, innovation extraction, morphological gradient, motion detection, segmentation-based coding, skeleton, top-hat transform, video processing

DOI: 10.3233/FI-2000-411202

Citation: Fundamenta Informaticae, vol. 41, no. 1-2, pp. 33-56, 2000

Authors: Vincent, Luc

Article Type: Research Article

Abstract: Granulometries constitute one of the most useful and versatile sets of tools of morphological image analysis. They can be applied to a wide range of tasks, such as feature extraction, texture characterization, size estimation, image segmentation, etc., both for binary and for grayscale images. However, for most applications, traditional granulometry algorithms – involving sequences of openings or closings with structuring elements of increasing size – are prohibitively costly on non-specialized hardware. This has prevented granulometries from reaching a high level of popularity in the image analysis community. This paper addresses the computational aspect of granulometries and proposes a comprehensive set …of fast algorithms. In binary images, all but the simplest cases (namely linear granulometries based on openings with line segments) require the prior extraction of opening transforms (also referred to as “granulometry functions”). A very efficient algorithm is proposed for the computation of the most useful opening transforms. In grayscale images, linear granulometries are considered first and a particularly efficient algorithm is described. The concept of an opening tree is then proposed as a gray extension of the opening transform. It forms the basis of a novel technique for computing granulometries based on maxima of openings by line segments in different orientations, as well as pseudo-granulometries based on minima of linear openings. Furthermore, opening trees can be used in local granulometry algorithms, thereby making it possible to compute such objects as size transforms directly from grayscale images. Other applications include adaptive openings and closings, as well as granulometric texture segmentation. The efficiency of this set of algorithms greatly increases the range of problems that can be addressed using granulometries. A number of applications are used throughout the paper to illustrate the usefulness of the proposed techniques. Show more

Keywords: algorithms, feature extraction, granulometries, local granulometries, mathematical morphology, opening transforms, opening tree, pattern spectrum, size transforms, texture

DOI: 10.3233/FI-2000-411203

Citation: Fundamenta Informaticae, vol. 41, no. 1-2, pp. 57-90, 2000

Authors: Maragos, Petros | Butt, Muhammad Akmal

Article Type: Research Article

Abstract: In differential morphology, multiscale dilations and erosions are modeled via nonlinear partial differential equations (PDEs) in scale-space. Curve evolution employs methods of differential geometry to study the differential equations governing the propagation of time-evolving curves, under velocities dependent on global information or on local geometric properties of the curve. The PDEs governing multiscale morphology, and most cases of curve evolution, are of the Hamilton-Jacobi type and are related to the eikonal PDE of optics. In this paper, we explore the common theoretical concepts, tools, and numerical algorithms used in differential morphology and curve evolution, by emphasizing level set methods. Morphological …operator representations of various curve evolution cases are discussed, as well as evolution laws for various morphological curve operations. We also focus on distance transforms, as the major route to connect differential morphology and curve evolution to the eikonal PDE. Furthermore, we discuss applications of differential morphology and curve evolution to various multiscale and/or eikonal problems, such as distance transform computation, ray tracing in optics, eikonal image halftoning, and watershed-based image segmentation. Show more

Keywords: computer vision, curve evolution, differential morphology, distance transforms, image processing

DOI: 10.3233/FI-2000-411204

Citation: Fundamenta Informaticae, vol. 41, no. 1-2, pp. 91-129, 2000

Authors: Soille, Pierre

Article Type: Research Article

Abstract: The convex hull of a set is the smallest convex set containing this set. In ℜ2 , this definition is equivalent to the intersection of all half-planes containing the set. We show that this latter definition is nothing but an algebraic closing that can be applied to 2-D grey scale images. The resulting grey scale image is convex, in the sense that all its cross-sections are convex. An efficient translation-invariant implementation, leading to a decreasing family of convex sets that converges to an exact discrete convex hull, is proposed.

Keywords: convex hull, pattern recognition, shape description, image analysis, discrete geometry, mathematical morphology, algorithms, half-plane closing

DOI: 10.3233/FI-2000-411205

Citation: Fundamenta Informaticae, vol. 41, no. 1-2, pp. 131-146, 2000

Authors: Serra, Jean

Article Type: Research Article

Abstract: Classically, connectivity is a topological notion for sets, often introduced by means of arcs. An algebraic definition, called connection, has been proposed by Serra to extend the notion of connectivity to complete sup-generated lattices. A connection turns out to be characterized by a family of openings parameterized by the sup-generators, which partition each element of the lattice into maximal components. Starting from a first connection, several others may be constructed; e.g., by applying dilations. The present paper applies this theory to numerical functions. Every connection leads to segmenting the support of the function under study into regions. Inside each region, …the function is ρ-continuous, for a modulus of continuity ρ given a priori, and characteristic of the connection. However, the segmentation is not unique, and may be particularized by other considerations (self-duality, large or low number of point components, etc.). These variants are introduced by means of examples for three different connections: flat zone connections, jump connections, and smooth path connections. They turn out to provide remarkable segmentations, depending only on a few parameters. In the last section, some morphological filters are described, based on flat zone connections, namely openings by reconstruction, flattenings and levelings. Show more

Keywords: complete lattices, connected operators, connectivity, flattenings, grain operators, levelings, mathematical morphology, segmentation

DOI: 10.3233/FI-2000-411206

Citation: Fundamenta Informaticae, vol. 41, no. 1-2, pp. 147-186, 2000

Authors: Roerdink, Jos B.T.M. | Meijster, Arnold

Article Type: Research Article

Abstract: The watershed transform is the method of choice for image segmentation in the field of mathematical morphology. We present a critical review of several definitions of the watershed transform and the associated sequential algorithms, and discuss various issues which often cause confusion in the literature. The need to distinguish between definition, algorithm specification and algorithm implementation is pointed out. Various examples are given which illustrate differences between watershed transforms based on different definitions and/or implementations. The second part of the paper surveys approaches for parallel implementation of sequential watershed algorithms.

Keywords: mathematical morphology, parallel implementation, sequential algorithms, watershed definition, watershed transform

DOI: 10.3233/FI-2000-411207

Citation: Fundamenta Informaticae, vol. 41, no. 1-2, pp. 187-228, 2000

Authors: Barrera, J. | Terada, R. | Hirata Jr., R. | Hirata, N.S.T.

Article Type: Research Article

Abstract: An important aspect of mathematical morphology is the description of complete lattice operators by a formal language, the Morphological Language (ML), whose vocabulary is composed of infimum, supremum, dilations, erosions, anti-dilations and anti-erosions. This language is complete (i.e., it can represent any complete lattice operator) and expressive (i.e., many useful operators can be represented as phrases with relatively few words). Since the sixties special machines, the Morphological Machines (MMachs), have been built to implement the ML restricted to the lattices of binary and gray-scale images. However, designing useful MMach programs is not an elementary task. Recently, much research effort has …been addressed to automate the programming of MMachs. The goal of the different approaches for this problem is to find suitable knowledge representation formalisms to describe transformations over geometric structures and to translate them automatically into MMach programs by computational systems. We present here the central ideas of an approach based on the representation of transformations by collections of observed-ideal pairs of images and the estimation of suitable operators from these data. In this approach, the estimation of operators is based on statistical optimization or, equivalently, on a branch of Machine Learning Theory known as PAC Learning. These operators are generated as standard form morphological operators that may be simplified (i.e., transformed into equivalent morphological operators that use fewer vocabulary words) by syntactical transformations. Show more

Keywords: mathematical morphology, operator decomposition, PAC learning

DOI: 10.3233/FI-2000-411208

Citation: Fundamenta Informaticae, vol. 41, no. 1-2, pp. 229-258, 2000