There has recently been essential theoretical development in the analysis of the statistical properties of morphological filters. In this paper we present a short summary of these results and analyze theoretically different characteristics of the effects of noise. These include output expectations and variances for different types of noise and signals. We also present a comprehensive experimental analysis based on extensive simulations of the effects of the shape and the size of the structuring set.

Morphological opening operations are useful in discriminating between lengths of sequences of non-zero signal amid a zero-valued background in a signal. In order to study simple one-dimensional detection algorithms involving openings, we would like to know how a finite-extent stochastic signal changes when it is opened with a convex, zero-height structuring element. Because the opening operation is nonlinear and the model signal has some spatial structure due to its finite extent, the opened model signal is not spatially stationary. This nonstationarity is dealt with by introducing the concept of the translation class1 of signal elements to distinguish the different distributions of those elements in the opened signal. The signal height distribution for a given translation class of an opened signal is derived using an extension of the method given by Stevenson and Arce in [2] to evaluate morphological operations on infinite-length sequences.

Treating a binary image as a random process results in the granulometric pattern spectrum being a random function and its moments being random variables. Because these moments are used as image signatures and as local texture descriptors, their statistical distributions, and in particular their moments, are of importance. The present paper employs a theorem of Cramer to show for a certain class of image models that the pattern-spectrum-moment distributions are asymptotically normal, and it provides asymptotic expressions for moments of the spectrum moments. To facilitate application of Cramer's theory the paper introduces the class of orthogonal granulometric generators.

We consider digital binary images as realizations of a bounded discrete random set, a mathematical object which can be defined directly on a finite lattice. In this setting, we show that it is possible to move between two equivalent probabilistic model specifications. We formulate a restricted version of the discrete-case analog of a Boolean random set model, obtain its probability mass function, and employ some methods of Morphological image analysis to derive tools for its statistical inference.

In this paper, Mathematical Morphology (M.M.) foundations as an algebraic, topological and geometrical theory are recalled within both a deterministic and a stochastic framework. Some new developments such as morphological filtering, Boolean model, topographical distance and fuzzy measurements, ifiustrate the relevance of these mathematical foundations. Starting from the notion of hierarchical process, we define a stochastic morphology and develop the concept of stochastic morphological operators. The example of the stochastic averaging operator is presented and its equivalence with simulated annealing stated. Moreover, we introduce stochastic operators based on specific energy functionals and show that they allow to consider statistical and soft morphologies as limiting or special cases of stochastic morphology.

There are various fuzzy morphologies (Minkowski algebras), these depending on the particular fuzzifification of set inclusion that is employed for the definition of erosion. Set-inclusion fuzzification depends upon the choice of an indicator for set inclusion and, based upon a collection of nine axioms, a class of indicators results such that each indicator in the class yields a Minkowski algebra in which a certain core of the ordinary propositions typically associated with mathematical morphology are valid. By going a bit further and postulating a certain mathematical form for the indicator, one obtains fitting characterizations for the basic operators. In ordinary crisp-set binary morphology, certain fundamental representation theorems hold, specifically the Matheron representations for increasing, translation invariant mappings and for T-openings. The definition of a T-opening extends for fuzzy T-openings. There is also a weakened version of the Matheron kernel representation for increasing, translation invariant mappings.

A method for combining fuzzy morphological operations with fuzzy logic operations in a heterogeneous network structure is described. The first layer of the network would consist of template operations. The other layers would perform decision making. Such a network could be used to perform classification, image processing functions, and computer vision tasks. Generalized template operations are defmed using image algebra. It is shown that fuzzy morphological operations and linear operations can be obtained from the generalized operations by suitable choices of parameters. Training rules are described that can be used to "learn" the parameters of the generalized operations in a fashion similar to standard backpropagation. Thus, the network could learn linear or morphological operations, or a combination of the two.

Work is underway on a rule—based expert system as the basis of an intelligent user interface for detecting arbitrary 2D shapes in images using mathematical morphology. This work builds on work done at the Ecole des Mines,1 and at the University of Washington,2 and is applicable to a wide range of vision tasks, including arbitrary shape detection, separation and segmentation problems. We address these tasks by defining an intermediate lexicon of 2D shape detection tasks, that can be carried out using the primitive operations of mathematical morphology. The expert system carries out a rule-based consultation with the user in order to express his vision task in terms of this lexicon. The graphical user interface prompts the user with textual or graphical menus, and at the end of the consultation, the system then generates the sequence of operations needed to accomplish the task.

