An Alternate Algorithm for (3x3) Median Filtering of Digital Images

Median filtering is a commonly used technique in imageprocessing. The main problem of the median filter is its highcomputational cost (for sorting N pixels, the temporalcomplexity is O(N?log N), even with the most efficient sortingalgorithms). When the median filter must be carried out in realtime, the software implementation in general-purpose processorsdoes not usually give good results. This Paper presents anefficient algorithm for median filtering with a 3x3 filter kernelwith only about 9 comparisons per pixel using spatial coherencebetween neighboring filter computations. The basic algorithmcalculates two medians in one step and reuses sorted slices ofthree vertical neighboring pixels. An extension of this algorithmfor 2D spatial coherence is also examined, which calculates fourmedians per step.