5.1.1 Adjacency and completeness; incidence pseudographs

Let G =[S,I, dim] be an incidence structure. c ∈ S is called an i-node if dim(c) = i. The maximum value of dim(c) for any c ∈ S is called the index dimension ind(G) of G.¹ If ind (G)= n, G is called an n-incidence structure. Any node of G that has dimension ind(G) is called a principal node, and any node that has smaller dimension is called a marginal node.

For example, 2D and 3D incidence grids define incidence structures and of index dimensions 2 and 3, respectively, in which pixels and voxels are the principal nodes. We generalize the adjacency definitions given for incidence grids in Section 2.2.1. Let I(c) = {c′ : c′ ∈ S Λ c′Ic}.

A relation A_i of i-adjacency between nodes of an incidence structure defines an adjacency structure G_i = [S, A_i], which is an adjacency graph if properties A1 through A3 are satisfied. All of the definitions and results regarding adjacency graphs in Chapter 4 apply to these G_is. For example (see Definition 4.1), two nodes c, c′ ∈ S are i-connected with respect to M ⊆ S iff there is an i-path (c₁, c₂,…, c_k) in [S, I, dim] where c = c₁, c′ = c_k, and the nodes of the path are either all in M or all in This allows us to define i-components of M.

Figure 5.1 (middle or right) shows (on the upper left) that, unlike the situation for adjacency grids, i-adjacency of two nodes does not necessarily imply h-adjacency for h <i.

This (symmetric and irreflexive) adjacency relation defines paths of nodes of equal dimension j > 0, and the reflexive and transitive closure of this relation defines connectedness and components for such nodes. Components of an incidence structure will be defined in the next section; these components need not contain only nodes of a single dimension.

Our main interest is in principal nodes. Let G =[S, I, dim] be an n-incidence structure. The set of n-nodes of G is called the core of G. G is called an incidence pseudograph iff it has the following properties:

Finally, we generalize Definition 2.5 (completeness) from incidence grids to arbitrary incidence pseudographs. Let G =[S, I, dim] be an incidence pseudograph, and let M ⊆ S. We define the completion M + of M with respect to G as the smallest subset of S that has the following properties:

Property (ii) leads to a recursive procedure for adding nodes: first (ind(G) −1)-nodes, then (ind(G) − 2)-nodes, and so forth. Figure 5.3 shows a rectangular subset of the 2D incidence grid² that is completed by adding six 1-nodes and then adding three 0-nodes.

Figure 5.1 (middle) is an example of a complete subset.

The core of the subset M on the left in Figure 5.3 is connected; it consists of four 1-components of 2-nodes. M is a proper subset of M ⁺, so M is not complete; the core of M ⁺ contains two 1-components of 2-nodes.

5.1.2 Incidence grids

[S, I, dim] is called a 2D or 3D incidence grid iff one of the following is true: (i) it is or ; (ii) it is a finite complete subpseudograph of defined by a core that is an m × n rectangular subset of ; or (iii) it is a finite complete subpseudograph of defined by a core that is an l × m × n cuboidal subset of .

Any incidence grid has properties I1 through I6, as well as two other properties:

In addition, the nodes of an incidence grid have locations in Euclidean space. Incidence grids are the “default examples” of incidence pseudographs, just as α- or (α₁,α₂)-adjacency grids are the “default examples” of adjacency graphs.

The cores of incidence grids are sets of pixels (2-cells) or voxels (3-cells). Definition 5.2 allows two 1-cells of to be 0-, 2-, or 3-adjacent, but, in accordance with property I4, they cannot be 1-adjacent. A 1-path in can contain 0-, 2-, or 3-cells but not 1-cells. An i-path or i-component can be restricted to contain only cells of a given dimension; see Figure 2.18. A path of cells of dimension i is defined by 0-, 1-,…,or (i − 1)-adjacency.

Figure 5.4 shows the one-dimensional incidence pseudograph of . Repeated merging operations (contraction; see Section 4.2.2), as shown in the middle of Figure 5.4 (including the deletion of all loops), can be used to transform this graph into a graph isomorphic to .

