The classical notion of a stack, or flat, operator on numerical functions is extended to functions on a complete lattice T. This implies to introduce cross sections of such functions, and also anamorphoses. The two theorems which characterize function operators from flat primitives, and their commutability under anamorphosis are then proved. An application to color images is presented.

In mathematical morphology, we are led to study the evolution of morphological tubes. By using some appropriate notions of set- valued analysis, viability theory and non-smooth analysis, this paper provides differential inclusions which govern these tubes.

In this paper, we investigate the morphological bounds on order- statistics (median) filters (and their repeated iterations). Conditions are derived for morphological openings and closing to serve as bounds (lower and upper, respectively) on order- statistics (median) filters (and their repeated iterations). Under various assumptions, morphological open-closings (open- close-openings) and close-openings (close-open-closings) are also shown to serve as (tighter) bounds (lower and upper, respectively) on iterations of order-statistics (median) filters. Conditions for the convergence of iterations of order-statistics (median) filters are proposed. Criteria for the morphological characterization of roots of order-statistics (median) filters are also proposed.

The present paper formulates increasing, translation-invariant filter design for the subtractive-noise restoration problem in terms of the classical boundary-value-problem paradigm. The boundary-value problem involves both operator relations and invariant (fixed-point) boundary conditions. A design approach is formulated that derives the morphological basis expansion directly from the statement of the boundary-value problem. Solutions are found that possess both minimal bases and minimal structuring elements.

The concept of dimensionality has been introduced in image analysis to assess the validity of image measurements. In this paper, we extend the notion of dimensionality to image operators and present formal definitions for a dimensional operator. We make a distinction between dimensional operators for unknown image plane scalings and dimensional operators for unknown intensity axis scalings. A dimensional operator is an operator that commutes with these scalings. Morphological operators are then reviewed to determine whether they are dimensional. Finally, we show that new dimensionality problems arise when the image plane itself has inhomogeneous units. This lead us to define dimensional image operators for image plane anamorphosis (i.e., stretching or shrinking of the image plane in one direction). Multivariate histograms are typical n-dimensional images whose image plane is not homogeneous. It is shown that some clustering techniques applied to these histograms encounter dimensionality problems.

We discuss a number of issues related to the morphological analysis of random shape by means of discrete random set theory. Our purpose here is twofold. First, we would like to demonstrate that, in the discrete case, a number of problems associated with random set theory can be effectively solved. Furthermore, we would like to establish a direct relationship between discrete random sets and binary random fields. To accomplish this, we first introduce the cumulative distribution and capacity functionals of a discrete random set, and review their properties. Under a natural assumption, we show that there exists a one-to-one correspondence between the probability mass function of a discrete binary random field and the cumulative distribution functional of the corresponding discrete random set. The cumulative distribution and capacity functionals are then related to higher-order moments of a discrete binary random field. We show that there exists a direct relationship between the capacity functional of a discrete random set and the capacity functional of the discrete random set obtained by means of dilation, erosion, opening, or closing. These relationships allow us to derive an interesting result, regarding the statistical behavior of elementary morphological filters. Finally, we introduce moments for discrete random sets, and show that the class of opening-based discrete size distributions are higher-order moments of a discrete random set. This last observation allows us to argue that discrete size distributions are good statistical summaries for shape.

Decomposition of morphological structure element in hexagon lattice will be discussed in the paper by using the results proposed for decomposition in square lattice. Some important theoretical results on geometry of the decomposition, singularity, compatibility, and decomposability, etc. will be presented. Based on them, methodology for decomposition will be proposed, including approximate decomposition, correction of singularity, and so on. These results are general for all kinds of decompositions. As applications of the theory, several practical decomposing system in hexagon lattice, including 1D, points-pair, quasi 1D (points-pair), and that into neighborhood configurations will be analyzed theoretically, and efficient decomposing algorithms will be provided.

Clutter in an image is non local noise, and is difficult to classify and train statistically. It may not be possible to distinguish clutter from a pattern of interest using low level processing in a small neighborhood. This paper presents a method for filtering out clutter from an image by developing a local model of the pattern of interest and not the noise. A filter is constructed that is guaranteed to pass that pattern. Noise will not be passed if it is sufficiently different than that pattern. The filter to be developed in this paper is called a vector opening.

Computational mathematical morphology was developed to provide a unified framework for the design of optimal filters: gray-scale- to-gray-scale, gray-scale-to-binary, and binary-to-binary. The present paper provides as representation for the mean-absolute error of increasing filters in terms of the errors resulting from single-erosion filters. It also provides a recursive form of the representation that can be employed in a computer search algorithm to find optimal filters, in particular, optimal restoration filters.

