Image Processing Reference
In-Depth Information
Theorem 2.11. d
Knight
is a metric over Z
2
.
Theorem 2.12. ∀u,v ∈ Z
2
, d
Knight
(u,v) is the length of a shortest Knight's
path from u to v as defined by N(Knight).
Proof. Adopt Algorithm 2 for N(Knight) and proceed as in d
m
.
The Knight's move is non-proximal and somewhat atypical in digital geom-
etry. Yet, it has been extended in [72] as a Super-Knight's Distance with a
class of neighborhood sets N(Super−Knight) = {(±p,±q),(±p,±q)} where
p,q ∈ P and p ≥ q ≥ 1. d
Super−Knight
is a metric under certain conditions
(see Exercise 3) on N(Super−Knight) [72].
2.4 Path-Dependent Neighborhoods and Distances
In the last section, we relaxed various neighborhood conditions from O(m)-
neighborhood to get new distances besides d
m
. Specifically, we got t-cost dis-
tances by relaxing the unity cost criteria and the Knight's distance (albeit in
2-D) by diluting the proximal condition. In this section, we introduce a new
form of relaxation in terms of path dependence of neighborhoods while revert-
ing back to neighbors being separated by unity costs and being proximal. We
start with an example in 2-D.
Example 2.12. In 2-D, City Block distance uses O(1)- or 4-neighbors while
Chessboard distance uses O(2)- or 8-neighbors. The first one produces a dia-
mond as a disk that is too small for a circle while the second produces a square
that is too large. Rosenfeld and Pfaltz [182] suggested a compromise between
them as octagonal distance, where a path starts with an O(1) neighbor but
then O(1)- and O(2)-neighbors are used alternately along the path.
Such a path from (0,0) to (9,5) is shown in Fig. 2.7.
Octagonal distance results in octagonal disks that better approximate cir-
cles, Hence the name.
€
In [59], the notion of path dependence has been extended further by al-
lowing for arbitrary sequences of neighborhoods for arbitrary dimensions. We
call them hyperoctagonal distances and present their properties.
2.4.1 Hyperoctagonal Distance
We first need to formalize the mathematics behind sequences and provide
for necessary characterizations.
Definition 2.19. A finite sequence that consists of the first n natural num-
bers is called a Neighborhood Sequence (or N-Sequence) in n-D. It is
