The three commonly used high-level image-template operations provided by the image algebra are the generalized convolution the additive maximum or generalized lattice convolution and the multiplicative maximum These are used to realize various nonrecursive image transformations e. g. DFT edge detection and morphological operations. Along with nonrecursive transformations a class of recursive transformations are also widely used in signal and image processing e. g. hR filters sequential block labeling predictive coding etc. . In this paper a couple of new recursive operations are introduced which allow the image algebra to express a set of linear and nonlinear recursive transformations. Algebraic properties of these recursive operations are given which provide a mathematical basis for recursive template composition and decomposition. Also some applications of recursive operations in image processing are presented.

A digital moving-average filter with nonnegative mask weights that sum to unity is a gray-scale morphological filter. As such it possesses a representation as a maximum of erosions over its morphological basis. The present paper investigates the special properties of the digital movingaverage morphological basis these properties being for the most part combinatoric in nature. Shapes of digital structuring elements are related to the filter weights by means of shape classes. This is accomplished by defining a characteristic of a signal relative to the filter weights and then characterizing basis elements by means of the characteristic. The notion of shape is then extended to a more general class of morphological filters. The concept of a morphological quasi-average is introduced and the power of such filters to approximate morphological filters is addressed.

In image algebra '' the concept of a coordinate set X is general in that such a set is simply a subset of ndimensional Euclidean space . The standard applications in 2-dimensional image processing use coordinate sets which are rectangular arrays X 72 x ZZm. However some applications may require other geometries for the coordinate set. We look at three such related applications in the context of image algebra. The first application is the modeling of photoreceptors in primate retinas. These receptors are inhomogeneously distributed on the retina. The largest receptor density occurs in the center of the fovea and decreases radially outwards. One can construct a hexagonal tessellation of the retina such that each hexagon contains approximately the same number of receptors. The resulting tessellation called a sunflower heart2 consists of concentric rings of hexagons whose sizes increase as the radius of the ring increases. The second application is the modeling of the primary visual . The neurons are assumed to be uniformly distributed as a regular hexagonal lattice. Cortical neural image coding is modeled by a recursive convolution of the retinal neural image using a special set of filters. The third application involves analysis of a hexagonally-tessellated image where the pixel resolution is variable .

Affine signal transformations are useful for modeling self-similar structures in fractal images and shape deformations in visual motion. In the first part of this paper a theoretical framework, called affine morphology, is developed to analyze parallel and serial superpositions of affine image transformations. Affine morphology unifies and extends translation-invariant morphological image transformations and their rotation/scaling-invariant generalizations by using action of affine groups on lattices. Several theoretical aspects of affine morphology are explored for binary images. In the second part of the paper, the affine transformations are extended to gray-level images and arbitrary signals, and affine models are developed by using a sum superposition of affine signal transformations. A solution is then given to the problem of estimating the parameters of this sum-affine model using least squares algorithms, and some applications are outlined for image and speech signal processing.

The current concept of mathematical morphology involves erosions and dilations using structuring elements and will be called scalar morphology in this paper. Scalar morphology can be extended to a matrix morphology formalism by the unusual idea that each matrix element is a set in EN space. An image matrix is an array of separate images and a structuring element matrix is defined to be an array where each component is a structuring element. Dilations or erosions of a matrix of images by a matrix of structuring elements consist of a number of dilations or erosions of various image components with structuring element components. The rules of matrix operations will tell which image components are transformed by which structuring element components and how the results are combined into a new array. Set unions and intersections are analogous to matrix addition. All non-increasing transformations can be described as a matrix erosion followed by a dilation inner product. Applications using scalar morphology can consist of a sequence of operations where several intermediate images are generated and recombined in various ways to eventually give a final result. These intermediate images can represent different features. Specific combinations of features in certain configurations can provide an identification or location of an object. It turns out that sequences of this type that consist of a multiplicity of operations on a multiplicity of images fit very well into the

Morphological operators have been ued extensively for description of shapes of binary objects. Often it involves ''probing'' the object with different structuring elements and establishing a degree of similarity with each of these. The skeleton of an image has been used as an effective shape descriptor. In this paper an ''absolutely disjoint skeleton'' has been defined. Decomposition of an image in terms of such a skeleton allows us to define a ''skeleton spectrum''. Finally a shape descriptor has been devised which allows to rank similarity in shape of a given image with respect to a set of structuring elements. Results have been presented for two sample images.

