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

Remark 5.18. Considering that the skeleton is defined as a set of voxels from
which an original input figure is restored, it may be possible that the amount
of memory can be reduced by storing coordinate values of a skeleton and the
DT value (or the squared DT value) on it instead of an input image itself. That
is, the skeleton may become a tool of image compression. From this viewpoint,
the smaller number of voxels in a skeleton is desirable for saving memory space
requirement. Therefore, it becomes more important that a skeleton extraction
algorithm extracts a skeleton of a smaller number of voxels with reasonable
computation time and that the skeleton satisfies the restoration requirement
[Borgefors97, Nilsson97].
Let us assume that a cuboid of 5 100 voxels was given. Consider that

the fixed neighborhood DT of the 26-neighborhood was applied to this figure
and then local maxima were extracted. If an extracted voxel set contains all
voxels on the centerline of this cuboid except two voxels inside it from 5

× 5 ×

5
faces of both sides, then such a set of voxels satisfies all conditions of the
skeleton. All the known definitions of the skeleton will give such a result.
However, the original cuboid will be recovered from a set of voxels extracted
from the above skeleton every five voxels. Unfortunately such reduction of the
skeleton is dicult without a prior knowledge of the shape of a figure.
Concerning image compression, we need not adhere to the Euclidean DT.
Any of the fixed neighborhood DT, that is, the 6-, 18-, and 26-neighborhood
DT will work reasonably well, although the performance may vary a little
according to the shape of an input figure.

×

Next let us show an algorithm to extract a skeleton of the Euclidean DT
[Saito94b]. We will first give two definitions of skeleton used here.

F

Definition 5.8 (Skeleton 1). Given a squared Euclidean DT image =

{ f ijk }

( f ijk

S

of voxels ( i, j, k ) = square of an Euclidean DT value), a set

defined below is called a Euclidean skeleton 1 .

x ) 2 +( j y ) 2 +( k z ) 2 <f ijk and S = { ( i, j, k ) |∃ ( x, y, z ) , ( i − − −

u ) 2 +( y v ) 2 +( z w ) 2 <f ijk }

( u,v,w ) {

f uvw |

( x

− − −

= f ijk }

. (5.28)

max

Definition 5.9 (Skeleton 2). Assume that a squared Euclidean image F =

{ f ijk } ( f ijk = square of an Euclidean DT value) is given, then a set S of

voxels ( i, j, k ) defined below is called a Euclidean skeleton 2 .

x ) 2 +( j y ) 2 +( k z ) 2 <f ijk and S = { ( i, j, k ) |∃ ( x, y, z ) , ( i − − −

u ) 2 − v ) 2 − w ) 2 }

( u,v,w ) {

max f uvw − ( x − ( y − ( z −

u ) 2 − v ) 2 − w ) 2 } = f ijk − ( x − ( y − ( z − . (5.29)

The above Skeleton 1 means as follows:
Put at each voxel ( i, j, k ) in an input figure a 3D maximum digital ball
that is centered at ( i, j, k ) and that does not overflow an input figure. After