Image Processing Reference
In-Depth Information
Border following has been a well-known problem in the process of a 2D
image. It is a processing to visit (follow) voxels on a boundary of a figure in
the direction given by the predetermined rule and to store their coordinate
values in the list [Rosenfeld82]. The borderline of a 2D figure is a 1D sequence
of voxels. If we start the following of a border at a particular pixel and go
forward clockwise (or counterclockwise), that is, seeing the inside of a figure
on the right-hand side (or the left side), we always come back to the starting
pixel after we have visited all border pixels. Thus, border following is a self-
evident process except for the process at several exceptional pixels such as a
crossing point and a branching point.
The situation is very different in a 3D figure. The border surface of a
3D figure is a 2D curved surface extending in 3D space, and a procedure to
visit all voxels on it is not easily found. Therefore, we first need to know the
method to visit all border voxels on a one border surface without missing
any of the border voxel and without visiting the same voxel more than once.
To achieve this, we use a kind of specific neighborhood relationship existing
between border voxels and we extract border voxels utilizing this relationship.
Let us define this neighborhood relationship. For the sake of convenience
of executing the algorithm, a special mark is given to a particular voxel. We
call this
mark value
of a voxel P and denote it by
M
(P). The explanation
below is based on [Matsumoto84, Matsumoto85].
Definition 5.10 (Surface neighborhood).
For a given voxel P
1
and an
integer
K
,wecallthesetofallvoxelsP
2
satisfying the following conditions
(i) and (ii)
surface neighborhood of
P
1
with the value
K
, and denote it by
NB
m
(P
1
,K
) (Fig. 5.17).
(i) P
2
∈N
[
m
]
(P
1
), if P
1
is a 1-voxel, P
2
∈N
[
m
]
(P
1
), if P
1
is a 0-voxel, where
m
denotes the type of connectivity shown in Table 4.1.
(ii) For two voxels
q
1
q
2
q
1
and
in positional relations shown in Fig. 5.17,
q
2
and
have density values different from P
1
and P
2
, and either of the
following (1) and (2) holds,
(1) Density value of
q
1
=densityvalueof
q
2
=
K
,where
K
=
0
,or
K
=
1
,
(2) The mark value of
q
1
,
M
(
q
1
) = the mark value of
q
2
,
M
(
q
2
)=
K
,
=
1
.
m
and
m
denote a pair of the type of connectivity shown in Table 4.1.
where
K
=
0
,and
K
Definition 5.11 (Border surface).
Given a connected component of 1-
voxels
P
(
m
-connected), and that of 0-voxels
Q
(
m
-connected),
the border
surface of
P
against
Q
, denoted by
B
(
P, Q
), is the set of all voxels in
P
such
that at least one voxel of
Q
exists in the
m
-neighborhood.
Definition 5.12 (Border voxel).
A border voxel of an
m
-connected com-
ponent consisting of voxels of the value
f
(=
0
or
1
) is a voxel that has at
least one voxel of the value
1
−
f
in its
m
-neighborhood.
Search WWH ::
Custom Search