Fast efficient algorithms for 3x3 ranked filters using finite-state machines
Frederick M. Waltz, Ralf Hack, Bruce G. Batchelor · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1998
Median filters and ranked filters of ranks other than median have often been proposed or used to remove image noise as well as for other reasons. These are nonlinear operations, and often have relative long execution times, making them unsatisfactory for many speed-critical industrial applications. This paper builds on the earlier work of Mahmoodi and Waltz to provide efficient implementations of 3 X 3 ranked filters of ranks 1 (minimum), 2, 3, 4, 5 (median), 6, 7, 8, and 9 (maximum). These implementations are based on a partial realization of the SKIPSM (Separated- Kernel Image Processing using finite-State Machines) paradigm. A full SKIPSM realization is not possible because, except for the filters of ranks 1 and 9, these operations are not separable. This paper shows that, in spite of this lack of separability, the finite-state machine aspect of SKIPSM can be used to advantage. The emphasis is on software implementations, but implementation is pipelined hardware have also been demonstrated. In addition, a fast `full- SKIPSM' implementation of a slightly different ranked filter, sometimes called the `separable median' filter, is presented. This filter guarantees that the output pixels are of rank 4, 5, or 6. For typical noise-reduction applications, it is difficult to find a convincing argument that this filter is inferior in any meaningful way to the true median filter.