CH-/1P‘IE'1?<” 5 11/1’LiL.jz'1’»-R411 TURE I{:E'COG1\E]'YOI\v’
`
`11 1’§'z‘.11Cl--]3BC1l gesture classes
`
`'c
`
`Q
`
`R
`
`S
`
`cu‘-,‘
`
`0
`
`_',,a..,, 1
`
`
`
`w~,
`to
`\
`0
`
`-
`‘X
`1
`
`Mu1ti~path
`Input
`
`i~———e——u»-.1.
`3._—n—._...
`
`~"~_
`
`
`
`
`
`K‘
`
`S Lchcxseu -;;es‘:=_u'e;
`
`Figure 5.3: C1assifyi11gmuiti-path gestures
`/1[‘ the top are cxamplcs 0fA‘E7u1‘ {Wmpa :12 g-1i'.s:u'1”CS cxpcc {Cd
`f1'21's Classiffc-1; and (3 t tbc [off a IWo—pa I12 gcstuz‘-z?
` V]? by (110 rj'c)£f(?{f iinr-.9,
`2'1’24:- Z}"?:'(‘ 170017
`/'5-ar:i7er,1’ 1'5 ambi_,z»;211M2s (Fm v:'z2g c}21'lriz‘et:r Q and S) 50 g gal fean12‘e.s are .2/sea’! Li; 1v9.s‘r,2IL'¢= the 4;"i5(,:1‘ep.-az;-(gyg and
`the
`1'5 rer;9 ;i;1'2es;’ as (71.3 55 S.
`
`Page 1251 of 1714
`
`SAMSUNG EXHIBIT 1006 (Part 7 of 8)
`
`Page 1251 of 1714
`
`
`
`SAMSUNG EXHIBIT 1006 (Part 7 of 8)
`
`

`
`5 4 3'i’\Z<li’i7‘J NE A ]‘v;»'UL II»-If/UH’ CL/5LS':'{IFI.E‘R
`
`54 Training a llvlaltiupatli Classifier
`
`examples of each multiv-path gesture class
`The training algorithm for a tnulti--path classifier
`(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 number of path classifiers, and
`decision
`tree.
`
`5.4-ti Creating the statistical classifiers
`
`The path classifiers and the global classifiers are created using the statistical algorithm (lCSCI‘;ll3C(l in
`Chapter 3. The paths of
`example are sorted, the paths for a given sorting index in each
`forniing a class used to train the path classifier for that index.
`For example, eonsitler training a niulti--path classifier to ttiscriininate hetween two niulti-path
`gesture classes, A and Br, each consisting oi‘ two paths. tiiesture class A consists oi‘ two path classes,
`A; and fig. the subscript inclicating the sorting indices of the paths. Similarly, class 5 consists of
`path classes B; and B3. The tirst path in all the /l e>-Laniples i"orm the class A1,, and so on. The
`examples are used to train path classifier l to rliscriniinate hetwcen At and 8;, and path classifier
`2 to discriminate
`A3 and E3. The global features of A and B are
`to
`the global
`classitier, tioiriina.lly able to cliserirninate between two classes of glolial featurest Al(; and 185".
`Within a given sorting index“, it
`quite possible and legitimate for paths froin ttilferent gesture
`classes to he iiidistingiiisliahle. For Bxétlllpla, path classes A; and B; may both he straiglit right
`stroltes. (liaesuniably A and B are distinguishable hy their secontl paths or global t'eatui'es,Ti hi this
`it is lilrely that exatnples of class A; will he mis-;.:lassit"ied
`B; or vice versa it is desirable to
`rcrnove these anihi guitics irorii the path classitierhy conihining all classes which could he rnistaltcn
`for each other into a single class.
`A nuinher of approaches could be taken for detecting and re moving ainhi guities from a. statistical
`classitiet. One possible approach would be to compute the Mahalanohis ttisiance hetween each pair
`ol‘ classes, merging those below a given threslioltl. Another approach involves applying a clustering
`algorithin [74] to all the examples, ineiging those classes whose tnenibers are just as likely to cluster
`with examples from other cl as their own. A third approach is to actually evaluate the actual
`peitorrnance of a classifier which attempts to distinguish hctween possibly anihiguous cl asses; the
`ntisclassitieations oi" the classifier then indicate which classes are to he rnergetl, The latter approach
`was the one pursued here.
`A naive approach for evaluating the performance of a classifier‘ would be to COl1SlI1l{‘i the
`classilier using Et set oi’ examples, anti then testing the perlorniance oi" the classilier on those very
`same examples. This approach obviously tniderestiniates the ambiguities of the classes since the
`classifier will he hiased toward correctly classifying its training exantples [62]. lnsteatl, a elassitiei’
`is constructed using only a small number of the exarnplcs (typically tive per class) and then
`the remaining examples to evaluate the constructed elassitiers. Misclassifications of the
`then indicate classes which are ambiguous and should he rnerged.
`In practice, thresholds must he
`established so that a single or
`small percentage. of niisclassiti.cations does not cause a merger.
`Matlierriatically, combining classes
`simple operation. The mean vector ol‘ the cornbiiietl
`class is eotriputerl as the average of the mean vectors of the component classes, each weightecl by
`
`Page 1252 of 1714
`
`

`
`CH;-4tP’I]E71i’
`
`A/1UL’1"}"»-Z3111}! YURE I~;’_t7'COG]‘vl’HO1‘v’
`
`A similar operation computes a composite average
`in the
`relative number ol‘
`covariance inatrix froin the covarhance inatrices of the
`heing eoinhined.
`The above algorithm, which removes arnhiguities by combining classes. is applied to each path
`classifier as well as the global classifier. lt remains now only to construct the decision tree for the
`multi -path cl
`
`5.4.2 Creating the decision tree
`
`inc.l.a.ss, a pointer to a n‘iulti~path gesture class, and next,
`A decision tree node has two fields:
`pointet to an array oi’ pointers to its stibnodes.
`'l‘o construct the decision tree, a root node is
`allocated. Then, during the class phase, each niulti-—path gesture elass is considered in turn. For
`eaech.
`:1 sequence of path classes (in sort index order), with its glohal t'e-attire
`appended,
`is
`eoiistnictecl. Nodes are created in the decision tree in such a way that hy following the sequence
`a leaf node whose mclass value is the content niulti-path gesture class is reached. This creates a
`decision tree which will correctly classify all niulti—class gesture whose component paths and global
`features are correctly classified.
`Next, during the exarnpiepliase, each e>:;atnple gesture is eonsitlered in turn, The paths are sorted
`and classified,
`are the glohal ‘features. A sequence is constructed and the class of the gesture is
`atlrled to the decision tree at the location conespoiitling to this sequ,eni::e
`before. Ntilrfllillly‘, the
`paths and global features of the gesture will have
`classified correctly, so there would already be
`a node in the tree corresponding to this sequence. llowever, if one of the paths or the global feature
`Vector of the gesture was classitied incorrectly., anew node may he created in the decision tree, and
`thus the same classification ni,istal<e in the future will still result in a correct el3.ss,ilieation for the
`
`gesture.
`
`When attempting to add a el using a sequence whose eotnponents are nriiselassilications,
`it is possible that the decision tree node reaened already
`a non-null n7.c.l_ass field elerring
`to a L‘-.it'fei'ent niulti—path gesture class than the one whose ertaihpl.e is currently being considered.
`This
`a Co,z7f_Z:'z:t and is resolved by ignoring the current exaniple (though a waming message is
`printed). ignoring all but the first instance of a sequence insures that the sequences generated during
`the class phase will take precedence over those generated during the Cxfilllpltl phase. Oi" course.
`a coiiilittt oeeuri'itig during the class phase indicates a serio-its prohieint narnely a pair of gesture
`classes hetween which the miilti—path classifier is unahle to discriminate.
`entiy with a
`During decision tree eonstnictioii, nodes that have only one global t‘ea.tui'e
`suhnode have theirmclas S value set to the same gesture class as the melas S Value of that suhnode.
`in other words, sequences that can be classified without referring to their global feature class are
`ll12Erl§;C4Zl as such This avoids the extra work (and potential for error) of global feature classification.
`
`5.5
`
`llath Features and Glohal Features
`
`'l'he mzlassltiaration of the individual paths and of the global features of a inulti-vpath gesture are
`central to the iiiulii--path gesture recognition algoiithtn discussed thus far. This section describes the
`particular feature vectors used in more detail.
`
`Page 1253 of 1714
`
`

`
`5 6 A F UR;l'HER Llfl”RO l«.’E‘_t’l,/.E.«"v’i’"
`
`87
`
`The elassillcation algonthrn used to classify paths and global features is the statistical algoritliin
`discussed in ‘Chapter 3, thus the erjteria fill‘ feature selection tliscussed in section
`must he
`arltlresseti.
`in particular, on y l'eatures with Gaussian~lii<e distrihuti:;iiis that can be calculated
`inereinentaily are tronsidered.
`One additional feature was
`The path features include all the features mentioned in Chapter
`added: the starting time of the path relative to the startin tithe of the gesture. Thus, for example,
`a gesture eonsistin of two lingers, one ahove the other, which enter the field of view of the Sensor
`Fraiite simultaneously and move right in parallel can he distinguished from a gesture in which a
`single
`enters the field tirst, and while it moving right a second
`is brought into the
`viewfteltl and tnoves right. in particular, the classifier {for the second sorting iridexl would he ahle
`to discriminate between a path which hegins at the start of the gesture and one which begins later.
`The path start time is also used for path sorting, as described in section 5.2.
`The main purpose of the global feature vector is to discriminate hetween multi-path gesture
`classes whose corresponding individual eoniponeiit paths
`indistinguishalule. Poi" example, two
`gestures hoth consisting of two lingers inovin g right. one having the fingers oriented Vertically. the
`other horizontally. Or, one having the lingers about one hall‘ inch apart, the other two inches apart.
`The global features are the duration of the entire gesture, the length of the hountling hos diagonal,
`the honnding ho); diagonal angle (always between G and in
`7’ so there are no wraparound prohlerns),
`the length, sine
`cosine between the first point or" the first path and the first point of the last path
`(ieietiriiig to the path sorting order), and the length, sine, and cosine between the
`point of the
`iirst path and the last point of the last path.
`global feature. is the actual
`Another tnulti—path gesture attribute. wliieli may he considered
`number of paths in the gesture. The nuniher of paths was not included in the above list, since it is not
`included in the vector input to the statistical (3l£lSSlll€T_
`lnstead, it is required that all the gestures of a
`given class have the same nurnher of paths. The nuinher of paths niust thatch exatrtly for a gesture to
`he
`as
`given class. This restriction has an additional advantage, in that ltnowing exaetly
`the number of paths simplifies specifying the semantics of the gesture (see Section 83.2),
`The global leatures, crude as they might appear, in most cases enahle eil'eetive discrimination
`between gesture
`which cannot he elassitied solely on the ‘basis of their eonstituent paths.
`
`5.6 A Further lrnprnvernent
`
`As mentioned, the niulti-path classifier a path classifier for earth sorting index. The path classifier
`for the
`path needs to distinguish between all the gestures consisting only of a single path, as
`well as the first path in those gestmes having two or niore paths. Siniiiarly, the se-;:ond path til-assitier
`must diseriniinate not only between the second path of the two--path gestures, hut also the second
`path of the three path gestures, and so on. This plaees an unnecessary harden on the path classitiers.
`Sinee gesture classes with tlitfererit nunthers of paths will never he confused, there is no need to
`have a path classifier able to discriminate between their constituent paths. This observation leads to
`a further inipruvernent in the niulti~path recogiiizei".
`The lt11pl'0\/(‘.l1ltZ‘.lli is instead of having a single nnilti--path retmgnizer for diseriniinating between
`n1ulti—path gestures with differing nulnhers of paths, to have one rnulti—path gesture recegnizer, as
`
`Page 1254 of 1714
`
`

`
`CH;-4iP’I]E71{’
`
`A/1ULJl"»-B1llH YURE I~;’_ECOG]‘vY1"YO1‘\/
`
`descn bed ahuve, for each possible it umber of paths. There is a multi—path recognizer for gestures
`eunsisting of only one path, I-mother fur twu—pa.tli gestures, and st) (in, up until the ma , llltlt number‘
`of paths expecterl. Each path elassi tier new deals only with those paths with a given sorting imlex
`frurn these gestures with a given nurnher of paths. The result is that many of the path
`have few ‘er paths to deal with. and improve their recognition ability aecorrilngly.
`Of course, for input devices in which the number of
`is tixetl, such as the Datafilove, this
`impruvernent does not apply.
`
`5.7 An Alternate Appreaeh: Path illustering
`
`fhe rnulti~path gesture recognition irnplemeutution for the Sensor Frame relies heavily on path
`sorting. Path setting is usecl to tlecicle which paths are s'uhlnitted to which iclassiiiers, as well
`in the
`global feature calculation. Errors in the path sorting (1. e. similar’ gestures liavirtg their currespontliiig
`paths end up in rlifferent places in the path urdering) are a potential source uf iniselassificatiuns.
`Thus, it was thought that a rnulti—path t'ee<>griitii'sn metln'nl that avoided path sum’ n g mi ght potentially
`he inure accurate.
`
`5.7.1 Gluhal features withuut path suiting
`
`The first step was to create tit global feature set which did next rely en path starting. As usual, at major‘
`design criterion was that a small change in a gesture should result
`a small change in its global
`features. Thus, features which depend largely upon the precise order’ that paths begin cannot he
`userl, since two patlis which start alnlsisst simultaneously niay appear in either order: However‘. such
`features can he weighted by the difference in starting times between successive paths. and thus Vary
`smoothly as paths change order. Another approach which avoids the problem is to create global
`features which depend on, say, every
`of paths; these tee would he innuurte to
`problems of
`path sortj ng.
`The global features are hasetl on the previous global features discussed. However, for each
`feature which relied on path ordering there, twu features were used here. The first was the previous
`feature weighted by path start time differences. For exaniplc, one feature is the length from the first
`point of the first
`te
`first point of the last path? multiplied by the differeiiee betweert the start
`tinies of the first and second path. and again rnultiplietl hy the cliffereuce between the start times of
`the last and next tu last path. The seeund was the sum of the feature between every pair path. such
`as the Still} of the length hetween the start points of every pair of paths. For the sine and t;iOSlttt3
`features. the sum of the absolute values was used.
`
`5.7.2 Multhpath reeugnitiun using tune single~path elassifier
`
`Path sorting allows there to he a number of rliffererit path classifiers, one for the first path, one for
`second, and so on 'll:t avuid path sorting, a single classifier
`used to classify
`paths. Referring
`to the exalnple in Section
`a single elassilier waitultl be used to rlistinguisli between A1. zlg, B1.
`and
`
`Page 1255 of 1714
`
`

`
`5 7 AN./¥'n_’.2’2ii'I\’J\/}‘l}t'E ./~l1'—’PI»3t’)./ilCI-i".* IZQIH CLtJ.<.'i’;E‘Rz?v‘t7-
`
`combined to
`Once all the paths in a gesture are classified, the class infonnation needs to
`proriuce a elassirieatioit for the gesture, as a whole. As hetore, a tleeision tree is used. However,
`since path sorting has heen cli mi nate=;l, there is now no apparent ortler ot" the classes which will
`matte up the setpience stlbtnittetl to the decision tree. To remecly this, each path class is assigneai an
`arbitrary distinct integer during training. The path class sequence is sortetl according to this integer
`ranlting (the glohal feature classification remains last in the sequence) and then the decision tree
`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 he explained later, each notle corresponds to a
`in ultiset.)
`
`classifier tletennines the
`the lone
`in essence, the recognition algoritlini is Very simple:
`classes of all the paths in the gesture; this set of path classes? together with the global feature class,
`deterinines the class of the gesture. Unfortu nately, this explanation glosses over a serious conceptual
`tliflicttlty: In order to train the path classifier. lrnown instances of each path class are required, But,
`without path sorting, how is it possible to know which or the two paths in an instance of gesture
`class A is /-‘l; and which is :43‘? One of the paths oi‘ the that fl example can arbitraril he ealletl /11.
`Once this is done, which of the paths in each of the other examples of class 11; are in .41‘?
`Once asked. the answer to this question is straightt'orwarrl. Tlie path in the second instance of
`A which is similar to the path previously called .41 should also he called .41. if a gesture class has
`.Npa.ths. the goal is to divide the set of
`used in all the training exaniples of the class into N
`groups, each group containing e>:actly one path frorn each e>:;arnple.
`ltleally, the paths forming a
`group are similar to each other, or. in other wonls, they correspond to one another.
`Note that path sorting pl’0£lUC€S exactly this set of groups. ‘Within all the exarnples of a given
`gesture class, all paths with the same sorting iiidex form a group. However, if the purpose of the
`endeavor is to build a rnulti—path recognizer which tloes not use path sorting. it seems inappropriate
`to resort to it during the training phase. Errors in sorting the example paths would get huilt into the
`path classitier, likely tttillityiitg any heneticial effettts of avoiding path sorting during recognition.
`Another way to proceeti.
`by analogy. Within a given gesture class, the paths in one example are
`compared to those oi‘ another example, and the corresponding paths are itlentiiied. The comparisons
`cottltl conceivably
`based on the feature of the path well
`the location and timing of the path.
`This approach was not tried. though in retrospect it seems the simplest and most likely to W0l'l{ well.
`
`5.7.3 Clnsterln{,>;
`
`instead. the grouping of sinrilar paths was attempted. The (letinition of similarity here only refers
`to the feature vector of the path. in particular. the relative location of the paths to one another was
`igrtored. to group similar paths together solely on the basis of their feature vectors, a statistical
`procedttre lznown
`Zriez'ar(:hi'(:a/ citz.<;te1"anai}«:s‘i'.s ['74]
`applied.
`The iirst step in cluster arta.lysis is to create a triaitgular
`-containing the distance hetween
`every pair of samples. in this case the samples being every path of every example of a given class.
`The distance was compntecl hy first normalizing each feature hy tlividing by the standard tleviation.
`(The typical l10t'tl1£1ll.£:':tll0ll step ol lirst subtracting out the leatttre mean was omitted since it has
`no effect on the tlifference between two instartces of a t"eatut'e;) The distance between each pair or
`
`Page 1256 of 1714
`
`

`
`90
`
`t:H;-4tPI]E7R
`
`A/1ULJl"»-B!lfH YURE I~;’_t'7COGNi'HO1‘v’
`
`example path feature vectors was then calculated
`horirtalized ieatures.
`
`the sum of the squared di l:l"t3t‘<31*.C€S hetween the
`
`the clustering algorithm protluees a cluster tree. or r,z’<:~r;a’t'r)g1'airz. A den-
`Front this matrix,
`drograni is a binary tree with an additional linear ordering on the interior nodes. The clustering
`algorithm initially C01‘lSltl€1’S each individual sample to he in a group (cluster) of its own, the distance
`tnatrix giving tlistanees between every pair oi" groups. Tlie two most sitnilar groups, 1'. e. the pair
`eon'esponth'ng to the smallest entry in the matrix; are combined into a single group. and a node
`representiing the new group is created
`the (l.€Tl(ll‘0gt”t";ttTl.,
`the snhnoties of which refer to the two
`constituent groups.
`aiistance iriatrlx is then uprlatetl. replacing the two rows and columns of the
`constituent groups with a single row and column representing the coinposite group.
`
`The distance of the composite group to each other group is calculaterl as a ttinetioii or" the
`distances of the two constituents to the other group. Many such combining functions are possible;
`the particular one used here is the g‘1‘0t1p at'e1'ager1ictl1otl, which computes the distance of the newly
`formed group to another group
`the average tfweiglited hy group size‘) of the two constituent groups
`to the other group. At"tet' the matrix is updated, the process is repeated: the smallest matrix element
`is found, the two correspontlirig groups eonihinetl, and the matrix updated. This continues until
`there is only one group left, representing the entire sample set. The order oi’ node creation gives the
`linear order on the tlentlrograrn nodes, notles created early having suhnotles whose groups
`more
`similar than nodes created later.
`
`Figure 5.4 shows the ttentlrograrn for the paths of it) 3—path clasp gestures, where the thumb
`rnoves slightly right while the index and ntitltlle
`iriove left. The leaves of the tlentlrogratri
`are labeled with the numbers of the paths of the examples. Notice how all the right strokes cluster
`together (one per exantple).
`do all the let"t sti'ol<,es (two per example).
`
`be broken into an arbitrary (between one and
`Using the rlentlrograrn, the original
`the number of samples) number of groups. To get Ngroups, one simply tliscurtls
`top 1“\/7~ l nodes
`of the rien-:li‘ograrn. For example, to get two groups, the root norle is rlisearrlerl, and the two groups
`are rcprcsciitcr.l by the two branches of the root node.
`
`Turning haul; new to the prohlern of finding corresponding paths in exarnples of the same multi-
`path gesture class, the tirst step is to compute the tlendroginnt of all the
`in
`examples of
`the gesture. The rlentlrograni is then trayerscr_l in a hottoni~up (post~orr.ler) fashion, and at each
`node a histogram that indicates the count of the number of paths for each e.\:a.rnple is eotnputetl.
`lfhe cornputation is str'aigl1tlorwartl: for each leaf node (1. for each path}
`count is zero for all
`eiraniples except the one the path canie front: for each interior node, each elenient of the histogram
`is the sum of the eorresporitling eletnents of the sul:3nocle’s histograni.
`
`nodes in the tree whose tiistogi'a.nt inrlieates that all the paths hetow this
`ideally, there will
`node conie lrorn differerit eyianiples, and that each example is represeritetl exactly once. in practice,
`however, things do not work out this nicely. First. errors in the clustering sornetirnes group two
`paths front the same example together before grouping one path from every example. This case
`is easily haritlletl hy setting a threshold.
`hy accepting nodes in which paths from all but two
`examples appear exactly once in the cluster.
`
`It is possible that two or more paths in a single
`The sect:-ncl dllllettlty is more l'un(laineiital.
`gesture are quite similar {r'errieriiher' that relative path location is being ignored). This is actually
`
`Page 1257 of 1714
`
`

`
`5 7 ANz¥'1;_’.2’2ii'I\’J\/}‘f\}!'E ./»§1'—’17I€Q4C'H‘
`
`IZZUH CLU5'1}E-”R&“v‘L3‘—
`
`r»»»»»»»»»»»»»»»>-
`
`1
`
`...............u
`
`70 90 El 80 42
`
`awn-var--av---I g 2
`
`muu..x._.._... S2
`
`nfiflov-at-not
`
`5 0
`
`Figure 5.4: ?-2:111 Clusters
`.S'h1)u'Ti.
`' his :.=.;'0w.s‘ I”;-e ream-'1' z:-1“ (‘i£I;‘§f€!‘iI'I_g ajapiiad (0 he .€I;'1'r.IfV paths of he tar) tht299—p.aI;r ciasp geasr'zI,"e.s'
`.m:‘}1 eta:-zp gE:.~!L!I“i?
`a simrig 1'1'gl1tv-/a1‘<i mov1'!;'_q ,‘
`sh and W1)’ :;imj.:'.a1; 10.15;’ ]st?w'a!’ci mo i/1173:; ,‘3a.f}25. The
`hi 1‘éz‘I”z'T}1I'C‘.éi}(Ti!15f(?E‘ifEg3I:gl)Z‘if[}}F)_g1UZ4gD:S 5it1;~1'I.a1' pa 5'1;-5 (sfigmzms ofpa ills) fogefizer The he1'gf2.f'0fa/2 infe1"z'o1'
`;,rm..e 1';
`1di'(;a fss (Z15 .s'_i112Uea;‘i1}-' 0,/',i{s gm.'.zp.s:, I01/ve,/' 1,im.:’es .bei,r1g 1120 .s‘imi.’a;,
`1'\r’u.f'.se ff}?/fl,’ file 1‘:'-‘(iii :sub.',a‘.s%:a 01"
`415* I'()U{ (S()fI."&‘i,F1.$ I U paiizs,
`(ill-£5 1}'c:I.v1 cigar}: ,r.r::,i!'/jz'—A}9a2/,1; gssizjzze,
`fl is ./is:/.5‘ {,ez'z.ti8e':’ :4 g:_;()(! €,‘]iI.'>.',c'3I’
`(iI1c1'ie;:: {ed
`V
`5: Ci”(7.’¢E‘ can {}'7€- g1‘.'ap-['1 , aI.ra'1'L_=;
`.::0I1sI'1'I':1€I1r'p52{izs
`c01‘r9::p.:2mz’. The 191‘: subzzee c'c2nZ'a1'm'I}g 2'0 paths,
`[M2
`
`L!
`
`if Wnziid /'73 Vt? i7-srén r7m7ciI1r3'c?(i fhaf all fizree pa fhs offrfir:
`a_ppr0Xi12mf:?!'_j.’ I 0 pa fl'7,~:, one M7122 ¢?az::"7 gesfI.'i‘(§),
`ciasp 4
`“Hire a1”.-—? £11’ 1% 7-17:. m’I‘_h {be cnrmspmjding paths gfv(—‘12
`ti)-9 gnaw‘ c1z:.st?rs. As it {mapper ‘a’, no
`de.<,:(.‘e1'1a'.az;'t of ii;-6 left .s'ubZI'ee ~.'»L’a5 a good 1:]iJ.§£81”, so z'."1':.: <70/2z:]udea’ thaf ism 0f.f,*’2r:- pafh.-5 w1't'hI'n ti, 7 clasp
`gestlwer are sizz;-ila I; aim’ Wil.’ (has be 4763 fed as e,\"aznpiss rjfmie .S'1'1}'.4:7,/€?—li}éi'{)l‘i <:I“5.s,
`
`Page 1258 of 1714
`
`

`
`92
`
`:‘:HL-4lPI]E71{’
`
`A/1ULJi"»-Z31lIH YURE RECOGi"t»HYO1‘\/
`
`common for Sensor Frame gestures that are performed by moving the elbow and shoulder while
`keeping; the wrist and lingers rigidi For these paths, it is just as likely that the two paths of
`same
`example he grouped together as it is that COF(t?S13tZ)tl(llllg paths oll tllliererit examples be grouped
`together. Tlitis, instead of a histogram that shows one path from each example, ideally there will he
`a node with a histogram containing two paths per exaniple. This is the ease in figure 5.4.
`Call a node which has a histogram iiidicating an equal (or almost equal) number oi" paths from
`each example a good cluster. The search for good clusters proceeds top down. The root node is
`surely a good cluster;
`given exaniples from a three path gesture class, the root node histogram
`will indicate three paths from each example gesture. ll no descendants of the root node are good
`cl rs, that indicates that all the paths of the gesture are similar. llowever, if there are goorl clusters
`helow the root {with fewer examples per path than the root), that indicates that not all the paths of
`the gesture are sirriilar to each other. in the three path example, if,
`one suhnorle of the root node
`was a good cluster with one path per exaniple, these paths form a distinct path
`different than
`the other path
`in the gesture class. The other suhnodc of the root will also he
`good cluster,
`with two paths per example. if there does not exist a descendant of that node which is a good cluster
`with one path per example, that intlicates that the two gesture paths classes are similar. Otherwise,
`good clusters below that norle (there will likely be two) indicate that each path class in the
`class is <;lil'l'erent,. The cluster analysis. soniewh-at like the path sorting, intlicates which paths in each
`example of a given gesture class correspontl. (Good clusters
`indicated by circles in Figure 5.4.)
`Occasiona.ll§a there are srragginrs, paths which are not in any of the good clusters irlentified
`by the analysis. An attei pt is made to
`the stragglcrs in an appropriate group. lf an cxaniplc
`contains a single straggler it can easily be placed in the group which is lacking an example from
`this
`if an exarnple contains more than one straggler, they are currently ignored. ll‘ desired, a
`path classifier‘ to discriminate between the good clusters could he created and then used to classity
`the straggglers. This was not done in the current irnplementation since there was never a signiiicant
`numher of stragglers.
`Once the path classes in each gesture cl ass have been identified using the clustering technique, a
`path classifier is trained which can rlistinguish hetween every path
`of every gesture class. ote
`that it is possible for a path class to he formed from two or more paths from each example oi’ a
`gesture class, it" the cluster analysis ii1(l.liZ'.al€(l
`the two paths were similar. If analogy techniques were
`used to separate such a class into multiple “one path per exairiple” classes. the resulting classifier
`would ainhiguously classify such paths.
`ln any case. ariihignities are still possible since ditfereiit
`gesture cl may have similar gesture paths. As in Section 5.4. the aiiihigtiities are removed lrom
`classifier by eornhining ainhiguous classes into a single class.
`"Each (new unambiguous) class
`which is recogni:I.ed hy the path classifier is riumheretl so
`to establish a canonical order for sorting
`path class sequences (luring training and recognition.
`
`5.7.4 Creating the decision tree
`
`constructed.
`After the sin gle-path anrl glohal classifiers have heen trained, the decision tree mast
`As
`‘ore. in the class phase, for each multi- path gesture class, the (now uiiaiiibiguoii classes of
`eacli constituent path are enumerated. Since two paths in a single gesture class may be similar.
`this enumeration ot‘ classes may list a single class more than once, and thus may he considered a
`
`Page 1259 of 1714
`
`

`
`5 8 DISCUSSION
`
`is sequenced into canonical order, the global feature class appentlcrl. and
`1’)’t‘dlli The list of
`the resulting seqtienee is used to add the nttilti-path class to the decision tree. As before, a eonliiet,
`due to the tact that two =;lit‘.l'et'ent. gesture classes have the same ntuiti set ol"path classes, is tatai.
`Next comes the example phase. The paths of each exarnple gesture are elztssltietl hy the single
`path classifier, and the resulting scqucr :0 (in canonical ortler with the global feature class appciitletl)
`is
`to add the elass of the example to the decision tree. Usually no work needs to he done,
`the same sequence has airearly heen used to add this class (usually in the class
`However. if
`one of the paths in the sequence has been niiselassified, adding it to the decision tree can improve
`iecognition. since this tniselassitieatioit may occur again
`future. Conliiets here are not fatal,
`but are simply ignored on the assumption that the sequences added in the class phase are more
`intpottant than those added. in the t3>;Bl’l1plt: phase.
`
`5.8 Bisetissioti
`
`the
`Two rnulti—path gesture recognition algorithms have been tlest:iiht:tl, which are refertetl to
`“path sorting" and the “path clustering" trtethotls.
`in situations where there is no tincettainty as to
`the path index irtfortnation (eg. a Dataiilo ve, since the sensors are attached to the harni) then the
`path~sortin method
`certainly superior: However, with input devices such
`the Sensor Prairie.
`the path sottittg has to he done lteuristically, which increases the lilcelihootl of recognition error.
`The p-ath—elustering method avoids path sorting; and its associated errors. Howeve r, other sources
`of niisclassification are ll’l[.l‘0(iU¢.T£’)4;lt One singlepath elassltier
`to discrirninate between all the
`path classes in the system, so will have to recognize a large number of classes. Since the error rate
`of a elassitler increases with the nntrther of classes}, the path classifier in a path~clnstering algoritltni
`will never perforrn as well as those in a path~sorting algorithm. A
`source of error is in the
`clustering itselt"; errors there cause errors in the classifier‘ trainin data, whi<;th cause the performance
`of the path classifier to degrade. One V 'ay around this is to cluster the paths by hand rather than
`by having a computer perform it automatically.
`needed to he done with some
`lrotn the Sensor Frame, which, because oi glitches in the traeiting hanlware, eoulrl not be clustered
`reli ahl y.
`In practice, the patl:-sorting rnethotl always pertorttted better The poor perforrnance of the
`path-clustering method was generally one to
`noisy Sensor Fratrte data. it is however dilficult to
`reach a general conclusion, as all the gesture sets upon which the ntethods were tested were designed
`with the path sorting algorithm in mind.
`it it easy to design a set of gestures that would perform
`poorly using sorted paths. One possibility for future worlt is to have a parameterizahle algorithm
`for sorting paths, and choose the parameters based on the gesture set.
`The Sensor l31‘£t1’l’tt) itself was
`significant source or" classification errors. Sornetirnes, the knuckles
`of lingers curletil so
`not to he sensed would inadvertently hr talc the sensing; plane, causing extra
`paths in the gesture (which would typica‘tl.y then he rejected). Also, three
`in the sensing
`plane can easily occlude each other with respect to the sensors. matting it difficult for the Sensor
`Frame to determine each tin§._zer’s location. The Sensor Frame harclware usually l<t‘tt3W from recent
`history that there were irttleeti three lingers present, and (lid its best to estlinate the positions ii:-l" each.
`lloweveri the resulting data often liaul glitches that tlegradetl classitlcatiori. srnnetirnes hy cunfnsirtg
`
`Page 1260 of 1714
`
`

`
`94
`
`:‘:HL-4iPI]E71i’
`
`it/1ULJi"»-ZZIXIH YURE RECOGi"t»HYO1‘\/
`
`It is likely that additional preproeessing of the paths before recognition
`tracking aigorithni.
`would iriiprove a<;euraeyi Aiso. the Sensor Eratiie jtseif is stiii under devetepiheiit, and it
`possihie
`that such glitches 5». it} he eiiriiinated hy the hardware in the. i'utu:re.
`Anot