Image Processing Reference
In-Depth Information
TABLE 2.5: t-Cost norms in 2-D and 3-D.
D
t
(u)
n
t
1
max(|u
1
|,|u
2
|)
2
2 |u
1
|+|u
2
|
1
max(|u
1
|,|u
2
|,|u
3
|)
3
2 max(|u
1
|+|u
2
|,|u
2
|+|u
3
|,|u
3
|+|u
1
|)
3 |u
1
|+|u
2
|+|u
3
|
Let n = 3:
d
1
(u) = min(|u
1
|,|u
2
|,|u
3
|)
− Non
-
metric.
d
2
(u) = max(min(|u
1
|,|u
2
|)), min(|u
2
|,|u
3
|), min(|u
1
|,|u
3
|) − Non
-
metric.
d
3
(u) = d
1
(u) + d
2
(u)
− Non
-
metric.
d
4
(u) = D
1
(u) = max(|u
1
|,|u
2
|,|u
3
|)
− Lattice distance.
d
5
(u) = d
1
(u) + d
4
(u)
− Semi
-
metric.
d
6
(u) = D
2
(u) = d
2
(u) + d
4
(u)
− A new metric.
d
7
(u) = D
3
(u) = d
1
(u) + d
2
(u) + d
4
(u) = |u
1
|,|u
2
|,|u
3
| − Grid distance.
€
In Table 2.5, t-cost norms in 2-D and 3-D are listed.
2.3.2.2 Length of Shortest Path
Theorem 2.8. D
t
gives the length of the shortest t-cost path between two
points. That is, ∀u,v ∈ Z
n
,
D
t
(u,v) = |Π
∗
(u,v;t : n)|.
Proof. Devise a shortest path algorithm for t-cost paths by adapting Algo-
rithm 2 and then proceed as in the case of d
m
(Section 2.3.1.1). For details
refer to [58].
2.3.2.3 Real-Valued Cost
An interesting and natural generalization to D
t
demands the cost param-
eter t to be a real value where mapping of D
t
is modified to D
t
: Z
n
×Z
n
→
R
+
∪{0}. Following the technique of analysis adopted so far, we prove the
property of D
t
for real t as well. It may be noted that, though the t-cost
neighborhood and the corresponding t-paths are defined primarily for integer
costs, they have immediate extensions to the real case. However, the functional
form of D
t
undergoes change, as stated in the following lemma.