Invariant representative cocycles of cohomology generators using irregular graph pyramids

arXiv:1105.3559v4 [cs.CV] 13 Jul 2011 Invariant Representative Cocycles of Cohomology Generators using Irregular Graph Pyramids Rocio Gonzalez-Diaza, Adrian Ionb,d, Mabel Iglesias-Hamb,c, and Walter G. Kropatschb aApplied Math Department, School of Computer Engineering University of Seville, Reina Mercedes Avenue, CP: 41012 Seville, Spain [email protected] bPattern Recognition and Image Processing Group, Vienna University of Technology, Faculty of Informatics, Institute of Computer Aided Automation, Favoritenstr. 9/1832, A-1040 Vienna, Austria. {ion,mabel,krw}@prip.tuwien.ac.at cPattern Recognition Department, Advanced Technologies Application Center, 7th Avenue #21812 %218 and 222, Siboney Neighborhood, Playa, C.P. 12200, Havana City, Cuba. [email protected] dInstitute for Numerical Simulation Faculty of Mathematics and Natural Sciences, University of Bonn, Wegelerstr. 6, 53115 Bonn, Germany. Abstract Structural pattern recognition describes and classifies data based on the relationships of features and parts. Topological invariants, like the Euler number, characterize the structure of objects of any dimension. Cohomology can provide more refined algebraic invariants to a topological space than does homology. It assigns ‘quantities’ to the chains used in homology to characterize holes of any dimension. Graph pyramids can be used to describe subdivisions of the same object at multiple levels of detail. This paper presents cohomology in the context of structural pattern recognition and introduces an algorithm to efficiently compute representative cocycles (the basic elements of cohomology) in 2D using a graph pyramid. An extension to obtain scanning and rotation invariant cocycles is given. Keywords: graph pyramids, representative cocycles of cohomology generators Preprint submitted to Computer Vision and Image Understanding July 2010 1. Introduction Image analysis deals with digital images as input to pattern recognition systems with the purpose to extract information about their content, usually objects. Objects appear in images affected by transformations (e.g. rotation, zoom, projection) and noise. Topological features have the ability to ignore changes in the geometry of objects by extracting object properties invariant to elastic transformations. Simple topological features are for example the number of connected components, the number of holes, etc., while more refined ones, like homology and cohomology, characterize holes and their relations. An example application of topological features is topology simplification, an active field in geometric modeling and medical imaging where highresolution surfaces are created through iso-surface extraction from volumetric representations, obtained by 3D photography, CT, or MRI. Iso-surfaces often contain many topological errors in the form of tiny handles. These nearly invisible artifacts hinder subsequent operations like mesh simplification, remeshing, and parametrization. See, for example [1]. Another application is shape description and matching, where persistence and homology of a function defined on a shape have been successfully applied to extract shape features [2]. A 2D image is the result of projecting a 3D scene into the image plane. Often the precise camera parameters are not known and still humans have no problem in correctly interpreting the displayed objects in the image. A 3D object is surrounded by a reflecting surface which itself may split into several smaller but connected patches which can be characterized by their color, their texture or other visual properties. The visible part of the object’s surface maps into a region of the image which shows the same adjacencies of patches as the original surface (because the camera sees the same side of the surface) although the geometry of the patches may change due to projection, due to camera or object movement or due to deformations of the object. Sometimes a collection of patches is completely surrounded by some other surface patches, e.g. a fancy soccer ball on a Spanish T-shirt (see Fig. 1). Although both the picture of the ball as well as the T-shirt may have a specific patch structure (stripes on shoulder and arms, logo) it is clear which subset of regions forms the ball and which regions belong to the remaining T-shirt. A simplified version could describe the pixels of the T-shirt 1’s and the ball’s pixels by 0 (see Fig. 1). Then the ball is a hole in the T-shirt 2 a) b) Figure 1: a) Original image: ball on T-shirt of world champions 2010 in soccer; b) a segmentation of the original image using pyramids. as long as the surrounding of the ball is visible and not occluded by other objects. It may be highly difficult to uniquely and reliably identify any of the involved small patches individually under difficult geometric deformations while the overall arrangement of patches forming the ball is mostly invariant to these geometric deformations. How to segment patches into meaningful aggregations has been dealt with in many other segmentation methods and it is not the main emphasis of this paper. We therefore restrict ourselves in the following on binary images with the understanding that each region may be the collection of several subregions belonging together. Considering 2D binary images, an object is defined by a connected set (4connectivity) of foreground pixels. A region adjacency graph (RAG) encodes the adjacency of regions in a partition. The holes in a RAG associated to an object of a 2D binary digital image can be characterized by establishing an equivalence between all the cycles as follows: two cycles are equivalent if one can be obtained from the other by joining to it one or more degenerate cycles (cycles with exactly 4 edges). For example, there is only one equivalence class for the foreground (gray pixels) of the digital image in Fig. 2, which represents the unique white hole. This is similar to considering the digital image as a cell complex1[3] (see Fig. 2.c). Unfortunately digital images are not ‘clean’, noise can create many unwanted holes which complicate the correct interpretation. One can ask for the edges we have to delete in order 1Intuitively a cell complex is defined by a set of 0-cells (vertices) that bound a set of 1-cells (edges), that bound a set of 2-cells (faces), etc. 3 to ‘destroy’ a hole. In the example in Fig. 2, it is not enough to delete only one edge. The deletion of the bold edges in Fig. 2.c together with the faces that they bound produces the ‘disappearing’ of the hole. The set of bold edges in Fig. 2.c define a 1-cocycle, a topological invariant of the respective object. Equivalence classes of such cocycles are the elements of cohomology. To cope with complexity issues that arise when highly complex algorithms must be applied to huge amounts of data, graph pyramids are used. These hierarchical data structures offer possibilities to reduce the amount of data by local operations which can be applied in parallel and which have the enormous advantage to preserve the topological properties of the data. Hence the search for independent cocycles can be correctly done on a fraction of the data at the top of the pyramid. The simplified geometry of these cocycles can then be delineated top-down through the levels of the pyramid by again local processes up to the high accuracy of the base level. Maybe due to its more abstract nature, lacking a geometric meaning and due to its computation complexity, cohomology has not been yet widely applied to pattern recognition and image processing. This paper is possibly the first attempt to use it in the context of digital images. For this purpose, in this paper we consider the best known environment which are 2D images whereas nD is the ultimate goal. Concepts related to cohomology can have associated interpretations in graph theory. Having these interpretations opens the door for applying classical efficient graph theory algorithms to compute and manipulate these features. Besides, for objects embedded in R3, homology– a wider used topological invariant, and cohomology groups are isomorphic. But the ring structure presented in cohomology characterizes the relations between 2-holes (cohomology generators of dimension 1), which homology does not. Indeed, dealing with homology and cohomology properties, representative cycles and cocycles, and their computation is quite different and doing this study in 2D gives important insights which should be relevant for extension to nD, n > 2. Initial results regarding this work have been presented in [4]. The current paper extends our earlier publication with detailed insights and proofs, and a refinement of the previous method that makes the obtained cocycles scanning and rotation invariant in the case of an identical discretization. The paper is organized as follows: Sections 2 and 3 recall graph pyramids and cohomology, and make initial connections. In Section 4, preservingtopology properties in irregular graph pyramids are given. Section 5 presents the proposed method. Section 6 uses the properties of the proposed method 4 a) b) c) d) Figure 2: a) A 2D digital image I; b) its RAG; c) a cell complex associated to I(with bold edges, a representative cocycle); and d) the cell complex without the hole. to extend it and obtain scanning and rotation invariant cocycles. Section 7 concludes the paper. 2. Irregular Graph Pyramids A graph (see for example [5]) is an ordered pair G= (V, E) comprising a set Vof vertices and a set Eof edges. Each edge e∈Eis incident to two not necessarily distinct vertices v, w ∈V, written as e= (v, w). An edge e= (v, w) is said to be directed if the pair (v, w) is an ordered pair. An edge is said to be a self-loop if v=w. The edge e= (v, w) is called a parallel edge iff ∃e′∈E, e′6=es.t. e′= (v, w). A graph is called undirected if none if its edges is directed, and it is called planar if it can be drawn in a plane with no edges crossing (vertices are drawn as points and edges as lines connecting their incident vertices). Given a graph G= (V, E) removing an edge e∈Ewill result in the graph G′= (V, E \ {e}), contracting the edge e= (v, w) implies removing it and identifying its incident vertices s.t any remaining edge previously incident to vor wis now incident to the unique vertex v=w. Given a decomposition of an object or image into regions a region adjacency graph (RAG) is an undirected graph that encodes the adjacency of regions in a partition. A vertex is associated to each region, vertices of neighboring regions are connected by an undirected edge. Classical RAGs do not contain any self-loops or parallel edges. An extended region adjacency graph (eRAG) is a RAG that contains the so-called pseudo edges, which are self-loops and parallel edges used to encode neighborhood relations to a cell completely enclosed by one or more other cells [6]. The dual graph of an eRAG Gis called a boundary graph (BG) and is denoted by ¯ G(Gis said to be the primal graph of ¯ G). The edges of ¯ Grepresent the boundaries (borders) of the regions encoded by G, and the vertices of ¯ Grepresent points 5 Figure 3: A digital image I, and boundary graphs ¯ G6,¯ G10 and ¯ G15 of the pyramid of I. where boundary segments meet. Gand ¯ Gare planar graphs. There is a one-to-one correspondence between the edges of Gand the edges of ¯ G, which induces a one-to-one correspondence between the vertices of Gand the 2D cells (will be denoted by faces2) of ¯ G. The dual of ¯ Gis again G. The following operations are equivalent: edge contraction in Gwith edge removal in ¯ G, and edge removal in Gwith edge contraction in ¯ G. A (dual) irregular graph pyramid [7, 8, 6, 9] is a stack of successively reduced planar graphs P={(G0,¯ G0),...,(Gn,¯ Gn)}. Each level (Gk,¯ Gk), 0< k ≤n, is obtained by first contracting edges in Gk−1(removal in ¯ Gk−1), if their end vertices have the same label (regions should be merged), and then removing edges in Gk−1(contraction in ¯ Gk−1) to simplify the structure. The contracted and removed edges are said to be contracted or removed (sometimes called removal edges) in (Gk−1,¯ Gk−1). In each Gk−1and ¯ Gk−1, contracted edges form trees called contraction kernels. One vertex of each contraction kernel is called a surviving vertex and is considered to have ‘survived’ to (Gk,¯ Gk). The vertices of a contraction kernel in level k−1 form the reduction window of the respective surviving vertex vin level k. The receptive field of vis the (connected) set of vertices from level 0 that have been ‘merged’ to vover levels 0,...,k. The equivalent contraction kernel (ECK) of a vertex vis the tree obtained by replacing vand all is descendants with their corresponding contraction kernels. The vertices of the ECK of vform the receptive field of v. Algorithm 1 gives the main steps used to build a graph pyramid. In Line 5 the operations are performed on both graphs (adjacency and boundary) even if for simplicity only one of the graphs is mentioned in each step. Line 5.ii removes self-loops bounding an empty face in the adjacency graph. Line 5.iii simplifies the region boundaries in the boundary graph. 2Not to be confused with the vertices of the dual of a RAG (sometimes also denoted by the term faces). 6 Algorithm 1 Build (dual) graph pyramid Input: image I/*pixels labeled ‘object’ or ‘background’*/ 1: (G0,¯ G0) = ((V0, E0),(¯ V0,¯ E0)) /*V0associates a vertex to every pixel. E0connects vertices corresponding to 4-connected pixels. G0and ¯ G0are dual.*/ 2: k= 0 3: repeat 4: /*select edges to contract*/ T=∅ for all v∈Gkdo i. select an edge (v, w)∈Gkwith v, w having the same label ii. T←T∪(v, w) /*add edge*/ 5: if T6=∅then /*region merging, easier described in the adjacency graph:*/ i. (G′,¯ G′)←contract edges Tof Gk(removal in ¯ Gk) /*simplification, easier described in the boundary graph:*/ ii. (G′′,¯ G′′)←contract pending trees in ¯ G′(removal in G′) iii. (Gk+1,¯ Gk+1)←contract one distinct edge incident to each vertex of degree 2 in ¯ G′′ (removal in G′′) 6: k←k+ 1 7: until T=∅ Output: Graph pyramid P={(G0,¯ G0),...,(Gk−1,¯ Gk−1)}. 3. Homology, Cohomology and Integral Operators We refer to [10] for an introduction to homology and cohomology. Intuitively, homology characterizes the holes of any dimension (i.e. connected components, 1-dimensional holes, etc.) of an n-dimensional object. It defines the concept of generators which, for example for 2D objects are similar to closed paths of edges surrounding holes. More general, k-dimensional manifolds surrounding (k+ 1)-dimensional holes are generators [10], and define equivalence classes of (k+1)-holes. Cohomology arises from the algebraic dualization of the construction of homology. It manipulates groups of homomorphisms to define equivalence classes. Intuitively, cocycles (the invariants computed by cohomology), represent the sets of elements (e.g. edges) to be removed to destroy certain holes. See Fig. 2.c for an example cocycle. 7 0-cells {v1, v2, v3, v4} 1-cells {e1, e2, e3, e4, e5, e6} 2-cells {f1} 1-chain e1+e3 1-boundary ∂f1=e1+e2+e5 1-cycle a=e3+e4+e5 1-cycle b=e1+e2+e3+e4 homologous cycles aand b; since a=b+∂f1 Figure 4: Example of cell, chain, boundary and cycle. Ahomeomorphism is a bijective continuous function between two spaces, that has a continuous inverse function. They are the mappings which preserve all the topological properties of a given space. Two spaces with a homeomorphism between them are called homeomorphic, and from a topological viewpoint they are the same. Two continuous functions from one topological space to another are called homotopic if one can be ‘continuously deformed’ into the other. Two spaces X and Yare homotopy equivalent if there are maps f:X→Yand g:Y→X such that gf is homotopic to idXand fg is homotopic to idY. Observe that if two spaces are homeomorphic then they are homotopic. A homotopy invariant is a topological property which is invariant under homotopy. Ap-dimensional cell (or p-cell, for short) is a topological space that is homeomorphic to the p-dimensional ball Bp. A 0-cell is homeomorphic to a point, a 1-cell to an arc and a 2-cell to a disk. Roughly speaking, a cell- (or CW-) complex is built by gluing together the basic building blocks called cells. Figures 4 and 5 illustrate the following abstract concepts. 3.1. Homology The notion of p-chain is defined as a formal sum of p-cells. The chains are considered over Z/2 coefficients i.e. a p-cell is either present in a pchain (coefficient 1) or absent (coefficient 0) - any cell that appears twice vanishes. The set of p-chains form an abelian group called the p-chain group Cp. This group is generated by all the p-cells. The boundary operator is a set of homomorphisms {∂p:Cp→Cp−1}p≥0connecting two consecutive dimensions. By linearity, the boundary of any p-chain is defined as the formal 8 0-cochain {v1} 1-cochain {e1, e4} 1-coboundary δ{v1}={e3, e4} 1-cocycle c={e1, e2} 1-cocycle d={e1, e2, e3, e4} homologous cocycles cand d; since d=c+δ{v1} Figure 5: Example of cochain, cocycle and coboundary. sum of the boundaries of each p-cell that appears in the chain. The boundary of 0-cells (i.e. points) is always 0. A chain complex is the set of all the chain groups connected by the boundary operator: ··· ∂p+1 →Cp ∂p →Cp−1→ · · · ∂1 → C0 ∂0 →0. Ap-chain σis called a p-cycle if ∂p(σ) = 0. If σ=∂p+1(µ) for some (p+ 1)-chain µthen σis called a p-boundary. Two p-cycles aand a′are homologous if there exists a p-boundary bsuch that a=a′+b. Denote the groups of p-cycles and p-boundaries by Zpand Bprespectively. For each p, ∂p−1∂p= 0. In other words, all p-boundaries are p-cycles (Bp⊆Zp). Define the pth homology group to be the quotient group Hp=Zp/Bp, for all p. Each element of Hpis a class obtained by adding each p-boundary to a given p-cycle a. Then ais a representative p-cycle of the homology class a+Bp. Since the chains are considered over Z/2 coefficients, the chain groups are vector spaces and the boundary operators are linear operators. The cycle and and boundary groups are just the kernel and image of such operator. The homology group is a quotien space. 3.2. Cohomology Cohomology groups are constructed by turning chain groups into groups of homomorphisms and boundary operators into their dual homomorphisms. Define a p-cochain as a homomorphism c:Cp→Z/2. We can see a p-cochain as a binary mask of the set of p-cells: imagine you order all p-cells in the complex. (let’s say we have n p-cells, and call this ordered set Sp). Then a p-cochain cis a binary mask of nvalues in {0,1}n, where nis the number of p-cells in the complex. When no confusion can arise, we will identify the p-cochain cwith the set Sof p-cells that are evaluated to 1 by c. The p-cochains form the set Cpwhich is a group. The boundary operator defines a dual set of homomorphisms, the coboundary operator {δp:Cp→ Cp+1}p≥0, such that δp(c) = c∂p+1 for any p-cochain c. Since the coboundary 9 Let KHbe the homology-generator level. Without loss of generality, we can suppose that KHis connected. If not, repeat the following reasoning for each connected component (region) of KH. Let {α1,...,αn}be the set of the self-loops surrounding a face of the background. Therefore, there are nwhite holes: O1,...On(see Fig. 8.d). Fix i,i= 1,...,n,αiis a representative 1cycle of the homology generator associated to the white hole Oi. Let βbe a self-loop surrounding the face fof the foreground (recall that we suppose that KHis connected) such that αiis in the boundary of fin KH. Form the sets {α1, β},...,{αn, β}. Let K0denote the boundary cell complex associated to the foreground in ¯ G0. Let {φp:Cp(K0)→Cp+1(K0)}p≥0be the composition of all integral operators associated with all removals and contractions of edges of the foreground of the boundary graphs of a given irregular graph pyramid. Let {πp=idp+φp−1∂p+∂p+1φp:Cp(K0)→Cp(KH)}p≥0where {ιp:Cp(KH)→Cp(K0)}p≥0is the inclusion map. Proposition 5.1. The 1-cochain α∗ idefined by the set {αi, β}in KHis a 1cocycle. Moreover, the set {α∗ 1,...,α∗ n}is a basis of representative 1-cocycles. Proof. The set of edges of KHis the set of the self-loops {α1,...,αn}surrounding a region of the background together with the self-loop β, renamed by αn+1, surrounding the face f. The 1-cochain α∗ iis a cocycle in KHiff δ1(α∗ i) = 0. Since we work with objects embedded in R2then αican only be in the boundary of two faces. In this case, one face belongs to the background and the other face is fin KH. Then δ1(α∗ i)(f) = α∗ i(∂2(f)) = α∗ i(αi+β+···) = α∗ i(αi) + α∗ i(β) + α∗ i(···) = 1 + 1 + 0 = 0. Let us prove minimality. Suppose, for example, that α∗ 1=α∗ j1+···+α∗ js where 1 < j1< . . . < js≤n,s≥1. Then α∗ 1is defined by the set {αj1,...,αjs}if seven, and {αj1,...,αjs, β}if sodd, which is a contradiction.  We will say that α∗ iis a representative 1-cocycle of the cohomology generator associated to the white hole Oi. Algorithm 2 gives the proposed method to downproject a cocycle α∗from level kto level k−1. Informally, in the homology-generator level, there is only one face representing the object. Based on the geometric interpretation of cocycles (Section 3), if we remove the edges and the face in-between, we destroy the hole. Then, there is no need to add any other edge to the cocycle to remove the hole. However, when going down in the pyramid, this face 16 Algorithm 2 Down project cocycle For each connected component (region) of KH. Let Ak, k > 0,denote the set of edges that define a cocycle in ¯ Gk(the boundary graph in level k). The down projection of Akto ¯ Gk−1is the set of edges Ak−1⊆¯ Gk−1that corresponds to Aki.e. represents the same cocycle. Ak−1is computed as Ak−1=As k−1∪Ar k−1, where As k−1denotes the set of surviving edges in ¯ Gk−1 that correspond to Ak, and Ar k−1is a subset of removed edges in ¯ Gk−1. The following steps show how to obtain Ar k−1: 1. Consider the contraction kernels of Gk−1(RAG) whose vertices are labeled with ℓ(the region for which cocycles are computed). The edges of each contraction kernel are oriented toward the respective root - each edge has a unique starting vertex. 2. For each contraction kernel T, from the leaves of Tto the root, let ebe an edge of T,vits starting point, and Evthe edges in the boundary of the face associated to v: label vwith the sum of the number of edges that are in both As k−1and in Ev, plus the labels of the children nodes of v. 3. A removal edge of ¯ Gk−1is in Ar k−1if the starting point of the corresponding edge of Gk−1is labeled with an odd number. is partitioned. A connection among all the new regions is determined by the contraction kernels of the RAG. When the first partitioning occurs, the contraction kernel will contain one or two nodes corresponding to faces with one surviving cocycle edge in its boundary, and the rest of the nodes will have none. What Algorithm 2 does is to find the unique path in the contraction kernel joining these two nodes, and take the set of boundary edges between consecutive faces as part of the new cocycle (see Prop. 6.2, 6.3, and their proofs). Lower levels will update the connections in subsections of the cocycle path. Every subsection will correspond to a partitioned region between two consecutive cocycle edges. Consider the example in Fig. 8. In the homology-generator level we have A5={α, β}the representative 1-cocycle of a cohomology generator (selfloops in Fig. 8.d). For down projection in level 4, A4=As 4∪Ar 4. We have that As 4is the surviving edges in bold of top level in Fig. 8.e). In this case, Ar 4=∅because there is no merging of foreground regions from the boundary cell complex obtained from the top level to the homology-generator level. 17 a) level 0 b) level 1 c) level 2 d) level 3 e) level 4 Figure 10: Top row: removed edges in boundary graph. Bottom row, from right to left: the down-projected cocycles in bold. Filled circles on faces, represent surviving vertices from the adjacency graph in foreground regions. In the example in Fig. 10, the cocycle α∗in level 4 is the set of the two edges in bold (see Fig. 10, bottom row, column d). The down projection from level 4 to 3 are the surviving edges of the cocycle in level 4. This is because there was no contraction in the foreground region. The contractions of the adjacency graph can be seen in the top row of the figure. In level 2 (Fig. 10, bottom row, column c), the first contraction of foreground in the adjacency graph with a single edge appears. In this case, the leaf node represents a face with an even number (2) of surviving cocycle edges in its boundary, which leads to not adding any other edge to the down-projected cocycle. Only in the base level (column a), one contraction kernel has a leaf node with an odd number (1) of surviving cocycle edges in the boundary. In this case, the corresponding edge in the boundary graph, for the edge connecting the respective node with its father, is added to the cocycle. Any edge ¯ G0that has survived to a higher level k, and was selected as part of the cocycle in ¯ Gk, will belong to the down-projected cocycle in ¯ G0. In particular, the edges in ¯ G0that have survived to be the edges α, β of the cocycle in the homology-generator level, are going to be the entry and exit point of the cocycle path through the foreground region. In Fig. 11, the space between the outside boundary of the object and the 18 d) e) f) g) Figure 11: a) Boundary cell complex obtained from the top level of the pyramid, (G4,¯ G4); b) homology-generator level with cocycles edges in bold; c) ECK of the foreground in RAG, drawn over ¯ G0with cocycle edges in bold; d) to g) shows removed edges in bold for levels from 3 to 0. Cocycle edges are marked with two small parallel lines. hole is bigger, allowing for more possibilities for the paths of the cocycle. The cocycle path in the base is going to converge to the unique path connecting the surviving edges α, β through the ECK (see Fig. 11.c). In Fig. 11.d the cocycle is made of the surviving cocycle edges from the homology-generator level in Fig. 11.b . The first partition of the foreground is connected by the contraction kernel in Fig. 11.e . Here, one of the regions in the partition contains in its boundary the two surviving cocycle edges, so there is no path to find and no new cocycle edge to add. In Fig. 11.f there is only one edge to add to the cocycle to connect the path of edges, which is identified with the leaf node with label 1. Notice that from level Fig. 11.f to the one in Fig. 11.g also the selected ‘surviving’ edges play a role, as edges to be removed at higher levels had to 19 have been ‘surviving’ ones at levels below. In this case, the edge we add to the cocycle in level 1 (Fig. 11.f), was a surviving edge in level below that was connecting two contraction kernels. Therefore, the selection of the surviving edges also determine the delineation of the down-projected cocycle together with the contracted ones. The ECK contains the decision of which edges were contracted but also which ones were simplified, determining the unique path. Proposition 5.2. 1. The down projection of α∗ iis a set of edges ‘blocking’ the creation of the hole Oi, i.e., given a cycle ghomologous to the down projection of the cycle αi, the down projection of α∗ icontains an odd number of edges of g. 2. The down projection of α∗ iis always a cocycle. Moreover, the down projection of {α∗ 1,...,α∗ n}is a basis of representative 1-cocycles. Proof. 1. The down projection of α∗ i, which is α∗ iπ1, contains an odd number of edges of giff α∗ i(g) = 1. First, if gis homologous to the down projection of αi, which is ι1(αi), then there exists a 2-chain bin K0such that g=ι1(αi) + ∂2(b). Second, α∗ iπ1(g) = α∗ iπ1(ι1(αi) + ∂1(b)) = 1, since α∗ iι1(αi) = α∗ i(αi) = 1, and α∗ iπ1∂2(b) = 0 because α∗ iis a cocycle and π1∂2=∂1π2(since {πp:Cp(K0)→Cp(K∗H)}p≥0is a chain equivalence [10]). So gmust contain an odd number of edges of the set that defines α∗ i. 2. Proof of correctness of the down projection algorithm: it is a consequence of Lemma 4.4.  Example down projections are shown in Fig. 9, 10, and 11. 5.1. Complexity Let nbe the height of the pyramid (number of levels) and v0, e0the number of vertices, respectively edges in the base level, with n≈log v0 (logarithmic height). An upper bound for the computation complexity is: O(v0n) to build the pyramid; for each foreground component, O(h) in the number of holes hto choose the representative cocycles in the top level; O(e0n) to down project each cocycle. The overall computation complexity 20 a) large hole - outer boundary b) small hole - outer boundary Figure 12: Example showing (top) normal and (bottom) rotation invariant cocycles. The cocycles are down-projected starting with the surviving edge of the outer boundary and the surviving edge of the a) large and b) small holes. is then below O(v0n+c(he0n)), where cis the number of cocycles that are computed and down projected. Actually not all edges are part of cocycles and not all levels have e0 number of edges. When building Ak−1one can go in linear time over the edges of Akand consider only the contraction kernels in Gk−1for which the surviving vertices in Gkcorrespond to one of the two faces to which an edge of Akis incident to. Then, computing Ak−1actually takes |Ak|+Pi|Ti k−1| number of steps, where Ti k−1∈Gk−1are the contraction kernels mentioned before. Thus in practice the complexity of down projecting a cocycle is below O(e0n). 6. A First Step Towards Stable Cocycles If topology is considered in the context of recognition, or a joint extraction of both topological and geometrical features is required, then the location and shape of the extracted topological invariants becomes relevant and is an important way to ensure stability/repeatability. A relevant example is the 21 work in [14] where handle and tunnel loops are made geometry aware by placing them on “geometrically relevant” positions. In this section we make a first stept towards obtaining stable cocycles and consider invariance with respect to scanning and rotation of the object. Because we start with a pixel grid and the 4 neighborhood,only rotations with multiple of 90 degrees produce identical discretizations allowing for identical cocycles. The following properties are required for Prop. 6.4 which gives the parts of the pyramid that the computed cocycles depend on. Proposition 6.1. The down-projected cocycles contain only removal edges in the boundary graphs, corresponding to edges in the ECK of the top vertex representing the object in Gn, and the two edges α, β that have survived to ¯ Gnand where selected as the cocycle α∗={α, β}. Proof. Algorithm 2 starts with two edges {α, β}in ¯ Gn, and for each level k=n−1,...,0 it adds only removal edges from ¯ Gki.e. edges that where contracted in Gkto merge neighboring regions belonging to the object.  Proposition 6.2. The result of down projection (Algorithm 2) does not depend on the selected surviving vertices in Gk. Proof. Consider the function q:T⊆Gk−1→N,q(T) = Pv∈T|As k−1∩Ev| (see Alg.2 for the used notation). Every cocycle Akhas an even number of edges from the boundary of any face in ¯ Gk(Section 3). Then q(T) is also even and the number of vertices vfor which |As k−1∩Ev|is odd, is even. For any edge e∈T= (V, E) consider the two connected components (trees) T1, T2 of the subgraph (V, E \ {e}) (eis a cut edge of Tbecause Tis a tree). The removal edge of ¯ Gk−1corresponding to the edge eis added to the cocycle if q(T1) and q(T2) are even, which is independent of the originally chosen surviving vertex, the root of T. Proposition 6.3. A down-projected cocycle does not depend on the order in which edges are removed in the boundary graphs (region merging). Proof. Consider the proof of Prop. 6.2. What Algorithm 2 does is to select additional edges from the contraction kernel T, to connect the vertices v with odd |As k−1∩Ev|. In a tree, there is a unique path connecting any two vertices. Denote by Kthe ECK of the vertex in Gncorresponding to the 22 a) b) Figure 13: a) original image; b) in bold, the paths in the RAG G0associated to the downprojected cocycles related to the holes representing the top-left and top-right windows. object. Algorithm 2 returns αand β, plus the set of edges of ¯ G0corresponding to the path in Kthat connects the two vertices whose corresponding faces in ¯ G0have αand βin their boundary. The ECK of a vertex does not depend on the order of the intermediate steps [15].  The following property is an immediate result of Properties 6.1, 6.2, and 6.3. Proposition 6.4. The cocycles computed by Algorithm 2 depend only on the cocycle {α, β}chosen in the top level, (Gn,¯ Gn), and on the ECK of the vertex in Gncorresponding to the face describing the object in ¯ Gn. The following property results from Prop. 6.4 and motivates the modification proposed in the rest of this section. Proposition 6.5. If the ECK of the vertex representing the object in the adjacency graph of the homology-generator level, and the edges that survive to be in the boundary of the corresponding face in the boundary graph, are scanning and rotation invariant, we will obtain scanning and rotation invariant cocycles. In the following we will consider the necessary additions to the pyramid building process, to ensure that computed cocycles do not depend on the scanning and rotation of the object. We follow Prop. 6.5 and consider the ECK and the boundary edges of the top level. 23 a) b) Figure 14: a) original image; b) in bold, the paths in the RAG G0associated to the down-projected cocycles. 6.1. Invariant ECK and surviving edges As the edges to be removed in ¯ Gkare ‘locally’ chosen, in a binary image like the ones used to represent our objects, there is no local structure and a random or scanning/orientation dependent direction is taken (Line 4 of Algorithm 1). To ‘add structure’ and create an ordering for selecting edges to be removed and contracted: 1. Compute a spanning tree of the subgraph O⊂G0corresponding to our object in the base level. Mark the edges of ¯ G0corresponding to the edges of the spanning tree to be the removed ones. 2. Create a strict ordering between any two edges. This ordering is used to select surviving edges during simplification, and thus controls the choice of edges in the homology-generator level. The tree. Given the graph Ocorresponding to our object, and a vertex s∈O, we define d(v) : O→Nto be the number of edges of the shortest path connecting vand sin Oi.e. the geodesic distance between the two pixels corresponding to vand s, using the 4 neighborhood. Note that a vertex scan be obtained in a rotation invariant manner for example by using an automatic shape orientation method [16] and then selecting the top, left-most vertex. 24 Stable ECK (in G0). Every vertex v∈G0,v6=s, labels the edge (v, v′)∈G0 with d(v′) = d(v)−1 as ‘to contract’. If vhas more than one neighbor v′ with d(v′) = d(v)−1 the neighbor that minimizes the angle \ SV V ′, and in case of angle equality, the one that has a clockwise orientation of SV V ′is chosen. S,V, and V′are the points in Z2corresponding to the centers of the pixels represented by s,v, and v′. The edges in ¯ G0corresponding to the edges of G0labeled as ‘to contract’, are marked as ‘to remove’. Region boundary simplification (in ¯ Gk). In Line 5.iii) of Algorithm 1, from any chain of edges bounded by at least one vertex of degree 2, one edge will survive and all others will be contracted. To choose to surviving edge, assign to each edge e∈¯ G0bounding a cell of the object, the value f(e) = min{d(v1), d(v2)}where v1,v2are the vertices of G0corresponding to the two faces of ¯ G0to which eis incident to. Faces not part of the object are ignored. When choosing the edge to survive i.e. not contract, the edges are sorted using the following (transitive) relation between any two edges eand e′: •f(e) vs. f(e′); •if f(e) = f(e′) then use the orientation of c(e)S c(e′) vs. the orientation of c(e′)S c(e), where c(e), c(e′)∈R2are the centers of the edges eand e′, and S∈Z2is the center of the pixel used to define the rotation invariant tree; •if c(e)S c(e′) are collinear, the Euclidean distance between c(e) and S vs. the Euclidean distance between c(e′) and S. Homology-generator level. When building the homology-generator level, all edges of ¯ Gn−1bounding the face of the object are sorted based on the criteria above. Edges are selected in inverse order and used to create the spanning tree to be contracted. Edges not bounding the face corresponding to the object are added in random order. Fig. 12 shows an example object and its computed cocycles with and without the rotation invariant pyramid. Fig. 13 and 14 show the paths in the RAG associated to the down-projected cocycles of the test images in [12]. Fig. 15 is another example showing the path in the RAG G0associated to the down-projected cocycle related to the hole associated to the ball. Finally, Fig 16 shows the down-projected cocycles computed on a image from the 2010 World Cup final in South Africa. 25