Image Processing Reference
In-Depth Information
Chapter 1
Digital Topology: Fundamentals
1.1
Tessellation of a Continuous Space ..............................
2
1.2
Digital Grid ......................................................
3
1.2.1
Jordan's Theorem on Closed Curves ....................
4
1.3
Grid Topology ....................................................
5
1.3.1
Component Labeling ....................................
6
1.3.2
Containment .............................................
7
1.3.3
Boundary and Interior ...................................
9
1.3.3.1
Contour Tracing ........................... 10
1.3.3.2
Chain Code ................................ 10
1.3.3.3
Neighborhood Plane Set (NPS) ............
11
1.4
Topology Preserving Operations ................................. 14
1.4.1
Skeletonization ........................................... 14
1.4.1.1
Extended SPTA (ESPTA) for 3-D Images
16
1.4.2
Adjacency Tree .......................................... 21
1.5
The Euler Characteristics ........................................ 22
1.6
Summary ......................................................... 25
Exercises ......................................................... 25
The conventional geometry of our surrounding space is Euclidean. Strictly
speaking, it is the geometry in a three-dimensional Euclidean space. If we
restrict the geometry in a plane (e.g. the floor of a building) it turns out to
be two dimensional Euclidean space. Again if a person is conservative enough
to take into account of the curvature of earth, the 2-D planar floor is not
strictly the Euclidean one. One may approximate it more accurately to the
Riemannian space, which consists of the points lying on a spherical surface
and the distances between two points are computed by the length of the arc
defined by the circle with center and radius that are the same as those of the
sphere.
A digital image is usually defined in two dimensions. Each element or pixel
of the image has integral coordinate positions, contrary to the respective 2-D
Euclidean space, which is continuous and has infinite points in the neigh-
borhood of any point in the space. This indicates that the geometry in the
image space is a non-Euclidean one. One must study this geometry and its
approximation to the Euclidean world. In general, the digital image space is
referred as the digital space. In this space, the points are represented by inte-
gral coordinate positions (for example, by row and column numbers). Hence,
1
