Method and apparatus for recognizing gestures on a computer system

• US 5,590,219 A
• Filed: 03/16/1995
• Issued: 12/31/1996
• 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): Couso, Jose L.
• Assistant Examiner(s): MEHTA, BHAVESH M
• Application Number:
  US08/405,542
• Time in Patent Office: 656 Days
• Field of Search: 382/187, 382/202, 382/203, 382/201, 382/188, 382/189, 395/146, 395/155, 345/156, 345/173, 345/179
• US Class Current: 382/202
• 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 an ellipse-type gesture input on a display screen of a computer system. A stroke is input by a user onto a computer screen, and the stroke is smoothed by reducing the number of points that represent the stroke. It is determined whether the smoothed stroke includes at least a predetermined minimum number of points, and, if so, angles between adjacent segments of the smoothed stroke and derivatives of the angles are calculated. It is determined if the stroke substantially represents an ellipse by checking if the stroke curves in one direction or more than one direction utilizing the angles and the derivatives of the angles. In addition, the stroke represents an ellipse if the end points are within a predetermined distance of each other, and if a sum of the derivatives of the angles is within a predetermined range of values. The method preferably includes selecting an object on the screen if the object is substantially overlapped by the smoothed stroke. An alternative embodiment includes determining whether the stroke is part of a multiple stroke gesture, and, if so, adding the stroke to stroke portions previously input by the user.

Claims

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

receiving a stroke input by a user onto a computer screen, the stroke being represented as a string of points;

smoothing said stroke by reducing the number of points that represent the stroke such that the points of the smoothed stroke are located at least a threshold distance apart from one another;

calculating angles between adjacent segments of said smoothed stroke and calculating derivatives of said angles; and

determining whether said stroke substantially represents an ellipse, the ellipse determining step utilizing said angles and said derivatives of said angles to determine whether said stroke substantially curves in one direction or curves in more than one direction, wherein said stroke is not considered to substantially represent an ellipse when said stroke does not curve in one direction, and summing said derivatives of said angles and checking whether said sum is within a predetermined range of values, wherein said stroke is not considered to substantially represent an ellipse when said sum is outside said range of values.

2. A method as recited in claim 1 further comprising the step of determining whether said smoothed stroke includes at least a predetermined minimum number of points and wherein said calculating and ellipse determining steps are only executed when said smoothed stroke includes at least the predetermined number of points.

3. A method as recited in claim 1 wherein said step of smoothing said stroke includes the substeps of:

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 the two adjacent points that are separated by less than the threshold distance with said new point.

4. A method as recited in claim 3 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.

5. A method as recited in claim 4 wherein the weight given to the location of a specific new point that is to be replaced as part of a subsequent repetition of the new point position calculating and adjacent point replacing substeps is proportional to the number of points that are represented by the specific new point.

6. A method as recited in claim 3 further comprising the steps of:

determining whether an ink object on a computer screen is substantially overlapped by said smoothed stroke; and

selecting said ink object when said ink object is overlapped by said smoothed stroke and said smoothed stroke substantially represents an ellipse.

7. A method as recited in claim 6 wherein said stroke and said object each have an associated bounding box, and wherein an object is substantially overlapped by said smoothed stroke when said bounding box of said stroke substantially overlaps said bounding box of said object.

8. A method as recited in claim 1 wherein said step of determining whether the stroke substantially represents an ellipse further includes the substep of determining whether a point on said stroke that is within a predetermined portion including an end point of said stroke is within a predetermined distance of an opposite end point of said stroke, wherein said stroke is not considered to be an ellipse gesture when said point is not within said predetermined distance of said opposite end point.

9. A method as recited in claim 8 wherein the predetermined range of values is about 6 to 8.5.

10. 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 part of a multiple stroke gesture.

11. 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;

calculating the angles formed between adjacent segments of the processed stroke and derivatives of said angles;

determining whether a first selected point within a predetermined portion including an end point of said stroke is within a predetermined distance of a second, opposite end point of said stroke, wherein said stroke is not considered to potentially represent an ellipse-type gesture when said first and second selected points are not within the predetermined distance; and

