PA170 Digital Geometry Lecture 05: Adjacency Graphs Martin Maˇska (xmaska@fi.muni.cz) Centre for Biomedical Image Analysis Faculty of Informatics, Masaryk University, Brno Autumn 2023 Boundaries, Borders, and Holes Informally What is a boundary, border, and hole of a set? 2/22 Boundaries, Borders, and Holes Informally What is a boundary, border, and hole of a set? Boundary lies “between” two sets and separates them from each other Border is a part of a set that lies near its boundary Hole is a component “inside” a set (a finite complementary component) Boundary Boundary Border Border Hole 3/22 Adjacency Structures as Adjacency Graphs Let S be a countable set and A be an adjacency relation on S. [S, A] is called an adjacency structure An adjacency structure [S, A] can be represented using an adjacency graph (its nodes correspond to the elements of S and its edges are given by A) Nodes of adjacency graphs do not have assigned locations in a Euclidean space 8-adjacency grid Voronoi tesselation Delaunay triangulation 4/22 Adjacency Sets Let [S, A] be an adjacency graph. The set A(M) of all nodes adjacent to M ⊆ S (i.e., the set of all p ∈ M such that A(p) ∩ M = ∅) is called the adjacency set of M Set M in a 4-adjacency graph 4-adjacency set of M 5/22 Region Adjacency Graphs If [S, A] is an adjacency graph, two disjoint subsets M1 and M2 of S are called adjacent (M1AM2 or (M1, M2) ∈ A) iff A(M1) ∩ M2 = ∅ A region adjacency relation A is irreflexive and symmetric Let R be a partition of S into connected components and (possibly) the infinite background component. The undirected graph [R, A] is called the region adjacency graph of R (8, 4)-adjacency graph and the corresponding region adjacency graph 6/22 Types of Nodes and Borders Let [S, A] be an adjacency graph and M ⊆ S be a subset of its nodes p ∈ M is called an interior node of M iff A(p) ⊆ M; otherwise it is called a border node of M The set M of all inner nodes of M is called the inner set of M The set δM of all border nodes of M is called the border (inner border) of M A border node of S \ M is sometimes called a coborder (outer border) node of M Set M Its inner 4-border Its outer 4-border 7/22 Invalid Edges and Boundary Let [S, A] be an adjacency graph and M ⊂ S be a proper subset of S An edge {p, q} of [S, A] is called M-invalid iff p ∈ M and q ∈ (S \ M) The boundary of M is the set of all M-invalid edges Set M in a 4-adjacency graph Boundary of M 8/22 Boundary Detection Detection of boundaries in 2D (3D) binary images is often performed using the Marching Squares (Cubes) algorithm It scans the input binary image in successive blocks of image elements and evaluates their configurations of foreground and background values assigned Foreground boundary Foreground boundary for (4, 8)-adjacency for (8, 4)-adjacency 9/22 Oriented Adjacency Graphs Let [S, A] be an adjacency graph. A local circular order ξ(p) at a node p ∈ S is an ordered sequence q1, . . . , qn of all nodes in A(p) without repetitions An oriented adjacency graph [S, A, ξ] is defined by an adjacency graph [S, A] and an orientation ξ, defined by local circular orders of the adjacency sets These local orders can be used to trace edges in [S, A, ξ] as follows: if we arrive at p from qi ∈ A(p), we move next to qk , where k = (i + 1) mod n 10/22 Oriented Adjacency Subgraphs A subset M ⊆ S induces a substructure [M, AM, ξM] of an oriented adjacency graph [S, A, ξ] where AM contains only those adjacency pairs {p, q} such that p, q ∈ M and {p, q} ∈ A, and where, for any p ∈ M, ξM(p) is the reduced local circular order defined by deleting all nodes that are not in M from ξ(p) The cycles of [M, AM, ξM] may differ from cycles of [S, A, ξ] 11/22 Oriented Adjacency Subgraphs A subset M ⊆ S induces a substructure [M, AM, ξM] of an oriented adjacency graph [S, A, ξ] where AM contains only those adjacency pairs {p, q} such that p, q ∈ M and {p, q} ∈ A, and where, for any p ∈ M, ξM(p) is the reduced local circular order defined by deleting all nodes that are not in M from ξ(p) The cycles of [M, AM, ξM] may differ from cycles of [S, A, ξ] 12/22 Atomic and Border Cycles Let (p, q) be a directed edge in [M, AM, ξM], ρ1 be the cycle generated by (p, q) in [M, AM, ξM], and ρ2 be the cycle generated by (p, q) in [M, A, ξ]. ρ1 is an atomic cycle of [M, AM, ξM] iff ρ1 = ρ2 and a border cycle of [M, AM, ξM] otherwise For any M ⊂ S, [M, AM, ξM] has at least one border cycle Each border cycle of [M, AM, ξM] contains at least one border node of M, and each border node is incident with at least one border cycle 13/22 Inner and Outer Border Cycles A border cycle of [M, AM, ξM] is called outer iff it separates M from the infinite complementary component All other border cycles of [M, AM, ξM] are called inner border cycles 14/22 Holes Let [S, A, ξ] be an infinite oriented adjacency graph and M be a finite connected subset of S with exactly one infinite complementary component Any finite complementary component of M is called a hole of M A (finite) complementary component of M assigned to an inner border cycle is called a proper hole of M A finite complementary component assigned to an outer border cycle of M is called an improper hole of M 15/22 Directed Invalid Edges Let [S, A, ξ] be an oriented adjacency graph and M ⊆ S be a subset of its nodes. A directed edge (r, q) from a coborder node r ∈ (S \ M) to a boder node q ∈ δM is called invalid Every directed invalid edge points to exactly one border cycle in [M, AM, ξM] 16/22 Border Tracing Algorithm: Main Idea Let [S, A, ξ] be an oriented adjacency graph and M ⊂ S be a finite proper subset of S Each component C of M is handled independently: Generate a list of all directed invalid edges for C Trace the border cycle to which one of these edges points to (and delete the already processed invalid edges) If there is still an undeleted directed invalid edge, repeat the tracing process 17/22 Border Tracing Algorithm: Main Idea Let [S, A, ξ] be an oriented adjacency graph and M ⊂ S be a finite proper subset of S Each component C of M is handled independently: Generate a list of all directed invalid edges for C Trace the border cycle to which one of these edges points to (and delete the already processed invalid edges) If there is still an undeleted directed invalid edge, repeat the tracing process 18/22 Border Tracing Algorithm: Main Idea Let [S, A, ξ] be an oriented adjacency graph and M ⊂ S be a finite proper subset of S Each component C of M is handled independently: Generate a list of all directed invalid edges for C Trace the border cycle to which one of these edges points to (and delete the already processed invalid edges) If there is still an undeleted directed invalid edge, repeat the tracing process 19/22 Border Tracing Algorithm: Directed Invalid Edge (q, p) 1 Let (q0, p0) := (q, p), i := 0, and k := 0 2 Let ξ(pi) = . . . , qk , q, . . . be the local circular order at pi. If q ∈ C, go to Step 4 3 Node q is another node on the border cycle. Let i := i + 1 and pi := q. Let ξ(pi) = . . . , pi−1, q, . . . be the local circular order at pi. If q ∈ C, go to Step 3; Otherwise, let k := i − 1, and go to Step 4 4 If (q, pi) = (q0, p0), go to Step 5. Otherwise, let k := k + 1 and qk := q, and go to Step 2 5 We are back at the original directed invalid edge (q, p). The border cycle of the component C is p0, p1, . . . , pi 20/22 Boundaries, Borders, and Holes Formally What is a boundary, border, and hole of a set M? 21/22 Boundaries, Borders, and Holes Formally What is a boundary, border, and hole of a set M? The boundary of M is the set of all M-invalid edges of the corresponding adjacency graph The border δM of M is the set of all border nodes of the corresponding adjacency graph Proper and improper holes of M are finite complementary components of M assigned to the border cycles of the corresponding oriented adjacency graph 22/22