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.
Search WWH ::




Custom Search