throbber
iii;-4;P’I]E71{’
`
`A/1UL’1"}"»-BZXIH YURE RECOG]‘v1’I1’O1‘\/
`
`'1th gesture classes
`
`R
`
`path 0 C., {sSi1,..i€1_
`
`Mu1ti~path
`
`. m...,
`.-D:

`[.'ef.1...\.O;\
`.\..\.€€
`
`{chosen gesture)
`
`»US
`
`\.-/
`4
`Fiazum 53: (‘}as.<ifVir1g‘nmltipaih gestures
`At the top are examples :3-ffo Z11‘ tWcr—pa ti:
`IUIES zexpe-z:€evj' by this (Ia ssfff-Sf, and 5: t the Ie1‘}.‘a I'Wo—;:-a ff) gesfzzfe
`ta be ciassifi}:-d. Path 0 ofL"11'5 gesture is classified ('22:!
`path U cIa5si'.’]5erj' as pa 612 D0, and pa fl] 1’ as (H.
`Lrhese pa H7 CIa5sif<:a1;":L'
`. 1'5 used fa .€'z'aVe1':;e
`the 4'ecisi0n tree, as .9324) ‘W3’?
`the a'z)tfe{2'1i12e.S. H28 1;"ee node
`/'ear,‘}1eau’ is at1:bigI1z2u.s (1)54 ving I,‘]1i1d1'<e‘t1 Q arm’ Si} Si} g,’<Jbaifea{I1z1%s 51525‘ 11.580’ 10 /’r:.s<,=:'s~&' If/5 b(‘I'.S(,‘I'€J[.7:3‘El(,'_fy‘,. am)’
`the gesture is rer;0gz21;?ee;" as class 53.
`
`Page 1251 of 1714
`
`

`
`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 glitche

This document is available on Docket Alarm but you must sign up to view it.


Or .

Accessing this document will incur an additional charge of $.

After purchase, you can access this document again without charge.

Accept $ Charge
throbber

Still Working On It

This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.

Give it another minute or two to complete, and then try the refresh button.

throbber

A few More Minutes ... Still Working

It can take up to 5 minutes for us to download a document if the court servers are running slowly.

Thank you for your continued patience.

This document could not be displayed.

We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.

Your account does not support viewing this document.

You need a Paid Account to view this document. Click here to change your account type.

Your account does not support viewing this document.

Set your membership status to view this document.

With a Docket Alarm membership, you'll get a whole lot more, including:

  • Up-to-date information for this case.
  • Email alerts whenever there is an update.
  • Full text search for other cases.
  • Get email alerts whenever a new case matches your search.

Become a Member

One Moment Please

The filing “” is large (MB) and is being downloaded.

Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.

Your document is on its way!

If you do not receive the document in five minutes, contact support at support@docketalarm.com.

Sealed Document

We are unable to display this document, it may be under a court ordered seal.

If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.


Access Government Site

We are redirecting you
to a mobile optimized page.





Document Unreadable or Corrupt

Refresh this Document
Go to the Docket

We are unable to display this document.

Refresh this Document
Go to the Docket