Image Processing Reference
In-Depth Information
1.4 Topology Preserving Operations
Following the notations of a digital picture, we define here addition and
deletion operations [118] on the foreground point set. A deletion of a fore-
ground point of a picture implies turning the point into its background. Simi-
larly, an addition implies the reverse operation of bringing a background point
into the foreground. For a set of points X ⊂ S in a picture P = (U,m,n,S),
the deletion of X transforms it into a picture P
′
= (U,m,n,S −X). A dele-
tion (or addition) operation is topology preserving if it keeps the number of
connected components of foreground points and the number of holes in 2-D
(or cavities and tunnels in 3-D) the same. In [197], the criteria for a topology
a preserving deletion operation in 2-D is provided as follows:
Let P = (G
2
,m,n,S) be a two-dimensional digital picture. Then a subset
X of S can be deleted safely to get a picture P
′
= (G
2
,m,n,S−X) preserving
the topology of P if and only if:
1. each foreground component of S contains exactly one foreground com-
ponent of P, and
2. each background component of P contains exactly one background com-
ponent of X.
1.4.1 Skeletonization
If in 2-D a topologically equivalent picture P consists of only simple arcs
and closed curves, we call it a skeleton of P. Similar notion is extended to 3-D
with simple surfaces, simple closed surfaces, simple arcs, and simple closed
curves to define a skeleton of a 3-D picture. Let us consider the case of 2-D
skeletonization first. We define a point simple, if its deletion still preserves the
topology of the picture. A simple point can be characterized in various ways.
The following theorem [155, 175] states a characterization of simple points in
2-D.
Theorem 1.1. Let p be a non-isolated border point in a digital picture. Let
S be its foreground pixel set, and let S = S −{p}. Then the following are
equivalent:
1. p is a simple point.
2. p is adjacent to just one component of N(p)
S.
3. p is adjacent to just one component of N(p)−S.
€
