PowerPoint PresentationSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18On-Line Handwriting Recognition•Transducer device (digitizer)•Input: sequence of point coordinates with pen-down/up signals from the digitizer•Stroke: sequence of points from pen-down to pen-up signals•Word: sequence of one or more strokes.System OverviewInputPre-processing (high curvature points)SegmentationRecognition EngineDictionaryCharacter RecognizerContext ModelsWord CandidatesSegmentation Hypotheses•High-curvature points and segmentation points:Character Recognition I•Fisher Discriminant Analysis (FDA): improves over PCA (Principal Component Analysis).Original space Projection spaceLinearprojec-tion p=WTx•Training set: 1040 lowercase letters, Test set: 520 lowercase letters•Test results: 91.5% correctFisher Discriminant Analysis•Between-class scatter matrix–C: number of classes–Ni: number of data vectors in class ii: mean vector of class i and : mean vector•Within-class scatter matrix–vji: j-th data vector of class i.CiiiiBN1T)()( μμμμ  CiNjiijiijWi1 1T)()( μvμvGiven a projection matrix W (of size n by m) and its linear transformation , the between-class scatter in the projection space isvWpT WΦWWμμμμWWμμμμWWμWμμWμWμWμWμWμWμμμμΨBCiiiiCiiiiCiiiiCiiiiCiiiiBNNNNNT1TT1TTT1TTTT1TTTTT1T)()()()()()()()()''()''(Similarly WΦWΨWWT•Optimization formulation of the fisher projection solution: (B, W are scatter matrices in projection space)Fisher Discriminant Analysis (cont.)WWWWWWWwBwBTToptmaxargmaxargFDA (continued)•Construction of the Fisher projection matrix:–Compute the n eigenvalues and eigenvectors of the generalized eigenvalue problem:–Retain the m eigenvectors having the largest eigenvalues. They form the columns of the target projection matrix..ySySwBCharacter Recognition Results•Training set: 1040 lowercase letters•Test set: 520 lowercase letters•Test results:FCM ECV Recognition rate 91.5% Avg. candidate set size 13.6Challenge I•The problem of the previous approach is: non-characters are classified as characters. When applied to cursive words it creates several/too many non-sense word hypothesis by extracting characters where they don’t seem to exist.•More generally, one wants to be able to generate shapes and their deformations.Challenge II•How to extract reliable local geometric features of images (corners, contour tangents, contour curvature, …) ?•How to group them ? •Large size data base to match one input, how to do it fast ?•Hierarchical clustering of the database, possibly over a tree structure (dandograms ?) or possibly over some general graph, may be the way. How to do it ? Which criteria to cluster ? Which methods to use it ?Recognition Engine•Integrates all available information, generates and grows the word-level hypotheses.•Most general form: graph and its search.•Hypothesis Propagation NetworkHypothesis Propagation NetworkH (t, m)Class m's legal predecessors"a" "b” "z""y"List length123TimeTtLook-back window rangemRecognition of 85% on 100 words (not good)Challenge III•How to search more efficiently in this network and more generally on Bayesian networks ?Visual Bigram Models (VBM)•Some characters can be very ambiguous when isolated: “9” and “g”; “e” and “l”; “o” and “0”; etc, but more obvious when put in a context.Character heightsRelative height ratio and positioning“go”“90”VBM: Parametersh1h2htop1top2bot1bot2• Height Diff. Ratio:HDR = (h1- h2) / h• Top Diff. Ratio:TDR = (top1- top2) / h• Bottom Diff. Ratio:BDR = (bot1- bot2) / hVBM: Ascendancy CategoriesCategory MembersAscender(A)b, d, f, h, k, l, tDescender(D)f, g, j, p, q, y, zNone (N)a, c, e, i, m, n, o, r, s, u, v, w, x•Total 9 visual bigram categories (instead of 26x26=676).VBM: Test ResultsUsing VBM Yes No Recognition rate 93% 85% Rank-1 4 8 Rank-2 1 2 Rank-3 1 2 Rank-4 1