Image Processing Reference
In-Depth Information
Definition 4.13 (Variable neighborhood path).
Let
β
M
=
{
b
0
,b
1
,...,b
M−
1
}
(4.55)
denote a sequence of neighborhoods, where
b
i
is a suitable symbol showing
the kind of the neighborhood. Then a sequence of voxels
x
0
(=
u
)
,
x
1
,
x
2
,...,
x
K−
1
,
x
K
(=
v
)
,
(4.56)
x
i
+1
∈N
[
b
i
]
(
where
x
i
)
,i
=
0
,
1
,...,K
−
1
, is called a
variable neighborhood
x
i
+1
∈N
[
b
i
]
(
path
from
u
to
v
with the neighborhood sequence
β
M
.Here
x
i
)
means that
x
i
. Neighborhoods are employed
according to the order of the given neighborhood sequence
β
M
.If
M<K
,the
entire sequence
β
M
is employed repeatedly. In practice we use the following
three types most frequently:
β
M
x
i
+1
is in the
b
i
-neighborhood of
=
{
6
}
(6-connected path),
β
M
=
{
18
}
(18-connected path),
β
M
=
{
26
}
(26-connected path).
As these examples show, a variable neighborhood path includes the path
of Def. 4.12 as its special case. That is, if the neighborhood sequence
β
M
includes only one element, the variable neighborhood path reduces to the
path in Def. 4.12. This case we call
fixed neighborhood path
if we need to
distinguish it from the path in Def. 4.13. The minimal path is also defined for
a variable neighborhood path in the same way as Def. 4.12.
To find the length of the variable neighborhood minimal path from an
arbitrary voxel
for a given neighborhood sequence is
not simple. We show here an algorithm to obtain this for a neighborhood
sequence consisting of only the 6-, 18-, and the 26-neighborhoods [Okabe83a,
Okabe83b].
u
to another voxel
v
Theorem 4.5.
Suppose that two voxels
u
=(
i, j, k
)and
v
=(
p, q, r
), and
the neighborhood sequence
β
M
=
(where
b
i
=
6
,
18
,
26
for
all
i
s) are given. Then the length of the variable neighborhood minimal path
d
(
{
b
0
,b
1
,...,b
M−
1
}
u
,
v
;
β
M
) is calculated by the following equations:
d
(
u
,
v
;
β
M
)=max
{
d
1
(
u
,
v
)
,d
2
(
u
,
v
)
,d
3
(
u
,
v
}
,
)
(4.57)
where
d
1
(
u
,
v
)=
P
[
α
1
/Q
1
]+
h
(
z
1
,β
M
)
α
1
(
u
,
v
)=
|
p
−
i
|
+
|
q
−
j
|
+
|
r
−
k
|
Q
1
=
F
6
+
2
F
18
+
3
F
26
(4.58)
z
1
(
u
,
v
)=mod(
α
1
,Q
1
)
)=
P
[
α
2
/Q
2
]+
h
(
z
2
,β
M
)
d
2
(
u
,
v
Search WWH ::
Custom Search