Gesture Recognition on Computing Device

• US 20110066984A1
• Filed: 12/17/2009
• Published: 03/17/2011
• Est. Priority Date: 09/16/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Li, Yang
• Granted Patent: US 8,341,558 B2
• Time in Patent Office: Days
• US Class Current: 715/863
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 3/04883 for inputting data by handwriting, e.g. gesture or text
• CPC Class Codes: G06V 10/242 by image rotation, e.g. by 90 degrees
• CPC Class Codes: G06V 40/20 Movements or behaviour, e.g. gesture recognition recognition of facial expressions G06V40/16

Abstract

A computer-implemented user interface method is disclosed. The method includes displaying information on a touchscreen of a computing device, receiving from a user of the device an input drawn on the touchscreen, correlating the input to a template, where the correlating includes employing a closed-form solution to find a rotation that reduces angular distance between the input and the template, and providing output based on a result of the correlating.

Claims

1. A computer-implemented user interface method, comprising

displaying information on a touchscreen of a computing device;

receiving from a user of the device an input drawn on the touchscreen;

correlating the input to a template, where the correlating comprises employing a closed-form solution to find a rotation that reduces angular distance between the input and the template; and

providing output based on a result of the correlating.

2. The method of claim 1, where displaying the information comprises displaying content from an operating system or application operating on the device, and the correlating comprises identifying a user-defined glyph corresponding to the input.

3. The method of claim 1, where the input is defined by a pointer contact with the touchscreen followed by a pointer release from the touchscreen, and a pointer path traced on the touchscreen between the pointer contact and the pointer release.

4. The method of claim 1, comprising:

preprocessing the input, before the correlating, in accordance with a predefined uniform representation.

5. The method of claim 4, where:

the predefined uniform representation comprises a vector representation of N points;

the correlating comprises finding an angle between a vector representation of the input and a vector representation of the template in an N-dimensional space to generate a similarity score; and

the employing comprises calculating the rotation from the vector representation of the input and the vector representation of the template.

6. The method of claim 5, where:

the correlating comprises generating the similarity score, S, in accordance with a first equation,

7. The method of claim 4, where:

the preprocessing comprises

resampling the input into a fixed number, N, equidistantly-spaced points,

translating the points to place a centroid of the points at an origin of a coordinate space,

determining whether the input is to be considered orientation invariant,

rotating the translated points around the centroid in accordance with an indicative angle of the translated points, if the input is orientation invariant, to define an input vector, and

aligning the translated points with one of multiple base orientations in the coordinate space, if the input is not orientation invariant, to define the input vector; and

the correlating comprises

calculating the rotation in accordance with an arc tangent function,

rotating the template in accordance with the rotation to generate a template vector, and

calculating a similarity score from the input vector and the template vector in accordance with an arc cosine function.

8. An article comprising a computer-readable data storage medium storing program code operable to cause one or more machines to perform operations comprising:

receiving first data indicating a gesture template;

modifying the first data to form a first vector representation;

saving the first vector representation;

receiving second data indicating a gesture input in a user interface;

modifying the second data to form a second vector representation;

calculating an adjustment angle using both the first and second vector representations as input; and

generating a score of similarity between the first and second vector representations, taking the adjustment angle into account, to assess whether the gesture input matches the gesture template.

9. The article of claim 8, where:

the generating comprises generating the score of similarity, S, in accordance with a first equation,

10. The article of claim 8, where:

the calculating comprises calculating the adjustment angle in accordance with an arc tangent function; and

the generating comprises generating the score of similarity in accordance with an arc cosine function.

11. The article of claim 10, where taking the adjustment angle into account comprises rotating the first vector representation by the adjustment angle, at runtime, before generating the score of similarity.

12. The article of claim 10, where modifying the first data and modifying the second data each comprise modifying input data by performing operations comprising:

resampling the input data into a fixed number, N, equidistantly-spaced points,

translating the points to place a centroid of the points at an origin of a coordinate space,

determining whether the input data is to be considered orientation invariant,

rotating the translated points around the centroid in accordance with an indicative angle of the translated points, if the input data is orientation invariant, to define an input vector, and

aligning the translated points with one of multiple base orientations in the coordinate space, if the input data is not orientation invariant, to define the input vector.

13. The article of claim 8, the operations comprising assessing whether the gesture input matches the gesture template based on the score of similarity, where the assessing comprises:

combining the score of similarity with an additional score of similarity, between the second vector representation and an additional vector representation of additional data indicating the gesture template, to form a composite similarity score; and

comparing the composite similarity score with one or more other similarity scores corresponding to other gesture templates to find a closest match.

14. A system comprising:

a graphical display to present at least a portion of a graphical user interface; and

a computing device including a gesture recognizer to receive user traces obtained with respect to the graphical display and to identify a user gesture in a received user trace in accordance with a process;

where the user gesture corresponds to a predefined gesture that is a valid input to the graphical user interface,

the predefined gesture is represented by one or more previously received user traces, and

the process correlates the received user trace with the one or more previously received user traces by employing a closed-form solution to find one or more rotations that reduce angular distance between the received user trace and respective ones of the one or more previously received user traces.

15. The system of claim 14, where the gesture recognizer is programmed to perform the process comprising:

modifying the one or more previously received user traces to form one or more first vector representations;

modifying the received user trace to form a second vector representation;

calculating an adjustment angle, for each of the one or more first vector representations, using data of the second vector representation and data of the first vector representation as input;

generating a score of similarity, for each of the one or more first vector representations, taking each respective adjustment angle into account.

16. The system of claim 15, where:

the generating comprises generating the score of similarity, S, in accordance with a first equation,

17. The system of claim 15, where:

the calculating comprises calculating the adjustment angle in accordance with an arc tangent function; and

the generating comprises generating the score of similarity in accordance with an arc cosine function.

18. The system of claim 17, where taking the adjustment angle into account comprises rotating the first vector representation by the adjustment angle, at runtime, before generating the score of similarity.

19. The system of claim 17, where modifying the one or more previously received user traces and modifying the received user trace each comprise modifying input data by performing operations comprising:

resampling the input data into a fixed number, N, equidistantly-spaced points,

translating the points to place a centroid of the points at an origin of a coordinate space,

determining whether the input data is to be considered orientation invariant,

rotating the translated points around the centroid in accordance with an indicative angle of the translated points, if the input data is orientation invariant, to define an input vector, and

aligning the translated points with one of multiple base orientations in the coordinate space, if the input data is not orientation invariant, to define the input vector.

20. The system of claim 15, comprising a mobile phone including the graphical display and the computing device, and the graphical display comprises a touchscreen display device.