Prediction-based touch contact tracking

Patent metadata

Field	Value
Publication number	US-9542092-B2
Application number	US-201113152991-A
Country	US
Kind code	B2
Filing date	Jun 3, 2011
Priority date	Feb 12, 2011
Publication date	Jan 10, 2017
Grant date	Jan 10, 2017

Abstract

In embodiments of prediction-based touch contact tracking, touch input sensor data is recognized as a series of components of a contact on a touch-screen display. A first component of the contact can be identified, and a second component can be determined to correlate to the contact. The first component and the second component can then be associated to represent a tracking of the contact. Subsequent components of the contact can be determined and associated with the previous components of the contact to further represent the tracking of the contact.

First claim

The invention claimed is:

1. A method, comprising:
recognizing touch input sensor data as a series of sequential components of a plurality of contacts on a touch-screen display;
identifying first components of each of the contacts;
identifying second components of each of the contacts by performing operations comprising:
identifying unassociated components of the contacts;
calculating sums of maximum distances between each of the first components and each of the unassociated components, a first sum calculated based on the distances between a first one of the first components and at least two of the unassociated components, at least a second sum calculated based on the distances between a second one of the first components and the at least two unassociated components;
selecting a set of pairings of the first components and the unassociated components, a first pairing selected corresponding to a largest sum, the first pairing selected based on a minimum distance between an unassociated component and a first component of the largest sum, the pairings in the set of pairings successively selected based on a next largest sum;
identifying the second components of each of the contacts from the unassociated components based on the selected set of pairings;

for each of the contacts, performing operations comprising:
associating a first component and a second component to represent a tracking of a respective contact; and
assigning a same identifier identifying a gesture to the first component and to the second component of the respective contact.

2. A method as recited in claim 1 , further comprising, for each of the contacts:
determining that a subsequent component correlates to the respective contact; and
assigning the same identifier to the subsequent component that combines with the first, second, and subsequent components to represent the tracking of the respective contact corresponding to the gesture.

3. A method as recited in claim 2 , wherein the determining that the subsequent component correlates to the respective contact comprises:
predicting a component position of the subsequent component from the tracking of the contact;
correlating the predicted component position to the subsequent component;
validating that the predicted component position correlates to the subsequent component based on a nearest-neighbor contact mapping criteria; and
associating the subsequent component with the same identifier identifying the gesture based on the validation.

4. A method as recited in claim 3 , wherein the nearest-neighbor contact mapping criteria evaluates distance from the predicted component position to one or more components of the contact.

5. A method as recited in claim 3 , further comprising merging multiple contacts that alias to a single unassociated component into the single unassociated component.

6. A method as recited in claim 5 , wherein said merging comprises determining an unreliable association of the components after the nearest-neighbor contact mapping, the unreliable association based on a total number of the unassociated components being greater than a difference between a number of the components and a number of the contacts.

7. A computing device, comprising:
a touch-screen display;
a touch input module configured to recognize two-dimensional touch input sensor data from a touch sensor array;
at least a memory and a processor to implement a contact tracking service configured to:
convert the two-dimensional touch input sensor data from the touch sensor array into a sequential series of components of a plurality of contacts on the touch-screen display;
identify first components of each of the contacts;
identify second components of each of the contacts by the contact tracking service further configured to:
identify unassociated components of the contacts;
calculate sums of maximum distances between each of the first components and each of the unassociated components, a first sum calculated based on the distances between a first one of the first components and at least two of the unassociated components, at least a second sum calculated based on the distances between a second one of the first components and the at least two unassociated components;
select a set of pairings of the first components and the unassociated second components, a first pairing selected corresponding to a largest sum, the first pairing selected based on a minimum distance between an unassociated component and a first component of the largest sum, the pairings in the set of pairings successively selected based on a next largest sum;
identify the second components of each of the contacts from the unassociated components based on the selected set of pairings;

for each of the contacts, the contact tracking service further configured to:
associate a first component and a second component to represent a tracking of a respective contact; and
assign a same identifier to the first component and to the second component of the respective contact as corresponding to a gesture.

8. A computing device as recited in claim 7 , wherein, for each of the contacts, the contact tracking service is further configured to:
determine that an additional component correlates to the respective contact; and
assign the same identifier to the additional component that represents the tracking of the respective contact corresponding to the gesture.

9. A computing device as recited in claim 8 , wherein, to determine that the additional component correlates to the respective contact, the contact tracking service is further configured to:
predict a component position of the additional component from the tracking of the contact, the tracking associated with the first and second components;
correlate the predicted component position to the additional component;
validate that the predicted component position correlates to the additional component based on a nearest-neighbor contact mapping criteria; and
associate the additional component of the contact with the same identifier as corresponding to the gesture based on the validation.

10. A computing device as recited in claim 9 , wherein the nearest-neighbor contact mapping criteria evaluates distance from the predicted component position to one or more components of the contact.

11. A computing device as recited in claim 9 , wherein the contact tracking service is further configured to merge multiple contacts that alias to a single unassociated component into the single unassociated component.

12. A computing device as recited in claim 11 , wherein, to merge the multiple contacts that alias to the single unassociated component, the contact tracking service is further configured to determine an unreliable association of the components after the nearest-neighbor contact mapping, the unreliable association based on a total number of the unassociated components being greater than a difference between a number of the components and a number of the contacts.

13. A computing device, comprising:
a touch input module configured to receive touch input sensor data as a sequential series of components of a plurality of contacts for a gesture input on a touch screen display;
a contact tracking service configured to generate a normalized two-dimensional grid of the touch input sensor data;
a memory and processor system configured to implement the contact tracking service and components of a contact tracking service, comprising:
a connected components analyzer configured to generate an array of connected components that represent the plurality of contacts for the gesture input, the array generated based on an input of the no

Assignees

• Zhao Weidong
• Stevens David A
• Uzelac Aleksandar
• Benko Hrvoje
• Miller John L
• Microsoft Technology Licensing Llc

Inventors

• Zhao Weidong
• Stevens David A
• Uzelac Aleksandar
• Benko Hrvoje
• Miller John L

Classifications

• G06F3/0418

  for error correction or compensation, e.g. based on parallax, calibration or alignment · CPC title

• G06F3/04883 Primary

  for inputting data by handwriting, e.g. gesture or text · CPC title

• G06F3/04886

  by partitioning the display area of the touch-screen or the surface of the digitising tablet into independently controllable areas, e.g. virtual keyboards or menus · CPC title

• G06F3/0416

  Control or interface arrangements specially adapted for digitisers · CPC title

• G06F3/0488

  using a touch-screen or digitiser, e.g. input of commands through traced gestures · CPC title