SKIPSM:SSEPARATED-KKERNELIIMAGEPPROCESSING USING FINITE-SSTATEMMACHINESFrederick M. Waltz, 2095 Delaware Avenue, Mendota Heights, MN 55118-4801 USAABSTRACTThis paper presents a fundamentally new way to carry out many standard image processing operations. In comparison withconventional hardware-based and software-based approaches, SKIPSM (Separated-Kernel Image Processing using Finite StateMachines) allows implementation at higher speeds and/or lower hardware cost. The key features of SKIPSM are• the separation of a large class of neighborhood image processing operations (generally considered not to be separable) into a rowoperation 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.Speed increases and/or neighborhood size increases by factors of 100 or more are achieved using conventional pipelined hardware inthis new way. Alternatively, inexpensive off-the-shelf “chips” can be configured to carry out the same operations as conventionalhardware. Corresponding “speedups” are achieved in software-based implementations. Furthermore, it is often possible to useSKIPSM to carry out 10 or more different image processing operations simultaneously, with no additional processing steps orhardware.Keywords: image processing, separability, real-time, implementations, finite-state machines, inspection1. INTRODUCTIONCertain image processing operations have become “standard” in the field: linear convolutions, minimum and maximum, morphology,and so on. The techniques for implementing these operations have largely become standardized also. Where the speeds available fromaffordable software-based systems are insufficient, a number (anywhere from one to dozens) of hardware boards are connectedtogether in various ways to perform desired combinations of operations on the input images. The conventional approach to carryingout image processing operations in fast hardware is essentially a “brute force” approach, using separate standard or custom integratedcircuits for each function: multipliers, adders, random-access memories, and so on. Improved performance (e.g., largerneighborhoods, faster speeds) is achieved by using more and/or faster functional blocks. The observed trend of ever-increasingperformance for such boards is due almost exclusively to the continuing miniaturization of the integrated circuits used, and not to anynew algorithms or ways of implementing the desired operations.In contrast, this paper and the companion papers1, 2, 3, 4, 5present what is believed to be a completely new way to implement a varietyof important image processing operations. The acronym SKIPSM (Separated-Kernel Image Processing using Finite State Machines)has been given to this family of techniques. This approach can use existing hardware, or can be implemented in custom hardware, orcan be implemented in software. Whatever the implementation, greatly improved performance is obtained, which may take the formof increased speed or larger neighborhoods or both. As new boards and components with enhanced performance become available,these new techniques will provide comparable additional performance improvements. Stated another way: Whatever components areneeded to achieve a specified result using conventional implementations, the use of these new techniques (where they apply) willallow either increased performance with the same components, or the same performance with fewer components, or somecombination of these two effects.The image processing categories to which SKIPSM can be applied include but are not limited to the following:• Binary morphology of all types with large, arbitrary SEs (structuring elements). SEs up to 25x25 and larger and with “holes” andother non-convex shapes can be applied in a single pipelined pass.• Multiple SEs can be applied simultaneously in a single pipelined pass. For example, 6 or more stages of the “Grassfire Transform”have been carried out in one pass, and even larger numbers of stages are possible.• Grey-level morphology, if the number of grey levels is not too large.• Binary template matching with large, arbitrary templates.• “Fuzzy” binary template matching and binary correlation.• Grey-level template matching, if the number of grey levels is not too large.• Various “smearing” operations, including row, column, and diagonal summations and Hough transforms.• Certain operations previously thought to be impossible in a pipelined system, such as “blob fill” and “patterned blob fill.”• Pipelined generation of certain standard images (e.g., grey-level wedges) and arbitrary image patterns (textures).SKIPSM: Separated-Kernel Image Processing using finite-State Machines SPIE Paper # 2347-36 F M Waltz SK1- 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.This paper presents the fundamental ideas of SKIPSM. Details of many of the above-noted applications are given in the companionpapers.1, 2, 3, 4, 5Four key ideas are involved:• the separation of 2-dimensional operations into a row operation followed by a column operation,• the reformulation of these operations in a recursive (“pipelined”) manner,• the implementation of these recursive operations as finite state machines, and• the automated generation of the finite state machine configuration data.Note that the separation of 2-D operators into two 1-D operators does not involve separability in the usual sense, such as is definedfor 2-D linear convolutions. All 2-D operators meeting a simple separability condition (defined below) can be separated usingSKIPSM, although the result may be unwieldy in some cases.Finite-state machine theory is a branch of automata theory. Finite-state machines (henceforth referred to as FSMs) are not machines,in the usual sense, but autonomous input-driven sequential mathematical/logical constructs having important analytical andcomputational properties and a very well-developed body of theory. Hardware implementations of FSMs using flip-flops,multiplexing switches, or ASICs are widely used for such things as