Speckle together with usual additive noises cause severe degradation of Synthetic Aperture Radar (SAR) images. Spatial averaging is the commonly used technique for removing speckle noise. However, this technique reduces image resolution appreciably and as a result the image is blurred. Morphological closings and openings offer a better way to reduce the speckle noise without blurring the image. In this paper we have introduced new operators to remove dark or bright spots which can not fit inside the boundary of a convex 2D structuring element. Any region that can not fit inside the boundary is preserved. A multiscale filtering process is required to remove noise spots of different sizes. While using samples images for processing at higher scales, a preprocessing is required before the sampling to retain important image features that may be lost in sampling. Finally, the paper presents an algorithm that ensures that no distortion is introduced in the final image as a result of intermediate sampling and reconstruction steps. We have used this algorithm to filter the noise in SAR images obtained at different wavelengths. The present technique is remarkably more successful in restoring complex image details than either spatial averaging or morphological filtering using median operators.

This paper presents an automated methodology for selecting morphological filters from a given set that will most improve a text image for character recognition. Toward this end, a classifier is described which generates an internal representation of the image qualities affecting readability, and which uses those properties to identify images that will benefit by application of a particular filter. In the study, handprint and machineprint character bitmaps are taken from binarized document images and enhanced using a set of non-recursive neighborhood operators. Features related to the connected components and their morphology are extracted prior to the filtering step. Character recognition results are obtained from commercially available recognition engines, which together with the measured morphological features, form a training set for statistical classifiers. The classifiers derive a partitioning of the input based on the morphological features, and the output yields an indication of the specific filter most appropriate to apply to improve character recognition. Results are presented for handprinted ZIP code digit images, and for average to poor quality and dot matrix alphanumeric machineprint obtained from postal application images. Performance for each case is statistically analyzed.

A novel method for optimal shape description based on the multiresolution morphological image processing is presented in this paper. The method is optimal in the sense that the optimal structuring element is determined that will enable best discrimination of object shapes. In this method a representation based on the areas of the input binary image successively eroded by multiple rotated structuring elements at different resolutions is used. For a given set of model shapes the optimal structuring element is selected by a means of genetic algorithm. The optimization criteria is formulated to enable a robust shape matching. Experiments have been performed on a set of model shapes. Genetic algorithm was used to create new generations of structuring elements by crossing over the genes which represent structuring elements. The result of the iterative procedure is the optimal structuring element which was used for shape description using the morphological signature transform. The proposed optimal shape representation method is applied to the problem of shape matching which evolves in many object recognition applications. Here, an unknown object from the input image is matched to a set of known objects in order to classify it into one of finite number of possible classes. Experimental results are presented and discussed.

This paper is but a first step toward a fast, robust, nonarithmetic filtering theory. The following will assume the sampled sequence is from a finite TOS (totally ordered set) S so that any subset (window) of sequence values may be ordered. In addition we will assume the existence of a distance function (metric) on S. This distance function may be as simple as counting but all results presented hold for any TOS with any distance function. In addition a median type operator will be defined that always has as output an element in S, unlike the usual median operator. Implementations will be discussed. It will be shown that implementation involves only a two layer NAND/NOR for ordering and range estimations, and the assumption of counting. Operation counts will be discussed.

In this work we present a classical morphological tool, granulometry, and a practical application on medical images, pneumoconiosis classification. The radiologist diagnose on these images is based on a preattentive discrimination process of the textural patterns appearing at the pulmonar parenchyma. Thus, in order to automatize this classification we have chosen a tool which agrees with perceptual theories of Computer Vision on texture discrimination. Our work is centered, concretely, on the perceptual models based on texton theory. These works base texture discrimination on differences in density of texton attributes. We link this approach with a morphological tool, granulometry, as a helpful multi-scale analysis of image particles. The granulometric measure provides a density function of a given feature, which depends on the family of algebraic openings selected. Thus in this paper we defined different granulometries which allow us to measure the main texton features, such as, shape, size, orientation or contrast, proposing a granulometric analysis as a systematic tool for texture discrimination according to a perceptual theory. And finally, we present the application of measuring size density on some radiographic images suffering from pneumoconiosis.

The Euclidean granulometries are generalized to allow the introduction of a positive increasing function h(t), as the scalar multiplier instead of t in the granulometry ((Psi) _t). A rather general result for the k^th pattern spectrum moment is derived. For polynomial choice of h^-1(t), the asymptotic expressions for the mean and variance of the pattern spectrum moments can be obtained and the asymptotic distribution can be shown to be normal. For other choices, the asymptotic expressions for the mean and variance are shown to provide excellent agreement with simulated pattern spectra, but the asymptotic distribution is not known.

