An Alternate Algorithm for (3x3) Median Filtering of Digital Images
DOI:
https://doi.org/10.24297/ijct.v1i1.6732Keywords:
Linear filtering, nonlinear filter, Median filter, bubble sort, Quick sort, computational cost, Algorithm complexityAbstract
Median filtering is a commonly used technique in image processing. The main problem of the median filter is its high computational cost (for sorting N pixels, the temporal complexity is O(N·log N), even with the most efficient sorting algorithms). When the median filter must be carried out in real time, the software implementation in general-purpose processors
does not usually give good results. This Paper presents an efficient algorithm for median filtering with a 3x3 filter kernel with only about 9 comparisons per pixel using spatial coherence between neighboring filter computations. The basic algorithm calculates two medians in one step and reuses sorted slices of three vertical neighboring pixels. An extension of this algorithm for 2D spatial coherence is also examined, which calculates four medians per step.
Downloads
References
Academic Press, Boston, 1990.
[2] [Paeth 1990] A. W. Paeth.Median finding on a 3x3 Grid. In Andrew Glassner, editor,Graphic Gems, pages 171-175.
Academic Press, Boston, 1990.
[3] L. Yin, R. Yang, M. Gabbouj, Y. Neuvo. “Weighted Median Filters: A Tutorialâ€, IEEE Trans. on Circuits and Systems,
43(3), pp. 157-192 (March 1996).
[4] T.S.Huang, G.J.Yang, G.Y.Tang, A fast two dimensional median filter algorithm, IEEE transactions on acoustics, speech
and signal processing, Vol ASSP 27 No 1, Feb 1979.
[5] Aho, Hopcroft, Ullman, The design and analysis of computer algorithms (p 102).
[6] The Image Processing Handbook, John C. Russ, CRC Press (second edition 1995)