Image Processing Reference
In-Depth Information
2.7 Summary
In this chapter, we introduced the generalized notions of neighborhoods,
paths, and distances in n-D digital geometry [71, 54, 221] and provided a
generic framework for tracing shortest paths and proving the metricity condi-
tions [61]. We studied a number of classes of digital distances under this frame-
work; notably, m-Neighbor [60], t-cost [58], hyperoctagonal [59], weighted cost
[37] and weighted t-cost [150] distances. Properties of the hyperspheres [70, 58]
of these distances in terms of the vertices, volumes, surface areas, and shape
features were explored in depth and the hyperspheres were geometrically and
algebraically compared with their Euclidean counterparts. Estimations of er-
rors in distance measures [69, 55] between digital distances and the Euclidean
norm were presented to identify good digital measures. A number of interest-
ing and useful special cases of distances and approximations in 2-D and 3-D
were presented in the form of Knight's [67, 72], octagonal [56, 55, 63] and
weighted t-cost [150] distance. Results for more classes of distances like t-cost-
m-Neighbor distances [167] and anisotropic neighborhood [62, 141] distances
in 2-D are given as exercises (Section 2.7) below.
Though the shortest path algorithms for most of these distances are out-
lined (primarily for path construction and metricity proofs), we do not dis-
cuss the (chamfer) algorithms for computing the distance transform for them.
These are taken up in Chapter 6.
For lack of space, most of the results in this chapter are presented without
proof. The reader is encouraged to refer to the details in the references in the
text.
Exercises
1. Generalize Algorithm 2 to work for any pair of points u,v ∈ Z n . Note
that the algorithm as presented works only when the destination point is
0, and the source point u has all positive coordinates and the coordinate
values are ordered, that is u ∈ Σ n .
2. Formulate the shortest path algorithms for t-cost, Knight's, octagonal
and hyperoctagonal distances by adopting Algorithm 2.
3. Super-Knight's distance (Section 2.3.4) is defined by the neighborhood
sets N(Super−Knight) = {(±p,±q),(±p,±q)} where p,q ∈ P and p ≥
q ≥ 1. Show that [72] d Super−Knight is a metric iff N(Super−Knight)
is well-behaved, that is, (p + q) mod 2 = 1 and gcd(p,q) = 1.
Search WWH ::




Custom Search