Median Filtering in Constant Time

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...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on image processing 2007-09, Vol.16 (9), p.2389-2394
Main Authors: Perreault, S., Hebert, P.
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Algorithms
Applied sciences
Approximation
Complexity
Complexity theory
Computer Graphics
Detection, estimation, filtering, equalization, prediction
Exact sciences and technology
Filtering
Filtering algorithms
Filtering theory
Filters
Filtration
Histograms
Image Enhancement - methods
Image Interpretation, Computer-Assisted - methods
Image processing
Information, signal and communications theory
Kernel
Kernels
median filters
Numerical Analysis, Computer-Assisted
Pressing
Reproducibility of Results
Runtime
Sensitivity and Specificity
Signal and communications theory
Signal processing
Signal, noise
Telecommunications and information theory
Time Factors
User-Computer Interface
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1057-7149
1941-0042
DOI:10.1109/TIP.2007.902329