Image Processing Reference
In-Depth Information
any loss of information. This set of 4-tuple is called a faithful characterization
of a DSLS. As C
i
= ⌊
q
(i−s)⌋−⌊
q
(i−s−1)⌋, we can easily see that among
other lines, the line
L : y =
p
q
(x−s) +⌈
sp
⌉
q
is one pre-image of C. Note that L is analogous to the nearest upper support
line of C as described by Kim and Anderson [4]. We also observe that if we
shift L vertically upward by an amount
q
, then the new line L
′
hits some
points outside C. All lines that can be drawn in this corridor between L and
L
′
have the same digital image and hence the same chain code C. The line L
passes through at least one point (s,⌈sp/q⌉) belonging to the given digital set.
Let P be the leftmost point on L, which is also a member of the digitization,
and R be the rightmost such point. Similarly, L
1
′
passes through one or more
grid points that are outside the given digitization. Let Q and S be such points
on L
′
which are leftmost and rightmost, respectively. Dorst carried out the
entire analysis in the (x,y)-plane using n inequalities mi+c−1 < y
i
≤ mi+c
arising out of the equations y
i
= ⌊mi + c⌋ for i = 0 to n. He showed that the
feasible set of values for m ranges from the slope of the line QR to the slope
of the line PS (refer to Fig. 3.3). For a given value of m, the span of c was
also derived. The domain of D, which is the set of tuples (m,c) that satisfies
the given n equations, was formulated in [78] . For an illustration, consider
Fig. 3.3. The DSLS is 101110111. The points P,R and Q,S are shown. Any
straight line lying completely within the shaded region produces the given
DSLS.
Inspired by McIlroy [139] to use the Farey series in characterizing the
domain of a given DSLS D, Dorst reviewed his proof for domain to achieve an
elegant solution in [76]. In [76], Dorst carried out the analysis in the parametric
(c,m)-plane. He also defined a line parameter transformation (LPT). Using
this transformation, a line y = mx + c is converted to a point (c,m). Also,
a point (x,y) gets transformed to a line c = −mx + y and vice versa. The
transformation preserves the incidence relationship.
For CSLSs that are in the standard situation (i.e., 0 ≤ m ≤ 1, 0 ≤ c < 1)
and are enclosed in x = 0 to x = n , it is su
cient to consider the grid points
(i,j) such that 0 ≤ j ≤ i ≤ n (see Fig. 3.4). Let us consider a CSLS L. If
we change the parameter (c,m) of L, the corresponding DSLS D(L) would
not necessarily change. D(L) changes only when L crosses a grid point which
is critical. In the dual plane L is a point, and change in (c,m) of L means a
movement of that point. When L sweeps over a critical point in the primal
plane, the point representing L traverses the LPT image of the critical point.
Hence, Dorst's idea is to partition the (c,m)-plane by drawing LPT images
of the critical points (which in this case are all the grid points) into several
facets, which are shown in Figs. 3.5 (a) for n = 3 and 3.5 (b) for n = 4. He
quantitatively characterized the facets so constructed and proved that they
are triangular or quadrilateral and each facet can be identified by four unique
integers. Finally, he established that each facet stands for the domain of a
