Feature extraction for real-time pattern recognition using single curve per pattern analysis

• US 6,898,315 B2
• Filed: 03/22/2002
• Issued: 05/24/2005
• Est. Priority Date: 03/23/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Guha, Angshuman
• Primary Examiner(s): LEE, TOMMY D
• Application Number:
  US10/104,453
• Publication Number:
  US 20020097910A1
• Time in Patent Office: 1,159 Days
• Field of Search: 382/181, 382/187, 382/188, 382/189, 382/186, 382/182, 382/184, 382/241, 382/137, 382/195, 382/197, 382/198, 382/201, 382/203, 382/122, 382/123, 345/441
• US Class Current: 382/187
• CPC Class Codes: G06V 30/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32

Abstract

A feature extractor samples points on an input pattern drawn in real time. In addition to X and Y coordinates, each sample has an up/down or Z coordinate value representing whether or not the sample point is a perceptible part of the pattern. The groups of coordinate values are transformed into respective sets of coefficients of Chebyshev polynomials by least-squares fit. A recognition unit can use the coefficients as features to identify the character. Additional features, such as aspect ratio and center of gravity, are also derived to aid in recognizing the pattern or reconstructing its image.

Claims

1. A computer-implemented method comprising:

recording coordinate values representing a two-dimensional pattern as a three-dimensional pattern, including storing x-coordinate and y-coordinate values in conjunction with a z-coordinate, the z-coordinate having a first value at times when the pattern is being entered and a second value at times when the pattern is not being entered;

fitting the x-coordinate, y-coordinate and z-coordinate values at sample points to a plurality of related mathematical basis functions by transforming the coordinate values at the sample points into coefficients of the function;

featurizing the input pattern into a plurality of features, at least some of the features corresponding to the coefficients of the basis function; and

performing computerized recognition by using the features to determine an alphanumeric value corresponding to the input pattern.

2. The method of claim 1 wherein the plurality of related mathematical basis functions comprises a polynomial.

3. The method of claim 1 wherein the plurality of related mathematical basis functions comprises a Chebyshev polynomial.

4. The method of claim 1 wherein recording coordinate values comprises, receiving x-coordinate and y-coordinate values representing strokes entered into an input device, and storing the x-coordinate and y-coordinate values in conjunction with the first value of the z-coordinate as the strokes are received.

5. The method of claim 1 wherein the computerized recognition is performed in real time.

6. The method of claim 1 wherein featurizing the input pattern further comprises, deriving other features from the input pattern in addition to the coefficient-based features.

7. The method of claim 1 further comprising, detecting an end to the entry of a set of strokes before performing computerized recognition on that set.

8. The method of claim 1 further comprising, normalizing at least some of the features.

9. A computer-readable medium having computer-executable instructions for performing the method of claim 1.

10. A method for recognizing an input pattern, comprising:

sampling the input pattern so as to produce a plurality of groups of coordinate values, each of the groups including an up/down coordinate such that the plurality of groups represent the input pattern as a single curve independent of a number of strokes that formed the pattern;

transforming the groups of coordinate values into coefficients of a plurality of related mathematical basis functions; and

providing the coefficients as features to a feature-based recognizer, the recognizer using the features to return information that identifies the entire input pattern as belonging to one class of a set of possible classes.

11. The method of claim 10 wherein the plurality of related mathematical basis functions comprises a polynomial.

12. The method of claim 10 wherein the plurality of related mathematical basis functions comprises a Chebyshev polynomial.

13. The method of claim 10 wherein transforming the groups of coordinate values comprises, normalizing the coefficients to compensate for characteristics of the input pattern.

14. The method of claim 10 wherein transforming the groups of coordinate values comprises, fitting the coefficients to the functions in accordance with an error criterion.

15. The method of claim 10 wherein transforming the groups of coordinate values comprises, fitting the coefficients to the functions in accordance with a least-squares criterion.

16. The method of claim 10 wherein the computerized recognition is performed in real time.

17. The method of claim 10 further comprising, providing other features of the input pattern in addition to the coefficient-based features to the feature-based recognizer.

18. A computer-readable medium having computer-executable instructions for performing the method of claim 10.

19. A method for recognizing a two-dimensional input pattern corresponding to a plurality of separate pattern strokes, each stroke being entered during a pen-down condition that occurs between pen-up conditions, the method comprising:

converting the input pattern into a single curve independent of pattern strokes by sampling the input pattern into a single set of a plurality of x-coordinate, y-coordinate and z-coordinate values, the z-coordinates having a first value corresponding to a pen-down condition or a second value corresponding to a pen-up condition;

transforming the x-coordinate, y-coordinate and z-coordinate values into coefficients of a plurality of related mathematical basis functions;

maintaining the coefficients, including those for the values representing the z-coordinate, as features of the input pattern; and

identifying the entire input pattern as belonging to one of a number of classes based on the features.

20. The method of claim 19 wherein the plurality of related mathematical basis function comprises a polynomial.

21. The method of claim 19 wherein the plurality of related mathematical basis functions comprises a Chebyshev polynomial.

22. The method of claim 19 wherein transforming the x-coordinate, y-coordinate and z-coordinate values into coefficients comprises, normalizing the coefficients to compensate for characteristics of the input pattern.

23. The method of claim 19 wherein transforming the x-coordinate, y-coordinate and z-coordinate values comprises, fitting the coefficients to the functions in accordance with an error criterion.

24. The method of claim 19 wherein transforming the x-coordinate, y-coordinate and z-coordinate values comprises, fitting the coefficients to the functions in accordance with a least-squares criterion.

25. The method of claim 19 wherein the computerized recognition is performed in real time.

26. The method of claim 19 further comprising, maintaining other features of the input pattern in addition to the coefficient-based features.

27. A computer-readable medium having computer-executable instructions for performing the method of claim 19.

28. A system for recognizing an input pattern, comprising:

an input device for producing a plurality of signals corresponding to coordinates of the input pattern on the input device, at least one of the signals identifying an up/down state of input, the coordinates representing the input pattern as a single curve independent of a number of pattern strokes that form the input pattern;

a data processor for transforming the signals into coefficients of related basis functions; and

a recognition unit responsive to the coefficients for identifying the input pattern as belonging to one of a number of classes.

29. The system of claim 28 wherein the input device comprises a pressure sensitive device that produces signals representing x-coordinates and y-coordinates when pressure is sensed thereby.

30. The system of claim 28 wherein the input device comprises a pressure sensitive device that produces at least one signal when pressure is sensed thereby and at least one other signal when pressure is not sensed thereby.

31. The system of claim 28 wherein recognition unit comprises a neural network.

32. A computer-readable medium having computer-executable instructions, which when executed perform a method, comprising:

sampling an input pattern comprising a plurality of distinct strokes, so as to produce a plurality of coordinate values including values representing an up/down coordinate, the plurality of coordinate values representing the input pattern as a single curve independent of how many distinct pattern strokes are in the plurality;

transforming the coordinate values, including those for the values representing the up/down coordinate, into coefficients of a set of basis functions;

maintaining the coefficients as features of the input pattern; and

identifying the input pattern as belonging to one of a number of classes based on the features.