Browse Prior Art Database

Polygon Approximation Using Minimum Description Length

IP.com Disclosure Number: IPCOM000118058D
Original Publication Date: 1996-Aug-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 2 page(s) / 76K

Publishing Venue

IBM

Related People

Flickner, M: AUTHOR [+2]

Abstract

Disclosed is a method of fitting polygons given a sequence of points in two dimensions obtained from sampling a 2-D curve, along its perimeter. The polygon is determined by minimizing a cost function obtained using the minimum description length principles. The resulting search problem is solved using Dykstra's algorithm. The execution time and space requirements of the algorithm are both O(n sup 2), where n is the number of points.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Polygon Approximation Using Minimum Description Length

      Disclosed is a method of fitting polygons given a sequence of
points in two dimensions obtained from sampling a 2-D curve, along
its perimeter.  The polygon is determined by minimizing a cost
function obtained using the minimum description length principles.
The resulting  search problem is solved using Dykstra's algorithm.
The execution time  and space requirements of the algorithm are both
O(n sup 2), where n is  the number of points.

      Given a sequence of points C = {  p sub i ' = ' (x sub i ,
y sub i)' | ' 0 ' <=' i ' < ' n} in two dimensions, such as that
obtained by sampling the perimeter of a planar region, we seek to
find a polygonal  approximation to C.  Such an approximation is a
sequence U of k points  such that the lines joining adjacent points
in U approximates the points  in C.  Examples are given in the
Figure.  Assume that the starting point  (==  ending point) of the
approximation is specified, and that this point  is the first point
in the data point sequence.

      The method produces a polygonal approximation U to the set of
points C such that (1) U has few vertices, and (2) it well
approximates C.  The two main features of the method are:
  1.  It assigns a goodness measure or cost function incorporating
       both of the above criteria to any possible approximating
       polygon.  This cost function is based on the Minimum
       Description Length principle.
  2.  It searches over all possible approximating polygons with
       vertices in C to find the best one, and this searching is
       done very fast.

The key novelties are:
  1.  The use of the MDL principle to define the cost functioned
       for a candidate approximating polygon.
  2....