Let G =[S, I, dim] be an n-incidence grid (n ≥ 1), and let 0 ≤ n₀ < n. By deleting all i-nodes from S (n₀ < i ≤ n) and all edges that have these i-nodes as endnodes, we obtain an n₀-incidence pseudograph that is a subpseudograph of [S, I, dim]. Such a subpseudograph is called a downward restriction of G For example, let G be the 3D incidence grid , and let n₀ = 2. We can delete all 3-cubes from to obtain a subpseudograph that consists of only grid squares, grid edges, and grid vertices. Figure 5.5 shows a 2D example: a one-dimensional downward restriction of a rectangular subgraph of , which can be transformed into by repeated merging operations.

A finite nonempty complete subset M ⊆ S of an incidence grid [S, I, dim] defines an incidence structure [M, I′, dim′], where I′ and dim′ are the restrictions of I and dim to M. Such a structure satisfies properties I1 through I3 but need not satisfy properties I4 through I8.

5.1.3 Components and regions; borders

In this section, M is a complete subset of an n-incidence structure G =[S, I, dim].

For example, M ⁺ on the right in Figure 5.3 is a component. A nonempty M may have no components, and the union of all of the components of M may not be all of M. Even a complete M is not always a union of components; there may be i-nodes in M (i < n) that are not incident with any n-node of M. Our main interest is in finite M s that are unions of components.

The following definitions are analogous to the definitions for adjacency graphs in Section 4.1.3:

For example, the incidence pseudograph shown in Figure 5.2 is a region. The completion of its core {a, e, f} is {a, d, e, f}. {a, b, d, e, f} and {a, c, d, e, f} are regions. M ⁺ on the right in Figure 5.3 is a region, but M on the left is not a region, because it is not complete.

If M = S, it has only inner nodes. Figure 5.6 shows two examples of inner sets and borders. (Closed and open regions will be defined in the next section.) The same sets are shown in Figure 5.7 using the geometric representation of 2D incidence grids that was defined in Section 2.1.5.

5.1.4 Closed and open regions

The following definitions do not have analogs for adjacency graphs:

Figure 5.6 shows examples of a closed and an open region. In Figure 5.2, {a, d, e, f} is an open region, because {b,c} is a closed set (but not a region); {a,b,d,e,f} is open; and {a, c, d, e, f} is neither closed nor open. In Figure 5.3, M + on the right is neither closed nor open. Evidently, S and θ are both closed and open. Any closed or open M is complete. Closed and open sets are not necessarily components; they may contain only nodes of dimensions < n, or they may be disconnected.

The proof of Proposition 2.3 gave a procedure for assigning every 0- or 1-cell of the 2D incidence grid to exactly one incident 2-cell in a 2D picture P, and Proposition 2.4 generalized this procedure to the 3D incidence grid. The procedure was based on a decomposition of the grid into P-equivalence classes, which define incidence substructures that are unions of components (and hence are complete). These substructures, except for the one that contains the infinite background component, are all finite. Figure 5.8 shows an example in which the 2D procedure produces either “black closed components” and “white open components” or vice versa.

As a direct consequence of the definition of closedness, we have the following:

The incidence pseudographs in Figures 5.3 and 5.6 are monotonic.

The closure of a finite subset M of an n-incidence pseudograph is the smallest closed region that contains M. We can construct the closure of M by adding all cells c′ such that c′ ∈ I(c) and dim(c′) < dim(c) for some c ∈ M.

5.2.1 Boundaries, chains, and frontiers

Let G =[S, I, dim] be an n-incidence pseudograph. A node c ∈ S is invalid with respect to M ⊆ S iff , but there is an n-node c′ ∈ M such that c′∈ I (c). This definition generalizes the concepts of invalid edges and boundaries in adjacency grids. We recall that any adjacency graph can be transformed into a one-dimensional incidence pseudograph; see Example 5.1.

Figure 5.9shows two examples of boundaries for n = 2. The boundary of S is empty, and the boundary of a region contains no principal nodes.

Let M ⊂ S be finite. A cell c of M will be denoted by c⁽ⁱ⁾ if dim(c) = i. An i-chain is an expression of the form C⁽ⁱ⁾ = where each b_k = 0 or 1 and the sum is taken over all of the i-dimensional cells of M. We say that is in C⁽ⁱ⁾ iff b_k = 1; we can identify C⁽ⁱ⁾ with the set of i-nodes that are in C⁽ⁱ⁾. We define the addition of i-chains modulo 2: where the bs are added modulo 2. Thus is in the sum of two i-chains iff it is in exactly one of the chains. We write C⁽ⁱ⁾ = 0 if all of its bs are 0 so that it corresponds to an empty set of i-nodes.