This paper presents a general methodology for picture segmentation using tools provided by mathematical morphology. This methodology is based on the marking of the objects to be segmented. The marking (using techniques which may differ according to the kind of picture to be analyzed) provides a " marker set" which is used to modify the gradient of the image. This modification using geodesic image reconstruction produces a new gradient image. The main characteristic of this modified gradient is that its minima exactly fit the various connected components of the " marker set" . In a second step a morphological transform called " watersheds" is performed on this gradient image. The watershed transform produces a partition of the image into homogeneous regions called " catchment basins" . Every catchment basin contains only one marker and its boundary corresponds to the pixels of the image where the contrast is locally maximum. Thus the transformed image exhibits the contours of the marked objects. Some examples illustrate the use of this process when objects marking is not too complex. Then we extend this method to situations where the marking step is not obvious and we show how the watershed transform together with the simplification of the image can provide efficient tools for detecting homogeneous regions in an image.

The analysis of some topological properties of the skeleton in the continuous plane leads us to propose a definition of the digital skeleton. The framework which is developed permits to define and to construct other related remarkable subsets of sets or functions : minimal skeletons conditional bisectors perceptual graphs watershed lines.

This paper defines several classes of morphological band-pass operations and discusses their importance with respect to the problem of automatically generating recognition algorithms. It is argued that for reasons of analytical efficiency the band-pass operators are better candidates for primitives in an automatic programming system than are the more basic morphological or image algebraic operators from which they are customarily derived. The bandpass operators are more powerful and compact they make the algorithm development process much easier and they avoid making redundant measurements on images for different but closely related operations. The classes of morphological band-pass operators defined in the paper include those based on erosion and opening of binary images which classify pixels in terms of size or distance as well as others based on dilation closing conditional erosion and conditional dilation along with some of their grey-level counterparts. In addition attention is drawn to a more parsimonious definition for the residues of extensive morphology operations (both binary and grey) which allows them to retain the extensive property and to retain symmetry with their anti-extensive counterparts in contrast to the more common definitions that are currently in use. It is shown that the alternative definitions of these operators are essential for defining band-pass operators for them which in turn is crucial to their employment in automatic algorithm generation systems.

The morphological operations of a hit-miss transform opening and closing are generalized in a number of ways. The new operations have been applied to a variety of binary image analysis problems that involve pattern detection and reconstruction. Generalized openings are developed by replacing erosions with hit-miss transforms. These new openings are shown to be anti-extensive idempotent and center-independent. Similarly generalized closings are developed and related to openings by duality. Additionally the hit-miss transform is further generalized by replacing the erosions with blur and rank order transforms in order to improve the robustness of pattern matches. The set of invariance properties of these new transforms can be widened by forming generalized openings from them.

Use of granulometric size distributions to generate features for binary images was first studied by Matheron. Of late the method has been employed for numerous purposes including analysis of particle dispersion analysis of texture and image segmentation. Fundamental to the Matheron theory is his characterization of the most important class of granulometries the Euclidean granulometries. This characterization takes place in the context of his fundamental representation theorem for general binary tau-openings. The present paper provides a full extension of the Matheron theory of Euclidean granulometries to the gray scale.

Mathematical morphology provides a geometric approach to image processing and pattern recognition. One important task in AM/FM conversion process is the recognition of various geometric objects in a utility map. In this paper, the AM/FM conversion process and the difficulties involved are briefly discussed. The application of morphological operators to utility map for shape recognition is presented. The comparison and relationship to the classical recognition techniques such as template matching and Hough transform are examined.

A closed-loop hybrid learning system that facilitates the automatic design of a multi-class pattern recognition system is described. The design process has three phases: feature detector generation feature set selection and classification. In the first phase a large population of feature detectors based on morphological erosion and hit-or-miss operators is generated randomly. From this population an optimized subset of features is selected using a novel application of genetic algorithms. The selected features are then used to initialize a generalized Hamming neural network that performs image classification. This network provides the means for self-organizing the set of training patterns into additional subclasses this in turn dynamically alters the number of detectors and the size of the neural network. The design process uses system errors to gradually refine the set of feature vectors used in the classification subsystem. We describe an experiment in which the hybrid learning paradigm successfully generates a machine that distinguishes ten classes of handprinted numerical characters.

