2.1.1 Grid points and grid cells

In 2D, the grid point set is Z², and, in 3D, the grid point set is Z³. A grid vertex is shifted by (0·5,0·5) with respect to a grid point in 2D and by (0·5, 0·5, 0·5) in 3D.¹ A pair of adjacent grid vertices (i.e., vertices at Euclidean distance 1 from each other)defines a grid edge. A grid square is defined by four grid edges that form a square, and a grid cube in 3D is defined by six grid squares that form a cube.

We specify grid points, vertices, edges, squares, and cubes in terms of Cartesian coordinates. In 2D, the set of positions of the grid vertices is as follows:

A grid edge² connects a pair of adjacent grid vertices:

(2.1)

A grid square is defined by a quadruple of grid edges in which successive edges (modulo 4) share a vertex.

(2.2)

In 3D, the positions of grid vertices, grid edges, grid squares, and grid cubes are specified similarly.

In both 2D and 3D, the sets of grid vertices and grid points are congruent This supports the use in this book of the same planar or spatial grid for 2D or 3D pictures when we use either the grid cell or grid point model.

The dimensionalities 3, 2,1, and 0 of grid cubes, grid squares, grid edges, and grid vertices suggest an alternative terminology:

In this terminology, a 2D grid point is the center point of a 2-cell (see Figures 2.2 and 2.3), and a 3D grid point is the center point of a 3-cell. C⁽ⁱ⁾₂ will denote the set of all i-cells in the plane (i = 0,1,2), and C⁽ⁱ⁾₂ will denote the set of all i-cells in 3D space (i = 0,1,2,3). We also define the following:

(The symbol is often used in the mathematic literature for the set of complex numbers, but this book will make no use of complex numbers, so there is no conflict when using to denote sets of cells.)

We now define the two basic grid models that will be used throughout this book:

These grids can also be defined for a grid constant θ different from 1, but θ = 1 is the default value throughout this book. Grid cells or grid points are the basic elements used in digital geometry. A pixel is either a 2-cell (grid square) or a grid point (the center of a 2-cell); see Figure 2.2. A voxel is either a 3-cell (grid cube) or a grid point (the center of a 3-cell). The formulation of a definition or algorithm may sometimes be more convenient when one or the other model is used.

A grid line in 2D is incident with two different grid points whose x- or y-coordinates are the same. The 2D grid Z² can be regarded as a subset of the 3D grid Z³ by adding a third coordinate z = 0 to every 2D grid point. In 3D, a grid plane is incident with two orthogonal grid lines. It follows that all of the grid points of a grid plane have the same x-, y-, or z-coordinate. A grid line in 3D is a set of points, two with coordinates that are constant in Z, whereas the third is a variable in R. Grid lines intersect at grid points in either 2D or 3D.

2.1.2 Variable grid resolution

The grid constant θ is the distance between neighboring grid lines. Grid resolution is the inverse of the grid constant. It refers to the number of grid elements per unit of distance without specifying the physical size of the unit. We will use an integer parameter h gt; 0 to denote grid resolution. In a grid with resolution h = 1, we can have either one grid point in a unit or two grid points as endpoints of a unit. In general, the maximum number of grid points per unit is h + 1.³

The parameters h and θ are useful when discussing the possible effects of improvements in geometric or picture resolution. They are especially relevant in theoretic studies of the convergence behavior of algorithms under refinement of grid resolution (i.e., decrease of the grid constant).

Let Z_h = {i/h : i Z}; then is the set of all 2D grid points in a grid of resolution h gt; 0, and is the set of all such 3D grid points. We similarly use the notation

for grid cells in a 2D or 3D grid of resolution h.

2.1.3 Adjacencies in 2D grids

In other words, two 2-cells c₁ and c₂ are 1-adjacent iff they are not identical but they share a grid edge. Let p_i be the center of c_i (i = 1,2); then c₁ and c₂ are 1-adjacent iff p₁ and p₂ are 4-adjacent

We have defined relations A₁ of 1-adjacency and A₄ of 4-adjacency for the grid cell and grid point models. In general, we write pR_q or (x,y)∈ R iff p,q are in relation R. In this notation, we have c₁A₁c₂ iff {c₁,c₂} ∈ A₁, iff c₁ and c₂ are 1-adjacent, and p₁A₄p₂ iff {p₁,p₂} ∈A₄ iff p₁,p₂ are 4-adjacent. The relation A₁ (A₄) is symmetric and irreflexive.

In other words, two 2-cells c₁ and c₂ are 0-adjacent iff they are not identical but share (at least) a grid vertex. Again, let p_i be the center of c_i (i = 1,2); then c₁ and c₂ are 0-adjacent iff p₁ and p₂ are 8-adjacent. The relation A₀ (A₈) is symmetric and irreflexive.Figure 2.4 illustrates relations A₀, A, A₄, and A₈ on a square grid.

Adjacent 2-cells are transformed into adjacent grid points by mapping the 2-cells onto their center points, and adjacent grid points are transformed into adjacent 2-cells by mapping the grid points into the 2-cells that have them as center points. The existence of this one-to-one mapping gives us the following:

(In general, let R₁ be a relation on a set S₁ and R₂ a relation on a set S₂. The structures [S₁, R₁] and [S₂, R₂] are called isomorphic iff there exists a one-to-one mapping f from S₁ onto S₂ such that pR₁q iff f (p)R₂f (q) for all p,q ∈ S₁. The mapping is called an isomorphism.)

For the relations A₁ and A₄ on C₂ (Z²), the number of pixels (grid points or grid cells) adjacent to a pixel is always 4. For A₀ and A₈, it is always 8; however, for adjacency relations defined on pictures, the number can vary.

Adjacencies between pixels in multilevel pictures are defined by locations and pixel values. To start with, let us consider the values alone. Let P be a picturedefined on the grid G in which pixel p has value P (p) in {0,1,…,G_max}. We say that two pixels p and q are P-equivalent iff P(p) = P(q). Let M_u be the set of all qg such that P(q)= u. If there exists pg such that u = P(p), M_u is an equivalence class with respect to the relation of P-equivalence on G (in brief, a P-equivalence class).