Let C⁽ⁱ⁾ be an i-chain (i> 0). The chain frontier is the (i − 1)-chain where a_k is the number (modulo 2) of i-cells in C⁽ⁱ⁾ that are incident with C⁽ⁱ⁻¹⁾. For i = 0, we define = 0. It is not hard to show that is a linear operator (i.e., [modulo 2]).

C⁽ⁱ⁾ is called an i-cycle if = 0. Evidently, a 0-chain is a cycle; a sum of i-cycles is an i-cycle; and the frontier of any chain is a cycle (i.e., for any i-chain, we have ).

Figure 5.10 shows a subset M of the 2D incidence grid, with 2-cells abhg, bcih, and so on; 1-cells ag, ab, and so on; and 0-cells a, b, and so on. Using the above definitions, we have a = 0; ab = a + b; abgh = ab + bh + gh + ag; (ij + jn + no + ko + jk) = i + 3j + 2n + 2o + 2k = i + j; and jk + ko + no + jn is a 1-cycle.

For example, the open region A consisting of the single 2-node jkno in Figure 5.10 has boundary M = {j, k, n, o, jk, ko, no, jn}. The set of 1-nodes in M has an empty frontier, so it is a 1-cycle.

Let M be a closed region in an infinite incidence pseudograph. is the union of a finite number of pairwise disjoint open regions and one infinite open subset of S. A (finite) open region is either an open hole (if it is circumscribed by its boundary) or an open finite background region; the infinite open subset is the open background. The border nodes of the closed region in Figure 5.11 are shown in Figure 5.12. If we assume that the incidence pseudograph in Figure 5.11 is a subset of the 2D incidence grid and use nodes of the incidence grid not shown in the figures, the border also contains the two 1-nodes in the top row and three more 1-nodes and five more 0-nodes that “close” the border on the right and at the bottom.

Similarly, if M is an open region, we obtain closed holes (circumscribed by their borders), closed finite background regions, and a closed background. Figure 5.6 (or Figure 5.7) shows an open hole (after removing node a), and Figure 5.13 shows an open region for which the infinite background is a closed component (but not a region because it is infinite). The boundary nodes in Figure 5.14 coincide with the boundary nodes of the open region in Figure 5.13.

We recall Definition 3.2 for a subset A of a Euclidean space: the frontier A is the set-theoretic difference between the closure A• and the interior A°. The frontier of A°,of A•, or of any set containing A° and contained in A• is also A.

In analogy with the Euclidean topology, we call the interior of M. Note that, if M is a component, M° is an open component.

Section 4.3.6 discussed borders and boundaries in adjacency grids at the abstract level of adjacency graphs. There we were able to state alternatives, but were unable to unify “border” and “boundary” as in Theorem 5.2, which led to Definition 5.11.

5.2.2 The matching theorem

The matching theorem in this section is a basic combinatorial formula for finite incidence pseudographs of index dimension n ≥ 0.

Because of self-incidence and property I4 (see Section 5.1.1), if dim(c) = i, we have a_ii(c) = 1. Table 5.1 gives examples of incidence counts.

Equation 4.4 follows from the matching theorem, because v(p) = a₀₁(p) for any node p of an adjacency graph [S, A]. Equation 4.4 can also be derived using the incidence counts a₁₀(e) for the edges e:

This definition generalizes Definition 4.7. The complete graphs K_n are examples of finite regular one-dimensional incidence pseudographs. The nodes of K_n have dimension 0, the edges of K_n have dimension 1, and every node is self-incident. The infinite incidence grids and are also regular.

If G has index dimension n ≥ 1 and M is a finite subset of G, the numbers shown here are called the class cardinalities of M:

(5.1)

We usually omit the superscript M.

From the Matching Theorem, we know that, for finite regular incidence pseudographs, we have α_ia_ij = α_ja_ji for 0 ≤ i, j ≤ n. It follows that this equation holds true

(5.2)

for any (e.g., fixed) index k (0 ≤ k ≤ n). Hence the possible integer values of the class cardinalities α_k and α_i define constraints (Diophantine equations) on the incidence counts aki and aik (and vice versa).

5.2.3 The Euler characteristic

In this section, we generalize the definition given in Section 4.3.2 for finite oriented adjacency graphs in 2D. Note that an edge is incident with a cycle iff it is listed in the cycle, and a node is incident with an edge iff it is one of the edge’s endnodes.

