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 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.
Perreault
Simon
S
Hébert
Patrick
P
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