10.1.1 Curve digitizations

The topologic frontier of a simply connected compact set S in the Euclidean plane is a simple curve γ :[0,1] → . We assume that γ is rectifiable. In a grid,γ and S are represented in digitized form. We are interested in estimating the length and curvature of γ from its digital representation. In accordance with Definition 2.10, let dig_h(γ) be a digitization of γ in . Three possible digitizations of γ are as follows:

These digitizations define 2D digital curves in either the grid point or grid cell model. Option (iii) is, in general, the same as the outer Jordan digitization of γ (e.g., if γ does not follow any grid edge).

The h-frontier of S may consist of several nonconnected curves, even if S is convex; see Figure 10.1. Figure 10.1 also shows how this situation can be resolved; if h is sufficiently large, the dark shaded rectangle in Figure 10.1 provides a connection between the components. However, situations in which components cannot be connected for any grid resolution can arise at a vertex of a polygon that has a small interior angle 0 <η π/2 (see Figure 10.2). The vertex of the angular sector (assumed here to be a grid point in ) cannot be connected with the other points in G_h(S) (shown as filled dots) by any 8-path. In this example, there is a ray with rational slope 1/5 “inside” the sector. Any grid resolution 5nh (n ≥ 1) leads to the same situation.

S is called h-compact iff there is an h₀ > 0 such that (S) is a single (connected) curve for any h ≥ h₀. When we deal with Gauss digitizations, we may sometimes have to require h-compactness.

In 3D, we will consider two possible digitizations of an arc or curve γ : [0,1] → ³:

If γ does not pass through any 1-cells, its outer Jordan digitization is a 2-connected sequence of voxels.

In either 2D or 3D, the input can be given as a sequence of pixels or voxels in an adjacency grid and can be encoded by a chain code i(0),i(1),…, where i(k) ∈ A = {0,…, 7} in 2D and i(k) ∈ A = {0,…,26} in 3D (k ≥ 0).

10.1.2 Local and global estimation

Arc length estimates can be based on local metrics such as weighted or chamfer distances; see the end of Section 3.2.3. For example, isothetic steps in the 2D grid can be weighted by θ and diagonal steps by or we can use weights , and in the 3D grid. An advantage of such estimates is that they have linear online algorithms. The same is true for local curvature estimates, which take only fixed numbers of neighboring pixels or voxels into account.

A local estimator makes use of a polygonization of the digital arc or curve obtained by connecting successive grid points or grid vertices in a neighborhood of constant size. Global estimators, on the other hand, do not use fixed neighborhoods. (“Local” and “global” are formally defined in Section 8.4.3.) They may be based on maximum-length digital straight segments (DSSs), on minimum-length polygons (MLPs), or on approximations of normals or tangents.

10.1.3 DSS-based estimation

A DSS segmentation of an α-path ρ consists of DSSs of maximum length that define a polygonization of ρ; see Figure 10.3 (left) for a 2D example. The DSSs of the polygon are of potentially unlimited length. The sum of the lengths of the DSSs defines a DSS-based length estimator. (No weights are needed; the lengths of the DSSs are the Euclidean lengths of the corresponding line segments.) This length may depend on the starting point and on whether ρ consists of grid points or of vertices of grid cells.

A DSS centered at a pixel or voxel p of ρ is also a global approximation of a tangential line segment¹ toρ and can be used in the estimation of the curvature of ρ at p.

10.1.4 MLP-based estimation

A second class of global arc length estimators are MLP-based; see Figure 10.3 (right) for a 2D example. In 2D, an MLP is a minimum-length polygon that circumscribes the inner frontier of S and is in the interior of its outer frontier. As we saw in Section 1.2.9, the 2D MLP is the convex hull of the inner frontier relative to the outer frontier and is uniquely defined.

The intrinsic distance (see Section 3.2.4) between two points in a simple polygon is the length of a shortest arc that connects the points and is contained in the polygon. It is not hard to see that this shortest arc is polygonal and that the polygon is a metric space under intrinsic distance. The intrinsic diameter of the polygon is the maximum intrinsic distance between any two of its points. It is not hard to see that this diameter is the intrinsic distance between two vertices of the polygon. Analogous definitions can be given for a simple polyhedron.

