Image Processing Reference
In-Depth Information
Definition 5.3 (Distance transformation (DT)).
A process to obtain an
output image
D
=
{
d
ijk
}
given below from an input image
F
=
{
f
ijk
}
is
called
distance transformation
of an image
F
=
{
f
ijk
}
.
3D distance transformation:
F
=
{
f
ijk
}→
D
=
{
d
ijk
}
d
ijk
=min
{
d
((
i, j, k
)
,
(
p, q, r
));
f
pqr
=
0
}
,
(5.1)
where
d
(
××
,
××
) = distance between
××
and
××
,
if
f
ijk
=
1
,
=
0
,
if
f
ijk
=
0
.
An image
is also called
distance transformation
(sometimes it is called
distance field and distance map).
D
The distance transformation is defined as follows.
(i) A process to give each 1-voxel of an input image the shortest distance (or
the length of the shortest path) to the background (a set of 0-voxels).
(ii) A process to shave an input figure repeatedly by one layer in each iteration
and to give a value
k
to a voxel shaved in the
k
times of iteration.
Contents of DT depend on the definition of the distance function
d
(
∗∗
∗
,
∗∗∗
) in Eq. 5.1. Usually, the Euclidean distance and other suitable ones
among those presented in Section 4.9 are employed. The use of the squared
distance
d
2
(
∗∗∗
,
∗∗∗
) is acceptable instead of
d
(
∗∗∗
,
∗∗∗
)insomeof
applications. This is called
squared distance transformation
. Computation load
is significantly reduced by using the squared distance in the Euclidean distance
transformation. If the comparative relation in the size of the distance values
is a main problem, results will be the same for using the distance value and
the square of it. An example is the application for thinning presented in the
previous section.
The use of the Euclidean distance is most natural in practical applications,
but the algorithm is complicated. The distance transformation using the 6-
and the 26-neighbor distance can be performed by much simpler algorithms.
However, deviation from the Euclidean distance is large in these distance
metrics, and results become unnatural in some cases. In subsequent sections
we will introduce algorithms for both of them. Skeleton will be explained later
in detail.
Distance transformations using variable and fixed neighborhood distances
are called
variable
and
fixed neighborhood distance transformation
, respec-
tively. The fixed neighborhood DT is called often by the name of the distance
metric employed in it such as the 26-neighbor DT. In the case of the Euclidean
metric, we need not consider a path if we want to calculate a distance between
two points. A path was discussed in detail in Section 4.9.
Remark 5.10.
An algorithm to perform DT closely relates to finding a short-
est path. For instance, if we find the shortest 26-connected path from a set
of all 0-voxels to a 1-voxel P, the length of this shortest path gives the value
Search WWH ::
Custom Search