The principle of shape recognition by using granulometries, is to transform a binary planar shape into a curve which is translation, rotation and scale invariant by a family of morphological transformations depending on the size of the structuring element. This paper presents a fast algorithm for the computation of the anti-granulometry by closings which avoids boundary effects. This algorithm is based on a simple geometric transformation called the `Steiner Inverse Transform', on which original theoretical results are given.

The use of statistical pattern recognition techniques in image processing has led to simplifying assumptions on the statistical interdependence of the pixel value of an image, which allow theoretical analysis and/or computational implementation to be achieved. For instance, the assumption of statistical independence of the values or that their joint distributions are multivariate normal, simplifies the analysis enormously. However, these results are very limiting in representing models for data, and do not allow for analysis of arbitrary spatial dependencies, in the data. One method for modeling two-dimensional data on a lattice array has been developed by Abend et al. called the Markov mesh model, and is a generalization of the familiar 1D Markov chain. The Markov mesh model allows the use of a class of spatial dependencies that is popular in many 2D data processing schemes, including image processing. One advantage of using this model is that it allows a computationally attractive implementation of statistical procedures involving joint and conditional probabilities. In this paper, we generalize Abend et al.'s results to a more comprehensive model, which we call the Markov pyramid model, using the concept of partial ordering. We present the necessary background for this model and show that Abend's model is a special case of our model. Finally, we present a simple application of our results to texture modeling.

Statistical Morphology is concerned with the statistical characterization of the four morphological operations — dilation, erosion, opening and closing. By statistical characterization of a morphological operator we mean the statistical characterization of the output in terms of the statistical characteristics of the input. Characterization of operators allows us to predict the characteristics of the output of an algorithm composed of a sequence of morphological operations in terms of the statistical characteristics of the input and the sequence of morphological operators used. Furthermore, such statistical analyses of morphological algorithms is necessary for evaluating the algorithm's performance. In this paper we describe what we have learned about one way to characterize the dilation and opening morphological operators in a one dimensional setting. That is, the input to each of these operators is assumed to be binary one-dimensional. The input is modeled as a union of randomly translated discrete lines of a fixed length. The line segments can overlap and result in line segments of various lengths. Thus the final output appears as an unordered pattern of lines and gaps of various lengths. This input is characterized by giving its line and gap length distribution and the distribution of the number of line and gap segments of various lengths. The characterization of a morphological operator, therefore, entails a similar characterization of the output. There has been a recent interest in the area of statistical morphology and some results have been published in the literature. Morales and Acharya {MA92} analyzed the statistical characteristics of a morphological opening on grayscale signals perturbed by Gaussian noise. Stevenson and Arce {SA92] studied the effects of opening for a class of structuring elements. Atola, Koskinen and Neuvo [ALN93] studied the output distributions of one dimensional grayscale filtering. Costa and Haralick {CH92} came up with an empirical description of the output graylevel distributions of morphologically opened signals. Dougherty and Loce [DL93] used libraries of structuring elements to restore corrupted signals in the case when a noise model is available. In the following section we set up the notation and definitions used in this paper. In section 3 we give a formal statement of the random process used to generate random sequences. In section 4 we give a maximum likelihood algorithm for estimating the model parameters. The four morphological operators are characterized in section 5.

In this paper the concept of rank selection probabilities of stack filters is reviewed. If they are known then the output distribution for i.i.d. input follows easily. Amazingly simple connections between different forms of output distribution based on rank selection probabilities and other quantities are derived. These connections lead also to a dramatically faster (O(2^N)) algorithm for finding the rank selection probabilities compared to the traditional (O(N

A general paradigm for lifting binary morphological algorithms to fuzzy algorithms is employed to construct fuzzy versions of several standard morphological operations. The lifting procedure is based upon an epistemological interpretation of both image and filter fuzzifications. Algorithms are discussed for the following image processing tasks: shape detection, edge detection, and filtering union noise.

Human visual perception treats images at different resolution levels. Multiscale analysis tries to simulate this behavior by including the image in a mono-parametric family of images generated out of the first and called scale-space image. The purpose of multiscale analysis is to extract information from the original image features, studying their behavior through various scale levels. In a review of multiscale bibliography, one realizes that the two most studied features of the image are blobs and edges. This paper presents a new methodology, based on the use of tools provided by Mathematical Morphology, applied to scale-space image feature tracing. This methodology is here intended to solve two concrete problems: edge detection and depth perception of it.

Engineering-based edge detection techniques generally use local intensity information to identify whether a pixel location is part of a boundary. Boundaries are presumed present where sharp transitions in the observed intensities occur. Unfortunately, these approaches are sensitive to error and hidden partial boundaries, which hinder the determination of closed object boundaries. In this research, a method to obtain statistically optimal closed object boundaries is presented.

In this paper, we review a number of pyramidal image decomposition techniques for image representation and compression. We argue that the design of an efficient pyramidal image decomposition procedure is directly related to the design of an optimal (non-linear in general) image predictor. However, determining such a predictor is not possible in general. To alleviate this problem, we propose four natural constraints, which uniquely identify the `optimal' predictor as being a morphological opening. This choice naturally leads to a morphological pyramidal image decomposition algorithm recently proposed by Heijmans and Toet. Experimental analysis, allows us to study six pyramidal image decomposition techniques, and demonstrate the superiority (in terms of compression performance and computational simplicity) of the Heijmans-Toet algorithm.

