DESIGN AND IMPLEMENTATION

New bit-level algorithm for general purpose median filtering

[+] Author Affiliations
Khaled Benkrid, Danny Crookes

Queen’s University of Belfast, School of Computer Science, 18 Malone Road, Belfast, BT7?1NN, Northern Ireland, United Kingdom E-mail: k.benkrid@qub.ac.uk

J. Electron. Imaging. 12(2), 263-269 (Apr 01, 2003). doi:10.1117/1.1557153
History: Received Apr. 5, 2002; Revised Oct. 31, 2002; Accepted Nov. 8, 2002; Online April 11, 2003
Text Size: A A A

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(N2) 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 SPIE and IS&T.

© 2003 SPIE and IS&T

Citation

Khaled Benkrid and Danny Crookes
"New bit-level algorithm for general purpose median filtering", J. Electron. Imaging. 12(2), 263-269 (Apr 01, 2003). ; http://dx.doi.org/10.1117/1.1557153


Access This Article
Sign in or Create a personal account to Buy this article ($20 for members, $25 for non-members).

Some tools below are only available to our subscribers or users with an online account.

Related Content

Customize your page view by dragging & repositioning the boxes below.

Related Book Chapters

Topic Collections

PubMed Articles
Advertisement
  • Don't have an account?
  • Subscribe to the SPIE Digital Library
  • Create a FREE account to sign up for Digital Library content alerts and gain access to institutional subscriptions remotely.
Access This Article
Sign in or Create a personal account to Buy this article ($20 for members, $25 for non-members).
Access This Proceeding
Sign in or Create a personal account to Buy this article ($15 for members, $18 for non-members).
Access This Chapter

Access to SPIE eBooks is limited to subscribing institutions and is not available as part of a personal subscription. Print or electronic versions of individual SPIE books may be purchased via SPIE.org.