Image Processing Reference
In-Depth Information
upper bound. Hence, only the relative error is used as a measure of goodness
of digital approximation to Euclidean distance.
We quote the theorems below. The proofs are from [69].
Theorem 2.34. The absolute error a(u) is unbounded, that is, for all M ∈
R
+
,∃u ∈ Σ
n
such that a(u) = |E
n
(u) −d
m
(u)| > M.
€
Theorem 2.35. ∀m,n, 1 ≤m ≤ n,
r(u) <
n
REL
0
(m,n) = max
u∈Σ
n
m
.
€
Corollary 2.16. ∀n,∀m,1 ≤ m ≤ n,REL
1−4
(m,n) are all bounded. The
bounds are as follows:
√
m−1,1−
n
n+m
REL
1
(m,n) < max
1−
√
m
,1−
n
REL
2
(m,n) < max
< 1
n+m
√
m−1
√
n
n+2m
REL
3
(m,n) < max
m+1
,
< 1
√
m−1
√
n
REL
4
(m,n) < max
m+1
,
< 1
√
n
2
+2nm+2m
2
€
The upper bound on REL
0
(m,n) as obtained in Theorem 2.35 is rather
loose and tends to suggest that d
m
improves as m increases and equals n.
However, further analysis shows that this is not true, and REL
0
(m,n) indeed
minimizes for an m between 1 and n. The mathematics for it is complicated
[69]. Based on the analysis the authors present Table 2.12 for optimal choice
of m in low dimensions.
2.6.3 Error of Real m-Neighbor Distance
The above analysis of relative errors between d
m
extends naturally to the
case of δ
m
using real m. In addition, the absolute normalized error is also
bounded.
Definition 2.40. The maxima of absolute (normalized) error between δ
m
and
E
n
is defined as: A(m,n) =
|E
n
(x) −δ
m
(x)|/M =
|E
n
(x)−δ
m
(x)|/M
max
x∈R
n
,|x
i
|≤M
max
0≤x
i
≤M
A is independent of the point spread parameter M, where the spread is [0,M]
n
.
Hence, it is not a parameter in A().
