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

.
Same as [STEP 1] except that the processing is applied to each column (the
sux i is replaced by the sux j ).
[STEP 3]
Input image:

Output image: G = { g ijk }

G = { g ijk } .

G = g ijk } .

Same as [STEP 1] except that the processing is applied to each plane (the
su x j is replaced by the su x k ).
[STEP 4]
Input image:

Output image: {

G = g ijk }

{ .

Output image: G = { g ijk } .

Binalize ,thatis,

for all ( i, j, k ) do
if g ijk > 0
then f ijk ←

G

1

else f ijk ← 0

endif
enddo

[Explanation of the algorithm]
The basic idea is almost the same as that of DT, except that it is what
is called a reverse operation. An input image is a skeleton image (although
not described as such), in which a voxel of a skeleton has a distance value
(a squared distance value in this case) and the other voxels are given the
value 0 . Algorithm 5.11 is in principle a formal description of the procedure
in Property 5.6. It is devised so that the range of the search for the maximum
may be reduced as much as possible. For details, see [Saito94b].
Suppose that a voxel P in an input image has the squared DT value f p .

Then the value of the squared RDT on a voxel at the distance d from P is at
most f p −

F

d 2 . This value is substituted subsequently to intermediate output

G .
For more detailed explanation, let us put d 2 = d i + d j + d k where d i , d j ,
and d k represent components of d 2 which are given by the difference between
the coordinate components in the i , j ,and k directions, respectively. Then
the value of f p −

G

images and

d 2 is not calculated directly. In this algorithm, it is obtained
subsequently according to the following order: f p − d i in [STEP 1], ( f p − d i ) d j

−

in [STEP 2], ( f p −

d i − d j ) − d k

in [STEP 3]. This part of the procedure is

illustrated in Fig. 5.14 (c) ∼ (e). Circles in Fig. 5.14 (a) show skeleton voxels

in an input image . Processing in Algorithm 5.11 is considered to arrange

parabolas so that their peaks come to the location of the mark

F

and to

obtain their upper envelope.
Negative values may be substituted temporarily into an output image as

is known from this figure. Then an original input image is derived by replacing
all positive values in

G

G by 0 . G by 1 and all the other negative values in

However, density values stored in the output image G when the process is