Image Processing Reference
In-Depth Information
€
Example 2.6. Table 2.3 lists a number of MPTs. These follow from Theorem
2.1 and Corollary 2.1.
TABLE 2.3: MPT examples.
MPT
Non−MPT
⌈x⌉
⌊x⌋,round(x) = ⌊x + 0.5⌋
ax
b
, a > 0 and 0 < b≤ 1
ax
b
, a > 0 and b > 0
x
2
1−exp(−mx), m > 0
mx, m > 0
m
1
x/(m
2
+ m
3
x), m
1
,m
2
,m
3
> 0
ln(1 + x)
However, for a particular A and d, σ(d) may still be a metric. For example,
let σ = ⌊x⌋, A = R
2
, and d(x,y) = ⌈E
2
(x,y)⌉. Clearly, D(x,y) = σ(d(x,y)) =
⌊⌈E
2
(x,y)⌉⌋ = ⌈E
2
(x,y)⌉ is a metric even though ⌊.⌋ is not an MPT.
€
MPTs are combined to form new MPTs as the following lemma states.
Lemma 2.2. If g and h are MPT's, then g◦h, g + h and max(g,h) are also
MPTs.
€
Example 2.7. Using g(x) = ⌈x⌉ and h(x) = 1 − exp(−x), σ = g ◦ h =
⌈1 − exp(−x)⌉ is a normalized 0/1 approximation for any metric d. Since
∀x,y ∈ A, 0 ≤σ(d(x,y)) ≤ 1, we have
σ(d(x,y))
=
0
⇐⇒
x = y
=
1
⇐⇒
x = y.
€
Next we generalize by introducing MPTs with n arguments.
2.2.4.1 Generalized Metricity Preserving Transforms (GMPT)
Definition 2.15. Let σ
n
: (R
+
∪ {0})
n
→ R
+
∪ {0} be a transforma-
tion which combines n metrics d
1
,d
2
,d
3
,··· ,d
n
on A. Define D(x,y) =
σ
n
(d
1
(x,y),d
2
(x,y),...,d
n
(x,y)), ∀x,y ∈ A. σ
n
is a Generalized Metric-
ity Preserving Transforms or GMPT if D is a metric for every possible
choice of metric d
i
, 1 ≤i ≤n on any set A.
€
Theorem 2.2 [61] presents the GMPT condition by extending Theorem 2.1.