For example, for the G shown in Figure 5.2, we have x(G) = 1 − 2 + 3 = 2. Adding an edge (e.g., between nodes b and e) does not change the Euler characteristic. However, deleting a node (e.g., 2-node e) results in an incidence pseudograph G′ for which x(G′’) = 1 −2 + 2 = 1.

If G is regular, the Matching Theorem gives us the following:

These n + 1 equations (k = 0, 1,…, n) are rational multiples of one another.

Figure 5.16 shows regions in the infinite regular incidence grid that define subpseudographs (loops omitted). For the upper left region, we have χ = 3 − 10 + 8 = 1; for the lower left region, we have x = 1 − 4 + 4 = 1; for the region on their right, we have χ = 5 − 5 + 1 = 1; and, for the remaining 1-path, we have χ = 7 − 6 + 0 = 1. For the region M + shown on the right in Figure 5.3, we have χ = 15 − 28 + 14 = 1; note that removing marginal border nodes changes this value. In Figure 5.6, for the closed region on the left, we have χ = 12 − 33 + 22 = 1, and, for the open region on the right, we have χ = 12 − 15 + 4 = 1. Removing the “central” 2-node a from the closed region creates an “open hole” and gives χ = 11 − 33 + 22 = 0. These examples illustrate the topologic invariance of the Euler characteristic; see Section 6.4.5.

5.3.1 Regular infinite incidence pseudographs

The incidence grids and , when regarded as pseudographs [S, I, dim], are monotonic (property I6) and also have properties I7 and I8.

This generalizes Definition 2.1. An informal description is as follows: A 1-cell is “created” by translating a 0-cell along any of the segments e_j. A 2-cell is the area occupied by a 1-cell while it shifts along an orthogonal segment e_j, and a 3-cell is the volume occupied by a 2-cell while it shifts along an orthogonal segment ej. Figure 5.17 illustrates these processes up to the creation of a 4-cell.

(n ≥ 1) is called the regular n-incidence grid. It can be verified that it has properties I6 and I8. Its incidence counts are as follows:

(5.3)

For example, an i-cell c ∈ is incident with 2^n–1 n-cells. Equation 5.3 implies the following for 0 ≤ i, j ≤ n:

(5.4)

Equation 5.4 in turn implies the following for 0 ≤ i ≤ n:

(5.5)

Both of these equations will later prove to be very useful.

5.3.2 The region matching theorem

In this section, are class cardinalities, and a_ij are incidence counts in the regular incidence grid . Note that the a_ij are constants. For n = 2, they are as follows:

a₀₀ = 1, a₀₁ = 4, a₀₂ = 4,

a₁₀ = 2, a₁₁ = 1, a₁₂ = 2,

a₂₀ = 4, a₂₁ = 4, a₂₂ = 1

For n = 3, they are as follows:

a₀₀ = 1, a₀₁ = 6,a₀₂ = 12, a₀₃ = 8,

a₁₀ = 2, a₁₁ = 1, a₁₂ = 4,a₁₃ = 4,

a₂₀ = 4, a₂₁ = 4, a₂₂ = 1,a₂₃ = 2,

a₃₀ = 8, a₃₁ = 12, a₃₂ = 6,a₃₃ = 1

The numbers shown here are called boundary counts for the cells in M:

The numbers shown here are called total boundary counts for M:

From now on, we omit the superscript M.

Note that the proof of this theorem makes no use of the connectedness of a region, but only of its being either closed or open. Figure 5.18 shows an open and a closed region. For the open region, we have α₀ = 0,α₁ = 1,α₂ = 2, b₁₀ = 2, b₂₀ = 8, and b₂₁ = 6; for example, 1 · 2 + 6 = 2 · 4 if i = 1 and j = 2. For the closed region, we have α₀ = 7,α₁ = 8,α₂ = 2, b₀₁ = 12, b₀₂ = 20, and b₁₂ = 8; for example, 7 · 4 − 20 = 2 · 4 if i = 0 and j = 2.

The formulas of the Region Matching Theorem hold for any finite union of pairwise disjoint closed (or open) regions.

For a closed region M or a finite union of pairwise disjoint closed regions, the Region Matching Theorem implies the following:

For example,α_n specifies the contents of an isothetic polyhedron in (n ≥ 2). These formulas allow us to calculate α_n based on counts of, for example, vertices; see Section 8.1.6 for n = 2 and Section 8.3.7 for n = 3. Using Equation 5.5, it follows that the Euler characteristic, as follows,

