Getting topological information for a 80-adjacency doxel-based 4D volume through a polytopal cell complex

Getting Topological Information for a 80-Adjacency Doxel-Based 4DVolume through a Polytopal Cell Complex Ana Pacheco and Pedro Real Dpto. Matematica Aplicada I, E.T.S.I. Informatica, Universidad de Sevilla, Avda. Reina Mercedes, s/n 41012 Sevilla (Spain) {ampm,real}@us.es http://ma1.eii.us.es/ Abstract. Given an 80-adjacency doxel-based digital four-dimensional hypervolume V, we construct here an associated oriented 4–dimensional polytopal cell complex K(V), having the same integer homological information (that related to n-dimensional holes that object has) than V. This is the first step toward the construction of an algebraic-topological representation (AT-model) for V, which suitably codifies it mainly in terms of its homological information. This AT-model is especially suitable for global and local topological analysis of digital 4D images. Keywords: 4–polytope, algebraic topological model, cartesian product, cell complex, integral operator, orientation. 1 Introduction Homology (informing about 0, 1, 2 and 3–dimensional holes: connected components, “holes” or tunnels and cavities) of the 3Dobjects is an algebraic tool which allows to describe them in global structural terms [9]. This and others related topological invariants are suitable tools for some applications in which pattern recognition tasks based on topology are used. Roughly speaking, integer homology information for a subdivided 3Dobject (consisting in a collection of contractile “bricks” of different dimensionality which are glued in a “coherent” way) is described in this paper in terms of explicitly determining a boundary operator and a homology operator for any finite linear combination (with integer coefficients) of bricks such that, in particular, the boundary of the boundary (resp. the homology of the homology) is zero. In [7], a method for computing homology aspects (with coefficients in the finite field Z/2Z={0,1}) of a three dimensional digital binary-valued volume V considered over a body-centered-cubic grid is described. The representation used This work has been partially supported by “Computational Topology and Applied Mathematics” PAICYT research project FQM-296, “Andalusian research project” PO6-TIC-02268, Spanish MEC project MTM2006-03722. E. Bayro-Corrochano and J.-O. Eklundh (Eds.): CIARP 2009, LNCS 5856, pp. 279–286, 2009. c Springer-Verlag Berlin Heidelberg 2009 280 A. Pacheco and P. Real there for a digital image is an algebraic-topological model (AT-model) consisting in two parts: (a) (geometric modeling level) A cell complex K(V) topologically equivalent to the original volume is constructed. A three dimensional cell complex consists of vertices (0–cells), edges (1–cells), faces (2–cells) and polyhedra (3–cells). In particular, each edge connects two vertices, each face is enclosed by a loop of edges, and each 3–cell is enclosed by an envelope of faces; (b) (homology analysis level) Homology information about K(V) is codified in homological algebra terms [5,6]. This method has recently evolving to a technique which for generating a Z/2Z-coefficient AT-model for a 26–adjacency voxel-based digital binary volume Vuses a polyhedral cell complex at geometric modeling level [11,12,17,19] and a chain homotopy map (described by a vector fields or by a discrete differential form) at homology analysis level [20,24]. Formally, an AT-model ((K(V),∂),φ) for the volume Vcan be geometrically specified by a cell (polyhedral) complex K(V) and algebraically specified by a boundary ∂:C(K(V))∗→C(K(V))∗−1and a homology φ:C(K(V))∗→C(K(V))∗+1 operator, where C(K(V)) is the chain complex canonically associated to the polyhedral cell complex K(V) (i.e., all the finite linear combinations of the elements of K(V)aretheelementsofC(K(V))). These maps satisfy the following relations: (a) ∂∂ =0=φφ;(b)φ∂φ =φ;(c)∂φ∂ =∂.K(V) is homologically equivalent (in fact, homeomorphically equivalent) to the voxel-based binary volume due to the fact that the process of construction of K(V)isdoneinalocal way by continuously deforming the geometric object formed by any configuration of “black” voxels (represented by unit cubes) in a 2 ×2×2 neighborhood to the corresponding (polyhedral) convex hull of the barycenters of these voxels. In fact, the different cells of K(V) are convex hulls of the configurations of m points placed in a 2 ×2×2elementarycube,withm≤8. The corresponding boundary and homology operators for each cell can be computed and saved in a look-up table for speeding up Z/2Z-homology runtime computation. This method is suitable for advanced topological analysis (computation of homology generators,Reeb graphs,cohomologyrings ...). Homology with integer coefficients condenses the information provided by homology groups with coefficients in another commutative ring or field (like, the field of real numbers, the field of rational numbers, finite fields ...). In [23], working with integer coefficients, a polyhedral 3DAT-model (K(V),∂),φ)fora 26–adjacency voxel-based binary digital volume is constructed. Fig. 1. Polyhedral cell complex K(V) associated to a digital volume V Getting Topological Information for a 80-Adjacency Doxel-Based 4DVolume 281 Fig. 2. Cell complex K(V) associated to a 2Ddigital object and a visual description of a homology operator In this paper, we work with a 4–dimensional ambiance (see [16]). More concretely, we work with a doxel-based digital binary 4Dvolume and using integer coefficients we determine a correct (“well oriented”) global boundary operator ∂K(V)of the cell complex K(V) as an alternating sum of the exterior faces ofit.Todoso,weconstructK(V) piece by piece specifying its corresponding local boundary operators knowing that they will be coherently glue one to each other to determine ∂K(V). A boundary isosurface extraction algorithm can be derived from this framework. Different homology computation techniques [2,3,6,7,15,22] can be applied to K(V). Starting from K(V) and using vector fields [20] or spanning-like trees [24,21], an algorithm (based on configuration look-up table) for constructing a global homology operator and, hence, a 4D AT-model of Vappears as a feasible task and will be our objective in a near future. 2 4–Polytopal Continuous Analogous We focus our interest in determining a orientation-correct 4–polytopal cell complex K(V) topologically equivalent to V. The process to construct it is: 1. We divide the 4D–volume into overlapped (its intersection is a “3–cube” of eight mutually 80–adjacents doxels) unit hypercubes formed by sixteen mutually 80–adjacents doxels (see Figure 3). The different maximal cells of K(V) will be suitable deformations of these unit hypercubes. Fig. 3. Overlapped 2 ×2×2×2hypercubes 2. We use cartesian product (CP) techniques to simplicially subdivide each unit 4D–cube as it is indicated in the Algorithm 1. 282 A. Pacheco and P. Real Algorithm 1. Obtaining a simplicialization using the CP Let L1,L 2,L 3,L 4be 1-simplices and we consider the CP L1×L2×L3×L4. We can interpret the 0,1,2,3,4-simplices non-degenerate of the following way: if ais a non-degenerate 0-simplex then ais vertex of the CP else if ais a non-degenerate 1-simplex then ais an edge of the CP and it are obtained as follows: (a) The first element of the first 1-simplex (a11), the first element of the second 1-simplex (a12), the first element of the third 1-simplex (a13)andthefirst element of the fourth 1-simplex (a14) form in order the coordinates of the vertex (a11,a 12,a 13,a 14)ofthesegment. (b) The second element of the first 1-simplex (a21), the second element of the second 1-simplex (a22), the second element of the third 1-simplex (a23)and the second element of the fourth 1-simplex (a24) form in order the coordinates of the vertex (a21,a 22,a 23,a 24)ofthesegment. else if ais a non-degenerate 2-simplex then ais a triangle whose vertices are (a11,a 12,a 13,a 14),(a21,a 22,a 23,a 24),(a31,a 32,a 33,a 34) else if ais a non-degenerate 3-simplex then ais a tetrahedron and the coordinates of its vertices are obtained as above else if ais a non-degenerate 4-simplex then ais a hypertetrahedron and the coordinates of its vertices are obtained as above end if 3. (cell deformation stage) With each unit hypercube Q4, we associate the corresponding 4–polytopal cell cand its border. The idea is to deform Q4 using integral operators (elementary chain homotopy operators increasing the dimension by 1, which are non null only acting on one element [5]) to get the convex hull of this configuration. Now, we give an orientation to each cell cwhich preserves the global coherence on the cell complex (see Algorithm 2). Algorithm 2. Obtaining the convex hull using integral operators if ais a white vertex then φ(a,b)(a)=bwhere bis an edge with aas one of its vertices else if ais an edge with a white vertex then φ(a,b)(a)=bwhere bis an triangle with aas one of its vertices else if ais a triangle with a white vertex then φ(a,b)(a)=bwhere bis an tetrahedron with aas one of its vertices else if ais a tetrahedron with a white vertex then φ(a,b)(a)=bwhere bis an hypertetrahedron with aas one of its vertices end if Remark 1. Let us note that a vertex is called black if it belongs to the initial object, otherwise the vertex is white. To finish this section, we are going to highlight “good” properties of our fourdimensional model: (a) It can capture the homology at the same time that we construct it; (b) It allows us to render the boundary surface of the 4–polytopal continuous analogous K(V); (c) It can be generalized to nD. Getting Topological Information for a 80-Adjacency Doxel-Based 4DVolume 283 3 Local Convex Hulls for the 4–Polytopal Cell Complex In this section we show a simplicial decomposition of the elementary hypercube Q4. This decomposition will help us in determining the correct boundary operator for the deformed cells coming from the different configurations of black vertices in the standard unit 4D–cube. To represent a set of vertices of Q4, we use two different visualizations: 1. (by 3D slices) We consider the 4Dobject divided into 3Dslices, such an object may be thought of as a “time series of 3Dobjects” (see Figure 4). Fig. 4. Visualizing a 4Dobject in 3Dslices 2. (by Schlegel diagram) It consists on a projection of a polytope, from a n–dimensional space into (n−1)–dimensional space, through a point beyond one of its facets. It is also called tesseract (see Figure 5). Fig. 5. Visualizing a 4Dobject using the Schlegel diagram Using the first visualization (for example in the Y-Representation), in order to obtain a Q4simplicialization (see Figure 4), we must compute the barycenter of each one of the eight 3–cubes which form the boundary of the unit 4–cube and so we will get two new cubes (see Figure 6) which we must simplicialize using Algorithm 1; so we will have the Y-Representation of a Q4simplicialization. Fig. 6. Obtaining a simplicialization of Q4by 3Dslices 284 A. Pacheco and P. Real Fig. 7. X,Y,Z,T-Representation of a Q4simplicialization The same way, we can obtain X,Z,T-Representation of a Q4simplicialization. In order to visualize the simplicialization of the interior of Q4we use the tesseract visualization (see Figure 5). First of all, we need to know pentatopes (hypertetrahedra) in which Q4is decomposed. To do this, we use the degeneracy operators of the CP. In this way, we obtain the 24 pentatopes of the hypercube Q4. Now, we have to order the vertices of the pentatopes in such a way that each one has inverse orientation to its neighbors. The 4–cube Q4is then defined as a cell complex, since the orientation of its pentatopes allows us to determine a correct boundary operator. Fig. 8. HT3(in red) with its neighbors Finally, we show here an example for getting the final boundary operator for a 4–polytopal cell, applying integral operators to the unit 4–cube Q4. We suppose that we have a unit 4–cube configuration of 15 vertices, without loss of generality, we can suppose that the vertex (1,0,0,1) is removed. Indeed, it is equivalent to say that we have a unit 4–cube configuration where 15 of them are black and one of them is white. Using the Algorithm 2 we must define the following integral operators for obtaining the convex hull of the configuration (affected simplices in Figure 9): φ((1,0,0,1),<(1,0,0,1),(1,0,1,1)>) φ((1,0,0,1),<(1,0,0,1),(1,1,0,1)>) φ((1,0,0,1),<(1,0,0,1),(0,0,0,1)>) φ(<(1,0,0,1),(0,0,0,0)>,<(1,0,0,1),(0,0,0,0),(1,0,1,1)>) φ(<(1,0,0,1),(1,1,1,1)>,<(1,0,0,1),(1,1,1,1),(0,0,0,0)>) φ(<(1,0,0,1),(0,0,0,0),(1,0,1,1)>,<(1,0,0,1),(0,0,0,0),(1,0,1,1),(1,0,0,0)>) φ(<(1,0,0,1),(0,0,0,0),(1,1,1,1)>,<(1,0,0,1),(0,0,0,0),(1,1,1,1),(1,0,1,1)>) Getting Topological Information for a 80-Adjacency Doxel-Based 4DVolume 285 Fig. 9. Integral operators acting on Q4: In blue the vertex affected, in green the edges affected, in red the triangles affected and in purple the tetrahedron affected φ(<(1,0,0,1),(0,0,0,1),(1,1,1,1)>,<(1,0,0,1),(0,0,0,1),(1,1,1,1),(1,1,0,1)>) φ(<(1,0,0,1),(0,0,0,0),(1,1,0,1)>,<(1,0,0,1),(0,0,0,0),(1,1,0,1),(1,1,1,1)>) φ(<(1,0,0,1),(0,0,0,0),(1,1,1,1),(1,1,0,0)>,<(1,0,0,1),(0,0,0,0),(1,1,1,1),(1,1,0,0),(0,0,1,0)>) 4 Conclusions and Applications This paper is a step toward the extension to 4Dand integer coefficients of the 3DAT-model proposed in [19,20]. Given a binary doxel-based 4Ddigital object Vwith 80–adjacency relation between doxels, it is possible to construct a homologically equivalent oriented hyperpolyhedral complex K(V) in linear time. Starting from this result, it is possible to design an algorithm for computing homology information of the object. In this algorithm, a look-up table with all the possible configurations of black doxels in the unit 4–cube Q4(that is, all possible polytopal unit cells) saves their boundary operator, simplicialization and homology operator. In a near future, we will intend to develop a technique for homology computation of 4Ddigital objects based on this schema. References 1. Couprie, M., Bertrand, G.: New Characterizations of Simple Points in 2D, 3D and 4D Discrete Spaces. IEEE Trans. Pattern Analysis and Machine Intelligence 31, 637–648 (2009) 2. Delfinado, C.J.A., Edelsbrunner, H.: An Incremental Algorithm for Betti Numbers of Simplicial Complexes on the 3–Sphere. Computer Aided Geometric Design 12, 771–784 (1995) 3. Dey, T.K., Guha, S.: Computing Homology Groups of Simplicial Complexes in R3. Journal of the ACM 45, 266–287 (1998) 4. Forman, R.: A Discrete Morse Theory for Cell Complexes. In: Yau, S.T. (ed.) Geometry, Topology & Physics for Raoul Bott, pp. 112–125. International Press (1995) 5. Gonzalez-Diaz, R., Jimenez, M.J., Medrano, B., Molina-Abril, H., Real, P.: Integral Operators for Computing Homology Generators at Any Dimension. In: RuizShulcloper, J., Kropatsch, W.G. (eds.) CIARP 2008. LNCS, vol. 5197, pp. 356–363. Springer, Heidelberg (2008) 6. Gonzalez-Diaz, R., Jimenez, M.J., Medrano, B., Real, P.: Chain homotopies for object topological representations. Discrete Applied Mathematics 157, 490–499 (2009) 286 A. Pacheco and P. Real 7. Gonzalez-Diaz, R., Real, P.: On the cohomology of 3D digital images. Discrete Applied Mathematics 147, 245–263 (2005) 8. Gonzalez-Diaz, R., Medrano, B., Real, P., Sanchez-Pelaez, J.: Algebraic Topological Analysis of Time-sequence of Digital Images. In: Ganzha, V.G., Mayr, E.W., Vorozhtsov, E.V. (eds.) CASC 2005. LNCS, vol. 3718, pp. 208–219. Springer, Heidelberg (2005) 9. Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2001) 10. Kenmochi, Y., Imiya, A.: Discrete Polyhedrization of a Lattice Point Set. In: Bertrand, G., Imiya, A., Klette, R. (eds.) Digital and Image Geometry. LNCS, vol. 2243, pp. 150–162. Springer, Heidelberg (2002) 11. Kenmochi, Y., Imiya, A., Ichikawa, A.: Discrete Combinatorial Geometry. LNCS, vol. 30, pp. 1719–1728. Springer, Heidelberg (1997) 12. Kenmochi, Y., Imiya, A., Ichikawa, A.: Boundary Extraction of Discrete Objects. Computer Vision and Image Understanding 71, 281–293 (1998) 13. Kong, T.Y., Roscoe, A.W., Rosenfeld, A.: Concepts of Digital Topology. Topology and its Applications 46, 219–262 (1992) 14. Kovalevsky, V.A.: Finite Topology as Applied to Image Analysis. Computer Vision, Graphics, and Image Processing 46, 141–161 (1989) 15. Kaczynski, T., Mischaikow, K., Mrozek, M.: Computational homology. Series Applied Mathematical Sciences, vol. 157. Springer, Heidelberg (2004) 16. Lee, M., De Floriani, L., Samet, H.: Constant-Time Navigation in FourDimensional Nested Simplicial Meshes. In: Proc. International Conference on Shape Modeling and Applications, pp. 221–230 (2004) 17. Mari, J.L., Real, P.: Simplicialization of Digital Volumes in 26-Adjacency: Application to Topological Analysis. Pattern Recognition and Image Analysis 19, 231–238 (2009) 18. May, J.P.: Simplicial Objects in Algebraic Topology. University of Chicago Press, Chicago (1967) 19. Molina-Abril, H., Real, P.: Advanced homological computation of digital volumes via cell complexes. In: da Vitoria Lobo, N., Kasparis, T., Roli, F., Kwok, J.T., Georgiopoulos, M., Anagnostopoulos, G.C., Loog, M. (eds.) S+SSPR 2008. LNCS, vol. 5342, pp. 361–371. Springer, Heidelberg (2008) 20. Molina-Abril, H., Real, P.: Cell AT-models for digital volumes. In: Torsello, A., Fscolano, F., Brun, L. (eds.) GBRPR 2009. LNCS, vol. 5534, pp. 314–323. Springer, Heidelberg (2009) 21. Molina-Abril, H., Real, P.: Homological Computation using Spanning Trees. In: CIARP 2009, Guadalajara, Mexico (2009) 22. Mrozek, M., Pilarczykand, P., Zelazna, N.: Homology algorithm based on acyclic subspace. Computers and Mathematics with Applications 55, 2395–2412 (2008) 23. Pacheco, A., Real, P.: Polyhedrization, homology and orientation. In: Wiederhold, P., Barneva, R.P. (eds.) Progress in Combinatorial Image Analysis, pp. 153–167. Research Publishing Services (2009) 24. Real, P., Molina-Abril, H., Kropatsch, W.: Homological tree-based strategies for image analysis. In: Computer Analysis and Image Patterns, CAIP (2009) (accepted) 25. Skapin, X., Lienhardt, P.: Using Cartesian Product for Animation. Journal of Visualization and Computer Animation 12, 131–144 (2001)