This paper presents a new image decomposition scheme that utilizes coding of convex hulls corresponding to a set of order statistic filters. The encoding of convex hulls can be done more efficiently than the encoding of the original image, especially when the boundaries of the encoded set are rough.

In the field of computer vision, multiscale analysis has received much attention in the past decade. In particular, Gaussian scale space has been studied extensively and has proven to be effective in multiscale analysis. Recent research has shown that morphological openings or openings or closings with isotropic structuring elements such as disks define a scale space, where the radius of a disk r is the scale parameter which changes continuously from 0 to infinity. The behaviors of objects described by the morphological scale space provide strong knowledge for multiscale analysis. Based on the theory of morphological scale space, we address in this paper the two fundamental problems in multiscale analysis: (1) how to select proper scale parameters for various applications, and (2) how to integrate the information filtered at multiscales. We propose two algorithms, binary morphological multiscale analysis (BMMA) and gray-scale morphological multiscale analysis (GMMA), for extracting desired regions from binary and gray images.

This paper deals with size-sensitive multiresolution decomposition using adaptive morphological filters with a flat structuring element. This type of decomposition generates a set of images, each containing elements of the original image with a specific size. The authors propose to extract a set of dominant shapes contained in the original image and to assess the size of a particular element by comparison with this set of dominant shapes. This approach is particularly suitable for texture images where dominant shapes are actually present. In a first step, it is shown how a flat structuring element of a morphological filter can be adapted to optimize a statistical criterion such as the mean square error. The approach is suitable for any morphological filters and the proposed algorithms are simple. Moreover, they can be easily modified to achieve a size-constrained optimization of the structuring element, which is an attractive solution for the extraction of dominant shapes. Finally,adaptive morphological filters are used in a multiresolution decomposition scheme which sorts the various components as a function of their size while taking into account the presence of dominant shapes. Two particular applications are presented. They address the problems of noise removal and texture defect detection.

A class of shift-variant reduction operations is introduced, that is useful for performing efficient and controllable shape and texture transformations between resolution levels. In their most general form, the operations proceed in three steps: (a) convolve a binary image with a kernel of arbitrary size; (b) threshold the result; (c) subsample to produce the reduced image. Taking a binary structuring element for the kernel, the threshold convolution on a binary image is equivalent to a rank order filter, and the full reduction operation is a threshold reduction. Threshold reductions that use convolution filters and subsample tiles of equal size are optimized by combining the three operations, using only logical raster operations and producing threshold convolution values only at the sampling points. For 2x reduction, the four possible threshold values (1, 2, 3, and 4) refer to the minimum number of ON pixels within each 2x2 tile for which a pixel in the reduced image will be ON. Algorithms for boolean raster operations are given for 2x, 3x, and 4x threshold reduction, and lookup tables that efficiently implement column raster operations are provided. Threshold reduction rates of 2.5x10⁷ pixel/second can be achieved with a Sun SparcStation2^TM . A maskforming image analysis cycle of threshold reduction, augmented by morphology and followed by replicative expansion to full resolution, is described, and some general properties of the cycle are derived. A simple application of threshold reduction to document image analysis, the extraction of halftone regions from scanned images that also contain text and line graphics, is illustrated. A sequence of 2x reductions with first low and then high thresholds is used to create a reduced image consisting of a mask over the halftone regions. In this way, the extraction occurs as a natural consequence of the reductions.

The classes of the equicontinuous functions from a metric space E into a metric lattice F offer a remarkably self-consistent theoretical framework to morphological operations. It is proved that in the case of robust lattices, they are closed under the Sup and Inf. A comprehensive class of dilations and erosions is continuous, as well as their combinations. Finally, when E = Rn, Minkowski and (more generally) translation invariant operators may be introduced.

If the concept of Euclidean and geodesic distance is of great importance in binary mathematical morphology (MM), the grey-level MM deals mainly with neighborhood configuration analysis. This paper presents a novel approach to grey-level MM based on the concept of the distance function relative to topographical surfaces. By introducing the notions of connection cost and deviation cost, we define the topographical and differential distances and develop a powerful theoretical framework for establishing the equivalence between the two fundamental notions of skeleton by influence zones and watershed: the SKIZ of the set of the minima of a grey-level image f with respect to the differential distance function is exactly the watershed of f. This leads to a duality between binary and grey-level images as well as new fast algorithms for computing the SKIZ and the watershed.

