Median Filtering in Constant Time
Authors:
- Simon PerreaultSPSimon Perreault
- Patrick HebertPHPatrick Hebert
- 13 August 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Image Processing
- Vol. 16 (9) , 2389-2394
Abstract
The median filter is one of the basic building blocks in many image processing situations. However, its use has long been hampered by its algorithmic complexity O(tau) of in the kernel radius. With the trend toward larger images and proportionally larger filter kernels, the need for a more efficient median filtering algorithm becomes pressing. In this correspondence, a new, simple, yet much faster, algorithm exhibiting O(1) runtime complexity is described and analyzed. It is compared and benchmarked against previous algorithms. Extensions to higher dimensional or higher precision data and an approximation to a circular kernel are presented, as well.Keywords
This publication has 9 references indexed in Scilit:
- Fast median and bilateral filteringACM Transactions on Graphics, 2006
- Involvement of peripheral benzodiazepine receptors in the protection of hematopoietic cells against oxygen radical damageBlood, 1996
- A coarse-to-fine algorithm for fast median filtering of image data with a huge number of levelsSignal Processing, 1994
- Computing 2-D min, median, and max filtersIEEE Transactions on Pattern Analysis and Machine Intelligence, 1993
- Three‐dimensional ultrasound of fetal surface featuresUltrasound in Obstetrics & Gynecology, 1992
- Multistage order statistic filters for image sequence processingIEEE Transactions on Signal Processing, 1991
- An efficient algorithm for running window pel gray level ranking in 2-D imagesPattern Recognition Letters, 1990
- Morphological filters--Part II: Their relations to median, order-statistic, and stack filtersIEEE Transactions on Acoustics, Speech, and Signal Processing, 1987
- A fast two-dimensional median filtering algorithmIEEE Transactions on Acoustics, Speech, and Signal Processing, 1979