“Fast median and bilateral filtering” by Weiss

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.

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. Google ScholarDigital Library
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.Google ScholarCross Ref
3. Durand, F. and Dorsey, J. 2002. Fast Bilateral Filtering for the Display of High-Dynamic-Range Images. ACM SIGGRAPH 2002. Google ScholarDigital Library
4. Heckbert, P. 1986. Filtering by Repeated Integration. ACM SIGGRAPH 1986. Google ScholarDigital Library
5. Huang, T. S. 1981. Two-Dimensional Signal Processing II: Transforms and Median Filters. Berlin: Springer-Verlag, pp. 209–211. Google ScholarDigital Library
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. Google ScholarDigital Library
7. Kabir, I. 1996. High Performance Computer Imaging. Greenwich, CT. Manning Publications. pp. 181–192. Google ScholarDigital Library
8. Paris, S. and Durand, F. 2006. A Fast Approximation of the Bilateral Filter using a Signal Processing Approach. ECCV 2006.Google Scholar
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.Google Scholar
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.Google Scholar
11. Terdiman, P. 2000. Radix Sort Revisited. <http://www.codercorner.com/RadixSortRevisited.htm>Google Scholar
12. Tanimoto, S. L. 1995. Fast Median Filtering Algorithms for Mesh Computers. Pattern Recognition, vol. 28, no. 12, pp. 1965–1972.Google ScholarDigital Library
13. Tomasi, C. and Manduchi, R. 1998. Bilateral filtering for gray and color images. In Proc. IEEE Int. Conf. on Computer Vision, 836–846. Google ScholarDigital Library
14. Tukey, J. W. 1977. Exploratory Data Analysis. Reading, MA. Addison-Wesley.Google Scholar
15. Weiss, B. 2006. Method and Apparatus for Processing Image Data. US Patent 7,010,163.Google Scholar
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. Google ScholarDigital Library