Method and system for extracting features in a pattern recognition system

• US 6,178,261 B1
• Filed: 08/05/1997
• Issued: 01/23/2001
• Est. Priority Date: 08/05/1997
• Status: Expired due to Fees

• Current Assignee: Board of Regents of the University of Michigan (University of Michigan)
• Original Assignee: Board of Regents of the University of Michigan (University of Michigan)
• Inventors: Williams, William J., Hero, Alfred O. III, OʼNeill, Jeffrey C., Nickel, Robert M., Zalubas, Eugene J.
• Primary Examiner(s): MEHTA, BHAVESH M
• Application Number:
  US08/906,253
• Time in Patent Office: 1,267 Days
• Field of Search: 382/169, 382/168, 382/159, 382/203, 382/181, 382/190, 382/191, 382/218, 382/224, 382/225, 382/276, 382/278, 382/197, 382/198, 704/250
• US Class Current: 382/190
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/187 Frequency domain transformation; Autocorrelation

Abstract

Method and system for extracting features from measurement signals obtained from real world, physical signals by first forming an invariant component of the measurement signals and then using a technique based on a noise subspace algorithm. This technique first casts or projects the transformed measurement signals into separate subspaces for each extraneous variation or group of variations. The subspaces have minimal over-lap. The recognition of a particular invariant component within a pertinent subspace is then preferably performed using Singular Value Decomposition (SVD) techniques to generate a pattern recognition signal. A series of transformations can be used to form an invariant component called the Scale and Translation Invariant Representation (STIR). In one embodiment, the first step is to form an appropriate time-frequency representation such as the Reduced Interference Distribution (RID) or other distribution whose properties are covariant with translations in time and frequency and changes in scale. A series of additional transformations including a scale transform yield the STIR representation. Features are then extracted from a set of STIR representations taken as examples of the desired signal. The STIR approach removes much of the variation due to translation. In bit-mapped documents, the same translation invariant and scale invariant transformations may be made to regularize characters and words. Also, the same feature selection method functions in an image setting. The method has been found to be particularly useful in word spotting in bitmapped documents corrupted by faxing.

Claims

1. A method of classifying an object represented by object signals containing a pattern of the object, the method comprising:

creating a noise subspace for at least one object class;

transforming the object signals to produce an object vector;

projecting the object vector onto the noise subspace for each object class; and

determining that the object represented by the object signals is a member of the object class based on the projection of the object vector onto the noise subspace.

2. A method of classifying an object as in claim 1 wherein each object class is defined using at least one exemplar vector, each exemplar vector having a number of elements greater than the number of exemplar vectors defining the object class.

3. A method of classifying an object as in claim 1 wherein the noise subspace comprises at least one vector normal to at least one exemplar vector, each exemplar vector based on an object representative of the object class.

4. A method of classifying an object as in claim 1 wherein the at least one object class is a plurality of object classes, determining that an object is a member of an object class comprising determining the object class with the minimum noise subspace projection.

5. A method of classifying an object as in claim 1 wherein transforming comprises scale transformation.

6. A method of classifying an object as in claim 1 wherein transforming comprises autocorrelation.

7. A method of classifying an object as in claim 1 wherein transforming comprises producing a scale and translation invariant representation (STIR).

8. A method of classifying an object as in claim 1 wherein the object is a character, the method further comprising:

determining that the object is a member of a font object class based on the projection of the object vector onto the noise subspace of at least one font class; and

determining that the object is a member of a character class based on the projection of the object vector onto the noise subspace of at least one character class.

9. A method of classifying an object as in claim 1 wherein transforming comprises obtaining the reduced interference distribution (RID).

10. A method of classifying an object as in claim 1 wherein creating a noise subspace comprises:

obtaining a plurality of exemplar signals;

forming a vector representation for each exemplar signal;

forming an invariant transform matrix from the vector representations, the matrix having a greater number of elements in each vector than the number of vector representations;

obtaining a singular value decomposition (SVD) of the matrix; and

defining the noise subspace as eigenvectors not forming a complete orthonormal basis.

11. A method of classifying an object as in claim 1 wherein the object signals comprise an image containing the object.

12. A method of classifying an object as in claim 1 further comprising generating an energy distribution signal corresponding to spectral energy content of the object signals and wherein transforming is performed on the energy distribution signal.

13. A method of pattern recognition comprising:

generating at least one noise subplane vector;

measuring signals representative of a pattern;

performing at least one invariant transformation on the measured signals;

measuring the orthogonality of the transformed signals and each noise subplane vector; and

recognizing the pattern based on the measured orthogonality between the transformed signals and each noise subplane vector.

14. A method of pattern recognition as in claim 13 wherein the pattern is recognized if the measured orthogonality is greater than a predetermined threshold.

15. A method of pattern recognition as in claim 13 wherein a pattern is to be recognized as one of a plurality of patterns, generating at least one noise subplane vector comprises generating at least one noise subplane vector for each of the plurality of patterns and recognizing a pattern comprises determining as a recognized pattern the pattern having the greatest orthogonality between the transformed signal and each noise subplane vector generated for the recognized pattern.

16. A method of pattern recognition as in claim 13 wherein performing at least one invariant transformation comprises converting the measured signals to a covariant time-frequency representation.

17. A method of pattern recognition as in claim 13 wherein performing at least one invariant transformation comprises autocorrelation in time.

18. A method of pattern recognition as in claim 13 wherein performing at least one invariant transformation comprises autocorrelation in frequency.

19. A method of pattern recognition as in claim 13 wherein performing at least one invariant transformation comprises autocorrelation in space.

20. A method of pattern recognition as in claim 13 wherein performing at least one invariant transformation comprises scale transformation.

21. A method of pattern recognition as in claim 13 wherein performing at least one invariant transformation comprises producing a scale and translation invariant representation (STIR).

22. A method of pattern recognition as in claim 13 wherein the pattern is a character, the method further comprising:

determining that the pattern is a member of a particular font based on the measured orthogonality of the transformed signals and noise subplane vectors for each font; and

determining that the pattern is a particular character based on the measured orthogonality of the transformed signals and noise subplane vectors for each character in the particular font.

23. A method of pattern recognition as in claim 13 wherein performing at least one invariant transformation comprises obtaining the reduced interference distribution (RID).

24. A method of pattern recognition as in claim 13 wherein generating at least one noise subplane vector comprises:

obtaining a plurality of exemplar signals;

forming a vector representation for each exemplar signal;

forming an invariant transform matrix from the vector representations, the matrix having a greater number of elements in each vector than the number of vector representations;

obtaining a singular value decomposition (SVD) of the matrix; and

defining each noise subplane vector as an eigenvector not forming a complete orthonormal basis.

25. A method of pattern recognition as in claim 13 wherein the signals representative of a pattern comprise an image containing the pattern.

26. A method of pattern recognition as in claim 13 further comprising generating an energy distribution signal corresponding to spectral energy content of the signals representative of a pattern and wherein the at least one invariant transformation is performed on the energy distribution signal.

27. A system for classifying an object represented by object signals containing a pattern of the object, the system comprising:

means for creating a noise subspace for at least one object class;

means for transforming the object signals to produce an object vector;

means for projecting the object vector onto the noise subspace for each object class; and

means for determining that the object represented by the object signals is a member of the object class based on the projection of the object vector onto the noise subspace.