ee
`
`CHAPTER & MULTL-RAIH GESTURE RECOGNITION
`
`4 multi-path gesture classes
`
`p
`
`8
`ie
`ql
`4 cantnenentincettetton
`no
`pi
`1
`™~.
`i
`Ones Peer i anne
`
`po
`
`Q
`
`R
`
`Multi-path
`
`sion Tree
`
`\p
`
`‘gl (chosen gesture)
`
`Input
` _oee
`
`_f
`
`pif
`
`.
`
`este
`Figure 5.3: Classifying multi-path ge
`
`At the top are examples offour two-pathgestures expectcdivthis class:‘ferf alandatthe Icita two-pathgesture
`These path classaificatons are usedto traverse the decision TCL, aS shown by the dottedfines, The tree nade
`thegesture is recognizedas class6
`
`ia be classified. Path Gofthis gesture is classified (hy the path O classifier]
`
`reachedis ambiguous (having children Q and S) so g
`
`as pati 0, and palh 7 as qt.
` te
`
`thal features are usedto resolve the discrepancy, and
`
`Page 1251 of 1714
`
`SAMSUNG EXHIBIT 1006 (Part 7 of 8)
`
`Page 1251 of 1714
`
`
`
`SAMSUNG EXHIBIT 1006 (Part 7 of 8)
`
`

`

`44 TRAINING A MULTIPATHCLASSIFIER
`
`a
`
`Fa
`
`5.4 Training a Multi-path Classifier
`
`The training algorithm for a multi-path classifier uses examples of each nmulti-path gesture class
`(typically ten to twenty examples of each class) to create a classifier The creation of a multi-path
`classifier consists of the creation of a global classifier, a wumber of path classifiers, and a decision
`tree.
`
`5.4.1 Creating the statistical classifiers
`
`The path classifiers and the global classifiers arc created using the statistical algorithmdescribed in
`Chapter 3. The paths of each example are sorted, the paths for a given sorting index im each class
`forming a class used to train the path classifier for that index.
`For example, consider training a multi-path classifier to discriminate between two orelti-path
`gesture classes, A and 8, each consisting of two paths. Gesture class A consists of two path classes,
`A; and Aj, the sabscript indicating the sorting indices of the paths. Similarly, class & consists of
`path classes A; and B;. The first path in all the A examples form the class 4;, and so on. The
`examples arc used to train path claasificr 1 ta discriminate betwoen A, and &,, and path classifier
`2 to discriminate between Ay and &:. The global features af A and § are used to create the global
`classifier, noroinally able to discriminate between twoclasses of global features, Ay and Bg.
`Within a given sorting index, it is quite possible and legitimate for paths fromdifferent gesture
`classes to be indistinguishable. For example, path classes A; and B, may both be siraight right
`strokes. (Presurnably A and 8 are distinguishable by their second paths or global features.) In this
`case itis likely that examples of class Ay will he raisclassified as 6; or vice versa. Tt is desirable to
`removethese ambiguities from the path classifier by combining all classes which could be mistaken
`for each other into a single class.
`Asumiber of approaches could be taken for detecting and removing ambiguities fromastatistical
`classifier, One possible approach wouldbe to compute the Mahalanchis distance between cach pair
`of classes, merging thase belowa given threshold. Another approachinvolves applying a clustering
`algorithm[74] to all the examples, merging those classes whose members are just as likely to cluster
`with examples from other classes as their own. A third approachis to actually evaluate the actual
`performance of a classificr which attempts to distinguish between passibly ambiguous classes; the
`misclassi fications of the classifier then indicate which classes are to be merged. The latter approach
`was the one pursued here.
`A native approach for evaluating the performance of a classifier would be to construct the
`classifier using a set of examples, and then testing the performance afthe classifier on those very
`same examples. This approach obviously underestimates the ambiguities of the classes since the
`classifier will be biased toward correctly classifying its training examples [62]. Instead, a classifier
`is constructed using only a small number of the examples (typically five per class) and then uses
`the remaming examples to evaluate the constructed classifiers. Misclassifications of the examples
`then indicate classes which are ambiguous and should be merged.
`In practice, thresholds mast be
`established so that a single or very small percentage of ousclassifications does not cause a merger.
`Mathematically, carbine classes is a sinmple operation. The mean vector of the combined
`class is computed as the average of the mean vectors of the component classes, each weighted by
`
`Page 1252 of 1714
`
`Page 1252 of 1714
`
`

`

