Dynamic time warping for the recognition of single-stroke input

Abstract

The work at hand presents thorough investigations of dynamic time warping (DTW) for on-line recognition of single-stroke input. We survey and give a systematization of nearest neighbor methods and show how concepts of DTW outperform current approaches without adding too much complexity. Observing mostly conservative and ‘expensive’ utilization and underestimation of DTW in this field, the contribution of this work is to give best practices for enhancing template matching by application of DTW which can be implemented in few lines of code. Our survey is substantiated by tests regarding questions of proper feature selection, pre-processing, and suitable parametrization. To provide flexible, device-independent recognition and as human input is also affected by practice or exhaustion, premise is a classification without interference by an input’s natural variances in speed, translation, scaling, and rotation. A set of geometric features prevalent in literature is given and extended by own contributions. Various specifications for DTW are evaluated with three different test sets. Our results show that features based on distances and common step patterns are outperformed by specific types of chain codes and local constraints. Classification also benefits from global warping windows usually applied in the context of speech recognition.

Keywords

Dynamic time warping (DTW)survey benchmark classification template-based single-stroke

1. Introduction and motivation

Recognition of stroke-based input1

¹
A stroke is the trajectory (time series of points) of a single touches movement as produced by pens or fingers on a touch-sensitive surface (see Schmidt and Weber [1] for detailed terminology).

is required in many domains and accordingly well studied. Existing methods can roughly be divided into based on motor models [2, 3], description languages [4, 5], rules [6, 7], statistics [8, 9], neural networks [10, 11], and template-matching (nearest neighbor).2

Though neural networks can be regarded statistically founded [12] as are some forms of template-matching [13, 1].

In general, template-based methods normalize training instances (templates or representatives) and input on the basis of a common representation before determining the template (and its class label) most similar to input. This nearest neighbor within the specified templates is retrieved by defining and applying a local distance measurement for parts and a global distance measurement for accumulating thus acquired local information, possibly by dynamic programming routines. On-line methods can take advantage of further constraints implied by the knowledge of input order and allow – besides, for instance, the Hungarian Matching method – dynamic time warping (DTW, also: elastic matching) as a restricted form of aligning local parts of input and template.

Dynamic time warping enhances template-matching between two time series by minimizing their mutual temporal distortions. In fact, most on-line template-based approaches can be realized as special cases of DTW classification that align shape signatures3

In the area of image retrieval, a shape signature represents the contour of a shape by a 1-D function [14].

of specific features under corresponding distance measurements and more or less restricting constraints.

Even if often seen as too expensive [15, 16, 17, 21], implications that DTW is a promising approach for classifying single strokes are given – besides its general accuracy for time series [18, 19] – in that it shows to be closer to rankings by human perception than several other methods [20], is well suited for writer-dependent character recognition [22], and improves already feasible accuracy of nearest neighbor classifiers even when compared to more sophisticated methods [15]. Additionally, DTW, in its plain variants, often is used as an expensive, but accurate reference classifier against other recognition strategies, for instance, to classify planar gestures [16, 17] – with usually competitive recognition results. Though DTW is extensively applied in different fields, comprehensive information and recommendations for suitable parametrization supported by tests are not available for single-stroke input. In literature apart from speech recognition, focus is on feature selection and DTW is used as a classification method in its quasi standard variant [16, 23] or under basic windowing techniques for speedup [20, 24], but without investigations of local or global constraints to the assignment process. Adamek and O’Connor [25] use manual adjustments, but recommend further investigations of weighting schemes.

In this work, we provide an extensive comparison of existing concepts for template matching by dynamic time warping in the general context of recognizing single-stroke input. We do not distinguish between symbols, planar gestures, sketches, or shapes as differences in existing literature are rather subtle. For instance, terms ‘sketches’ and ‘gestures’ are often used exchangeable [26, 27] and corresponding input is processed by the same routines [28, 7]. Likewise, hand-drawn Arabic numerals [29, 30] fall in categories of symbols, characters, or sketches. It is shown how applying DTW routines enhances on-line template-bases methods. With comparable implementation effort and in equal time complexity, accuracy superior to popular methods [16, 31, 32] in the field of HCI can be achieved. Additionally, on the basis of a set of common geometric features and own extensions, we investigate suitable choices and normalization strategies in comparison with existing methods.

2. Dynamic time warping

In principle, dynamic time warping computes stretch-insensitive distances between time series – without premise of equal lengths. Given two such sequences:

$\displaystyle X=\vec{x_{1}},\vec{x_{2}},...,\vec{x_{m}}$ $\displaystyle Y=\vec{y_{1}},\vec{y_{2}},...,\vec{y_{n}}$

the task is to find a mapping $(\vec{x_{i}},\vec{y_{j}})$ , $1\leqslant i\leqslant m$ , $1\leqslant j\leqslant n$ by not necessarily bijectively assigning elements of $X$ and $Y$ to one another along their temporal progress and under additional constraints. Following the notation of [33], the mapping F (the warping function) is described as a sequence of index pairs4

⁴
Without temporal distortions it would be $i(k)=j(k)$ , $\forall k$ and $m=n$ .

given next:

$\displaystyle F=c(1),c(2),...,c(K)\ \textit{with}\ c(k)=(i(k),j(k)),1\leqslant k% \geqslant K,\ 1\leqslant i(k)\leqslant m,\ 1\leqslant j(k)\leqslant n$

Furthermore, given a local distance measurement5

⁵

Commonly, (squared) Euclidean distances $d(i,j)=\|\vec{x_{i}}-\vec{y_{j}}\|$ are used [33, 19].

d(i,j)

and some weighting

w:k\rightarrow\mathbb{R}

, the distortion-minimized DTW-distance between two time series is retrieved by solving

$\displaystyle d(X,Y)=\min_{F}{\frac{\sum_{k=1}^{K}d(c(k))\cdot w(k)}{\sum_{k=1% }^{K}w(k)}}$ (1)

normally by exploiting dynamic programming techniques6

⁶

An optimal assignment for minimal costs can be iteratively and efficiently found in $\mathcal{O}(mn)$ .

and by basic constraints to keep the assignments of feature vectors within time series in temporal order, avoid temporal ‘jumps’, or skipping of signals.

Mainly in the area of speech recognition, modified or additional local (applied in terms of step patterns and weightings) and global (warping windows) constraints were investigated [33, 34, 35]. Such constraints adjust which and how much temporal distortion within the signals is removed and force the warping path, for instance, to prefer diagonal directions without correction of distortions instead of vertical or horizontal steps. Global constraints are applied a-priori-knowledge and restrict allowed temporal equalization by constraining the area in which the warping path is allowed to enter [36]. In literature, three types of global warping windows are common. Sakoe and Chiba [33] define a maximum gap between assigned index pairs. For equal sized time series, the ‘Slanted Band’ [36] imposes the same constraints, but, in contrast, can also be used when lengths of both time series differ much.7

