|
The principles of SKIPSM (Separated-Kernel Image Processing using Finite State Machines), a powerful new way to implement many standard image processing operations, are presented here and in a group of companion papers. This paper describes the application of SKIPSM to the computation of the Grassfire Transform (GT), the mapping of a binary image into a grey-level image in such a way that the output grey level of each interior pixel of each individual blob is proportional to the distance of that pixel from the blob boundary. Distance can be defined in terms of various norms: Euclidean distance, elliptical distance, 'boxcar' distance, etc. While potentially very useful, the GT has seen limited application because of the many computational steps required to calculate it. In comparison with conventional hardware-based and software-based approaches, SKIPSM allows implementation of the GT at higher speeds and/or lower hardware cost. The key developments upon which this improved performance is based are (1) the separation of 2D the binary erosions on which the GT is based into row operations followed by column operations, (2) the formulation of these row and column operations in a form compatible with pipelined operation, (3) the implementation of the resulting operations as simple finite-state machines, (4) the automated generation of the finite-state machine configuration data for structuring elements (SEs), and (5) the simultaneous application of all these nested SEs in a single pipeline pass. Some key features of SKIPSM, as applied to the GT, are listed below: (1) Because the SEs can be large and arbitrary, any distance measure can be used. There is no penalty involved in using true circles or ellipses, rather that the octagons or squares resulting from sequential application of 3 X 3 SEs. (2) The simultaneous application of six circular erosion stages (SEs of size 3 X 3, 5 X 5, ..., 13 X 13) has already been demonstrated. Eight or more simultaneous circular erosion stages may be possible (sizes 3 X 3, 5 X 5, ..., 17 X 17, ...). (3) The user specifies the SE or SEs. All other steps are automated. These results are can be achieved using conventional pipelined hardware in this new way. Alternatively, inexpensive off-the-shelf 'chips' can be configured to carry out the same operations as conventional image processing hardware. Corresponding 'speedups' are achieved in software-based implementations.2347
|