Let M_θ be the union of the cells in a simple 1-curve in [², ≤] (see Section 7.2.2). ϑM_θ can be partitioned into two curves γ₁ and M₂ that are the frontiers of two isothetic polygons P₁ and P₂ such that P₁ ⊂ P₂°. The length of M_θ is defined as the length of the minimum-length curve in M_θ that encircles M₁ (see Figure 10.4, left). Similarly, let M_θ be the union of all of the cells in a simple 1-arc in [, ≤]. The length of M_θ is defined as its intrinsic diameter (see Figure 10.4, right). It is not hard to prove that M_θ is a DSS iff its intrinsic diameter is defined by a straight line segment.

Similarly, let M_θ ⊂ be the union of all of the cells in a simple 2-arc or 2-curve in [, ≤]. If M_θ is a simple 2-curve, its length is the length of a minimum-length curve that is contained in M_θ and is not contractible into a single point in M_θ (see Figure 10.5, left). If M_θ is a simple 2-arc, its length is its intrinsic diameter (see Figure 10.5, right), and M_θ is a DSS iff its intrinsic diameter is defined by a straight line segment. M_θ is called planar iff the centers of all of its cells are coplanar. It can be shown that the intrinsic diameter of a nonplanar simple 2-arc is defined by a unique polygonal arc. For a given M_θ, these MLP-based length estimates are uniquely defined, but they may depend on the value of θ.

10.1.5 Tangent-based estimation

Arc length estimates can also be based on estimated tangents; see Equations 8.1 and 8.18 for the 2D and 3D cases. Figure 10.6 shows an example. An 8-path is traced along, for example, the “upper” alternating sequence of 0-cells and 1-cells of its grid cell representation. For each 1-cell, we estimate normals n₁ and n₂ at its endpoint 0-cells, using a DSS or MLP method to find straight line approximations to the 8-path on both sides of the 1-cell. Let n₀ be the unit normal to the 1-cell, and let n = (n₁ + n₂)/2. We use (n, n₀) = n·n₀ as an approximation to Evidently, such a tangent-based length estimate depends on how the normals are estimated and combined. The normals can also be used to estimate the curvature of the path at the 1-cell.

In this chapter, we will study estimates of the arc lengths or curvatures of 2D digital arcs or curves, particularly with respect to their multigrid convergence; for 3D curves, see Chapter 11. Statistic properties of digital arcs and curves can also be studied; see Section 1.2.11.

10.2.1 Local estimators

Local estimations were historically the first ones used for arc length estimation in picture analysis. These estimators were applied to digital curves defined by digitization methods (i) or (ii) in Section 10.1.1.

Local estimators are based on shortest paths in a weighted adjacency grid of pixels. The weights are chosen to approximate Euclidean distance; see the discussion of chamfer metrics at the end of Section 3.2.3.

To make arc length estimates as accurate as possible, it has been suggested that statistic analysis be used to find weights that minimize the mean square error between the estimated and true length of a straight line segment. This leads to the definition of a best linear unbiased estimator (BLUE, for short) for straight line segments. One such estimator [281] is as follows,

(10.1)

where n_i is the number of isothetic steps and n_d the number of diagonal steps in the digital arc or curve. (The subscript “chm” refers to the chessboard metric d₈.) Similar estimators have been proposed in [104] for chamfer distances (e.g., coefficients 0.95509 and 1.33693 for isothetic and diagonal steps for chamfer distances using a 3 × 3 neighborhood). Another local estimator [1115] is the cornercount estimator (coc, for short), where n_c is the number of odd-even transitions in the chain code of the digital arc or curve:

(10.2)

Algorithms for calculating these local estimators are straightforward: trace a digital curve and locally update the estimator’s value.

10.2.2 DSS estimators

Section 9.6 reviewed algorithms for DSS recognition. These algorithms decide whether a given sequence of grid points is a DSS; some of them also segment a digital arc or curve into a sequence of maximum-length DSSs. A length estimator E_DSS is then defined by the length of the resulting polygon or polygonal arc. For example, algorithm DR1995 (for 8-curves) defines the E_8ss estimator, and algorithm K1990 (for 4-curves) defines the E_4ss estimator. Note that the segmentation into DSSs is not uniquely defined; it depends on the method, the chosen starting point, and the direction in which the arc or curve is traced.

