Method and apparatus for recognizing gestures on a computer system

• US 5,594,810 A
• Filed: 06/05/1995
• Issued: 01/14/1997
• Est. Priority Date: 09/30/1993
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Gourdol, Arnaud P. J.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): MEHTA, BHAVESH M
• Application Number:
  US08/463,293
• Time in Patent Office: 589 Days
• Field of Search: 382/186, 382/187, 382/202, 382/203
• US Class Current: 382/187
• CPC Class Codes: G06F 3/04883 for inputting data by handwriting, e.g. gesture or text
• CPC Class Codes: G06V 30/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32
• CPC Class Codes: G06V 30/333 Preprocessing; Feature extraction
• CPC Class Codes: G06V 30/373 using a special pattern or subpattern alphabet

Abstract

A method and apparatus for recognizing a gesture input on a display screen of a computer system. A stroke is input by a user on the screen, and the stroke is smoothed by reducing the number of points that define the stroke. The number of points are reduced by calculating a weighted position for a new point between two adjacent points that are within a threshold distance, and replacing a plurality of points that are separated by less than the threshold distance with the new point. The stroke is also normalized by dividing coordinates of the points by a scaling factor and storing selected points of the stroke in a prototype buffer. The normalized stroke is matched to one or more of a plurality of gesture prototypes by utilizing a correlation score that is calculated for each prototype. The gesture prototypes preferably include standard gestures having standardized shapes as well as gestures input by a user, and include bracket and pigtail gestures. An alternative embodiment determines whether the stroke is part of a multiple stroke gesture and, if so, adds the stroke to previously-entered strokes.

Claims

1. A method for recognizing a gesture input on a display screen for a computer system, the method comprising the steps of:

(a) processing a stroke entered on a computer screen to smooth said stroke, said stroke including a plurality of points, said processing step including reducing the number of points that define said stroke such that said points of said smoothed stroke are located at least a threshold distance apart from one another, and including the substeps of;

(i) calculating a position for a new point that is positioned between two adjacent points in the stroke that are separated by less than the threshold distance; and

(ii) replacing a plurality of points that are separated by less than the threshold distance with said new point, wherein the weight given to the location of a specific new point is proportional to the number of points that are replaced by the specific new point;

(b) normalizing said smoothed stroke;

(c) determining whether said normalized stroke matches one of a plurality of gesture prototypes; and

(d) when at least one gesture prototype matches said normalized stroke, selecting the gesture represented by a best matched gesture prototype as an interpretation of said stroke.

2. A method as recited in claim 1 wherein two adjacent points that are separated by less than the threshold distance are replaced with said new point.

3. A method as recited in claim 2 wherein said steps of calculating a position and replacing said two adjacent points with said new point are repeated until all of the remaining points in the stroke are separated by at least the threshold distance.

4. A method as recited in claim 1 wherein said step of normalizing said stroke includes a substep of storing selected points of said smoothed stroke in at least one prototype buffer.

5. A method as recited in claim 4 wherein said step of normalizing said stroke includes the substep of storing coordinates of said selected points of said stroke in said prototype buffer, wherein horizontal coordinates of said selected points are stored in a first prototype buffer, and said vertical coordinates of said selected points are stored in a second prototype buffer.

6. A method as recited in claim 5 wherein said step of normalizing said stroke includes the substeps of:

subtracting an offset value from each coordinate; and

dividing each coordinate by a scaling factor.

7. A method as recited in claim 4 wherein said step of normalizing said stroke includes the substep of storing coordinates of said selected points of said stroke in said prototype buffer, wherein said stored coordinates are normalized coordinates.

8. A method as recited in claim 4 wherein said prototype buffer stores up to a predetermined number of selected points, and wherein said selected points are distributed approximately along a full length of said stroke.

9. A method as recited in claim 8 wherein said selected points are selected approximately as every nth point of said stroke, wherein n is calculated as the number of points in said stroke divided by said predetermined number of points in said prototype buffer.

10. A method as recited in claim 4 wherein said step of determining whether said normalized stroke matches one of a plurality of gesture prototypes further includes the substep of calculating a plurality of scores, each score indicating the correspondence of said normalized stroke to an associated one of said gesture prototypes.

11. A method as recited in claim 10 wherein said step of calculating a plurality of scores includes calculating a standard deviation and a Pearson'"'"'s Correlation for said points stored in said at least one prototype buffer.

12. A method as recited in claim 10 wherein said step of selecting said gesture represented by the best matched gesture prototype includes selecting the gesture prototype having the highest of said calculated scores.

13. A method as recited in claim 12 wherein said step of selecting said gesture is accomplished only when said highest score is above a predetermined threshold value.

14. A method as recited in claim 10 wherein said gesture prototypes include standard gestures including an open bracket gesture and a close bracket gesture operative to select an object displayed on said computer screen.

15. A method as recited in claim 14 wherein said standard gestures include a pigtail gesture operative to delete an object displayed on said computer screen.

16. A method as recited in claim 15 wherein said gesture prototypes include gestures inputted by a user, each gesture representing one of said standard gestures.

