Image Processing Reference
In-Depth Information
properties (R3 and R4, Theorem 4.3) of a DSS. For example, in Fig. 4.4, the
DSS are all exactly straight, whereas the ADSS are visually straight.
The concept of ADSS can also be used for an e
cient polygonal approxi-
mation. Since the set of ADSS provides an elegant and compact representation
of digital curve segments, it is very effective in producing approximate poly-
gons (or, polychains) using a single parameter. The whole process consists
of two stages: extraction of ADSS and polygonal approximation. The major
features are as follows:
• The detection of ADSS is based on chain-code properties; only primitive
integer operations, such as comparison, increment, shift, and addition
(subtraction) are required.
• Does not use any recursion, and thus saves execution time.
• To obtain the polygonal approximation, only the endpoints of ADSS are
required with a few integer multiplications.
• The actual approximation of a digital curve segment never oversteps the
worst-case approximation for a given value of a control parameter.
Several other methods [43, 44, 95, 220] have been proposed recently for (ap-
proximate) line detection. Most of the conventional parametric approaches are
based on certain distance criteria, usage of masks, eigenvalue analysis, Hough
transform, etc. In contrast, the ADSS-based method relies on utilizing some
of the basic properties of DSS for extraction of ADSS. Earlier algorithms for
approximating a given digital curve segment may be seen in [2, 8, 103]. Sev-
eral variants of this technique were proposed later [16, 17, 163, 188, 191].
The class of polygonal approximation algorithms, in general, can be broadly
classified into two categories: one in which the number of vertices of the ap-
proximate polygon(s) is specified, and the other where a distortion criterion
(e.g., maximum Euclidian distance) is used.
Most of the existing polygonal approximation algorithms, excepting a few,
have super-linear time complexities, for example, O(N) in [210], O(MN
2
) in
[163], O(N
2
) in [188] and [191], and O(N
3
) in [173], where M denotes the
number of segments, and N the total number of points representing the input
set of digital curve segments. A comparative study of these algorithms can be
found in [13, 223]. Further, in order to analyze curvature, most of them require
intensive floating point operations [3, 83, 89, 205, 219]. For other details, the
reader may look at [10, 80, 161, 210, 217, 183, 205, 224, 225]. The ADSS-
based polygonal approximation proposed in [13] uses only integer operations,
and yields a suboptimal polygonal approximation with linear time complexity
(see [13]).
4.2.1 Extraction of ADSS
In the algorithm DETECT-ADSS, designed for extraction of ADSS from
a digital curve segment S, we have used R1 along with certain modifications
