Simple points and discrete homotopy
Involved people : Gilles Bertrand, Michel Couprie,
Christophe Lohou.
A simple point is a point of an object which is such that its removal does
not modify the topology of the object (see fig. 2). This
concept is at the base of all the algorithms making it possible to
analyze an image according to topological criteria. We proposed in
a former work a necessary and sufficient condition allowing to
characterize the simple points in a cubic 3D mesh, within the
framework of digital topology. More concise and easier to evaluate
than the preceding characterizations, this characterization requires
only the search for two numbers of connected components which we called
topological numbers. In addition to the characterization of the
simple points, the topological numbers make it possible to carry out a
classification of the points according to their local topological
characteristics. Thus, it is possible to detect the points which have
locally the same topological characteristics as curve points,
surface points, points of intersection between surfaces, curves... We also
proposed several ways of calculating these two topological numbers;
for example, we showed that one can calculate these two numbers by
detecting the presence of certain configurations in the vicinity of
the considered point [ Ber96 ].
In addition, within the framework of the orders, we
introduced the new concepts of unipolar point and free point, which
are ``inessential'' elements from the point of view of topology. We
also introduced a discrete definition of homotopy and a generalization
of the concept of simple point [ Ber99 ]
: a point is regarded as simple if its vicinity, deprived of
itself, retracts in only one point (see fig. 3).
From these notions, some particularly elegant and effective parallel
algorithms of skeletonization can be derived (see the section ``3D skeletonization algorithms'').
| |
(A)
| (b)
|
Figure 2: (A): The central point is simple, (b):
the central point is not simple : if it is
withdrawn, a hole is locally created. If one withdraws this point of
the object (which can extend beyond the vicinity 3x3x3 shown here)
this will cause, either to create a hole in the object, or to remove a
cavity of the object (see also the section ``A 3D hole closing algorithm' ').
Figure 3: The central point (appeared by a cube) is simple
: its vicinity, deprived of itself (black elements), can
retract in a point.