These P-equivalence classes are defined only by pixel values, not by locations. Each P-equivalence class splits into components, depending on the adjacency relation used for the pixels. For example, we can define p and q to be P-adjacent if they are 8-adjacent (or 0-adjacent) and P-equivalent. The number of pixels P-adjacent to p can then vary between 0 and 8. Using 8-adjacency uniformly for all values u may lead to situations such as the one illustrated in Figure 1.9.d (If there are more than two values, we cannot use 4-connectedness for one value and 8-connectedness for the other as proposed in Section 1.1.4 for binary pictures.)

More generally, we can model ‘uncertainties” in picture values by assuming that we are given a similarity relation σ (a reflexive and symmetric relation) on V × V, where V = {0,1,…,G_max}. (For example,σ₂ is the similarity relation in which uσ₂v iff |u – v|≤ 2.) Define two pixels p,q to be σ,α)-adjacent iff pA αq and P(p)σP(q). The relation of (σ,α)-adjacency is symmetric and irreflexive. Note that p may have no (σ,α)-adjacent pixels if P(p) is not σ-similar to the value of any of the pixels that are α-adjacent to p.

In the remainder of this section, we describe a method of defining adjacencies in a 2D multivalued picture P, which we call switch adjacency (or s-adjacency) and denote with A_s. Switch adjacency allows us to avoid topologic conflicts (see Section 1.1.4 about binary pictures).

Pairs of 4-adjacent pixels are always regarded as s-adjacent; in other words, A_s ⊇ A₄. In addition, in each 2 × 2 block of pixels, we call exactly one of the two diagonally adjacent pairs s-adjacent. We can think of the 2 × 2 block as a switch that can be in either of the two diagonal positions (see Figure 2.5); the position of the switch determines which diagonally adjacent pair of pixels in the block is regarded as s-adjacent. The states of the switches in P can be specified by a binary picture S (a ‘switch state matrix”) that has pixels that correspond to the lower left-hand corners of the 2 × 2 blocks of pixels in P. A pixel of S has value 1 iff the switch in the corresponding 2 × 2 block of P is to the left (in the main diagonal position) and value 0 iff that switch is to the right (in the other diagonal position).

We can define specific s-adjacency relations in many ways. The switch position in a block can depend on the position of the block (i.e., on the coordinates of its lower left-hand corner) and not on the values of the pixels in the block. For example, S can be the binary picture in which pixel (x,y) has value 1 if y is odd and 0 if y is even. (In this case, two pixels are s-adjacent iff their hexagonal distance d_h is 1;see the leftmost image of Figure 2.7, and see Section 3.2.3 about metric d_h.) It is more ‘natural” to let the diagonal s-adjacencies depend on the pixel values. Let the difference between the values of one pair of diagonally adjacent pixels in a 2 × 2 block be d₁ and the difference between the values of the other pair be d₂; if d₁ d₂, we call the first pair s-adjacent; if d₂ d₁, we call the second pair s-adjacent. This determines all of the s-adjacencies, except in flip-flop cases, where d₁ = d₂; in such a case, the switch can be in either position. In real pictures, flip-flop cases are rare (see Figure 2.6); there are typically less than 0.5% of such cases in a grayscale picture and less than 0.2% in a color picture (see Figure 2.8 for four grayscale examples).

Evidently the s-adjacency relation is symmetric and irreflexive. The number of pixels s-adjacent to p can be anywhere between 4 (the pixels 4-adjacent to p) and 8 (up to four additional diagonal adjacencies).

In general, we can use a Set Switches procedure to define a switch state matrix S. The procedure can analyze larger neighborhoods of a pixel to determine the state of its switch. This analysis can be based on templates such as those shown in Figure 2.9 in which the state of the switch in the lower 2 × 2 block is also used in the upper 2 × 2 block. S can even be generated randomly (using a random number generator) or using a function of the pixel coordinates (e.g., a pseudorandom function, to avoid bias).

2.1.4 Adjacencies in 3D grids

The definitions of 1-adjacency and 0-adjacency of 2-cells (Definitions 2.2 and 2.3) can also be used in 3D, and we can also define the 0-adjacency of 1-cells. However, ourmain interest is in adjacencies between 3-cells or 3D grid points. Let d_e be the Euclidean metric (see Section 1.2.1).

Let c₁ and c₂ be 3-cells and let pi be the center of c_i (i = 1, 2). Then c₁ and c₂ are 0-adjacent iff p₁ and p₂ are 26-adjacent iff c₁ and c₂ are not identical but share a grid vertex; c₁ and c₂ are 1-adjacent iff p₁ and p₂ are 18-adjacent iff c₁ and c₂ are not identical but share a grid edge; and c₁ and c₂ are 2-adjacent iff p₁ and p₂ are 6-adjacent iff c₁ and c₂ are not identical but share a grid square (see Figure 2.10).

This defines symmetric and irreflexive relations A_α, where α = 0,1,2 for the grid cell model and α = 6, 18, 26 for the grid point model. The parameter α denotes the dimension of the intersection of the grid cells in the first case and the number of adjacent grid points in the second case.

Data-dependent types of adjacencies (see Section 2.1.3) can also be generalized to 3D grids. We can now define the 2D and 3D grid point and grid cell adjacency models:

Both 2D and 3D grid point and grid cell adjacency models are called α-adjacency grids; the value of α determines whether we use a grid point model (α > 4) or a grid cell model (α ≤ 3). In Section 1.1.4, we briefly mentioned a dual use of adjacencies for 2D binary pictures P:α₁-adjacency for and α₂-adjacency for ; in this case we speak about (α₁,α₂)-adjacency grids.

Let A be a symmetric and irreflexive adjacency relation on a set S. A(p) = {q : qS ∧ qAp} is called the adjacency set of p∈S. For example, for relation A₄ on grid points, we have the following,

(2.3)

provided all four of these grid points are also contained in the grid G_m,n.

