title: Median filtering in constant time.
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 of O (r) 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.
authors.forename: Simon
authors.initials: S
authors.lastname: Perreault
authors.forename: Patrick
authors.initials: P
authors.lastname: Hébert
mesh_terms: D000465:Algorithms; D003196:Computer Graphics; D007089:Image Enhancement / Q000379:methods*; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D009716:Numerical Analysis, Computer-Assisted; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D013997:Time Factors; D014584:User-Computer Interface