A family of asteroids the Apollos have orbits which cross that of the earth. Most of these bodies are small and have low reflectivity making detection difficult. A telescope of modest size equipped with a charge-coupled device (CCD) can be used to search for these objects which will inevitably sirike the earth. The destructive power of a small Apollo asteroid 200m in diameter would be on the order of 1 gigaton causing severe global damage. It is important to find and track these objects so that their numbers and orbits may be accurately determined. The discovery process is typically done by human comparison of time skewed images. Two photographic plates are aligned by hand on a blink comparator which animates the images by alternating light sources. Once a moving object has been found its celestial coordinates on each image are calculated. This process is repeated with other images to determine an orbit. These orbital elements are then compared with the elements of known objects which exist in machine readable form. This paper examines algorithms stated in Air Force Image Algebra which facilitate automation of this process and discusses issues relative to conducting a fast search for such objects. These techniques are also appropriate for detection of comets or any moving extraterrestrial body.

A primary task which must be accomplished by mobile robots is that of self-location or position determination. This task should utilize all available sensors which can supply useful information and must be able to combine that information in a way which minimizes uncertainty. One such method for combining this information is presented in this paper. It is based on using morphological operators on sets representing the environment with structuring elements representing the sensor readings. This method applies to those situations where the environment is known and can be represented by sets of 2 dimensional geometric objects. I.

The goal of CAE is to form a real object from the model. Thus the NC-programming is an important phase in manufacturing. Several requirements have to be met with the NC-programs. For example the tools have to be selected as large as possible and the path of the tool has to be selected to be minimum while the speed of the tool should be as high as possible. Also extra moves should be avoided. When the structure is complicated these requirements are often meat only partially. In most of the CAE-programs the path of a tool is calculated from the surface model or from the volume model. In this paper an approach that utilizes three dimensional morphological filters is presented. In fact the tool can be used as the kernel of the filter according to which the original block of material is eroded. The morphological operations are done to the voxel image generated from the CAE-model. The computation for the generation of the path is fast. Also the requirements for the speed of the tool and accuracy of the path can be meat.

In binary image processing digital erosion has been used successfully for the removal of small sporadic elements from images at the sacrifice of losing edge detail in objects of interest. Typically an erosion operation is followed by a dilation process generating the familiar opening operation. This step which attempts to restore the original edge information works well in many applications where the edge detail of the original object is unimportant. In this paper a conditional digital erosion operation designed specifically for the processing of inherently noisy magnetic resonance (MR) images of the lower spine is presented. This operation in essence preforms a test for the removal of entire objects prior to the erosion. The method was applied to edge enhanced images and resulted in the elimination of edges of insufficient span regardless of their thickness or absolute length. The developed method has proven useful for the removal of sporadic noise and the retention of small anatomic edge boundaries in edge enhanced MR images of the lower spine. The results of images processed with the operator favorably compare with those obtained from morphological (Minkowski) open and close operations.

The requirements of high resolution electron microscopy in the field of digital image processing are presented. The suitability of a particular image algebra for expressing the operations required in electron image processing is assessed. It is argued that complex image values should be more fully incorporated.

Morphological operations suit well to be used in the three-dimensional microscopy. In this paper an approuch to extract cytoskeletal proteins of a Confocal Scanning Laser Microscope images is introduced. In the results the position of fibres fit well to those position that a man might propose. In the procedure only quite simple operations are needed.

A deformation-tolerant method of rectifying imagery distorted by refraction at an arbitrarily-corrugated ocean surface is presented which employs spatial transformations expressed in terms of the Image Algebra (IA). Derived from concepts of set theory and functional mapping inherent in abstract mathematics the IA exhibits advantages of clear concise formulation and inherent parallelism. In this study a ray-tracing model of ocean optical propagation is derived from physical relationships among optical system parameters sea surface topography and sensed object features. Theory specific to extraction of sea topography via LIDAR (lightwave radar) is presented. Additionally a method is proposed for the reduction of errors due to multiple scattering which employs linear-algebraic inversion of generalized space-invariant convolution templates derived from blur functions. The image restoration algorithm is evaluated in terms of residual error computational cost and suitability for parallel implementation.

