On Parallel Thinning Algorithms: Minimal Non-simple Sets, P-simple Points and Critical Kernels
Tóm tắt
Critical kernels constitute a general framework in the category of abstract complexes for the study of parallel homotopic thinning in any dimension. In this article, we present new results linking critical kernels to minimal non-simple sets (MNS) and P-simple points, which are notions conceived to study parallel thinning in discrete grids. We show that these two previously introduced notions can be retrieved, better understood and enriched in the framework of critical kernels. In particular, we propose new characterizations which hold in dimensions 2, 3 and 4, and which lead to efficient algorithms for detecting P-simple points and minimal non-simple sets.
Tài liệu tham khảo
Alexandroff, P.S.: Diskrete Räume. Math. Sb. 2(3), 501–518 (1937)
Bertrand, G.: On P-simple points. C. R. Acad. Sci., Sér. Math. I(321), 1077–1084 (1995)
Bertrand, G.: Sufficient conditions for 3D parallel thinning algorithms. In: SPIE Vision Geometry IV, vol. 2573, pp. 52–60 (1995)
Bertrand, G.: On critical kernels. C. R. Acad. Sci., Sér. Math. I(345), 363–367 (2007)
Bertrand, G., Couprie, M.: A new 3D parallel thinning scheme based on critical kernels. In: Discrete Geometry for Computer Imagery. Lecture Notes in Computer Science, vol. 4245, pp. 580–591. Springer, Berlin (2006)
Bertrand, G., Couprie, M.: Two-dimensional parallel thinning algorithms based on critical kernels. J. Math. Imaging Vis. 31(1), 35–56 (2008)
Bing, R.H.: Some aspects of the topology of 3-manifolds related to the Poincaré conjecture. Lect. Mod. Math. II, 93–128 (1964)
Burguet, J., Malgouyres, R.: Strong thinning and polyhedric approximation of the surface of a voxel object. Discrete Appl. Math. 125, 93–114 (2003)
Cohen, M.M.: A Course in Simple Homotopy Theory. Springer, Berlin (1973)
Couprie, M.: Note on fifteen 2d parallel thinning algorithms. Internal Report, Université de Marne-la-Vallée, IGM2006-01 (2006)
Couprie, M., Bertrand, G.: New characterizations of simple points in 2D, 3D and 4D discrete spaces. IEEE Trans. Pattern Anal. Mach. Intell. 31(4), 637–648 (2009)
Gau, C.-J., Kong, T.Y.: Minimal non-simple sets in 4D binary images. Graph. Models 65, 112–130 (2003)
Giblin, P.: Graphs, Surfaces and Homology. Chapman and Hall, London (1981)
Hall, R.W.: Tests for connectivity preservation for parallel reduction operators. Topol. Appl. 46(3), 199–217 (1992)
Kaczynski, T., Mischaikow, K., Mrozek, M.: Computational Homology. Springer, Berlin (2004)
Khalimsky, E., Kopperman, R., Meyer, P.R.: Computer graphics and connected topologies on finite ordered sets. Topol. Appl. 36, 1–17 (1990)
Kong, T.Y.: On topology preservation in 2-D and 3-D thinning. Int. J. Pattern Recognit. Artif. Intell. 9, 813–844 (1995)
Kong, T.Y.: Topology-preserving deletion of 1’s from 2-, 3- and 4-dimensional binary images. In: Discrete Geometry for Computer Imagery. Lecture Notes in Computer Science, vol. 1347, pp. 3–18. Springer, Berlin (1997)
Kong, T.Y.: Minimal non-simple and minimal non-cosimple sets in binary images on cell complexes. In: Discrete Geometry for Computer Imagery. Lecture Notes in Computer Science, vol. 4245, pp. 169–188. Springer, Berlin (2006)
Kong, T.Y.: Minimal non-deletable and minimal non-codeletable sets in binary images. Theor. Comput. Sci. 406(1–2), 97–118 (2008)
Kong, T.Y., Gau, C.-J.: Minimal non-simple sets in 4-dimensional binary images with (8–80)-adjacency. In: International Workshop on Combinatorial Image Analysis, pp. 318–333 (2004)
Kong, T.Y., Rosenfeld, A.: Digital topology: introduction and survey. Comput. Vis. Graph. Image Process. 48, 357–393 (1989)
Kong, T.Y.: On the problem of determining whether a parallel reduction operator for N-dimensional binary images always preserves topology. In: Proc. SPIE Vision Geometry II, vol. 2060, pp. 69–77 (1993)
Kong, T.Y., Litherland, R., Rosenfeld, A.: Problems in the topology of binary digital images. In: Open Problems in Topology, pp. 376–385. Elsevier, Amsterdam (1990)
Kovalevsky, V.A.: Finite topology as applied to image analysis. Comput. Vis. Graph. Image Process. 46, 141–161 (1989)
Lohou, C., Bertrand, G.: A 3D 12-subiteration thinning algorithm based on P-simple points. Discrete Appl. Math. 139, 171–195 (2004)
Lohou, C., Bertrand, G.: A 3D 6-subiteration curve thinning algorithm based on P-simple points. Discrete Appl. Math. 151, 198–228 (2005)
Ma, C.M.: On topology preservation in 3d thinning. Comput. Vis. Graph. Image Process. 59(3), 328–339 (1994)
Manzanera, A., Bernard, T.M., Prêteux, F., Longuet, B.: N-dimensional skeletonization: a unified mathematical framework. J. Electron. Imaging 11(1), 25–37 (2002)
Maunder, C.R.F.: Algebraic Topology. Dover, New York (1996)
Ronse, C.: Minimal test patterns for connectivity preservation in parallel thinning algorithms for binary digital images. Discrete Appl. Math. 21(1), 67–79 (1988)
Rosenfeld, A.: A characterization of parallel thinning algorithms. Inf. Control 29, 286–291 (1975)
Whitehead, J.H.C.: Simplicial spaces, nuclei and m-groups. Proc. Lond. Math. Soc. 45(2), 243–327 (1939)
Zeeman, E.C.: On the dunce hat. Topology 2, 341–358 (1964)