The concept of a deformable (active) marker of an image, defined as a numerical marker whose support is limited by a deformable (active) contour, is introduced. An active marker is specified by defining (1) an interface deformable model as well as the deformation process associated with it, and (2) an interaction process between the marker and the external field. We present a particular active marker model relying on a novel expanding-contracting inhomogeneous membrane/thin-plate model called a g-snake, and an interaction process based on controlled morphological marking techniques. We show that by allowing the external force field to be simplified and taking into account a global source of information, active markers provide a consistent solution to three major problems encountered by active contour models when applied to the segmentation of highly noisy images: (1) sensitivity to initialization, (2) undesirable attractions by non-significant localized or regionalized zones in the image, and (3) no relationship between their state of equilibrium and the real contours to be extracted. The efficiency and robustness of the method are demonstrated on ultrasound medical images.

The notion of a heterogeneous matrix product is developed. After defining this product, the authors show how it generalizes the common matrix and vector products of linear algebra as well as the generalized forward and backward convolutions of image algebra. Some specific examples are provided.

Image Algebra Ada (IAA) is a superset of the Ada programming language designed to support use of the Air Force Armament Laboratory's image algebra in the development of computer vision application programs. The IAA language differs from other computer vision languages is several respects. It is machine independent, and an IAA translator has been implemented in the military standard Ada language. Its image operands and operations can be used to program a range of both low- and high-level vision algorithms. This paper provides an overview of the image algebra constructs supported in IAA and describes the embodiment of these constructs in the IAA extension of Ada. Examples showing the use of IAA for a range of computer vision tasks are given. The design of IAA as a superset of Ada and the implementation of the initial translator in Ada represent critical choices. The authors discuss the reasoning behind these choices as well as the benefits and drawbacks associated with them. Implementation strategies associated with the use of Ada as an implementation language for IAA are also discussed. While one can look on IAA as a program design language (PDL) for specifying Ada programs, it is useful to consider IAA as a separate language superset of Ada. This admits the possibility of directly translating IAA for implementation on special purpose architectures. This paper explores strategies for porting IAA to various architectures and notes the critical language and implementation features for porting to different architectures.

Hardware technology advances have dramatically reduced the cost of image computation for machine vision; unfortunately, machine vision software technology has not kept pace. This paper presents OLIVE, an object-oriented language for machine vision and image processing, intended to make it easier to develop efficient, portable applications. First, OLIVE's principal object types are defined -- IMAGEs and LOCUSes (abstractions of point sets and geometric entities) -- and their corresponding operations, including the use of LOCUSes as generalized indexes for IMAGEs. Next, a hardware architecture that simplifies the implementation while enhancing performance is discussed. Finally, the authors compare the IMAGE/LOCUS objects to the IMAGE/TEMPLATE objects of the image algebra proposed by Ritter,Wilson and Davidson.

The development of a preprocessor for image algebra on the MasPar computer, a SIMD processor array, is discussed. One of the parallel languages used on the MasPar is MPL, a parallel version of the programming language C. This machine and language were chosen because of the close correspondence between MPL and image algebra and, as a result, MPL is easily extended to include image algebra. The preprocessor consists of three primary components: the lexical analyzer, the parser, and the code generator. The lexical analyzer converts the input stream into tokens the parser recognizes. The parser checks the program for syntax errors.The code generator produces MPL source code which is then compiled and run on the MasPar. The architecture of the MasPar computer is reviewed, and in particular the structures used for routing data through the array are examined. The parallel language MPL is also reviewed, with attention given to the methods in which the extensions to C in MPL interact with the MasPar architecture. The close correspondence between MPL and image algebra is specifically discussed. The authors present the structure and development of the image algebra preprocessor, including possible future extensions. Examples of image algebra preprocessor code and the corresponding MPL code produced by the preprocessor are given.

A hybrid, electro-optical image processing system capable of interpreting image algebra operations is presented. The classical, Vander Lugt optical system provides a basis for architectural discussion; however, it is anticipated that newer and more compact systems will provide the realization. Distribution of image algebra operations over the proposed system is the implementation. Linear and nonlinear algebraic system operations are shown to be obtainable using optical convolution and cross-correlation procedures.

