Medial Axis Transform - Digital Geometry in Image Processing - page 218

TABLE 6.4: Number of medial spheres for different objects.
Distance Function

Dumble Dumb-Cone Sph-Cone

{1} 31947 16356 4695

{112} 26995 15818 4652

{113} 25371 15696 4963

{12} 25253 15378 4509

{122} 23509 15278 4678

{123} 21813 14964 4625

{13} 22877 15046 4933

{133} 19941 14816 5037

{2} 21305 14210 5179

{223} 19825 13956 4961

{23} 19289 13646 4929

{233} 18025 13620 5107

{3} 15977 13020 5331

Reprinted from Pattern Recognition Letters , 21(2000), J. Mukherjee et al., Fast Computation of Cross-Sections of
3-D Objects from Their Medial Axis Transforms, 605-613, Copyright (2000), with permission from Elsevier.

6.6.3 Using Euclidean Approximation
We know that computation of the intersection with a Euclidean sphere
and the xy-plane is trivial. Suppose (t x ,t y ,t z ) be the center of an Euclidean
sphere of radius r. Its intersection with a plane parallel to the xy-plane at
z = k, is given by a Euclidean circle, whose center is at (t x ,t y ) and radius is

r 2 −(k−t z ) 2 . Hence, for computing the intersection with Euclidean MAT,
in the step 1a of the algorithm, it is required only to transform its center
instead of vertices of a polyhedron. Moreover, there is no need to compute
intersecting points and form a convex polygon from them in Steps 1b to 1d of
the algorithm. It is su cient to note the center and radius of the intersecting
circle as discussed above. The union of all such circles from the medial spheres
results in the formation of a cross-section of the objects. The same concept
can be extended to MATs of digital distances, assuming their spheres as Eu-
clidean. Naturally, the distances whose disks are closer to Euclidean disks,
should provide better results in this computation. A measure of the quality
of approximation is used in [152], which is discussed below. Let S d (i,j) and
S e (i,j) be the cross-section images computed from digital medial spheres us-
ing the algorithm CSUM and their Euclidean approximations as discussed
in this section, respectively. We define an approximation error E csect of the
computation as follows:

Σ i Σ j e(i,j)
Σ i Σ j S d (i,j)

E csect = ×100% (6.6)

1 if S d (i,j) = S e (i,j)
0, otherwise.

where e(i,j) =

In Table 6.5, typical values of E csect for computation of cross-sections us-
ing Euclidean approximation are reported from [152]. We note that for some
distance functions like {113}, {112}, and {12}, the values are small. In partic-