This tutorial is being developed as part of a Pattern Recognition course(308-644B) given by the McGill University School of Computer Science . The course lecturer is Godfried Toussaint. If you're looking at this Prof. Toussaint - I sent you an e-mail last week asking for that extension - I'll be working on this very hard over the next few days and hope to have things in shape by Monday the 4th of May. The tutorial is layed out as follows.
This webpage shall contain an explanation of a sequential algorithm used for polygonal approximation of plane, closed curves, which was presented in a 1985 paper by L.P. Cordella(University of Naples, Italy), and G.Dettori (Institue of Applied Mathematics of C.N.R., Geneva, Italy).
Piecewise linear approximation of digital curves is a useful technique in many pattern recognition tasks. The objective is to represent a digital curve by a sequence of segments, whereby the obtained polygon preserves the original shape and size to a specified tolerance. This method is useful for preprocessing for the following reasons
Cordella and Dettori's algorithm is an iterative one, based on scale- independent appoximation criterion. The tolerance on the smoothing is given as a percentage of the original polygon area. The algorithm is thus area-preserving. Thus, in the case of picture processing, each object is assigned its own area tolerance. This prevents objects being assigned unsuitable tolerances. If a picture consisted of 2 shapes, one large, and one small, then it would not be appropriate to assign the same absolute tolerance to both, but a percentage area of each object solves the problem.
The algorithm assumes the following
Area Ao of the polygon to be smoothed is known. All N vertices of the polygon are available.
There are different acceptable methods of assigning an area tolerance. This is because a polygon may well be characterized by both number of sides and by the length of these sides.
Consider the following.
An area tolerance is assigned to the polygon in percentage terms. This is called Eo.
The more formal definition is Eo : the a priori estimate of the maximum percentage area variation which can be admitted.
Thus, the numerical value of the tolerance is simply
Allowable Error = (AoEo)/N
