US5029223A — Constraint driven-on line recognition of handwrit…

Claim 1

Independent Claim 136 words

A method for identifying a valid symbol or a string of valid symbols from a sequence of handwritten strokes comprising the steps of: generating, in response to one or more handwritten strokes, a plurality of stroke labels each having an associated score; and processing the plurality of stroke labels to identify stroke labels indicative of a valid symbol or portion of a valid symbol, the step of processing including the steps of storing the stroke labels within a data structure by order of score, the data structure storing all or a portion of all paths through a search space defined by the plurality of stroke labels; and reading a path from the data structure, extending the path with possible successor paths, and merging the extended paths back into the data structure as a function of score.

Claim 2

Independent Claim 136 words

A method for identifying a valid symbol or a string of valid symbols from a sequence of handwritten strokes comprising the steps of: generating, in response to one or more handwritten strokes, a plurality of stroke labels each having an associated score; and processing the plurality of stroke labels to identify stroke labels indicative of a valid symbol or portion of a valid symbol, the step of processing including the steps of storing the stroke labels within a data structure by order of score, the data structure storing all or a portion of all paths through a search space defined by the plurality of stroke labels; and reading a path from the data structure, extending the path with possible successor paths, and merging the extended paths back into the data structure as a function of score.

Claim 3

Dependent Claim 37 words

A method as set forth in claim 1 wherein the step of generating includes an initial step of inputting x-y coordinate data from an electronic tablet means, the x-y coordinate data being indicative of a handwritten stroke.

Claim 4

Dependent Claim 27 words

A method as set forth in claim 1 wherein the step of extending includes a step of evaluating the path with at least one constraint validation filter.

Claim 5

Dependent Claim 73 words

A method as set forth in claim 1 wherein the step of processing further includes the steps of: 1.) reading a top path from the data structure; 2.) extending the top path with all possible successor stroke labels to form one or more extended paths; 3.) merging the extended paths into the search space as a function of score; and 4.) repeating from step (1.) until an end of input condition is reached.

Claim 6

Dependent Claim 27 words

A method as set forth in claim 1 wherein the step of processing further includes the steps of: 1.) removing a top path from the data structure;

Claim 7

Dependent Claim 110 words

5) extending a younger sister path from a parent of the top-path; 1.6) merging the younger sister path back into the stack as a function or score; 1.7) sending the top path through at least one constraint validation filter; if the top path survives the filter, 2.) extending the top path with the best one among candidates returned from the constraint validation filter; 3a.) merging the extended top path back into the data structure with an associated FLAG=OPEN; 3b.) merging the original top-path back into the data structure with an associated FLAG=CLOSED; and 4.) repeating the steps of the procedure from (1.) until an end of input condition is reached.

Claim 8

Dependent Claim 110 words

5) extending a younger sister path from a parent of the top-path; 1.6) merging the younger sister path back into the stack as a function or score; 1.7) sending the top path through at least one constraint validation filter; if the top path survives the filter, 2.) extending the top path with the best one among candidates returned from the constraint validation filter; 3a.) merging the extended top path back into the data structure with an associated FLAG=OPEN; 3b.) merging the original top-path back into the data structure with an associated FLAG=CLOSED; and 4.) repeating the steps of the procedure from (1.) until an end of input condition is reached.

Claim 9

Dependent Claim 81 words

A method as set forth in claim 5 wherein as a result of the execution of Step 1.7 a plurality of possible results are obtained, including: (a) the constraint validation filter eliminates the top path when the path violates the constraint represented by the constraint validation filter; (b) the constraint validation filter penalizes the score associated with the top path; and (c) the constraint validation filter validates the top path such that the score associated with the top path is unchanged.

Claim 10

Dependent Claim 27 words

A method as set forth in claim 4 wherein the step of merging includes a step of providing a pointer to another entry in the data structure.

Claim 11

Dependent Claim 28 words

A method as set forth in claim 5 wherein the steps of merging each include a step of providing a pointer to another entry in the data structure.

Claim 12

Dependent Claim 54 words

A method as set forth in claim 1 wherein the step of processing includes an initial step of specifying for use one or more constraint validation filters selected from the group consisting of dictionary constraint filters, syntactic constraint filters, semantic constraint filters, stroke topology constraint filters, n-gram constraint filters and variations and combinations thereof.

Claim 13

Dependent Claim 140 words