[283] defined a most probable original (mpo) length estimation method for DSSs that has superlinear convergence O(r^−1·5); it is multigrid convergent for grid-intersection digitization and for the class of all straight line segments γ. Let n be the length of the DSS ρ_h,8(γ) = i(0),…, i(n−1), and let a/b be the best possible rational estimate of its slope. (Formally, b is the length of the shortest period, which is the smallest k ∈ {1,…,n} such that k = n or i(m + k) = i(m) for 0 ≤ m ≤ n – k −1. a is the height difference in one period; for example, if i(m) ∈ {0,1} for all 0 ≤ m ≤ n − 1, then a = i(0) + … + i(q − 1).) Then we have the following:

(10.3)

In [283], this estimator was limited to single straight line segments, but it also defines an 8-DSS-based arc length estimator 8mp: apply the 8-DSS segmentation algorithm DR1995 and sum the mpo length estimates of the 8-DSSs.

10.2.3 MLP estimators

In MLP-based length estimators, a simple 1-curve ρ is described by two isothetic polygons γ₁ and γ₂ that are the frontiers of sets S₁ and S₂ such that S₂ is contained in the interior of S₁ and ρ is contained in . Here γ is defined by digitization method (iii) in Section 10.1.1, and S₁ and S₂ are and , with the constraint that γ₁ and γ₂ are at Hausdorff distance 1 with respect to L_∞. We find an MLP that is contained in B and circumscribes γ₂; the E_mlp length estimate is then the length of this (uniquely defined) MLP.

We will describe two MLP-based length estimators. The standard MLP estimator E_mlp defines B to be the difference set between the outer and inner Jordan digitizations of S. The approximating-sausage estimator E_aps also involves a parameterδ (0 <δ ≤ 0.5/h).

10.2.4 MLPs of simple 1-curves

We assume that γ₁ and γ₂ are traced in the positive orientation (i.e., counterclockwise in a righthand coordinate system). A vertex v_i on γ₁ or γ₂ is called a convex vertex if the frontier makes a positive turn at v_i (i.e., D(v_i−1, v_i, v_{i + 1}) > 0 [see Equation 8.14]). Similarly, v_i is called a concave vertex if the frontier makes a negative turn (D(v_i−1, v_i, v_{i + 1}) < 0) and a collinear vertex if D(v_i−1, v_i, v_i+1) = 0.

Our algorithm traces γ₁ (or γ₂), detects convex and concave vertices, puts their coordinates into a list L, and marks them as convex or concave. For simplicity, assume that the coordinates are integers. The coordinates of two successive vertices with indices i and i + 1 satisfy |x_{i + 1} – x_i| + |y_{i + 1} –y_i| = 1.

It is easy to show that only convex vertices of the “inner ” curve γ₂ and only concave vertices of the “outer ” curve γ₁ can be vertices of the MLP. There exists a mapping from the set of all concave vertices of γ₂ onto the set of all concave vertices of γ₁ such that each concave vertex of γ₁ corresponds to at least one concave vertex of γ₂. See Figure 10.7 for an example. The numbers denote successive vertices in the list L; 1 is a start vertex (i.e., an already known MLP vertex); 3 and 5 are successive convex vertices on γ₂; 2, 4, and 6 are successive concave vertices on γ₁. Vertex 7 is not between the negative (black line) and positive (white line) sides of sector (6,1,5); therefore 5 is the next MLP vertex and is a new start vertex.

The algorithm starts by putting all of the vertices of γ₂ into L. We then replace each concave vertex of γ₂ in L with its corresponding concave vertex of γ₁ by modifying its coordinates by ±1, where the sign depends on the orientations of the incident edges. L now contains all of the vertices that will form the MLP. Note that the vertices in L are still in the original vertex order on γ₂.

Suppose we already know that vertex v_i of L is an MLP vertex. Then v_j (j > i) can be an MLP vertex only if all convex vertices such that i < k < j lie on the positive side of (v_i, v_j) or are collinear with it (i.e., D(v_i,, v_j) ≥ 0). Similarly, all concave vertices such that i < l < j must lie on the negative side of (v_i, v_j) or be collinear with it. (Otherwise (v_i, v_j) would cross either γ₁ or γ₂, which is not allowed to happen.) Suppose a convex vertex v ⁺ and a concave vertex v⁻ both satisfy these conditions. When we consider a vertex v as a candidate MLP vertex, the following situations can occur:

