Patent EP0220032A2 successfully refreshed from Google Patents.
EP0220032A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Pattern classification means
Assignee: Caere Corp
•
Filing: 1986-10-10
•
Granted: —
•
Expires: 2006-10-10
Abstract
Abstract An apparatus and a method of identifying unknown input data, such as patterns or characters, in which, in order to classify unknown input characters, reference data is first collected and analyzed in order to form "ringed clusters" for each class of input data which are later used during the classification of an unknown input character. Thus coarse ringed clusters such that all data of a given class are associated with a single cluster are used to eliminate possible reference data as being the unknown input data if the unknown input data does not fall within that coarse ringed cluster. Instead there is used a set of medium ringed clusters for each class of reference data such that all data of a given class fail within the union of the set, or fine ringed clusters in which there are no known aliens contained within the union of fine ringed clusters of each given reference data class. The ringed clusters may include "certainty spheres", "confidence spheres" and "possibility spheres".
Inventors
- 👤 Mindy R. Bokser
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-10 00:53
CPC Classifications
G; G06; G06F; G06F18/00; G06F18/20; G06F18/23; G06V; G06V30/00; G06V30/10
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
78 words
An apparatus for processing known reference data which defines one or more reference classes, characterized by: means for sorting the reference data into at least one reference class; and means for forming from each class of reference data a respective set of ringed clusters of reference data, each of the ringed clusters containing a certainty sphere in turn containing selected reference data, and the set of ringed clusters containing all of the reference data of the respective class.
Claim 2
Independent Claim
78 words
An apparatus for processing known reference data which defines one or more reference classes, characterized by: means for sorting the reference data into at least one reference class; and means for forming from each class of reference data a respective set of ringed clusters of reference data, each of the ringed clusters containing a certainty sphere in turn containing selected reference data, and the set of ringed clusters containing all of the reference data of the respective class.
Claim 3
Independent Claim
74 words
An apparatus for classifying an unknown input data value, characterized by: means for receiving the input data value; means for comparing the input data value with a plurality of possibility sphere sets each of which is associated with a respective class of reference data values; and means for creating a possibility set of those reference data value classes associated with a ringed cluster set in which a possibility sphere contains the input data value.
Claim 4
Independent Claim
74 words
An apparatus for classifying an unknown input data value, characterized by: means for receiving the input data value; means for comparing the input data value with a plurality of possibility sphere sets each of which is associated with a respective class of reference data values; and means for creating a possibility set of those reference data value classes associated with a ringed cluster set in which a possibility sphere contains the input data value.
Claim 5
Independent Claim
71 words
An apparatus for classifying an unknown input data value characterised by: means for receiving the unknown input data value; means for comparing the unknown input data value with at least one certainty sphere associated with a respective reference data value class; and means for classifying the unknown input data value in the reference data value class associated with a certainty sphere if the certainty sphere contains said unknown input data value.
Claim 6
Independent Claim
71 words
An apparatus for classifying an unknown input data value characterised by: means for receiving the unknown input data value; means for comparing the unknown input data value with at least one certainty sphere associated with a respective reference data value class; and means for classifying the unknown input data value in the reference data value class associated with a certainty sphere if the certainty sphere contains said unknown input data value.
Claim 7
Independent Claim
121 words
A method of grouping and characterizing a plurality of patterns of different given types, each given type of pattern having one or more representations each of which possibly differs in varying ways from other representations of the same type of pattern, characterized by the steps of: forming a centre of a sphere within which it is desired to locate as many representations of a given pattern type as possible; defining certainty bounds by locating the representation of a pattern not of the given type closest to the centre; and defining a "certainty sphere" for representations of the given type by drawing the surface of the certainty sphere to exclude the closest known representation of a pattern not of the given type.
Claim 8
Independent Claim
121 words
A method of grouping and characterizing a plurality of patterns of different given types, each given type of pattern having one or more representations each of which possibly differs in varying ways from other representations of the same type of pattern, characterized by the steps of: forming a centre of a sphere within which it is desired to locate as many representations of a given pattern type as possible; defining certainty bounds by locating the representation of a pattern not of the given type closest to the centre; and defining a "certainty sphere" for representations of the given type by drawing the surface of the certainty sphere to exclude the closest known representation of a pattern not of the given type.
Claim 9
Dependent Claim
77 words
A method as claimed in claim 4 characterized in that the step of forming a centre of a sphere for a given type of pattern includes the steps of: collecting a large number of examples of the type of pattern; converting each example into a representation in the form of data called a "feature vector"; and for each representation, determining the distance from that representation's vector to the closest vector representing a pattern of a different type.
Claim 10
Dependent Claim
43 words
A method as claimed in claim 4 or 5 characterized by the step of defining, outside each uncertainty sphere, a "possibility sphere" such that the union of possibility spheres for a given type of pattern includes all representations of the type of pattern.
Claim 11
Dependent Claim
36 words
A method as claimed in claim 4, 5 or 6 characterized by the step of forming for each type of pattern a single coarse possibility sphere including all given known representations of the type of pattern.
Claim 12
Dependent Claim
19 words
A method as claimed in claim 7 characterized in that the coarse possibility sphere is as small as possible.
Claim 13
Independent Claim
18 words
A method as claimed in any one of claims 4-8 characterized by forming a plurality of certainty spheres.
Claim 14
Dependent Claim
68 words
A method as claimed in claim 9 characterized by the step of defining, outside each of the certainty sphere, a sphere called a "confidence sphere" enlarged from the certainty sphere by a function selected for the union of the confidence spheres to include a greater percentage of potential representations of the type and possibly also to include a number of representations of patterns not of the given type.
Claim 15
Dependent Claim
21 words
A method as claimed in claim 9 characterized in that the function is a constant factor for each type of pattern.
Claim 16
Dependent Claim
33 words
A method as claimed in claim 10 or 11 characterized by the step of defining the confidence spheres using additional representations not contained in any certainty sphere for the same type of pattern.
Claim 17
Dependent Claim
51 words
A method as claimed in claim 9, 10, 11 or 12 characterized in that the plurality is the minimum number of certainty spheres determined to be necessary for the union of certainty spheres to include every known representation of that type of pattern, the certainty spheres being called "fine certainty spheres".
Claim 18
Dependent Claim
34 words
A method as claimed in claim 10, 11, 12 or 13 characterized in that the combination of the possibility sphere and the included confidence sphere and certainty sphere is denoted as a "ringed cluster".
Claim 19
Independent Claim
112 words
A method of classifying a representation of an unknown pattern, characterized by the steps of obtaining in advance, for each pattern, a plurality of representations of the type of the pattern, and from the representations predefining for the type of pattern, within the space of all possible representations, regions certain to contain only representations of the type of pattern, and storing said precomputed definitions of regions, and, to classify the representation of an unknown pattern, comparing the representation of the unknown pattern with at least one predefined region, and if the region contains the representation of an unknown pattern, classifying the unknown pattern as that type of pattern associated with the region.
Claim 20
Independent Claim
112 words
A method of classifying a representation of an unknown pattern, characterized by the steps of obtaining in advance, for each pattern, a plurality of representations of the type of the pattern, and from the representations predefining for the type of pattern, within the space of all possible representations, regions certain to contain only representations of the type of pattern, and storing said precomputed definitions of regions, and, to classify the representation of an unknown pattern, comparing the representation of the unknown pattern with at least one predefined region, and if the region contains the representation of an unknown pattern, classifying the unknown pattern as that type of pattern associated with the region.
Claim 21
Independent Claim
409 words
A method of grouping and characterizing representations of unknown patterns of different pattern types characterized by the steps of: defining, for each of a plurality of types of known reference patterns, a coarse possibility sphere certain to contain all representations possibly of that pattern type, and defining within the coarse possibility sphere a coarse certainty sphere containing only representations certain to be of that pattern type, defining a moderate number of medium possibility spheres the union of which is certain to contain all representations possibly of that pattern type, and defining within each medium possibility sphere a medium confidence sphere in turn containing a medium certainty sphere such that the union of the medium certainty spheres contains only representations certain to be of that pattern type, and defining at least a moderate number of fine confidence spheres each containing a fine certainty sphere. such that the union of the fine certainty spheres is certain to contain all representations, and only representations, of that type of pattern, and forming one or more lists of candidate pattern types possibly represented by the unknown representation, and, until the unknown representation is determined to be certainly known or unknown, determining for successive candidate types whether the corresponding coarse possibility sphere contains said unknown representation, and if not, eliminating that candidate type, else determining whether the corresponding coarse certainty sphere contains the unknown representation and if so, deeming the unknown representation to be that type of pattern, else for each candidate not yet eliminated, successively determining whether the union of medium possibility spheres contains the unknown pattern, and if not, eliminating that candidate, else determining whether one of the unions of medium certainty spheres contains the unknown representation, and if so, deeming the unknown representation to be the same type pattern as the corresponding medium certainty union, else for each candidate not yet eliminated, successively determining whether one of the unions of medium certainty spheres contains said unknown representation, and if a union of medium certainty spheres does contain said unknown representation, deeming the unknown representation to be that type of pattern, else, associating that candidate with a medium confidence value for the unknown representation, and determining whether one of the unions of fine certainty spheres contains the unknown representation and if so deeming the unknown representation to be the type of pattern corresponding to that union, else deeming the unknown representation to be that type of pattern having the highest associated confidence value.
Claim 22
Independent Claim
409 words
A method of grouping and characterizing representations of unknown patterns of different pattern types characterized by the steps of: defining, for each of a plurality of types of known reference patterns, a coarse possibility sphere certain to contain all representations possibly of that pattern type, and defining within the coarse possibility sphere a coarse certainty sphere containing only representations certain to be of that pattern type, defining a moderate number of medium possibility spheres the union of which is certain to contain all representations possibly of that pattern type, and defining within each medium possibility sphere a medium confidence sphere in turn containing a medium certainty sphere such that the union of the medium certainty spheres contains only representations certain to be of that pattern type, and defining at least a moderate number of fine confidence spheres each containing a fine certainty sphere. such that the union of the fine certainty spheres is certain to contain all representations, and only representations, of that type of pattern, and forming one or more lists of candidate pattern types possibly represented by the unknown representation, and, until the unknown representation is determined to be certainly known or unknown, determining for successive candidate types whether the corresponding coarse possibility sphere contains said unknown representation, and if not, eliminating that candidate type, else determining whether the corresponding coarse certainty sphere contains the unknown representation and if so, deeming the unknown representation to be that type of pattern, else for each candidate not yet eliminated, successively determining whether the union of medium possibility spheres contains the unknown pattern, and if not, eliminating that candidate, else determining whether one of the unions of medium certainty spheres contains the unknown representation, and if so, deeming the unknown representation to be the same type pattern as the corresponding medium certainty union, else for each candidate not yet eliminated, successively determining whether one of the unions of medium certainty spheres contains said unknown representation, and if a union of medium certainty spheres does contain said unknown representation, deeming the unknown representation to be that type of pattern, else, associating that candidate with a medium confidence value for the unknown representation, and determining whether one of the unions of fine certainty spheres contains the unknown representation and if so deeming the unknown representation to be the type of pattern corresponding to that union, else deeming the unknown representation to be that type of pattern having the highest associated confidence value.
Claim 23
Dependent Claim
40 words
A method as claimed in claim 16 characterized by the step of excluding from the union of confident-possibility spheres possible spheres having confidence values much less than a selected fraction of the greatest confidence value in the list of possibilities.
Claim 24
Dependent Claim
38 words
A method as claimed in claim 16 or 17 characterized by the step of comparing the unknown representation with a relatively small number of certainty spheres having been used recently to classify with certainty previously received unknown representations.
Claim 25
Dependent Claim
47 words
A method as claimed in claim 16, 17 or 18 characterized in that the patterns are optical characters, and in that the comparing step comprises comparing the set of certainty spheres with the unknown representation in a selected order determined by subline information in the unknown representation.
Claim 26
Dependent Claim
34 words
A method as claimed in claim 16, 17, 18 or 19 characterized by the step of comparing the certainty spheres in order of frequency of use of the respective character in a selected language.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.