Apparatus for identifying a valid symbol or a string of valid symbols from a sequence of handwritten strokes comprising: means for generating, in response to one or more handwritten strokes, a plurality of stroke labels each having an associated score; and means for processing the plurality of stroke labels to identify stroke labels indicative of a valid symbol or portion of a valid symbol, the means for processing comprising means for storing the stroke labels within a data structure by order of score, the data structure storing all or a portion of all paths through a search space defined by the plurality of stroke labels; and means for reading a path from the data structure, means for extending the path with possible successor paths, and means for merging extended paths back into the data structure as a function of score.

Claim 14

Dependent Claim 140 words

Apparatus for identifying a valid symbol or a string of valid symbols from a sequence of handwritten strokes comprising: means for generating, in response to one or more handwritten strokes, a plurality of stroke labels each having an associated score; and means for processing the plurality of stroke labels to identify stroke labels indicative of a valid symbol or portion of a valid symbol, the means for processing comprising means for storing the stroke labels within a data structure by order of score, the data structure storing all or a portion of all paths through a search space defined by the plurality of stroke labels; and means for reading a path from the data structure, means for extending the path with possible successor paths, and means for merging extended paths back into the data structure as a function of score.

Claim 15

Dependent Claim 34 words

Apparatus as set forth in claim 10 wherein the means for generating includes means for inputting x-y coordinate data from an electronic tablet means, the x-y coordinate data being indicative of a handwritten stroke.

Claim 16

Dependent Claim 20 words

Apparatus as set forth in claim 10 wherein the means for processing includes at least one constraint validation filter means.

Claim 17

Dependent Claim 60 words

Apparatus as set forth in claim 10 wherein the means for processing further comprises: means for reading a top path from the data structure; means for extending the top path with all possible successor stroke labels to form one or more extended paths; and means for merging the extended paths back into the data structure as a function of score.

Claim 18

Dependent Claim 102 words

Apparatus as set forth in claim 13 and further including one or more constraint validation filters switchably coupled in series between the extending means and the merging means and wherein the means for extending is comprised of: means for extending a younger sister path from a parent of the top-path; means for merging the younger sister path back into the data structure as a function of score; means for directing the top path through the at least one constraint validation filter; and means for extending the top path with a most probable one of the paths returned from the constraint validation filter.

Claim 19

Dependent Claim 43 words

Apparatus as set forth in claim 14 wherein the at least one constraint validation filter is selected from the group consisting of dictionary constraint filters, syntactic constraint filters, semantic constraint filters, stroke topology constraint filters, n-gram constraint filters and variations and combinations thereof.

Claim 20

Independent Claim 119 words

A method for identifying a valid symbol or a string of valid symbols from a sequence of handwritten strokes comprising the steps of: generating in response to one or more handwritten strokes a plurality of stroke labels each having an associated score; storing the stroke labels within a first data structure; and processing selected ones of the plurality of stored stroke labels with one or more constraint validation filter means to identify those stored stroke labels indicative of a valid symbol or portion of a valid symbol, the step of processing including a step of storing within a second data structure those stored stroke labels identified to be indicative of a valid symbol or portion of a valid symbol.

Claim 21

Independent Claim 119 words

A method for identifying a valid symbol or a string of valid symbols from a sequence of handwritten strokes comprising the steps of: generating in response to one or more handwritten strokes a plurality of stroke labels each having an associated score; storing the stroke labels within a first data structure; and processing selected ones of the plurality of stored stroke labels with one or more constraint validation filter means to identify those stored stroke labels indicative of a valid symbol or portion of a valid symbol, the step of processing including a step of storing within a second data structure those stored stroke labels identified to be indicative of a valid symbol or portion of a valid symbol.

Claim 22

Dependent Claim 46 words

A method as set forth in claim 16 wherein the step of storing within a second data structure includes a step of storing within a stack data structure all or a portion of all paths through a search space defined by the plurality of stroke labels.

Claim 23

Dependent Claim 111 words

A method as set forth in claim 17 wherein the step of processing includes a step of inputting a selected one of the stored stroke labels to at least one of the constraint validation filter means, the step of inputting including a step of determining if the inputted stroke label is validated or invalidated by the at least one constraint validation filter means, and further includes a step of increasing the score associated with the inputted stroke label by an amount within a range of zero to some positive value, the amount being a function of whether the inputted stroke label is validated or invalidated by the constraint validation filter means.

Claim 24

Dependent Claim 39 words

A method as set forth in claim 18 and including a step of merging a processed stroke label into the stack data structure at a position that is a function of a modified score of the processed stroke label.

