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.
Search WWH ::




Custom Search