In the process of manufacturing silicon carbide reinforced aluminum metal matrix composites silicon carbide particles are mixed with aluminum powder and subjected to an extrusion process. The orientation of the silicon carbide particles in the resulting composite should be random for the stiffness of the material to be the same in the three orthogonal directions. Secondary electron images show that the orientation of the particles follow some pattern rather than being random. To determine stiffness it becomes necessary to study nondestructively the rnicrostructure characteristics such as the distribution of size orientation length and aspect ratio of the silicon carbide particles. In silicon carbide particles it was found that many of the silicon carbide particles appear connected. A new procedure has been developed that aims at separating these connected particles thereby making it possible to characterize the rnicrostructure. This procedure is an extension of the cluster fast segmentation algorithm (CFS) a morphological algorithm that can break the connectivity among particles that overlap. Seeds are generated for every individual particle it can identify. CFS fails when there is no constriction at the region of connection of the particles. Certain properties of the skeleton can then be used to generate markers for as many particles as possible. After partitioning is completed the markers are grown back using morphological rules.

This paper describes the morphological methods used in a prototype for an automated visual on-line metal strip inspection system. The system is capable of both detecting and classifying surface defects in copper alloy strips and it has been installed for evaluation in a production line in a rolling mill. Mathematical morphology is used for the preprocessing and segmentation of images. This approach is powerful because the metal strip defects cannot be discriminated from the defecfless background by their contrast alone but only by reference to their shape and size as well. The algorithms have been mapped onto commercial hardware modules.

This paper presents a method for generating morphological template features for use in a word verification system. Word verification is a process of matching an image of a word against a list of candidate strings. The verification process assigns a confidence value to each string. The rank of the correct string is one measure of success. A character by character rank may also be obtained. The paper describes experiments using 20 samples in each of 57 character classes to automatically develop 60 template features for the word verification process. The generation process is guided by a measure of orthogonality between the features. Two slightly different versions of the orthogonality measure are compared. The resulting features are then trained on roughly 67 character samples to form the feature/character statistics. Results of the word verification process using the automatically generated features are compared with earlier results using a set of manually generated features. The principal result is that automatically generated template features perform better than the manually generated features.

This paper describes a LISP based environment for the automatic manipulation and analysis of morphological expressions. The foundation of this environment is an aggregation of morphological knowledge that includes signal and system property information rule bases for representing morphological relationships and inferencing mechanisms for using this collection of knowledge. The layers surrounding this foundation include representations of abstract signal and structuring element classes as well as actual structuring elements implementations of the morphological operators and the ability to optimally decompose structels. The representational requirements for automatically manipulating expressions and determining the computational cost are described and the capabilities of the environment are illustrated by examples of symbolic manipulations and expression analysis.

The Image Algebra Ada (IAA) system is the basis for a programming environment that enables the nearly direct use of image algebra by an Ada programmer. The system has two components: a translator which converts the IAA source into pure Ada and runtime support packages for the resulting programs. The most important data structures in this system are images. An image is a map from a set of points (the domain of the image) to values in some Ada type. A point is an n-tuple of integers (any number of dimensions is supported). Points are usually interpreted as being represented in Cartesian coordinates however in principle other coordinate systems e. g. polar could be used. A design goal of IAA was to allow arbitrary domains while still supporting " boxy" domains (parailelepipeds) efficiently. A naive strategy for this is to have one representation for boxes which records the bounds of the box and one for non-boxes which is a linear list of the points. The approach taken however avoids having two different representations. We decompose the domain into slices along one dimension and use an interval representation for consecutive identical slices. This can represent arbitrary sets and achieves its least space and time costs for boxy sets. The representation is recursive: boxes resemble lists and nonboxes resemble trees. With this representation non-boxy domains are fairly compact when they represent areas or

