Abstract
In this paper we propose an algorithm (EDAS-d) to approximate the jump discontinuity set of functions defined on subsets of ℝd. We have limited our study to the 1D (EDAS-1) and 2D (EDAS-2) versions of the algorithm. Theoretical and computational results prove its effectiveness in the case of piecewise continuous 1D functions and piecewise constant 2D functions. The algorithm is based on adaptive splitting of the domain of the function guided by the value of an average integral. EDAS-d exhibits a number of attractive features: accurate determination of the jump points, fast processing, absence of oscillatory behavior, precise determination of the magnitude of the jumps, and ability to differentiate between real jumps (discontinuities) and steep gradients. Moreover, low-dimensional versions of EDAS-d can be used for solving higher dimensional problems. Computational experiments also show that EDAS-d can be applied to solve some problems involving general piecewise continuous functions. EDAS-1 and EDAS-2 have been used to determine edges in 2D-images. The results are quite satisfactory for practical purposes.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alvarez, L., Lions, P.L., Morel, J.M.: Image selective smoothing and edge detection by nonlinear diffusion II. SIAM J. Numer. Anal. 29, 845–866 (1992)
Archibald, R., Gelb, A., Gottlieb, S., Ryan, J.: One-sided post-processing for the discontinuous Galerkin method using ENO type stencil choosing and the local edge detection method. J. Sci. Comput. 28, 167–190 (2006)
Archibald, R., Gelb, A., Yoon, J.: Polynomial fitting for edge detection in irregularly sampled signals and images. SIAM J. Numer. Anal. 43, 259–279 (2005)
Bänsch, E., Mikula, K.: A coarsening finite element in image selective smoothing. Comput. Vis. Sci. 1, 53–61 (1997)
Bänsch, E., Mikula, K.: Adaptivity in 3D image processing. Comput. Vis. Sci. 4, 21–30 (2001)
Berntsen, J., Espelid, T.O.: Error estimation in automatic quadrature routines. ACM Trans. Math. Softw. 17, 233–252 (1991)
Bliss, A., Su, F.E.: Lower bounds for simplicial covers and triangulations of cubes. Discrete Comput. Geom. 33, 669–686 (2005)
Bosnjak, A., Montilla, G., Villegas, R., Jara, I.: 3D segmentation with an application of level set-method using MRI volumes for image guided surgery. In: Proceedings of the 29th Annual International Conference of the IEEE EMBS, pp. 5263–5266, Lyon, France, August 23–26 (2007)
Catté, F., Lions, P.L., Morel, J.M., Coll, T.: Image selective smoothing and edge detection by nonlinear diffusion. SIAM J. Numer. Anal. 29, 182–193 (1992)
Chen, M.-H., Chin, R.T.: Partial smoothing splines for noisy + boundaries with corners. IEEE Trans. Pattern Anal. Mach. Intell. 15, 1208–1216 (1993)
Chen, G., Yang, Y.H.: Edge detection by regularized cubic B-spline fitting. IEEE Trans. Syst. Man Cybern. 25, 636–643 (1995)
Fujioka, H., Kano, H.: Extrema detection of optimal smoothing splines with application to edge detection problem. In: Proceedings of the 32nd Annual Conference on Industrial Electronics (IECON 2006), pp. 3294–3299. IEEE, New York (2006)
Gamelin, Th.W., Greene, R.E.: Introduction to Topology. Dover, New York, Mineola (1999)
Gelb, A., Tadmor, E.: Detection of edges in spectral data. Appl. Comput. Harmon. Anal. 7, 101–135 (1999)
Gelb, A., Tadmor, E.: Detection of edges in spectral data II. Nonlinear enhancement. SIAM J. Numer. Anal. 38, 1389–1408 (2000)
Gelb, A., Tadmor, E.: Adaptive edge detectors for piecewise smooth data based on the minmod limiter. J. Sci. Comput. 28, 279–306 (2006)
Gelb, A., Cates, D.: Detection of edges in spectral data III-refinement of the concentration method. J. Sci. Comput. 36, 1–43 (2008)
Gelb, A., Cates, D.: Segmentation of images from Fourier spectral data. Commun. Comput. Phys. 5, 326–34 (2009)
Gevers, T., Smeulders, A.W.M.: Combining region splitting and edge detection through guided Delaunay image subdivisions. In: IEEE Proceedings of CVPR, pp. 1021–1026 (1997)
González, R.C., Woods, R.E., Eddins, S.L.: Digital Image Processing using MATLAB. Prentice Hall, New York (2004)
Gottlieb, D., Shu, Ch.-W.: On the Gibbs phenomenon and its resolution. SIAM Rev. 39, 644–668 (1997)
Grundmann, A., Möller, H.M.: Invariant integration formulas for the n-simplex by combinatorial methods. SIAM J. Numer. Anal. 15, 282–290 (1978)
Guan, X., Guan, Z.: Edge detection of high resolution remote sensing imaginary using wavelet. In: Proceedings of the International Conference on Info-tech and Info-net (ICII 2001), vol. 1, pp. 302–307. IEEE, New York (2001)
Horowitz, S.L., Pavlidis, T.: Picture segmentation by a tree traversal algorithm. J. ACM 23, 368–388 (1975)
Kass, M., Witkin, A., Terzopoulos, D.: Snakes: Active contour models. Int. J. Comput. Vis. 1, 321–331 (1988)
Krylov, V.I.: Approximate Calculation of Integrals. Dover, New York (2005)
Lizier, M.A.S., Martins, D.C. Jr., Cuadros-Vargas, A.J., Cesar, R.M. Jr., Nonato, L.G.: Generated segmented meshes from textured color images. J. Vis. Commun. Image R. 20, 190–203 (2009)
Llanas, B., Lantarón, S., Sáinz, F.J.: Constructive approximation of discontinuous functions by neural networks. Neural Process. Lett. 27, 209–226 (2008)
Llanas, B., Sáinz, F.J.: Fast training of neural trees by adaptive splitting based on cubature. Neurocomputing 71, 3387–3408 (2008)
Meinhardt, E., Zacur, E., Frangi, A.F., Caselles, V.: 3D edge detection by selection of level surface patches. J. Math. Imaging Vis. 34, 1–16 (2009)
Orden, D., Santos, F.: Asymptotically efficient triangulations of the d-cube. Discrete Comput. Geom. 30, 509–528 (2003)
Paragios, N., Chen, Y., Faugeras, O. (eds.): Handbook of Mathematical Models in Computer Vision. Springer, Berlin (2006)
Pavlidis, T., Liow, Y.-T.: Integrating region growing and edge detection. IEEE Trans. Pattern Anal. Mach. Intell. 12, 225–233 (1990)
Perona, P., Malik, J.: Scale space and edge detection using anisotropic diffusion. In: Proceedings of the IEEE Workshop on Computer Vision, Miami, pp. 16–22 (1987)
Preußer, T., Rumpf, M.: An adaptive finite element method for large scale image processing. J. Vis. Commun. Image R. 11, 183–195 (2000)
Rumpf, M., Voigt, A., Berkels, B., Rätz, A.: Extracting grain boundaries and macroscopic deformations from images on atomic scale. J. Sci. Comput. 35, 1–23 (2008)
Subbotin, Y.N.: Error of the approximation by interpolation polynomials of small degrees on n-simplices. Math. Notes 48, 1030–1037 (1990)
Tang, Y.Y., Yang, L., Liu, J.: Quadratic spline wavelet approach to automatic extraction of baselines from document images. In: Proceedings of the Fourth International Conference on Document Analysis and Recognition, vol. 2, pp. 693–696. IEEE, New York (1997)
Wu, X.: Adaptive split-and-merge segmentation based on piecewise least-square approximation. IEEE Trans. Pattern Anal. Mach. Intell. 15, 808–815 (1993)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Llanas, B., Lantarón, S. Edge Detection by Adaptive Splitting. J Sci Comput 46, 485–518 (2011). https://doi.org/10.1007/s10915-010-9416-8
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10915-010-9416-8