Method for pattern recognition using prototype transformations and hierarchical filtering
First Claim
1. A method for sorting articles bearing graphical patterns to be referred to as input patterns, the method comprising the steps of:
- converting each input pattern to a pixel array, storing the pixel array in a digital pattern-recognition machine, classifying each input pattern, and performing a prescribed physical manipulation of each article in response to the result of classifying the pattern borne by that article;
wherein the machine comprises a storage device and a library of prototype patterns stored within the storage device, each prototype pattern belongs to one of a multiplicity of known classes, and each prototype pattern is labeled with its respective class, and the classifying step comprises, in said machine;
a) for each input pattern, retrieving each of the prototype patterns from the storage device and evaluating a distance function d1 between the input pattern and each of the prototype patterns, wherein d1 is the first of a plurality of distance functions di, i=1, . . . , M, M a positive integer at least 2;
b) responsive to (a), keeping the K1 closest prototype patterns and eliminating from consideration the rest of the prototype patterns, wherein K1 is a positive integer less than the total number of prototype patterns in the library;
c) evaluating at least one further distance function dj between the input pattern and at least some of the K1 closest prototype patterns, wherein j is a positive integer at least 2 and at most M;
d) responsive to the evaluation of each further distance function di, i=2, . . . M, keeping the Ki closest prototype patterns and eliminating from consideration the rest of the prototype patterns, wherein Ki is a positive integer less than Ki-1 ; and
e) choosing the best class, according to an appropriate decision procedure, from the classes represented in a population of prototype patterns that is limited in response to the evaluation of the last distance function dM, wherein;
f) each evaluation of step (c) is carded out between the input pattern and the Kj-1 closest prototype patterns that were kept in response to the evaluation of the last preceding distance function dj-1 ;
g) at least one of the further distance functions di, i at least 2, such distance to be referred to as a tangent distance of complexity Li, is evaluated with reference to a set of image transformations that are selected to leave the respective classes of the prototype patterns invariant, and such evaluation comprises the further steps of;
generating Li tangent vectors from a subset of said image transformations, wherein Li is at least 1, and the Li tangent vectors define an input hyperplane containing the input pattern; and
evaluating a Euclidean distance with respect to a transformed pattern lying on the input hyperplane.
5 Assignments
0 Petitions
Accused Products
Abstract
Articles being graphical input patterns are sorted by a pattern-recognition machine that includes a data base of prototype patterns, each labeled with its respective class. The sorting method includes stops of storing input patterns in the pattern-recognition machine and classifying the stored input patterns. The classification is performed by calculating at least two distance functions between input patterns and prototype patterns. The distance functions belong to a hierarchy of distance functions that vary in the degree to which they are computationally intensive, and concomitantly, in their accuracy. Overall computational requirements are reduced by using less computationally intensive distance functions to preliminary filter out those prototype patterns that are farthest from the input pattern.
-
Citations
7 Claims
-
1. A method for sorting articles bearing graphical patterns to be referred to as input patterns, the method comprising the steps of:
- converting each input pattern to a pixel array, storing the pixel array in a digital pattern-recognition machine, classifying each input pattern, and performing a prescribed physical manipulation of each article in response to the result of classifying the pattern borne by that article;
wherein the machine comprises a storage device and a library of prototype patterns stored within the storage device, each prototype pattern belongs to one of a multiplicity of known classes, and each prototype pattern is labeled with its respective class, and the classifying step comprises, in said machine; a) for each input pattern, retrieving each of the prototype patterns from the storage device and evaluating a distance function d1 between the input pattern and each of the prototype patterns, wherein d1 is the first of a plurality of distance functions di, i=1, . . . , M, M a positive integer at least 2; b) responsive to (a), keeping the K1 closest prototype patterns and eliminating from consideration the rest of the prototype patterns, wherein K1 is a positive integer less than the total number of prototype patterns in the library; c) evaluating at least one further distance function dj between the input pattern and at least some of the K1 closest prototype patterns, wherein j is a positive integer at least 2 and at most M; d) responsive to the evaluation of each further distance function di, i=2, . . . M, keeping the Ki closest prototype patterns and eliminating from consideration the rest of the prototype patterns, wherein Ki is a positive integer less than Ki-1 ; and e) choosing the best class, according to an appropriate decision procedure, from the classes represented in a population of prototype patterns that is limited in response to the evaluation of the last distance function dM, wherein; f) each evaluation of step (c) is carded out between the input pattern and the Kj-1 closest prototype patterns that were kept in response to the evaluation of the last preceding distance function dj-1 ; g) at least one of the further distance functions di, i at least 2, such distance to be referred to as a tangent distance of complexity Li, is evaluated with reference to a set of image transformations that are selected to leave the respective classes of the prototype patterns invariant, and such evaluation comprises the further steps of; generating Li tangent vectors from a subset of said image transformations, wherein Li is at least 1, and the Li tangent vectors define an input hyperplane containing the input pattern; and evaluating a Euclidean distance with respect to a transformed pattern lying on the input hyperplane. - View Dependent Claims (3, 4, 5, 6, 7)
- converting each input pattern to a pixel array, storing the pixel array in a digital pattern-recognition machine, classifying each input pattern, and performing a prescribed physical manipulation of each article in response to the result of classifying the pattern borne by that article;
-
2. A method for sorting articles bearing graphical patterns to be referred to as input patterns, the method comprising the steps of:
- converting each input pattern to a pixel array, storing the pixel array in a digital pattern-recognition machine, classifying each input pattern, and performing a prescribed physical manipulation of each article in response to the result of classifying the pattern borne by that article;
wherein the machine comprises a storage device and a library of prototype patterns stored within the storage device, each prototype pattern belongs to one of a multiplicity of known classes, and each prototype pattern is labeled with its respective class; and
the classifying step comprises, in said machine;a) for each input pattern, retrieving each of the prototype patterns from the storage device and evaluating a distance function d1 between the input pattern and each of the prototype patterns, wherein d1 is the first of a plurality of distance functions di, i=1, . . . , M, M a positive integer at least 2; b) responsive to (a), keeping the K1 closest prototype patterns and eliminating from consideration the rest of the prototype patterns, wherein K1 is a positive integer less than the total number of prototype patterns in the library; c) evaluating at least one further distance function dj between the input pattern and at least some of the K1 closest prototype patterns, wherein j is a positive integer at least 2 and at most M; d) responsive to the evaluation of each further distance function di, i=2, . . . M, keeping the Ki closest prototype patterns and eliminating from consideration the rest of the prototype patterns, wherein Ki is a positive integer less than Ki-1 ; and e) choosing the best class, according to an appropriate decision procedure, from the classes represented in a population of prototype patterns that is limited in response to the evaluation of the last distance function dM, wherein; f) each evaluation of step (c) is carded out between the input pattern and the Kj-1 closest prototype patterns that were kept in response to the evaluation of the last preceding distance function dj-1 ; g) at least one of the further distance functions di, i at least 2, such distance to be referred to as a tangent distance of complexity Li, is evaluated with reference to a set of image transformations that are selected to leave the respective classes of the prototype patterns invariant, and such evaluation comprises the further steps of; generating Li tangent vectors from a subset of said image transformations, wherein Li is at least 1, and the Li tangent vectors define a prototype hyperplane containing a prototype pattern; and evaluating a Euclidean distance with respect to a transformed pattern lying on the prototype hyperplane.
- converting each input pattern to a pixel array, storing the pixel array in a digital pattern-recognition machine, classifying each input pattern, and performing a prescribed physical manipulation of each article in response to the result of classifying the pattern borne by that article;
Specification