In case (1), v + becomes the next MLP vertex. In case (2), v becomes a candidate for the MLP and must replace either v ⁺ or v⁻ depending on the sign of v. In case (3), v⁻ becomes the next MLP vertex. This is also correct in the trivial case where v ⁺, v⁻,or both coincide with v_i. Thus we can start with a vertex v₁ that is known to be an MLP vertex (e.g., the uppermost-leftmost vertex of γ₂); set v ⁺ and v⁻ equal to v₁; and then test all subsequent vertices as just described. Whenever the next MLP vertex is detected, it becomes a new start vertex.

The algorithm is given in Algorithm 10.1; it also provides a length estimate L.

If we are given a simply connected 4-component in the grid point model, the 4-path through all of the 8-border points of S defines the inner frontier γ₂. We can expand γ₂ into an outer frontier γ₁ at Hausdorff distance 1 from γ₂ (with respect to L_∞) and use γ₁ and γ₂ as inputs for the MLP algorithm. Figure 10.8 shows that the algorithm can handle “narrow concavities.” The resulting MLP intersects all of the invalid edges of S.

Figure 10.8 also illustrates how the algorithm proceeds. The top left shows an example of the set between γ₁ and γ₂. The top right shows the original sequence

of 8-border points as a dark curve (γ₂); the bottom left shows the curve that connects all convex vertices on γ₂ and concave vertices on γ₁ in the order tested in the algorithm; and the bottom right shows the resulting MLP. The algorithm has linear time complexity.

10.2.5 The approximating sausage approach

Let the h-frontier of S be represented by Π = (v₀, v₁…, v_n−1) where the vertices are in clockwise order and the interior of S lies to the right. We define the forward shift f (v_i) of v_i as the point on the edge (v_i, v_{i + 1}) at distanceδ from v_i, and the backward shift b(v_i) of v_i as the point on the edge (v_i−1, v_i) at distance δ from v_i.

To generate the approximating sausage “around” Π, for each edge (v_i, v_{i + 1}), we define the line segment (v_i, f(v_{i + 1})) that joins v_i to the forward shift of v_{i + 1}; this is referred to as the forward approximating segment and is denoted by L_f (v_i). The backward approximating segment (v_i, b(v_i−1)) is defined similarly and denoted by L_b(v_i). We now have three sets of edges: the original edges of the h-frontier and the forward and backward approximating segments. Using these edges, we define a connected region that is homeomorphic to an annulus as follows:

Given a polygonal circuit Π that describes an h-frontier in clockwise orientation, by reversing Π, we obtain a polygonal circuit Π⁻¹ in counterclockwise orientation. In the initialization step of our approximation procedure, we consider Π and Π⁻¹ as the external and internal bounding polygons of a polygon Π_B that is homeomorphic to the annulus. This initial polygon Π_B has area 0, and its points coincide with those of ϑ_h(S).

We now “move” the external polygon Π “away” from G_h(S) and the internal polygon Π⁻¹ “into” G_h(S), as described below. (The Hausdorff distance between Π and Π⁻¹ is nonzero when the sets are not identical.) This process expands Π_B step by step into a final polygon that containsϑ_h(S), and such that the Hausdorff distance between Π and Π⁻¹ is always less than or equal to 1/h. For this purpose, we add forward and backward approximating segments to Π and Π⁻¹ to increase the area of Π_B.

In the “moving” process, for any forward or backward approximating segment L_f (v_i), or L_b(v_i), we first remove the part lying in the interior of the current polygon Π_B and update Π_B by adding the remaining part of the segment as a new frontier edge. The orientation of this edge is chosen so that the interior of Π_B lies to the right of it. The resulting polygon is referred to as the approximating sausage of the h-frontier and is denoted by (see Figure 10.9, left, for δ = 1/2). Note that the width of the approximating sausage depends on δ. An aps approximation of the frontier of S is a shortest closed curve that lies entirely in the interior of and encircles the internal frontier of (see Figure 10.9, right). It follows that is uniquely defined and is a polygonal curve defined by finitely many straight line segments. Note that depends on the choice of δ; we have used δ = 0.5/h in our experiments.