N(p) = A(p)∪{p} is called the (smallest nontrivial) neighborhood of p ∈ S defined by adjacency relation A. N defines a symmetric and reflexive relation qNpon S.p ∈ S is never in A(p) but is always in N(p). Figure 2.11 shows A₁ (A₄) and N₁ (N₄) for the 2D grid cell and grid point models. Analogous drawings for A₀ (A₈) and N₀(p) (N₈(p)) would also contain the grid cells or grid points in the four corners.

2.1.5 Grid cell incidence

Two sets are called incident iff one of them contains the other (i.e., any set is incident with itself). For example, a 3D grid vertex (0-cell) is incident with six grid edges (1-cells); a grid square (2-cell) is incident with four grid edges; and a grid cube (3-cell) is incident with 12 grid edges.

Figure 2.12 shows four ways of representing a 2D grid. In the grid cell model, we can use only 2-cells (upper right), or we can also use 0- and 1-cells (lower right). In the first case, we can use 0- or 1-adjacency to define a grid cell adjacency model, and, in the second case, we use the incidence relations between all of the cells to define the 2D grid cell incidence model.

There exists a grid point adjacency (incidence) model that is isomorphic to any of these grid cell adjacency (incidence) models. For grid points, we usually use only an adjacency model; however, for completeness, we mention that a grid point incidence model can be defined by adding isothetic edges between grid points—and “loops” consisting of quadruples of such edges—to the set of grid points. This refined model is isomorphic to the grid cell incidence model. In the correspondence between the models, a grid point p is the center of a 2-cell, an isothetic edge connecting p with another grid point intersects a 1-cell, and a loop of four such edges has a 0-cell as its center. The dimensions of the elements in the grid point incidence model are defined by the dimensions of the corresponding cells; for example, a loop is zero-dimensional.

Analogously, there are four types of models for 3D grids: (1) grid point and (2) grid cell adjacency models (see Section 2.1.4); (3) a grid cell incidence model that includes 0-, 1-, and 2-cells in addition to 3-cells (and again, for completeness, (4) the grid point model allows a structure that is isomorphic to the grid cell incidence model in which a grid point corresponds to a 3-cell [in which it is the center]); an isothetic edge between two grid points corresponds to a 2-cell (which it intersects at its center point), a loop of four isothetic edges corresponds to a 1-cell (where the loop defines a square having the 1-cell at its center), and 12 such edges forming a cube correspond to a 0-cell (at the center of the cube).

The 2D and 3D grid cell incidence models are called (2D or 3D) incidence grids.

This definition leads to a recursive test for completeness: start with the 3-cells, then check the 2-cells between them, then check the 1-cells that are incident only with 2- or 3-cells already known to be in M, and so on.

The geometric representation of the 2D incidence grid used in this book is illustrated in Figure 2.13: 0-cells are small squares (representing grid vertices);1-cells are thin rectangles (representing grid edges); and 2-cells are large squares.⁴In 3D, we use a similar representation, with small cubes as 0-cells, large cubes as 3-cells, and elongated (flat) cuboids as 1-cells (2-cells); see Figure 2.14. Despite these geometric representations, an i-cell is still considered to be of (abstract) dimension i.

2.2.1 Connectedness and components

Let G be an adjacency grid. A sequenceρ = (p₀,…,p_n) of pixels or voxels, where p₀ = p, p_n = q, and p_i+1 is adjacent to p_i (0 ≤ i ≤ n − 1), is called a path of length n from p to q, and p and q are called the endpixels or endvoxels ofρ. The elements p and q are called connected if there is a path from p to q. In particular, for α-adjacency (α {0, 1, 2, 3, 4, 6, 8, 18, 26}), we use the terms ‘α-path” and ‘α-connected.”

Figure 2.15 shows a 1-path of 2-cells in the grid cell model and the corresponding 4-path in the grid point model. Figure 2.16 shows a 2-path of 3-cells in the grid cell model and the corresponding 6-path in the grid point model.

Let M be a finite subset of G. A maximal connected set of pixels or voxels of M is called a component of M. Evidently p, q M are in the same component of M iff there is a path completely contained in M that has p and q as endpixels (endvoxels).

Let G_m,n be an m × n grid. (Similar remarks apply to an l × m × n grid G_l,m,n) G_m,n can be extended into the infinite discrete plane (Z² in the case of the grid point model; in the case of the grid cell model). Let M be a subset of G_m,n; thus the complement of M contains the complement _m,n of G. The (infinite) set of pixels of M that are connected to pixels of G_m,n is called the background component of M. Any other pixel of belongs to a finite component of .

Let P be a picture defined on G. The P-equivalence classes define subsets of G. Components of these classes are often of interest, as we will see in later chapters. Figure 2.17 illustrates the components defined by these classes in a 5-valued picture using 1-adjacency in the grid cell model. Class 5 consists of six 1-components (also defining two complementary 1-components, one of which belongs to the background 1-component of class 5); class 4 consists of five 1-components (both complementary 1-components belong to the background 1-component of class 4); class 3 consists of four 1-components (one complementary 1-component); class 2 consists of four 1-components (two complementary 1-components, both belonging to the background 1-component of class 2); and class 1 consists of three 1-components.

In the 2D or 3D incidence grid, two cells c₁ and c₂ are called k-adjacent iff they are not identical and there is a k-cell c (c ≠ c₁ and c ≠ c₂) that is incident with both c₁ and c₂

Figure 2.18 shows examples of paths for these adjacency relations. This definition generalizes the concepts of 1-adjacency (see Definition 2.2) and 0-adjacency (see Definition 2.3) between 2-cells or of α-adjacency (0 ≤α ≤ 2) between 3-cells (see Definition 2.4). Connectedness and components in 2D or 3D incidence grids can be defined using these adjacency relations.

The following two propositions show that for pictures defined on an incidence grid, cells can be assigned to P-equivalence classes in such a way that the componentsof the classes are complete. We give the proof for the 2D grid only; the 3D generalization is straightforward.

