Masters Theses

Date of Award

12-1993

Degree Type

Thesis

Degree Name

Master of Science

Major

Computer Science

Major Professor

Jens Gregor

Committee Members

Michael G. Thomason, Bradley Vander Zanden

Abstract

Polygon Approximation is the process of representing a general contour with a piecewise linear function. When the length of each linear segment is constant, the result is an Equilateral Polygonal Approximation. This thesis proposes a first attempt to solve the Equilateral Polygonal Approximation Problem for closed contours. The solution is based on Nonlinear Programming and the approximation is modeled as an optimization process. The constant length restriction is simply handled as a set of nonlinear constraints. Four objective functions are presented: a least-squares function, two area-based functions, and an energy function. The energy function is presented as the major contribution of this work. It considers each polygon vertex as being pulled by a set of linear springs connected to the contour and the optimal solution is achieved when this system reaches its equilibrium state. Experimental results are reported for a set of fourteen tools using the energy method. Approximations for five different segment lengths are derived for each tool. Two sets of experiments are carried out over all the approximations obtained. The first experiment is intended to assess the quality of the approximations, that is, to measure how closely they resemble original contours. The results of this experiment indicates that the approximations are highly satisfactory for small segment lengths. The other experiment measures the classification capabilities of the approximations using string matching by dinammic programming. The main conclusion that can be drawn from this experiment is that the segment length plays an important role when the method is used in pattern recognition.

Download
Files over 3MB may be slow to open. For best results, right-click and select "save as..."

Share

COinS