Scale-space Techniques For Polygonal Approximation Of Planar Curves

Polygonal approximation of object shapes is a basic problem in the fields of computervision and image analysis. Related algorithms have been widely used in shape matching,object recognition, shape retrieval, shape coding and other vision and image tasks. Thispaper first introduces the developments of polygonal approximation techniques, as well asthe scale-space concept and the curvature scale-space technique in shape description andanalysis. By a combination of the two kinds of techniques, two scale-space techniques forpolygon approximation are proposed to solve two major problems in the polygonalapproximation process. One is the Min-#problem: to obtain an approximate polygon witha given error threshold and as much as fewer line segments. Another is the Min-εproblem: to obtain an approximate polygon with a given number of line segments and atotal error as smaller as possible. According to the nature of different problems, twodifferent algorithms are developed to express the scale-space concept and solve theapproximation problem.1) Polygonal approximation with a limited maximum error of single point. Thisalgorithm can effectively solve the Min-#problem.2) Polygonal approximation with minimized integral square error. This algorithm canget approximation polygon with an arbitrary number of vertices. It can therefore be used tosolve the Min-ε problem.Due to the effect of the scale-space concept, the two proposed algorithms can takeinto account the information on different levels of the shape contours. As a consequence,they can preserve local shape details while not lose the global shape information. Duringthe designing of the algorithm, we analyze the global process of curve evolution to get aset of reasonable scale parameters. Numerical results show that the scale-space based polygonal approximation algorithms are more in line with the effect of the human visualsystem, when compared with the traditional approximation algorithms.