Efficient image segmentation using partial differential equations and morphology. (English) Zbl 1003.68712

Summary: The goal of this paper is to investigate segmentation methods that combine fast preprocessing algorithms using Partial Differential Equations (PDEs) with a watershed transformation with region merging. We consider two well-founded PDE methods: a nonlinear isotropic diffusion filter that permits edge enhancement, and a convex nonquadratic variational image restoration method which gives good denoising. For the diffusion filter, an efficient algorithm is applied using an Additive Operator Splitting (AOS) that leads to recursive and separable filters. For the variational restoration method, a novel algorithm is developed that uses AOS schemes within a Gaussian pyramid decomposition. Examples demonstrate that preprocessing by these PDE techniques significantly improves the watershed segmentation, and that the resulting segmentation method gives better results than some traditional techniques. The algorithm has linear complexity and it can be used for arbitrary dimensional data sets. The typical CPU time for segmenting a \(256^2\) image on a modern PC is far below 1 s.


68U99 Computing methodologies and applications
68U10 Computing methodologies for image processing
68T10 Pattern recognition, speech recognition
Full Text: DOI


[1] V. Caselles, J.M. Morel, G. Sapiro, A. Tannenbaum (Eds.), Partial Differential Equations and Geometry-Driven Diffusion in Image Processing and Analysis (special issue), IEEE Trans. Image Process. 7 (3) (1998) 269-473.
[2] B. ter Haar Romeny, L. Florack, J. Koenderink, M. Viergever (Eds.), Scale-Space Theory in Computer Vision, Lecture Notes in Computer Science, Vol. 1252, Springer, Berlin, 1997.
[3] M. Nielsen, P. Johansen, O.F. Olsen, J. Weickert (Eds.), Scale-Space Theories in Computer Vision, Lecture Notes in Computer Science, Vol. 1682, Springer, Berlin, 1999.
[4] J. Weickert, Anisotropic Diffusion in Image Processing, ECMI Series, Teubner, Stuttgart, 1998. · Zbl 0886.68131
[5] 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) · Zbl 0746.65091
[6] Schnörr, C., Unique reconstruction of piecewise smooth images by minimizing strictly convex non-quadratic functionals, J. math. imaging vision, 4, 189-198, (1994)
[7] P. Charbonnier, L. Blanc-Féraud, G. Aubert, M. Barlaud, Two deterministic half-quadratic regularization algorithms for computed imaging, Proceedings of IEEE International Conference on Image Processing (ICIP-94, Austin, November 13-16, 1994), Vol. 2, IEEE Computer Society Press, Los Alamitos, 1994, pp. 168-172.
[8] Weickert, J.; ter Haar Romeny, B.M.; Viergever, M.A., Efficient and reliable schemes for nonlinear diffusion filtering, IEEE trans. image process., 7, 398-410, (1998)
[9] Acton, S.T., Multigrid anisotropic diffusion, IEEE trans. image process., 7, 280-291, (1998)
[10] Orphanoudakis, S.C.; Tziritas, G.; Haris, K., A hybrid algorithm for the segmentation of 2D and 3D medical images, (), 385-386
[11] D. De Vleeschauer, F.A. Cheikh, R. Hamila, M. Gabbouj, Watershed segmentation of an image enhanced by Teager energy driven diffusion, Proceedings of Sixth International Conference on Image Processing and its Applications (IPA 97, Dublin, July 15-17, 1997), 1997, pp. 254-258.
[12] Sijbers, J.; Scheunders, P.; Verhoye, M.; Van der Linden, A.; Van Dyck, D.; Raman, E., Watershed-based segmentation of 3D MR data for volume quantization, Magn. reson. imaging, 15, 679-688, (1997)
[13] Griffin, L.D.; Colchester, A.C.F.; Robinson, G.P., Scale and segmentation of gray-level images using maximum gradient paths, Image vision comput., 10, 389-402, (1992)
[14] Olsen, O.F., Multiscale watershed segmentation, (), 191-200
[15] M. Sramek, T. Wrbka, Watershed based image segmentation — an effective tool for detecting landscape structure, in: E. Wenger, L.I. Dimitrov (Eds.), Sixth International Workshop on Digital Image Processing and Computer Graphics: Applications in Humanities and Natural Sciences, SPIE Vol. 3346, 1997, pp. 227-235.
[16] Olsen, O.F.; Sporring, J., Segmenting by compression using linear scale-space and the watersheds, (), 513-518
[17] Jackway, P.T., Gradient watersheds in morphological scale-space, IEEE trans. image process., 5, 913-921, (1996)
[18] Niessen, W.J.; Vincken, K.L.; Weickert, J.; Viergever, M.A., Nonlinear multiscale representations for image segmentation, Comput. vision image understanding, 66, 233-245, (1997)
[19] W.J. Niessen, K.L. Vincken, J. Weickert, B.M. ter Haar Romeny, M.A. Viergever, Multiscale segmentation of three-dimensional MR brain images, Int. J. Comput. Vision 31 (1999) 185-202.
[20] Weickert, J., Fast segmentation methods based on partial differential equations and the watershed transformation, (), 93-100
[21] Perona, P.; Malik, J., Scale space and edge detection using anisotropic diffusion, IEEE trans. pattern anal. Mach. intell., 12, 629-639, (1990)
[22] R. Deriche, O. Faugeras, Les EDP en traitement des images et vision par ordinateur, Traitement du Signal 13 (6) (1996).
[23] Nashed, M.Z.; Scherzer, O., Least squares and bounded variation regularization with nondifferentiable functionals, Numer. funct. anal. optim., 19, 873-901, (1998) · Zbl 0914.65067
[24] Scherzer, O.; Weickert, J., Relations between regularization and diffusion filtering, J. math. imaging vision, 12, 43-63, (2000) · Zbl 0945.68183
[25] Nordström, N., Biased anisotropic diffusion — a unified regularization and diffusion approach to edge detection, Image vision comput., 8, 318-327, (1990)
[26] Geiger, D.; Yuille, A., A common framework for image segmentation, Int. J. comput. vision, 6, 227-243, (1991)
[27] Weickert, J., Theoretical foundations of anisotropic diffusion in image processing, Computing, 11, Suppl., S221-S236, (1996)
[28] Marchuk, G.I., Splitting and alternating direction methods, (), 197-462 · Zbl 0875.65049
[29] J. Weickert, J. Heers, C. Schnörr, K.J. Zuiderveld, O. Scherzer, H.S. Stiehl, Fast parallel algorithms for a broad class of nonlinear variational diffusion approaches, Real-Time Imaging, in press.
[30] Burt, P.J.; Adelson, E.H., The Laplacian pyramid as a compact image code, IEEE trans. commun., 31, 532-540, (1983)
[31] Canny, J., A computational approach to edge detection, IEEE trans. pattern anal. Mach. intell., 8, 679-698, (1986)
[32] S. Beucher, C. Lantuéjoul, Use of watersheds in contour detection, Proceedings of International Workshop on Image Processing, Real-Time Edge and Motion Detection/Estimation (Rennes, September 17-21, 1979), IRISA Report No. 131, 2.1-2.12, 1979.
[33] Meyer, F.; Beucher, S., Morphological segmentation, J. visual commun. image repr., 1, 21-46, (1990)
[34] Marr, D.; Hildreth, E., Theory of edge detection, Proc. roy. soc. London ser. B, 207, 187-217, (1980)
[35] Najman, L.; Schmitt, M., Watershed of a continuous function, Signal processing, 38, 99-112, (1994)
[36] Torre, V.; Poggio, T.A., On edge detection, IEEE trans. pattern anal. Mach. intell., 8, 148-163, (1986)
[37] J. Fairfield, Toboggan contrast enhancement for contrast segmentation, Proceedings of 10th International Conference on Pattern Recognition (ICPR 10, Atlantic City, June 16-21, 1990), Vol. 1, IEEE Computer Society Press, Los Alamitos, 1990, pp. 712-716.
[38] Oltmans, H., A watershed algorithm, project work, laboratory of technomathematics, (1993), University of Kaiserslautern Germany
[39] Najman, L.; Schmitt, M., Geodesic saliency of watershed contours and hierarchical segmentation, IEEE trans. pattern anal. Mach. intell., 18, 1163-1173, (1996)
[40] Vincent, L.; Soille, P., Watersheds in digital spaces: an efficient algorithm based on immersion simulation, IEEE trans. pattern anal. Mach. intell., 13, 583-589, (1991)
[41] Maes, F.; Vandermeulen, D.; Suetens, P.; Marchal, G., Computer-aided interactive object delineation using an intelligent paintbrush technique, (), 77-83
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.