Image Processing Reference
In-Depth Information
q
6 p+d), then the while loop (steps 10-19) is not executed, and the current
ADSS, L
(k
i
, ends with the truncated part of that run (truncated maximally,
i.e., up to length p + e, in Step 15 of the previous iteration) as its rightmost
run, r.
For checking (c2), however, we have to be more careful. For the second run
(i.e., the run immediately following l) of the current ADSS, (c2) is checked
(with respect to l) in Step 8. It may be noted that, if l−p > e, then (c2) is
not satisfied, and so the first two runs (l and its successor) trivially constitute
an ADSS by Step 7; because for two runs, we get only l and r (and no p or
q), and no relation is imposed between l and r to define an ADSS.
For the third and the subsequent run(s), if any, the corresponding
run length is stored in k (Step 10). If some (small enough) k violates (c2), then
that k is treated as r (steps 11-13), and the current ADSS ends with that run
as the rightmost run (of run length k), whereby the maximality criterion of
the ADSS is fulfilled. Otherwise, if k does not exceed the maximum possible
length of the rightmost run (checked in Step 14), then we consider k as a valid
run of the current ADSS (Step 14), else we truncate it to the maximum per-
missible length (p+e) as the rightmost run (Step 15). Note that, if k > p+e,
then k > q (for p + e > p + d > q), and Step 19 updates q to k, whence (c1)
will be false in Step 9 in the next iteration, and so, the ADSS will end here
with the (maximally) truncated part (p + e) as its rightmost run.
€
Time Complexity: Determination of the parameters (
n
,
s
,l) in ADSS-PARAMS
consists of two cases—the first one (Steps 2-5) being easier than the second
(Steps 6-16). In either of these two cases, the procedure searches linearly
in S for two distinct (but not necessarily consecutive) chain code values and
determines the parameters accordingly. As evident from the loop in either case,
the three parameters are obtained using only a few integer comparisons. The
number of comparisons is l + 1 for the first case, and that for the second case
is the number of characters in S until two consecutive non-singular characters
are found.
The parameters
n
,
s
,l obtained in ADSS-PARAMS are successively passed
through a number of checkpoints, as mentioned earlier, which take constant
time, as evident in Steps 3-8 of DETECT-ADSS. In Step 5 of DETECT-ADSS,
the first run length of
n
is measured immediately after the leftmost run length
of
n
, if any, and it starts from the first non-singular character out of the two
consecutive characters detected in ADSS-PARAMS. In Step 10 of DETECT-
ADSS, we have another simple (and silent) loop that determines in linear
time each valid run of
n
in S, the validity criteria being verified and up-
dated in Steps 9-19, each of these steps taking constant time. Hence, for
the ADSS, L
(k
i
, the algorithm DETECT-ADSS, together with the procedure
ADSS-PARAMS, takes linear time; wherefore the time complexity for extrac-
tion of all ADSS in S is strictly linear on the number of points in S.
