A Graph-with-Loop Structure for a Topological Representation of 3D Objects

A Graph-with-Loop Structure for a Topological Representation of 3D Objects Rocio Gonzalez-Diaz, Mar´ıa Jos´eJim´enez, Belen Medrano, and Pedro Real Applied Math Department, University of Seville, Spain {rogodi,majiro,belenmg,real}@us.es http://alojamientos.us.es/gtocoma Abstract. Given a cell complex Kwhose geometric realization |K|is embedded in R3and a continuous function h:|K|→R(called the height function), we construct a graph Gh(K) which is an extension of the Reeb graph Rh(|K|). More concretely, the graph Gh(K) without loops is a subdivision of Rh(|K|). The most important difference between the graphs Gh(K)andRh(|K|)isthatGh(K) preserves not only the number of connected components but also the number of “tunnels” (the homology generators of dimension 1) of K. The latter is not true in general for Rh(|K|). Moreover, we construct a map ψ:Gh(K)→K identifying representative cycles of the tunnels in Kwith the ones in Gh(K) in the way that if eis a loop in Gh(K), then ψ(e) is a cycle in K such that all the points in |ψ(e)|belong to the same level set in |K|. 1 Reeb Graphs and Tunnels We are interested in analyzing and visualizing intrinsic properties of geometric models and scientific data. Specifically, Reeb graphs [13], which express the connectivity of level sets, have been used in the past to construct data structures and user-interfaces for modeling and visualization applications [5]. Let Xbe a topological space and h:X→Ra continuos map. A level set is the primage of a constant value, h−1(t). Call a connected component of a level set a contour.Twopointsx, y ∈Xare equivalent, x∼y,iftheybelongtothe same contour, that is, if h(x)=h(y)andxand yare connected by a path on X. The Reeb graph of h,Rh(X), is the quotient space defined by this equivalence relation. Observe that, by construction, the Reeb graph has a point for each contour and the connection is provided by ψ:X→Rh(X) that maps each point xto its equivalence class. Even though the Reeb graph loses a lot of the original topological structure, some things can be said: a tunnel in Xthat maps (by ψ) to a tunnel in Rh(X) cannot be continuously deformed to a single point, and two tunnels in Xthat map to different tunnels in Rh(X). The number of connected components of X,β0(X), is preserved and the number of tunnels of X,β1(X), cannot increase, i.e. β0(Rh(X)) = β0(X)andβ1(Rh(X)) ≤β1(X). Partially supported by Junta de Andaluc´ıa (FQM-296 and TIC-02268) and Spanish Ministry for Science and Education (MTM-2006-03722).  Fellow associated to University of Seville under a Junta de Andalucia research grant. W.G. Kropatsch, M. Kampel, and A. Hanbury (Eds.): CAIP 2007, LNCS 4673, pp. 506–513, 2007. c Springer-Verlag Berlin Heidelberg 2007 A Graph-with-Loop Structure for a Topological Representation 507 Fig. 1. From left to right, the torus X; representative cycles of the two tunnels of X (the tunnel ais obvious and the other one, b, is not); a geometric realization of the Reeb Graph Rh(X)thathassociates to each point on Xits elevation; and a geometric realization of the graph with loops Gh(X) In [2] the authors adapt concepts developed for smooth manifolds to discrete surface models, introducing an extended Reeb graph representation for a generic polyhedral surface. Their approach is based on the computation of a sufficiently dense number of contour lines and the definition of the Reeb graph from the contour set. However, such a construction is actually not an extension of the Reeb graph itself, but rather an application of its definition in the discrete domain. In [4], tight upper and lower bounds of the number of tunnels in the Reeb graph that depend on the genus, the number of boundary components and whether or not the 2-manifold is orientable, is given. In this paper, we focus on objects embedded in R3. Several combinatorial structures may represent a cellular subdivision which models an object such as simplicial, cubical and simploidal complexes. Roughly speaking, the cells of a given simplicial complex are simplices (vertices, edges, triangles and tetrahedra); vertices, edges, squares and cubes constitute the collection of cells of a cubical complex; in the case of simploidal complexes, which generalize both simplicial and cubical complexes (see [3]), cells are cartesian products of simplices. In all the cases they fit together in a natural way to form the object (see [11,3]). From now on, a graph G=(V,E), where Vis a set of vertices and Easetof edges, is considered as a particular complex only with vertices and edges. Given Fig. 2. A simplicial, cubical and simploidal complex acomplexK(simplicial, cubical or simploidal), a geometric realization of it (e.g. a 3D triangulated surface) |K|, and a continuous function h:|K|→R,ouraim is the computation of a graph Gh(K) and a function Ψ:Gh(K)→Kwith the following properties: 508 R. Gonzalez-Diaz et al. –Gh(K) has the same number of connected components and tunnels than K. –Each loop (an edge such that its endvertices are the same) of Gh(K)maps to a non-contractible cycle cin Ksuch that |c|(the geometric realization of all the cells in c) lies in a contour of |K|,twoloopsinGh(K)mapto non-homologous cycles in K, and each edge in Gh(K) map to a path in K. –If we do not consider the loops in Gh(K), then Gh(K) is a subdivision of the Reeb graph Rh(K). Therefore, Gh(K) can be seen as an extension of Rh(K) such that not only the number of connected components and tunnels of Gh(K)andKcoincide (this is not true, in general, for Rh(K)), but also there exists a one-by-one identification of tunnels in Gh(K) with tunnels in Kin the way that if eis a loop in Gh(K), then ψ(e) is a cycle in Ksuch that all the points in |ψ(e)|have the same height. 2 Algebraic-Topological Models for 3D Objects This section introduces the algebraic topology background needed to understand the rest of the paper, which is essentially extracted from Munkres’ book [12]. The concept of AT-model established in [8,9] for cohomology computation of 3D digital images is adapted here to solve the problem of computing the graph Gh(K) and the function Ψ:Gh(K)→K. Without lost of generality, we will consider that the ground ring is Z/2. Achain complex Cis a sequence {Cq,d q}of abelian groups Cqand homomorphisms dq:Cq+1 →Cq, such that, for all q,dqdq+1 =0.Theset{dq}q≥0is called the differential of C. The chain complex Cis free if Cqis a free abelian group for each q;itisfinite if there exists an integer n>0 such that Cq=0forq>nand each abelian group Cqis finitely generated. All chain complexes considered here are finite and free. A chain cin Cis a q-cycle if c∈Ker dq.Ifc∈Im dq+1 then ais called a q-boundary. Denote the groups of q–cycles and q–boundaries by Zq and Bqrespectively. Define the integer qth homology group to be the quotient group Zq/Bq, denoted by Hq(C). We say that cis a representative q–cycle of the homology generator c+Bq(denoted by [c]). For each q,theqth homology group Hq(C) is a finitely generated free abelian group. The rank of Hq, denoted by βq, is called the qth Betti number of C. Homology is a powerful topological invariant, which characterizes an object by its q-dimensional “holes” (connected components, tunnels and cavities). Let Kbe a complex (simplicial, cubical or simploidal). A q-chain cis a formal sum of q-cells (where qis the dimension of the cell) in K.Let{σq 1,...,σq mi}be the set of q-cells in K,thenc=mi i=1 λiσq i,whereλi∈{0,1}. Alternatively, we can think of cas the set {σq i,such that λi=1}, and the sum of two q-chains as their symmetric difference. The q-chains together with the addition operation form the group of q-chains denoted as Cq(K). The differential of a q-cell σin K,dq(σ), is the sum of the (q−1)-cells in Kthat belong to the boundary of σ. By linearity, the differential can be extended to q–chains. The chain complex C(K) is the sequence of chain groups Cq(K) connected by the homomorphisms dq. The homology of Kis defined as the homology of C(K). Since we work with A Graph-with-Loop Structure for a Topological Representation 509 objects embedded in R3, the homology groups are torsion–free (see [1, ch.10]). Moreover, Theorem of Universal Coefficient [12] ensures that all the homology information can be computed working with coefficients in Z/2. An AT-model for Kis established in [8,9] and used to obtain the homology and representative cycles of homology generators of K.AnAT-modelcanbe computed starting from an ordering of the cells in K[8,9]. We deal here with a particular ordering based on a cover forest Tof K(any two vertices are connected by exactly one path in Tif and only if they are connected in K). Let T=(V,E) be a cover forest of Kwhere Vis the set of all the vertices of Kand Ea subset of edges of K.S=(σ0,...,σ m)isaT-filter if it is an ordering of all the cells in Ksuch that: –for each j(where 0 ≤j≤m), {σ0,...,σ j}is a subcomplex of K; –if i<j, the dimension of σiis less or equal than the dimension of σj; –if i<j,σiand σjare two edges and σj∈T,thenσi∈TThat is, the edges of the cover forest are in first positions in S). Observe that σ0is always a vertex of K.AnAT-modelforKis then defined as the output of the following algorithm, having as the input a complex Kand a T-filter Sof K. Algorithm 1. [8,9] AT-model Algorithm. Input: aT-filter S=(σ0,...,σ m)of K, H:= {σ0},f(σ0):=σ0,g(σ0):=σ0,φ(σ0):=0. For i=1 to mdo If fd(σi)=0, then H:= H∪{σi},f(σi):=σi,φ(σi):=0,g(σi):=σi+φd(σi). If fd(σi)=0, then: k:= max {jsuch that σj∈fd(σi),j=1, ..., i −1}, H:= H\{σk},f(σi):=0,φ(σi):=0. For j=1 to i−1do if σk∈f(σj), f(σj):=f(σj)+fd(σi),φ(σj):=φ(σj)+σi+φd(σi). Output: the set (S, H, f, g, φ). Notice that in the ith step of the algorithm (i=1,...,m), exactly one homology generator is created or destroyed. The algorithm runs in time at most O(m3). Proposition 1. Let Kbe a complex (simplicial, cubical or simploidal), let T= (V,E)be a cover forest of Kand SaT-filter of K. The output of Algorithm 1, (S, H, f, g, φ), satisfies that: –His a subset of Ssuch that no edge in Tis an edge in H.Hgenerates a chain complex denoted by Hwith null differential; –The number of vertices, edges and triangles in Hequals the number of connected components, tunnels and cavities in |K|, respectively. In other words, the homology of Kis isomorphic to H. –f:C(K)→Hsatisfies that if cad care two cycles in Ksuch that f(c)= f(c)then cand care homologous. 510 R. Gonzalez-Diaz et al. –g:H→C(K)satisfies that {[g(h)] : h∈H}is a set of homology generators of K.Ifh, h∈H,h=h,theng(h)and g(h)are not homologous. Moreover, if ais an edge in H,theng(a)is a simple cycle in Kand all the edges in g(a)\{a}are edges in T.Infact,g(a)\{a}is the simple path in T connecting the endvertices of a. –φ:C(K)→C(K)satisfies that if x∈Hthen φ(x)=0and there is no y∈Ssuch that φ(y)=x. Moreover, if vis a vertex in K,thenφ(v)is the simple path in Tconnecting vwith the vertex in Hthat belongs to the same connected component in Kthan v. S H f g φ 0 0 0 00 1 0 0,1 2 0 0,2 0,10 0 0,20 0 1,2 1,2 1,2 1,2+0,2+0,10 Fig. 3. AafilterSof a simplicial complex Kand the result of applying Algorithm 1 to S(an AT-model for K) 3 Computing a Graph-with-Loop Representation of a 3D Object Let Kbe a complex (simplicial, cubical or simploidal); |K|its geometric realization in R3;andh:|K|→Ra continuous function. Let exy denote an edge with endvertices xand y. We say that the height of a point p∈|K|is tif h(p)=t and the height of a cell σ∈Kis the minimum of the heights of all the points on |σ|.WesaythatKis an h-complex if: –the set of the vertices of Kcan be partitioned into a finite number of subsets in terms of their height, V=r i=1 Vi,whereVi={v∈V:h(v)=tiand t1<···<t r. –if evw is an edge in Kthen vand wbelong to Vifor some i=1,...,r or v∈Vi−1and w∈Vifor some i=2,...,r. h-Complexes appear in a natural way when they are defined by the neighborhood relations of voxels of a 3D digital image and his the real function that associates to each point on |K|its elevation. Let Kbe an h-complex and σa cell in K.Wesaythatσis horizontal if the heights of all the points on |σ|coincide; otherwise, it is vertical.Fori=1,...,r, let Kibe the collection of all the horizontal cells in Kwith the same height ti, i=0,1,...,r.Kiis a subcomplex of Kand if a cell σis not in Ki,thenσis vertical. Let Ti=(Vi,E i) be a cover forest of Kiand SiaTi-filter of Ki.Denote by (Si,H i,f i,g i,φ i), i=1,...,r, the AT-models obtained using Algorithm 1. Let Vbe the set of vertices in K,T=(V,E) a cover forest of K(obtained A Graph-with-Loop Structure for a Topological Representation 511 Fig. 4. From left to right: a digital image and 3 h-complexes associated to it considering the 6, 14 and 26-adjacency, respectively after adding vertical edges in Kin increasing ordering in height to the graph (V,r i=1 Ei)), and SaT-filter of K.Denoteby(S, H, f, g, φ)theAT-model obtained using Algorithm 1. Proposition 2. The AT-model (S, H, f, g, φ)satisfies that: –If ais a horizontal edge in H,thena∈Hifor some iand g(a)=gi(a)is a simple cycle such that its edges are in Ki. –If ais a vertical edge in H, then for each level i,i=1,...,r,g(a)has an even number of vertical edges of height ti. Now, let us explain how to construct the graph Gh(K) and the function Ψ: Gh(K)→KusingtheAT-models(Si,H i,f i,g i,φ i),i=1,...,rand(S, H, f, g, φ) computed before. First, the vertices in Gh(K) in each level iare the vertices in Hi, i=1,...,r.Ifvis a vertex in Gh(K), then Ψ(v)=v. Second, for each level iand (horizontal) edge ain Hi∩H,weaddaloopαin Gh(K) such that its endvertex is the vertex in the level iof Gh(K) which belongs to the same connected component than |a|in |Ki|. Define Ψ(α)=gi(a)=g(a). Third, we add an edge exy between two vertices xand yin Gh(K)ifx∈Hiand y∈Hi+1 for some iand f(x)= f(y)=z∈H(i.e. xand ybelong to the same connected component in K). Define Ψ(exy)=φ(x)+φ(y) (the simple path in Tconnecting the vertices xand y). Finally, for each vertical edge evw in H,anedgebis added to Gh(K). Since evw is vertical, then v∈Hiand w∈Hi+1 for some i. The endvertices of bare the vertices in Gh(K) which belong to the same connected component than vin Kiand win Ki+1, respectively. Define Ψ(b)=evw +φi(v)+φi+1(w). Theorem 2. Given a complex Kand a continuous function h:|K|→R.IfK is an h-complex, then: 1. The graph Gh(K)and the complex Khas the same number of tunnels and connected components. 2. For each loop α∈Gh(K),Ψ(α)is a simple cycle representative of a homology generator of K.Ifα1and α2are two different loops in Gh(K),thenΨ(α1) and Ψ(α2)are two representative cycles of two non-equivalent generators of homology. 3. For each edge exy in Gh(K)that comes from a vertical edge evw ∈H,then Ψ(exy)+φ(x)+φ(y)=g(evw)is a representative cycle of a homology generator of K. 4. The graph Gh(K)without loops is a subdivision of the Reeb graph Rh(K). 5. The graph Gh(K)and the function Ψcan be computed in O(m3),wherem is the number of cells in K. 512 R. Gonzalez-Diaz et al. Proof. The number of tunnels of Kis the number of edges in H.Byconstruction, each horizontal edge in Hproduces a loop in Gh(K) (i.e. a tunnel in Gh(K)). Each vertical edge evw in Hproduces a vertical edge βin Gh(K). Let vin Kiand win Ki+1.LetVand Wbe the two vertices in Gh(K) that belong to the same connected component than vand w, respectively. Since evw ∈H,thenevw created a cycle when it was added. Therefore, vand wbelong to the same connected component in Kand so, there exists a path pbetween Vand Win Gh(K)apartfrom the edge βthat produces evw, by construction. Then, p+βis a cycle in Gh(K). Moreover, Ψ(p+β)=g(b) is a representative cycle of the homology generators of dimension 1 of K. Since representative cycles of a homology generator of dimension 1 of Kmap by ψto a cycle in Rh(K), then ψ(g(b)) is a cycle in Rh(K). Since Kis an h-complex, then a vertex in Rh(K) corresponds to a contour in a level ti, i=1,...,r. Therefore, a vertex in Rh(K)isavertexinGh(K).  Fig. 5. From left to right: a cover forest Tof the cubical complex Kshowed on the right of Figure 4; the complexes K0,K1,K2and K3; a set of representative cycles of the generators H1(K); and the graph Gh(K) Example 1. Let Kbe the cubical complex Kon the right in Figure 4. A cover forest Tof K;thecomplexesK0,K1,K2and K3; a set of representative cycles of the generators H1(K); and the graph Gh(K) The non-trivial identification of the edges and loops in Gh(K)andKby Ψare: Gh(K)Ψ h1eab +ebc +ecd +edo +eof +eaf v1eBj +eij +ehi +egh +edg +ecd +eac +eab +ebC v2eBj +eij +ebi +eab +eaC v3eBk +ek +em +emn +enC The representative cycles of generators of H1(K)are: α0=Ψ(h1)=eab +ebc +ecd +edo +eof +eaf α1=Ψ(v1)+eBC =eBj +eij +ehi +egh +edg +ecd +eac +eab +ebC +eBC α2=Ψ(v2)+eBC =eBj +eij +ebi +eab +eaC +eBC α3=Ψ(v3)+eBC =eBk +ek +em +emn +enC +eBC A Graph-with-Loop Structure for a Topological Representation 513 4 Conclusions and Future Work It is possible to obtain representative cycles on the boundary of the given complex Kif we compute a cover forest of Kfirst adding the edges on the boundary. Another task is the generalization of the method to any dimension. The problem is that the homology of a complex of a dimension higher than 3 can have torsion groups. In order to capture the torsion part of the homology we could use the concept of λ-AT-model developed in [10]. A possible extension of this work is the construction of a discrete Morse complex Mh(K) associated to a cell complex K, such that there is not only a oneby-one identification of all the homology generators of Mh(K)withthatofK, but also an isomorphism between cohomology rings. Mh(K) can be constructed using a gradient vector field VKassociated to a discrete Morse function (see [6,7]) thatcanbeobtainedfromanAT-modelforK. References 1. Alexandroff, P., Hopf, H.: Topologie I. Springer, Berlin (1935) 2. Biasotti, S., Facidieno, B., Spagnuolo, M.: Extended Reeb Graphs for Surface Understanding and Description. In: Nystr¨om, I., Sanniti di Baja, G., Borgefors, G. (eds.) DGCI 2000. LNCS, vol. 1953, pp. 185–197. Springer, Heidelberg (2000) 3. Dahmen, W., Micchelli, C.A.: On the Linear Independence of Multivariate bSplines. Triangulation of Simploids. SIAM J. Numer. Anal., 19 (1982) 4. Cole-McLaughlin, K., Edelsbruner, H., Harer, J., Natarajan, V., Pascucci, V.: Loops in Reeb Graphs of 2-mainifolds. Discrete Comput. Geom. 32, 231–244 (2004) 5. Fomenko, A.T., Kunii, T.L.: Topological Methods for Visualization. Springer, Heidelberg (1997) 6. Forman, R.: A discrete Morse theory for cell complexes. In: Yau, S.T.(ed.) Geometry, Topology and Physics for Raoul Bott. International Press (1995) 7. Forman, R.: Discrete Morse Theory and the Cohomology Ring. Transactions of the American Mathematical Society 354, 5063–5085 (2002) 8. Gonzalez-Diaz, R., Real, P.: Towards Digital Cohomology. In: Nystr¨om, I., Sanniti di Baja, G., Svensson, S. (eds.) DGCI 2003. LNCS, vol. 2886, pp. 92–101. Springer, Heidelberg (2003) 9. Gonzalez-Diaz, R., Real, P.: On the Cohomology of 3D Digital Images. Discrete Applied Math. 147, 245–263 (2005) 10. Gonzalez-Diaz, R., Jim´enez, M.J., Medrano, B., Real, P.: Extending AT-Models for Integer Homology Computation. In: GbR2007. LNCS, vol. 4538, pp. 330–339. Springer, Heidelberg (2007) 11. Massey, W.M.: A Basic Course in Algebraic Topology. New York (1991) 12. Munkres,J.R.:ElementsofAlgebraicTopology.Addison-Wesley,London,UK(1984) 13. Reeb, G.: Sur les Points Singuliers d’une Forme de Pfaff Complement Integrable ou d’une Function Num´erique. C. Rendud Acad. Sciences 222, 847–849 (1946)