Image Processing Reference
In-Depth Information
Lemma 2.13. Proportional error is bounded over n-D space, that is, ∀n ≥ 1,
1 ≤t ≤ n ∃C
1
,C
2
∈R
+
such that ∀u ∈ Z
n
−{0}
C
1
.D
t
(u) ≤E
n
(u) ≤ C
2
.D
t
(u).
€
Theorem 2.38. ∀n, n ≥ 1, 1 ≤ t ≤n,
√
√
REL(t,n) = max
u∈Z
N
{r(u)} = max(
t−1,1−t/
n).
€
Optimal Choice of Cost
For every n, there are n different choices of the associated cost t, 1 ≤ t ≤
n. Every cost gives a corresponding maximum error REL(t,n). We want to
choose cost t
opt
in such a way that it minimizes the maxima of relative error.
That is,
n
min
t=1
REL(t
opt
,n) =
REL(t,n).
This choice of cost clearly gives the best D
t
. Interestingly, for all n the
value of t
opt
lies between 1 and 3. Hence the theorem from [58].
Theorem 2.39. ∀n, n ≥ 1, we have 1 ≤ t
opt
≤ 3.
€
√
√
Proof. Clearly, REL(t,n) minimises for the solution of
t− 1 = 1 −t/
n.
Here the right-hand side is < 1. Hence t < 4.
√
Example 2.19. For n = 2, REL(1,2) = 1 − 1/
2 = 0.2929 < 0.4142 =
√
2−1 = REL(2,2). Thus D
1
or Chessboard is better than D
2
or City Block
in 2-D.
For n=3, REL(1,3) = 1−1/
√
√
3 = 0.4226, REL(2,3) =
2−1 = 0.4142
√
3 − 1 = 0.7321. Thus, the newly introduced metric D
2
is
better than both D
1
or lattice distance and D
3
or grid distance in 3-D.
and REL(3,3) =
€
2.6.4.1
Error of t-Cost Distance for Real Costs
Finally, we present a result of the error estimate for real costs.
Theorem 2.40. ∀n ∈ N, ∀t ∈R
+
,
REL(t,n) ≤ (t−⌈t⌉).REL(⌊t⌋,n) + (1 +⌈t⌉−t).REL(⌈t⌉,n).
€