Morphological processing provides a powerful set of tools for analyzing shape. However the user of morphological techniques can easily become overwhelmed by the large number of possible solutions to be investigated. A large solution space exists because the structure elements used in morphological operations can be extremely varied in size and shape. Similarly fundamental morphological operations can be combined in numerous sequences. The user therefore needs a tool for rapidly investigating the large number of structure elements and operator combinations available for a given task. This paper describes a computer system that has been developed expressly for rapidly defining structure elements building and executing operator combinations and viewing the resultant image. The system uses a mouse-driven graphical interface to allow rapid prototyping of morphological operations. An expression parser is embedded in the system to allow sequences of morphological operators to be executed with a single command. The system will help computer vision algorithm designers explore the solution space more rapidly and may lead to a broader appreciation of the field of morphology by facilitating exploration of its capabilities. t

Commercial hardware for neural network implementations is becoming more readily available. However as yet there exists no hardware- or software-independant environments in which to compare neural net chips. This paper presents a comparison of the Hamming net modeled on two neural net chips using image algebra a mathematical structure developed for use in image processing and related fields. The two chips used in the comparison are the Electrically Trainable Analog Neural Network (ETANN) from Intel and the Neural Bit Slice (NBS) from Micro Devices and are on opposite ends of the spectrum of available neural network hardware. The ETANN is almost entirely analog while the NBS is an all-digital device. The image algebra pseudocode modeled well not only the internals of the chips but the external logic and control as well.

The Air Force Image Algebra formalizes the notion of a generalized matrix product (GMP). The GMP is the basis for image-template operations in the Image Algebra. In a mathematical sense the GMP supports the combining of matrices using paradigms other than the dot product approach of linear algebra. This permits one to view linear and non-linear image transformations and mathematical morphology operations as different embodiments of the same concept. The GMP has been implemented on a variety of computers from sequential to massively parallel. Our experience with use of the GMP on parallel machines has shown that the GMP unifies the three concepts of many-to-one one-to-many and one-to-one data transfers (reduction replication and permutation respectively). This paper demonstrates the utility of the generalized mathx product as a tool in algorithm description. It discusses the relationship of the GMP to the three data transfer paradigms of massively parallel machines and shows how GMP mappings and their transposes can be efficiently implemented on massively parallel processors. It also presents code restructuring techniques necessary to implement GMP operations efficiently on sequential computers linking the general problem of serializing parallel programs to implementation of the GMP operation.

Current image analysis and image understanding applications in DoD systems require very high performance image pixel processing in real time. To attain the necessary performance within stringent system size weight and power constraints requires special-purpose parallel processing hardware architectures. At the same time it is desirable to retain as much programmability as possible in order to rapidly adapt the hardware to new applications or evolving system requirements. The Parallel Recirculating Pipeline processor uses techniques adopted from image algebra and mathematical morphology to provide a low-cost low-complexity high-performance architecture that is suitable for silicon implementation and programmable in high-order languages. This paper discusses the programming model for the Parallel Recirculating Pipeline. The model treats two dimensional data arrays as elementary operands. Elementary operators such as addition are performed point by point on these data arrays. A primitive spatial translation operator allows complex operations such as convolution to be constructed by combining " shifted" and non-shifted imtermediate result arrays. This model corresponds closely with the underlying hardware model and permits processor expressions embedded in " host" language source code to be translated in situ. The translation is accomplished by a simple preprocessor and the resulting modified source code can be cross compiled by any existing compiler of the host language.

This paper describes a parallel real-time stereo segmentation algorithm and its performance on the Thinking Machines Corporation''s Connection Machine. Following Y. Yeshuran and IL Schwartz''s work on the cepstral filter we compute the disparity in stereo image pairs using an implementation of the image algebra developed especially for the Connection Machine. The algorithm utilizes the FFT-based cepstral filter applied to interlaced patches of the stereo pairs producing disparity vectors that provide depth information. The principle advantage of this technique is that it is non-4terative and maps well to massively parallel architectures. Alternatives to the FFT portion of the algorithm are explored including the Hartley Transform and ad hoc methods. Some results are presented for realistic images and random dot stereograms.

A high-speed special purpose architecture is presented to implement convolution and morphological filters in real-time. The highly parallel pipelined architecture developed has the characteristics of both a systolic array and an augmented 2-D mesh connected computers. We refer to this hybrid architecture as a systolic mesh (SMESH). In contrast to previous work in this area which has the emphasized the computational aspects the SMESH architecture addresses both computation and TO issues. We exploit the systolic array approach to improve the computation execution time while using a special broadcast scheme to speed-up JO communication leading to an 10-computation balanced design. I.

