Image Processing Reference
In-Depth Information
TABLE 2.2: Illustrations for metric behaviour of transformed Euclidean dis-
tance in 2-D.
Transformed Function
Remarks
⌊e⌋, round(e), e
2
Violates triangularity
(1 −exp(−e(x,y)))
Is normalized (C
1
= 0 and C
2
= 1) and a metric
⌈e⌉
Integer approximated and a metric
In general the issue of the metricity of D is settled iff both σ and d are
known. Often this involves a lot of algebraic manipulations that are easily
avoided if a certain property of the transformation σ is known. Theorem 2.1
from [61] provides a characterization for the class of transforms σ which pro-
duce a metric D for any given metric d over any A.
Definition 2.14. σ is a Metricity Preserving Transform or MPT if for
all metrics d over any set A, D = σ◦d is a metric on A.
€
It may be noted, however, that if σ is not an MPT, we cannot say anything
regarding the metricity of D unless d is known. Depending on the choice of
d, D may or may not be a metric. It merely ensures that there exists at least
one metric d on some A (for example, E
2
on R
2
) for which D is not a metric.
Theorem 2.1. σ : R
+
∪{0}→ R
+
∪{0} is an MPT iff σ satisfies the following
conditions:
1. σ is total
2. σ(x) = 0 iff x = 0
3. σ(x) + σ(y) ≥ max
x+y
z=|x−y|
σ(z),∀x,y ∈ R
+
∪{0}
Proof. We prove the su
ciency first. Given a σ satisfying (1)-(3), a set A, and
a metric d on A, consider the metric properties of D = σ◦d.
Positive-definiteness: Clearly D : A × A → R
+
∪{0} and hence D(x,y) ≥
0,∀x,y ∈ A. Again D(x,y) = σ(d(x,y)) = 0 and if D(x,y) = 0, then,
σ(d(x,y)) = 0. By (2) then d(x,y) = 0 and x = y. Hence, D is positive-
definite.
Symmetry: D(x,y) = σ(d(x,y)) = σ(d(y,x)) = D(y,x),∀x,y ∈A.
Triangularity: Since d is a metric on A, from triangularity of d, we have
|d(x,y)−d(y,z)|≤ d(x,z) ≤ d(x,y) + d(y,z),∀x,y,z ∈A. So
D(x,y) = σ(d(x,y)) ≤
d(x,y)+d(y,z)
max
u=|d(x,y)−d(y,z)|
{σ(u)}.