Claim 25

Dependent Claim 30 words

A method as set forth in claim 19 wherein the step of merging includes a step of providing a pointer to another stroke label stored in the stack data structure.

Claim 26

Dependent Claim 54 words

A method as set forth in claim 16 wherein the step of processing includes an initial step of specifying for use one or more constraint validation filters selected from the group consisting of dictionary constraint filters, syntactic constraint filters, semantic constraint filters, stroke topology constraint filters, n-gram constraint filters and variations and combinations thereof.

Claim 27

Dependent Claim 37 words

A method as set forth in claim 16 wherein the step of storing the stroke labels within a first data structure includes a step of forming a linked list of stroke labels associated with each handwritten stroke.

Claim 28

Dependent Claim 61 words

A method as set forth in claim 1 wherein the step of generating a plurality of stroke labels includes the steps of: comparing a handwritten stroke to a plurality of stroke templates to identify a symbol or symbols of which the handwritten stroke may be a constituent; and associating the handwritten stroke with a specific constituent stroke of each identified symbol.

Claim 29

Dependent Claim 38 words

A method as set forth in claim 23 wherein the associated score is assigned a value that is a function of a degree of correlation between the handwritten stroke and a stroke template corresponding to the identified symbol.

Claim 30

Dependent Claim 26 words

A method as set forth in claim 24 wherein the step of generating includes a step of ordering the stroke labels by order of associated score.

Claim 31

Dependent Claim 79 words

A method as set forth in claim 23 wherein the step of associating the handwritten stroke with a specific constituent stroke of each identified symbol includes a step of determining a stroke label having the form (m/nC), where C is the identified symbol, where m is indicative of a number of a specific stroke out of a sequence of strokes that comprise C, and wherein n is indicative of a total number of strokes in the sequence of strokes.

Claim 32

Independent Claim 151 words

A method for identifying a valid symbol from a sequence of handwritten strokes, for each handwritten stroke the method comprises the steps of: comparing a handwritten stroke to a plurality of stroke templates to identify a symbol or symbols of which the handwritten stroke may be a constituent; associating the handwritten stroke with a portion of each identified symbol to form a stroke label; assigning a score to each stroke label, the score having a value that is a function of a degree of similarity between the handwritten stroke and the stroke template corresponding to the identified symbol; ordering the stroke labels associated with the handwritten stroke by order of score; and processing the stroke labels associated with the handwritten stroke by determining which stroke labels, if any, when combined with stroke labels associated with a subsequently written handwritten stroke, comprise a valid symbol or a portion of a valid symbol.

Claim 33

Independent Claim 151 words

A method for identifying a valid symbol from a sequence of handwritten strokes, for each handwritten stroke the method comprises the steps of: comparing a handwritten stroke to a plurality of stroke templates to identify a symbol or symbols of which the handwritten stroke may be a constituent; associating the handwritten stroke with a portion of each identified symbol to form a stroke label; assigning a score to each stroke label, the score having a value that is a function of a degree of similarity between the handwritten stroke and the stroke template corresponding to the identified symbol; ordering the stroke labels associated with the handwritten stroke by order of score; and processing the stroke labels associated with the handwritten stroke by determining which stroke labels, if any, when combined with stroke labels associated with a subsequently written handwritten stroke, comprise a valid symbol or a portion of a valid symbol.

Claim 34

Dependent Claim 51 words

A method as set forth in claim 27 wherein the step of processing includes an initial step of storing the stroke labels within a data structure by order of score value, the data structure storing all or a portion of all paths through a search space defined by the stroke labels.

Claim 35

Dependent Claim 72 words

A method as set forth in claim 28 wherein the step of processing includes the steps of: 1.) reading a top path from the data structure; 2.) extending the top path with all possible successor stroke labels to form one or more extended paths; 3.) merging the extended paths into the search space as a function of score; and 4.) repeating from step (1.) until an end of input condition is reached.

Claim 36

Independent Claim 203 words

