Image Processing Reference
In-Depth Information
of them occurs singly (also refer to Theorems 4.3 and 4.2 in Chapter 4). A
number of algorithms for generating digital straight line segments have been
developed since then [34, 5, 6].
Apart from characterizing whether a given set of 2-D digital points is a
DSLS, there are two related problems.
1. To reconstruct a DSLS that gives us a CSLS whose digitization may
have produced it.
2. To compute the domain of a DSLS. The domain of a DSLS denotes the
set of all CSLSs whose digitization may have yielded the given DSLS.
In our subsequent discussion, we use the function dist(p,q) as a generic
notation for expressing distance between two geometric entities, where any
one of them could be a point, straight line, DSLS, digital planar segment
(DPS), and plane. We apply the common notion of our distances in Euclidean
geometry in respective cases. For example, dist(p,l) between a point p and
a straight line l denotes the perpendicular distance from p to l. Similarly for
dist(D,l) between a DSLS D and a straight line l, denotes the maximum of
dist(p,l) such that p ∈D. We define the following important constructs for a
digitization scheme.
Definition 3.1. Given a CSLS l, whose digitization produces a DSLS D, l is
called the pre-image of D, and D is called the digital image of l.
€
Definition 3.2. A support line (SL)(or support) of a DSLS is a continuous
line going through at least one point of the DSLS so that all other points of
the DSLS lie on one side of the SL.
€
Definition 3.3. Given a DSLS D, and a CSLS l that lies on a support of D
and dist(D,l) < 1, l is a pre-image of D. Such a support of D is called the
nearest support of a DSLS.
€
3.1.1 Computation of Support Line of DSLS
One of the most popular schemes of 2-D DSLS was presented by Kim and
Anderson [4]. In this section, we describe the concepts and results of their
work. Let us assume that a 2-D DSLS is obtained by the inner digitization
scheme and that the slope m of the corresponding CSLS lies between 0 and
1.
A DSLS D has two kinds of pre-images, one lying above and the other
below D as the pre-image (i.e., CSLS l) can be traversed in two different
directions in inner digitization. To find the nearest support of a DSLS, the
following result is useful.
Lemma 3.1. If D is a DSLS, then there exists a CSLS l such that D is the
digital image of l and l passes through at least two points of D [4].
€
