Multistroke gesture recognizer¶

New in version 1.9.0.

Warning

This is experimental and subject to change as long as this warning notice is present.

See kivy/examples/demo/multistroke/main.py for a complete application example.

Conceptual Overview¶

This module implements the Protractor gesture recognition algorithm.

Recognizer is the search/database API similar to GestureDatabase. It maintains a list of MultistrokeGesture objects and allows you to search for a user-input gestures among them.

ProgressTracker tracks the progress of a Recognizer.recognize() call. It can be used to interact with the running recognizer task, for example forcing it to stop half-way, or analyzing results as they arrive.

MultistrokeGesture represents a gesture in the gesture database (Recognizer.db). It is a container for UnistrokeTemplate objects, and implements the heap permute algorithm to automatically generate all possible stroke orders (if desired).

UnistrokeTemplate represents a single stroke path. It’s typically instantiated automatically by MultistrokeGesture, but sometimes you may need to create them manually.

Candidate represents a user-input gesture that is used to search the gesture database for matches. It is normally instantiated automatically by calling Recognizer.recognize().

Usage examples¶

See kivy/examples/demo/multistroke/main.py for a complete application example.

You can bind to events on Recognizer to track the state of all calls to Recognizer.recognize(). The callback function will receive an instance of ProgressTracker that can be used to analyze and control various aspects of the recognition process

from kivy.vector import Vector
from kivy.multistroke import Recognizer

gdb = Recognizer()

def search_start(gdb, pt):
    print("A search is starting with %d tasks" % (pt.tasks))

def search_stop(gdb, pt):
    # This will call max() on the result dictionary, so it's best to store
    # it instead of calling it 3 times consecutively
    best = pt.best
    print("Search ended (%s). Best is %s (score %f, distance %f)" % (
        pt.status, best['name'], best['score'], best['dist'] ))

# Bind your callbacks to track all matching operations
gdb.bind(on_search_start=search_start)
gdb.bind(on_search_complete=search_stop)

# The format below is referred to as `strokes`, a list of stroke paths.
# Note that each path shown here consists of two points, ie a straight
# line; if you plot them it looks like a T, hence the name.
gdb.add_gesture('T', [
    [Vector(30, 7), Vector(103, 7)],
    [Vector(66, 7), Vector(66, 87)]])

# Now you can search for the 'T' gesture using similar data (user input).
# This will trigger both of the callbacks bound above.
gdb.recognize([
    [Vector(45, 8), Vector(110, 12)],
    [Vector(88, 9), Vector(85, 95)]])

On the next Clock tick, the matching process starts (and, in this case, completes).

To track individual calls to Recognizer.recognize(), use the return value (also a ProgressTracker instance)

# Same as above, but keep track of progress using returned value
progress = gdb.recognize([
    [Vector(45, 8), Vector(110, 12)],
    [Vector(88, 9), Vector(85, 95)]])

progress.bind(on_progress=my_other_callback)
print(progress.progress) # = 0

# [ assuming a kivy.clock.Clock.tick() here ]

print(result.progress) # = 1

Algorithm details¶

For more information about the matching algorithm, see:

“Protractor: A fast and accurate gesture recognizer” by Yang Li: http://yangl.org/pdf/protractor-chi2010.pdf
“$N-Protractor” by Lisa Anthony and Jacob O. Wobbrock: http://depts.washington.edu/aimgroup/proj/dollar/ndollar-protractor.pdf
Some of the code is derived from the JavaScript implementation here:: http://depts.washington.edu/aimgroup/proj/dollar/ndollar.html

class kivy.multistroke.Recognizer(**kwargs)[source]¶

Bases: kivy.event.EventDispatcher

Recognizer provides a gesture database with matching facilities.

Events

on_search_start: Fired when a new search is started using this Recognizer.
on_search_complete: Fired when a running search ends, for whatever reason. (use ProgressTracker.status to find out)

Properties

db

A ListProperty that contains the available MultistrokeGesture objects.

db is a ListProperty and defaults to []

add_gesture(name, strokes, **kwargs)[source]¶: Add a new gesture to the database. This will instantiate a new MultistrokeGesture with strokes and append it to self.db.

Note

If you already have instantiated a MultistrokeGesture object and wish to add it, append it to Recognizer.db manually.

export_gesture(filename=None, **kwargs)[source]¶

Export a list of MultistrokeGesture objects. Outputs a base64-encoded string that can be decoded to a Python list with the parse_gesture() function or imported directly to self.db using Recognizer.import_gesture(). If filename is specified, the output is written to disk, otherwise returned.

This method accepts optional Recognizer.filter() arguments.

filter(**kwargs)[source]¶

filter() returns a subset of objects in self.db, according to given criteria. This is used by many other methods of the Recognizer; the arguments below can for example be used when calling Recognizer.recognize() or Recognizer.export_gesture(). You normally don’t need to call this directly.

