Ben Weiss
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.
Supplemental Material
- 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 Scholar
Digital Library
- 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
- Durand, F. and Dorsey, J. 2002. Fast Bilateral Filtering for the Display of High-Dynamic-Range Images. ACM SIGGRAPH 2002. Google ScholarDigital Library
- Heckbert, P. 1986. Filtering by Repeated Integration. ACM SIGGRAPH 1986. Google ScholarDigital Library
- Huang, T. S. 1981. Two-Dimensional Signal Processing II: Transforms and Median Filters. Berlin: Springer-Verlag, pp. 209--211. Google ScholarDigital Library
- 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
- Kabir, I. 1996. High Performance Computer Imaging. Greenwich, CT. Manning Publications. pp. 181--192. Google ScholarDigital Library
- Paris, S. and Durand, F. 2006. A Fast Approximation of the Bilateral Filter using a Signal Processing Approach. ECCV 2006.Google Scholar
- 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
- 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
- Terdiman, P. 2000. Radix Sort Revisited. <http://www.codercorner.com/RadixSortRevisited.htm>Google Scholar
- Tanimoto, S. L. 1995. Fast Median Filtering Algorithms for Mesh Computers. Pattern Recognition, vol. 28, no. 12, pp. 1965--1972.Google ScholarDigital Library
- 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
- Tukey, J. W. 1977. Exploratory Data Analysis. Reading, MA. Addison-Wesley.Google Scholar
- Weiss, B. 2006. Method and Apparatus for Processing Image Data. US Patent 7,010,163.Google Scholar
- 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
Index Terms
- Fast median and bilateral filtering
Recommendations
Fast median and bilateral filtering
SIGGRAPH '06: ACM SIGGRAPH 2006 PapersMedian 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 ...
Constant Time Median and Bilateral Filtering
This paper formulates both the median filter and bilateral filter as a cost volume aggregation problem whose computational complexity is independent of the filter kernel size. Unlike most of the previous works, the proposed framework results in a ...
Comments