Granted Patent B2

US 7,706,612 · App. 11/284,569 · Granted Apr 27, 2010

Abstract

Claims (90)

1. A method for classifying two-dimensional shapes, comprising using a computer to perform steps of:

creating a training shape dataset including a similar shape group and a dissimilar shape group;

computing a first average shape from the similar shape group;

generating first polygonal approximations of shapes in the training shape data set and of the first average shape;

generating cumulative angle turning functions for the first polygonal approximations;

using the turning functions, aligning the first polygonal approximations of shapes in the training shape dataset to the first polygonal approximation of the first average shape to produce aligned shapes;

computing first similarity distances between the turning functions of the aligned shapes in the training shape dataset and the first average shape;

generating a distribution of the frequency of the first similarity distances for the aligned shapes;

accessing a new shape;

generating a second polygonal approximation of the new shape;

generating a cumulative angle turning function for the second polygonal approximation;

using the turning functions for the second polygonal approximation and for the first polygonal approximation of the first average shape, aligning the polygonal approximations of the new shape and the first average shape;

computing a second similarity distance between the turning functions for the second polygonal approximation of the new shape and the first polygonal approximation of the first average shape; and

using the distribution, classifying the new shape into either the similar shape group or the dissimilar shape group based on the second similarity distance.

2. The method of claim 1 , wherein the step of computing the first average shape comprises steps of:

identifying one shape from the similar shape group as a template shape;

aligning shapes in the similar shape group to the template shape;

generating a second average shape from the similar shape group;

determining a sum of distances between the second average shape and the shapes in the similar shape group; and

outputting the first average shape when the sum of distances is a minimum.

3. The method of claim 2 , wherein the step of outputting comprises steps of:

identifying the second average shape as the template shape; and

repeating the steps of aligning, generating, and determining until the sum of distances is a minimum.

4. The method of claim 1 , wherein the step of classifying a new shape comprises a step of:

identifying a classification threshold from the distribution by which to classify the new shape.

5. A method for classifying two-dimensional shapes, comprising using a computer to perform steps of:

creating a training shape dataset including a similar shape group and a dissimilar shape group;

computing a first average shape from the similar shape group;

aligning shapes in the training shape dataset to the first average shape;

using polygonal approximations of the aligned shapes, computing a similarity distance between the shapes in the training shape dataset and the first average shape;

generating a distribution of the frequency of similarity distances for shapes in the training shape dataset;

accessing a new shape;

using the distribution, classifying the new shape into either the similar shape group or the dissimilar shape group based on a similarity distance of the new shape, the classifying including a step of identifying a classification threshold from the distribution by which to classify the new shape; and

updating the first average shape, the distribution of the frequency and the classification threshold using the new shape, when the new shape has been classified into the similar shape group.

6. The method of claim 5 , wherein the step of computing the first average shape comprises steps of:

identifying one shape from the similar shape group as a template shape;

aligning shapes in the similar shape group to the template shape;

generating a second average shape from the similar shape group;

determining a sum of distances between the second average shape and the shapes in the similar shape group; and

outputting the first average shape when the sum of distances is a minimum.

7. The method of claim 6 , wherein the step of outputting comprises steps of:

identifying the second average shape as the template shape; and

repeating the steps of aligning, generating, and determining until the sum of distances is a minimum.

8. The method of claim 5 , wherein the step of aligning shapes comprises steps of:

generating a polygonal approximation for each of the shapes; and

using a cumulative angle turning function to align the polygonal approximation to the first average shape.

9. A method for classifying two-dimensional shapes, comprising using a computer to perform steps of:

creating a training shape dataset including a similar shape group and a dissimilar shape group;

computing a first average shape from the similar shape group;

aligning shapes in the training shape dataset to the first average shape;

using polygonal approximations of the aligned shapes and cumulative angle turning functions of the polygonal approximations, computing a similarity distance between the shapes in the training shape dataset and the first average shape;

generating a distribution of the frequency of similarity distances for shapes in the training shape dataset;

accessing a new shape;

using the distribution, classifying the new shape into either the similar shape group or the dissimilar shape group based on a similarity distance of the new shape, the classifying including a step of identifying a classification threshold from the distribution by which to classify the new shape; and

updating the first average shape, the distribution of the frequency and the classification threshold using the new shape, when the new shape has been classified into the similar shape group.

10. The method of claim 9 , wherein the step of computing the first average shape comprises steps of:

identifying one shape from the similar shape group as a template shape;

aligning shapes in the similar shape group to the template shape;

generating a second average shape from the similar shape group;

determining a sum of distances between the second average shape and the shapes in the similar shape group; and

outputting the first average shape when the sum of distances is a minimum.

11. The method of claim 10 , wherein the step of outputting comprises steps of:

identifying the second average shape as the template shape; and

repeating the steps of aligning, generating, and determining until the sum of distances is a minimum.

12. The method of claim 9 , wherein the step of aligning shapes comprises steps of:

generating a polygonal approximation for each of the shapes; and

using a cumulative angle turning function to align the polygonal approximation to the first average shape.

13. A method for classifying two-dimensional shapes, comprising using a computer to perform steps of:

creating a training shape dataset including a similar shape group and a dissimilar shape group;

computing a first average shape from the similar shape group;

generating first polygonal approximations of shapes in the training shape data set and of the first average shape;

aligning the first polygonal approximations of shapes in the training shape dataset to the first polygonal approximation of the first average shape to produce aligned shapes;

computing first similarity distances using the aligned first polygonal approximations of the aligned shapes in the training shape dataset and the first average shape;

generating a distribution of the frequency of the first similarity distances for the aligned shapes;

accessing a new shape;

generating a second polygonal approximation of the new shape;

aligning the polygonal approximations of the new shape and the first average shape;

computing a second similarity distance using the aligned polygonal approximations of the new shape and the first average shape; and

using the distribution, classifying the new shape into either the similar shape group or the dissimilar shape group based on the second similarity distance.

14. The method of claim 13 , wherein the step of computing the first average shape comprises steps of:

identifying one shape from the similar shape group as a template shape;

aligning shapes in the similar shape group to the template shape;

generating a second average shape from the similar shape group;

determining a sum of distances between the second average shape and the shapes in the similar shape group; and

outputting the first average shape when the sum of distances is a minimum.

15. The method of claim 14 , wherein the step of outputting comprises steps of:

identifying the second average shape as the template shape; and

repeating the steps of aligning, generating, and determining until the sum of distances is a minimum.

16. The method of claim 13 , wherein the step of classifying a new shape comprises a step of:

identifying a classification threshold from the distribution by which to classify the new shape.

Assignments (13)