Image Processing Reference
In-Depth Information
Algorithm 2: TRACE(x, n, N(·)): Trace an N(·) path from 0 to x
Require: x ∈ Σ
n
and N(·) is isotropic and symmetric.
y ← x
length← 0
print x
while y = 0 do
// Next Point
Choose z ∈ Σ
n
∩Neb(y;N(·)) such that z is closer to 0 than y
// Update Length
length← length + δ(z−y)
// Update Point
y ← z
print y
end while
print length
2. d is a positive: d(u,v) ≥ 0.
3. d is a definite: d(u,v) = 0 iff u = v.
4. d is symmetric: d(u,v) = d(v,u).
5. d is triangular: d(u,v) + d(v,w) ≥d(u,w).
Note that the condition of being total is important because Π(u,v) may
not exist ∀u,v ∈ Z
n
, and hence d(u,v) may not be defined. Examples include
Bishop's Neighborhood N(Bishop) = {±1,±1} or Super-Knight's Neighbor-
hood (see Section 2.3.4, [72]).
If d violates one or more of (1) through (4), it is usually not of any interest
and it is called a non-metric. If d violates only (5), it is called a semi-
metric.
€
Though we primarily deal with the digital n-D space Z
n
, we at times
generalize the results for the real n-D space R
n
as well. The distance function
then is defined as d : R
n
× R
n
→ R
+
∪{0} and the Euclidean distance as
E
n
: R
n
× R
n
→ R
+
∪{0}. The notion of the metric property holds in a
similar manner over R
n
.
2.2.3.1
Distance as a Norm
The neighborhoods, paths, shortest paths, and associated distance func-
tions in this chapter are all translation invariant. That is, the choice of the
origin does not affect these notions in any way. ∀u
1
,v
1
,u
2
,v
2
∈ Z
n
with
|u
1
−v
1
| = |u
2
−v
2
|, every path Π(u
1
,v
1
) corresponds, point-by-point, with
a path Π(u
2
,v
2
) where the same neighborhood difference vector is used at
every step of the two paths. Hence, the sets of paths between two points are
