Image Processing Reference
In-Depth Information
For digital distances, these weights are integers. The weighted distances
are defined as follows in low dimensions:
In 2-D:
d
2
<a,b>
(u,v) = a|u
1
−v
1
|+ (b−a)|u
2
−v
2
|
where a and b are positive integers and a ≤ b≤ 2a.
In 3-D:
d
3
<a,b,c>
(u,v) = a|u
1
−v
1
|+ (b−a)|u
2
−v
2
|+ (c−b)|u
3
−v
3
|
where a, b, and c are positive integers and b≤ 2a, b ≤c and a + c ≤ 2b.
The advantage of such distances includes ease of computation by cham-
fering, simple functional form, and the ability to approximate the Euclidean
norm fairly accurately. In [37], Borgefors et al. present their chamfering al-
gorithm as the Weighted Distance Transform (WDT). They also prove
various interesting results for face-centered-cubic (FCC) and body-centered-
cubic (BCC) grids in 3-D.
2.3.4 Knight's Distance
In the game of chess, the move of a knight has been particularly interesting
because of its tricky and non-proximal nature. If a knight is placed in the cell
x ∈ Z
2
, then in the next step it moves to any of the eight possible cells y,
where (y−x) ∈N(Knight) = {(±1,±2),(±2,±1)} (Fig. 2.1), where the cost
δ is taken to be unity. The notions of Knight's path and path length naturally
follow.
The Knight's distance d
Knight
(u,v) [67] is defined as: ∀u,v ∈ Z
2
,
d
Knight
(u,v)
=
max(⌈x
1
/2⌉,⌈(x
1
+ x
2
)/3⌉) + (x
1
+ x
2
)) if x= (1,0),(2,2),
−max(⌈x
1
/2⌉,⌈(x
1
+ x
2
)/3⌉) mod 2
=
3
if x = (1,0),
=
4
if x = (2,2),
where
x
1
= max(|u
1
−v
1
|,|u
2
−v
2
|), x
2
= min(|u
1
−v
1
|,|u
2
−v
2
|).
The distance between any two points is the number of steps taken to
trace a shortest path from one point to another. Hence, at every step on
a shortest path the larger coordinate (x
1
) of x should be decreased by 2,
whereas x
2
should be decreased by 1. This indicates the need for the first term
max(⌈x
1
/2⌉,⌈(x
1
+x
2
)/3⌉) in d
Knight
, where the ceiling function is introduced
to get the integral number of steps. The second term in d
Knight
is due to a
parity correction necessary for the motion at the final step to be defined. For
two points, namely (1, 0) and (2, 2), such a function does not hold due to the
peculiar nature of the motion. Thus they are explicitly defined. The proofs of
the functional form and the metric properties of d
Knight
are given in [67].