Arguments

name

Limits the returned list to gestures where MultistrokeGesture.name matches given regular expression(s). If re.match(name, MultistrokeGesture.name) tests true, the gesture is included in the returned list. Can be a string or an array of strings

gdb = Recognizer()

# Will match all names that start with a capital N
# (ie Next, New, N, Nebraska etc, but not "n" or "next")
gdb.filter(name='N')

# exactly 'N'
gdb.filter(name='N$')

# Nebraska, teletubbies, France, fraggle, N, n, etc
gdb.filter(name=['[Nn]', '(?i)T', '(?i)F'])

priority

Limits the returned list to gestures with certain MultistrokeGesture.priority values. If specified as an integer, only gestures with a lower priority are returned. If specified as a list (min/max)

# Max priority 50
gdb.filter(priority=50)

# Max priority 50 (same result as above)
gdb.filter(priority=[0, 50])

# Min priority 50, max 100
gdb.filter(priority=[50, 100])

When this option is used, Recognizer.db is automatically sorted according to priority, incurring extra cost. You can use force_priority_sort to override this behavior if your gestures are already sorted according to priority.

orientation_sensitive

Limits the returned list to gestures that are orientation sensitive (True), gestures that are not orientation sensitive (False) or None (ignore template sensitivity, this is the default).

numstrokes

Limits the returned list to gestures that have the specified number of strokes (in MultistrokeGesture.strokes). Can be a single integer or a list of integers.

numpoints

Limits the returned list to gestures that have specific MultistrokeGesture.numpoints values. This is provided for flexibility, do not use it unless you understand what it does. Can be a single integer or a list of integers.

force_priority_sort

Can be used to override the default sort behavior. Normally MultistrokeGesture objects are returned in priority order if the priority option is used. Setting this to True will return gestures sorted in priority order, False will return in the order gestures were added. None means decide automatically (the default).

Note

For improved performance, you can load your gesture database in priority order and set this to False when calling Recognizer.recognize()

db

Can be set if you want to filter a different list of objects than Recognizer.db. You probably don’t want to do this; it is used internally by import_gesture().

import_gesture(data=None, filename=None, **kwargs)[source]¶

Import a list of gestures as formatted by export_gesture(). One of data or filename must be specified.

This method accepts optional Recognizer.filter() arguments, if none are specified then all gestures in specified data are imported.

parse_gesture(data)[source]¶: Parse data formatted by export_gesture(). Returns a list of MultistrokeGesture objects. This is used internally by import_gesture(), you normally don’t need to call this directly.

prepare_templates(**kwargs)[source]¶

This method is used to prepare UnistrokeTemplate objects within the gestures in self.db. This is useful if you want to minimize punishment of lazy resampling by preparing all vectors in advance. If you do this before a call to Recognizer.export_gesture(), you will have the vectors computed when you load the data later.

This method accepts optional Recognizer.filter() arguments.

force_numpoints, if specified, will prepare all templates to the given number of points (instead of each template’s preferred n; ie UnistrokeTemplate.numpoints). You normally don’t want to do this.

recognize(strokes, goodscore=None, timeout=0, delay=0, **kwargs)[source]¶

Search for gestures matching strokes. Returns a ProgressTracker instance.

This method accepts optional Recognizer.filter() arguments.

Arguments

strokes: A list of stroke paths (list of lists of Vector objects) that will be matched against gestures in the database. Can also be a Candidate instance.

Warning

If you manually supply a Candidate that has a skip-flag, make sure that the correct filter arguments are set. Otherwise the system will attempt to load vectors that have not been computed. For example, if you set skip_bounded and do not set orientation_sensitive to False, it will raise an exception if an orientation_sensitive UnistrokeTemplate is encountered.
goodscore: If this is set (between 0.0 - 1.0) and a gesture score is equal to or higher than the specified value, the search is immediately halted and the on_search_complete event is fired (+ the on_complete event of the associated ProgressTracker instance). Default is None (disabled).
timeout: Specifies a timeout (in seconds) for when the search is aborted and the results returned. This option applies only when max_gpf is not 0. Default value is 0, meaning all gestures in the database will be tested, no matter how long it takes.
max_gpf: Specifies the maximum number of MultistrokeGesture objects that can be processed per frame. When exceeded, will cause the search to halt and resume work in the next frame. Setting to 0 will complete the search immediately (and block the UI).

Warning

This does not limit the number of UnistrokeTemplate objects matched! If a single gesture has a million templates, they will all be processed in a single frame with max_gpf=1!
delay: Sets an optional delay between each run of the recognizer loop. Normally, a run is scheduled for the next frame until the tasklist is exhausted. If you set this, there will be an additional delay between each run (specified in seconds). Default is 0, resume in the next frame.
force_numpoints: forces all templates (and candidate) to be prepared to a certain number of points. This can be useful for example if you are evaluating templates for optimal n (do not use this unless you understand what it does).

