Derived neighborhoods and frontier orders. (English) Zbl 1478.94024
Summary: Many applications require the extraction of an object boundary from a discrete image. In most cases, the result of such a process is expected to be, topologically, a surface, and this property might be required in subsequent operations. However, only through careful design can such a guarantee be provided. In the present article we will focus on partially ordered sets and the notion of \(n\)-surfaces introduced by A. V. Evako et al. [J. Math. Imaging Vis. 6, No. 2-3, 109–119 (1996; Zbl 1191.05088)] to deal with this issue. Partially ordered sets are topological spaces that can represent the topology of a wide range of discrete spaces, including abstract simplicial complexes and regular grids. It will be proved in this article that (in the framework of simplicial complexes) any \(n\)-surface is an \(n\)-pseudomanifold, and that any \(n\)-dimensional combinatorial manifold is an \(n\)-surface. Moreover, given a subset of an \(n\)-surface (an object), we show how to build a partially ordered set called frontier order, which represents the boundary of this object. Similarly to the continuous case, where the boundary of an \(n\)-manifold, if not empty, is an \((n -1)\) -manifold, we prove that the frontier order associated to an object is a union of disjoint \((n -1)\)-surfaces. Thanks to this property, we show how topologically consistent Marching Cubes-like algorithms can be designed using the framework of partially ordered sets.
MSC:
| 94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |
| 68U10 | Computing methodologies for image processing |
| 06A06 | Partial orders, general |
| 54H99 | Connections of general topology with other structures, applications |
Keywords:
discrete topology; discrete surfaces; partially ordered sets; simplicial complexes; frontier ordersCitations:
Zbl 1191.05088References:
| [1] | J. Hudson, Piecewise Linear Topology, W.A. Benjamin inc. 1969. |
| [2] | J. Alexander, ”The combinatorial theory of complexes,” Ann. Math., Vol. 31, pp. 294–322, 1930. · JFM 56.0497.02 · doi:10.2307/1968099 |
| [3] | W. Lickorish, ”Simplicial moves on complexes and manifolds,” Geometry and Topology Monograph, Proccedings of the KirbyFest, Vol. 2, pp. 229–320, 1998. · Zbl 0963.57013 |
| [4] | E. Moise, ”Affine structures on 3-manifolds,” Annals of mathematics, Vol. 56, pp. 96–114, 1952. · Zbl 0048.17102 · doi:10.2307/1969769 |
| [5] | T.Y. Kong and A. Rosenfeld, ”Digital topology: Introduction and survey,” Computer Vision, Graphics and Image Processing, Vol. 48, pp. 357–393, 1989. · doi:10.1016/0734-189X(89)90147-3 |
| [6] | D. Morgenthaler and A. Rosenfeld, ”Surfaces in three-dimensional images,” Information and Control, Vol. 51, pp. 227–247, 1981. · Zbl 0502.68017 · doi:10.1016/S0019-9958(81)90290-4 |
| [7] | R. Malgouyres, ”A definition of surfaces of \(\mathbb{Z}\)3,” in Discrete Geometry for Computer Imagery, pp. 23–34, 1993. |
| [8] | M. Couprie and G. Bertrand, ”Simplicity surfaces : A new definition of surfaces in \(\mathbb{Z}\)3,” SPIE Vision Geometry V Proceedings, Vol. 3454, pp. 40–51, 1998. |
| [9] | R. Ayala, E. Dominguez, A. Frances, A. Quintero, and J. Rubio, ”On surfaces in digital topolgy,” Discrete Geometry for Computer Imagery, pp. 271–276, 1995. |
| [10] | G. Bertrand and M. Couprie, ”A model for digital topology,” in Springer (Ed.), Discrete Geometry for Computer Imagery, Vol. 1568, of LNCS, pp. 229–241, 1999. · Zbl 0935.68117 |
| [11] | E. Khalimsky, ”On topologies of generalized segments,” Soviet Mat. Doklady, Vol. 10, pp. 1508–1511, 1969. · Zbl 0213.49703 |
| [12] | G. Bertrand, ”New notions for discrete topology,” in Springer (Ed.), Discrete Geometry for Computer Imagery, Vol. 1568 of LNCS, pp. 218–228, 1999. · Zbl 0935.68116 |
| [13] | P. Alexandroff, Combinatorial Topology, Dover Publications, 1947. |
| [14] | A.V. Evako, R. Kopperman, and Y.V. Mukhin, ”Dimensional properties of graphs and digital spaces,” Jour. of Math. Imaging and Vision, Vol. 6, pp. 109–119, 1996. · Zbl 1191.05088 · doi:10.1007/BF00119834 |
| [15] | A.V. Ivashchenko, ”Representation of smooth surfaces by graphs,” Transformations of Graphs which do not Change the Euler Characteristic of Graphs, Discrete Mathematics, Vol. 122, pp. 219–133, 1993. · Zbl 0839.57003 |
| [16] | A.V. Ivashchenko, ”Dimension on discrete spaces,” International Journal of Theoretical Physics, 1994. · Zbl 0811.05064 |
| [17] | E.D. Khalimsky and R. Kopperman P. M., ”Computer graphics and connected topologies on finite ordered sets,” Topology Appl. Vol. 36, pp. 1–17, 1990. · Zbl 0709.54017 · doi:10.1016/0166-8641(90)90031-V |
| [18] | R. Kopperman, P.R. Meyer, and R.W., ”A Jordan surface theorem for three-dimensional digital spaces,” Discrete Computational Geometry, Vol. 6, pp. 155–161, 1991. · Zbl 0738.68086 |
| [19] | G. Herman, ”Discrete multidimensional Jordan surfaces,” Graphicals Models and Image Processing, Vol. 54, pp. 507–515, 1992. · doi:10.1016/1049-9652(92)90070-E |
| [20] | G. Herman, ”Oriented surfaces in digital spaces,” Graphicals Models and Image Processing, Vol. 55, pp. 381–396, 1993. |
| [21] | J. Udupa, ”Multidimensional digital boundaries,” Graphicals Models and Image Processing, Vol. 56, pp. 311–323, 1994. · doi:10.1006/cgip.1994.1028 |
| [22] | R. Aharoni, G.T. Herman, and M.L., ”Jordan graphs,” Graphicals Models and Image Processing, Vol. 58, pp. 345–359, 1996. |
| [23] | J. Burguet, R.M., ”Strong thinning and polyhedric approximation of the surface of a voxel object,” Discrete Applied Mathematics, Vol. 125, pp. 93–114, 2003. · Zbl 1050.68148 |
| [24] | W. Lorensen and H. Cline, ”Marching cubes: A high resolution 3D surface construction algorithm,” Computer Graphics, Vol. 21, pp. 163–169, 1987. · doi:10.1145/37402.37422 |
| [25] | J.O. Lachaud and A. Montanvert, ”Continuous analogs of digital boundaries: A topological approach to iso-surfaces,” Graphical models, Vol. 62, pp. 129–164, 2000. · doi:10.1006/gmod.2000.0522 |
| [26] | X. Daragon, M. Couprie, and G. Bertrand, Marching chains algorithm for Alexandroff-Khalimsky spaces. In: SPIE Vision Geometry XI proceedings, pp. 51–62, 2002. |
| [27] | X. Daragon, M. Couprie, and G. Bertrand, ”Discrete frontiers,” in Springer (Ed.) Discrete Geometry for Computer Imagery, Vol. 2886 of LNCS, pp. 236–245, 2003. · Zbl 1254.68298 |
| [28] | V. Kovalevsky, ”Finite topology as applied to image analysis,” Computer Vision, Graphics and Image Processing, 1989. |
| [29] | Y. Cointepas, I. Bloch, and L. Garnero, ”A cellular model for multi-objects multi-dimensional homotopic deformations,” Pattern Recognition, Vol. 34, No. 9, pp. 1785–1798, 2001. · Zbl 0995.68165 · doi:10.1016/S0031-3203(00)00106-0 |
| [30] | C. Lohou and G. Bertrand, ”Poset approach to 3d parallel thinning,” in SPIE Vision Geometry VIII, Vol 3811, pp. 45–56, 1999. |
| [31] | X. Daragon and M. Couprie, ”Segmentation topologique du neo-cortex cérébral depuis des données IRM,” in: RFIA 2002, Vol. 3, pp. 809–818, 2002. |
| [32] | J. Pescatore, Maillages homotopiques tétraédriques des tissus de la tête pour le calcul du problème direct en électro/magnéto-encéphalographie. Ph.D. Thesis, ENST Paris, 2001. |
| [33] | J. Burguet and I. Bloch, ”Homotopic labeling of elements in a tetrahedral mesh for the head modeling,” in Procs. 9th Iberoamerican Congress on Pattern Recognition, CIARP 2004, pp. 566–573, 2004. |
| [34] | M. Couprie, G. Bertrand, and Y. Kenmochi, ”Discretization in 2d and 3d orders,” Graphical Models, Vol. 65, pp. 77–91, 2003. · Zbl 1039.68142 · doi:10.1016/S1524-0703(03)00003-1 |
| [35] | X. Daragon, M. Couprie, and G. Bertrand, ”Derived neighborhoods and frontier orders,” Discrete Applied Mathematics, Special issue on DGCI, Vol. 147, No. 2–3, pp. 227–243, 2005. · Zbl 1061.68165 |
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.
