Image Processing Reference
In-Depth Information
Lemma 2.7. ∀n ∈N, ∀t ∈R
+
, ∀x ∈ Z
n
,
⌊t⌋
D
t
(x) =
f
i
(x) + (t−⌊t⌋).f
⌈t⌉
(x).
i=1
€
Note that if t is integral, that is t = ⌈t⌉, the above reduces to Corollary
2.5. Moreover, D
t
is a linear combination of D
⌊t⌋
and D
⌈t⌉
. Hence we get,
Lemma 2.8. ∀n ∈N, ∀t ∈R
+
, ∀x ∈ Z
n
,
D
t
(x) = (t−⌊t⌋).D
⌈t⌉
(x) + (1 +⌊t⌋−t).D
⌈t⌉
(x).
€
Using this result, we prove the result similar to Theorem 2.7.
Theorem 2.9. D
t
is a metric over Z
n
and it gives the length of the shortest
t-path between two points, where t is any positive real cost.
€
2.3.2.4 t-Cost Distance in Real Space
Interestingly, the t-cost distance generalizes to the real n-D space.
Theorem 2.10. ∀n ∈ N, ∀t ∈R
+
, D
t
: R
n
×R
n
→ R
+
∪{0} is a metric.
€
We present further generalizations of this result as weighted t-cost distance
in Section 2.4.3.
2.3.3 Weighted Cost Distance
In general, computing the distance from each object grid point to each
background grid point in an image leads to very high computational cost. So
often the spatial consistency of a distance map is used to allow for propagation
of local information. This is known as chamfering and is discussed in Chapter
5. When using the chamfer algorithm, only a small neighborhood of each
grid point is considered. A weight, a local distance, is assigned to each grid
point in the neighborhood. By propagating the local distances in the two-scan
algorithm, the correct distance map is obtained. For example, City Block and
Chessboard distances are obtained by using unit weights for the neighbors.
Borgefors et al. [22, 23, 24, 25, 202] worked extensively on computational
aspects of digital distances using chamfering. Chamfering is used to compute
the distance maps of the distances discussed so far. In addition, it opens the
opportunity to define new measures through a linear combination of differ-
ence of coordinates of points (leading to different types of motion such as
vertical and horizontal motions in 2-D) and local weights. These are known
as weighted cost distances [37].