transfer_gesture(tgt, **kwargs)[source]¶

Transfers MultistrokeGesture objects from Recognizer.db to another Recognizer instance tgt.

This method accepts optional Recognizer.filter() arguments.

class kivy.multistroke.ProgressTracker(candidate, tasks, **kwargs)[source]¶

Bases: kivy.event.EventDispatcher

Represents an ongoing (or completed) search operation. Instantiated and returned by the Recognizer.recognize() method when it is called. The results attribute is a dictionary that is updated as the recognition operation progresses.

Note

You do not need to instantiate this class.

Arguments

candidate: Candidate object to be evaluated
tasks: Total number of gestures in tasklist (to test against)

Events

on_progress: Fired for every gesture that is processed
on_result: Fired when a new result is added, and it is the first match for the name so far, or a consecutive match with better score.
on_complete: Fired when the search is completed, for whatever reason. (use ProgressTracker.status to find out)

Attributes

results

A dictionary of all results (so far). The key is the name of the gesture (ie UnistrokeTemplate.name usually inherited from MultistrokeGesture). Each item in the dictionary is a dict with the following entries:

name
Name of the matched template (redundant)

score
Computed score from 1.0 (perfect match) to 0.0

dist
Cosine distance from candidate to template (low=closer)

gesture
The MultistrokeGesture object that was matched

best_template
Index of the best matching template (in MultistrokeGesture.templates)

template_results
List of distances for all templates. The list index corresponds to a UnistrokeTemplate index in gesture.templates.

status

search: Currently working
stop: Was stopped by the user (stop() called)
timeout: A timeout occurred (specified as timeout= to recognize())
goodscore: The search was stopped early because a gesture with a high enough score was found (specified as goodscore= to recognize())
complete: The search is complete (all gestures matching filters were tested)

best¶: Return the best match found by recognize() so far. It returns a dictionary with three keys, ‘name’, ‘dist’ and ‘score’ representing the template’s name, distance (from candidate path) and the computed score value. This is a Python property.

progress¶: Returns the progress as a float, 0 is 0% done, 1 is 100%. This is a Python property.

stop()[source]¶: Raises a stop flag that is checked by the search process. It will be stopped on the next clock tick (if it is still running).

class kivy.multistroke.MultistrokeGesture(name, strokes=None, **kwargs)[source]¶

Bases: builtins.object

MultistrokeGesture represents a gesture. It maintains a set of strokes and generates unistroke (ie UnistrokeTemplate) permutations that are used for evaluating candidates against this gesture later.

Arguments

name

Identifies the name of the gesture - it is returned to you in the results of a Recognizer.recognize() search. You can have any number of MultistrokeGesture objects with the same name; many definitions of one gesture. The same name is given to all the generated unistroke permutations. Required, no default.

strokes

A list of paths that represents the gesture. A path is a list of Vector objects:

gesture = MultistrokeGesture('my_gesture', strokes=[
  [Vector(x1, y1), Vector(x2, y2), ...... ], # stroke 1
  [Vector(), Vector(), Vector(), Vector() ]  # stroke 2
  #, [stroke 3], [stroke 4], ...
])

For template matching purposes, all the strokes are combined to a single list (unistroke). You should still specify the strokes individually, and set stroke_sensitive True (whenever possible).

Once you do this, unistroke permutations are immediately generated and stored in self.templates for later, unless you set the permute flag to False.

priority

Determines when Recognizer.recognize() will attempt to match this template, lower priorities are evaluated first (only if a priority filter is used). You should use lower priority on gestures that are more likely to match. For example, set user templates at lower number than generic templates. Default is 100.

numpoints

Determines the number of points this gesture should be resampled to (for matching purposes). The default is 16.

stroke_sensitive

Determines if the number of strokes (paths) in this gesture is required to be the same in the candidate (user input) gesture during matching. If this is False, candidates will always be evaluated, disregarding the number of strokes. Default is True.

orientation_sensitive

Determines if this gesture is orientation sensitive. If True, aligns the indicative orientation with the one of eight base orientations that requires least rotation. Default is True.

angle_similarity

This is used by the Recognizer.recognize() function when a candidate is evaluated against this gesture. If the angles between them are too far off, the template is considered a non-match. Default is 30.0 (degrees)

permute

If False, do not use Heap Permute algorithm to generate different stroke orders when instantiated. If you set this to False, a single UnistrokeTemplate built from strokes is used.

add_stroke(stroke, permute=False)[source]¶: Add a stroke to the self.strokes list. If permute is True, the permute() method is called to generate new unistroke templates

get_distance(cand, tpl, numpoints=None)[source]¶

