Abstract
Connectivity is a concept of great relevance to image processing and analysis. It is extensively used in image filtering and segmentation, image compression and coding, motion analysis, pattern recognition, and other applications. In this paper, we provide a theoretical tour of connectivity, with emphasis on those concepts of connectivity that are relevant to image processing and analysis. We review several notions of connectivity, which include classical topological and graph-theoretic connectivity, fuzzy connectivity, and the theories of connectivity classes and of hyperconnectivity. It becomes clear in this paper that the theories of connectivity classes and of hyperconnectivity unify all relevant notions of connectivity, and provide a solid theoretical foundation for studying classical and fuzzy approaches to connectivity, as well as for constructing new examples of connectivity useful for image processing and analysis applications.
Similar content being viewed by others
References
S.-Z. Bai and W.-L. Wang, “I type of strong connectivity in L-fuzzy topological spaces,” Fuzzy Sets and Systems, Vol. 99, pp. 357–362, 1998.
S. Beucher and F. Meyer, “The morphological approach to segmentation: The watershed transformation,” in Mathematical Morphology in Image Processing, E.R. Dougherty (Ed.), Marcel Dekker: New York City, New York, 1993, pp. 433–481.
G. Birkhoff, Lattice Theory, 3rd ed., Vol. 25, American Mathematical Society, Providence, Rhode Island, 1967.
U.M. Braga-Neto, “Connectivity in image processing and analysis: Theory, multiscale extensions, and applications,” PhD Thesis, Center for Imaging Science and Department of Electrical and Computer Engineering, The Johns Hopkins University, Baltimore, MD, 2001.
U.M. Braga-Neto and J. Goutsias, “Multiresolution connectivity: An axiomatic approach,” in Mathematical Morphology and its Applications to Image and Signal Processing, J. Goutsias, L. Vincent, and D.S. Bloomberg (Eds.), Kluwer Academic Publishers: Boston, MA, 2000, pp. 159–168.
U.M. Braga-Neto and J. Goutsias, “A complete lattice approach to connectivity in image analysis,” Technical Report ECE 00-05, Department of Electrical and Computer Engineering, The Johns Hopkins University, Baltimore, MD, 2000.
U.M. Braga-Neto and J. Goutsias, “On a general theory of connectivity in image analysis,” in Proceedings of the IEEEE-URASIP Workshop on Nonlinear Signal and Image Processing, Baltimore, MD, June 3–6, 2001. Available on CD-ROM.
U.M. Braga-Neto and J. Goutsias, “A multiscale approach to connectivity,” Computer Vision and Image Understanding, Vol. 89, pp. 70–107, 2003.
U.M. Braga-Neto and J. Goutsias, “Connectivity on complete lattices: New results,” Computer Vision and Image Understanding, Vol. 85, pp. 22–53, 2002.
C.L. Chang, “Fuzzy topological spaces,” Journal of Mathematical Analysis and Applications, Vol. 24, pp. 182–190, 1968.
S. Dellepiane and F. Fontana, “Extraction of intensity connectedness for image processing,” Pattern Recognition Letters, Vol. 16, pp. 313–324, 1995.
R. Diestel, Graph Theory, Springer-Verlag: New York City, NY, 1997.
J. Dugundji, Topology, Allyn and Bacon: Boston, MA, 1966.
U.V. Fatteh and D.S. Bassan, “Fuzzy connectedness and its stronger forms,” Journal of Mathematical Analysis and Applications, Vol. 111, pp. 449–464, 1985.
J.A. Goguen, “L-fuzzy sets,” Journal of Mathematical Analysis and Applications, Vol. 18, pp. 145–174, 1967.
H.J.A.M. Heijmans, Morphological Image Operators, Academic Press: Boston, MA, 1994.
H.J.A.M. Heijmans, “Connected morphological operators for binary images,” Computer Vision and Image Understanding, Vol. 73, pp. 99–120, 1999.
S.-G. Li, “Connectedness in L-fuzzy topological spaces,” Fuzzy Sets and Systems, Vol. 116, pp. 361–368, 2000.
R. Lowen, “Fuzzy topological spaces and fuzzy compactness,” Journal of Mathematical Analysis and Applications, Vol. 56, pp. 621–633, 1976.
R. Lowen, “A comparison of different compactness notions in fuzzy topological spaces,” Journal of Mathematical Analysis and Applications, Vol. 64, pp. 446–454, 1978.
R. Lowen, “Connectedness in fuzzy topological spaces,” Rocky Mountain Journal of Mathematics, Vol. 11, pp. 427–433, 1981.
G. Matheron, Random Sets and Integral Geometry, John Wiley: New York City, NY, 1975.
G. Matheron, “Remarques sur les fermetures-partitions,” Internal Report, Center of Geostatistics and Mathematical Morphology, Paris School of Mines, Fontainebleeau, France, 1985.
J.N. Mordeson and P.S. Nair, Fuzzy Mathematics: An Introduction for Engineers and Scientists, Physica-Verlag, Heidelberg, 1998.
J.R. Munkres, Topology: A First Course, Prentice Hall: Englewood Cliffs, NJ, 1975.
P.-M. Pu and Y.-M. Liu, “Fuzzy topology. I. Neighborhood structure of a fuzzy point and Moore-Smith convergence,” Journal of Mathematical Analysis and Applications, Vol. 76, pp. 571–599, 1980.
S.E. Rodabaugh, “Connectivity and the L-fuzzy unit interval,” Rocky Mountain Journal of Mathematics, Vol. 12, pp. 113–121, 1982.
C. Ronse, “Set-theoretical algebraic approaches to connectivity in continuous or digital spaces,” Journal of Mathematical Imaging and Vision, Vol. 8, pp. 41–58, 1998.
C. Ronse and J. Serra, “Geodesy and connectivity in lattices,” Fundamenta Informaticae, Vol. 46, pp. 349–395, 2001.
A. Rosenfeld, “Fuzzy graphs,” in Fuzzy Sets and Their Applications, L.A. Zadeh, K.S. Fu, and M. Shimura (Eds.), Academic Press, 1975, pp. 77–95.
A. Rosenfeld, “Fuzzy digital topology,” Information and Control, Vol. 40, pp. 76–87, 1979.
A. Rosenfeld, “On connectivity properties of grayscale pictures,” Pattern Recognition, Vol. 16, pp. 47–50, 1983.
A. Rosenfeld, “The fuzzy geometry of image subsets,” Pattern Recognition Letters, Vol. 2, pp. 311–317, 1984.
H.G. Senel, R.A. Peters, and B. Dawant, “Topological median filters,” IEEE Transactions on Image Processing,Vol. 11, pp. 89–104, 2002.
J. Serra, Image Analysis and Mathematical Morphology, Academic Press: London, UK, 1982.
J. Serra (Ed.), Image Analysis and Mathematical Morphology, Vol. 2: Theoretical Advances, Academic Press: London, UK, 1988.
J. Serra, “Connectivity on complete lattices,” in Mathematical Morphology and its Applications to Image and Signal Processing, P. Maragos, R.W. Schafer, and M.A. Butt (Eds.), Kluwer Academic Publishers: Boston, MA, 1996, pp. 81–96.
J. Serra, “Connectivity on complete lattices,” Journal of Mathematical Imaging and Vision, Vol. 9, pp. 231–251, 1998.
J. Serra, “Connections for sets and functions,” Fundamenta Informaticae, Vol. 41, pp. 147–186, 2000.
J.K. Udupa and S. Samarasekera, “Fuzzy connectedness and object definition: Theory, algorithms, and applications in image segmentation,” Graphical Models and Image Processing, Vol. 58, pp. 246–261, 1996.
L. Vincent, “Morphological area openings and closings for grey-scale images,” in Shape in Picture: Mathematical Description of Shape in Grey-level Images,Y.-L. O, A. Toet, D. Foster, H.J.A.M. Heijmans, and P. Meer (Eds.), Springer-Verlag: New York City, NY, 1994, pp. 197–208.
P. Wuyts, “On the determination of fuzzy topological spaces and fuzzy neighborhood spaces by their level-topologies,” Fuzzy Sets and Systems, Vol. 12, pp. 71–85, 1984.
R.T. Yeh and S.Y. Bang, “Fuzzy relations, fuzzy graphs, and their applications to clustering analysis,” in Fuzzy Sets and Their Applications, L.A. Zadeh, K.S. Fu, and M. Shimura (Eds.), Academic Press, 1975, pp. 125–149.
L.A. Zadeh, “Fuzzy sets,” Information and Control, Vol. 8, pp. 338–353, 1965.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Braga-Neto, U., Goutsias, J. A Theoretical Tour of Connectivity in Image Processing and Analysis. Journal of Mathematical Imaging and Vision 19, 5–31 (2003). https://doi.org/10.1023/A:1024476403183
Issue Date:
DOI: https://doi.org/10.1023/A:1024476403183