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

Search the minimum above by changing n sequentially over the range ( 1 ≤

j + n ≤ M ) of an input image.

enddo

[STEP 3] (Corresponds to Transformation III)
Input image H = { h ijk } ,

Output image s ijk }

for all ( i, j, k ) do (Perform the following processing at each voxel)
s ijk ←

S = {

where r = h ijk
Search area for the minimum the same as in [STEP 2] .
enddo

−r≤n≤r {

h ij ( k + n ) + n 2 }

min

F

If an input image need not be preserved after the execution of the

F G , G H S

algorithm, images maybeassignedtothesamearray

on the computer. In [STEP 2], after the values of i , j ,and k are specified, a
list (1D array) is necessary for storing

, , ,and

{ g ijk ; 1 ≤ j ≤ M } . This is the same

in [STEP 3].
Details of the algorithm are shown in [Saito92, Saito93, Saito94a, Kato95]
with the range of search in [STEP 2] and [STEP 3] and faster algorithms.
Modifications for a parallelepiped voxel will be obvious.
Let us summarize properties of this algorithm:

(a) Squared Euclidean distance : This algorithm gives the squared Euclidean
distance transformation. Exact values of distances are easily obtained by
calculating the square root of suitable voxel values in the output image.
Only calculation among integers is used in the algorithm (square roots
appearing in the range of search in [STEP 2] and [STEP 3] are only for
saving the computation time). Exact calculation of them is not always
required.
(b) Amount of computation : Amount of computation in three transforma-
tions in the algorithm is estimated as follows.
(Transformation I) O (Num)
(Transformation II) O (average of square roots of voxel values in G ×

Num)
(Transformation III) O (average of square roots of voxel values in H ×

Num)
Here, O means the order and Num is the number of voxels in an input
image. If averages of square roots of voxel values in images

G H

are
large compared with image sizes M and N , the above estimation may not
be applicable, because the range of search is mostly determined by the
image size.
Assuming that the total amount of computation is approximated by
the sum of that of three transformation, and that square roots of voxel
values in

and

G and H are approximated by the square roots of the distance

transformation S multiplied by a constant, the total amount of computa-