Image Processing Reference
In-Depth Information
Similarly, the upper boundary of Domain(D
o
) can also be formulated as
a pair of straight lines defined by (c
l
,m
u
), (c
QS
,m
QS
), and (c
u
,m
l
), where
Q = (h,y
h
+1), S = (h
′
,y
h
′
+1) (Fig. 3.7 ) , c
QS
= (h
′
y
h
−hy
h
′
+h
′
−h)/(h
′
−h)
and m
QS
= (y
h
′
−y
h
)/(h
′
−h).
Note that m
PR
= m
QS
. In Example 3.1, the domain is a quadrilateral with
vertices (c
l
,m
u
) = (1/2,1/2), (c
PR
,m
PR
) = (2/3,1/3), (c
u
,m
l
) = (1,1/4),
and (c
QS
,m
QS
) = (1,1/3) (Fig. 3.7).
In special cases, where Q and S (or P and R) coincide, the region Dom(D
o
)
becomes triangular because either (c
QS
,m
QS
) = (c
l
,m
u
) or (c
PR
,m
PR
) =
(c
u
,m
l
). This leads us to the following theorem.
Theorem 3.11. The domain Domain(D
o
) for a DSLS D
o
is a quadrilat-
eral, in general determined by the following vertices: (c
l
,m
u
),(c
PR
,m
PR
) and
(c
u
,m
l
), and (c
QS
,m
QS
)
€
Finally, we would like to highlight that there is a direct correspondence be-
tween the iterative refinement (I R) algorithm presented here and the analysis
formulated in other relevant works [78, 4, 134]. The crux of the analysis of dig-
ital straight lines lies in the identification of these four points: P, Q, R and S.
We get them from Theorem 3.11 as P = (g
′
,y
g
′
), Q = (h,y
h
+ 1), R = (g,y
g
),
′
and S = (h
,y
h
′
+ 1). It follows, then, that PS = (c
l
,m
u
), QR = (c
u
,m
l
),
and m
u
= α
+
, m
l
= α
−
, c
l
= e
+
and c
u
= e
−
in Dorst's notation [78]. Thus,
there exists a direct correspondence between the iterative refinement scheme
and the (n,q,p,s)-characterization.
3.2.4 Speed and Convergence of Iterative Refinement
The complexity of the I R algorithm to compute c
l
,m
u
,c
u
, and m
l
de-
pends heavily on the speed of convergence of the proposed iterative scheme.
The worst case time complexity of the iterative algorithm has not been proven
theoretically. However, with some modifications the complexity is reduced
drastically. In the following we state the modified algorithms, and present ex-
perimental evidence of reduction of complexity. The proof is left as an exercise.
In the algorithm presented in Theorem 3.6, in every iteration the values
of m
l
,m
u
,c
l
,c
u
are computed from the values of m
k−1
,c
k−1
l
,c
k−
u
. Let
us call this parallel I R algorithm. The first improvement in this algorithm is
to use the most recent estimate to compute the bounds of m and c instead of
computing all bounds in parallel for the same k. The resulting algorithm is
given in Algorithm 4.
The correctness of Algorithm 4 follows from the I R algorithm. It is also
noted that this sequential version improves the speed of the earlier algorithm
by approximately a factor of two!
Another heuristic may be suggested to achieve more speed. In this case,
when we compute m
k+1
l
,m
k−1
u
l
and c
k+
u
, we also tabulate i,j, where m
k+1
= (y
i
−
l
u
= (y
j
+ 1−m
k+
l
j) .
Then we calculate the gradient m and the slope c of the line joining the
c
u
)/i; and c
k+2
