Design and implementation of a novel algorithm for general purpose median filtering on FPGAs

Abstract

We present a novel bit serial algorithm which is scalable and easily implemented on small FPGA chips. The basis of the algorithm is similar to that of Quicksort, and is based on a 'Bit Voter' (BV) block. The paper also extends the basic BV algorithm to include Weighted Median and Ranked Order Median filtering. The median finding unit, whose inputs are the N pixel values to sort, has an O(N) hardware complexity compared to O(N/sup 2/) complexity for an equivalent unit using Bubble sort. The novel algorithm has been implemented on an XC4010E-1 FPGA chip. For comparison purposes, we also present an FPGA implementation of an existing 'Triple Input Sorter' based algorithm (TIS) which is an optimised version of the Bubble sort algorithm for the special case of a 3/spl times/3 window size. The BV's median finding unit occupies 15 CLBs only whereas TIS occupies 60 CLBs. For 512/spl times/512 input images of 8-bit/pixel, comparative timings show that BV can operate at 25 frames per second (fps), while TIS can achieve 39 fps. Thus, both algorithms can achieve real time performance, and BV is the more compact.