Figure 2.19 shows an example of such an assignment for the picture P shown in Figure 2.17. Note that we do not need an extended data structure to represent P on an incidence grid; all of the assignments of 0- or 1-cells are determined by the order of the picture values.

2.2.2 Counting connected sets

A finite connected subset of the 1-adjacency grid[] is called a polyomino. (Polyominoes illustrate the combinatorial complexity of finite sets of pixels; see Chapters 13 and 14 about polyominoes in the context of digital convexity and digital tomography.) If it consists of exactly n grid squares, it is called an n-omino.

Equivalence classes of polyominoes can be defined with respect to geometric transformations that map the grid into itself. Such transformations include (see also Section 14.4) translations by vectors (i,j), i, jZ∈ rotations around the origin by 90°, 180°, or 270° and reflections in the x- or y-axis.

Two polyominoes are called translation-equivalent if there is a translation that maps one of them into the other. A translation-equivalence class of polyominoes is called a fixed polyomino. An equivalence class of polyominoes with respect to translations and rotations is called a chiral polyomino; an equivalence class of polyominoes under translations, rotations, and reflections (a congruence class) is called a free polyomino.⁵

Figure 2.20 shows the 12 free 5-ominoes. Figure 2.21 shows the 369 free 8-ominoes (the 8-ominoes that contain a hole are positioned in the center of the figure; the filled dots indicate 8-ominoes that contain at least one 2 × 2 block).

The numbers of fixed n-ominoes, chiral n-ominoes, and free n-ominoes are denoted by t(n), r(n), and s(n), respectively. It is not hard to show the following:

There are no simple formulas for these functions, but the following has been demonstrated [371]:

(2.4)

Table 2.1 shows the values of t(n),r(n), and s(n) for 1 ≤ n ≤ 24. The calculation of these functions is a topic in the theory of polyominoes. Redelmeier’s algorithm [839] for calculating them has exponential time complexity; no algorithm is yet known that has subexponential time complexity. An algorithm for generating polyominoes would also be of interest; it could be used to generate data sets for testing algorithms in digital geometry.

2.2.3 Component labeling

The following task arises frequently in picture analysis and computer graphics; it is known as labeling, filling, or region detection. Let P be a 2D multivalued picture defined on a finite adjacency or incidence grid G, and let the P-equivalence classes have a total of k components. We regard the (infinite) complement of G as consisting of pixels that all have the same value, so they belong to one of the components. The task is to assign k labels (e.g., integers) to the pixels of P in such a way that all ofthe pixels in each component have the same label and pixels in different components have different labels. To keep P unaltered, we can put the labels into an array of the same size as P.

A simple method of labeling components is as follows. Scan the picture until a pixel p is found that has not yet been labeled. Suppose P(p)=u and that labels L₁,…,L_k−1 have already been used. Choose a new label L_k, and call the procedure FILL(p, u,L_k) (see Algorithm 2.1). (Note that the adjacency set A(r) may depend on u [e.g., if we use 1-adjacency for 1s and 0-adjacency for 0s].) After labeling the component that contains p, continue scanning the picture until all of the pixels have been labeled.⁶Figure 2.22 shows the order of the pixel visits (assuming the ordershown on the right is used for visiting 1-adjacent pixels) when this algorithm is used to label the white pixels of the picture in Figure 2.23.

The Rosenfeld-Pfaltz labeling algorithm [921] labels all of the components of P in two scans of P (see Section 1.1.3); see Algorithm 2.2 In the first scan, we propagate smallest labels, and, whenever labels merge, we note this fact in a table of equivalent pairs of labels. In the second scan, we replace each label with a representative of its equivalence class. This algorithm replaces the use of a stack (of size mn) in procedure FILL with the use of an equivalence table; its run time can be compared with that of the simple depth-first search procedure for given classes of pictures. It also provides an illustration of the cases that can occur during component labeling.

As an example of the operation of this algorithm, consider the binary picture shown in Figure 2.23. In the label propagation step of the algorithm, we use 1-adjacency for white pixels and 0-adjacency for black pixels. At the end of the first scan (a standard scan), we have the equivalence table shown in Table 2.2. Label A is also the label of all of the pixels of the background component. Note that some equivalences are detected more than once.

The equivalences between pairs of the 20 labels A,…,T are shown in Figure 2.24. We will use the smallest label in each equivalence class as the pivot of that class.

To find the pivots, we scan the labels in order, smallest first. Any label that is equivalent to A has pivot A and can be marked and replaced with A. We next examine the smallest label that has not yet been marked; this label must be the pivot of its equivalence class so that all of the labels equivalent to it can be marked and replaced with it. This process is repeated until all of the labels have been marked.⁷The pivots in our example are shown in Table 2.3.

A binary picture of size m × n in which 0s and 1s alternate (‘a chessboard”) requires O(mn) labels. An a priori threshold on the number of labels can be used to limit the size of the equivalence table. However, memory limitations are no longer an issue, which they were in 1966, when the algorithm was first published.

The nontriviality of connected component labeling is illustrated in Figure 2.25. In one of these binary pictures, the black pixels are connected, and in the other one, there are two 4-components of black pixels; can you tell which is which?

2.3.1 Gauss digitization

C.F. Gauss (1777–1855) studied the measurement of the area of a planar set S ⊂ R² by counting the grid points (i,j)∈Z² contained in S. This approach suggests the following:

Figure 2.26 shows the Gauss digitizations G(D) of four disks D of different diameters (measured in grid units). (The results would be the same if the disks all had unit diameter and were digitized on grids of different resolutions. The Gauss digitization of S on a grid of resolution h will be denoted by G_h(S).) G(D) is an isothetic polygon that has 12 vertices for diameter 5, 20 vertices for diameter 10, and 36 vertices for diameter 17. Note that the number of vertices is always a multiple of 4, because a disk that is centered at a grid point has a symmetric Gauss digitization.

Obviously, different sets can have identical Gauss digitizations. Figure 2.27 shows the Gauss digitization of a simple polygon Π with area 102,742.5 and perimeter 4,040.796,631… drawn on a 512 × 512 grid. On the upper left, each grid squarecontains 64 × 64 squares of the original 512 × 512 grid; in the upper middle, 32 × 32; and so on.

