Homological spanning forest framework for 2D image analysis

Ann Math Artif Intell (2012) 64:385–409 DOI 10.1007/s10472-012-9297-7 Homological spanning forest framework for 2D image analysis Helena Molina-Abril·Pedro Real Published online: 10 May 2012 © Springer Science+Business Media B.V. 2012 Abstract A 2D topology-based digital image processing framework is presented here. This framework consists of the computation of a flexible geometric graphbased structure, starting from a raster representation of a digital image I.This structure is called Homological Spanning Forest (HSF for short), and it is built on a cell complex associated to I. The HSF framework allows an efficient and accurate topological analysis of regions of interest (ROIs) by using a four-level architecture. By topological analysis, we mean not only the computation of Euler characteristic, genus or Betti numbers, but also advanced computational algebraic topological information derived from homological classification of cycles. An initial HSF representation can be modified to obtain a different one, in which ROIs are almost isolated and ready to be topologically analyzed. The HSF framework is susceptible of being parallelized and generalized to higher dimensions. Keywords Computational algebraic topology·Image processing·Object recognition·Homology with coefficients in a field·Chain homotopy operator· Chain homotopy equivalence·Discrete Morse Theory Mathematics Subject Classifications (2010) 55N99·55U15·68R10·68U10 1 Introduction One of the main goals of digital image processing and computer vision is the research and development of flexible and topologically-consistent frameworks for nD image H. Molina-Abril (B)·P. Real Dpto. Matematica Aplicada I, E.T.S.I. Informatica, Universidad de Sevilla, Avda. Reina Mercedes, s/n 41012 Sevilla, Spain e-mail: [email protected] P. Real e-mail: [email protected] 386 H. Molina-Abril, P. Real processing and object recognition. Roughly speaking, topology in a discrete context helps to understand the degree of connectivity of subdivided geometric structures. For subdivided objects, homology is topology measured in terms of linear combinations (called chains) of unit elements or bricks (also called cells), and in terms of a “boundary operator” describing the connectivity dependencies among these bricks. Homology depends on the ring of coefficient and it gives an algebraic answer in terms of formal sums of bricks that have no boundary (for example, closed subdivided curves or surfaces). These sums are called cycles and homology determines a representative cycle for each n-dimensional hole or homology generator the object has (connected components, tunnels, cavities, etc). In this way, homology can be considered as an specification of the contribution of each brick, to the creation of the homology representative cycles. We present here a 2Dtopology-based digital image processing framework that is built on a graph-based structure, called Homological Spanning Forest (HSF, for short). This framework allows an efficient and complete topological region-of- interest (ROI, for short) analysis (that is to process a single subregion of an image, leaving other regions unchanged). The proposed framework provides a representation that can be used for the development of efficient algorithms to compute analytical, geometrical and topological features of discrete objects. In order to facilitate the understanding of this idea, we start with an elementary example of a subdivided object. Given a geometric graph G, the homology information in which we are interested can be directly captured by means of a spanning tree Tof G. In fact, we transform Tinto a directed tree Tdby adding arrows to every edge in T, in such a way that at most one arrow comes out from each vertex. Therefore, there will be only one vertex sof G, called sink, from which no arrow comes out. Let us take now the simple example of Fig. 1,drawnonR2. Let us now interpret an arrow (f,e)in Tdfrom the vertex fto the vertex eas an elementary “deformation” operation “contracting” in a continuous way the vertex fonto ethrough the edge (e,f)inside the object. The result of applying (no matter the order we choose) the set of homology-preserving operations V={(a,f), (b,c), (c,d), (d,e), ( f,e)}on Gis a reduced (in terms of bricks) subdivided structure consisting of only three bricks: the vertex e, and two loops or “edges” starting and ending at the same common vertex e(in fact, they represent the cycles {(c,f), (e,f), (d,e), (c,d)}and {(a,b), (a,f), (e,f), (d,e), (c,d), (b,c)}coming from (c,f)and (a,b), respectively). Fig. 1 a A geometric graph Gdrawn on R2,ba directed spanning tree (in red) showing a homological “deformation” process and cthe minimal homological object (in black) Homological spanning forest framework for 2D image analysis 387 The directed spanning tree Tdcan be interpreted in dynamical terms, as the way in which the set of vertices of the graph is “collapsed” to a representative vertex of the connected component (in this case, the vertex ein black). These three representative cycles of homology generators (in this case, no matter of the ground ring we use but heavily dependent on the spanning tree T) are determined by the following bricks of G(called critical): the edges (c,f),(a,b)belonging to G\T, and the sink vertex e belonging to T. Its integer homology groups are one copy of Zin dimension 0and two copies in dimension 1. A Homological Spanning Forest or HSF representation F(G)for the subdivided geometric structure Gis the set of coordinate-based trees F(G)={Td,T1,T2},whereT1and T2are trees composed by only one “vertex”: the original edges (a,b)and (c,f)respectively. This “homological representation” has some properties that we will study later under a more general, rigorous and formal mathematical context: (a) Non-uniqueness: it is not unique and strongly depends on how the set of bricks is managed in order to obtain a minimal homological expression. (b) Local Transformability: a global HSF representation can be transformed into a different one by using local combinatorial operations. (c) Geometric Acuity: the use of coordinate-based trees allows to capture the geometry of the original object (each node is specified by an ordered pair of integer coordinates with respect to the square grid of the initial image). (d) Topological Acuity: it suitably encodes advanced topological features (Euler characteristic, Betti numbers, classification of cycles, determining the contractibility and transformability of cycles inside the object, numerical invariants related to cohomology algebra, cohomology operations, ...), due to the fact that the HSF forest can be automatically rewritten in algebraic terms (with coefficients in a field) as a chain homotopy operator determining a strong relationship at chain level (formal sums of bricks) between the geometric object Gand its minimal homological expression; that is, a chain homotopy equivalence. (e) Reusability: a HSF representation of a subgraph Gof Gcan be derived automatically from a previously computed HSF representation of G. We work in this paper with HSF structures within the context of discrete (raster) 2D images. In this highly structured setting, preference will be given to an ambiancebased digital image processing rather than to an object-based one. Assuming that the ambiance carrier (cell complex) of a digital image is topologically trivial (i.e., it has the homology of a point), we extend here to dimension two the homological meaning (in terms of cell collapse-like operations) of the spanning tree notion over a graph. In this way, such a combinatorial HSF scaffolding in which the values of the pixels of a digital image Ibecome the weights for the respective 0-cells fully represent Ifrom a topological point of view. Referring to a whole image Iof dimension n×m, its associated HSF set of coordinated-based direct trees can be, initially, independent of the pixel contents of the digital image I. A HSF representation F(I)leans on an common underlying continuous analogous for all the images. In 2D, it is a finite cell complex Km,nthat is collapsible to a cell (more precisely, cubical) complex version of the Euclidean plane P, whose 0-cells are the pixels of I,the1-cells describe the relationships between 4- adjacent pixels in terms of straight lines, and the closure of 2-cell are squares formed 388 H. Molina-Abril, P. Real by four pixels mutually 8-adjacent. Although this framework works for any different discrete type of adjacency between pixels (8, 6 or 4 connectedness), we focus here on 8-connectedness. In this case, Kn,mis a cell complex with elementary “pockets” (see Fig. 9). Now, starting from a HSF-representation of a digital image, there is an efficient way to “deform” it to a new one, and to isolate ROIs, in order to, for example, analyze further topological features on them. Let us emphasize that these constructions can be built in a parallel setting. There are in the literature an enormous number of papers dealing with techniques that reduce the structural shape of a 2Dregion to a graph (skeletons, shock graph, cut-graph methods, combinatorial maps, pyramids, ...) (see for example [11,31,32]). A substantial minor number of papers handle a cell complex based representation of a2Ddigital image (see for instance [2,24,28,29]). Our combinatorial HSF framework for 2D digital image processing can be classified as a hybrid method that is based on the description of homological information about cell complexes in terms of directed graphs. The object modeling in this context can be considered as a combinatorial refinement of the AT-model method (algebraic-topological method) developed in papers [16–18]. The AT-model is based in the description of homology in terms of chain homotopies. This idea is not new (comes back to the Eilenberg–MacLane work on Algebraic Topology [10]) and has been developed in algebraic-topological methods like Effective Homology [37,40] and Homological Perturbation Theory [20] and in the discrete settings in Discrete Morse [13] and AT-model [15,33] theories. For example, in Discrete Morse Theory, the HSF structure can be specified as an appropriate graph description of an optimal discrete gradient vector field. The paper is structured as follows: We begin with recalling basic definitions and results in Section 2. In the following section, we give an introductory idea of the HSF technique for finite cell complexes. In Section 4the proposed framework for discrete 2D images is detailed. Homology and cohomology computation based on the HSF technique are developed in Section 5. We present a parallel homology-based processing using the HSF framework in Section 6, and conclude the paper in Section 7. Most of the figures of 2Ddigital images in the paper have been created using the software developed in [38]. 2 Preliminaries In this section, we introduce some useful concepts for the understanding of the paper. Adigital image I is a function defined on a discrete set Din Rn(carrier of the image) onto a discrete set Vin R(usually {0,1}for binary images or {0,1,...,255} for gray-level images). The carrier of Iis usually a subset of a uniform regular grid defining Z2. An object of interest O⊂Din a digital image I:D→V, has as image support function w:D→{0,1}, which assigns the value 1 to any pixel of O, whereas each pixel of Oc=D\Ohas the value 0(Ocis named the background). Let us now recall some definitions from algebraic topology. Atopological space is a set of points Xwith a definition for the open subsets of X, usually called neighborhoods. Two topological spaces Xand Yare considered equivalent if there exist a homeomorphism between them, i.e., a continuous bijective function f:X→Ywhose inverse is continuous. Homological spanning forest framework for 2D image analysis 389 The goal of a topological map is to partition a topological space up into regions that are homeomorphic to open balls (see [5,42]). More formally, for p≥1define Bp={x∈Rp:|x|<1},Bp={x∈Rp:|x|≤1},Sp={x∈Rp+1:|x|=1}. A space homeomorphic to Bpis called an open p-cell, a space homeomorphic to Bpis called a closed p-cell, and a space homeomorphic to Spis called a p-sphere.By convention we say that single points are both open and closed 0-cells. A partition of a space into open cells is called a CW-complex. Recall that a p-dimensional (finite, normal, homogeneous) CW-complex Kis a pair (X,{Ki}p i=0)where Xis a Hausdorff space and {Ki}p i=0is a finite partition of Xinto open cells such that: –thesetKiis the set of all open i-cells with 0≤i≤p. – for every open p-cell, σ, there is a continuous map hσ:Bp→Xwhose restriction to Bpis a homeomorphism onto σand whose restriction to Sp−1, called boundary of σand denoted ∂σ, is the union of open cells in K of dimension less than p.Thespacehσ(Bp)=σis called closure of the open cell σand σ=σ∪∂σ. In addition it is required that every open cell σis either a p-cellorisinthe boundary of a p-cell. To indicate relationships between cells, we write τ>σ(or σ<τ) and we say that σis a face of τif σ= τand σ⊂τ.Wewriteτ≥σif either τ≥σor τ>σ. The p-skeleton K(p)of Kis the set of all k-cell p r=0Kr,with0≤k≤p.Ifallthe cells of Kare convex sets of the Euclidean p-dimensional space, then each cell can be represented by a its a new point interior to each cell (commonly, its barycenter) and Kis called convex cell complex. Simplicial, cubical and some polyhedral complexes are special cases of convex cell complexes. All the complexes in this paper are convex cell complexes embedded into the Euclidean p-dimensional space. In this paper the considered ring of coefficients is the finite field Z/2Z={0,1}, but all the results are valid for any commutative field (another finite field, the rational numbers, the real numbers,...). Let {x1,x2, ..., xn}be a finite set of symbols. The finite vector space of formal linear combinations λ1x1+λ2x2+...+λnxn,withλi∈,is denoted by [x1,...,xn]. Given a cell complex K, one can define, for each dimension q, the chain vector space C(K)qwhose elements, called q-chain, are linear combinations of cells of dimension q(q-cells). Then, the chain complex C(K)canonically associated to the finite cell complex Kis a differential graded vector space given by a couple (C(K), ∂), where C(K)={C(K)q}0≤q≤dis a finite sequence of chain vector spaces C(K)q,and the differential (bounding relation) ∂={∂q}0≤q≤dis a sequence of homomorphisms ∂q:C(K)q→C(K)q−1, such that the composition of any two consecutive maps is zero: ∂q◦∂q−1=0for all 0<q≤d(and ∂0≡0). For the convex cell complexes and the coefficients ring considered in this paper, the differential for an open p-cell σcan be automatically deduced from its boundary. If τ1,...,τ rare the open (p−1)-cells belonging to the the boundary ∂σ,the differential for σis the sum τ1+...+τr. Aq-chain c∈C(K)qis called a q-cycle if ∂qc=0.Ifc=∂q+1bfor some b∈ C(K)q+1then cis called a q-boundary. Denote the vector space of q-cycles and qboundaries by Zqand Bqrespectively. Roughly speaking, the idea of homology is to analyze the degree of connectivity of cell complexes using formal sums of cells. Thanks to the nilpotency property of ∂,itistruethatZq⊆Bqfor all q≥0.Define the qth homology group of the cell complex K(or equivalently, of the chain complex 390 H. Molina-Abril, P. Real C(K)) to be the quotient group Zq/Bq. We say that cis a representative q-cycle of the homology generator c+Bq. Elementary chain homotopy operators (that is, linear maps φ:C(K)∗→ C(K)∗+1) acting on a cell complex Kcan be used to describe the process of homology computation for Kat chain complex level. In the case of coefficients on a field, it has been proved (see [15,22,33]) that the whole homology computation process can be exclusively specified by the exhaustive use of these operations. In that case, they are a chain homotopy equivalence version of the classical cell collapsing operation (see, for example, [4]). We interpret now some elementary notions of Discrete Morse Theory [13,14]in terms of chain homotopy equivalences. Let Kbe a finite cell complex and σacellofKof dimension t(t∈{1,2}). If u1,...,ur(r∈N)arethe(t−1)-cells which form the boundary ∂(σ) of σ,letus take φui,σ :Z/2Z[K]→Z/2Z[K]defined by φ(ui)=σand zero elsewhere. The map φui,σ is called cell homology collapsing and is a chain homotopy operator satisfying the properties: (a) φui,σ ◦φui,σ =0,(2-nilpotency condition) and (b) φui,σ ◦∂◦φui,σ = φui,σ (chain contraction condition). In fact, this map generates the following chain homotopy equivalence between differential graded vector spaces (also called a chain contraction in [10]): (fui,σ ,incl,φ ui,σ ):(C(K)=Z/2Z[K],∂)→f(C(K)) =(f(C(K)), ∂)(1) where fui,σ :C(K)→f(C(K)) is the map fui,σ =1(C(K)+∂◦φui,σ +φui,σ ◦∂(being 1C(K):C(K)→C(K)the identity function on C(K)), f(C(K)) ={f(c)/c∈ C(K)}⊂C(K),incl :f(C(K)) →C(K)is the linear operator defined by i(z)= z,∀z∈f(C(K)) and ∂:f(C(K))q→f(C(K))q−1is the differential defined by ∂(f(c)) =f(∂(c)) =(∂ +∂◦φui,σ ◦∂)(c). Concretely, f(ui)=k=iuk,f(σ ) =0 and if σ∈Ct(K)and ∂(σ)=ui+...,then f(σ )=σ+σand ∂(f(σ)) =∂(σ + σ). Finally, fis the identity map and ∂=∂for the rest of cells. In Fig. 2,acell homology collapsing operator (represented with a red arrow) and the result after its application are shown. It is straightforward to prove the following properties (guaranteeing in this way that cui,σ =(fui,σ ,incl,φ ui,σ )is a chain contraction): (a) 1C(K)+incl ◦fui,σ =∂◦φui,σ +φui,σ ◦∂ (b) fui,σ ◦incl =1f(C(K) (c) φui,σ ◦incl =0=fui,σ ◦φui,σ Fig. 2 A cell homology collapsing and the resulting cell complex Homological spanning forest framework for 2D image analysis 391 In particular, these properties mean that the homology groups of the differential graded vector spaces C(K)and f(C(K)) are isomorphic. If uibelongs to the boundary of only one cell σ({ui,σ}is also called afreepair), then f(C(K)) =(Z/2Z[K\ {ui,σ}],∂) and this chain contraction is a classical cell collapse (see Fig. 3for an example). A finite cell complex Xcollapses onto Yif there is a sequence of cell complexes <X0,X1,...,X>(also called cell collapse sequence) such that X0=Xand X= Y, and there is an elementary collapse from Xi−1to Xi,foralli=1,...,.Acell complex Y⊂Xis called a strong deformation retract if the cell complex Xcollapses onto Y. A cell complex Xis called collapsible if it collapses onto a cell complex X{∗} made of a single point. In particular, a collapsible cell complex is acyclic, that is, having the same homology groups as a single point. The elementary collapse operation from Xi−1to Xiis specified by a free pair {u,σ}in Xi−1.Bothuand σ also belong to X0, due to the fact that at each step, free pairs are considered. In this way, we can reinterpret the notion of cell collapse sequence at chain complex level as a sum of chain contractions. This homotopy equivalence is determined by the chain homotopy operator such that φ(u)=σ, for all the involved free pairs {u,σ}. In the next section, we determine a method for dealing with elementary chain contractions cu,σ ,where{u,σ}runs over a discrete vector field Vfor determining the global homological structure of an acyclic cell complex in combinatorial terms. The following notions from Discrete Morse Theory [14] are essential in the sequel: Adiscrete vector field Vdefined on a cell complex Kis a pairwise disjoint collection of sets of two incident cells {α(p)<β (p+1)}. An integral path γfor a discrete vector field Vis an alternating sequence of cells α(p) 0,β(p±1) 0,α(p) 1,β(p±1) 1,α(p) 2,..., such that for each pair of consecutive simplexes, one is a maximal face of the other, and the following condition is satisfied: one of the couples {α(p) i,β(p±1) i}or {β(p±1) i,α(p) i+1}belongs to V,∀i≥0. If the final simplex in the path γabove is α(p) r,thenwesaythatγhas length r. If it ends with β(p±1) rthen we say that γhas length r1 2. If the cells biof the path γare of dimension p+1and it has length r1 2, the integral path γis called upper integral path. An integral path is non trivial and closed if r≥1and the first and last cells in the sequence are the same. A discrete gradient vector field is a discrete vector field with no closed integral path. Acellαis a critical cell of Vif it is not paired with any other cell in V. The number of critical cells depends on the discrete gradient vector field considered. A gradient vector field is optimal if it has the minimum possible number of critical cells. Forman Fig. 3 A cell complex and the resulting cell complex after applying the chain homotopy φ(1)= 1,2(on the left) and a cell complex and the result after applying φ(1,2)=1,2,3(on the right) 392 H. Molina-Abril, P. Real proved that the topology of a discrete manifold is related to these critical elements, mimicking the results of Morse in the smooth case. 3 HSF technique for finite cell complexes In this section, we extract the homological nature of a HSF structure for a finite cell complex, which is half-way between the combinatorial notion of an optimal gradient vector field (Discrete Morse Theory) and the classical algebraic concept of chain contraction (Effective Homology Theory) or even the less elaborate abstraction of a chain homotopy operator (AT-model theory). In Fig. 1, it is shown that the spanning tree together with the two critical bricks can be seen as a non-redundant structure M(G)which combinatorially represents the geometric graph G. There is a strong algebraic relationship between M(G)and Gthat is described by means of a chain contraction between them with a chain homotopy operator specified by the HSF structure. Denoting by Z/2Z[G]the graded vector space formed by the finite linear combinations of 0-cells and 1-cells of G,we can formalize this chain homotopy operator: φM:Z/2Z[G]→Z/2Z[G](2) with φM(a)=(a,f)+(f,e),φM(b)=(b,c)+(c,d)+(d,e)and, for the rest of vertices, φM(x)is the sum of arrows of the directed path from xto efollowing the “maximal paths” φM(a)or φM(b). Concerning the vertex e,φM(e)=0. The evaluation of φMon each of the edges of Gis zero. Using φM, the following operators can be defined: 1. The flow, defined as fM=1+φM◦∂+∂◦φM:Z/2Z[G]→Z/2Z[G],where 1and ∂are functions from Z/2Z[G]to Z/2Z[G]denoting the identity and the boundary operator of the graph cell complex G, respectively. 2. The inclusion operator incl: Z/2Z[C0,C1,C2]→Z/2Z[G],whereC i(i∈{0,1,2}) are the homology representative cycles. In Fig. 1,fM(x)={C0=e}for each vertex xof Gand fM((x,y)) =0for each edge (x,y)in the spanning tree T. The flow of the critical edges (a,b)and (f,c) are, respectively the cycles C1=(a,b)+(b,c)+(c,d)+(e,f)+(f,a)and C2= (c,f)+(c,d)+(d,e)+(e,f). Therefore, under these conditions, any cell cof Gcan be obtained as a sum of a homology representative cycle Ci(i∈{0,1,2})and the homologically inessential linear combination (∂ ◦φM+φM◦∂)(c). The cycles Ci(i∈{0,1,2}) are invariant linear combinations of cells through the flow. In other words, the triple (fM,incl,φM)is a chain contraction from the chain complex C(G)to M(G)=Z/2Z[C0,C1,C2], which is entirely determined by the chain homotopy operator φM. For general and higher dimensional cell complexes, the HSF method is more complicated and needs more explanation (see, for example [35]). We first give the definition of HSF structure on a general finite cell complex and, later, we focus on the two-dimensional case, by specifying a priori an optimal gradient vector field on it, and to cell complexes embedded in a regular Cartesian grid (considering this last as a cell complex). Homological spanning forest framework for 2D image analysis 393 Definition 1 Let Kbe a finite cell complex. A HSF representation Fof Kis a set of coordinate-based directed trees F={T1(F), T2(F),...,Tr(F)}(for some positive integer r) satisfying the following conditions: (a) Every convex cell of Kis a vertex of only one of the trees of Fand it is represented by its barycenter. (b) The vertices of a tree Ti(F)∈F(i=0,...p) are either p-cells (called primary vertices of Ti)or(p+1)-cells (called secondary vertices of Ti). The directed edges of Ti(F)are either upwards F-arrows from a p-cell α(p)to a (p+1)-cell β(p+1)(from which α(p)is boundary), or downwards F-arrows from a (p+1)- cell β(p+1)to one of its boundary p-cell α(p).Tiis called a p-tree of F.Tican have no directed edges and, in this case, it is a trivial tree with only one vertex. Each p-tree Tihas at least one leave that is a p-cell. The upwards F-arrows determine a discrete vector field V(F)on K. (c) The following equalities hold: φ(F)◦∂◦φ(F)=φ(F)and ∂◦φ(F)◦∂=∂. where ∂is the differential of Kand φ(F):C∗(K)→C∗+1(K), called chain homotopy operator associated to F, is defined by: φ(F)(σ(p))is 0if σ(p)is a pcell belonging to a (p−1)-tree of F;ifσ(p)is a vertex of a p-tree Tof F,then φ(F)(σ(p))=i(aimod2)β(p+1) i,whereβ(p+1) iruns over all the (p+1)-cells of Tand aiis the number of upper integral V(F)-paths from σ(p)to β(p+1) i. In any HSF-representation of K, if exists, its 0-dimensional homological trees specify (not considering the arrows) a barycentric subdivision of a spanning forest of the 1-dimensional skeleton K(1)of K. In some way, this decomposition method can be seen as a “natural” extension to higher dimension of the graph-based techniques for computing the spanning forest of a graph complex and its corresponding zero and one dimensional homology groups. For that reason, we have named this decomposition “Homological Spanning Forest”. As we later prove, there exists such a tree-based structure in digital context. We propose here to calculate HSF strutures for digital objects by means of “deformations” of HSF structures on the ambiance space. Let Kbe a finite cell complex such that a cell complex version of a finite regular Cartesian grid is a strong deformation retract of K. From now on, we name such type of space as ASDR (Acyclic Strong Deformation Retract) cell complex. Let Vbe an optimal discrete gradient vector field installed on K. Therefore, Kis homologically null and all the cells of Kare paired by V, excepting a 0-cell scalled sink of V.Infact,s is a representative cycle of the zero dimensional homology group of Kand the chain contraction generated by φVconnects the chain complex canonically associated to Kwith Z/2Z[s]. In these conditions, Kcan be “decomposed” into a HSF structure. Moreover, in this case, due to the fact that the context of ASDR cell complexes is highly structured and that the vertices of the HSF structure are convex cells determined by their barycenter, we can talk about HSF representation of digital objects. In order to prove this result, we take advantage of the algebraic technique of Homological Perturbation Theory [20,21] applied to the discrete gradient vector field φV. This idea has already been exploited in a more general setting in the paper of Romero-Sergeraert [37] for establishing an strong interplay between Effective 400 H. Molina-Abril, P. Real Fig. 10 Arrow reversing example where the blue point represents c0and the green one represents c0 In Fig. 10, an arrow-reversing operation is shown (see the path drawn in red). Arrow-reversing operations for 1-cells are not allowed due to the fact that each 1- cell that does not belong to the 1-forest F1of the HSF Fis paired with a 2-cell. Algorithm 2 (Edge Rotation) Let c0be a 0-cell, c1and c1be two 1-cells and c2a2-cell of an ASDR cell subcomplex Lof L.LetF={F0,F1}be a HSF-representation of Lwith associated combinatorial chain homotopy operator φ. Working at Conceptual Level, if {c0,c1}is an arrow in the 0-tree F0,{c1,c2}is an arrow in the 1-forest F1and c0,c 1and c1belongs to the boundary of c2, then we can generate a HSF-representation ˜ Fwith associated combinatorial chain homotopy operator ˜ φdefined by ˜ φ(c)=φ(c) for any cell c different from c0and c1,˜ φ(c0)=c1and ˜ φ(c1)=c2. In the Edge Rotation transformation, the underlying cellular structure can be modified. We can not guarantee that the final HSF representation belongs to the original cell complex L.InFig.11, we show some elementary examples of edge rotations. Fig. 11 Edge rotation examples Homological spanning forest framework for 2D image analysis 401 Fig. 12 Face rotation example Algorithm 3 (Face Rotation) Let c1 2and c2 2two (both square or both triangular) 2−cells of an ASDR cell subcomplex Lof L, sharing a common edge e1 1=e2 1.Let Fbe a HSF representation of Land φan associated combinatorial chain homotopy operator. Working at Conceptual Level, if all the cells of the subcomplex C(c1 2,c2 2) generated by the closures of c1 2and c2 2can be grouped by pairs of the gradient vector field F, then we can generate a new acyclic combinatorial chain homotopy operator ˜ φ. Using the labeling indicated in Fig. 12, its HSF representation ˜ Fagrees with F excepting for the pairs of C(c1 2,c2 2). For such pairs and for i,j∈{1,2}with i = j, {vi k,ei } belongs to a 0-tree of ˜ Fif {vj k,ej }belongs to a 0-tree of Fand {ei k,ci 2}belongs to a 1-tree of ˜ Fif {ej k,cj 2}belongs to a 1-tree of F(see Fig. 12). Let I:D→Rbe a digital image with an 8-connected object of interest O∈D. Then, it is possible to modify an initial HSF representation (and its corresponding combinatorial chain homotopy operator) by means of the previous local operations, in such a way that the result is a new HSF representation, called HSF-representation of Ibased on O, in which a finite set of edges (called bridge edges) link the object of interest with the background. This homology-based transformation is processed in two steps: (a) for each pixel in the inner boundary of O(that is, belonging to Oand having a pixel not in Oas 8-neighbor) we select, if possible, an arrow connecting this pixel with other neighbor pixel of the inner boundary of O(by using an elementary edge rotation); (b) for each Fig. 13 Examples of HSF-representation based on objects of interest 402 H. Molina-Abril, P. Real pixel in the outer boundary of O(that is, belonging to the complementary of Oand having a pixel in Oas 8-neighbor) we select, if possible, an arrow connecting this pixel with other neighbor pixel of the outer boundary of O(by using an elementary edge rotation). At the end of this process, we have almost “isolated” (along its crack) the object Ofrom the background, excepting the existence of a set of edges in the new HSF representation, called bridge edges, that connect Owith its complementary. In Fig. 13, some HSF-representations based on an object of interest are shown. 5 Homology and cohomology of objects of interest Let I:D→Rbe a 2D digital image and O∈Dbe a (non-necessarily 8-connected) object of interest. Let F={F0,F1}be a HSF representation based on Oand φ: L→Z/2Z[L]be its corresponding acyclic combinatorial chain homotopy operator over an ASDR cell subcomplex Lof L. It is possible to deduce homology groups and generators of the cell subcomplex L(O)⊂Lgenerated by the pixels of O(it is called the homology of Owith coefficients in Z/2Z) from the HSF representation F. In other words, the 8-connected components and holes of the object of interest can be easily determined from this HSF representation. In other words, it is possible to deduce a HSF representation for a digital object from one of the ambiance space, by doing some minor local modifications (Fig. 14). The idea is to consider the sub-forest Fof the forest F, corresponding to the subcomplex L(O)(that is, the HSF representation of the object O). Fig. 14 Example of HSF representation based on two ROIs (set of black pixels in the image). The 0-tree is represented by a spanning tree and the 1-tree of the HSF structure is determined by a vector field Homological spanning forest framework for 2D image analysis 403 Let us denote F=(T1,1,...T1,n1,T2,1,...T2,n2),whereT1,∗are 0-trees (with ∗∈ {1,...,n1})ofFand T2,∗are 1-trees (with ∗∈{1,...,n2})of F. Let us suppose that the sink sis not in O. Then, the following results hold: (a) the (unpaired) vertices in O(also called critical vertices) are representative cycle generators of the corresponding connected components of O. Therefore cis the number of connected components in O. (b) any unpaired 1-cell (u,v) (also called critical edge) gives rise to a 1-homology generator fitting geometrically with the outer or some inner boundary of O.In fact, this homology cycle is obtained by the formula {u,v}+φ(u)+φ(v).Ifthe complementary of Ohas hconnected components (including background), the number of critical edges is h−1. Associated to each critical edge, there is a 1- tree of F. The number of 1-cells corresponding to critical edges of a 1-tree of Fcan be greater than one. Each critical edge can be “moved” along its associated tree Tm,n,inorderto get different representative cycles of the corresponding 1-homology generator. This translation of the critical edge can be done using reversing-arrow operations. It is clear that a HSF-representation based on an object of interest Ois also suitable for obtaining homology information about the complementary of O. In Fig. 15 two different HSF representations of an object of interest are shown. The black edge represents the 1-homology generator of the hole in the object. The homology cycle is colored in blue. Fig. 15 Two different examples of HSF-representations and the resulting homology generator (in blue) computed for the same object of interest 404 H. Molina-Abril, P. Real Moreover, we can easily deal with cohomology information starting from a HSF representation of an object. For example, the tree T{u,v}associated to each critical edge (u,v)determines in a straightforward manner a representative cocycle cTof a cohomology generator of dimension 1. This cochain cT:{1−cells ∈L(O)}→Z/2Z is not null only for the vertices (that is, the 1-cells of L(O)) belonging to the tree Tu,v. In Fig. 16 we show how cohomology can be equivalent to a type of paths in the HSF representation such that if we “cut” the object through this path, the resulting object has one hole less than before. We have asserted in the abstract that the HSF framework produces algorithmic answers to certain problems related to the homological classification of cycles (i.e., a sum of cells having zero boundary). The main important ones in the area of discrete image processing are the shortest cycle, contractibility and transformability problems. The shortest cycle problem is a generalization of the well-known shortest path problem [8] and can be stated as follows: Given a cycle con a cell complex version Kof a ROI, what is the shortest cycle on Khomologically equivalent to it? The contractibility problem consists of checking wether a cycle can be contracted to a point and the transformability problem analyses wether two cycles can be transformed into each other. These problems have significant connections with another in computational topology: to determine the fundamental group of Kor, equivalently, to construct a polygonal schema (cut a closed genus gsurface to a canonical polygon with 4gedges). The work of Gouillard [19] gives a very complete account of the state of the art about these questions, treating them under a homotopical perspective. We limit ourselves to demonstrate that contractibility and transformability problems can be automatically solved using the chain contraction (fFK,gFK,φFK)canonically associated to an HSF structure FKof a ROI K. Given a contractible q-cycle con K, then we have: c+gKfK(c)=∂KφK(c)+φK∂K(c) Since ∂K(c)=0(cis a cycle) and fK(c)=0(because cis contractible and its associated homology generator is zero), we reduce the previous equality into the following one: c=∂KφK(c) That means, that φK(c)is the (q+1)-chain whose boundary is c(Fig. 17). Fig. 16 A HSF-representation (on the left) and the path (on the right picture, in black) representing cohomology Homological spanning forest framework for 2D image analysis 405 Fig. 17 An acyclic scenario, one cycle cin blue, and the corresponding sum of 2-cells φK(c)in strong green color Given now two q-cycles homologically equivalent cand c, then: c+gKfK(c)=∂KφK(c) c+gKfK(c)=∂KφK(c) If we subtract one equation from another, we have: c+c=∂KφK(c−c) Fig. 18 A simple scenario of acyclic ambiance, two cycles c and cin blue and grey, respectively and the sum of 2-cells composing φK(c+c)in strong green color 406 H. Molina-Abril, P. Real due to the fact that gKfK(c)=gKfK(c). That means that φK(c+c)is the (q+1)- chain whose boundary is the difference between the original cycles (Fig.18). 6 Parallel homology-based processing Within this context of homology-based processing, it is possible to exploit data parallelism. Although the methods designed here open the possibility to a parallel processing, we are still far from devising a realistic and practical parallel approach. Being nthe number of pixels or 0-cells in L, the idea is to decompose the cell complex Linto nsubsets of cells, each of them included into the neighborhood of a concrete vertex. We consider as many Processing Elements (PE) as pixels the image has. A PE(v) in this architecture consists of a subset Eof cells having a pixel vwith integer coordinates (x,y)as element of its boundary. More concretely: E={(x,y)},{(x,y), (x−1,y+1)}+,{(x,y), (x−1,y+1)}−,{(x,y), (x+1,y)}, {(x,y), (x−1,y), (x−1,y+1)},{(x,y), (x−1,y+1), (x,y+1)}, {(x,y), (x,y+1)},{(x,y), (x+1,y+1)}+,{(x,y), (x+1,y+1)}−, {(x,y), (x,y+1), (x+1,y+1)},{(x,y), (x+1,y), (x+1,y+1)}, {(x,y), (x+1,y), (x+1,y+1), (x,y+1)} where (x,y)±indicates the respective upper (+)andlower(−) diagonal edges. In order to clarify this idea, a PE is shown on the left image of Fig. 19. The pixel Pis represented in green, the six 1-cells in blue, the four triangular-like 2-cells in yellow, and the one square 2-cell in orange. As it is shown in the middle image of Fig. 19, we consider that the cells {(x,y), (x− 1,y+1)}−and {(x,y), (x−1,y), (x−1,y+1)}are always paired. Given a pixel which is not the sink, the task consists of pairing the vertex Pwith an edge of E, being paired the rest of cells in Ein a straightforward manner. For example, if we pair Pwith the edge {(x,y), (x−1,y+1)}+, then the pairing of the rest of cells is (see right image of Fig. 19): ({(x,y), (x,y+1)},{(x,y), (x−1,y+1), (x,y+1)}), ({(x,y), (x+1,y+1)}+,{(x,y), (x,y+1), (x+1,y+1)}), ({(x,y), (x+1,y+1)}−,{(x,y), (x+1,y), (x+1,y+1)}), ({(x,y), (x+1,y)},{(x,y), (x+1,y), (x+1,y+1), (x,y+1)}) Fig. 19 APEontheleft and a pairing example on the right Homological spanning forest framework for 2D image analysis 407 This procedure is specified in the following algorithm: Algorithm 4 (Parallel optimal discrete gradient vector field) PE(v) is a unit processing element “centered” at pixel v. for each PE(v) parallel do Choose one edge e having as source the vertex v. Establish the pair {v,e}. Pair the rest of incident edges and 2-cells in PE(v). end Taking nprocessors (as many as pixels the image has), the speedup Sn, measuring how much the parallel algorithm of establishing a random acyclic combinatorial chain homotopy operator φis faster than the corresponding sequential algorithm, is ideal. That means that Sn=n 1=nand its efficiency is 1. We suppose here that the sink of φis always a priory known pixel. 7 Conclusions Several applications in digital imagery are in need of a flexible and topologicallyconsistent framework for nD object analysis and recognition. We have presented here a new 2D digital image processing framework based on chain homotopies determining an advanced topological analysis of cell complexes. The main notion in this framework is called Homological Spanning Forest (or HSF, for short) for a digital object due to the fact that it can be considered as a suitable generalization to higher dimensional cell complexes of the topological meaning of a spanning tree of a geometric graph. This new model for a digital object Ois a set of directed forests, which can be constructed under an underlying cell complex format K(I)of the image. Taken as initial data, a 2D digital image Iand a set of ROIs R1,R2,...,Rtpreviously determined by means of an image processing algorithm, we follow the sequence: (1) To construct an initial HSF representation for a whole 2D digital image Ithat is independent of the pixel contents of it and that “suits” well with the concrete task we want to do. (2) To construct a new HSF configuration “adapted” to the ROIs, from which new HSF structures for the last ones can be almost automatically obtained and a subsequent topological analysis of them can be done. This schema focus on transforming conceptual level information starting from relevant logical level knowledge. It is also possible to deduce new logical level structures from the data at pixel level, remaining “untouched” the HSF system that is fixed at the very beginning. In this case, the result at conceptual level could be interpreted in highly hierarchical terms (quad-trees, pyramids,...). In the immediate future, we have the intention of progressing to the following directions: (a) A short-term objective is to extend this method to higher dimensions. This would allow a fast topological-controlled processing of big images like for example medical 4D images. Whereas the study of 2D and 3D digital images has been very fruitful, in the study of 4D-phenomena many research questions 408 H. Molina-Abril, P. Real related to the topology are still fully open. 4D-images analysis is an important next step, because it adheres to the dimensionality of what is the physical reality. We also intend to achieve parallelism in this context. (b) The application of the HSF schema brings many advantages for fast geometrical transformations of images, and for implementing flexible and reliable methods for structural image analysis (see for instance [12]). Depending of the application we want to deal with, it seems possible to modulate the potential full flexibility of the proposed framework, in such a way that its conceptual description would be suitable for a concrete topological task (skeletons, thinning, Reeb graphs, mathematical morphology, etc). (c) To integrate in the HSF framework persistence homological techniques [9], discrete differential forms methods [7] and Morse Homology descriptors [1]. (d) A carefully study about cycle transformability questions and others related to relative homology and advanced algebraic topological information (cohomology algebra, homology A(∞)-coalgebra, cohomology operations,....) in 3D or 4D HSF context will also be done in a future work. The computational homological algebra framework developed in [34] for HSF operators will be essential for advancing in this area. Acknowledgements This work has been partially supported by the Andalusian Research Group CATAM FQM-296, and the Spanish MICINN Research Project MTM2009-12716. The first author has also been partially supported by the Austrian Science Fund under grant P20134-N13. References 1. Allili, M., Corriveau, D.: Topological analysis of shapes using Morse theory. Comput. Vis. Image Underst. 105, 188–199 (2007) 2. Ankeney, L.A., Ritter, G.X.: Cellular topology and its applications in image processing. Int. J. Parallel Program. 12, 433–456 (1983) 3. Ayala, R., Domínguez, E., Francés, A.R., Quintero, A.: Determining the components of the complement of a digital (n-1)-manifold in Zn. In: Proceedings of the 6th International Workshop on Discrete Geometry for Computer Imagery, pp. 163–176. Springer-Verlag, London, UK (1996) 4. Bertrand, G., Couprie, M.: On parallel thinning algorithms: minimal non-simple sets, p-simple points and critical kernels. J. Math. Imaging Vis. 35, 23–35 (2009) 5. Cardoze, D., Miller, G., Phillips, T.: Representing topological structures using cell-chains. In: Geometric Modeling and Processing, pp. 248–266. Pittsburgh, PA (2006) 6. Chassery, J.M.: Connectivity and consecutivity in digital pictures. Comput. Graph. Image Process. 9(3), 294–300 (1979) 7. Desbrun, M., Kanso, E., Tong, Y.: Discrete differential forms for computational modeling. In: ACM SIGGRAPH 2005 Courses, SIGGRAPH ‘05. ACM, New York, NY, USA (2005) 8. Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1, 269–271 (1959) 9. Edelsbrunner, H., Letscher, D., Zomorodian, A.: Topological persistence and simplification. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pp. 454–463. IEEE Computer Society, Washington, DC, USA (2000) 10. Eilenberg, S., Mac Lane, S.: On the groups H(π, n), i, ii, iii. Ann. Math 58, 60, 60, 55–106,48–139, 513–557 (1953,1954) 11. El-Kwae, E.A., Kabuka, M.R.: Binary object representation and recognition using the Hilbert morphological skeleton transform. Pattern Recogn. 33(10), 1621–1636 (2000) 12. Feichtinger, H.G., Onchis, D.M.: Constructive realization of dual systems for generators of multiwindow spline-type spaces. J. Comput. Appl. Math. 234, 3467–3479 (2010) 13. Forman, R.: A discrete Morse theory for cell complexes. In: Yau, S.T. (ed.) Geometry, Topology and Physics for Raoul Bott. International Press (1995) Homological spanning forest framework for 2D image analysis 409 14. Forman, R.: Morse theory for cell complexes. Adv. Math. 134, 90–145 (1998) 15. González-Diaz, R., Jiménez, M., Medrano, B., Molina-Abril, H., Real, P.: Integral operators for computing homology generators at any dimension. In: Ruiz-Shulcloper, J., Kropatsch, W. (eds.) Progress in Pattern Recognition, Image Analysis and Applications. Lecture Notes in Computer Science, vol. 5197, pp. 356–363. Springer Berlin/Heidelberg (2008) 16. González-Díaz, R., Jiménez, M.J., Medrano, B., Real, P.: Chain homotopies for object topological representations. Discrete Appl. Math. 157(3), 490–499 (2009) 17. González-Díaz, R., Jiménez, M.J., Medrano, B., Real, P.: A tool for integer homology computation: λ-AT-model. Image Vis. Comput. 27(7), 837–845 (2009) 18. González-Díaz, R., Real, P.: On the cohomology of 3d digital images. Discrete Appl. Math. 147(2–3), 245–263 (2005) 19. Gouaillard, A.: Contexte générique bi-multirésolution basé ondelettes pour l’optimisation d’algorithmes de surfaces actives. Ph.D. thesis, Inst. National des Sciences Appliquées de Lyons (2005) 20. Gugenheim, V.K.A.M., Lambe, L.A., Stasheff, J.D.: Perturbation theory in differential homological algebra. Ill. J. Math 33, 357–373 (1989) 21. Gugenheim, V.K.A.M., Lambe, L.A., Stasheff, J.D.: Perturbation theory in differential homological algebra. ii. Ill. J. Math. 35(3), 357–373 (1991) 22. Kaczynski, T., Mrozek, M., Slusarek, M.: Homology computation by reduction of chain complexes. Comput. Math. Appl. 35(4), 59–70 (1998) 23. Khalimsky, E.: Pattern analysis of n-dimensional digital images. In: Proc. IEEE Int. Conf. Systems, Man and Cybernatics, pp. 1559–1562 (1986) 24. Klette, R.: Cell complexes through time. In: Latecki, L.J., Mount, D.M., Wu, A.Y. (eds.) Proc. Vision Geometry IX, vol. 4117, pp. 134–145 (2000) 25. Klette, R., Rosenfeld, A.: Digital Geometry: Geometric Methods for Digital Picture Analysis. Morgan Kaufmann Series in Computer Graphics (2004) 26. Kong, T.Y., Kopperman, R., Meyer, P.R.: A topological approach to digital topology. Am. Math. Mon. 98, 901–917 (1991) 27. Kovalevsky, V.: Finite topology as applied to image analysis. Comput. Vis. Graph. Image Process. 46, 141–161 (1989) 28. Kovalevsky, V.: Algorithms in digital geometry based on cellular topology. Lect. Notes Comput. Sci. 3322, 366–393 (2005) 29. Kovalevsky, V.: Axiomatic digital topology. J. Math. Imaging Vis. 26, 41–58 (2006) 30. Kovalevsky, V.: Geometry of Locally Finite Spaces. House Dr. Baerbel Kovalevski (2008) 31. Kropatsch, W.G., Haxhimusa, Y., Ion, A.: Multiresolution image segmentations in graph pyramids. In: Kandel, A., Bunke, H., Last, M. (eds.) Applied Graph Theory in Computer Vision and Pattern Recognition. Studies in Computational Intelligence, vol. 52, pp. 3–41. Springer (2007) 32. Lienhardt, P.: Topological models for boundary representation: a comparison with n-dimensional generalized maps. Comput.-Aided Des. 23(1), 59–82 (1991) 33. Molina-Abril, H., Real, P.: Homological computation using spanning trees. In: CIARP 2009. Lecture Notes in Computer Science, vol. 5856, pp. 272–278 (2009) 34. Molina-Abril, H., Real, P.: Towards optimality in discrete Morse theory through chain homotopies. In: CTIC 2010, Imagen-a, vol. 1, pp. 33, 40 (2010) 35. Molina-Abril, H., Real, P.: Homological optimality in discrete Morse theory through chain homotopies. Pattern Recog. Lett. (2012). doi:10.1016/j.patrec.2012.01.014 36. Parker, J.: Algorithms for Image Processing and Computer Vision. Wiley, New York (1997) 37. Romero, A., Sergeraert, F.: Discrete vector fields and fundamental algebraic topology. CoRR abs/1005.5685 (2010) 38. Romero Rodríguez, B., Falces Sánchez, J.: Homología y Arboles Recubridores. Master’s thesis, E.T.S. Ingeniería Informática, Universidad de Sevilla, Spain (2009) 39. Rosenfeld, A.: Connectivity in digital pictures. J. Assoc. Comput. Mach. 17(1), 146–160 (1970) 40. Sergeraert, F.: The computability problem in algebraic topology. Adv. Math. 104, 1–29 (1994) 41. Webster, J.: Cell complexes and digital convexity, pp. 272–282. Springer, New York (2001) 42. Whitehead, J.: Combinatorial homotopy i. Bull. Amer. Math. Soc. 55, 213–245 (1949)