Patent US1968954A successfully refreshed from Google Patents.
Patent US5757964A successfully refreshed from Google Patents.
US5757964A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for automatic subcharacter unit and lexicon generation for handwriting recognition
Assignee: Apple Inc
•
Filing: 1997-07-29
•
Granted: 1998-05-26
•
Expires: 2017-07-29
Abstract
Abstract A system for automatic subcharacter unit and lexicon generation for handwriting recognition comprises a processing unit, a handwriting input device, and a memory wherein a segmentation unit, a subcharacter generation unit, a lexicon unit, and a modeling unit reside. The segmentation unit generates feature vectors corresponding to sample characters. The subcharacter generation unit clusters feature vectors and assigns each feature vector associated with a given cluster an identical label. The lexicon unit constructs a lexical graph for each character in a character set. The modeling unit generates a Hidden Markov Model for each set of identically-labeled feature vectors. After a first set of lexical graphs and Hidden Markov Models have been created, the subcharacter generation unit determines for each feature vector which Hidden Markov Model produces a highest likelihood value. The subcharacter generation unit relabels each feature vector according to the highest likelihood value, after which the lexicon unit and the modeling unit generate a new set of lexical graphs and a new set of Hidden Markov models, respectively. The feature vector relabeling, lexicon generation, and Hidden Markov Model generation are performed iteratively until a convergence criterion is met. The final set of Hidden Markov Model model parameters provide a set of subcharacter units for handwriting recognition, where the subcharacter units are derived from information inherent in the sample characters themselves.
Inventors
- 👤 Kai-Fu Lee
- 👤 Yen-Lu Chow
- 👤 Kamil Grajski
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 15:02
CPC Classifications
G; G06; G06F; G06F18/00; G06F18/20; G06F18/28; G06F18/29; G06F18/295
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
176 words
In a handwriting recognition system having a processing unit, a handwriting input device, and a memory, a method for automatic subcharacter unit and lexicon generation comprising the steps of: retrieving a plurality of sample characters, each sample character representing a reference character within a character set; partitioning each sample character into a set of segments with associated time intervals; creating a feature vector corresponding to each segment; clustering the feature vectors according to a distance metric; storing in each feature vector a label identifying a cluster with which the feature vector is associated; creating a pattern recognition model for each set of identically-labeled feature vectors; selecting a feature vector; determining which pattern recognition model produces a highest likelihood value for the selected feature vector; storing a label identifying the pattern recognition model producing the highest likelihood value in the selected feature vector; determining whether a convergence criterion has been satisfied; and if said convergence criterion is satisfied, incorporating the segment corresponding to said labeled feature vector into a lexicon of subcharacters for said handwriting recognition system.
Claim 2
Dependent Claim
176 words
In a handwriting recognition system having a processing unit, a handwriting input device, and a memory, a method for automatic subcharacter unit and lexicon generation comprising the steps of: retrieving a plurality of sample characters, each sample character representing a reference character within a character set; partitioning each sample character into a set of segments with associated time intervals; creating a feature vector corresponding to each segment; clustering the feature vectors according to a distance metric; storing in each feature vector a label identifying a cluster with which the feature vector is associated; creating a pattern recognition model for each set of identically-labeled feature vectors; selecting a feature vector; determining which pattern recognition model produces a highest likelihood value for the selected feature vector; storing a label identifying the pattern recognition model producing the highest likelihood value in the selected feature vector; determining whether a convergence criterion has been satisfied; and if said convergence criterion is satisfied, incorporating the segment corresponding to said labeled feature vector into a lexicon of subcharacters for said handwriting recognition system.
Claim 3
Dependent Claim
38 words
The method of claim 1, wherein the steps of selecting a feature vector, determining which pattern recognition model produces a highest likelihood value, and storing a label identifying the pattern recognition model are performed for each feature vector.
Claim 4
Dependent Claim
50 words
The method of claim 2, wherein the steps of creating a pattern recognition model, selecting a feature vector, determining which pattern recognition model produces a highest likelihood value, and storing a label identifying the pattern recognition model are repeated if it is determined that the convergence criterion is not satisfied.
Claim 5
Dependent Claim
42 words
The method of claim 1, wherein each feature vector includes a first data field for storing a reference to a corresponding sample character, a second data field for storing a time index, and a third data field for storing a feature list.
Claim 6
Dependent Claim
15 words
The method of claim 1, wherein the pattern recognition model is a Hidden Markov Model.
Claim 7
Dependent Claim
31 words
The method of claim 1, further comprising the steps of: selecting a first reference character within the character set; and generating a detailed lexical graph corresponding to the selected reference character.
Claim 8
Dependent Claim
55 words
The method of claim 6, wherein the step of generating a detailed lexical graph comprises the steps of: selecting a first feature vector generated from a first sample character associated with the selected reference character; and storing the label of the first feature vector in a label list that corresponds to the first sample character.
Claim 9
Dependent Claim
24 words
The method of claim 7, wherein the steps of selecting and storing are performed for each sample character associated with the selected reference character.
Claim 10
Dependent Claim
34 words
The method of claim 7, further comprising the steps of: selecting a next feature vector generated from the first sample character; and storing the label of the next feature vector in the label list.
Claim 11
Dependent Claim
21 words
The method of claim 6, further comprising the step of simplifying the detailed lexical graph to produce a simplified lexical graph.
Claim 12
Dependent Claim
188 words
In a handwriting recognition system having a processing unit, a handwriting input device, and a memory, a method for automatic subcharacter unit and lexicon generation comprising the steps of: retrieving a plurality of sample characters, each sample character representing a reference character within a character set; partitioning each sample character into a set of segments, with associated time intervals; creating a feature vector corresponding to each segment; clustering the feature vectors created according to a distance metric; storing in each feature vector a label identifying a cluster with which the feature vector is associated; creating a pattern recognition model for each set of identically-labeled feature vectors; selecting a feature vector; determining which pattern recognition model produces a highest likelihood value for the selected feature vector; storing a label identifying the pattern recognition model producing the highest likelihood value in the selected feature vector; determining whether a convergence criterion has been satisfied; selecting a first reference character within the character set; generating a detailed lexical graph corresponding to the selected reference character; and simplifying the detailed lexical graph by using dynamic time warping to produce a simplified lexical graph.
Claim 13
Dependent Claim
188 words
In a handwriting recognition system having a processing unit, a handwriting input device, and a memory, a method for automatic subcharacter unit and lexicon generation comprising the steps of: retrieving a plurality of sample characters, each sample character representing a reference character within a character set; partitioning each sample character into a set of segments, with associated time intervals; creating a feature vector corresponding to each segment; clustering the feature vectors created according to a distance metric; storing in each feature vector a label identifying a cluster with which the feature vector is associated; creating a pattern recognition model for each set of identically-labeled feature vectors; selecting a feature vector; determining which pattern recognition model produces a highest likelihood value for the selected feature vector; storing a label identifying the pattern recognition model producing the highest likelihood value in the selected feature vector; determining whether a convergence criterion has been satisfied; selecting a first reference character within the character set; generating a detailed lexical graph corresponding to the selected reference character; and simplifying the detailed lexical graph by using dynamic time warping to produce a simplified lexical graph.
Claim 14
Dependent Claim
180 words
In a handwriting recognition system having a processing unit, a handwriting input device, and a memory, a means for automatic subcharacter unit and lexicon generation comprising: means for retrieving a plurality of sample characters; means for creating a set of segments with associated time intervals associated with each sample character; means for creating a feature vector corresponding to each segment; means for clustering the feature vectors according to a distance metric; means for storing in each feature vector a label identifying a cluster with which the feature vector is associated; means for training a pattern recognition model for each set of identically-labeled feature vectors; means for selecting a feature vector; means for determining which pattern recognition model produces a highest likelihood value for the selected feature vector; means for storing a label associated with the pattern recognition model producing the highest likelihood value in the selected feature vector; means for determining whether a convergence criterion has been satisfied; and means for incorporating the segment corresponding to said labeled feature vector into a lexicon of subcharacters for said handwriting recognition system.
Claim 15
Dependent Claim
180 words
In a handwriting recognition system having a processing unit, a handwriting input device, and a memory, a means for automatic subcharacter unit and lexicon generation comprising: means for retrieving a plurality of sample characters; means for creating a set of segments with associated time intervals associated with each sample character; means for creating a feature vector corresponding to each segment; means for clustering the feature vectors according to a distance metric; means for storing in each feature vector a label identifying a cluster with which the feature vector is associated; means for training a pattern recognition model for each set of identically-labeled feature vectors; means for selecting a feature vector; means for determining which pattern recognition model produces a highest likelihood value for the selected feature vector; means for storing a label associated with the pattern recognition model producing the highest likelihood value in the selected feature vector; means for determining whether a convergence criterion has been satisfied; and means for incorporating the segment corresponding to said labeled feature vector into a lexicon of subcharacters for said handwriting recognition system.
Claim 16
Dependent Claim
39 words
The means for automatic subcharacter unit and lexicon generation of claim 12, further comprising: means for selecting a first reference character within the character set; and means for generating a detailed lexical graph corresponding to the selected reference character.
Claim 17
Dependent Claim
69 words
The means for automatic subcharacter unit and lexicon generation of claim 13, wherein the means for generating a detailed lexical graph corresponding to the selected reference character comprises: means for selecting a first feature vector generated from a first sample character associated with the selected reference character; and means for storing the label of the first feature vector in a label list that corresponds to the first sample character.
Claim 18
Dependent Claim
27 words
The means for automatic subcharacter unit and lexicon generation of claim 13, further comprising means for simplifying the detailed lexical graph to produce a simplified lexical graph.
Claim 19
Independent Claim
190 words
A system for automatic subcharacter unit and lexicon generation for handwriting recognition in a computer system having a processing unit and a handwriting input device, the system for automatic subcharacter unit and lexicon generation comprising: a segmentation unit, for segmenting a sample character, with associated time intervals, and generating a set of feature vectors corresponding to the sample character, the segmentation unit coupled to receive a sample character from the handwriting input device; a lexicon unit, for generating a detailed lexical graph, the lexicon unit coupled to receive a feature vector from the segmentation unit; a modeling unit, for training a pattern recognition model corresponding to identically-labeled feature vectors, the modeling unit coupled to receive a feature vector from the segmentation unit; and a subcharacter generation unit, for clustering feature vectors, labeling feature vectors, and initiating the operation of the modeling unit, the subcharacter generation unit coupled to receive a feature vector from the segmentation unit and coupled to initiate the operation of the lexicon unit and the modeling unit to incorporate the segment corresponding to said labeled feature vector into a lexicon of subcharacters for said handwriting recognition system.
Claim 20
Independent Claim
190 words
A system for automatic subcharacter unit and lexicon generation for handwriting recognition in a computer system having a processing unit and a handwriting input device, the system for automatic subcharacter unit and lexicon generation comprising: a segmentation unit, for segmenting a sample character, with associated time intervals, and generating a set of feature vectors corresponding to the sample character, the segmentation unit coupled to receive a sample character from the handwriting input device; a lexicon unit, for generating a detailed lexical graph, the lexicon unit coupled to receive a feature vector from the segmentation unit; a modeling unit, for training a pattern recognition model corresponding to identically-labeled feature vectors, the modeling unit coupled to receive a feature vector from the segmentation unit; and a subcharacter generation unit, for clustering feature vectors, labeling feature vectors, and initiating the operation of the modeling unit, the subcharacter generation unit coupled to receive a feature vector from the segmentation unit and coupled to initiate the operation of the lexicon unit and the modeling unit to incorporate the segment corresponding to said labeled feature vector into a lexicon of subcharacters for said handwriting recognition system.
Claim 21
Dependent Claim
23 words
The system of claim 16, wherein the lexicon unit performs simplification operations upon the detailed lexical graph to produce a simplified lexical graph.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-05-25 | 2001-11-24 | 2002-05-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-05-25 | 2005-11-24 | 2006-05-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-05-25 | 2009-11-24 | 2010-05-26 | $7700.00 | Window Closed / Lapsed |