Reconstructing persistent graph structures from noisy images

Reconstructing persistent graph structures from noisy images Alexey Chernov1, Vitaliy Kurlin2 1Dept Computer Science and Technology, University of Bedfordshire, Luton, LU1 3JU, UK, and Computer Learning Research Centre, RHUL, Egham, Surrey, TW20 0EX, UK. 2Department of Mathematical Sciences, Durham University, Durham DH1 3LE, UK. [email protected], [email protected] Abstract Let a point cloud be a noisy dotted image of a graph on the plane. We present a new fast algorithm for reconstructing the original graph from the given point cloud. Degrees of vertices in the graph are found by methods of persistent topology. Necessary parameters are automatically optimized by machine learning tools. Keywords: graph reconstruction, noisy image, point cloud data, persistent topology 1 The problem of a graph reconstruction We build up on the methods for a graph reconstruction in [1]. Our goal is to reduce the number of arbitrarily chosen or manually adjustable parameters and to avoid any ad hoc preprocessing when there is no metric graph structure on the data. Let us consider a black-and-white dotted image or a collection of black pixels on a white background. We assume that a point cloud Cof black pixels represents a noisy image of a graph Γ⊂R2. Each edge is a polygonal line of straight arcs. We prove that our algorithm reconstructs the graph Γwith a high probability under reasonable restrictions on Γand a point cloud C⊂R2sampled around Γ. 2 Methods of persistent topology Persistent topology is a new branch of computational topology that studies topological features (homology groups) of a filtration (a collection of spaces). Starting from a point cloud C⊂R2, let us define the filtration of graphs {C(�)}as follows. Figure 1: some graphs C(�) for the point cloud Cof 5 points (0,0), (1,0), (2,1), (2,3), (0,5) 19 The vertices of any graph C(�) are all points from the cloud C. For a threshold distance �≥0, if two points p, q ∈Care at distance not more than �, we connect p, q by an edge in the graph C(�). Hence, for any small enough �≥0, the graphs C(�) consist of only isolated vertices at the points of the cloud C, see Fig. 1. However, when �is increasing, we add more edges and eventually C(�)becomes a complete graph where any two vertices are connected by an edge. The resulting filtration {C(�)}characterizes relative positions of points in the original cloud C. Now we can compute topological invariants of C(�)(forexample,thenumber of connected components or the number of independent cycles) and analyze how they change as the parameter �increases. For instance, if the graphs C(�)havetwo connected components over a long range of �, then the original cloud Cis likely to have two clusters. Similarly, counting cycles in C(�)mayrevealthatthepointcloud Clooks like a topological closed loop. See [2] for a much more general discussion. 3 First stage: split points by degree In the first stage of the algorithm, we split a given point cloud Cinto several parts: •collections of edge points, which will form edges of a future reconstructed graph G; •collections of vertex points, which will form vertices (of different degrees) in G. To put each point p∈Cinto one of the collections above, we find a number degC(p)thatresemblesthedegreeofavertexinagraph.Recallthatthedegree of a vertex vin a graph Γis the number of arcs attached to v, see Fig. 2.Pointson edges between vertices of Γcan be considered as trivial vertices of degree 2. Figure 2: finding a degree of a point p, points of potential degree 2 are green, others are red We can not count arcs attached to a point pin a cloud Cand adapt another way of finding degrees. If a sufficiently small neighborhood U(v)⊂Γof a vertex v∈Γ is a ‘star with krays’, then deg v=k. For each point p∈C, we consider all points from the cloud Cwithin the neighborhood Uδ(p)withcenterpand radius δ. The authors of [1] count the number of small clusters of C∩Uδ(p)nearthe boundary of Uδ(p)togetthepotentialdegreedeg C(p). We add the boundary circle to Uδ(p) and count ‘holes’ (independent cycles in the first homology) in the ‘wheel’ C∩¯ Uδ(p), which seems more resilient to the noise than counting small clusters. So we convert the small cloud C∩¯ Uδ(p) into the filtration of 2-dimensional Rips complexes R(�), which are triangulated subsets of the plane. Namely, the vertices of R(�)areallpointsofthesmallcloud. Twoverticesareconnectedbyanedge 20 if the distance between them is not more than �. If any two edges intersect, then we drop one of them. Three vertices span a triangle in R(�) if they are pairwise connected. The number of independent cycles in the small triangulation R(�)can be found fast and equals the number of ‘holes’ whose diameter is more than �. The resulting number degC(p) depends on a radius δand a threshold distance �. We shall later show that under certain conditions on Γand Cthe degree degC(p) remain stable when δand �vary over long enough intervals for many points p∈C. So our algorithm automatically learns the parameters δand �for any point p∈C. 4 Second stage: vertex clusters and edge clusters After finding potential degrees degC(p)forallpointsp∈C, we split Cinto several smaller subclouds Ckby the degree k. Our next aim is to divide the subcloud C2 of all points pwith degC(p)=2intoclustersthatrepresentedgesofthegraphG. We consider the filtration of graphs C2(�), where the vertices are all points p∈C with degC(p) = 2. Two vertices of the graph C2(�)areconnectedbyanedgeifthe distance between them is not more than �. We shall later show that under certain conditions on Gand C, some connected components of C2(�)remainstableovera long interval of �and can represent edges of the underlying graph G. Similarly, for any k�= 2, we split the subcloud Ckof all points p∈Cwith degC(p)=kinto clusters that represent degree kvertices of G. Under certain conditions on a graph Gand a cloud Caround G, every vertex of Ghas a neighborhood where all points from Chave degC(p)=kand form a cluster in the subcloud Ck. In practice, after trying different threshold distances �to form clusters of vertices and clusters of edges, we try to build the corresponding graph where an edge is attached to a vertex if the corresponding clusters have points that are sufficiently close to each other. Then we validate the resulting graph by the following tests: •every edge joins 2 vertices, so every edge cluster is close to 2 vertex clusters; •every cluster of points with degC(p)=k�= 2 has exactly kclose edge clusters. To get the final reconstructed graph G, we put a vertex at the center of mass for each vertex cluster and connect all resulting vertices by straight arcs in the plane. 5 Justification of the algorithm: an outline Input parameters for our algorithm are denoted by Latin letters, e.g. a point cloud C, a number of points n, a fixed point petc. Greek letters denote parameters that the algorithm learns or does not use, e.g. an original graph Γ,anoiselevelτ,a threshold distance δetc. Let d(p, q)betheEuclideandistancebetweenp, q ∈R2. For a cloud C⊂R2, denote the least distance between points p, q ∈Cby dmin(C). Let dcon(C)betheleastdistance�such that the graph C(�)isconnected. The following proposition illustrates the case when an original graph Γis a set of vertices without edges. Namely, if a given point cloud Csplits into subclouds around 21 finitely many unknown centers that are sufficiently away from each other, then the single edge clustering algorithm always correctly identifies the subclouds. Proposition (single edge clustering). For a set ν={ν1,...,νκ}⊂R2, let us take any point cloud C⊂∪ κ i=1Uτ(νi), where Uτ(νi) is the round disk of a radius τat the center νi. If τ<1 4min �dmin(ν) + dmin(C),2dmin(ν)−dcon(C)�, then our clustering algorithm correctly splits the given cloud Cinto κexpected clusters. We analyse connected components of the graph C(�)when�is increasing. In the interval 2τ<�<dmin(ν)−2τ, all graphs C(�)haveexpectedκcomponents. The upper bound on τguarantees that this interval is long enough. A forthcoming extended paper with proofs will be available by April 2013 at the webpage below. 6 Java applet for graph reconstruction www.maths.dur.ac.uk/~dma0vk/java-applets/graph-reconstruction.html The version of the Java applet on 1st March 2013 shows how the algorithm works for random clouds that are uniformly generated around the following graphs: •a ‘star’ graph with one central vertex and a random number of 3-8 rays (spokes), •a ‘wheel’ graph obtained from a star graph by adding the polygonal boundary, •a branched cross whose 4 main rays of random length are along regular bisectors in 4 quadrants, each of these rays has 2 smaller tentacles with random endpoints. The original graph that the algorithm will reconstruct is shown in green. Clicking on the ‘new random cloud’ button generates a blue point cloud around a chosen graph. The button ‘split points by degree’ calls for the first stage of the algorithm computing the potential degree degC(p)ofeachpointpin the generated point cloud C. Degree 1 points are highlighted in blue, degree 2 points are green, degree 3 points are red, degree 4 points are cyan, points of higher degrees are yellow. The button ‘reconstructed graph’ shows the final red graph with the original green graph. The ‘demo’ button demonstrates successive stages with a time delay: a new point cloud, all points colored by degree and a reconstructed graph. The applet starts with a demo mode for a wheel graph with 5 vertices and 8 edges. Acknowledgements The research was supported by the EPSRC grant EP/I030328/1 Persistent topological structures in noisy images. We thank Gunnar Carlsson (Stanford) and Fr´ed´eric Chazal (INRIA Saclay) for fruitful discussions at an ealier stage of our research. References [1] M. Aanjaneya, F. Chazal, D. Chen, M. Glisse, L. J. Guibas, D. Morozov: Metric Graph Reconstruction from Noisy Data, Int J Comp Geometry Appl, v.22 (2012), n. 4, p. 305–325. [2] G. Carlsson: Topology and Data, Bull Amer Math Society, v.46 (2009), n. 2, p. 255–308. 22