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

[STEP 2] (Trace of border voxels of the background)
(1) Put S 0 into the work area TEMP. Give the mark M 0 to S 0 .
(2) Repeat the following until TEMP becomes empty.
Pull out one element P from TEMP. Extract from an input image all voxels
in the surface neighbor of P with the value 1 such that the mark has not been
given yet. Give them the mark M 0 and put them into TEMP.
(3) Go to [STEP 3]
[STEP 3] (Trace of voxels of a border surface)
(1) Put S 1 into the work area TEMP and the output array, and give a mark
M 1 to S 1 .
(2) Repeat the following until TEMP becomes empty.
Pull out one element P from TEMP. Extract all voxels in the surface neighbor
of P with the value M (S 0 ) such that they do not have the mark M 1 ;givethem
the mark M 1 , and put them into TEMP and an output array.
(3) Put a mark into the end of the output array in order to show the end of
border voxels sequence of one border surface. Go to (2) of [STEP 1] .
This algorithm has the following property.
Property 5.9 (Property of Algorithm 5.17).
(1) Coordinate values of border voxels are output for all border surfaces. Con-
tents of the output list are separated into individual border surfaces.
(2) One border voxel is output only once. If the same border voxel belongs to
more than one border surface, that voxel is written into the list the same
number of times as the number of border surfaces it belongs to.
(3) The adjacency relationship (connectivity relation) among voxels put into
the output list is represented in the form of a graph (or a tree).
(4) The algorithm is applicable to all four types of connectivity (6, 18, 18 ,
and 26 connectivity).
(5) An original input figure is restored exactly from the list of extracted border
voxels and starting voxel pairs (see Section 5.6.3 also).
Remark 5.19. The reason that the marking process is applied to the set
of 0-voxels here, in spite of the following of borders of 1-components, is that
different border surfaces should be traced separately. In Fig. 5.18, for example,
let us consider a figure P with a cavity Q , and let us assume that the thickness
of the figure P is one (one voxel width) at a voxel X. Then, both the border
surface B ( P, Q )and B ( P, Q ) share a voxel X. Unless a mark is given to 0-
voxels, two borders B ( P, Q )and B ( P, Q ) are not separated at the voxel X.
Thus, those two borders are traced continuously without being separated into
two border surfaces. If a mark is given to 0-voxels of Q , B ( P, Q )and B ( P, Q )
are followed separately as two border surfaces.ThevoxelXisvisitedand
output once for each border surface.