Compute the distance from this Candiate to a UnistrokeTemplate. Returns the Cosine distance between the stroke paths.

numpoints will prepare both the UnistrokeTemplate and Candidate path to n points (when necessary), you probably don’t want to do this.

match_candidate(cand, **kwargs)[source]¶

Match a given candidate against this MultistrokeGesture object. Will test against all templates and report results as a list of four items:

index 0
Best matching template’s index (in self.templates)

index 1
Computed distance from the template to the candidate path

index 2
List of distances for all templates. The list index corresponds to a UnistrokeTemplate index in self.templates.

index 3
Counter for the number of performed matching operations, ie templates matched against the candidate

permute()[source]¶

Generate all possible unistroke permutations from self.strokes and save the resulting list of UnistrokeTemplate objects in self.templates.

Quote from http://faculty.washington.edu/wobbrock/pubs/gi-10.2.pdf

We use Heap Permute [16] (p. 179) to generate all stroke orders
in a multistroke gesture. Then, to generate stroke directions for
each order, we treat each component stroke as a dichotomous
[0,1] variable. There are 2^N combinations for N strokes, so we
convert the decimal values 0 to 2^N-1, inclusive, to binary
representations and regard each bit as indicating forward (0) or
reverse (1). This algorithm is often used to generate truth tables
in propositional logic.

See section 4.1: “$N Algorithm” of the linked paper for details.

Warning

Using heap permute for gestures with more than 3 strokes can result in very large number of templates (a 9-stroke gesture = 38 million templates). If you are dealing with these types of gestures, you should manually compose all the desired stroke orders.

class kivy.multistroke.UnistrokeTemplate(name, points=None, **kwargs)[source]¶

Bases: builtins.object

Represents a (uni)stroke path as a list of Vectors. Normally, this class is instantiated by MultistrokeGesture and not by the programmer directly. However, it is possible to manually compose UnistrokeTemplate objects.

Arguments

name: Identifies the name of the gesture. This is normally inherited from the parent MultistrokeGesture object when a template is generated.
points: A list of points that represents a unistroke path. This is normally one of the possible stroke order permutations from a MultistrokeGesture.
numpoints: The number of points this template should (ideally) be resampled to before the matching process. The default is 16, but you can use a template-specific settings if that improves results.
orientation_sensitive: Determines if this template is orientation sensitive (True) or fully rotation invariant (False). The default is True.

Note

You will get an exception if you set a skip-flag and then attempt to retrieve those vectors.

add_point(p)[source]¶: Add a point to the unistroke/path. This invalidates all previously computed vectors.

prepare(numpoints=None)[source]¶: This function prepares the UnistrokeTemplate for matching given a target number of points (for resample). 16 is optimal.

class kivy.multistroke.Candidate(strokes=None, numpoints=16, **kwargs)[source]¶

Bases: builtins.object

Represents a set of unistroke paths of user input, ie data to be matched against a UnistrokeTemplate object using the Protractor algorithm. By default, data is precomputed to match both rotation bounded and fully invariant UnistrokeTemplate objects.

Arguments

strokes: See MultistrokeGesture.strokes for format example. The Candidate strokes are simply combined to a unistroke in the order given. The idea is that this will match one of the unistroke permutations in MultistrokeGesture.templates.
numpoints: The Candidate’s default N; this is only for a fallback, it is not normally used since n is driven by the UnistrokeTemplate we are being compared to.
skip_bounded: If True, do not generate/store rotation bounded vectors
skip_invariant: If True, do not generate/store rotation invariant vectors

Note that you WILL get errors if you set a skip-flag and then attempt to retrieve the data.

add_stroke(stroke)[source]¶: Add a stroke to the candidate; this will invalidate all previously computed vectors

get_angle_similarity(tpl, **kwargs)[source]¶: (Internal use only) Compute the angle similarity between this Candidate and a UnistrokeTemplate object. Returns a number that represents the angle similarity (lower is more similar).

get_protractor_vector(numpoints, orientation_sens)[source]¶: (Internal use only) Return vector for comparing to a UnistrokeTemplate with Protractor

get_start_unit_vector(numpoints, orientation_sens)[source]¶: (Internal use only) Get the start vector for this Candidate, with the path resampled to numpoints points. This is the first step in the matching process. It is compared to a UnistrokeTemplate object’s start vector to determine angle similarity.

prepare(numpoints=None)[source]¶: Prepare the Candidate vectors. self.strokes is combined to a single unistroke (connected end-to-end), resampled to numpoints points, and then the vectors are calculated and stored in self.db (for use by get_distance and get_angle_similarity)

« Metrics

Parser utilities »

Version

Quick search

Table Of Contents

Multistroke gesture recognizer¶

Conceptual Overview¶

Usage examples¶

Algorithm details¶