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

a connected component of border voxels beforehand in order that the surface
neighborhood may be available. In this process it is enough that a border
is given a mark. The extraction and storing of border voxels to a list while
preserving the adjacency relation is not required here. This is performed by
simply applying the same border surface-following algorithm to a set of 0-
voxels.

5.6.2 Examples of algorithm

By integrating the above procedures, a border surface-following algorithm is
derived, which consists of the following three steps:

(1) search of a starting voxel,
(2) border surface following of connected components of 0-voxels (marking),
(3) following of a border surface B ( P, Q ).

Algorithm 5.17 (Border-surface following).

M 0 , M 1 : mark value for a 0-voxel and a 1-voxel.
(S 01 , S 02 ): Starting voxel pair. A pair of a mutually 6-adjacent 0-voxel S 0 and
a1-voxelS 1 which are on the same scan line (on the same row). We assume
that at least one of them has not been given a mark yet (Fig. 5.17).
TEMP: Work area. A cue or a stack that stores coordinate values of border
voxels. (In the subsequent part, the expression put a voxel into TEMP
simply means write coordinate values ( numbers of a row, a column and a
plane ) of a voxel into TEMP .)
Output array: coordinate values of voxels belonging to the border surface are
stored, being separated with a specific marker into each connected com-
ponent.
P: Temporary variable representing a voxel.
Scanning of an image: Raster scan (Fig. 2.13).
Input: A 3D binary image. A set of 1-voxels is regarded as a figure. A figure
is treated as an m -connected component ( m = 6 , 18 , 18' or 26 ).

[STEP 1] (Search of a starting voxel)
(1) M 0 ←−

1 , M 1 ←

1
(2) Scan an input image in the order shown in Fig. 2.13. Scan starts at the
voxel next to the previous starting voxel. Search an input image for a starting
voxel pair, that was shown in Fig. 5.17. Go to (3), if a starting pair was
detected. Stop, if the whole of an input image has been scanned.
(3) M 0 ← M 1 + 1

If S 0 of the starting voxel pair (S 0 , S 1 ) has a mark, go to [STEP 3] ;otherwise
go to [STEP 2] .HereS 0 is a 0-voxel and S 1 is a 1-voxel.

M 0 − 1 , M 1 ←

Note: Border following is reduced here to graph search. TEMP becomes a cue if
we adopt the width-first search, and becomes a stack if the depth-first search is
employed.