can be calculated for any j (0 ≤ j ≤ n) by counting only invalid cells (cells on the boundary of the region). Similarly, for an open region M or a finite union of pairwise disjoint open regions, we have the following for any 0 ≤ j ≤ n:

Indices j = 0 and j = n give the simplest expressions. In the next section, we will show that these expressions can be further simplified.

5.3.3 Euler characteristics

We apply the Region Matching Theorem and Conclusion 5.3.2:

Analogously, for open regions, we have the following:

The following theorem was proved by K. Voss in 1993 for open regions:

The b_i–1,_is and b_i+1,_i s in Theorem 5.2 can be replaced with class cardinalities and (globally known) incidence counts because the following are given:

Let n = 3. For a closed region, b₀₁ is the number of invalid grid edges incident with grid vertices in the region, b₁₂ is the number of invalid grid squares incident with grid edges in the region, and b₂₃ is the number of invalid grid cubes incident with grid squares in the region. For open regions, we use b₁₀, which is the number of invalid grid vertices incident with grid edges in the region; b₂₁, the number of invalid grid edges incident with grid squares in the region; and b₃₂, the number of invalid grid squares incident with grid cubes in the region. Note that the total boundary counts are sums over all cells in M so that invalid cells may be counted repeatedly if they are incident with several cells in M.

Figure 5.19 shows a 2D example. For the left closed region, we have b₁₂ = 16 and b₀₁ = 16, and, for the right closed region, we have b₁₂ = 4 and b₀₁ = 8. For the left open region, we have b₂₁ = 16 and b₁₀ = 16, and, for the right open region (a single node), we have b₂₁ = 4 and b₁₀ = 0.

5.4.1 Ordered labeling

In a labeled incidence pseudograph G =[S, I, dim], each node in G has a label, and the labels belong to a finite set {L₀,…, L_max}.

A picture assigns labels (values of pixels or voxels) to all of the principal nodes of S. We assume that the set of these labels is totally ordered by “significance,” so nodes labeled L_max are the “most significant” (e.g., “object pixels”) and nodes labeled L₀ are the “least significant” (e.g., “background pixels”). For example, a 2D picture assigns labels (pixel values) to all 2-cells in G _m,n and label L₀ to all 2-cells in the infinite background component.

An ordered labeling of the nodes of an incidence pseudograph is defined by assigning labels to the principal nodes and extending this labeling to the other nodes by applying the following maximum-label rule:

According to I5, any marginal node has candidate labels, and, according to I1, the set of candidates is finite, which allows us to choose the largest of them. The rule ensures that regions labeled with L_max are closed and regions labeled with L₀ are open.

In picture processing or analysis, we do not need to perform actual labeling but only to detect adjacencies between labeled principal nodes, assuming that all marginal nodes have been labeled. During a scan through the set of principal nodes, we have to decide whether two nodes c₁ and c₂ such that I(c₁) ∩ I(c₂) ≠ ø are still adjacent after ordered labeling. An algorithm for this is given in Algorithm 5.1. An order by decreasing node dimension (Step 2) has been assumed for efficiency reasons; the scan through the marginal nodes in I(c₁) ∩ I(c₂) should visit nodes with I(c) s that have increasing cardinalities, and the ordering by node dimension may ensure this.

If G is a binary picture and we assume that black (or white) is the most significant label, the resulting adjacency is just the (4,8)- or (8,4)-adjacency defined in Section 2.1.4. These two adjacencies are illustrated in Figure 5.20, together with the corresponding representations of the components in the incidence grid.

The situation is more complicated if G is a multilevel picture, because there are many possible total orderings of the labels. Figure 5.21 illustrates three such orderings for a three-valued picture; each ordering yields a different adjacency structure.

In the next section, we will describe a general method of defining adjacencies for a given ordered labeling. In a 2D picture, this method yields adjacencies in which diagonal adjacencies never “cross,” as illustrated in Figure 5.22. These adjacencies can be defined using the 2 × 2 masks shown in Figure 5.23. Note that these masks accept all 4-adjacencies between pixels that have the same label and that they also accept diagonal adjacencies between two pixels that have the same label as a third pixel that is adjacent to both of them. Only in case (g) is it necessary to choose between

tween the (black, black) and (white, white) diagonal adjacencies. When this method of defining adjacencies is used, the adjacencies define a planar graph, and, as we will see in Chapter 7, the resulting region adjacency graph is a tree.

