Image Processing Reference
In-Depth Information
Definition 2.27. An N-Sequence B is well-behaved (wb) iff
B(i,j) ≻B(1,j) ∀i∀j,1 ≤i,j ≤p.
€
From [59], we present the functional form for d(u,v;B), the length of the
shortest N(B)-path, as a function of u, v, and B.
Theorem 2.13. The length of the minimal path from u to v determined by
B is denoted by d(u,v;B) = |Π
∗
(u,v;B)| and is given by:
n
max
d(u,v;B) =
i=1
d
i
(u,v)
where
a
i
f
i
(p)
d
i
(u,v)
= p
+ h(z
i
;B
i
)
p
j=1
a
i
+g
i
(j)
f
i
(p)
=
n−i+1
j=1
x(j)
x = (x
1
,x
2
,··· ,x(n))
such that x is formed by sorting |u
i
a
i
=
−v
i
|, 1 ≤ i ≤n, in non-increasing order,
that is, x
i
≥ x
j
for i < j:
B
i
= {b
i
(1),b
i
(2),··· ,b
i
(p)} such that ∀i,1 ≤i ≤ n,
b(j), b(j) < n−i + 2,
n−i + 1, otherwise
b
i
(j) =
j
k=1
b
i
(k), 1 ≤ j ≤ p,
f
i
(j) =
0,
j = 0
z
i
= a
i
mod f
i
(p)
h(z
i
;B
i
) = min{k : f
i
(k) ≥z
i
}; that is,
f
i
(h(z
i
;B
i
)− 1) < z
i
≤ f
i
(h(z
i
;B
i
)); and
g
i
(j) = f
i
(p)−f
i
(j −1)−1,1 ≤ j ≤p.
Proof. The proof is rather complicated [59]. It proceeds as in the case of d
m
(Section 2.3.1.1).
2.4.1.1
Necessary and Su
cient Condition for Metricity
Unfortunately, for all B's the corresponding d(B)'s do not sat-
isfy the metric (specifically, triangular) properties. For example, in 2-
D, d({1,2}) (octagonal distance) is a metric [182]. But d({2,1}) is not
a metric as it violates the triangle inequality for the points (0,0), (l,l)
and (2,2) with d((0,0),(1,1);{2,1})=1 and d((1,1),(2,2);{2,1})=1 but
d((0,0),(2,2);{2,1})=3 (>1+1).
In the following theorem (from [59]), we present a necessary and su
cient
condition on a B for the d(B) to be a metric.