Image Processing Reference
In-Depth Information
where l is length of the leftmost run of n in the current straight edge, and
α(> 0) is the factor of relaxation. Clearly, on increasing the value of α, (q−p)
increases, giving more relaxation to the property R2. Thus, if α is high, then
fewer straight edges would be produced at the cost of an error of approxima-
tion; whereas, if α is low, then we obtain better information about the straight
edges at the cost of increasing their count.
4.4.4 Finishing the Edge Sequence
The boundary of an object in a gray-scale image is represented as
a sequence of straight edges, namely e
1
,e
2
,...,e
m
, with their vertices
v
1
,v
2
,...,v
m
being stored in order in a stack S. Note that the end point
of e
i
coincides with the start point of e
i+1
for i = 1,2,...,m − 1. Finally,
if the end point of e
m
coincides with the start point of e
1
, then the edges
e
1
,e
2
,...,e
m
form a closed polygon; otherwise, the extracted straight edges
make a poly-chain.
The vertices are popped from the stack S, one by one, in order to reduce
the number of straight edges defining the boundary of an object. If a sequence
of vertices, thus popped from S, are almost collinear, then they are combined
together to form a single edge. In effect, if e
i
,e
i+1
,...,e
j
be the maximal
subset of straight edges that are almost collinear, then these j−i+1 edges are
combined to a single edge. The process is repeated for all such maximal subsets
in succession to obtain a reduced set of (almost) straight edges corresponding
to the object boundary.
We have used the technique based on area deviation [210]. If p(x
p
,y
p
),
q(x
q
,y
q
), and r(x
r
,y
r
) are three consecutive vertices popped from S, then the
magnitude of area of the triangle pqr is
∆ =
1
2
|(x
q
y
r
−y
q
x
r
) + (x
r
y
p
−y
r
x
p
) + (x
p
y
q
−y
p
x
q
)|.
Now, for a tolerance of approximation, τ (= 2 as used in [168]),
4
if ∆ does
not exceed τ ·d(p,r), where d(p,r) is the distance between p and r, then the
two edges, p,q and q,r, are merged into a single edge, p,r.
4.5 Examples
Some typical examples of DSS and ADSS have been shown in Fig. 4.4. It
is evident from these examples that an ADSS is not only reasonably straight,
but also fewer in count while covering a digital curve segment compared to
4
τ = 2 implies that each of the dropped vertices is at most at a distance 2 from the
combined edge [210].
