Image Processing Reference
In-Depth Information
FIGURE 3.6: Construction of a straight line which after digitization pro-
duces D
o
(Theorem 3.9). The nearest support line PR is also illustrated.
Reprinted from
Pattern Recognition Letters
, 12(1991), S. Chattopadhyay et al., A new method of analysis for discrete
straight lines, 747-755, Copyright (1991), with permission from Elsevier.
x is not an integer, D(FG) = D
o
. The same is true if (x,y) are integers and
y = y
x
. So, we deal with the case where x is an integer and y = y
x
+ 1.
Consider a point M
′
unit ordinate below M (Fig. 3.6).
′
′
Construct a line M
I with slope zero and a line M
J with slope π/4. The
′
two intersections are obtained on two sides of M
.
′
′
J as we are considering
0− 1 chain codes only. Now, it is possible to draw a CSLS L that lies in the
region traced by BMDEJM
No grid point exists in the triangle MM
I or MM
IA so that D(L) = D
o
.
€
Thus, if we take any m,m
l
< m < m
u
, we may draw at least one CSLS L
that lies in the region BMDEJM
′
′
IA producing the same digitization as D
o
.
Numerically this line can be found by a simple binary-search-like algorithm
that uses Theorem 3.8 to terminate. Similarly, we can compute one m for
reconstruction given a c, such that c
l
< c < c
u
. So, we can say that R
ul
is the
smallest rectangle containing the domain of D
o
.
3.2.3 Computation of Precise Domain of a DSLS
The reconstruction algorithm of the last section computes at least one
straight line with the given digitization. We are more interested in all values
of c,m parameters that allow for reconstruction. Next, we discuss computation
of the domain of D
o
.
We note that little modifications of the iteration equations of the last
section directly lead to the computation of Domain(D
o
), of which R
ul
is only
a tight bound. We present it in the next theorem after necessary lemmas.
Lemma 3.3. Suppose that D denoted by y
i
from 0 ≤ i ≤ n is a DSLS. For