Template decomposition plays an important role in image processing algorithm optimization and parallel image processing. In this paper, a template decomposition technique based on the factorization of max-polynomials is presented. A morphological template may be represented by a max-polynomial, a notation used in combinatorial optimization. The problem of decomposition of a morphological template is thus reduced to the problem of factorization of the corresponding max-polynomial. A sufficient condition for decomposing a one-dimensional morphological template into a set of two-point templates is established. Once the condition is satisfied, the construction of the decomposition is straightforward. A general procedure is also given for testing whether such a decomposition exists for an arbitrary one-dimensional morphological template.

The family of real-valued circulant templates on nXm rectangular images is isomorphic to a quotient ring of the ring of real polynomials in two variables. Template decomposition is equivalent to factoring the corresponding polynomial. Template invertibility corresponds to polynomial invertibility in the quotient ring. Factoring and inverting are more difficult for polynomials in two variables than for those in one. Hexagonally sampled images have properties which simplify these operations. Hexagons organize themselves naturally into a hierarchy of snowflake-shaped regions. These tile the plane and consequently yield a simple definition of circulancy. Unlike the circulancy of rectangles in the plane, which yields a toroidal topology, the hexagonal analogue yields the topology of a circle. As a result, circulant templates are mapped isomorphically into a quotient of the ring of polynomials in one variable. These polynomials are products of linear factors over the complex numbers. A polynomial will be invertible in the quotient ring whenever each of its linear factors is invertible. This results in a simple criterion for template invertibility.

Methods are presented for the decomposition of two-dimensional von Neumann-like convolution operators into sums and products of smaller von Neumann-like operators. Consequences of the techniques include the face that ever second-order operator is the sum and product of five or fewer first-order operators. A totally symmetric second-order operator can be written as the sum and product of three or fewer first-order operators. In general, an nth-order von Neumann-like operator can always be written as the sum and product of three lower order operators. The following inversion result is also discussed. If the (circulant) von Neumann mean filter operator is defined on a square coordinate set with n rows and n columns, then it fails to be invertible only if either the integer 5 divides n or the integer 6 divides n. This result provides a partial solution to a question posed by P. Gader.

This paper presents an application of morphology neural networks to a template learning problem. Morphology neural networks are a nonlinear version of the familiar artificial neural networks. Typically, an artificial neural net is used to solve pattern classification problems One useful characterization of many neural network algorithms is the ability to 'learn' to respond correctly to new data based only on a selection of known data responses. For example, in the multilayer perceptron model, the 'learning' is a procedure whereby parameters are fed back from output to input neurons and the weights changed to give a better response. The morphological neural net in this paper solves a different type of image processing problem. Specifically, given an input image and an output image which corresponds to a dilated version of the input, one would like to determine what template produced the output. The problem corresponds to teaching the network to solve for the weights in a morphological net, as the weights are the template's values. A reasonable method has been investigated for the boolean case; in this paper results are presented for gray scale images. Image algebra has been shown to provide a succinct expression of neural networks algorithms and also to allow a generalization of neural networks, and thus the authors describe the algorithm in image algebra. The remainder of the paper gives a brief discussion of image algebra, the relationship of image algebra and neural networks, a recap of the dilation morphology neural network boolean for boolean images, and the generalization to grayscale data.

A very robust form of pattern recognition results from using mathematical morphology on binary images that have been segmented into various edge directions. These edge direction images are then transformed by a set of structuring elements to derive a set of feature images. Morphological transformations on the feature images by a final set of structuring elements result in the location or classification of the desired objects. Thus, there are two types of structuring element sets. The training of the final set of structuring elements can be provided by a method similar to supervised Hebbian learning used in neural networks, where the goal is to unambiguously locate specified objects. The first set of structuring elements is similar to a hidden layer in neural networks and is more difficult to train. A technique of unsupervised competitive learning is used. The definition of orthogonality, or uniqueness within the set of features defined by the first layer of erosions is crucial to successful training. These features must be independent and span the space of possible features; otherwise, information that may be critical to the final layer of erosions will be lost. This paper will concetrate on a technique for unsupervised learning of hidden layers of structuring elements where a training image is inspected with very little input as to what will be done with the image.