The most common form for representing digital images is the rectangular matrix where each member of the matrix is a picture element. In a small neighborhood of the image plane, there is a finite number of elements and so a topology of finite sets is needed for digital images. The concepts of digital topology provide for finite sets, but they are not perfect solutions. Problems exist in the connectivity definitions for the object and the background and in the fact that boundaries can be represented by four different sets which are either inner or outer connected and either four or eight connected.

In this paper a morphological features extraction algorithm referred to as a morphological scanning edge detector (MSED) is presented. MSED consists of three cascaded processes which are filtering, detecting and scanning. First, a robust morphological filtering process is used to reduce noise in the image without disrupting the edge structures. Then, in the detecting process, two intermediate images are derived by manipulating the filtered image morphologically; one is the difference between dilation and closing, and the other is the difference between opening and erosion. Finally, from these two images, edge positions and strength are located and marked using a scanning process. This scanning process involves the proper selection of thresholding values for feature enhancement. MSED treats various signal features such as step, ramp, ridge, corner, and junction differently. Hence a tailored scanning process can be designed to detect a particular structure. Experimental results are provided to show the effectiveness of the MSED in detecting different image features.

Binary image component labeling is a fundamental process in image processing and computer vision. This paper presents several image component labeling algorithms with local operators expressed in the language of image algebra. These algorithms are then analyzed for their time and space complexities.

Image algebra has been implemented in a variety of programming languages designed specifically to support the development of image processing and computer vision programs. Our current work involves the implementation of a class library, iac++, that supports image algebra programming in C++. The paper discusses the relation of the iac++ class library to previous implementations of image algebra. The paper assumes a rudimentary knowledge of C++ and object oriented programming, but reviews the concepts critical to explanation of image algebra implementation issues. The image algebra is implemented by a group of C++ classes providing objects corresponding to points in n-dimensional Real And Integer Cartesian product spaces, homogeneous sets of points over these spaces, images over those point sets, and templates mapping points into images. Both point sets and images can comprise objects that are represented as data structures--the more common view--or as functions--which introduces a variety of capabilities unavailable with the data structure view. The paper also introduces the use of iterator classes for processing all elements of a point set or all pixels in an image or template.

The logical architecture for this effort was developed at Wright Laboratory. Oak Ridge National Laboratory has taken the design and reordered the data flow to allow a physical architecture to be prototypes using DSP chips, transputers, or VLSI. The design allows image algebra operations to be executed in a staged pipeline at nearly the same throughput as a memory to memory transfer. The control is by direct memory access from the host, in this case a SUN SPARC II. Reduce operations such as sum, maximum, and minimum are captured as by-products of the pipeline operation.

This paper deals with the notion of connected operators in the context of mathematical morphology. In the case of gray level functions, the flat zones over a space E are defined as the largest connected components of E on which the function is constant (a flat zone may be reduced to a single point). Hence, the flat zones of every function make a partition of the space. A connected operator acting on a function is a mapping which enlarges the partition of the space created by the flat zones of the functions. In this paper, it is shown that, from any connected operator acting on sets, one can construct a connected operator for functions. Then, the concept of pyramid is introduced and one of the most important results of this study is that, if a pyramid is based on connected operators, the flat zones of the functions increase with the level of the pyramid. In other words, the flat zones are nested. Then, a very important class of connected filter called `filter by reconstruction' is defined and its properties are stated and discussed. Rules to create pyramids relying on filters by reconstruction are proposed.

Weighted order statistic filters form an important subclass of stack filters, i.e. filters which are defined by threshold decomposition and positive Boolean function. In this paper we present an efficient algorithm based on fast conjunctive matrix transforms for converting a weighted order statistic filter into a stack filter.

A common challenge in many image analysis applications is the segmentation of the data into objects of interest (foreground) and background. Typically, the contrast of the data and the background greylevel varies across the image, thereby requiring some form of normalization prior to a threshold step. Previous morphological techniques for data normalization have been quite successful. These approaches include the `rolling ball' of Sternberg and the `top hat' of Serra. These techniques are particularly effective for patterns of interest that are spaced relatively far apart compared to their width. In contrast, the algorithm introduced in this paper is applicable to closely spaced thin broken lines on a highly variable background. Using a combination of greyscale morphology and conditional masking of image data, the approach is shown to be highly robust for closely spaced foreground/background patterns.