The hit-or-miss operator is used as the building block ofoptimal morphological restoration filters. Using the conditional expectation in a binary setting, filter design methodologies are given for general, maximum, and minimum noise environments, the latter two producing optimal thinning and thickening filters, respectively. Unions ofhit-or-miss transforms are expressed as canonical logical sums ofproducts. The final hit-or-miss templates are obtained by logic reduction.

Morphological sequences (algorithms or programs) are generated using an evolutionary approach. A population of morphological sequences is manipulated and expanded in discrete steps. At each time-step two tasks are initiated--program discovery and program construction. The discovery phase searches for short morphological sequences which extract novel features. Program composition utilizes these sequences, which are partial solutions, to form increasingly effective sequences. The composition phase selects pairs of sequences and combines them into extended sequences which capture spatial relationships. The enhanced population serves as the basis for another phase of discovery and composition. Several demonstrations illustrate the system's ability to synthesize and integrate feature extraction routines.

Artificial neural networks have proven to be quite useful for a variety of different applications. A recent addition to the arena of neural networks, morphology neural networks use a morphology-like operation as their basic nodal calculation, instead of the usual linear operation. Several morphology neural nets have been developed, and lattice-type learning rules have been used to train these networks. In this paper, we present a different kind of learning rule for morphology neural nets that is based on the simulated annealing algorithm. Simulated annealing has been applied to many different areas involving optimization.

Image algebra as a mathematical structure provides a much broader framework of neural computing. The matrix product in the basic equations of the current linear-based neural networks are furnished by the generalized matrix product obtaining new computational models as morphological neural networks (MNN). In this paper we propose a theoretic approach on the invariant perception. We also show that image algebra can be used not only in the field of image processing but in other areas related to artificial perception systems. Our study is based on both a general theory of neural network and the invariant perception by the cortex theory. The neural structures that we propose uphold both the architecture and functionality of the cortex. We present a neural network model for computing auditory homothetic invariances in accordance with a general framework in image algebra. The neuronal synthesis of this model is obtain using MNN theory with the binary operations the maximum and the multiplication in the neural network formulation. We also propose a second model which is achieved introducing a simple logarithmic transformation in the current model. In addition we propose an alternative MNN for computing homothetic invariances which arise from how the problems are formulated in the systems of artificial vision. This last neural network is appropriate to compute visual invariances when we process patterns defined in two dimension spaces.

The Image Algebra Algorithm Development Environment provides the user with a portable, flexible, and comprehensive environment for the development and exercise of computer vision algorithms. It includes a powerful set of tools which provides the user with specific algorithmic capabilities that are tied together to form an environment through the use of common file formats, programming language and an underlying environment manager. The environmental makes use of the Image Algebra Ada language, translator, and run-time capability. Its major components include two X Window System based tools: one provides an image display and analysis capability, and the other provides a graphical interface for defining invariant image algebra templates. As well as supporting the development of programs using translators, compilers and libraries of routines, the Algorithm Development Environment includes an Image Algebra Ada Interpreter that allows the user to interactively developed algorithms in a rapid prototyping environment. This paper gives an overview of the various components of the Algorithm Development Environment.

An important research problem in image processing is to find appropriate tools to support algorithm development. There have been efforts to build algorithm development support systems for image algebra in several languages, but these systems still have the disadvantage of the time consuming algorithm development style associated with compilation-oriented programming. This paper starts with a description of the Run-Time Support Library (RTSL), which serves as the base for executing programs on both the Image Algebra Ada Translator (IAAT) and Image Algebra Ada Interpreter (IAAI). A presentation on the current status of IAAT and its capabilities is followed by a brief introduction to the utilization of the Image Display Manager (IDM) for image manipulation and analysis. We then discuss in detail the current development stage of IAAI and its relation with RTSL and IDM. The last section describes the design of a syntax-directed graphical user interface for IAAI. We close with an analysis of the current performance of IAAI, and future trends are discussed. Appendix A gives a brief introduction to Image Algebra (IA), and in Appendix B the reader is presented to the Image Algebra Ada (IAA) grammar.

