ALGORITHM OF BINARY IMAGE PROCESSING - Fundamentals of Three-Dimensional Digital Image Processing - page 157

It is not so easy to find a definition of the skeleton which is applicable to
all kinds of DT.

The skeleton has been defined differently in papers published in the past.
Here we employ the definition 5.5 (1) because we consider that the restoration
of an original figure is the most important property of the skeleton.

Remark 5.13. Let us consider a definition of the skeleton from a different
viewpoint from the above. The following properties were expected as desirable
properties of the skeleton.

(a) An original figure is fully recovered from a skeleton and distance values
on it (restorability).
(b) The number of voxels contained in a skeleton is minimum (minimality).
(c) A skeleton is close to a result of thinning. It is important that the skele-
ton has the same topological features (connectivity) as an input image
(topology preservation).
(d) An ecient algorithm exists to extract the skeleton and to restore an input
image (existence of an algorithm).

For any kind of DT known, no skeleton exists that satisfies all of the above
four requirements. In this text, we consider, for the moment, that the first of
the above is indispensable. In this case, it is easily known that there exists a
figure that does satisfy (b) but does not satisfy (c). Therefore, we do not take
into account the third requirement.
There has not been reported a skeleton that exactly satisfies both (b) and
(d), although reasonable algorithms exist to extract such skeletons that meet
both the restorability and the minimal requirements [Borgefors97, Nilsson97].
For example, let us assume that we extracted skeletons according to a suitable
definition. Then we put on all the skeleton voxels digital balls of the radius
which is equal to the distance value at each skeleton voxel. Then we eliminate
a ball that is completely covered by other balls. By this algorithm we can
reduce the number of skeleton voxels while keeping restorability of an original
figure [Borgefors97, Nilsson97].
The first requirement in the above means that the skeleton consists of
a relatively small number of voxels, although not always minimized. If we
require the minimality condition too strictly, an effective algorithm to obtain
it may not be found.
Let us assume that a skeleton

S

satisfying the restorability condition has

S ∗ that consists of

been obtained. Then a set of voxels and one more 1-voxel

selected arbitrarily from an input image still satisfies the above restorability
condition. In other words, an arbitrary voxel set that includes any skeleton
S

S

satisfying the restorability will again satisfy the restorability requirement.
Obviously such skeletons will be meaningless. Thus the minimality condition
will be significant in the sense that such a meaningless skeleton is excluded.