Method and apparatus for pattern recognition and representation using fourier descriptors and iterative transformation-reparametrization

• US 6,044,171 A
• Filed: 05/09/1995
• Issued: 03/28/2000
• Est. Priority Date: 05/09/1995
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Vadem Limited
• Inventors: Ryleev, Mikhail A., Gorbatov, Boris E., Polyakov, Vladislav G.
• Primary Examiner(s): Johns, Andrew W.
• Application Number:
  US08/437,638
• Time in Patent Office: 1,785 Days
• Field of Search: 395/142, 382/225, 382/227, 382/228, 382/159, 382/161, 382/181, 382/190, 382/224, 382/276, 382/280, 345/442
• US Class Current: 382/159
• CPC Class Codes: G06V 10/431 Frequency domain transformation; Autocorrelation

Abstract

A boundary curve or line pattern is recognized by using iterative parametrization and transformation to develop a Fourier descriptor set that is mutually independent and of minimal size and then applying a classification procedure to the Fourier descriptor set to obtain a recognition result. The Fourier descriptor set so obtained has properties that enable effective recognition and compression.

Claims

1. In a computer-aided pattern recognition system, a method for recognizing a pattern comprising the steps of:

digitizing said pattern to obtain a digital representation of said pattern;

converting said digital representation of said pattern into an optimized descriptor set by repeated parametrization and transformation;

determining in a descriptor space, using said optimized descriptor set, a decision region in which said optimized descriptor set lies, said decision region having an associated class label; and

converting said class label to a recognition result.

2. The method of claim 1 wherein said converting step comprises the steps of:

constructing a source polygon from said digital representation of said pattern;

parameterizing said source polygon to obtain an initial parametric representation of said pattern;

transforming said initial parametric representation to obtain a frequency domain representation of said pattern;

attenuating said frequency domain representation in accordance with a predetermined order of approximation to obtain an attenuated frequency domain representation;

inverse-transforming said attenuated frequency domain representation to obtain a parametric representation of an approximation of said source polygon;

computing a parametrization of said approximation from said parametric representation of said source polygon;

normalizing said parametrization of said approximation to obtain a successor parametrization of said source polygon;

reparameterizing said source polygon in accordance with said successor parametrization to obtain a successor parametric representation of said source polygon;

repeating said transforming, attenuating, inverse-transforming, computing, normalizing, and reparameterizing steps until said approximation meets a predetermined goodness-of-fit criterion or predetermined convergence criterion; and

truncating a last frequency domain representation in accordance with said predetermined order of approximation, thereby obtaining a truncated last frequency domain representation as said optimized descriptor set.

3. The method of claim 2 wherein said attenuating step comprises truncating said frequency domain representation.

4. The method of claim 2 wherein said transforming step comprises obtaining a Discrete Cosine Transform of said source polygon.

5. The method of claim 2 wherein said transforming step comprises obtaining a Discrete Fourier Transform of said source polygon.

6. The method of claim 1 wherein said pattern is a character to be recognized.

7. The method of claim 1 wherein said determining step comprises the steps of:

selecting, in said descriptor space, using said optimized descriptor set, a nearest reference descriptor set from a plurality of class-labeled reference descriptor sets stored in an electronic memory device; and

identifying said class-label of said decision region to be a class-label associated with said nearest reference descriptor set.

8. In a computer-aided pattern recognition system, a method for constructing a library of reference descriptor sets for use in pattern recognition, said method comprising the steps of:

capturing a digital representation of a reference pattern and a class label of the reference pattern;

converting said digital representation of said reference pattern into an optimized reference descriptor set by repeated parametrization and transformation;

storing said optimized reference descriptor set and said class label in a memory device as an entry in said library; and

repeating said capturing, digitizing, compressing, and storing steps for a plurality of reference patterns and class labels.

9. The method of claim 8 further comprising the steps of:

capturing a digital representation of a further reference pattern and a class label of said further reference pattern;

converting said digital representation of said further reference pattern into an optimized descriptor set by repeated parametrization and transformation;

determining, in a descriptor space, a nearest previously stored reference descriptor set to said optimized descriptor set;

if the previously stored class label of said nearest previously stored reference descriptor set does not match said class label of said further reference pattern, storing said optimized descriptor set and said class label of said further reference pattern in said electronic memory device as an entry in said library; and

if the previously stored class label of said nearest previously stored reference descriptor set does match said class label of said further reference pattern,

determining, in the descriptor space, a first distance between said nearest previously stored reference descriptor set and said optimized descriptor set;