10.2.6 Tangent-based estimators

We can use a tangent vector integration process to estimate the length of a curve; see Equation 8.1. Let be the length of the tangent vector associated with γ(t). Then the following can be approximated by using discrete estimates of the products dt:

(10.4)

To estimate the normals n₁ and n₂ (see Figures 10.6 and 10.10), we regard the 0-cell as the center point p of a maximum-length DSS of the 8-curve that is obtained by tracing one frontier of the digitized (in the grid cell model) curve γ. A centered maximum-length DSS always has even length. The estimates can also be based on 4-DSSs that approximate the 4-curve of the chosen frontier. Figure 10.10 shows a DSS approximation on the left and a 4-DSS approximation on the right.

The DSS (or 4-DSS) approximates the tangent line to γ, and the normal is perpendicular to this line. This method can make use of any DSS definition and recognition algorithm. Straightforward application of a linear online DSS recognition algorithm starting at p and proceeding alternatingly in both directions along the curve leads to an solution, where n is the number of pixels on the curve.

An optimization method proposed in [323] allows us to compute all of the discrete tangents in linear time by using the discrete tangent computed at each vertex to initialize the discrete tangent at the next vertex; on average, this requires only a constant number of changes. We will use DSS approximation of the outer frontiers of simple 0-curves. The discrete version of Equation 10.4 is as follows, where S is the set of all pixels in dig_h(γ):

(10.5)

For each 1-cell c in the alternating sequence of 0-cells and 1-cells along the chosen frontier, we calculate n(c) and n₀(c).

10.3.1 Online and offline algorithms and time complexity

The notions of online, offline, and linear time apply to estimators of all four classes; we describe them here for DSS estimators (see Section 9.6). An offline DSS algorithm takes an entire arc or curve (defined by a finite word u ∈ A^*) as input and decides whether it is a DSS. An online DSS algorithm reads successive chain codes i(0), i(1),…; for each n, it decides whether i(0),i(1),…, i(n) is a DSS; if not, it initializes a new DSS with i(n − 1)i(n). After a maximum-length DSS has been found, its length estimate (usually the Euclidean distance between its end vertices) is added to the length estimate of the arc or curve. An offline algorithm is linear iff it runs in time (i.e., it performs at most basic computation steps for any input word u ∈ A^*). An online algorithm is linear iff it performs on the average a constant number of operations for each chain code symbol.

10.3.2 Multigrid convergence theorems

We apply the general definition of multigrid convergence (Definition 2.10) to the problem of estimating the length L(γ) of an arc or curve γ. Assume that the estimate E is defined for all curves γ in a given class (e.g., the class of all simple curves in the Euclidean plane) and for all digitizations dig_h(γ) where h > 0. E is multigrid convergent to L with respect to digitization model dig_h iff E(dig_h(γ)) converges to L(γ) as h → ∞ for any curve γ in the class of interest. More formally, we have the following:

(10.6)

where lim_h→∞ κ(h) = 0; the speed of convergence is .

In general, we expect that an increase in grid resolution will result in an increase in accuracy. Suppose the digitization of a straight line segment consists of all cells that have nonempty intersections with the segment (i.e., we use outer Jordan digitization; see Figure 10.11). If the grid resolution is h > 0, the Hausdorff distance between the segment and the frontier of its outer Jordan digitization is . Hence the frontier converges to the segment with respect to the Hausdorff metric generated by the Euclidean metric. However, the perimeter of the union of the cells remains constant as h increases; this shows that this perimeter cannot be used for length estimation.

The local estimators chm and coc of the lengths of digitized arcs or curves (see Section 10.3) are not multigrid convergent. No proof has yet been published that local estimators cannot achieve multigrid convergence for “sufficiently complex” input data (e.g., not just for isothetic rectangles).² Given an algorithm for constructing a DSS approximation of the h-frontier of a simply connected digital set G_h(S), we define ε_DSS/h as the maximum Hausdorff distance between and γ_h:

(10.7)

(This theorem is from [560]; for a proof, see Section 10.3.3.) The value of h₀ depends on the given set. If ε_DSS (h) = 1/h, it follows from Equation 10.8 that the upper error bound for DSS approximations is as follows³:

(10.9)