A method for identifying a valid symbol from a sequence of handwritten strokes, for each handwritten stroke the method comprises the steps of: comparing a handwritten stroke to a plurality of stroke templates to identify a symbol or symbols of which the handwritten stroke may be a constituent; associating the handwritten stroke with a portion of each identified symbol to form a stroke label; assigning a score to each stroke label, the score having a value that is a function of a degree of similarity between the handwritten stroke and the stroke template corresponding to the identified symbol; ordering the stroke labels associated with the handwritten stroke by order of score; and processing the stroke labels associated with the handwritten stroke by determining which stroke labels, if any, when combined with stroke labels associated with a subsequent handwritten stroke, comprise a valid symbol or a portion of a valid symbol, wherein the step of processing includes an initial step of storing the stroke labels within a data structure by order of score value, the data structure storing all or a portion of all paths through a search space defined by the stroke labels, and wherein the step of processing includes the steps of:

Claim 37

Independent Claim 203 words

A method for identifying a valid symbol from a sequence of handwritten strokes, for each handwritten stroke the method comprises the steps of: comparing a handwritten stroke to a plurality of stroke templates to identify a symbol or symbols of which the handwritten stroke may be a constituent; associating the handwritten stroke with a portion of each identified symbol to form a stroke label; assigning a score to each stroke label, the score having a value that is a function of a degree of similarity between the handwritten stroke and the stroke template corresponding to the identified symbol; ordering the stroke labels associated with the handwritten stroke by order of score; and processing the stroke labels associated with the handwritten stroke by determining which stroke labels, if any, when combined with stroke labels associated with a subsequent handwritten stroke, comprise a valid symbol or a portion of a valid symbol, wherein the step of processing includes an initial step of storing the stroke labels within a data structure by order of score value, the data structure storing all or a portion of all paths through a search space defined by the stroke labels, and wherein the step of processing includes the steps of:

Claim 38

Dependent Claim 56 words

) removing a top path from the data structure; 1.5) extending a younger sister path from a parent of the top-path; 1.6) merging the younger sister path back into the data structure as a function of score; 1.7) sending the top path through at least one constraint validation filter; if the top path survives the filter,

Claim 39

Dependent Claim 56 words

) removing a top path from the data structure; 1.5) extending a younger sister path from a parent of the top-path; 1.6) merging the younger sister path back into the data structure as a function of score; 1.7) sending the top path through at least one constraint validation filter; if the top path survives the filter,

Claim 40

Dependent Claim 64 words

) extending the top path with the best one among candidates returned from the constraint validation filter; 3a.) merging the extending top path back into the data structure with an associated FLAG=OPEN; 3b.) merging the original top-path back into the data structure with an associated FLAG=CLOSED; and 4.) repeating the steps of the procedure from (1.) until an end of input condition is reached.

Claim 41

Dependent Claim 64 words

) extending the top path with the best one among candidates returned from the constraint validation filter; 3a.) merging the extending top path back into the data structure with an associated FLAG=OPEN; 3b.) merging the original top-path back into the data structure with an associated FLAG=CLOSED; and 4.) repeating the steps of the procedure from (1.) until an end of input condition is reached.

Claim 42

Dependent Claim 67 words

A method as set forth in claim 27 wherein the step of associating includes a step of generating a stroke label having the form (m/nC), where C is the identified symbol, where m is indicative of a number of a specific stroke out of a sequence of strokes that comprise C, and wherein n is indicative of a total number of strokes in the sequence of strokes.

Claim 43

Dependent Claim 118 words

Apparatus for identifying a valid symbol or a string of valid symbols from a sequence of handwritten strokes, comprising: means for generating, in response to one or more handwritten strokes, a plurality of stroke labels each having an associated score; means for storing the stroke labels within a first data structure; and means for processing selected ones of the plurality of stored stroke labels with one more constraint validation filter means to identify stored stroke labels that are indicative of a valid symbol or portion of a valid symbol, the processing means including means for storing within a second data structure any stroke labels identified as being indicative of a valid symbol or portion of a valid symbol.

Claim 44

Dependent Claim 118 words

Apparatus for identifying a valid symbol or a string of valid symbols from a sequence of handwritten strokes, comprising: means for generating, in response to one or more handwritten strokes, a plurality of stroke labels each having an associated score; means for storing the stroke labels within a first data structure; and means for processing selected ones of the plurality of stored stroke labels with one more constraint validation filter means to identify stored stroke labels that are indicative of a valid symbol or portion of a valid symbol, the processing means including means for storing within a second data structure any stroke labels identified as being indicative of a valid symbol or portion of a valid symbol.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1994-07-01	1994-12-31	1995-07-02	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	1998-07-01	1998-12-31	1999-07-02	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2002-07-01	2002-12-31	2003-07-02	$7700.00	Window Closed / Lapsed

Constraint driven-on line recognition of handwritten characters and symbols

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag