Image Processing Reference
In-Depth Information
segment. If we cut DSS(p,q) at any intermediate point r ∈ DSS(p,q), then
the sequence of digital points in DSS(p,q) from p to r may not be the same
as DSS(p,r); similarly, this difference may be observed between the sequence
of digital points in DSS(p,q) from r to q and DSS(r,q).
4.1.1 Slopes and Continued Fractions
In Sec. 3.1.2, a number-theoretic characterization of a DSS (or a DSLS)
is presented. In this section, we elaborate it further by elucidating the link
between the rational slope of a straight line and the chain code of its digital
image. We illustrate this relationship by using Euclid's famous algorithm for
expressing a rational number in the form of continued fractions.
We consider that the digitization process of a straight line is by the method
of nearest integral coordinates (NIC), as discussed in Sec. 3.1. This means that
given a real line l, its corresponding DSL is the sequence of digital points such
that the isothetic distance of each digital point p from l is at most
1
2 . The
isothetic distance of p(i,j) from l is given by min{|x−i|,|y−j|}, where (j,x)
and (i,y) are the respective (real) points of intersection of l with the horizontal
and the vertical lines passing through p. As mentioned earlier, a DSS is a finite
segment of a DSL, and hence it may be obtained by cutting the DSL at two
arbitrary digital points, namely p and q, and the cut-off DSS is very likely
to differ from DSS(p,q) obtained by digitization of the real line segment, pq.
Hence, given a digital curve segment as a sequence of digital points, S, we
cannot decide whether S is digitally straight simply by verifying whether S
is identical with the DSS formed by joining the endpoints (i.e., first and last
points) of S. Following the NIC digitization process, we formally define a DSS
as follows:
Definition 4.1. If p = (i p ,j p ) and q = (i q ,j q ), and without loss of generality,
if i p < i q and the slope of pq lies between 0 and 1, then for each vertical line
x = i with i lying in the integer interval [i p ,i q ], we have a unique pixel (i,j)
in DSS(p,q) where j is rounded off from the y-coordinate of the intersection
point of the real line pq with x = i. Hence, the set of points defining the DSS
from p to q is given by
(i,j) ∈ Z 2 | i p 6 i 6 j p ,j = round(y), y−j q
j q
= i−i q
i q
DSS(p,q) =
.
−j p
−i p
(4.1)
Clearly, given two digital points p and q, the subsequent DSS(p,q) involves
a mapping from R 2 to Z 2 . On the contrary, the problem related to digital
straightness is the reverse and involves the mapping from Z 2 to R 2 . For, given
the sequence of digital points constituting a digital curve segment S, its digital
straightness should be verified not only with respect to the real line segment
joining the terminal points of S, but also with respect to other line segments
Search WWH ::




Custom Search