Parallel touch point detection using processor graphics

Patent metadata

Field	Value
Publication number	US-9448663-B2
Application number	US-201314129427-A
Country	US
Kind code	B2
Filing date	Jun 28, 2013
Priority date	Jun 28, 2013
Publication date	Sep 20, 2016
Grant date	Sep 20, 2016

Abstract

Technologies for touch point detection include a computing device configured to receive input frames from a touch screen, identify touch point centroids and cluster boundaries, and track touch points. The computing device may group cells of the input frame into blocks. Using a processor graphics, the computing device may dispatch one thread per block to identify local maxima of the input frame and merge centroids within a touch distance threshold. The computing device may dispatch one thread per centroid to detect cluster boundaries. The computing device may dispatch one thread per previously identified touch point to assign an identifier of a previously tracked touch point to a touch point within a tracking distance threshold, remove duplicate identifiers, and assign unassigned identifiers to closest touch points. The computing device may dispatch one thread per block to assign unique identifiers to each unassigned touch point. Other embodiments are described and claimed.

First claim

The invention claimed is:

1. A computing device for touch point centroid detection, the computing device comprising:
a processor graphics;
a touch screen;
an input frame module to receive an input frame from the touch screen, the input frame defining a plurality of cells, each cell having a touch data value;
a centroid detection module to:
group the cells of the input frame into a plurality of blocks, wherein each block includes a predetermined number of cells;
search for a local maximum cell within each of the plurality of blocks, the local maximum cell having a touch data value having a predefined relationship with a signal threshold value, wherein to search for the local maximum cell comprises to assign one search task per block to be executed by the processor graphics;
identify each of the local maximum cells as a centroid;
merge centroids that are located within a touch distance threshold of each other, wherein to merge the centroids comprises to select a merged centroid from two or more centroids that are located within the touch distance threshold of each other, and wherein to merge the centroids comprises to assign one merge task per block to be executed by the processor graphics; and
detect a cluster boundary around each of the merged centroids, each cluster boundary to include at least one cell of the input frame, wherein to detect the cluster boundary around each of the merged centroids comprises to assign one detection task per merged centroid to be executed by the processor graphics; and

a parallel dispatch module to (i) execute the search tasks in parallel, (ii) execute the merge tasks in parallel, and (iii) execute the detection tasks in parallel using multiple execution units of the processor graphics.

2. The computing device of claim 1 , wherein to merge the centroids comprises to:
traverse the blocks in vertical stripes and merging centroids in neighboring blocks separated vertically by less than the touch distance threshold;
traverse the blocks in horizontal stripes and merging centroids in neighboring blocks separated horizontally by less than the touch distance threshold; and
traverse the blocks in diagonally adjacent pairs and merging centroids in neighboring blocks separated diagonally by less than the touch distance threshold.

3. The computing device of claim 2 , wherein to:
traverse the blocks in vertical stripes comprises to:
dispatch one task per block using the processor graphics, wherein each task comprises to merge a centroid within the block that is located within the touch distance threshold from another centroid located in the neighboring block; and
set data dependencies between the tasks using a scoreboard of the processor graphics to traverse the blocks in vertical stripes;

traverse the blocks in horizontal stripes comprises to:
dispatch one task per block using the processor graphics, wherein each task comprises to merge a centroid within the block that is located within the touch distance threshold from another centroid located in the neighboring block; and
set data dependencies between the tasks using the scoreboard of the processor graphics to traverse the blocks in horizontal stripes; and

traverse the blocks in diagonally adjacent pairs comprises to:
dispatch one task per square group of four blocks using the processor graphics, wherein each task comprises to merge centroids within the square group of blocks that are located within the touch distance threshold from another centroid located in a neighboring block; and
set data dependencies between the tasks using the scoreboard of the processor graphics to traverse the blocks in diagonally adjacent pairs.

4. The computing device of claim 1 , wherein to detect the cluster boundary around each of the merged centroids comprises to:
load data from the input frame for cells surrounding the centroid;
zero cells including a touch data value less than the signal threshold value;
define an input window including cells of the input frame surrounding the cluster boundary;
replicate edge cells of the cluster to build a comparison window having a size equal to a size of the input window;
subtract a touch data value of each edge cell of the input window from a touch data value of a corresponding replicated edge cell of the comparison window to determine a plurality of edge cell differences;
increase the comparison window size in response to a determination that none of the edge cell differences is less than zero; and
count a number of valid cells in the input window in response to a determination that any of the edge cell differences is less than zero, each valid cell having a corresponding edge cell difference not less than zero.

5. The computing device of claim 1 , wherein to detect the cluster boundary around each of the merged centroids comprises to:
load data from the input frame for cells surrounding the centroid;
zero cells including a touch data value less than the signal threshold value;
calculate a first maximum of edge cells within the first window;
calculate a sum of edge cells within a second window of the input frame surrounding the centroid, the second window surrounding the first window;
calculate a second maximum of edge cells within the second window;
determine whether the sum is less than the number of edge cells within the second window multiplied by the signal threshold;
determine whether the second maximum is greater than the first maximum;
increase a size of the first window and the second window in response to a determination that the sum is not less than the number of edge cells within the second window multiplied by the signal threshold and a determination that the second maximum is not greater than the first maximum; and
count a number of valid cells in the first window in response to a determination that the sum is less than the number of edge cells within the second window multiplied by the signal threshold or a determination that the second maximum is greater than the first maximum.

6. The computing device of claim 1 , wherein the centroid detection module is to perform at least one of to: search for the local maximum cell, merge centroids, or detect the cluster boundary using a single-instruction-multiple-data instruction of the processor graphics.

7. A method for detecting touch point centroids on a computing device, the method comprising:
receiving, on the computing device, an input frame from a touch screen of the computing device, the input frame defining a plurality of cells, each cell having a touch data value;
grouping, on the computing device, the cells of the input frame into a plurality of blocks, wherein each block includes a predetermined number of cells;
searching, on the computing device, for a local maximum cell within each of the plurality of blocks, the local maximum cell having a touch data value having a predefined relationship with a signal threshold value, wherein searching for the local maximum cell comprises assigning one search task per block to be executed by a processor graphics of the computing device and executing the search tasks in parallel using multiple execution units of the processor graphics;
identifying, on the computing device, each of the local maximum cells as a centroid;
merging, on the computing device, centroids that are located within a touch distance threshold of each other, wherein merging the centroids comprises selecting a merged centroid from two or more centroids that are located within the touch distance threshold of each other, and wherein merging the centroids comprises assigning one merge task per block to be executed by the processor graphics and executing the merge tasks in parallel using multiple execution units of the processor graphics; and
detecting, on t

Assignees

• Intel Corp

Inventors

• Gandra Chaitanya R
• Vembu Balaji
• Kumar Arvind A
• Shah Nilesh V

Classifications

• G06F3/0488

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

• G06F3/0416 Primary

  Control or interface arrangements specially adapted for digitisers · CPC title

• G06F2203/04104

  Multi-touch detection in digitiser, i.e. details about the simultaneous detection of a plurality of touching locations, e.g. multiple fingers or pen and finger · CPC title

• G06F3/0418 Primary

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

• G06T1/20

  Processor architectures; Processor configuration, e.g. pipelining · CPC title