Towards Minimal Barcodes

Towards Minimal Barcodes Roc´ıo Gonz´alez-D´ıaz1,Mar´ıa-Jos´e Jim´enez1,andHamidKrim 2 1Applied Math Dept., School of Computer Engineering, U. Seville, Spain 2ECE Dept., NCSU, Raleigh, NC USA {rogodi,majiro}@us.es, [email protected] Abstract. In the setting of persistent homology computation, a useful tool is the persistence barcode representation in which pairs of birth and death times of homology classes are encoded in the form of intervals. Starting from a polyhedral complex K(an object subdivided into cells which are polytopes) and an initial order of the set of vertices, we are concerned with the general problem of searching for filters (an order of the rest of the cells) that provide a minimal barcode representation in the sense of having minimal number of “k-significant” intervals, which correspond to homology classes with life-times longer than a fixed number k. As a first step, in this paper we provide an algorithm for computing such a filter for k= 1 on the Hasse diagram of the poset of faces of K. Keywords: Persistent homology, persistence barcodes, graphs, polyhedral complexes. 1 Introduction The persistence barcode representation, which encodes pairs of cells meaning birth and death of homology classes in persistent homology computation, depends on the filter considered for such computation. Although, as we will see later, the total number of intervals remains invariant, the lengths of these intervals depend on the selected filter. Since, non-significant intervals (i.e. intervals with short length) do not imply relevant homological information, we are interested in providing good properties to be satisfied by the selected filter, so that the number of non-significant intervals in the corresponding persistence barcode is maximized (i.e. the number of significant intervals is minimized). Motivated by practical applications of persistent homology computation, our starting point is a given polyhedral complex and an initial order of the set of vertices. From an information-theoretic viewpoint, and if we interpret the number of ”significant intervals” as the coding length of a complex, our goal is to then select the most ”parsimonious” representation (also by Occam’s razor principle). As is also well known, the coding length is also intimately related to the notion of entropy (i.e. a topological entropy of a complex in our case). While ideally, one would want to balance this minimization with a penalty term of the number of ”insignificant” Partially supported under grant MTM2012-32706. Authors listed alphabetically. W.G. Kropatsch et al. (Eds.): GbRPR 2013, LNCS 7877, pp. 184–193, 2013. c Springer-Verlag Berlin Heidelberg 2013 Towards Minimal Barcodes 185 intervals. This development is under way, and requires the statistical distribution of the long intervals. Our aim is to look for a way to insert the rest of the cells along the filter in order to minimize the number of significant intervals. The remainder of this paper is organized as follows. Section 2 covers the relevant background material. In Section 3, we prove that the number of intervals in a persistence barcode does not depend on the selected filter, we give the definition of minimal barcode and show two practical examples in which computation of minimal barcodes can be useful. In Section 4, an algorithm for computing on the Hasse diagram of the poset of faces of the polyhedral complex, a filter that produces a minimal barcode is given. Section 5 is devoted to relations between minimal barcodes and the optimal discrete Morse function. Conclusions and future work are presented in Section 6. 2 Background This paper is developed in a combinatorial algebraic topology setting, where the objects of interest are (geometric) polyhedral complexes [14]. A polyhedral complex Kis a collection of convex polytopes such that: (1) every face of a polytope in Kis itself a polytope in K; (2) the intersection of any two polytopes in Kis a face of each of them. The set of cells of dim. i(or i-cells), σi(superscript specifies its dimension), will be denoted by Ki, and the number of cells in the set of cells Sby |S|.Ann-dim.polyhedralcomplex satisfies that Kn=∅and Kn+1 =∅, where n>0. Particular cases arise when the polytopes belong to a specified set of polyhedra, such as simplicial complexes (vertices, edges, triangles, tetrahedra, up to dim. 3) or cubical complexes (vertices, edges, squares, cubes, up to dim. 3). In general, we will always refer to a finite polyhedral complex K(i.e. with mcells, mbeing a finite number). Several polytopes associated with combinatorial optimization problems have surprisingly small extended formulations (see [3,20,10]). It may not be very surprising that no polynomial size extended formulations of polytopes associated with NP-hard optimization problems like the traveling salesman polytope are known. Homology theory uses algebraic groups to encode the topological structure of K. Finite formal sums of elements of Ki(called i-chains) define an additive abelian group structure on Ki.Aproper face of σ∈Kiis a face of σof dim. i−1. The boundary of σ, denoted by ∂(σ) is the formal sum (with coefficients in Z/Z2) of the proper faces of σ. The boundary operator is extended to all chains of Kby linearity. An i-chain ais an i-cycle if ∂(a) = 0; it is an i-boundary if there is an (i+1)-chainbsuch that ∂(b)=a.Twoi-cycles aand aare homologous if a+ais an i-boundary. The quotient of i-cycles over i-boundaries is the ith homology group of K.Thei-Betti number that is the rank of the ith homology group of Kwill be denoted by βi. Then, the basic topological structure of K is quantified by the number of independent cycles in each homology group. See [17,12]. Persistent homology [4,21] studies homology classes and their lifetimes (persistence). While homology characterizes an object, persistent homology characterizes a sequence of growing object-instances, i.e. an object together with an 186 R. Gonz´alez-D´ıaz, M.-J. Jim´enez, and H. Krim Fig. 1. An example of a 2-dim. simplicial complex and three persistence barcodes corresponding to different filters (fixed by the order in the set of cells given along the horizontal axis of the representations). Bottom: two minimal barcodes. Right: two barcodes with same order of the 0-cells. order of the cells {σ1,...,σ m}(where σs<σ tiff s<t) called a filter, such that if σiis a proper faces of σjthen i<j. Given a filter of K, the algorithm for computing persistent homology that appears in [4], marks an i-cell σtas positive (birth) if it belongs to an i-cycle in Kt(σtcreates a new homology class at time t) and negative (death) otherwise (σtdestroys the homology class created at some time sfor 0 ≤s<t). Given a filter {σ1,...,σ m},apersistence barcode [2] is a graphical representation of pairs of birth and death times as a collection of horizontal line segments (intervals) in a plane. If a cell σscreates a homology class at time s,andit is destroyed at time t,0≤s<t≤mthen the interval [s, t) is added to the corresponding persistence barcode (see [2]); If a cell σs,0≤s≤mcreates a homology class at time sand it survives along the process, then the interval [s, ∞) is added to the persistence barcode. 3 Minimal Barcodes In this section, a formal definition of minimal barcode is presented along with two practical examples for which a computation of minimal barcodes can be useful. For a fixed i, we refer to i-barcode the set of intervals of a given persistence barcode corresponding to the pairs of positive i-cells and negative (i+ 1)-cells of K. The following result holds. Lemma 1. The number of intervals in an i-barcode, 0≤i≤n, is constant, independently of the selected filter. Proof. First, the number of intervals of infinite length in the i-barcode is independent on the filter since it coincides with βi. Second, each i-cell σi tin the Towards Minimal Barcodes 187 given filter, 0 ≤t≤m, is marked as positive or negative. No cell can remain unmarked after the whole process. This is easy to prove using AT-models [6]: σi t is marked as positive if fi−1∂(σi t) = 0 and negative otherwise (see [7]). Third, let Bi(resp. Di) be the number of positive (resp. negative) i-cells. Then, we have that |K0|=B0,|Kn|=Bn+Dn,βn=Bn, and, for 0 <i<n,|Ki|=Bi+Di and βi=Bi−Di+1. Therefore, we obtain that D0=0,B0=|K0|,andfor 0<i≤n,Di=|Ki−1|−βi−1−Di−1and Bi=|Ki|−Di. We conclude that, for 0 ≤i≤n,norBineither Di(which coincides with the number of finite intervals in the (i−1)-barcode) depend on the selected filter.  A general idea in the study of topological persistence is that significant topological attributes must have long life-times, and topological features with short life-times are considered to be “noise”. Following this idea, in the definition below, k-significant intervals correspond to homology classes whose life-times are longer than a fixed number k. Definition 1. Fixed k>0, an interval [s, t)is k-significant if k<t−s. Our general aim is to find, under some constraints, depending on the nature of the application, filters that minimize the number of long-life homological classes which are associated with significant intervals. Nevertheless, filters are, in many cases, totally determined. Examples of this is when objects are presented as point cloud data and Rip or Cech complexes are constructed to fill in the higher-dimensional simplices of the proximity graph whose edges are determined by proximity, i.e. vertices within some specified distance (see [8]). But, in other cases, only order of 0-cells are given. For example, when a continuous function (e.g. a height function or barycentric distance) is provided and the 0-cells of Kare ordered by the function values at them. We briefly present here two particular examples of this last case: 1. Application of persistent homology to the evaluation of a 3D reconstruction process (carving voxel) of human models from images captured from a set of cameras placed around the subject. In fact, we refer to the visual hull that is constructed from images of cameras from different viewpoints. This problem can be seen as a view planning problem (see [19], a survey of computer vision sensor planning, [18], a more recent survey of view planning for 3-D vision). In our case, [9], starting from a compact block of voxels, each time a camera is added, a set of voxels are deleted (carved) from the 3D reconstruction, so the sequence of 3D reconstructions along decreasing number of cameras gives place to a filter of the corresponding cubical complexes. This allows to analyze the topological evolution of the reconstruction process. Only ksignificant intervals are considered, where kis the distance (in number of cells) from one reconstruction to the next one. An initial partial order is hence considered in the set of vertices that have to be added in the computation along the process. See Fig. 2. 2. In [11] an image/video application using topological invariants for human gait recognition is shown. Using a background subtraction approach, a stack of silhouettes is extracted and glued through their gravity centers, forming 188 R. Gonz´alez-D´ıaz, M.-J. Jim´enez, and H. Krim Fig. 2. Examples of 3D reconstructions using a) 4 cameras and b) 10 cameras. Representative cycles of homology are highlighted in both cases. c) Persistence barcode associated to the whole sequence of 3D reconstructions with increasing number of cameras (from 1 to 50) is shown. a 3D digital image I. From this 3D representation, the boundary simplicial complex ∂K(I) is obtained. Four filters are computed preserving four different given orders of the vertices of ∂K(I) depending on four directions of view. The persistence barcodes associated with the previous filters are then computed (see Fig. 3). These filters capture relations among the parts of the human body when walking. Only intervals with long life-times are considered. Finally, a topological gait signature is extracted from the persistence barcodes according to the filters. From now on, suppose a bijective function h:K0→{1,2, ..., |K0|} (i.e. an order of the 0-cells of K) is given. Let us denote by Fthe set of filters Fof Ksuch that for any two 0-cells σ0 s,σ0 t∈F,s<t, it is satisfied that h(σ0 s)<h(σ0 t). Definition 2. A persistence barcode associated with a filter F∈Fis minimal if the persistence barcode associated with any other filter in Fcontains greater or equal number of significant intervals. Observe that a filter F∈Fwith a minimal barcode always exists and might not be unique (see Fig. 1 as examples of minimal barcodes). 4 Hasse Diagrams for the Poset of Faces and Minimal Barcodes Our aim in this section is to construct a filter F∈F with a minimal barcode. Consider the poset given by the set of cells of Ktogether with the partial order induced by the coface relation, that is, τ<σif τis a face of σ.TheHasse diagram Hof this poset (poset of faces) is the directed graph whose vertex set is the set of cells and whose arcs are the covering pairs (τ,σ) in the poset, that is, τ<σand there is no ρsuch that τ<ρ<σ(it is said that σcovers τ). We draw the Hasse diagram in the plane in such a way that, if τis a face of Towards Minimal Barcodes 189 Fig. 3. Left: A simplicial complex ∂K(I) corresponding to a gait, vertical direction of view (defined by the segment [a, b]) and the gravity center GC. Right: persistence barcode according to the vertical direction of view, corresponding to a filter of the subcomplex K[a,GC](from ato GC)of∂K(I). σ(σcovers τ), then the point representing σis in a lower level than the point representing τ, corresponding the level with the dimension of the cells. Then no arrows are required in the drawing, since the directions of the arrows are implicit. Videnotes the set of points viat level i,for0≤i≤n. In Alg. 1, a matching (or independent set of edges) Min His provided, together with a vertex-labeling of H(see Fig. 4). The resulting labeling and matching will produce a filter of K. Aweightwi(vi)foreachvi∈Vi,1≤i≤n, will also be assigned along the process as follows. First, 0:V0→{1,...,|K0|} is defined for each vertex v0∈V0by 0(v0)=h(σ0), where σ0is the 0-cell represented by the point v0. Second, for i=1toi=n, the weight of each point vi∈Viwill be wi(vi)=max{i−1(vi−1) such that vi−1is adjacent to vi}. Observe that more than one point in Vican have the same weight. Then, a matching between vertices of Vi−1and vertices of Viis given satisfying that if vi−1is matched with vithen (vi−1)=w(vi). Observe that fixing a weight w, only one point of the set W={vi∈Visuch that wi(vi)=w}is matched with some point in Vi−1. At the end of the process, a bijective function i:Vi→ {1,...,|Ki|},1≤i≤n, is obtained, satisfying: P1 if wi(ui)<w i(vi), then i(ui)< i(vi) for any ui,vi∈Vi; P2 if wi(vi)=wi(ui)and(vi−1,vi)∈Mfor some vi−1∈Vi−1,vi,u i∈Vi then i(vi)< i(ui) (any point in Vimatched with a point in Vi−1always precedes the other points in Viwith same weight); P3 if wi(vi)=wi(ui), vi,u i∈Viand (vi,vi+1)∈Mfor some vi+1 ∈Vi+1 then i(ui)< i(vi) (points in VimatchedwithpointsinVi+1 go after other points in Vinot matched with any point in Vi+1, with same weight); P4 Points in Viwith same weight have consecutive labels. 190 R. Gonz´alez-D´ıaz, M.-J. Jim´enez, and H. Krim Fig. 4. a) An example of a 2-dim. simplicial complex; b) 1st step (i=1)ofAlg.1 (red edges represent matchings); c) 2nd step (i= 1) of Alg. 1; d) subgraph Hv3and an augmenting path (blue and red edges); e) a maximal matching for Hv3(red edges); f) final matching Mon H. P1, P2 and P3 will guarantee that the corresponding filter is correct in the sense that a cell is not added to the filter until all its faces are added. Algorithm 1. Computing a vertex-labeling and a matching Mof H. a. Labeling 0:V0→{1,2,...,|K0|} is given by the corresponding initial order of the 0-cells of K. b. Assign the weight w1(v1)to each point v1∈V1. c. M={(v0,v1)satisfying that v0∈V0,v1∈V1,0(v0)=w1(v1)}.Ifthere are more than one point in V1with the same weight, select one of them to match. d. Construct 1:V1→{1,2,...,|K1|} satisfying P1, P2, P4. Repeat the following process for i=1to i=n−1: 1. Assign the weight wi+1(vi+1)to each point vi+1 ∈Vi+1. 2. Update matching: M:= M∪{(vi,vi+1)such that vi∈¯ Mi,vi+1 ∈Vi+1,i(vi)=wi+1(vi+1)}, where ¯ Miis the set of points of Vinot-matched with any point of Vi−1.If there are more than one point in Vi+1 with the same weight, select one of them to match. 3. For each vi−1∈Vi−1, consider the subgraph Hvi−1whose set of vertices is: A∪B∪Cwhere A={vi−1},B={vi∈Visuch that wi(vi)=i−1(vi−1)} and C={vi+1 ∈Vi+1 such that wi+1(vi+1)=i(vi)for some point vi∈Vi satisfying that wi(vi)=i−1(vi−1)}. Towards Minimal Barcodes 191 3.1. If the matching M|Hvi−1(i.e., Mrestricted to Hvi−1)isnotmaximalin Hvi−1, find a maximal one, Mvi−1, using the augmenting path algorithm, with the restriction that each augmented path always begins in a notmatched vertex vi∈Hvi−1∩Vi. This last restriction will guarantee that if vi−1was not matched in Hvi−1, it remains unmatched in Hvi−1. 3.2. Remove from Mthe pairs in M|Hvi−1and add to Mthe pairs in Mvi−1. 4. Update i:Vi→{1,2,...,|Ki|} satisfying P1, P2, P3, P4. 5. For each point vi+1 ∈Vi+1, update weight wi+1(vi+1)if needed. 6. Construct i+1 :Vi+1 →{1,2,...,|Ki+1|} satisfying P1, P2, P4. Observe that a labeling isatisfying P1, P2, P3, P4 (Step 4 in the description of the algorithm above) can always be obtained. First, before updating, labeling isatisfied P1, P2, P4 (Step 6). Second, to satisfy P3, we just interchange the labels between points in Viwith same weight, then the updated labeling iwill also P3 and also P1, P2 and P4. Since the points vi∈Vicorrespond to i-cells in K,0≤i≤n,anorderof all the points in the planar representation of the Hasse diagram of Kprovide a filter of K. Such an order Ocan be constructed as follows: Algorithm 2. Computing a filter Fof Kform a vertex-labeling and matching Mof Hobtained in Alg. 1. 1. Initially Ois the ordered set of all the points in V0ordered by their labels. 2. For i=1to i=ndo: (a) For every point vi∈Vimatchedwithapointvi−1∈Vi−1,insertvi in Ojust after vi−1(this way, the i-cell associated with the point viis added to the filter Fjust after its last face is added). (b) Add the rest of the points in Viat the end of Oordered by their labels. Remark 1. The number of non-significant intervals in the filter Fgiven by the order Ocoincides with the number of pairs in M. Proposition 1. Fixing a filter Fof Kup to dimension i−1(i.e., a filter of i−1 j=0 Kj), Step 3 in the description of Alg. 1 produces a minimal i-barcode. Proof. Observe that fixing a labeling and matching up to level i−1, Setp 3 of Alg. 1 produces a maximal matching between points at level i−1, iand i+1, with the condition that points in vi−1already matched with points in Vi−2are not matched with any point in Vi. Implementation of the above algorithms is an ongoing work. Based on the previous proposition and some preliminary computations our conjecture is that the procedure explained above produces a filter with a minimal barcode. 5 Relations between Minimal Barcodes and Optimal Discrete Morse Function Discrete Morse functions on cell complexes were defined by Forman in [5]. A function, f:K→Ris a discrete Morse function if for every σ∈K,ftakes a 192 R. Gonz´alez-D´ıaz, M.-J. Jim´enez, and H. Krim value less than or equal to f(σ)onatmostonecofaceofσand takes a value greater than or equal to f(σ)onatmostonefaceofσ. A cell σis critical if all cofaces take strictly greater values and all faces are strictly lower. A discrete vector field Vis a collection of pairs (σi<σ i+1) of cells in Ksuch that each cellisinatmostonepairofV. A discrete Morse function defines a discrete vector field by pairing σi<σ i+1 whenever f(σi)≥f(σi+1). The critical cells are precisely those that do not appear in any pair. Discrete vector fields that arise from Morse functions are called gradient vector fields. A V-path is a sequence of cells: σi 0,σi+1 0,σi 1,σi+1 1,...σi r−1,σi+1 r−1,σi rwhere (σi t,σi+1 t)∈V,σi+1 t>σ i t+1 and σi t=σi t+1.AV-path is a non-trivial closed V-path if σi r=σi 0for r≥1. Forman shows that a discrete vector field is the gradient vector field of a discrete Morse function if and only if there are no non-trivial closed V-paths. There have been several works in the literature dealing with the problem of obtaining optimal discrete Morse functions (the function has the minimum possible number of critical cells in each dimension) and perfect Morse function (the number of critical i-cells coincides with the ith Betti number of the complex). In [13] it is shown that computing optimal Morse matchings in the setting of simplicial complexes is NP-hard. In [15], a linear algorithm to define optimal discrete Morse functions on discrete 2-manifolds is introduced. In [1] the authors establish conditions under which a 2-dim. simplicial complex admits a perfect discrete Morse function and conversely. It is clear that our work presents similarities with the problem of the computation of optimal discrete Morse functions. But in our case, a fixed ordering on the 0-cells are given. Then, optimal discrete Morse matchings could not produce minimal barcodes (indeed, could not produce valid filters) and viceversa, the set of non-significant intervals in a minimal barcode could not be an optimal discrete Morse matching. 6 Conclusions and Future Work In this paper, starting from a polyhedral complex Kand an initial order of the set of vertices, we provide an algorithm for computing a filter on the Hasse diagram of the poset of faces of Ksuch that the associated persistence barcode representation has a minimal number of significant intervals which correspond to homology classes with life-times longer than 1. An idea to adapt the presented algorithm to compute minimal barcodes to the case in which significant intervals are intervals with length greater than k,for k>1, could be: First, to compute a minimal barcode using the above algorithms. Observe that, in this case, the matched points are successively inserted in the filter whereas the non-matched points are successively added at the end. Second, modify the Hasse diagram pretending collapses of the pairs of cells associated with the non-significant intervals and apply the above algorithm again. Observe that in this step we only reorder the cells that have been added to the end. Third, repeat the process k−1 times.