zbMATH — the first resource for mathematics

Does median filtering truly preserve edges better than linear filtering? (English) Zbl 1160.62086
Summary: Image processing researchers commonly assert that “median filtering is better than linear filtering for removing noise in the presence of edges.” Using a straightforward large-\(n\) decision-theory framework, this folk-theorem is seen to be false in general. We show that median filtering and linear filtering have similar asymptotic worst-case mean-squared error (MSE) when the signal-to-noise ratio (SNR) is of order 1, which corresponds to the case of constant per-pixel noise level in a digital signal. To see dramatic benefits of median smoothing in an asymptotic setting, the per-pixel noise level should tend to zero (i.e., the SNR should grow very large).
We show that a two-stage median filtering using two very different window widths can dramatically outperform traditional linear and median filtering in settings where the underlying object has edges. In this two-stage procedure, the first pass, at a fine scale, aims at increasing the SNR. The second pass, at a coarser scale, correctly exploits the nonlinearity of the median.
Image processing methods based on nonlinear partial differential equations (PDEs) are often said to improve on linear filtering in the presence of edges. Such methods seem difficult to analyze rigorously in a decision-theoretic framework. A popular example is the mean curvature motion (MCM), which is formally a kind of iterated median filtering. Our results on iterated median filtering suggest that some PDE-based methods are candidates to rigorously outperform linear filtering in an asymptotic framework.

