Fast, efficient algorithms for 3x3 ranked filters using finite-state machinesFrederick M. Waltza, Ralf Hackb, and Bruce G. Batchelorba 2095 Delaware Avenue, Mendota Heights, MN 55118-4801 USAb Department of Computer Science, University of Wales Cardiff, Cardiff, Wales, UKABSTRACTMedian filters and ranked filters of ranks other than median have often been proposed or used to remove image noise as wellas for other reasons. These are nonlinear operations, and often have relative long execution times, making them unsatisfac-tory for many speed-critical industrial applications.This paper builds on the earlier work of Mahmoodi and Waltz1to provide efficient implementations of 3x3 ranked filters ofranks 1 (minimum), 2, 3, 4, 5 (median), 6, 7, 8, and 9 (maximum). These implementations are based on a partial realizationof the SKIPSM (SSeparated-KKernel IImage PProcessing using finite-SState MMachines) paradigm. A full SKIPSM realization isnot possible because, except for the filters of ranks 1 and 9, these operations are not separable. This paper shows that, in spiteof this lack of separability, the finite-state machine aspect of SKIPSM can be used to advantage. The emphasis is on softwareimplementations, but implementations in pipelined hardware have also been demonstrated.In addition, a fast “full-SKIPSM” implementation of a slightly different ranked filter, sometimes called the “separablemedian” filter, is presented. This filter guarantees that the output pixels are of rank 4, 5, or 6. For typical noise-reductionapplications, it is difficult to find a convincing argument that this filter is inferior in any meaningful way to the true medianfilter.Keywords: median filter, ranked filters, separable median filter, separation, finite-state machines1. INTRODUCTIONThere are three commonly-used measures of central tendency: the mean, the mode, and the median. The ordinary mean, oruniformly-weighted average, is an easily-computed linear operation involving only addition, scaling, and rounding. Theweighted average, usually called a convolution, is a variation of this. Both are sensitive to extreme values, and hence maygive poor results in situations with “shot” noise or “salt-and-pepper” noise.The mode, or most commonly observed value, requires even more computation than the median and often fails to give aunique value. For example, the set [1, 1, 1, 4, 5, 6, 9, 9, 9] has both mean and median equal to 5, but it is “bi-modal” – it hastwo modes, 1 and 9. The set [1, 1, 1, 5, 5, 5, 9, 9, 9] has both mean and median equal to 5, but is tri-modal. For normaldistributions on large sets, the mean, mode, and median give essentially the same value. However, the mode is generallyerratic on small sets (the kind most commonly used in image processing), and should usually be avoided.The median, or middle value of an ordered set of values, has the great advantage of being totally unaffected by one or a fewextreme values. It has the disadvantage of requiring considerably more computation than the mean. Median filters andranked filters of ranks other than the median have often been proposed or used to remove image noise as well as for otherreasons. These are nonlinear operations, and often have relative long execution times, making them unsatisfactory for manyspeed-critical industrial applications. Therefore, if a faster method of computing the median filter and other ranked filters canbe developed, these filters can be expected to be used in a wider range of applications. This paper builds on the earlier work of Mahmoodi and Waltz1to provide efficient implementations of 3x3 ranked filters ofranks 1 (minimum), 2, 3, 4, 5 (median), 6, 7, 8, and 9 (maximum). For ranks 2 through 8, these implementations are based ona partial realization of the SKIPSM (SSeparated-KKernel IImage PProcessing using finite-SState MMachines) paradigm. Detaileddiscussions of SKIPSM have been presented in numerous previous works2-21, and will not be repeated here, except to saythat extreme speedups of many 2-D and 3-D neighborhood image-processing operations have been obtained, and significantspeedups have been achieved for many other operations.A full SKIPSM realization is not possible for ranked filters because these operations are not separable, except for the filtersof ranks 1 and 9. Separability in this context is not limited to the familiar separability of a subset of the linear-convolutionkernels. Instead, it has been shown2-21that a wide range of 2-D operations can be separated into two 1-D operations – a rowoperation followed by a column operation, or a column operation followed by a row operation, or two orthogonal diagonalFast, efficient algorithms for 3x3 ranked filters using finite-state machinesSPIE Paper 3521-31 Frederick M. Waltz SK18-1SPIE Conf. on Machine Vision Systems for Inspection and Metrology VII Originally published Boston, Nov. 1998Copyright July 1998 by F. M. Waltz. Duplication by permission only.operations. The speedups provided by SKIPSM result primarily from this separation, as well as the pipelining of theoperation and the use of recursive finite-state machines.To see why the median operation is not one of those which can be separated, let us first consider a few operations which areseparable:• Addition or, equivalently, averaging – If we divide a set of numbers to be added into subsets, and add the members of thesubset separately, then the overall sum is the sum of the subset sums. For averaging, the same conclusion holds ifweighting is taken into account.• Maximum (rank 9) – The overall maximum is the maximum of the subgroup maximums.• Minimum (rank 1) – The overall minimum is the minimum of the subgroup minimums.• Binary erosion – If the various parts of the structuring element “fit” the corresponding parts of the image, then theoverall structuring element “fits” the image.Now consider the median of a set of numbers: The overall median is, in general, not the median of the subset medians. Hereis a counter-example: Let the subsets be [2, 2, 1], [4, 8, 9], and [5, 8, 9]. The subset medians are 2, 8, and 8. The median ofthese numbers is 8. But the median of the overall set [1, 2, 2, 4, 5, 8, 8, 9, 9] is 5. Similar conclusions hold for ranks between2 and 8 (of 9-element sets). Separability rules for arbitrary operators are given in 1.This paper shows that, in spite of this lack of separability, the FSM (finite-state machine) aspect of SKIPSM can be used