`86
`
`CHAPTER & MULTI-PATH GESTURE RECOGNITION
`
`the relative number of examples in the class. A similar operation computes a composite average
`covariance matrix from the covariance matrices of the classes being combined.
`The above algorithm, which removes ambiguities by cornbining classes, is apphed to each path
`classifier as well as the global classifier. Tt remains now only to constract the decision tree for the
`nxnlti-path classifier.
`
`5.4.2 Creating the decision tree
`
`A decision tree node has two fields: mclags, a pointer to a niulti-path gesture class, and next,
`a pounler lo an array of pouders to its subnades. To construct ihe decision tree, a root nade is
`allocated. Then, during the class phase, each multi-path gesture class is considered in turn. For
`each, a sequence of path classes Ga sort index order}, with ifs glohal feature class appended
`consimicted. Nades are ercated in the decision tree in such a way that by following the sequence
`a feaf node whose mclags vahue is the current multi-path gesture class is reached. This creates a
`decision tree which will correctlyclassify all multi-class gesture whose component paths and global
`features are correctly classified.
`Next, during the examplephase, cach example gesture is considered in turn. The paths are sorted
`and classified, as are the global features. A sequence is constructed and the class of the gesture is
`added to the decision tree at the location corresponding to this sequence as before. Normally, the
`paths and global features of the gesture will have been classified correctly, so there would already be
`a nodein the tree correspondingto this sequence. However, if one of the paths or the global feature
`vector of the gesture was classtiied incorrectly, a mew node maybe created in the decision trec, and
`s the same classification mistake in the future will stul result in a correct classification for the
`
`etuee
`
`When attempting ta add a class using 4 sequence whose components are misclassifications,
`it is possible that the decision tree node reached already bas a non-null melass field referring
`to a different mmulti-path gesture class than the cne whose example is currently being considered.
`This is a confict and is resofved by ignoring the current example (though a warning message is
`printed). [gnoring all but the first instance of a Sean’© insures that the sequences generated during
`the class phase will take precedence over those generated during the example phase. anCORESE,
`
`a conflict occurring during the class phase indicates a serious problem, namely a pair of
`classes between which the multi-path classifier is anable to discriminate.
`During decision tree construction, nodes that have only one global feature class entry with a
`subnode have theirmclass value set to the same gesture class as the molass vahie of that subnode.
`in other words, sequences that can be classified without referring to their global feature class are
`marked as such. ‘Uhis avoids the extra work (and potential for error) of global feature classification.
`
`gesture
`
`5.5 Path Features and Global Features
`
`‘The classification of the individual paths and of the global features of a multi-path gesture are
`central to the multi-path gesture recognition aleorithodiscussed thus far. This section describes the
`particular feature vectors used in more detail.
`
`Page 1253 of 1714
`
`Page 1253 of 1714
`
`

`

`S@ AFURTHER IMPROVEMENT
`
`37
`
`The classification algorithm usedto classify paths and global features is the statistical algorithm
`discussed in Chapter 3, thus the criteria for feature selection discussed in section 3.3 must be
`addressed.
`[Tn particular, oaly features with Gaussian-like distributions thal can be calculated
`
`he path featares include all the features mentioned in Chapter 3. One additional featare was
`
`tneremnentally are considered.
`addesd the starting time ofthe path relative to the starting time of the gesture. Thus, for example,
`a gesture consisting of two fingers, one above the other, which enter thehell of view of the Sensor
`
`Prame simultancously and move right in parallel can be distinguished from a gesture in which a
`single finger enters the field first, and whue it is moving right a second finger is brought into the
`viewfickd and moves right. In particular, the classifier Gorthe secondsorting index) would be able
`to discriminate between a path which begins at the start of the gesture and anc which begins later,
`The path start timeis also used for path sorting, as describedin section $.2.
`The main purpose of the global feature vector is to discriminate between multi-path gesture
`classes whose corresponding individual component paths are indistinguishable. Por example, two
`gestures both consisting of two fingers moving right, one having the fingers oriented vertically, the
`other honzontally. Gr, one having the Gingers about one half inch apart, the olher twa inches apart.
`Theglobal features are the duration ofthe entire gesture, the length of the bounding box diagonal,
`
`the bounding box diagonal angle (always between 0 and 7/2 so there are no wrap-around problems),
`the length, sine and casine between the first point of the first path andthe first paint of the last path
`(referring to the path sorting order), and the length, sine, and cosine between the first point of the
`first path and the last point of thelast path.
`Another noulti-path gesture attribute, which may be considered a global feature, is the actual
`number of pathsin the gesture. The numberof paths was not includedin the abovelist, since itis not
`included in the vector inputto thestatistical classifier. Instead, it is required that all the gestures of a
`given class have the sanic numberof paths. The aumberof paths must match cxactly fora gesture to
`be classified as a given class. This restriction has an additional advantage, in that knowing exactly
`the number of paths simplifies specifying the semantics of the gesture (see Section 8.3.2}
`The global features, crude as hey might appear, in most cases enable elective discrimination
`between gesture classes which cannot be classified solely on the basis of their constituent paths.
`
`5.6 A Further lmprovement
`
`As mentioned, the multi-pathclassifier has a path classifier for each sorting index. The path classifier
`for the first path needs to distinguish between all the gestures consisting only of a single path, as
`well as the first path m those gestures having two or more paths. Similarly, the secondpath classifier
`miust discriminate nat only between the second path of the two-path gestures, but also the second
`path of the three path gestures, andso on. This places an teimecessary burden on the path classifiers.
`Sinec gesture classes with different numbers of paths will never be confused, there is no necdto
`have a path classifier ableto discriminate between their constituent paths. This observation leads to
`a further improvernent in the multi-path recognizer.
`‘The improvement is instead of having a single multi-path recogniver for discriminatimgbetween
`rufti-path gestures with differing nembers of paths, to have one roulti-path gesture recognizer, as
`
`Page 1254 of 1714
`
`Page 1254 of 1714
`
`

`

`‘
`36
`
`CHAPTER & MULTI-PATH GESTURE RECOGNITION
`
`described above, for cach possible number of paths. There is a multi-path recognizer for gestures
`consisting of only one path, another for two-path gestures, and so on, up until the maximum qumber
`of paths expected. Each path classifier now deals only with those paths with a given sorting index
`fromthose gestures with a given oumber of paths. The result is that many of the path classifiers
`have fewer paths to deal with, and improve their recognition ability accordingly.
`Of course, for input devices in which the number of paths is fixed, such as the DataGlove, this
`Lprovement does not apply.
`
`5.7 An Alternate Approach: Path Clustering
`
`The multi-path gesture recognition implementation for the Sensor Frame relies heavily on path
`sorting. Path sorting is used to decide which paths are submitted to which classifiers, as well as in the
`mlobal feature calculation. Errors in the path sarting G.e. sinular gestures having their corresponding
`paths end up in different places in the path ordering) are a potential source of musclassifications.
`Thus, it was thoughtthat a raultt-path recognition method that avoided path sorting might potentially
`be more accurate.
`
`5.7.1 Giohal features without path sorting
`
`The first step was to create a global feature set which did nai rely on path sortimg. As usual, a niajor
`design criterion was that a small change in a gesture should result in a small change in its global
`features. Thus, features which depend largely upon the precise order that paths begin cannot be
`used, since two paths whichstart almost sirnultaneously may appear in either order. However, such
`features can be weighted bythe difference in starting times between successive paths, and thus vary
`smoothly as paths change order. Another approach which avoids the problemis to create global
`features which depend on, say, every pair of paths; these tog would be immune to the problems of
`path sorting.
`The global features are based on the previous global features discussed. However, for each
`featare which relied on path ordering there, two features were used here. The first was the previous
`featarc weighted by path start hime differcnees. Far cxampic, one feature is the length fromthe first
`point of the first path to thefirst point of thelast path, multiplied by the difference between the start
`times of the first and second path, and again multiplied by the difference betweenthe start times of
`the last and next to last path. The second was the surn of the feature between every pair path, such
`as the sumof the length between the start points of every pair of paihs. For the sine and cosine
`features, the sura of the absohite values was used.
`
`5.7.2 Multi-path reeegnition using one singie-path classifier
`
`Path sorting allows there to be a numberofdifferent path classtfers, onefor the first path, one for the
`second, and sc on. ‘lo avoid path sorting, a single classifier is used to classify all paths. Referring
`to the example in Section 5.4, a single classifier would be used to distinguish beiween Ay, Ao, Bi,
`and By.
`
`Page 1255 of 1714
`
`Page 1255 of 1714
`
`

`

`4&7 ANALTERNATE APPROACH PATH CLUSTERING
`
`89
`
`Once all the paths in a gestare are classified, the class information needs to be combined to
`produce a classification for the gesture as a whole. As before, a decision tree is used. However,
`simce path sorting has been elimunated, there is aow no apparent order of the classes which will
`make up the sequence submitted ta the decision tree. To remedythis, each path class is assigned an
`arbitrary distinct integer duringtraining. The path class sequenceis sorted accordingto this infegerr
`ranking (the global feature classification remains last in the sequence) and then the decision tree is
`examined. The net result is that each node in the decision tree corresponds to a set (rather than a
`sequence) of path classifications. (Actually, as will be explained later, each node corresponds to a
`maultiset.)
`
`the lone path classifier determines the
`In essence, the recognition algorithm is very simple:
`classes ofall the paths in the gesture; this sct of path classes, together with the global feature class,
`determines the class of the gesture. Unfortunately, this explanation glosses over a serious conceptual
`difficulty: In order to train the path classifier, known instances of each path class are required. But,
`without path sorting, how is it possible to know which of the two paths in an instance of gesture
`class Ais A; and which is 49? One ofthe paths of the first A example canarbitrarily be called Aj.
`Once this is done, which of the paths in cach of the other examples of class Aare in A)?
`
`Awhich is semtlar to the path previously called A, should also be called A).Ifa gesture class has
`
`Once asked, the answer to this question is straightforward. The path in ne second instance of
`Nopaths,
`tthe goal is to divule the set of paths used inall the training svaanplesofthe class inte NV’
`
`groups, each group cantaining exactly one path frarn each example. Hdeally, the paths forming a
`group are similar to each other, or, in other wards, they correspond to one another.
`Note that path sorting produces exactly this set of groups. Within all the examples of a given
`gesture class, all paths with the same sorting uidex form a group. However, if the parpose of the
`endeavorts to build a multi-path recognizer which does not use path sorting, if seenis Inappropriate
`to resort to it during the training phase. Errors in sorting the example paths would get built
`intothe
`path classifier, likely nullifying any beneficial effects of avoiding path sorting during recognition.
`Another waytc proceedis by analogy. Within a given gestureclass, the paths in one exampleare
`compared to those of another example, and the corresponding pathsare identified. The coniparsons
`could conceivably be based on the featere of the path as well as the location and timing ofthe path.
`This approach was not tried, thoughin retrospect it seems the simplest and most likely to work well.
`
`=“e
`oe! 4 Chistering
`
`Instead, the grouping of similar paths was attempted. The definition of similarity here only refers
`to the feature vector ofthe path. In particular, the relative location of the paths to one another was
`ignored,
`‘lo group similar paths together solely on the basis of their feature vectors, a statistical
`procedure known as hierarchical cluster analysis {74] was apphed.
`‘The first step in chister analysis is to create a triangular matrix containing the distance between
`every pair of samples, in this case the samples being every path of every example ofa given class.
`‘The distance was computed byfirst normalizing each feature by dividing bythe standard deviation.
`(The typical normalvation step offirst subtracting out the feature orean was omitied since il has
`
`no effect on the difference between two instances of a featere.) The distances between each“pair of
`
`Page 1256 of 1714
`
`Page 1256 of 1714
`
`

