Image Processing Reference
In-Depth Information
owing to some unexpected values of l and r. The DSS properties R1-R4,
however, do not give any idea about the possible values of l and r (depending
on
n
). Further, in the algorithm for DSS recognition [50], l and r are not
taken into account for adjudging the DSS characteristics of a curve segment.
However, we impose some bounds on the possible values of l and r, in order to
ensure a reasonable amount of straightness at either end of an extracted ADSS.
The values of d and e are heuristically chosen so that they become computable
with integer operations only. Some other values, like d = ⌊(p + 3)/4⌋ and e =
⌊(p + 1)/2⌋, or so, may also be chosen provided the computation is realizable in
the integer domain and does not produce any undesirable ADSS. For example,
in Fig. 4.4, the curve S
5
has p = 1,q = 3,l = 12,r = 1. In our case (Eqns. 4.7
and 4.8), therefore, we get d = 1 and e = 1 resulting in a violation of (c2) by
l; thus S
5
will not be accepted as an ADSS.
To justify the rationale of c1 and c2, we consider a few digital curves, S
1
-
S
5
, as shown in Fig. 4.4. It is interesting to observe that, although each of S
1
and S
2
has the appearance of a digital line segment, they fail to hold all the
four properties of DSS simultaneously, as shown in their respective figures.
The curve S
1
violates R3, and the curve S
2
violates R4. However, they satisfy
R1, c1, and c2, and therefore each of them is declared as an ADSS. Similarly,
the curve S
3
satisfies R1-R4 and (c1, c2); it is both an ADSS and a DSS.
However, none of the curves S
4
and S
5
can be identified as a DSS or an ADSS
because of the violation of R2, c1, and c2.
4.2.2 Algorithm DETECT-ADSS
Algorithm 7 shows the algorithm DETECT-ADSS for extracting ADSS
from the chain code of each digital curve segment, say S
k
, stored in the list
S. This requires n
k
repetitions from Step 2 through Step 23, where n
k
is
the number of ADSS in S
k
. Let the ith repetition on S
k
produce the ADSS
L
(k)
i
. Recognition of L
(k
i
is prompted by finding its corresponding parameters
(
n
,
s
,l) using the ADSS-PARAMS procedure in Step 2 of DETECT-ADSS. This
is followed by checking/validating the following:
(i) Property R1: Step 4 and Step 10;
(ii) Condition (c1): while loop check at Step 9;
(iii) Condition (c2): on the leftmost run length l in Step 8 and Step 11, and
on the rightmost run length r in Step 14.
Proof of correctness: For each ADSS, L
(k
i
, we show that property R1 and
conditions (c1) and (c2) are simultaneously satisfied. We also show that L
(k)
i
is maximal in length in S
k
in the sense that inclusion of the character (
n
or
s
or any other in {0,
1
,...,7}) (or a substring of characters) that immediately
precedes or follows the part of the digital curve segment corresponding to L
(k)
i
in S
k
does not satisfy the ADSS property/conditions.