⁷

Both windows reduce computational costs of DTW to linear complexity in dependence of the sum of lengths of both time series.

The so called ‘Itakura Parallelogram’ [37] allows stronger rectifications towards the center of time series, but restricts removal of distortions on their tails. Relaxing local constraints as skipping of observations [22], also utilized in Levenshtein distance8

⁸

Levenshtein distances can be seen as special form of DTW where time series are symbols sequences, local distances are defined in terms of editing expenses and skipping of elements is allowed, but penalized.

computations [38], or the usage of partial matchings [36] can be applied, too. Myers et al. [35] conclude after testing several approaches that local constraints’ influences on quality are either small or, in complex cases, worsen results. The authors state that global constraints improve performance (in terms of run-time), but lower accuracies in classification. On the other hand, besides aspired performance optimization, there are also indications of accuracy advantages [39]. In [40], this effect is explained by the avoidance of pathological removal of distortions that otherwise assign small parts of one time series to large segments of the other one. Xi et al. [19] state that unrestricted warping windows might in most cases increase error rates against intuition.9

⁹

In [41], this is partly supported as for several data sets results of both approaches are close together.

Actually, the best size for the concrete warping window of [33] is rather small. In their tests, it did not exceed 10%10

¹⁰

A size that is also empirically determined in [42] in the context of signature verification.

and may depend on the sample size of training data. Keogh and Ratanamahatana [43] reference this value as the commonly used one in literature, but provide tests that additionally show the problem-dependency of the window’s size. It is further remarked [43, 19] that too much constrains, as for the special case of a diagonal warping path with point-wise Euclidean distances, are typically less accurate. Though cases exist where this (local Manhattan distances achieve similar results) outperforms unrestricted DTW, superiority of the latter is also supported in [41].

All correction of temporal distortions prolong the warping path and, therefore, increases calculated distances accumulated along this path. Normalization to this effect is regarded by a correction term in DTW distance calculation of Eq. (1). However, such normalization depends on the applied local step pattern and its weightings and is efficiently possible only if the value of the normalization term can be computed in advance (utilizing the time series’ lengths). For instance, for the ‘symmetric1’ step pattern (Fig. 4) with equal weightings ( $w(k)=1,\forall{k}$ ), the normalization term is not constant and depends on the warping path’s length [36]. By applying the weight of $w(k)=2$ to diagonal steps, however, distances normalized to [0..1] can be achieved under the correction term $\sum_{k=1}^{K}{w(k)}=n+m$ within Eq. (1). Such normalization can be skipped in case of DTW distance computations between time series that are re-sampled to fixed and equal lengths. Normally, DTW handles time series with different lengths very well, but re-sampling offers some other benefits, too. The special case of DTW with a strict diagonal warping path is only defined on equal length data. Similarly, some global constraints or asymmetric local step patterns can lead to unsolvable problems when lengths of the two time series differ to much [36]. No significant differences between DTW with and without re-sampling are expected, even under varying global constraints [44]. Exceptional special cases, for instance, signature verification that considers temporal variances [42], are not conferrable to the recognition of shapes, symbols, gestures, sketches, and characters.

Besides, due to re-sampling, performance gains can be achieved by applying estimations of lower boundings [40] or further constraints that narrow the search space. In [45] (by the term ‘nonlinear elastic matching’), it is shown that DTW-distances are not a metric, but can be assumed as a weakened form by certain assumptions. Actually, in empirical tests for symmetric types of DTW (symmetric weightings in step patterns) no violation of the triangular equation could be found in a large database of speech recognition cases [46]. By this, index techniques [40] promise further possible speed ups. Alon et al. [15] reduce the number of similarity score computations for on-line and off-line character recognition by prototype selection via cross validation. Alignment process can also be sped up by applying restrictions, for instance, by utilizing global discrimination properties (shape contexts) at each point of two shapes and estimate alignment transformations by their correspondence [47].

In the following, we investigate the usefulness of different DTW strategies on the basis of shape signatures made from geometric features including special cases commonly utilized in literature.

Figure 1.

Features used to create shape signatures. The black dots are forming the left to right trajectory. Grey dots illustrate centers of gravity. Selected features are depicted by dashed lines (distances in 1–3), curves (angles of 4–8), or crosses (positions in 9).

3. Selected feature set and pre-processing

As efficient shape features should be invariant to translation, rotation, and scale [48], our selected set (Fig. 1) consists of features either intrinsically providing these qualities or allowing for efficient normalization routines. Besides positions and distances, we included relative or absolute turning angle sequences (i.e., chain codes [49]) which provide common shape signatures [50, 20, 30] for on-line classification of stroke-based input.

Features shown in the first row (1–3) of Fig. 1 represent Euclidean distances from points of a trajectory to its start point (1) – similar to the approach in [22] that uses Manhattan distances, its global centroid (2) – as utilized by the 1¢ recognizer [32], or incremental centroid11

¹¹
The incremental centroid is the center of gravity computed for all points within the trajectory from the start point up to the currently investigated point.

(3).

Different scale and rotation invariant angles are depicted for the numbers of 4 to 7. Numbers 4 and 5 represent angles at each trajectory point enclosed by line segments to its successor (4) or endpoint (5) and the start point in each case. Features numbers 6 and 7 are defined as angles at each trajectory point enclosed by its predecessor and the center of gravity (6) or the incremental centroid (7). Feature number 8 represents typical chain codes, here investigated only in terms of absolute angles (as relative ones behave rather chaotically). Finally, number 9 depicts points of the trajectory itself as applied in the ‘$1’ classifier [16] under Euclidean distances or in ‘Protractor’ [31] under cosine-distances between such shape signatures (seen as points in multi-dimensional space).

Of our own contributions (3–7), features 3, 4, 7 additionally allow for partial matchings during an unfinished input as it is done in [51], though incremental centroids (3, 7) are not as robust ‘anchor’ points as centroids.

To each feature type corresponds a metric to be used as local distance at computing time series distances by Eq. (1). The related metric to features 1–3 is the absolute difference $|x_{i}-y_{j}|$ . Local comparisons between points (feature 9) are done via Manhattan (9a), Euclidean (9b), squared Euclidean (9c) or cosine- (9d) distances. A special metric