`

`30
`
`CHAPTER & MULTI-PATH GESTURE RECOGNITION
`
`example path feature vectors was then calculated as the surn of the squared differences between the
`normalized features.
`
`the clustering algorithm produces a chister tee, or dendrogram A den-
`Fromthis matrix,
`drogram is a binary tree with an additional linear ordering on the interior nodes. The clustering
`algorithm imitially considers each individual sarnple to be im a group {cluster} of its own, the distance
`pur. giving distances between every pair of groups. The two most similar groups. Le. the pair
`corresponding to the smallest entry in the maatrix, are combined into a single group, and a node
`representing the newgroup is created in the dendrogram, the sabnodes of which refer to the two
`constituent groups. Thedistance matrix is then updated, replacing the two rows and colurans of the
`constituent groups with a simgic row and cohimnrepresenting the composite group.
`The distance of the composite group to each other group is calculated as a function of the
`distances af the two constituents to the other group. Many such combining functions are possible;
`the particular onc used here is the group average mcthod, which computes the distanceofthe newly
`formed group to another groupas the average (weighted by group size) of the two constituent groups
`to the other group. After the matrix is updated, the process is repeated: the smallest matrix clement
`is found, the two corresponding groaps combined, and the matrix updated. This continnes until
`there is only one group left, representing the enlire saraple set. The order of node creation gives the
`linear order on the dendrogramnodes, nodes created early having subnodes whose groups are more
`similar than nodescreated later.
`
`Figure 3.4 shows the dendrogramfor the paths of 10 3-path clasp gestures, where {he thumb
`moves sliehtly right while the index and middle fingers move left. The leaves of the dendrogram
`are labeled with the mumbers of the paths of the examples. Notice howall the right strokes cluster
`together (one per example), as do all the loft strokes (twe per exampic).
`Using the dendrogram, the original samples can be broken into an arbitrary (between one and
`the number of samples) number of groups. To get A’groups, onesimply discards the top N-~- 1 nodes
`of the dendrogram. For example, to get two groups, the root node is discarded, and the two groups
`are represented bythe two branches of the root nadc.
`‘Taming back nowto the problem offinding corresponding paths in examples of the same mulu-
`path gesture class, the first step is to compute the dendrogramofall the paths in all examples of
`the gesturc, The dendrogram is then traversed in a hottom-up (post-order) fashion, and at cach
`node a histogram that indicates the count of the number ofpaths for each example is computed.
`The carmputation is straightforward: for each leaf node U.e. for each path) the count is zero forall
`examples except the one the path came from: for cach interior node, each element ofthe histogram
`is the sumofthe corresponding elements of the subnode’s histogram.
`ideally, there will be nodes in the tree whose histogramindicates that all the paths below this
`node come from different examples, and that cach example is represented exactly once. In practice,
`however, things do nat work out this nicely. First, errors in the clustering sometimes group two
`paths trom the same cxample together before grouping one path from every exaraple. This case
`is easily handled bysetting a threshold, eg. by accepting nodes in which paths from all but two
`examples appear exactly once in the cluster.
`It is possible that two or more paths im a single
`The second dilficully is more fundamental.
`gesture are quite similar (rememberthat relative path location is being ignored). This is actually
`
`Page 1257 of 1714
`
`Page 1257 of 1714
`
`

`

`4&7 ANALTERNATE APPROACH PATH CLUSTERING
`
`91
`
`waeeennnennnnnl
`
` {
`
`
`
`
`
`|
`
`!
`
`32 54
`
`80 42
`
`i
`
`bof
`
`O1 31
`
`92 7 82
`
`|
`
`60 24 92
`
`BC
`
`21
`
`12 62 G2
`
`30 40
`
`41 72 52
`
`22 91
`
`90 10
`
`70 9G €1
`
`Ri yy
`ny
`6
`etye-eom SL
`.
`“em 21 _ PPB20-O0E 21
`20 we
`tom Roux | ||
`ws Bee» 91
`
`
`coooo=K=K QF +epee-20e-te2 12 Bee 5 > ta se 42 ee aa
`
`
`
`
`12
`2
`mts
`seems 60
`
`Boao 5 Z
`51 esporene
`50
`
`Peresere 6
`aL POOPOKORE
`62
`Bd
`
`Semen 74
`‘70 aoe
`a
`cee 5
`
`ae
`
`ao
`
`wonnen-n-o-0- 5
`meeer—ee
`
`go Oi
`GD ros00%-=iF *
`90
`Leeaeeare
`
`Figure 5.4: Path Chuisters
`This shaws the resuit of clustering applied to the thirty paths of the ten three-path Clash gestures shown.
`
`
`The
`Fach clasp gesture has a short, rightward moving path and two similar Jongleftward moving paths.
`hierarchical clust
`eringalgorithin groups similar paths for groups ofpaths} together The height ofan interior
`o
`ee OF
`ut subti
`Note that the righ
`node indicates the similarity of its groups, lower nodes being more stinilar
`i
`tf is tf
`goodcluster (indicated
`the roof contains 10 paths, oue from each imulti-pail: gesture.
`qus ferred 4
`astituent paths correspond. The |
`eff subtree containing 20 paths,
`two
`by a circ
`ithe graph], and [ts co.
`Had one oftis descendants been anather goodcluster (containing
`approximately 10 paths, one from each gestre}, tt would have been conctudedthat all three paths ofthe
`
` clasp ,
`sture are diffe
`
`ding paths given by the good clusters As it happer
`with the correspon
`descendant of the left subtree was
`
`a good cluster, sa it is concluded that
`wo ofthe paths within the C
`gesture are similar and will thus be treated as examples ofone sfogle-path class.
`
`from nachgesture, 1s aiso a goodchuste
`
`Page 1258 of 1714
`
`Page 1258 of 1714
`
`

`

