Software and VLSI algorithms for generalized ranked order filtering

Abstract

The threshold decomposition architecture is known to provide a modular and parallel design for ranked order filtering. However, the chip area grows exponentially with the number of bits in the input. In this paper a new architecture which is equivalent to the threshold decomposition is shown to have linear growth in the size of the input words. Filtering is accomplished by a pipelined bit by bit algorithm. Hardware modifications to the filtering scheme are accomplished by changing data paths and the number of cells to be replicated rather than modifying the functions performed by each module. Hardware redundancy to prevent single points of failure can be provided when space for extra modules is available. If external data flow control is provided, the chip can be programmed for many different filtering operations. The basic representation of the generalized rank order filter as a maximum of minimums also provides a fast software implementation and intuitive description of these filters as adaptive rank operations. Because the threshold description is extremely slow on a general-purpose computer, this is essential for investigating new applications of these robust signal and image processing filters.