The proposed architecture is a logical design specifically for image algebra and other matrix related operations. The design is a fine grain SIMD concept consisting of three tightly coupled components: a spatial configuration processor, a weighting processor (point-wise), and an accumulation processor (point-wise). The flow of data and image processing operations are directed by a control buffer and pipe lined to each of the three processing components. The low-level abstraction of the proposed computational system is founded on the mathematical principle of discrete convolution and its geometrical decomposition. This geometrical decomposition combined with array processing requires redefining specific algebraic operations and reorganizing their order of parsing in the abstract syntax. The logical data flow of such an abstraction leads to a division of operations, those defined by point-wise operations, the others in terms of spatial configuration. The effect of this particular decomposition allows convolution type operations to be computed strictly as a function of the number of elements in the template (mask, filter, etc.) instead of the number of picture elements in the image. The potential utility of this architectural design lies in its ability to provide order statistic filtering and all the arithmetic and logic operations of the image algebra's generalized matrix product. The generalized matrix product is the most powerful fundamental formulation in the algebra, thus allowing a wide range of applications.

Our problem is to find an efficient pattern-matching method in two dimensions in order to solve a puzzle automatically. The contours of the objects must first be coded in order to be analyzed. A contour descriptor code that is quite invariant to rotation, translation, and scaling of the original object is proposed. It is an extension of the Freeman and Shape Descriptor codes. The code is based on approximating the contour by linear segments and arcs. A robust segmentation method to cut up the contour in pieces well adapted to the approximation is needed. Such a method is proposed here, namely one that segments a puzzle piece in four sides using a Hough-transform based algorithm. The roughly linear segments forming each side are detected by the transform in order to detect the frontiers of each side. Each contour piece is then encoded using the before mentioned code. The resulting database of all the piece's side codes will be used in combination with morphological features, extracted from the contour codes using morphological operators, to detect pieces sharing a common side and assemble them automatically.

An algorithm for integrating images has been published recently. It is shown that the obtained integral is the inverse of the half-morphological gradient: (1) integration followed by derivation yields the initial image, and (2) derivation followed by integration yields the initial image and appropriate limit conditions. Examples of applications are given.

In this paper, we propose a robust and accurate method for segmenting grayscale images of corneal endothelial tissue. Its first step consists of the extraction of markers of the corneal cells using a dome extractor based on morphological grayscale reconstruction. Then, marker- driven watershed segmentation yields binary images of the corneal cell network. From these images, we derive histograms of the cell sizes and number of neighbors, which provide quantitative information about the condition of the cornea. We also construct the neighborhood graph of the corneal cells, whose granulometric analysis yields information on the distribution of cells with large number of neighbors in the tissue. Lastly, these results help us propose a model for the corneal cell death phenomenon. The numerical simulation of this model exhibits a very good match with our experimental results. This model not only allows us to refine our understanding of the phenomenon: combined with our results, it enables the estimation of the percentage of cells having died in a given corneal endothelial tissue.

In previous work, an hierarchical system for shape classification based on morphological techniques was developed. A major concern, however, was the lack of a fast and accurate morphological algorithm for calculating the convex hull of an object, an important step in the classification process. Presented here are an overview of the classification system to date and several different convex hull algorithms designed to overcome these problems.

The classes of the equicontinuous functions from a metric space E into an ecart lattice T offer a remarkably consistent theoretical framework to morphological operations. It is proved that in the case of robust lattices, they are closed under sup and inf, with exceptional properties of continuity in addition. Special attention is paid to the cases when T is totally ordered (e.g., R or Z), and to the (finite or not) products of this case, i.e., to multispectral and/or motion images modelling.

