Fast Algorithms for Dominant Point Detection with Variable Tradeoff between the Approximation Error and the Compression

摘要

This paper proposes two new algorithms for dominant point detection in digital curves. The motivation is the following: 'points of large curvature contain much information about shape; however, points of small curvature are not devoid of such information. In many cases, the cumulative curvature due to a large number of such points occurring consecutively is significant.' In the proposed schemes, detecting the next dominant point on the curve involves determining the curvature at each point, and computing the resultant cumulative curvature for all the points starting with the last detected dominant point. It is demonstrated that such an approach effectively imposes an upper bound on the error in reconstruction. In our algorithms, the compression ratio and the error in the shape representation have been controlled by appropriately chosen parameters. The magnitude of curvature and its sign are both important. Since the algorithms use only 1-curvature, they are very efficient. The proposed strategies yield excellent results, and have been compared with the Teh-Chin algorithm and the Ansari-Huang algorithm.