In [883], a DSS is assumed to be a finite 8-path. When we use cell complexes, it is appropriate to consider a finite 4-path to be a DSS iff its main diagonal width is less than ; see [20, 597, 848].

Both of the MLP-based arc length estimators described in Section 10.2 (mlp and aps) are known to be multigrid convergent for convex Jordan curves γ.

There are several convergence theorems for MLP approximations in [1005]. The perimeter of such an approximation is a convergent estimator of the perimeter of a bounded convex smooth or polygonal set in the Euclidean plane. The following theorem is basically from [1005]; it specifies the asymptotic constant for mlp perimeter estimates.

From Theorems 10.1, 10.2, and 10.3, we see that the DSS upper error bound 4·5/h is smaller than the aps upper bound 5·844/h, which is in turn smaller than the mlp upper bound 8/h. However, this does not imply anything about the relative size of these errors. The determination of optimum error bounds remains an open problem.

The speed of convergence and the maximum error bound for these estimates have not yet been determined.

10.3.3 Proof of Theorem 10.1

To prove Theorem 10.1, we use two lemmas from integral geometry [958].

We recall that an ε-sausage of a curve γ (as originally discussed by H. Minkowski [732]; see Figure 7.2) is the set of all points ρ such that d_e({p}, γ) ≤ε.

We now prove Theorem 10.1. We assume that S is h-compact for h ≥ h₀, so G_h(S) is connected, and the DSS approximation of is a single (connected) polygonal curve. We will prove that there exists a constant h₁ ≥ 1 such that the following is true for all h ≥ h₁:

(10.12)

Suppose this Hausdorff distance was greater than . Then there would exist either (A) at least one point p on with a minimum Euclidean distance to that is greater than or (B) at least one point q on ϑS with a minimum Euclidean distance to that is greater than .

In case (A), the circle with centerρ and radius would not contain any point of ϑS; hence this circle would be either (A1) disjoint from S or (A2) completely inside of S. Let p be on the frontier of a grid square with midpoint . The grid point is inside the circle. In case (A1), it follows that cannot be in S (i.e., is not in G_h(S)). It follows that p cannot be on ϑ_h(S), which contradicts our assumption. In case (A2), p is on an h-edge incident with two h-squares with midpoints that are both in the circle and thus in S; hence, in this case, too, p cannot be on ϑ_h (S). Thus case (A) is impossible.

In case (B), because S is h-compact for h ≥ h₀, the distance between q and the nearest grid point can become arbitrarily small as h → ∞, while G_h(S) still remains connected. Thus, in case (B), we must increase h so that h ≥ h₁ ≥ h₀ for some h₁, which represents the situation in which the minimum Euclidean distance from q ∈ to is less than or equal to . Only a finite number of vertices on the frontier of S can require such increases in h₀. This concludes the proof of Equation 10.12.

Equations 10.12 and 10.7 and the triangle inequality for Hausdorff distance imply the following:

Let . Then the perimeter of S and the length of γ_h differ by at most 2πε. To show this, let γ_h be the frontier of a convex (polygonal) set C so that the following is true:

(10.13)

We will show that the following is true, which will complete the proof of the theorem:

(10.14)

The frontier lies in the ε-sausage of the frontier . Let be the outer frontier of the ε-sausage of . By Lemma 10.1, we have the following:

By Lemma 10.2, we have the following:

Hence, the following is true:

(10.15)

lies in the ε-sausage of , because Hausdorff distance is symmetric. Let be the outer frontier of the ε-sausage of . By Lemma 10.1, we have the following:

By Lemma 10.2, we have the following:

Hence, the following is true:

(10.16)

From Equations 10.15 and 10.16, we have the following

which proves Equation 10.14 and thus the theorem.

10.3.4 Experimental evaluation

Comparative evaluations of length estimators should investigate their accuracy and stability both on convex and nonconvex curves. In the experiments reported in [206], we used the test curves shown in Figure 10.12 digitized on grids of sizes between 30 × 30 and 1000 × 1000 using any of the three digitization methods in Section 10.1.1.

Two performance measures were used: (i) the relative error (in percent) between the estimated and true curve length; and (ii) for the DSS and MLP methods, a tradeoff measure defined as the product of the relative error and the number of generated segments (the efficiency of convergence).

