Image Processing Reference
In-Depth Information
tion is given approximately as
O
(arrange of values of the DT
×
Num).
This result is confirmed in experiments [Saito94a, Saito94b].
(c)
Memory requirement
: When an input image is preserved after the execu-
tion of the DT, two arrays of the same size as an input image are required
for storing an output image and a work area. If an input image needs
not be preserved after the transformation and it is desirable to minimize
memory requirements, the algorithm can be executed using one 3D array
of the same size as an input image and one 1D array of the size max
(
M, N
). In this case, an input image, working area, and an output image
are all assigned to the same 3D array. A 1D array is necessary also as a
work area. This is one of the main advantages of this algorithm when a
very large 3D input image has to be processed.
(d)
Type of algorithm
: This algorithm is sequential in an approximate sense,
because it can be executed on one 3D array. However, this is not true, in
a strict sense, because the processing of [STEP 2] and [STEP 3] (search of
the minimum) is not always sequential. Since the range of search cannot
be fixed beforehand and depends on input data, the algorithm is of the
data-dependent type. Thus it cannot be regarded as the local processing.
One-dimensional decomposition is achieved because it is represented as a
serial composition of three 1D processing, each of which is performed in
each coordinate axis direction. Thus this algorithm cannot be classified
into a well-defined execution type. It is not yet clear how it is advantageous
in hardware implementation. Implementation of the squared Euclidean
DT on a parallel-type computer was discussed in [Miyazawa06, Hirata96].
Next let us introduce a parallel-type algorithm of the Euclidean DT.
Algorithm 5.8 (Euclidean distance transformation - parallel type).
Input image:
F
=
{
f
ijk
}
Output image:
G
=
{
g
ijk
}
(distance transformation)
for
all (
i, j, k
)
do
radius of the maximum ball which has the center at (
i, j, k
)and
does not contain a 0-voxel inside it, if
f
ijk
=
1
,
0
,
if
f
ijk
=
0
,
g
ijk
←
enddo
In order to find the maximum radius of a ball we need to perform a kind of
search procedure. Although various shortcuts may be possible in this process,
much computation time is still necessary. If the width of a figure is small
everywhere, this type of algorithm may be useful.
Remark 5.11.
An algorithm has been developed in which a coordinate value
of the nearest 0-voxel is propagated. This propagation does not always cor-
respond to a path introduced in Section 4.9. The algorithm is implemented
by a kind of iterative procedure. Examples of such algorithms for a 2D image
were given in [Yamada84, Danielsson80], and the extension to a 3D image was
Search WWH ::
Custom Search