5.4.2 The ordered adjacency procedure

We now describe a general procedure for the ordered labeling of incidence grids that applies in particular to 2D or 3D multilevel pictures. Let G =[S, I, dim] be a labeled n-incidence grid, and assume a total ordering of the set of labels. Our ordered adjacency procedure defines adjacencies between principal nodes of G that depend on this total order.

Let S be finite, let c₀ be a 0-cell, and let I ⁽ⁿ⁾(c₀) be the set of all principal nodes in I(c₀). We begin with any 0-cell c₀ in S and any pair c₁ and c₂ of nodes in I ⁽ⁿ⁾(c₀), and we proceed as described in Algorithm 5.2. We then continue for all of the remaining 0-cells in S.

This procedure guarantees that components are defined by (n − 1)-adjacency between principal nodes if they have the same label or by i-adjacency (i <n) if their label “wins” over at least one “competing” label. It simplifies the switch approach described in Section 2.1.3 by eliminating redundant adjacencies and generalizes it to incidence grids of arbitrary dimension.

The result of applying the procedure to the multilevel picture shown in Figure 2.19 is shown in Figure 5.24. The scan of I⁽ⁿ⁾(c₀) to list all pairs (c₁,c₂) in it can be based on a uniform local cyclic order, but the result is independent of the order in which the pairs are chosen.

The adjacency defined by applying the procedure to a picture depends only on the total order of the labels 0,…, G_max. As a default, we assume the order 0 < 1 < … <G_max, for which we have the following:

5.4.3 Frontiers in 2D incidence grids

In a 2D incidence grid, the boundary of a closed region consists of one or more 1-components of 2-cells (grid squares), and the boundary of an open region consists of one or more 0-components of 1-cells (grid edges). The union of the 1-cells in the boundary of an open region is the same as the boundary of the region in the 1-adjacency grid. Figure 4.27 (right) shows an example.

The set of 1-cells that are incident with exactly one 2-cell of a region defines the frontier of the region. Every 0-component of these 1-cells has a Hamiltonian circuit that visits each 1-cell in the 0-component exactly once.³ The border tracing algorithm (see Chapter 4) can be used to trace the border cycles in the 0-adjacency graph of these 1-cells.

We now describe a method of representing these sets of 0- and 1-cells. Let P be a picture on an m × n grid G, which we call the picture grid. We extend this grid to an (m + 1) × (n + 1) frontier grid F, where each grid point in F represents a grid vertex (0-cell) in F specifically, grid vertex (x–0·5, y−0·5) in G represents grid point (x,y) in F⁴ Figure 5.25 shows the picture grid and the frontier grid for the picture shown in Figures 1.10 and 5.22.

The geometric representation of the frontiers in G is the union of the small squares and thin rectangles that represent 0-cells and 1-cells, respectively. Figure 5.25 shows counterclockwise frontier traversals for the interior regions and clockwise traversals for the exterior regions and the (infinite) background component. This reflects the use of local circular order (A) in Figure 4.19. We use the following notation when q₂ is the direct successor of q₁ in the local circular order at p_i :

To traverse all of the frontiers, we scan the picture (e.g., using a standard scan [see Section 1.1.3]) until we arrive at a pixel (x₀, y₀) in G that has an 0-cell on a “new” frontier component of a region or of the background. We then generate a 4-path in G that traverses this frontier. To do this, we start at the upper left 0-cell of (x₀, y₀) (i.e., at grid point (x₀, y₀ + 1) in F). Each step from a grid point to a 4-adjacent grid point on the frontier goes around a pixel, keeping the pixel on the right as shown in Figure 5.26. A step σ ∈ {UP, RIGHT, DOWN, LEFT} specifies how the coordinates of this pixel τ_σ are chosen.

We assume the default order for the pixel values u and v. In the flip-flop case (g) (see Figure 5.23), adjacency between pixels that have value v is preferred over adjacency between pixels that have value u if u <v. The frontier tracing algorithm is given in Algorithm 5.3. It is a special case of the general border tracing algorithm of Figure 4.26. The important difference is that here we test whether the step sequences σ, σ′ are possible at a grid point. If a step sequence is not a left turn, it is possible iff the pixelτ_σ′(q) has value u = P(x₀,y₀); if it is a left turn, it is impossible iff the two diagonal pixels other thanτ_σ (p_i) andτ_σ′ (q) have the same value w> u. The algorithm could be further optimized by removing redundant tests, but its time complexity is linear in the number of 1-cells on the 0-component of the frontier that is being traced.