An important aspect of mathematical morphology is the description of set mappings by the use of a formal language, called here the morphological language (ML), whose vocabulary are erosions, dilations, anti-erosions, anti-dilations, infimum and supremum. Since the sixties, special machines, the Morphological maChines (MC), have been built to efficiently perform this language. These machines have proved to be very useful by solving hundreds of image analysis problems. A natural question that arises is: what class of mappings are phrases of the ML? Now, we can answer this question precisely. In 1991, Banon and Barrera proved that any translation-invariant (TI) mapping can be decomposed as the supremum of sup-generating mappings (the infimum of an erosion and an anti-dilation), with structuring elements that are extremities of closed set intervals contained in the kernel. Adding the hypothesis of upper semi-continuity (USC), they simplified the result by taking a minimal subcollection of sup- generating mappings. Now, we follow the same idea and generalize the concept of kernel, in order to state that any set mapping (non necessarily TI) can be built in a MC. We present decompositions for set mappings in terms of sets of (non-TI) sup-generating mappings, defined from the generalized kernels. Under the USC hypothesis, we also arrive to minimal decompositions. Some examples illustrate the main results.

The purpose of this paper is to present a radically new image transform, called the Minimax Eigenvector Decomposition (MED) transform. This novel transform is based on the minimax product of two matrices and is an analogue of the Singular Value Decomposition (SVD) transform of linear algebra. In comparison to the SVD transform, in the MED transform eigenvalues need not be computed as they turn out to be zero. Furthermore, computation of eigenvectors is trivial. This makes the use of the MED transform more desirable as the major problem associated with the SVD transform is the computation of the singular values and eigenvectors. These are computationally extensive and often lead to significant numerical errors.

Ganulometries are defined on function classes over topological vector spaces. The usual Euclidean property for scaling compatibility, set scaling in the binary case and graph scaling in the gray-scale case, is changed so that it is with respect to spatial (domain) scaling for function spaces. As in the binary case, scaling compatible granulometries possess representations as double suprema over scaled generating elements. Without further constraint on the generating elements, the double supremum involves, for each generating element, all scalings exceeding the parameter of the particular granulometric operator. The salient theorem of the present paper concerns necessary and sufficient conditions under which there is a reduction of the double-supremum representation to a single supremum over singularly scaled generating functions. Specifically, and in the context of locally convex topological vector spaces, there is a determination of when a domain-scaled function t*f is f-open for all t < 1 . Key roles are played by both topology and local convexity.

On a grey level image, extrema correspond to zones of uniform altitude whose neighboring pixels have a strictly lower (maxima) or strictly higher (minima) altitude. If an image is seen as a relief, minima are located at the bottom of valleys or pits (structures darker than the background) and maxima are located at the top of plateaus, pics, or domes (structures lighter than the background). The detection of extrema is often used as the first step of a segmentation process when we just need to roughly located objects of interest. Unfortunately, the noise sensitivity of this transformation makes it uneasy to use. We propose in this paper a transformation which valuates the extrema on a contrast criterion: the dynamics. The selection of the minima of interest is easier with this contrast information. The dynamics is a measure at the scale of the structure. It does not characterize the extremum itself or its catchment basin but the structure containing the extremum. An original aspect of the dynamics is that this transformation does not consider the size and the shape of the structures. We do not need to know a priori the size of the structures to evaluate their contrast. That is not the case for contrast feature extraction like the top-hat transformation. The computation of the dynamics is not straight forward from its definition. We propose a technique of computation based on flooding simulations. Using last algorithmical developments, this implementation is particularly efficient. That will help to develop the use of the promising transformations based on the dynamics.

We present a unifying approach for the morphological processing of image sequences. The mathematical tool that we choose to work with is lattice theory. Lattice theory allows us to introduce two different, in general, approaches to the problem of morphologically processing image sequences. The first approach formalizes and generalizes the vector approach suggested by Wilson. The second approach is new and extends the vector ideas, proposed by Astola, Haavisto, and Neuvo, regarding median filtering.

In this paper a class of morphological filters acting on moving targets is introduced. The aim is to reduce noise such as impulsive noise that may occur at any stage of a communication system. Good and well known classical techniques, such as median filtering, already exist to enhance images corrupted by impulsive noise. The common problem with the use of these techniques for still and moving images is that they generally blur the image. Contours and fine structures present in the image may be gravely affected or even lost. The proposed method is a three-dimensional morphological filter based on the temporal connectivity of image sequences. Additional spatial morphological filters have been used to improve the performance in sequences with high motion or high density of noise. Results are presented that show how the filters act for suppressing impulsive noise and the high resolution obtained in the filtered image sequences.

