New bit-level algorithm for general purpose median filtering

Khaled Benkrid; Danny Crookes

doi:10.1117/1.1557153

1 April 2003 New bit-level algorithm for general purpose median filtering

Khaled Benkrid, Danny Crookes

Journal of Electronic Imaging, Vol. 12, Issue 2, (April 2003). https://doi.org/10.1117/1.1557153

Median filtering has proved an effective way to remove impulse noise while preserving rapid signal changes. A classic general purpose median filter is based on a bubble sort approach. We present a novel bit-level algorithm that is readily scalable and very compact. The basis of the algorithm is similar to that of Quicksort, and is based on a bit voter (BV) block. The work 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 an O(N²) complexity for an equivalent unit using bubble sort. The novel algorithm has been implemented on a Xilinx Spartan XCS30XL-4 FPGA chip. For comparison purposes, we also present an FPGA implementation of an existing triple input sorter based algorithm (TIS), which is an optimized version of the bubble sort algorithm for the special case of a 3×3 window size. The BV median finding unit occupies 15 configurable logic blocks (CLBs) only, whereas TIS occupies 60 CLBs. For PAL video (720×576 images of 8-bit/pixel), comparative timings show that BV can operate at 26 frames/sec (fps), while TIS can achieve 33 fps. Thus, both algorithms can achieve real-time performance, and BV is the more compact.

©(2003) Society of Photo-Optical Instrumentation Engineers (SPIE)

Citation Download Citation

Khaled Benkrid and Danny Crookes "New bit-level algorithm for general purpose median filtering," Journal of Electronic Imaging 12(2), (1 April 2003). https://doi.org/10.1117/1.1557153

Published: 1 April 2003

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available