Well-Composed Cell Complexes

Well-Composed Cell Complexes Rocio Gonzalez-Diaz, Maria-Jose Jimenez, and Belen Medrano Applied Math Department, University of Seville, Av. Reina Mercedes, s/n, Seville, Spain {rogodi,majiro,belenmg}@us.es Abstract. Well-composed 3D digital images, which are 3D binary digital images whose boundary surface is made up by 2D manifolds, enjoy important topological and geometric properties that turn out to be advantageous for some applications. In this paper, we present a method to transform the cubical complex associated to a 3D binary digital image (which is not generally a well-composed image) into a cell complex that is homotopy equivalent to the first one and whose boundary surface is composed by 2D manifolds. This way, the new representation of the digital image can benefit from the application of algorithms that are developed over surfaces embedded in R3. Keywords: Well-composed digital images, cubical complex, cell complex, homotopy equivalence. 1 Introduction We are mainly interested in studying topological features of 3D digital images. More concretely, our ultimate purpose is that of extracting cohomological information of a 3D model that could be used in characterization or recognition tasks (see [5,6,4,7] as related works). For this aim, it would be useful to compute first geometrically relevant representative cycles of homology generators of dimension 1 in the surface of the model, since this could simplify cohomological computations. Many applications such as topology repair, surface parameterization and feature recognition benefit from computing loops on surfaces that wrap around their ‘handles’ and ‘tunnels’ (defined by Dey et al. in [2]). In the paper [3], there is an algorithm to compute topologically correct loops that are also geometrically relevant in that sense. A refinement of the algorithm is given in [1]. However, all the computations are carried out over a connected closed surface in R3. Since we are interested in applying these results to 3D binary digital images, we focus in the so-called well-composed images. A 3D binary digital image is said to be well-composed if and only if the square faces shared by foreground and background voxels of the image form a 2D manifold. Well-composed images enjoy important topological and geometric properties: there is only one type of connected component in any well-composed image, and hence, several algorithms used in computer vision, computer graphics and image processing are simpler; thinning algorithms can be simplified and naturally made parallel if the input I. Debled-Rennesson et al. (Eds.): DGCI 2011, LNCS 6607, pp. 153–162, 2011. c Springer-Verlag Berlin Heidelberg 2011 154 R. Gonzalez-Diaz, M.-J. Jimenez, and B. Medrano image is well-composed [10,13]; some algorithms for computing surface curvature or extracting adaptive triangulated surfaces [8], assume that the input image is well-composed. Since 2D and 3D images are often not well-composed images, there are several methods (repairing algorithms) for turning 3D binary digital images that are not well-composed into well-composed ones (see [12,15]), but these methods do not guarantee the topological equivalence between the original object and its corresponding well-composed image. In fact, the purpose can even be to simplify as much as possible the topology in the sense of removing little topological artifacts from the image. However we are concerned with the fact of preserving the topology of the input image having in mind cases in which subtle details can be important. 2 3D Digital Images and Cubical Complexes Consider Z3as the set of points with integer coordinates in 3D space R3.A3D binary digital image I=(Z3,26,6,B)(orI=(Z3,B) for short), where B⊂Z3 is the foreground and Bc=Z3\Bthe background, is represented by the set of unit cubes (voxels) centered at the points of Btogether with all their faces. This identification of voxels with 3D cubes in R3leads, in a natural way, to the combinatorial structure of cubical complexes, whose geometric building blocks (cells) are points, edges, squares and cubes (see [9]). More concretely, given a voxelcenteredatapointofZ3of coordinates (i, j, k), the cells associated to this voxel considered as a 3D cube are denoted as follows (see Fig.1): –The eight vertices (0-cells): (i±1 2,j±1 2,k±1 2) –The twelve edges (1-cells): (i, j ±1 2,k±1 2), (i±1 2,j,k±1 2), (i±1 2,j±1 2,k). –The six square faces (2-cells): (i, j, k ±1 2), (i, j ±1 2,k), (i±1 2,j,k). –Thecube(3-cell):(i, j, k). By considering the (26,6)-relationship we can guarantee that the topology of the cubical complex associated to the image reflects the topology of the object. A cubical complex is, in fact, a special case of cell complex, which is a more general topological structure by which a space is decomposed into basic elements (cells) of different dimensions that are glued together by their boundaries. Given a cell complex K,aproper face of σ∈Kis a face of σwhose dimension is strictly less than the one of σ.Afacet of σisaproperfaceofσof maximal dimension. A maximal cell of Kis a cell of Kwhich is not a proper face of any other cell of K. The dimension of Kis the maximal dimension of the maximal cell of K. A facet that is incident only to one cell is called a boundary facet.The union of all the boundary facets is the boundary of the cell complex which is denoted by ∂K. The cubical complex Q(I) representing a 3D binary digital image Isatisfies that the maximal cells are cubes and the elements of the boundary of Q(I), ∂Q(I), are all the square faces of Q(I) which are shared by a voxel of Band a voxel of Bctogether with all their faces. Well-Composed Cell Complexes 155 Fig. 1. Notation of the vertices {pi},edges{ai}and square faces {ci}associated to the voxel (i, j, k) Given a cell complex K, define Kqas the set of q-cells of K. Define the morphism kq:Kq×Kq−1→Z2given by kq(c, c):=1ifcis a facet of cand kq(c, c) := 0 in other case (we do not take into account orientation). Then, we can codify a cell complex as a pair (K, k)whereK=qKqis the set of cells of Kand k=⊕qkqdefines the relation between each cell and its facets. The morphism kis called the incidence number (see [14]). For example, since any cubical complex Qis a particular case of cell complex, it can be codified as a pair (Q, kQ): Let Q0be the set of vertices, Q1the set of edges, Q2the set of square faces and Q3the set of cubes of Q. Define the morphism kQ q:Qq×Qq−1→Z2given by kQ q(c, c):=1ifcis a facet of cand kQ q(c, c) := 0 in other case. Taking into account the notation given for the cells of Qas points in R3, define kQ q(c, c) := 1 if the Euclidean distance between c and cis 1 2and kQ q(c, c) := 0 in other case. 3 Well-Composed Cell Complexes A3Dbinary digital image I=(Z3,B)iswell-composed [10] if the boundary of the cubical complex associated, ∂Q(I), is a 2Dmanifold, i.e. if each point in 156 R. Gonzalez-Diaz, M.-J. Jimenez, and B. Medrano ∂Q(I) has a neighborhood homeomorphic to R2. This definition implies a simple correspondence between a 3Dbinary digital image and the boundary surface of the associated cubical complex. Thus, one can use well-known properties of continuous boundary surfaces to determine and analyze properties of these digital images. Since the boundary of the cubical complex associated to I=(Z3,B)coincides with the one of Ic=(Z3,Bc), a 3Dbinary digital image Iis well-composed iff Icis also well-composed. 3D binary digital images are often not well-composed images. Nevertheless, there are several methods for turning 3D binary digital images that are not well-composed into well-composed ones (see [12,15]). The problem is that, in general, these techniques do not guarantee the topological equivalence between the original object and its corresponding well-composed image, since they can modify the original image by moving some voxels from Bcto B. In this section, we are interested in obtaining a homotopy-equivalent cell complex to the cubical complex associated to a 3D binary digital image whose geometric realization could enjoy the advantages of well-composed images. Specifically, we present a method to transform the cubical complex Qassociated to a 3D binary digital image which is not generally a well-composed image into a cell complex (K, k). This cell complex (K, k) satisfies that it is homotopy equivalent to Qand its boundary surface, ∂K, is composed by 2D manifolds. The following proposition shows the characterization of well-composed images in terms of simple local conditions on cubes in the cubical complex associated, as one can observe in Fig. 2. Proposition 1. [11] A 3Dbinary digital image I=(Z3,B)is well-composed iff the configurations of cubes C1, C2 and C3 (modulo reflections and rotations) do not occur in Q(I): C1 Four cubes share an edge (a, b, c)and exactly two of them which do not share a face are contained in Q(I)and the other two are not contained in Q(I). That is, if Wdenotes the set of the four cubes sharing the edge (a, b, c),there are exactly two cubes of W, denoted by w1and w2, that are cubes of Q(I) and whose squared Euclidean distance is 2. C2 Eight cubes share a vertex (a, b, c)and exactly two of them which are corneradjacent are contained in Q(I)while the other six are not. That is, if S denotes the set of the eight cubes sharing the vertex (a, b, c), there are exactly two cubes of S, denoted by s1and s2, that are cubes of Q(I)and whose squared Euclidean distance is 3. C3 Eight cubes share a corner point and exactly two of them which are corneradjacent are contained in Q(Ic)while the other six are not. That is, if T denotes the set of the eight cubes sharing the vertex (a, b, c).Then,thereare exactly two cubes of T, denoted by t1and t2, that are not cubes of Q(I)and whose squared Euclidean distance is 3. Given a cubical complex Qassociated to a 3D binary digital image, we say that an edge (a, b, c)ofQis a critical edge if (a, b, c) is an edge shared by four Well-Composed Cell Complexes 157 Fig. 2. Configurations C1, C2 and C3 (modulo reflections and rotations). These configurations cannot occur in Q(I). cubes that constitute the C1-configuration. We say that a vertex (a, b, c)ofQ is a critical vertex if it is either a vertex shared by eight cubes that constitute the C2-configuration or a vertex shared by eight cubes that constitute the C3-configuration or a vertex shared by eight cubes such that one or several critical edges are incident to it. Summing up, one can observe in Fig. 3 all the critical configurations that are possible by the combination of the mentioned critical elements within a set of eight cubes sharing a vertex. Notice that configurations C(2,0), C(2,1), C(3,0) and C(3,1) are complementary to configurations C(6,2), C(6,1), C(5,1) and C(5,2), respectively; as well as configurations C(4,1), C(4,2) and C(4,3) are self-complementary. Now, given a cubical complex Qassociated to a 3D binary digital image, we present a method to generate a new cell complex by some basic operations on the input cubical complex to repair all the critical edges and critical vertices that appear in Q. The method consists of three steps: (1) all the critical edges and critical vertices that appear in Qare labeled and put into either the set E of critical edges or the set Vof critical vertices; (2) apply Algorithm 1 to the cubical complex Qto repair all the edges of Eand (3) apply Algorithm 2 to the cell complex output by the previous algorithm to repair all the vertices of V. Algorithm 1. Repair the critical edges in E. Input: The cubical complex (Q, kQ)associated to a 3D binary digital image. Initialize K i:={(a, b, c, 0):such that (a, b, c)∈Qi}and k i((a, b, c, 0),(a,b ,c ,0)) := kQ i((a, b, c),(a,b ,c )), for any (a, b, c),(a,b ,c )∈Qiand for 0≤i≤3. –For each critical edge (a, b, c)∈E, do: •Duplicate the edge: K 1:= K 1\{(a, b, c, 0)}∪{(a, b, c, 1),(a, b, c, 2)}. •Addanew2-cell: K 2:= K 2∪{(a, b, c, 1,2)}. •Denote by w11 and w12 the two square faces of w1sharing the edge (a, b, c).Denotebyw21 the one of the square faces of w2sharing the edge (a, b, c)such that the squared Euclidean distance between w11 and w21 is 1 2.Denotebyw22 the other square face of w2sharing the edge (a, b, c)(see Fig. 4). 158 R. Gonzalez-Diaz, M.-J. Jimenez, and B. Medrano Fig. 3. All the critical configurations within a set of eight cubes sharing one vertex (modulo reflections and rotations) •Define k 1((a, b, c, j),v):=k 1((a, b, c, 0),v)for j=1,2and for any vertex v∈K 0. •Define k 2(f,(a, b, c, j)) := 1 if f=wij ,fori=1,2,orf=(a, b, c, 1,2), for j=1,2. •Define k 2((a, b, c, 1,2),e):=0if e=(a, b, c, j)for j=1,2, that is, the only facets of the new 2-cell (a, b, c, 1,2) are the edges (a, b, c, 1) and (a, b, c, 2). •Define k 3(w, (a, b, c, 1,2)) := 1 if w=wifor i=1,2and 0in other case. Output: The cell complex (K,k). Algorithm 2. Repair the critical vertices in V. Input: The cell complex (K,k)obtained after applying Algorithm 1. Initialize Ki:= K iand ki:= k ifor 0≤i≤3. –For each critical vertex (a, b, c)∈Vwith the configuration C(2,1), do: •Duplicate the vertex: K0:= K0\{(a, b, c, 0)}∪{(a, b, c, 1),(a, b, c, 2)}. •Add two new edges: K1:= K1∪{(a, b, c, 1,2),(a, b, c, 2,1))}. •Addanew2-cell:K2:= K2∪{(a, b, c, 1,2,1)}. Well-Composed Cell Complexes 159 Fig. 4. Notations for the cells around a critical edge (a, b, c) •Take two square faces of s1sharing the vertex (a, b, c)and denote them by s11 and s12. Take the square face of s2sharing the vertex (a, b, c) whose squared Euclidean distance to s11 is 2;denoteitbys22.Denoteby s21 the other square face of s2sharing the vertex (a, b, c)whose squared Euclidean distance to s12 is 2(see Fig. 5). •Define k1(e, (a, b, c, 1)) := 1 if either e=(a, b, c, 1,2) or e=(a, b, c, 2,1), or eis a face edge of s1shared by s11 and s12 or eis any of the other two edges of s2such that k 1(e, (a, b, c, 0)) = 1 and that are not shared by s21 and s22 at the same time, and 0otherwise. •Define k1(e, (a, b, c, 2)) := 1 if either e=(a, b, c, 1,2) or e=(a, b, c, 2,1), or eis a face edge of s2shared by s21 and s22 or eis any of the other two edges of s1such that k 1(e, (a, b, c, 0)) = 1 and that are not shared by s11 and s12 at the same time, and 0otherwise. •Define k2(f,(a, b, c, 1,2)):=1 if f=s12 or f=s22 or f=(a, b, c, 1,2,1), and 0otherwise. •Define k2(f,(a, b, c, 2,1)):=1 if f=s21 or f=s11 or f=(a, b, c, 1,2,1), and 0otherwise. •Define k3(w, (a, b, c, 1,2,1)) := 1 if w=sifor i=1,2and 0otherwise. –For each critical vertex (a, b, c)∈Vwith any configuration of Fig. 3 apart from C(2,1), do: •Label the background connected components of the configuration of eight 3-cells around the critical vertex with labels 1,2,3and 4, respectively (notice that the number of connected components may vary from 2to 4). Let L={1,2,...,l}be the set of labels assigned. •Label all the edges incident to (a, b, c)that belong to the boundary of K, with the corresponding label of the background component that shares such an edge. •Substitute the critical vertex by a set of vertices, one for each label corresponding to a background connected component: K0:= K0\{(a, b, c, 0)}∪ {(a, b, c, 1),...,(a, b, c, l)}. 160 R. Gonzalez-Diaz, M.-J. Jimenez, and B. Medrano Fig. 5. Notations for the cells around a critical vertex (a, b, c) with the configuration C(2,1) •Add new edges: K1:= K1∪{(a, b, c, i, j),i,j∈L, i < j}. •If l≥3, add new 2-cells K2:= K2∪{(a, b, c, i, j, k), i,j,k ∈L, i < j < k}. •If l=4, add a new 3-cell K3:= K3∪{(a, b, c, 1,2,3,4)}. •Define k1(e, (a, b, c, i)) := 1 if either k 1(e, (a, b, c, 0)) = 1 and eis an edge with label ior e=(a, b, c, i, j), for any jor e=(a, b, c, j, i), for any j, and 0otherwise. •Define k2(f,(a, b, c, i, j)) := 1 if either fis a 2-cell with two face edges labeled as iand jor f=(a, b, c, i, j, k)or f=(a, b, c, i, k, j)or f= (a, b, c, k, i, j),and0otherwise. •Define k3(w, (a, b, c, i, j, k)) := 1 if either wis a 3-cell with three face edges labeled as i,jand k,orw=(a, b, c, 1,2,3,4),and0otherwise. Output: The cell complex (K, k). Proposition 2. The cell complex (K, k)and the cubical complex Qare homotopy equivalent. Moreover, the boundary surface ∂K, of the cell complex (K, k), is composed by 2D manifolds, that is, each point of ∂K has a neighborhood homeomorphic to R2. Example 1. Consider the 3Dbinary digital image I=(Z3,B)withB={(1,1,0), (0,0,1),(0,2,1),(0,1,2)}.LetQthe cubical complex associated to the image. This cubical complex has 4 voxeles (3-cells), 24 square faces (2-cells), 45 edges (1-cells) and 26 vertices (0-cells). The conflictive cells of Kare: –The edges a1=(0,1 2,3 2)anda2=(0,3 2,3 2); –The vertices v1=( 1 2,1 2,1 2)andv2=( 1 2,3 2,1 2). Applying the previous method to this cubical complex, the obtained wellcomposed cell complex Khave four 3-cells, twenty eight 2-cells (21 square faces, 2 pentagons and 1 hexagon), 51 edges and 28 vertices (see Fig. 7). Well-Composed Cell Complexes 161 Fig. 6. Notations for the cells around a critical vertex (a, b, c), with the configurations C(6,1)(firstrow)andC(4,1) (second one) Fig. 7. Example of a cubical complex and well-composed complex 4 Conclusion and Future Work We have presented a method for obtaining a well-composed cell complex from the cubical complex associated to a 3D binary digital image. We are convinced that this new representation will satisfy very nice properties: first, the new cell complex will allow to compute the homology of the image by computing the