Note: Descriptions are shown in the official language in which they were submitted.
CA 02507290 2005-05-13
13-05-05 ~ 04:4TPM FROhI--GOwIING +613-563-6869 T-142 P.05/~T F-512
Svsterr6,and ~,~gihad of Gerst~l,re F ~o l~eca~nition
FIELD OF THE INVENTION
The invention relates generally to a system and method of gesture fdature
recogttirion.
>3ACKGROUND OF THE IN'VLN'TION
There arc systems for automatically recogni,zitig handwrittetl synbals and
characters using a pen device or similar method of input. In order to
recognize
handwritten input, composed of characiexs and symbols, it is riot stt~'leieai
tp simply
identify general characters and cymbals. The precise location of certain
feai~ures of these
of these characters and sYmbol$ also should be identified.
For example, to recognize a string oftext, the baseline of each character
should be
identif-xed. '> his is important, for example, to distinguish between the
letter 'fig' aRCi the
number '9'.
Another example of the need to identify the precise locatioa of certai~r
features
occurs in recognizing ranathematical formulae. Far example, in addition to
r~co~aizing a
(square) root symt~ol, one also has to identify the region that is "inside"
the rpot symbol
attd differentiate it fxom the region that is "outside" the root symbol. The
"inside" region
will contain the argume~lt of the root, whereas the "outside" region rnay
contain the order
(square, cubic, etc.) of the root,
One current way that the problem formulated above is presently addressed is to
have feature identification code explicitly inserted for each character or
symbol w be
recagnixed. This interferes with training of the system, and in parncular,
with
2s extensibility with additional eltaractcrs and symbols. For Example, is
addition to
teaching the system to recognize a new character or symbol, explicitly
coded',,instructious
have to be provided to the system for each feature (baseline, etc.) that is
reco~ized
within that new character or symbol.
Another method that is presently being used identifies the handwritten
characters
and symbols with a stored model symbol. Since the feature locations are
knortwn in the
model symbol, the feature location in the handwritten symbol can be
approximated by
scaling the location in the model to the size of the handwritten symbol. The
fact that this
method can only approximate the location of such features and may
accasion~llly be
-1-
CA 02507290 2005-05-13
13-05-05~ 04:46PM FROiMG09ItING +613-563-0869 T-142 P.06/2T F-512
incorrect, interferes with the recognition process of the overaEl input and
leads to incorrect
recognition results if these results are (partially) based on the supposed
location of these
features. For example, a '9' may be recognized as a 'g' if the baseline is not
accurately
identified.
A system and method for more reliably finding the location for features in
handwritten symbols is desired.
SUMMARY of THE INVENTioN
In accordance with an embodiment of the invention, there is provided a gesture
14 feature recognition system. The gesture feature recognition system
comprises ats
inpuuoutput component for reeor~ding pen strokes and for displaying them as
suokes on a
display device, a repository for storing gesture recognition data and a
recoguizer
component for analyzing the strokes using the gesture recognidon data.
In accordance with another embodiment of the present invention., there is
provided
15 a method of gesture feature recognition. The method comtprises the steps of
receiving
input data that represents the stroke sequence of handwritten characters and
symbols,
comparing the input data to a predefined symbol set stored in a repository,
identifying
characters and symbols present in the input data, and identifyins the location
of relevant
features of the characters and symbols.
ERIEF DESCRIPTIONS dF THE DRAWINGS
.A,n embodiment of the invention will now be described by way of example only
with reference to the following drawings in which:
Figure 1 shows a gesture feature recognition system, in accordance with an
embodiment of the present invention;
Figure 2 show in a flowchart a tnethad of gesture feature recognition, in
accordance with an embodiment of the gesture feature recognition system;
Figure 3 shows another example of a gesture feature recognition system;
Figure 4 shows in a flowchart another method of gesture feature recognition,
in
accordance with an embodiment of the gesture feature recognition systctn;
Figures 5A and 58 depict examples of primitives, in accordance with an
embodiment of the gesture feature recognition system;
_z_
CA 02507290 2005-05-13
13-05-05 04:48PM FROM-GOWLING +613-563-8868 T-142 P.OT/2t F-51E
Figure 6 shows in a flowchart a method of decomposing ar segmenting stroke and
timing information of primitives, in accordance with an embodiment of the
gesture
feature recognition system;
Figure 7 shows in a flowchart an example of a method of calculating a partial
solution, in accordance with an embodiment of the gesture feature recognition
system;
Figure 8 shows the configuration at each step in the loop of steps (fit) to
(70) of
the method described in Figure 7;
Figure 9 shows iti a flowchart an cxatnple of a method of comparing a sequence
of
segmented primitives with a predefined sequence of primitives, in accordance
with an
embodiment of the gesture feature recognition system;
Figure 10 shawl iu a flowchart an example of a method of performing a detailed
uiatch against a database entry with high probability of match, is accordance
with an
embodiment of the gesture feature recognition system;
Figure 1 I shows in a flowchart and example of a method of analyzing a
correlation of features between an observation and base model to predict which
shape is
the baseline, fn accordance with an embodiment of the gesture feature
recognition system;
Figure 12 shows in a flowchart an example of a method of approximating a
baseline location of an observed sequence by observing the bounds of the
corresponding
baseline shape, in accordance with an embodiment of the gesture feature
recognition
system; and
Figure 13 shows in a flowchart an example of a method at dynamic matching, in
accordance with an embodiment of the gesture feature t~ecognition system.
DETAILED DESCRIPTION OF TfiB PItE>;13RRED EMBODIMENTS
Figure 1 shows a gesture feature recognition system 10, in accordance with au
embodiment of the present invention. The gesture feature recognition system 10
comprises an ingut/output compnneat 12 for retarding pen strokes and for
displaying
them as strokes on a display device, a repository 14 for storing gesture
recognition data,
and a recognizcr component 16 fat analyzing the strokes using the gesture
recognition
data. The inputloutput component 12 includes a display panel that allows a
user to input
pen strokes using a stylus pen, mouse, or otter pointing device. Other
components may
be added to the gesture fbatttre recognition system 10.
3 ..
CA 02507290 2005-05-13
13-05-D5 04:43PM fROI~GOwIiNG +613-563-9868 T-142 P.08/2T F-512
Figtue 2 show in a flowchart a method of gesture feature recogaitian (20), in
.. accordance with an eznbodimeht of the gesture feature recognition system
10. The
method begs with the gesture feature recognition systeut 10 receiving input
data (22)
chat represents the stroke sequence of handwritten characters and symbols. The
input data
is compared to a predefined symbol net (24) stored in the repository 14. This
comparison
step (24) identifies characters and sytnbals present is the input data. For
tech such
identified character or symbol, the gesture feature recognition system 10
identifies the
location of relevant features {26). Qnce the location of relevant features is
identified for
each identi$ed character or symbol (2~, the method (2o) is done {2>3). Qther
steps may
1 o be added to thG method (20), including displaying digital characters or
symbols that
correspond to the ident~ed characters or symbols, and outlining the identified
relevant
features in the display.
Tire predefined symbol set is produced during the training phase of the
recognition
system. For tech symbol that needs to be recognized one or more hand-drawn
instances
1 S of that sytubol are produced and stored in the repository.
Figure 3 shows another example of a gesture feature recognition system I0. In
this example, tl~ iuputloutpux component 12 is shown: twice: once showing
strokes
received as input data 12a, and once showing the digital display of the input
data 12b.
Preferably, there is one ixiputloutput device 12 where input data is received
and than
20 displayed as digital data, Alternatively, there may be separate devices for
the input of the
input data arad the output of the digital data. In the example provided in
Figure 3, the
handwritten symbols for '9', 'g' and the cubic root of gamma are correctly
identified,
along with the location of relevant features. The baselines 32 of '9' and 'g'
arc marked
with a dotted line and the "it~.side" 39 and "outside" 36 regions of the root
syuibol are
ZS marked with a dotted rectangle. A baseline on a text character refers to
the vertical
position on the character that would be aligned to the horizontal baseline of
the text when
drawing the W aracter on a line of text.
1~igure 4 shows in a flowchart another method of gesture fcatuxe recognition
(4Q),
in accordance with an embodiment nfthe gesture feature recognition system 10.
The
30 method begins with decomposing stroke and timing informatipn {42) gathered
by an input
into a sequence 4f"primitives". The set of such "priuiitives" may include
lines, arcs,
corners and intersections. For example, the stroke sequence for the character
'q' may
result is the following sequence of two "primitives":
-4-
CA 02507290 2005-05-13
13-05-05 04:49PM FROM-GOWLING +fit3-563-9869 T-142 P.09/Zt F-612
~ An arc, drawn counter-clockwise, starting at an angle of 3 S degrees and
extending
to an angle of 350 degCeos (see Figure SA); and
A straight, verrincal line, drawn downwards, connected to the izrst primitive
at the
top erid (see Figure 5B}.
S Next, this sequence of "primitives" is compatzd to a set of pr~edefned
sequences of .
"primitives" (44}. 'rhe goal of this comparison step (~4) is to identify the
predofined
sequence that is "closest" to the original one. The set of prcde~ned
primitives includes
feature location information within each sequence of gritnitives. Far example,
a
predefined sequence of primitives representing the character q may be composed
of the
l0 following four primitives:
~ Aa arc, drawn counter-clockwise
A "baseline bounding box marker", indicating that the baseline of the
character is
at the Lowest eoordinaie of all strokes that appear prior to this primitive.
A vertical lice, dr$wa downwards
15 ~ A horizontal line, intersecting the veriieal one
Once a set of sequences corresponding to the primitives is identified (44) the
method is
done (4b). Other steps may be added to the method (40), including displaying
the
identified set of sequences in an output or inputloutput device 12.
Before a recognition is initiated, the set of predefined segueuces of
primitives is
20 created. This is achieved by gathering stroke data for each symbol to be
recognized and
then using the process described above w decompose this stroke data into
primitives.
'These sequences of primitives are stored in a repository such that they can
be reused for
multiple recognitions. Feature location ittfarmation is manually inserted into
each
sequence of primitives, if required. 'typically such a repository would be
created during
25 the "training" phase of building a recognition system.
Figure b shows in a flowchart a method of decomposing or segmenting soroke and
taming information of primitives (4Z}, in accordance with an embodiment of the
gesture
feature recognition system 1 D. The method begizts with receiving a sequence
of packets
(S2). rnput is a discrete sequence of packets representing stroke data. Next,
a packet is
30 selected (5~1). A partial solution is determined (Sb) based upon each
packet selected to
this point. The partial solution may be determined using a dynamic
segmentation
method. partial solutions are calculated starting from the last packet to the
first, iu
-S
CA 02507290 2005-05-13
13-05-05 04:46P11 FR0~1-GOWLING +613-563-986!3 T-142 P.10/Zt F-51Z
reverse order. The final solution corresponds to the partial solution begnning
at the first
packet. If all packets have been processed (58) then a sequence of shapes
which
correspond to the best ftt representation of the input packets is outputted
(59). Otherwise,
the next packet is selected (54}.
Figure 7 shows in a tlowcharl an example of a method of calculatir~ a partial
solution, in accordance with au embodiraent of the gesture feature recognition
system 10.
The method begins wilt calculating a "best" shape for segment l ..i (62),
where i denotes
the level of the packet aelection. Next, the cumulative probability using the
"bast" shape
I ..i and best arrangement for segment i+i..n is calculated (64), where n
denotes the
number of points. A stroke consists of n goirits in two-dizztensional space,
where n is au
integrr granter than zero. The xtroke itself is uniquely represented by an
ordered
sequence of such points. Since the sequence of points is ordered, we can label
each point
with a number from 1 to n. 'The variable i denotes the nu~er of a point in the
stroke. ~t
each iteration of the method, the points that lie in the range of I to i are
considered. The
I5 variable i is incremented at each iteration. "Paints" denote the individual
two-
dimensioual points, or pairs of numbers of the form (x ,y}, which form the
stroke. In the
analysis of stroke shapes, there are certain shape primitives. These
primitives include
(but may not be limited to) Lines, curves, dais, and loops.
Far example, suppose t shape primitives are defined and denoted S 1 to St,
where t
is as integer greater than A. For each shape Sj, a distance fuactian d~Sj]
exists. The
function d[Sj] takes as an argument a scguence of points {p1, ..., pq}, and
returns a real
number greater than or equal to zero. This distance function is called a
metric. h can be
considered a measure of sirailarity between the shape Sj aacl the sequence of
points tpl,
..., pq}. "Best" or "optimal" arrangement refers to the choice of shape S
(from the set of
2S shapes {SI, ..., St}} such that the similarity reported by d[Sj({p1, ...,
pq,~) is greatest.
For instance, the distance function for the "lira" shape, when applied to a
stroke where all
the points are collinear, would report s greater amount of similarity than the
distance
functions for the ''curve" shape, "dot" shape, or "loop" shape when applied to
the same
suoke. If the probability calculated in step (b4) is greater than the best
arranganeat so
far, then the best arrangement is set to the current arrangement (66).
Otherwise (64), i is
incremented by one (68). If i is greater than the cumber of points (7D), then
the current
best arrangement is antcrcd in a table f7~). Qtherwise (70), the best shape
for segment
I..i is calculated (b2).
-6-
CA 02507290 2005-05-13
13-05-05 04:50PM FROi4-GOWLING +613-563-9869 T-14Z P.111tT F-512
The table is a list where the entry at index i consists of the best continuous
shape
found starring ac index i, aad the span of that shape. The next shape starts
at the index
following the spark. The list of shapes is formed in this fashion. Figure 8
shawl the
configuration at each step in the loop of steps (b2) to (70) of the method
described in
Figure ?.
By matching corresponding primitives iu the original sequence and the sequence
that was identiixed as the "closest" in the predefined set, the position in
the original
sequence to insert aay feanue location markers is identified. It is desirable
to insert the
markers in floe original sequence which best correspond to the position of the
markers in
the target sequence. The target seqaencc is the model that is used as a
reference in the
systctn. It is stared in memory, possibly as an crluy in a database or
repository. The
location of all the markers in all target models are known with certainty, The
original is
an unknown model that is to be matched to an existing model is the database.
At this
paint is the method, it is determined that the target sequence matches tha
otigizial with a
1 S measure of certainty above some predefuted threshold. The lacatio~ at
which a particular
marker should be inserted in the original is estuxtatad. 'llie estimate is
based on the
surrounding features and position of the marker in the target.
In the example of Figure 8, arc in the original sequance is matched with the
arc in
the target sequence and tha vertical line in the original seguence is matched
with the
vertical line in the target sequence. The extra horizontal line in the target
sequence is
identified as missing from the original sequence. Since the baseline marker
appears in
between the arc primitive and the vertical line primitive, the baseline marker
is inserted
between the arc primitive and the vertical line primitive in the original
Sequence. The
original sequence of primitives, augmented with the baseline marker now looks
as
2S follows:
~ An arc, drawn counter-clockwise, starting at an angle of 15 degrees and
extending
to an angle of 350 degrees
A "baseline bounding box marker", indicating that the baseline of the
character is
at the lowest coordinate of alI strokes that appear prior to this primitive.
~ A straight, vertical line, drawn downwards, connected to the fast primitive
at the
top.end.
The location of all features for which information was present in the target
sequence is
now identified. In the example of figure 8, the location of the baseline is
located by
CA 02507290 2005-05-13
13-05-05 04:50PM FROi~GOWLING +613-563-9669 T-142 P.12/2T F-612
computing the lowest coordinate that was present in the original stmlce
information for
primitives that occur prior to the baseline marker. That is, the lowest
coordinate of the
stroke information that was identified as the counter-clockwise arc.
Figure q shows in a flowchart an example of a method of coruparing a sequence
of
S scented primitives with a predef ncd sequence of primitives {44), in
accordance with
an embodiment of the gesture feature recognition system. The method begins
with a
database lookup mechanism performing a detailed match against a database entry
with
high probability of match (82). This step is illustrated in Figure 10, using
an observed
shape sequence of primitives 92 for the number '9'. Next, a correlation of
features
between the observation gad base model is aualyxed to predict which shape'is
the t~aseline
(84). This step is illustrated ire Figure 11. A base model with a known
baseline location
9A. is shown atortg with primitives 92. An observed shapo sequence with an
inferred
baseline location from dynamic matching 96 is also shown in )~ figure 11. Tile
primitives
92 are matched. Once the eorrclation analysis (84) is caznplete, a basclinG
location of the
1 S observed sequence is approximated by observing the bounds of the
corresponding
baseline shape (86). This step is shown in Figure 12, whore a baseline is
calculated from
the bounds of packets corresponding to a baseline shape.
If the predefined set of sequences contains sequences for all characters and
symbols in the alphabet that are desired to be recognized, the characters and
symbols
themselves are identified as a side effect of locating their features.
However, a separate
recognizer can also be used to identify the characters and symbols, which
enables a mode
of only supplying the subset of predefined sequences to the feature locator,
that
correspond to the character or symbol that was recognized.
When comparing two sequences of primitive, how "close" these two sequences
are is detea~ined as determining the sequence from a collection of sequences,
which is
"closest" to the target sequence is a critical step in the method (44), as
seen in Figures 10
to 12.
First, how to characterize tire "closeness" of two individual primitives is
defused.
A numeric measure between 0.0 and 1.0 is assigned, where 0.0 means that the
primitives
are identical, I mearss that the primitives are fully distinct and a vatue
between 0.0 arsd
1.0 indicates a progressively more distant resemblance between the two
primitives. If the
primitives are not of the same type (e.g., they are not both lines or not both
arcs), a
measure of 1.0 is assigned and comparison is stopped. If the pritttitavas are
of the same
-g.
CA 02507290 2005-05-13
13-05-05 04:50PM FROWI-GOWLING +613-563-6860 T-142 P.13/~T F-512
type, detailed properties of the two primitives are analyzed, which depend on
the type of
the primitive. For example, for a line, these properties would include the
length of the
line and the angle of the line. For an arc, the properties would include the
arc length, the
starting eagle and the exuding angle. The closer the numeric values for these
properties
are, the smaller~ti~-vrdue for tile "closeness'- that gets assigned.
Next, how to characterize "closeness" hetweea two sequences of primitives is
defined. The method begins with a value of O.p for the tentative "closeness"
of these two
sequcricrs. A "current position" for both scequences is defined and
iniiializcd at the
beginning of both sequences. "fhe "elosextess" of the two primitives at the
"current
position" of both sequences is evaluated using the method (44) above. 1'f this
value is
above a cextain threshold, say 0.9, the "closeness" of the next element in the
first
sequence is computed with the current element iu the second sequence as web as
the
"closeness" of the next element in the second sequence with the current
element iu the
first sequence. If the minimum value of these two computations is above the
threshold
(the threshold can, for example, have a value of 0.9), a peuahy value is
added, say 0.1, to
the overall "closeness" value far the two sequences, increment the "cuz~t
position" far
both sequences and iterate as above until one afthe sequences is exhausted. If
there are
primitives Ieft is the other sequence, a penalty of 0.1 is added, multiplied
with the number
of lei over sequences to the overall "closeness" value and return the latter.
If the
minimum value of the two aomputatior~ above is below the threshold (0.9~, a
penalty for
a "raissing primitive" is added, say 0.05 w the pverall "closeness" value,
irurement the
"curzeat position" far the sequenco where the next primitive more closely
matched the
primitive at the ''current gosition" of the other sequence and iterate as
above.
At the end of this process a "closeness" measure is computed which indicates
how
similar the two sequences of primitives are. tJther measures of "closeness"
can be used
as long as they have the property that low values are assigned far two
sequences of
primitives corresponding to similar pen strokes and high values arc assigned
for two
sequences corresponding to strokes that axe different. Alternate techniques
can be used to
compare two sequences of primitives, ir~.stead of the approach described
above. Far
example, standaxd techniques commonly used in the held of biainfarmatics can
be
applied.
-9_
CA 02507290 2005-05-13
13-05-05 04:51PM FR0IkGOWLING +613-563-9669 T-14Z P.14/2t F-51?
A method of dynamic matching can be used as an alternative to the process
above
for the step (A~4) of finding "close" matches of setluences of primitives in a
database.
Advantageously, the method of dynamic matching has the following
characteristics:
1. To be able w search for inexact matches within a b-tree data structure
efficiently,
and associate a measure of "closeness" with each potential match.
2. To perform this search with little auxiliary storage. .
3. To be able to account for extra or missing shapes in the sequence when
looking
for candidates in the database.
4. To accurately score the "ctascness" of each match between observation
sequence
and database record.
R description of the b-tree is provided, the data structure used for the
database. A
b-tree is clan known as a mutti-wiry search tree. It is useflal for staring a
database of
words over an alphabet. Far example, a dictionary of English words can be
stored as a b-
tree where the alphabet corresponds to the Roman alphabet. A, series of
telephone
numbers can also be stored in a b-tree should the need arise to index and lack
up entries
in a database by telephone number. In this case, the alphabet would correspond
to digits
in the phone number. Alphabets can also consist of abstract symbols; iu the
feature
gesture recognition system 10, alphabets arc slxake shapes that are recognized
by the
tokonization process. An alphabet in the feature gesture recognition system 10
comprises
a fuute number of letters.
rt is similar in concept to a linked liar, with multiple "next" nodes
branching from
a single node. Each "next" node corresponds to a letter in the alphabet.
Suppose that we
are at a node n which is k levels deep from the mot, Then n corresponds to
the.pFeftx of
some word in the tree A~4z...A~ whose letters correspond to the path of "next"
nodes
required to reach n from the root. Theze exists a painter at the "next" node
corresponding
to letter X in the alphabet, if and only if there exists a word with prefix
A,Aa.. .,~"Jf in the
tree. t7therwise, the "next" node cprrespanding to X at n is empty (null).
An advantage of such a data structure is that it can be searched efficiently
far '
exact tnatchrs while maintaining storage efficiency. In addition, it admits an
efFcient
~0 method to search for inexact matches against an input sequence. The latter
method is not
an exhaustive search, but is able to produce correct matches with high da~ee
of
probability. It is in this method th&t baseline extrapolation through
correspondence of
shapes in the sequence is performed.
-10-
CA 02507290 2005-05-13
13-05-05 ~ 04:51PM FROI~GOWLING +613-563-9868 T-142 P.15/ZT F-512
The impetus driving the development of a method of dynamic matching is the
desire to perform comparisons between two data sets when the data are
different and a
measure of similarity is reguired. The dynamic matching approach is able to
determine
the optimal set of consrr&ints cruder which the similarity measure is at its
greatest, while
running in polynomial time,
The method of dynamic matching described above employs an intermediate data
structtue, a priority queue, to maintain a record of the best full and partial
matches found
sa far at arty point in the method. The method of recording critical feature
correspondence between base alai observation also uses this data structure.
I O When comparing two sequences, it is traditional to consider "current"
characters
in both sequences. At each iteration fn the method of dynamic matching,
different
eboices for the "current" characters are used and the partial match score is
adjusted.
There arc three choices for score adjustment. Suppose that the current
characters in the
two sequences are at indices f and j, respectively.
1. Take the score from comparing the two current characters and z~pply it to
the
cumulative bast score froxtt the substring that was found by comparing until
indices i -1 and, j -1 in the two lists.
2. Skip the character at index i in the first list, and apply a constant "skip
character in
first list" penalty to the measurement to the score from the substrin8 formed
by
indices i -1 and,j.
3. Skip the character at index J in the second list, and apply a constant
"skip
character in second list" penalty to the measurement to the score from the
substriag Formed by indices i ands -1.
The choice with the greatest score, or meas~u~ement of similarity, is choxen
ac the paxtiaL- .---.--
solution for the sub-problem at indices i and j.
The coruparison starts with bath indices at 1 (the base cas~, where the
comparison
is done on two strings of length 1), and iterates by alternately incrementing
each index
until the length of both strings is exhausted. 'The final result is a score
computed at the
fatal character of both strings.
3o The method of dynamic matching as described may be used over two arrays,
across which can be traversed by index. To adapt this to the b-tree, note that
several
cases that arise during the iteration ofthe method of dynamic matching that
correspond to
degenerate cases which would almost never be applicable as a final solution.
These
-11-
CA 02507290 2005-05-13
13-05-05 04:52Pw1 FROM-GDyILING +613-663-8869 T-142 P.16/t!t F-51.2
boundary conditions include the case where the eexrent symbols under
consideration
differ by a sufficient number of indices that the penalty for skipping so many
symbols
makes the match unviablc. In the majority of cases, we such conditions are
ignored
without affecting the correctness ofthe matching.
It is the above fact that allows the method to be used over a b-tree. Instead
of
indices, pointers are used to nodes in the tree to track our progress through
the fist that
exists within the b-tree. An index i is associated with the position of each
"current"
symbol in the observation seaucnce with the pointer and maintain a score In
the same way
as described in the method (120).
1 o This approach has the advantage that it can be employed with a priority
queue to
perform an optimirxd R * search of the database. This means that an extension
of the
dynamic matching algorithm, which is designed to comps only two lists at once,
can be
used to compare multiple lists and search the database. The disadvantage is
that by
performitt$ a search in this meaner, an exhaustive search is no longer
required. Thus by
1 S adopting this method, the zesults might miss some potential rriatches that
would otherwise
be found by an exhaustive search.
For the purposes of ending corresponding shapes for feaxure extraction, an
extra
ealculatian is performed if choice 1 was taken is the above method. If there
is a baseline
marker at the shape in the base sequence, then occurrence is recorded to
indicate which
20 index in the observed sequence corresponds to the baseline shape. This
information is
recorded in the partial match. if the partial match leads to a full solution
that is returned
as a candidate, then this information is propagated to the final solution. The
method in ,
which the information is stoted and propagated is specific to the
imglementadon, and can
be performed with a custom data suucture.
25 'The system and method described above identify the precise location of
features
in online recognition of handwritten characters arid syiubols, i.e., in the
presence of stroke
and timing information.
Advantageously, the approach enables the system to identify the location of
features in handwritten characters and symbols with high precision, and
without
30 sacri~ciug a straightforward training phase or extensibility with
additional characters and
symbols.
'fhe systems and methods according to the present invention cnay be
implemented
by any hardware, software or a combinatipn of hardware and software having the
shave
-12-
CA 02507290 2005-05-13
13-05-05 04:52PM FROIA-OOWLING +613-563-9860 T-14t P.iTl2T F-5t2
described functions. The software code, either in its entirety or a part
thereof, may be
stored in a computer readablo memory. Furkher, a coraputer data signet
representing the
software code which may be embedded in a carrier wave may be uansmitted via a
comraunication network. Such a computer readable memory and a computer data
sigtLal
S arc alt within the scope of the present iuveniion, as well as the hardware,
software and
the combination thereof.
While particular embodiments of the present invention have been shown and
described, changes and modifxcations may be made to such embodiments without
departing from the true scope of the iuventioa.
_13-
