Image Processing Reference
In-Depth Information
It is also easy to observe that such a pre-image of D is periodic in a sense.
This we state in the following theorem.
Theorem 3.2. Let D = {d
1
,d
2
,...,d
n
} be a DSLS and let l be a CSLS whose
digital image is D such that l contains at least two points of D. If d
i
and d
j
are successive such points, then d
i
and d
j
determine a period on D. That is,
if k = j −i, then dist(d
h
,l) = dist(d
h
+ k,l) for 1 ≤ h ≤ n−k [4].
€
The following theorem helps us to find a pre-image of D that passes
through at least two points of D.
Theorem 3.3. If l is a CSLS that is a pre-image of DSLS D and l contains
two points of D, then l is a segment of one of the nearest support of D.
€
Thus, we can make the following statement.
Corollary 3.1. If D is a DSLS, then there is at most one line above (below)
D that contains two points of D and also contains a CSLS that is a pre-image
of D.
€
All these results help us to find the nearest support of DSLS D by finding
a pre-image of D that passes through two points of D. Lemma 3.1 guarantees
the existence of at least one such pre-image, and Corollary 3.1 tells us that
there can be at most one above and one below D. We could, for example,
examine each edge of H(D), the convex hull of D, since any support that
contains two points of D must contain an edge of H(D).
But there may be many candidates if D is large. The following theorem
allows us to limit the search to one possible candidate on each side of D.
Theorem 3.4. Let D be a DSLS and let P = {v
1
,v
2
,..,v
j
.,...,v
n
} be the
vertices of H(D) listed in counter-clockwise order, where v
1
is the leftmost
point and v
j
is the rightmost point of D. If line segment (v
i
,v
i+1
) lies on a
pre-image of D, then the horizontal length of (v
i
,v
i+1
),1 ≤ i ≤ j is greater
than the horizontal length of all of D to the left of v
i
or to the right of v
i+1
. In
particular, (v
i
,v
i+1
) is the longest edge of H(D) below D. Similarly, if there is
an edge of H(D) above D that lies on a pre-image of D, then it is the longest
edge of H(D) above D [4].
€
For finding the convex hull of a planar set of digital points, a variation of
Graham's method [169] can be used. Once the convex hull is obtained, the
nearest support of a digital line segment can be algorithmically computed.
Such an algorithm has a time complexity of O(n). It is possible to have two
nearest support lines, one above the convex hull of the set of digital points
and another nearest support line below the said set. We also note that the
nearest support line above the digital point set, D, is also a pre-image of D if
an OBQ digitization scheme is used.
Since there are many CSLSs leading to the same DSLS, another pertinent
problem is to find the entire set of real line segments corresponding to a given