In the plots in Figure 10.13, convergence is evident for all of the estimators. However, for estimators chm and coc, the convergence is to a false value! The errors are calculated for each curve, combined into a mean error for each grid size, and then the plots are generated by taking sliding means over 30 grid sizes. We show both linear and logarithmic plots of the errors. 8mp slightly overestimates the length as compared with 8ss.

The tradeoff measure is plotted in Figure 10.14 for the DSS and MLP estimators. Here, too, the errors are calculated for each curve and combined into a mean error for a given grid size, and the plots are generated by taking sliding means over 30 grid sizes.

As an additional test, a square of fixed size was rotated in a grid of resolution 128. Figure 10.15 shows its estimated perimeter as a function of rotation angle. Except for chm and coc, the estimates are relatively orientation-independent.

Figure 10.16 shows the runtimes of the DSS and MLP estimators as compared with local estimators. Obviously, the local estimators are fastest. MLP as implemented in [555] (as described in Section 10.2.3) is the fastest global estimator, but 4ss and 8ss come close to it. The aps estimator has not yet been optimized; faster implementations may be possible. Theoretically, the tan estimator has a linear asymptotic runtime implementation [323], but the estimator that was tested had quadratic runtime; optimization is needed here, too.

These experiments show that the local estimators are not multigrid convergent even for our simple test data set. For the five global estimators, we obtained experimental confirmations of known theoretic convergence results.

Interestingly, the runtimes of the polygonal DSS and MLP estimators were only slightly greater than those of the local estimators; hence the use of local estimators is not justified by a runtime argument. The choice of a global estimator may depend on the available software. Studies involving more extensive test data might be useful in the selection of the most efficient estimator for a given application.

All of the tested estimators have linear online complexity. Of all of the possible MOP extensions of the DSS and MLP estimators we have reported only on 8mp. Our theoretic studies answered (in most cases) the following questions:

multigrid convergence: Is the estimator multigrid convergent at least for convex curves? (If so, we are also interested in its convergence speed.)

discrete: Does the core of the estimation algorithm deal only with integers?

unique: Is the result independent of initialization (starting point, tracing orientation, and so forth)?

3D extension: Can the estimator be extended to digital curves in 3D space?

Table 10.1 provides a summary of the answers to these questions. Convergence speed is known to be linear for 8ss, 4ss, mlp and aps; see Theorems 10.1,10.2,10.3, and 10.4.

10.4.1 Corner detectors

Curvature analysis is often oriented toward detecting high-curvature pixels (“corners”). We first review two early methods that detect such pixels without calculating curvature estimates.

10.4.2 Curvature estimators

Curvature can be estimated from (C1.1) the change in the slope angle of the tangent line (e.g., relative to the x-axis); (C1.2) derivatives along the curve; or (C1.3) the radius of the osculating circle (circle of curvature); see Definition 8.1, Equation 8.9, and Equation 8.11, respectively.

10.4.3 Experimental evaluation

[661] contains an experimental comparison of several curvature estimation methods (see Sections 10.4.1 and 10.4.2) that were published before 1990 as well as some other local methods (see the references in Section 10.6). The results obtained from algorithm BT1987 were described as being “in best correspondence to human perception.”

We illustrate comparative evaluations for only two algorithms, CMT2001 and HK2003. The curvature of a circle of radius R is κ = 1/R. Figures 10.18 and 10.19 show the error averaged over all pixels on 8-curves that are the borders of Gauss digitizations of disks x² + y² = r² or x² + y² = r² + r (r = 100,…, 1000). The plots are sliding means, which eliminate “digitization noise” by symmetrically averaging 19 values before and 19 values after the current value r.

Figure 10.18 shows total errors for algorithms CMT2001 and HK2003, on the left for the digitized disk x² + y² = r² + r and on the right also for the disk x² + y² = r². In the latter case, the digital disk has small “peaks” on its border due to the fact that its radius is an integer. These “unsmooth” situations slightly increase the error for both algorithms.

Figure 10.19 shows how the errors behave if the unlimited-length DSS approximation in HK2003 is replaced by backward b_i,k and forward vectors f_i,_k of constant length (5 and 7 in the figure). The errors are smaller than for the global method up to about r = 100 for k = 5 and up to about r = 200 for k = 7.

