APPLICATION OF SKIPSM TO GREY-LEVEL MORPHOLOGYFrederick M. Waltz, 2095 Delaware Avenue, Mendota Heights, MN 55118-4801 USAABSTRACTAn overview of SKIPSM (Separated-Kernel Image Processing using Finite State Machines), a powerful new way to implement manystandard image processing operations, is presented in a two companion papers.1, 2 This paper describes the application of SKIPSM togrey-level morphology, which involves• in some cases, the reformulation of the grey-level morphology problem as a set of binary morphology operations,• the separation of 2-D morphological operations into a row operation followed by a column operation,• the formulation of these row and column operations in a form compatible with pipelined operation,• the implementation of the resulting operations as simple finite-state machines, and• the automated generation of the finite-state machine configuration data.Grey-level morphology presents some difficulties to the SKIPSM paradigm having to do with word length. In spite of this, some veryuseful results can be obtained. Some key features of SKIPSM, as applied to grey-level morphology, are• There is a tradeoff between structuring element (SE) size and number of grey levels.• The SEs can be arbitrary . With currently-available components, SEs up to 5x5 and larger can be obtained. • In certain special cases, SEs up to 9x9 and larger can be obtained. • Multiple SEs can be applied simultaneously in a single pipeline pass.• The user specifies the SE or SEs. All other steps can be automated.This paper includes some simple examples of the results and gives implementation feasibility guidelines based on SE size and numberof grey levels. The limitations of SKIPSM in this application all relate to the capabilities of the available RAM microchips. As chipcapabilities expand, larger SE sizes and greater numbers of grey levels will become feasible.Keywords: image processing, separability, real time, implementations, finite-state machines, grey-level morphology1. INTRODUCTIONAn overview of SKIPSM (Separated-Kernel Image Processing using Finite State Machines), a powerful new way to implement manystandard image processing operations, is presented in a set of companion papers.1, 2, 3, 4, 5 This paper describes the application ofSKIPSM to grey-level morphology. As with the other uses of SKIPSM described in other papers, the application to grey-levelmorphology involves• in some cases, the reformulation of the grey-level morphology problem as a set of binary morphology operations,• the separation of 2-D morphological operations into a row operation followed by a column operation,• the formulation of these row and column operations in a form compatible with pipelined operation,• the implementation of the resulting operations as simple finite-state machines, and• the automated generation of the finite-state machine configuration data.Grey-level morphology presents some difficulties to the SKIPSM paradigm having to do with word length. In spite of this, some veryuseful results can be obtained. Some key features of SKIPSM, as applied to grey-level morphology, are• There is a tradeoff between structuring element (SE) size and number of grey levels. It is easy to obtain 16 grey levels, but 64 ormore grey levels are not practical at this time except in special cases.• The SEs can be arbitrary . With currently-available components, SEs up to 5x5 and larger can be obtained. • In certain special cases, defined below, SEs up to 9x9 and larger can be obtained. • Multiple SEs can be applied simultaneously in a single pipelined pass.• The user specifies the SE or SEs. All other steps are automated.This paper includes some simple examples of the results and gives implementation feasibility guidelines based on SE size and numberof grey levels. The limitations of SKIPSM in this application all relate to the capabilities of the available RAM microchips. As chipcapabilities expand, larger SE sizes and greater numbers of grey levels will become feasible.It is useful from an implementation standpoint to divide the overall morphology problem into four cases, as shown in Figure 1, whichillustrates the erosion operation. The heavy lines represent cross-sections of the input image, which can be thought of as analogous toa mountain range, with brighter grey levels corresponding to higher elevations. The smaller shaded figures are the structuring element(SEs). At each pixel position, the SE is pushed up from below as far as it will go. The diamonds then show the corresponding outputvalues. Grey levels ranging from zero to 255 are shown, but other levels could be used.Application of SKIPSM to grey-level morphology SPIE Paper # 2347-40 F M Waltz SK5-1SPIE Conf. on Machine Vision Applications, Architectures, and Systems Integration III Originally published Boston, Nov. 1994Revised and republished January 1998. Copyright Jan. 1998 by F. M. Waltz. Duplication by permission only.Figure 1. Grey-level morphology classification scheme showing cross-sections (“side views”) of 2-D images and SEs.The morphology companion paper2shows that SKIPSM handles Case BB, ordinary binary morphology, very well. The GrassfireTransform3is an example of Case BG, as is the Euclidean Distance Map.6This paper provides a more general solution for Case BG.On the other hand, Case GB, which is actually the unweighted neighborhood minimum operation, can be implemented using SKIPSMif there are sufficiently few grey levels in the image or the neighborhood is sufficiently small, but a direct solution usingneighborhood minimum-maximum hardware is preferable if such hardware is available and affordable.True grey-level morphology, Case GG, can be implemented in certain rather limited but still useful situations.2. FSM ESSENTIALS AND SEPARABILITY AS APPLIED TO GREY-LEVEL MORPHOLOGYThe companion papers1, 2, 3include discussions of SKIPSM and finite-state machine (FSM) fundamentals and implementationarchitectures. This paper builds on the developments given in the binary morphology paper2and the Grassfire Transform paper3, thedetails of which will not be repeated here. The overall conclusions of these papers, as applied to the grey-level morphology, can besummarized as follows:• Grey-level morphology operations can be formulated in terms of binarymorphology operations, particularly binary erosion.• The binary erosion operation can be separated into a row operation followed bya