Image Processing Reference
In-Depth Information
2.3 Neighborhood Distances
We now present different distance functions based on neighborhood sets.
2.3.1 m-Neighbor Distance
From Euclidean geometry, we know that the length of the shortest path
(that is, a straight line between two points) is given by the Euclidean distance.
A similar result holds for O(m)-neighbor (Table 2.1) paths in digital n-D
geometry. O(m)-paths are denoted by Π(u,v;m : n). Examples in 2-D and
3-D are presented in Figs. 2.3 and 2.4.
We start with the closed functional form for this distance [60].
Definition 2.16. ∀m,n ∈ N and ∀u,v ∈ Z
n
, we define m-neighbor dis-
tance d
m
(u,v) between u and v as
n
k=1
|u
k
−v
k
|
m
max
k=1
d
m
(u,v) = max(
|u
k
−v
k
|,
).
€
Using the norm for this distance, we write d
m
(u,0) as d
m
(u) =
max(max
k=1
P
n
k
=1
|u
k
|
). Also, d
m
is used in place of d
m
(u,v) in cases
|u
k
|,
m
where no confusion arises.
Theorem 2.3. ∀m,n ∈ N, d
m
is a metric over Z
n
.
Proof. The proof follows from MPT (Theorem 2.1) given that max
k=1
|u
k
| &
n
k=1
| are metrics and scaling (1/m), ceiling (⌈·⌉) and maximum (max)
are MPTs (Table 2.3). An elaborate proof is given in [60].
|u
k
The above theorem suggests an infinite class of m-neighbor distances, each
characterized by some m ∈ N. This is an apparent contradiction as we know
that for n = 2 and n = 3 there are only 2 (d
4
and d
8
) and 3 (d
6
, d
18
and d
26
)
possible distances respectively. The following lemma removes this contradic-
tion by showing that infinitely many of these distances are necessarily same
and there are only n distances in n-D.
Lemma 2.3. ∀m,n∈ N, m > n and ∀x ∈ Z
n
, d
m
(x) = d
n
(x).
Proof. Show that ∀m,m ≥ n,d
m
(x) = max
i
|x
i
|.
Corollary 2.2. There exists exactly n number of m-neighbor distance func-
tions in n-D space Z
n
, given by d
m
(u,v) = max(d
n
(u,v),
d
1
(u,v)
m
) for
1 ≤m ≤ n.
€
