Image Processing Reference
In-Depth Information
F
=
{
f
ijk
}
: Input binary image
g
(2)
G
(2)
=
{
ijk
}
: Output image (distance transformation)
g
(0)
g
(1)
G
(0)
=
G
(1)
=
: Work array
Edges of these arrays are assumed to be filled with
0
.
{
ijk
}
,
{
ijk
}
[STEP 1]
(Initialization)
Initial value image
g
(0)
G
(0)
=
{
ijk
}
is given as follows.
for
all (
i, j, k
)s
do
if
f
ijk
=
1
then
g
(0)
ijk
←
M
(
M
is a suciently large integer)
else
g
(0)
ijk
←
0
endif
enddo
[STEP 2]
(Forward scan)
for
all (
i, j, k
)s
do
g
(1)
g
(0)
ijk
g
(1)
ijk
←
min
{
,
min
{
pqr
;(
p, q, r
)
∈
S
1
}
+
1
}
enddo
Concerning (
i, j, k
), use the scan mode (I) in Fig. 5.13 (a). The
S
1
is selected
as shown in Fig. 5.13 (i), (ii), and (iii) according to the 6-, 18-, and 26-
neighborhood.
[STEP 3]
(Backward scan)
for
all (
i, j, k
)s
do
g
(2)
g
(1)
ijk
g
(2)
ijk
←
min
{
,
min
{
pqr
;(
p, q, r
)
∈
S
2
}
+
1
}
enddo
Concerning (
i, j, k
), use the scan mode (II) in Fig. 5.13 (a). The
S
2
is se-
lected as shown in Fig. 5.13 (i), (ii), and (iii) according to 6-, 18-, and 26-
neighborhood.
5.5.6 Supplementary comments on algorithms of DT
Large numbers of papers and reports have been published on the DT of a 2D
image, including various types of transformation and diversity of applications
[Yokoi81, Toriwaki79, Toriwaki81, Toriwaki92, Jones06]. A chief motivation of
different algorithms was that the difference from the Euclidean distance was
significantly large in the DT using the simple 4-neighbor or 8-neighbor dis-
tance. Another reason was that a good algorithm of the Euclidean DT was not
known. Although this situation has remarkably changed after the algorithm
of the squared Euclidean DT had been developed about 1992 [Saito94a], such
traditional algorithms are still useful to understand basic properties of DT.
Let us briefly introduce here how those traditional algorithms are extended
to a 3D image:
Search WWH ::
Custom Search