62M40 Random fields; image analysis
62G08 Nonparametric regression and quantile regression
62M20 Inference from stochastic processes and prediction
62G20 Asymptotic properties of nonparametric inference
62C20 Minimax procedures in statistical decision theory
35Q80 Applications of PDE in areas other than physics (MSC2000)
60G35 Signal detection and filtering (aspects of stochastic processes)
Full Text: DOI arXiv
[1] Anonymous. (2007). Median filter. Wikipedia.
[2] Barner, K. and Arce, G. R. (2003). Nonlinear Signal and Image Processing : Theory , Methods , and Applications . CRC Press, Boca Raton, FL.
[3] Bottema, M. J. (1991). Deterministic properties of analog median filters. IEEE Trans. Inform. Theory 37 1629-1640. · Zbl 0748.93073
[4] Brandt, J. (1998). Cycles of medians. Util. Math. 54 111-126. · Zbl 1109.94310
[5] Candès, E. J. and Donoho, D. L. (2002). Recovering edges in ill-posed inverse problems: Optimality of curvelet frames. Ann. Statist. 30 784-842. · Zbl 1101.62335
[6] Candès, E. J. and Donoho, D. L. (2002). Recovering edges in ill-posed inverse problems: Optimality of curvelet frames. Ann. Statist. 30 784-842. · Zbl 1101.62335
[7] Cao, F. (1998). Partial differential equations and mathematical morphology. J. Math. Pures Appl. 77 909-941. · Zbl 0920.35040
[8] Caselles, V., Sapiro, G. and Chung, D. H. (2000). Vector median filters, inf-sup operations, and coupled PDEs: Theoretical connections. J. Math. Imaging Vision 12 109-119. · Zbl 0955.68116
[9] Donoho, D. L. (1999). Wedgelets: Nearly minimax estimation of edges. Ann. Statist. 27 859-897. · Zbl 0957.62029
[10] Donoho, D. L. and Johnstone, I. M. (1998). Minimax estimation via wavelet shrinkage. Ann. Statist. 26 879-921. · Zbl 0935.62041
[11] Donoho, D. L., Johnstone, I. M., Kerkyacharian, G. and Picard, D. (1995). Wavelet shrinkage: Asymptopia? J. Roy. Statist. Soc. Ser. B 57 301-369. JSTOR: · Zbl 0827.62035
[12] Donoho, D. L. and Yu, T. P.-Y. (2000). Nonlinear pyramid transforms based on median-interpolation. SIAM J. Math. Anal. 31 1030-1061. · Zbl 0953.42017
[13] Fan, J. and Hall, P. (1994). On curve estimation by minimizing mean absolute deviation and its implications. Ann. Statist. 22 867-885. · Zbl 0806.62030
[14] Gu, J., Meng, M., Cook, A. and Faulkner, M. G. (2000). Analysis of eye tracking movements using fir median hybrid filters. In ETRA ’00 : Proceedings of the 2000 symposium on Eye tracking research and applications 65-69. ACM Press, New York.
[15] Guichard, F. and Morel, J.-M. (1997). Partial differential equations and image iterative filtering. In The State of the Art in Numerical Analysis ( York , 1996). Inst. Math. Appl. Conf. Ser. New Ser. 63 525-562. Oxford Univ. Press, New York. · Zbl 0881.65122
[16] Gupta, M. and Chen, T. (2001). Vector color filter array demosaicing. In Sensors and Camera Systems for Scientific , Industrial , and Digital Photography Applications . II (M. B. J. C. N. Sampat, ed.). Proceedings of the SPIE 4306 374-382. SPIE, Bellingham, WA.
[17] Hamza, A. B., Luque-Escamilla, P. L., Martínez-Aroza, J. and Román-Roldán, R. (1999). Removing noise and preserving details with relaxed median filters. J. Math. Imaging Vision 11 161-177.
[18] Huber, P. J. (1964). Robust estimation of a location parameter. Ann. Math. Statist. 35 73-101. · Zbl 0136.39805
[19] Justusson, B. (1981). Median filtering: Statistical properties. In Two-Dimensional Digital Signal Processing. II (T. S. Huang, ed.). Topics in Applied Physics 43 161-196. Springer, Berlin.
[20] Koch, I. (1996). On the asymptotic performance of median smoothers in image analysis and nonparametric regression. Ann. Statist. 24 1648-1666. · Zbl 0867.62031
[21] Korostelev, A. P. and Tsybakov, A. B. (1993). Minimax Theory of Image Reconstruction. Lecture Notes in Statistics 82 . Springer, New York. · Zbl 0833.62039
[22] Mallows, C. L. (1979). Some theoretical results on Tukey’s 3 R smoother. In Smoothing Techniques for Curve Estimation ( Proc. Workshop , Heidelberg , 1979). Lecture Notes in Math. 757 77-90. Springer, Berlin. · Zbl 0427.93050
[23] Mason, D. M. (1984). Weak convergence of the weighted empirical quantile process in L 2 (0, 1). Ann. Probab. 12 243-255. · Zbl 0543.60010
[24] Matheron, G. (1975). Random Sets and Integral Geometry . Wiley, New York. · Zbl 0321.60009
[25] Morel, J.-M. and Solimini, S. (1995). Variational Methods in Image Segmentation . Birkhäuser Boston, Boston, MA. · Zbl 0827.68111
[26] Mumford, D. and Shah, J. (1989). Optimal approximations by piecewise smooth functions and associated variational problems. Comm. Pure Appl. Math. 42 577-685. · Zbl 0691.49036
[27] Perona, P. and Malik, J. (1990). Scale-space and edge detection using anisotropic diffusion. IEEE Trans. Pattern Anal. Mach. Intell. 12 629-639.
[28] Piterbarg, L. I. (1984). Median filtering of random processes. Problemy Peredachi Informatsii 20 65-73. · Zbl 0548.60044
[29] Rousseeuw, P. J. and Bassett, G. W. Jr. (1990). The remedian: A robust averaging method for large data sets. J. Amer. Statist. Assoc. 85 97-104. JSTOR: · Zbl 0702.62030
[30] Rousseeuw, P. J. and Bassett, G. W. Jr. (1990). The remedian: A robust averaging method for large data sets. J. Amer. Statist. Assoc. 85 97-104. JSTOR: · Zbl 0702.62030
[31] Sapiro, G. (2001). Geometric Partial Differential Equations and Image Analysis . Cambridge Univ. Press, Cambridge. · Zbl 0968.35001
[32] Semmes, S. W. (1988). Quasiconformal mappings and chord-arc curves. Trans. Amer. Math. Soc. 306 233-263. JSTOR: · Zbl 0653.30008
[33] Serra, J. (1982). Image Analysis and Mathematical Morphology . Academic Press, London. · Zbl 0565.92001
[34] Sethian, J. A. (1999). Level Set Methods and Fast Marching Methods , 2nd ed. Cambridge Monographs on Applied and Computational Mathematics 3 . Cambridge Univ. Press, Cambridge. · Zbl 0929.65066
[35] Shorack, G. R. and Wellner, J. A. (1986). Empirical Processes with Aplications to Statistics . Wiley, New York. · Zbl 1170.62365
[36] Stranneby, D. (2001). Digital Signal Processing : DSP and Applications . Oxford Univ. Press, London, UK.
[37] Tukey, J. W. (1977). Exploratory Data Analysis . Addison-Wesley, Reading, MA. · Zbl 0409.62003
[38] Velleman, P. and Hoaglin, D. (1981). Applications , Basics , and Computing of Exploratory Data Analysis . Duxbury, North Scituate, MA.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.