`92
`
`CHAPTER & MULTI-PATH GESTURE RECOGNITION
`
`common for Sensor Frame gestures that are performed by moving the elbow and shoulder while
`keeping the wrist and fingers rigid. Por these paths, it is past as lukely that the two paths of the sare
`example be grouped together as u is that corresponding paths of different examples be grouped
`together Thus, mstead of a histogram that shows one path from each example, ilealby there will be
`a node with a histogramcontaining two paths per example. This is the case in figure 5.4.
`Call a node which has a histogram indicating an cqual (or almost equal) namber of paths from
`each example a good cluster. The search for good chusters proceeds top down. The root node is
`surely a good chister; eg. given examples from a three path gesture class, the root node histogram
`will indicate three paths from each example gesture. If no descendants of the root node are good
`clusters, that indicates that all the paths of the gesture are simular, However, if there are good clusters
`belowthe root Qvith fewer oxarnpies per path than the root), that indicates that not all the paths of
`the gesture are similar to cach other. In the three path example, if, say, one subnode of the root nade
`was @ good cluster with one path per example, thase paths forma distinct path class, different than
`the other path classes in the gesture class. The other subnode of the roor will alse be a good cluster,
`with two paths per example. If there does not exist a descendant of that node whichts a good cluster
`with one path per example, that indicates that the two gesture paths classes are similar. Otherwise,
`goodclusters below that node (there will likely be two) indicate that each path class in the gesture
`class is dilferent. The cluster analysis, somewhat like the path sorting, indicates which paths m each
`example of a given gesture class correspond. (Goodclusters are indicated bycircles in figure 5.4.)
`Occasionally, there are straggicrs, paths which are not in any of the good chisters identried
`by the analysis. An attempt is made to put the stragelers in an appropriate group. If an example
`contains a single straggler it can easily be placed in the group which is lacking an example from
`this class, If an example contains more than one straggler, they are currently ignored. Hf desired, a
`path classifier to discriminate between the good chisters could be created and then used to classity
`the stragglers. ‘his was not done in the current unaplementation since there was never a significant
`nurpber of stragglers.
`Once the path classes in each gesture class have been identified using the clustering technique, a
`path classifier is trained which can distinguish between every path class of every gesture class. Note
`that if is passibic for a path class to bc formed from two or more paths fromcach exampleofa singic
`gesture class, ithe cluster analysis indicated the two paths were similar Hf analogy techniques were
`used to separate such a class into multiple “one path per example” classes, the resulting classifier
`would ambiguously classify such paths.
`In any case, ambiguities are sul possible since different
`gesture classes may have similar gesture paths. As in Section 5.4, the ambiguities are removed from
`the classifier by combining ambiguous classes into a single class. Fach (Gaow unambiguous) class
`whichis recognized by the path classifier is numbered soas to establish a canonical order for sorting
`path class sequences during training and recognition.
`
`3.7.4 Creating the decision tree
`
`3
`After the single-path and global classifiers have been trained, the decision tree must be constructed.
`As before, in the class phase, for each multi-path gesture class, the (now unambiguous) classes of
`each constituent path are enumerated. Since two paths in a single gesture class may be similar,
`this enumeration of classes may list a single class more than onee, and thas may be considered a
`
`Page 1259 of 1714
`
`Page 1259 of 1714
`
`

`

