Thinning-free Polygonal Approximation of Thick Digital Curves Using Cellular Envelope

Since the inception of successful rasterization of curves and objects in the digital space, several algorithms
have been proposed for approximating a given digital curve. All these algorithms, however, resort to
thinning as preprocessing before approximating a digital curve with changing thickness. Described in this
paper is a novel thinning-free algorithm for polygonal approximation of an arbitrarily thick digital curve,
using the concept of “cellular envelope”, which is newly introduced in this paper. The cellular envelope,
defined as the smallest set of cells containing the given curve, and hence bounded by two tightest (inner and
outer) isothetic polygons, is constructed using a combinatorial technique. This envelope, in turn, is analyzed
to determine a polygonal approximation of the curve as a sequence of cells using certain attributes of digital
straightness. Since a real-world curve=curve-shaped object with varying thickness, unexpected disconnectedness,
noisy information, etc., is unsuitable for the existing algorithms on polygonal approximation, the
curve is encapsulated by the cellular envelope to enable the polygonal approximation. Owing to the implicit
Euclidean-free metrics and combinatorial properties prevailing in the cellular plane, implementation
of the proposed algorithm involves primitive integer operations only, leading to fast execution of the algorithm.
Experimental results that include output polygons for different values of the approximation parameter
corresponding to several real-world digital curves, a couple of measures on the quality of approximation,
comparative results related with two other well-referred algorithms, and CPU times, have been presented to
demonstrate the elegance and efficacy of the proposed algorithm.