summing all of said derivatives of all of said angles and checking to determine whether the sum is within a predetermined range of values, wherein when the sum is within the predetermined range, the stroke is interpreted to potentially represent an ellipse-type gesture.

12. A method as recited in claim 11 wherein the predetermined range is about 6 to 8.5.

13. A method as recited in claim 11 wherein said first selected point is set to be a first end point of said stroke.

14. A method as recited in claim 13 wherein said second selected point is located within a predetermined portion of a second end of said stroke and is set to be the point in said second end of said stroke that is closest to said first selected point.

15. A method as recited in claim 11 further comprising the step of determining whether said processed stroke includes at least a predetermined minimum number of points and wherein said derivative calculating and summing steps are only executed when said processed stroke includes at least the predetermined number of points.

16. 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;

means for receiving a stroke input by a user onto said screen means by said pointer means, the stroke being represented as a string of points;

means for smoothing said stroke by reducing the number of points that represent the stroke such that the points of the smoothed stroke are located at least a threshold distance apart from one another;

means for determining whether said smoothed stroke includes at least a predetermined minimum number of points;

means for calculating angles between adjacent segments of said smoothed stroke and calculating derivatives of said angles; and

means for determining whether said stroke substantially represents an ellipse when said angles and said angle derivatives are calculated, the means for determining utilizing said angles and said derivatives of said angles in the determination of whether said stroke substantially represents an ellipse.

17. A computer system as recited in claim 16 wherein said pointer means is selected from the group comprising a stylus, a mouse, and a trackball pointing device.

18. A computer system as recited in claim 17 wherein said screen means and said pointer means are parts of a pen based computer system, and wherein said pointer means includes a stylus and a tablet.

19. A computer system as recited in claim 16 wherein said means for smoothing said stroke includes:

means for 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

means for replacing the two adjacent points that are separated by less than the threshold distance with said new point.

20. A computer system as recited in claim 16 wherein said means for determining whether said stroke substantially represents an ellipse includes means for summing said derivatives of said angles and means for checking if said sum is within a predetermined range of values.

21. A computer system as recited in claim 16 further comprising:

means for determining whether an object displayed on said screen means is substantially overlapped by said smoothed stroke; and

means for selecting said object when said object is overlapped by said smoothed stroke and said smoothed stroke substantially represents an ellipse.

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

receiving a stroke input by a user onto a computer screen, the stroke being represented as a string of points;

smoothing said stroke by reducing the number of points that represent the stroke such that the points of the smoothed stroke are located at least a threshold distance apart from one another;

calculating angles between adjacent segments of said smoothed stroke and calculating derivatives of said angles; and

determining whether said stroke substantially represents an ellipse, the ellipse determining step utilizing said angles and said derivatives of said angles to determine whether said stroke either substantially curves in one direction or substantially curves in more than one direction, wherein said stroke is not considered to substantially represent an ellipse when said stroke substantially curves in more than one direction.

23. A method as recited in claim 22 wherein said step of determining whether said stroke substantially represents an ellipse includes the steps of:

(a) summing the absolute values of said derivatives of said angles;

(b) taking the absolute value of the sum of said derivatives of said angles; and

(c) examining a difference between the results of steps (a) and (b) to determine whether said stroke substantially curves in one direction or substantially curves in more than one direction.

24. 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;

calculating the angles formed between adjacent segments of the processed stroke and derivatives of said angles;

summing all of said derivatives of all of said angles and checking to determine whether the sum is within a predetermined range of values, wherein when the sum is within the predetermined range, the stroke is interpreted to potentially represent an ellipse-type gesture.

25. A method as recited in claim 24 further comprising the step of determining whether said processed stroke includes at least a predetermined minimum number of points and wherein said derivative calculating and summing steps are only executed when said processed stroke includes at least the predetermined number of points.

26. A method as recited in claim 25 wherein said step of smoothing said stroke includes the substeps of:

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 the two adjacent points that are separated by less than the threshold distance with said new point.

27. A method as recited in claim 24 further comprising the steps of:

determining whether an object displayed on a computer screen is substantially overlapped by said smoothed stroke; and

selecting said object when said object is overlapped by said smoothed stroke and said smoothed stroke substantially represents an ellipse.