Persistent Homology for 3D Reconstruction Evaluation

Persistent Homology for 3D Reconstruction Evaluation Antonio Gutierrez1, David Monaghan2, Mar´ıa Jos´e Jim´enez1, and Noel E. O’Connor2 1Applied Math Department, School of Computer Engineering, University of Seville, Campus Reina Mercedes, 41012 Sevilla, Spain [email protected] 2CLARITY: Centre for Sensor Web Technologies, Dublin City University, Ireland {david.monaghan,noel.oconnor}@dcu.ie Abstract. Space or voxel carving is a non-invasive technique that is used to produce a 3D volume and can be used in particular for the reconstruction of a 3D human model from images captured from a set of cameras placed around the subject. In [1], the authors present a technique to quantitatively evaluate spatially carved volumetric representations of humans using a synthetic dataset of typical sports motion in a tennis court scenario, with regard to the number of cameras used. In this paper, we compute persistent homology over the sequence of chain complexes obtained from the 3D outcomes with increasing number of cameras. This allows us to analyze the topological evolution of the reconstruction process, something which as far as we are aware has not been investigated to date. Keywords: voxel carving, volume reconstruction, persistent homology, evaluation. 1 Introduction Homology is topologically invariant, meaning it is a property of an object that does not change under continuous (elastic) transformations of the object. Roughly speaking, homology characterizes “holes” in any dimension (e.g. connected components, tunnels and cavities in a 3D space). Homology computation can be carried out over a combinatorial structure called cell complex, which is built up by basic elements (cells ) of different dimensions (vertices, edges, faces, etc.). One can take advantage of the combinatorial nature of a digital image (as a set of voxels) to compute homology by taking as input the (algebraic) cubical complex associated to the image. Persistent homology studies homology classes and their life-times (persistence) in the belief that significant topological attributes must have a long life-time in a filtration (an increasing nested sequence of subcomplexes). In this paper, we compute persistent homology via the Incremental and Decremental Algorithms for computing AT-models (see [5]), which allow to combine an incremental with a decremental technique in the case of a non-increasing M. Ferri et al. (Eds.): CTIC 2012, LNCS 7309, pp. 139–147, 2012. c Springer-Verlag Berlin Heidelberg 2012 140 A. Gutierrez et al. filtration, that is, a sequence of subcomplexes. In the following Section, we describe the context in which we apply persistent homology computation. Section 3 is devoted to recall basic tools used in our computations. Section 4 describes the application of persistent homology to the evaluation of the voxel carving process. We draw some conclusions and ideas for future work in the last Section. 2 Voxel Carving Approach Space carving is a well-known method for constructing three-dimensional models of objects from a set of images. The process involves capturing a series of images of an object, and, by analysis of these images, deriving a description of the shape of the object. In particular, space (or voxel) carving aproaches [2,3,9,11] are non-invasive techniques that allow the reconstruction of a 3D human model from the images captured from a set of cameras placed around the subject. In each image, firstly, the region of interest (subject silhouette) is segmented from the background by an autonomous adaptive “approximate median” background modelling algorithm; then a 3D bounding box is drawn around the subject’s approximate position in 3D space. By using extracted silhouettes from each image, inconsistent voxels are eliminated from the defined volume, iterating through each of the cameras [9]. In [1], the authors present a technique to quantitatively evaluate spatially carved volumetric representations of humans using a synthetic dataset of typical sports motion in a tennis court scenario. Such a quantification is based on the computation of Normalised Mean Square Error (NMSE) of a groundtruth volumentric reconstruction (which has been considered at 50 cameras, based on experimental observation) against any reconstruction from an inferior camera setup (with less cameras than the setup used to carve the ground truth). The aim of such an evaluation is to somehow quantify the accuracy of the 3D volume produced by the voxel carving process with regard to the number of cameras used. This investigation was motivated by the fact that very little work has been done to date on evaluating the quality of space carving results. In this paper, we intend to give a different insight into the voxel carving work by homologically characterising the sequence of reconstruction volumes. This may be interesting as the surfaces produced with a few cameras are quite noisy with many holes, which are irrelevant topological information that can be discarded by using persistent homology. Given the nature of the carvings, we believe that a homology-based approach is a more appropriate quantification than the relatively simple NMSE-based approach used previously. 3 Homology Computations on a Set of Voxels Acell complex is a general topological structure by which a space is decomposed into basic elements (cells) of different dimensions, which are glued together by their boundaries (see a formal definition of CW-complex in [8]). Due to the nature of our input data, we focus on a special type of cell complex: cubical complex. A cubical complex Qin R3, is given by a finite collection of p-cubes Persistent Homology for 3D Reconstruction Evaluation 141 Fig. 1. Voxel carving approach for 3D reconstruction. Process with 4 cameras around the subject and an overhead camera. such that a 0-cube is a vertex, a 1-cube is an edge, a 2-cube is a filled square (we call it, simply, a square) and a 3-cube is a filled cube (resp. a cube); together with all their faces and such that the intersection between two of them is either empty or a face of each of them. We consider Z/2 as the ground ring for algebraic computations, since we do not need to deal with torsion. The cubical chain complex associated to the cubical complex Qis the collection C(Q)={Cp(Q),∂ p}pwhere: (a) each Cp(Q) is the corresponding chain group generated by the p-cubes of Q, over Z/2; (b) the boundary operator ∂p:Cp(Q)→Cp−1(Q) connects two immediate dimensions. The boundary of a p-cube is the formal sum (mod 2) of all its facets (proper faces of maximal dimension). It is extended to p-chains by linearity. Roughly speaking, the homology groups of a cubical chain complex will be a chain group whose elements are equivalence classes of cycles, such that if one cycle can be obtained from another by continuous deformation through the object, then they are homologous (or equivalent). For example, two vertices are homologous if there exists a path through the object between them. Formally, a p-cycle is a p-chain asuch that ∂p(a)=0.Ifa=∂p+1bfor some p+1-chainbthen ais called a p-boundary.Wesaythattwop-cycles aand bare homologous if there exists a (p+1)-chaincsuch that a=b+∂p+1c. Define the p-th homology group to be the quotient group of p-cycles mod p-boundaries denoted by Hp(Q). Each element [a]ofHp(Q) is a quotient class obtained by adding each p-boundary toagivenp-cycle acalled a representative cycle of the homology class [a]. The homology of Qis the chain group H(Q)={Hp(Q)}p. See [10] for further details. 3.1 Incremental-Decremental Algorithms for Computing Persistent Homology We focus on homology computation methods based on the concept of AT-model [7]. Given a cell complex, Incremental Algorithm for computing AT-models [7] 142 A. Gutierrez et al. computes homology information of the cell complex by an incremental technique, considering the addition of a cell each time. Once homology of an object has been computed, the same algorithm can be used again to update homology information if new cells are added to the existing complex; Decremental Algorithm for computing AT-models [6] can be used for the same aim, in the case that some cells are deleted. Given a cubical complex Q, an algebraic-topological model (AT-model [7]) for Qis a set of data (Q, H, f, g, φ), such that: –Qis the cubical complex itself. –His a subset of Qthat characterizes the homology of Qby containing a p-cube for each p-homology class, for all p.In3D,Hcan only have points, edges and squares: each point of Hrepresents a connected component of Q, each edge represents a “tunnel” and each square represents a “void” (i.e. a connected component of the background inaccessible from the outside). –fis a chain map from C(Q)toC(H). This map provides the equivalence relation between cycles (that is, if two cycles, aand b, are equivalent, then f(a)=f(b)). Moreover, fg(c)=cfor any c∈H. –gis a chain map from C(H)toC(Q). For each cube cin H,g(c)isarepresentative cycle of a homology class. –φis a map from C(Q)toC(Q) that is a chain homotopy (see [10]) from gf to the identity homomorphism on C(Q). This map can be seen as a kind of boundary inverse. For example, if cis a vertex, then φ(c) is the path from c to the vertex v∈Hhomologous to c. Fig. 2. A simple example of execution of Incremental Algorithm for computing AT- models. a) The input cubical complex, a filled square with all its faces (only the labels of the vertices are shown). b) The elements in H. c) The table with the information related to f,gand φ. Read, for instance, f(16) = 16, g(16) = 16, φ(16) = 0, φ(17) = 16 −17 (edge from 16 to 17). In [5], the authors revisit the algorithm for computing AT-models using an incremental technique that appears in [7] (we will refer to it as the Incremental Algorithm) with the aim of setting its equivalence with persistent homology computation algorithm [4,12]. Given a cubical complex Qassociated to a 3D digital image, consider a full ordering of its cubes {c1,...,c n}such that if ciis a Persistent Homology for 3D Reconstruction Evaluation 143 face of cj,theni<j; take a nested sequence of subcomplexes ∅=Q0⊆Q1···⊆ Qn(a filtration over Q) such that Qi={c1,...,c i}(notice that all the proper faces of ciare in Qi−1). Under these conditions, Incremental Algorithm can be applied to compute persistent homology over the filtration. See Fig. 2 as a simple example of execution of the Incremental Algorithm for computing AT-models. Fig. 3. A simple example of execution of Decremental Algorithm for computing an AT- model (Q,H,f,g,φ ) after removing a 2-cube (the square 16 −17 −24 −23) from Fig. 2.a. a) The output cubical complex (only the labels of the vertices are shown) after deleting the square. b) The cubes in H. c) The table with the information related to f,gand φ. Now, let (Q, H, f, g, φ) be an AT-model for a cubical complex Qcomputed by the Incremental Algorithm. Let cmbe a maximal cube of Q.ThenanAT-model for Q=Q\{cm},(Q,H,f,g,φ ), can be constructed by the Decremental Algorithm given in [5], where it was redefined (with respect to the one of [6]) with the aim of extending the concept of persistent homology for objects with a filtration that is not necessarily increasing. See Fig. 3 as an example of execution of Decremental Algorithm for computing AT-models. Notice that by removing the 2-cube from the initial cubical complex on Fig. 2, a new homology class is created. The output of the algorithm is the set (Q,H,f,g,φ ) represented in a table form in Fig. 3.c). Now, let ∅=Q0↔Q1↔···↔Qnbe a zig-zag filtration, that is, a sequence of cell complexes such that every two consecutive complexes differ by a single cell c, i.e. either Qi=Qi−1∪{c}or Qi=Qi−1\{c}. Then, one can compute persistent homology over the filtration by combining the application of Incremental and Decremental Algorithms depending on whether a cell cis added or deleted each time. 4 Persistent Homology for 3D Reconstruction Evaluation We are concerned with the application of persistent homology computation to provide topological evaluation of the 3D reconstruction process by the voxel carving technique. The new insight could significantly enrich the evaluation made 144 A. Gutierrez et al. Fig. 4. 3D Reconstructions using a) 4 cameras and b) 10 cameras. Representative cycles of homology are highlighted in both cases. c) Barcode associated to the whole sequence of 3D reconstructions with increasing number of cameras (from 1 to 50). d) 3D reconstruction using 50 cameras, what is considered the groundtruth model. in [1] by means of NMSE quantification. For this aim, we must consider the sequence of different 3D models, obtained by voxel carving under increasing number of cameras, as a whole object on which we have to set up a filtration over which to compute persistent homology. This way, in particular, we can get an estimation of the minimum number of cameras needed in order to obtain a topologically correct 3D model (which in general has only one connected component and no tunnels or voids). We denote by Rkthe cubical complex associated to the 3D reconstruction obatined using kcameras (which are randomly chosen). Starting from the first reconstruction R1(obtained by “one carving” of the initial 3D bounding box), we can use Incremental Algorithm to compute its homology. Notice that Rk+1 may be obtained from Rkby removing some voxels (cubes, together with all their faces in the cubical complex). This fact makes this context good for making use of the Decremental Algorithm for getting homology computations through increasing number of cameras. Both, Incremental and Decremental Algorithms provide all the pairs of cells responsible for the creation/destruction of homology classes along the process, what allows to follow the evolution of these classes with respect to time, that is, the number of cameras used. Actually, to compute persistent homology of the whole sequence of 3D models, {Rk}k, the zigzag filtration is given by the sequence {Rk}kitself with the inclusion, between Rkand Rk+1,of a sequence of complexes {Rik k}ik=1...nkgiven by the addition or deletion of a cell, each time. Compute, then, a big barcode for visualizing the hole computation in Persistent Homology for 3D Reconstruction Evaluation 145 Fig. 5. 3D Reconstructions (viewed from different angles) using different number of cameras: a) 4 cameras, b) 15 cameras and c) 24 cameras, which is similar to the one obtained with 50 cameras (groundtruth model). Representative cycles of homology are highlighted. Below, barcode associated to the whole sequence of 3D reconstructions from 1 to 50 cameras. order to easily analyze the stability of the elements of homology. We want also to remark that, due to the nature of the voxel carving process, only voxels on the surface of the object are removed each time, so different connected componentes and tunnels (but no cavities) may arise. We have used for computation five different frames extracted from a 3D video sequence with a voxel resolution of 4 cm, that is, the spacing between each voxel is 4 cm in the OX,OY and OZ directions. This means 15,625 voxels per cubic metre. We have appreciated, as it was expected, that simpler poses of the subject produce simpler barcodes while more complex poses give place to more interesting homological information. Fig. 4 shows that the carving process, in a case of simple pose, stabilizes at 10 cameras (with a unique connected component), while below that point, 3 different tunnels have been living for some time. That means that, in order to produce a topologically correct model, 146 A. Gutierrez et al. at least 10 cameras are needed. Fig. 5 reflects a more complex pose, though it also corresponds to a 3D object with one connected component and no tunnels or voids. Notice the more complex barcode associated (in which 2 connected components and 16 tunnels are represented) and, especially, the fact that a 1–homology class is created at time k= 15, that persists until k= 23. So stabilization of one connected component as final state, occurs much later than in the former case. We are working also on other approaches: –To compute persistent homology of the sequence of 3D difference complexes {Dk}kwith respect to the groundtruth model (R∞), where Dk=Rk\R∞. Now the barcode for the whole sequence will provide different information about the whole process that might complement the one given by the reconstructions themselves. –To compute persistent homology of the sequence of 3D complexes generated by the convex deficiencies of each 3D reconstruction, that is, the complexes obtained by the substraction of each 3D reconstruction to its 3D convex hull. 5 Conclusions and Future Work Persistent homology computation provides an interesting new insight into the 3D model reconstruction process explained in this paper. There are lots of ideas and experimentation still to be investigated. An important point is to study the dependence of the observations on the resolution of the input data. An alternative approach could be to compute some homology-based features extracted from each reconstruction Rkand to compare them against a groundtruth model. These features should be measurable so that a distance with respect to the groundtruth model could be computed. These parameters could be extracted from the comparison of weighted histograms of connected components (for 0-homology study) or minimal-legth (in some sense) representative cycles of 1-homology. Another interesting question arises by fixing a certain number of cameras and considering the sequence of 3D reconstructions along time. Holes can be produced along time by different movements of the body that should not be stable along the complete scene, so the homological analysis of voxel carving performance of video sequences could shed some light on the classification of these movements. References 1. Monaghan, D., Kelly, P., OConnor, N.E.: Quantifying Human Reconstruction Accuracy for Voxel Carving in a Sporting Environment. In: ACM MM, Scottsdale, AZ, November 28 - December 1 (2011) 2. Broadhurst, A., Drummond, T., Cipolla, R.: A probabilistic framework for space carving. In: Conf. on Computer Vision, vol. 1, p. 388 (2001) 3. Culbertson, W.B., Malzbender, T., Slabaugh, G.: Generalized voxel coloring. In: Intern. Workshop on Vision Algorithms: Theory and Practice, pp. 100–115 (1999) Persistent Homology for 3D Reconstruction Evaluation 147 4. Edelsbrunner, H., Letscher, D., Zomorodian, A.: Topological persistence and simplification. In: FOCS 2000, pp. 454–463. IEEE Computer Society (2000) 5. Gonzalez-Diaz, R., Ion, A., Jimenez, M.J., Poyatos, R.: Incremental-Decremental Algorithm for Computing AT-Models and Persistent Homology. In: Real, P., Diaz-Pernil, D., Molina-Abril, H., Berciano, A., Kropatsch, W. (eds.) CAIP 2011, Part I. LNCS, vol. 6854, pp. 286–293. Springer, Heidelberg (2011) 6. Gonzalez-D´ıaz, R., Medrano, B., S´anchez-Pel´aez, J., Real, P.: Simplicial Perturbation Techniques and Effective Homology. In: Ganzha, V.G., Mayr, E.W., Vorozhtsov, E.V. (eds.) CASC 2006. LNCS, vol. 4194, pp. 166–177. Springer, Heidelberg (2006) 7. Gonzalez-Diaz, R., Real, P.: On the cohomology of 3D digital images. Discrete Applied Math. 147(2-3), 245–263 (2005) 8. Hatcher, A.: Algebraic Topology. Cambridge University Press (2002) 9. Kutulakos, K.N., Seitz, S.M.: A theory of shape by space carving. Intern. Journal of Computer Vision 38, 199–218 (2000) 10. Munkres, J.: Elements of Algebraic Topology. Addison-Wesley Co. (1984) 11. Seitz, S.M., Curless, B., Diebel, J., Scharstein, D., Szeliski, R.: A comparison and evaluation of multi-view stereo reconstruction algorithms. In: IEEE Conference on Computer Vision and Pattern Recognition, vol. 1, pp. 519–528 (2006) 12. Zomorodian, A., Carlsson, G.: Computing persistent homology. Discrete and Computational Geometry 33(2), 249–274 (2005)