Image Processing Reference
In-Depth Information
Chapter 4
Digital Straightness and Polygonal
Approximation
4.1
Digital Straightness .............................................. 129
4.1.1
Slopes and Continued Fractions ......................... 130
4.1.1.1
Analyzing a Continued Fraction ........... 133
4.1.2
Periodicity ............................................... 135
4.2
Approximate Straightness ........................................ 136
4.2.1
Extraction of ADSS ..................................... 138
4.2.2
Algorithm DETECT-ADSS .............................. 140
4.2.3
Error Points ............................................. 143
4.3
Polygonal Approximation ........................................ 143
4.3.1
Approximation Criterion ................................ 144
4.3.1.1
Cumulative Error .......................... 144
4.3.1.2
Maximum Error ............................ 145
4.3.2
Algorithm for Polygonal Approximation ................ 146
4.3.3
Quality of Approximation ............................... 146
4.4
Approximation on Gray-Scale Images ........................... 148
4.4.1
Commencing a Straight Edge ........................... 149
4.4.2
Exponential Averaging .................................. 149
4.4.3
Checking the Straightness ............................... 150
4.4.4
Finishing the Edge Sequence ............................ 151
4.5
Examples ......................................................... 151
4.6
Summary ......................................................... 154
Exercises ......................................................... 154
Digital straight segments (DSS) started gaining special attention since the
1960s from the viewpoint of their theoretical formulation [28, 86, 87, 166, 180].
Many interesting properties of DSS have been discovered in later periods by
various researchers, which are mostly related to the theory of words and num-
bers [7, 32, 117] and continued fractions [113, 115, 119, 143, 209]. With the pro-
liferation of digitization and vectorization of graphical objects and visual im-
ageries, uses of these properties have been investigated by different researchers
for different application-specific problems related with computer graphics and
image analysis. The most significant among these is to determine whether or
not a given digital curve segment S is a DSS, and its algorithmic solutions for
several defining criteria have been reported in the literature in the 1980s and
127
