Equivalence between digital well-composedness and well-composedness in the sense of Alexandrov on \(n\)-d cubical grids. (English) Zbl 1497.68508
Summary: Among the different flavors of well-composednesses on cubical grids, two of them, called, respectively, digital well-composedness (DWCness) and well-composedness in the sense of Alexandrov (AWCness), are known to be equivalent in 2D and in 3D. The former means that a cubical set does not contain critical configurations, while the latter means that the boundary of a cubical set is made of a disjoint union of discrete surfaces. In this paper, we prove that this equivalence holds in \(n\)-D, which is of interest because today images are not only 2D or 3D but also 4D and beyond. The main benefit of this proof is that the topological properties available for AWC sets, mainly their separation properties, are also true for DWC sets, and the properties of DWC sets are also true for AWC sets: an Euler number locally computable, equivalent connectivities from a local or global point of view. This result is also true for gray-level images thanks to cross section topology, which means that the sets of shapes of DWC gray-level images make a tree like the ones of AWC gray-level images.
MSC:
| 68U03 | Computational aspects of digital topology |
| 54H30 | Applications of general topology to computer science (e.g., digital topology, image processing) |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68U10 | Computing methodologies for image processing |
References:
| [1] | Alexandrov, PS, Diskrete Räume, Matematicheskii Sbornik, 2, 3, 501-519 (1937) · Zbl 0018.09105 |
| [2] | Alexandrov, PS, Combinatorial Topology (2011), New York: Dover Publications, New York |
| [3] | Alexandrov, PS; Hopf, H., Topologie I, volume 45 of Die grundlehren der mathematischen wissenschaften in einzeldarstellungen (1945), Berlin: Springer, Berlin |
| [4] | Aubin, J-P; Frankowska, H., Set-valued Analysis (2009), Berlin: Springer, Berlin |
| [5] | Bertrand, G.: New notions for discrete topology. In: Discrete Geometry for Computer Imagery, volume 1568 of Lecture Notes in Computer Science Series, pp. 218-228. Springer, Berlin (1999) · Zbl 0935.68116 |
| [6] | Bertrand, G., Everat, J.-C., Couprie, M.: Topological approach to image segmentation. In: SPIE’s International Symposium on Optical Science, Engineering, and Instrumentation, volume 2826 of Vision Geometry V, pp. 65-76. International Society for Optics and Photonics (1996) |
| [7] | Bertrand, G.; Everat, J-C; Couprie, M., Image segmentation through operators based on topology, J. Electron. Imaging, 6, 4, 395-405 (1997) · doi:10.1117/12.276856 |
| [8] | Beucher, S.; Meyer, F., The morphological approach to segmentation: the watershed transformation, Opt. Eng., 34, 433-433 (1992) |
| [9] | Boutry, N.: A Study of Well-Composedness in \(n\)-D. Ph.D. thesis, Université Paris-Est, Noisy-Le-Grand, France, December (2016) |
| [10] | Boutry, N., Géraud, T., Najman, L. How to make \(n\)-D functions digitally well-composed in a self-dual way. In: International Symposium on Mathematical Morphology and Its Applications to Signal and Image Processing, volume 9082 of Lecture Notes in Computer Science Series, pp. 561-572. Springer, Berlin (2015) · Zbl 1445.68243 |
| [11] | Boutry, N.; Géraud, T.; Najman, L., A tutorial on well-composedness, J. Math. Imaging Vis., 60, 443-478 (2017) · Zbl 1435.68337 · doi:10.1007/s10851-017-0769-6 |
| [12] | Boutry, Nicolas, Géraud, Thierry, Najman, Laurent: How to make \(n\)-D plain maps defined on discrete surfaces Alexandrov-well-composed in a self-dual way, J. Math. Imaging Vis., 10, 849-873 (2019) · Zbl 1446.68176 · doi:10.1007/s10851-019-00873-4 |
| [13] | Daragon, X.: Surfaces discrètes et frontières d’objets dans les ordres. Ph.D. thesis, Université de Marne-la-Vallée (2005) |
| [14] | Daragon, X., Couprie, M., Bertrand, G.: Discrete frontiers. In: Discrete geometry for computer imagery, volume 2886 of Discrete Geometry for Computer Imagery, pp. 236-245. Springer (2003) · Zbl 1254.68298 |
| [15] | Eckhardt, U.; Latecki, LJ, Digital Topology (1994), New York: Institut für Angewandte Mathematik, New York |
| [16] | Evako, AV; Kopperman, R.; Mukhin, YV, Dimensional properties of graphs and digital spaces, J. Math. Imaging Vis., 6, 2-3, 109-119 (1996) · Zbl 1191.05088 · doi:10.1007/BF00119834 |
| [17] | Géraud, T., Carlinet, E., Crozet, S., Najman, L.: A quasi-linear algorithm to compute the tree of shapes of \(n\)-D images. In: International Symposium on Mathematical Morphology and Its Applications to Signal and Image Processing, volume 7883 of Lecture Notes in Computer Science Series, pp. 98-110. Springer (2013) · Zbl 1382.68261 |
| [18] | Géraud, T., Xu, Y., Carlinet, E., Boutry, N.: Introducing the dahu pseudo-distance. In: International Symposium on Mathematical Morphology and Its Applications to Signal and Image Processing, pp. 55-67. Springer (2017) · Zbl 1479.94027 |
| [19] | Huynh, L.D., Xu, Y., Géraud, T.: Morphology-based hierarchical representation with application to text segmentation in natural images. In: 2016 23rd International Conference on Pattern Recognition (ICPR), pp. 4029-4034. IEEE (2016) |
| [20] | Kelley, JL, General Topology (1975), New York: Springer, New York · Zbl 0306.54002 |
| [21] | Khalimsky, E.; Kopperman, R.; Meyer, PR, Computer graphics and connected topologies on finite ordered sets, Topol. Appl., 36, 1, 1-17 (1990) · Zbl 0709.54017 · doi:10.1016/0166-8641(90)90031-V |
| [22] | Kovalevsky, V., Axiomatic digital topology, J. Math. Imaging Vis., 26, 1, 41-58 (2006) · Zbl 1478.94055 · doi:10.1007/s10851-006-7453-6 |
| [23] | Latecki, L.; Eckhardt, U.; Rosenfeld, A., Well-composed sets, Comput. Vis. Image Underst., 61, 1, 70-83 (1995) · doi:10.1006/cviu.1995.1006 |
| [24] | Latecki, LJ, 3D well-composed pictures, Gr. Models Image Process., 59, 3, 164-172 (1997) · doi:10.1006/gmip.1997.0422 |
| [25] | Boutry, N.; Huynh, LD; Géraud, T., Connected filters on generalized shape-spaces, Pattern Recogn. Lett., 128, 348-354 (2019) · doi:10.1016/j.patrec.2019.09.018 |
| [26] | Mazo, L.; Passat, N.; Couprie, M.; Ronse, C., Digital imaging: a unified topological framework, J. Math. Imaging Vis., 44, 1, 19-37 (2012) · Zbl 1255.68254 · doi:10.1007/s10851-011-0308-9 |
| [27] | Meyer, F., Skeletons and perceptual graphs, Sig. Process., 16, 4, 335-363 (1989) · doi:10.1016/0165-1684(89)90030-3 |
| [28] | Najman, L., Géraud, T.: Discrete set-valued continuity and interpolation. In: Mathematical Morphology and Its Applications to Signal and Image Processing, volume 7883 of Lecture Notes in Computer Science Series, pp. 37-48. Springer (2013) · Zbl 1382.68269 |
| [29] | Ngoc, M.V., Jonathan, G.T.: Saliency-based detection of identy documents captured by smartphones. In: 2018 13th IAPR International Workshop on Document Analysis Systems (DAS), pp. 387-392. IEEE (2018) |
| [30] | Xu, Y., Géraud, T., Najman, L.: Morphological filtering in shape spaces: Applications using tree-based image representations. In: 2012 21st International Conference on Pattern Recognition (ICPR), pp. 485-488. IEEE (2012) |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
