Strong Euler well-composedness. (English) Zbl 1504.90112
Summary: In this paper, we define a new flavour of well-composedness, called strong Euler well-composedness. In the general setting of regular cell complexes, a regular cell complex of dimension \(n\) is strongly Euler well-composed if the Euler characteristic of the link of each boundary cell is 1, which is the Euler characteristic of an \((n-1)\)-dimensional ball. Working in the particular setting of cubical complexes canonically associated with \(n\)D pictures, we formally prove in this paper that strong Euler well-composedness implies digital well-composedness in any dimension \(n\ge 2\) and that the converse is not true when \(n\ge 4\).
MSC:
| 90C27 | Combinatorial optimization |
Keywords:
digital topology; discrete geometry; well-composedness; cubical complexes; manifolds; Euler characteristicReferences:
| [1] | Boutry N, Géraud T, Najman L (2015) How to make \(n\) D images well-composed without interpolation. In: 2015 IEEE international conference on image processing (ICIP). IEEE, pp 2149-2153 |
| [2] | Boutry N, Géraud T, Najman L (2015) 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, lecture notes in computer science, vol 9082. Springer, pp 561-572 · Zbl 1445.68243 |
| [3] | Boutry, N.; Géraud, T.; Najman, L., A tutorial on well-composedness, J Math Imaging Vis, 60, 3, 443-478 (2018) · Zbl 1435.68337 · doi:10.1007/s10851-017-0769-6 |
| [4] | Boutry, N.; Gonzalez-Diaz, R.; Jimenez, MJ, Weakly well-composed cell complexes over \(n\) D pictures, Inf Sci, 499, 62-83 (2019) · Zbl 1451.68298 · doi:10.1016/j.ins.2018.06.005 |
| [5] | Boutry N, Gonzalez-Diaz R, Jimenez MJ, Paluzo-Hildago E (2020) Euler well-composedness. In: Lukic T, Barneva RP, Brimkov V, Comic L, Sladoje N (eds) Combinatorial image analysis: proceedings of the 20th international workshop, IWCIA 2020, Novi Sad, Serbia, July 16-18, 2020, lecture notes in computer science, vol 12148. Springer, pp 3-19 · Zbl 1471.68296 |
| [6] | Boutry N, Gonzalez-Diaz R, Najman L, Géraud T (2020) A 4d counter-example showing that DWCness does not imply CWCness in \(n\) D. In: Lukic T, Barneva RP, Brimkov V, Comic L, Sladoje N (eds) Combinatorial image analysis: proceedings of the 20th international workshop, IWCIA 2020, Novi Sad, Serbia, July 16-18, 2020, lecture notes in computer science, vol 12148. Springer, pp 73-87 · Zbl 1490.54121 |
| [7] | Boutry, N.; Najman, L.; Géraud, T., Equivalence between digital well-composedness and well-composedness in the sense of Alexandrov on n-d cubical grids, J Math Imaging Vis, 62, 1285-1333 (2020) · Zbl 1497.68508 · doi:10.1007/s10851-020-00988-z |
| [8] | Edelsbrunner, H.; Harer, J., Computational topology: an introduction (2010), Providence: American Mathematical Society, Providence · Zbl 1193.55001 |
| [9] | Géraud T, Carlinet E, Crozet S, Najman L (2013) 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. Springer, pp 98-110 · Zbl 1382.68261 |
| [10] | Gonzalez-Diaz, R.; Jimenez, MJ; Medrano, B., 3D well-composed polyhedral complexes, Discrete Appl Math, 183, 59-77 (2015) · Zbl 1319.68229 · doi:10.1016/j.dam.2014.08.036 |
| [11] | Gonzalez-Diaz, R.; Jimenez, MJ; Medrano, B., Efficiently storing well-composed polyhedral complexes computed over 3D binary images, J Math Imaging Vis, 59, 1, 106-122 (2017) · Zbl 1419.68198 · doi:10.1007/s10851-017-0722-8 |
| [12] | Hatcher, A., Algebraic topology (2002), Cambridge: Cambridge University Press, Cambridge · Zbl 1044.55001 |
| [13] | Lachaud, JO; Montanvert, A., Continuous analogs of digital boundaries: a topological approach to iso-surfaces, Graph Models, 62, 3, 129-164 (2000) · doi:10.1006/gmod.2000.0522 |
| [14] | Latecki, LJ, 3D well-composed pictures, Graph Models Image Process, 59, 3, 164-172 (1997) · doi:10.1006/gmip.1997.0422 |
| [15] | Latecki, LJ, Discrete representation of spatial objects in computer vision (1998), Dordrecht: Kluwer Academic, Dordrecht · Zbl 0894.68162 · doi:10.1007/978-94-015-9002-0 |
| [16] | Latecki, L.; Eckhardt, U.; Rosenfeld, A., Well-composed sets, CVIU, 61, 1, 70-83 (1995) |
| [17] | Marchadier, J.; Arquès, D.; Michelin, S., Thinning grayscale well-composed images, Pattern Recognit Lett, 25, 5, 581-590 (2004) · doi:10.1016/j.patrec.2003.12.005 |
| [18] | Siqueira M, Latecki LJ, Gallier J (2005) Making 3d binary digital images well-composed. In: SPIE, vision geometry XIII, vol 5675. International Society for Optics and Photonics, pp 150-164 |
| [19] | Siqueira, M.; Latecki, L.; Tustison, N.; Gallier, J.; Gee, J., Topological repairing of \(3\) D digital images, J Math Imaging Vis, 30, 249-274 (2008) · Zbl 1523.68162 · doi:10.1007/s10851-007-0054-1 |
| [20] | Stelldinger P, Latecki LJ (2006) 3D object digitization: majority interpolation and marching cubes. In: 18th international conference on pattern recognition, vol 2. IEEE, pp 1173-1176 |
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.