`&S& DISCUSSION
`
`93
`
`muluset. The list of classes is sequenced into canonical order, the global feature class appended, and
`the resulting sequence is used to add the omlti-path class to the decision tree. As before, a coniict,
`due to ihe fact that bvo dillereri gesture classes have the sanie muiluisei of path classes, is fatal.
`Next comes the example phase. The paths of each example gesture are classified bythe single
`path classifier, and the resulting sequence Gn canonical order with the global feature class appended}
`is used to add the class of the example to the decision tree. Usually no work needs to be done, as
`the same sequence has already been used to add this class (usually in the class phase}. However, if
`one of the paths in the sequence has been misclassified, adding it to the deciston tree can improve
`recognition, since this misclassification may occur again in the future. Conflicts here are not fatal,
`but are simply ignored on the assumption that the sequences added in the class phase are more
`important than those addedin the exaniple phase.
`
`5.8 Discussion
`
`‘Swo multi-path gesture recognition algorithms have been described, which are referred to as the
`“path sartmg” and the “path clustering” methods.
`In situations where there is no uncertainty as to
`the path index information (e.¢. a DataGlove, since the sensors are attached to the hand) then the
`path-sorting methodis certainly superior However, with input deviees such as the Sensor Frame,
`the path sorting has to be done heuristically, which increases the likelihood of recognition error.
`‘The path-clustering method avouls path sorting and its associated errors. However, other sources
`of misclassificationare introduced. One single-path classifier is used ta discriminate betweenall the
`path classes in the system, so will have to recognize a large numberof classes. Since the error rate
`of a classifier increases with the namber of classes, the path classifier in a path-clustering algonthm
`will never perform as well as those in a path-sorting algorithm. A second source of crror is in the
`clustering itself; errors there cause errors in the classifier aiming data, which cause the performance
`of the path classifier to degrade. One way around this is to cluster the paths by hand rather than
`by having a computer performit automatically. This needed to be done with some gesture classes
`from the Sensor Frame, which, because of glitches in the tracking hardware, could not be clustered
`reliably.
`¥n practice, the path-sorting method always performed better, The poor performance of the
`path-clastering method was generally due to the noisy Sensor Frame data. Itis however difficult to
`reach a general conclusion, as all the gesture sets upon whichthe methods were tested were designed
`with the path sorting algorithm in mind. Tt it easy to design a set of gestures that would perform
`poorly using sorted paths. Qne possibility for future work is to have a parameterizable algorithm
`for sorting paths, and choose the parameters based on the gesture set.
`‘The Sensor Frameitself was a significant source of classification errors. Sometimes, the knuckles
`of fingers curled so as not to be sensed would inadvertently break the scnsing planc, causing extra
`paths in the gesture Gvhich would typically then be rejected}. Also, three fingers in the sensing
`plane can easily occlude each other with respect to the sensors, making it difficult for the Sensor
`Frame to determine each finger’s location. The Sensor Prame hardware usually knewfrom recent
`historythai there were indeed three fingers present, and did its best to estimate the positions af each,
`However, the resulting date often had glitches that degraded classification, sometimes by canfasing
`
`Page 1260 of 1714
`
`Page 1260 of 1714
`
`

`

`o4
`
`CHAPTER & MULTI-PATH GESTURE RECOGNITION
`
`It is likely that additional preprocessing of the paths before recognition
`the tracking algorithm.
`would improve accuracy. Also, the Sensor Prame itself is still under development, and i is possible
`that such ghiches will be eliminated bythe hardware in the future.
`Another area for future work is to apply the single-path eager recognition work described in
`
`Chapter 4 to the eager recognition of multt-path gestures. Presumably this is simply a matter of
`eagerly recognizing cach path, and combining the results using the decision tree. Howwell this
`works remains to be seen.
`
`It woald also be possible to apply the raulti-path algorithm to the recognition of multi-stroke
`gestures. The path sorting im this case w