Cost-effective two-dimensional rank-order filters on FPGAs

By Gabor Szedo, Xilinx and Peter Szanto, Budapest University of Technology and Economics
September 20, 2007  -- dspdesignline.com

Rank-order filtering is a non-linear filtering technique in which an element is selected from an ordered list of samples. Two-dimensional (2D) filtering is performed on the contents of a rectangular window that slides across an image. As the window moves by one pixel, a set of obsolete elements are discarded and a set of new elements are inserted into the filter window. The samples within the window are sorted and the element with the specified rank is selected as output. Most typical ranks are median, minimum, and maximum.

Compared to linear filters such as finite impulse response (FIR) or IIR, rank filters can effectively remove specks while preserving edges. This can be very useful for noise-removal or pre-processing applications. In this article, we'll present an architecture that lends itself well to area and performance trade-offs in high-performance FPGAs.

Previous Work

Earlier rank-filter implementations have not dealt with aspects of color image processing, predominantly classifying a filter as 2D if it was able to generate a valid pixel output in a single clock cycle.

Bit-serial approaches provide the lowest complexity. Processing rates are not usually dependent on the number of new samples the filter can handle in a single clock cycle. Bit-serial approaches are non-recursive and consequently easy to pipeline, but require a large number of comparators. Filtering performance is proportional to input data width.

Word-parallel architectures usually implement a sorting network that employs bubble sorting, odd/even merge sorting, and other architectures optimized for resource efficiency.

Most rank-filter architectures either store samples by the order of arrival (FIFO) or magnitude ordered. Insert/delete architectures store samples ordered by magnitude. The oldest sample is discarded and the most recent input is inserted into the sorting structure at the appropriate location. These solutions require fewer comparators.

FIFO-based architectures dynamically calculate the location of the output sample. These architectures are easier to pipeline and adapt to multiple samples per clock cycle, which is essential for 2D filtering.

To read the full article, click here