When considering ways to automate the generation of image processing algorithms for object recognition tasks, one critical element is the availability of measures to assess the potential and actual ability of individual operations for making a set of desired discriminations. This paper discusses the analysis and evaluation of grey-level image processing operators or algorithms from the perspective of trying to search automatically through a large space of them for one which satisfactorily performs a given recognition or discrimination task. Performance of an operator may be expressed in terms of accuracy, consistency, and cost, over an entire set of training images.The major issues of evaluating and choosing between operators in this context are discussed, and examples are given of measures which can be used to evaluate classes of operators for applicability, or to evaluate individual operators or parameter settings for actual performance. The paper first describes the form of the analysis for binary morphological operators, and then shows how it may be directly extended to grey-level morphological operators. Several examples are provided to show how grey-level pixel sets may be discriminated on the basis of various combinations of grey level and spatial criteria, as calculated by the basic morphological operators of erosion, dilation, opening, and closing.

This paper is an investigation into the use of genetic algorithm techniques for doing optimal feature set selection in order to discriminate large sets of characters. Human experts defined a set of over 900 features from many different classes which could be used to help discriminate different characters from a chosen character set. Each of the features was assigned a cost, based on the average amount of CPU time necessary to compute it for a typical character. The goal of the task was to find the subset of features which produced the best trade-off between recognition accuracy and computational cost. The authors were able to show that by using all of the features or even major classes of them, high rates of discrimination accuracy for a printed character set (above 98% correct, first choice) could be obtained. Application of the genetic algorithm to selected subsets of characters and features demonstrated the ability of the method to significantly reduce the computational cost of the classification system and maintain or increase accuracy from the case where a complete set of features was used.

An image representation is developed that is useful for designing optimal morphological filters to restore images suffering from degradation due to subtractive noise. The image and noise models are predicated on the existence of some class of shape primitives into which both image and noise can be decomposed (relative to union). Both deterministic and nondeterministic cases are considered, and in each case the relevant model constraints are fully discussed. The type of filters that are naturally compatible with the image-noise models are analyzed, and the relation to general mean-square morphological optimization is explored.

For both the binary and gray scales, mean-square optimal digital morphological filters have been fully characterized previously in terms of the Matheron erosion representation for increasing, translation-invariant mappings. Included in the characterization is the minimal search strategy for the optimal filter basis; nonetheless, in the absence of prior statistical information or an adequate image-noise model, even in the binary setting design is computationally intractable for moderately sized observation windows.The computational burden can be mitigated by imposing constraints on the filter. The present paper is mainly concerned with the development of structuring-element libraries to which the basis search can be confined. More specifically, the authors focus on the expert-library approach: various sublibraries are formed, each of which corresponds to certain key filters, the overall library is formed as the union of the sublibraries, and a suboptimal filter is derived from image-noise statistics in conjunction with a basis search restricted to relevant sublibraries.

An algorithm is described for estimating the weights of gray-scale templates used for morphological feature detection. The problem of finding optimal templates for object detection is formulated as a statistical estimation problem. The problem is solved using a gradient descent algorithm. This procedure is applied to the problem of detecting trucks in simulated SAR imagery. Good performance is achieved with 22 of 24 trucks being identified in a test set and no false alarms.

New morphological operations, called soft morphological operations, are introduced. They maintain most of the properties of standard morphological operations, yet give improved performance under certain conditions. The main difference to standard morphological operations is that soft morphological operations are less sensitive to additive noise and to small variations in the shape of the objects to be filtered.

Basic morphological operations can be incorporated within a statistical physics formulation as a limit when the temperature of the system tends to zero. These operations can then be expressed in terms of finding minimum variance estimators of probability distributions. It enables one to relate these operations to alternative Bayesian or Markovian approaches to image analysis. It is shown how to derive elementary dilations (winner-take-all) and erosions (loser-take-all). These operations, referred to as statistical dilations and erosion, depend on a temperature parameter (beta) equals 1/T. They become purely morphological as (beta) goes to infinity and purely linear averages as (beta) goes to 0. Experimental results are given for a range of intermediate values of (beta) . Concatenations of elementary operations can be naturally expressed by stringing together conditional probability distributions, each corresponding to the original operations, thus yielding statistical openings and closings. Techniques are given for computing the minimal variance estimators.

In the framework of mathematical morphology, we study in two particular cases how morphological measurements characterize a set. The first one concerns the geometrical covariogram and we show that in the generic polygonal (non necessarily convex) case, the geometrical covariogram is characteristic up to a translation and reflection about the origin. The second one concerns the surface area of the dilation by compacts. We show that in the random case, the mean value of the measurements allows a characterization up to a random translation. In the deterministic case the theorem holds. Procedures to retrieve the original set from its measurements is given in both cases.