Figure 2.28 shows the relative deviations of the area and perimeter of G_h (Π) from those of Π when Π is digitized on a 2ⁿ × 2ⁿ grid (i.e., h = 2ⁿ). The relative deviation is the absolute difference between the property values for G_h (Π) and Π divided by the property value for Π. See Chapter 4 for an in-depth discussion about perimeter estimation; the perimeter of G_h(Π) (i.e., the number of 1-cells on its frontier) is not a good estimate of the perimeter of Π.

Gauss digitization is defined analogously in 3D. If S ⊂ R³, the Gauss digitization G_h(S) is the union of all of the 3-cells (in a grid of resolution h gt; 0) with center points in S.

2.3.2 Jordan digitization

Let S ⊂ R³ and h gt; 0. The magnification of S by factor h is denoted by h. S. In terms of multiplication of vectors by a scalar (see Section 1.2.12), we have the following:

This magnification leaves the origin (0,0,0) fixed; other points of R³ could also be chosen as fixed points.

C. Jordan (1838–1922) [484] used grids to estimate the volumes of subsets of R³. Let S ⊂ R³ be contained in the union of finitely many 3-cells. Magnify S by factor h with respect to an arbitrary fixed point p R³; this transforms S into . Let (S) be the number of 3-cells completely contained in and the number of 3-cells that have nonempty intersections with . Then and converge to limits L(S) and U(S), respectively, as h goes to infinity; these limits are the same for any p [484]. Jordan called L(S) the inner volume and U(S) the outer volume of S or the volume V(S) of S if L(S) = U(S).

We use Jordan’s digitization model for subsets of the plane as well as of 3D space:

Outer Jordan digitization is also called super-cover digitization [209]. (Inner Jordan digitization will be further specified in Section 3.2.5 by one additional [topologic] constraint that is still missing in the above definition.) Figure 2.29 shows a 2D example in which S is a circle of radius n (in grid units) for n = 4 (left), n = 8 (middle), and n = 16 (right). If the frontier of a nonempty set S ⊆ R² does not contain any grid edge segment of nonzero length, then the frontier of (S) never intersects the frontier of (S). For example, this is the case if S has a smooth frontier that has continuous partial derivatives with respect to both coordinates and has positive curvature everywhere. A straight line γ has an empty (γ) and a connected J⁺ (γ).

Propositions 2.5 and 2.6 have straightforward 3D generalizations.

2.3.3 Grid-intersection digitization

Gauss digitization and inner Jordan digitization are obviously not appropriate for curves or arcs.⁹ Outer Jordan digitization is appropriate, but, in this section, we will define grid-intersection digitization, which is commonly used for arcs and curves in the plane.

Figure 2.30 illustrates this definition. Note that an intersection point may have the same minimum distance to two different grid points; such an intersection point contributes two grid points to R (γ). (Alternatively, we could always choose, for example, the right point or the upper point.)

A traversal of γ defines an ordered sequence (list) of grid points in R (γ). We assume the following for simplicity: (i) if an intersection point is at the same minimum distance from two grid points, we list only the grid point that has the larger x-coordinate, or, if their x-coordinates are equal, the one with the larger y-coordinate; and (ii) if consecutive intersection points have the same closest grid point, we list that grid point only once.

The resulting ordered sequence of grid points is called the digitized grid-intersection sequence ρ(γ) of γ (see Figure 2.31). It defines a polygonal arc (or polygon) with vertices at grid points. The sequence represents R(γ) uniquely if an intersection point is never at the same minimum distance from two grid points.

A similar method can be used to digitize a 3D arc or curve γ: for each intersection point of γ with a grid plane, we add the grid point(s) closest to the intersection point to the digitization.

Successive pairs of grid points inρ(γ) define steps of length 1 along grid lines and diagonal steps of length . The directions of the steps can be represented with codes 0,1,…,7 as shown at the lower left of Figure 2.31 code i represents a step that makes angle (45.i)° with the positive x-axis. Figure 2.31 shows an example of the directional encoding of an arc. The directional codes are usually called chain codes. A chain is an ordered finite sequence of code numbers. In Chapter 9, such a sequence will be described as a word in an alphabet, which is the (finite) set of code numbers. The length of a chain is the number of code numbers in it; note that this length is not related to the geometric length of the arc or curve represented by the chain.

The (geometric) length of ρ(γ) is the sum of the lengths of the steps. The question arises whether this length can be used to estimate the length of γ. In what follows, we denote the grid-intersection digitization of γ in a grid of resolution h with R_h(γ) and the corresponding digitized grid intersection sequence by ρh(γ). Note that, for any γ, we have the following:

(2.5)

Let γ be rectifiable; thus γ has a well-defined length L(γ). The length ofρ(γ) is not a good estimate of L(γ); it does not necessarily converge to L(γ) as the grid constant goes to zero.

As a simple example, consider the straight line segment pq in Figure 2.32 that has a slope of 22.5° and a length of The length of ρ(pq) is for grid constant 1 and for all grid constants 1/2ⁿ (n > 1). This shows that the length ofρ(pq) does not converge to as the grid constant goes to zero.

As a more general example, consider a line segment γ with slope 1/(m + 1). Its chain code representation is (0^m1)^k, where k depends on the grid resolution. No matter what k is, the length ofρ(γ) is k(m + ) where L(γ) is . The ratio L(ρ(γ))/L(γ) is not 1 unless m = 0 or m →∞.

We conclude this section by discussing the grid-intersection digitization of a straight line segment. Bresenham’s algorithm [122] is a standard routine in computer graphics (Algorithm 2.3). We discuss the use of this algorithm to digitize a segment of a line y = ax + b in the first octant (i.e., with slope a ∈ [0, 1]). To draw the resulting digital straight line segment, we increase the x-coordinate stepwise by + 1; the y-coordinate is ‘occasionally ” increased by + 1 and remains constant otherwise. (By interchanging the startpoints and endpoints of the segment, we can handle octants ‘to the left of the y-axis.” In the eighth octant, we use a y-increment of −1, and in the second and seventh octants, we interchange the roles of the x- and y-coordinates.)

