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.
Search WWH ::




Custom Search