ABSTRACT

Median filtering is a cornerstone of modern image processing and is used extensively in smoothing and de-noising applications. The fastest commercial implementations (e.g. in Adobe® Photoshop® CS2) exhibit O(r) runtime in the radius of the filter, which limits their usefulness in realtime or resolution-independent contexts. We introduce a CPU-based, vectorizable O(log r) algorithm for median filtering, to our knowledge the most efficient yet developed. Our algorithm extends to images of any bit-depth, and can also be adapted to perform bilateral filtering. On 8-bit data our median filter outperforms Photoshop's implementation by up to a factor of fifty.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

1   Alparone, L., Cappellini, V., and Garzelli, A. 1994. A coarse-to-fine algorithm for fast median filtering of image data with a huge number of levels. Signal Processing, Vol. 39 No. 1-2, pp. 33--41.

2   Cooley, J. H. and Tukey, J. 1965. An Algorithm for the Machine Calculation of the Complex Fourier series. Mathematics of Computation, vol. 19, pp. 297--301.

3   Durand, F. and Dorsey, J. 2002. Fast Bilateral Filtering for the Display of High-Dynamic-Range Images. ACM SIGGRAPH 2002.

4   Heckbert, P. 1986. Filtering by Repeated Integration. ACM SIGGRAPH 1986.

5   Huang, T. S. 1981. Two-Dimensional Signal Processing II: Transforms and Median Filters. Berlin: Springer-Verlag, pp. 209--211.

6   Gil, J. and Werman, M. 1993. Computing 2-D Min, Median, and Max Filters. IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 15 No. 5, pp. 504--507.

7   Kabir, I. 1996. High Performance Computer Imaging. Greenwich, CT. Manning Publications. pp. 181--192.

8   Paris, S. and Durand, F. 2006. A Fast Approximation of the Bilateral Filter using a Signal Processing Approach. ECCV 2006.

9   Pha, T. Q. and Vliet, L. J. V. 2005. Separable bilateral filtering for fast video preprocessing. IEEE Int. Conf. on Multimedia & Expo. CD1-4.

10   Ranka, S. and Sahni, S. 1989. Efficient Serial and Parallel Algorithms for Median Filtering. Proceeding 1989 International Conference on Parallel Processing, III-56--III-62.

11   Terdiman, P. 2000. Radix Sort Revisited. <http://www.codercorner.com/RadixSortRevisited.htm>

12   Tanimoto, S. L. 1995. Fast Median Filtering Algorithms for Mesh Computers. Pattern Recognition, vol. 28, no. 12, pp. 1965--1972.

13   Tomasi, C. and Manduchi, R. 1998. Bilateral filtering for gray and color images. In Proc. IEEE Int. Conf. on Computer Vision, 836--846.

14   Tukey, J. W. 1977. Exploratory Data Analysis. Reading, MA. Addison-Wesley.

15   Weiss, B. 2006. Method and Apparatus for Processing Image Data. US Patent 7,010,163.

16   Wu, C. H. and Horng, S. J. 2003. Fast and Scalable Selection Algorithms with Applications to Median Filtering. IEEE Transactions on Parallel and Distributed Systems, vol. 14, no. 10, pp. 983--992.