The digital straight line segment is a sequence of grid points (x_i, y_i), i > 1. The point (x₁,y₁) is the grid point closest to the endpoint of the real segment. If we already have point (x_i, y_i), the next point has x-coordinate x_i1, and, for its y-coordinate, we must decide between y_i and y_i + 1. Let y = a(x_i + 1) + b, and define the differences

h₁ and h₂ (see Figure 2.33) with the following:

To decide between y_i and y_i + 1, we use the following difference:

We choose (x_i + 1,y_i) if h₁ h₂ and (x_i + 1,y_i + 1) otherwise. For reasons of efficiency (integer arithmetic only), we do not use h₁ – h₂ for this decision. Rather, let p = (x₁, y₁) and q = (x_q, y_q) be the grid points closest to the endpoints of the segment, and let dx = x_q – x₁ and dy = y_q – y₁. Let e_i = dx · (h₁ – h₂); thus e_i = 2(dy · x_i – dx · y_i) + b′, where b′ = 2dy + 2dx · b – dx is independent of i. Thus e_i can be updated iteratively for successive decisions at x_i + 1 and x_i + 2:

Thus

because x_i.₁ = x_i + 1; this is sufficient for deciding about the y-increment. Let x₁ = x_p = 0 and y₁ = y_p = 0 give the starting value:

The resulting algorithm for the first octant is shown above. At Step 1, we have error = e₁ = 2dy − dx. The values b₁ = 2 · dy and b₂ = 2 · dy − 2 · dx are used to efficiently update the variable error. The algorithm runs in O(x_q – x_p) time because, for each i, it involves only a constant number of operations: setting one pixel value, two simple logical tests, one addition, and one or two increments.

2.3.4 Types of digital sets

If γ is, for example, a straight line, straight line segment, circle, or parabola, we call R_h(γ) a digital straight line, digital straight segment, digital circle, or digital parabola, respectively.

If S is, for example, a disk, square, or convex set (and similarly in 3D), we call (S),G_h(S), or (S) a digital disk, digital square, or digital convex set, respectively, provided it is connected. We call a connected set of grid points a digital disk and so forth (with respect to a given digitization model), if there exists a disk and so forth that has that connected set as its digitization.

If Gauss or inner Jordan digitization is used, a connected set can have a digitization that consists of several connected isothetic polygons (polyhedra). On the other hand, the outer Jordan digitization of a connected set S is always a single connected isothetic polygon or polyhedron. However, J⁺ does not preserve simple connectedness; it can create holes.

Figure 2.34 shows how a disk in different positions can create different digital disks by Gauss digitization. The left and center digital disks both consist of 24 grid points, but the disk on the right consists of only 22 grid points. It can be shown that the number of different digital disks (up to translation), with respect to Gauss digitization, that consist of exactly n ≥ 1 grid points is at most the following:

(2.6)

Gauss and Jordan digitization allow us to study methods or algorithms of digital geometry under slightly different assumptions about the relationships between sets S in the Euclidean plane and their digitizations. Evidently, (and similarly for R³). If S is a nonempty proper subset of R² or of R³ with a smooth frontier, we have . Furthermore, the following is true:

(2.7)

One or both relations ⊆ in the left part of Equation 2.7 can be replaced by =, but both cannot be if S has a smooth frontier. Let S be a finite union of grid squares; then we have J⁻(S) = G(S) = J⁺ (S).

2.3.5 Domain digitizations

In this section, we define a framework for a general class of digitization models. To simplify the discussion, we formulate this framework in n dimensions (n ≥ 1), but our main interest is of course in n = 2 and n = 3.

Let the following be the n-cell centered at the origin o = (0,…,0):

Let ≠ Π_σ ⊆ Π_cube…., and consider translates Π_σ (q) = {q + p : pΠ_σ} of Π_σ centered at grid points q Zⁿ. (Note that Π_σ(q) is the Minkowski sum of Π_σ and {q}.) In particular, π_cube…. (q) is the n-cell c_q centered at q.

We will use the translates Π_σ (q) of Π_σ as the domains of influence for digitizations that we call and For any set S ⊆ Rⁿ,(q) is the union of all c_q such that Π_σ (q) intersects S, and (S) is the union of all c_q such that Π_σ (q) is contained in S. Thus the following is true:

(2.8)

So (S) is called the outer σ-digitization of S and the inner σ-digitization of S. Evidently, for any S ⊆rⁿ, we have (S) ⊆ (S) ⊆ .

We now show that Jordan and Gauss digitizations are all σ-digitizations and that grid-intersection digitization can also be regarded as a σ-digitization.