$\displaystyle d(i,j)=\left\{\begin{array}[]{ll}\frac{1}{\pi}|x_{i}-y_{j}|,&|x_% {i}-y_{j}|<\pi\\ \\ \frac{1}{\pi}(2\pi-|x_{i}-y_{j}|),&\textit{otherwise}\end{array}\right.$ (2)

is used for angular measurements and computes absolute angular distances normalized to an interval [0..1].

Table 1

Characteristics of the features (first column) when used to build up time series for DTW. Each feature is listed together with its type, the corresponding local distance and necessary pre-processings to retain all aspired invariances

Shape	Local	Local	Pre-processing
signature	feature	distance
1, 1¢ (2), 3	Distance	Absolute	Scaling
4, 5, 6, 7	Angle	Angular	–
8	Angle	Angular	Rotation
9a	Point	Manhattan	Transl., scal., rot.
9b, $1 (9b)	Point	Euclidean	Transl., scal., rot.
Procrustes (9c)	Point	Sq. Euclidean	Transl., scal., rot.
Protractor (9d)	Points	Cosine	Rotation

Further normalizations retain our required invariances against translation, scale, rotation, and speed. Normalization regarding input speed is done by a trajectory’s uniform re-sampling (accompanied by linear interpolation).12

¹²

The sample size of 64 is used in [16] and we, too, regarded it large enough to adequately represent an input.

This step also allows for comparisons regarding special cases of warping windows.

Figure 2.

Illustration of gestures within the ILGDB-set [53] and examples of concrete specifications.

Figure 3.

Collection of gestures chosen from the MTIS set [54] for testing purposes. Various instances of these gestures are shown on the right side.

Figure 4.

The selection of step patterns considered in our tests. From known patterns, asymmetric, smoothed and duplicate versions are excluded.

Figure 5.

Accuracies of nearest neighbor classifications with all shape signatures when using two different step patterns for DTW.

All relative distances (features 1–3) are invariant to rotation and translation. With exception of feature number 8, all other angular features (4–7) are intrinsically invariant to variations in translation, scale, and rotation. Features of type 8 represent absolute angles and have to be normalized regarding rotations. In case of features 9a, 9b, and 9c, normalization regarding all three variations is necessary for point-wise (Manhattan/Euclidean) distances and normalization of rotational offsets is needed for the cosine-distance (9d).

Except for the ‘$1’ method with its less formal heuristic routine, analytical normalization of translation, scaling,13

¹³

Normalization of distances (1–3) regarding scale by division through the length of the complete path or the maximum length of one of its segments leads to time series of values within the range [0..1]. However, tests showed significant improvements ( $>15\%$ ) of classification accuracies, if uniform scaling is done in advance to the feature extraction routine.

or rotation is applied according to the Procrustes Analysis [52]. In fact, fully restricted DTW (warping path is diagonal) under feature 9c is equivalent to this method. Table 1 summarizes, for each type of feature, all – besides re-sampling – necessary normalization steps to achieve the required invariances. In the following, all labels for our features are used to name thus normalized shape signatures in combination with their corresponding metrics.

4. Evaluation routine

As our focus is not on starting point problems of closed contour shape retrieval when matching shape signatures, we selected on-line test sets with known start and end points. Note that, as we are investigating DTW and feature selection strategies, comparing our single-feature results with other classification methods is not main purpose of this work. Therefore, incorporating our findings within comparisons of heterogeneous recognition approaches on the basis of other common test sets (i.e., MPEG 7 shape or ETH-80 3-D objects databases) is part of future work.

We conducted tests on three single-stroke gesture sets. A pre-selection of appropriate candidates of shape signatures and local constraints (step patterns) is found by classification tests with templates from five persons of the gesture set provided by [16]. This set is seen as a reference for minimal requirements as its data contains little noise. To avoid overfitting by parameter bias as warned in [41], two new sets of single-stroke templates are utilized for concluding tests of these promising methods under common warping windows. We follow the argumentation of [43] and, to avoid data bias, aim for reproducibility and comparability by selecting one gesture set – the ‘Intuidoc-Loustic Gestures DataBase’ (ILGDB) [53] – which is freely available and already investigated in publications. The last gesture set consists of single-stroke letters from the gesture alphabet (Multi-Touch Text Input System, MTIS) developed in [54].

The ILGDB Set was collected by three user groups. Two of them had to specify complete or partial gestures for given interactions. Therefore, these gesture sets are heterogeneous and not suitable for user-independent tests. A fixed selection of 21 gesture classes was presented to all 11 users of group 3 that specified five templates for each of them. We use these templates14

¹⁴
Templates are available at: www.irisa.fr/intuidoc/ILGDB.html. Note that only 11 gesture sets for group 3 are available, in contrary to 12 mentioned within the publication [53].

for our following tests. Figure 2 shows the gesture set and example instances.

Gestures of the ILG data base frequently show cusps at beginning or end of a gesture (Fig. 2 right). In general, such noisy data can be classified better by global features whereas shape signatures account for local variations. However, we do not apply smoothing in this work as we are interested in chosen methods’ performance in those cases.

Gestures of the MTIS set were collected in tests of [54] at training phase15

¹⁵

A symbol represented the correct shape of the input that were to be specified by users.

without knowledge of the users. The original set contained specifications of a single-touch and a multi-touch group and we use all single-touch templates of the gesture classes depicted in Fig. 3.

Table 2

Results (in percent) of DTW classification tests per shape signature and for suitable and common step patterns. Bold values show step patterns that achieved highest accuracies for a shape signature. Framed values assign the most promising shape signature to a step pattern. Averaged results ( $\oslash$ ) as well as standard deviations (s) over rows and columns are given.

	9b	8	4	9a	6	7	$\oslash$	s
rigid	97.50	98.45	98.40	97.40	97	94.80	97.26	1.22
symmetric 1	98.25	97.20	97.90	98.00	97.25	94.85	97.24	1.24
symmetric2	98.10	96.95	97.10	98.00	95.40	93.15	96.45	1.89
symmetricP1	98.30	98.55	99.70	98.20	97.70	97.55	98.33	0.77
symmetricP2	98.40	99.50	99.70	98.25	97.95	98.95	98.79	0.71
symmetricP05	98.20	98.30	99.65	98.00	97.35	95.70	97.87	1.30
typeIa	98.25	98.80	99.70	98.10	97.70	96.30	98.14	1.14
typeIb	98.25	98.60	99.70	98.15	97.85	98.35	98.48	0.64
typeIIa	97.85	98.40	99.70	97.45	97.85	99.15	98.40	0.87
typeIIb	98.25	98.70	99.70	98.00	97.80	99.20	98.61	0.74
typeIId	98.05	98.60	99.70	97.80	97.80	99.25	98.53	0.80
rabinerJuang5a	97.85	98.15	99.65	97.80	96.85	89.20	96.58	3.73
rabinerJuang5b	98.30	98.40	99.65	98.10	97.65	97.30	98.23	0.81
rabinerJuang6a	98.25	99.50	99.65	98.10	98.00	98.35	98.64	0.73
rabinerJuang6b	98.30	99.45	99.70	98.30	98.00	99.15	98.82	0.71
$\oslash$	98.19	98.51	99.37	98.02	97.51	96.89
s	0.17	0.75	0.81	0.22	0.69	2.90

The gestures chosen from 22 classes of the MTIS set do not contain as much cusps or noise as the instances within the ILGDB set. However, high inter-user variability is inherent to both test sets.

To investigate the influence of different step patterns, the ‘dtw’ package [55] of the statistics software ‘R’ [56] is used. It provides commonly used step patterns as ‘symmetric1’, ‘symmetric2’, ‘asymmetric’ and the restrictive case of only one allowed diagonal warping path ‘rigid’ as well as a large selection of patterns mainly used in speech recognition.16

¹⁶

Though to the authors’ knowledge, this is the most extensive library for DTW parametrizations, its incorporation by a (inevitably slow) COM interface biases meaningful investigations of run-times beyond complexity examinations.

Included are eight patterns by the taxonomy of Sakoe and Chiba [33], 14 by Rabiner and Myers [57], 56 by Rabiner and Juang [58] and one by Mori et al. [59]. Eliminating duplicates and variations with smoothed weighting parameters by Rabiner and Juang (28), Sakoe and Chiba (3), Rabiner and Meyers (4), gets us a selection of 30 step patterns. In our work, only symmetric step patterns are investigated as we assume no systematical difference between templates and actual input. We follow the conclusion in [33] insofar that each part of the input should be equally important and do not expect data with high noise in stroke-based input. However, we include the pattern types of Rabiner-Myers ‘typeIIa’, ‘typeIIb’, ‘typeIId’ (normalizable) in our set that allow discontinuous warping paths and the omission of data points. The final set includes all 15 step patterns that are shown17

¹⁷

All illustrations of step patterns and global windows were produced by by the R statistics software [56] and the ‘dtw’ package [55].

in Fig. 4.

Figure 6.

Global warping windows ‘Sakoe-Chiba Band’ [33] (left) at window size 6, ‘Itakura Parallelogram’ [37] (middle), and an asymmetric local step pattern constraint which produces the ‘Itakura Parallelogram’, too (right).

4.1 Reducing the set of methods

Tests in terms of classifications under DTW and all shape signatures represented by features in Table 1 are performed on the gesture set of [16]. For a first selection of shape signatures suitable for further investigations, we apply two basic step patterns without any other global constraints – ‘rigid’ (no time warping, can be seen as a fully restrictive global constraint of DTW which allows diagonal steps only) and ‘symmetric2’ (warping in unconstrained horizontal, diagonal, or vertical steps with normalizable weightings). Test results of this comparison are presented in Fig. 5.

Figure 5 demonstrates that the approaches ‘Protractor’,‘$1’, and ‘Procrustes’, achieve results similar (but overall worse) to DTW under features 4, 8, and 9. Differences between fully restricted DTW and utilization of the ‘symmetric2’ step pattern are small for non-distance based features and most distinctive for feature number 1. With exceptions at features 9a/9b, rigid comparisons are superior to DTW with unconstrained warping path. Interestingly, a decline of accuracies in DTW for strong restrictions, as observed in [19], seems to be correct for local Euclidean distances between points, but not for shape signatures that where built of distances and angles.

However, all shape signatures built of distances or feature 5 achieve low recognition rates compared to the other methods even on the simple test case. Further analysis of these method is, therefore, not advantageous and we do not include them in further tests. A $\chi^{2}$ -test with Yates-correction showed ( $\chi^{2}=90.91$ ; $df=1$ ; $p\ll 0.01$ ) a significant difference between the worst result (signature 7) of methods we further investigate and best result (signature 1) of methods not regarded in the following. Detailed investigations of the remaining signatures under all step patterns are presented in Table 2. The special case of the ‘rigid’ pattern is given for comparison reasons, but not incorporated into average results.

The new feature 4 shows – with exceptions at patterns ‘symmetric1’ and ‘symmetric2’ – consistently best results which are nearly unaffected by the choice of a step pattern. Interestingly, the common patterns ‘symmetric1’ and ‘symmetric2’ achieve good results only for the prevalent local distances between points of a trajectory (features 9a, 9b). Although, even in this case, better choices of step patterns18

¹⁸
For instance, the non-normalizable and discontinuous version of the ‘symmetric1’ pattern, ‘typeIa’, showed better results under all signatures.

exist. With one exception for ‘typeIId’ at signature 7 (for which deviations are highest), the patterns ‘symmetricP2’ and ‘rabinerJuang6b’ achieved best results over all signatures.

Influence of the step pattern is strongly significant (single-factor ANOVA at $\alpha=0.05$ ) for shape signatures 4, 8, 6, 7 ( $p\leqslant 0.01$ ), but classification results at classical shape signatures 9a ( $p=0.89$ ) or 9b ( $p=0.98$ ) seem neither significantly nor by trend to be influenced by the selection of a step pattern. As expected from accuracy values in Table 2, signature 4 is rather robust and not influenced ( $p\approx 1$ ) by the choice of a step pattern aside from ‘symmetric1’ and ‘symmetric2’. As we are interested in robust classifications, for further tests, we regard results above and exclude step patterns that do not promise good results by showing inferior to most of the others on the first test set.

Step patterns investigated in our final tests are those with best results under one of the signatures (‘rabinerJuang6a’, ‘rabinerJuang6b’, ‘symmetricP2’, ‘typeIId’). Furthermore, ‘rabinerJuang5b’ is consistently better than patterns of equal type and different weightings (‘symmetricP05’ and ‘rabinerJuang5a’). The similar types ‘symmetricP1’, ‘typeIa’, and ‘typeIb’ all show inferior to ‘symmetricP2’, but we include ‘typeIb’ for being the best representative of this group. Patterns ‘typeIIa’, ‘typeIIb’, and ‘typeIId’ are alike, too. The normalizable ‘typeIId’ already is included and kept as the one representative of this type as average results are very similar. Nearly all (except ‘typeIId’) step patterns showed consistently better results than ‘symmetric1’ and ‘symmetric2’ which are, therefore, not regarded anymore. In the following, shape signature 9a is not investigated as 9b is superior to 9a in that the latter one achieves consistently inferior results.

The six selected step patterns19

¹⁹

‘symmetricP2’, ‘typeIb’, ‘typeIId’, ‘rabinerJuang5b’, ‘rabinerJuang6a’, ‘rabinerJuang6b’.

plus the strict version ‘rigid’ as well as three global constraints, the remaining five signatures and the methods ‘Protractor’, ‘$1’, and ‘Procrustes’ are used for elaborated concluding tests.

4.2 Concluding evaluations

By [40], the ‘Sakoe-Chiba Band’ and ‘Itakura Parallelogram’ (Fig. 6) are used most frequently. The latter one is also produced by some local constraints as the Rabiner-Juang step pattern type IV [36] or the similar Rabiner-Myers typeIIIc which is depicted in Fig. 6 (right). We investigate, under the reduced set of step patterns, the ‘Sakoe-Chiba Band’ (due to re-sampled data identical to the ‘Slanted Band’) and ‘Itakura Parallelogram’ versus no global constraints. Lacking detailed information to derive window sizes from test data, we use the 10% restriction ( $\lfloor(n\cdot 10\%)\rfloor=6$ ) as proposed in [19, 42] for the ‘Sakoe-Chiba Band’.

In our tests, each procedure (or choice of parameter) is performed for the same ten test cases – five for ILGDB and five for MTIS – of user-independent and randomly selected templates and test instances. Within the MTIS set, each test case contained five (randomly chosen) templates and 15 test instances per class. The ILGDB tests were similarly conducted, but due to smaller size of the gesture set only ten test instances per class were chosen. Results are presented within the next section and assigned to best choices of shape signatures, step patterns, and global windows.

Table 3
Classification accuracies (in percent) for ILGDB (left) and MTIS (right) test sets in dependence of selected shape signatures, step patterns, and warping windows. Framed entries tag overall best results for a step pattern, bold entries mark best results for fixed shape signatures and mean results (over all local constraints) of (in average) best performing shape signatures. Underlined values show exceptional cases were the ‘Sakoe-Chiba’-window at equal shape signatures and step patterns does not perform best over all other global constraints

Results for ILGDB
Warping Window	Shape Signature	symmetricP2	rabinerJuang5b	rabinerJuang6a	rabinerJuang6b	typeIb	typeIId	$\oslash$
	9b	78.00	78.57	77.71	78.29	78.57	78.48	78.27
	8	92.76	92.10	92.48	92.67	92.19	92.57	92.46
	4	79.43	77.71	79.24	79.81	79.24	78.86	79.05
N/A	6	78.19	75.62	78.48	79.52	77.43	76.57	77.63
	7	73.52	72.57	73.43	74.38	73.43	75.62	73.83
	$\oslash$	80.38	79.31	80.27	80.93	80.17	80.42	80.25
	9b	78.00	78.57	77.71	78.29	78.57	78.48	78.27
	8	92.76	92.00	92.48	92.67	92.19	92.57	92.44
	4	79.43	77.90	79.24	79.81	79.24	78.86	79.08
	6	78.19	75.81	78.48	79.52	77.43	76.57	77.67
Itakura	7	73.52	72.86	73.43	74.38	73.43	75.62	73.87
	$\oslash$	80.38	79.43	80.27	80.93	80.17	80.42	80.27
	9b	78.00	78.57	77.71	78.29	78.57	78.48	78.27
	8	93.33	93.14	93.14	93.24	93.05	93.05	93.16
	4	79.33	79.71	79.14	79.90	79.81	80.29	79.70
	6	78.29	76.48	78.38	79.33	77.62	76.57	77.78
	7	74.00	73.43	73.43	74.67	74.67	75.81	74.33
Sakoe-Chiba	$\oslash$	80.59	80.27	80.36	81.09	80.74	80.84	80.65
	$\oslash$	80.45	79.67	80.3	80.98	80.36	80.56	80.39

Results for MTIS
Warping Window	Shape Signature	symmetricP2	rabinerJuang5b	rabinerJuang6a	rabinerJuang6b	typeIb	typeIId	$\oslash$
	9b	94.18	94.06	93.88	94.18	94.06	93.94	94.05
	8	96.06	93.15	95.76	96.24	94.42	94.00	94.94
	4	95.76	94.61	95.52	95.88	95.33	94.97	95.34
N/A	6	94.97	93.03	94.48	95.09	94.24	94.36	94.36
	7	93.94	90.97	93.70	94.12	92.18	93.33	93.04
	$\oslash$	94.98	93.16	94.67	95.10	94.05	94.12	94.35
	9b	94.18	94.06	93.88	94.18	94.06	93.94	94.05
	8	96.06	93.33	95.76	96.24	94.42	94.00	94.97
	4	95.76	94.97	95.52	95.88	95.33	94.97	95.40
	6	94.97	93.52	94.48	95.09	94.24	94.36	94.44
Itakura	7	93.94	90.97	93.70	94.12	92.18	93.33	93.04
	$\oslash$	94.98	93.37	94.67	95.10	94.05	94.12	94.38
	9b	94.18	94.06	93.88	94.18	94.06	93.94	94.05
	8	96.55	95.27	96.42	96.79	95.82	95.94	96.13
	4	95.76	96.12	95.58	95.94	96.36	95.70	95.91
	6	94.97	94.42	94.55	95.09	94.85	94.73	94.77
	7	94.67	94.18	94.36	94.73	94.30	95.03	94.55
Sakoe-Chiba	$\oslash$	95.22	94.81	94.96	95.35	95.08	95.07	95.08
	$\oslash$	95.06	93.78	94.76	95.18	94.39	94.44	94.60

5. Results and discussion

Average accuracy values of tests with ILGDB and MTIS depending on choices of shape signature, step patterns and global windows are given in Table 3.

Accuracy results in Table 3 show that the ‘Sakoe-Chiba’-window at width 10% outperforms ‘Itakura’-parallelogram or unrestricted DTW in most cases. Though differences between warping windows are small, these impression is reassured by consistently better average results per step pattern. Besides one exceptions within the ILGDB tests, overall best results occur at the ‘Sakoe-Chiba’-constraint, too. Definite evidence towards preferences of a step pattern can not be given. However, the step pattern ‘rabinerJuang6b’ achieves again best average results and the overall best result for the MTIS set. Second best average results for the MTIS set and the overall best value for ILGDB is produced by the ‘symmetricP2’ pattern.

A consistent result is that shape signature 8 outperforms others by showing highest average results as well as most frequent best accuracy values and overall best classification rates – with ‘symmetricP2’ (ILGDB) or ‘rabinerJuang6b’ (MTIS) being the most appropriate choices. Signature 4 produced second best results and, confirming results of the first test, achieves better accuracies for data with little noise while signature 8 is far less affected by noisy data (ILGDB) as other signatures. Similarly, results for pattern ‘typeIId’ – which goes along well with shape signature 7 – indicate that discontinuous patterns may be more appropriate for noisy data. Adequacy of angular features 6 and (its incremental pendant) 7 is confirmed only when compared with distances between points (9b) for the ILGDB testset.

The methods Procrustes, Protractor, and $1 can be seen as DTW under the ‘rigid’ step pattern with only allowed diagonal warping paths – which is equivalent to a ‘Sakoe-Chiba’-window at width 0. Average classification accuracies of these methods are shown in Table 4 and compared with results of all other shape signatures under the ‘rigid’ constraint.

Table 4
Average classification rates at ‘rigid’ constraint for two groups containing Procrustes, Protractor, $1, and shape signatures 4, 6, 7, 8, and 9b, respectively. Results are for the ILGDB and MTIS set and group-wise in descending order in each case

ILGDB
Shape Signature	Accuracy (%)
Protractor	83.81
$1	74.29
Procrustes	72.48
8	90.19
4	76.29
6	75.24
9b	74.86
7	68.10

MTIS
Shape Signature	Accuracy (%)
Procrustes	92.00
$1	90.12
Protractor	84.30
8	96.79
4	95.09
6	93.52
9b	92.97
7	92.30

Figure 7.

Classification results for the ILGDB (left) and MTIS (right) set achieved at best parameter selections for each shape signature.

Except for signature 8 (absolute angles) within the MTIS tests, no shape signature benefits from too much restriction of DTW (‘rigid’) without any correction of temporal distortions. Interestingly, the overall best result for this set is achieved with this signature at the the‘rigid’ pattern and under global ‘Sakoe-Chiba’ constraint with step patterns ‘rabinerJuang6b’. Again, shape signature 8 achieves consistently best results – ‘Protractor’ (ILGDB) or signature 4 (MTIS) are second best choices. As in the first test, for the ILGDB set, the ‘$1’ classifier achieves higher accuracy than the Procrustes analysis. However, the analytical pre-processing of ‘Procrustes’ can improve the ‘$1’ method which can be seen at signature 9b that consistently outperforms both methods. As stated before, shape signature 9b represents in fact a Procrustes analysis with Euclidean local distances instead of squared ones.

A comprehensive overview of results regarding all shape signatures at best parameter choices is presented in Fig. 7. With exception of signature 6 within ILGDB tests, this means a selection of the global constraint ‘Sakoe-Chiba’, though equal results appear under free DTW or ‘Itakura’ in few cases. Best results for each shape signature within ILGDB tests are achieved by local step patterns: ‘symmetricP2’ (8), ‘rabinerJuang5b’ and ‘typeIb’ (9b), ‘rabinerJuang6b’ (6), and ‘typeIId’ (4, 7). Best settings for step patterns at MTIS tests (containing less deviations over different approaches) are ‘symmetricP2’ (9b), ‘rabinerJuang6b’ (6, 8, 9b), ‘typeIb’ (4), ‘typeIId’ (7), or ‘rigid’ (8). In average, step pattern ‘rabinerJuang6b’ performs best.

6. Summary and conclusion

In this work, tests of a broad range of DTW parametrizations on three different gesture sets with varying degrees of idealization in templates’ shapes were performed. Though some heterogeneous results occurred, consistent conclusions can be inferred. Overall, geometric features of angles are to be preferred over points and distances. We confirm previous findings [31, 22] insofar that shape signatures of directional features seem to be generally well suited for classification. This aspect seems to be more important on noisy data. In both final tests, shape signature 8 (absolute angles) achieved best results and showed robust against cusps at beginning or end of an instance within the ILGDB set. Our proposed signature 4 can be similarly efficiently obtained and achieved second best (in case of the $1 set even best) results. In contrast to signature 8, all aspired invariances are inherent to this elegant feature and, besides re-sampling, no further pre-processing is required. Usually, if normalization regarding scale, rotation, translation is utilized, information on the complete input sequence is required. For signature 4, computation is incrementally possible and, therefore, can be done for partial input. Both signatures, 8 and 4, are superior to Procrustes analysis at equal linear complexity – even though, Procrustes analysis systematically improves by usage of Euclidean distances instead of squared ones. The analytical solution to scaling and rotation normalization, however, were overall valuable and are to be preferred over non-uniform scaling and iterative correction of rotational offsets as in [16].

Results for each of the tested signatures can still be improved at appliance of DTW strategies. With exception of one case within the ILGDB test, the ‘Sakoe-Chiba’ window at 10% width around the warping path was the best option for a global constraint. It can be assumed that smaller window sizes imply further improvements, but a too rigid constraint showed inferior. Performance improvements by the ‘Sakoe-Chiba’ window come with no additional costs and actually reduces quadratic run-time – which is a drawback of DTW compared to other template-matching approaches – to linear complexity. Regarding step patterns, the common ‘symmetric1’ or ‘symmetric2’ types can be avoided. DTW under these local constraints can improve results of methods based on local distances between points, but even in those cases better options exist. In all our tests, best results were obtained by the ‘rabinerJuang6b’ pattern. Alternatively, ‘symmetricP2’ achieved good results, too. Advantage of the latter is its normalizability. At noisy input, discontinuous step patterns as ‘typeIId’ may be an option, but without a-priori-knowledge, consistently performing choices should be applied.

For the classification of single-trajectory data, the selection by accuracy is sufficient. If no normalization shall be applied, signature 4 is adequate, otherwise signature 8 should perform well in most cases. DTW strategies can improve both methods under scalable costs.20

²⁰

See [39] for estimations regarding speed of DTW approaches.

There seem to be no reason to prefer distances between points to angular distances other than slightly higher computational costs of angle calculations.

We showed that investigations of approaches suitable for speech recognition and refinements for DTW are profitable for shape-matching, too. In dependence of selected features, special local constraints are advantageous. However, improvements by global constraints and robust step patterns are reliably possible in general and expected to be independent of the selected feature set. Future work should incorporate these promising parametrizations into template-based classification under more sophisticated sets of features. Similarly, findings should be transferable to the broad range of applications for DTW. When using DTW as a reference classifier, it should be implemented (with nearly same effort) in its more competitive version and at least incorporate the basic ‘Sakoe-Chiba’ window at 10% width, a robust step pattern (e.g., ‘Rabiner-Juang 6b’), and more reliable (angular) features. Otherwise, capacity regarding run-time or accuracy is not sufficiently exploited.

Footnotes

Acknowledgments

The authors kindly thank all reviewers for their help and constructive input.

References

Schmidt

Weber

, Template based classification of multi-touch gestures, Pattern Recognition 46(9) (2013) 2487–2496. doi: 10.1016/j.patcog.2013.02.001.

Schmidt

G.S.

House

D.H.

, Towards model-based gesture recognition, in: Proceedings of the Fourth IEEE International Conference on Automatic Face and Gesture Recognition 2000, FG ’00, IEEE Computer Society, Washington, DC, USA, 2000, p. 416.

Cao

Zhai

, Modeling human performance of pen stroke gestures, in: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, CHI ’07, ACM, New York, NY, USA, 2007, pp. 1495–1504.

Dai

, Gesture language use in natural UI: pen-based sketching in conceptual design, in: Pan

Shi

(Eds.), Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, Vol. 4756 of Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, 2003, pp. 122–128.

Khandkar

S.H.

Maurer

, A domain specific language to define gestures for multi-touch applications, in: Proceedings of the 10th Workshop on Domain-Specific Modeling, DSM ’10, ACM, New York, NY, USA, 2010, pp. 2:1–2:6.

Fitzgerald

Geiselbrechtinger

Kechadi

, Application of fuzzy logic to online recognition of handwritten symbols, in: Frontiers in Handwriting Recognition, 2004. IWFHR-9 2004. Ninth International Workshop on, 2004, pp. 395–400. doi: 10.1109/IWFHR.2004.19.

Zeleznik

R.C.

Bragdon

Liu

C.-C.

Forsberg

, Lineogrammer: creating diagrams by drawing, in: Proceedings of the 21st Annual ACM Symposium on User Interface Software and Technology, UIST ’08, ACM, New York, NY, USA, 2008, pp. 161–170. doi: 10.1145/1449715.1449741.

Rubine

, Specifying gestures by example, SIGGRAPH Comput. Graph. 25(4) (1991) 329–337.

Deufemia

Risi

Tortora

, Sketched symbol recognition using latent-dynamic conditional random fields and distance-based clustering, Pattern Recognition 47(3) (2014) 1159–1171, handwriting Recognition and other {PR} Applications. doi: https://dx-doi-org.web.bisu.edu.cn/10.1016/j.patcog.2013.09.016. URL https://www-sciencedirect-com.web.bisu.edu.cn/science/article/pii/S0031320313003889.

10.

Yuan

Liu

Barner

, Tactile gesture recognition for people with disabilities, in: Acoustics, Speech, and Signal Processing, 2005. Proceedings. (ICASSP ’05). IEEE International Conference on, Vol. 5, 2005, pp. 461–464. doi: 10.1109/ICASSP.2005.1416340.

11.

Crossan

Brewster

, Multimodal trajectory playback for teaching shape information and trajectories to visually impaired computer users, ACM Trans. Access. Comput. 1(2) (2008) 12:1–12:34.

12.

Duda

R.O.

Hart

P.E.

Stork

D.G.

, Pattern Classification, 2nd Edition, Wiley, New York, 2001.

13.

Wilson

Bobick

A.F.

, M.I. of Technology. Media Laboratory. Vision, M. Group, Using Configuration States for the Representation and Recognition of Gesture, M.I.T. Media Lab Vision and Modeling Group technical report, Vision and Modeling Group, Media Laboratory, Massachusetts Institute of Technology, 1995.

14.

El-ghazal

Basir

Belkasim

, Farthest point distance: A new shape signature for fourier descriptors, Signal Processing: Image Communication 24(7) (2009) 572–586.

15.

Alon

Athitsos

Sclaroff

, Online and offline character recognition using alignment to prototypes, in: Document Analysis and Recognition, 2005. Proceedings. Eighth International Conference on, IEEE, 2005, pp. 839–843.

16.

Wobbrock

J.O.

Wilson,

A.D.

, Gestures without libraries, toolkits or training: a $1 recognizer for user interface prototypes, in: UIST ’07: Proceedings of the 20th Annual ACM Symposium on User Interface Software and Technology, ACM, New York, NY, USA, 2007, pp. 159–168.

17.

Willems

Niels

van Gerven

Vuurpijl

, Iconic and multi-stroke gesture recognition, Pattern Recognition 42(12) (2009) 3303–3312, new Frontiers in Handwriting Recognition.

18.

Zhang

, A Comparative Study on Shape Retrieval Using Fourier Descriptors with Different Shape Signatures, Journal of Visual Communication and Image Representation 14(1) (2003) 41–60.

19.

Keogh

Shelton

Wei

Ratanamahatana

C.A.

, Fast time series classification using numerosity reduction, in: Proceedings of the 23rd International Conference on Machine learning, ICML ’06, ACM, New York, NY, USA, 2006, pp. 1033–1040.

20.

Niblack

Yin

, A pseudo-distance measure for 2d shapes based on turning angle, in: Proceedings of the 1995 International Conference on Image Processing (Vol. 3)-Volume 3 – Volume 3, ICIP ’95, IEEE Computer Society, Washington, DC, USA, 1995, pp. 3352–.

21.

Petitjean

Forestier

Webb

Nicholson

Chen

Keogh

, Faster and more accurate classification of time series by exploiting a novel dynamic time warping averaging algorithm. Knowledge and Information Systems 47(1) (2016) 1–26.

22.

Connell

S.D.

Jain

A.K.

, Template-based online character recognition, Pattern Recognition 34(1) (2001) 1–14.

23.

Santosh

Lamiroy

Wendling

, Dtw-radon-based shape descriptor for pattern recognition, International Journal of Pattern Recognition and Artificial Intelligence 27(03) (2013) 1350008.

24.

Tuzcu

Nas

, Dynamic time warping as a novel tool in pattern recognition of ecg changes in heart rhythm disturbances, in: Systems, Man and Cybernetics, 2005 IEEE International Conference on, Vol. 1, IEEE, 2005, pp. 182–186.

25.

Adamek

O’Connor

N.E.

, A multiscale representation method for nonrigid shapes with a single closed contour, IEEE Trans. Cir. and Sys. for Video Technol. 14(5) (2004) 742–753.

26.

Landay

J.A.

Myers

B.A.

, Interactive sketching for the early stages of user interface design, in: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, CHI ’95, ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 1995, pp. 43–50.

27.

Henry

T.R.

Hudson

S.E.

Newell

G.L.

, Integrating gesture and snapping into a user interface toolkit, in: Proceedings of the 3rd Annual ACM SIGGRAPH Symposium on User Interface Software and Technology, UIST ’90, ACM, New York, NY, USA, 1990, pp. 112–122.

28.

Fonseca

M.J.

Pimentel

Jorge

J.A.

, Cali: An online scribble recognizer for calligraphic interfaces, in: Sketch Understanding, Papers from the 2002 AAAI Spring Symposium, 2002, pp. 51–58.

29.

Yang

, Hidden markov model for gesture recognition, Tech. Rep. CMU-RI-TR-94-10, Robotics Institute, Pittsburgh, PA (May 1994).

30.

Deng

Tsui

, An hmm-based approach for gesture segmentation and recognition, in: Pattern Recognition, 2000. Proceedings. 15th International Conference on, Vol. 3, 2000, pp. 679–682 vol.3. doi: 10.1109/ICPR.2000.903636.

31.

, Protractor: a fast and accurate gesture recognizer, in: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, CHI ’10, ACM, New York, NY, USA, 2010, pp. 2169–2172.

32.

Herold

Stahovich

T.F.

, The 1¢recognizer: a fast, accurate, and easy-to-implement handwritten gesture recognition technique, in: Proceedings of the International Symposium on Sketch-Based Interfaces and Modeling, SBIM’12, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 2012, pp. 39–46.

33.

Sakoe

Chiba

, Dynamic programming algorithm optimization for spoken word recognition, Acoustics, Speech and Signal Processing, IEEE Transactions on 26(1) (1978) 43–49.

34.

Rabiner

Rosenberg

Levinson

, Considerations in dynamic time warping algorithms for discrete word recognition, Acoustics, Speech and Signal Processing, IEEE Transactions on 26(6) (1978) 575–582.

35.

Myers

Rabiner

Rosenberg

, Performance tradeoffs in dynamic time warping algorithms for isolated word recognition, Acoustics, Speech and Signal Processing, IEEE Transactions on 28(6) (1980) 623–635.

36.

Giorgino

, Computing and Visualizing Dynamic Time Warping Alignments in R: The dtw Package, Journal of Statistical Software 31(7) (2009) 1–24.

37.

Itakura

, Minimum prediction residual principle applied to speech recognition, Acoustics, Speech and Signal Processing, IEEE Transactions on 23(1) (1975) 67–72. doi: 10.1109/TASSP.1975.1162641.

38.

Levenshtein

V.I.

, Binary codes capable of correcting deletions, insertions, and reversals, Soviet Physics Doklady 10(8) (1966) 707–710.

39.

Ratanamahatana

C.A.

Keogh

E.J.

, Three myths about dynamic time warping data mining, in: SDM’05, 2005, pp. 1–1.

40.

Keogh

, Exact indexing of dynamic time warping, in: Proceedings of the 28th International Conference on Very Large Data Bases, VLDB’02, VLDB Endowment, 2002, pp. 406–417.

41.

Wang

Mueen

Ding

Trajcevski

Scheuermann

Keogh

, Experimental comparison of representation methods and distance measures for time series data, Data Mining and Knowledge Discovery 26(2) (2013) 275–309.

42.

Henniger

Müller

, Effects of time normalization on the accuracy of dynamic time warping, in: Biometrics: Theory, Applications, and Systems, 2007. BTAS 2007. First IEEE International Conference on, 2007, pp. 1–6.

43.

Keogh

Ratanamahatana

C.A.

, Exact indexing of dynamic time warping, Knowl. Inf. Syst. 7(3) (2005) 358–386.

44.

Ratanamahatana

Keogh

, Everything you know about dynamic time warping is wrong, 3rd Workshop on Mining Temporal and Sequential Data, in conjunction with 10th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (KDD-2004), Seattle, WA.

45.

Fagin

Stockmeyer

, Relaxing the triangle inequality in pattern matching, International Journal of Computer Vision 30 (1996) 219–231.

46.

Casacuberta

Vidal

Rulot

, On the metric properties of dynamic time warping, Acoustics, Speech and Signal Processing, IEEE Transactions on 35(11) (1987) 1631–1633. doi: 10.1109/TASSP.1987.1165065.

47.

Belongie

Malik

Puzicha

, Shape matching and object recognition using shape contexts, Pattern Analysis and Machine Intelligence, IEEE Transactions on 24(4) (2002) 509–522.

48.

Yang

Kpalma

Ronsin

et al., A survey of shape feature extraction techniques, Pattern recognition (2008) 43–90.

49.

Freeman

, On the encoding of arbitrary geometric configurations, Institute of Radio Engineers, Transactions on Electronic Computers EC-10 (1961) 260–268.

50.

Kim

, On-Line Gesture Recognition by Feature Analysis, Research Report, IBM Thomas J. Watson Research Center, 1987.

51.

Schmidt

Weber

, Prediction of multi-touch gestures during input, in: Kurosu

(Ed.), Human-Computer Interaction. Advanced Interaction Modalities and Techniques, Vol. 8511 of Lecture Notes in Computer Science, Springer International Publishing, 2014, pp. 158–169.

52.

Dryden

I.L.

Mardia

, Statistical shape analysis, Wiley series in probability and statistics: Probability and statistics, J. Wiley, 1998.

53.

Renau-Ferrer

Delaye

Anquetil

, The ilgdb database of realistic pen-based gestural commands., in: ICPR, IEEE, 2012, pp. 3741–3744.

54.

Schmidt

Fibich

Weber

, Mtis: A multi-touch text input system, in: Streitz

Stephanidis

(Eds.), Distributed, Ambient, and Pervasive Interactions, Vol. 8028 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2013, pp. 62–71.

55.

Giorgino

, Computing and visualizing dynamic time warping alignments in r: The dtw package, Journal of Statistical Software 31(7) (2009) 1–24.

56.

R Development Core Team, R: A Language and Environment for Statistical Computing, R Foundation for Statistical Computing, Vienna, Austria, ISBN 3-900051-07-0 (2011). URL http://www.R-project.org

57.

Myers

C.S.

, A Comparative Study Of Several Dynamic Time Warping Algorithms For Speech Recognition, Master’s thesis, Massachusetts Institute of Technology, Cambridge (1980). URL http://dspace.mit.edu/bitstream/1721.1/27909/1/07888629.pdf

58.

Rabiner

Juang

B.-H.

, Fundamentals of Speech Recognition, Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1993.

59.

Mori

Uchida

Kurazume

Taniguchi

R.-i.

Hasegawa

Sakoe

, Early recognition and prediction of gestures, in: Proceedings of the 18th International Conference on Pattern Recognition – Volume 03, ICPR ’06, IEEE Computer Society, Washington, DC, USA, 2006, pp. 560–563.

Dynamic time warping for the recognition of single-stroke input

Abstract

Keywords

1. Introduction and motivation

1 A stroke is the trajectory (time series of points) of a single touches movement as produced by pens or fingers on a touch-sensitive surface (see Schmidt and Weber [1] for detailed terminology).

4 Without temporal distortions it would be i ⁢ ( k ) = j ⁢ ( k ) , ∀ k and m = n .

11 The incremental centroid is the center of gravity computed for all points within the trajectory from the start point up to the currently investigated point.

14 Templates are available at: www.irisa.fr/intuidoc/ILGDB.html. Note that only 11 gesture sets for group 3 are available, in contrary to 12 mentioned within the publication [53].

18 For instance, the non-normalizable and discontinuous version of the ‘symmetric1’ pattern, ‘typeIa’, showed better results under all signatures.

Table 4 Average classification rates at ‘rigid’ constraint for two groups containing Procrustes, Protractor, $1, and shape signatures 4, 6, 7, 8, and 9b, respectively. Results are for the ILGDB and MTIS set and group-wise in descending order in each case

Footnotes

Acknowledgments

References

¹
A stroke is the trajectory (time series of points) of a single touches movement as produced by pens or fingers on a touch-sensitive surface (see Schmidt and Weber [1] for detailed terminology).

⁴
Without temporal distortions it would be $i(k)=j(k)$ , $\forall k$ and $m=n$ .

¹¹
The incremental centroid is the center of gravity computed for all points within the trajectory from the start point up to the currently investigated point.

¹⁴
Templates are available at: www.irisa.fr/intuidoc/ILGDB.html. Note that only 11 gesture sets for group 3 are available, in contrary to 12 mentioned within the publication [53].

¹⁸
For instance, the non-normalizable and discontinuous version of the ‘symmetric1’ pattern, ‘typeIa’, showed better results under all signatures.

Table 4
Average classification rates at ‘rigid’ constraint for two groups containing Procrustes, Protractor, $1, and shape signatures 4, 6, 7, 8, and 9b, respectively. Results are for the ILGDB and MTIS set and group-wise in descending order in each case