Image Processing Reference
In-Depth Information
board distances in 2-D and grid and lattice distances in 3-D into n-D space.
There are n distinct t-cost norms.
Definition 2.18. ∀n,n ≥ 1 we define a component-based distance function
d
p
,1 ≤ p≤ 2
n
−1 over Z
n
as
d
p
(u,v) = Σ
i=1
[b(i).f
i
(u−v)]
∀u,v ∈ Z
n
,
where
p = Σ
i=1
[b(i).2
n−i
] = [b(1),b(2),...,b(n)]
2
and 0 ≤b(i) ≤ 1,1 ≤ i≤ n.
€
2.3.2.1 Necessary and Su
cient Condition for Metricity
In Theorem 2.7 [58], we present the necessary and su
cient condition on
p, for d
p
to be a metric. Before proceeding with the theorem, we state the
condition for positive definiteness in Lemma 2.6.
Lemma 2.6. ∀n,n≥ 1, d
p
is positive definite iff 2
n−1
≤ p≤ 2
n−1
.
€
Theorem 2.7. ∀n,n ≥ 1 and 1 ≤ p ≤ 2
n
−1,d
p
is a metric iff p = [1
r
0
n−r
]
2
for some r,1 ≤ r ≤n.
€
Corollary 2.4. ∀n,n ≥ 1,d
p
is a non-metric iff 1 ≤p ≤ 2
n−1
−1.
€
Corollary 2.5. Define t-cost distance [58] D
t
: Z
n
× Z
n
→ P for n ∈
N,t ∈{1,2,3,...,n} as follows. ∀u,v ∈ Z
n
,
D
t
(u,v)
= d
p
(u,v),
for p = [1
t
0
n−t
]
2
Σ
i=1
f
i
(u−v).
=
€
From the preceding theorem D
t
is a metric, 1 ≤ t ≤ n, for all n. Actually,
the n t-cost distances are the only metrics in the general definition of (2
n
−1)
distance functions.
Corollary 2.6. ∀n,n ≥ 1, the number of d
p
's that are Metric, Non-Metric
and semi-metric are given by n (Theorem 2.7), 2
n−1
− 1(Lemma 2.6) and
(2
n
−1)−(2
n−1
−1)−n = 2
n−1
−n, respectively.
€
Note that if we allow p to be zero, then we get a trivial distance function
d
0
, defined as d
0
(u) = 0, ∀u ∈ Z
n
. It violates definiteness and does not have
any interesting property.
Now we illustrate the generalized distance, d
p
's in 2- and 3-D.
Example 2.11. Let n = 2:
d
1
(u)
=
min(|u
1
|,|u
2
|)
− Non
-
metric.
D
1
(u) = max(|u
1
|,|u
2
|)
d
2
(u)
=
− Chessboard distance.
D
2
(u) = d
1
(u) + d
2
(u) = |u
1
|+|u
2
| − City Block distance.
d
3
(u)
=
