Shape simplification through polygonal approximation in the fourier domain

• Main Authors: Andrews, Mark, Kakarala, Ramakrishna
• Other Authors: Röning, Juha
• Format: Conference or Workshop Item
• Language: English
• Published: 2015
• Subjects: DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity
• Online Access: https://hdl.handle.net/10356/106994; http://hdl.handle.net/10220/25238
• Institution: Nanyang Technological University

Fourier descriptors have long been used to describe the underling continuous contours of two-dimensional shapes. Approximations of shapes by polygons is a natural step for efficient algorithms in computer graphics and computer vision. This paper derives mathematical relationships between the Fourier descriptors of the continuous contour, and the corresponding descriptors of a polygon obtained by connecting samples on the contour. We show that the polygon's descriptors may be obtained analytically in two ways: first, by summing subsets of the contour's descriptors; and second, from the discrete Fourier transform (DFT) of the polygon's vertices. We also analyze, in the Fourier domain, shape approximation using interpolators. Our results show that polygonal approximation, with its potential benefits for efficient analysis of shape, is achievable in the Fourier descriptor domain.