Thus the Jordan digitizations are σ-digitizations in which Π_σ is a cube; Gauss digitization is a σ-digitization in which Π_σ is a point; and grid-intersection digitization is essentially a σ-digitization in which Π_σ is a cross. Other digitization models can be defined by using other simple sets Π_σ (e.g.,“ball digitization” by using Π_σ = {(x₁,…,x_n):}, ‘diamond digitization” by using Π_σ = {(x₁,…,x_n): max{|x₁|,…,|x_n|, 1/(n−1) These digitizations are illustrated in Figure 2.35. The figure also illustrates a general property that follows directly from the definitions of dig_σ⁺ and and :

2.4.1 Content estimation

Any simple grid polygon P has a well-defined area and perimeter. The area A(P) is defined by the number of grid squares contained in P multiplied by h⁻², which is the area of a single grid square. The perimeter P(P) is defined by the number of grid edges that form the frontier of P multiplied by 1/h, which is the length of a single grid edge. These measurements are invariant with respect to rotations and translations.

A grid polyhedron is simple iff it is topologically equivalent to a closed sphere. (For topologic equivalence, see Chapter 6.) The surface area S (Π) and the volume V (Π) of a simple grid polyhedron Π are defined by the number of 2-cells that form the frontier of Π multiplied by h⁻² and the number of 3-cells contained in Π multiplied by h⁻³, respectively.

The question arises whether these properties of grid polygons or grid polyhedra can serve as estimates of the corresponding properties of real objects that have the polygons or polyhedra as their digitizations. Such estimates can be evaluated using criteria such as absolute error or bias (for a fixed h) or convergence (as h → ∞).

Let S ⊂ rⁿ (n ≥ 1) be a closed bounded set that has measurable content C(S), which is the length L(S) for n = 1, the area A(S) for n = 2, and the volume V(S) for n = 3. We consider a fixed grid constant 1 and magnifications of S by factors h gt; 1. (Our preferred model of a fixed set S and increases in the grid constant will be used in Section 2.4.2.) Let N (S)= C (G(S)) be the number of grid points in S; this is defined by its Gauss digitization in the n-dimensional orthogonal grid.

Suppose S_h depends on only one parameter h gt; 0 (e.g., a disk or a sphere depends on its radius h). Then the following is true as h →∞:

(2.9)

Magnification of S by the factor h with respect to the origin O ∈ Rⁿ transforms S into S_h. (Magnification was defined in Section 2.3.2 only for n = 3, but its generalization to any n ≥ 2 is straightforward.) For n = 2, we have [616, 1023] the upper bound

(2.10)

where P(S) ≥ 1 is the perimeter of S, assuming that S has a rectifiable frontier.¹¹The following general upper bound (for n > 2) was claimed by R. Lipschitz (1832–1903) in [658]:

in a recent letter to him. Let J be a closed rectifiable Jordan curve of length l, enclosing an area a. Then, provided l > 1, the number w of points with integral coordinates inside J satisfies | w – a| l. The proof is elementary and depends on the following result: if a Jordan arc S joins two points on the boundary of the square , dividing the square into two regions, and if Δ is the region which does not contain the origin, then the area of Δ is less than the length of S. This is proved by simple considerations in each of four possible cases.” The following general upper bound (for n > 2) was claimed by R. Lipschitz (1832–1903) in [658]:

(2.11)

where Q is the greatest (n − 1)-dimensional content of any of the projections of S into the (n − 1)-dimensional subspaces of Rⁿ defined by x_i = 0(i = 1,…,n) and c is a positive constant. Without discussing constraints on the set S, it was pointed out in [248] that this upper bound cannot be correct; in fact, it fails for a long thin cylinder around one of the coordinate axes, where N(S) can be arbitrarily large and C(S) and Q can be arbitrarily small.

Suppose the bounded closed set S ⊂ Rⁿ is such that the following are true: (i) any line parallel to one of the coordinate axes intersects S at a set of points that (if it is not empty) consists of at most t intervals; and (ii) the same is true (with m in place of n) for any of the m-dimensional sets (m = 1,…,n−1) obtained by projecting S into a subspace defined by setting any n – m coordinates to zero. Then we have the following:

Note that t does not change when S is magnified by a factor h (e.g., with respect to the origin).

The n-dimensional content of S ⊂ Rn is the zero-order moment of S (see Chapter 17). Error estimates for content and for digital moments are a general topic in number theory. For information about error estimates for digital moments when n = 2, see Theorems 17.2 and 17.3.

2.4.2 Convergent 2D area estimates

A (real) disk of unit diameter has A(D) = π/4 and P(D) = π. The area of a digitized disk converges toward the area of the real disk:

(2.12)

On the other hand, the perimeter of the digitized disk is always equal to 4, because the total length of the isothetic edges on its frontier remains constant as h increases; thus it trivially converges, but not toward the correct value P(D) = π.

Digital geometry should provide accurate estimates of quantitative properties of digitized sets if the grid resolution is sufficiently large. The study of the accuracy of such estimates is one of the main topics in this book.

Estimation of the area of a planar set by the number of grid points contained in the set has an extensive history in number theory. C.F. Gauss and his colleague P. Dirichlet (1805–1859) at Göttingen University already knew that the number of grid points (i,j)Z² inside h · S (the magnification of a given planar convex set S by factor h) estimates A(h · S) within an asymptotic order of O(P(h · S)). Note that, because S is convex, P(h · S) is O(h).

Let S be a convex set contained in a unit square so that P(S) ≤ 4 =O(1), and consider increases in the grid resolution h instead of magnifications by an increasing factor h. A(G_h(S)) is estimated by the number of grid points (i/h,j/h) inside S times the scale factor h⁻²; note that h⁻² is the size of a 2-cell in G_h(S). Then we can rewrite the historic result as follows:

2.4.3 Multigrid convergence

A general scheme for comparing measurements made on a digital picture subset with the true measurements for the preimage of the subset in Euclidean space has been formalized by J. Serra [969]. (Limit properties with respect to digitizations were also studied in [740] by U. Montanari.)

Let F be a family of sets S in Rⁿ, and let dig_h (S) denote a digitization of S on a grid of resolution h. Assume that a property Q (e.g., area, perimeter) is defined for all S ∈F. The following definition specifies also a measure of the speed of convergence of a digital quantity toward the true quantity:

In Theorems 2.2, 2.3, and 2.4, F is the set of planar convex 3-smooth sets, dig_h is the Gauss digitization G_h, and Q is the area A. The estimate E_a is obtained by counting the number of grid points scaled by the area of the 2-cells. Theorems 2.2 and 2.4 demonstrate progress in obtaining upper bounds on the convergence speed, and Theorem 2.3 provides a lower bound. The actual convergence speed is between these bounds and is still unknown.

There are two ways to study convergence with respect to increased grid resolution: either consider sets h · S digitized on a grid with unit grid constant, or consider sets S digitized on grids with grid constant 1/h. In both cases, h →∞ corresponds to an increase in grid resolution; we consider either a repeatedly magnified h · S in the grid with unit grid constant or a fixed S in a repeatedly refined grid. The repeatedly refined grid approach is commonly used in numeric mathematics and is also the preferred approach in this book. This is motivated by the assumed scenario in which the set to be analyzed remains physically the same while improvements in hardware (e.g., scanners, computing power) allow refinements in grid resolution. However, in experiments on multigrid convergence, it is often more appropriate to use repeatedly magnified sets digitized into pictures of increasing size.

1. A spider sitting on the surface of a cubic room wants to crawl over all six faces of the cube and return to its starting point as quickly as possible. Does the starting point affect the length of the shortest path?

2. Prove that there is no equilateral triangle that has all three of its vertices in Z² (see also Exercise 15 in Section 1.3) but that there are equilateral grid triangles in Z³.

3. Use the 12 free 5-ominoes (see Figure 2.20) to cover a 6 × 10 rectangle without overlap. (Hint: All congruence transformations are allowed.)

4. The following figure shows a convex polygon S and its digitization G_h(S). In this example, G_h(S) consists of two rectangles. Give conditions on a bounded convex polygon S and on the grid resolution h gt;0 that imply that G_h(S) consists of exactly one simple isothetic polygon. (For example, this is true if S is an isothetic rectangle.)

5. Construct Gauss digitizations of a square (of constant size) in different orientations using grid resolution 6. Draw a diagram showing the relative deviations of the area and perimeter of the digitized square as a function of its orientation.

6. Consider a polygonal arc with vertices that are grid points and with endpoints that are on the border of G_mn so that the arc cuts G_m,n into two parts. Write a program to determine whether the parts can be moved apart (as in the three cases on the left in the figure above) or not (as in the three cases on the right). (Hint: If so, they can be moved apart by sliding them in the direction of one of the arc segments.)

7. When we use the coding scheme of Figure 2.31, adding 2 modulo 8 to all of the directional codes results in a 90 rotation of the curve. Give an example of a digital curve for which adding 1 modulo 8 to all of the codes results in a digital arc that is not a closed digital curve. (It follows that the addition of 1 modulo 8 does not result in a 45 rotation.)

8. Define a code for the frontier of a free polyomino consisting of the numbers of 2-cells incident with the vertices of the polyomino when the vertices are visited by scanning the frontier of the polyomino in clockwise order. For example, 113131121312 encodes the free 5-omino shown on the right in Figure 2.21 when the scan starts at the upper left vertex. Any cyclic permutation of this code represents the same free polyomino with respect to a different starting vertex. Define the vertex chain code (VCC) of the free polyomino as the smallest integer that can be generated in this way. (In our example, it is 112131211313.) Prove that, for any free polyomino, the sum of the codes in a VCC of length n is 2n − 4.

9. Let n be the length of the VCC (see Exercise 2.8) of a given free m-omino M, and let c be the number of 1-adjacent pairs of 2-cells in M. (For example, c = 4 for the free 5-omino shown on the right in Figure 2.21.) Prove that 2c + n = 4m.

10. Let γ be the straight line y = x +ε. How does the value of ε affect the digitizations J⁺ (γ), R(γ), andρ(γ)?

11. Show that the 2D cross digitization of any planar convex set is either empty or a polygonally connected set (see Exercise 4 in Section 1.3).

12. How large should h be to achieve the same accuracy of π = 3.14 that Archimedes obtained if the perimeter of the convex hull of G_h(D) is used for the perimeter estimation of D where D is the unit disk? (Hint: The answer can be found by implementing Graham Scan [see Section 1.2.9] using the leftmost and rightmost vertices in all the rows of the grid that intersect D.)

13. Implement Bresenham’s algorithm (see Algorithm 2.3) and measure the length of the digital segment by initializing a variableL_est as 0 and adding 1 for every isothetic step and . for every diagonal step. Calculate the relative deviation between L_est and d_e (p, q) (the length of the real segment pq) for different slopes of pq. Which slopes produce maximum deviations?

14. The circle (x – x_c)² + (y – y_c)² = r² can be digitized by using the formula y = y_c± (r² – (x – x_c)²)^1/2, which defines (in general) two y-values for every integer x in [x_c – r,x_c + r]. Alternatively, each grid line that intersects the circle is perpendicular to a diameter of the circle that divides the grid line into two rays. Usually there exists a grid point on each of these rays that minimizes the residual |(x² – x_c)² + (y – y_c)² – r²|; these minimum-residual grid points also define a digitization of the circle. Characterize positions of (x_c,y_c) and values of r for which the minimum is not unique.

15. Prove that the residual |x² + y² – r²| is never the same for adjacent grid points on a grid line if r² is an integer. It follows that the minimum is unique whenever (x_c,y_c)∈Z² and r²∈Z.

16. The digital circle produced by the minimum-residual method has a sharp corner iff three of its consecutive grid points form a right angle; this can happen only at octant frontiers. The figure below illustrates a sharp corner when r = 4 and shows that no sharp corner exists when r = 9. Prove that sharp corners occur iff either there exists an integer x > 0 such that r² = x² + x + 1 or there exists an integer y >0 such that r² = 2y² − y + 1.

17. Let (x_c,y_c) = (0,0) and r ∈ Z, and suppose (x_i,y_i) (i ≥ 1) is a grid point on the digital circle generated using the minimum-residual method, where (x₁,y₁) = (0,r) and x_i r. Suppose the (upper) ray at x = x_i intersects the circle at (x_i,y), where y ∈ R. Let d_1,i = –y², d_2,i = y² – ( − 1)², and e_i = d_1,i – d_2,i. Prove the following:

    Show how these error calculations can be used to generate a digital disk using the given formulas in the second octant and using reflection in the remaining octants.

18. Let S be a measurable set in R² with a frontier that is a rectifiable simple closed curve. Let A(S) be the area of S and P(S) its perimeter. We recall (see Section 1.2.11) that P²(S)/A(S) ≤ 4π and = 4π iff S is a disk. Let M be a finite set of grid points; define A(M) as the number of grid points in M and P(M) as the number of border grid points in M (i.e., grid points of M that are adjacent to ). Show that P²(M)/A(M) does not take on its minimum value when M is the set of grid points of a digitized disk.