A gray level image in N dimensions can be mapped into an N + 3-dimensional binary space called a floating stack array. The three added dimensions are a stack decomposition, a neighborhood window, and a stack decomposition of a kernel associated with that window. All popular linear and nonlinear translation invariant operators can be represented as a sequence of projections and cross-sections of the floating stack array along various hyperplanes. The operators that can be represented include 2- and 3-dimensional morphology, gray level hit- and-miss transforms, rank order filters, generalized rank order filters, convolutions, and neural networks on an image space.

Pebble_Pond performs morphologically-based wave propagation on an input set of points on the plane, with the points corresponding to the locations of detected image features. The waves are allowed to pass through each other, resulting in an complex evolving state space from which can be obtained a diverse class of non-planar spatial measures and structures, e.g., all k nearest neighbors, k-th order Voronoi tessellations, and k-th order Gabriel graphs. One perspective on Pebble_Pond is that it takes spatial structure and transforms it into temporal structure. That is, at each iteration in the wave propagation, measures on the state space reflect spatial structure at the scale corresponding to the current iteration. Thus, at each iteration all measures obtained (in parallel) from the state space report on all spatial relations falling within the distance that the waves have propagated. This paper investigates particular measures of the underlying state space that provide a rotation and scale invariant signature of the spatial relationship between planar points. Also, based on preliminary data, the signature is robust with respect to spurious points, i.e., spatial commonalities are preserved amongst the differences. The measures are based upon the formation of an evolving grey-scale surface which corresponds to the cardinality of the intersection of the point wave sources. The centroids of the local maxima of these intersection surfaces are used as normalizing origins from which to plot the relative angles of nearby wave front crossings. The signature plots the relative angles of wave crossings (with respect to their local maxima centroids) that evolve over time as local maxima regions arise and combine to form new local maxima regions.

We illustrate a cooperation between Voronoi diagram and Mathematical Morphology in 2-D and 3-D. Domains of application are multiple: 2-D image segmentation, and 3-D image representation, cellular sociology in 2-D and 3-D. The principal tool that we use is the algorithm of research of connected components in a graph abiding by constraints. The originality takes place in the choice of the constraint parameters. Other tools are used: binary dilation, labeling, and influence zone on graphs. The graph support of our work is the Voronoi diagram, well known for its power of modelling for natural reality. The dual graph of this space partition is the Delaunay graph containing all the neighboring information. The first developed application concerns a method for 2-D and 3-D images segmentation. We have elaborated tools to measure intra-graph structures distance, search of connected component under constraints to extract a 3-d object included in a volume data. The second application we developed concerns the theory of cellular sociology where the set of points identified the location of cells. Our method makes it possible to determine for a given set of cells, a model including its nearest homogeneous set, and the intrinsic disorder to which it refers. In this paper, our methods will be discussed and illustrated in the biological domain.

A common perception among researchers who are only superficially acquainted with image algebra is that although convolutions and morphological operations are easily expressible in the language of image algebra, higher level image operations, such as structural descriptions of scene content, are outside the realm of image algebra. The purpose of this paper is to dispel this perception by providing examples of structural descriptions of images using image algebra. Specifically, we present structural descriptions such as adjacency and inclusion relationships between regions of regionally-segmented images and quadtree representation of binary images, and show how these can be concisely expressed in image algebra.

The hit-or-miss operator is used as the building block ofoptimal morphological restoration filters. Using the conditional expectation in a binary setting, filter design methodologies are given for general, maximum, and minimum noise environments, the latter two producing optimal thinning and thickening filters, respectively. Unions ofhit-or-miss transforms are expressed as canonical logical sums ofproducts. The final hit-or-miss templates are obtained by logic reduction.

In this paper, the invertibility of the morphological representation of binary images is investigated. We provide necessary and sufficient conditions for the exact reconstruction of a binary image from its morphological representation. The necessary and sufficient conditions obtained are given by a restriction defined in terms of the morphological thining transformation. Subsequently, sufficient conditions, for the exact reconstruction of a binary image from its morphological representation, given by a direct restriction on the morphological thining transformation, are determined. Additionally, we derive necessary conditions, for the exact reconstruction of a binary image from its morphological representation, given by a direct restriction on the morphological thining transformation.

