Image Processing Reference
In-Depth Information
Fig. 5.25.
Digital knot of the length
26
and three crossing points.
a diagram that shows border lines of all Voronoi regions is called a
Voronoi
diagram
.
To calculate the Voronoi tessellation of a given 3D image, we first need to
define
d
(Q
,F
i
), the distance between a figure
F
i
andavoxelQ.Thefollowing
is a widely employed example.
d
(Q
,F
i
)=min
{
d
(Q
,
P); P
∈
F
i
}
(5.31)
= distance to the nearest voxel in
F
i
It is necessary to further determine the distance metric concretely. For
more detail, see [Mase81, Yashima83].
Some additional problems, which were not caused in 2D continuous images,
must be taken into consideration to calculate Voronoi tessellation of a 3D
image.
(1) Voronoi division surface (borders of Voronoi regions) is, in general, a sur-
face figure in 3D space. However, a large number of voxels may exist that
are equally distant from two or more figures. Then a Voronoi division sur-
face may become thick arbitrarily. The same situation may occur in a 2D
digitized image [Mase81, Yashima83, Toriwaki84, Toriwaki88].
(2) A Voronoi division surface may have a hole, depending on the distance
metric employed in its calculation.
(3) The shape of a Voronoi division surface (or dominate area) may become
extraordinarily complicated.
Calculation of the Voronoi tessellation is not dicult in principle. One
idea, for example, is to perform the labeling first, then to perform the distance
transformation of the background with propagating labels synchronously or
considering distance values if the 6-, 18-, or 26-neighborhood distance is em-
ployed. Different types of label propagation may be required in the case that
Search WWH ::
Custom Search