Algorithm to Compute a Minimal Length Basis of Representative Cocycles of Cohomology Generators

Algorithm to Compute a Minimal Length Basis of Representative Cocycles of Cohomology Generators Mabel Iglesias-Ham1,2, Edel Garc´ıa-Reyes1, Walter G. Kropatsch2and Roc´ıo Gonzalez-D´ıaz3 1CENATAV, Pattern Recognition Department, Havana, Cuba. 2Vienna University of Technology, Pattern Recognition and Image Processing Group, Austria. 3University of Seville, Applied Math Department, Spain. {miglesias,egarcia}@cenatav.co.cu,{krw,mabel}@prip.tuwien.ac.at,[email protected] Abstract An algorithm to compute a minimal length basis of representative cocycles of cohomology generators for 2D images is proposed. We based the computations on combinatorial pyramids foreseeing its future extension to 3D objects. In our research we are looking for a more refined topological description of deformable 2D and 3D shapes, than they are the often used Betti numbers. We define contractions on the object edges toward the inner of the object until the boundaries touch each other, building an irregular pyramid with this purpose. We show the possible use of the algorithm seeking the minimal cocycles that connect the convex deficiencies on a human silhouette. We used minimality in the number of cocycle edges in the basis, which is a robust description to rotations and noise. Keyworks cohomology; combinatorial pyramids; representative cocycles of cohomology generators. 1 Introduction The use of topological invariants is a promising alternative in order to describe deformable shapes in 2D and 3D [16]. This has motivated a lot of research to obtain efficient algorithms on different topological object decompositions (simplicial complexes [3, 4], cubical complexes [12], irregular pyramids [15, 10], and others [8, 1]). However, most of the algorithms are looking for generators of homological groups in order to characterize the object by the number of connected components and holes (1-dimensional holes). Pursuing a more refined description it is possible to use shape features on the holes. But, usually the boundaries of the holes are seriously affected by noise in real world applications of image processing and object modeling [17]. The final goal of our research, is to find a new descriptor that improves the lower robustness of the present object topological descriptions. Taking into account the dual relationship between the homology and cohomology [6], we intend to show that a refined description based on the minimal length basis of cocycle is more robust to noise and can be used to evaluate the similarity between objects in 2D and 3D. The representative cocycles that were computed in an irregular graph pyramid before [5], associated to a path in the Region Adjacency Graph (RAG) going from one hole boundary to the outside boundary, can now be computed with minimal length. In this way, it can be used as an stable feature to noise in the hole boundary and to rotations. Also, the associated path in the RAG will now be following straight lines as long as possible, and will be described with the minimum number of edges needed. The minimum basis of representative cocycles of cohomology generators are the minimum number of edges associated with paths in the RAG, connecting all the holes boundaries and the outside boundary. If we consider the hole boundaries and the outside boundary as nodes, and the 121 paths in the RAG as edges connecting those nodes, then the minimal length basis of representative cocycles can be seen as a minimal spanning tree. We selected as the underline representation combinatorial pyramids due to 2D combinatorial maps are easily extendable to 3D, where the proposed algorithm could be adapted. The minimal length cocycle basis can be used as a descriptor of how strong is a shape, with applications to medicine in measuring strength of bone structures. In Section 2 a recall about combinatorial pyramids is given. In Section 3 the new algorithm for computing the minimal length basis of representative cocycles is presented. Then, in Section 4 we show experimental results followed by conclusions and future work in Section 5. 2 Recall: Combinatorial Pyramids A Combinatorial Pyramid is an Irregular Graph Pyramid where each level in represented by a Combinatorial Map. The Combinatorial Maps are encoding the topology of the original data. Every level represents a reduced representation of the level below, and in general of the base level representing the data in detail. On top level is the minimal topologically equivalent representation of the initial data. A 2D combinatorial map is defined by a triplet M = (D,β1,β2) where D is a set of darts and β1 and β2are two permutations. The intuitive way of understanding this representation is starting with a graph, we split each edge in two darts and the set of all the darts is named D. Then, β1 works as a connection between the two darts that belongs to the same initial edge. If we have and edge dthat was split in darts d1and d2, then β1(d1)=d2and β1(d2)=d1. (See Fig. 1) Figure 1: Example of a fragment of a combinatorial map. The darts obtained from the edges around the center vertex are labeled for demonstration. The second permutation β2encodes the order of darts around a vertex clockwise. In the example of the figure for the center vertex the result of applying the second permutation is shown in the table 2. Figure 2: Table shows the result of applying the β2permutation over the darts around the central vertex in Fig. 1 We can obtain all the darts around a face in counter-clockwise order applying alternatively the two operations as shown in the Fig. 3. A vertex in a level lof a pyramid represents a set of vertices in the base level (receptive field). This set of vertices have been contracted or joint to a single one by successively applying contractions of neighboring similar vertices on every intermediate level 122 up to l. After joining or contracting a pair of vertices, the edge in between disappears. In general after applying the set of contractions in one level a number of edges disappear. The rest of the edges encodes the topology of the represented data but with possible redundancies. The operation of eliminating the redundant edges is called simplification. At this point, the remaining edges survives to the next level and are called bridges. Bridges produces a new edge in the next level, connecting surviving nodes product of the contraction of its end points. The interested reader can find more detailed properties and definitions in [11, 13, 2]. Figure 3: Alternative applying the two permutations leads to a traversal of all the darts around a face. We call the infinite face to the one that gives all the darts in the outside of the image, which are bounding the infinite or unknown face. Finally, there is some previous work showing the pyramid can be constructed with log(m) height in the number of vertices in the base level. (See [14, 7]). 3 Algorithm to Compute a Minimal Basis for Cohomology Starting from a white and black image, we first build a combinatorial map which is initialized in the faces with the color of the respective pixel plus a label identifying the boundary it is adjacent to. In the case of inside faces, the label is initialized in zero (See Fig. 4). In the figure (b), black pixels represent inside faces, and the rest of the foreground pixels (no white pixels), are identified with different colors depending of its adjacent boundaries. a) b) Figure 4: Labeling of faces next to boundaries in the initialization step: a) original image b) image with boundary labels. In principle, the edges that are allowed to be contracted are edges from the foreground region only, reducing the number of computations. The aim of the method is to expand boundary labels until they meet its closest boundary (a cocycle is found) taking into account the moment where a cocycle basis is obtained (all boundaries are connected with a spanning tree of paths in the RAG). 123 Here, similar adjacent vertices1are the ones that apply to two properties depending on its labels: 1. Only edges between faces with different labels can be removed, i.e. neighboring vertices with different labels can be contracted. 2. Different labels that are already connected by a cocycle are not considered different anymore, i.e. neighboring vertices with different labels that are already connected by a cocycle can not be contracted anymore2. In this way, the notion of similar vertices is determined by the values of its labels. We only consider the gray value of the input image (binary) to identify the foreground region. After the initial labeling of the foreground region, the decision of what are considered neighboring similar vertices to be contracted is determined by the conditions described above. Following those rules, the contractions will be describing expansions of the boundary labels, until they meet in the closest ones. As a result, the cocycle basis will be made of cocycles with minimum length. When two faces are contracted, the surviving face will keep the label of the expanded boundary label or an arbitrary one from the child faces in case of a boundary meeting (cocycle found). Removals of degree two vertexes are not allowed here, as they are representing different possible ways of extending the actual paths for the cocycles. In order to keep track of the future cocycle, every face will save the index of the exit edge for the path that arrives to it. In the case of a face representing a pixel next to a boundary, its exit edge will be the one that separates the face with the background. After a contraction, the new face labeled (boundary label expansion) will be saving the exit edge as the contracted one. Then, when a cocycle is found we save as a cocycle the meeting edge and the traced exit edges starting from both meeting faces. 4 Experiments In this section we show some examples of minimal cocycle basis obtained from test images and a human silhouette. In figure 5 we show the base level combinatorial map from a sample image. Edges in red show the ones belonging to the cocycle basis with minimal length computed. Figure 5: In red the edges belonging to the minimal length cocycle basis of cohomology is shown. In figure 6 we show the result for an image and its rotated version. Notice that even though the edges that belong to the cocycle basis changes, the length in the number of edges of the result remains the same. 1vertices representing a pixel or face, in order to keep the same notation of the figures. 2They are considered the same label from this moment on. 124 a) b) c) d) Figure 6: Minimal cocycle basis for image in a) and its rotated version c) are shown in b) and d) respectively. Different colors (red and blue) identifies different cocycles. Finally, in figure 7 we show an example of a minimal basis of cocycles computed on a human silhouette. In this case, as the human silhouette does not contain many holes, we consider a preprocessing step where its convex deficiencies will be the new holes [9]. For doing that, all points outside the convex hull of the human silhouette, and inbetween the top and the bottom of the silhouette height, will become foreground (see Fig. 7 b)). In this way, the computed cocycles with go inside of the original human shape connecting the convex deficiencies through its closest points (see Fig. 7 c)). 5 Conclusions In this paper we presented an algorithm to obtain the minimal length basis of representative cocycles on a combinatorial pyramid from 2D images. We show the use of the algorithm seeking the minimal cocycles that connects the convex deficiencies of the human silhouette. The new feature is robust to noise and rotations of the object, and could have applications in areas like medicine to measure strength of shapes like bones. In future works we will try its extensions to 3D objects taking advantage of the underline object representation based on combinatorial maps. Finally, we plan to include demonstrations that proves the edges associated to paths in the RAG connecting all the boundaries are in fact a basis for Cohomology. References [1] M. Allilli, D. Corriveau, and D. Ziou. Morse homology descriptor for shape characterization. In 17th International Conference on Pattern Recognition, pages 27–30, 2004. 125 a) b) c) Figure 7: Minimal length cocycle basis computed for a human silhouette with its convex deficiencies as holes. [2] Luc Brun and Walter G. Kropatsch. Construction of combinatorial pyramids. In GbRPR’03: Proceedings of the 4th IAPR international conference on Graph based representations in pattern recognition, pages 1–12, Berlin, Heidelberg, 2003. Springer-Verlag. [3] Delfinado and Edelsbrunner. An incremental algorithm for betti numbers of simplicial complexes on the 3-sphere. CAGD, 1995. [4] J. G. Dumas, F. Heckendach, B. D. Saunders, and V. Welker. Computing simplicial homology based on efficient smith normal form algorithm. Algebra, Geometry and Software Systems, pages 177–206, 2003. [5] Rocio Gonzalez-Diaz, Adrian Ion, Mabel Iglesias-Ham, and Walter G. Kropatsch. Irregular graph pyramids and representative cocycles of cohomology generators. In Andrea Torsello, Francisco Escolano, and Luc Brun, editors, Proceedings of the 7th IAPR-TC15 International Workshop on Graph-based Representations in Pattern Recognition, volume 5534 of LNCS, pages 263–272, Venice, Italy, May 2009. Springer. [6] Rocio Gonzalez-Diaz and Pedro Real. On the cohomology of 3d digital images. Discrete Applied Mathematics, 147(2-3):245–263, 2005. [7] Yll Haxhimusa, Roland Glantz, Maamar Saib, Georg Langs, and Walter G. Kropatsch. Logarithmic tapering graph pyramid, 2002. [8] M. Hilaga, Y. Shinagawa, T. Kohmura, and T. L. Kunii. Topological matching for fully automatic similarity estimation of 3d shapes. In SIGGRAPH01, pages 203–212, 2001. [9] Kropatsch W. G. Gonzalez R. Iglesias, M. and A. Ion. Object classification by topology of convex deficiencies. Workshop on Computational Topology in Image Context, 2009. [10] Mabel Iglesias-Ham, Adrian Ion, Walter G. Kropatsch, and Edel B. Garc´ıa. Delineating homology generators in graph pyramids. In 13th Iberoamerican Congress on Pattern Recognition (CIARP 2008), volume 5197 of LNCS, pages 576–584. Springer, 2008. [11] Thomas Illetschko. Minimal combinatorial maps for analyzing 3d data. Technical Report PRIP-TR-110, Vienna University of Technology, Inst. of Computer Aided Automation, Pattern Recognition and Image Processing Group, 2006. 126 [12] T. Kaczynsky, K. Mischaikow, and M. Mrozek. Computational Homology. Springer, 2004. [13] W. G. Kropatsch. Building irregular pyramids by dual graph contraction. IEE-Proc. Vision, Image and Signal Processing, 142, 6, 366-374 (1995). [14] Walter G. Kropatsch, Yll Haxhimusa, Zygmunt Pizlo, and George Langs. Vision pyramids that do not grow too high. Pattern Recogn. Lett., 26(3):319–337, 2005. [15] Samuel Peltier, Adrian Ion, Walter G. Kropatsch, Guillaume Damiand, and Yll Haxhimusa. Directly computing the generators of image homology using graph pyramids. Image and Vision Computing, 27(7):846–853, 2009. [16] Stina Svensson, Carlo Arcelli, and Gabriella Sanniti di Baja. Characterising 3D objects by shape and topology. In Discrete Geometry for Computer Imagery, volume LNCS 2886, pages 124–133. Springer-Verlag, 2003. [17] A. J. Zomorodian. Topology for Computing. Cambridge University Press, 2005. 127 128