selecting, from a set including only previously stored reference descriptor sets that do not have the same class label as the nearest previously stored reference descriptor, a non-matching previously stored reference descriptor set that is nearest to said optimized descriptor set in said descriptor space;

determining, in said descriptor space, a second distance between said nearest reference descriptor set and said nearest non-matching reference descriptor set; and

if a ratio of said first distance to said second distance exceeds a predetermined threshold, storing said optimized descriptor set and said class label of said further reference pattern in said electronic memory device as an added entry in said library.

10. An apparatus for pattern recognition comprising:

a digitizer that digitizes said pattern to obtain a digital representation of said pattern;

a converter that converts said digital representation of said pattern into an optimized descriptor set by repeated parametrization and transformation; and

a classifier that determines, in a descriptor space, a nearest predetermined reference descriptor set to said optimized descriptor set and that converts said nearest reference descriptor set to a recognition result.

11. The apparatus of claim 10 wherein said converter comprises:

means for constructing a source polygon from said digital representation of said pattern;

means for parameterizing said source polygon to obtain an initial parametric representation of said pattern;

means for transforming said initial parametric representation to obtain a frequency domain representation of said pattern;

means for attenuating said frequency domain representation in accordance with a predetermined order of approximation to obtain an attenuated frequency domain representation;

means for inverse-transforming said attenuated frequency domain representation to obtain a parametric representation of an approximation of said source polygon;

means for computing a parametrization of said approximation from said parametric representation of said source polygon;

means for normalizing said parametrization of said approximation to obtain a successor parametrization of said source polygon;

means for reparameterizing said source polygon in accordance with said successor parametrization to obtain a successor parametric representation of said source polygon;

means for repeatedly applying said transforming, attenuating, inverse-transforming, computing, normalizing and reparametrizing means until said approximation meets a predetermined goodness-of-fit criterion or predetermined convergence criterion; and

means for truncating a last frequency domain representation of said pattern in accordance with said predetermined order of approximation, thereby obtaining a last attenuated frequency domain representation as said optimized descriptor set.

12. The apparatus of claim 11 wherein said attenuating means comprises means for truncating said frequency domain representation.

13. The apparatus of claim 11 wherein said transforming means comprises means for obtaining a Discrete Cosine Transform of said source polygon.

14. The apparatus of claim 11 wherein said transforming means comprises means for obtaining a Discrete Fourier Transform of said source polygon.

15. The apparatus of claim 10 wherein said pattern is a character to be recognized.

16. The apparatus of claim 10 wherein said classifier comprises:

means for selecting, in said descriptor space, using said optimized descriptor set, a nearest reference descriptor set from a plurality of class labeled reference descriptor sets stored in an electronic memory device; and

means for identifying said class label of said decision region to be a class label associated with said nearest reference descriptor.

17. In a computer-aided pattern recognition system, apparatus for constructing a library of reference descriptor sets for use in pattern recognition, said apparatus comprising:

means for capturing a digital representation of a reference pattern and a class label of the reference pattern;

means for converting said digital representation of said reference pattern into an optimized reference descriptor set by repeated parametrization and transformation;

means for storing said reference descriptor set and said class label in a memory device as an entry in said library; and

means for repeatedly applying said capturing, digitizing, converting, and storing means for a plurality of reference patterns and class labels.

18. The apparatus of claim 17 further comprising:

means for capturing a digital representation of a further reference pattern and a class label of said further reference pattern;

means for converting said digital representation of said further reference pattern into an optimized descriptor set by repeated parametrization and transformation;

means for determining, in a descriptor space, a nearest previously stored reference descriptor set to said optimized descriptor set;

means for, if the previously stored class label of said nearest previously stored reference descriptor set does not match said class label of said further reference pattern, storing said optimized descriptor set and said class label of said further reference pattern in said electronic memory device as a library entry; and

means for, if the previously stored class label of said nearest previously stored reference descriptor set does match said class label of said further reference pattern,

determining, in the descriptor space, a first distance between said nearest previously stored reference descriptor set and said optimized descriptor;

selecting, from a set including only previously stored reference descriptor sets that do not have the same class label as the nearest previously stored reference descriptor set, a non-matching previously stored reference descriptor set that is nearest to said optimized descriptor set said descriptor space;

determining, in said descriptor space, a second distance between said nearest reference descriptor set and said nearest non-matching reference descriptor set; and

if a ratio of said first distance to said second distance exceeds a predetermined threshold, storing said optimized descriptor set and said class label of said further reference pattern in said electronic memory device as an added entry in said library.