Image Processing Reference
In-Depth Information
ing from
b
0
until
b
n
repeatedly. By doing this, the variable neighborhood dis-
tance determined by the length of the variable neighborhood minimal path is
given to a voxel of an output image. Strictly speaking, this should be proved
theoretically. For details see [Yokoi81, Toriwaki92].
Most of the process time is spent on the execution of [STEP 2]. Com-
putation time primarily depends on how many times [STEP 2] is executed.
It is dominated by the maximum of distance values and varies according to
an individual input image. However, it is only voxels in the neighborhood of
those updated in the previous iteration that a voxel value is replaceable during
the current iteration. Therefore, it is possible to reduce the computation time
by using a list in the same way as Algorithms 5.5 and 5.6. It is particularly
effective in the fixed neighborhood DT.
Remark 5.12.
Denoting the output image of the
k
times of iteration in the
above algorithm by
F
(
k
)
and the operation to calculate it from
F
(
k−
1)
by
Φ
(
k
)
,then
F
(
k
)
=
Φ
(
k
)
(
F
(
k−
1)
)
,k
=1
,
2
,...
(5.11)
F
(0)
≡
F
where
(input image)
Applying the serial composition of image operations presented in Sec-
tion 2.3 to the above image operation,
F
(
k
)
=
Φ
(
k
)
·
Φ
(
k−
1)
·
Φ
(
k−
2)
·
Φ
(1)
(
...
·
F
)
.
(5.12)
Since
Φ
(
k
)
=
Φ
,
∀
k
in the fixed neighborhood DT,
F
(
k
)
=
Φ
k
(
F
)
.
(5.13)
However, it is not so easy to derive a theoretically clear form of represen-
tation for the contents of
Φ
k
(
).
Let us consider the fixed neighborhood DT for the sake of simplicity, and
let us perform always
g
ijk
←
F
d
+
1
in [STEP 2] of Algorithm 5.9 and that
two cases
d
=
M
and
d
=
M
are considered separately. The final result is the
same as Algorithm 5.9. Denoted by
Φ
the minimum filter of the neighborhood
adopted there, the transformation from
F
(
k−
1)
to
F
(
k
)
is represented as
Φ
+I,
that is
F
(
k
)
=(
Φ
+I)(
F
(
k−
1)
)=
Φ
(
F
(
k−
1)
)+
F
(
k−
1)
,
∀
k.
(5.14)
Repeating this representation for all
k
,then
F
(
k
)
=(
Φ
k
+
Φ
k−
1
+
...
+
Φ
2
+
Φ
+I)(
F
)
.
(5.15)
This form of representation is common to both 2D images and 3D images.
Next, let us give the sequential type of algorithm for the fixed neighbor-
hood DT [Kuwabara82].
Algorithm 5.10 (Fixed neighborhood (
6
,
18
,
26
-neighborhood) DT
sequential type).
Search WWH ::
Custom Search