17. A method as recited in claim 1 further comprising a step of determining whether said stroke is part of a multiple stroke gesture, and adding said stroke to stroke portions previously input when said stroke is determined to be part of a multiple stroke gesture.

18. A method of interpreting a gesture input onto a display screen associated with a pen-based computer system, the method comprising the steps of:

detecting a pointer-created stroke input by a user onto the computer screen;

processing the stroke for gesture recognition, the stroke processing step resulting in a series of line segments formed between adjacent points that define the stroke wherein said step of processing the stroke includes smoothing said stroke by reducing the number of points that define the stroke such that the points of the smoothed stroke are located at least a threshold distance apart from one another, said reducing including calculating a position for a new point that is positioned between two adjacent points in the stroke that are separated by less than the threshold distance, and replacing a plurality of points that are separated by less than the threshold distance with said new point;

normalizing said processed stroke by;

dividing each coordinate by a scaling factor; and

storing scaled coordinates of selected points of the stroke to fit in at least one prototype buffer as a normalized stroke, said points being selected based on a size of said prototype buffer;

comparing the normalized stroke to a multiplicity of gesture prototypes, wherein a plurality of the gesture prototypes represent the same gesture; and

selecting a gesture associated with the gesture prototype that most closely resembles the normalized stroke.

19. A method as recited in claim 18 wherein the step of normalizing the stroke includes the substep of subtracting an offset value from each coordinate of the points of the processed stroke.

20. A method as recited in claim 18 wherein said gesture prototypes include standard gesture prototypes having standardized shapes and user-inputted gesture prototypes having been previously handwritten by a user.

21. A method as recited in claim 20 wherein a gesture is represented by a standard gesture prototype and a plurality of user-inputted gesture prototypes.

22. A method as cited in claim 18 further comprising a step of determining whether the processed stroke is correlated to the most closely resembled prototype by at least a predetermined threshold correlation, wherein the stroke is only interpreted as the selected gesture when the correlation exceeds the predetermined threshold.

23. A method as recited in claim 18 wherein horizontal coordinates of said selected points are stored in a first prototype buffer, and said vertical coordinates of said selected points are stored in a second prototype buffer.

24. A method as recited in claim 18 wherein said prototype buffer stores up to a predetermined number of coordinates, and wherein said selected points are distributed approximately along a full length of said stroke.

25. A method as recited in claim 24 wherein said selected points are selected approximately as every nth point of said stroke, wherein n is calculated as the number of points in said stroke divided by said predetermined number of coordinates in said prototype buffer.

26. A method as recited in claim 18 wherein the weight given to the location of a specific new point is proportional to the number of points that are replaced by the specific new point.

27. A method as recited in claim 18 wherein when said stroke is entered by said user within a predetermined distance of a previous stroke and within a predetermined time of when said previous stroke was entered, said stroke and said previous stroke are together considered a multiple-stroke gesture.

28. A computer system comprising:

a central processing unit (CPU);

screen means coupled to said CPU;

pointer means coupled to said CPU to provide user inputs which can be displayed on said screen means;

processing means for smoothing a stroke entered by said pointer means on said screen means by reducing the number of a plurality of points that define the stroke such that the points of the smoothed stroke are located at least a threshold distance apart from one another, said reducing including calculating a position for a new point that is positioned between two adjacent points in the stroke which are separated by less than the threshold distance, and replacing a plurality of points that are separated by less than the threshold distance with said new point;

means for normalizing said smoothed stroke by dividing each coordinate by a scaling factor and storing coordinates of selected points of the stroke as the normalized stroke in at least one buffer of predetermined size;

means for determining whether said normalized stroke matches one of a plurality of gesture prototypes; and

means for selecting the gesture represented by a best matched gesture prototype as an interpretation of said stroke.

29. A computer system as recited in claim 28 wherein said pointer means is selected from the group comprising stylus, mouse, and trackball pointing devices.

30. A computer system as recited in claim 29 wherein said screen means and said pointer means are parts of a pen computer system.

31. A computer system as recited in claim 28 wherein said gesture prototypes include an open bracket gesture and a close bracket gesture operative to select an object displayed on said computer screen.

32. A computer system as recited in claim 31 wherein said gesture prototypes include a pigtail gesture operative to delete an object displayed on said computer screen.

33. A computer system as recited in claim 28 wherein said step of normalizing said smoothed stroke includes subtracting an offset value from each coordinate of each of said points.

34. A computer system as recited in claim 33 wherein horizontal coordinates of said selected points are stored in a first prototype buffer, and said vertical coordinates of said selected points are stored in a second prototype buffer.

35. A computer system as recited in claim 28 wherein said normalized stroke is compared to a standard gesture prototype having a standardized shape and said normalized stroke is compared to a plurality of user gesture prototypes previously handwritten by a user of said computer system.

36. A computer system as recited in claim 28 wherein the weight given to the location of a specific new point is proportional to the number of points that are replaced by the specific new point.

37. A commuter system as recited in claim 28 wherein said selected points are selected based on said predetermined size of said at least one buffer.

38. A computer system as recited in claim 28 wherein when said stroke is entered by said user within a predetermined distance and within a predetermined time of a previous stroke, said stroke and said previous stroke are together considered a multiple-stroke gesture.