[703] contains an extensive experimental comparison of corner detectors and curvature estimation methods; it demonstrates good performance of algorithm M2003 as compared with 28 other methods. We illustrate the experimental comparison in [703] by giving results obtained by five methods on two 8-curves (4-borders of 4-regions); Figure 10.20 shows these 8-curves.

Figure 10.21 shows corner or curvature values for the symmetric curve (which is of length 222) calculated by methods RJ1973 (with a = 0.1), FD1977 (with k = 9), BT1987 (with k_L = 9, k_U = 14, and b = 0.1), M2003 (with k = 10), and HK2003.

RJ1973 produces a “plateau” between border points 115 and 124. The original algorithm would label all of these points as being corners. In the resulting segmentation, which is shown in Figure 10.22 on the upper left, only the midpoint of this “plateau” is taken as a corner.

FD1977 reproduces the curve’s symmetry in the calculated values E_i,k. The original algorithm maps these into asymmetric corner positions; see the segmentation shown in Figure 10.22, which uses k = 9. The following modification would produce perfectly symmetric corners: select p_i as a corner iff E_i,k > E_j,k for all j such that |i – j| ≤ k.

A maximum of 14 corners was used for BT1987. No corners were detected by FD1977 at any of pixels 63 through 93 or 146 through 176.

Threshold 0.08 was used for corner detection in M2003. This algorithm also detects subsequences of corners that are “nearly collinear”; see the three corners on the left and on the right in Figure 10.22. Elimination of corners that are nearly collinear with the preceding and following corners would eliminate this type of redundancy.

Method HK2003 does not require any specification of parameters, but it depends on the orientation in which the border is traversed. The curvature values are not symmetric because a maximum-length DSS from p_i to p_j is not necessarily a maximum-length DSS from p_j to p_i. At each p_i, a “backward interval” and a “forward interval” are defined by backward and forward DSSs. A corner is detected iff the curvature at p_i is at least equal to the curvatures at every p_j in p_is backward and forward intervals.

Figure 10.24 shows corner or curvature values for the asymmetric curve in Figure 10.20 (which has length 223) calculated by the same five methods. The resulting segmentations are shown in Figure 10.23.

1. The Archimedes-Hui constant of a length estimation algorithm is the minimum grid resolution h₀ such that the algorithm initially estimates π within the error interval defined by Equation 1.6 when a circular region centered at the origin is digitized in a grid with edge length 1/h. Note that the estimates “oscillate,” so later estimates may be outside of this interval. Using a sliding mean is critical because the behavior of the errors is uncertain. Can you give a “better” definition of such a constant? Calculate the constants (using the above definition or an improved definition) for DSS and MLP length estimation methods.

2. Consider the inner and outer Jordan digitizations of a bounded connected planar set S and the MLP contained in the difference set of the two digitizations and circumscribing the inner digitization. Identify cases in which the grid-intersection digitizations of this MLP and of the frontier of S are (are not) the same.

3. In cases A and B in Figure 10.8, two border vertices are at distance 1 or 2 in the grid but at distance greater than 2 on the border 4-curve. Prove that the Algorithm 10.1 produces a grid polygon that circumscribes the inner polygon, even in cases A and B.

4. If two grid cells that share an edge e in a 2D multivalued picture P have values u and v, we say that e has strength |u – v|. The sum of the strengths of all of the grid edges in P is called the total frontier strength of P. Prove that, if P is binary, its total frontier strength is equal to the sum of the lengths (in grid edge units) of all of the frontier of P along which 0s meet 1s.

5. Implement algorithm M2003 and at least one other curvature estimation algorithm of your choice, and evaluate their performance as was done in Section 10.4.3.

6. Let ρ be a 4-path with pixels p₁,…, p_n that are all distinct. At each pixel p_i (1 < i < n), the path is either straight or makes a right or left turn, depending on whether the determinant D(p_i−1, p_i, p_{i + 1}) is zero, positive, or negative. In these cases, we say that the turn of ρ at p_i is 0, π/2, or −π/2, respectively;θ_i is the turn ofρ at p_i. If p₁ is a 4-neighbor of p_n (so that the path defines a closed curve), we can also define its turn at p_n (modulo n). Prove that the total turn of a closed curve is 2π.