Topological Analysis of Simple Segmentation Maps

Topological Analysis of Simple Segmentation Maps Maria-Jose Jimenez(B)and Belen Medrano Universidad de Sevilla, Av. Reina Mercedes s/n, 41012 Seville, Spain {majiro,belenmg}@us.es Abstract. In this paper, we propose a geometry-aware topological analysis of a segmentation of an image into regions which might correspond, for example, to a geographical map or to segmented cells in a microscopic image of a biological packed tissue. The regions must satisfy that the centroid of each one lies inside the region itself. We propose a novel simplicial complex modeling such data, for persistent homology computation, that better respects the geometry of the regions than existing techniques. More specifically, our approach joins benefits from previous models by encoding both neighbouring relations between the regions, as well as spatial distribution of the set of centroids. In addition, we introduce geometric information regarding distances between centroids and boundaries delimiting each region. Keywords: Persistent homology ·Segmentation map ·Shape descriptor of regions ·Topological organization of regions 1 Introduction A segmentation map is a partition of an image into different regions, each one representing an object or a specific area on the image. In this paper, we are inspired by the problem of analysing the organization of cells in a biological packed tissue. The process of segmentation of a microscopic image of a packed tissue into cells is usually based on edge detection that partitions the plane into different regions. A well-founded idea in cellular biology is using Voronoi diagrams built on the set of centroids of cells for estimating their morphology. In [10], the authors evaluated the suitability of approximating the cells by such a mathematical construction. More generally, the approximation of regions on a map by Voronoi regions is a classical problem. In [13], a measure of the error of the approximation was given. There have been several works in the literature [1,2,9,14] analysing the organization of the cells using Topological Data Analysis (TDA) tools. In [9,14], the This research was funded by Ministerio de Ciencia e Innovaci´on - Agencia Estatal de Investigaci´on/10.13039/501100011033, grant PID2019-107339GB-I00 and Agencia Andaluza del Conocimiento, grant PAIDI-2020 P20-01145. Authors listed in alphabetical order. ´E. Baudrier et al. (Eds.): DGMM 2022, LNCS 13493, pp. 123–135, 2022. https://doi.org/10.1007/978-3-031-19897-7_11 124 M.-J. Jimenez and B. Medrano authors used a contact graph representing neighbouring relations between the cells as ground for the analysis. In [1], they used, instead, alpha complexes, which are constructed out of the set of centroids of the regions, to model the inner structure of the cells. By doing this, they were implicitly approximating the regions of the cells by Voronoi regions of their centroids (see Fig. 1). In a more recent work, [2], they use two different approaches: (1) topological analysis of the contact graph constructed from neighbouring regions; (2) topological analysis of the point cloud of centroids of the regions. Once persistent homology is computed out of the generated complexes in each case, different topological features summarising the corresponding outputs can be computed. We are concerned with the design of a simplicial complex that models the regions in a segmentation of the plane, capturing both neighbouring information and spatial distribution of the centroids, while at the same time, saving geometric information related to the shape of the regions. An effective construction will be described over a labelled image representing a segmentation into regions of a subset of the plane Ω=[0,M −1] ×[0,N −1], with some constraints. The paper is organized as follows: in Sect. 2, we introduce some fundamentals of TDA; we define a new simplicial complex associated to a specific type of segmentation into regions of a subset of the plane in Sect. 3; Sect. 4will describe the specific input labelled images to be processed, as well as the algorithm to get the new complex out of them; some application examples will be shown in Sect. 5; finally, some conclusions and future research lines are drawn in Sect. 6. Fig. 1. Image of a cell tissue: cells are delimited in black; centroids of each region are depicted in red; Voronoi region corresponding to the set of centrois in blue. (Color figure online) 2 Tools from TDA In this section, we recall the tools from Topological Data Analysis (TDA) used in this paper. Main theoretical concepts may be consulted in [5]. Simplicial Complex and Filtration. An (abstract) simplicial complex Kis formed by a finite set V(whose elements are called vertices) together with a collection of Topological Analysis of Simple Segmentation Maps 125 subsets of V, called simplices of K, such that for all σ∈Kand for all non-empty σ⊂σ,σ∈K. σ={v0,...,v k}∈Kis called a k-simplex or simplex of dimension k.Each -simplex contained in σwith <kis called a face of σ.Thedimension of a simplicial complex is the maximum of the dimensions of its simplices. Afiltration over a simplicial complex Kis a finite increasing sequence of simplicial complexes K1⊂K 2⊂...⊂K n=K. This way, a partial ordering of all the simplices in a simplicial complex Kproduces a filtration over Kwhenever σ⊂μimplies that the order index of σis less or equal than the one of μ. Sometimes, a filtration is defined using a monotonic function f:K→Rsuch that, for any two simplices σ, μ ∈K,ifσis a face of μ, then f(σ)≤f(μ). That way, if a1≤... ≤anare the function values of all the simplices in K, then the subcomplexes Ki=f−1(−∞,a i], for i=1...n define a filtration over K. Clique Complex. Given an undirected graph Gwith set of vertives V, the clique complex X(G) is an abstract simplicial complex formed by the sets of vertices in the cliques (complete subgraphs) of G. This way, each clique of kvertices of Gcorresponds to a simplex of dimension k−1ofX(G). Vietoris-Rips Complex. Given a metric space (X, d), the Vietoris-Rips complex for Xassociated to a parameter ∈(0,+∞), VR(X, d, ), is the simplicial complex with vertex set Xand k-simplices spanned by {x0,...,x k}whenever d(xi,x j)≤for all 0 ≤i, j ≤k. Then, the Vietoris-Rips filtration is defined by increasing the filter value . Alpha Complex. Given a finite collection Fof sets, the nerve of F[5], consists of all non-empty subcollections whose sets have a non-empty common intersection, that is, Nrv F={X⊆F:X=∅}. Notice that Nrv Fis always an abstract simplicial complex. The Nerve Theorem [3] states that if Fis a finite collection of closed, convex sets in Euclidean space, then Nrv Fhas the same homotopy type than F. Such a theoretical result provides the ground for the construction of the alpha complex (see [5]). AVoronoi diagram is a partitioning of the plane depending on a set of vertices V={v1,...,v n}: for each vertex vi, the Voronoi region Viassociated to viis given by Vi={x|d(vi,x)≤d(vj,x),∀j=1,···n, j =i}. That is, each region Viis formed by points of the plane for which that vertex is the closest point (see the first row of images in Fig. 3). 126 M.-J. Jimenez and B. Medrano Fixed a value α, consider Bi αas the ball of center viand radius αand consider the region Ui α=Bi α∩V i.Analpha complex Kαis a simplicial complex such that a k-simplex {v0...v k}belongs to Kαwhen the intersection of the regions Ui α=Bi α∩V i,∀i=0,···k, is not empty. If the vertices are in general position in the plane, no k-simplex will arise with kgreater than 2 and the final simplicial complex is known as the Delaunay triangulation [5, p. 63]. See Fig. 3, first row. Varying α, the simplicial complexes Kαinduce a filtration over the Delaunay triangulation called alpha filtration. Persistent Homology and Barcodes. The concept of homology class, from algebraic topology, defines n-dimensional holes rigorously and computes them using linear algebra (see [8] for rigorous definitions). Intuitively, 0-dimensional holes are connected components, 1-dimensional holes are tunnels and 2-dimensional holes are cavities. Persistent homology [6,15] is the main tool in TDA defined for tracking the persistence or the lifetime (encoding birth and death moments) of holes along a filtration. For example, in the case of an alpha complex constructed from a point cloud on the plane, 0-dimensional and 1-dimensional persistent homology describe, respectively, the evolution of connected components and holes of the collection of regions (intersection of Voronoi diagrams and balls) as the balls radii increase. The persistence of each n-dimensional hole can be represented using an interval of the form [b, d], where bis the birth time, that is, the index for which Kbis the simplicial complex (in the filtration) where the hole first appears, and dis the death time, if Kdis the first simplicial complex (in the filtration) where the hole disappears. If the hole remains until the final simplicial complex, we write d=∞. This codification in terms of intervals (or bars) [b, d] is called the n-dimensional persistence barcode,n-barcode for short, (see Fig. 2). A formal definition of homology and persistent homology together with algorithms for computing it can be found in [5]. Fig. 2. Left: example of a filtration over a complex K=K4. Rigth: 0 and 1-barcodes representing connected components and holes (in red and blue, respectively). (Color figure online) Notice that small perturbations on the boundary between regions would lead to small perturbations on the positions of the centroids and the stability results for persistent homology (see [4]) would imply small changes in the barcodes. Topological Analysis of Simple Segmentation Maps 127 Fig. 3. An example of simplicial complexes (in red) associated to a partition into regions, each one, from left to right, corresponding to a higher value of the radius α. Top row: alpha complexes (forgetting the real boundaries of the regions). Bottom row: complexes associated to the regions. (Color figure online) 3 Simple Segmentation Complex We set the definition of simple segmentation map on the plane and a filtration that is inspired by the one of alpha complex. However, in this case, we cannot guarantee that the Nerve Theorem is satisfied, so we have to prove that the filtration is correctly built. Definition 1. Consider Ω=[0,N −1] ×[0,M −1] ⊂R2. We say that R= {Rj}j=1,···nis a simple segmentation map of Ωif Ω=j=1,···nRjsuch that: –eachregionRjis homeomorphic to a disk, delimited by a boundary curve, which is a Jordan curve, whose points are considered to be part of that region as well; – the centroids {c1,...,c n}lie inside each region; – two regions have either empty intersection or they share a set of curve segments on the boundary of both regions (and we say then that they are neighbour regions). Notice that the regions may not be convex and that the intersection between two regions may be formed by several disjoint curve segments. Filtration Associated to a Simple Segmentation Map. We define now a filtered simplicial complex associated to a simple segmentation map R. Definition 2. Given a simple segmentation map, R, whose set of centroids is {c1,...,c n}, consider Bα(ci)as the ball of center ciand radius α.Foreachα, consider the region UR α(ci)=Bα(ci)∩Riand define the simplicial complex KR α with simplices {c1...c k}∈K R αwhen  i=1...k UR α(ci)=∅. 128 M.-J. Jimenez and B. Medrano In other words, a simplex lies in KR αwhen the intersection of balls with radius α and centers its vertices with their corresponding regions (of which those vertices are centroids) is not empty (see Fig. 3, bottom row). Given a simple segmentation map R,thecontact graph of Ris a graph whose vertices are the centroids of the regions of Rand whose edges represent neighbouring relations between regions. No multiple edges are allowed, even if the intersection of two regions are two (or more) disjoint curve segments. Proposition 1. Given a simple segmentation map, R,{KR α}αis a filtration over the simplicial complex generated as the clique complex of the contact graph of the regions. Proof. In order to prove that the filtration is well constructed, we only must check that the minimum value αfor which a simplex σbelongs to KR αis always greater than the minimum value βfor which any of its proper faces μbelongs to KR β. Notice first, that all the vertices of the complex (the centroids) lie in KR 0. Assume that σis a 2-simplex (associated to three regions R1,R 2,R 3)andμa 1-simplex. Then αis the maximum distance from the three centroids c1,c 2,c 3to their intersection point P123.Ifμrepresents, the neighbouring relation between R1and R2, then βis the minimum of the maxima values of the pairs of distances of each point of the boundary curve to both centroids c1and c2. Then, if α≤β, since α>d(c1,P 123)andα>d(c2,P 123), that would mean that β>d(c1,P 123) and β>d(c2,P 123), what is a contradiction (since P123 also belongs to the boundary curve between R1and R2). Since all the neighbouring relations of more than 3 regions also occur due to one intersection point and the value of the filter is given by the maximum distance to each centroid, then the statement is true in all the cases.  4 Labelled Images Representing Simple Segmentation Maps and Associated Simplicial Complex In order to put into practice the model that we propose, we constrain to the setting of labelled images representing a simple segmentation map. In this section we introduce first, the input images that we are going to process and later, we set the algorithm that produces the filtered complex that will be the object of study. For basic concepts of digital topology, see [12]. By labelled image we refer to a digital image L:D→{0,1,2,...,m}, where D= ([0,M −1] ×[0,N −1]) ∩Z2, for given Mand N, and the labels i∈ {0,1,2,...,m}, have a specific meaning, such as the result of a segmentation process. Our input images are labelled images, as in Fig. 4representing regions that are bounded by boundary pixels. Notice that the regions “touching” first/last row/column might correspond to regions that are not fully represented, so we will consider them as non-valid regions. We are interested in computing a simplicial complex representing the structure of valid regions. Topological Analysis of Simple Segmentation Maps 129 Fig. 4. Left: a labelled image. Each label has been assigned a gray level. Boundary pixels have been drawn in white. Right: a portion of the labelled image containing, partially, three different regions. Color is used only for visualization purposes. (Color figure online) We will assume that each region is bounded by a 4−connected curve with no simple point [11]. Recall that a 4–connected curve is a closed path of pixels that are 4−adjacent; a pixel is a simple point if the change of its value does not change the topology of the image, that is, removing it from the boundary curve (by changing its value to the label of the neighbour region), the boundary is still a 4-connected curve. Hence, the deletion of a simple point of a 4–connected curve still produces a 4–connected curve bounding the same region. If the set of boundary pixels has simple points, then, a morphological thinning can be accomplished to remove them (see, for example, [7], Ch. 9, p.660). We assume that the regions are big enough so that their boundary pixels do not disconnect them (there is no Jordan paradox). Sometimes, a segmentation process provides a labelled image that partitions the image in 4-connected regions with no holes, whose centroids lie inside each region, but with no boundary pixels. Then, the set of boundary pixels could be defined by: 1) taking those pixels having a 4-adjacent pixel with a different label; 2) thinning that set of pixels, so that it has no simple points for 4–connectivity. We put all the constraints together to define our simplesegmentation image. Definition 3. Let L: ([0,M −1] ×[0,N −1]) ∩Z2→{0,1,2,...,m}be an M×Nlabelled image. We will say that Lis a simple segmentation image if it is a union of sets of 4-connected pixels with the same label such that: –labels{1,2,...,m}are assigned, each one, to a 4–connected component with no holes, whose centroid lies inside the region; – label 0 is assigned to a 4–connected component of pixels with no simple points, called boundary pixels, with as many holes as regions with labels from 1 to mand such that each region is bounded by a 4−connected curve of boundary pixels. 130 M.-J. Jimenez and B. Medrano Taking into account that the boundary pixels delimiting each region are formed by 4–connected paths, it is easy to check that in the intersection of exactly 3 regions (and not 4), there will be only one pixel whose 3 ×3 neighbourhood contains pixels from the 3 regions, as in Fig. 4. In the case of 4 incident regions, two cases may arise: (1) a 3 ×3 cross, where there would be 4 incident regions (Fig. 5, left); (2) the configuration in Fig. 5, right, with 4 incident regions too. Fig. 5. Left: A 3 ×3 cross configuration of boundary pixels (in grey) delimiting 4 different regions. Right: Configuration of pixels on the boundary (grey) containing a 2×2 block of boundary pixels. Pixels with a cross can lie either on the boundary or not. (Color figure online) Lemma 1. If there is a configuration of 2×2pixels on the boundary, then, the 4×4neighbourhood around those 2×2pixels, will have the configuration of pixels given in Fig. 5, on the right, and, hence, will contain 4 incident regions. Proof. A thorough check of all cases shows that, first, any other configuration in the 4 ×4 neighbourhood would contain a simple point in the set of boundary pixels and also that if there were three (or fewer) incident regions, then, there would be a simple point.  See Fig. 5. The 3 ×3 neighbourhood of each pixel in the 2 ×2 configuration will contain pixels with labels of, at most, two different regions. Thus, the 4 incident regions will be adjacent two by two. However, in this case, it seems natural to consider that the four regions appearing in the 4 ×4 neighbourhood, should be mutually adjacent. That way, we provide the following definition for adjacency of regions (or neighbour regions): Definition 4. Let Lbe a simple segmentation image. Then, we will say that two regions with labels 1and 2,areneighbour regions if either there is a 3×3 neighbourhood centered on a boundary pixel that contains pixels with labels 1 and 2or there is a 2×2configuration of boundary pixels such that the 4×4 neighbourhood centered on it contains pixels with labels 1and 2. Simplicial Complex Associated to a Simple Segmentation Image. We will use the concept of neighbour regions defined above to construct a simplicial complex out of the input labelled image, together with a filtration. Hence, each region is represented by its centroid (as a vertex), pairs of adjacent regions will produce Topological Analysis of Simple Segmentation Maps 131 Fig. 6. Illustration of Algorithm 1:{cmi}i=21,22,25 are centroids of regions of labels i=21,22,25 and {pi}i=1,...,4sample boundary pixels. All the pixels {pi}belong to the boundary between regions with labels 21 and 22. Their distances to the corresponding centroids are: d(p1,cm 21)=31.18 and d(p1,cm 22)=18.39; d(p2,cm 21)=25.29 and d(p2,cm 22)=17.87; d(p3,cm 21)=29.19 and d(p3,cm 22)=14.15; d(p4,cm 21)=30.67 and d(p4,cm 22)=14.28. Then, the filter value for the edge {21,22}is 25.29, whenever there is no other pixel on the boundary whose greater distance to one of both centroids is lower than that amount. Finally, the pixel p4lies on the boundary of regions 21, 22 and 25 and d(p4,cm 25)=24.01, so the triangle {21,22,25}is assigned filter value 30.67. edges between them, triples of neighbour regions, triangles and configurations of Fig. 5will lead to tetrahedra in the simplicial complex. For that aim, we follow the steps in Algorithm 1to build a complex as well as a filtration (stored in F): roughly, run over all the boundary pixels and consider the centroids of labels arising in the 3 ×3 neighbourhood E3(i, j) of each boundary pixel (i, j). When there are two labels, consider the pair of distances to both centroids and take the minimum between the greater distance of each pair of distances; when there are 3 or 4 labels, simply take the maximum distance for the filter value. See Fig. 6 for an illustration of the process. The 4×4 neighbourhood E4(i, j) is considered only in exceptional cases of configuration as in Fig. 5right. Proposition 2. The list Fof Algorithm 1produces a filtration over the simplicial complex representing all the neighbouring relations as in Definition 4. Proof. The proof follows the same argument as in Proposition 1. Notice that now, the maximum number of incident regions is 4 by construction. 5 Discussion Our method can be considered as an improvement of the alpha complex in the case where the points in a point cloud on the plane have an associated region to which the increasing balls have to be restricted. In Fig. 7, top row, we can see that the 1-simplices of the simple segmentation complex coincides with the contact graph, while in the case of the alpha complex