Current image analysis and image understanding applications in DoD systems require very high performance image pixel processing in real time. To attain the necessary performance within stringent system size weight and power constraints requires special-purpose parallel processing hardware architectures. At the same time it is desirable to retain as much programmability as possible in order to rapidly adapt the hardware to new applications or evolving system requirements. The Parallel Recirculating Pipeline processor uses techniques adopted from image algebra and mathematical morphology to provide a low-cost low-complexity high-performance architecture that is suitable for silicon implementation and programmable in high-order languages. The parallel recirculating pipeline hardware architecture is based on a cellular array structure in which each cell is a pipelined neighborhood processor. Each processor cell transforms an entire image segment by successively executing an operation on small fixed-size neighborhoods around each pixel. By cascading a series of these operations transforms on larger neighborhoods can be achieved. The parallel recirculating pipeline achieves cascading by allowing a series of cells to be connected in a pipelined fashion. Partial results can recirculate several times through the hardware pipeline via an external buffer memory. A virtual pipeline of any length is thus achieved. Several novel features of the architecture allow multiple pipelines to operate in parallel on strips of the same image. These features can support parallel expansion to a large number of processors with correspondingly

This paper presents an efficient VLSI architecture for the real-time implementation of grayscale morphological operations. The proposed architecture employs a bit-serial approach which allows grayscale morphological operations to be decomposed into bit-level binary operations by a bit-modification algorithm, and thus requires only p binary operation units for the p-bit grayscale signal. In this realization, grayscale opening and closing are accomplished by local rather than cascade operations, providing greatly increased data throughput. It is shown that this realization is simple and modular in structure and is suitable for VLSI implementation.

This paper describes the VLSI hardware implementation onto an ASIC (Application Specific Integrated Circuit) of a gray-scale morphology processor. This is a prototype first chip of a series for a project to perform real-time image processing for NDE (Non-Destnicve Evaluation) applications. Processing of images requires the performance of relatively simple mathematical operations like additions subtractions and comparisons on a tremendously large amount of pixels (data points). This hardware implementation uses the idea of an array processor where each processor performs the exact same operations at the same time but on different pixels. The morphology operation is done in a highly parallel fashion thus enabling a real time performance of 80 MOPS (Million Operations Per Second). The chip described in this paper has the capability of performing both erosion and dilation operations on variable size images with a variable size structuring element. This custom chip was designed using a 2. t CMOS process on a die size of 6. 8 x 6. 9 mm2 in the Department of Electrical Engineering and Computer Engineering at Iowa State University. Custom layout was chosen over standard cell implementation in order to reduce the area of the chip and to increase the operational speed. The fabrication is being done through the MOSIS fabrication services. For the project the final version of the chip will be implemented in a 1jt CMOS technology thus enhancing the speed and

Optical morphological processor implementations and results are provided using a correlator architecture. The multifunctional MIMD (multiple-instruction multiple-data) advantages of the optical correlator realization used are noted together with the role for optics in the various levels of computer vision. Filter realizations of the morphological structuring elements (SEs) as matched spatial filters (MSFs) are considered. All major morphological processing operations are described and optical laboratory data for many cases are provided to unify much of our prior work on this topic. I .