When one starts to learn mathematical morphology, binary morphology techniques generally appear early on the menu. they are often viewed as somewhat more basic than, and a good introduction to, more complicated items used in gray-level morphology. However, mathematical morphology, being based on topology, is very deeply rooted in the binary world, which is more full of surprise than one would think. Segmenting overlapping convex particles in binary images, which means separating them from each other, is one of the older problems in binary morphology. It has often been investigated in past works in very different contexts, using such tools as ultimate erosions, skeletons, conditional bisectors, and reconstruction by watershed lines, to name a few. Although well suited to a large number of applications, these techniques often lead to oversegmentation when there is a wide range in the dimension of the overlapping particles. In this paper we present a new method to overcome this problem based on the concept of weighted skeletons. We will apply it to a real-world problem: the separation of man-made vitreous fibers embedded in resin, for which it was originally developed. The first section refreshes our memory on the fundamental tools that will be used in the second section, where we present some binary segmentation methods based on ultimate erosions and related problems. The third section presents our proposed method and its results.

This report presents a technique of decomposing an arbitrary binary image into the union of rectangles so that the number of rectangles becomes as small as possible. This decomposition is referred as adaptive rectangular decomposition. Decomposing a binary image into objects with a same basic shape but with different sizes is familiar as morphological skeleton decomposition. To implement adaptive rectangular decomposition, we generalize the discrete version of morphological skeleton decomposition by replacing a sequences of disks {nB}, n equals 0,1, (DOT)(DOT)(DOT) with a structuring element sequence {B_n}, where B_n equals B_n-1 (direct sum) G_n-1 and G_n is called a generator. A good selection of each generator in a generator sequence {G_n} makes a compact representation of a given binary image. In adaptive rectangular decomposition, we restrict each generator G_n by one of only two objects; the vertical 2-pixel line V and the horizontal 2-pixel line H. The adaptive rectangular decomposition algorithm selects the best sequence {G_n} using dynamic programming (DP) technique. In some experiments, we compared adaptive rectangular decomposition with other types of decomposition in the viewpoint of the time cost of morphological operations by decomposed structuring elements (decomposed binary images). Experimental results show that the time cost of the operations by the structuring elements represented by adaptive rectangular decompositions is smaller than the case of other types of decompositions.

Binary images of machine-printed characters are essentially graphical objects composed of nodes (extremes, intersections) and lines connecting them. Provided distinction is made between straight lines and curves, this is a fair representation of individual characters. Only a few carefully located pixels convey the most significant part of the information concerning the curvature of the path connecting two nodes. These pixels may be thought of as additional nodes connected by straight lines in a graph that represents the machine-printed character. In this paper, a character is represented by nodes (character extremes, intersections and additional nodes replacing curves) and straight lines connecting them. This graphical object carries two kinds of information about the character that is represented: geometric information concerning the location of nodes with the relative length and orientation of the connecting lines, and the topological information about the existing connections between different pairs of nodes given by the connectivity matrix or a corresponding graph. Due to its geometric properties, this object can be used for character recognition by template matching, which is insensitive to broken characters caused by missing (or parasite) pixels. On the other hand, its graph, as a mathematical object, can be used for structure based optical character recognition, so that the character can be recognized under wide variations in character styles. Combining template matching of graphs as geometric objects with spectral distance of graphs meant as sets of relations between nodes and edges, seems to be a promising way to achieve high accuracy multifont character recognition. The procedure to obtain the graph representation of machine-printed characters is based on morphological processing of their binary images.

While the Fast Fourier Transform (FFT) is frequently used to efficiently implement a shift invariant convolution operator, it is of little use in implementing a variant operator which is to be evaluated at only selected locations in the image. The analysis of efficient implementation of a special class of circular-arc convolution operators found useful in the analysis of echocardiographic images leads to the observation that a much wider class of arc-like operators can also be approximated by the sum of a small number of invariant operators. While the immediate application is analyzed for the 3 X 3 computing environment, the techniques are general.