Two of the most important basic morphological operations used in image filtering are erosion and dilation. In this paper the authors consider the case when a finite image is part of a pixel display which changes ate discrete times. Taking advantage of the fact that not all pixels will change from time t to time t + 1, they develop two important algorithms for computing the dilation and erosion of such images in o(n2) less time then with brute force. These results hold also for translation and rotation and can be extended to opening and closing of images by structuring elements. These results are also extended to images which contain multi-uncertain values, that is, the extended fuzzy pointing set. The advantages of these fast operations are obvious in on-the-fly image processing schemes such as real-time filtering of images.

This paper describes a two-dimensional target tracking system model and the image algebra specification of its algorithm. The visual tracking process in this model is divided into four subprocesses. Each target is abstracted as a parametrically described closed curve and the neighboring points of the curve. A description of the two-space motion of a target is obtained from the parameters defining the curve in sequential image frames, while curve construction and occlusion detection are accomplished using neighboring points of curve approximations from previous frames. The curve approximation is based on fitting the two-dimensional target boundary contour and is implemented as an error minimization problem. The simplest form of curve considered is an ellipse, but the target descriptions can be made more robust by adding more parameters as needed to describe more complex curves. The parameters of the curves identified in previous frames can be used as constraints in the error minimization process when occlusion is detected. The model can be applied to different types of targets by applying type-specific boundary estimation methods to each target's approximate boundary region. The image algebra description of this algorithm is concise and inherently parallel. This image algebra algorithm specification is of interest because it represents a complex vision activity rather than a simple filtering operation. In particular, the algorithm manipulates many small subimage regions specified by computing their point sets and gives a description of targets as a result, as is typical of vision algorithms. The implementation of the algorithm is described and its performance on a microcomputer vision system is characterized by giving two real-time tracking systems: a two-dimensional block tracking system and one that tracks human faces.

The use of the optical hit-or-miss (HOM) morphological operation for target detection in automatic target detection (ATR) imagery is considered. Formal gray-scale morphology can be implemented with a number of binary morphological operations. Each binary morphological operation can be implemented on a binary optical correlator at very high speeds with very large structuring elements (SEs). A modified HOM algorithm is advanced and demonstrated on ATR gray-scale imagery for target detection. The algorithm is very attractive for implementation on a binary optical correlator.

The authors have developed a morphological technique, based on geodesic dilation using fast propagation of regional maxima, for segmenting the skin, bone, and dura from 3-D MR studies of the head, exposing the outer surface of the brain for 3-D rendering. The proposed algorithm for segmentation belongs to the class of connectivity segmentation techniques and uses morphological gray scale reconstruction and the distance function to discriminate connections by their width. By following only the connections wider than a critical dimension, the connectivity does not extend outside of the brain through nerves and other small paths connecting the brain to other tissues. On an IBM 6000 RISC workstation, the entire segmentation process takes less than three seconds per slice. With the volume segmented, we render the brain using a modification of the rendering process proposed by Michael Bomans and Karl-Heinz Hohn for visualizing poorly defined surfaces such as the sulci of the brain. The modification uses a depth map transformation that permits replacing the compute-intensive 3-D closing with the rolling ball applied in 2-D. This method also eliminates the need to maintain two separate volumes for the rendering process.

Range images provide an explicit encoding of the shape and the geometric structure of the objects in the image from the point of view of the sensor. Morphological operators are ideally suited for analysis of range images due to their inherently geometric nature. Most morphological edge operators meant for intensity images are concerned only with jump and ramp edges and not with crease and roof edges. Since roof and crease edges do not correspond to depth discontinuity, such operators cannot be used to detect these edges in range images. In this paper, edge detection schemes for range images based on morphological operations are presented. It is shown that by a suitable choice of the structuring element, selective crease and roof edges can be extracted, and by using multiple structuring elements oriented in different directions, directional sensitivity to edge detection can be incorporated. Several examples of morphological edge detection in range images are presented.

Secondary electron microscope images of silicon carbide particles in aluminum metal matrix composites show that many of the particles appear in clusters. In order to determine the stiffness of the material, microstructural characteristics such as orientation and percentage area of the particles have to be evaluated. To facilitate this, the connectivity among the various particles has to be broken. Three algorithms have been developed that are fairly successful in separating the particles. The results of the three methods are compared with a manual method of separating the particles in images.