Method and apparatus for recognizing cursive writing from sequential input information

A method for recognizing cursive handwritten words from the dynamics of the input strokes, said method comprising the steps of

• receiving input signals having values representative of a sequence of points symbolizing handwriting and of a beginning point and of an ending point of said sequence of points;
• selecting as a candidate word the sequence of points bounded by said beginning point and said ending point;
• replacing said candidate word with a string of input metastrokes in sequential order, each metastroke being representative of an element of a cursive handwritten cipher, to obtain a preliminary metastroke string for each said candidate word;
• constructing word correlation tables by dynamic programming said word correlation tables based on stroke order and stroke position relative to a baseline using a feature correlation table of all metastrokes forming a vocabulary, said feature correlation table relating input metastrokes to vocabulary metastrokes, for selecting strings of vocabulary metastrokes corresponding to said candidate word, said strings of vocabulary metastrokes comprising a listing of entries compiled from variants of known strings of said metastrokes;
• wherein said dynamic programming step includes:
• determining for each cell in each said word correlation table a first candidate maximum score for substituting a first metastroke for a second metastroke, using substitution weighting from said feature correlation table;
• determining for each cell in each said word correlation table a second candidate maximum score for inserting a metastroke from the string of vocabulary metastrokes into said candidate word, using addition penalty weighting from said feature correlation table;
• determining for each cell in each said word correlation table a third candidate maximum score for deleting a metastroke from said candidate word to obtain a possible match to the string of vocabulary metastrokes, using penalty weighting from said feature correlation table;
• and
• placing in each cell the maximum one from among the first maximum candidate score, the second maximum candidate score and the third maximum candidate score;
• thereafter
• extracting a single candidate maximum score for each one of said word correlation tables only upon completion of said word correlation table;
• and
• identifying, to an output device, upon completion of said constructing step, based on the highest one of said maximum scores, a most likely match between said candidate word and one of said strings of vocabulary metastrokes.

A method for recognizing cursive handwritten words from the dynamics of the input strokes, said method comprising the steps of:

• receiving input signals having values representative of a sequence of points symbolizing handwriting and of a beginning point and of an ending point of said sequence of points;
• selecting as a candidate word the sequence of points bounded by said beginning point and said ending point;
• locating and tabulating, in sequential order, critical points in said candidate word, said critical points including maxima, minima, intersections, dots and crossovers;
• replacing said candidate word with a string of metastrokes in sequential order, each metastroke being representative of an element of a cursive handwritten cipher, said replacing step comprising comparing said critical points against indicia of known critical points of a selection of said metastrokes to obtain a preliminary metastroke string for each said candidate word;
• constructing word correlation tables, by use of a feature correlation table of all metastrokes forming a vocabulary, said feature correlation table relating input metastrokes to vocabulary metastrokes, for selecting strings of vocabulary metastrokes corresponding to said candidate word, said strings of vocabulary metastrokes comprising a listing of entries compiled from variants of known strings of said metastrokes;
• choosing preferred metastroke strings according to an optimal cost calculation, said optimal cost calculation comprising the weighting of additions, deletions, and substitutions of metastrokes relative to adjacent metastrokes;
• extracting a single candidate maximum score for each one of said word correlation tables only upon completion of said word correlation table;
• and
• identifying, to an output device, candidate words from a listing of said most likely matches from said dictionary, with an indication of positive recognition of a single candidate word upon achievement of a likelihood of match in excess of a preselected threshold value.

A method for recognizing cursive handwritten words from the dynamics of the input strokes, said method comprising the steps of:

• receiving input signals having values representative of a sequence of points symbolizing handwriting and of a beginning point and of an ending point of said sequence of points, said sequence of points being defined within a coordinate system;
• selecting as a candidate word the sequence of points bounded by said beginning point and said ending point;
• reconstructing said candidate word as a reconstructed word with a substitute sequence of points, said substitute sequence of points having interpolated points inserted and spurious points deleted;
• establishing a bottom baseline and a top baseline for said candidate word to determine height and scale;
• locating and tabulating, in sequential order, critical points in said reconstructed word, said critical points including maxima, minima, intersections, dots and crossovers;
• replacing said reconstructed word with a string of metastrokes in sequential order, each metastroke being representative of an element of a handwritten cipher, said replacing step comprising comparing said critical points against indicia of known critical points of a minimum of twenty of said metastrokes to obtain a preliminary metastroke string for each said reconstructed word;
• constructing word correlation tables, by use of a feature correlation table of all metastrokes forming a vocabulary, said feature correlation table relating input metastrokes to vocabulary metastrokes, for selecting strings of vocabulary metastrokes corresponding to said candidate word, said strings of vocabulary metastrokes comprising a listing of entries compiled from variants of known strings of said metastrokes;
• choosing preferred metastroke strings according to an optimal cost calculation, said optimal cost calculation comprising the weighting of additions, deletions, and substitutions of metastrokes relative to adjacent metastrokes;
• extracting a single candidate maximum score for each one of said word correlation tables only upon completion of said word correlation table;
• and
• identifying, to an output device, based on the highest one of said maximum scores, a most likely match between said candidate word and one of said strings of vocabulary metastrokes upon achievement of a maximum score in excess of a preselected threshold value.

A method for recognizing cursive handwritten words from the dynamics of the input strokes, said method comprising the steps of:

• receiving input signals having values representative of a sequence of points symbolizing handwriting and of a beginning point and of an ending point of said sequence of points;
• selecting as a candidate word the sequence of points bounded by said beginning point and said ending point;
• locating and tabulating, in sequential order, critical points in said candidate word, said critical points including maxima, minima, intersections, dots and crossovers;
• replacing said candidate word with a string of metastrokes in sequential order, each metastroke being representative of an element of a cursive handwritten cipher, said replacing step comprising comparing said critical points against indicia of known critical points of a selection of said metastrokes to obtain a preliminary metastroke string for each said candidate word;
• constructing word correlation tables, by use of a feature correlation table of all metastrokes forming a vocabulary, said feature correlation table relating input metastrokes to vocabulary metastrokes, for selecting strings of vocabulary metastrokes corresponding to said candidate word, said strings of vocabulary metastrokes comprising a listing of entries compiled from variants of known strings of said metastrokes;
• choosing preferred metastroke strings according to an optimal cost calculation, said optimal cost calculation comprising the weighting of additions, deletions, and substitutions of metastrokes relative to adjacent metastrokes;
• extracting a single candidate maximum score for each one of said word correlation tables only upon completion of said word correlation table;
• and
• identifying, to an output device, candidate words from a listing of said most likely matches from said dictionary, with an indication of positive recognition of a single candidate word upon achievement of a likelihood of match in excess of a preselected threshold value;
• wherein said optimal cost calculation comprises the steps of:
• determining a first candidate maximum score value of an exchange of a first candidate metastroke with a second candidate metastroke at a cell in the word correlation table employing data from the feature correlation table and a height correlation table according to the relation:
• .alpha.1.sub.i.sup.j =.alpha..sub.i-1.sup.j-1 +p(a.sub.i,b.sub.j)+q(a.sub.j,b.sub.j) [1]
• determining a second candidate maximum score value of an addition of a second candidate metastroke at a cell in the word correlation table according to the relation:
• .alpha.2.sub.i.sup.j =.alpha..sub.i-1.sup.j +p(a.sub.i)+q(a.sub.i)[2]
• and
• determining a third candidate maximum score value of a deletion of said first candidate metastroke at a cell in the word correlation table according to the relation:
• .alpha.3.sub.i.sup.j =.alpha..sub.i.sup.j-1 p(b.sub.j)+q(b.sub.j)[3]
• wherein:
• .alpha..sup.j.sub.i is the "cost value " (as used in the vocabulary of dynamic programming), or cumulative score at the cell (i,j) for passing from the origin via cell (i-1, j-1) in substituting the vocabulary metastroke "a" at row position (i) for the input metastroke "b" at column position (j);
• p(a.sub.i,b.sub.j) is a similarity weighting value of the substitution of an input metastroke "a.sub.1 " by a vocabulary metastroke "b.sub.j ";
• q(a.sub.j,b.sub.j) is the height weighting value for height substitution occurring in the foregoing substitution of input metastroke "a.sub.i " by vocabulary metastroke "b.sub.j ";
• .alpha.2is the "cost value" or cumulative score for passing from the origin via cell (i-1,j) to cell (i,j) in inserting the vocabulary metastroke "a" at row position (i) after the input metastroke "b" at column position (j);
• .alpha.3 is the "cost value" for cumulative score for passing from the origin via cell (i,j-1) to cell (i,j) in deleting the input metastroke "b" at column (j) along a sequence of metastrokes;
• p(a.sub.i) is a penalty value for inserting the vocabulary metastroke "a" at row position (i) after the input metastroke "b" at column position (j);
• q(.sub.i) is the penalty value for height associated with the foregoing insertion;
• p(b.sub.j) is a penalty value for deleting a metastroke "b.sub.j ";
• q(b.sub.j) is the penalty value for height associated with the foregoing deletion.

An apparatus for recognizing cursive handwritten words from the dynamics of the input strokes, said apparatus comprising:

• means for receiving input signals having values representative of a sequence of points symbolizing handwriting and of a beginning point and of an ending point of said sequence of points;
• means coupled to said receiving means for selecting as a candidate word a sequence of points bounded by said beginning point and said ending point;
• means coupled to said combining means for locating and tabulating, in sequential order, critical points in said candidate word, said critical points including maxima, minima, intersections, dots and crossovers;
• means coupled to said locating and tabulating means for replacing said candidate word with a sequence of metastrokes in sequential order, each metastroke being representative of an element of a cursive handwritten cipher, said replacing means comprising means for comparing said critical points against indicia of known critical points to obtain a preliminary metastroke sequence for each said candidate word;
• means for constructing word correlation tables, by use of a feature correlation table of all metastrokes forming a vocabulary, said feature correlation table relating input metastrokes to vocabulary metastrokes, for selecting strings of vocabulary metastrokes corresponding to said candidate word, said strings of vocabulary metastrokes comprising a listing of entries compiled from variants of known strings of said metastrokes;
• means for choosing preferred metastroke strings according to an optimal cost calculation, said choosing means comprising means for the weighting of additions, deletions, and substitutions of metastrokes relative to adjacent metastrokes;
• means for extracting a single candidate maximum score for each one of said word correlation tables only upon completion of said word correlation table;
• and
• means for identifying, to an output device, candidate words from a listing of said most likely matches from said dictionary, with an indication of positive recognition of a single candidate word upon achievement of a likelihood of match in excess of a preselected threshold value.