Image processing afid image analysis tasks have large (lata processing requirements and inherent parallelism. Because they involve a large amount of data, their operations can he extremely complex. During the past few years, numerous papers lave used an algebraic approach to aid in image processing [Serra82, Lotigheed8o, JUL Lcr87, Ciardina8i, Agui82, lluang87aJ. A simple algebraic system for expressing parallel image transformations would be very helpful for people to learn the art of parallel image processing, to compare different algorithms and architectures, arid to design a special-purpose image processor. Iii this paper, we use a binary image algebra (}31A) [ llnang89a, iluang9OJ, an axiomatic algebraic structure, to serve as a standar(l mathematical structure for the processing of binary images. Some parallel binary image processing architures can then be derived and compared. Section 2 reviews BEA and discusses the requirements for implementing A. Section 3 (liscusses three kinds of parallel architectures for f3JA: near-neighbor array architectures, hypercube architectures, and pipeline architectures. Section 4 discusses their implementation techniques. Section 5 gives a conclusion.

Convolutions are a fundamental tool in image processing. Classical examples of 2-dimensional linear convolutions include image correlation the mean filter the discrete Fourier transform and a multitude of edge mask filers. Nonlinear convolutions are used in such operations as the median filter the medial axis transform and erosions and dilations as defined in mathematical morphology. For large convolution mask the computation cost resulting from implementation can be prohibitive. However in many instances this cost can be significantly reduced by decomposing the masks or templates into a sequence of smaller templates. In addition such decompositions can often be made architecture specific and thus resulting in optimal transform performance. In this paper the issues of template decomposition are discussed in the context of the image algebra. Necessary and sufficient conditions as well as some efficient methods for decomposing rectangular symmetric convex and spherical templates are presented.

A convex, filled polygonal shape in R x R can be uniquely represented in the discrete Zx Z domain by the set of all the lattice points lying in its interior and on its edges. We define a reslricled convex shape as the discrete four connected set of points representing any convex, filled polygon whose vertices lie on the lattice points and whose interior angles are multiples of 450 In this paper we introduce the Boundary Code (B-Code), and we express the morphological dilation operation on the restricted convex shapes with structuring elements that are also restricted convex shapes. The algorithm for this operation is of O( 1) complexity and hence is independent of the size of the object. Further, we show that the algorithmic for the n-fold dilation is of 0(1) complexity. We prove that there is an unique set of thirteen shapes {K1 ,K2, . . . , "13) such that any given restricted convex shape, K, is expressible as K = K' K . . . K3 where K, represents the ni-fold dilation of K. We also derive a finite step algorithm to find this decomposition.

Template decomposition techniques can be useful for improving the efficiency of image processing algorithms. The improved efficiency can be realized either by reorganizing a computation to fit a specialized structure such as an image processing pipeline or by reducing the number of operations used. In this paper two techniques for decomposing templates with respect to gray-scale morphological operations are presented. One of the techniques can be also be applied to binary templates as well.

Lattice transformations are a class of nonlinear image processing transforms that include mathematical morphology transforms as a subclass. By using a matrix representation lattice transforms may apply results established in minimax algebra a matrix algebra originally developed for operations research. This paper presents a strong decomposition technique for a translation invariant template that is a lattice transform using a minimax matrix approach. The factors of the decomposition correspond to variant templates. This method is particularly suited for implementation on multiple-instruction multiple-data (MIMD) architectures. Since the minimax algebra is a subalgebra of the Air Force image algebra which in turn encompasses mathematical morphology this technique provides another tool for template decomposition which in particular can be applied to morphology transforms.

This paper consists of two distinct contributions. The first contribution formulates the theory of translational invariant image transformations in the context of symbolic transformation groups and presents results describing the decomposability of certain image transformations. The ultimate objective of such studies is to decompose image transformations efficiently by decomposing them into short sequences of simpler transformations. Our methods are used to show particular indecomposable transformations, so that where previously only existence results were shown (Nasu's theorem), we can now explicitly search for indecomposable transformations. The second contribution discusses related stochasticconcepts. It formulates several Markovian approximations to images with potential application to image segmentation, image generation, and image coding. One family of models is closely related to the renormalizationgroup concepts that were originally formulated to address problems in statistical physics and quantum field theory, and have more recently been used to provide hierarchical methods for image processing. We apply these approximations to a specific binary valued random field- the two dimensionalIsing model- and demonstrate that segmentation can be achieved, and that a hierarchical model haspromise in this regard.

This paper begins by reviewing methods recently developed by the authors for the decomposition of twodimensional shift-invariant convolution operators of size (2m + 1) x (2n + 1) into sums and products of 3x3 operators. Results include the fact that every 5x5 operator can be decomposed into the sum and product of at most five 3 x 3 operators and a theorem giving a characterization for those 5 x 5 operators which can be decomposed into the sum and product of at most three 3x3 operators. The focus of the new theorems presented here will center on the problem of extending results valid for shift-invariant operators to non shift-invariant operators. The image algebra developed by G. X. Ritter will provide the setting for this investigation.