5.4.4 Frontiers in 3D incidence grids

In a 3D incidence grid, the boundary of a closed region consists of one or more 2-components of 3-nodes (grid cubes), and the boundary of an open region consists

of one or more 1-components of 2-nodes (grid faces). In the latter case, the boundary defines a 1-adjacency graph of grid faces, all incident with grid cubes in the open region and with grid cubes in the complementary set. Figure 5.27 shows the simplest example; the open region consists of a single grid cube, and the 1-adjacency graph of its frontier has a Hamiltonian circuit.⁵ If we add one cube at a time that is incident with exactly one face of the union of the existing cubes (note that we also have to add that face itself to ensure that the region remains complete), we obtain a 2-connected set of grid cubes that forms a simple 2-tree that contains no circuits (and therefore is a tree) and no 2 × 2 cube configurations (and therefore is simple).

Arbitrary regions in a 3D incidence grid may not have Hamiltonian circuits or paths through the 1-components of 2-nodes on their frontiers. A complete traversal of the faces on the frontier requires in general that some faces be visited repeatedly.

Let F = [S, I, dim] be a downward restriction of the 3D incidence grid that contains all of the cells in the frontier of a region. The FILL procedure (see Algorithm 4.1) provides a way of visiting all of the faces in F.

Let L be a 3D array of the same size as the array that represents the voxels. We assign labels to L that correspond to voxel positions. We use six bit-positions in each label, which correspond to the six faces of a voxel. A 1 in the ith position indicates that the face has already been visited. The tracing algorithm starts at some face in S and applies FILL based on the adjacency defined for the faces in F by available 0- and 1-cells. We can use a stack or queue in Figure 4.3 to implement a depth-first or breadth-first traversal of all of the faces on the frontier.

This frontier tracing algorithm is easy to implement, but the faces are visited in an “unordered” sequence. The purpose of the tracing (e.g., coloring all of the frontier faces, approximating the frontier by segments of digital planes) may determine whether the algorithm is of interest. Note that the algorithm is based on graph-theoretic concepts only; it makes no use of an embedding of the 3D incidence grid into a Euclidean or metric space.

1. Which of the following relational properties are true in general for adjacency, (smallest nontrivial) neighborhood, and incidence: reflexivity, irreflexivity, symmetry, and transitivity?

2. A simple polygon has vertices (cells of dimension 0), edges (cells of dimension 1), and one face (a cell of dimension 2). Suppose we tile the plane with simple polygons in an arbitrary, irregular way, adding one simple polygon at a time that is disjoint from all previous polygons except for sharing an edge with one of them. This defines an incidence pseudograph with respect to set-theoretic incidence. What is the Euler characteristic of this pseudograph, assuming that the union of all of the polygons is a simple polygon (i.e., it has no holes)?

3. A Gray code [376] for a sequence of consecutive integers has the property that the codes for successive integers differ by only one bit. For example, 0 → 00, 1 → 01, 2 → 11, and 3 → 10 is a Gray code for the integers 0,1, 2, and 3 (in that order). In analogy to Definition 5.15, we can construct hypercubes as follows: We label the vertices of a 1-cell 0 and 1. Given a labeled k-dimensional hypercube, we make two copies of it, append 0 and 1 to the node labels of the first and second copy, respectively, and connect corresponding nodes in the two copies with new edges. Prove that the sequence of node labels on any Hamiltonian circuit of the resulting (k + 1) -dimensional hypercube defines a Gray code for the integers 0,1,…,2^k + ¹ −1.

4. Prove that the family of open (closed) regions in is closed under finite unions and intersections.

5. Let the unions of the following sets of cells be either open or closed regions in . Calculate the Euler characteristics of these regions using the equation in Definition 5.14 or using Theorem 5.2.

6.  Prove Equation 5.6 by induction on m.

7. Suppose the ordered adjacency procedure is applied to the two multilevel pictures shown below. Identify the components of the P-equivalence classes, trace their frontiers, and calculate their Euler characteristics.

8. Implement the frontier tracing algorithm for 2D multilevel pictures, assuming the default total order of the picture values.

9. Extend the frontier tracing program of Exercise 8 by counting local properties during frontier tracing and combining the counts to determine the Euler characteristic. The program should have runtime complexity linear in the number of 1-cells visited during frontier tracing.