Image Processing Reference
In-Depth Information
88
-
8
-
8
+
88
+
8
-
8
+
(
a
)
(
b
)
Fig. 5.15.
Illustration of skeleton or Euclidean DT [Saito94b]: (
a
)Skeleton1;(
b
)
skeleton 2.
all such balls have been placed, select a ball that contains at least one voxel
that is not covered by other balls. Then a set of centers of such balls gives a
desired skeleton (Fig. 5.15 (a)). This skeleton corresponds to the skeleton in
Def. 5.5 (1) and (4).
In the second case (Skeleton 2), a skeleton is generated by using a solid
constructed by an image plane and a parabolic cylinder with the axis per-
pendicular to an image plane. This cylinder is placed on a figure so that its
bottom surface (circle) does not surpass the border of an input figure. This
circular bottom surface is centered at each voxel and its radius is equal to the
distance value at the voxel. After all of such cylinders have been placed on
possible voxels, select such parabolic cylinders that at least one point of the
surface of the solid exists that is not covered by other cylinders (Fig. 5.15 (b)).
Then a set of all center voxels on which the above selected parabolic cylinders
were placed gives the Skeleton 2 defined in Def. 5.9. This skeleton satisfies the
restorability requirement. The number of voxels in Skeleton 2 may become
smaller than that of Skeleton 1. This point has not been discussed in depth.
The following algorithm has been developed to extract Skeleton 1 and
Skeleton 2 [Saito93, Saito94b, Toriwaki01].
Algorithm 5.15 (Extraction of Skeleton 1 of Def. 5.8).
Input image
F
=
{
f
ijk
}
: Squared Euclidean DT image.
Output image:
: Skeleton image. Initial value is
0
for all voxels.
In the output, the value
1
is given to skeleton voxels, and
0
is given to
other voxels.
Work arrays:
H
=
{
h
ijk
}
X
{
x
ijk
}
Y
{
y
ijk
}
Z
{
z
ijk
}
R
{
r
ijk
}
=
,
=
,
=
,and
=
:Initialvalue
is
0
for all voxels in all arrays.
for
all (
i, j, k
) such that
f
ijk
>
0
do
for
all (
p, q, r
) such that (
p
i
)
2
+(
q
j
)
2
+(
r
k
)
2
<f
ijk
do
−
−
−
if
r
pqr
<f
ijk
then
x
pqr
←
i
y
pqr
←
j
Search WWH ::
Custom Search