System and method for handwriting matching using edit distance computation in a systolic array processor
First Claim
1. Apparatus for comparing an electronic handwritten pattern to a stored string representing a handwritten document comprising at least one of the group consisting of a paragraph, a page, a sentence, text and graphics, the stored string including a group of portions, each portion having at least one stroke, the apparatus comprising:
- means for monitoring movement of a stylus that forms the electronic handwritten pattern, the handwritten pattern being shorter than the stored string, the monitoring means generating therefrom an input handwritten sequence of strokes, each stroke representing one of a plurality of predetermined stylus movements within a predetermined alphabet, the input handwritten sequence of strokes having a plurality of portions;
a linear systolic array processor for determining an edit distance between a substring of the stored string and the input handwritten sequence of strokes, thereby to search the stored string of handwritten strokes for an occurrence of the input handwritten sequence of strokes, the substring including a subset of the group of portions, the linear systolic array processor including;
means for comparing a first one of the group of portions of the stored string to a first one of the plurality of portions of the input handwritten sequence of strokes to form a comparison, and for generating a plurality of edit distance components based on the comparison, each edit distance component corresponding to a respectively different set of operations that transforms the first portion of the stored string into the first portion of the pattern, wherein at least one of the plurality of edit distance components is calculated based on a further comparison between a second portion of the stored string and a second portion of the handwritten sequence of strokes,wherein the means for comparing generates the plurality of edit distance components including a group of initial edit components related to the stored string which are set to 0,means for selecting the edit distance component which has a minimum value among the plurality of edit distance components,means for determining the edit distance based on a plurality of comparisons, wherein the plurality of comparisons includes the comparison and the further comparison, andmeans for determining which substring of the stored string differs from the input handwritten sequence of strokes by the smallest edit distance, thereby locating the one substring within the stored string that most closely matches the input handwritten sequence of strokes that is shorter than the stored string.
3 Assignments
0 Petitions
Accused Products
Abstract
Apparatus and a method for comparing an electronic handwritten pattern to a stored string are provided. The string includes a group of portions, each having at least one stroke. Movement of a stylus forms the pattern, and a sequence of strokes is generated. Each stroke represents a stylus movement within a predetermined alphabet. The sequence of strokes has a plurality of portions. A linear systolic array processor determines an edit distance between the string and the pattern. The processor compares a first portion of the string to a first portion of the pattern. A plurality of edit distance components are generated based on the comparison. Each component corresponds to a different set of operations that transforms the first portion of the stored string into the first portion of the pattern. The components are calculated based on a further comparison between additional portions of the stored string and the pattern. The component which has a minimum value is selected. The comparison is performed between each respective portion of the pattern and the corresponding portion of the stored string. The total edit distance is based on the component selected during a last comparison between a last portion of the stored string and a last portion of the pattern.
69 Citations
25 Claims
-
1. Apparatus for comparing an electronic handwritten pattern to a stored string representing a handwritten document comprising at least one of the group consisting of a paragraph, a page, a sentence, text and graphics, the stored string including a group of portions, each portion having at least one stroke, the apparatus comprising:
-
means for monitoring movement of a stylus that forms the electronic handwritten pattern, the handwritten pattern being shorter than the stored string, the monitoring means generating therefrom an input handwritten sequence of strokes, each stroke representing one of a plurality of predetermined stylus movements within a predetermined alphabet, the input handwritten sequence of strokes having a plurality of portions; a linear systolic array processor for determining an edit distance between a substring of the stored string and the input handwritten sequence of strokes, thereby to search the stored string of handwritten strokes for an occurrence of the input handwritten sequence of strokes, the substring including a subset of the group of portions, the linear systolic array processor including; means for comparing a first one of the group of portions of the stored string to a first one of the plurality of portions of the input handwritten sequence of strokes to form a comparison, and for generating a plurality of edit distance components based on the comparison, each edit distance component corresponding to a respectively different set of operations that transforms the first portion of the stored string into the first portion of the pattern, wherein at least one of the plurality of edit distance components is calculated based on a further comparison between a second portion of the stored string and a second portion of the handwritten sequence of strokes, wherein the means for comparing generates the plurality of edit distance components including a group of initial edit components related to the stored string which are set to 0, means for selecting the edit distance component which has a minimum value among the plurality of edit distance components, means for determining the edit distance based on a plurality of comparisons, wherein the plurality of comparisons includes the comparison and the further comparison, and means for determining which substring of the stored string differs from the input handwritten sequence of strokes by the smallest edit distance, thereby locating the one substring within the stored string that most closely matches the input handwritten sequence of strokes that is shorter than the stored string. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 25)
-
-
22. Apparatus for comparing an electronic handwritten pattern to a stored string representing a handwritten document comprising at least one of the group consisting of a paragraph, a page, a sentence, text and graphics, the stored string including a group of strokes, comprising:
-
means for monitoring movement of a stylus that forms the electronic handwritten pattern, the handwritten pattern being shorter than the stored string, the monitoring means generating therefrom an input handwritten sequence of strokes, each stroke representing one of a plurality of predetermined stylus movements within a predetermined alphabet; a linear systolic array processor for determining an edit distance between a substring of the stored string and the sequence of strokes, the substring including a subset of the group of strokes, the linear systolic array processor comprising a plurality of processing elements connected in a line, such that each one of the plurality of processing elements includes means for storing a respective one of the strokes in the input handwritten sequence of strokes, and the group of strokes within the stored string are successively transmitted across the line of processing elements, in order to search the stored string of handwritten strokes for an occurrence of the input handwritten sequence of strokes, each of the plurality of processing elements including; means for receiving first and second input edit distance components from first and second previous ones of the plurality of processing elements, and for storing the first and second input edit distance components for a period of time during which the processing element processes two of the strokes within the input handwritten sequence of strokes, means for comparing a portion of the stored string to a portion of the pattern to form a comparison, and for generating a plurality of edit sequence components based on (1) the comparison and (2) the first and second input edit distance components, each edit sequence component identifying a respectively different set of operations that transforms the portion of the stored string into the portion of the pattern, each edit sequence component having a respective edit distance components, wherein the means for comparing generates the plurality of edit distance components including a group of initial edit components related to the stored string which are set to 0, means for selecting the edit sequence component for which the edit distance component has a minimum value; and means for determining which substring of the stored string differs from the input handwritten sequence of strokes by the smallest edit distance, thereby locating the one substring within the stored string that most closely matches the input handwritten sequence of strokes that is shorter than the stored string.
-
-
23. Apparatus for comparing an electronic handwritten pattern to a stored string representing a handwritten document comprising at least one of the group consisting of a paragraph, a page, a sentence, text and graphics, the stored string including a group of strokes, comprising:
-
means for monitoring movement of a stylus that forms the electronic handwritten pattern, and for generating therefrom an input handwritten sequence of strokes, each stroke representing one of a plurality of predetermined stylus movements within a predetermined alphabet; a linear systolic array processor for determining an edit distance between the stored string and the input handwritten sequence of strokes, thereby to search the stored string of handwritten strokes for an occurrence of the input handwritten sequence of strokes, the linear systolic array processor comprising a plurality of processing elements connected in a line, such that each one of the plurality of processing elements includes means for storing a respective one of the strokes in the input handwritten sequence of strokes, and the corresponding strokes within the stored string are successively transmitted across the line of processing elements, each of the plurality of processing elements including; (a) means for determining a first edit distance component based on a given stroke being present at the specific position within the input handwritten sequence of strokes but being absent from the specific position within the stored string; (b) means for determining a second edit distance component based on the given stroke being present at the specific position within the stored string, but a different stroke being substituted therefor at the specific position within the input handwritten sequence of strokes; (c) means for determining a third edit distance component based on two strokes being present at the specific position within the stored string, but a single stroke being substituted therefor at the specific position within the input handwritten sequence of strokes; (d) means for determining a fourth edit distance component based on a single stroke being present at the specific position within the stored string, but two strokes being substituted therefor at the specific position within the input handwritten sequence of strokes; (e) means for determining a fifth edit distance component based on two strokes being present at the specific position within the stored string, but two further strokes being substituted therefor at the specific position within the input handwritten sequence of strokes; (f) means for determining a sixth edit distance component based on the given stroke being present at a specific position within the stored string but being absent from the specific position within the input handwritten sequence of strokes; (g) means for selecting a minimum component from the group consisting of the first through sixth edit distance components, wherein the systolic array processor generates the first through sixth edit distance components to include a group of initial edit components related to the stored string which are set to 0.
-
-
24. A method for comparing an electronic handwritten pattern to a stored string representing a handwritten document comprising at least one of the group consisting of a paragraph, a page, a sentence, text and graphics, the stored string including a group of strokes, comprising the steps of:
-
(1) monitoring movement of a stylus that forms the electronic handwritten pattern, the handwritten pattern being shorter than the stored string, and generating therefrom an input handwritten sequence of strokes, each stroke representing one of a plurality of predetermined stylus movements within a predetermined alphabet; (2) transmitting the group of strokes and the input handwritten sequence of strokes to a linear systolic array processor comprising a plurality of cascade connected processing elements, (3) storing a respective one of the strokes in the input handwritten sequence of strokes within each one of the plurality of processing elements (4) transmitting the group of strokes within the stored string successively across the cascade connected processing elements, each of the plurality of processing elements performing the steps of; (a) receiving first and second input edit distance components from first and second previous ones of the plurality of processing elements, (b) storing the first and second input edit distance components for a period of time during which the processing element processes two of the strokes within the input handwritten sequence of strokes, (c) comparing a portion of the stored string to a portion of the pattern to form a comparison, (d) generating a plurality of edit sequence components based on (1) the comparison and (2) the first and second input edit distance components, each edit sequence component identifying a respectively different set of operations that transforms the portion of the stored string into the portion of the pattern, each edit sequence component having a respective edit distance component, and (e) selecting the edit sequence component for which the edit distance component has a minimum value; (5) determining an edit distance between a subset of the stored string and the input handwritten sequence of strokes, the substring including a subset of the group of strokes, based on the edit sequence component selected by a last one of the plurality of processing elements;
including a step of generating the edit distance to include an initial edit component related to the stored string which is set to 0, and(6) determining which substring of the stored string differs from the input handwritten sequence of strokes by the smallest edit distance, thereby locating the one substring within the stored string that most closely matches the input handwritten sequence of strokes that is shorter than the stored string, thereby to search the stored string of handwritten strokes for an occurrence of the sequence of strokes.
-
Specification